Year: 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 under the overparameterized twolayer neural-network parameterization. In detail, assuming independent sampling, 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. 1

heading: 1 INTRODUCTION
text: In reinforcement learning (Sutton and Barto, 2018), an agent aims to maximize its expected total reward by taking a sequence of actions according to a 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-based optimization. As policy gradient methods are easily implementable and readily integrable with advanced optimization techniques such as variance 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-value function (critic) are parameterized by neural networks, policy 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 manipulation (Peters and Schaal, 2006; Duan et al., 2016), and natural language processing (Wang et al., 2018). See Li (2017) for a detailed survey.
In stark contrast to the tremendous empirical successes, policy gradient methods remain much less well understood in terms of theory, especially when they involve neural networks. More specifically, 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 nonconvex optimization, Papini et al. (2018); Shen et al. (2019); Xu et al. (2019a); Karimi et al. (2019);
∗equal contribution †Northwestern University; lingxiaowang2022@u.northwestern.edu ‡Northwestern University; qicai2022@u.northwestern.edu §Princeton University; zy6@princeton.edu ¶Northwestern University; zhaoranwang@gmail.com 1See https://arxiv.org/abs/1909.01150 for the full version.
Zhang et al. (2019) establish the rate of convergence of REINFORCE to a 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 a 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 a class are 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 temporal-difference update (Sutton, 1988). As a result, the estimated policy gradient may be biased, which possibly leads to divergence. Even if the algorithm converges to a 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 a stationary point remains unclear. The only exception is the linear-quadratic regulator (LQR) setting (Fazel et al., 2018; 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 twolayer 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 a 1/ √ T -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) divergence regularization, we prove that neural natural policy gradient converges to a globally optimal policy at a 1/ √ T -rate in the expected total reward. In particular, a 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 initializations for both the actor and critic, which is often used as a practical heuristic (Mnih et al., 2016). 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 (REINFORCE) 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; Xu et al., 2019a;b; Shen et al., 2019; Karimi et 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 improvement 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
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/ √ T -rates in the tabular and linear settings. In the tabular setting, their rate of 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 critics are parameterized by neural networks, and establish their 1/ √ T - 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.
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 et al., 2018; Wu 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; 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 Ω and p > 0, we define ‖f(·)‖µ,p = ( ∫ Ω |f |pdµ)1/p as the Lp(µ) norm of f . We define ‖f(·)‖µ,∞ = inf{C ≥ 0 : |f(x)| ≤ C for µ-almost every x} as the L∞(µ)norm of f . We write ‖f‖µ,p for notational simplicity when the variable of f is clear from the context. We further denote by ‖ · ‖µ the L2(µ)-norm for notational simplicity. For a vector φ ∈ Rn and p > 0, we denote by ‖φ‖p the `p-norm of φ. We denote by x = ([x]>1 , . . . , [x]>m)> a vector in Rmd, where [x]i ∈ Rd is the i-th block of x for i ∈ [m].

heading: 2 BACKGROUND
text: 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, ζ, r, γ). Here S and A are the sets of all possible states and actions, respectively. Meanwhile, P is the Markov transition kernel and r is the reward function, which is possibly stochastic. Specifically, when taking action a ∈ A at state s ∈ 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 S0 ∈ S and γ ∈ (0, 1) is the discount factor. In addition, policy π(a | s) gives the probability of taking action a at state s. We denote the state- and action-value functions associated with π by V π : S → R and Qπ : S × A → R, which are defined respectively as
V π(s) = (1− γ) · E [ ∞∑ t=0 γt · r(St, At) ∣∣∣∣ S0 = s], ∀s ∈ S, (2.1)
Qπ(s, a) = (1− γ) · E [ ∞∑ t=0 γt · r(St, At) ∣∣∣∣ S0 = s,A0 = a], ∀(s, a) ∈ S ×A, (2.2)
where S0 ∼ ζ(·), At ∼ π(· |St), and St+1 ∼ P(· |St, At) for all t ≥ 0. Also, we define the advantage function of policy π as the difference between Qπ and V π , i.e., Aπ(s, a) = Qπ(s, a) − V π(s). By the definitions in (2.1) and (2.2), V π and Qπ are related via
V π(s) = Eπ [ Qπ(s, a) ] = 〈Qπ(s, ·), π(· | s)〉,
where 〈·, ·〉 is the inner product in R|A|. Here we write Ea∼π(· | s)[Qπ(s, a)] as Eπ[Qπ(s, a)] for notational simplicity. Note that policy π together with transition probability P induces a Markov
chain over state space S. We denote by %π the stationary state distribution of the Markov chain induced by π. We further define ςπ(s, a) = π(a | s) · %π(s) as the stationary state-action distribution over S × A. Meanwhile, policy π induces a state visitation measure over S and a state-action visitation measure over S × A, which are denoted by νπ and σπ , respectively. Specifically, for all (s, a) ∈ S ×A, we define
νπ(s) = (1− γ) · ∞∑ t=0 γt · P(St = s), σπ(s, a) = (1− γ) · ∞∑ t=0 γt · P(St = s,At = a),
(2.3)
where S0 ∼ ζ(·), At ∼ π(· |St), and St+1 ∼ P(· |St, At) for all t ≥ 0. By definition, we have σπ(s, a) = π(a | s) · νπ(s). We define the expected total reward function J(π) by
J(π) = (1− γ) · E [ ∞∑ t=0 γt · r(St, At) ] = Eζ [ V π(s) ] = Eσπ [ r(s, a) ] , ∀π, (2.4)
where we write Eσπ [r(s, a)] = E(s,a)∼σπ(·,·)[r(s, a)] for notational simplicity. The goal of reinforcement learning is to find the optimal policy that maximizes J(π), which is denoted by π∗. When state space S is large, a popular approach is to find the maximizer of J(π) over a class of parameterized policies {πθ : θ ∈ B}, where θ ∈ B is the parameter and B is the parameter space. In this case, we obtain the optimization problem maxθ∈B J(πθ).
Policy Gradient Methods. Policy gradient methods maximize J(πθ) using∇θJ(πθ). These methods are based on the policy gradient theorem (Sutton and Barto, 2018), which states that
∇θJ(πθ) = Eσπθ [ Qπθ (s, a) · ∇θ log πθ(a | s) ] , (2.5)
where σπθ is the state-action visitation measure defined in (2.3). Based on (2.5), (vanilla) policy gradient maximizes the expected total reward via gradient ascent. Specifically, we generate a sequence of policy parameters {θi}i∈[T ] via
θi+1 ← θi + η · ∇θJ(πθi), (2.6) where η > 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 πθ, which is given by
F (θ) = Eσπθ [ ∇θ log πθ(a | s) [ ∇θ log πθ(a | s) ]>] . (2.7)
At each iteration, natural policy gradient performs
θi+1 ← θi + η · F−1(θi) · ∇θJ(πθi), (2.8)
where F−1(θi) is the inverse of F (θi) and η is the learning rate. In practice, both Qπθ in (2.5) and F (θ) in (2.7) remain to be estimated, which yields approximations of the policy improvement steps in (2.6) and (2.8).

heading: 3 NEURAL POLICY GRADIENT METHODS
text: In this section, we represent πθ by a 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).

heading: 3.1 OVERPARAMETERIZED NEURAL POLICY
text: We now introduce the parameterization of policies. For notational simplicity, we assume that S × A ⊆ Rd with d ≥ 2. Without loss of generality, we further assume that ‖(s, a)‖2 = 1 for all (s, a) ∈ S ×A. A two-layer neural network f((s, a);W, b) with input (s, a) and width m takes the form of
f ( (s, a);W, b ) =
1√ m m∑ r=1 br · ReLU ( (s, a)>[W ]r ) , ∀(s, a) ∈ S ×A. (3.1)
Here ReLU: R → R is the rectified linear unit (ReLU) activation function, which is defined as ReLU(u) = 1{u > 0} · u. Also, {br}r∈[m] and W = ([W ]>1 , . . . , [W ]>m)> ∈ Rmd in (3.1) are the parameters. When training the two-layer neural network, we initialize the parameters via [Winit]r ∼ N(0, Id/d) and br ∼ Unif({−1, 1}) for all r ∈ [m]. Note that the ReLU activation function satisfies ReLU(c · u) = c · ReLU(u) for all c > 0 and u ∈ R. Hence, without loss of generality, we keep br fixed at the initial parameter throughout training and only update W in the sequel. See, e.g., Allen-Zhu et al. (2018b) for a detailed argument. For notational simplicity, we write f((s, a);W, b) as f((s, a);W ) hereafter.
Using the two-layer neural network in (3.1), we define πθ(a | s) = exp [ τ · f ( (s, a); θ )]∑ a′∈A exp [ τ · f ( (s, a′); θ
)] , ∀(s, a) ∈ S ×A, (3.2) where f((·, ·); θ) is defined in (3.1) with θ ∈ Rmd playing the role of W . Note that πθ defined in (3.2) takes the form of an energy-based policy (Haarnoja et al., 2017). With a slight abuse of terminology, we 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 φθ = ([φθ]>1 , . . . , [φθ] > m) > : Rd → Rmd of a two-layer neural network f((·, ·); θ) as
[φθ]r(s, a) = br√ m · 1 { (s, a)>[θ]r > 0 } · (s, a), ∀(s, a) ∈ S ×A, ∀r ∈ [m]. (3.3)
By (3.1), it holds that f((·, ·); θ) = φθ(·, ·)>θ. Meanwhile, f((·, ·); θ) is almost everywhere differentiable with respect to θ, and it holds that∇θf((·, ·); θ) = φθ(·, ·). In the following proposition, we calculate the closed forms of the policy gradient ∇θJ(πθ) and the Fisher information matrix F (θ) for πθ defined in (3.2). Proposition 3.1 (Policy Gradient and Fisher Information Matrix). For πθ defined in (3.2), we have
∇θJ(πθ) = τ · Eσπθ [ Qπθ (s, a) · ( φθ(s, a)− Eπθ [ φθ(s, a ′) ])] , (3.4)
F (θ) = τ2 · Eσπθ [( φθ(s, a)− Eπθ [ φθ(s, a ′) ])( φθ(s, a)− Eπθ [ φθ(s, a ′) ])>] , (3.5)
where φθ(·, ·) is the feature mapping defined in (3.3), τ is the temperature parameter, and σπθ is the state-action visitation measure defined in (2.3). Here we write Eπθ [φθ(s, a′)] = Ea′∼πθ(· | s)[φθ(s, a′)] for notational simplicity.
Proof. See §H.1 for a detailed proof.
Since the action-value function Qπθ in (3.4) is unknown, to obtain the policy gradient, we use another two-layer neural network to track the action-value function of policy πθ. Specifically, we use a two-layer neural network Qω(·, ·) = f((·, ·);ω) defined in (3.1) to represent the action-value function Qπθ , where ω plays the same role as W in (3.1). Such an approach is known as the actorcritic 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, a shared architecture and random initialization between the actor Qω and the energy function of critic πθ ensures approximate compatible function approximations. See §B for details.

heading: 3.2 NEURAL POLICY GRADIENT METHODS
text: Now we present neural policy gradient and neural natural policy gradient. Following the actor-critic scheme, they generate a sequence of policies {πθi}i∈[T+1] and action-value functions {Qωi}i∈[T ].

heading: 3.2.1 ACTOR UPDATE
text: As introduced in §2, we aim to solve the optimization problem maxθ∈B J(πθ) iteratively via gradient-based methods, where B is the parameter space. We set B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}, where R > 1 and Winit is the initial parameter defined in §3.1. For all i ∈ [T ], let θi be the
policy parameter at the i-th iteration. For notational simplicity, in the sequel, we denote by σi and ςi the state-action visitation measure σπθi and the stationary state-action distribution ςπθi , respectively, which are defined in §2. Similarly, we write νi = νπθi and %i = %πθi . To update θi, we set
θi+1 ← ΠB ( θi + η ·G(θi) · ∇̂θJ(πθi) ) , (3.6)
where we define ΠB : Rmd → B as the projection operator onto the parameter space B ⊆ Rmd. Here G(θi) ∈ Rmd×md is a matrix specific to each algorithm. Specifically, we have G(θi) = Imd for policy gradient and G(θi) = (F (θi))−1 for natural policy gradient, where F (θi) is the Fisher information matrix in (3.5). Meanwhile, η is the learning rate and ∇̂θJ(πθi) is an estimator of ∇θJ(πθi), which takes the form of
∇̂θJ(πθi) = 1 B · B∑ `=1 Qωi(s`, a`) · ∇θ log πθi(a` | s`). (3.7)
Here τi is the temperature parameter of πθi , {(s`, a`)}`∈[B] is sampled from the state-action visitation measure σi corresponding to the current policy πθi , and B > 0 is the batch size. Also, Qωi is the critic obtained by Algorithm 2. Here we omit the dependency of ∇̂θJ(πθi) on ωi for notational simplicity. See §C for the sampling from visitation measures.
Inverting Fisher Information Matrix. Recall that G(θi) is the inverse of the Fisher information matrix used in natural policy gradient. In the overparameterized regime, inverting an estimator F̂ (θi) of F (θi) can be infeasible as F̂ (θi) is a high-dimensional matrix, which is possibly not invertible. To resolve this issue, we estimate the natural policy gradient G(θi) · ∇θJ(πθi) by solving
min α∈B ‖F̂ (θi) · α− τi · ∇̂θJ(πθi)‖2, (3.8)
where ∇̂θJ(πθi) is defined in (3.7), τi is the temperature parameter in πθi , and B is the parameter space. Meanwhile, F̂ (θi) is an unbiased estimator of F (θi) based on {(s`, a`)}`∈[B] sampled from σi, which is defined as
F̂ (θi) = τ2i B · B∑ `=1 ( φθi(s`, a`)− Eπθi [ φθi(s`, a ′ `) ])( φθi(s`, a`)− Eπθi [ φθi(s`, a ′ `) ])> , (3.9)
where a′` ∼ πθi(· | s`) and φθi is defined in (3.3) with θ = θi. The actor update of neural natural policy gradient takes the form of
τi+1 ← τi + η, τi+1 · θi+1 ← τi · θi + η · argmin α∈B ‖F̂ (θi) · α− τi · ∇̂θJ(πθi)‖2, (3.10)
where we use an arbitrary minimizer of (3.8) if it is not unique. Note that we also update the temperature parameter by τi+1 ← τi + η, which ensures θi+1 ∈ B. It is worth mentioning that up to 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, at the i-th iteration, neural policy gradient obtains θi+1 via projected gradient ascent using ∇̂θJ(πθi) defined in (3.7). Meanwhile, neural natural policy gradient solves (3.8) and obtains θi+1 according to (3.10).

heading: 3.2.2 CRITIC UPDATE
text: To obtain ∇̂θJ(πθ), it remains to obtain the critic Qωi in (3.7). For any policy π, the action-value function Qπ is the unique solution to the Bellman equation Q = T πQ (Sutton and Barto, 2018). Here T π is the Bellman operator that takes the form of
T πQ(s, a) = E [ (1− γ) · r(s, a) + γ ·Q(s′, a′) ] , ∀(s, a) ∈ S ×A,
where s′ ∼ P(· | s, a) and a′ ∼ π(· | s′). Correspondingly, we aim to solve the following optimization problem
ωi ← argmin ω∈B
Eςi [( Qω(s, a)− T πθiQω(s, a) )2] , (3.11)
where ςi and T πθi are the stationary state-action distribution and the Bellman operator associated with πθi , respectively, and B is the parameter space. We adopt neural temporal-difference learning (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
ω(t+ 1/2) ← ω(t)− ηTD · ( Qω(t)(s, a)− (1− γ) · r(s, a)− γQω(t)(s′, a′) ) · ∇ωQω(t)(s, a), (3.12)
ω(t+ 1)← argmin α∈B ‖α− ω(t+ 1/2)‖2, (3.13)
where (s, a) ∼ ςi(·), s′ ∼ P(· | s, a), a′ ∼ π(· | s′), and ηTD 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. Meanwhile, the state-action pairs in (3.12) are sampled from the stationary state-action distribution ςi, which is achieved by sampling from the Markov chain induced by πθi until it mixes. See Algorithm 2 in §F for details. Finally, combining the actor updates and the critic update described in (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 η, learning rate ηTD
of neural TD, temperature parameters {τi}i∈[T+1], batch size B. 1: Initialization: Initialize br ∼ Unif({−1, 1}) and [Winit]r ∼ N(0, Id/d) for all r ∈ [m]. Set B ← {α ∈ Rmd : ‖α−Winit‖2 ≤ R} and θ1 ←Winit. 2: for i ∈ [T ] do 3: Update ωi using Algorithm 2 with πθi as the input, ω(0) ← Winit and {br}r∈[m] as the initialization, TTD as the number of iterations, and ηTD as the learning rate. 4: Sample {(s`, a`)}`∈[B] from the visitation measure σi, and estimate ∇̂θJ(πθ) and F̂ (θi) using (3.7) and (3.9), respectively. 5: If using policy gradient, update θi+1 by
θi+1 ← ΠB ( θi + η · ∇̂θJ(πθi) ) .
If using natural policy gradient, update θi+1 and τi+1 by
τi+1 ← τi + η, τi+1 · θi+1 ← τi · θi + η · argmin α∈B ‖F̂ (θi) · α− τi · ∇̂θJ(πθi)‖2.
6: end for 7: Output: {πθi}i∈[T+1].

heading: 4 MAIN RESULTS
text: In this section, we establish the global optimality and convergence for neural policy gradient methods. Hereafter, we assume that the absolute value of the reward function r is upper bounded by an absolute constant Qmax > 0. As a result, we obtain from (2.1) and (2.2) that |V π(s, a)| ≤ Qmax, |Qπ(s, a)| ≤ Qmax, and |Aπ(s, a)| ≤ 2Qmax for all π and (s, a) ∈ S × A. In what follows, we show that neural policy gradient converges to a stationary point of J(πθ) with respect to θ at a sublinear rate. We further characterize the geometry of J(πθ) and establish the global optimality of the obtained stationary point. We defer the global optimality and convergence of neural natural policy gradient to §A. In the sequel, we study the convergence of neural policy gradient, i.e., Algorithm 1 with (3.6) as the actor update, where G(θ) = Imd. In what follows, we lay out a regularity condition on the action-value function Qπ .
Assumption 4.1 (Action-Value Function Class). We define FR,∞ = { f(s, a) = f0(s, a) + ∫ 1 { w>(s, a) > 0 } · (s, a)>ι(w)dµ(w) : ‖ι(w)‖∞ ≤ R/ √ d } ,
where µ : Rd → R is the density function of the Gaussian distribution N(0, Id/d), f0(·, ·) = f((·, ·);Winit) is the two-layer neural network corresponding to the initial parameter Winit, and ι : Rd → Rd together with f0 parameterizes the element of FR,∞. We assume that Qπ ∈ FR,∞ for all π.
Assumption 4.1 is a mild regularity condition on Qπ , as FR,∞ captures a sufficiently general family of functions, which constitute a subset of the reproducing kernel Hilbert space (RKHS) induced by the random feature 1{w>(s, a) > 0} · (s, a) with w ∼ N(0, Id/d) (Rahimi and Recht, 2008; 2009) up to the shift of f0. 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 νπ and the stationary state distribution %π .
Assumption 4.2 (Regularity Condition on νπ and %π). Let π and π̃ be two arbitrary policies. We assume that there exists an absolute constant c > 0 such that
Eπ̃·νπ [ 1 { |y>(s, a)| ≤ u }] ≤ c · u/‖y‖2,
Eπ̃·%π [ 1 { |y>(s, a)| ≤ u }] ≤ c · u/‖y‖2, ∀y ∈ Rd, ∀u > 0.
Here the expectations are taken over the joint distributions π̃(· | ·) · νπ(·) and π̃(· | ·) · %π(·) over S ×A, respectively.
Assumption 4.2 essentially imposes a regularity condition on the Markov transition kernel P of the MDP as P determines νπ and %π for all π. Such a regularity condition holds if both νπ and %π 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 ηTD = min{(1 − γ)/8, 1/ √ TTD} in Algorithm 1. Let Qωi be the output of the i-th critic update in Line 3 of Algorithm 1, which is an estimator of Qπθi obtained by Algorithm 2 with TTD iterations. Under Assumptions 4.1 and 4.2, it holds for TTD = Ω(m) that
Einit [ ‖Qωi −Qπθi‖2ςi ] = O(R3 ·m−1/2 +R5/2 ·m−1/4), (4.1)
where ςi is the stationary state-action distribution corresponding to πθi . Here the expectation is taken over the random initialization.
Proof. See §F.1 for a detailed proof.
Cai et al. (2019) show that the error of the critic update consists of two parts, namely the approximation error of two-layer neural networks and the algorithmic error of neural TD. The former decays as the widthm grows, while the latter decays as the number of neural TD iterations TTD in Algorithm 2 grows. By setting TTD = Ω(m), the algorithmic error in (4.1) of Proposition 4.3 is dominated by the approximation error. In contrast with Cai et al. (2019), we obtain a more refined convergence characterization under the more restrictive assumption that Qπ ∈ FR,∞. Specifically, such a restriction allows us to obtain the upper bound of 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 ∇̂θJ(πθi) of the policy gradient ∇θJ(πθi) based on {(s`, a`)}`∈[B]. We introduce the following regularity condition on the variance of ∇̂θJ(πθi). Assumption 4.4 (Variance Upper Bound). Recall that σi is the state-action visitation measure corresponding to πθi for all i ∈ [T ]. Let ξi = ∇̂θJ(πθi)−E[∇̂θJ(πθi)], where ∇̂θJ(πθi) is defined in (3.7). We assume that there exists an absolute constant σξ > 0 such that E[‖ξi‖22] ≤ τ2i · σ2ξ/B for all i ∈ [T ]. Here the expectations are taken over σi given θi and ωi.
Assumption 4.4 is a mild regularity condition. Such a regularity condition holds if the Markov chain that generates {(s`, a`)}`∈[B] mixes sufficiently fast and Qωi(s, a) with (s, a) ∼ σi have upper
bounded second moments for all i ∈ [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 a regularity condition on the discrepancy between the state-action visitation measure and the stationary state-action distribution corresponding to the same policy. Assumption 4.5 (Regularity Condition on σi and ςi). We assume that there exists an absolute constant κ > 0 such that {
Eςi [(
dσi dςi (s, a)
)2]}1/2 ≤ κ, ∀i ∈ [T ]. (4.2)
Here dσi/dςi is the Radon-Nikodym derivative of σi with respect to ςi.
We highlight that if the MDP is initialized at the stationary distribution ςi, the state-action visitation measure σi is the same as ςi. 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 L∞-norm of dσi/dςi is upper bounded, whereas we only assume that its L2-norm is upper bounded.
Meanwhile, we impose the following regularity condition on the smoothness of the expected total reward J(πθ) with respect to θ. Assumption 4.6 (Lipschitz Continuous Policy Gradient). We assume that ∇θJ(πθ) is L-Lipschitz continuous with respect to θ, where L > 0 is an absolute constant.
Such an assumption holds when the transition probability P(· | s, a) and the reward function r are both Lipschitz continuous with respect to their inputs (Pirotta et al., 2015). Also, Karimi et al. (2019); Zhang et al. (2019); Xu et al. (2019b); Agarwal et al. (2019) verify the Lipschitz continuity of the policy gradient under certain regularity conditions.
Note that we restrict θ to the parameter space B. Here we call θ̂ ∈ B a stationary point of J(πθ) if it holds for all θ ∈ B that ∇θJ(πθ̂)
>(θ − θ̂) ≤ 0. We now show that the sequence {θi}i∈[T+1] generated by neural policy gradient converges to a stationary point at a sublinear rate. Theorem 4.7 (Convergence to Stationary Point). We set τi = 1, η = 1/ √ T , ηTD = min{(1 −
γ)/8, 1/ √ TTD}, TTD = Ω(m), and B = {α : ‖α−Winit‖2 ≤ R} by Algorithm 1, where the actor update is given in (3.6) with G(θ) = Imd. For all i ∈ [T ], we define
ρi = η −1 · [ ΠB ( θi + η · ∇θJ(πθi) ) − θi ] ∈ Rmd, (4.3)
where ΠB : Rmd → B is the projection operator onto B ⊆ Rmd. Under the assumptions of Proposition 4.3 and Assumptions 4.4-4.6, for T ≥ 4L2 we have
min i∈[T ]
E [ ‖ρi‖22 ] ≤ 8/ √ T · E [ J(πθT+1)− J(πθ1) ] + 8σ2ξ/B + εQ(T ),
where κ is defined in (4.2) of Assumption 4.2 and εQ(T ) = κ · O(R5/2 ·m−1/4 · T 1/2 + R9/4 · m−1/8 · T 1/2). Here the expectations are taken over all the randomness.
Proof. See §D.1 for a detailed proof.
By Theorem 4.7 with m = Ω(T 8 · R18) and B = Ω( √ T ), we obtain mini∈[T ] E[‖ρi‖22] = O(1/ √ T ). Therefore, when the two-layer neural networks are sufficiently wide and the batch size B is sufficiently large, neural policy gradient achieves a 1/ √ T -rate of convergence. Moreover, ρi defined in (4.3) is known as the gradient mapping at θi (Nesterov, 2018). It is known that θ̂ ∈ B is a stationary point if and only if the gradient mapping at θ̂ is a zero vector. Therefore, (a subsequence of) {θi}i∈[T+1] converges to a stationary point θ̂ ∈ B as mini∈[T ] E[‖ρi‖22] converges to zero. In other words, neural policy gradient converges to a stationary point at a 1/ √ T -rate. Also, we remark
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 a stationary point at a similar sublinear rate. See §G for details.
We now characterize the global optimality of the obtained stationary point θ̂. To this end, we compare the expected total reward of πθ̂ with that of the global optimum π ∗ of J(π).
Theorem 4.8 (Global Optimality of Stationary Point). Let θ̂ ∈ B be a stationary point of J(πθ). It holds that
(1− γ) · ( J(π∗)− J(πθ̂) ) ≤ 2Qmax · inf
θ∈B ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ ,
where Qmax is the upper bound of |r| and uθ̂ : S ×A → R is defined as
uθ̂(s, a) = dσπ∗
dσπ θ̂
(s, a)− dνπ ∗
dνπ θ̂
(s) + φθ̂(s, a) >θ̂, ∀(s, a) ∈ S ×A. (4.4)
Here dσπ∗/dσπ θ̂ and dνπ∗/dνπ θ̂ are the Radon-Nikodym derivatives, and ‖ · ‖σπ θ̂ is the L2(σπ θ̂ )- norm.
Proof. See §D.2 for a detailed proof.
To understand Theorem 4.8, we highlight that for θ, θ̂ ∈ B, the function φθ̂(·, ·) >θ is well approximated by the overparameterized two-layer neural network f((·, ·); θ). See Corollary E.4 for details. Therefore, the global optimality of πθ̂ depends on the error of approximating uθ̂ with an overparameterized two-layer neural network. Specifically, if uθ̂ is well approximated by an overparameterized two-layer neural network, then πθ̂ is nearly as optimal as π
∗. In the following corollary, we formally establish a sufficient condition for any stationary point θ̂ to be globally optimal.
Theorem 4.9 (Global Optimality of Stationary Point). Let θ̂ ∈ B be a stationary point of J(πθ). We assume that uθ̂ ∈ FR,∞ in Theorem 4.8. Under Assumption 4.2, it holds that
(1− γ) · Einit [ J(π∗)− J(πθ̂) ] = O(R3/2 ·m−1/4).
More generally, without assuming uθ̂ ∈ FR,∞ in Theorem 4.8, under Assumption 4.2, it holds that (1− γ) · Einit [ J(π∗)− J(πθ̂) ] = O(R3/2 ·m−1/4) + Einit [ ‖ΠFR,∞uθ̂ − uθ̂‖σπθ̂ ] .
Here the expectations are taken over the random initialization, and ΠFR,∞ is the projection operator onto FR,∞ with respect to the L2(σπ
θ̂ )-norm.
Proof. See §H.2 for a detailed proof.
By Theorem 4.9, a stationary point θ̂ is globally optimal if uθ̂ ∈ FR,∞ and m → ∞. Moreover, following from the definition of ρi in (4.3) of Theorem 4.7, we obtain that
∇θJ(πθi)>(θ − θi) ≤ (2R+ 2η ·Qmax) · ‖ρi‖2, ∀θ ∈ B. (4.5)
See §H.3 for a detailed proof of (4.5). Since ‖ρi‖2 = 0 implies that θi is a stationary point, the right-hand side of (4.5) quantifies the deviation of θi from a stationary point θ̂. Following similar analysis to §D.2 and §H.2, if uθi ∈ FR,∞ for all i ∈ [T ], we obtain that
(1− γ) · min i∈[T ]
E [ J(π∗)− J(πθi) ] = O(R3/2 ·m−1/4) + (2R+ 2η ·Qmax) · min i∈[T ] E [ ‖ρi‖2 ] .
Thus, by invoking Theorem 4.7, it holds for sufficiently largem andB that the expected total reward J(πθi) converges to the global optimum J(π ∗) at a 1/T 1/4-rate.

heading: A NEURAL NATURAL POLICY GRADIENT
text: 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 θi and τi in (3.2) are both updated. To analyze the critic update, we impose Assumptions 4.1 and 4.2, which guarantee that Proposition 4.3 holds. Meanwhile, to analyze the actor update, we impose the following regularity conditions.
In parallel to Assumption 4.4, we lay out the following regularity condition on the variance of the estimators of the policy gradient and the Fisher information matrix. Assumption A.1 (Variance Upper Bound). Let B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}, where Winit is the initial parameter. We define
δi = (τi+1 · θi+1 − τi · θi)/η = argmin α∈B ‖F̂ (θi) · α− τi · ∇̂θJ(πθi)‖2, ∀i ∈ [T ],
where ∇̂θJ(πθi) and F̂ (θi) are defined in (3.7) and (3.9), respectively. With slight abuse of notation, for all i ∈ [T ], we define the function ξi : Rmd → Rmd as
ξi(α) = F̂ (θi) · α− τi · ∇̂θJ(πθi)− E [ F̂ (θi) · α− τi · ∇̂θJ(πθi) ] .
We assume that there exists an absolute constant σξ > 0 such that E [ ‖ξi(δi)‖22 ] ≤ τ4i · σ2ξ/B, E [ ‖ξi(ωi)‖22 ] ≤ τ4i · σ2ξ/B, ∀i ∈ [T ].
Here the expectations are taken over σi given θi and ωi.
Next, we lay out a regularity condition on the visitation measures σi, νi and the stationary distributions ςi, %i, respectively. Assumption A.2 (Upper Bounded Concentrability Coefficient). We denote by ν∗ and σ∗ the state and state-action visitation measures corresponding to the global optimum π∗. For all i ∈ [T ], we define the concentrability coefficients ϕi, ψi, ϕ′i, and ψ ′ i as
ϕi = { Eσi [ (dσ∗/dσi) 2 ]}1/2 , ψi = { Eνi [ (dν∗/dνi) 2 ]}1/2 ,
ϕ′i = { Eςi [ (dσ∗/dςi) 2 ]}1/2 , ψ′i = { E%i [ (dν∗/d%i) 2 ]}1/2 , (A.1)
where dσ∗/dσi, dν∗/dνi, dσ∗/dςi, and dν∗/d%i are the Radon-Nikodym derivatives. We assume that the concentrability coefficients defined in (A.1) are uniformly upper bounded by an absolute constant c0 > 0.
The regularity condition on upper bounded concentrability coefficients is commonly imposed in the reinforcement learning literature and is standard for theoretical analysis (Szepesvári and Munos, 2005; Munos and Szepesvári, 2008; Antos et al., 2008; Lazaric et 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 on the initial parameter Winit in Algorithm 1. Assumption A.3 (Upper Bounded Moment at Random Initialization). Let φ0(s, a) ∈ Rmd be the feature mapping defined in (3.3) with θ = Winit. We assume that there exists an absolute constant M > 0 such that
Einit [
sup (s,a)∈S×A ∣∣f((s, a);Winit)∣∣2] = Einit[ sup (s,a)∈S×A |φ0(s, a)>Winit|2 ] ≤M2.
Here the expectations are taken over the random initialization.
Note that as m → ∞, the two-layer neural network φ0(s, a)>Winit converges to a Gaussian process indexed by (s, a) (Lee et al., 2018), which lies in a compact subset of Rd. It is known that under certain regularity conditions, the maximum of a Gaussian process over a compact index set is a sub-Gaussian random variable (van Handel, 2014). Therefore, the regularity condition that max(s,a) |φ0(s, a)>Winit| has a finite second moment is mild. We now establish the global optimality and rate of convergence of neural natural policy gradient.
Theorem A.4 (Global Optimality and Convergence). We set η = 1/ √ T , ηTD = min{(1 −
γ)/8, 1/ √ TTD}, TTD = Ω(m), τi = (i − 1) · η, and B = {α : ‖α − Winit‖2 ≤ R} in Algorithm 1, where the actor update is given in (3.10). Under the assumptions of Proposition 4.3 and Assumptions A.1-A.3, we have
min i∈[T ]
E [ J(π∗)− J(πθi) ] ≤ log |A|+ 9R 2 +M
(1− γ) · √ T
+ 1 (1− γ) · T · T∑ i=1 ̄i(T ). (A.2)
Here M is defined in Assumption A.3 and ̄i(T ) satisfies
̄i(T ) = √
8c0 ·R1/2 · (σ2ξ/B)1/4︸ ︷︷ ︸ (a)
(A.3)
+O ( (τi+1 · T 1/2 + 1) ·R3/2 ·m−1/4 +R5/4 ·m−1/8 )︸ ︷︷ ︸ (b) + εQ,i︸︷︷︸ (c) ,
where c0 is defined in Assumption A.2 and εQ,i = c0 · O(R3/2 ·m−1/4 +R5/4 ·m−1/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 mini∈[T ] E[J(π∗)−J(πθi)] is upper bounded by two terms. Intuitively, the first O(1/ √ T ) 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 ∇̂θJ(πθ) due to the finite batch size B, which vanishes as B →∞. Also, (b) corresponds to the incompatibility between the parameterizations of the actor and critic. As introduced in §3.1, we use shared architecture and random initialization to ensure approximately compatible function approximations. In particular, (b) vanishes as m → ∞. Meanwhile, (c) corresponds to the policy evaluation error, i.e., the error of approximating Qπθi using Qωi . 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) {πθi}i∈[T+1] obtained from the neural natural policy gradient converges to the global optimum J(π∗) at a 1/ √ T -rate. 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 = Ω(R10 · T 6) and B = Ω(R2 · T 2 · σ2ξ ) that
min i∈[T ]
E [ J(π∗)− J(πθi) ] = O
( log |A|
(1− γ) · √ T
) .
Here the expectation is taken over all the randomness.
Proof. See §H.4 for a 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 overparameterized two-layer neural networks, both neural policy gradient and neural natural policy gradient converge at 1/ √ T -rates. In comparison, when m and B are sufficiently large, neural policy gradient is only shown to converge to a stationary point under the additional regularity condition that ∇θJ(πθ) is Lipschitz continuous (Assumption 4.6). Moreover, by Theorem 4.8, the global optimality of such a 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 Assumption 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 et al., 2018; Tu and Recht, 2018), where natural policy gradient enjoys an improved rate of convergence.
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 et al., 2015; 2017). Although Liu et al. (2019) establish a similar 1/ √ T -rate of convergence to the global optimum, neural PPO is different from neural natural policy gradient, as it requires solving a subproblem of policy improvement in the functional space by fitting an overparameterized two-layer neural network using multiple stochastic gradient steps in the parameter space. In contrast, neural natural policy gradient only requires a single stochastic natural gradient step in the parameter space, which makes the analysis even more challenging.

heading: B SHARED INITIALIZATION AND COMPATIBLE FUNCTION APPROXIMATION.
text: Sutton et al. (2000) introduce the notion of compatible function approximations. Specifically, the action-value function Qω is compatible with πθ if we have ∇ωAω(s, a) = ∇θ log πθ(a | s) for all (s, a) ∈ S × A, where Aω(s, a) = Qω(s, a) − 〈Qω(s, ·), πθ(· | s)〉 is the advantage function corresponding to Qω . 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).
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 πθ, and initialize Qω and πθ with the same parameter Winit, where [Winit]r ∼ N(0, Id/d) for all r ∈ [m]. We show that in the overparameterized regime where m is large, the shared architecture and random initialization ensure Qω to be approximately compatible with πθ in the following sense. We define φ0 = ([φ0] > 1 , . . . , [φ0] > m) > : Rd → Rmd as the centered feature mapping corresponding to the initialization, which takes the form of
[φ0]r(s, a) = br√ m · 1 { (s, a)>[Winit]r > 0 } · (s, a) (B.1)
− Eπθ [ br√ m · 1 { (s, a′)>[Winit]r > 0 } · (s, a′) ] , ∀(s, a) ∈ S ×A,
where Winit is the initialization shared by both the actor and critic, and we omit the dependency on θ for notational simplicity. Similarly, we define for all (s, a) ∈ S×A the following centered feature mappings,
φθ(s, a) = φθ(s, a)− Eπθ [ φθ(s, a ′) ] , φω(s, a) = φω(s, a)− Eπθ [ φω(s, a ′) ] . (B.2)
Here φθ(s, a) and φω(s, a) are the feature mappings defined in (3.3), which correspond to θ and ω, respectively. By (3.1), we have
Aω(s, a) = Qω(s, a)− Eπθ [ Qω(s, a ′) ] = φω(s, a) >ω, ∇θ log πθ(a | s) = φθ(s, a), (B.3)
which holds almost everywhere for θ ∈ Rmd. As shown in Corollary E.3 in §E, when the width m is sufficiently large, in policy gradient methods, both φθ and φω are well approximated by φ0 defined in (B.1). Therefore, by (B.3), we conclude that in the overparameterized regime with shared architecture and random initialization, Qω is approximately compatible with πθ.

heading: C SAMPLING FROM VISITATION MEASURE.
text: Recall that the policy gradient ∇θJ(πθ) in (3.4) involves an expectation taken over the state-action visitation measure σπθ . Thus, to obtain an unbiased estimator of the policy gradient, we need to sample from the visitation measure σπθ . To achieve such a goal, we introduce an artificial MDP (S,A, P̃, ζ, r, γ). Such an MDP only differs from the original MDP in the Markov transition kernel P̃ , which is defined as
P̃(s′ | s, a) = γ · P(s′ | s, a) + (1− γ) · ζ(s′), ∀(s, a, s′) ∈ S ×A× S. Here P is the Markov transition kernel of the original MDP. That is, at each state transition of the artificial MDP, the next state is sampled from the initial state distribution ζ with probability 1 − γ.
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 νπθ . Therefore, when we sample a trajectory {(St, At)}t≥0, where S0 ∼ ζ(·), At ∼ π(· |St), and St+1 ∼ P̃(· |St, At) for all t ≥ 0, the marginal distribution of (St, At) converges to the state-action visitation measure σπθ .

heading: D PROOF OF MAIN RESULTS
text: 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 J(π) at the global optimum π∗. Such a lemma is adapted from Kakade and Langford (2002). Lemma D.1 (Performance Difference (Kakade and Langford, 2002)). It holds for all π that
J(π∗)− J(π) = (1− γ)−1 · Eν∗ [ 〈Qπ(s, ·), π∗(· | s)− π(· | s)〉 ] ,
where ν∗ is the state visitation measure corresponding to π∗.
Proof. Following from Lemma J.1, which is Lemma 6.1 in Kakade and Langford (2002), it holds for all π that
J(π∗)− J(π) = (1− γ)−1 · Eσ∗ [ Aπ(s, a) ] , (D.1)
where σ∗ is the state-action visitation measure corresponding to π∗, andAπ is the advantage function associated with π. By definition, we have σ∗(·, ·) = π∗(· | ·)·ν∗(·). Meanwhile, it holds for all s ∈ S that
Eπ∗ [ Aπ(s, a) ] = Eπ∗ [ Qπ(s, a) ] − V π(s) = 〈Qπ(s, ·), π∗(· | s)〉 − 〈Qπ(s, ·), π(· | s)〉
= 〈Qπ(s, ·), π∗(· | s)− π(· | s)〉. (D.2)
Combining (D.1) and (D.2), we conclude that J(π∗)− J(π) = (1− γ)−1 · Eν∗ [ 〈Qπ(s, ·), π∗(· | s)− π(· | s)〉 ] ,
which concludes the proof of Lemma D.1.

heading: D.1 PROOF OF THEOREM 4.7
text: Proof. We first lower bound the difference between the expected total rewards of πθi+1 and πθi . By Assumption 4.6,∇θJ(πθ) is L-Lipschitz continuous. Thus, it holds that
J(πθi+1)− J(πθi) ≥ η · ∇θJ(πθi)>δi − L/2 · ‖θi+1 − θi‖22, (D.3)
where δi = (θi+1 − θi)/η. Recall that ξi = ∇̂θJ(πθi) − E[∇̂θJ(πθi)], where the expectation is taken over σi given θi and ωi. It holds that
∇θJ(πθi)>δi = ( ∇θJ(πθi)− E [ ∇̂θJ(πθi) ])> δi − ξ>i δi + ∇̂θJ(πθi)>δi. (D.4)
On the right-hand side of (D.4), the first term represents the error of estimating ∇θJ(πθi) using E[∇̂θJ(πθi)] = Eσi [∇θ log πθi(a | s) · Qωi(s, a)], the second term is related to the variance of the estimator ∇̂θJ(πθi) of the policy gradient ∇θJ(πθi), and the last term relates the increment δi of the actor update to ∇̂θJ(πθi). In the following lemma, we establish a lower bound of the first term. Lemma D.2. It holds that∣∣∣(∇θJ(πθi)− E[∇̂θJ(πθi)])>δi∣∣∣ ≤ 4κ ·R/η · ‖Qπθi −Qωi‖ςi , where ∇̂J(πθi) is defined in (3.7), ςi is the stationary state-action distribution, and κ is the absolute constant defined in Assumption 4.5. Here the expectation is taken over σi given θi and ωi.
Proof. See §H.5 for a detailed proof.
For the second term on the right-hand side of (D.4), we have
−ξ>i δi ≥ −‖ξi‖22/2− ‖δi‖22/2. (D.5)
Now it remains to lower bound the third term on the right-hand side of (D.4). For notational simplicity, we define
ei = θi+1 − ( θi + η · ∇̂J(πθi) ) = ΠB ( θi + η · ∇̂J(πθi) ) − ( θi + η · ∇̂J(πθi) ) ,
where ΠB is the projection operator onto B. It then holds that
e>i [ ΠB ( θi + η · ∇̂J(πθi) ) − x ] = e>i (θi+1 − x) ≤ 0, ∀x ∈ B. (D.6)
Specifically, setting x = θi in (D.6), we obtain that e>i δi ≤ 0, which implies
∇̂Jθ(πθi)>δi = (δi − ei/η)>δi ≥ ‖δi‖22. (D.7)
By plugging Lemma D.2, (D.5), and (D.7) into (D.4), we obtain that
∇θJ(πθi)>δi ≥ −4κ ·R/η · ‖Qπθi −Qωi‖ςi + ‖δi‖22/2− ‖ξi‖22/2. (D.8)
Thus, by plugging (D.8) and the definition that δi = (θi+1 − θi)/η into (D.3), we obtain for all i ∈ [T ] that
(1− L · η) · E [ ‖δi‖22/2 ] ≤ η−1 · E [ J(πθi+1)− J(πθi) ] + 4κ ·R/η · E [ ‖Qπθi −Qωi‖ςi ] + E [ ‖ξi‖22/2 ] , (D.9)
where the expectations are taking over all the randomness.
Now we turn to characterize ‖ρi − δi‖2. By the definition of ρi in (4.3), we have ‖ρi − δi‖2 = η−1 · ∥∥∥ΠB(θi + η · ∇θJ(πθi))− θi − (ΠB(θi + η · ∇̂θJ(πθi))− θi)∥∥∥
2 = η−1 · ∥∥ΠB(θi + η · ∇θJ(πθi))−ΠB(θi + η · ∇̂θJ(πθi))∥∥2
≤ ‖∇θJ(πθi)− ∇̂θJ(πθi)‖2. (D.10)
The following lemma further upper bounds the right-hand side of (D.10).
Lemma D.3. It holds for all i ∈ [T ] that E [ ‖∇θJ(πθi)− ∇̂θJ(πθi)‖22 ] ≤ 2E [ ‖ξi‖22 ] + 8κ2 · E [ ‖Qπθi −Qωi‖2ςi ] .
Here the expectations are taken over all the randomness.
Proof. See §H.6 for a detailed proof.
Recall that we set η = 1/ √ T . Upon telescoping (D.9), it holds for T ≥ 4L2 that
min i∈[T ]
E [ ‖ρi‖22 ] ≤ 1/T · T∑ i=1 E [ ‖ρi‖22 ] ≤ 1/T ·
T∑ i=1 ( 2E [ ‖δi‖22 ] + 2E [ ‖ρi − δi‖22 ]) ≤ 1/T ·
T∑ i=1 4(1− L · η) · E [ ‖δi‖22 ] + 2E [ ‖ρi − δi‖22 ] ≤ 8/ √ T · E [ J(πθT+1)− J(πθ1) ] + 8/T ·
T∑ i=1 E [ ‖ξi‖22 ] + εQ(T ), (D.11)
where the third inequality follows from the fact that 1−L · η ≥ 1/2, while the fourth inequality follows from (D.9), (D.10), and Lemma D.3. Here the expectations are taken over all the randomness, and εQ(T ) is defined as
εQ(T ) = 32κ ·R/ √ T · T∑ i=1 E [ ‖Qπθi −Qωi‖ςi ] + 16κ2/T · T∑ i=1 E [ ‖Qπθi −Qωi‖2ςi ] .
By Proposition 4.3 and Assumption 4.4, it holds for all i ∈ [T ] that E [ ‖Qπθi −Qωi‖2ςi ] = O(R3 ·m−1/2 +R5/2 ·m−1/4), E[‖ξi‖22] ≤ σ2ξ/B. (D.12)
By plugging (D.12) into (D.11), we conclude that
min i∈[T ]
E [ ‖ρi‖22 ] ≤ 8/ √ T · E [ J(πθT+1)− J(πθ1) ] + 8σ2ξ/B + εQ(T ),
where
εQ(T ) = κ · O(R5/2 ·m−1/4 · T 1/2 +R9/4 ·m−1/8 · T 1/2). Thus, we complete the proof of Theorem 4.7.

heading: D.2 PROOF OF THEOREM 4.8
text: Proof. Since θ̂ is a stationary point of J(πθ), it holds that
∇θJ(πθ̂) >(θ − θ̂) ≤ 0, ∀θ ∈ B. (D.13)
Therefore, by Proposition 3.1, we obtain from (D.13) that
∇θJ(πθ̂) >(θ − θ̂) = Eσπ
θ̂
[ φθ̂(s, a) >(θ − θ̂) ·Qπθ̂ (s, a) ] ≤ 0, ∀θ ∈ B. (D.14)
Here φθ̂ and φ̄θ̂ are defined in (3.3) and (B.2) with θ = θ̂, respectively. Note that
Eσπ θ̂ [ φθ̂(s, a) >(θ − θ̂) · V πθ̂ (s) ] = Eνπ θ̂ [ Eπ θ̂ [ φθ̂(s, a) ]> (θ − θ̂) · V πθ̂ (s) ] = 0,
Eσπ θ̂
[ Eπ
θ̂
[ φθ̂(s, a ′)>(θ − θ̂) ] ·Aπθ̂ (s, a) ] = Eνπ
θ̂
[ Eπ
θ̂
[ φθ̂(s, a ′)>(θ − θ̂) ] · Eπ
θ̂
[ Aπθ̂ (s, a) ]] = 0,
which holds since Eπ θ̂ [φθ̂(s, a)] = Eπθ̂ [A π θ̂ (s, a)] = 0 for all s ∈ S. Thus, by (D.14), we have
Eσπ θ̂ [ φθ̂(s, a) >(θ − θ̂) ·Qπθ̂ (s, a) ]
= Eσπ θ̂ [ φθ̂(s, a) >(θ − θ̂) ·Aπθ̂ (s, a) ] − Eσπ θ̂ [ Eπ θ̂ [ φθ̂(s, a ′)>(θ − θ̂) ] ·Aπθ̂ (s, a) ] + Eσπ
θ̂
[ φθ̂(s, a) >(θ − θ̂) · V πθ̂ (s) ]
= Eσπ θ̂ [ φθ̂(s, a) >(θ − θ̂) ·Aπθ̂ (s, a) ] ≤ 0, ∀θ ∈ B. (D.15)
Meanwhile, by Lemma D.1 we have (1− γ) · ( J(π∗)− J(πθ̂) ) = Eν∗ [ 〈Aπθ̂ (s, ·), π∗(· | s)− πθ̂(· | s)〉 ] . (D.16)
In what follows, we write ∆θ = θ − θ̂. Combining (D.15) and (D.16), we obtain that (1− γ) · ( J(π∗)− J(πθ̂) ) ≤ Eν∗ [ 〈Aπθ̂ (s, ·), π∗(· | s)− πθ̂(· | s)〉 ] − Eσπ
θ̂
[ φθ̂(s, a) >∆θ ·Aπθ̂ (s, a) ]
= Eν∗ [ 〈Aπθ̂ (s, ·), π∗(· | s)− πθ̂(· | s)〉 ] − Eνπ
θ̂
[ 〈Aπθ̂ (s, ·), φθ̂(s, ·) >∆θ · πθ̂(· | s)〉 ] , (D.17)
where we use the fact that σπ θ̂ (·, ·) = πθ̂(· | ·) · νπθ̂ (·). It remains to upper bound the right-hand side of (D.17). By calculation, it holds for all (s, a) ∈ S ×A that( π∗(a | s)− πθ̂(a | s) ) dν∗(s)− φθ̂(s, a) >∆θ · πθ̂(a | s)dνθ̂(s)
=
( π∗(a | s)− πθ̂(a | s)
πθ̂(a | s) · dν∗ dνθ̂ (s)− φθ̂(s, a) >∆θ
) · πθ̂(a | s)dνπθ̂ (s)
= ( uθ̂(s, a)− φθ̂(s, a) >θ ) dσπ θ̂ (s, a), (D.18)
where uθ̂ is defined as
uθ̂(s, a) = dσπ∗
dσπ θ̂
(s, a)− dνπ ∗
dνπ θ̂
(s) + φθ̂(s, a) >θ̂, ∀(s, a) ∈ S ×A.
Here dσπ∗/dσπ θ̂ and dνπ∗/dνπ θ̂ are the Radon-Nikodym derivatives. By plugging (D.18) into (D.17), we obtain that
(1− γ) · ( J(π∗)− J(πθ̂) ) ≤ Eν∗ [ 〈Aπθ̂ (s, ·), π∗(· | s)− πθ̂(· | s)〉 ] − Eνπ
θ̂
[ 〈Aπθ̂ (s, ·), φθ̂(s, ·) >∆θ · πθ̂(· | s)〉 ]
= ∫ S ∑ a∈A Aπθ̂ (s, a) · (( π∗(a | s)− πθ̂(a | s) ) dν∗(s)− φθ̂(s, a) >∆θ · πθ̂(a | s)dνθ̂(s) )
= ∫ S×A Aπθ̂ (s, a) · ( uθ̂(s, a)− φθ̂(s, a) >∆θ ) dσπ θ̂ (s, a)
≤ ‖Aπθ̂ (·, ·)‖σπ θ̂ · ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ , (D.19)
where the second equality follows from (D.18) and the last inequality is from the Cauchy-Schwartz inequality. Note that |Aπθ̂ (s, a)| ≤ 2Qmax for all (s, a) ∈ S ×A. Therefore, it follows from (D.19) that
(1− γ) · ( J(π∗)− J(πθ̂) ) ≤ 2Qmax · ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ , ∀θ ∈ B. (D.20)
Finally, by taking the infimum of the right-hand side of (D.20) with respect to θ ∈ B, we obtain that (1− γ) · ( J(π∗)− J(πθ̂) ) ≤ 2Qmax · inf
θ∈B ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ ,
which concludes the proof of Theorem 4.8.

heading: D.3 PROOF OF THEOREM A.4
text: Proof. For notational simplicity, we write πi = πθi hereafter. In the following lemma, we characterize the performance difference J(π∗)− J(πi) based on Lemma D.1. Lemma D.4. It holds that
(1− γ) · η · ( J(π∗)− J(πi) ) = Eν∗ [ DKL ( π∗(· | s) ∥∥πi(· | s))−DKL(π∗(· | s)∥∥πi+1(· | s)) −DKL ( πi+1(· | s)
∥∥πi(· | s))]−Hi, where Hi is defined as
Hi = Eν∗ [〈 log ( πi+1(· | s)/πi(· | s) ) − η ·Qωi(s, ·), π∗(· | s)− πi(· | s) 〉] ︸ ︷︷ ︸
(i)
(D.21)
+ η · Eν∗ [ 〈Qωi(s, ·)−Qπi(s, ·), π∗(· | s)− πi(· | s)〉 ]︸ ︷︷ ︸ (ii)
+ Eν∗ [〈 log ( πi(· | s)/πi+1(· | s) ) , πi+1(· | s)− πi(· | s) 〉] ︸ ︷︷ ︸
(iii)
.
Proof. See §H.7 for a detailed proof.
Here Hi defined in (D.21) of Lemma D.4 consists of three terms. Specifically, (i) is related to the error of estimating the natural policy gradient using (3.8). Also, (ii) is related to the error of estimating Qπi using Qωi . Meanwhile, (iii) is the remainder term. We upper bound these three terms in §H.8. Combining these upper bounds, we obtain the following lemma.
Lemma D.5. Under Assumptions 4.2 and A.3, we have E [ |Hi| − Eν∗ [ DKL ( πi+1(· | s) ∥∥πi(· | s))]] ≤ η2 · (9R2 +M2) + η · (ϕ′i + ψ′i) · εQ,i + εi. Here the expectation is taken over all the randomness. Meanwhile, ϕ′i and ψ ′ i are the concentrability coefficients defined in (A.1) of Assumption A.2, εQ,i is defined as εQ,i = E[‖Qπi −Qωi‖ςi ], M is the absolute constant defined in Assumption A.3, and εi is defined as
εi = √ 2 ·R1/2 · η · (ϕi + ψi) · τ−1i · { E [ ‖ξi(δi)‖2 ] + E [ ‖ξi(ωi)‖2 ]}1/2 (D.22)
+O ( (τi+1 + η) ·R3/2 ·m−1/4 + η ·R5/4 ·m−1/8 ) .
Here ξi(δi) and ξi(ωi) are defined in Assumption A.1, where δi = η−1 · (τi+1 · θi+1− τi · θi), while ϕi and ψi are the concentrability coefficients defined in (A.1) of Assumption A.2.
Proof. See §H.8 for a detailed proof.
By Lemmas D.4 and D.5, we obtain that
(1− γ) · E [ J(π∗)− J(πi) ] ≤ η−1 · E [ Eν∗ [ DKL ( π∗(· | s)‖πi(· | s) ) (D.23)
−DKL ( π∗(· | s)‖πi+1(· | s) )]] + η · (9R2 +M2) + η−1 · εi + (ϕ′i + ψ′i) · εQ,i,
where εQ,i is defined as εQ,i = E[‖Qπi−Qωi‖ςi ],M is the absolute constant defined in Assumption A.3, εi is defined in (D.22) of Lemma D.5, and the expectations are taken over all the randomness. Recall that we set η = 1/ √ T . Upon telescoping (D.23), we obtain that
(1− γ) · min i∈[T ]
E [ J(π∗)− J(πi) ] ≤ 1− γ T · T∑ i=1 E [ J(π∗)− J(πi) ] (D.24)
≤ 1√ T · ( E [ Eν∗ [ DKL ( π∗(· | s) ∥∥π1(· | s))]]+ 9R2 +M2) + 1
T · T∑ i=1 (√ T · εi + (ϕ′i + ψ′i) · εQ,i ) ,
where the expectations are taken over all the randomness and the last inequality follows from the fact that
DKL ( π∗(· | s) ∥∥πT+1(· | s)) ≥ 0, ∀s ∈ S, ∀θT+1 ∈ Rmd. In what follows, we upper bound the right-hand side of (D.24). Note that we set τ1 = 0. By the parameterization of policy in (3.2), it then holds that π1(· | s) is uniform over A for all s ∈ S and θ1 ∈ Rmd. Therefore, we obtain that
DKL ( π∗(· | s)‖π1(· | s) ) ≤ log |A|, ∀s ∈ S, ∀θ1 ∈ Rmd. (D.25)
Meanwhile, by Assumption A.1, we have
E [ ‖ξi(δi)‖2 ] ≤ { E [ Eσi [ ‖ξi(δi)‖22 ]]}1/2 ≤ τ2i · σξ ·B−1/2,
where the expectation Eσi [‖ξi(δi)‖22] is taken over σi given θi and ωi, while the other expectations are taken over all the randomness. A similar upper bound holds for E[‖ξi(ωi)‖2]. Therefore, by plugging the upper bounds of E[‖ξi(σi)‖2] and E[‖ξi(ωi)‖2] into εi defined in (D.22) of Lemma D.5, we obtain from Assumption A.2 that
√ T · εi ≤ 2 √ 2c0 ·R1/2 · σ1/2ξ ·B −1/4 (D.26)
+O ( (τi+1 · T 1/2 + 1) ·R3/2 ·m−1/4 +R5/4 ·m−1/8 ) .
Also, combining Assumption A.2 and Proposition 4.3, it holds that
(ϕ′i + ψ ′ i) · εQ,i ≤ 2c0 · E [ ‖Qπi −Qωi‖ςi ] = c0 · O(R3/2 ·m−1/4 +R5/4 ·m−1/8). (D.27)
Finally, by plugging (D.25), (D.26), and (D.27) into (D.24) and setting
̄i(T ) = √ T · εi + (ϕ′i + ψ′i) · εQ,i,
we complete the proof of Theorem A.4.

heading: E LINEARIZATION ERROR
text: In this section, we lay out a fundamental lemma that characterizes the distance between a two-layer neural network φ>θ θ and its linearization φ > 0 θ, where φθ is the feature mapping of the two-layer neural network defined in (3.3) and φ0 is the feature mapping corresponding to 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 > 0 be an absolute constant. For all m ∈ N, we define
F̃R,m = { f̂ ( (s, a);W ) = 1√ m · m∑ r=1 br · 1 { [Winit] > r (s, a) > 0 } · [W ]>r (s, a) (E.1)
: ‖W −Winit‖2 ≤ R } ,
where [Winit]r ∼ N(0, Id/d) and br ∼ Unif({−1, 1}) are the initial parameters of the two-layer neural network defined in (3.1).
Note that F̃R,m in (E.1) is a class of functions that are linear in W but nonlinear in (s, a). Meanwhile, it holds that ∇W f̂((s, a);W ) = ∇W f((s, a);W )|W=Winit for all (s, a) ∈ S × A, where f((·, ·);W ) is the two-layer neural network defined in (3.1). Thus, f̂((·, ·);W ) can be viewed as the linearization of f((·, ·);W ) at the initial parameter Winit. Moreover, for a fixed R, the linearization error of f̂((·, ·);W ) decays to zero as the width m → ∞. Intuitively, since ‖W −Winit‖2 is upper bounded by R, the differences between blocks ‖[W ]r − [Winit]r‖2 are sufficiently small for a sufficiently large m and all r ∈ [m]. As a result, for a sufficiently large m, we have 1{[Winit]>r (s, a) > 0} = 1{[W ]>r (s, a) > 0} with high probability for all r ∈ [m] and (s, a) ∈ S ×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 Winit be the initial parameter of the twolayer neural network defined in (3.1). Let B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}. Under Assumption 4.2, it holds for all θ, θ′ ∈ B that
Einit [ ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ ] = O(R3 ·m−1/2),
where the expectation is taken over the random initialization. Here φθ and φ0 are the feature mappings defined in (3.3), which correspond to θ and Winit, respectively, and σ(·, ·) = π(· | ·) · ν(·) is the distribution over S ×A such that Assumption 4.2 holds.
Proof. By the definition of feature mapping in (3.3), we obtain that
φθ(s, a) >θ′ − φ0(s, a)>θ′
= 1√ m · m∑ r=1 ( 1 { (s, a)>[θ]r > 0 } − 1 { (s, a)>[Winit]r > 0 }) · (s, a)>[θ′]r. (E.2)
Meanwhile, for 1{(s, a)>[θ]r > 0} 6= 1{(s, a)>[Winit]r > 0}, we have
|(s, a)>[Winit]r| ≤ |(s, a)>[θ]r − (s, a)>[Winit]r| ≤ ‖(s, a)‖2 · ‖[θ]r − [Winit]r‖2, (E.3)
where the last inequality follows from the Cauchy-Schwartz inequality. Recall that ‖(s, a)‖2 ≤ 1 for all (s, a) ∈ S ×A. Thus, it follows from (E.3) that∣∣1{(s, a)>[θ]r > 0}− 1{(s, a)>[Winit]r > 0}∣∣
≤ 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } . (E.4)
By plugging (E.4) into (E.2), we obtain that
|φθ(s, a)>θ′ − φ0(s, a)>θ′|
≤ 1√ m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } · |(s, a)>[θ′]r|
≤ 1√ m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } · ( |(s, a)>[Winit]r|+
∣∣(s, a)>([θ′]r − [Winit]r)∣∣) ≤ 1√
m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } (E.5)
· ( |(s, a)>[Winit]r|+ ‖[θ′]r − [Winit]r‖2 ) ,
where the last inequality follows from the Cauchy-Schwartz inequality and the fact that ‖(s, a)‖2 ≤ 1. Following from the fact that 1{|x| ≤ y} · |x| ≤ 1{|x| ≤ y} · y, we obtain from (E.5) that
|φθ(s, a)>θ′ − φ0(s, a)>θ′|
≤ 1√ m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } (E.6)
· ( ‖[θ]r − [Winit]r‖2 + ‖[θ′]r − [Winit]r‖2 ) .
Therefore, following from the Cauchy-Schwartz inequality, we obtain from (E.6) that
|φθ(s, a)>θ′ − φ0(s, a)>θ′|2 (E.7)
≤ 1 m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } · m∑ r=1 ( 2‖[θ]r − [Winit]r‖22 + 2‖[θ′]r − [Winit]r‖22
) ≤ 1 m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } · 2 ( ‖θ −Winit‖22 + ‖θ′ −Winit‖22 ) ,
where the first inequality follows from the fact that (x + y)2 ≤ 2x2 + 2y2. Recall that θ, θ′ ∈ B, where B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}. Thus, following from (E.7), we have
|φθ(s, a)>θ′ − φ0(s, a)>θ′|2 ≤ 4R2 m · m∑ r=1 1 { |(s, a)>[Winit]r| ≤ ‖[θ]r − [Winit]r‖2 } . (E.8)
By Assumption 4.2, we obtain from (E.8) that ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ = Eσ [ |φθ(s, a)>θ′ − φ0(s, a)>θ′|2 ] ≤ 4c ·R 2
m · m∑ r=1 ‖[θ]r − [Winit]r‖2 ‖[Winit]r‖2 , (E.9)
where c is the absolute constant defined by Assumption 4.2. It now suffices to take the expectation of the right-hand side of (E.9) over the random initialization. Following from the Cauchy-Schwartz
inequality, we obtain that( m∑ r=1 ‖[θ]r − [Winit]r‖2 ‖[Winit]r‖2 )2 ≤ ( m∑ r=1 ‖[θ]r − [Winit]r‖22 ) · ( m∑ r=1 1/‖[Winit]r‖22 )
= ‖θ −Winit‖22 · m∑ r=1 1/‖[Winit]r‖22
≤ R2 · m∑ r=1 1/‖[Winit]r‖22, (E.10)
where the last inequality follows from the fact that θ ∈ B. Therefore, combining (E.9) and (E.10), we conclude that
Einit [ ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ ] ≤ 4c ·R 3
m · Einit [( m∑ r=1 1/‖[Winit]r‖22 )1/2]
≤ 4c ·R 3 m · ( m∑ r=1 Einit [ 1/‖[Winit]r‖22 ])1/2 = 4c1 ·R3 ·m−1/2,
where the second inequality follows from the Jensen’s inequality and c1 = c·Ex∼N(0,Id/d)[1/‖x‖22]. Thus, we complete the proof of Lemma E.2.
By Lemma E.2, the linearization φ>0 θ converges to the two-layer neural network φ > θ θ as the width m → ∞. Based on Lemma E.2, the following corollary characterizes a similar convergence where the feature mappings φθ and φ0 are replaced by the centered feature mappings φ0 and φθ defined in (B.1) and (B.2), respectively. Corollary E.3. Let Winit be the initial parameter and B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R} be the parameter space. Under Assumption 4.2, it holds for all θ, θ′ ∈ B that
Einit [ ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ ] = O(R3 ·m−1/2),
where the expectation is taken over the random initialization. Here φ0 and φθ are the centered feature mappings defined in (B.1) and (B.2), respectively, and σ(·, ·) = π(· | ·) · ν(·) is the distribution over S ×A such that Assumption 4.2 holds.
Proof. By the definitions of φ0 and φθ in (B.1) and (B.2), respectively, we obtain that ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ = ∥∥φθ(·, ·)>θ′ − φ0(·, ·)>θ′ − Eπθ[φθ(·, a′)>θ′ − φ0(·, a′)>θ′]∥∥2σ
≤ 2‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ + 2‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2πθ·ν ,
where the second inequality follows from the Jensen’s inequality and the fact that ‖x + y‖22 ≤ 2‖x‖22 + 2‖y‖22. Therefore, by Assumption 4.2 and Lemma E.2, we obtain that
Einit [ ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ ] ≤ 2Einit [ ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2σ ] + 2Einit [ ‖φθ(·, ·)>θ′ − φ0(·, ·)>θ′‖2πθ·ν ] = O(R3 ·m−1/2),
which concludes the proof of Corollary E.3.
In what follows, we present a corollary that quantifies the difference between the function φθ̂(·, ·) >θ and the two-layer neural network f((·, ·); θ) = φθ(·, ·)>θ by the L2(σ)-norm, where σ(·, ·) = π(· | ·) · ν(·) is the distribution over S ×A such that Assumption 4.2 holds. Corollary E.4. Let B = {α ∈ Rmd : ‖α −Winit‖2 ≤ R}. Under Assumption 4.2, it holds for all θ, θ̂ ∈ B that
Einit [ ‖φθ̂(·, ·) >θ − φθ(·, ·)>θ‖σ ]
= O(R3/2 ·m−1/4), where the expectation is taken over the random initialization. Here φθ is the feature mapping defined in (3.3), and σ(·, ·) = π(· | ·) · ν(·) is the distribution over S ×A such that Assumption 4.2 holds.
Proof. By the triangle inequality, we have Einit [ ‖φθ̂(·, ·) >θ − φθ(·, ·)>θ‖σ ]
≤ Einit [ ‖φθ̂(·, ·) >θ − φ0(·, ·)>θ‖σ ] + Einit [ ‖φθ(·, ·)>θ − φ0(·, ·)>θ‖σ ] , (E.11)
where φ0 is the feature mapping defined in (3.3) with θ = Winit. Meanwhile, for all θ, θ̂ ∈ B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}, it follows from Assumption 4.2 and Lemma E.2 that
Einit [ ‖φθ̂(·, ·) >θ − φ0(·, ·)>θ‖σ ]
= O(R3/2 ·m−1/4), Einit [ ‖φθ(·, ·)>θ − φ0(·, ·)>θ‖σ ] = O(R3/2 ·m−1/4), (E.12)
where the expectations are taken over the random initialization. Combining (E.11) and (E.12), we obtain that
Einit [ ‖φθ̂(·, ·) >θ − φθ(·, ·)>θ‖σ ] = O(R3/2 ·m−1/4),
which concludes the proof of Corollary E.4.
Corollary E.4 implies that when the width m is sufficiently large, φθ̂(·, ·) >θ is well approximated by the two-layer neural network f((·, ·); θ) in L2(σ)-norm, where σ(·, ·) = π(· | ·) · ν(·) is the distribution over S ×A such that Assumption 4.2 holds.

heading: F NEURAL TD
text: In this section, we introduce the details of neural TD (Cai et al., 2019) for critic update in Algorithm 1. Neural TD solves the optimization problem in (3.11) using the TD iterations defined in (3.12) and (3.13), which is summarized in Algorithm 2.
Algorithm 2 Neural TD (Cai et al., 2019) Require: The policy π, number of TD iterations TTD, and learning rate ηTD of neural TD.
1: Initialization: Initialize br ∼ Unif({−1, 1}) and [Winit]r ∼ N(0, Id/d). Set B ← {α ∈ Rmd : ‖α−Winit‖2 ≤ R} and ω(0)←Winit. 2: for t = 0, . . . , TTD − 1 do 3: Sample a tuple (s, a, r, s′, a′), where (s, a) ∼ ςi, s′ ∼ P(· | s, a), r ← r(s, a), and a′ ∼ π(· | s′). 4: Compute the Bellman residue δ ← Qω(t)(s, a)− (1− γ) · r − γ ·Qω(t)(s′, a′). 5: Perform a TD update step: ω(t+ 1/2)← ω(t)− η · δ · ∇ωQω(t)(s, a). 6: Perform a projection step: ω(t+ 1)← ΠB(ω(t+ 1/2)). 7: Perform an averaging step: ω ← t+1t+2 · ω + 1 t+2 · ω(t+ 1). 8: end for 9: Output: Qout(·)← Qω(·).
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 set ηTD = min{(1 − γ)/8, 1/ √ TTD} in Algorithm 2. Under Assumption 4.2, it holds that
Einit [ ‖Qout −Qπ‖2ςπ ] ≤ 2Einit [ ‖ΠF̃R,mQ π −Qπ‖2ςπ ]
(F.1)
+O(R2 · T−1/2TD +R 3 ·m−1/2 +R5/2 ·m−1/4),
where ΠF̃R,m is the projection operator onto F̃R,m, and ςπ is the stationary state-action distribution corresponding to π.
Proof. See Proposition 4.7 in Cai et al. (2019) for a detailed proof.

heading: F.1 PROOF OF PROPOSITION 4.3
text: Proof. By Theorem F.1, to establish the rate of convergence of neural TD, it suffices to characterize the approximation error Einit[‖ΠF̃R,mQ
π − Qπ‖2ςπ ] in (F.1). To this end, we first define a new function class
FR,m = { f̂ ( (s, a);W ) = 1√ m · m∑ r=1 br · 1 { [Winit] > r (s, a) > 0 } ·W>r (s, a)
: ‖[W ]r − [Winit]r‖∞ ≤ R/ √ md } ,
where [Winit]r ∼ N(0, Id/d) and br ∼ Unif({−1, 1}) are the initial parameters. By definition, FR,m is a subset of F̃R,m defined in Definition E.1. The following lemma obtained from Rahimi and Recht (2009) characterizes the deviation of FR,m from FR,∞ given in Assumption 4.1. Lemma F.2 (Projection Error of FR,m (Rahimi and Recht, 2009)). Let f ∈ FR,∞, where FR,∞ is defined in Assumption 4.1. For any δ > 0, it holds with probability at least 1− δ that
‖ΠFR,mf − f‖ς ≤ R ·m −1/2 ·
[ 1 + √ 2 log(1/δ) ] , (F.2)
where ς is a distribution over S ×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 P ( ‖ΠFR,mf − f‖ς ≥ t ) ≤ exp ( −1/2 · (t · √ m/R− 1)2 ) . (F.3)
Meanwhile, by Assumption 4.1, we have Qπ ∈ FR,∞. Therefore, by setting f = Qπ and ς = ςπ in (F.3), we obtain that
Einit [ ‖ΠFR,mQ π −Qπ‖2ςπ ] = ∫ ∞ 0 P ( ‖ΠFR,mQ π −Qπ‖2ςπ ≥ t ) dt
≤ ∫ ∞
0
exp ( −1/2 · (t · √ m/R− 1)2 ) dt = O(R ·m−1/2), (F.4)
where the expectation is taken over the random initialization. Also, note that FR,m ⊆ F̃R,m, where F̃R,m is defined in Definition E.1. Therefore, it follows from (F.4) that
Einit [ ‖ΠF̃R,mQ π −Qπ‖2ςπ ] ≤ Einit [ ‖ΠFR,mQ π −Qπ‖2ςπ ] = O(R ·m−1/2). (F.5)
Combining (F.5) and Theorem F.1, we obtain for ηTD = min{(1− γ)/8, 1/ √ TTD} that
Einit [ ‖Qout −Qπ‖2σπ ] = O(R ·m−1/2 +R2 · T−1/2TD +R 3 ·m−1/2 +R5/2 ·m−1/4). (F.6)
Specifically,Qωi is the output of Algorithm 2 with πθi as the input. Finally, by setting TTD = Ω(m) in (F.6), we obtain
Einit [ ‖Qωi −Qπθi‖2ςi ] = O(R3 ·m−1/2 +R5/2 ·m−1/4),
which concludes the proof of Proposition 4.3.

heading: G PROJECTION-FREE NEURAL POLICY GRADIENT
text: 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-free actor update takes the form of
θi+1 ← θi + η · ∇̃θJ(πθi).
Here ∇̃θJ(πθi) is an estimator of the policy gradient∇θJ(πθi), which takes the form of
∇̃θJ(πθi) = τi B · B∑ `=1 Q̃ωi(s`, a`) · ∇θ log πθi(a` | s`). (G.1)
Here τi is the temperature parameter of πθi , {(s`, a`)}`∈[B] is sampled from the state-action visitation measure σi corresponding to the current policy πθi , and B > 0 is the batch size. Also, Q̃ωi is the modified critic. Specifically, for all (s, a) ∈ S ×A, we define
Q̃ωi(s, a) = Qmax · 1 { Qωi(s, a) ≥ Qmax } −Qmax · 1 { Qωi(s, a) ≤ −Qmax } (G.2)
+Qωi(s, a) · 1 { −Qmax < Qωi(s, a) < Qmax } ,
whereQωi is obtained from Algorithm 2 with πθi as the input. We summarize projection-free neural policy gradient in Algorithm 3.
Algorithm 3 Projection-Free Neural Policy Gradient Require: Number of iterations T , number of TD iterations TTD, learning rate η, learning rate ηTD
of neural TD, temperature parameters {τi}i∈[T+1], and batch size B. 1: Initialization: Initialize br ∼ Unif({−1, 1}) and [Winit]r ∼ N(0, Id/d) for all r ∈ [m]. Set B ← {α ∈ Rmd : ‖α−Winit‖2 ≤ R} and θ1 ←Winit. 2: for i ∈ [T ] do 3: Update ωi using Algorithm 2 with πθi as the input, ω(0) ← Winit and {br}r∈[m] as the initialization, TTD as the number of iterations, and ηTD as the learning rate. 4: Sample {(s`, a`)}`∈[B] from the visitation measure σi, and estimate ∇̃θJ(πθ) using (G.1) and (G.2). 5: Update θi+1 by θi+1 ← θi + η · ∇̃θJ(πθi). 6: end for 7: Output: {πθi}i∈[T+1].

heading: G.1 CONVERGENCE OF PROJECTION-FREE NEURAL POLICY GRADIENT
text: In this section, we show that the sequence {θi}i∈[T+1] generated by projection-free neural policy gradient converges to a stationary point at a sublinear rate. In parallel to Assumption 4.4, we lay out the following regularity condition on the moments of the estimator ∇̃θJ(πθi). Assumption G.1 (Moment Upper Bound). Recall that σi is the state-action visitation measure corresponding to πθi for all i ∈ [T ]. Let ξ̃i = ∇̃θJ(πθi) − E[∇̃θJ(πθi)], where ∇̃θJ(πθi) is defined in (G.1). We assume that there exists absolute constants σξ̃, ςξ̃ > 0 such that E[‖ξ̃i‖ 2 2] ≤ τ2i · σ2ξ̃/B and E[‖ξ̃i‖32] ≤ τ3i · ς3ξ̃ /B 3/2 for all i ∈ [T ]. Here the expectations are taken over σi given θi and ωi.
Similar to Theorem 4.7, in the following theorem, we show that the sequence {θi}i∈[T+1] generated by Algorithm 3 converges to a stationary point θ̂ with∇θJ(πθ̂) = 0 at a sublinear rate. Theorem G.2 (Convergence to Stationary Point). Let η = 1/ √ T , τi = 1, ηTD = min{(1 −
γ)/8, 1/ √ TTD}, and TTD = Ω(m) in Algorithm 3. Under the assumptions of Proposition 4.3 and Assumptions 4.5, 4.6, and G.1, it holds for T ≥ 4L2 and B = Ω(σ2 ξ̃ · T 1/2) that
min i∈[T ]
E [ ‖∇θJ(πθi)‖22 ] ≤ 8/ √ T · E [ J(πθT+1)− J(πθ1) ] + PG,
where
PG = O(T−1/2 +R3/2 ·m−1/4 · T +R5/4 ·m−1/8 · T ).
Here the expectations are taken over all the randomness.
Proof. Our proof aligns closely to that of Theorem 4.7 in §D.1. We first lower bound the difference J(πθi+1)− J(πθi). By Assumption 4.6, we have
J(πθi+1)− J(πθi) ≥ η · ∇θJ(πθi)>δi − L/2 · ‖θi+1 − θi‖22, (G.3) where
δi = (θi+1 − θi)/η = ∇̃θJ(πθi), ∀i ∈ [T ]. Following the proof of Lemma D.2 in §H.5, we obtain that∣∣∣(∇θJ(πθi)− E[∇̃θJ(πθi)])>δi∣∣∣ ≤ κ/η · 2‖θi+1 − θi‖2 · ‖Qπθi − Q̃ωi‖ςi , (G.4) where the expectation is taken over σi given θi and ωi. Recall that ξ̃i = ∇̃θJ(πθi)− E[∇̃θJ(πθi)], where the expectation is taken over σi given θi and ωi. Following from (G.4), we obtain that
∇θJ(πθi)>δi = ( ∇θJ(πθi)− E [ ∇̃θJ(πθi) ])> δi − (ξ̃i)>δi + ∇̃θJ(πθi)>δi
≥ −2κ · ‖θi+1 − θi‖2/η · ‖Qπθi − Q̃ωi‖ςi − ‖ξ̃i‖22/2 + ‖δi‖22/2, (G.5) where the second inequality follows similar analysis to §D.1. Hence, by plugging (G.5) into (G.3), we have
J(πθi+1)− J(πθi)
≥ (η − L · η2)/2 · ‖δi‖22 − η · ‖ξ̃i‖22/2− 2κ · ‖θi+1 − θi‖2 · ‖Qπθi − Q̃ωi‖ςi . (G.6) It remains to upper bound ‖θi+1 − θi‖2. To this end, we use the fact that
‖θi+1 − θi‖2 ≤ ‖θi −Winit‖2 + ‖θi+1 −Winit‖2, and upper bound ‖θi−Winit‖2 and ‖θi+1−Winit‖2. By the actor update in Algorithm 3, we obtain for all i > 1 that
‖θi −Winit‖2 ≤ i−1∑ j=1 η · ‖∇̃θJ(πθj )‖2 ≤ i−1∑ j=1 η · (∥∥E[∇̃θJ(πθj )]∥∥2 + ‖ξ̃j‖2), (G.7)
where the expectation is taken over σi given θi and ωi. Meanwhile, it holds that∥∥E[∇̃θJ(πθj )]∥∥2 = ∥∥Eσj [φθj (s, a) · Q̃ωj (s, a)]∥∥2 ≤ Eσj [‖φθj (s, a)‖2 · |Q̃ωj (s, a)|], (G.8) where φθj 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 ‖φθj (s, a)‖2 ≤ 2 for all (s, a) ∈ S ×A. Meanwhile, by (G.2), we obtain that
|Q̃ωj (s, a)| ≤ Qmax, ∀(s, a) ∈ S ×A. (G.9) By plugging (G.9) into (G.8), we obtain for all j ∈ [T ] that∥∥E[∇̃θJ(πθj )]∥∥2 ≤ 2Qmax. (G.10) By further plugging (G.10) into (G.7), we obtain for all i > 1 that
‖θi −Winit‖2 ≤ 2Qmax · η · T + i−1∑ j=1 η · ‖ξ̃j‖2. (G.11)
We now lower bound the right-hand side of (G.6) based on (G.11). Following from the CauchySchwartz inequality and Assumption G.1, we obtain that
E [ ‖θi −Winit‖2 · ‖Qπθi − Q̃ωi‖ςi ] ≤ 2Qmax · η · T · { E [ ‖Qπθi − Q̃ωi‖2ςi
]}1/2 +
i−1∑ j=1 η · { E [ ‖ξ̃i‖22 ]}1/2 · { E [ ‖Qπθi − Q̃ωi‖2ςi ]}1/2 ≤ (2Qmax · η · T + σξ̃ · η · T ·B −1/2) · { E [ ‖Qπθi − Q̃ωi‖2ςi ]}1/2 , (G.12)
where the expectations are taken over all the randomness, and σξ̃ is the absolute constant defined in Assumptions G.1. By plugging (G.12) into (G.6), we obtain that
(η − L · η2)/2 · E [ ‖δi‖22 ] ≤ E [ J(πθi+1)− J(πθi) ] + η · σ2 ξ̃ /(2B) +R0(T ) · { E [ ‖Qπθi −Qωi‖2ςi ]}1/2 , (G.13)
where we use the fact that ‖θi+1 − θi‖2 ≤ ‖θi+1 −Winit‖2 + ‖θi −Winit‖2. Here the expectations are taken over all the randomness, and R0(T ) is defined by
R0(T ) = 4Qmax · η · T + 2σξ̃ · η · T ·B −1/2.
By Proposition 4.3 and Assumption 4.2, we obtain for η = 1/ √ T , B = Ω(σ2
ξ̃ · T 1/2), and TTD =
Ω(m) that
R0(T ) = O( √ T ), E [ ‖Qπθi − Q̃ωi‖2ςi ] ≤ E [ ‖Qπθi −Qωi‖2ςi ] = O(R3 ·m−1/2 +R5/2 ·m−1/4), (G.14)
where the inequality holds since |Qπθi (s, a)| ≤ Qmax for all (s, a) ∈ S × A. By plugging (G.14) into (G.13) with η = 1/ √ T and B = Ω(σ2
ξ̃ · T 1/2), we obtain that
(1− L/ √ T )/2 · E [ ‖δi‖22 ] ≤ √ T · E [ J(πθi+1)− J(πθi) ] + PG, (G.15)
where
PG = O(T−1/2 +R3/2 ·m−1/4 · T +R5/4 ·m−1/8 · T ). (G.16)
It remains to upper bound ‖δi−∇θJ(πθi)‖2, where δi = ∇̃J(πθi). Following from similar analysis to §H.6, we obtain that
E [ ‖∇θJ(πθi)− ∇̃θJ(πθi)‖22 ] ≤ 2E [ ‖ξ̃i‖22 ] + 8κ2 · E [ ‖Qπθi − Q̃ωi‖2ςi ] ,
where the expectations are taken over all the randomness. Therefore, following from Proposition 4.3 and Assumption G.1, it holds for η = 1/ √ T , B = Ω(σ2
ξ̃ · T 1/2), and TTD = Ω(m) that E [ ‖∇θJ(πθi)− ∇̃θJ(πθi)‖22 ] = O(T−1/2 +R3 ·m−1/2 +R5/2 ·m−1/4). (G.17)
Thus, combining (G.15) and (G.17), we obtain for all i ∈ [T ] that E [ ‖∇θJ(πθi)‖22 ] ≤ 2E [ ‖δi‖22 ] + 2E [ ‖∇θJ(πθi)− ∇̃θJ(πθi)‖22 ] ≤ 4(1− L/ √ T ) · E [ ‖δi‖22 ] + 2E [ ‖∇θJ(πθi)− ∇̃θJ(πθi)‖22
] ≤ 8 √ T · E [ J(πθi+1)− J(πθi) ] + PG, (G.18)
where we use the fact that T ≥ 4L2 and we define PG in (G.16). Finally, by telescoping (G.18), we obtain that
min i∈[T ]
E [ ‖∇θJ(πθi)‖22 ] ≤ 1 T · T∑ i=1 E [ ‖∇θJ(πθi)‖22 ] ≤ 8E [ J(πθT+1)− J(πθ1) ]/√ T + PG,
where PG = O(T−1/2 +R3/2 ·m−1/4 · T +R5/4 ·m−1/8 · T ).
Here the expectations are taken over all the randomness. Thus, we complete the proof of Theorem G.2.
Following from Theorem G.2, it holds for m = Ω(R10 · T 12) that
min i∈[T ]
E [ ‖∇θJ(πθi)‖22 ] = O(1/ √ T ).
Therefore, θi converges to a stationary point at a 1/ √ T -rate if the width m 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 3 needs a larger width m to achieve the 1/ √ T -rate of convergence. Such a stronger requirement on m is the extra price to pay for using the projection-free actor update.

heading: G.2 GLOBAL OPTIMALITY OF PROJECTION-FREE NEURAL POLICY GRADIENT
text: In this section, we characterize the global optimality of projection-free neural policy gradient. We define a sequence of parameter spaces {Bi}i∈[T ] as follows,
Bi = { α ∈ Rmd : ‖α− θi‖2 ≤ R0 } , ∀i ∈ [T ], (G.19)
where R0 ≥ 1 is an absolute constant. The sequence {Bi}i∈[T ] characterizes the global optimality of the parameter sequence {θi}i∈[T ]. Specifically, similar to (4.5), we have
∇θJ(πθi)>(θ − θi) ≤ ‖θ − θi‖2 · ‖∇θJ(πθi)‖2 ≤ R0 · ‖∇θJ(πθi)‖2, ∀θ ∈ Bi, ∀i ∈ [T ], where the first inequality follows from the Cauchy-Schwartz inequality. Following similar analysis to §D.2, we obtain for all i ∈ [T ] that
(1− γ) · ( J(π∗)− J(πθi) ) ≤ 2Qmax · inf
θ∈Bi ‖uθi(·, ·)− φθi(·, ·)>θ‖σi +R0 · ‖∇θJ(πθi)‖2. (G.20)
We now introduce the parameter space BT that includes the sequence {θi}i∈[T ] and the parameter space Bi as its subspace for all i ∈ [T ] as follows,
BT = { α ∈ Rmd : ‖α−Winit‖2 ≤ R(T ) +R0 } , (G.21)
where
R(T ) = 2Qmax · η · T + η · T∑ i=1 ‖ξ̃i‖2. (G.22)
Here ξ̃i is defined in Assumption G.1. Following from (G.7) and (G.10) in the proof of Theorem G.2 in §G.1, we have θi ∈ BT for all i ∈ [T ]. By Corollary E.4, φθi(·, ·)>θ is well approximated by f((·, ·); θ) for θ, θi ∈ BT when the width m is sufficiently large. Thus, following from (G.20), for a sufficiently large m, the suboptimality of θi is characterized by ‖∇θJ(πθi)‖2, which is further quantified by Theorem G.2, and the approximation error infθ∈Bi ‖uθi(·, ·) − f((·, ·); θ)‖σi , 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-free neural policy gradient to be globally optimal. Theorem G.3 (Global Optimality of Projection-Free Neural Policy Gradient). Let η = 1/ √ T , τi = 1, ηTD = min{(1− γ)/8, 1/ √ TTD}, and TTD = Ω(m) in Algorithm 3. We define
ũθi(s, a) = uθi(s, a) + φθi(s, a) >(Winit − θi), ∀(s, a) ∈ S ×A.
Here uθi is defined in (4.4) of Theorem 4.8 with θ̂ = θi, and φθi is the feature mapping defined in (3.3) with θ = θi. Under the assumptions of Theorem G.2, if it holds that
ũθi ∈ FR0,∞, ∀i ∈ [T ],
then for T ≥ 4L2, B = Ω(T 1/2), and m = Ω(R10 · T 12), we have
(1− γ) · min i∈[T ]
E [ J(π∗)− J(πθi) ] = O(R0 · T−1/4).
Here the expectation is taken over all the randomness.
Proof. To prove Theorem G.3, it suffices to upper bound the expectation of the right-hand side of (G.20) over all the randomness. We first upper bound the following term,
E [
inf θ∈Bi ‖uθi(·, ·)− φθi(·, ·)>θ‖σi
] ,
where the expectation is taken over all the randomness. Note that
uθi(s, a)− φθi(s, a)>θ = ũθi(s, a) + φθi(s, a)>θi − φθi(s, a)>Winit − φθi(s, a)>θ = ũθi(s, a)− φ0(s, a)>(θ − θi +Winit) (G.23)
− ( φθi(s, a)− φ0(s, a) )> (θ − θi +Winit),
which holds for all (s, a) ∈ S ×A and θ ∈ Bi with Bi defined in (G.19). Therefore, by the triangle inequality, we obtain from (G.23) that
inf θ∈Bi ‖uθi(·, ·)− φθi(·, ·)>θ‖σi ≤ inf θ∈Bi
{ ‖ũθi(·, ·)− φ0(·, ·)>(θ − θi +Winit)‖σi (G.24)
+ ∥∥(φθi(·, ·)− φ0(·, ·))>(θ − θi +Winit)∥∥σi}.
We now upper bound the right-hand side of (G.24). In what follows, we define θ̃i by
φ0(·, ·)>θ̃i = ΠF̃R0,m ũθi(·, ·),
where ΠF̃R0,m is the projection operator onto F̃R0,m. It then follows from the definition of F̃R0,m in Definition E.1 that θ̃i ∈ B1 = {α ∈ Rmd : ‖α −Winit‖2 ≤ R0} for all i ∈ [T ]. Meanwhile, by the definition of Bi in (G.19), we have
θ̃i + θi −Winit ∈ Bi, ∀i ∈ [T ]. (G.25) Combining (G.24) and (G.25), we have
inf θ∈Bi ‖uθi(·, ·)− φθi(·, ·)>θ‖σi ≤ ‖ũθi(·, ·)− φ0(·, ·)>θ̃i‖σi + ∥∥(φθi(·, ·)− φ0(·, ·))>θ̃i∥∥σi . (G.26)
Now, it suffices to upper bound the right-hand side of (G.26). Following from the proof of Proposition 4.3 in §F.1, we obtain for ũθi ∈ FR0,∞ that
E [ ‖ũθi(·, ·)− φ0(·, ·)>θ̃i‖σi ] = E [∥∥ũθi(·, ·)−ΠF̃R0,m ũθi(·, ·)∥∥σi] = O(R0 ·m−1/2), (G.27) where the expectations are taken over all the randomness. Meanwhile, note that
‖θ̃i −Winit‖2 ≤ R0 ≤ R0 +R(T ),
where R(T ) is defined in (G.22). Therefore, we obain that θi, θ̃i ∈ BT . By Assumption G.1, we obtain for η = 1/ √ T and B = Ω(T 1/2) that
E [ R(T )2 ] = O(T ), E [ R(T )3 ] = O(T 3/2), (G.28)
where the expectations are taken over all the randomness given Winit. Thus, following from (G.28), Assumption 4.2, and Lemma E.2, we obtain for all θi, θ̃i ∈ BT that
E [ ‖φ0(·, ·)>θ̃i − φθi(·, ·)>θ̃i‖σi ] ≤ { E [ ‖φ0(·, ·)>θ̃i − φθi(·, ·)>θ̃i‖2σi ]}1/2 = O(T 3/4 ·m−1/4). (G.29)
By plugging (G.27) and (G.29) into (G.26), we have E [
inf θ∈Bi ‖uθi(·, ·)− φθi(·, ·)>θ‖σi ] ≤ E [ ‖ũθi(·, ·)− φ0(·, ·)>θ̃i‖σi ] + E [ ‖φ0(·, ·)>θ̃i − φθi(·, ·)>θ̃i‖σi
] = O(R0 ·m−1/2 + T 3/4 ·m−1/4), (G.30)
which holds for all i ∈ [T ].
Meanwhile, by Theorem G.2, we obtain for B = Ω(T 1/2) and m = Ω(R10 · T 12) that
min i∈[T ]
E [ ‖∇θJ(πθi)‖2 ] = O(T−1/4). (G.31)
Thus, by plugging (G.30) and (G.31) with m = Ω(R10 · T 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 J(πθi) converges to the global optimum J(π ∗) at a 1/T 1/4-rate.

heading: H PROOF OF AUXILIARY RESULTS
text: In this section, we lay out the proof of the auxiliary results.

heading: H.1 PROOF OF PROPOSITION 3.1
text: 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 ∇θ log πθ(· | ·). By the definition of πθ(· | ·) in (3.2), it holds for all (s, a) ∈ S ×A that
∇θ log πθ(a | s) = τ · ∇θf ( (s, a); θ ) − τ ·
∑ a′∈A∇θf ( (s, a′); θ ) · exp [ τ · f ( (s, a′); θ )]∑ a′∈A exp [ τ · f ( (s, a′); θ
)] = τ · ∇θf ( (s, a); θ ) − τ · Eπθ [ ∇θf ( (s, a′); θ )] , (H.1)
where we write Eπθ [∇θf((s, a′); θ)] = Ea′∼πθ(· | s)[∇θf((s, a′); θ)] for notational simplicity. Meanwhile, recall that ∇θf((·, ·); θ) = φθ(·, ·), where φθ is the feature mapping defined in (3.3). Thus, (H.1) implies that
∇θ log πθ(a | s) = τ · φθ(s, a)− τ · Eπθ [ φθ(s, a ′) ] . (H.2)
Finally, by plugging (H.2) into (2.5) and (2.7), we have ∇θJ(πθ) = τ · Eσπθ [ Qπθ (s, a) · ( φθ(s, a)− Eπθ [ φθ(s, a ′) ])] ,
F (θ) = τ2 · Eσπθ [( φθ(s, a)− Eπθ [ φθ(s, a ′) ])( φθ(s, a)− Eπθ [ φθ(s, a ′) ])>] ,
which concludes the proof of Proposition 3.1.

heading: H.2 PROOF OF THEOREM 4.9
text: Proof. By Theorem 4.8, we have (1− γ) · ( J(π∗)− J(πθ̂) ) ≤ 2Qmax · inf
θ∈B ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ , (H.3)
where uθ̂ is defined in (4.4). It suffices to upper bound the right-hand side of (H.3) under the expectation over the random initialization. Following from the triangle inequality, we obtain that
inf θ∈B ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂
≤ inf θ∈B {∥∥uθ̂(·, ·)−ΠF̃R,muθ̂(·, ·)∥∥σπ θ̂ + ∥∥ΠF̃R,muθ̂(·, ·)− φθ̂(·, ·)>θ∥∥σπ θ̂ } = ∥∥uθ̂(·, ·)−ΠF̃R,muθ̂(·, ·)∥∥σπ
θ̂
+ inf θ∈B ∥∥ΠF̃R,muθ̂(·, ·)− φθ̂(·, ·)>θ∥∥σπ θ̂ , (H.4)
where F̃R,m is defined in Definition E.1. It remains to upper bound the right-hand side of (H.4). In what follows, we define θ̃ by
φ0(·, ·)>θ̃ = ΠF̃R,muθ̂(·, ·) ∈ F̃R,m,
where φ0 is the feature mapping defined in (3.3) with θ = Winit. By the definition of F̃R,m in Definition E.1, it holds that θ̃ ∈ B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}. Thus, by (H.4) and the fact that θ̃ ∈ B, we have
inf θ∈B ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ ≤ ‖uθ̂(·, ·)− φ0(·, ·) >θ̃‖σπ θ̂ + ‖φ0(·, ·)>θ̃ − φθ̂(·, ·) >θ̃‖σπ θ̂ .
(H.5)
Following from the proof of Proposition 4.3 in §F.1, it holds for uθ̂ ∈ FR,∞ that Einit [ ‖uθ̂(·, ·)− φθ̂(·, ·) >θ̃‖σπ θ̂ ] ≤ { Einit [ ‖uθ̂(·, ·)− φθ̂(·, ·)
>θ̃‖2σπ θ̂
]}1/2 = O(R ·m−1/2), (H.6)
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, we obtain for all θ̂, θ̃ ∈ B that
Einit [ ‖φ0(·, ·)>θ̃ − φθ̂(·, ·) >θ̃‖σπ θ̂ ] ≤ { Einit [ ‖φ0(·, ·)>θ̃ − φθ̂(·, ·)
>θ̃‖2σπ θ̂
]}1/2 = O(R3/2 ·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− γ) · Einit [ J(π∗)− J(πθ̂) ] ≤ 2Qmax · Einit [ inf θ∈B ‖uθ̂(·, ·)− φθ̂(·, ·) >θ‖σπ θ̂ ] = O(R3/2 ·m−1/4),
where the first inequality follows from (H.3). Similarly, if the assumption that uθ̂ ∈ FR,∞ is not imposed, we conclude that
(1− γ) · Einit [ J(π∗)− J(πθ̂) ] ≤ O(R3/2 ·m−1/4) + Einit [ ‖ΠFR,∞uθ̂ − uθ̂‖σπθ̂ ] ,
which completes the proof of Theorem 4.9.

heading: H.3 PROOF OF INEQUALITY (4.5)
text: Proof. Recall that we define ρi by
ρi = η −1 · ( ΠB ( θi + η · ∇θJ(πθi) ) − θi ) , (H.8)
where ΠB is the projection operator onto B. Following from (H.8) and the fact that (ΠBy − y)>(ΠBy − x) ≤ 0 for all x ∈ B, we have(
η · ρi − η · ∇θJ(πθi) )> (η · ρi + θi − θ) ≤ 0, ∀θ ∈ B. (H.9)
Thus, following from (H.9), we obtain that
∇θJ(πθi)>(θ − θi) ≤ ρ>i (θ − θi)− η · ‖ρi‖22 + η · ρ>i ∇θJ(πθi) ≤ ‖ρi‖2 · ( ‖θ − θi‖2 + η · ‖∇θJ(πθi)‖2 ) , ∀θ ∈ B, (H.10)
where the last inequality follows from the Cauchy-Schwartz inequality and the fact that−η ·‖ρi‖22 ≤ 0. It remains to upper bound the right-hand side of (H.10). For all θ, θi ∈ B = {α ∈ Rmd : ‖α −Winit‖2 ≤ R}, we have ‖θ − θi‖2 ≤ 2R. Meanwhile, recall that we set τi = 1. Therefore, following from Proposition 3.1, we obtain that
‖∇θJ(πθi)‖2 ≤ Eσi [ |Qπθi (s, a)| · ‖φθi(s, a)‖2 ] ≤ 2Qmax, (H.11)
where the first inequality follows from the Jensen’s inequality, and the second inequality follows from the facts that |Qπθi (s, a)| ≤ Qmax and ‖φθi(s, a)‖2 ≤ 2 for all (s, a) ∈ S × A. By plugging (H.11) and the upper bound ‖θ − θi‖2 ≤ 2R into (H.10), we conclude that
∇θJ(πθi)>(θ − θi) ≤ (2R+ 2η ·Qmax) · ‖ρi‖2, ∀θ ∈ B,
which concludes the proof of (4.5).

heading: H.4 PROOF OF COROLLARY A.5
text: Proof. It suffices to calculate i(T ) defined in (A.3) in Theorem A.4. Note that we set τi = (i − 1)/ √ T . Therefore, we have τi = O( √ T ) for all i ∈ [T ]. Thus, it holds for m = Ω(R10 · T 6) that
O ( (τi+1 · T 1/2 + 1) ·R3/2 ·m−1/4 ) = O(T−1/2), ∀i ∈ [T ],
O(R5/4 ·m−1/8) = O(T−1/2). (H.12)
Meanwhile, it holds for B = Ω(R2 · T 2 · σ2ξ ) that
R1/2 · (σ2ξ/B)1/4 = O(T−1/2). (H.13)
Therefore, combining (H.12) and (H.13), we obtain that
i(T ) = √ 8c0 ·R1/2 · (σ2ξ/B)1/4 +O ( (1 + τi+1 · T 1/2) ·R3/2 ·m−1/4 +R5/4 ·m−1/8 ) = O(T−1/2).
By Theorem A.4, we have
min i∈[T ]
E [ J(π∗)− J(πθi) ] =
log |A|+ 9R2 +M (1− γ) · √ T
+O ( (1− γ)−1 · T−1/2 ) = O ( log |A|
(1− γ) · √ T
) ,
which concludes the proof of Corollary A.5.

heading: H.5 PROOF OF LEMMA D.2
text: Proof. In the sequel, we write gi = E[∇̂θJ(πθi)] for notational simplicity, where ∇̂θJ(πθi) is defined in (3.7), and the expectation is taken over σi given θi and ωi. Recall that we set τi = 1. By Proposition 3.1, we obtain that
|(∇θJ(πθi)− gi)>δi| = ∣∣∣Eσi[φθi(s, a) · (Qπθi (s, a)−Qωi(s, a))]>δi∣∣∣
≤ ‖δi‖2 · Eσi [ ‖φθi(s, a)‖2 · |Q πθi (s, a)−Qωi(s, a)| ] , (H.14)
where φθi(s, a) is the centered feature mapping defined in (B.2) with θ = θi, and the inequality follows from the Jensen’s inequality. Note that θi, θi+1 ∈ B. It holds that ‖δi‖2 = ‖θi+1 − θi‖2/η ≤ 2R/η. Meanwhile, note that ‖φθi(s, a)‖2 ≤ 2 for all (s, a) ∈ S×A. Therefore, it follows from Assumption 4.5 and (H.14) that
|(∇θJ(πθi)− gi)>δi| ≤ 4R/η · Eσi [ |Qπθi (s, a)−Qωi(s, a)| ] ≤ 4R/η · { Eςi [ (dσi/dςi) 2 ]}1/2
· ‖Qπθi −Qωi‖ςi ≤ 4κ ·R/η · ‖Qπθi −Qωi‖ςi ,
where the second inequality follows from the Cauchy-Schwartz inequality, dσi/dςi is the RadonNikodym derivative, and κ is defined in Assumption 4.5. Thus, we complete the proof of Lemma D.2.

heading: H.6 PROOF OF LEMMA D.3
text: Proof. In what follows, we write gi = E[∇̂J(πθi)] for notational simplicity, where the expectation is taken over σi given θi and ωi. Note that
E [ ‖∇θJ(πθi)− ∇̂θJ(πθi)‖22 ] ≤ 2E [ ‖ξi‖22 ] + 2E [ ‖∇θJ(πθi)− gi‖22 ] , (H.15)
where we use the fact that ‖x + y‖22 ≤ 2‖x‖22 + 2‖y‖22, and the expectations are taken over all the randomness. By Proposition 3.1, we have
‖∇θJ(πθi)− gi‖2 = ∥∥∥Eσi[φθi(s, a) · (Qπθi (s, a)−Qωi(s, a))]∥∥∥
2 ≤ Eσi [ ‖φθi(s, a)‖2 · |Q πθi (s, a)−Qωi(s, a)| ] , (H.16)
where φθi is defined in (B.2) with θ = θi and the second inequality follows from the Jensen’s inequality. Since ‖φθi(s, a)‖2 ≤ 2 for all (s, a) ∈ S ×A, we obtain from (H.16) that
‖∇θJ(πθi)− gi‖22 ≤ { Eσi [ ‖φθi(s, a)‖2 · |Q πθi (s, a)−Qωi(s, a)| ]}2
≤ 4κ2 · ‖Qπθi −Qωi‖2ςi , (H.17) where κ is defined in Assumption 4.5 and the inequality follows from the Cauchy-Schwartz inequality. By plugging (H.17) into (H.15), we obtain that
E [ ‖∇θJ(πθi)− ∇̂θJ(πθi)‖22 ] ≤ 2E [ ‖ξi‖22 ] + 8κ2 · E [ ‖Qπθi −Qωi‖2σi ] ,
which concludes the proof of Lemma D.3.

heading: H.7 PROOF OF LEMMA D.4
text: Proof. By the definition of the KL divergence, it holds for all s ∈ S that DKL ( π∗(· | s) ∥∥πi(· | s))−DKL(π∗(· | s)∥∥πi+1(· | s)) = 〈 log ( πi+1(· | s)/πi(· | s) ) , π∗(· | s) 〉 . (H.18)
Meanwhile, the right-hand side of (H.18) can be expanded as follows,〈 log ( πi+1(· | s)/πi(· | s) ) , π∗(· | s) 〉 = 〈 log ( πi+1(· | s)/πi(· | s) ) , π∗(· | s)− πi+1(· | s) 〉 + 〈 log ( πi+1(· | s)/πi(· | s) ) , πi+1(· | s)
〉 = 〈 log ( πi+1(· | s)/πi(· | s) ) , π∗(· | s)− πi+1(· | s)
〉︸ ︷︷ ︸ Li +DKL ( πi+1(· | s) ∥∥πi(· | s)). (H.19) Combining (H.18) and (H.19), we obtain that
Li = DKL ( π∗(· | s) ∥∥πi(· | s))−DKL(π∗(· | s)∥∥πi+1(· | s))−DKL(πi+1(· | s)∥∥πi(· | s)). (H.20) In what follows, we calculate the difference
Eν∗ [Li]− (1− γ) · η · ( J(π∗)− J(πi) ) .
By Lemma D.1, we have J(π∗)− J(πi) = (1− γ)−1 · Eν∗ [ 〈Qπi(s, ·), π∗(s, ·)− πi(s, ·)〉 ] . (H.21)
Meanwhile, for Li defined in (H.19), we obtain that
Li − η · 〈Qπi(s, ·), π∗(s, ·)− πi(s, ·)〉 = 〈 log ( πi+1(· | s)/πi(· | s) ) , π∗(· | s)− πi+1(· | s) 〉 − η · 〈Qπi(s, ·), π∗(s, ·)− πi(s, ·)〉
= 〈 log ( πi+1(· | s)/πi(· | s) ) − η ·Qωi(s, ·), π∗(· | s)− πi(· | s) 〉 (H.22)
+ η · 〈Qωi(s, ·)−Qπi(s, ·), π∗(· | s)− πi(· | s)〉 + 〈 log ( πi+1(· | s)/πi(· | s) ) , πi(· | s)− πi+1(· | s) 〉 .
Note that upon taking the expectation over s ∼ ν∗(·) in (H.22), the right-hand side of (H.22) is equal to Hi defined in (D.21) of Lemma D.4. Thus, combining (H.21) and (H.22), we obtain that
Eν∗ [Li]− (1− γ) · η · ( J(π∗)− J(πi) ) = Hi, (H.23)
where Hi is defined in (D.21). By plugging (H.20) into (H.23), we conclude that (1− γ) · η · ( J(π∗)− J(πi) ) = Eν∗ [ DKL ( π∗(· | s) ∥∥πi(· | s))−DKL(π∗(· | s)∥∥πi+1(· | s)) −DKL ( πi+1(· | s)
∥∥πi(· | s))]−Hi, which concludes the proof of Lemma D.4.

heading: H.8 PROOF OF LEMMA D.5
text: Proof. By (D.21), we have
E [ |Hi| ] ≤ E [ Eν∗ [〈 log ( πi+1(· | s)/πi(· | s) ) − η ·Qωi(s, ·), π∗(· | s)− πi(· | s) 〉]] (H.24)
+ η · E [ Eν∗ [ |〈Qωi(s, ·)−Qπi(s, ·), π∗(· | s)− πi(· | s)〉| ]] + E [ Eν∗ [∣∣〈log(πi(· | s)/πi+1(· | s)), πi+1(· | s)− πi(· | s)〉∣∣]],
where the inequality 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 on the right-hand side of (H.24) respectively in the following lemmas.
Lemma H.1. It holds that E [ Eν∗ [ |〈Qωi(s, ·)−Qπi(s, ·), π∗(· | s)− πi(· | s)〉| ]] ≤ (φ′i + ψ′i) · E [ ‖Qωi −Qπi‖ςi ] ,
where φ′i, ψ ′ i are the concentrability coefficients defined in (A.1) of Assumption A.2. Here the expectations are taken over all the randomness.
Proof. See §I.1 for a detailed proof.
Lemma H.2. Under Assumptions 4.2 and A.3, it holds that
E [ Eν∗ [∣∣〈log(πi+1(· | s)/πi(· | s)), πi(· | s)− πi+1(· | s)〉∣∣]]
≤ E [ Eν∗ [ DKL ( πi+1(· | s) ∥∥πi(· | s))]]+ η2 · (9R2 +M2) +O(τi+1 ·R3/2 ·m−1/4), where M is the absolute constant defined in Assumption A.3. Here the expectations are taken over all the randomness.
Proof. See §I.2 for a detailed proof.
Lemma H.3. Under Assumption 4.2, it holds that
E [ Eν∗ [∣∣〈log(πi+1(· | s)/πi(· | s))− η ·Qωi(s, ·), π∗(· | s)− πi(· | s)〉∣∣]]
≤ √ 2(ϕi + ψi) · η ·R1/2 · τ−1i · { E [ ‖ξi(δi)‖2 ] + E [ ‖ξi(ωi)‖2 ]}1/2 +O ( (τi+1 + η) ·R3/2 ·m−1/4 + η ·R5/4 ·m−1/8 ) ,
where ϕi and ψi are the concentrability coefficients defined in (A.1) of Assumption A.2 and ξi(δi), ξi(ωi) are defined in Assumption A.1. Here the expectations are taken over all the randomness.
Proof. See §I.3 for a detailed proof.
Finally, applying Lemmas H.1, H.2, and H.3 to (H.24), it holds under Assumptions 4.2 and A.3 that E [ |Hi| − Eν∗ [ DKL ( πi+1(· | s) ∥∥πi(· | s))]] ≤ η2 · (6R2 +M2)+ η · (ϕ′i + ψ′i) · εQ,i + εi, where
εQ,i = E [ ‖Qπi −Qωi‖ςi ] εi = { E [ ‖ξi(δi)‖2 + ‖ξi(ωi)‖2 ]}1/2 +O ( (τi+1 + η) ·R3/2 ·m−1/4 + η ·R5/4 ·m−1/8 ) .
Here the expectations are taken over all the randomness. Therefore, we complete the proof of Lemma D.5.

heading: I PROOF OF SUPPORTING LEMMAS
text: In this section, we provide the proof of the lemmas in §H.

heading: I.1 PROOF OF LEMMA H.1
text: Proof. We define ∆Q,i(s, a) = Qωi(s, a)−Qπi(s, a) for all (s, a) ∈ S ×A. It holds for all i ∈ [T ] that
Eν∗ [ |〈∆Q,i(s, ·), π∗(· | s)− πi(· | s)〉| ] =
∫ S ∣∣∣∣∑ a∈A ∆Q,i(s, a) · ( π∗(a | s)− πi(a | s) )∣∣∣∣dν∗(s). (I.1) Meanwhile, it holds for any s ∈ S that∣∣∣∣∑
a∈A ∆Q,i(s, a) ·
( π∗(a | s)− πi(a | s) )∣∣∣∣ =
∣∣∣∣∫ a∈A ∆Q,i(s, a) · ( π∗(a | s)− πi(a | s) )/ πi(a | s)dπi(a | s) ∣∣∣∣ ≤ ∫ a∈A
∣∣∆Q,i(s, a) · (π∗(a | s)− πi(a | s))/πi(a | s)∣∣dπi(a | s), (I.2) where the inequality follows from the Jensen’s inequality. By plugging (I.2) into (I.1), we have
Eν∗ [ |〈∆Q,i(s, ·), π∗(· | s)− πi(· | s)〉| ] ≤ ∫ S×A
∣∣∆Q,i(s, a) · (π∗(a | s)− πi(a | s))/πi(a | s)∣∣dσ̃(s, a), (I.3) where we define σ̃(·, ·) = πi(· | ·) · ν∗(·). Recall that ςi(·, ·) = πi(· | ·) · %i(·) and σ∗(·, ·) = π∗(· | ·) · ν∗(·). Therefore, following from (I.3), it holds that
Eν∗ [ |〈∆Q,i(s, ·), π∗(· | s)− πi(· | s)〉| ] ≤ ∫ S×A |∆Q,i(s, a)|dσ∗ + ∫ S×A |∆Q,i(s, a)| · dν∗ d%i (s) dςi(s, a). (I.4)
Finally, applying the Cauchy-Schwartz inequality to (I.4) yields that E [ Eν∗ [ |〈∆Q,i(s, ·), π∗(· | s)− πi(· | s)〉| ]] ≤ ({ Eςi [ (dσ∗/dςi) 2 ]}1/2 + { E%i [ (dν∗/d%i) 2 ]}1/2) · E [{ Eςi [ |∆Q,i(s, a)|2
]}1/2] = (ϕ′i + ψ ′ i) · E [{ Eςi [ |∆Q,i(s, a)|2 ]}1/2] = (ϕ′i + ψ ′ i) · E [ ‖∆Q,i‖ςi ] ,
where dσ∗/dςi and dν∗/d%i are the Radon-Nikodym derivatives, ϕ′i and ψ ′ i are the concentrability coefficients defined in (A.1) of Assumption A.2, and the expectations are taken over all the randomness. Thus, we complete the proof of Lemma H.1.

heading: I.2 PROOF OF LEMMA H.2
text: Proof. Following from the definition of πθ in (3.2), we obtain that〈 log ( πi+1(· | s)/πi(· | s) ) , πi(· | s)− πi+1(· | s) 〉 = 〈 τi+1 · f ( (s, ·); θi+1 ) − τi · f ( (s, ·); θi ) , πi(· | s)− πi+1(· | s) 〉 (I.5)
− 〈 Ci(s), πi(· | s)− πi+1(· | s) 〉 ,
where f((·, ·); θ) is the two-layer neural network defined in (3.1) and Ci(s) is defined by
Ci(s) = log (∑ a∈A exp ( τi · f ( (s, a); θi ))) − log (∑ a∈A exp ( τi+1 · f ( (s, a); θi+1 ))) .
Note that both πi(· | s) and πi+1(· | s) are distributions over A, which implies that 〈Ci(s), πi(· | s)− πi+1(· | s)〉 = Ci(s)− Ci(s) = 0, ∀s ∈ S. (I.6)
Meanwhile, recall that we define the feature mapping φθ(s, a) in (3.3). For the two-layer neural network f((·, ·); θ), we have
f ( (s, a); θ ) = φθ(s, a) >θ, ∀(s, a) ∈ S ×A. (I.7)
In what follows, we write φi(s, a) = φθi(s, a) and ∆i(a | s) = πi(a | s)− πi+1(a | s) for notational simplicity. By plugging (I.6) and (I.7) into (I.5), we obtain for all s ∈ S that∣∣〈log(πi+1(· | s)/πi(· | s)),∆i(· | s)〉∣∣ = |〈τi+1 · φi+1(s, ·)>θi+1 − τi · φi(s, ·)>θi,∆i(· | s)〉|
≤ |〈φi(s, ·)>(τi+1 · θi+1 − τi · θi),∆i(· | s)〉| + τi+1 · |〈φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1,∆i(· | s)〉| ≤ ‖φi(s, ·)>(τi+1 · θi+1 − τi · θi)‖∞,A · ‖∆i(· | s)‖1,A︸ ︷︷ ︸ (i)
(I.8)
+ τi+1 · |〈φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1,∆i(· | s)〉|︸ ︷︷ ︸ (ii) ,
where the last inequality follows from the Hölder’s inequality. Here we denote by ‖ · ‖∞,A and ‖ · ‖1,A the `∞- and `1-norms defined on R|A|, respectively. In what follows, we upper bound (i) and (ii) on the right-hand side of (I.8) respectively.
Upper Bounding (i) in (I.8). Recall that we define
δi = η −1 · (τi+1 · θi+1 − τi · θi) = argmin α∈B ‖F̂ (θi) · α− τi · ∇̂J(πθi)‖2.
Thus, it holds that δi ∈ B and ‖δi −Winit‖2 ≤ R, where Winit is the initial parameter. In what follows, we denote by φ0 the feature mapping defined in (3.3) with θ = Winit. Then for all (s, a) ∈ S ×A, we have
|φi(s, a)>(τi+1 · θi+1 − τi · θi)| = η · |φi(s, a)>δi| ≤ η · ( |φ0(s, a)>Winit|+ |φi(s, a)>δi − φi(s, a)>θi|+ |φi(s, a)>θi − φ0(s, a)>Winit| ) ≤ η · ( M0 + ‖φi(s, a)‖2 · ‖δi − θi‖2 + |φi(s, a)>θi − φ0(s, a)>Winit| ) , (I.9)
where the first inequality follows from the triangle inequality, the second inequality follows from the Cauchy-Schwartz inequality, and M0 is defined by
M0 = sup (s,a)∈S×A
|φ0(s, a)>Winit|. (I.10)
In what follows, we upper bound the right-hand side of (I.9). Note that τi−1 + η = τi. Therefore, we obtain that
‖θi −Winit‖2 ≤ τi−1/τi · ‖θi−1 −Winit‖2 + η/τi · ‖δi−1 −Winit‖2, (I.11)
which holds for all i > 1. Recursively, since θ1 = Winit ∈ B and δi ∈ B for all i ∈ [T ], it then follows from (I.11) that θi ∈ B for all i ∈ [T ]. Thus, it holds that ‖δi − θi‖2 ≤ 2R. Meanwhile, following from (3.3), it holds for all θ ∈ Rmd and (s, a) ∈ S × A that ‖φθ(s, a)‖2 ≤ 1. Therefore, we obtain that
‖φi(s, a)‖2 · ‖δi − θi‖2 ≤ 2R, ∀(s, a) ∈ S ×A. (I.12)
It remains to upper bound |φi(s, a)>θi − φ0(s, a)>Winit| for all (s, a) ∈ S × A, which is equal to |f((s, a); θi) − f((s, a);Winit)| by (I.7). Recall that f((·, ·); θ) is differentiable with respect to θ ∈ Rmd almost everywhere, and the gradient∇θf = ([∇θf ]>1 , . . . , [∇θf ]>m)> is given by
[∇θf ]r(s, a) = br√ m · 1 { (s, a)>[θ]r > 0 } · (s, a) = [φθ]r(s, a), ∀(s, a) ∈ S ×A,
where φθ(s, a) is defined in (3.3). Since ‖φθ(s, a)‖2 ≤ 1 for all θ ∈ Rmd and (s, a) ∈ S × A, we obtain for all (s, a) ∈ S ×A that
|φi(s, a)>θi − φ0(s, a)>Winit| = ∣∣f((s, a); θi)− f((s, a);Winit)∣∣
≤ sup θ∈Rmd ∥∥∇θf((s, a); θ)∥∥2 · ‖θi −Winit‖2 = sup θ∈Rmd ‖φθ(s, a)‖2 · ‖θi −Winit‖2 ≤ R, (I.13)
where the last inequality holds since θi ∈ B. By plugging (I.12) and (I.13) into (I.9), we have
|τi+1 · φi(s, a)>θi+1 − τi · φi(s, a)>θi| ≤ η · (M0 + 3R), ∀(s, a) ∈ S ×A, where M0 is defined in (I.10). Therefore, it holds for all s ∈ S that ‖τi+1 · φi(s, ·)>θi+1 − τi · φi(s, ·)>θi‖∞,A = sup
a∈A |τi+1 · φi(s, a)>θi+1 − τi · φi(s, a)>θi|
≤ η · (M0 + 3R). (I.14) Finally, by the Pinsker’s inequality, it follows from (I.14) that
‖φi(s, ·)>(τi+1 · θi+1 − τi · θi)‖∞,A · ‖∆i(· | s)‖1,A −DKL ( πi+1(· | s) ∥∥πi(· | s)) ≤ η · (M0 + 3R) · ‖πi+1(· | s)− πi(· | s)‖1,A − 1/2 · ‖πi+1(· | s)− πi(· | s)‖21,A. (I.15)
By completing the squares, we further upper bound the right-hand side of (I.15) by ‖φi(s, ·)>(τi+1 · θi+1 − τi · θi)‖∞,A · ‖∆i(· | s)‖1,A −DKL ( πi+1(· | s) ∥∥πi(· | s)) = −1/2 · ( ‖πi+1(· | s)− πi(· | s)‖1,A − η · (M0 + 3R) )2 + 1/2 · η2 · (M0 + 3R)2
≤ 1/2 · η2 · (M0 + 3R)2 ≤ η2 · (M20 + 9R2), (I.16)
which holds for all s ∈ S. Here the last inequality follows from the fact that (x+ y)2 ≤ 2x2 + 2y2.
Upper Bounding (ii) in (I.8). It holds for all s ∈ S that
|〈φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1,∆i(· | s)〉| ≤ |〈φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1, πi(· | s)〉|+ |〈φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1, πi+1(· | s)〉| ≤ ‖φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1‖πi,1 + ‖φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1‖πi+1,1. (I.17)
Here for any distribution π ∈ P(A), we denote by ‖ · ‖π,p the Lp(π)-norm, which is defined by ‖v‖π,p = [ ∑ a∈A π(a) · |v(a)|p]1/p. Following from Assumption 4.2 and Lemma E.2, it holds that
E [ Eν∗ [ ‖φi+1(s, ·)>θi+1 − φ0(s, ·)>θi+1‖πi,1 ]] ≤ E [ ‖φi+1(·, ·)>θi+1 − φ0(·, ·)>θi+1‖πi·ν∗ ] = O(R3/2 ·m−1/4),
E [ Eν∗ [ ‖φi(s, ·)>θi+1 − φ0(s, ·)>θi+1‖πi,1 ]] ≤ E [ ‖φi(·, ·)>θi+1 − φ0(·, ·)>θi+1‖πi·ν∗ ] = O(R3/2 ·m−1/4), (I.18)
where the inequalities follow from the Cauchy-Schwartz inequality, and the expectations are taken over all the randomness. Meanwhile, it holds that
‖φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1‖πi,1 ≤ ‖φi+1(s, ·)>θi+1 − φ0(s, ·)>θi+1‖πi,1 + ‖φi(s, ·)>θi+1 − φ0(s, ·)>θi+1‖πi,1. (I.19)
Combining (I.18) and (I.19), we obtain that E [ Eν∗ [ ‖φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1‖πi,1 ]] = O(R3/2 ·m−1/4). (I.20)
Similarly, it holds that E [ Eν∗ [ ‖φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1‖πi+1,1 ]] = O(R3/2 ·m−1/4), (I.21)
where the expectation is taken over all the randomness. By plugging (I.20) and (I.21) into (I.17), we obtain that
τi+1 · E [ Eν∗ [ |〈φi+1(s, ·)>θi+1 − φi(s, ·)>θi+1,∆i(· | s)〉| ]] = O(τi+1 ·R3/2 ·m−1/4). (I.22)
Finally, by plugging (I.16) and (I.22) into (I.8), it holds under Assumptions 4.2 and A.3 that E [ Eν∗ [∣∣〈log(πi+1(· | s)/πi(· | s)), πi(· | s)− πi+1(· | s)〉∣∣]]
≤ E [ Eν∗ [ DKL ( πi+1(· | s) ∥∥πi(· | s))]]+ η2 · (9R2 +M2) +O(τi+1 ·R3/2 ·m−1/4), where M is the absolute constant defined in Assumption A.3. Thus, we complete the proof of Lemma H.2.

heading: I.3 PROOF OF LEMMA H.3
text: Proof. Note that Eπθi [φθi(s, a ′)] and Eπθi [φωi(s, a ′)] depend solely on s ∈ S, where we write Eπθi [φθi(s, a
′)] = Ea′∼πθi (· | s)[φθi(s, a ′)] for notational simplicity. Thus, we have〈 Eπθi [ φθi(s, a ′)>δi − φωi(s, a′)>ωi ] , π∗(· | s)− πi(· | s) 〉 = 0, ∀s ∈ S. (I.23)
Meanwhile, following from the parameterization of πθ in (3.2) and (I.6) in §I.2, we obtain that〈 log ( πi+1(· | s)/πi(· | s) ) − η ·Qωi(s, ·), π∗(· | s)− πi(· | s) 〉 = 〈τi+1 · φθi+1(s, ·)>θi+1 − τi · φθi(s, ·)>θi − η · φωi(s, ·)>ωi, π∗(· | s)− πi(· | s)〉. (I.24)
In what follows, we define ∆∗i (· | ·) = π∗(· | ·)− πi(· | ·) for notational simplicity. Then, combining (I.23) and (I.24), we obtain for all s ∈ S that〈
log ( πi+1(· | s)/πi(· | s) ) − η ·Qωi(s, ·),∆∗i (· | s) 〉 = η · 〈φθi(s, ·)>δi − φωi(s, ·)>ωi,∆∗i (· | s)〉
+ τi+1 · 〈φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1,∆∗i (· | s)〉 = η · 〈φθi(s, ·) >δi − φωi(s, ·) >ωi,∆
∗ i (· | s)〉︸ ︷︷ ︸
(iii)
(I.25)
+ τi+1 · 〈φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1,∆∗i (· | s)〉︸ ︷︷ ︸ (iv) ,
where φθi and φωi are the centered feature mappings defined in (B.2) that correspond to θi and ωi, respectively, and δi is defined by
δi = η −1 · (τi+1 · θi+1 − τi · θi) = argmin ω∈B ‖F̂ (θi)ω − τi · ∇̂J(πθi)‖2. (I.26)
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ν∗ [ |〈φθi(s, ·) >δi − φωi(s, ·) >ωi, π ∗(· | s)〉| ]
≤ ∫ S×A |φθi(s, a) >δi − φωi(s, a) >ωi|dσ∗(s, a)
= ∫ S×A |φθi(s, a) >δi − φωi(s, a) >ωi| · dσ∗ dσi (s, a)dσi(s, a) ≤ ϕi · ‖φθi(·, ·) >δi − φωi(·, ·) >ωi‖σi , (I.27)
where dσ∗/dσi is the Radon-Nikodym derivative, ϕi is defined in (A.1) of Assumption A.2, and the last inequality follows from the Cauchy-Schwartz inequality. Similarly, it holds that
Eν∗ [ |〈φθi(s, a) >δi − φωi(s, a) >ωi, πi(a | s)〉| ] ≤ ∫ S×A |φθi(s, a) >δi − φωi(s, a) >ωi|dπi(a | s) · ν∗(s)
= ∫ S×A |φθi(s, a) >δi − φωi(s, a) >ωi| · dν∗ dνi (s)dσi(s, a) ≤ ψi · ‖φθi(·, ·) >δi − φωi(·, ·) >ωi‖σi , (I.28)
where dν∗/dνi is the Radon-Nikodym derivative, ψi is defined in (A.1) of Assumption A.2, and the last inequality follows from the Cauchy-Schwartz inequality. Combining (I.27) and (I.28), we obtain that
Eν∗ [ |〈φθi(s, ·) >δi − φωi(s, ·) >ωi,∆ ∗ i (· | s)〉| ] ≤ (ϕi + ψi) · ‖φθi(·, ·) >δi − φωi(·, ·) >ωi‖σi . (I.29)
It now suffices to upper bound ‖φθi(·, ·) >δi − φωi(·, ·) >ωi‖σi . With a slight abuse of notation, we write φθi = φθi(·, ·) and φωi = φωi(·, ·) hereafter for notational simplicity. Note that
‖δ>i φθi − ω > i φωi‖σi = √ Eσi [ (δ>i φθi − ω > i φωi) · (δ > i φθi − ω > i φωi) ] ≤ √∣∣(δi − ωi)>Eσi[φθi · (δ>i φθi − ω>i φωi)]∣∣︸ ︷︷ ︸
(iii.a)
(I.30)
+ √ Eσi [ (ω>i φθi − ω > i φωi) · (δ > i φθi − ω > i φωi) ]︸ ︷︷ ︸ (iii.b) .
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 ωi, δi ∈ B, where δi is defined in (I.26) and B = {α ∈ Rmd : ‖α−Winit‖2 ≤ R}. Therefore, we obtain that
‖ωi − δi‖2 ≤ 2R. (I.31)
Meanwhile, following from Proposition 3.1 and (3.7), it holds that Eσi [ F̂ (θi) ] = F (θi) = τ 2 i · Eσi [ φθi(φθi) >], Eσi [ ∇̂θJ(πθi) ] = τi · Eσi [ φθi · (φωi) >ωi ] , (I.32)
where the expectations are taken over σi given θi and ωi. In what follows, we write gi = Eσi [∇̂J(πθi)] for notational simplicity, where the expectation is taken over σi given θi and ωi. By plugging (I.31) and (I.32) into (iii.a) in (I.30), we obtain that∣∣∣(δi − ωi)>Eσi[(φθi · (δ>i φθi − ω>i φωi))]∣∣∣ = τ−2i · ∣∣(δi − ωi)>(F (θi) · δi − τi · gi)∣∣
≤ 2R · τ−2i · ‖F (θi) · δi − τi · gi‖2, (I.33)
where the last inequality follows from the Cauchy-Schwartz inequality and (I.31). By (I.33), we have
E [∣∣(δi − ωi)>Eσi[φθi(δ>i φθi − ω>i φωi)]∣∣1/2] ≤ Ci · E[(∥∥F (θi) · δi − τi · gi]∥∥2)1/2] ≤ Ci · E [( ‖F̂ (θi) · δi − τi · ∇̂θJ(πθi)‖2 + ‖ξi(δi)‖2
)1/2] ≤ Ci · { E [ ‖F̂ (θi) · δi − τi · ∇̂θJ(πθi)‖2 ] + E [ ‖ξi(δi)‖2 ]}1/2 , (I.34)
where the expectations are taken over all the randomness. Here the last inequality follows from the Jensen’s inequality, Ci = √ 2R · τ−1i , and ξi(δi) is defined by
ξi(δi) = F̂ (θi) · δi − τi · ∇̂θJ(πθi)− ( F (θi) · δi − τi · gi ) . (I.35)
In what follows, we upper bound ‖F̂ (θi) · δi − τi · ∇̂θJ(πθi)‖2 on the right-hand side of (I.34). Recall that we define δi by
δi = η −1 · (τi+1 · θi+1 − τi · θi) = argmin ω∈B ‖F̂ (θi) · ωi − τi · ∇̂θJ(πθi)‖2. (I.36)
Therefore, since ωi ∈ B, we obtain from (I.36) that
‖F̂ (θi) · δi − τi · ∇̂θJ(πθi)‖2 ≤ ‖F̂ (θi) · ωi − τi · ∇̂θJ(πθi)‖2 ≤ ‖F (θi) · ωi − τi · gi‖2 + ‖ξi(ωi)‖2, (I.37)
where recall that, similar to (I.35), we define ξi(ωi) by ξi(ωi) = F̂ (θi) · ωi − τi · ∇̂θJ(πθi)− ( F (θi) · ωi − τi · gi ) . (I.38)
By plugging (I.37) into (I.34), we obtain that E [∣∣(δi − ωi)>Eσi[φθi · (δ>i φθi − ω>i φωi)]∣∣1/2] ≤ Ci · { E [ ‖F (θi) · ωi − τi · gi‖2 ] + E [ ‖ξi(δi)‖2 ] + E [ ‖ξi(ωi)‖2 ]}1/2 , (I.39)
where Ci = √
2R · τ−1i and ξi(δi), ξi(ωi) are defined in (I.35) and (I.38), respectively. To upper bound the right-hand side of (I.39), it now suffices to upper bound the expectation E[‖F (θi) · ωi − τi · gi‖2]. By (I.32), we obtain that
‖F (θi) · ωi − τi · gi‖2 = τ2i · ∥∥Eσi[φθi · (φθi − φωi)>ωi]∥∥2
≤ τ2i · Eσi [ ‖φθi · (φθi − φωi) >ωi‖2 ] = τ2i · Eσi [ ‖φθi‖2 · |(φθi − φωi) >ωi| ] , (I.40)
where the inequality follows from the Jensen’s inequality. In what follows, we upper bound the right-hand side of (I.40). Note that ‖φθi(s, a)‖2 ≤ 2 for all (s, a) ∈ S × A. By further plugging into (I.40), we obtain that
‖F (θi) · ωi − τi · gi‖2 ≤ 2τ2i · Eσi [ |(φθi − φωi) >ωi| ] ≤ 2τ2i · ‖(φθi − φωi) >ωi‖σi , (I.41)
where the last inequality follows from the Jensen’s inequality. Recall that ωi, θi ∈ B. Therefore, by Assumption 4.2 and Corollary E.3, we have
E [ ‖(φθi − φωi) >ωi‖σi ]
≤ E [ ‖(φθi − φ0) >ωi‖σi ] + E [ ‖(φ0 − φωi) >ωi‖σi ] = O(R3/2 ·m−1/4), (I.42)
where the expectations are taken over all the randomness. Combining (I.41) and (I.42), we obtain that
E [ ‖F (θi) · ωi − τi · gi‖2 ] = O(2τ2i ·R3/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
E [∣∣(δi − ωi)>Eσi[φθi · (δ>i φθi − ω>i φωi)]∣∣1/2] ≤ Ci · { E [ ‖F (θi) · ωi − τi · gi‖2 ] + E [ ‖ξi(ωi)‖2 ] + E [ ‖ξi(δi)‖2
]}1/2 = O(R5/4 ·m−1/8) + √ 2R · τ−1i · { E [ ‖ξi(δi)‖2 + ‖ξi(ωi)‖2 ]}1/2 , (I.44)
where Ci = √ 2R · τ−1i and ξi(δi), ξi(ωi) are defined in Assumption A.1.
Upper Bounding (iii.b) in (I.30). Following from the Cauchy-Schwartz inequality, it holds that√ Eσi [ (ω>i φθi − ω > i φωi) · (δ > i φθi − ω > i φωi) ] ≤ ( ‖ω>i φθi − ω > i φωi‖σi · ‖δ > i φθi − ω > i φωi‖σi )1/2 . (I.45)
To upper bound the right-hand side of (I.45), we first upper bound ‖ω>i φθi −ω > i φωi‖σi . Recall that ωi, θi ∈ B. Following from Assumption 4.2 and Corollary E.3, it holds that
E [ ‖ω>i φθi − ω > i φ0‖2σi ] = O(R3 ·m−1/2),
E [ ‖ω>i φωi − ω > i φ0‖2σi ] = O(R3 ·m−1/2), (I.46)
where φ0 is defined in (B.1) and the expectations are taken over all the randomness. Therefore, following from (I.46), we obtain that
E [ ‖ω>i φθi − ω > i φωi‖ 2 σi ] ≤ 2E [ ‖ω>i φθi − ω > i φ0‖2σi ] + 2E [ ‖ω>i φωi − ω > i φ0‖2σi ] = O(R3 ·m−1/2). (I.47)
It remains to upper bound ‖δ>i φθi − ω > i φωi‖σi on the right-hand side of (I.45). Since δi ∈ B, by Assumption 4.2 and Corollary E.3, we obtain that
E [ ‖δ>i φθi − δ > i φ0‖2σi ] = O(R3 ·m−1/2), (I.48)
where the expectation is taken over all the randomness. Meanwhile, following from the fact that ‖φ0(s, a)‖2 ≤ 2 for all (s, a) ∈ S ×A, we obtain that
|δ>i φ0(s, a)− ω>i φ0(s, a)| ≤ ‖φ0(s, a)‖2 · ‖δi − ωi‖2 ≤ 4R, ∀(s, a) ∈ S ×A, (I.49)
where the first inequality follows from the Cauchy-Schwartz inequality and the second inequality follows from the fact that δi, ωi ∈ B. Combining (I.46), (I.48), and (I.49), we obtain that
E [ ‖δ>i φθi − ω > i φωi‖ 2 σi ] ≤ 3E [ ‖δ>i φθi − δ > i φ0‖2σi ] + 3E [ ‖δ>i φ0 − ω>i φ0‖2σi ] + 3E [ ‖ω>i φωi − ω > i φ0‖2σi ] = O(R2 +R3 ·m−1/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
E [{ Eσi [ (ω>i φθi − ω > i φωi)(δ > i φθi − ω > i φωi) ]}1/2] ≤ { E [ ‖ω>i φθi − ω > i φωi‖σi · ‖δ > i φθi − ω > i φωi‖σi
]}1/2 ≤ { E [ ‖ω>i φθi − ω > i φωi‖ 2 σi ] · E [ ‖δ>i φθi − ω > i φωi‖ 2 σi
]}1/4 = O(R3/2 ·m−1/4 +R5/4 ·m−1/8), (I.51)
where the inequalities follow from the Cauchy-Schwartz inequality and the expectations are taken over all the randomness.
Finally, by plugging (I.44), (I.51), and (I.30) into (I.29), we obtain that E [ Eν∗ [ |〈φθi(s, ·) >δi − φωi(s, ·) >ωi,∆ ∗ i (· | s)〉| ]] = η · (ϕi + ψi) · ( O(R5/4 ·m−1/8 +R3/2 ·m−1/4) (I.52)
+ √ 2R · τ−1i · { E [ ‖ξi(δi)‖2 + ‖ξi(ωi)‖2 ]}1/2) ,
where ξi(δi) and ξi(ωi) are defined in Assumption A.1. Here the expectations are taken over all the randomness.
Upper Bounding (iv) in (I.25). The analysis of (iv) is similar to that of (ii) in §H.8. It holds that
|〈φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1,∆∗i (· | s)〉| ≤ |〈φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1, π∗(· | s)〉|+ |〈φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1, πi(· | s)〉| ≤ ‖φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1‖π∗,1 + ‖φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1‖πi,1. (I.53)
Note that θi, θi+1 ∈ B. Following from Assumption 4.2 and Lemma E.2, it holds that E [ Eν∗ [ ‖φθi+1(s, ·)>θi+1 − φ0(s, ·)>θi+1‖π∗,1 ]] ≤ E [ ‖φθi+1(·, ·)>θi+1 − φ0(·, ·)>θi+1‖σ∗ ] = O(R3/2 ·m−1/4),
E [ Eν∗ [ ‖φθi(s, ·)>θi+1 − φ0(s, ·)>θi+1‖π∗,1 ]] ≤ E [ ‖φθi(·, ·)>θi+1 − φ0(·, ·)>θi+1‖σ∗ ] = O(R3/2 ·m−1/4), (I.54)
where the inequalities follow from the Jensen’s inequality, φ0 is the feature mapping defined in (3.3) with θ = Winit, and the expectations are taken over all the randomness. Following from (I.54), we obtain that
E [ Eν∗ [ ‖φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1‖π∗,1 ]] ≤ E [ Eν∗ [ ‖φθi+1(s, ·)>θi+1 − φ0(s, ·)>θi+1‖π∗,1
]] + E [ Eν∗ [ ‖φθi(s, ·)>θi+1 − φ0(s, ·)>θi+1‖π∗,1
]] = O(R3/2 ·m−1/4), (I.55)
where the expectations are taken over all the randomness. Similarly, it holds that E [ Eν∗ [ ‖φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1‖πi,1 ]] = O(R3/2 ·m−1/4). (I.56)
By plugging (I.55) and (I.56) into (I.53), we obtain that E [ Eν∗ [ |〈φθi+1(s, ·)>θi+1 − φθi(s, ·)>θi+1,∆∗i (· | s)〉| ]] = O(R3/2 ·m−1/4). (I.57)
Finally, by plugging (I.52) and (I.57) into (I.25), we obtain that E [ Eν∗ [∣∣〈log(πi+1(· | s)/πi(· | s))− η ·Qωi(s, ·), π∗(· | s)− πi(· | s)〉∣∣]]
≤ √ 2(ϕi + ψi) · η ·R1/2 · τ−1i · { E [ ‖ξi(δi)‖2 ] + E [ ‖ξi(ωi)‖2 ]}1/2 +O ( (τi+1 + 1) ·R3/2 ·m−1/4 + η ·R5/4 ·m−1/8 ) ,
where ϕi, ψi are defined in Assumption A.2 and ξi(δi), ξi(ωi) are defined in Assumption A.1. Thus, we complete the proof of Lemma H.3.

heading: J AUXILLIARY LEMMA
text: Lemma J.1 (Performance Difference (Kakade and Langford, 2002)). It holds for any π and π̃ that J(π̃)− J(π) = (1− γ)−1 · Eπ̃·νπ̃ [ Aπ(s, a) ] .
Here νπ̃ is the state visitation measure corresponding to π̃, which is defined in (2.3).
Proof. See Kakade and Langford (2002) for a detailed proof.

Review summaries:
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.