# Finite-Sample Analysis of Proximal Gradient TD Algorithms

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2020.

## Built on by (most cited first, 30 of 32)

- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning](https://mlsanity.com/paper/2104.13844/) (2021)
- [TD Convergence: An Optimization Perspective](https://mlsanity.com/paper/2306.17750/) (2023)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [Faster Deep Reinforcement Learning with Slower Online Network](https://mlsanity.com/paper/2112.05848/) (2021)
- [Revisiting a Design Choice in Gradient Temporal Difference Learning](https://mlsanity.com/paper/2308.01170/) (2023)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction](https://mlsanity.com/paper/2106.00993/) (2021)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Toward Efficient Gradient-Based Value Estimation](https://mlsanity.com/paper/2301.13757/) (2023)
- [An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks](https://mlsanity.com/paper/2405.04017/) (2024)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment](https://mlsanity.com/paper/2109.05110/) (2021)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task](https://mlsanity.com/paper/2106.00922/) (2021)
- [Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02850/) (2022)
- [Backstepping Temporal Difference Learning](https://mlsanity.com/paper/2302.09875/) (2023)
- [A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothness](https://mlsanity.com/paper/2307.15892/) (2023)
- [Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2602.16629/) (2026)
- [A Unified Off-Policy Evaluation Approach for General Value Function](https://mlsanity.com/paper/2107.02711/) (2021)
- [A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.15092/) (2021)
- [Gradient Descent Temporal Difference-difference Learning](https://mlsanity.com/paper/2209.04624/) (2022)
- [Variational Actor-Critic Algorithms](https://mlsanity.com/paper/2108.01215/) (2021)
- [STOPS: Short-Term-based Volatility-controlled Policy Search and its Global Convergence](https://mlsanity.com/paper/2201.09857/) (2022)
- [Towards Provable Log Density Policy Gradient](https://mlsanity.com/paper/2403.01605/) (2024)

## Abstract (arXiv)

In this paper, we analyze the convergence rate of the gradient temporal difference learning (GTD) family of algorithms. Previous analyses of this class of algorithms use ODE techniques to prove asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done. Moreover, there has been not much work on finite-sample analysis for convergent off-policy reinforcement learning algorithms. In this paper, we formulate GTD methods as stochastic gradient algorithms w.r.t.~a primal-dual saddle-point objective function, and then conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Two revised algorithms are also proposed, namely projected GTD2 and GTD2-MP, which offer improved convergence guarantees and acceleration, respectively. The results of our theoretical analysis show that the GTD family of algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios.