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

• URL: http://arxiv.org/abs/2603.18514v1
• Date: Thu, 19 Mar 2026 05:47:57 GMT
• Title: On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
• Abstract summary: We show that in the general realizable, piecewise-stationary setting with $L$ stationary segments, the optimal regret is $(Llog T)$ as long as $Lgeq 2$.<n>A key ingredient in our analysis is a novel Fano-based framework tailored to nonstationary bandits via a emphpost-interaction reference construction.
• Score: 20.199782529861913
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \emph{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.

Related papers

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  In this paper, we revisit the linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process.<n>We propose a novel variance-adaptive algorithm textttVAEE for large action set, which actively explores actions that maximize the information gain.<n>We establish a nearly matching lower bound for the fixed action set setting indicating that emphharmonic-mean dependent rate is unavoidable.
  arXiv  Detail & Related papers  (2026-07-26T14:24:34Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  We study the statistical efficiency of online learning with respect to KL-regularized objectives.<n>We show that the KL-regularized regret for MABs is $$-independent and scales as $tilde(sqrtKT)$.
  arXiv  Detail & Related papers  (2026-03-02T18:17:33Z)
• Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
  We tackle the heavy-tailed piecewise-stationary bandit problem.<n>We provide a novel Catoni-style change-point detection strategy tailored for heavy-tailed distributions.<n>We introduce Robust-CPD-UCB, which combines this change-point detection strategy with optimistic algorithms for bandits.
  arXiv  Detail & Related papers  (2025-05-26T14:40:47Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  We introduce a simple, unified UCB-based algorithm that achieves novel $p$-mean regret bounds.<n>Our framework encompasses both average cumulative regret and Nash regret as special cases.
  arXiv  Detail & Related papers  (2024-12-14T08:38:26Z)
• Adaptive Smooth Non-Stationary Bandits [0.8158530638728501]
  We study a $K$-armed non-stationary bandit model where rewards change smoothly.<n>We establish the minimax dynamic regret rate generally for all $K,beta,lambda$.<n>We also study the problem of attaining faster gap-dependent regret rates in non-stationary bandits.
  arXiv  Detail & Related papers  (2024-07-11T16:37:15Z)
• Smooth Non-Stationary Bandits [49.19728527803684]
  We study a non-stationary bandits problem where each arm's mean reward sequence can be embedded into a $beta$-H"older function. We show the first separation between the smooth (i.e., $betage 2$) and non-smooth (i.e., $beta=1$) regimes by presenting a policy with $tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2$-H"older instance.
  arXiv  Detail & Related papers  (2023-01-29T06:03:20Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits [10.127456032874978]
  We prove an instance (poly) logarithmic regret for contextual bandits with linear payoff. contexts indeed help to reduce the regret from $sqrtT$ to $polylog(T)$.
  arXiv  Detail & Related papers  (2022-05-19T23:41:46Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  We study the problem of regret minimization for episodic Reinforcement Learning (RL) We focus on learning with general function classes and general model classes. We show that a logarithmic regret bound is realizable by algorithms with $O(log T)$ switching cost.
  arXiv  Detail & Related papers  (2022-03-03T02:55:55Z)
• An Experimental Design Approach for Regret Minimization in Logistic Bandits [26.674062544226636]
  The main challenge of logistic bandits is reducing the dependence on a potentially large problem dependent constant $kappa$. We propose a new warmup sampling algorithm that can dramatically reduce the lower order term in the regret in general.
  arXiv  Detail & Related papers  (2022-02-04T21:56:40Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces.<n>A central theme here is the adaptive discretization of the action space, which gradually zooms in'' on the more promising regions.<n>We provide the first algorithm for adaptive discretization in the adversarial version, and derive instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-06-22T16:06:25Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.