mlsanityData to 14 Oct 2026

A Theoretical Analysis of Deep Q-Learning

arXiv 1901.00137 ↗First posted 1 Jan 2019cs.LG math.OC stat.MLcited by 215

Not on the map. Why?

Cited by 49 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on a slight simplification of DQN that fully captures its key features. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by DQN. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players. Borrowing the analysis of DQN, we also quantify the difference between the policies obtained by Minimax-DQN and the Nash equilibrium of the Markov game in terms of both the algorithmic and statistical rates of convergence.

Key facts. Cited by 215 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 2; 2021: 42; 2022: 40; 2023: 46; 2024: 38; 2025: 28; 2026: 19.

215 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  2. 2023A Cookbook of Self-Supervised Learningcited by 250
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  4. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  6. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  7. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  8. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 95
  9. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  10. 2022q-Learning in Continuous Timecited by 91
  11. 2024Process Reward Model with Q-Value Rankingscited by 80
  12. 2024Simplifying Deep Temporal Difference Learningcited by 78
38 more
  1. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  2. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  3. 2024Large Language Model for Table Processing: A Surveycited by 52
  4. 2021Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challengescited by 50
  5. 2023Reward-Directed Conditional Diffusion: Provable Distribution Estimation and Reward Improvementcited by 49
  6. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  7. 2024Parameter-Efficient Fine-Tuning in Large Models: A Survey of Methodologiescited by 47
  8. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  9. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  10. 2021Deeply-Debiased Off-Policy Interval Estimationcited by 36
  11. 2025LLM-Powered GUI Agents in Phone Automation: Surveying Progress and Prospectscited by 32
  12. 2022Off-Policy Confidence Interval Estimation with Confounded Markov Decision Processcited by 31
  13. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  14. 2022When Data Geometry Meets Deep Function: Generalizing Offline Reinforcement Learningcited by 31
  15. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  16. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  17. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  18. 2021Estimating Optimal Infinite Horizon Dynamic Treatment Regimes via pT-Learningcited by 26
  19. 2023Resetting the Optimizer in Deep RL: An Empirical Studycited by 26
  20. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  21. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  22. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  23. 2024Diffusion Model for Data-Driven Black-Box Optimizationcited by 24
  24. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  25. 2026Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statisticcited by 21
  26. 2021A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representationcited by 19
  27. 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 19
  28. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  29. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  30. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  31. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  32. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  33. 2023Reinforcement Unlearningcited by 17
  34. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  35. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 16
  36. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  37. 2023TD Convergence: An Optimization Perspectivecited by 16
  38. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16

50 most cited of 215 All 215 (JSON)