Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
arXiv:2006.04761
Abstract
Temporal-difference and Q-learning play a key role in deep reinforcement learning, where they are empowered by expressive nonlinear function approximators such as neural networks. At the core of their empirical successes is the learned feature representation, which embeds rich observations, e.g., images and texts, into the latent space that encodes semantic structures. Meanwhile, the evolution of such a feature representation is crucial to the convergence of temporal-difference and Q-learning. In particular, temporal-difference learning converges when the function approximator is linear in a feature representation, which is fixed throughout learning, and possibly diverges otherwise. We aim to answer the following questions: When the function approximator is a neural network, how does the associated feature representation evolve? If it converges, does it converge to the optimal one? We prove that, utilizing an overparameterized two-layer neural network, temporal-difference and Q-learning globally minimize the mean-squared projected Bellman error at a sublinear rate. Moreover, the associated feature representation converges to the optimal one, generalizing the previous analysis of Cai et al. (2019) in the neural tangent kernel regime, where the associated feature representation stabilizes at the initial one. The key to our analysis is a mean-field perspective, which connects the evolution of a finite-dimensional parameter to its limiting counterpart over an infinite-dimensional Wasserstein space. Our analysis generalizes to soft Q-learning, which is further connected to policy gradient.
add acknowledgement
References in corpus (25)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- On Exact Computation with an Infinitely Wide Neural Net
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- Bridging the Gap Between Value and Policy Based Reinforcement Learning
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU 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
- Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
- Combining policy gradient and Q-learning
- Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
- SGD Learns the Conjugate Kernel Class of the Network
- Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
- A mean-field limit for certain deep neural networks
- Deep Reinforcement Learning with a Natural Language Action Space
- Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
- A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
- How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
- Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
- Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
- Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes