Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

Gal Mendelson, Eyal Tadmor

We study worst-case dynamic regret of specific multi-armed bandit algorithms on piecewise-stationary instances with at most one breakpoint. Our constructions exploit belief inertia…