Research
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 cons
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 Kgeq 2 and every window Kleqauleq T, we prove the finite gap-free lower bound frac{1}{20}min{T,(Kln 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{KTln(KT)}), whereas SW-UCB necessarily incurs Omega((Kln 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.
Related
- Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
- A Modularized Framework for Piecewise-Stationary Restless Bandits
- Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer
- Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
- On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
Source: arXiv cs.LG | 2026-09-30