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

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

## 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 (most cited first, 30 of 33)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms](https://mlsanity.com/paper/2012.13329/) (2020)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions](https://mlsanity.com/paper/2202.01331/) (2022)
- [The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions](https://mlsanity.com/paper/2006.05900/) (2020)
- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Convex Regularization Behind Neural Reconstruction](https://mlsanity.com/paper/2012.05169/) (2020)
- [Application of Deep Q-Network in Portfolio Management](https://mlsanity.com/paper/2003.06365/) (2020)
- [Decision Making in Monopoly using a Hybrid Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2103.00683/) (2021)

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

- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [Discrete State Diffusion Models: A Sample Complexity Perspective](https://mlsanity.com/paper/2510.10854/) (2025)
- [Deep Reinforcement Learning: A Convex Optimization Approach](https://mlsanity.com/paper/2402.19212/) (2024)

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