Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback (arxiv.org)
arXiv:2502.04678v2 Announce Type: replace
Abstract: Repeated first-price auctions are contextual decision problems with censored but reusable feedback: after submitting a bid, a learner can infer the outcomes of related bids and evaluate them under different private values. This structure motivates cross-learning contextual bandits with graphical feedback, where playing an arm reveals the losses of its out-neighbors in every context. A central open question was whether, under i.i.d. contexts and a fixed strongly observable feedback graph with independence number $\alpha$, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate $\widetilde O(\sqrt{\alpha T})$. The question was open even for stochastic losses and graphs in which every arm has a self-loop. We answer it affirmatively under the stronger model of oblivious adversarial losses and for all strongly observable graphs, including those with arms without self-loops. The key obstruction is that a frequently played no-self-loop arm can nevertheless have a vanishing observation probability. Our algorithm isolates one such arm per epoch, uses a pessimistic correction to cancel its first-order estimation drift, and shifts the losses in the FTRL analysis to control the resulting quadratic term. It achieves expected regret $\widetilde O(\sqrt{\alpha T})$. Controlled synthetic experiments show the benefit of combining graph feedback with cross-learning and exhibit the predicted scaling in both $T$ and $\alpha$. The main theorem is formalized in Lean in an end-to-end development exceeding 100,000 lines of Lean code. The formalization and experiment artifacts are available in the GitHub repository: https://github.com/RuiyuanHuang/graphical-cross-learning-review-artifact.
Abstract: Repeated first-price auctions are contextual decision problems with censored but reusable feedback: after submitting a bid, a learner can infer the outcomes of related bids and evaluate them under different private values. This structure motivates cross-learning contextual bandits with graphical feedback, where playing an arm reveals the losses of its out-neighbors in every context. A central open question was whether, under i.i.d. contexts and a fixed strongly observable feedback graph with independence number $\alpha$, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate $\widetilde O(\sqrt{\alpha T})$. The question was open even for stochastic losses and graphs in which every arm has a self-loop. We answer it affirmatively under the stronger model of oblivious adversarial losses and for all strongly observable graphs, including those with arms without self-loops. The key obstruction is that a frequently played no-self-loop arm can nevertheless have a vanishing observation probability. Our algorithm isolates one such arm per epoch, uses a pessimistic correction to cancel its first-order estimation drift, and shifts the losses in the FTRL analysis to control the resulting quadratic term. It achieves expected regret $\widetilde O(\sqrt{\alpha T})$. Controlled synthetic experiments show the benefit of combining graph feedback with cross-learning and exhibit the predicted scaling in both $T$ and $\alpha$. The main theorem is formalized in Lean in an end-to-end development exceeding 100,000 lines of Lean code. The formalization and experiment artifacts are available in the GitHub repository: https://github.com/RuiyuanHuang/graphical-cross-learning-review-artifact.
Comments