# A Theoretical Analysis of Deep Q-Learning

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

## Key facts

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

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

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [A Cookbook of Self-Supervised Learning](https://mlsanity.com/paper/2304.12210/) (2023)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [q-Learning in Continuous Time](https://mlsanity.com/paper/2207.00713/) (2022)
- [Process Reward Model with Q-Value Rankings](https://mlsanity.com/paper/2410.11287/) (2024)
- [Simplifying Deep Temporal Difference Learning](https://mlsanity.com/paper/2407.04811/) (2024)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Large Language Model for Table Processing: A Survey](https://mlsanity.com/paper/2402.05121/) (2024)
- [Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges](https://mlsanity.com/paper/2102.01168/) (2021)
- [Reward-Directed Conditional Diffusion: Provable Distribution Estimation and Reward Improvement](https://mlsanity.com/paper/2307.07055/) (2023)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Parameter-Efficient Fine-Tuning in Large Models: A Survey of Methodologies](https://mlsanity.com/paper/2410.19878/) (2024)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [Deeply-Debiased Off-Policy Interval Estimation](https://mlsanity.com/paper/2105.04646/) (2021)
- [LLM-Powered GUI Agents in Phone Automation: Surveying Progress and Prospects](https://mlsanity.com/paper/2504.19838/) (2025)
- [Off-Policy Confidence Interval Estimation with Confounded Markov Decision Process](https://mlsanity.com/paper/2202.10589/) (2022)
- [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)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [Estimating Optimal Infinite Horizon Dynamic Treatment Regimes via pT-Learning](https://mlsanity.com/paper/2110.10719/) (2021)

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