Research map / Reinforcement learning / MDPs and planning
Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LMC-LSVI, a Thompson-sampling RL method that samples Q-function parameters via noisy gradient descent (Langevin Monte Carlo), proves an Õ(d^{3/2}H^{3/2}√T) linear-MDP regret bound, and extends it to a deep RL variant Adam LMCDQN evaluated on N-Chain and 8 Atari games.
Problem
Exploration in RL is hard to make both provably efficient and scalable to deep RL; existing Thompson sampling methods rely on Gaussian approximations of the Q-function posterior that are poor in practice.
Approach
Directly sample the Q-function from its approximate posterior by running Langevin Monte Carlo (noisy gradient descent) on the least-squares value-iteration loss, and replace the SGD step with Adam-preconditioned SGLD for deep RL.
Key results
- Theory: LMC-LSVI achieves Õ(d^{3/2}H^{3/2}√T) regret in linear MDPs, matching the best known randomized (TS-based) bound (LSVI-PHE) and LinTS bounds for H=1.
- On N-Chain with chain length up to N=100, Adam LMCDQN maintains high performance while Bootstrapped DQN and Noisy-Net drop quickly as N grows.
- On 8 Atari hard-exploration games, Adam LMCDQN is competitive with baselines and shows a strong advantage in Gravitar and Venture.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LMC-LSVI instead of OPT-RLSVI | Linear MDP exploration · Linear MDP | regret upper bound: \Tilde{\mathcal{O}}(d^2 H^2 \sqrt{T} ) -> \Tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T}) | Helped |
| Use LMC-LSVI instead of LSVI-UCB | Linear MDP exploration · Linear MDP | regret upper bound: \Tilde{\mathcal{O}}(d^{3/2} H^{3/2} \sqrt{T} ) -> \Tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T}) | No clear effect |
| Use LMC-LSVI instead of LSVI-PHE | Linear MDP exploration · Linear MDP | regret upper bound: \Tilde{\mathcal{O}}(d^{3/2} H^{3/2} \sqrt{T}) -> \Tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T}) | No clear effect |
| Use LMC-LSVI instead of ELEANOR | Linear MDP exploration · Linear MDP | regret upper bound: \Tilde{\mathcal{O}}(dH^{3/2}\sqrt{T}) -> \Tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T}) | Mixed |
| Use Adam LMCDQN instead of DQN, Bootstrapped DQN, or Noisy-Net | Deep RL exploration · N-Chain (N=25, 50, 75, 100) | mean return | Helped |
| Use Adam LMCDQN instead of the Atari baselines | Deep RL exploration · Gravitar | return | Helped |
| Use Adam LMCDQN instead of the Atari baselines | Deep RL exploration · Venture | return | Helped |
| Remove the double Q trick (ablation) | Adam LMCDQN · Atari games | performance | Hurt |
| Vary the bias factor a (ablation) | Adam LMCDQN · Qbert | performance | Mixed |
| Vary the inverse temperature beta_k (ablation) | Adam LMCDQN · Qbert | performance | No clear effect |
| Replace Adam LMCDQN with Langevin DQN | Deep RL exploration · Sparse-reward hard-exploration Atari games | performance | Hurt |
| Replace Adam LMCDQN with Langevin DQN | Deep RL exploration · Dense-reward hard-exploration Atari games | performance | No clear effect |
Surprising findings
- Practical deep variant uses J_k=1 update per step on Atari, far fewer than the theoretical J_k=2κ log(4HKd).
Limitations
- Theoretical analysis is limited to linear MDPs with fixed features; the deep variant has no regret guarantee.
- Regret bound holds only for failure probability above a constant (1/(2√(2eπ))) in the stated theorem.
- Performance is sensitive to the bias factor a, and the theoretical H dependence is suboptimal compared with lower bound.
Experimental setup
Datasets: N-Chain Atari 2600 (Alien, Freeway, Gravitar, H.E.R.O., Pitfall, Qbert, Solaris, Venture) RiverSwim simulated linear MDPs
Benchmarks: N-Chain Atari 8 hard exploration games RiverSwim
Metrics: mean return median return across seeds regret bound
Baselines: DQN Bootstrapped DQN Noisy-Net Double DQN Prioritized DQN C51 QR-DQN IQN Langevin DQN LSVI-UCB OPT-RLSVI LSVI-PHE
Builds on: LSVI-UCB randomized least-square value iteration Langevin DQN Adam SGLD Bootstrapped DQN
Closest papers by meaning
- Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning (ICLR 2025 · similarity 0.90)
- Fast Value Tracking for Deep Reinforcement Learning (ICLR 2024 · similarity 0.89)
- No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes (NeurIPS 2025 · similarity 0.88)
- Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts (NeurIPS 2026 · similarity 0.88)
- Parameter Exploration for RLVR via Variational Learning (NeurIPS 2026 · similarity 0.88)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.