On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
Year: 2021

Abstract:
Policy gradient (PG) gives rise to a rich class of reinforcement learning (RL) methods. Recently, there has been an emerging trend to accelerate the existing PG methods such as REINFORCE by the variance reduction techniques. However, all existing variance-reduced PG methods heavily rely on an uncheckable importance weight assumption made for every single iteration of the algorithms. In this paper, a simple gradient truncation mechanism is proposed to address this issue. Moreover, we design a Truncated Stochastic Incremental Variance-Reduced Policy Gradient (TSIVR-PG) method, which is able to maximize not only a cumulative sum of rewards but also a general utility function over a policy’s long-term visiting distribution. We show an Õ( −3) sample complexity for TSIVR-PG to find an -stationary policy. By assuming the overparameterization of policy and exploiting the hidden convexity of the problem, we further show that TSIVR-PG converges to global -optimal policy with Õ( −2) samples.

heading: 1 Introduction
text: In this paper, we investigate the theoretical properties of Policy Gradient (PG) methods for Reinforcement Learning (RL) [43]. In view of RL as a policy optimization problem, the PG method
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
parameterizes the policy function and conduct gradient ascent search to improve the policy. In this paper, we consider the soft-max policy parameterization
πθ(a|s) = exp{ψ(s, a; θ)}∑ a′ exp{ψ(s, a′; θ)}
(1)
where (s, a) is a state-action pair and ψ is some smooth function. Potentially, one can set the function ψ to be some deep neural network with weights θ and input (s, a). The main problem considered in this paper is the policy optimization for a general utility function:
max θ R(πθ) := F (λ
πθ ), (2)
where F is a general smooth function, and λπθ denotes the unnormalized state-action occupancy measure (also referred to as the visitation measure). For any policy π and initial state distribution ξ,
λπ(s, a) := +∞∑ t=0 γt · P ( st = s, at = a ∣∣π, s0 ∼ ξ), (3) where γ stands for the discount factor and P denotes the probability of a certain event. When F is linear, the problem reduces to the standard policy optimization problem where the objective is to maximize a cumulative sum of rewards. When F is nonlinear, problem (2) goes beyond standard Markov decision problems: examples include the max-entropy exploration [16], risk-sensitive RL [50], certain set constrained RL [27], and so on.
In the standard cumulative-return case (i.e., F is linear), numerous works have studied PG methods in various scenarios, see e.g. [47, 5, 58, 22, 21, 37, 38, 23]. When directly optimizing over the policy space without any parameterization, the policy mirror descent (PMD) method [23] achieves an Õ( −2) sample complexity to find an O( )-optimal solution. However, for the more practical parameterized policy optimization, to the authors’ best knowledge, the most recent variant of PG methods, using the SARAH/Spider stochastic variance reduction technique [13, 29], find a local -stationary policy using O( −3) samples [48, 33]. This poses a contrast with the known Õ( −2) sample complexity results that can be achieved by various value-based methods [4, 42, 41] and are provably matching information-theoretic lower bounds [12, 3, 4]. In this paper, we attempt to close this gap and prove an Õ( −2) sample complexity bound for a PG method. Most importantly, when it comes to PG estimation, the application of the variance reduction technique typically relies on certain off-policy PG estimator, resulting in the difficulty of distribution shift. We notice that none of the existing variance-reduced PG methods attempt to address this challenge. Instead, they directly make an uncheckable assumption that the variance of the importance weight is bounded for every policy pair encountered in running the algorithm, see e.g. [31, 48, 49, 33]. In this paper, we propose a simple gradient truncation mechanism to fix this issue.
Next, let us go beyond cumulative return and consider policy optimization for a general utility where F may be nonlinear. However, much less is known in this setting. The nonlinearity of F invalidates the concept of Q-function and value function, leading to the failure of policy gradient theorem [44]. To overcome such difficulty, [51] showed that the policy gradient for the general utilities is the solution to a min-max problem. However, estimating a single PG is highly nontrivial in this case. It is still unclear how to make PG methods to use samples in a most efficient way.
In this paper, we aim to investigate the convergence and sample efficiency of the PG method, using episodic sampling, for both linear F (i.e., cumulative rewards) and nonlinear F (i.e., general utility). Observe that problem (2) is an instance of the Stochastic Composite Optimization (SCO) problem [45, 46]: minx f(Eν [gν(x)]), which involves an inner expectation that corresponds to the occupancy measure λπ . Motivated by this view point, we attempt to develop stochastic policy gradient method with provable finite-sample efficiency bounds.
Main results. Our main results are summarized below.
• We propose the TSIVR-PG algorithm to solve problem (2) via episodic sampling. It provides a conceptually simple stochastic gradient approach for solving general utility RL.
• We provide a gradient truncation mechanism to address the distribution shift difficulty in variance-reduced PG methods. Such difficulty has never been addressed in previous works.
• We show that TSIVR-PG finds an -stationary policy using Õ( −3) samples if F and ψ are general smooth functions. When F is concave and ψ satisfies certain overparameterization condition, we show that TSIVR-PG obtains a gloal -optimal policy using Õ( −2) samples.
Technical contribution. Our analysis technique is also of independent interest in the relating areas.
• For stochastic composite optimization (SCO), most existing algorithms require estimating the Jacobian matrix of the inner mapping, which corresponds to ∇θλπθ in our setting. This is in practice prohibitive if the Jacobian matrix has high dimensions, which is exactly the case in our problem. Unlike SCO algorithms such as [24, 54, 53, etc.], our analysis enables us to avoid the Jacobian matrix estimation.
• For the stochastic variance-reduced gradient methods, our analysis implies a convergence of SARAH/Spider methods to global optimality and a new O( −2) sample complexity for nonconvex problems with “hidden convexity” structure, which has not been studied in the optimization community yet.

heading: 2 Related Works
text: Policy gradient gives rises to a rich family of RL algorithms, such as REINFORCE and many of its variants [47, 5, 58], as well as extensions such as the natural policy gradient methods [20, 32], the actor-critic methods [22, 21, 28], the trust-region policy optimization [37, 57, 39], and the proximal policy optimization method [38, 25], etc. In this paper we mainly focus on REINFORCE-type methods, where many of them need Õ( −4) samples to find an -stationary solution, including the vanilla REINFORCE [47], as well as its variants with baseline [58, 43] and GPOMDP [5], etc. By incorporating the stochastic variance reduction techniques, the sample efficiency of PG methods can be further improved. In [31], the SVRG [19] variance reduction scheme is adopted and an O( −4) sample complexity is achieved, which is later improved to O( −10/3) by [48]. With additional Hessian information, [40] achieved an O( −3) complexity. By utilizing a more efficient SARAH/Spider [29, 13] variance reduction scheme, people are able to achieve O( −3) sample complexity without second-order information [48, 33]. We would like to comment that these results are only for finding -stationary (rather than near-optimal) solutions, and all of them requires an uncheckable condition on the importance weights in every iteration.
Recently, for cumulative reward, a series of works have started to study the convergence of policy gradient method to global optimal solutions [1, 14, 56, 6, 26, 7, 9, 55]. In particular, [51] exploited the hidden convexity property of the MDP problem and established the convergence to global optimality for general utility RL problem, as long as the policy gradient can be computed exactly.
Our approach is related to the stochastic composite optimization (SCO) [45, 46]. For the general composition problem, there have been numerous developments, including momentum-based and multi-time-scale algorithms [45, 46, 15], and various composite stochastic variance-reduced algorithms [24, 17, 52, 54]. Our approach is also inspired by variance reduction techniques that were initially used for stochastic convex optimization, see [19, 36, 11, 29]; and were later on extended to the stochastic nonconvex optimization problems [2, 34, 18, 35, 13, 30]. In particular, we will utilize the SARAH/Spider scheme [13, 30].

heading: 3 Problem Formulation
text: Consider an MDP with a general utility function, denoted as MDP(S,A,P, γ, F ), where S is a finite state space, A is a finite action space, γ ∈ (0, 1) is a discount factor, and F is some general utility function. For each state s ∈ S, a transition to state s′ ∈ S occurs when selecting an action a ∈ A following the distribution P(·|a, s). For each state s ∈ S , a policy π gives a distribution π(·|s) over the action space A. Let ξ be the initial state distribution and let the unnormalized state-action occupancy measure λπ be defined by (3), we define the general utility function F as a smooth function of the occupancy measure, and the goal of the general utility MDP is to maximize F (λπ). With the policy πθ being parameterized by (1), we propose to solve problem (2), which is
max θ R(πθ) := F (λ
πθ ) .
For notational convenience, we often write λ(θ) instead of λπθ . Such utility function is very general and includes many important problems in RL. We provide a few examples where F are concave.
Example 3.1 (Cumulative reward). When F (λπθ ) = 〈r, λπθ 〉, for some r ∈ R|S||A|. Then we recover the standard cumulative sum of rewards: R(πθ) = E [∑+∞ t=0 γ t · r(st, at) ∣∣πθ, s0 ∼ ξ].
Example 3.2 (Maximal entropy exploration). Let µπθ (s) = (1 − γ) ∑ a λ
πθ (s, a), ∀s ∈ S be the state occupancy measure, which is the margin of λπθ over S. Let F (·) be the entropy function, then we recover the objective for maximal entropy exploration [16]:R(πθ) = − ∑ s∈S µ πθ (s) logµπθ (s).
Example 3.3 (RL with Set Constraint). Let z(st, at) ∈ Rd be a vector feedback received in each step. The cumulative feedback is u(πθ) := E [∑+∞ t=0 γ t · z(st, at)|s0 ∼ ξ, πθ ]
= Mλπθ for some matrix M ∈ Rd×|S||A|. [27] proposed a set-constrained RL problem which aims to find a policy π s.t. u(π) ∈ U for some convex set U . This problem can be formulated as an instance of (2) by letting F (·) be the negative squared distance: R(πθ) = −minu′∈U ‖u′ − u(πθ)‖2.

heading: 4 The TSIVR-PG Algorithm
text: In this section, we propose a Truncated Stochastic Incremental Variance-Reduced Policy Gradient (TSIVR-PG) method, which is inspired by techniques of variance reduction and off-policy estimation. A gradient truncation mechanism is proposed to provably control the importance weights in off-policy sampling.

heading: 4.1 Off-Policy PG Estimation
text: Policy Gradient First, let us derive the policy gradient of the general utility. Let V πθ (r) be the cumulative reward under policy πθ, initial distribution ξ and reward function r. By Example 3.1, V πθ (r) = 〈λ(θ), r〉, the chain rule and policy gradient theorem [44] indicates that
∇θV πθ (r) = [ ∇θλ(θ) ]> r = Eξ,πθ [+∞∑ t=0 γt · r(st, at) · ( t∑ t′=0 ∇θ log πθ(at′ |st′) )] , (4)
where∇θλ(θ) is the Jacobian matrix of the vector mapping λ(θ). That is, policy gradient theorem actually provides a way for computing the Jacobian-vector product for the occupancy measure. Following the above observation and the chain rule, we have
∇θR(πθ)=[∇θλ(θ)]>∇λF (λ(θ)) = ∇θV πθ (r)|r=∇λF(λ(θ)).
Therefore, we can estimate the policy gradient using the typical REINFORCE as long as we pick the “quasi-reward function" as r := ∇λF (λ(θ)). To find this quasi-reward, we need to estimate the state-action occupancy measure λ(θ) (unless F is linear).
Importance Sampling Weight Let τ = {s0, a0, s1, a1, · · · , sH−1, aH−1} be a length-H trajectory generated under the initial distribution ξ and the behavioral policy πθ1 . For any target policy πθ2 , we define the importance sampling weight as
ωt(τ |θ1, θ2) = Πth=0πθ2(ah|sh) Πht=0πθ1(ah|sh) , 0 ≤ t ≤ H − 1. (5)
It is worth noting that such importance sampling weight is inevitable in the stochastic variance reduced policy gradient methods, see [31, 48, 49, 33, 25]. In these works, the authors usually directly assume Var(ωH−1(τ |θ1, θ2)) ≤ W for all the policy pairs encountered in every iteration of their algorithms. However, such assumption is too strong and is uncheckable.
Based on the above notation of behavioral and target policies, as long as the importance sampling weights, we present the following off-policy occupancy and policy gradient estimators.
Off-Policy Occupancy Measure Estimator Denote esa the vector with (s, a)-th entry being 1 while other entries being 0. We define the following estimator for λ(θ2)
λ̂ω(τ |θ1, θ2) := H−1∑ t=0 γt · ωt(τ |θ1, θ2) · estat . (6)
When θ2 = θ1, ωt(τ |θ1, θ2) ≡ 1 and λ̂ω(τ |θ1, θ2) becomes the on-policy (discounted) empirical distribution, for which we use the simplified notion λ̂(τ |θ2) := λ̂ω(τ |θ2, θ2).
Off-Policy Policy Gradient Estimator Let r ∈ R|S||A| be any quasi-reward vector. We aim to estimate the Jacobian-vector product [∇θλ(θ2)]>r for target policy πθ2 by
ĝω(τ |θ1, θ2, r) := H−1∑ t=0 γt · ωt(τ |θ1, θ2) · r(st, at) · ( t∑ t′=0 ∇θ log πθ2(at′ |st′) ) . (7)
When θ2 = θ1, ωt(τ |θ1, θ2) ≡ 1 and ĝω(τ |θ1, θ2, r) becomes the on-policy REINFORCE estimator with quasi-reward function r. In this case, we use the simplified notion ĝ(τ |θ2, r) := ĝω(τ |θ2, θ2, r).
Estimators λ̂ω(τ |θ1, θ2) and ĝω(τ |θ1, θ2, r) are almost unbiased. In details, ‖Eτ∼πθ1 [λ̂ω(τ |θ1, θ2)]− λ(θ2)‖≤O(γH) and ‖Eτ∼πθ1 [ĝω(τ |θ1, θ2, r)]− [ ∇θλ(θ2) ]> r‖≤O(H·γH); see details in Appendix E. Therefore the bias due to truncation is almost negligible if H is properly selected.

heading: 4.2 The TSIVR-PG Algorithm
text: To achieve the Õ( −2) sample complexity, we propose an epoch-wise algorithm called Truncated Stochastic Incremental Variance-Reduced PG (TSIVR-PG) Algorithm. Let θi0 be the starting point of the i-th epoch, TSIVR-PG constructs the estimators for λ(θi0), quasi-reward ∇λF (λ(θi0)) and the policy gradient ∇θF (λ(θi0)) by
λi0 = 1
N ∑ τ∈Ni λ̂(τ |θi0), ri0 = ∇λF (λi0) and gi0 = 1 N ∑ τ∈Ni ĝ(τ |θi0, ri0). (8)
where Ni is a set of N independent length-H trajectories sampled under πθi0 . When j ≥ 1,
λij = 1
B ∑ τ∈Bij ( λ̂(τ |θij)− λ̂ω(τ |θij , θij−1) ) + λij−1, r i j = ∇λF (λij) (9)
gij = 1
B ∑ τ∈Bij ( ĝ ( τ |θij , rij−1 ) − ĝω ( τ |θij , θij−1, rij−2 ) ) + gij−1, (10)
where Bij is a set ofB independent length-H trajectories sampled under πθij , and we default r i −1 := r i 0. Specifically, ĝω(τ |θij , θij−1, rij−2) is used instead of ĝω(τ |θij , θij−1, rij−1) for independence issue. The details of the TSIVR-PG algorithm are stated in Algorithm 1.
Algorithm 1: The TSIVR-PG Algorithm
1 Input: Initial point θ10 = θ̃0; batch sizes N and B; sample trajectory length H; stepsize η; epoch length m; gradient truncation radius δ. 2 for Epoch i = 1, 2, ..., do 3 for Iteration j = 0, ...,m− 1 do 4 if j == 0 then 5 Sample N trajectories under policy πθi0 of length H , collected as Ni. 6 Compute estimators λi0, r i 0 and g i 0 by (8). Default r i −1 := r i 0. 7 else 8 Sample B trajectories under policy πθij with length H , collected as B i j . 9 Compute estimators λij , r i j and g i j by (9) and (10).
10 Update the policy parameter by a truncated gradient ascent step:
θij+1 = { θij + η · gij , if η‖gij‖ ≤ δ, θij + δ · gij/‖gij‖ , otherwise.
(11)
11 Set θi+10 = θ̃i = θ i m.
It is worth noting that the truncated gradient step (11) is equivalent to a trust region subproblem:
θij+1 = argmax ‖θ−θij‖≤δ
F (λ(θij)) + 〈gij , θ − θij〉+ 1
2η ‖θ − θij‖2 (12)
where the approximate Hessian matrix is simply chosen as (η)−1 · I .

heading: 5 Sample Efficiency of TSIVR-PG
text: In this section, we analyze the finite-sample performance of TSIVR-PG. We first show that TSIVR-PG finds an -stationary solution with Õ( −3) samples. Given additional assumptions, we show that TSIVR-PG finds a global -optimal solution with Õ( −2) samples .

heading: 5.1 Convergence Towards Stationary Points
text: Since we focus on the soft-max policy parameterization where πθ(a|s) = exp{ψ(s,a;θ)}∑ a′ exp{ψ(s,a′;θ)}
, we make the following assumptions on the parameterization function ψ and the utility F . Assumption 5.1. ψ(s, a; ·) is twice differentiable for all s and a. There ∃ `ψ, Lψ > 0 s.t.
max s∈S,a∈A sup θ ‖∇θψ(s, a; θ)‖ ≤ `ψ and max s∈S,a∈A sup θ ‖∇2θψ(s, a; θ)‖ ≤ Lh, (13)
where ‖ · ‖ stands for L2 norm and spectral norm for vector and matrix respectively. Assumption 5.2. F is a smooth and possibly nonconvex function. There exists `λ,∞ > 0 such that ‖∇λF (λ)‖∞ ≤ `λ,∞. And there exist constants Lλ,∞, Lλ > 0 s.t. it holds for ∀λ, λ′ that
‖∇λF (λ)−∇λF (λ′)‖∞ ≤ Lλ‖λ− λ′‖2 and ‖∇λF (λ)−∇λF (λ′)‖∞ ≤ Lλ,∞‖λ− λ′‖1.
Based on the above assumptions, we have the following supporting lemmas. Lemma 5.3. Given Assumption 5.1 and 5.2, the following results hold: (i). For any policy parameter θ and any state-action pair (s, a), the following inequalities hold: ‖∇θ log πθ(a|s)‖ ≤ 2`ψ , ‖∇2θ log πθ(a|s)‖ ≤ 2(Lψ + `2ψ), and ‖∇θF (λ(θ))‖ ≤ 2`ψ·`λ,∞ (1−γ)2 . (ii). For any policy parameters θ1 and θ2, it holds that ‖λπθ1 − λπθ2‖1 ≤ 2`ψ(1−γ)2 · ‖θ1 − θ2‖. (iii). The objective function F ◦λ(·) is Lθ-smooth, with Lθ = 4Lλ,∞·`2ψ (1−γ)4 + 8`2ψ·`λ,∞ (1−γ)3 + 2`λ,∞·(Lψ+`2ψ) (1−γ)2 .
To measure the convergence, we propose to use the gradient mapping defined as follows:
Gη(θ) = θ+ − θ η , where θ+ = { θ + η · g , if η‖g‖ ≤ δ, θ + δ · g/‖g‖ , otherwise
where g = ∇θF (λ(θ)). We remark that, E[‖Gη(θij)‖2] is more suitable for the ascent analysis of the truncated gradient updates, compared with the commonly used E[‖∇θF (λ(θij))‖2]. Note that Gη(θ) = ∇F (λ(θ)) if ‖Gη(θ)‖ ≤ δ and ‖∇F (λ(θ))‖ is bounded for any θ. Based on such observation, we have the following lemma to validate the choice of the proposed stationarity measure. Lemma 5.4. For any random vector θ, E[‖Gη(θ)‖] ≤ implies E[‖∇θF (λ(θ))‖] ≤ O(δ−1 · ).
Based on the notion of Gη , we characterize the per-iteration ascent as follows. Lemma 5.5. Let the iterates be generated by Algorithm 1. Then it holds that
F (λ(θij+1))≥F (λ(θij))+ η
4 ‖Gη(θij)‖2+ ( 1 2η −Lθ ) ‖θij+1−θij‖2− (η 2 + 1
2Lθ
) ‖∇θF (λ(θij))−gij‖2.
This suggests us to bound mean-squared-error E[‖∇θF (λ(θij))−gij‖2]. For this purpose, we need to bound the importance sampling weight, by utilizing the soft-max form of policy parameterization (1). Lemma 5.6. For any behavioral policy πθ1 and target policy πθ2 parameterized by (1), the importance weight satisfies ωt(τ |θ1, θ2) ≤ exp { 2(t+ 1)`ψ‖θ1 − θ2‖ } , for ∀0 ≤ t ≤ H − 1.
Since TSIVR-PG only uses importance weights for two consecutive iterations θij , θ i j−1 while forcing ‖θij−θij−1‖≤δ by the truncated gradient step (11), we have ωH−1(τ |θij ,θij−1)≤exp{2H`ψδ} w.p. 1. As we will see later, the effective horizonH only has a mild magnitude ofO ( (1−γ)−1 ·log(1/ ) ) , the truncation radius only need to satisfy δ = O(H−1`−1ψ ) s.t. ωt−1(τ |θij ,θij−1)=O(1), for ∀t≤H−1. Consequently, combining Lemma 5.3, 5.6 and Lemma B.1 of [48] gives the following result. Lemma 5.7. Let policy πθ be parameterized by (1) with function ψ satisfying Assumption 5.1. Suppose behavioral policy πθ1 and target policy πθ2 satisfy ‖θ1 − θ2‖ ≤ δ, then
E[ωt(τ |θ1, θ2)] = 1 and Var (ωt(τ |θ1, θ2)) ≤ Cω(t+ 1) · ‖θ1 − θ2‖2, where τ is sampled under policy πθ1 , and Cω(t) = t ( 4`2ψ(t+ 1 2 ) + 2Lψ ) (e4`ψδt + 1).
As a result, we can bound the mean-squared-error of the gij as follows.
Lemma 5.8. For the PG estimators gij , we have E [ ‖gij −∇θF (λ(θij))‖2 ] ≤ C1 N + C2γ 2H + C3 B · j∑ j′=1 E [ ‖θij′−1 − θij′‖2 ] + C4E [ ‖θij−1 − θij‖2
] for some constants C1, .., C4 > 0. In case j = 0, we default ∑0 j′=1 · = 0.
The expression of constants Ci’s are complicated, we provide their detailed formula in the appendix. If we set H = O ( log(1/ ) 1−γ ) and δ ≤ 12H`ψ , then Ci only depends polynomially on the Lipschitz constants, log( −1), and (1− γ)−1. Combining Lemma 5.5, 5.8, and 5.4 gives Theorem 5.9.
Theorem 5.9. For Algorithm 1, we choose H = 2 log(1/ )1−γ , δ = 1 2H`ψ , B = m = −1, N = −2, η = 1 1+(C3+C4)/L2θ · 12Lθ . After running the algorithm for T = −1 epochs and output θout from {θij} i=1,··· ,T j=0,··· ,m−1 uniformly at random, we have E[‖Gη(θout)‖] ≤ O( ). The total number of samples is T × ((m− 1)B +N)×H = Õ( −3). By Lemma 5.4, we also have E[‖∇θF (λ(θout))‖] ≤ O( ).

heading: 5.2 Convergence Towards Global Optimality
text: Next, we provide a mechanism to establish the convergence of TSIVR-PG to global optimality. For this purpose, we introduce the hidden convexity of the general utility RL problem. In addition to the smoothness of F (Assumption 5.2), we further assume its concavity, formally stated as follows. Assumption 5.10. Function F is a concave function of the state-action occupancy measure.
Let L be the image of the mapping λ(θ). Then the parameterized policy optimization problem (2) can be rewritten as an equivalent occupancy optimization problem:
maxθ F (λ(θ)) ⇐⇒ maxµ∈L F (µ). (14) When the policy parameterization is powerful enough to represent any policy, the image L is a convex polytope, see e.g. [10]. Since F is concave, the occupancy optimization problem is a convex optimization problem. In this case, if the mapping λ(·) is invertible (see [51]), we may view the original problem (2) as a reformulation of a convex problem by a change of variable: θ = λ−1(µ). We call this property “hidden convexity”. However, requiring λ(·) to be invertible is too restrictive, and it doesn’t even hold for simple soft-max policy with ψ(s, a; θ) = θsa where multiple θ correspond to a same policy. Therefore, we adopt a weaker assumption where (i). πθ can represent any policy (ii). a continuous inverse λ−1(·) can be locally defined over a subset of θ. Assumption 5.11. For policy parameterization of form (1), θ overparametrizes the set of policies in the following sense. (i). For any θ and λ(θ), there exist (relative) neighourhoods θ ∈ Uθ ⊂ B(θ, δ) and λ(θ) ∈ Vλ(θ) ⊂ λ(B(θ, δ)) s.t. ( λ|Uθ ) (·) forms a bijection between Uθ and Vλ(θ), where(
λ|Uθ ) (·) is the confinement of λ onto Uθ. We assume (λ|Uθ )−1(·) is `θ-Lipschitz continuous for any θ. (ii). Let πθ∗ be the optimal policy. Assume there exists ̄ small enough, s.t. (1− )λ(θ) + λ(θ∗) ∈ Vλ(θ) for ∀ ≤ ̄, ∀θ.
Based on Assumption 5.11, we replace Lemma 5.5 with the following lemma.
Lemma 5.12. For ∀ < ̄ with ̄ defined in Assumption 5.11, it holds for all iterations that F (λ(θ∗))− F (λ(θij+1)) ≤ (1− ) ( F (λ(θ∗))− F (λ(θij)) ) (15)
+ ( Lθ + 1
2η ) 2 2`2θ (1− γ)2 − ( 1 2η − Lθ ) ‖θij+1 − θij‖2 + 1 Lθ ‖gij −∇θF (λ(θij))‖2.
The analysis of Lemma 5.12 is very different from its nonconvex optimization counterpart (Lemma 5.5). Next, we derive the sample complexity of the TSIVR-PG algorithm given Lemma 5.12 and 5.8. Theorem 5.13. For TSIVR-PG method (Algorithm 1), let ∈ (0, ̄) be the target accuracy. If we choose H,m,B,N and δ according to Theorem 5.9. and we let the stepsize to be small enough s.t. η ≤ 12Lθ+8(C3+C4)/Lθ , then after at most T = log2( −1) epochs, E [ F (λ(θ∗))−F (λ(θ̃T )) ] ≤ O( ). The total number of samples taken is T × ((m− 1)B +N)×H = Õ( −2).

heading: 6 Numerical Experiments

heading: 6.1 Maximizing Cumulative Reward.
text: In this experiment, we aim to evaluate the performance of the TSIVR-PG algorithm for maximizing the cumulative sum of reward. As the benchmarks, we also implement the SVRPG [49], the SRVRPG [48], the HSPGA [33], and the REINFORCE [47] algorithms. Our experiment is performed on benchmark RL environments including the FrozenLake, Acrobot and Cartpole that are available from OpenAI gym [8], which is a well-known toolkit for developing and comparing reinforcement learning algorithms. For all the algorithms, their batch sizes are chosen according to their theory. In details, let be any target accuracy. For both TSIVR-PG and SRVR-PG, we set N = Θ( −2), B = m = Θ( −1). For SVRPG, we set N = Θ( −2), B = Θ( −4/3) and m = Θ( −2/3). For HSPGA, we set B = Θ( −1), other parameters are calculated according to formulas in [33] given B. For REINFORCE, we set the batchsize to be N = Θ( −2). The parameter ε and the stepsize/learning rate are tuned for each individual algorithm using a grid search. For each algorithm, we run the experiment for multiple times with random initialization of the policy parameters. The curve is obtained by first calculating the moving average of the most recent 50 episodes, and then calculate the median of the return over the outcomes of different runs. The upper and lower bounds of the shaded area are calculated as the 14 and 3 4 quantiles over the outcomes. We run the experiment for 10 times for the FrozenLake environment and 50 times for the other environments. The detailed parameters used in the experiments are presented in the Appendix.
FrozenLake The FrozenLake8x8 environment is a tabular MDP with finite state and action spaces. For this environment, the policy is parameterized with ψ(s, a; θ) = θsa.
Cartpole and Acrobot Both the Cartpole environment and the Acrobot environment are environments with a discrete action space and a continuous state space. For both environments, we use a neural network with two hidden layers with width 64 for both layers to model the policy.
Result We plot our experiment outcomes in Figure 6.1. The experiments show that given enough episodes, all of the algorithms are able to solve the tasks, achieving nearly optimal returns. And as expected, the REINFORCE algorithm takes the longest time to find the optimal policy. While the other algorithms yield a faster convergence speed, the TSIVR-PG algorithm consistently outperforms the other benchmark algorithms under all of the environments, showing the advantage of our method.

heading: 6.2 Validating the Õ( −2) Sample Complexity
text: Besides the comparison between different benchmark algorithms, we also perform a validation experiment showing that for certain environments, the convergence rate of TSIVR-PG is close to the theoretical guarantee. Because the parameters N,B,m are dependent on the target accuracy , in this section we adopt a different way to set up these parameters: We first set a fixed epoch E, and perform experiments using different values of the parameter N . The parameter B and m are set according to our choice of N by B = m = √ N . The performance of the algorithm output is calculated as the average score of the last few episodes, which is then averaged over 10 independent runs. Again, we use the FrozenLake8x8 environment to do the experiment. Because FrozenLake8x8 is a tabular
environment whose transition and reward function can be easily obtained from the document, we can calculate it’s optimal value simply by value iteration, which takes 0.4146 when we choose γ = 0.99. In this way, we calculate the gap between the algorithm return and the optimal value, and get log-log figure w.r.t. the gap and the number of episodes calculated by E(N +Bm) = 2EN .
Result The result is shown in the first sub-figure of Figure 6.3, where the blue curve is the gap between the average return of experiment outcome and the optimal value and the shaded area is the range of one standard deviation of the logarithm value. In addition, we add a orange dotted line to fit the convergence curve, whose slope takes value −0.496, which nearly matches the O( −2) theoretical bound (slope −0.5).

heading: 6.3 Maximizing Non-linear Objective Function
text: The TSIVR-PG algorithm is designed not only to solve typical RL problems, but is also able to solve a broader class of problems where the objective function is a general concave function. Unfortunately, none of the benchmark algorithms proposed in the previous section have the ability to solve this kind of problem. To evaluate the performance of our algorithm, we choose another benchmark algorithm, which is the MaxEnt algorithm [16]. In the experiment, we use FrozenLake8x8 environment since it’s more tractable to compute λ for a discrete state space. We set the objective function as
F (λ) = ∑ s∈S log (∑ a∈A λs,a + σ ) ,
where σ is a fixed small constant. We choose σ = 0.125 in our experiment. The orders of N,B,m are set in the same way as those in section 6.1. For the MaxEnt algorithm, note that in the original paper, the nonlinear objective function assumes the input value is the stationary state distribution dπ , but the input value can easily be changed into our λ without changing the steps of the algorithm much. The result is illustrated in Fig. 6.3. From the result, we may see that our algorithm consistently outperforms the benchmark.

heading: 7 Broader Impact
text: There has been an emerging trend of applying stochastic variance reduction technique to enhance the performance of the policy gradient methods. However, all the existing variance-reduced policy gradient methods depend on an algorithm-dependent assumption that is made to every single iteration in running the algorithm, which actually may not be satisfied by many of these algorithms. We propose a simple yet effective mechanism to fix such dilemma for applying the SARAH/Spider variance reduction scheme in policy gradient methods. Our analysis can also be applied to other schemes such as STORM and Hybrid SARAH-SGD. Beyond that, we also show how the hidden convexity and overparameterization of the RL problem can help stochastic variance-reduced policy gradient methods to converge to global optima and yield better sample complexity.

heading: 8 Limitation
text: To compute the policy gradient for the general utility function, one needs to compute gradient of the function F with respect to the state-action occupancy measure. Although for many instances, including standard cumulative sum of reward (Example 3.1) and set constrained RL (Example 3.3), estimating the occupancy measure is not necessary. There are many instances where estimating the occupancy measure is unavoidable. Due to the curse of dimensionality, the need for estimating the occupancy measure is a potential limitation if the state and action spaces are continuous and high-dimensional. One potential solution is to incorporate a function approximation for the occupancy measure, in a similar style of the Q-function approximation in the actor-critic method. We leave this for future development.

Review summaries:
There is a lot of interest in studying policy gradient type of algorithms for solving the RL problem recently.  This paper develops a variance reduced policy gradient method, where the objective function can be some general utility function instead of just being the cumulative reward. A sample complexity of $\mathcal{O}(\epsilon^{-3})$ was established under some mild conditions, and it was further improved to $\mathcal{O}(\epsilon^{-2})$ under a convexity assumption and a so-called over-parametrization assumption. 

In this paper, the authors propose a new policy gradient algorithm called TSIVR-PG for the policy optimization for a general utility function. They adopt a gradient truncation mechanism in TSIVR-PG to get rid of the uncheckable importance weights assumption which is frequently used in previous literatures. They establish convergence rate to stationary points, and global convergence results with additional assumptions. Moreover, they conduct experiments and compare with other previous methods.