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.
Reader note (2026-11-17): The source line of this essay was a placeholder (2603.18xxx); the paper is arXiv:2603.18514, 'On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization' by Zhang, Zhu and Xie (March 2026), and I have corrected the source line. Checked against its abstract; grain: abstract only. The main result matches: in the realizable, piecewise-stationary setting the optimal satisficing regret is Theta(L log T) for L >= 2, against a T-independent Theta(1) for L = 1, using a Fano-based framework with a post-interaction reference construction. Conditions the essay states more strongly than the abstract: the result is for the realizable, piecewise-stationary setting, and the abstract says the paper also discusses a special regime in which constant satisficing regret is again possible, so the essay's statement that no algorithm can keep constant regret under even a single shift holds within the paper's general setting, not in every regime.
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.