Fast convergence method improves learning in regularized reinforcement learning
Fast Regularized Policy Mirror Descent with One-Step TD Updates
Machine Learning
Summary
Learning the best actions in uncertain environments is tricky because accurately assessing the value of each action usually takes a lot of effort. The authors studied a way to speed up this learning process by combining policy updates with quick value estimates using just one update step. They proved mathematically that their approach reliably finds good policies faster than before, even when starting from random guesses and using limited data. This method works without needing complicated resets or extra models, making learning more efficient.
What this means in practice
- •For reinforcement learning engineers: Speed up policy learning in simulated environments with limited resets using fewer data transitions.
- •For robotics developers: Improve sample-efficient learning of robot control policies where retraining with environment resets is costly.
Authors
Qipei Chen, Wenye Li, Yule Sun, Ke Wei
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 $\widetilde{O}(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.