A Theoretical Analysis of Deep Q-Learning

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.

arXiv comment65 pages

References in corpus (43)

• Continuous control with deep reinforcement learning
• Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding
• Trust Region Policy Optimization
• Dueling Network Architectures for Deep Reinforcement Learning
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Hindsight Experience Replay
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Implicit Quantile Networks for Distributional Reinforcement Learning
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• A Deeper Look at Experience Replay
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Benchmarking Batch Deep Reinforcement Learning Algorithms
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Reinforcement Learning in Healthcare: A Survey
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• A Theory of Regularized Markov Decision Processes
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Norm-Based Capacity Control in Neural Networks
• Actor-Critic Policy Optimization in Partially Observable Multiagent Environments
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Value Function Approximation in Zero-Sum Markov Games
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Information-Theoretic Considerations in Batch Reinforcement Learning
• On the Inductive Bias of Neural Tangent Kernels
• Approximation and Estimation for High-Dimensional Deep Learning Networks
• A Selective Overview of Deep Learning
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Shallow Updates for Deep Reinforcement Learning
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Remember and Forget for Experience Replay
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Online Reinforcement Learning in Stochastic Games
• The Effects of Memory Replay in Reinforcement Learning

Cited by in corpus (48)

• Game-Theoretic Multiagent Reinforcement Learning
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• VIREL: A Variational Inference Framework for Reinforcement Learning
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Mathematical Models of Overparameterized Neural Networks
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Is Pessimism Provably Efficient for Offline RL?
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Provably Efficient Exploration in Policy Optimization
• Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• A novel policy for pre-trained Deep Reinforcement Learning for Speech Emotion Recognition
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation
• Provably Efficient Reinforcement Learning with Aggregated States
• A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
• Geometric Insights into the Convergence of Nonlinear TD Learning
• Efficient time stepping for numerical integration using reinforcement learning
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• On the Reduction of Variance and Overestimation of Deep Q-Learning
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Deeply-Debiased Off-Policy Interval Estimation
• Learning to reflect: A unifying approach for data-driven stochastic control strategies
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Breaking the Deadly Triad with a Target Network
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Fast Rates for the Regret of Offline Reinforcement Learning
• Optimal policy evaluation using kernel-based temporal difference methods
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• Deep Reinforcement Learning based Dynamic Optimization of Bus Timetable
• Reinforcement Learning for Process Control with Application in Semiconductor Manufacturing
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Curriculum learning for multilevel budgeted combinatorial problems
• Reinforcement Learning In Two Player Zero Sum Simultaneous Action Games
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Logistic Q-Learning
• Periodic Q-Learning
• Evolution of Q Values for Deep Q Learning in Stable Baselines
• Decentralized Deep Reinforcement Learning for Network Level Traffic Signal Control
• Distributed Reinforcement Learning for Age of Information Minimization in Real-Time IoT Systems
• Dynamic treatment effects: high-dimensional inference under model misspecification