# More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 39 of its 53 references that are in the map.
- First posted on arXiv 18 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [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)
- [Implicit Quantile Networks for Distributional Reinforcement Learning](https://mlsanity.com/paper/1806.06923/) (2018)
- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [(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)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [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)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [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)
- [Tianshou: a Highly Modularized Deep Reinforcement Learning Library](https://mlsanity.com/paper/2107.14171/) (2021)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [On Bonus-Based Exploration Methods in the Arcade Learning Environment](https://mlsanity.com/paper/2109.11052/) (2021)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)

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

- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning](https://mlsanity.com/paper/2501.17827/) (2025)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Provably Efficient and Agile Randomized Q-Learning](https://mlsanity.com/paper/2506.24005/) (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)
- [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)
- [Retry Policy Gradients in Continuous Action Spaces](https://mlsanity.com/paper/2606.05888/) (2026)
- [Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distribution](https://mlsanity.com/paper/2602.06239/) (2026)

## Abstract (arXiv)

Thompson sampling (TS) is one of the most popular exploration techniques in reinforcement learning (RL). However, most TS algorithms with theoretical guarantees are difficult to implement and not generalizable to Deep RL. While the emerging approximate sampling-based exploration schemes are promising, most existing algorithms are specific to linear Markov Decision Processes (MDP) with suboptimal regret bounds, or only use the most basic samplers such as Langevin Monte Carlo. In this work, we propose an algorithmic framework that incorporates different approximate sampling methods with the recently proposed Feel-Good Thompson Sampling (FGTS) approach (Zhang, 2022; Dann et al., 2021), which was previously known to be computationally intractable in general. When applied to linear MDPs, our regret analysis yields the best known dependency of regret on dimensionality, surpassing existing randomized algorithms. Additionally, we provide explicit sampling complexity for each employed sampler. Empirically, we show that in tasks where deep exploration is necessary, our proposed algorithms that combine FGTS and approximate sampling perform significantly better compared to other strong baselines. On several challenging games from the Atari 57 suite, our algorithms achieve performance that is either better than or on par with other strong baselines from the deep RL literature.