mlsanityData to 14 Oct 2026

Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximation

arXiv 2103.01391 ↗First posted 2 Mar 2021cs.LG cs.AI math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the dynamics of temporal difference learning with neural network-based value function approximation over a general state space, namely, Neural TD learning. We consider two practically used algorithms, projection-free and max-norm regularized Neural TD learning, and establish the first convergence bounds for these algorithms. An interesting observation from our results is that max-norm regularization can dramatically improve the performance of TD learning algorithms, both in terms of sample complexity and overparameterization. In particular, we prove that max-norm regularization improves state-of-the-art sample complexity and overparameterization bounds. The results in this work rely on a novel Lyapunov drift analysis of the network parameters as a stopped and controlled random process.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 32 of its 55 references that are in the map. First posted on arXiv 2 Mar 2021.

Builds on

32 of 55 references.

References · 32

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  4. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 743
  5. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  6. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  7. 2018On Lazy Training in Differentiable Programmingcited by 675
  8. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  9. 2014Convex Optimization: Algorithms and Complexitycited by 575
  10. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  11. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  12. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
20 more
  1. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  2. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  3. 2016Deep Reinforcement Learning for Dialogue Generationcited by 288
  4. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  6. 2013Maxout Networkscited by 187
  7. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  8. 2018Applications of Deep Reinforcement Learning in Communications and Networking: A Surveycited by 167
  9. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  10. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  11. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  12. 2017Virtual-to-real Deep Reinforcement Learning: Continuous Control of Mobile Robots for Mapless Navigationcited by 98
  13. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 88
  14. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  15. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  16. 2018Experience-driven Networking: A Deep Reinforcement Learning based Approachcited by 41
  17. 2019Manipulation by Feel: Touch-Based Control with Deep Predictive Modelscited by 36
  18. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  19. 2019Geometric Insights into the Convergence of Nonlinear TD Learningcited by 13
  20. 2019Asymptotics of Reinforcement Learning with Neural Networkscited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 1; 2024: 6; 2025: 0; 2026: 1.

10 papers.

  1. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 28
  2. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  3. 2024Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysiscited by 8
  4. 2024Recurrent Natural Policy Gradient for POMDPscited by 8
  5. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 7
  6. 2023On the Performance of Temporal Difference Learning With Neural Networkscited by 6
  7. 2024An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networkscited by 4
  8. 2024A Riemannian Optimization Perspective of the Gauss-Newton Method for Feedforward Neural Networkscited by 3
  9. 2024Regularized Q-Learning with Linear Function Approximationcited by 2
  10. 2026On the Convergence of Semi-Gradient TD: A Mean Field Perspectivecited by 0