# Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 88 references that are in the map.
- First posted on arXiv 30 Dec 2024.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Sample-efficient Cross-Entropy Method for Real-time Planning](https://mlsanity.com/paper/2008.06389/) (2020)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Bayesian linear regression with sparse priors](https://mlsanity.com/paper/1403.0735/) (2014)
- [On Online Learning in Kernelized Markov Decision Processes](https://mlsanity.com/paper/1911.01871/) (2019)
- [Variational Bayesian Reinforcement Learning with Regret Bounds](https://mlsanity.com/paper/1807.09647/) (2018)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Model-Based Bayesian Exploration](https://mlsanity.com/paper/1301.6690/) (2013)
- [Model-based Reinforcement Learning for Continuous Control with Posterior Sampling](https://mlsanity.com/paper/2012.09613/) (2020)
- [Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10728/) (2024)
- [Bayesian Bellman Operators](https://mlsanity.com/paper/2106.05012/) (2021)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)

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

- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)

## Abstract (arXiv)

Common assumptions, like linear or RKHS models, and Gaussian or log-concave posteriors over the models, do not explain practical success of RL across a wider range of distributions and models. Thus, we study how to design RL algorithms with sublinear regret for isoperimetric distributions, specifically the ones satisfying the Log-Sobolev Inequality (LSI). LSI distributions include the standard setups of RL theory, and others, such as many non-log-concave and perturbed distributions. First, we show that the Posterior Sampling-based RL (PSRL) algorithm yields sublinear regret if the data distributions satisfy LSI and some mild additional assumptions. Also, when we cannot compute or sample from an exact posterior, we propose a Langevin sampling-based algorithm design: LaPSRL. We show that LaPSRL achieves order-optimal regret and subquadratic complexity per episode. Finally, we deploy LaPSRL with a Langevin sampler -- SARAH-LD, and test it for different bandit and MDP environments. Experimental results validate the generality of LaPSRL across environments and its competitive performance with respect to the baselines.