Ensemble sampling for linear bandits: small ensembles suffice

arXiv:2311.08376v2 Announce Type: replace-cross
Abstract: 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 …

abstract analysis arxiv assumptions cs.lg ensemble horizon linear sampling show small standard stat.ml stochastic type