Going Beyond Linear RL: Sample Efficient Neural Function Approximation

Abstract

Deep Reinforcement Learning (RL) powered by neural net approximation of the Q function has had enormous empirical success. While the theory of RL has traditionally focused on linear function approximation (or eluder dimension) approaches, little is known about nonlinear RL with neural net approximations of the Q functions. This is the focus of this work, where we study function approximation with two-layer neural networks (considering both ReLU and polynomial activation functions). Our first result is a computationally and statistically efficient algorithm in the generative model setting under completeness for two-layer neural networks. Our second result considers this setting but under only realizability of the neural net function class. Here, assuming deterministic dynamics, the sample complexity scales linearly in the algebraic dimension. In all cases, our results significantly improve upon what can be attained with linear (or eluder dimension) methods.

References in corpus (16)

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Recovery Guarantees for One-hidden-layer Neural Networks
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Label Noise SGD Provably Prefers Flat Global Minimizers
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization