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 (36)

• Continuous control with deep reinforcement learning
• Playing Atari with Deep Reinforcement Learning
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Dota 2 with Large Scale Deep Reinforcement Learning
• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• A Convergence Theory for Deep Learning via Over-Parameterization
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Deep Reinforcement Learning that Matters
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Recovery Guarantees for One-hidden-layer Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Few-Shot Learning via Learning the Representation, Provably
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• Practical Contextual Bandits with Regression Oracles
• Active Learning for Cost-Sensitive Classification
• 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
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exploration-Enhanced POLITEX
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• On Oracle-Efficient PAC RL with Rich Observations
• 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