On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
Yixuan Zhang, Ruihao Zhu, Qiaomin Xie · 2026
Read On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization by Yixuan Zhang, Ruihao Zhu, Qiaomin Xie (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18514.txt.
Introduction
Zhang, Zhu, and Xie study satisficing regret in nonstationary multi-armed bandits. Satisficing seeks a good-enough arm rather than the best one, following Simon's principle. With two or more stationary segments, optimal regret grows as L log T, they prove. One stationary segment alone allows constant, T-free regret under realizability. Even a little nonstationarity thus forces regret to scale with time; a Fano-based framework drives the proof.
Catalog record
| CREATOR | Yixuan Zhang, Ruihao Zhu, Qiaomin Xie |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60039 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18514
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization Yixuan Zhang, Ruihao Zhu, Qiaomin Xie Abstract Motivated by the principle of satisficing in decision-making, we study satisficing regret guarantees for nonstationary K K -armed bandits. We show that in the general realizable, piecewise-stationary setting with L L stationary segments, the optimal regret is Θ ( L log T ) \Theta(L\log T) as long as L ≥ 2 L\geq 2 . This stands in sharp contrast to the case of L = 1 L=1 (i.e., the stationary setting), where a T T -independent Θ ( 1 ) \Theta(1) satisficing regret is achievable under realizability. In other words, the optimal regret has to scale with T 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. keywords nonstationary bandits, satisficing regret, fano methods, post-interaction reference † † runningtitle: On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization † † authors: Department of Industrial & Systems Engineering, University of Wisconsin-Madison [email protected] SC Johnson College of Business, Cornell University [email protected] Department of Industrial & Systems Engineering, University of Wisconsin-Madison [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction The multi-armed bandit (MAB) problem is a classical framework for studying the exploration–exploitation trade-off in sequential decision-making. In the standard MAB setting, a learner repeatedly chooses among K arms with unknown, arm-specific stationary reward distributions, with the goal of minimizing cumulative regret ( 26 , 17 ) . For the canonical MAB problem and its many variants, a rich literature has established sharp performance guarantees; see, for example, 18 . While identifying the optimal action is essential in some high-stakes settings, many practical applications only require a “good-enough,” or satisficing , decision. Introduced by 32 , satisficing aims for an acceptable solution rather than the absolute best one. This perspective is common in practice. For instance, recommendation and advertising systems often deploy a candidate only if its KPI exceeds a threshold S with sufficient confidence ( 16 , 35 ) , and inventory control typically targets a desired service level (e.g., 90–95%) to mitigate stockout costs ( 11 , 15 ) . These considerations motivate the study of satisficing bandits ( 33 , 22 , 27 , 10 , 14 ) , where the learner aims to pull a satisficing arm —an arm whose mean reward is no less than a prescribed threshold S —as often as possible. Performance is measured by the satisficing regret , defined as the cumulative shortfall of the selected arm’s mean reward relative to S . To the best of our knowledge, existing results on satisficing regret primarily focus on stationary environments: 33 , 22 , 27 study the K -armed bandit setting, 10 extend the framework to more general bandit optimization problems, and 14 study the average-reward Markov decision process setting. Under a realizability condition—namely, that at least one (initially) unknown arm is strictly satisficing with mean exceeding S —these works show that the satisficing regret can be bounded by a constant independent of the decision horizon T . In many real-world scenarios, however, stationarity fails: consumer preferences drift with seasons and trends ( 1 ) , and platform marketplaces (e.g., ride-hailing) experience demand surges and changing competitive conditions ( 4 ) . As a result, an arm’s reward distribution may evolve over time. Despite the growing literature on satisficing regret in stationary environments, much less is understood in the nonstationary setting that frequently arises in practice. Motivated by this gap, we study satisficing regret minimization under nonstationarity, focusing on piecewise-stationary bandits with L stationary segments. Building on the stationary case (corresponding to L=1 ), it is natural to ask: Can we similarly achieve a T -independent satisficing regret in the piecewise-stationary setting? At first glance, this appears plausible since if the change points were known in advance, one could simply restart a stationary satisficing algorithm on each segment, leading to an \mathcal{O}(L) satisficing regret. 1.1 Our Contributions In this work, however, we provide a negative answer to the above conjecture. Specifically, • In Section 4 , we establish an \Omega\bigl(L\log(T/L)\bigr) lower bound on the satisficing regret for nonstationary K -armed bandits. We then propose Algorithm 1 , which achieves an almost matching upper bound of \mathcal{O}(L\log T) . Together, these results show that the additional \log T factor is unavoidable in general when the change points are unknown, thereby ruling out the conjectured \mathcal{O}(L) satisficing regret guarantee. • To establish the lower bounds above, we extend recent interactive Fano techniques for bandit regret lower bounds ( 7 , 31 ) from stationary to nonstationary environments. More importantly, we introduce a post-interaction reference framework that strictly generalizes the classical Fano approach and is particularly well suited to nonstationary bandits. The key feature is that an auxiliary random variable (the “reference”) may influence the data-generating process and is revealed to the estimator after the interaction. This leads to two complementary principles for lower-bounding regret (Section 3.2 ): (i) reducing a portion of the regret to an identification error under a suitable separation condition, and (ii) interpreting a portion of the regret as an information cost . We further emphasize that this framework may extend to broader classes of nonstationary bandit problems and may be of independent interest. • In Section 5 , we complement the general negative result by identifying a special case in which constant satisficing regret is still achievable. Specifically, when there exists an always-realizable arm and no satisficing arm ever becomes non-satisficing, the stationary algorithms of 22 can be applied directly in the nonstationary setting, yielding constant satisficing regret that is independent of both the horizon T and the number of stationary segments L . 1.2 Related Work Nonstationary bandits. Most work on nonstationary bandits evaluates performance through dynamic regret , which compares the learner with the best arm at each round. For piecewise-stationary environments with at most L segments, sliding-window and change-point-based methods achieve \widetilde{\mathcal{O}}(\sqrt{LT}) dynamic regret ( 13 , 3 ) . Under a variation-budget model with total drift D , the optimal rate is \widetilde{\mathcal{O}}(D^{1/3}T^{2/3}) ( 5 , 8 ) , and 34 obtain the unified guarantee \widetilde{\mathcal{O}}(\min\{\sqrt{LT},D^{1/3}T^{2/3}\}) . These results address a stronger benchmark than ours: dynamic regret competes with the instantaneous best arm, whereas our objective only requires selecting an arm whose mean exceeds a fixed threshold. Stationary satisficing regret. Our work is most closely related to the literature on threshold-based satisficing regret in stationary bandits. 22 , 27 , and 10 study cumulative satisficing regret under a fixed threshold and show that, under realizability, constant regret is achievable in stationary settings. Our paper shows that this phenomenon changes sharply under nonstationarity: once the environment may change at unknown times, constant satisficing regret is no longer achievable in general. Threshold-based pure exploration and other satisficing