A Theoretical Analysis of  Deep Q-Learning
Authors: Zhuoran Yang
Yuchen Xie
Zhaoran Wang
Venue:  (2020)
Keywords: reinforcement learning
deep Q network
minimax-Q learning
zero-sum Markov Game

Abstract: Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on a slight simplification of DQN that fully captures its key features. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by DQN. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players, which is deferred to the appendix due to space limitations.

Under review as a conference paper at ICLR 2020
A THEORETICAL ANALYSIS OF DEEP Q-LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the great empirical success deep reinforcement learning, its theoretical foundation less well understood. In this work. we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on the fitted Q iteration (FQI) algorithm with deep neural networks, which is slight simplification of DQN that captures the tricks of experience replay and target network used in DQN. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by FQI. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic eπror converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques experience replay and target network, which are crucial the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-Doo -DNN algorithm for zero-sum Markov game with players, which is deferred to the appendix due to space limitations.
INTRODUCTION
Reinforcement learning (RL) attacks the multi-stage decision-making problems by interacting with the environment and learning from the experiences. With the breakthrough deep learning, deep reinforcement learning (DRL) demonstrates tremendous success in solving highly challenging problems, such as the game of Go (Silver et al., 2016; 2017), robotics (Kober & Peters, 2012), and dialogue systems (Chen et al., 2017). In DRL, the value policy functions often represented as deep neural networks and the related deep learning techniques can be readily applied. For example, deep Q-network (DQN) (Mnih et al., 2015), asynchronous advantage actor-critic (A3C) and (Mnih et al., 2016) demonstrate superhuman performance in various applications and become standard algorithms for artificial intelligence.
Despite its great empirical success, there exists a gap between the theory and practice of DRL. In particular, most existing theoretical work on reinforcement learning focuses on the tabular case where the state and action spaces are finite, or the case where the value function is linear. Under these restrictive settings, the algorithmic and statistical perspectives of reinforcement learning well-understood via the tools developed for convex optimization and linear regression. However, in presence of nonlinear function approximators such deep neural network, the theoretical analysis of reinforcement learning becomes intractable as it involves solving highly nonconvex statistical optimization problem.
To bridge such a gap in DRL, we make the first attempt to theoretically understand DQN, which can be cast as an extension of the classical Q-learning algorithm (Watkins Dayan, 1992) that uses deep neural network to approximate the action-value function. Although the algorithmic and statistical properties of the classical Q-learning algorithm are well-studied, theoretical analysis of DQN is highly challenging due to its differences in the following aspects.

---

Under review as a conference paper at ICLR 2020
First, in online gradient-based cemporal-differees reinforcement learning algorithms, approximating the action-valus value function often leads to instability. Baird (1995) proves that this is the case even with linear function approximation. The key technique to achieve stability in DQN is experience replay (Lin, 1992; Mnih et al., 2015). In specific, a replay memory is used to store the trajectory of the Markov decision process (MDP). At each iteration of DQN, a mini-batch of states, actions, rewards, and next states are sampled from the replay memory as observations to train the Q-network, which approximates the action-value function. The intuition behind experience replay is to achieve stability by breaking the temporal dependency among the observations used in the training of the deep neural network.
Second, in addition to the aforementioned Q-network, DQN uses another neural network named target network to obtain an unbiased estimator of the mean-squared Bellman error used in training the Q-network. The target network is synchronized with the Q-network after each period of iterations, which leads to a coupling between the two networks. Moreover, even if we fix the target network and focus on updating the Q-network, the subproblem of training a neural network still remains less well-understood in theory.
In this paper, we focus on a slight simplification of DQN, which is amenable theoretical analysis while fully capturing the above two aspects. In specific, we simplify the technique of experience replay with an independence assumption, and focus on deep neural networks with rectified linear units (ReLU) (Nair & Hinton, 2010) and large batch size. Under this setting, DQN is reduced to the neural fitted Q-iteration (FQI) algorithm (Riedmiller, 2005) and the technique of target network can be cast as the value iteration. More importantly, by adapting the approximation results for ReLU networks to the analysis of Bellman operator, we establish the algorithmic and statistical rates of convergence for the iterative policy sequence obtained by DQN, As shown in the main results in $3, the statistical error characterizes the bias and variance that arise from approximating the action-value function using neural network, while the algorithmic error geometrically decays to zero as the number of iteration goes infinity.
Our contribution is two-fold. First, we establish the algorithmic and statistical errors of the neural FQI algorithm, which can be viewed as slight simplification of DQN. Under mild assumptions, our results show that the proposed algorithm obtains sequence of Q-networks that geometrically converges to the optimal action-value function up to an intrinsic statistical error induced by the approximation bias of ReL.U network and finite sample size. Second, as a byproduct, our analysis justifies the techniques of experience replay and target network used in DQN, where the latter can be viewed as the value iteration. In addition, we also extend our algorithm to zero-sum Markov games. Due to space limit, we defer these results the appendix.
Notation. For a measurable space with domain S, we denote by B(S, V) the set of measurable functions on S that are bounded by V in absolute value. Let P(S) be the set of all probability measures over S. For any E P(S) and any measurable function f: S - RR we denote by II the fn-norm of f with respect to measure v for p 2 1. In addition, for simplicity, we write I|lll for ll. - In addition, let (n))), ((n)),g(())))))) ((n)))()))))))))))))))))) h221 be two positive series. We write
s(m) S g(n) if there exists a constant C such that (n) I C. g(n) for all n larger than some 7kg E N. In addition, we write (m) x g(n) if f(n) S g(n) and g(n) S f(n).
2 BACKGROUND
In this section, we introduce the background. We first lay out the formulation of the reinforcement learning problem, and then define the family of ReLU neural networks.
2.1 REINFORCEMENT LEARNING
discounted Markov decision process is defined by tuple (S,A,,,,R,). Here S is the set of all states, which can be countable or uncountable, A is the set of all actions, P: S A P(S)
2

---

Under review as a conference paper at ICLR 2020
is the Markov transition kernel, R: X A - P(R) is the distribution of the immediate reward, and y E (0, 1) is the discount factor. In specific, upon taking any action E A at any state E S, P( [s, a) defines the probability distribution of the next state and R(- {s, a.) is the distribution of the immediate reward. Moreover, for regularity, we further assume that S is a compact subset of Ie which can be infinite, A = {a1,
} has finite cardinality M, and the rewards are uniformly bounded by Rmax. i.c., RR- |s, a) is supported on [maaax Amax] for any & E S and a E A.
policy T: + P(A) for the MDP maps any state S probability distribution m[||s) over A. For policy π, the corresponding value function V*: S + I. is defined as the cumulative discounted reward obtained by when the actions are executed according to S, that is,
(s) =
Σ
Rs
So = s,A, ~ St,) ~ P(-1S,,
(2.1)
t=
Similarly, the action-value function Q* :S x A + defined as
Q" (s) E
Σ
R4
So s, Ao A n(. SS,) P(. P(- Ai)
(2.2)
For any given action-value function Q: S x A - R. define the one-step greedy policy "Q any policy that selects the action with the largest Q-value, that is, for any E S, Te [s) satisfies
=o(a [)) = if Q(s,a) F max Q(s,a'). d'EA
(2.3)
Moreover, define operator p by
())
A4) - P(.
T(-15)]]
(2.4)
and define the Bellman operator T by (T (TT)) r)s + + a), where r(s, a) [rdddr s, a) the expected reward obtained state s when taking action a. Then it can be verified that Q" is the unique fixed point of T
The goal of reinforcement learning is to find the optimal policy, which achieves the largest cumulative reward. To characterize optimality, we define optimal action-valus value function Q" as
(' a) = sup Q" (s,
(2.5)
where the supremum is taken over all policies. Based on Q", we define the optimal policy n² as any policy that greedy with respect to Q*. can be shown that Q Q" Finally, we define the Bellman optimality operator T via
(TQ) a) = r(s,a) + max Q(S (s)s,'')5 P(.( ''EA
(2.6)
Then we have Bellman optimality equation TQ" = Q"
2.2 DEEP NEURAL NETWORK
We study the performance of DQN with rectified linear unit (ReLU) activation function (u) max(u, 0). For any positive integer L and {d N, a ReLU network f: R + R with L hidden layers and width {d,) 1+1 is of form
L++1
f(x) W (W (W. oW2o 01) ... v.) vL),
(2.7)
where We E didexde- and U2 E de are the weight matrix and the shift vector in the b-th layer, respectively. Here we apply a to to each entry of its argument in (2.7). deep learning, the network structure fixed, and the goal to learn the network parameters (weights) (We, ue (e) with the convention that U = O. For deep neural networks, the number of parameters greatly exceeds the input dimension dg- To restrict the model class, focus on the class of ReLU networks where most parameters zero
3

---

Under review as a conference paper at ICLR 2020
Definition 2.1 (Sparse ReLU Network). For any L.s e N.
{dz} 1-+1 CN, and V > O, the family of
sparse ReI.U networks bounded by V with I. hidden layers, network width d, and weight sparsity is defined as
(1.,1)) F(L, (4,) 8 V)= =
max EE|L-1]
Well 1
Σ 8=1
L+1
Wello S
max selde+1]
||Ssl s sv]. (2.8)
where we denote (We, ve) by We. Moreover, / in (2.8) is expressed as in (2.7), and ʃj is the j-th component of f.
Here we focus on functions that are uniformly bounded because the value functions in (2.1) and (2.2) are always bounded by Vmax Rmax/ (1 - 7). In the sequel, write F(L, as F(L, {d, 1 s) to simplify the notation. In addition, we restrict the networks weights to be sparse, i.e., s is much smaller compared with the total number of parameters. Such an assumption implics that the network has sparse connections, which are useful for applying deep learning in memory-constrained situations such as mobile devices (Han et al., 2015; Liu et al., 2015).
s, Vmax)
Moreover, we introduce the notion of Hölder smoothness as follows, which is generalization of Lipschitz continuity, and is widely used characterize the regularity of functions.
Definition 2.2 (Hölder Smooth Function). Let 'D be compact subset of R", where r E N. We define the set of Hölder smooth functions on D as
100 f(x) 0 (v) yl 8- 18]
C, H) f: D-::
Σ 100 fllo + <a|
sup F.VED wny ||||||=[||
Σ
S H
||
where 3 > 0 and H >> 0 are parameters and [B] the largest integer no greater than B. In addition. here use the multi-inder notation by letting aa) E N", and d = 0m 80.
Finally, conclude this section by defining functions that can be written a composition of multiple Hölder functions, which captures complex mappings in real-world applications such as multi-level feature extraction.
Definition 2.3 (Composition of Hölder Functions). Let E N and (p, he( S N be integers, and let {az, by }ett) C R such that ay < by j E [4]. Moreover, let gy: [ay, 6y10 + [dz+1, b be function, Vj E [a]- Let (g))))=(p;= be the components of gn, and we assume that each gyk is Hölder smooth, and depends on at most i of its input variables, where t, could be much smaller than Pj. i.c. gis: E Ct2 ([a,, b,]3,, ,3, Hz). Finally, we denote by (((,) L, 3j: H2 sela) the family of functions that can be written as compositions of {gz Jee(g with the convention that Pq+1 1. That is, for any G(Ip,, 4, Bj, H4 belg)))) we can write
9g 99-1 92 91,
with g5k E Cr, (la,,,yl',,, H2) for each h E [p)+1] and j E [g]-
3 UNDERSTANDING DEEP Q-NETWORK
In the DQN algorithm, a deep neural network Qu: S x A + R is used approximate Q', where 0 is the parameter. For completeness, state the DQN as Algorithm 2 in SA. As shown in the experiments in Mnih et al. (2015), two tricks are pivotal for the success of DQN.
First, DQN use the trick of experience replay (Lin, 1992). Specifically, at each time t, we store the transition (S,, Ar, Re, St41) into the replay memory M, and then sample a minibatch of independent samples from M to train the neural network via stochastic gradient descent. Since the trajectory of MDP has strong temporal correlation, the goal of experience replay is to obtain uncorrelated samples, which yields accurate gradient estimation for the stochastic optimization problem.
Another trick is to use target network Q8- with parameter 0+ Specifically, with independent samples ((5,, 0z Fi, x()) from the replay memory, to update the parameter 0 of the Q-network,
4

---

Under review as a conference paper at ICLR 2020
compute the target Y; r + y maX.E Qo- (5// a), and update @ by the gradient of
1 n Σ Yr Q0(8:;
((0)
(3.1)
Whereas parameter 0* is updated once every T Turget steps by letting 6" = 0. That is, the target network hold fixed for T Tugert steps, and is thus updated in slower pace.
To demystify DQN, it is crucial to understand the role played by these two tricks. For experience replay, in practice, the replay memory size is usually very large. For example, the replay memory size is 10th in Mnih et al. (2015). Moreover, DQN use the e-greedy policy, which enables exploration over S x A. Thus, when the replay memory is large, experience replay is close to sampling independent transitions from an explorative policy. This reduces the variance of the (L()), which is used to update 0.
Thus, experience replay stabilizes the training of DQN, which benefits the algorithm in terms of computation. To understand the statistical property of DQN, we replace the experience replay by sampling independent transitions from fixed distribution from the replay memory, we sample i..dd observations {(S, A.) hejai from o. Moreover, for any i E [n]. let R, and S be the immediate reward and the next state when taking action A; at state S, Under this setting, we have B(Y; S, A,) = (TQa- (S,,, where Qo- is the target network, which, as we show as follows, is motivated from a statistical consideration.
PPS A). That is, instead of sampling
Let us first neglect the target network and set 8* = 8. Using barsanari decomposition, the the expected value of T(()) in (3.1) is
E [T((O]] = 11Qa TQ + ( (S,,)(())))))) }
(3.2)
Here the first term in (3.2) is known the mean-square Bellman error (MSBE), and the second term is the variance of Y,. Whereas I(()) can be viewed as the empirical version of the MSBE, which has bias { - (TQ, }1) that also depends on 6. Thus, without the target network, minimizing L(0) can be drastically different from minimizing the MSBE.
To resolve this problem, we use a target network in (3.1), which has expectation
B[T(O)] = l1Qo TQo 11: + T [Yi (TQo- )S)) Ai)]"
where the variance of Y1 does not depend on 0. Thus, minimizing ((0) is close solving
minimize |QQ - TQQ== 11:. 0E0
(3.3)
where is the parameter space. Note that in DQN we hold 6* still and update 0 for Turget steps. When Turget is sufficiently large and we neglect the fact that the objective in (3.3) is nonconvex, we would update by the minimizer of (3.3) for fixed 6*.
Therefore, in the ideal case, DQN aims solve the minimization problem (3.3) with 6* fixed, and then update 0* by the minimizer 0. Interestingly, this view of DQN offers statistical interpretation of the target network. In specific, if (Qo: 0 E Q) is sufficiently large such that it contains TQ then (3.3) has solution Qe = TQ+., which can be viewed as one-step of value iteration (Sutton & Barto, 201 for neural networks. In addition, in the sample setting, Qø- is used to construct [Yi)eemn) which serve as the response in the regression problem defined in (3.1), with (TQ+-) being the regression function.
Furthermore, turning the discussion above into a realizable algorithm. we obtain the neural fitted Q-iteration (FQI) algorithm, which generates sequence of value functions. Specifically, let F be class of function defined on S x A. In the k-th iteration of FQI, let Q2 be current estimate of Q". Similar to (3.1) and (3.3), we define Y, R2 + 7 max.g. (5( a). and update Q2 by
Qu+1 argmin JEF
Y f(S, A.))
(3.4)
i=1
5

---

Under review as a conference paper at ICLR 2020
This gives the fitted-Q iteration algorithm, which is stated in Algorithm 1.
When F is the family of neural networks, Algorithm is known as the neural FQI, which is proposed in Riedmiller (2005). Thus, we can view neural FQI as an modification of DQN, where we replace experience replay by sampling from fixed distribution a, so as to understand its the statistical property. As a byproduct, such a modification naturally justifies the trick of target network in DQN. In addition, note that the optimization problem in (3.4) appears in each iteration of FQI, which is nonconvex when neural networks are used. However, since we focus solely on the statistical aspect, we make the assumption that the global optima of (3.4) can be reached, which is also contained F. Interestingly, recent line of research deep learning (Du et al., 2018b;a; Zou et al., 2018; Chizat & Bach, 2018 8; Allen-Zhu et al., 2018a;;; Jacot et al., 2018: Cao & Gu, 2019; Arora et al., 2019; Ma et al., 2019; Mei et al., 2019; Yehudai & Shamir, 2019) has established global convergence of gradient- based algorithms for empirical risk minimization when the neural networks are overparametrized. We provide more discussions on the computation aspect in $B. Moreover, we make the i.i.d. assumption in Algorithm to simplify the analysis. Antos et al. (2008b) study the performance of fitted value iteration with fixed data used in the regression sub-problems repeatedly, where the data sampled from a single trajectory based on fixed policy such that the induced Markov chain satisfies certain conditions on the mixing time. Using similar analysis as in Antos al. (2008b), our algorithm can also be extended to handled fixed data that is collected beforehand.
Algorithm Fitted Q-Iteration Algorithm Input: MDP A, P.P. R, 7), function class F, sampling distribution number of iterations K, number of samples the initial estimator Qo-
for k = 0, 1,,,,.....
do
Sample i.i.d. observations Ai), E [n]] from a, obtain Rg ~ R(- (8,, and S
P. A.).
Compute Y, R2 + 7 max @x(5),
Update the action-valus function:
Q++1 & argmin
-Ixx n1
- f(S,, A.)]
jeF
end for
Define policy TK as the greedy policy with respect to QK. Output: An estimator QK of Q" and policy иk.
4 THEORETICAL RESULTS
We establish statistical guarantees for DQN with ReLU networks. Specifically, let Q be the action-value function corresponding to πK. which is returned by Algorithm 1. In the following, we obtain an upper bound for Q - I1, where μ E P(S x A) allowed to be different from v. In addition, we assume that the state space is compact subset in IR" and the action space A is finite. Without loss of generality, we let = [0, 1]" hereafter, where a fixed integer. To begin with, we first specify the function class F in Algorithm 1.
Definition 4.1 (Function Classes). Following Definition 2.1, let F(L, (di)++t 8) be the family of sparse ReLU networks defined on S with do and dr 1. Then we define Fo by
Fo = =J: A R: f(, a) F(L, (d,) 8) for any a E A}.
(4.1)
In addition, let G((p), ty. 33. H1 H be set of composition of Hölder smooth functions defined on S C Rr. Similar to Fu. define function class Go as
Go (f: x f(;a) G(1p, 3g, H1 H1) for any A}.
(4.2)

---

Under review as a conference paper at ICLR 2020
By this definition, for any function E Fo and any action a A. f(.,a) is ReLU network defined on S, which is standard for Q-networks. Moreover, Go contains a broad family of smooth functions on S x A. In the following, we make mild assumption on Fo and Gu-
Assumption 4.2. We assume that for any J E Fo. we have Tʃ Go. where T is the Bellman optimality operator defined in (2.6). That is, for any F and any a E A, (T,) a) can be written as compositions of Hölder smooth functions
function of E S.
We remark that this assumption holds when the MDP satisfies some smoothness conditions. For any state-action pair (s, E x A, let P( s, a) be the density of the next state. By the definition of the Bellman optimality operator in (2.6), we have
[ [max f(' [''' P(s' a,dd''s.
(Tf) = r(s,(( a) +
(4.3)
''EE
For any s E 8 and E A, we define functions 91, 92 by letting g (s) = r(s, a) and g2(s) P(s' s, a). Suppose both 91 and are Hölder smooth functions on S = |0, 1]" with parameters B and H. Since ol I Vmmx. by changing the order of integration and differentiation with respect to in (4.3), we obtain that function s - (f,, a) belongs to the Hölder class (,, B, H') with H' H + Vmax). Furthermore, in the more general case, suppose for any fixed a E A. we can write P(s' ss a) as h [h2(s, a), hs(s'),, where h2: S R", and h3: S - IR"2 can be viewed as feature mappings, and h1: I2" r2 + a bivariate function. We define function h4: R + R by
h4(4) / [max f(s,, a²)] h1 hss(s))ds'. ''EA
Then by (4.3) we have (Tf)(s, a) = (s) + h4 h2(s, a). Then Assumption 4.2 holds if h4 is Hölder smooth and both and h2 can be represented as compositions of Hölder functions. Thus, Assumption 4.2 holds both the reward function and the transition density of the MDP are sufficiently smooth.
Moreover, even when the transition density not smooth, we could also expect Assumption 4.2 to hold. Consider the extreme case where the MDP has deterministic transitions, that is, the next state s' is function of and a, which is denoted by s' h(s,a). In this case, for any ReLU network have (s,)) = r(s,a) + max E. / [[((( a)) Since
max f(1 d') - max f(2,, a') S max f(1, d') - f(2,,a)) d'EAA
e'EAA
d'EAA
for any 81, 82 E S, and network f(, a) is Lipschitz continuous for any fixed a E A, function mi (s) = max,' [(x,, a') is Lipschitz on S. Thus, for any fixed a E AA if both gi (s) = r(s, a) and m²(s) h(s, a) are compositions of Hölder functions, so is (T)) a) (s) + mm m))s). Therefore, even if the MDP has deterministic dynamics, if both the reward function r(s, a) and the transition function h(s, a) are sufficiently nice, Assumption 4.2 still holds true.
In the following, we define the concentration coefficients, which measures the similarity between two probability distributions under the MDP.
Assumption 4.3 (Concentration Coefficients), Let v1, 1/2 E P(S x A) be two probability measures that are absolutely continuous with respect to the Lebesgue measure on S A. Let ( be sequence of policies. Suppose the initial state-action pair (So, Ag) of the MDP has distribution Vi, and we take action A, according to policy ne. For any integer m, denote by pm pTm-t p v the distribution of (Sm, Am). Then we define the m-th concentration coefficient as
d (P p4m-1 pr v1)
11
27 1/2
(1m;;,,24)
sup
E
(4.4)
du
where the supremum is taken over all possible policies.
Furthermore, let a be the sampling distribution in Algorithm and let μ be a fixed distribution on x A. We assume that there exists a constant 6p.o < 00 such that
(1 7), Σ m- <(m; ,l, (), S &p.a;
(4.5)
m21
where (1 21 in (4.5) is normalization term, since Emz1 m- (1 -2
7

---

Under review as a conference paper at ICLR 2020
By definition, concentration coefficients in (4.4) quantifies the similarity between My and the dis- tribution of the future states of the MDP when starting from V1- Moreover, (4.5) is standard assumption in the literature. See, e.g., Munos & Szepesvári (2008); Lazaric et al. (2016); Scherrer et al. (2015); Farahmand et al. (2010; 2016). This assumption holds for large class of systems MDPs and specifically for MDPs whose top-Iyyapunov exponent is finite. See Munos & Szepesvári (2008); Antos et al. (2007) for more detailed discussions on this assumption.
Now we are ready to present the main theorem.
Theorem 4.4. Under Assumptions 4.2 and 4.3, let Fo be defined (4.1) based on the family of sparse
ReLU networks F(L", {d) ) ,5*) and let Go be given (4.2). Moreover, for any j [q 1]. we define 3 - 3j -I= min(3e, 1); let 3g 1. In addition, let a* maxxelul (283 3 (t) For the parameters of Go. assume that there exists constant & >> 0 such that
max 1 S. JC
Σ jE
log', X n)5 and max P5 X (logn)5. jE
(4.6)
For the hyperparameters L" [d and 8 of the ReLU network, we set dj = 0 and di,,41 1.
Moreover, we set L S (logn)5
max tj} n S min dj S max dj S ne, ]E0/
and x""n" (logn)8
(4.7)
jELL
for some constant 5' O. For any K E N, let QT* be the action-value function corresponding to policy тk. which returned by Algorithm based on function class Fo. Then there exists constants E* and C' such that
||Q - Q SC
0 7 (1 7)2
|A| (logn)s' 'n(a' 11/2
4 4
Raaxx
(4.8)
(1-
This theorem implies that the statistical rate of convergence the sum of a statistical error and an algorithmic error. The algorithmic error converges to zero in linear rate as the algorithm proceeds, whereas the statistical error reflects the fundamental difficulty of the problem. Thus, when the number of iterations satisfy
K K²C' [log] + (1-a") -log) log(1/>)
iterations, where C' is sufficiently large constant, the algorithmic error is dominated by the statistical error. In this case, if we view both and Φu.o constants and ignore the polylogarithmic term, Algorithm achieves eтror rate
|A| n (a" (a" 11/2 = [A| max (2/
(4.9)
JE(n]
which scales linearly with the capacity of the action space, and decays to zero when the n goes to infinity. Furthermore, the rates {n -85 92/(22 ( Jjet( in (4.9) recovers the statistical rate of nonparametric regression in fn-norm, whereas our statistical rate na 11//2 in (4.9) is the fastest among these nonparametric rates, which illustrates the benefit of compositional structure of Go.
Furthermore, concrete example, we assume that both the reward function and the Markov transition kernel are Hölder smooth with smoothness parameter B. As stated below Assumption 4.2, for any f E Fo. have (-) C, H'). Then Theorem 4.4 implies that Algorithm I achieves error rate - -9/(288++ when K is sufficiently large. Since |A| is finite, this rate achieves the minimax-optime
statistical rate of convergence within the class of Hölder smooth functions defined on [o, 1] (Stone, 1982) and thus cannot be further improved.
In addition, as simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players. Specifically, in this setting, there are two players with action spaces A and B. The action-valus function Q" a, b): correspond the value obtained by pair of policies that constitute the Nash equilibrium. Minimax- DQN differs from the original DQN mainly in the computation of target, which is obtained by solving
A x B - R can be similarly defined, which
8

---

Under review as a conference paper at ICLR 2020
zero-sum matrix game via linear programming. Using similar proof technique, establish both the algorithmic and statistical convergence rates of the action-value functions associated with the sequence of policies returned by the Minimax-DQN algorithm. Due to space limit, we defer the algorithm and its theory to $E.1 in the appendix.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv: 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.03396. 2018b.
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009.
András Antos, Csaba Szepesvári, and Rémi Munos. Value-iteration based fitted policy iteration:
learning with a single trajectory. In IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, pp. 330-337. IEEE, 2007.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration continuous action-space mdps. In Advances neural information processing systems, pp. 9-16, 2008a.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129) 129, 2008b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: 2019.
Kai Arulkumaran, Marc Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. A brief survey of deep reinforcement learning, arXiv preprint arXiv:1708.0588 2017.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Peter I. Bartlett.
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions Information Theory, 44(2):525-536, 1998.
Peter L Bartlett Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems, pp. 190-196, 1999.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky, Sperttally-normalizedd margin bounds for neural networks. Advances in Neural Information Processing Systems, pp. 6241-6666666 12250, 2017a.
Peter L Bartlett, Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pscudodimension bounds for piecewise linear neural networks. arXiv preprint arXiv:1703.02993 2017b.
Benedikt Bauer, Michael Kohler, et al. On deep learning as a remedy for the curse dimensionality in nonparametric regression. The Annals of Statistics, 47(4):2261-228 2019.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Michael Bowling. Rational and convergent learning in stochastic games. In International Conference on Artifiical Intelligence, 2001.
Justin A Boyan. Technical update: Least-squares temporal difference learning. Machine Learning,
49(2-3):23-246, 2002.
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1-3):33-57, 1996.
10

---

Under review as a conference paper at ICLR 2020
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning parameterized deep relu networks. arXiv preprint arXiv: 2019.
Hongshen Chen, Xiaorui Liu, Dawei Yin, and Jiliang Tang. A survey on dialogue systems: Recent advances and new frontiers, arXiv preprint arXiv:/711.01731, 2017.
Lenaic Chizat and Francis Bach. A note lazy training in supervised differentiable programming. arXiv preprint arXiv: (812.0891 2018.
Vincent Conitzer and Tuomas Sandholm. AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Muchine Learning, 67(1-2):23-43 43, 2007.
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 1010111111.00... 2018 10.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810002054 2018b.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint orXivv:703..11 1008, 2017.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6(Apr):503-555) 2005.
Jianqing Fan, Cong Ma, and Yiqiao Zhong. A selective overview of deep learning. arXiv preprint arXiv:9904005526, 2019.
Amir-massoute Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Regular- ized fitted Q-iteration for planning in continuous-space Markovian decision problems. In American Control Conference, pp. 725-730. IEEE, 2009.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, pp. 568-576, 2010.
Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor, Reg- ularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research, 17(1):8099-4877 2016.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. arXiv preprint 127, 2019.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint 1rXiv:1712.06541, 2017.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint
2015.
Matthew Hausknecht and Peter Stone. Deep recurrent Q-learning for partially observable mdps. In 2015 AAAI Fall Symposium Series, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571 8580, 2018
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint
2017.
11

---

Under review as a conference paper at ICLR 2020
Jason M Klusowski and Andrew R Barron. Risk bounds for high-dimensional ridge function combinations including neural networks. arXiv preprint arXiv: 167.00134.444
Jens Kober and Jan Peters. Reinforcement learning in robotics: A survey. In Reinforcement Learning, pp. 579-610. Springer, 2012.
Michail Lagoudakis and Ronald Parr. Value function approximation in zero-sum markov games. In Uncertainty Artificial Intelligence. pp. 283-292, 2002.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of machine learning 2003.
research, 4(Dec): 107-1149, 107119:1177-1199,
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement /eanfor. In Reinforcement learning, pp. 45-73. Springer, 2012.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Finite-sample analysis of least- squares policy iteration. Journal of Machine Learning Research, 13(0ct):3041-3074 2012.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Analysis of classification- policy iteration algorithms. The Journal of Machine Learning Research, 17(1):583--0) 612, 2016.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent structured data. In Advances in Neural Information Processing Systems, pp. 8157-8166. 2018.
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher Rao metric, geometry, and complexity of neural networks. arXiv preprint 1rX1::171.001500,
2017. 2017.
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learming, 8(3-4):293-322 1992.
Michael Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pp. 157-163. Elsevier, 1994.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse convolu- tional neural networks. Conference on Computer Vision and Pattern Recognition, pp. 806-814, 2015.
Ruishan Liu and James Zou. The effects of memory replay in reinforcement learning. arXiv preprint arXiv:1710.06574. 2017.
Chao Ma, Lei Wu, et al. A comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynamics. arXiv preprint 1rXiv:1904.04333
2019.
Wolfgang Maass. Neural nets with superlinear VC-dimension. Neural Computation, 6(5):877-884, 1994.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. arXiv preprint arXiv: 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 51 51877540):529-533, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference Machine Learning, pp.
2016.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT Press, 2012.
12

---

Under review as a conference paper at ICLR 2020
Rémi Munos and Csaba Szepesvári. Finite-time time bounds for fitted value iteration. Journal of Machine Learning Research, 9(May):815-88) 2008.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In International conference on machine learning, pp. 807-814, 2010.
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-SGD: Path-normalized opti- mization deep neural networks. Advances Neural Information Processing Systems, pp. 2422-2430, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015b. 2015b.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A PAC- Bayesian approach to apeotrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564. 2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5949-5958,
2017b.
Stephen David Patek. Stochastic and shortest path games: theory and algorithms. PhD) thesis, Massachusetts Institute of Technology, 1997.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming two-player zero-sum markov games. In International Conference on Machine Learning (ICML 2015), 2015.
Julien Pérolat, Bilal Piot, Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. Softened approximate policy iteration for markov games. In International Conference Machine Learning, 2016a.
Julien Pérolat, Bilal Piot, Bruno Scherrer, and Olivier Pietquin. On the use of non-stationary strategies for solving two-player zero-sum markov games, In International Conference on Artificial Intelligence and Statistics, pp. 893-901, 2016b.
Julien Pérolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultaneous move multistage games. In International Conference on Artificial Intelligence and Statistics, 2018.
HL Prasad, Prashanth LA, and Shalabh Bhatnagar. Two-timescale algorithms for learning Nash equilibria in general-sum stochastic games. In International Conference on Autonomous Agents and Multiagent Systems, pp. 1371-1377 International Foundation for Autonomous Agents and Multiagent Systems, 2015.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, pp. 1177-1184, 2008
Martin Riedmiller. Neural fitted Q iteration experiences with a data efficient neural reinforcement learning method. In European Conference Machine Learning, pp. 317-328. Springer, 2005.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. International Conference Learning Representations, 2016.
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game tetris. Journal of Machine Learning Research, 16:1629-1676. 2015.
Johannes Schmidt-Hieber Nonparametric regression using deep neural networks with ReLU activa- tion function. arXiv preprint arXiv: 1781v:1708.06633 2017.
13

---

Under review as a conference paper at ICLR 2020
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 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.
Sriram Srinivasan, Mare Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environments. In Advances Neural Information Processing Systems, pp. 3426-3433 2018.
Charles J Stone, Optimal global rates of convergence for nonparametric regression. The Annals of Statistics, pp. 1040-1053, 1982.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT Press, 2011.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pp. 1057-1063, 2000.
Taiji Suzuki. Adaptivity of deep relu network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:1810.08033, 2018.
Manel Tagorti and Bruno Scherrer. On the rate of convergence and error bounds for LSTD (A), In International Conference Machine Learning, pp- 1521-1529, 2015.
Samuele Tosatto, Matteo Pirotta, Carlo D' Eramo, and Marcello Restelli. Boosted fitted Q-iteration. In International Conference on Machine Learning, pp. 3434-3443, 2017.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. In AAAI Conference Artificial Intelligence, 2016.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton University Press, 1947.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International Conference on Machine Learning, pp. 1995-2003, 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Chen-Yo Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems. pp. 4987-4997, 2017.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv: 006877 2019.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Başar. Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02788,, 2018.
Shangtong Zhang and Richard S Sutton. A deeper look at experience replay. arXiv preprint
a7Xiv:1712.01225, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018
14

---

Under review as a conference paper at ICLR 2020
A DEEP Q-NETWORK
We are present the DQN algorithm for MDP in details, which is proposed by Mnih al. (2015) and adapted here to discounted MDP. As shown in Algorithm/ 2 below, DQN features two key tricks that lead to its empirical success, namely, experience replay and target network.
Algorithm 2 Deep Q-Network (DQN)
Input: MDP (S, P. 7) replay memory M, number of iterations T, minibatch size n, exploration probability E (0, 1). a family of deep Q-networks Qu: : S x A + R, integer Turget for updating the target network, and sequence of stepsizes {01)-20-
Initialize the replay memory M to be empty. Initialize the Q-network with random weights Initialize the weights of the target network with 6" 0.
Initialize the initial state Sg-
for t 0, ........77 do With probability e, choose A, uniformly random from A, and with probability 1 choose A, such that (S,, At) max.e Qo a))
Execute A, and observe reward R₂ and the next state S1+1- Store transition (S,, A,, Re, S2+1) in .M. Experience replay: Sample random minibatch of transitions {(si, ai, s Mimm from M. For each E [r.]. compute the target Y; = r; + maxaeA Qo (8), Update the Q-network: Perform gradient descent step
- 0 a4
Σ kE(m)
[r, [o(s voQo(s;,a).
Update the target network: Update 0* + 0 every Tirger steps. end for
Define policy गे as the greedy policy with respect to Qo. Output: Action-value function Qa and policy ा.
B COMPUTATIONAL ASPECT OF DQN
Recall that in Algorithm we assume that the global optima of the nonlinear least-squares problem in (3.1) is be obtained in each iteration. We make such assumption as our focus is on the statistical analysis. In terms of optimization, it has been shown recently that, when the neural network overparametrized, (stochastic) gradient descent converges the global minima of the empirical function. Moreover, the generalization error of the obtained neural network can also be established. The intuition behind these results is that, when the neural network is overparametrized, it behaves similar to the random feature model (Rahimi & Recht, 2008). See, e.g., Li & Liang (2018); Du et al. (20188) 2018b;a); Zou et al. (2018); Chizat & Bach (2018), Allen-Zhu et al. (2018a;b); Jacot et al. (2018); Cao & Gu (2019); Arora et al. (2019); Ma et al. (2019): Mei et al. (2019); Yehudai & Shamir (2019) and the references therein. Also see Fan et al. (2019) for a detailed survey. In the following, we make an initial attempt in providing a unified statistical and computational analysis of DQN.
In the following, we consider the reinforcement learning problem with the state space S (0, 1)" and finite action space A. To simplify the notation, we represent action using one-hot embedding and thus identify as an element in (0, 1|14, Thus, we can pack the state and the action together and obtain vector (8, a) in IRd where we denote r A by d.
15

---

Under review as a conference paper at ICLR 2020
We represent the Q-network by the family of two-layer neural networks
Qls,a;b,W)
m by o [ (s, a)]:
E(x
(B.1)
Here m is the number of neurons, by E IR and W3 E ERd for all j E [ma]. and (u) = max fu, 0} is the ReLU activation function. Here b = (bi,...,b dm) E R" and W = (WI...., Wm) E Rd are the weights the neural network. Then, the k-th iteration of Algorithm 1, the optimization problem in (3.1) becomes
minimize
Σ y (; W, 2n
1
(B.2)
where Y; = R.+ Qx (S): a) is the target and Q%: is the Q-network computed in the previous iteration. Notice that this problem is the least-squares regression with two-layer neural networks in the overparametrized setting. We solve the optimization in (B.2) via gradient descent. Specifically, we initialize. the parameters via by iid. Unif((-1,1)) and Wj iid. ( Ia/d), where is the identity matrix in RR. Moreover, for ease of presentation, during training we keeping fb...... bm fixed as the random initialization and only optimize over W. Moreover, let W(0) Rdxm be the initialization of W. We restrict the weight W to Frobenius ball centered W with radius B > i.e, we define
BB (W mdxm: I|W W (O)) fro S B),
(B.3)
where a sufficiently large constant. Thus, the problem in (B.2) is transformed into
1 Σ.r Q(S, Agb, Agb,
minimize In (W) WeBs
(B.4)
2n
where is fixed to the initial value. We solve this optimization problem via projected gradient descent, which generates sequence of weights (W()))22 S BB satisfying
W(t + 1) = Is, W(1) Σ Dy As0, Aw (B.5)
where Il, is the projection operator onto B3 and r7 > 0 is the step size.
To understand the convergence of the updates in (B.4), we utilize the fact that overparametrized two-layer neural networks behave similar to the random feature model. Specifically, notice that we have
m
Q(s,a;b,W) W) = Vm Σ by
1[W7 (8) > 03 WJ (s,
(B.6)
j=1
Vw,Q(s,a:b,W) _ bj 1(W) 0}
Vj e im].
(B.7)
Vm"
We define function class
F(()
Q((..))=
m
(s, 03 WJ](s,]]))))))))))))) by (s,,
w w BBB)
(B.8)
B.m
Vm j=1
By (B.6) and (B.7), every Q E (()
B.m can be written
m
Q( = Q( a ((t)
Σ by 1(W,())((s.a)) > 0} (W, W,(1)) (s.
vm
-=1
= -
16

---

Under review as a conference paper at ICLR 2020
Thus, B.m contains first-order approximations of Q(, a; (()). Furthermore, shown in Du et al. (2018b;a) Arora et al. (2019), when is sufficiently large, the overall effect of the scaled indicators (1/vmm (() (s,a) > 0} are well approximated by the indicators produced by the initial weights. That is, when m approaches infinity, for each fixed t, F(th in (B.8) is close to
FB.m =
= [[nQ(s,)=
ΣE by 1(W,(0) > 0} W (8. W E BB V
1
m
(B.9)
Notice that {Ø) (0//a))=1//mmm/// class FB.m is family of functions that can be written combinations of random features, i...
11//mmbb (0) a) 0} are i..dd random variables. Thus, function
Fr,m =
= =((.s.))(({aaa....)))
+ Σ as) [ S BB.
(B.10)
where we utilize the definition of B3. More importantly, when m goes to infinity, the empirical distribution of the random features (øy(s, a) [emm converges to its population distribution. We denote :3 1s B, w) as the random feature, where 3 Unif([-1, 11,1)) 13) and w ~ N(aa/d). We denote Ju as the joint distribution of (3 and w. Then, FB.m (B.10) converges a set. Fü given by
FB Q(s.a) Qo(s.a) / ols w) T a dp(B,w), / ||a(3, w)ll dp(3, w) S B²
(B.11)
where a is function over {-1,1] x R.d and Qo(s, a) = limm- Q(s, a; W(O)).
Furthermore, can be shown that Fi is subset a reproducing kernel Hilbert space (Rahimi Recht, 2008) H. generated by kernel
K ((s,a))(e d')) (x Besides, the inner product induced by the RKHS norm between functions
[w (8,a) > 03 11 (s',a'' > ({s, ( (B.
f1 f1= ((.:3, w) (3, w) du(3,w) w) and
f2 = 6(, w) T
as (B, w) du(33 w)
is given by (/1, f2hN (an (8, w) on w)) du(3, w.) Thus, Fi given in (B.11) can be written RKHS-norm ball
FB 1Q Qo + S: |1 S B)
with radius B. As a result, when both m and go to infinity, the population problem correspond to (B.2) becomes minimizeqeP; I|Q TQ whose solution is denoted by Q Therefore, utilizing the recent result in optimization for two-layer neural networks Arora et al. (2019), the Q-networks obtained by the projected gradient descent in (B.5) satisfy
, W(1) 11 x 1/v7
(B.13)
when both m and are sufficiently large. That is, when the network is overparametrized, projected gradient descent produces solution Q++1 with O(1/Vn) generalization error. Moreover, using inequality (a + b)2 < 2a² + 2b², we have
1 - 112 11++1 - Qitillae + +11 T x 3//7 dist( (f T), (B.14)
where dist(FT,, 0, T) is defined
dist(F o, T)
inf sup |l - Tgll.
feT g
which measures the approximation error of functions in the RKHS ball F with respect the Bellman operator and the sampling distribution a. Finally, combining (B.14) with the error propagation result in Theorem D.I. 1, we obtain the error of neural-FQI with overparametrized two-layer neural networks.
17

---

Under review as a conference paper at ICLR 2020
C RELATED WORK
There is a huge literature in deep reinforcement learning, where algorithms are based on Q-learning or policy gradient (Sutton et al., 2000). We refer the reader to Arulkumaran et al. (2017) for a survey of the recent developments of DRL. In addition, the DQN algorithm is first proposed in Mnih et al. (2015), which applies DQN to Artari 2600 games (Bellemare al., 2013). The extensions of DQN include double DQN (van Hasselt et al., 2016), dueling DQN (Wang et al., 2016), deep recurrent Q-network (Hausknecht & Stone, 2015), and asynchronous DQN (Mnih et al., 2016). All of these algorithms are corroborated only by numerical experiments, without theoretical guarantees. Moreover, these algorithms not only inherit the tricks of experience replay and the target network proposed in the original DQN, but develop even more tricks to enhance the performance. Furthermore, recent work such as Schaul et al. (2016); Liu & Zou (2017); Zhang & Sutton (2017) study the effect of experience replay and propose various modifications.
In addition, our work is closely related the literature on batch reinforcement learning (Lange et al., 2012), where the goal is estimate the value function given transition data. These problems are usually formulated into least-squares regression, for which various algorithms are proposed with finite-sample analysis. However, most existing work focus the settings where the value function are approximated by linear functions. See Bradtke & Barto (1996); Boyan (2002); Lagoudakis & Parr (2003); Lazaric et al. (2016); Farahmand et al. (2010); Lazaric et al. (2012); Tagorti & Scherrer (2015) and the references therein for results of the least-squares policy iteration (LSPI) and Bellman residue minimization (BRM) algorithms. Beyond linear function approximation, a recent work Farahmand al. (2016) study the performance of LSPI and BRM when the value function belongs to a reproducing kernel Hilbert space. However, we study the fitted Q-iteration algorithm, which is a batch RL counterpart of DQN. The fitted Q-iteration algorithm is proposed in Ernst et al. (2005), and Riedmiller (2005) propose the neural FQI algorithm. A finite-sample bound for FQI is established in Munos & Szepesvári (2008) for large class of regressors. However, their results not applicable to ReLU networks due to the huge capacity of deep neural networks. Furthermore, various extensions of FQI are studied in Antos et al. (2008a); Farahmand et al. (2009); Tosatto et al. (2017); Geist et al. (2019) to handle continuous actions space, ensemble learning, and entropy regularization.
Furthermore, our work is also related to works that apply reinforcement learning to zero-sum Markoy games. The Minimax-Q learning is proposed by Littman (1994), which an online algorithm that an extension Q-learning. Subsequently, for Markov games, various online algorithms are also proposed with theoretical guarantees. These work consider either the tabular case linear function approximation. See, e.g., Bowling (2001); Conitzer & Sandholm (2007); Prasad et al. (2015); Wei et al. (2017); Pérolat et al. (2018); Srinivasan et al. (2018); 8); Wei et al. (2017) and the references therein. In addition, batch reinforcement learning is also applied to zero-sum Markov games by Lagoudakis & Parr (2002); Perolat et al. (2015); Pérolat et al. (2;16;;)); Zhang et al. (2018), which are closely related to our work. All of these works consider either linear function approximation or a general function class with bounded pseudo-dimension (Anthony & Bartlett, 2009). However, there results cannot directly imply finite-sample bounds for Minimax-DQN due to the huge capacity of deep neural networks.
Finally, our work is also related line of research on the model capacity of ReLU deep neural networks, which leads to understanding the generalization property of deep learning (Mohri et al., 2012; Kawaguchi et al., 2017). Specifically, Bartlett (1998); Neyshabur et al. (2015b;a); Bartlett et al. (2017a); Golowich et al. (2017); Liang et al. (2017) propose various norms computed from the networks parameters and establish capacity bounds based upon these norms. In addition, Maass (1994); Bartlett et al. (1999); Schmidt-Hieber (2017); Bartlett et al. (2017b); Klusowski & Barron (2016); Suzuki (2018); Bauer et al. (2019) study the Shpmik-Chervonenkis (VC) dimension of neural networks and Dziugaite& Roy (2017); Neyshabur et al. (2017a) establish the PAC-Bayes bounds for neural networks. Among these work, our work is more related to Schmidt- Hiiberrrt-reerrrrr (2017); Suzuki (2018), which relate the VC dimension of the ReLU networks to set of hyperparameters used to define the networks. Based the VC dimension, they study the statistical error of nonparametric
18

---

Under review as a conference paper at ICLR 2020
regression using ReLU networks. In sum, theoretical understanding of deep learning is pertinent to the study of DRI algorithms. See Kawaguchi et al. (2017); Neyshabur et al. (2017b); Fan et al. (2019) and the references therein for recent developments on theoretical analysis of the generalization property of deep learning.
D PROOF OF THE MAIN THEOREM
In this section, we present detailed proof of Theorem 4.4.
Proof. The proof requires two key ingredients. First in Theorem D.1 quantify how the error of action-value function approximation propagates through each iteration of Algorithm 1. Then in Theorem D.2 we analyze such one-step approximation enror for ReLU networks.
Theorem D.1 (Error Propagation). Recall that (osSS are the iterates of Algorithm 1. Let тK be the one-step greedy policy with respect to Qk, and let QTk be the action-value function corresponding to и.. Under Assumption 4.3, we have
20 (1 7)- Emax + (1 (1-7)²
4,K+1
II Q
11,p S
Rmax
(D.1)
where we define the maximum one-step approximation error Emax max
[T
1xl
Here &p is a constant that only depends on the probability distributions μ and
Proof. See $F.1 1 for a detailed proof.
In the sequel, we establish an upper bound for the one-step approximation error 1 for each & E: [K].
Theorem D.2 (One-step Approximation Error). Let C BBS A, Vmax) be a class of measurable functions S A that are bounded by Vmax Rmax/(1-7) and let be a probability distribution on S x A. Also, let {S,, (.) be ii.d. random variables in S x AA following σ. For each i e [n), let R2 and S/ be the reward and the next state corresponding to (St, A.). In addition, for any fixed Q E F, we define Y; R; + 7 max.eA Q(S', a). Based on {(,,, A;, He)m) we define
Q as the solution to the least-squares problem
minimize FEF
= n2
[f() Y.]
(D.2)
Meanwhile, for any > O, let (5, -norm, and we denote by Ns its cardinality. Then for any (0, and any > have
F, || (1x)) be the minimal 5-covering of F with respect to
QQ TQII s (1 + c)² w(F) + C. V2 V
/ (n c) log No C Vmax 5,
(D.3)
where C and C" are two positive absolute constants and (F) is defined
w(F) sup inf |l Tgll.. gEF FEF
(D.4)
Proof. See $F.2 for a detailed proof.
To obtain an upper bound for | 2+ as required in Theorem D.I, we set Q Q+ in
Theorem D.2. Then according to Algorithm 1, Q defined in (D.2) becomes Qr. We set the function class F in Theorem D.2 be the family of ReL.U Q-networks Fo defined (4.1). By setting e and 1/n in Theorem D.2, we obtain
11@ TQx < (F)) C. V2 V / log No.
(D.5)
19

---

Under review as a conference paper at ICLR 2020
where C' is a positive absolute constant and
No = [N ||<c]]
(D.6)
the 1/n-covering number of Fo. the subsequent proof, we establish upper bounds for (FF) defined (D.4) and log No, respectively. Recall that the family of composite Hölder smooth functions Go is defined in (4.2). By Assumption 4.2, have Tg E 9o for any g Fo- Hence, we have
((Fo)
sup inf |lf fl = sup inf |I - f' E' JEFo
(D.7)
l' fEFo
where the right-hand side is the -eror of approximating the functions in Go using the family of ReLU networks Fo.
By the definition of 9o in (4.2), for any E 9n and any a E A, f(,,a) E G(((p). 15,88, H2)] se(g))
a composition of Hölder smooth functions, that is, f(-,a) = 94 o...o 91. Recall that, as defined in Definition 2.3, Sikk is the k-thh entry of the vector-valued function Øj- Here 9j* E Cr, (laj, 6,]"s 33. Hj) for each & [p]+1] and [9]. In the sequel, construct ReLU network to approximate f(: and establish an upper bound of the approximation error the right-hand side of (D.7). We first show that f(- a) can be reformulated as composition of Hölder functions defined on a hypercube. We define h1 = 91 / (2H1) + 1/2,
hu 9j (2 (2H, + 1/2, for all j E 92.....9- --...,,
and hu(4) 9q (2H Hg-1). Then immediately have
a() = .... 01 = hy ......................... /11
(D.8)
Furthermore, by the definition of Hölder smooth functions in Definition 2.2, for any it E [P2]. we have that his takes value in [0, 1] and hIs E Ce, ([0, 1 1). Similarly, for any j E ( ........-- 9-1...91111 and ls [ps+i], hig also takes value in [0, 1] and
hgs C.2 (Io, (2H(()))))))
Finally, recall that we use the convention that Po+1 = 1, that is, hg is a scalar-valued function that satisfies
hy Ci (I0, 11 Bq. 1)
Now we employ the following lemma of Schmidt- (2017) to construct a ReLU network that approximates each hij, which combined with (D.8) yields a ReLU network that is close to a() Recall that, as defined in Definition 2.2, we denote by C, 3, H) the family of Hölder smooth functions with parameters 3 and on D S TR..
Lemma D.3 (Approximation of Hölder Smooth Function). For any integers m 2 and N 2 max( (B++)), (H++)), let (1 [logz r]), dg r, = 12r for each j [Z], and dr++1 1. For any g C, C, 1J", H), there exists a ReLU network F(L, [d - 8, Vmax) defined in Definition 2.1 such that
|| - olloo < (2H +1) 2 + H. 22 .N 8/r
where the parameter s satisfies S 94 2 (3 + 1)2r. N (m + 6) (1 [log2 rl).
Proof. See Theorem of Schmidt-Hieebee (2017) for a detailed proof.
We apply Lemma D.3 to hyx: [o, 1]s + j0, 1] for any j E [q] and k E [p5+1]. Wet m = 77 [log, n for a sufficiently large constant v) > 1, and set N to be a sufficiently large integer depending on n, which will be specified later. addition, we set
L = 9 9 (m + 5) (1 + [logg tj
(D.9)
and define
W max
max 15
(2H (2,(211-11))
(D.10)
20

---

Under review as a conference paper at ICLR 2020
which is constant. Without loss of generality, assume W 2 hereafter. Then by Lemma D.3, there exists ReLU network hyx such that
Ihix h S (2W + +1) -35 .N n + W -2 10..NN-00 N-0//1, Furthermore, we have his F(1,, (t,, N2... 13, with
(D.11)
8 94 13 (8, 1) N. Nmmm+ (m++ 6) (1 [log2 4
(D.12)
takes imput from [0, 1|,,,, we need to further transform Tyyk so that takes value in [0, 1]. In particular, define (u) 1 (1-u)+ min mmax (u, 0}, 13 for any E IR. Note that a be represented by a two-layer ReLU network with four nonzero weights. Then we define h5sk = o hig and h (h3s) keles+1 Note that by the definition of hyk- we have hyg E F(L + 2, [t,, N. 12t, N, 11. sy + 4), which yields
Meanwhile, since hy+1 = (h
hy F(, + (t,, 1 Ps+1, 12 Ps+1. (8, + 4) Pj+1).
Moreover, since both hyn and hys take value in [0, 11. by (D.11) we have
hha ho = 11o o hyg - o hysll I [laz hys
(2W + . N + W 22 ...NN N-///ts,
(D.13)
where the constant W is defined in (D.10). Now we define f: S R by f hy .... hi which falls in the function class
F(I. (r, d _. 1).33),
(D.14)
where we define L= E + 2). d = max 121, P5+1 N, and -; (sy + 4) Ps+1- Recall that, as defined in (D.9), we have Lj sufficiently large, we have
(m + 5) (1 + [log2 t2 Then when n
I Σ [1 (log2 n 5) (1 + [loga t,1]] s Σ log t, log, (logn)*+s,
(D.15)
where >> is an absolute constant. Here the last inequality follows from (4.6). Moreover, for in (D.14), by (4.6) we have
N max jE(n
4/ S J < 12. N. (maxp;) (max (2) S N- (logn)5.
(D.16)
jE
"JEn)
In addition, combining (D.12), (4.6), and the fact that Lj S Pj. we obtain
3 $ N logn (max p3)
log Lj S N (logn)++22
(D.17)
jE[y]
Now we show that the function class in (D.14) can be embedded in F(L", (dg s²), where L3, {dz ) +++1 and s* are specified in (4.7). To this end, we set
j=
max C Cn (nt/ 15159
N
(D.18)
where the absolute constant C' > is sufficiently large. Note that we define a* = max 4/ 1,). Then (D.18) implies that N x n= When g in (4.7) satisfies g' 1 + 25, by (D.15) we have
i is S (I"gn)ss.
In addition, (D.16) and (4.7) implies that we can set dj 2 d for j (T*). Finally, by (D.17) and 1D.,8), have 5 S na* (logn)s', which implies + (I. T.) & 8". For an T--layer ReLU
21

---

Under review as a conference paper at ICLR 2020
network in (D.14), make it L -l-layer ReLU network by inserting L* Σ identity layers, since the inputs of each layer are nonnegative. Thus, ReI.U networks in (D.14) can be embedded in
FL fr, a.... ā. 11. 5. (L' - -))r
which is a subset of F(L", F 8t) by (4.7).
To obtain the approximation error | - [(, a) || bl we define G3 = h1. o.....oly and G, = hi o......... for any j E [4]. By triangle inequality, for any j > 1 we have
|[; G2 S ||, G - h2 Gj-1llo a1 + [1b G5-1 h2 G1-111
S ..W.il -IG -1j-l1- + 11g - h,l1
(D.19)
where the second inequality holds since hy is Hölder smooth. To simplify the notation, we define Xラ = =T==)+1 A 1) for any j E 1 - I]. and set X, = 1. By applying recursion to (D.19), we
obtain
II((; - Fllo= = ||G - -Gylec I W
Σ 11, j=1
hyll
(D.20)
where the constant W is defined in (D.10). Here in (D.20) use the fact that (a + b) a + D0 for all a E [0, 1] and a, b > 0.
In the sequel, we combine (D.7), (D.13). (D.20), and (D.18) to obtain the final bound on (Fo).
Since we can set the constant 77 in (D.13) to be sufficiently large, the second term on the right-hand side of (D.13) is the leading term asymptotically, that is,
[h - ha -
(D.21)
Also note that 33 = 3, II -1= 11 (3e 11 93 Xy for all E [g 1]. Thus we have 87 Bz X for all j E [q]. Combining (D.20) and (D.21), we have
a)((sa) - S Σ (N-B///))>
N 83/ts S max N 1-/3/
(D.22)
jE(n]
2=1
j=l
Thus, combine (D.7), (D.18), and (D.22) to obtain
w(Fo) S (max N - 15/1)²² x max n
285 (227
+t2) = n a1
(D.23)
JE
jEl9.
As the final step of the proof, remains to control the covering number of Fo defined in (4.1). By definition, for any f E Fo, we have f(-a)) F(L", /dt s*) for any a E A. For notational simplicity, we denote by Nss the d-covering of F(L", [d]] L'+1 +1 s*), that is, we define
No. - ( s*),11 -1x]].
By the definition of covering, for any f E Fo and any E A. there exists ga Na such that a) 9a boo < 8. Then we define a function g: S A + R by g(s,a) ga(s) for any (8,a) E S x A. By the definition of g, it holds that ||ʃ - gll S 8. Therefore, the cardinality of (6,, || lloo) satisfies
W Fo, |1. 11~0) < L4
(D.24)
Now utilize the following lemma in Anthony & Bartlett (2009) to obtain upper bound of the cardinality of As.
Lemma D.4 (Covering Number of ReLU Network), Recall that the family of ReLU networks I 1.
F(L, (dg ( s, Vmax) is given in Definition 2.1. Let D
(de + 1). For any 6 > 0, we have
log NTO ((L (4//2, Vmax),
||o]]
< (s+ log 1og (L 1) Dz].
22

---

Under review as a conference paper at ICLR 2020
Proof. See Theorem 14.5 of Anthony & Bartlett (2009) for detailed proof.
Recall that denote (1/n,, Fu, || (llo) by No in (D.6). By combining (D.24) with Lemma D.4 and setting å = 1/n, we obtain that
log No _ |A] log W $ |A| (s" + 1) log [2n (L" + -
where = II -' (dz + 1). By the choice of I,", s" and {d] }=1 + in (4.7), we conclude that
log No |A| s* L max log dj) x n" (log = jE[L-1
(D.25)
Finally, combining (D.1), (D.5), (D.23), and (D.25), we conclude the proof of Theorem 4.4.
E EXTENSION TO TWO-PLAYER ZERO-SUm MARKOV GAMES
In this section, we propose the Minimax-DQN algorithm, which combines DQN and the Minimax-Q learning for two-player zero-sum Markov games. We first present the background of zero-sum Markov games and introduce the the Minimax-DQU algorithm in $E.1. Borrowing the analysis for DQN in the previous section, provide theoretical guarantees for the proposed algorithm in $E.2.
E. MINIMAX-DQN ALGORITHM
As one of the simplistic extension MDP to the multi-agent setting, two-player zero-sum Markov game is denoted by (S, A. B, 7), where S is state space, A and B are the action spaces of the first and second player, respectively. In addition, P: A x B P(S) is the Markov transition kernel, and R: S x A x B + P(R) is the distribution of immediate reward received by the first player. At any time 4, the two players simultaneously take actions A, E A and B, B at state S, E S, then the first player receives reward RG ~ R(S;, Ar, B,) and the second player obtains RRe- The goal of each agent is to maximize its own cumulative discounted return.
Furthermore, let x: S + P(A) and v: S + P(B) be policies the first and second players, respectively. Then, we similarly define the action-value function QT. S x R.
(s, E
Σ
t. Re (So, Ao, Ba) = (s, a, b), A₁ ~ ( (St), B, ~ vl (s))
(E.1)
t=
and define the state-value function Vav S R as
E<QT)) (s, A ~ T(-
v(-1s)].
(E.2)
Note that these two value functions are defined by the rewards of the first player. Thus, at any state-action tuple (s,a,b) the two players aim to solve max, min, (* a, b) and min, max, Q* a, b), respectively. By the von Neumann's minimax theorem (Von Neumann Morgenstern, 1947; Patek, 1997), there exists a minimax function of the game, Q+: S Ax R. such that
Q", = max min (8, = min max QT (8, a,,.,,)).
(F.3)
Moreover, for joint policy (T, v) of two players, we define the Bellman operators T and T by
(s) a, b) = r(s, a, b) + (p (s, (TQ) a, = r(s, a, + (P* (P,Q)(s,a, where a)), R(dr k, and define operators P PT.. and pa by (PT:)) a, b) = Ey P(aaa) ( (' [Q(s' b').
(E.4)
(E.5)
(P*Q)(s, = Eg-rr-ls.... (EP() EP((B)
max min Eg n / V/ ~nd [Q (((ss,d')))]
23

---

Under review as a conference paper at ICLR 2020
Note that P is defined by solving a zero-sum matrix game based on Q(s', , RLAII|81, which could be achieved via linear programming. It can be shown that both T and 7 are --contractive, with QT." defined in (E.1) and Q" defined in (E.3) being the unique fixed points, respectively. Furthermore, similar to (2.3), in zero-sum Markov games, for any action-value function Q, the equilibrium joint policy with respect to Q is defined as
[ (6,, v- })] = argmax argmin Eawx' Noww [Q(s, a, b]], E x' x'EP(A) o' E(B)(
(E.6)
That is, = and v |s) solves the zero-sum matrix game based on Q(8,.))) :) for all 8 E S. By this definition, we obtain that the equilibrium joint policy with respect the minimax function Q" defined in (E.3) achieves the Nash equilibrium of the Markov game.
Therefore, to learn the Nash equilibrium, it suffices to estimate Q", which is the unique fixed point of the Bellman operator T. Similar to the standard Q-learning for MDP, Littman (1994) proposes the Minimax-Q Q learning algorithm, which constructs a sequence of action-value functions that converges to Q² Specifically, in each iteration, based on transition (s, a, b, s'), Minimax-Q learning updates the current estimator of Q", denoted by Q, via
Qs., b) + (1-a) a) a) a {r(s,a,))+ max min Bu' [Q(s o' (b]] (EP(A)EE((B)
where a E 1) is the stepsize.
Motivated by this algorithm, we propose the Minimax-DQX algorithm which extend DQN to two- player zero-sum Markov games. Specifically, we parametrize the action-value function using a deep neural network Qo: S x B - I and store the transition (St, Ac, Be, RG, Si+1) into the replay memory M at each time-step. Parameter of the Q-network is updated follows. Let Qa- be the target network. With independent samples ((st, 0i, bi, ri, (E()) from M, for all i E [n]. compute the target
Y1 ri 7
max min Eass' boww (Qo- (8/2 a, b)]. EEE((A) EPP(B)
(E.7)
which can be attained via linear programming. Then update 0 in the direction of V (.). where [()) n=1 Eiem [Y; Qo(s;, a, b,)]². Finally, the target network Qo- is updated every Turget steps by letting 0" 0.
To understand the theoretical aspects of this algorithm, we similarly utilize the framework of batch reinforcement learning for statistical analysis. With the insights gained in $3, we consider a modifica- tion of Minimax -DQN based on neural fitted Q-iteration, whose details are stated in Algorithm As in the MDP setting, we replace sampling from the replay memory by sampling i.id. state-action tuples from fixed distribution PPS A x B), and estimate Q" in (E.3) by solving a sequence of lquares regression problems.
E.2 THEORETICAL RESULTS FOR MINIMAX-FQI
Following the theoretical results established in $4, in this subsection, we provide statistical guarantees for the Minimax-FQI algorithm with F being a family of deep neural networks with ReLU activation. Hereafter, without loss of generality, we assume S = [0, 1J" with r being a fixed integer, and the action spaces A and are both finite. To evaluate the performance of the algorithm, we first introduce the best-response policy follows.
Definition E. For any policy n: S P(A) of player one, the best-response policy against n, denoted by =² defined as the optimal policy of second player when the first player follows æ. In other words, for all S, we have v²(- = argmin, (T)),,), where y is defined in (E.2).
Note that when the first player adopt a fixed policy æ, from the perspective of the second player, the Markov game becomes a MDP. Thus, v is the optimal policy of the MDP induced by n. Moreover, it can be shown that, for any policy x, Q" (s, a, b) 2 Q=.'((ss (8, a, b) holds for every state-action tuple
24

---

Under review as a conference paper at ICLR 2020
Algorithm 3 Minimax Deep Q-Network (Minimax-DQN) for the second player
Input: Zero-Sum Markov game (S, B, P, n)), replay memory M, number of iterations T, minibatch size n, exploration probability e E (0. 1), a family deep Q-networks Qo: SxAxB + R. an integer iaggst for updating the target network, and a sequence of stepsizes {ar)e20 Initialize the replay memory M to be empty.
Initialize the Q-network with random weights e.
Initialize the weights of the target network by letting 0* = 0.
Initialize the initial state So-
for ( = 0, ,,..,. do
T
With probability 6, choose B, uniformly at random from B, and with probability sample
Be according to the equilibrium policy Pg, (-1 S.)) defined in (??). Execute B, and observe the first player's action A,, reward R, satisfying R. R(S., A,, B.). and the next state St-1 P(- St, Ar. B₂).
Store transition A, B,, R1, S(+1) in M.
Experience replay: Sample random minibatch of transitions {(8,, ai b Tas si) from M. For each i E [n)] compute the target
Y; +
max min Baws' bow bow [Q0- (5/, a, b)]. (EP(() E'EP(A)
Update the Q-network: Perform gradient descent step
- 0 - Cz
Σ
[ Qo(si, at b,)] VoQo(s;,,;
1E|m
Update the target network: Update 0* +- 0 every Target steps. end for
Output: Q-network Qo and equilibrium joint policy with respect to Qo-
Algorithm 4 Fitted Q-Iteration Algorithm for Zero-Sure Sum Markov Games (Minimax-FQI
Input: Two-player zero-sum Markov game (S, B, P, R),,, function class F, distribution
a E P(S A x B), number of iterations K, number of samples n, the initial estimator Qo E F. for 0, 1, ..,,,.... K do
Sample n i.i.d. observations {(S,, (,)eej))) from o, obtain R. R(: [S,, A,, B,) and
Si~0 ~ P(- [S, A,, B.).
Compute Y, = R, + EEXA))(A)) min E Bante (Qx(5), a, b)).
Update the action-value function:
1 n
Qu+1 argmin
-E [Y, A(S,,
fEF
end for Let (Tx, vx) be the equilibrium joint policy with respect to Qx, which is defined in (E.6).
Output: An estimator Qx of Q" and joint policy (TK, DK).
(8, a, b). Thus, by considering the adversarial case where the opponent always plays the best-response policy, the difference between Q= and Q" servers as a characterization of the suboptimality of n. Hence, to quantify the performance of Algorithm 4, we consider the closeness between Q" and Q which will be denoted by Q hereafter for simplicity. Specifically, in the following we establish an upper bound for ||Q Q¹x بر for some distribution P(S x Ax x B)..
We first specify the function class F in Algorithm as follows.
25

---

Under review as a conference paper at ICLR 2020
Assumption E.2 (Function Classes). Following Definition 4.1, let F(L, -=) and
Hel))()) be the family of sparse ReI.U networks and the set of composition of Hölder G(p 4. Rg.
smooth functions defined on S, respectively. Similar to (4.1), we define Fi by
F = (s: {
IR: f(; ai,a,,) b) E F(,, (=) 8) for any (a,b) E A x B).
(E.8)
For the Bellman operator 7 defined (E.5), we assume that for any S Fi and any state-action tuple (s, a, b), we have (+ a, b) E (( 1, 83. H3 He)le
We remark that this Assumption is in the same flavor as Assumption 4.2. As discussed in $4, this assumption holds if both the reward function and the transition density of the Markov game are sufficiently smooth.
In the following, define the concentration coefficients for Markov games.
Assumption E.3 (Concentration Coefficient for Zero-Sum Markov Games). Let (Tt: S + P(A x } be a sequence of joint policies for the two players in the zero-sum Markov game. Let V1, M2 P(S A x B) be two absolutely continuous probability measures. Suppose the initial state- action pair (Su, Ag; Bo) has distribution 2/, the future states are sampled according to the Markov transition kernel, and the action (A,, B,) is sampled from policy тr. For any integer m, denote by prm pmm-pm-11 pmm-1... pn the distribution of (Sm, Am, B,.) Then, the m-th concentration coefficient is defined as
d(p prm 1 priv) 2 1/2
k(m;),
sup
Exz
(E.9)
dv/
where the supremum is taken over all possible joint policy sequences [Fe)eejm)
Furthermore, for some μ P(S x A B), we assume that there exists finite constant op.er such that (1-7)² Em>1 7 mm m n(m; p. o) S Sn.c. where o the sampling distribution in Algorithm and nmm; p4, 0) is the m-th concentration coefficient defined in (F.9).
We remark that the definition of the m-th concentration coefficient the same as in (4.4) if we replace the action space of the MDP by A B of the Markov game. Thus, Assumptions 4.3 and E.3 are of the same nature, which are standard in the literature.
Now we are ready to present the main theorem.
Theorem E.4. Under Assumptions E.2 and E.3, consider the Minimax-FQI algorithm with the function class FF being Fi defined in (E.8) based the family of sparse ReLU net- works F(L", [d; - s"). We make the same assumptions on F(L', "t and G(P,, 4j, 3j, )E())
in (4.6) and (4.7). Then for any K E N, let (*K, VK) be the policy returned by the algorithm and let O% be the action-value function corresponding to (T v (g)) Then there exists constants &x and C' such that
I|Q - Qulli S 6p. ? (1-7)² |A| - 1BI1- (1'/21)/2 + 71- Rmaxx (E.10)
K+1
where a= maxxele) (/ + (z) and 0,, is specified in Assumption E.3.
Similar to Theorem 4.4, the bound in (E.10) shows that closeness between (TK, vx) returned by Algorithm and the Nash equilibrium policy (TQ., "Q*). measured by ||Q" Q I1a is bounded by the sum of statistical error and algorithmic error. Specifically, the statistical error balances the bias and variance of estimating the value functions using the family of deep ReLU neural networks, which exhibits the fundamental difficulty of the problem. Whereas the algorithmic error decay to zero geometrically as K increases. Thus, when K is sufficiently large, both and O are constants, and the polylogarithmic term is ignored, Algorithm 4 achieves error rate
|A| |B] na -1
|A|
B
max 12 03 02/(225++))) JE(y
(E.
26

---

Under review as a conference paper at ICLR 2020
which scales linearly with the capacity of joint action space. Besides, if [B| The Minimax-FOI algorithm reduces to Algorithm 1. In this case, (F.11) also recovers the error rate of Algorithm 1. Furthermore, the statistical rate n fa'-11) -1)/2 achieves the optimal 4--norm error of regression for nonparametric regression with a compositional structure, which indicates that the statistical error in (F.10) (0) can not be further improved.
Proof. See $G for detailed proof.
F PROOFS OF AUXILIARY RESULTS
In this section, we present the proofs for Theorems D.1 and D.2, which are used in the 3D establish our main theorem.
F.1 PROOF OF THEOREM D.1
Proof. Before we present the proof, we introduce some notation. For any & {o...., K - 1}, we denote TQn by Qk+1 and define
2 Qx - Qx--
(F.1)
Also, we denote by TT the greedy policy with respect to Q.. In addition, throughout the proof, for two functions Q2: S E S and any a E and define Q1 S Q2 similarly. Furthermore, for any policy n, recall that in (2.4) we define the operator ps by
E, we use the notation Q1 Q2 if Qi a) 2 Q2 a) for any
(PT))(s, = E
~ P(-1s,a), A' ~ (((15')]
(F2)
In addition, we define the operator T by
(TT r(s, a) + (PT))(ss))s)))
Finally, we denote Rmax/ (a///11199/ 7)) by Vimax Now we are ready to present the proof, which consists of three key steps.
Step (i): In the first step, we establish a recursion that relates Q - Qu+i with Q' - Qu to measure the sub-optimality of the value function Qs. In the following, we first establish an upper bound for Q" 1 as follows. For each k: , K. - 1]. by the definition of @k+ in (F.1), we have
Q QK+1 Q" - (Qi+1 @++1) = Q" Qu+1 + 0k+1 = Q" - -QQ 2k+1
= QQ- Q + (TT Q2 - -TQ;) + 0k+1,
(F3)
where T² is the greedy policy with respect to Q", Now we leverage the following lemma to show "T" Q₁ < <TQu.
Lemma F.1. For any action-value function Q S A E and any policy it holds that
T Q TQ T
Proof. Note that we have max,, ((s'.a') a²) > Q( 1'',000 a²) for any s' E S and a' E A. Thus, it holds that
(s) r(s, a) + E max Q a') S' P(- s,)]
2 rr(s a) + [S( A') 5' ~ P(- a), A' ~ x-115"]] (+))))
Recall that To is the greedy policy with respect to Q such that
IP A E argmax Q(s, a) A Te(- [s]] 1,
27

---

Under review as a conference paper at ICLR 2020
which implies
E [[Q(s', A' ~ =T[.1166] = max Q(s',
Consequently, have
(), r(s, a) t B(Q(S", P(-1s.a), A' -0x00(-)5)))))) = - a) + 7 B max ,') ~ P(-1s,a)] = (T)))
which concludes the proof of Lemma F.I.
By Lemma F.I, we have TQk 2 T Qk. Also note that Q" is the unique fixed point of T Thus, by (F.3) we have
Q' - -x+1=
= = - Q Qs) + (T Q - TQQx) + 0k+1 S (T" Q- -T" Qx) + ex+1,
(F.4)
In the following, we establish a lower bound for Q* - Qu+1 based on -"-Q2 Qs. Note that, by Lemma F.I. we have 7 Qu= TQk and TQ" 2 T Q-, Similar to (F.3), since Q is the unique fixed point of T. it holds that
Q' ---Q44 = =Q -TQu -x- 1= Q" T Qu + @k+1 = -0" + (TT=Q' Tx* + ek+1
= (TQ' - T Q*) = (T - T Qx) + ex+1 2 (T Q" - T Qx) + 2x+1-
(F.5)
Thus, combining (F:4) and (F.5) we obtain that, for any & E [0,...,K-1]
T Q" - Qu 2k+1 S Q" Qh+1 S T -"- Qx + @k+1-
(F6)
The inequalities in (F.6) show that the error Q" - Qu+1 can be sandwiched by the summation of term involving Q" - Qx and the error 0k+1, which defined in (F.1) and induced by approximating the action-value function. Using pa defined in (F.2), we can write (F.6) in a more compact form,
7 p "0" -x)) 2x+1 2 Q" - -K+11 27 pT (Q" - Qx) + 2k+1
(F.7
Meanwhile, note that px defined in (F:2) is a linear operator. In fact, px is the Markov transition operator for the Markov chain on S x A with transition dynamics
S P(. Ad),
A411
m(- S(41)
By the lincarity of the operator pr and the one-step error bound in (F.6), we have the following characterization of the multi-step error.
Lemma F.2 (Error Propagation). For any k, (0,1, ..... K- - 1} with k < f, we have
Q--Qi
r 8-1-i ye---e--i li+1 + get (pr") jonn)===( (=* - -x))
(F88)
k=
Q' - 2 b-1-i pte-.. ... ptt4))0it) + get (pre-1 pre-a ..........( pT* Q+).
(F.9)
Here 0i+1 is defined in (F.1) and we use pa pm' and (Pry* to denote the composition of operators.
Proof. Note that pa is a linear operator for any policy We obtain (F.8) and (F.9) by iteratively applying the inequalities in (F.7).
28

---

Under review as a conference paper at ICLR 2020
Lemma F.2 gives the upper and lower bounds for the propagation of enror through multiple iterations of Algorithm I, which concludes the first step of our proof.
Step (i): The results in the first step only concern the propagation of error Q' - Qu. In contrast, the output of Algorithm I is the greedy policy Ta with respect to Qs. In the second step, goal is to quantify the suboptimality of Q*h, which is the action-vall function corresponding to In the following, we establish an upper bound for Q - -
To begin with, we have Q 2 Thh by the definition of Q" in (2.5). Note that we have Q" = =T Q" and QT T=* Hence, holds that
Q' Q =T
" Q- T = T Q" +--""""''00 Qu + T Qx) (-TTxQu + TT) - = =TTT Q - Qx) + Q' Qx) + (T - Q=)
(F.10)
Now we quantify the three terms on the right-hand side of (F.10) respectively, First, by Lemma F.1, have
T Qm Qx = T Qx - TQ: - 0.
(F.1I)
Meanwhile, by the definition of the operator ps in (F:2), we have
T" Q' T Q = P (Q Qk), T - T QTM = Pmu (āx - -TTA. (F.12)
Plugging (F.11) and (F.12) into (F.10), we obtain
Q' Q"* S ps (Q" - Q2) +7, pn (Ō) Q
= (px' - (Q= - 2n) t7 . p (Q' - Qm²),
which further implies that
(I - (--7- 1----Pm P** (Q= - =*+) S (p" - p Qa).
Here is the identity operator. Since T is c-contractive operator for any policy n, r p is invertible. Thus, we obtain
0 Q - -0t 57 - [ -Q- pm
- (Q' - Qu)] (F.13)
which relates Q" -** with Q' - Qx. In the following, we plug Lemma F.2 into (F.13) to obtain the multiple-step error bounds for QT First note that, by the definition of p in (F:2), for any functions f2 : S x A + IP satisfying S1 2 f2. we have pa f1 2 P* Combining this inequality with the upper bound in (F.8) and the lower bound in (F.9), we have that, for any k < t.
6-1
p (Q' -Q--
Σ
f-1-i,
(pt li+ + th (e=t)e-k+((0 (Q" -
(F.14)
i=k
6-1
(Q' - Q > Σ
1-1-1 (per p ... pr(+1 pr(tt) 1i+t1
i=
t t- k (pre p 1... pTn) Qxx).
(F.15)
Then plug (F.14) and (F.15) into (F.13) and obtain
0 2
< (1 -
pme)-
Σ g-i [(px yeui (poe prreppe-i pr(t) liit
t=k
+ tgeti-k peptt (pti p ... pad p=0' -00- 2x)
(F.
29

---

Under review as a conference paper at ICLR 2020
for any lo f. To quantify the enror of Q"*, set l = K and i 0 in (F.16) to obtain
K-
0 s Q" - Q** < - -pak) -
Σ ki [[p= ) - (pax pak-i... pa.+i) li+1
+ tttt [(pti) - (pa* prx 1 ... pxo (00) 200
(F.17)
For notational simplicity. we define
a (1 7)7 -i-1
(1 - 7)7 K
1 - K+ for 0 0 -1 and ak
(F.18)
1 7 R
One can show that Σ ai = 1. Meanwhile, we define K + linear operators {0* by
[(p=)) -+ Ox = - -1- [(P5))K (1 + pa.. ...
O, (1 (1- 72/2 (PTx) "
... (pox pr..i...ppt. p=(t)]] for S i K -1 1,
Using this notation, for any (s,a) E x A. by (F.17) we have
(Q, QQTM (s,u))
2y - - (1 7)
K-
a. (0.lett))))sss)) + ak (Ox|Q" - -s.
(F.19)
where both Oil0i+1l and Ox 1Q" Øo are functions defined on S A. Here (F.19) gives a uniform upper bound for Q* Q**, which concludes the second step.
Step (iii): In this step. we conclude the proof by establishing an upper bound for -Q"-QQ** I| based on (F.19). Here μ E P(S A) is fixed probability distribution. To simplify the notation, for any measurable function f: S x A + R, denote puf) to be the expectation of f under μa, that is, u(f) = fSxA f(s, as, a). Using this notation, by (F.19) we bound ||Q* -=* 11 by
||Q- - TTk ||,,- = u(1@ QQ*KI)
2y - 1 <
K-1 a. (o.let1)) + tak (0xlQ- -ãal] (0x1Q--Qol)
Σ
(F.20)
(1 - 7)2
2=0
By the linearity of expectation, (F:20) implies
11,, S 2y(1- 21(1-x*+1
K-1
Σ a: (c..(OO.eet1))) + tak =(00'Q"0000000 -ōo1] (F21)
||Q" Q
(1 71-
Furthermore, since both Q and To are bounded by Vmax = Rmaxx/ (L (1-7) in loo -oom, we have
m(Ox|Q' - @o1) S 2 Rmmxx/ (1 7)-
(F.22)
Moreover, for any i E (O..... K - 1}. by expanding (1 <PPxx) into a infinite series, we have -
((oleettl)) = 11 2
(1 11 ( )k= + (PEk pan-i... p= 3leet1
1- 4
g². (PT + (pek) H- ( i... .....pp...) (ee4)]lettal
(F.23)
To upper bound the right-hand side of (F.23), we consider the following quantity
u[(p=x)i y (Ptm p ... pT)
(P pim-1 ... pT) (3) (F:24)
SxA
30

---

Under review as a conference paper at ICLR 2020
Here "I,..., Tm are m policies. Recall that P" is the transition operator of Markov process defined on S x A for any policy Then the integral on the right-hand side of (F.24) corresponds to the expectation of the function f(X;), where (Xt ) is a Markov process defined on S x A. Such Markov process has initial distribution Xo ~ The first m transition operators are {P*) ]e[m]] followed by j identical transition operators p=k_ Hence, (P*x) (P pTm-1.... ... ... ) is the marginal distribution of Xj+m. which we denote by jú for notational simplicity. Hence, (F.24) takes the form
1 ( pmm pr) )f] = =E(f(X)-n)) (m)) (1,(f)
JSXA f(s, f(s.a) (F.25)
for any measurable function f on S x A. By Cauchy-Schwand inequality, we have
p,( - [Sx24 diz
(s, a) do((s,o) a))
1/2
SXA [/ooa
1/2
(F.26)
in which /jo//do: 8 A R is the Radon-Nikodym derivative. Recall that the (m j)-th order concentration coefficient smm J: 14, 0) is defined in (4.4). Combining (F.25) and (F.26), obtain
m5( S x(m + js,,o) ||/
Thus, by (F.23) we have
((O:(ei+1l)
1 1- 7
? (u(( " + (ptrtttttt................. po.t1 lei+il]
2
j=0
$ $1 (1-7)
?¹ x( K
j:110) |eettlla.
(F:27)
Now combine (F.21), (F:22), and (F.27) obtain
27 1 - (1 7)²
K
11Q - -
111,s 5
Σ =(O.lei+1) + ax m(Ox 12 -
1=0
2y(1 p
ai x(K (K-itjjpoo) |lei+ 1llo + 4 - kk+]
.kk Rmax.
(1-
(1 7)3
1=
Recall that in Theorem D.1 and (F.1) we define Emax max eello. We have that I|Q QT | is further upper bounded by
l1Q- -=* 1|
(F.28)
5 2y k1+-)
K K-1
Emax + 4 ((11-k41)
x(K - -i+s;No) Ci 2
O. Rmax
(1-
(1 7)
ł= 1=0
27(1 27(1- (xt1)
K-
K+
Σ
7d x(K - - Emax
Rmax
(1 (1-7)
K+1
K+1
(1 71-
j=0
where the last equality follows from the definition of (o.)osisK in (F.18). We simplify the summa- tion on the right-hand side of (F.28) and use Assumption 4.3 to obtain
K-1-1
Σ
M.. i jj,,00)
1 k+1
1=
1=
K-1
1 1-7 7
K K-itj-1 x(K - i jiN,o)
7 K+I
j=0 1=0
1 1-7
2p.
<
(F.29)
g K+1
1 77)
m=0
31

---

Under review as a conference paper at ICLR 2020
where the last inequality follows from (4.5) in Assumption 4.3. Finally, combining (F.28) and (F.29), we obtain
||Q QTK 11,, I 27 Qu. (1 (1- Emax
4,
Rmaxx
(1 (1-
which concludes the third step and hence the proof of Theorem D.I.
F.2 PROOF OF THEOREM D.2
Proof. Recall that Algorithm we define Y; + maXacA Q(5++ A a), where Q is any function in F. By definition, we have E(Y; SS = A, a) = (T)) for any (s, a) S A. Thus, TQ can be viewed as the underlying truth of the regression problem defined in (D.2), where the covariates and responses are {S; A:) and (Yi))( respectively. Moreover, note that TQ is not necessarily in function class F. We denote by Q" the best approximation of TQ in F, which is the solution to
minimize JEF
f - = -)), -.S A.]²]
(F.30)
For notational simplicity, in the sequel we denote (S,, A,) by X, for all i E [n]. For any f E F, we define I| = 1/n [x,)) Since both Q and TQ are bounded by Vmax = Rumax/ /1 - 7), we only need to consider the case where log N3 S n. Here N₂ is the cardinality of (6, Moreover, let fi,...,NN, be the centers of the minimal 5-covering F. Then by the definition of d-covering, there exists A* E [Ns] such that I| Sx- Il S. is worth mentioning that k* is random variable since Q is obtained from data.
|1
In the following, prove (D.3) in two steps, which are bridged by B[[l@ TQ
Step (i): We relate Æ - TQl with its empirical counterpart || - --QI2 Recall that we define Y; RG + max.cA ((5++1, a) for each E [v]]. By the definition of Q, for any f E F we have
Σ 1=1
Yg ((x))) S I [(x,))²
(F.31)
For each i E [n], we define & Y; (TTQ)(X).. Then (F.11) can be written as
-QTTI < |l - TQII? +
2
Σ & [Q(x,) - f(x.))
(F.32)
n
Since both and Q are deterministic, have B(If TQl)2) |l TQ Moreover, since B(E Xx)) by definition, we have E[G, g(X,)] = 0 for any bounded and measurable function g. Thus, it holds that
E Σ & (2(()())))))))))))))(() (Q(x)) ((x)))((xx]] =
Σ & {
((xx)x(re(xx1]
(F.33)
1=1
In addition, by triangle inequality and (F.33), we have
n
Σ & (²(x.) - (IQ))x01)
E
& 1²(x.) fu. (x.3) + E Σ & (x.)
[
(F.34)
where fx- satisfies || I1 < 8. In the following, upper bound the two terms the right-hand side of (F.34) respectively. For the first term, by applying Cauchy- -chchy-SShwarz inequality
32

---

Under review as a conference paper at ICLR 2020
twice, we have
}
1/2
E
S. (Q(x,)
(x-(()))
s svn. vn.
E
Σ
-1Q
fa- 111
nn-
E
2
1/2
[EI ft-1l?))
1/2
no [E(E3)] 1/2
(F.35)
where we use the fact that (een have the same marginal distributions and q fx- 1l S 6. Since both Y; and TQ bounded by Vmaxx &. is bounded random variable by its definition. Thus, there exists constant Cg > 0 depending
such that E(E?) C V22 max. Then (F.35) implies
- (X.) }
E
& 10(x.) fa-
$ Ce Vmmx nd.
(F.36)
It remains upper bound the second term the right-hand side of (F.34. We first define N₂ self-normalized random variables
2, - E ( - -1 (TQ)
(F.37)
for all E [Ns]. Here recall that {f>bse[Na) are the centers of the minimal ò-covering of F. Then we have
[fk- (X,) - (T)) } =vn BilBBl TQU 1Z
E
E
Vn. E - TQQIn + 11 - Sh. [x [2 vn. B |1|@ ((11@-TQU - +0] - }.
B
(F.38)
where the first incquality follows from triangle inequality and the second inequality follows from the fact that ||Q fk= oo I 8. Then applying Cauchy-Schward inequality to the last term on the right-hand side of (F.38), we obtain
1/2
B [ - TQll, + 5|
IZ }
BBlll@ - -TQIIn -5 -81²}
E ((Z2)-)
((=(110 < [TQ1]]]] +0)
E max 23) 1/2
(F.39)
JE[N]
where the last inequality follows from
E - - TQIIa] < - 1/2 /
Moreover, since & is centered conditioning on (Xi and is bounded by 2Vmax & is sub- Gaussian random variable. In specific, there exists an absolute constant Hę >> 0 such that ||Eillz S He Viax for each i E [n.]. Here the -orm of random variable W E R is defined as
1 sup p [LE(IWP))]
p21
By the definition of Z, in (F.77,, conditioning (Xi)iem)) & (]((,)) (TQ)(X.) centered and sub-Gaussian random variable with
| [(,())) (TQ)( S Vmax |4(X,) - (X.)(X.))-
Moreover, since Zj is summation of independent sub-Gaussian random variables, by Lemma 5.9 of ?, the thymnorm of Z, satisfies
1 n
1/2
||Zy|ls C Hgg Vmax |15 - -QI==1
Σ (x,) -
C Hlg V
maxx
33

---

Under review as a conference paper at ICLR 2020
where C > 0 is an absolute constant. Furthermore, by Lemmas 5.14 and 5.15 of ? Z3 is sub-exponential random variable, and its the moment-generating function is bounded by
E E(exp(t z3)l & exp(C e H V
(F.40)
for any satisfying C' 14 H V2 S where C and C' are positive absolute constants.
Moreover, by Jensen's inequality, we bound the mooenttggeneratnng function maxje[Na] 23 by
E
exp(( max 23) JE[No]
E (exp(t 27)].
(F.41)
jE[Na]
Combining (F.40) and (F.41,, we have
E max
73) S C². JEIN]
H
V2 max log No,
(F.42)
where C is an absolute constant. Hence, plugging (F.42) into (F.38) and (F.39), we upper bound the second term of the right-hand side of (F.33) by
E [xk- (X.) - (TQ)(X
$ {
- [E[@--TQ133)
1/2
+ +8) .C- He Vmax vn log No.
(F.43)
Finally, combining (F.32), (F.36) and (F.43), we obtain the following inequality
E [[I@@ - TQ
s inf E [||s- TQl + Ce Vmax 8
(F.44)
JEF
+ [E[l (TQ) (TQ) 122 +0) .C. ..- HE Vmax Vlog No/n
C V Vmax Ns/nn { - (TT))1133 + inf
1/2
inn in B[If--QUII CC Vima JEF
where C and C" are two positive absolute constants. Here in the first inequality we take the infimum over F because (F31) holds for any f F, and the second inequality holds because log Ns S n.
Now we invoke a simple fact to obtain the final bound for (e[IQ-TQQ1 from (F.44). Let and be positive numbers satisfying a² < 2ab+cc For any (0. 1], since 2ab <. (1 b3 /c. we have
a² < (1 +6)2 1/ +c)
(F.45)
Therefore, applying (F.45) (F.4)) with a² = _ TQ b C Vmax Vlo Ns/n, and = yer Elll -TQI + C' Vnax 5, we obtain
B[1@ - TQ s <1 + e) inf E [[I - TQI +C- V2 max log Ns/(1e) + C", -max 8,
JeF
(F.46)
where C' and C" are two positive absolute constants. Now we conclude the first step.
Step (ii). In this step, we relate the population risk || - TQl with Ell@ - TQ which
is characterized in the first step. To begin with, we generate i.i.d. random variables {X; (5,, At) following a, which are independent of {(,,, A,, R,, St) he[m]- Since || fx- ll S 5,
for any E S x A, we have
[Q(x)) - - (
[f)-(2) = =1((z) fa-(x) -1(xx) fo- 2(TQ) < 4Vmax 6,
(F.47)
34

---

Under review as a conference paper at ICLR 2020
where the last inquality follows from the fact that [[ Viax and bl Then by the definition of ||Q TQl and (F.47), we have
Vmax for any f E F.
72 n
- -Q1 E.
((xx)) - (x)]²
I B
11ē BB11ē
TQl
Σ fi- (X,, - (T.) (x)) + 8V 8
= = - TQI)) +
x,) (x,, hys (X,,
+ +V
(F.48)
where we apply (F.47) to obtain the first inequality, and in the last equality define
hz y) (v)(v) (TQ) [f)(z) (TQ)(=))*
(F.49)
for any (x. v) E x dom. By the definition of h in (F.49), we have (1, f)1 & 4V for any (z, S x and (X,, = 0 for any i E [n].. Moreover, the variance of (X, X,) is upper bounded by
x A and any j E [Na]. Note that h2- is a random function since he is ran-
Var [ X = 2 Var ((()x))((((((x)))
s 2B [f)(x.) - (XI) s <8T² Vmax
where we define by letting
T max (4V2 log No/n, max E
(F.50)
jEINo]
Furthermore, we define
T sup
Σ (X,,, X.)/ JE[Na]
(F.51)
Combining (F.48) and (F.51), we obtain
|| - TQI: < - TQl + T/n E(T) + 8Vmax 8.
(F.52)
In the sequel, we utilize Bernstein's 's inequality establish an upper bound for ETT), which is stated follows for completeness.
Lemma F.3 (Bernstein's Inequality). Let UI.... Un be independent random variables satisfying E(U,) 0 and [U;] < M for all E [n]. Then for any > 0, we have
12
PP
Σ
U
22
S
2exp
2M 1/3 20
where 0² === Ei Var(U:) is the variance of Σim U..
We first apply Bernstein's 's inequality by setting U, hyy Xi)/T for each i [n]]. Then take union bound for all [N&] to obtain
-12
P(T 2) P
sup [i[[NN]
Σ (x,( 2t < 2Ns exp
8V2
[t/(3T) + +n]
(F.53)
Since T is nonnegative, we have E(T) = lo P(T 2 t)dt. Thus, for any E (0,3T n), by (F.53) it holds that
3'n
12
-3Y
E(T) S
P(T 2 l)dl S
2N,
exp
di + 2N,
exp
di
16V2
n
J3
16V2
2
-972
32.
22 max n/u exp
32.N
V2 max/ /(3)) eep
16V2
n2
161/2
(F.54)
35

---

Under review as a conference paper at ICLR 2020
where in the second inequality the fact that l (op(-t/2)cc I 1/s exp(-s2/2) for all > O. Now we set 4Vmax vn n log N8 in (F.54) and plug in the definition of Y in (F.50) to
obtain
E(T) 4V vn log No- + 8V v log No 6V vn/ log No S 8V vn log No, (F.55)
where the last incquality holds when log N₂ 2 4. Moreover, the definition of T in (F.50) implies that T S max[2V max / Vlog Ns/n, I|Q - TQl,, + 6). In the following, only need to consider the case where Y S Q| - TQ + 6, since we already have (D.3) if I|Q TQII + å S 2V /lo No/ n. which concludes the proof.
Then, when Y S Q TQ]|, 8 holds, combining (F.52) and (F.55) obtain
@1 TQl - 18 [|[ TQ] + 8V Vlog(N)/n || TQ] + 8Vmax v log N&/n. 8V 6
- E [1[ - []]] + max / log Ns/n || TQ] + 16V max 8.
(F.56)
We apply the incquality in (F.45) to (F.56) with a = | - TQ = Vaxa v Vlog No/n, and
el|l TQ + 16V 8. Hence we finally obtain that
I - TQl s (1 + <) [[[ TQ
+ (1 + e)². 64V
(1+ 18V 6,
(F.57)
which concludes the second step of the proof.
Finally, combining these two steps together, namely, (F.46) and (F.57), we conclude that
I TQI? (1 +) inf [1I TQI + C1 V2 Vmxx loog Ng/(1r <) C2 Vmax 8,
FEF
where C1 and C2 two absolute constants. Moreover, since Q E F, we have
inf
Bllf !
s sup
{ inf B[llf - TQlN
JEF
QEF fEF
which concludes the proof of Theorem D.2.
G PROOF OF THEOREM E.4
In this section, we present the proof of Theorem E.4. The proof is similar to that of Theorem 4.4, which is presented in $D in details. In the following, we follow the proof in $D and only highlight the differences for brevity.
Proof. The proof requires two key ingredients, namely the error propagation and the statistical error incurred by a single step of Minimax-FQL.
Theorem G.1 (Error Propagation). Recall that (Q*losAsK are the iterates of Algorithm and (TK; ux) is the equilibrium policy with respect to QK- Let Q be the action-value function corresponding to (TK, V² where V is the best-response policy of the second player against тк- Then under Assumption E.3, we have
20p "7 (1 7)- Emax +
K
|1Q - -2 S
Rmaxx
(G.1)
(1-
where we define the maximum one-step approximation error Emax = maxKE[K] IT 1u and constant 6n2 is specified Assumption E.3.
Proof. We note that the proof of Theorem D.1 cannot be directly applied to prove this theorem. The main reason that here we also need to consider the role played by the opponent, namely player two. Different from the MDP setting, here Q is fixed point of nonlinear operator due to the fact that player two adopts the optimal policy against тg. Thus, need to conduct a more refined analysis. See $ for detailed proof.
36

---

Under review as a conference paper at ICLR 2020
By this theorem, need to derive upper bound of Emax- We achieve such goal by studying the one-step approximation error ITQ - Qu for each A: E [
Theorem G.2 (One-step Approximation Error). Let F B(S A B, Vmax) be family of measurable functions on 8 x A B that are bounded by Vimax Rmax/( (1 7). Also, let {(S,, A,, B,) be n iid. random variables following distribution a E P(S A x B). For each i E [n]] let Rg and S be the reward obtained by the first player and the next state following (Si, A,, B.). In addition, for any fixed Q E F, we define the response variable as
Y1 R4 +
max min Banx' dow (Q(S), [))]- T'EP(A) EE(())
(G.2)
Based on ((X,, A,, Yi) hejmj we define Q as the solution the least-squares problem
min PEF
Σ [s(S;, A.) Yi]²
(G.3)
Then for any E (0, and any 5 have
l - TQ S (1 + +)² sup inf [l - Tgll C. V22 V .) log No + C² Vmax 8, (G.4)
SEF FEF
where C' and C" are two positive absolute constants, T is the Bellman operator defined in (E.5), No is the cardinality of the minimal 5-covering of F with respect to -nomm.
Proof. By the definition of Y; in (G.2), for any (s, b) ES x A min) we have
BYY; S: = A, = a, B; b) = =r(s,a) + P l...))))))) max min Be' [Q a. b)] (Q(d',, (EEP(A)'EE((S
(TQ)(s,
Thus, TQ can be viewed as the ground truth of the nonlinear least-squares regression problem in (G.3). Therefore, following the same proof of Theorem D.2, we obtain the desired result.
Now we let F be the family of ReLU Q-networks Fi defined in (E.8) and set Q = Qu in Theorem G.2. In addition, setting ε and = 1/n (G.4), we obtain
1|@++1 T 2 < 4 sup inf
|| - Toll + C. Vilue/n /n log N1
gef, feFi
I 4- sup inf - + C. V2 V/ax/n log N1,
(G.5)
fee fEF,
where C' is a positive absolute constant, N1 is the 1/n-covering number of Fi, and function class G defined as
9. = (f:
R( E G((,, B, H,, Hi))))) for any (a, E AAxB)
(G.6)
Here the second inequality follows from Assumption E.2.
Thus, it remains to bound the -eror of approximating functions 91 using ReLU Q-networks in Fi and the 1/ I/n-conering number of Ft. In the sequel, obtain upper bounds for these two terms.
By the definition of G. in (G.6), for any E 91 and any (a, b) E A x B, have f(;, a),, g((2i 4,, 3, H)))set))) Following the same construction as in $F2, we can find a function f in F(L", +'+1 +1 ,8*) such that
(V( Íll z max 28, 200 ((29] +G, = =
m20 jEln
which implies that
sup inf ||ʃ - 1'1133 S a1--1 reesh JEF,
(G.7)
37

---

Under review as a conference paper at ICLR 2020
Moreover, for any f Fi and any (a,b) x x B, we have f(,,a,)) E F(LL, ([""{d])f= (d)) Let No be the d-covering of F(L", {dj) + ,*) in the -norm. Then for any f E Fi and any (a, b) E A x B, there exists Jab E No such that [[[(; //(aa,,)) Sa I 6. Thus, the cardinality of the (6, Fi, Illo) satisfies
[V 1| ID| - |4
(G.8)
Combining (G.8) with Lemma D.4 and setting 8 = /n.. obtain that
log N S A [ log [N8|
- |A| [B] (s* + 1) log 2n (L" + 1) D2
B L"
max log(d') x |A| [B] n (log 2+24 JE(
(G.9)
where D = -I (dž + 1) and the second inequality follows from (4.7).
Finally, combining (G.1), (G.5), (G.7), and (G.9), we conclude the proof of Theorem E.4.
G.1 PROOF OF THEOREM G.1
Proof. The proof is similar to the that of Theorem G.I. Before presenting the proof, we first introduce the following notation for simplicity, For any k E (O...., K 1}. we denote TQR by Qu+1 and define @k Qx Qu- In addition, throughout the proof, for two action-value functions Q1 and Q2. we write Q < Q2 if (s. a. b) 2 Q2(s, a, b) for any (s, b) E S A x B, and define Q1 2 Q2 similarly. Furthermore, we denote by (Tk, v/)) and (x*,x") the equilibrium policies with respect to Q by Q", respectively. Besides, in addition the Bellman operators T and T defined in (E.4) and (E.5), for any policy of the first player, we define
T (s, a, b) = r(s,a, b) + (EspP--laa.) min ('EP((B
Bn'n=, [Q65' ,313
(G.10)
corresponds to the case where the first player follows policy т and player 2 adopts the best policy in response to т. By this definition, it holds that Q' = T Q', Unlike the MDP setting, here 7 a nonlinear operator due to the minimization in (G.10). Furthermore, for any fixed action-value function Q, we define the best-response policy against π with respect to Q, denote by V(T, Q), as
v(m Q) (s) argmin Bawn,br [Q(ss a, EBEP(B)
(G.11)
Using this notation, write (G.10) equivalently as TT Q(s a, b) = r(s, a, b) + (p a, b).
Notice that (=,v(s.Q) Q) is linear operator and that "q = U(TQ. Q) by definition.
Now we are ready to present the proof, which can be decomposed into three key steps.
Step (i): In the first step, we establish recursive upper and lower bounds for {Q- QuTocksk. For each & E {O...., K- - 1}. similar to the decomposition in (F.3), we have
Q - = Q Q--Q++1=Q'--
Qx + (I Q+ TÂx) @k+1.
(G.12)
where ग² is part of the equilibrium policy with respect to Q" and 7 is defined in (G.10).
Similar to Lemma F.1, we utilize the following lemma to show T Q 2 TQp-
Lemma G.3. For any action-value function Q S x A B > IR, let (IQ, vQ) ) be the equilibrium policy with respect to Q. Then for and any policy æ of the first player, it holds that
T TQ T
Furthermore, for any policy :: S + P(A) of player one and any action-value function Q, we have
T=) = T < T
(G.13)
for any policy v: S > PPB), where u(z, Q) is the best-response policy defined in (G.11).
38

---

Under review as a conference paper at ICLR 2020
Proof. Note that for any s' E S, by the definition of equilibrium policy, have
min Bat [Q( ((8',,o a', [b]] min r'EP(B)
Ba' [Q(s', a', 8')]
T'EP(A) MEP((B
Thus, for any state-action tuple (s, a, b), taking conditional expectations of with respect to P(-1s,a, a) b) on both ends of this equation, have
(T*9 r(s, 0) + 7 Bgsp( (2..)) min Ba' (Q(s', (EP(()
=r(s,,, b) + 7 Pg (.,,b)
min ('EP(A) EP(())
max
En w~w QQ(s d' 8)] ] (TQ)
which proves T TQ. Moreover, for any policy of the first player, it holds that
max min I'EP(A) (PP(())
Be'' - (Q d' b0] 2 min v'EP(B)
Ea'Nn,br [Q(5', a' [)]-
Taking expectations with respect s P( s, a, b) on both ends, establish TQ > T
It remains show the second part of Lemma G.3. By the definition of (ST, Q), we have
Pal'nn,b' ()) (Q(s' a'' b),
min E(EP(B)
Ea'-a, and [Q(s',
which, combined with the definition of T in (G.10), implies that ( = T.Q. Finally, for any policy y of player two, we have
min Eainn Moo (Q(s', d', K)] 2 Ba' [Q( 1/), EEP((
which yields T & Q..Q. Thus, we conclude the proof of this lemma.
Hereafter, for notational simplicity, for each k; let (Ik, v&) be the equilibrium joint policy with respect to QR. and we denote u(T", Qu:) and U(TA, Q*) by Di and in. respectively. Applying Lemma G.3 to (2.12) and utilizing the fact that Q = 2 Q", we have
- @u+1 S (Q' - T 2x) ) + e++1 (T Q T Qx) + 2k+1
< (1 Px Q - T v. Qk) + Øk+1 = 7 p th (Q' - Qxx) + Ck+1.
(G.14)
where the last inequality follows from (G.13). Furthermore, for lower bound of Q" Qk+1, similar (F.5), have
Q' - (IQ' T Q*) + (T Q" T Qx) + Qk+1
2 (T Q" T Qu) + 2++1 2 7. p= (Q' - Qx) + @k+1:
(G.15)
where the both inequalities follow from Lemma G.3. Thus, combining (G.14) and (G.15) we have
q. pa Ih (Q" - -xx) 0x+1 2 Q" - Q 2 P (Q' Q+) @k-1-
(G.16)
for any (0, ...,, K 1}. Similar the proof of Lemma F.2 by applying recursion (G.16), obtain the following upper and lower bounds for the error propagation of Algorithm 4.
Lemma G.4 (Error Propagation). For any k, {0, (0..,...,44 K 1} with k < E, we have
{-1
-
Q S 2 t-1-j
@e px Dt. p Di+1
imk
+ tge-k, ip- px in-2... p (Q"
(G.17)
[-1
Q' Q 2
/ --ا
1pse wel aud) 20e2 2 1 0i+1
i=
+ thi-k.
(pre- pao p (Q"" (Q"") Qa)) (G.18)
39

---

Under review as a conference paper at ICLR 2020
Proof. The desired results follows from applying the inequalities in (G.16) multiple times and the linearity of the operator px, for any joint policy v).
The above lemma establishes recursive upper and lower bounds for the error terms {Q" QulosksK-I- which completes the first step of the proof.
Step (ii): In the second step, we characterize the suboptimality of the equilibrium policies constructed by Algorithm 4. Specifically, for each Tk. we denote by Q the action-value function obtained when agent one follows тт while agent two adopt the best-response policy against тT. In other words, Q is the fixed point of Bellman operator 7* defined in (G.10). In the following, we obtain an upper bound of Q Qi which establishes the notion of suboptimality of policy (Tk, Pk) from the perspective of the first player.
To begin with, for any k. we first decompose Q" - - by
Qi Q' -i = (T Q' T Q" Qu) + (T Qk - Tx* + (TTMQu TTT
(G.19)
Since Fy is the equilibrium policy with respect Qu, by Lemma G.3, we have T Q: S T Q Recall that (r",""" 1²*) is the joint equilibrium policy with respect to Q*. The second argument of Lemma G.3 implies that
Q' STT Q"
T S T Q
(G.20)
where in v/T'' Qk) and we define Dg u(TKK Qi). Thus, combining (G.19) and (G.20) yields that
OSQ - Q S 7. p Me (Q' - Qx) +7 P (Ōx - -Qi) 7 ( (p .h P Pz (Q" - -Qx) +7 pr (Q" - Qi)-
(G.21)
Furthermore, since - 7. pr is invertible, by (G.21) we have
0 5 Q Q S 7 (I- - 7 p= [p Ey (Q* -xx) p (Q* -Q+)]
(G.22)
Now we apply Lemma G.4 to the right-hand side of (G.22). Then for any S we have
px By (0 - Qi) s
Σ 7
f-1-j (pr" we pt tt-1 px Pit1) 0i+1 (it1
i=k
+ tgt (px pips" Pe-1... pa pa 2x (Q) QR)), (G.23)
t-1
prc (Q- - Q:) 2
(-1-i (prene prcee- P1tt1 li+1
i=k
+ + pp prx. -Q² Qa). (G.24)
Thus, setting = K and 0 in (G.23) and (G.24), we have
Q' -
Qk < (T (1-7. pxxx -1
(G.25)
K-1
Σ K-1,
(px' Dx ps F pa pat1))1)) - (pax DK pak 10k-1.. p1111. a++1
1=0
+ K+1,
[(po pa .x--.. pm Bo) (pai peK-nik-I poo.Ro) -00)
To simplify the notation, we define {ar 1K as in (F.18). Note that we have Σx= a; = - definition. Moreover, we define K linear operators {Ox) k=o as follows. For any S K --11 1,
O 1-7 (I - px) -1 '( exx ix p p=ppp==x_- ... pm (+1)) #x-1...
(pTK,PK pnk L . p=..1.
40

---

Under review as a conference paper at ICLR 2020
Moreover, define Og by
OK 1-2,1110 7 ( (pr Ux pa .K--1... 1... px P0) (PEKIPM pex 2. 1... pro:
2
Therefore, taking absolute values on both sides of (G.25), we obtain that
(Q,(s, - (x(ssa, a, b)
$ 2y(1 (
Σ ai (0.lett))(ssa aak ax (OxlQ* [ol)(s,a.)) (G.26) ==0
(1 71-
for any (s, a, E x A x B, which concludes the second step of the proof.
Step (iii): We note that (G.26) is nearly the same as (F.19) for the MDP setting. Thus, in the last step, we follow the same proof strategy as in Step (iii) in FF.11 For notational simplicity, for any function f: S x A x B + IR and any probability distribution E P(S x A x B), we denote the expectation of f under μ by p(f). By taking expectation with respect to in (G.26), we have
||Q- - Q2 I 2y(1 2x(1- Py(1-*Kt) x
K
Σ ay (e.xOOlleett) + +ak m(Ok Q- - -261] (G.27)
(1 7)²
By the definition of Oj, can write u(O:lei+1))
((Olletta))= = 2
p
[pr (pr iu pr .K-1.... px pr P111)
(G.28)
1=0
+ (
... prtt Pre. |ettll
pER-I.K-1
To upper bound the right-hand side of (G.28), we consider the following quantity
u[p ... ...]) 1 ISXANB pTm-i........ ... Pm [s] a, b)dp(s,
where {n:: S + P(A x B)Eemml are m joint policies of the two-players. By Cauchy-Schwarz inequality, it holds that
[[pmm.... PT) s Us d( (Tm pim-i... ... pr 1)
1/2
(s, b) do(s,, a,
do USndve (((s,,,))Pdd33, where <(m;; o) is the m-th concentration parameter defined in (E.9). Thus, by (G.28)we have
S <k(m; |l
((O.lentil) - (1 7)
K(K - -i i+s;p,,) ||e
(G.29)
3=0
Besides, since both Q" and @u are bounded by Rmaxx (1 7) in lo -norm, we have !OOIQQ" - -Qol) < 2 Rmax/ (1 7))
(G.30)
Finally, combining (G.27), (G.29), and (G.30), we obtain that
l|Q - R 111,0
2y - K+))
K-1
47 07(1-2k11
7)
ai
x(K - j:p,n) -le.t1llo 3
(1 7)3
.aK Rmax
==
2y(1 - -g
K
7)7 K K-i-1
4 K7
T x((K - -it ++H1)
Emax +
Rmaxx
(1 (1-))
g K+1
(1 7)2
1=0 1=
41

---

Under review as a conference paper at ICLR 2020
where the last inequality follows from the fact that Emax | Ileillo. Note that in (F.29) show that it holds under Assumption E.3 that
K-1 (1 ( ΣΣ ==U j=0
Pu.
- (1 (1-gk+))(1-)))
1-
Hence, we obtain (G.1) and thus conclude the proof of Theorem G.1.
42


Reviews:
[{"review_id": "SyeZTEeEFH", "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": "This paper analyze the off-policy policy improvement algorithm with a very limited sparse ReLU function class. Although some of the results are interesting, I have lots of concern on the motivation of this work. I believe this paper is technically correct, but the authors focus on a very simplified case: they just use samples generated from a fixed sampling policy, which gets rid of the analysis of exploration and sample complexity that is a main focus of the reinforcement learning community. From my point of view, this may not be some analysis of reinforcement learning, at least not for Deep Q-learning, but more likely to be some learning theory of off-policy FQI. The main theorem investigates the statistical error and convergence rate of this problem, which can be of individual interest. But overall, I think the problem the authors want to solve is not a traditional reinforcement learning algorithm, and it is not appropriate to introduce the result as the theoretical analysis of Deep Q-Learning.\n\nDetailed comments:\n1. I think the assumption of Sparse ReLU network is too strong and generally not held in practice. Also, the optimization of such kind of network is painful, as the ell_0 constraint makes the optimization problem NP-hard. In other words, I think the authors only handle a very specific case under very ideal condition like assuming an oracles that can return the optimal network each turn.\n2. The equivalence between FQI and target network is well-known and may not occupy so many places in Sec 3. Also, the results in Appendix B can be simply derived follows the recent development of neural network optimization. As this may be not the main contribution of this paper, I think it is better to omit these parts to make the paper more neat. \n3. Moreover, in appendix B, the authors assumed the function class as two-layer ReLU network, which is different from the assumption in the main text and cannot justify the global convergence of (3.4).\n4. It is somewhat strange of assume a sampling distribution, as when we say Q-learning, we want to balance the exploration and exploitation given current estimation Q. Even in Deep Q-Learning, the data are sampled with \\epsilon-greedy policy w.r.t the current Q network. This kinds of problems are more like off-policy policy improvement. I think call it the analysis of Deep Q-Learning is somehow not accurate and over-claimed. Maybe better called off-policy policy improvement with deep neural networks.\n5. Theorem 4.4 is an interesting result as it shows that the error of the proposed algorithm can be decomposed into the a statistical error which depends on the smoothness of the operator Tf and an algorithm error that depend on the number of iterations. I am wondering what's the main technical differences between this work and [1], as I find the main difference is [1] don't give K-dependent algorithm error, instead assuming K have a order of log 1/epsilon to ensure algorithm error is smaller than \\epsilon. I feel it's not so hard to derive a bound that combines statistical error and algorithm error for [1]. Also, FVI in [1] is not in spirit totally different from FQI in this paper given that [1] use the maximum operator over action when do FVI, not take expectation over the target policy. I hope the authors can clarify in their paper.\n6. The authors don’t mention much of the target network in the main theorem. I know the generalization to the update with target network is not so hard, but as the authors mentioned so much time in the main text, shall it be better to include the result with target network?\n\nStill, in my opinion, the main theorem has its own value. However, it is not proper to claim as a theoretical analysis of Deep Q-Learning. Also, I feel the function class is too restricted and the optimization issue in the proposed algorithms cannot be simply solved, and the main analysis is similar to [1] with little generalization to Holder smoothness. Thus, I tend to reject this paper.\n\n[1] Munos, Rémi, and Csaba Szepesvári. \"Finite-time bounds for fitted value iteration.\" Journal of Machine Learning Research 9.May (2008): 815-857.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of 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": {}}, {"review_id": "SJlXXDdAcr", "reviewer": "AnonReviewer4", "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": "Overview:\n\nThis paper provides an analysis of fitted Q-iteration in the off-policy reinforcement learning setting, for the setup where the value function class of interest is a class of neural networks. The provide bounds on the rate at which fitted Q iteration converges to a near-optimal policy under the assumption that the transition dynamics satisfy a certain notion of Holder smoothness. This result is motivated by the problem of understanding why deep Q-learning works, which the authors relate to the problem above via certain simplifying assumptions. The authors also extend this result to give similar guarantees for two-player zero-sum stochastic games.\n\nReview:\n\nThis paper addresses an important and challenging problem, and the results appear technical sound. It is also fairly thorough and well-written. However, my overall feelings toward the result are mixed, because I believe the assumptions the authors make are so strong that they essentially remove most of the interesting problem structure, and consequently the results follow by straightforward application of known techniques. \n\nTwo major challenges in understanding DQN are as follows:\n1) Exploration: Why does the algorithm successfully explore and solve MDPs with large state spaces?\n2) Generalization: How do the overparameterized neural networks used for value function approximation help with generalization (or exploration)?\n\nThe issue of exploration is assumed away by the authors, as they work in the batch/offline RL setting where examples (s,a,r,s') are i.i.d., and the assume that the so-called \"concentrability coefficient\", which measures mismatch between the data distribution and the data induced by the optimal policy, is bounded. This assumption is standard in the analysis of fitted Q-iteration for off-policy RL (eg, Munos and Szepesvari '08), but it implies that the algorithm does not need to solve a challenging exploration problem, since the data-gathering policy has good coverage. Unfortunately, the authors do not justify why this assumption should hold for DQN.\n\nThe standard analysis for off-policy fitted Q-iteration does not simply require that the concentratability coefficient is bounded, but also requires another strong assumption, which is that the function class is closed/complete under bellman updates. In general, this is a difficult property to verify, and it is well-known that fitted Q-iteration can cycle and fail to converge when it does not hold. This leads to the issue of generalization: The way the authors get around the issue of closedness/completeness is to work in the fully nonparametric regime: They take the class of neural nets under consideration to be large enough to approximate any Holder smooth function, then show that under mild assumptions on the dynamics this class of Holder smooth functions is closed under bellman updates. This is a good trick, but it has an unfortunate consequence, which is that by blowing up the class of neural networks, the generalization bound one can prove is quite weak. Ultimately, the generalization bound the authors give follows the standard rate for Holder-smooth functions in nonparametric statistics, which is exponential in dimension whenever the function class is $p$th order smooth for constant $p$. For example, when the class of functions is lipschitz the rate is $n^{-1/(2+d)}$, where $n$ is the number of examples. Since we are paying the fully nonparametric rate for generalization here, this begs the question of why neural nets were even used to begin with, which is not addressed.\n\nTo conclude, this is a certainly a challenging problem, but I don't think the paper is transparent about the limitations of the techniques (as described above) and I believe the title of the paper, \"A theoretical analysis of deep Q-learning\", is too strong given the shortcomings of the results.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of 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": {}}, {"review_id": "SJeRYDrnYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The authors provide a theoretical analysis of deep Q-learning based on the neural fitted Q-iteration (FQI) algorithm [1]. Their analysis justifies the techniques of experience replay and target network, both of which are critical to the empirical success of DQN. Moreover, the authors establish the algorithmic and statistical errors of the neural FQI algorithm.\nThen, the authors propose the Minimax-DQN algorithm for the zero-sum Markov game with two players. They further establish the algorithmic and statistical convergence rates of the sequence of action-value functions obtained by the Minimax-DQN algorithm.\n\n[1] Martin Riedmiller. Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method. In European Conference on Machine Learning, pp. 317–328. Springer, 2005.\n\nThe strengths of this paper are as follows.\n1. This paper is theoretically sound. The authors establish the convergence rates with detailed proofs step by step. \n2. It is the first theoretical analysis that provides the errors of the neural FQI algorithm with a ReLU network. This analysis provides a rigorous approach to understand deep q-learning algorithms.\n3. The authors propose an extension of DQN for the zero-sum Markov game with two players. They further analyze the convergence rates of the sequence of action-value functions obtained by the proposed algorithm.\n\nMinor comments:\n1. Page 2: In Notation, \"$\\|f\\|_{2,v}$\" may be \"$\\|f\\|_{v,2}$\"。\n2. Page 3: In the 2th line of Section 2.2, \"$\\{d_j\\}_{i=0}^{L+1}$\" may be \"$\\{d_i\\}_{i=0}^{L+1}$\".\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors offer theoretical guarantees for a simplified version of the deep Q-learning algorithm. However, the majority of the reviewers agree that the simplifying assumptions are so many that the results do not capture major important aspects of deep Q-Learning (e.g. understanding good exploration strategies, understanding why deep nets are better approximators and not using neural net classes that are so large that can capture all non-parametric functions). For justifying the paper to be called a theoretical analysis of deep Q-Learning some of these aspects need to be addressed, or the motivation/title of the paper needs to be re-defined. 
Decision: Reject