mlsanityData to 14 Oct 2026

On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization

arXiv 2211.07675 ↗First posted 14 Nov 2022cs.LG cs.AIcited by 3

Not on the map. Why?

Abstract (arXiv)

Deep Q-learning based algorithms have been applied successfully in many decision making problems, while their theoretical foundations are not as well understood. In this paper, we study a Fitted Q-Iteration with two-layer ReLU neural network parameterization, and find the sample complexity guarantees for the algorithm. Our approach estimates the Q-function in each iteration using a convex optimization problem. We show that this approach achieves a sample complexity of tildeO(1/ε2), which is order-optimal. This result holds for a countable state-spaces and does not require any assumptions such as a linear or low rank structure on the MDP.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 33 of its 71 references that are in the map. First posted on arXiv 14 Nov 2022.

Builds on

33 of 71 references.

References · 33

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  3. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,241
  4. 2017Hindsight Experience Replaycited by 1,136
  5. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 415
  8. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  9. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  11. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  12. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
21 more
  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  3. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  4. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 98
  5. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  6. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  7. 2018On Markov Chain Gradient Descentcited by 63
  8. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  9. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  10. 2020Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithmscited by 34
  11. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  12. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
  13. 2020The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutionscited by 30
  14. 2022Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformerscited by 30
  15. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  16. 2020Convex Regularization Behind Neural Reconstructioncited by 15
  17. 2020Application of Deep Q-Network in Portfolio Managementcited by 11
  18. 2021Decision Making in Monopoly using a Hybrid Deep Reinforcement Learning Approachcited by 6
  19. 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settingscited by 5
  20. 2021Q-Value Weighted Regression: Reinforcement Learning with Limited Datacited by 4
  21. 2021One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networkscited by 3

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  2. 2025Discrete State Diffusion Models: A Sample Complexity Perspectivecited by 5
  3. 2024Deep Reinforcement Learning: A Convex Optimization Approachcited by 0