# Thompson Sampling for 1-Dimensional Exponential Family Bandits

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2013.

## Built on by (most cited first, 30 of 42)

- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [No-Regret Reinforcement Learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2102.12769/) (2021)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)
- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [The Typical Behavior of Bandit Algorithms](https://mlsanity.com/paper/2210.05660/) (2022)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [When and why randomised exploration works (in linear bandits)](https://mlsanity.com/paper/2502.08870/) (2025)
- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)
- [Spectral Thompson sampling](https://mlsanity.com/paper/2604.13739/) (2026)
- [Extreme Bandits using Robust Statistics](https://mlsanity.com/paper/2109.04433/) (2021)
- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Thompson Exploration with Best Challenger Rule in Best Arm Identification](https://mlsanity.com/paper/2310.00539/) (2023)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits](https://mlsanity.com/paper/2110.00158/) (2021)
- [Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits](https://mlsanity.com/paper/2302.01544/) (2023)
- [Monte-Carlo tree search with uncertainty propagation via optimal transport](https://mlsanity.com/paper/2309.10737/) (2023)
- [Multi-armed bandits for resource efficient, online optimization of language model pre-training: the use case of dynamic masking](https://mlsanity.com/paper/2203.13151/) (2022)
- [Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms](https://mlsanity.com/paper/2304.03056/) (2023)
- [Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards](https://mlsanity.com/paper/2304.14989/) (2023)
- [Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics](https://mlsanity.com/paper/2501.19239/) (2025)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention](https://mlsanity.com/paper/2402.15127/) (2024)

## Abstract (arXiv)

Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (and thus Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families.