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

2022/11/14 by Gaur, Mudit, Aggarwal, Vaneet, Agarwal, Mridul · 1 citation
#Artificial Intelligence (cs.AI) #F.2.1 #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2211.07675

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 O(1/ε²), 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.

Cited by

• Discrete State Diffusion Models: A Sample Complexity Perspective

Related

• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training
• Universal Approximation Theorem of Deep Q-Networks
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes
• Deep Q-Learning: Theoretical Insights from an Asymptotic Analysis