Fast Regularized Policy Mirror Descent with One-Step TD Updates
Abstract
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 Õ(1/((1−γ)5 σ̃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 σ̃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.
Related
- Does Policy Mirror Descent Converge in Policy with Non-Decomposable Mirror Maps? A Counterexample
- Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
- Mirror descent algorithms with logarithmic barriers
- Stochastic Mirror Descent under Dependent Observations
BibTeX
@misc{chen2026fast,
title = {{Fast Regularized Policy Mirror Descent with One-Step TD Updates}},
author = {Qipei Chen and Wenye Li and Yule Sun and Ke Wei},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39837},
eprint = {2609.39837},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39837},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fast Regularized Policy Mirror Descent with One-Step TD Updates
AU - Qipei Chen
AU - Wenye Li
AU - Yule Sun
AU - Ke Wei
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39837
UR - https://arxiv.org/abs/2609.39837
AB - 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 Õ(1/((1−γ)^5 σ̃_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 σ̃_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.
ER -