Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
Authors: Lingxiao Wang
Qi Cai
Zhuoran Yang
Zhaoran Wang
Venue:  (2020)

Abstract: Policy gradient methods with actor-critic schemes demonstrate tremendous empirical successes, especially when the actors and critics are parameterized by neural networks. However, it remains less clear whether such "neural" policy gradient methods converge to globally optimal policies and whether they even converge at all. We answer both the questions affirmatively in the overparameterized regime. In detail, we prove that neural natural policy gradient converges to a globally optimal policy at a sublinear rate. Also, we show that neural vanilla policy gradient converges sublinearly to a stationary point. Meanwhile, by relating the suboptimality of the stationary points to the~representation power of neural actor and critic classes, we prove the global optimality of all stationary points under mild regularity conditions. Particularly, we show that a key to the global optimality and convergence is the "compatibility" between the actor and critic, which is ensured by sharing neural architectures and random initializations across the actor and critic. To the best of our knowledge, our analysis establishes the first global optimality and convergence  guarantees for neural policy gradient methods. 

Published conference paper at ICLR 2020
NEURAL POLICY GRADIENT METHODS: GLOBAL OPTIMALITY AND RATES OF CON- VERGENCE
Lingxiao Wang"
Qi Cai
Zhuoran Yangå
Zhaoran Wang
ABSTRACT
Policy gradient methods with actor-critic schemes demonstrate tremendous empir- ical successes, especially when the actors and critics are parameterized by neural networks. However, remains less clear whether such "neural" policy gradient methods converge globally optimal policies and whether they even converge all. We answer both the questions affirmatively under the overparameterized two- layer neural-network parameterization. In detail, assuming independent sampling. we prove that neural natural policy gradient converges to globally optimal pol- icy at sublinear rate. Also, we show that neural vanilla policy gradient converges sublinearly to stationary point. Meanwhile, by relating the suboptimality of the stationary points the representation power of neural actor and critic classes, we prove the global optimality of all stationary points under mild regularity condi- tions. Particularly, we show that a key to the global optimality and convergence is the "compatibility" between the actor and critic, which is ensured by sharing neural architectures and random initializations across the actor and critic. To the best of our knowledge, our analysis establishes the first global optimality and con- vergence guarantees for neural policy gradient methods.
INTRODUCTION
In reinforcement learning (Sutton and Barto, 2018), an agent aims to maximize its expected total reward by taking a sequence of actions according to policy in a stochastic environment, which is modeled as a Markov decision process (MDP) (Puterman, 2014). To obtain the optimal policy, policy gradient methods (Williams, 1992; Baxter and Bartlett, 2000; Sutton et al., 2000) directly maximize the expected total reward via gradient-hased optimization. As policy gradient methods are easily implementable and readily integrable with advanced optimization techniques such as vari- ance reduction (Johnson and Zhang, 2013; Papini et al., 2018) and distributed optimization (Mnih et al., 2016; Espeholt et al., 2018), they enjoy wide popularity among practitioners. In particular, when the policy (actor) and action-valus function (critic) are parameterized by neural networks, pol- icy gradient methods achieve significant empirical successes in challenging applications, such as playing Go (Silver et al., 2016; 2017), real-time strategy gaming (Vinyals et al., 2019), robot manip- ulation (Peters and Schaal, 2006; Duan et al., 2016), and natural language processing (Wang et al., 2018). See Li (2017) for detailed survey.
In stark contrast the tremendous empirical successes, policy gradient methods remain much less well understood in terms of theory, especially when they involve neural networks. More specifi- cally, most existing work analyzes the REINFORCE algorithm (Williams, 1992; Sutton et al., 2000), which estimates the policy gradient via Monte Carlo sampling. Based on the recent progress in non- convex optimization, Papini al. (2018); Shen al. (2019); Xu al. (2019a); Karimi et al. (2019);
"qual contribution
Northwestem University; wttp://www.....g/....o..ooeeeee.
: NNrtthwestemn
5 Sprinceton University; ey@@princetoon.eer
Northwestem University, thanranngnhhoorraaaaggggggg com
See https://axxvv.org/abba...
for the full version.

---

Published as a conference paper at ICLR 2020
Zhang et al. (2019) establish the rate of convergence of REINFORCE to first- or second-order stationary point. However, the global optimality of the attained stationary point remains unclear. A more commonly used class of policy gradient methods is equipped with the actor-critic scheme (Konda and Tsitsiklis, 2000), which alternatingly estimates the action-value function in the policy gradient via policy evaluation step (critic update), and performs a policy improvement step using the estimated policy gradient (actor update). The global optimality and rate of convergence of such class even more challenging to analyze than that of REINFORCE. In particular, the policy evaluation step itself may converge to an undesirable stationary point or even diverge (Tsitsiklis and Van Roy. 1997), especially when it involves both nonlinear action-value function approximator, such as neural network, and cemporal-differene update (Sutton, 1988). As result, the estimated policy gradient may be biased, which possibly leads divergence. Even if the algorithm converges to stationary point, due to the nonconvexity of the expected total reward with respect to the policy as well as its parameter, the global optimality of such stationary point remains unclear. The only exception is the linear-quadratic regulator (LQR) setting (Fazel et al., 2018; 8: Malik et al., 2018; Tu and Recht, 2018; Yang et al., 2019a; Bu et al., 2019), which is, however, more restrictive than the general MDP setting that possibly involves neural networks.
To bridge the gap between practice and theory, we analyze neural policy gradient methods equipped with actor-critic schemes, where the actors and critics are represented by overparameterized two- layer neural networks. In detail, we study two settings, where the policy improvement steps are based on vanilla policy gradient and natural policy gradient, respectively. In both settings, the policy evaluation steps are based on the TD(0) algorithm (Sutton, 1988) with independent sampling. In the first setting, we prove that neural vanilla policy gradient converges to a stationary point of the expected total reward at 1/v -rate in the expected squared norm of the policy gradient, where T is the number of policy improvement steps. Meanwhile, through a geometric characterization that relates the suboptimality of the stationary points to the representation power of the neural networks parameterizing the actor and critic, we establish the global optimality of all stationary points under mild regularity conditions. In the second setting, through the lens of Kullback- Leibler (KL) diver- gence regularization, we prove that neural natural policy gradient converges to a globally optimal policy at a 1 1/ /Taee in the expected total reward. In particular, key to such global optimality and convergence guarantees is a notion of compatibility between the actor and critic, which connects the accuracy of policy evaluation steps with the efficacy of policy improvement steps. We show that such a notion of compatibility is ensured by using shared neural architectures and random initial- izations for both the actor and critic, which is often used as a practical heuristic (Mnih et al., 2016) 6). To our best knowledge, our analysis gives the first global optimality and convergence guarantees for neural policy gradient methods, which corroborate their significant empirical successes.
Related Work. In contrast to the huge body of empirical literature on policy gradient methods, theoretical results on their convergence remain relatively scarce. In particular, Sutton et al. (2000) and Kakade (2002) analyze vanilla policy gradient (RHINFORCE) and natural policy gradient with compatible action-value function approximators, respectively, which are further extended by Konda and Tsitsiklis (2000); Peters and Schaal (2008); Castro and Meir (2010) to incorporate actor-critic schemes. Most of this line of work only establishes the asymptotic convergence based on stochastic approximation techniques (Kushner and Yin, 2003; Borkar, 2009) and requires the actor and critic to be parameterized by linear functions. Another line of work (Papini et al., 2018 8; Xu et al., 201 9a;b; Shen et al., 2019; Karimi al., 2019; Zhang et al., 2019) builds on the recent progress in nonconvex optimization to establish the nonasymptotic rates of convergence of REINFORCE. (Williams, 1992; Baxter and Bartlett, 2000; Sutton et al., 2000) and its variants, but only to first- or second-order stationary points, which, however, lacks global optimality guarantees. Moreover, when actor-critic schemes are involved, due to the error of policy evaluation steps and its impact on policy improve- ment steps, the nonasymptotic rates of convergence of policy gradient methods, even to first- or second-order stationary points, remain rather open.
Compared with the convergence of policy gradient methods, their global optimality is even less explored in terms of theory. Fazel et al. (2018); Malik et al. (2018); Tu and Recht (2018); Yang et al. (2019a); Bu et al. (2019) prove that policy gradient methods converge to globally optimal policies in the LQR setting, which is more restrictive. In very recent work, Bhandari and Russo (2019) establish the global optimality of vanilla policy gradient (REINFORCE) in the general MDP setting. However, they require the policy class to be convex, which restricts its applicability to the tabular
2

---

Published conference paper at ICLR 2020
and LQR settings. In independent work, Agarwal et al. (2019) prove that vanilla policy gradient and natural policy gradient converge to globally optimal policies at 1 1/vTT- -raes in the tabular and the tabular setting, their rate convergence of vanilla policy gradient depends on the size of the state space. In contrast, we focus on the nonlinear setting with the actor-critic scheme, where the actor and critic are parameterized by neural networks. It is worth mentioning that when such neural networks have linear activation functions, our analysis also covers the linear setting, which is, however, not our focus. In addition, Liu et al. (2019) analyze the proximal policy optimization (PPO) and trust region policy optimization (TRPO) algorithms (Schulman et al., 2015; 2017), where the actors and crities are parameterized by neural networks, and establish their 1/vTT- rates of convergence to globally optimal policies. However, they require solving a subproblem of policy improvement in the functional space using multiple stochastic gradient steps in the parameter space, whereas vanilla policy gradient and natural policy gradient only require a single stochastic (natural) gradient step in the parameter space, which makes the analysis even more challenging.
-rates
linear settings.
There is also an emerging body of literature that analyzes the training and generalization error of deep supervised learning with overparameterized neural networks (Daniely, 2017: Jacot al., 2018; Wu et al., 2018; Allen-Zhu et al.. 2018a;b; Du et al., 20:8a;b; Zou et al., 2018; Chizat and Bach, 2018: Jacot al., 2018; Li and Liang, 2018; Cao and Gu, 2019a;b; Arora et al., 2019; Lee et al., 2019), especially when they are trained using stochastic gradient. See Fan et al. (2019) for a detailed survey. In comparison, our focus is on deep reinforcement learning with policy gradient methods. In particular, the policy evaluation steps are based on the TD(0) algorithm, which uses stochastic semigradient (Sutton, 1988) rather than stochastic gradient. Moreover, the interplay between the actor and critic makes our analysis even more challenging than that of deep supervised learning.
Notation. For distribution μ on Q and p > O, we define Il = Ua If/P as the Lp(u) norm of f. We define (.f(-))p.s norm of f. We write [[ ppp for notational simplicity when the variable of f is clear from the context. We further denote by -1 the [=()))-orm for notational simplicity. For a vector & E TR.
inf(C 2 0: [f(=) S C for p-almost every x} as the Loo (p)-
and p > O, we denote by ||ől the fn-norm of Φb We denote by x = ([x]] ..... [x]]T] T vector in Rmnd where [xlk Rd is the i-th block of for i E [m]]
BACKGROUND
In this section, we introduce the background of reinforcement learning and policy gradient methods.
Reinforcement Learning. A discounted Markov decision process (MDP) is defined by tuple (S, .A, P.C.T,7) 7). Here S and A are the sets of all possible states and actions, respectively. Mcan- while, P is the Markov transition kernel and r the reward function, which is possibly stochastic. Specifically, when taking action a E A at state s E S, the agent receives reward r(s, a) and the environment transits into a new state according to transition probability P(- s, a). Meanwhile, Ç is the distribution of initial state So E S and 7 (0, 1) is the discount factor. In addition, policy r (a| 8) gives the probability of taking action a at state 8. We denote the state- and action-value functions associated with x by V + IR and Q" : S x A R. which are defined respectively as
V*(()= = (1 (1-7)--0
r(S, A.)
So So=5
Vs E,
(2.1)
Q" = (1 7) E
7 r(St, Ax) 1
So = s, Ao =
V(s,a) E ESX
(2.2)
where So <(-). A, (t). and S41
for all t 2 0. Also, we define the advantage function of policy as the difference between Q* and VT, i.e., A (x( a) Q" (x.aa) (s).. By the definitions (2.1) and (2.2), Va' and Q" are related via (Q (s. (-1s)),
VTT E., Q*
where (5-) is the inner product in RIA, Here we write B notational simplicity. Note that policy æ together with transition probability P induces a Markov
| a) 12 (s. a)) as E,, [ (s, a)) for
3

---

Published conference paper at ICLR 2020
chain over state space S. We denote by 2r the stationary state distribution of the Markov chain induced by и. We further define Sr a) = x(a s) (r((s (s) as the stationary state-action distribution over S x A. Meanwhile, policy induces state visitation measure over S and state-action visitation measure over S x A, which are denoted by Pr and on, respectively. Specifically, for all (s, S A. we define
v=(6) =1 (1 (1- Σr P.S = s),
Σ H.P(S s, A, a),
(2.3)
where So ~ ((:), A, St), and S1+1 ~ St, A,) for all 2 0. By definition, we have (x(8, ( (8) -vx(s). We define the expected total reward function J(T) by
=1 (1 (1-7)- .
Σ r Cr..r(rS, A.) (c(V Bo, [r(s,))]. Vx, 1=
(2.4)
where we write E.,, [r(ss = ((.a))ao (--)) [r(s, a)] for notational simplicity. The goal of re- inforcement learning is to find the optimal policy that maximizes J(T), which is denoted by π². When state space S is large, a popular approach is to find the maximizer of ((r) over class of parameterized policies { E B), where 8 E B is the parameter and the parameter space. In this case, we obtain the optimization problem max (TT)..
Policy Gradient Methods. Policy gradient methods maximize (TTO) using (To( These meth- ods are based on the policy gradient theorem (Sutton and Barto, 2018), which states that
( Eg., [ (s. Vo log (a
(2.5)
where nn is the state-action visitation measure defined in (2.3). Based on (2.5), (vanilla) policy gra- dient maximizes the expected total reward via gradient ascent. Specifically, we generate a sequence of policy parameters (0. (e())) via
0++1 + 0,+ (TJ(
(2.6)
where 7) > 0 is the learning rate. Meanwhile, natural policy gradient (Kakade, 2002) utilizes natural gradient ascent (Amari, 1998), which is invariant to the parameterization of policies. Specifically, let F()) be the Fisher information matrix corresponding to policy ma. which is given by
F(0)= Er.,, Vo log (a [V log (a {)] {)]
(2.7)
At each iteration, natural policy gradient performs
(2.8) where (0:( is the inverse of F(O:) and 17 is the learning rate. In practice, both Q in (2.5) and F(0) in (2.7) remain to be estimated, which yields approximations of the policy improvement steps in (2.6) and (2.8).
01+1 + 8 + 77 ( VoJ(TO).
NEURAL POLICY GRADIENT METHODS
In this section, represent ma by two-layer neural network and study neural policy gradient methods, which estimate the policy gradient and natural policy gradient using the actor-critic scheme (Konda and Tsitsiklis, 2000).
3.1 OVERPARAMETERIZAA NEURAL POLICY
We now introduce the parameterization of policies. For notational simplicity, we assume that S x A C gd with > 2. Without loss of generality, we further assume that [[(s, a) ||2 for all
(s,a) E x A. A two-layer neural network f((s, a); W, with input (s, a) and width m takes the form of
a((s.a):W.b) 1 b, (T ((s.
(3.1)

---

Published conference paper at ICLR 2020
Here ReLU: IR - I is the rectified linear unit (Rel.U) activation function, which is defined as ReLU(u) = 1 fu > 0} u. Also, [br]re(m] and W (W]] ...., )
R in (3.1) the parameters. When training the two-layer neural network, we initialize the parameters via [Winit]r ~ (0, Ia/d) and b, ~ 11)) for all r E [m]. Note that the ReLU activation function satisfies ReLU(c
ReLU(() for all > and u R. Hence, without loss of generality, we keep b, fixed at the initial parameter throughout training and only update W in the sequel. See, e.g., Allen-Zhh et al. (2018b) for detailed argument. For notational simplicity, write s((s, a); W, b) as [(( a); W) hereafter.
Using the two-layer neural network in (3.1), we define
exp F [((() a);0)]
To 8) = ExeAe exp ((ss)');0))] V(s,a) E A,
(3.2)
where ((::));;) is defined in (3.1) with 0 mmd playing the role of W. Note that Te defined in (3.2) takes the form of an energy-based policy (Haarnoja et al., 2017). With a slight abuse of terminology, call the temperature parameter and f((,, :): :) the energy function in the sequel.
In the sequel, we investigate policy gradient methods for the class of neural policies defined in (3.2). We define the feature mapping dg ([oo]] .............. (.....)) Fd - R of two-layer neural network f((::)):
br Vm
(s,
a)) [0], 00 (s, V(s,a) E Vr [m].
(3.3)
By (3.1), it holds that entiable with respect to 6, and it holds that Vaf((-.-); @u(:,)) In the following proposition, we calculate the closed forms of the policy gradient VoJ(TT) and Fisher information matrix F(0) for Te defined in (3.2).
)o. Meanwhile, f((,,)) 0) is almost everywhere differ-
Proposition 3.1 (Policy Gradient and Fisher Information Matrix). For Ta defined in (3.2), we have
VoJ(TT)) = Tooo [ot, (s (oo(s,a) - Exo (do(s,a')))
(3.4)
F(0) = -2. (0o(s..)) E.d [0o(s, d')) (00(s, - E.. [oo(s, '
(3.5)
where : is the feature mapping defined in (3.3). T is the temperature parameter, and Txa is the state-action visitation measure defined in (2.3). Here we write E., oe (s, a')] = Ba' ( a')] for notational simplicity.
(s)
Proof. See 1H.1 for detailed proof.
Since the action-vales value function QTa in (3.4) is unknown, to obtain the policy gradient, we use another two-layer neural network track the action-value function of policy wy. Specifically, we use two-layer neural network (:-). = f((,.));a defined in (3.1) to represent the action-vale value function Q where w plays the same role as W in (3.1). Such an approach is known as the actor- critic scheme (Konda and Tsitsiklis, 2000). We call and Q. the actor and critic, respectively. We highlight that in the overparameterized regime where the width of two-layer neural networks m is large, shared architecture and random initialization between the actor Qu and the energy function of critic Ta ensures approximate compatible function approximations. See BB for details.
3.2 NEURAL POLICY GRADIENT METHODS
Now we present neural policy gradient and neural natural policy gradient. Following the actor-critic scheme, they generate sequence of policies ( heir+1) and action-value functions (Qw. hee(r)-
3.2.1 ACTOR UPDATE
As introduced in $2, we aim to solve the optimization problem maXges J ((TO) iteratively via gradient-based methods, where B is the parameter space. We set B {ar Rmnd ||a Wint S R), where R > and Wi is the initial parameter defined in $3.1. For all E [T]. , let 0g be the
5

---

Published conference paper at ICLR 2020
policy parameter at the i-th iteration. For notational simplicity, in the sequel, we denote by and the state-action visitation measure one and the stationary state-action distribution STe, respectively, which are defined in $2. Similarly, we write V4 Vaa, and 2: 2ma, To update fs. we set
0,41 - 10, + G(OD) (Fo,)))
(3.6)
where we define Igg Rmd - B as the projection operator onto the parameter space B C RRmd__ Here G(Ø,)) IR. md is matrix specific to each algorithm. Specifically, we have G(0,) md for policy gradient and G(O+) (F(O.))~ for natural policy gradient, where F(O.) is the Fisher information matrix in (3.5). Meanwhile, yf is the learning rate and (Tn( is an estimator of (Te( which takes the form of
(
Σ Qui (sc, az) Va log ne. (az [8)-
(3.7)
Here Ti is the temperature parameter of TT,,, {(s;, at) [8] is sampled from the state-action visita- tion measure o; corresponding to the current policy TØ,, and B the batch size. Also, Qw, is the critic obtained by Algorithm 2. Here we omit the dependency of (To) on w; for notational simplicity. See &C for the sampling from visitation measures.
Inverting Fisher Information Matrix. Recall that G(0:)) is the inverse of the Fisher information matrix used in natural policy gradient. In the overparameterizee regime, inverting an estimator F(0.) of (O,)) can be infeasible as F(O.) is high-dimensional matrix, which is possibly not invertible. To resolve this issue, we estimate the natural policy gradient G(O,). VaJ(TT)) by solving
min aEB
[0:))
(To,)))
(3.8)
where (TT,) is defined in (3.7), 7; is the temperature parameter in na., and B is the parameter space. Meanwhile, F(O:) is an unbiased estimator of F(O:) based on {(82, (z) (e) sampled from og which is defined as
B (0
F(O.)
T. B
Exo, [do, (se, d')l) (0e, (se, az) - Exo [0e, (sts de)l) (3.9)
where ag To, (:) and Φo, defined in (3.3) with 0,. The actor update of neural natural policy gradient takes the form of
T++1 0 + Ti 0, + 17 argmin [F(0)) ((0.)--rr, -a VeJ Ml.. (3.10)
T++1 + T, +1,
aEB
where
arbitrary minimizer of (3.8) if it is not unique. Note that we also update the temperature parameter by Ti+1 < T, + 17, which ensures 0;41 E B. It is worth mentioning that up minor modifications, our analysis allows for approximately solving (3.8), which is the common practice of approximate second-order optimization (Martens and Grosse, 2015; Wu et al., 2017).
To summarize, the i-th iteration, neural policy gradient obtains 0,+1 via projected gradient ascent using ) defined in (3.7). Meanwhile, neural natural policy gradient solves (3.8) and obtains 0:+1 according to (3.10).
3.2.2 CRITIC UPDATE
To obtain (TT),, it remains to obtain the critic Qu, in (3.7). For any policy म, the action-value function Q the unique solution to the Bellman equation Q T (Sutton and Barto, 2018). Here T is the Bellman operator that takes the form of
a)) = [[(1- -7) r(s, + Q(s's a')], V(s,a) SxA.
where ~ P(- a) and a' ~ a(. 1')) Correspondingly, we aim to solve the following optimiza- tion problem
Wi - argmin I3 (Qu((s) -TTh
(3.11)

---

Published conference paper at ICLR 2020
where and T are the stationary state-action distribution and the Bellman operator associated with wo,, respectively, and B is the parameter space. We adopt neural temporal-different (TD) studied in Cai et al. (2019), which solves the optimization problem in (3.11) via stochastic semigradient descent (Sutton, 1988). Specifically, an iteration of neural TD takes the form of
learning
w(t + 1/2) - w(t) - VID (Qwtt) -
(1-1) r(s,a) a) - Quitt) Vuluee)(s,)) (3.12) w(t + 1) - argmin ||a w(++
+ 11/)]11,
(3.13)
aEB
where (s.a) (') P(. a). a' ~ [-||s'), and 7TD is the learning rate of neural TD. Here (3.12) is the stochastic semigradient step, and (3.13) projects the parameter obtained by (3.12) back to the parameter space B. Mcanwhile, the state-action pairs in (3.12) are sampled from the stationary state-action distribution S., which is achieved by sampling from the Markov chain induced by To, until it mixes. See Algorithm 2 in 3F for details. Finally, combining the actor updates and the critic update described (3.6), (3. 10), and (3.11), respectively, we obtain neural policy gradient and natural policy gradient, which are described in Algorithm 1.
Algorithm 1 Neural Policy Gradient Methods
Require: Number of iterations T, number of TD iterations TTD, learning rate v), learning rate yrD of neural TD, temperature parameters {Ti)ke(T+1)) batch size B.
1: Initialization: Initialize b, Unif(1 -1, 1}) and [Wmat]r ~ N(0, for all r E [m]] Set
B < {a E Rmdd ||a Wmallp R. and 01 Winit.
2: for E [T] do
3: Update wi using Algorithm 2 with To, the input, (0) W and {br Jremm as the initialization, TTD as the number of iterations, and mrDD as the learning rate.
4: Sample {(s2, az) bee from the visitation measure and estimate VoJ(To) and F(0.) using (3.7) and (3.9), respectively.
5: If using policy gradient, update 0:+1 by
0.41 < (0, + VaJ(T))))
If using natural policy gradient, update 0:+1 and T++1 by
Ti+1 < + n.
Te+1
O.41 + Ti 0; + argmin aEB
((0,) a a- T VoJ(Ta))
6: end for
7: Output: (merrrat
MAIN RESULTS
In this section, we establish the global optimality and convergence for neural policy gradient meth- ods. Hereafter, we assume that the absolute value of the reward function r is upper bounded by an absolute constant Qiax 0. As a result, we obtain from (2.1) and (2.2) that V* a) < Qmax+ a)) < Q @axx and (A" a)l < 2Q for all and (s, a) E S x A. In what follows, we show that neural policy gradient converges to stationary point of J(Te) with respect to 9 at a sub- linear rate. We further characterize the geometry of J (TT) and establish the global optimality of the obtained stationary point. We defer the global optimality and convergence of neural natural policy gradient to SA.
In the sequel, we study the convergence of neural policy gradient, i.e., Algorithm 1 with (3.6) as the actor update, where G(Ø) Imdd- In what follows, lay out regularity condition the action-value function Q".
Assumption 4.1 (Action- Value Function Class). We define
FR. f(s,a) = fo(s,a) + 1[w
(s, (s, > 0} ((a))((w)dp(w)) [[g])/)()))(((((<<<>><)))>>))))) S
( SRIVA].
7

---

Published conference paper at ICLR 2020
where 1a: I2d + IR is the density function of the Gaussian distribution N(, Ia/d), fo(::") f((,,) :) Win Winit) the two-layer neural network corresponding to the initial parameter Winits and 6: RR + Re together with fo parameterizes the element of FR,c0- We assume that Q" E FRoo for all π.
Assumption 4.1 a mild regularity condition on Q", FR.sc captures sufficiently general family of functions, which constitute a subset of the reproducing kernel Hilbert space (RKHS) induced by the random feature 1(w" 1(wT(s, a) > 0} (s, a) with N(, Ia/d (Rahimi and Recht, 2008; 2009) up to the shift of Jo- Similar assumptions are imposed in the analysis of batch reinforcement learning in RKHS (Farahmand et al., 2016).
In what follows, we lay out a regularity condition on the state visitation measure V/= and the station- ary state distribution 0x-
Assumption 4.2 (Regularity Condition on V and 2r). Let and सr be two arbitrary policies. We assume that there exists an absolute constant > 0 such that
E
1 ( T (s, a)l s u} S c. u/llv/l [yllz,
11 (s, [s,a)]= S w} c u/llllla EyeRS, Vu 0. Here the expectations are taken over the joint distributions 7(-1) (+) and (-1--) (x(-) over S A, respectively.
Eg
Assumption 4.2 essentially imposes regularity condition on the Markov transition kernel P of the MDP as P determines V- and @- for all æ. Such a regularity condition holds both V= and @r have upper-bounded density functions for all
After introducing these regularity conditions, we present the following proposition adapted from Cai et al. (2019), which characterizes the convergence of neural TD for the critic update.
Proposition 4.3 (Convergence of Critic Update). We set WTD = min (1 7)/8, 1/vTrD} in Algorithm 1. Let Qu, be the output of the i-th critic update Line of Algorithm which is an estimator of QTe. obtained by Algorithm 2 with TTD iterations. Under Assumptions 4.1 and 4.2, it holds for TTD = 2(m) that
Emii [1|Q., Q [. O(R2 m + R5/2 m 11/1),
(4.1)
where is the stationary state-action distribution corresponding to Te, Here the expectation is taken over the random initialization.
Proof. See 1 for a detailed proof.
Cai et al. (2019) show that the error of the critic update consists of two parts, namely the approxima- tion еттоr of two-layer neural networks and the algorithmic сπтог of neural TD. The former decays as the width m grows, while the latter decays as the number of neural TD iterations TTD in Algorithm grows. By setting TTD 2(m), the algorithmic error in (4.1) of Proposition 4.3 is dominated by the approximation error. contrast with Cai et al. (2019), we obtain a more refined convergence char- acterization under the more restrictive assumption that Q" E FR Specifically, such restriction allows us to obtain the upper bound the mean squared error in (4.1) of Proposition 4.3.
It now remains to establish the convergence of the actor update, which involves the estimator (o.()o))) of the policy gradient VoJ(TT, based on {(se, (()))))) We introduce the following regularity condition on the variance of (Tr.)
Assumption 4.4 (Variance Upper Bound). Recall that o, is the state-action visitation measure cor- responding to Te, for all i E [T'. Let &; = ( V ( ]]. where (TJ( defined in (3.7). We assume that there exists absolute constant og 0 such that E Eills I 7Ý ooo / for all i [T]. Here the expectations are taken over o; given 0 and w,.
Assumption 4.4 is mild regularity condition. Such regularity condition holds if the Markov chain that generates {(e,, ) hee[B] mixes sufficiently fast and Qw, a) with (s, a) ~ a; have upper

---

Published conference paper at ICLR 2020
bounded second moments for all i E [T]. Zhang et al. (2019) verify that under certain regularity conditions, similar unbiased policy gradient estimators have almost surely upper bounded norms, which implies Assumption 4.4, Similar regularity conditions are also imposed in the analysis of policy gradient methods by Xu et al. (2019a;b).
In what follows, we impose regularity condition on the discrepancy between the state-action visi- tation measure and the stationary state-action distribution corresponding to the same policy.
Assumption 4.5 (Regularity Condition on 0; and 4)). We assume that there exists an absolute con- stant > 0 such that
do: ( ds;
(
1/2 ""3"
(8,
(4.2)
Here dog//s; is the Radon-Nikodym derivative of o, with respect to St-
We highlight that if the MDP is initialized the stationary distribution S, the atatenaction visitation measure o, is the same as ç, Meanwhile, if the induced Markov state-action chain mixes sufficiently fast, such an assumption also holds. A similar regularity condition is imposed by Scherrer (2013), which assumes that the -nom of do:/ds; is upper bounded, whereas we only assume that its L L2-norm is upper bounded.
Meanwhile, we impose the following regularity condition on the smoothness of the expected total reward (TT) with respect 0.
Assumption 4.6 (Lipschitz Continuous Policy Gradient). We assume that VoJ((TO) is L-Lipschitz continuous with respect to 8, where L > is an absolute constant.
Such an assumption holds when the transition probability P(- s, a) and the reward function are both Lipschitz continuous with respect to their inputs (Pirotta et al., 2015). Also, Karimi et al. (2019); Zhang et al. (2019); Xu et (2019b) Agarwal et al. (2019) verify the Lipschitz continuity of the policy gradient under certain regularity conditions.
Note that restrict 9 to the parameter space B. Here we call θ B stationary point of J(Te) holds for all 0 E B that (rg( generated by neural policy gradient converges to stationary point at sublinear rate.
0) S O. We now show that the sequence (0:)<e(T+1)
Theorem 4.7 (Convergence to Stationary Point). We set T; 1, 7 1/vT, MTD min((1
7)/8, 1/VTTD) TTD I(m), and B {a: ||a Winit 2 Rİ by Algorithm 1, where the actor
update is given in (3.6) with G(0) = Imd- For all E [T). we define
.ー [LB + VoJ(TT))) 0.| E Rdd
(4.3)
where Hs: Rdd B is the projection operator onto C Rmd,, Under the assumptions of Proposi- tion 4.3 and Assumptions 4.4-4.6, for T 2 41,2 we have
min E [1p: < 8/vT E[J(Ter))) J + So E
where k is defined in (4.2) of Assumption 4.2 and EQ (T) = O m 1/4 11/4, 1/2 + R9/4 m- 1/8. T1/2). Here the expectations are taken over all the randomness.
Proof. See $D.1 for a detailed proof.
By Theorem 4.7 with = 2(7 R28) and B 2(VT), we obtain minegr [|||e O(I/VT). Therefore, when the two-layer neural networks are sufficiently wide and the batch size B is sufficiently large, neural policy gradient achieves a 1/vT-rate of convergence. Moreover, Ps defined in (4.3) is known as the gradient mapping at 6; (Nesterov, 2018). It is known that θ E B is stationary point if and only if the gradient mapping 0 is zero vector. Therefore, (a subsequence stationary point 0 B min4e/r E[[le:|[0] converges zero. In other words, neural policy gradient converges to a stationary point at a 1/VT-rate. Also, we remark
of) {0.) her-- converges

---

Published conference paper at ICLR 2020
that the projection operator in the actor update is adopted only for the purpose of simplicity, which can be removed with more refined analysis. Moreover, the projection free version of neural policy gradient converges to stationary point at similar sublinear rate. See &G for details.
We now characterize the global optimality of the obtained stationary point 0. To this end, we com- pare the expected total reward of Ta with that of the global optimum x² of J(r).
Theorem 4.8 (Global Optimality Stationary Point). Let Ø E B stationary point of J(me). holds that
(1-7)-(J(T)) - J(Ta)) S 2Qmax inf ||ua(;)) 2g( 0llong AEB
where Qmax the upper bound |r| and ug: S x A + defined as
ug(s, a) = doz (s,a)
dvz' (s) - og(5.a) E(x.A)
(4.4)
dong
dv
Here do /do and dv /dvng are the Radon-Nikodym derivatives, and || llog is the Lo(orr)) norm.
Proof. See $D.2 for a detailed proof.
To understand Theorem 4.8, we highlight that for 8, 0 E B, the function -T is well approxi- mated by the overparameterized two-layer neural network -); See Corollary E.4 for details. Therefore, the global optimality of Ta depends on the error of approximating "a with an overparam- eterized two-layer neural network. Specifically, if ug is well approximated by an overparameterized two-layer neural network, then Tg is nearly as optimal as x. In the following corollary, we formally establish a sufficient condition for any stationary point Ō to globally optimal.
Theorem 4.9 (Global Optimality of Stationary Point). Let 0 B be stationary point of J(xo)- We assume that "g E FR.o in Theorem 4.8. Under Assumption 4.2, holds that
(1 7) Binit [J(m²) )- J(ma)
1/4).
More generally, without assuming ug FR, in Theorem 4.8, under Assumption 4.2, it holds that
(1 71 Einin [ - [TT)]] = O m -nn)1//4--- + Einic [[][] ug ugl vgllo-z]
Here the expectations are taken over the random initialization, and IR is the projection operator onto FR, with respect to the L2(0x²) (=xx))-noom) -norm.
Proof. See HH. for a detailed proof.
By Theorem 4.9, stationary point 0 is globally optimal if ug E FR, and m + cc. Moreover, following from the definition of p; in (4.3) of Theorem 4.7, we obtain that
VoJ(TO,) 0,) < (2R + 2n Qmax) ||
(4.5)
See $H.3 for a detailed proof of (4.5). Since || = implies that 0, a stationary point, the right-hand side of (4.5) quantifies the deviation of 0, from a stationary point 0. Following similar analysis to $D.2 and H.. if ug, FR.c for all i [T], we obtain that
(1 1 min [(T(T)) - (TTT.) = O . m 1/4) + (2R+ 2n Qmax) min E [[ E
[E[T]
Thus, by invoking Theorem 4.7, it holds for sufficiently large m and B that the expected total reward ( converges to the global optimum J(T") at a 1/4 rate.
10

---

Published conference paper at ICLR 2020
REFERENCES
Agarwal, A., Kakade, S. M., Lee, J. D. and Mahajan, G. (2019). Optimality and approximation with
policy gradient methods in Markov decision processes. arXiv preprini 00261.
Allen-Zhu, Z., Li, Y. and Liang, Y. (2018a). Learning and generalization in overparameterized neu- ral networks, going beyond two layers. arXiv preprint 18X1v:1811.04911
Allen-Zhu, Z., Li, Y. and Song, Z. (20186). A convergence theory for deep learning via over- parameterization. arXiv preprint 1811vv98
Amari, S.-I. (1998). Natural gradient works efficiently in learning. Neural Computation. 10 251- 276.
Antos, A., Szepesvári, C. and Munos, R. (2008). Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 89-129.
Arora, S., Du, S., Hu, W., Li, Z. and Wang, R. (2019). Fine-grained analysis of optimiza- tion and generalization for overparameterized two-layer neural networks. arXiv preprint TrXiv:9901.0858.
Barron, A. R. (1994). Approximation and estimation bounds for artificial neural networks. Machine Learning, 14 115-133.
Baxter, J. and Bartlett, P. L. (2000). Direct gradient-based reinforcement learning, In International Symposium on Circuits and Systems.
Bhandari, J. and Russo, D. (2019). Global optimality guarantees for policy gradient methods. arXiv preprint 19Xx:19900601766.
Borkar, V. S. (2009). Stochastic Approximation: A Dynamical Systems Viewpoint, vol. 48. Springer.
Bu, J., Mesbahi, A., Fazel, M. and Mesbahi, M. (2019). LQR through the lens of first order methods: Discrete-time case. arXiv preprint 1907:199
Cai, Q., Yang, Z., Lee, J. and Wang, Z. (2019). Neural temporal-differene learning converges to global optima. arXiv preprint arXiv: 10027.
Cao, Y. and Gu, Q. (2019a). Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint 13Xiv:1905.13210.
Cao, Y. and Gu, Q. (2019b). A generalization theory of gradient descent for learning over- parameterized deep ReLU networks. arXiv preprint
Castro, D. D. and Meir, R. (2010). convergent online single time scale actor critic algorithm. Journal of Machine Learning Research, 11 367-410.
Chen, J. and Jiang, N. (2019). Informatiin-theorrtiic considerations batch reinforcement learning. arXiv preprint arXiv:1905.00330
Chizat, L. and Bach, F. (2018). note on lazy training in supervised differentiable programming. arXiv preprint 11X.v:18/2.00996.
Daniely, A. (2017), SGD learns the conjugate kernel class of the network. In Advances in Neural Information Processing Systems.
Du, S. S.. Lee, J. D., Li, H., Wang, deep neural networks. arXiv preprint
L. and Zhai, X. (2018a). Gradient descent finds global minima
Du, S. S., Zhai, X., Poczos, B. and Singh, A. (2018b). Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiv:1810.02055

---

Published conference paper at ICLR 2020
Duan, Y., Chen, X., Houthooft, R., Schulman, J. and Abbeel, P. (2016). Benchmarking deep rein- forcement learning for continuous control. In International Conference on Machine Learning.
Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V.,
Harley, T., Dunning, et al. (2018). IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. arXiv preprint
Fan, J., Ma, C. and Zhong, Y. (2019). A selective overview of deep learning. arXiv preprint arXiv: 1rXiv:994.05552
Farahmand, A.- Ghavamzadeh, M., Szepesvári, C. and Mannor, S. (2016). Regularized policy
iteration with nonparametric function spaces. Journal of Machine Learning Research, 17 4809- 4874.
Farahmand, A.m Szepesvári, and Munos, (2010). Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems.
Fazel, M., Ge, R., Kakade, S. M. and Mesbahi, M. (2018). Global convergence of policy gradient methods for the linear quadratic regulator. arXiv preprint arXiv: N0t::8801000033
Funahashi, K.-I. (1989). On the approximate realization continuous mappings by neural networks. Neural Networky, 2 183-192.
Haarnoja, a. T., Tang, H., Abbeel, and Levine, S. (2017). Reinforcement learning with deep energy- based policies. In International Conference Machine Learning.
Jacot, A., Gabriel, F. and Hongler, C. (2018). Neural tangent kernel: Convergence and generaliza- tion in neural networks. In Advances in Neural Information Processing Systems.
Johnson, R. and Zhang, T. (2013). Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems.
Kakade, S. and Langford, J. (2002). Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning.
Kakade, S. M. (2002). A natural policy gradient. In Advances in Neural Information Processing Systems.
Karimi, B., Miasojedow, B., Moulines, E. and Wai, H.-T. (2019). Non-asymptotic analysis of biased stochastic approximation scheme. arXiv preprint 1rXiv:1902.000
Klusowski, J. M. and Barron, A. R. (2016). Risk bounds for high-dimensional ridge function com- binations including neural networks. arXiv preprint 1607
Konda, V. (2002). Actor-Critic Algorithms. Ph.D. thesis, Massachusetts Institute of Technology.
Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. In Advances in Neural Information Processing Systems.
Kushner, H. and Yin. G. G. (2003). Stochastic Approximation and Recursive Algorithms and Appli- cations, vol. 35. Springer Science & Business Media.
Lazaric, A., Ghavamzadeh, M. and Munos, R. (2016). Analysis of classification-based policy itera- tion algorithms. Journal of Machine Learning Research, 17 583-612.
Lee, J., Bahri, Y., Novak, R., Schoenholz, S. S., Pennington, J. and Sohl-Dickstein, J. (2018). Deep neural networks as Gaussian processes. In International Conference on Learning Representa- tions.
Lee, J.. Xiao, L., Schoenholz, S. S., Bahri, Y., Sohl-Dickstein, J. and Pemnington, J. (2019). Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint orXiv:/902.04
12

---

Published conference paper at ICLR 2020
Li, Y. (2017). Deep reinforcement learning: An overview. arXiv preprint arXiv: 1701.07777
Li, and Liang, Y. (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems.
Liu, B., Cai, Q. Yang. Z. and Wang, Z. (2019). Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv:
Malik, D., Pananjady, A., Bhatia, K., Khamaru, K., Bartlett, P. L. and Wainwright, M. (2018). Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. arXiv preprint arXiv: 08305.
Martens, and Grosse, (2015). Optimizing neural networks with kronecker-factored approxi- mate curvature. In International Conference on Machine Learning.
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap. T., Harley, T., Silver, D. and Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning. In International Conference on Machine Leurning.
Munos, R. and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. Journal of Ma- chine Learning Research, $15-857.
Nesterov, Y. (2018). Lectures on Convex Optimization. Springer.
Pan, X. and Srikumar, V. (2016). Expressiveness of rectifier networks. In International Conference Machine Learning.
Papini, M., Binaghi, D., Canonaco, G., Pirotta, M. and Restelli, M. (2018). Stochastic variance- reduced policy gradient. arXiv preprint arXiv: 08.18
Peters, J. and Schaal, S. (2006). Policy gradient methods for robotics. In International Conference on Intelligent Robots and Systems.
Peters, J. and Schaal, S. (2008). Natural actor-critic. Neurocomputinng 71 1180-1190.
Pirotta, M., Restelli, M. and Bascetta, L. (2015). Policy gradient in Lipschitz Markov decision pro- cesses. Machine Learning, 100 255-283.
Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley Sons.
Rahimi, A. and Recht, B. (2008). Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems.
Rahimi, A. and Recht, B. (2009). Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances Neural Information Processing Systems.
Scherrer, B. (2013). On the performance bounds of some policy search dynamic programming algorithms. arXiv preprint
Scherrer, B., Ghavamzadeh, M., Gabillon, V., Lesner, B. and Geist, M. (2015). Approximate mod- ified policy iteration and its application to the game of Tetris. Journal of Machine Learning Research, 16 1629-1676.
Schulman, J., Levine, S., Abbeel, P., Jordan, M. and Moritz, P. (2015). Trust region policy optimiza- tion. In International Conference on Machine Learning.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A. and Klimov, O. (2017). Proximal policy opti- mization algorithms. arXiv preprint arXiv:1707.0632
Shen, Z.,, Ribeiro, A., Hassani, H., Qian, H. and Mi, C. (2019). Hessian aided policy gradient. In International Conference on Machine Learning.
13

---

Published conference paper at ICLR 2020
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.,, Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M. al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529 484.
Silver, D., Schrittwessrr, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A. et al. (2017). Mastering the game of Go without human knowl- edge. Nature, 550 354.
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 9-44.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT press.
Sutton, R. S., McAllester, D. A., Singh, S. P. and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Pro- cessing Systems.
Szepesvári, C. and Munos, R. (2005). Finite time bounds for sampling based fitted value iteration. In International Conference on Machine Learning-
Tsitsiklis, J. N. and Van Roy, B. (1997). Analysis of cemporal-difffrrent learning with function approximation. In Advances in Neural Information Processing Systems.
Tu, S. and Recht, B. (2018). The gap between model-based and model-free methods the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv: (rXx::8//2.03663
Handel, R. (2014). Probability in High Dimension. Princeton University.
Vinyals, O., Babuschkin, I,, Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W. M., Dudzik, A., Huang, A., Georgiev, P., Powell, R., Ewalds, T., Horgan, D., Kroiss, M., Danihelka, I., Agapiou, J., Oh, J., Dalibard, V., Choi, D., Sifre, L., Sulsky, Y., Vezhnevets, S., Molloy, J., Cai, T., Budden, D., Paine, T., Gulcehre, C., Wang, Z., Pfaff, T., Pohlen, T., Wu, Y., Yogatama, D., Cohen, J., McKinney, K., Smith. O., Schaul, T., Lillicrap, T., Apps, C., Kavukcuoglu, K.. Hassabis. D. and Silver, (2019). AlphaStar: Master- ing the Real-Time Strategy Game StarCraft II. https: : /dwppmieemmmeee//////// nd. com/blog/ a -agr-mmtttteri---el--teeeee
satpra--am-ssttrrraaeee starcraft-11/.
Wagner, P. (2011). A reinterpretation of the policy oscillation phenomenon in approximate policy iteration. In Advances Neural Information Processing Systems.
Wagner, P. (2013). Optimistic policy iteration and natural actor-critic: A unifying view and a non- optimality result. Advances in Neural Information Processing Systems.
Wang, W. Y., Li, and He, X. (2018). Deep reinforcement learning for NLP. In Association for Computational Linguistics.
Williams, R. J. (1992). Simple statistical follleent--loowinggg algorithms for connectionist reinforce- ment learning. Machine Learning, 8 256-256.
Wu, I.,, Ma, C. and Weinan, F. (2018). How SGD selects the global minima in over-parameterized learning: A dynamical stability perspective. In Advances in Neural Information Processing Sys- tems.
Wu, Y., Mansimov, E., Grosse, R. B., Liao, S. and Ba, J. (2017). Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation. In Advances in Neural Information Processing Systems.
Xu, P., Gao, and Gu, Q. (2019a). An improved convergence analysis of stochastic variance- reduced policy gradient. arXiv preprint arXiv: /2615.
Xu, P., Gao, and Gu, Q (2019b). Sample efficient policy gradient methods with recursive variance reduction, arXiv preprint arXiv: wwXivv/9090086000
14

---

Published conference paper at ICLR 2020
Yang, Z., Chen, Y., Hong. M. and Wang, Z. (2019a). On the global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. arXiv preprint (xXiv:907..0222
Yang, Z., Xie, Y. and Wang, Z. (2019h). A theoretical analysis of deep Q-learning. arXiv preprint
Zhang, K., Koppel, A.. Zhu, H. and Başar, T. (2019). Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprint 1rXiv:1906.08888..
Zou, D., Cao, Y., Zhou, D. and Gu, Q. (2018). Stochastic gradient descent optimizes over- parameterized deep ReLU networks. arXiv preprint arXiv: 1.1108888
15

---

Published conference paper at ICLR 2020
A NEURAL NATURAL POLICY GRADIENT
In the sequel, we study the convergence of neural natural policy gradient. As shown in Algorithm 1, neural natural policy gradient uses neural TD for policy evaluation and updates the actor using (3.10), where 0g and Tr in (3.2) are both updated. To analyze the critic update, we impose As- sumptions 4.1 and 4.2, which guarantee that Proposition 4.3 holds. Meanwhile, analyze the actor update, we impose the following regularity conditions.
In parallel to Assumption 4.4, we lay out the following regularity condition the variance of the estimators of the policy gradient and the Fisher information matrix.
Assumption A.1 (Variance Upper Bound). Let B {a Rndd ||a Winit ll S R), where Winit the initial parameter. We define
8, (Ti+1 0.t1 - Ti -.,)/n argmin [IF(()) a Ti (F. Vi E [T).
aEB
where (TT.) and (0.)) are defined in (3.7) and (3.9), respectively, With slight abuse of notation, for all i E [T), we define the function & Rmn - R mdd as
(a) F(0.)
( - E ((.) a- T. VeJ(Ta))
We assume that there exists an absolute constant 0g > 0 such that
61 S ने. oe/B, E ((I)( S T .ogBBB/BBB Vie
Here the expectations are taken over o; given 0g and w;.
Next, we lay out regularity condition on the visitation measures and the stationary distribu- tions St. di. respectively.
Assumption A.2 (Upper Bounded Concentrability Coefficient). We denote by n. and a, the state and state-action visitation measures corresponding the global optimum n² For all [T]. we define the concentrability coefficients si, Vi. s,, and viद
1/2
1/2
jp: Eo. (do./do;))
th = Eng
1/ (Eg, [ddo//<s))) 1/2
V/ = [Ee, [dv. /de:) 1/2
(A.1) where do./do,, /v./dv,, do./ds;, and dv, /dg; are the Radon-Nikodym derivatives. We assume that the concentrability coefficients defined in (A.1) are uniformly upper bounded by an absolute constant cu > 0.
The regularity condition on upper bounded concentrability coefficients is commonly imposed in the reinforcement learning literature and is standard for theoretical analysis (Szepesvári and Munos, 2005; Munos and Szepesvári, 2008; Antos et al., 2008; Lazaric al., 2016; Farahmand et al., 2010; 2016; Scherrer, 2013; Scherrer et al., 2015; Yang et al., 2019b; Chen and Jiang, 2019).
Finally, we introduce the following regularity condition the initial parameter Wintt in Algorithm 1.
Assumption A.3 (Upper Bounded Moment Random Initialization). Let Φo(8, a) E Rend be the feature mapping defined in (3.3) with 0 Wintt We assume that there exists an absolute constant M > 0 such that
Einit
sup (A
[f((s, a); Winit)
Emn sup (s.a))SXA
(o((s Winit! 12
s M
Here the expectations are taken over the random initialization.
Note that + oc, the two-layer neural network Φu(s, a) Wiit converges Gaussian pro- cess indexed by (s, a.) (Lee et al., 2018), which lies in a compact subset of Rdd known that under certain regularity conditions, the maximum of Gaussian process sub-Gaussian random variable (van Handel, 2014). Therefore, the regularity condition that max(...) (60(s, a) Wint has finite second moment is mild.
compact index set
We now establish the global optimality and rate of convergence of neural natural policy gradient.
16

---

Published conference paper at ICLR 2020
Theorem A.4 (Global Optimality and Convergence). We set 7) = 1/VT. TTD min
7)/8, L/VTTD TTD = lim)), Ti = (i 1) 1)-77 and B = {a : ||a - Winitlla S RJ in Algo-
rithm 1, where the actor update is given (3.10). Under the assumptions of Proposition 4.3 and Assumptions A.1-A.3, we have
min B[J(=))- J((o))] - log |A| 912 + M <E[T]
T
(T))
(A.2)
(1-7) vT
(1 (1-7)
1=1
Here M is defined in Assumption A.3 and (T) satisfies
((T) = vBco R1/2 - B)1//
(A.3)
+ ((T41 1//22, + 1) R2/2 m m114 + +R5/4 m7 1/8) + +EQ.
(b)
(c)
where co is defined in Assumption A.2 and EQ. co O(R3/2 2, m-1/4 4 R5/4 . m m=//8). Here the
expectation is taken over all the randomness.
Proof. See $D.3 for a detailed proof.
As shown in (A.2) of Theorem A.4, the optimality gap min -[J is upper bounded by two terms. Intuitively, the first D(I/VT) term characterizes the convergence of neural natural policy gradient as m, B - Meanwhile, the second term aggregates the errors incurred by both the actor update and the critic update due to finite m and B. Specifically, in (A.3) of Theorem A.4, (a) corresponds to the estimation error of F()) and (TT) due to the finite batch size B, which vanishes B + oc. Also, (b) corresponds the incompatibility between the parameterizations of the actor and critic. As introduced in 13.1, we use shared architecture and random initialization to ensure approximately compatible funetion approximations. In particular, (b) vanishes as + oo. Meanwhile, (c) corresponds to the policy evaluation error, i.e., the error of approximating QTa using Qui- As shown in Proposition 4.3, such an error is sufficiently small when both m and TTD are sufficiently large. To conclude, when m, B, and TTD are sufficiently large, the expected total reward of (a subsequence of) bejrr+) obtained from the neural natural policy gradient converges to the global optimum J(x²) at a 1/VT-ratee Formally, we have the following corollary. Corollary A.5 (Global Optimality and Convergence). Under the same assumptions of Theorem A.4, it holds for m Q(R220 76) and B = Q(R2 _
of) that
min [[((T') - ((TA.)] - =o E
log |A|
VT
Here the expectation is taken over all the randomness.
Proof. See $H.4 for detailed proof.
Corollary A.5 establishes both the global optimality and rate of convergence of neural natural policy gradient. Combining Theorem 4.7 and Corollary A.5, we conclude that when we use overparam- eterized two-layer neural networks, both neural policy gradient and neural natural policy gradient converge at 1/vT-rates. In comparison, when m and B are sufficiently large, neural policy gra- dient is only shown to converge to a stationary point under the additional regularity condition that (oJ(TT) is Lipschitz continuous (Assumption 4.6). Moreover, by Theorem 4.8, the global optimal- ity of such stationary point hinges on the representation power of the overparameterized two-layer neural network. In contrast, neural natural policy gradient is shown to attain the global optimum when both m and B are sufficiently large without additional regularity conditions such as Assump- tion 4.6, which reveals the benefit of incorporating more sophisticated optimization techniques to reinforcement learning. A similar phenomenon is observed in the LQR setting (Fazel et al., 2018; Malik al., 2018; Tu and Recht, 2018), where natural policy gradient enjoys improved rate of convergence.
17

---

Published conference paper at ICLR 2020
In recent work, Liu et al. (2019) study the global optimality and rates of convergence of neural proximal policy optimization (PPO) and trust region policy optimization (TRPO) (Schulman al., 2013; 2017). Although Liu al. (2019) establish similar 1/vT-rate of convergence the global optimum, neural PPO is different from neural natural policy gradient, as it requires solving sub- problem of policy improvement neural network using multiple stochastic gradient steps in the parameter space. In contrast, neural natural policy gradient only requires single stochastic natural gradient step in the parameter space, which makes the analysis even more challenging.
the functional space by fitting an overparameterized two-layer
B SHARED INITIALIZATION AND COMPATIBLE FUNCTION APPROXIMATION.
Sutton et al. (2000) introduce the notion of compatible function approximations. Specifically, the action-value function Qw compatible with Te if we have V. (8, a) Vy log aa(a s) for all (s,a) E S A, where (s, responding to Qw. Compatible function approximations enable us to construct unbiased estimators of the policy gradient, which are essential for the optimality and convergence of policy gradient methods (Konda and Tsitsiklis, 2000; Sutton et al., 2000; Kakade, 2002; Peters and Schaal, 2008; Wagner, 2011; 2013).
(s, a) (s, TT(. {)) is the advantage function cor-
To approximately obtain compatible function approximations when both the actor and critic are represented by neural networks, we use a shared architecture between the action-value function Q and the energy function of næ, and initialize Qw and To with the same parameter Winit. where [Wiml= (0, /d) for all r E [m]] We show that in the overparameterized regime where m is large, the shared architecture and random initialization ensure Q2 to be approximately compatible with Te in the following sense. We define do = ([oo]T ( TR. - Rmnd as the centered feature mapping corresponding to the initialization, which takes the form of
br Vm 1f ( [W > 0} (s.
[0.l-(8, a)
(B.1)
a(sssa)) (Wint) > 0} 00000000000) (6,0)): (ss,a) Vm
br
E
where Wint is the initialization shared by both the actor and critic, and we omit the dependency on for notational simplicity. Similarly, define for all (s, a) E S x A the following centered feature mappings,
a=(+,a) = Φ0( - Ex, [0o(s,
(x, = ou (8, - ETD (s,
(B.2)
Here de (s. a) and (s, a) are the feature mappings defined in (3.3), which correspond and w, respectively. By (3.1), we have
as, = (s, a) E., (s. = as
V la = (s, (B.3)
which holds almost everywhere for E Rdnd As shown in Corollary E.3 in ŞE, when the width m is sufficiently large, in policy gradient methods, both og and の_ are well approximated by oo defined in (B.1). Therefore, by (B.3), conclude that in the overparameterized regime with shared architecture and random initialization, Qu is approximately compatible with Tg.
C SAMPLING FROM VISITATION MEASURE.
Recall that the policy gradient (T)( in (3.4) involves an expectation taken over the state-action visitation measure Une- Thus, to obtain unbiased estimator of the policy gradient, need to sample from the visitation measure owg. To achieve such a goal, we introduce an artificial MDP (S, A, Such an MDP only differs from the original MDP in the Markov transition kernel P. which is defined as
- -
s. + (1-7) ((s'), as, S Ax
Here P is the Markov transition kernel of the original MDP. That is, at each state transition of the artificial MDP, the next state sampled from the initial state distribution ( with probability - 7-
18

---

Published conference paper at ICLR 2020
In other words, at each state transition, we restart the original MDP with probability 1 - As shown in Konda (2002), the stationary state distribution of the induced Markov chain is exactly the state visitation measure Mxg. Therefore, when sample trajectory {(S,, Ar) where So (()). A, a(- St). and S411 P( As) for all 2 O, the marginal distribution of (St, A.) converges to the state-action visitation measure Ozg.
D PROOF OF MAIN RESULTS
In this section, we present the proof of Theorems 4.7. 4.8, and A.4. Our proof utilizes the following lemma, which establishes the one-point convexity of ((x) at the global optimum x². Such a lemma is adapted from Kakade and Langford (2002).
Lemma D.1 (Performance Difference (Kakade and Langford, 2002)). It holds for all æ that
( - ((T) = (1 - -)
- R., [[Q (s, :), T" (-18) (( [+))]]
where is the state visitation measure corresponding to n²
Proof. Following from Lemma J.1, which is Lemma 6.1 in Kakade and Langford (2002), it holds for all x that
-x')-J(a)) (1 -- E. A (s)
(D.1)
where o. is the acteonction visitation measure corresponding to x², and A is the advantage function associated with æ. By definition, we have a. (:, = n (-1-))_ Meanwhile, holds for that
Ex- (A [ = Ex- (0 (*))) = (s, ) (-1s)) - = -Q" (s. T- (.13) (--s)-((-1s)) (()
(D.2)
Combining (D.1) and (D.2), conclude that
( J (TT) (1 ---))-- E.
<T(1s)]]]]
which concludes the proof of Lemma D.I.
D.1 PROOF OF THEBREM 4.7
Proof. We first lower bound the difference between the expected total rewards of To... and To, By Assumption 4.6, VaJ is L-Lipschitz continuous. Thus, it holds that
J(Fo..n) - J(mo)) 2 T To: L/2 110 0.112.
(D.3)
where 6; (0:+1 fn)/n. Recall that &; = VOJ(TOO)) E where the expectation is taken over o; given 6; and w;. It holds that
VoJ(TT,) T To.- (Vo.(TT)) - E Vo 8, ET (o.(TT)) 8,
(D.4)
On the right-hand side of (D.4), the first term represents the error of estimating (F.( using E[VoJ[(Te))) ) E., o log Te, (a s) Qu, (s, a)], the second term is related to the variance of the estimator VoJ (To.) of the policy gradient VoJ(mo),, and the last term relates the increment 5, of the actor update to (TT.). ). In the following lemma, we establish a lower bound of the first term. Lemma D.2. It holds that
( (VoJ(To.) - LE (V)((()))))) 5, < 4k R/n _1Q - Qu,
where (TO.) defined in (3.7), Si is the stationary state-action distribution, and k is the absolute constant defined in Assumption 4.5. Here the expectation is taken over given 0, and
Proof. See HH.5 for a detailed proof.
19

---

Published conference paper at ICLR 2020
For the second term on the right-hand side of (D.4), we have
c -1c:l///2 -
(D.5)
Now remains to lower bound the third term on the right-hand side of (D.4). For notational sim- plicity, we define
e 0,+1 - (0,+ +n ()(e)) = (TB(0; + (((T)))) - (0: + (T(T))
where Iy is the projection operator onto B. It then holds that
e TT (0, + (mo,)) x e, (0i+1 x) S 0,
Vor E B.
(D.6)
Specifically, setting 0; in (D.6), we obtain that e, 5, - 0, which implies
(a(To)) 6. = (6; - e//n) T 6, 2 |
(D.7)
By plugging Lemma D.2, (D.5), and (D.7) into (D.4), we obtain that
(To 6, 2 -4x R/n 11 Qui 1|6,1//2 - 1
(D.8)
Thus, by plugging (D.8) and the definition that d; = (0i+1 - 0:)/n into (D.3), we obtain for all i [T] that
(1 - L 1)) |//1
Σ 1. [T - ((TO,) )] + 4m R/n E [[[1QT Qui + [[IS////2].
(D.9)
where the expectations are taking over all the randomness.
Now we turn to characterize llp; - --lle- By the definition of ps in (4.3), we have
|p 51112 = - [ (0; + VoJ(mo.)) - 0; [ (0: + VoJ(TO))) 0.) 01)11
11 [Ts (O; + VoJ(TO)) ITg (0, + (oJ(mT)))
V (Te.) J ||2-
(D.10)
The following lemma further upper bounds the right-hand side of (D.10).
Lemma D.3. It holds for all E [T] that
E VoJ( a (Te, )l < 21E [6 Sx² B[[1 Qw, 11a.
Here the expectations are taken all the randomness.
Proof.
See $H.6 for a detailed proof.
Recall that we 17 1/VT. Upon telescoping (D.9), it holds for T 2 4L that
T i=1
min |
[|
1/T
[1
< 1/7 Σ
+ 2E 6.112]
1=1
4(1 L - 2E [llp: 5.11 <//T Σ
T
< 88/VT. J((or()))))) - ) 8/T Σ
B[ + +T)(T), (D.11)
20

---

Published conference paper at ICLR 2020
where the third inequality follows from the fact that 1 - I. 1/2, while the fourth inequality fol- lows from (D.9), (D.10), and Lemma D.3. Here the expectations are taken over all the randomness, and (I') is defined as
(T) = 32x R/VT
B IIQ - Qw; [ks.] + 16x² /T.
E El Qui 11a]
By Proposition 4.3 and Assumption 4.4, it holds for all E [T] that
[lI - Qu; [ ORR m 1/2 1/2 R5/2 1p//2.m11// 11/4),
B||G S o B.
(D.12)
By plugging (D.12) into (D.11), we conclude that min EE || < 8/vT ([JTr((( J + 80 B =QQ i
where
ET(T) 0 mm-1/4 T1/2 + 19/4 m m1/8 1/))
Thus, complete the proof of Theorem 4.7.
D.2 PROOF OF THEOREM 4.8
Proof. Since 0 a stationary point of (mo)) holds that VOJ(TT) (0 8) S 0, Therefore, by Proposition 3.1, we obtain from (D.13) that
40 E B.
(D.13)
VoJ(Fg) (0- 0) Es. [ a) T (0- θ) Q** 20, v0 E B. Here og and o5 are defined (3.3) and (B.2) with 0 = 0, respectively. Note that
(D.14)
Bo,, p a) (0 0) (s)) Ev-g
Eng ( a)] (0 0) V V=8 = 0, B ( a' T(O 0)] FFTg [A o, which holds since E 00 (0, a)) = E,g 11 (1" a)] ] for all S. Thus, by (D.14), have Bor, (0 a) (0 0) QT (s,
E., FTT do (0 0)] A (8, a)
= Erwng
-Bo. [
0) A (T, [)) - -Bo.ng Bigg (') (s)
+ BBrnn 00 a) 0) v=(
BBog ( Ō) A a)) < 0, v0 EB.
(D.15)
Meanwhile, by Lemma D.I we have
(1 (1 (J(=*) - J ((T)) = E., ( (=1ss) --------1-1 (s)]]
(D.16)
In what follows, we write Ag - 0. Combining (D.15) and (D.16), we obtain that
(1 - 7) ( (J(x*) J(Tz))
< Ev. (AA0 :), (.18) TT{+111)]] Bir.n [dg(s T Ao (T a)]
Ey. (AAo (s. ),=²')) xt (.1s) [T(- -Eveg [AAT ) (g( :) T Ao TT(: s))] (D.17)
where we the fact that o. (. a.(.1 .) Urg (-). It remains upper bound the right-hand side of (D.17). By calculation, holds for all (s) S A that
T (a 8) Tπ(a 8) (s) 65(8 a) Ag TT(a| s)dug(s)
n (a 8) - Tp(a (a) 8) de,
(s) Φ5(5, a) A0) mp(a (8)
T
du
(uz(s,a) dz(), T d) (s.
(D.18)
21

---

Published conference paper at ICLR 2020
where Ug is defined as
xxxx do
dvs" dvng
(s) (s) - og(s,a)T0,
up(s,a)= a)
(s)
Here do /d and duz fdvz are the Radon-Nikodym derivatives. By plugging (D.18) into (D.17), obtain that
7)- - -(Ta))
Sv. [ T (-1s) - (-]{1)))] Ev,, (AA og(ss))))) -T Do [
-/s E (") ((T - 8) (u) - 2z(s, a) Do TTya 8 s)duy(s)
aEA
. (s) (ug(s,a) (s a) Do) Do) ().a)
SXA [|A7 [1 S (,, 1lo.g'
(D.19)
where the second equality follows from (D.18) and the last inequality is from the Mauchy-Sehwarte inequality. Note that (A a)l S mQmax for all (s,a) S A. Therefore, it follows from (D.19)
that
(1-7)- (0)))(((('') ((T)) I 2Qmax |1 0g(. Tollo
4o E B.
(D.20)
Finally, by taking the infimum the right-hand side of (D.20) with respect to E B, we obtain that
(1 ()- (J(=") - J(Ta)) S 2Qmax inf OEB
[|u](s)) - og(.,)) (
which concludes the proof of Theorem 4.8.
D.3 PROOF OF THEOREM A.4
Proof. For notational simplicity, we write ne, hereafter. In the following lemma, we charac- terize the performance difference (Tx)) - J(r,) based on Lemma D.I.
Lemma D.4. It holds that
(1 (1-))- - (J(x") - J(T:)) = Ev. DxL (TT (-1 (... ([[s)][=s((11))))
DKL (x T+1(-11s)
Dri (T ( (-][[=(-115)) (1s)]] - H.,
where H; is defined as
H: = Ev, (log(Ts+1l) (0)mm(())))))))) - (,, me(.1 (s))))))))))))))))))))))))))((
(D.21)
(i)
n Ev. ((uu,(s))) (s, TT (-1s) Te( m()]ss)]]
(ii)
Ev. (. ()) T4 (-18) me(. T<(11s))
iiii
Proof. See 5H.7 for detailed proof.
Here H, defined in (D.21) of Lemma D.4 consists of three terms. Specifically, (i) is related to the emror of estimating the natural policy gradient using (3.8). Also, (ii) is related to the error of estimating Q. using Qu,- Meanwhile, (iii) is the remainder term. We upper bound these three terms in HH.8. Combining these upper bounds, we obtain the following lemma.
22

---

Published conference paper at ICLR 2020
Lemma D.5. Under Assumptions 4.2 and A.3, we have
E H.l - Ev. DKI ( (Te+I (-1+ Te( (-)]) S s (nn² + M²) + n (5)) + vir) =Q2 + Es.
Here the expectation is taken over all the randomness. Meanwhile, so and v are the concentrability coefficients defined (A.1) of Assumption A.2, EQ,i is defined as Eq,i = EillQ Qui Quilss.. M is the absolute constant defined in Assumption A.3, and e; defined as
E = V2. R2/2 17 (50 + 4/)) T. [[)]( + [[Il))( 1/2
(D.22)
+ ((141 + 17) R m 1/4 77 R5/1 - m
Here (.():) and (w:: are defined in Assumption A.I, where ó; = = (T++1 -1:11 T....). while Pi and thy are the concentrability coefficients defined (A.1) of Assumption A.2.
Proof. See $H.8 for a detailed proof.
By Lemmas D.4 and D.5, we obtain that
71-7)- [[](T( (ma)] s $n
ミnd 1.
Ey. [KL (x* (-(()))]]
(D.23)
-KI.(TT (T:)a()))) (-
+ (9R² +2)++M+++
1²)+ +, e; + ( + va EQ,
where e is defined &Q. = lls, .M is the absolute constant defined in Assumption A.3, e; is defined in (D.22) of Lemma D.5, and the expectations are taken over all the randomness. Recall that we set 1j = 1/VT. Upon telescoping (D.23), we obtain that
T
(1 - 7) min B[J(TT) [TT:)] S EE[T]
1-7
Σ
- J(TT) B[J(TT)
(D.24)
T
i=1
1
E
Ep,
DKL (-1s)]|
+ + + +22
VT
T
Σ
CVT ( + +() eQ.).
+
T
where the expectations are taken over all the randomness and the last inequality follows from the fact that
DKL (R (-1() [T+I (-1)))()))))))))))))))))))))))) 2 Vs E S, VOT+1 mdd
In what follows, we upper bound the right-hand side of (D.24). Note that we set Ti = 0. By the parameterization of policy in (3.2), it then holds that (- 8) is uniform over A for all S and 0 E IRd Therefore, we obtain that
DEL (m" (- (=I+)] S log [A,, vs S, AO, Rd
(D.25)
Meanwhile, by Assumption A.1, we have
1/2
E (6)) < E E., (6)))
< 0g B 1/2
where the expectation E,, (+.) is taken over o, given 0 and w,. while the other expectations are taken over all the randomness. similar upper bound holds for Elll (w)l)) Therefore, by plugging the upper bounds of (oll)(())))l))) and [[]l([(w;)]la into defined in (D.22) of Lemma D.5, we obtain from Assumption A.2 that
VT e < 222c, R!/2. og 1/2 ///-B-1/ B-144
(D.26)
+ +0((T41 1/2 + 1) R3/2 m 1/4 + R5/4 m -1/8).
23

---

Published conference paper at ICLR 2020
Also, combining Assumption A.2 and Proposition 4.3, it holds that (0) + v/)) Eq, S 20p F Qwills]] = co O 11/1 + p0/4. .m (D.27)
Finally, by plugging (D.25), (D.26), and (D.27) into (D.24) and setting (T) VT e; (4) v/) EQ.
complete the proof of Theorem A.4.
E LINEARIZATION ERROR
In this section, we lay a fundamental lemma that characterizes the distance between two-layer neural network 0 f and its linearization % 0, where Φp the feature mapping of the two-layer neural network defined in (3.3) and do the feature mapping corresponding the initial parameter Winit-
We first introduce a function class that consists of lineaizations of f((--); W/) defined in (3.1). Definition E.1 (Function Class). Let R be absolute constant. For all E N, we define
m
Fumm [(s = mm
Σ b, r=1
mi (s, > 0} [W]] (8,a)
(E.1)
I iiit ll2 S
where [Winit]r ~ NO0, Ta/d) and by ~ Unif((-1,1)) are the initial parameters of the two-layer neural network defined in (3.1).
Note that FR.m in (E.1) a class of functions that are linear W but nonlinear in (s, a). Meanwhile, it holds that Vw a): W) = Vwi W) W= for all (s,a) E S x A, where f((:-); W) is the two-layer neural network defined in (3.1). Thus, f((::); W)
be viewed as the linearization of f((, :); W) at the initial parameter Wiit. Moreover, for a fixed R. the linearization error of f(((,)): W) decays zero as the width
xc. Intuitively, since I|W Wint ll2 upper bounded by R, the differences between blocks [[[]], -[W [Wmater 2l2 are suf- ficiently small for sufficiently large and all r [m²] As result. for a sufficiently large m, we have 1 [[
(s, a) > 0} 1 [[W]] (s.a) a) > 0} with high probubility for all r E [m] and (s, E S x A. and thus f((,, :): W) is well approximated by its linearization f((-,-): W))
The following lemma formally characterizes the corresponding linearization error.
Lemma E.2 (Linearization Error (Cai et al., 2019)). Let Wint be the initial parameter of the two- layer neural network defined in (3.1). Let B = {ar E Redd ||a- Wimtell ll S R). Under Assumption 4.2, it holds for all 0, 0' B that
Einit -
O( m m=11)),
where the expectation is taken over the random initialization. Here de and do are the feature map- pings defined in (3.3), which correspond to f and Wiit.. respectively, and a(.,)) = Λ (.1 v(-) is the distribution over such that Assumption 4.2 holds.
Proof. By the definition of feature mapping in (3.3), we obtain that
(o(s.a) T'
@o(s,a) a) T
1
(((,,)) > 0) - [(((s))) [ >0)) (8, T0')
(E.2)
Vm
Mcanwhile, for 1 [[(ss a) (0), > 0) # 1[(s, a) [W > 0}, we have
(s, T (s) T - (s, a) T[Wmmah+ | s ([(s, a) [[[@], - [Wmadlrl2.
(E.3)
24

---

Published conference paper at ICLR 2020
where the last inequality follows from the Schhhr-Sch inequality. Recall that (I(s, S for all (8, a) E A. Thus, follows from (E.3) that
{s [0], 0} as),a) ( [-int]+ > 0}
- 1 ((),s) [Wiil |1 [Win
(E.4)
By plugging (E.4) into (F.2), we obtain that
( a)) 0 60(5, a) 00
(1 a) [Wiutrl & [1[0]- - [Winlrll2] (
<
[[((s, a) [Wiml $ [1[0)- - [Wmsssrl12]
(I(s,.) a) [Wintteel+ (s,aa) a) (107, -[Wmitl))
m
1 a) ( (lmmall [1[0]- [Wims]
(E.5)
m
(I(s, a) [Wantell + [|00), [Wmal+ll2).
where the last inequality follows from the Cauchy- Sehwba--chhwrtzzt inequality and the fact that (1 a)Ila I 1. Following from the fact that |1/=|| S y} |0|| S 1[ < y} y. we obtain from (E.5) that
(s, a) T
Øu(s, a) T8
a(),,a)) T [ < [[0]- [Wlitt]ll2)
(E.6)
(100) [Wimt | + [[(0)) [=l
Therefore, following from the Cauchy- Schwartz inequality, we obtain from (E.6) that
100(s, TT so(s,00 a) T012
(E.7)
[[(ss, a) [Winttel I [[0),, [Wmatrrll2)
m
(2][[),- (mide 2] (l)
1 (1(s,a)TT Wel < [[0),- [Wiittrll2) 2(110 Winit 112 + 110'
Winit lin)tl12)
where the first inequality follows from the fact that (x + y) < 2x.2 + 2yy. Recall that 0, 0 E B, Wmit ||2 < RJ. Thus, following from (E.7), have
where B (a Rmnd
la
W
4R²
m
@ T) a)
Σ a(((,a)
[[ [[Wma]]
S [[0], Wmnllll2) (E.8)
m
By Assumption 4.2, we obtain from (E.8) that
[0o(:.)) doo:..)T0')) 0'
E, [100 (s, a) To' (s a) T
4c R²
[10], - [Wmitllll
(E.9)
[iiittlll
where e is the absolute constant defined by Assumption 4.2. It now suffices take the expectation of the right-hand side of (E.9) over the random initialization. Following from the Cauchy-Sehward
25

---

Published conference paper at ICLR 2020
inequality, we obtain that
Σ
m
0 r [Winttrlle
Σ [10), [Wintrl11
(
[i f 2
m
110 Init 11
Σ
1/
m
R2
(E.10)
where the last inequality follows from the fact that A E we conclude that
Therefore, combining (E.9) and (E.10),
4c R
m
1/2
nnit (1.)0.,))T0) -ol(:-) TT
Binit
Σ
1 1/1 mitt W
m
4c R
m
1/2
E Einit [1/Il[Wintth mn
m
= 4c1 R
1/2
where the second inequality follows from the Jensen's inequality and 61 = No.o- Thus, we complete the proof of Lemma E.2.
L
By Lemma E.2, the linearization of 0 converges to the two-layer neural network oJ 0 as the width + Based on Lemma E.2, the following corollary characterizes similar convergence where the feature mappings da and do are replaced by the centered feature mappings é and @o defined in (B.1) and (B.2), respectively.
Corollary F.3. Let Wini be the initial parameter and B fax E RRdd ||a Winit l| R) be the parameter space. Under Assumption 4.2, it holds for all 0, E that
Ema ( -) T T Φo( -) 01:3 ORR m 1/2).
where the expectation is taken the random initialization. Here o and dh the centered feature mappings defined in (B.1) and (B.2), respectively, and o.:--) = n --)--)- v(-)
is the distribution over
S A such that Assumption 4.2 holds.
Proof. By the definitions of o and oe in (B.1) and (B.2), respectively, obtain that (:.) -n(-.) T T 11 = | 6' do(.-) - E.p [oo(:.a) 0' o' T 2-1)oo(.-)) To' - (. 00 + ( ( To' (. T
where the second inequality follows from the Jensen's inequality and the fact that || + v11 S 2 2||2 11 31..1 Therefore, by Assumption 4.2 and Lemma E.2, obtain that
Emit [1 TO' oo(: To'113]
2T (:))) TT' (o(:;)) 0'11e] + 2iinit [Iloo(;,)] T To 1 O(R3 m m-122)
which concludes the proof of Corollary E.3.
In what follows, we present a corollary that quantifies the difference between the function de (T and the two-layer neural network f((-,-); (); - TO by the (o)r-moorm, where (.:))
(:1-)) v-) is the distribution over S x A such that Assumption 4.2 holds. Corollary E.4. Let B fa Rand ||a 0, 0 E B that
Winit |2 R). Under Assumption 4.2, it holds for all
Eint [1 To ( T O113/2 m 11/4),
where the expectation is taken over the random initialization. Here is the feature mapping defined
in (3.3), and a(,,)) = . (-) v(-) ) the distribution over S x A such that Assumption 4.2 holds.
26

---

Published conference paper at ICLR 2020
Proof. By the triangle inequality, we have
Einit [Iloa(--)) T - Φe(- - 0 - Binit (l Φ0(- 0 + Binit (1 -
(E.11)
where du is the feature mapping defined in (3.3) with Wint. Meanwhile, for all 8, 0 E B for E IRmd ||a Winie 22 v RJ. follows from Assumption 4.2 and Lemma E.2 that
Binit [1] 0 (.) ) (o(::-)'o)) 0|1b] = O( 1/R2//2mm. m m11)), Binit ()) T oo(:,-) ( 0||~] = O(R3/2 mm m-1/4),
(E.12)
where the expectations are taken over the random initialization. Combining (E.11) and (E.12), obtain that
Binit (1lbb(.)))) -000~~o0--)) do(::)) O(13/2 m m/1/,,,
which concludes the proof of Corollary E.4.
Corollary E,4 implies that when the width m sufficiently large, op(.,)) is well approximated by the two-layer neural network [((::);;)) in L2(r))-orm) where a(.,-) x(-1-) v(-) is the distribution over A such that Assumption 4.2 holds.
F NEURAL TD
In this section, we introduce the details neural TD (Cai et al., 2019) for critic update in Algorithm
1. Neural TD solves the optimization problem in (3.1 1) using the TD iterations defined in (3.12) and
(3.13), which summarized in Algorithm
Algorithm 2 Neural TD (Cai et al., 2019)
Require: The policy म, number of TD iterations TTD, and learning rate 7ID of neural TD. 1: Initialization: Initialize by ~ Unif([-1,1}) and [Winit]r ~ N(0, NO,,a//) Set B +- (ar E
R.nd ||a W init| l|2 R) and (0) <- Wmit.
2: for t- 0,.., TTD- - do
Sample a tuple (s, a, r, s', a'), where (s,a) Si, s P(: (,))s,)), r(s,a), and a' T-)1=').
4: Compute the Bellman residue + Qu(n) (s, a) - -) . -1-77)---7- 2u
5: Perform TD update step: w(t + 1/2) w(l) 11- 8. (s.
6: Perform projection step: w(t 1) +- 11/2)
7: Perform an averaging step: w + 4+1 w 42 w(t +1).
142
8: end for
9: Output: Q.ui(.) Qw(-).
The following theorem by Cai et al. (2019) characterizes the rate of convergence of Algorithm 2. Theorem F.1 (Convergence of Neural TD (Cai et al., 2019)). We WTD min((1 7)/8, /TD) in Algorithm 2. Under Assumption 4.2, it holds that
Einit [I]Qout @²I < 2Finit [|[T
FR.m Q -2113-
(E.1)
+ORR²
T/
1/2 + R² m 1/2 + R5/2 .m -1/4).
where 11,,, is the projection operator onto Fr and s is the stationary state-action distribution corresponding to n.
Proof. See Proposition 4.7 Cai et al. (2019) for detailed proof.
27

---

Published conference paper at ICLR 2020
F.1 PROOF OF PROPOSITION 4.3
Proof. By Theorem F.I, to establish the rate convergence of neural TD, suffices to characterize 1 in (F.1). To this end, we first define the approximation error Emit II R. function class
Qa
F R,m [((,a)::))
Σ
m
br 1 [n (s, a) > 03 W, (8,
mm
[[[,, - [Wintt-llo R//mmd
where [Winit]r ~ N(0, Ia/d) and b, ~ Uni are the initial parameters. By definition, FR,m is subset of FR,m defined in Definition E.1. The following lemma obtained from Rahimi and Recht (2009) characterizes the deviation of Fu,m from FR given in Assumption 4.1.
Lemma F2 (Projection Error of F.,m (Rahimi and Recht, 2009)). Let f FR,co, where FR,co is defined in Assumption 4.1. For any ò 0, it holds with probability at least - 8 that
[ Rn J - Alk S R m 1/2 [1 + v /2log(1/0))
(F.2)
where is distribution over 8 A.
Proof. See Rahimi and Recht (2009) for a detailed proof.
Following from (F.2) in Lemma F.2, for all f FR and t >> 0, we have
F.m f Alls 2 < exp(-1/2 vm/R 1)?).
(F33
Meanwhile, by Assumption 4.1, we have Q E FR Therefore, by setting = Q" and ç = in (F.3), we obtain that
l P( R,m QF Q= 2 f)
Einit [||L
R.m Q" -0=
(xp(-1/2- (t Vm/R - 1)²) dt O(R m m/1)), (F4)
where the expectation is taken over the random initialization. Also, note that Fr,m S Fn,m. where F R. is defined in Definition E.1. Therefore, follows from (F.4) that
Einit [1 Fm Q - 2= < Emit [ [ R.m Q" 1=1 [2
O(R OOR-m 1/23)
(F.)
Combining (F.5) and Theorem F.1, we obtain for WTD min (11 78/8, 1/ TTVTTD) that
Emnt [l]Qout Q" 1= O(R m m-2 R² TTD + R² m -12 + R5/2 -1/4). (F.6
Specifically. Qw, is the output of Algorithm with TT, as the input. Finally, by setting TTD 3(m) in (F.6), we obtain
Enii [1|Qu, TT
; [2.1 O -mm 1/2 112 R5/2 m 1144),
which concludes the proof of Proposition 4.3.
G PROJECTION-FREE NEURAL POLICY GRADIENT
In this section, we study the convergence of neural policy gradient where we do not impose the projection in the actor update. Specifically, the projection-fres free actor update takes the form of
0 + 0, + (T
28

---

Published conference paper at ICLR 2020
Here (TO,) is an estimator of the policy gradient (oJ()oo)). which takes the form of
B
(.). = Ti Qun (e)
Vg log ne, (ar st).
(G.1)
B
Here Ti is the temperature parameter of To, {(s2, Re) is sampled from the state-action visita- tion measure o; corresponding to the current policy Te, and B >> O is the batch size. Also, Qw, is the modified critic. Specifically, for all (8,a) E A, define
Qui (s, a) Mmx (Q, Qmax mmxx 11 [1 -mmax)
(G.2)
(s, a) 1m Qw, Qw,(s,))
< Qmax)
where Qu, is obtained from Algorithm with Te, as the input. We summarize projection-free neural policy gradient in Algorithm 3.
Algorithm 3 Projection- Free Neural Policy Gradient
Require: Number of iterations 7, number of TD iterations TTD, learning rate 7), learning rate 1rD of neural TD, temperature parameters {Tx (ET)) and batch size B.
1: Initialization: Initialize b, ~ [,, and [Wint], ~ NO,, for all r E [m]. Set
B {a E Rend ||a Wintele S R] and 01 + W Wiit.
2: for E [T] do
3: Update wi using Algorithm with Te, as the input, w(0) + Wiit and (br)rem) as initialization, TTD the number of iterations, and 1/D as the learning rate.
4: Sample {(SE, (eee,ae)eee(e from the visitation measure di, and estimate VoJ(mo) using (G.1) and (G.2).
5: Update 0.+1 by 01+1 +0 + (To.))
6: end for
7: Output: (TO, ]e((++])-
G.1 CONVERGENCE OF PROJECTION FREE NEURAL POLICY GRADIENT
In this section, we show that the sequence (eef)e(T+1 generated by projection-free neural policy gradient converges to stationary point at sublinear rate. In parallel to Assumption 4.4, we lay out the following regularity condition on the moments of the estimator (TJ(
Assumption G.1 (Moment Upper Bound). Recall that o; is the state-action visitation measure cor- responding to Te, for all (T). Let & V E ([ )}, where V (Tg,) is defined (G.1). We assume that there exists absolute constants az S3 > such that E[[ S 7ス of and EiIl wi.
Tp ///3/2 for all i [T]. Here the expectations are taken o, given 0 and
Similar to Theorem 4.7, in the following theorem, we show that the sequence (orlver++) generated by Algorithm converges to stationary point Ø with VoJ ( O at sublinear rate.
Theorem G.2 (Convergence Stationary Point). Let r 1/VT, 7)/8, L/DT and TTD (mm) in Algorithm 3. Under the assumptions of Proposition 4.3 and Assumptions 4.5, 4.6, and G.1, it holds for T 2 4T. and B = l( T1/2) that
1, MDD min
[1 min E V (
1
(TO, )] + EPG. < <8/VT B[J((er...) J
where
EPG 1/2 RR/2 m m144 T 15/44.m-1/ 11/8 .T).
Here the expectations are taken over all the randomness.
29

---

Published conference paper at ICLR 2020
Proof. Our proof aligns closely to that of Theorem 4.7 in $D.1. We first lower bound the difference ( - J(T.). By Assumption 4.6, we have
where [ (TT.) ) 2 ") (TJ( To;
0.112.
(G.3)
6, 60:+1 (0)+1
0,)/n ( Ei [T].
Following the proof of Lemma D.2 in 9H.5, obtain that
( (VoJ((To)) [[VoJ((Te.)) 6.1 k/n 2| 0oll2 -1001 - Qui lls..
(G.4)
where the expectation is taken over o; given and wi. Recall that &, VoJ( where the expectation taken over as given 0; and wi. Following from (G.4), we obtain that
(mo,))
(o.( 6; = (voo(=))) - [V 6; - (G:) 5, + [ T5
2 2k |0:+1 0.112/1 11 Qw,, l| 11//2 /
(G.5)
where the second inequality follows similar analysis BD.1. Hence, by plugging (G.5) into (G.3), we have
J(Fo):)) - -
(1 L ())))))))))1)))))))) //2)/2 ||0:1 - n. 11/1//2 2x |10,+1 0:112 102-11@0 - Qui
(G.6)
remains upper bound ||0++1 0.|12. To this end, we use the fact that
||0++1 0:l12 S 110, Winiella+ + ||0..1 Winitl22,
and upper bound |10, Wintt 2 and ||0:+1 Winiella By the actor update in Algorithm 3, we obtain for all i >>> 1 that
i-1
0 - Wini lla S
Σ n /=1
(To, S Σn n (II 111l + (1&ll2)
(G.7)
j=1
where the expectation is taken over o, given 0, and wi Meanwhile, it holds that
[[Vo }] 1|2 = =I, [oo, (s, a) Du,, (s, ()]]|/ s Bag [1 (s, a)ll2 12,, (s, a)], (G.8)
where Φe, is the centered feature mapping defined in (B.2), and the last inequality follows from the Jensen's inequality. We now upper bound the right-hand side of (G.8). Note that 11 (s, a)ll
for all (8, a) ES A. Meanwhile, by (G.2), we obtain that
Qw,, (s,a)l S Qmax: E
(G.9)
By plugging (G.9) into (G.8), we obtain for all j [T]] that | J )] 111 S 2Q
(G.10)
By further plugging (0. into (G.7), we obtain for all i that
i-1
00, Winiell2 S 2Qmax n T Σn n- |1l12
(G.11)
j=1
We now lower bound the right-hand side of (G.6) based on (G.11). Following from the Cauchy- Schwartz inequality and Assumption G.1, we obtain that
B[ - Winit llz ||@T Qu: Il<.]
1/2
< 2Q 17 T. [I - 2..1
Σ " 1=1
E [ }
1/2
{ElIQTT - Q [2:] 1/2
{BlIIQTO, - -Qu 12:1 1/2
< (2Qmax 17 - og n. T B-
(G.12)
30

---

Published conference paper at ICLR 2020
where the expectations are taken over all the randommess, and oe is the absolute constant defined in Assumptions G.I. By plugging (2.12) into (G.6), we obtain that
(1- Ln- [1
) + 0 /2B) + RT( {B[IQTT (((T)))((IQT) - Qw,, 1211]
- [ -
(G.13)
where we use the fact that ||:++1 - 0:112 - |10 Wiittll lll + 100 Wintt Here the expectations are taken over all the randomness, and (T) is defined by
Ro(T) 4Q 11 + 20g 1 T - B-1/2
By Proposition 4.3 and Assumption 4.2, obtain for 77 1/VT, B =s T112), and TTD
(mm) that
O -
-u, [1:] - E[lQQT Qw, [2.]
= O m 112 + R5/2 m 1
(G.14)
where the inequality holds since (8, a)l S max for all (s, a) E x A. By plugging (G.14) into (G.13) with fj = L/VT and B = Mo T we obtain that
(1 -1- L/- 2 6 S VT EE (TT)))) - [(TO)] + EPG:
(G.15)
where
GPG OO' + R m T T R5/4 mm 118 .
(G.16)
It remains upper bound ||ō; V.. 112,, where 6, ( Following from similar analysis to 6H.6, we obtain that
E (e)) ( >a - 21E [|]]]]]] + Sx² [l[1QT - Qw. 11a.]
where the expectations are taken over all the randomness. Therefore, following from Proposition 4.3 and Assumption G.1, it holds for 1/VT, B = o? T12)), and TID = 32(m) that
E (T)T( - ( > = OT R m 1/2 R5/2 m 1/4).
(G.17)
Thus, combining (G.15) and (G.17), we obtain for all E [7] that
( - 2E |1, [ n. (To)) र (
- 4(1 I/V E [1 + 2 [oJ(ma, (
< T [[ - (TT.)) )] + EPG.
(G.18)
where we use the fact that T 2 2L and we define EPG in (G.16). Finally, by telescoping (G.18), we obtain that
min E
< T
V[I < 8E [E(Tr)))))) ( (Te -
EPG.
where
EPG O(T 1/2 + R2/2 m 1/4 T +R// m -1/8 -1/8
Here the expectations are taken over all the randomness. Thus, we complete the proof Theorem G.2.
Following from Theorem G.2, it holds for m = -( (21) that min
o |||] O(IVVT). sE[T]
Therefore, O converges to stationary point at 1/vT-raat if the width of the two-layer neural network and the batch size B are sufficiently large. We highlight that compared with neural policy gradient with projection in the actor update, Algorithm needs larger width to achieve the 1/vT-rate of convergence. Such stronger requirement is the extra price pay for using the projection-free actor update.
31

---

Published conference paper at ICLR 2020
G.2 GLOBAL OPTIMALITY OF PROJECTION-FREE NEURAL POLICY GRADIENT
In this section, we characterize the global optimality of projection-free neural policy gradient. We define sequence of parameter spaces {B, herry as follows,
B far E Brdd ||a 0: S Roj, e (T),
(G.19)
where Ro 2 is an absolute constant. The sequence {B: HE(m characterizes the global optimality of the parameter sequence (erre- Specifically, similar to (4.5), we have
VoJ(=o,) ( 0:) - ||0 0:l12 [ )ll2 - Ro [To))o)) AA Bi, E
where the first inequality follows from the Sschh--S inequality. Following similar analysis 5D.2, we obtain for all i [2'] that
(1 7)) (J(TT) ((Te)) I 20max
inf [luoo 6o, (ll.) Ro Vooo AEB:
(G.20)
We now introduce the parameter space Br that includes the sequence {Oilietz and the parameter space B; as its subspace for all E [T] as follows,
By far E Rmdd ||a (la--mielll Wmilll S R(T)) + no)
(G.21)
where
T
R(T)= 2Qmax 11 T T 7
k
(G.22)
Here E, is defined in Assumption G.1. Following from (G.7) and (G.10) in the proof of Theorem G.2 in JG.1, we have 0g E Br for all i E [7]. By Corollary E.4, (o,(..) ( is well approximated by f((::));)) for 8, 8; E By when the width m is sufficiently large. Thus, following from (G.20), for sufficiently large m, the suboptimality of 0, is characterized by || [ [12, which is further quantified by Theorem G.2, and the approximation error inf ||u0, (: f((ss );0)]l which quantifies the representation power of the overparameterized two-layer neural networks. In the following theorem, we present a sufficient condition for the output of projection-fris free neural policy gradient to be globally optimal.
Theorem G.3 (Global Optimality of Projection-Free Neural Policy Gradient). Let 1 Ti YTD min [(1 - /), /TD)), and TTD (mm) in Algorithm We define
1/VT,
To. (s, a) = uo, ()) + de, (s,a) T (Wint - 0.), V(s.a) E S x A.
Here us, is defined in (4.4) of Theorem 4.8 with Ō = 0,, and Φv, is the feature mapping defined in (3.3) with 0 = 0,. Under the assumptions of Theorem G.2 if it holds that
uØ. E F Vi E [T].
then for 72 4L2, B -2)22/2) and m = S(R10 T2,), we have
(1 - 7) min (E(T]
B[J(x*) J(Ta:)) O -T-14/11/4)
Here the expectation is taken over all the randomness.
Proof. To prove Theorem G.3, it suffices upper bound the expectation of the right- side of (G.20) over all the randomness. We first upper bound the following term,
E inf || (...). Φo. (...) TTll)) LAeB,
where the expectation is taken over all the randomness. Note that
un (8, a) - Φ0, (s, a)T 0 = uo (s, a) Φ0, a) aa 0, (s, T
Winit - (0, aT,
= ūo (s, a) @0(8, a) (0 - 0 + Wintt)
(G.23)
(0o. (s, a) - Co(s, a)) T (00 0 + Wmnt)
32

---

Published conference paper at ICLR 2020
which holds for all (s. E 8 x A and A E B, with B; defined in (G.19). Therefore, by the triangle inequality, we obtain from (G.23) that
inf Iue, ((.) de, (c.)) Oloo. 6llo, deB:
inf deB,
[ (4-)) -oo;))) 0, Wintt)lla
(G.24)
+ (1( (s. - oo(s 0, + Wiin)la llo
We now upper bound the right-hand side of (G.24). In what follows, we define 0, by
co(s.) -)
I1 Bg.. (t--).
where H Ro.m
is the projection operator onto F It then follows from the definition of Ro.m
in Definition E. that 0, E B1 = (a E IRmd ||a - Winit ll x Ro} for all i E [7]. Meanwhile, by
the definition of Be in (G.19), we have
0 + 0; Winit Bi, Vi [T].
(G.25)
Combining (G.24) and (G.25), we have
inf [[-),(--)) ou, TT.))ollo, S |ūo (s.)) - + (((()))))l,+(((((((()))) ((((o(((--))((..)))) Oo DEB,
(G.26)
Now, it suffices to upper bound the right-hand side of (G.26). Following from the proof of Proposi- tion 4.3 in IF.I, we obtain for uæ, FR that
Uo. (..-) do(.,.) T = E ( (+.))
Rg To. (..).))) Ila.] = O m m/3), (G.27)
where the expectations are taken over all the randomness, Meanwhile, note that
|00 Wintt/22 S Ro S Ro + R(T):
where R(T') is defined in (G.22). Therefore, we obain that 0,, Tg E By. By Assumption G.I, we obtain for 1/VT and B = 1/2 that
E { O(T),
E [[((T)']
(G.28)
where the expectations are taken over all the randomness given Wint- Thus, following from (G.28), Assumption 4.2, and Lemma E.2, we obtain for all 0g, 0g E By that
E [1 TØ. - de. (...) 1ello.. TTe
$ [ 0, Φo. (-.-) To.1e.) 1/2 = O(T8/4.
(G.29)
By plugging (G.27) and (G.29) into (G.26), we have
inf LoeB
[lua. (::)) - de. (:..) T 81(a,)
< EE ان (., (0(.,.) 0.llo.] (((o00(,))) (..( T.llos)]
O (Ro 112 7// 11/4),
(G.30)
which holds for all i E [7].
Meanwhile, by Theorem G.2, we obtain for B = 12(11/2) and m = 2(R10 7212 that
min E Vo 1l2]] = (T-4
(G.31)
#E|2"
Thus, by plugging (G.30) and (G.31) with m = 2(R'0 12)) into (G.20), we complete the proof of Theorem G.3.
By Theorem G.3, it holds for sufficiently large width m and batch size B that the expected total reward. (TTo) converges to the global optimum J(T²) at a 1 1/T11/-
33

---

Published conference paper at ICLR 2020
H PROOF OF AUXILIARY RESULTS
In this section, we lay the proof of the auxiliary results.
H.1 PROOF OF PROPOSITION 3.1
Proof. The proof is based on the policy gradient theorem (Sutton and Barto, 2018) in (2.5) and the definition of the Fisher information matrix in (2.7). It suffices to calculate Vo log ( By the definition of To(: in (3.2), it holds for all (s,a) S A that
Vo log (a s) T- Vof((s, - T En'Es Vof((s, exp[T f((s a'):)
Eved exp f(ss,a'):0)
()) -T. E. [of((s,
(H.1)
where we write Ex, (of((s,a'):0)) Meanwhile, recall that Vef((:))); :) oo(;)), where de is the feature mapping defined in (3.3). Thus, (H.I) implies that
Eg'nro(- Vof((s, a'); 0)] for notational simplicity.
Va log no (a
0n(s, a)
ETO [0n
(H.2)
Finally, by plugging (H.2) into (2.5) and (2.7), we have
VoJ(TO) = Bor, (s, (s) (do(s.a) - Emo (oo(s,
F(0) = Eo., ( (oo(s) a) - E [oo((s (o)s (0o((),)) - END [do a')!) ]:
which concludes the proof of Proposition 3.1.
H.2 PROOF OF THEOREM 4.9
Proof. By Theorem 4.8, we have
(1 (1-7) (J(=") - J(TT)) < 2Qmax inf - Tlllm..
-
(H.3)
BEB
where Ug is defined (4.4). suffices to upper bound the right-hand side of (H.3) under the expectation the random initialization. Following from the triangle inequality, obtain that
inf [lug(+,)) - ) BEB
inf ||ug(:-) II upl. (o(.,))1l -loo. + || |1 mm ug(:.)) (oll.-)T0ll.. BEB
- 11.pp.. up(: -lloosg
+ inf BEB
11 Fn... ug(;,) opl., T). 00loo.
(H.4)
where Fn.m is defined in Definition E. It remains to upper bound the right-hand side of (H.4). In what follows, define 0 by
6 0 51 ug(:)) E FR.m
where du is the feature mapping defined in (3.3) with 0 = Wmit- By the definition of FR.m in Definition E.1. it holds that 0 E B {a Rmnd ||a Winit l2a R). Thus, by (H.4) and the fact that 0 E B, we have
inf [| ()(: < || - ) Tollo + I1 DEB
oz(; T0
(H.5)
Following from the proof of Proposition 4.3 in SF.1 it holds for ug E FR,cc that
Emit [[ug((--) -) ( 01
1/2 = = m -1/3),
x Einit [1]ug(:-) - og(. T 111
(H.6)
34

---

Published conference paper at ICLR 2020
where the first inequality follows from the Jensen's inequality, and the expectations are taken over the random initialization. Meanwhile, following from Lemma E.2, obtain for all 0,0 B that
Eiit [1oo0(.)) (e((:-) T r
1/2 Emit [1 )T oz( T012
-0(R3/2.m .mmmmmm//// m-1/4),
(H.7)
where the expectations are taken over the random initialization. Finally, by plugging (H.6) and (H.7) into (H.5), we obtain that
(1 (1- Emit [J(x*) - [(T))] 2Qmax Eiii
inf ||ug(--) 0g(:.)) 0(18/2 m m/1))
WEB
where the first inequality follows from (H.3). Similarly, if the assumption that ug E FR,o 0o is imposed, we conclude that
(1 (1-7) Eiit [J(²") [(T)) s O(R m 11/1 + Rinit [| " ugllog uglloggl
which completes the proof of Theorem 4.9.
H.3 PROOF OF INEQUALITY (4.5)
Proof. Recall that we define pt by
= .n (1s( + VoJ(TT)) - 0.).
(H.8)
where 1T the projection operator onto B. Following from (H.8) and the fact that (TBy
y) (Wav - x) s 0 for all x E B, have
(17
1 voJ(zo))) (1 P: + 0, -
vo B. S0 -0)
(H.9)
Thus, following from (H.9), we obtain that
( TT (0 0,) S p. 0,) - 17 11e: + 7 p. (TO)
< pxlll (110 0:112 + " 1 (To,)))))) A0 E B,
(H.10)
where the last inequality follows from the Cauchy-Schwar inequality and the fact that 17- p| It remains upper bound the right-hand side of (H.10). For all 0, 0 B {a R md
||o - Winit 2 < RJ. we have ||0 - 0 la < 2R. Meanwhile, recall that we set T; = 1. Therefore, following from Proposition 3.1, we obtain that
[ lll S E.,, [[QT a)l |1 [s.a S 2Q
(H.11)
where the first inequality follows from the Jensen's inequality, and the second inequality follows from the facts that =Q (s, a I Q Qmax and (, (s, a)ll2 < 2 for all (s, a) E S x A. By plugging (H. and the upper bound |10 0, _ 2R into (H.10), we conclude that
(TO, T(o 0.) S (2R + 2n Qmax) ||pil2, e
which concludes the proof of (4.5).
H.4 PROOF OF COROLLARY A.5
Proof. It suffices to calculate (T) defined in (A.3) in Theorem A.4. Note that we set = (i
1T. Therefore, we have = O(VT) for all E [T]. Thus, it holds for m Q( 76) that
((T44 ( + 1) 123/2 1/4) 2/7-)/2), vie [T), O m 118) = (T-222)
(H.12)
Meanwhile, it holds for B = N(R 2 of) that
/2 (o BB) 1/4 -
(H.13)
35

---

Published conference paper at ICLR 2020
Therefore, combining (H.12) and (H.13), we obtain that
(T') = /8pp RR/2. (o (oC/B) (1L + T+11 T2/23 1882 10/..m .m mm1/1 + 1/5/ m m1/88
(/22) By Theorem A.4, we have
log |A| + 9R M
min (()TT) - -J [TT.)) E
+ +0((1 (0((1-7)-11) -
(1 (1-7)- VT
log |A|
(1 (1-7) vT
which concludes the proof of Corollary A.5.
H.5 PROOF OF LEMMA D.2
Proof. In the sequel, write Ii E[VoJ( for notational simplicity, where (TJ(TO) is defined in (3.7), and the expectation is taken over given 0, and w;. Recall that we set 7, = 1. By Proposition 3.1, obtain that
((Vo](TO.) - 9:) To)To, = E., To. (s, a) (Q (s, (u, 6: 5,
S ||0:|22 E., 1100, (s, a)ll2 1Q (s, a) - Qw, (8, a))
(H.14)
where 60 (s, a) is the centered feature mapping defined in (B.2) with 0 O. and the inequality follows from the Jensen's inequality. Note that 0; 0:+1 E It holds that
||6/ |10 0.112/1 S 2R/n.
Meanwhile, note that 10,, (s, (s, for (s, E SxA. Therefore, it follows from Assumption 4.5 and (H. that (Vo. (.))).a. 8,1 4R/n Es,
1...111000 _10 (s, a) Qw. (s,
1/2
< 44/ Es, /
11Q Quilk
< 4k R// 11QTh, Qui
where the second inequality follows from the Cauchy-Schwee Schwartz inequality, do:/ds; is the Radon- Nikodym derivative, and is defined in Assumption 4.5. Thus, we complete the proof of Lemma D.2.
H.6 PROOF OF LEMMA D.3
Proof. In what follows, we write 9i = J((,(TTO))) ) for notational simplicity, where the expectation taken over o, given 0g and wi. Note that
IE [e) - G.. (1)) < 21 [|2] + ( - g. 1
(H.15)
where we use the fact that || + v113 s 2||x|| + 2 2. and the expectations are taken over all the randomness. By Proposition 3.1, we have
(oo.(TT) - 9ill2 = Es, T (s. a) (Q (s,a) Qw Qu.
< E., [10y, (s. al Th; (8, - Qw, (s)
(H.16)
where 06 is defined in (B.2) with inequality. Since 00 (s, a)lla 5 2 for all (s, a) E ES A, we obtain from (H.16) that
0, and the second inequality follows from the Jensen's
[Vo](To)) 1:l12 < F.., [1 (s. a)ll 1Q (s,a) Qw,, (s,
2 =1 Qw, 1I.
(H.17)
where x is defined in Assumption 4.5 and the inequality follows from the Cauchy-Schwarte inequal- ity. By plugging (H.17) into (H.15), obtain that
E [ ( J 11 < 2E [& S E[[[ Qw: 113.1
which concludes the proof of Lemma D.3.
36

---

Published conference paper at ICLR 2020
H.7
PROOF OF LEMMA D.4
Proof. By the definition of the KL divergence, holds for all a E S that
DeL (T" ( [|))
( ()][
s)) DRL. (#* ( (-1s)[[=++((1)))
(log (++1( s) (T( s)) , nT (-1s))
(H.18)
Meanwhile, the right-hand hand side of (H.18) be expanded as follows,
(Iog(T.+1( (++ s)/m())/lm////m (-))) - (-1s))
= (1:g( {)) x'((' (-1 -=:-1((.ss)) + (log ( (11s)/ssss/sss))) (oss((ls))...)) (
(log((T41 (-1))//(()1mm(((((() 8)) x (.16) 7--1(-11 (-])) + +Ra, (T (+16)( (.)))) (H.19)
L
Combining (H.18) and (H.19), we obtain that
L, DKL ( (T= (-1 (+|s)]] [+ s)) In what follows, we calculate the difference
DKL (=' (='([ss|||
DKL (T)4)((-)))) TT(- (c(-ss).
(H.20)
Ev, [L,] (1 (7) --7.11111 (J(TT) - J(TT)).
By Lemma D.1, we have
J(x") J(x,) (1-)) Ev, (s,) (T.
(H.21)
Meanwhile, for Lg defined in (H.19), we obtain that
L 1 (QT (s, 1), x (s, (s.
(log(T:+)) (8)/m(( (-)=)=||)==(( (.1s) - (--1(-11)) - -1 (,, (s)
= -(lg (T++ ())mm(((-
(s, x) (.(s) - TT(+1s))
(H.22)
+ (s, (s, (-1s) - x;(:18))
+ (log(T:+1( (- s)) (((-ss) T++1(-1 (-)+)=1s))
Note that upon taking the expectation over 8 ~ v.(.) in (H.22), the right-hand side of (H.22) is equal H, defined in (D.21) of Lemma D.4. Thus, combining (H.21) and (H.22), obtain that
Ep, L.] - (1 7) n7 (J(T") ((T)) H,,
(H.23)
where H; is defined in (D.21). ) By plugging (H.20) into (H.23), we conclude that (1-7) (J(m*) J(m))) F., [KKL (TT (: (.18)[ (s)) DRL. DKL 3)[[=((( (1s))]]]]] - His
which concludes the proof of Lemma D.4.
H.8 PROOF OF LEMMA D.5
Proof.
By (D.21), we have
H < E Ev.
(log(TH4(-1ss/TT]
n Qu, (s. .( [s)]]]]]]]]]
(H.24)
+ E
Ev, [1Q (s, - Q² (s. -T (-1 T. (+(1s))]]]
+ E E,, (log ( TT/ s)) m (s)s) - o5 (((1s)
where the incquality follows from the Jensen's inequality. and the expectations are taken over all the randomness. To prove Lemma D.5, we establish the upper bounds of the three terms the right-hand side of (H.24) respectively in the following lemmas.
37

---

Published conference paper at ICLR 2020
Lemma H.1. It holds that
E Ev. [KQ
m (.(1ss))]]] S (Ø) + w [[Il@,, Q. 11
where d/, &y are the concentrability coefficients defined in (A.1) of Assumption A.2. Here the expectations are taken over all the randomness.
Proof. See II.1 for detailed proof.
Lemma H.2. Under Assumptions 4.2 and A.3, it holds that
E Ev. (log((T+1( (1/4+1((lss//m((( s)) (Ts |s) T m=+((116)]]]]
Ev, DKI. (+]s)] mee [1)) + 1 (9n² + M²) + O 12/22 1m/..mm11 m m=//)
where M is the absolute constant defined in Assumption A.3. Here the expectations are taken over all the randomness.
Proof. See $1.2 for detailed proof.
Lemma H.3. Under Assumption 4.2, it holds that
E Ev.
(10g((=-1(115))
(.((()) -s,
17. Qw,
a.(: (.((1s))]] {)){|]
$ /2((p + the) 1/2 TT { (1)) + B(lls)(wo)) 1/2
+ + 17) R3/2 m 1/4 17 125/ m 1/$))
where i and vi the concentrability coefficients defined in (A.1) of Assumption A.2 and (6,), (wx) are defined in Assumption A.1. Here the expectations are taken over all the randomness.
Proof. See $L.3 for detailed proof.
Finally, applying Lemmas H.1, H.2, and H.3 (H.24), holds under Assumptions 4.2 and A.3 that
H.l Ev, DKL ( (1)))( [1)]]] sn (6R2 + M²) n (v4 + wh) EQU + ex
where
EQ.: = E[lQ=: - Quilla]]
1/2 6, = ([1I((66))1a + [1((]))))a]] + ( +n) R3/2 m m144 + R5/4 m -1/8).
Here the expectations are taken over all the randomness. Therefore, we complete the proof of Lemma D.5.
I PROOF OF SUPPORTING LEMMAS
In this section, we provide the proof of the lemmas in gH.
38

---

Published conference paper at ICLR 2020
I.1
PROOF OF LEMMA H.1
Proof.
We define AQ,(s,,) a) = Qwi ((= for all (s, x It holds for all i E [T]
that
Ex. (0.[11q,,(s,) x (-1s) m((-s))]]]
-161 / ( (T" 8) mi(a|o)) do)
(LI)
Meanwhile, holds for any that
Σ AQ)(s,a) (T"(a) 8) =((als))
aEA
1/ Aq)(s,a) (7*(a)s) 8) (a (llss)//mm [a s)dm; (a 8)
< / (ei(s,a) (a 8) m: 8)) (a dd 8),
(I.2)
JaE
where the inequality follows from the Jensen's inequality. By plugging (I.2) into (I.1), we have Ex- [1(Aqu(s) :), T (-|s) (+)+))))
f (Q,(s,a) a) (a s) (: 5)) (1 |a| () 5xA
(1.3)
where we define o(..)) ) T- 1.). 144 v+). Recall that s.(.-) (.1. ex(+) and o =x(1--)))
v+(.). Therefore, following from (I.3), holds that
EE- || T² (:18) Tz( [+)])))]]
Efo JSXA A a)ldo, + Sf. IAq.(s.)) a)l du*
(s) ds,
(I.4)
dg.
Finally, applying the Cauchy-Schwartz inequality to (I.4) yields that E Ev. [K 2 " (-1s) T (.(1ss)]]]
{ Reg [[do./ds))
1/2
{ (ee, [(dus/de:)
)12))))) E Fe, ( a)) 1/2
+
E { (Aqs(ss 1/2 [(pb (v% + v/ E Aq.
(vp) + v/(
where do. do./ds; and dv, /de: are the Radon- -Nikodym derivatives, s6 and v are the concentrability coefficients defined in (A.1) 1) Assumption A.2, and the expectations are taken over all the random- ness. Thus, we complete the proof of Lemma H.I.
I.2 PROOF OF LEMMA H.2
Proof. Following from the definition me in (3.2), we obtain that
(log (T41 (sssss((((s() (-1ss) - T.-I( ( ss)
(T
- - 0.) ml(. (s) m+1((11s)
(I.5)
(CC.(s), -
where f((- 0); is the two-layer neural network defined in (3.1) and C,(s) is defined by
Cs(s) log Σ exp(T: (((s.)): loo Σ exp
T+4 [(ss, a); ((+1)))
aEA
aEA
Note that both TT(-1 8) and T++ 5) are distributions over A, which implies that
(C)(s), (, (++((:1)) = C.(s) Cs(s) = 00,
vs E.
(L66
39

---

Published conference paper at ICLR 2020
Meanwhile, recall that we define the feature mapping (0( in (3.3). For the two-layer neural network f)(:,);;), we have
a(() @o(ssa) V(s.a) ES
(I.7)
In what follows, we write (s, a) = co, (s, a) and (a)a)) Ti(a 8) mi+i(a) 8) for notational simplicity. By plugging (1.6) and (I.7) into (I.5), we obtain for all that
(log (Te+(()) 8) (-( 8)), ( {)> = (15+1 (1t1 0.+1 7 oz(s, T 00, A.(-1s))
(0:(s, " (T++1 8.41
0,), A.(-1s))
T+41 (8041 ( (s(s, -) 0,+1, A.(-)))()))))))))))))))))))))A
S |oo((s, (T+41 0st1 - T; -.. -:))lloo. |1.(- 15)1I.A
(1.8)
T442 (er+1(s,)) ) 1041 or(s, [.411 A: s)))
(ii)
where the last inequality follows from the Hölder's inequality. Here we denote by || Iloo.A and ||- 1..44 the fo-- and fn-orsms defined on RIAI, respectively. In what follows, we upper bound (i) and (ii) on the right-hand side of (L.8) respectively.
Upper Bounding (i) in (I.8). Recall that define
8; - (Ta+1 0.+1 0,) -argmin [((,)) aEB
J((
Thus, it holds that 8, e B and |6 - Winst 2 < R. where Wintt is the initial parameter. In what follows, denote by do the feature mapping defined in (3.3) with 0 Wmit- Then for all (s,a) x A, we have
[0,(s, a)T (Ti+1 0;+1 Ti 0.)1 10: a) T5l
S 17 (1oo(s, a) Wmitt + (0:(s, 6, 0z(s, a) To (dr(s, 0, Φ0(8, (od(s,))TWaal Winit)) 5n (Mo + (s a)ll ||o, 0,112 + (s. a) T 0; do a) Wiintt)
(I.9)
where the first inequality follows from the triangle inequality, the second inequality follows from the Cauchy-Sehwartz, inequality, and Mo is defined by
Mo = sup 1Øo(s, a) Wintel- (a.0)ESxA
(L.10)
In what follows, we upper bound the right-hand side of (I.9). Note that Ti-1 + = TV. Therefore, we obtain that
110 - Wintella S T--ITT 10.-1 - Winit ll2 + n/T; 11,,-11 - Winit ll2:
(L.II)
which holds for all i >> 1. Recursively, since 0 = Winit E B and 8, E B for all i E [T], it then follows from (I. that 0, E B for all i [T'] Thus, holds that ||,; 0.112 < 2R. Meanwhile, following from (3.3), it holds for all A E Rend and (s, E S x A that [| a) 12 S 1. Therefore, we obtain that
[0, a)ll 1| 0.l12 2 2R, ((s,a)
(1.12)
remains to upper bound (s, a) TT,, (0ss T Wiall for all (s, E S A. which equal to (.f((s,); 6)) f((s, a); Wini)l by (I.7). Recall that f((-.):0) is differentiable with respect to 0 E IRmd almost everywhere, and the gradient Voʃ = ([Vas] .........., ...., (VollT) is given by
by Fm
[Vflr(s,
I((ssa)TT [0) > 0} (s, a) = (s,),) ((s,))
40

---

Published conference paper at ICLR 2020
where Φ0(8. a) is defined in (3.3). Since 1, a)ll2 a))l2 - 1 for all 0 E Rend and (s,a) S x A, we obtain for all (s.a) E x that
lo:(s, a) 00= Φ0(8,,)) Winitl
|5((s, a): 0.) (({,
S sup BER md
Vof 0) 10: Winit
sup
160(s,0))l: 10, - Winit S R, (L.13)
BERwd
where the last inequality holds since 0; B.
By plugging (1.12) and (1.13) into (I.9), we have
T+41 (s(ss a) 0,+1 T; (s a) 0,1 S n (Mo + +3R), Exx,
where Mo defined in (1.10). Therefore, it holds for all 8 E S that
|+ d 0:+ (s, "Bllloo.A = sup TT+1 oi(s, a) 8,41 0)(,
aEA
5 (Mo + 3R).
(1.14)
Finally, by the Pinsker's inequality, follows from (1.14) that [s,(s,,) (T++1 0:41 0:)1 1-4,(-1111101 II DRL (T n (Mo + 3R) ||T+ (- |) ( .)]| 1/2 || (: () m.( s)ll (L.15)
By completing the squares, we further upper bound the right-hand side of (1.15) by
[1 (((s))))(TT)))))) O.+1 (.))))) | | 1) DKL m)[[==(() (-1s))
-112 (1 (-1 - (-(11)))l1.4
(Mo + 312)) 1/2 17² (Mo + 3R))
11/2-17 (Mo + 3R)) < ,7 (M3 + 9/²",,
(1.16)
which holds for all 8 E S. Here the last inequality follows from the fact that (x + y)² - 2x.2 + 22y2.
Upper Bounding (ii) in (1.8). It holds for all s S that
(0++1(8,)) ) T0 (s, T 0,41, (.(1s), s))
< (1, (T -0 ) O Te (=)])))]] (s, T0+1 (1(s,-) (T Oc41, T++1611)) 0:+1
< [|0141(8, )) 00+1 - d2( )) 0.41llme.1 + 11 ) 0,+1 - 01(8,)) TT 0041llmenn 1.1- (I.17)
Here for any distribution π E P(AA), we denote by || 1| the - which is defined by
||u||z,p /EDEA (aa) (Iu(a))111 Following from Assumption 4.2 and Lemma E.2, it holds that
E Ev. [11 -) T00+ ou(s, ( To 00tallzaa]]
E[ (1, To To((:.)To0 0e+ [1 O(R3/2 mm:.:/mmm11 m 1144)
E E, (s. T) T0411 -o(s, TT
0 (4+1)
S (-( 0,-1 -o(: (o 0,+1 = 0(13/2 m m-144,,
(I.18)
where the inequalities follow from the Cauchy-Schie Schwwatt inequality, and the expectations are taken over all the randomness. Mcanwhile, it holds that
|| T T0 - (.(s. 0.41 1 0.+1 (s T 0.4 ()) 0..1 do(s, 10411lla,..
(I.19)
Combining (L.18) and (I.19), we obtain that
E Ev. [1l T
0c41 (1(3,))) T0.41 = (111//)
m
(I.20)
Similarly, it holds that E,, [1l041((,,) T 0i(0, T = 0(R3/2. 1188/2mm1111 -1/4),
(I.21)
41

---

Published conference paper at ICLR 2020
where the expectation is taken over all the randomness. By plugging (1.20) and (I.21) into (I.17,, we obtain that
7++1 IE
Bv. (1(0++1(s,)) 0:+1 (i(s.)) T0
A.( [ ((41,
O(T+1 R3/2 m 1/14.) (I.22)
Finally, by plugging (1.16) and (1.22) into (1.8), it holds under Assumptions 4.2 and A.3 that
E Ey. [[ [1og(
(++ m- s)) .T. x=-1(-1s))]]
- Ey, |KL ( () (. }))]
+ + (9R2 + M²) + 0(T+1 R m 11/1),
where M is the absolute constant defined in Assumption A.3. Thus, we complete the proof of Lemma H.2.
1.3 PROOF OF LEMMA H.3
Proof. Note that ExO, (0o, a')] and Ero, (s, depend solely on 8 E S, where we write Eme, (ov, (8,, (s, = Ea'NNO, ( (e) so0, (s, a')] for notational simplicity. Thus, we have
(Exo, [obo, (8. a 6, ow, a') a0]] (-(111)) x,(- [8)) 0, Es Meanwhile, following from the parameterization Ty in (3.2) and (I.6) in 51.2, we obtain that (log( (T (-15)/ s)) - Qwi (s, (-1s) - x.(-1s)
(I.23)
= (T++1 00,, (8. 0z+1 Tq (8,
n thes .) Tw;, "W,,,"'( (- T.(- (1))))))- (I.24)
In what follows, we define ()(-).) (-1-)) (.( (.1.) for notational simplicity. Then, combining (1.23) and (1.24), we obtain for all E S that
(log( (log(=:11(-11 8) T/( 8)) - Qwi (s, -), (-1ss))
7 (00, (s, TT 6r Pu, Lur ww, A {))
T+11 . (0o. (s, 8,41 - Φe. (s, ( 0.+1, A/(:
= 7 (0, (8, :) To, - pam (s, Wi, Twi,
(I.25)
Ts+1 . (00.4 (s, 0.41 Φe. (s, ( T0+1, A.(sss)
(iv)
where on and Φ., are the centered feature mappings defined in (B.2) that correspond to f and wi respectively, and ò; is defined by
6 = 1 (Te+1 0.+1- T; 0.) argmin [],
&J
(I.26)
WEB
In what follows, we upper bound the expectations of (iii) and (iv) over all the randomness separately.
Upper Bounding (iii) in (I.25). It holds that
E, [100, (8. To, - -e,, (8, W3s T.,,
SxA oo as) To 6,
-., (s) Too ww (s,
=// J0 (s, To 5. -
(s, will do do; (s,a)do((ssa)
$ 3i 1 (3.)) - - (.. Walloa.
(I.27)
42

---

Published conference paper at ICLR 2020
where do, /do; is the Radon-Nikodym derivative, yi; is defined in (A.1) of Assumption A.2, and the last inequality follows from the Cauchy- Saucch-Schwartz inequality. Similarly, it holds that
Ey, [1 (s, 8, - - (s,a) wi, (a s)Xl
/ 0 (8, (8) 5. - p., a) wi d (s) vs(
SXA
SXA 10 (8.00 8, - (u, a) will du (s)d,
/
du
2/4 (0, (:.-) - (...) Twillo.
(I.28)
where /vv/dv; is the Radon-Nikodym derivative, th is defined in (A.1) of Assumption A.2, and the last inequality follows from the Cauchy-Schwar inequality. Combining (I.27) and (1.28), we obtain that
Tw; EP, (100 (8, " d: T., (8, wi, (76-1))
$ (p) v/)) -1000, (:,.) To, --, ( willow
(I.29)
It now suffices to upper bound 1 (T:))To, (: (T: With a slight abuse of notation, we write के. Φo, (:) and o.. (..( hereafter for notational simplicity. Note that
118, σo. wi wi VBo, [(6] 0.. Tun) (6, 9o. Pm))
$ (6, wi) TEo 000- (6, do. - w/ Twn)]l
(1.30)
(iii.a)
/ BBo Eo, [(w] 0o. w/ (m)) (0, Qu. w, [1)0)
(iii.)
We now upper bound the expectations of the right-hand side of (I.30) over all the randomness.
Upper Bounding (iii.a) in (I.30). Note that w; 6g E B, where &; is defined in (I.26) and B = {ax Ignd ||a - Winttla S R3. Therefore, we obtain that
||ا; & S 2R.
(1.31)
Meanwhile, following from Proposition 3.1 and (3.7), holds that
E,, [(.)) F(,)) T?² Eo; 0o, (0), Es, V (5o.)) = T2 E., To. (ow,) Twi].
(I.32)
where the expectations are taken over o; given 0, and w, In what follows, we write di = E,, [Too)) for notational simplicity, where the expectation is taken over a; given 0 and wi. By plugging (I.31) and (I.32) into (iii.a) in (I.30), we obtain that
(5: - w Eo,, [0e. (8 0o. w/ 2e (0))))]== = 1 - wi) (F)((F(()) 6, - Ti gi)l
2R T [[F(,)) 8, - T. gill2, (I.33)
where the last inequality follows from the Cauchy-Schward inequality and (I.31). By (1.33), we have
166 ww) To, (o (6, 0o. - w/ T 2/ s C. E (1 (
& - T, 9.] sllll) l1)))) 1/2
SC. E (1)(()) o, - VoJ(To,)) (o))) '2]
SQ. (l.))(()) d, - F.J(TO) M1 + [1 1/2
(I.34)
43

---

Published conference paper at ICLR 2020
where the expectations are taken over all the randomness. Here the last inequality follows from the Jensen's inequality, C; = /2R T, and ((() is defined by
(,.) F(0.)) 6, - (To) (F(O:) 6, Ti 9:).
(I.35)
In what follows, we upper bound [[.().) 6; - VoJ(TT))l on the right-hand side of (I.34). Recall that we define by
6, = = (T++1 0.11 ..) = argmin wEB
[[((0)) - VoJ(To))
(I.36)
Therefore, since wi E B, we obtain from (1.36) that
[P(0.) 6, - Ti (TO )l2 S [1F(),)) wi - TI VoJ(TT))
[(:(:: we gill2 + [1::(w)))2:
(I.37)
where recall that, similar to (I.35), we define (w;) by
E((w)) = (0..)
VoJ(TO,) (F(O.) wi 7s 9))
(1.38)
By plugging (L.77) into (I.34), we obtain that
E (6, wi) T Eo, Too. (0,T0, oa. - -w, p.. (0)))11
1/2
s C. (E(.BBI(()))) wi 96ll2] + (l(( + ([]))((a;))) [2]
(I.39)
where C₁ = /2R T- and & (,)), (i(w)) are defined in (L.35) and (I.38), respectively, To upper bound the right-hand side of (I.39), it now suffices to upper bound the expectation ((I) wa Ts gilla], By (I.32), we obtain that
[(0,)) w. Ti 9oll2 =² Eo. 00 (0n. - - )
Tws]
$ T, E., [1ō0, (oo: - -,, TT, woll2] = 7ē E., [1 1l2 16o, - -T,,)
(L.40)
where the inequality follows from the Jensen's inequality. In what follows, we upper bound the right-hand side (I.40). Note that 11 (8, a)ll2 < 2 for all a) E A. By further plugging into (L.40), we obtain that
[(())) wi Ti 9:l12 - 2T,² 1E,, |(oo, Tw.ll s 2T? 11(0,. )w.) willa,, Twillay
(I.41)
where the last inequality follows from the Jensen's 's inequality. Recall that wi, 02 B. Therefore, by Assumption 4.2 and Corollary E.3, we have
E [[][o, - "w.) Twi [..]
[ - Φ0) wi 1:11o.1+
V.. = O(R3/2 m -1/14)
(I.42)
where the expectations are taken over all the randomness. Combining (I.41) and (I.42), we obtain that
E ((e.) wi T. 9:l12] - 0(2 R²/2 m 1/4),
(I.43)
where the expectation is taken over all the randomness. Finally, by plugging (I.43) into (I.39), we conclude that
R (0: wi) TE,, po. (o. th. - -.T (1
S. (E(IF((8.) wi - To gille] + E [[1lE((())ll)) + ([II)((0)111]] 1/2
= 5 m 118 + 22 T, [1, [[((())))2)
(I.44)
where C, = V2R T; and (5,),, (wx) are defined Assumption A.1.
44

---

Published conference paper at ICLR 2020
Upper Bounding (iii.b) in (I.30), Following from the Cauchy-Schwartz inequality, it holds that Es, [w]To. ou)) (6, Pu. w [nn) 2 (112) do; w/ Ows lla 110, 0o. wi wwilla;) 1/2
(I.45)
To upper bound the right-hand side of (I.45), we first upper bound ||W! do. - w/ ow Ilo. Recall that Wi, 0 B. Following from Assumption 4.2 and Corollary E.3, it holds that
E ||: o. wi o lla O m 1/2),
E I|, Pu. - w, @olle.1 O(R m 1/2).
(I.46)
where 6n is defined in (B.1) and the expectations are taken over all the randomness. following from (I.46), we obtain that
Therefore,
[| 0o. w/ T 12.1 S 2E [|]] de. w &oll3, + -B [Iw]] dw. - wT volll - O(R2 - m 1/2).
(I.47)
It remains to upper bound 16 &g. - w/ uw lla, on the right-hand side of (I.45). Since 8; E B, by Assumption 4.2 and Corollary E.3, we obtain that
E 1 do. - of volle,1 O m 1/3),,
(I.48)
where the expectation is taken over all the randomness. Meanwhile, following from the fact that (s, a)ll2 I for all (s E S x A, we obtain that
1 ( a) - wi (
1 (s)al22 11 will2 S 4R, V(s ES
(I.49)
where the first inequality follows from the Cauchy-Schwand inequality and the second inequality follows from the fact that w/ E B. Combining (I.46), (I.48), and (I.49), we obtain that
E [1102] oo. wi p., [Ie] S 3E [1|8] oo. 8. 101._ 3E [|5, Φ w/ 201
+ 3E [[|,] p... w o - O(R² + R m 11/2),
(I.50)
where the expectations are taken over all the randomness. Finally, plugging (I.47) and (I.50) into (I.45), we obtain that
Far, [ww) tb. w/ w,, (0, 0o, - -w m1 1/2
E
1/2
E ||w pe. - -uiTon. p., llo. ||0, 0Ø. - w, Ja, [1a]]
12 Ilw 30. - pe, 12.] [B(10 Φo. - wT Tur
-T,
323222 1/4 R5/4 m 1/8).
(I.51)
where the inequalities follow from the Cauchy-Schward inequality and the expectations taken over all the randomness.
Finally, by plugging (I.44), (I.51), and (I.30) into (I.29), we obtain that
E Ev. [l(60, (s.-) TT, 8, Ja, (T,,))ww, ws, AT( (((]))))]]
s))1]
n (p + vhr) (O(R3/1 1m11// R3/2 /2 . m-14/)
(I.52)
+ 122 (Bll) [[((w))])]] 1/3
where (d(5)) and (e(ws) are defined in Assumption A.1. Here the expectations taken over all the randomness.
45

---

Published conference paper at ICLR 2020
Upper Bounding (iv) in (I.25). The analysis of (iv) is similar to that of (ii) in 5H.8. It holds that
1000, (s 81+1 - Φ0, (s. 0 A [s)]
$ (00 (s.-) ( 01+1
60, 60, (s, 0.11 x (-1s)) + 1(00. (s.-)) T 6o, (s, Dct1 ms(-1s)) - |100.+1 , (s, - 0x+1 - Φb, (5, 0,41llx + l (s, )) 01+1 - Φe, 000-1lm.11 (1.53)
Note that 8, 1 E B. Following from Assumption 4.2 and Lemma E.2, it holds that
B Ev. [1 (s, ) 0 Φ0(3. ( 1 [1r
< Ellloo. 11 (3.) (.)000+1 0.+1 oo(: ( 01t1ll..] = 0 m mm1)4),
E Ev. [1100, ( [14+1 00(s,,) T
0.+1 [|]
$ [ To co((.)) 0 1lo..] 0011/2.m-1111
m
(I.54)
where the inequalities follow from the Jensen's 's inequality, du is the feature mapping defined in (3.3) with 0 = Wint. and the expectations are taken over all the randomness. Following from (I.54), we obtain that
E Ev. |1 (8, ) 0,+ co, (8, T ('0+11ll=..) [|
$ Ev. [1loo,1 (s, .) T 0.+1 - do(s. :) 01+1 [|r
Ey. [1 (8, T ()) [ctalbasa]] O 1/4),
(I.55)
where the expectations are taken over all the randomness. Similarly, it holds that
E Ep. [lloe, (s, [T0++ - Φe, (s. ( 01t1llmaa]] = 0 m 1111).
(I.56)
By plugging (L.55) and (1.56) into (I.53), we obtain that
E Ev, [1 (s. 0.+1 Φ0, (s. 0
= - m mm1/))
(L.57)
Finally, by plugging (I.52) and (I.57) into (I.25), we obtain that
E Ep, (log((T(-1f)) s)/ क. s)) 17 Qw (s. =. (.1s) a. }]}{]
S V2(pp. + 0x) 17 R1/2 Ti f [1lE: [2] B[Il(((x)112] 1/2
+ + R3/2 m 1/4 + v R²/4 m 1/5))
1/4
where pps 4/; are defined in Assumption A.2 and (6))),, (ww, are defined in Assumption A.1. Thus, we complete the proof of Lemma H.3.
AUXILLIARY LEMMA
Lemma J.1 (Performance Difference (Kakade and Langford, 2002)). It holds for any and ă that J( J(z) - 7) Ei.u [AT(s,a)]
Here us is the state visitation measure corresponding to म. which is defined in (2.3).
Proof. See Kakade and Langford (2002) for a detailed proof.
46


Reviews:
[{"review_id": "HygSQAMAYr", "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 studies policy gradient where the policy is parameterized by an extremely wide neural network. The authors assume that the number of nodes ($m$) in the network is extremely large ($T^{8}R^{18}$, $T$ is the total runtime and $R$ is the radius of the function class that the network falls into), and they restrict their convergence analysis of the policy gradient algorithm in a particular function class and claims that the approximation error between the true network and the function class goes to zero when $m$ is large. The paper is written in a rigorous way and the presentation is mostly clear. I have some concerns about many of the assumptions made across the paper that are not explained or verified. This may potentially further decrease the usefulness of the analysis in this paper though the theoretical result with $m=T^8$ is already very impractical. Another major issue with this paper is that the theoretical analysis is not novel in terms of bringing new insights and results to the field given many other papers including global convergence of policy gradient (Agarwal et al., 2019;), convergence of neural TD learning (Cai et el., 2019), theory for overparameterized neural networks (Jacot et al., 2018; Allen-Zhu et al., 2018a;b; Du et al., 2018a;b; Zou et al., 2018; Chizat and Bach, 2018; Jacot et al., 2018, etc.) and other very similar papers. \n\nThere is a prior work by Agarwal et al. (2019) that proves the global convergence of both vanilla policy gradient and natural policy gradient methods. In the related work, the authors distinguish their paper from that of Agarwal et al. (2019) by claiming that they are studying the non-tabular setting and they use the actor-critic scheme. However, the first claim is incorrect because Agarwal et al. (2019) also studied the non-tabular setting (see Section 6 in Agarwal et al. (2019)) and proved an O(1/\\sqrt{T}) convergence rate. Moreover, the actor-critic scheme in this paper is just a trivial modification of the nonlinear policy gradient method by calling existing result for TD learning in Cai et al. (2019). Therefore, the contribution of this paper is not so clear given existing papers.\n\nIn Algorithm 1, the policy gradient estimator $\\widehat{\\nabla} J(\\pi_{\\theta_i})$ also depends on the critic parameter $\\omega_i$. It is better to show this dependency in the notation as well.\n\nIn Algorithm 1, the temperature parameter $\\tau_i$ is updated in natural policy gradient but not in vanilla policy gradient. It seems that $\\tau_i$ increases linearly with $i$, which makes the policy defined in eq (3.1) close to a uniform distribution when the time horizon goes to infinity. This seems to offset the update of parameter $\\theta_i$.\n\nIn the update of natural policy gradient, solving eq (3.8) is really expensive in computation, especially in the setting of this paper where $m$ is chosen as $T^{8}$. It seems impossible to obtain a reasonable solution within the claimed $O(1/T^{1/4})$ runtime.\n\nWhat is the function $\\iota(w)$ in Assumption 4.1?\n\nIt would be better for the authors to discuss more about Assumption 4.1. It is unknown why the action-value function $Q^{\\pi}$ for all policy can fall into this class. \n\nThe equation in Assumption 4.2 is exceeding the paper margin. Please make sure the paper follows the format guidelines.\n\nAssumption 4.2 seems to be very strong. The remark after the assumption says that this condition is made on the Markov transition kernel. However, this may not be true since the assumption needs to hold for any two arbitrary policies. It is not known what kind of transition kernel $\\mathcal{P}$ will satisfy this.\n\nIn each step of the neural policy gradient (Algorithm 1), the authors need to call a TD learning (Algorithm 2) to approximate the unknown action-value function $Q_{\\omega_i}$ associated with the policy $\\pi_{\\theta_i}$ at the $i$-th step. It seems that in the learning process of ALgorithm 2, at each iteration, it samples independent data from the stationary state-action distribution which is unknown.  \n\nIn the proof of Theorem 4.8, it seems that eq (D.14) and (D.15) are the same. Why it needs to be proved twice? In addition, why the equation after (D.14) holds?\n\nThe authors should provide more details about the function $u_{\\hat \\theta}$ defined in eq (4.4), which seems to approximate the critic function. Specifically, why are there the derivative terms instead of just the inner product term in eq (4.4).\n\nOther comments:\nIn the last sentence of Section 3.1, “... approximate aompatible function approximation ...”\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "ByxGBAtpKS", "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": "\n[Summary]\nThis paper studies the convergence of actor-critic algorithms with two-layer neural networks under iid assumption. Theoretical results show that, in the aforementioned setting, policy gradient and natural policy gradient converge to a stationary point at a sublinear rate and natural policy gradient's solution is globally optimal. \n\n[Decision]\nI recommend accepting this paper. While these results may not have immediate practical interest, the analysis is an important step in understanding the behavior of actor-critic algorithms with neural networks. The final revision needs to be more clear on the limiting assumptions and include a conclusion section that assembles the results.\n\n[Comments]\nThe first important assumption is the architecture of the neural network. The results in the paper consider two-layer neural networks but the abstract implies that the analysis applies to general neural networks.\n\nThe second assumption is that the state-action pairs are sampled iid from the policy's stationary distribution. In reality, these samples are either gathered online (and are therefore temporally correlated), or from a buffer that is also affected by previous policies. The description of results in the abstract and introduction should clarify this setting.\n\nSection G in the appendix shows the analysis for the projection-free method. The projection radius (R) does not seem to play a role in the new algorithm, but the convergence rate still depends on R. Does R have a different definition in this context?\n\nSubsection 3.1 says \"without loss of generality, we keep b_r fixed at the initial parameter throughout training and only update W.\" Whether this modification affects the optimization of the neural network and its convergence rate is not obvious to me.\n\nThe paragraph above Theorem 4.7 defines the stationary point. Is this point guaranteed to, or assumed to, exist?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByerOV_aFH", "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": "This paper provides theoretical studies for neural policy gradient descents for reinforcement learning problems. The authors prove global optimality and rates of convergence of neural natural/vanilla policy gradient. Their results rely on the key factor for \"compatibility\" between the actor and critic. This is ensured by sharing neural architectures and random initializations across the actor and critic. \n\nThe paper is well written with clear derivations. I suggest the publication of this paper. ", "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 makes a solid contribution to understanding the convergence properties of policy gradient methods with over-parameterized neural network function approximators.  This work is concurrent with and not subsumed by other strong work by Agarwal et al. on the same topic.  There is sufficient novelty in this contribution to merit acceptance.  The authors should nevertheless clarify the relationship between their work and the related work noted by AnonReviewer2, in addition to addressing the other comments of the reviewers.
Decision: Accept (Poster)