Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Problem Statement
The paper addresses the linear-Gaussian bandit problem, a sequential decision-making setting where a player selects actions $A_t \in \mathcal{A} \subset \mathbb{R}^d$ to maximize cumulative rewards. The reward at time $t$ is generated by $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$, where $\theta_\star$ is an unknown parameter vector and $W_{t+1}$ is i.i.d. Gaussian noise with variance $\sigma^2$. The objective is to minimize the Bayesian regret, defined as the expected difference between the reward of the optimal action and the chosen action over a horizon $T$, assuming a prior distribution $\rho$ on $\theta_\star$. Specifically, the authors focus on the case where $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$ and the action set is a scaled $\ell_2$-ball of radius $r$.

Methodology
The authors analyze Thompson sampling, a posterior sampling algorithm that draws a parameter estimate $\hat{\theta}_t$ from the posterior distribution given the history $H_t$ and selects the action maximizing the expected reward under $\hat{\theta}_t$.

To derive the regret bounds, the authors employ a decomposition of the instantaneous regret into two terms:

1. Term (I): The regret incurred when the sampled parameter $\hat{\theta}_t$ is close to the true parameter $\theta_\star$ (within a high-probability event defined by the posterior precision matrix).
2. Term (II): The regret incurred when the sampled parameter is far from the true parameter.

The core technical innovation lies in the analysis of Term (I). The authors introduce a generalized elliptical potential lemma (Lemma 3). Unlike standard elliptical potential lemmas used in linear bandit literature (e.g., Abeille & Lazaric, 2017; Dani et al., 2008), which typically require the initial precision matrix to be bounded away from zero (e.g., $V_0 \succeq I$) and bound quadratic errors, this new lemma:

• Allows the initial precision matrix $V_0$ to be arbitrarily small (or even zero in the limit), accommodating diffuse priors.
• Introduces a flexible exponent $p \in [0, 1]$ in the summation of norms.
• Explicitly separates the bound into a logarithmic determinant term (capturing the long-run information gain) and a trace term involving the initial precision matrix (capturing the initial "burn-in" cost).

The analysis of Term (II) relies on standard concentration inequalities for Gaussian distributions to bound the probability of large deviations between $\hat{\theta}_t$ and $\theta_\star$.

Key Contributions and Results
The primary contribution is a new Bayesian regret bound for Thompson sampling in the linear-Gaussian setting that decouples the prior-dependent "burn-in" term from the minimax regret rate.

1. Improved Regret Bound: The authors prove that Thompson sampling achieves a regret of:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   Here, $\sigma d \sqrt{T}$ represents the asymptotic minimax rate, while $d r \sqrt{\text{Tr}(\Sigma_0)}$ represents the initial cost of reducing uncertainty from the prior scale to the noise scale.

2. Decoupling of Terms: Previous bounds (e.g., Kalkanli & Özgür, 2020) exhibited a multiplicative dependence, such as $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, where the prior diffusiveness $\sqrt{\text{Tr}(\Sigma_0)}$ scaled the entire minimax rate. The new result shows that, up to logarithmic factors, the prior diffusiveness only adds an additive constant to the regret, independent of the time horizon $T$.

3. Lower Bounds: The paper establishes a lower bound for any policy in this setting, demonstrating that the burn-in term $d r \sqrt{\text{Tr}(\Sigma_0)}$ is unavoidable for Gaussian priors. This confirms that the additive structure of the upper bound is tight (up to logarithmic factors) and that the prior diffusiveness cannot be eliminated from the regret entirely.

4. Generalization: The authors note that their results can be extended to strongly log-concave priors and noise distributions, not limited strictly to the Gaussian case.

Significance
The paper claims that its results resolve a looseness in existing regret bounds for Thompson sampling. By proving that the prior-dependent term is additive rather than multiplicative, the work clarifies the role of prior diffusiveness: it acts as a one-time "burn-in" cost required to reduce uncertainty to the level of observation noise, after which the algorithm's performance is governed solely by the noise variance $\sigma$ and the dimension $d$. This provides a more precise characterization of the algorithm's efficiency, particularly in regimes where the prior is highly diffuse (large $\text{Tr}(\Sigma_0)$), showing that such diffusiveness does not permanently degrade the asymptotic convergence rate. The introduction of the generalized elliptical potential lemma is presented as a tool that enables more flexible analysis of stochastic optimization problems where initial uncertainty may be unbounded.