# Adaptive Temporal Difference Learning with Linear Function Approximation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

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

- [Spectral Normalisation for Deep Reinforcement Learning: an Optimisation Perspective](https://mlsanity.com/paper/2105.05246/) (2021)
- [Correcting Momentum in Temporal Difference Learning](https://mlsanity.com/paper/2106.03955/) (2021)
- [Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimization](https://mlsanity.com/paper/2201.10447/) (2022)
- [Review of Metrics to Measure the Stability, Robustness and Resilience of Reinforcement Learning](https://mlsanity.com/paper/2203.12048/) (2022)
- [n-Step Temporal Difference Learning with Optimal n](https://mlsanity.com/paper/2303.07068/) (2023)
- [A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2506.01052/) (2025)
- [A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging](https://mlsanity.com/paper/2606.24981/) (2026)
- [Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation](https://mlsanity.com/paper/2202.13863/) (2022)
- [Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximation](https://mlsanity.com/paper/2408.06945/) (2024)

## Abstract (arXiv)

This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. Typically, the performance of TD(0) and TD(λ) is very sensitive to the choice of stepsizes. Oftentimes, TD(0) suffers from slow convergence. Motivated by the tight link between the TD(0) learning algorithm and the stochastic gradient methods, we develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation that we term AdaTD(0). In contrast to the TD(0), AdaTD(0) is robust or less sensitive to the choice of stepsizes. Analytically, we establish that to reach an ε accuracy, the number of iterations needed is tildeO(ε-2ln4frac1ε/ln4frac1ρ) in the general case, where ρ represents the speed of the underlying Markov chain converges to the stationary distribution. This implies that the iteration complexity of AdaTD(0) is no worse than that of TD(0) in the worst case. When the stochastic semi-gradients are sparse, we provide theoretical acceleration of AdaTD(0). Going beyond TD(0), we develop an adaptive variant of TD(λ), which is referred to as AdaTD(λ). Empirically, we evaluate the performance of AdaTD(0) and AdaTD(λ) on several standard reinforcement learning tasks, which demonstrate the effectiveness of our new approaches.