# On Frequentist Regret of Linear Thompson Sampling

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [When and why randomised exploration works (in linear bandits)](https://mlsanity.com/paper/2502.08870/) (2025)
- [Improved Regret of Linear Ensemble Sampling](https://mlsanity.com/paper/2411.03932/) (2024)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits](https://mlsanity.com/paper/2306.14872/) (2023)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Robust Thompson Sampling Algorithms Against Reward Poisoning Attacks](https://mlsanity.com/paper/2410.19705/) (2024)
- [Sharp analysis of linear ensemble sampling](https://mlsanity.com/paper/2602.08026/) (2026)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Exploration via Feature Perturbation in Contextual Bandits](https://mlsanity.com/paper/2510.17390/) (2025)
- [Thompson Sampling Is 2-Competitive for Mistakes](https://mlsanity.com/paper/2607.12389/) (2026)
- [Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling](https://mlsanity.com/paper/2609.01999/) (2026)
- [Linear Ensemble Sampling with Smaller Ensembles](https://mlsanity.com/paper/2609.13954/) (2026)

## Abstract (arXiv)

This paper studies the stochastic linear bandit problem, where a decision-maker chooses actions from possibly time-dependent sets of vectors in ℝd and receives noisy rewards. The objective is to minimize regret, the difference between the cumulative expected reward of the decision-maker and that of an oracle with access to the expected reward of each action, over a sequence of T decisions. Linear Thompson Sampling (LinTS) is a popular Bayesian heuristic, supported by theoretical analysis that shows its Bayesian regret is bounded by widetildeO(d√T), matching minimax lower bounds. However, previous studies demonstrate that the frequentist regret bound for LinTS is widetildeO(d√dT), which requires posterior variance inflation and is by a factor of √d worse than the best optimism-based algorithms. We prove that this inflation is fundamental and that the frequentist bound of widetildeO(d√dT) is the best possible, by demonstrating a randomization bias phenomenon in LinTS that can cause linear regret without inflation.We propose a data-driven version of LinTS that adjusts posterior inflation using observed data, which can achieve minimax optimal frequentist regret, under additional conditions. Our analysis provides new insights into LinTS and settles an open problem in the field.