mlsanityData to 7 Oct 2026

Ensemble sampling for linear bandits: small ensembles suffice

arXiv 2311.08376 ↗First posted 14 Nov 2023stat.ML cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We provide the first useful and rigorous analysis of ensemble sampling for the stochastic linear bandit setting. In particular, we show that, under standard assumptions, for a d-dimensional stochastic linear bandit with an interaction horizon T, ensemble sampling with an ensemble of size of order d log T incurs regret at most of the order (d log T)5/2 √T. Ours is the first result in any structured setting not to require the size of the ensemble to scale linearly with T -- which defeats the purpose of ensemble sampling -- while obtaining near smash√T order regret. Our result is also the first to allow for infinite action sets.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 15 of its 39 references that are in the map. First posted on arXiv 14 Nov 2023.

Builds on

15 of 39 references.

References · 15

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018Exploration by Random Network Distillationcited by 966
  3. 2016Deep Exploration via Bootstrapped DQNcited by 518
  4. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 218
  5. 2017Deep Exploration via Randomized Value Functionscited by 155
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2020Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planningcited by 83
  8. 2017Ensemble Samplingcited by 62
  9. 2020Hypermodels for Explorationcited by 37
  10. 2019Perturbed-History Exploration in Stochastic Linear Banditscited by 28
  11. 2020Targeting for long-term outcomescited by 23
  12. 2022An Analysis of Ensemble Samplingcited by 23
3 more
  1. 2018Coordinated Exploration in Concurrent Reinforcement Learningcited by 17
  2. 2021Deep Exploration for Recommendation Systemscited by 14
  3. 2023Exploration via linearly perturbed loss minimisationcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 3.

7 papers.

  1. 2025When and why randomised exploration works (in linear bandits)cited by 8
  2. 2024Improved Regret of Linear Ensemble Samplingcited by 6
  3. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  4. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  5. 2026Sharp analysis of linear ensemble samplingcited by 1
  6. 2026Randomized Exploration for Linear Bandits via Absolute Perturbationscited by 0
  7. 2026Linear Ensemble Sampling with Smaller Ensemblescited by 0