Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Authors: Uri Sherman
Tomer Koren
Yishay Mansour
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning Theory
Function Approximation
Optimization
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We develop a theoretical framework for PMD in the agnostic, non-complete policy class setting, and prove upper bounds on the rate of convergence w.r.t. the best-in-class policy

Abstract: Modern policy optimization methods roughly follow the policy mirror descent (PMD) algorithmic template, for which there are by now numerous theoretical convergence results.
    However, most of these either target tabular environments, or can be applied effectively only when the class of policies being optimized over satisfies strong closure conditions, which is typically not the case when working with parametric policy classes in large-scale environments. 
    In this work, we develop a theoretical framework for PMD for general policy classes where we replace the closure conditions with a generally weaker variational gradient dominance assumption, and obtain upper bounds on the rate of convergence to the best-in-class policy. Our main result leverages a novel notion of smoothness with respect to a local norm induced by the occupancy measure of the current policy, and casts PMD as a particular instance of smooth non-convex optimization in non-Euclidean space.

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Uri Sherman Tomer Koren
12 Yishay Mansour 12
Abstract
function of x and B is distance-like function employed to regularize the update as to not stray too far from x², The solution to Equation (1) is usually produced by optimizing a parametric neural network model zo (known as the actor, or policy network) via multiple steps of stochastic gradient descent, and consequently, the policy class II is the set of policies representable by the model; where p denotes the number of parameters in the network.
Modern policy optimization methods roughly fol- low the policy mirror descent (PMD) algorithmic template, for which there are by now numerous theoretical convergence results. However, most of these either target tabular environments, or can be applied effectively only when the class of poli- cies being optimized over satisfies strong closure conditions, which is typically not the case when working with parametric policy classes in large- scale environments. In this work, we develop a theoretical framework for PMD for general policy classes where we replace the closure conditions with a strictly weaker variational gradient dom- inance assumption, and obtain upper bounds on the rate of convergence to the best-in-class pol- icy. Our main result leverages a novel notion of smoothness with respect to a local norm induced by the occupancy measure of the current policy, and casts PMD as a particular instance of smooth non-convex optimization in non- non-Euclidean space.
(Ie 0 R²),
Contemporary theoretical analyses of this algorithm (Shani et al., 2020; Agarwal et al., 2021: Xiao, 2022; Ju & Lan, 2022; Zhan et al., 2023; Yuan et al., 2023; Alfano et al., 2023) all have their roots the online Markov decision pro- cess (MDP) framework, and roughly build on decomposing Equation (I) state-wise and casting the problem as a collec- tion of independent online mirror descent steps (Even- -Dar et al., 2009). The disadvantage of such an approach lies in the requirement that the update step be exact (or almost exact) in each state independently. effectively limiting the applicability of such analyses to policy classes that are com- plete, (i.e., Il S) ) or otherwise satisfy strong closure conditions.
Largely, papers that develop convergence upper bounds for algorithms following Equation (1), commonly known as Policy Mirror Descent (PMD; Tomar et al., 2020; Xiao, 2022; Lan, 2023), fall into two main categories. The first category includes studies that target the tabular setup (e.g.. Geist et al., 2019: Shani et al., 2020; Agarwal al., 2021; Xiao, 2022; Johnson al., 2023; Lan, 2023; Zhan al., 2023), where sampling distribution je² is involved (or it has effect) and updates are performed in per-state man- ner. The second category consists of papers that consider parametric policy classes (e.g., Agarwal et al., 2021; Alfano & Rebeschini, 2022: Ju & Lan, 2022: Yuan et al., 2023; Al- fano et al., 2023; Xiong et al., 2024) often sollding-ethoen directly or indirectly-on the compatible function approx- imation framework (Sutton al., 1999). As such, these works essentially assume that the update in Equation (1) remains "close" to the one that would have been performed over the complete policy class (see Section 1.2 for further discussion). This state affairs is (at least partially) due to the fact that policy gradient methods in the general policy class setting are prone to local optima (Bhandari & Russo.
1. Introduction
Modern policy optimization algorithms (Peters & Schaal, 2006; 2008; Lillicrap, 2015; Schulman et al., 2015; 2017) operate by solving a sequence of stochastic optimization problems, each of which being roughly equivalent to:
(Qt. (.B((Ts)))))) {
arg min Es-ne TEll
(1)
where j² is state probability measure (typically related, or equal to, the occupancy measure of the current policy )² from which sampling is granted through interaction with the environment; Ø is an estimate of the action-value
Blavatnik School of Computer Science and AI, Tel Aviv Uni- versity, Tel Aviy, Israel Google Research, Tel Aviv, Isracl. Corre- spondence to: Uri Sherman <urisherman @ tau.iila.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
2024), and a result, structural assumptions are necessary to establish global optimality guarantees.
larization, V(**) minx*en V(*²)=
o C211 12/3
+ (C.H+AHRR Vester + Exgd
The present paper aims to establish best-in-class conver- gence of PMD (Equation (1)) for general policy classes, relaxing the stringent closure conditions and assuming in- stead a variational gradient dominance (VGD) condition (Bhandari & Russo, 2024; Agarwal et al., 2021; Xiao, 2022). can be shown that a general form of closure conditions implies VGD and that the converse does not hold, hence it is strict relaxation of the setup assumptions (see detailed discussion in Section 1.2 and Appendix A). Our main result features a novel analysis technique that casts Equation (1) as a particular instance of smooth non-conven optimization in a non-Euclidean space, where the smoothness of the objective w.r.t. a local norm induced by the current policy occu- pancy measure. Importantly, this approach leads to rates independent of the cardinality of the state space. In contrast, previous results that establish convergence of gradient based methods (though not of PMD; e.g., Agarwal et al., 2021; Bhandari & Russo, 2024; Xiao, 2022) that are applicable in our setting, lead to bounds that depend on the size of the state-space, thus rendering them useful only in tabular setups.
and with negative Entropy regularization, we have that V(**) - min V(**)=
C211 2217
(C.H+ (CHH+19HH47) V Evgd
where the big-O only suppresses constant numerical factors.
To obtain our main result, our analysis casts PMD as a proximal point algorithm in non-Euclidean setting (see Teboulle, 2018 for review), where the proximal operator uses regularizer that adapts to local smoothness of the ob- jective. As we demonstrate in Lemma 2, the approximation error of the linearization of the objective V(-) at x² can be bounded w.r.t. the local norm (1=) crucially, a norm according to which the decision set II has diameter indepen- dent of the cardinality of the state-space. This significantly deviates from the commonly used smoothness of the value function w.r.t. the Euclidean norm (Agarwal al., 202 I), which assigns a diameter of [S] to II, and therefore leads to rates that have merit only in tabular environments.
1.1. Main results
1.2. Discussion: VGD vs. Closure
We consider the problem of finding an (approximately) op- timal policy in a discounted MDP M M= P.r within general policy class II A(R)S. We assume the action set is finite A= = |,, and denote the effective horizon by H == T Our goal is to minimize the value V(r), defined as the iong term discounted cost (we interpret r: S x A - [0. 1] as measuring regret, or cost). Our cen- tral structural assumption, that replaces and relaxes specific closure conditions, is the following.
Our work establishes best-in-class convergence subject to the VGD condition presented in the previous section. This is substantially different starting point than that of the preva- lent closure conditions based on the compatible function approximation approach (Sutton et al., 1999) assumed in recent works on parametric policy classes (Agarwal et al., 2021; Yuan et al., 2023; Alfano et al., 2023; Xiong et al., 2024). The assumptions employed in these works fall into two main categories; The first and more general one is that of a bounded approximation error (e.g.. Alfano et al., 2023; Yuan et al., 2023), which essentially requires that the update step in Equation (1) be close (up to a small error) to the update that would have been performed over the complete policy class aail = A(T)S. The second is that of bounded transfer error (e.g., Agarwal et al., 2021; Yuan et al., 2023), which roughly requires that the update be accurate (up to small error) when accuracy is measured over the optimal policy occupancy measure. This assumption is commonly employed in the specific log-linear policy class setup: to the best of our knowledge, there do not exist results that employ these conditions ting (Agarwal et al., 2021 consider non- -MD method in bounded transfer error setup where the policy class satisfies additional smoothness assumptions).
Definition 1 (Variational Gradient Dominance). We say that II satisfies a (C., Evga) vvrriatiil gradient domi- nance (VGD) condition w.r.. M, if there exist constants C.. Evgd > O, such that for any policy π E III:
V(z) - v* (II) s C. max (VV(T), x #) + Exgd- #ell
(2)
We note that any policy class satisfies the above conditions with some C. 2 1, Evgd & H. and that the complete policy class is (H I|u* / poll... V)DV w.r.t. any MDP (see Bhan- dari& & Russo, 2024; Agarwal et al., 2021, and Lemma 16 for completeness). Our main result is the following.
fully general policy class set-
Theorem (informal). Let II C (A)S be convex and as- sume it satisfies (C., VVD w.r.t. M. Suppose further that the actor and critic are approximately optimal up to some error Ettt > 0. Then, with well tuned 6- e-greedy explo- ration and learning rate 17, we have that the PMD method (Equation (1)) converges as follows. With Fuclidean regu-
The relation between closure and VGD is subtle, primarily because closure conditions are algorithm dependent. Typ- ically, they relate to one or more of the following three
2

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Table 1: Comparison of assumptions and bounds representative prior works for PMD with fixed step size. Columns refer to assumptions required either implicitly or explicitly by different works. VGD is implied by a natural extension of closure; see Appendix A.1 for further details. The Realizability column refers to approximate realizabilityy. which is implied by closure conditions. The Rate column suppresses all factors other than K, and ignores error floors. Closure (perfect): The policy class is closed to a PMD update up foo-norm error. Closure (approx): The policy class closed a PMD update up error that depends on the sampling distribution. General dual with EMP parametrization: EMaP stands for Exact Mirror and Project; in these works the policy class is induced by a general dual variable parametrization, combined with an operator that performs the mirror and project steps accurately.
Parametric
Paper
VGD
I1 Convexity
Realizability
Closure
Rate
Assumptions
Xiao (2022);
Yes
No
Yes
Yes (perfect)
Tabular
1/K
Lan (2023)
Yuan et al. (2023)
Yes
No
Yes
Yes (approx)
Log-linear
1/K
General dual w/ EMaP
Lan (2022)
Yes
No
Yes
Yes (perfect)
1/VK
General dual w/ EMaP
Alfano et al. (2023)
Yes
No
Yes
Yes (approx)
1/K
This Work
Yes
Yes
No
No
No
1/K2/3
Prior works on the tabular setting typically assume the policy class complete II A(H)S, and thus convex. However their arguments extend to the case that II satisfies perfect closure, which eliminates the need for II being convex.
We refer to the bounds obtained by Yuan al. (2023) subject to bounded approximation error. Yuan et al. (2023) also obtain convergence subject to bounded transfer error - it is unclear to what extent (if at all) bounded transfer error implies VGD.
Ju & Lan (2022) also obtain an (11/K) rate for regularized PMD.
We report our rate for Euclidean PMD. More generally, our bounds depend on the smoothness of the action regularizer, and dependence on K degrades for non- -on-uucideann regularizers such as negative entropy.
Assuming only VGD without closure, our analysis requires convexity of II. However, in the presence of closure assumptions such as those of Alfano et al. (2023), our analysis does not require convexity of TI (see Appendix A.2 for further details).
elements; step-size range, action regularizer, and the partic- ular algorithmic approach employed to solve Equation (1). At the same time, the VGD condition is algorithm inddpnn- dent, as it relates only to the policy class-MDP combination. Nonetheless, as we show in Appendix A.I, reasonable extension of PMD closure conditions implies variational gradient dominance, effectively establishing PMD closure = VGD. At a high level, this builds on a similar claim from Bhandari & Russo (2024), that closure to policy im- provement implies VGD. We further demonstrate in Ap- pendix A.3 that the converse does not hold; that there exist simple examples where the VGD condition holds whereas closure does not take place. We refer to Table 1 for high level comparison between our work and prior art, and con- clude this section with the following additional remarks.
size PMD. Many prior works that study PMD in the tabu- lar setup or subject to closure conditions establish linear convergence for geometrically increasing step size se- quences (Xiao, 2022; Johnson et al., 2023; Yuan et al., 2023; Alfano et al., 2023). We do not expect such rates are possible assuming only VGD. Roughly speaking, the reason these rates are attainable subject to closure is that the algorithm dynamics mimic those of policy iteration in the tabular setting, where convergence is indeed at a lin- ear rate. Assuming only VGD, policy iteration no longer converges, as the policy class loses the favorable structure allowing for convergence of such an aggressive algorithm. This should highlight the value in studying the function approximation setup without closure assumptions.
Realizability. Closure conditions generally imply (approximate) realizability, thus under this assump- tion convergence w.r.t. the true optimal policy x* arg min pey V(T) is possible. We do not assume real- izability and therefore prove convergence to the optimal in-class policy. Specifically, all prior works prove bounds that only hold in (approximately) realizable settings, while our bounds do not require realizability.
Convexity of the policy class. Unlike prior works, we consider VGD instead of closure but additionally require convexity of the policy class II. However, subject to perfect closure, it can be shown that the iterates of PMD satisfy optimality conditions w.r.t. a convex policy class that contains II (concretely, will be the complete policy class ((A)),, ), which is the key element required in analysis. Thus, our analysis accommodates non convex policy classes as long as perfect closure holds. We refer the reader to Appendix A.2 for a more formal discussion.
Geometric rates. Table reports rates for fixed step
3

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
1.3. Additional Related work
of conditions on the parametric representation. We refer the reader to Yuan et al. (2022) for further review.
PMD with non-tabular policy classes. Most closely re- lated to our work are papers that study convergence of PMD in setups where the policy class is given by function approx- imators (Vaswani et al., 2022; Ju & Lan, 2022; Grudzien et al., 2022; Alfano et al., 2023; Xiong et al., 2024). The motivation of Alfano et al. (2023); Xiong et al. (2024) is somewhat related to ours but they address a different as- peet of the problem in question. These works focus on the approximation errors in the update step (thus essentially assuming closure) and propose algorithmic mechanisms to ensure it is small, but obtain meaningful upper bounds only when it is indeed small w.r.t. the exact steps over the complete policy class (as discussed in the previous section). There is a long line of works on parametric policy classes and specific instantiations of PMD such as the Natural Pol- icy Gradient (NPG; Kakade, 2001); which is the focus of, e.g., Alfano & Rebeschini (2022); Yuan et al. (2023); Cayei et al. (2024) as well as Agarwal et al. (2021). Many works also study convergence dynamics induced by particular pol- icy classes, e.g., Liu et al. (2019); Wang et al. (2020); Liu et al. (2020); we refer the reader to Alfano et al. (2023) for an excellent and more detailed account of these works.
Bregman proximal point methods. As mentioned, our analysis builds on realizing PMD as an instance of a Breg- man proximal point algorithm - roughly, this is proximal point algorithm (Rockafellar, 1976) in a non-Euclident set- ting (see Teboulle (2018) for a review). There are numerous studies that investigate non-Euclidean proximal point meth- ods for both convex and non-convex objective functions (e.g., Tseng. 2010; Ghadimi et al., 2016; Bauschke et al., 2017; Lu et al., 2018; Zhang & He, 2018; Fatkhullin & He, 2024; see also Beck, 2017). although none of them accommodate the particular setup that PMD fits into (see Appendix E for details). Our analysis for the proximal point method presented in Section 3.2 is mostly inspired by the work of Xiao (2022); specifically, their upper bounds for projected gradient descent, where they apply a proximal point analysis in the euclidean setting.
2. Preliminaries
Discounted MDPs. A discounted MDP M is defined by tuple M = A, P. Prr,y y.p). where S denotes the state- space, A the action set, P: S x A - A(S) the transition dynamics, r: S x A - [0. I] the reward function, 0 < y < 1 the discount factor, H = T-y the effective horizon, and po A(S) the initial state distribution. For notational convenience, for s.a E S x A we let P... = IP( s,a) A(S) denote the next state probability measure.
Several prior works have made the observation that PMD is mirror descent step on the linearization of the value function with dynamically weighted regularization term (Shani et al., 2020; Tomar et al., 2020; Vaswani et al., 2022; Xiao, 2022), which is the starting point of our work. In particular, this perspective is the focus of Vaswani et al. (2022); however this work did not establish any convergence guarantees.
We assume the action set is finite with A == [Al, and identify AR with R... We additionally assume, for clarity of expo- sition and in favor of simplified technical arguments, that the state space is finite with S = (S), and identify R$ with R.S. We emphasize that all our arguments may be extended to the infinite state-space setting with additional technical work. An agent interacting with the MDP is modeled by a policy æ: S - A for which we let л, E A(R) C RA denote the action probability vector at s and As,a E [0. 1] denote the probability of taking action a at s. We denote the value of æ when starting from a state s S by (T)::
PMD in the tabular setting. The modern analysis ap- proach for PMD the generic (agnostic to the regularizer) tabular setup is due to Xiao (2022). Additional works that study the tabular setup include Geist et al. (2019); Lan (2023); Johnson et al. (2023); Zhan et al. (2023). As in the function approximation case, many works study conver- gence of the prototypical PMD instantiation; the NPG or its derivatives TRPO (Schulman et al., 2015) and PPO (Schul- man et al., 2017) in tabular or coftmax-tabulke settings, e.g., Agarwal et al. (2021); Shani et al. (2020); Cen et al. (2022); Bhandari & Russo (2021); Khodadadian al. (2021; 2022).
V,(T) E Σ rr(s, a,) 1 so = =,
Policy Gradients in parameter space. There is rich line of work into policy gradient algorithms that take gradient steps in parameter space, both in the tabular and non-tabular setups (Zhang al., 2020; Mei et al., 2020; 2021; Yuan et al., 2022; Mu & Klabjan, 2024). This class of algorithms are a special case of on-policy PMD only in the case of the direct parametrization, but are not PMD algorithms in general. Most of the results in the case of non-tabular. generic parameterizations characterize convergence in terms
and more generally for any P E A(S), Vo(x) = V When the subscript is omitted, V(r) denotes value of when starting from the initial state distribution pw:
80
V(x) = (T) E
(T)
Σ 1=0
yr(ss,
1 so Po.
For any state action pair s, E S x A. the action-valde function of π,, or Q-function, measures the value of æ when
4

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
starting from 8, taking action a, and then following for the reset of the interaction:
Algorithm Policy Mirror Descent (on-policy)
Input: learning rate > O, regularizer R: R- _ R Initialize x²
oo Σ
2
=E r'rrss)))))) s0 = a 1=0
for k to do
Set f == n² @ θ π xk*1 - arg min E--ut || (1(2t. BR( xell
We further denote the discounted state-occupancy measure of æ induced by any start state distribution E A(S) by ug:
end for
8
(5)s)= = (1 Σ y Pr(ss = s p.x).
Definition 2 (Bregman divergence). Given convex differ- entiable regularizer R: IR IR, the Bregman divergence w.r.t R is:
is easily verified that μ" A(S) is indeed a state prob- ability measure. In the sake of brevity, we take the MDP true start state distribution po as the default case one is not specified:
BR(u,v) = R(u) R(v) (VR(v),uv))
Throughout, make the following assumptions regard- ing the solutions to the sub-problems and the Q-function estimates Algorithm 1.
118h
(3)
Assumption I (Sub-problem optimization oracle). We as- sume that for all k, n²*1 is approximately optimal, in the sense that constrained optimality conditions hold up to error Eact
Learning objective. In the conventional formulation of MDPs, the objective is to maximize the discounted total reward, i.e., max, V(r). In this paper, we follow Xiao (2022) and adopt a minimization formulation in order to better align with conventions in the optimization literature. To this end, we regard each r(s,a) a) [o, 1] as a value measuring regret, or cost, rather than reward. Given any reward function r, may reset r(s, a) < 1 - r(s, a) for all s, E S x A to transform it into a regret function. With this in mind, we consider the problem of finding an approximately optimal policy within a given policy class I A(A)S;
VT E II, (V ), - -ntt1) 2 -Eact.
where (T( = Ex-pe [H (Qt. + (R(
Assumption 2 (Q-function oracle). We assume that for all
Es-pa |10: -2,11
Eerit
We remark that our results can be easily adapted to some- what weaker conditions on the critic error; we defer the discussion Appendix B.I.
arg min V(z). xell
(4)
To avoid ambiguity, denote the optimal value attainable by an in-class policy (a solution to Equation (4)) by V* (II),
Additional notation. Given state probability measure μ A(S) and action space norm I1-1le R - R, we define the induced state-action weighted L" norm II-Izee(, RSA - R as follows:
and the optimal value attainable by any policy by V*:
v* (II) arg min ((T*); e
V
arg min V(x*).
(5)
x² **)A(
| = (Es-z I1u, 1/2
We note that we do not make any explicit structural assump- tions about M. We will however make some assumptions about the policy class II, which will be made clear in the statements of our theorems.
For any norm |1-I1, we let I1-I1" denote its dual. When dis- cussing a generic norm and there is no risk of confusion, we may use Il-I1, to refer to its dual. We repeat the following notation that is used throughout the paper for convenience:
2.1. Problem Setup
In this work, we focus on the PMD method Algorithm 1 for solving Equation (4) in the case that the policy class is non- complete, π # A In each iteration, PMD solves a stochastic optimization sub-problem formed by an estimate of the current policy Q-function and a Bregman divergence term which is defined below.
1 = H
S S=
A A=
1-y
2.2. Optimization preliminaries
We proceed with several basic definitions before concluding the setup.
5

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Definition 3 (Lipschitz Gradient). We say function h: Q2 R. Ω IRd has L--Lipschitz gradient or is L-smooth w.r.t norm I|-II if for all x, y 5
In both cases, big-O notation suppresses only constant fac- tors.
To our knowledge, Theorem 1 is the first result to establish best-in-class convergence (at any rate) of PMD without clo- sure conditions. Two additional comments are in order: (1) Our current analysis technique requires the action regular- izer to be smooth. This is also the source of the degraded rate in the negative entropy case. (2) The greedy exploration stems from the smoothness parameter we establish for the value function, and leads to worse rates in the Euclidean case (for negative entropy, it actually implies smoothness of the regularizer, though this is not the primary reason for which it is introduced). We discuss this point further in Section 3.1.
|| vh(y)l,. s ||x yll
Definition 4 (Gradient Dominance), We say f: X - IR satisfies the variational gradient dominance condition with parameters (C..6), 6), or that f is (C., 6)-VD, if here exist constants C., 8 > O, such that for any x X, it holds that:
f(x) - arg min f'(**) s C. max (V fx)xxx x) + xEX
x
Definition 5 (Local Norm). We define a local norm over a set X [ IRd by a mapping x H II-Ilx such that II= is a norm for all x E X. We may denote a local norm by Il-lle) or byx x II-IIx-- Definition 6 (Local Smoothness). We say f: X R is B-locally smooth w.r.t local norm + 11-11x if for all x,y& Ex: X:
Analysis overview. The analysis leading up to Theorem I builds on casting PMD as instance of Bregman proxi- mal point (or equivalently, mirror descent) algorithm. This follows by demonstrating PMD proceeds by optimizing subproblems formed by linear approximations of the value function and a proximity term that adapts to local smooth- ness of the objective, as measured by the norm induced by the current policy occupancy measure.
B < 2 lly xlI2.
156) (0x)
3. Best-in-class Convergence of Policy Mirror Descent
In fact, it has already been previously observed (c.g.. Shani et al., 2020; Xiao, 2022) that the on-policy PMD update step is completely equivalent to mirror descent step w.r.t. the value function gradient equipped with dynami- cally weighted proximity term. For any two policies æ and x* by the policy gradient theorem (Sutton et al., 1999, see also Lemma 15 in Appendix D.1):
In this section, we present our main results which establish convergence rates for the PMD method in the non-complete class setting we consider. Our main theorem, given below, provides convergence rates for two classic instantiations of PMD; with Euclidean regularization and negative entropy regularization. Our results require that e-greedy exploration be incorporated into the policy class. To that end, let I1e denote the policy class obtained by adding e-greedy explo- ration to II:
-
Ex-pa 11 (et.
+ BR (B(
11
= -(VV(x"). x)+ - B (I, ,²),
(6)
II {(1 -)xx + eu | E II), where us I/A.
17
We have the following.
where we denote j = p @* = Q* and B (u. v) = Es-ga (R(,, However, these prior observations did not yield new convergence results, as the algorithm in question significantly deviates from a standard instantiation of mirror descent; priori, it is unclear how the regularizer associated with B relates to the objective in optimization terms.
Theorem Let II C A(A)S be convex and assume it (C., VVD w.r.t M. Consider the on-policy PMD method Algorithm I when run over II fep Then, assuming Eact Scri I Eas, and with proper tuning of nJ Eexpl, it holds that:
The high level components of our analysis are outlined next. In Section 3.1 we establish local smoothness of the value function (Lemma 2), which the key element in es- tablishing convergence of PMD through a proximal point algorithm perspective. Then, in Section 3.2 we introduce the optimization setup that accommodates proximal point methods that adapt to local smoothness of the objective, and present the convergence guarantees for this class of algorithms. Finally, we return to prove Theorem in Ap- pendix D.3, where we apply both Lemma 2 and the result of Section 3.2 to establish convergence of PMD.
i. If R(p) = 1 11112 is the Euclidean action-regularizer. we have (TT*) -IT
12
0
+ AHP V + Evgd
K213
i. If R(p)= = Ei pi log pi is the negative entropy action- regularizer, we have (xx)) - (I)
0
K2/7 + (C.H+ Λ²H2k417)
Vessa + Eyga
6

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
3.1. Local smoothness of the value function
3.2. Digression: for locally smooth objectives
Constrained non-convex optimization
The principal element of our approach builds on smoothness of the value function w.r.t the local norm induced by the occupancy measure of the policy which we take the linear approximation, given by the below lemma. We defer the proof to Appendix D.2.
In this section, consider the constrained optimization problem:
min f(x), x
Lemma 2. Let π: S - A(H) be any policy such that = mins,a {T > 0. Then, for any it E AA),, we have:
where the decision set E Rd is convex and endowed with local norm x II-llx (see Definition 5), and f is differ- entiable over an open domain that contains X. We assume access to the objective is granted through an approximate first order oracle, as defined next.
IV( V(x) (VV(T),
x)1
Assumption 3. We have first order access to f through an Ey appppooxee gradient oracle; For all x E X, we have
H
AH3 Ve || x x
S min
Ve || π||
(1(
& S
It is instructive to consider Lemma 2 in the context of the more standard non-weighted L.2 smoothness property estab- lished in Agarwal et al. (2021).
Theorem 3 given below establishes convergence rates for the
algorithm we describe next. Given an initialization X1 E X, learning rate rj > O, and local regularizer R₃: It - R for all x E X, iterate for II....,. K:
Dependence on S: The standard L smoothness leads rates that scale with ||r| - -x*1l2- which scales with S in general. Indeed, prior works that exploit smoothness of the value function (e.g.. Agarwal et al., 2021; Xiao, 2022) derive bounds for PGD (i.e., mirror descent with non-local, euclidean regularization) that do in fact hold the setting we consider here, but inevitably lead to convergence rates that scale with the cardinality of the state-space. This is while the diameter assigned to the decision set II by ( for any π, depends only on the diameter assigned to A(H) by II-Ilo, and thus is independent of S.
X6+1 arg min yeX
(8)
The above algorithm can be viewed either a mirror descent algorithm (Nemirovskij & Yudin, 1983; Beck & Teboulle, 2003) or a proximal point algorithm (Rockafellar, 1976) in a non-Fuctidean setup (see Teboulle, 2018 for a review), where the non-smooth term is the decision set indi- cator function. Our analysis (detailed Appendix E) hinges descent property of the algorithm, thus naturally takes the proximal point perspective. We prove the following.
Theorem 3. Suppose that f is (Cx, Evgd)-VGD as per Def- inition 4, and that f == min f(x) > -00. Assume further that:
The standard 2 smoothness does not naturally integrate with the PMD framework, and leads to algorithms (such as vanilla projected gradient descent) where the update step cannot be framed as a solution stochastic optimization problem induced by some policy occupancy measure. As such, these do not admit formulation that is easily implemented in practical applications.
Relation to PMD:
(i) The local regularizer R₂ is 1-strongly convex and has an L-Lipschitz gradient w.r.. I1-1lx all x E X.
(i) For all x E X. maxu.vex I|u - vllx s D, and [[V s M.
(iii) f is B-locally smooth w.r.t. x x 11-11x-
Then, assuming k+1 are Eopt approxipoyi optimal (in the same sense of Assumption 1), the proximal point algorithm Equation (8) has the following guarantee when nj S 1/(2B):
Smoothness parameter: The smoothness parameter in Lemma 2 depends on the minimum action probability assigned by the policy at which we linearize the value function (and as we discuss in Appendix B.2, this is not an artifact of our analysis). A simple resolution for this is given by adding e-greedy exploration. Notably, the relatively large ((1/Ve) smoothness constant ultimately leads to rate that is worse than the (1//) achievable with the standard 2 smoothness (but that crucially, does not scale with S).
C21.22 n₁K
f(xK1) -
Eerr + Exgd
where C1 = D) 11 and
E = (C.D+ c1 E CxEope + c1 Eopp//
where C1 = 1) n.M.
7

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
The proof of Theorem 3 well as additional technical details for this section provided in Appendix E.
where second inequality follows from Lemma 12 and the inequality from Assumption 2. Further:
3.3. Proof of main result
By a simple relation (Lemma 13) between R and the state-action it regularizer it induces defined below,
To prove our main result, we begin with lemma that essen- tially "maps" the PMD setup into the optimization frame- work of Section 3.2. The proof consists of showing that the appropriate assumptions on actor, critic, and action regu- larizer translate to the conditions of Theorem 3 for locally smooth optimization.
R (TT) Ex-yx
we have that (+,) is the Bregman divergence of R and further using (i) that Rx* is I-strongly convex and has an L--Lipschitz gradient w.r.t. || (l
Lemma 4. Let II be a convex policy class that is (C., Evga)- VGD w.r.. the MDP M. Consider the on-policy PMD method Algorithm 1, and assume that the following con- ditions hold:
2. For all n. A. by (ii),
| Alle VEs-yn l| # D.
(i) R: R - R is 1-strongly convex and has an L- Lipschitz gradient w.r.t an action-space norm I1-
In addition by (ii) and the dual norm expression (Lemma 12), for any x::
(ii) max () llp - all. s D. and |0,511. s M for all E L.S.x M II.
|V H 11 ( = = (112 s HM.
(iii) The value function is B-locally smooth over II w.r.t the local norm |l-||x == (1-1)==
Then, we have the following guarantee:
Finally, the objective is B-locally smooth by assump- tion (iii).
C. C.
- =
+ Estat + Evgd
n
The result now follows from Theorem 3.
where 0i = = DDD+nHM, and
Estat = (C.D+c1L3) cIL?) H V Ca + C1 LLL/eaann
We conclude with a proof sketch of Theorem for the Euclidean case; the full technical details are provided in Appendix D.3.
For μ E Q E SA we define the state to late-nction element-wise product l Q SA by (H a 2),aa (s.) Observe that for all k, it holds that
Proof sketch of Theorem I (Fuclidean case). The first step is showing that the -ree-yg exploration introduces an error term that scales with == Eesp1 H²² (see Lemma 19). This implies that fespl (C.. + 5)-VGD w.r.t M. In addition, by definition of 1[ we have min,,a {Tr.a) 2 Eexpl/ A for all πI Feepl We now argue the following:
Es-yp H (et,
- BR(( " = -(v((T)).)) .7)+ B Ba (7,
with: B Ba (T) = (R Rs), PV(T) Hp* @ Next, we demonstrate PMD is instance of the op- timization algorithm Equation (8), and verify that all of the conditions in Theorem 3 hold w.r.t. the local norm π + |1=1 First, to see that the gradient error is bounded by H VErn. observe:
1. The action regularizer R(p) llll2 is I-strongly convex and has I-Lipschitz gradient w.r.t 11-112-
2. Vs, I|TT, f,ll2 D 2, 112.112 s M VAH.
(5(())- VV(T) (
= =||u" (Q- (0= Meree
3. By Lemma 2, the value function is (B=
13/2 Vongl
locally smooth w.r.t π + 11-1112000)22
Ex-po (10--00=1
The result now follows from Lemma with = 1/(28) and Eepp K 2233
5 Veerit
8

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
4. Conclusions and Outlook
Impact Statement
In this work, we introduced a novel theoretical framework and established best-in-class convergence of PMD for gen- eral policy classes, subject to an algorithm independent vari- ational gradient dominance condition instead of a closure condition. In addition, we discussed the relation between VGD and closure thoroughly, and demonstrated closure implies VGD but not the other way around (Section 1.2 and Appendix A). We conclude by outlining two directions for valuable (in our view) future research.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
e-greedy exploration. Our approach builds on ensuring descent on each iteration, which we establish by demon- strating local smoothness holds globally, for any refer- ence policy æ. As we discuss in Appendix B.2, seems that this technique cannot yield better results. However, is bounded,
Alfano, C. and Rebeschini, P. Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209. 15382, 2022.
Alfano, C., Yuan, R., and Rebeschini, P. A novel framework for policy mirror descent with general parameterization and linear convergence. Advances in Neural Information Processing Systems, 36:30681-333 1-0022,, 2023.
when the multiplicative ratio / arguments similar to those given in Appendix D.2 demon- strate a somewhat weaker notion of smoothness but without dependence on the exploration parameter. Fur- thermore, an analysis approach that combines with the classic mirror descent analysis might do without the per iteration descent property.
Bauschke, H. H., Bolte, J., and Teboulle, M. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Op- erations Research, 42(2):330-344 2017.
Beck, A. First-order methods in optimization. SIAM, 2017.
Non-smooth action regularizers. Our approach encoun- ters an obstacle that seems related to existing techniques for non-convex, non-Euclidcan proximal point methods, which leads to the requirement of a smooth regularizer. This is also the source of the degraded rate in the negative entropy case. Progress can be made by either advancing state-of-the-art in this area of optimization (or showing the limitation is inherent to the setup), or alternatively exploiting additional structure specific to the value func- tion.
Beck, A. and Teboulle, M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Bhandari, J. and Russo, D.
On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pp. 2386-2394. PMLR, 2021.
Bhandari, J. and Russo, D. Global optimality guarantees for policy gradient methods. Operations Research, 2024.
Acknowledgements
Cayci, S., He, N., and Srikant, R. Convergence of entropy- regularized natural policy gradient with linear function approximation. SIAM Journal on Optimization, 34(3): 2729-2755 2024.
This project has received funding from the European Re- search Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreements No. 101078075; 882396). Views and opinions expressed are however those of the author(s) only and do not neces- sarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant numbers 3174/23; 1357/24), and a grant from the Tel Aviv University Center for AI and Data Science (TAD). This work was partially supported by the Deutsch Foundation.
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4): 2563-2578, 2022.
Chen, J. and Jiang, N. information-thcorett considerations in batch reinforcement learning. In International Con- ference on Machine Learning. pp. 1042-1051. PMLR, 2019.

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Epasto, A., Mahdian, M., Mirrokni, V., and Zampetakis, tradeoffs for soft-
Lan, G. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and gen- eralized problem classes. Mathematical programming, 198(1):1059-110) 2023.
E. Optimal approximation-smooohnee max functions. Advances in Neural Information Process- ing Systems, 33:265 1 1-2660, 2020.
Even-Dar, E., Kakade, S. M., and Mansour, Y. Online markov decision processes. Mathematics of Operations Research, 34(3):726-736, 2009.
Lillicrap, T. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.0299 2015.
Liu, B., Cai, Q. Yang, Z., and Wang. Z. Neural trust region/proximal policy optimization attains globally opti- mal policy. Advances in neural information processing systems, 32, 2019.
Fatkhullin, I. and He, N. Taming nonconvex stochastic mir- ror descent with general bregman divergence. In Interna- tional Conference on Artificial Intelligence and Statistics, PMLR, 2024.
pp.
Liu, Y., Zhang, K., Basar, T., and Yin, W. An improved analysis of Ivariance-reduced policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636, 2020.
Geist, M., Scherrer, B., and Pietquin, O. A theory of regu- larized markov decision processes. In International Con- ference on Machine Learning, pp. 2160-2169. PMLR, 2019.
Lu, H., Freund, R. M., and Nesterov, Relatively smooth convex optimization by first-order methods, and appli- cations. SIAM Journal on Optimization, 28(1)3333-35, 2018.
Ghadimi, S., Lan, G., and Zhang, H. Mini-batch stochastic approximation methods for nonconvex stochastic com- posite optimization. Matematical Programming, 155(1): 267-305, 2016.
Grudzien, J., De Witt, C. A. S., and Foerster, J. Mirror learning: unifying framework of policy optimisation. In International Conference on Machine Learning, pp- 2824.7844. PMLR, 2022.
McSherry, F. and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 94- 103. IEEE, 2007.
Hiriart-Urutty J.-B. and Lemaréchal, C. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. On the global convergence rates of softmax policy gradient methods. In International conference on machine learn- PMLR, 2020.
ing, pp.
Johnson, E., Pike-Burke, C., and Rebeschini, Optimal convergence rate for exact policy mirror descent in dis- counted markov decision processes. Advances in Neural Information Processing Systems,
Mei, J., Gao, Y., Dai, B., Szepesvari, C., and Schuurmans, D. Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, pp. 7555-7564. PMLR, 2021.
2023.
Ju, C. and Lan, G. Policy optimization over general state and action spaces, arXiv preprint arXiv:2211.167155 2022.
Mu, S. and Klabjan, D. On the second-order convergence of biased policy gradient algorithms. In Forty-first Inter- national Conference Machine Learning, 2024.
Kakade, S. and Langford, J. Approximately optimal ap-
proximate reinforcement learning, In Proceedings of the Nineteenth International Conference on Machine Learn- ing. pp. 267-274, 2002.
Munos, R. and Szepesvári, C. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9 (5), 2008
Kakade, S. M. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Nemirovskij, S. and Yudin, D. B. Problem complexity and method efficiency in optimization, 1983.
Khodadadian, S., Jhunjhunwala, P. R., Varma, S. M., and Maguluri, S. T. On the linear convergence of natural policy gradient algorithm. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 3794-3799. IEFF, 2021.
Nesterov, Y. Gradient methods for minimizing composite
functions. Mathematical programmingg 140(1):125-161, 2013.
Khodadadian, S., Jhunjhunwala, P. R., Varma, S. M., and Maguluri, S. T. On linear and super-linear convergence of natural policy gradient algorithm. Systems & Control Letters, 164: 1042105444, 2022.
Peters, J. and Schaal, S. Policy gradient methods for robotics. In 2006 IEFE/RSJ international conference on intelligent robots and systems, pp. 2219-2225. IEEE, 2006.
10

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Peters, J. and Schaal, S. Reinforcement learning of motor skills with policy gradients. Neural networks, 21(4))682- 697, 2008.
Yuan, R., Gower, R. M., and Lazaric, A. A general sample complexity analysis of vanilla policy gradient. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 3332-3380. PMLR, 2022.
Rockafellar, R. T. Monotone operators and the proximal point algorithm. SIAM journal on control and optimiza- tion, 14(5):877-898, 1976.
Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., and Xiao, L. Linear convergence of natural policy gradient meth- ods with log-linear policies. In The Eleventh Interna- tional Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https:: /ttppeee//peeeevieew forum? id= z 9hdsyUWVQ.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and
Zanette, A. When is realizability sufficient for off- reinforcement learning? In International Conference on Machine Learning, pp.
Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: (XX7:0777700447 2017.
PMLR, 2023.
Shani, L., Efroni, Y., and Mannor, S. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Con- ference on Artificial Intelligence, pp. 5668-5675, 2020.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989 PMLR, 2020.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, D., and Chi, Y. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear conver- gence. SIAM Journal on Optimization, 13(2):1061-109) 2023.
Teboulle, M. A simplified view of first order methods for optimization. Mathematical Programming, 170(1):67-96, 2018.
Zhang, K., Koppel, A., Zhu, H., and Basar, T. Global con- vergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimiza- tion, (886))3386-36111 2020.
Tomar, M., Shani, L., Efroni, Y., and Ghavamzadeh, M. Mirror descent policy optimization. arXiv preprint arXiv:2005.098// 2020.
Zhang, S. and He, N. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint arXiv: /806.00488 2018.
Tseng. P. Approximation accuracy, gradient methods, and error bound for structured convex optimization. Mathe- matical Programming. 125(2):263-29) 295, 2010.
Vaswani, S., Bachem, O., Totaro, S., Müller, R., Garg, S., Geist, M., Machado, M. C., Samuel Castro, P., and Le Roux, N. A general class of surrogate functions for stable and efficient reinforcement learning. In Proceed- ings of The 25th International Conference on Artificial Intelligence and Statistics, 2022.
Wang, L.. Cai, Q. Yang, Z., and Wang, Neural pol- icy gradient methods: Global optimality and rates of convergence. In International Conference Leurning Representations. 2020.
Xiao, I. On the convergence rates of policy gradient meth- ods. Journal of Machine Learning Research, 23(282): 1 1-36, 2022.
Xiong, Z., Fazel, M., and Xiao, L. Dual approximation policy optimization. arXiv preprint arXiv:2410.01249, 2024.

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
A. Variational Gradient Dominance and Closure Conditions
In this section, we include detailed discussions regarding the VGD and closure conditions. In Appendix A.I, we demonstrate closure = VGD; In Appendix A.3, we show that VGD # closure we present a simple example where VGD holds, but closure doesn't t and furthermore that bounds of prior works fail to capture convergence of PMD; Finally, in Appendix A.4, conclude with several general remarks.
A.1. Closure implies VGD
In this section, we provide formal proofs that closure conditions employed by prior works imply the VGD condition. Throughout this section, in favor of a simpler comparison, we assume the critic and actor errors zero, i.e., all algorithms have access to exact action-value functions, and Eact = 0. We introduce the following, slightly extended version of the VGD condition.
Definition 7. We say policy class II satisfies (C., Evgdi -VVGD if for all x E II:
V(x) v* C. max (VV(x), At Eugd-
Rell
The above extension of the VGD assumption enables a clearer comparison with prior works. As closure implies (approximate) realizability, prior works obtain bounds w.r.t. the optimal (potentially out-of-class) value function V min miinxeai,0p> V(z). Our original VGD condition Definition is stated with the reasonable v* (II) choice, however our bounds hold just the same under the assumption VGD holds for other y* (such as v* V*).
As we show next, both Yuan et al. (2023) (see Lemma 6) and Alfano et al. (2023) (see Lemma 8) adopt assumptions that imply their policy classes satisfy Definition 7 with suitable parameters Ca, and y* = V* Notably, the error floors in their convergence results are indeed precisely (up to constant factors) Eygd- We note the implication we establish is not "perfect", make the argument we need slight variations of the original algorithm dependent conditions our goal here to highlight the strong relation between the two assumptions. Before proceeding, specifically note the following:
(see
To simplify presentation, we consider closure assumptions (bounded approximation error, concentrability, and distribu- tion mismatch) globally, rather than on the specific iterates selected by the algorithm. However, the same arguments can be made iterate specific, which would lead VGD conditions on the specific iterates, which is indeed all that is required by our analyses.
The concentrability assumptions employed by Yuan et al. (2023); Alfano et al. (2023) relate to the current policy x² and the next one = The direct global extension of this condition would concern a policy æ and a policy x² selected by a step of the algorithm with the given step size and regularizer. Our proof requires x² to be selected differently (e.g.. with a different step size choice), which leads to a concentrability assumption that relates to a different x²* than the original ones. In this sense, the assumption we make here is a different one, but still qualitatively similar. Again, to simplify presentation we assume stronger concentrability in the lemma statements where x² may be arbitrary, but this can be relaxed explained above. In addition, current occupancy measure μ² rather than the next one pu This may actually be considered a weaker assumption than the original one, as the next policy is only determined after performing the step that uses v²A Further, we may always simply select , = μ² o x² to obtain optimal support for f.f.
concentrability requires the sampling distribution v to support the
In Lemma 8, we prove that when (the natural extension of) closure assumptions of Alfano al. (2023) hold for Euclidean regularization, VGD holds as well. The claim be extended to other regularizers with the price of additional regularity assumptions. Regardless, the bounded approximation error assumption of Alfano et al. (2023) may alternatively be interpreted as bound on the statistical error, in which case the policy class operated over is (v+, 0; VVGDV we provide further details in Appendix A.2.
The work of Bhandari & Russo (2024) demonstrated that closure policy improvement implies VGD, and further observed there is also connection between bounded approximation error and VGD (Lemma 16, Appendix B in their work). The arguments we give below may be considered generalization of those in Bhandari & Russo (2024), strengthening the connection between closure and VGD.
I We refer to their results based on bounded approximation error.
12

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Lemma 5 (Generic closure VGD). Let IT be a policy class, π II a policy, and A(S x R) a state-action probability measure. Suppose there exists x² e II such that:
Ex-pa (0t.
S Ex-pu min 2. Egroody.
where Es,a-v 1 - -2 )2
S Eapprox
and further:
p(ss)as.a 2
E 5
$ CC,,
(u-concentrability)
v(s,a)
For i E ",, fi where x= arg min TEMASS V(x), p² = n²* Then, it holds that
4* 11
V(T) V*
max (VV(*), x - REll
Egready + 4 CuEpropr
Proof. We first establish bounds on approximation error terms, then proceed to leverage the approximate greedification assumption to establish VGD.
Approximation error.
For any policy and state-occupancy Jr, we have:
Ex-p (0: 2T. at.
-0000 -0 @
2^ (20)) || a alliz(n) $ Eapprex ll l (2(2))
where the last inequality is by our assumption. Further, by y-concentrability,
A(s)
|l o Alli)()) = -VE
s VC.
u()
holds for ă x,,xt.n xT) "*) tHt , Now, for such μi, A, have:
Es-p (0r -Z, n, - As) s Es-p (er - -ē. @..,,.) )/+ Es-p (e: - - (g.5)))) s 2 CyEapprox
therefore,
Ex-wa 1, - Œ,- n, x²)
$ $2 C.E
Ex-pp* (er - ē,. n. x;²
s 22
Greedification. Observe,
Ex-pa (e, nT n²¹) = Es-yr (ūr xx² Es-px (0:- -5. F4 nT¹
2 Es-ur max (ō:- Rr - -P) Egrcody 2 CaEpprox
- Ey-gr max (ō.- p) s Es-pu (e, R, πτt) + Egreedy + 2 C
13

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Therefore, by Lemma 14 (value difference),
(V(z) V*)= Ex-pe (25 Rss -x5))
= Ex-pu* (25 RT - ,τ² + (0: - 2 Rs x3z
Ex-pr
max 5 Es-u pEA(A)
(@:- (e.,TT
TPp -p) + 22
Ex-ne max PEA(A))
055 Rs p) 2 CyEppprox
Ex-pr (0 nT, - ==²)) +
Egreedy + 2 Cr Eappeoxx
2 Eappppoox
Ex-pa (0 nT - =2²)
Egroedy + 4 Cy Eapprox
(VV(T), x²)
Egreedy 4v Eappros
max (VV 12)
Egreedy + 44 EyC
11
Fell
which completes the proof after multiplying by H.
Lemma 6 (Log-linear dual closure = VGD). Let
E Ied be state-action feature vectors, and let II be the
log-linear policy class II {x(0) E [ where
exp(oT,a))
(0) = Ed'eg exp(o)
Assume further that for all π E II it holds that
(ww Øs,a - ei,al 21 S Epppeox
min (s,a-((5Ox)
w
and,
Vx-
and,
h Cr.
Ex.a-(utox)
where h represents ā for all n. (n²,"²), )²), and we denote x²* arg min TEA(AYS V(T), = = Then II satisfies (v..5v.HH /f V*>-VGD (Definition 7).
Proof. Let π E II, and denote Ø. $J.a T where
w = arg min Ex.a-(xoox)) ((v [iTT ts.a -aaa--,ral 2,ra)
By Lemma 7, the policy x² == x(6t) Il defined by Ø+ = (log(d)/ Egreedy) w satisfies
Vs (0: ( & min 2.-- + Egreddy-
Now, by the above and our assumptions, we are in the position to apply Lemma 5, which immediately implics the desired for Egreedy Capappo
14

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Lemma (MMcSherry & Talwar, 2007; Epasto al., 2020)). Let oy R. Then if (log d)/6, holds that
e Σ TMi
minx, +
Proof. We have
Ei e Txe
e Eie-xi (-xxx
minx; = max (-x:}
Σ, TT
Mi e
The result now follows from the original statement, which says that for any Z1...... 2n R.
E max E1 E Sd. 6.
Next, we provide a proof for closure conditions of Alfano et al. (2023) in the case of regularizer with bounded Bregman divergence, which simplifies some technical issues and is sufficient for the Euclidean case. The implication can be shown to hold more generally subject to some additional regularity conditions on the policy class. We note that such general version of the lemma would in particular imply Lemma 6, thus rendering the above proof redundant. However, we opted for an independent proof of Lemma avoid the additional regularity assumptions.
Lemma (Generic dual closure = VGD). Let II c MAYS be a policy class, and R: RA B. an action regularizer. For any policy let 17 > 0 be a chosen step size and be a chosen state-action catt-accioon probability measure. Define
|- (1--)))R())) - 2*) 1
s (T. n)) = arg min /EF
π = = PR(n
where PR(nf)s Men (VR((1fs)) Assume that:
||- (VR(T)- -2a))
Sapprox
(AI)
for "xxxtxx)) r. f E (u². )
A 2
s
$ CCp
(A2)
v(s,a)
and finally.
sup (s) μ (s)
V+-
(A3)
Then, R has a bounded Bregman divergence, maXp.gea(<) BR(p,q), q). and the above holds for any n, it holds that II satifies (y.. VVv. Eappppos V*)) VVG (Definition 7).
Proof. Fix I1 and define
@a = (VR(T)) ft = f* - ( (V(()) - Ō",
which implies that:
Vs, x.- =ag min 2,- p) + (p( xT)
pEA(TT)
15

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
We have:
|ee -- (2())
= =||5- -1 VR(() - -2*) 12(0))
@approx
and for = B/ Egreddy by Lemma 9:
Vs. ( x3) min Q5 + Egreedy.
Choosing Egreedy VC the result follows by Lemma 5.
Lemma' 9. Let e > 0, R: R R be a convex regularizer with bounded Bregman divergence B 2 maxp. (p(p,q). and & R be a linear objective, with a* = arg min, 8a. Then, for any x AAA),, for nj 2 B/c, we have:
x min (g.2)+ + 1 (Ba(co)) = 8(x*) s Sa +e. =E((A)
11
Proof. By optimality of x²:
8(x*) s g(ea)) BR(ear,))- BR(xtxx)
$ 8a + B/n
Su E,
and the result follows.
A.2. Closure without convexity
In this section, we explain how the approximate closure conditions of Alfano et al. (2023) eliminate the need for convexity of IT in our analysis. Roughly speaking, closure conditions imply approximate optimality conditions hold for the PMD iterates w.r.t. the complete policy class. And, our analysis, we obtain guarantees w.r.t. the policy class the PMD iterates satisfy optimality conditions with respect to, regardless of actual policy class the algorithm operates over. To make the argument formal, consider the following assumption, which characterizes the behavior of the algorithm in relation "ambient" policy class II.
Assumption 4 (PMD w.r.t. ambient IT). For II policy class, and ,'...., ........e K+1 is sequence of policies, it holds that:
1. ÎT is convex.
2. Î satisfies (C., Evgdi V")- the iterates π² ..... K+l,
v(**) v* I C. max (VV(**),x* - #) Evgd
#cll
3. n² ......,. x K+1 satisfy PMD approximate optimality conditions w.r.t IT':
VI E ÎT' (Vox(*+*)) k+l ), xt1) 2 Eacts
where ( = Ex-pu (eet ( + (x(Ts,
We note that PMD algorithm does not necessarily need access to ΠI to satisfy Assumption 4. In particular, it may be that the algorithm operates over non-convex II, but satisfies Assumption 4 with îl = IT' A(A) Next, we restate our guarantees for the Euclidean case reframed in the context of Assumption 4, and then proceed to demonstrate assumptions of Alfano et al. (2023) imply Assumption 4.
Theorem (Restatement of Theorem 1; Euclidean case). Let πl c A be policy class and suppose x², _ K+1 is sequence of policies for which Assumption 4 holds with IT' Sepe R(p) = 11 and 17, Eexpl properly tuned. Then, it holds that:
CAARH
v(**) - --==
+ (C.H+ AHPx1/6) V Evgd
K2/3
16

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
To establish the next lemma, we interpret the colure conditions of Alfano al. (2023) as perfect closure, where Supprox bounds the actor error, rather than relating to expressivity of the dual policy parametrization.
Lemma 10. Suppose that for all E [K].
| (17 (R(TT) -
-2*) "*
S Eupproxx
(AI)
and k+] = =PR(1f where PR(nf)s = =I M(a)
(nfs)). Suppose further that for all k,
H (s) sup (*((s)
S Vx-
(A3)
Then, with the choice of = jet o u, i.e. s, ~ wk
ut= Un) we have that Assumption 4 is satisfied with N1 = IT' = A(H)S, 1* = V*, C. = Vx. Eugd = O, and Eact s 2 Aupppro-
Proof. Let cktl= = pkttl - (17 ((((t) - 2*) Then || (122 L2((k) Eapprox: and
phtl (((()) (0t + ghtl).
Now by definition of xz k+1
n, k+1 arg min (e: + cktl .Ts)) + - BB (T
n, ((
hence, by optimality conditions, for any E A(A)S:
- rkt -
- -VR(x))) .ns -x(ttl 2
17
e (VR(T)=))- - ((())))))))))))))))))))))))))-) xxttt
(rtt1 , a3)
17
Now, note that
E Ex-at (getl Re ntg (ur o ,ktl,zktt1 - x²)
I|kt ghtilli (122 1 1p x|| x1112108)22
s 2 (Es ||
Further, by the choice of y² = 1et
Ex-pe 1kxtt112-
E, Ex-ue
Σ
pk+1 Ss.a
= AEE-pt
Σ
ck+1 Sx,a
A 1|
A
nE A
Therefore, for all π E A(H)S:
Eg-ga (ot + 17
1 (VR(r++))-VR(()) TT x
-
with Eact S A Finally, the complete class satisfies (y* O)+GG) on the x² iterates by Lemma 16, with y* in place of Hvo owed to our assumption (A3).
Finally, we note that we could have traded the dependence on the action set with an additional concentrability assumption.
17

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
So
(c)
(1)
S1
S2
Figure I: A simple MDP with convex value landscape. Each action represented by a (fcature-vector, edge) pair leads deterministically to the state at the other end of the edge. The two outer bold edges labeled inflict cost of 1, the others have cost 0.
A.3. VGD does not imply closure
In this section, present sinple example where the VGD condition holds but closure does not, and result existing analyses fail to establish convergence of PMD. We note that the fact that VGD does not imply closure is immediate, as closure implies realizability but VGD does not. We go further here to show that the bounds of prior works may indeed become vacuous in setups where VGD holds and closure does not. We consider the MDP depicted in Figure I with the log-linear policy class II induced by the state-action feature vectors shown the diagram.
For simplicity we assume there are no statistical errors the execution of the algorithm (Estat 0). this example the value landscape is convex (in state-action space) over II, and thus (1, O)-VG and convergence PMD follows by our main theorem:
v(n min V(r*)
K-o0 0.
xtell
At the same time, results based on closure imply convergence to an error floor that is larger than H. For instance, by Theorem 1 of Yuan et al. (2023) establishes that:
1 -
v(x*) - min V(r*) s 2H
+2Hvov A
(9)
meaning:
v(x*) - min V(x*)
2Hvo v ACoobias 2 10H,
xtell
K-000
where Ebias 2(11, H² and Co is certain concentrability coefficient larger than 1. Here, both the transfer error and approximation eтror are ()bbia)) A rigorous analysis is given below in Appendix A.3.1. Recent papers such Alfano et al. (2023); Xiong et al. (2024) accommodate more general policy parameterizations but still include the log-linear setup as a special case (see discussion in Alfano et al., 2023 and Appendix F). The error floor in their results is also larger than H for the example in question for exactly the same reasons; their results depend on the approximation error, which for this example as mentioned behaves the same the transfer error.
Finally, we note that the example is not realizable and the discussion focuses best-in class convergence the objective. If we were to look for convergence w.r.t. the true optimal policy, our Theorem establishes convergence to emror floor of V(II*) - V* H /2, while closure based analyses suffer from the same 2 H error floor. In all that follows, we focus on the transfer error : the argument for the approximation error is the same.
1. ANALYSIS
We denote the actions:
0
18

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
and the state-action features, for all s:
s,, = (/)
$s,2 == [1]. 0, = (0x11)0))=)(113 E R2x2
In favor of conciseness, we will let
11, = US....
For 0 E R2, we denote the log-linear policy N² == (), (), where or is the softmax function:
e
(u)) Enen
This gives rise to the log-linear policy class:
II == {TT 10 RR)
Since such policy x² in this MDP must select actions independent of the state, we let a denote the probability it chooses and - a the probability it chooses b; a = xf. = a = -, Now, denote V," == Vs, (r²), Qi. = Q5 and observe that by direct computation:
Vo(o) (1 - ()(1+))
a (1- ))) =: H (1(22== (1 =
Vi(a) a yH a² (1-a)2)
V2((r) = (1 - 0) + x2 (1 11)2)
and,
2o yVi(a),
20, vV2(a);
6 = + yVo(a),
Ui, yVo(a);
0 yVo(a),
25 + yVo(a).
Let (SO) 1- (SP) = PS( = p/2 for some
[0. l). Then
V(a)= (1 - p + H 0² + (1 - -a)² p/2.
(o²
The VGD condition holds. is not hard to verify the value function convex (in state-action space) over this policy class. Indeed, we have
( V Va.V(TT)), x xx)= ova
da (ā ar),
and therefore convexity of ya w.r.t. implies convexity in the direct parametrization over II. Hence in particular, II is (1, 0)-VG w.r.t. the MDP in question. Thus, convergence of PMD follows by Theorem 1, which in this case guarantees the sub-optimality of ,x tends to 0 as K grows (since there is no error floor).
Closure does not hold, and the error floor in closure based analyses is 1| T-y Let n² = = then
(S,) (1 (1
1-p+yH
1+y
(1 (1+y)H
(*(()) (1-y)p+ (So)
(S2) (1 -11p)p+++ y(1 a1 (So).
19

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
is immediate that the optimal in-class policy is given by 8 (1, 1), a² =1/2, and satisfies,
1 1-p+ (S1) 2 (S2) H p 1 (So)
p
(1 (1+
+ 2
Now suppose that y 2 0.99 and p $ 1/100, then by direct computation,
1
( x 2' μ (S1) = 4' (52) x 4'
where the approximation is correct up error of 1/100. Recall that for policy x (8), in the NPG update step (Agarwal et al., 2021; Yuan et al., 2023)
(R) == arg min E aamt (10 (0ha SEal )
Meanwhile, by definition
(oT ( -
(K)
2x 121
Cbia
Ex-Wu* Ex-pta--nii(T ())
(w1 - 2 0t.ma) )
arg min Ex-px*
(2 (wi---y0) >VV1(((())2++ 1 + 11 (w1 - -Vo(a)2
arg min
Wi
arg min {(W1- - (-Vo---)o))+++ + (wi->Vo(a))
W1
32
Now the bias term in Equation (9) is at least as large as
1
H
PO
Venias
H 11- 2
p 1V32
32
10H.
A.4. Additional Remarks
In this section we include several additional points for consideration regarding closure and VGD conditions.
On-policy PMD is prone to local optima. The necessity of some structural assumption (whether VGD closure) is motivated in the introduction by the fact that policy gradient methods over non-complete policy classes II # ((A) are prone to local optima (Bhandari & Russo, 2024). While PMD and vanilla policy gradients are not the same algorithm, the example given in Bhandari & Russo (2024) (Example 1) also applies to PMD with Euclidean regularization, as we explain next. A vanilla policy gradient update in the direct parametrization case equivalent to:
k+1 arg min xell
Eg-px [(et, nT)] + 277 || , 11
which is "unweighted regularization" version of Euclidean PMD. While this is equivalent PMD for A(A)S (in the error free case), it is indeed not equivalent in general. However, Example 1 of Bhandari & Russo (2024) indeed also applies to Fuclidean PMD because the policy class in question contains only policies æ such that xT,a Zx for all s, Hence, for any two policies π, E II. ||T, I = || - x for all s', and || - イ 2 = SE || x
2E ||T, -/, Thus, for the example in question the two algorithms are equivalent up to scaling of the step-size by a constant factor.
20

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Closure conditions in practice. Closure conditions (that are based on bounded approximation error) roughly stipulate the policy class is closed to soft policy improvement step. This has flavor that is similar Bellman completeness (Munos& & Szepesvári, 2008; Chen & Jiang, 2019; Zanette et al., 2020; Zanette, 2023), a property of Q-function class that says the class is closed to Bellman backup step. Bellman completeness is widely considered too strong a condition to hold in practice, the reasoning being that increasing capacity of a function class that violates completeness inadvertently introduces new functions for which completeness needs to be satisfied. Therefore, an increase in capacity may actually cause completeness to be further violated. The same can be argued for closure conditions, with one difference being that the complete policy class A(R)$ is naturally closed to any policy improvement step. However, in a large scale environment setting, the complete policy class is typically many orders of magnitude too large be well approximated by realistically sized neural network architectures (at least at the present time).
PMD and VGD from the optimization perspective. Standard arguments from optimization literature are insufficient to establish convergence of PMD with the VGD condition. First, PMD is not an algorithm that has (prior to our work) a formulation within a purely optimization based framework. Second, convergence in a smooth non-convex setting typically scales with the distance to the optimal solution, measured by the norm induced by smoothness of the objective. Prior works that establish convergence of gradient descent type methods (though not of PMD; e.g., Agarwal al., 2021; Bhandari & Russo, 2024; Xiao, 2022) exploit smoothness of the value function w.r.t. the Euclidean norm (established in Agarwal et al., 2021), and as result obtain bounds that scale with the cardinality of the state-space.
Divergence of Policy Iteration. Our setup with the VGD condition is general enough to accommodate examples where the policy iteration algorithm does not converge (the same example we discuss in Appendix A.3 demonstrates this). Here, since the policy class is non-complete, the policy improvement step is performed over the current policy occupancy measure (see Bhandari & Russo, 2024 who introduce this natural adaptation). Arguably, it should not be expected that policy iteration converges for real world, large-scale problems, as it is very "non-regularized" algorithm from an optimization perspective. At the same time, in setups where closure conditions based on bounded approximation error hold, in particular, closure to policy improvement as studied in Bhandari & Russo (2024), the policy iteration algorithm converges at linear rate. Thus it is not immediately clear why should we employ more sophisticated algorithms such as PMD in such settings.
Convergence beyond the VGD condition. Using our framework, it can be shown that PMD converges to a stationary point regardless of any VGD condition; see Appendix E.3.
B. Deferred Discussions
B.1. Assumption on the critic error
Our results can be easily adapted to the (generally weaker) assumption that
Ex-pe 10= - S Ecrit-
(In which case the bounds would depend on Egrit rather than VEeni.) Assumption 2 in its current form simplifies presentation, since it allows working with the weighted 1.2 norm for both smoothness and errors in the gradient approximation. Also noteworthy, when working with the negative entropy regularizer, approximation w.r.t. the llo norm would suffice. Since the statistical errors are not the focus of this work, we make these concessions in favor of a more streamlined and clear presentation.
B.2. Local smoothness of the value function requires greedy exploration
In this section we discuss why the dependence on e the bound of Lemma 2 cannot be improved in general. We consider the MDP in Figure 2, for which we can show Lemma 2 has tight dependence on the e-exploration parameter, Let p E (0, 1/2) and 0- < p. Define:
11,0 1, O,
# = x",
# = 0, #1.0 1.
Idea. Think of much smaller than p. When measuring distance with the local norm || = the large difference || - xi Il? gets little weight: (Si) = e. Meanwhile, the error of the linear approximation behaves like
21

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
ag
So
a 0,0
1 a
a1
0,1 = a
S1
40
a1
1,0 =?
Ti,1 =?
A state deterministic MDP, with (So) Each edge is labeled with action (a {ag, a }) that takes the agent to the state the other end. A policy x², a e [0. 1] takes actions in So with probabilities displayed in the diagram next the relevant action. The probabilities л² assigns to actions in Si denoted by are unrelated to a and left for later.
Figure 2:
(see proof of Lemma 2 in Appendix D.2):
Σ (s) Σ (xxa asa) Σ 11 (5') [| - -2:-11 1.1ll
where the weight assigned || xi +illi is approximately (Ho.1 To,1) p Hence, if p².
IV(#) - V(T) (VV(x), x>) = p.
|| x 211 ( = p².
so
[V v(x) (VV())
Ve || 1 =1122000)11
Computations.
The term that is equal to the linearization error, up to constant factors, is the following:
Σ n (s) (Asa - Asa) Σ uu (s') (2 Rt. TTc) ||
Assume 6. By choosing cost function r(s,i) = i s e (Sa. S1). i E (0. 1} we have that for all s,
(0 n. - -x,) = 2(1 rTlll).
hence focus lower bounding
(*) Σ (s) Σ (Asa nsa)
E (5') (1) T3-111
22

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
By direct computation,
YE (1+ -1 (())
(So) 1+ ye
and
1 - molli = =2pp -ll | - π 11 =2.
Thus,
(#0,0 - No.0) Σ (Pn.0('') (s') - asl1i (1 e) - p)lp e -p² +e
(oo.1 1o.1) > M (s') Rslli -.
and further,
Σ (1 - ml,a)
(1 - -x (5)
=0.
We obtain
(+) (5 (p-p²) x p- (p-p2)>p--? p².
Meanwhile,
| - x1 x122 x = 4(p c)2 l+ y1+ = =p-c)²+c
4yE
+
Now,
(VV())))
p p-p² p² (p- 2)-
|| x (2(1
Now, for = pp.p 1/2, obtain
p² (p - 6) + p2- p
p- p²
4p2 4p 4
C. Stath-weighted state-action space: Basic Facts
Given a state probability measure μ E A(S), and an action space norm |l. R - R, we define the induced state-action weighted L norm I1-Ilzewa SA R:
| == (Es-n [lu,lle)
(10)
In addition, for μ RS.Qe RSA, we define the state state-action element-wise product μ RSA
(μ 2s (ss)
(11)
Lemma 11. For any strictly positive measure μ E R.S the dual norm of (1) given by
|kll = / ((s)) (1les ds
(12)
23

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Proof. First denote
23 = arg max (1s, 2x)
U.ER -luull..1
| 2s) and |keill 1.
Now let x E SA be defined by x,
1
u(s) 2g. then
(x, = ʃ
| uss)
25) ds ds= = ʃ m(s) (IIzalli2ass ds.
Now, note that
|411)2())0 f (xss)
1
||=311== = / m(s) (11zs11222 = (x, 2)
1
(s))
hence, for E = x/1x have || (2)). 1, and
(R. / (us) (12zs18) ds.
On the other hand, for any v such that [| 1, we have
(v,2)= = =f
/ (((s) 2s) ds /
/| ([(] [
/ ((s) IIvall (o))lllll / ((s)-1 (1kss1(())))1))) ds
$ S ((s) (1kx ds,
and the proof complete.
Lemma 12. μ E A(S), and consider the state-action norm 11-,0 For any W RSA, we have
|| Wll = VE (IIW+11))
Proof. By Lemma 11,
|| Wll = / (I)))w = Es--p (IIW)I1))?
Lemma 13, Assume h: A - is 1-strongly convex and has L--Lipschitz gradient w.t. II-I]. Let E A(S), and define
(T) = =Er-p[((Ts]]] Then
1. BR, = ( E
2. Ry is 1-strongly convex and has an L-Lipschitz gradient w.r.t 11
Proof. We have
Vs,
R BR, = (T) R₂( - (V), #) =Es-H [R(TT) - R(Ts) (VR(H,), Rz)
ER #t).
24

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Further, 1-strongly convexity follows by
1 C.-gB((xss)) 2 2 Er ||,,- -7,1lo.
and the Lipschitz gradient condition from Lemma 12:
(z) (R 112 (T) = =Ilu (Vh(x,)) -
-VEs- (IIV(TT)) (1()))11))
$ L VVE, Es-y 1|, - xx
|| - x= ==111200)00
which completes the proof.
D. Deferred proofs
D.I. Auxiliary Lemmas
Lemma (Value difference; Kakade Langford, 2002). For any p A(S),
V% (xT)
I s- (2, F.. -ss)
Lemma 15 (Policy gradient theorem; Sutton et al., 1999). For any p A(S),
(VVx(x)),,a 1- 1 (5)
(V),(x),ã-1)) 1- Ex-p (e7 Ai πz))
The following lemma can be found in e.g., (Bhandari & Russo, 2024; Agarwal et al., 2021). The proof below is provided for convenience. Lemma 16. Let II c A(A) Ha == A(A)S and suppose that for any policy π E II, we have
max e'ell
Es-yi (e . xxx)"
max Es-μa (2" x') x'ellan
Then Il is (IIv, eIf2vo)-VGD w.r. M, for vo
Proof. Let x* arg men ren (it). By value difference Lemma 14,
V(x) V(**) = -1Es-p 112 T,, xT)i|
H1 max Ex-px* ((255 .T&s x;y]
x'ella
(4)
H
max Es-wa [10 n, -xT' x'ellal
1
S H
a*
max Esyya [0 TT イī))| + EH
max (VV* π²) cH 4*
x'ell
(o)
H
max (VV" π 2) 2 zell
Pg
25

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
To explain the transitions above, (+) follows by the fact that within the complete policy class we may choose x' to be greedy w.r.t. 2*, which means (e. Rs π;) 0 for all e S. The last transition (s*) follows from the fact that:
4 (s)
1 H
Pr(s, = s Po. = H PD((s) + Σ Pr(s, = s Po. 2 FP((s).
1=0
Lemma 17. For any policy S - A(H), 8,a E A:
2 - 2x = yHHE
s' s
(Q Rx -xx)
Proof. By Lemma 14, we have:
2 2 Prr -
>yHEs-Paa Es (e.
=yH Σ P(s'ls,a) Σ u (5") (Q:r. -
yH Σ
(2 Aly nT.))
Σ EF (5") (5)) R," n.r))
yH -HE Aga -Ty))-
Lemma 18. Let h: A - R be the negative entropy regularizer h(p) = Σ, Pi log pt, and assume Ae (A) M(H) is such that 2 e for all A. (A). Then h has 1/e-Lipschitz gradient w.E.t. |1-I1: over A. (A).
Proof. Let p. Ae (A),, and note,
[V<(p) VI(p)l = [Vv(p)) Vh(ā))l
Let i A, and observe that by the mean value theorem, for some a E [p:.pil.
a log(x)
1
[log(p;) - log( p.) =
|p; Pil
1p: p.l s - 1p: -Pll s -1pp-- +l11
since Pi pi 2
D.2. Proof of Lemma 2
We have, by Lemmas 14 and 15,
| - t - (VV", . x = HHE s (0, R, nT,) - HIE - A, -r,
11 Es- (2 -2, #, R5)1.
26

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Applying Lemma 17 yields,
1 yH
V V -(VV", -(VV",#-
-
Σ (Er--pEa (5 =s7) (Asa asa)
Σ
(s)
(s) Σ (Aso Asal Σ
Eus E (5') At. (f -3ar))
Σ (s) (Asa Asa)
VIr((s) EnE UP (5') (Q5 -1rs)
Σ 1 (s) (Asa - )
Σ (s)
Σ up (5) As
(Cauchy- (Cawahy-Schwarz)
Σ (s) (Asa - )sa)²
Σ u (s)
Σ
HP (s') (Q Rs. -
(Jensen)
3,0
3,4t
Σ net
(s) (s)
1|At - TEll2
Σ
u 1* (S) (6t) Ar. ixx)) xx²)
Isa
s.a
Σ (s) || - x=l12
Σ
Σ
n= (s) (6)) (
xxx))
$ VE
3,a
for E := mins,a {T Now, by the law of total probability (applied on the discounted probability measure μ²);
Σ nd (s) (5) =
Σ
(s so po) (s' 1 Psa)
5,a
3,a
Σ
p a so (0) I so ~ Psa)
5.a
#5 | pp)
= (s")
Combining with our previous inequality, we obtain
YH2
V - va (VV" मे
T>| s
Σ (s) || Toll
(s) (Q As. - )
Ve
2112
Eur(s)) (0 a )
|| x
ve
Further,
E (e
R. - Σ (o<(s)/le111 1 - πx s H| =112200))11
and
Σ (s)) Rs. -x s
Σ (o) - - s AH ş| -x)12(07)22-
v
27

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
The first inequality above gives
yH² Ve
yH3
- v -VV* - x
2 11 Tll2A(17),1 & Ve
1| π T11
which proves the first claim, and the second one
yAI13
YAHI3
V V* (VV* |>
||
21)22 || (1),2
|| x x Ve
Ve
which proves the second and completes the proof.
D.3. Proof of Theorem 1
The theorem makes of the following.
Lemma 19. Assume II is (C., Evga)))) w.r. M, and consider the e-greedy exploratory version of II, II {(I E)π eu x E II}, where Us.a 1/A. Then II is (Cx,6)-VGD with 5 == Exgd + 12C, Ac. Concretely, for any лe IIf, we have:
C. max (VV(T"), - x²) 2 V - V* Ell
Evgd 12eC, H2A.
We now prove our corollary and return to prove the above lemma later in Appendix D.4.
Proof of Theorem I. By Lemma 19, we have that II Smpt is (C., 8)-VGD with ó Eygd 12E C. H.A. Therefore, under the conditions of Theorem 3 and the value difference Lemma 14,
v(***1) v s V(* V* (11 Feol) + | (II - - VTT(
=0 -0(c2L2 C2L3c nn
(C.D+c1LL) H H Ca + c1 Lnj 112 Veac t
where 01 = + nHH. Next we apply Lemma the both cases considered, using the fact that for all π Fiopt, we have
mins.a {Ts.a] 2 Eexpl/A A. In the euclidean case, we argue the following:
1. R is I-strongly convex and has 1-Lipschitz gradient w.r.t. ||-112-
2. Vs, ||x,- Asll2 s D 2. 112 M = VAII.
3. The value function is (B =
H Veoul
locally smooth w.r.t || 11-1222007)2
Hence, C₁ = 0(1,, and Lemma 4 gives:
C² C. (Hii + Eac)) + +n 1/2 Veace aec +
- -orktl)-v*(m s nn
2
V2A
+ C+ (I + Enc)
Eact 6.
VeepiK
Sexpl 1/4
Setting Gexpl = K233 we obtain
122
-
+ C. (H Eac)) AH2 Venc + Euga
K2/3
In the negative-entropy case, have the following.
1. R is 1-strongly convex and has a (a//eep))-Lipschiie gradient w.r.t I|-I1, (by Pinsker's inequality and Lemma 18).
28

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
2. Vs. aT #sll1 D = 11 M 11
3. The value function is (B =
H² VFogl
localll smooth w.r.t (
Hence, = 0(1,, and Lemma 4 gives:
- V*I x
C²A²
+ C+
A? tespl?
H Veern CxEact +
A
Eact + 5
Gexpl 2 2nk
Eexpl V
2/ 11: HI- C²
A2 Eexp!?
A3/2
Cx
HN + Cxt
Sexp1 8/4 V
VEac + 6.
2/2 5/2K
We now set Eexpl K-2/7A2/55 in order to balance the terms,
2 C²
C. C.H²
AEexpl
Eexpl 5/2K
which yields,
v(**tl) VIIII
C2A3/2H²
(c.+ 12x47) H HVEen CaBaa + A312 x5114 V + Evgd
=0
K217
and completes the proof.
D.4. Proof of Lemma 19 Lemma 20. For any MDP M= PS, P.p,y,p)) and two policies n, ;: S A(A), have:
|| - ,* S <HI π xlle
Proof. Consider the MDP M,
r. P.r. the same MDP M but with reward function defined by rx (s, =x). Let Vigre 2. denote its value and action-value functions, respectively. We have
=
I'1 (s, = x} 50 = =s.a0 a.
1=0
80
y Pr (s, =x 1 s. a,
= =I(s [S=x) +
Pr = 5,00 a.
1=1
=1(s=x}+> +y
Pr =x ~ ~ Psa. R)
1=1
1(s x + y k0
(x).
29

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Hence,
#² (x))
V Aiix
V
Maix
=E (Q (Q Az - -As)
(Lemma 14)
HE
Σ 01s =x} + +YMp (x) (Asa Isa)
Σ 1 (s = x) (Asa Asal +Y Σ #
MPn (x) (#sa - asal
a
Σ HP (x) (Asa Asaa)
yHESs-u
Therefore,
-x) = Elu - =yH Σ Ex-po Σ
# MBsa (x) (Fsa Asa))
$ yH Σ Es-ui
Σ
MR (x)
t
Tsal
x
=yHllEx-pr x-pp"
Σ
Σ
Hb &
(x)
İasa Txal
-yHEsspu
x
Σ
1 nsal
=yH || 21121113)111
and the proof is complete.
Proof of Lemma 19. Let rt E IIf and set II to be the non-exploratory version of xf. We have, by Lemma 14:
- =Es-pa (e Ts πニ)) = =Es-pr (25 .T, u) 2eHl.
(13)
In addition,
VV -VV))))(()))))>>)))) = Σ llue (s) - (100l
$ Σ Ilee51l 11 IA (s)
(+)++ (s)- ( er
$ AH AH|| - μ"1l + Es - -
1.
To bound the first term, apply Lemma 20:
AH I || s AH2 || xlle)00),1 S EAH2 || ulle S 2EAH2
To bound the second term, we have for any 7:
E e.ll H² EnT(s ΣΣ u (5') nslli
1122A A Σ Σ n (s)
MP, (5') || - -
3.4
H2 || n 1
30

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
where R$ is defined by
v(5)
(s) MPP.a (s').
3,0
By the law of total probability, A(S) is in fact state probability measure. Hence, we obtain
E e. -
[/' - =EfiA ull 2e/f?A.
The bounds on both terms, combined with the previous display now yields
(TT
s 4EAH².
(14)
We now turn to apply Equations (13) and (14) to establish the claimed VGD condition. xt E II be an arbitrary e-greedy policy and π E the non-exploratory version of π.. The assumption that II is (C., Evga)- Evga)-VGD implies
max (VV()),
(V(x) - (II Evyd)
#ell
C+
Let E be the policy maximizing the LHS, and # E) + Eul II its corresponding greedy exploration policy. have,
(VV(*"), xx)) = (WV
= (1 - <) (VV( x) x) (1 - (1-V
2 1-E (V(T) V*(II) Eigd) (1- -V((),
C.
2
(V(x) - -VI - Exgd) - -
C.
1
(V(x) (IIII) Engu) - SEHPA
(Equation (14))
C.
2 (V(*)) V*TII Evgd [V(x)) V(x)l) 8
C.
2 (V(x*) VII Evgd 2EH - 8EH2 A
(Equation (13))
C,
1
C. (V(x*) (ITF) Sugd 4eH) 8 A.
(Equation (13))
(Indeed, we pay for the difference V*(I+)- V*II) here, only pay it again in the other direction later, but is cleaner this way and results in only an extra constant numerical factor.) Therefore,
max #'lll (VV(T x²) 2 V(x²) V* (IIf) Eyg 12EC, H2A.
which completes the proof.
E. Constrained non-convex optimization for locally smooth objectives: Analysis
In this section, we provide the full technical details for Section 3.2. Recall that we consider the constrained optimization problem:
min f(x). xeX
(15)
where the decision set X C Rd is convex and endowed with a local norm x + ||-11, (see Definition 5), and access to the objective granted through an approximate first order oracle, as defined in Assumption 3. We assume f: - R is differentiable and defined over an open domain dom f s Rd that contains X. We consider an approximate version of the
31

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
algorithm described in Equation (8), hence for the sake of rigor, we introduce some additional notation. Given any convex regularizer h: Rd - R, we define Bregman proximal point update with step-size 1j > 0 by:
(x((x; h) arg min yex
(16)
and the set of -pproxppoee solutions by: Supt 1 (x; li) = x* E EXIVEEX: (Br()) (),(x",x),2-x" --x Bopu
{
(17)
Now, the approximate version of our algorithm is given by:
l....,K
K Xk+1 (x2; Rxx)-
(18)
We recall our main theorem below.
Theorem (restatement of Theorem 3). Suppose that f is (C*, Evga)- VVD as per Definition 4, and that f = minxex f(x)
-00 Assume further that:
The local regularizer R₂ is I-strongly convex and has an L-Lipsshitz gradient w.r.t. Il-l1x for all x e X.
(ii) For all x E X, max I|u - vllx s D, and [()]l, s M.
(iii) f' is B-locally smooth w.r.t H ||-IIx-
Then, for the algorithm described in Equation (18) we have following guarantee when s 1/(2B):
C.L. {
((
(C,.D+co1))e) e Cat c1 Eop + Exgd
nnK
where 0₁ = D 1.M.
Evidently, since the objective is not convex, standard mirror descent analyses are inadequate, and our analysis takes the proximal point update view of Equation (18). While there are numerous prior works that investigate non-euclidean proximal point methods for both convex and non-convex objective functions (e.g., Tseng, 2010; Ghadimi et al., 2016; Bauschke et al., 2017; Lu et al., 2018; Zhang& & He, 2018; Fatkhullin & He, 2024; see also Beck, 2017). non of them fit into the specific setting we study here. The notable differences being the use of local smoothness (Definition 6), and the goal of seeking convergence in function values for a non-convex objective by exploiting variational gradient dominance.
Our approach may be best described as one that adapts the work of Xiao (2022) to the non-euclidean (and, "local") setup, but without relying on the objective having a Lipschitz gradient (note that we do not claim our definition of local smoothness implies Lipschitz gradient condition). Since Xiao (2022) relies global smoothness of the objective w.r.t. the euclidean norm (as was established by Agarwal et al., 2021), their bounds inevitably scale with the size of the state-space S, which we want to avoid. Given any convex regularizer h: Rd - R, we define Bregman gradient mapping by:
Gx h) = (Vh(x) - vh(x*)),
(19)
where x e Rd should be interpreted as an approximate proximal point update step, i.e., x* T (x;
E. Bregman prox: Descent and Stationarity
In this section we provide basic results relating to proximal point descent and stationarity conditions. Our first lemma is (roughly) a non-euclidean version of a similar lemma given in (Nesterov, 2013) for the euclidean case.
Lemma 21 (Bregman proximal step descent). Let ||-I| be norm, and suppose x E X is such that
B lly x112
Vy e (f(y) f(x) (V)()), x)1
Assume further that:
32

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
1. 0 77 1/(28),
2. h: Rd - IR is I --strongly convex and has an Li-Liccchitz gradient, w.r.t II-II-
3. (1(x))-s(())) 8c.
Then, for x* E 1 (x; hi) we have that:
f(x)) S f(x)
(G,(x, ne- (x,,(xxx';;:]]] Eopt.
21,
Proof. Observe,
f(x) s f(x+ (Vf(x),x* - -x) B
| x||
2
f(x)+ (5)(x),x* xx)
|x x|I² + +Vv((x) (F())))((()))++-))
2
+((++ (7)(x),x* -x)
B
|r+ + x|I + 6. |xx - x||
$(()+ (0)()),x** - B ||+
x|I + n7v (x,(x,x h)|l
(Lemma 23)
Further, since xt E T (x; h), for any ZE X,
-+) (
vh(x)), -hh)))) 6opt-
Hence,
f()+ (0++(1(0)) (F)(2),x* - x)++ 1
/ 111 - -xIp
f())+ 7
1 (Vh()) vh(x+),x* -xx)))>xxxx++++-
+ B -
2
-x] Eopt
f(x) 1 (Ba(r*xx + Bx(xxx*)) + B -11=-=11 -x|p Eupl
7
$ fx)
(B,(+* x) (x,xxx*)) + +B + Eopt
7)
f()
(Ba(x*, .x) Bn(xxx*)) Eapt.
2n
where the last line inequality follows from - 1/(2)). Combining with the previous derivation, we now have
1
f(x*) fxx) - 2n
(x, .x) + (x(x,x)) + copt + m7. (x,,
(20)
Finally, the assumption that h has an L,, Lipschitz gradient implies that
x (l,,,,x,,x* w]]l =|[//(x**) vh(+)]] s 1 1|+ =1I2 Bn
and similarly 7? (x, m)ll s (xxxxx Hence,
2n (Ba(x*,x) (xxxx)))) s (G,
21, which completes the proof after combining with Equation (20).
33

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Our second lemma bounds the in optimality conditions at any point X w.r.t. the gradient mapping dual norm. We remark that here do not assume Lipschitz gradient condition holds for the objective function, commonly done in similar arguments (e.g., Nesterov, 2013; Xiao, 2022).
Lemma 22. Let |I-I1 be a norm, and X. Assume that:
1. h: Rd - --stonggyy convex and has an Ln-Lipschitz gradient, w.E.f II-II.
2. [[(() -V Sc.
3. D > 0 upper bounds the diameter of Xf: yax l|z yll s D
4. M upper bounds the gradient dual norm x: [[ s M.
Then, ifx* E TT (x; li), it holds that:
V (Vf(x) (D (D+ ExD copt.
Proof. By assumption, we have for all y e X,
((x()) - G0,(,,";,,;;,,,) - -x)) 2 Eopt
= (Vf(x),x*-)) - (G,(xx,x:1)..y1 (Vf(x) (f(x) -5) Expt
s (x, 11]l D 8.D + Sopt.
Further,
(Vf(x).x-)) (V)tt)))
$ (x,(x,,' 11) D+ Cupt + (x)
x C,,(x,x 11) D+ D, Eopt + M 1|x xx1
x Gn 11) D e, Eopt + M xx, 11]l.
(Lemma 23)
D MM) || m|]. E.D Eapt.
which completes the proof.
Lemma 23. For any norm |I-I], and any x,x E X, we have ||x x s ,
Proof. For any u, it holds that (see e.g., Hiriart-Urruty & Lemaréchal, 2004))
||u v11 s B, v) (Vh(u,, Vh(v)) _ ||Vh(u) - V The result now follows by the definition of G G,,xxxxthh)
E.2. Proof of Theorem
We begin by establishing the objective satisfies weak gradient mapping domination condition similar (but not identical, due to the differences mentioned above) to that considered in Xiao (2022).
Definition 8. We say that f: X satisfies weak gradient mapping domination condition w.r.t. local regularizer R if there exist ö, such that for all X:
(G, V2w(f(x)- -
The lemma below establishes our objective function satisfies Definition 8 with suitable choice of parameters.
34

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Lemma 24, Suppose that is (C., - as per Definition 4, and that f minxex f'xx Assume further that Rx is 1-strongly convex and has L-ILipschitz gradient w.r.t. II-Ilx for all x X. Then, we have the following weak gradient mapping domination condition; for all x X,xx T Rx):
[x, Rx)I1* 2 V2w (f(x) f 6
for w = (D+ + 6 Evgd cpp C+ &.C.D.
Proof. Letx E X, and apply Lemma 22 with ||-1| = Il-Il,, and h Rx. to obtain:
E (vf(x),x - y) (D MM) nD) (x, R.) E. Eupt-
Further, since f is (C., Eygd) VGD, we have
1 max (Vf(x),x-)) y) (f(x) f Euga)
yeX
Cx
Combining both inequalities, the result follows.
We are now ready to prove Theorem 3,
Proof of Theorem 3. In the sake of notational clarity, define:
Gx = (x,, Rsp Ilss
(21)
We begin by applying Lemma 21 for every k E [K] with ||-11 = -11-11 and h = Rx which implies,
f(xx+1) - f(x+) s 212 gh + neaGr Eopt-
(22)
Let us first assume that for all E [K]:
4L 8L +
EEopt $ Gk.
(23)
vi
Then Equation (22) along with Lemma 24 gives
f(x+1)) f(xx) S S S
nw
-(x
4L,
41.2
with w (D) and 5 = Evgd + Copr D. D. We proceed to define Es == f(xx) and note that the above display implies Ex+1 S E,. Hence, we may assume that Eg 2 25 for all & E [K], otherwise the claim holds trivially. With this in mind, we now have,
Exs1 Eg s
nw 4L2
(Ex - -0
nw
E2
167
Dividing both sides by Eg Ex+1 yields
170
Eg
Ex
Ex+1
16L.
Eg+1
Summing over k I..... K and telescoping the sum on the LHS, we obtain
710
Ex
E
Ek+1
167
ER+1
k=1
116
K
Ex
nw
EK-1 - E1 S
Ei)
(Ek+1E1) K,
161
Ex+1
16L
k=1
35

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
where the last inequality follows from the descent property Ex+1 Eg. Rearranging, have
nw
S Ek+1 S El
1672 K+IK)
167.
32C L2 (D + nM)²
Ex+1 S
nou
n
which completes the proof for the case that Equation (23) holds for all k [K]. Assume now that this is not the case, and let kg [K] be the last iteration such that
GKo < 8L + 4L
Vegii.
Vi
Then by Lemma 22,
Ekg s (n+ + 6g1) + Eopt $ 8(D + nM) 1.60 + I. (1/eap/1) + E. + Sopt.
and therefore by Equation (22),
EgG+1 S Eko + n =0 ( M)) L'er L (oop///))
Now, if kp K are done. Otherwise, by the definition of ko we have that Equation (23) holds for all & [ko 1, K] hence Ex+1 S Eg for all & 2 ko 1. This implies that Ex+1 I Eko-1, which completes the proof.
E.3. Convergence stationary point without VGD condition
In this section, include proof that the proximal point algorithm consider converges stationary point, also without assuming VGD condition. The proof follows from standard arguments and is given for completeness; for simplicity, provide analysis only for the error free case. As an implication, we have that PMD converges to stationary point in any MDP; this follows by combining the below theorem with Lemma 4 and Lemma 2, and proceeding with an argument similar to that of Theorem
Theorem 25. Suppose that f* = mingex f(x) -00, and assume:
(i) The local regularizer Ry is 1-strongly convex and has an L-Lipschitz gradient w.r.t. for all x e X.
(ii) For all x E X, maxu,veX ||u - vllx s D. and [V s M.
(iil) f is B-locally smooth w.r.f. x x I1.
Consider an exact version of the proximal point algorithm Equation (8) with nj 1/(2B) where &s and k+1 (xgxg Rxy) for all k. Then, after K iterations, there exists k* [K] such that:
VyeX, - 2(D +
+ MM) (f(x)) (f
VK
Proof. the sake of notational clarity, define:
Gx = (1=
begin by applying Lemma for every k E [K] with |1-11 = =11-11xg and h = Rus. which implies,
f(xx11 f(xx)
21,2 G
17
(24)
36

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Now,
K
(ik+1)-(xx) ((x++) - _
7
Σ g
2L
thus, rearranging and bounding f(**+1) 2 f(x*) gives
1
21.2 (f(x)) (fxx)) (xx))
K
n
Hence, it must hold for k* arg ming g
G 2L (f(x)) (f(x)))((x)) f(xx))
n1K
We now apply Lemma 22 conclude,
Vy (V/(x=).xx++ (D + 2
Vnk
which implies the required result.
F. Policy Classes with Dual Parametrizations
In general, solving the following OMD problem in some state E S,
Z k+1
arg min (e: BR (p.
(25)
pc((A
is equivallntt to the following two updates:
VR(* VR(T
-
2 k+l
(
A19)
Let us denote the composition of the dual-to-primal mirror-map and the projection:
PR(y) 11 ( (VR*())).
and note that
* (R(VR((!")))
When we are in non-tabular setup and have non-complete policy class II A(R)S, we cannot update each state independently according to Equation (25). There however a number of places we can "intervene" in the policy class representation derive slightly different update procedures based on the dual variables. The PMD step in its general form is given by:
x 8+1 arg min E Ey- (ett n.) 1 Br (TT xT))
(26)
Without making any assumptions regarding the parametric form of II, we cannot decompose Equation (26) into meaningful dual space steps. We discuss next two types of policy class parameterizations and the update steps associated with them.
37

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
F.1. Generic dual parameterizations
This the approach taken in (Alfano al., 2023) (see also the followup Xiong al., 2024), and perhaps the most general one that allows for explicit dual space update well as leads to an approximate solution of Equation (26) that satisfies approximate optimality conditions in the complete-class setting. Consider parametric function class Fe == foo e RSA 0 6), and the policy class:
m = {nt (fETa). where N. = PR(fs), V.es.
Then, to solve Equation (26) we can proceed by:
fh+t arg min E- feT
||Is (lV-)V((T))) - -
x+1 the policy defined by x.S1 PR(
(A)
F.2. The log-linear policy class
This is special of the one discussed in the previous sub-section. In general, when try to approximate the true solution of the unconstrained mirror descent step in specific state:
fs ~ VR(n,) n
we need to overcome two sources of error; one from the previous policy dual variable and one from the Q function. More specifically, in general we have VR(=*) & F and Q* & F. (For æ RA we define VR(x), = VR(Tz)..) In the special case that our function class F can represent ((rr perfectly for all æ E IIF) and closed to linear combinations, we can focus our attention on approximating the Q function. Now, we may proceed by the following special case of (A):
@+ - arg min E, Esa--u QEF
(eraa- -
jk+1 VR(x*) - π²
k+1 the policy defined by nkttl PR PR((tt
(B)
Let óx,a E R be given feature vectors, and let Φs == [ds,a ... &r,an E RPXA and consider the log-linear policy class:
II = f 10 [
00,0
where Vs S, x. P)(
Σa 00.a0"
Note that:
1. This the class II(F) for = {00+ + ((s,a) + 0)
2. This is precisely case where F can model RR(x) is the negative entropy regularizer.
Here, we may proceed as follows:
" < arg min Es,a-u* WeRp @k+l - 0² nn
(05. - e
x the log-linear policy defined by gh+1
38

---

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
The above be special of (B), by considering the induced updates in state-action space:
(R:0 Q5.0 )21 (s, 0 w
@ arg min E QET
5.a-
k+1 VR(T.) 2
= log l o - log 2, 2
o 8K 2 log
e0l okn
x= k+1 the policy defined by n PR(stt+))=
En @
Note that in the above,
f. = -
no w log(Z,)
and that z is the same for all actions in s, hence makes no difference after the projection step..
39


Reviews:
[{"review_id": "WSgezPlWlU", "reviewer": "Reviewer_zqsi", "summary": "This paper studies the convergence of policy mirror descent under the variational gradient dominance condition.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and comments.\n\n**1.** We show in the paper (Appendix A.2) that perfect closure in the negative entropy case implies VGD. Following your comment and those of the other reviewers, we have extended this implication to hold for general approximate closure assumptions as formalized in Alfano et al., 2023. A summary comparing our assumptions / bounds with prior works is given below. Columns state assumptions required by the different works. Rates are for constant step size PMD.\n\n| Paper                | VGD | Closure  Assumptions     | Parametric Assumptions | Realizability | Rate        |\n| -------------------- | --- | ------------- | ---------------------- | ------------- | ----------- |\n| Lan 2023 / Xiao 2022 | Yes | Yes (perfect) | Yes (Tabular)          | Yes           | $1/K$       |\n| Yuan et al. 2022     | Yes | Yes (approx)  | Yes (Log-linear)       | Yes           | $1/K$       |\n| Ju & Lan 2022        | Yes | Yes (approx)  | Yes (EMaP$^{[a]}$)     | Yes           | $1/\\sqrt K$ |\n| Alfano et al. 2023   | Yes | Yes (approx)  | Yes (EMaP$^{[a]}$)     | Yes           | $1/K$       |\n| **Our work**         | Yes | No            | No                     | No            | $1/K^{2/3}$ |\n|                      |     |               |                        |               |             |\n- $[a]$ Stands for Exact Mirror and Project\n\nWe refer to our response to Reviewer 9aB9 (Under “Relation of VGD and Closure” and “Comparison with prior works”) for additional details regarding the comparison. The other paper [2] Zhan et al. 2023 you have mentioned studies the regularized MDP setup, and requires the same set of assumptions as Lan 2023/ Xiao 2022. Note that while VGD is indeed a relaxation of the PL inequality, prior works do not make the PL-inequality assumption directly.\n\n**2.** Lemma 4 is just a building block in the proof of Theorem 1. The connection between the MDP parameters and the parameters stated in the Lemma is given in the proof of Theorem 1; the proof sketch for the Euclidean case is given in the main text in the final paragraph of Section 3.3, and the detailed proof for both Euclidean and negative entropy cases is given in Appendix C.3.\n\n**3.** These are standard assumptions in the general function approximation setup; we expect these to be achieved by optimizing neural network models (e.g., actor and critic networks). Since we do not make any structural assumptions, the corresponding optimization problems are non convex in the network parameter space and thus do not admit provably efficient optimization procedures. See e.g., Alfano et al. 2023 and Xiong et al., 2024 where similar assumptions are made. The assumption on optimality conditions is implied by approximate optimality in function values.\n\n**4.** We are not sure we understand the question, the main contribution of the paper is Theorem 1. In order to prove Theorem 1, we break it into several building blocks. The central building block on the optimization side is Theorem 3. In order to obtain Theorem 1 from Theorem 3, we need to combine it with Lemma 2 (which establishes the key local smoothness property of the value function), and Lemma 4, which links Theorem 3 with the MDP setting.\n\n## Other Strengths and Weaknesses\nThank you for your comments, we will revise our exposition for the final version.\n\nPlease note however that it is a common practice to provide an overview of the results with only minimal preliminaries as we do in Section 1.1. This is beneficial for the many readers that only want to understand the main results at a high level. That said, if you have any specific suggestions we will be happy to hear and consider them during our revision.", "claims_and_evidence": "Under the variational gradient dominance condition, this work obtains the first convergence rate of PMD. I have some major concerns:\n1. I am confused about the claim in Section 1.2 that VGD is not comparable with the other conditions in the literature. Since this is a relaxation of the usual PL-inequality, at least one can compare the theoretical results in this paper with the prior works assuming PL or strong convexity. Following this logic, I suggest the authors providing a table showing how condition (2) is satisfied in the literature and list the corresponding convergence rate of the algorithm. At least, the comparison to [1, 2] should be presented.\n2. I am concerned about the assumptions in Lemma 4. Could you show how $D$, $M$ and $\\beta$ depend on the parameters of a MDP?\n3. I am also concerned about Assumption 1 & 2. Usually in the literature, we need a subroutine to have small $\\varepsilon_{\\rm act}$ and $\\varepsilon_{\\rm crit}$. How do you achieve this in your setup?\n4. Seemingly Theorem 1 is only a consequence of Theorem 3. Then what is the contribution of this paper? \n\n\n[1] Lan, G. (2023). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1), 1059-1106.\n\n[2] Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, J. D., & Chi, Y. (2023). Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33(2), 1061-1091.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "NA", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The presentation of this work should be significantly improved.\n1. Introduce notations, assumptions and definitions only when you need them. Move any notions that are not directly relevant to your analysis to the appendix.\n2. Avoid redundancy. Many results and notations are introduced twice, first time in Section 1.1 and then again in Section 2. Be precise and consistent.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CFm5uCj2iH", "reviewer": "Reviewer_ch65", "summary": "The paper addresses the convergence of policy mirror descent method for generalized policy classes ie policy classes with a general parametrization. Most of the prior literature considers either the tabular case where each state can be mapped to any probability vector over the action space, or they consider policy classes which are closed under the PMD update. The main assumption the authors rely on is the variational gradient dominance (VGD) (a PL inequality of sorts for the policy class) of the value function and the convexity of the policy class. The authors argue that the prior assumption over the policy class being closed is stronger than VGD since a closed policy class implies VGD whereas the converse isn't true, making VGD a weaker assumption.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and providing thoughtful comments. We were glad to hear you appreciate our work, in particular, that the reviewer recognizes our paper **“addresses an important problem in the literature”**, and **“relaxes an assumption (from closed policy class to VGD) typically involved in the analysis of these problems”**.\n\n\n# Weaknesses\n\n**1.** Following your comment and those of the other reviewers, we have tightened our comparison with prior works. \n\n### Comparison of assumptions and rates\nThe table below summarizes representative papers and their rates for constant step size PMD. Columns state assumptions made in different works.\n\n| Paper                | VGD | Closure Assumptions | Parametric Assumptions | Realizability | Rate        |\n| -------------------- | --- | ------------------- | ---------------------- | ------------- | ----------- |\n| Lan 2023 / Xiao 2022 | Yes | Yes (perfect)       | Yes (Tabular)          | Yes           | $1/K$       |\n| Yuan et al. 2022     | Yes | Yes (approx)        | Yes (Log-linear)       | Yes           | $1/K$       |\n| Ju & Lan 2022        | Yes | Yes (approx)        | Yes (EMaP$^{[a]}$)     | Yes           | $1/\\sqrt K$ |\n| Alfano et al. 2023   | Yes | Yes (approx)        | Yes (EMaP$^{[a]}$)     | Yes           | $1/K$       |\n| **Our work**         | Yes | No                  | No                     | No            | $1/K^{2/3}$ |\n|                      |     |                     |                        |               |             |\n- $[a]$ Stands for Exact Mirror and Project\n\n\nFor additional remarks, we refer to our response to Reviewer 9aB9 (“Comparison with prior works”). Regarding the formal relation between VGD and closure, see below “Relation of VGD and Closure”.\n\n### The example in Section 2.1\nThe technical argument is given with full detail in Appendix E.2, where we demonstrate a strong form of closure w.r.t. the optimal policy occupancy (bias-error) does not hold. The simplest way to see that the standard approximation-error closure does not hold globally is since the setup in question is not approximately realizable (we have $V^\\star=0$ while $V^\\star(\\Pi)=H/2$). \n\n\nThe goal with this example was not only to show that closure does not hold, but also that the bounds of prior works become vacuous, and for that, additional technical arguments are required. Following your comment, we will revise the exposition of this example, and try to find a better balance between conveying the idea while keeping technical details to the minimum.\n\n\n\n**2.** The $O(\\epsilon)$ term you are missing is there through the additive $\\delta$ term. We define it in the first line of the proof, line 1013, $\\delta=\\epsilon_{\\rm vgd} + 12\\epsilon_{\\rm expl}C_\\star H^2 A^2$. We suppose it is now clear that the reason for setting $\\epsilon_{expl}=K^{-2/3}$ is to balance the two terms. We will highlight the definition of $\\delta$ in a display equation so that it cannot be easily missed.\n\n## Questions for Authors:\nThis is a good question, as we show in the paper in Appendix A.2, perfect closure with negative entropy regularization implies $\\epsilon_{\\rm vgd}=0$. Thanks to your comments and those of the other reviewers, we have added a simple extension of this implication to hold for the general closure conditions as formalized in Alfano et al. 2023.\n\n# Relation of VGD and Closure\nWe adopt the closure conditions as formalized in Alfano et al. 2023. Let $C_v$ be concentrability coefficient (A2 in Alfano et al.) and $\\nu_\\star$ the distribution mismatch coefficient (A3 in Alfano et al.).\n\nThen the following relation holds: $\\epsilon$-Approximate Closure (A1 in Alfano et al.) $\\implies$ $(\\nu_\\star,H\\nu_\\star\\sqrt{C_v \\epsilon})-$VGD.\nImportantly, the $\\epsilon_{vgd}=H\\nu_\\star\\sqrt{C_v \\epsilon}$ is **exactly** the error floor exhibited in the results of Alfano et al. 2023 (as well as in other works based on closure).", "claims_and_evidence": "I haven't read through the appendix in detail but the paper in its current form cannot be assessed without a detailed reading of the appendix. \nHowever I do some comments/concerns that I have elaborated on later.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I haven't examined the proofs in detail.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "Convergence of PMD methods for generalized policy classes is indeed an important question that needs to be answered. Especially in the context of Deep reinforcement learning, where the policies are parametrized in terms of the weights of the NN, the theoretical performance of these algorithms is not very well understood.", "essential_references_not_discussed": "I am not well versed in the literature pertaining to the non tabular PMD methods, hence I am unsure of all the important references being included.", "other_strengths_and_weaknesses": "Strengths:\n1. Addresses an important problem in the literature\n2. Provides bounds that are independent of the cardinality of the state space\n3. Relaxes an assumption (from closed policy class to VGD) typically involved in the analysis of these problems\n\nWeaknesses:\n1. The paper can use better presentation. In its current form it is hard to delineate what the different assumptions are in different prior works. Also the example in Section 1.2 needs better elaboration. It is not clear at all as to why the policy class here is not closed. \n2. In appendix C.3 Proof of theorem 1, line 1034, in the suboptimality expression of $V$, the exploration probability $\\epsilon_{expl}$ appears in the denominator. Typically inducing an $\\epsilon$ exploration in your policy class leads to a suboptimality which grows $O(\\epsilon)$, but here greater the exploration probability smaller the suboptimality, which is contradicting to whats typically observed. I don't understand the reason for this. Also, is there a reason for setting $\\epsilon_{expl} = K^{-2/3}$? Cause this seems to lead to a regret that eventually increases in terms of the approximation errors (in theorem 1).", "other_comments_or_suggestions": "NA", "questions_for_authors": "What does a closed policy class implying VGD mean in terms of $\\epsilon_{vgd}$? Since $\\epsilon_{vgd} = \\frac{1}{1-\\gamma}$ is trivially true for all policy classes, do closed policy classes yield an $\\epsilon_{vgd} < \\frac{1}{1-\\gamma}$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vz0k3C9bmk", "reviewer": "Reviewer_9aB9", "summary": "This paper establishes an upper bound on the convergence rate of the on-policy policy mirror descent (PMD) algorithm in an agnostic learning setting for discounted MDPs. The authors replace the commonly assumed closure condition with a weaker variational gradient dominance (VGD) assumption. Under this condition, they prove that PMD achieves a convergence rate of  $O(K^{-2/3})$￼with Euclidean regularization and $O(K^{-2/7})$ with negative entropy regularization, where $K$ is the number of iterations. Their analysis frames PMD as a non-Euclidean proximal point method, leveraging a local smoothness property of the value function defined by local norms induced by the policy’s occupancy measure.\n\n## update after rebuttal\nI have reviewed the authors’ rebuttal and found their responses satisfactory. My assessment remains unchanged, and I continue to recommend acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work and for your thoughtful comments.\n\n**“Overall, this paper is well-structured and provides a solid theoretical contribution...”** We were happy to read that the reviewer appreciates the value of our contribution, and in particular that the reviewer recognizes **“Using local smoothness of the value function to establish convergence rate independent of the cardinality of state space is a novel technical contribution.”** - we completely agree!\n\n## Weaknesses\n**“The paper lacks a comparison … the closure condition.” / “A careful comparison between … more restrictive assumptions.”** This is a good point which we will address in our revision. Thanks to your comment, and questions from other reviewers, we have extended the “perfect closure implies VGD” from our Appendix A.2 to hold generally; see below “Relation of VGD and Closure”. Also below, we have included a summary comparing assumptions and rates of ours and prior works “Comparison with prior works”.\n\n**“Empirical validation … could provide valuable insights.”** Our contribution is primarily theoretical and empirical evaluations are outside the scope of our work. We agree that such research may be valuable and should be considered for future work.\n\n\n## Questions For Authors:\n**“How do the derived rates … degrade rates?)?”** With constant step sizes, the best rate achievable (given closure or in the tabular, exact, complete class setup) is $O(1/K)$. With non constant geometrically increasing step sizes, linear rates (i.e., $O(e^{-cK})$ for some constant $c$) are attainable (again, given closure or a tabular setup). We do not expect these rates to be attainable assuming only VGD. We include additional remarks in the comparison below.\n\n# Relation of VGD and Closure\nWe adopt the closure conditions as formalized in Alfano et al. 2023. Let $C_v$ be concentrability coefficient (A2 in Alfano et al.) and $\\nu_\\star$ the distribution mismatch coefficient (A3 in Alfano et al.).\n\nThen the following relation holds: $\\epsilon$-Approximate Closure (A1 in Alfano et al.) $\\implies$ $(\\nu_\\star,H\\nu_\\star\\sqrt{C_v \\epsilon})-$VGD.\nImportantly, the $\\epsilon_{vgd}=H\\nu_\\star\\sqrt{C_v \\epsilon}$ is **exactly** the error floor exhibited in the results of Alfano et al. 2023 (as well as in other works based on closure).\n\n# Comparison with prior works\nThe table below summarizes representative papers and their rates for constant step size PMD. Columns state assumptions made in different works.\n\n\n\n\n| Paper                | VGD | Closure Assumptions | Parametric Assumptions | Realizability | Rate        |\n| -------------------- | --- | ------------------- | ---------------------- | ------------- | ----------- |\n| Lan 2023 / Xiao 2022 | Yes | Yes (perfect)       | Yes (Tabular)          | Yes           | $1/K$       |\n| Yuan et al. 2022     | Yes | Yes (approx)        | Yes (Log-linear)       | Yes           | $1/K$       |\n| Ju & Lan 2022        | Yes | Yes (approx)        | Yes (EMaP$^{[a]}$)     | Yes           | $1/\\sqrt K$ |\n| Alfano et al. 2023   | Yes | Yes (approx)        | Yes (EMaP$^{[a]}$)     | Yes           | $1/K$       |\n| **Our work**         | Yes | No                  | No                     | No            | $1/K^{2/3}$ |\n|                      |     |                     |                        |               |             |\n- $[a]$ Stands for Exact Mirror and Project\n\n\n### Remarks\n\n- *Our rate.* We report our $K^{2/3}$ rate for the Euclidean regularization case. More generally, our rates depend on smoothness of the action regularizer, which leads to worse rates for regularizers such as the negative-entropy. We conjecture both that the base rate can be improved to $1/K$ and that dependence on regularizer smoothness can be lifted; however, this seems to require new ideas and we leave it for future work.\n\n- *Non constant step size results.*  With non constant geometrically increasing step sizes, linear rates (i.e., $O(e^{-cK})$ for some constant $c$) are attainable (e.g., Alfano et al. 2023, Xiao 2022, Jhonson et al. 2023). We do not expect this is possible assuming only VGD. The reason these rates are attainable subject to closure is that the algorithm dynamics mimic those of the tabular setting, where policy iteration converges at a linear rate. Assuming only VGD, policy iteration no longer converges (at all), as the policy class loses the favorable structure allowing for convergence of such an aggressive algorithm. This should highlight the value in studying the function approximation setup without closure.\n\n- *Convexity of the policy class.* In our submission we point out the convexity of the policy class as a potential differentiator between our approach and that of Alfano et al., 2023. Following the reviewers comments, we realized this is not the case, and that convexity requirements are similar in our work and that of Alfano et al. 2023. Given closure, our analysis does not require convexity, same as Alfano et al.", "claims_and_evidence": "The claims are well-supported by rigorous theoretical proofs and an illustrative example.", "methods_and_evaluation_criteria": "The authors carefully discuss and compare their results with prior work.", "theoretical_claims": "I did not find any issues in the theoretical claims, though I did not verify the deferred proofs in the appendix.\n\nA key component of the analysis is Lemma 2, which establishes the local smoothness of the value function with respect to the local norm induced by the policy’s occupancy measure. The proof relies on value difference lemmas and occupancy measure properties. This local smoothness condition enables the authors to derive convergence rates independent of the state space size.\n\nAnother crucial component is the reduction of the PMD setup to an optimization framework for constrained non-convex optimization of locally smooth objectives. The theoretical framework introduced is novel.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The discussion of related prior work is thorough.", "other_strengths_and_weaknesses": "Overall, this paper is well-structured and provides a solid theoretical contribution to the convergence of PMD under the agnostic learning setup for discounted MDPs.\n\nStrengths:\n- Introducing the VGD condition and proving the convergence of PMD without closure conditions are novel contributions.\n- Using local smoothness of the value function to establish convergence rate independent of the cardinality of state space is a novel technical contribution.\n\nWeaknesses:\n- The paper lacks a comparison between the convergence rate obtained under the VGD condition with existing convergence results under more restrictive conditions, such as the complete policy class or the closure condition.\n- There is a lack of experiments to validate the theory, though this is common in RL theory papers.", "other_comments_or_suggestions": "- Empirical validation of the theoretical results would strengthen the paper. Implementing PMD under the VGD condition and comparing its empirical convergence with the derived theoretical bounds could provide valuable insights.\n- A careful comparison between the convergence rates under the VGD condition and those under the closure condition would help contextualize the benefits and limitations of the proposed framework. This could clarify whether VGD provides comparable or significantly different guarantees relative to more restrictive assumptions.", "questions_for_authors": "How do the derived rates under VGD (e.g., $O(K^{-2/3})$) compare to known rates under closure conditions (e.g., does VGD degrade rates?)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper analyzes policy mirror descent (PMD) for general policy classes (where policy closure conditions are not necessarily satisfied), and obtains upper bounds on the convergence rate to the best (in class) policy. 

The reviewers unanimously agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the rebuttal/discussion, I tend to agree. Please incorporate the following comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Improve the presentation and include the table (in response to all the reviewers) in the main paper. 
- Include an explanation as to when/how assumptions 1 and 2 can be satisfied in simple settings (e.g., linear function approximation)
- Better explain the example in Section 2.1 (response to Rev. ch65)
- Include the comments about the rates obtained assuming closure vs those obtained using VGD (response to Rev. 9aB9)
Decision: Accept (poster)