# UCB algorithms for multi-armed bandits: Precise regret and adaptive inference arXiv: https://arxiv.org/abs/2412.06126 · HTML: https://mlsanity.com/paper/2412.06126/ ## Key facts - Cited by 19 papers in the map (data through 14 Oct 2026). - Builds on 21 of its 65 references that are in the map. - First posted on arXiv 9 Dec 2024. ## Builds on (most cited first, 21 of 21) - [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019) - [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019) - [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015) - [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019) - [Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits](https://mlsanity.com/paper/2106.02029/) (2021) - [Accurate Inference for Adaptive Linear Models](https://mlsanity.com/paper/1712.06695/) (2017) - [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022) - [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019) - [Post-Contextual-Bandit Inference](https://mlsanity.com/paper/2106.00418/) (2021) - [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021) - [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017) - [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014) - [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019) - [Near-optimal inference in adaptive linear regression](https://mlsanity.com/paper/2107.02266/) (2021) - [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018) - [On Bayesian index policies for sequential resource allocation](https://mlsanity.com/paper/1601.01190/) (2016) - [Online Debiasing for Adaptively Collected High-dimensional Data with Applications to Time Series Analysis](https://mlsanity.com/paper/1911.01040/) (2019) - [Semi-parametric inference based on adaptively collected data](https://mlsanity.com/paper/2303.02534/) (2023) - [Adaptive Linear Estimating Equations](https://mlsanity.com/paper/2307.07320/) (2023) - [Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference](https://mlsanity.com/paper/2310.00532/) (2023) - [On Lai's Upper Confidence Bound in Multi-Armed Bandits](https://mlsanity.com/paper/2410.02279/) (2024) ## Built on by (most cited first, 19 of 19) - [PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving](https://mlsanity.com/paper/2502.16111/) (2025) - [GAAPO: Genetic Algorithmic Applied to Prompt Optimization](https://mlsanity.com/paper/2504.07157/) (2025) - [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025) - [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024) - [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026) - [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025) - [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025) - [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026) - [Learning from Prompt itself: the Hierarchical Attribution Prompt Optimization](https://mlsanity.com/paper/2601.02683/) (2026) - [In-Context Reinforcement Learning through Bayesian Fusion of Context and Value Prior](https://mlsanity.com/paper/2601.03015/) (2026) - [Efficient Inference after Directionally Stable Adaptive Experiments](https://mlsanity.com/paper/2602.21478/) (2026) - [Scalable and Interpretable Contextual Bandits: A Literature Review and Retail Offer Prototype](https://mlsanity.com/paper/2505.16918/) (2025) - [Offline-Online Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2604.11994/) (2026) - [Bandit Simulation for Average Reward Inference](https://mlsanity.com/paper/2606.00913/) (2026) - [MINTS: Minimalist Thompson Sampling](https://mlsanity.com/paper/2606.01655/) (2026) - [Statistical Inference for Misspecified Contextual Bandits](https://mlsanity.com/paper/2606.22639/) (2026) - [Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors](https://mlsanity.com/paper/2607.22935/) (2026) - [Sharp Characterization of Bias in Post-Bandit Inference](https://mlsanity.com/paper/2608.01069/) (2026) - [Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits](https://mlsanity.com/paper/2608.17841/) (2026) ## Abstract (arXiv) Upper Confidence Bound (UCB) algorithms are a widely-used class of sequential algorithms for the K-armed bandit problem. Despite extensive research over the past decades aimed at understanding their asymptotic and (near) minimax optimality properties, a precise understanding of their regret behavior remains elusive. This gap has not only hindered the evaluation of their actual algorithmic efficiency, but also limited further developments in statistical inference in sequential data collection. This paper bridges these two fundamental aspects--precise regret analysis and adaptive statistical inference--through a deterministic characterization of the number of arm pulls for an UCB index algorithm [Lai87, Agr95, ACBF02]. Our resulting precise regret formula not only accurately captures the actual behavior of the UCB algorithm for finite time horizons and individual problem instances, but also provides significant new insights into the regimes in which the existing theory remains informative. In particular, we show that the classical Lai-Robbins regret formula is exact if and only if the sub-optimality gaps exceed the order σ√Klog T/T. We also show that its maximal regret deviates from the minimax regret by a logarithmic factor, and therefore settling its strict minimax optimality in the negative. The deterministic characterization of the number of arm pulls for the UCB algorithm also has major implications in adaptive statistical inference. Building on the seminal work of [Lai82], we show that the UCB algorithm satisfies certain stability properties that lead to quantitative central limit theorems in two settings including the empirical means of unknown rewards in the bandit setting. These results have an important practical implication: conventional confidence sets designed for i.i.d. data remain valid even when data are collected sequentially.