Bootstrapping Upper Confidence Bound

2019/06/12 by Botao Hao, Yasin Abbasi-Yadkori, Hao, Botao +5 · 8 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1906.05247

Accepted by NeurIPS 2019

openalex publication_date 2019/06/12 · arxiv created 2019/10/31 · arxiv updated 2019/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Reinforcement learning in robotics: A survey
• Thompson Sampling for Contextual Bandits with Linear Payoffs

Cited by

• On the Accuracy of Newton Step and Influence Function Data Attributions
• Empirical Orlicz norms
• TextBandit: Evaluating Probabilistic Reasoning in LLMs Through Language-Only Decision Tasks
• On the Provable Performance Guarantee of Efficient Reasoning Models
• Wonder Wins Ways: Curiosity-Driven Exploration through Multi-Agent Contextual Calibration
• Toward Optimal Statistical Inference in Noisy Linear Quadratic Reinforcement Learning over a Finite Horizon
• Robust Dynamic Material Handling via Adaptive Constrained Evolutionary Reinforcement Learning
• Not All Documents Are What You Need for Extracting Instruction Tuning Data

Related

• Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits
• Differentiable Linear Bandit Algorithm
• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference
• Precise Asymptotics and Refined Regret of Variance-Aware UCB
• Inference with the Upper Confidence Bound Algorithm