# Policy Mirror Descent with Lookahead

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

## Key facts

- Cited by 6 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 24 of its 49 references that are in the map.
- First posted on arXiv 21 Mar 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, 24 of 24)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [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)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Mirror Descent Policy Optimization](https://mlsanity.com/paper/2005.09814/) (2020)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [Beyond the One Step Greedy Approach in Reinforcement Learning](https://mlsanity.com/paper/1802.03654/) (2018)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [How to Combine Tree-Search Methods in Reinforcement Learning](https://mlsanity.com/paper/1809.01843/) (2018)
- [Policy Mirror Descent Inherently Explores Action Space](https://mlsanity.com/paper/2303.04386/) (2023)
- [Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction](https://mlsanity.com/paper/2107.01715/) (2021)
- [Efficient Exploration via Epistemic-Risk-Seeking Policy Optimization](https://mlsanity.com/paper/2302.09339/) (2023)
- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation](https://mlsanity.com/paper/2109.13419/) (2021)
- [SoftTreeMax: Policy Gradient with Tree Search](https://mlsanity.com/paper/2209.13966/) (2022)

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

- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding](https://mlsanity.com/paper/2602.00781/) (2026)
- [Gradient Extrapolation-Based Policy Optimization](https://mlsanity.com/paper/2605.06755/) (2026)
- [Fast Regularized Policy Mirror Descent with One-Step TD Updates](https://mlsanity.com/paper/2609.39837/) (2026)

## Abstract (arXiv)

Policy Mirror Descent (PMD) stands as a versatile algorithmic framework encompassing several seminal policy gradient algorithms such as natural policy gradient, with connections with state-of-the-art reinforcement learning (RL) algorithms such as TRPO and PPO. PMD can be seen as a soft Policy Iteration algorithm implementing regularized 1-step greedy policy improvement. However, 1-step greedy policies might not be the best choice and recent remarkable empirical successes in RL such as AlphaGo and AlphaZero have demonstrated that greedy approaches with respect to multiple steps outperform their 1-step counterpart. In this work, we propose a new class of PMD algorithms called h-PMD which incorporates multi-step greedy policy improvement with lookahead depth h to the PMD update rule. To solve discounted infinite horizon Markov Decision Processes with discount factor γ, we show that h-PMD which generalizes the standard PMD enjoys a faster dimension-free γh-linear convergence rate, contingent on the computation of multi-step greedy policies. We propose an inexact version of h-PMD where lookahead action values are estimated. Under a generative model, we establish a sample complexity for h-PMD which improves over prior work. Finally, we extend our result to linear function approximation to scale to large state spaces. Under suitable assumptions, our sample complexity only involves dependence on the dimension of the feature map space instead of the state space size.