mlsanityData to 14 Oct 2026

Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning

arXiv 2306.08803 ↗First posted 15 Jun 2023cs.LG cs.AI stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Thompson sampling (TS) is widely used in sequential decision making due to its ease of use and appealing empirical performance. However, many existing analytical and empirical results for TS rely on restrictive assumptions on reward distributions, such as belonging to conjugate families, which limits their applicability in realistic scenarios. Moreover, sequential decision making problems are often carried out in a batched manner, either due to the inherent nature of the problem or to serve the purpose of reducing communication and computation costs. In this work, we jointly study these problems in two popular settings, namely, stochastic multi-armed bandits (MABs) and infinite-horizon reinforcement learning (RL), where TS is used to learn the unknown reward distributions and transition dynamics, respectively. We propose batched textitLangevin Thompson Sampling algorithms that leverage MCMC methods to sample from approximate posteriors with only logarithmic communication costs in terms of batches. Our algorithms are computationally efficient and maintain the same order-optimal regret guarantees of O(log T) for stochastic MABs, and O(√T) for RL. We complement our theoretical findings with experimental results.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 30 of its 56 references that are in the map. First posted on arXiv 15 Jun 2023.

Builds on

30 of 56 references.

References · 30

  1. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,240
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2013Learning to Optimize Via Posterior Samplingcited by 256
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  6. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 169
  7. 2015A Complete Recipe for Stochastic Gradient MCMCcited by 146
  8. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  9. 2019Batched Multi-armed Bandits Problemcited by 98
  10. 2017Convergence of Langevin MCMC in KL-divergencecited by 88
  11. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  12. 2020Safe Imitation Learning via Fast Bayesian Reward Inference from Preferencescited by 73
18 more
  1. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  2. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  3. 2017Ensemble Samplingcited by 62
  4. 2018Mirrored Langevin Dynamicscited by 61
  5. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  6. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  7. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  8. 2022Langevin Monte Carlo for Contextual Banditscited by 22
  9. 2020Steady State Analysis of Episodic Reinforcement Learningcited by 21
  10. 2021Parallelizing Thompson Samplingcited by 20
  11. 2021Batched Thompson Samplingcited by 19
  12. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  13. 2019Thompson Sampling in Non-Episodic Restless Banditscited by 16
  14. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15
  15. 2020Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescited by 13
  16. 2016Posterior Sampling for Reinforcement Learning Without Episodescited by 6
  17. 2017Posterior Sampling for Large Scale Reinforcement Learningcited by 3
  18. 2014Better Optimism By Bayes: Adaptive Planning with Rich Modelscited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 2.

5 papers.

  1. 2025Toward Efficient Exploration by Large Language Model Agentscited by 17
  2. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  3. 2024Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regretcited by 1
  4. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  5. 2024Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Banditscited by 0