Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

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.

Machine Learning (cs.LG); Probability (math.PR); Machine Learning (stat.ML)

arXiv:2511.05620 [cs.LG]

(or arXiv:2511.05620v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2511.05620 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.