Timezone: »

 
Poster
Going Beyond Linear RL: Sample Efficient Neural Function Approximation
Baihe Huang · Kaixuan Huang · Sham Kakade · Jason Lee · Qi Lei · Runzhe Wang · Jiaqi Yang

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @
in Poster Session 5 »

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.

Keywords: Theory · Deep Learning · Reinforcement Learning and Planning · Generative Model

Author Information

Baihe Huang (Peking University)
Kaixuan Huang (Princeton University)
Sham Kakade (Harvard University & Microsoft Research)
Jason Lee (University of Southern California)
Qi Lei (Princeton University)
Runzhe Wang (Princeton University)
Jiaqi Yang (Tsinghua University)

More from the Same Authors