# Linear Ensemble Sampling with Smaller Ensembles

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 22 references that are in the map.
- First posted on arXiv 12 Sep 2026.

## Builds on (most cited first, 16 of 16)

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [On Frequentist Regret of Linear Thompson Sampling](https://mlsanity.com/paper/2006.06790/) (2020)
- [Deep Exploration for Recommendation Systems](https://mlsanity.com/paper/2109.12509/) (2021)
- [Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making](https://mlsanity.com/paper/2007.15788/) (2020)
- [Ensemble sampling for linear bandits: small ensembles suffice](https://mlsanity.com/paper/2311.08376/) (2023)
- [Improved Regret of Linear Ensemble Sampling](https://mlsanity.com/paper/2411.03932/) (2024)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Sharp analysis of linear ensemble sampling](https://mlsanity.com/paper/2602.08026/) (2026)

## Abstract (arXiv)

Ensemble sampling offers a practical approach to randomized exploration by maintaining a collection of models, but how small an ensemble can be while retaining strong regret guarantees remains unresolved. In particular, the existing guarantees use an ensemble size of Theta(dlog T), leaving a logarithmic gap in the horizon T relative to the intrinsic Omega(d) ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to Theta(dlog d+dloglog T), while preserving the state-of-the-art tilde O(d3/2√ T) regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality K, the proposed algorithm achieves the sharper regret bound tilde O(d√Tlog K). To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms: the tilde O(d3/2√T) rate for arbitrary bounded arm sets and the tilde O (d√Tlog K) rate for finite arm sets. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.