Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

Gal Mendelson, Eyal Tadmor

We study the problem of worst case regret in piecewise stationary multi armed bandits. While the minimax theory for stationary bandits is well established, understanding analogous…