Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
Subhodip Panda, Shubhada Agrawal · 2026
Read Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards by Subhodip Panda, Shubhada Agrawal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14876.txt.
Introduction
Panda and Agrawal study regret tails for asymptotically optimal bandits. Such algorithms can show heavy regret tails, landing regret with real probability, while existing characterizations stay parametric. They extend KLinf-UCB to a nonparametric class under assumptions, proving optimality in expectation. They derive an upper bound on regret-tail probability. Special cases recover guarantees for bounded-support and heavy-tailed models, and for finitely supported rewards the bound matches the lower bound. The work gives a tight characterization of regret tails for KL-based UCB algorithms beyond parametric models.
Catalog record
| CREATOR | Subhodip Panda, Shubhada Agrawal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78823 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14876
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards Subhodip Panda, Shubhada Agrawal 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 KL inf \operatorname{KL_{inf}} -UCB algorithm of Agrawal et al., 2021a 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 \operatorname{KL} -based UCB algorithms, going beyond parametric models. 1 Introduction The multi-armed bandit (MAB) problem is a classical framework for sequential decision-making under uncertainty, in which an algorithm interacts with a set of K arms, each associated with an unknown reward distribution. At each round, the algorithm selects an arm and observes a stochastic reward, with the goal of maximizing the total expected reward till time T>0 . This objective is typically formalized via the notion of regret, defined as the difference between the cumulative reward of an algorithm over a horizon T and that of an oracle policy that always plays the arm with the largest mean reward. Minimizing expected regret is equivalent to maximizing expected cumulative reward, and serves as the standard performance criterion in bandit problems. A dominant focus of the contemporary literature has been on designing algorithms that minimize the expected regret. Lai and Robbins, 1985 ; Burnetas and Katehakis, 1996 proposed a fundamental lower bound on the expected cumulative regret suffered by any reasonable algorithm for this setup. Algorithms achieving this lower bound (even in the multiplicative constants) have also been developed for a wide class of reward distributions ( Honda and Takemura, 2010 ; Honda and Takemura, 2011 ; Agrawal and Goyal, 2012 ; Agrawal and Goyal, 2013 ; Kaufmann et al., 2012 ; Cappé et al., 2013 ; Honda and Takemura, 2015 ; Agrawal et al., 2021a ) . We refer the reader to Lattimore and Szepesvári, 2020 ; Bubeck et al., 2012 for a comprehensive treatment of this classical setup. While expected regret is a canonical performance metric in stochastic bandits, it provides only a coarse summary of algorithmic behavior. A more informative characterization is obtained by studying the distribution of the regret ( Audibert et al., 2009 ; Salomon and Audibert, 2011 ; Kalvit and Zeevi, 2021 ) , and in particular its tail behavior. Understanding the upper tail of the regret distribution is crucial for quantifying the probability of rare but severe failure events in which an algorithm may incur considerable regret. Such high-regret outcomes can be especially consequential in applications such as clinical trials, where such events may correspond to exposing a large number of patients to suboptimal treatments. Consequently, controlling heavy regret tails, rather than merely minimizing expected regret, is a key objective in risk-sensitive and safety-critical settings. Thus, a theoretical understanding of regret tail probabilities of existing algorithms can provide a principled avenue for identifying and mitigating the vulnerabilities of these optimal algorithms, and for guiding the design of more robust bandit strategies (see also, Ashutosh et al., 2021 ). In recent work, Fan and Glynn, 2024 establish a lower bound on the tail probabilities of the regret for any asymptotically optimal bandit algorithm, that is, one which matches the leading-order term in the regret lower bound, including the exact multiplicative constant. They further provide a detailed analysis of the regret tail upper bound for the KL-UCB algorithm of Cappé et al., 2013 , showing that its regret tail matches their lower bound, thereby demonstrating the tightness of these bounds for the single-parameter exponential family (SPEF) of reward distributions. While the authors discuss the extensions of their lower bounds to certain non-parametric classes of reward distributions, the regret tail upper bounds for optimized algorithms in these more general settings remained open. In particular, their analysis does not extend to the \operatorname{KL_{inf}} -UCB algorithm, which is known to be optimal for finitely-supported distributions ( Cappé et al., 2013 , Theorem 2) , bounded-support distributions ( Agrawal et al., 2021a , Proposition 4) , as well as for a broad class of heavy-tailed distributions ( Agrawal et al., 2021a ) . This motivates the following central question: Can we characterize the regret-tail behavior of asymptotically optimal bandit algorithms for broader nonparametric classes of reward distributions? In this work, we address the above question affirmatively. We first show that a natural generalization of the \operatorname{KL_{inf}} -UCB algorithm is asymptotically optimal for a very broad class of distributions \cal L , introduced later. We then prove the first regret-tail upper bound for this algorithm for arm distributions from \cal L , and demonstrate its tightness in different settings. We conclude this section by presenting the key contributions of this work. • We extend the \operatorname{KL_{inf}} -UCB algorithm of Agrawal et al., 2021a to a much broader family of reward distributions \mathcal{L} (to be introduced later), and show that it is asymptotically optimal (Theorem 3.1 ). This is a substantial generalization that includes the moment-bounded class studied by the authors, as well as bounded-support distributions as special cases. • Our main technical result is the regret tail upper bound for the generalized \operatorname{KL_{inf}} -UCB algorithm (Theorem 4.5 ). This is the first regret-tail upper bound for asymptotically optimal bandit algorithms beyond parametric models. As immediate corollaries, we get the upper bounds for the classical settings: (a) the moment-bounded heavy-tailed class considered in Agrawal et al., 2021a (Corollary 4.6 ); and (b) the bounded-support reward distributions (Corollary 4.7 ). When the class \mathcal{L} satisfies an additional property called discrimination-equivalence (Definition 4.2 ), we can show that the upper bounds that we prove exactly match the regret tail lower bound proposed in Fan and Glynn, 2024 . • For the special yet nontrivial case of finitely-supported distributions, a class that does not satisfy the discrimination-equivalence property, we provide a much tighter regret tail upper bound (Theorem 5.1 ), and show that it matches the lower bound of Fan and Glynn, 2024 . Organization: The rest of the paper is organized as follows. Section 2 presents the setup and necessary background. In Section 3 , we present the Generalized \mathrm{KL}_{\inf} -UCB algorithm and analyze its asymptotic optimality in the sense of expected regret. Section 4 analyzes the regret tail behavior of this optimal UCB algorithm, and presents a tight regret tail characterization under discrimination equivalence. Finally, Section 5 provides a refined regret tail analysis for the finitely supported setting, to obtain a tight upper bound, without relying on the discrimination equivalence. We review the relevant literature in detail in Appendix B . 2 Preliminaries