Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

We prove that Thompson sampling exhibits \tilde{O}(σd \sqrt{T} + d r \sqrt{Tr(Σ_0)}) Bayesian regret in the linear-Gaussian bandit with a 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{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.