On Computation and Generalization of Generative Adversarial Imitation Learning
Authors: Minshuo Chen
Yizhou Wang
Tianyi Liu
Zhuoran Yang
Xingguo Li
Zhaoran Wang
Tuo Zhao
Venue:  (2020)

Abstract: Generative Adversarial Imitation Learning (GAIL) is a powerful and practical approach for learning sequential decision-making policies. Different from Reinforcement Learning (RL), GAIL takes advantage of demonstration data by experts (e.g., human), and learns both the policy and reward function of the unknown environment. Despite the significant empirical progresses, the theory behind GAIL is still largely unknown. The major difficulty comes from the underlying temporal dependency of the demonstration data and the minimax computational formulation of GAIL without convex-concave structure. To bridge such a gap between theory and practice, this paper investigates the theoretical properties of GAIL. Specifically, we show: (1) For GAIL with general reward parameterization, the generalization can be guaranteed as long as the class of the reward functions is properly controlled; (2) For GAIL, where the reward is parameterized as a reproducing kernel function, GAIL can be efficiently solved by stochastic first order optimization algorithms, which attain sublinear convergence to a stationary solution. To the best of our knowledge, these are the first results on statistical and computational guarantees of imitation learning with reward/policy function ap- proximation. Numerical experiments are provided to support our analysis.


Published as a conference paper at ICLR 2020
ON COMPUTATION AND GENERALIZATION OF GENER- ATIVE ADVERSARIAL IMITATION LEARNING
Minshuo Chen" Yizhou Wang Tianyi Liu" Zhuoran Yang?
Xingguo Li
Zhaoran Wang"* Tuo Zhao'
*
Georgia Tech, t Xian Jiaotong University, & Princeton University, ** Northwestern University
ABSTRACT
Generative Adversarial Imitation Learning (GAIL) is powerful and practical ap- proach for learning sequential secision-making policies. Different from Rein- forcement Learning (RL). GAIL takes advantage of demonstration data by experts (e.g.. human), and learns both the policy and reward function of the unknown en- vironment. Despite the significant empirical progresses, the theory behind GAIL is still largely unknown. The major difficulty comes from the underlying temporal dependency of the demonstration data and the minimax computational formula- tion of GAIL. without convex-coneat structure. To bridge such gap between theory and practice, this paper investigates the theoretical properties of GAIL. Specifically, we show: (1) For GAIL with general reward parameterization, the generalization can be guaranteed long as the class of the reward functions is repro- properly controlled; (2) For GAIL, where the reward is parameterized ducing kernel funetion, GAIL can be efficiently solved by stochastic first order optimization algorithms,, which attain sublinear convergence to stationary solu- tion. To the best of our knowledge, these are the first results on statistical and computational guarantees of imitation learning with reward/policy function ap- proximation. Numerical experiments are provided to support our analysis.
INTRODUCTION
As various robots (Tail et al., 2018), self-driving cars (Kuefler et al., 2017), unmanned aerial ve- hicles (Pfeiffer et al., 2018) and other intelligent agents are applied to complex and unstructured environments, programming their behaviors/policy has become increasingly challenging. These in- telligent agents need to accommodate huge number of tasks with unique environmental demands. To address these challenges, many reinforcement learning (RL) methods have been proposed for learning sequential decision-making policies (Sutton et al., 1998; Kaelbling et al., 1996; Mnih al., 2015). These RL methods, however, heavily rely on human expert domain knowledge to design proper reward functions. For complex tasks, which are often difficult to describe formally, these RL methods become impractical.
The Imitation Learning (IL, Argall al. (2009); Abbeel & Ng (2004)) approach is a powerful and practical alternative to RL. Rather than having a human expert handcrafting a reward function for learning the desired policy, the imitation learning approach only requires the human expert to demonstrate the desired policy, and then the intelligent agent (a.k.a. learner) learns to match the demonstration. Most existing imitation learning methods fall in the following two categories:
Behavioral Cloning (BC, Pomerleau (1991)). BC treats the IL problem as supervised learning. Specifically, it learns policy by fitting a regression model over expert demonstrations, which di- rectly maps states to actions. Unfortunately, BC has fundamental drawback. Recall that in super- vised learning, the distribution of the training data is decoupled from the learned model, whereas in imitation learning, the agent's policy affects what state is queried next. The mismatch between training and testing distributions, also known as covariate shift (Ross & Bagnell, 2010; Ross et al., 2011), l), yields significant compounding errors. Therefore, BC often suffers from poor generalization.
Inverse Reinforcement Learning (IRL, Russell (1998): Ng et al. (2000): Finn et al. (2016); Levine & Koltun (2012)). IRL. treats the II. problem as bi-level optimization. Specifically, it finds reward

---

Published as a conference paper at ICLR 2020
function, under which the expert policy is uniquely optimal. Though IRL does not have the error compounding issue, its computation is very inefficient. Many existing IRL methods need to solve sequence of computationally expensive reinforcement learning problems, due to their bi-level optimization nature. Therefore, they often fail to scale to large and high dimensional environments.
More recently, Ho & Ermon (2016) propose Generative Adversarial Imitation Learning (GAIL) method, which obtains significant performance gains over existing IL methods in imitating complex expert policies in large and high-dimensional environments. GAIL generalizes IRL by formulating the IL problem as minimax optimization, which can be solved by alternating gradient-type algo- rithms in more scalable and efficient manner.
Specifically, we consider an infinite horizon Markov Decision Process (MDP), where S denotes the state space, A denotes the action space, P denotes the Markov transition kernel, r" denotes the reward function, and Po denotes the distribution of the initial state. We assume that the Markov transition kernel P fixed and there is an unknown expert policy n²: + P(A), where P(A) denotes the set of distributions over the action space. As can be seen, {8r - essentially forms a Markov chain with the transition kernel induced by ग as p= (s) = E.EA Ta s)- a). Given n demonstration trajectories from x² denoted by {s az (T) where i L,... n, so po- a, 'T" (-) 8t), and 81+1 ~ P( St, 0e), GAIL aims to learn nt by solving the following minimax optimization problem.
min, max, a) E,,r(ss a)l,
(1)
where [x(r(s,)) a)] = lim E DiD rstt, [=] denotes the average reward under the policy
when the reward function is and E., [r(s, a) क. Ex (0) aa denotes the
empirical average reward over the demonstration trajectories. As shown in (I), GAIL aims to find a policy, which attains an average reward similar to that of the expert policy with respect to any reward belonging to the function class R.
For large and high-dimensional imitation learning problems, we often encounter infinitely many states. To ease computation, we need to consider function approximations. Specifically, suppose that for every E S and E A, there are feature vectors v. E Rd and vaa E Rd associated with a and 8, respectively. Then we can approximate the policy and reward as
. (-1s) = 7m (1ba) and r(s,a) = Fo va).
where स and 7 belong to certain function classes (e.g. reproducing kernel Hilbert space or deep neural networks, Ormoneit & Sen (2002); LeCun et al. (2015)) associated with parameters w and 0, respectively. Accordingly, we can optimize (I) with respect to the parameters w and 0 by scalable alternating gradient-type algorithms.
Although GAIL has achieved significant empirical progresses, its theoretical properties still largely unknown. There are three major difficulties when analyzing GAIL: 1). There exists tempo- ral dependency in the demonstration trajectories/data due their sequential nature (Howard, 1960; Puterman, 2014; Abounadi et al., 2001); 2). GAIL is formulated as a minimax optimization prob- lem. Most of existing learning theories, however, focus on empirical risk minimization problems, and therefore are not readily applicable (Vapnik, 2013; Mohri et al., 2018; Anthony & Bartlett, 2009); 3). The minimax optimization problem in (1) does not have a convex-concave structure, and therefore existing theories in convex optimization literature cannot be applied for analyzing the al- ternating stochastic gradient-type algorithms (Willem, 1997; Ben- & Nemirovski, 1998; Murray & Overton, 1980; Chambolle & Pock, 2011; Chen et al., 2014). Some recent results suggest to use stage-wise stochastic gradient-type algorithms (Rafique et al., 2018: Dai et al., 2017). More specif- ically, at every iteration, they need to solve the inner maximization problem up to high precision, and then apply stochastic gradient update to the outer minimization problem. Such algorithms, how- ever, rarely used by practitioners, as they are inefficient in practice (due the computationally intensive inner maximization).
To bridge such gap between practice and theory, establish the generalization properties of GAIL and the convergence properties of the alternating mini-batch stochastic gradient algorithm for solving (1). Specifically, our contributions can be summarized as follows:
2

---

Published as a conference paper at ICLR 2020
We formally define the generalization of GAIL under the "so-called" R-reward distance, and then show that the generalization of GAIL can be guaranteed under reward distance as long as the class of the reward functions is properly controlled;
We provide sufficient conditions, under which an alternating mini-batch stochastic gradient algo- rithm efficiently solve the minimax optimization in (1), and attains sublinear convergence stationary solution.
To the best of our knowledge, these the first results statistical and computational theories of imitation learning with reward/policy function approximations.
Our work is related to Syed et al. (2008); Cai et al. (2019). Syed et al. (2008) study the generalization and computational properties of apprenticeship learning. Since they assume that the state space of the underlying Markov decision process is finite, they do not consider any reward/policy function approximations; Cai et al. (2019) study the computational properties of imitation learning under a simple control setting. Their assumption on linear policy and quadratic reward is very restrictive, and does not hold for many real applications.
Notation. Given a vector x = (#1,-..,,a.)) E TRd, we define ||>:|1 = ΣØ= az. Given a function
f: IR' R, we denote its fo norm || max, [f())
2 GENERALIZATION GAIL
To analyze the generalization properties of GAIL, we first assume that we can access an infinite num- ber of the expert's demonstration trajectories (underlying population), and that the reward function is chosen optimally within some large class of functions. This allows us to remove the maximum operation from (1), which leads to an interpretation of how and in what sense the resulting policy is close to the true expert policy. Before proceed, we first introduce some preliminaries.
Definition (Stationary Distribution). Note that any policy æ induces a Markov chain on S x A. The transition kernel is given by
(x a' 8, a)
(d'11')) ) P(s' [s,a), ((s,)), (s', E A.
When such Markov chain is aperiodic and recurrent, we denote its stationary distribution as
Note that policy æ is uniquely determined by its stationary distribution Pa in the sense that {a s) (s a)/ Enc, (s a).
Then write the expected average reward of r(s, a) under the policy x as (r,, a)] tim B f E r(st, a.) m| Bp [r(s, = P r(s,a).
We further define the R-distance between two policies and n' as follows.
Definition 2. Let R denote a class of symmetric reward functions from S x to R. i.e., ifr E R, then -r E R. Given policy nt' and n, the R-distance for GAIL is defined
dæ(#, n') CouPreR(EErr(G a) E.rr(s,)),
The R-distance over policies for Markov decision processes is essentially Integral Probability Metric (IPM) over stationary distributions (Müller, 1997). For different choices of R, we have vari- ous R-distances. For example, we can choose R the class of all 1-Lipschitz continuous functions, which yields that dæ (æ, x') is the Wasserstein distance between Pr and px (Vallender, 1974). For computational convenience, GAIL and its variants usually choose as a class of functions from some reproducing kernel Hilbert space, a class of neural network functions.
Definition 3. Given n demonstration trajectories from time 0 7' obtained by an expert policy (5) (-)
n" denoted by (x))) ag Tt= where i = 1,..., policy रे learned by GAIL generalizes under the R-distance dx(())) with generalization error e, if with high probability, we have
(dR(= 7) (x" 7)] S 6,
where dR (TT 7) is the empirical R-distance between `t and âे defined as
dR (m #) SuPreR [ a) Rer(s, with Bxglr(s, + El Ei-llr(s (r
(())--
3

---

Published as a conference paper at ICLR 2020
The generalization of GAIL implies that the R-distance between the expert policy x¹ and the learned policy A is close to the empirical R-distance between them. Our analysis aims to prove the former distance to be small, whereas the latter one is what attempts to minimize in practice.
We then introduce the assumptions on the underlying Markov decision process and expert policy. Assumption 1. Under the expert policy x², (3t. 4:) forms a stationary and exponentially 3- mixing Markov chain, i.e.,
B(k) sup, Enegy Au [P(A|B) (P(A) S 80 exp(-Bik-))
where Bo 31, are positive constants, and of is the o-algebra generated by (st, a.)z for is j.
Moreover, for every S and A, there feature vectors th, Rds and tha Rdd associated with a and s, respectively, and vha and tha are uniformly bounded, where
|| ll2 S and I|vall2 1, vs E and Va E A.
Assumption 1 requires the underlying MDP to be ergodic (Levin & Peres, 2017), which is a com- monly studied assumption in exiting reinforcement learning literature on maximizing the expected average reward (Strehl & Littman, 2005; Li et al., 201 I; Brafman & Tennenholtz, 2002; Kearns & Singh, 2002). The feature vectors associated with a and allow us to apply function approxima- tions to parameterize the reward and policy functions. Accordingly, r(s, a) = F(t,, va), which is assumed to be bounded.
write the reward function as
Assumption 2. The reward function class is uniformly bounded, i.c., ||r S B, for any r R.
Now we proceed with our main result on generalization properties of GAIL. We use N' (R, c, llae) to denote the covering number of the function class R under the &oo distance || ll
Theorem (Main Result). Suppose Assumptions 1-2 hold, and the policy Iearned by GAIL satisfies
dR ( 7) inf (
where the infimum is taken over all possible learned policies. Then with probability at least 1 - we have
over the joint distribution of ((a)") .8
(6)
10) Ji=1
Br
log(1/0) V 11o0) + Bry nT/C
( () - inf d 0
VnTTC log.N (R, (
+ E,
where Ç = (BT log
T 5 )
Theorem implies that the policy मे learned by GAIL generalizes as long as the complexity of the function class R is well controlled. To the best of our knowledge, this is the first result on the generalization of imitation learning with function approximations. As the proof of Theorem is involved, we only present a sketch due to space limit. More details are provided in Appendix A.
Proof Sketch. Our analysis relies on characterizing the concentration property of the empirical av- erage reward under the expert policy. For notational simplicity. we define
F., E
r(s (4) (.)).
The key challenge comes from the fact that (s) a,")sss are dependent. To handle such depen- dency, we adopt the independent block technique from Yu (1994). Specifically, we partition every trajectory into disjoint blocks (where the block size is the order O(log(TT) + log((18)) and construct two separable trajectories: One contains all blocks with odd indices (denoted by Boad), and the other contains all those with even indices (denoted by Beven). We define
E ExE r(s,
2 EE E(s (alfiaaateee BB r(s (0)))
and analogously for d2 with (s) a E B Then we have
(8)
P(supreR 2 =) P(supreR $1 suPreR d7 2 2)) P(suupre di 2 + P(supreR 02 2 E).
4

---

Published as a conference paper at ICLR 2020
We consider block-wise independent counterpart of 01 denoted by Ø1, where each block is sampled independently from the same Markov chain as Φ1 i.e., 01 has independent blocks of samples from same exponentially 8-mixing Markov chain Accordingly, we denote Φi as
2 #7 Ei= E(s5") (al"",aa)))) Je.o. r(s) )
1 = E. r(s,
where Boda denotes i..dd. blocks of samples. Now we bound the difference between Φ1 and お by
P(sup Φ1 - -[[sup ø1] 2
E[ssp FR
ø1)) S (P(sup #1 - E[sup क1 2 E B|sup Φil) rER
ER
rER
PER CCBT/(lo((T) log(1/6))
PER
where C' is a constant, and 3 the mixing coefficient, and P(supreR क EjsupreR क. 2 E[supreR éi]) be bounded using the empirical process technique for independent random variables. The details of the above inequality can be found in Corollary in Appendix A.I, where the proof technique is adapted from Lemma in Mohri & Rostamizadeh (2009). Let Ø be defined analogously as Φ1. With similar argument further applied Φ2 and Φ2, we obtain
P((sup Φ 2 E) v 2P(uup क FE
Elsup ক 2 & E[sup
Φ1)) + 2C + ())))/))4//, rER
rER
FR
The rest of our analysis follows the PAC-learning framework using Rademacher complexity and omitted (Mohri et al., 2018). We complete the proof sketch.
Example 1: Reproducing Kernel Reward Function. One popular option to parameterize the
reward by functions is the reproducing kernel Hilbert space (RKHS, Kim & Park (2018); Li et al. (2018)). There have been several implementations of RKHS, and we consider the feature mapping approach. Specifically, we consider g IR& Rd + 129, and the reward can be written as
r(s, a) Fo (v... va) = 0 g(t,,, wha,,
where 0 R2. We require g to Lipschitz continuous with respect to (va. 4.)).
Assumption 3. The feature mapping g satisfies g(0, 0) 0, and there exists a constant Pg such that for any th. Vaa V. and V', we have
(la(v.. - g(b., vo1l Po 11 - vi112 + 1| v.
Assumption mild and satisfied by popular feature mappings, e.g., random Fourier feature map- ping" (Rahimi & Recht, 2008; Bach, 2017). The next corollary presents the generalization bound of GAIL using feature mapping.
Corollary 1. Suppose ||0|2 < Bg- For large enough and T, with probability at least â over the joint distribution of {(a - 1-11
1 we have
d 7) - inf dx (T= xT) S o
Pg VnITs
log(1/8)
V V log (eg Bo BoynT/S) + Pg Bay
+
nT/C
Corollary indicates that with respect to a class of properly normalized reproducing kernel reward functions, GAIL generalizes in terms of the R-distance.
Example 2: Neural Network Reward Function. Another popular option to parameterize the reward function is to neural networks. Specifically, let (v)) = [max(u,, U1 O},..., max(raa 0)] denote the ReLU activation for v E Rd. We consider D-layer feedforward neural network with ReLU activation follows.
r(s, a) = Fw( (ba)
(W (I]T))
where W = (W^ WA E Idde- xd, = I,... D - 1,, WD E Rd and do d + ds. The next corollary presents the generalization bound of GAIL using neural networks.
'More precisely, Assumption actually holds with overwhelming prohability over the distribution of the random mapping.
5

---

Published as a conference paper at ICLR 2020
Corollary 2. Suppose ||Will2 1, where i = 1, D. For large enough and T, with probability at least 1 - over the joint distribution of {(aE) ,t 1io Fiz we have
(1)
dx("", #) inf dx("', .am".,))) of ( d' (DvdiT/s) +V
log(1/8) nTT/S
+ E.
Corollary 2 indicates that with respect to class of properly normalized neural network reward functions, GAIL generalizes in terms the R-distance.
Remark (The Tradcoff between Generalization and Representation of GAIL). As can seen from Definition 2, the R-distances are essentially differentiating two policies. For the Wasserstein- type distance, i... R contains all 1-Lipschitz continuous functions, if di (T, x') ) is small, it is safe to conclude that two policies and n' are nearly the same almost every everywhere. However, when choose R. to be the reproducing kernel Hilbert space or the class of neural networks with relatively small complexity, dR (T,, n') can be small even if and x' are not very close. Therefore, need to choose a sufficiently diverse class of reward functions to ensure that we recover the expert policy.
As Theorem suggests, however, that need to control the complexity of the function class R to guarantee the generalization. This implies that when parameterizing the reward function, we need carefully choose the function class to attain the optimal tradeoff between generalization and representation of GAIL.
3 COMPUTATION OF GAIL
To investigate the computational properties of GAIL, we parameterize the reward by functions be- longing to some reproducing kernel Hilbert space. The implementation is based on feature mapping, as mentioned in the previous section. The policy can be parameterized by functions belonging to some reproducing kernel Hilbert space or some class of deep neural networks with parameter w. Specifically, we denote Taass) Fw(+)), where (v+))) is the parametrized policy mapping from Ids to a simplex in R with |A| = For computational convenience, we consider solving a slightly modified minimax optimization problem:
min,, max Sk B [s) Fo v2a) (H( 11012.
where Forss, a) 0 g( ).). H (m.) some regularizer for the policy (e.g., causal entropy regu- larizer, Ho & Ermon (2016)), and X > 0 and J are tuning parameters. Compared with (1), the additional regularizers in (2) can improve the optimization landscape, and help mitigate computa- tional instability in practice.
We apply the alternating mini-batch stochastic gradient algorithm (2). Specifically, denote the objective function in (2) as F(w, () for notational simplicity. At the (t + 1)-th iteration, we take
((++1) 1I, (0(()
Ne To
EEEMSO (efs(w(t) 0(0)) and
(3)
w (++1) = (t)
The Tus
EjEMS (w)() g((+11),
(4)
where he and Th are learning rates, the projection (v) = (1lu|12 S k) v + 1(10/// > x) . K
v/ [|lll Vfy's 's and Vfy's are independent stochastic approximations of F (Sutton et al., 2000),
and M M are mini- batches with sizes gu and q respectively. Before we proceed with the convergence analysis, we impose the follow assumptions on the problem.
Assumption 4. There are two positive constants M,, and Mo such that for any w and ||0]|2 s k.
Unbiased EV (w = = (w. 0) = (WW, 0),
Bounded E fy F(w, 0)1 M. and Ve VeF(w, 0) < Me.
Assumption 4 requires the stochastic gradient to be unbiased with bounded variance, which is common assumption existing optimization literature (Nemirovski et al., 2009; Ghadimi & Lan, 2013; Duchi et al., 2011; 1; Bottou, 2010).

---

Published as a conference paper at ICLR 2020
Assumption 5. (i) For any w, there exists some constant and (0, 1) such that
[1(P= Pä llv S xv',
where Px. (s', a' s,a) = "a(d's") s, a) is the transition kernel induced by Tw. Po the initial distribution of (so, an), and P=_ is the stationary distribution induced by Tu-
(ii) There exist constants S Bur Lp LQ such that for any w, w', we have
W log(# (als)) V log( (als))lla S S* ||W 2l12
V log (a|ss)) S Bwr
llp=, P# 1Iv S Lp|w w w1122
11Q QF af bl I LQ ||W w'll2
where (s, Er= 13 [(st, at) En_ [7] = 0,00 a, Tw] is the action-valuc function.
(iii) There exist constants Bh and Sh > such that for any w, w', we have
H S BH, and
S Su || - wl112
Note that (i) of Assumption 5 requires the Markov Chain to be geometrically mixing. (ii) and (iii) state some commonly used regularity conditions for policies (Sutton et al., 2000; Pirotta al., 2015).
We then define L-staaionary points of F. Specifically, we say that (w", 0*) is stationary point of F, and only if, for any fixed a > O,
Flw"", ,0) = 0 and 0" - (1, + +aVaF(w" 0*)) -.
The L-stationarity is generalization of the stationary point for unconstrained optimization, and is a necessary condition for optimality. Accordingly, we take a = and measure sub-stationarity of the algorithm at the iteration N by
JN minigigN Elje() (T(( VeF(W ) F(u ((())))11
We then state the global convergence of the alternating mini-bated stochastic gradient algorithm. Theorem 2. Suppose Assumptions 1-5 hold. We choose step sizes 71, The satisfying
n S min {
In
1
7L +1
(SL + +2) 2L f n7 S min 150μ²
150S
100 SS)
(1) + B L. and S. 2 //(11 v). Given any O, we choose batch sizes do ((1/e) and
and meanwhile nw/10 S 13/0ww + 5), where I. = 2V2(S= + L,
Iu = ((1/c). Then we need at most
N = 1/(O + 2v + un² + 2ABh)e
iterations such that JN See where Co depends on the initialization, and depends on nh and me-
Here Ô hides linear or quardic dependence on some constants in Assumptions 1-5. Theorem 2 shows that though the minimax optimization problem in (2) does not have convex-concave structure, the alternating mini-batch stochastic gradient algorithm still guarantees to converge to stationary point. We are not aware of any similar results for GAIL in existing literature.
Proof Sketch. We prove the convergence by showing
(5) where is a constant and Ne/2 the accumulation of noise in stochastic approximations of F.. Then we straightforwardly have Njv S C Ne/2. Dividing both sizes by N, can derive the desired result. The main difficulty of showing (5) comes from the fact that the outer minimization problem is nonconvex and we cannot solve the inner maximization problem exactly. To overcome this difficulty, we construct a monotonically decreasing potential function:
B (0()) + VoF(w!(,000) (()) 1 E o((t))) 5 Ce
c(t) (f((w(() ((()) + s(11 2n, Lw)/ Bl) w 11
+ (21m/2110 pm//4 /44 + 3m 2 /2) E. 0((+ )(+) 2 pm /8. Bl|o(*) 0(t 11))
for a constant to be chosen later. Denote < and <l'') as the i.i.d. noise the stochastic gradients. The following lemma characterizes the decrement of the potential function each iteration.

---

Published as a conference paper at ICLR 2020
Lemma 1. With the step sizes no and n chosen in Theorem 2, we have
g((+1) - S b1 1 A= - (( 1| k3 - 11
- kaBBl((++1) - 000011 -1, - 1
+ s (B| 11 + E (5( 113)
where v a constant depending on F. no. and nu- Moreover, we have constants 1 k2, K3, h1, Ass
0 for s = (n2 (58L,, + +)).
Let m/n kk,, his) and Φ = max (1, 1/ng. 1/n We obtain
N -= E ((t)
11, + (oF(w!)) )()))) + V F(w(t) 0((
N [[ g(t) [| with 11 kō(g()) E(N) KoN B 11
where (i) follows from plugging in the update (3) as well as the contraction property of projection,
and (ii) follows from Lemma 1. Choosing qo 4kóvMa/e and qu = 4kovMM/c c, we obtain
Σn E (0(+) + VoF(w() (())) E V F(wlo) 1 - kō(E()) E(N) + Ne 2
We have g(N) 2 (F(((()) ,(N)) by the construction of g(N), It is easy to verify that F is lower bounded (Lemma 10 in Appendix B). Eventually, we complete the proof by substituting the lower bound and choosing N = (2((2(()) + 4/22pp px² + 22BB))
4 EXPERIMENT
To verify our theory in Section 3, we conduct experiments in three reinforcement learning tasks: Acrobot, MountainCar, and Hopper. For each task, we first train an expert policy using the proximal policy optimization (PPO) algorithm in (Schulman et al., 2017) for 500 iterations, and then use the expert policy to generate the demonstration data. The demonstration data for every task contains 500 trajectories, each of which is series of state action pairs throughout one episode in the environment. When training GAIL, we randomly select mini-batch of trajectories, which contain at least 8192 state action pairs. We use PPO to update the policy parameters. This avoids the instability of the policy gradient algorithm, and improves the reproducibility of our experiments.
Average reward (performance)
Acrobot-v1 (1)- 30 1. Mh 1e 3)
Hopper-v2 (n. = be 1. le 3)
MountainCar-vo (v 5e 4, le 3)
-100
1000
150
-200
800
160
600
-300
NN reward
400
multi-step
-100
200
Inner one-step
190
500
200
500
1000 1500 2500
15/0) 2001 2500 3000
2000)
3000
iteration
Figure 1: Performance of GAIL on three different tasks. The plotted curves are averaged over 5 independent runs with the vertical axis being the average reward and horizontal axis being the number iterations.
We use the same neural network architecture for all the environments. For policy, we use fully connected neural network with two hidden layers of 128 neurons in each layer and tanh activation. For reward, we use a fully connected ReLU neural network with two hidden layers of 1024 and 512 neurons, respectively. To implement the kernel reward, we fix the first two layers of the neural network after random initialization and only update the third layer, i.e., the first two layers mimic the random feature mapping. We choose = and μ 0.3. When updating the neural network reward, we use weight normalization in each layer (Salimans & Kingma, 2016).
When updating the kernel reward at each iteration, we choose to take the stochastic gradient ascent step for either once (i.e., alternating update in Section 3) or 10 times. When updating the neural network reward at each iteration, we choose take the stochastic gradient ascent step for only once. We tune step size parameters for updating the policy and reward, and summarize the numerical results of the step sizes attaining the maximal average episode reward in Figure 1.
8

---

Published as a conference paper at ICLR 2020
As be seen, using multiple stochastic gradient ascent steps for updating the reward at each iteration yields similar performance as that of one step. We present the convergence analysis of using multiple stochastic gradient ascent steps for updating the reward in Appendix C. Moreover, we observe that parameterizing the reward by neural networks slightly outperform that of the kernel reward. However, its training process tends to be unstable and takes longer time to converge.
DISCUSSIONS
Our proposed theories of GAIL are closely related Generative Adversarial Networks (Goodfellow et al., 2014; Arjovsky et al., 2017): (1) The generalization of GANs is defined based on the integral probabilistic metric (IPM) between the synthetic distribution obtained by the generator network and the distribution of the real data (Arora et al., 2017). As the real data in GANs are considered as independent realizations of the underlying distribution, the generalization of GANs can be analyzed using commonly used empirical process techniques for i.i.d. random variables. GAIL, however, involves dependent demonstration data from experts, and therefore the analysis is more involved. (2) Our computational theory of GAIL can be applied to MMD- -ANN and its variants, where the IPM induced by some reproducing kernel Hilbert space (Li et al., 2017; Binkowski et al., 2018; Arbel et al., 2018). The alternating mini-batch stochastic gradient algorithm attains a similar sublinear rate of convergence to a stationary solution.
Moreover, our computational theory of GAIL, only considers the policy gradient update when learn- ing the policy (Sutton et al., 2000). Extending to other types of updates such as natural policy gradient (Kakade, 2002), proximal policy gradient (Schulman al., 2017) and trust region policy optimization (Schulman et al., 2015) is a challenging, but important future direction.
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 1. ACM, 2004.
Jinane Abounadi, D Bertsekas, and Vivek Š Borkar. Learning algorithms for markov decision pro- cesses with average cost. SIAM Journal on Control and Optimization, 40(3):681-698, 2001.
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cam- bridge University Press, 2009.
Michael Arbel, Dougal Sutherland, Mikolaj Binkkwski, and Arthur Gretton. On gradient regular- izers for mmd gans. In Advances in Neural Information Processing Systems, pp. 6700-6710, 2018.
Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning, A survey of robot learning from demonstration. Robotics and autonomous systems, 57(5):469 483, 2009.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214 114,222,,20 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In Proceedings of the 34th International Conference on Machine Learming- Searning-Volume Volume 70, pp. 224 232. JMLR. org. 2017.
Francis Bach. On the equivalence between kernel quadrature rules and random feature expansions.
The Journal of Machine Learning Research, (8(1):714-755) 117114157,,017 2017.
Aharon Ben-Tal and Arkadi Nemirovski. Robust convex optimization. Mathematics of operations research, 23(4):769-805 1998.
Mikolaj Binkowski, Dougal J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying mmd gans. arXiv preprint arXiv: 1801 01. 4010 2018.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of C0MPSTAT'2100, pp. 177-186. Springer, 2010.
9

---

Published as a conference paper at ICLR 2020
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-22 - 2002.
Qi Cai, Mingyi Hong, Yongxin Chen, and Zhaoran Wang. On the global convergence of imitation learning: A case for linear quadratic regulator. arXiv preprint arXi::1901.03672 2019.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-145,, 2011.
Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Optimal primal-dual methods for class of saddle point problems. SIAM Journal on Optimization, (((4):177--1844 2014.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sheed: Convergent reinforcement learning with nonlinear function approximation. arXiv preprint arXiv:1712.10285, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul))2121-2155) 2011.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on Machine Learning, pp. 49-58, 2016.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-233) -2368, 2013.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, pp. 4565-4573, 2016.
Ronald A Howard. Dynamic programming and markov processes. 1960.
Leslie Pack Kaelbling, Michael L. Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pp. 1531-1538, 2002.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2-3):209-2 2002.
Kee-Eung Kim and Hyun Soo Park. Imitation learning via kernel mean embedding. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Alex Kuefler, Jeremy Morton, Tim Wheeler, and Mykel Kochenderfer. Imitating driver behavior with generative adversarial networks. In 2017 IEEE Intelligent Vehicles Symposium (IV), pp- 204-211. IEEE, 2017.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436, 2015.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
Sergey Levine and Vladlen Koltun. Continuous inverse optimal control with locally optimal exam- ples. arXiv preprint arXiv:1206. 4617, 2012.
Chun-Liang Li, Wei-Cheng Chang. Yu Cheng, Yiming Yang, and Barnabás Póezos. Mmd gan: Towards deeper understanding of moment matching network. In Advances in Neural Information Processing Systems, pp. 2203-2213, 2017.
Lihong Li. Michael Littman, Thomas J Walsh, and Alexander L Strehl. Knows what it knows: a framework for self-aware learning. Machine learning, 82(3):399 443, 2011.
10

---

Published as a conference paper at ICLR 2020
Shuang Li, Shuai Xiao, Shixiang Zhu, Nan Du Yao Xie, and Le Song. Learning temporal point processes via reinforcement learning. In Advances in Neural Information Processing Systems, pp. 10781-10791, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-iid processes. In Advances in Neural Information Processing Systems, pp. 1097-1104, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. MIT press, 2018.
Foundations of machine learning-
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429-44) 1997.
Walter Murray and Michael L. Overton. projected lagrangian algorithm for nonlinear minimax optimization. SIAM Journal on Scientific and Statistical Computing, 133):355-770, 1980.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic
approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Andrew Y Ng. Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In Ieml, volume 1, pp. 2, 2000.
Dirk Ormoneit and Šaunak Sen. Kernel-based reinforcement learning. Machine learning, 49(2-3): 161-178, 2002.
Mark Pfeiffer, Samarth Shukla, Matteo Turchetta, Cesar Cadena, Andreas Krause, Roland Siegwart, and Juan Nieto. Reinforced imitation: Sample efficient deep reinforcement learning for mapless navigation by leveraging prior demonstrations. IEEE Robotics and Automation Letters, 3(4): 4423 4430-4430, 2018
Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Policy gradient in lipschitz markov decision processes. Machine Learning, 100(2-3):255-283. 2015.
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neu- ral Computation, 3(1):88-99) 97, 1991.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprini arXiv:1810.02066. 2018.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-668, 2010.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc-
tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference on artificial intelligence and statistics, pp. 627-635, 2011.
Stuart Russell, Learning agents for uncertain environments. In COLT, volume 98, pp- 101-103, 1998.
Tim Salimans and Durk P Kingma. Weight normalization: simple reparameterization accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, pp. 901-909, 2016.
11

---

Published as a conference paper at ICLR 2020
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Alexander L Strehl and Michael L. Littman. theoretical analysis of model-based interval estima- tion. In Proceedings of the 22nd international conference on Machine learning, pp. 856-863. ACM, 2005.
Richard S Sutton, Andrew G Barto, et al. Introduction to reinforcement learning, volume 135, MIT press Cambridge, 1998.
Richard Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- tion processing systems. pp. 1057-1063, 2000.
Umar Syed, Michael Bowling, and Robert Schapire. Apprenticeship learning using linear pro- gramming- In Proceedings of the 25th international conference on Machine learning, pp. 1032- 1039. ACM, 2008.
Lei Tail, Jingwei Zhang, Ming Liu, and Wolfram Burgard. Socially compliant navigation through raw depth inputs with generative adversarial imitation learning. In 2018 IEEE International Con- ference on Robotics and Automation (ICRA), pp. 1111-1117. IEEF, 2018.
SS Vallender. Calculation of the wasserstein distance between probability distributions on the line. Theory of Probability Its Applications, 18(4):784-786, 1974.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Michel Willem. Minimax theorems, volume 24. Springer Science & Business Media, 1997.
Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pp. 94-116, 16, 1994.
12

---

Published as a conference paper at ICLR 2020
A PROOFS IN SECTION 2
A. PROOF OF THEOREM 1
We first consider For notational simplicity, denote It (5e, az) and (0x)7=) Then the generalization gap is bounded by
d ;) inf dR (T", x) = dxe [T" , - dx( R)
dn (Ti 8) - inf dR 7 
dR ( π²) inf d ( (T)
2
sup Ex.r T nR
Σ
r(st, te.
t=0
T-1 ((t, = suPrER (()
T-1 Σ r(x,). utilize 1=
Denote ((T) = supreR (()
- t=0
the independent block technique first proposed in Yu (1994) to show the concentration of Φ(r)). Specifically, we partition J into 2m blocks of equal size b. We denote two alternating sequences as
Tu = (X1, X2, ... (m)
X; = (1(21-1)6+1 (211119646)
71 (x x!)" )()))
X₃ (220041. (220011)"""22001)))
We now define new sequence
7. (X1, X2, .mm).
(6)
where X's are i.d blocks of size b. and each block X, follows the same distribution as X,.
We define X + R as rX( Ek r(xx). Note that 7 is essentially the average reward on a block. Accordingly, we denote R₂ as the set of rs 's induced by E R.
Before we proceed, we need to introduce lemma which characterizes the relationship between the expectations of bounded measurable function with respect to To and To-
Lemma 2. (Yu, 1994) Suppose h is a measurable function bounded by M defined over the blocks X3, then the following inequality holds:
[Er, (h) - Er, (h)) S (m - 1)b)
where E., denotes the expectation with repect To. and EE, denotes the expectation with respect to To-
Corollary 3. Applying Lemma 2, we have
(,(((7) c) 2T. (T(7)) E, (
E7, ((T))) 2(m 1))(())
Proof. Consider (T((TT)= w) have
T
P. (+( c) (sup E,, r(x)
1
Σ
r(x))
FER
T
1=0
suPPER E r(x)
2 Σ
r(x))
suPreR Ex.((z) - - Σ r(x))
P
2
2
(8)
(T(((T))+ + +(n) > 2c)
( > +P, (2(T)) x)
(
2P (T(T)) E, (()o) E,, (F)))),
13

---

Published as a conference paper at ICLR 2020
where the first inequality (8) follows from the convexity of supremum.
Applying Lemma 2 and setting / (( E,, (., > c (f00)] we obtain
P (T())) ( > E7, (T))
Σ Pr. (( - E; (T)) > E - B, ( (o)))) + 2(m 1)3(b).
Now since To consists of independent blocks, we can apply McDiarmid's inequality to rs by viewing X,'s 's as i.d samples. We rewrite ) as
( sup Ts (X),) rERR,
(X,)
m
Given samples X1, X X and X1, X,, Xmm have
① X X,," X o (X1, X, ... Xm S 2
2B,
ro(
Then by McDiarmid's incquality, we have
-m(c E7, ((F0)))22)
Pr. (D( EF, (P()) c- Evo [(Fo))) cxp
(9)
2B
Now combining (7) and (9), obtain
-mi( Ei, (T)0)))))
Pr (+)( > c) - 2exp
+ 2(m 1)3(b).
(10)
2B?
By the argument of symmetrization, we have
E7, [ 2E
Σ Eor r.ERa
sup
(11)
where o, 's are i.idd Rademacher random variables. Now we relate the Rademacher complexity (11) to its counterpart taking i.i.d samples. Specifically, we denote 2/6 the j-th point of the t-th block.
Denote 7i as the collection of the j-th sample from each independent block X; for i 1, 1,..., Plugging in the definition rb, we have
2T
sup m
1
(1)
2FF
sup (1) m PER
FER
j=1
t=1
2
Eng
sup m rER
1
(1))
2
E 10
sup m YER
b
1=1
m m
ar)(a(())
2E
sup
(12)
YER
Setting the right-hand side of (10) to be and substituting (12), we obtain, with probability at least 1 8 for all r R,
log 4
((7) S 2E,g.
sup m rER
Σ
(1)() + +2B,
3
(13)
2m
where 8' = 1(mm 1)).
14

---

Published as a conference paper at ICLR 2020
Then denote
Rademacher complexity for Xy's: nn = Ragia
Σ
car(T]] (0)
sup
m. rER
Empirical Rademacher complexity for Xy's: Riy = EE
sup
FER
1
Empirical Rademacher complexity for Xy's: Rm = R
car(z!
sup
m
rER
Applying Lemma 2 to the indicator function 11 Rm c), obtain
P(D Rm > c) - P Rog
> c) (m 10,011))2222 1) $ P( Rzy > + (m 1))((b.
It is straightforward to verify that given (1) Rademacher complexity satisfies
(6)
(m) and x .... 11 (8)
(1)
(m) the
,,..,
....,
2B,
R
Rey <
Then by applying McDiarmid's Inequality again, we obtain
-mc?
P R Rm c)
S
exp
+ (m 1)3(6).
2
Thus with probability at least 2. we have
nD Pim < 2B,
log 8/2 112-(m-11) 1)3(0]
log
S 2B,
(14)
2m
2m
Combining (13) and (14), we have with probability 1 1-6, 8,
log 37 2m
(T) S 2
6B.,
(15)
We apply the Dudley's entropy integral to bound Pm.. Specifically, we have
/ VlogN II 1lx Jde
Rt
<
m
Ja
4a
12B,
/oog.NRR,,,, 1loo).
(16)
mm
Vm
It suffices to pick 1-8. 8,
By combining (6), (15), and (16), we have with probability at least
7m
16 + m
48B, vm
log 7 2m
dx(n", ;,) - inf - (,(
Nog, 1/vm, (1,b)) + 12B,
+
e,
where 8' = - 44mm - (b) and 2bm = T. Substituting m -T/2b, we have
32h +
48B,
log + c.
d inf ( <
(R (1x)) 12B,,
T 2T/26
T/b
(17)
Now we instantiate choice of and m for expotentially 9-mixing sequences, where the mixing coefficient B(b) E So exp(p3pppp 3,) for constants Bo, B1, 0. We set 8 > 5 8-4(m 41mm-1)300 3-
15

---

Published as a conference paper at ICLR 2020
By simple calculation, it enough to choose b (1ok(42:T/0) ) Substituting such a b into (17).
We have with probability at least 6:
/ L.1 1100) Br VT/C log.
B,
log(1/8)
d inf dR (nt ( ()) 50
+
T/5
(18)
where Ç (= (31 log PnT
When 1, concatenate trajectories to form sequence of length nT, and such sequence is still exponentially 8-mixing. Applying the same technique, we partition the whole sequence into 2nm blocks of equal size b. Then with probability at least 6, have
Jog. v V 5 11x0) BIV VnT/c
Br
log(1/6) nT/5
dR(T", R) inf inf ( (x)
A.2 PROOF OF COROLLARY
The reward function can be bounded by
Ir(s, a)l 10 g(Ve, va)l & 110121l9 va)ll2 I V2Bapm
where the first inequality comes from Cauchy-Schwarte inequality. To compute the covering number, we exploit the Lipschitz continuity of r(s, a) with respect to parameter 8. Specifically, for two different parameters 0 and 6', we have
||r(s, a) al) (| 8¹) (1 va) lxx
110 0'1l2
sup (aa)ESxA
1lg(ths, Va)ll2
(i)
(iii) v Vival12 + 2all S V2p, 10 0'1l2>
< <22
1120g sup (s,0)ESxA
where (i) comes from Cauchy-Schwartz inequality, (ii) comes from the Lipschitz continuity of g. and (iii) comes from the boundedness of th, and vh.
Denote θ (0 |2 |1012 - Ba}. J. By the standard argument of the volume ratio, we have
N(O,,, (1 1+ 2Bg
Accordingly, we have
N
R,
2 log (8)
-1xc SN θ
1
2( log (0g(4)//88))
,1| 1-11
T
v2pg
T
T
1 + 1+ 2V-222p Bo
(19)
2(3
log (4,6T
Plugging (19) into (18), we have
( R) inf d T))
=0 Pg VT/C
T Po {
log(1/8) T/C
glog
+ Bo
+e
hold, with probability least 1 8.
16

---

Published as a conference paper at ICLR 2020
A.3 PROOF OF COROLLARY
We investigate the Lipschitz continuity of r with respect to the weight matrices Wi, Wn- Specifically, given two different sets of matrices W,,..., WD and Wi, W. we have
(s)s |Woo .. (Wb) ot )..))..)))
| WWhoWW--Lo...oWWWel v. )_.))))))-)))))))))))))
111 )...))]l
+ [[W")) +I(W"') o(WD--oooooo...WWWl - oW . "
- W W Wwl-WWlllloooooooooooWW ,
+ |1bll (
Note that we have
[WD W. v. )...)...)) 1> S WD- [ 1 )...)
(ii)
WWD-lll2 ||oo|llo..ooo._.. ( a ".. I II v. 1 112 S v2.
where (i) comes from the definition of the ReLU activation, (ii) comes from ||Wil22 S and recur- sion, and (iii) comes from the boundedness of v/, and V.. Accordingly, we have
[|r[s, a) r' (s, a)ll <2 W2ll2 + 1W (oololl
oWW -
<2 - 1lll2 W| - W/ W(,)1..))11
W
22 IW, 2
where (i) comes from the Lipschitz continuity of the ReLU activation, and (ii) comes from the recursion. We then derive the covering number of R. by the Cartesian product of the matrix covering of W WD:
D N
(1
V2Dvd
RD
N(R, 11 s
II
W.,
DV2 11112 1111)
E
S 1
(20)
i=1
where the second inequality comes from the standard argument of the volume ratio. Plugging (20) into (18), we have
dx(m", 7) inf (n=",,
1
dT
(og(1/5)
d2 log
DVV
+
+
VT/S
T/S
hold, with probability least 8.
B PROOF THEOREM 2
The proof is arranged as follows. We first prove the bounded ness of Q fucntion and characterize the Lipschitz properties of the gradients of F with respect to w and 9, respectively, in Section B.2. Then we provide some important lemmas in Section B.3. Using these lemmas, we prove Lemma in Section B.4. We prove Theorem in Section B.5. For notational simplicity, we denote (..)) as the vector inner product throughout the rest of our analysis.
B. BOUNDEDNESS OF Q FUNCTION
Lemma 3. For any w, we have
|
< BQ
where BQ 2v2KppX
17

---

Published as a conference paper at ICLR 2020
Proof.
TTh (s,a)
Blra(se;
-Bz 80 - 5, = a, Tm)
X Fols, (s) ('d(s,)) 1
SSXA JSxA (s,
(8,
Sx1
1=
ro(s, (o(s:a))o0(3,0)(P_. P# (s, (s)))){(ssa)
8xA
2 11000 |1 (/po(Pm))* -Paullrv
1=0
Σ Xv 22/2xpyX
2V 2kPp
1 1-v
where the first inequality comes from the definition of Total Variance distance of probability mea- sures and the second inequality results from (i) of Assumption
B.2 LIPSCUITZ PROPERTIES OF THE GRADIENTS
Lemma 4. Suppose that Assumption 1, 3 and hold. For any w, w', A and 0', have
Vw 0) - V.. (al(((())) 0)12 S L || w'll2
|V 0) Fe 0') S a 110 0' 12
where T. 22205++2B, B.q. 1-
Proof. By the Policy Gradient Theorem (Sutton et al., 2000), we have
VaF(w, Er, v (a))
Therefore,
V Fw, F( 0)1
Br, Vlog(fu 8)
R3,, V Vlog(far(a (²))))= (s, (8,
<
8)) Ex, (4 (s) - Ez Vlog(T
+
Ex.. V Vlog(T 8) Q)) (s. a) - B Vlog(T 8) s)) (s, a)
BQ + L || w/ w'llz + 2B BQ || P llv
< B2 + BBLQ BqLp) || w'llz,
(21)
where the second and the third inequality results from (ii) of Assumption 5. Plugging BQ 2v2npax into (21) yields the desired result. I-o Similarly, we have
[V VoF(w, 0' S 11- 8'1l2 S # 110 8112.
We then characterize the Lipschitz continuity of v with respect to w. Lemma 5. Suppose Assumptions 1, 3 and 5 hold. For any w. and 0, we have
[VoF(w, VoF(w' 0) Sullw w' w'll2,
where S., 22/2gRp,BB_
18

---

Published as a conference paper at ICLR 2020
Proof. We have
VeF(w, -10 Vo [B [0' g' va:]] Bx 10 g(Uss whae
-11 Eppt ( Vor)l Epp Lo(Voo
Therefore, we have
V (w VoF(w',
Epn [o(Vor. Way]] - -Epe [g( wo.)
v max 15i5q Bps g(Ver Nails - Bpp I Nar)s
(22)
Suppose j argmaxigjsa Epe, (v.., voc)s Bps_ A.v.r Vol )a} by Mean Value Theorem, there exists vector W, which is some interpolation between vectors and w', such that Epen g(hh. V )j Epp gl (han)s pV AW va. 1j, w w')
(23)
By Policy Gradient Theorem, we have
Vu Boe I( Wards
= || Vlog (a Ta 8 2) (s, ($)
I sup
V log Tz 8) 1)) (s.
(sa))SxA
$ Bw:
(24)
as where = 0 Eig(s;, ())); ERg 180= 8,000 a, 7z). Combining (22), (23), (24)
and using Cauchy-Schwartz Inequality, we prove the lemma.
B.3 SOME IMPORTANT LEMMAS FOR PROVING LEMMA 1
We denote
(1) VoF(w!))
1
Σ
Vols(wn)) ,000)
20
JEM
and ( (aF
1
Σ
Vuls(w(t) (0ls(())),00011) o(0+1)
4w
JEM
as the i.i.d. noise of the stochastic gradient, respectively. Throughout the rest of the analysis, the expectation IE taken with respect to all the noise in each iteration of the alternating mini-batch stochastic gradient descent algorithm. The next lemma characterizes the progress at the (t + 1)-th iteration. For notational simplicity, we define vector function
G(T)) Ep. (1/,, via)
(25)
Lemma 6. At the (L + 1)-th iteration, we have (F((()+1), (((((et),,(++11))) (F(W((),00)) g(0))
1 [l((((+ (+)
12 + Sw
E (0 (t-1)) 1
L
Tww
2
2
1
+
Sw
+ (1)
E g((++)
g10 113
1
+
1111 LE 0000)
H
g(--1)
2
2n10
2
2110
2
c(0)
1/b 1|
+ 1E
112
+ E
2/
Proof. We have
(t+1) g((-1)) - (F(((())
= -EF((((+t)) - EF(w(()) (((+))))) 3 (0.000 -EF (w(()(()) g(0).
19

---

Published as a conference paper at ICLR 2020
By the mean value theorem, we have
V F(Tl) "aai""ggtt ((t+))),, w(+t1) - w(1) -w)) = F(w(tt)) g(0+1))) - -F(w() ((w(0))((tt))) g((tt))
where (0() is some interpolation between w(++1) and w(t). Then we have
(F( (((tt))))))))))))))))))))))))))) (F(w(()) o((+1))
(((t)))))) -E(V F 0(++1))) (ws()) 100t)) w(th))
+ F(W! gl(+1)), w(tt)) ,((+))),w((+1)) - w(l)).
(26)
By Cauchy- Swartz inequality, we have
F(V 0(++1)
VWF(W ((tt1) o(t+1)), w((+)) - w00)) I E V g((+2)) - (wol gl++2) ) (2llw(++)) - w00
< L Bljw - w 1
where the last inequality comes from Lemma 5. Morever, (4) implies
w(++)) 1 w(t) = n (W g(++1) - 5.
Therefore, we have
B(V=F(w ) w(+1) (1:l)__wh -0( Ell - (0) 11 -E(E!)) (1+1) (1)
E(E!O, n (v Fwi(t)))) g((+2)) E(
1 Ell ((+1) - 10
n
Thus, have
EF( g(++1)) - (FF(w(() p(++1)) S (Iw
) (++2) -
+ The | 2 (27)
By (3), the increment of F(w, 0) takes the form F(wl), F(w10,00++)) g((+1)) - F (w 0(0)) -(G(Fu()) - G(T"))( g((-1) 8(0) 4
2 - 11000)
(G(Tuo)) - G(TT)) - , - 0(1))
,((+1)
(28)
For notational simplicity, we define
(1+1) = 0((+1) - -(0()) + 110 (VoF(w!)) 0000)) +5((0) )(()))
(29)
Note that we have
((.(()) ((1)) = G(T -G(T") - Ho(())
(30)
Plugging (29) and (30) into (28), we obtain
((w(()) (lt+)))) - F (,())) < g((++)) - -(() - (t+1)
((0) 0((+1)) ((1)
710
Since 0 belongs to the convex set (0) 1101/ S 1.). we have
((00)((t))) g(t)) 2 0.
20

---

Published as a conference paper at ICLR 2020
Then obtain
F(w(1) g(++1)
F(w(t) ,0(1))
1 (0(1+11) ((0) + c()) - -((4t), g(++1) -(()) - -(66 g((+1) -((o))
(c - ((t+1), g(tt))) - 0(0)) + 110
| - /0001 - (56 , p(c+1) - )())).
n
(31)
By the definition of (()) in (29), we have
(1+1) = g((+1) - (0(0) + no (VDF(Wl), ((00) + =662)
(32)
and
(0) g(() (gic-1) + no (VoF(wit-)) g(e-1)) + 56- -6-
(33)
Subtracting (33) from (32), obtain
(t) ((+1) (0(1) g(t+1)) - no (VoF(ult-tt) p(t-1)) V FoF(wu() 8(()))
(e (t-1) ((t))
(34)
Plugging (34) into the first term on the right hand side of (31), we obtain
(c) (1+1)) g((+1) g(0)
110
1
(0(t) g(c-1), 0((+1)) g00) (Vol(w(0) 000) Ve p(it-1)),, 0(++1) ((0)
1/0
(B)
(4)
1 - (5( <D
(t-1) 0((+1) ) 000))
(35)
7/0
For term
(A), we apply the Cauchy-Schie Schwarz inequality to obtain an upper bound as follows.
1 L ((80) g(t-1), g(++1) g(4))
1
|0(0) ((t-1) 1)
| g(e) 800/11
s
no
170
2
(8()) prc-1) ||3
1
|occ - B(0)
8(0
< 2no
(36)
2nd
2
To derive the upper bound of (B), we apply Lemma 5 to obtain
(Vo(( ol0) (w 0(1-1)), g((+1) - /(0)
(w)F(((t)) ((9) VoF(w((t1), 0(0), g(++1) -B(1))
( F (lul ((0)-
VoF(w p((-1)) ) p(c+1) - p(0))
< Sw
(1()) (1-1) 11
|oct)) - -0(0) | + 10(0) 0 -
-
S,
(0)))) ( 11
2
Sw
[((++)) g(t)
+
2
2
41
|00)
g(--1)
2
+
|o(e+1) g(t) 2
(37)
2
Plugging (36) and (37) into (35), we obtain
1
(c()) (++1), g((+1) 0(0)
Sw
|
g(t) 12
+
no
2mo
2
1
11
(0(0)
grt-23)1 13
2110
2
5
|w:10)
w
||- (E())) c/ع (1) (((+1) (((+1)_00 -0(0) (38)
-
2
21

---

Published as a conference paper at ICLR 2020
Further plugging (38) into (31), obtain
,(((+1)- F(w(0)0((t1)) F( ,000)
F(w(!),
1
Sw
+ 2/1 -000
(1 1
+ "
|000 p(c-1)
2110
2
2
2010
2)
+
Sw
(0(0) w/0-//
-(56--1
,((++)) - -0(1))
2
1
Sw
+ 11)
| - 0(0)
-0(0
||
1
+ 1 2 1000) - -0(t-1
+
+
2110
2
2110
2
[/)
<c(-11)
||
Sw
wil
1
(39)
2/1
Finally, taking expectation of (39) with respect to the noise and together with (27), , we prove the final result.
EF (t+11) g((+1)) - (F(((( ((0))
1
Su
(w))) (t 2
L
(000 1
-w(
+
Ylu
2
1
Sw
g((e+)) g(t)) 2
+
+
+
E
2110
2
+
1
+
((0)
gic-1)| + n
c(()
+ 1 E
56
1t-
2nee
2
2μ
We then characterize the update of w.
Lemma 7. The update of satisfies
EE (w(+)))++ (w)()) w(t-1)), (,((t()))) - -((tt)))w(()) w(t))
F (((00)42) - p((+1)) (B(++1) g(11) (c((+2) - ((++1),, p((+1) (((+t)),((++) 8(0)
770
MM
E
0((ct++1) - 000013 100001))000011
nh + E _ -w(t) - nott
| - w(
2
2
Nw
+ n
|c( | +
nh E ||(0-11)
2
24
2
22

---

Published as a conference paper at ICLR 2020
Proof. By the update policy, we have
E ((w(tt)) w(t) (wl1) w((l wolltt)) ) - -w(t))
V Vwr(( 01++1)) + E(() -vf(w((-1) ((()) e((-1) ,w((+)) w(())
B
((wl" (((+1))- FwF(())) gl0)) (((())))))))) -w(())
-. V F(w (1) (10) V-F(wlt-)) (00)). w(ttt) - -w(()) ) -n ( The (V V Fl o((-1)) + <(-)) + n ( (EL- (w(lt1) ( - w(1))
S E. Fl g((+1)) - F( ((0)) (1+1) - wwit)
(C)
1E (WF(W(())
(w (1)((111),00)) ,0(1)), w((+1) - -w(!)
(D)
E
+
n
E
((-1)
2 + 2
Th ((+1)) -
- 3
(40)
Then for (C), by the definition of objective function, we have
(C) = ns V
G(T -
0l()) - -w(()
= = Σ
V
- -V + Vu (1) w((++) ),);
w(1))
1 (g(++1) -(());
= E (0(++))) -(024t)-00))
0(0)) [[]]][VVVG[. (V.G(Fwo)) - V. )i), w(+1)) w(())
B. > - - (v.G( ).), - w!!)
(41)
where for every j. Tato is some interpolation between vectors Tuco and Taatn such that
- w()) = G(Fait)))) - G(Fwt))))
(42)
For the first term in the right hand side of (41), by Lemma 4, we have
F E.N. Σ (o(1+1) - 0(0) (Va V. (( w(tt) -00))
22 (wo(tt))) - -0
(43)
For the second term in the right hand side of (41), by (42) we have
-(o(+1)- - - (Vu ((, w())
E E
=-n.E (G(Twer-)) - G(F ), g(++1) - -0(0)
23

---

Published as a conference paper at ICLR 2020
Then by the defintion of objective function, we have
Th E.
Σ (0(++1) (0(+t1) -())) ( (V )5 wl(t1)
-w(()))))((
1 (0lc+2) 0((+1] - c(( =((t1)) + +10((t1)
= nh E
770
1 (p(t))) g(() - (((+1) + 5%55 1 gl++1) B(0)
110
E E (100+))) 0(++1))= - (0(t+)) - )000 - (e (e(1+2) - ((+11)), - 0(+)
1/0
B(((tt) ,(t-)
0((-1) 0(0) - mm | - ((0) -0(0) ?
2
S E (0lt+2) - -0(+1)) - (0(++1) - ) - - - e((+1)), 0(++1) - ((()
170
-Bto M | - 00001 +
nu
E
(1)
(44)
24
For (D), applying Cauchy-Schwarcc inequality we have
-Iu.B(V ,000) - o(+) ((+11)
- (0))
LB - (0)
|w( (c-11)
2
2
nowb E |ws w())
2 + Notww E -
122 (45)
2
Finally, combining (40)-(45), we prove Lemma
For notational simplicity, we define
g(t+2) (0(++2) - g(t+1)) (0((+))) 0(0)).
(46)
Lemma 8. The first term on the right hand side of Lemma (7) satisfies
M E
(10le+2) - -l(+1)) - (Q(l+1) - 0(()) (e((+2) - (((1))))
- -010)
(47)
no
The E
|oltt2) - -oictu) +
pl(ctt) - -0r0/1
+
E
2010
2
2110
52
E
[[ll(cct1)) - (t)
2
3
7o
E
c
(1+1) 22
+
E
(660) 11=)
(48)
2
Proof. Plugging (46) into (47), obtain
nh E ((0l422) g((+1)) - (g(e+)) (00+t1--009 -8(0) - (6(1+2) - (l(1)) g(c+1) - ((0)
nw ( (8(1-2) (c(1+2) - ((+1)), g((+2) ((0042) gg(t1)))
77
Th TE (5(e=2) - (c(+2) - (1+1)) )8122))
ThE è (51t42) gll+2) - g((+1))
no
Th E ((ll)))) ((+1))), g g((+1))
(49)
178
By applying the equality
1
(u, 7
2 +
|10112 122
1/u =l(2))
24

---

Published as a conference paper at ICLR 2020
to the first two terms the right hand side of (49), we obtain
T B
(10(4)))
(0(++1)- -((+)))
- (e(1+)) - (((t)) 0(+++))))))) - -0(+)
1j0
Tw EE
(110443) -(e - c(ttn)1 ||: + +11000122 ? ||(0t)) -clttll 2
2116
Thw E
[|60412/1 2
1/² + =|1o0ct2)) - -0c+t1112 [0(+1) - 00000/
2010
2
M TE (t+2) - ( (((+t)))((++)) -((+1)). +
(50)
170
Recall that
0((+2) = 11 (oitt1) + all (Vot(w+tD)(tt)) + c/ <b++1))
and
@(++1)= = 11x (0() + no (VoF(w + 2b²)))
Following from the convexity of [0) |10||, S k), we have
(c()2), g((+2) - g((+1)) < 0 and
(e(++)),((++)) - p((+1)) 2 0.
Thus, the last term on the right side of (50) is negative. By rearranging the terms in (50), we obtain
E -
- 0(++1)) - (0(++)) 1) - )(0)- - (e (++22 - (t+11)), 0(++1)
-0()) 0(0)
130
< Th
B Blb042) (L(2) - _(tt)) | The E |llt2) p((+1) ||
+ Th E plct2) 010) 2
2n00
2n10
2
2n10
(51)
By definition of ((++2) in (46), we have
g(t+2) (e(++2) - (1) (0(t++))
( 0(+++) -((+))))))+))) - -
- -0(0) _ -c(t+1))
no [G( G(F - m((((+1)) - o(()) + 56 c(l+1) - -
Using the Cauchy-Schwarz inequality, we obtain
nw
E - (c(1+)) ( -((t)))
2110
31/=000
[B|G(( - G(a )12 + IE' -u(olett)-001)
[(++1) - =5001(3)
+ EE 58
2
31
- w 1 51rn
E
3
BB BBlloctt)) p(0)
1/
2 3
E [((tt)))
e(8)
2
2
2
(52)
Plugging (52) into (51) yields (48), which concludes the proof of Lemma 8.
Lemma 9. For the update of w, we have
2 (1+1)) (1)
2
(1) (1) 1)
2
2
2
nu (5Lm
+ 1) +
S7
(((+1) - w(t) w00013 +
nww
E. 2l(ws)) - w
<
E
2
2
2
The
E
| - (1++1)
+
no
2
nw
mm
E Bllocct O(5) 2
2110
2no
2
+ (n2
+
n EF
[(t)
2
+
n
E
|
1)
2 +
no
[
E
+ E ||
2/1
2
2
2
25

---

Published as a conference paper at ICLR 2020
Proof.
Combing Lemma 7 and Lemma 8, we obtain B(w((t1) w() - (w(t) w((t-1),, w(t)) - (1))
The (0cet2) 0c+t1)/
1|2
+
2 51
Tl
E
[iit+)) - 0(0)
2710
2
2010
2
w
(c+11)
w0)0
1/2
1ml B
|
-B(00/2
2
2
2
2
+
2m LW
- w
+
(Lw
now
(Lw
+
11
(w+
- 000
+ Moww
2 E (l(1)) - (t /
2
+
+
Th J
c(t)
nh
c(l
(1-1))
2
+
Tw (IB) 156
((++1)
2
+ E
1 c000
112
(53)
21
2
2
2
2
Note that we have
((w(1+1) (1) (wi1)
(((-1))
) (((+)))
(())
E w (1-11) - w///// 11/
1
E
w (t)
-w(t-)) | =
-w()) (w) - w(( 1) ||
2
2
2 2 ( !10
1 1
B
w (1-1)
(54)
2 2
Combining (53) and (54), conclude the proof of Lemma 9.
Lemma 10. Suppose Assumption 1, and 5 hold. F(w(t), (()) is lower bounded throughout all iterations.
Proof. By definition of in (2), we have
F(w(0) 2 Ex Ei Faces (), En Foc (Ve. v/a) 11 |10| ABH
2 222 x= + ~n²² +BBH).
(55)
B.4 PROOF OF LEMMA
Recall that we construct a potential function that dacays monotonically along the solution path, which takes the form
g((+1) EF ((((1) g(++2)) +
1 + 2m
E (w 100
2
+
Tl
pml
2 mon
3
E
[|00-)) 0/(+1)1?2 wiw E g(cc1) -800)))100/()) (56)
2118
4
for some constant s > O. We define five constants k2, 12, ks, his, his as
1
(ow (7 +1)
no
S
8.
k2 = s
21w
2
2
2
2
nwHH
3
pm
1
+ μ
hig
nw 1112
hs
2
8
2110
pM
Sw + 2/1
11 8
+
2110
2
Here, restate Lemma and then prove it.
Lemma 1. We choose step sizes 1jo, The satisfying
L (8L + 2) 2L 0
7L +
1
The S min
no S min
150
150S?
100(2 +
S.)
26

---

Published as a conference paper at ICLR 2020
and meanwhile nw/ng no 1 /\ 4//30L + 5), where Li Sx + ASH Then have
g(++1) g(() S - =b ( - (())
kizlE |w(0)) (t-1) 2 - kalE
p - 0
2
kgB [0(c+1) (/00
1
kg
[000 1(1-1)
|2
2
2 +
1 R
cll
11
2
2
+ B
+
?
E
ctt
2
+
3nw 10
(E
50
(c+ 13
+ E
| 13))
(57)
2
2
2
2
Moreover, we have k1, k2, K3, kg Ks
>
0 for
8
(58
9)
Proof. For notational simplicity, we define
k(++1) = 1 Ln (w(tt) w(t) w(11
2
+
Tle
mm
+
3
E [o(tt)) - p(C-1)
-/ +
E g(e+1) - 810) 01011
(58)
2ne 4
2
8
By rearranging the inequality in Lemma (9), we obtain
k((+1) k(()) -K()) =
Ta (TL + 1)
+
no S
(e+1))
wr
||
2
2
2
Nu Lo
E
wil() (1-)
kM
3u
E
|
(((+2) |
2
2
4
2
1ul
B
[o(c-1)
8(()
E
[0(()
- o((-1)
1/
8
8
2
+ (m/ +
nu
E
(t)
2
+
Tu
E
[e(tt (w
1)
+
37
(E
(((+1)) 1
12
+
5/60 2
12)
(59)
2μ
2
2
2
By definition of p(t) in (56), we have
g(() (1) ((0)) + 8 K(t)
for some constant s > 0. Combining (59) and Lemma 6, since The < zt. we obtain
nh (7T + 1) +
3n )) |lusttD - w()) 2
g(++)) - =(( $ -
s.
27w
2
2
nhw Lu
Sw
(w())) (t-1))
(
mm
3y2
| - g(0+1)|1
-
2
2
12
4
2
mml
2p +
S. 1) |
010)
2
+
8
2110
2
mM
1
)) ) (00)) - -
|
+
8
21j0
2
(( 2
+ E
c(1)
+
1
2/1
2
+
(1
+
Nh
E
(1)
+
E
clt
1)
3n
(E
40
(t+1)
+
2
2/
2
2
(60)
Since 7/0 < 150p we have hig > Now we choose a proper constant & such that ki, kz his his are positive. Note that they are positive if and only if
(T + 1)/2+ 31 }),
1/(2n=)
(61)
noLw/2> S/,,/,
(62)
s (um=/8) > 1/(2n0) + (2p + S2) (mmw)/8> 1/(2n0) + 11/2.
(63)
(64)
27

---

Published as a conference paper at ICLR 2020
Rearranging the terms in (61), (62), (63), (64), obtain
Sw
1/(27w)
< < (7T + 1 + 3mo S2)/2
(65)
fl I:-
1/(2))) + (Sw. + 22)/2
1/(21/w)
< 8 <
(66)
mmw88
N/w (T + 1 + 3no /
Since
7L +1
n7 -
and ne
1505%
100 Sw)
by rearranging the terms in (65) and (66) and taking the leading terms, obtain
T
< P
Tl
<
and
Sw +)
no
M + 5
Therefore, have
1
<
n < The and no < n1: 30L +5"
170
where
L
The min
(8L + +2)" 2L
7L. +
To min
150gz
1505
100 + Sw)
B.5 PROOF THEOREM 2
Let k 1/ min (k1, and Φ = max (1, 1/ 1/n8). Then we have
10 [ |lactD - p(() -p()) -
E (+(t)) - w(0)
NJN
t=1
S Φb Σ (E()] - -E((22)
N
Σ
N
((1 + 8n +
8TS 24u
2
+
1
E
50
(t-1)
|2
2/1
s (nw/22 E [<(l-1)
1)
mo /2. (B 550
(++11)
2
+ E
c.6 (?:1)
2
NV
I ok (E(1)) - -E(N)) +
Σ
(2 max
Tu + sn
817
87/
(+)
2
2/1
2
1=1
+ max {
3m
(((()
13)
(67)
(24²
2
Now
V= max
2 mmx Thw + 2u
87W
87w
3 max
1
3m
2/1"
241²
and divide both sides of (67) by N, we have
JN ko(g - E(N))
Mc
Ma
kov
(68)
N
aw
90
By definition of & in (56) and Lemma 10, we have
g(M) 2 (N) ,0(N)) 2 (2V2ppk + 1²²²" + ABHH)
-0c.
Now for any given e > O, we take
4kouMs 4k and N = kó
20(1) + 4v 4V + pxi² + 2XBH
and obtain
JN S..
28

---

Published as a conference paper at ICLR 2020
C EMPIRICAL MAXIMIZER CASE
Notice that the object function (2) is quadratic in and thus we are able to get the empirical maxi- mizer by simple calculation instead of performing stochastic gradient ascent at each iteration. This allows us avoid using large batches while achieving the same sample complexity Ö
Given a fixed w(), by definition of G in (25), we can get the optimal 0* (w(()) in population form:
- [G((m())) G(TT)))))
0" (w))))
(69)
At the (t + 1)-th iteration, one trajectory randomly and then apply stochastic gradient descent to the outer minimization. More specifically, the updating rule is defined
achieve the closed form of the empirical maximizer by sampling
(1++1) (w))) [ G(TT")]
(70)
11
((+1) (t) n (0
(71)
where G is the empirical version of G obtained by sampling, and Vwf is the stochastic approxima- tion of V F at the (t + 1-e iteration.
We define the stationary point as follow.
Definition 4. We call w an stationary point VwF("", (""""""""""""""""""""""""""""""" (w)))) =
Before proceed with the convergence analysis, impose the following assumptions the problem.
Assumption 6. There is some constant MG > 0 s.t. forany wi 0 and æ, the following two conditions hold.
Unbiased EV, 0) F(w, = BG(
Gradient bounded I V.Tilw oII s Mc.
Assumption 6 requires the stochastic gradient to be unbiased with bounded second moment.
Corollary 4. Under Assumption 1, 3 and 5, there exists Bp = 12p2 have [lw,, (w))) Br.
μ + +Bu such that for any w, we
Proof. By Equation (69).we have (10' (w)ll2 2v2p, Plugging this into F(w, 0 (w)), we have for any w.
FFw, 8" (w))l = Ex (w)( gWeer e. ve.)) - Ex. (0"(w),g(().. g( va.)) ( - (10((w)) (w))l2
s 210 (w)llz max [lg valll - AH (F + p 2/2 10" (w))l
8,
< 12p2 + AM #
(1WW0)00++))) Vofi(w(t), (0t)))) the i.i.d stochastic noise and 0g (t) (w) g(0) as the i.i.d error of empirical maximizer. We denote E. as
For notational simplicity, We define (t)
(t) (t 2 1). We measure the sub uub-stationarity of the algotithm the expectation over e!! (t > and of
at the iteration N by
NN min E V (()) .0 (
IS
Then state the global convergence of the above mentioned optimization method.
29

---

Published as a conference paper at ICLR 2020
Theorem 3. Suppose Assumptions 1, 3, 5, 6 hold. +S(2 then we need at most
Given any
0, we take T
N = (1B/let ABH) + S2/N)Ma
iterations to have IN- < C.
Proof. By employing the first inequality in Lemma have F( (w(())) ((w((), 0 (w)())) (V,F(w((t) )) (ott)) w00)
L
$
(72)
2
Note that
V ((w(0)) (" (w((1))) (((+1) - -w(0)
= FWWV (n (V ((1) + =
BW (w(()) Th (V
(w) - -bb) + +
@ B(V F( 1 (w) mhL (V F F( (w(()) + ((
E(V F (w ())) - V. F(w (w)
E
V F (w) 0 (w
(73)
where (i) comes from the unbiased property of g(t) and the fact that Fw,, 0) is linear in 8, and (ii) comes from the unbiased property of [u(,, 0). Now taking the expectation on both sides of (72)
and plugging (73) in, we obtain
12 - 2
T n Mc. (74)
(t(( o (w)()))= - F(w!t, or (w)))) + I.
Dividing both sides by Nw and rearranging the terms in (74), we get
(wF(W 0 (w(()) 2 EF(W!), 8" (w(()) - 1(w(t+1), 0" (w(())
Lu MG
E
T BF(w()) 0 (w())) ((w(t+)) O (w((+)1))
2
Lu
MG
NW (F((()) or (witt)1)) - F(witt1), 0r (w((1)))
2
(75)
7h
Now consider F(w(t+1), (e (((((()))))) - F(u((-1)) .0 (w((t))), we have
((w(t+1), 00 () - ((w((t))),0
=(G(Twrl))) G(x'))(() "),0" (000((((+))))) (++11)) - (((( - -((")) 0" (w)(0)) 100 (w)()) 1?]
1" (1(00(( 1
2
(uo (wllt)))), 0 (w)())))) - 0r (w)))))
1 (0r (w)(t+))) 0 (w((t), o (w(t+)))
00 (w))
/ 0 (wnlet1)) 0¹ (witt)) |
(G(T))tt)) ((Twe())
1
82 < 2p
(t+1) - -0))
(76)
30

---

Published as a conference paper at ICLR 2020
Taking expectation on both sides of (76) with respect to the noise introduced by SGD, we have
(F(w(()))) ff (w)(+1i)) F(wlt+1), 8 (w(1)) z n Me.
24
Summing the equation(75) (75) up, we have
N
F (w(t)) 80 (w(()))) |
E
I (F( 00 (w)))) F(w((t1)) (w)()))) 2
No
1
( (' F(w((t1), Or (w(t))))
1/2
N
Lw Na
EF EF (++1), (0 ,0((((+1))) - F(w(t+1), 0 (w((())) +
N
2
N
(F( .0 (a((t)))) - F(w(t+1), or (w(++11)
7/2
Lu Na.
neu Mc
fl
2p
Dividing both sides of the above equation by N. we get
S [F(W()) 0 (w())) (F(( 0 (w((N))))
F 0- (w()))
min
SSK
Nmw
+ ( Lu
$
+ Ma.
2
2/
Since (F(w or (w(l)))) - EF(w(N-1), (W(N++)))) S 2Bp. Take The V (T.,.2 (2/2)MoH then we have
2Bc
EE ((W!)) 0 (1) S 4/
Br S5//))aa
min
ISIN
N
12pd
where Bp + AMH. This implies that when Thw 55/
we need at most
N = (18g/ut AMH)(Lw
+ (///++ANH)(L
M)
62
such that IN < E.
31


Reviews:
[{"review_id": "SklghBKaYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper presents theoretical analysis of the generalization properties of GAIL, as well as the local convergence of the traditional minibatch SGD applied to its min-max optimization problem (without assuming convex-concave structure of the game).  Specifically, the authors first prove a generalization bound for GAIL that characterizes how well optimizing the empirical GAIL objective minimizes the true population version (in terms of an \"R-distance\" they use the characterize the expected distributions induced by the underlying policies for a given reward class).  Second, they prove a convergence result for minibatch SGD applied to the min-max game, showing that the method will converge to a stationary point regardless of any convex-concave structure.\n\nComments: Before I begin, I should add that several elements of the paper were a bit difficult for me to follow, so I'm happy for the authors to correct any factual errors that I might make.  Overall, I think that this is an interesting, if somewhat incremental and technical paper about the generalization and convergence of GAIL.\n\nFirst, on the generalization aspects, the methodology here seems to largely parallel Arora et al.'s analysis of generalization in GANs.  The main technical steps seem to be, 1) some effort in determining the proper distance to use in the first place, and how to define generalization, which they do via the R-distance, and then 2) on the more technical side, overcoming the fact that trajectories do not provide iid samples as is the case in the GAN analysis.  This later difficulty is overcome via the independent block technique, which allows one to bound the relevant population quantities of interest by sampling from subsampled blocks of the original trajectory.\n\nSecond, on the convergence side, the main result here seems to be a generic convergence result for minibatch SGD applied to a non-convex-concave game.  I may be missing something here, but it doesn't seem like there is any real specificity to the GAIL objective, but rather this would apply to any such min-max problem (I suppose also in the case where there is an L2 projection in the gradient step); while there is some discussion of the chain mixing properties, this seems largely needed just to provide bounds on certain constants.  The proof is rather technical (I admit I didn't go through it in much detail) and even the sketch doesn't provide a great intuition about what might make this problem harder than proving convergence of traditional SGD in the non-convex pure minimization case.  And for example, even convex-concave games have well-known pathologies when running gradient descent, such as cycling around an optimal point, and I didn't understand whether anything was being done to explicitly account for this, or if one of their assumptions essentially just avoids this possibility (maybe the mixing properties prevent this?).\n\nOn the whole, despite what seems to me to be a somewhat incremental nature, I'm still leaning toward accepting the paper: technical analysis like this is good to have, and the setting is distinct enough from past e.g., GAN work, that I believe it stands on its own.  I do think the clarity of the paper can be improved, as well.  This includes some simple elements like spacing out the equations better in Section 4, which were currently very condensed and difficult to read (and there is plenty of space to make the paper longer).  But I also would have liked a bit higher-level explanation of the challenges involved in proving convergence (like avoiding cycling), rather than just highlighting the functional elements of the proof.  I actually think the generalization section did this relatively well, in regards to the setting up their choice of IPM in contrast to the GAN work, but it was lacking in the convergence section.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkx21bQxqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the theoretical support for Generative Adversarial Imitation Learning (GAIL).   Specifically, two main points are shown: (1) For general reward parameterization, the generalization of GAIL can be guaranteed, as long as the class of the reward functions is properly controlled; (2) When the reward is parameterized as a reproducing kernel function, GAIL can be efficiently solved by stochastic first order optimization algorithms. \n\nNumerical experiments are provided on three classic continuous control tasks. RL algorithms are generally questioned in terms of reproducibility. Does the variance of different runs have an impact on the validation of the proposed theory?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJlR4KlCKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submission provides theoretical analysis of GAIL regarding its generalization and convergence properties.\nThe first part establishes a probabilistic upper bound on the change of the worst-case regret (over the possible reward function) when shifting from the empirical expectation of the expect reward to the true expectation.\nThe second part considers the convergence properties of GAIL when alternating mini-batch stochastic gradient updates on the policy and discriminator. This section shows that number of iterations required to achieve a \"sub-stationarity\" J < epsilon is in O(1/epsilon). The proof assumes (vanilla) policy gradient updates, and seems to be further restricted to linear discriminators with bounded weights.\nExperiments on Acrobot, Hopper and MountainCar compare learning curves for a 3-layer neural network reward function, and linear reward functions. The linear reward function uses the neural network architecture but does not optimize the first two layers (and is thus linear in random features). Furthermore--for the linear reward function--single gradient updates are compared with 10 gradient updates per iteration. The experiments indicate that single updates perform similar to 10 updates and that the linear reward function converges more stable than the neural network. The neural network, however, can achieve slightly better performance on the considered problems. These results are consistent with the provided theory.\n\nContribution/Significance:\nI think that the theoretical properties of GAIL and related adversarial IL and IRL methods are not yet sufficiently understood. Both achieving stable convergence and generalization from limited number of trajectories can be difficult in practice, so there is high interest in theoretic analysis of these methods. I am not aware of similar analysis of GAIL.\n\nSoundness:\nI did not have the time to fully verify the proofs, so I only skimmed the appendix and focused on the proof sketches in the actual manuscript. The assumptions seem reasonable and I could not find errors in the proof sketches. I am having some problems with the proof sketch of Theorem 1. I am not sure about the meaning of $\\mathbb{E} \\phi(s')$ at the last line of page 4, which is unfortunately not rigorously defined. I assume the expectation is with respect to the sampled blocks. So wouldn't this term be a functional of r? However, I assume the supremum is only w.r.t. the first term (what would be a supremum over an inequality anyway?). Also it seems like the term could be subtracted from both sides of the inequality. Some hints would be highly appreciated here.\n\nOn a minor note, I think that min and max should be swapped in Equation 1 and 2 (r corresponding to a reward, not cost).\n\nPresentation/Clarity:\nI don't have a strong mathematical background and would not say that the paper is fully clear to me. However, this is rather caused by the nature of the paper. Indeed, I think that the paper is well written and relatively clear.\n\nEvaluation:\nThe paper only contains a very short experiment section, however, this is reasonable given that contributions are theoretical. I would be interested in some insights on the strong oscillatory behavior of the NN-reward on the acrobot task. I noticed such behavior with GAIL also on more complex tasks and sometimes it would not even recover as quickly as in the acrobot plot. Is this caused by overfitting of the discriminator?\n\nAssessment:\nI think that the paper could be an interesting contribution for ICLR. However, my confidence is rather small here.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a theoretical analysis of the recent and popular Generative Adversarial Imitation Learning (GAIL) approach. Valuable new insights on generalization and convergence are developed, and put GAIL on a stronger theoretical foundation. Reviewer questions and suggestions were largely addressed during the rebuttal.
Decision: Accept (Poster)