mlsanityData to 14 Oct 2026

Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data

arXiv 2512.24056 ↗First posted 30 Dec 2025math.OC cs.LGcited by 2

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

Abstract (arXiv)

This paper studies the policy mirror descent (PMD) method, which is a general policy optimization framework in reinforcement learning and can cover a wide range of policy gradient methods by specifying difference mirror maps. Existing sample complexity analysis for policy mirror descent either focuses on the generative sampling model, or the Markovian sampling model but with the action values being explicitly approximated to certain pre-specified accuracy. In contrast, we consider the sample complexity of policy mirror descent with temporal difference (TD) learning under the Markovian sampling model. Two algorithms called Expected TD-PMD and Approximate TD-PMD have been presented, which are off-policy and mixed policy algorithms respectively. Under a small enough constant policy update step size, the tildeO(varepsilon-2) (a logarithm factor about varepsilon is hidden in tildeO(·)) sample complexity can be established for them to achieve average-time varepsilon-optimality. The sample complexity is further improved to O(varepsilon-2) (without the hidden logarithm factor) to achieve the last-iterate varepsilon-optimality based on adaptive policy update step sizes.

Key facts. Cited by 2 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 48 of its 67 references that are in the map. First posted on arXiv 30 Dec 2025.

Builds on

48 of 67 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation23 Sep
  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 · 42

  1. 2020Learning Quadrupedal Locomotion over Challenging Terraincited by 604
  2. 2019Learning agile and dynamic motor skills for legged robotscited by 504
  3. 2022Learning robust perceptive locomotion for quadrupedal robots in the wildcited by 382
  4. 2019A Theory of Regularized Markov Decision Processescited by 286
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  6. 2025A Survey of Reinforcement Learning for Large Reasoning Modelscited by 180
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  8. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  9. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  10. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  11. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  12. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
30 more
  1. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  2. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  3. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  4. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  5. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  6. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  7. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 52
  8. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 48
  9. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  10. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  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. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  14. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  15. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  16. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  17. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  18. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 24
  19. 2025Reinforcing Action Policies by Prophesyingcited by 22
  20. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 21
  21. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  22. 2019Policy Optimization with Stochastic Mirror Descentcited by 18
  23. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  24. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  25. 2021Bregman Gradient Policy Optimizationcited by 17
  26. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  27. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 14
  28. 2023Policy Mirror Descent Inherently Explores Action Spacecited by 13
  29. 2023On the Convergence of Projected Policy Gradient for Any Constant Step Sizescited by 6
  30. 2023On the Linear Convergence of Policy Gradient under Hadamard Parameterizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Value Mirror Descent for Reinforcement Learningcited by 1
  2. 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. 2024Learning mirror maps in policy mirror descent
  3. 2026Approximation of Log-Partition Function in Policy Mirror Descent Induces Implicit Regularization for LLM Post-Training
  4. 2024Policy Gradient for Robust Markov Decision Processes
  5. 2025On the Effect of Regularization in Policy Mirror Descent
  6. 2025Mirror Descent Policy Optimisation for Robust Constrained Markov Decision Processes
  7. 2026Mirror descent actor-critic methods for entropy regularised MDPs in general spaces: stability and convergence
  8. 2026On the Policy Convergence of Policy Mirror Descent Methods