@inproceedings{
janz2024ensemble,
title={Ensemble sampling for linear bandits: small ensembles suffice},
author={David Janz and Alexander Litvak and Csaba Szepesvari},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=SO7fnIFq0o}
}
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 $\smash{d \log T}$ incurs regret at most of the order $\smash{(d \log T)^{5/2} \sqrt{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{\sqrt{T}}$ order regret. Ours is also the first result that allows infinite action sets.
Ensemble sampling for linear bandits: small ensembles suffice
David Janz Alexander Litvak Csaba Szepesvari