mlsanityData to 7 Oct 2026

Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo

arXiv 2401.11665 ↗First posted 22 Jan 2024stat.ML cs.AI cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Approximate Thompson sampling with Langevin Monte Carlo broadens its reach from Gaussian posterior sampling to encompass more general smooth posteriors. However, it still encounters scalability issues in high-dimensional problems when demanding high accuracy. To address this, we propose an approximate Thompson sampling strategy, utilizing underdamped Langevin Monte Carlo, where the latter is the go-to workhorse for simulations of high-dimensional posteriors. Based on the standard smoothness and log-concavity conditions, we study the accelerated posterior concentration and sampling using a specific potential function. This design improves the sample complexity for realizing logarithmic regrets from tilde O(d) to tilde O(√d). The scalability and robustness of our algorithm are also empirically validated through synthetic experiments in high-dimensional bandit problems.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 31 of its 65 references that are in the map. First posted on arXiv 22 Jan 2024.

Builds on

31 of 65 references.

References · 31

  1. 2017A Tutorial on Thompson Samplingcited by 420
  2. 2014Stochastic Gradient Hamiltonian Monte Carlocited by 341
  3. 2013Learning to Optimize Via Posterior Samplingcited by 253
  4. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  5. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  6. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  7. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  8. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  9. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  10. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  11. 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 96
  12. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
19 more
  1. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  2. 2014Consistency and fluctuations for stochastic gradient Langevin dynamicscited by 65
  3. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  4. 2020Non-convex Learning via Replica Exchange Stochastic Gradient MCMCcited by 33
  5. 2020Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Banditscited by 30
  6. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  7. 2019Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributionscited by 28
  8. 2020MOTS: Minimax Optimal Thompson Samplingcited by 28
  9. 2020Optimal Thompson Sampling strategies for support-aware CVaR banditscited by 26
  10. 2022Langevin Monte Carlo for Contextual Banditscited by 22
  11. 2022Thompson Sampling for High-Dimensional Sparse Linear Contextual Banditscited by 16
  12. 2019Thompson Sampling with Approximate Inferencecited by 15
  13. 2020Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusioncited by 15
  14. 2015On the Prior Sensitivity of Thompson Samplingcited by 14
  15. 2017Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributionscited by 12
  16. 2022Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditscited by 11
  17. 2022Interacting Contour Stochastic Gradient Langevin Dynamicscited by 9
  18. 2022Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Controlcited by 8
  19. 2018Stochastic Variance-Reduced Hamilton Monte Carlo Methodscited by 7

Built on by

Cited by year

Citing papers per year: 2024: 5; 2025: 5.

10 papers.

  1. 2024Conformalized-DeepONet: A Distribution-Free Framework for Uncertainty Quantification in Deep Operator Networkscited by 28
  2. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  3. 2024Epsilon-Greedy Thompson Sampling to Bayesian Optimizationcited by 8
  4. 2024Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamicscited by 7
  5. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdowncited by 4
  6. 2025Active Learning with Bayesian Multi-Fidelity Laplace Neural Operators for Oscillatory Parametric PDEscited by 2
  7. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  8. 2024Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regretcited by 1
  9. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  10. 2025Analysis of kinetic Langevin Monte Carlo under the stochastic exponential Euler discretization from underdamped all the way to overdampedcited by 0