# Online Learning with Feedback Graphs: Beyond Bandits

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2015.

## Built on by (most cited first, 30 of 80)

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [Exploiting Correlated Auxiliary Feedback in Parameterized Bandits](https://mlsanity.com/paper/2311.02715/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback](https://mlsanity.com/paper/2206.07908/) (2022)
- [Efficient Contextual Bandits with Uninformed Feedback Graphs](https://mlsanity.com/paper/2402.08127/) (2024)
- [Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models](https://mlsanity.com/paper/2601.22538/) (2026)
- [Dueling Bandits with Adversarial Sleeping](https://mlsanity.com/paper/2107.02274/) (2021)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Topological Structure Learning Should Be A Research Priority for LLM-Based Multi-Agent Systems](https://mlsanity.com/paper/2505.22467/) (2025)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)

## Abstract (arXiv)

We study a general class of online learning problems where the feedback is specified by a graph. This class includes online prediction with expert advice and the multi-armed bandit problem, but also several learning problems where the online player does not necessarily observe his own loss. We analyze how the structure of the feedback graph controls the inherent difficulty of the induced T-round learning problem. Specifically, we show that any feedback graph belongs to one of three classes: strongly observable graphs, weakly observable graphs, and unobservable graphs. We prove that the first class induces learning problems with widetildeTheta(α1/2 T1/2) minimax regret, where α is the independence number of the underlying graph; the second class induces problems with widetildeTheta(δ1/3T2/3) minimax regret, where δ is the domination number of a certain portion of the graph; and the third class induces problems with linear minimax regret. Our results subsume much of the previous work on learning with feedback graphs and reveal new connections to partial monitoring games. We also show how the regret is affected if the graphs are allowed to vary with time.