Going Beyond Linear RL: Sample Efficient Neural Function Approximation
Authors: Baihe Huang
Kaixuan Huang
Sham M. Kakade
Jason D. Lee
Qi Lei
Runzhe Wang
Jiaqi Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: beyond eluder dimension
neural net 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.

Going Beyond Linear RL: Sample Efficient Neural Function Approximation
Baihe Huang", Kaixuan Huang"", Sham M. Kakade Jason D. Lee²*
Qi Lei Runzhe Wang"*, Jiiqi Yang]
Peking University Microsofft Research
Princeton University Harvard University
TTiinghua University
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 proaches, 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 dynamies, the sample complexity scales linearly in the algebraic dimension. all cases, our results significantly improve upon what can be attained with linear (or cluder dimension) methods.
linear function approximation (or eluder dimension) ap-
Introduction
In reinforcement learning (RL), agent aims to learn the optimal decision-makinn rule by interacting with an unknown environment (71). Deep Reinforcement Learning, empowered by deep neural networks [48 32 has achieved tremendous success in various real-world applications, such Go [68], Atari [54] Dota2 [7], Texas Holdém poker [56], and autonomous driving [66]. Those modern RL applications
characterized by large state-action spaces, and the empirical success of deep RI. corroborraes the observation that deep neural networks can extrapolate well across state-action
spaces
[35 55 50).
Although in practice non- non-linear function approximation scheme is prevalent, theoretical understand- ings of the sample complexity of RL mainly focus tabular or linear function approximation settings 69 38 5 41
43 44 (77. These results rely on finite state space or exact linear ap- proximations. Recently, sample efficient algorithms under non-linear function approximation settings
63
88 [
72 13 16). Those algorithms are based on Bellman rank [40], eluder dimension 64 neural tangent kernel 377 4 [4 [92], sequential Rademacher complexity [60| 61). Yet, the understanding of how deep RL learns and generalizes in large state spaces is far from complete. While the aforementioned works study function approximation structures that possess the nice properties of linear models, such as low information gain and low eluder dimensions, the highly non-linear nature of neural networks renders challenges their applicability For one thing, recent wisdoms in deep learning theory cast doubt on the ability of neural tangent kernel and random features to model the actual neural networks. Indeed, the neural tangent kernel
are proposed 82
12
51
deep RL.
Alphabetical order. Correspondence to: Baihe Huang, baihehuanggpkk edu, cn. Jason D. Lee, Jasondl@
pr prineeton.co edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

approximately reduces neural networks to linear models, but the RKHS norm of neural networks exponential 887. Moreover. it remains unclear what neural networks models have low eluder dimensions. For example, recent work [3] shows that two layer neural networks have exponential eluder dimension the dimension of features. Thus, the mismatch between the empirical success of deep RI. and its theoretical understanding remains significant, which yields the following important question:
What are the structural properties that allow sample-effcieet algorithms for RL with neural network function approximation?
Recent work in RL suggests that learning RL with neural networks function approximation is exponentially hard [3 49 52].
In this paper, however, we advance the understanding of the above question by displaying several structural properties that allow efficient RL algorithms with neural function approximations. We consider several value function approximation models that possess high information gain and high eluder dimension. Specifically, we study two structures, namely two- layer neural networks and structured polynomials (i.e. two-layer neural networks with polynomial activation functions), under two RI. settings, namely RL with simulator model and online RI.. In the simulator (generative model) setting [45] 67). the agent can simulate the MDP at any state-action pair. In online RL, the agent can only start at an initial state and interact with the MDP step by step. The goal in both settings is to find a near-optimal policy while minimizing the number of samples used.
We obtain the following results. For the simulator setting, we propose sample-efficient algorithms for RL with two-layer neural network function approximation. Under either policy completeness, Bellman completeness, or gap conditions, our method provably learns near-optimal policy with polynomial sample complexities. For online RI., we provide sample-efficient algorithms for RL with structured polynomial function approximation. When the transition deterministic, we also present sample-efficien algorithms under only the realizability assumption [18 78 Our main techniques
are based on neural network recovery [90 39 28 and algebraic geometry [53 65 76).
1.1 Summary of our results
Our main results in different settings are summarized in Table | We consider two-layer neural networks f(z) = (v. (Wx)) (where a is ReLU activation) and rank k polynomials (see Example
Table 1: Baselines and our main results for the sample complexity to find an e-optimal policy.
rank & polynomial
Neural Net of Width A
Sim. + Det. (R) Onl. Det. (R)
Sim. + Det. (R)
Sim. Gap. (R)
Sim. + Stoch, (C)
Baseline
(dd')
O(d") O(d""1(179)) (*)
O(d9bb177)
O(dm))(179)
Our results
O(dk)
O(dk)
O(poly(d) exp(k))
O(poly(d,k))
Olpolyíd, k)/e")
We make the following elaborations on Table
For simplicity. we display only the dependence on the feature dimension d, network width polynomial rank k, precision e, and degree p (of polynomials).
In the table Sim. denotes simulator model, Onl. denotes online RL, Det. denotes deter- ministic transitions, Stoch. denotes stochastic transitions, Gap. denotes gap condition, (R) denotes realizability assumption only, and (C) denotes completeness assumption (either policy complete or Bellman complete) together with realizability assumption.
We apply (1 for the deterministic transition baseline, and apply 19 for the stochastic transition baseline. We are unaware of any methods that can directly learn MDP with neural network value function approximation
1
3p
In polynomial case, the baseline first vectorizes the tensor
into a vector in R(d+1)"
and then performs this vector. In the neural network case, the baseline uses polynomial degree 1/c to approximate the neural network with precision e and then vectorizes the polynomial into a vector in 12 poly((1))
The baseline method for realizable model (denoted

---

by (*)) needs further gap assumption of gap 2 d c to avoid the approximation error from escalating [2T]; note for small e this condition never holds but we include it in the table for the sake of comparison.
In rank polynomial case, our result O(dk) in simulator model can be found in Theo- rem 4.7 and our result O(dk) in online RL model can be found in Theorem 4.8 These results only require a realizability assumption. Efficient explorations are guaranteed by algebraic-geomenne arguments. In neural network model, our result (ppol((d) exp(k:) in simulator model can he found in Theorem 3.4 This result also only relies the realizability assumption. For stochastic transitions, our result O(poly(d. k)/²²) works for either policy complete or Bellman complete settings, as in Theorem 3.5 and Theorem respetttct The Oppolydd, k)) result for gap condition can be found in Theorem 3.8
1.2 Related Work
Linear Function Approximation. RL with linear function approximation has been widely studied
While these papers have proved efficient regret and sample complexity bounds, their analyses relied heavily on two techniques: they used the confidence ellipsoid to quantify the uncertainty, and they used the elliptical potential lemma to bound the total uncertainty (2. These two techniques were integral to their analyses but are so restrictive that they generally do not extend to nonlinear cases.
under various settings, including linear MDP and linear mixture MDP 89 85
Eluder Dimension. 162 [5] proposed eluder dimension, complexity measure of the function space, and proved regret and sample complexity bounds that scaled with the cluder dimension, for bandits and reinforcement learning 733 42). They also showed that the cluder dimension is small in several settings, including generalized linear models and LQR. However, as shown in [3] the eluder dimension could be exponentially large even with single ReLU neuron, which suggested the eluder dimension would face difficulty in dealing with neural network cases. The eluder dimension is only known to give non-trivial bounds for linear function classes and monotone functions of linear function classes. For structured polynomial classes, the eluder dimension simply embeds into an ambient linear space of dimension dP, where d is the dimension, and p the degree. This parallels the lower bounds in linearization neural tangent kernel (NTK) works [79 30 3] which show that linearization also incurs similarly large penalty of d" sample complexity, and more advanced algorithm design is need to circumvent linearization 6 9
22
83
26
58
29
57
34
75 [0].
Bellman Rank and Completeness. They used Bellman rank to measure the error of the function class under the Bellman operator and gave proved bounds in the term of it. Recently, [16] propose bilinear rank and encompass more function approximation models. However, it is hard to bound either the Bellman rank or the bilinear rank for neural nets. Therefore, their results are not known to include the neural network approximation setting, Another line of work shows that exponential sample complexity is unavoidable even with good representations [19 80 78), which implies the realizability assumption alone might be insufficient for function approximations.
440 70 studied RL with general function approximation.
2 Preliminaries
An episodic Markov Decision Process (MDP) is defined by the tuple M (S where S is the state space, A is the action set, H is the number of time steps in each episode, P is the transition kernel and r is the reward function. In each episode the agent starts at a fixed initial state 81 and at each time step h E [H] takes action an, receives reward r' (8h, (n) and transits to sh+1 ~ P(. an).
A deterministic policy π is length H sequence of functions π = {T S +
- Given policy n, we define the value function V (s) as the expected sum of reward under policy π starting from
'Piior work on neural function approximation has focused on neural tangent kernels, which would require (o/v(( to approximate lwyer network [I]
3

---

8//
S:
(s) = E
Σ (e ar)|sn =
and we define the Q function 0% (s, a) as the the expected sum of reward taking action a in state S/z = and then following
H (), = E rr(ss, - s,
Lemb
The Bellman operator Ta applied to Q-function Q++1 defined as follow
To Th a) == (s, a) + ( Qx+1(s(aa))
There exists an optimal policy x" that gives the optimal value function for all states, i.e. Vrr (8) = sup- (s) for all h E [H] and 8 E S. For notational simplicity we abbreviate V= as V and correspondingly Q as Q*. Therefore Q satisfies the following Bellman optimality equations for all E S. A and h E [M]:
(7 a) = (*%
The goal is to find policy æ that is e-optimal in the sense that (s1) VIT (s1) s, within a small number samples. We consider two query models of interacting with MDP:
In the simulator model 45, 67 the agent interacts with black-box that simulates the MDP, At each time step h E [M]. the agent can start at a state-action pair (s, a) and interact with the black box by executing some policy chosen by the agent.
In online RL, the agent can only start at the initial state and interact with the MDP by using policy and observing the rewards and the next states. In each episode k. the agent proposes a policy n based on all history up to episode h 1 and executes x to generate a single trajectory (sh, of J==1 with af x (s and s P. a.).
2.1 Function approximation
In reinforcement learning with value function approximation, the learner is given a function class
F = Fi x Fu, where Fh C {f S A + (0, 1]] is of candidate functions approximate Q'. The following assumption is commonly adopted in the literature [43, 17).
Assumption 2.1 (Realizability). Qi E Fr for all h E [H].
The function approximation equipped with feature mapping Φ A + {u Rd ||u||2 BB} that is known to the agent. We focus the continuous action setting (e.g. in control and robotics problems) and make the following regularity assumption on the feature function Assumption 2.2 (Bounded features). Assume o a) < B3, V(s,a) ESX.
Notation For any vector E Rdd let Trax == max;e[d] and Tmin = min Zt. Let s;(-) denote the i-th singular value, (.) denotes the minimum eigenvalue and 8max(-) denotes the maximum eigenvalue. The conditional number is defined by s(-) == Smax(-) (anxx-)/ssp 11/smi(() We use & to denote Kronecker product and o to denote Hadamard product. For given integer H. we use [H] denote the set 21, ........ H}. For function f x + 2), we use
f (g) e X f(x) = y]
to denote the preimage of y E 2). We use the shorthand x I (x 3) to indicate I S O (ar (yy)).
3 Neural Network Function Approximation
In this section we show sample-efficient algorithms with neural network function approximations. The function class of interest given in the following definition. More general neural network class is discussed in Appendix B.5

---

Definition 3.1 (Neural Network Function Class), We use FNN to denote the function class of a()(s,)) 8 x A + where f(x) (u, (WW))] R + two-layer neural network where a is ReLU, || || I Bw, v E {=1}", .I. 8: (W) (W) S X, Smax 5max(W)/ WW)/mmnn (W) S K. and k S d. Here Φ A x S + R is known feature map whose image contains a ball {u E R ||ul12 s ) with b d polylog(d)
We introduce the following completeness properties in the setting of value function approximations. Along with Assumption 2. they are commonly adopted in the literature.
Definition 3.2 (Policy complete). Given MDP M = (S, A. r, H), function class Fp : x A
R. h E [M] is called policy complete if for all and h E [H], Q% E Fh.
Definition 3.3 (Bellman complete). Given MDP M (S, A. Prr, H). function class Fr. S A
R. h E [ is called Bellman complete if for all h E [H] and Qs+1 E F1+1, Tn (Qu+1) E Fr.
3.1 Warmup: Realizable Q' with deterministic transition
We start by considering the case when the transition kemel is deterministic. In this case only Assump- neural network function approximations. Algorithm [ learns optimal policy from time step H to Suppose we have learned policies -h--:---.; RH at level h and they are exactly the optimal policies. We first explore features d(s), aj,) over a stan- dard Gaussian distribution, and if || [ 122 2 6, then we simply skip this trial. Recall that 56 2 d doloy log(d)) so with high probability (w.r. d) almost all feature samples will be explored. We next construct an estimate Q% of (s) af)) by collecting cumulative rewards using Mh+1,.... TH as the roll-out. Since the transition is deterministic, Qi = Q" (s) aj)) for all explored samples (s), af.) Recall that Q7, is a two-layer neural network, we can now recover its parameters in Line 12 exactly by invoking techniques in neural network optimization (see, e.g. [39 27 (00). Details of this step can be found in Appendix [B.]] where the method is mainly based on [90]. This means the reconstructed
tion 2.1 is required for the expressiveness
Qn in Line 13 is precisely Q", and the algorithm can thus find optimal policy ny in the h-th level.
Algorithm 1 Learning realizable Q" with deterministic transition
1: for h H,... do
2: Sample r/, i E [n]] from standard Gaussian (0, Ta)
3: for i [m] do
4:
if || || < 8 then Find (s), ag)))
5:
(zf)) and locate the state 8), in the generative model
(t) Pull action of, and use 1h TH as the roll-out collect rewards Th TH Construct estimation
(3)
6:
7:
( 2 +- hh + +TH
(4)
8:
else
Let Q4 + 0. end if
9:
11:
end for
Compute (vh, Wh) <- NRURAL.NTTREEOVRYY 13: Set (8, a) + "/ (WWn((Wn
14: Let (8) +- arg max Qn(s,a)
15:
end for
16:
Return TI...., TH
Theorem 3.4. (Informal) n 2 d poly(s, k, A, logd, Bw, BB, H), then with high probability Algorithm 7 learns the optimal policy.
The formal statement and complete proof deferred the Appendix B.I The main idea of exact neural network recovery can be summarized in the following. We first use method of moments to
'Here the & is chosen only for simplicity. In general this assumption can be relaxed to that the image of contains an arbitrary dense ball near the origin, since one can always rescale the feature mapping in the neural function approximation.
5

---

find a 'rough' parameter recovery. If this 'rough' recovery is sufficiently close to the true parameter, the empirical & loss function is locally strongly convex and there is unique global minimum. Then we can apply gradient descent to find this global minimum which is exactly the true parameter.
3.2 Policy complete neural function approximation
Now we consider general stochastic transitions. Difficulties arise this scenario due noises in the estimation of Q-functions. In the presence of model misspecification, these noises cause estimation errors to amplify through levels and require samples to be exponential in H. In this section, we show that neural network function approximation is still learnable, assuming the function class FNN policy complete with regard MDP M. Thus for all E II, we can denote Q7 a) = (o" (W. a)s.
Algorithm 2 Learn policy complete NN with simulator.
1: for h = H do
2:
Sample x/.
[ni] from standard Gaussian (0, Ta)
3:
for E [n] do
4:
if || S 6 then
5:
Find (s), a)) E (xf)) and locate the state s), in the generative model
6:
Pull action of, and use Th+l..... TH as the roll-out to collect rewards Th ..... ,
(8)
7:
Construct unbiased estimation of Q 2h+tinn8 (s ai)
Q - +
TH
8:
else
9:
Let Q4 t 0. end if
11:
end for
12: Compute (Eh, WT.) + NEURALLETTOOSSRRCCOVYYYY& ()) (xl}))
13: Set (8, c "i, (Wnn((s a))
Let (8) +- arg msx Qu(s,a)
15:
end for Return Mi...... TH
Algorithm 2 learns policy from level H, H - 1,...,, In level h, the algorithm has learned policy Th+1,.... TH that is only sub-optimal by (H h)e/Hl H. Then it explores features o(s, a) from (O0 Ia). The algorithm then queries (s, a) and uses learned policy Thth. TH as roll out to collect an unbiased estimate of the Q-function ",*,1=""*** (s, a). Since Q (s, a) FNN is a two-layer neural network, it can then be recovered from samples. Details of this step can be found in Appendix B.5] where the methods are mainly based on 190). The algorithm then reconstructs this Q-function and finds its optimal policy The
Theorem 3.5. (Informal) Fix c,t, if 2 2-. poly(k, k, Bw, B H, log(d/t)), then with probability at least Algorithm 2 returns an c-optimal policy
The formal statement and complete proof are deferred to Appendix B.2
Notice that unlike the case of Theorem 3.4 the sample complexity does not depend on X, thus avoiding the potential exponential
dependence in k.
The main idea of the proof is that at each time step neural network surrogate of Q" can be constructed by the policy already learned. Suppose we have learned Th+1..... JH in level h, then from policy obtain its
belongs to FNN and we interact with the simulator estimate Qn- If I|Q, - 2 Th 00 small, the optimistic planning based on Qn is not far from the optimal policy O #H Therefore the errors can decoupled into the errors in recovering 2% th .. and the suboptimality of "T 11... which depends on level + This reasoning can then be recursively performed to level H. and thus can bound the suboptimality of mi.
completeness Th++

---

3.3 Bellman complete neural function approximation
In addition to policy completeness, we show that neural network function approximation can also learn efficiently under the setting where the function class FNN is Bellman complete with regard to MDP M. Specifically, for Q++1 Fh+1, there are &Qh+ and W such that Ta (Q++1)(s,))
(u (W a(s,)))).
Algorithm
3 is similar to the algorithm in previous section. Suppose level h, the algorithm has constructed the Q-function Qn+ (s, a) = -ih+1 o WWtii((s ((8,)) a)) that (H - hiee H-llose to the optimal +1+ It then recovers weights U/. Wi. from Ta (Qn+))(s a) o using unbiased estimates ra af))) + V The Q-function Qn a) v/ (WWn((s reconstructed from weights Uh W₁ is thus (H - h + 1)c/ H-llose to the Qi.-
Algorithm 3 Learn Bellman complete NN with simulator.
1:
for h H, do
2: Sample x/, E [na]
from standard Gaussian (0, Ia)
3:
for i [n] do
4:
if [x)] | S 6 then
5:
Find (s), (i)) E (xf, and locate the state 8i in the generative model
6:
Pull action oj, and and observe rh (s/, a, s/
7:
Construct unbiased estimation of Ta (Qn+1) o7))
S + (s(s a + V
8:
else
9:
Let Q4 < O. end
11:
end for
12:
Compute (ER, Wh. + NEURALLETNNOS ii [n]])
Set Qn (8, 4 1/ (WWnlWW u)) and Vn max.ed Qn(s,a)
13:
Let TA (8) +- arg max (s)
15:
end for
Return Ni....,
Theorem 3.6. (Informal) Fix e,t, if 2 d poly(K, k, Bw, B,, H, log(d/t)), then with probability at least Algorithm returns an e-optimal policy n.
Due to Bellman completeness, the error of estimation Qn can be controlled recursively. In fact, we show ||Ê, Q'' al is small by induction. The formal statement and detailed proof deferred to Appendix [33] Similar to Theorem 3.5 the sample complexity does not explicitly depend on X, thus avoiding potentially exponential dependence in k.
3.4 Realizable Q" with optimality gap
In this section we consider MDPs where there is non-zero gap between the optimal policy and any other ones. This concept, known as optimality gap, widely used reinforcement learning and bandit literature (20 11 21
Definition 3.7. The optimality gap is defined as
inf (s.a))VVV))
V'(s)-Q'(sx.
We show that in the presence positive optimality gap. there exists algorithm that can learn the optimal policy with polynomial samples even without the completeness assumptions. Intuitively, this is because one only needs to recover the neural network up to precision p/4 in order to make sure the greedy policy identical to the optimal one. The formal statement and proof are deferred to Appendix B.4

---

Theorem 3.8. (Informal) Fix t E if o² poly(K, k, Bw BB, H, log(d/t)), then with probability at least 1 - t there exists an algorithm that returns the optimal policy x².
Remark 3.9. In all aforementioned methods, there are two key components that allow efficient learning. First, the exploration conducted in a way that guarantees an lox recovery of candidate functions. By Ese recovery we mean the algorithm recovers candidate Q-function in this class deviating from the target function Q" by at most e uniformly for all state-action pairs in the domain of interest. This notion of learning guarantee has received study in active learning 133 46 and recently gain interest in contextual bandits [25j. Second, the agent constructs unbiased estimators of certuin approximations to Q' that lie in the neural function approximation class. This allows the recovery error to decouple linearly across time steps, which is made possible in several well bell-posed MDP instances, such deterministic MDPs, MDPs with completeness assumptions, and MDPs with gap conditions. In principle, we note that provably efficient RL algorithms with general function approximation is possible as long as the above two components are present. We will see in the next section another example of learning RL. with highly non-convex cnnccovexfunction approximations, where the function class of interest, admissible polynomial families, also allows for exploration schemes to achieve loo recovery.
4 Polynomial Realizability
In this section, we study the sample complexity to learn deterministic MDPs under polynomial realizability. We identify sufficient and necessary conditions for efficiently learning the MDPs for two different settings the generative model setting and the online RL setting. Specifically, we show that if the image of the feature map @n (5%, αλ) satisfies some positive measure conditions, then by random exploring, we can identify the optimal policy with samples linear in the algebraic dimension of the underlying polynomial class. We also provide a lower bound example showing the separation between the two settings.
Next, we introduce the notion of Admissible Polynomial Families, which the families of structured polynomials that enable efficient learning.
Definition 4.1 (Admissible Polynomial Families). For x E Rd, denote ã = [1, Let == {T x E ].d]. For any algebraic variety V, we define Fy == (fe(z) = (0, (0))
E V} as
the polynomial family parameterized by θ E V. We say Fy is admissible" w.r.t. X, if for any e E V. dim(A' n {X X (X, 0}}) < dim(X'= = d. We define the dimension D of the family to be the dimension of V.
The following theorem shows that to learn an admissible polynomial family, the sample complexity only scales with the algebraic dimension of the polynomial family.
Theorem 4.2 ( (36)). Consider the polynomial family F&v of dimension D. For 2 2D, there exists a Lebesgue- measure zero set N Rd x ... Rd. such that (a1,.... .In. & for any yt, there is unique f (or no such f) to the system of equations ys = f(r) Fv.
We give two important examples of admissible polynomial families with low dimension.
Example 4.3. (Low-rank Polynomial of rank k) The function f Fy a polynomial with k terms, that is
F(x) = Σ Ao (0,,
where p = m.. The dimension of this family is upper bounded by D dk. Neural network with monomial/polynomial activation functions are low-rank polynomials.
Example 4.4. The function f E Fy of the form f(x) = q(Ux),, where E R and q is a degree polynomial. The polynomial and matrix U are unknown. The dimension of this family is upper bounded by D < d(k + I)P
Next, we introduce the notion of positive measure.
'Admissible means the dimension of X decreases by one when there is an additional linear constraint
X) =
8

---

Definition 4.5, We say a measurable set E E R is of positive measure if ({E) >> O, where ju is the standard Lebesgue measure on R.
If measurable set E satisfies μ(E) > O, then there exists a procedure to draw samples from E, such that for any N C R of Lebesguee-masuur zero, the probability that the sample falls in N is zero. In fact, the sampling probability can be given by P ta E E). The intuition behind its definition that for all admissible polynomial families, the of ( , .nn with "redundant information" about learning the parameter θ is of Lebesgue-measuee zero. Therefore, positive measure set allows you to query randomly and avoids getting coherent measurements.
Next two theorems identify the sufficent conditions for efficiently learning deterministic MDPs under polynomial realizability. Specifically, under online RL setting, require the strong assumption that the set {Ør (s, a) E A} is of positive measure for all h E [H] and all 8 E S, while under generative model setting, we only require the union set U.es (Øx (s, a)Ia A} be of positive measure for all h E [H] The algorithms for solving the both cases are summarized in Algorithms and
Assumption 4.6 (Polynomial Realizability). For all [H]. Qj (8), az), viewed as the function of Φn (5h, an), lies in some admissible polynomial family Fv,, with dimension bounded by D.
Theorem 4.7. For the generative model setting, assume that the set (sn, a) s E S, E A} is of positive measure at any level h. Under the polynomial realizability, Algorithm allostt surely learns the optimal policy x* with at most = 2DH samples.
Theorem 4.8. For the online RL setting, assume that (0)(s, a) l E AA is of positive measure for every state s at every level h. Under polynomial realizability, within T = 2DH episodes, Algorithm 5 learns the optimal policy x² almost surely.
Algorithm 4 Dynamic programming under generative model settings
1: for h 1 do
2: Sample 2D points {on(s)) (6) , a )22 according to (r E Ex) where Ey as) s S,a E A}.
(8)
3: Query the generative model with acteon pair (5% ah
level h for i 1..... 2D,
and observe the next state 8/ and reward rh
(6) 4: Solve for Q7, with the 2D equations Q7 0 = =r ( Vitt (3)
5:
Set (s) arg max, Q7 (8, a) and (s) max. (s.
6: end for
7: Output x²*
Algorithm 5 Dynamic programming under online RL settings
1: for h = H,.... ..... do
2:
Fix any action sequence a1, ... Q4-1- Play a1,-.. _a--1 for the first h - levels and reach state Sh- Sample 2D points
3:
(dn an (1)
(1) ) according I. (-1z Ex) where En {on a) e A}.
(11) Play an at sh for = 1,..., .D,. and observe the next state $) and reward (0)
4:
5:
Solve for Q7, with the 2D equations (%
(6) ()) =r + V (2))).
6: Set (s) = arg max, Q7 (8, a) and Vî (8) max, Q (8, a).
7: end for
8: Output -
We remark that our Theorem 4.8 for learning MDPs under the online RL setting relies very strong assumption that allows the learner to explore randomly for any state. However, this assumption necessary in some sense, is suggested by our lower bound example in the next subsection.
4.1 Necessity of Generic Feature Maps in Online RL
In this section, we consider lower bounds for learning deterministic MDPs with polynomial realizable Q" under online RL setting. Our goal is to show that in the online setting the generic assumption

---

the feature maps d% (s.-) is necessary. On the contrary, under the generative model setting one can efficiently learn the MDPs without such strong assumption, since at every level h the we can set the state arbitrarily.
MDP construction We briefty introduce the intuition of our construction. Consider family of MDPs with only two states S = {Suo Stad we set the feature map Φn such that, for the good state Sgodd it allows the learner to explore randomly, i.e., { (Soodd a) a A} is of postive measure.
However, for the bad state Smad. all actions are mapped to some restricted set, which forbids random exploration, i.e., {oh, (Sted a) | a E A} is measure zero. This is illustrated in Figure [
Specifically, at least (ddd)) actions are needed identify the groud-truth polynomial of Q7, for Stad- while (d) actions suffice for Sgood.
The transition P, is constructed as PA, (Sbad 8, a) 1 for all S, E A, which means it is impossible for the online scenarios to reach the good state for > 1.
Φh (S good AA)
state
action set
S good
A
Φ
X
Φh (Shad, A)
S
An illustration of the hard case for deterministic MDPs with polynomial realizable Q'. The image of the feature map On at Sgood is of positive measure, while the image on, at Spad is not. This makes difficult to learn under the online RL setting.
Figure I:
Theorem 4.9. There exists family of MDPs satisfying Assumption 4.6 such that the set (oh,s, E S, E A] is of positive measure at any level h, but for all there is some Soad E such that (dr (Sbad, a) | E A} is measure zero. Under the online RL setting, any algorithm needs to play at least (2dP) episodes to identify the optimal policy. On the contrary, under the generative model setting, only (d) H samples are needed.
5
Conclusions
In this paper, we consider neural network and polynomial function approximations in the simulator and online settings. To our knowledge, this is the first paper that shows sample-efficien reinforcement learning is possible with neural function approximation. Our results substantially improve upon what can be achieved with existing results that primarily rely on embedding neural networks into linear function classes. The analysis reveals that for function approximations that allows for efficient lo recovery, such as two layer neural networks and admissible polynomial families, reinforcement learning can be reduced parameter recovery problems, as well-studied in theories for deep learning. phase retrieval, and etc. Our method can also be potentially extended to handle three-layer and deeper neural networks, with advanced tools 23 24].
Our results for polynomial activation require deterministic transitions, since we cannot handle how noise propagates in solving polynomial equations. We leave to future work an in-depth study of the stability of roots of polynomial systems with noise, which is a fundamental mathematical problem and even unsolved for homogeneous polynomials. In particular, noisy tensor decomposition approaches combined with zeroth-orde order optimization may allow for stochastic transitions [36].
In the online RL setting, assumption on the feature mapping. We leave to future work identifying more realistic and natural conditions which permit efficient learning in the online RL setting.
only show efficient learning under very strong yet necessary
Finally, in future work, we hope to consider deep neural networks where parameter recovery or fox error is unattainable, and deep reinforcement learning with representation learning [84 [5]
10

---

Acknowledgements
JDL acknowledges support of the ARO under MURI Award N911NF-11-1-030 the Sloan Research Fellowship, NSF CCF 2002272, and an ONR Young Investigator Award. QL is supported by NSF 2030859 and the Computing Research Association for the CiFellows Project. SK acknowledges funding from the NSF Award CCF-1703574 and the ONR award N00014-18-1-2247,
References
[1] Yasin Abbasi-Yadkorf Nevena Lazic, Csaba Szepesvari, and Gellert Weisz. Exploration- enhanced POLITEX. arXiv preprint arXiv:1908. 10479, 2019.
[2] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[3] Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprini arXiv: 1905. /0337, 2019.
[4] Zeyuan Allen-Zhu, Yuanzhi Li. and Zhao Song. A convergence theory for deep learning via over- paeeraaaatteiiziiinnn. In International Conference on Machine Learning (ICML), pages 242 252, 2019.
[5] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference Machine Learning, pages 263-272, 2017.
[6] Yu Bai and Jason D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations, 2020.
[7] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, and Chris Hesse. Dota with large scale deep reinforcement learning. arXiv preprint arXiv: 1tt.::191.0068000 2019.
[8] Jacek Bochnak, Michel Coste, and Marie-Françon Roy. Real algebraic geometry, volume 36. Springer Science & Business Media, 2013.
[9] Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. Neural Information Processing Systems (NeurIPS), 2020.
[10] Alex Damian, Tengyu Ma, and Jason Lee. Label noise sgd provably prefers flat global minimiz- ers. arXiv preprint arXiv:2 106.063300 2021.
[11] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. On oracle-efficient PAC-RL with rich observations. In Advances Neural Information Processing Systems, 2018.
[12] Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Vn-regret for learning in Markov decision processes with function approximation and low Bellman rank. In Conference on Learning Theory, pages 1557- PMLR, 2020.
[13] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. arXiv preprint 1rXiv:2102.041C0 2021.
[14] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), pages 1675-1685 PMLR, 2019.
[15] Simon $ Du, Wei Hu, Sham Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002. 09434, 2020.

---

[16] Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: structural framework for provable generalization in arXiv preprint arXiv:2103.10897 2021.
[17] Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: structural framework for provable generalization in RL. arXiv preprini arXiv:2 10897, 2021.
[18] Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
[19] Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
[20] Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RI. with rich observations via latent state decoding. In International Conference Machine Learning, pages 1665-1674, 2019.
[21] Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic Q-learning with function approximation deterministic systems: Tight bounds on approximation error and sample complexity. Advances in Neural Information Processing Systems, 2020.
[22] Cong Fang, Jason D Lee, Pengkun Yang, and Tong Zhang. Modeling from features: mean-field framework for over-parameterized deep neural networks. arXiv preprint arXiv:2007.01452 2020.
[23] Massimo Fornasier, Timo Klock, and Michael Rauchensteiner. Robust and resource efficient identification two hidden layer neural networks. arXiv preprint 1017.0990700445 2019.
[24] Massimo Fornasier, Jan Vybíral, and Ingrid Daubechies. Robust and resource efficient iden- tification of shallow neural networks by fewest samples. arXiv preprint wrXiv:1804001522 2019.
[25] Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E. Schapire. Practical contextual bandits with regression oracles. Proceedings of the 35th International Conference on Machine Learning, 2018
[26] Ruiqi Gao, Tianle Cai, Haochuan Li, Liwei Wang, Cho-Jui Hsieh, and Jason D Lee. Convergence of adversarial training in overparametrized networks. Neural Information Processing Systems (NeurIPS), 2019.
[27] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. arXiv preprint #xXiv:771.0000011 2017.
[28] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-laye neural networks with landscape design. In International Conference on Learning Representations (ICLR), 2018.
[29] Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. International Conference Learning Representations (ICLR), 2018.
[30] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks high dimension. arXiv preprint arXiv: 12191, 2019.
[31] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Lincarized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-10551 2021.
[32] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
[33] Steve Hanneke. Active learning for cost-sensitive classification. Foundations and T in Machine Learning, 7(2-3):131-30) 2014.
[34] Jeff 7.. HaoChen, Colin Wei, Jason D. Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006.0886 2020.
12

---

[35] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger, Deep reinforcement learning that matters. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[36] Baihe Huang, Kaixuan Huang, Sham M Kakade, Jason D Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient- based algorithms for non-concave bandit optimization. arXiv preprint arXiv:2107.04578 2021.
[37] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems (NeurIPS), pages 8571-8580, 2018.
[38] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal bounds for reinforcement learning. Journal of Machine Learning Research, 11(App):1533-1600 2010.
[39] Majid Janzamin, Hanie Sedghi, and Anankumar Anima. Beating the perils of nonconvexity; Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv:1506.08473. 2015.
[40] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning, pages 1704-1713, 2017.
[41] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learnin provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873 2018.
[42] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00875. 2021.
[43] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137- 2143. PMLR, 2020.
[44] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143, 2020.
[45] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of College London, 2003.
[46] Akshay Krishnamurthy, Alckh Agarwal, Tzu-Kuo Huang, Hal Daume III, and John Lang- ford. Active learning for cost-sensitive classification. Proceedings of the 34th International Conference on Machine Learning, 2017.
[47] Volodymyr Kuleshov, Arun Chaganty, and Percy Liang. Tensor factorization via matrix factor- ization. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics (AISTATS), page 507-516, 2015.
[48] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
[49] Gene Li, Pritish Kamath, Dylan J. Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprint arXiv: 2xXiv:2004.060 104.06970, 2021.
[50] Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: (50.002999.9 2015.
[51] Boyi Liu, Qi Cai. Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy optimization attains globally optimal policy, arXiv preprint arXiv: 1906. 2019.
[52] Dhruv Malik, Aldo Pacchiano, Vishwak Srinivasan, and Yuanzhi Li. Sample efficient rein- forcement learning in continuous state spaces: perspective beyond linearity. arXiv preprint arXiv:2106.07814, 2021.
13

---

[53] James S. Milne. Algebraic geometry (v6.02), 2017. Available at www.jmilne.orgmmaii
[54] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan- Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement Jeannnnnnnntttttennene reinforcement learning, arXiv preprint 13Xiv 2013.
[55] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv:13/2.5602, 2013.
[56] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-55)) -13, 2017.
[57] Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D Lee, Nathan Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. Neural Information Processing Systems (NewrIPS), 2020.
[58] Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee. Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference on Machine Learning, pages 4683-4692 PMLR, 2019.
[59] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[60] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. Journal of Machine Leurning Research, 16(6):155-186, 2015.
[61] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1-2):111-533 2015.
[62] Dan Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pages 2256-2264, 2013,
[63] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Advances in Neural Information Processing Systems, pages 14433-14443, 2019.
complexity of optimistic [64] Daniel Russo and Benjamin Van Roy. Eluder dimension and the compleco exploration. In Advances in Neural Information Processing Systems, 2013.
[65] Igor R Shafarevich. Basic Algebraic Geometry 1: Varieties in Projective Space. Springer Science & Business Media, 2013.
[66] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03299 2016.
[67] Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with generative model. 2018.
arXiv preprint arXiv:1806.011
[68] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, and Marc Lanctot. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
[69] Alexander L Strehl, Lihong Li. Eric Wiewiora, John Langford, and Michael L Littman. PAC model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pages 881 181-888, ACM, 2006.
[70] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model- based RI. in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference Learning Theory, pages 2898-2933 2019.
14

---

[71] Richard S Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[72] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01 150, 2020.
[73] Ruosong Wang, Ruslan Salakhutdinov, and Lin Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005.10804 2020.
[74] Ruosong Wang, Ruslan Salakhutdinov, and Lin Yang. Provably efficient reinforcement learning with general value function approximation. Advances in Neural Information Processing Systems, 2020.
[75] Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over-parameterizzed tensor decomposition. Neural Information Processing Systems (NeurIPS), 2020.
[76] Yang Wang and Zhiqiang Xu. Generalized phase retrieval: measurement number, matrix recovery and beyond. Applied and Computational Harmonic Analysis, 47(2):423 446, 2019.
[77] Yining Wang, Ruosong Wang, Simon S. Du, and Akshay Krishnamurthy. Optimism in rein- forcement learning with generalized linear function approximation. International Conference on Learning Representations, 2021.
[78] Yuanhao Wang, Ruosong Wang. and Sham M. Kakade. An exponential lower bound for linearly-realizable mdps with constant suboptimality gap. arXiv preprint arXiv:2103.12690, 2021.
[79] Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances Neural Information Processing Systems, pages 9709-9721, 2019.
[80] Gellert Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly- optimal action-value functions. arXiv preprint arXiv:2010.01374, 2020.
[81] Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. In Advances in Neural Information Processing Systems, pages 3021- 3029, 2013.
[82] Zheng Wen and Benjamin Van Roy. Efficient reinforcement Icarning in deterministic systems with value function generalization. Math. Oper. Res., 42(3):762- 2017.
[83] Blake Woodworth, Suriya Genesekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. In Conference on Learning Theory (COLT), 2019.
[84] Jiaqi Yang, Wei Hu, Jason Lee, and Simon S Du, Provable benefits of representation learning in linear bandits. arXiv preprint arXiv:2010.0633 2020.
[85] Lin Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. International Conference on Machine Learning, 2020.
[86] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient reinforcement learning with kemnel and neural function approximations. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 13903-13916. Curran Associates, Inc., 2020.
[87] Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for under- standing neural networks. arXiv preprint arXiv: Na0:::994000000 2019.
[88] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
15

---

[89] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, 2020.
[90] Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. Proceedings of the Thirty-fourth International Conference on Machine Learning (ICML), 70, 2017.
[91] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. Proceedings of the 37th International Conference on Machine Learning, 2020.
[92] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08880 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our abstract and introduction accurately reflect our main contribution.
(b) Did you describe the limitations of your work? [Yes] In the Preliminary section clearly state the settings we considered and when our results apply.
(c) Did you discuss any potential negative societal impacts your work? [No] Our work is theoretical and generally will not have negative social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes] The assump- tions are clearly included in every theorem or lemma.
(b) Did you include complete proofs of all theoretical results? [Ye]] All the proofs can be found in the appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "zzy8VqUUBIq", "reviewer": "Reviewer_AzY2", "summary": "This paper focuses on analyzing sampling efficiency of nonlinear reinforcement learning with neural network approximations of the $Q$ function. It reduces the sampling complexity from $O(d^{\\text{poly}(1/\\epsilon)})$ to $O(\\text{poly}(d) \\exp(k))$ where $k$ is the width of the hidden layer of a two-layer fully connected neural network. The idea is described accurately and the paper is overall well written. ", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers both neural network and polynomial approximations of the $Q$ function. Since polynomial approximation does not scale well with the dimensionality, the analysis on the sampling complexity of neural network-based $Q$ function approximation is more interesting. In the neural network setting, the RL algorithms, i.e., Algorithm 1, 2 and 3 are quite standard RL algorithms, so the novelty does not lie in algorithm development. In my opinion, the main contributions of this paper should be the proof of Theorem 4.4, 4.5 and 4.6. However, the main idea of the proofs are not included in the main paper. \n\nWhen digging into Appendix, it becomes apparent that the key improvement of the sampling complexity are based on the results in \n\nKai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. Proceedings of the Thirty-fourth International Conference on Machine Learning (ICML), 70, 2017.\n\nFor example, the proof of Theorem 4.4 is given in Appendix as Theorem A.1. In the proof of Theorem A.1, the key step is the use of Theorem A.14. When looking at Theorem A.14, the proof is provided in Appendix A.4.2 from Line 715 to Line 725. The main ingredient of the ten-line proof is the used of Lemma D.3, Lemma D.11 and Lemma D.16 in [Zhong et al. 2017]. Similar strategy is used to prove Theorem 4.5 and 4.6. Therefore, I think Theorem 4.4 - 4.6 are just simple extension of the results in [Zhong et al. 2017] to the RL setting, so the theoretical contribution of this paper is not significant.\n\nOn the other hand, I strongly disagree with the way the theoretical results are presented, because I don't think the importance of [Zhong et al. 2017] is explicitly and sufficiently acknowledged in the main text. In fact, the paper [Zhong et al. 2017] is only cited twice in the main text. Even though it is mentioned in Line 49 that [Zhong et al. 2017] is one of the main technique used in this paper, but it is not completely not clear that the complexity of NN-based approximation in Table 1 comes from the neural network recovery result in [Zhong et al. 2017]. \n\nAdditionally, there is a lack of justification of the appropriateness of Assumption 3.1 and 3.2. It looks like the assumptions were made on purpose so that the results in [Zhong et al. 2017] can be used. It would be helpful if the authors can provide some RL examples that satisfy the assumptions.  \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "tW9N4qGxPw", "reviewer": "Reviewer_92NY", "summary": "This paper studies sample efficient RL with two-layer neural network function approximation with a generative model. In particular, they prove that they can learn an optimal policy with poly samples with only realizability in deterministic MDP, and that the sample complexity for learning a near-optimal policy in stochastic MDPs is in an order of $\\epsilon^{-2}$ in two cases: policy completeness assumption and Bellman completeness assumption. The algorithms they use are based on simple (non-optimistic) value regression. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strong points**:\n- Sample efficient RL with deep neural network function approximation is an important and timely topic \n- The sample complexity with neural network function approximation does not suffer from the curse of dimensionality  (i.e., sample efficiency is possible in RL with neural network function approximation)\n\n**Weak points**: \n- The main guarantees are direct results of the lemmas of the exact network recovery from noisy/noiseless data [Zhong et al, 2017]. What is a technical innovation in this paper?  \n- I think learning with a simulator (a generative model) is rather not a practical setting as in practice, data is sequentially obtained from the beginning of an episode. Can the result with neural network function approximation here be extended to such online setting? Currently, the paper has the result in an online setting with polynomial realizability. \n- The paper claims that “this is the first paper that shows sample efficient RL is possible with neural net function approximation”. It does not seem so. For example, Yang et al., 2020 “On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces” already obtains a sample efficient RL in online setting with neural function approximation using optimism. Without optimism, Pan Xu and Quanquan Gu “A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation” obtains sample efficiency of Q-learning with neural network function approximation in online setting with Markovian data.  \n\n**Minor comments**\n- The abstract only mentions neural network function approximation but in the main paper, it also considers polynomial function. \n- Line 139: typo, \\kappa = s_{\\max} / s_{\\min}\n- Line 93: Missing literature, I think you should consider adding Jin et al, 2021, “Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms”, as you discuss sample efficient RL with function approximation. \n\n**Questions for authors**:\n- What is a rationale for the sample efficiency of simple value regression without optimism in your proposed algorithms Alg 1,2,3? What is the key to such a simple algorithm that can lead to the obtained sample efficiency? Probably due to the generative model that we can obtain good coverage of the state-action space that does not require intricate exploration such as optimism, but I would like to hear the authors discuss more on this. \n- More discussion on how mild are the policy-complete and Bellman-complete assumptions. \n\n------------------ POST-REBUTTAL----------------------\n\nThank you the authors for providing a detailed response to my concerns. After reading the authors' responses and other reviews, I am happy to raise my initial score to 6 for the following reasons: the paper has made a solid contribution in showing the feasibility of sample efficient RL with non-linear neural network function approximation in the generative setting. Technically, though the paper relies heaviely on the parameter recovery theorem in non-linear neural networks and an extension to RL setting in the generative model is quite natural and straightforward, the result in the paper does complement the literature of RL with non-linear function approximation and can be helpful to the community. My initial score was due to mainly two issues: the technical contribution of the paper and the result's significance. Though there is no significant technical contribution as in my initial review, I misinterpreted the paper result when comparing it with the literature RL with overparameterized neural networks. I encourage the authors to take the discussion into the revision.   \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have partly addressed the limitations of their work and fully addressed the societal impact of their work. ", "review_text": "", "extra_scores": {"ethical_concerns": "No concern. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Hhl9F8pO3Fq", "reviewer": "Reviewer_qeUq", "summary": "This paper studies reinforcement learning with a 1-hidden layer neural network and low-rank polynomial function approximation schemes. \n\nUnder mostly standard assumptions about realizability, completness etc, they provide algorithms mainly focusing on sample complexity in cases when there is access to a perfect generative model of the transitions and in the fully online setting, where planning is not possible in episodic reinforcement learning.\n\nThey improve upon the sample complexity with respect to existing baselines for the respective function approximation schemes.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main questions and concerns are as follows:\n\n1)The baseline considered in Du et al 2020c, considers a weaker form of realizability assumption, where they can find the best function approximation for $Q^*$ in the given class upto a error $\\delta > 0$. Now, since the class here are 1-layer neural networks or low-rank polynomials, there exists simple deterministic transitions that have complex Q functions (i.e, when using shallow networks this requires exponential width), (see Dong et al. 2020). Is it possible to comment on the tradeoff due to expressivity errors?\n\n2) Could the authors clarify on the dependence on H, more explicitly if possible?\n\n3) Theorem 5.2 states that there is a unique solution to the system of equations. Is there an efficient algorithm for it? Since it is used in Algorithms 4 and 5.\n\n4) A large portion of the results in the neural network recovery is from Zhong et al. 2017, as a clarification is assumption A11 satisfied by ReLu activation?\n\nAdditional Reference:\nDong, Kefan, et al. \"On the expressivity of neural networks for deep reinforcement learning.\" International Conference on Machine Learning. PMLR, 2020.\n\nAfter Rebuttal:\n\n I raise my score after the authors made the necessary clarifications.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "HeLJ1jT8a5i", "reviewer": "Reviewer_3peY", "summary": "The paper considers RL with neural function approximation, extending significantly previous works that only focuses on linear feature approximation. In particular, the authors propose (1) an efficient algorithm using two-layer NNs in a generative model assuming completeness, and (2) an efficient algorithm with two-layer NNs but only assuming realizability.\n\nThe results significantly extends prior research on linear methods, or methods with bounded eluder dimension.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Originality: the paper is one of the few papers that consider reinforcement learning in (the more general) neural network approximation regime. Related works are clearly cited and ~the work has made significant contributions different from existing research~. Please see the updated comment. I realized I neglected the result's reliance on [1] and have adjusted my score accordingly.\n\n- Quality: the theorems and results in the paper are well justified. \n\n- Clarity: proofs are clear and well-written.\n\n- Significance: being one of the first papers studying neural network approximation, the paper could pave way for future research in this area. ~The results are technically sound and significant.~ See updated comment.\n\n[1] Zhong, Kai, et al. \"Recovery guarantees for one-hidden-layer neural networks.\" International conference on machine learning. PMLR, 2017", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and scopes of the theoretical results are clearly stated. The strong assumptions required are reemphasized in the conclusion and directions for future research are proposed.\n\nNo apparent negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has received a lot of discussion.
In the end, the reviewers agree that the paper contributes to the literature and should be accepted.
There are a number of useful comments that the authors should take into account when preparing the camera ready version of the paper.
Decision: Accept (Poster)