Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Lists
Only you see this
Abstract
We prove that Thompson sampling exhibits $\tilde{O}(σd \sqrt{T} + d r \sqrt{\mathrm{Tr}(Σ_0)})$ Bayesian regret in the linear-Gaussian bandit with a $\mathcal{N}(μ_0, Σ_0)$ prior distribution on the coefficients, where $d$ is the dimension, $T$ is the time horizon, $r$ is the maximum $\ell_2$ norm of the actions, and $σ^2$ is the noise variance. In contrast to existing regret bounds, this shows that to within logarithmic factors, the prior-dependent ``burn-in'' term $d r \sqrt{\mathrm{Tr}(Σ_0)}$ decouples additively from the minimax (long run) regret $σd \sqrt{T}$. Previous regret bounds exhibit a multiplicative dependence on these terms. We establish these results via a new ``elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.
BibTeX
@inproceedings{zhu2026prior,
author = {Yifan Zhu and John C. Duchi and Benjamin Van Roy},
title = {{Prior Diffusiveness and Regret in the Linear-Gaussian Bandit}},
booktitle = {International Conference on Machine Learning},
year = {2026},
url = {https://openreview.net/forum?id=GeYKOC4BzB},
}Loading related content...