Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
This paper shows that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al.