stat.MLDate pending

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

Authors: Qing Feng, Tianyi Ma, Ruihao Zhu

Abstract

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.

Explore similar work

CardsList
May 20, 2026cs.LG

Finite-Time Regret Analysis of Retry-Aware Bandits

We study a stochastic bandit algorithm motivated by retry-aware objectives that value the best outcome among multiple attempts, such as pass@kk and max@kk. Given a posterior over arm values, ReMax chooses a sampling distribution that maximizes the posterior expected maximum reward over MM virtual draws. Although this objective was introduced in reinforcement learning as an exploration mechanism under uncertainty, its regret properties in bandit problems have remained unclear. For Gaussian rewards and the first nontrivial case M=2M=2, we characterize the optimal ReMax distribution through an expected-improvement balance condition and prove the first sublinear regret bound for ReMax. Our analysis separates the usual saturation behavior of suboptimal arms from a ReMax-specific underestimation effect, in which the optimal arm may be sampled too rarely after an unfavorable estimate. This explains why ReMax can be more exploitative than Thompson sampling (TS) and why its regret analysis is technically delicate. Experiments support this picture: ReMax often outperforms KL-UCB and Thompson sampling under mild underestimation, while posterior-variance scaling empirically mitigates severe underestimation.
Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1
Multi-Armed BanditsLinear RegretRegretPosteriorOverconfidence
AskPDF
Jul 15, 2026stat.ML

Price of Fairness in Bandits: A Tight Minimax Characterization

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized pp-mean, interpolating between utilitarian welfare (p=1p=1), Nash welfare (p→0p\to0), and Rawlsian fairness (p→−∞p\to-\infty). Although tight guarantees are known for p≥0p\ge0, the strictly fair regime q=−p>0q=-p>0 remains unresolved because negative-power means are dominated by the smallest per-round rewards. For σσ-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret O(k(q+1)/2/T)O(k^{(q+1)/2}/\sqrt{T}), while the only general lower bound was the classical Ω(σk/T)Ω(σ\sqrt{k/T}). Thus it was unclear whether the extra dependence on kk was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound Ω(σkmax⁡(1,q)/T)Ω(σ\sqrt{k^{\max(1,q)}/T}); for q>1q>1, this shows that the penalty kq/2k^{q/2} is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is O~(σkmax⁡(1,q)/T)\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T}), matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as qq grows.
Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury
Linear RegretBanditsMinimaxFairness ConstraintsFairness InterventionsPrices+1
AskPDF
Apr 16, 2026cs.IT

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that even such algorithms can exhibit heavy regret tails, incurring large regret with non-negligible probability. Existing sharp characterizations of regret tails are largely restricted to parametric settings, such as single-parameter exponential families. In this work, we extend the \KLinf\KLinf-UCB algorithm of to a broad nonparametric class of reward distributions satisfying mild assumptions, and establish its asymptotic optimality in expectation. We then analyze the tail behavior of its regret and derive a novel upper bound on the regret tail probability. As special cases, our results recover regret-tail guarantees for both bounded-support and heavy-tailed (moment-bounded) bandit models. Moreover, for the special case of finitely-supported reward distributions, our upper bound matches the known lower bound exactly. Our results thus provide a unified and tight characterization of regret tails for asymptotically optimal KL-based UCB algorithms, going beyond parametric models.
Subhodip Panda, Shubhada Agrawal
Optimal Bandit AlgorithmsRegretLong-Tailed DistributionBanditsConcentration Inequalities
AskPDF