mlsanityData to 7 Oct 2026

Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs

arXiv 2206.00873 ↗First posted 2 Jun 2022cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

This study considers online learning with general directed feedback graphs. For this problem, we present best-of-both-worlds algorithms that achieve nearly tight regret bounds for adversarial environments as well as poly-logarithmic regret bounds for stochastic environments. As Alon et al. [2015] have shown, tight regret bounds depend on the structure of the feedback graph: strongly observable graphs yield minimax regret of tildeTheta( α1/2 T1/2 ), while weakly observable graphs induce minimax regret of tildeTheta( δ1/3 T2/3 ), where α and δ, respectively, represent the independence number of the graph and the domination number of a certain portion of the graph. Our proposed algorithm for strongly observable graphs has a regret bound of tildeO( α1/2 T1/2 ) for adversarial environments, as well as of O ( fracα (ln T)3 Deltamin ) for stochastic environments, where Deltamin expresses the minimum suboptimality gap. This result resolves an open question raised by Erez and Koren [2021]. We also provide an algorithm for weakly observable graphs that achieves a regret bound of tildeO( δ1/3T2/3 ) for adversarial environments and poly-logarithmic regret for stochastic environments. The proposed algorithms are based on the follow-the-regularized-leader approach combined with newly designed update rules for learning rates.

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

Builds on

17 of 51 references.

References · 17

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2014A Second-order Bound with Excess Lossescited by 91
  5. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  6. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 79
  7. 2014Nonstochastic Multi-Armed Bandits with Graph-Structured Feedbackcited by 61
  8. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  9. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  10. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  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
5 more
  1. 2016Online Learning with Feedback Graphs Without the Graphscited by 27
  2. 2020Prediction with Corrupted Expert Advicecited by 26
  3. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  4. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  5. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 9; 2024: 7; 2025: 5; 2026: 2.

26 papers.

Sort:

  1. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  2. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  3. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  4. 2023Best of Both Worlds Policy Optimizationcited by 17
  5. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  6. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  7. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  8. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  9. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  10. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  11. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  12. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
14 more
  1. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  2. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
  3. 2022Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphscited by 5
  4. 2024Information Capacity Regret Bounds for Bandits with Mediator Feedbackcited by 4
  5. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  6. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
  7. 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
  8. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  9. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  10. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  11. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  12. 2025A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyondcited by 0
  13. 2025Multi-Play Combinatorial Semi-Bandit Problemcited by 0
  14. 2026Leveraging Similarities in Multi-Armed Banditscited by 0