Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Benjamin Van Roy; John C. Duchi; Yifan Zhu

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

T0 review · 0 major / 7 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In the linear-Gaussian bandit, Thompson sampling's Bayesian regret is, up to log factors, the sum of the minimax rate and a prior-diffusiveness burn-in that no algorithm can avoid.

desk verdict A real advance: the additive decoupling of prior-diffusiveness burn-in from the noise-driven minimax rate in the linear-Gaussian bandit, with a proof that holds up on inspection. read the letter →

arxiv 2601.02022 v2 pith:37GP7ART submitted 2026-01-05 cs.LG

Yifan Zhu , John C. Duchi , Benjamin Van Roy This is my paper · ORCID

classification cs.LG MSC 62L0568W27

keywords ThompsonsamplinglinearbanditsBayesianregretboundsellipticalpotentiallemmapriordiffusivenessburn-inGaussian

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that for linear-Gaussian bandits, Thompson sampling's Bayesian regret is, up to log factors, the sum of two pieces: the long-run minimax rate σd√T set by observation noise, and a 'burn-in' term dr√Tr(Σ0) that reflects how diffuse the initial Gaussian prior is. In earlier bounds these two quantities multiplied each other, making the regret look worse whenever the prior is spread out. The paper shows the prior-dependent term is actually additive and unavoidable: any policy must pay it while learning the initial uncertainty across all d dimensions. This makes Thompson sampling near-optimal in most parameter regimes and clarifies what prior choice can and cannot affect.

What carries the argument

The load-bearing tool is a generalized elliptical potential lemma. Standard versions assume the initial precision matrix is at least the identity; this one allows an arbitrary positive definite V0 and any exponent p∈[0,1], producing a bound with two terms: a log-determinant term capturing the usual exploration cost and a trace term Tr(V0^{−p}) − Tr(VT^{−p}) that exactly accounts for a diffuse starting prior. Applied with p=1/2 and V0 scaled to σ²Σ0^{−1}/r², it converts the sum of instantaneous regrets into the additive form.

What would settle it

Run Thompson sampling with exact posterior sampling on a d-dimensional linear-Gaussian bandit with action set the unit ball, prior covariance S²I, noise σ, and horizon T=d. The lower bound says any policy must have Bayesian regret at least c·S·d^{3/2} for a numerical constant c. If a policy is found whose regret is o(S d^{3/2}) on this instance, the claim that the burn-in term is unavoidable is false. Conversely, checking that regret at T=r²Tr(Σ0)/σ² is dominated by dr√Tr(Σ0), independent of σ, would confirm the additive decoupling.

Watch

Extended reading notes

Core claim

In the linear-Gaussian bandit with actions in an ℓ2 ball of radius r and Gaussian prior N(0,Σ0) on the unknown coefficients, Thompson sampling suffers Bayesian regret Õ(σd√T + dr√Tr(Σ0)). The proof introduces a generalized elliptical potential lemma that bounds sums of Mahalanobis norms with an explicit dependence on the initial potential, yielding the additive burn-in term. A companion lower bound shows the dr√Tr(Σ0) term is unavoidable for any policy under standard Gaussian priors, up to log factors.

Load-bearing premise

The theorem assumes the prior is well-specified—θ* really is drawn from N(0,Σ0)—and the noise variance σ² is known exactly; if either fails, the additive decoupling need not hold, since the analysis is Bayesian rather than frequentist.

Editorial extensions

If this is right

Thompson sampling is near-optimal for linear-Gaussian bandits across essentially all parameter regimes: when T ≤ r²Tr(Σ0)/σ² the burn-in term dominates and matches the lower bound; when T is large the long-run rate σd√T dominates.
Prior diffusiveness affects only the early burn-in period, not the asymptotically dominant regret.
The bound extends to strongly log-concave priors and noise distributions via sub-Gaussian concentration (Theorem 9).
The generalized elliptical potential lemma is a standalone tool for linear bandit analysis with arbitrary initial precision.
The lower bound (Theorem 6) shows any policy pays a burn-in proportional to the tail eigenvalues of Σ0, so the additive term is not an artifact of the analysis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The additive decoupling suggests that a practitioner can choose an aggressively diffuse prior without harming long-run regret; the only cost is a fixed burn-in that is amortized over a long horizon.
Because the burn-in depends on the trace rather than the operator norm of Σ0, a prior with many small-variance directions is cheaper than one with a single large-variance direction—a distinction that could guide prior elicitation.
For misspecified priors (where θ* is not drawn from N(0,Σ0)), the additive bound should fail; quantifying that failure could measure the value of prior knowledge, a natural extension the paper leaves open.
The lower-bound technique—combining Weyl's inequality with a variance decomposition of posterior uncertainty—might carry over to other Bayesian bandit problems with Gaussian structure, such as kernelized or Gaussian-process bandits.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Let me cut to the chase: this is a genuine advance in the linear-Gaussian bandit. The bound Reg(T) = Õ(σd√T + dr√Tr(Σ0)) finally separates the prior-diffusiveness burn-in from the long-run minimax rate, and the upper and lower bounds line up to within logs in the regimes the authors claim. I'd send it to review.

The new piece that matters is the generalized elliptical potential lemma (Lemma 3), which lets V0 be near zero and handles a flexible exponent p. The proof via the case split, Sherman-Morrison, and Hölder is coherent. I checked the application to the Thompson sampling decomposition; the χ² concentration and the E(β) event are standard and handled correctly. The lower bound in Section 4 is a clean adaptation of Rusmevichientong-Tsitsiklis, with the mild caveat that it matches the upper bound only for non-pathological eigenvalue scalings; Corollary 8 covers the polynomial case. Minor issues: Lemma 12's summation should start at i = t+2, but the final summation in Theorem 6 absorbs this, so the conclusion stands. Also, the log-concave generalization in Section 5 is sketched in the main text with the proof deferred to the appendix; the appendix argument is plausible but less polished and should be checked carefully by a referee.

The soft spots are actually scope conditions more than errors. This is a Bayesian regret bound under a well-specified Gaussian prior and known noise variance, as the authors state in Section 6. That means the additive decoupling should not be read as a frequentist guarantee under prior misspecification. Exact posterior sampling is assumed, which is standard for Thompson sampling analyses but worth flagging. None of this undermines the central theorem, which is proven with explicit constants and no fitted parameters.

Citation pattern looks fine: the comparison to Kalkanli and Özgür's multiplicative bound is accurate, and the related-work discussion is honest about what each prior result does and doesn't capture. The new elliptical potential lemma is likely to be reusable beyond this specific setting.

Who gets value from this? Bandit theorists, especially those working on posterior sampling or elliptical potential arguments. It deserves a serious referee: the proof is nontrivial, the result improves on prior bounds, and the lower bound gives evidence of near-optimality. My recommendation: full peer review, with attention to the log-concave appendix and the minor index typos in the lower-bound section.

Referee Report

0 major / 7 minor

Summary. The paper studies Bayesian regret of Thompson sampling in the linear-Gaussian bandit with actions in rB_2^d and a Gaussian prior N(0, Σ0). Theorem 1 states an upper bound of order σd√T·C2 + 3r√d·Tr(Σ0^{1/2})C1 + r√(2TrΣ0), which Corollary 2 converts to Õ(σd√T + dr√Tr(Σ0)). The proof introduces a generalized elliptical potential lemma (Lemma 3) that controls sums of the form ∑∥u_t∥^{2p}_{V_t^{-1}} with an explicit burn-in term Tr(V_0^{-p})−Tr(V_T^{-p}), and combines it with a standard regret decomposition and χ² concentration for the complement event. Section 4 provides a lower bound based on prior eigenvalues, arguing that a burn-in term is unavoidable. Section 5 extends the upper bound to strongly log-concave priors and noise. The scope is explicitly Bayesian with a well-specified prior and known noise variance.

Significance. If correct, the result meaningfully improves on prior bounds in which prior diffusiveness multiplies the T-dependent term: the burn-in cost dr√Tr(Σ0) decouples additively from the minimax rate σd√T. The proof is self-contained and derives the bound without fitted constants; C1 and C2 are explicit functions of the problem parameters, and the generalized elliptical potential lemma appears to be a new and potentially reusable tool. The lower bound, while not optimal for every spectral shape, matches the upper bound up to logarithmic factors for polynomially scaled eigenvalue sequences. The paper is also careful in stating its limitations: Bayesian regret under a well-specified Gaussian prior and known σ, as noted in Section 6.

minor comments (7)

[Section 3, proof of Lemma 3] The telescoping sum after applying Hölder is written with log det V_{T+1}/det V_1; the product telescopes to V_T/V_0. The displayed index is inconsistent with Lemma 3's statement and with the subsequent application to U_T/U_0. Please correct the indices.
[Section 2.1, final display before Theorem 1] The displayed final bound contains an extra √2 multiplier before d√T σ C2. The derivation from inequality (11), with β=√d C1 and C2=C1√(2 log(...)), gives σd√T C2, not √2 σ d√T C2. This is a typographical inconsistency between the proof and the theorem statement.
[Section 4, Lemma 12] The summation in Lemma 12 should run from i=t+2 to d, not i=t+1, based on the Weyl-inequality argument preceding it. The final summation in Theorem 6 should be aligned with this index shift, with the cap at min{T,d} made explicit.
[Section 4, Lemma 10] The basis vector u_{t,1}=μ_t/∥μ_t∥_2 is undefined when μ_t=0, which occurs at t=0 for the zero-mean prior. The proof should specify an arbitrary orthonormal basis in that case; the argument is unchanged.
[Section 2.1.3] The concentration statement says the high-probability event holds 'for all t∈{1,...,T}', but the regret sum runs over t=0,...,T−1. This is only a relabeling issue but should be corrected for consistency.
[Related work / Introduction] The description of Kalkanli and Özgür's bound differs between the introduction (d√T(σ²+r²TrΣ0) log(1+T/d)) and the related-work paragraph (σd√T + dr√Tr(Σ0)T). Please reconcile the two descriptions and cite the exact form.
[Throughout] Several typos should be fixed: 'trivally' near inequality (10), 'random variabels' in Appendix B.1, and 'Leinder' for Leindler in Appendix B.1.1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main regret bound and lower bound are derived from explicit assumptions with self-contained proofs.

full rationale

The paper's central result, Theorem 1, is obtained by substituting explicit algorithm definitions into a regret decomposition (Eq. 6), bounding term (I) with the new elliptical-potential Lemma 3 (proved in Section 3 using Sherman-Morrison and Hölder) and term (II) with chi-square concentration. The constants C1 and C2 are explicit functions of problem inputs; no quantity is fitted to the data being predicted, and no step equates the target result to an input by definition. The lower bound (Theorem 6) is an independently argued information-theoretic/adversarial argument adapting Rusmevichientong and Tsitsiklis (2010), not a restatement of Theorem 1. Self-citations (Dong and Van Roy 2018; Russo and Van Roy 2013, 2014, 2016) occur only in the related-work comparison and are not load-bearing in the proof. The paper explicitly acknowledges the Bayesian/well-specified-prior scope in Section 6, which is an assumption, not a circular step. Thus no circularity is present.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The theorem introduces no fitted constants and no new entities. The constants C1 and C2 are explicit logarithmic functions of problem parameters. The proof relies only on standard mathematical results plus the explicitly stated canonical Gaussian model assumptions.

assumptions (8)

standard math Gaussian conjugacy: posterior precision is V_t = Σ0^{-1} + σ^{-2} Σ_{i<t} A_i A_i^T.
Used in Eq. (4) and the posterior sampling step; exact under the stated Gaussian prior and Gaussian noise model.
standard math Chi-square tail bound: P(χ²_d - d ≥ s) ≤ max{e^{-s²/(8d)}, e^{-s/8}}.
Used in Section 2.1.2 to choose β and control the small-probability regret term (II).
standard math Convexity of -Tr(M^p) on positive definite matrices for 0 < p ≤ 1 (Lewis 1996).
Used in the interpolation argument in the proof of Lemma 3.
standard math Hölder's inequality, in scalar and summation forms.
Used in Lemma 5 and in the final summation step of Lemma 3.
standard math Weyl's eigenvalue perturbation inequality for low-rank updates.
Used in Lemma 11 and the lower bound proof to control how the posterior covariance eigenvalues shrink.
standard math Prékopa-Leindler inequality and sub-Gaussian concentration bounds for strongly log-concave distributions.
Used in Section 5 / Appendix B for the strongly log-concave generalization.
domain assumption Well-specified prior and known noise variance: θ* ~ N(0,Σ0), W_t iid N(0,σ²), with σ² and Σ0 known.
The Bayesian regret definition and the whole analysis assume the prior is the true generating distribution; Section 6 lists this as a limitation.
domain assumption Actions are bounded in Euclidean norm: A ⊂ rB_2^d.
Used throughout to bound instantaneous regret, normalize the elliptical potential lemma, and construct the lower bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Prior Diffusiveness and Regret in the Linear-Gaussian Bandit." pith.science (2026). https://pith.science/paper/37GP7ART

@misc{pith2026260102022,
  author       = {Pith},
  title        = {Pith review of: Prior Diffusiveness and Regret in the Linear-Gaussian Bandit},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/37GP7ART}},
  note         = {Machine review of arXiv:2601.02022}
}

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 1 linked inside Pith

[1]

Abbasi-Yadkori, D

Y. Abbasi-Yadkori, D. P \'a l, and C. Szepesv \'a ri. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312--2320, 2011

2011
[2]

Abeille and A

M. Abeille and A. Lazaric. Linear T hompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

2017
[3]

Agrawal and N

S. Agrawal and N. Goyal. T hompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, 2013

2013
[4]

K. Ball. An elementary introduction to modern convex geometry. In S. Levy, editor, Flavors of Geometry, pages 1--58. MSRI Publications, 1997

1997
[5]

Buldygin and Y

V. Buldygin and Y. Kozachenko. Metric Characterization of Random Variables and Random Processes, volume 188 of Translations of Mathematical Monographs. American Mathematical Society, 2000

2000
[6]

Carpentier, C

A. Carpentier, C. Vernade, and Y. Abbasi-Yadkori. The elliptical potential lemma revisited. arXiv:2010.10182 [stat.ML], 2020

arXiv 2010
[7]

S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, pages 844--853, 2017

2017
[8]

V. Dani, T. Hayes, and S. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the Twenty First Annual Conference on Computational Learning Theory, 2008

2008

Show all 23 references

[9]

Dong and B

S. Dong and B. Van Roy. An information-theoretic analysis for T hompson sampling with many actions. In Advances in Neural Information Processing Systems 31, 2018

2018
[10]

S. B. Gales, S. Sethuraman, and K.-S. Jun. Norm-agnostic linear bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 73--91, 2022

2022
[11]

Hamidi and M

N. Hamidi and M. Bayati. Technical note -- the elliptical potential lemma for general distributions with an application to linear T hompson sampling. Operations Research, 71 0 (4): 0 1434--1439, 2022

2022
[12]

Kalkanli and A

C. Kalkanli and A. \" O zg\" u r. An improved regret bound for T hompson sampling in the G aussian linear bandit setting. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2783--2788, 2020. doi:10.1109/ISIT44484.2020.9174371

2020
[13]

A. S. Lewis. Convex analysis on the H ermitian matrices. SIAM Journal on Optimization, 6: 0 164--177, 1996

1996
[14]

Rusmevichientong and J

P. Rusmevichientong and J. N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35 0 (2): 0 395--411, 2010

2010
[15]

Russo and B

D. Russo and B. Van Roy . Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems 26, 2013

2013
[16]

Russo and B

D. Russo and B. Van Roy . Learning to optimize via posterior sampling. Mathematics of Operations Research, 39 0 (4): 0 1221--1243, 2014

2014
[17]

Russo and B

D. Russo and B. Van Roy . An information-theoretic analysis of T hompson sampling. Journal of Machine Learning Research, 17 0 (68): 0 1--30, 2016

2016
[18]

Srinivas, A

N. Srinivas, A. Krause, S. Kakade, and M. Seeger. G aussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, 2010

2010
[19]

W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25 0 (3-4): 0 285--294, 1933

1933
[20]

Vershynin

R. Vershynin. High Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2019

2019
[21]

M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019

2019
[22]

Zhang, H

R. Zhang, H. H \'e di, and C. Richard. Linear bandits on ellipsoids: Minimax optimal algorithms. In N. Haghtalab and A. Moitra, editors, Proceedings of the Thirty Eighth Annual Conference on Computational Learning Theory, volume 291 of Proceedings of Machine Learning Research,...

2025
[23]

Zhang, J

Z. Zhang, J. Yang, X. Ji, and S. S. Du. Improved variance-aware confidence sets for linear bandits and linear mixture MDP . In Advances in Neural Information Processing Systems 34, 2021

2021

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Abbasi-Yadkori, D

Y. Abbasi-Yadkori, D. P \'a l, and C. Szepesv \'a ri. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312--2320, 2011

2011

[2] [2]

Abeille and A

M. Abeille and A. Lazaric. Linear T hompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

2017

[3] [3]

Agrawal and N

S. Agrawal and N. Goyal. T hompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, 2013

2013

[4] [4]

K. Ball. An elementary introduction to modern convex geometry. In S. Levy, editor, Flavors of Geometry, pages 1--58. MSRI Publications, 1997

1997

[5] [5]

Buldygin and Y

V. Buldygin and Y. Kozachenko. Metric Characterization of Random Variables and Random Processes, volume 188 of Translations of Mathematical Monographs. American Mathematical Society, 2000

2000

[6] [6]

Carpentier, C

A. Carpentier, C. Vernade, and Y. Abbasi-Yadkori. The elliptical potential lemma revisited. arXiv:2010.10182 [stat.ML], 2020

arXiv 2010

[7] [7]

S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, pages 844--853, 2017

2017

[8] [8]

V. Dani, T. Hayes, and S. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the Twenty First Annual Conference on Computational Learning Theory, 2008

2008