Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes
Authors: Emmeran Johnson
Ciara Pike-Burke
Patrick Rebeschini
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning Theory
Policy Mirror Descent
Policy Gradient
TL;DR: Our work establishes the linear $\gamma$ convergence rate for exact Policy Mirror Descent in tabular Markov Decision Processes and shows that this rate is optimal.

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, unregularised PMD algorithmically regularises the policy improvement step of PI without regularising the objective function. 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 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.

Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes
Emmeran Johnson Department of Mathematics
Ciara Pike-Burke Department of Mathematics
Imperial College London
Imperial College London
emmeran. wwt.sooonnnnnnpeeriaaaa ac. uk
pike-bbuke@inperr ac uk
Patrick Rebeschini
Department of Statisties University of Oxford
ox ac
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 y of a Markov Decision Process. In this work, bridge the gap between PI and PMD with exact policy evaluation and show that the dimension-free "rrate of P 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 7-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 the first 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 direct analysis 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.
Introduction
The problem of finding 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) 22 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
of the MDP 9 Recently, increased interest has been devoted the study of sereditgr (PG)
approaches based on optimising a parameterised policy with respect to an objective [36] 23 20).
Given their popularity, it is of interest 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 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 Linear convergence of PMD was established by (88, though their rate depends on an instance-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

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-independer 7-rate is achievable, although their results do not cover general PMD. In MDPs where the objective regularised, the y-rate has been established for PMD 13 24 The classical approaches (PI and VI) achieve the 7-rate without regularisation, revealing that regularisation is, in general, not necessary for algorithms to reach the 7-rate. This motivates the following questions:
Can the classical linear "y-rate be matched by unregularised policy-gradient algorithms? And what is the best rate that unregularised -raddint methods can achieve
For PMD, our work answers the first question positively and answers the second by establishing that the "--ate is in fact the best rate achievable for PMD as well as for 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 a general framework that encompasses 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
We recover the 7-rate for the general family of PMD algorithms with exact policy eval- uations under an adaptive size (see the third bullet point below). In particular, Theorem 4.1 establishes the following bound in loo -norm for the value y** of the policy x* after k iterations of PMD compared to the value V= of an optimal policy.. x',
2
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 inndeeddonnnddeeedeent 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 matching non-asymptotic lower-bound in Theorem 4.2, establishing the y-rate as the optimal rate for PMD methods in early iterations. Our results show that particular choice of learning rate allows PMD to reach this lower- bound exactly. Note that an asymptotic lower-bound not possible due to the exact convergence of PI in finite iterations (see Section 4.1 for discussion of the significance of this asympooii nower-bound)
The y-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 7-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 [9]. 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 iestence-indeeendent sample complexity of Ó(IS) |||[] -) under a generative model, where the notation Ö() hides poly-logarithmic factors, is the state space of the MDP, AA is the action space and 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-dependen 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 functions (see Section 5). paving the way for further improvements in instance-indeepndent 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-valuee of policies, and the simplicity of the analysis. The sample complexity result in the inexact setting illustrates how our analysis can be casily extended to

---

Table 1: Comparison of contributions with prior work that study PMD. 22 focus on NPG, an instance of PMD for specific mirror map (see Section 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 "-rate holds the linear convergence with the ry-rate, not only linear convergence. The fo- -bound is satisfied if it holds for || V" ]|ac.
Dimension independence satisfied when there is no instance for which the hound can scale with the size of the state or action space. We compare these works in more detail in Section 4
Linear 7 -ate
General
t0 Bound
Dimension Independent
Matching Lower-Bound
Step-Size Necessity
Mirror Map
X
This work
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.
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 333 and NPG specifically [3] though these have since been improved to linear convergence results as discussed below. Note that the work of [ 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 con- vergence has been established for NPG with entropy regularisation [13], PMD with strongly-com -onveex regularisers [2 and PMD with convex non-smooth regularisers 41) The rates of convergence
either exactly or can be made arbitrarily close to y 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 [2) 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 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 consists of bounding the difference in value between iterates of both methods. [1I also establish linear convergence for number of algorithms including PMD, although it is in the idcalised setting of choosing the step size at each iteration that leads to the largest increase in value. This step-size choice will make PMD least good as PI since arbitrarily large step-sizes PMD with an infinite step-size converges to a PI update. Since PI converges linearly, so will PMD. This does establish linear convergence of PMD for step-sizes with closed-form expression. However, linear convergence for unregularised general PMD was recently established by 38 under 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 [2] for 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
focus on this work. Their analysis relies on link between NPG and PI and
be chosen and
presented in Table [ and discussed in more detail in Section 4 In terms of optimality, 22 provide lower-boun for constant step-size NPG, though it only applies to MDPs with 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 O). We provide 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.
3

---

2.2 Sample complexity of inexact policy mirror descent
Sample complexity in the inexact policy evaluation setting refers the number of samples needed to guarantee an e-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-prou probabbbbbllltty 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 ②
SI
by 66 This lower-bound can be reached by model- basee approches
(1-7)
2 26 and model-free approaches 34 37
The sample-complexity for PG methods has been recently studied in [3). Under a generative model, some works have considered PMD or NPG under various types of regularisation [13] 24 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 e-dependence of (E P). [25 show that a variant of Pl, special case of PMD, achieves the optimal e-dependence of O(e More recently,
[38] show that the general family of PMD methods match the O(e-2) sample complexity with a e and 1 ? 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 those settings.
factor of (1 7)-² -8. Our result for the inexact setting shares the same dependence
3 Preliminaries
A Markov Decision Process (MDP) is a discrete- time stochastic process, comprised of a set of states S, a set of actions A. discount factor 7 [0, 1) and for each state-action pair (s, a) next-state transition function p(-|s, a) E ASS) and a (assumed here deterministic) reward function a(s,a) E J0, 1). A(X) denotes the probability simplex over set X. We consider both S and A to be finite, which is known as the tabular setting. In a state 8, an agent chooses an action o, which gives them reward r(s, a) and transitions them to a new state according to the transition function p(- (s, a). Once they are in a new state, the process continues. The actions chosen by an agent are formalised through policies. A policy π. : S + A(A) is mapping from a state to a distribution over actions. We will often write it as element in IT (AA)(S). In each state E S, an agent following policy chooses an action E A according to π; = x-1ss) E A(A).
In this work, the goal is to learn how to behave in a -ddiscounted infinite-horizon MDP. We measure the performance of policy with respect to the value function V S + R.
V (s) E 2'r(SE, (.),, =s]
Σ
where Sr, 4. are the state and action in time-step and the expectation is with respect to both the randomness in the transitions and the choice of actions under policy т. This a notion of long-term reward that describes the discounted rewards accumulated over future time-steps when following policy x and starting in state 8. For distribution over starting states p E ASS), we write (T(()) Eees p(s)V*(s for the expected value when starting in state distributed according to p. is also useful to work with the state-action value Q= : :S x A + lR:
(s( = Σ
r'r(st, a:) 80 s, a0 - a)
t=0
which is similar to V*, with the additional constraint of taking action a in the first time-step. We will often write V E RiSi (resp. Q" E R () (1 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 E R| for the vector of action-values in state The following expressions, which relate Q" and V in terms of each other and when combined give the Bellman equations (9, follow from their definitions above,
V (s)) (Q), TT), Q² = a) + + Σ p(s' p(sl(s,a)) (s))
S'ES

---

We now define the discounted visitation-distriutiio for starting state s' and policy x,
0c (1 >'P ( t
s|80 5'),
(I)
which plays an important part in the study of PG methods. Note that IP s|80 = 8') is the probability of being in state s at time when starting in state and following policy и. We also write (5(ss = Eves p(s (s).
One of the main aims of reinforcement learning is to find a policy ι that maximises V*, It is known that there exists deterministic policy that simultaneously maximises V and Q" for all states and actions (9]. We call such policy an optimal policy and denote by x². We are interested in finding an s-optimal policy, i.e policy π such that ||V* V* <.
3.1 Exact policy mirror descent
We are interested in PG methods that are based on optimising a parameterised policy we with respect use the direct parameterisation of
to 5*8 (p) for some p E (SS). In the tabular setting, policy Te. which associates a parameter to each state-action pair, ie. we have my (a(s) = 8g.a. We will drop the subscript / 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
① V
(p)
1 1-7 d (s)
@t(als)
Mirror Descent (MD, (8) carries out gradient descent in a geometry that is non- non-Euclidean. Using -V -V* (p) as the minimising objective, the proximal perspective of MD gives an update of the form
n *+1
argmin pen'
7k (VV* (p).p) + (a(p.=)))
where h dom h > R is the mirror map (with II c dom and Dd is the Bregman divergence generated by h. We require h to be of Legendre type [0), i.e strictly convex and essentially smooth (differentiable and || Vh(x))) )ll -> oo for any sequence x& converging to a point on the boundary of dom h) on the relative interior (rint) of dom h. The Bregman Divergence is defined as
Dr (TT, x') = ((T)) - h((=)=--= - (Vh(('), --'')->>)
n²)
for n, E dom h.
As the objective (p) is non-convex in general 3 usual techniques from convex theory 12 are not applicable.
The presence of the visitation-distribttioo term (s) in the gradient of the objective in 2 can slow down learning because it can lead vanishingly small gradients when states are infrequently visited under the current policy π 3 To circumvent this issue, Policy Mirror Descent (PMD) 24 33 38
applies a variant of update B with a weighted Bregman divergence DPMD that matches the visitation
distribution factors of the gradient DPMD (p) =, d5, (s) (P., T where the mirror map h is
now defined on a subset of IRI The resulting update has for all states a factor of d (s) in both terms. The minimisation can then be applied for each state individually to get the PMD update
k+ argmin
ma .p) xp)))
for all states We will often add superscript A to any quantity that is associated to * For example, V*((s y=* (s). Similarly for x* and the superscript *. Exact PMD iteratively applies update (4) for some sequence of step-sizes 7 > O and initial policy T E rint II. We call this algorithm exact because we assume access the true state-action values Q*
The update 4 of PMD considered in this work uses the true action-value Q". 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 a different algorithm that converges to a policy that is optimal in the regularised MDP but not in the original unregularised MDP.
PMD is general family that covers many algorithms, specified by the choice of mirror map These will inherit the guarantees of PMD, which motivates the study of the convergence guarantees of
5

---

PMD beyond specific instances. Taking h to be the negative entropy yields NPG, whose theoretical properties have attracted a lot of interest B [3 22). With null Bregman Divergence, PMD recovers PI. Pl is generated by constant mirror map, which is not of Legendre type but the analysis still applies so all results on PMD remain valid for PI. fact, PMD can be viewed as a form of regularised PI since the update ( converges to a Pl update 7/s - Do, 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 corresponding mirror map generating unique Bregman Divergence 77. highlighting the generality PMD.
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 state E S and an integer k 2 O. Let A = {a E A Q* (s.a) e (s,,')) denote the set of optimal actions in state under policy x² Denote by IT the set of greedy policies w.r.t Q in state i. ll { e A(A) Ene p(a) 1 We are now ready to state our main result in the setting of exact PMD, which is proved in Section
Theorem 4.1. Let {ck kezzo be a sequence of positive reals. Consider applying iterative updates of with TO E rint II and step-sizes satisfying for all le 2 O,
The 2
max #E$
min #
Da( (Tg)
(5)
Ck
ElI+
Then we have for all 2 O.
- - 1o I I (IV+ - + Σx
(6)
The sequence {c* kez2o plays an important role in both the siep constraint 5 and the bound c In particular, different choices will lead different guarantees. We focus on G; = 2(++)) cg for some > O, giving a size with a geometrically increasing component. The resulting bound is
I - 1o S (IV* V0
-10 +
co
which converges linearly with the y-rate, and matches the bounds of and VI as co goes to O. PMD cannot do better as will show in Theorem 4.2 We discuss other choices of (ck) 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
Lincar convergence of unregularised PMD was first established by [38 under geometrically increasing step-size 7 T//"". We discuss this step-size further and show the necessity of adaptivity to achieve the y-rate in Section 4.2 Their rate of convergence is 1 0, where 9, is an instance-dependent term defined as follows
Comparison to 38)
0, 0
where d is the visitation distribution defined in I under optimal policy and p is the starting-state distribution to which the bound applies, i.c the bound on V (p(p) V*)).. This Op is at best y when we use p to be the stationary distribution of the optimal policy. However, in this case, the guarantee only applies states on the support of this stationary distribution and provides no guarantees for other states. In general, it is unclear how Op may scale in specific MDP. In particular, it is possible to construct an MDP where 6, scales linearly with the size of the state space |S] (Appendix H.I). Though this MDP is somewhat trivial, it nonetheless illustrates how 8, 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 p in the denominator of the mismatch coefficient in 0, In contrast, we obtain the optimal 7-rate of convergence and our result holds fac - norm over all states so avoids having to deal with starting-state distribution p altogether.

---

This distribution mismatch coefficient commonly appears in convergence bounds in the literature 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 removable for the general family of PMD algorithms to obtain dimension-fre linear convergence. The techniques we use may be of interest for removing this coefficient in other settings.
19
I0
33
Comparison to [22]: The 7-rate was established by [22 for NPG, specific instance of PMD for which the Bregman Divergence is the KL-divergence. The bound shown in their work is sim- ilar to the one implied by our result with G; = 22(1++) cn. Defining (*) = max (s, a) max et Ab Q (s, a). the minimal sub-optimality gap in state s under π², then the step-size correspond- ing to their bound with the KL as Bregman Divergence is
Th Z max 2, a +E LL + log| A| + D(T
where L = Lkk for some constant L. > O. This highlights the connection with our step-size condition (5)- In particular, they both have adaptive component that depends linearly 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 (s(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 (s(s) arbitrarily small and the step-size of [2 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-fore form update of NPG to bound the difference in value with an update of PI. Our analysis applies to PMD for 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 55 for the step-size can be simplified. The minimum over #5+1 E [i*+1 can be removed by taking any # 1i 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. A will contain a single action and there will just be one policy in lī As for the maximum over E 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 8, denoted ma (s) would just have to satisfy (choosing any T E h
- Dm ( CF
(s)(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 A ((A) (as for the negative entropy) but then all iterates will belong to the relative interior of ((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 7-rate. The following result shows that this rate is in fact optimal in a worst-case sense. The proof can be found in Appendix H
Theorem 4.2. Fix n >> O. There exists a class of MDPs with |S| = 2n + 1 and a policy TO rint II such that running iterative updates of (4 for any positive step-size regime, we have for l < n.
I - V 2 5 > D01'
A key feature of this result is that the bound holds for & < n. For a fixed iteration budget, Theorem 4.2 implies that there exists an MDP which PMD will not do better than the linear 7-rate for any step-size. The 7-rate for PMD that we prove in Theorem 4.1 is optimal in this sense.
Lower-bound beyond k < n? For a fixed space size |S| = 2n + 1, it is not known what lower-bound holds when 1: 2 n. However, PT is an instance of PMD (see Section 3.1 and thus a lower bound that scales with n for all k > 0 cannot hold since PI converges exactly in finite-iterations
7

---

(in fact with number of iterations that scales linearly with |S] [T Theorem 3)). However, an asymptotic bower-bound for PMD under arbitrary step-size will not hold even we exclude PI from the class of considered algorithms. As the step-size tends to infinity, any PMD update recovers a Pl update. This implies that general PMD can be arbitrarily close to Pl'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 [S] 31 Theorem 3]. the number of iterations guaranteed by Theorem 4.2 has the same dependence on [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 7 new. We expect this result may have been known for the special case of Pl, though we could not find proof of it in the literature. The works that establish lower bound for Pl do so the setting of exact convergence to the optimal policy (18), not e-accurate convergence, and for undiscounted MDPs [T6.
establishes that the 7-rate is optimal in the first |S|/2 iterations. This non-asymptotic optimality is justified by the discussion above, which highlights that 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.
Rate-Optimality Theorem 4.2
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- 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 1.1 that PMD under an adaptive step-size achieves a linear 7-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 y-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 > and x > 0.2. There exists an MDP with state state-space of size |S| = 2n + 1 and a policy x² E rint II such that running iterative updates of NPG (PMD with h as the negative entropy) that satisfy V - Vl I
**[[ V + 1=2) requires
mh. 2 KL T )/2
#k+t fi++1
(8)
for i L,..., n.t. Kn < kg < ... < kn where {s. 3n} are distinct states of the considered MDP.
This theorem states that there are at least n distinct iterations with 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 linear y-rate. This is precisely the notion of adaptivity that appears in the step-size condition of Theorem 4. and [22]. Theorem 4.3 shows we cannot improve on this in general and provides justification for using 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 [
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 '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.
8

---

Sample complexity of inexact policy mirror descent under generative model
In the previous sections, we have assumed access the state-action values Q earry out the PMD) update. In Inexact PMD (IPMD), we replace Q with an estimate 0% giving the update
+++ argmin 7Tx (2. p) + Dn(p, }-
(9)
Similarly to the exact case, IPMD iteratively applies update (9) for some sequence of 7 > 0 and initial policy x² E rint 11, this time only assuming access to an inexact estimator of Q*
We consider the setting of a generative model [21] which is a sampling model where we can draw samples from the transition probabilities p(-ls, 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 Mj trajectories of length or horizon H, i.e samples of the form ((s) (0)) (s)) a(") ).... ($ 1
( - i=1, i where
(t)) (8, a). Using these dz is drawn from T (-lss") ). $2+1 is drawn from p(-|s} (6) and (s0 ,0n
samples, we can define truncated Monte-Carlo estimate of the values as follows,
M₁
H-1
(*saa))= = Mr > (ssss,)) a), where (i)(s,
Σ 1=
r'r(s
(10)
We use these @* a) to replace Q* a) in the PMD update step. accuracy of this estimator which is restated in Appendix extend Theorem 4.1 I to the inexact setting. The following theorem establishes sample complexity result, which is the sufficient number of calls to the generative model to obtain an e-optimal policy. For simplicity, we focus on the step-size following from the choice c; = -(((+))
38 present a bound on the
Following the same ideas as [38], we can
Theorem 5.1. Consider applying iterative updates of ( using the Q-extimator in 70 given access to generative model with T rint II and step-sizes satisfying for all k: 2 0 (with the definitions of A and l1k++1 suitably adjusted with O5 instead of Q2:).
{
D m3)
UH 2 max SES
min +
26++1
Fix E > 0. For any 8 E (0, 1), suppose the following are satisfied for all k: 2 0,
1
16
7 2-2
2K |||A
K 1 log (1 7) H 1 1-9 log (1 71-
and M₁ M 2 log
Then with probability least 1 - 8, 11 - -yv--vllo nh (IIV- v + 1
(-7337" 7
8
Choosing K, H and M to be tight to their lower-bounds, the corresponding sample complexity is where the notation Ö() hides poly-logarithmie factors.
ò (
The proof can be found Appendix G.1 The sample complexity established by 38 (Theorem 16)
under generative model and the same Q-estimator is ò SSIA >>
d 3
In their work, 38 stresses the interest in reducing the dependence on both 1/(1 7) and the distribution mismatch coefficient in order to scale the PMD guarantees to more relevant settings such as function approximation. Theorem p..]pmaalll resolves this matter by removing the dependence on the distribution mismatch coefficient, which may scale with the size the state space (Appendix H.I. This makes the result dimension-optimall which is crucial when scaling the results to large or infinite state or action spaces. The dependence on 1/(1 - 7) remains distant from the 1/(1 - 7)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
key component establishing the 7-rate avoiding the performance difference lemma that we state in Appendix B In prior works, the quantity

---

that we are looking to bound V*(p) - (p) arises through the performance difference lemma. In particular, [38] use the lemma on B. 1:Q ; "3 - )]] which introduces a distribution mismatch coefficient in order to get a recursion. On the other hand, we extract the value sub-optimalities (*()) (*()) and ||V* |lo directly from (Q+: = 1) in (2). This leads 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 7-rate.
Proof of Theorem 4.1: Fix & E and 2 O. From Lemma A.2 we have that (Q a < (Q%+1 n - = V=+ (s). This decouples the dependencies on " and m below and is one of the ingredients that allows to bypass the performance difference lemma. Using this,
(Q - T 2 (2% m ( (s) = (Q) Q;, m;) + (Q)) - (s)
2 -1 1+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 the next time-step, which is discounted by a factor of y. Formally, for any acte-nction pair (s,a) E E x A.
(s)),)) Q" a) = Σ (V) (v())-(())))))))
Σ p( - - >|IV* - Vb
which is the same phenomenon that is responsible for the contraction of the Bellman operator. This
gives ||Q; 11 S >1|V* -V Plugging into Equation (1).
(*(s) ()+ (s) >/|V* 10
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 m E m++1
(s) >|VV* 1+ S (Q T T 1
(12)
(Q xk+1 m
(13)
where we use that +1+1
11 is greedy with respect Q We then apply Lemma A.l or 16 to
(2t T x D( x²) D(# m m D( m
D mm))
7
Combining with 13 and noting that this holds for any #
E f we have
1
V*(s) - (s) > - Vo
D( m+) S cs.
7/4
from the size condition in the statement of the theorem. Rearranging and recalling that and were arbitrary, we can choose s where V*((s= v*+1(s) reaches its maximum value. We get
||V - | < >/IV* - 1o + Cks
and unravelling this recursion completes the proof.
7 Conclusion
In this paper, we have shown that the general family of exact policy mirror descent algorithms in tabular MDPs under adaptive step-size achieve the same dimension-free linear 7-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 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-valle of a policy. We provide 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 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.
10

---

Acknowledgments and Disclosure of Funding
EJ funded by EPSRC through the Modern Statistics and Statistical Machine Learning (StatMI.) CDT (grant no. EP/S023151/I).
We would like to thank the reviewers and meta-reviewers for their time and feedback, which led to better version of this paper.
References
[1] 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.
[2] 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.
[3] 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): 2021.
[4] Carlo Alfano and Patrick Rebeschini. Linear convergence for natural policy gradient with log-linear policy parametrization. 2022. Preprint, arXiv: 15382.
[5] 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,
[6] 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-334 3495,349.445 2013.
[7] Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. Journal of Machine Learning Research, 6(58):1705-177)) 2005.
[8] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[9] Richard Bellman. Dynamic Programming. Dover Publications, 1957.
[10] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. 2019. Preprint, arXiv: 1906.01786.
[11) 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 2396-2394. PMLR, 2021.
[12] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4), 2015.
[13] 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.
[14] Gong Chen and Marc Teboulle. Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions. SIAM Journal Optimization, 3(3):538-543, 1993.
[15] Zaiwei Chen and Siva Theja Maguluri. Sample complexity of policy-based methods under off-policy sampling and linear function approximation. In Proceedings The 25th International Conference on Artificial Intelligence and Statisties, volume 151 of Proceedings of Machine Learning Research, pages 11195-11214, PMLR, 2022.
11

---

[16] John Fearlley Exponential lower bounds for policy iteration. In Automata, Languages and Programminng pages 551-562, 2010.
[17] Matthieu Geist, Brumo Scherrer, and Olivier Pietquin. theory of regularized Markov decision processes. In Proceedings the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2160-2160 PMLR, 2019.
[18] Romain Hollanders, Jean-Charles Delvenne, and Raphaël M. Jungers. The complexity of policy iteration is exponential for discounted markov decision processes. In 5 IEEE Conference on Decision and Control (CDC), pages 5997-6003 2012.
[19] Sham Kakade and John Langford. Approximately Optimal Approximate Reinforcement Learn- ing. In Proceedings of the 19th International Conference on Machine Learning, volume 2, pages 267-274, 2002.
[20] Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, volume 14, 2001.
[21] Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in Neural Information Processing Systems, volume 11, 1998.
[22] 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.
[23] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, volume 12, 1999.
[24] Guanghui Lan. Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes. Mathematical Programming, 2021.
[25] 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.
[26] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. In Advances Neural Information Processing Systems, volume 33, pages
2020.
[27] Yan Li, Guanghui Lan, and Tuo Zhao. Homotopic policy mirror descent: Policy convergence, implicit regularization, and improved sample complexity. Mathematical Programming, 2023.
[28] 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.
[29] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1994.
[30] R. Tyrrell Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970.
[31] Bruno Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. In Advances in Neural Information Processing Systems, volume 26, 2013.
[32] Bruno Scherrer. Approximate policy iteration schemes: A comparison. In Proceedings of the 11 International Conference on Machine Learning. volume 32 of Proceedings of Machine Learning Research, pages 1314-1322. PMLR, 2014.
[33] 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-567)
2020.
[34] 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. Advances in Neural Information Processing Systems, volume 31, 2018.
12

---

[35] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, second edition, 2018.
[36] Richard 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.
[37] M. J. Wainwright. Variance-reduced Q-learning is minimax optimal. Technical report, UC Berkeley, 2019. Preprint,
[38] Lin Xiao. On the convergence rates policy gradient methods. Journal of Machine Learning Research, 23(282):1-36, 2022.
[39] Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3332-3380. PMLR, 2022.
[40] Rui Yuan, Simon Shaolei Du, Robert M. Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log- linelinear policies. In The Eleventh International Conference on Learning Representations, 2023.
[41] 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):0061-109) 2023.
13

---

A Properties of PMD
We present lemmas relevant 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 proof can be found, though we use a slightly modified version from 38 (Lemma 6).
Lemma A.1 (Three-Point Descent Lemma, Lemma in [38]) Suppose that C Th a closed convex set, Φ C + R is proper, closed convex function, Dr (---)) is the Bregman divergence generated by a function of Legendre type and rint domh C + For any x E rint domh,
x² = arggmin = + (x),
(14)
Then xt rint dom h n C and Vu E.C. C.
Φ(x+) + Da S ((u) + (a D2 xu,
(15)
The update ( of PMD is an instance of the proximal minimisation (4) with C ((A).
and (xx) W) (Q+ .²). Plugging these into (15). Lemma A.1 rel the decrease in the proximal
objective of n to any other policy, i.e. Vp E (AA).
-mk ( + + DA(T, ,, S -Tt(0% + ()( (p, (p, -
(16)
This equation is key to the analysis in Section 6 In particular, it allows prove the following lemma regarding the monotonic improvement in action-value of PMD iterates. This is an extension of Lemma in [38].
Lemma A.2. Consider the policies produced by the iterative updates of PMD in Then for any
k $20
Q (s. a) 2 (s,,a)
((s,a)
A.1 Proof of Lemma A.2
We first present Lemma from
38 from which Lemma 2.2
almost immediately follows.
Lemma A.3 (Descent Property of PMD, Lemma in 38 ) Consider the policies produced by the iterative updates of PMD in ( Then for any k 2 0
m k+1 - 2 0, Vs
vk+1(p) 2 (p), Ap E A(S).
Proof. From 38 Recall that the Three-Poine Descent Lemma states that Vp A(A),
-T) ( k+1) + (n ,,²)) < (0 p) Da Du(p, x. t++))
Using this with k
D (n Dn (T k+1 +イ S 7k ( k+1 x
and since the Bregman divergences are none-negative and 7)x > 0,
0 < (Q - k+1 - イ
and the result follows by application of the performance difference lemma (Appendix B
vk+1(p) (*(p)
1
E
ahts
(0 ++1
m+))
1 1-7
2 0.
Note that the performance difference lemma here because it gives simple concise proof, but we do not actually need to. To maintain our claim that we avoid the use of the performance difference lemma, get the same result without it. We sketch how to do this follows. From the first part of the lemma, we have
(Q., mlt1) 2 (Q). m (*),
14

---

in all states s. Now note that the left hand side above is
10 +
k+1 (als)
(a|s) (als) ( ((s. + E((
and can then apply (Q Tx 1 (5') at state 8s: (s) v π x+1
(als) r(s, a) + Σ p(
(als) ((),)) (als) + Σ p(s'ls, Σ -
and proceeding iteratively in the limit you get exactly (k+
Since Lemma A.3 holds for any p E ASS), it guarantees that the value in each state is non-decreasing for an update of PMD, i.e for all S, V (s) V*(s) 2.
Using this, we get
( (s.a) = Σ p(s'ls, [p(s'|s,a) (3tt),)) 2 0,
(s,
s'ES
which concludes the proof.
A.2 Extension of Lemma A.2 to inexact setting:
As in the exact case, we first present Lemma 12 from 33 which is the extension 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 Qh of Q Lemma A.4. Consider the policies produced by the iterative updates of IPMD in 9 For any k 2 0, if ll lo I T, then
@ n -x() 2 0, V
2r
(x+ V* (p)
Vp ASS).
Proof. From 38 The Three-Point Descent Lemma applied to the IPMD update ( gives Vp A(A),
-Th Qh T k+ + (T N+ .m)) < 71h (Q:..)) p) + Dn ) - =
Using this with p n
k+1 x+)) (n +t D2 (m ) S 7) Q2: n
and since the Bregman divergences are none-negan -eganiet and 17k: > O,
@ k+1 + n.
which proves the first inequality. Now we cannot use the above inequality directly with the perfor- mance difference lemma since Qu not the true action-value. Instead, we have
vk+1(p) V*(p)=
1
(
n k+1 -
1
1 - Qb mht1 m + (Qt, k+1 - -mt)
E
1
1
E
- 11Q 1611oo117 1+ 731111
-
snu -1
?
1
snn k-1
- 2T
1
2T
1 1-7
which concludes the proof.
15

---

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 ilerative updates of IPMD in ( For any 2 0,
if 11 - -Q² llo I T, then
2Ty
(s, (+,
(ss
Proof. As in the exact case, since Lemma all E S,
A.4 holds for any P A(S), it applies to each state, i. for
2r
(s+ (s) (*( 2 ---1- 1-7
Using this, we immediately have
(st) -(t,))= E pls'l1,, Ep66lle.o(vvttt -6))) 1-
v4())) -2Ty
e'ES
which concludes the proof.
B
Performance difference lemma
Lemma B.1 (Performance Difference Lemma). For any n, n' E II, we have
(T(()) VT (p)
By [00 TTs n'?
The performance difference lemma [9] 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.
C Guarantees of Theorem 4.1 for various step-size choices
We give here two more choices of {cr (c.2e for the step-size 5 of PMD and their corresponding guarantees from Theorem 4.1
G Co for some cu yields a step-size with a constant component. The resulting bound
is
|| 1 -* S ~ vo
co 1-7"
which converges linearly up to accuracy controlled by co-
=gS+le co for some initial > will yield step-size with a component that is
geometrically increasing as 38 though at slower rate than the one discussed in Section The resulting bound is
I - V* SD -IVV
Vo keo)
which converges linearly with the sought-for 7-rate, though in early iterations the k factor may dominate.
16

---

D Simulations
In this Section, 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 5 = (1 " /100,000 ? 0.99, (a = a (note that a1 is the optimal action in each state). In each of the plots, we compare the performance
[S] = 51 and |A| = We use
NPG using our step-size (5) from Theorem 7 and co and the step-size (88 ` '/0/7* (denoted by INC the discussion below) for fixed 1/ In each of the plots, the left plot -| V de against iterations and the right plot is Th against iterations.
(denoted Adaptive in the plots and by ADA in the discussion below) with
In all plots, the green curve represents the y-rate. In particular it is the curve of y = =
Discussion
With fixed initial step-size = for INC, the convergence of NPG with INC can be made arbitrarily slow in early iterations by choosing a (= x (a1 (s) closer (Figures 1-3). The convergence of NPG with ADA is unaffected by small values of a because it adapts to them.
These observations agree with the theoretical results established. Our adaptive step-size (5) achieves the "-rate (Theorem[4. 4.1) and this optimal for iterations k up until n = 25 (Theorem 4.2). The adaptivity in the step-size necessary to achieve the 7-rate in these early iterations (Theorem
iterations 200), INC has faster convergence than ADA. In these later iterations, acting greedily with respect to the action value of 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 super- linear convergence (as discussed in 38 beyond the optimal 7-rate valid up to finite iteration (see Section
In later iterations (Figure I: iterations R 100. Figure 2:
17

---

10a
10a
Adaptive (ADA)
du ruly"
10a2
Size
10a
10
10
Adaptive (ADA)
10-4
Ge Rafy" (NC)
100
200
300
400
500
1000
200
300
400
500
Figure I: a = 10-1, Green curve: y = 7
10a
10a
10
16a
-V1-
10a
10-1
10"1
10-2
10
Adaptive (ADA)
Adaptive (ADA)
Du noly" (NC)
Tu nut (INC)
100
200
300
400
500
100
200
300
400
500
Figure a 10 10-10 Green curve: y 7
10a1
102
10
Sizp-Szze
10t
10-7
Adaptive (ADA)
Adaptive (ADA)
4. ov/
109
100
200
300
400
500
100
200
300
400
500
Figure
10
50
Green curve: y 7.a
108
4 max/ADA, royr")
Nv - qull (INC)
10-2
Stap-Sio S.00
101
10-1
MaxIADA,
10-30
10a
0
100
200
300
400
500
100
200
300
400
500
Iterations
Figure 4: a 10-10 7 max(Adaptive, no/ means the step-size chosen as the largest between our "Adaptive" and the geometrically increasing of [38]. Green curve: y = y²
18

---

+71
+
+Tn
&
2
s'
+11
A2
+
a2
+ n
a1
@1
A1
+1
$o
$1
$2
S
+0
+0
+0
Figure 5: Example MDP used the proof Theorem
4.2
E Proof of Theorem 4.2
The state space is S {5a, 81, s1 si,..., Sn, } and the action space A = a2) There is chain of states of length n + with the states indexed from 0 to n. The left-most state (sp) is absorbing with reward +1. In the other states in the chain (s; for i 1.... n2,, the agent can take action aj and move left (to $;-1) with reward of O, or take action d2 and move to an additional absorbing state unique to the state is currentl in (s() with reward ri -a*11 + 8 (that the agent also receives in that state for all future time-steps). Summarising, we have for 1 < i S
Fix n > 0 and 8 E (0, -0,11-1))) ))" Consider the MDP shown in Figure 5
1(8;-118;,01) = r(8;,1)) =0,
p(8))s2,02) =1, 02); = = = - + 8,
p(s;}b%,a)=1 =1 r()(, = = = + Va e A.
The value of 8 carefully restricted so that the optimal action in all the states of the chain a1- 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 a2 then it has to learn that 0 the optimal action in the state directly to the left before
start switching from action d2 to aj 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 ² n² (agls) following claim from which the result will follow straightforwardly.
s.t - (a, (s)
for all states and some s.t 0 < < 8(1 7). We make the
Claim: Fix & < n. The policies produced by PMD satisfy (ar(ss): S a for k < <isn. n
We prove this claim by induction.
Base Case: We want to show that x (an (s;) S for > We do this by showing that Q" a1) S Q2 a2) for i > 1 so that the probability of n (a. (s,) cannot increase w.r.t a (a(lss))) which is
19

---

(this follows from (Q.. xk+ - -m 2 0 for all iterations of PMD). We have:
(81, = ->
=7 =7(aQ0 (8-1,, + (1
(1=
y f-1
M1-1
+
1 1-71
?) 7
1-7 + - + 8)
1 (0
1-9 ?
1+1
87(1 + -1))
1-7
1-7
(6) y
à
+
1-7
1-1
(8 az);
where we used S 6(1 - 7) in (a) and 7( + +-----1777 < for E [0, in (b). This concludes the base case.
Inductive Step: Now assume that the claim is true for k and we want to show that v² (a1 s;) S a
for >> k + 1. We do this in the same way as the base case by showing that (*;, 01) I (*1 02) for k ++++ so that the probability of x *++ (ails)) cannot increase w.r.t n (a](s;), which less than or equal to by the inductive hypothesis. We have:
Q" (s;, (s) >>>
+ + ((0)))/(((___))))))))0//// (0000))))))
(0)
S (00 (s--1, Q* (s--1,
- + r1-1
(001 - 7) g01
7 + 7 + 8)
1 y
7 81 + -p))
1-7
1-7
2 1-1
+
1-n 1-7
= Q* (s;, az),
where we used (a) that n² (aj (8-1) 4 a for i > 1 + 1, which true by the inductive hypothesis
since i 1 >>>>> k, in (b) that a S 6(1-7) 7) and in (c) that 7(1 + 7²) < 1 for 7 E [0, 1). This
concludes the proof of the claim.
Now using the claim
(*(+1))) = x (0 a1) + x² (0
At1
< 1- + Tk+1
1-7
xt1 xkt2 + 6
a 1-7
+ 1 1-
20

---

So
x+11
gh+² + 8
(*84+1)) (8k+1)) 2
0
1 1- 7
1 -
- y
2 xx (1 - 7)
a7*+1 8
1 1-y 7
1-9
a a+ 8
2 /
k+1
1 1-7
2gtt1 28
(17)
1-7¹
where we used that a S 6. Now note that
(81) = aQ"(s1,
+ (1 - a=)
+ (1 - a) 72 +8
1-7
1-7¹
80
72 + 8
(1(s)) - (s))
a
7
(1 a)
1 - 7
7
1-7 7
2 4
7
(1
a)
(1 a)
1- 7
7
a
7 72 - 6)
= 1 - 7
$ 1 - a
( -2)
7
1 a 11 (1-
7 -
= 71 a)
and by induction we show this is the case for all states (ahove is base case), the inductive step is as follows (assuming V* (s*(s - (sx)) S 5)
1 1-7 - -11-a) rt2 4
(*(*x+1) - (sx+1)
(sx)
1 1-7
(1 a) ghhll - -ght2 8
+ an -ss))) (sx))
1 1-7
< (1 a) + a22
and so
||V - 1 S7,
which combining with 17 gives,
28
('(4++1) - (*6+1)) 2 2**1ll= V0
1 1-9
28
1| - 1 2 - - -v
1 1-7
Choosing 6 = (1-1) 70 V - 10 < 4 - (which is in the valid range of 8) concludes the
proof since
T-y < 27
26
///l V 10 l0.
21

---

Proof of Theorem 4.3
Consider the same MDP as in the proof of Theorem 4.2 in Appendix (see Figure 5 for 7 > 0.2.
Denote
1- and note that VT 1-7 since 1
1+
1+ 1
Suppose you consider NPG updates with initial policy x (a)))s a. 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
T" (a Ea Th ()t
++ (a|s) (als)
We know from the proof of Theorem that for any step-size regime, for i > +
("i, a1) S (s; 02).
V-s) 5 (see Section F.1 below). The idea of the proof show that satisfying the bound given in the statement of the theorem will imply that a certain condition on the step-size.
Now, ||V--V*|
Fix state 8k and let ko be the first iteration where Q (sk, a1) Q (ske 02). By the above, must have k < kn + I, or ko (before iteration ko, ((sk,)) -) favors a2, so r (a1 (sx) has not increased compared to π (aills))) = a).
1. By the proof of Theorem E we also have n (a1 (sx) S
We want 7-contraction at every iteration, i.e. assume the following is satisfied:
8
(*(*k) - vhotl (8N) S s - 10 + +) S hot
(
1 1- + c).
Now, by direct computation,
7tt T
(*(ss) k a ho (ats(()))) (Vx-() V ko ( + x (a2l32)
1 1-
8
2 n
1-7
Putting this together with the above (this is an implication as this is about the necessity rather than sufficiency), must have:
8
n Ao (a2 (82
I-9 I 2
1- + c)
7 r (r 1-7 + c)
to (60t((22/82) S
6 = 3
(7 I-7)
we choose < (1 7) vi then < v and require
n ko ( S v.
22

---

To see this, start from B 5 v7, this is equivalent to
7 k1+ (7-
5
+
c)
1-7
S
V
(g
6
)
- cc)
1-7
S V>
since ko + 1 2 k
(7* 1
6
8
(7- 1 1-7 +c) S
v5(T
k
1
8
=
+ + () s V7(0**
1-9
5
c) 5
-
5
S
(v7 -7
1-7
V7 1 1-?
V7 1 1-7
} V7 7- + v7 2
since c
1-7
1+ /7 2
6
} (V7 7-- - v7 (1 -)))
S
1-7 7
2
8
(V7 7 V7 1
1-7
2 2
v/ 2 2
- 20 v 7)),
2
which is the condition for å we imposed initially.
To achieve the above condition hoo (a2ls2) S recallng that / (a2l52) 2 1 aa Tho has to satisfy
log((1 - a) vh)) + KL 86 xx
T)ko 2 Qko a1) - Qua (0k; a2)
To see this, again start from A/ (s2) S y this is equivalent to (use ku = m for simplicity of notation) using the closed-form update of NPG:
n:' (az(2182)) exp(mm (5 az)) z
VT(TT" (52)52) exp(mm Q'' a2)) + T"' (a1ls)) exp(1m (" (sk,
1 2 1+ TT' (a2l2s>) $2)
T- (a11s2)
exp(1mm (sk, a1) (sk, (2)))
1 1- / " (a2l52)
< exp(1/m
(sk: (Q"(st,a))) - Q (sk, (sk, az)))
V1 (a1(8))
v Th (a (22)
nm (Q (sk, - QT (sk, a2)) 2 log
v7
Tm (82)
1
v
1
mm 2 Qm a1) Qm (sk, 02)
log
x (ugll2))
+ log (1(()119)))
V7
1 - v7
+ KI(#mmt , mmm) ]
mm 2 QTT ai) Qi (S 22)
log
m=+1 ,m,) [log (1 (1-a)) a)(1 - vT) + K KL (x st
Bm 2 Qth (mx a1) (T)( az)
As we take - 0. the KL term will dominate. In particular, note < 7 so 1- a > 7 and
(1 - --a)(1 - -)(1- 7(1 v7)
23

---

and if we further impose the condition < <x²(1- - vF2 then
(1-a)(1- v1) va v (
and the step-size needs to satisfy the following condition:
Aok 2 (sx a1) - Q (Sk: Q2)
log( V (to((11)2)) KL mbp)
1
1
=
KL _mb2) + KL TT8
(sk, a1) Qko (sk: (2))
2
KL =T
(18)
2(Q (sk. a1)
Qua a2))
Distinct Iterations: Note that the iteration (*)())) where Q(:, 8k) starts becoming bigger at 01 that a2 is distinct for each Sg. Fix any 8& and Ro = (sk)) We have
01) < 2 (sk, 02)
Quo+ (sk, 02) Q ho (1)
S a (since Q' points towards in for all f S ko). Then applying exactly the same steps as in the proof of Theorem 4.2 we have
then x (a (a1lsk) (sx) S x
@uo+ (1)+1, < Q ($141,
meaning that (s( is disctinct to (8(++11).
Upper Bounding Q-value difference: We want upper-bound the Q-value difference appearing in the step-size condition above. We have,
rk gk +6 5
(sk, 02) 1 --7 1-9
7
(sk, Vo (sk-1) 5
-
So,
7/
g+1 +
(sk, - Qoo
S
1 -
1-7
8
x
1 1-?
Plugging this into the above bound (8), if the iterates NPG satisfy the bound with the y-rate in the statement of the theorem, the step-size must at least satisfy the following condition:
ns. 2 2
which concludes the proof.
F.1 Largest sub-optimality gap at iteration
In this section, we prove the claim that
8
I 1O = V - V S 1-
Proof:
First of all, V*(x)) - (s = n (a2ls))) = (1-a) a) 8 S 1-
For the
first part, we proceed by induction. We will use throughout that
n/
5
8
x
< vV (s1) =1 (1-
1 1-7 7
1-7)
24

---

This is true if (when LHS is the largest)
8 1-7
1 1-7 (1--a)(7
which holds when
a 5 7(1 7)
7(1 - 7) -
a < 1 1177
Base Case:
(*())) - = (s2)) an((())) - (1-))) -12
1-7
(s) - -10))) (s1)
<V'(s)) - (s))
Inductive Step: Assume true for k. Then,
- ((())) + a) / rx+1
(*(*++1)- -
1-7 ?
<s)(V*(s)) (*(s)) +(1 (s1) - (s1)
S (81) (s)))
which concludes the proof.
25

---

G Inexact policy mirror descent and the generative model
The following Lemma from 38
controls the accuracy of the estimator 2% specified in (10) of Section
S with respect to H and Mg:
Lemma G.I (Lemma 15 in 38 Consider using 10
estimate Q for all state-action pairs for K iterations of IPMD. Then for 8 E 1). for all k S K.
-2H
2K |
M& 2 2
log
8
Then with probability at least 1 - 8, we have for all k S K,
2- 11
I 1011ox 1 1-7
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 Section 6
Fix state E S and an integer k > 0. For now let's assume that our Q-estimates are r-accurate
(T > 0), i.e.
1 - 1 1x ST
for all k 2 0. With this assumption, we have from Lemma A.5 in Appendix A.1
27T
@++ a) 2 Q² (s,
(
1-
Now proceeding in similar way to Section 6
Q Tg. - (Q _ T k+1 (²: Q+ n..
2 (0 m.) - (Qth k+1) 10: 0² ll
|/000| ||
k+1 |||
2yT
2 (0. m.) (Q*+1 , k+1)
2T
1 1-7 7
47T
> (0 m.) - pk (s) 1-7
4yr
(0) Q m.) + (s)) vh+ (s) 1- ?
477
2 -1 11 0 + V*())- pk+1(s) (s)
1 -
4yt
2 -- - 1ا + (s)) vh+ (s) 1
Now again proceeding exactly in Section 6 with this extra 7-term using the step-size condition (ck = 2 ), we end up with
47T
I - 1l+ S --IV== - Vol
+ +220-1+ + 1 1-
Unravelling this recursion yields
Vo -1 Σ 7 2(16111)) + 4,5 1-1
IV v*1 1lo S ~* (11V* 1117~-99)
7
$ th |1V - 1ol00
I )
477
(1 - 7)
26

---

Now using the properties of the estimator (00 in Lemma G.1 l K,
we have with probability - 6 for all
2
1 --1 7
giving
1
8y11
|V - |
1o S 7*
- +
+
1
(1 7)3
2
87
/6
(1 1 71-
This establishes the first bound. Now
K >
1
log
b: S E
7
(1 11-79 --)
1 7
1
16
87
H 2
log
(1 7)3 S E/2
7
(1 -))3
giving
| - 1o 5
as required. In terms of M, we have
7
2H
2K|S||A
M 2
log
2
5
1
16
2K S|
log
2
(1
7
8
162
2K S|AAA
2(1 62 log
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 that is of the following order).
SS| |A] K M = 0 |S||A
(1 (1-7)
where the notation Ö() hides poly-logarithmic factors. This completes the proof.
27

---

H
MDP examples
H.1 MDP on which distributionnmmisaate coefficient scales with size of state space
We construct an MDP on which
0
scales with |S], and hence so does the iteration complexity of the bound of (38 for exact PMD.
Consider MDP with state-space S = {si. $2, 8n of size and arbitrary action space A. is an absorbing state giving out rewards of at each time-step, regardless of the action taken, i.e
p(s1|51,0) a)
r(s1, a) =1 Va E A.
All others states have an action, say d1, that gives out reward of and with probability - 8 brings the agent to state 5 for some other states. The other actions have arbitrary rewards strictly less than associated to them, and arbitrary transition probabilities that place mass on state 81, i.e
and spreads the remaining probability arbitrarily amongst the
p(si/s, a1) = -1-
-88, 8, ((s,a1) =1 Vs 4 # 81,
p(si/s,a) = 0, r(s,a)= 1 ss + s1, va + aj.
Denote Tmax maxx/s a(s,a) 1. The following condition ensures that aj the optimal action in all states,
8 5 1-7
(1 Tmax)
7
that n" 7s) ai for all states s. To this, consider 8; + 81. am # aj and an arbitrary policy n.
1
n Σ
= as)
((s)))))aa))))(s))
j=2
1-8
21+7 1-7
QT r(sis am) +
Σ
f=2
S Tmax + +7
1-7
and solving
Tiax + 7
<
will yield the condition above.
Then for t (abusing notation, s, denotes the state at time t),
pa (st $1 s1 5) Σ 1s (st 51, St-1 = = =s
Σ p(sils', 10',1s,,000 )P* (5 =s(1s0
(1 8) (s,-1 = s'(s0 8)
= 1-88
28

---

and
=
= (1 - Σ ((s)
'I==" (s: 81|/80 s)
1=0
2 (1 - 7) Σ (8) Σ 7 - 6)
(1 7) Σ (ss)
(1 8)
71 8).
Now
(5(5)) 711 p(81)
2 p(81)
and depending what p you consider, 0, can be arbitrarily large. In particular, the natural choice of
the uniform starting-stat state distribution p(s) = 1/n leads to
0, 2 n (1-6)
7-
which gives an iteration complexity under the result of (38) for an e-optimal policy that
7 8) log "
2
(1 7)
(1 (1-7)
Recall that n [S], so this iteration complexity scales linearly with the size 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 A (s) defined in Section 4 can be made arbitrarily small.
Consider an arbitrary MDP M with state space S and action space A. For each state-action pair (s, a) S A. create duplicate action a' s.t the transitions from that action in that state the same as for the original pair, i.
p(8 11 a) p(")s,,a' Vs' E
and the reward is shifted down by from the original reward, i.e
r(s a') = r(s, 6. -.
This results in new MDP M with an augmented action space A', that is twice the size of the action space of the original MDP M. In terms of action-value of arbitrary policy æ,, this results in
(s, (s,(s, 8,
where the notation Qh, refers to action-values in the MDP M' In terms of sub-optimality gaps, this gives
A (8) 8.
Choosing 8 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 does not depend directly on A (s)), and not at all in the first iteration. Beyond its generality to PMD, this illustrates the benefit of our result restricted NPG over the result of 22
29


Reviews:
[{"review_id": "xysWlRwTYZ", "reviewer": "Reviewer_wj3u", "summary": "The paper studies the convergence rate of Policy Mirror Descent. The authors prove a $\\gamma$-rate for exact PMD update and a matching lower bound for this class of algorithm. Then they prove a sample complexity bound of $O(\\epsilon^{-2}(1-\\gamma)^{-8})$.\n\n", "questions": "1) A lower bound on a class of algorithm and not on the problem seems strange. Could please the author elaborate on this point? Is this standard in RL literature?\n2) The terminology: Unregularized PMD is not explicitly explained in text. It would be helpful to clarity it explicitly.", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper analyses an interesting problem on the convergence rate for a general class of RL algorithms. The work is nicely structured and the theoretical results seems not trivial to obtain.", "weaknesses": "In the reviewer's opinion the paper does not convey clearly the contribution of the paper. More specifically it's hard to understand if the paper advances theoretically the field of RL or just the theoretical understanding of PMD.\n\nMinor:\nThe following sentence in the abstract: \"Motivated by the instability of policy iteration (PI) with inexact policy evaluation, unregularised PMD algorithmically regularises the policy improvement step of PI without regular5 ising the objective function\" sounds convoluted and maybe even grammatically incorrect. Please have a look", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer wj3u for their valuable comments and feedback. We have now performed numerical experiments to validate our theoretical findings (see “global” Author Rebuttal and attached pdf), which we will include in the final version.\n\n&nbsp;  \n\n### A.1 In the reviewer's opinion the paper does not convey clearly the contribution of the paper. More specifically it's hard to understand if the paper advances theoretically the field of RL or just the theoretical understanding of PMD.\n\nThe contributions of our work can be summarised as\n- **1. Optimal Rate:** We show that exact PMD achieves the linear $\\gamma$-rate (Theorem 4.1) and that this is optimal for any mirror map (we give a lower bound in Theorem 4.2).\n- **2. Step-Size Necessity:** We show that adaptivity in the step-size is necessary for the optimal $\\gamma$-rate (Theorem 4.3; in at least one instance of PMD). The instance is PMD with negative-entropy and prevents improvement on the step-size in Theorem 4.1 for general mirror map.\n- **3. Simple Analysis:** Our analysis (Section 6) avoids visitation distributions and the performance difference lemma, which is one of the most widely used proof techniques to analyse PMD-like algorithms (c.f. below).\n- **4. Sample Complexity:** We extend our results to inexact PMD (Theorem 5.1) giving the first result optimal with respect to dimension ($|\\mathcal{S}|, |\\mathcal{A}|$) for PMD under a generative model. In particular, we remove an instance dependent factor (that may depend on dimension) that appeared in prior work [7]. More generally, the analysis can easily be combined with any 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.\n\nThese contributions advance the theoretical understanding of PMD. Algorithms achieving the $\\gamma$-rate were already known (Policy Iteration / Value Iteration) but **it was not known for PMD** in general prior to our work. In particular, we characterise both **necessary** (Theorem 4.3) and **sufficient** (Theorem 4.1) conditions for PMD to achieve the $\\gamma$-rate. We also **improve the sample-complexity** of PMD under a generative model. These are advances in the theoretical understanding of PMD specifically.\n\nThe **novelty in our analysis advances the field of RL** as a whole. Our analysis avoids the use of the  performance difference lemma, an important theoretical tool central to the analysis of PMD in previous work [7, 9, 17]. The technique we use is not restricted to PMD and is **applicable to RL algorithms in general**.\n\nSee C.1 (in the response to TTxd)  for more discussion on the significance of the contributions.\n\n&nbsp;  \n\n### A.2 Sentence in abstract sounds convoluted and maybe even grammatically incorrect.\n\n\nThis sentence was originally trying to convey both the distinction between Policy Iteration (PI) and PMD as well as the distinction between PMD on a regularised and unregularised MDP. The important distinction is between PI and PMD. As a result, we have simplified the sentence to the following: \n\n**“Motivated by the instability of policy iteration (PI) with inexact policy evaluation, PMD algorithmically regularises the policy improvement step of PI\".**\n\nAs for the second point regarding PMD on a regularised and unregularised MDP, we will now make an explicit remark about this in the main text (see A.4).\n\n\n\n\n&nbsp;  \n\n\n### A.3 A lower bound on a class of algorithm and not on the problem seems strange.\n\nWe emphasise that the main contribution of the work is on the $\\gamma$-rate upper bound for PMD (Theorem 4.1). However, to demonstrate the tightness/optimality of this rate, we also provide a lower bound (Theorem 4.2).\n\nThis type of lower-bound is not standard in the RL literature. However, lower bounds for solving infinite-horizon MDPs with knowledge of the underlying dynamics are rare, and the only work we are aware of, by Chen and Wang (https://arxiv.org/abs/1705.07312), focuses on the computational complexity, which is not our focus.\n\nWe assume access to a policy-evaluation oracle for any policy. The problem we consider is the number of iterations needed to find an $\\varepsilon$-optimal policy, where at each iteration we are allowed one query from our oracle for any policy. As far as we know, there is currently no existing lower bound for this problem.\n\nIt is unclear what the lower-bound on the problem in general might be. However **our lower-bound holds on this problem for a large class of algorithms**: any algorithm that at each iteration increases the probability of the greedy action with respect to the action-value of the previous policy. \n\nIn addition, as we remarked in A.1, we are interested in the theoretical understanding of PMD, so we **want to compare the rate we establish for PMD to the best rate possible for PMD**. Our algorithmic specific lower-bound answers this question **positively**.\n\n\n\n\n\n\n&nbsp;  \n\n\n### A.4 Unregularized PMD is not explicitly explained in text.\n\nIn an attempt to avoid any confusion, we used the terminology “unregularized PMD” in the abstract to refer to the version of PMD we consider (as opposed to a different version used in prior work). For clarity, we will not use this terminology (see A.2) and will make the following explicit remark when defining PMD in Section 3.1:\n\n**“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 [11] where the action-value is augmented with some form of regularisation and is no longer the true action-value. This is a different algorithm that converges to a policy that is not optimal in the original unregularised MDP.”**"}, {"review_id": "eTRFu5jP0O", "reviewer": "Reviewer_YE79", "summary": "This work considers the class of Policy Mirror Descent (PMD) methods and establishes a linear $\\gamma$-rate which is dimension-free using adaptive step sizes. In particular, the convergence rate does not depend on visitation distribution mismatch coefficients or the state/action space sizes. It is further shown that this rate is optimal for PMD methods as it is the case for Policy Iteration via a matching lower bound. Adaptive step sizes are also shown to be necessary for this result to hold. Improving over prior work, the analysis which does not make use of the performance difference lemma is further extended to the inexact setting where the action value function needs to be estimated under a generative model. ", "questions": "1.  How easy is it to compute the adaptive step sizes in (5)? Is there any computational tradeoff? The step sizes seem to potentially involve dependence on the state/action space sizes and would require some computational efforts to be computed. For instance, computing the set $\\mathcal{A}_s^k$ requires screening the action space. Could you comment on this and compare to the step sizes in [7] regarding this aspect?  \n\n2. Does Theorem 4.3 about adaptive step-size necessity only hold for the particular case of the negative entropy for $h$ unlike all other results which hold for the general class of PMD methods? Could you comment on the reasons for that?  \n\n3. In Eq. (8), is the definition of $\\tilde{\\pi}_{s_i}^{k_i + 1}$ the same as in (5)? What are the states ${s_i}$ in l. 289? \n", "limitations": "The suboptimality in terms of the dependence on $1/(1-\\gamma)$ (which does not match the known lower bound) is discussed both in l. 330-332 and in the conclusion. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The independence of the rate on the visitation distribution mismatch coefficients is interesting and the novel analysis avoids using the performance difference lemma to achieve this. The flexibility of the analysis offers the possibility to close the gap between the convergence rates of PG methods and value-based methods in terms of $1/(1-\\gamma)$ and match the known lower bound. \n\n- The convergence rate which holds for the $l_{\\infty}$ norm is shown to be optimal and the adaptive step size is also necessary.  \n\n- The paper is well-written and the contributions are clearly presented.\n\n- The results are sound and the proof of the main result is clean.", "weaknesses": "- The interesting dimension-free rate seems to come with the price of more complicated adaptive step sizes compared to the increasing steps in [7]. \n\n- Some recent related works going beyond the tabular setting are missing in the discussion, especially regarding l. 131-133.  \n\nYuan, R., Du, S. S., Gower, R. M., Lazaric, A., & Xiao, L. Linear convergence of natural policy gradient methods with log-linear policies. ICLR 2023\n\nAlfano, C., & Rebeschini, P. (2022). Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209.15382.\n\nAlfano, C., Yuan, R., & Rebeschini, P. (2023). A novel framework for policy mirror descent with general parametrization and linear convergence. arXiv preprint arXiv:2301.13139.\n\n- While a matching lower bound is provided for the convergence rate, the dependence with respect to $1/(1-\\gamma)$ does not improve over prior work and does not match the known lower bound as acknowledged by the paper. \n\n-  Leveraging a connection with Policy Iteration, a dimension free rate was previously established in the literature in [9] for the NPG method with adaptive step sizes which is a particular case of the PMD class of methods. The present work extends somehow this result with adaptive step sizes which are independent on the minimal sub-optimality gap, using a different analysis (as discussed in l. 237 to 253). The extension to the inexact setting follows the same lines as prior work [7].    \n\n**Minor:** \n\n- l. 174: The function $h$ is continuously differentiable on the relative interior of the simplex $\\Delta(\\mathcal{A})$, so I guess $\\pi'$ belongs to the relative interior of $\\Delta(\\mathcal{A})$. \n\n**Typos:** \n- l. 184: mirror map h -> $h$\n- Eq. (4) (and Eq. (9)): $p \\in \\Delta(\\mathcal{A})$ and then $p_s$ is used in the argmin. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer YE79 for their valuable comments and feedback and for pointing our typos. We have now performed numerical experiments to validate our theoretical findings (see “global” Author Rebuttal and attached pdf), which we will include in the final version.\n\n&nbsp;  \n\n### B.1 Weaknesses\n\n- 1. As shown in Theorem 4.3, this step-size is in fact **necessary** for the dimension free $\\gamma$-rate. In section B.2 below, we also discuss the computational feasibility of the step-size.\n- 2. Thanks for mentioning these works. We will include them in the discussion.\n- 3. We stress that the focus of our work is on the **exact setting** (Theorem 4.1, 4.2 and 4.3). We include the inexact setting to showcase that **our analysis can also be used in this setting to remove an instance dependent factor** (that may depend on dimension) that appeared in prior work [7]. More generally, the analysis can easily be combined with any 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.\n- 4. While a dimension free rate was established in [9] for the specific case of NPG with adaptive step size, **no justification was provided for this step-size until our Theorem 4.3**.\n\n**Minor:** If $h$ is of Legendre type on the relative interior of $\\Delta(\\mathcal{A})$ (as for the negative entropy), then all iterates will belong to the relative interior of $\\Delta(\\mathcal{A})$ as long as $\\pi^0$ does. But if $h$ is of Legendre type for a domain that is larger than $\\Delta(\\mathcal{A})$ (as for the squared euclidean norm) then iterates will not always be in the relative interior of $\\Delta(\\mathcal{A})$, nor do we require $\\pi^0$ to be in the relative interior of $\\Delta(\\mathcal{A})$.\n\n&nbsp;  \n\n### B.2 Question 1\n\nHere are some additional comments regarding the adaptive step-size condition. We will include these in the final version. Recall $\\mathcal{A}^k_s = \\\\{a\\in\\mathcal{A}:Q^k(s,a)=\\max_{a'\\in \\mathcal{A}}Q^k(s,a')\\\\} $ denotes the set of optimal actions in state $s$ under policy $\\pi^k$ and $\\widetilde{\\Pi}^{k+1}\\_s$ is 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\\\\}$. For $\\\\{c_k\\\\}\\_{k \\in \\mathbb{Z}\\_{\\geq 0}}$ a sequence of positive reals, the step-size condition in (5) is\n\\begin{equation*}\n        \\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\\\\}.\n\\end{equation*}\n\n**The dependence on the action space can be removed:** The condition in (5) is a minimum over $\\widetilde{\\pi}^{k+1}_s\\in \\widetilde{\\Pi}^{k+1}_s$ so taking the condition for any $\\widetilde{\\pi}^{k+1}_s \\in \\widetilde{\\Pi}^{k+1}_s$ will be sufficient. In particular, we used the minimum to have the smallest condition but that is not necessary. Also note that in many cases, there will only be one greedy action, i.e. $\\mathcal{A}^k_s$ will consist of a single action and there will just be one policy in $\\widetilde{\\Pi}^{k+1}_s$.\n\nAs for the maximum over $s \\in \\mathcal{S}$, this is imposed because we are using the same step-size in all states for simplicity. If we allow different step-size in each state, then the step-size in state $s$, denoted $\\eta_k(s)$ would just have to satisfy \n\\begin{align*}\n        \\eta_k(s)\\geq\\frac{1}{c_k}\\Big\\\\{\\min_{\\widetilde{\\pi}^{k+1}_s\\in \\widetilde{\\Pi}^{k+1}_s}D_h(\\widetilde{\\pi}^{k+1}_s,\\pi^k_s)\\Big\\\\}.\n\\end{align*}\n\nFurthermore if we choose any $\\widetilde{\\pi}^{k+1}_s \\in \\widetilde{\\Pi}^{k+1}_s$, then the following is sufficient:\n\\begin{align*}\n        \\eta_k(s)\\geq\\frac{1}{c_k}D_h(\\widetilde{\\pi}^{k+1}_s,\\pi^k_s).\n\\end{align*}\n\n**The computational complexity of computing the step-size is then that of computing the Bregman divergence between two policies.**\n\nSo in general, this will be more expensive than the step-size of [7]: $\\eta_k = \\eta_0 / \\gamma^k$. However, in many cases, computing the Bregman divergence is no more expensive than computing the PMD update in a state given the step-size (e.g. for relative-entropy and squared euclidean distance mirror maps). If so, the cost of computing the step-size in (5) adds to the overall computational complexity of the algorithm but the order of magnitude would remain the same.\n\n&nbsp;  \n\n### B.3 Question 2\n\nYes, 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.\n\nWe need the closed form update because we show that there is an iteration $k_0$ where the amount of probability mass on the sub-optimal action of a state has to drop by a certain amount from $\\pi^{k_0}$ to $\\pi^{k_0 + 1}$ in order to satisfy the $\\gamma$-rate condition of Theorem 4.3. We then explicitly relate this drop to the size of the step-size by using the closed form update. \n\n&nbsp;  \n\n### B.4 Question 3\n\nIn Eq. (8), the definition of $\\tilde{\\pi}^{k_i+1}\\_{s_i}$ is the **same** as in (5). In particular, the MDP considered in the proof has 2 actions in each state so it is the policy which is greedy w.r.t $Q^{\\pi^{k_i}}_{s_i}$.\n\nAs for the states in l. 289, the MDP consists of a chain of $n+1$ states, $n$ of which have an additional state associated to them (total of $2n + 1$ states). The states $\\{s_1,...,s_n\\}$ in Theorem 4.3 are the $n$ states in the chain which have this additional state (see Appendix E for more detail on the construction of this MDP). In fact, these states are the only none-trivial states of the MDP where the 2 actions are not both optimal. **The main point is that this necessary condition is enforced in $n$ distinct iterations in the $n$ distinct non-trivial states of the MDP.**"}, {"review_id": "PpVAbQItVw", "reviewer": "Reviewer_TTxd", "summary": "This paper studies the convergence rate of a general family of policy gradient methods called Policy Mirror Descent (PMD) in the setting of discounted MDP, unregularized objective, and tabular policy model. In prior work ((Xiao, 2022), [7] in the paper), it has been known that with a geometrically increasing step size schedule, all PMD algorithms enjoy nice convergence rate and sample complexity with respect to the discounting factor $\\gamma$, but the bounds proved in [7] also depend on a \"distribution mismatch coefficient\" term. This paper shows that with a more adaptive step-size schedule, this \"distribution mismatch coefficient\" term can be removed from the bounds. The results are derived by simplifying the analysis in [7] with a value improvement property of PMD algorithms (Lemma A.2). The paper also presents theorems to argue that the convergence rate they proved is tight, and that the adaptive step-size schedule is necessary for achieving this rate.", "questions": "A. Table 1: Why isn't \"linear $\\gamma$-rate\" checked for [7], while at Line 31 you said \"*linear convergence of PMD was established by [7]*\"?\n\nB. Line 264-266: I wonder if extending (7) to k>n will necessarily contradict with the fact that PI converges in finite iterations. Specifically, the latter implies that for large enough k, we have $||V^*-V^k||=0$. To have (7) hold for such k, we \"only\" need to have $\\gamma^k ||V^*-V^0||\\leq \\frac{2\\delta}{1-\\gamma}$, which does not look impossible to me unless $\\delta$ and $V^0$ have some special constraints -- can you explain a bit more here? Although (7) is linear to $\\gamma^k$, does the negative constant term $-\\frac{2\\delta}{1-\\gamma}$ in (7) actually allows exact convergence to $V^*$?\n\nC. Line 308: $(s^0_t, a^0_t)$ should be $(s^i_0, a^i_0)$ ?", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper seems to be a solid follow-up work after (Xiao, 2022) [7]. The paper gives a nice analysis to the PMD algorithms (removing unnecessary and \"ugly\" terms in previous results, simplifying the analysis framework, providing optimality/necessity arguments, etc.).\n\n2. The results presented in this paper are nicely compared and contrasted with previous works.", "weaknesses": "1. I am not very sure about the significance of the results presented by the paper. While it is nice to see that with carefully scheduled step sizes every PMD algorithm could match the performance of PI and NPG, the step-size schedule required does not look very practically feasible to me, and it's still not clear if any concrete and practical PMD algorithm can demonstrate better performance than PI and NPG. Because PI and NPG are two special cases of PMD, bounds applying to all PMD algorithms are necessarily subject to the bounds of PI and NPG, so I wonder if aiming at proving bounds that \"universally\" apply to all PMD algorithms, as this paper does, can be truly helpful in identifying *better* PMD algorithms. Maybe the authors can consider to better motivate this work.\n\n2. I have some concern about whether Theorem 4.2 can indeed establish the optimality of the convergence rate as proved in the paper. If I understand correctly, Theorem 4.2 says that for any given state-space size $|S|$, there exists a MDP with $|S|$ states such that no PMD algorithm can be faster than the linear $\\gamma$-rate in the first $|S|/2$ PMD iterations. But this result does not bound the asymptotic performance of PMD, right? As the paper already mentioned (Line 265), PI can converge exactly to the optimal policy in finite iterations, this fact means PI, as one instance in the PMD family, must converge faster than the linear $\\gamma$-rate after the first $|S|/2$ iterations. In this case I am not sure why the linear bound in Theorem 4.1 must be optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer TTxd for their valuable comments and feedback. We have now performed numerical experiments to validate our theoretical findings (see “global” Author Rebuttal and attached pdf), which we will include in the final version.\n\n&nbsp;  \n\n### C.1 I am not very sure about the significance of the results presented by the paper.\n\nThe purpose of this work is not to demonstrate that certain instances of PMD outperform PI or NPG in the exact setting. In fact, as indicated by the lower-bound in Theorem 4.2, **no instance of PMD can surpass the performance of PI in this setting**. Instead, our focus lies in understanding the theoretical properties of PMD, as discussed in more detail in section A.1 of this rebuttal (in response to wj3u). Specifically, **our results characterize the step-size required for each mirror-map to match the performance of PI**. In doing so, we develop a **novel theoretical proof scheme** that avoids visitation distributions and the use of the performance difference lemma, an important theoretical tool central to the analysis of PMD in previous work [7, 9, 17]. The **technique we use is not restricted to PMD and may be of independent interest to RL algorithms in general**.\n\n**Our results rule out searching for instances of PMD that may improve on PI or NPG**. Although proving bounds that universally apply to all PMD instances will not directly help in identifying better PMD algorithms, our work show that, in the exact setting, the algorithmic differences between instances of PMD do not affect the performance of the algorithm beyond the step-size condition.\n\nRegarding the feasibility of the step-size, a detailed discussion can be found in section B.4 (in response to YE79).\n\n&nbsp;  \n\n### C.2 Question A\n\nIn Table 1, linear $\\gamma$-rate is checked if the result is not only linear convergence but linear convergence with the $\\gamma$-rate. [7] establish linear convergence of PMD but not with the $\\gamma$-rate (see lines 217-231 for more details).\n\n&nbsp;  \n\n### C.3 Question B\n\n\nIn the statement of Theorem 4.2, $\\delta$ can take any value in $(0, (1-\\gamma)\\gamma^n)$. We could choose $\\delta = \\frac{1}{2} (1-\\gamma) \\gamma^n \\|\\|V^{\\star} - V^0\\|\\|\\_\\infty$ (in the construction of the MDP we have $\\|\\|V^{\\star} - V^0\\|\\|\\_\\infty < 1$ so this is a valid choice of $\\delta$) and get the following bound\n\\begin{align}\n    \\|\\|V^{\\star} - V^k\\|\\|\\_\\infty \\geq \\Big(\\gamma^{k} - \\gamma^n \\Big) \\|\\|V^{\\star} - V^0\\|\\|\\_\\infty,\n\\end{align}\n\nwhich would hold for all $k$. However, the bound would be **meaningless** for $k \\geq n$ and the implication of the result would not be different to restricting $k \\leq n$. \n\nIn general, we can take $\\delta$ arbitrarily close to 0 and the lower-bound is arbitrarily close to $\\gamma^{k} \\|\\|V^{\\star} - V^0\\|\\|\\_\\infty$. \n\nFor further comments on the extension of Theorem 4.2 to arbitrary iterations, refer to the section below (C.4).\n\n&nbsp;  \n\n### C.4 I have some concern about whether Theorem 4.2 can indeed establish the optimality of the convergence rate as proved in the paper.\n\nThe understanding of TTxd of Theorem 4.2 is correct, it does not bound the asymptotic performance of PMD. But any attempt to establish a lower-bound on the **asymptotic** rate of convergence for PMD (with **arbitrary** step-size) will fail.\n\nIn fact, any attempt to establish a lower-bound on the convergence rate of PMD will necessarily fall into one of two categories: (i) being limited to finite iterations, as we have done in Theorem 4.2, or (ii) having the bound become negative after a finite number of iterations, as TTxd has suggested. This stems from the **exact** convergence of PI within a finite number of iterations [33].\n\nHowever, this has to be the case **even if we exclude PI** from the class of considered algorithms because we state Theorem 4.2 for PMD with **arbitrary** step-size. 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 meet one of the above requirements ((i) or (ii)).\n\nAlso, note that the finite-time convergence of PI depends on the size of the state space and action space. This **justifies having a finite-iteration lower-bound that depends on the size of the state space as ours does**. One possible improvement to Theorem 4.2 could involve having the iterations for which it holds align precisely with PI's exact finite-iteration convergence. Beyond this, Theorem 4.2 is unimprovable (given that we consider PMD for any step-size).\n\n**Rate-Optimality**\n\nTheorem 4.2 establishes that the **$\\gamma$-rate is optimal in the first $|\\mathcal{S}|/2$ iterations**. The explanations in the discussion above (C.4) establish that the **optimal rate is only optimal for a finite number of iterations**, and specifically up until the exact convergence of PI.\n\nWith this in mind, (we believe that) the **claim of rate-optimality is valid** because for any finite number of iterations $K$, there is an MDP of size $2K + 1$ such that no PMD algorithm is faster than the linear $\\gamma$-rate in those $K$-iterations. Additionally, if we consider PMD on a tabular MDP with fixed state space size $|\\mathcal{S}|$, then the $\\gamma$-rate is optimal for the initial $|\\mathcal{S}|/2$ iterations. We will however clarify these points more explicitly in the final version.\n\n&nbsp;  \n\n### C.5 Question C\n\nReviewer TTxd is correct. Thanks for pointing this out."}, {"review_id": "91N7fG6xuO", "reviewer": "Reviewer_GGgc", "summary": "This paper proposes a new analysis of the policy mirror descent algorithm and achieves a linear convergence rate with exact $Q$-function that does not contain any distribution mismatch coefficient. Furthermore, it also proposes lower bounds showing that the linear convergence rate is optimal under specific setting and policy-dependent learning rates are necessary to achieve this rate.", "questions": "- What are the difficulties of extending the result in Theorem 4.2 to the setting of $k\\geq n$?\n- Is that possible to strengthen the Theorem 4.3 in a form saying that (under the same or similar setting for $n$, $\\gamma$ and $\\mathcal{S}$) policy-dependent learning rates are necessary whenever we hope to achieve $\\Vert V^\\star-V^k\\Vert_{\\infty}\\leq c_0\\gamma^k(\\Vert V^\\star-V^0\\Vert_{\\infty}+c_1)$ for any $c_0, c_1>0$?\n- Is $\\eta_k$ always guaranteed to be finite?", "limitations": "The limitations are not addressed very well as explained in the weakness section.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The convergence result for policy mirror descent is strong while the analysis is concise.\n- The proposed two lower bounds are also considered to be novel.", "weaknesses": "One weakness of this paper lies in the lower bound stated in Theorem 4.2 only holds for $k<n$, which does not rule out possibility of stronger convergence rate when $k\\geq n$. Therefore, it seems not very appropriate to claim that this result is optimal without any qualifiers.\n\nAnother weakness is on the lack of experiments. Since the major results of this paper strongly rely on a delibrately designed learning rate, it will be much better to empirically (in some tabular MDPs) see that this choice of learning rate is indeed better than other choices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer GGgc for their valuable comments and feedback. We have now performed numerical experiments to validate our theoretical findings (see “global” Author Rebuttal and attached pdf), which we will include in the final version.\n\n&nbsp;  \n\n### D.1 What are the difficulties of extending the result in Theorem 4.2 to the setting of $k<n$ ?\n\nSee Section C.3 (in reply to TTxd) for a discussion of this. \n\n&nbsp;  \n\n### D.2 It seems not very appropriate to claim that this result is optimal without any qualifiers.\n\nSee Section C.4 (in reply to TTxd) for a discussion of this. \n\n&nbsp;  \n\n### D.3 Another weakness is on the lack of experiments.\n\n**We have now performed numerical experiments** to validate our theoretical findings (see “global” Author Rebuttal and attached pdf), which we will include in the final version.\n\n&nbsp;  \n\n### D.4 Is it possible to strengthen Theorem 4.3 ?\n\nIt is possible relax the condition in Theorem 4.3 slightly. If we are hoping to achieve a bound of the form\n\\begin{align*}\n    \\|\\|V^\\star - V^k\\|\\|\\_\\infty \\leq c_0 \\gamma^{k} (\\|V^\\star - V^0\\|_\\infty + c_1)\n\\end{align*}\n\nfor $c_0, c_1 > 0$. Then to obtain a similar statement to Theorem 4.3, we will require at least:\n\\begin{align*}\n    c_0 (\\gamma + c_1) < 1.\n\\end{align*}\n\nThis condition arises from technical conditions in the proof. There is limited scope for improving the value of $c_0$, which is constrained to be bounded by $1/\\gamma$ as $c_1$ approaches zero. However, if one chooses to decrease $c_0$, then larger values of $c_1$ can be accommodated. We are happy to provide more details on the steps of the proof that require this condition.\n\n&nbsp;  \n\n### D.5 Is $\\eta_k$ always guaranteed to be finite?\n\n**The step-size 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). 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. If $h$ is of Legendre type for a domain that is larger than $\\Delta(\\mathcal{A})$ (as for the squared euclidean norm) then iterates will not always be in the relative interior of $\\Delta(\\mathcal{A})$ but there are no issues evaluating the bregman divergence for policies on the boundary of $\\Delta(\\mathcal{A})$ so the step-size is also finite."}]

Author rebuttal:
We have now performed numerical experiment to validate our theoretical findings (see attached pdf), which we will include in the final version.

The plots in the attached PDF are made by running NPG (PMD with negative-entropy mirror map, see [9]) on the hard MDP used to prove Theorem 4.2. 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 [7]: $\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$.

&nbsp;  


### 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 in our paper.** 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 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 [7]) beyond the optimal $\gamma$-rate valid up to a finite iteration (recall that for arbitrary step size, PMD can be arbitrarily close to policy iteration, which converges in finite iterations; see C.4 in the response to Reviewer TTxd).

Meta-review: This paper obtains the optimal dimension-free rates for Policy Mirror Descent (PMD) and shows that unregularized PMD methods with an adaptive step-size can match the performance of PI. 

The reviewers agree that the paper is well-written, and its contributions merit acceptance. I agree and recommend the acceptance of this paper. Please incorporate the reviewer's comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Adding the numerical experiments included as part of the rebuttal 
- Clearly including the discussion about the computational complexity of calculating the adaptive step-size. 
- Include the discussion with Rev. TTxd and GGgc about the (non)-asymptotic performance of PMD.
Decision: Accept (poster)