Thompson sampling with the online bootstrap

Dean Eckles, Maurits KapteinarXiv 2014 · arXiv

Abstract

Traditional Thompson Sampling (TS) provides a powerful Bayesian framework for the multi-armed bandit problem but faces significant hurdles in scalability and robustness to model misspecification. This paper introduces Bootstrap Thompson Sampling (BTS), which replaces the Bayesian posterior with an online bootstrap distribution. By maintaining a set of model replicates updated via a "double-or-nothing" bootstrap, BTS achieves $O(1)$ update complexity and demonstrates superior resilience to non-parametric noise, making it highly suitable for large-scale industrial applications.

Introduction

In the multi-armed bandit (MAB) setting, an agent must navigate the exploration-exploitation trade-off to maximize cumulative rewards. Thompson Sampling (TS) is a leading approach that samples from a posterior distribution to guide action selection. However, in real-world scenarios—such as those encountered at Facebook—TS encounters two primary challenges: computational scalability for complex models and sensitivity to parametric assumptions. Calculating posteriors for models like logistic regression often requires expensive MCMC simulations, and if the data's noise profile deviates from the assumed distribution (e.g., Gaussian), TS performance can degrade significantly.

The Bootstrap Thompson Sampling (BTS) Framework

To address these limitations, the authors propose Bootstrap Thompson Sampling (BTS). Instead of relying on Bayes' Rule, BTS leverages the Online Bootstrap to approximate the uncertainty of reward estimates.

The Replicate Strategy

BTS maintains $J$ distinct replicates of the model parameters for each arm. When a new observation arrives, the algorithm employs a Double-or-Nothing Bootstrap (DoNB): each replicate is updated with a random weight (typically 0 or 2, effectively a Poisson(1) approximation). This allows the algorithm to simulate a distribution of possible parameter values without the need for complex integration.

Decision Making and Scalability

At each decision step, the agent randomly selects one of the $J$ replicates for each arm and chooses the action that is optimal according to those specific parameters. Because updates only involve modifying $J$ fixed replicates, the computational cost per update remains constant ($O(1)$) relative to the total number of observations $t$. This makes BTS "embarrassingly parallelizable" and ideal for high-throughput systems.

Empirical Evaluation

The researchers evaluated BTS against standard TS using several synthetic benchmarks, including Bernoulli bandits and contextual bandits with heteroscedastic Gaussian noise.

Cumulative regret for Thompson sampling and BTS across different arm counts (K) and noise levels (epsilon).

As shown in the experimental results, BTS performs competitively with traditional Thompson Sampling in standard settings. More importantly, in environments with model misspecification (such as varying noise levels), BTS often outperforms TS. The bootstrap's non-parametric nature allows it to adapt to the actual data distribution more effectively than a rigid parametric Bayesian model.

The Impact of Replicate Count ($J$)

A critical hyperparameter in BTS is the number of replicates, $J$. This parameter controls the fidelity of the bootstrap approximation and, by extension, the degree of exploration.

Impact of the number of bootstrap replicates (J) on cumulative regret.

If $J$ is too small, the algorithm may become overly "greedy," potentially failing to explore the optimal arm if it is not represented in the limited set of replicates. As $J$ increases, the performance converges toward the ideal bootstrap distribution. The results indicate that even a moderate $J$ (e.g., 100 to 1000) is often sufficient to achieve near-optimal regret while maintaining computational efficiency.

Conclusion

Bootstrap Thompson Sampling offers a practical and robust alternative to Bayesian Thompson Sampling. By utilizing the online bootstrap, it bypasses the computational bottlenecks of MCMC and the fragility of parametric assumptions. Its $O(1)$ update complexity and parallelizable nature make it a compelling choice for modern, large-scale recommendation and optimization systems.

Summary updated

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.
BibTeX
@misc{eckles2014thompson,
  author = {Dean Eckles and Maurits Kaptein},
  title = {{Thompson sampling with the online bootstrap}},
  year = {2014},
  eprint = {1410.4009},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.4009},
}
Figure