mlsanityData to 14 Oct 2026

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

arXiv 2310.16173 ↗First posted 24 Oct 2023cs.LGcited by 17

Not on the map. Why?

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.

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

57 of 91 references.

References · 57

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  4. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 743
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  6. 2017Deep Neural Networks as Gaussian Processescited by 622
  7. 2016Deep Exploration via Bootstrapped DQNcited by 527
  8. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  9. 2019What do you learn from context? Probing for sentence structure in contextualized word representationscited by 438
  10. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  11. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  12. 2017Noisy Networks for Explorationcited by 266
38 more
  1. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  4. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  6. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
  7. 2017Socially Aware Motion Planning with Deep Reinforcement Learningcited by 136
  8. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  9. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  10. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  11. 2020Feature Purification: How Adversarial Training Performs Robust Deep Learningcited by 107
  12. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  13. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  14. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  15. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  16. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  17. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  18. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  19. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  20. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  21. 2018Efficient Exploration through Bayesian Deep Q-Networkscited by 67
  22. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  23. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  24. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  25. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  26. 2019Deep Reinforcement Learning for Autonomous Internet of Things: Model, Applications and Challengescited by 37
  27. 2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
  28. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  29. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  30. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 31
  31. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  32. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  33. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  34. 2018Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalizationcited by 21
  35. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  36. 2022How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysiscited by 19
  37. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  38. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 7; 2025: 5; 2026: 4.

17 papers.

Sort:

By area:

  1. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  2. 2024LLM-Empowered State Representation for Reinforcement Learningcited by 28
  3. 2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
  4. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  5. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 12
  6. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  7. 2023Digital Twin-Enhanced Deep Reinforcement Learning for Resource Management in Networks Slicingcited by 7
  8. 2024How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalancecited by 6
  9. 2024SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learningcited by 5
  10. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  11. 2025How Can Mamba Learn In Context with Outliers and Generalize Provably?cited by 2
  12. 2026Periodic Regularized Q-Learningcited by 1
5 more
  1. 2025Approximation to Deep Q-Network by Stochastic Delay Differential Equationscited by 0
  2. 2025Optimizing Metachronal Paddling with Reinforcement Learning at Low Reynolds Numbercited by 0
  3. 2026Towards Model-Free Learning in Dynamic Population Games: An Application to Karma Economiescited by 0
  4. 2026A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Boundscited by 0
  5. 2026Limiting-Kernel Q(λ): Bridging Short and Long Horizonscited by 0