# Bootstrapping Upper Confidence Bound

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

## Built on by (most cited first, 30 of 36)

- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent](https://mlsanity.com/paper/2310.00692/) (2023)
- [Sharper Sub-Weibull Concentrations](https://mlsanity.com/paper/2102.02450/) (2021)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descent](https://mlsanity.com/paper/2212.14883/) (2022)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [Did we personalize? Assessing personalization by an online reinforcement learning algorithm using resampling](https://mlsanity.com/paper/2304.05365/) (2023)
- [On the Provable Performance Guarantee of Efficient Reasoning Models](https://mlsanity.com/paper/2510.09133/) (2025)
- [Multi-armed Bandit Requiring Monotone Arm Sequences](https://mlsanity.com/paper/2106.03790/) (2021)
- [Wonder Wins Ways: Curiosity-Driven Exploration through Multi-Agent Contextual Calibration](https://mlsanity.com/paper/2509.20648/) (2025)
- [Debiasing Samples from Online Learning Using Bootstrap](https://mlsanity.com/paper/2108.00236/) (2021)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework](https://mlsanity.com/paper/2201.12955/) (2022)
- [A Critical Review of Traffic Signal Control and A Novel Unified View of Reinforcement Learning and Model Predictive Control Approaches for Adaptive Traffic Signal Control](https://mlsanity.com/paper/2211.14426/) (2022)
- [Feature Normalization Prevents Collapse of Non-contrastive Learning Dynamics](https://mlsanity.com/paper/2309.16109/) (2023)
- [Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm](https://mlsanity.com/paper/2303.07287/) (2023)
- [Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehicles](https://mlsanity.com/paper/2312.13910/) (2023)
- [Not All Documents Are What You Need for Extracting Instruction Tuning Data](https://mlsanity.com/paper/2505.12250/) (2025)
- [TextBandit: Evaluating Probabilistic Reasoning in LLMs Through Language-Only Decision Tasks](https://mlsanity.com/paper/2510.13878/) (2025)
- [On the Accuracy of Newton Step and Influence Function Data Attributions](https://mlsanity.com/paper/2512.12572/) (2025)
- [Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty](https://mlsanity.com/paper/2106.08477/) (2021)
- [GuideBoot: Guided Bootstrap for Deep Contextual Bandits](https://mlsanity.com/paper/2107.08383/) (2021)
- [Centroid Approximation for Bootstrap: Improving Particle Quality at Inference](https://mlsanity.com/paper/2110.08720/) (2021)
- [Double Thompson Sampling in Finite stochastic Games](https://mlsanity.com/paper/2202.10008/) (2022)

## Abstract (arXiv)

Upper Confidence Bound (UCB) method is arguably the most celebrated one used in online decision making with partial information feedback. Existing techniques for constructing confidence bounds are typically built upon various concentration inequalities, which thus lead to over-exploration. In this paper, we propose a non-parametric and data-dependent UCB algorithm based on the multiplier bootstrap. To improve its finite sample performance, we further incorporate second-order correction into the above construction. In theory, we derive both problem-dependent and problem-independent regret bounds for multi-armed bandits under a much weaker tail assumption than the standard sub-Gaussianity. Numerical results demonstrate significant regret reductions by our method, in comparison with several baselines in a range of multi-armed and linear bandit problems.