mlsanityData to 7 Oct 2026

Thompson Sampling for 1-Dimensional Exponential Family Bandits

arXiv 1307.3400 ↗First posted 12 Jul 2013stat.MLcited by 41

Not on the map. Why?

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.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Jul 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 7; 2023: 12; 2024: 4; 2025: 8; 2026: 1.

41 papers.

Sort:

By area:

  1. 2021Batched Thompson Samplingcited by 19
  2. 2021The Fragility of Optimized Bandit Algorithmscited by 15
  3. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
  4. 2021Maillard Sampling: Boltzmann Exploration Done Optimallycited by 13
  5. 2022Bregman Deviations of Generic Exponential Familiescited by 13
  6. 2021Diffusion Approximations for Thompson Sampling in the Small Gap Regimecited by 12
  7. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  8. 2022Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditscited by 11
  9. 2022The Typical Behavior of Bandit Algorithmscited by 10
  10. 2025When and why randomised exploration works (in linear bandits)cited by 8
  11. 2023Optimal Best-Arm Identification in Bandits with Access to Offline Datacited by 6
  12. 2025Stable Thompson Sampling: Valid Inference via Variance Inflationcited by 6
29 more
  1. 2022Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimizationcited by 5
  2. 2024Diffusion Models Meet Contextual Banditscited by 5
  3. 2024Best Arm Identification with Minimal Regretcited by 5
  4. 2026Spectral Thompson samplingcited by 5
  5. 2021Extreme Bandits using Robust Statisticscited by 4
  6. 2021From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Banditscited by 4
  7. 2023A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithmscited by 4
  8. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
  9. 2021Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Banditscited by 3
  10. 2023Optimality of Thompson Sampling with Noninformative Priors for Pareto Banditscited by 3
  11. 2023Monte-Carlo tree search with uncertainty propagation via optimal transportcited by 3
  12. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 3
  13. 2022Multi-armed bandits for resource efficient, online optimization of language model pre-training: the use case of dynamic maskingcited by 2
  14. 2023Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithmscited by 2
  15. 2023Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewardscited by 2
  16. 2025Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamicscited by 2
  17. 2023Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphscited by 1
  18. 2024Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstentioncited by 1
  19. 2024On Lai's Upper Confidence Bound in Multi-Armed Banditscited by 1
  20. 2025Communication Bounds for the Distributed Experts Problemcited by 1
  21. 2025Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Samplingcited by 1
  22. 2025Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Samplingcited by 1
  23. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  24. 2021Asymptotically Optimal Bandits under Weighted Informationcited by 0
  25. 2022Thompson Sampling on Asymmetric α-Stable Banditscited by 0
  26. 2023The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Modelscited by 0
  27. 2023Generalized Regret Analysis of Thompson Sampling using Fractional Posteriorscited by 0
  28. 2023From Bandits Model to Deep Deterministic Policy Gradient, Reinforcement Learning with Contextual Informationcited by 0
  29. 2023Approximate information maximization for bandit gamescited by 0