Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

תקציר מקורי באנגליתarXiv:2511.05620v2 Announce Type: replace 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