A Theoretical Analysis of Deep Q-Learning

By Zhuoran Yang, Yuchen Xie, Zhaoran Wang. 2019

772 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Towards Characterizing Divergence in Deep Q-Learning (2019, methodology): “Unlike Q-learning, DQL in its standard form currently has no known convergence guarantees, although some convergence results (Yang et al., 2019) have been obtained for a closely-related algorithm called Neural-Fitted Q Iteration (Riedmiller, 2005) when used with deep ReLU networks. is the neural…”
VIREL: A Variational Inference Framework for Reinforcement Learning (2018, background): “[72] for a theoretical exposition of Q-learning using function approximators.”
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, methodology): “Additionally, finite-time performance of Q-learning and its variants have been analyzed by [5, 9, 20, 28, 35, 44, 48] in the tabular setting, by [6, 8, 10, 17, 18, 21, 49, 52] in the context of function approximations, and by [36] with nonparametric regression.”
Is Pessimism Provably Efficient for Offline RL? (2020, neutral): “…2010; 2016; Scherrer et al., 2015; Liu et al., 2018; Nachum et al., 2019a;b; Chen and Jiang, 2019; Tang et al., 2019; Kallus and Uehara, 2019; 2020; Fan et al., 2020; Xie and Jiang, 2020a;b; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin et al., 2020; Qu and Wierman, 2020; Li…”
Recent advances in reinforcement learning in finance (2021, background): “Thus, experience replay stabilizes the training of DQN, which benefits the algorithm in terms of computational efficiency.”
The Kolmogorov-Arnold representation theorem revisited (2020, background): “Approximation properties of deep neural networks for composed functions are studied in [12, 25, 21, 13, 26, 3, 23, 27, 6].”
Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, methodology): “For modern RL methods commonly used in power systems, such as DQN and actor-critic, the sample complexity also depends on the complexity of the function class adopted to approximate the Q -function and the intrinsic approximation error of the function class [48], [190].”