# Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 61 of its 105 references that are in the map.
- First posted on arXiv 29 May 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Implicit Quantile Networks for Distributional Reinforcement Learning](https://mlsanity.com/paper/1806.06923/) (2018)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [Count-Based Exploration with Neural Density Models](https://mlsanity.com/paper/1703.01310/) (2017)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Parameter Space Noise for Exploration](https://mlsanity.com/paper/1706.01905/) (2017)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Tianshou: a Highly Modularized Deep Reinforcement Learning Library](https://mlsanity.com/paper/2107.14171/) (2021)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)

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

- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation](https://mlsanity.com/paper/2402.15399/) (2024)
- [Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning](https://mlsanity.com/paper/2501.17827/) (2025)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent](https://mlsanity.com/paper/2402.10228/) (2024)
- [Random Latent Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.13755/) (2024)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Emergence of Exploration in Policy Gradient Reinforcement Learning via Retrying](https://mlsanity.com/paper/2606.00151/) (2026)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Prior-dependent analysis of posterior sampling reinforcement learning with function approximation](https://mlsanity.com/paper/2403.11175/) (2024)
- [Sequential Decision Making with Expert Demonstrations under Unobserved Heterogeneity](https://mlsanity.com/paper/2404.07266/) (2024)
- [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)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret](https://mlsanity.com/paper/2412.20824/) (2024)
- [CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.18980/) (2025)
- [Universal Value-Function Uncertainties](https://mlsanity.com/paper/2505.21119/) (2025)
- [Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective](https://mlsanity.com/paper/2510.05023/) (2025)
- [Direct Soft-Policy Sampling via Langevin Dynamics](https://mlsanity.com/paper/2602.07873/) (2026)
- [Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration](https://mlsanity.com/paper/2501.13394/) (2025)
- [Thompson Sampling in Online RLHF with General Function Approximation](https://mlsanity.com/paper/2505.23927/) (2025)
- [Priors Matter: Addressing Misspecification in Bayesian Deep Q-Learning](https://mlsanity.com/paper/2508.21488/) (2025)
- [Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distribution](https://mlsanity.com/paper/2602.06239/) (2026)
- [Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes](https://mlsanity.com/paper/2603.28595/) (2026)
- [Bayesian learning for the stochastic shortest path problem](https://mlsanity.com/paper/2606.04845/) (2026)

## Abstract (arXiv)

We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL). One of the key shortcomings of existing Thompson sampling algorithms is the need to perform a Gaussian approximation of the posterior distribution, which is not a good surrogate in most practical settings. We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo, an efficient type of Markov Chain Monte Carlo (MCMC) method. Our method only needs to perform noisy gradient descent updates to learn the exact posterior distribution of the Q function, which makes our approach easy to deploy in deep RL. We provide a rigorous theoretical analysis for the proposed method and demonstrate that, in the linear Markov decision process (linear MDP) setting, it has a regret bound of tildeO(d3/2H3/2√T), where d is the dimension of the feature mapping, H is the planning horizon, and T is the total number of steps. We apply this approach to deep RL, by using Adam optimizer to perform gradient updates. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.