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