A Theoretical Analysis of Deep Q-Learning

Jianqing Fan, Zhaoran Wang, Yuchen Xie, Zhuoran Yang

Research output: Contribution to journalConference articlepeer-review

240 Scopus citations

Abstract

Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, 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.

Original languageEnglish (US)
Pages (from-to)486-489
Number of pages4
JournalProceedings of Machine Learning Research
Volume120
StatePublished - 2020
Event2nd Annual Conference on Learning for Dynamics and Control, L4DC 2020 - Berkeley, United States
Duration: Jun 10 2020Jun 11 2020

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Keywords

  • Deep Q-Learning
  • Markov Decision Process
  • Zero-Sum Markov Game

Fingerprint

Dive into the research topics of 'A Theoretical Analysis of Deep Q-Learning'. Together they form a unique fingerprint.

Cite this