# Better Best of Both Worlds Bounds for Bandits with Switching Costs

arXiv: https://arxiv.org/abs/2206.03098 · HTML: https://mlsanity.com/paper/2206.03098/

## Key facts

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

## Builds on (most cited first, 10 of 10)

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2103.12487/) (2021)

## Built on by (most cited first, 13 of 13)

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms](https://mlsanity.com/paper/2302.13534/) (2023)
- [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Understanding the Role of Feedback in Online Learning with Switching Costs](https://mlsanity.com/paper/2306.09588/) (2023)
- [Learning the Optimal Path and DNN Partition for Collaborative Edge Inference](https://mlsanity.com/paper/2410.01857/) (2024)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Safe Exploitative Play with Untrusted Type Beliefs](https://mlsanity.com/paper/2411.07679/) (2024)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)
- [Beyond Binary: Continuous State Optimization with Graph-Structured Objectives](https://mlsanity.com/paper/2608.09366/) (2026)

## 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.