Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

We prove that Thompson sampling exhibits $\tilde{O}(\sigma d \sqrt{T} + d r \sqrt{\mathrm{Tr}(\Sigma_0)})$ Bayesian regret in the linear-Gaussian bandit with a $\mathcal{N}(\mu_0, \Sigma_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 $\sigma^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}(\Sigma_0)}$ decouples additively from the minimax (long run) regret \sigma 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.

Many learning systems improve by trying actions, observing feedback, and gradually learning which actions work best. But if the system starts with very uncertain beliefs, it is unclear how much this initial uncertainty should slow down learning. Prior analyses suggested that this uncertainty could keep making learning harder over the entire time horizon. We show that, for an important model of sequential decision-making with noisy feedback, this pessimism is unnecessary. For Thompson sampling, a widely used strategy that chooses actions by sampling from its current beliefs, the cost of initial uncertainty is mostly a one-time “burn-in” cost. After this early phase, performance is governed mainly by the noise in the feedback, not by how uncertain the system was at the start. We also prove that this burn-in cost is unavoidable in general: any method must spend some effort resolving large initial uncertainty. Our results give a sharper understanding of when Thompson sampling is efficient, and help explain why broad prior uncertainty need not permanently harm long-run learning.