mlsanityData to 7 Oct 2026

Going Beyond Linear RL: Sample Efficient Neural Function Approximation

arXiv 2107.06466 ↗First posted 14 Jul 2021cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 57 of its 99 references that are in the map. First posted on arXiv 14 Jul 2021.

Builds on

57 of 99 references.

References · 57

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2017Deep Reinforcement Learning that Matterscited by 727
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  9. 2018Is Q-learning Provably Efficient?cited by 485
  10. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  11. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  12. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
38 more
  1. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  2. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  3. 2020Few-Shot Learning via Learning the Representation, Provablycited by 213
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  7. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  8. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  9. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  10. 2019Linearized two-layers neural networks in high dimensioncited by 155
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  13. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  14. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  15. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  16. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  17. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  18. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  19. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  20. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  21. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  22. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  23. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  24. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  25. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  26. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 70
  27. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  28. 2019Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Modelscited by 53
  29. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  30. 2020Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networkscited by 44
  31. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 42
  32. 2017Active Learning for Cost-Sensitive Classificationcited by 40
  33. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  34. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  35. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  36. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  37. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  38. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 4; 2024: 0; 2025: 1; 2026: 1.

9 papers.

  1. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  2. 2022Representation Learning in Deep RL via Discrete Information Bottleneckcited by 13
  3. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  4. 2023On Representation Complexity of Model-based and Model-free Reinforcement Learningcited by 6
  5. 2023Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fieldscited by 4
  6. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  7. 2023Uncertainty-aware transfer across tasks using hybrid model-based successor feature reinforcement learningcited by 1
  8. 2025Representative Action Selection for Large Action Space: From Bandits to MDPscited by 0
  9. 2026Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilitiescited by 0