# On the Prior Sensitivity of Thompson Sampling

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

## Key facts

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

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

- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Metalearning Linear Bandits by Prior Update](https://mlsanity.com/paper/2107.05320/) (2021)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Contextual Thompson Sampling via Generation of Missing Data](https://mlsanity.com/paper/2502.07064/) (2025)
- [Best Arm Identification with Possibly Biased Offline Data](https://mlsanity.com/paper/2505.23165/) (2025)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)
- [Contextual Online Pricing with (Biased) Offline Data](https://mlsanity.com/paper/2507.02762/) (2025)
- [Tractable Optimality in Episodic Latent MABs](https://mlsanity.com/paper/2210.03528/) (2022)
- [Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning](https://mlsanity.com/paper/2011.14266/) (2020)
- [Ranking In Generalized Linear Bandits](https://mlsanity.com/paper/2207.00109/) (2022)
- [Bayesian policy gradient and actor-critic algorithms](https://mlsanity.com/paper/2604.27563/) (2026)
- [The Value of Mechanistic Priors in Sequential Decision Making](https://mlsanity.com/paper/2605.10018/) (2026)
- [Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift](https://mlsanity.com/paper/2605.10289/) (2026)
- [The Greedy Advantage in Finite-Horizon Bandits](https://mlsanity.com/paper/2607.29375/) (2026)

## Abstract (arXiv)

The empirically successful Thompson Sampling algorithm for stochastic bandits has drawn much interest in understanding its theoretical properties. One important benefit of the algorithm is that it allows domain knowledge to be conveniently encoded as a prior distribution to balance exploration and exploitation more effectively. While it is generally believed that the algorithm's regret is low (high) when the prior is good (bad), little is known about the exact dependence. In this paper, we fully characterize the algorithm's worst-case dependence of regret on the choice of prior, focusing on a special yet representative case. These results also provide insights into the general sensitivity of the algorithm to the choice of priors. In particular, with p being the prior probability mass of the true reward-generating model, we prove O(√T/p) and O(√(1-p)T) regret upper bounds for the bad- and good-prior cases, respectively, as well as matching lower bounds. Our proofs rely on the discovery of a fundamental property of Thompson Sampling and make heavy use of martingale theory, both of which appear novel in the literature, to the best of our knowledge.