Gradient Temporal Difference with Momentum: Stability and Convergence
This work addresses the problem of enhancing convergence and stability in policy evaluation for reinforcement learning practitioners, though it is incremental as it builds upon existing gradient TD methods.
The paper tackles the stability and convergence of gradient temporal difference algorithms with heavy ball momentum in reinforcement learning, proving asymptotic convergence under specific parameter choices and demonstrating performance improvements over vanilla algorithms on standard RL problems.
Gradient temporal difference (Gradient TD) algorithms are a popular class of stochastic approximation (SA) algorithms used for policy evaluation in reinforcement learning. Here, we consider Gradient TD algorithms with an additional heavy ball momentum term and provide choice of step size and momentum parameter that ensures almost sure convergence of these algorithms asymptotically. In doing so, we decompose the heavy ball Gradient TD iterates into three separate iterates with different step sizes. We first analyze these iterates under one-timescale SA setting using results from current literature. However, the one-timescale case is restrictive and a more general analysis can be provided by looking at a three-timescale decomposition of the iterates. In the process, we provide the first conditions for stability and convergence of general three-timescale SA. We then prove that the heavy ball Gradient TD algorithm is convergent using our three-timescale SA analysis. Finally, we evaluate these algorithms on standard RL problems and report improvement in performance over the vanilla algorithms.