# An Algorithm for Stochastic and Adversarial Bandits with Switching Costs

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 18 references that are in the map.
- First posted on arXiv 19 Feb 2021.

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

- [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)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020)
- [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)

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

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [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)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023)
- [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)
- [Better Best of Both Worlds Bounds for Bandits with Switching Costs](https://mlsanity.com/paper/2206.03098/) (2022)
- [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)
- [Multi-Drafter Speculative Decoding with Alignment Feedback](https://mlsanity.com/paper/2604.05417/) (2026)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (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)
- [Phase Transitions in Learning and Earning under Price Protection Guarantee](https://mlsanity.com/paper/2211.01798/) (2022)
- [Adversarial Combinatorial Bandits with Switching Costs](https://mlsanity.com/paper/2404.01883/) (2024)
- [The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs](https://mlsanity.com/paper/2410.14533/) (2024)
- [Learning in Markovian bandits with non-observable states and constrained decision epochs](https://mlsanity.com/paper/2606.27448/) (2026)
- [Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees](https://mlsanity.com/paper/2610.14790/) (2026)

## Abstract (arXiv)

We propose an algorithm for stochastic and adversarial multiarmed bandits with switching costs, where the algorithm pays a price λ every time it switches the arm being played. Our algorithm is based on adaptation of the Tsallis-INF algorithm of Zimmert and Seldin (2021) and requires no prior knowledge of the regime or time horizon. In the oblivious adversarial setting it achieves the minimax optimal regret bound of Obig((λ K)1/3T2/3 + √KTbig), where T is the time horizon and K is the number of arms. In the stochastically constrained adversarial regime, which includes the stochastic regime as a special case, it achieves a regret bound of Oleft(big((λ K)2/3 T1/3 + ln Tbig)sumi neq i^* Deltai-1right), where Deltai are the suboptimality gaps and i^* is a unique optimal arm. In the special case of λ = 0 (no switching costs), both bounds are minimax optimal within constants. We also explore variants of the problem, where switching cost is allowed to change over time. We provide experimental evaluation showing competitiveness of our algorithm with the relevant baselines in the stochastic, stochastically constrained adversarial, and adversarial regimes with fixed switching cost.