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

Mudit Gaur; Vaneet Aggarwal; Mridul Agarwal

ICML 2023poster3 citations

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

Mudit Gaur, Vaneet Aggarwal, Mridul Agarwal

Abstract

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 $\tilde{\mathcal{O}}(1/\epsilon^{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.

BibTeX

@inproceedings{icml2023_ontheglobalconve,
  title = {On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization},
  author = {Mudit Gaur and Vaneet Aggarwal and Mridul Agarwal},
  booktitle = {ICML 2023},
  year = {2023}
}