UCB Algorithms

UCB: Upper Confidence Bound

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 38

All topics

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
Apr 16, 2026Subhodip Panda, Shubhada AgrawalMulti-Armed Bandits UCB Algorithms
Department of ECE · Indian Institute of Science · Bangalore, India
RepUCB: Representation Learning-Based UCB for Heterogeneous Multi-Task Linear Bandits
Apr 1, 2026Jiabin Lin, Shana MoothedathMulti-Armed Bandits Multi-Task Learning
Department of Electrical and Computer Engineering, Iowa State University, USA
Mixture-Greedy for Online Generative Model Selection: Is UCB Necessary in Diversity-Aware Multi-Armed Bandits?
Mar 23, 2026Bahar Dibaei Nia, Farzan FarniaMulti-Armed Bandits Exploration-Exploitation Tradeoff
Department of Computer Science and Engineering, Chinese University of Hong Kong.
Rising Multi-Armed Bandits with Known Horizons
Feb 11, 2026Seockbean Song, Chenyu Gan, Youngsik Yoon +3Multi-Armed Bandits UCB Algorithms
Graduate School of AI, POSTECH, Pohang, Republic of Korea · Qiuzhen College, Tsinghua University, Beijing, China · Department of CSE, POSTECH, Pohang, Republic of Korea +1
Managing Self-Learning Experts under Per-Round Budget Constraints
Oct 26, 2025Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin +2Multi-Armed Bandits Algorithm Selection
AI Center, Lomonosov Moscow State University MSU Institute for Artificial Intelligence Moscow, Russia · Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · IITP RAS Moscow, Russia +1
On the Sublinear Regret of Continuous K-Max Bandits
Feb 19, 2025Yu Chen, Siwei Wang, Longbo Huang +1Multi-Armed Bandits UCB Algorithms
Institute for Interdisciplinary Information Sciences, Tsinghua University · 2Microsoft Research Asia
Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport
Feb 11, 2025Lorenzo CroissantMulti-Armed Bandits UCB Algorithms
CREST,FAIRPLAY,ENSAE Paris
Allocation Stability and Wald Inference under Variance-Aware UCB
Dec 12, 2024Yingying Fan, Yuxuan Han, Jinchi Lv +2Multi-Armed Bandits UCB Algorithms
Data Sciences and Operations Department University of Southern California Los Angeles, CA 90089, USA · Stern School of Business, New York University, New York, NY 10003, USA

Apr 16, 2026, cs.ITJ/K move · Enter open · S save

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

Subhodip Panda, Shubhada Agrawal

Department of ECE · Indian Institute of Science · Bangalore, India

Multi-Armed Bandits UCB Algorithms

Open paper AskPDF arXiv

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.

Momentum

Related topics

Latest papers 38