mlsanityData to 7 Oct 2026

Bootstrapping Upper Confidence Bound

arXiv 1906.05247 ↗First posted 12 Jun 2019stat.ML cs.LGcited by 36

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 9; 2023: 7; 2024: 2; 2025: 7; 2026: 2.

36 papers.

Sort:

By area:

  1. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inferencecited by 40
  2. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  3. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  4. 2024UCB algorithms for multi-armed bandits: Precise regret and adaptive inferencecited by 16
  5. 2021Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priorscited by 14
  6. 2022Bregman Deviations of Generic Exponential Familiescited by 13
  7. 2021Sharper Sub-Weibull Concentrationscited by 8
  8. 2023A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descentcited by 8
  9. 2022Residual Bootstrap Exploration for Stochastic Linear Banditcited by 7
  10. 2022Misspecified Phase Retrieval with Generative Priorscited by 7
  11. 2022Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descentcited by 7
  12. 2023Did we personalize? Assessing personalization by an online reinforcement learning algorithm using resamplingcited by 6
24 more
  1. 2025On the Provable Performance Guarantee of Efficient Reasoning Modelscited by 6
  2. 2021Multi-armed Bandit Requiring Monotone Arm Sequencescited by 5
  3. 2025Wonder Wins Ways: Curiosity-Driven Exploration through Multi-Agent Contextual Calibrationcited by 4
  4. 2021Debiasing Samples from Online Learning Using Bootstrapcited by 3
  5. 2022Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Modelscited by 3
  6. 2023Multiplier Bootstrap-based Explorationcited by 3
  7. 2022Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Frameworkcited by 2
  8. 2023Feature Normalization Prevents Collapse of Non-contrastive Learning Dynamicscited by 2
  9. 2022A Critical Review of Traffic Signal Control and A Novel Unified View of Reinforcement Learning and Model Predictive Control Approaches for Adaptive Traffic Signal Controlcited by 1
  10. 2023Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Normcited by 1
  11. 2023Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehiclescited by 1
  12. 2025Not All Documents Are What You Need for Extracting Instruction Tuning Datacited by 1
  13. 2025TextBandit: Evaluating Probabilistic Reasoning in LLMs Through Language-Only Decision Taskscited by 1
  14. 2021Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertaintycited by 0
  15. 2021GuideBoot: Guided Bootstrap for Deep Contextual Banditscited by 0
  16. 2021Centroid Approximation for Bootstrap: Improving Particle Quality at Inferencecited by 0
  17. 2022Double Thompson Sampling in Finite stochastic Gamescited by 0
  18. 2022Robust Tests in Online Decision-Makingcited by 0
  19. 2023Zero-Inflated Banditscited by 0
  20. 2025Don't Trade Off Safety: Diffusion Regularization for Constrained Offline RLcited by 0
  21. 2025Robust Dynamic Material Handling via Adaptive Constrained Evolutionary Reinforcement Learningcited by 0
  22. 2025On the Accuracy of Newton Step and Influence Function Data Attributionscited by 0
  23. 2026Cost-Driven Representation Learning for Linear Quadratic Gaussian Control: Part IIcited by 0
  24. 2026Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learningcited by 0