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.
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.
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