mlsanityData to 7 Oct 2026

Online Learning with Feedback Graphs: Beyond Bandits

arXiv 1502.07617 ↗First posted 26 Feb 2015cs.LGcited by 79

Not on the map. Why?

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.

Key facts. Cited by 79 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Feb 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 13; 2023: 13; 2024: 12; 2025: 15; 2026: 18.

79 papers.

Sort:

By area:

  1. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  2. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  3. 2022An Analysis of Ensemble Samplingcited by 23
  4. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  5. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  6. 2022Contextual Information-Directed Samplingcited by 16
  7. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  8. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  9. 2021Understanding Bandits with Graph Feedbackcited by 14
  10. 2021Beyond Bandit Feedback in Online Multiclass Classificationcited by 14
  11. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  12. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
38 more
  1. 2024Improved Algorithms for Contextual Dynamic Pricingcited by 11
  2. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  3. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  4. 2021Online Selective Classification with Limited Feedbackcited by 8
  5. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  6. 2023Online Learning with Set-Valued Feedbackcited by 7
  7. 2025Nearly Tight Regret Bounds for Profit Maximization in Bilateral Tradecited by 7
  8. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  9. 2023Exploiting Correlated Auxiliary Feedback in Parameterized Banditscited by 6
  10. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
  11. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  12. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  13. 2022Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphscited by 5
  14. 2023Online Learning with Feedback Graphs: The True Shape of Regretcited by 5
  15. 2024Stochastic contextual bandits with graph feedback: from independence number to MAS numbercited by 5
  16. 2025Topological Structure Learning Should Be A Research Priority for LLM-Based Multi-Agent Systemscited by 5
  17. 2021Cooperative Online Learning with Feedback Graphscited by 4
  18. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  19. 2022Online Learning with Off-Policy Feedbackcited by 4
  20. 2023On Interpolating Experts and Multi-Armed Banditscited by 4
  21. 2023Apple Tasting: Combinatorial Dimensions and Minimax Ratescited by 4
  22. 2024Information Capacity Regret Bounds for Bandits with Mediator Feedbackcited by 4
  23. 2024Deterministic Apple Tastingcited by 4
  24. 2026Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Modelscited by 4
  25. 2026Online learning with noisy side observationscited by 4
  26. 2022Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimalitycited by 3
  27. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  28. 2024Improved Regret Bounds for Bandits with Expert Advicecited by 3
  29. 2024Adversarial Online Learning with Temporal Feedback Graphscited by 3
  30. 2025Pure Exploration with Feedback Graphscited by 3
  31. 2025Optimal Arm Elimination Algorithms for Combinatorial Banditscited by 3
  32. 2021Online Learning with Uncertain Feedback Graphscited by 2
  33. 2024Learning from Snapshots of Discrete and Continuous Data Streamscited by 2
  34. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  35. 2025Graph Learning Is Suboptimal in Causal Banditscited by 2
  36. 2026Revealing graph bandits for maximizing local influencecited by 2
  37. 2022Improved Algorithms for Bandit with Graph Feedback via Regret Decompositioncited by 1
  38. 2023Regret Lower Bounds in Multi-agent Multi-armed Banditcited by 1

50 most cited of 79 All 79 (JSON)