# Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes arXiv: https://arxiv.org/abs/2302.11381 · HTML: https://mlsanity.com/paper/2302.11381/ ## Key facts - Cited by 18 papers in the map (data through 14 Oct 2026). - Builds on 21 of its 42 references that are in the map. - First posted on arXiv 22 Feb 2023. ## Builds on (most cited first, 21 of 21) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019) - [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020) - [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) - [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019) - [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022) - [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019) - [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020) - [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021) - [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021) - [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019) - [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022) - [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020) - [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021) - [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022) - [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014) - [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) - [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022) - [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022) ## Built on by (most cited first, 18 of 18) - [One-Step Flow Policy Mirror Descent](https://mlsanity.com/paper/2507.23675/) (2025) - [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024) - [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024) - [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024) - [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023) - [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) - [On the Linear Convergence of Policy Gradient under Hadamard Parameterization](https://mlsanity.com/paper/2305.19575/) (2023) - [Dual Approximation Policy Optimization](https://mlsanity.com/paper/2410.01249/) (2024) - [Fast Convergence of Softmax Policy Mirror Ascent](https://mlsanity.com/paper/2411.12042/) (2024) - [Convergence of Policy Mirror Descent Beyond Compatible Function Approximation](https://mlsanity.com/paper/2502.11033/) (2025) - [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025) - [Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes](https://mlsanity.com/paper/2406.04163/) (2024) - [Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning](https://mlsanity.com/paper/2507.04406/) (2025) - [Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes](https://mlsanity.com/paper/2607.22982/) (2026) - [PolicyAttention: Softmax Attention Implements Policy Mirror Descent for Closed-Loop Control](https://mlsanity.com/paper/2609.30500/) (2026) - [Fast Regularized Policy Mirror Descent with One-Step TD Updates](https://mlsanity.com/paper/2609.39837/) (2026) - [Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs](https://mlsanity.com/paper/2610.04117/) (2026) ## Abstract (arXiv) Policy Mirror Descent (PMD) is a general family of algorithms that covers a wide range of novel and fundamental methods in reinforcement learning. Motivated by the instability of policy iteration (PI) with inexact policy evaluation, PMD algorithmically regularises the policy improvement step of PI. With exact policy evaluation, PI is known to converge linearly with a rate given by the discount factor γ of a Markov Decision Process. In this work, we bridge the gap between PI and PMD with exact policy evaluation and show that the dimension-free γ-rate of PI can be achieved by the general family of unregularised PMD algorithms under an adaptive step-size. We show that both the rate and step-size are unimprovable for PMD: we provide matching lower bounds that demonstrate that the γ-rate is optimal for PMD methods as well as PI, and that the adaptive step-size is necessary for PMD to achieve it. Our work is the first to relate PMD to rate-optimality and step-size necessity. Our study of the convergence of PMD avoids the use of the performance difference lemma, which leads to a direct analysis of independent interest. We also extend the analysis to the inexact setting and establish the first dimension-optimal sample complexity for unregularised PMD under a generative model, improving upon the best-known result.