# Thompson sampling with the online bootstrap

arXiv: https://arxiv.org/abs/1410.4009 · HTML: https://mlsanity.com/paper/1410.4009/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2014.

## Built on by (most cited first, 19 of 19)

- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Reinforcement Learning in Modern Biostatistics: Constructing Optimal Adaptive Interventions](https://mlsanity.com/paper/2203.02605/) (2022)
- [Risk Aware and Multi-Objective Decision Making with Distributional Monte Carlo Tree Search](https://mlsanity.com/paper/2102.00966/) (2021)
- [Monte Carlo Tree Search Algorithms for Risk-Aware and Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2211.13032/) (2022)
- [Debiasing Samples from Online Learning Using Bootstrap](https://mlsanity.com/paper/2108.00236/) (2021)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning](https://mlsanity.com/paper/2011.14266/) (2020)
- [CORe: Capitalizing On Rewards in Bandit Exploration](https://mlsanity.com/paper/2103.04387/) (2021)
- [Dynamic Information Sub-Selection for Decision Support](https://mlsanity.com/paper/2410.23423/) (2024)
- [Contextual bandits with entropy-based human feedback](https://mlsanity.com/paper/2502.08759/) (2025)
- [GuideBoot: Guided Bootstrap for Deep Contextual Bandits](https://mlsanity.com/paper/2107.08383/) (2021)
- [Integrating Hyperparameter Search into Model-Free AutoML with Context-Free Grammars](https://mlsanity.com/paper/2404.03419/) (2024)
- [Leveraging priors on distribution functions for multi-arm bandits](https://mlsanity.com/paper/2503.04518/) (2025)
- [Estimating Causal Effects in Networks with Cluster-Based Bandits](https://mlsanity.com/paper/2505.04200/) (2025)
- [POETS: Uncertainty-Aware LLM Optimization via Compute-Efficient Policy Ensembles](https://mlsanity.com/paper/2605.07775/) (2026)
- [Learning to Assign Prediction Tasks to Agents with Capacity Constraints](https://mlsanity.com/paper/2605.27999/) (2026)
- [Bootstrap-Conditioned Action Selection with Tabular Foundation Models](https://mlsanity.com/paper/2608.06559/) (2026)

## Abstract (arXiv)

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.