Bootstrapping Upper Confidence Bound
arXiv:1906.05247
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.
arXiv commentAccepted by NeurIPS 2019
References in corpus (10)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Further Optimal Regret Bounds for Thompson Sampling
- Thompson Sampling for 1-Dimensional Exponential Family Bandits
- Bootstrap confidence sets under model misspecification
- Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression
- Thompson sampling with the online bootstrap
- New Insights into Bootstrapping for Bandits
- Non-asymptotic theory for nonparametric testing
- Suprema of canonical Weibull processes