mlsanityData to 14 Oct 2026

On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation

arXiv 2509.18822 ↗First posted 23 Sep 2025math.OC cs.LGcited by 3

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Policy mirror descent (PMD) is a general policy optimization framework in reinforcement learning, which can cover a wide range of typical policy optimization methods by specifying different mirror maps. Existing analysis of PMD requires exact or approximate evaluation (for example unbiased estimation via Monte Carlo simulation) of action values solely based on policy. In this paper, we consider policy mirror descent with temporal difference evaluation (TD-PMD). It is shown that, given the access to exact policy evaluations, the dimension-free O(1/T) sublinear convergence still holds for TD-PMD with any constant step size and any initialization. In order to achieve this result, new monotonicity and shift invariance arguments have been developed. The dimension free γ-rate linear convergence of TD-PMD is also established provided the step size is selected adaptively. For the two common instances of TD-PMD (i.e., TD-PQA and TD-NPG), it is further shown that they enjoy the convergence in the policy domain. Additionally, we investigate TD-PMD in the inexact setting and give the sample complexity for it to achieve the last iterate varepsilon-optimality under a generative model, which improves the last iterate sample complexity for PMD over the dependence on 1/(1-γ).

Key facts. Cited by 3 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 38 of its 57 references that are in the map. First posted on arXiv 23 Sep 2025.

Builds on

38 of 57 references.

Closest ancestors · 6

Same direction, newest first

  1. 2024Structure Matters: Dynamic Policy Gradient7 Nov
  2. 2024Functional Acceleration for Policy Mirror Descent23 Jul
  3. 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation3 Jun
  4. 2024Elementary Analysis of Policy Gradient Methods4 Apr
  5. 2024Policy Mirror Descent with Lookahead21 Mar
  6. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction2 Jan

Other references · 32

  1. 2020Learning Quadrupedal Locomotion over Challenging Terraincited by 604
  2. 2022Learning robust perceptive locomotion for quadrupedal robots in the wildcited by 382
  3. 2019A Theory of Regularized Markov Decision Processescited by 286
  4. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  6. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  7. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  8. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  9. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  10. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  11. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  12. 2020Mirror Descent Policy Optimizationcited by 106
20 more
  1. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  2. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  3. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  4. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  5. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 52
  6. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 48
  7. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  8. 2021Safe Reinforcement Learning Using Advantage-Based Interventioncited by 47
  9. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  10. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  11. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  12. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  13. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  14. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  15. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  16. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  17. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  18. 2023On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluationcited by 9
  19. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 7
  20. 2023On the Convergence of Projected Policy Gradient for Any Constant Step Sizescited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  2. 2026PolicyAttention: Softmax Attention Implements Policy Mirror Descent for Closed-Loop Controlcited by 0
  3. 2026Fast Regularized Policy Mirror Descent with One-Step TD Updatescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025StaQ: a Finite Memory Approach to Discrete Action Policy Mirror Descent
  2. 2026Approximation of Log-Partition Function in Policy Mirror Descent Induces Implicit Regularization for LLM Post-Training
  3. 2026On the Policy Convergence of Policy Mirror Descent Methods
  4. 2025On the Effect of Regularization in Policy Mirror Descent
  5. 2024Learning mirror maps in policy mirror descent
  6. 2026Mirror descent actor-critic methods for entropy regularised MDPs in general spaces: stability and convergence
  7. 2024Operator World Models for Reinforcement Learning
  8. 2024Policy Gradient for Robust Markov Decision Processes