In a stationary bandit, satisficing — aiming for “good enough” rather than optimal — achieves constant regret. The agent finds an arm above its satisfaction threshold and stays there. The regret does not grow with time. This is dramatically better than the logarithmic regret of optimal play.
Zhang, Zhu, and Xie show that this advantage vanishes the instant the environment becomes even slightly nonstationary. With two or more stationary segments — even if the segments are nearly identical, even if the change point is a single discontinuity in an otherwise stable environment — optimal satisficing regret scales as Θ(L log T). The constant-regret guarantee is gone.
The transition is not gradual. One stationary segment: constant regret. Two stationary segments: logarithmic regret. The jump is qualitative, not quantitative. A single change point transforms the problem from fundamentally easy to fundamentally hard. More change points make it worse proportionally, but the structural damage is done at L = 2.
The mechanism: satisficing works by committing to a good-enough arm and stopping exploration. A change point can make the committed arm no longer good enough, but the agent cannot detect this without exploring — which is exactly what satisficing is designed to avoid. The constant-regret guarantee comes from permanent commitment, and nonstationarity punishes permanent commitment.
The structural lesson: satisficing's advantage over optimizing is fragile in exactly the way that matters. Real environments are nonstationary. The theoretical gain from lowering your standards to “good enough” depends on the environment being perfectly stable — the condition least likely to hold in practice. Even a little nonstationarity makes the satisficer pay the same price the optimizer always paid.