← All papers
First page of Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

Ruiyuan Huang, Zengfeng Huang

cs.LG Feb 7, 2025 · v2
The main regret theorem is formalized end-to-end in Lean, in more than 100,000 lines with a public artifact repository; GPT-5.6 assisted the formalization.
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 $α$, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate $\widetilde O(\sqrt{α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{αT})$. Controlled synthetic experiments show the benefit of combining graph feedback with cross-learning and exhibit the predicted scaling in both $T$ and $α$. 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.

Cross-learning contextual bandits with graphical feedback model settings such as repeated first-price auctions. An open question was whether, with i.i.d. contexts and a strongly observable feedback graph, regret of order sqrt(alpha T) is achievable without polynomial dependence on the number of contexts. Here alpha is the graph's independence number.

The algorithm is an FTRL method with a negative-entropy regularizer and implicit-exploration estimators. It isolates one under-observed no-self-loop arm per epoch and applies a pessimistic correction to cancel that arm's first-order estimation drift. Losses are shifted in the FTRL analysis to control the resulting quadratic term. The main theorem is formalized in Lean in an end-to-end development of over 100,000 lines.

The algorithm achieves expected regret of order sqrt(alpha T) up to log factors. This holds for oblivious adversarial losses and all strongly observable graphs, with only logarithmic dependence on the number of contexts. Synthetic experiments show the predicted scaling in T and alpha.