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

arXiv: https://arxiv.org/abs/2502.04678 · HTML: https://mlsanity.com/paper/2502.04678/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 21 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 17 of 17)

- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Learning to Bid in Repeated First-Price Auctions with Budgets](https://mlsanity.com/paper/2304.13477/) (2023)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Efficient Contextual Bandits with Uninformed Feedback Graphs](https://mlsanity.com/paper/2402.08127/) (2024)
- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Graph Feedback Bandits with Similar Arms](https://mlsanity.com/paper/2405.11171/) (2024)
- [High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions](https://mlsanity.com/paper/2410.04080/) (2024)

## Built on by (most cited first, 1 of 1)

- [Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces](https://mlsanity.com/paper/2606.27917/) (2026)

## Abstract (arXiv)

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(√α 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(√α 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.