mlsanityData to 7 Oct 2026

Better Best of Both Worlds Bounds for Bandits with Switching Costs

arXiv 2206.03098 ↗First posted 7 Jun 2022cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

We study best-of-both-worlds algorithms for bandits with switching cost, recently addressed by Rouyer, Seldin and Cesa-Bianchi, 2021. We introduce a surprisingly simple and effective algorithm that simultaneously achieves minimax optimal regret bound of O(T2/3) in the oblivious adversarial setting and a bound of O(minlog (T)/Delta2,T2/3) in the stochastically-constrained regime, both with (unit) switching costs, where Delta is the gap between the arms. In the stochastically constrained case, our bound improves over previous results due to Rouyer et al., that achieved regret of O(T1/3/Delta). We accompany our results with a lower bound showing that, in general, tildeOmega(min1/Delta2,T2/3) regret is unavoidable in the stochastically-constrained case for algorithms with O(T2/3) worst-case regret.

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

Builds on

10 of 34 references.

References · 10

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  2. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  3. 2019Batched Multi-armed Bandits Problemcited by 97
  4. 2019Regret Bounds for Batched Banditscited by 49
  5. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  6. 2015Fighting Bandits with a New Kind of Smoothnesscited by 45
  7. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  8. 2013Bandits with Switching Costs: T^{2/3} Regretcited by 38
  9. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  10. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 3; 2025: 4; 2026: 2.

13 papers.

Sort:

  1. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  2. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  3. 2023Best of Both Worlds Policy Optimizationcited by 17
  4. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  5. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  6. 2023Understanding the Role of Feedback in Online Learning with Switching Costscited by 3
  7. 2024Learning the Optimal Path and DNN Partition for Collaborative Edge Inferencecited by 3
  8. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
  9. 2024Safe Exploitative Play with Untrusted Type Beliefscited by 0
  10. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  11. 2025Fairness-Regularized Online Optimization with Switching Costscited by 0
  12. 2026SCaLE: Switching Cost aware Learning and Explorationcited by 0
1 more
  1. 2026Beyond Binary: Continuous State Optimization with Graph-Structured Objectivescited by 0