# On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 19 Mar 2026.

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

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Thresholding Bandits with Augmented UCB](https://mlsanity.com/paper/1704.02281/) (2017)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Guaranteed satisficing and finite regret: Analysis of a cognitive satisficing value function](https://mlsanity.com/paper/1812.05795/) (2018)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)

## Abstract (arXiv)

Motivated by the principle of satisficing in decision-making, we study satisficing regret guarantees for nonstationary K-armed bandits. We show that in the general realizable, piecewise-stationary setting with L stationary segments, the optimal regret is Theta(Llog T) as long as L≥ 2. This stands in sharp contrast to the case of L=1 (i.e., the stationary setting), where a T-independent Theta(1) satisficing regret is achievable under realizability. In other words, the optimal regret has to scale with T even if just a little nonstationarity presents. A key ingredient in our analysis is a novel Fano-based framework tailored to nonstationary bandits via a post-interaction reference construction. This framework strictly extends the classical Fano method for passive estimation as well as recent interactive Fano techniques for stationary bandits. As a complement, we also discuss a special regime in which constant satisficing regret is again possible.