New Insights into Bootstrapping for Bandits

Abstract

We investigate the use of bootstrapping in the bandit setting. We first show that the commonly used non-parametric bootstrapping (NPB) procedure can be provably inefficient and establish a near-linear lower bound on the regret incurred by it under the bandit model with Bernoulli rewards. We show that NPB with an appropriate amount of forced exploration can result in sub-linear albeit sub-optimal regret. As an alternative to NPB, we propose a weighted bootstrapping (WB) procedure. For Bernoulli rewards, WB with multiplicative exponential weights is mathematically equivalent to Thompson sampling (TS) and results in near-optimal regret bounds. Similarly, in the bandit setting with Gaussian rewards, we show that WB with additive Gaussian weights achieves near-optimal regret. Beyond these special cases, we show that WB leads to better empirical performance than TS for several reward distributions bounded on $[0,1]$. For the contextual bandit setting, we give practical guidelines that make bootstrapping simple and efficient to implement and result in good empirical performance on real-world datasets.

References in corpus (11)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• API design for machine learning software: experiences from the scikit-learn project
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Further Optimal Regret Bounds for Thompson Sampling
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Bandit Problems with Side Observations
• Bootstrapped Thompson Sampling and Deep Exploration
• Online Stochastic Linear Optimization under One-bit Feedback
• Thompson sampling with the online bootstrap
• A Practical Method for Solving Contextual Bandit Problems Using Decision Trees

Cited by in corpus (9)

• Bootstrapping Upper Confidence Bound
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• Perturbed-History Exploration in Stochastic Linear Bandits
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Differentiable Linear Bandit Algorithm
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Debiasing Samples from Online Learning Using Bootstrap
• Towards Tractable Optimism in Model-Based Reinforcement Learning
• CORe: Capitalizing On Rewards in Bandit Exploration