mlsanityData to 7 Oct 2026

An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits

arXiv 1702.06103 ↗First posted 20 Feb 2017cs.LG stat.MLcited by 43

Not on the map. Why?

Abstract (arXiv)

We present a new strategy for gap estimation in randomized algorithms for multiarmed bandits and combine it with the EXP3++ algorithm of Seldin and Slivkins (2014). In the stochastic regime the strategy reduces dependence of regret on a time horizon from (ln t)3 to (ln t)2 and eliminates an additive factor of order Delta e1/Delta2, where Delta is the minimal gap of a problem instance. In the adversarial regime regret guarantee remains unchanged.

Key facts. Cited by 43 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 Feb 2017.

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: 10; 2024: 8; 2025: 2; 2026: 2.

43 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. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  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. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  11. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  12. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
31 more
  1. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  2. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  3. 2023Best of Both Worlds Policy Optimizationcited by 17
  4. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  5. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  6. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  7. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  8. 2022Best of Both Worlds Model Selectioncited by 11
  9. 2022Pareto Regret Analyses in Multi-objective Multi-armed Banditcited by 11
  10. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  11. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  12. 2024Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraintscited by 10
  13. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 9
  14. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  15. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  16. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  17. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  18. 2021Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximationscited by 4
  19. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  20. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  21. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  22. 2023CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruptioncited by 2
  23. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  24. 2024Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approachcited by 2
  25. 2025Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedbackcited by 2
  26. 2022SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzingcited by 1
  27. 2024Stochastic Bandits Robust to Adversarial Attackscited by 1
  28. 2026Best of both worlds: Stochastic & adversarial best-arm identificationcited by 1
  29. 2023Allocating Divisible Resources on Arms with Unknown and Random Rewardscited by 0
  30. 2025Hierarchical Adversarial Bandits for Online Configuration Optimizationcited by 0
  31. 2026Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leadercited by 0