mlsanityData to 7 Oct 2026

An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks

arXiv 2405.04017 ↗First posted 7 May 2024cs.LG cs.AI math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

Temporal difference (TD) learning algorithms with neural network function parameterization have well-established empirical success in many practical large-scale reinforcement learning tasks. However, theoretical understanding of these algorithms remains challenging due to the nonlinearity of the action-value approximation. In this paper, we develop an improved non-asymptotic analysis of the neural TD method with a general L-layer neural network. New proof techniques are developed and an improved new tildeO(ε-1) sample complexity is derived. To our best knowledge, this is the first finite-time analysis of neural TD that achieves an tildeO(ε-1) complexity under the Markovian sampling, as opposed to the best known tildeO(ε-2) complexity in the existing literature.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 28 of its 52 references that are in the map. First posted on arXiv 7 May 2024.

Builds on

28 of 52 references.

References · 28

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,302
  5. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  6. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  7. 2016OpenAI Gymcited by 1,684
  8. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  9. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  10. 2019Behavior Regularized Offline Reinforcement Learningcited by 654
  11. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  12. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
16 more
  1. 2021Offline Reinforcement Learning with Fisher Divergence Critic Regularizationcited by 237
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  4. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  5. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  6. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  7. 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
  8. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  9. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
  10. 2019Neural Temporal-Difference and Q-Learning Provably Converge to Global Optimacited by 20
  11. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 13
  12. 2019Geometric Insights into the Convergence of Nonlinear TD Learningcited by 12
  13. 2017Convergent Tree Backup and Retrace with Function Approximationcited by 11
  14. 2021Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximationcited by 9
  15. 2014Rate of Convergence and Error Bounds for LSTD(λ)cited by 8
  16. 2023On the Performance of Temporal Difference Learning With Neural Networkscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  2. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  3. 2026Beyond the Independence Assumption: Finite-Sample Guarantees for Deep Q-Learning under τ-Mixingcited by 0