mlsanityData to 7 Oct 2026

Multiplier Bootstrap-based Exploration

arXiv 2302.01543 ↗First posted 3 Feb 2023cs.LGcited by 3

Not on the map. Why?

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.

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

Builds on

32 of 57 references.

References · 32

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  2. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 166
  3. 2017Deep Exploration via Randomized Value Functionscited by 155
  4. 2014Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Armscited by 78
  5. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  6. 2015Cascading Bandits: Learning to Rank in the Cascade Modelcited by 75
  7. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  8. 2018A Contextual Bandit Bake-offcited by 64
  9. 2017Ensemble Samplingcited by 62
  10. 2017MNL-Bandit: A Dynamic Learning Approach to Assortment Selectioncited by 50
  11. 2016Cascading Bandits for Large-Scale Recommendation Problemscited by 45
  12. 2013Thompson Sampling for Complex Bandit Problemscited by 43
20 more
  1. 2015Bootstrapped Thompson Sampling and Deep Explorationcited by 40
  2. 2017Provably Optimal Algorithms for Generalized Linear Contextual Banditscited by 38
  3. 2014Efficient Learning in Large-Scale Combinatorial Semi-Banditscited by 36
  4. 2019Bootstrapping Upper Confidence Boundcited by 36
  5. 2017Thompson Sampling for the MNL-Banditcited by 35
  6. 2018Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Banditscited by 33
  7. 2019Perturbed-History Exploration in Stochastic Linear Banditscited by 28
  8. 2020Concentration Inequalities for Statistical Inferencecited by 24
  9. 2021Metadata-based Multi-Task Bandits with Bayesian Hierarchical Modelscited by 24
  10. 2022An Analysis of Ensemble Samplingcited by 23
  11. 2014Thompson sampling with the online bootstrapcited by 19
  12. 2019Perturbed-History Exploration in Stochastic Multi-Armed Banditscited by 16
  13. 2017Variational inference for the multi-armed contextual banditcited by 15
  14. 2019Thompson Sampling with Approximate Inferencecited by 15
  15. 2018Thompson Sampling Algorithms for Cascading Banditscited by 13
  16. 2020Residual Bootstrap Exploration for Bandit Algorithmscited by 12
  17. 2022Towards Scalable and Robust Structured Bandits: A Meta-Learning Frameworkcited by 10
  18. 2021Sharper Sub-Weibull Concentrationscited by 8
  19. 2022Residual Bootstrap Exploration for Stochastic Linear Banditcited by 7
  20. 2018New Insights into Bootstrapping for Banditscited by 6

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2025BanditSpec: Adaptive Speculative Decoding via Bandit Algorithmscited by 18
  2. 2024Improved Regret of Linear Ensemble Samplingcited by 6
  3. 2023An Online Bootstrap for Time Seriescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021GuideBoot: Guided Bootstrap for Deep Contextual Bandits
  2. 2025Multi-Armed Sampling Problem and the End of Exploration
  3. 2021Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits
  4. 2025Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Sampling
  5. 2026Bootstrap-Conditioned Action Selection with Tabular Foundation Models
  6. 2026Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
  7. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
  8. 2026RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits