An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods

Introduction

Policy gradient (PG) methods, or more generally direct policy search methods, have long been recognized as one of the foundations of reinforcement learning (RL) . Specifically, PG methods directly search for the optimal policy parameter that maximizes the long-term return in Markov decision processes (MDPs), following the policy gradient ascent direction . This search direction can be more efficient using a preconditioning matrix, e.g., using the natural PG direction . These methods have achieved tremendous empirical successes recently, especially boosted by the power of (deep) neural networks for policy parametrization . These successes are primarily attributed to the fact that PG methods naturally incorporate function approximation for policy parametrization, in order to handle massive and even continuous state-action spaces.

In practice, the policy gradients are usually estimated via samples using Monte-Carlo rollouts and bootstrapping . Such stochastic PG methods notoriously suffer from very high variances, which not only destabilize but also slow down the convergence. Several conventional approaches have been advocated to reduce the variance of PG methods, e.g., by adding a baseline , or by using function approximation for estimating the value function, namely, developing actor-critic algorithms . More recently, motivated by the advances of variance-reduction techniques in stochastic optimization , there have been surging interests in developing variance-reduced PG methods , which are shown to be faster.

In contrast to the empirical successes of PG methods, their theoretical convergence guarantees, especially non-asymptotic global convergence guarantees, have not been addressed satisfactorily until very recently . By non-asymptotic global convergence, here we mean the convergence behavior of PG methods from any initialization, and the quality of the point they converge to (usually enjoys global optimality up to some compatible function approximation error due to policy parametrization), after a finite number of iterations/samples. These recent prominent guarantees are normally beyond the folklore first-order stationary-point convergence That is, finding a parameter $\theta$ such that $\|\nabla J(\theta)\|^{2}\leq\varepsilon$, where $J$ is the expected return. , as expected from a stochastic nonconvex optimization perspective of solving RL with PG methods. Special landscapes of the RL objective, though nonconvex, have enabled the convergence to even globally optimal values. On the other hand, none of the aforementioned variance-reduced PG methods have been shown to enjoy these desired global convergence properties. It remains unclear whether these methods can converge to beyond first-order stationary policies.

Motivated by these advances and the questions that remain to be answered, we aim in this paper to improve the convergence of PG and natural PG (NPG) methods, and their variance-reduced variants, under general smooth policy parametrizations. Our contributions are summarized as follows.

Contributions. With a focus on the conventional Monte-Carlo-based PG methods, we propose a general framework for analyzing their global convergence. Our contribution is three-fold: first, we establish the global convergence up to compatible function approximation errors due to policy parametrization, for a variance-reduced PG method SRVR-PG ; second, we improve the global convergence of NPG methods established in , from $\mathcal{O}\left(\varepsilon^{-4}\right)$ to $\mathcal{O}\left(\varepsilon^{-3}\right)$; third, we propose a new variance-reduced algorithm based on NPG, and establish its global convergence with an efficient sample-complexity. These improvements are based on a framework that integrates the advantages of previous analyses on (variance reduced) PG and NPG, and rely on a (mild) assumption that the Fisher information matrix induced by the policy parametrization is positive definite (see Assumption 2.1). A comparison of previous results and our improvements is laid out in Table 1.

Global Convergence of (Natural) PG. Recently, there has been a surging research interest in investigating the global convergence of PG and NPG methods, which is beyond the folklore convergence to first-order stationary policies. In the special case with linear dynamics and quadratic reward, shows that PG methods with random search converge to the globally optimal policy with linear rates. In , with a simple reward-reshaping, PG methods have been shown to converge to the second-order stationary-point policies. shows that for finite-MDPs and several control tasks, the nonconvex RL objective has no suboptimal local minima. prove that (natural) PG methods converge to the globally optimal value when overparametrized neural networks are used for function approximation. provides a fairly general characterization of global convergence for these methods, and a basic sample complexity result for sample-based NPG updates. It is also worth noting that trust-region policy optimization (TRPO) , as a variant of NPG, also enjoys global convergence with overparametrized neural networks , and for regularized MDPs . Very recently, for actor-critic algorithms, a series of non-asymptotic convergence results have also been established , with global convergence guarantees when natural PG/PPO are used in the actor step.

Variance-Reduction (VR) for PG. Conventional approaches to reduce the high variance in PG methods include using (natural) actor-critic algorithms , and adding baselines . The idea of variance reduction (VR) is first proposed to accelerate stochastic minimization. VR algorithms such as SVRG , SAGA , SARAH , and Spider achieve acceleration over SGD in both convex and nonconvex settings. SVRG is also accelerated by applying a positive definite preconditioner that captures the curvature of the objective . Inspired by these successes in stochastic optimization, VR is also incorporated into PG methods , with empirical validations for acceleration, and analyzed rigorously in . Then, improves the sample complexity of SVRPG, and proposes a new SRVR-PG method that uses recursively updated semi-stochastic policy gradient, which leads to an improved sample complexity of $\mathcal{O}(\varepsilon^{-1.5})$ over previous works. More recently, proposes a new STORM-PG method, which blends momentum in the update and matches the sample complexity of in , and applies the idea of SARAH and considers a more general setting with regularization. Finally, heavy-ball type of momentum has also been applied to PG methods . We highlight that all these sample complexity results are for first-order stationary-point convergence (which might have arbitrarily bad performance: see (2.2)), in contrast to the more desired global convergence guarantees (up to some function approximation errors that can be small) that we are interested in.

Preliminaries

We first introduce some preliminaries regarding both the MDPs and policy gradient methods.

For notational convenience, let us denote $J(\pi_{\theta})$ by $J(\theta)$. Many of the previous works focus on establishing stationary convergence of policy gradient methods. That is, finding a $\theta$ that satisfies

Obviously, such a $\theta$ may not lead to a large $J(\theta)$. Instead, we are interested in finding a $\theta$ such that

where $J^{\star}=\max_{\pi}J(\pi)$, and the $\mathcal{O}(\sqrt{\varepsilon_{\text{bias}}})$ term reflects the inherent error related to the possibly limited expressive power of the policy parametrization $\pi_{\theta}$ (see Assumption 4.4 for the definition).

2 (Natural) Policy Gradient Methods

To solve the optimization problem (2.1), one standard way is via the policy gradient (PG) method . Specifically, let $\tau_{i}=\{s^{i}_{0},a^{i}_{0},s^{i}_{1},\cdots\}$ denote the data of a sampled trajectory under policy $\pi_{\theta}$. Then, a stochastic PG ascent update is given as

where $\eta>0$ is a stepsize, $N$ is the number of trajectories, and $g(\tau_{i}{\,|\,}\theta^{k})$ estimates $\nabla J(\theta^{k})$ using the trajectory $\tau_{i}$. Common unbiased estimators of PG include REINFORCE , using the policy gradient theorem , and GPOMDP . The commonly used GPOMDP estimator will be given by

where $\nabla_{\theta}\log\pi_{\theta}(a^{i}_{t}{\,|\,}s^{i}_{t})$ is the score function. If the expectation of this infinite sum exits, then (2.5) becomes an unbiased estimate of the policy gradient of the objective $J(\theta)$ defined in (2.1). This unbiasedness is established in App. B for completeness.

In practice, a truncated version of GPOMDP is used to approximate the infinite sum in (2.5), as

where $\tau_{i}^{H}=\{s^{i}_{0},a^{i}_{0},s^{i}_{1},\cdots,s^{i}_{H-1},a^{i}_{H-1},s^{i}_{H}\}$ is a truncation of the full trajectory $\tau_{i}$ of length $H$. (2.6) is thus a biased stochastic estimate of $\nabla J(\theta)$, with the bias being negligible for a large enough $H$. For notational simplicity, we denote the $H$-horizon trajectory distribution induced by the initial state distribution $\rho$ and policy $\pi_{\theta}$ as $p^{H}_{\rho}(\cdot{\,|\,}\theta)$, that is,

Hereafter, unless otherwise stated, we refer to this $H$-horizon trajectory simply as trajectory, drawn from $p^{H}_{\rho}(\cdot{\,|\,}\theta)$.

As a significant variant of PG, NPG also incorporates a preconditioning matrix $F_{\rho}(\theta)$, leading to the following update

The NPG update (2.7) can also be written as

where $L_{\nu^{\pi_{\theta}}_{\rho}}(w;\theta)$ is the compatible function approximation error defined by

Here, $\nu^{\pi_{\theta}}_{\rho}(s,a)=d^{\pi_{\theta}}_{\rho}(s)\pi(a{\,|\,}s)$ is the state-action visitation measure induced by $\pi_{\theta}$ and initial state distribution $\rho$, which can also be written as

For convenience, we will denote $\nu^{\pi_{\theta}}_{\rho}$ by $\nu^{\pi_{\theta}}$ hereafter. In other words, the NPG update direction $w^{k}$ is given by the minimizer of a stochastic optimization problem. In practice, one obtains an approximate NPG update direction $w^{k}$ by SGD (see Procedure 1).

Regarding the NPG update (2.8), we make the following standing assumption on the Fisher information matrix induced by $\pi_{\theta}$ and $\rho$.

For all $\theta\in\Rd$, the Fisher information matrix induced by policy $\pi_{\theta}$ and initial state distribution $\rho$ satisfies

Assumption 2.1 essentially states that $F_{\rho}(\theta)$ behaves well as a preconditioner in the NPG update (2.8). This is a common (and minimal) requirement for the convergence of preconditioned algorithms in both convex and nonconvex settings in the optimization realm, for example, the quasi-Newton algorithms , and their stochastic variants . In the RL realm, one common example of policy parametrizations that can satisfy this assumption is the Gaussian policy , where $\pi_{\theta}(\cdot{\,|\,}s)=\mathcal{N}(\mu_{\theta}(s),\Sigma)$ with mean parametrized linearly as $\mu_{\theta}(s)=\phi(s)^{\top}\theta$, where $\phi(s)$ denotes some feature matrix of proper dimensions, $\theta$ is the coefficient vector, and $\Sigma\succ 0$ is some fixed covariance matrix. In this case, the Fisher information matrix at each $s$ becomes $\phi(s)\Sigma^{-1}\phi(s)^{\top}$, independent of $\theta$, and is uniformly lower bounded (positive definite sense) if $\phi(s)$ is full-row-rank, namely, the features expanded by $\theta$ are linearly independent, which is a common requirement for linear function approximation settings . See App. B.2 for more detailed justifications, as well as discussions on more general policy parametrizations.

In the pioneering NPG work , $F(\theta)$ is directly assumed to be positive definite. So is in the follow-up works on natural actor-critic algorithms . In fact, this way, $F(\theta)$ will define a valid Riemannian metric on the parameter space, which has been used for interpreting the desired convergence properties of natural gradient methods . In a recent version of , a relevant assumption (specifically, Assumption 6.5, item 3) is made to establish the global convergence of NPG, in which it is assumed that $\lambda_{\textrm{min}}(F_{\rho}(\theta))$ is not too small compared with the Fisher information matrix induced by a fixed comparator policy. this can be implied by our Assumption 2.1. To sum up, the positive definiteness on the Fisher preconditioning matrix is common and not very restrictive.

In Sec. 4, we shall see that under Assumption 2.1, the stationary convergence of NPG can be analyzed, and NPG enjoys a better sample complexity of $\mathcal{O}(\varepsilon^{-3})$ in terms of its global convergence, compared with the existing sample complexity of $\mathcal{O}(\varepsilon^{-4})$ in . In addition, interestingly, PG and its variance-reduced version SRVR-PG also enjoy global convergence, although the Fisher information matrix does not appear explicitly in their updates.

Variance-Reduced Policy Gradient Methods

Recently, proposes an algorithm called Stochastic Recursive Variance Reduced Policy Gradient (SRVR-PG, see Algorithm 2), which applies variance-reduction on PG. It achieves a sample complexity of $\mathcal{O}(\varepsilon^{-1.5})$ to find an $\varepsilon-$stationary point, compared with the $\mathcal{O}(\varepsilon^{-2})$ sample complexity of stochastic PG. However, it remains unclear whether SRVR-PG converges globally. In this work, we provide an affirmative answer to this question by showing that SRVR-PG has a sample complexity of $\mathcal{O}(\varepsilon^{-3})$ to find an $\varepsilon-$optimal policy, up to some compatible function approximation error due to policy parametrization.

We also propose a new algorithm called SRVR-NPG to incorporate variance reduction into NPG, which is described in Algorithm 1. In Sec. 4, we provide a sample complexity for its global convergence, which is comparable to our improved NPG result.

In line 8 of Algorithm 1, $g_{w}(\tau^{H}_{j}|\theta^{j+1}_{t-1})$ is a weighted gradient estimator given by

where the importance weight factor $w_{0:h}(\tau^{H}_{j}|\theta^{j+1}_{t-1},\theta^{j+1}_{t})$ is defined by

This importance sampling makes $u^{j+1}_{t}$ an unbiased estimator of $\nabla J^{H}(\theta^{j+1}_{t})$.

In lines 4 and 8 of Algorithm 1, $w^{j+1}_{t}$ is produced by SRVR-NPG-SGD (see Procedure 2), which applies SGD Following , we apply SGD to make a fair comparison. One can also apply the SA algorithm and AC-SA algorithm . to solve the following subproblem:

where $\nu^{j+1}_{t}$ is the state-action visitation measure induced by $\pi_{\theta^{j+1}_{t}}$. The exact update direction given by (3.3) is $F^{-1}_{\rho}(\theta^{j+1}_{t})u^{j+1}_{t}$, and as in NPG, $F_{\rho}(\theta^{j+1}_{t})$ also serves as a preconditioner.

Theoretical Results

Before presenting the global convergence results, we first introduce some standard assumptions.

The truncated GPOMDP estimator $g(\tau^{H}{\,|\,}\theta)$ defined in (2.6) satisfies $\text{Var}\left(g(\tau^{H}{\,|\,}\theta)\right)\coloneqq\E[\|g(\tau^{H}{\,|\,}\theta)-\E[g(\tau^{H}{\,|\,}\theta)]\|^{2}]\leq\sigma^{2}$ for any $\theta$ and $\tau^{H}\sim p^{H}_{\rho}(\cdot{\,|\,}\theta)$.

$\|\nabla_{\theta}\log\pi_{\theta}(a{\,|\,}s)\|\leq G$ for any $\theta$ and $(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

$\|\nabla_{\theta}\log\pi_{\theta_{1}}(a{\,|\,}s)-\nabla_{\theta}\log\pi_{\theta_{2}}(a{\,|\,}s)\|\leq M\|\theta_{1}-\theta_{2}\|$ for any $\theta_{1},\theta_{2}$ and $(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

For the importance weight $w_{0:h}(\tau^{H}|\theta_{1},\theta_{2})$ (3.2), there exists $W>0$ such that

Assumptions 4.1, 4.2 and 4.3 are standard in the analysis of PG methods and their variance reduced variants . They can be verified for simple policy parametrizations such as Gaussian policies; see for more justifications.

Following the Assumption 6.5 of , we assume that the policy parametrization $\pi_{\theta}$ achieves a good function approximation, as measured by the transferred compatible function approximation error.

For any $\theta\in\Rd$, the transferred compatible function approximation error satisfies

$\varepsilon_{\text{bias}}$ reflects the error when approximating the advantage function from the score function, it measures the capacity of the parametrization $\pi_{\theta}$. When $\pi_{\theta}$ is the softmax parametrization, we have $\varepsilon_{\text{bias}}=0$ . When $\pi_{\theta}$ is a restricted parametrization, $\varepsilon_{\text{bias}}$ is often positive as $\pi_{\theta}$ may not contain all stochastic policies. For rich neural parametrizations, $\varepsilon_{\text{bias}}$ is very small .

Inspired by the global convergence analysis of NPG in , we present a general framework that relates the global convergence rates of these algorithms to i) their stationary convergence rate on $J(\theta)$, and ii) the difference between their update directions and exact NPG update directions.

Let $\{\theta^{k}\}_{k=1}^{K}$ be generated by a general update of the form

Furthermore, let $w^{k}_{\star}=F_{\rho}^{-1}(\theta^{k})\nabla J(\theta^{k})$ be the exact NPG update direction at $\theta^{k}$. Then, we have

where $\pi^{\star}$ is an optimal policy that maximizes $J(\pi)$.

The detailed proof of this global convergence framework can be found in J. To obtain a high level idea, one first starts from the $M-$smoothness of the score function to get

On the other hand, the renowned Performance Difference Lemma tells us that

The final result follows from a telescoping sum on $k=0,1,...,K-1$.

With Assumption 2.1, we can also show that the last term of (4.2) is small. Take stochastic PG as an example; then, we have $w^{k}=\frac{1}{N}\sum_{i=1}^{N}g(\tau^{H}_{i}|\theta^{k})$, and

When $H$ and $N$ are large enough, $w^{k}$ is a low-variance estimator of $\nabla J^{H}(\theta^{k})$, and $\nabla J^{H}(\theta^{k})$ is close to $\nabla J(\theta^{k})$, this makes the first term above small. The second term also goes to $0$ as $\theta^{k}$ approaches stationarity.

2 Global Convergence Results

By applying Proposition 4.5 on the PG, NPG, SRVR-PG, and SRVR-NPG updates and analyzing their stationary convergence, we obtain their global convergence rates. In the following, we only keep the dependences on $\sigma^{2}$ (the variance of the gradient estimator), $W$ (variance of importance weight), $\frac{1}{1-\gamma}$ (the effective horizon) and $\varepsilon$ (target accuracy). The specific choice of the parameters and sample complexities, as well as the proof, can be found in the appendix.

In the stochastic PG (2.4) with the truncated GPOMDP estimator (2.6), take $\eta=\frac{1}{4L_{J}}$, $K=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2}\varepsilon^{2}}\right)$, $N=\mathcal{O}\left(\frac{\sigma^{2}}{\varepsilon^{2}}\right)$, and $H=\mathcal{O}\left(\log(\frac{1}{(1-\gamma)\varepsilon})\right)$. Then, we have

In total, stochastic PG samples $\mathcal{O}\left(\frac{\sigma^{2}}{(1-\gamma)^{2}\varepsilon^{4}}\right)$ trajectories.

$L_{J}=\frac{MR}{(1-\gamma)^{2}}$ is the Lipschitz constant of $\nabla J$, see Lemma B.1 for details.

Theorem 4.6 improves the result of [1, Thm. 6.11] from (impractical) full gradients to sample-based stochastic gradients.

In the NPG update (2.8), let us apply $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\right)$ iterations of SGD as in Procedure 1 to obtain an update direction. In addition, take $\eta=\frac{\mu_{F}^{2}}{4G^{2}L_{J}}$ and $K=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2}\varepsilon}\right)$. Then,

In total, NPG samples $\mathcal{O}\left(\frac{1}{(1-\gamma)^{6}\varepsilon^{3}}\right)$ trajectories.

Compared with [1, Coro. 6.10], Theorem 4.9 improves the sample complexity of NPG by $\mathcal{O}(\varepsilon^{-1})$. This is because our stationary convergence analysis on NPG allows for a constant stepsize $\eta$, while [1, Coro. 6.10] applies a stepsize of $\eta=\mathcal{O}(1/\sqrt{K})$. It is worth noting that the $\mathcal{O}(\sqrt{\varepsilon_{\text{bias}}})$ term is the same as in , and we also apply the average SGD to solve the NPG subproblem (2.8).

In SRVR-PG (Algorithm 2), take $\eta=\frac{1}{8L_{J}}$, $S=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2.5}\varepsilon}\right)$, $m=\mathcal{O}\left(\frac{(1-\gamma)^{0.5}}{\varepsilon}\right)$, $B=\mathcal{O}\left(\frac{W}{(1-\gamma)^{0.5}\varepsilon}\right)$, $N=\mathcal{O}\left(\frac{\sigma^{2}}{\varepsilon}\right)$, and $H=\mathcal{O}\left(\log(\frac{1}{(1-\gamma)\varepsilon})\right)$. Then, we have

In total, SRVR-PG samples $\mathcal{O}\left(\frac{W+\sigma^{2}}{(1-\gamma)^{2.5}\varepsilon^{3}}\right)$ trajectories.

Theorem 4.11 establishes the global convergence of SRVR-PG proposed in , where only stationary convergence is shown. Also, compared with stochastic PG, SRVR-PG enjoys a better sample complexity thanks to its faster stationary convergence.

In SRVR-NPG (Algorithm 1), let us apply $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\right)$ iterations of SGD as in Procedure 2 to obtain an update direction. In addition, take $\eta=\frac{\mu_{F}}{16L_{J}}$, $S=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2.5}\varepsilon^{0.5}}\right)$, $m=\mathcal{O}\left(\frac{(1-\gamma)^{0.5}}{\varepsilon^{0.5}}\right)$, $B=\mathcal{O}\left(\frac{W}{(1-\gamma)^{0.5}\varepsilon^{1.5}}\right)$, $N=\mathcal{O}\left(\frac{\sigma^{2}}{\varepsilon^{2}}\right)$, and $H=\mathcal{O}\left(\log(\frac{1}{(1-\gamma)\varepsilon})\right)$. Then,

In total, SRVR-NPG samples $\mathcal{O}\left(\frac{W+\sigma^{2}}{(1-\gamma)^{2.5}\varepsilon^{2.5}}+\frac{1}{(1-\gamma)^{6}\varepsilon^{3}}\right)$ trajectories.

Compared with SRVR-PG, our SRVR-NPG has a better dependence on $W$ and $\sigma^{2}$, which could be large in practice (especially $W$). The current sample complexity of SRVR-NPG is not better than our (improved) result of NPG since, in our analysis, the advantage of variance reduction is offset by the cost of solving the subproblems.

Numerical Experiments

In this section, we compare the numerical performances of stochastic PG, NPG, SRVR-PG, and SRVR-NPG. Specifically, we test on benchmark reinforcement learning environments Cartpole and Mountain Car. Our implementation is based on the implementation of SRVPG https://github.com/Dam930/rllab and SRVR-PG https://github.com/xgfelicia/SRVRPG, and can be found in the supplementary material.

For both tasks, we apply a Gaussian policy of the form $\pi_{\theta}(a{\,|\,}s)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{(\mu_{\theta}(s)-a)^{2}}{2\sigma^{2}}\right)$ where the mean $\mu_{\theta}(s)$ is modeled by a neural network with Tanh as the activation function.

For the Cartpole problem, we apply a neural network of size $32\times 1$ and a horizon of $H=100$. In addition, each training algorithm uses $5000$ trajectories in total. For the Mountain Car problem, we apply a neural network of size $64\times 1$ and take $H=1000$. $3000$ trajectories are allowed for each algorithm. The numerical performance comparison, as well as the settings of algorithm-specific parameters, can be found in Figures 2 and 2. In App. O, we provide more implementation details.

Concluding Remarks

In this work, we have introduced a framework for analyzing the global convergence of (natural) PG methods and their variance-reduced variants, under the assumption that the Fisher information matrix is positive definite. We have established the sample complexity for the global convergence of stochastic PG and its variance-reduced variant SRVR-PG, and improved the sample complexity of NPG. In addition, we have introduced SRVR-NPG, which incorporates variance-reduction into NPG, and enjoys both global convergence guarantee and an efficient sample complexity. Our improved analysis hinges on exploiting the advantages of previous analyses on (variance reduced) PG and NPG methods, which may be of independent interest, and can be used to design faster variance-reduced NPG methods in the future.

Broader Impact

The results of this paper improves the performance of policy-gradient methods for reinforcement learning, as well as our understanding to the existing methods. Through reinforcement learning, our study will also benefit several research communities such as machine learning and robotics. We do not believe that the results in this work will cause any ethical issue, or put anyone at a disadvantage in our society.

Acknowledgements

Yanli Liu and Wotao Yin were partially supported by the Office of Naval Research (ONR) Grant N000141712162. Yanli Liu was also supported by UCLA Dissertation Year Fellowship. Kaiqing Zhang and Tamer Ba0sar were supported in part by the US Army Research Laboratory (ARL) Cooperative Agreement W911NF-17-2-0196, and in part by the Office of Naval Research (ONR) MURI Grant N00014-16-1-2710.

We would like to thank Rui Yuan for his suggestions to improve the proof of Lemma B.1 and Proposition G.1.

References

Appendix A Derivation of Previous Complexity Bounds

In this section, we briefly explain how to derive the sample complexities bounds in the first line of Table 1.

In the most recent version of , a complexity bound of $\mathcal{O}(\varepsilon^{-6})$ can be obtained the taking $N=\mathcal{O}(\varepsilon^{-4})$ and $N=\mathcal{O}(\varepsilon^{-2})$ in its Corollary 6.2. Note this complexity bound can be improved to $\mathcal{O}(\varepsilon^{-4})$ if a uniform upper bound for exact NPG update directions is applied. In this case, one can apply the convergence bound of SGD instead of Projected SGD for the NPG subproblem. In this paper, we establish an upper bound for $\|\nabla J(\theta)\|$ in Lemma B.1. Therefore the exact NPG update direction is also upper bounded thanks to Assumption 2.1.

For , the sample complexity bound of $\mathcal{O}(T_{TD}\varepsilon^{-2})$ is achieved by its Theorem 4.13. To be specific, one takes $T=\mathcal{O}(\varepsilon^{-2})$ and $T_{\text{TD}}=\mathcal{O}(m)$ number of temporal difference updates at each iteration. Here, $m$ is width of the neural network.

Note that in the proof of its Corollary 4.14, we can choose $m=\mathcal{O}(T^{4})$ (instead of $\mathcal{O}(T^{6})$) to have a convergence bound of the form $\mathcal{O}(\sqrt{\varepsilon_{0}})+\varepsilon$ (instead of $\mathcal{O}(\varepsilon)$), which is similar to our $\frac{\sqrt{\varepsilon_{\text{bias}}}}{1-\gamma}+\varepsilon$ convergence bound.

For , by the Corollary 4.10 therein, one needs to take $K=\mathcal{O}(\varepsilon^{-2})$ and $T=\mathcal{O}(K^{3})=\mathcal{O}(\varepsilon^{-6})$, which results in a total sample complexity of $\mathcal{O}(\varepsilon^{-8})$.

For , its Theorem 5 (item 1) gives a sample complexity of $\sum_{k=1}^{N}M_{k}=\mathcal{O}(\varepsilon^{-4})$, where we have applied $N=\mathcal{O}(\varepsilon^{-2})$ and $M_{k}=\mathcal{O}(\varepsilon^{-2})$.

Appendix B Helper Lemmas

In this section, we lay out several results that will be useful in later analyses and proofs.

First, for any $H>1$, we define the $H$-horizon truncated versions of the return $J(\theta)$ as

where the expectation is taken over the trajectories, starting from the state distribution $\rho$. Now we establish several properties of the GPOMDP policy gradient estimators and the return functions.

Recall the GPOMDP policy gradient estimate given in (2.5). The following properties hold:

If the infinite-sum in (2.5) is well defined, $g(\tau_{i}{\,|\,}\theta)$ in (2.5) is an unbiased estimate of the PG $\nabla J(\theta)$. Similarly, the truncated GPOMDP estimate $g(\tau_{i}^{H}{\,|\,}\theta)$ given by (2.6) is an unbiased estimate of the PG $\nabla J^{H}(\theta)$.

$J(\theta),J^{H}(\theta)$ are $L_{J}$-smooth, where $L_{J}=\frac{MR}{(1-\gamma)^{2}}+\frac{2G^{2}R}{(1-\gamma)^{3}}$. Furthermore, we have $\max\big\{\|\nabla{J}(\theta)\|,\|\nabla{J}^{H}(\theta)\|\big\}\leq\frac{GR}{(1-\gamma)^{2}}$.

We also have $\|\nabla J^{H}(\theta)-\nabla J(\theta)\|\leq GR\left(\frac{H+1}{1-\gamma}+\frac{\gamma}{(1-\gamma)^{2}}\right)\gamma^{H}$.

the unbiasedness of $g(\tau_{i}{\,|\,}\theta)$ follows directly from . A similar decomposition can also be done for its truncated version $g(\tau_{i}^{H}{\,|\,}\theta)$.

The second argument follows directly from the Proposition 4.2 in .

For the third argument, one can calculate that

This rest of the proof follows from the unbiasedness of $g(\tau_{i}|\theta)$ and $g(\tau_{i}^{H}|\theta)$ for estimating $\nabla J(\theta)$ and $\nabla J^{H}(\theta)$, respectively. ∎

B.2 On the Positive Definiteness of Fρ​(θ)F_{\rho}(\theta)

Now we remark that the positive definiteness on the Fisher information matrix induced by $\pi_{\theta}$, as stated in Assumption 2.1, is not restricted. Assumption 2.1 essentially states that $F(\theta)$ behaves well as a preconditioner in the NPG update (2.8). This is a common (and minimal) requirement for the convergence of preconditioned algorithms in both convex and nonconvex settings in the optimization realm .

For $\mu_{\theta}(s)$ being nonlinear functions of $\theta$, e.g., neural networks, the positive definiteness can still be satisfied, if the Jacobian of $\mu_{\theta}(s)$ at all $\theta$ uniformly satisfies the aforementioned conditions of $\phi(s)$ (the Jacobian in the linear case). In addition, beyond Gaussian policies, with the same conditions mentioned above on the feature $\phi(s)$ or the Jacobian of $\mu_{\theta}(s)$, Assumption 2.1 also holds more generally for any full-rank exponential family parametrization with mean parametrized by $\mu_{\theta}(s)$, as the Fisher information matrix, in this case, is also positive definite, in replace of the covariance matrix $\phi(s)\Sigma^{-1}\phi(s)$ in the Gaussian case .

Indeed, the Fisher information matrix is positive definite for any regular statistical model . In the pioneering NPG work , $F(\theta)$ is directly assumed to be positive definite. So is in the follow-up works on natural actor-critic algorithms . In fact, this way, $F_{\rho}(\theta)$ will define a valid Riemannian metric on the parameter space, which has been used for interpreting the desired convergence properties of natural gradient methods . In sum, the positive definiteness on the Fisher preconditioning matrix is common and not restrictive.

Appendix C SGD and Sampling Procedures

Similar to the Algorithm 1 of , we also apply the averaged SGD algorithm as in to solve the subproblems of NPG and SRVR-NPG.

For NPG, its subproblem (2.8) is of the form

Then, we can obtain a stochastic gradient at $w_{t}$ by

where $(s,a)\sim\nu^{\pi_{\theta^{k}}}$, and $\widehat{A}^{\pi_{\theta^{k}}}(s,a)$ is an unbiased estimate of $A^{\pi_{\theta^{k}}}(s,a)$. We will describe how to obtain $(s,a)\sim\nu^{\pi_{\theta^{k}}}$ and $\widehat{A}^{\pi_{\theta^{k}}}(s,a)$ in App. C.2.

Following Corollary 6.10 of , we can verify that $\widetilde{\nabla}l(w_{t})$ is an unbiased estimate of $\nabla{l}(w_{t})$.

For SRVR-NPG, its subproblem (3.3) is of the form

Then, a stochastic gradient $\widetilde{\nabla}l(w_{t})$ is given by

where $(s,a)\sim\nu^{\pi_{\theta^{j+1}_{t}}}$ is obtained in a similar way as above. It is straightforward to verify that $\widetilde{\nabla}l(w_{t})$ is an unbiased estimate of $\nabla{l}(w_{t})$.

C.2 Sampling Procedures

Sampling $(s,a)\sim\nu^{\pi_{\theta^{k}}}$ and Obtaining $\widehat{A}^{\pi_{\theta^{k}}}(s,a)$ can be done in a standard way, for example, by apply Algorithm 3 of . Both of them needs to sample $\frac{1}{1-\gamma}$ state-action pairs in expectation.

Appendix D SRVR-PG Algorithm

The Stochastic Recursive Variance-Reduced PG (SRVR-PG) algorithm is introduced in , where a recursively updated semi-stochastic gradient $u^{j+1}_{t}$ is applied as an update direction.

Here, the gradient estimators $g$ and $g_{w}$ are defined in (2.6) and (3.1), respectively.

Appendix E Stationary Convergence

In this section, we proceed to establish the stationary convergence of stochastic PG, NPG, SRVR-PG, and SRVR-NPG from an optimization perspective.

The stationary convergence of stochastic PG follows from the analysis of SGD. For SRVR-PG, we adapt its analysis in .

For NPG and SRVR-NPG, the Fisher information matrix $F(\theta)$ is applied as a preconditioner on top of PG and SRVR-PG, respectively. Regarding $F(\theta)$, we know from Assumptions 2.1 and 4.2 that

Since $\mu_{F}>0$, we know that $F(\theta)$ defines a nice metric around $\theta$. Consequently, with the analysis of gradient methods in nonconvex optimization, one can show that NPG (SRVR-NPG) has a similar iteration complexity compared with PG (SRVR-PG), although at each iteration, a subproblem needs to be solved in order to obtain an approximate preconditioned update direction.

We next present the stationary convergence results, and prove them in the subsequent sections. These results are established for $J^{H}(\theta)$ or $J(\theta)$, and we will apply the intermediate results in their proof to establish the global convergence on $J(\theta)$ (up to function approximation errors due to policy parametrizations).

In the stochastic PG update (2.4), by choosing $\eta=\frac{1}{4L_{J}}$, $K=\frac{32L_{J}(J^{H,\star}-J^{H}(\theta_{0}))}{\varepsilon},$ and $N=\frac{6\sigma^{2}}{\varepsilon}$, we have

In total, stochastic PG samples $\mathcal{O}\left(\frac{\sigma^{2}}{(1-\gamma)^{2}\varepsilon^{2}}\right)$ trajectories.

In the NPG update (2.8), let us apply $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon}\right)$ iterations of SGD as in Procedure 1 to obtain an update direction $w^{k}$. In addition, let us take $\eta=\frac{\mu_{F}^{2}}{4G^{2}L_{J}}$ and $K=\frac{32L_{J}G^{4}(J^{\star}-J(\theta_{0})}{\mu_{F}^{2}\varepsilon}$. Then, we have

In total, NPG samples $\mathcal{O}\left(\frac{1}{(1-\gamma)^{6}\varepsilon^{2}}\right)$ trajectories.

(Theorem 4.5 of ) In SRVR-PG (Algorithm 2), take $\eta=\frac{1}{4L_{J}}$, $N=\frac{12\sigma^{2}}{\varepsilon}$, $S=\frac{64MR(J^{\star}-J(\theta^{0}))}{(1-\gamma)^{2.5}\varepsilon^{0.5}}$, $m=\frac{(1-\gamma)^{0.5}}{\varepsilon^{0.5}}$, and $B=\frac{72\eta G^{2}(2G^{2}+M)(W+1)\gamma}{M(1-\gamma)^{3}}m$. Then, we have

In total, SRVR-PG samples $\mathcal{O}\left(\frac{W+\sigma^{2}}{(1-\gamma)^{2.5}\varepsilon^{1.5}}\right)$ trajectories.

In SRVR-NPG (Algorithm 1), take $\eta=\frac{\mu_{F}}{8L_{J}}$, $S=\frac{24G^{2}(J^{H,\star}-J^{H}(\theta_{0}))}{\eta\varepsilon^{0.5}}$, $m=\frac{1}{\varepsilon^{0.5}}$, $B=\left(\frac{\eta}{\mu_{F}}+\frac{\eta}{4G^{2}}\right)\frac{72RG^{2}(2G^{2}+M)(W+1)\gamma}{(1-\gamma)^{5}}\frac{1}{L_{J}\varepsilon^{0.75}}$, and $N=3\left(\frac{8G^{2}}{\mu_{F}}+2\right)\frac{\sigma^{2}}{\varepsilon}.$ In addition, assume that $\varepsilon$ is small enough such that

Let us also apply $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon}\right)$ iterations of SGD as in Procedure 2 to obtain an update direction $w^{j+1}_{t}$. Then, in order to have

SRVR-NPG samples $\mathcal{O}\left(\frac{\sigma^{2}}{(1-\gamma)^{2}\varepsilon^{1.5}}+\frac{W}{(1-\gamma)^{3}\varepsilon^{1.75}}+\frac{1}{(1-\gamma)^{6}\varepsilon^{2}}\right)$ trajectories.

Appendix F Proof of Theorem E.1

Let $g^{k}=\frac{1}{N}\sum_{i=1}^{N}g(\tau^{H}_{i}|\theta^{k})$. Then, we have

where we have applied Lemma B.1 in the first inequality, and Cauchy-Schwartz in the second inequality.

Taking expectation on both sides and applying Lemma B.1 and Assumption 4.1 yields

Let us further telescope from $k=0$ to $K-1$ to obtain

Taking $\eta=\frac{1}{4L_{J}}$, $K=\frac{32L_{J}(J^{\star}-J^{H}(\theta_{0}))}{\varepsilon},$ and $N=\frac{6\sigma^{2}}{\varepsilon}$ gives

Finally, by applying $L_{J}=\frac{MR}{(1-\gamma)^{2}}+\frac{2G^{2}R}{(1-\gamma)^{3}}$, we know that PG needs to sample $KN=\mathcal{O}\left(\frac{\sigma^{2}}{(1-\gamma)^{2}\varepsilon^{2}}\right)$ trajectories. ∎

Appendix G Proof of Theorem E.2

Before proving Theorem E.2, let us first establish the sample complexity of SGD when applied to obtain an approximate NPG update direction $w^{k}$.

In Procedure 1, take $\alpha=\frac{1}{4G^{2}}$ and let the objective be

Let $w^{k}_{\star}$ be the minimizer of $l(w)$. Then, in order to achieve

where $l^{\star}$ is the minimum of $l(w)$, and $\xi$ is defined such that

where $g_{\star}$ is a stochastic gradient of $l(w)$ at $w_{\star}$.

Following the proof of Corollary 6.10 of (arXiv V2 version), we obtain an upper bound of $\xi$ as follows.

where $s,a\sim\nu^{\pi_{\theta}}$ and $a^{\prime}\sim\nu^{\pi_{\theta}}(\cdot|s)$. Therefore, we can stipulate that

From Lemma B.1 and Assumption 2.1 we have

Since each stochastic gradient of SGD has a cost of $\frac{2}{1-\gamma}$ (see App. C), this means to sample $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{\prime}}\right)$ trajectories. ∎

We apply SGD to obtain a $w^{k}$ such that

By Proposition G.1, we need to sample $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon}\right)$ trajectories.

where $\theta^{k+1}_{\star}=\theta^{k}+\eta F^{-1}(\theta^{k})\nabla J(\theta^{k})$.

where we have applied Cauchy-Schwartz in the first and second inequalities, and $\theta^{k+1}_{\star}=\theta^{k}+\eta F^{-1}(\theta^{k})\nabla J(\theta^{k})$ in the last step.

Taking full expectation on both sides yields

where we have applied (G.2) in the second inequality.

Telescoping the above inequality from $k=0$ to $k=K-1$ gives

Finally, by taking $\eta=\frac{\mu_{F}^{2}}{4G^{2}L_{J}}$ and $K=\frac{32L_{J}G^{4}(J^{\star}-J(\theta_{0})}{\mu_{F}^{2}\varepsilon}=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2}\varepsilon}\right)$, we arrive at

Recall that at each iteration of NPG, we apply SGD as in Procedure 1 to reach (G.1). By Proposition G.1, we know that in total, NPG requires to sample

Appendix H Proof of Theorem E.3

By Theorem 4.5 of , we know that if $\eta=\frac{1}{4L_{J}}$ and

Therefore, taking $N=\frac{12\sigma^{2}}{\varepsilon}$ and $Sm=\frac{64MR(J^{\star}-J^{H}(\theta^{0}))}{(1-\gamma)^{2}\varepsilon}$ yields

Let us take $S=\frac{64MR(J^{\star}-J^{H}(\theta^{0}))}{(1-\gamma)^{2.5}\varepsilon^{0.5}}$ and $m=\frac{(1-\gamma)^{0.5}}{\varepsilon^{0.5}}$. Then, the number of trajectories required by SRVR-PG is

Therefore, SRVR-PG needs to sample $\mathcal{O}\left(\frac{W+\sigma^{2}}{(1-\gamma)^{2.5}\varepsilon^{1.5}}\right)$ trajectories. ∎

Appendix I Proof of Theorem E.4

In order to prove Theorem E.4, we need the following technical results.

This lemma is adapted from the Equation B.10 of , where SRVR-PG is analyzed. It is also true for our SRVR-NPG since the update rule of $u^{j+1}_{t}$ is the same for both algorithms. ∎

In SRVR-NPG, apply SGD as in Procedure 2 to solve the subproblems. Take $\alpha=\frac{1}{4G^{2}}$ and let the objective be

Let $w^{j+1}_{t,\star}=F^{-1}(\theta^{j+1}_{t})\nabla J^{H}(\theta^{j+1}_{t})$ be the minimizer of $l(w)$. Assume in addition that

for each $s=0,1,...,S-1$ and $t=0,1,...,m-1$, Procedure 2 requires sampling

Recall that we are applying SGD as in Procedure 2 to solve the SRVR-NPG subproblem (3.3).

Recall from (C.4) that a stochastic gradient $\nabla l(w_{t})$ is given by

where $l^{\star}$ is the minimum of $l(w)$, and $\xi$ is defined such that the stochastic gradient $g_{\star}$ at the solution $w^{j+1}_{0,\star}$ satisfies

Similar as Proposition G.1, we know that $\xi$ can be chosen by

As a result, the number of iterations, $T$, should be

Since each stochastic gradient of $l(w)$ only needs to sample a state-action pair, this is equivalent to sampling $\mathcal{O}\left(\frac{1}{(1-\gamma)^{3}\varepsilon^{\prime}}\right)$ trajectories.

Now, let us turn to $t\geq 1$. $u^{j+1}_{t}$ is an unbiased estimate of $\nabla J(\theta^{j+1}_{t})$, and its variance is bounded as in Lemma I.1. Therefore,

Now, we are ready to prove the desired results by induction.

Assume that for all $t^{\prime}<t$, we have

Similar to the case of $t=0$, we know that this yields

iterations of SGD as in Procedure 2 so that

Since each stochastic gradient of $l(w)$ has a cost of $\frac{1}{1-\gamma}$ (see App. C), this is equivalent to sample

And we want to apply SGD as in Procedure 2 to obtain a $w^{j+1}_{t}$ that satisfies

Recall that the parameters $S,m,B$ and $N$ are chosen as

the requirements of Proposition I.2 are satisfied:

By applying Proposition I.2, we know that in order to have (I.2), one needs to sample

where $\theta^{j+1}_{t+1,\star}=\theta^{j+1}_{t}+\eta F^{-1}(\theta^{j+1}_{t})u^{j+1}_{t}$.

where we have applied Lemma B.1 in the first inequality, and Cauchy-Schwartz in the second one.

Applying $F^{-1}(\theta)\succeq\frac{1}{G^{2}}I$ on the first inner product, and Cauchy-Schwartz on the second inner product term leads to

Applying $\|\nabla J^{H}(\theta^{j+1}_{t})\|^{2}\leq 2\|\nabla J^{H}(\theta^{j+1}_{t})-u^{j+1}_{t}\|^{2}+2\|u^{j+1}_{t}\|^{2}$ and $F(\theta^{j+1}_{t})\succeq\mu_{F}I_{d}$ yields

Telescoping for $s=0,1,...,S-1$ and $t=0,1,...,m-1$ and dividing by $Sm$ gives

Let us first show that the first term on the left hand side of (I.5) is non-negative. In fact, from $\eta=\frac{\mu_{F}}{8L_{J}}$ and $B=\left(\frac{\eta}{\mu_{F}}+\frac{\eta}{4G^{2}}\right)\frac{4C_{\gamma}m}{L_{J}\varepsilon^{0.25}}$ we have

we can set all the three terms on the right hand side of (I.5) to be $\frac{\varepsilon}{3}$, which gives

where the last requirement is satisfied according to (I.3).

For the parameters $S,m,B$, and $N$, we have

where we have applied the definition of $C_{\gamma}$ in Lemma I.1 in the third equality.

Therefore in total, the number of trajectories required by SRVR-NPG to reach $\varepsilon-$stationarity is

Appendix J Proof of Proposition 4.5

In this section, we proceed to prove Proposition 4.5, which establishes a general global convergence result on policy gradient methods of the form $\theta^{k+1}=\theta^{k}+\eta w^{k}$.

First, by the $M-$smoothness of score function (see Assumption 4.2), we know that

On the other hand, by the performance difference lemma we know that

Now, let us apply Jensen’s inequality and Assumption 4.2 to obtain

Combining this with Assumption 4.4 yields

Finally, let us telescope the above inequality from $k=0$ to $K-1$, and divide by $K$, which gives

On the right hand side of (J.2), the first term reflects the function approximation error due to the possibly imperfect policy parametrization. The second term vanishes as $K\rightarrow\infty$.

By looking at the third and fourth term, we know that for an update of the form $\theta^{k+1}=\theta^{k}+\eta w^{k}$, its global convergence rate depends crucially on i) the difference between its update directions $w^{k}$ and the exact NPG update direction $w^{k}_{\star}$, and ii) its stationary convergence rate.

In the rest of this paper, we shall see that for stochastic PG, NPG, SRVR-PG, and SRVR-NPG, both the third and fourth terms of (J.2) go to $0$ as $K\rightarrow\infty$, whose speed lead to different global convergence rates for different algorithms. In order to achieve this, we will apply some intermediate results in the previous proof of stationary convergence.

Appendix K Proof of Theorem 4.6

Bounding $\frac{1}{K}\sum_{k=0}^{K-1}\|w^{k}-w^{k}_{\star}\|$.

we have from Lemma B.1 and Assumption 4.1 that

Furthermore, Assumption 2.1 tells us that

Combining (K.2) and (K.3) with (K.1) gives

Let us take $\eta=\frac{1}{4L_{J}}$. In addition, let $H$, $N$, and $K$ satisfy

Bounding $\frac{1}{K}\sum_{k=0}^{K-1}\|w^{k}\|^{2}$.

In summary, we require $N$ and $K$ to satisfy (K.5), (K.7), and (K.9), which leads to

By combining (K.6), (K.8), (K.10) and (J.2), we can conclude that

In total, stochastic PG requires to sample $KN=\mathcal{O}\left(\frac{\sigma^{2}}{(1-\gamma)^{2}\varepsilon^{4}}\right)$ trajectories.

Appendix L Proof of Theorem 4.9

Let us take $\eta=\frac{\mu_{F}^{2}}{4G^{2}L_{J}}$ and apply SGD as in Procedure 1 to obtain a $w^{k}$ that satisfies

From Proposition G.1, we know that this requires sampling $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\right)$ trajectories at each iteration.

Bounding $\frac{1}{K}\sum_{k=0}^{K-1}\|w^{k}-w^{k}_{\star}\|$.

Recall that the update direction $w^{k}\approx w^{k}_{\star}=F^{-1}(\theta^{k})\nabla J(\theta^{k})$ is obtained by solving the subproblem

By (L.1) and Jensen’s inequality, we can write

On the other hand, by replacing (G.1) with (L.1), the stationary convergence of NPG stated in (G.3) becomes

Bounding $\frac{1}{K}\sum_{k=0}^{K-1}\|w^{k}\|^{2}$.

Taking $\eta=\frac{\mu_{F}^{2}}{4G^{2}L_{J}}$ and

In summary, we require $K$ to satisfy (L.3) and (L.5), which leads to

By combining (L.2), (L.4), (L.6) and (J.2), we can conclude that

Since at each iteration, SGD needs to sample $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\right)$ trajectories so that (L.1) is satisfied, NPG requires to sample $\mathcal{O}\left(\frac{1}{(1-\gamma)^{6}\varepsilon^{3}}\right)$ trajectories in total.

Appendix M Proof of Theorem 4.11

Bounding $\frac{1}{Sm}\sum_{s=0}^{S-1}\sum_{t=0}^{m-1}\|w^{j+1}_{t}-w^{j+1}_{t,\star}\|$.

Since $w^{j+1}_{t}=u^{j+1}_{t}$ and $w^{j+1}_{t,\star}=F^{-1}(\theta^{j+1}_{t})\nabla J(\theta^{j+1}_{t})$, we have from Lemmas I.1 and B.1 that

where we have applied Lemma B.1 and Assumption 2.1 in the second inequality, and Lemma I.1 in the third one.

Telescoping this over $s=0,1,..,S-1$, $t=0,1,m-1$ and dividing by $Sm$ gives

On the other hand, from Equation (B.14) of we know that

By the definition of $C_{\gamma}$ in Lemma I.1, we have

Since $\eta=\frac{1}{8L_{J}}$, we further have

Putting these inequalities back into (M.1) yields

Bounding $\frac{1}{Sm}\sum_{s=0}^{S-1}\sum_{t=0}^{m-1}\|w^{j+1}_{t}\|^{2}$

By setting $\eta=\frac{1}{8L_{J}}$ and applying (M.3) and (M.4), we further have

By combining (M.6), (M.8), (M.10) and (J.2), we can conclude that

To achieve this, we require $Sm$ and $N$ to satisfy (M.5), (M.7), and (M.9), which leads to

By (M.3), we know that $B=\mathcal{O}(W(1-\gamma)^{-1}m)$.

Therefore, by taking $S=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2.5}\varepsilon}\right)$ and $m=\mathcal{O}\left(\frac{1}{(1-\gamma)^{-0.5}\varepsilon}\right)$, the sample complexity of SRVR-PG is

Appendix N Proof of Theorem 4.13

Let us take $\eta=\frac{\mu_{F}}{16L_{J}}$ and apply SGD as in Procedure 2 to obtain a $w^{j+1}_{t}$ that satisfies

In order to apply Proposition I.2, let assume the following so that its assumptions are satisfied:

At the end of this proof, we will see that these assumptions are indeed satisfied for small $\varepsilon$.

From Proposition I.2, we know that this requires sampling $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\right)$ trajectories at each iteration.

Bounding $\frac{1}{Sm}\sum_{s=0}^{S-1}\sum_{t=0}^{m-1}\|w^{j+1}_{t}-w^{j+1}_{t,\star}\|$.

where we have applied Assumption 2.1 in the second inequality, and Lemmas I.1 and B.1 in the third one.

Telescoping this over $s=0,1,..,S-1$, $t=0,1,m-1$ and dividing by $Sm$ gives

On the other hand, from (I.5) we know that

Since $\eta=\frac{\mu_{F}}{16L_{J}}$, (N.4) becomes

Putting these inequalities back into (N.3) and applying (N.1) yields

where we have applied (N.1) in the first equality.

Bounding $\frac{1}{Sm}\sum_{s=0}^{S-1}\sum_{t=0}^{m-1}\|w^{j+1}_{t}\|^{2}$.

where we have applied (N.6) in the first inequality, and (N.1) in the last step.

By combining (N.8), (N.10), (N.12) and (J.2), we can conclude that

To achieve this, we require $Sm$, $B$, and $N$ to satisfy (N.5), (N.7), (N.9), and (N.11), which leads to

By Proposition I.2, we know that in order to achieve (N.1), SGD requires sampling $\mathcal{O}\left(\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\right)$ trajectories per iteration.

Therefore, by taking $S=\mathcal{O}\left(\frac{1}{(1-\gamma)^{2.5}\varepsilon^{0.5}}\right)$ and $m=\mathcal{O}\left(\frac{(1-\gamma)^{0.5}}{{\varepsilon}^{0.5}}\right)$, the amount of trajectories required by SRVR-NPG is

It is straightforward to verify that the requirements listed in (N.2) are also satisfied as long as $\varepsilon$ is small enough.

Appendix O Implementation Details

In this section, we provide additional details on the implementation of PG, NPG, SRVR-PG and SRVR-NPG.

For NPG, we use the default implementation provided by rllab https://github.com/rll/rllab, which actually implements the trust region policy optimization(TRPO) algorithm . For cartplole, we sample 200 trajectories at each iteration to solve the subproblem of TRPO. For mountain car, we sample 120 trajectories at each iteration.

We found that the naive implementation of PG and SRVR-PG typically do not work for our tests. For example, PG and SRVR-PG often give an average reward around $-90$ for the mountain-car test, despite of our best efforts.

As in and , we found that it is necessary to apply Adagrad or Adam type of averaging to improve their performances.

In our experiments, we apply Adagrad type of averaging for PG and SRVR-PG, which results in much better performances. As for SRVR-NPG, we apply Adam type of averaging, which gives an approximation of the Fisher information matrix at each iteration (see section 11.2 of ). We leave the implementation of a better approximation of the Fisher information matrix to the future work.