# Fast Regularized Policy Mirror Descent with One-Step TD Updates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 35 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 27 of 27)

- [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)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning](https://mlsanity.com/paper/1709.06293/) (2017)
- [A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization](https://mlsanity.com/paper/2110.08923/) (2021)
- [Regularized Policies are Reward Robust](https://mlsanity.com/paper/2101.07012/) (2021)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [Path Consistency Learning in Tsallis Entropy Regularized MDPs](https://mlsanity.com/paper/1802.03501/) (2018)
- [Tsallis Reinforcement Learning: A Unified Framework for Maximum Entropy Reinforcement Learning](https://mlsanity.com/paper/1902.00137/) (2019)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022)
- [Policy Mirror Descent Inherently Explores Action Space](https://mlsanity.com/paper/2303.04386/) (2023)
- [On the Convergence of Projected Policy Gradient for Any Constant Step Sizes](https://mlsanity.com/paper/2311.01104/) (2023)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [Strongly-polynomial time and validation analysis of policy gradient methods](https://mlsanity.com/paper/2409.19437/) (2024)
- [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)
- [On the Convergence of Policy in Unregularized Policy Mirror Descent](https://mlsanity.com/paper/2205.08176/) (2022)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)
- [On the Policy Convergence of Policy Mirror Descent Methods](https://mlsanity.com/paper/2607.11626/) (2026)

## Abstract (arXiv)

Policy mirror descent (PMD) enjoys fast convergence in regularized Markov decision processes (MDPs), but existing guarantees often rely on exact or increasingly accurate policy evaluation. We analyze PMD coupled with a persistent critic advanced by one temporal-difference (TD) update. For finite discounted MDPs, we establish global linear convergence in value for exact coordinate-wise Bellman updates, with any positive constant actor stepsize and arbitrary finite critic initialization. The proof combines a resolvent-based auxiliary distribution with a decaying Bellman-violation correction and a potential weighted by inverse coordinate weights. We then study stochastic TD-PMD with general strongly convex mirror maps under a single off-policy Markov trajectory. With suitably chosen constant stepsizes and a finite-batch TD update, the method achieves an expected value gap of ε after widetildeO(1/((1-γ)5 widetildeσb ε)) transitions. The stochastic analysis relies on the trajectory-wise Lipschitz continuity of the regularizer, derived from uniform bounds on vertex Bregman divergences, together with a visitation-weighted resolvent estimate for signed critic-error propagation that yields an inverse-linear dependence on behavior coverage widetildeσb. In contrast to many prior guarantees for regularized policy optimization, our sample-complexity guarantee holds without trajectory resets, generative-model access, or nested policy-evaluation loops. Numerical results are consistent with the theoretical convergence analysis.