Research map / Reinforcement learning / MDPs and planning
Policy Mirror Descent with Lookahead
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 h-PMD, a policy mirror descent variant using h-step lookahead greedy improvement, proving a gamma^h-linear rate in the exact setting and improved sample complexity and linear function approximation bounds in the inexact setting.
Problem
Standard policy mirror descent (PMD) uses 1-step greedy policy improvement, which may not be the best choice; the paper asks whether multi-step lookahead can speed up PMD convergence and sample complexity in discounted infinite-horizon MDPs.
Approach
Incorporate h-step lookahead greedy improvement into the PMD update (h-PMD), so the mirror step uses the h-step lookahead action values Q_h; this interpolates between PMD (h=1) and multi-step policy iteration as stepsize grows, and yields a gamma^h contraction rate that is dimension-free.
Key results
- Exact h-PMD achieves a gamma^h linear convergence rate, dimension-free and without distribution mismatch coefficients, improving on PMD's gamma rate.
- Under a generative model, the sample complexity improves from O~(1/(eps^2 (1-gamma)^8)) (prior PMD analysis) to O~(S/(h eps^2 (1-gamma)^6 (1-gamma^h)^2) + SA/(eps^2 (1-gamma)^7)).
- In DeepSea simulations, h-PMD converges in fewer iterations as lookahead depth h increases in both exact and inexact settings; the paper notes large h is not always better in runtime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add lookahead depth h to the PMD policy-improvement update | PMD · Discounted infinite-horizon MDPs, exact evaluation | value-suboptimality convergence rate: γ -> γ^h | Helped |
| Increase lookahead depth h (ablation) | h-PMD · DeepSea, exact setting | iterations to convergence | Helped |
| Increase lookahead depth h (ablation) | h-PMD · DeepSea, inexact setting | iterations to convergence | Helped |
| Increase lookahead depth h (ablation) | h-PMD · DeepSea, inexact setting | runtime to convergence | Helped |
| Use lookahead depth h=100 (ablation) | h-PMD · DeepSea, inexact setting | iterations to convergence: a single iteration | Helped |
| Increase lookahead depth beyond intermediate values (ablation) | h-PMD · Additional challenging practical environment | performance | Mixed |
| Use larger lookahead depth in inexact h-PMD | h-PMD · Discounted infinite-horizon MDPs, inexact evaluation | asymptotic suboptimality error: \frac{2b}{(1 - \gamma)(1 - \gamma^h)} ... smaller ... than \frac{4b}{(1 - \gamma)^2} | Helped |
| Use Monte Carlo lookahead estimation with h-PMD | h-PMD · Generative-model sample complexity | sample complexity: \tilde{\mathcal{O}}(\frac{1}{\epsilon^2(1 -\gamma)^7}) vs. \Tilde{\mathcal{O}}(\frac{1}{\epsilon^2 (1 - \gamma)^8}) | Helped |
| Use linear function approximation with h-PMD | h-PMD · Large-state-space MDPs | performance-bound dependence | Helped |
Surprising findings
- With very large lookahead depth (h=100) on DeepSea, the inexact algorithm converges in a single iteration.
- Larger lookahead depth is not always better in practice: intermediate h performed best in one more challenging setting.
Limitations
- Per-iteration computational cost grows exponentially in lookahead depth h (O((MA)^h)).
- Monte Carlo lookahead estimator exhaustively samples actions, without selective/bandit-guided sampling.
- Practical gains are environment-dependent; large h is not always better in runtime.
Experimental setup
Datasets: DeepSea (bsuite) continuous control tasks
Benchmarks: DeepSea (bsuite), 64x64 grid
Metrics: suboptimality gap ||V* - V^{pi_k}||_inf iterations to convergence runtime samples
Baselines: PMD (h=1) h-PI Xiao PMD analysis
Builds on: policy mirror descent policy iteration with lookahead (h-PI) natural policy gradient Johnson et al. dimension-free PMD analysis
Closest papers by meaning
- Learning mirror maps in policy mirror descent (ICLR 2025 · similarity 0.92)
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.91)
- Operator World Models for Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
- Convergence of Policy Mirror Descent Beyond Compatible Function Approximation (ICML 2025 · similarity 0.89)
- Mirror descent actor-critic methods for entropy regularised MDPs in general spaces: stability and convergence (NeurIPS 2026 · similarity 0.87)
- Flow Matching Policy Optimization with Mirror Descent and Entropy Constraints (NeurIPS 2026 · similarity 0.87)
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.