Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

• URL: http://arxiv.org/abs/2604.14876v1
• Date: Thu, 16 Apr 2026 11:05:30 GMT
• Title: Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
• Abstract summary: We study the tail behavior of regret in multi-armed bandits for algorithms that are optimal in expectation.<n>We derive a novel upper bound on the regret tail probability.<n>Our results provide a unified and tight characterization of regret tails for optimal KL-based UCB algorithms.
• Score: 3.396415446890748
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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$-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.

Related papers

• Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards [1.370633147306388]
  $text-mathrmNPTS_mathrmSG$ is an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits.<n>We prove that $text-mathrmNPTS_mathrmSG$ achieves regret matching the instance-dependent lower bound to leading order in $log n$.
  arXiv  Detail & Related papers  (2026-06-08T08:26:37Z)
• Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses [0.6321283533425183]
  We study a class of adversarial bandit optimization problems in which the loss functions may be non-smooth.<n>As a special case of our analysis, we recover an improved high-probability for classical bandit optimization.
  arXiv  Detail & Related papers  (2026-03-27T04:33:08Z)
• Tail Distribution of Regret in Optimistic Reinforcement Learning [3.9962751777898955]
  We characterize the tail distribution of the cumulative regret $R_K$ over $K$ episodes, rather than only its expectation or a single high-probability quantile.<n>A proposed algorithm depends on a tuning parameter $$, which balances the expected regret and the range over which the regret exhibits a sub-Gaussian tail.
  arXiv  Detail & Related papers  (2025-11-23T02:23:09Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  We quantify the excess risk incurred using approximate posterior probabilities in batch binary decision-making.<n>We identify regimes where recalibration alone addresses most of the regret, and regimes where the regret is dominated by the grouping loss.<n>On NLP experiments, we show that these quantities identify when the expected gain of more advanced post-training is worth the operational cost.
  arXiv  Detail & Related papers  (2025-03-23T10:52:36Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family. We propose a Thompson sampling, termed Expulli, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm.
  arXiv  Detail & Related papers  (2022-06-07T18:08:21Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers [31.102181563065844]
  Quantile (and, more generally, KL) regret bounds relax the goal of competing against the best individual expert to only competing against a majority of experts on adversarial data. More recently, the semi-adversarial paradigm (Bilodeau, Negrea, and Roy 2020) provides an alternative relaxation of adversarial online learning by considering data that may be neither fully adversarial nor adversarial. We achieve the minimax optimal regret in both paradigms using FTRL with separate, novel, root-logarithmic regularizers, both of which can be interpreted as yielding variants of NormalHedge.
  arXiv  Detail & Related papers  (2021-10-27T22:38:52Z)
• The Fragility of Optimized Bandit Algorithms [4.390757904176221]
  Much of the literature on optimal design of bandit algorithms is based on fragility of expected regret. We show that optimized UCB bandit designs are fragile when the problem is even slightly mis-specified. We show that UCB algorithms can be modified so as to ensure a desired degree of robustness to mis-specification.
  arXiv  Detail & Related papers  (2021-09-28T10:11:06Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  We introduce a new family of oracle-efficient algorithms for $varepsilon$-misspecified contextual bandits. We obtain the first algorithm that achieves the optimal $O(dsqrtT + varepsilonsqrtdT)$ regret bound for unknown misspecification level.
  arXiv  Detail & Related papers  (2021-07-12T21:30:41Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• 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)

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.