Going Beyond Linear RL: Sample Efficient Neural Function Approximation

• URL: http://arxiv.org/abs/2107.06466v1
• Date: Wed, 14 Jul 2021 03:03:56 GMT
• Title: Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Authors: Baihe Huang and Kaixuan Huang and Sham M. Kakade and Jason D. Lee and Qi Lei and Runzhe Wang and Jiaqi Yang
• Abstract summary: We study function approximation with two-layer neural networks. Our results significantly improve upon what can be attained with linear (or eluder dimension) methods.
• Score: 76.57464214864756
• License: http://creativecommons.org/publicdomain/zero/1.0/
• 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.

Related papers

• The limitation of neural nets for approximation and optimization [0.0]
  We are interested in assessing the use of neural networks as surrogate models to approximate and minimize objective functions in optimization problems. Our study begins by determining the best activation function for approximating the objective functions of popular nonlinear optimization test problems.
  arXiv  Detail & Related papers  (2023-11-21T00:21:15Z)
• Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning [53.97335841137496]
  We propose an oracle-efficient algorithm, dubbed Pessimistic Least-Square Value Iteration (PNLSVI) for offline RL with non-linear function approximation. Our algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation.
  arXiv  Detail & Related papers  (2023-10-02T17:42:01Z)
• Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
  The linearized-Laplace approximation (LLA) has been shown to be effective and efficient in constructing Bayesian neural networks. We study the usefulness of the LLA in Bayesian optimization and highlight its strong performance and flexibility.
  arXiv  Detail & Related papers  (2023-04-17T14:23:43Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  We study weight decay regularized training problems of deep neural networks with threshold activations. We derive a simplified convex optimization formulation when the dataset can be shattered at a certain layer of the network.
  arXiv  Detail & Related papers  (2023-03-06T18:59:13Z)
• Deep neural networks for smooth approximation of physics with higher order and continuity B-spline base functions [0.4588028371034407]
  Traditionally, the neural network employs non-linear activation functions to approximate a given physical phenomenon. We present an alternative approach, where the physcial quantity is approximated as a linear combination of smooth B-spline basis functions. We show that our approach is cheaper and more accurate when approximating physical fields.
  arXiv  Detail & Related papers  (2022-01-03T23:02:39Z)
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed [27.38015169185521]
  We show theoretically that two-layer neural networks (2LNN) with only a few hidden neurons can beat the performance of kernel learning. We show how over-parametrising the neural network leads to faster convergence, but does not improve its final performance.
  arXiv  Detail & Related papers  (2021-02-23T15:10:15Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  We study estimation in a class of generalized Structural equation models (SEMs) We formulate the linear operator equation as a min-max game, where both players are parameterized by neural networks (NNs), and learn the parameters of these neural networks using a gradient descent. For the first time we provide a tractable estimation procedure for SEMs based on NNs with provable convergence and without the need for sample splitting.
  arXiv  Detail & Related papers  (2020-07-02T17:55:47Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.