mlsanityData to 13 Oct 2026

Finite-Sample Analysis of Proximal Gradient TD Algorithms

arXiv 2006.14364 ↗First posted 6 Jun 2020cs.LG stat.MLcited by 32

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 14; 2022: 5; 2023: 6; 2024: 3; 2025: 1; 2026: 3.

32 papers.

Sort:

By area:

  1. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  2. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  3. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 30
  4. 2021A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learningcited by 26
  5. 2023TD Convergence: An Optimization Perspectivecited by 15
  6. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  7. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
  8. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  9. 2021Faster Deep Reinforcement Learning with Slower Online Networkcited by 7
  10. 2023Revisiting a Design Choice in Gradient Temporal Difference Learningcited by 7
  11. 2021Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexitycited by 5
  12. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
20 more
  1. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  2. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  3. 2021On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correctioncited by 4
  4. 2023Toward Efficient Gradient-Based Value Estimationcited by 4
  5. 2021An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environmentcited by 3
  6. 2022Finite-Time Error Bounds for Greedy-GQcited by 3
  7. 2024An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networkscited by 3
  8. 2021An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Taskcited by 2
  9. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2
  10. 2023Backstepping Temporal Difference Learningcited by 2
  11. 2023A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothnesscited by 2
  12. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
  13. 2021A Unified Off-Policy Evaluation Approach for General Value Functioncited by 1
  14. 2021A Law of Iterated Logarithm for Multi-Agent Reinforcement Learningcited by 1
  15. 2022Gradient Descent Temporal Difference-difference Learningcited by 1
  16. 2021Variational Actor-Critic Algorithmscited by 0
  17. 2022STOPS: Short-Term-based Volatility-controlled Policy Search and its Global Convergencecited by 0
  18. 2024Towards Provable Log Density Policy Gradientcited by 0
  19. 2026Behavior-Induced Mirror-Prox Temporal-Difference Learning for Faster Off-Policy Predictioncited by 0
  20. 2026Behavior-Aware Auxiliary Corrections for Off-Policy Temporal-Difference Predictioncited by 0