# Prior-free and prior-dependent regret bounds for Thompson Sampling

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2013.

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

- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Metalearning Linear Bandits by Prior Update](https://mlsanity.com/paper/2107.05320/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [Leveraging Demonstrations to Improve Online Learning: Quality Matters](https://mlsanity.com/paper/2302.03319/) (2023)
- [Module-wise Adaptive Distillation for Multimodality Foundation Models](https://mlsanity.com/paper/2310.04550/) (2023)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)
- [Bayesian Reinforcement Learning with Limited Cognitive Load](https://mlsanity.com/paper/2305.03263/) (2023)
- [Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits](https://mlsanity.com/paper/2302.01544/) (2023)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)
- [Overcoming Prior Misspecification in Online Learning to Rank](https://mlsanity.com/paper/2301.10651/) (2023)
- [Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averages](https://mlsanity.com/paper/2308.14350/) (2023)
- [Learning with Posterior Sampling for Revenue Management under Time-varying Demand](https://mlsanity.com/paper/2405.04910/) (2024)
- [Online Bayesian Meta-Learning for Cognitive Tracking Radar](https://mlsanity.com/paper/2207.06917/) (2022)
- [A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles](https://mlsanity.com/paper/2301.07156/) (2023)
- [Thompson Sampling for Linear Bandit Problems with Normal-Gamma Priors](https://mlsanity.com/paper/2303.03348/) (2023)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (2023)
- [Posterior Sampling-based Online Learning for Episodic POMDPs](https://mlsanity.com/paper/2310.10107/) (2023)
- [Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts](https://mlsanity.com/paper/2506.01685/) (2025)

## Abstract (arXiv)

We consider the stochastic multi-armed bandit problem with a prior distribution on the reward distributions. We are interested in studying prior-free and prior-dependent regret bounds, very much in the same spirit as the usual distribution-free and distribution-dependent bounds for the non-Bayesian stochastic bandit. Building on the techniques of Audibert and Bubeck [2009] and Russo and Roy [2013] we first show that Thompson Sampling attains an optimal prior-free bound in the sense that for any prior distribution its Bayesian regret is bounded from above by 14 √n K. This result is unimprovable in the sense that there exists a prior distribution such that any algorithm has a Bayesian regret bounded from below by frac120 √n K. We also study the case of priors for the setting of Bubeck et al. [2013] (where the optimal mean is known as well as a lower bound on the smallest gap) and we show that in this case the regret of Thompson Sampling is in fact uniformly bounded over time, thus showing that Thompson Sampling can greatly take advantage of the nice properties of these priors.