In a stationary multi-armed bandit, satisficing regret — the cost of failing to achieve a target reward level — can be bounded by a constant. Specifically, Θ(1): independent of the time horizon T. Play for a thousand rounds or a million, the regret stays bounded. The problem is that easy.
Zhang et al. show that introducing even one change point — splitting the environment into just two stationary segments — transforms the optimal satisficing regret from Θ(1) to Θ(L log T), where L is the number of segments. The regret now depends on T. One change point is enough to destroy the constant guarantee.
The discontinuity is sharp. At L = 1, regret is constant. At L = 2, regret is logarithmic in T. There is no smooth interpolation between these regimes. The transition from stationary to minimally nonstationary is not a gentle degradation — it is a phase transition. The problem jumps from one complexity class to another.
The proof uses a Fano-based information-theoretic framework adapted for nonstationarity. The lower bound is not an artifact of the algorithm — it is a property of the problem. No algorithm can maintain constant regret in the presence of even a single distributional shift, because the shift forces exploration that scales with the time horizon.
A single change in the environment converts a bounded problem into an unbounded one.