mlsanityData to 7 Oct 2026

A Blackbox Approach to Best of Both Worlds in Bandits and Beyond

arXiv 2302.09739 ↗First posted 20 Feb 2023cs.LG cs.AI stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

Best-of-both-worlds algorithms for online learning which achieve near-optimal regret in both the adversarial and the stochastic regimes have received growing attention recently. Existing techniques often require careful adaptation to every new problem setup, including specialised potentials and careful tuning of algorithm parameters. Yet, in domains such as linear bandits, it is still unknown if there exists an algorithm that can simultaneously obtain O(log(T)) regret in the stochastic regime and tildeO(√T) regret in the adversarial regime. In this work, we resolve this question positively and present a general reduction from best of both worlds to a wide family of follow-the-regularized-leader (FTRL) and online-mirror-descent (OMD) algorithms. We showcase the capability of this reduction by transforming existing algorithms that are only known to achieve worst-case guarantees into new algorithms with best-of-both-worlds guarantees in contextual bandits, graph bandits and tabular Markov decision processes.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 37 of its 60 references that are in the map. First posted on arXiv 20 Feb 2023.

Builds on

37 of 60 references.

References · 37

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2016Corralling a Band of Bandit Algorithmscited by 99
  6. 2014A Second-order Bound with Excess Lossescited by 91
  7. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  8. 2021Adapting to Misspecification in Contextual Banditscited by 81
  9. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 79
  10. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  11. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  12. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
25 more
  1. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  2. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  3. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  4. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  5. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  6. 2018On the optimality of the Hedge algorithm in the stochastic regimecited by 32
  7. 2013From Bandits to Experts: A Tale of Domination and Independencecited by 28
  8. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  9. 2019Connections Between Mirror Descent, Thompson Sampling and the Information Ratiocited by 23
  10. 2020Corralling Stochastic Bandit Algorithmscited by 23
  11. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  12. 2019Improved Path-length Regret Bounds for Banditscited by 22
  13. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  14. 2020Regret Balancing for Bandit and RL Model Selectioncited by 20
  15. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  16. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  17. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  18. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  19. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  20. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  21. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  22. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  23. 2022Best of Both Worlds Model Selectioncited by 11
  24. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  25. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 10; 2025: 7; 2026: 2.

29 papers.

Sort:

  1. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  2. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  3. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  4. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  5. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  6. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  7. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 9
  8. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  9. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  10. 2023Accelerated Rates between Stochastic and Adversarial Online Convex Optimizationcited by 7
  11. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  12. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
17 more
  1. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  2. 2023On Interpolating Experts and Multi-Armed Banditscited by 4
  3. 2024Information Capacity Regret Bounds for Bandits with Mediator Feedbackcited by 4
  4. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  5. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
  6. 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
  7. 2025Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problemscited by 3
  8. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  9. 2025Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedbackcited by 2
  10. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  11. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  12. 2023Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed banditscited by 1
  13. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  14. 2025A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyondcited by 0
  15. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  16. 2026Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leadercited by 0
  17. 2026Leveraging Similarities in Multi-Armed Banditscited by 0