A Finite-Time Analysis of  Q-Learning with Neural Network Function Approximation
Authors: Pan Xu
Quanquan Gu
Venue:  (2020)
Keywords: Reinforcement Learning
Neural Networks

Abstract: Q-learning with neural network function approximation (neural Q-learning for short) is among the most prevalent deep reinforcement learning algorithms. Despite its empirical success, the non-asymptotic convergence rate of neural Q-learning remains virtually unknown. In this paper, we present a finite-time analysis of a neural Q-learning algorithm, where the data are generated from a Markov decision process and the action-value function is approximated by a deep ReLU neural network. We prove that neural Q-learning finds the optimal policy with $O(1/T)$ convergence rate if the neural function approximator is sufficiently overparameterized, where $T$ is the number of iterations. To our best knowledge, our result is the first finite-time analysis of neural Q-learning under non-i.i.d. data assumption.

Under review as a conference paper at ICLR 2020
A FINITE-TIME ANALYSIS OF Q-LEARNING WITH NEURAL NETWORK FUNCTION APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Q-learning with neural network function approximation (neural Q-learning for short) among the most prevalent deep reinforcement learning algorithms. De- spite its empirical success, the non-asymptotic convergence rate of neural Q- learning remains virtually unknown. In this paper, we present a finite-time analy- sis of neural Q-learning algorithm, where the data are generated from a Markov decision process and the action-value function approximated by a deep ReLU neural network. We prove that neural Q-learning finds the optimal policy with O(1/VT) convergence rate if the neural function approximator is sufficiently overparameterized, where is the number of iterations. To our best knowledge, our result is the first finite-time analysis of neural Q Q-learning under non-i..d. data assumption.
INTRODUCTION
Q-learning has been shown to be one of the most important and effective learning strategies in
Reinforcement Learning (RL) over the past decades (Watkins & Dayan 1992, Schmidhuubrr 2015
Sutton & Barto 2018), where the agent takes action based the action-valus function (a.k.a., Q-
value function) at the current state. Recent advance in deep learning has also enabled the application
of Q-learning algorithms large-Scale decision problems such mastering Go (Silver al. 2016
2017), robotic motion control (Levine et al. [0155] Kalashnikov et al. (018)) and autonomous driving (Shalev-Shwartz et al.] 2016)] Schwarting et al. 2018). In particular, the seminal work by MMih et al. (2015) introduced the Deep Q-Network (DQN) to approximate the action-value function and
achieved superior performance versus human expert in playing Atari games, which triggers a
line of research on deep reinforcement learning such as Double Deep Q-Learning (Van Hasseli
ct al. 2016) and Dueling DQN (Wang et al. 2016).
Apart from its widespread empirical success in numerous applications, the convergence of Q- learning and temporal difference (TD) learning algorithms has also been extensively studied in the literature (Jaakkola et al., 1994 Baird 1995] Tsitsiklis & Van Roy 1997 Perkins & Pendrith (2022 Meyn | et al. 2015 Bhandari et 2018 Lakshmmmsmnnnrrtyyan
& Szepesvari 2018 Zou et al. |l.] (0T9b). However, the convergence guarantee of deep Q-learning algo- rithms remains a largely open problem. The only exceptions are Yang et al. (2019) which studied the fitted Q-iteration (FQI) algorithm (Riedmiller 20055 Munos & Szepesvári 2008 with action-valus function approximation based on a sparse ReLU network, and Cai et al. (2019a) which studied the global convergence of Q-learning algorithm with i.i.d. observation model and action-value func- tion approximation based on two-layer neural network. The main limitation of the aforementioned work is the unrealistic assumption that all the data used in the Q-learning algorithm are sampled i.i.d. from fixed stationary distribution, which fails to capture the practical setting of neural Q-learning.
Melo et al. 2
In this paper, in order to bridge the gap between the empirical success of neural Q-learning and the theory of conventional Q-learning (i.e., tabular Q-learning, and Q-learning with linear function approximation), we study the non-asymptotic convergence of a neural Q-learning algorithm under non-i.i.d. observations. In particular, we use deep neural network with the ReLU activation func- tion to approximate the action-valuu function. In each iteration of the neural Q-learning algorithm, updates the network weight parameters using the temporal difference (TD) error and the gradient of the neural network function. Our work extends existing tnite-time analyses for TD learning (Bhan-) dari et al. 2018) and Qllearning (Zou et al. 2019b), from linear function approximation to deep

---

Under review as a conference paper at ICLR 2020
Table 1: Comparison with existing finite-time analyses of Q-learning.
Non-iid. Neural Approximation
Multiple Layers
Rate
Bhandari ct al. (0188)
X
O
Zou et al. 2019b)
X
O(1/T)
Cai al. 2019a)
/
X
0(I/TT)
This paper
V
/
0(1/VT)
neural network based function approximation. Compared with the very recent theoretical work for neural Q-learning (Yang al. 2019 Cai et al. 2019a), our analysis relaxes the non-realistic i.i.d. data assumption and applies to neural network approximation with arbitrary number of layers. Our main contributions summarized as follows
We establish the first finite- time analysis of Q-learning with deep neural network function approx- imation when the data are generated from a Markov decision process (MDP). We show that, when the network is sufficiently wide, neural Q-learning converges to the optimal action-value function up to the approximation error of the neural network function class.
We establish O(1/ (T) convergence rate of neural Q-learning to the optimal Q-value function up to the approximation error, where T is the number iterations. This convergence rate matches the one for TT>-learning with linear function approximation and constant stepsize (Bhandari al., 2018). Although we study a more challenging setting where the data are non-i.i.d. and the neural network approximator has multiple layers, our convergence rate also matches the O(1/VT) rate proved in Cai et al. (2019)) with i.i.d. data and two-layer neural network approximator.
To sum up, present comprehensive comparison between our work and the most relevant work in terms of their respective settings and convergence rates in Table
Notation We denote [n| {L,.... n for N+ |x||2 is the Euclidean norm of vector Rd. For matrix W IR X we denote by ||W]l2 and || [[]] its operator norm and Frobenius norm respectively. We denote by vec (ec the vectorization of W, which converts W into column vector. For semi-definite matrix E Iddd and vector x Rd ||x|| vx Σx denotes the Mahalanobis norm. We reserve the notations {Ci)i=o,1... to represent universal positive constants that are independent of problem parameters. The specific value of [C+] can be different
line by line. We write an = (b,,) if an I Cb, for some constant C > 0 and an Ō(b,) if a, (bb,) up some logarithmic terms of bn.
RELATED WORK
Due to the huge volume of work in the literature for TD learning and Q-learning algorithms, we only review the most relevant work here.
Asymptotic analysis The asymptotic convergence of TD learning and Q-learning algorithms has been well established in the literature (Jaakkola et al., 1994 Tsitsiklis & Van Roy 1997] Konda & Tsitsiklis 2000; Borkar & Meyn 2000 Ormoneit & Sen 2002 Melo et al. 2008 Devraj & Meyn 2017). In partieular, [Titsikkis & Van Roy (1997) specified the precise conditions for TD learning with linear function approximation to converge and gave counterexamples that diverge. Melo el al. 20088 proved the asymptotic convergence of Q-learning with linear function approximation from standard ODE analysis, and identified a critic condition on the relationship between the learning policy and the greedy policy that ensures the almost sure convergence.
Finite-time analysis The finite-time analysis of the convergence rate for Q-learning algorithms has Szepes- vari (2018) studied the convergence of TD(0) algorithm with linear function approximation under L..d. data assumptions and constant step sizes. Concurrently, a seminal work by Bhandari et al. 2018 provided a unified framework of analysis for TD learning under both i.i.d. and Markovian noise assumptions with an extra projection step. The analysis has been extended by Zou et al. 2019h) to SARSA and Q-learning algorithms with linear function approximation. More recently,
been largely unexplored until recently. In specific, Dalal et al. (2018); Lakshminaaaaaaaan
2

---

Under review as a conference paper at ICLR 2020
Srikant & Ying (2019) established the finite-time convergence for TD learning algorithms with lin- ear function approximation and a constant step-size without the extra projection step under non-ii.d. data assumptions through carefully choosing the Lyapunov function for the associated ordinary dif- ferential equation of TD update. A similar analysis was also extended to Q-learning with linear function approximation (Chen et al., 2019). (Hu & Syed (2019) further provided unified analysis for a class of TD learning algorithms using Markov jump linear system.
Neural ffunction approximation Despite the empirical success of DQN, the theoretical convergence of Q-learning with deep neural network approximation is still missing in the literature. Following the recent advances in the theory of deep learning for overparameterized networks (Jacot et al., 2018 Chizat & Bach, 2018; Du et al. 2019b a Allen-Zhu et al. 2019b a Zou et al.) [019a;] Arora jet al. 2019: Cao & Gul 2019a Zou Gu 2019 Cai et al. 2019b), two recent work by Yang et al.
(2019) and Cai et al. (2019a) proved the convergence rates of fitted Q-iteration and Q-learning with
a sparse multi-layer ReLU network and two-layer neural network approximation respectively, under i..d. observations.
3 PRELIMINARIES
A discrete-time Markov Decision Process (MDP) is denoted by tuple M (8, (,,,, S and A are the sets of all states and actions respectively. P : S x A + P(S) is the transition kernel such that P(s'|s, a) gives the probability of transiting to state s' after taking action at state S: x A + [-1, is deterministic reward function. y E (0, 1) is the discounted factor. A policy P(A) is function mapping state 8 E S to probability distribution 7 T--ss) over the action space. Let 8, and 0f denote the state and action at time step I. Then the transition kernel P and the policy determine a Markov chain }== For any fixed policy n, its associated value function V= + I. is defined as the expected total discounted reward:
(*(s) EI 20r( (s0 = s], Ys E.
The corresponding action-value function Q" S A TR defined as
(*(ssa) = =E ('r(s) (s0 do al r(s, a) + ('T a)d''
for all s E S. a E A. The optimal action-value function Q- is defined as Q a) sup, ( A. Based on Q" the optimal policy x² can be derived by following the greedy algorithm such that x" (als) 1 if Q(s, a) maxse Q" (s, b) and n" (als) = otherwise. We define the optimal Bellman operator T follows
for all (s, a) E
TQ(s, a) r(s, a) + [maxxe Qs' b)|s a(-
(3.1)
It is worth noting that the optimal Bellman operator T is "-contractive in the sup-norm and Q* is the unique fixed point of T (Bertsekas et al. 1995).
THE NEURAL Q-LEARNING ALGORITHM
In this section, we start with brief review of Q-learning with linear function approximation. Then we will present the neural Q-learning algorithm.
4.1 Q-LEARNING WITH LINEAR FUNCTION APPROXIMATION
In many reinforcement learning algorithms, the goal is to estimate the action-value function Q(:,). which can be formulated minimizing the mean-squared Bellman error (MSBE) (Sutton & Barto 2018
[ (TQ(=, Q633
min Eu.,
Q(s, a))
(4.1)
where state is generated from the initial state distribution μ and action is chosen based on fixed learning policy т. To optimize (4.1). Q-learning iteratively updates the action-value function using the Bellman operator in B.I i... Qs+1(s, (Q,(s, a) for all (s, a) S x A. However, due to the large state and action spaces, whose cardinalities, i.e.. |S] and [A], can be infinite for continuous problems in many applications, the aforementioned update impractical. To address this
3

---

Under review as a conference paper at ICLR 2020
issue, linear function approximator is often used (Szepesvari 2010 Sutton & Barto 2018). where the vation-value function is assumed to be parameterized by a linear function, i.c., Q(s, a; 0) = Ó(s, 0 for any (s, E S x A. where @ S x A + R' maps the state-action pair to d- dimensional vector; and A E θ C TR is an unknown weight vector. The minimization problem in 4.1 then turns minimizing the MSBE over the parameter space O
4.2 NEURAL Q-LEARNING
Analogous to Q-learning with linear function approximation, the action-value function can also be approximated by a deep neural network to increase the representation power of the approximator. Specifically, we define a L-hidden-layer neural network as follows
f(0;x) = WLWLO (WL WW-1----. (--x)- .......... )....
(4.2)
where x _d is the input data, W Ruxd Wt E 1g and W, mmmx for | = 2, L 1, 0 = (vec(W) [1)) ..... vee( Wt) w))" TT is the concatenation of the vectorization of all parameter matrices, and (2) max(0, x} is the ReLU activation function. Then, we can parameterize (s, a) using deep neural network as ((s, 0) = f(0; a)). where 0 E O and ø S x A - in this paper. Let be an arbitrarily stationary policy. The MSBE minimization problem in (4. can be rewritten in the following form
Rd is a feature mapping. Without loss of generality, we assume that [|(((,.)) u))l
min F, [[Q(s, a; 0) (Q a; 0))²]- 00
(4.3)
Recall that the optimal action-value function Q" is the fixed point of Bellman optimality operator T which is 7-contractive. Therefore Q' the unique global minimizer of (4.3
The nonlinear parameterization of Q(::)) .) turns the MSBE in 4.3 to be highly nonconvex, which imposes difficulty in finding the global optimum 0" To mitigate this issue, we will approximate the solution of (4.3) by project the Q-value function into some function class parameterized by 0, which leads to minimizing the mean square projected Bellman error (MSPBE):
min E,,. [[Q(s, 0) - II=TQQ(>, a; 0)) BE
(4.4)
}} is some function class parameterized by O E O, and Hy is projection operator. Then the neural Q-learning algorithm updates the weight parameter 0 using the following projected descent step: 0,-1 [o (0.)) where the gradient term gx(O:) is defined as
where F (Q(:;;)) 0
(0.) = Val(Ors ax)) ()((() (88, ac)) - rt maxic ((0;; ((04)) ((8441
def Ae(st, Ct, 8141; V.) of ((s), a)),,
(4.5)
and A, is the temporal difference (TD) error. It should be noted that g: is not the gradient of the MSPBE nor an unbiased estimator for it. The details of the neural Q-learning algorithm displayed in Algorithm [ where Og is randomly initialized, and the constraint set is chosen to be θ B(O,, which defined as follows
B ((Oo, w)
def' {0- = (vec( (.) I)) ....,
"....,eee vec( ( /W, - w/ || S w. = I,...,, (4.6)
for some tunable parameter w. easy to verify that 0 -01 0113== IW, Will?.
CONVERGENCE ANALYSIS OF NEURAL Q-LEARNING
In this section, we provide a finite-sample analysis of neural Q-learning. Note that the optimization problem in (.4) is nonconvex. We focus on finding a surrogate action-value function in the neural network function class that well approximates Q*
5.1 APPROXIMATE STATIONARY POINT THE CONSTRAINED SPACE
To ease the presentation, we abbreviate s(0; Ø(8 a)) as (()) when no confusion arises. We define the function class Fe.m as collection of all local linearization of f(0) at the initial point 0g
Fe.m (S(00) (Ol)) 0 Oo) 0 E O).
(5.1)
4

---

Under review as a conference paper at ICLR 2020
Algorithm Neural Q-Learning with Gaussian Initialization
1: Input: learning policy т, learning rate (Te........... discount factor y, constraint set θ Ran- domly generate the entries of w from [(, 1/m), (= I,...,m
2: Initialization: 0g = (W
0
3: for O,............ ....., T do
4: Sample data (5t, az. Ft. S141) from policy π
5: A, = (0,; (18), at) (rt + maxse f(0;;
6: (+,) = fof(0: 0;; (88, at))
7: 0.+1 ll 0, 7, (.,)))))
8: end for
Following the local linearization analysis in Cai et al. (2019),, we define the approximate station- ary point of Algorithm [ as follows.
Definition 5.1 (Cai al. (2019)). point 0* θ is said to be the approximate stationary point
of Algorithm I iit for all 0 E O holds that
E p,,,, A8,, (VV of a)), 0 0*) 2
(5.2)
where F(0; Ó(, a)) f(0)= Fe.m and the temporal difference error Å is
(s,, a, s:;0) f(0; ois a)) (r(s, + maxied
(5.3)
For any E Fo.m. it holds that (Vof(0'), 0*) = (Vof(On), 0 - -0) = f(()) f(0)).
Definition 5.1 immediately implies
E,,,PP [[((0) TT( (T() - S(0'))] 20,
v E O.
(5.4)
According to Proposition 4.2 Cai al. 2019a). this further indicates f(0*) IT T).
In other words, f(0") is the unique fixed point of the MSPBE in 4.4 Therefore, we can show the convergence of neural Q-learning to the optimal action-value function Q' by first connecting it to the minimizer f(0*) and then adding the approximation error of Fe.m.
5.2 THE MAIN THEORY
Before we present the convergence of Algorithm I let us lay down the assumptions used throughout our paper. The first assumption controls the bias caused by the Markovian noise in the observations through assuming the uniform ergodicity of the Markov chain generated by the learning policy æ.
Assumption 5.2. The learning policy and the transition kernel P induce a Markov chain (se.t... such that there exist constants À 0 and p (0, satisfying
sup supsesdTv (P(ss -|s0 s), T) Ap', for all t 0,
Assumption 5.2 also appears in Bhandari et al. (2018): Zou et al. (0019)). which is essential for the analysis of the Markov decision process. The unitorm ergodicity can be established via the mi- norization condition for irreducible Markov chains (Meyn & Tweedie 2012 Levin & Peres 2017).
For the purpose of exploration, we also need assume that the learning policy π satisfies some regularity condition. Denote m (0) argmax, a oVoof( b), 0) for any 0 E O. Similar to
Melo et (2008); ; /ou al. (2019b): Chen et (019), we define
Σ, 1 1/mE E = 1/mmE Vel (0o; s, bmax (0) V (Bo; ; s, (m)
Vol [(0; 8, Vo (00: a,)
(5.5)
(5.6)
Note that E,, is independent of 0 and only depends on the policy π and the initial point Og in the definition of f. In contrast, Σ; (; ) defined based on the greedy action under the policy associated with O. The scaling parameter 1 1/m is used ensure that the operator norm of Σ,, to be in the order of (1). It is worth noting that E,, is different from the neural tangent kernel (NTK) or the Gram matrix in Jacot al. (2018): ; Du et al. (2019a); Arora et al. (2019), which
X matrices defined based on a finite set data points [(., 0, } I......- When f is linear, Σ, reduces to the covariance matrix of the feature vector.
5

---

Under review as a conference paper at ICLR 2020
Assumption 5.3. There exists constant such that Σ,, - E; > 0 for all @ and O..
Assumption555 5. also made for Q-eaarnin with linear function approximation in Melo et al. (2008);
Zou et al. (2019b); Chen et al. (2019). Moreover, Chen et al. (2019) presented numerical simulations to verify the validity of Assumption 5.3 Cai et al. (2019a) imposed a slightly different assumption but with the same idea that the learning policy should be not too far away from the greedy policy. The regularity assumption on the learning policy is directly imposed on the action value function in Cai et al. (2019a), which can be implied by Assumption 5.3 and thus is slightly weaker. We note that Assumption 5.3 can be relaxed to the one made in Cai et al. (2019a) without changing any of our analysis. Nevertheless, we choose to present the current version which more consistent
with existing work on Q-learning with linear function approximation (Melo et al. 2008 Chen et al., 2019).
Theorem 5.4. Suppose Assumptions 5.2 and 5.3 hold. The constraint set C is defined as in (4.6)
bya the step size in Algorithm 1 as r = 1/(2(1111)))) 1/2 m We set the radius as w = Com 1/2 1-
and the width of the neural network as m 2 C1 max (dI.2 (og.2 m/ 0), w 1/3 logg (m/ (w)))) where 5 E (0, 1). Then with probability at least 1 25 L22 exp( C2m3// over the randomness of the Gaussian initialization Oo it holds that
T-1 - E (f(o.) ( F(o)))
CogTTog(T/0)) log 1ylogmlog(T)) 3m//6
T
VT
PVT
where 8 = 1- a 11/2 E (0, 1) is constant, T minst = 0, 1.., S } is the mixing time the Markov chain {sc, ar) t=)... and {C= are universal constants independent of problem parameters.
Remark 5.5. Theorem 5.4 characterizes the distance between the output of Algorithm [ to the approximate stationary point defined in function class Fe.m. From (5.4), we know that f(0) is the minimizer of the MSPBE (4.4). Note that T* in the order of O 5.4 suggests that neural Q-learning converges to the minimizer of MSPBE with a rate in the order of (1og(())))) /VTT + log m TogT/m which reduces to 0(1/vT) when the width of the neural network is sufficiently large.
log Theorem
In the following theorem, we show that neural Q-learning converges to the optimal action-vatt value function within finite time if the neural network is overparameterized.
Theorem 5.6. Under the same conditions as in Theorem 5.4] with probability at least - 35
2 cxp( C/m L) over the randomness of 0p. it holds that
T-1 ((( Q* (s)))
3E (II Q'(s,a) (o.,a)))Q(ssa))"
1
Σ
(1-
VT
Cir" log(T/8) log + C2 C2log(T/0) log
/2
Bmm-6
where all the expectations are taken conditional on Oo Q" the optimal action-value function, 5 E (0, 1) and {Ci)i=o..... are universal constants.
The optimal policy x* can be obtained by the greedy algorithm derived based on Q" Remark 5.7. The convergence rate in Theorem 5.6 can be simplifies as follows
E[(Q(s, 0.) - Q" as. = ō B -"(s.)))((sss)))) + m//6 t=o
Q"
T
VT
The first term is the projection error of the optimal Q-value function the function class Fe which decreases to zero as the representation power of Fe, m increases. In fact, when the width m of the DNN is sufficiently large, recent studies (Cao & Gu 2019a 9a b) show that f(0) is almost linear around the initialization and the approximate stationary point f(0)) becomes the fixed solution of the MSBE (Cai et al. 2019a). Moreover, this term diminishes when the Q function is approximated by linear functions when the underlying parameter has a bounded norm (Bhandari et al., 2018 Zou let al. 2019b). As m goes to infinity, we obtain the convergence of neural Q-learnig to the optimal Q-value function with an O(1/VT) rate.

---

Under review as a conference paper at ICLR 2020
6 PROOF OF MAIN RESULTS
In this section, we provide the detailed proof of the convergence of Algorithm | presentation, write ((0;o(s, a)) as f(0; a) throughout the proof when no confusion arises.
To simplify the
We first define some notations that will simplify the presentation of the proof. Recall the definition of g.(+) in (4.5). For any 0 E O define the following vector-value map g that is independent of the data point.
g g E =. Vof(0: 8, (f(0,, 8, r(s, a) ymaxse f(0; b))),
(6.1)
where s follows the initial state distribution is chosen based on the policy rT(1ss and s' follows the transition probability P(-|s, a). Similarly, for all E θ we define the following gradient terms based on the linearized function f E Fe.m
m, (0) [(s,, Ge, 8t+1; ( ()), ( E,,,,, [A(s, s':
(6.2)
where A is defined in 5.3 and population version based on the linearized function.
Now we present the technical lemmas that are useful in our proof of Theorem 5.4 For the gradients
(.) defined in (4.5) and (-) defined in (6.2), we have the following lemma that characterizes the difference between the gradient of the neural network function f and the gradient of the linearized function f.
Lemma 6.1. The gradient of neural network function is close to the lincarized gradient. Specifically, if 0, E TB(@) w) and m and satisfy
m Co max (dL (m 08) -//3 log log(m/(w66)) and 1, 1m-mmmm-- 3/4 S w S C2 "(log
8/3
(6.3)
(1)ogm)= C2I.="(oggm)
then it holds that
(g: - m. (0).) 00) C3(2 + 7)w- 13 3 lo log(T/6)](0 0" ll2
+ (C4w4/3 4/3 2 11/3 hommmmloggg
log m + Cras L L' 110 - 0 12.
with probability at least 1 2 - exp( 0/3 2/3 over the randomness of the initial point, and llg:((; ||2 < (2+>)C7 / m (Tg(T/8) holds with probability at least 5 5 L 2/ L). where {C. > :0...... are universal constants.
The next lemma upper bounds the bias of the non-i.idd data for the linearized gradient map.
Lemma 6.2. Suppose the step size sequence {No, .........7. .r) is nonincreasing. Then it holds that
E [m, (0.) i 0.), 0, |00] s Co(mmog(TT)) + m²w?)r" (0,t7))0
for any fixed T. where Co > 0 is universal constant and 7" min(! 0, PApt S Wr }o is the mixing time of the Markov chain {st, az h
Since i is linear function approximator of the neural network function f. can show that the gradient of J satisfies the following nice property in the constrained set O
Lemma 6.3. Under Assumption
5.3 m(-) defined in (6.2) satisfies
m 0
m )
- 0*) 2 (1 - a a- 1/2 -1/2 -
AO E e.
Now we can integrate the above results and obtain proof of Theorem 5.4
Proof of Theorem
5.4 By Algorithm and the non-expansiveneess of projection Ie, have
| - 1
[lle (0, 7:gr) 0-
0: 7/8: 0-
10 0" 11
n/ ga 12 27p (gi, P: -").
(6.4)

---

Under review as a conference paper at ICLR 2020
We need to find an upper bound for the gradient norm and lower bound for the inner prod-
uct. According to Definition 5.T, the approximate stationary point 0 of Algorithm
| satisfies
m (0))) 0 - 0*) 2 0 for all 0 E Q The inner product in (6.4) can be decomposed into
(gr, O. 0*) (g: m0) 0. 0*) + (m:(0:) mm()), O2 0-) + (m(()), O, 0*)
(g: m, 0: - 0*) + (m: (0t) m())), 02 - 0-)
(m)))) m(0"), 0, 0*)
(6.5)
Combining results from and 6..5 we have
|0 -0
11 2 = 100
0 11 + ||g 2n
(gi m, 0r - 0*)
2n (m, (0.) m(,)) 0. 0*) 2n (m(0, mmmm)))) (00))..) 0*) (6.6)
1
Recall constraint set defined in 4.6). We have O BBO,, w) 10: |W, w/ 1|e S w, VI 1...., .}} and that m and w satisfy the condition in 66.3
Term I, is the error of the local linearization of f(0) on- By Lemma 6.1 with probability least
1 25 3 exp( C1332/3 L) over the randomness of the initial point 6g, we have
lg: m. (0.), 0, 0-) S C2(2
1/6 / log log(T/6)
(6.7)
holds uniformly for all 0,, 0 E O where we used the fact that w = Com-1/22 L-/44 9/4 Term I2 is the bias of caused by the non-i.id. data (st, dz 8141) used in the update of Algorithm 1 Conditional on the initialization, by Lemma 6.2 we have
E (m, (0.) m 0,), 0 - 00) S Cs(mlog(TT)) + m mm?")r" Mmax (D,t-7*)+
(6.8)
where T" min = 0, 1, ... D'p S (r} is the mixing time of the Markov chain (8t, 0r ( t
Term 13 the estimation error for the linear function approximation. By Lemma 6.3 we have
(m())) m(0)) ), 02 0*) 3E [(f(O.) -((00)
(6.9)
where B = =( a1-a-1/ 1/2) E (0, 1) is a constant. Substituting 6.7p. (6.8) and 6.99 into 6.6 we have
holds that
10++1 0-1 < 10, 0 + (
(2 + 1 (0tx
2n,, 3E -(())
(6.10)
I.) over the randomness of the initial point Og, where we used the fact that |g:]| < C2 + 7) m log from Lemma 6.1 Rearranging the above inequality yields
with probability at least 1 - 25 37,2
B[( - -(0r))² <
0, 0" 1
0.+1 0
C2(2 + 7)m 1/6 log m log(T/8)
2,81
B
Ca(2 + 2m log log(T/8)m
Cam(log(T/8) + mw²)) "max))000000
B
2/3 L) over the randomness of the initial point 0g. Recall the choices of the step sizes 170 = = 7r = 1/(2mmVT) and the radius w
with probability at least 1 - 26 31
Com 1/2 L 9/4 Dividing the above incquality by T and telescoping it from = 0 to T yields
T
E [ - f(0))) 0ul < ml|Ou - 1
C2(2 + 7)m 1/6 log m (Tg()
T t=
VT
C4(2 + 7)2 2 log (T)( log Ca(log(T/8)) + 1)T" log T
/T
3VT
8

---

Under review as a conference paper at ICLR 2020
For Uu. 0" E O again by Cm 1 9/4 we have ||0u - 00 - 1/m. Since f()) Fe.m.
holds with probability at least 28 -3,2 of the initial point 0g that
by Lemma 6. 1
over the randomness
E[(((.))) - 100) -=(()))-700))00
Cir log
C2 logomm m (Tg(T 3mm//6
VT
8VT
where we used the fact that 7 < 1. This completes the proof.
CONCLUSIONS
In this paper, we provide the first finite-time analysis of Q-learning with neural network function approximation (i.e., neural Q-learning), where the data are generated from a Markov decision pro- cess and the action-value function is approximated by deep ReLU neural network. We prove that neural Q-learning converge to the optimal action-value function up to the approximation error with O(1/VT) rate, where T is the number of iterations. Our proof technique is of independent interest and can be extended to analyze other deep reinforcement learning algorithms. One interesting fu- ture direction would be to remove the projection step in our algorithm by applying the ODE based analysis in Srikant& & Ying (2019); Chen et al. (2019).
Chen
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In Advances in neural information processing systems, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li. and Zhao Song. convergence theory for deep learning via over- paramcterization. In International Conference on Machine Learning, pp. 242-252, 2019b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pp. 1691-1692, 2018
Vivek S Borkar and Sean P Meyn. The ode method for convergence stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
Qi Cai, Zhuoran Yang, Jason D) Lee, and Zhaoran Wang. Neural temporal-differenc learning con- verges to global optima. In Advances Neural Information Processing Systems, 2019a.
Tianle Cai, Ruiqi Gao, Jikai Hou, Siyu Chen, Dong Wang, Di He, Zhihua Zhang, and Liwei Wang. A gram- gauss- method learning overparameterized deep neural networks for regression problems. arXiv preprint arXiv: 1675, 2019h.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint axxiv:1902.01388. 2019a.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, 2019b.
Zaiwei Chen, Sheng Zhang, Thinh T. Doan, Siva Theja Maguluri, and John-Paul Clarke. Perfor- mance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint 1 1425, 2019.

---

Under review as a conference paper at ICLR 2020
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in neural information processing systems. pp. 3036-3046, 2018.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Adithya M Devraj and Sean Meyn. Zap q-learning. Advances in Neural Information Processing Systems, pp. 2234-2244, 2017.
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, pp- 1675- 1685, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019b. URL
net. net./ wtteee/ooormmmmdlll.......
Bin Hu and Usman Ahmed Syed. Characterizing the exact behaviors of temporal difference learning algorithms using markov jump linear system theory. arXiv preprint urXiv:1906.0678) 2019.
Tommi Jaakkola, Michael Jordan, and Satinder P Singh. Convergence of stochastic iterative dy- namic programming algorithms. In Advances in Neural Information Processing Systems, pp. 703-710, 1994.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. In Advances in neural information processing systems, pp. 8571- 1- 8580, 2018
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, al. Scalable deep reinforce- ment learning for rision-basee robotic manipulation. In Conference on Robot Learning, pp. 651- 673, 2018.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pp. 1008-1014, 2000.
Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pp. 1347-1355, 2018.
David Levin and Yuval Peres. Markov chains and mixing times, volume 107, American Mathe- matical Soc., 2017.
Sergey Levine, Nolan Wagener, and Pieter Abbeel. Learning contact-rich manipulation skills with guided policy search. In 2015 IEEE International Conference Robotics and Automation (ICRA), pp. 156-163. IEEE, 2015.
Bo Liu, Ji Liu, Mohammad Ghavanzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient algorithms. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pp. 504-513. AUAI Press, 2015.
Prashant Mehta and Sean Meyn. Q-learning and pontryagin's 's minimum principle. In Proceedings of the 48h IEEE Conference Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pp. 3598-3605, 3605. IEEE, 2009.
Francisco S Melo, Sean Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th International Conference on Machine Learning, pp. 664-671. ACM, 2008.
Sean Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
10

---

Under review as a conference paper at ICLR 2020
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning, Nature, 5 518(7540):529, 2015.
Rémi
Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(May):8 185-857, 2008.
Dirk Ormoneit and Šaunak Sen. Kernel-based reinforcement learning. Machine learning, 49(2-3): 161-178, 2002.
Theodore J Perkins and Mark D Pendrith. On the existence of fixed points for q-learning and sarsa in partially observable domains. In Proceedings of the Nineteenth International Conference Machine Learning, pp. 490-497. Morgan Kaufmann Publishers Inc., 2002.
Martin Riedmiller. Neural fitted q iteration-first experiences with data efficient neural reinforce- ment learning method. European Conference on Machine Learning, pp. 317-328. Springer, 2005.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 61:85-117, 2015.
Wilko Schwarting, Javier Alonso-Mora, and Daniela Rus. Planning and decision-making for au- tonomous vehicles, Annual Review of Control, Robotics, and Autonomous Systems, 2018.
Shai Shalev-Shward Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. CoRR, abs/1610.03295, 2016. URL [tllatttp/axxiv.
abs/1610 03295
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, loannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484-455 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature. 550(7676):354, 2017.
Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and td learning. arXiv preprint arXiv:1902.0092: 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvari. Algorithms for reinforcement learning. Synthesis lectures on artificial intelli- gence and machine learning, 4(1):1-103, 2010.
John Tsitsiklis and Benjamin Van Roy. Analysis of tefporal-diffference learning with function approximation. In Advances in Neural Information Processing Systems, pp. 1075-1081, 1997.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-
learning. In Thirtieth AAAI conference on artificial intelligence, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Ducling network architectures for deep reinforcement learning. In International Conference on Machine 2016.
Learning, pp.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):77-299, 1992.
Zhuoran Yang, Yuchen Xie, and Zhaoran Wang. A theoretical analysis of deep q-learning. arXiv preprint XrXiv:1901.00133 2019.
Difan Zou and Quanquan Gu. An improved analysis training over permeerraeteii deep neural networks. In Advances in Neural Information Processing Systems, 2019.
11

---

Under review as a conference paper at ICLR 2020
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 2019a.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa and q-learning with linear function approximation. In Advances in Neural Information Processing Systems, 2019b.
12

---

Under review as a conference paper at ICLR 2020
A PROOF OF THEOREM 5.6
Before we prove the global convergence of Algorithm 1 we present the following lemma that shows that near the initialization point Qn the neural network function f(0: x) is almost linear in 0 for all unit input vectors.
Lemma A.1 (Theorems 5.3 and 5.4 Cao & Gu (2019a)) Let 0, (w)) the initial point and (W(I) W E 18(0, w) be a point in the neighborhood of Oo. If
[1JT
y be
m C1 max lo(md/ooogm/m)mmmm__ -/ (g(m/((w6)) and S C2L -2og m) m) 3/2 m)-3/2
then for all x Sd-1, with probability at least 1 it holds that
(f(0:x) - f(0;x)) L3/3 log m
| w CCL m Σ w w
Under the same conditions on m and w. if 0, (B w) for all 1,... , T, then with probability at least 1 - 6, we have [f(0; ((s,, at))l s C4 C4/log(T/0) for E [7].
Proof of Theorem 5.6 By triangle inequality, it holds that
Q(s.a;0r) (s, S f(Or:s, - f f(Or;s,a) ;,0";,,a)
+ f(00 :..a) (s)
(A.1)
Recall that i(0': ; the fixed point of 7 and Q' (.,)) is the fixed point of T. Then we have [[00s,,0) Q" a) = |8(0"; ;000;,,00 ;, - II m (' a) + II (3) (" a))
II [f(0":s,0) II TQ (s, a) IIFa. (s, as.
F Tf(0": - -II TQ a) + [ m. (s, (s)
S = (s) [ (s, (s,
where the first inequality follows the triangle inequality and in the second inequality used the fact that Fl T is c-cottractvve. This further leads to
f-- a) Q" a)l < [ (s, Q" (s, a)]-
To simplify the notation, we abbreviate El- as B[. in the rest of this proof. Therefore, we have
([((ss, ar)) - (s)
s 3D (f f(or,,,)) -)
+3E((((0ss.a) -')
< 3R ({(Or(,)))))) i(0r: ,, a)) 9 3B + f(0
+ 3(1 3 ( Q' a) (s, 11
By Lemma A.I and the parameter choice that C1 C1/LVLL" 1/4), we have
[[ff(0r:so) - f(Or:s, a)) < C2( L m mmlogm) m) < / C2m 1/3 log m
with probability at least 6. Combining the above result with Theorem 5.4 we have
3E [I1 m Q' Q" (s.
E[(Q(s, 0r) -((,)))))
71- + C2T log(T/5) log
VT
C3 Colog(T) /8) logm
B/TT
Bmm166
with probability at least - 35 1.2 (C00--Cmm//,, which completes the proof.
13

---

Under review as a conference paper at ICLR 2020
B
PROOF OF SUPPORTING LEMMAS
B.1 PROOF OF LEMMA 6.1
Before we prove the error bound for the local linearization, we first present some useful lemmas from recent studies of overparameterized deep neural networks. Note that in the following lemmas, {Ci)e=1... are universal constants that are independent of problem parameters such as d, 0, m, and their values can be different in different contexts. The first lemma states the uniform upper bound for the gradient of the deep neural network. Note that by definition, our parameter 0 a long vector containing the concatenation of the vectorization of all the weight matrices. Correspondingly, the gradient of (0; x) is also a long vector.
Lemma B.1 (Lemma B.3 in Cao Gu (2019b)). Let E B(Qn, w) with the radius satisfying C,d8/2 3/2 I w I C2I. (lo.g m) 3/2 Then for all unit vectors in IRd, i.e. x E 5 the gradient of the neural network f defined in (4.2) is bounded as [ef(0; S Csym with
probability at least 1 - L Sap(-Camw2/0
The second lemma provides the perturbation bound for the gradient of the neural network function. Note that the original theorem holds for any fixed d dimensional unit vector x. However, due the choice of w and its dependency on m. and d, it is easy to modify the results to hold for all x E 5
Lemma B.2 (Theorem in Allen- Zhu et al. 2019b)). Let E [B(o..w) w) with the radius satisfying
Ci L, 3/2 m 3/2 (log m) 3/2 S C2L 9/2 (logm)
C2L-
Then for all 54-1, with probability least 1 exp(<C3mm 2/3 L) over the randomness of 0.. it holds that
[ef((0; vef(0ox S C/wt/3 L3 L logm Vef(0o:x)]1>
Now we are ready to bound the linearization error.
Proof of Lemma 6.7 Recall the definition of (0,), and m,,0.) in (4.5) and 6.. respectively. We have (0.) m; = Vef at) 8:41: 0.) - V Vef st a A(s (st, ae s441: ;141:00)11
s (Vo ar) V Ves(O at)) s111i 0c)112
80 01) A 88,,
As,, 8141i 01) 00))ll2 (B.1)
Since F(0) Fo.m. we have (0) f(0,) + Vol e 0o) and vof(0) vof Then
with probability at least - 22. cxp( 2/3 L), have
|| ( Sc. a.) - (0f a, or 8141 ; 0,)112
A(st, aes 8 0.)l (V a.) -
Sr, sr,
I 1/3 / m log m A ((8e az 0cb
where the inequality comes from Lemmas B.I and B.2 1 - 5, it holds that
By Lemma
A.I with probability at least
(Ss at s141; 0,)1 - (0 - max s0p; 8141, b) BEA
max
< (2 (333))al/og(TT/)
which further implies that with probability at least 1 - 5 - 212
we have
[Voof(;; st,
Vof(O a;)) ae, s 0.)112
$ (2 C 1/3 1/ 323//m log
lo log
For the second term in B. we have
VoJ (0 az) (A 8111; 0.) [ at 81+1; 0.))
14

---

Under review as a conference paper at ICLR 2020
())((; sr
Vo sc,
f(e;; sc, ai))
Vol 8r. ax)
f(0;; s111, b) max f(o:: st1.
max
bEA
bEA
V 0: 8c, an [f(0;: sc. 0z) a()
Vof 0,; 8t: 0t)ll2 max [(0; s1 f(0; 8111, BEA
(B.2)
By Lemma A.1 with probability at least 1 - 6 we have
18(0;; - I(0; 82, ae) 1/4/3 V log + CRw L /mm
for all (st, ae) E S x A such that | at) 12 = 1. Substituting the above result into (B.2)
and applying the gradient bound in Lemma B.I obtain with probability at least 5
L²
that
Ve ( ar, s141:0) - (ss a, s141: S 4/3 1//33 Vlog m + Cow L'm.
Note that the above results require that the choice of w should satisfy all the constraints in Lemmas A.1 and B.2 of which the intersection
B.1
2/2 L' 3/4 < CgL "log m)
Therefore, the error of the local linearization of (0.) can be upper bounded by
(g((,) m m0.)), 0: 0^) (2 (2)) 1/3 L m log m mogg 0" 00112 + (Csw 11/3 m log m + Cow L L'm) |0, - 0" 1|,
which holds with probability at least 25 3L exp( initial point. For the upper bound of the norm of ge. by Lemmas B.I and A.I
2/3 m over the randomness of
we have
lgg ll2 Vo St, ac) (f(0;ss,))) ())
f(O,; 56+ 6))
- Tr ? max BEA
(2 + 7) log(
holds with probability at least - 8 2 exp( -1 expp-C1mman 2/3
B.2 PROOF OF LEMMA 6.2
Let us define (0) (m.
0 0*), which characterizes the bias of the data. Different from the similar quantity Çe in Bhandari et al. (2018), our definition is based on the local lincarization of f. which essential to the analysis in our proof.
easy verify that E [m
m(6 for
any fixed and deterministic 0. However, it should be noted that [mm,, (0, 0 * m ( because
0, depends on all historical states and actions {sr, 0t, 8: 0
at-1. 19-1,,tt-1:-
and m depends on the
current observation {st, Gt 8;-1) and thus also depends on {8,-1: a1-1, 8 az-2,-.. Therefore, we need careful analysis of Markov chains to decouple the dependency between O, and m.(.).
The following lemma uses data processing inequality to provide information theoretic control of coupling.
Lemma B.3 (Control coupling, [Banddri et al. 2018)). Consider two random variables and Y that form the following Markov chain:
X 81+7
where / {0, 1, and >> Suppose Assumption 5.2 holds. Let X' and Y' be independent copies drawn from the marginal distributions P(X = & P(Y = Then for any bounded function h + E. holds that
and respectively, i.e., TPXX' = Y'
E T Y) E[h(X', Y'Ill < suu [h(s, s')
9,8'
15

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 6.2 The proof of this lemma is adapted from Bhandari al. (2018), where the result was originally proved for linear function approximation of temporal difference learning. We first show that (x) is Lipschitz. For any 0, 0' E B(On, w)), we have
(0) (e0) (m, (0) m (). 0 - 0*) (m. (mm))))) ). 0 -0) 6*)
(m, m 0) (m, m 0*)
(m. m ((())), -0), 0¹),
which directly implies
[G:(0) - (.(0') s (0) m, ( 1|22 10 0' ||2 + (m) m000)l2 110 0 ll2
+ ||m,((') m00')l 110 0'112-
By the definition of m., we have
mm (0) m.(0')l2
f(0'; = vo (f(0) s,a) (
-7(
max f(O;s', - max f(0'; (()):() BEA
DEA
(1+ 31+ 12112.
which holds with probability at least 1 - L (oxp(-Camw22/ D), where we used the fact that the neural network function is Lipschitz with parameter Caym by Lemma B.] Similar bound can also be established for (0) m, (0') in the same way. Note that for 0 B B(Ou, w) with w and m
satisfying the conditions in Lemma 6. we have by the definition in (6.2 that
(m)le) - (1F(0) ()) ()) + + max f(0: b [o)
< +20=+))0((0000=
< 2(2 -/2==))c[Cs/mm/log//
C3mw).
The same bound can be established for ||ml| a similar way. Therefore, we have (.))))) 0' 11, where L, defined as
L 0 L,
b, 2(1 + 7) + 2(2 VC + Cymw).
Applying the above inequality recursively, for all r 0,...,,, we have
(.))) s (((0=r) + Lm,L
0 - 0sll2 Σ i=t-
+ O2mw))m.
Σ T (B.3)
Next, we need to bound G (0.-r). Define the observed tuple O₂ = (st. az S141) as the collection of the current state and action and the next state. Note that 0,-, - 8t- - 8t -> O, forms a Markov chain induced by the target policy æ. Recall that m.(.) depends on the observation O,. Let's rewrite m0,, O.) (0). Similarly, we can rewrite (:) as <(0, Ot). Let Of and Où be independently drawn from the marginal distributions of O; and O respectively. Applying Lemma B.3 yields
B.3
E(((0 0,) ([((0, 0,1 < sup ((0,
8,0
where used the uniform mixing result in Assumption
5.2
By definition 0,_, and Oj are inde-
pendent, which implies E m0 0 mi and
Eiç(6 0,) = [m (m(,,,, 0₂) - 66,) 0 0")1[0"] = 0.
Therefore, for any O...., ...,, we have
((C)(0,)) s Eç,00--) + 2(2 +2-+2222/2///////////TCC + Csmw)
Σ m
i=t-T
16

---

Under review as a conference paper at ICLR 2020
sup Ap + + 212+)))((GG/////1(((77)) + Cymw)
(B.4)
Define T" as the mixing time of the Markov chain that satisfies
min(! 2, .Ap' S mr).
When S T", we choose f in B.4 and obtain
(O.) - Elç. + 2(2 CaCaaaCCaaCaaaoooocco + C3mw)em,L 22 +
C3mw))m....
where we used the fact that the initial point 0g is independent of {8t, Ct 81 O1-10 ................................ 80, ao) and thus independent (e()). When > T", we can choose = T" in B.4) and obtain
((.)) x 2mr + 2(2 CC < (m (T)) + "
+ C3mw)) 1/--7
where Č > O is a universal constant, which completes the proof.
B.3 PROOF OF LEMMA 6.3
Proof of Lemma 6.3
To simplify the notation, we use E, to denote Ep,x,,, namely, the expectation u,a (-1s)) and 8 P(-ss, a), in the rest of the proof. By the definition of m in 66.2
we have
(m) m0") ) 8*)
B [ -" 07)
[x(((s a) - V
>Ex ( max f(0; s', - max f(o ss Vef 00 07) beeAA
be
where in the first equation we used the fact that vof(0) vof for all 0 O and f Fe.m-
Further by the property of the local linearization of f at 0g we have
f(0:s, ;(0";,.0) (V) 0"),
(B.5)
which further implies
E [[ s, a) (o
1o]] = (0 0*) TE (( V a) 0o] (0 0*)
ml0
where Σn is defined in Assumption 5.3 For the other term, we define b (0)
=
argmaxbe 8'0;'', and bmax(0") = argmaxbe. 8(0); Then we have
1r. max F(0;s', s', max f(0 b)) (ef(Or;s, 07) DEA
bEA
Ex [[F(B:; s', bmax) f(0': binnw (Vof s. 0*)
(B.6)
For all (s, a, 8'), when
a), 0r) 2 0. B.6 can be upper bounded by
(f(0; s' bmax) f(0 ;8' b b(nax)) Vol( s,a, 0*)
(f(0:'' 5., bmax) ~0'0 Umax) + f(00; bmax) 7(0"; ;''
(Vo --0
0*)
$ (f(0;s' s', bmax) - f(o': ; s' bmax)) (Ve.
0*)
(0- 0*) Too((00 bruxx) /o. Vol
07)
(0 8r) Vos(Ou; 8 bmax)) )1 (oo (0 0²)
17

---

Under review as a conference paper at ICLR 2020
where the inequality comes from the optimality of baax and the last equality follows the fact that f(;: -) linear. When (Vof(Oois, s, 0*) O, using the same argument, can upper bound (B.6) as follows
(f(;; bmax) f(0"; 8 max (Vos(0o: 8, a), 0r)
(f(0;'', bmax) f(0;s 5 (max) + f(0; , max) - f(00; s mmxx) (Vo(((00)))))) 0*)
S (f(0; s', mmxx) f(0": s', b ) (Vof(00: a), 8*)
< [0 - 0*) VoJ(On; 8 maxx )1 oo. (0p; a) (0 0-)]-
Combining the above result, we have for all tuples (8, a, 8') it holds that
(f(0; s', mmxx) F(0'; max)) (0f
0*)
$ 10 0*) T Vef(Ou: s' m Vo (0 1²)
+ + 0²) (of m Vej(Ou: 8, a) (0 1
where we denote 1 = (f 8, a). 0-00 0*) 2 0} and 1 ( a). 0 00) < 0}.
Taking expectation over the above inequality and applying Cauchy-Schwarz inequality, we have
E [[((; bmax) - f(00;s* s' max) (Vof a). --0
V Ex ( max (e )*) Vef T s b)1) V E. | (Vef(( a) T -,))²
=m - 0- 01 (0-00)))) e.)
) | 0'
where we used the fact that Σ ( 0*) = 1/mB, Vo. /ol (0o; kmux) VoI 8, bmax) and
dmax a (Ou: s, b), 0 8*) according to (5.6) Substituting the above results
into
B.6 we obtain
E, [[ max f(0: s' b) max (() (o. 8*)] bEA
S <m|0 0" [x: (0-0 0 1=
which immediately implies
m 0 (.)) 0²) 2 ml 0' (10- 0 0'||x, - 110 0" 11 (0-00))))) 0r)
10 0" 12, - 0- [; (0 (0-
ml|0 0" ['
1 0 ||=, + 7/10 0- (--0--)))
2 m(1 a 1/2 110 0 1|,
= (1 - a 1/2 | (f f(0))) 0o)
where the second inequality is due to Assumption 5.3 and the last equation is due to [B.5) and the definition of E in (5.5).
18


Reviews:
[{"review_id": "HJxVNuXatB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a finite-time analysis of a neural Q-learning algorithm, where the data are generated from a Markov decision process and the action-value function is approximated by a deep ReLU neural network. When the neural function is sufficiently over-parameterized, the O(1/T) convergence rate is attained. \n\nPros: This paper makes theoretical contribution to the understanding of neural Q-learning. This is an important but difficult task. The recent finite-time analysis on Q-learning either assumes a linear function approximation or an i.i.d. setting in the neural Q-learning. This paper makes a first attempt to study the neural Q-learning with Markovian noise. Overall, this paper is very easy to follow.  \n\nCons: In spite of its theoretical contributions, this paper has a few major issues.\n\n1. The projection step relies on a parameter $\\omega$ which is unknown in practice. In theorem, $\\omega = C m^{-1/2}$ for some unknown constant $C$. It would be of practical interests to seek other proof techniques to avoid such projection step. For instance, Srikant and Yang (2019) and Chen et al. (2019) removed this projection step in the finite-time analysis of Q-learning with a linear function approximation. \n\n2. Assumption 5.3 is problematic for the considered neural Q-learning setting. The matrix $\\hat{\\Sigma}_{\\pi}$ is of a very large dimension in the order of $O(m^2) * O(m^2)$ where the width of the neural network $m$ is assumed to diverge in the Theorem 5.4 for the over-parameterization purpose. Given the diverging dimension scenario, it is problematic to ensure Assumption 5.3. Moreover, it is unclear how to verify this condition in practice. In the literature, Melo et al. (2008) and Zou et al. (2019b) assumed a similar condition, which is OK because in the Q-learning with linear function approximation, this matrix reduces to the covariance matrix of the feature vector. \n\n3. The error rate in Theorem 5.4 is an increasing function of the layer $L$ in DNN, which is counterintuitive. A typically practical observation is that a larger $L$ is better. \n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeNiNNRYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a finite time analysis of Q-learning with neural network function approximators across multiple layers and no iid assumption. \n\n[Pros]\n+ Provides a novel way to analyze Q learning with nn function approximators that can be applied to other algorithms (notably in my mind, TD in actor critic where iid assumptions are often violated). \n\n[Cons]\n+ The novelty is a bit unclear other than the non-iid assumption. We note that modern Q-learning tends to use batching so doesn't require much of an iid assumption anyways, but this allows for more robust proofs in TD settings with non-iid training.\n+ The paper was a bit dense and hard to follow, we suggest reducing p.8 to have more discussion with references to proofs in the Appendix as in Chen2019. \n+ As the authors admit in open commentary, there is a mistake to be fixed which needs to be reviewed before acceptance. I think there is value to this work, however, would require seeing the change to assess a revision.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1l0WBG3tB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\nThis paper studies the convergence of Q-Learning when a wide multi-layer network in the Neural Tangent Kernel (NTK) regime is used as the function approximator. Concretely, it shows that Q-learning converges with rate O(1/T) with data sampled from a single trajectory (non-i.i.d.) of an infinite-horizon MDP + a certain (stationary) exploration policy. \n\n[Pros]\nThe results in this paper improve upon recent work on the same topic. It is able to handle multi-layer neural nets as opposed to two-layer, prove a faster rate O(1/T), and handle non-iid data (as opposed to iid data where (s,a,r,s’) are sampled freshly from the beginning at each step.)\n\nThe paper is generally well-written. The results and proof sketches are well presented and easy to follow. The proof seems correct to me from my check, including the indicator issue pointed out in the comments which I think can be easily fixed (by explicitly writing out the indicator and thus the Cauchy-Schwarz will still apply.)\n\n[Cons]\nThe result in this paper seems more or less like a direct combination of existing techniques, and thus may be limited in bringing in new techniques / messages. Key technical bottlenecks that are assumed out in prior work are still assumed out in this paper with potentially different forms but essentially the same thing.\n\nMore concretely, the proof of the main theorem (Thm 5.4) seems to rely critically on Lemmas 6.2 and 6.3, both of which are rather straightforward adaptations of prior work:\n\nLemma 6.2 (concentration of stochastic gradients on linearized problem): Seems to me like almost the same as [Bhandari et al. 2018], expect that now the network is an affine function---rather than a linear function---of \\theta, where the additional constant term f(\\theta_0; s, a) depends on (s, a). \n\nLemma 6.3 (good landscape of linearized problem): Comparing with prior work (Theorem 6.3, Cai et al. 2019), this Lemma works by directly assuming out the property of the arg-max operator in Assumption 5.3, which has a slightly different form from, but is essentially the same thing as (Assumption 6.1, Cai et al. 2019). \n\nTo be fair, the paper has to deal with the linearization error of a multi-layer net, which is dealt with in Lemma 6.1 and should be valued. But still I tend to think the above adaptations are rather straightforward and technically not quite novel.\n\n[Potential improvements]\nI would like to hear more from the authors about the technical novelty in this paper, specifically how Lemma 6.1 - 6.3 compare with prior work. I would be willing to improve my evaluation if this can be addressed.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This was an extremely difficult paper to decide, as it attracted significant commentary (and controversy) that led to non-trivial corrections in the results.  One of the main criticisms is that the work is an incremental combination of existing results.  A potentially bigger concern is that of correctness: the main convergence rate was changed from 1/T to 1/sqrt{T} during the rebuttal and revision process.  Such a change is not trivial and essentially proves the initial submission was incorrect.  In general, it is not prudent to accept a hastily revised theory paper without a proper assessment of correctness in its modified form.  Therefore, I think it would be premature to accept this paper without a full review cycle that assessed the revised form.  There also appear to be technical challenges from the discussion that remain unaddressed.  Any resubmission will also have to highlight significance and make a stronger case for the novelty of the results.
Decision: Reject