Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima

Abstract

Temporal-difference learning (TD), coupled with neural networks, is among the most fundamental building blocks of deep reinforcement learning. However, due to the nonlinearity in value function approximation, such a coupling leads to nonconvexity and even divergence in optimization. As a result, the global convergence of neural TD remains unclear. In this paper, we prove for the first time that neural TD converges at a sublinear rate to the global optimum of the mean-squared projected Bellman error for policy evaluation. In particular, we show how such global convergence is enabled by the overparametrization of neural networks, which also plays a vital role in the empirical success of neural TD. Beyond policy evaluation, we establish the global convergence of neural (soft) Q-learning, which is further connected to that of policy gradient algorithms.

References in corpus (29)

• Continuous control with deep reinforcement learning
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Trust Region Policy Optimization
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• A Convergence Theory for Deep Learning via Over-Parameterization
• Deep Reinforcement Learning that Matters
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Equivalence Between Policy Gradients and Soft Q-Learning
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• A unified view of entropy-regularized Markov decision processes
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• SGD Learns the Conjugate Kernel Class of the Network
• Stochastic Variance Reduction Methods for Policy Evaluation
• Towards Characterizing Divergence in Deep Q-Learning
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• A Selective Overview of Deep Learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Convergent Tree Backup and Retrace with Function Approximation
• Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting
• TD or not TD: Analyzing the Role of Temporal Differencing in Deep Reinforcement Learning
• Geometric Insights into the Convergence of Nonlinear TD Learning
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes

Cited by in corpus (11)

• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• Experience Replay with Likelihood-free Importance Weights
• Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Breaking the Deadly Triad with a Target Network
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Actor-critic is implicitly biased towards high entropy optimal policies
• A Unified Off-Policy Evaluation Approach for General Value Function