# Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo

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

## Key facts

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

## Builds on (most cited first, 30 of 31)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Consistency and fluctuations for stochastic gradient Langevin dynamics](https://mlsanity.com/paper/1409.0578/) (2014)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Non-convex Learning via Replica Exchange Stochastic Gradient MCMC](https://mlsanity.com/paper/2008.05367/) (2020)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [Optimal Thompson Sampling strategies for support-aware CVaR bandits](https://mlsanity.com/paper/2012.05754/) (2020)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion](https://mlsanity.com/paper/2007.01990/) (2020)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [On the Prior Sensitivity of Thompson Sampling](https://mlsanity.com/paper/1506.03378/) (2015)
- [Thompson Sampling with Approximate Inference](https://mlsanity.com/paper/1908.04970/) (2019)
- [Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions](https://mlsanity.com/paper/1708.07114/) (2017)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Interacting Contour Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2202.09867/) (2022)
- [Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Control](https://mlsanity.com/paper/2206.08520/) (2022)

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

- [Conformalized-DeepONet: A Distribution-Free Framework for Uncertainty Quantification in Deep Operator Networks](https://mlsanity.com/paper/2402.15406/) (2024)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Epsilon-Greedy Thompson Sampling to Bayesian Optimization](https://mlsanity.com/paper/2403.00540/) (2024)
- [Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2405.07839/) (2024)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Active Learning with Bayesian Multi-Fidelity Laplace Neural Operators for Oscillatory Parametric PDEs](https://mlsanity.com/paper/2502.00550/) (2025)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret](https://mlsanity.com/paper/2412.20824/) (2024)
- [Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective](https://mlsanity.com/paper/2510.05023/) (2025)
- [Analysis of kinetic Langevin Monte Carlo under the stochastic exponential Euler discretization from underdamped all the way to overdamped](https://mlsanity.com/paper/2510.03949/) (2025)

## 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.