Sharp analysis of linear ensemble sampling
Arya Akhavan, David Janz, Csaba Szepesvári · 2026
Read Sharp analysis of linear ensemble sampling by Arya Akhavan, David Janz, Csaba Szepesvári (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08026.txt.
Description
Ensemble sampling explores uncertain choices by perturbing estimates with random noise, but its theory lagged behind the Thompson sampling benchmark it resembles. David Janz and two co-authors give a sharp analysis for linear bandits with standard Gaussian perturbations.
With an ensemble size scaling like dimension times log horizon, ensemble sampling attains regret of order dimension to the three-halves times root horizon, closing the gap to Thompson sampling at comparable compute. The proof reduces the analysis to a time-uniform exceedance problem for independent Brownian motions, a continuous-time viewpoint the authors call strikingly natural. Bandit theorists gain both a tight bound and a proof technique worth reusing.
Catalog record
| CREATOR | Arya Akhavan, David Janz, Csaba Szepesvári |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-08026