← Back to papers
2023 ICML ICML 2023

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

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.

🧭 Keyword Pioneer — neural network parametrization
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Data Science & Analytics, Deep Learning, Machine Learning, Mathematics & Optimization, Reinforcement Learning, Robotics
🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning

Authors

Mudit Gaur , Vaneet Aggarwal , Mridul Agarwal

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Neural Network Optimization Reinforcement Learning > Methods > Deep RL Reinforcement Learning > Methods > Value Iteration Machine Learning > Optimization & Theory > Sample Complexity

Keywords

global convergence sample complexity fitted q-iteration relu neural network deep q-learning neural network parametrization
Download PDF

Related papers

Orthogonality-Enforced Latent Space in Autoencoders: An Approach to Learning Disentangled Representations 2023
On the Convergence Rate of Gaussianization with Random Rotations 2023
Synthetic Prompting: Generating Chain-of-Thought Demonstrations for Large Language Models 2023
Generative Adversarial Symmetry Discovery 2023
Function-Space Regularization in Neural Networks: A Probabilistic Perspective 2023