Fooling Algorithms in Non-Stationary Bandits using Belief Inertia
TL;DR
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 that yields an algorithmic separation.
Abstract
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, $\epsilon$-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\geq 2$ and every window $K\leq\tau\leq T$, we prove the finite gap-free lower bound $\frac{1}{20}\min\{T,(K\ln T)^{1/3}T^{2/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(\sqrt{KT\ln(KT)})$, whereas SW-UCB necessarily incurs $\Omega((K\ln T)^{1/3}T^{2/3})$ until the linear cap becomes active, regardless of how its window is tuned. Thus, with respect to the horizon, the class admits essentially $T^{1/2}$ regret while SW-UCB necessarily incurs $T^{2/3}$ regret. This shows that the $T^{2/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.
