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

Yixuan Zhang; Ruihao Zhu; Qiaomin Xie

stat.MLMar 19, 2026

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

Authors: Yixuan Zhang, Ruihao Zhu, Qiaomin Xie

Organizations: Department of Industrial & Systems Engineering, University of Wisconsin-Madison · SC Johnson College of Business, Cornell University

Abstract

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 $Θ(L\log T)$ as long as $L\geq 2$ . This stands in sharp contrast to the case of $L=1$ (i.e., the stationary setting), where a $T$ -independent $Θ(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.

Figures & tables

Panel of Figure 1 — Figure 1: Schematic illustration: the full horizontal line represents the time horizon $T$ , blue/red segments denote the two stationary environments, and the shaded region marks where the two instances disagree.

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 113 papers

Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution
Jun 10, 2024Qing Feng, Tianyi Ma, Ruihao ZhuMulti-Armed Bandits Regret Minimization
School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
Jul 3, 2026Zihao Hu, Yuan Yao, Jiheng Zhang +1Dynamic Regret Minimization Non-Stationary Bandits
Department of Mathematics, The Hong Kong University of Science and Technology
Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
Aug 18, 2026Kaifei Wang, Yinyu Ye, Han ZhongMulti-Armed Bandits UCB Algorithms
Peking University · Stanford University · Shanghai Jiao Tong University

Jun 10, 2024J/K move · Enter open · S save

Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution

Qing Feng, Tianyi Ma, Ruihao Zhu

School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University

Multi-Armed Bandits Regret Minimization

Open paper AskPDF arXiv

Motivated by the concept of satisficing in decision-making, we consider the problem of satisficing regret minimization in bandit optimization. In this setting, the learner aims at selecting satisficing arms (arms with mean reward exceeding a certain threshold value) as frequently as possible. The performance is measured by satisficing regret, which is the cumulative deficit of the chosen arm's mean reward compared to the threshold. We propose SELECT, a general algorithmic template for Satisficing REgret Minimization via SampLing and LowEr Confidence bound Testing, that attains constant expected satisficing regret for a wide variety of bandit optimization problems in the realizable case (i.e., a satisficing arm exists). As a complement, SELECT also enjoys the same (standard) regret guarantee as the oracle in the non-realizable case. To further ensure stability of the algorithm, we introduce SELECT-LITE that achieves a light-tailed satisficing regret distribution plus a constant expected satisficing regret in the realizable case and a sub-linear expected (standard) regret in the non-realizable case. Notably, SELECT-LITE can operate on learning oracles with heavy-tailed (standard) regret distribution. More importantly, our results reveal the surprising compatibility between constant expected satisficing regret and light-tailed satisficing regret distribution, which is in sharp contrast to the case of (standard) regret. Finally, we conduct numerical experiments to validate the performance of SELECT and SELECT-LITE on both synthetic datasets and a real-world dynamic pricing case study.

Abstract

Regret Minimization

Explore similar work

Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits