Understanding Deep Q-Learning

• Activity Number: 533 - Prediction and Inference in Statistical Machine Learning
• Type: Invited
• Date/Time: Thursday, August 11, 2022 : 10:30 AM to 12:20 PM
• Sponsor: IMS
• Author(s): Jianqing Fan and Zhaoran Wang and Yuchen Xie and Zhuoran Yang*
• Companies: Princeton University and Northwestern University and Northwestern University and Yale University
• Keywords: Reinforcement Learning; Deep Learning; statistical errors; algorithmic error; Markov Decision process;

Abstract

We provide theoretically understand the deep Q-network (DQN) algorithm from both algorithmic and statistical perspectives. Specifically, we focus on a slight simplification of DQN that fully captures its key features. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by DQN. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players. Borrowing the analysis of DQN, we also quantify the difference between the policies obtained by Minimax-DQN and the Nash equilibrium of the Markov game in terms of both the algorithmic and statistical rates of convergence.