# Convergence and Optimality of Policy Gradient Methods in Weakly Smooth
Settings

Matthew S. Zhang  Department of Computer Science at the University of Toronto,
and Vector Institute<EMAIL_ADDRESS>Murat A. Erdogdu
Department of Computer Science and Department of Statistical Sciences at the
University of Toronto, and Vector Institute<EMAIL_ADDRESS>Animesh
Garg  Department of Computer Science at the University of Toronto, and Vector
Institute<EMAIL_ADDRESS>
###### Abstract

Policy gradient methods have been frequently applied to problems in control
and reinforcement learning with great success, yet existing convergence
analysis still relies on non-intuitive, impractical and often opaque
conditions. In particular, existing rates are achieved in limited settings,
under strict regularity conditions. In this work, we establish explicit
convergence rates of policy gradient methods, extending the convergence regime
to weakly smooth policy classes with $L_{2}$ integrable gradient. We provide
intuitive examples to illustrate the insight behind these new conditions.
Notably, our analysis also shows that convergence rates are achievable for
both the standard policy gradient and the natural policy gradient algorithms
under these assumptions. Lastly we provide performance guarantees for the
converged policies.

##  1 Introduction

Modern Reinforcement Learning (RL) has solved challenges in diverse fields
such as finance, healthcare, and robotics [Den+16, YLN19, KBP13]. Nonetheless,
the theory behind these methods remains poorly understood, with convergence
results being limited to narrow classes of problems. Classical approaches to
RL theory focus on tabular problems where discrete techniques can be applied
(see [Aga+20, Sid+18]). However, most practical problems exist in continuous,
high-dimensional domains [Doy00], and may even be infinite-dimensional or non-
compact.

Theoretical results in continuous domains do not effectively characterize
practical algorithms. Value-based estimators have obtained strong results in
some regimes such as linear MDPs, both in on- and off-line settings [Cai+19,
YW19]. In contrast to value-based methods, direct policy estimators possess
numerous advantages, in that they are theoretically insensitive to
perturbations in the problem parameters, and typically satisfy better
smoothness assumptions. Nonetheless, bounds for direct parameterizations of
the policy have been less successful. They either restrict the cardinality or
size of the space [Aga+20], or apply strong assumptions on the policy and MDP
[Liu+19, XWL20, Liu+20]. This conflicts with practical results, where
convergence often occurs without boundedness or smoothness preconditions on
the function approximator.

Consequently, in this paper, we analyse two key questions: (i) how can we
relax existing conditions on MDPs while retaining guarantees for convergence,
(ii) how can we bound the performance of the policies under these conditions.
Arguably, the convergence of gradient algorithms needs to rely on some
constraints of the function class. Prior work has relied on assumptions of (a)
smoothness and (b) absolute boundedness of the gradient. However, these
conditions are overly restrictive and exclude many useful function
approximators.

Summary of Contributions. We make contributions with respect to each of these
assumptions: (a) strong smoothness is relaxed to weak smoothness (Hölder
conditions); (b) absolute boundedness of the gradient is relaxed to $L_{2}$
integrability under the visitation distribution. While this is an important
theoretical development, it also expands the scope of practical convergence
results. We include many practical examples of MDPs and policies that satisfy
our criteria, with applications to exploration and safety in reinforcement
learning. To the best of our knowledge, ours is the first study to consider
this setting.

Under these assumptions, we find (Corollary 1) that with an appropriate
learning rate, the gradients satisfy
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t-1})\right\rVert^{2}\right]\leq\epsilon$ for both the standard and
natural policy gradient for large enough $T,B$, where $T$ is the number of
iterations and $B$ is the batch size. We also show (Corollary 2) that natural
policy gradient satisfies the following bound:

$\displaystyle\min_{t=0,1,\ldots{T-1}}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t})\right]\leq\epsilon+\mathcal{O}\left(\frac{\sqrt{E_{\Pi}}}{1-\gamma}\right),$
(1)

for large enough $T,B$, where $E_{\Pi}$ can be tuned by choosing an
appropriately regular policy class and $\theta_{*}$ is the maximizer of $J$.
$E_{\Pi}$ is formally defined in §5. Under a strong additional assumption,
standard policy gradient also satisfies
$\min_{t=0,1\ldots{T-1}}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t})\right]\leq\epsilon$
for large enough $T,B$. In the strictly smooth limit these results have
previously been discovered [Aga+20a, XWL20, ZXL19], although our results hold
for a wider range of functions and MDPs.

The remainder of the paper is structured as follows: in §2 we cover the
mathematical formulation of MDPs; in §3 we introduce the policy gradient
algorithm as well as our assumptions. In §4, we list several candidate
policies that satisfy our assumptions, and demonstrate their utility in a
variety of contexts. §5 then states our main results; §6 summarizes works
related to optimization and RL theory.

##  2 Background

###  2.1 Markov Decision Processes

Let a state-space be denoted by $\mathcal{S}$, and an action-space by
$\mathcal{A}$. Let a transition measure $P(\cdot|s,a)$ and a reward measure
$R(\cdot|s,a)$ be probability measures on $\mathcal{S}$ and $\mathbb{R}$
respectively, both conditioned on variables
$(s,a)\in\mathcal{S}\times\mathcal{A}$. A Markov Decision Process
$\mathcal{M}$ is formally defined as a tuple
$(\mathcal{S},\mathcal{A},P,R,\gamma)$, where $\gamma\in[0,1)$ is the discount
factor. By abuse of notation, we use the same notation for a measure and its
density, unless otherwise specified. Let $\left\lVert
z\right\rVert=\left\lVert z\right\rVert_{2}$ the $2$-norm for vectors,
$\left\lVert z\right\rVert_{op}$ the operator norm for matrices, and
$\left\lVert p-q\right\rVert_{TV}\triangleq\int\left|p(x)-q(x)\right|dx$ the
total variation distance for signed measures. Hereafter we assume that the
absolute magnitude of the rewards are bounded, i.e. $R(\cdot|s,a)$ only has
support on $[-\alpha,\alpha]$ for some $\alpha\geq 0$, and all $s,a$.

Policies: For a given state $s\in\mathcal{S}$, we denote a stochastic policy
with $\pi(\cdot|s)$, which is a probability distribution over $\mathcal{A}$.

Trajectories: To generate trajectories, we start from an initial state
distribution $\rho$, and then at each time $t\in\mathbb{N}$, we sample an
action from the policy: $a_{t}\sim\pi(\cdot|s_{t})$. Subsequently a state and
reward are queried as $s_{t+1}\sim P(\cdot|a_{t},s_{t}),r_{t}\sim
R(\cdot|a_{t},s_{t})$, and the process continues indefinitely. Consequently
$\pi,\rho,\mathcal{M}$ together parameterize a probability distribution on the
set of trajectories. Letting $\rho$ be fixed, we write this as
$\\{(s_{t},a_{t}),t=0,1,2,\ldots\\}\sim\text{MDP}$ following $\pi$.

Value Functions: We can define the value function as: $V_{\pi}(s)\triangleq$
$\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0}=s],$ and the Q-function
as:
$Q_{\pi}(s,a)\triangleq\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0}=s,a_{0}=a]$.
Note that both expectations are taken over trajectories following the policy
$\pi$. If $\left|r_{t}\right|\leq\alpha$ almost surely, both functions are
bounded by $[-\alpha/(1-\gamma),\alpha/(1-\gamma)]$ almost surely as well. We
can also define the advantage function $A_{\pi}(s,a)\triangleq
Q_{\pi}(s,a)-V_{\pi}(s).$

Discounted Visitation:It will be useful to define the sum of time-discounted
visitation probability densities through the following:
$d_{\pi}^{s}(s,a)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}p_{t}(s,a|s_{0}=s)$
where $p_{t}(\cdot|s_{0}=s)$ is the conditional probability density of $s,a$
being sampled at time $t$ from the MDP following $\pi$, given the initial
state $s_{0}=s$. We overload notation and write $d_{\pi}^{\rho}(s,a)=\int
d_{\pi}^{s^{\prime}}(s,a)\rho(s^{\prime})\,ds^{\prime}.$ This defines a
probability density function on $\mathcal{S}\times\mathcal{A}$. We also write
$H_{\theta}^{\rho}(s)=\int d_{\theta}^{\rho}(s,a)\,da$ for the state-component
of the visitation distribution.

Reinforcement Learning A reinforcement learning agent is one which produces a
sequence of policies $\pi_{t}$ based on the queried states $s_{t},r_{t}$,
which seeks to iteratively maximize the value function: $J(\pi)=\int
V_{\pi}(s)\rho(s)\,ds$. The existence of an optimum in the space of stochastic
functions has been shown as a classical result [Bel54].

##  3 Algorithms

###  3.1 Policy Class

In this work, we limit our discussion to exponential policy classes which are
continuously differentiable. In particular, we denote the distribution of an
exponential policy, parameterized by a variable
$\theta\in\Theta\subseteq\mathbb{R}^{N}$, such that
$\pi_{\nu_{\theta}}(a|s)=\frac{\exp(\nu_{\theta}(s,a))}{\int_{\mathcal{A}}\exp(\nu_{\theta}(s,a))\,da}$
where $\nu_{\theta}:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}$. We require
that the integral $\int_{\mathcal{A}}\exp(\nu_{\theta}(s,a))\,da<\infty$ is
finite for all $\theta\in\Theta,s\in\mathcal{S}$, and that $\nu_{\theta}(s,a)$
is differentiable in $\theta$ for all $s,a$. Let us define
$\pi_{\theta}\triangleq\pi_{\nu_{\theta}}$, $J(\theta)\triangleq
J(\pi_{\theta})$ and use $\theta$ instead of $\pi_{\theta}$ in subscripts
where there is no confusion. Let us denote the score function as
$\psi_{\theta}(s,a)=\nabla_{\theta}\log\pi_{\theta}(a|s)$. Then the gradient
can be written as $\nabla J(\theta)=\mathbb{E}_{s,a\sim
d_{\theta}^{\rho}}[Q_{\theta}(s,a)\psi_{\theta}(s,a)]$. While successful
tabular approaches rely on explicit computation of each softmax probability,
this is not feasible for most MDPs where the action space is infinite and
possibly uncountable. Typically some form of well-chosen function class is
required to address this issue. In this work, we consider all softmax
functions that satisfy the following smoothness properties:

######  Assumption 1.

(Smoothness of Policy Class) Consider policies
$\pi_{\theta}\propto\exp(\nu_{\theta})$. We require that $\pi$ obeys the
following two smoothness conditions:

$\displaystyle\int_{\mathcal{A}}\pi_{\theta}(a|s)\log\frac{\pi_{\theta}(a|s)}{\pi_{\theta+\eta}(a|s)}\,da\,\leq
C_{\nu,1}\left\lVert\eta\right\rVert^{\beta_{1}},$ (2)
$\displaystyle\left\lVert\psi_{\theta}(s,a)-\psi_{\theta+\eta}(s,a)\right\rVert\\!\leq\\!C_{\nu,2}\left\lVert\eta\right\rVert^{\beta_{2}}\\!\\!\\!\\!,$
(3)

where the constants $C_{\nu,1},C_{\nu,2}\geq 0$,
$\beta_{1}\in[1,2],\beta_{2}\in(0,1]$ are valid for all $\theta,s,a$.
Consequently we define $\beta_{0}=\min(\beta_{1}/4,\beta_{2})$ as the dominant
order of smoothness.

It will also be useful in our analysis to define
$\beta_{max}=\max(\beta_{1}/4,\beta_{2})$. We note that (2) is a Hölder
condition on the Kullback–Leibler (KL) divergence of the policies, while (3)
is a Hölder requirement on the score function.

Remarks: $\beta_{1}<2,\beta_{2}<1$ are weakly smooth cases. This is a weaker
assumption than traditional assumptions on Lipschitz smoothness; particularly,
it allows for slow tail decay. It is also possible to relax this assumption to
local conditions (i.e. only holding when $\left\lVert\eta\right\rVert\leq C$)
with Lipschitz behaviour at larger scales.

We introduce an additional assumption on the second moment of the score
function:

######  Assumption 2.

(Boundedness of Moments) Assume that the score function is absolutely bounded
in $L_{2}$ across all policies i.e. that the following holds for all $\theta$

$\displaystyle\int_{\mathcal{S}}\int_{\mathcal{A}}\left\lVert\psi_{\theta}(s,a)\right\rVert^{2}d_{\theta}^{\rho}(s,a)da\,ds\leq\psi_{\infty},$
(4)

for any $\theta$ in our parameter space, where $\psi_{\infty}<\infty$ is a
constant independent of $\theta$.

Remarks: Higher order integrability assumptions are possible. In fact, if
$\left\lVert\psi_{\theta}\right\rVert\leq\sqrt{\psi_{\infty}}$ holds
$d_{\theta}^{\rho}$-almost surely, we recover the standard bounded gradient
assumption found in other works, e.g. [XWL20, Liu+20].

Finally, we require the following standard assumption (see e.g. [XWL20,
ZXL19]) which we use to show smoothness of the objective function.

######  Assumption 3.

(Ergodicity) We have for all states $s_{0}\in\mathcal{S}$:

$\left\lVert\mathbb{P}^{n}_{\theta}(\cdot|s_{0})-\rho_{*}(\cdot)\right\rVert_{TV}\leq
C_{0}\delta^{n},$

where $\mathbb{P}^{n}_{\theta}$ is the $n$-step state transition kernel
following $\pi_{\theta}$, $\rho_{*}$ is the invariant state distribution,
$C_{0}\geq 0,\delta<1$ are constants independent of $s_{0},\theta$.

###  3.2 Policy Gradient

1: Initial parameter $\theta_{0}$.

2: for Step $t=1,\ldots,T$ do

3: for $i=1,\ldots B$ do

4: Let $j\sim\text{Geom}(1-\gamma)$, $h\sim\text{Geom}(1-\gamma^{1/2})$,
$\tau=j+h$.

5: Sample $\left(s_{0},a_{0},\ldots s_{\tau},a_{\tau}\right)\sim\text{MDP}$
following $\pi_{\theta_{t-1}}$.

6: $s_{t,i}\leftarrow s_{j},a_{t,i}\leftarrow a_{j}$.

7: $v_{t,i}\leftarrow\sum_{u=j}^{\tau}\gamma^{(u-j)/2}r_{u}$, $r_{u}\sim
R(\cdot|s_{u},a_{u})$.

8: end for

9: Choose $h_{t}$ specified in our learning rates section.

10:
$\theta_{t}\leftarrow\theta_{t-1}+\frac{h_{t}}{B}\sum_{i=1}^{B}v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})$.

11: end for

12: Return $\theta_{T}$.

Algorithm 1 Policy Gradient for Hölder Smooth Objectives

1: Initial parameter $\theta_{0}$, stability parameter $\xi\in(0,1]$.

2: for Step $t=1,\ldots,T$ do

3: for $i=1,\ldots B$ do

4: Let $j\sim\text{Geom}(1-\gamma)$, $h\sim\text{Geom}(1-\gamma^{1/2})$,
$\tau=j+h$.

5: Sample $\left(s_{0},a_{0},\ldots s_{\tau},a_{\tau}\right)\sim\text{MDP}$
following $\pi_{\theta_{t-1}}$.

6: $s_{t,i}\leftarrow s_{j},a_{t,i}\leftarrow a_{j}$.

7: $v_{t,i}\leftarrow\sum_{u=j}^{\tau}\gamma^{(u-j)/2}r_{u}$, $r_{u}\sim
R(\cdot|s_{u},a_{u})$.

8: end for

9: for $i=1,\ldots B$ do

10: Let $j\sim\text{Geom}(1-\gamma)$.

11: Sample $\left(s^{\prime}_{0},a^{\prime}_{0},\ldots
s^{\prime}_{j},a^{\prime}_{j}\right)\sim\text{MDP}$ following
$\pi_{\theta_{t-1}}$.

12: $s^{\prime}_{t,i}\leftarrow s^{\prime}_{j},a^{\prime}_{t,i}\leftarrow
a^{\prime}_{j}$.

13: end for

14: Choose $h_{t}$ specified in our learning rates section.

15:
$K_{t}\leftarrow\frac{1}{B}\sum_{i=1}^{B}\psi_{\theta_{t-1}}(s^{\prime}_{t,i},a^{\prime}_{t,i})\psi_{\theta_{t-1}}^{\top}(s^{\prime}_{t,i},a^{\prime}_{t,i})$.

16: $\theta_{t}\leftarrow\theta_{t-1}+\frac{h_{t}}{B}(K_{t}+\xi
I)^{-1}\sum_{i=1}^{B}v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})$.

17: end for

18: Return $\theta_{T}$.

Algorithm 2 Natural Policy Gradient for Hölder Smooth Objectives

Given these assumptions on the policy class, we can apply direct policy ascent
on the space of parameters in order to get the gradient update

$\theta_{t}=\theta_{t-1}+h_{t}\nabla_{\theta}J(\theta_{t-1}),$ (5)

where $h_{t}\in\mathbb{R}$ is an adaptive step size. Alternatively, natural
policy gradient (NPG), first introduced by [Kak01], is a parameter invariant
method that applies the following update

$\theta_{t}=\theta_{t-1}+h_{t}K^{\dagger}(\theta_{t-1})\nabla_{\theta}J(\theta_{t-1}),$
(6)

where $K(\theta)=\mathbb{E}_{s,a\sim
d_{\theta}^{\rho}}\left[\psi_{\theta}(s,a)\psi_{\theta}(s,a)^{\top}\right]$.
Here $(\cdot)^{\dagger}$ is the matrix pseudo-inverse. The advantage of this
method is that the optimization landscape becomes well-behaved.

Since the true loss function and Fisher information matrix are not available
to us, we estimate each of them through sampling. In particular, we use the
following minibatch estimators for $\nabla J$ and $K$:

$\displaystyle\widehat{\nabla
J(\theta_{t-1})}=\frac{1}{B}\sum_{i=1}^{B}v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i}),$
(7) $\displaystyle
K_{t}=\frac{1}{B}\sum_{i=1}^{B}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})\psi_{\theta_{t-1}}^{\top}(s_{t,i},a_{t,i}),$
(8)

and we use $(K_{t}+\xi I)^{-1}$ to approximate the inverse of the Fisher
matrix, where $\xi>0$ is a hyperparameter that guarantees the estimator is
numerically stable, $v_{t,i}$ is an unbiased estimator for
$Q_{\theta_{t-1}}(s,a)$ given in Algorithms 1-2 wherein we follow [Zha+20a,
Algorithm 1], and to sample from the occupancy measure $d_{\theta}^{\rho}$, we
sample trajectories following [Aga+20, Algorithm 1]. This procedure is
summarized in our Algorithms.

###  3.3 Learning Rates

In the sequel, we consider the following learning rates: (i) constant
$h_{t}=\lambda$, (ii) dependent on the total number of steps $h_{t}=\lambda
T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$, (iii) decaying $h_{t}=\lambda
t^{-q},q\in[0,1)$. We also state our Theorems 1-2 more generally for any step
size sequence $h_{t}$.

##  4 Applications

Figure 1: (a) Tail Growth: Comparing the growth of $\psi_{\theta}$ in one-
dimension for Gaussian policies versus the Generalized Gaussian (Example 1)
with $\alpha=0.5$, for the $[0,0]$ state in the MountainCar environment. (b)
Exploration Performance: Comparing the performance of Generalized Gaussian and
the standard Gaussian policy, with $\alpha=0.5$, for the reward function found
in Equation (10), $\left|\theta^{*}-\theta\right|=3.9$. The Generalized
Gaussian significantly outperforms during the exploration phase. The result is
similar for both PG and NPG. (c) Gradient Norm Growth: Comparing the growth of
Example 3 using as estimate of the $L_{2}$ norm described by Assumption 2,
versus $\max_{n}\left\lVert\psi_{\theta}(s_{n},a_{n})\right\rVert$ with
growing number of samples. While our criterion is stable, the $\max$ diverges
logarithmically.

We note two prominant applications of our assumptions: (i) an application of
Assumption 1 to exploration has been explicitly shown in [CMS17], (ii)
Assumption 2 has been shown to apply to Safe RL via the work of [PPR19]. Some
additional examples will serve to illustrate these points below.

For ease of demonstration, we consider policies and environments which
independently satisfy Assumptions 1-2 and Assumption 3 respectively, so long
as the other component is sufficiently regular. The following policies
illustrate why we might value weak smoothness:

######  Example 1.

(Generalized Gaussian Policy) If we choose the parameter $\kappa\in(1,2]$, we
can choose the generalized Gaussian distribution to parameterize our policy:

$\nu_{\theta}(a|s)=-\left|\left\langle\phi(s,a),\theta\right\rangle\right|^{\kappa}.$
(9)

See Figure 1(a) for a visualization of the smoothness of this policy.

This distribution is covered by our assumptions; in contrast, previous works
only permitted the strictly Gaussian distribution, where $\kappa=2$. In
particular, the tails of this distribution decay much more slowly than the
tails of the Gaussian distribution, which has applications to exploration-
based strategies. Indeed, let us consider the following single-state
exploration problem with the following (deterministic) reward

$\displaystyle
r(a_{t})=\left(1-(a_{t}-\theta^{*})^{2}\right)\mathbbm{1}_{\left|a_{t}-\theta^{*}\right|\leq
1},$ (10)

with policies $\nu_{\theta}(a)=-\left|a-\theta\right|^{\kappa}$ for $\kappa=2$
(a Gaussian policy) and $\kappa\in(1,2]$ (a generalized Gaussian).
$\theta^{*}\in\mathbb{R}$ is an unknown target. If $\theta^{*}$ is far from
our initial parameter, the agent will receive no gradient information so long
as it does not sample actions from the region of interest
$[\theta^{*}-1,\theta^{*}+1]$. For a policy with exponent $\kappa$, this
occurs with probability

$\displaystyle\pi_{\kappa,\theta_{0}}(a_{t}\in[\theta^{*}-1,\theta^{*}+1])$
$\displaystyle\quad=\frac{1}{2\Gamma(\kappa+1/\kappa)}\int_{\theta^{*}-1}^{\theta^{*}+1}\exp(-\left|a-\theta_{0}\right|^{\kappa})da,$

where $\pi_{\kappa,\theta_{0}}$ is the policy measure under the generalized
Gaussian with exponent $\kappa$ and parameter $\theta_{0}$. If
$\mathcal{U}=[\theta^{*}-1,\theta^{*}+1]$

$\displaystyle\pi_{\kappa,\theta_{0}}(a_{t}\in\mathcal{U})-\pi_{2,\theta_{0}}(a_{t}\in\mathcal{U})$
$\displaystyle\quad\geq\frac{1}{2\Gamma(\kappa+1/\kappa)}\int_{\theta^{*}-1}^{\theta^{*}+1}\exp(-\left|a-\theta_{0}\right|^{\kappa})$
$\displaystyle\ \ \ \ -\exp(-\left|a-\theta_{0}\right|^{2}+\log 2)da,$

which is $>0$ by simply comparing the terms in the exponents, when $\kappa\ll
2$ and $\left|\theta^{*}-\theta_{0}\right|\gg 0$. This difference in
probability can improve sample efficiency by many orders of magnitude. The
empirical performance of the two policies is found in Figure 1(b), with a
large improvement in number of samples needed to discover the correct action.
This example can be easily generalized to more complex bandits/MDPs.

Another example shows the richness of the weakly smooth assumption:

######  Example 2.

($p$-Harmonic minimizers) It is known [CM99, Lin17] that local minimizers
$\nu$ to the $p$-Harmonic functional, for
$p(x):\mathbb{R}^{d}\mapsto\mathbb{R}$

$\mathcal{F}(\nu)\triangleq\int_{\mathbb{R}^{d}}\left\lVert\nabla\nu\right\rVert^{p(x)}\,dx,$
(11)

are weakly smooth of some order $L(p)<1$ when $p(x)>1$.

One can also restrict the integration above to a compact set. Consequently,
these can serve as interesting potential functions. Note that we can add any
bounded potential with bounded and Lipschitz gradient to such functions while
preserving Hölder regularity. Weak smoothness has also been shown for many
other elliptic families of PDEs [HL20, Sci14], which may also motivate some
candidate policies.

To illustrate the distinction of Assumption 2 from standard
$\left\lVert\cdot\right\rVert_{\infty}$ bounds, consider the following policy
class:

######  Example 3.

(Safe Policies) Consider the following potential for
$\theta\in[-1,1],\left\lVert\phi^{*}\right\rVert\leq 1$:

$\nu_{\theta}(s,a)=-\theta\log\left\lVert\phi(s,a)-\phi^{*}\right\rVert.$ (12)

Under uniform dynamics and a uniform distribution of $\phi(s,a)$ on a ball of
radius $1$ around the origin, this family satisfies Assumption 2, but not the
standard assumption of absolute boundedness
$\sup_{s,a}\left\lVert\psi_{\theta}(s,a)\right\rVert_{\infty}<\infty$ (see
Figure 1(c) for an empirical demonstration). This policy explicits avoids the
state-action region around $\phi^{*}$; this can arise practically when
considering safety or instability constraints in RL.

##  5 Main Results

In the sequel, define
$E_{\Pi}=\max_{\theta\in\Theta}\mathbb{E}_{s,a\sim{d_{\theta}^{\rho}}}\left[\left\lVert\psi_{\theta}(s,a)^{\top}K(\theta)^{\dagger}\nabla
J(\theta)-A_{\theta}(s,a)\right\rVert^{2}\right]$ and the quantity
$D_{\infty}=1+\sup_{\theta_{1},\theta_{2}\in\Theta}\left\lVert\frac{d_{\theta_{1}}^{\rho}}{d_{\theta_{2}}^{\rho}}\right\rVert_{\infty}$.

######  Theorem 1.

Under Assumptions 1-3, Policy Gradient and Natural Policy Gradient achieves
the following convergence:

$\displaystyle\sum_{t=1}^{T}h_{t}\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t})\right\rVert^{2}\right]$ $\displaystyle\leq
C_{k,1}\left(J_{*}-J(\theta_{0})\right)+\frac{C_{k,2}}{1-\gamma}\sum_{t=1}^{T}\Biggl{(}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t})\right\rVert^{\frac{\beta_{1}}{4}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}\right)$
$\displaystyle\qquad+h_{t}^{\beta_{2}+1}\left(\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t})\right\rVert^{\beta_{2}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}\right)\Biggr{)},$

where the $k$ in $C_{k,1},C_{k,2}$ is either $PG,NPG$ depending on whether
policy gradient or natural policy gradient is considered. The exact values of
these constants are defined in the Appendix. They do not depend on
$\epsilon,\gamma$ for either algorithm. $\sigma=3\alpha\sqrt{\psi_{\infty}}$
controls the variance of the gradient. $J(\theta_{0})$ is the initial
performance and $J_{*}=\sup_{\theta\in\Theta}J(\theta)$, which is finite due
to the boundedness of the reward. $B$ is the batch size and the remaining
constants are specified in the Appendices.

Remarks: If we replace Assumption 2 with an almost sure bound on
$\left\lVert\psi_{\theta}\right\rVert$, the exponent $\beta_{1}/4+1$ becomes
instead $\beta_{1}/2+1$.

With respect to the ergodicity mixing rate $\delta$, $C_{k,2}$ scales as
$1/(1-\delta)$ for both algorithms, which is analogous to other works with
ergodicity [XWL20, Proposition 1].

######  Corollary 1.

(Rates under various step-size schemes) Table 1 encapsulates the orders of
growth of $\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t})\right\rVert^{2}\right]$ for each of the learning rates examined
in our paper, for the choice of $\lambda$ sufficiently small and
$B\gtrsim\frac{\sigma^{2}}{(1-\gamma)^{2}}.$

Table 1: Results for various learning rate schemes, for both policy gradient and natural policy gradient. We only track the primary dependence in $T,B,\gamma$. For the decaying learning rate, we define the coefficient $f(q,\beta_{0})=\min(\frac{2q\beta_{0}}{1-\beta_{0}},1-q)$. In each case we require at least $\lambda^{\beta_{0}}\lesssim\frac{1-\gamma}{C}$ where $C$ does not depend on $\gamma,\epsilon$. $h_{t}$ | Order | Considerations
---|---|---
$\lambda$ | $O(\lambda^{-1}T^{-1})+O((\sqrt{B}(1-\gamma))^{-\beta_{0}-1})+O((\lambda^{\beta_{0}}(1-\gamma))^{-1})^{\frac{2}{1-\beta_{0}}})$ |  $\lambda$-dependent Bias
$\lambda T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$ | $O(\lambda^{-1}T^{-\frac{2\beta_{0}}{1-\beta_{0}}})+O(T^{\frac{\beta_{0}^{2}-\beta_{0}}{\beta_{0}+1}}(\sqrt{B}(1-\gamma))^{-\beta_{0}-1})$ |
$\lambda t^{-q}$ | $\tilde{O}(\lambda^{-1}T^{-f(q,\beta_{0})})+O(T^{-q\beta_{0}}(\sqrt{B}(1-\gamma))^{-\beta_{0}-1})$ |

For global optimality, policy gradient requires another opaque assumption in
order to demonstrate convergence:

######  Assumption 4.

(Requirements for Policy Gradient) Assume that there is a
$\theta_{*}\in\Theta$ where $J$ attains its maximum. Furthermore, let
$\theta\in\Theta$ be any parameter. Then, we assume that $J$ is $m$-dominated
for any $m>0$, i.e. that the following holds

$\displaystyle
J(\theta_{*})-J(\theta)\leq\frac{m}{1-\gamma}\left\langle\theta_{*}-\theta,\nabla
J(\theta)\right\rangle.$

Furthermore, suppose that
$\text{Diam}(\Theta)\triangleq\sup_{\theta_{1},\theta_{2}\in\Theta}\left\lVert\theta_{1}-\theta_{2}\right\rVert<\infty$.

See [BR19, Lemma 3(a)] for analogous conditions, which are often violated in
practice.

######  Theorem 2.

Let $\theta_{*}=\arg\max_{\theta\in\Theta}J(\theta)$. Under Assumptions 1-3,
Natural Policy Gradient is bounded with the following for $t\in 1\ldots T$:

$\begin{split}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t-1})\right]&\leq\frac{C_{NPG,3}}{1-\gamma}h_{t}^{\beta_{1}-1}\left(\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{1}}+\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t-1})\right\rVert^{\beta_{1}}\right]\right)\\\
&\qquad+\frac{C_{NPG,4}h_{t}^{\beta_{2}}}{1-\gamma}\left(\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}+\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t-1})\right\rVert^{\beta_{2}+1}\right]\right)\\\
&\qquad+\frac{C_{NPG,5}}{1-\gamma}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}+\frac{\sqrt{E_{\Pi}}}{\sqrt{\psi_{\infty}}}+\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t-1})\right\rVert\right]\right).\end{split}$

Here, $E_{\Pi}$ is a policy dependent parameter that serves to lower bound the
optimality of the function class, $\sigma$ is the variance from Theorem 1, and
$\xi$ is the stability constant found in Algorithm 2.

If, additionally, Assumption 4 is added, then the standard Policy Gradient is
bounded by the following for $t\in 1\ldots T$:

$J(\theta_{*})-\mathbb{E}{\left[J(\theta_{t-1})\right]}\leq\frac{m\text{Diam}(\Theta)}{1-\gamma}\mathbb{E}\left[\left\lVert\nabla
J(\theta_{t-1})\right\rVert\right],$ (13)

where $\text{Diam}(\Theta)$ is defined in Assumption 4.

Here, $\theta_{*}$ is the minimizer from Assumption 4, and $C_{NPG,3-5}$ are
not dependent on $h_{t},B,T,\gamma$ and are stated explicitly in the
appendices. For natural policy gradient, there are no additional assumptions
apart from the bias term $E_{\Pi}$ being finite; this is bounded under
standard assumptions (see [Aga+20, Remark 6.4]). This is a major advantage of
NPG over its vanilla counterpart, which requires a strong additional
regularity condition.

For both natural and standard policy gradient, if we take the minimum over
$t=1\ldots T$, we obtain the rates in the following corollary.

######  Corollary 2.

For $\lambda$ sufficiently small and the learning rate $h_{t}=\lambda
T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$, for Policy Gradient the following holds
under Assumptions 1-4

$\displaystyle\min_{t=0,\ldots
T-1}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t})\right]\leq\epsilon.$

For Natural Policy Gradient the following holds under Assumptions 1-3

$\displaystyle\min_{t=0,\ldots
T-1}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t})\right]\leq\epsilon+\frac{\sqrt{D_{\infty}E_{\Pi}}}{1-\gamma}.$

Recall that $E_{\Pi}$ is an approximation error, and $D_{\infty}$ measures the
irregularity of the initial distribution. For either algorithm if
$h_{t}=\lambda T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$,

$\displaystyle
T\geq\epsilon^{-\frac{\beta_{0}+1}{\beta_{0}}}(1-\gamma)^{-\frac{2\beta_{0}^{2}+3\beta_{0}+1}{2\beta_{0}^{2}}},\qquad
B\gtrsim\epsilon^{-2}(1-\gamma)^{-\frac{4\beta_{0}^{2}+5\beta_{0}-1}{\beta_{0}(\beta_{0}+1)}}.$

For both algorithms if instead $h_{t}=\lambda$,

$\displaystyle
T\geq\epsilon^{-\frac{\beta_{0}+1}{\beta_{0}}}(1-\gamma)^{-\frac{2+\beta_{0}}{\beta_{0}}},\qquad
B\gtrsim\epsilon^{-\frac{4}{\beta_{0}+1}}(1-\gamma)^{-\frac{6+2\beta_{0}}{\beta_{0}+1}}.$

##  6 Related Work

###  6.1 Optimization and Stochastic Approximation

We primarily refer to work on stochastic approximation, which began with the
work by authors [PJ92, KY03], who established basic conditions for convergence
for linear approximation procedures, with rates being obtained under strong
assumptions. Tighter bounds have recently been achieved through improved
analysis and techniques, both in asymptotic and non-asmyptotic contexts
[Che+16, LS18, Jai+18].

The theory for optimizing weakly smooth rather than Lipschitz functionals was
primarily developed in the following works [DGN14, Nes15, Yas16], introducing
the definition of weak-smoothness through Hölder conditions, and showing
convergence via smoothing or fast decaying learning rates. Lastly, our
analysis relies heavily on the theory of ergodicity for MDPs. We build on the
works of [Mit05] which yields perturbation bounds on the state distribution,
and subsequent improvements in the assumptions and condition numbers [FHL13,
RS+18, MS20].

###  6.2 Reinforcement Learning

The general formulation of reinforcement learning can be attributed to
Bellman’s formulation of Markov Decision processes [Bel54]. Gradient-based
approaches were proposed to solve direct policy parameterizations [Wil92];
developments in this classical setting include [SPS99, KT00, Kak+03]. These
works established asymptotically tight bounds for convergence in the tabular
setting, while outlining rough conditions for convergence when feature
transformations were applied. The introduction of natural gradient techniques
[Kak01], which borrowed from similar work in standard optimization [Ama98],
yielded improved convergence with respect to policy condition numbers. In
particular, strong convergence holds for domains such as the linear quadratic
regulator [Faz+18, TR18] and other linearized problems.

Even so, lower bounds for general problems can be quite pessimistic,
especially when the conditions are ill-specified [Sut+00]. This debate has
attracted renewed focus in recent years, with an on-going discussion on the
quality of representation and its effect on learnability [Du+19, VD19].
Nonetheless, real world problems are either continuous or well-approximated by
continuous algorithms, with smooth state-space. [Aga+20a, Aga+20] provided a
convergence and optimality result for both tabular and linear settings, but
only when the action space was discrete and the problem was deterministic.
Other results in this setting include [Mei+21, Zha+20, Mei+20, Zha+21].
[XWL20, KKR19] focus on general settings, but only under generous smoothness
and boundedness assumptions. Numerous works have since focused on feature
representations in policy learning, particularly through use of neural
networks [TB17, Wan+19, Liu+19]; these apply similarly strict assumptions on
the problem class in order to achieve good rates of convergence.

We would like to comment extensively on the results of [Liu+20], which obtains
highly competitive rates for PG and NPG, of $O(\epsilon^{-4})$ and
$O(\epsilon^{-3})$ respectively. While our rate for NPG is worse at $\to
O(\epsilon^{-4}),\beta_{0}\to 1$, this is because of numerous differences
between our formulations. [Liu+20] rely on more complex sampling and natural
gradient procedures, particularly requiring stochastic gradient descent in
order to solve for the NPG update vector. It is unclear whether this technique
can generalize to the weakly smooth regime. Instead, we analyze a much simpler
algorithm that involves direct estimation of the Fisher information matrix,
with an additional cost in $\epsilon$, while also handling non-constant
learning rates.

Our results are simultaneously valid for continuous settings, while removing
many of the strict assumptions found in previous results. In particular,
smoothness of the policy class and boundedness of the gradient limited the
scope of policies. We build upon work in weakly smooth optimization to relax
these assumptions.

##  7 Discussion

In this work, we established the convergence guarantees for the policy
gradient for weakly smooth and continuous action space settings. To the best
of our knowledge, this is the first work to establish the convergence of
policy gradient methods under an unbounded gradient without Lipschitz
smoothness conditions. Thus, our work significantly generalizes the scope of
existing analysis while opening numerous lines of future research. Our
assumptions are also practically applicable, as we demonstrate through several
examples.

Nonetheless, there are many important limitations for our analysis. Firstly,
it is likely that Assumption 4 can be significantly relaxed, as in other
recent work [Liu+20]. A more careful analysis would have more complex
dependence on the problem parameters. It may also be interesting to consider
weaker assumptions than ergodicity, by adding regularization conditions on the
initial distribution of policies. For practical problems, this is often
necessary since the smoothness coefficients can be unbounded except in a
reasonable starting set. We also believe that weak smoothness can be relaxed
further to locally non-smooth problems ($\beta_{0}=0$), by applying smoothing
techniques from optimization [Nes15]. In addition, no practical studies on
empirical performance have been done when considering the trade-off between
smoothness conditions and convergence rates. Finally, we can quantify the
convergence of the distribution of $J(\theta)$ using functionals such as the
KL divergence or Wasserstein metric.

## References

  * [Aga+20] Alekh Agarwal, Sham M Kakade, Jason D Lee and Gaurav Mahajan  “Optimality and approximation with policy gradient methods in markov decision processes”  In _Conference on Learning Theory_ , 2020, pp. 64–66
  * [Aga+20a] Alekh Agarwal, Mikael Henaff, Sham Kakade and Wen Sun  “Pc-pg: Policy cover directed exploration for provable policy gradient learning”  In _arXiv preprint arXiv:2007.08459_ , 2020
  * [Ama98] Shun-Ichi Amari  “Natural gradient works efficiently in learning”  In _Neural computation_ 10.2 MIT Press, 1998, pp. 251–276
  * [Bel54] Richard Bellman  “The theory of dynamic programming”, 1954
  * [BR19] Jalaj Bhandari and Daniel Russo  “Global optimality guarantees for policy gradient methods”  In _arXiv preprint arXiv:1906.01786_ , 2019
  * [Cai+19] Qi Cai, Zhuoran Yang, Chi Jin and Zhaoran Wang  “Provably efficient exploration in policy optimization”  In _arXiv preprint arXiv:1912.05830_ , 2019
  * [Che+16] Xi Chen, Jason D Lee, Xin T Tong and Yichen Zhang  “Statistical inference for model parameters in stochastic gradient descent”  In _arXiv preprint arXiv:1610.08637_ , 2016
  * [CM99] Alessandra Coscia and Giuseppe Mingione  “Hölder continuity of the gradient of p (x)-harmonic mappings”  In _Comptes Rendus de l’Académie des Sciences-Series I-Mathematics_ 328.4 Elsevier, 1999, pp. 363–368
  * [CMS17] Po-Wei Chou, Daniel Maturana and Sebastian Scherer  “Improving stochastic policy gradients in continuous control with deep reinforcement learning using the beta distribution”  In _International conference on machine learning_ , 2017, pp. 834–843  PMLR
  * [Den+16] Yue Deng et al.  “Deep direct reinforcement learning for financial signal representation and trading”  In _IEEE transactions on neural networks and learning systems_ 28.3 IEEE, 2016, pp. 653–664
  * [DGN14] Olivier Devolder, François Glineur and Yurii Nesterov  “First-order methods of smooth convex optimization with inexact oracle”  In _Mathematical Programming_ 146.1 Springer, 2014, pp. 37–75
  * [Doy00] Kenji Doya  “Reinforcement learning in continuous time and space”  In _Neural computation_ 12.1 MIT Press, 2000, pp. 219–245
  * [Du+19] Simon S Du, Sham M Kakade, Ruosong Wang and Lin F Yang  “Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?”  In _arXiv preprint arXiv:1910.03016_ , 2019
  * [Faz+18] Maryam Fazel, Rong Ge, Sham M Kakade and Mehran Mesbahi  “Global convergence of policy gradient methods for linearized control problems”, 2018
  * [FHL13] Déborah Ferré, Loïc Hervé and James Ledoux  “Regular perturbation of V-geometrically ergodic Markov chains”  In _Journal of applied probability_ 50.1 Cambridge University Press, 2013, pp. 184–194
  * [HL20] Fredrik Arbo Høeg and Peter Lindqvist  “Regularity of solutions of the parabolic normalized p-Laplace equation”  In _Advances in Nonlinear Analysis_ 9.1 De Gruyter, 2020, pp. 7–15
  * [Jai+18] Prateek Jain et al.  “Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification”  In _Journal of Machine Learning Research_ 18, 2018
  * [Kak+03] Sham Machandranath Kakade  “On the sample complexity of reinforcement learning”, 2003
  * [Kak01] Sham M Kakade  “A natural policy gradient”  In _Advances in neural information processing systems_ 14, 2001, pp. 1531–1538
  * [KBP13] Jens Kober, J Andrew Bagnell and Jan Peters  “Reinforcement learning in robotics: A survey”  In _The International Journal of Robotics Research_ 32.11 SAGE Publications Sage UK: London, England, 2013, pp. 1238–1274
  * [KKR19] Harshat Kumar, Alec Koppel and Alejandro Ribeiro  “On the sample complexity of actor-critic method for reinforcement learning with function approximation”  In _arXiv preprint arXiv:1910.08412_ , 2019
  * [KT00] Vijay R Konda and John N Tsitsiklis  “Actor-critic algorithms”  In _Advances in neural information processing systems_ , 2000, pp. 1008–1014
  * [KY03] Harold Kushner and G George Yin  “Stochastic approximation and recursive algorithms and applications”  Springer Science & Business Media, 2003
  * [Lin17] Peter Lindqvist  “Notes on the p-Laplace equation”  University of Jyväskylä, 2017
  * [Liu+19] Boyi Liu, Qi Cai, Zhuoran Yang and Zhaoran Wang  “Neural proximal/trust region policy optimization attains globally optimal policy”  In _arXiv preprint arXiv:1906.10306_ , 2019
  * [Liu+20] Yanli Liu, Kaiqing Zhang, Tamer Basar and Wotao Yin  “An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods.”  In _NeurIPS_ , 2020
  * [LS18] Chandrashekar Lakshminarayanan and Csaba Szepesvari  “Linear stochastic approximation: How far does constant step-size and iterate averaging go?”  In _International Conference on Artificial Intelligence and Statistics_ , 2018, pp. 1347–1355  PMLR
  * [Mei+20] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari and Dale Schuurmans  “On the global convergence rates of softmax policy gradient methods”  In _International Conference on Machine Learning_ , 2020, pp. 6820–6829  PMLR
  * [Mei+21] Jincheng Mei et al.  “Leveraging non-uniformity in first-order non-convex optimization”  In _arXiv preprint arXiv:2105.06072_ , 2021
  * [Mit05] A Yu Mitrophanov  “Sensitivity and convergence of uniformly ergodic Markov chains”  In _Journal of Applied Probability_ 42.4 Cambridge University Press, 2005, pp. 1003–1014
  * [MS20] Yonghua Mao and Yanhong Song  “Perturbation theory and uniform ergodicity for discrete-time Markov chains”  In _arXiv preprint arXiv:2003.06978_ , 2020
  * [Nes15] Yu Nesterov  “Universal gradient methods for convex optimization problems”  In _Mathematical Programming_ 152.1 Springer, 2015, pp. 381–404
  * [PJ92] Boris T Polyak and Anatoli B Juditsky  “Acceleration of stochastic approximation by averaging”  In _SIAM journal on control and optimization_ 30.4 SIAM, 1992, pp. 838–855
  * [PPR19] Matteo Papini, Matteo Pirotta and Marcello Restelli  “Smoothing policies and safe policy gradients”  In _arXiv preprint arXiv:1905.03231_ , 2019
  * [RS+18] Daniel Rudolf and Nikolaus Schweizer  “Perturbation theory for Markov chains via Wasserstein distance”  In _Bernoulli_ 24.4A Bernoulli Society for Mathematical StatisticsProbability, 2018, pp. 2610–2639
  * [Sci14] Berardino Sciunzi  “Regularity and comparison principles for p-Laplace equations with vanishing source term”  In _Communications in Contemporary Mathematics_ 16.06 World Scientific, 2014, pp. 1450013
  * [Sid+18] Aaron Sidford et al.  “Near-optimal time and sample complexities for solving discounted Markov decision process with a generative model”  In _arXiv preprint arXiv:1806.01492_ , 2018
  * [SPS99] Richard S Sutton, Doina Precup and Satinder Singh  “Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning”  In _Artificial intelligence_ 112.1-2 Elsevier, 1999, pp. 181–211
  * [Sut+00] Richard S Sutton, David A McAllester, Satinder P Singh and Yishay Mansour  “Policy gradient methods for reinforcement learning with function approximation”  In _Advances in neural information processing systems_ , 2000, pp. 1057–1063
  * [TB17] Philip S Thomas and Emma Brunskill  “Policy gradient methods for reinforcement learning with function approximation and action-dependent baselines”, 2017
  * [TR18] Stephen Tu and Benjamin Recht  “Least-squares temporal difference learning for the linear quadratic regulator”  In _International Conference on Machine Learning_ , 2018, pp. 5005–5014  PMLR
  * [VD19] Benjamin Van Roy and Shi Dong  “Comments on the du-kakade-wang-yang lower bounds”  In _arXiv preprint arXiv:1911.07910_ , 2019
  * [Wan+19] Lingxiao Wang, Qi Cai, Zhuoran Yang and Zhaoran Wang  “Neural policy gradient methods: Global optimality and rates of convergence”  In _arXiv preprint arXiv:1909.01150_ , 2019
  * [Wil92] Ronald J Williams  “Simple statistical gradient-following algorithms for connectionist reinforcement learning”  In _Machine learning_ 8.3-4 Springer, 1992, pp. 229–256
  * [XWL20] Tengyu Xu, Zhe Wang and Yingbin Liang  “Improving Sample Complexity Bounds for Actor-Critic Algorithms”  In _arXiv preprint arXiv:2004.12956_ , 2020
  * [Yas16] Maryam Yashtini  “On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients”  In _Optimization letters_ 10.6 Springer, 2016, pp. 1361–1370
  * [YLN19] Chao Yu, Jiming Liu and Shamim Nemati  “Reinforcement learning in healthcare: A survey”  In _arXiv preprint arXiv:1908.08796_ , 2019
  * [YW19] Lin F Yang and Mengdi Wang  “Sample-optimal parametric q-learning using linearly additive features”  In _arXiv preprint arXiv:1902.04779_ , 2019
  * [Zha+20] Junyu Zhang et al.  “Variational policy gradient method for reinforcement learning with general utilities”  In _arXiv preprint arXiv:2007.02151_ , 2020
  * [Zha+20a] Kaiqing Zhang, Alec Koppel, Hao Zhu and Tamer Basar  “Global convergence of policy gradient methods to (almost) locally optimal policies”  In _SIAM Journal on Control and Optimization_ 58.6 SIAM, 2020, pp. 3586–3612
  * [Zha+21] Junyu Zhang et al.  “On the convergence and sample efficiency of variance-reduced policy gradient method”  In _arXiv preprint arXiv:2102.08607_ , 2021
  * [ZXL19] Shaofeng Zou, Tengyu Xu and Yingbin Liang  “Finite-sample analysis for sarsa with linear function approximation”  In _arXiv preprint arXiv:1902.02234_ , 2019

The structure of the appendix is as follows. First we show the weak smoothness
of the objective function $J(\theta)$. Then, we prove Theorem 1 and Theorem 2
respectively, as well as their respective corollaries. In the final appendix,
we state the details for our numerical demonstrations.

##  Appendix A Weak Smoothness of Objective

Recall the definitions of $\mathbb{P}^{n}_{\theta}$ as the $n$-step state
transition kernel of the Markov chain induced by the policy $\pi_{\theta}$. We
denote $\mathbb{P}_{\theta}\triangleq\mathbb{P}_{\theta}^{1}$ as a shorthand.
In the following, we refer to a Markov Chain as a pair
$(\mathcal{S},\mathbb{Q})$, where the first item is the state-space and the
second item is the (time-invariant) transition function.

###  A.1 Visitation Distribution Smoothness

Now we bound the differences between the visitation distributions of two
policies. We first introduce a lemma from the theory of Markov Chains,
connecting ergodicity with the perturbation bounds on the $n$-step transition
kernels.

######  Lemma 1.

(Adapted from [MS20], Theorem 2.1) Let the Markov Chains generated by
$(\mathcal{S},\mathbb{P}_{\theta})$, $\mathcal{S}$ satisfy the uniform
ergodicity assumption, Assumption 3. Then for any initial distribution $\rho$,

$\displaystyle\int\mathbb{E}_{s_{0}\sim\rho}\left[\left|\mathbb{P}_{\theta}^{n}(s|s_{0})-\mathbb{P}_{\theta+\eta}^{n}(s|s_{0})\right|\right]\,ds\leq\frac{C_{0}}{1-\delta}D(\mathbb{P}_{\theta},\mathbb{P}_{\theta+\eta}),$

where
$D(\mathbb{Q},\mathbb{R})=\sup_{s}\int\left|\mathbb{Q}(s^{\prime}|s)-\mathbb{R}(s^{\prime}|s)\right|\,ds^{\prime}$
is a measure of distance between two kernels, and where $C_{0},\delta$ are the
constants from Assumption 3.

######  Lemma 2.

Let $\rho$ be any probability distribution on $\mathcal{S}$, and $\pi$. Then,
for parameters $\theta,\eta\in\mathbb{R}^{n}$

$\displaystyle\left\lVert
d_{\theta}^{\rho}-d_{\theta+\eta}^{\rho}\right\rVert\leq
L_{d}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}},$

where $L_{d}=\frac{(1+C_{0}-\delta)\sqrt{2C_{\nu,1}}}{(1-\delta)}$, with
$C_{0},\delta$ from Assumption 3 and $C_{\nu,1},\beta_{1}$ from Assumption 1.

Proof: Let us factor the state distribution as the following:

$d_{\theta}^{\rho}(s^{\prime},a)=H_{\theta}^{\rho}(s^{\prime})\pi_{\theta}(a|s^{\prime}).$

Therefore we can bound the difference of two visitation distributions as:

$\begin{split}\int\int\left|d_{\theta}^{\rho}(s,a)-d_{\theta+\eta}^{\rho}(s,a)\right|\,da\,ds&\leq\int\int\left|H_{\theta}^{\rho}(s)\pi_{\theta}(a|s)-H_{\theta+\eta}^{\rho}(s)\pi_{\theta+\eta}(a|s)\right|\,da\,ds\\\
&\qquad+\int\int\left|H_{\theta+\eta}^{\rho}(s)\pi_{\theta}(a|s)-H_{\theta+\eta}^{\rho}(s)\pi_{\theta+\eta}(a|s)\right|\,da\,ds\\\
&\leq\int\left|H_{\theta}^{\rho}(s)-H_{\theta+\eta}^{\rho}(s)\right|\int\pi_{\theta}(a|s)\,da\,ds\\\
&\qquad+\int
H_{\theta}^{\rho}(s)\int\left|\pi_{\theta}(a|s)-\pi_{\theta+\eta}(a|s)\right|\,da\,ds\\\
&\leq\left\lVert
H_{\theta}^{\rho}-H_{\theta+\eta}^{\rho}\right\rVert_{TV}+\sup_{s}\int\left|\pi_{\theta}(a|s)-\pi_{\theta+\eta}(a|s)\right|\,da.\end{split}$

The second term can be bounded using Pinsker’s inequality and Assumption 1,
obtaining

$\displaystyle\sup_{s}\int\left|\pi_{\theta}(a|s)-\pi_{\theta+\eta}(a|s)\right|\,da$
$\displaystyle\leq\sqrt{2}\sup_{s}\sqrt{\int\pi_{\theta}(a|s)\log\frac{\pi_{\theta}(a|s)}{\pi_{\theta+\eta}(a|s)}\,da}$
$\displaystyle\leq\sqrt{2C_{\nu,1}}\left\lVert\eta\right\rVert^{\beta_{1}/2}.$

For the other term, by Lemma 1, we know that for all $n>0$ under Assumption 3

$\int\left|\mathbb{E}_{s_{0}\sim\rho}\left[\mathbb{P}_{\theta}^{n}(s|s_{0})-\mathbb{P}_{\theta+\eta}^{n}(s|s_{0})\right]\right|\,ds\leq\frac{C_{0}}{1-\delta}D(\mathbb{P}_{\theta},\mathbb{P}_{\theta+\eta}).$

Under these assumptions, the norm of the visitation distribution under
perturbation can be bounded by the norm of the perturbation kernel using Lemma
2:

$\displaystyle\left\lVert
H_{\theta}^{\rho}-H_{\theta+\eta}^{\rho}\right\rVert_{TV}$
$\displaystyle\leq\int(1-\gamma)\sum_{n=1}^{\infty}\gamma^{n}\left|\mathbb{E}_{s_{0}\sim\rho}[\mathbb{P}^{n}_{\theta}(s|s_{0})-\mathbb{P}^{n}_{\theta+\eta}(s|s_{0})]\right|\,ds$
$\displaystyle=(1-\gamma)\sum_{n=1}^{\infty}\gamma^{n}\int\left|\mathbb{E}_{s_{0}\sim\rho}\left[\mathbb{P}_{\theta}^{n}(s|s_{0})-\mathbb{P}_{\theta+\eta,\rho}^{n}(s|s_{0})\right]\right|\,ds$
$\displaystyle\leq\frac{C_{0}}{1-\delta}D(\mathbb{P}_{\theta},\mathbb{P}_{\theta+\eta})$
$\displaystyle=\sup_{s}\frac{C_{0}}{1-\delta}\left(\int\int
P(s^{\prime}|s,a)\left|\pi_{\theta}(a|s)-\pi_{\theta+\eta}(a|s)\right|\,ds^{\prime}\,da\right)$
$\displaystyle\overset{(i)}{=}\sup_{s}\frac{C_{0}}{1-\delta}\int\left|\pi_{\theta}(a|s)-\pi_{\theta+\eta}(a|s)\right|\,da$
$\displaystyle\overset{(ii)}{\leq}\frac{C_{0}\sqrt{2C_{\nu,1}}}{(1-\delta)}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}},$

where $(i)$ follows as $\int P(s^{\prime}|s,a)\,ds^{\prime}=1$ for any $s,a$,
$(ii)$ is again using Pinsker’s inequality and Assumption 1. Returning to our
overall bound, we get:

$\begin{split}\left\lVert
d_{\theta}^{\rho}-d_{\theta+\eta}^{\rho}\right\rVert_{TV}&\leq\left\lVert
H_{\theta}^{\rho}-H_{\theta+\eta}^{\rho}\right\rVert_{TV}+\sup_{s}\int\left|\pi_{\theta}(a|s)-\pi_{\theta+\eta}(a|s)\right|\,da\\\
&\leq\frac{C_{0}\sqrt{2C_{\nu,1}}}{(1-\delta)}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}}+\sqrt{2C_{\nu,1}}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}}\\\
&\leq\frac{(1+C_{0}-\delta)\sqrt{2C_{\nu,1}}}{(1-\delta)}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}}.\end{split}$

This concludes the proof. $\square$

###  A.2 Q-function Analysis

######  Lemma 3.

Let $\rho$ be any probability distribution on $\mathcal{S}$, and let the
policy class and the MDP satisfy Assumptions 1, 3. Then for parameters
$\theta,\eta\in\mathbb{R}^{n}$

$\int\int
d_{\theta}^{\rho}(s,a)\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|\,da\,ds\leq\frac{L_{Q}}{1-\gamma}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}},$

where
$L_{Q}=\frac{\alpha\gamma(1+C_{0}-\delta)\sqrt{2C_{\nu,1}}}{(1-\delta)}$, with
$C_{0},\delta$ from Assumption 3 and $C_{\nu,1}$ from Assumption 1, $\alpha$
bounds the absolute value of the reward, and $\gamma$ is the discount factor.

Define the state distribution with the density
$\tilde{\rho}_{s,a}(s^{\prime})=P(s^{\prime}|a,s)$ as the state distribution
after taking action $a$ in state $s$ We can write the definition of the
Q-function as:

$\displaystyle Q_{\theta}(s,a)$ $\displaystyle=\int
rR(r|s,a)\,dr+\gamma\int\int\int
r\tilde{\rho}_{s,a}(s^{\prime})\pi_{\theta}(a^{\prime}|s^{\prime})R(r|s^{\prime},a^{\prime})\,dr\,da^{\prime}\,ds^{\prime}$
$\displaystyle\qquad+\sum_{n=2}^{\infty}\gamma^{n}\int\int\int
r\mathbb{E}_{s_{0}\sim\tilde{\rho}_{s,a}}\left[\mathbb{P}_{\theta}^{n-1}(s^{\prime}|s_{0})\right]\pi_{\theta}(a^{\prime}|s^{\prime})R(r|s^{\prime},a^{\prime})\,dr\,da^{\prime}\,ds^{\prime}$
$\displaystyle=\int rR(r|s,a)\,dr+\frac{\gamma}{1-\gamma}\int\int\int
rR(r|s^{\prime},a^{\prime})d_{\theta}^{\tilde{\rho}_{s,a}}(s^{\prime},a^{\prime})\,dr\,da^{\prime}\,ds^{\prime},$

Subsequently the difference reduces to:

$\displaystyle\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|$
$\displaystyle\leq\frac{\gamma}{1-\gamma}\int\int\int\left|r\right|R(r|s^{\prime},a^{\prime})\left|d_{\theta}^{\tilde{\rho}_{s,a}}(s^{\prime},a^{\prime})-d_{\theta+\eta}^{\tilde{\rho}_{s,a}}(s^{\prime},a^{\prime})\right|\,dr\,da^{\prime}\,ds^{\prime}$
$\displaystyle\overset{(i)}{\leq}\frac{\alpha\gamma}{1-\gamma}\int\int\left|d_{\theta}^{\tilde{\rho}_{s,a}}(s^{\prime},a^{\prime})-d_{\theta+\eta}^{\tilde{\rho}_{s,a}}(s^{\prime},a^{\prime})\right|\,da^{\prime}\,ds^{\prime},$

where in $(i)$ we recall that the reward distribution has bounded support on
$[-\alpha,\alpha]$. This then reduces to Lemma 2, under the initial
distribution $\tilde{\rho}_{s,a}$. From our earlier bound we obtain the
following:

$\begin{split}\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|&\leq\frac{\alpha\gamma
L_{d}}{1-\gamma}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}}.\end{split}$

Finally, we can plug this bound into the integral to get

$\displaystyle\int\int
d_{\theta}^{\rho}(s,a)\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|\,da\,ds\leq\frac{\alpha\gamma
L_{d}}{1-\gamma}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}}\int\int
d_{\theta}^{\rho}(s,a)\,ds\,da=\frac{\alpha\gamma
L_{d}}{1-\gamma}\left\lVert\eta\right\rVert^{\frac{\beta_{1}}{2}}.$

$\square$

###  A.3 Bounding Score Function

######  Lemma 4.

Under Assumption 1, the score function is bounded as

$\displaystyle\int\int
d_{\theta}^{\rho}(s,a)\left\lVert\psi_{\theta}(s,a)-\psi_{\theta+\eta}(s,a)\right\rVert\,ds\,da\leq
C_{\nu,2}\left\lVert\eta\right\rVert^{\beta_{2}},$

where the constants $C_{\nu,2},\beta_{2}$ are given in Assumption 1.

Proof: This follows from the second bound in Assumption 1.

$\begin{split}&\int\int
d_{\theta}^{\rho}(s,a)\left\lVert\psi_{\theta}(s,a)-\psi_{\theta+\eta}(s,a)\right\rVert\,da\,ds\leq
C_{\nu,2}\left\lVert\eta\right\rVert^{\beta_{2}}\int\int
d_{\theta}^{\rho}(s,a)\,da\,ds=C_{\nu,2}\left\lVert\eta\right\rVert^{\beta_{2}}.\end{split}$

$\square$

###  A.4 Weak Smoothness of Objective

We conclude by proving the weak smoothness property of the loss function.

######  Proposition 1.

For any $\theta,\eta\in\mathbb{R}^{d}$, $\nabla J(\theta)$ satisfies the
following smoothness property

$\displaystyle\left\lVert\nabla J(\theta)-\nabla
J(\theta+\eta)\right\rVert\leq\frac{L_{1}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{1}/4}+\frac{L_{2}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{2}},$

where $L_{1}=\frac{2\alpha
C_{\nu,1}^{1/4}\sqrt{\psi_{\infty}(1+C_{0}-\delta)}\left(\sqrt{\gamma}+\sqrt{D_{\infty}}\right)}{1-\delta}$
and $L_{2}=\alpha C_{\nu,2}$. Here $\gamma$ is the discount factor,
$\beta_{1},\beta_{2}$ are the smoothness coefficients defined in Assumption 1,
$D_{\infty}\triangleq\sup_{\theta_{1},\theta_{2}\in\Theta}\left\lVert\frac{d_{\theta_{1}}^{\rho}}{d_{\theta_{2}}^{\rho}}\right\rVert_{\infty}+1$
is a distribution mismatch coefficient, $C_{0},\delta$ are defined in
Assumption 3, $C_{\nu,1},C_{\nu,2}$ are defined in Assumption 1,
$\psi_{\infty}$ is defined in Assumption 2, and $\alpha$ is the bound on the
reward.

Proof: Decomposing $\nabla J(\theta)=\mathbb{E}_{(s,a)\sim
d_{\theta}^{\rho}}[Q_{\pi_{\theta}}(s,a)\psi_{\theta}(s,a)]$ and using the
triangle inequality and Jensen’s inequality, we get

$\displaystyle\left\lVert\nabla J(\theta)-\nabla J(\theta+\eta)\right\rVert$
$\displaystyle=\Bigl{\|}\int\int
Q_{\theta}(s,a)\psi_{\theta}(s,a)d^{\rho}_{\theta}(s,a)\,ds\,da$
$\displaystyle\qquad-\int\int
Q_{\theta+\eta}(s,a)\psi_{\theta+\eta}(s,a)d^{\rho}_{\theta+\eta}(s,a)\,ds\,da\Bigr{\|}$
$\displaystyle\leq\int\int\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta}(s,a)\right\rVert
d_{\theta}^{\rho}(s,a)\,ds\,da$
$\displaystyle\quad+\int\int\left|Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta}(s,a)-\psi_{\theta+\eta}(s,a)\right\rVert
d_{\theta}^{\rho}(s,a)\,ds\,da$
$\displaystyle\quad+\int\int\left|Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta+\eta}(s,a)\right\rVert\left|d_{\theta}^{\rho}(s,a)-d_{\theta+\eta}^{\rho}(s,a)\right|\,ds\,da.$

We handle each of these terms separately. For the first term,

$\displaystyle\int\int\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta}(s,a)\right\rVert
d_{\theta}^{\rho}(s,a)\,ds\,da$
$\displaystyle\qquad\leq\sqrt{\int\int\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|^{2}d_{\theta}^{\rho}(s,a)\,ds\,da}\times\sqrt{\int\int\left\lVert\psi_{\theta}(s,a)\right\rVert^{2}d_{\theta}^{\rho}(s,a)\,ds\,da}$
$\displaystyle\overset{(i)}{\leq}\sqrt{\frac{2\psi_{\infty}\alpha}{1-\gamma}\times\int\int\left|Q_{\theta}(s,a)-Q_{\theta+\eta}(s,a)\right|d_{\theta}^{\rho}(s,a)\,ds\,da}$
$\displaystyle\overset{(ii)}{\leq}\sqrt{2\psi_{\infty}\frac{\alpha
L_{Q}}{(1-\gamma)^{2}}\left\lVert\eta\right\rVert^{\beta_{1}/2}}=\frac{\sqrt{2\psi_{\infty}\alpha
L_{Q}}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{1}/4},$

where in $(i)$ we use Assumption 2 and that $\left\lVert
Q_{\theta}\right\rVert_{\infty}\leq\frac{\alpha}{1-\gamma}$ by boundedness of
the reward for any $\theta$, and in $(ii)$ we use Lemma 3. For the second
term, we use

$\displaystyle\int\int\left|Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta}(s,a)-\psi_{\theta+\eta}(s,a)\right\rVert
d_{\theta}^{\rho}(s,a)\,ds\,da$ $\displaystyle\qquad\leq\left\lVert
Q_{\theta+\eta}\right\rVert_{\infty}\int\int
d_{\theta}^{\rho}(s,a)\left\lVert\psi_{\theta}(s,a)-\psi_{\theta+\eta}(s,a)\right\rVert\,ds\,da$
$\displaystyle\qquad\leq\frac{\alpha
C_{\nu,2}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{2}}.$

For the final term, we get

$\displaystyle\int\int\left|Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta+\eta}(s,a)\right\rVert\left|d_{\theta}^{\rho}(s,a)-d_{\theta+\eta}^{\rho}(s,a)\right|\,ds\,da$
$\displaystyle\qquad\leq\int\int\left|Q_{\theta+\eta}(s,a)\right|\left\lVert\psi_{\theta+\eta}(s,a)\right\rVert\left|\frac{d_{\theta}^{\rho}(s,a)}{d_{\theta+\eta}^{\rho}(s,a)}-1\right|d_{\theta+\eta}^{\rho}(s,a)\,ds\,da$
$\displaystyle\qquad\leq\left\lVert
Q_{\theta+\eta}\right\rVert_{\infty}\sqrt{\int\int\left\lVert\psi_{\theta+\eta}(s,a)\right\rVert^{2}d_{\theta+\eta}^{\rho}(s,a)\,ds\,da}\times\sqrt{\int\int\left|\frac{d_{\theta}^{\rho}(s,a)}{d_{\theta+\eta}^{\rho}(s,a)}-1\right|^{2}d_{\theta+\eta}^{\rho}(s,a)\,ds\,da}$
$\displaystyle\qquad\leq\frac{\sqrt{\psi_{\infty}}\alpha}{1-\gamma}\sqrt{\left\lVert\frac{d_{\theta}^{\rho}(s,a)}{d_{\theta+\eta}^{\rho}(s,a)}\right\rVert_{\infty}+1}\times\sqrt{\int\int\left|d_{\theta}^{\rho}(s,a)-d_{\theta+\eta}^{\rho}(s,a)\right|\,ds\,da}$
$\displaystyle\qquad\leq\frac{\sqrt{D_{\infty}\psi_{\infty}L_{d}}\alpha}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{1}/4},$

where we denote
$D_{\infty}\triangleq\sup_{\theta_{1},\theta_{2}\in\Theta}\left\lVert\frac{d_{\theta_{1}}^{\rho}}{d_{\theta_{2}}^{\rho}}\right\rVert_{\infty}+1$
as the distribution mismatch coefficient.

Putting all of this together, we get a final bound of:

$\begin{split}\left\lVert\nabla J(\theta)-\nabla
J(\theta+\eta)\right\rVert&\leq\frac{\sqrt{2\psi_{\infty}\alpha
L_{Q}}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{1}/4}+\frac{\alpha
C_{\nu,2}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{2}}+\frac{\sqrt{D_{\infty}\psi_{\infty}L_{d}}\alpha}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{1}/4}\\\
&\leq\frac{L_{1}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{1}/4}+\frac{L_{2}}{1-\gamma}\left\lVert\eta\right\rVert^{\beta_{2}}.\end{split}$

$\square$

Remarks: Note that the applications of Cauchy-Schwarz are not necessary if we
simply assume that $\left\lVert\psi_{\theta}\right\rVert$ is bounded almost
surely. Consequently we can retain the smoothness parameters $\beta_{1}/2$.
This fact is noted in the main text. Furthermore, we will no longer need to
bound the distribution mismatch coefficient, and instead we can directly apply
Lemma 2. Thus we obtain in the case $\beta_{1}=2,\beta_{2}=1$ a bound of the
form $\left\lVert\nabla J(\theta)-\nabla
J(\theta+\eta)\right\rVert\leq\frac{L}{1-\gamma}\left\lVert\eta\right\rVert$
for some $L$ not dependent on $\gamma,\theta,\eta$, which is a standard result
(see e.g. [XWL20, Proposition 1]).

##  Appendix B Theorem 1

Proof of Theorem 1: We divide the analysis into the one for vanilla policy
gradient, and the one for natural policy gradient respectively. Note that
unless otherwise specified the expectations will be taken with respect to all
randomness in the optimization procedure.

First, we show a lemma that $v_{t,i}$ in Algorithms 1-2 is an unbiased
estimator for $Q$, which we adapt the following Lemma from [Zha+20a, Theorem
3.4].

######  Lemma 5.

The sampler for $Q$ is unbiased, i.e. for all $t,i$,

$\displaystyle\mathbb{E}\left[v_{t,i}\mid
s_{t,i}=s,a_{t,i}=a\right]=Q_{\theta_{t-1}}(s,a).$

###### Proof.

Let $h$ be distributed on $\mathbb{N}$ as $\text{Geom}(1-\gamma^{1/2})$, and
$j\sim\text{Geom}(1-\gamma)$. Then we can write the following

$\displaystyle\mathbb{E}\left[\sum_{u=m}^{m+h}\gamma^{(u-m)/2}r_{u}\mid
j=m,s_{m}=s,a_{m}=a\right]$
$\displaystyle=\mathbb{E}\left[\sum_{k=0}^{\infty}\text{Pr}(h=k)\sum_{u=m}^{m+k}\gamma^{(u-m)/2}r_{u}\mid
j=m,s_{m}=s,a_{m}=a\right]$
$\displaystyle=\mathbb{E}\left[\sum_{u=m}^{\infty}\text{Pr}(h\geq
u-m)\gamma^{(u-m)/2}r_{u}\mid j=m,s_{m}=s,a_{m}=a\right]$
$\displaystyle=\sum_{u=m}^{\infty}\mathbb{E}\left[\text{Pr}(h\geq
u-m)\gamma^{(u-m)/2}r_{u}\mid j=m,s_{m}=s,a_{m}=a\right]$
$\displaystyle\overset{(i)}{=}\sum_{u=m}^{\infty}\mathbb{E}\left[\gamma^{u-m}r_{u}\mid
j=m,s_{m}=s,a_{m}=a\right]$ $\displaystyle=Q_{\theta_{t-1}}(s,a),$

where in $(i)$ we use that $h\sim\text{Geom}(1-\gamma^{1/2}).$ Finally, taking
the conditional expectation on $j$ of both sides and using that $Q$ does not
depend on $m$ completes the proof. ∎

To control the noise, we introduce the following basic lemma on the variance
of (one-dimensional) random variables:

######  Lemma 6.

Let $X,Y$ be two random variables. Then if
$\mathsf{Var}(XY)=\mathbb{E}\left[(XY-\mathbb{E}\left[XY\right])^{2}\right]$
and $|Y|\leq C$ almost surely,

$\mathsf{Var}(XY)\leq 2C^{2}\mathbb{E}\left[X^{2}\right].$

###### Proof.

$\displaystyle\mathsf{Var}(XY)$
$\displaystyle\leq\mathbb{E}\left[(XY)^{2}\right]+\mathbb{E}\left[\left|XY\right|\right]^{2}$
$\displaystyle\leq
C^{2}\mathbb{E}\left[X^{2}\right]+C^{2}\mathbb{E}\left[\left|X\right|\right]^{2}$
$\displaystyle\leq 2C^{2}\mathbb{E}\left[X^{2}\right],$

where in the last step we use Jensen’s inequality on the second term. ∎

Finally, we can show the following lemma concerning the gradient:

######  Lemma 7.

(Variance of Minibatch Policy Gradient) Consider the noise term

$\displaystyle
e_{t}=\frac{1}{B}\sum_{i=1}^{B}v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})-g_{t},$
(14)

where $s_{t,i},a_{t,i}$ are i.i.d. sampled from $d_{\theta_{t-1}}^{\rho}$. We
show that its variance is finite:

$\mathbb{E}\left[\left\lVert
e_{t}\right\rVert^{2}\right]\leq\frac{\sigma^{2}}{(1-\gamma)^{2}B},$

where $\sigma=3\alpha\sqrt{\psi_{\infty}}$ is a positive constant controlled
by the maximum reward $\alpha$ and the integrability constant $\psi_{\infty}$
from Assumption 2.

###### Proof.

First let us analyze a single sampled gradient, and take the conditional
expectation with $\theta_{t-1}$. Applying Lemma 6 to each component and noting
that $s_{t,i},a_{t,i}\sim d^{\rho}_{\theta_{t-1}}$,

$\begin{split}\mathbb{E}\left[\left\lVert
g_{t}-v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})\right\rVert^{2}|\
\theta_{t-1}\right]&\leq\frac{8\alpha^{2}}{(1-\gamma)^{2}}\mathbb{E}_{s,a\sim
d_{\theta_{t-1}}^{\rho}}\left[\left\lVert\psi_{\theta_{t-1}}(s,a)\right\rVert^{2}\mid\theta_{t-1}\right]\\\
&\overset{(i)}{\leq}\frac{8\alpha^{2}\psi_{\infty}}{(1-\gamma)^{2}},\end{split}$

where in $(i)$ we use Assumption 2. Then, since the samples
$v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})$ are i.i.d., when analyzing the
variance of the sum we are left with

$\displaystyle\mathbb{E}\left[\left\lVert
g_{t}-\frac{1}{B}\sum_{i=1}^{B}v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})\right\rVert^{2}\bigg{|}\
\theta_{t-1}\right]$
$\displaystyle\leq\frac{8\alpha^{2}\psi_{\infty}}{(1-\gamma)^{2}B}.$

Taking another expectation with respect to $\theta_{t-1}$ concludes the proof.

∎

Remarks: The analysis is much simpler if we assume that
$\left\lVert\psi_{\theta}(s,a)\right\rVert_{\infty}<\infty$; in that case, the
quantity $\left\lVert v_{t,i}\psi_{\theta_{t}}(s_{t,i},a_{t,i})\right\rVert$
is bounded almost surely.

Thus the error terms have variance $\mathbb{E}\left[\left\lVert
e_{t}\right\rVert^{2}\right]\leq\frac{\sigma^{2}}{(1-\gamma)^{2}B}$, and
$\mathbb{E}\left[\left\lVert
e_{t}\right\rVert^{c+1}\right]\leq\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{c+1}$
by Jensen’s inequality for any $c\in[0,1]$.

###  B.1 Policy Gradient

We first analyze the vanilla policy gradient. For convenience and brevity, let
$g_{t}=\nabla_{\theta}J(\theta_{t-1})$ be shorthand for the exact gradient at
time $t$, and
$e_{t}=\frac{1}{B}\sum_{i=1}^{B}v_{t,i}\psi_{\theta_{t-1}}(s_{t,i},a_{t,i})-g_{t}$
as the error from the sampled gradient, where $v_{t,i},s_{t,i},a_{t,i}$ are
the sampled estimates from Algorithm 1. From [Aga+20, Algorithm 1], we know
that $s_{t,i},a_{t,i}$ are sampled from $d_{\theta}^{\rho}$ and $v_{t,i}$ is
an unbiased estimate of $Q_{\theta}(s_{t,i},a_{t,i})$. Consequently,
$\mathbb{E}\left[e_{t}\right]=0$, where the expectation is over all randomness
in the sampling process.

Following Proposition 1, we know that the target function $J(\theta)$
satisfies a smoothness condition, i.e. $\left\lVert\nabla J(\theta)-\nabla
J(\theta+\eta)\right\rVert\leq\frac{1}{1-\gamma}\left(L_{1}\left\lVert\eta\right\rVert^{\beta_{1}/4}+L_{2}\left\lVert\eta\right\rVert^{\beta_{2}}\right)$.
We know from our algorithm that $\theta_{t}-\theta_{t-1}=h_{t}(g_{t}+e_{t})$.
Thus we apply mean value theorem to get:

$\begin{split}&\left|J(\theta_{t})-J(\theta_{t-1})-\left\langle
g_{t},h_{t}(g_{t}+e_{t})\right\rangle\right|\\\
&\qquad=\left|\int_{0}^{1}\left\langle\nabla J(\theta_{t-1}+\tau
h_{t}(g_{t}+e_{t}))-g_{t},h_{t}(g_{t}+e_{t})\right\rangle d\tau\right|\\\
&\qquad\leq\left\lVert h_{t}(g_{t}+e_{t})\right\rVert\int_{0}^{1}\left|\nabla
J(\theta_{t-1}+\tau h_{t}(g_{t}+e_{t}))-g_{t}\right|d\tau\\\
&\qquad\leq\frac{1}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert\left(L_{1}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\frac{\beta_{1}}{4}}\int\tau^{\frac{\beta_{1}}{4}}d\tau+L_{2}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\beta_{2}}\int\tau^{\beta_{2}}d\tau\right)\\\
&\qquad\leq\frac{L_{1}}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\frac{\beta_{1}}{4}+1}+\frac{L_{2}}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\beta_{2}+1}.\end{split}$

Consequently the following holds,

$\begin{split}J(\theta_{t})&\geq J(\theta_{t-1})+\left\langle
h_{t}(g_{t}+e_{t}),g_{t}\right\rangle-\frac{L_{1}}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\frac{\beta_{1}}{4}+1}-\frac{L_{2}}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\beta_{2}+1}\\\ &\geq
J(\theta_{t-1})+h_{t}\left\lVert g_{t}\right\rVert^{2}+h_{t}\left\langle
e_{t},g_{t}\right\rangle-\frac{L_{1}}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\frac{\beta_{1}}{4}+1}-\frac{L_{2}}{1-\gamma}\left\lVert
h_{t}(g_{t}+e_{t})\right\rVert^{\beta_{2}+1}\\\ &\geq
J(\theta_{t-1})+h_{t}\left\lVert g_{t}\right\rVert^{2}+h_{t}\left\langle
e_{t},g_{t}\right\rangle-\frac{2L_{1}}{1-\gamma}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}+\left\lVert
e_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right)\\\
&\qquad-\frac{2L_{2}}{1-\gamma}h_{t}^{\beta_{2}+1}\left(\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}+\left\lVert
e_{t}\right\rVert^{\beta_{2}+1}\right).\end{split}$

Rearranging and taking expectation, we get

$\displaystyle h_{t}\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[J(\theta_{t})-J(\theta_{t-1})\right]+\frac{2L_{1}}{1-\gamma}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right]+\mathbb{E}\left[\left\lVert
e_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right]\right)$
$\displaystyle\qquad+\frac{2L_{2}}{1-\gamma}h_{t}^{\beta_{2}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]+\mathbb{E}\left[\left\lVert
e_{t}\right\rVert^{\beta_{2}+1}\right]\right).$

Then, we can substitute our bound and apply Jensen’s inequality to obtain

$\displaystyle h_{t}\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[J(\theta_{t})-J(\theta_{t-1})\right]+\frac{2L_{1}}{1-\gamma}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}\right)$
$\displaystyle\qquad+\frac{2L_{2}}{1-\gamma}h_{t}^{\beta_{2}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}\right)$
$\displaystyle\leq\mathbb{E}\left[J(\theta_{t})-J(\theta_{t-1})\right]+\frac{2(L_{1}+L_{2})}{1-\gamma}\Biggl{(}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}\right)$
$\displaystyle\qquad+h_{t}^{\beta_{2}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}\right)\Biggr{)}.$

Summing this from $t=1\ldots T$, and using that $J_{*}$ is the supremum of
$J$, concludes the proof with $C_{PG,1}=1$ and $C_{PG,2}=2(L_{1}+L_{2})$ for
policy gradient. $\square$

Proof of Corollary 1, PG:

Learning Rate II: Now consider the learning rate, $h_{t}=\lambda
T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$, when $\beta_{0}\neq 1$. (For the case
$\beta_{0}=1$, see the constant step-size analysis below). In that case, we
get the following bound of convergence, using that $\lambda\leq 1$ and
$T^{\beta_{0}-1}\leq 1$

$\displaystyle h_{t}\left\lVert
g_{t}\right\rVert^{2}-\frac{2(L_{1}+L_{2})}{1-\gamma}\left(h_{t}^{\frac{\beta_{1}}{4}+1}\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}+h_{t}^{\beta_{2}+1}\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right)$ $\displaystyle\geq\lambda
T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{2}-\frac{2(L_{1}+L_{2})\lambda^{\beta_{0}+1}}{1-\gamma}T^{\beta_{0}-1}\left(\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}+\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right)$ $\displaystyle=\lambda
T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{2(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}(1+\left\lVert
g_{t}\right\rVert^{\beta_{max}-\beta_{0}})\right)$ $\displaystyle\geq\lambda
T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\right).$

The last step follows since if $\left\lVert g_{t}\right\rVert\geq 1$,
$\frac{2(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{\beta_{max}-\beta_{0}}\leq\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}$ as long as
$\lambda^{-\beta_{0}}\geq\frac{4(L_{1}+L_{2})}{1-\gamma}$, and if $\left\lVert
g_{t}\right\rVert<1$ then $\left\lVert
g_{t}\right\rVert^{\beta_{max}-\beta_{0}}<1$ as well.

Now consider the following cases: either $\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}\geq\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1+\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}$,
in which case the following holds:

$\displaystyle\lambda T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\right)\geq\frac{\lambda}{4}T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{2},$

or $\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}<\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{\beta_{0}+1}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}$,
in which case we have the following:

$\displaystyle\lambda T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\right)$
$\displaystyle\geq\frac{\lambda}{2}T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{2}-\left(\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\right)^{\frac{\beta_{0}+1}{1-\beta_{0}}}\left(\frac{4(L_{1}+L_{2})\lambda^{\beta_{0}+1}}{1-\gamma}T^{\beta_{0}-1}\right)$
$\displaystyle\geq\frac{\lambda}{2}T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{2}-\frac{\lambda}{4}T^{-1},$

if we choose $\lambda^{-\beta_{0}}\geq\frac{16(L_{1}+L_{2})}{1-\gamma}$. In
either case, we can use the worst case bound

$\displaystyle\frac{\lambda}{4}T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\left\lVert
g_{t}\right\rVert^{2}-\frac{\lambda}{4}T^{-1}.$

Thus, if $B\geq\sigma^{2}(1-\gamma)^{-2}$, this implies the following
inequality:

$\displaystyle\sum_{t=1}^{T}\frac{\lambda}{4}T^{\frac{\beta_{0}-1}{\beta_{0}+1}}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$ $\displaystyle\leq
J_{*}-J(\theta_{0})+\frac{\lambda}{4}+\frac{4(L_{1}+L_{2})\lambda^{\beta_{0}+1}}{1-\gamma}T^{\beta_{0}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}.$

After rearranging, we get

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$
$\displaystyle\leq\frac{4}{\lambda}T^{-\frac{2\beta_{0}}{\beta_{0}+1}}\left(J_{*}-J(\theta_{0})+\frac{\lambda}{4}\right)$
$\displaystyle\qquad+T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}.$

Learning Rate I: Now consider the time-independent learning rate,
$h_{t}=\lambda$ for some $\lambda>0$. We follow the same steps as for the
previous learning rate, only briefly sketching the argument below. Under the
same assumption that $\lambda^{-\beta_{0}}\geq\frac{4(L_{1}+L_{2})}{1-\gamma}$

$\displaystyle h_{t}\left\lVert
g_{t}\right\rVert^{2}-\frac{2(L_{1}+L_{2})}{1-\gamma}\left(h_{t}^{\frac{\beta_{1}}{4}+1}\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}+h_{t}^{\beta_{2}+1}\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right)$ $\displaystyle\geq\lambda\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}\right).$

Consequently, we can divide our analysis into the following cases: either
$\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}\geq\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}$
or $\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}<\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}$.
By analogy to the previous analysis, in the first case we get

$\displaystyle\lambda\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}\right)$
$\displaystyle\geq\frac{\lambda}{4}\left\lVert g_{t}\right\rVert^{2}$

i

$\displaystyle\lambda\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}\right)$
$\displaystyle\geq\frac{\lambda}{2}\left\lVert
g_{t}\right\rVert^{2}-\left(\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}\right)^{\frac{\beta_{0}+1}{1-\beta_{0}}}\left(\frac{4(L_{1}+L_{2})\lambda^{\beta_{0}+1}}{1-\gamma}\right)$
$\displaystyle\geq\frac{\lambda}{2}\left\lVert
g_{t}\right\rVert^{2}-4^{\frac{3+\beta_{0}}{1-\beta_{0}}}\left(\frac{L_{1}+L_{2}}{1-\gamma}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{\beta_{0}+1}{1-\beta_{0}}},$

with a resulting bound

$\displaystyle\lambda\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}\right)\geq\frac{\lambda}{4}\left\lVert
g_{t}\right\rVert^{2}-4^{\frac{3+\beta_{0}}{1-\beta_{0}}}\left(\frac{L_{1}+L_{2}}{1-\gamma}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{\beta_{0}+1}{1-\beta_{0}}},$

which holds in both cases. This yields for the final bound if
$B\geq\frac{\sigma^{2}}{(1-\gamma)^{2}}$

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$ $\displaystyle\leq\frac{4}{\lambda
T}\left(J_{*}-J(\theta_{0})\right)+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}+2^{\frac{8}{1-\beta_{0}}}\left(\frac{L_{1}+L_{2}}{1-\gamma}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{2\beta_{0}}{1-\beta_{0}}}.$

This results in a bias term that cannot be removed by minibatching, but can be
shrunk with an appropriate choice of $\lambda$ small.

Learning Rate III: We can generalize our analysis to a decaying learning rate
$h_{t}=\lambda t^{-q}$ for $q\in[0,1)$. We again follow the same steps as for
the previous learning rate, only briefly sketching the argument below. Again
we derive under the same condition
$\lambda^{-\beta_{0}}\geq\frac{2(L_{1}+L_{2})}{1-\gamma}$ that

$\displaystyle h_{t}\left\lVert
g_{t}\right\rVert^{2}-\frac{2(L_{1}+L_{2})}{1-\gamma}\left(h_{t}^{\frac{\beta_{1}}{4}+1}\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}+h_{t}^{\beta_{2}+1}\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right)$ $\displaystyle\qquad\geq\lambda
t^{-q}\left\lVert g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}t^{-q\beta_{0}}\right).$

Dividing again into the two cases: either $\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}\geq\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}t^{-q\beta_{0}}$
or $\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}<\frac{16(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}t^{-q\beta_{0}}$,
with a resulting bound of

$\displaystyle\lambda t^{-q}\left\lVert
g_{t}\right\rVert^{\beta_{0}+1}\left(\frac{1}{2}\left\lVert
g_{t}\right\rVert^{1-\beta_{0}}-\frac{4(L_{1}+L_{2})\lambda^{\beta}_{0}}{1-\gamma}t^{-q\beta_{0}}\right)\geq\frac{\lambda}{4}t^{-q}\left\lVert
g_{t}\right\rVert^{2}-\frac{\lambda}{4}t^{\frac{-q\beta_{0}-q}{1-\beta_{0}}},$

which holds in both cases if
$\lambda^{-\beta_{0}}\geq\frac{16(L_{1}+L_{2})}{1-\gamma}$. Consequently,
noting that $\sum_{t=1}^{T}t^{-p}\leq\frac{T^{1-p}}{1-p}$ for $p\in[0,1)$ and
using $B\geq\sigma^{2}(1-\gamma)^{-2}$

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$ $\displaystyle\leq\frac{4}{\lambda
T^{1-q}}\left(J_{*}-J(\theta_{0})\right)+\frac{1-\beta_{0}}{1-2q\beta_{0}-\beta_{0}}T^{\frac{-2q\beta_{0}}{1-\beta_{0}}}$
$\displaystyle\qquad+\frac{1}{1-q\beta_{0}}T^{-q\beta_{0}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1},$

as long as the exponent $q<\frac{1-\beta_{0}}{2\beta_{0}}$. If instead
$q\geq\frac{1-\beta_{0}}{2\beta_{0}}$, we use simply $\sum_{t=1}^{T}t^{p}\leq
4\ln T$ for $p\leq 1$ to get

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$ $\displaystyle\leq\frac{4}{\lambda
T^{1-q}}\left(J_{*}-J(\theta_{0})\right)+\frac{4\ln
T}{T}+\frac{1}{1-q\beta_{0}}T^{-q\beta_{0}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}.$

Note here that the first term is dominant for all $q<1$.

$\square$

We can also note that $\min_{t\leq T}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{p}\right]\leq\frac{1}{T}\sum_{t\leq
T}\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{p}\right]$ for any power $p$,
which allows us to bound the minimum gradient for $t\leq T$ as well.

###  B.2 Natural Policy Gradient

Facts: Assumption 2 also guarantees that the Fisher information matrix
$K(\theta)=\mathbb{E}\left[\psi_{\theta}(s,a)\psi_{\theta}(s,a)^{T}\right]$
has bounded norm, since by the trace inequality

$\displaystyle\left\lVert K(\theta)\right\rVert$
$\displaystyle=\left\lVert\int\int\psi_{\theta}(s,a)\psi_{\theta}(s,a)^{\top}d_{\theta}^{\rho}(s,a)\,da\,ds\right\rVert$
$\displaystyle\leq\int\int\left\lVert\psi_{\theta}(s,a)\psi_{\theta}(s,a)^{\top}\right\rVert
d_{\theta}^{\rho}(s,a)\,da\,ds$
$\displaystyle\overset{}{\leq}\int\int\left\lVert\psi_{\theta}(s,a)\right\rVert^{2}d_{\theta}^{\rho}(s,a)\,da\,ds\leq\psi_{\infty}.$

This will be important when analyzing the NPG algorithm. Likewise, by the
triangle inequality and the i.i.d. sampling,

$\displaystyle\mathbb{E}\left[\left\lVert
K_{t}\right\rVert|\theta_{t-1}\right]$
$\displaystyle\overset{}{=}\mathbb{E}\left[\left\lVert\frac{1}{B}\sum_{i=1}^{B}\psi_{\theta_{t-1}}(s^{\prime}_{t,i},a^{\prime}_{t,i})\psi_{\theta_{t-1}}(s^{\prime}_{t,i},a^{\prime}_{t,i})^{\top}\right\rVert\Bigg{|}\theta_{t-1}\right]$
$\displaystyle\leq\frac{1}{B}\sum_{i=1}^{B}\mathbb{E}_{s,a\sim
d_{\theta_{t-1}}^{\rho}}\left[\left\lVert\psi_{\theta_{t-1}}(s,a)\psi_{\theta_{t-1}}(s,a)^{\top}\right\rVert\right]$
$\displaystyle\leq\psi_{\infty}.$

Proof for Theorem 1, NPG: We now perform the same analysis for the exact
natural policy gradient, applying mean value theorem and Proposition 1 to get

$\displaystyle J(\theta_{t})$ $\displaystyle\geq J(\theta_{t-1})+\left\langle
g_{t},h_{t}(K_{t}+\xi
I)^{-1}(g_{t}+e_{t})\right\rangle-\frac{L_{1}}{1-\gamma}\left\lVert
h_{t}(K_{t}+\xi I)^{-1}(g_{t}+e_{t})\right\rVert^{\frac{\beta_{1}}{4}+1}$
$\displaystyle\qquad-\frac{L_{2}}{1-\gamma}\left\lVert h_{t}(K_{t}+\xi
I)^{-1}(g_{t}+e_{t})\right\rVert^{\beta_{2}+1}$
$\displaystyle=J(\theta_{t-1})+\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}g_{t}\right\rangle+\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}e_{t}\right\rangle$
$\displaystyle\qquad-\frac{L_{1}}{1-\gamma}\left\lVert h_{t}(K_{t}+\xi
I)^{-1}(g_{t}+e_{t})\right\rVert^{\frac{\beta_{1}}{4}+1}-\frac{L_{2}}{1-\gamma}\left\lVert
h_{t}(K_{t}+\xi I)^{-1}(g_{t}+e_{t})\right\rVert^{\beta_{2}+1}$
$\displaystyle{\geq}J(\theta_{t-1})+\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}g_{t}\right\rangle+\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}e_{t}\right\rangle$
$\displaystyle\qquad-\frac{L_{1}}{(1-\gamma)\xi^{\frac{\beta_{1}}{4}+1}}h_{t}^{\frac{\beta_{1}}{4}+1}\left\lVert
g_{t}+e_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}-\frac{L_{2}}{(1-\gamma)\xi^{\beta_{2}+1}}h_{t}^{\beta_{2}+1}\left\lVert
g_{t}+e_{t}\right\rVert^{\beta_{2}+1}$
$\displaystyle{\geq}J(\theta_{t-1})+\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}g_{t}\right\rangle+\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}e_{t}\right\rangle$
$\displaystyle\qquad-\frac{2L_{1}}{(1-\gamma)\xi^{\frac{\beta_{1}}{4}+1}}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}+\left\lVert
e_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right)-\frac{2L_{2}}{(1-\gamma)\xi^{\beta_{2}+1}}h_{t}^{\beta_{2}+1}\left(\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}+\left\lVert
e_{t}\right\rVert^{\beta_{2}+1}\right).$

This is entirely analogous to the standard policy gradient case, except for
the terms $(K(\theta_{t-1})+\xi I)$ which appears from the natural policy
gradient.

Finally, we take expectation. First,

$\displaystyle\mathbb{E}\left[\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}g_{t}\right\rangle\right]$ $\displaystyle=\mathbb{E}\left[\left\langle
g_{t},h_{t}(K_{t}+\xi I)^{-1}g_{t}\right\rangle\right]$
$\displaystyle\overset{(i)}{\geq}\mathbb{E}\left[\mathbb{E}\left[\frac{1}{\left\lVert
K_{t}\right\rVert+\xi}\Big{|}\theta_{t-1}\right]\left\langle
g_{t},h_{t}g_{t}\right\rangle\right]$
$\displaystyle\overset{(ii)}{\geq}h_{t}\mathbb{E}\left[\mathbb{E}\left[\left\lVert
K_{t}\right\rVert+\xi\Big{|}\theta_{t-1}\right]^{-1}\left\lVert
g_{t}\right\rVert^{2}\right]$
$\displaystyle\overset{(iii)}{\geq}h_{t}(\psi_{\infty}+\xi)^{-1}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right],$

where in $(i)$ we use that the minimum eigenvalue of $(K_{t}+\xi I)^{-1}$ is
lower bounded by $\frac{1}{\left\lVert K_{t}\right\rVert+\xi}$. In $(ii)$ we
use the fact that for any positive random variable $X$,
$\mathbb{E}\left[1/X\right]\geq\mathbb{E}\left[X\right]^{-1}$ by Jensen’s
inequality, and in $(iii)$ we use our bound on $\mathbb{E}\left[\left\lVert
K_{t}\right\rVert\right]$.

Secondly, we note the following

$\displaystyle\mathbb{E}\left[h_{t}\left\langle g_{t},h_{t}(K_{t}+\xi
I)^{-1}e_{t}\right\rangle\right]$ $\displaystyle=\mathbb{E}\left[\left\langle
g_{t},h_{t}\mathbb{E}\left[(K_{t}+\xi)^{-1}e_{t}\Big{|}\theta_{t-1}\right]\right\rangle\right]=0,$

since $K_{t}$ is independent of $e_{t}$ given $\theta_{t-1}$ from our sampling
procedure, and $e_{t}$ has zero expectation given $\theta_{t-1}$, where again
the inner expectation is on the randomness in the sampling procedure at
iteration $t$, and the outer expectation is with respect to the random
variable $\theta_{t-1}$.

Finally, this yields for $\xi<1$

$\displaystyle h_{t}\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{2}\right]$
$\displaystyle\leq(\psi_{\infty}+\xi)\mathbb{E}\left[J(\theta_{t})-J(\theta_{t-1})\right]+\frac{2L_{1}(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}h_{t}^{\frac{\beta_{1}}{4}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}\right)$
$\displaystyle\qquad+\frac{2L_{2}(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}h_{t}^{\beta_{2}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}\right).$

Summing from $t=1\ldots T$, and bounding $J(\theta_{t})$ with $J_{*}$
completes the proof, if we take,

$C_{NPG,1}=(\psi_{\infty}+\xi),\qquad
C_{NPG,2}=\frac{2(L_{1}+L_{2})(\psi_{\infty}+\xi)}{\xi^{\beta_{max}+1}}.$

$\square$

Proof of Corollary 1, NPG:

The proof techniques for generating the convergence rates are nearly identical
to policy gradient, except for the change in the constant term $C_{NPG}$. We
show the constant learning rate as an illustrative case:

Learning Rate I: Let $\lambda\leq 1$, then by Jensen’s inequality and that
$h_{t}\leq 1$

$\displaystyle h_{t}\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{2}\right]-$
$\displaystyle\frac{2(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\left(h_{t}^{\frac{\beta_{1}}{4}+1}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\frac{\beta_{1}}{4}+1}\right]+h_{t}^{\beta_{2}+1}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]\right)$ $\displaystyle\leq
h_{t}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]-\frac{2(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}h_{t}^{\beta_{0}+1}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{1}+4}{8}}+\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{2}+1}{2}}\right)$
$\displaystyle=\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{0}+1}{2}}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}-\frac{2(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}\left(1+\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{max}-\beta_{0}}{2}}\right)\right).$

Now either $\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{2}\right]\geq 1$,
in which case if
$\lambda^{-\beta_{0}}\geq\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}$,
then we can bound this by

$\displaystyle\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{0}+1}{2}}\left(\frac{1}{2}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}-\frac{2(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}\right),$

or $\mathbb{E}\left[\left\lVert g_{t}\right\rVert^{2}\right]<1$, in which case
the following bound suffices:

$\displaystyle\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{0}+1}{2}}\left(\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}-\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}\right).$

In both cases, we can lower bound the quantity with

$\displaystyle\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{0}+1}{2}}\left(\frac{1}{2}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}-\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}\right).$

Now again we split the analysis into two cases. If
$\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}\geq\frac{16(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}$,
in which case the following bound suffices:

$\displaystyle\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{0}+1}{2}}$
$\displaystyle\left(\frac{1}{2}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}-\frac{1}{4}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}\right)$
$\displaystyle\geq\frac{\lambda}{2}\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right].$

In the other case, when $\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}<\frac{16(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}$,
we get

$\displaystyle\lambda\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{\beta_{0}+1}{2}}$
$\displaystyle\left(\frac{1}{2}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]^{\frac{1-\beta_{0}}{2}}-\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}\right)$
$\displaystyle=\frac{\lambda}{2}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]-\left(\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta_{0}+1}\right)\left(\frac{16(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta}_{0}\right)^{\frac{\beta_{0}+1}{1-\beta_{0}}}$
$\displaystyle\overset{(i)}{\geq}\frac{\lambda}{2}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]-4^{\frac{3+\beta_{0}}{1-\beta_{0}}}\left(\frac{(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{\beta_{0}+1}{1-\beta_{0}}}.$

In either case the worst case bound

$\frac{\lambda}{4}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]-4^{\frac{3+\beta_{0}}{1-\beta_{0}}}\left(\frac{(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{\beta_{0}+1}{1-\beta_{0}}}$

suffices.

Plugging this into our earlier expression for $B\geq\sigma^{2}(1-\gamma)^{-2}$
and rearranging, using again that
$\lambda^{-\beta_{0}}\geq\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}$

$\displaystyle\frac{\lambda}{4}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$
$\displaystyle\leq(\psi_{\infty}+\xi)\mathbb{E}\left[J(\theta_{t})-J(\theta_{t-1})\right]+4^{\frac{3+\beta_{0}}{1-\beta_{0}}}\left(\frac{(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{\beta_{0}+1}{1-\beta_{0}}}$
$\displaystyle\qquad+\frac{4(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\lambda^{\beta_{0}+1}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}$
$\displaystyle\leq(\psi_{\infty}+\xi)\mathbb{E}\left[J(\theta_{t})-J(\theta_{t-1})\right]+4^{\frac{3+\beta_{0}}{1-\beta_{0}}}\left(\frac{(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{\beta_{0}+1}{1-\beta_{0}}}$
$\displaystyle\qquad+\frac{\lambda}{4}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}.$

It remains to average from $1\ldots T$ and use the supremum bound on $J$, to
get

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{2}\right]$
$\displaystyle\leq(\psi_{\infty}+\xi)(J_{*}-J(\theta_{0}))+2^{\frac{8}{1-\beta_{0}}}\left(\frac{(L_{1}+L_{2})(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{2\beta_{0}}{1-\beta_{0}}}$
$\displaystyle\qquad+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\frac{\beta_{1}}{4}+1}.$

As can be seen from this analysis, the only difference in our analysis from
the same learning rate in the policy gradient is that we manipulate the
expectations of the quantities, and the slight difference in constants. The
convergence rates for the other two learning rates follow from analogy to the
policy gradient case. $\square$

##  Appendix C Theorem 2

As with Theorem 1, we divide our analyze between policy gradient and natural
policy gradient. We will use the same notation as in the proof of Theorem 1.

###  C.1 Policy Gradient

Note that for standard policy gradient, the stationary points can in general
be highly sub-optimal, see [Aga+20]. Under a strong first order condition,
however, we can obtain some guarantees.

Consequently, we can use Assumption 4 to show the global optimality of our
algorithm for vanilla policy gradient.

Proof of Theorem 2, PG: This follows directly from Assumption 4, as we find
that for any $\theta_{*}$ that maximizes $J$:

$\displaystyle\min_{t=1,\ldots T}J(\theta_{*})-J(\theta_{t-1})$
$\displaystyle\leq\min_{t=1,\ldots
T}\frac{m\left\lVert\theta_{t-1}-\theta_{*}\right\rVert}{1-\gamma}\left\lVert
g_{t}\right\rVert$
$\displaystyle\leq\frac{m\text{Diam}(\Theta)}{(1-\gamma)}\min_{t=1,\ldots
T}\left\lVert g_{t}\right\rVert,$

since $g_{t}=\nabla J(\theta_{t-1})$. $\square$

To show the corollary, it remains to substitute the bounds for
$\min_{t=1,\ldots T}\left\lVert g_{t}\right\rVert$ that we obtain from
Corollary 1. When converted to a sample complexity bound, this yields the
final result.

Proof of Corollary 2, PG:

It remains now to substitute the learning rate and gradient bounds from each
of the cases we analyzed earlier; doing so obtains the rates found in the
corollary. In the sequel, $\lesssim$ and $\gtrsim$ only concern terms
depending on $\lambda,\epsilon,\gamma$.

Case I, $h_{t}=\lambda$: Recall that in this case,

$\displaystyle\min_{t\leq T}\left\lVert
g_{t}\right\rVert^{2}\leq\frac{4}{\lambda
T}\left(J_{*}-J(\theta_{0})\right)+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}+2^{\frac{8}{1-\beta_{0}}}\left(\frac{L_{1}+L_{2}}{1-\gamma}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{2\beta_{0}}{1-\beta_{0}}}.$

Subsequently, we can choose
$\lambda\lesssim(1-\gamma)^{\frac{2-\beta_{0}}{\beta_{0}}}\epsilon^{\frac{1-\beta_{0}}{\beta_{0}}}$,
so that the final term is $\lesssim\epsilon^{2}(1-\gamma)^{2}$. Note that this
choice does not conflict with our earlier constraints on $\lambda$ from
Corollary 1.

Subsequently we require $T\gtrsim\frac{1}{\lambda\epsilon^{2}(1-\gamma)^{2}}$
to make the first term $\lesssim(1-\gamma)^{2}\epsilon^{2}$ and
$B\gtrsim\epsilon^{-\frac{4}{\beta_{0}+1}}(1-\gamma)^{-2-\frac{4}{\beta_{0}+1}}$
to make the second term $\lesssim(1-\gamma)^{2}\epsilon^{2}$. Substituting our
requirement on $\lambda$, we get
$T\gtrsim\epsilon^{-\frac{1+\beta_{0}}{\beta_{0}}}(1-\gamma)^{-\frac{2+\beta_{0}}{\beta_{0}}}.$
Thus, we get $\min_{t\leq T}\left\lVert
g_{t}\right\rVert^{2}\lesssim(1-\gamma)^{2}\epsilon^{2}$. This then implies

$\displaystyle\min_{t\leq
T}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t-1})\right]\lesssim\epsilon.$

Case II, $h_{t}=\lambda T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$: Recall that in
this case,

$\min_{t\leq T}\left\lVert
g_{t}\right\rVert^{2}\leq\frac{4}{\lambda}T^{-\frac{2\beta_{0}}{\beta_{0}+1}}\left(J_{*}-J(\theta_{0})+\frac{\lambda}{4}\right)+T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}.$

Subsequently we require
$T\gtrsim\left(\frac{1}{\lambda\epsilon^{2}(1-\gamma)^{2}}\right)^{\frac{\beta_{0}+1}{2\beta_{0}}}$
to bound the first term by $\lesssim\epsilon^{2}(1-\gamma)^{2}$. For
simplicity, take $\lambda\asymp(1-\gamma)^{1/\beta_{0}}$, in which case we get
$T\gtrsim\left(\frac{1}{\epsilon^{2}(1-\gamma)^{2+{1/\beta_{0}}}}\right)^{\frac{\beta_{0}+1}{2\beta_{0}}}$.
Consequently, the second term is bounded by

$\displaystyle
T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}$
$\displaystyle\lesssim\left(\frac{1}{\epsilon^{2}(1-\gamma)^{2+1/\beta_{0}}}\right)^{\frac{\beta_{0}-1}{2}}\left(\frac{1}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}$
$\displaystyle\lesssim\epsilon^{1-\beta_{0}}(1-\gamma)^{-\frac{4\beta_{0}^{2}+\beta_{0}-1}{2\beta_{0}}}B^{-\frac{\beta_{0}+1}{2}}.$

So we can take
$B\gtrsim\epsilon^{-2}(1-\gamma)^{\frac{4\beta_{0}^{2}+5\beta_{0}-1}{\beta_{0}(\beta_{0}+1)}}$,
to make this term $\lesssim(1-\gamma)^{2}\epsilon^{2}$. This then implies

$\displaystyle\min_{t\leq
T}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t-1})\right]\lesssim\epsilon.$

$\square$

###  C.2 Natural Policy Gradient

First we show the following lemma:

######  Lemma 8.

For any $\theta\in\Theta$ and vector $x$, the following holds:

$\left\lVert(K(\theta_{t-1})+\xi
I)^{-1}x-K(\theta_{t-1})^{\dagger}x\right\rVert\leq C_{\xi}\left\lVert
x\right\rVert,$

where $C_{\xi}=\max(\zeta^{-1},\xi^{-1})>0$ and
$\zeta=\inf_{\theta}\min_{k:\lambda_{k}>0}\lambda_{k}(K(\theta))\geq 0$ is a
policy-dependent regularity constant, which measures the smallest non-zero
eigenvalue of $K(\theta)$ across all policies $\theta$.

Remarks: We adapt this from a similar result presented in [XWL20]. This lemma
is used to bound the stable inverse Fisher matrix $(K(\theta_{t})+\xi I)^{-1}$
from the unstable pseudo-inverse $K(\theta_{t})^{\dagger}$. Not only is the
computation of the inverse far simpler than computation of the pseudo-inverse,
but it will also be used to upper bound the rate of convergence. We can
rewrite the condition number $\zeta$ in terms of the condition number used in
[Aga+20], but this introduces unnecessary complexity for our purposes.

###### Proof.

Since $K(\theta)$ is real and symmetric, it is diagonalizable into
$U(\theta)^{\top}\Xi(\theta)U(\theta)$, where $U(\theta)=[u_{1},u_{2},\ldots
u_{d}]$ is the orthonormal space of eigenvectors (and appropriate basis for
the null-space) and $\Xi(\theta)=\text{diag}(\xi_{1},\ldots,\xi_{d})$ where
$\xi_{i}$ is the $i$-th eigenvalue (including zeroes). Thus we can write the
following:

$\begin{split}\left[K(\theta)+\xi
I\right]^{-1}x&=U(\theta)^{\top}(\Xi(\theta)^{-1}+\frac{1}{\xi}I)U(\theta)x,\\\
&=U(\theta)^{\top}\left[\frac{1}{\xi_{1}+\xi}\left\langle
u_{1},x\right\rangle,\frac{1}{\xi_{2}+\xi}\left\langle
u_{2},x\right\rangle\ldots\frac{1}{\xi_{d}+\xi}\left\langle
u_{d},x\right\rangle\right]^{\top}.\end{split}$

Analogously, the exact pseudo-inverse yields:

$\begin{split}K(\theta)^{\dagger}x&=U(\theta)^{\top}\Xi(\theta)^{\dagger}U(\theta)x\\\
&=U(\theta)^{\top}\left[\frac{1}{\xi_{1}}\left\langle
u_{1},x\right\rangle,\frac{1}{\xi_{2}}\left\langle
u_{2},x\right\rangle\ldots\frac{1}{\xi_{k}}\left\langle
u_{k},x\right\rangle,0\ldots 0\right]^{\top},\end{split}$

where $k$ is the rank of $K(\theta)$. Subsequently their difference is:

$\begin{split}&K(\theta+\xi I)^{-1}x-K(\theta)^{\dagger}x\\\ &\leq
U(\theta)^{\top}\left[\left(\frac{1}{\xi_{1}+\xi}-\frac{1}{\xi_{1}}\right)\left\langle
u_{1},x\right\rangle,\ldots\left(\frac{1}{\xi_{k}+\xi}-\frac{1}{\xi_{k}}\right)\left\langle
u_{k},x\right\rangle,\frac{1}{\xi}\left\langle
u_{k+1},x\right\rangle\ldots\frac{1}{\xi}\left\langle
u_{d},x\right\rangle\right]^{\top}\\\ &=-\xi
U(\theta)^{\top}\left[\left(\frac{1}{\xi_{1}(\xi_{1}+\xi)}\right)\left\langle
u_{1},x\right\rangle,\ldots\left(\frac{1}{\xi_{k}(\xi_{k}+\xi)}\right)\left\langle
u_{k},x\right\rangle,-\frac{1}{\xi^{2}}\left\langle
u_{k+1},x\right\rangle\ldots-\frac{1}{\xi^{2}}\left\langle
u_{d},x\right\rangle\right]^{\top}.\end{split}$

Since the information matrix is always positive semidefinite, we bound
$\xi_{1}+\xi\geq\xi_{k}+\xi\geq\xi$. Thus the norm is bounded:

$\begin{split}\left\lVert K(\theta+\xi
I)^{-1}x-K(\theta)^{\dagger}x\right\rVert&\leq\xi\left\lVert
U(\theta)^{\top}\right\rVert\max(\xi^{-2},\xi^{-1}\zeta^{-1})\left\lVert
x\right\rVert\\\ &\leq\max(\zeta^{-1},\xi^{-1})\left\lVert
x\right\rVert\triangleq C_{\xi}\left\lVert x\right\rVert,\end{split}$

where $\zeta$ is described in the lemma statement, and we use the fact that
$U$ is unitary. ∎

We adapt another Lemma without proof, to quantify the gap between any two
policies in a policy class.

######  Lemma 9.

(Performance Difference Lemma, Adapted from [Aga+20, Lemma 3.2]) For all
policies $\pi_{\theta_{1}},\pi_{\theta_{2}}$ and all initial distributions
$\rho$:

$J(\theta_{1})-J(\theta_{2})\triangleq\mathbb{E}_{s\sim\rho}\left[V_{\theta_{1}}(s)-V_{\theta_{2}}(s)\right]=\frac{1}{1-\gamma}\mathbb{E}_{s,a\sim
d_{\theta_{1}}^{\rho}}\left[A_{\theta_{2}}(s,a)\right].$

Proof of Theorem 2 for NPG: Consider a $\mathsf{KL}$ function on the policies
at each state:
$F(\theta,s)=\mathsf{KL}(\pi_{*}(\cdot|s),\pi_{\theta}(\cdot|s))\triangleq\int_{\mathcal{A}}\pi_{*}(a|s)\log\frac{\pi_{*}(a|s)}{\pi_{\theta}(a|s)}\,da$,
where $\pi_{*}\triangleq\pi_{\theta_{*}}$ is any policy that maximizes $J$.
Let $d_{*}^{\rho}$ be the visitation distribution measure induced by $\pi_{*}$
on $\mathcal{S}\times\mathcal{A}$, and let $H_{*}^{\rho}$ be the state
component of this distribution measure as in Appendix A. If we define
$F(\theta)=\mathbb{E}_{s\sim H_{*}^{\rho}}\left[F(\theta,s)\right]$, then

$\displaystyle F(\theta_{t})-F(\theta_{t-1})$
$\displaystyle\triangleq\mathbb{E}_{s\sim
H_{*}^{\rho}}\left[F(\theta_{t},s)-F(\theta_{t-1},s)\right]$
$\displaystyle=\mathbb{E}_{s\sim
H_{*}^{\rho}}\left[\int_{\mathcal{A}}\left(\log\frac{\pi_{*}(a|s)}{\pi_{\theta_{t}}(a|s)}-\log\frac{\pi_{*}(a|s)}{\pi_{\theta_{t-1}}(a|s)}\right)\pi_{*}(a|s)\,da\right]$
$\displaystyle=\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\log\pi_{\theta_{t-1}}(a|s)-\log\pi_{\theta_{t}}(a|s)\right]$
$\displaystyle\overset{(i)}{\geq}\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\nabla\log\pi_{\theta_{t-1}}(a|s)\right]^{\top}(\theta_{t}-\theta_{t-1})-C_{\nu,2}\left\lVert\theta_{t}-\theta_{t-1}\right\rVert^{\beta_{2}+1}$
$\displaystyle\triangleq\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(\theta_{t}-\theta_{t-1})-C_{\nu,2}\left\lVert\theta_{t}-\theta_{t-1}\right\rVert^{\beta_{2}+1},$

where in $(i)$ we use the Hölder-smoothness condition on
$\psi_{\theta}\triangleq\nabla\log\pi_{\theta}$ from Assumption 1. Let
$g_{t}+e_{t}$ be the exact and error components of the approximate gradient as
before. Concentrating on the first term, we can make use of the triangle
inequality to obtain the following:

$\displaystyle\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(\theta_{t}-\theta_{t-1})$
$\displaystyle=\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(h_{t}(K_{t}+\xi
I)^{-1}(g_{t}+e_{t}))$ $\displaystyle=\underbrace{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(h_{t}(K_{t}+\xi
I)^{-1}g_{t}-h_{t}(K(\theta_{t-1})+\xi I)^{-1}g_{t})}_{(a)}$
$\displaystyle\quad+\underbrace{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(h_{t}(K(\theta_{t-1})+\xi
I)^{-1}g_{t}-h_{t}K(\theta_{t-1})^{\dagger}g_{t})}_{(b)}$
$\displaystyle\quad+\underbrace{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)^{\top}h_{t}K(\theta_{t-1})^{\dagger}g_{t}-h_{t}A_{\theta_{t-1}}(s,a)\right]}_{(c)}+\underbrace{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[h_{t}A_{\theta_{t-1}}(s,a)\right]}_{(d)}$
$\displaystyle\quad+\underbrace{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(h_{t}(K_{t}+\xi
I)^{-1}e_{t})}_{(e)}.$

Briefly explaining the meaning of each of these: (a) represents the difference
between using the sampled Fisher matrix $K_{t}$ and the true matrix
$K(\theta_{t-1})$, while (b) represents the difference between the stabilized
matrix $(K+\xi I)^{-1}$ and the unstabilized matrix $K^{\dagger}$, (c) is used
to represent the difference between the natural gradient objective and the
true function, (d) represents the true objective, and (e) represents the error
due to the approximate gradient.

Consequently we bound each of these terms individually. We begin with $(b)$:

$\displaystyle(b):\quad\quad$ $\displaystyle\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(h_{t}(K(\theta_{t-1})+\xi
I)^{-1}g_{t}-h_{t}(K(\theta_{t-1})^{\dagger}g_{t})$
$\displaystyle\overset{}{\geq}-h_{t}\left\lVert\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]\right\rVert\left\lVert
K(\theta_{t-1})^{\dagger}g_{t}-(K(\theta_{t-1})+\xi I)^{-1}g_{t}\right\rVert$
$\displaystyle\overset{(i)}{\geq}-h_{t}C_{\xi}\sqrt{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\left\lVert\psi_{\theta_{t-1}}(s,a)\right\rVert^{2}\right]}\left\lVert
g_{t}\right\rVert$
$\displaystyle\overset{(ii)}{\geq}-h_{t}C_{\xi}\sqrt{\left\lVert\frac{d_{*}^{\rho}}{d_{\theta_{t-1}}^{\rho}}\right\rVert_{\infty}}\sqrt{\mathbb{E}_{s,a\sim
d_{\theta_{t-1}}^{\rho}}\left[\left\lVert\psi_{\theta_{t-1}}(s,a)\right\rVert^{2}\right]}\left\lVert
g_{t}\right\rVert$
$\displaystyle\overset{(iii)}{\geq}-h_{t}C_{\xi}\sqrt{D_{\infty}\psi_{\infty}}\left\lVert
g_{t}\right\rVert,$

where in $(i)$ we apply Lemma 8, and in $(ii)$ we change the measure from
$d_{*}^{\rho}$ to $d_{\theta_{t-1}}^{\rho}$ and use the Triangle inequality,
and in $(iii)$ we substitute the definition for $D_{\infty}$, and
$\psi_{\infty}$ as defined in Assumption 2. For $(a)$, we get:

$\displaystyle(a):\quad\quad$ $\displaystyle\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}(h_{t}(K_{t}+\xi
I)^{-1}g_{t}-h_{t}(K(\theta_{t-1})+\xi I)^{-1}g_{t})$
$\displaystyle\overset{(i)}{\geq}-h_{t}\left\lVert\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)\right]\right\rVert\left\lVert(K_{t}+\xi
I)^{-1}g_{t}-(K(\theta_{t-1})+\xi I)^{-1}g_{t}\right\rVert$
$\displaystyle\overset{(ii)}{\geq}-h_{t}\sqrt{D_{\infty}\psi_{\infty}}\left\lVert(K_{t}+\xi
I)^{-1}g_{t}-(K(\theta_{t-1})+\xi I)^{-1}g_{t}\right\rVert$
$\displaystyle\overset{(iii)}{\geq}-h_{t}\frac{2\sqrt{D_{\infty}\psi_{\infty}}}{\xi}\left\lVert
g_{t}\right\rVert,$

where in $(i)$ we use the Cauchy-Schwarz inequality, in $(ii)$ we again change
the measure and use Assumption 2, and in $(iii)$ we use the boundedness
$\left\lVert K_{t}+\xi I\right\rVert\geq\xi$, $\left\lVert K(\theta_{t-1})+\xi
I\right\rVert\geq\xi$. This term can be tightened but it will not change the
order of the resultant bound.

$\begin{split}(c):\quad\quad&\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\psi_{\theta_{t-1}}(s,a)^{\top}h_{t}K(\theta_{t-1})^{\dagger}g_{t}-h_{t}A_{\theta_{t-1}}(s,a)\right]\\\
&\geq-h_{t}\sqrt{\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\left(\psi_{\theta_{t-1}}(s,a)^{\top}K(\theta_{t-1})^{\dagger}g_{t}-A_{\theta_{t-1}}(s,a)\right)^{2}\right]}\\\
&\overset{(i)}{\geq}-h_{t}\sqrt{\left\lVert\frac{d_{*}^{\rho}}{d_{\theta_{t-1}}^{\rho}}\right\rVert_{\infty}}\sqrt{\mathbb{E}_{s,a\sim
d_{\theta_{t-1}}}\left[(\psi_{\theta_{t-1}}(s,a)^{\top}K(\theta_{t-1})^{\dagger}g_{t}-A_{\theta_{t-1}}(s,a))^{2}\right]}\\\
&\overset{(ii)}{\geq}-h_{t}\sqrt{D_{\infty}E_{\Pi}},\end{split}$

where in $(i)$ we substitute again the distribution mismatch coefficient, and
in $(ii)$ we substitute the condition number of the policy class:
$E_{\Pi}=\max_{\theta}\mathbb{E}_{s,a\sim
d_{\theta}^{\rho}}\left[\psi_{\theta}(s,a)^{\top}K(\theta)^{\dagger}\nabla
J(\theta)-A_{\theta}(s,a))^{2}\right]$.

$\begin{split}(d):\quad\quad\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[h_{t}A_{\theta_{t-1}}(s,a)\right]\overset{}{=}h_{t}(1-\gamma)(J(\theta_{*})-J(\theta_{t-1})),\end{split}$

by the performance difference lemma, Lemma 9. Lastly we recall that the noise
term is bounded by:

$\begin{split}(e):\mathbb{E}_{s,a\sim
d_{*}}\left[\psi_{\theta_{t-1}}(s,a)\right]^{\top}\mathbb{E}\left[(h_{t}(K_{t}+\xi
I)^{-1}e_{t})\right]&\geq-\frac{h_{t}\sqrt{D_{\infty}\psi_{\infty}}}{\xi}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right).\\\
\end{split}$

Finally, combining all of these inequalities together and taking expectation
over the randomness of $\theta_{t}$, we get:

$\displaystyle\mathbb{E}\left[F(\theta_{t})-F(\theta_{t-1})\right]$
$\displaystyle\geq
h_{t}(1-\gamma)\mathbb{E}\left[J(\theta_{*})-J(\theta_{t-1})\right]-C_{\nu,2}\mathbb{E}\left[\left\lVert
h_{t}(K_{t}+\xi I)^{-1}(g_{t}+e_{t})\right\rVert^{\beta_{2}+1}\right]$
$\displaystyle\qquad-
h_{t}\sqrt{D_{\infty}\psi_{\infty}}\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}+\frac{\sqrt{E_{\Pi}}}{\sqrt{\psi_{\infty}}}+\frac{C_{\xi}\xi+2}{\xi}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert\right]\right)$
$\displaystyle\overset{(i)}{\geq}h_{t}(1-\gamma)\mathbb{E}\left[J(\theta_{*})-J(\theta_{t-1})\right]-\frac{C_{\nu,2}h_{t}^{\beta_{2}+1}}{\xi^{\beta_{2}+1}}\left(\mathbb{E}\left[\left\lVert
g_{t}+e_{t}\right\rVert^{\beta_{2}+1}\right]\right)$ $\displaystyle\qquad-
h_{t}\sqrt{D_{\infty}\psi_{\infty}}\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}+\frac{\sqrt{E_{\Pi}}}{\sqrt{\psi_{\infty}}}+\frac{C_{\xi}\xi+2}{\xi}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert\right]\right)$
$\displaystyle\overset{}{\geq}h_{t}(1-\gamma)\mathbb{E}\left[J(\theta_{*})-J(\theta_{t-1})\right]-\frac{2C_{\nu,2}h_{t}^{\beta_{2}+1}}{\xi^{\beta_{2}+1}}\left(\mathbb{E}\left[\left\lVert
e_{t}\right\rVert^{\beta_{2}+1}\right]+\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]\right)$ $\displaystyle\qquad-
h_{t}\sqrt{D_{\infty}\psi_{\infty}}\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}+\frac{\sqrt{E_{\Pi}}}{\sqrt{\psi_{\infty}}}+\frac{C_{\xi}\xi+2}{\xi}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert\right]\right)$
$\displaystyle\overset{(ii)}{\geq}h_{t}(1-\gamma)\mathbb{E}\left[J(\theta_{*})-J(\theta_{t-1})\right]-\frac{2C_{\nu,2}h_{t}^{\beta_{2}+1}}{\xi^{\beta_{2}+1}}\left(\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}+\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]\right)$ $\displaystyle\qquad-
h_{t}\sqrt{D_{\infty}\psi_{\infty}}\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}+\frac{\sqrt{E_{\Pi}}}{\sqrt{\psi_{\infty}}}+\frac{C_{\xi}\xi+2}{\xi}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert\right]\right),$

where in $(i)$ we use that $K_{t}+\xi I$ has minimum eigenvalue $\xi$, in
$(ii)$ we again use our bound in Lemma 7.

Finally, we note that

$\displaystyle F(\theta_{t})-F(\theta_{t-1})$
$\displaystyle=\mathbb{E}_{s,a\sim
d_{*}^{\rho}}\left[\log\frac{\pi_{\theta_{t-1}}}{\pi_{\theta_{t}}}(a|s)\right]$
$\displaystyle\leq D_{\infty}\mathbb{E}_{s,a\sim
d_{\theta_{t-1}}^{\rho}}\left[\log\frac{\pi_{\theta_{t-1}}}{\pi_{\theta_{t}}}(a|s)\right]$
$\displaystyle=D_{\infty}\mathbb{E}_{s\sim
H_{\theta_{t-1}}^{\rho}}\left[\mathbb{E}_{a\sim\pi_{\theta_{t-1}}(\cdot|s)}\left[\log\frac{\pi_{\theta_{t-1}}}{\pi_{\theta_{t}}}(a|s)\right]\right]$
$\displaystyle\overset{(i)}{\leq}C_{\nu,1}D_{\infty}\left\lVert\theta_{t-1}-\theta_{t}\right\rVert^{\beta_{1}}$
$\displaystyle\leq\frac{C_{\nu,1}D_{\infty}}{\xi^{\beta_{1}}}h_{t}^{\beta_{1}}\left(\left\lVert
g_{t}+e_{t}\right\rVert^{\beta_{1}}\right)$
$\displaystyle\leq\frac{2C_{\nu,1}D_{\infty}}{\xi^{\beta_{1}}}h_{t}^{\beta_{1}}\left(\left\lVert
g_{t}\right\rVert^{\beta_{1}}+\left\lVert
e_{t}\right\rVert^{\beta_{1}}\right),$

where in $(i)$, we use the $\mathsf{KL}$ smoothness bound in Assumption 1.
Thus, we find after taking expectation the following inequality:

$\begin{split}J(\theta_{*})-\mathbb{E}\left[J(\theta_{t-1})\right]&\leq\frac{2C_{\nu,1}D_{\infty}}{\xi^{\beta_{1}}(1-\gamma)}h_{t}^{\beta_{1}-1}\left(\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}\right)^{\beta_{1}}+\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{1}}\right]\right)\\\
&\qquad+\frac{2C_{\nu,2}h_{t}^{\beta_{2}}}{\xi^{\beta_{2}+1}(1-\gamma)}\left(\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}\right)^{\beta_{2}+1}+\mathbb{E}\left[\left\lVert
g_{t}\right\rVert^{\beta_{2}+1}\right]\right)\\\
&\qquad+\frac{\sqrt{D_{\infty}\psi_{\infty}}}{1-\gamma}\left(\frac{\sigma}{\xi(1-\gamma)\sqrt{B}}+\frac{\sqrt{E_{\Pi}}}{\sqrt{\psi_{\infty}}}+\frac{C_{\xi}\xi+2}{\xi}\mathbb{E}\left[\left\lVert
g_{t}\right\rVert\right]\right).\end{split}$

This concludes the proof if we write
$C_{NPG,3}=\frac{2C_{\nu,1}D_{\infty}}{\xi^{\beta_{1}}}$,
$C_{NPG,4}=\frac{2C_{\nu,2}h_{t}^{\beta_{2}+1}}{\xi^{\beta_{2}+1}}$ and
$C_{NPG,5}=\frac{(C_{\xi}\xi+2)}{\xi}\sqrt{D_{\infty}\psi_{\infty}}.$
$\square$

In the following, we take the minimum of the right hand side over $t=1\ldots
T$.

Proof of Corollary 2, NPG:

It remains now to substitute the learning rate and gradient bounds from each
of the cases we analyzed earlier. Since $\beta_{1}\geq 1$, $\beta_{2}>0$, the
final term always dominates the order when we consider the dependencies in
$\epsilon,(1-\gamma)$. In the sequel, we will ignore the leading terms, noting
that they may contribute to other dependencies in $\xi$, $D_{\infty}$, etc.

Case I, $h_{t}=\lambda$: Recall that in this case,

$\displaystyle\min_{t\leq T}\left\lVert g_{t}\right\rVert^{2}$
$\displaystyle\leq\frac{4(\psi_{\infty}+\xi)}{\lambda
T}\left(J_{*}-J(\theta_{0})\right)+\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}$
$\displaystyle\qquad+2^{\frac{8}{1-\beta_{0}}}\left(\frac{\left(L_{1}+L_{2}\right)(\psi_{\infty}+\xi)}{(1-\gamma)\xi^{\beta_{max}+1}}\right)^{\frac{2}{1-\beta_{0}}}\lambda^{\frac{2\beta_{0}}{1-\beta_{0}}}.$

Subsequently, we can choose
$\lambda\lesssim(1-\gamma)^{\frac{2-\beta_{0}}{\beta_{0}}}\epsilon^{\frac{1-\beta_{0}}{\beta_{0}}}$,
so that the final term is $\lesssim\epsilon^{2}(1-\gamma)^{2}$.

Subsequently we require $T\gtrsim\frac{1}{\lambda\epsilon^{2}(1-\gamma)^{2}}$
to make the first term $\lesssim(1-\gamma)^{2}\epsilon^{2}$ and
$B\gtrsim\epsilon^{-\frac{4}{\beta_{0}+1}}(1-\gamma)^{-2-\frac{4}{\beta_{0}+1}}$
to make the second term $\lesssim(1-\gamma)^{2}\epsilon^{2}$. Substituting our
requirement on $\lambda$, we get
$T\gtrsim\epsilon^{-\frac{1+\beta_{0}}{\beta_{0}}}(1-\gamma)^{-\frac{2+\beta_{0}}{\beta_{0}}}.$
Thus, we get $\min_{t\leq T}\left\lVert
g_{t}\right\rVert^{2}\lesssim(1-\gamma)^{2}\epsilon^{2}$. This then implies

$\displaystyle\min_{t\leq
T}J_{*}-\mathbb{E}\left[J(\theta_{t})\right]\lesssim\epsilon+\frac{\sqrt{D_{\infty}E_{\Pi}}}{1-\gamma}.$

Case II, $h_{t}=\lambda T^{\frac{\beta_{0}-1}{\beta_{0}+1}}$: Recall that in
this case,

$\min_{t\leq T}\left\lVert
g_{t}\right\rVert^{2}\leq\frac{4(\psi_{\infty}+\xi)}{\lambda}T^{-\frac{2\beta_{0}}{\beta_{0}+1}}\left(J_{*}-J(\theta_{0})+\frac{\lambda}{4}\right)+T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}.$

Subsequently we require
$T\gtrsim\left(\frac{1}{\lambda\epsilon^{2}(1-\gamma)^{2}}\right)^{\frac{\beta_{0}+1}{2\beta_{0}}}$
to bound the first term by $\lesssim\epsilon^{2}(1-\gamma)^{2}$. For
simplicity, take $\lambda\asymp(1-\gamma)^{1/\beta_{0}}$, in which case we get
$T\gtrsim\left(\frac{1}{\epsilon^{2}(1-\gamma)^{2+{1/\beta_{0}}}}\right)^{\frac{\beta_{0}+1}{2\beta_{0}}}$.
Consequently, the second term is bounded by

$\displaystyle
T^{\frac{\beta_{0}(\beta_{0}-1)}{\beta_{0}+1}}\left(\frac{\sigma}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}$
$\displaystyle\lesssim\left(\frac{1}{\epsilon^{2}(1-\gamma)^{2+1/\beta_{0}}}\right)^{\frac{\beta_{0}-1}{2}}\left(\frac{1}{(1-\gamma)\sqrt{B}}\right)^{\beta_{0}+1}$
$\displaystyle\lesssim\epsilon^{1-\beta_{0}}(1-\gamma)^{-\frac{4\beta_{0}^{2}+\beta_{0}-1}{2\beta_{0}}}B^{-\frac{\beta_{0}+1}{2}}.$

So we can take
$B\gtrsim\epsilon^{-2}(1-\gamma)^{\frac{4\beta_{0}^{2}+5\beta_{0}-1}{\beta_{0}(\beta_{0}+1)}}$,
to make this term $\lesssim(1-\gamma)^{2}\epsilon^{2}$. This then implies

$\displaystyle\min_{t\leq
T}J_{*}-\mathbb{E}\left[J(\theta_{t-1})\right]\leq\epsilon+\frac{\sqrt{D_{\infty}E_{\Pi}}}{1-\gamma}.$

$\square$

Remark: It is possible to do similar analysis for policy gradient using this
technique, but the quantity $E_{\Pi}$ lacks a meaningful interpretation in
that case.

##  Appendix D Experiments

All results of these experiments can be found in the two Figures in the main
text, and they are primarily intended to demonstrate practical examples of
policies that satisfy our assumptions. All experiments were run locally on a
single CPU, with 1Gb of dedicated RAM. The experiments are not computationally
intensive and are primarily illustrative.

###  D.1 Generalized Gaussian Policies

For Figure 1(a), we sampled $4000$ actions from a generalized Gaussian with
mean $\left\langle s,\theta\right\rangle$ with $\theta\in\mathbb{R}^{2}$ and
parameter $\kappa=1.2$, for a state $[1.0,0]$ in $\mathbb{R}^{2}$. We let the
first coordinate $\theta^{(1)}$ range from $[-2,2]$ and compute the score
function is then computed for these actions. The magnitude of the difference
(compared to the reference point, $\theta^{(1)}=0$) is then generated, and
plotted against the standard Gaussian ($\kappa=2$). The tail growth properties
as well as local smoothness can be seen clearly from the Figure.

For the exploration problem, we implement the reward function described in
Equation (10) with parameter $\theta^{*}=3.9$ and initial parameter
$\theta_{0}=0$. We aggregate gradients using a batch size of $1000$ and update
using our policy gradient rule. The performance is then reported on a batch of
$1000$, with standard deviations reported within this batch. We ran this
experiment for 5 seeds and found that the qualitative behaviour does not
change (although the inflection point of the policy behaviour is highly
random, the Gaussian policy is always significantly worse than the generalized
Gaussian).

###  D.2 Unbounded Gradient

We devise a simple policy and show that its gradient appears to be unbounded
(in fact scaling logarithmically with the number of samples), but has a
bounded integral according to its own measure $\pi_{\theta}$. For this, we
simply implement the policy given in Example 3, and sample larger batches of
actions. We then compute the gradients, and compare two norms that have been
used in assumptions, that is the norm $\max_{n=1,\ldots
K}\left\lVert\psi_{\theta}(s,a_{n})\right\rVert$ and our assumption
$\frac{1}{K}\sum_{n=1}^{K}\left\lVert\psi_{\theta}(s,a_{n})\right\rVert^{2}$.
We find that the former is unbounded for larger sets while the latter
converges smoothly to a fixed value. As we explain in our paper, this shows
that interesting policies can be covered by our assumptions while not being
allowed in prior work.