Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

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: observations collected before a change can make an algorithm slow to revise the empirical ordering on which its decisions are based. We first illustrate this mechanism for Explore-Then-Commit, ε-greedy, and UCB, for which deterministic one-breakpoint instances can produce linear regret. Our principal result concerns standard sliding-window UCB (SW-UCB), which was designed to forget outdated observations. For every K≥ 2 and every window K≤τ≤ T, we prove the finite gap-free lower bound frac120minT,(Kln T)1/3T2/3 on its worst-case regret. The proof combines two deterministic obstructions: a stationary small-gap instance that makes repeated forgetting costly, and a one-breakpoint instance that creates a strict post-change index lock. This yields an algorithmic separation. The class with at most one breakpoint admits regret O(√KTln(KT)), whereas SW-UCB necessarily incurs Omega((Kln T)1/3T2/3) until the linear cap becomes active, regardless of how its window is tuned. Thus, with respect to the horizon, the class admits essentially T1/2 regret while SW-UCB necessarily incurs T2/3 regret. This shows that the T2/3 behavior appearing in gap-free analyses of forgetting policies is not merely an artifact of an upper-bound proof for SW-UCB. The comparison does not resolve the different dependence on K or the logarithmic factors. All constants are explicit, and the SW-UCB proof permits arbitrary non-anticipating randomized tie-breaking.