An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
  We propose an algorithm for stochastic and adversarial multiarmed bandits
with switching costs, where the algorithm pays a price $\lambda$ 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 $O\big((\lambda K)^{1/3}T^{2/3}
+ \sqrt{KT}\big)$, 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
$O\left(\big((\lambda K)^{2/3} T^{1/3} + \ln T\big)\sum_{i \neq i^*}
\Delta_i^{-1}\right)$, where $\Delta_i$ are the suboptimality gaps and $i^*$ is
a unique optimal arm. In the special case of $\lambda = 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.
