# A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2019.

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

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [When Data Geometry Meets Deep Function: Generalizing Offline Reinforcement Learning](https://mlsanity.com/paper/2205.11027/) (2022)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices](https://mlsanity.com/paper/2402.05876/) (2024)
- [Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximation](https://mlsanity.com/paper/2103.01391/) (2021)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Funnel-based Reward Shaping for Signal Temporal Logic Tasks in Reinforcement Learning](https://mlsanity.com/paper/2212.03181/) (2022)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [On the Performance of Temporal Difference Learning With Neural Networks](https://mlsanity.com/paper/2312.05397/) (2023)
- [Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization](https://mlsanity.com/paper/2411.07591/) (2024)
- [Data Sampling Affects the Complexity of Online SGD over Dependent Data](https://mlsanity.com/paper/2204.00006/) (2022)
- [SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learning](https://mlsanity.com/paper/2405.15920/) (2024)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Does DQN Learn?](https://mlsanity.com/paper/2205.13617/) (2022)
- [An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks](https://mlsanity.com/paper/2405.04017/) (2024)
- [Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods](https://mlsanity.com/paper/2202.06922/) (2022)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [Multi-Bellman operator for convergence of Q-learning with linear function approximation](https://mlsanity.com/paper/2309.16819/) (2023)
- [A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothness](https://mlsanity.com/paper/2307.15892/) (2023)

## Abstract (arXiv)

Q-learning with neural network function approximation (neural Q-learning for short) is among the most prevalent deep reinforcement learning algorithms. Despite its empirical success, the non-asymptotic convergence rate of neural Q-learning remains virtually unknown. In this paper, we present a finite-time analysis of a neural Q-learning algorithm, where the data are generated from a Markov decision process and the action-value function is approximated by a deep ReLU neural network. We prove that neural Q-learning finds the optimal policy with O(1/√T) convergence rate if the neural function approximator is sufficiently overparameterized, where T is the number of iterations. To our best knowledge, our result is the first finite-time analysis of neural Q-learning under non-i.i.d. data assumption.