# Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

arXiv: https://arxiv.org/abs/2511.05620 · HTML: https://mlsanity.com/paper/2511.05620/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 19 references that are in the map.
- First posted on arXiv 6 Nov 2025.

## Builds on (most cited first, 8 of 8)

- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits](https://mlsanity.com/paper/1507.04523/) (2015)
- [Self-Concordant Analysis of Generalized Linear Bandits with Forgetting](https://mlsanity.com/paper/2011.00819/) (2020)
- [A Change-Detection Based Thompson Sampling Framework for Non-Stationary Bandits](https://mlsanity.com/paper/2009.02791/) (2020)
- [Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection](https://mlsanity.com/paper/1302.3721/) (2013)
- [Bridging Adversarial and Nonstationary Multi-armed Bandit](https://mlsanity.com/paper/2201.01628/) (2022)

## Abstract (arXiv)

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.