# A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothness

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 101 references that are in the map.
- First posted on arXiv 29 Jul 2023.

## Builds on (most cited first, 30 of 40)

- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2001.11113/) (2020)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Consistent On-Line Off-Policy Evaluation](https://mlsanity.com/paper/1702.07121/) (2017)
- [Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shift](https://mlsanity.com/paper/1901.09455/) (2019)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Universal Off-Policy Evaluation](https://mlsanity.com/paper/2104.12820/) (2021)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Gradient Temporal-Difference Learning with Regularized Corrections](https://mlsanity.com/paper/2007.00611/) (2020)
- [A Kernel Loss for Solving the Bellman Equation](https://mlsanity.com/paper/1905.10506/) (2019)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [On Convergence of Emphatic Temporal-Difference Learning](https://mlsanity.com/paper/1506.02582/) (2015)
- [Deep Residual Reinforcement Learning](https://mlsanity.com/paper/1905.01072/) (2019)
- [Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms](https://mlsanity.com/paper/2011.05053/) (2020)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis](https://mlsanity.com/paper/1509.05172/) (2015)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Emphatic Temporal-Difference Learning](https://mlsanity.com/paper/1507.01569/) (2015)
- [Investigating practical linear temporal difference learning](https://mlsanity.com/paper/1602.08771/) (2016)

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

- [Revisiting a Design Choice in Gradient Temporal Difference Learning](https://mlsanity.com/paper/2308.01170/) (2023)
- [Baird Counterexample is Solved: with an example of How to Debug a Two-time-scale Algorithm](https://mlsanity.com/paper/2308.09732/) (2023)

## Abstract (arXiv)

Gradient Temporal Difference (GTD) algorithms (Sutton et al., 2008, 2009) are the first O(d) (d is the number features) algorithms that have convergence guarantees for off-policy learning with linear function approximation. Liu et al. (2015) and Dalal et. al. (2018) proved the convergence rates of GTD, GTD2 and TDC are O(t-α/2) for some α ∈ (0,1). This bound is tight (Dalal et al., 2020), and slower than O(1/√t). GTD algorithms also have two step-size parameters, which are difficult to tune. In literature, there is a "single-time-scale" formulation of GTD. However, this formulation still has two step-size parameters. This paper presents a truly single-time-scale GTD algorithm for minimizing the Norm of Expected td Update (NEU) objective, and it has only one step-size parameter. We prove that the new algorithm, called Impression GTD, converges at least as fast as O(1/t). Furthermore, based on a generalization of the expected smoothness (Gower et al. 2019), called L-λ smoothness, we are able to prove that the new GTD converges even faster, in fact, with a linear rate. Our rate actually also improves Gower et al.'s result with a tighter bound under a weaker assumption. Besides Impression GTD, we also prove the rates of three other GTD algorithms, one by Yao and Liu (2008), another called A-transpose-TD (Sutton et al., 2008), and a counterpart of A-transpose-TD. The convergence rates of all the four GTD algorithms are proved in a single generic GTD framework to which L-λ smoothness applies. Empirical results on Random walks, Boyan chain, and Baird counterexample show that Impression GTD converges much faster than existing GTD algorithms for both on-policy and off-policy learning problems, with well-performing step-sizes in a big range.