# Inference with the Upper Confidence Bound Algorithm

arXiv: https://arxiv.org/abs/2408.04595 · HTML: https://mlsanity.com/paper/2408.04595/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 8 Aug 2024.

## Builds on (most cited first, 12 of 12)

- [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)
- [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)
- [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)
- [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)

## Built on by (most cited first, 12 of 12)

- [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)
- [Simulation-Based Inference for Adaptive Experiments](https://mlsanity.com/paper/2506.02881/) (2025)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [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)
- [Efficient Inference after Directionally Stable Adaptive Experiments](https://mlsanity.com/paper/2602.21478/) (2026)
- [Bandit Simulation for Average Reward Inference](https://mlsanity.com/paper/2606.00913/) (2026)
- [Statistical Inference for Misspecified Contextual Bandits](https://mlsanity.com/paper/2606.22639/) (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)
- [Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime](https://mlsanity.com/paper/2610.06213/) (2026)

## Abstract (arXiv)

In this paper, we discuss the asymptotic behavior of the Upper Confidence Bound (UCB) algorithm in the context of multiarmed bandit problems and discuss its implication in downstream inferential tasks. While inferential tasks become challenging when data is collected in a sequential manner, we argue that this problem can be alleviated when the sequential algorithm at hand satisfies certain stability property. This notion of stability is motivated from the seminal work of Lai and Wei (1982). Our first main result shows that such a stability property is always satisfied for the UCB algorithm, and as a result the sample means for each arm are asymptotically normal. Next, we examine the stability properties of the UCB algorithm when the number of arms K is allowed to grow with the number of arm pulls T. We show that in such a case the arms are stable when fraclog Klog T rightarrow 0, and the number of near-optimal arms are large.