# Multiplier Bootstrap-based Exploration

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 57 references that are in the map.
- First posted on arXiv 3 Feb 2023.

## Builds on (most cited first, 30 of 32)

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Bootstrapped Thompson Sampling and Deep Exploration](https://mlsanity.com/paper/1507.00300/) (2015)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Concentration Inequalities for Statistical Inference](https://mlsanity.com/paper/2011.02258/) (2020)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Thompson sampling with the online bootstrap](https://mlsanity.com/paper/1410.4009/) (2014)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [Variational inference for the multi-armed contextual bandit](https://mlsanity.com/paper/1709.03163/) (2017)
- [Thompson Sampling with Approximate Inference](https://mlsanity.com/paper/1908.04970/) (2019)
- [Thompson Sampling Algorithms for Cascading Bandits](https://mlsanity.com/paper/1810.01187/) (2018)
- [Residual Bootstrap Exploration for Bandit Algorithms](https://mlsanity.com/paper/2002.08436/) (2020)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Sharper Sub-Weibull Concentrations](https://mlsanity.com/paper/2102.02450/) (2021)

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

- [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025)
- [Improved Regret of Linear Ensemble Sampling](https://mlsanity.com/paper/2411.03932/) (2024)
- [An Online Bootstrap for Time Series](https://mlsanity.com/paper/2310.19683/) (2023)

## Abstract (arXiv)

Despite the great interest in the bandit problem, designing efficient algorithms for complex models remains challenging, as there is typically no analytical way to quantify uncertainty. In this paper, we propose Multiplier Bootstrap-based Exploration (MBE), a novel exploration strategy that is applicable to any reward model amenable to weighted loss minimization. We prove both instance-dependent and instance-independent rate-optimal regret bounds for MBE in sub-Gaussian multi-armed bandits. With extensive simulation and real data experiments, we show the generality and adaptivity of MBE.