2019

A Theoretical Analysis of Deep Q-Learning

Fan, Jianqing, Wang, Zhaoran, Xie, Yuchen et al.

Understand

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.

Built on

A generalization theory of gradient descent for learning over-parameterized deep ReLU networks
Original
Cao, Y · 1902
Earlier work this paper cites.
Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation
Original
Yang, G · 1902
Earlier work this paper cites.
A selective overview of deep learning
Original
Fan, J · 1904
Earlier work this paper cites.
Striving for simplicity in off-policy deep reinforcement learning
Original
Agarwal, R · 1907
Earlier work this paper cites.
A fine-grained spectral perspective on neural networks
Original
Yang, G · 1907
Earlier work this paper cites.
Reinforcement learning in healthcare: A survey
Original
Yu, C · 1908
Earlier work this paper cites.
Beyond linearization: On quadratic and higher-order approximation of wide neural networks
Original
Bai, Y · 1910
Earlier work this paper cites.
Benchmarking batch deep reinforcement learning algorithms
Original
Fujimoto, S · 1910
Earlier work this paper cites.
A finite-time analysis of Q-learning with neural network function approximation
Original
Xu, P · 1912
Earlier work this paper cites.
Theory of games and economic behavior
Von Neumann, J · 1947
Earlier work this paper cites.
Stochastic games
Shapley, L. S · 1953
Earlier work this paper cites.
Dropout: A simple way to prevent neural networks from overfitting
Srivastava, N · 1958
Earlier work this paper cites.
Projection pursuit regression
Friedman, J. H · 1981
Earlier work this paper cites.
Optimal global rates of convergence for nonparametric regression
Stone, C. J · 1982
Earlier work this paper cites.
Self-improving reactive agents based on reinforcement learning, planning and teaching
Lin, L.-J · 1992
Earlier work this paper cites.
Q-learning
Watkins, C. J · 1992
Earlier work this paper cites.
Markov games as a framework for multi-agent reinforcement learning
Littman, M. L · 1994
Earlier work this paper cites.
Neural nets with superlinear VC-dimension
Maass, W · 1994
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
Baird, L · 1995
Earlier work this paper cites.
Linear least-squares algorithms for temporal difference learning
Bradtke, S. J · 1996
Earlier work this paper cites.
Stochastic and shortest path games: Theory and algorithms
Patek, S. D · 1997
Earlier work this paper cites.
The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network
Bartlett, P. L · 1998
Earlier work this paper cites.
Almost linear VC dimension bounds for piecewise polynomial networks
Bartlett, P. L · 1999
Earlier work this paper cites.
Actor-critic algorithms
Konda, V. R · 2000
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S · 2000
Earlier work this paper cites.
Rational and convergent learning in stochastic games
Bowling, M · 2001
Earlier work this paper cites.
Technical update: Least-squares temporal difference learning
Boyan, J. A · 2002
Earlier work this paper cites.
Why do deep residual networks generalize better than deep feedforward networks?–A neural tangent kernel perspective
Original
Huang, K · 2002
Earlier work this paper cites.
Value function approximation in zero-sum Markov games
Lagoudakis, M. G · 2002
Earlier work this paper cites.
Least-squares policy iteration
Lagoudakis, M. G · 2003
Earlier work this paper cites.
Optimal dynamic treatment regimes
Murphy, S. A · 2003
Earlier work this paper cites.
Tree-based batch mode reinforcement learning
Ernst, D · 2005
Earlier work this paper cites.
A generalization error for Q-learning
Murphy, S. A · 2005
Earlier work this paper cites.
Neural fitted Q iteration – First experiences with a data efficient neural reinforcement learning method
Riedmiller, M · 2005
Earlier work this paper cites.
Value-iteration based fitted policy iteration: Learning with a single trajectory
Antos, A · 2007
Earlier work this paper cites.
AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents
Conitzer, V · 2007
Earlier work this paper cites.
Kernel methods in machine learning
Hofmann, T · 2008
Earlier work this paper cites.
Finite-time bounds for fitted value iteration
Munos, R · 2008
Earlier work this paper cites.
Random features for large-scale kernel machines
Rahimi, A · 2008
Earlier work this paper cites.
Introduction to nonparametric estimation
Tsybakov, A. B · 2008
Earlier work this paper cites.
Neural network learning: Theoretical foundations
Anthony, M · 2009
Earlier work this paper cites.
Regularized fitted Q-iteration for planning in continuous-space Markovian decision problems
Farahmand, A.-m · 2009
Earlier work this paper cites.
Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning
Rahimi, A · 2009
Earlier work this paper cites.
Reinforcement learning design for cancer clinical trials
Zhao, Y · 2009
Earlier work this paper cites.
Error propagation for approximate policy and value iteration
Farahmand, A.-m · 2010
Earlier work this paper cites.

Similar

Rectified linear units improve restricted boltzmann machines
Nair, V · 2010
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
Original
Vershynin, R · 2010
Cited alongside, same era.
Performance guarantees for individualized treatment rules
Qian, M · 2011
Cited alongside, same era.
Reinforcement learning: An introduction
Sutton, R. S · 2011
Cited alongside, same era.
Reinforcement learning strategies for clinical trials in nonsmall cell lung cancer
Zhao, Y · 2011
Cited alongside, same era.
Q-learning with censored data
Goldberg, Y · 2012
Cited alongside, same era.
Reinforcement learning in robotics: A survey
Kober, J · 2012
Cited alongside, same era.
Batch reinforcement learning
Lange, S · 2012
Cited alongside, same era.
Finite-sample analysis of least-squares policy iteration
Lazaric, A · 2012
Cited alongside, same era.
Foundations of machine learning
Mohri, M · 2012
Cited alongside, same era.
Q-learning: A data analysis method for constructing adaptive interventions
Nahum-Shani, I · 2012
Cited alongside, same era.
A robust method for estimating optimal treatment regimes
Zhang, B · 2012
Cited alongside, same era.

Then

Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
Original
Dziugaite, G. K · 2017
Later among the works it cites.
Reinforcement learning with deep energy-based policies
Haarnoja, T · 2017
Later among the works it cites.
Generalization in deep learning
Original
Kawaguchi, K · 2017
Later among the works it cites.
Shallow updates for deep reinforcement learning
Levine, N · 2017
Later among the works it cites.
Interactive q-learning for quantiles
Linn, K. A · 2017
Later among the works it cites.
Exploring generalization in deep learning
Neyshabur, B · 2017
Later among the works it cites.
Proximal policy optimization algorithms
Original
Schulman, J · 2017
Later among the works it cites.
Mastering the game of Go without human knowledge
Silver, D · 2017
Later among the works it cites.
Boosted fitted Q-iteration
Tosatto, S · 2017
Later among the works it cites.
Online reinforcement learning in stochastic games
Wei, C.-Y · 2017
Later among the works it cites.
A deeper look at experience replay
Original
Zhang, S · 2017
Later among the works it cites.
Residual weighted learning for estimating individualized treatment rules
Zhou, X · 2017
Later among the works it cites.
Approximation and estimation for high-dimensional deep learning networks
Original
Barron, A. R · 2018
Later among the works it cites.
Size-independent sample complexity of neural networks
Golowich, N · 2018
Later among the works it cites.
Neural tangent kernel: Convergence and generalization in neural networks
Jacot, A · 2018
Later among the works it cites.
The effects of memory replay in reinforcement learning
Liu, R · 2018
Later among the works it cites.
A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks
Neyshabur, B · 2018
Later among the works it cites.
Actor-critic fictitious play in simultaneous move multistage games
Pérolat, J · 2018
Later among the works it cites.
High-dimensional A-learning for optimal dynamic treatment regimes
Shi, C · 2018
Later among the works it cites.
Actor-critic policy optimization in partially observable multiagent environments
Srinivasan, S · 2018
Later among the works it cites.
Finite-sample analyses for fully decentralized multi-agent reinforcement learning
Original
Zhang, K · 2018
Later among the works it cites.
Stochastic gradient descent optimizes over-parameterized deep ReLU networks
Original
Zou, D · 2018
Later among the works it cites.
Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks
Arora, S · 2019
Closest in time.
Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
Bartlett, P. L · 2019
Closest in time.
On deep learning as a remedy for the curse of dimensionality in nonparametric regression
Bauer, B · 2019
Closest in time.
On the inductive bias of neural tangent kernels
Bietti, A · 2019
Closest in time.
Neural temporal-difference learning converges to global optima
Cai, Q · 2019
Closest in time.
Information-theoretic considerations in batch reinforcement learning
Chen, J · 2019
Closest in time.
On lazy training in differentiable programming
Chizat, L · 2019
Closest in time.
The lottery ticket hypothesis: Finding sparse, trainable neural networks
Frankle, J · 2019
Closest in time.
Algorithm-dependent generalization bounds for overparameterized deep residual networks
Frei, S · 2019
Closest in time.
Convergence of adversarial training in overparametrized networks
Gao, R · 2019
Closest in time.
A theory of regularized Markov decision processes
Geist, M · 2019
Closest in time.
Fisher-Rao metric, geometry, and complexity of neural networks
Liang, T · 2019
Closest in time.
Mean-field theory of two-layers neural networks: Dimension-free bounds and kernel limit
Mei, S · 2019
Closest in time.
Remember and forget for experience replay
Novati, G · 2019
Closest in time.
Adaptivity of deep relu network for learning in Besov and mixed smooth Besov spaces: Optimal rate and curse of dimensionality
Suzuki, T · 2019
Closest in time.
Dynamic Treatment Regimes: Statistical Methods for Precision Medicine
Tsiatis, A. A · 2019
Closest in time.
Grandmaster level in StarCraft II using multi-agent reinforcement learning
Vinyals, O · 2019
Closest in time.
Neural policy gradient methods: Global optimality and rates of convergence
Wang, L · 2019
Closest in time.
A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics
Weinan, E · 2019
Closest in time.
On the power and limitations of random features for understanding neural networks
Yehudai, G · 2019
Closest in time.
Proper inference for value function in high-dimensional Q-learning for dynamic treatment regimes
Zhu, W · 2019
Closest in time.
Nonparametric regression using deep neural networks with ReLU activation function
Schmidt-Hieber, J · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…