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

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

## 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 (most cited first, 30 of 32)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Deep Reinforcement Learning for Dialogue Generation](https://mlsanity.com/paper/1606.01541/) (2016)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Maxout Networks](https://mlsanity.com/paper/1302.4389/) (2013)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Applications of Deep Reinforcement Learning in Communications and Networking: A Survey](https://mlsanity.com/paper/1810.07862/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Virtual-to-real Deep Reinforcement Learning: Continuous Control of Mobile Robots for Mapless Navigation](https://mlsanity.com/paper/1703.00420/) (2017)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Experience-driven Networking: A Deep Reinforcement Learning based Approach](https://mlsanity.com/paper/1801.05757/) (2018)
- [Manipulation by Feel: Touch-Based Control with Deep Predictive Models](https://mlsanity.com/paper/1903.04128/) (2019)
- [Neural tangent kernels, transportation mappings, and universal approximation](https://mlsanity.com/paper/1910.06956/) (2019)

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

- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysis](https://mlsanity.com/paper/2402.12241/) (2024)
- [Recurrent Natural Policy Gradient for POMDPs](https://mlsanity.com/paper/2405.18221/) (2024)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [On the Performance of Temporal Difference Learning With Neural Networks](https://mlsanity.com/paper/2312.05397/) (2023)
- [An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks](https://mlsanity.com/paper/2405.04017/) (2024)
- [A Riemannian Optimization Perspective of the Gauss-Newton Method for Feedforward Neural Networks](https://mlsanity.com/paper/2412.14031/) (2024)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)
- [On the Convergence of Semi-Gradient TD: A Mean Field Perspective](https://mlsanity.com/paper/2610.20014/) (2026)

## 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.