mlsanityData to 7 Oct 2026

A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs

arXiv 2206.00557 ↗First posted 1 Jun 2022cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both stochastic and adversarial environments. The bound against oblivious adversaries is tildeO (√α T), where T is the time horizon and α is the independence number of the feedback graph. The bound against stochastic environments is Obig( (ln T)2 maxS∈ mathcal I(G) sumi ∈ S Deltai-1big) where mathcal I(G) is the family of all independent sets in a suitably defined undirected version of the graph and Deltai are the suboptimality gaps. The algorithm combines ideas from the EXP3++ algorithm for stochastic and adversarial bandits and the EXP3.G algorithm for feedback graphs with a novel exploration scheme. The scheme, which exploits the structure of the graph to reduce exploration, is key to obtain best-of-both-worlds guarantees with feedback graphs. We also extend our algorithm and results to a setting where the feedback graphs are allowed to change over time.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 23 of its 51 references that are in the map. First posted on arXiv 1 Jun 2022.

Builds on

23 of 51 references.

References · 23

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2014A Second-order Bound with Excess Lossescited by 91
  5. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 79
  6. 2014Nonstochastic Multi-Armed Bandits with Graph-Structured Feedbackcited by 61
  7. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  8. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  9. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  10. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  11. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  12. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
11 more
  1. 2018On the optimality of the Hedge algorithm in the stochastic regimecited by 32
  2. 2016Online Learning with Feedback Graphs Without the Graphscited by 27
  3. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
  4. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  5. 2019Feedback graph regret bounds for Thompson Sampling and UCBcited by 17
  6. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  7. 2021Beyond Bandit Feedback in Online Multiclass Classificationcited by 14
  8. 2016Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learningcited by 13
  9. 2017Reward Maximization Under Uncertainty: Leveraging Side-Observations on Networkscited by 8
  10. 2021Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizerscited by 8
  11. 2018Adaptation to Easy Data in Prediction with Limited Advicecited by 7

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 7; 2024: 3; 2025: 4.

17 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. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  4. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  5. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  6. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  7. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  8. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  9. 2025Topological Structure Learning Should Be A Research Priority for LLM-Based Multi-Agent Systemscited by 5
  10. 2023On Interpolating Experts and Multi-Armed Banditscited by 4
  11. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  12. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
5 more
  1. 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
  2. 2025Pure Exploration with Feedback Graphscited by 3
  3. 2023Stochastic Graph Bandit Learning with Side-Observationscited by 1
  4. 2025A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyondcited by 0
  5. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0