Policy Mirror Descent With Temporal Difference Learning: Sample Complexity Under Online Markov Data

Abstract

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 \(\tilde\{O\}(\epsilon^\{-2\})\) (a logarithm factor about \(\epsilon\) is hidden in \(\tilde\{O\}(\cdot)\)) sample complexity can be established for them to achieve average-time \(\epsilo

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyli2025policy

Related papers

• Policy Mirror Descent Inherently Explores Action Space (2023)2.26
• Optimal Convergence Rate For Exact Policy Mirror Descent In Discounted Markov Decision Processes (2023)0.00
• Mirror Descent Policy Optimisation For Robust Constrained Markov Decision Processes (2025)0.00
• Learning Mirror Maps In Policy Mirror Descent (2024)0.00
• Policy Gradient For Robust Markov Decision Processes (2024)0.00
• Policy Optimization With Stochastic Mirror Descent (2019)7.50
• Policy Optimization For Constrained Mdps With Provable Fast Global Convergence (2021)0.00
• A Novel Framework For Policy Mirror Descent With General Parameterization And Linear Convergence (2023)2.26