Understanding Deep Neural Function Approximation in Reinforcement Learning via $\epsilon$-Greedy Exploration
Authors: Fanghui Liu
Luca Viano
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep reinforcement learning
function approximation
$\epsilon$-Greedy Exploration

Abstract: This paper provides a theoretical study of deep neural function approximation in reinforcement learning (RL) with the $\epsilon$-greedy exploration under the online setting. This problem setting is motivated by the successful deep Q-networks (DQN) framework that falls in this regime. In this work, we provide an initial attempt on theoretical understanding deep RL from the perspective of function class and neural networks architectures (e.g., width and depth) beyond the ``linear'' regime. To be specific, we focus on the value based algorithm with the $\epsilon$-greedy exploration via deep (and two-layer) neural networks endowed by Besov (and Barron) function spaces, respectively, which aims at approximating an $\alpha$-smooth Q-function in a $d$-dimensional feature space. We prove that, with $T$ episodes, scaling the width $m = \widetilde{\mathcal{O}}(T^{\frac{d}{2\alpha + d}})$ and the depth $L=\mathcal{O}(\log T)$ of the neural network for deep RL is sufficient for learning with sublinear regret in Besov spaces. Moreover, for a two layer neural network endowed by the Barron space, scaling the width $\Omega(\sqrt{T})$ is sufficient. To achieve this, the key issue in our analysis is how to estimate the temporal difference error under deep neural function approximation as the $\epsilon$-greedy exploration is not enough to ensure "optimism". Our analysis reformulates the temporal difference error in an $L^2(\mathrm{d}\mu)$-integrable space over a certain averaged measure $\mu$, and transforms it to a generalization problem under the non-iid setting. This might have its own interest in RL theory for better understanding $\epsilon$-greedy exploration in deep RL.

Understanding Deep Neural Function Approximation in Reinforcement Learning via e-Greedy Exploration
Fanghui Luca Viano, Volkan Cevher Laboratory for Information and Inference Systems
École Polytechnique Fédérale de Lausanne (EPFL), Switzerland (first). [last]
Abstract
This paper provides a theoretical study of deep neural function approximation reinforcement learning (RL) with the e-greedy exploration under the online setting. This problem setting motivated by successful deep Q-networks (DQN) framework that falls in this regime. In this work, we provide an initial attempt on theoretical understanding deep RL from the perspective of function class and neural networks architectures (c.g., width and depth) beyond the "linear" regime. To specific, we focus on the value based algorithm with the e-greedy exploration via deep (and two-layer) neural networks endowed by Besov (and Barron) function spaces, respectively, which aims at approximating an a-smooth Q-function in a d-dimensional feature space. We prove that, with T episodes, scaling the width m = ) and the depth = Oloo T' the neural network for deep RL is sufficient for learning with sublinear regret in Besov spaces. Moreover, for a layer neural network endowed by the Barron space, scaling the width 12( (2(TT) is sufficient. To achieve this, the key issue our analysis is how to estimate the temporal difference error under deep neural function approximation exploration is not enough to ensure "optimism". Our analysis reformulates the temporal difference error in an T.2 (dnteinteeaa space
the e-greedy
certain averaged measure 14, and transforms it to generalization problem under the non-iid setting. This might have its own interest in RL theory for better understanding e-greedy exploration in deep RL.
Introduction
Efficient reinforcement learning (RL) under the large (or even infinite) state space and action space setting increasingly important and relevant challenge 32. One of the first successful approaches towards this problem is the deep Q-network (DQN) 4. 5 framework, which deploys powerful nonlinear function approximation techniques via Deep Neural Networks (DNNs) [6) to concisely approximate state and action spaces. Despite its impressive practical success, there is still a gap between practical uses and theoretical understanding on deep RL with regard the function class and the employed e-greedy policy.
In the perspective of function class, many theoretical works center around linear function approxima- tion 778 and linear mixtures IO]. Existing non-linear function approximation results on RL are largely based neural tangent kernel (NTK) [1] [2), Bellman rank [13) [4), and Eluder dimension
[5] 16, [7]. Nevertheless, these approaches fail truly capturing the highly non-linear properties of
deep RL. For example, NTK (or lazy training
(18) essentially works in "linear" regime [19 20 21],
and can not efficiently learn even a single ReLU neuron 22 24 as it requires Q( ") samples
"Corresoondence to: Fanghui Liu <fanghui liu@epfl. ch> and Luca Vianocluca. vianoRepf1.cht ch>.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to achieve E approximation error, where d is the (original) or transformed feature dimension input; the Bellman rank normally difficult to be estimated for neural networks as suggested by [25]; the Eluder dimension is at least in an exponential order [26 27 even for two-layer neural networks. The above general function approximation schemes appear difficult to fully demonstrate the success of practical deep RL both theoretically and empirically.
In the perspective of exploration schemes, DQN is directly equipped with the e-greedy policy instead of confidence-
based scheme that are commonly used in RL theory. The e-greedy exploration theoretically demonstrated to have exponential sample complexity in the worst case [28] but is still popular in practical deep RL due to its simple implementation. In this case, theoretical analyses of e-greedy in deep RL are still required. Besides, to ensure sublinear regret, under the NTK regime. the width of neural networks is required to be m = (2(T1s) [12, where T is the number of episodes. This does not match deep RI. in practice with small width/depth under large episodes 29].
To bridge the large theory-practice gap, we study the value iteration algorithm with deep neural function approximation and the e-greedy policy under the online setting, which broadly captures the key features of DQN. Our analysis framework is based on DNNs (as well as two-layer neural networks) where the target Q function lies in the Besov space [30] or the Barron space [II, respectively. These function classes can fully capture the properties of Q-functions, e.g., smoothness by neural networks. Our results demonstrate that the sublinear regret can be achieved for deep neural function approximation under the e-greedy exploration with reasonably finite width and depth in practice. Besides, the relationship between the problem- -eepeddee smoothness of Q-function and regret bounds is also developed. These results could also motivate practitioners to consider different architectures of implementations of deep RL.
1.1 Technical challenges and contributions
Most previous RL theory results on function approximation in the online setting work with "optimism in the face of uncertainty" principle for exploration, leading to series of upper confidence bound (UCB)-type algorithms to ensure the temporal difference (TD) error smaller than zero.
Conceptually, optimism is sometimes too aggressive and UCB-style algorithms can suffer exponential sample complexity even for nonlinear bandits (27). Technically, UCB-type algorithms in linear/kernel function approximation 77 [2 32) depend on known feature mapping or the NTK kernel, which appears invalid for deep neural function approximation beyond the "linear" regime. This is because, the used confidence ellipsoid and elliptical potential lemma are not applicable for data-dependent feature mapping of DNNs. To avoid explicitly designing a bonus function, Thompson sampling 33 34 appears promising in a Bayesian perspective by using randomized (i.e., perturbed) versions of the estimated model or value function (35). Nevertheless, the bonus function is still implicitly included in confidence estimate of perturbations.
In this work, we center around deep neural function approximation with the e-greedy exploration. Since this exploration scheme is not enough to ensure the TD error smaller than zero, the technical challenge in our analysis is how to estimate by measure transform, the TD error is analysed in an averaged measure wrt a mini-batch of historical state-action pairs. To break the dependence between the episodes for neural networks training. we utilize the experience replay scheme [36] from DQN, and then transform the TD eттor estimation to generalization error under the independent but non- identically distributed data setting and approximation error in the respective function spaces. Note that in practice, experience replay makes observations to be (nearly) iid, but our analysis only requires the independence of observations, that is weaker than iid. Such generalization problem can be addressed by uniform convergence via (local) Rademacher complexity of the Besov/Barron spaces under the averaged measure. This considered function spaces in this work is more general than Hölder spaces used in offline RL [37].
ensure the sublinear regret. In our proof framework, space, where jı is the
Our results show that (i) the problem-dependent smoothness of Q-function affects the efficiency of learning with deep RL, which can be improved by increasing the model capacity (width and depth). We use a as a parameter indicating the smoothness degree of Q-function. A larger indicates smoother functions, easier RL tasks, and smaller exploration times, which coincides with our theory. (ii) for deep neural networks under the Besov space, the width m = O(T'z=a) ) and the depth L (1) are enough for sublinear regret under the e-greedy policy, where Ō(.) omits the log
2

---

terms. (iit) for two-layer neural networks under the Barron space, the width m Q(VT) suffices to ensure sublinear regret. Furthermore. our regret bounds can be independent the feature dimension, supporting the premise of practical, high-dimensional data in RI..
1.2 Related work
Recent work on neural network function approximation beyond NTK (or the Eluder dimension) mainly restrict on the generative setting [25 38 by assuming a simulator in which the agent can require any state and action, and the offline setting [37 39 In sequel, we review RL with function approximation under the online setting that DQN falls into this regime. We also mention that, theoretical understanding of DQN
be conducted by from the perspective of neural fitted Q- iteration algorithm [40, 337 41, and Q learning [22 in the perspective understanding the target network [3) and experience replay [44 45 46
with linear function approximation. Note that, for notational consistency with previous work, in this subsection, ''' denotes the total number of steps (i.e., interactions with the environment) instead of the number of episodes in our paper.
RL with linear/kernel function approximation: RL with linear function approximation achieves a sublinear regret bound with Ö(V HT)) under a low-rank MDP in a model-free setting 7 and D(dH2vT) in model-based setting 322 where H is the length of each episode. The regret can be improved to Ö(dH TT) under low inherent Bellman error by assuming global planning oracle 47 or under a Bernstein-type exploration bonus and controlling extra uniform convergence cost This nearly optimal regret can be also achieved under the linear mixtures setting [IO]. In the kernel regime, the regret can be achieved with (68 33)) intrinsic complexity (e.g.. effective dimension) of the function class RKHS F. The above bounds are based on confidence ellipsoid to quantify the uncertainty in an explicit bonus function by feature mapping/kernel function; while Thompson sampling 34 33) utilizes implicit bonus function in
32 12,, where 6z is the
probability estimation uncertainty quantification, which leads to H linear function approximation.
35 regret in
RL with general function approximation: One prototypical scheme uses the Eluder dimension 15)
which measures the degree of dependence among action rewards, resulting in ((poly(6-11))
regret [6 [7). where the complexity 05= depends on the Eluder dimension. Using this metric, the sublinear regret under the e-greedy exploration can be achieved by [49]. Besides, the low Bellman rank assumption (13), where the Bellman error "matrix" admits a low-rank factorization, can be also used general function approximation [[4] by measuring the error of the function class under the Bellman operator. Combining Bellman rank and Eluder dimension results in a new metric, Bellman Eluder dimension [50), achieving O(H Vo where 6 depends on this metric.
Overall, the above metrics are difficult the nonlinear spaces of DNNs beyond "linear" regime that concern us.
2 Background and preliminaries
In this section, we introduce the necessary background and definitions with respect to online rein- forcement learning based on episodic Markov decision processes (MDPs) and function spaces of deep (and two-layer) ReLU neural networks.
Notation: We denote by a(n) b(n): there exists positive constant independent of n such that a(n) & cb(n); a(n) x b(n): there exists two positive constant and C2 independent of such that b,b(n) & a(n)= & czb(n). We use the shorthand [n] := {1, .,..., n for some positive n and [x:] denotes the smallest integer exceeding Let X' [0. 1]d be domain of the functions,
denote the T i.ttnrtgrel space by T.2) endowed by the norm 11/llze(x) = (Jx (==)) and the in-ntegrrblee I," space by [P(d)) for probability measure μ on X' and the norm is given by [[L[let(w)) = (Jx Pdp)) 1/9
2.1 Episodic Markov decision processes
(finite-horizon) episodic MDPs denoted as MDP(SS, A,, H,PPr), where is the state space with possibly infinite states; A is the finite action space; H is the number of steps in each episode;
3

---

::= (PA) is the Markov transition kernel with the transition probability PA (-|s,, a) on action a taken at state s E S in the h-th step; the reward functions r == [ra]h=r are assumed to be deterministic. For notational simplicity, denote X' = S x A and æ - (8, a), we assume X' = [0, 1 as a compact space of Id and rn : S A + [0, 1] at h-th step.
A non-stationary policy is a collection of H functions π == {TH : + A) Given policy t, the (state) value function VA= : S -> [0, H] is defined as the expected cumulative reward of the MDP starting from step h E [H]. i.e., Vi. (s) = E, Ei'=h (sw (sws,)a)))) ) sy. s], Vs E S, E [H] where E. [-] denotes the expectation with respect to the randomness of the trajectory {(h, )n)) obtained by the policy т. Likewise, the action-value function Q x A + [0, H| is defined as
(s, a) = E, > The (sw, 8n. 8, an = =a]
Moreover, since the action space and episode length are both finite, there always exists an optimal policy π [51] such that (s) = supx (s) for all s E S and h E [H]. To simplify the
notation, denote (PP)V)s, a) == (-).a) (s') and the Bellman operator (TxV)ss a)
(s) + (P,, (P, a) for any measurable function V: S - [0, H). Using this notation, the Bellman equation associated with a policy и can be formulated as
(T a) (Tp V. 1ss,)ss,)),
V/ (s) = (Q% TA (-1s)A
V V#++ (s) = =0.
(1)
Similarly, the Bellman optimality equation is given by (*,,,) a) = (Tx (ss,))
(x) = max Q7 a),
(+)= = 0.
(2)
aεA
Accordingly, the optimal policy x² is the greedy policy with respect to (Q1) Hence the Bellman optimality operator T72 is defined as
(Ti (sn, on) = rh (sh, an) + (
Imaa [max (sh++1,)]] aEA
A VQ: x A [0, H).
By definition, the Bellman equation in Eq. is equivalent to Q7 = T Vh [H].
In the online setting, the goal is to learn the optimal policy x* by minimizing the cumulative regret under the interaction with the environment over number of episodes. For any policy и, the difference between V/" and Vi quantifies its sub-optimality. Thus, after (fixed but large) episodes, the total (expected) regret is defined as Regret(7) = EV - Vf2 (s()], where #f is the policy executed in the t-th episode and of is the initial state.
2.2 Function spaces
We give an overview of Besov spaces for deep neural networks and the Barron space for two-layer neural networks. More details refer to Appendix A For description simplicity, we focus on the ReI.U activation function in this work.
Besov spaces: Previous work in approximation theory focuses the "smoothness" of the function, e.g., Hölder spaces [52] 37 and Sobolev spaces [53]. Here we consider the concept of a-smooth
from modulus of smoothness 30), cf., Appendix A
Based on this, we consider a more general function space beyond Hölder spaces and Sobolev spaces, ie., Besov spaces [54 30), which allows for spatially inhomogeneous smoothness with spikes and jumps. The Besov space is defined by (2)) = {f E L'(x') lIflle,, < oo}, where the Besov norm is ||f := ( + If The smoothness parameter a indicates which function at certain smoothness degree can be represented. For example, if a > d/p, then the related Besov space continuously embedded in the set of the continuous functions; if a < d/p, then the functions in the Besov space are longer continuous. The formal definition and relations to Hölder spaces and Sobolev spaces are deferred to Appendix[A]
Barron spaces: A two-layer neural network with m neurons can be represented as f()) = I Ene (wo + c&) with the ReLU activation function a(-) used in this work and the neural network parameters {be, Ck)CH
It admits the integral representation f(x) So ba (wT c) p(db, due, do), E X, where Ω R x Rdd x IR and p is probability measure over Q. Then the Barron space (31] endowed by the Barron norm is defined as
p = {s admits Eq.
12 : |[ x = inf (E + +c)} < 00

---

The Barron space P
B1 can be (roughly) equipped with the { f1-path norm, i.e., llfll < Ilfle
1 Ek= [/1[[| + ca.) & 1.. Accordingly, it is natural to use || to denote the Barron
norm, as the discrete version.
The Barron space [3 can be regarded as the largest function space for two-layer ReLU neural networks. Here the "largest" terminology BI 551 means that the approximation ability can avoid curse of dimensionality, i.c. 1) any function in Barron spaces can be efficiently approximated by two-layer neural networks with bounded norm; 2) any continuous function that can be efficiently approximated by two-layer neural networks with bounded norm belongs to Barron space.
We remark that, avoiding curse of dimensionality is important in theory for practical high-dimensional data in RL. However, Besov spaces are too large and thus do not enjoy this property for deep ReLU neural networks.
3 Algorithm: Value iteration via DNNs under e-greedy exploration
In this section, we lay out our algorithm I via value iteration by DNNs under the e-greddy policy. Though our value iteration algorithm is different from one gradient-step for deep Q-learning in DQN, it still shares the key spirit with DQN in terms of function approximation via DNNs, e-greedy exploration, and experience replay.
Function class: We define the function class F. given by = x ... x Fu, including Few for two-layer (Shallow) ReLU neural networks and FoRz for deep ReLU neural networks as below
{
10, + [0, ()))))
1 m Σ beo beoww ck), I| B
FSRX
where B > 0 is the f1-path norm constraint parameter, and deep ReLU neural networks 30
Fom m, S) = { f 10, 11sh 10
10, (1 = (w())(()) + ble)) (W + b()).
Σ (I + 1100))0)) < S, max(I loo v 1ox) < B
where the weight parameters are ( E Roxd W E mm VI E (2, 12 1]. and W(L) E IR"; the bias parameter are b(0) E Rm, AI E [] and b(L) E R. Such sparsely- connected neural networks require most of the network parameters be zero or non-active, which can be verified [56]. The depth I., the width m, the sparsity parameter S and the norm parameter B can be determined later in our proof to achieve good approximation and estimation performance.
Experience replay: In our setting, after initialization, at t-th episode, at h-th time step, we have observed 1 transition tuples, {(s), 0%, s) and attempt to estimate { via DNNs. Note that, at each time step h. these t - transition tuples are neither independent nor identically distributed due to the interaction with value functions and stochastic transition. To pursue the independence among the transition tuples that is required in our analysis, we follow the experience replay scheme (36) that is successfully applied in DQN 4 The intuition behind experience replay is to break (or weaken) the temporal dependency among the observations for neural networks training. When the replay memory is large (c.g., 10th in DQN 44), experience replay is close to sampling independent transitions. To be specific, at f-th episode, we store transition {(s}, a The S )) in the replay memory DD, and then sample a mini-batch of independent observations from D with ((5R a 11+41) ((.n))e()())))(((( for DNNs training. Here the number of mini- batch is denoted as
f := [et] with the mini-batch ratio (0, 1), and {rş} is the index for the mino-batch of f independent samples. Note that such independence assumption from experience replay also used
in RL theory, e.g., [37 44 and theoretically demonstrated to be good de-correlator (57]. In fact, our analysis only requires independence via experience replay, which still weaker than the standard iid assumption.
Value iteration via neural networks: In our algorithm, we apply the classical least squares value iteration via neural networks for value function learning (28). We solve the following least squares
5

---

Algorithm Value Iteration via DNNs under e-greedy exploration with experience replay
Input: Function class F, the number of episodes T,, the e-greedy parameter e (0, 1), mini-batch
ratio E (0,1).
2: Initialize replay memory D.
3: for episode t 1. 1..... T do
4: Receive the initial state si.
5: Set + as the zero function.
6: Set the minibatch size i =
[et] for experience replay.
7:
for step h = H...., do
Obtain Q% argmin sez Σラ= [f(s]] a, ( ax) Vhtt1 (
8:
9:
Obtain Q Qi and Vy(+) = max 0 (:)).
10:
end for
11:
Iycegreddy for exploration
12:
Take the policy { to be greedy policy with probability or any policy with probability e.
13:
for step h= l..... H do
14:
Take af, (-1s%))
15:
Observe the reward (sh af,) and obtain the next state + end for
17:
//experience replay
Store transition { of The s 1) Kー in D.
19:
Sample random mini-bated of transitions from D with pairs {(s) , (2n
20: end for
regression problem via independent samples
i argmin ()( = Σ [666
rn(RR a.) 1
(5)
JEF
For ease of simplicity for analyses, we directly assume that the global minima solution of problem (5) can be obtained, that follows (58 52 [9] in deep learning theory. Nevertheless, our result could be extended to allow small optimization error in each episode that will be discussed in Section [6]
Besides, we also need the expectation version of ε in problem (5) for our analysis. Formally, we assume each state-action pair in the mini-batch is sampled from a respective (unknown) probability measure, i.e., (5) a p Vj E [f]. where 14 (S x A) from the collection of all
probability distribution on S A. Taking the averaged measure F.j := of E,, is defined
1 the expectation
E) =
(Pa-een.. (8), - rn (x
(
Note that, Q4 in Eq. (5) is not an unbiased estimator of the squared Bellman error minimizer [60] 61 Indeed, E differs from the squared Bellman error because of extra variance term caused by the stochastic transition [62]. This biased estimation issue can avoided (or alleviated) in practice by introducing target networks in DQN [63]. Some variants [64] of DQN can also reduce the biased estimate and performs well without target networks. Nevertheless, in our analysis, we center around the uniform bound sup (f) - ( instead of the Bellman error.
c-greedy exploration: In order work in the online setting, need to ensure that the learner visits "good" state action pairs in the sense that are almost maximizers of the value function for unseen state, a.k.a., exploration. In RL theory, classical way is to design optimistic estimate of the value function via bonus function 6j, 11 65 such that O min Q + 6f, HJ+ Instead, we employ the e-greedy exploration that follows DQN-like algorithms. Using the e-greedy exploration will ensure each state-action pair can be visited with positive probability and favor independence among samples. In our algorithm, we directly set Q == min Q2, 17++ + and then naturally incorporate the truncation operation in neural networks training, Eqs. and

---

Based on the above description, our algorithm centers around deep neural function approximation via value iteration under the e-greedy exploration and experience replay under the online setting. This problem setting matches the spirit of practical DQN, which allows for better understanding deep RI..
4
Main results
This section presents our results for value iteration under deep (as well as two-layer) ReL.U neural net- works via the Besov spaces and Barron spaces, respectively. Our theory is based on the independence assumption via experience replay and achieves sublinear regret under the e-greedy exploration.
4.1 Efficient value iteration via DNNs in Besov spaces
In this setting, we consider O = argmin fe (f) in Eq. (5). where Frmm the function space of deep ReI.U neural networks defined in Eq. 4 We make the following assumption on the Besov space B, similar to [2), where the Bellman optimality operator maps any bounded value function to bounded Besov space ball.
Assumption 1. Let R be a fixed constant. Define B { B (2))
||f & R] in the Besov [0, H. we have T E Bg-
p.q
space and assume that for any h E [H] and Q: S
Remark: Due to Q E [o, H the radius R in fact depends on H, i.e., R H.
Based on this assumption, we have the following theorem on the regret bound in the Besov space for deep RL under the e-greedy exploration.
Theorem 1. Under Assumption with the smoothness parameter
d(1/p 1144+ in the Besov
space B (X)) considering value function learning (5) via DNNs defined by Eq. (4) in Algorithml under the e-greedy exploration and the mini-batch ratio E (0, 1), and taking
the depth L 2a+d log the width m 2a T Iuld log T
then given MDP dependennd constant K E [1, H. for any 8 E (0, 1), the total regret can be upper bounded with probability at least
1
HiTEi log 3 T H V V log (2) log cHT
(T)
TH log log
A
V
8
KKto+418442 N (20+0)(+2 ) taking e O(HK) Rtz A A (20 (10xx
S
K
Remark:
We make the following remarks.
The constant K describes the "myopic" level of MDPs under the e-greedy policy, e.g., the worst case (K ;= H) under the sparse rewards setting; the benign case K := (for some small constant e) under the helpful dense rewards setting discussed in [49]. The exponential dependence on H (in the worst case for any MDP) can be avoided at an additional cost of worsening T dependence, In fact, whether in the benign/worst case, the sublinear regret is always achieved under some certain values in Eq. (8) which theoretically demonstrates the efficiency of deep RL. Note that the chosen C (0, 1) is always satisfied under large episode T.
tî) Clearly, the regret bound is non-increasing function of the smoothness parameter a, which shows that easier task (i.e., the target function is more smooth) leads regret bounds with faster rates. Specially, we take a - do (i.e., the target Q function is sufficiently smooth), which holds for linear function approximation
Regret(T) S K
H14
which recovers the regret bound Ö(T x in 49 Theorem 3] via Eluder dimension. In the best case (K = 1), our regret bound implies Ō ( A with H 4, which matches the optimal regret bound for the contextual bandits problem in terms of dependence on T or A under the e-greedy exploration [66]. In the worst case (K := H), we can still obtain the sublinear regret at a certain #+1 Ö #2 rate.
7

---

Theorem demonstrates that the sublinear regret can be achieved by choosing (log T)) depth and Ö(TTaT)) width, but the sublinear regret bound Ö(T (2x+3](842) +1+
heavily depends on the feature dimension d, failing in the curse of dimensionalityy which appears ineffective on high dimensional data in deep RI.. In the next, we consider the Barron spaces, i.e., the "largest" function space for two-layer neural networks to avoid the curse of dimensionality. this case, the rate of the sublinear regret can get rid of d, which is useful for high dimensional data in practical RL.
4.2 Efficient value iteration via two-layer neural networks in Barron spaces
As mentioned before, Barron spaces are the "largest" function space for two-layer neural networks. In this setting, we consider Qh argmin e f) of two-layer ReLU neural networks defined in Eq. (3 We give similar assumption on the Bellman optimality operator in the Barron space.
(f) in Eq. (5). where Fsuu is the function space
Assumption 2. Let R. O be a fixed constant. Define PR. = (f E 1lflpp S R in the Barron space, and assume that for any h E [H] and Q: S x A + (0, HJ, we have T E PR
Based on this assumption, we have the following regret bounds for two-layer ReLU neural networks. Theorem 2. Under Assumption Q considering value function learning ( by two-layer ReLU neural networks with width m and bounded E norm B defined by Eq. (3) in Algorithm I Junder the e-greedy exploration and the mini-bute buich ratio @ E (0, 1), then given MDP- dependeettt conslant K E [1, H), for any E (0, 1), the total regret can be upper bounded with probability at least
(T) - (
$
H2T
B(log d) +log+
(0)
HºT m
+ +CHT + TH3 T log
(4)
Ö(H (TTT
by taking ((VT) and O (H z
Remark: In result, taking 2(vT) is suffice to achieve the sublinear regret bound Ö(r (4),, which also gets rid of the feature dimension d, allowing for high-dimensional image data in practice.
28
5 Discussion on architecture guidelines in deep RL
In this section, we present a detailed discussion on how our results provide the architecture guidelines in practical deep RL, in the perspective of the width, the depth, and problem-dependent smoothness of the Q function.
Width-depth and DQN: According to Theorem i the Ologg T) depth and ((TT2o41)) width are enough for sublinear regret in deep RL. Interestingly, practical implementation of DQN. For example, the choices of [4] m = 512 and L 5 can be explained by theory, indeed log(512) Re 6. Specially, when taking + oc, this setting holds for linear function approximation. For two-layer neural networks endowed by the Barron space, the curse of dimensionality in terms of width and regret bound can be avoided in Theorem 2 supporting the premise of practical, high- nigh-dimensional RL.
notice that this result is closely matching
The problem-dependdnt smoothness, determined by a, largely affects our regret bounds. The difficulty of task in deep RL can be defined in two views: one is the smoothness of the targer Q function; and the other is the degree of exploration. Intuitively speaking, if RL task is difficult, then the target Q function is often complicated, and thus admits relative lower smoothnes;; results coincide with these two views. One hand, the regret bound in Theorem Tis a non-increasing function of the smoothness parameter a. A more difficult task in deep RL (i.e., smaller a) leads to a slower rate of the sublinear regret, which indicates that more episodes are required. On the other hand, Theorem [ shows that the parameter is also a non non-increasing function of That means, more difficult task in deep RL requires a larger e, i.e., we need conduct exploration more frequently.
Problem-dependent smoothness and exploration:
need conduct more exploration in a complex scenario. Our
Besides, the exploration parameter is also affected by K for MDPs with different situations. For example, compared to the best case K = 1, more frequent exploration (a larger a) is required in MDPs under difficult cases, which coincides with our certain value in Theorems and 2
8

---

statistical error: Lem.
with (VVHTT)
Regret
generalization
decomp.
Term (1) < Lem.
Lem. 4:
|| || La(a))
+ Lem. 3 p (C) >
approximation
Lem.
e-greedy exploration: eHf
Figure 1: Proof framework of regret decomposition and transformation of the TD error.
Width and depth trade-off: Under a limit parameter budget, according the width-depth ratio m/L = Tadia in Theorem our theory indicates that less problem-dependent smoothness of Q-function requires DNNs be wider. In practice, if work in the limited budget of parameters N in neural networks, e.g., N x m² our theory implies that there is tradeoff between the depth and width on smoothness, i.e., the depth |
N1/31 3,244;;
2d increasing with (or ')) and the width
m N 1/3 522 decreasing with a (or 2).
Besides, according the width-depth ratio, it can be found that, the change of leads to less changes on the depth but more changes on the width. This shows that width and depth admit different levels of parameter sensitivity under the change of problem-dependent smoothness.
6 Proof outline
In this section, we outline the proof of our theoretical results presented in Section 4 As mentioned before, the technical challenge in our analysis how to estimate the TD error without bonus function design. Apart from the regret decomposition, our proof framework includes two main parts: transformation of TD eтrоr estimation to generalization bounds, see Figure [ and generalization bounds on non-iid data in certain Besov/Barron spaces for TD error analysis, see Figure 2 The complete proof is reported the appendix.
Regret decomposition: This part is standard and commonly studied in RI. theory, e.g., We briefly include here for self-completeness. Define the temporal-differeence (TD) error
65
12
T7 (s. a) (s a) (PA (s, a) (s. = (TA (s, a) (% a), V(s,a) E Sx
(9)
where ry is function on S x A for all h [H] and t E [T]. Accordingly, the regret can be decomposed into (c.f. Lemma
[T] (Sh, an) 81 =s{] (s ab)) +Term (11) + cHT,
Regret(T) (T)
E
(10)
Torn
where the first term relates the TD error and the second term is the statistical error based on the standard martingale difference sequences, which can be upper bounded by the Hoeffding-Azumi inequality with O(VH3T) regret (c.f. Lemma 2). The last term eHT is due to the e-greedy exploration.
Transforming TD error to generalization bounds: To bound the TD error, we first introduce
Lemma 3 with / (C) > O, where the event C denotes that all state-action pairs have been visited at all time steps under the e-greedy policy. Then we are able build the connection between Term (1) and | (Tlaaz(g))))) in the (dpf,, -iittggri space (c.f. Lemma 4b. After analysis of E in
Proposition 1. we transform the estimation of | (Tlll the following two terms: generalization error and approximation error, respectively (c.f. Lemma
[[T 12 (a < (
min & (n] fEF
inf in Ti fEF
(11)
where the first term is the generalization error which we elucidate in the next and the second term is the approximation error and can be considered in an L (XY) space for Besov spaces in Corollary For example, the approximation error the Besov space admits the certain ONN -22//) rate in for deep ReLU networks with L x log N, S x N, x N log N.

---

Rademacher complexity non-iid data: Lem. Lem.
two-layer NNs: Thm.
= O(If
logd/n)
Lem.
13 Rademacher complexity of Barron spaces
DNNs: Thm.
O 2 Prop. Lem.
12
LRC for Besov spaces
Figure 2: Proof framework of the TD error via generalization bounds on non-iid data. We denote LRC by local Rademacher complexity for short.
The key part left is to bound the generalization error on non-i.i.d data for the TD error estimation, see the proof framework in Figure In our proof, we firstly verify that the maximum eπror in estimating the mean of any function E F can be still bounded by the Rademacher complexity F in Lemma [ and then generalization bounds by Rademacher complexity still holds by Lemma via the averaged measure n/ which only requires the data to be independent. These results can be easily extended to local Rademacher complexity.
Generalization bounds on non-iid data:
For deep neural networks, by computing the local Rademacher complexity of Fexu in Lemma 12 and choosing proper neural network parameters in Eq. 4 we derive the convergence rate of
generalization bounds at certain O(n x rate in Besov spaces (c.f. Proposition 2 with non-iid data. Combining the result of approximation error and taking the depth and width in Eq. (7)
Term (i) can be upper bounded with high probability. Finally we conclude the proof of Theorem by combining with the statistical error.
For two-layer neural networks, by computing the Rademacher complexity of Fau in Lemma 13
obtain the generalization error at certain O(H²² B /log d/nn) convergence rate. Combining the result of approximation error in Barron spaces with other terms in the regret decomposition, we conclude the proof of Theorem 2
Regret bounds effected by optimization error: Here we briefly discuss the regret bound affected by a solution (denoted as 21) that is not global minimum of problem (5). Assume that the optimization error is small in the functional view, i.e., 11 (a & Copt. that will appear in Eq. 11 and
accordingly Term (1) incurs in an extra regret bound O(H² log T' if we take Eopt := H / This
condition is fair and reasonable as the optimization error decreases with the mini-batch size i for neural network training but requires a refined analysis under non-iid data 67 68
7 Conclusion
This paper provides an in-depth understanding on neural network function approximation with the c-greedy exploration under the online setting beyond the "linear" regime. Our results provide theoretical guarantees of sublinear regret bounds, and shed light on some guidelines for understanding deep RL in the perspective of the width-depth configuration and the problem deppndeen smoothness of RL tasks.
The analysis of this work is built on the e-greedy policy for exploration, which are satisfied in practical cases when employing DQN. Nevertheless, designing provably efficient exploration mechanism for deep RL could be an interesting future direction in both practice and theory. Besides, our theory requires state-action pairs to be independent, which (approximately) holds via experience replay and could be improved by reverse experience replay [69]. Furthermore, our work built on the value iteration based algorithm, which is different from practical DQN that adapts Q-learning via one-step gradient descent. Towards a better understanding DQN in terms of Q learning and target networks would be an interesting direction.
43
Acknowledgement
The authors would like to thank anonymous reviewers for their constructive suggestions to improve the presentation and point out the independence issue.
This work was supported by SNF project - Deep Optimisation of the Swiss National Science Foundation (SNSF) under grant number 200021 1021__050111 I; the Enterprise for Society Center (F4S); the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement n 2725594 time-data).
10

---

References
[1] Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning, 4(1):1-103, 2010.
[2] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[3] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International conference on machine learning, pages 1587-1596.
PMLR, 2018. T
[4] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):59-5333 2015.
2015.
2
[5] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game Go with deep neural networks and tree search. Nature, 529(7587)4844-88, 2016.
[6] LeCun Yann, Bengio Yoshua, and Hinton Geoffrey. Deep learning. Nature, 521 5215553):4436-444
2015. [
[7] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[8] Yining Wang, Ruosong Wang, Simon Shaolci Du, and Akshay Krishnamurthy, Optimism in reinforcement learning with generalized linear function approximation. In International Conference on Learning Representations, 2020.
[9] Alex Ayoub, 7eyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. International Conference on Machine Learning, pages 463-474. PMLR, 2020.
[10] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532 4576. PMLR, 2021.
[11] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, pages 8571-8580, 2018.
[12] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. In Advances in Neural Information Processing Systems, 2020.
18 19
[13] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, Robert Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017. 3
[14] Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Root-n-regret for learning in markov decision processes with function approximation and low bellman rank. In Conference on Learning Theory, pages 1554-1557. PMLR, 2020. 33
[15] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
[16] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. In Advances in Neural Information Processing Systems, volume 33, pages 6123-6135, 2020.

---

[17] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration reinforcement learning with general value function approximation. In International Conference on Machine Learning, pages 4607-4616. PMIR, 2021.
13
[18] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable pro- gramming. In Advances in Neural Information Processing Systems, pages 2933, 2019.
[19] Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, pages 8570-
8581, 2019. T
[20] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673. PMLR, 2020. [
[21] Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020(11): 13301, 2020.
[22] Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(1):629 681, 2017.
[23] Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for un- derstanding neural networks. In Advances in Neural Information Processing Systems, pages 6594-6604, 2019. [
[24] Michael Celentano, Theodor Misiakiewicz, and Andrea Montanari. Minimum complexity interpolation in random features models. arXiv preprint arXiv:2 15996, 2021.
[25] Baihe Huang, Kaixuan Huang, Sham Kakade, Jason D Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Going beyond linear rl: Sample efficient neural function approximation. In Advances in Neural Information Processing Systems, 2021.
[26] Gene Li, Pritish Kamath, Dylan J Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprint arXiv:2104.069700 2021.
[27] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. In Advances in Neural Information Processing Systems, volume 34, 2021. [
[28] Ian Osband, Benjamin Van Roy. Daniel Russo, Zheng Wen, et al. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 62, 2019.
[29] Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep Ielarning from demonstrations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018. 2
[30] Taiji Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2019,
26
[31] Weinan Chao Ma, and Lei Wu. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, pages 1-38, 2021.
18 29 30
[32] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020. 2
[33] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Oshand, Zheng Wen, et tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
12

---

[34] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi aumti bandit problem. In Conference on Learning Theory, pages 1-39. JMLR Workshop and Conference Proceedings, 2012.
2 3
[35] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics,, pages 1954-1964. PMLR, 2020. 3
[36] Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3):233-211, 1992. 2 5
[37] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pages 186-489, 2020.
5
[38] Jihao Long. Jiequn Han, et al. An 12 analysis of reinforcement learning in high dimensions with kernel and neural network approximation. arXiv preprint arXiv:2104.07794, 2021. 3
[39] Thanh Nguyen-Tange Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. Sample complexity of offline reinforcement learning with deep relu networks. arXiv preprint arXiv:2103.06671,
2021. g
[40] Martin Riedmiller. Neural fitted Q iteration-first experiences with data efficient neural reinforcement learning method. In European Conference on Machine Learning, pages 317-328.
Springer, 2005. 3
[41] Pan Xu and Quanquan Gu. A time analysis of q-leaming with neural network function approximation. In International Conference on Machine Learning, pages 10555-10565. PMLR, 2020.
[42] Chi Jin, Zeyuan Ahu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? In Advances in neural information processing systems, 2018. 3
[43] Andrea Zanette and Martin J Wainwright. Stabilizing Q-learning with linear architectures for provably efficient learning. arXiv preprint arXiv:2206.0000 00796, 2022.
10
[44] Diogo Carvalho, Francisco S Melo, and Pedro Santos. A new convergent variant of Q-learning with linear function approximation. In Advances in Neural Information Processing Systems, volume 33, pages 19412- 19421, 2020. 3 T0
[45] Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Online target Q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXiv preprint arXiv:21100008440, 2021.
[46] Liran Szlak and Ohad Shamir. Convergence results for Q-learning with experience replay. arXiv preprint arXiv:21 / 2021. 3
[47] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages (0978-10989, PMLR, 2020.
[48] Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 8971-9019, 2022. S
[49] Chris Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Guaran- tees for apsilon-greede reinforcement learning with function approximation. In International Conference Machine Learning, pages
2022.
7 20
[50] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021. 3
[51] Martin I. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. 4
13

---

[52] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. Advances in neural information processing systems, 12:8174-8118 2019.
4 6
[53] Ahmed Abdeljawad and Philipp Grohs. Approximations with deep neural networks in sobolev time-space. arXiv preprint arXiv:2101.06/15, 2020.
[54] Yoshihiro Sawano. Theory of Besov spaces, volume 56. Springer, 2018.
[55] Weinan E and Stephan Wojtowytsch. Representation formulas and pointwise properties for barron functions. arXiv preprint arXiv:2006.05982 2020. 5 18
[56] Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns.
Advances Neural Information Processing Systems, 32, 2019. [
[57] Shirli Di-Castro. Shie Mannor, and Dotan Di Castro. Analysis of stochastic processes through replay buffers. In International Conference on Machine Learning, pages 5039-5060. PMLR, 2022.
[58] Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU
activation function. Annals of Statistics, 48(4):1875-1897 2020. G
[59] Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic besov space. Advances in Neural Information Processing Systems,
2021. 6
[60] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with gellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89-112) 129, 2008. 6
[61] Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference on Machine Learning, pages 2892-2999 2902.
PMLR, 2021. 6 22
[62] Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning. 22(1):33-517 1996. G
[63] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint
1312. arXiv: 13 132..602, 2013. 6
[64] Seungchan Kim, Kavosh Asadi, Michael Littman, and George Konidaris. Deepmellow: re- moving the need for a target network in deep q-learning. In International Joint Conference Artificial Intelligence, 2019.
[65] Qi Cai,, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294, 2020. 6
18 19
20
[66]
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[67] Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Streaming linear system identification with reverse experience replay. In Advances in Neural Information Processing Systems, pages 30140-30152, 2021. 10
[68] Ahmet Alacaoglu and Hanbaek Lyu. Convergence and complexity of stochastic subgradient methods with dependent data for nonconvex optimization. arXiv preprint arXiv:2203. 15797, 2022.
I0
[69] Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Nagaraj. and Praneeth Netrapalli. Online target Q-learning with reverse experience replay: Efficiently finding the optimal policy for linear MDPs. In International Conference on Learning Representations, 2022. 10
[70] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control neural networks. In Conference on Learning Theory, pages 1376-1401. PMLR, 2015.
18
14

---

[71] Mehryar Mohri. Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
MIT press, 2018. 23
[72] Martin Wainwright. Iligh-dimensional statistics; non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
23 30
[73] Shahar Mendelson. Improving the sample complexity using global data. IEEE transactions
Information Theory, 1991, 2002. 23 26
[74] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
23
25
[75] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 339-:13477 2005.
25
26
[76] Yunwen Lei, Lixin Ding, and Yingzhou Bi. Local rademacher complexity bounds based on covering numbers, Nearocomputing, 218:320-330, 2016.
25
15

---

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]
(b) Did you describe the limitations of your work? [Yes] We clearly discuss the limitation
of this work in the Conclusion section.
(c) Did you discuss any potential negative societal impacts your work? [No] Our work is theoretical and generally will have no negative societal 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 of assumptions of all theoretical results? [Yes] The assump- tions are clearly stated and well discussed.
(b) Did you include complete proofs of all theoretical results? [Yes] All of 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 the supplemental material or as 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 eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if 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 participant compensation? [N/A]
16


Reviews:
[{"review_id": "Y_pS7CaLTxx", "reviewer": "Reviewer_7U3N", "summary": "This paper theoretically studies value iteration type algorithms in RL using neural networks belonging to either the Besov or Barron function spaces. Under the probabilistic sufficient exploration assumption, scalings of the width and depth of the neural network are revealed for achieving sublinear regret for the proposed least square value iteration with neural networks. It is argued that the width has a more prominent effect than depth. Quantitative regret bound is established and only depends logarithmically on the dimension $d$.", "questions": "Some comments and questions are as follows:\n\n1. There is a mismatch between the terminology 'Q-learning' and the actual algorithm studied in this paper, which is indeed a least square value iteration algorithm with a neural network estimator. This is different from the usual Q-learning type algorithm, where the Q updates correspond to gradient descent of one-step TD error. This should be clarified in the paper.\n2. The regret bounds in Theorem 1 and 2 scale with $T^{4/3}$ and $T^{\\frac{\\alpha+d}{2\\alpha+d}}$, which are strictly worse than $\\sqrt{T}$. Do these results degenerate to $\\sqrt{T}$-type bound under simpler settings such as linear function approximation?\n3. Why there is no need to do exploration in Algorithm 1? It should be necessary for online RL algorithms. Is this due to the PSE assumption?\n4. Indeed, the PSE assumption seems unclear to me. In the definition of $\\mathcal{G}_\\epsilon$, is $f$ an arbitrary function? Here $\\epsilon$ seems to depend on the value of $\\|f\\|_\\infty$, and it is unclear where $f$ is specified. Apart from this, by letting $\\bar\\mu_h^t(\\mathcal{G}_\\epsilon) > 0$ hold with probability at least $1-\\delta$, it is imposing some condition on $\\widehat Q_h^1, \\ldots, \\widehat Q_h^T$, which is obtained in an online manner. Then, conditioning on Assumption 1 being true, $\\{\\widehat Q_h^t\\}$ is not a martingale sequence any more as conditioning changes its distribution (so do the TD error), thus it needs to be justified how to use martingale concentration inequalities (line 307-308).\n5. When running Algorithm 1, the collected data is conditionally independent instead of independent, because the policy in episode $t$ depends on all the previous data. Then how can we apply Lemma 5/6 (line 320-321)? ", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is easy to follow, and it is an important topic to analyze RL algorithms that employ neural network type estimators. The algorithm studied in this paper (Algorithm 1) is well-known, while it is claimed that the theoretical analysis reveals guidelines for the training setup in real applications. The discussion about related works for RL with function approximation can be more detailed, especially comparing the difference between the assumptions on the function classes. Also, it seems that some existing literature on theoretical analysis of Q-learning algorithms is missing, e.g., [1] and [2].\n\n\n\nReference:\n\n[1] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, Michael I. Jordan. Is Q-learning Provably Efficient?\n\n[2] Pan Xu, Quanquan Gu. A finite-time analysis of Q-learning with neural network function approximation.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MbvDyZWMBLu", "reviewer": "Reviewer_TT8h", "summary": "This paper provides a theoretical study of the successful deep Q-networks (DQN) framework under an online, episodic Markov decision process (MDP) model with T episodes. They focus on Besov and Barron function spaces in approximating an $\\alpha$ smooth Q-function in a d-dimensional feature space. Under some assumptions, they prove that DQN with shallow layers and medium width can learn the MDP with sublinear regret.", "questions": "1. In practice, how large is the norm parameter B?\n2. I do not understand why the regret bound in Theorem 1 not depend on dimension $d$ but in Theorem 2 it depends on $d$ explicitly. What is the reason behind such difference?\n3. What is the role of sparsity parameter $S$ defined in Eq. (5)?\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nIn summary, this is a good paper for RL theory. It tries to give a theoretical understanding of the widely used DQN algorithm, which is fundamental in Deep RL. The theoretical results in this paper is also interesting. It shows that DQN-type algorithm can achieve sublinear regret using a small-scale neural network, under some assumptions. As far as I know, these results are novel in RL theory. Also, the results match the practical experience.\n\nWeaknesses:\n1. The algorithm requires optimizing a neural network function to minimum. However in practice, it is usually not achievable. What will the results be if we only have an approximate solution to the optimization problem?\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2BEG0EneVOU", "reviewer": "Reviewer_Pwx6", "summary": "This paper studies a deep Q-network algorithm in the online and episodic MDP setting. With the probabilistic sufficient exploration assumption, this paper focuses on Besov and Barron function spaces to model the deep Q-networks. Two main theoretical guarantees are provided: one is for shadow neural networks, and the other is for deep neural networks. In both two cases, sublinear regret is achieved. From the theoretical results, this paper claims that for low smooth Q-functions, the width has a more important role and a constant depth is enough. From this perspective, this paper may shed light on width and depth guidelines in deep Q-learning. \n\n===\n\nAfter rebuttal, my concerns are addressed. This paper may shed new light on understanding deep neural networks in reinforcement learning. Yet, there are several future works, as noted in the conclusion part. Therefore, I change my score from 4 to 6. ", "questions": "I have a few concerns about this paper's motivation and theoretical implications. I list my questions as follows. \n\n1. Can the authors justify the (technical) challenge after Assumption 1 is satisfied? \n\nI have this question because I believe how to address the exploration-and-exploitation trade-off is the core of online learning. However, if we make the so-called Probabilistic sufficient exploration, it is not clear (at least for me) what is challenging in this setting. It seems that it is sufficient to consider the offline setting, where a fixed dataset is provided, to study how to approximate optimal Q-value functions. I guess that the online setting considered in this paper may introduce unnecessary (technical) challenges. I would appreciate it if the authors could help clarify this point.\n\n2. Can the authors further explain the empirical objective in Equation (3)?\n\nIt is known that DQN has two key components: experience replay and the target network. Without the target network, Q-learning with function approximation can easily diverge in theory; see [2] and Section 11.3 of [3]. From the workshop paper [4] to the nature version, the target network is introduced, and the performance is improved a lot for DQN. In practice, if the target network is removed, it is easy to see that DQN cannot work for games like Pong and Breakout. \n\nThis paper shows that i.i.d. sampling by experience replay is not necessary. This is acceptable. Then, this paper further studies Algorithm 1, where the target network is not used. This is a huge difference with practice. With a powerful approximation power, it is not very surprising that Algorithm 1 can converge. However, the issue is that the computation cost of Algorithm 1 is huge, which restricts the application of Algorithm 1. Based on this thought, I am not convinced that the theoretical implications in this paper are well-aligned with practical observations.  Please also refer to [5] for the study of online target Q-learning (authors are excused for this paper because this paper is recently posted).\n\n[2] Baird, Leemon. \"Residual algorithms: Reinforcement learning with function approximation.\" *Machine Learning Proceedings 1995*. Morgan Kaufmann, 1995. 30-37. \n\n[3] Sutton, Richard S., and Andrew G. Barto. *Reinforcement learning: An introduction*. MIT press, 2018.\n\n[4] Mnih, Volodymyr, et al. \"Playing atari with deep reinforcement learning.\" *arXiv preprint arXiv:1312.5602* (2013).\n\n[5] Zanette, Andrea, and Martin J. Wainwright. \"Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning.\" arXiv preprint arXiv:2206.00796 (2022).", "limitations": "This paper does a great job of analyzing Q-learning with deep neural networks. The main limitations are listed below. \n\n- Assumption 1 is quite strong for studying online learning. Though this paper explains that epsilon-greedy can achieve this, it is known that epsilon-greedy is much inefficient. \n- A gap between Algorithm 1 and practical one (i.e., the target network is not considered). It is hard for me to believe the theoretical implications in this paper are well-aligned with practical observations. If the authors can provide some numerical results to justify the theoretical results, I would be much convinced. \n\nI would suggest that the authors can elaborate on the technical challenge and provide more justification for the setting studied in this paper. \n\n**Minor Issues**\n\nThis writing of this paper can be further improved, as there are several grammar errors. To name a few,\n\n- In Line 35, demonstrates -> demonstrate\n- In Line 82, effects -> affects \n- In Line 93, assuming a simulator can require any state and action -> assuming a simulator in which the agent can require any state and action\n- In Line 99, the above algorithms -> the above bounds \n- In Line 112, function spaces of two -> and function spaces of two \n- In Line 177, which not heavily depends on -> which does not heavily depend on \n- In Line 190, $\\ell_1$ path norm -> $\\ell_1$-path norm \n- In Line 206, it is not clear the meaning of \"this requirement\"\n- In Line 251, they -> [12]\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- More border function classes are considered. Most prior works focus on the linear function approximation or (limited) non-linear function approximation.\n- A tighter bound in terms of the dependence on the width and depth is provided. For the prior work that relies on NTK, an impractical width $m = \\Omega(T^{13}) $is required.\n\n**Weakness**\n\n- The whole theory heavily relies on the assumption of probabilistic sufficient exploration. With this assumption, the exploration issue is already addressed. To this end, it is unclear why this paper studies the function approximation in the online setting. It seems that the offline setting considered in [1] is sufficient to study how to approximate optimal Q-value functions. \n- To my knowledge, the value iteration algorithm (with neural networks) is rarely used in practice, meaning that a gap separates the theory in this paper from practical algorithms. To clarify, Algorithm 1 has two computational issues. First, it is hard to compute the global minimizer defined in the empirical objective (i.e., Equation (3)) for each iteration. The computation cost is unacceptable. Therefore, people prefer iterative algorithms like Q-learning. Second, Q-learning with function approximation can easily diverge, and the target network is introduced to address this issue in DQN. However, these features are not captured by Algorithm 1 and theoretical results.\n\n[1] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pages 486–489, 2020.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept