# On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 57 of its 91 references that are in the map.
- First posted on arXiv 24 Oct 2023.

## Builds on (most cited first, 30 of 57)

- [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)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [What do you learn from context? Probing for sentence structure in contextualized word representations](https://mlsanity.com/paper/1905.06316/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [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)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Socially Aware Motion Planning with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.08862/) (2017)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)

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

- [How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?](https://mlsanity.com/paper/2402.15607/) (2024)
- [LLM-Empowered State Representation for Reinforcement Learning](https://mlsanity.com/paper/2407.13237/) (2024)
- [A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Experts](https://mlsanity.com/paper/2405.16646/) (2024)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [The Central Role of the Loss Function in Reinforcement Learning](https://mlsanity.com/paper/2409.12799/) (2024)
- [Digital Twin-Enhanced Deep Reinforcement Learning for Resource Management in Networks Slicing](https://mlsanity.com/paper/2311.16876/) (2023)
- [How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalance](https://mlsanity.com/paper/2403.07310/) (2024)
- [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)
- [How Can Mamba Learn In Context with Outliers and Generalize Provably?](https://mlsanity.com/paper/2510.00399/) (2025)
- [Periodic Regularized Q-Learning](https://mlsanity.com/paper/2602.03301/) (2026)
- [Approximation to Deep Q-Network by Stochastic Delay Differential Equations](https://mlsanity.com/paper/2505.00382/) (2025)
- [Optimizing Metachronal Paddling with Reinforcement Learning at Low Reynolds Number](https://mlsanity.com/paper/2507.18849/) (2025)
- [Towards Model-Free Learning in Dynamic Population Games: An Application to Karma Economies](https://mlsanity.com/paper/2605.11042/) (2026)
- [A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Bounds](https://mlsanity.com/paper/2609.18782/) (2026)
- [Limiting-Kernel Q(λ): Bridging Short and Long Horizons](https://mlsanity.com/paper/2609.27741/) (2026)

## Abstract (arXiv)

This paper provides a theoretical understanding of Deep Q-Network (DQN) with the varepsilon-greedy exploration in deep reinforcement learning. Despite the tremendous empirical achievement of the DQN, its theoretical characterization remains underexplored. First, the exploration strategy is either impractical or ignored in the existing analysis. Second, in contrast to conventional Q-learning algorithms, the DQN employs the target network and experience replay to acquire an unbiased estimation of the mean-square Bellman error (MSBE) utilized in training the Q-network. However, the existing theoretical analysis of DQNs lacks convergence analysis or bypasses the technical challenges by deploying a significantly overparameterized neural network, which is not computationally efficient. This paper provides the first theoretical convergence and sample complexity analysis of the practical setting of DQNs with ε-greedy policy. We prove an iterative procedure with decaying ε converges to the optimal Q-value function geometrically. Moreover, a higher level of ε values enlarges the region of convergence but slows down the convergence, while the opposite holds for a lower level of ε values. Experiments justify our established theoretical insights on DQNs.