Satisficing Regret Minimization under Nonstationarity

Motivated by the principle of satisficing in decision-making, we study satisficing regret minimization for piecewise-stationary $K$-armed bandits. Prior work has shown that, under stationarity and realizability, satisficing regret can be bounded independently of the horizon $T$. Our main finding is that the difficulty of the problem is not determined by the number of stationary segments $L$, but rather by the number of down-crossings $D$, namely, changes at which a previously satisficing arm becomes non-satisficing. When $D \geq 1$, we establish lower bounds showing that, in the fixed-gap regime, unknown down-crossings necessarily incur regret that grows logarithmically with $T$. We develop a unified algorithm that requires no prior knowledge of either $L$ or $D$. In the fixed-gap regime, where $\Delta$ denotes the gap between arm means and the satisficing threshold, its satisficing regret scales as $ \mathcal O\left( \frac{K(D+1)}{\Delta} \log\left(\frac{1}{\Delta}\right) + \frac{D\log T}{\Delta} \right),$ matching the lower bound whenever $D \geq 1$. When $D=0$, the same algorithm achieves $T$-independent regret, recovering the stationary scaling when $L=1$ and extending it to nonstationary environments with no down-crossings, even when $L$ is arbitrarily large.