Data to 14 Oct 2026

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

arXiv 1912.04511 ↗First posted 10 Dec 2019cs.LG math.OC stat.MLcited by 47

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 9; 2023: 8; 2024: 9; 2025: 8; 2026: 4.

47 papers.

Sort:

By area:

2021Recent Advances in Reinforcement Learning in Financecited by 110
2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
2021Breaking the Deadly Triad with a Target Networkcited by 47
2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
2022When Data Geometry Meets Deep Function: Generalizing Offline Reinforcement Learningcited by 31
2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 12

35 more

2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
2021Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximationcited by 10
2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
2022Funnel-based Reward Shaping for Signal Temporal Logic Tasks in Reinforcement Learningcited by 8
2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
2023On the Performance of Temporal Difference Learning With Neural Networkscited by 6
2024Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorizationcited by 6
2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
2024SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learningcited by 5
2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
2022Does DQN Learn?cited by 4
2024An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networkscited by 4
2022Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methodscited by 3
2022Finite-Time Error Bounds for Greedy-GQcited by 3
2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrizationcited by 3
2023Multi-Bellman operator for convergence of Q-learning with linear function approximationcited by 3
2023A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothnesscited by 2
2024Regularized Q-Learning with Linear Function Approximationcited by 2
2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2
2021Finite-Time Error Bounds for Distributed Linear Stochastic Approximationcited by 1
2024A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimizationcited by 1
2025Deep neural networks can provably solve Bellman equations for Markov decision processes without the curse of dimensionalitycited by 1
2025A Communication-Efficient Decentralized Actor-Critic Algorithmcited by 1
2026Learning to Hand Off: Provably Convergent Workflow Learning under Interface Constraintscited by 1
2023Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximationcited by 0
2023A Single-Loop Deep Actor-Critic Algorithm for Constrained Reinforcement Learning with Provable Convergencecited by 0
2024Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximationcited by 0
2025Context-aware Constrained Reinforcement Learning Based Energy-Efficient Power Scheduling for Non-stationary XR Data Trafficcited by 0
2025Joint User Priority and Power Scheduling for QoS-Aware WMMSE Precoding: A Constrained-Actor Attentive-Critic Approachcited by 0
2025Reinforcement Learning and Consumption-Savings Behaviorcited by 0
2025Deep SOR Minimax Q-learning for Two-player Zero-sum Gamecited by 0
2026Implicit Q-Learning and SARSA: Liberating Policy Control from Step-Size Calibrationcited by 0
2026Beyond the Independence Assumption: Finite-Sample Guarantees for Deep Q-Learning under τ-Mixingcited by 0
2026A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Boundscited by 0