Thompson sampling with the online bootstrap

Abstract

Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal, Thompson sampling can be computationally demanding in large scale bandit problems, and its performance is dependent on the model fit to the observed data. We introduce bootstrap Thompson sampling (BTS), a heuristic method for solving bandit problems which modifies Thompson sampling by replacing the posterior distribution used in Thompson sampling by a bootstrap distribution. We first explain BTS and show that the performance of BTS is competitive to Thompson sampling in the well-studied Bernoulli bandit case. Subsequently, we detail why BTS using the online bootstrap is more scalable than regular Thompson sampling, and we show through simulation that BTS is more robust to a misspecified error distribution. BTS is an appealing modification of Thompson sampling, especially when samples from the posterior are otherwise not available or are costly.

13 pages, 4 figures

References in corpus (2)

• On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
• Online Learning, Stability, and Stochastic Gradient Descent

Cited by in corpus (19)

• Bootstrapped Thompson Sampling and Deep Exploration
• A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
• A Contextual Bandit Bake-off
• Adapting multi-armed bandits policies to contextual bandits scenarios
• Bootstrapping Upper Confidence Bound
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Budgeted Policy Learning for Task-Oriented Dialogue Systems
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• New Insights into Bootstrapping for Bandits
• contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Perturbed-History Exploration in Stochastic Linear Bandits
• Risk Aware and Multi-Objective Decision Making with Distributional Monte Carlo Tree Search
• Targeting for long-term outcomes
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Debiasing Samples from Online Learning Using Bootstrap
• Continuous-Time Birth-Death MCMC for Bayesian Regression Tree Models
• Hawkes Process Multi-armed Bandits for Disaster Search and Rescue