aiqbench analysis
This research presents a theoretical advancement in policy optimization by establishing global linear convergence for Policy Mirror Descent when coupled with simple one-step temporal-difference updates. The analysis demonstrates that high sample efficiency can be achieved without relying on exact policy evaluation, trajectory resets, or generative models, offering a more practical framework for reinforcement learning algorithms.
Fast Regularized Policy Mirror Descent with One-Step TD Updates
arXiv:2609.39837v1 Announce Type: new 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 $\epsilon$ after $\widetilde{O}(1/((1-\gamma)^5 \widetilde{\sigma}_b \epsilon))$ 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{\sigma}_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.
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 $\epsilon$ after $\widetilde{O}(1/((1-\gamma)^5 \widetilde{\sigma}_b \epsilon))$ 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{\sigma}_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.
Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2609.39837 [cs.LG]
(or arXiv:2609.39837v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.39837 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 296 words
Related coverage
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
arXiv · Jun 12, 2026
On KL-Regularized Policy Optimization
arXiv · Oct 8, 2026
Advanced Policies: A First-Principles Path from Policy Gradient to Q-Learning
arXiv · Sep 30, 2026
Tariffs didn’t bring manufacturing jobs back to the US
The Verge · Jul 27, 2026