# Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted
Markov Decision Processes

Emmeran Johnson
Department of Mathematics
Imperial College London
<EMAIL_ADDRESS>
&Ciara Pike-Burke
Department of Mathematics
Imperial College London
<EMAIL_ADDRESS>
Patrick Rebeschini
Department of Statistics
University of Oxford
<EMAIL_ADDRESS>

###### Abstract

Policy Mirror Descent (PMD) is a general family of algorithms that covers a
wide range of novel and fundamental methods in reinforcement learning.
Motivated by the instability of policy iteration (PI) with inexact policy
evaluation, PMD algorithmically regularises the policy improvement step of PI.
With exact policy evaluation, PI is known to converge linearly with a rate
given by the discount factor $\gamma$ of a Markov Decision Process. In this
work, we bridge the gap between PI and PMD with exact policy evaluation and
show that the dimension-free $\gamma$-rate of PI can be achieved by the
general family of unregularised PMD algorithms under an adaptive step-size. We
show that both the rate and step-size are unimprovable for PMD: we provide
matching lower bounds that demonstrate that the $\gamma$-rate is optimal for
PMD methods as well as PI, and that the adaptive step-size is necessary for
PMD to achieve it. Our work is the first to relate PMD to rate-optimality and
step-size necessity. Our study of the convergence of PMD avoids the use of the
performance difference lemma, which leads to a direct analysis of independent
interest. We also extend the analysis to the inexact setting and establish the
first dimension-optimal sample complexity for unregularised PMD under a
generative model, improving upon the best-known result.

##  1 Introduction

The problem of finding an optimal policy in tabular discounted Markov Decision
Processes (MDPs) was classically solved using dynamic programming approaches
such as policy iteration (PI) and value iteration (VI) [29, 35]. These methods
are well understood theoretically and are guaranteed to converge linearly to
the optimal policy in the tabular setting with a rate equal to the discount
factor $\gamma$ of the MDP [9]. Recently, increased interest has been devoted
to the study of policy-gradient (PG) approaches based on optimising a
parameterised policy with respect to an objective [36, 23, 20].

Given their popularity, it is of interest to better understand PG methods and
determine if their guarantees match those of classical algorithms in tabular
MDPs. Among the recent works focused on understanding these methods in the
tabular setting, [38] study a general family of algorithms known as Policy
Mirror Descent (PMD). PMD algorithmically regularises the policy improvement
step of PI and as such can be seen as a version of regularised PI, without
actually regularising the objective of interest. It is also viewed as a
policy-gradient method through its connection to mirror descent [8]. Linear
convergence of PMD was established by [38], though their rate depends on an
instance-dependent factor that can scale with the dimension of the problem,
such as the size of the state space. For a specific instance of PMD known as
Natural Policy Gradient (NPG), [22] showed that an instance-independent
$\gamma$-rate is achievable, although their results do not cover general PMD.
In MDPs where the objective is regularised, the $\gamma$-rate has been
established for PMD [13, 24, 41]. The classical approaches (PI and VI) achieve
the $\gamma$-rate without regularisation, revealing that regularisation is, in
general, not necessary for algorithms to reach the $\gamma$-rate. This
motivates the following questions:

Can the classical linear $\gamma$-rate be matched by unregularised policy-
gradient algorithms? And what is the best rate that unregularised policy-
gradient methods can achieve ?

For PMD, our work answers the first question positively and answers the second
by establishing that the $\gamma$-rate is in fact the best rate achievable for
PMD as well as for a more general family of algorithms (see Section 4.1). PMD
allows for a choice of a mirror map that specifies different algorithms. Among
these, NPG and PI are two ubiquitous instances of PMD each corresponding to
their own mirror map. However, PMD is much more general and other mirror maps
will lead to alternative algorithms endowed with the guarantees of PMD that we
establish in this paper. In particular, the correspondence of mirror maps with
exponential families [7] allows us to specify a wealth of valid mirror maps.
This illustrates that PMD is a general framework that encompasses a wide range
of novel but also fundamental algorithms, and motivates the study of its
convergence guarantees. In this work, we make the following contributions and
summarise them in Table 1,

  * •

We recover the $\gamma$-rate for the general family of PMD algorithms with
exact policy evaluations under an adaptive size (see the third bullet point
below). In particular, Theorem 4.1 establishes the following bound in
$\ell_{\infty}$-norm for the value $V^{\pi^{k}}$ of the policy $\pi^{k}$ after
$k$ iterations of PMD compared to the value $V^{\pi^{\star}}$ of an optimal
policy $\pi^{\star}$,

$\displaystyle\|V^{\pi^{\star}}-V^{\pi^{k}}\|_{\infty}\leq\frac{2}{1-\gamma}\gamma^{k},$

providing guarantees for any starting-state distribution. This matches the
rate of VI and PI as well as the best known rates for PMD on regularised MDPs.
This is also the first fully dimension-independent linear convergence result
for unregularised PMD, by which we mean that there is no dependence on the
size of the state space or the action space.

  * •

We provide a matching non-asymptotic lower-bound in Theorem 4.2, establishing
the $\gamma$-rate as the optimal rate for PMD methods in early iterations. Our
results show that a particular choice of learning rate allows PMD to reach
this lower-bound exactly. Note that an asymptotic lower-bound is not possible
due to the exact convergence of PI in finite iterations (see Section 4.1 for a
discussion of the significance of this non-asymptotic lower-bound).

  * •

The $\gamma$-rate for PMD in Theorem 4.1 relies on an adaptive step-size,
where the adaptivity comes from the fact that the step-size depends on the
policy at the current iteration (see Section 4). In Theorem 4.3 we show that
this adaptivity is necessary for PMD to achieve the $\gamma$-rate,
establishing our step-size as both sufficient and necessary.

  * •

We establish a novel theoretical analysis that avoids the use of the
performance difference lemma [19]. This leads to a simple analysis and avoids
needing to deal with visitation distribution mismatches that lead to dimension
dependence in prior work.

  * •

By extending our analysis to the inexact setting, with an approach similar to
that of in [38], we establish an instance-independent sample complexity of
$\tilde{O}(|\mathcal{S}||\mathcal{A}|(1-\gamma)^{-8}\varepsilon^{-2})$ under a
generative model, where the notation $\tilde{O}()$ hides poly-logarithmic
factors, $\mathcal{S}$ is the state space of the MDP, $\mathcal{A}$ is the
action space and $\varepsilon$ is the required accuracy. This improves on the
previous best known sample complexity for PMD by removing the dependence on a
distribution mismatch coefficient that can scale with problem-dependent
quantities such as the size of the state space. More generally, we highlight
that the analysis we establish in the exact setting can easily be combined
with any other scheme for estimating the Q functions (see Section 5), paving
the way for further improvements in instance-independent sample complexity
results should more efficient estimation procedures be developed.

Our contributions are primarily on establishing the optimal rate for general
(not just NPG) exact PMD where we assume access to the true action-values of
policies, and the simplicity of the analysis. The sample complexity result in
the inexact setting illustrates how our analysis can be easily extended to
obtain improved results for inexact PMD. These contributions advance the
theoretical understanding of PMD and rule out searching for instances of PMD
that may improve on PI or NPG in the exact setting. The algorithmic
differences between instances of PMD do not affect the performance of the
algorithm beyond the step-size condition.

Table 1: Comparison of contributions with prior work that study PMD. [22] focus on NPG, an instance of PMD for a specific mirror map (see Section 3). Their analysis is fundamentally different to ours as it exploits the closed-form update of NPG. Their step-size is similar to ours, although it has a dependence on a sub-optimality gap (see Section 4). Linear $\gamma$-rate holds if the linear convergence is with the $\gamma$-rate, not only linear convergence. The $\ell_{\infty}$-bound is satisfied if it holds for $\|V^{\pi^{\star}}-V^{\pi^{k}}\|_{\infty}$. Dimension independence is satisfied when there is no instance for which the bound can scale with the size of the state or action space. We compare these works in more detail in Section 4. | Linear | General | $\ell_{\infty}$ | Dimension | Matching | Step-Size
---|---|---|---|---|---|---
|  $\gamma$-Rate | Mirror Map | Bound | Independent | Lower-Bound | Necessity
[22] | $\checkmark$ | $\times$ | $\checkmark$ | $\checkmark$ | $\times$ | $\times$
[38] | $\times$ | $\checkmark$ | $\times$ | $\times$ | $\times$ | $\times$
This work | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$

##  2 Related work

###  2.1 Convergence rates for exact policy mirror descent

We first consider the setting where exact policy evaluation is assumed. In
this setting, several earlier works have sub-linear convergence results for
PMD [17, 33] and NPG specifically [3, 1], though these have since been
improved to linear convergence results as discussed below. Note that the work
of [1] refers to their algorithm as "Politex", which shares the same update as
NPG.

A line of work has considered PG methods applied to regularised MDPs. In this
setting, linear convergence has been established for NPG with entropy
regularisation [13], PMD with strongly-convex regularisers [24] and PMD with
convex non-smooth regularisers [41]. The rates of convergence are either
exactly $\gamma$ or can be made arbitrarily close to $\gamma$ by letting the
step-size go to infinity.

In the setting of unregularised MDPs, which is the focus of this paper, linear
convergence of the special case of NPG was established [11, 22] under an
adaptive step-size similar to ours that depends on the current policy at each
step. The bound of [11] has an additive asymptotic error-floor that can be
made arbitrarily small by making the step-size larger, while for a similar
step-size [22] does not have this term so we focus on this work. Their
analysis relies on a link between NPG and PI and consists of bounding the
difference in value between iterates of both methods. [11] also establish
linear convergence for a number of algorithms including PMD, although it is in
the idealised setting of choosing the step size at each iteration that leads
to the largest increase in value. This step-size choice will make PMD at least
as good as PI since arbitrarily large step-sizes can be chosen and PMD with an
infinite step-size converges to a PI update. Since PI converges linearly, so
will PMD. This does not establish linear convergence of PMD for step-sizes
with a closed-form expression. However, linear convergence for unregularised
general PMD was recently established by [38] under a geometrically increasing
step-size. In general, their rate is instance-dependent and may scale with
problem dependent quantities such as the size of the state space. For general
starting-state distributions, this same instance-dependent rate was
established by [27] for a variant of PMD which augments the update with an
added regularisation term. We focus our comparison on the work of [38] rather
than this work as the guarantees are equivalent in both but [27] do not
directly study PMD and have a more complicated algorithm. A summary of our
results compared to those of [22] and [38] is presented in Table 1 and
discussed in more detail in Section 4. In terms of optimality, [22] provide a
lower-bound for constant step-size NPG, though it only applies to MDPs with a
single-state, which can be solved in a single iteration with exact policy
evaluation as the step-size goes to infinity (for which the lower-bound goes
to 0). We provide a lower-bound in Theorem 4.2 that applies to PMD with
arbitrary step-size on an MDP with any finite state space. To the best of our
knowledge, prior to this work no lower-bound has been established in this
general setting.

###  2.2 Sample complexity of inexact policy mirror descent

Sample complexity in the inexact policy evaluation setting refers to the
number of samples needed to guarantee an $\varepsilon$-optimal policy is
returned when we no longer have access to the Q-values exactly. We here give
an outline of results, typically established in high-probability, under a
generative model that we formally present in Section 5. The lower bound on the
sample complexity in this setting was shown to be of
$\tilde{\Omega}\Big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}\Big{)}$
by [6]. This lower-bound can be reached by model-based approches [2, 26] and
model-free approaches [34, 37].

The sample-complexity for PG methods has been recently studied in [39]. Under
a generative model, some works have considered PMD or NPG under various types
of regularisation [13, 24, 41]. We focus on unregularised methods, for which
results for PMD or its instances on tabular MDPs under a generative model are
limited. There are works that obtain sample complexity results for NPG [3, 28]
and for PMD [33] though they do not attain the optimal
$\varepsilon$-dependence of $\mathcal{O}(\varepsilon^{-2})$. [25] show that a
variant of PI, a special case of PMD, achieves the optimal
$\varepsilon$-dependence of $\mathcal{O}(\varepsilon^{-2})$. More recently,
[38] show that the general family of PMD methods match the
$\mathcal{O}(\varepsilon^{-2})$ sample complexity with a factor of
$(1-\gamma)^{-8}$. Our result for the inexact setting shares the same
dependence on $\varepsilon$ and $1-\gamma$ as [38] but removes an instance-
dependent quantity which can depend on the size of the state space. Further
comparison to the result in [38] is given in Section 5. Beyond tabular MDPs
and generative models, [15] study NPG under linear function approximation and
off-policy sampling, though their results imply worse sample complexities when
restricted to tabular MDPs under a generative model. PMD under linear function
approximation [40, 4] and general function approximation [5] have also been
studied and results similar to [38] were obtained in those settings.

##  3 Preliminaries

A Markov Decision Process (MDP) is a discrete-time stochastic process,
comprised of a set of states $\mathcal{S}$, a set of actions $\mathcal{A}$, a
discount factor $\gamma\in[0,1)$ and for each state-action pair $(s,a)$ a
next-state transition function $p(\cdot|s,a)\in\Delta(\mathcal{S})$ and a
(assumed here deterministic) reward function $r(s,a)\in[0,1]$.
$\Delta(\mathcal{X})$ denotes the probability simplex over a set
$\mathcal{X}$. We consider both $\mathcal{S}$ and $\mathcal{A}$ to be finite,
which is known as the tabular setting. In a state $s$, an agent chooses an
action $a$, which gives them a reward $r(s,a)$ and transitions them to a new
state according to the transition function $p(\cdot|s,a)$. Once they are in a
new state, the process continues. The actions chosen by an agent are
formalised through policies. A policy
$\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ is a mapping from a state to a
distribution over actions. We will often write it as an element in
$\Pi=\Delta(\mathcal{A})^{|\mathcal{S}|}$. In each state $s\in\mathcal{S}$, an
agent following policy $\pi$ chooses an action $a\in\mathcal{A}$ according to
$\pi_{s}=\pi(\cdot|s)\in\Delta(\mathcal{A})$.

In this work, the goal is to learn how to behave in a $\gamma$-discounted
infinite-horizon MDP. We measure the performance of a policy with respect to
the value function $V^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$,

$V^{\pi}(s)=\mathbb{E}\Big{[}\sum\limits_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|\pi,s_{0}=s\Big{]},$

where $s_{t},a_{t}$ are the state and action in time-step $t$ and the
expectation is with respect to both the randomness in the transitions and the
choice of actions under policy $\pi$. This is a notion of long-term reward
that describes the discounted rewards accumulated over future time-steps when
following policy $\pi$ and starting in state $s$. For a distribution over
starting states $\rho\in\Delta(\mathcal{S})$, we write
$V^{\pi}(\rho)=\sum_{s\in\mathcal{S}}\rho(s)V^{\pi}(s)$ for the expected value
when starting in a state distributed according to $\rho$. It is also useful to
work with the state-action value
$Q^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$:

$Q^{\pi}(s,a)=\mathbb{E}\Big{[}\sum\limits_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|\pi,s_{0}=s,a_{0}=a\Big{]},$

which is similar to $V^{\pi}$, with the additional constraint of taking action
$a$ in the first time-step. We will often write
$V^{\pi}\in\mathbb{R}^{|\mathcal{S}|}$ (resp.
$Q^{\pi}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|}$) to refer to the
vector form, where each entry represents the value (resp. action-value) in
that state (resp. state-action pair). Similarly, we write
$Q^{\pi}_{s}\in\mathbb{R}^{|\mathcal{A}|}$ for the vector of action-values in
state $s$. The following expressions, which relate $Q^{\pi}$ and $V^{\pi}$ in
terms of each other and when combined give the Bellman equations [9], follow
from their definitions above,

$V^{\pi}(s)=\langle Q^{\pi}_{s},\pi_{s}\rangle,\quad
Q^{\pi}(s,a)=r(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)V^{\pi}(s^{\prime}).$

We now define the discounted visitation-distribution for starting state
$s^{\prime}$ and policy $\pi$,

$\displaystyle
d^{\pi}_{s^{\prime}}(s)=(1-\gamma)\sum\limits_{t=0}^{\infty}\gamma^{t}\mathbb{P}^{\pi}(s_{t}=s|s_{0}=s^{\prime}),$
(1)

which plays an important part in the study of PG methods. Note that
$\mathbb{P}^{\pi}(s_{t}=s|s_{0}=s^{\prime})$ is the probability of being in
state $s$ at time $t$ when starting in state $s^{\prime}$ and following policy
$\pi$. We also write
$d^{\pi}_{\rho}(s)=\sum_{s^{\prime}\in\mathcal{S}}\rho(s^{\prime})d^{\pi}_{s^{\prime}}(s)$.

One of the main aims of reinforcement learning is to find a policy $\pi$ that
maximises $V^{\pi}$. It is known that there exists a deterministic policy that
simultaneously maximises $V^{\pi}$ and $Q^{\pi}$ for all states and actions
[9]. We call such a policy an optimal policy and denote it by $\pi^{\star}$.
We are interested in finding an $\varepsilon$-optimal policy, i.e a policy
$\pi$ such that $\|V^{\pi^{\star}}-V^{\pi}\|_{\infty}<\varepsilon$.

###  3.1 Exact policy mirror descent

We are interested in PG methods that are based on optimising a parameterised
policy $\pi_{\theta}$ with respect to $V^{\pi_{\theta}}(\rho)$ for some
$\rho\in\Delta(\mathcal{S})$. In the tabular setting, we can use the direct
parameterisation of a policy $\pi_{\theta}$, which associates a parameter to
each state-action pair, i.e. we have $\pi_{\theta}(a|s)=\theta_{s,a}$. We will
drop the subscript $\theta$ for notational convenience. The gradient of the
value function with respect to this parameterisation [36] is given for each
state-action pair (s,a) by

$\frac{\partial}{\partial\pi(a|s)}V^{\pi}(\rho)=\frac{1}{1-\gamma}d^{\pi}_{\rho}(s)Q^{\pi}(s,a).$
(2)

Mirror Descent (MD, [8]) carries out gradient descent in a geometry that is
non-Euclidean. Using $-V^{\pi}(\rho)$ as the minimising objective, the
proximal perspective of MD gives an update of the form

$\pi^{k+1}=\text{argmin}_{p\in\Pi}\Big{\\{}-\eta_{k}\langle\nabla
V^{\pi^{k}}(\rho),p\rangle+D_{h}(p,\pi^{k})\Big{\\}}$ (3)

where $h:\text{dom }h\rightarrow\mathbb{R}$ is the mirror map (with
$\Pi\subset\text{dom }h$) and $D_{h}$ is the Bregman divergence generated by
$h$. We require $h$ to be of Legendre type [30], i.e strictly convex and
essentially smooth (differentiable and $\|\nabla h(x_{k})\|\rightarrow\infty$
for any sequence $x_{k}$ converging to a point on the boundary of $\text{dom
}h$) on the relative interior (rint) of $\text{dom }h$. The Bregman Divergence
is defined as

$D_{h}(\pi,\pi^{\prime})=h(\pi)-h(\pi^{\prime})-\langle\nabla
h(\pi^{\prime}),\pi-\pi^{\prime}\rangle\quad\quad\text{for
}\pi,\pi^{\prime}\in\text{dom }h.$

As the objective $V^{\pi}(\rho)$ is non-convex in general [3], usual
techniques from convex theory [12] are not applicable.

The presence of the visitation-distribution term $d^{\pi}_{\rho}(s)$ in the
gradient of the objective in (2) can slow down learning because it can lead to
vanishingly small gradients when states are infrequently visited under the
current policy $\pi$ [3]. To circumvent this issue, Policy Mirror Descent
(PMD) [24, 33, 38] applies a variant of update (3) with a weighted Bregman
divergence $D^{\text{PMD}}_{h}$ that matches the visitation distribution
factors of the gradient
$D^{\text{PMD}}_{h}(p,\pi^{k})=\sum_{s}d^{\pi^{k}}_{\rho}(s)D_{h}(p_{s},\pi^{k}_{s})$
where the mirror map $h$ is now defined on a subset of
$\mathbb{R}^{|\mathcal{A}|}$. The resulting update has for all states a factor
of $d^{\pi^{k}}_{\rho}(s)$ in both terms. The minimisation can then be applied
for each state individually to get the PMD update

$\pi^{k+1}_{s}=\text{argmin}_{p\in\Delta(\mathcal{A})}\Big{\\{}-\eta_{k}\langle
Q^{\pi^{k}}_{s},p\rangle+D_{h}(p,\pi^{k}_{s})\Big{\\}}$ (4)

for all states $s$. We will often add a superscript $k$ to any quantity that
is associated to $\pi^{k}$. For example, $V^{k}(s)=V^{\pi^{k}}(s)$. Similarly
for $\pi^{\star}$ and the superscript $\star$. Exact PMD iteratively applies
update (4) for some sequence of step-sizes $\eta_{k}>0$ and initial policy
$\pi^{0}\in\text{rint }\Pi$. We call this algorithm exact because we assume
access to the true state-action values $Q^{k}$.

The update (4) of PMD considered in this work uses the true action-value
$Q^{\pi}$. In prior work, PMD has sometimes been applied to regularised MDPs
[24] where the action-value is augmented with regularisation and is no longer
the true action-value. This is a different algorithm that converges to a
policy that is optimal in the regularised MDP but not in the original
unregularised MDP.

PMD is a general family that covers many algorithms, specified by the choice
of mirror map $h$. These will inherit the guarantees of PMD, which motivates
the study of the convergence guarantees of PMD beyond specific instances.
Taking $h$ to be the negative entropy yields NPG, whose theoretical properties
have attracted a lot of interest [3, 13, 22]. With a null Bregman Divergence,
PMD recovers PI. PI is generated by a constant mirror map, which is not of
Legendre type but the analysis still applies so all results on PMD remain
valid for PI. In fact, PMD can be viewed as a form of regularised PI since the
update (4) converges to a PI update as $\eta_{k}\rightarrow\infty$, regardless
of the mirror map. Beyond these, providing mirror maps that generate other
Bregman Divergences will lead to different algorithms. In particular, every
exponential family has a corresponding mirror map generating a unique Bregman
Divergence [7], highlighting the generality of PMD.

##  4 Main results for exact policy mirror descent

In this section, we present our main results on the convergence of exact PMD.
We first introduce some relevant notation. Fix a state $s\in\mathcal{S}$ and
an integer $k\geq 0$. Let
$\mathcal{A}^{k}_{s}=\\{a\in\mathcal{A}:Q^{k}(s,a)=\text{max}_{a^{\prime}\in\mathcal{A}}Q^{k}(s,a^{\prime})\\}$
denote the set of optimal actions in state $s$ under policy $\pi^{k}$. Denote
by $\widetilde{\Pi}^{k+1}_{s}$ the set of greedy policies w.r.t $Q^{k}_{s}$ in
state s, i.e
$\widetilde{\Pi}^{k+1}_{s}=\Big{\\{}p\in\Delta(\mathcal{A}):\sum_{a\in\mathcal{A}^{k}_{s}}p(a)=1\Big{\\}}$.
We are now ready to state our main result in the setting of exact PMD, which
is proved in Section 6.

######  Theorem 4.1.

Let $\\{c_{k}\\}_{k\in\mathbb{Z}_{\geq 0}}$ be a sequence of positive reals.
Consider applying iterative updates of (4) with $\pi^{0}\in\text{rint }\Pi$
and step-sizes satisfying for all $k\geq 0$,

$\displaystyle\eta_{k}\geq\frac{1}{c_{k}}\max_{s\in\mathcal{S}}\Big{\\{}\min_{\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}}D_{h}(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s})\Big{\\}}.$
(5)

Then we have for all $k\geq 0$,

$\|V^{\star}-V^{k}\|_{\infty}\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+\sum_{i=1}^{k}\gamma^{-i}c_{i-1}\Big{)}.$
(6)

The sequence $\\{c_{k}\\}_{k\in\mathbb{Z}_{\geq 0}}$ plays an important role
in both the step-size constraint (5) and the bound (6). In particular,
different choices will lead to different guarantees. We focus on
$c_{i}=\gamma^{2(i+1)}c_{0}$ for some $c_{0}>0$, giving a step-size with a
geometrically increasing component. The resulting bound is

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+\frac{c_{0}}{1-\gamma}\Big{)},$

which converges linearly with the $\gamma$-rate, and matches the bounds of PI
and VI as $c_{0}$ goes to 0. PMD cannot do better as we will show in Theorem
4.2. We discuss other choices of $\\{c_{k}\\}$ in Appendix C. We provide some
simulations that demonstrate the behaviour of our step-size (5) and validate
its benefits compared to the step-size of [38] in Appendix D.

Comparison to [38]: Linear convergence of unregularised PMD was first
established by [38] under a geometrically increasing step-size
$\eta_{k}=\eta_{0}/\gamma^{k}$. We discuss this step-size further and show the
necessity of adaptivity to achieve the $\gamma$-rate in Section 4.2. Their
rate of convergence is $1-\frac{1}{\theta_{\rho}}$ where $\theta_{\rho}$ is an
instance-dependent term defined as follows

$\displaystyle\theta_{\rho}=\frac{1}{1-\gamma}\Big{\|}\frac{d^{\star}_{\rho}}{\rho}\Big{\|}_{\infty},$

where $d^{\star}_{\rho}$ is the visitation distribution defined in (1) under
an optimal policy and $\rho$ is the starting-state distribution to which the
bound applies, i.e the bound is on $V^{\star}(\rho)-V^{k}(\rho)$. This
$\theta_{\rho}$ is at best $\gamma$ when we use $\rho$ to be the stationary
distribution of the optimal policy. However, in this case, the guarantee only
applies to states on the support of this stationary distribution and provides
no guarantees for other states. In general, it is unclear how $\theta_{\rho}$
may scale in a specific MDP. In particular, it is possible to construct an MDP
where $\theta_{\rho}$ scales linearly with the size of the state space
$|\mathcal{S}|$ (Appendix H.1). Though this MDP is somewhat trivial, it
nonetheless illustrates how $\theta_{\rho}$ can easily be large leading to
slow rates of convergence. It is also not straightforward to obtain
convergence in individual states from the bound in [38] due to the presence of
$\rho$ in the denominator of the mismatch coefficient in $\theta_{\rho}$. In
contrast, we obtain the optimal $\gamma$-rate of convergence and our result
holds in $\ell_{\infty}$-norm over all states so avoids having to deal with a
starting-state distribution $\rho$ altogether.

This distribution mismatch coefficient commonly appears in convergence bounds
in the literature [19, 32, 10, 33, 3], both under exact and inexact policy
evaluation. For many of these papers mentioned, removing it would be of great
interest though often does not appear possible. Our results show that it is
removable for the general family of PMD algorithms to obtain dimension-free
linear convergence. The techniques we use may be of interest for removing this
coefficient in other settings.

Comparison to [22]: The $\gamma$-rate was established by [22] for NPG, a
specific instance of PMD for which the Bregman Divergence is the KL-
divergence. The bound shown in their work is similar to the one implied by our
result with $c_{i}=\gamma^{2(i+1)}c_{0}$. Defining
$\Delta^{k}(s)=\text{max}_{a\in\mathcal{A}}Q^{k}(s,a)-\text{max}_{a\notin\mathcal{A}^{k}_{s}}Q^{k}(s,a)$,
the minimal sub-optimality gap in state $s$ under $\pi^{k}$, then the step-
size corresponding to their bound with the KL as Bregman Divergence is

$\displaystyle\eta_{k}\geq\text{max}_{s,\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}}\Big{\\{}\Big{(}L_{k}+\text{log}|\mathcal{A}|+D(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s})\Big{)}\frac{1}{\Delta_{k}(s)}\Big{)}\Big{\\}},$

where $L_{k}=Lk$ for some constant $L>0$. This highlights the connection with
our step-size condition (5). In particular, they both have an adaptive
component that depends linearly on the Bregman divergence between the current
policy and the greedy policy and a non-adaptive component on which the bound
depends. An important difference is that our step-size is independent of the
sub-optimality gap $\Delta_{k}(s)$, and will be robust to situations where
this gap is small. We can construct a general family of MDPs for which we can
make $\Delta_{k}(s)$ arbitrarily small and the step-size of [22] will
correspondingly become arbitrarily large (Appendix H.2). Despite the apparent
similarities with our results, their analysis is significantly different to
ours as it exploits the specific closed-form update of NPG to bound the
difference in value with an update of PI. Our analysis applies to PMD for a
general mirror map (not just NPG) and as such does not utilize specific
properties of the mirror map and does not require the analytic solution of the
update to be known. Our analysis also easily extends to inexact PMD (see
Section 5), which theirs does not.

#### Computing the step-size:

The expression (5) for the step-size can be simplified. The minimum over
$\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}$ can be removed by
taking any $\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}$. It was
stated with the minimum to have the smallest condition but that is not
necessary. In fact, there will often only be one greedy action, i.e.
$\mathcal{A}^{k}_{s}$ will contain a single action and there will just be one
policy in $\widetilde{\Pi}^{k+1}_{s}$. As for the maximum over
$s\in\mathcal{S}$, this condition is imposed because we are using the same
step-size in all states for simplicity. If we allow different step-sizes in
each state, then the step-size in state $s$, denoted $\eta_{k}(s)$ would just
have to satisfy (choosing any
$\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}$)

$\displaystyle\eta_{k}(s)\geq\frac{1}{c_{k}}D_{h}(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s}).$

The computational complexity of the step-size is then that of the Bregman
divergence between two policies. Note that the step-size (5) is always finite.
It can be unbounded when $h$ is of Legendre type on the relative interior of
$\Delta(\mathcal{A})$ (as for the negative entropy) but then all iterates will
belong to the relative interior of $\Delta(\mathcal{A})$ and the Bregman
divergences are well defined so the step-size is finite.

###  4.1 Optimality of PMD

We have established in Theorem 4.1 that PMD achieves a linear $\gamma$-rate.
The following result shows that this rate is in fact optimal in a worst-case
sense. The proof can be found in Appendix E.

######  Theorem 4.2.

Fix $n>0$. There exists a class of MDPs with $|\mathcal{S}|=2n+1$ and a policy
$\pi^{0}\in\text{rint }\Pi$ such that running iterative updates of (4) for any
positive step-size regime, we have for $k<n$:

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}\geq\frac{1}{2}\gamma^{k}\|V^{\star}-V^{0}\|_{\infty}.$
(7)

A key feature of this result is that the bound holds for $k<n$. For a fixed
iteration budget, Theorem 4.2 implies that there exists an MDP on which PMD
will not do better than the linear $\gamma$-rate for any step-size. The
$\gamma$-rate for PMD that we prove in Theorem 4.1 is optimal in this sense.

#### Lower-bound beyond $\mathbf{k<n}$?

For a fixed state-space size $|\mathcal{S}|=2n+1$, it is not known what lower-
bound holds when $k\geq n$. However, PI is an instance of PMD (see Section
3.1) and thus a lower bound that scales with $\gamma^{k}$ for all $k>0$ cannot
hold since PI converges exactly in finite-iterations (in fact with a number of
iterations that scales linearly with $|\mathcal{S}|$ [31, Theorem 3]).
However, an asymptotic lower-bound for PMD under arbitrary step-size will not
hold even if we exclude PI from the class of considered algorithms. As the
step-size tends to infinity, any PMD update recovers a PI update. This implies
that general PMD can be arbitrarily close to PI’s exact convergence for the
same finite number of iterations. Thus, any lower-bound on the convergence of
PMD must be limited to finite iterations. Since the finite iteration
convergence of PI only scales linearly with $|\mathcal{S}|$ [31, Theorem 3],
the number of iterations guaranteed by Theorem 4.2 has the same dependence on
$|\mathcal{S}|$ as the number of iterations needed for exact convergence of
PI. To the best of our knowledge, this lower bound on the value convergence of
PMD scaling with $\gamma^{k}$ is new. We expect this result may have been
known for the special case of PI, though we could not find a proof of it in
the literature. The works that establish a lower bound for PI do so in the
setting of exact convergence to the optimal policy [18], not
$\varepsilon$-accurate convergence, and for undiscounted MDPs [16].

#### Rate-Optimality

Theorem 4.2 establishes that the $\gamma$-rate is optimal in the first
$|\mathcal{S}|/2$ iterations. This non-asymptotic optimality is justified by
the discussion above, which highlights that a rate for PMD under arbitrary
step-size can only be optimal for a finite number of iterations, and
specifically up until the exact convergence of PI.

There are some results on the super-linear convergence of NPG in the
literature, though these apply once you have a policy within some
neighbourhood of the optimal policy or value. [13] establish such a result for
NPG in the regularised case, and [22] in the unregularised case under
additional conditions. Theorem 4.2 does not contradict this latter result as
for the MDP considered in the proof, the super-linear convergence would kick-
in for iterations beyond the $k<n$ considered here.

#### Lower-bound for general PG methods:

The lower bound of Theorem 4.2 in fact applies to any algorithm that at each
iteration increases the probability of the current greedy action. The greedy
action is the action with highest action-value for the current policy. This
covers algorithms more general than PMD and in particular, includes the
vanilla PG algorithm.

###  4.2 Adaptive step-size necessity

We have established in Theorem 4.1 that PMD under an adaptive step-size
achieves a linear $\gamma$-rate and in Theorem 4.2 that this rate is optimal
for PMD. We now show the adaptivity is in fact necessary to achieve the
$\gamma$-rate. This strengthens the notion of optimality from the previous
section - both the rate and step-size are unimprovable. The proof can be found
in Appendix F.

######  Theorem 4.3.

Fix $n>0$ and $\gamma>0.2$. There exists an MDP with state-space of size
$|\mathcal{S}|=2n+1$ and a policy $\pi^{0}\in\text{rint }\Pi$ such that
running iterative updates of NPG (PMD with h as the negative entropy) that
satisfy
$\|V^{\star}-V^{k}\|_{\infty}\leq\gamma^{k}(\|V^{\star}-V^{0}\|_{\infty}+\frac{1-\gamma}{8})$
requires

$\displaystyle\eta_{k_{i}}$ $\displaystyle\geq
KL(\tilde{\pi}^{k_{i}+1}_{s_{i}},\pi^{k_{i}}_{s_{i}})/2\gamma^{k_{i}},\qquad\tilde{\pi}^{k_{i}+1}_{s_{i}}\in\widetilde{\Pi}^{k+1}_{s}$
(8)

for $i=1,...,n$ s.t $k_{1}<k_{2}<...<k_{n}$ where $\\{s_{1},...,s_{n}\\}$ are
distinct states of the considered MDP.

This theorem states that there are at least $n$ distinct iterations with $n$
distinct states where the step-size has to be bigger than a quantity depending
on the Bregman divergence between the current policy and its greedy policy in
the considered state in order to achieve a linear $\gamma$-rate. This is
precisely the notion of adaptivity that appears in the step-size condition of
Theorem 4.1 and [22]. Theorem 4.3 shows we cannot improve on this in general
and provides justification for using an adaptive step-size instead of the one
from [38]. Beyond its necessity, the adaptivity of our step-size can be a
strength: it is large when needed, small when not. This is illustrated by the
simulations we provide in Appendix D.

Theorem 4.3 only holds for the particular case of the negative entropy (NPG).
This limitation is due to technical reasons rather than fundamental ones. The
proof relies on the closed form update of NPG and we don’t have this for
general mirror map (see Appendix F). However, this result for NPG is enough to
establish the necessity of the step-size for PMD in general.

##  5 Sample complexity of inexact policy mirror descent under generative
model

In the previous sections, we have assumed access to the state-action values
$Q^{k}_{s}$ to carry out the PMD update. In Inexact PMD (IPMD), we replace
$Q^{k}_{s}$ with an estimate $\widehat{Q}^{k}_{s}$ giving the update

$\pi^{k+1}_{s}=\text{argmin}_{p\in\Delta(\mathcal{A})}\Big{\\{}-\eta_{k}\langle\widehat{Q}^{k}_{s},p\rangle+D_{h}(p,\pi^{k}_{s})\Big{\\}}.$
(9)

Similarly to the exact case, IPMD iteratively applies update (9) for some
sequence of $\eta_{k}>0$ and initial policy $\pi^{0}\in\text{rint }\Pi$, this
time only assuming access to an inexact estimator of $Q^{k}$.

We consider the setting of a generative model [21], which is a sampling model
where we can draw samples from the transition probabilities $p(\cdot|s,a)$ for
any pair $(s,a)$. We borrow an estimator common in the literature (see e.g.
[38], [25]): for all state-actions pairs $(s,a)$, draw $M_{k}$ trajectories of
length or horizon $H$, i.e samples of the form
$\big{(}(s_{0}^{(i)},a_{0}^{(i)}),(s_{1}^{(i)},a_{1}^{(i)}),...,(s_{H-1}^{(i)},a_{H-1}^{(i)})\big{)}_{i=1,...,M_{k}}$,
where $a_{t}^{(i)}$ is drawn from $\pi^{k}(\cdot|s_{t}^{(i)})$,
$s_{t+1}^{(i)}$ is drawn from $p(\cdot|s_{t}^{(i)},a_{t}^{(i)})$ and
$(s_{0}^{(i)},a_{0}^{(i)})=(s,a)$. Using these samples, we can define a
truncated Monte-Carlo estimate of the values as follows,

$\displaystyle\widehat{Q}^{k}(s,a)=\frac{1}{M_{k}}\sum_{i=1}^{M_{k}}\widehat{Q}^{k}_{(i)}(s,a),\quad\text{where
}\quad\widehat{Q}^{k}_{(i)}(s,a)=\sum_{t=0}^{H-1}\gamma^{t}r(s_{t}^{(i)},a_{t}^{(i)}).$
(10)

We use these $\widehat{Q}^{k}(s,a)$ to replace $Q^{k}(s,a)$ in the PMD update
step. [38] present a bound on the accuracy of this estimator which is restated
in Appendix G. Following the same ideas as [38], we can extend Theorem 4.1 to
the inexact setting. The following theorem establishes a sample complexity
result, which is the sufficient number of calls to the generative model to
obtain an $\varepsilon$-optimal policy. For simplicity, we focus on the step-
size following from the choice $c_{i}=\gamma^{2(i+1)}$.

######  Theorem 5.1.

Consider applying iterative updates of (9) using the Q-estimator in (10) given
access to a generative model with $\pi^{0}\in\text{rint }\Pi$ and step-sizes
satisfying for all $k\geq 0$ (with the definitions of $\mathcal{A}^{k}_{s}$
and $\widetilde{\Pi}^{k+1}_{s}$ suitably adjusted with $\widehat{Q}^{k}_{s}$
instead of $Q^{k}_{s}$),

$\displaystyle\eta_{k}\geq\max_{s\in\mathcal{S}}\Big{\\{}\min_{\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}}\frac{D(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s})}{\gamma^{2k+1}}\Big{\\}}.$

Fix $\varepsilon>0$. For any $\delta\in(0,1)$, suppose the following are
satisfied for all $k\geq 0$,

$K>\frac{1}{1-\gamma}\log\frac{4}{(1-\gamma)\varepsilon},\quad
H\geq\frac{1}{1-\gamma}\text{log}\frac{16}{(1-\gamma)^{3}\varepsilon}\quad\text{and}\quad
M_{k}=M\geq\frac{\gamma^{-2H}}{2}\text{log}\frac{2K|\mathcal{S}||\mathcal{A}|}{\delta}.$

Then with probability at least $1-\delta$,
$\|V^{\star}-V^{k}\|_{\infty}\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+\frac{1}{1-\gamma}\Big{)}+\frac{8}{(1-\gamma)^{3}}\gamma^{H}<\varepsilon$.
Choosing $K$, $H$ and $M$ to be tight to their lower-bounds, the corresponding
sample complexity is
$\tilde{O}\Big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{8}\varepsilon^{2}}\Big{)}$,
where the notation $\tilde{O}()$ hides poly-logarithmic factors.

The proof can be found in Appendix G.1. The sample complexity established by
[38] (Theorem 16) under a generative model and the same Q-estimator is
$\tilde{O}\Big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{8}\varepsilon^{2}}\Big{\|}\frac{d^{\star}_{\rho}}{\rho}\Big{\|}_{\infty}^{3}\Big{)}$.

In their work, [38] stresses the interest in reducing the dependence on both
$1/(1-\gamma)$ and the distribution mismatch coefficient in order to scale the
PMD guarantees to more relevant settings such as function approximation.
Theorem 5.1 partially resolves this matter by removing the dependence on the
distribution mismatch coefficient, which may scale with the size of the state
space (Appendix H.1). This makes the result dimension-optimal, which is
crucial when scaling the results to large or infinite state or action spaces.
The dependence on $1/(1-\gamma)$ remains distant from the $1/(1-\gamma)^{3}$
lower-bound of [6] (see Section 2). Whether this can be reached by PMD methods
remains open, though using a more suitable Q-estimator than (10) with our step
size regime and analysis, which extends to arbitrary Q-estimators, could bring
the sample complexity closer to this.

##  6 Analysis

In this section, we present the proof of Theorem 4.1. A key component in
establishing the $\gamma$-rate is avoiding the performance difference lemma
that we state in Appendix B. In prior works, the quantity that we are looking
to bound $V^{\star}(\rho)-V^{k}(\rho)$ arises through the performance
difference lemma. In particular, [38] use the lemma on $\mathbb{E}_{s\sim
d^{\star}_{\rho}}[\langle Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle]$,
which introduces a distribution mismatch coefficient in order to get a
recursion. On the other hand, we extract the value sub-optimalities
$V^{\star}(s)-V^{k}(s)$ and $\|V^{\star}-V^{k+1}\|_{\infty}$ directly from
$\langle Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle$ in (12). This leads
to an elegant analysis that may be of interest in the study of other methods,
and ultimately allows us to remove distribution mismatch factors and obtain an
exact $\gamma$-rate.

Proof of Theorem 4.1: Fix $s\in\mathcal{S}$ and $k\geq 0$. From Lemma A.2, we
have that $\langle Q^{k}_{s},\pi^{k+1}_{s}\rangle\leq\langle
Q^{k+1}_{s},\pi^{k+1}_{s}\rangle=V^{k+1}(s)$. This decouples the dependencies
on $\pi^{k}$ and $\pi^{k+1}$ below and is one of the ingredients that allows
us to bypass the performance difference lemma. Using this,

$\displaystyle\langle
Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle\geq\langle
Q^{k}_{s},\pi^{\star}_{s}\rangle-V^{k+1}(s)$ $\displaystyle=\langle
Q^{k}_{s}-Q^{\star}_{s},\pi^{\star}_{s}\rangle+\langle
Q^{\star}_{s},\pi^{\star}_{s}\rangle-V^{k+1}(s)$
$\displaystyle\geq-\|Q^{\star}_{s}-Q^{k}_{s}\|_{\infty}+V^{\star}(s)-V^{k+1}(s),$
(11)

where the last step uses Hölder’s inequality. Now we use that the difference
in state-action values of different policies for the same state-action pair
propagates the error to the next time-step, which is discounted by a factor of
$\gamma$. Formally, for any state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle Q^{\star}(s,a)-Q^{k}(s,a)$
$\displaystyle=\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)(V^{\star}(s^{\prime})-V^{k}(s^{\prime}))$
$\displaystyle\leq\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)\|V^{\star}-V^{k}\|_{\infty}=\gamma\|V^{\star}-V^{k}\|_{\infty},$

which is the same phenomenon that is responsible for the contraction of the
Bellman operator. This gives
$\|Q^{\star}_{s}-Q^{k}_{s}\|_{\infty}\leq\gamma\|V^{\star}-V^{k}\|_{\infty}$.
Plugging into Equation (11),

$\displaystyle
V^{\star}(s)-V^{k+1}(s)-\gamma\|V^{\star}-V^{k}\|_{\infty}\leq\langle
Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle.$

The rest of the proof relies on making the right-hand side of the above
arbitrarily small by taking a large enough step size. Choose any greedy policy
with respect to $Q^{k}_{s}$,
$\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}$,

$\displaystyle V^{\star}(s)-V^{k+1}(s)-\gamma\|V^{\star}-V^{k}\|_{\infty}$
$\displaystyle\leq\langle Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle$ (12)
$\displaystyle\leq\langle
Q^{k}_{s},\widetilde{\pi}^{k+1}_{s}-\pi^{k+1}_{s}\rangle$ (13)

where we use that $\widetilde{\pi}^{k+1}_{s}$ is greedy with respect to
$Q^{k}_{s}$. We then apply Lemma A.1 or (16) to $p=\widetilde{\pi}^{k+1}_{s}$,

$\displaystyle\langle
Q^{k}_{s},\widetilde{\pi}^{k+1}_{s}-\pi^{k+1}_{s}\rangle\leq\frac{D(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s})-D(\widetilde{\pi}^{k+1}_{s},\pi^{k+1}_{s})-D(\pi^{k+1}_{s},\pi^{k}_{s})}{\eta_{k}}\leq
D(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s})/\eta_{k}.$

Combining with (13) and noting that this holds for any
$\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}$, we have

$\displaystyle V^{\star}(s)-V^{k+1}(s)-\gamma\|V^{\star}-V^{k}\|_{\infty}$
$\displaystyle\leq\frac{1}{\eta_{k}}\text{min}_{\widetilde{\pi}^{k+1}_{s}\in\widetilde{\Pi}^{k+1}_{s}}D(\widetilde{\pi}^{k+1}_{s},\pi^{k}_{s})\leq
c_{k}$

from the step-size condition in the statement of the theorem. Rearranging and
recalling that $s$ and $k$ were arbitrary, we can choose $s$ where
$V^{\star}(s)-V^{k+1}(s)$ reaches its maximum value. We get

$\displaystyle\|V^{\star}-V^{k+1}\|_{\infty}$
$\displaystyle\leq\gamma\|V^{\star}-V^{k}\|_{\infty}+c_{k},$

and unravelling this recursion completes the proof. $\hfill\blacksquare$

##  7 Conclusion

In this paper, we have shown that the general family of exact policy mirror
descent algorithms in tabular MDPs under an adaptive step-size achieve the
same dimension-free linear $\gamma$-rate of convergence of classical
algorithms such as policy iteration. We provide matching lower-bounds that
establish this rate as optimal for PMD and the adaptive step-size as
necessary. We exploit a new approach to study the convergence of PMD, for
which avoiding the performance difference lemma is a key element. Though the
focus of our work is on the exact policy evaluation setting, the analysis
naturally extends to the inexact setting, given access to an estimator of the
action-value of a policy. We provide a result for a simple estimator under a
generative model that improves upon the best-known sample complexity, although
it still does not match the lower bound. Our method is general and applies to
any estimator, meaning our result could be improved by a better estimator.
Exploiting further algorithmic properties of PMD in the inexact setting may be
needed to bridge the gap to the optimal sample complexity, and determine if
PMD can match the lower bound in the inexact setting.

## Acknowledgments and Disclosure of Funding

EJ is funded by EPSRC through the Modern Statistics and Statistical Machine
Learning (StatML) CDT (grant no. EP/S023151/1).

We would like to thank the reviewers and meta-reviewers for their time and
feedback, which led to a better version of this paper.

## References

  * Abbasi-Yadkori et al. [2019] Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz.  POLITEX: Regret bounds for policy iteration using expert prediction.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 3692–3702. PMLR, 2019.
  * Agarwal et al. [2020] Alekh Agarwal, Sham Kakade, and Lin F. Yang.  Model-based reinforcement learning with a generative model is minimax optimal.  In _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 67–83. PMLR, 2020.
  * Agarwal et al. [2021] 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.
  * Alfano and Rebeschini [2022] Carlo Alfano and Patrick Rebeschini.  Linear convergence for natural policy gradient with log-linear policy parametrization.  2022\.  Preprint, arXiv: 2209.15382.
  * Alfano et al. [2023] Carlo Alfano, Rui Yuan, and Patrick Rebeschini.  A novel framework for policy mirror descent with general parametrization and linear convergence.  2023\.  Preprint, arXiv: 2301.13139.
  * Azar et al. [2013] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen.  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  _Machine Learning_ , 91(3):325–349, 2013.
  * Banerjee et al. [2005] Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh.  Clustering with bregman divergences.  _Journal of Machine Learning Research_ , 6(58):1705–1749, 2005.
  * Beck and Teboulle [2003] Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  _Operations Research Letters_ , 31(3):167–175, 2003.
  * Bellman [1957] Richard Bellman.  _Dynamic Programming_.  Dover Publications, 1957.
  * Bhandari and Russo [2019] Jalaj Bhandari and Daniel Russo.  Global optimality guarantees for policy gradient methods.  2019\.  Preprint, arXiv: 1906.01786.
  * Bhandari and Russo [2021] 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 of _Proceedings of Machine Learning Research_ , pages 2386–2394. PMLR, 2021.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends in Machine Learning_ , 8(3-4), 2015\.
  * Cen et al. [2021] 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, 2021\.
  * Chen and Teboulle [1993] Gong Chen and Marc Teboulle.  Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions.  _SIAM Journal on Optimization_ , 3(3):538–543, 1993.
  * Chen and Theja Maguluri [2022] Zaiwei Chen and Siva Theja Maguluri.  Sample complexity of policy-based methods under off-policy sampling and linear function approximation.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pages 11195–11214. PMLR, 2022.
  * Fearnley [2010] John Fearnley.  Exponential lower bounds for policy iteration.  In _Automata, Languages and Programming_ , pages 551–562, 2010.
  * Geist et al. [2019] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin.  A theory of regularized Markov decision processes.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2160–2169. PMLR, 2019.
  * Hollanders et al. [2012] Romain Hollanders, Jean-Charles Delvenne, and Raphaël M. Jungers.  The complexity of policy iteration is exponential for discounted markov decision processes.  In _51st IEEE Conference on Decision and Control (CDC)_ , pages 5997–6002, 2012.
  * Kakade and Langford [2002] Sham Kakade and John Langford.  Approximately Optimal Approximate Reinforcement Learning.  In _Proceedings of the 19th International Conference on Machine Learning_ , volume 2, pages 267–274, 2002.
  * Kakade [2001] Sham M Kakade.  A natural policy gradient.  In _Advances in Neural Information Processing Systems_ , volume 14, 2001.
  * Kearns and Singh [1998] Michael Kearns and Satinder Singh.  Finite-sample convergence rates for q-learning and indirect algorithms.  In _Advances in Neural Information Processing Systems_ , volume 11, 1998.
  * Khodadadian et al. [2021] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri.  On the linear convergence of natural policy gradient algorithm.  In _60th IEEE Conference on Decision and Control (CDC)_ , pages 3794–3799, 2021.
  * Konda and Tsitsiklis [1999] Vijay Konda and John Tsitsiklis.  Actor-critic algorithms.  In _Advances in Neural Information Processing Systems_ , volume 12, 1999.
  * Lan [2021] Guanghui Lan.  Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes.  _Mathematical Programming_ , 2021.
  * Lazaric et al. [2016] Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos.  Analysis of classification-based policy iteration algorithms.  _Journal of Machine Learning Research_ , 17(19):1–30, 2016.
  * Li et al. [2020] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen.  Breaking the sample size barrier in model-based reinforcement learning with a generative model.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 12861–12872, 2020.
  * Li et al. [2023] Yan Li, Guanghui Lan, and Tuo Zhao.  Homotopic policy mirror descent: Policy convergence, implicit regularization, and improved sample complexity.  _Mathematical Programming_ , 2023.
  * Liu et al. [2020] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin.  An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 7624–7636, 2020.
  * Puterman [1994] Martin L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  Wiley Series in Probability and Statistics. Wiley, 1994.
  * Rockafellar [1970] R. Tyrrell Rockafellar.  _Convex Analysis_.  Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970.
  * Scherrer [2013] Bruno Scherrer.  Improved and generalized upper bounds on the complexity of policy iteration.  In _Advances in Neural Information Processing Systems_ , volume 26, 2013.
  * Scherrer [2014] Bruno Scherrer.  Approximate policy iteration schemes: A comparison.  In _Proceedings of the 31st International Conference on Machine Learning_ , volume 32 of _Proceedings of Machine Learning Research_ , pages 1314–1322. PMLR, 2014.
  * Shani et al. [2020] Lior Shani, Yonathan Efroni, and Shie Mannor.  Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):5668–5675, 2020.
  * Sidford et al. [2018] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye.  Near-optimal time and sample complexities for solving markov decision processes with a generative model.  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, second edition, 2018.
  * Sutton et al. [1999] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In _Advances in Neural Information Processing Systems_ , volume 12, 1999.
  * Wainwright [2019] M. J. Wainwright.  Variance-reduced $Q$-learning is minimax optimal.  Technical report, UC Berkeley, 2019.  Preprint, arxiv:1906.04697.
  * Xiao [2022] Lin Xiao.  On the convergence rates of policy gradient methods.  _Journal of Machine Learning Research_ , 23(282):1–36, 2022.
  * Yuan et al. [2022] Rui Yuan, Robert M. Gower, and Alessandro Lazaric.  A general sample complexity analysis of vanilla policy gradient.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pages 3332–3380. PMLR, 2022.
  * Yuan et al. [2023] Rui Yuan, Simon Shaolei 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.
  * Zhan et al. [2023] 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.

##  Appendix A Properties of PMD

We present lemmas relevant to the analysis of PMD. Key to the analysis is the
Three-Point Descent Lemma, that relates the improvement of the proximal
gradient update compared to an arbitrary point. It originally comes from [14]
(Lemma 3.2) where a proof can be found, though we use a slightly modified
version from [38] (Lemma 6).

######  Lemma A.1 (Three-Point Descent Lemma, Lemma 6 in [38]).

Suppose that $\mathcal{C}\subset\mathbb{R}^{n}$ is a closed convex set,
$\phi:\mathcal{C}\rightarrow\mathbb{R}$ is a proper, closed convex function,
$D_{h}(\cdot,\cdot)$ is the Bregman divergence generated by a function h of
Legendre type and $\text{rint dom}h\cap\mathcal{C}\neq\emptyset$. For any
$x\in\text{rint dom}h$, let

$x^{+}=\text{argmin}_{u\in C}\\{\phi(u)+D_{h}(u,x)\\}.$ (14)

Then $x^{+}\in\text{rint dom }h\cap C$ and $\forall u\in C$,

$\phi(x^{+})+D_{h}(x^{+},x)\leq\phi(u)+D_{h}(u,x)-D_{h}(u,x^{+})$ (15)

The update (4) of PMD is an instance of the proximal minimisation (14) with
$\mathcal{C}=\Delta(\mathcal{A})$, $x=\pi^{k}_{s}$ and
$\phi(x)=-\eta_{k}\langle Q^{k}_{s},x\rangle$. Plugging these into (15), Lemma
A.1 relates the decrease in the proximal objective of $\pi^{k+1}_{s}$ to any
other policy, i.e. $\forall p\in\Delta(\mathcal{A})$,

$-\eta_{k}\langle
Q^{k}_{s},\pi^{k+1}_{s}\rangle+D_{h}(\pi^{k+1}_{s},\pi^{k}_{s})\leq-\eta_{k}\langle
Q^{k}_{s},p\rangle+D_{h}(p,\pi^{k}_{s})-D_{h}(p,\pi^{k+1}_{s}).$ (16)

This equation is key to the analysis in Section 6. In particular, it allows us
to prove the following lemma regarding the monotonic improvement in action-
value of PMD iterates. This is an extension of Lemma 7 in [38].

######  Lemma A.2.

Consider the policies produced by the iterative updates of PMD in (4). Then
for any $k\geq 0$,

$Q^{k+1}(s,a)\geq
Q^{k}(s,a),\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$

###  A.1 Proof of Lemma A.2

We first present Lemma 7 from [38], from which Lemma A.2 almost immediately
follows.

######  Lemma A.3 (Descent Property of PMD, Lemma 7 in [38]).

Consider the policies produced by the iterative updates of PMD in (4). Then
for any $k\geq 0$

$\langle Q^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle\geq 0,\quad\forall
s\in\mathcal{S},$ $V^{k+1}(\rho)\geq
V^{k}(\rho),\quad\forall\rho\in\Delta(\mathcal{S}).$

###### Proof.

From [38]. Recall that the Three-Point Descent Lemma states that $\forall
p\in\Delta(\mathcal{A})$,

$-\eta_{k}\langle
Q^{k}_{s},\pi^{k+1}_{s}\rangle+D_{h}(\pi^{k+1}_{s},\pi^{k}_{s})\leq-\eta_{k}\langle
Q^{k}_{s},p\rangle+D_{h}(p,\pi^{k}_{s})-D_{h}(p,\pi^{k+1}_{s}).$

Using this with $p=\pi^{k}_{s}$,

$\displaystyle
D_{h}(\pi^{k}_{s},\pi^{k+1}_{s})+D_{h}(\pi^{k+1}_{s},\pi^{k}_{s})\leq\eta_{k}\langle
Q^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle$

and since the Bregman divergences are none-negative and $\eta_{k}>0$,

$\displaystyle 0\leq\langle Q^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle$

and the result follows by an application of the performance difference lemma
(Appendix B)

$\displaystyle V^{k+1}(\rho)-V^{k}(\rho)$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{k+1}_{\rho}}\Big{[}\langle
Q^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle\Big{]}$ $\displaystyle\geq 0.$

Note that we use the performance difference lemma here because it gives a
simple concise proof, but we do not actually need to. To maintain our claim
that we avoid the use of the performance difference lemma, we can get the same
result without it. We sketch how to do this as follows. From the first part of
the lemma, we have

$\displaystyle\langle Q^{k}_{s},\pi^{k+1}_{s}\rangle\geq\langle
Q^{k}_{s},\pi^{k}_{s}\rangle=V^{k}(s),$

in all states $s$. Now note that the left hand side above is

$\displaystyle\langle Q^{k}_{s},\pi^{k+1}_{s}\rangle$
$\displaystyle=\sum_{a}\pi^{k+1}(a|s)Q^{k}(s,a)$
$\displaystyle=\sum_{a}\pi^{k+1}(a|s)\Big{(}r(s,a)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)V^{k}(s^{\prime})\Big{)}$

and we can then apply $\langle
Q^{k}_{s^{\prime}},\pi^{k+1}_{s^{\prime}}\rangle\geq V^{k}(s^{\prime})$ at
state $s^{\prime}$:

$\displaystyle V^{k}(s)$
$\displaystyle\leq\sum_{a}\pi^{k+1}(a|s)\Big{(}r(s,a)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)V^{k}(s^{\prime})\Big{)}$
$\displaystyle\leq\sum_{a}\pi^{k+1}(a|s)\Big{(}r(s,a)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)\sum_{a^{\prime}}\pi^{k+1}(a^{\prime}|s^{\prime})\Big{(}r(s^{\prime},a^{\prime})+\gamma\sum_{s^{\prime\prime}}p(s^{\prime\prime}|s^{\prime},a^{\prime})V^{k}(s^{\prime\prime})\Big{)}\Big{)}$

and proceeding iteratively in the limit you get exactly $V^{k+1}(s)$. ∎

Since Lemma A.3 holds for any $\rho\in\Delta(\mathcal{S})$, it guarantees that
the value in each state is non-decreasing for an update of PMD, i.e for all
$s\in\mathcal{S}$,

$\displaystyle V^{k+1}(s)-V^{k}(s)\geq 0.$

Using this, we get

$\displaystyle
Q^{k+1}(s,a)-Q^{k}(s,a)=\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\Big{(}V^{k+1}(s^{\prime})-V^{k}(s^{\prime})\Big{)}\geq
0,$

which concludes the proof. $\hfill\blacksquare$

###  A.2 Extension of Lemma A.2 to inexact setting:

As in the exact case, we first present Lemma 12 from [38] which is the
extension of Lemma A.3 to the inexact case. We note that in the inexact case,
we lose the monotonic increase of values due to the inaccuracy in our estimate
$\widehat{Q}^{k}$ of $Q^{k}_{s}$.

######  Lemma A.4.

Consider the policies produced by the iterative updates of IPMD in (9). For
any $k\geq 0$, if $\|\widehat{Q}^{k}_{s}-Q^{k}_{s}\|_{\infty}\leq\tau$, then

$\langle\widehat{Q}^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle\geq
0,\quad\forall s\in\mathcal{S},$ $V^{k+1}(\rho)\geq
V^{k}(\rho)-\frac{2\tau}{1-\gamma},\quad\forall\rho\in\Delta(\mathcal{S}).$

###### Proof.

From [38]. The Three-Point Descent Lemma applied to the IPMD update (9) gives
$\forall p\in\Delta(\mathcal{A})$,

$-\eta_{k}\langle\widehat{Q}^{k}_{s},\pi^{k+1}_{s}\rangle+D_{h}(\pi^{k+1}_{s},\pi^{k}_{s})\leq-\eta_{k}\langle\widehat{Q}^{k}_{s},p\rangle+D_{h}(p,\pi^{k}_{s})-D_{h}(p,\pi^{k+1}_{s}).$

Using this with $p=\pi^{k}_{s}$,

$\displaystyle
D_{h}(\pi^{k}_{s},\pi^{k+1}_{s})+D_{h}(\pi^{k+1}_{s},\pi^{k}_{s})\leq\eta_{k}\langle\widehat{Q}^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle$

and since the Bregman divergences are none-negative and $\eta_{k}>0$,

$\displaystyle
0\leq\langle\widehat{Q}^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle,$

which proves the first inequality. Now we cannot use the above inequality
directly with the performance difference lemma since $\widehat{Q}^{k}_{s}$ is
not the true action-value. Instead, we have

$\displaystyle V^{k+1}(\rho)-V^{k}(\rho)$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{k+1}_{\rho}}\Big{[}\langle
Q^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle\Big{]}$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{k+1}_{\rho}}\Big{[}\langle
Q^{k}_{s}-\widehat{Q}^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle+\langle\widehat{Q}^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle\Big{]}$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{k+1}_{\rho}}\Big{[}-\|Q^{k}_{s}-\widehat{Q}^{k}_{s}\|_{\infty}\|\pi^{k+1}_{s}-\pi^{k}_{s}\|_{1}\Big{]}$
$\displaystyle\geq\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{k+1}_{\rho}}\Big{[}-2\tau\Big{]}$ $\displaystyle=-\frac{2\tau}{1-\gamma}$

which concludes the proof. ∎

Using the above lemma, we can state and prove the extension of Lemma A.2 to
the inexact setting.

######  Lemma A.5.

Consider the policies produced by the iterative updates of IPMD in (9). For
any $k\geq 0$, if $\|\widehat{Q}^{k}_{s}-Q^{k}_{s}\|_{\infty}\leq\tau$, then

$\widehat{Q}^{k+1}(s,a)\geq\widehat{Q}^{k}(s,a)-\frac{2\tau\gamma}{1-\gamma},\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$

###### Proof.

As in the exact case, since Lemma A.4 holds for any
$\rho\in\Delta(\mathcal{S})$, it applies to each state, i.e for all
$s\in\mathcal{S}$,

$\displaystyle V^{k+1}(s)-V^{k}(s)\geq-\frac{2\tau}{1-\gamma}.$

Using this, we immediately have

$\displaystyle
Q^{k+1}(s,a)-Q^{k}(s,a)=\gamma\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\Big{(}V^{k+1}(s^{\prime})-V^{k}(s^{\prime})\Big{)}\geq\frac{-2\tau\gamma}{1-\gamma},$

which concludes the proof. ∎

##  Appendix B Performance difference lemma

######  Lemma B.1 (Performance Difference Lemma).

For any $\pi,\pi^{\prime}\in\Pi$, we have

$V^{\pi}(\rho)-V^{\pi^{\prime}}(\rho)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\pi}_{\rho}}\Big{[}\langle
Q^{\pi^{\prime}}_{s},\pi_{s}-\pi^{\prime}_{s}\rangle\Big{]}.$

The performance difference lemma [19] is a property that relates the
difference in values of policies to the policies themselves. The proof can be
found in their paper under Lemma 6.1.

##  Appendix C Guarantees of Theorem 4.1 for various step-size choices

We give here two more choices of $\\{c_{k}\\}_{k\in\mathbb{Z}_{\geq 0}}$ for
the step-size 5 of PMD and their corresponding guarantees from Theorem 4.1:

  * •

$c_{i}=c_{0}$ for some $c_{0}>0$ yields a step-size with a constant component.
The resulting bound is

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}\leq\gamma^{k}\|V^{\star}-V^{0}\|_{\infty}+\frac{c_{0}}{1-\gamma},$

which converges linearly up to some accuracy controlled by $c_{0}$.

  * •

$c_{i}=\gamma^{i+1}c_{0}$ for some initial $c_{0}>0$ will yield a step-size
with a component that is geometrically increasing as in [38], though at a
slower rate than the one discussed in Section 4. The resulting bound is

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+kc_{0}\Big{)},$

which converges linearly with the sought-for $\gamma$-rate, though in early
iterations the $k$ factor may dominate.

##  Appendix D Simulations

In this Section, we present simulations (see Figures 1-4 below) made by
running NPG (PMD with negative-entropy mirror map, see [22]) on the hard MDP
used to prove Theorem 4.2 \- see Appendix E for the details of the
construction. We use $n=25$ so $|\mathcal{S}|=51$ and $|\mathcal{A}|=2$. We
use $\delta=(1-\gamma)\gamma^{n}/100$, $\gamma=0.99$,
$\pi^{0}(a_{1}|s)=\alpha$ (note that $a_{1}$ is the optimal action in each
state). In each of the plots, we compare the performance of NPG using our
step-size (5) from Theorem 4.1 (denoted Adaptive in the plots and by ADA in
the discussion below) with $c_{k}=\gamma^{2k}$ and $c_{0}=1$ and the step-size
of [38] $\eta_{k}=\eta_{0}/\gamma^{k}$ (denoted by INC in the discussion
below) for a fixed $\eta_{0}=1$. In each of the plots, the left plot is
$\|V^{\star}-V^{k}\|_{\infty}$ against iterations and the right plot is
$\eta_{k}$ against iterations.

In all plots, the green curve represents the $\gamma$-rate. In particular it
is the curve of $y=\gamma^{x}$.

Discussion

With fixed initial step-size $\eta_{0}=1$ for INC, the convergence of NPG with
INC can be made arbitrarily slow in early iterations by choosing $\alpha$ (=
$\pi^{0}(a_{1}|s)$) closer to 0 (Figures 1-3). The convergence of NPG with ADA
is unaffected by small values of $\alpha$ because it adapts to them.

These observations agree with the theoretical results we established. Our
adaptive step-size (5) achieves the $\gamma$-rate (Theorem 4.1) and this is
optimal for iterations $k$ up until $n=25$ (Theorem 4.2). The adaptivity in
the step-size is necessary to achieve the $\gamma$-rate in these early
iterations (Theorem 4.3).

In later iterations (Figure 1: iterations $\approx 100$. Figure 2: iterations
$\approx 200$), INC has faster convergence than ADA. In these later
iterations, acting greedily with respect to the action value of the current
policy gives the optimal policy so INC converges faster because the step-size
is larger (see Figure 1-2 right plot). This suggests combining ADA and INC by
taking the maximum of both (Figure 4), yielding faster convergence than both.
This is encouraging for future-work on super-linear convergence (as discussed
in [38]) beyond the optimal $\gamma$-rate valid up to a finite iteration (see
Section 4.1).

Figure 1: $\alpha=10^{-1}$. Green curve: $y=\gamma^{x}$.

Figure 2: $\alpha=10^{-10}$. Green curve: $y=\gamma^{x}$.

Figure 3: $\alpha=10^{-50}$. Green curve: $y=\gamma^{x}$.

Figure 4: $\alpha=10^{-10}$. $\eta_{k}$ = max(Adaptive, $\eta_{0}/\gamma^{k}$)
means the step-size is chosen as the largest between our "Adaptive" and the
geometrically increasing of [38]. Green curve: $y=\gamma^{x}$.

##  Appendix E Proof of Theorem 4.2

Figure 5: Example MDP used in the proof of Theorem 4.2

Fix $n>0$ and $\delta\in(0,(1-\gamma)\gamma^{n})$. Consider the MDP shown in
Figure 5. The state space is
$\mathcal{S}=\\{s_{0},s_{1},s_{1}^{\prime},...,s_{n},s_{n}^{\prime}\\}$ and
the action space is $\mathcal{A}=\\{a_{1},a_{2}\\}$. There is a chain of
states of length $n+1$ with the states indexed from $0$ to $n$. The left-most
state ($s_{0}$) is absorbing with reward +1. In the other states in the chain
($s_{i}$ for $i=1,...,n$), the agent can take action $a_{1}$ and move left (to
$s_{i-1}$) with reward of 0, or take action $a_{2}$ and move to an additional
absorbing state unique to the state it is currently in ($s_{i}^{\prime}$) with
reward $r_{i}=\gamma^{i+1}+\delta$ (that the agent also receives in that state
for all future time-steps). Summarising, we have for $1\leq i\leq n$

$\displaystyle p(s_{i-1}|s_{i},a_{1})=1,\quad r(s_{i},a_{1})=0,$
$\displaystyle p(s_{i}^{\prime}|s_{i},a_{2})=1,\quad
r(s_{i},a_{2})=r_{i}=\gamma^{i+1}+\delta,$ $\displaystyle
p(s_{i}^{\prime}|s_{i}^{\prime},a)=1,\quad
r(s_{i}^{\prime},a)=r_{i}=\gamma^{i+1}+\delta\quad\forall a\in\mathcal{A}.$

The value of $\delta$ is carefully restricted so that the optimal action in
all the states of the chain is $a_{1}$. The proof will consist in showing that
if the agent starts with an initial policy that places most probability mass
on the sub-optimal action $a_{2}$, then it has to learn that $a_{1}$ is the
optimal action in the state directly to the left before it can start switching
from action $a_{2}$ to $a_{1}$ in the current state. And this can at best
happen one iteration at a time starting starting from the left-most state. In
particular, we consider $\pi^{0}$ s.t $\pi^{0}(a_{1}|s)=\alpha$,
$\pi^{0}(a_{2}|s)=1-\alpha$ for all states and some $\alpha$ s.t
$0<\alpha\leq\delta(1-\gamma)$. We make the following claim from which the
result will follow straightforwardly.

Claim: Fix $k<n$. The policies produced by PMD satisfy
$\pi^{k}(a_{1}|s_{i})\leq\alpha$ for $k<i\leq n$.

We prove this claim by induction.

Base Case: We want to show that $\pi^{1}(a_{1}|s_{i})\leq\alpha$ for $i>1$. We
do this by showing that $Q^{0}(s_{i},a_{1})\leq Q^{0}(s_{i},a_{2})$ for $i>1$
so that the probability of $\pi^{1}(a_{1}|s_{i})$ cannot increase w.r.t
$\pi^{0}(a_{1}|s_{i})$, which is $\alpha$ (this follows from $\langle
Q^{k}_{s},\pi^{k+1}_{s}-\pi^{k}_{s}\rangle\geq 0$ for all iterations of PMD).
We have:

$\displaystyle Q^{0}(s_{i},a_{1})$ $\displaystyle=\gamma V^{0}(s_{i-1})$
$\displaystyle=\gamma\Big{(}\alpha
Q^{0}(s_{i-1},a_{1})+(1-\alpha)Q^{0}(s_{i-1},a_{2})\Big{)}$
$\displaystyle\leq\gamma\Big{(}\alpha\frac{\gamma^{i-1}}{1-\gamma}+\frac{r_{i-1}}{1-\gamma}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\gamma\Big{(}\delta(1-\gamma)\frac{\gamma^{i-1}}{1-\gamma}+\frac{\gamma^{i}+\delta}{1-\gamma}\Big{)}$
$\displaystyle=\frac{\gamma^{i+1}}{1-\gamma}+\frac{\delta\gamma(1+\gamma^{i-1}-\gamma^{i})}{1-\gamma}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\gamma^{i+1}}{1-\gamma}+\frac{\delta}{1-\gamma}$
$\displaystyle=Q^{0}(s_{i},a_{2}),$

where we used $\alpha\leq\delta(1-\gamma)$ in (a) and
$\gamma(1+\gamma^{i-1}-\gamma^{i})<1$ for $\gamma\in[0,1)$ in (b). This
concludes the base case.

Inductive Step: Now assume that the claim is true for $k$ and we want to show
that $\pi^{k+1}(a_{1}|s_{i})\leq\alpha$ for $i>k+1$. We do this in the same
way as the base case by showing that $Q^{k}(s_{i},a_{1})\leq
Q^{k}(s_{i},a_{2})$ for $i>k+1$ so that the probability of
$\pi^{k+1}(a_{1}|s_{i})$ cannot increase w.r.t $\pi^{k}(a_{1}|s_{i})$, which
is less than or equal to $\alpha$ by the inductive hypothesis. We have:

$\displaystyle Q^{k}(s_{i},a_{1})$ $\displaystyle=\gamma V^{k}(s_{i-1})$
$\displaystyle=\gamma\Big{(}\pi^{k}(a_{1}|s_{i-1})Q^{k}(s_{i-1},a_{1})+\pi^{k}(a_{2}|s_{i-1})Q^{k}(s_{i-1},a_{2})\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\gamma\Big{(}\alpha
Q^{k}(s_{i-1},a_{1})+Q^{k}(s_{i-1},a_{2})\Big{)}$
$\displaystyle\leq\gamma\Big{(}\alpha\frac{\gamma^{i-1}}{1-\gamma}+\frac{r_{i-1}}{1-\gamma}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\gamma\Big{(}\delta(1-\gamma)\frac{\gamma^{i-1}}{1-\gamma}+\frac{\gamma^{i}+\delta}{1-\gamma}\Big{)}$
$\displaystyle=\frac{\gamma^{i+1}}{1-\gamma}+\frac{\delta\gamma(1+\gamma^{i-1}-\gamma^{i})}{1-\gamma}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{\gamma^{i+1}}{1-\gamma}+\frac{\delta}{1-\gamma}$
$\displaystyle=Q^{k}(s_{i},a_{2}),$

where we used in (a) that $\pi^{k}(a_{1}|s_{i-1})\leq\alpha$ for $i>k+1$,
which is true by the inductive hypothesis since $i-1>k$, in (b) that
$\alpha\leq\delta(1-\gamma)$ and in (c) that
$\gamma(1+\gamma^{i-1}-\gamma^{i})<1$ for $\gamma\in[0,1)$. This concludes the
proof of the claim.

Now using the claim

$\displaystyle V^{k}(s_{k+1})$
$\displaystyle=\pi^{k}(a_{1}|s_{k+1})Q^{k}(s_{k+1},a_{1})+\pi^{k}(a_{2}|s_{k+1})Q^{k}(s_{k+1},a_{2})$
$\displaystyle\leq\alpha\frac{\gamma^{k+1}}{1-\gamma}+\frac{r_{k+1}}{1-\gamma}$
$\displaystyle=\alpha\frac{\gamma^{k+1}}{1-\gamma}+\frac{\gamma^{k+2}+\delta}{1-\gamma},$

so

$\displaystyle V^{\star}(s_{k+1})-V^{k}(s_{k+1})$
$\displaystyle\geq\frac{\gamma^{k+1}}{1-\gamma}-\alpha\frac{\gamma^{k+1}}{1-\gamma}-\frac{\gamma^{k+2}+\delta}{1-\gamma}$
$\displaystyle=\frac{\gamma^{k+1}(1-\gamma)}{1-\gamma}-\frac{\alpha\gamma^{k+1}+\delta}{1-\gamma}$
$\displaystyle\geq\gamma^{k+1}-\frac{\alpha+\delta}{1-\gamma}$
$\displaystyle\geq\gamma^{k+1}-\frac{2\delta}{1-\gamma},$ (17)

where we used that $\alpha\leq\delta$. Now note that

$\displaystyle V^{0}(s_{1})$ $\displaystyle=\alpha
Q^{0}(s_{1},a_{1})+(1-\alpha)Q^{0}(s_{1},a_{2})$
$\displaystyle=\alpha\frac{\gamma}{1-\gamma}+(1-\alpha)\frac{\gamma^{2}+\delta}{1-\gamma},$

so

$\displaystyle V^{\star}(s_{1})-V^{0}(s_{1})$
$\displaystyle=\frac{\gamma}{1-\gamma}-\alpha\frac{\gamma}{1-\gamma}-(1-\alpha)\frac{\gamma^{2}+\delta}{1-\gamma}$
$\displaystyle=(1-\alpha)\frac{\gamma}{1-\gamma}-(1-\alpha)\frac{\gamma^{2}+\delta}{1-\gamma}$
$\displaystyle=\frac{1-\alpha}{1-\gamma}\Big{(}\gamma-\gamma^{2}-\delta\Big{)}$
$\displaystyle\leq\frac{1-\alpha}{1-\gamma}\Big{(}\gamma-\gamma^{2}\Big{)}$
$\displaystyle=\gamma\frac{1-\alpha}{1-\gamma}\Big{(}1-\gamma\Big{)}$
$\displaystyle=\gamma(1-\alpha)$ $\displaystyle\leq\gamma$

and by induction we can show this is the case for all states (above is base
case), the inductive step is as follows (assuming
$V^{\star}(s_{k})-V^{0}(s_{k})\leq\gamma$),

$\displaystyle V^{\star}(s_{k+1})-V^{0}(s_{k+1})$
$\displaystyle=\frac{\gamma^{k+1}}{1-\gamma}-(1-\alpha)\frac{\gamma^{k+2}+\delta}{1-\gamma}-\alpha\gamma
V^{0}(s_{k})$
$\displaystyle=(1-\alpha)\Big{[}\frac{\gamma^{k+1}-\gamma^{k+2}-\delta}{1-\gamma}\Big{]}+\alpha\gamma\Big{[}V^{\star}(s_{k})-V^{0}(s_{k})\Big{]}$
$\displaystyle\leq(1-\alpha)\gamma^{k+1}+\alpha\gamma^{2}$
$\displaystyle\leq\gamma$

and so

$\displaystyle\|V^{\star}-V^{0}\|_{\infty}\leq\gamma,$

which combining with (17) gives,

$\displaystyle
V^{\star}(s_{k+1})-V^{k}(s_{k+1})\geq\gamma^{k}\|V^{\star}-V^{0}\|_{\infty}-\frac{2\delta}{1-\gamma}$
$\displaystyle\implies$
$\displaystyle\|V^{\star}-V^{k}\|_{\infty}\geq\gamma^{k}\|V^{\star}-V^{0}\|_{\infty}-\frac{2\delta}{1-\gamma}.$

Choosing
$\delta=\frac{(1-\gamma)}{4}\gamma^{n}\|V^{\star}-V^{0}\|_{\infty}\leq\frac{(1-\gamma)}{4}\gamma^{n+1}$
(which is in the valid range of $\delta$) concludes the proof since
$\frac{2\delta}{1-\gamma}\leq\frac{1}{2}\gamma^{k}\|V^{\star}-V^{0}\|_{\infty}$.
$\hfill\blacksquare$

##  Appendix F Proof of Theorem 4.3

Consider the same MDP as in the proof of Theorem 4.2 in Appendix E (see Figure
5). Denote $c=\frac{1-\gamma}{8}$ and note that
$c<\frac{\sqrt{\gamma}}{1+\sqrt{\gamma}}\frac{1-\gamma}{2}$ since
$\frac{1}{4}<\frac{\sqrt{\gamma}}{1+\sqrt{\gamma}}$ for $\gamma>0.2$.

Suppose you consider NPG updates with initial policy
$\pi^{0}(a_{1}|s_{i})=\alpha$. Recall that NPG is the instance of PMD with
relative entropy as the mirror map. It can be shown that NPG has the closed
form update

$\displaystyle\pi^{k+1}(a|s)=\frac{\pi^{k}(a|s)e^{\eta_{k}Q^{k}(s,a)}}{\sum_{a^{\prime}}\pi^{k}(a^{\prime}|s)e^{\eta_{k}Q^{k}(s,a^{\prime})}}.$

We know from the proof of Theorem E that for any step-size regime, for $i>k+1$

$\displaystyle Q^{k}(s_{i},a_{1})\leq Q^{k}(s_{i},a_{2}).$

Now,
$\|V^{\star}-V^{0}\|_{\infty}=V^{\star}(s_{1})-V^{0}(s_{1})\leq\gamma-\frac{\delta}{1-\gamma}$
(see Section F.1 below). The idea of the proof is to show that satisfying the
bound given in the statement of the theorem will imply that a certain
condition on the step-size.

Fix a state $s_{k}$ and let $k_{0}$ be the first iteration where
$Q^{k_{0}}(s_{k},a_{1})>Q^{k_{0}}(s_{k},a_{2})$. By the above, we must have
$k\leq k_{0}+1$, or $k_{0}\geq k-1$. By the proof of Theorem E, we also have
$\pi^{k_{0}}(a_{1}|s_{k})\leq\alpha$ (before iteration $k_{0}$,
$Q(s_{k},\cdot)$ favors $a_{2}$, so $\pi^{k_{0}}(a_{1}|s_{k})$ has not
increased compared to $\pi^{0}(a_{1}|s_{k})=\alpha$).

We want a $\gamma$-contraction at every iteration, i.e. we assume the
following is satisfied:

$\displaystyle
V^{\star}(s_{k})-V^{k_{0}+1}(s_{k})\leq\gamma^{k_{0}+1}(\|V^{\star}-V^{0}\|_{\infty}+c)\leq\gamma^{k_{0}+1}(\gamma-\frac{\delta}{1-\gamma}+c).$

Now, by direct computation,

$\displaystyle V^{\star}(s_{k})-V^{k_{0}+1}(s_{k})$
$\displaystyle=\pi^{k_{0}+1}(a_{1}|s_{k})\gamma(V^{\star}(s_{k-1})-V^{k_{0}+1}(s_{k-1}))+\pi^{k_{0}+1}(a_{2}|s_{2})\frac{\gamma^{k}-r_{k}}{1-\gamma}$
$\displaystyle\geq\pi^{k_{0}+1}(a_{2}|s_{2})\frac{\gamma^{k}-r_{k}}{1-\gamma}=\pi^{k_{0}+1}(a_{2}|s_{2})(\gamma^{k}-\frac{\delta}{1-\gamma}).$

Putting this together with the above (this is an implication as this is about
the necessity rather than sufficiency), we must have:

$\displaystyle\pi^{k_{0}+1}(a_{2}|s_{2})(\gamma^{k}-\frac{\delta}{1-\gamma})\leq\gamma^{k_{0}+1}(\gamma-\frac{\delta}{1-\gamma}+c)$
$\displaystyle\implies$
$\displaystyle\pi^{k_{0}+1}(a_{2}|s_{2})\leq\frac{\gamma^{k_{0}+1}(\gamma-\frac{\delta}{1-\gamma}+c)}{(\gamma^{k}-\frac{\delta}{1-\gamma})}=\beta$

If we choose $\delta<\frac{1}{2}(1-\gamma)(1-\sqrt{\gamma})\gamma^{k}$ then
$\beta<\sqrt{\gamma}$ and require

$\displaystyle\pi^{k_{0}+1}(a_{2}|s_{2})\leq\sqrt{\gamma}.$

To see this, start from $\beta\leq\sqrt{\gamma}$, this is equivalent to

$\displaystyle\frac{\gamma^{k_{0}+1}(\gamma-\frac{\delta}{1-\gamma}+c)}{(\gamma^{k}-\frac{\delta}{1-\gamma})}\leq\sqrt{\gamma}$
$\displaystyle\impliedby$
$\displaystyle\frac{\gamma^{k}(\gamma-\frac{\delta}{1-\gamma}+c)}{(\gamma^{k}-\frac{\delta}{1-\gamma})}\leq\sqrt{\gamma}\quad\text{
since }k_{0}+1\geq k$ $\displaystyle\iff$
$\displaystyle\gamma^{k}(\gamma-\frac{\delta}{1-\gamma}+c)\leq\sqrt{\gamma}(\gamma^{k}-\frac{\delta}{1-\gamma})$
$\displaystyle\impliedby$
$\displaystyle\gamma^{k}(\gamma+c)\leq\sqrt{\gamma}(\gamma^{k}-\frac{\delta}{1-\gamma})$
$\displaystyle\iff$
$\displaystyle\gamma^{k-\frac{1}{2}}(\gamma+c)\leq\gamma^{k}-\frac{\delta}{1-\gamma}$
$\displaystyle\iff$
$\displaystyle\frac{\delta}{1-\gamma}\leq\gamma^{k-\frac{1}{2}}(\sqrt{\gamma}-\gamma-c)$
$\displaystyle\impliedby$
$\displaystyle\frac{\delta}{1-\gamma}\leq\gamma^{k-\frac{1}{2}}(\sqrt{\gamma}-\gamma-\frac{\sqrt{\gamma}}{1+\sqrt{\gamma}}\frac{1-\gamma}{2})\quad\text{
since }-c>-\frac{\sqrt{\gamma}}{1+\sqrt{\gamma}}\frac{1-\gamma}{2}$
$\displaystyle\iff$
$\displaystyle\frac{\delta}{1-\gamma}\leq\gamma^{k-\frac{1}{2}}(\sqrt{\gamma}-\gamma-\frac{\sqrt{\gamma}}{2}(1-\sqrt{\gamma}))$
$\displaystyle\iff$
$\displaystyle\frac{\delta}{1-\gamma}\leq\gamma^{k-\frac{1}{2}}(\sqrt{\gamma}-\gamma-\frac{\sqrt{\gamma}}{2}+\frac{\gamma}{2})$
$\displaystyle\iff$
$\displaystyle\frac{\delta}{1-\gamma}\leq\gamma^{k-\frac{1}{2}}(\frac{\sqrt{\gamma}}{2}-\frac{\gamma}{2})$
$\displaystyle\iff$
$\displaystyle\delta\leq\frac{1}{2}\gamma^{k}(1-\sqrt{\gamma})(1-\gamma),$

which is the condition for $\delta$ we imposed initially.

To achieve the above condition $\pi^{k_{0}+1}(a_{2}|s_{2})\leq\sqrt{\gamma}$,
recalling that $\pi^{k_{0}}(a_{2}|s_{2})\geq 1-\alpha$, $\eta_{k_{0}}$ has to
satisfy

$\displaystyle\eta_{k_{0}}\geq\frac{1}{Q^{k_{0}}(s_{k},a_{1})-Q^{k_{0}}(s_{k},a_{2})}\Big{[}\log((1-\alpha)(1-\sqrt{\gamma}))+KL(\tilde{\pi}^{k_{0}+1}_{s_{k}},\pi^{k_{0}}_{s_{k}})\Big{]}$

To see this, again start from $\pi^{k_{0}+1}(a_{2}|s_{2})\leq\sqrt{\gamma}$,
this is equivalent to (use $k_{0}=m$ for simplicity of notation) using the
closed-form update of NPG:

$\displaystyle\pi^{m}(a_{2}|s_{2})\exp(\eta_{m}Q^{m}(s_{k},a_{2}))\leq$
$\displaystyle\sqrt{\gamma}(\pi^{m}(a_{2}|s_{2})\exp(\eta_{m}Q^{m}(s_{k},a_{2}))+\pi^{m}(a_{1}|s_{2})\exp(\eta_{m}Q^{m}(s_{k},a_{1})))$
$\displaystyle\iff$ $\displaystyle\frac{1}{\sqrt{\gamma}}\leq
1+\frac{\pi^{m}(a_{1}|s_{2})}{\pi^{m}(a_{2}|s_{2})}\exp(\eta_{m}(Q^{m}(s_{k},a_{1})-Q^{m}(s_{k},a_{2})))$
$\displaystyle\iff$
$\displaystyle\frac{1-\sqrt{\gamma}}{\sqrt{\gamma}}\frac{\pi^{m}(a_{2}|s_{2})}{\pi^{m}(a_{1}|s_{2})}\leq\exp(\eta_{m}(Q^{m}(s_{k},a_{1})-Q^{m}(s_{k},a_{2})))$
$\displaystyle\iff$
$\displaystyle\eta_{m}(Q^{m}(s_{k},a_{1})-Q^{m}(s_{k},a_{2}))\geq\log\Big{(}\frac{1-\sqrt{\gamma}}{\sqrt{\gamma}}\frac{\pi^{m}(a_{2}|s_{2})}{\pi^{m}(a_{1}|s_{2})}\Big{)}$
$\displaystyle\iff$
$\displaystyle\eta_{m}\geq\frac{1}{Q^{m}(s_{k},a_{1})-Q^{m}(s_{k},a_{2})}\Big{[}\log\Big{(}\frac{1-\sqrt{\gamma}}{\sqrt{\gamma}}\pi^{m}(a_{2}|s_{2})\Big{)}+\log\Big{(}\frac{1}{\pi^{m}(a_{1}|s_{2})}\Big{)}\Big{]}$
$\displaystyle\implies$
$\displaystyle\eta_{m}\geq\frac{1}{Q^{m}(s_{k},a_{1})-Q^{m}(s_{k},a_{2})}\Big{[}\log\Big{(}(1-\alpha)\frac{1-\sqrt{\gamma}}{\sqrt{\gamma}}\Big{)}+KL(\tilde{\pi}^{m+1}_{s_{k}},\pi^{m}_{s_{k}})\Big{]}$
$\displaystyle\implies$
$\displaystyle\eta_{m}\geq\frac{1}{Q^{m}(s_{k},a_{1})-Q^{m}(s_{k},a_{2})}\Big{[}\log\Big{(}(1-\alpha)(1-\sqrt{\gamma})\Big{)}+KL(\tilde{\pi}^{m+1}_{s_{k}},\pi^{m}_{s_{k}})\Big{]}.$

As we take $\alpha\rightarrow 0$, the KL term will dominate. In particular,
note $\alpha<1-\gamma$ so $1-\alpha>\gamma$ and

$\displaystyle(1-\alpha)(1-\sqrt{\gamma})>\gamma(1-\sqrt{\gamma})$

and if we further impose the condition
$\alpha<\gamma^{2}(1-\sqrt{\gamma})^{2}$ then

$\displaystyle(1-\alpha)(1-\sqrt{\gamma})>\sqrt{\alpha}>\sqrt{\pi^{k_{0}}(a_{1}|s_{2})}$

and the step-size needs to satisfy the following condition:

$\displaystyle\eta_{k_{0}}$
$\displaystyle\geq\frac{1}{Q^{k_{0}}(s_{k},a_{1})-Q^{k_{0}}(s_{k},a_{2})}\Big{[}\log(\sqrt{\pi^{k_{0}}(a_{1}|s_{2})})+KL(\tilde{\pi}^{k_{0}+1}_{s_{k}},\pi^{k_{0}}_{s_{k}})\Big{]}$
$\displaystyle=\frac{1}{Q^{k_{0}}(s_{k},a_{1})-Q^{k_{0}}(s_{k},a_{2})}\Big{[}-\frac{1}{2}KL(\tilde{\pi}^{k_{0}+1}_{s_{k}},\pi^{k_{0}}_{s_{k}})+KL(\tilde{\pi}^{k_{0}+1}_{s_{k}},\pi^{k_{0}}_{s_{k}})\Big{]}$
$\displaystyle=\frac{1}{2(Q^{k_{0}}(s_{k},a_{1})-Q^{k_{0}}(s_{k},a_{2}))}KL(\tilde{\pi}^{k_{0}+1}_{s_{k}},\pi^{k_{0}}_{s_{k}})$
(18)

Distinct Iterations: Note that the iteration $k_{0}(s_{k})$ where
$Q(\cdot,s_{k})$ starts becoming bigger at $a_{1}$ that $a_{2}$ is distinct
for each $s_{k}$. Fix any $s_{k}$ and $k_{0}=k_{0}(s_{k})$. We have

$\displaystyle Q^{k_{0}}(s_{k},a_{1})<Q^{k_{0}}(s_{k},a_{2})$ $\displaystyle
Q^{{k_{0}}+1}(s_{k},a_{2})\leq Q^{{k_{0}}+1}(s_{k},a_{1})$

then $\pi^{{k_{0}}+1}(a_{1}|s_{k})\leq\pi^{k_{0}}(a_{1}|s_{k})\leq\alpha$
(since $Q^{t}$ points towards $a_{2}$ in $s_{k}$ for all $t\leq k_{0}$). Then
applying exactly the same steps as in the proof of Theorem 4.2, we have

$\displaystyle Q^{{k_{0}}+1}(s_{k+1},a_{1})<Q^{{k_{0}}+1}(s_{k+1},a_{2}),$

meaning that $k_{0}(s_{k})$ is disctinct to $k_{0}(s_{k+1})$.

Upper Bounding Q-value difference: We want to upper-bound the Q-value
difference appearing in the step-size condition above. We have,

$\displaystyle Q^{k_{0}}(s_{k},a_{2})$
$\displaystyle=\frac{r_{k}}{1-\gamma}=\frac{\gamma^{k+1}+\delta}{1-\gamma}$
$\displaystyle Q^{k_{0}}(s_{k},a_{1})$ $\displaystyle=\gamma
V^{k_{0}}(s_{k-1})\leq\frac{\gamma^{k}}{1-\gamma}.$

So,

$\displaystyle Q^{k_{0}}(s_{k},a_{1})-Q^{k_{0}}(s_{k},a_{2})$
$\displaystyle\leq\frac{\gamma^{k}}{1-\gamma}-\frac{\gamma^{k+1}+\delta}{1-\gamma}$
$\displaystyle=\gamma^{k}-\frac{\delta}{1-\gamma}$
$\displaystyle\leq\gamma^{k}.$

Plugging this into the above bound (18), if the iterates of NPG are to satisfy
the bound with the $\gamma$-rate in the statement of the theorem, the step-
size must at least satisfy the following condition:

$\displaystyle\eta_{k_{0}}$
$\displaystyle\geq\frac{1}{2\gamma^{k}}KL(\tilde{\pi}^{k_{0}+1}_{s_{k}},\pi^{k_{0}}_{s_{k}}),$

which concludes the proof. $\hfill\blacksquare$

###  F.1 Largest sub-optimality gap at iteration 0

In this section, we prove the claim that

$\displaystyle\|V^{\star}-V^{0}\|_{\infty}=V^{\star}(s_{1})-V^{0}(s_{1})\leq\gamma-\frac{\delta}{1-\gamma}$

Proof: First of all,
$V^{\star}(s_{1})-V^{0}(s_{1})=\pi^{0}(a_{2}|s_{1})\frac{\gamma-
r_{1}}{1-\gamma}=(1-\alpha)(\gamma-\frac{\delta}{1-\gamma})\leq\gamma-\frac{\delta}{1-\gamma}$.
For the first part, we proceed by induction. We will use throughout that

$\displaystyle\frac{\gamma^{k}-r_{k}}{1-\gamma}=\gamma^{k}-\frac{\delta}{1-\gamma}\leq
V^{\star}(s_{1})-V^{0}(s_{1})=(1-\alpha)(\gamma-\frac{\delta}{1-\gamma}).$

This is true if (when LHS is the largest)

$\displaystyle\gamma^{2}-\frac{\delta}{1-\gamma}\leq(1-\alpha)(\gamma-\frac{\delta}{1-\gamma})$

which holds when

$\displaystyle\alpha\leq\frac{\gamma(1-\gamma)^{2}}{\gamma(1-\gamma)-\delta}$
$\displaystyle\impliedby$ $\displaystyle\alpha\leq 1-\gamma$

Base Case:

$\displaystyle V^{\star}(s_{2})-V^{0}(s_{2})$
$\displaystyle=\alpha\gamma(V^{\star}(s_{1})-V^{0}(s_{1}))+(1-\alpha)\frac{\gamma^{2}-r_{2}}{1-\gamma}$
$\displaystyle\leq\alpha\gamma(V^{\star}(s_{1})-V^{0}(s_{1}))+(1-\alpha)(V^{\star}(s_{1})-V^{0}(s_{1}))$
$\displaystyle\leq V^{\star}(s_{1})-V^{0}(s_{1})$

Inductive Step: Assume true for $k$. Then,

$\displaystyle V^{\star}(s_{k+1})-V^{0}(s_{k+1})$
$\displaystyle=\alpha\gamma(V^{\star}(s_{k})-V^{0}(s_{k}))+(1-\alpha)\frac{\gamma^{k+1}-r_{k+1}}{1-\gamma}$
$\displaystyle\leq\alpha\gamma(V^{\star}(s_{1})-V^{0}(s_{1}))+(1-\alpha)(V^{\star}(s_{1})-V^{0}(s_{1}))$
$\displaystyle\leq V^{\star}(s_{1})-V^{0}(s_{1}),$

which concludes the proof. $\hfill\blacksquare$

##  Appendix G Inexact policy mirror descent and the generative model

The following Lemma from [38] controls the accuracy of the estimator
$\widehat{Q}^{k}_{s}$ specified in (10) of Section 5 with respect to $H$ and
$M_{k}$:

######  Lemma G.1 (Lemma 15 in [38]).

Consider using (10) to estimate $Q^{k}_{s}$ for all state-action pairs for $K$
iterations of IPMD. Then for $\delta\in(0,1)$, if for all $k\leq K$,

$M_{k}\geq\frac{\gamma^{-2H}}{2}\text{log}\big{(}\frac{2K|\mathcal{S}||\mathcal{A}|}{\delta}\big{)}.$

Then with probability at least $1-\delta$, we have for all $k\leq K$,

$\|\widehat{Q}^{k}_{s}-Q^{k}_{s}\|_{\infty}\leq\frac{2\gamma^{H}}{1-\gamma}.$

The proof of this result can be found in Lemma 15 of [38].

###  G.1 Proof of Theorem 5.1

This proof is similar to that of [38] (Theorem 14). It is also similar in
structure to the proof of Theorem 4.1 in Section 6.

Fix a state $s\in\mathcal{S}$ and an integer $k\geq 0$. For now let’s assume
that our Q-estimates are $\tau$-accurate ($\tau>0$), i.e.

$\displaystyle\|Q^{k}-\widehat{Q}^{k}\|_{\infty}\leq\tau$

for all $k\geq 0$. With this assumption, we have from Lemma A.5 in Appendix
A.1,

$\displaystyle Q^{k+1}(s,a)\geq
Q^{k}(s,a)-\frac{2\gamma\tau}{1-\gamma},\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$

Now proceeding in a similar way to Section 6,

$\displaystyle\langle\widehat{Q}^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle$
$\displaystyle=\langle
Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle+\langle\widehat{Q}^{k}_{s}-Q^{k}_{s},\pi^{\star}_{s}-\pi^{k+1}_{s}\rangle$
$\displaystyle\geq\langle Q^{k}_{s},\pi^{\star}_{s}\rangle-\langle
Q^{k}_{s},\pi^{k+1}_{s}\rangle-\|\widehat{Q}^{k}_{s}-Q^{k}_{s}\|_{\infty}\|\pi^{\star}_{s}-\pi^{k+1}_{s}\|_{1}$
$\displaystyle\geq\langle Q^{k}_{s},\pi^{\star}_{s}\rangle-\langle
Q^{k+1}_{s},\pi^{k+1}_{s}\rangle-\frac{2\gamma\tau}{1-\gamma}-2\tau$
$\displaystyle\geq\langle
Q^{k}_{s},\pi^{\star}_{s}\rangle-V^{k+1}(s)-\frac{4\gamma\tau}{1-\gamma}$
$\displaystyle=\langle
Q^{k}_{s}-Q^{\star}_{s},\pi^{\star}_{s}\rangle+V^{\star}(s)-V^{k+1}(s)-\frac{4\gamma\tau}{1-\gamma}$
$\displaystyle\geq-\|Q^{\star}_{s}-Q^{k}_{s}\|_{\infty}+V^{\star}(s)-V^{k+1}(s)-\frac{4\gamma\tau}{1-\gamma}$
$\displaystyle\geq-\gamma\|V^{\star}-V^{k}\|_{\infty}+V^{\star}(s)-V^{k+1}(s)-\frac{4\gamma\tau}{1-\gamma}.$

Now again proceeding exactly as in Section 6 with this extra $\tau$-term using
the step-size condition ($c_{k}=\gamma^{2k+1}$), we end up with

$\displaystyle\|V^{\star}-V^{k+1}\|_{\infty}$
$\displaystyle\leq\gamma\|V^{\star}-V^{k}\|_{\infty}+\gamma^{2k+1}+\frac{4\gamma\tau}{1-\gamma}.$

Unravelling this recursion yields

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}$
$\displaystyle\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+\sum_{i=1}^{k}\gamma^{-i}\gamma^{2(i-1)+1}\Big{)}+\frac{4\gamma\tau}{1-\gamma}\sum_{i=0}^{k-1}\gamma^{i}$
$\displaystyle\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+\frac{1}{1-\gamma}\Big{)}+\frac{4\gamma\tau}{(1-\gamma)^{2}}.$

Now using the properties of the estimator (10) in Lemma G.1, we have with
probability $1-\delta$ for all $0\leq k\leq K$,

$\displaystyle\tau=\frac{2\gamma^{H}}{1-\gamma},$

giving

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}$
$\displaystyle\leq\gamma^{k}\Big{(}\|V^{\star}-V^{0}\|_{\infty}+\frac{1}{1-\gamma}\Big{)}+\frac{8\gamma^{H}}{(1-\gamma)^{3}}$
$\displaystyle\leq\frac{2}{1-\gamma}\gamma^{k}+\frac{8\gamma^{H}}{(1-\gamma)^{3}}.$

This establishes the first bound. Now

$\displaystyle
K>\frac{1}{1-\gamma}\text{log}\frac{4}{(1-\gamma)\varepsilon}\implies\frac{2}{1-\gamma}\gamma^{k}\leq\varepsilon/2,$
$\displaystyle
H\geq\frac{1}{1-\gamma}\text{log}\frac{16}{(1-\gamma)^{3}\varepsilon}\implies\frac{8\gamma^{H}}{(1-\gamma)^{3}}\leq\varepsilon/2$

giving

$\displaystyle\|V^{\star}-V^{k}\|_{\infty}\leq\varepsilon/2+\varepsilon/2=\varepsilon$

as required. In terms of M, we have

$\displaystyle M$
$\displaystyle\geq\frac{\gamma^{-2H}}{2}\text{log}\frac{2K|\mathcal{S}||\mathcal{A}|}{\delta}$
$\displaystyle\geq\frac{1}{2}\Big{(}\frac{16}{(1-\gamma)^{3}\varepsilon}\Big{)}^{2}\text{log}\frac{2K|\mathcal{S}||\mathcal{A}|}{\delta}$
$\displaystyle=\frac{16^{2}}{2(1-\gamma)^{6}\varepsilon^{2}}\text{log}\frac{2K|\mathcal{S}||\mathcal{A}|}{\delta}$

and the corresponding number of calls to the sampling model, i.e. the sample
complexity is (what we have shown above is actually a lower bound but can
choose $K,H,M$ so that it is of the following order),

$\displaystyle|\mathcal{S}|\cdot|\mathcal{A}|\cdot K\cdot H\cdot M$
$\displaystyle=\tilde{O}\Big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{8}\varepsilon^{2}}\Big{)},$

where the notation $\tilde{O}()$ hides poly-logarithmic factors. This
completes the proof. $\hfill\blacksquare$

##  Appendix H MDP examples

###  H.1 MDP on which distribution-mismatch coefficient scales with size of
state space

We construct an MDP on which

$\displaystyle\theta_{\rho}=\frac{1}{1-\gamma}\Big{\|}\frac{d^{\star}_{\rho}}{\rho}\Big{\|}_{\infty},$

scales with $|\mathcal{S}|$, and hence so does the iteration complexity of the
bound of [38] for exact PMD.

Consider an MDP with state-space $\mathcal{S}=\\{s_{1},s_{2},...,s_{n}\\}$ of
size n and arbitrary action space $\mathcal{A}$. $s_{1}$ is an absorbing state
giving out rewards of 1 at each time-step, regardless of the action taken, i.e

$\displaystyle p(s_{1}|s_{1},a)=1,\quad r(s_{1},a)=1\quad\forall
a\in\mathcal{A}.$

All others states have an action, say $a_{1}$, that gives out a reward of 1
and with probability $1-\delta$ brings the agent to state $s_{1}$ for some
$\delta>0$ and spreads the remaining $\delta$ probability arbitrarily amongst
the other states. The other actions have arbitrary rewards strictly less than
1 associated to them, and arbitrary transition probabilities that place 0 mass
on state $s_{1}$, i.e

$\displaystyle p(s_{1}|s,a_{1})=1-\delta,\quad r(s,a_{1})=1\quad\forall s\neq
s_{1},$ $\displaystyle p(s_{1}|s,a)=0,\quad r(s,a)<1\quad\forall s\neq
s_{1},\forall a\neq a_{1}.$

Denote $r_{\max}=\max_{s\neq s_{1},a\neq a_{1}}r(s,a)<1$. The following
condition ensures that $a_{1}$ is the optimal action in all states,

$\displaystyle\delta\leq\frac{1-\gamma}{\gamma}(1-r_{\max})$

so that $\pi^{\star}(s)=a_{1}$ for all states $s$. To see this, consider
$s_{i}\neq s_{1}$, $a_{m}\neq a_{1}$ and an arbitrary policy $\pi$,

$\displaystyle Q^{\pi}(s_{i},a_{1})$
$\displaystyle=1+\gamma\Big{(}\frac{1-\delta}{1-\gamma}+\sum_{j=2}^{n}p(s_{j}|s_{i},a_{1})V^{\pi}(s_{j})\Big{)}$
$\displaystyle\geq 1+\gamma\frac{1-\delta}{1-\gamma}$ $\displaystyle
Q^{\pi}(s_{i},a_{m})$
$\displaystyle=r(s_{i},a_{m})+\gamma\sum_{j=2}^{n}p(s_{j}|s_{i},a_{1})V^{\pi}(s_{j})$
$\displaystyle\leq r_{\max}+\gamma\frac{1}{1-\gamma}$

and solving

$\displaystyle r_{\max}+\gamma\frac{1}{1-\gamma}\leq
1+\gamma\frac{1-\delta}{1-\gamma}$

will yield the condition above.

Then for $t\geq 1$ (abusing notation, $s_{t}$ denotes the state at time t),

$\displaystyle\mathbb{P}^{\pi^{\star}}(s_{t}=s_{1}|s_{0}=s)$
$\displaystyle=\sum_{s^{\prime}}\mathbb{P}^{\pi^{\star}}(s_{t}=s_{1},s_{t-1}=s^{\prime}|s_{0}=s)$
$\displaystyle=\sum_{s^{\prime}}p(s_{1}|s^{\prime},a_{1})\mathbb{P}^{\pi^{\star}}(s_{t-1}=s^{\prime}|s_{0}=s)$
$\displaystyle\geq\sum_{s^{\prime}}(1-\delta)\mathbb{P}^{\pi^{\star}}(s_{t-1}=s^{\prime}|s_{0}=s)$
$\displaystyle=1-\delta$

and

$\displaystyle d^{\star}_{\rho}(s_{1})$
$\displaystyle=(1-\gamma)\sum_{s}\rho(s)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}^{\pi^{\star}}(s_{t}=s_{1}|s_{0}=s)$
$\displaystyle\geq(1-\gamma)\sum_{s}\rho(s)\sum_{t=1}^{\infty}\gamma^{t}(1-\delta)$
$\displaystyle\geq(1-\gamma)\sum_{s}\rho(s)\frac{\gamma}{1-\gamma}(1-\delta)$
$\displaystyle=\gamma(1-\delta).$

Now

$\displaystyle\Big{\|}\frac{d^{\star}_{\rho}}{\rho}\Big{\|}_{\infty}\geq\frac{d^{\star}_{\rho}(s_{1})}{\rho(s_{1})}\geq\frac{\gamma(1-\delta)}{\rho(s_{1})}$

and depending on what $\rho$ you consider, $\theta_{\rho}$ can be arbitrarily
large. In particular, the natural choice of the uniform starting-state
distribution $\rho(s)=1/n$ leads to

$\displaystyle\theta_{\rho}\geq n\frac{\gamma(1-\delta)}{(1-\gamma)}$

which gives an iteration complexity under the result of [38] for an
$\varepsilon$-optimal policy that is

$\displaystyle
n\frac{\gamma(1-\delta)}{(1-\gamma)}\text{log}\frac{2}{(1-\gamma)\varepsilon}.$

Recall that $n=|\mathcal{S}|$, so this iteration complexity scales linearly
with the size of the state space.

###  H.2 Family of MDPs on which sub-optimality gaps can be made arbitrarily
small

We present how to construct a family of MDPs on which $\Delta^{k}(s)$ defined
in Section 4 can be made arbitrarily small.

Consider an arbitrary MDP $\mathcal{M}$ with state space $\mathcal{S}$ and
action space $\mathcal{A}$. For each state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, create a duplicate action $a^{\prime}$
s.t the transitions from that action in that state are the same as for the
original pair, i.e

$\displaystyle p(s^{\prime}|s,a)=p(s^{\prime}|s,a^{\prime})\quad\forall
s^{\prime}\in\mathcal{S}$

and the reward is shifted down by $\delta>0$ from the original reward, i.e

$\displaystyle r(s,a^{\prime})=r(s,a)-\delta.$

This results in a new MDP $\mathcal{M}^{\prime}$ with an augmented action
space $\mathcal{A}^{\prime}$, that is twice the size of the action space of
the original MDP $\mathcal{M}$. In terms of action-value of an arbitrary
policy $\pi$, this results in

$\displaystyle
Q^{\pi}_{\mathcal{M}^{\prime}}(s,a)-Q^{\pi}_{\mathcal{M}^{\prime}}(s,a^{\prime})=\delta,$

where the notation $Q^{\pi}_{\mathcal{M}^{\prime}}$ refers to action-values in
the MDP $\mathcal{M}^{\prime}$. In terms of sub-optimality gaps, this gives

$\displaystyle\Delta^{\pi}(s)\leq\delta.$

Choosing $\delta$ small enough, we can make the step-size of [22] arbitrarily
large, at least in early iterations. The step-size condition (5) of Theorem
4.1 will be less affected by this issue as it does not depend directly on
$\Delta^{k}(s)$, and not at all in the first iteration. Beyond its generality
to PMD, this illustrates the benefit of our result restricted to NPG over the
result of [22].