Sharp analysis of linear ensemble sampling

David Janz, Arya Akhavan, Csaba Szepesvári
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3716-3750, 2026.

Abstract

We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size $m=\Theta(d\log n)$, ES attains $\tilde O(d^{3/2}\sqrt n)$ high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for $m$ independent Brownian motions. This continuous-time lens appears particularly natural here: it yields an exact representation of the relevant discrete-time processes, and we do not know another route to a sharp ES bound.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-janz26a, title = {Sharp analysis of linear ensemble sampling}, author = {Janz, David and Akhavan, Arya and Szepesv{\'a}ri, Csaba}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3716--3750}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/janz26a/janz26a.pdf}, url = {https://proceedings.mlr.press/v336/janz26a.html}, abstract = {We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size $m=\Theta(d\log n)$, ES attains $\tilde O(d^{3/2}\sqrt n)$ high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for $m$ independent Brownian motions. This continuous-time lens appears particularly natural here: it yields an exact representation of the relevant discrete-time processes, and we do not know another route to a sharp ES bound.} }
Endnote
%0 Conference Paper %T Sharp analysis of linear ensemble sampling %A David Janz %A Arya Akhavan %A Csaba Szepesvári %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-janz26a %I PMLR %P 3716--3750 %U https://proceedings.mlr.press/v336/janz26a.html %V 336 %X We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size $m=\Theta(d\log n)$, ES attains $\tilde O(d^{3/2}\sqrt n)$ high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for $m$ independent Brownian motions. This continuous-time lens appears particularly natural here: it yields an exact representation of the relevant discrete-time processes, and we do not know another route to a sharp ES bound.
APA
Janz, D., Akhavan, A. & Szepesvári, C.. (2026). Sharp analysis of linear ensemble sampling. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3716-3750 Available from https://proceedings.mlr.press/v336/janz26a.html.

Related Material