# Projected Policy Gradient Converges in a Finite Number of Iterations

Jiacai Liu  School of Data Science, Fudan University, Shanghai, China.  Wenye
Li  School of Data Science, Fudan University, Shanghai, China.  Ke Wei  School
of Data Science, Fudan University, Shanghai, China.

###### Abstract

The convergence of the projected policy gradient (PPG) method under the
simplex parameterization is studied and it is shown that this method indeed
achieves the exact convergence in a finite number of iterations for any
constant step size. To establish this result, we first establish the sublinear
convergence of PPG for an arbitrary fixed step size, which is also new, to the
best of knowledge. The finite iteration convergence property is also
applicable to a preconditioned version of PPG, namely the projected Q-ascent
(PQA) method. Additionally, the linear convergence of PPG and its equivalence
to PI are established under the non-adaptive increasing step sizes and the
adaptive step sizes, respectively.

Keywords. Projected policy gradient, sublinear convergence, finite iteration
convergence, linear convergence, equivalence to PI

##  1 Introduction

Reinforcement learning (RL) is essentially about how to make efficient
sequential decisions to achieve a long term goal. It has received intensive
investigations both from theoretical and algorithmic aspects due to its recent
success in many areas, such as games [21, 24, 4, 26], robotics [10, 15, 19]
and various other real applications [1, 8, 20]. Typically, RL can be modeled
as a discounted Markov decision process (DMDP) represented by a tuple
$\mathcal{M}\left({\cal S},{\cal A},P,r,\gamma,\mu\right)$, where ${\cal S}$
is the state space, ${\cal A}$ denotes the action space, $P(s^{\prime}|s,a)$
is the transition probability or density from state $s$ to state $s^{\prime}$
under action $a$, $r:{\cal S}\times{\cal A}\rightarrow\mathbb{R}$ is the
reward function, $\gamma\in[0,1)$ is the discounted factor and $\mu$ is the
probability distribution of the initial state $s_{0}$. In this paper, we focus
the tabular setting where ${\cal S}$ and ${\cal A}$ are finite, i.e., $|{\cal
S}|<\infty$ and $|{\cal A}|<\infty$. Let $\Delta({\cal A})$ be the probability
simplex over the set ${\cal A}$, defined as

$\displaystyle\Delta\left({\cal A}\right)=\left\\{\theta\in\mathbb{R}^{|{\cal
A}|}:\theta_{i}\geq 0,\sum_{i=1}^{|{\cal A}|}{\theta_{i}}=1\right\\}.$ (1.1)

Then the set of admissible stationary policies for DMDP (i.e., the direct or
simplex parameterization of policies) is given by

$\displaystyle\Pi:=\left\\{\pi=\left(\pi_{s}\right)_{s\in\mathcal{S}}\,\,|\,\,\pi_{s}\in\Delta\left(\mathcal{A}\right)\,\,\text{for
all }s\in\mathcal{S}\right\\},$ (1.2)

where $\pi_{s}:=\pi(\cdot|s)\in\mathbb{R}^{|{\cal A}|}$ and
$\pi\in\mathbb{R}^{|{\cal S}|\times|{\cal A}|}$.

Given a policy $\pi\in\Pi$, the state value function at $s\in{\cal S}$ is
defined as

$\displaystyle V^{\pi}\left(s\right)$
$\displaystyle:=\mathbb{E}\left\\{\sum_{t=0}^{\infty}{\gamma^{t}r\left(s_{t},a_{t}\right)}|s_{0}=s,\pi\right\\},$
(1.3)

while the state-action value function at $(s,a)\in{\cal S}\times{\cal A}$ are
defined as

$\displaystyle Q^{\pi}\left(s,a\right)$
$\displaystyle:=\mathbb{E}\left\\{\sum_{t=0}^{\infty}{\gamma^{t}r\left(s_{t},a_{t}\right)}|s_{0}=s,a_{0}=a,\pi\right\\}.$
(1.4)

Overall, the goal of RL is to find a policy that maximizes the weighted
average of the state values under the initial distribution $\mu$, namely to
solve

$\displaystyle\underset{\pi\in\Pi}{\max}\,V^{\pi}\left(\mu\right)$ (1.5)

Here
$V^{\pi}\left(\rho\right):=\mathbb{E}_{s\sim\rho}\left[V^{\pi}\left(s\right)\right]$
for any $\rho\in\Delta({\cal S})$.

Projected policy gradient (PPG) is likely to be the most direct optimization
method for solving (1.5). Given an initial policy $\pi_{0}\in\Pi$, PPG
generates a policy sequence $\\{\pi^{k}\\}$ for $k=1,2,3,...$ as follows:

$\displaystyle\pi^{k+1}$
$\displaystyle\in\underset{\pi\in\Pi}{\mathrm{arg}\min}\left\\{-\eta_{k}\left<\nabla_{\pi}V^{\pi}\left(\mu\right)\left|{}_{\pi=\pi^{k}}\right.,\pi-\pi^{k}\right>+\frac{1}{2}\left\|\pi-\pi^{k}\right\|_{2}^{2}\right\\},$
(1.6)
$\displaystyle\in\underset{\pi\in\Pi}{\mathrm{arg}\min}\left\\{\sum_{s\in\mathcal{S}}{\left(-\eta_{k}\left<\nabla_{\pi_{s}}V^{\pi}\left(\mu\right)\left|{}_{\pi=\pi^{k}}\right.,\pi_{s}-\pi_{s}^{k}\right>+\frac{1}{2}\left\|\pi_{s}-\pi_{s}^{k}\right\|_{2}^{2}\right)}\right\\},$

or equivalently,

$\displaystyle\pi_{s}^{k+1}=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(\pi_{s}^{k}+\eta_{k}\nabla_{\pi_{s}}V^{\pi}\left(\mu\right)\left|{}_{\pi=\pi^{k}}\right.\right),\quad\forall
s\in\mathcal{S},$

where $\left<\cdot\right>$ denotes the inner product, $\eta_{k}$ is the step
size and $\text{Proj}_{\Delta(\mathcal{A})}$ denotes the projection onto
$\Delta(\mathcal{A})$ in Euclidean norm, i.e.,
$\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(v\right)=\underset{p\in\Delta\left(\mathcal{A}\right)}{\mathrm{arg}\min}\,\,\left\|p-v\right\|_{2}^{2}$.
According to the policy gradient theorem [25],

$\nabla_{\pi_{s}}V^{\pi}\left(\mu\right)=\frac{d_{\mu}^{\pi}\left(s\right)}{1-\gamma}Q^{\pi}(s,\cdot)$

where $d_{\mu}^{\pi}$ is the state visitation probability defined as

$\displaystyle
d_{\mu}^{\pi}\left(s\right):=\left(1-\gamma\right)\mathbb{E}\left\\{\sum_{t=0}^{\infty}{\gamma^{t}\mathbbm{1}_{[s_{t}=s]}}|s_{0}\sim\mu,\pi\right\\}.$
(1.7)

Thus, PPG can be written explicitly in the following form:

$\displaystyle\mbox{(PPG)}\quad\pi_{s}^{k+1}=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(\pi_{s}^{k}+\frac{\eta_{k}d^{k}_{\mu}(s)}{1-\gamma}Q^{k}(s,\cdot)\right),\quad\forall
s\in\mathcal{S},$ (1.8)

where $d^{k}_{\mu}$ and $Q^{k}(s,\cdot)$ are short for $d^{\pi_{k}}_{\mu}$ and
$Q^{\pi_{k}}(s,\cdot)$, respectively. Note that $d^{k}_{\mu}(s)$ can be
extremely small for infrequently visited states and thus may slow down the
learning rate of PPG significantly. In contrast, Projected Q-ascent (PQA) uses
the dynamic weighted squared $\ell_{2}$-distance
$\sum_{s\in\mathcal{S}}{\frac{d_{\mu}^{k}\left(s\right)}{1-\gamma}\cdot\frac{1}{2}\left\|\pi_{s}-\pi_{s}^{k}\right\|^{2}_{2}}$
in (1.6) to cancel the negative effect of $d^{\pi}_{\mu}(s)$, leading to the
following update:

$\displaystyle\mbox{(PQA)}\quad\pi_{s}^{k+1}$
$\displaystyle=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(\pi_{s}^{k}+\frac{\eta_{k}\left(1-\gamma\right)}{d_{\mu}^{k}\left(s\right)}\nabla_{\pi_{s}}V^{\pi}\left(\mu\right)\left|{}_{\pi=\pi^{k}}\right.\right)$
$\displaystyle=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(\pi_{s}^{k}+\eta_{k}Q^{k}(s,\cdot)\right),\quad\forall
s\in\mathcal{S}.$ (1.9)

PQA is indeed a special case of policy mirror ascent methods (e.g. [9, 23, 14,
28, 7, 30, 16, 11]) where the Bregman distance is the squared
$\ell_{2}$-distance and it can also be seen as a preconditioned version of
PPG.

In this paper we will focus on convergence analysis of PPG and PQA (in
particular PPG but partial results are also new for PQA). Despite this, we
would like to mention that the convergence of various different policy
optimization algorithms have been studied under different parameterizations in
the tabular setting, such as those under the softmax polices and log-linear
polices, see [2, 18, 13, 29, 3] and references therein for more details.

###  1.1 Related work

In this section, we will give a brief overview of existing convergence results
on PPG and PQA. The convergence of PPG is firstly studied in [2]. Letting
$d^{*}_{\rho}:=d^{\pi^{*}}_{\rho}$, it is shown that PPG satisfies

$\displaystyle\underset{0<k\leq
K}{\min}\left\\{V^{*}\left(\rho\right)-V^{k}\left(\rho\right)\right\\}\leq\varepsilon\quad\text{whenever
}K>\frac{64\gamma\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{\varepsilon^{2}\left(1-\gamma\right)^{6}}\left\|\frac{d_{\rho}^{*}}{\mu}\right\|_{\infty}^{2}$
(1.10)

for any $\rho\in\Delta(\mathcal{S})$, where
$\left\|\frac{\tilde{\rho}}{\tilde{\mu}}\right\|_{\infty}:=\underset{s\in\mathcal{S}}{\max}\left\\{\frac{\tilde{\rho}\left(s\right)}{\tilde{\mu}\left(s\right)}\right\\}$
is called the distribution mismatch of $\tilde{\rho}\in\Delta({\cal S})$ from
$\tilde{\mu}\in\Delta({\cal S})$ (with the convention $\frac{0}{0}=1$), and
$V^{*}(\rho)$ and $V^{k}(\rho)$ are weighted state values associated with the
policy and the $k$-th iteration policy, respectively. This result has been
improved in [31] and [28] to

$\displaystyle
V^{*}\left(\mu\right)-V^{k}\left(\mu\right)\leq\mathcal{O}\left(\frac{\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{\left(1-\gamma\right)^{5}k}\left\|\frac{d_{\mu}^{*}}{\mu}\right\|_{\infty}^{2}\right).$
(1.11)

Note that the state value error
$V^{*}\left(\rho\right)-V^{k}\left(\rho\right)$ for arbitrary
$\rho\in\Delta({\cal S})$ can be derived from (1.11) with an additional factor
$\left\|\frac{\rho}{\mu}\right\|_{\infty}$ ([28], Theorem 2),

$\displaystyle
V^{*}\left(\rho\right)-V^{k}\left(\rho\right)\leq\mathcal{O}\left(\frac{\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{\left(1-\gamma\right)^{5}k}\left\|\frac{d_{\mu}^{*}}{\mu}\right\|_{\infty}^{2}\left\|\frac{\rho}{\mu}\right\|_{\infty}\right).$
(1.12)

We should emphasize that the aforementioned results are all obtained under the
step size condition $\eta\leq\frac{1}{L}$, where
$L=\frac{2\gamma\left|\mathcal{A}\right|}{\left(1-\gamma\right)^{3}}$ is the
smoothness coefficient of the value functions. In addition, [6] also shows
that PPG enjoys a linear convergence with exact line search which cannot be
computed.

The analyses in [2, 31, 28] are carried out in the general optimization
framework for projected gradient methods. More precisely, [31] leverages the
dual linear programming parameterization while [2, 28] relies on following two
ingredients:

  * •

Smoothness ([2, Lemma 54]): For any $\pi,\pi^{\prime}\in\Pi$, it holds that

$\left\|\nabla_{\pi}V^{\pi}\left(\mu\right)-\nabla_{\pi}V^{\pi^{\prime}}\left(\mu\right)\right\|_{2}\leq\frac{2\gamma\left|\mathcal{A}\right|}{(1-\gamma)^{3}}\left\|\pi-\pi^{\prime}\right\|_{2}.$

  * •

Gradient domination:

$V^{*}\left(\mu\right)-V^{\pi}\left(\mu\right)\leq\mathcal{O}\left(\left\|\nabla_{\pi}V^{\pi}\left(\mu\right)\right\|\right)$

In particular, [2] developes a variational gradient dominant lemma (see Lemma
4) and shows that

$V^{*}\left(\rho\right)-V^{\pi}\left(\rho\right)\leq\frac{1}{1-\gamma}\left\|\frac{d_{\rho}^{*}}{\mu}\right\|_{\infty}\underset{\pi^{\prime}\in\Pi}{\max}\left<\nabla_{\pi}V^{\pi}\left(\mu\right),\pi-\pi^{\prime}\right>.$

The “variational” refers to the term
$\underset{\pi^{\prime}\in\Pi}{\max}\left<\nabla_{\pi}V^{\pi}\left(\mu\right),\pi-\pi^{\prime}\right>$
since it differs from $\left\|\nabla_{\pi}V^{\pi}\left(\mu\right)\right\|$
which is widely used in unconstrained optimization. A weak gradient-mapping
dominance for general nonconvex composite optimization is presented in [28]
(see Definition 3), from which the sublinear convergence result (1.11)
follows.

Since PQA is a special case of policy mirror ascent methods, the analysis of
PQA follows directly from those for policy mirror ascent methods. In [23], it
is shown that PQA converges at a rate of
$\mathcal{O}\left(\frac{1}{\sqrt{k}}\frac{\sqrt{\mathcal{A}}}{\left(1-\gamma\right)^{2}}\right)$
under infinity norm with the step size
$\eta_{k}=\mathcal{O}\left(\frac{1}{\sqrt{k}}\frac{1-\gamma}{\sqrt{\mathcal{A}}}\right)$.
The following convergence result is established in [9] for the constant step
size $\eta_{k}=1$,

$\frac{1}{k}\left\|\sum_{i=1}^{k}{(V^{*}-V^{i})}\right\|_{\infty}\leq\mathcal{O}\left(\frac{1-\gamma^{k}}{\left(1-\gamma\right)^{2}}\frac{1}{k}\right).$

An improved result is obtained in [28] which shows that, with any constant
step size and arbitrary $\rho\in\Delta({\cal S})$, PQA achieves the following
sublinear convergence rate,

$\displaystyle
V^{*}\left(\rho\right)-V^{k}\left(\rho\right)\leq\frac{1}{k+1}\left(\frac{\mathbb{E}_{s\sim
d_{\rho}^{*}}\left[\left\|\pi_{s}^{*}-\pi_{s}^{0}\right\|_{2}^{2}\right]}{2\eta\left(1-\gamma\right)}+\frac{1}{\left(1-\gamma\right)^{2}}\right).$
(1.13)

It is further shown that in [28] that PQA enjoys a linear convergence under
geometrically increasing step sizes. Moreover, the linear convergence of PQA
in terms of the infinity norm has been established in [11] under adaptive step
sizes.

###  1.2 Main contributions

#### Sublinear convergence of PPG for full range of constant step sizes.

A new convergence analysis of PPG is conducted and we show that it has at
least sublinear convergence for any constant step size $\eta$ and arbitrary
$\rho\in\Delta({\cal S})$,

$V^{*}\left(\rho\right)-V^{k}\left(\rho\right)\leq\frac{1}{k}\frac{1}{\left(1-\gamma\right)^{2}}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}\left(1+\frac{2+5|{\cal
A}|}{\eta\tilde{\mu}}\right)$

Compared with the results in [2, 31, 28], we break the restriction
$\eta_{k}\leq\frac{1}{L}$ on the step size and obtain a new best sublinear
convergence rate for PPG by setting
$\eta\geq\frac{2+5\left|\mathcal{A}\right|}{\tilde{\mu}}$,

$\mathcal{O}\left(\frac{1}{k}\frac{1}{\left(1-\gamma\right)^{2}}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}\right).$

Furthermore, a more careful derivation shows that both PPG and PQA enjoys a
linear convergence rate of
$\left(1-\frac{1-\gamma}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)^{k}$
in the early stage of the iterations (i.e. linear convergence for $k\leq
k_{0}(\eta)$ and sublinear for $k\geq k_{0}(\eta)$, where $k_{0}(\eta)$ is the
threshold related to step size $\eta$).

#### Finite iteration convergence of both PPG and PQA.

Based on the sublinear convergence, we show that both PPG and PQA output the
optimal policies after a finite number of iterations. The intuition behind
this result is that when the value error of PPG or PQA is sufficiently small,
the projection onto simplex will put all the probability masses on the optimal
actions. This can’t be achieved by policy gradient methods under other
parameterization such as softmax PG ([2, 18]) and softmax NPG ([2, 13]) since
the policies generated by these methods are always the interior points of
$\Pi$. As a by-product, we present a new dimension-free bound for the finite
iteration convergence of PI and VI, which does not explicitly depend on
$|{\cal S}|$ and $|{\cal A}|$.

#### Linear convergence and equivalence to PI.

Using non-adaptive geometrically increasing step sizes
$\eta_{k}=\mathcal{O}\left(\frac{1}{\gamma^{2k}}\right)$, the global
$\gamma$-rate linear convergence of PPG is established. We also show that both
PPG and PQA are equivalent to PI when the step size $\eta_{k}$ is larger than
a threshold that can be calculated from the current policy $\pi^{k}$.

It is worth noting that the techniques used in our proofs are substantially
different with those in [2, 23, 9, 31, 28, 11]. Instead of considering PPG in
the general context of projected gradient methods in optimization, we leverage
the more explicit form of the projection onto the probability simplex to
derive the lower bound for one-step policy improvement and to discuss the
support information of policies.

###  1.3 Notation and assumptions

Recalling the definitions of the state value function (1.3) and the state-
action value function (1.4), the advantage function of a policy $\pi$ is
defined as

$\displaystyle
A^{\pi}\left(s,a\right):=Q^{\pi}\left(s,a\right)-V^{\pi}\left(s\right).$

It is evident that $A^{\pi}(s,a)$ measures how well a single action is
compared with the average state value. Moreover, we use $V^{*}(s)$,
$Q^{*}(s,a)$ and $A^{*}(s,a)$ to denote the corresponding value functions
associated with the optimal policy $\pi^{*}$, and use $V^{k}(s)$, $Q^{k}(s,a)$
and $A^{k}(s,a)$ to denoted the corresponding value functions associated with
the policy output by the algorithm in the $k$-th iteration. In the sequel we
often use the shorthand notation for ease of exposition, for example,

$\displaystyle\pi_{s,a}:=\pi(a|s),\quad\pi_{s}:=\pi(\cdot|s),\quad
Q^{\pi}_{s,a}:=Q^{\pi}(s,a),\quad\mbox{and}\quad
Q^{\pi}_{s}:=Q^{\pi}(s,\cdot).$

Given a state $s\in{\cal S}$, the set of optimal actions ${\cal A}_{s}^{\ast}$
at state $s$ is defined as,

$\displaystyle{\cal A}_{s}^{\ast}=\arg\max_{a\in{\cal
A}}Q^{\ast}(s,a)=\arg\max_{a\in{\cal A}}A^{\ast}(s,a).$

Given a policy $\pi\in\Pi$, a state $s\in{\cal S}$ and a set $B\subset{\cal
A}$, define

$\pi_{s}\left(B\right)=\sum_{a\in B}{\pi_{s}\left(a\right)}$

as the probability of $\pi_{s}$ on $B$ and denote by $b_{s}^{\pi}$ the
probability on non-optimal actions,

$b_{s}^{\pi}=\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{*}\right).$

When $b_{s}^{\pi}$ is small for any $s\in\mathcal{S}$, it is natural to expect
that $\pi$ will be close to be optimal. Thus, $b_{s}^{\pi}$ is a very
essential optimality measure of a policy. The set of $\pi$-optimal actions at
state $s$, denoted $\mathcal{A}_{s}^{\pi}$, is defined as

$\mathcal{A}_{s}^{\pi}=\underset{a\in\mathcal{A}}{\mathrm{arg}\max}\,\,A^{\pi}\left(s,a\right),$

with $\mathcal{A}_{s}^{k}$ being the abbreviation of
$\mathcal{A}_{s}^{\pi^{k}}$. The following quantity is quite central in the
finite iteration convergence analysis, which has also appeared in previous
works, see for example [18, 13].

######  Definition 1.1.

The optimal advantage function gap $\Delta$ is defined as follows:

$\displaystyle\Delta:=\underset{s\in\tilde{S},a\notin\mathcal{A}_{s}^{*}}{\min}\left|A^{*}(s,a)\right|,$
(1.14)

where $\widetilde{S}=\\{s\in{\cal S}:{\cal A}^{*}_{s}\neq{\cal A}\\}$ denotes
the set of states that have non-optimal actions.

Without loss of generality, we assume $\tilde{{\cal S}}\neq\emptyset$. It is
trivial that $\Delta>0$ since $A^{*}(s,a)<0$ holds for all non-optimal
actions. Additionally, we will make the following two standard assumptions
about the reward and the initial state distribution.

######  Assumption 1.1.

(Bounded reward.) $r(s,a)\in[0,1],~{}\forall s\in{\cal S},~{}a\in{\cal A}.$

######  Assumption 1.2.

(Traversal initial distribution.) $\tilde{\mu}:=\underset{s\in{\cal
S}}{\min}\,\mu\left(s\right)>0.$

Recall that $d_{\mu}^{\pi}$ defined (1.7) is the state visitation measure
following policy $\pi$. We use $d^{*}_{\mu}$ to the state visitation measure
following the optimal policy $\pi^{*}$ and use $d^{k}_{\mu}$ to denote the
visitation measure following the policy output by the algorithm in the $k$-th
iteration. For $\pi\in\Pi$, $\mu\in\Delta({\cal S})$ and $s\in{\cal S}$, it
follows immediately from Assumption 1.2 that

$\displaystyle d^{\pi}_{\mu}(s)\geq(1-\gamma)\tilde{\mu}.$ (1.15)

###  1.4 Organization of the paper

The rest of the paper is outlined as follows. In Section 2, some preliminary
results are provided which be used in our later analysis. The sublinear
convergence of PPG with any constant step size is discussed in Section 3,
followed by the finite convergence in Section 4. The dimension-free bound for
the finite iteration convergence of PI and VI is also presented in Section 4.
In Section 5, we present the results of linear convergence and equivalence to
PI under different step size selection rules.

##  2 Preliminaries

###  2.1 Useful lemmas for the DMDP setting

As we assume the reward function $r$ is bounded in Assumption 1.1, all the
value functions are bounded as they are discounted summations of rewards.

######  Lemma 2.1.

For any policy $\pi\in\Pi$ and $(s,a)\in{\cal S}\times{\cal A}$,

$\displaystyle
V^{\pi}(s)\in\left[0,\frac{1}{1-\gamma}\right],\;\;Q^{\pi}(s,a)\in\left[0,\frac{1}{1-\gamma}\right],\;\;A^{\pi}(s,a)\in\left[-\frac{1}{1-\gamma},\frac{1}{1-\gamma}\right].$

By leveraging the structure property of DMDP, we further have the lemma below.

######  Lemma 2.2.

For any policy $\pi$ ,

  * •

$\left\|Q^{*}-Q^{\pi}\right\|_{\infty}\leq\gamma\left\|V^{*}-V^{\pi}\right\|_{\infty}$

  * •

$\left\|A^{*}-A^{\pi}\right\|_{\infty}\leq\left\|V^{*}-V^{\pi}\right\|_{\infty}$

  * •

$\left\|V^{*}-V^{\pi}\right\|_{\infty}\leq\frac{V^{*}\left(\rho\right)-V^{\pi}\left(\rho\right)}{\tilde{\rho}}$
for any $\rho\in\Delta({\cal S})$ such that $\tilde{\rho}:=\underset{s\in{\cal
S}}{\min}\,\rho\left(s\right)>0$.

###### Proof.

Recalling the definition of state-action value function (1.4), one has

$\left|Q^{\pi}\left(s,a\right)-Q^{*}\left(s,a\right)\right|=\gamma\,\Big{|}\mathbb{E}_{s^{\prime}\sim
P\left(\cdot|s,a\right)}\left[V^{\pi}\left(s^{\prime}\right)-V^{*}\left(s^{\prime}\right)\right]\Big{|}\leq\gamma\left\|V^{\pi}-V^{*}\right\|_{\infty}.$

For the advantage function, one has

$A^{\pi}\left(s,a\right)-A^{*}\left(s,a\right)=\left(V^{*}\left(s\right)-V^{\pi}\left(s\right)\right)-\left(Q^{*}\left(s,a\right)-Q^{\pi}\left(s,a\right)\right).$

On the one hand,

$A^{\pi}\left(s,a\right)-A^{*}\left(s,a\right)\leq
V^{*}\left(s\right)-V^{\pi}\left(s\right)\leq\left\|V^{*}-V^{\pi}\right\|_{\infty}.$

On the other hand,

$A^{*}\left(s,a\right)-A^{\pi}\left(s,a\right)\leq
Q^{*}\left(s,a\right)-Q^{\pi}\left(s,a\right)\leq\gamma\left\|V^{*}-V^{\pi}\right\|_{\infty}.$

Thus $\left\|A^{\pi}-A^{*}\right\|\leq\left\|V^{*}-V^{\pi}\right\|_{\infty}$.
For the bound on $\left\|V^{*}-V^{\pi}\right\|_{\infty}$, a direct computation
yields

$\left\|V^{*}-V^{\pi}\right\|_{\infty}=\underset{s\in\mathcal{S}}{\max}\left\\{V^{*}\left(s\right)-V^{\pi}\left(s\right)\right\\}\leq\sum_{s}{\frac{\rho\left(s\right)}{\rho\left(s\right)}\left(V^{*}\left(s\right)-V^{\pi}\left(s\right)\right)}\leq\frac{V^{*}\left(\rho\right)-V^{\pi}\left(\rho\right)}{\tilde{\rho}},$

which concludes the proof. ∎

The performance difference lemma below is a fundamental lemma in the analysis
of RL algorithms (e.g. [2, 18, 13, 17, 28]). It characterizes the difference
between the value functions of two arbitrary policies can be represented as
the weighted average of the advantages.

######  Lemma 2.3 (Performance difference Lemma [12]).

For any two policies $\pi_{1},\pi_{2}$, and any $\rho\in\Delta({\cal S})$, one
has

$\displaystyle
V^{\pi_{1}}(\rho)-V^{\pi_{2}}(\rho)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{\rho}^{\pi_{1}}}\left[\mathbb{E}_{a\sim\pi_{1}(\cdot|s)}\left[A^{\pi_{2}}(s,a)\right]\right].$

Recall that $b^{\pi}_{s}$ denotes the probability on non-optimal actions which
can be viewed as an essential measure for the optimality of a policy. The
following two lemmas establish the relation between $b_{s}^{\pi}$ and the
mismatch $V^{\ast}(\rho)-V^{\pi}(\rho)$.

######  Lemma 2.4 ([13, Theorem 3.1]).

For any policy $\pi\in\Pi$ and $\rho\in\Delta({\cal S})$,

$V^{\ast}(\rho)-V^{\pi}(\rho)\leq\frac{1}{\left(1-\gamma\right)^{2}}\cdot\mathbb{E}_{s\sim
d_{\rho}^{\pi}}\left[b_{s}^{\pi}\right].$

######  Lemma 2.5.

For any policy $\pi\in\Pi$ and $\rho\in\Delta({\cal S})$,

$\mathbb{E}_{s\sim\rho}\left[b_{s}^{\pi}\right]\leq\frac{V^{*}\left(\rho\right)-V^{\pi}\left(\rho\right)}{\Delta}.$

###### Proof.

According to the performance difference lemma,

$\displaystyle V^{\ast}(\rho)-V^{\pi}(\rho)$
$\displaystyle=-\left(V^{\pi}\left(\rho\right)-V^{*}\left(\rho\right)\right)$
$\displaystyle=\frac{1}{1-\gamma}\sum_{s}{d_{\rho}^{\pi}\left(s\right)\sum_{a}{\pi\left(a|s\right)\cdot\left(-A^{*}\left(s,a\right)\right)}}$
$\displaystyle=\frac{1}{1-\gamma}\sum_{s\in\tilde{\mathcal{S}}}{d_{\rho}^{\pi}\left(s\right)\sum_{a\notin\mathcal{A}_{s}^{*}}{\pi\left(a|s\right)\cdot\left|A^{*}\left(s,a\right)\right|}}$
$\displaystyle\geq\frac{1}{1-\gamma}\sum_{s\in\tilde{\mathcal{S}}}{d_{\rho}^{\pi}\left(s\right)\sum_{a\notin\mathcal{A}_{s}^{*}}{\pi\left(a|s\right)\cdot\Delta}}$
$\displaystyle=\frac{\Delta}{1-\gamma}\sum_{s\in\tilde{\mathcal{S}}}{d_{\rho}^{\pi}\left(s\right)b_{s}^{\pi}}$
$\displaystyle\geq\Delta\cdot\mathbb{E}_{s\sim\rho}\left[b_{s}^{\pi}\right].$

The proof is complete after rearrangement. ∎

Given an arbitrary value vector $V\in\mathbb{R}^{|{\cal S}|}$, one can extract
a greedy policy $\pi_{V}$. The error between $V$ and $V^{\pi_{V}}$ can be
bounded as follows.

######  Lemma 2.6 (Error amplification [5]).

For any vector $V\in\mathbb{R}^{\left|\mathcal{S}\right|}$, let $\pi_{V}$ be
the greedy policy with respect to $V$, that is,

$\quad\mathrm{supp}\left(\pi_{V}\left(\cdot|s\right)\right)\subset\underset{a\in\mathcal{A}}{\mathrm{arg}\max}\,\,Q^{V}\left(s,a\right),\quad\forall
s\in\mathcal{S},$

where $Q^{V}\left(s,a\right):=\mathbb{E}_{s^{\prime}\sim
P\left(\cdot|s,a\right)}\left[r\left(s,a\right)+\gamma
V\left(s^{\prime}\right)\right]$ is the Q function induced by $V$. Then

$\left\|V^{*}-V^{\pi_{V}}\right\|_{\infty}\leq\frac{2\gamma}{1-\gamma}\left\|V-V^{*}\right\|_{\infty}.$

###  2.2 Basic facts about projection onto probability simplex

Recall that Euclidian projection onto the probability simplex is defined as

$\displaystyle\mathrm{Proj}_{\Delta({\cal A})}(p)=\underset{y\in\Delta({\cal
A})}{\arg\min}\|y-p\|^{2}.$

This projection has an explicit expression, presented in the following lemma.

######  Lemma 2.7.

For arbitrary vector
$p=\left(p_{a}\right)_{a\in\mathcal{A}}\in\mathbb{R}^{\left|\mathcal{A}\right|}$,

$\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(p\right)=\left(p+\lambda\mathbf{1}\right)_{+}$

where $\lambda$ is a constant such that
$\sum_{a\in\mathcal{A}}{\left(p_{a}+\lambda\right)_{+}}=1$.

###### Proof.

This fact can be obtained by studying the KKT condition of the projection
problem, see for example [27] for details. ∎

######  Remark 2.1.

It’s trivial to see that the projection onto probability simplex has a shift-
invariant property. That is,
$\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(p\right)=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(p+c\mathbf{1}\right)$
holds for arbitrary constant $c\in\mathbb{R}$. Therefore, PPG and PQA can also
be expressed in terms of advantages functions. For example, we have the
following alternative expression for PPG:

$\displaystyle\pi_{s}^{k+1}=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(\pi_{s}^{k}+\frac{\eta_{k}d^{k}_{\mu}(s)}{1-\gamma}A^{k}(s,\cdot)\right),\quad\forall
s\in\mathcal{S}.$

Lemma 2.7 implies that the projection onto the probability simplex can be
computed by first translating the vector with an offset, followed by
truncating those negative values to zeros. Moreover, the next lemma provides a
characterization on the support of the projection, which will be used
frequently in our analysis.

######  Lemma 2.8 (Gap property).

Let $\mathcal{B}$ and $\mathcal{C}$ be two disjoint non-empty sets such that
$\mathcal{A}=\mathcal{B}\cup\mathcal{C}$. Given an arbitrary vector
$p=\left(p_{a}\right)_{a\in\mathcal{A}}\in\mathbb{R}^{\left|\mathcal{A}\right|}$,
let $y=\mathrm{Proj}_{\Delta\left(\mathcal{A}\right)}\left(p\right)$. Then

$\forall
a^{\prime}\in\mathcal{C},~{}y_{a^{\prime}}=0\Leftrightarrow\,\,\sum_{a\in\mathcal{B}}{\left(p_{a}-\underset{a^{\prime}\in\mathcal{C}}{\max}\,\,p_{a^{\prime}}\right)_{+}}\geq
1.$

Roughly speaking, this lemma indicates that if the entries of $p$ in the index
set $\mathcal{C}$ are generally smaller than those in the index set
$\mathcal{B}$ and the cumulative gap satisfies
$\sum_{a\in\mathcal{B}}{\left(p_{a}-\underset{a^{\prime}\in\mathcal{C}}{\max}\,\,p_{a^{\prime}}\right)}_{+}\geq
1$, then the index set $\mathcal{C}$ will be excluded from the support set of
the projection $y$. The proof of this lemma is essentially contained in the
argument for Theorem 1 in [27]. To keep the presentation self-contained, we
give a short proof below.

###### Proof of Lemma 2.8.

First note that $\forall a\in{\cal A}$,

$y_{a}=0\,\stackrel{{\scriptstyle(a)}}{{\Longleftrightarrow}}\,\lambda\leq-
p_{a}\,\stackrel{{\scriptstyle(b)}}{{\Longleftrightarrow}}\,\sum_{a^{\prime}\in{\cal
A}}\left(p_{a^{\prime}}-p_{a}\right)_{+}\geq 1,$

where $(a)$ follows from Lemma 2.7 and $(b)$ is due to $\sum_{a\in{\cal
A}}(p_{a}+\lambda)_{+}=1$ and the monotonicity of $(\cdot)_{+}$. Thus we have

$y_{a^{\prime}}=0,~{}~{}\forall
a^{\prime}\in\mathcal{C}\Leftrightarrow\,\,\underset{a^{\prime}\in\mathcal{C}}{\min}\sum_{a\in\mathcal{A}}{\left(p_{a}-\,p_{a^{\prime}}\right)_{+}}\geq
1\Leftrightarrow\sum_{a\in\mathcal{A}}{\left(p_{a}-\underset{a^{\prime}\in\mathcal{C}}{\max}\,\,p_{a^{\prime}}\right)_{+}}\geq
1\Leftrightarrow\sum_{a\in\mathcal{B}}{\left(p_{a}-\underset{a^{\prime}\in\mathcal{C}}{\max}\,\,p_{a^{\prime}}\right)_{+}}\geq
1,$

which completes the proof. ∎

Based on Lemma 2.7, we can now rewrite the one-step update of PPG in (1.8) and
PQA in (1.9) into a unified framework with an explicit expression for the
projection. This is the prototype update that will be mainly analysed. Given
an input policy $\pi\in\Pi$ and step size $\eta>0$, the new policy $\pi^{+}$
is generated via

$\displaystyle\mbox{(Prototype
Update)}\quad\quad\pi^{+}_{s,a}(\eta)=\left(\pi_{s,a}+\eta_{s}A_{s,a}^{\pi}+\lambda_{s}\right)_{+},\quad\forall
s\in\mathcal{S},a\in\mathcal{A},$ (2.1)

where $\lambda_{s}$ is a constant such that $\sum_{a}{\pi}^{+}_{s,a}=1$. Note
that, given a constant step size $\eta$, $\eta_{s}=\frac{\eta
d_{\mu}^{\pi}\left(s\right)}{1-\gamma}$ for PPG while $\eta_{s}=\eta$ for PQA.

###  2.3 Basic properties of prototype update

Before presenting the sublinear convergence of PPG, we give a brief discussion
on the basic properties of the prototype update. The lemma below presents all
the possibilities for the support set of the new policy $\pi^{+}_{s}(\eta)$
(the subscript $s$ in $\eta_{s}$ will be omitted in this section for
simplicity).

######  Lemma 2.9.

Consider the prototype update in (2.1). Denote by ${\cal B}_{s}(\eta)$ the
support set of $\pi^{+}_{s}$:

$\displaystyle{\cal B}_{s}(\eta):=\left\\{a:\pi^{+}_{s,a}(\eta)>0\right\\}.$

Then for any $\eta>0$, ${\cal B}_{s}(\eta)$ admits one of the following three
forms:

  1. 1.

${\cal B}_{s}(\eta)\subsetneqq{\cal A}^{\pi}_{s}$,

  2. 2.

${\cal B}_{s}(\eta)={\cal A}^{\pi}_{s}$,

  3. 3.

${\cal B}_{s}(\eta)={\cal A}^{\pi}_{s}\cup{\cal C}_{s}(\eta)$, where ${\cal
C}_{s}(\eta)\subseteq{\cal A}\setminus{\cal A}_{s}^{\pi}$ is not empty.

###### Proof.

Without loss of generality, assume $\mathcal{A}^{\pi}_{s}\neq\mathcal{A}$.
Then it suffices to show that if ${\cal B}_{s}(\eta)$ contains an action
$a^{\prime}\notin{\cal A}^{\pi}_{s}$, all $\pi$-optimal actions are included
in ${\cal B}_{s}(\eta)$. Given any $\hat{a}\in\mathcal{A}_{s}^{\pi}$, define

$\hat{\mathcal{A}}_{s}=\left\\{a\in{\cal A}:\pi_{s,a}+\eta
A_{s,a}^{\pi}\geq\pi_{s,\hat{a}}+\eta A_{s,\hat{a}}^{\pi}\right\\}.$

Next we will show that

$\displaystyle I:=$ $\displaystyle\sum_{a\in\mathcal{A}}{\left(\pi_{s,a}+\eta
A_{s,a}^{\pi}-\left(\pi_{s,\hat{a}}+\eta
A_{s,\hat{a}}^{\pi}\right)\right)_{+}}$ $\displaystyle=$
$\displaystyle\sum_{a\in\hat{\mathcal{A}}_{s}}{\left(\pi_{s,a}+\eta
A_{s,a}^{\pi}-\left(\pi_{s,\hat{a}}+\eta A_{s,\hat{a}}^{\pi}\right)\right)}$
$\displaystyle\,\,=$
$\displaystyle\sum_{a\in\hat{\mathcal{A}}_{s}\cap\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}\right)}+\sum_{a\in\hat{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}+\eta\left(A_{s,a}^{\pi}-A_{s,\hat{a}}^{\pi}\right)\right)},$
$\displaystyle<$ $\displaystyle 1$

from which the claim follows immediately using Lemma 2.8.

If $\tilde{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}\neq\emptyset$, then

$\displaystyle\sum_{a\in\hat{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}+\eta\left(A_{s,a}^{\pi}-A_{s,\hat{a}}^{\pi}\right)\right)}<\sum_{a\in\hat{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}\right)},$

since $A_{s,a}^{\pi}<A_{s,\hat{a}}^{\pi}$ for
$a\in\hat{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}$. Consequently,

$\displaystyle
I<\sum_{a\in\hat{\mathcal{A}}_{s}\cap\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}\right)}+\sum_{a\in\hat{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}\right)}\leq
1.$

On the other hand, if
$\hat{\mathcal{A}}_{s}\setminus\mathcal{A}_{s}^{\pi}=\emptyset$ , one has
$\hat{\mathcal{A}}_{s}\subset\mathcal{A}_{s}^{\pi}$. In this case,

$I=\sum_{a\in\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a}-\pi_{s,\hat{a}}\right)}\leq\pi_{s}\left(\mathcal{A}_{s}^{\pi}\right)<1,$

where the last inequality is due to the fact that ${\cal B}_{s}(\eta)$
contains an action $a^{\prime}\notin{\cal A}^{\pi}_{s}$. ∎

The last lemma implies that at least one $\pi$-optimal action is included in
the support set ${\cal B}_{s}(\eta)$. In addition, it is not hard to verify
that when step size $\eta$ goes to infinity every $\pi$-suboptimal actions
will be excluded from the support set of $\pi^{+}_{s}$, which suggests that
${\cal B}_{s}(\eta)$ might shrink as $\eta$ increases. The following lemma
confirms that this observation is indeed true.

######  Lemma 2.10.

For $\eta_{1}>\eta_{2}>0$ we have

${\cal B}_{s}(\eta_{1})\subseteq{\cal B}_{s}(\eta_{2}).$

###### Proof.

Since the relation holds trivially when ${\cal B}_{s}(\eta_{2})=\mathcal{A}$,
we only consider the case ${\cal B}_{s}(\eta_{2})\neq\mathcal{A}$. First the
application of Lemma 2.8 yields that

$\displaystyle\sum_{a\in{\cal B}_{s}(\eta)}\left[\pi_{s,a}+\eta
A^{\pi}_{s,a}-\max_{a^{\prime}\not\in{\cal
B}_{s}(\eta)}(\pi_{s,a^{\prime}}+\eta A^{\pi}_{s,a^{\prime}})\right]_{+}\geq
1$ (2.2)

and

$\displaystyle a^{\prime}\not\in{\cal
B}_{s}(\eta)\Longleftrightarrow\sum_{a\neq a^{\prime}}\left[\pi_{s,a}+\eta
A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta A^{\pi}_{s,a^{\prime}})\right]_{+}\geq
1.$ (2.3)

If ${\cal B}_{s}(\eta_{2})\subseteq{\cal A}^{\pi}_{s}$ (i.e. the first two
cases in Lemma 2.9), then for any $a^{\prime}\not\in{\cal B}_{s}(\eta_{2})$ we
have

$\displaystyle\sum_{a\neq
a^{\prime}}\left[\pi_{s,a}+\eta_{1}A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta_{1}A^{\pi}_{s,a^{\prime}})\right]_{+}$
$\displaystyle\geq\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}+\eta_{1}A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta_{1}A^{\pi}_{s,a^{\prime}})\right]_{+}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}+\eta_{2}A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta_{2}A^{\pi}_{s,a^{\prime}})\right]_{+}\geq
1,$

where $(a)$ is due to the fact $(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\geq 0$
for $\forall a\in{\cal B}_{s}(\eta_{2})\subseteq{\cal A}^{\pi}_{s}$. This
implies that $a^{\prime}\not\in{\cal B}_{s}(\eta_{1})$, and thus ${\cal
B}_{s}(\eta_{1})\subseteq{\cal B}_{s}(\eta_{2})$.

For the case that ${\cal B}_{s}(\eta_{2})={\cal A}_{s}\cup{\cal
C}_{s}(\eta_{2})$, fixing $a^{\prime}\not\in{\cal B}_{s}(\eta_{2})$, it
follows from (2.2) that

$\displaystyle\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}+\eta_{2}A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta_{2}A^{\pi}_{s,a^{\prime}})\right]_{+}\geq\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}+\eta_{2}A^{\pi}_{s,a}-\max_{a^{\prime}\not\in{\cal
B}_{s}(\eta_{2})}(\pi_{s,a^{\prime}}+\eta_{2}A^{\pi}_{s,a^{\prime}})\right]_{+}\geq
1.$

Furthermore, since $a^{\prime}\not\in{\cal B}_{s}(\eta_{2})$ it is trivial to
see that $\forall a\in{\cal B}_{s}(\eta_{2})$

$\displaystyle\pi_{s,a}+\eta_{2}A^{\pi}_{s,a}>\pi_{s,a^{\prime}}+\eta_{2}A^{\pi}_{s,a^{\prime}}.$

Therefore,

$\displaystyle\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}+\eta_{2}A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta_{2}A^{\pi}_{s,a^{\prime}})\right]_{+}$
$\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}+\eta_{2}A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta_{2}A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{2}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle\geq 1,$

which yields

$\displaystyle\sum_{a\in{\cal
B}_{s}(\eta_{2})}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\geq 0,$

as $\eta_{2}>0$. Consequently,

$\displaystyle\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{1}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]_{+}-\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{2}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]_{+}$
$\displaystyle=$ $\displaystyle\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{1}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]_{+}-\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{2}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle\geq$ $\displaystyle\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{1}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]-\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{2}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle=$ $\displaystyle(\eta_{1}-\eta_{2})\sum_{a\in{\cal
B}_{s}(\eta_{2})}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})>0,$

yielding

$\displaystyle\sum_{a\neq
a^{\prime}}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{1}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]_{+}$
$\displaystyle\geq\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{1}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]_{+}$
$\displaystyle\geq\sum_{a\in{\cal
B}_{s}(\eta_{2})}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta_{2}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]_{+}\geq
1.$

Together with (2.3) we have $a^{\prime}\not\in{\cal B}_{s}(\eta_{1})$, which
implies ${\cal B}_{s}(\eta_{1})\subseteq{\cal B}_{s}(\eta_{2})$. ∎

The following lemma shows that $A^{\pi}_{s,a}$ should be sufficiently large in
order to be included in the support set of $\pi_{s}^{+}$, which is reasonable.

######  Lemma 2.11.

Consider the prototype update in (2.1). We have

$A_{s,a}^{\pi}\geq\underset{{\tilde{a}}\in\mathcal{A}}{\max}\,\,A_{s,{\tilde{a}}}^{\pi}-\frac{2\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{\pi}\right)}{\eta},\quad\forall
a\in{\cal B}_{s}(\eta).$

###### Proof.

It suffices to consider the third case in Lemma 2.9. According to Lemma 2.8,
for any action $a\in{\cal B}_{s}(\eta)\setminus{\cal A}_{s}^{\pi}$, we have

$\displaystyle 1$
$\displaystyle>\sum_{a^{\prime}\in\mathcal{A}}{\left(\pi_{s,a^{\prime}}+\eta
A_{s,a^{\prime}}^{\pi}-\pi_{s,a}-\eta A_{s,a}^{\pi}\right)_{+}}$
$\displaystyle\geq\sum_{a^{\prime}\in\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a^{\prime}}+\eta
A_{s,a^{\prime}}^{\pi}-\pi_{s,a}-\eta A_{s,a}^{\pi}\right)_{+}}$
$\displaystyle=\sum_{a^{\prime}\in\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a^{\prime}}-\pi_{s,a}+\eta\left(\underset{\tilde{a}\in\mathcal{A}}{\max}A_{s,\tilde{a}}^{\pi}-A_{s,a}^{\pi}\right)\right)_{+}}$
$\displaystyle\geq\sum_{a^{\prime}\in\mathcal{A}_{s}^{\pi}}{\left(\pi_{s,a^{\prime}}-\pi_{s,a}+\eta\left(\underset{\tilde{a}\in\mathcal{A}}{\max}A_{s,\tilde{a}}^{\pi}-A_{s,a}^{\pi}\right)\right)}$
$\displaystyle=\pi_{s}\left(\mathcal{A}_{s}^{\pi}\right)+\left|\mathcal{A}_{s}^{\pi}\right|\left(\eta\left(\underset{\tilde{a}\in\mathcal{A}}{\max}A_{s,\tilde{a}}^{\pi}-A_{s,a}^{\pi}\right)-\pi_{s,a}\right).$

It follows that

$\eta\left(\underset{\tilde{a}\in\mathcal{A}}{\max}A_{s,\tilde{a}}^{\pi}-A_{s,a}^{\pi}\right)\leq\pi_{s,a}+\frac{1-\pi_{s}\left(\mathcal{A}_{s}^{\pi}\right)}{\left|\mathcal{A}_{s}^{\pi}\right|}\leq\left(1+\frac{1}{\left|\mathcal{A}_{s}^{\pi}\right|}\right)\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{\pi}\right)\leq
2\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{\pi}\right).$

The proof is complete after rearrangement. ∎

##  3 Sublinear convergence of PPG for any constant step size

As already mentioned, the sublinear convergence of PQA for any constant step
size has already been developed in [28]. Thus we restrict our focus on PPG in
this section. Apart from the performance difference lemma, the three point
descent lemma is also utilized in [28] to establish the sublinear convergence
of PQA (see Theorem 8 in [28]). However, the technique used for PQA cannot be
used to establish the sublinear convergence of PPG for any constant step size.
Instead, we will utilize the explicit form of the projection onto the
probability simplex to establish the lower bound for the one-step improvement,

$\sum_{a\in\mathcal{A}}{\pi_{s,a}^{k+1}A_{s,a}^{k}}\geq\frac{\left(\underset{a\in\mathcal{A}}{\max}\,A_{s,a}^{k}\right)^{2}}{\underset{a\in\mathcal{A}}{\max}\,A_{s,a}^{k}+C},\quad\forall
s\in\mathcal{S}.$

Combining this result with the performance difference lemma yields that

$V^{k+1}\left(\rho\right)-V^{k}\left(\rho\right)\geq\mathcal{O}\left(\left(V^{*}\left(\rho\right)-V^{k}\left(\rho\right)\right)^{2}\right),$

which directly implies the sublinear convergence of PPG.

Following the notation in the prototype update, the key ingredient in our
analysis is

$\displaystyle f_{s}(\eta_{s}):=\sum_{a\in{\cal
A}}\pi^{+}_{s,a}(\eta_{s})A^{\pi}_{s,a},$

where $\eta_{s}=\frac{\eta d^{\pi}_{\mu}(s)}{1-\gamma}$ for PPG. We first give
an expression for $f_{s}(\eta_{s})$.

######  Lemma 3.1 (Improvement expression).

Consider the prototype update in (2.1). For any $\eta_{s}>0$ one has

$\displaystyle f_{s}(\eta_{s})$ $\displaystyle=\eta_{s}\left(\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left(A^{\pi}_{s,a}\right)^{2}-\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\left(\sum_{a\in{\cal
B}_{s}(\eta_{s})}A^{\pi}_{s,a}\right)^{2}\right)$
$\displaystyle+\sum_{a^{\prime}\in{\cal A}\setminus{\cal
B}_{s}(\eta_{s})}\pi_{s,a^{\prime}}\left(\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\sum_{a\in{\cal
B}_{s}(\eta_{s})}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right).$

The proof of Lemma 3.1 is deferred to Section 3.1. Based on this lemma, we are
able to derive a lower bound for $f_{s}(\eta_{s})$, as stated in the next
lemma whose proof is deferred to Section 3.2.

######  Theorem 3.2 (Improvement lower bound).

Consider the prototype update in (2.1). For any $\eta_{s}>0$ one has

$\displaystyle
f_{s}(\eta_{s})\geq\frac{\left(\max_{a}A^{\pi}_{s,a}\right)^{2}}{\max_{a}A^{\pi}_{s,a}+\frac{2+5|\mathcal{A}|}{\eta_{s}}}.$

With this lower bound, the sublinear convergence of PPG can be established
together with the performance difference lemma.

######  Theorem 3.3 (Sublinear convergence of PPG).

With any constant step size $\eta_{k}=\eta$ and distribution
$\rho\in\Delta({\cal S})$, the policy sequence $\pi^{k}$ generated by PPG
satisfies,

$\displaystyle
V^{*}(\rho)-V^{k}(\rho)\leq\frac{1}{k}\frac{1}{(1-\gamma)^{2}}\left\|\frac{d^{*}_{\rho}}{\rho}\right\|_{\infty}\left(1+\frac{2+5|{\cal
A}|}{\eta\tilde{\mu}}\right).$ (3.1)

######  Remark 3.1.

Compared with the previous results in [28, 2, 31], the result in (3.1) removes
the constraint $\eta_{k}\leq\frac{1}{L}$ on the step size, where
$L=\frac{2\gamma\left|\mathcal{A}\right|}{\left(1-\gamma\right)^{3}}$ is the
smoothness coefficient of the value function. The best sublinear convergence
rate for PPG in prior works is achieved when $\eta_{k}=\frac{1}{L}$, see
(1.10). By setting
$\eta_{k}=\frac{1}{L}=\frac{\left(1-\gamma\right)^{3}}{2\gamma\left|\mathcal{A}\right|}$
and $\rho=\mu$ in (3.1) we can obtain the bound

$V^{*}\left(\mu\right)-V^{k}\left(\mu\right)\leq\frac{1}{k}\frac{1}{\left(1-\gamma\right)^{2}}\left\|\frac{d_{\mu}^{*}}{\mu}\right\|_{\infty}\left(1+\frac{2\gamma\left|\mathcal{A}\right|\left(2+5\left|\mathcal{A}\right|\right)}{\left(1-\gamma\right)^{3}\tilde{\mu}}\right)=\mathcal{O}\left(\frac{1}{k}\frac{\left|\mathcal{A}\right|^{2}}{\left(1-\gamma\right)^{5}}\left\|\frac{d_{\mu}^{*}}{\mu}\right\|_{\infty}\frac{1}{\tilde{\mu}}\right).$

Compared with (1.10), the new bound has the same dependency on the discounted
factor. In addition, the new bound is proportional to
$\left|\mathcal{A}\right|^{2}$ instead of $|{\cal S}||{\cal A}|$, which is
better in the case when $|{\cal S}|>|{\cal A}|$. Since
$\left\|\frac{d_{\mu}^{*}}{\mu}\right\|_{\infty}^{2}\leq\left\|\frac{d_{\mu}^{*}}{\mu}\right\|_{\infty}\frac{1}{\tilde{\mu}}$,
the new bound may have a stronger dependency on the distribution mismatch
coefficient. Moreover, Theorem 3.3 suggests that the best sublinear
convergence rate for PPG is indeed achieved when
$\eta_{k}=\eta\geq\frac{2+5|{\cal A}|}{\tilde{\mu}}$ rather than
$\eta_{k}=\frac{1}{L}$, yielding

$\mathcal{O}\left(\frac{1}{k}\frac{1}{(1-\gamma)^{2}}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}\right).$

###### Proof of Theorem 3.3.

By the performance difference lemma (Lemma 2.3) and Lemma 3.2, one has

$\displaystyle V^{k+1}\left(\rho\right)-V^{k}\left(\rho\right)$
$\displaystyle=\frac{1}{1-\gamma}\sum_{s\in\mathcal{S}}{d_{\rho}^{k+1}\left(s\right)\sum_{a\in\mathcal{A}}{\pi_{s,a}^{k+1}A_{s,a}^{k}}}$
$\displaystyle\geq\mathbb{E}_{s\sim\rho}\left[\frac{\left(\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}\right)^{2}}{\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}+\frac{2+5\left|\mathcal{A}\right|}{\eta^{k}_{s}}}\right]$
$\displaystyle\overset{\left(a\right)}{\geq}\mathbb{E}_{s\sim\rho}\left[\frac{\left(\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}\right)^{2}}{\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}+\frac{2+5\left|\mathcal{A}\right|}{\eta\tilde{\mu}}}\right]$
$\displaystyle=\mathbb{E}_{s\sim\rho}\left[g\left(\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}\right)\right],$
$\displaystyle\geq\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\mathbb{E}_{s\sim
d_{\rho}^{*}}\left[g\left(\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}\right)\right]$
$\displaystyle\overset{\left(b\right)}{\geq}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot
g\left(\mathbb{E}_{s\sim
d_{\rho}^{*}}\left[\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}\right]\right),$
(3.2)

where $g\left(x\right):=\frac{x^{2}}{x+\frac{2+5|{\cal A}|}{\eta\tilde{\mu}}}$
is a convex and monotonically increasing function when $x\geq 0$, (a) is due
to $\eta_{s}^{k}=\frac{\eta d^{k}_{\mu}(s)}{1-\gamma}\geq\eta\tilde{\mu}$
according to inequality (1.15), and (b) is due to the Jensen Inequality.
Notice that

$\displaystyle\mathbb{E}_{s\sim
d_{\rho}^{*}}\left[\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{k}\right]$
$\displaystyle\geq\mathbb{E}_{s\sim
d_{\rho}^{*}}\left[\mathbb{E}_{a\sim\pi_{s}^{*}}\left[A_{s,a}^{k}\right]\right]$
$\displaystyle=\left(1-\gamma\right)\left[\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{\rho}^{*}}\left[\mathbb{E}_{a\sim\pi_{s}^{*}}\left[A_{s,a}^{k}\right]\right]\right]$
$\displaystyle=(1-\gamma)\left(V^{*}(\rho)-V^{k}(\rho)\right).$ (3.3)

Let $\delta_{k}:=V^{*}(\rho)-V^{k}(\rho)$. As $g$ is monotonically increasing,
plugging (3.2) into (3.3) yields that

$\displaystyle\delta_{k}-\delta_{k+1}$
$\displaystyle\geq\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot
g\left(\left(1-\gamma\right)\delta_{k}\right)$
$\displaystyle=\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot\frac{\left(1-\gamma\right)^{2}\delta_{k}^{2}}{\left(1-\gamma\right)\delta_{k}+\frac{2+5\left|\mathcal{A}\right|}{\eta\tilde{\mu}}}.$
(3.4)

Since $\delta_{k}\leq\frac{1}{1-\gamma}$ by Lemma 2.1, we have

$\displaystyle\delta_{k}-\delta_{k+1}$
$\displaystyle\geq\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot\frac{\left(1-\gamma\right)^{2}\delta_{k}^{2}}{1+\frac{2+5\left|\mathcal{A}\right|}{\eta\tilde{\mu}}}.$

This inequality implies that $\delta_{k}$ is monotonically decreasing.
Dividing both sides by $\delta_{k}^{2}$ yields

$\displaystyle\frac{1}{\delta_{k+1}}-\frac{1}{\delta_{k}}=\frac{\delta_{k}-\delta_{k+1}}{\delta_{k}\delta_{k+1}}\geq\frac{\delta_{k}-\delta_{k+1}}{\delta_{k}^{2}}\geq\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot\frac{\left(1-\gamma\right)^{2}}{1+\frac{2+5\left|\mathcal{A}\right|}{\eta\tilde{\mu}}}.$

Consequently,

$\displaystyle\delta_{k}=\frac{1}{\frac{1}{\delta_{k}}}=\frac{1}{\delta_{0}+\sum_{i=0}^{k-1}\left(\frac{1}{\delta_{k+1}}-\frac{1}{\delta_{k}}\right)}\leq\frac{1}{\sum_{i=0}^{k-1}\left(\frac{1}{\delta_{k+1}}-\frac{1}{\delta_{k}}\right)}\leq\frac{1}{k}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}\left(\frac{1}{(1-\gamma)^{2}}+\frac{2+5|{\cal
A}|}{\eta\tilde{\mu}(1-\gamma)^{2}}\right),$

and the proof is complete.

∎

A refined discussion of inequality (3.4) reveals that PPG converges linearly
in the early stage. Roughly speaking, when $\delta_{k}$ is quite large (3.4)
implies that $\delta_{k}-\delta_{k+1}\geq{\cal O}\left(\delta_{k}\right)$,
leading to the linear convergence rate of PPG. Since $\delta_{k}$ will finally
decreases to 0 (Theorem 3.3), the proposition below shows that there exists a
threshold $k_{0}(\eta)$ such that the linear convergence rate can be achieved
when $0<k<k_{0}(\eta)$.

######  Proposition 3.4.

For PPG with arbitrary constant step size $\eta$, denote by $k_{0}$ the first
time that the error $\delta_{k}$ is smaller than $\frac{2+5|{\cal
A}|}{(1-\gamma)\eta\tilde{\mu}}$, i.e.

$k_{0}\left(\eta\right):=\mathrm{inf}\left\\{k\geq
0:\delta_{k}<\frac{2+5|{\cal A}|}{(1-\gamma)\eta\tilde{\mu}}\,\,\right\\}.$

Then

$\displaystyle\delta_{k}\leq\left(1-\frac{1-\gamma}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)^{k}\delta_{0},\quad\forall
0<k<k_{0}(\eta).$

###### Proof.

According the definition of $k_{0}(\eta)$, for $k<k_{0}(\eta)$ we have
$(1-\gamma)\delta_{k}\geq\frac{2+5|{\cal A}|}{\eta\tilde{\mu}}$. Combining it
with inequality (3.4) gives

$\displaystyle\delta_{k}-\delta_{k+1}\geq\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot\frac{\left(1-\gamma\right)\delta_{k}^{2}}{\delta_{k}+\delta_{k}}=\frac{\left(1-\gamma\right)}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\cdot\delta_{k}.$

Thus,

$\delta_{k}\leq\left(1-\frac{\left(1-\gamma\right)}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)\delta_{k-1}\leq...\leq\left(1-\frac{\left(1-\gamma\right)}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)^{k}\delta_{0},$

which completes the proof. ∎

######  Remark 3.2.

Notice that the distribution mismatch coefficient satisfies
$\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}\geq 1$. By setting $\rho$
as the stationary distribution induced by $\pi^{*}$, i.e. $\rho=d^{*}_{\rho}$,
one has $\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}=1$. In this case,
the linear convergence rate in Proposition 3.4 reduces to
$\mathcal{O}\left(\left(\frac{1+\gamma}{2}\right)^{k}\right).$

######  Remark 3.3.

The sublinear linear convergence for PQA can also be established based on a
similar argument as that for PPG, which yields the following sublinear rate,

$V^{*}\left(\rho\right)-V^{k}\left(\rho\right)\leq\frac{1}{k}\frac{1}{\left(1-\gamma\right)^{2}}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}\left(1+\frac{2+5\left|\mathcal{A}\right|}{\eta}\right).$

Compared with (1.13) established in [28], this bound catches the
$\frac{1}{(1-\gamma)^{2}}$ dependency, but overall looses a distribution
mismatch factor.

######  Remark 3.4.

The early stage linear convergence property of PPG in Proposition 3.4 is also
applicable for PQA, which is also new. More precisely, if the value error is
larger than $\frac{2+5\left|\mathcal{A}\right|}{\left(1-\gamma\right)\eta}$,
PQA converges at a rate of
$\mathcal{O}\left(1-\frac{1-\gamma}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)^{k}$.

###  3.1 Proof of Lemma 3.1

Noting that

$\displaystyle 1=\sum_{a\in{\cal A}}\pi_{s,a}$ $\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{s})}\pi^{+}_{s,a}(\eta_{s})$ $\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left[\pi_{s,a}+\eta_{s}A^{\pi}_{s,a}+\lambda_{s}(\eta_{s})\right]_{+}$
$\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left[\pi_{s,a}+\eta_{s}A^{\pi}_{s,a}+\lambda_{s}(\eta_{s})\right],$

we have

$\displaystyle\lambda_{s}(\eta_{s})$ $\displaystyle=\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\left(1-\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left[\pi_{s,a}+\eta_{s}A^{\pi}_{s,a}\right]\right)$
$\displaystyle=\frac{1}{|{\cal B}_{s}(\eta_{s})|}\left(\sum_{a\in{\cal
A}\setminus{\cal B}_{s}(\eta_{s})}\pi_{s,a}-\eta_{s}\sum_{a\in{\cal
B}_{s}(\eta_{s})}A^{\pi}_{s,a}\right).$ (3.5)

It follows that

$\displaystyle f_{s}(\eta_{s})$ $\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{s})}\pi^{+}_{s,a}(\eta_{s})A^{\pi}_{s,a}$
$\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left[\pi_{s,a}+\eta_{s}A^{\pi}_{s,a}+\lambda_{s}(\eta_{s})\right]A^{\pi}_{s,a}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\lambda_{s}(\eta_{s})\sum_{a\in{\cal
B}_{s}(\eta_{s})}A^{\pi}_{s,a}+\eta_{s}\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left(A^{\pi}_{s,a}\right)^{2}-\sum_{a^{\prime}\in{\cal
A}\setminus{\cal B}_{s}(\eta_{s})}\pi_{s,a}A^{\pi}_{s,a}$
$\displaystyle=\eta_{s}\left(\sum_{a\in{\cal
B}_{s}(\eta_{s})}(A^{\pi}_{s,a})^{2}-\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\left(\sum_{a\in{\cal
B}_{s}(\eta_{s})}A^{\pi}_{s,a}\right)^{2}\right)+\sum_{a^{\prime}\in{\cal
A}\setminus{\cal B}_{s}(\eta_{s})}\pi_{s,a^{\prime}}\left(\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\sum_{a\in{\cal
B}_{s}(\eta_{s})}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right),$

where $(a)$ utilizes the fact $\sum_{a\in{\cal
B}_{s}(\eta_{s})}\pi_{s,a}A^{\pi}_{s,a}=0$.

###  3.2 Proof of Theorem 3.2

Without loss of generality, we only consider the case ${\cal
B}_{s}(\eta_{s})\setminus{\cal A}_{s}^{\pi}\neq\emptyset$. First recall the
expression of $f_{s}(\eta_{s})$ in Lemma 3.1:

$\displaystyle
f_{s}(\eta_{s})=\eta_{s}\left(\underset{I_{1}}{\underbrace{\sum_{a\in{\cal
B}_{s}(\eta_{s})}(A^{\pi}_{s,a})^{2}-\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\left(\sum_{a\in{\cal
B}_{s}(\eta_{s})}A^{\pi}_{s,a}\right)^{2}}}\right)+\underset{I_{2}}{\underbrace{\sum_{a^{\prime}\in{\cal
A}\setminus{\cal B}_{s}(\eta_{s})}\pi_{s,a^{\prime}}\left(\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\sum_{a\in{\cal
B}_{s}(\eta_{s})}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right)}}.$

For the term $I_{1}$, it is evident that

$\displaystyle I_{1}$ $\displaystyle=|{\cal
B}_{s}(\eta_{s})|\left(\mathbb{E}_{a\sim
U}\left[\left(A^{\pi}_{s,a}\right)^{2}\right]-\left(\mathbb{E}_{a\sim
U}\left[A^{\pi}_{s,a}\right]\right)^{2}\right)$ $\displaystyle=|{\cal
B}_{s}(\eta_{s})|\cdot\operatorname{Var}_{a\sim U}\left[A^{\pi}_{s,a}\right],$

where $U$ denotes the uniform distribution on the support set ${\cal
B}_{s}(\eta_{s})$. Letting $\Delta_{s,a}^{\pi}:=\underset{a^{\prime}\in{\cal
A}}{\max}\,A^{\pi}_{s,a^{\prime}}-A^{\pi}_{s,a}$,

$\displaystyle I_{1}$ $\displaystyle=|{\cal
B}_{s}(\eta_{s})|\cdot\mathrm{Var}_{a\sim U}\left[A^{\pi}_{s,a}\right]$
$\displaystyle=|{\cal B}_{s}(\eta_{s})|\cdot\mathrm{Var}_{a\sim
U}\left[\Delta^{\pi}_{s,a}\right]$ $\displaystyle=\sum_{a\in{\cal
B}_{s}(\eta_{s})}(\Delta_{s,a}^{\pi})^{2}-\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\left(\sum_{a\in{\cal
B}_{s}(\eta_{s})}\Delta_{s,a}^{\pi}\right)^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{a\in{\cal
B}_{s}(\eta_{s})}(\Delta_{s,a}^{\pi})^{2}-\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\left(\sum_{\tilde{a}\in{\cal B}_{s}(\eta_{s})\setminus{\cal
A}_{s}^{\pi}}\Delta_{s,\tilde{a}}^{\pi}\right)^{2}$
$\displaystyle\geq\sum_{a\in{\cal
B}_{s}(\eta_{s})}(\Delta_{s,a}^{\pi})^{2}-\frac{|{\cal
B}_{s}(\eta_{s})\setminus{\cal A}^{\pi}_{s}|}{|{\cal
B}_{s}(\eta_{s})|}\sum_{\tilde{a}\in{\cal B}_{s}(\eta_{s})\setminus{\cal
A}_{s}^{\pi}}(\Delta_{s,\tilde{a}}^{\pi})^{2}\ $
$\displaystyle=\left(1-\frac{|{\cal B}_{s}(\eta_{s})\setminus{\cal
A}^{\pi}_{s}|}{|{\cal B}_{s}(\eta_{s})|}\right)\sum_{a\in{\cal
B}_{s}(\eta_{s})}(\Delta_{s,a}^{\pi})^{2}$ $\displaystyle=\frac{|{\cal
B}_{s}(\eta_{s})\cap A^{\pi}_{s}|}{|{\cal B}_{s}(\eta_{s})|}\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left(\Delta_{s,a}^{\pi}\right)^{2}$
$\displaystyle\geq\frac{1}{|{\cal B}_{s}(\eta_{s})|}\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left(\Delta_{s,a}^{\pi}\right)^{2},$

where $(a)$ leverages the property that $\Delta_{s,a}^{\pi}=0$ for
$\pi$-optimal actions $a\in{\cal A}_{s}^{\pi}$.

For the term $I_{2}$, we can rewrite it through the notation $\Delta^{\pi}$ as
follows:

$\displaystyle I_{2}=\sum_{a^{\prime}\in{\cal A}\setminus{\cal
B}_{s}(\eta_{s})}\pi_{s,a^{\prime}}\left(\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}\right),$

where $\bar{\Delta}_{s}^{\pi}:=\frac{1}{|{\cal
B}_{s}(\eta_{s})|}\sum_{a\in{\cal B}_{s}(\eta_{s})}\Delta^{\pi}_{s,a}$. By
lemma 2.8, for any action $a^{\prime}\notin{\cal B}_{s}(\eta)$ we have

$\displaystyle\sum_{a\in{\cal B}_{s}(\eta)}\left[\pi_{s,a}+\eta
A^{\pi}_{s,a}-(\pi_{s,a^{\prime}}+\eta A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle\geq\sum_{a\in{\cal B}_{s}(\eta)}\left[\pi_{s,a}+\eta
A^{\pi}_{s,a}-\max_{a\prime\not\in{\cal B}_{s}(\eta)}(\pi_{s,a^{\prime}}+\eta
A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{a\in{\cal
B}_{s}(\eta)}\left[\pi_{s,a}+\eta A^{\pi}_{s,a}-\max_{a\prime\not\in{\cal
B}_{s}(\eta)}(\pi_{s,a^{\prime}}+\eta A^{\pi}_{s,a^{\prime}})\right]_{+}\geq
1,$

where $(a)$ is due to $a\in{\cal B}_{s}(\eta)$ and $a^{\prime}\not\in{\cal
B}_{s}(\eta)$, implying $\pi_{s,a}+\eta A^{\pi}_{s,a}>\pi_{s,a^{\prime}}+\eta
A^{\pi}_{s,a^{\prime}}$. It follows that

$\displaystyle 1$ $\displaystyle\leq\sum_{a\in{\cal
B}_{s}(\eta)}\left[\pi_{s,a}-\pi_{s,a^{\prime}}+\eta(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})\right]$
$\displaystyle=\eta\sum_{a\in{\cal
B}_{s}(\eta)}(A^{\pi}_{s,a}-A^{\pi}_{s,a^{\prime}})-|{\cal
B}_{s}(\eta)|\pi_{s,a^{\prime}}+\sum_{a\in{\cal B}_{s}(\eta)}\pi_{s,a},$

which yields

$\displaystyle\frac{1}{\left|{\cal
B}_{s}\left(\eta\right)\right|}\sum_{a\in{\cal
B}_{s}\left(\eta\right)}\left({A_{s,a}^{\pi}}-A_{s,a^{\prime}}^{\pi}\right)\geq\frac{1}{\eta\left|{\cal
B}_{s}\left(\eta\right)\right|}\left(1-\sum_{a\in{\cal
B}_{s}\left(\eta\right)}{\pi_{s,a}}+\left|{\cal
B}_{s}\left(\eta\right)\right|\pi_{s,a^{\prime}}\right)\geq\frac{\pi_{s,a^{\prime}}}{\eta}.$

Using the notation of $\Delta^{\pi}_{s,a}$ and $\bar{\Delta}^{\pi}_{s}$, this
inequality can be reformulated as

$\displaystyle\forall a^{\prime}\in{\cal A}\setminus{\cal
B}_{s}(\eta_{s}):\quad\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}\geq\frac{\pi_{s,a^{\prime}}}{\eta_{s}}.$
(3.6)

Let ${\cal B}_{s}(0):=\mathrm{supp}(\pi_{s})=\left\\{a:\pi_{s,a}>0\right\\}$.
By (3.6) we know that

$\displaystyle\forall a^{\prime}\in\left({\cal A}\setminus{\cal
B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0):\quad\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}\geq\frac{\pi_{s,a^{\prime}}}{\eta_{s}}>0.$
(3.7)

Furthermore,

$\displaystyle I_{2}=\sum_{a^{\prime}\in{\cal A}\setminus{\cal
B}_{s}(\eta_{s})}\pi_{s,a^{\prime}}\left(\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}\right)=\sum_{a^{\prime}\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}\pi_{s,a^{\prime}}\left(\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}\right).$

Combining $I_{1}$ and $I_{2}$ together, we have

$\displaystyle f_{s}(\eta_{s})\geq\frac{\eta_{s}}{|{\cal
B}_{s}(\eta_{s})|}\sum_{a\in{\cal
B}_{s}(\eta_{s})}\left(\Delta_{s,a}^{\pi}\right)^{2}+\sum_{a^{\prime}\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}\pi_{s,a^{\prime}}(\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}).$

By Cauchy-Schwarz Inequality,

$\displaystyle
f_{s}\left(\eta_{s}\right)\times\left(\frac{\left|\mathcal{B}_{s}\left(\eta_{s}\right)\right|}{\eta_{s}}\sum_{a\in\mathcal{B}_{s}\left(\eta_{s}\right)}{\left(\pi_{s,a}\right)^{2}}+\sum_{a^{\prime}\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a^{\prime}}}\frac{\left(\Delta_{s,a^{\prime}}^{\pi}\right)^{2}}{\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}}\right)$
$\displaystyle\geq\left(\frac{\eta_{s}}{\left|\mathcal{B}_{s}\left(\eta_{s}\right)\right|}\sum_{a\in\mathcal{B}_{s}\left(\eta_{s}\right)}{\left(\Delta_{s,a}^{\pi}\right)^{2}}+\sum_{a^{\prime}\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a^{\prime}}}\left(\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}\right)\right)$
$\displaystyle\times\left(\frac{\left|\mathcal{B}_{s}\left(\eta_{s}\right)\right|}{\eta_{s}}\sum_{a\in\mathcal{B}_{s}\left(\eta_{s}\right)}{\left(\pi_{s,a}\right)^{2}}+\sum_{a^{\prime}\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a^{\prime}}}\frac{\left(\Delta_{s,a^{\prime}}^{\pi}\right)^{2}}{\Delta_{s,a^{\prime}}^{\pi}-\bar{\Delta}_{s}^{\pi}}\right)$
$\displaystyle\geq\left(\sum_{a\in\mathcal{B}_{s}\left(\eta_{s}\right)}{\pi_{s,a}\Delta_{s,a}^{\pi}}+\sum_{a^{\prime}\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a^{\prime}}}\Delta_{s,a^{\prime}}^{\pi}\right)^{2}$
$\displaystyle{=}\left(\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{\pi}\right)^{2}.$

Therefore, we can obtain

$f_{s}(\eta_{s})\geq\frac{1}{G}\left(\underset{a\in{\cal A}}{\max}{\cal
A}^{\pi}_{s,a}\right)^{2},$

where

$\displaystyle
G:=\underset{G_{1}}{\underbrace{\frac{\left|\mathcal{B}_{s}\left(\eta_{s}\right)\right|}{\eta_{s}}\sum_{a\in\mathcal{B}_{s}\left(\eta_{s}\right)}{\left(\pi_{s,a}\right)^{2}}}}+\underset{G_{2}}{\underbrace{\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}\frac{\left(\Delta_{s,a}^{\pi}\right)^{2}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}}}.$

Next we will give an upper bound of $G$. For the term $G_{1}$, it is
straightforward to see that

$G_{1}<\frac{\left|\mathcal{B}_{s}\left(\eta_{s}\right)\right|}{\eta_{s}}\left(\sum_{a\in\mathcal{B}_{s}\left(\eta_{s}\right)}{\pi_{s,a}}\right)^{2}<\frac{\left|\mathcal{A}\right|}{\eta_{s}}.$

For the term $G_{2}$, a direct computation yields that,

$\displaystyle G_{2}$ $\displaystyle=\sum_{a\in\left({\cal A}\setminus{\cal
B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}\frac{\left(\Delta_{s,a}^{\pi}\right)^{2}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}$
$\displaystyle=\sum_{a\in\left({\cal A}\setminus{\cal
B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}\frac{\left(\Delta_{s,a}^{\pi}\right)^{2}-\left(\bar{\Delta}_{s}^{\pi}\right)^{2}+\left(\bar{\Delta}_{s}^{\pi}\right)^{2}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}$
$\displaystyle=\sum_{a\in\left({\cal A}\setminus{\cal
B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}\left(\Delta_{s,a}^{\pi}+\bar{\Delta}_{s}^{\pi}+\frac{\left(\bar{\Delta}_{s}^{\pi}\right)^{2}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}\right)}$
$\displaystyle=\sum_{a\in\left({\cal A}\setminus{\cal
B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}\Delta_{s,a}^{\pi}}+\bar{\Delta}_{s}^{\pi}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}+\left(\bar{\Delta}_{s}^{\pi}\right)^{2}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\frac{\pi_{s,a}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}}$
$\displaystyle\leq\sum_{a\in\mathcal{A}}{\pi_{s,a}\Delta_{s,a}^{\pi}}+\bar{\Delta}_{s}^{\pi}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}+\left(\bar{\Delta}_{s}^{\pi}\right)^{2}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\frac{\pi_{s,a}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}}$
$\displaystyle=\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{\pi}+\bar{\Delta}_{s}^{\pi}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}+\left(\bar{\Delta}_{s}^{\pi}\right)^{2}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\frac{\pi_{s,a}}{\Delta_{s,a}^{\pi}-\bar{\Delta}_{s}^{\pi}}}.$
(3.8)

Lemma 2.11 shows that

$\displaystyle\forall a\in{\cal
B}_{s}(\eta_{s}):\Delta_{s,a}^{\pi}\leq\frac{2\pi_{s}({\cal A}\setminus{\cal
A}_{s}^{\pi})}{\eta_{s}}\leq\frac{2}{\eta_{s}}\quad\Longrightarrow\quad\bar{\Delta}_{s}^{\pi}\leq\frac{2}{\eta_{s}}.$
(3.9)

Plugging (3.7) and (3.9) into (3.8) we have

$\displaystyle G_{2}$
$\displaystyle\leq\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{\pi}+\frac{2}{\eta_{s}}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}+\left(\frac{2}{\eta_{s}}\right)^{2}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\frac{\pi_{s,a}}{\frac{1}{\eta_{s}}\pi_{s,a}}}$
$\displaystyle=\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{\pi}+\frac{2}{\eta_{s}}\sum_{a\in\left({\cal
A}\setminus{\cal B}_{s}(\eta_{s})\right)\cap{\cal
B}_{s}(0)}{\pi_{s,a}}+\frac{4}{\eta_{s}}\sum_{a\in\left({\cal A}\setminus{\cal
B}_{s}(\eta_{s})\right)\cap{\cal B}_{s}(0)}{1}$
$\displaystyle\leq\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{\pi}+\frac{2+4\left|\mathcal{A}\right|}{\eta_{s}}.$

Thus we can finally obtain

$G=G_{1}+G_{2}\leq\underset{a\in\mathcal{A}}{\max}\,\,A_{s,a}^{\pi}+\frac{2+5\left|\mathcal{A}\right|}{\eta_{s}},$

and

$\displaystyle
f_{s}(\eta_{s})\geq\frac{\left(\max_{a}A^{\pi}_{s,a}\right)^{2}}{G}\geq\frac{\left(\max_{a}A^{\pi}_{s,a}\right)^{2}}{\max_{a}A^{\pi}_{s,a}+\frac{2+5|\mathcal{A}|}{\eta_{s}}}.$
(3.10)

##  4 Finite iteration convergence results

###  4.1 Finite iteration convergence of PPG and PQA

In this section, we show that both PPG and PQA output an optimal policy after
a finite iteration $k_{0}$ and we will use the sublinear analysis (Theorem 3.3
for PPG and (1.13) for PQA) to derive an upper bound of $k_{0}$. The overall
idea is first sketched as follows. For an arbitrary $s\in\mathcal{S}$, letting
$\mathcal{B}=\mathcal{A}^{*}_{s}$, $\mathcal{C}={\cal
A}\setminus\mathcal{A}^{*}_{s}$ in Lemma 2.8 (recall that ${\cal A}^{*}_{s}$
is the set of optimal actions, i.e. $\pi^{*}$-optimal actions), we have

$\displaystyle\forall
a^{\prime}\notin\mathcal{A}_{s}^{*},\;\;\pi_{s,a^{\prime}}^{+}=0\;\Longleftrightarrow\;\sum_{a\in\mathcal{A}_{s}^{*}}{\left(\pi_{s,a}+\eta_{s}A_{s,a}^{\pi}-\underset{a^{\prime}\notin\mathcal{A}_{s}^{*}}{\max}\left(\pi_{s,a^{\prime}}+\eta_{s}A_{s,a^{\prime}}^{\pi}\right)\right)_{+}}\geq
1.$ (4.1)

By the definition of $b^{\pi}_{s}$ and $\Delta$,

$\displaystyle
b_{s}^{\pi}=\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{*}\right),\quad\quad\Delta=\underset{s\in\tilde{S},a\notin\mathcal{A}_{s}^{*}}{\min}\left|A^{*}(s,a)\right|,$

when $V^{\pi}$ is sufficiently close to $V^{*}$, we know that for any
$a^{\prime}\notin{\cal A}^{*}_{s}$,

$\sum_{a\in\mathcal{A}_{s}^{*}}{\pi_{s,a}}\approx
1,\;\;A_{s,a}^{\pi}-A_{s,a^{\prime}}^{\pi}\approx
A_{s,a}^{*}-A_{s,a^{\prime}}^{*}\geq\Delta.$

Since $\pi_{s,a^{\prime}}\leq b_{s}^{\pi}$, we asymptotically have

$\sum_{a\in\mathcal{A}_{s}^{*}}{\left(\pi_{s,a}+\eta_{s}A_{s,a}^{\pi}-\underset{a^{\prime}\notin\mathcal{A}_{s}^{*}}{\max}\left(\pi_{s,a^{\prime}}+\eta_{s}A_{s,a^{\prime}}^{\pi}\right)\right)_{+}}\geq
1-\mathcal{O}\left(b_{s}^{\pi}\right)+\mathcal{O}\left(\Delta\right).$

This implies that if $b^{\pi}_{s}$ is sufficiently small, the condition in
(4.1) will be met. Then both PPG and PQA will output the optimal policy.

######  Lemma 4.1 (Optimality condition).

Consider the prototype update in (2.1). Define

$\varepsilon^{\pi}_{s,a}:=\eta_{s}\left(A^{\pi}_{s,a}-A^{*}_{s,a}\right)\quad\mbox{and}\quad\varepsilon^{\pi}_{s}:=[\varepsilon_{s,a}^{\pi}]_{a\in\mathcal{A}}.$

If the input policy $\pi$ satisfies,

$\displaystyle
b_{s}^{\pi}+\|\varepsilon_{s}^{\pi}\|_{\infty}\leq\frac{\eta_{s}\Delta}{2},\quad\forall
s\in\mathcal{S},$ (4.2)

then $\pi^{+}=\pi^{*}$, i.e., $\pi^{+}_{s}=\pi^{*}_{s}$ for all $s\in{\cal
S}$.

###### Proof.

For any $s\in{\cal S}$, a direction computation yields that

$\displaystyle\sum_{a\in\mathcal{A}_{s}^{*}}{\left(\pi_{s,a}+\eta_{s}A_{s,a}^{\pi}-\max_{a^{\prime}\notin\mathcal{A}_{s}^{*}}\left(\pi_{s,a^{\prime}}+\eta_{s}A_{s,a^{\prime}}^{\pi}\right)\right)_{+}}$
$\displaystyle\geq\sum_{a\in\mathcal{A}_{s}^{*}}{\left(\pi_{s,a}+\eta_{s}A_{s,a}^{\pi}-\max_{a^{\prime}\notin\mathcal{A}_{s}^{*}}\left(\pi_{s,a^{\prime}}+\eta_{s}A_{s,a^{\prime}}^{\pi}\right)\right)}$
$\displaystyle\overset{\left(a\right)}{=}\sum_{a\in\mathcal{A}_{s}^{*}}{\left(\pi_{s,a}+\eta_{s}A_{s,a}^{\pi}-\left(\pi_{s,\tilde{a}}+\eta_{s}A_{s,\tilde{a}}^{\pi}\right)\right)}$
$\displaystyle=\sum_{a\in\mathcal{A}_{s}^{*}}{\left[\left(\pi_{s,a}-\eta_{s}\left|A_{s,a}^{*}\right|+\varepsilon_{s,a}^{k}\right)-\left(\pi_{s,\tilde{a}}-\eta_{s}\left|A_{s,\tilde{a}}^{*}\right|+\varepsilon_{s,\tilde{a}}^{\pi}\right)\right]}$
$\displaystyle\overset{\left(b\right)}{=}\sum_{a\in\mathcal{A}_{s}^{*}}{\left[\left(\pi_{s,a}+\varepsilon_{s,a}^{k}\right)-\left(\pi_{s,\tilde{a}}-\eta_{s}\left|A_{s,\tilde{a}}^{*}\right|+\varepsilon_{s,\tilde{a}}^{\pi}\right)\right]}$
$\displaystyle\overset{\left(c\right)}{\geq}\sum_{a\in\mathcal{A}_{s}^{*}}{\left[\left(\pi_{s,a}-\pi_{s,\tilde{a}}\right)+\eta_{s}\Delta+\left(\varepsilon_{s,a}^{\pi}-\varepsilon_{s,\tilde{a}}^{\pi}\right)\right]}$
$\displaystyle\geq\sum_{a\in\mathcal{A}_{s}^{*}}{\left[\left(\pi_{s,a}-b_{s}^{\pi}\right)+\eta_{s}\Delta-2\left\|\varepsilon_{s}^{\pi}\right\|_{\infty}\right]}$
$\displaystyle=\sum_{a\in\mathcal{A}_{s}^{*}}{\pi_{s,a}}+\left|\mathcal{A}_{s}^{*}\right|\left(\eta_{s}\Delta-
b_{s}^{\pi}-2\left\|\varepsilon_{s}^{\pi}\right\|_{\infty}\right)$
$\displaystyle=1-b_{s}^{\pi}+\left|\mathcal{A}_{s}^{*}\right|\left(\eta_{s}\Delta-
b_{s}^{\pi}-2\left\|\varepsilon_{s}^{\pi}\right\|_{\infty}\right)$
$\displaystyle\geq
1-\left|\mathcal{A}_{s}^{*}\right|b_{s}^{\pi}+\left|\mathcal{A}_{s}^{*}\right|\left(\eta_{s}\Delta-
b_{s}^{\pi}-2\left\|\varepsilon_{s}^{\pi}\right\|_{\infty}\right)$
$\displaystyle=1+\left|\mathcal{A}_{s}^{*}\right|\left[\eta_{s}\Delta-2\left(b_{s}^{\pi}+\left\|\varepsilon_{s}^{\pi}\right\|_{\infty}\right)\right]$
$\displaystyle\geq 1,$

where
$\tilde{a}:=\mathrm{argmax}_{a^{\prime}\notin\mathcal{A}_{s}^{*}}\,\,\left\\{\pi_{s,a^{\prime}}^{k}+\eta_{s}A_{s,a^{\prime}}^{k}\right\\}$
in $(a)$, $(b)$ is due to $A^{*}_{s,a}=0$ for all $a\in\mathcal{A}^{*}_{s}$,
and $(c)$ follows from the definition of $\Delta$. Combining this result with
Lemma 2.8 we obtain that

$\displaystyle\pi_{s,a}^{+}=0,\quad\forall a\notin\mathcal{A}_{s}^{*}.$

which means $\pi^{+}$ is an optimal policy. ∎

Next we will show that the LHS of (4.2) is actually of order
$\mathcal{O}\left(\left\|V^{*}-V^{k}\right\|_{\infty}\right).$ Thus the
condition (4.2) can be satisfied provided the value error converges to zero
and step sizes are constant (in this case the RHS of (4.2) is
$\mathcal{O}(\Delta)$).

######  Lemma 4.2 (Optimality condition continued in terms of state values).

Consider the prototype update in (2.1). If the state values of the input
policy $\pi$ satisfies,

$\displaystyle\left\|V^{*}-V^{\pi}\right\|_{\infty}\leq\frac{\Delta}{2}\frac{\eta_{s}\Delta}{1+\eta_{s}\Delta},\quad\forall
s\in\mathcal{S},$ (4.3)

then $\pi^{+}=\pi^{*}$, i.e. $\pi^{+}_{s}=\pi^{*}_{s}$ for all $s\in{\cal S}$.

###### Proof.

For any $s\in\mathcal{S}$, setting
$\rho\left(\cdot\right)=\mathbb{I}\left(\cdot=s\right)$ in Lemma 2.5, where
$\mathbb{I}$ is the indicator function, yields that

$\displaystyle
b_{s}^{\pi}\leq\frac{V^{*}\left(s\right)-V^{\pi}\left(s\right)}{\Delta}\leq\frac{\left\|V^{*}-V^{\pi}\right\|_{\infty}}{\Delta}.$

Combining this result with Lemma 2.2 we have

$\displaystyle\underset{s\in\mathcal{S}}{\max}\,\,b_{s}^{\pi}+\left\|\varepsilon_{s}^{\pi}\right\|_{\infty}\leq\frac{1}{\Delta}\left\|V^{*}-V^{\pi}\right\|_{\infty}+\eta_{s}\left\|V^{*}-V^{\pi}\right\|_{\infty}=\left(\frac{1}{\Delta}+\eta_{s}\right)\left\|V^{*}-V^{\pi}\right\|_{\infty}.$
(4.4)

The proof is completed by noting the assumption and Lemma 4.1. ∎

Since the sublinear convergence of PPG (Theorem 3.3) and PQA ((1.13)) has
already been established, there must exist an iteration $k_{0}$ such that
$\left\|V^{*}-V^{k}\right\|_{\infty}$ is smaller than the threshold given in
Lemma 4.2.

######  Theorem 4.3 (Finite iteration convergence of PPG).

With any constant step size $\eta_{k}=\eta>0$, PPG terminates after at most

$\displaystyle
k_{0}:=\left\lceil\frac{2}{\Delta}\left(1+\frac{1}{\eta\tilde{\mu}\Delta}\right)\frac{1}{\tilde{\mu}(1-\gamma)^{2}}\left\|\frac{d^{*}_{\mu}}{\mu}\right\|_{\infty}\left(1+\frac{2+5|{\cal
A}|}{\eta\tilde{\mu}}\right)\right\rceil$

iterations.

###### Proof.

Since $\eta^{k}_{s}=\frac{\eta d^{k}_{\mu}(s)}{1-\gamma}>\eta\tilde{\mu}$ for
PPG, the RHS of (4.3) satisfies

$\displaystyle\frac{\Delta}{2}\frac{\eta_{s}^{k}\Delta}{1+\eta_{s}^{k}\Delta}\geq\frac{\Delta}{2}\frac{\eta\tilde{\mu}\Delta}{1+\eta\tilde{\mu}\Delta}.$
(4.5)

According to Lemma 2.2 and Theorem 3.3,

$\displaystyle\left\|V^{*}-V^{k}\right\|_{\infty}$
$\displaystyle\leq\frac{V^{*}\left(\mu\right)-V^{k}\left(\mu\right)}{\tilde{\mu}}$
$\displaystyle\leq\frac{1}{k}\frac{1}{(1-\gamma)^{2}}\left\|\frac{d^{*}_{\mu}}{\mu}\right\|_{\infty}\frac{1}{\tilde{\mu}}\left(1+\frac{2+5|{\cal
A}|}{\eta\tilde{\mu}}\right)$
$\displaystyle\leq\frac{\Delta}{2}\frac{\eta_{s}\Delta}{1+\eta_{s}\Delta},$
(4.6)

where the last inequality follows from (4.5) and the expression of $k_{0}$. ∎

######  Theorem 4.4 (Finite iteration convergence of PQA).

With any constant step size $\eta_{k}=\eta>0$, PQA terminates after at most

$k_{0}:=\left\lceil\frac{2}{\Delta}\left(1+\frac{1}{\eta\Delta}\right)\left(\frac{1}{\eta\left(1-\gamma\right)}+\frac{1}{\left(1-\gamma\right)^{2}}\right)-1\right\rceil$

iterations.

###### Proof.

Plugging $\rho_{s}\left(\cdot\right):=\mathbb{I}\left\\{\cdot=s\right\\}$ into
(1.13) yields that

$\displaystyle V^{*}\left(s\right)-V^{k}\left(s\right)$
$\displaystyle\leq\frac{1}{k+1}\left(\frac{\mathbb{E}_{s\sim
d_{\rho_{s}}^{*}}\left[\left\|\pi_{s}^{*}-\pi_{s}^{0}\right\|_{2}^{2}\right]}{2\eta\left(1-\gamma\right)}+\frac{1}{\left(1-\gamma\right)^{2}}\right)$
$\displaystyle\leq\frac{1}{k+1}\left(\frac{1}{\eta\left(1-\gamma\right)}+\frac{1}{\left(1-\gamma\right)^{2}}\right).$

Since this bound holds for any $s$, it also holds for
$\|V^{*}-V^{k}\|_{\infty}$. Then it can be easily verified that the condition
in Lemma 4.2 is satisified given the expression of $k_{0}$. ∎

######  Remark 4.1.

On the one hand, when the value error $\delta_{k}:=V^{*}(\rho)-V^{k}(\rho)$ is
larger than
$\frac{2+5\left|\mathcal{A}\right|}{\left(1-\gamma\right)\eta\tilde{\mu}}$,
PPG exhibits the linear convergence of
$\left(1-\frac{1-\gamma}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)^{k}$
by Proposition 3.4. On the other hand, the proof in Theorem 4.3 indicates that
PPG terminates if the value error with respect to the infinite norm is smaller
than $\frac{\Delta}{2}\frac{\eta\tilde{\mu}\Delta}{1+\eta\tilde{\mu}\Delta}$.
Thus, by setting

$\displaystyle\frac{2+5\left|\mathcal{A}\right|}{\left(1-\gamma\right)\eta\tilde{\mu}}<\frac{\Delta}{2}\frac{\eta\tilde{\mu}\Delta}{1+\eta\tilde{\mu}\Delta},$
(4.7)

PPG enjoys the linear convergence rate of
$\left(1-\frac{1-\gamma}{2}\left\|\frac{d_{\rho}^{*}}{\rho}\right\|_{\infty}^{-1}\right)^{k}$
before termination. This case also holds for PQA if the constant step $\eta$
size satisfies

$\displaystyle\frac{2+5\left|\mathcal{A}\right|}{\left(1-\gamma\right)\eta}<\frac{\Delta}{2}\frac{\eta\Delta}{1+\eta\Delta}.$
(4.8)

It is trivial to see that the inequalities (4.7) and (4.8) hold if $\eta$ is
large enough.

###  4.2 Finite iteration convergence of PI and VI

As a by-product, we will derive a new dimension-free bound for the finite
iteration convergence of PI and VI in terms of $\Delta$ in this section. The
following lemma demonstrates that once the state values of a policy are
sufficiently close to the optimal state values, the current optimal action set
$\mathcal{A}^{\pi}_{s}$ will be included in the global optimal action set
$\mathcal{A}^{*}_{s}$.

######  Lemma 4.5.

For any policy $\pi\in\Pi$, if

$\gamma\left\|V^{*}-V^{\pi}\right\|_{\infty}\leq\frac{\Delta}{3},$

then for all $s\in\mathcal{S}$,
$\mathcal{A}_{s}^{\pi}\subset\mathcal{A}_{s}^{*}$.

###### Proof.

By lemma 2.1 we know that

$\displaystyle\left\|Q^{*}-Q^{\pi}\right\|_{\infty}\leq\gamma\left\|V^{*}-V^{\pi}\right\|_{\infty}\leq\frac{\Delta}{3},$

from which the claim follows directly. ∎

######  Theorem 4.6 (Finite iteration convergence of PI).

PI terminates after at most

$\displaystyle
k_{0}=\left\lceil\frac{1}{1-\gamma}\log\left(\frac{3}{(1-\gamma)\Delta}\right)\right\rceil$

iterations.

###### Proof.

Notice that the value error generated by PI satisfies,

$\left\|V^{*}-V^{k}\right\|_{\infty}\leq\gamma^{k}\left\|V^{*}-V^{0}\right\|_{\infty}\leq\frac{\gamma^{k}}{1-\gamma},$

see for example [5] for the proof. According to Lemma 4.5, when

$\displaystyle\frac{\gamma^{k+1}}{1-\gamma}\leq\frac{\Delta}{3},$ (4.9)

we have $\mathcal{A}^{k}_{s}\subset\mathcal{A}^{*}_{s}$ after that. It’s
trivial to verify that (4.9) holds for $\pi^{k}$ when $k\geq k_{0}$. Since PI
puts all the probabilities on the action set $\mathcal{A}^{k}_{s}$ in each
iteration, we have ${\cal A}_{s}^{k}\subset{\cal A}^{*}_{s}$ when $k\geq
k_{0}$, which implies PI outputs an optimal policy after $k_{0}$. ∎

######  Remark 4.2.

It is well-known that PI is a strong polynomial algorithm (see for example
[22]), which means that PI outputs an optimal policy within at most
$\mathcal{O}\left(\frac{\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{1-\gamma}\log\frac{1}{1-\gamma}\right)$
iterations. Compared with this strong polynomial bound, the bound in Theorem
4.6 is dimension-free but relies on the parameter $\Delta$ that depends on the
particular DMDP problem. The dimension-free bound is better in the case
$\frac{1}{\Delta}=o\left(\frac{1}{\left(1-\gamma\right)^{\left|\mathcal{S}\right|\left|\mathcal{A}\right|}}\right)$.

######  Theorem 4.7.

Let $\pi^{k}$ be the sequence of greedy policy generated by $V^{k}$ in VI
(Note that $V^{k}$ is not necessarily a value function of $\pi^{k}$). Then
after at most

$k_{0}:=\left\lceil\frac{1}{\left(1-\gamma\right)}\log\left(\frac{6}{\Delta}\frac{1}{\left(1-\gamma\right)^{2}}\right)\right\rceil$

iterations, $\pi^{k}$ is one of the optimal policies.

###### Proof.

According to Lemma 2.6, we have

$\left\|V^{*}-V^{\pi^{k}}\right\|_{\infty}\leq\frac{2\gamma}{1-\gamma}\left\|V-V^{k}\right\|_{\infty}\leq\frac{2\gamma^{k+1}}{\left(1-\gamma\right)^{2}}\leq\frac{\Delta}{3}.$

Then the proof is completed following the same argument as in the proof of
Theorem 4.6. ∎

######  Remark 4.3.

It is worth noting that since VI does not evaluate the value function of
$\pi^{k}$ in each iteration, Theorem 4.7 does not really mean the algorithm
terminates in a finite number of iterations.

##  5 Linear convergence and equivalence to PI

###  5.1 Linear convergence of PPG under non-adaptive increasing step sizes

In Proposition 3.4, we have shown that PPG enjoys linear convergence in the
early stage of the iterations for constant step sizes. In this section, we
further show that with increasing step sizes $\eta_{k}\geq{\cal
O}\left(\frac{1}{\gamma^{2k}}\right)$, the classical $\gamma$-rate linear
convergence can be achieved globally.

######  Theorem 5.1.

Consider the prototype update in (2.1). Suppose the step size in the $k$-th
iteration satisfies

$\displaystyle\eta^{k}_{s}\geq\frac{1}{\gamma^{2k+1}c_{0}}\cdot
2\pi_{s}^{k}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{k}\right),\quad\forall
s\in\mathcal{S}$ (5.1)

for a given constant $c_{0}>0$. Then the value errors satisfy

$\left\|V^{*}-V^{k}\right\|_{\infty}<\gamma^{k}\left(\left\|V^{*}-V^{0}\right\|_{\infty}+\frac{c_{0}}{1-\gamma}\right).$

###### Proof.

For simplicity of notation, let
$\tilde{\eta}_{s}^{k}:=\frac{2\pi_{s}^{k}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{k}\right)}{\eta_{s}^{k}}$.
According to Lemma 2.11, for any $k>0$ and $s\in{\cal S}$,

$\sum_{a\in\mathcal{A}}{\pi_{s,a}^{k+1}Q_{s,a}^{k}}\geq\sum_{a\in\mathcal{A}}{\pi_{s,a}^{k+1}\left(\underset{\tilde{a}\in\mathcal{A}}{\max}\,Q_{s,\tilde{a}}^{k}-\tilde{\eta}_{s}^{k}\right)}=\underset{\tilde{a}\in\mathcal{A}}{\max}\,Q_{s,\tilde{a}}^{k}-\tilde{\eta}_{s}^{k}.$

Then

$\displaystyle V^{*}\left(s\right)-V^{k+1}\left(s\right)$
$\displaystyle=V^{*}\left(s\right)-\mathbb{E}_{a\sim\pi_{s}^{k+1}}\left[Q^{k+1}_{s,a}\right]$
$\displaystyle\leq
V^{*}\left(s\right)-\mathbb{E}_{a\sim\pi_{s}^{k+1}}\left[Q^{k}_{s,a}\right]$
$\displaystyle\leq
V^{*}\left(s\right)-\left(\underset{\tilde{a}\in\mathcal{A}}{\max}\,Q_{s,\tilde{a}}^{k}-\tilde{\eta}^{k}_{s}\right)$
$\displaystyle=\underset{a\in\mathcal{A}}{\max}\,Q^{*}_{s,a}-\underset{\tilde{a}\in\mathcal{A}}{\max}\,Q_{s,\tilde{a}}^{k}+\tilde{\eta}^{k}_{s}$
$\displaystyle\leq\gamma\left\|V^{*}-V^{k}\right\|_{\infty}+\tilde{\eta}^{k}_{s},$

where in the first inequality we have used the fact $Q^{k+1}_{s,a}\leq
Q^{k}_{s,a}$ due to the improvement. It follows that

$\displaystyle\left\|V^{*}-V^{k}\right\|_{\infty}$
$\displaystyle\leq\gamma\left\|V^{*}-V^{k-1}\right\|_{\infty}+\underset{s\in\mathcal{S}}{\max}\,\tilde{\eta}_{s}^{k}$
$\displaystyle\,\,\leq\gamma^{2}\left\|V^{*}-V^{k-2}\right\|_{\infty}+\gamma\underset{s\in\mathcal{S}}{\max}\,\tilde{\eta}_{s}^{k-1}+\underset{s\in\mathcal{S}}{\max}\,\tilde{\eta}_{s}^{k}$
$\displaystyle\,\,\leq...$
$\displaystyle\,\,\leq\gamma^{k}\left\|V^{*}-V^{0}\right\|_{\infty}+\sum_{i=0}^{k-1}{\left(\underset{s\in\mathcal{S}}{\max}\,\tilde{\eta}_{s}^{i}\right)\gamma^{k-1-i}}$
(5.2)

Notice that the condition (5.1) is equivalent to

$\underset{s\in\mathcal{S}}{\max}\,\tilde{\eta}_{s}^{i}\leq
c_{0}\gamma^{2i+1}.$

Plugging it into (5.2) yields

$\left\|V^{*}-V^{k}\right\|_{\infty}\leq\gamma^{k}\left\|V^{*}-V^{0}\right\|_{\infty}+c_{0}\sum_{i=0}^{k-1}{\gamma^{2i+1}\gamma^{k-1-i}}<\gamma^{k}\left(\left\|V^{*}-V^{0}\right\|_{\infty}+\frac{c_{0}}{1-\gamma}\right),$

which completes the proof. ∎

The $\gamma$-rate linear convergence of PPG follows immediately by noting that
$\eta_{s}^{k}=\eta_{k}\frac{d_{\mu}^{k}(s)}{1-\gamma}$ in PPG and
$d_{\mu}^{k}(s)\geq(1-\gamma)\tilde{\mu}$.

######  Proposition 5.2.

For PPG, if
$\eta_{k}\geq\frac{1}{\tilde{\mu}}\frac{1}{c_{0}}\frac{2}{\gamma^{2k+1}},$
then

$\left\|V^{*}-V^{k}\right\|_{\infty}<\gamma^{k}\left(\left\|V^{*}-V^{0}\right\|_{\infty}+\frac{c_{0}}{1-\gamma}\right).$

######  Remark 5.1.

The $\gamma$-rate linear convergence of PQA can be similarly obtained from
Theorem 5.1 provided $\eta_{k}\geq\frac{1}{c_{0}}\frac{2}{\gamma^{2k+1}}$.
Note that this result can also be obtained from Theorem 1 in [11]. More
precisely, it is shown in [11] that if

$\displaystyle\eta_{k}\geq\frac{1}{\gamma^{2\left(k+1\right)}c_{0}}\underset{s\in\mathcal{S}}{\max}\left\\{\underset{\tilde{\pi}_{s}^{k+1}\in\tilde{\Pi}_{s}^{k+1}}{\min}\frac{1}{2}\left\|\tilde{\pi}_{s}^{k+1}-\pi_{s}^{k}\right\|_{2}^{2}\right\\},\quad\mbox{where
}\tilde{\Pi}_{s}^{k+1}=\\{p\in\Delta\left(\mathcal{A}\right):\sum_{a\in\mathcal{A}_{s}^{k}}{p\left(a\right)}=1\\},$

then the value errors of PQA satisfy

$\left\|V^{*}-V^{k}\right\|_{\infty}<\gamma^{k}\left(\left\|V^{*}-V^{0}\right\|_{\infty}+\frac{c_{0}}{1-\gamma}\right).$

Since
$\underset{\tilde{\pi}_{s}^{k+1}\in\tilde{\Pi}_{s}^{k+1}}{\min}\frac{1}{2}\left\|\tilde{\pi}_{s}^{k+1}-\pi_{s}^{k}\right\|_{2}^{2}\leq
1$, the step size condition reduces to
$\eta_{k}\geq\frac{1}{c_{0}}\frac{1}{\gamma^{2k+1}}$ which is similar with the
step size condition obtained from Theorem 5.1. Indeed, the flow of the proof
for Theorem 5.1 is overall aligned with that for Theorem 1 in [11]. The major
difference is that we use Lemma 2.11 to get an upper bound of
$\underset{a\in\mathcal{A}}{\max}A_{s,a}^{k}-\sum_{a}{\pi_{s,a}^{k+1}A_{s,a}^{k}}$
while the three point descent lemma is used in [11].

###  5.2 Equivalence of PPG and PQA to PI under adaptive step sizes

In this section, we study the convergence of PPG and PQA with adaptive step
sizes and show that both PPG and PQA are equivalent to PI when the step size
$\eta_{k}$ is greater than a threshold. The analysis of this section is
similar to that for the finite iteration convergence. We utilize the gap
property (Lemma 2.8) again to show that once the step size is large enough,
then the action set $\mathcal{A}\setminus\mathcal{A}^{k}_{s}$ will be
eliminated from the support set of the new policy.

######  Theorem 5.3.

Consider the prototype update in (2.1) and suppose the step size $\eta$
satisfies

$\displaystyle\underset{s\in\mathcal{S}}{\min}\,\,\eta_{s}>\mathscr{T}^{\pi}:=\frac{2}{\Delta^{\pi}}\cdot\underset{s\in\mathcal{S}}{\max}\left\\{\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{\pi}\right)\right\\},$
(5.3)

where
$\Delta^{\pi}:=\underset{s\in\mathcal{S}}{\min}\left|\underset{a^{\prime}\in\mathcal{A}}{\max}A_{s,a^{\prime}}^{\pi}-\underset{a^{\prime}\notin\mathcal{A}_{s}^{\pi}}{\max}A_{s,a^{\prime}}^{\pi}\right|$.
Then the new policy at state $s$ (i.e., ${\pi}_{s}^{+}$) is supported on the
action set $\mathcal{A}^{\pi}_{s}$, which implies that the prototype update is
equivalent to PI.

###### Proof.

Notice that for each state $s\in{\cal S}$ and $a\notin\mathcal{A}^{\pi}_{s}$,
$A_{s,a}^{\pi}\leq\underset{a^{\prime}\notin\mathcal{A}_{s}^{\pi}}{\max}A_{s,a^{\prime}}^{\pi}$.
By Lemma 2.11, when the step size satisfies

$\frac{2\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{\pi}\right)}{\eta_{s}}<\underset{a^{\prime}\in\mathcal{A}}{\max}A_{s,a^{\prime}}^{\pi}-\underset{a^{\prime}\notin\mathcal{A}_{s}^{\pi}}{\max}A_{s,a^{\prime}}^{\pi},$

or equivalently

$\displaystyle\eta_{s}<\frac{2\pi_{s}\left(\mathcal{A}\setminus\mathcal{A}_{s}^{\pi}\right)}{\underset{a^{\prime}\in\mathcal{A}}{\max}A_{s,a^{\prime}}^{\pi}-\underset{a^{\prime}\notin\mathcal{A}_{s}^{\pi}}{\max}A_{s,a^{\prime}}^{\pi}},$
(5.4)

all the $a^{\prime}\not\in{\cal A}^{\pi}_{s}$ are not in ${\cal
B}_{s}(\eta_{s})$. That is, the new policy $\pi^{+}_{s}$ is supported on
$\mathcal{A}^{\pi}_{s}$. It’s trivial to see that the condition (5.3) implies
(5.4) for every $s\in\mathcal{S}$, thus the proof is completed. ∎

######  Corollary 5.4.

For PPG, if the step size satisfies
$\eta_{k}\geq\frac{1}{\tilde{\mu}}\mathscr{F}^{\pi^{k}},$ the condition of
Theorem 5.3 is met.

######  Corollary 5.5.

For PQA, if the step size satisfies $\eta_{k}\geq\mathscr{F}^{\pi^{k}},$ the
condition of Theorem 5.3 is met.

######  Remark 5.2.

It is worth noting that the step size threshold in the above two corollaries
only relies on the current policy $\pi^{k}$.

## References

  * [1] Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen Lee, Jiaji Li, Daniel R. Melamed, Gal Oshri, Oswaldo Ribas, Siddhartha Sen, and Alex Slivkins.  Making Contextual Decisions with Low Technical Debt.  arXiv:1606.03966, 2016.
  * [2] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan.  On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift.  Journal of Machine Learning Research, 22(98):1–76, 2021.
  * [3] Carlo Alfano and Patrick Rebeschini.  Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization.  arXiv:2209.15382, 2022.
  * [4] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal Jozefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, HenriquePondedeOliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang.  Dota 2 with Large Scale Deep Reinforcement Learning.  arXiv:1912.06680, 2019.
  * [5] Dimitri P. Bertsekas.  Reinforcement learning and optimal control.  Athena Scientific, 2019.
  * [6] Jalaj Bhandari and Daniel Russo.  On the Linear Convergence of Policy Gradient Methods for Finite MDPs.  In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 2386–2394. PMLR, 2021\.
  * [7] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi.  Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization.  Operations Research, 70(4):2563–2578, 2022.
  * [8] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H. Chi.  Top-k off-policy correction for a REINFORCE Recommender System.  In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456–464. Association for Computing Machinery, 2019.
  * [9] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin.  A Theory of Regularized Markov Decision Processes.  In Proceedings of the 36th International Conference on Machine Learning, pages 2160–2169, 2019.
  * [10] Jemin Hwangbo, Joonho Lee, Alexey Dosovitskiy, Dario Bellicoso, Vassilios Tsounis, Vladlen Koltun, and Marco Hutter.  Learning agile and dynamic motor skills for legged robots.  Science Robotics, 4(26), 2019.
  * [11] Emmeran Johnson, Ciara Pike-Burke, and Patrick Rebeschini.  Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes.  In Sixteenth European Workshop on Reinforcement Learning, 2023.
  * [12] Sham M. Kakade and John Langford.  Approximately Optimal Approximate Reinforcement Learning.  In International Conference on Machine Learning (ICML ’02), pages 267–274, 2002.
  * [13] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri.  On the Linear Convergence of Natural Policy Gradient Algorithm.  In 2021 60th IEEE Conference on Decision and Control (CDC), pages 3794–3799, 2021.
  * [14] Guanghui Lan.  Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes.  Mathematical Programming, 198(1):1059–1106, 2021.
  * [15] Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter.  Learning quadrupedal locomotion over challenging terrain.  Science Robotics, 5(47), 2020.
  * [16] Yan Li, Guanghui Lan, and Tuo Zhao.  Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity.  Mathematical Programming, 2023.
  * [17] Jiacai Liu, Jinchi Chen, and Ke Wei.  On the Linear Convergence of Policy Gradient under Hadamard Parameterization.  arXiv:2305.19575, 2023.
  * [18] Jincheng Mei, Chenjun Xiao, Csaba Szepesvári, and Dale Schuurmans.  On the Global Convergence Rates of Softmax Policy Gradient Methods.  In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 6820–6829. PMLR, 2020.
  * [19] Takahiro Miki, Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter.  Learning robust perceptive locomotion for quadrupedal robots in the wild.  Science Robotics, 7(62), 2022.
  * [20] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Quoc V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean.  A graph placement methodology for fast chip design.  Nature, 594(7862):207–212, 2021.
  * [21] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533, 2015.
  * [22] Bruno Scherrer.  Improved and Generalized Upper Bounds on the Complexity of Policy Iteration.  In Advances in Neural Information Processing Systems 26 (NeurIPS 2013), volume 26. Curran Associates, Inc., 2013.
  * [23] Lior Shani, Yonathan Efroni, and Shie Mannor.  Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs.  In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5668–5675, 2020.
  * [24] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of Go with deep neural networks and tree search.  Nature, 529(7587):484–489, 2016.
  * [25] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy Gradient Methods for Reinforcement Learning with Function Approximation.  In Proceedings of the 12th International Conference on Neural Information Processing Systems, pages 1057–1063, 1999.
  * [26] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, JohnP. Agapiou, Julian Schrittwieser, John Quan, Stephen Gaffney, Stig Petersen, Karen Simonyan, Tom Schaul, Hadovan Hasselt, David Silver, TimothyP. Lillicrap, Kevin Calderone, Paul Keet, Anthony Brunasso, David Lawrence, Anders Ekermo, Jacob Repp, and Rodney Tsing.  Starcraft II: A New Challenge for Reinforcement Learning.  arXiv:1708.04782, 2017.
  * [27] Weiran Wang and Miguel A. Carreira-Perpiñán.  Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application.  arXiv:1309.1541, 2013.
  * [28] Lin Xiao.  On the Convergence Rates of Policy Gradient Methods.  Journal of Machine Learning Research, 23(282):1–36, 2022.
  * [29] Rui Yuan, Simon S. Du, Robert M. Gower, Alessandro Lazaric, and Lin Xiao.  Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies.  In The Eleventh International Conference on Learning Representations, 2023.
  * [30] Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D. Lee, and Yuejie Chi.  Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence.  SIAM Journal on Optimization, 33(2):1061–1091, 2023.
  * [31] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvári, and Mengdi Wang.  Variational Policy Gradient Method for Reinforcement Learning with General Utilities.  In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), volume 33, pages 4572–4583. Curran Associates, Inc., 2020.