Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Yifan Zhu, John Duchi, Benjamin Van Roy

Introduction

In the realm of reinforcement learning and sequential decision-making, the linear bandit is a foundational model: an agent selects an action vector and receives a reward based on a linear function of that action, plus some noise. Thompson Sampling (TS) is a highly popular algorithm for this setting due to its simplicity and strong empirical performance.

However, a significant theoretical gap has persisted regarding its regret bounds. Historically, regret bounds—which measure the reward lost compared to an optimal, omniscient policy—suggested a multiplicative relationship between the uncertainty of the initial guess (the prior diffusiveness) and the problem's complexity (dimension and time). This implied that starting with a vague prior would cause regret to balloon massively over time. This paper demonstrates that this multiplicative penalty is an artifact of previous analytical limitations, not a fundamental flaw of Thompson Sampling.

Methodological Innovations

The authors focus on the Bayesian regret of Thompson Sampling in a linear-Gaussian setting. To overcome previous analytical hurdles, they introduce a novel mathematical tool: the Generalized Elliptical Potential Lemma.

Standard versions of this lemma, which are workhorses in bandit theory, typically require the initial precision of knowledge to meet a certain threshold (e.g., the identity matrix). The generalized version removes this restriction, accommodating nearly zero initial knowledge. It also introduces a flexible exponent ($p$) that enables a more surgical analysis of how uncertainty diminishes over time.

Key Results and Insights

Additive Decoupling of Regret

The paper establishes a much sharper Bayesian regret bound of $\tilde{O}(\sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)})$. Crucially, the prior uncertainty (the "burn-in" term, $d r \sqrt{\text{Tr}(\Sigma_0)}$) and the minimax rate ($\sigma d \sqrt{T}$) are decoupled additively rather than multiplicatively. Over long time horizons ($T$), this additive formulation yields a significantly smaller regret bound, finally aligning theoretical guarantees with the algorithm's strong empirical performance.

The Burn-in is Mandatory

The authors do not just provide a better upper bound; they also prove a corresponding lower bound. This demonstrates that the initial burn-in cost is unavoidable. Any algorithm must suffer a regret penalty proportional to the prior's diffusiveness—you cannot escape the cost of starting from scratch.

Information Localization

The analysis highlights that after the initial exploration phase (the burn-in), observation noise becomes the dominant factor in regret. At this stage, the influence of the starting prior effectively washes out.

Beyond Gaussian Distributions

The authors extend their findings to a broader class of "strongly log-concave" distributions. They prove that this additive decoupling is a fundamental property of these models, demonstrating that the dynamics hold even when the noise and prior are not strictly Gaussian, provided their log-density functions exhibit the right curvature.

Limitations and Future Directions

While this paper significantly tightens the theoretical understanding of Thompson Sampling, it operates strictly in the Bayesian setting, assuming the true underlying parameter is drawn from the specified prior distribution. It does not address misspecified priors where the initial guess is fundamentally incorrect.

Furthermore, extending these sharp additive bounds to frequentist regret (worst-case performance for a fixed parameter) remains an open challenge. Finally, while broader than Gaussian models, the requirement for log-concavity is still restrictive, leaving room for future exploration into whether these burn-in dynamics hold for heavier-tailed or more complex distributions.

Summary updated

Abstract

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.
BibTeX
@inproceedings{zhu2026prior,
  author = {Yifan Zhu and John 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},
}
Figure