mlsanityData to 7 Oct 2026

An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits

arXiv 1605.08722 ↗First posted 27 May 2016cs.LGcited by 47

Not on the map. Why?

Abstract (arXiv)

We present an algorithm that achieves almost optimal pseudo-regret bounds against adversarial and stochastic bandits. Against adversarial bandits the pseudo-regret is O(K√n log n) and against stochastic bandits the pseudo-regret is O(sumi (log n)/Deltai). We also show that no algorithm with O(log n) pseudo-regret against stochastic bandits can achieve tildeO(√n) expected regret against adaptive adversarial bandits. This complements previous results of Bubeck and Slivkins (2012) that show tildeO(√n) expected adversarial regret with O((log n)2) stochastic pseudo-regret.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 15; 2023: 8; 2024: 5; 2025: 2; 2026: 4.

47 papers.

Sort:

By area:

  1. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  2. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  3. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  4. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  5. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  6. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  7. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  8. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  9. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  10. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  11. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  12. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
35 more
  1. 2023Best of Both Worlds Policy Optimizationcited by 17
  2. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  3. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  4. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  5. 2022Best of Both Worlds Model Selectioncited by 11
  6. 2022Pareto Regret Analyses in Multi-objective Multi-armed Banditcited by 11
  7. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  8. 2024Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraintscited by 10
  9. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  10. 2021Robust Bandit Learning with Imperfect Contextcited by 8
  11. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  12. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  13. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  14. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  15. 2021Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximationscited by 4
  16. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  17. 2022Best of Many Worlds Guarantees for Online Learning with Knapsackscited by 4
  18. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  19. 2023Byzantine-Resilient Decentralized Multi-Armed Banditscited by 3
  20. 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
  21. 2022Bridging Adversarial and Nonstationary Multi-armed Banditcited by 2
  22. 2022AutoFR: Automated Filter Rule Generation for Adblockingcited by 2
  23. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  24. 2022Contextual Bandits and Optimistically Universal Learningcited by 2
  25. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  26. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  27. 2025Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedbackcited by 2
  28. 2023MNL-Bandit in non-stationary environmentscited by 1
  29. 2026Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Lossescited by 1
  30. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  31. 2026Best of both worlds: Stochastic & adversarial best-arm identificationcited by 1
  32. 2021Towards the D-Optimal Online Experiment Design for Recommender Selectioncited by 0
  33. 2023Decentralized Online Bandit Optimization on Directed Graphs with Regret Boundscited by 0
  34. 2025A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyondcited by 0
  35. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0