Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

• URL: http://arxiv.org/abs/2605.05102v2
• Date: Thu, 07 May 2026 02:34:23 GMT
• Title: Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
• Abstract summary: We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels $in (0,1]$.<n>We present a simple UCBVI-style algorithm with exploration bonus $minc_1,k/N, c_2,k/sqrtN$, where $N$ denotes the visit count and $(c_1,k,c_2,k)$ are user-specified parameters.<n>Our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes
• Score: 39.8867004581646
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels $δ\in (0,1]$, thereby characterizing the regret distribution across the full range of $δ$. We present a simple UCBVI-style algorithm with exploration bonus $\min\{c_{1,k}/N, c_{2,k}/\sqrt{N}\}$, where $N$ denotes the visit count and $(c_{1,k},c_{2,k})$ are user-specified parameters. For arbitrary parameter sequences, we derive general gap-independent and gap-dependent distributional regret bounds, yielding a principled characterization of how the parameters control the trade-off between expected performance, tail risk, and instance-dependent behavior. In particular, our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes. As a special case, for multi-armed bandits with $A$ arms and horizon $T$, we obtain a distributional regret bound of order $\mathcal{O}(\sqrt{AT}\log(1/δ))$, confirming the conjecture of Lattimore & Szepesvári (2020, Section 17.1) for the first time.

Related papers

• Parameter-Free Heavy-Tailed Bandits [36.983245230853434]
  We study adaptation to the moment bound $u$ for a fixed tail exponent $$.<n>We prove that every algorithm unaware of $u$, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees.
  arXiv  Detail & Related papers  (2026-07-31T14:27:28Z)
• Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
  We consider a multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback.<n>We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight.<n>We establish a gap-free regret bound $tildeO(dsqrtnkT)$ that holds on every instance, together with a gap
  arXiv  Detail & Related papers  (2026-07-28T21:10:39Z)
• 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)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• 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)
• 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)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  We study the regret minimization problem when $epsilon$ and $u$ are unknown to the learner. AdaR-UCB is the first algorithm that enjoys regret guarantees nearly matching those of the non-adaptive heavy-tailed case.
  arXiv  Detail & Related papers  (2023-10-04T17:11:15Z)
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption [21.709840199725015]
  We investigate the regret-minimisation problem in a multi-armed bandit setting with arbitrary corruptions. We introduce CRIMED, an algorithm that achieves the exact lower bound on regret for bandits with known variance. Notably, CRIMED can effectively handle corruptions with $varepsilon$ values as high as $frac12$.
  arXiv  Detail & Related papers  (2023-09-28T16:19:53Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits [8.508198765617198]
  We propose a novel contextual bandit algorithm for generalized linear rewards with an $tildeO(sqrtkappa-1 phi T)$ regret over $T$ rounds. We also provide an $O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms under a probabilistic margin condition.
  arXiv  Detail & Related papers  (2022-09-15T00:20:38Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• Adaptation to the Range in $K$-Armed Bandits [1.14219428942199]
  We consider bandit problems with $K$ arms associated with a bounded distribution supported on the range $[m,M]$. A new trade-off between distribution-dependent and distribution-free regret bounds arises, which prevents from simultaneously achieving the typical $ln T$ and $sqrtT$ bounds.
  arXiv  Detail & Related papers  (2020-06-05T11:26:35Z)

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.