Abstract
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(T^2/3) in the oblivious adversarial setting and a bound of O(min{log (T)/Δ²,T^2/3}) in the stochastically-constrained regime, both with (unit) switching costs, where Δ 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(T^1/3/Δ). We accompany our results with a lower bound showing that, in general, Ω(min{1/Δ²,T^2/3}) regret is unavoidable in the stochastically-constrained case for algorithms with O(T^2/3) worst-case regret.