Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs
Authors: Dongsheng Ding
Chen-Yu Wei
Kaiqing Zhang
Alejandro Ribeiro
Venue: NeurIPS 2023 poster (2023)
Keywords: Constrained Markov decision processes
policy gradient primal-dual methods
non-convex saddle-point problem
last-iterate convergence
entropy regularization
optimistic gradient
TL;DR: We have developed the first two single-time-scale policy-based primal-dual algorithms for solving constrained MDPs with non-asymptotic policy last-iterate convergence.

Abstract: We study the problem of computing an optimal policy of an infinite-horizon discounted constrained Markov decision process (constrained MDP). Despite the popularity of Lagrangian-based policy search methods used in practice, the oscillation of policy iterates in these methods has not been fully understood, bringing out issues such as violation of constraints and sensitivity to hyper-parameters. To fill this gap, we employ the Lagrangian method to cast a constrained MDP into a constrained saddle-point problem in which max/min players correspond to primal/dual variables, respectively, and develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. Specifically, we first propose a regularized policy gradient primal-dual (RPG-PD) method that updates the policy using an entropy-regularized policy gradient, and the dual variable via a quadratic-regularized gradient ascent, simultaneously. We prove that the policy primal-dual iterates of RPG-PD converge to a regularized saddle point with a sublinear rate, while the policy iterates converge sublinearly to an optimal constrained policy. We further instantiate RPG-PD in large state or action spaces by including function approximation in policy parametrization, and establish similar sublinear last-iterate policy convergence. Second, we propose an optimistic policy gradient primal-dual (OPG-PD) method that employs the optimistic gradient method to update primal/dual variables, simultaneously. We prove that the policy primal-dual iterates of OPG-PD converge to a saddle point that contains an optimal constrained policy, with a linear rate. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs. We further validate the merits and the effectiveness of our methods in computational experiments.

Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs
Dongsheng Ding" University of Pennsylvania dongshed@seas. upenn. edu
Chen-Yu Yu Wei* University of Virginia chenyu. wei wei@virginia.. edu
Kaiqing Zhang' University of Maryland, College Park kaiqing@und. edu
Alejandro Ribeiro University of Pennsylvania aribeirodseas upenn. edu
Abstract
We study the problem of computing an optimal policy of an infinite-horizon dis- counted constrained Markov decision process (constrained MDP). Despite the popularity of Lagrangian-based policy search methods used in practice, the oscil- lation of policy iterates in these methods has not been fully understood, bringing out issues such as violation of constraints and sensitivity to hyper- parameters. To fill this gap. we employ the Lagrangian method to cast a constrained MDP into a constrained saddle-poid problem in which max/min players correspond to pri- mal/dual variables, respectively, and develop two single-time-scat policy- based primal-dual algorithms with non-asympiotic convergence of their policy iterates to an optimal constrained policy. Specifically, we first propose a regularized policy gradient primal-dual (RPG-PD) method that updates the policy using entropy- regularized policy gradient, and the dual variable via a quadratic-regularizz gra- dient ascent, simultaneously. We prove that the policy primal-dual iterates of RPG-PD converge to regularized saddle point with a sublinear rate, while the policy iterates converge sublinearly to optimal constrained policy. We further instantiate RPG-PD in large state or action spaces by including function approx- imation in policy parametrization, and establish similar sublinear last-iterate pol- icy convergence. Second, we propose an optimistic policy gradient primal-dual (OPG-PD) method that employs the optimistic gradient method to update pri- mal/dual variables, simultaneously. We prove that the policy primal-dual iterates of OPG-PD converge with a linear rate. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-caale algo- rithms in constrained MDPs. We further validate the merits and the effectiveness of our methods computational experiments.
saddle point that contains an optimal constrained policy,
Introduction
Constrained Markov decision process (Constrained MDP) is the classical model for constrained dynamic systems in the early stochastic control literature (e.g., [1, 2, 3, 4, 5]) and the recent con- strained reinforcement learning (RL) literature (e.g., [6, 7, 8, 9, 10, 11]). It is applicable to many constrained control problems by integrating other system specifications in constraints, and admits natural extension of constrained optimization and Lagrangian in policy space. Lagrangian bassed policy search methods, especially posicy-based primal-dual methods that work simultancously with
Alphabetical order.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

primal/dual variables, lie at the heart of recent successes of constrained MDPs, e.g., navigation [12], autonomous driving [13, 14], robotics [15], and finance [16]; see [17, 18, 19, 20] for more examples.
Despite the popularity of policy-based primal-dual algorithms, classical asymptotic convergence as- sumes that primal-dual updates are in two-time-scue type [21, 6, 22, 16, 9] (and/or work in two nested loops'). and considerable global non-asymptotic convergence guarantee is measured via an average of past objective/constraint functions [23, 24, 25, 26] or mixture of past policies [27, 28]. These results are unfavorable in constrained dynamie systems, especially safety-critical ones, due to three reasons: (i) Average and mixture performance of non-asymptotic convergence conceals os- cillating (or even overshooting) ohjective/constraint functions of immediate policy iterates [29, 30), and oscillation-incurred constraint violation impedes a policy iterate being optimal; (ii) Asymptotic convergence is not instructive, because arbitrarily slow convergence, and oscillation and overshoot in any finite time can happen; (iii) Two-time-sen algorithms including algorithms with nested loops are sensitive to hyper- parameters and are therefore typically difficult to tune [16, 9]. Thus, we ask the following question in constrained MDPs:
Can the policy iterates of single-time-scale policy- primal- algorithm converge to an optimal constrained policy with non-asymptotic rate?
By "single-time-scale"" we refer to the classical methods [31, 32, 33] that iterate primal/dual vari- ables concurrently (with the same constant stepsize). Only partial answers to this question are pro- vided in recent studies [34, 35, 36] since they either do work in the single-time-scale scheme or they do not have non-asymptotic convergence guarantees. In this work, we provide an affirma- tive answer in two methodologies. First, we initiate the design and analysis of single-time seslee-tme-scalle scale policy-based primal-dual algorithms via regularization, while previous works [24, 28, 34] rely on two-time-scale schemes. Second, inspired by convex minimax optimization [37, 38, 39], we pro- pose new optimistic policy gradient for single-time-scal policy-based primal-dual algorithm that solves a class of non-convex minimax problem. While preparing our work, we noticed a contempo- raneous work [40], which has empirically validated the effectiveness of other optimistic methods in constrained MDPs, has further inspired the pursuit of our contributions, as outlined in detail below.
Contributions. To compute an optimal policy of an infinite-horizon discounted constrained MDP, we employ the Lagrangian method to cast it into a constrained saddle-point problem in which max/min players correspond to primal/dual variables, propose two single-time sigle-ttme-scalee policy-based primal-dual algorithms, and prove global non-asymptotic convergence of their policy iterates.
Nearly dimension-free sublinear last-iterate policy convergence. We propose a regularized pol- icy gradient primal-dual (RPG-PD) method that updates the policy using an entropy- regulariee policy gradient, and the dual using a prove that the policy primal-dual iterates of RPG-PD converge regularized saddle point with a sublinear rate, and the policy iterates converge to an optimal constrained policy sublinearly.
gradient ascent, simultaneously. We
Sublinear last-iterate policy convergence with function approximation. We generalize RPG-PD for constrained MDPs with large state/action spaces by including function approximation in pol- icy parametrization. We prove that the policy primal-dual iterates of an inexact RPG-PD converge to a regularized saddle point with a sublinear rate, but up to a function approximation error, and the policy iterates converge sublinearly to an optimal constrained policy when the error is small.
Problem-depender linear last-iterate policy convergence. We propose an optimistic policy gra- dient primal-dual (OPG-PD) method that employs the optimistic gradient method to update the primal/dual, simultaneously. We prove that the policy primal-dual iterates of OPG-PD converge to saddle point that contains an optimal constrained policy with a problem-dependen linear rate.
While last-iterate convergence is of importance in its own right, by adding proper conservatism in the constraint, both methods can ensure no constraint violation for the last policy iterate, which perhaps is best for safety-critical tasks [10, 20J. As far as we know, this work shows the first non- asymptotic and policy last-iterate convergence for single-time-saale algorithms in the constrained MDP literature. We further exhibit the merits and the effectiveness of our methods in experiments.
I One update has relatively very large/small (fast/sloww stepsize than the other.
We view an algorithm with two nested gradient- based loops as wwo-time-scale algorithm.

---

Technical comparisons with prior art Although global asymptotic last-iterate convergence has been established for single-time-scalc algorithms very recently [36, 40], and value-average policy- mixture non-asymptotic convergence have been established for other algorithms [23, 24, 25, 27, 28, 41, 42, 26], these studies did not investigate global non-asymptotic and last-iteratt convergence for single-time time-scale algorithms. Our results not only strengthen these prior guarantees, but also set up new framework for analyzing policy-basee based primal-dual algorithms via the distance of primal-dual iterates to a saddle point that contains an optimal constrained policy. Our RPG-PD and OPG-PD keep the simplicity of single-time-scale primal-dual methods and output nearly-optimal policy in the last iterate, which is more convenient than the history-average policies [28, 24] or the policies from subroutines [34, 35]. Compared with the policy-based methods [40], our OPG-PD is pro- jected policy gradient method that enjoys policy last-iterate convergence with linear rate. Compared with the constrained saddle-point problems [38, 391, our minimax optimization that results from constrained MDP is non-convex. Hence, our OPG-PD extends the last-iterate convergence guaran- tee from convex minimax optimization to a class of non-convex ones, while preserving a linear rate. Compared with the analysis in the two-player zero-sum Markov game [43, 44], there is no reduction from constrained MDPs per-state bilinear games. Please see more details in Appendix A.
2 Preliminaries
We consider an infinite-horizon discounted constrained Markov decision process [3, 5, 8] CMDP ( S, A, P, r, u, 7: where and are state/action spaces, P is a transition kernel that specifies the transition probability P(s'I (1s'|s,u a) from state s to next state s' under action a E A,
S x > [0, 1] are reward/utility functions, b a constraint threshold, 7 E [0, 1) is a discount factor, and p is an initial state distribution. A stationary stochastic policy S + (AA) determines
st) at time t, where ((A) is probability simplex over A. Let 11 be the set of all possible stochastic policies. A policy π E II, together with the initial state distribution p. induces a distribution over trajecto- ries T {(s,, dg, FT, ux) 1t= 0r where so P. a a(- st), rt r(se, oz), u u(st: az) and 8141 ~ P(- St az) for all 20
a probability distribution over the action space A based on current state, i.c., ag ~ x(. x(-|st)
Given policy x, the value functions V V. S - IR associated with the reward function or the utility function и are given by the expected sums of discounted rewards or utilities under policy m:
(s) == E
rr((s, az) 100 = and (s) = E Σ 1=0
Σ
r'u(se at)
so
0
where the expectation E is over the randomness of the trajectory T induced by m. Their expected and V (p) == E,
x [V (s) ]. It is useful to introduce the discounted state visitation distribution, d=,, (s) = (1 10--) 7) E. -0 Pr = s म. su) which adds up discounted probabilities of visiting 8 in the execution of π starting from 8p- Denote (s) == Eee Pepp-ph pl (d%, (s)] and thus (s) 2 (1 -))p(s) for any p and s. Furthermore, for the reward function we introduce the state-action value function QF: S x A + E when the agent begins with state- action pair (s, a) and follows a policy म, and the associated advantage function A5: S A + R.
values under are V.² == Es-p [ [s)]
(5,a) = E
7'r(s ar) 80 =8,00 - and (s, == (5, - (T).). Σ
0
Similarly, we define Q7 S x A R and A S x A - R for the utility function u. In this work, aim to find policy solution '²" of constrained policy optimization problem,
maximize *
(p) subject to V (p) 2 b
(I)
where the objective is the reward value function (p( and the constraint requires that the utility
value function V. (p) is above given threshold For notational simplicity we assume a single constraint, but our algorithms are readily generalizable to the problems with multiple constraints, as well as our subsequent last-iterate convergence theory. Since V.- (p) and V (p) E [0, 1/(1 1/(1-))
we assume b E (0, 1/(1 - 7)] to avoid trivial cases. Let g: S S [-1, g= u =-
We, equivalently, translate the constraint V (p) 2 b into V** (p) 2 0 that is our focal constraint.
The optimal constrained policy n² depends on the initial state distribution P; see Appendix B.
3

---

By the method of Lagrange multipliers [45], we dualize the constraint in (1) and present a standard Lagrangian A) := (p) + XV5 (p), where π E ll is the primal variable and À E [0, oo] is the dual variable or the Lagrangian multiplier. Introduction of the Lagrangian L(TT, X) interprets Problem (I) as a max-min problem: maximize, e I1 minimize,, [0, L A), and thus we can view the Lagrangian [(x,, A) as a value function with composite function + Ag.
maximize minimize T 11
V Vx+2g())
A [0.00)
However, it's defective view Problem (2) as standard MDP problem by fixing a dual variable X, even the optimal one; also see 19, 46, 47, 30]. This is often referred to as the scalarization fallacy [46]; see Appendix B.2 for the detail. From the perspective of game theory, we instead view V II x [0, xo] + IR as a payoff function for a two-player zero-sum game in which max- player is the policy и E II and min-player is the dual variable À E [0, oo J. and study its saddle points. To proceed, we assume feasibility for Problem (1) throughout our analysis.
Assumption (Feasibility). There exists a policy
TI and & > 0 such that V (p) 2.
Feasibility mirrors the Slater condition in the duality analysis of constrained optimization [45]. It can be verified by solving an unconstrained MDP problem with respect to VT((p)
A saddle point (²) satisfies V & Va (oxx)(()) S V (ftg(()) (p) for all π E II, A E [o) or equivalently, nO is the max-min point, i.e., '' E argmax, e II V (P)))p) and X' is the min-max point, i.c., X' E argmin e [0.0o] ViT (p)) To view Problem (2) as a saddle-point problem, we denote V (p) == x [0,oo] Vy as the primal function which takes V, (p) when (g) 2 0 and -00 otherwise, and VD(p) := max, E (p) as the dual function. Let optimal dual variable be X E argmin, [0,cc] (p). For Problem (1) under Assumption I, strong duality holds in policy space [12, Theorem 3] and optimal dual variables are bounded [48, Lemma 3].
Lemma 1 (Strong duality/Saddle point existence and boundedness). Let Assumption 1 hold. Then, (i) strong duality holds for Problem (I), i.e., Vp (p) VB (p); (ii) optimal dual variables are bounded, i.e., X* E (V, V.-)/E)-
Let the set of max-min points be II := argmax, x E minx e [0,cc] V (pt and the set of min- max points be A := argmin, e [0, max, e V V++ (p). From Lemma 1 (ii), A is contained in a bounded interval A := [0. 1/((1 - ]) Lemma 1 (i) shows that any pair (T*,'*)= E III x A solves the following constrained saddle-point problem,
maximize minimize ViT AEA
minimize maximize V (p). A
(3)
* elll
Any saddle points associated with the set A+ are captured by Problem (3) due to the invariance of saddle points, and searching for any pair X*) E IT x A' is sufficient by the interchangeability
of saddle points; see Lemmas 8-9 in Appendix B.3 for the properties of saddle points. Thus, we view the policy (primal) as max-player and the dual as min-player in a zero-sum game.
Three structural properties from constrained MDPs distinguish Problem (3) from recent last-iterate convergence for learning in zero-sum games (e.g.. [37, 38, 43, 39, 44]): (i) Two players are asymmet- ric. One plays a stochastic policy that affects the transition dynamics and the other selects an action in continuous interval that only changes the payoff; (ii) Problem (3) is non-convex game, because of the non-concyvyty of the payoff V (P) in policy æ (e.g., [49, Lemma 1)); (iii) A saddle-pois point policy for Problem (3) cannot be uniformly max-min optimal, i.c., being optimal across all states, since optimal policy often depends the initial state distribution p in a constrained MDP; see Appendix I. Hence, known last-iterate results in zero-sum convex games or symmetric Markov games that admit uniformly optimal policies can't be applied and new techniques are required to address this non-standard saddle-poin problem, which warrants our contributions in this work.
Warm-up: Indirect policy search in occupancy-measure space. Finding a saddle point of a non- convex game is hard in general [50]. Nevertheless, Problem (1) can be rewritten as a linear program regarding the occupancy measure [5], which permits indirectly searching for saddle point of a bilin- ear I Lagrangian [51, 42, 36). These asymptotic or average-iterate convergence results can be easily strengthened by applying last-iterate convergence results for bilinear games (e.g., [38, 39I) to be

---

non-asympiotic and last-iterate. By doing so, we state an optimistic primal-dual (OPD) method (18) in Appendix B.4. Compared with a contemporaneous work [40], OPD is free of projection to an occupancy measure set, and enjoys strengthened linear convergence.
OPD is an indirect policy search method that iterates using occupancy measure- based gradients, not policy-based gradients. is crucial to develop direct policy search methods that are widely-used in RL, which is our focus. We propose two such methods in Section 3 and Section 4, respectively.
3 Policy Last-Iterate Convergence: Regularized Method
Towards achieving policy last-iterate convergence, practical strategy is using regularization [52] to "convexify" Problem (3). We present a regularized method - Regularized Policy Gradient Primal- Dual (RPG-PD) that converges to saddle point that yields an optimal constrained policy.
3.1 Regularized policy gradient primal-dual method
We introduce regularized Lagrangian L, (T, A) ularization term 7(T=) + A onto the original Lagrangian V= (p), where T is a regularization
V (p) + (H((T) + 42²) by adding a reg-
parameter, and H(T)) == E E - log (a, [&)] is an entropy-like regularization term [52]. We now introduce regularized constrained saddle-point problem.
maximize minimize Ax, = minimize maximize xEΛ
(T,
(4)
Λελ
#ell
Problem (4) well-defined, since there exists a saddle point for L A) over II A and is unique; see Appendix C.I for proof. A saddle point (x,, {²), i... क = argmax, e n minxe E (, A) and x argminxe A max, II Ly (I,, A), satisfies sandwich-lik property,
V (P) (+( z Vi S (D) =x²² for all (T
(5)
that states that (= X2) is saddle point of the original Lagrangian V V (p), up to 7-terms. We thus propose a regularized policy gradient primal-dual (RPG-PD) method by maintaining sequence for policy and dual variables each: { for the policy-player, and {Aerr20 for the dual-player,
(-41(118) =
argmax (())))
Σ T(als) (tthsttt (s, (L( me())))
(6a)
7
Ac+1 argmin XEA
g (o) + 2n
- -
(6b)
where the gradient direction 1T- Agtto (s,a) a) is the state-action value function under composite function + Aug Tahy in which (8, a) == log ( 8), (L(P, Ea Pa log is the Kull-
V.
back-Leibler (KL) divergence, ((A) = (=(-|s)
1 a E A} is a restricted
probability simplex set with parameter eo (0, 1). r7 is the stepsize, and (#o(- (s)(]sss, Ao) E Â(A) A is an initial point. Projecting the policy iterate to the simplex set ((A) ensures the boundedness of the gradient. Primal update (6a) works as the classical mirror descent with KL divergence [53]
with projection onto the set Á(A). Dual update (6b) performs typical projected gradient descent. Hence, RPG-PD is a single-time-scal method. RPG-PD simplifies the -i--iime-scale method [34] to be single-time-scale and generalize the single-time-scale methods [23, 54] with regularization.
3.2 Policy last-iterate convergence
In Theorem 2, we show that the primal-dual iterates of RPG-PD converge in the last iterate; see Appendix C.2 for proof. We characterize the convergence via a distance metric D KL((p) +
(A; -2,,,, where KL.(p) == (1/(1- E, 43 (s) and KLę(s): == KL( se, (s))) Theorem 2 (Linear convergence of RPG-PD). Let Assumption I hold. If we set the stepsize S 1/Cr, then the primal-dual iterates of RPG-PD (6) satisfy
& D < e -nt art d + max ((Cr,5,00) (Chs)))
(A). where Cr,5,00 == (1+1/((11 (1) + log Al) (1-)) - Log(Eo/ Al). C+.s (1+7/5)/(1-7).
5

---

Theorem states that the primal-dual iterates of RPG-PD converge to a neighborhood of (#t, XP) in a linear rate, The size of neighborhood scales with n/TT 1 (1++og* so) and the convergence rate is m/. Even if 6o is very small, the log cu-term is almost constant. If we take 17 = min(er, 1/Cr, and 6o = e, then after ((1/c) iterations the RPG-PD's 's primal-dual iterate (Te, Ax) is e-close to (#, );), i... D2- (e) for any t 2 (1/(er")) log(1/)). For small 5, convergence for the value functions in Corollary 3; see Appendix C.3 for proof.
translate the policy
Corollary (Nearly-optimal constrained policy). Lel Assumption I hold. For small e > O, if we take 7E ( = +(E²). and Eo = e, then the policy iterates of RPG-PD (6) satisfy
Jorany/ V (p) -7) S e and Vo)(() S 6 .for any 1 52
(
1 c
log ! :
where ()()) only has some problem-dependee constant.
Corollary 3 states that the last policy iterate of RPG-PD is e-optimal policy for Problem (1) after 9(1/c9) iterations. Compared with the single-time-scae methods [23, 54], RPG-PD improves the convergence from average-value (or regret-type) to last policy iterute. Not just being theoretically stronger, the last-iterate convergence is more appealing since it captures the stability of trajectories of an algorithm [29, 40J. Compared with the two-time-scale methods [28, 24, 34, 351, RPG-PD is free of nested loops, and uniform ergodicity and exploratory initial state distribution. We notice that the dual methods [28, 24] yield distory-average policies and the dual methods [34, 35] return policies from a subroutine. In contrast, RPG-PD outputs a hearly-optimal policy in the last iterate, the first- of-its-kind in the constrained MDP literature, albeit the rate is worse than the average ones [23, 54].
To get zero constraint violation, i.e., V (p) 2 0 at some I, it is straightforward to employ conser- vative constraint V (p) 2 O with g' = 9= g- - (1 - 7)8 for some > O. When e is small enough, there always exists some 8 such that the policy iterates of RPG-PD (6) satisfy V, (p) V. (p) S and Ve 2 for large I; see Appendix C.4 for proof. Our zero constraint violation ensures the last policy iterate of RPG-PD to satisfy the constraint, which is not the zero average constraint violation in the episodic setting [55, 56]. Compared with the zero constraint violation of a policy induced by an average of past occupancy measures [42], RPG-PD's zero constraint violation directly settles the policy iterates down, which appears to be the first policy-based zero constraint violation.
Last but not least, the iteration complexity of RPG-PD is nearly-free of the MDP dimension, except for an log A |ttemm, which inherits the dimension- -ree property of the NPG methods [49, 57, 23]. Hence, it is ready to view RPG-PD as a variant of NPG methods and generalize RPG-PD to con- strained MDPs with large state spaces in the function approximation setting.
3.3 Linear function approximation case
To deal with large state spaces, we use a parametrized policy go with e E Idd' for RPG-PD (6) without restricting A (AA) where d much smaller than the size of state/action spaces. To introduce function approximation, we begin with a tabular softmax policy To s) = Σ.. explo..aa)) for all (s.a) E
exp(8..a)
S x A and f R AI, Connecting NPG to mirror descent [49, 58), we express RPG-PD (6) NPG method with the following update; see Appendix C.5 for proof,
Gs+1 O. + (1 F, VOLL-(TO, 2x)
(7a)
Aet1 = PA (11 (11 )x VV=""((0
(7b)
where F,(B,)t VOLL 21) is NPG direction, and (0) is the Fisher information ma-
trix for a policy ne. i.e., (,(() == B., d7 Bew not- | V = s) log (a [a] A
useful property of (7a) is that NPG can be related to a linear regression. For any policy ma and a state-action value function Q7² the associated compatible function approximation error is ((s.a)~=l (w V log Te(a s) (T (s,a)))),, where v(s, a) = d= (s)mT(a s) is state-action distribution. It is known that (7a) is equivalent to O++1 = O. + muut, where wt E argmin Ru Eq(w, 6z, v)) in which (s, = Q (s, a) and vi(s,a) = (r"*(s) (s) (al 8) (e.g.. [59, Lemma I)). In practice, only an approximate minimizer wi is avail- able if a sample-basee based algorithm is used, e.g., We Ro argmin w (w, O2 vt), where W > 0.
Eq(w,

---

useful generalization of the softmax policy to large state spaces is the log-linear policy based on linear function approximation. Let Φs.a ,a E 12d be feature map with |0 S 1 for each state-action pair a). A log-linear policy no: S (AA) is parametrized by parameter 0 E R
exp( 0z,a 0) To(a|s s) = Ea exp( @ 0)
for all (s.a) E S
which takes the tabular softmax policy special case, i.e., Φs,a is indicator function. We notice that V, log aa(a s) = 2,.a En (-(-| s) @ ]. Since the log-linear policy is invariant to any action-independent term, it is convenient to replace V log Te by ós,a and we introduce a sim- plified compatible function approximation error, Eq(w: 0,v) == B(a.a) (Ø a - - (s, (,,a)) Thus, we can take we E argmin Rd (w 02 1/) in which Q (s,a) = Q +rtggro (s, a) and ve(s,a) dp (s) ma, (a 8) to update 0.+1 0g + spet. Using the
policy class, we replace the primal gradient direction of RPG-PD (6) by its linear function approximation o uy.
Te (-1s) =
argmna a) Á(A)
{
Σ
x(a [Taaas)0 s)o.
1 KL(T(- no. (- { 77
(8)
which, together with Dual update (6b), leads to a general version of RPG-PD. The set ((A) en- sures bounded true gradient direction Q742igtt (s, a). When there is no function approximation error, (8) reduces to Primal update (6a). In practice, we can only compute wł approximately via
We
argmin Eq(w, 0c, de,.)
which leads to an inexact RPG-PD: Primal update (8) in which w is replaced by wy and Dual Te So, ag) is
update (6b), where dr,, == (s0 ~r Σi= Pr(s, = s, ar state-action distribution starting from any distribution v. Noticeably, de, is more general than vt. To control the function approximation error, we divide Eq (wr, Gr, de,)) into a statistical error Eq( (we, 0r, d - (q(w;, , 62, de,x) that is similar to the excess risk in supervised learning, and an approximation error Eq(wğ. 62, dr.,) that captures how well a linear function (wf)² Os.a approx- imates the true value function under de.-- If the on-policy distribution de, in Eq , 0r, de,)) is replaced by y" v"(s,a) a) d (s) (n), ance matrix of øs.a in any state-action distribution be Σ, := ([s nul w E.
define transfer error EQ(w7,0,, v²). Let the covari- & To s,a and the relative
condition number between E, and Ey, be Ni max ERd
w "I'.ww"
We make an assumption on the statistical error, the transfer error, and the relative condition number. Assumption 2. (i) There exist estas, Ehins > 0 such that EE[ [[Eo(w; , Oz, dr.)) - EE (wt Oc, de,)) ] S Extat
and & 02, D*)] S ébiasi (ūi The relative condition number is finite, i.e., Ky < CC.
We assess the convergence of inexact RPG-PD via the distance metric E [ == E (P) E (A; - -,,--,,, }, where the expectation is over the randomness of computing w, via a sample- based algorithm. We state the convergence in Theorem 4 and delay its proof Appendix C.6.
Theorem 4 (Linear convergence of inexact RPG-PD). Let Assumptions 1-2 hold. If we take the stepsize 17 S 1/Cw. then the primal-dual iterates of inexact RPG-PD satisfy
1 max ((Cw)², (C*s),(Chhs))) + 7 where Cw == 21/(1-12)) 7) and C² (1+ (1)
E [++1] < e e-1='E tb +
2
(ViAlebins + VIA Kutata
Theorem 4 states that the primal-dual iterates of inexact RPG-PD converge to a neighborhood of (T; At) in a linear rate. The convergence rate is 1fT and the size of neighborhood scales with a sum of an 1/ /tr-m and an 1/ 1-r-term that amplifies the effect of function approximation (Guat Chims) We note that, Theorem 4 does not require the strong duality in the parametrized policy class, and the function approximation error includes the duality gap caused by the inexpensiveness of function class and the policy representation error caused by the restricted policy set Á ().. When there is no function approximation error, Theorem 4 has similar result Theorem 2. It is important to control
7

---

(Estats Ebias) to be small: (i) Application of stochastic gradient methods to the linear regression leads to Sata = ((///)) or ()) where is the number of gradient steps, and thus, it is easy to control Estat (ii) When eo is very small, the parametrized policy iterate can be contained in (AA), and thus Ebios becomes zero in some cases, e.g., tabular softmax case [49] or low-rank MDPs [60, 61] with d 2 |A|; it can be made very small if the function class is rich, e.g., wide neural networks [62]. When the errors are small, it is ready to establish Corollary 5; see Appendix C.7 for proof.
Corollary& 5 (Nearly-optinee
constrained policy). Let Assumptions 1-2 hold and Cuas Chias O(e))
for small e, 6o > O. If we take the stepsize = O(()) and 7 = ( then the policy iterates of inexact RPG-PD satisfy
V, V, (p) S and E -V (p)] S for any t = 12 (
( 108821 !
E8
V (p)
where D)-)) only has some problem-depencee constant.
Corollary states that the iteration complexity in Corollary 3 holds in the function approximation case. When is small enough, can design conservative constraint such that the policy iterates of inexact RPG-PD satisfy V (p) Vi (p) I and V2, (p) 2 for large t; see Appendix C.8 for proof. Compared with the zero average constraint violation [63]. this appears to be the first policy- based constraint violation result in the function approximation setting. Moreover, we extend inexact RPG-PD to be a sample-base algorithm and provide its sample complexity in Appendix C.9.
4 Policy Last-Iterate Convergence: Optimistic Method
Having established sublinear policy last-iterate convergence via regularization, we turn the opti- mistic gradient method [37] for faster rate. We propose an optimistic method - Optimistic Policy Gradient Primal-Dual (OPG-PD)- that converges an optimal constrained policy linear rate.
4.1 Optimistic policy gradient primal-dual method
We propose an optimistic policy gradient primal-dual (OPG-PD) method by maintaining two se- quences for policy and dual variables each: (Te)22 and (#+J021 for the policy-player, and 2 and {ddee11 for the dual-player,
Te(-1 = argmax -(-1))EA(A))
| - -
2m
(9a)
1
#t4(-1|s)
argmax E(()))
x(als)(
|| (r(-1s) - 1e)-1,))1
201
d
argmin ΛEΛ
A AVT=-1 (p) +
() - 21)²
2n
(9b)
S011 = argmin XEA
A AV (p) +
(A {n}p
2m
where y is the stepsize and (fo, Ån) = (To, Ao) E x A is the initial point. OPG-PD concurrently works with two primal iterates and two dual iterates, and each two updated consecutively to stabi- lize the algorithm dynamics. The "optimistic" in optimization, e.g., [64] views (#z+1, Re+ 1 as real policy gradient step and (IE. A₂) -u)-up as prediction step that generates an intermediate iterate (TT, Ax). Not policy gradient at (ft, 2t), the real step uses a policy gradient at (T,, A²) from prediction, exhibiting the optimism towards the prediction. Specifically, Primal update (9a) works as the projected Q-ascent [58, 65], application of the classical mirror descent with Euclidean distance [53], where the projection onto a probability simplex can be solved efficiently [66]. Dual update (9b) performs standard projected gradient descent. We note that OPG-PD is different from the one-step multiplicative weights update in the policy- based ReLOAD [40].
When there is no MDP transition dynamics, i.e., constrained bandit [40], last-iterate convergence
of OPG-PD to saddle point known in the minimax optimization [67, 68, 38, 39], because Prob-
lem (3) reduces to a bilinear zero-sum game in this case. However, it is prohibitive to apply such
8

---

bilinear game results to the Lagrangian (g in every state s, as has been done for zero-sum Markov games [43, 44]. The main reason for this is that there may not exist an optimal constrained policy that is uniformly optimal across all states; see Appendix B.2.
4.2 Policy last-iterate convergence
We define the distribution mismatch coefficient over p as Kip := supTEn maximum distribution mismatch of policy и relative to p. where d is divided per state. Hence, d |l S kp/(L - 7) for any policy π E II and Kip I 1/Pminn where Pmin == ming p(s). The projection operator Px on a closed convex set X defines Px(x) := argmin x' E x || -
/ which is the
We state the policy last-iterate convergence of OPG-PD (9) in Theorem 6.
Theorem 6 (Linear convergence of OPG-PD). Let Assumption hold. Assume the optimal state visitation distribution be unique, i.e., dz = d for any II", and pmii O. we set the stepsize 7 & min (1/(4V0), (1-7))/(4|A4))) (1 (1-1) (2xx/(2xx))) where i > 0 is defined in Appendix D.I,
then the primal-due iterates of OPG-PD (9) satisfy
di (s) PP (ft(- s)) (s)1 + 1 -
2(1 7) Σ
(I+C)
where C' =- min(7(1 - 7)88 7n/² (1 (C, Pmiin (2xip.)))) in which Cp.s and Kp,yy are given + 1/((1- 7)))), Kpp. == max(K//(( (1-7),1) and e > 0 is a
by Cp. == cpmin/ (2tmn//22////1/// problem-dependent constant from Lemma 26.
Theorem 6 states that the primal-dual iterates of OPG-PD converge II X A in linear rate, or putting it differently, (9) is contracting to a set of optimal primal/dual variables. The rate is governed by problem-dependent constant. Proof of Theorem 6 is provided in Appendix D. A key to our analysis is to bridge the per-state policy gradient update and the policy improvement for (p))(p) (p) that is non-convex in policy æ. which departs from the convex last-iterate analysis [38, 39]. In addition, prevents learning an optimal policy from per-state bilinear games in zero-sum Markov games [43, 44]. Instead, characterize the proximity of primal-dual iterates an optimal state visitation distribution d Second, Problem (3) is an asymmetric game since one plays a stochastic policy over a finite set of discrete actions and controls the transition dynamics, but the other selects an action in continuous interval. Thus, dual-player analysis handles the long-term effect of the policy-played which did not appear in the symmetric game [43, 44].
address two technical difficulties. First, the lack of uniformly optimal policies
saddle point supported by
A direct corollary of Theorem 6 is stated below; see Appendix D.3 for the proof.
Corollary (Neaaly-optimal constrained policy). Let Assumption I hold and the optimal state visi- tation distribution be unique, i.e., d; d, for any IIo, and Puin > O. we use the stepsize from Theorem 6, then the policy iterates of OPG-PD (9) satisfy
V (p)- c and - -V (p) S e for foyanyt t St log" 1 é
where 12--) only has some crroblem-depencee constant.
Corollary states that the last policy iterate of OPG-PD is an e-optimal policy for Problem (1) after an almost constant number of iterations, which improves the sublinear rate in Corollary 3. OPG- PD also improves the average-vally convergence of the single-time-scale methods [23, 54] and the two-time-scale methods [28, 24, 34, 35), and matches the last-iterate convergence rate of the two- time-scale methods [34, 35]. We stress that our last-iterate convergence indicates the stability of whole primal-dus iterates, which is not the last policy iterate from subroutine [34, 35]. Again, when E is small, we can design conservative constraint such that the policy iterates of OPG-PD satisfy V." (p) V (p) < e and v²x(p) (p) 2 for large t; see Appendix D.4 for the proof.
5 Computational Experiment
We validate the effectiveness of RPG-PD (6) and OPG-PD (9) by comparing them with typical primal-dual methods in Figure 1. A few observations are in order. The initial oscillation of RPG-PD

---

(--) is damped, and OPG-PD (-) is almost free oscillation as PID Lagrangian (...). However, oscillation of NPG-PD (--) causes its last-iterate policy violating the constraint V 2 0. OPG- PD (-) reaches the maximum reward value in four methods and RPG-PD (--) converges to slightly smaller value due regularization, while both meet the constraint at the end. However, PID Lagrangian (1...) highly sub-optimal. Hence, our methods OPG-PD and RPG-PD can overcome oscillation and approach nearly-optine constrained policy in the last-iterate fashion.
Reward value
Utility value
0.5
Iteration
Iteration
Figure 1: Convergence performance of RPG-PD, OPG-PD, and primal-dual methods. Learning curves of our RPG-PD (--) and OPG-PD (-), and NPG-PD [23] (--) and PID Lagrangian [29] (--.)
methods. The horizontal axes mean the policy iterations { 2 that are generated by each method and the vertical axes mean the value functions of the policy iterates { h 20: reward value V (p) (Left) and utility value V (p) (Right). In this experiment, we use the same stepsize 0.1 for all methods, the regularization parameter T = 0.08 RPG-PD, and the uniform initial distribution p.
We showcase the linear convergence of OPG-PD (9) with three constant stepsizes in Figure 2. Three policy optimality gaps decrease linearly in the logarithmic scale plot, which verifies the linear last- iterate convergence of OPG-PD's policy iterates in Theorem Noticeably, there is no oscillation behavior in OPG-PD's policy iterates, which perhaps is best for learning constraints [29, 10]. We also see that large stepsize 17 = 0.2 improves the convergence, which is reflected by our rate.
Policy optimality gap
1339
Iteration
Figure 2: Convergence performance of OPG-PD with stepsize vp: (n = 0.05, ..... (n = 0.1, -.-),
(n 0.2, -). The horizontal axis represents the policy iterations { o that generated by OPG-PD and the vertical axis means the policy optimality gap that measures the distance of the policy iterates (=. to an optimal policy nh: Σ. (-((-s)) T- (-| In this experiment, we take the initial distribution p to be uniform one.
Please Appendix E for more details of this experiment, more baselines, and sensitivity analysis.
Concluding Remarks
We have presented two single-time-scale policy-based primal-dual methods for finding an optimal policy of constrained MDP, with global non-asymptotic and last-iterate policy convergence guar- antees. Our first regularized method enjoys nearly dimension-fiee sublinear rate, while our second optimistic method possesses a linear rate that is problem-dependent. Our work stimulates a num- ber of compelling future directions: (i) Our problem setting circumvents the exploration difficulty, which leaves online exploration open; (ii) Our convergence rates are not as sharp as solving convex- concave minimax optimization problems, regarding the order or instance-relate constant; (iii) Last- iterate convergence under-examined in constrained MDPs with other constraints, and unexplored for other gradient methods.
10

---

Acknowledgments and Disclosure of Funding
D. Ding and A. Ribeiro supported by THEORINET Simons-NSF MoDL, and DCIST CRA. K. Zhang acknowledges the support from Jimons-Berkelye Research Fellowship and Northrop Grumman Maryland Seed Grant Program.
References
[1] Frederick J Beutler and Keith Ross. Optimal policies for controlled Markov chains with constraint. Journal of Mathematical Analysis and Applications, 1 112(1):236-252, 1985.
[2] Keith W Ross. Randomized and past-dependent policies for Markov decision processes with multiple constraints. Operations Research, 37(3):77-477, 1989.
[3] Alexey Piunovskiy. Control of random sequences in problems with constraints. Theory of Probability & Its Applications, 38(4):751-76,, 1994.
[4] Eugene A Feinberg and Adam Shwartz. Constrained discounted dynamic programming. Mathematics of Operations Research, 21(4):922 945, 1996.
[5] Eitan Altman. Constrained Markov decision processes, volume 7. CRC press, 1999.
[6] Vivek S Borkar. An actor-critic algorithm for constrained Markov decision processes. Sys- tems Control Letters, 54(3):207-213, 2005.
[7] Naoki Abe, Prem Melville, Cezar Pendus, Chandan K Reddy, David Jensen, Vince Thomas, James Bennett, Gary F Anderson, Brent Cooley, Melissa Kowalczyk, et al. Optimizing debt collections using constrained reinforcement learning. In Proceedings of the 16th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 75-84, 2010.
[8] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimiza- tion. Proceedings of the International Conference on Machine Learning, pages 22-31, 2017.
[9] Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimiza- tion. In Proceedings of the International Conference Learning Representations, 2019.
[10] Gabriel Dulac-Amold, Nir Levine, Daniel Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 10(9))2419-2468. 2021.
[11] Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang, Derek Pang, Rene Claus, Ching-Han Chiang, et al. Muzero with self- competition for rate control in VP9 video compression. arXiv preprint arXiv:2202.06622 2022.
[12] Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Auto- matic Control, 2022.
[13] Xiangkun He, Haohan Yang, Zhongxu Hu, and Chen Lv. Robust lane change decision making for autonomous vehicles: An observation adversarial reinforcement learning approach. IEEE Transactions on Intelligent Vehicles, 2022.
[14] Ziqing Gu, Lingping Gao, Haitong Ma, Shengbo Eben Li, Sifa Zheng, Wei Jing, and Junbo Chen. Safe-state enhancement method for autonomous driving via direct hierarchical rein- forcement learning, IEEE Transactions Intelligent Transportation Systems, 2023,

---

[15] Dan A Calian, Daniel Mankowitz, Tom Zahavy, Zhongwen Xu, Junhyuk Oh, Nir Levine, and Timothy Mann. Balancing constraints and rewards with meta-gradient D4PG, In Pro- ceedings of the International Conference on Learning Representations, 2021.
[16] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk- constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-6120 2017.
[17] Javier Garcia and Fernando Fernández. comprehensive survey on safe reinforcement learn- ing. Jourmal of Machine Learning Research, 16(1):1437-148)) 2015.
[18] Frits De Nijs, Erwin Walraven, Mathijs De Weerdt, and Matthijs Spaan. Constrained mul- tiagent Markov decision processes: A taxonomy of problems and algorithms. Journal of Artificial Intelligncee Research, 70:955-1001, 2021.
[19] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in roboties: From learning-based control to safe rein- forcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5:411- 1- 444, 2022.
[20] Shangding Gu, Long Yang, Yali Du, Guang Chen, Florian Walter, Jun Wang, Yaodong Yang, and Alois Knoll. A review of safe reinforcement learning: Methods, theory and applications. arXiv preprint arXiv: 103300 2022.
[21] F Vazquez Abad, Vikram Krishnamurthy, Katerine Martin, and Irina Baltcheva. Self learning control constrained Markov chains a gradient approach. In Proceedings of the 41st IEEE Conference Decision and Control, volume 2, pages 1940-1945, 2002.
[22] Shalabh Bhatnagar and K Lakshmanan. An online actor-critic algorithm with function ap- proximation for constrained Markov decision processes. Journal of Optimization Theory and Applications, 153:688-700 708, 2012.
[23] Dongsheng Ding, Kaiqing Zhang, Tamer Başar, and Mihailo R Jovanović. Natural policy gradient primal-dual method for constrained Markov decision processes. Proceedings of the Advances in Neural Information Processing Systems, 33:8378-8390, 2020.
[24] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Policy optimization for constrained MDPs with provable fast global convergence. arXiv preprint 1xXi:2111.00055: 2021.
[25] Arushi Jain, Sharan Vaswani, Reza Babanezhad, Csaba Szepesvari, and Doina Precup. To- wards painless policy optimization for constrained MDPs. In Proceedings of the Uncertainty in Artificial Intelligence, pages 895-905, 2022.
[26] Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time complexity of online primal- dual natural actor-critic algorithm for constrained Markov decision processes. Proceedings of the IEEE 6lst Conference on Decision and Control, pages 4028-4033, 2022.
[27] Yi Chen, Jing Dong, and Zhaoran Wang. A primal-dual approach to constrained Markov decision processes. arXiv preprint arXiv:2101.10895 2021.
[28] Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang and Guanghui Lan. Faster algorithm and sharper analysis for constrained Markov decision process. arXiv preprint wrxiv:2110.1035)) 2021.
[29] Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learn- ing by PID Lagrangian methods. Proceedings of the International Conference on Machine Learning, pages 9133-9143, 2020.
12

---

[30] Miguel Calvo-Fullana, Santiago Paternain, Luiz FO Chamon, and Alejandro Ribeiro. State augmented constrained reinforcement learning: Overcoming the limitations of learning with rewards. IEEE Transactions on Automatic Control, 2023.
[31] Kenneth J. Arrow, Leonid Hurwicz, and Hirofumi Uzawa. Studies in linear and non-linear programming. Stanford University Press, 1958.
[32] Galina M Korpelevich. The extragradient method for finding saddle points and other prob- lems. Matecon, 12:747-756, 1976.
[33] Angelia Nedié and Asuman Ozdaglar. Subgradient methods for saddle-poii problems. Jour- nal of Optimization Theory and Applications, 142:205-228, 2009.
[34] Donghao Ying. Yuhao Ding, and Javad Lavaei. A dual approach to constrained Markov de- cision processes with entropy regularization. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 1887-1909, 2022.
[35] Egor Gladin, Maksim
Karina Zainullina, Varvara Rudenko, Alexander Gasnikov, and Martin Takac. Algorithm for constrained Markov decision process with linear convergence. In Proceedings of the International Conference on Artificial Intelligence and Slafistics, pages 11506-1153. PMLR, 2023.
[36] Tianqi Zheng. Pengcheng You, and Enrique Mallada. Constrained reinforcement learning via dissipative saddle flow dynamics. arXiv preprint arXiv:2212.01505,, 2022.
[37] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the con- vergence of single-call stochastic extra-gradient methods. Proceedings of the Advances in Neural Information Processing Systems, 32, 2019.
[38] Chen-Ye Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate con- vergence in constrained saddle-point optimization. In Proceedings of the International Con- ference on Learning Representations, 2020.
[39] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv preprint arXiv:2204.09223 092220 2022.
[40] Ted Moskovitz, Brendan O'Donoghue, Vivek Veeriah, Sebastian Flennerhag, Satinder Singh, and Tom Zahavy. ReLOAD: Reinforcement learning with optimistic ascent-descent for last- iterate convergence in constrained MDPs. arXiv preprint arXiv:2302.01275. 2023.
[41] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. In Proceedings of the Advances in Neural Information Processing Systems, volume 35, pages 31 3110-3122, 2022.
[42] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achiev- ing zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3682- 3689, 2022.
[43] Chen Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in sefnite-horizon competitive Markov games. In Proceedings of the Conference on learning theory, pages 4259 4299, 2021.
[44] Zhuoqing Song, Jason Lee, and Zhuoran Yang. Can we find Nash equilibria at a linear rate in Markov games? In Proceedings of the International Conference on Learning Representa- tions, 2023.
[45] Dimitri Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic Press, 2014.
13

---

[46] Csaba Szepesvári. Constrained MDPs and the reward hypothesis. http://readiineem.. blogspot com/2020/08 200020003//0 hts//onstraaine-maeee mdps- seapss-addreeaae and html,, 2020. Access on January 21, 2023.
[47] Tom Zahavy, Brendan O' O'Donoguue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex MDPs. Proceedings of the Advances Neural Information Processing Systems, 34:25746-25777 2021.
[48] Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Başar, and Mihailo R Jovanovié. Con- vergence and sample complexity of natural policy gradient primal-dual methods for con- strained MDPs. arXiv preprint arXiv:2206.022 02366, 2022.
[49] Alekh Agarwal, Sham M Kakade, Jason D Lee. and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4506 2021.
[50] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021.
[51] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the International Conference on Machine Learning, pages 4890-4900 2020.
[52] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global conver- gence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563-2578, 2022.
[53] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends() in Machine Learning, 8(3-4):231-357, 2015.
[54] Dongsheng Ding and Mihailo R Jovanović. Policy gradient primal-dual mirror descent for constrained MDPs with large state spaces. Proceedings of the IEEE ó1st Conference on Decision and Control, pages
2022.
[55] Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained MDPs. Proceedings of the Advances Neural Information Processing Systems, 34:17183-17193, 2021.
[56] Honghao Wei, Xin Liu, and Lei Ying. Triple-Q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 3274-3307, 2022.
[57] Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competi- tive games with entropy regularization. Proceedings of the Advances in Neural Information Processing Systems, 34:27952-27964, 2021.
[58] Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages
2021.
[59] Rui Yuan, Simon Shaolei Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with lonear policies. In Proceedings of the International Conference on Learning Representations, 2022.
[60] Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In Proceedings of the International Conference on Machine Learning, pages 6995- 7004, 2019.
14

---

[61] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforce- ment learning with linear function approximation. In Proceedings of the Conference Learning Theory, pages 2137-2143, 2020.
[62] Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In Proceedings of the International Conference on Leurning Representations, 2020.
[63] Qinbo Bai, Amrit Singh Bedi, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 6737-6744, 2023.
[64] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the Conference on Learning Theory, pages 993-1019. PMLR, 2013.
[65] Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282): 1-36, 2022.
[66] Laurent Condat. Fast projection onto the simplex and the I ball. Mathematical Programming, (58555):555-588 2016.
[67] C Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and con- strained min-max optimization. In Proceedings of the Innovations in Theoretical Computer Science (ITCS) Conference, 2019.
[68] Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, et al. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In Proceedings of the International Conference Artificial Intelligence and Statistics, pages 1441-1449, 2021.
[69] Dongsheng Ding, Kaiqing Zhang, Tamer Başar, and Mihailo Jovanović. Convergence and optimality of policy gradient primal-dual method for constrained Markov decision processes. Proceedings of the American Control Conference, pages 2851 1-56,,, 2022.
[70] Ruida Zhou, Tao Liu, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Anchor- changing regularized natural policy gradient for multi-objective reinforcement learning. In Proceedings of the Advances Neural Information Processing Systems, 2022.
[71] Aria HasanzadeZonuzz, Dileep Kalathil, and Srinivas Shakkottai. Model-based reinforce- ment learning for mainite-horizon discounted constrained Markov decision processes. In Proceedings of the International Joint Conference on Artificial Intelligence, 2021.
[72] Leonid Denisovich Popov. A modification of the Arrow-Hurwizz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28:845-88 848, 1980.
[73] Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimiza- tion for safe reinforcement learning. In Proceedings of the Advances in Neural Information Processing Systems, volume 32, 2019.
[74] Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter Ramadge. Projection- based constrained policy optimization. In Proceedings of the International Conference Learning Representations, 2020.
[75] Yiming Zhang, Quan Vuong, and Keith Ross. First order constrained optimization in policy space. In Proceedings the Advances in Neural Information Processing Systems, volume 33, pages 15338-15344 2020.
[76] Long Yang, Zhang, Jiaming Ji, Juntao Dai, and Weidong Zhang. CUP: A conservative update policy algorithm for safe reinforcement learning, 2022.
15

---

[77] Tengyu Xu, Yingbin Liang, and Guanghui Lan. CRPO: A new approach for safe reinforce- ment learning with convergence guarantee. In Proceedings of the International Conference on Machine Learning, pages 11480-11491, 2021.
[78] Yongshuai Liu, Jiaxin Ding, and Xin Liu. IPO: Interior-point policy optimization under constraints. In Proceedings of the AAAI Aonference on Artificial Intelligence, volume 34, pages 4940-4947, 2020.
[79] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploiaaion in constrained MDPs. arXiv preprint arXiv:2003.c 02000. 189, 2020.
[80] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanović. Provably efficient safe exploration via primal-dual policy optimization. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 3304-334 3312, 2021.
[81] Liyun Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Proceedings of the Learning for Dynamics and Control, pages 620-629, 2020.
[82] Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual reinforcement learning for CMDP with adversarial loss. In Proceedings of the Advances in Neural Information Processing Systems, volume 33, pages 15277-15287, 2020.
[83] Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave- convex and knapsack settings. In Proceedings of the Advances in Neural Information Pro- cessing Systems, volume 33, pages 16315-16326. 2020.
[84] Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi-objective competitive RL. In Proceedings of the International Conference on Machine Learning, pages 12167-12176, 2021.
[85] Thiago Simão, Nils Jansen, and Matthijs TJ Spaan. AlwaysSafe: Reinforcement learning without safety constraint violations during training. In Proceedings of the 20th International Conference on Autonomous Agents and Multi-Agent Systems, pages 1226-1235, 2021.
[86] Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. sample-efficient algorithm for episodic finite-horizon MDP with constraints. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 8030-8037, 2021.
[87] Sobhan Miryoosefi and Chi Jin. A simple reward-free approach to constrained reinforcement learning. In Proceedings of the International Conference Machine Learning, pages 15666- 15698, 2022.
[88] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficien model-free algorithm for infinite- horizon average- constrained Markov decision processes. Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 1868-3876, 2022.
[89] Liyu Chen, Rahul Jain, and Haipeng Luo. Learning infinite-horizzt average- reward Markov decision process with constraints. In Proceedings of the International Conference on Machine Learning, pages 3246-3270, 2022.
[90] Archana Bura, Aria HasanzadeZonuzy, Dileep Kalathil, Srinivas Shakkottai, and Jean- Francois Chamberland. DOPE: Doubly optimistic and pessimistic exploration for safe re- inforcement learning. In Proceedings the Advances in Neural Information Processing Systems, volume 35, pages 1047-1059, 2022.
[91] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained RI. with linear function approximation. Proceedings of the Advances in Neural Information Processing Systems, 2022.
16

---

[92] Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning in constrained Markov decision processes. IEEE Transactions Control of Network Systems, 10(1):441-433, 2022.
[93] Honghao Wei, Arob Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. Provably efficient model-free algorithms for non-stationary CMDPs. In Proceedings of the International Con- ference on Artificial Intelligence and Statistics, pages 6527-6570, 2023.
[94] Jacopo Germano, Francesco Emanuele Stradi, Gianmarco Genalti, Matteo Castiglioni, Al- berto Marchesi, and Nicola Gatti. A coat-of-both-worlld algorithm for constrained MDPs with long-term constraints. arXiv preprint arXiv:2304. /4326, 2023.
[95] Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. Safe posterior sampling for con- strained MDPs with bounded constraint violation. arXiv preprint arXiv:2301.11547 2023,
[96] Soumyajit Guin and Shalabh Bhatnagar. A policy gradient approach for finite horizon strained Markov decision processes. arXiv preprint arXiv:2210.04527, 2022.
[97] Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained reinforcement learning has zero duality gap. In Proceedings of the Advances in Neural Information Processing Systems, 2019.
[98] Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: generalized framework with linear convergence. SIAM Journal on Optimization, 33(2): 2023.
[99] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming, 198(1):105--110) 2023.
[100] Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-25,, 1995.
[101] Yu Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimizatioo, 25(1):502-52) 2015.
[102] Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min- max optimization: Convergence of Hamiltonian gradient descent and consensus optimization. Proceedings of the Algorithmic Learning Theory, pages 3-47, 2021.
[103] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclusions and constrained nonconvex-nonconcave min-max optimization. arXiv preprint arXiv:2206.05248, 2022.
[104] Quoc Tran-Dinh. hypomonotone inclusions. arXiv preprint arXiv:2302. 04099, 2023.
Extragradient-lype methods with
rates for co-
[105] Stephen J Wright. Primal-dual interior-point methods. SIAM, 1997.
[106] Michele Benzi, Gene H Golub, and Jörg Liesen. Numerical solution saddle point problems. Acta Numerica, 14: 14:1-137, 2005.
[107] Kenneth J Arrow and Leonid Hurwiez. Reduction of constrained maxima to saddle-poin problems. In Traces and Emergence of Nonlinear Programming, pages 61-80. 2013.
[108] Kazufumi Ito and Karl Kunisch. Lagrange multiplier approach to variational problems and applications. SIAM, 2008
[109] Bingsheng He and Xiaoming Yuan. On the acceleration of augmented Lagrangian method for linearly constrained optimization. Optimization Online, 3, 2010.
17

---

[110] Alp Yurtsever, Quoe Tran Dinh, and Volkan Cevher. universal primal-dual convex op- timization framework. In Proceedings of the Advances in Neural Information Processing Systems, volume 28, 2015.
[111] Bingsheng He and Xiaoming Yuan. On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers. Numerische Mathematik, 130(3)567-5777, 2015.
[112] Ya-Feng Liu, Xin Liu, and Shiqian Ma. On the nonergodic convergence rate of an inex- act augmented Lagrangian framework for composite convex programming. Mathematics of Operations Research, 44(2):632-650, 2019.
[113] Yangyang Xu. Iteration complexity of inexact augmented Lagrangian methods for con- strained convex programming. Mathematical Programming, 185:199-244, 2021.
[114] Quoe Tran Dinh. Non-ergodic alternating proximal augmented Lagrangian algorithms with optimal rates. Proceedings of the Advances in Neural Information Processing Systems, 31, 2018.
[115] Quoc Tran-Dinh and Yuzixuan Zhu. Augmented Lagrangian-based decomposition methods with non-ergodic optimal rates. arXiv preprint 180.vv/800.05222 2018.
[116] Shoham Sabach and Mare Teboulle. Faster Lagrangian- based methods in convex optimiza- tion. SIAM Journal on Optimization, 32(1):204-22 227, 2022.
[117] Tao Zhang, Yong Xia, and Shiru Li. Lagrangian- based methods convex optimiza- tion: prediction-correction frameworks with non-ergodic convergence rates. arXiv preprint arXiv:2304.02459, 2023.
[118] Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non- convex constrained optimization. In Proceedings of the Algorithmic Learning Theory, pages 300-332, 2019.
[119] Richard Bellman and Stuart Dreyfus. Functional approximations and dynamic programming. Mathematics of Computation, 13668:2247-251, 1959.
[120] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[121] Wenhao Zhan, Baihe Huang. Audrey Huang. Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Proceedings of the Conference on Learning Theory, pages 2730-2775, 2022.
[122] John Nash Jr. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951.
[123] Vivek S Borkar. A convex analytic approach Markov decision processes. Probability Theory and Related Fields, 78(4):583-602, 1988.
[124] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Cautious reinforcement learning via distributional risk in the dual domain. IEEE Journal on Selected Areas in Infor- mation Theory, 2(2):61 1--626, 2021.
[125] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achiev- ing zero constraint violation for concave utility constrained reinforcement learning via primal-dual approach. 2022.
[126] Donghao Ying, Mengzi Amy Guo, Yuhao Ding, Javad Lavaei, and Zuo-Jun Shen. Policy- based primal-dual methods for convex constrained Markov decision processes. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10963-10971, 2023.
[127] Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176. 1958.
18

---

[128] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the International Conference Machine Learning, pages 928-936, 2003.
[129] Yasushi Terazono and Ayumu Matani. Continuity of optimal solution functions and their conditions on objective functions. SIAM Journal on Optimization, 25(4):2050-2000, 2015.
[130] Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach to obtaining an ((1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:/212.2002, 2012.
[131] Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv preprint arX11:2110.0011,, 2021.
[132] Haipeng Luo. Introduction to online optimization//laaiing: Lecture 1. https: pdf, 2022.
/ //haipeng-lun 1uo.umu.... wweengluo.nee//outtee (ttprreeeesSSI66///222aaaaa///
Access on January 21, 2023.
19

---

Supplementary Materials for "LasttIterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs"
A More Comparisons and Additional Related Works
In this section, we discuss more comparison details and other related works.
Iterate Type
Method
Single-time-scale
Complexity
Saddle flow dynamics [36]
Yes
asymptotic
Occupancy measure
ReLOAD [40]
Yes
asymptotic
OPD (18)
Yes
Ω (log" :)
Dual descent [34]
No
Q (1og" 2
Cutting-plane [35]
No
Ω (log") :)
Policy
Policy-based ReLOAD [40]
Yes
RPG-PD (6)
Yes
Ω ( t/b log" 2
OPG-PD (9)
Yes
Ω (log² 1
Table 1: Iteration complexities of our methods and representative algorithms for solving a con- strained MDP problem: maximize, (F()) subject to VTT(e) 2 0 with reward/utility functions [0, 1), و []. The iteration complexity is the number of gradient-based updates for an algorithm to output the last policy-iteran n, that satisfies (p) (p) S c and -V (p) S.
Last-iterate and value-average (or policy-mixture) performance in constrained MDPs. There has been a flurry of research activities in studying convergence behaviors direct policy search or policy gradient-based algorithms for constrained MDPs in the infinit-hhrizon discounted setting. There are two main streams: (i) Lagrangian- -based policy search and (ii) Approximate constrained policy search.
(i) Lagrangian-basee based policy search. In the Lagrangian-bart based framework, last-iterate perfor- mance has been established as asymptotic convergence for several policy-basee -ased primal-dual algorithms, e.g., naive policy gradient- gradient-based primal-dus method [21] and actor-critic vari- ants of policy gradient primal-dual methods [6, 22, 16, 9]. These studies rely modeling primal-dual updates two separate time scales and/or two nested loops as continuous time gradient flow dynamics, and their asymptotic convergence is often restricted to some sta- tionary points. We notice that recent global asymptotic convergence results [36, 40] are in terms of occupancy measure iterates instead of instantaneous policy iterates, highlighted in Table 1. In contrast, our first method: OPD strengthens the asymptotic last-iterate con- vergence asympttiiii and last-iterate convergence with linear rate.
To provide efficiency and optimality performances, crucial to develop algorithms with global aon-asyyptotic convergence guarantees. Several recent policy-based primal-dual al- gorithms have been proved to converge with non-asymptotic convergence rates, e.g., policy gradient primal-dual method [69], natural policy gradient-based or policy mirror-descent style primal-dual methods [23, 27, 54], accelerated natural policy gradient-based primal- dual methods [24, 25, 28), actor-critic version of natural policy gradient-based primal-dual
20

---

method [26], and anchor-changing natural policy gradient-basee primal-dual method [70]. These studies characterize non-asympiotic convergence to an optimal constrained policy regarding the average of value functions, except for [27] in which the convergence is for mixture of past policies and [28] in which the convergence is for a policy induced by a history-weighted occupancy measure. Similar non-asymptotie convergence can also be ceasure-bbsed primal-dual method [42], where the convergence is
found in occupancy in terms of the average of occupancy measures. Besides, sublinear non-asymptotic con- vergence can be found in generative model-based methods [71, 41], regarding mixture of past policies. In contrast, our two policy-based methods: RPG-PD and OPG-PD strengthen the sublinear non-asymptotic convergence of average value functions or a mixture of past policies to sublinear and linear non-asympiotic convergence of policy iterates. In particu- lar, we exploit the regularization technique [52] and the optimistic gradient method [72, 37] to augment typical policy-based primal-dual methods with novel identification of decreas- ing distances of policy iterates an optimal constrained policy, which allows for stronger convergence.
Instead of working with policy primal and dual variables both, Lagrangian- dual method formulates a constrained MDP as convex dual problem that enables classical dual ascent method [12]. Despite guaranteed convergence in dual space from convex opti- mization, it is challenging to compute an optimal constrained policy in primal policy space even if we use an optimal dual variable [9, 47, 30J. Recently, regularization [52] has been used in dual ascent methods 35] in which policy last-iterates of natural policy gradient- based subroutines can be nearly-optimal. These dual-based algorithms [34, 35] work with two nested loops and their non-asymptotic last-iterate convergence relies on tuning loop parameters optimally. In contrast, our two policy- methods: RPG-PD and OPG-PD remove the double loop requirement as listed in Table 1, which permits outputting the last- iterate policy as a nearly-optimal constrained policy. In Table I, we see that our RPG-PD method has worse rate while OPG-PD achieves a linear rate which is similar as the dual- based methods [34, 35]. Importantly, our non-asymptotic convergence characterizes the stability of primal-dual iterates generated by the algorithms,, which is theoretically stronger and more appealing in practice.
(ii) A Approximate constrained policy search. Approximation of constrained MDPs with sur- rogate funetions has been shown to be effective, e.g., constrained policy optimization [8], successive convex relaxation [73], projection-basee based constrained policy optimization [74], first-order constrained optimization [75], and conservative policy update [76]. These stud- ies have shown impressive empirical performance by iteratively solving an approximated constrained optimization problem and such performance is characterized in the worst-case policy improvement, except for [73] in which local asymptotic convergence is established, which leaves non-asymptotic convergence of policy iterates open. A related approach is the primal method [77] that treats constrained MDP as unconstrained one and corrects pol- icy iterates whenever constraint violation happens. Non-asymptotic convergence of primal method has been established in terms of mixture of past policies. Another approximation method is the interior-point policy optimization [78] that solves an unconstrained MDP by adding a logarithm barrier function into the objective function, while convergence of this method is unknown. In contrast, we have supported our methods with non-asymptotic last-iterate convergence. Since Lagrangian-basse based methods are typically used to solve an approximated constrained optimization problem [8, 74, 75, 76), our methodologies can be applied these methods for better convergence, which we leave as future work.
For constrained MDPs in the finite-horizon episodic setting and the total or average-reward settings, there is rich line of works that have developed learning algorithms with non-asymptotic conver- gence guarantees in terms of the average of value functions [79, 80, 81, 82, 83, 84, 85, 55, 86, 87, 88, 89, 56, 90, 91, 92, 93, 94, 95], except for [96] in which global asymptotic convergence of policy gradient method has been established in the finite-horizon constrained MDP setting. Although being not directly comparable, their non-as msymsttpttoicc and last-iterate convergence not established yet, to the best of our knowledge.
Sngrangian-basel policy gradient methods in constrained MDPs. Our methods are closely per- tinent to Lagrangian-based policy gradient methods for solving constrained MDPs in the infinite- horizon discounted setting, e.g., policy gradient-hased primal-dual methods [21, 6, 22, 16, 9, 69),
21

---

natural policy srudient-based or mirror-descent style primal-dual methods [23, 27, 28, 24, 54, 25, 26], dual descent methods [97, 34, 35, 12]. Regarding algorithm implementation, primal-dual meth- ods [21, 6, 22, 16, 9, 23, 27, 28, 24, 54, 25, 26, 69] work with primal-dual iterates simultaneously in single loop, which is similar to the classical gradient-based primal-dual methods in constrained op- timization [31, 32, 33], while diminishing stepsizes in different speeds is often required in many of them [21, 6, 16, 9]: dual descent methods 39,,34 35, 12] intermittently operate the dual iterate only after a sufficient number of primal iterations, which often adds difficulty of tuning hyper-parameten of nested loops in practice. It is worth mentioning that, it is convenient to view such dual descent methods as primal-dual methods that update primal variable faster than iterating dual variable. With respect convergence analysis, stochastic approximation has been widely used to establish asymp- totic convergence of several primal-dual methods [6. 22, 16, 9] by analyzing the stability of limiting gradient flow dynamics, while recent methods [28. 24, 54, 25, 26, 69, 34, 35] exploit the connec- tion between policy gradient and mirror-descent in convex optimization to prove non-asymptotic convergence. However, non-asymptotic convergence of primal-dual methods only characterizes the average of value functions [23, 54, 25, 26, 69] or mixture of past policies [27, 28, 24] because of the dual update that results from regulating constraint violation. For the dual descent meth- ods [34, 35], non-asymptotic convergence is characterized in terms of last-iterate policies that are computed by approximately solving unconstrained RI. problems with fixed dual variables. There- fore, designing Lagrangian-based policy gradient methods that enjoy the single-loop simplicity and the non-asymptotic convergence of policy iterates is challenging. because of the oscillation and overshoot issues of updating primal-dual variables simultaneously [29, 40J. In this work, we have established non-asymptotic and last-iterate convergence of two single-loop Lagrangian- policy gradient methods via the regularization and optimistic gradient techniques and our analysis builds on the distance of policy iterates, which is stronger than the prior art. Compared with recent efforts [40, 36] as shown in Table 1, our algorithms are simpler and our theoretical guarantees are stronger.
analysis for policy gradient methods [49, 98, 65, 99] while focusing on the
Gradient-based methods with last-iterate convergence for learning in games. Since the Lagrangian-based approach for constrained MDPs can be viewed as solving a constrained saddle- point problem, another line of related work is gradient-based methods for solving saddle-point (or minimax optimization) problems with last-iterate convergence. Last-iterate convergence of gradient- based methods has been established in several scenarios, e.g., linear rates of extragradient meth- ods for strongly convex problems [100, 101], asymptotic convergence of optimistic multiplicative weights updates for convex problems [67, 68]. linear rates of optimistic gradient methods for convex problems [43], and lower bound-mo matching rates of extragradient and optimistic gradient methods for convex problems [39]. These studies focus convex-concave saddle poidee-pointtt problems except for [102, 103, 104] in which non-asymptotic last-iterate convergence is achievable for madle--oint problems with special non-convexity structure. In contrast, our constrained saddle-poin problem that result from constrained MDP is non-convex in policy primal variable, which prevents direct ap- plication of these last-iterate results. A slightly twisted exception is that our constrained saddle-pon point problem can be reformulated to be convex in occupancy measure instead of policy, which leads the second and third methods in Table 1. To solve our Lagrangian-basee constrained saddle-point prob- lem in policy space, our first palicy-based method: RPG-PD relaxes the non-convexity by adding regularization into the objective function and we provide sublinear last-iterate policy convergence guarantee using the distance analysis for policy primal-dual iterates. To improve the convergence rate, we further develop another policy-based method: OPG-PD that extends the optimistic gradient method [37] for a class of non-convex constrained saddle-poin problems. This extension departs from previous extensions for zero-sum Markov games [43, 44), because lacking of uniformly opti- mal policies prevents learning an optimal policy from per-state bilinear games. Instead, we provide a new distance analysis of policy primal-dual iterates of an optimistic gradient method for solving new class of constrained non-convex saddle-point problems, with linear last-iterate policy conver- gence.
Non-asymptotic last-iterate (or non-ergodic) convergence in constrained optimization. Re- duction of constrained optimization to saddle-point problems is a classical idea to solve con- strained optimization problems by developing primal-dual algorithms, e.g., primal-dual interior- point methods [105], Uzawa and Huroiz algorithms [31, 106, 107]. and Lagrange mul- tiplier methods [108, 45]. Inspired by the Lagrange multiplier methods, many recent studies on constrained optimization have significantly advanced primal-dual algorithms with last-iterate convergence, e.g., accelerated augmented Lagrangian method [109], accelerated universal primal-
22

---

dual gradient method [110]. Douglas-Rachten Rachford alternating direction method [[11], inexact aug- mented Lagrangian method [112, 113], alternating proximal augmented Lagrangian algorithm [114], augmented Lagrangian-baze based decomposition method [115], faster Lagrangian method [116], and cetpiiiiionccorectioo----eo based primal-dual method [117]. However, all these studies build aug- mented Lagrangian methods to solve the classical convex optimization problems with linear con- straints. In comparison, have studied class of non-convex constrained optimization problems that result from constrained MDPs using the standard Lagrange multiplier method. We notice that a Lagrangian-based two-player game has been used study general non-convex constrained optimization problems with average performance analysis [118]. Our two policy-based primal- dual methods with sublinear and linear last-iterate convergence appear be the first global non- asymptotic and last-iterate convergence result in non-convex constrained optimization.
B Proofs in Section
In this section, we make some helpful observations and provide proofs of the claims in Section 2.
B.1 Lack of uniformly optimal stationary policies in constrained MDPs
In unconstrained MDPs, there always exists an optimal policy that is optimal simultaneously for all states (e.g., see [119] and [120, Chapter 6)). In contrast, this is not true anymore for constrained MDPs. To this, adopt counter-example from [46] and investigate it in the constrained MDP setting.
(L, 0,
(R/L, 1,1)
R
(R. 1)
VTT(p) Figure 3: An example of constrained MDP that has the objective function V (p) and the con- straint set { 11 (p) 2 0}. The pair (a, g) associated with directed arrow represents (reward, utility) received when action at certain state is taken.
We introduce a constrained MDP with two states: Left (T.) and Right (R), in Figure 3. In each state, there actions (T., R). The MDP transition dynamics is deterministic. In state T,, if the agent chooses action L., then the next state is and the reward/utility (0, 0) is received; otherwise, action Rt leads to next state R and reward/utility (1, -1). In state R, matter which action the agent takes, the next state is R and the reward/utility (1, 1) is received.
Since the state R is trivial, stationary policy can be represented by the probability of taking action L state L denoted by p. With a slight abuse of notation, we use notion to represent the probability of starting off from state L. Thus, Bellman equations, i.c., V(s) = E. x (a ()(ss, a) + Σ. P(s' s, (s))) for all
compute the value functions follows via the
V.(I)
x (0 (V, x1 V,(R) 0)) + (1 p) (L. 0+ (R x 1))
take action L
take action R
V,(R)
1-7
and
Vy(L)
p (0 (V,(()) +V x (0)+))+( (1 x x 0 V,(R)) 1))
take action
take action R
VR(R))
I
or, equivalently,
1- 1
1
Vi(L)
V.(R)
1 7p
1-9"
1 1-7
23

---

1
27 - 1 y (g(R) 1
and VG(D)
x
1 yp
1-7
It is easy to check basic case: 7 0 [46]. We can compute the value functions as follows,
(p) = (1- - p)p + (1 - p)
(p)
+ (1 - p).
Feasibility of the policy p requires that (p( 2 0, i.c.,
2p for any E
1 2
2
(10)
P
Hence, the maximum (p) within the feasible region can be reached at the optimal policy,
p 2p 11
P
Therefore, the optimal policy p' depends the initial state distribution p. Moreover, except that or 2. the optimal policy p* is a stochastic policy and is unique.
(ii) A slightly more general case is given by y 4. Thus, we can compute the value functions as follows,
1 p
VP(D) =
xp +
x (1
1 p/4
2
1 p
4
(g(
3 - p/4 p +
(1 p).
3
Feasibility of the policy p requires that (p) 2 0, ie.,
2 2 x 3p-2 2
for any P E
3
3p -
In particular, if we take p 7 then p p2 2.2 In this case, the maximization of V/P(p) yields 9.
optimal policy p* 1.20 which is uniform policy and is unique.
B.2 Scalarization fallacy in constrained MDPs
In constrained RL, scalarization is often used to reduce constrained MDP problem to a standard unconstrained one, which might permit many unconstrained RL algorithms [8, 9]. Unfortunately, as pointed out in the literature (e.g.. [46, Part 4] and [30]), such a reduction does not necessarily provide solution to the original constrained MDP problem. It is easy to see this from the previous examples in Figure 3. In the basic case: = 0, if we take
3.J then from (10) the optimal policy is given by p² = g. which is a stochastic policy; we see a uniform optimal policy when 1. By shaping a composite function r + Ag with some fixed À [0, oo]. the scalarization method aims to solve the following unconstrained MDP problem.
maximize T I1
(P)
(11)
However, by the optimality of dynamic programming [120. Chapter 6], an optimal policy is given in deterministic form which has been widely used in theory and practice. Therefore, solving the above scalarized version of constrained MDP problem does not necessarily provide an optimal solution for the original constrained MDP problem. We also notice that this phenomenon is reported recent empirical studies [9, 30] and more formal statement [47, Lemma 1]. Hence, it can be infeasible for dual descent methods [12, 30] to find an optimal constrained policy, because solving Problem (11) often yields deterministic policy, which can be sub-optimal for a constrained MDP with unique stochastic optimal policy, e.g., constrained MDP examples in Appendix B.
24

---

B.3 Properties of saddle points
First, we state the invariance property of saddle points [121] for our constrained saddle-point prob- lem (3). By the invariance property of saddle points, we can restrict the problem domain without changing the saddle-point property when the original saddle points
contained in the restricted domain. Let the set of max-min points be 11* := argmax, E min [0, Vr (p) and the set of min-max points be A == argmin e [0.co] maxş I1 Vrttg (p).
Lemma 8 (Invariance of saddle points). Let (i²", (T) II x A be saddle point of V2++g (p) over x [0, tol. For any subset A' C [0, too), if (TT X²) II M, then (x* (x)) is saddle poins of Vi+2g (p) over II M.
Proof. From the saddle-point property of x²), we have
argmax V (p) and X argmin ViT
=EI
Ae [,,+
It is straightforward to see that
V (P)) I Vi for any I1.
(12)
Since A' C [o0] and X E A' g minx A V Hence,
V (ox & V (p) for any E A'
(13)
Finally, combining (12) and (13) defines (T* X²) as a saddle point of of V r+ (p) over 11 x A'.
We next show the interchangeability of saddle points in two-player zero-sum games [122] for our non-convex game.
Lemma 9 (Interchangeabilityy of saddle points). Let (a* ,*), (#* X+) E II x A be two sad- dle points of V V (p) over II x [O, +ool. Then, both (T*,**) and (#* X²) are saddle points of Vi+tg (p) over +ocl.
Proof. By the definition of saddle points (x* x*) and (T*,*))
g(+ I Vx* (0) s V (P) for all v E and X e [0, oo]
T (p) S V# (p2)g(0) S V (p) for all æ II and e [0, oo].
V
Then,
v (p) $ V (p) S Vi
(Px S
VT v= (p) s ya (=))(())
Therefore,
r4i0g (p) S Vaa ( (p) S Va. (p) I VHL ( (0) S Va V (p) S v S Va' (p)
for all æ E II and À E [0, oo), which shows that (T* (x) is a saddle point of V V.tag(p) over Il x [0, +oo].
Similarly, we can prove it for ,²,,").
B.4 Constrained MDPs in acupancy-measurre space
In the analytic approach [123, 5], the value functions in Problem (1) are bilinear in the occupancy measure V/T (p) (o, q) for o = r or u, where q=: S x A + RR is an (un-normalized) occupancy measure over the state-action space,
(s. =
Σ
y Priss = s, 0f = a //,
(14)
1=0
25

---

which adds up discounted probabilities visiting (s, a) in the execution и. Furthermore, we let the operator P RIISIAA + RRss| be (P g)(s) = Ex P(s|s', "a',d))g d')g(s', (')(ss and the operator E IISI | be (E' q)(s) == E. ((s,a) simply (s)). With slight abuse of notation, denote p [p(s)),-.. p()))) A valid occupancy measure q"' [RSS|AA satisfies the the Bellman flow equations,
= {1 E R E
and q 20
(15)
known that the Bellman flow constraint necessary and sufficient for any y E [RSS|AA to valid occupancy measure (e.g.. [124, Lemma IJ).
Let the concatenation of r(s, a). u(s, a) for all (s, a) be r, u E |I respectively. In the occu- pancy measure space, the goal of constrained MDP is to find solution q of a linear program,
maximize RE
(r. .) subject to (u.g) 2 b.
(16)
Denoting g: S + (g.9) 2 0. By the method of Lagrange multipliers, we dualize two constraints in (16) and introduce a standard Lagrangian,
[-1,1] as == u- (1 - 7)6, we simplify the constraint (u, q) 2 b as
(r+ )g, + ( 9)
where π E II is the primal variable, X E [0, oo) is the dual variable for the constraint (g.9) 2 0, and μ is the dual variable for the equality constraint feasible linear program. the boundedness of X in Lemma holds for L(q. X, μd) Thus, any saddle point (q", , ,²") also a max-min and min-max point, i.., 9" is the occupancy measure associated with the optimal policy x², and "*,,"" E argmin 2 0, m o L(g. X, n). Boundedness of g* straightforward from (14),
Since the strong duality holds for any
1 8" E Q = q E TVERISII RRIIIIAI/0 = ((8,a) 2 1 M3,a)
which allows us further restrict q Q Q We next show boundedness of (Ax, μ²)) in Lemma 10. Lemma 10 (Boundedness). Let Assumption hold. Then, X E A and nº E M, where A is stated below (3) and M := {u [m(s]] S Pmax: Vs E S} where Umax := 1-741/5 (1-7)²
Proof. From the saddle-poie point property of (q", ,²"),, we have
q' E argmax "1,,"",1"
QEQ
(2*, E argmin L(g", X, 220,
equivalently, for any E Q 0,L(g X x²) (g 9¹) < 0. and for any μ and A 2 0, O,L(o" X²
,'',", - -x) 2 0. Hence, for any g E Q
(xP E) + X' 9-) < 0.
Arbitrary g E Q demands the inequality r + E) + X'g 0. By the definition of occupancy measure, we know that for any E S there exists an action a E A such that q² (s, a) > O. Thus, the equality + (nP- E) Xtg must hold at such state-action pairs in which we represent the associated reward and transition by (F, P). Hence,
|| + >glla = ||7P- -E)
2 (1- 111111100
Thus, (1 - (1-7))lu*") || < A*. However, by Assumption 1, L(q. x*, S ",,, Hence, (r,4" Φ (g.4 - 2 0
which, together with the feasibility of q and the optimality of q², imply that S A S (r, ① Hence, 0 5 X < [I-- which further yields bound on || 1l
26

---

We now obtain a constrained saddle-point problem in terms of the q-based Lagrangian,
maximize minimize L(q, p.) C E M
minimize maximize L(g. 2)
(17)
A nEQ
where we take bounded polytopes Q and A x M such that they contain q" and (X* ,"), respectively.
For notational brevity, we introduce (g. A, n)), Z Q x A M, and Z Q" A M* which contains all saddle points x² := (q" ; X*, 1² Let the gradient of [(g, X, μ1) be
- vgL(g.A,1)
21), ==
V LQ.
Due to the bilinearity of L(g. over compact domain, L(g. X, has gradient Lipschitz constant Ly. Let LetPx be the projection operator onto X, i.e., Px(x)= argmin x [|x'= zl|- Since the q-based Lagrangian Lgg, X, 14) is bilinear and the domains are polytopes, Problem (17) satisfies the metric subregularity condition [38, Theorem 5].
Lemma 11 (Metric subregularity condition). Let Assumption I hold. Then, the gradient function F(z) satisfies that for any E 7/2² with z" = (z),
T F(2) (z - 22)
sup
2 C
# E
2 - 2'1l
where C' > is a problem-dependen constant.
Hence, application of the optimistic gradient method [38] Problem (17) yields Opti- mistic Primal-Dual (OPD) algorithm that begins with two initial tuples of primal/dual variables (qu, Åo h0) = (q,, A1) E Z, and performs two gradient steps for each primal/dual variable at time 2
2t Pz ( nF((z11))
(18)
241
(2 ()(22)
where v) is the stepsize. Let the squared distance of point Z to the set be dist z*):= ==
||2 Pz. (=)]1 It is straightforward to employ [38, Theorem 8] to claim last-iterate convergence guarantee of OPD (18) below.
Theorem 12 (Linear convergence of OPD). Let Assumption 1 hold. If the stepsize nj in OPD (18) satisfies 17 < 8Ly then the iterates (2h20 converge to the set of saddle points Z linearly,
dist dist
(21, 2n) S Ci
C2 T+C2)
where Ci = 64 64 dis ("1, and C2 = min(
C6
-2) for problem-dependeet constant C > 0. 81
Theorem 12 shows that the primal-dual iterates of OPD converge to the saddle point set Z* in linear rate. Compared with contemporaneous work [40], OPD is free of projection to occupancy measure set, and enjoys aon-asymptotic and last-iterate linear convergence. If the underlying policy is recovered via (a 8) E., (((),a) for all (s, a), these policy iterates n, associated with the optimal constrained policy n²"
qi(s,))
occupancy measure iterates de also converge
Corollary 13 (Nearly-optimal constrained policy). Let Assumption hold. Assume Puin min, p(s) > and re-define Q := {q E IR [|| | < g(s, a) < 1/(1-
2 Pmiin(1
7), V(saa) a) E S x A). Ie the stepsize n, similar way as in Theorem 12, then the recovered policy iterates {mi)2 of OPD (18) satisfy
for Jorany any i = St loog" 2
VF (p) (p) e and -V
where Te(a|s)
(:(5,)) E. v:ls,aj for all (s, a), and 12-)) only has some problem-dependenn constant.
27

---

Proof. The key to our proof is to connect the occupancy measure iterates q with associated policy iterates TT. It is straightforward that Theorem 12 continues to hold, with further restricted the domain Q. we set the stepsize rj in a similar way as Theorem 12, then for any t S2(log 2)
max [PQq- (4)) ze 2 (P) 1,ll,, I| (14) - mell ] = -O(e)-
Let ni be policy that is associated with the occupancy measure q -Pq (q:) and To be a policy ((s,a)
that is associated with the occupancy measure iterate qr, i.e, T((al ()) Ev E.l,a)) for all (s, We denote (z) (Px- (Ne), PM (mt)). Thus,
Σ c (s) (TTe m (-1))l
(s. (s.))
Σ di (s)
(r(s)
(s)
[el(,,)) - (s, (()))
+ Σ dhf (s) 11q.(s, (()((s)))( - grt (s)l
- Σ doi (s)
||a((s.)) - gri (s,-)1 (s)
(((s)q (s)
(u(()) (c(s)
(s))
(s)
VIAl
- Σ (10.(8))- -t. (s. +((((s) - q" (8)1
Pmin
VIA
VIsI
Σ llae(s,)) - (s, vIS|AA|
Σ
lec a) 9rd (s, (s, a)
Pmin
8,a
2 |S
qt 9mb
Pmin
2
Po-
Pmin
where the first inequality is due to triangle inequality, we use the fact: (1 - (1 = d3. (s), dhi (s) S 1, and [19.(s.)) S VIAl q (s), (s) Pmins and Pmii O, we apply Cauchy-Schwarz inequality in the fourth inequality, and finally we combine two square root terms by relaxing the first one in the last inequality.
1-7 in the second inequality, the third inequality is due to that
First, we have
d (s) (=)
- x 8)) O. (8, (8,a)
=
8,
dp
(+1ss m (-11s)]]
(1
7)2
|
w
(s)
1 (-13))
7)
where the equality is due to performance difference lemma in Lemma 28, we use Cauchy-Sehwaa inequality in the first inequality, and the second inequality is due to || I vdl ||rlll for IR., which shows V (p) - VT* s O(Ve). By the optimality of oद. V. (p) = V." (p). Therefore,
V.F" (p) V.ae (p) I O(vc).
Second, we have
(p)
V
(p)
V (p) (ii)
Similar to bounding V. (p) V.*. we can show that (ii) S ((v)). By the optimality of m/, we have Vi (p) 2 O. Therefore, - -V (p) - O(V)).
Finally, we replace the accuracy ve by and combine all big O notation conclude the proof. D
28

---

Corollary 13 states that after an almost constant number of iterations policy induced by the last oc- cupancy measure iterate of OPD is e-optimal constrained policy for Problem (I). We notice that recent last-iterate convergence result for convex-concave saddle-point problems [39] is also appli- cable Problem (17), which provides the optimal rate without wroblem-dependent constants. It is worth mentioning that direct application
such last-iterate convergence results in convex minimax optimization to constrained MDPs with general utilities [125, 126] and convex MDPs [124, 47] in accupancy-meastee space is also straightforward. We omit these exercises in this paper, and focus on the design and analysis of algorithms in policy space.
C Proofs in Section 3
In this section, we provide proofs of the claims in Section 3.
C.1 Existence and uniqueness of regularized saddle points
Lemma 14 (Existence and uniqueness). There exists a unique primal-dual pair (7, X) E 11 such that L, (ū, A) L, ( A) L, ( X) for any π E II and X A.
Proof. We first re-write the regularized Lagrangian Ly (T, A) in terms of occupancy measure E Q
+g + (((T)) + 1 x²²)
Lr(x,))
g(s,a)
H(T) = - Σ ( log
= H(q))
Ee g(s, a')
6.0
We next use notation (g, A) to represent L, (T, A). We first check that H((4) is a concave function,
Hlan + (11aa)p
(s, a) + (1 a (2()))((ss))))
- Σ (aq) (8, a) (1)a)g2(s;.)) log Ea (1,8, a') + a:) Ev
8,0
(s,a))
(1 (2
2 Σ
aq aqn (s. log a a.r (1(,
Ia- a)g2 log (1 - (x) Ev 42 (8,
= aH((n) + (1 H){())
for any 41 E Q and E [0, 1, where the inequality is because of the log sum inequality
E. a.) In E, 24
Σ. ba < Σ og
In e: for non neg-tegttive a; and b,, and the equality holds if and only if by
(s, E. (1(3,
(2(8, EN (2 for all s.a.
Therefore, Ly (q. A) is concave in q E Q and strongly convex in E A. We notice that @ is a polytope and A is a bounded interval. By Sion's minimax theorem [127], L, (g. A) has saddle point (7, À) E Q x From the one-to-one correspondence between policy and occupancy measure, induces policy स and (T, X) serves as a saddle point of L,( A), which proves the existence of saddle points.
To show the uniqueness of (Æ, X) (or (ÿ, X)). it is sufficient to show that L, (g. A) is strictly concave y and strictly convex in The second argument is straightforward from strong convexity of
L, (g, X) in X. We next show the first argument that L-(4, X) is strictly concave in g for any X A. Assume that there are two (different) policies म and πa and the associated two occupancy measures
gı and 92. From the concavity of H (q). there is another occupancy measure agı + (1 a)
29

---

that satisfies
I-(0q +(1 a0)2, X)
fr+ Ag, + (1 - a)q2) + H(aqq + (1 a) + 1
+ xx²)
2 a (r+ \g, 91) + [+((9)) + T 2 + (1 -a) ( >g. + +H(12) + 7 =
aL, A) + -a) (:2,
where the inequality 2 has to be strict since क and m2 differentiate by least one state-action pair (8, (8,a),
21 (1 ④)
Q2(3, a)
m 8) =
= T2(a 8) En' (2(5,
(1 a')
Hence, new policy associated with aq + (1 a)g2 can achieve strietly higher value of the convex combination of two objective functions, unless q1 d2 or equals either 1. Therefore, L Lg, A) is strictly concave in E Q for any À E A.
Let a saddle point of L,(T,, A) be b argminxes A max, E II (TT A). Existence of saddle points in Lemma 14 ensures that,
argmax, e minx A (, A) and X
Lr X2) & (T X2) S (r A) for (v, A in which the first inequality implies that for any II,
V (p) (p) + ( [17)))
( 2 V (0) +r (H(T) + 1 (x;)))
2 V +T (A7)2
and the second inequality implies that for any A E A,
Vuz (p) + (M(TT) + {x²)
Vaa
(+x:g(p) (p) + (H(T)) + (x)2)
r4 (p) + +H((x²))
Combination of two implied inequalities above leads to (5), i... (m X;) is saddle point of the original Lagrangian Vi+tg (p), up to two r-terms.
C.2 Proof of Theorem
Proof. We begin with the standard decomposition of the primal-dual gap,
LT( de) Lo (Te, A²) = LT(T,, Ar) - L, (TE, Ne) + Lo (TT, - Lo L. 2;)
(19)
(ii)
and we next deal with (i) and (ii), separately. We notice that
H(T))
E
y log ( (s)(
- Σ ()) log s)-
We note that Q Ao (s, a) is sum of a soft Q value function associated with composite func- tion r + Azg log ne, and - log πe. Because of the boundedness of the soft Q value function and the ce-restriction the policy domain Á(A), 10 (s, a)l < - ( + log [Al)
30

---

T log co = Cr,E.00 For the term (i),
[A]
[. de) - T. (Te,
Vitt 14 (p) - Vi (P)
=
Σ (3)(((())))) 8) + 1-7 (5)()<((aa)))) (((ls))
8.
rou (p)
V rtiigtTe (p) -vV= (p) V (p)
Σ
(4) log (a 8) + Σ (o)g
do (a]]s)) Q Arg (5,
8,0
de (1)) 1-7 7
7
dhe (5)TT((a log (s)
(1) 8) +
dh (s)xx((a (()
1
8,0
8,a
(s)
(s) (T - 5 8)) Q Q a (s,a) 1-7 Σ d (s)KL((s)
T KLc(s) (LL(s))KL(41($)) + ((Cr.1100))
Σ (s)
1-7 >x Σ (s)(())()))))
17(1 -11-)) ?)
(1 (1-177) (L, -KLot1))))) (L)
Σ d (s)
((Cr,1,00))
11(1 77)
(1 qr KLx kp)+ n(Crrg.oo)?.
71)
where the first two equalities are because of the entropy regularization H(T)), we apply the per- formance difference lemma in Lemma 28 and (s. = log [ to the third equality, the first inequality is due to application of Lemma 27 with x" (+ (s) Tel- g = 2f (s, 4)/(a)(1111 - 7), and $ 1/Cr,g,e0.
Similarly, for the term (ii).
(, Ae) - (Te,
= Vi (p) VitA;g(p) + TAr) 2 TA2)²
1
1
= (Ae 1²)V,((( (p) + 2 (2,)²²
2 T1;))
= (Ar 1;) Viae (p) + +
T(e - -X:}²
(A; A1)² - -(1; - -\411)2
1
1
2 ((
2 -
27
(1 -1- ()7 2x) (x;- ~
+
2 (C
2n
where the inequality is due to the standard descent lemma [128] and V (T)+ S (1+ =
Cr.g.
Using the definition 4, :- (p) + {A; 22)2, we combine the two inequalities above show that,
< (1 - D ([T Ar) - LT(TT,,;)) + 172 max (,,
< - 4/ + 17² max (Crr. (Ch,))
31

---

where the second inequality is due to Lemma 14. If we expand the incquality above recursively, then,
4 1-
2 (1 - + nf² max ((Cr.g.o) (C=
s (1 -r)) (v² n (1 nT)) max ((Cr, (Ctrs)
< (1 11-1p -1p))( (1p (1+ + (1 177) + (1 1772² +7))++...) +...)) max ((Cr,soo)?
(Ct (C)
S (1 / ? max ((Cr, (C,
s m $ + = max ((C+,,,00 (C,,,)
"
which completes the proof.
C.3 Proof of Corollary
Proof. According to Theorem 2, if we take r r= = =((2), and 6 = e, then P = (c) for any = 2 log 1). where (2()) hides some prohlem-dependent constant. We next consider primal-dual iterate (Tr, Aς) for some = Q log )). is straightforward to check that
KLt(P) = O and / [ X1) = O(e).
First, we have
(p)( (p) 100-V, (p) V (0) Vi (p)
1 (p) V. (p)
(20)
i1)
(1I)
For the term (ii), because (p) O(e), we have
(ii) = 1-
Σ
t (s) (T) ((((ss))))))))) O (s)
3,a
<
(s) ||T ae (s1s)]l
(1 7)²
1
5
de (s)
(1 7)2
2 Σ ())
7)2
7)2 (p)
where we use Cauchy-Schwarz inequality in the first and third inequalities, and the second inequal- ity is due Pinsker's inequality, which shows V (p) V.T S O(Ve). For the term (i), if take π = x² in (5), then,
V. (p) -H((T)); < (= + x V (p) -V, Vy vp))
Meanwhile, if we take À = 0 in (5), then X; \; (p) < 0. We notice that the feasibility of n yields
V*" (p) > 0. Hence,
V.- (p) (p) < TH(m))
We now substitute the upper bounds of (i) and (ii) above into (20) to obtain V." (p) - V.* S
(( VE), where we take (e)).
32

---

Second, we have
8 (p) = V0 (p)
+ V9 (p) V (p).
(21)
(iv)
Similar to bounding V (p) V (p), we can show that (iv) S O(ve). Let Amax the term (iii), if we take X = Amnax in (5), then,
For
[1~>)5'
(Amax 13)V3-(0) - 2 (mmx))
By the definition X == argmiin (VV= (0) + _사²]. there are three values for X to take:
(c) or O, or Amax as follows
(1) When [o) Amaxi X; = V (p) which shows that Amax - X; > 0;
(2) When (p 50. 0. X O which shows that Amax A Amax >> 0;
(3) When (p)
Amaax X Amax- In this case, using (5) with xT leads to
Amax (V (0) v (0)) & (p) - V (p) +
(22)
Meanwhile, for any saddle point (TT", X*) II x A V. (p) - (p) s X (p)
V (p)), which in conjunction with (22) and V (p) 2 yields,
-(Amax VoVVTT (p) S -H(
It is easy to see that we can always take X < Amax- In fact, except for X = 0, we know that A >'V (p) S leads to V/ (p) = 0. By the definition X E argmin A Vi4tg (p),
any X < Amax is a min-max point. Therefore,
(iii) <
X²) H(TT)).
(Amax
By combining three cases above, we conclude that (iii) S
We now substitute the upper bounds of (iii) and (iv) above into (21) to obtain (p) O(VE).
Finally, we replace the accuracy Ve by e and combine all big O notation to conclude the proof. G
C.4 Zero constraint violation of RPG-PD (6)
Corollary 15 (Zero constraint violation). Let Assumption 1 hold. For small there exists d > 0
such that if instead use the conservative constraint (p) 2 0 g' = g (1 - 7)6, and take
1 = ) T = +(e2), and En = e, then the policy iterates of RPG-PD (6) satisfy
V. (p) (p) < and VV (p) S 0 for any t 52 ( 6 log" 1 !)
where 2(-)) only has some problem-dependent constant.
Proof. We apply the conservatism the translated constraint (g) 2 0 in Problem (1), Specifi-
cally, for any 8 min(g, 1), we let g' = 9 (1 77) and define a conservative constraint,
V
(p) 2 0.
is straightforward to see that Assumption ensures that VT (p) 2 0 is strictly feasible for new "g"
slack variable g == E 8. We now can apply RPG-PD (6) to a new regularized Lagrangian,
(T, = Vi VP (p) + 7 (((TT) + 2 x²
33

---

and Corollary holds if we replace in RPG-PD by g'. Thus,
V ( - 1 (p) S e and V (p) S e for any t St (
= é
where !?(-) hides some problem-dependeen dependent constant, and Tī is an optimal policy to the 8-perturbed constrained policy optimization problem,
maximize V, (D) TE
subject to (p) 8 0.
(23)
We notice that the above S2(.) has g'-dependence and we denote it by E(5'), where E: R, + R. a positive function. Thus, we select such that 2 <E(5"), which is always possible for small enough e, for instance, 8 = É and ç¹ = Hence, if we take 5 = 2 and such small e, then,
V (r)( 0 s cE(E") for any 2 ( log )
-V (0)
which shows that ( 2 0 for some large t.
The rest is to show that ( (p) - (p) S O(c). We notice that n² is an optimal policy to Problem (23) when 5 O. Let 9" and 93 be associated occupancy measures of policies '² and x In the occupancy measure space, Problem (23) becomes a linear program and it has a solution 9z. Thus, view o as a 5-perturbed solution of convex optimization problem in which all functions are continuously differentiable and the domain is convex and compact. It is known from [129, Theorem 3.1] that the optimal solution g is continuous in 8, which implies that for any 0, there
exists 8' > 0 such that (r. (r, og) S O(e) for any 5 < 8. Thus, IV,"" (p) V. (p) < O()) for small enough e. Therefore,
V (7) s V (p) (p)
(p) + VV, (p) V (p) 1 O(e)
for some large t. Collecting all conditions on 5 leads to our final choice of 5 = min mi 1') Finally, we combine all big notation to complete the proof.
C.5 Reduction of RPG-PD (6) as a NPG variant (7)
We introduce some useful notation in the regularized MDP [52]. Let V.7 == V (p) + +H()). We introduce the soft-Q value function Q S x A + IR and V S + IR via Bellman equations,
(s) r(s,a) + Ag(s, a) yB P( s.a) [V7(s'))
(s)
E, ~ a(1a)) - log 8) as)
We also define A7 = (7, a) - - (a (1))|||))))))){ (s). Hence
O (0 a) (T( - loog=(()
A (7
(5 Va (7+
where vi(s, == - log 8) for all (s. ESXA.
Setting = 0, it is easy to show that RPG-PD (6) is case of (7) in the tabular case by introducing
the softmax policy that is widely used in policy optimization. softmax policy we: S - A(A) parametrized by a parameter 0 IR || via a softmax function,
exp(Os.a) for all (s,0) Enp exp(0..a)
Te ()
With slight abuse of notation, also use notation To vector in R| Lemma 16. Set Eo O. Under the softmax policy parametrization. RPG-PD (6) is equivalent to (7).
34

---

Proof. Dual update (7b) is straightforward. We next show the equivalence for the primal update by applying the softmax function to both sides of Primal update (7a).
We first notice that Fo(O:) VoL, (TO. x,) Fp(O,) VoV (p). Thus,
exp(0++1saa) exp(Ot,0,)) exp (n/(1 - (F)((())) (oT, )e))s,a)
exp(Or.0,a) exp (nA, (s, + s]((s))
where c(s) is an action-independent constant, and the second equality is the property of natural policy gradient Lemga, we have
Lemma 29). Hence, after normalization over actions and some re-arrangement,
exp (nA7 (s, a) + no(ss)
To. (a|
To, (als)
Ea no, (a' 8) exp (1 "h (8, a') + n]((s)
exp (n== (s, a) nT log no. (a s))
To. (a Eo To, (a 3) exp (nQ= "h (s, a²) BTT log To, (a' s))
exp n (8,
(al()))) Eo (a, exp (n0 (8, a'))
which is explicit form of the policy update in (6). Since the above derivation holds in both directions, the proof is complete.
C.6 Proof of Theorem
Proof. We utilize the decomposition of the primal-dual gap as (19) and analyze the term (i) and the term (ii), separately.
35

---

For the term (i), we have
[,,(T,,11) de) - Top (T0, 21)
V (p)
V r4iig
Vi (p)
7
Σ
d (1)7(al())))) 8) + 7
Σ
dr
(S)TT, (a 8) log ne. (a s)
1-7 8,0
8,0
V V+Aigtto - -V (p) r Vo (p)
7
(s) 8) + Σ
dp (s) (a no, (als)
9,a
(s) (T)(a|s)- s)) Q Q + (s,
8,0
T
(00 (als)
7
Σ di (s) (a log no, (a 5)
1-7
(1) 8) +
Σ
dip (s) (a 8) log To, (als) 8)
1 -
8,0
8;a
* (m - s)) 2
T
S (L{
P
8,0
1
Σ (s) (T] To. (a ( (8,
2s.a Wt
Σ d (s)
KL,(s) - ( + n(Cr)) -
711 ((1-))
- - - do (s) (s)
T
Σ
Σ
dh (s) (a:(a - (a. ( (s, To.a wis
8,0
(1 (1-177)L4((5 - kl(+1(+) + n(Cw))
Σ (5)
(1)
1 Σ
(8, - 03.0 (ao(aa))) (8,
Wi
8.0
(1 nT KL(()) KL(+1(p)
+ n((w))
7/1 7)
1
Σ dhf (+) (a)
(Q ( (8, & we
where the first two equalities are because of the entropy regularization H(T), we apply performance difference lemma in Lemma 28 and (s, a) log To, (a s) to the third equality, the inequality is due to an application of Lemma 27 with x- = x;( 8), (-,(-1)), 9 - W., and
7 < 1/Cw, where I wt - 7)1 < 2W/(1- - 7) = Cw. Moreover, the cross term has the following decomposition,
Σ ds (s) (T s) To. To (a) (Oftingtuu)s -05,a -55,a 26
8.0
Σ (a)
(o (8, - -00 )bam))
+ Σ
(a) (we wx))
8,0
5.a
(a)
(b)
Σ
def (s)= TT n. (w) - wee + Σ
de (s) (05. wi - Quiieatt (s,a)
8.0
8,a
(d)
36

---

We now deal with the four terms (a), (b), (c), and (d), separately. For the term (a),
[a)] I Σ t (s)T ()
Q P (s, 2z.a wi!
do (s)mi(a $)}?
Σ (s)Uni(()))) (o (OrtsOOTO (8,0) o3
(s)(nnn
(d)+(s) s))? (s)(n
Eq(wt, Oc, 0t) v*)
df (s) (8)
Eo(w,,
(a)
VI 0r, v*).
where we recall the definition of Eq(w?, Ve) Similarly, we can bound the term (d) by ((d) s / VIAlEolu Oc, u*). For the term (b),
[bb] Σ de (S)
(wr wi))
(s) (a 8))?
Edy dx (s)Unifa(a) (ØJ,a (wr wx))²
(s)Unif (a) s.a
(s) (a ss) dz (s))ni(((((a))
||e0 E.
(s)To, (al
|wwe -
(n)
|A] |lwe - will 1
IA
|Als 1|ase w 1 "iree."'
where we recall the definition of Ky obtain the last line. Similarly, we can bound the term (c)
by (()) s /IA I|l, yields,
wi 1 Moreover, the optimality of w argmin eRa Eq Oe de,x)
(w- wi) Www 0c, dev) 2 0, for any |||||| $ W which further implies that for any || I W.
Eq(w, (w, G2, de.)) - Eq(wi, de.de.))
(OT
P0 o wi + oT w - Q rol - (s) - Eq(wi, Pc, dr,
((aa) ~ di.
((aa) ~ di.
(oT w 03 w,) 21
+ 2(w w ((s.))
~ew (eaa (05,aut witiigtte,ss..
B(s,a) ~ di.
(05 T 23 )21
2
2(w wt) V En Oc,
[(,,a) ~ de.
(05 - oJaw w 3
||l wi|l 15
Therefore,
[bb] 5 / IAlNs l|l, will
/ Alm (Eo OG, dr,) - Eq(ut, O,, dr.))
37

---

With a similar reasoning, we can bound the term (c) by
(c)
VIAlis (Eq(wr, 0e, Eq(wi, dc, dr,,)).
By applying the upper bounds above to the cross term, and then taking expectation over the random- ness in Wi, we have
B Ly (T; 21) L- (To, Ae)]
11T [E]KL, E[KL(+1(P) (p)]
+ nn(C))² 2E v [A; B,,
"7
+ 2E V |Alrs (EQ(ur. b2 deyr) Eq(ut, (e, de.))
(1 777 [B[KL+ - E[KL++1(0)) (p)] + n(Cw)? 2 [Eq 0,, v*)
77
+ +22 | Ali B. (wq 02, de,u) fo(ut, de,)]
(1 ue (B)LL(( - E[KL(+1(p] n(w)) 2//Alciius 2 ( Cim
n
Similarly, for the term (ii).
(T No) - L, (T 2;)
rrte (p) V (p) + [A,)] 2 TA,))
2
1
(Ae 1² (p) + T(2))²
T(2))2
2
2
1
(Ae );) Vg (0) + +
T(x: -27²
2
(A; Aa)² - (A; -x+1)²
1
1
(n((tss)
2 TT x;)²
21
2
(1 - (1; >x)² - -A;
- xe+1)²
1
+ ((
2n
2
where the inequality is due to the standard descent lemma [128] and (p) S 1- (1+ Cr.s. By taking expectation over the randomness in W's
(1-17)LE [A= Ae) -E [( - de+1)2] + (1Chh))
E (TT, Ac) L, L, [;)]
21
Using the definition [ = E [LL( + - ),)3J, we combine the two inequalities above to show that,
E P
<
(1 - m77 [ - -7/E (TT dz) Lr (T0, x;)1 + 7² max (C"
+ 21/ |Alebiis + 2// 1////////i
(1 - 17)) [b,] + 172 max
((CW)?, + 2 TAloisss + 2n / Estt
38

---

where the second incquality is due to Lemma 14. If we expand the incquality above recursively, then,
IE
[++1]
2 (1 m/ IE ++ ] + nf max ((Cw) (C,,,) (C),,) + 2 AAlebin + 20/ [AprvEssta
(1 - 17)) + | + (17² + 11 - T7r)) max (C,))
+ (1 + (1- (VIAlebic + 22 |A Niv Estat
(1- (1-n))'B[4) + (1²² (1 + (1 - 17) + (1 -n + +...) max ((Cw) (C*ss)
2n (1 + - (1) (1 1/7 +...) (VlAlctius vI VIAlnive Emm
(1- (1- { - max ((Cw)² (C²=)))) 2
+ (ViAletins VAlliss
s " E 1
" max ((Cw) (C*,))) (C',s))),,,)))
2
(VIAlcouas + VIAlispfam
which completes the proof.
C.7 Proof of Corollary 5
Proof. The proof is similar to the proof of Corollary 3, except that we take the expectation over the randomness of computing wy via sample-based algorithm.
According to Theorem and Cant O(c²). Cstar = O(c*), if we take O(c) and ry O(e?), then
[[ O(e) for any t Ω (3 log 2). We next consider a primal-dual iterate (TT, Ae) for some
t = Ω log 4). It is straightforward to check that
(p) O(e) and
_ [ -a0 O(e).
2
First, we have
E VT (p) - V, (p)
V. V. (p)
E
VØ (p)
V, (p)
(24)
(ii)
For the term (ii), because of KL, (p) (c), we have
i E
(s) (Ti(a (s) (a) (s,
8))
ग., (-11))ll (x) (-))
7)²
Σ
To (s) 2E (L)())
(1 7)3
Σ dhi (s)
s (1 7)2
(1 (1- V 2 (p)
where we use Cauchy- Cauchy-Schwarz inequality in the first and third inequalities, and the second inequal- ity is due to Pinsker's 's inequality and Jensen's 's inequality, which shows E V. - V," (p) -
( For the term (i), if we take π = x² in (5), then,
V. (p) +(())) < (p) + x; (vo (p) -V vv((p).
39

---

Meanwhile, we take À = 0 in (5), then \;V (p) S O. We notice that the feasibility of nt yields
V 9 (p) 2 0. Hence,
i V. (p) V (p) I +((+))
We now substitute the upper bounds of (i) and (ii) into (24) to obtain [V - - [p)] s O(Ve), where we take r = (c)).
Second, we have
[-v Vg (p)] = -Va (p)
(p) Vi (0)
(25)
(iii
(IV)
Similar to bounding E V, (p) V, (p)
show that E. ((iv) ((vc). For the term (iii),
can show that (iii) (T) O()) in similar way dealing with (iii) in (21).
We now substitute the upper bounds of (iii) and (iv) above into (25) to obtain E [VV (p) S
((Ve).
Finally, replace the accuracy Ve by and combine all big O notation conclude the proof.
C.8 Zero constraint violation of inexact RPG-PD
Corollary 17 (Zero constraint violation). Let Assumptions 1-2 hold and Estat Cuias (E²)) for small CD > 0. For small 6, there exists 8 >> 0 such that if we instead use the conservative constraint
Vi (p) 2 0 for o' = 9 - (1 - 7)6, and take the stepsize r = ( and T = ( then the policy iterates of inexact RPG-PD satisfy
S 0 for any t = Ω ( log" 1
E V. ( (p) < and E -
VV
e
where 22.)) only has some depeedm- constant.
Proof. We apply the conservatism to the translated constraint (p) 0 in Problem (1). Specifi- cally, for any 8 min(g, 1), we let g' 9 (1 --) and define a conservative constraint,
V5 = V (p) 5 2 0.
is straightforward to see that Assumption ensures that Vi" (p) 2 0 strictly feasible for new slack variable g := - - 5. We now can apply inexact RPG-PD (8) to a new regularized Lagrangian,
AT,
(p) + H((T) -
O(E0) for small and Corollary 5 holds if we replace y in inexact RPG-PD by g' and Estats Chias é > 0. Thus,
(p) - vp) s and -V3
E - Vr
for any t= Ω (1e log" log²!) !
where S2(-) has some wroblem-dependee constant, and कテ is an optimal policy to the 8-perturbed constrained policy optimization problem,
maximize V," (p) T
subject to (p) - 5 2 0.
(26)
We notice that the above 22-)) has g'-dependence and denote it by E(E'), where E: R. + R. a positive function. Thus, we select such that 2 <E(g)), which is always possible for small enough e, for instance, 8 = & and g' = f. Hence, if we take 8 = f and such small e, then
V Tol (p) = E -v Tei (p)] + s <E(E') for any t = 22 (1 log -
E
which shows that E [V,7 (p)] 2 0 for some large I.
40

---

The rest is to show that E [V (p)- [p)] & O(e). We notice that x is an optimal policy to Problem (26) when 8 = 0. Let q" and g3 be associated occupancy measures of policies " and z3. In the occupancy measure space, Problem (26) becomes a linear program and it has a d-perturbed solution of a convex optimization problem in which all functions are continuous differentiable and the domain convex and compact. It is known from [129, Theorem 3.1] that the optimal solution 93 is continuous in 6, which implies that for any e > O, there exists such that Kr; q²) (r, 187l I O(e) for any d < 8'. Thus, IV," (p) V,* (p)) = (c)) for small enough e. Therefore,
solution 9z- Thus, can view q
E V. (p) V."' [p)] s E V (p) V, v,T*(()) + 1V, V. - O())
for some large I. Collecting all conditions on 5 leads to our final choice of 5 = 1 1,8). Finally, we combine all big O notation to complete the proof.
C.9
Sample-based inexact RPG-PD algorithm
We generalize the inexact RPG-PD to be sample-based algorithm that only takes sample-bases estimates. We propose a sample-based RPG-PD with linear function approximation as follows,
Σ vaa 5) ún
1 (- (- (-1))
18442(-10) =
argmax ((-1))
(27a)
7
X (p) (0) (0)+
1 - (A (A-2x13 2n
Ae+1 = argmin ΛEΛ
+
(27b)
where W, and ViTe are the sample-based estimates of NPG directions and value functions. It is standard to assume that there exists policy simulator that generates policy rollouts for any given policies [49]. At time t, we can estimate w by solving the regression problem Eq(w, 9g de,,) [(e.a) [. w QTo (s, a))² with QT (s,a) Q, -rthggtv (s, a) via projected stochastic gradient descent (SGD) method,
W
k-1
Pllll sw (w, a G+
where 2 0 counts the number of SGD iterations, and G a sample-based estimate of the population gradient V EQW( 02, dr.)).
G = 2 2 ut Of az.a.
From the projected SGD result [130], we use weighted average K(K+I) Ek=1(k + 1)u as our Wt. We note that Th Q (s, a) is a sum of soft-Q value function associated with a com- posite function r + Agg - 7 log Te,, and - log To., Thus, we can estimate the value function QTthgtry, (8, a) using policy rollouts in Algorithm 2, which provides an unbiased estimate and has bounded variance [131].
no, ( (5, s,a = Q Q (s, a) and E [[G]] = Vn Oz, de,v)
where the expectation E' is taken over the randomness of drawing (s de Another value function VTThh (p) can be estimated using policy rollouts in Algorithm 3, E V.T (p) ViTT (p). which also unbiased and has bounded variance [23]. Hence, simply replacing all population quantities in inexact RPG-PD by their sample-based estimates leads to sample-base based inexact RPG- PD that is detailed in Algorithm 1.
We are now ready to establish the sample complexity of Algorithm 1 by exploiting the projected SGD result [130]. Corollary 18 (Sample complexity of inexact RPG-PD). Assumptions 1-2 hold. Assume E,, ((e,) ~v ( [ 2 Kol for any state-action distribution and some 0. If we take the
41

---

Algorithm Sample-based inexact RPG-PD algorithm with log-linear policy parametrization
1: Input: Learning rate 7), number of SGD iterations K, SGD learning rate
2: Initialize 0g = 0, Ao = 0,
3: for =0, 0, ...... T
do
4: Initialize wi = 0.
5: for 0, 1....,,--1 do
6: Estimate Qr (s, a) for some (s,a) ~ de using Algorithm with policy ne.-
7: Perform projected SGD step with Or ko(k+2)
w P|lwll sw (wf 2ax (0 wx Ortingtten (8, a)) )s.a)
8:
end for Set úù
K(K+1) Ek=d(k 1)
9:
Estimate Vi (p) using Algorithm 3 with policy ne.-
11: Perform inexact RPG-PD update,
T0.4 (-1s)
= argmax
Σ T 5)0 20 KL(T(: (s), To. (-)
A411 = PA (1-nT)Ar nV (p)
12: end for
Algorithm Unbiased estimate Q
1: Input: Initial state-action distribution v, policy क, dual variable X, regularization parameter T, discount factor 7,
2: Sample (sg. an) ~ v, execute the policy æ with probability y at each step h; otherwise, accept (sh, ag) the sample.
3: Start with (s), an), execute the policy x with the termination probability 1 - V7. Once ter- minated, add all composite values (((- Ag + Ty²) from step & = h + 1 onwards and
-T log (an (x)) 07+ (sh, an).
4:
Output: (8), an)) and 27 Ag+ ( an).
Algorithm 3 Unbiased estimate V
1: Input: Initial state distribution policy n, discount factor 7.
2: Sample so p, execute the policy with the termination probability 1- 7. Once terminated, add all utilities up as V75()) (p).
3:
Output: V.(())
42

---

stepsize n S 1/Cw, then the primal-dut dual iterates of sample-based inexact RPG-PD in Algorithm satisfy
" max ((Cw) (Ctg)) CW.E.T.ce 7
|
- -V|A
E 11+1] -
e-MBB 11] T
<VAAeebis
Ebias
K K+1
where Ow = 21 7), CW.a. == 8(W + 2/(((1 v5) + (2 log A + log eo eol)/((1 ()) and
Proof. The proof is based on the proof of Theorem 4. Additionally, we have to take the randomness
of sample-based estimates into account and bound the statistical emror can using the projected SGD
result [130]. We first check all conditions of the projected SGD [130] are indeed satisfied by the
SGD step in Algorithm I: (i) The domain ||æ||| S W is convex and bounded; (ii) The gradient G is an unbiased estimate of the population gradient; (iii) The minimizer of &Q (w, O2, x. is unique,
since Ed,, 2 kg/ / for some Ko > O; (iv) The squared norm of the estimated gradient G is bounded or the gradient has bounded variance. To show (iv), it is sufficient to check that
E 11
E
110.00 0..a [|0211]]
W
[]
(o (oo (8, (0)))) 2 11
E
O (s. a)os,a
E
(0 (8.)))
2
E
where we use the boundedness of || | S W and
|لla S
We notice that Ir + Aegl S (1-7)8-
By [131, Lemma 3.5], we know that
E (ortheetre
(2((1-2)6)
T log [A]
s 4
( 1- +4
+ T Flog
A
where the first two terms in the upper bound due to the variance of soft-Q value function, and the last term is due to log ma, S log [2] for Te, E Á(A). Hence, the estimated gradient G has bounded second-order moment (or variance), which verifies (iv). From the projected SGD re- sult [130], the SGD stepsize ar = k#2 then
16 W +
2
+ 72 log ||| log col
E11 811-v9}"
(1- (1-V115
E [ Oc, dr,r) - Eq(wi, 0,, dr,,) <
Ko K + +1)
4(W (WW+2/((0VV)))++ log [A| log (el)/((11))))))) Substituting the bound
which leads to Vesal <
+1](K+1) of eesti into the proof of Theorem 4 yields our desired result.
Corollary 18 states a similar result as Theorem 4. The effect of using sample-based estimates to update inexact RPG-PD appears as the number K of SGD steps each time t. Thus, we can interpret the iteration complexity in Corollary 5 in terms of the number of SGD steps by taking Gus O(e)). i.e., K ② 2(})) (.). Thus, whenever Ebias O(e)) for small > 0, if we take (n, r) in
Corollary and K =2 for Algorithm then,
V. - V (p) s e and E [-VV," (p)) s for any t- ( log !)
E
where 2(-) only has some problem-dependent constant. In other words, the total number of policy rollouts sampled trajectories tk Ω (++² is required for Algorithm output e-optimal constrained policy. Furthermore, the zero constraint violation Corollary 17 can be interpreted similarly. When c is small enough,
design conservative constraint such that the policy iterates of Algorithm 1 satisfy V."" (p) V. (p) < and V7 (p) 2 0 for some K that sat- isfy IK- = Ω ).). This appears to be the first sample-based zero constraint violation result for constrained MDPs in the function approximation setting. We leave achieving the optimal sample
complexity as future work.
43

---

D Proofs in Section 4
In this section, we provide proofs for the claims in Section 4.
D.1 Prelininary last-iterate analysis of OPG-PD (9)
To measure the proximity of the primal-dual iterates of OPG-PD (9) the optimal pair (T²,, 2²), introduce the following two distance metrics θ and S. at time t 2 1,
(s) (- (s) Pn- (fe( 8 s))[
+ 2 (A: 1 ())))
2(1 7)
_ (dr 2
1
+
(s) AT (- () ( (-ss]]
16(1 - 7)
16
dp (8)11=411(+15) mc(1))]
1
(d143 xx0²
2(1 7)
d (s) [ (1)))] 1 2 2,
2(1
and a problem-dependen constant
87 /AAmi (11 (1-7)6
2*21
1 (1+ (1-2)pp2) (1-7)3
4
== max
(28)
Lemma 19. Let the optimal state visitation distribution be unique, i.e. d =d for any II. we set the stepsize 1) 1/(4/)), then the primal-dual iterates of OPG-PD (9) satisfy
7 St for all 1 1.
O S O,
(29)
16
Proof. We begin with the standard decomposition of the primal-dual gap at time / 2 1,
V (p) Votxigg = Vittie (p) - V ( (p) + ViTe VrtAgg (p) V (p)
(30)
(ii)
and we next deal with (i) and (ii), separately. For the first term (i),
rtggg (p) - V (P)
1
Σ dh (s)(T - nr(a| =<(a|)))(rrt ()))(iitg((sa)))
1
Σ di (s)(TT ()) # s)) ( (s,a)
8,0
dh (s) - (a ()) s)) (8,
8,0
1
Σ d% (s) (s)) x, s)) Q (s, - (0
do (s) ( - || (-18) ( 1 #e(- +e((1.))1))
21y(1 - 7)
1
Σ dF' (8) (11++)(-11)) #((11a))1 || (+1x) - n.( [)] || - (1()))))²)
21((1 - 7)
?
+
1
Σ
1o (s)) #e(a ())
( (8, a) 1 (8, a)
1-
(31)
44

---

where the first equality is due to performance difference lemma in Lemma 28, the second equality is because of some re-arrangement, the inequality is from application of Lemma 24 to #z+1 (-1s)
and Te (.. s):
Σ (1 (al s) 1 (aa[aa)))Q@0)))) +)))Q++aa rrgg ())
I 2n (1ss)
(+|s) - +r(-1s)] - (-1s) - +-+1(-1))] - [1 - #
Σ (m(
- ==(al=)))[+4 (1((()))) - ==((1s))1²)
S 21 (1 (1s))) ((())) 1 ( (+1))) -
Similarly, we deal with the second term (ii) with some re-arrangement, and apply Lemma 24 to det1 and Xe.
VI ( V (
(Ae (V-,,)V3'..))
(Ae- V241) (0) + (re --t1) (V, Vg" (p))
+(i++1 2²)Vz (p)
s 27 ((hrt1 21)² - (de41 X1)² (de 21)2)
(Ae - -det1) (Vz (p) -V V==-i (p))
1 (0x - -ha3 (X* - -e+1)² - -(xet1 1 S2)2)
2n
(32)
On the other hand, from Lemma 25, we have
[ Te(-|s)]]
s n - - 19(8)-)
(33)
and
D& deaal I (p) Vo [p)-
(34)
Hence,
Σ az (s)( 8) ne(als)) (Q (0 - Pii (s,
$ 7 Σ
th. (s) Oott (s. -:= (s. ?
< 2m Σ 5h (s) (s)
Ar- - 105 (s, 1113
19 (8,-) - 10 (0,,))) 11))
+
2m
4772
(de 1== + (1 - 7)
1 + (1 - 72
max (ax]|(((-1 - -
(1 7)2
2m
4177 2 Kip
(1 7)2 ()e -)=-1)² + (1 - 7)5
1+
(1 - 71-
4n
(Ae 1},) (de - 2x-1)²))
11 7)2
8m 2 AAAlrip
( Σ Σdh J. (s) [|Tr(.18)) +.(-10))2= [|+e(-18) - 7)
Te- T (.1s)]
where the first inequality is due to Cauchy-Schward inequality and (33), we subtract and add 2x + +yy in the second inequality, the third inequality
Qh 1 and apply the inequality (x)
45

---

due to Lemma 22 and the boundedness of value functions and dual variables, the fourth incquality
comes from the property of Kp. and the last inequality is due to the inequality (z + y)² I 2x + 2y²
and the inequality Ipp 11, I v A Ip p'lla for two probability distributions p and p'. Mean- while, using a similar reasoning. we can derive that
(he )et1) (Vg (p) - -Vg '(o))
(Vi (p)
VØg 1()))² 2
2
m
Σ d
(s) [| ---0))m--111111111 (-11(-1))
-6
m 2
Σ (v (8) [ T-- (--((_1)]l]))
(1 76
21 2 A|
Σ dx (s) ( (1 7)
- =c(-1s)11 + [| - TT-1(11))1
where the first inequality is due to Cauchy-Schwarz inequality and (34), the second inequality is due to Lemma 22, the third inequality is an application of Cauchy-Schwarz inequality, and the last inequality is due to the inequality (I + v)² I 2x² + 2y² and the inequality ||p p' 1 S V|4I lpp p'll2 for two probability distributions p and p'.
We set notation,
2x21
872 Ki (1 - 76
1
6. == max
(1 7)
1+ (1 2gg2 :
7)3
After applying the established inequalities above to (31) and (32), we combine them into (30) as,
V. Votgng (p) - V. g (0)
1
Σ dz ( (-=((=11)))
# (-)](= 1 (.16) #te ((( (8) (1 - + (+)1= - 1| (-10) = [+)11 [| +=(11))]]
211(1 - 7
1
Σ dz' p
+
21 7)
+ 1
(Se+1 - 22,2 - (5e+1 - 2x)² - (A. - 2,)²)
2n
1
(A* - )0)² - (A* - -det1)2 - (det1 - -x,)
+
2n
+ m((, - ).)² + ne((A - 1)=
+ m1 Σ d5 (s) (| (s) # =e)l + [|
m
We notice that V V (p) - V= (p) 2 0 and non-exxansiveness of projection operators Prr.,
PA.,
PT (fe+ (-16) - 7.+1((18))
< || (.18) - Fr+ (.18)]
PA (2++1) )et1
5 x Se+1
46

---

for any x" E II and X E A If we take xt = Pri (fr(-18) and x PAx (de), then after some re-arrangement, we have
1
Σ
(8) [PT (ft+1(-1)) (-1)))))))))))))))))))) +t+1(-1))1 + 2 (Pax- (de+1) - Sc-1)2
2(1
d (s) Pm (fte (8)) 1
+ 1/2 (Pax (2c) - -)et1)²
2(1 - 7)
K
Σ
dhh (s) | ( (8)) #x(1ss)11
1
(Pa. (2x) - -20)2
2(1 7)
2
2(1 7) Σ dhd (s) | (s) --(11 ((] - (dc+1 - -20²2
2
2(1 77) n?² Σ d% (s) [ [[]+))]11 - (1
- n²²) (A: - -20²
2
+ r Σ E (s) (-(()1)) TT [=]] + c2 - xc-1)²
where we also use the assumption d= dz for any E II., By taking riar S to and using notation O and lo, we have Oc+1 S O 16 Le.
To show the convergence, we next relate Sa with O An intermediate step is to show that Çe has the following lower bound.
Lemma 20. Let Kp.. max( F 1). If we set the stepsize 1) min (1 (1->) (1-2)% ).
then the
4/4 20p
primal-duc dual iterates of OPG-PD (9) satisfy
Edn (8) (1Te((16)) #e((11)) + ( -Te(-1))1) (1 Sul? + 11 Setil))
V r+ (p) - -V+tt (o)] [=)]
1/2
for all (Tr, A) # (Fe+1,det1))
9k2 p.
maxx [|x(- #t41(-|s)|| + -
Proof.
From the optimality of ft41(. 8) in OPG-PD, we know that for any æ E II,
- -a.((sssfeflllll
[- 8) - fe+1 ())
2 n (s, T # (s)
70 (8, (-1 (- 5) म (-1 {s}} + n(2 (s,-) 2rthig (s,-), - # (-1s))
+ (8, thee r+he+1g (s, x (-1s) (+))).
(35a)
Similarly, from the optimality of Teta (: 8) in OPG-PD, know that for any II,
- (- s), T(- (1) (
- #e+
( (t 8) T+1(11s)
- (s.)) (- () u (-1 8)) + ((0 (s4th (s.+), (...((1()))) - =c41(-1s))
(s,
T01 1fthhing
(s, ) x(-1s) (+2((115))
(35b)
47

---

On the other hand, from the optimality 4e+1 in OPG-PD, we know that for any À E A.
(A++1- - -4 )411) 2 (
VV (p)(1++1 - 2) + (p) - -Va-11 (p))(())) - -2)
(36a)
and the optimality of d4t1 in OPG-PD yields,
(Ac+1 (A+1-))(AA- A441) 2 (P) - A)
V2 (p)(A++1 - A) (V Vg9 Vi (p))(A+41 - -A).
(36b)
First, take the expectation of (35a) over some state distribution dz both sides and add it to (36a),
Eg0) - (s) #t+1(11 + (A41 - 50(a -841))
7
n
( (s, (T (-+1(-1s)
1-
n
Σ (T(6) (8.-) 2 (s, ), ((( (1sss) - (-41(-1
+
1
7
Σ 1 (s. - - (8, ), x (-1s) - #11((11))
+
+ A) + '(V - (p))({t) A)
2
VT
(p)
-V ( (p)
7
Σ (5))
1 oTitig (3, - Q Q (s,
||[(-|s) (-))
n
Σ (5))
@ (8, :) - -Qam @ (8, ||T(-11
# (-18)]
1
+n (p) -) - -n11,' (p) V (p) (p)11(+111 A1
VT M (p) - / rthm_g (p) + nVft+ti (p) -
2
mlA
max ||Te( 8) (- s)ll Σ d7. (s) || #-+1(-18))
(1 7
n
Σ (s)) - Se41l # s)ll
(1 7)2
[A] [A
(1- Σ d% (s) [|](-)))) - s) (8e41 - X
(37)
where the second inequality is due to performance difference lemma in Lemma 28 and Cauchy-
Schwarz inequality, and the last inequality results from Lemma 22 and the inequality |p - p'll 5 AA| [pp -p'l, 2l2 for two probability distributions p and p'. By using the inequality ac + bd 5
48

---

d) for a 2 0.6 62 0, O, and 2 O. with some re-arrangement, we have
(max [|T( (:)())))-)))) - - (-18)( + a Se411) x
Kp Σ dp (s)
1 y | (- - - + (1 7)3
2n|AA|
[ - nel. ae(-1s)]l
+ +1Ae+1 - del + m/ppp
(1- De detil
|| - - (-1)) 1-7 Σ (s)x
Kp
max
(1 | - - +
m/\ A|
| (-11) -mm(--1))))) -T((115]1= + (1 (1ーン)aソb) th )etrl)
(1 733
+ 1 Setal 1 - del+ 778p v A
Σ d% (111((22(-11) - m 8)|l
(1 (1-1) 7)3
max
||,([-] s) - - (1.6)]]] Σ (s)x
( || (0) - #t(l15)]] + (1 - 7)3
mA
max | (s1s) - Te(-1s)]l +
77 (1- Ds - detal)
+11- Setal | 1iiii-Ael +rl+ 18pp v A
Σ do (s) (1144(1(1)))) Tr(- (-))))]
(1 - (1-7)3
n (Vithessg (p) Viltyy (o)
where the second inequality comes from the property of Kip and the last inequality is straightforward from (37). We take > O such that max If we take the square of both sides of the inequality above, then the second product argument has the following upper bound,
2g/44 D6p- [I-ン] [I- S 2 and denote Kpr == max 1)
2
Σ Th (s) (1ft+1(11s)-t(( + + 27/.A|
(1 11-20 (1-7)3 | [s) no(-115]1) + 1set1 - -Pll + 1788p
1he
-Setal
(1-7)²
2
(- Σ df (s) (1+t41(11)-- -- [|)||| +
2 || ne(-1s)]]) + 1 - Sul+ + 1 ++11xx - -detal
1
2
Σ dh (s)
(Ime(-1s)) - #e(.1 (()]s)] + 2 ( me(1)))]] + 1A - -1l++ + -/1, - -detal
3
2 de (s) ([[Te(-1)) - #e (s)]s)]] + || (.1 (8) - ne(. (s)] +
3
(I^ 2z + 1>= - -Sot1))
2
9
Σ dz (s) (|<A(-18)) #x 11) + | -s))-m()))))))))
9 ( 2,1² + +1x+ - 12)
where we use the inequality (xr + y) < 2x² + 2y² and Jensen's incquality.
Recall the definition of Kp and Rip S 1/Pmiu. where Pmin == min, p(s).
Lemma 21. Assume Pmin > 0. For any t > 1, the primal-dual iterates of OPG-PD (9) satisfy
v r+ (p) (
sup AEA max, || 8) $. 8)]l + 1A A4tal
Σ dh (s) || (- (-1s) - PTT (fe+1 (- [s)]]| + 17c1 - PA PA- (deni))
2 C...E
- 7)E) in which O is described in Lemma 26. where Co. cawin/ /2 - 1/((1-7)8)
49

---

Proof. Denote V* == V v (p) and Dmax == max E E (max, || s) - --([-s)) +
{A 1--11 X1). We observe that if we can prove that there exist constants C1, C2 > 0 such that
V
(p) V 2 alde PPx- (dc(1i)))
(38a)
EEl r+d4tgg
V min V V (p) 2 C2 Σ dh (s) 11 Pn. (f (-1s))1,
(38b)
AEa
then,
V 14 (p) - 11421(
sup
TETT, ΛEΛ max, (1T(-1)) - (141 (1))1 + 12 detal
V (-Sde (p) (P)
sup D Dmax TENTAA
max V Tell r+d441 (p) (p) -v+) + D Dinax
(
min (42)(p) XEa
Dmax
min(ci, 02)
Σ dh (s) (| - Pu (f6-1(: [s)]|| + 1d4t - Pa (24t2))
W
Dmax
which proves the lemma by taking Cp.s == min(er.c2).
Danx
We next prove (38) using the bilinear game result in Lemma 26. By the linear program formulation of constrained MDP, we can express the value function in terms of the occupancy measure q", e-g., 17 (p) = (a", + >g), where qe is the occupancy measure that lives a polytope Q that given by (15). Hence, the constrained saddle-point problem (3) reduces to,
maximize minimize (q" rr" Ag) minimize maximize (q", r >g)- ΛEΛ
9- YEA
q E
We notice that the game value keeps the same as V that is achieved at (q" ,'),, where qad the occupancy measure under the policy n² Let the set of occupancy measures associated with II* be Q*, According to Lemma 26, we know that there exists a constant > 0 such that
max 4 r Ag) V* 2 PA- E V min (q" Ag) 2 clla (e-(1")).
(39a)
(39b)
is more straightforward to see (38a) from (39a) we take İ = Sedi and e₁ = c. We next show (38b) using (39b) by taking T (-1 8) to be the policy associated with Po- (1*),
EΦs (s)
8) - n (-1s))
9 (s. g (s.
Σ d. (5)
=
(T((8) 9"d (x)
1rth (8, ) n" (8, qtd (8)
1 14 9" (s)
(s)
+ Σ d: (s)
(=())a²²) (s)
9"h (s)g""(s
(s :) 9Th (s, + Σ
1gt q" (s)
(5(s)
(5)
oF (s, 9" (s, + +10 9" (s))
Pmin
< Pmin
VISI
(s, (x, (1, + v A
Σ
1ath (8, -0 (s,
8,a
2 [
Pmin
2
|
119" P (I
Pmin
50

---

where the first incquality is due to triangle inequality, we use the fact: (1 (1-2)0 -09= (s)= = (s),
dz (s) S 1, and 1 (x, (8, s 1 in the second inequality, the third inequality is due to that n- (8) 2 Punin and we apply Cauchy-Schwand inequality the last inequality. Hence, we can further lower bound (39b),
V min (q" rr Ag) xEΛ
c 1100" - (2)(11))
cpmin
df [s) --
2 ||| A
cpmin
d= (.) (8) - (--((((-1)))
2/ |
which yields (38b) using
GPain
2 IS J4
Finally, we combine all selected constants and take D Dmax (1-3)E conclude the proof.
Lemma 22. For any policies a and TT, we have
(T7())) -2 (1>)l $
7 max || - xl(1))]l
(1 (1-
(V) V/" (p) 1
Kp
E dp
(1 7)3
Proof. By the Bellman equations, for each pair a),
(s) = r(s,a) + Σ () (100))))
8',a'
OF (s) = r(s,a) + Σ (s)''s (s)); (s,
Hence, for each pair (s, a),
(s, - 0 (s,a)]
S 7 ((8 a(d (() x'd'' ((d1)))) (6,
a'
<
Σ (( [( ((d' 18) (8,d)
e'.a'
Σ P(5'|s,a)='(d 0F(5) (s
7
8'aa
7 max [|([|s) - + (1 OF (
which yields the first inequality.
To show the second inequality, we employ the performance difference lemma to show that,
[Vg(p) (p) V (p)
(s) n'a | ( (s,a)l
Σ (5))) ||T <'(1=>]l
(1 7)2
1
Σ d7)(s) (|
(1 7)2
where replace dz by dz" using the inequality 1007/45 11 S <kp(11 7) for any policy
II.
51

---

D.2
Proof of Theorem
Proof. From the non-increasing relation (29) in Lemma 19, we have
Σ dy (s) (1 (-ss)) + _ [( - Xx)2 s
16
16
-
2(1
7
7
Meanwhile, from Lemma 20, we obtain that
Se 2 4 Σ de (8) 1. (-18) --(+1)]] + 1 [dett Ax)²
Σ dh (s) (11+611(111) - 10)1 + ||Te(.11 - =
4
(deet - 2e0² + (Ae - -})²)
4
Σ d5 (1)+1 Te(-1 T=(11)]1 + [det+ 2x)2
>
4
V
r (p) - (p) +
11²
sup
36x? p,y = II,
maxx || (8) - + 1A - Sctal)
Σ de (1) - = + 1 (5++1 - Xx)²
mel
1
C PrE
Σ Ts (1 PPn- (f ss))| + (det1 - Pa- PA- (hx1)))))))
36
417² CrpC
(1 7) min
ac+1
9M
where the third inequality is due to Lemma 21, the inequalities: (x + y)² 2 x² +2² for 2 0,
and dī (s) 2 (1 Pmin. and Cr := (1 - C. Pmmin Hence, the relation (29) reduces into,
7 TTPC as
1
θ, (1 - 7) min
O(+1
8 36x2,7
which implies that O decreasing to zero at an exponential rate.
D.3 Proof of Corollary 7
Proof. According to Theorem 6, if we take the same stepsize 17. then for any = 22(og ?),
2(1 (11-7)= Σ d7 (s) P (Ro() s)) ())2 O(e) and 2 (Pa (hx) 2.)² O
1 Σ
Let # (-1s)= Pri (- and A PA (Re). Because of the interchangeabiilty of saddle
points from Lemma 9, (#t, Xx) saddle point the set IT A for any 2
First, we have
(p) -v+))(
(#t 8) - (a s)) Q7 (s)
?
(+ ,.(1s))l
(1 2
A
(+ (-11s))
(1 7)2
VA
de (s)
[1] -
(1 7)²
52

---

where we use
incquality in the first and third inequalities, and the second inequal-
ity is due to || v vd || for x E Id, which shows V.* ( I O(ve). By the saddle-point property of (#t At), #द is also an optimal constrained policy, i.e., V, (p) V, (p).
Therefore, V. (p) t (p) - O(Ve). Second, we have
V
Vi (p) + Vi
(p)
V (p). 9
(ii)
Similar to bounding V," (p)- V (p). can show that (ii) S ((E)). By the saddle-point property
of (#t,A1 (t), Vight (p) 2 0. Therefore, - V (p) S O(Ve).
Finally, we replace the accuracy ve by c and combine all big O notation to conclude the proof. L
D.4 Zero constraint violation of OPG-PD (9)
Corollary 23 (Zero constraint violation). Let Assumplion 1 hold and the optimal state visitation distribution be unique, ie.. d = di for any x E II, and Pmin >> 0. For small c, there exists ó > O such that if we instead use the conservative constraint VT(p) )) 2 foror g' = - 7)8, and take the stepsize n from Theorem then the policy iterates of OPG-PD satisfy
V (p) V S and - V S for any Q log" _ E
where (2(-) only omits some wroblem-dependet constant.
Proof. We apply the conservatism to the translated constraint (p) 2 0 in Problem (1). Specifi- cally, for any 8 < min(5, 1), we let g' == 9 - (1 - 7)0 and define a conservative constraint,
VT
(p) 8 8 2 0.
It is straightforward to see that Assumption I ensures that (p) > 0 is strictly feasible for new slack variable g' := = 5-6. 6. We now can apply OPG-PD (9) to new Lagrangian,
L'(x, A) == (g (p)
and Corollary 7 holds if we replace in OPG-PD by g' Thus,
V (p) V s O(e) and
V V (p) s O(c) for any Ω (oog2
where 22(-) hides some wooleem-dependent constant, and тミ is optimal policy the 8-perturbed constrained policy optimization problem,
maximize V (p) e
subject to V - 0.
(40)
We notice that the above 2(-) has some problem-dependen constant > 0. Thus, we select 8 such that 8 2 eY, which is always possible for small enough e, for instance and g 5. Hence, we take 5 = & and such small then,
-V V²*(() (p) -V (p) (8) (p) eT for any t= = Ω log" )
which shows that VR (p) 2 0 for some large L.
The rest to show that V.* (p) V.* S O(c). We notice that ** is an optimal policy to Problem (40) when 5 = O. Let q" and of be associated occupancy measures of policies x" and тÿ. In the occupancy measure space, Problem (40) becomes linear program and has solution 43. Thus, we can view o as d-perturbed solution of convex optimization problem in which all functions are continuous differentiable and the domain convex and compact. It known from [129, Theorem 3.1] that the optimal solution of is continuous in ô, which implies that for any
53

---

e > O, there exists such that Kr,g*) - (r, 93)1 - O()) for any d < Thus, V,; (p) (p)1
(e)) for small enough e. Therefore,
V ( (p) I [
+ IV; (p) V (p) _ O(c)
for some large 1. Collecting all conditions ö leads to our final choice of 8 min( ( 1,8). Finally, we combine all big O notation to complete the proof.
E Other Computational Experiments
In this section, report details of our experimental setup and additional experimental results that verify merits and effectiveness of our methods: RPG-PD (6) and OPG-PD (9). We implement RPG-PD in the form of NPG [49] and the restricted probability simplex ((A) by restraining policy parameter be bounded.
To properly assess the convergence performance, our experiment is a tabular constrained MDP with randomly generated transition kernel, discount factor y 0.9, uniform rewards r E [0, 1] and utilities E [-1,1], and a uniform initial state distribution p. The constraint is (p) 2 0. To check feasibility, employ the standard policy iteration procedure solve standard MDP problem with respect to V (p). If feasible, we then solve a linear program in ceuupancy-measune space to find the optimal reward value V.5" (p) at optimal policy x² induced by the optimal occupancy measure. Throughout all experiments, the random seed is fixed and V.²i (p) takes the value 8.16 at optimal policy n².
We compare our methods RPG-PD and OPG-PD with three typical learning algorithms in the con- strained MDP literature: (i) primal-dual methods [23, 29]; (ii) dual methods [28, 24, 34]; and (iii) primal method [77]. We have reported our comparison for primal-dual methods in Section 5 and Figure 1. We now report our comparison experiments on other two baseline methods: (ii) dual methods [28, 24, 34] and (iii) primal method [77], in Section E. In addition, we showcase the last-iterate zero constraint violation performance of our methods in Section E.2, and conduct sensi- tivity analysis of our methods regularization and stepsize in Section E.3 and Section E.4, together with a variant of OPG-PD and policy-based ReLOAD [40]. All the experiments were conducted on an Apple MacBook Pro 2017 laptop equipped with 2.3 GHz Dual-Core Intel Core i5 in Jupyter Notebook.
E.1 Last-iterate convergence comparison with other baselines
We report our comparison for dual methods in Figure 4. We notice that dual methods [28, 24, 34] work double-loop fashion, where a (regularized) NPG subroutine is executed perform the dual update. To make a fair comparison, the number of dual updates and the number of NPG steps are set be 53 and 20 to ensure that dual methods take the same number of policy gradient updates: 1060, as RPG-PD and OPG-PD, and we evaluate all policy iterates inside the NPG subroutines of dual methods.
In Figure 4, RPG-PD (--) and OPG-PD (-) outperform PMD-PD [24] (--, AR-CPO [28] (--), and Accelerated Dual [34] (.... in several aspects. First, see that the known oscillation behavior in primal-dual methods also shows up in these dual methods, which could result from that we can't 't exactly evaluate the search direction of the dual update via NPG subroutine. Thus, dual methods can be viewed an instantiation of two-time-scale methods in which the primal update performs faster than the dual update. Regarding this, RPG-PD and OPG-PD show outstanding performance in suppressing oscillation behavior. Second, since RPG-PD and OPG-PD are single-timesscal primal- dual methods, easy tune algorithmic parameters compared with double-loop dual methods. For instance, in Accelerated Dual, it is relatively difficult to find a set of algorithmic parameters that avoid the sub-optimal performance in Figure Third, OPG-PD reaches the maximum reward value 8.16 and RPG-PD converges to slightly smaller reward value because of regularization, while both methods enjoy the utility constraint satisfaction in the last-iterate fashion, which seems to be difficult for dual methods because of oscillating utility values. Hence, using the same number of policy gradient updates, we have verified that OPG-PD and RPG-PD also can outperform several dual methods by yielding an optimal constrained policy in the last-iterate fashion.
54

---

80
Reward value
75
Utility value
5.0
200
400
600
600
1000
200
400
600
300
1000
Iteration
Iteration
Figure 4: Convergence performance of RPG-PD, OPG-PD, and dual methods. Learning curves of our RPG-PD (--) and OPG-PD (-), and PMD-PD [24] (--), AR-CPO [28] (--), and Accelerated Dual [34] (--.) methods. The horizontal axes represent the policy iterations { that gener- ated by each method and the vertical axes mean the value functions of the policy iterates { [T of reward value (p) (Left) and utility value V (p) (Right). In this experiment, for RPG-PD and OPG-PD, we use the stepsize = 0.1 and the regularization parameter 5 = 0.08 for RPG-PD, and the initial distribution p is uniform. For PMD-PD, AR-CPO, and Accelerated Dual, stepsize = 0.1 for the dual update, the regularized NPG stepsize a = 1, and the regularization parameter 0.08, and the uniform initial distribution p.
the
We report our comparison for a primal method in Figure In Figure RPG-PD (--) and OPG-PD (-) outperform CRPO [77] (--). We notice that although CRPO [77] works in a singlc-time-scan fashion as RPG-PD and OPG-PD, the policy has be updated by alternatively using the gradient directions of reward/utility value functions. To ensure constraint satisfaction, CRPO often switches between the gradient directions reward/utility value functions depending on the amount of con- straint violation. As result, we see that CRPO reaches a slightly lower reward value than OPG- PD's, and the constraint satisfaction is relatively conservative and has mild oscillation behavior, In contrast, OPG-PD achieves the maximum reward value 8.16 and RPG-PD converges to a slightly smaller reward value because of regularization, while both methods enjoy the utility constraint satis- faction in the last-iterate fashion. Last but not least, we have supported RPG-PD and OPG-PD with a policy last-iterate convergence theory, while such theory is unknown for CRPO as far as we know.
8.0
Reward value
7.5
Utility value
0.5
-1.0
200
800
1000
Iteration
Iteration
Figure 5: Convergence performance of RPG-PD, OPG-PD, and primal methods. Learning curves of our RPG-PD (--) and OPG-PD (-), and CRPO [77] (--) methods. The horizontal axes repre- sent the policy iterations { 2 that are generated by each method and the vertical axes mean the value functions of the policy iterates { h o. reward value (p² (Left) and utility value V (p) (Right). In this experiment, for RPG-PD and OPG-PD, we use the stepsize = 0.1 and the regu- larization parameter
0.08 for RPG-PD, and the initial distribution is uniform. For CRPO, update the policy via the NPG step with stepsize 0.1 and the uniform initial distribution p.
55

---

E.2 Last-iterate zero constraint violation comparison
In this experiment, we continue our previous tabular constrained MDP with random transition,
a discount factor 7 = 0.9, uniform rewards E [0, 1] and utilities g E [[-1, and an uniform conservative constraint (o) 2 0 in RPG-PD and OPG-PD, where g' := (1 7)6 is conservative utility function and is the conservative parameter. To get zero constraint violation regarding the nominal constraint, we apply RPG-PD and OPG-PD to the conservative constraint V (Ø)
initial state distribution p. Instead of the nominal constraint (p) 2 0,
where we take the conservative parameter 8 = 0.1. As above, we compare conservative RPG-PD and OPG-PD with three typical learning algorithms in the constrained MDP literature: (i) primal-
dual methods [23, 29]; (ii) dual methods [28, 24, 34]; and (iii) primal approach [77]. We report our comparison for primal-dual methods in Figure 6, for dual methods [28, 24, 34] in Figure 7, and for primal approach [77] in Figure 8. We observe that conservative RPG-PD and OPG-PD achieve similar performance regarding the oscillation suppression and the optimality of reward values as shown in Figure 1, Figure 4, and Figure 5. Interestingly, in Figure 6, Figure 7, and Figure 8, RPG- PD and OPG-PD converge to a utility value that is strictly above zero, i.c. V (p) > 0 for large t, which is not guaranteed in many of other methods. To sum up, we have confirmed that RPG-PD and OPG-PD can ensure zero constraint violation of instantaneous policy iterates in a finite number of training time.
8.0
Reward value
4.5
Utility value
200
800
1000
Iteration
Iteration
Figure 6: Convergence performance of RPG-PD, OPG-PD, and primal-dual methods. Learning curves of our RPG-PD (--) and OPG-PD (-), and NPG-PD [23] (--) and PID Lagrangian [29] (...) methods. The horizontal axes represent the policy iterations { 20 that are generated by each method and the vertical axes mean the value functions of the policy iterates { h > reward value V.* (p) (Left) and utility value V=((p) (Right). In this experiment, we apply RPG-PD and OPG-PD to a conservative constraint (p) 2 6, and we take the conservative parameter d 0.1, the same stepsize 0.1 for all methods, the regularization parameter 0.08 for RPG-PD, and the uniform initial distribution
E.3 Sensitivity of RPG-PD (6) regularization and stepsize
In this experiment, we use our previous tabular constrained MDP with random transition, dis- count factor 7 0.9, uniform rewards r [0, 1] and utilities g E [-1, 1], an uniform initial state distribution p. The constraint is 1 (p) 2 O. We recall that when we set the regularization parameter T = 0, RPG-PD becomes policy-based primal-dual method [23] that often suffers the oscillation issue as shown in Figure 1. However, larger regularization usually bias regularized methods more to sub-optimal solutions. Hence, it is important to reveal how the last-iterate convergence of RPG-PD depends the regularization parameter and the stepsize 77.
We first repeat executing RPG-PD with fixed stepsize = 0.1, but varying three different reg- ularization parameters 7 {0.1, 0.05, 0.013. In Figure 9, RPG-PD damps initial oscillations suc- cessfully for 0.1 and 0.05, and oscillates for = 0.01. When we decrease from 0.1 to 0.05, the reward value RPG-PD converges to becomes higher, and the utility value's oscillation is o slightly amplified initially, but damped eventually. When r is further reduced to 0.01, although the reward value reaches a value around the optimal reward value 8. 16, the utility value behaves oscillating.
56

---

80
Reward value
75
Utility value
5.0
200
400
600
600
1000
200
400
600
300
1000
Iteration
Iteration
Figure 7: Convergence performance of RPG-PD, OPG-PD, and dual methods. Learning curves of our RPG-PD (--) and OPG-PD (-), and PMD-PD [24] (--), AR-CPO [28] (--), and Accelerated Dual [34] (--.) methods. The horizontal axes represent the policy iterations { that gener- ated by each method and the vertical axes mean the value functions of the policy iterates { [ > reward value (p) (Left) and utility value Vg (p) (Right). In this experiment, we apply RPG- PD and OPG-PD to conservative constraint V (p) 2 8, and we take the stepsize 7) 0.1, the conservative parameter 5 0.1, the regularization parameter = 0.08 for RPG-PD, and the ini- tial distribution p is uniform. For PMD-PD, AR-CPO, and Accelerated Dual, we use the stepsize 7 = 0.1 for the dual update, the regularized NPG stepsize a = 1, and the regularization parameter 0.08, and the uniform initial distribution p.
Reward value
Utility value
0.0
-0.5
400
600
800
1000
200
400
600
800
1000
Iteration
Iteration
Figure 8: Convergence performance of RPG-PD, OPG-PD, and primal methods. Learning curves of our RPG-PD (--) and OPG-PD (-), and CRPO [77] (--) methods. The horizontal axes represent the policy iterations (me) 2 that generated by each method and the vertical mean the value functions of the policy iterates { of reward value V (p) (Left) and utility value V/T (p) (Right), In this experiment, we apply RPG-PD and OPG-PD to a conservative constraint V (p) 2 6, and we take the conservative parameter å 0.1, the stepsize n = 0.1, the regularization parameter 0.08 for RPG-PD, and the initial distribution is uniform. For CRPO, we update the policy via the NPG step with stepsize 7 0.1 and the uniform initial distribution p.
reason for this is that RPG-PD with a relatively small regularization parameter (compared to the stepsize) works as usual un-regularized single-time-scat primal-dual methods. Hence, increasing the regularization parameter, = 0.1 can accelerate the convergence and attenuate the oscillation more effeectively, although it makes the reward value more sub-optimal, which is also clearly shown in Figure 10.
To demonstrate the convergence of RPG-PD's policy iterates, we measure the policy optimality gap squared norm distance of policy iterates to an optimal policy n' that obtained from an mecupancy-measure-bben
linear program. From the optimality gap in Figure 10, see that three policy optimality gaps decrease sublinearly to some constants the logarithmic scale plot, which verifies the sublinear last-iterate convergence of RPG-PD's policy iterates in Theorem 2. Hence, we
57

---

conjecture that it impossible to improve the order of RPG-PD's sublinear rate, without introducing new algorithmic design.
To reduce the oscillation behavior, we repeat this experiment with a smaller stepsize 7) 0.01 as suggested by Corollary 3. We report our result in Figure 11 and Figure 12. The oscillation in the utility value previously happened for r 0.01 becomes less frequent, and the best reward value achieved in this case. A noticeable loss is that the convergence has been slowed down, apparently Figure Hence, we have shown that balancing the stepsize and the regularization parameter (e.g., Corollary 3) is important for RPG-PD to achieve better oscillation attenuation and last-iterate convergence practice.
8.0
1.0
Reward value
7.5
Utility value
0.5
0.0
-0.5
-1.0
250
500
750
1200
1250
1500
1750
2000
230 1000
1250
1500
1750
2000
Iteration
Iteration
Figure 9: Convergence performance of RPG-PD with regularization parameter (T 0.1, -), (r 0.05, -)), (r 0.01 ...... The horizontal axes represent the policy iterations { (t2 that are generated by RPG-PD and the vertical axes mean the value functions of the policy iterates { {me)e of reward value V (p) (Left) and utility value V (p) (Right). In this experiment, we fix the same stepsize 17 0.1 and take the regularization parameter among 0.1, 0.05, and 0.01, and the uniform initial distribution
Policy optimality gap
10a
109
0
250
500
750
1000
1250
1500
1750
2000
Iteration
Figure 10: Convergence performance of RPG-PD with regularization parameter 7: (r = 0.1, -).
(r 0.05. --), 0.01, ..... The horizontal axis represents the policy iterations {me) 2 that are generated by RPG-PD and the vertical axis means the policy optimality gap that measures the distance of the policy iterates fo o to an optimal policy -": Σ, Te s) x- (-|ss) || In this experiment, fix the stepsize 7) 0.1 and take the regularization parameter among 0.1, 0.05, and 0.01, and the uniform initial distribution
58

---

80
1.0
Reward value
7.5
Utility value
7.0
6.
6.0
-0.5
-1.0
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Iteration
Iteration
Figure 11: Convergence performance of RPG-PD with regularization parameter т: (r = 0.1, -), (r 0.05,- --). ...). The horizontal axes represent the policy iterations {me) that are generated by RPG-PD and the vertical axes mean the value functions of the policy iterates {Ty J oi reward value (p) (Left) and utility value v (p) (Right). In this experiment, we fix the same stepsize 1 0.01 and take the regularization parameter among 0.1, 0.05, and 0.01, and the uniform initial distribution p.
Policy optimality gap
10a
60
3x
500
1500 1750
Iteration
Figure 12: Convergence performance of RPG-PD with regularization parameter т: (r = 0.1, -),
(r 0.05, --), 0.01, ..... The horizontal axis represents the policy iterations { (me)e20 2 that are generated by RPG-PD and the vertical axis means the policy optimality gap that measures the distance of the policy iterates { o to optimal policy n": Es [e s) x [+|s) || In this experiment, we fix the stepsize 0.01 and take the regularization parameter among 0.1, 0.05, and 0.01, and the uniform initial distribution p.
E.4 Sensitivity of OPG-PD (9) to stepsize
In this experiment, we use our previous tabular constrained MDP with random transition, a dis- count factor y 0.9, uniform rewards state distribution p. The constraint is V (p) 2 O. We repeat executing OPG-PD by varying three different stepsizes E (0.05, 0.1, 0.2}. To demonstrate the optimality of OPG-PD's policy iterates, we measure the policy optimality gap via the squared norm distance of policy iterates an optimal policy x* that is obtained from an occupancy meaccyy-mauure-baae based linear program. To demonstrate the optimality of OPG-PD's policy iterates, we measure the policy optimality gap via the squared norm distance of policy iterates to optimal policy ** that is obtained from an ceaupancc--masure-baee linear program. From the policy optimality gap in Figure we see that three policy optimality gaps decrease linearly in the logarithmic scale plot, which verifies the linear last-iterate convergence of
[0, 1] and utilities g [-1, 1]. and an uniform initial
59

---

OPG-PD's policy iterates in Theorem Furthermore, in Figure we show the optimality of OPG- PD's policy iterates by plotting the optimality gap V (p) ()*( and the constraint violation V=*())) where V." (p) = 8.16. We see that the optimality gap and the constraint violation both decay asymptotically in linear rates in spite of some oscillations, and larger stepsize enjoys faster convergence. worth mentioning that, these descending oscillations actually show that value functions approaching the optimal ones. Hence, we have verified the linear last-iterate conver- gence of OPG-PD's policy iterates in Theorem using a range of constant stepsizes.
Constraint violation
107
Optimality gap
10-1
1
10-
10
10
250
500
730
1250
1500
1750
230
1000
1250
2000
Iteration
Iteration
Figure 13: Convergence performance of OPG-PD with stepsize (17 = 0.05, ...... (17 = 0.1, --.,
(1) = 0.2, -). The horizontal axes represent the policy iterations {Te > that are generated by OPG-PD and the vertical axes mean the optimality of the policy iterates { 2 of optimality gap of reward value |V.-" (p) Vi (p)l (Left) and constraint violation of utility value V (p) (Right). In this experiment, we take stepsize rj among 0.05, 0.1, and 0.2, and the uniform initial distribution
Last but not least, extend this experiment for variant of OPG-PD that is based on the multi- plicative weights update (MWU). We call this variant as an optimistic multiplicative weights update primal-dual (OMWU-PD) method which maintains two sequences for policy and dual variables each: {Thh2 and { for the policy-player, and (Nehe2 and {de121 1 for the dual- mull-player,
(=(118) = argmax E(()))
(atd)))) T(a {( (0 11 (8, - KL(T(. (8), (1))
(41a)
(14(-11s)
argmax ((-10)
x(a (
KL (s), #t(((1))
d argmin XEA
A Vm 1(p) + () - 21)²
2n
(41b)
Se-1 argmin XEA
A VT (p) + 2m
(A ).)3
where 7 is the stepsize and (fo. 2o) = (mo, Ao) E x A the initial point. OMWU-PD con- currently works with two primal iterates and two dual iterates, which is similar to OPG-PD. The only difference is that Primal update (41a) works as the NPG or MWU updates [23, 54], instead of the projected Q-ascent [58, 65], which is also different from the one-step optimistic MWU in policy-based ReLOAD [40].
To further investigate the applicability of optimistic gradient methods, we execute OMWU-PD in the same setting and report our result in Figure 14 and Figure 15. We see that the policy optimality gaps decay sublinearly in Figure 14, and the optimality gap and the constraint violation asymptotically decay in sulinear rates in Figure 15. As comparison, we repeat the same experiment for policy- based ReLOAD [40], which is different from our OMWU-PD in using one-step optimistic gradient updates. In Figure 16 and Figure 17, we observe sublinear decay of policy optimality gap, optimality gap and constraint violation, where similar shown in Figure 14 and Figure 15.
60

---

The empirical results from two MWU-based optimistic primal-dual algorithms are suggestive. First, MWU-based optimistic algorithms also have policy last-iterate convergence an optimal pol- icy. Second, convergence rates of MWU-based optimistic algorithms look slower than OPG-PD's under the same constant stepsize, which we leave immediate future work to establish sublinear convergence rates for MWU-based optimistic primal-dual algorithms.
Policy optimality gap
10
10
0
250
500
750
1000
1250
1500
1750
2000
Iteration
Figure 14: Convergence performance OMWU-PD with stepsize qp: (n) 0.05, (n 0.1,--),
(1) = 0.2, -). The horizontal axis represents the policy iterations { h o that are generated by OMWU-PD and the vertical axis means the policy optimality gap that measures the distance of the policy iterates (xe) o to optimal policy x²: Σ, (I-(=((-1s) (- ())) . In this experiment, we take the stepsize 1j among 0.05, 0.1, and 0.2, and the uniform initial distribution p.
Constraint violation
10a
Optimality gap
10a4
10
Iteration
Iteration
Figure 15: Convergence performance of OMWU-PD with stepsize (1) = 0.05, ....), (n = 0.1,
-.), 0.2, -). The horizontal axes represent the policy iterations { hee that generated by OMWU-PD and the vertical axes mean the optimality of the policy iterates mm3r02 of optimality gap of reward value |V."* (p) V. (p)] (Left) and constraint violation of utility value V (p) (Right). In this experiment, take the stepsize 77 among 0.05, 0.1, and 0.2, and the uniform initial distribution p.
Supporting Lemmas
In this section, we collect some lemmas that are helpful to our analysis.
61

---

Policy optimality gap
10a
109
0
250
500
750
1000
1250
1500
1750
2000
Iteration
Figure 16: Convergence performance of policy-based ReLOAD [40] with stepsize yy: (n 0.05, "."), (1) 0.1, (1) = 0.2, -). The horizontal axis represents the policy iterations {m 2 o that are generated by Rel.OAD and the vertical axis means the policy optimality gap that measures the distance of the policy iterates {*e he 2 o to optimal policy x²: Σ, KL.(x" (-1 (-11s, T.(. [)) In this experiment, we take the stepsize among 0.05, 0.1, and 0.2, and the uniform initial distribution p.
Constraint violation
Optimality gap
10"4
199
10-
Mmmmmm
30
10-1
250
500
730
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Iteration
Iteration
Figure 17: Convergence performance of policy-based ReLOAD [40] with stepsize my: (n 0.05,
.."), (17 = 0.1, --), (17 = 0.2, -). The horizontal axes represent the policy iterations ( Je that generated by ReLOAD and the vertical axes mean the optimality of the policy iterates { [Te o² optimality gap of reward value VV,"* (p) V (p)l (Left) and constraint violation of utility value [V) (Right). In this experiment, we take the stepsize among 0.05, 0.1, and 0.2, and the uniform initial distribution p.
E1 Lemmas in optimization
For any convex differentiable function dh. X - IR, the Bregman divergence x, x' X is given by Du (x', .x) == v5(x') (xxx) (V - z). When is a-strongly convex, D (x', x)) 2
|| - 2|1 for any z'. X. Specifically, when (xx ||^|| (z(,' || x1|
Lemma 24. Let X be convex set. If x' argmin, x (ū. D (ā, then for any X² X,
(o' -
-'-" x*,g) S Do(x* xx) - Dw (x* xx (a (x',)).
Proof. See [38, Lemma 10).
Lemma 25. Assume that ( 2 1 ||I 1'1 for some ib and p If
argmin (z.g1) .1) + Dos (ā) and x2 = argmin (2. .2) + D (σ,x)
xEX
62

---

then
21 22|1, -
11
92l1,
where 1 p 9
+ 1 1.
Proof. See [38, Lemma 11].
Lemma 26. Let R and Y R be polytopes and M Rmxx be a matrix. Then, there exists a problem-dependent constant c. > O such that
max x My V* || - Px- (x))
V' E
V min (3)) (a') My 2 c cly Py- EX
where V is the game value,
V minimize maximize x My maximize minimize x. My NEY
yEY
=e
and (X*, Y*) the set of minimax optimal strategies.
Proof. See [38, Theorem 5].
((A) be a convex set and g be a bounded vector in RRAL If x' argmin, E (.. 9) + k), x), then for any x² E X,
Lemma 27. Let
KL(x" r) - KL(x" x²)
(x - x²' ,9) s
+ 1 Σ {g()
n
EEA
where nn satisfies n9aa 2 - forrr a E A.
Proof. See [132, Theorem 2].
F.2 Properties of policy gradient
Lemma 28 (Performance difference lemma). For any two policies and x', and any state so.
V* (so) V (so) 1 1-7
E. dr E. ~ 1(18)) A (s,
Proof. See [49, Lemma 3.2].
Lemma 29 (Regularized PG and NPG under softmax parametrization). Let an entropy-regularzzed value Sunction be Vp(p) V,((p) (p) + TH(F), and define Q S A and V7 R via Bellman equations,
(7( r(s,a) + Ag(s, +BB s.a) [V*
(s) Banat --T log म (al 8) Q7 (s,a))-
Let parametrized policy be ne for some parameter Rd. If the policy me differentiable and Ea (o s) = 1, then,
0v (p)
1 - dme (s) To s) A7 (s,a)
00...
dell (s) Ta(a 8) (QT (s, a) - log (a ( 8))
for all (s, a)) E S x A, where (5, a) = Q7 (s, a) T log T 8) ( Moreover, if the exp(!...)
policy my is in form of the softmax function To (a s) En exp(e for all (s, a) E S x A, then
(F)( V.V. (p)
c(s)
1
where c(s) is an action-independenn constant.
Proof. See [52, Lemma 6].
63


Reviews:
[{"review_id": "6STbYuH4fU", "reviewer": "Reviewer_jUv5", "summary": "Two single-timescale algorithms (RPG-PD and OPG-PD) are proposed, and their finite-time convergence rates have been derived. The iteration complexity guarantees for RPG-PD are (nearly) dimension-free but are sublinear. Guarantees for OPG-PD are linear but depend on problem-dependent quantities.\n\n", "questions": "1. I could not find any explanations/insights on why the previous approaches lead to oscillations while the newly proposed approaches do not. In particular, why does OPG-PD more or less have no oscillations? Also, in Figure 8, the oscillations are more pronounced for smaller parameter choices. Why does that happen? \n\n2. It is unclear how the proposed ideas can be implemented in practice: they involve (a) computing exact expectations or Monte-carlo estimates from a priori unknown distributions and (b) optimizing certain objective functions over the set of all policy distributions, e.g., 6a, 9a, or 27a. These seem very challenging. Can the authors comment on it? \n\n3. While the authors have mentioned the online version as part of future work, do they expect this version to also have the benefits of damped oscillations?\n\n4. In practice, one often may require that the constraints not be violated with high probability. Would the proposed approach extend to cover that scenario as well?\n\n5. What is `optimistic' about the OPG-PD method? Some insights would be helpful for the reader. ", "limitations": "Limitations of the proposed techniques have been adequately discussed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Last-iterate convergence and constraint satisfaction are useful and generally more challenging. Unlike average and mixture performance measures, these do not hide possible oscillations in objective/constraint functions of immediate policy iterates, which can be undesirable for constrained dynamic systems.\n\n2. Empirical studies showing improved performance over existing algorithms. Most notably -  RPG-PD and OPG-PD suppress oscillation in utility values while achieving optimal reward values.\n\n3. Very thorough literature survey.", "weaknesses": "See Questions.\n\n Minor typos\n1. At several places, the references are to the results in the appendix, e.g., Theorem 18 below the statement of Thm. 4. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper, and the valuable feedback. Please find our specific remarks as follows. \n\n---\n## Weaknesses\n\n>1. *Minor typos: At several places, the references are to the results in the appendix, e.g., Theorem 18 below the statement of Thm. 4.*\n\n**Response**: Below the statement of Theorem 4, `Theorem 18` should be `Theorem 4`. We will correct this typo and check all cross-references in the final version. \n\n---\n\n## Questions\n\n>1. *... why does OPG-PD more or less have no oscillations? ... in Figure 8, the oscillations are more pronounced for smaller parameter choices. Why does that happen?*\n\n**Response**: A key insight into the oscillation of Lagrangian-based primal-dual algorithms is from the game-theoretic view. Primal/dual iterates in a primal-dual method are two players: max-/min-players are primal/dual updates, respectively. Gradient-based learning dynamics are not necessarily contractive at the stationary points. The simplest case is the cyclic behavior, e.g., iterates cycle in a bilinear game: $\\max_x \\min_y x^\\top y$ (see Figure 2 of [R1]) in which $(0,0)$ is not a contracting point of usual gradient descent-ascent methods. \n\nA key reason why almost no oscillation is in our OPG-PD (see Equation (9)) is that its gradient-based learning dynamics is `contracting` to the set of stationary points. Particularly, our theory (see Theorem 6) shows that the distance from primal-dual iterates to a set of optimal ones decreases to zero, linearly. Due to fast last-iterate convergence, any oscillation is damped exponentially fast, yielding `more or less have no oscillations.' \n\nFigure 8 evaluates the sensitivity of our RPG-PD (see Equation (6)) using different regularizations $\\tau \\in \\{ 0.1, 0.05, 0.01 \\}$ and a fixed stepsize $\\eta$. Decreasing $\\tau$ from $0.1$ to $0.01$ causes the utility value function in Figure 8 (Right) to oscillate more and more. A reason for this is that RPG-PD with small regularization works as an un-regularized primal-dual method. However, oscillation is inherent to naive primal-dual methods, e.g., un-regularized one [R2]. \n\nThanks for the questions, and we will emphasize these points in the final version. \n\n[R1] *ReLOAD: Reinforcement learning with optimistic ascent-descent for last-iterate convergence in constrained MDPs. ICML 2023.*\n\n[R2] *Responsive safety in reinforcement learning by PID Lagrangian methods. ICML 2020.*\n\t\n>2. *... unclear how the proposed ideas can be implemented in practice ... Can the authors comment on it?*\n\n**Response**: In practice, our primal-dual algorithms: RPG-PD (see Equation (6)) and OPG-PD (see Equation (9)) can be implemented using policy simulators. Executing primal-dual updates in RPG-PD and OPG-PD needs 2 things: (i) estimation of state and state-action value functions of a current policy; and (ii) projection onto a probability simplex. We can implement them efficiently. For instance, an version of RPG-PD with linear function approximation is given in Algorithm 1 (see it in Appendix C.9), where the policy gradient direction is a linear function. Since current policy is from the last update, we simulate it to form unbiased estimates of value functions in Algorithm 2 and Algorithm 3 (see them in Appendix C.9) and the best linearly approximated state-action value function serves as a policy gradient direction.\n\nThe policy gradient steps in Equation (6a), Equation (9a), and Equation (27a) can be evaluated explicitly.  Since Equation (6a) and Equation (27a) perform the classical mirror descent step with KL divergence; see their closed-form expressions in [R1]. For Equation (9a), it is the classical mirror descent step with Euclidean distance, i.e., projected gradient, where probability simplex projection can be solved with linear complexity [R2].\n\nThanks for the questions, and we will emphasize these points in the final version. \n\n[R1] *Mirror descent, Large-Scale Optimization for Data Science, \n\t[Link](https://yuxinchen2020.github.io/ele522_optimization/lectures/mirror_descent.pdf)*\n\n[R2] *Fast projection onto the simplex and the $l_1$ ball. MP 2016.*\n\t\n>3. *... online version ... do they expect this version to also have the benefits of damped oscillations?*\n\n**Response**: An open question raised by our work is: can we have a policy-based primal-dual algorithm with online exploration and prove its last-iterate convergence? Due to the last-iterate convergence, it would inherit the benefits of damped oscillations. We conjecture that the answer to this question is positive, considering last-iterate results for zero-sum games [R1, R2].\n\n[R1] *Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games. AISTATS 2023.*\n\n[R2] *Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games. arXiv:2303.02738. 2023.*\n\t\n>4. *... constraints not be violated with high probability ... extend to cover that scenario ...*\n\n**Response**: Our constrained MDP takes an inequality constraint on a value function. Such a constraint can approximate the feasible region of a high probability constraint, e.g., obstacle-avoidance [R1]. Hence, we can apply our algorithms to high probability constraints. We will remark this in the final version.\n\t\n[R1] *Safe policies for reinforcement learning via primal-dual methods. IEEE TAC 2022.*\n\t\n>5. *What is `optimistic' about the OPG-PD method? ...*\n\n**Response**: The notion `optimistic` is from optimization, e.g., [R1]. If we view Equation (9b) as a real policy gradient step that gives a policy $\\hat\\pi_{t+1}$, then Equation (9a) serves as a prediction step that gives an intermediate policy $\\pi_t$. Not policy gradient at $\\hat\\pi_t$, a real step uses a policy gradient at $\\pi_t$ from prediction.  Thus, OPG-PD is `optimistic` on the predicted policy $\\pi_t$, as it leads the direction of policy search. We will remark this in the final version.\n\n[R1] *Optimization, learning, and games with predictable sequences. NeurIPS 2013.*"}, {"review_id": "qL18HmP9Ci", "reviewer": "Reviewer_NJhb", "summary": "This work shows the first non-asymptotic and policy last-iterate convergence for single-time-scale algorithms in the CMDP literature. In particular, it provides nearly dimension-free sublinear last-iterate policy convergence, sublinear last-iterate policy convergence with function approximation, and problem-dependent linear last-iterate policy convergence.\n\n", "questions": "1. Compared with the references [95, 24], if there is any other technical difficulty apart from replacing the convex inequality conditions in constrained convex optimization with the specialty property of CMDP, such as the performance difference lemma?\n2. How is the last-iterate converge rate established in this paper compared with the last-iterate converge rates using two-time-scale methods? Are the convergence rates in this paper better? If not, why not, and if it is possible to reduce the gap?\n3. For problem (4), why do you directly show that the strong duality holds? Lemma 1 can not be directly applied to the problem (4).\n4. In Theorem 6, how strong is the assumption that optimal state visitation distribution is unique given that there may exist multiple optimal policies for CMDP.\n\n", "limitations": "See questions", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This work strengthened the prior works which only guarantee asymptotic last-iterate convergence or value-average or policy-mixture non-asymptotic convergence.\n2. It sets up a new framework for analyzing policy-based primal-dual algorithms via the distance of primal-dual iterates to a saddle point.", "weaknesses": "1. It is better to give a more formal definition of the \"single-time-scale\" and \"two-time-scale\" at the beginning of the paper to help readers better understand the introduction.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper, and the valuable feedback. Please find our specific remarks as follows. \n\n---\n## Weaknesses\n\n>1. *...  a more formal definition of the \"single-time-scale\" and \"two-time-scale\" ... help readers better understand the introduction.*\n\n**Response**: This is an important point. `single-time-scale` refers to the classical gradient-based methods that update multiple iterates, concurrently, using constant stepsize [R1, R2]. `two-time-scale` is from stochastic approximation [R3]: stepsizes for different iterates are relatively large/small (or iterates change relatively fast/slow). We notice that methods with two nested gradient loops are in the `two-time-scale` type, since one iterate waiting for another iteration loop is slower. We will explicitize this notion in the final version. \n\t\n[R1] *Studies in linear and non-linear programming. Stanford University Press, 1958.*\n\t\t\n[R2] *A modification of the Arrow-Hurwicz method for search of saddle points. USSR. 1980.*\n\t\n[R3] *Stochastic approximation: a dynamical systems viewpoint. Springer. 2009.*\n\n---\n\n## Questions\n\n>1. *Compared with the references [95, 24] ... any other technical difficulty apart from replacing the convex inequality conditions in constrained convex optimization with the specialty property of CMDP, such as the performance difference lemma?*\n\n**Response**: Besides handling non-convexity, our first technical contribution, we see other two considerable technical difficulties we have addressed. First, our constrained saddle-point problem is not symmetric: one takes a stochastic policy that affects transition dynamics and the other selects an action in a continuous interval that changes payoff. Our last-iterate analysis works for the asymmetric saddle points, which departs from the symmetric setting [R1, R2]. Second, a saddle-point policy is not uniformly max-min optimal, i.e., being optimal across all states, since an optimal policy depends on the initial state distribution in a constrained MDP. Our duality analysis goes beyond the per-state analysis [R3, R4], which could be of independent interest for analyzing constrained Markov games. \n\nThanks for the question, and we will emphasize these points in the final version.\n\n[R1] *Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv:2204.09228. 2022.*\n\t\n[R2] *On linear convergence of iterative methods for the variational inequality problem. JCAM. 1995.*\n\t\n[R3] *Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. COLT 2021.*\n\t\n[R4] *Can We Find Nash Equilibria at a Linear Rate in Markov Games? ICLR 2023.*\n\n>2. *... compared with the last-iterate converge rates using two-time-scale methods? ... better? ... reduce the gap?*\n\n**Response**: The last-iterate rate of RPG-PD is sublinear in time, which is worse than the linear rates of two-time-scale methods [R1, R2]. We notice that RPG-PD converges to a regularized saddle point at a linear rate, up to a neighborhood that is dictated by the stepsize and regularization parameters. The slow rate results from proper parameters that set the neighborhood to be a desired accuracy. In our experiment, RPG-PD converges to the optimal saddle point sublinearly; see Figure 9 in Appendix E.3. So, we conjecture that it is impossible to improve the order of rate without new algorithmic design.\n\nThe last-iterate rate of OPG-PD is linear in time, which matches the linear rate of the two-time-scale method [R1] and improves the linear rate in [R2]. We note that our last-iterate convergence captures the stability of primal-dual iterates, while the last policy iterates in [R1, R2] come from NPG subroutines. We also notice that problem-dependent constants occur in all three linear rates, which we leave as future work of uncovering the optimal rate. \n\nPlease see more rate comparison in Table 1 in Appendix A. Thanks for the questions, and we will emphasize these points in the final version.\n\t\n[R1] *A dual approach to constrained markov decision processes with entropy regularization. AISTATS 2022.*\n\t\n[R2] *Algorithm for constrained Markov decision process with linear convergence. AISTATS 2023.*\n\n>3. *... problem (4), why do you directly show that the strong duality holds? ...*\n\n**Response**: Because the strong duality in Lemma 1 is for the un-regularized problem (see Equation (1)), it is not relevant to the regularized constrained saddle-point problem (see Equation (4)). So, it is crucial to check well-definedness of this regularized saddle-point problem, by showing the existence and uniqueness of a saddle point; see Appendix C.1 for proof.\n\n>4. *...  Theorem 6, how strong is the assumption that optimal state visitation distribution is unique ...*\n\n**Response**: This is an important point. To measure the proximity of primal-dual iterates to a saddle point, we assume the uniqueness of the optimal state visitation distribution to define a distance metric supported by this distribution. Compared with the unique optimal policy, it is a mild assumption, since different optimal policies can share the same state visitation. This can be viewed from the linear program formulation of MDPs: occupancy measures $\\{q^{\\pi_k^\\star}(s,a), k =1,2,\\cdots\\}$ associated with optimal policies $\\{\\pi_k^\\star, k =1,2,\\cdots\\}$ share the same state visitation $q(s) = \\sum_a q^{\\pi_k^\\star}(s,a)$ for all $k$. We notice that when we restrict the set of optimal policies $\\Pi^\\star$ with this property (any such optimal policy induces the same state visitation), our theory (see Theorem 6 and Corollary 7) still holds (or algorithms indeed converge to a `set` of optimal policies that share the same state visitation). Therefore, we believe that this uniqueness assumption is arguably mild. We leave further relaxing this assumption as our immediate future work."}, {"review_id": "r3NVjs1jMH", "reviewer": "Reviewer_V7nr", "summary": "This paper studied the policy gradient primal-dual approach for constraint MDP with last iterate convergence guarantee. A regularized policy gradient primal-dual method is first proposed where regularization on the policy and dual variables are introduced to add curvature to the minimax problem and with appropriately chosen regularization factor, sublinear last-iterate convergence is obtained. An optimistic poicy gradient primal-dual method is then proposed with linear convergence of the squared distance between the last iterate (policy, dual variable) pair and the saddle region under some additional assumptions. The key analysis technique is to bridge the policy update and update in occupancy measure, and CMDP is convex w.r.t. the occupancy measure.", "questions": "The first inequality in Page 29 between Line 1045 - Line 1046: could you justify the usage of Lemma 27, since \\pi^*_\\tau may not be the optimal w.r.t. to dual variable \\lambda_t?\n\nIt seems that there is some order mismatch of the terms (i), (ii) in Eq. (20), where (i) is O(\\sqrt{epsilon}) and (ii) is O(epsilon). It is possible to further reduce the sample complexity by carefully selecting \\tau?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The last iterate convergence of algorithm for CMDP is meaningful. The proposed methods with counterparts in minimax optimization are intuitive and explained very well. Multiple varations of CMDP has been studied, i.e., linear function approximation, zero constraint violations. The I went over a majority part of the proofs and have some questions. I will increase my score after the my questions are addressed. The majority of proofs are sound to me.", "weaknesses": "I did  not find  perticular weaknesses of the current paper. The ideas are explained clearly and easy to follow. The limitations are also discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper, and the valuable feedback. Please find our specific remarks as follows. \n\n---\n## Questions\n\n> *The first inequality in Page 29 between Line 1045 - Line 1046: could you justify the usage of Lemma 27, since \\pi^*_\\tau may not be the optimal w.r.t. to dual variable \\lambda_t?*\n\n**Response**: Thank you for raising this important question. We apologize for a typo in Lemma 27: $x'$ on the left-hand side of the inequality should be $x$. We repeat Lemma 27 in a more convenient argmax-form here: if $x' \\in argmax_{\\bar{x}\\in X} \\langle \\bar{x}, g \\rangle - \\frac{1}{\\eta} \\text{KL}(\\bar{x},x)$, where $X$ is a probability simplex $\\Delta(A)$ and $g$ is a bounded vector in $\\mathbb{R}^{|A|}$, then for any $x^\\star\\in X$, $\\langle x^\\star - x, g\\rangle \\leq \\frac{1}{\\eta} (\\text{KL}(x^\\star,x)-\\text{KL}(x^\\star,x'))  + \\eta \\sum_a x_a (g_a)^2$. Since the explicit form of $x'$ is the standard update of Hedge: $x_a'\\propto x_a {\\rm e}^{\\eta g_a}$, its proof follows from the proof of Theorem 2 in the note [R1] by flipping the sign of the loss. \n\nApplication of Lemma 27 to the primal update of RPG-PD per state (see Equation (6a)) can be verified by taking $x' = \\pi_{t+1}(\\cdot \\vert s)$, $\\bar{x} = \\pi(\\cdot \\vert s)$, $g =  Q_{r+\\lambda_t g +\\tau \\psi_t}^{\\pi_t}(s,\\cdot)$, $x = \\pi_t(\\cdot \\vert s)$, and $x^\\star = \\pi_{\\tau}^\\star(\\cdot \\vert s)$.  We notice that the left-hand side of the inequality in Lemma 27 does not require the optimality of $x^\\star$. Then, the boundedness of the value function $g$ leads to the inequality between line 1045 and line 1046.\n\nThanks for the question, and we will remove this typo and explicitize the application of Lemma 27 in the final version.\n    \n[R1] Lecture 1, Introduction to Online Optimization/Learning, [Link](https://haipeng-luo.net/courses/CSCI659/2022_fall/lectures/lecture1.pdf)\n\n> *It seems that there is some order mismatch of the terms (i), (ii) in Eq. (20), where (i) is O(\\sqrt{epsilon}) and (ii) is O(epsilon). It is possible to further reduce the sample complexity by carefully selecting \\tau?*\n\n**Response**: Given a desired accuracy $\\epsilon\\in(0,1)$, adding two big O notations $O(\\epsilon)$ and $O(\\sqrt{\\epsilon})$ leads to $O(\\epsilon) + O(\\sqrt{\\epsilon}) \\leq O(\\sqrt{\\epsilon})$ when $\\epsilon\\to 0$, which summarizes the way we combine the terms (i), (ii) in Equation (20). \n\nWe note that the regularization parameter $\\tau$ has been carefully selected. The KL distance between the policy iterate and the optimal regularized policy is determined by a sum of ${\\rm e}^{-\\eta \\tau t}$ and $\\eta/\\tau$, where $\\eta$ is the stepsize and $\\tau$ is the regularization parameter. To ensure $\\epsilon$-optimality gap and $\\epsilon$-constraint violation, the KL distance must be $O(\\epsilon^2)$ and the regularization parameter needs to be $\\Theta(\\epsilon^2)$  (see Proof of Corollary 3). Hence, the stepsize has to be $\\Theta(\\epsilon^4)$ and the iteration complexity thus becomes $\\Omega  (1/\\epsilon^6)$.\n\n---\n\nWe would like to thank the reviewer again for the helpful comments. Please feel free to let us know if there are any other concerns we can address that could improve your assessment of our work.\n\n"}, {"review_id": "sGdIdbubbD", "reviewer": "Reviewer_tcAd", "summary": "This paper studies the problem of policy searching for constrained MDPs. The authors devise two Lagrangian-based named regularized policy gradient primal-dual (RPG-PD) method and optimistic policy gradient primal-dual (OPG-PD) method, respectively. Their methods are single-time-scale and thus insensitive to hyperparameter changes. They also show that the proposed methods have the property of last-iterate convergence and give the convergence rate in theoretical analysis.", "questions": "* The paper only considered constrained MDP with a single constraint as a simplified case. Can the results be generalized to the case of multiple constraints?\n* Could the homotopic strategy (gradually shrink the regularization term, see [Li et al. 2022]) be applied to the RPG-PD method? Would that yield better theoretical guarantees?\n\n\n[Li et al. 2022] Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity\nYan Li, Guanghui Lan, Tuo Zhao arXiv:2201.09457", "limitations": "See comments above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and easy to follow. The related works section is particularly commendable, providing a comprehensive overview of relevant works in this field. The authors are the first to give a non-asymptotic rates for last-iterate convergence of single-timescale primal-dual methods. The theoretical analysis is technically sound. From my view point this paper can be a nice addition to the literature on constrained policy optimization.", "weaknesses": "* The convergence of the proposed methods relies on the strong duality property of CMDPs, which may not be true for general parametrized policy classes (like NNs).\n* The numerical experiments are only conducted on tabular cases. And I suggest the authors compare their results to more baselines, for example, primal methods like CRPO in [102].\n* The paper seems a little bit too long to appear in a conference proceeding. I suggest the author remove some redundant explanations or examples to shorten the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper, and the valuable feedback. Please find our specific remarks as follows. \n\n---\n\n## Weaknesses\n\n> - *The convergence of the proposed methods relies on the strong duality property of CMDPs, which may not be true for general parametrized policy classes (like NNs).*\n\n**Response**: This is an important point. First, strong duality is a `structural property` of constrained MDPs when no function approximation is used, i.e., it can be `proved` under the strict feasibility/Slater condition; see e.g.,  [R1, R2]. Slater condition has been commonly used in the literature to develop convergence theory for constrained MDPs, see e.g., [R2, R3] and many follow-up works.\n\nSecond, in the function approximation setting we do not require strong duality in the `parametrized policy class`, and the function approximation error has captured the possible duality error caused by the inexpressiveness of the function class; see also [R3]. Interestingly, we would like to point out that for our regularized method: RPG-PD (see  Equation (8)), the theory (see Theorem 4 and Corollary 5) only assumes the saddle-point property/strong duality for the regularized Lagrangian, without requiring the strong duality for the original un-regularized Lagrangian. Hence, even if the original strong duality fails, when the saddle point of the regularized Lagrangian is close to the solution of the original constrained MDP problem, our regularized method is still applicable. \n\nThanks for the comment, and we will remark this point in the final version.\n\n[R1] *Constrained Markov Decision Processes. Routledge. 2021.*\n\n[R2] *Safe policies for reinforcement learning via primal-dual methods. TAC 2022.*\n\n[R3] *Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs. arXiv:2206.02346. 2022.*\n\n> - *The numerical experiments are only conducted on tabular cases. And I suggest the authors compare their results to more baselines, for example, primal methods like CRPO in [102].*\n\n**Response**: We have compared RPG-PD and OPG-PD with a primal method CRPO [R1] in Figure 4 in Appendix E.1. To control constraint satisfaction, CRPO switches between the gradient directions of reward/utility value functions depending on the amount of constraint violation. As a result, Figure 4 shows that CRPO reaches a slightly lower reward value than OPG-PD's, and the constraint satisfaction is relatively conservative and has mild oscillation behavior. Hence, we conjecture that the policy last-iterate convergence holds for CRPO, up to some error caused by the switching overhead.\n\nThanks for the suggestion, and we will check other baselines and add more experiments in the final version.\n\n> - *The paper seems a little bit too long to appear in a conference proceeding. I suggest the author remove some redundant explanations or examples to shorten the paper.*\n\n**Response**: Thanks for the suggestion, and we will shorten the final version according to your suggestion.\n\n---\n\n## Questions\n\n> - *The paper only considered constrained MDP with a single constraint as a simplified case. Can the results be generalized to the case of multiple constraints?*\n\n**Response**: We can generalize the constrained saddle-point formulation (see Equation (3)) for constrained MDPs with a finite number of constraints by introducing a vector form of Lagrangian multiplier. Thus, the dual updates of RPG-PD and OPG-PD are in vector form and the last-iterate convergence analysis carries over to this general case. We notice that we are not the first using such a simplification, as it has been used in several other studies, e.g., [R1, R2, R3]. \n\nThanks for the question, and we will remark this point in the final version. \n\n[R1] *Provably efficient model-free constrained rl with linear function approximation.  NeurIPS 2022.*\n\n[R2] *DOPE: Doubly optimistic and pessimistic exploration for safe reinforcement learning. NeurIPS 2022.*\n\n[R3] *Natural policy gradient primal-dual method for constrained markov decision processes. NeurIPS 2020.*\n\n> - *Could the homotopic strategy (gradually shrink the regularization term, see [Li et al. 2022]) be applied to the RPG-PD method? Would that yield better theoretical guarantees?*\n\n**Response**: Thank you for providing this important reference [R1]. We believe that the homotopic strategy can be adopted in our regularized method, and hopefully with better convergence guarantee. We notice two challenges in applying the homotopic strategy: (i) an optimal policy is not necessarily induced by some deterministic optimal policies that usually do not exist for a constrained MDP; (ii) since instability of saddle-point gradient dynamics often results from large stepsize, monotonically increasing stepsizes could make primal-dual algorithms divergent. Hence, additional effort is needed to prove the homotopic strategy for solving constrained MDPs. \n\nThanks for the suggestion, and we will remark this reference, and include this important future direction in the final version.\n\t\n[R1] *Homotopic policy mirror descent: Policy convergence, implicit regularization, and improved sample complexity. arXiv:2201.09457. 2022.*\n\n---\n\nWe would like to thank the reviewer again for the helpful comments. Please feel free to let us know if there are any other concerns we can address that could improve your assessment of our work.\n"}]

Author rebuttal:

Meta-review: The paper makes a nice contribution in achieving both non-asymptotic and last-iterate convergence for single-time-scale primal-dual algorithms in solving CMDP. All reviewers are positive about the the paper and agree it should be accepted.
Decision: Accept (poster)