# Gradient Temporal Difference with Momentum: Stability and Convergence

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 22 Nov 2021.

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

- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Quasi-hyperbolic momentum and Adam for deep learning](https://mlsanity.com/paper/1810.06801/) (2018)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings](https://mlsanity.com/paper/2002.12414/) (2020)
- [Accelerated Gradient Temporal Difference Learning](https://mlsanity.com/paper/1611.09328/) (2016)
- [Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning](https://mlsanity.com/paper/1504.06043/) (2015)
- [Two Timescale Stochastic Approximation with Controlled Markov noise and Off-policy temporal difference learning](https://mlsanity.com/paper/1503.09105/) (2015)
- [Online Algorithms for Estimating Change Rates of Web Pages](https://mlsanity.com/paper/2009.08142/) (2020)

## Built on by (most cited first, 2 of 2)

- [Toward Efficient Gradient-Based Value Estimation](https://mlsanity.com/paper/2301.13757/) (2023)
- [Stability and Convergence of Distributed Stochastic Approximations with large Unbounded Stochastic Information Delays](https://mlsanity.com/paper/2305.07091/) (2023)

## Abstract (arXiv)

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.