# Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

arXiv: https://arxiv.org/abs/2601.02022 · HTML: https://mlsanity.com/paper/2601.02022/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 5 Jan 2026.

## Builds on (most cited first, 8 of 8)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [The Elliptical Potential Lemma Revisited](https://mlsanity.com/paper/2010.10182/) (2020)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Linear Bandits on Ellipsoids: Minimax Optimal Algorithms](https://mlsanity.com/paper/2502.17175/) (2025)

## Built on by (most cited first, 1 of 1)

- [An Information-Theoretic Definition for Open-Ended Learning](https://mlsanity.com/paper/2606.08369/) (2026)

## Abstract (arXiv)

We prove that Thompson sampling exhibits tildeO(σ d √T + d r √Tr(Sigma0)) Bayesian regret in the linear-Gaussian bandit with a N(μ0, Sigma0) prior distribution on the coefficients, where d is the dimension, T is the time horizon, r is the maximum ℓ2 norm of the actions, and σ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 √Tr(Sigma0) decouples additively from the minimax (long run) regret σ d √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.