Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning
Authors: Alessandro Montenegro
Marco Mussi
Matteo Papini
Alberto Maria Metelli
Venue: NeurIPS 2024 poster (2024)
Keywords: Constrained Reinforcement Learning
Last-Iterate Convergence
Global Convergence
Policy Gradients
Primary area: reinforcement_learning

Abstract: *Constrained Reinforcement Learning* (CRL) tackles sequential decision-making problems where agents are required to achieve goals by maximizing the expected return while meeting domain-specific constraints, which are often formulated on expected costs. In this setting, *policy-based* methods are widely used since they come with several advantages when dealing with continuous-control problems. These methods search in the policy space with an *action-based* or *parameter-based* exploration strategy, depending on whether they learn directly the parameters of a stochastic policy or those of a stochastic hyperpolicy. In this paper, we propose a general framework for addressing CRL problems via *gradient-based primal-dual* algorithms, relying on an alternate ascent/descent scheme with dual-variable regularization. We introduce an exploration-agnostic algorithm, called C-PG, which exhibits global last-iterate convergence guarantees under (weak) gradient domination assumptions, improving and generalizing existing results. Then, we design C-PGAE and C-PGPE, the action-based and the parameter-based versions of C-PG, respectively, and we illustrate how they naturally extend to constraints defined in terms of *risk measures* over the costs, as it is often requested in safety-critical scenarios. Finally, we numerically validate our algorithms on constrained control problems, and compare them with state-of-the-art baselines, demonstrating their effectiveness.

Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning
Alessandro Montenegro Politecnico di Milano, Milan, Italy alessandro. hww.aaaddr..ootteeerooooooo montenegro@pollii..
Marco Mussi
Politecnico di Milano, Milan, Italy marco wwwsmmuussssnnam
Matteo Papini
Alberto Maria Metelli
Politecnico di Milano, Milan, Italy matteo. www.teeo.pppiiipplll....
Politecnico di Milano, Milan, Italy al beertomaria. wtt.mmaaaaaammeeeeeeeee.eeee wwt.mmmmtteelleeeeeeeeeeeeeeeeee imi
Abstract
Constrained Reinforcement Learning (CRL) tackles sequential decision-making problems where agents are required to achieve goals by maximizing the expected return while meeting domain-specific constraints, which are often formulated as expected costs. In this setting, policy-based methods are widely used since they come with several advantages when dealing with continuous-contro problems. These methods search in the policy space with action-based or parameter-based exploration strategy, depending on whether they learn directly the parameters of a stochastic policy or those of a stochastic hyperpolicy. In this paper, we propose a general framework for addressing CRL problems via gradient-ber based primal-dual algorithms, relying variable regularization. We introduce an C-PG. which exhibits global last-iterate convergence guarantees under (weak) gradient domination assumptions, improving and generalizing existing results. Then. we design C-PGAE and C-PGPE, the action- and the parameter-based versions of C-PG, respectively, and we illustrate how they naturally extend to constraints defined in terms of risk measures over the costs, it often requested in safety-critical scenarios. Finally, we numerically validate our algorithms on constrained control problems, and compare them with state-of-tt of-the-art baselines, demonstrating their effectivvness.
alternate ascent/descent scheme with dual- algorithm, called
Introduction
When applying Reinforcement Learning (RL, Sutton and Barto, 2018) to real-world scenarios, we tasked with addressing large-scale continuous control problems where, in addition to reaching a goal, it is necessary to meet structural or utility-based constraints. For instance, an autonomous- driving car has its main objective of getting to the desired destination (i.e., goal) while avoiding collisions, ensuring the safety of people on the streets, adhering to traffic rules, and respecting the physical requirements of the engine avoid damaging it (i.e., constraints) (Likmeta al., 2020). To pursue such an objective, it is necessary to extend the RI. problem formulation with the possibility to account for constraints. Constrained Reinforcement Learning (CRL., Uchibe and Doya, 2007) aims at solving this family of problems by employing RI. techniques to tackle Constrained Markov Decision Processes (CMDPs, Altman, 1999), which provide an established and widely-used framework for modeling constrained control tasks. The conventional CRL framework primarily focuses on constraints related directly to expected costs (Stooke et al., 2020; Ding et al., 2020: Ying
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

et al., 2022; Ding et al., 2024). However, especially in safety-cring cafety-critica contexts, the expected cost may not represent a reliable index of safe behavior. In response to this issue, chance constraints were introduced to ensure that the probability of unsafe events is minimized. Nonetheless, employing chance constraints presents several challenges (Chow et al., 2017). To strike balance between these two extremes, constraints are defined in terms of risk measures over the costs. Examples include the Conditional Value at Risk (CVaR, Rockafellar and Uryasev, 2000) and the Mean- Variana (MV, Markowitz and Todd, 2000; Li and Ng, 2000). These risk measures offer generalization of the previous concepts, allowing for the consideration of uncertainties while preserving the focus on the cost. When incorporating constraints on risk measures, CRL is often referred to as Risk- CRL (Chow et al., 2017).
Among the RL methods applicable to CMDPs, Policy Gradients (PGs, Deisenroth et al., 2013) are particularly appealing. Indeed, PGs have demonstrably achieved impressive results in continuous- control problems due to several advantages that make them well-suited for real-world applications. These advantages include the ability to handle continuous state and action spaces (Peters and Schaal, 2006), resilience sensor and actuator noise (Gravell et al., 2020), robustness in partially-observabee environments (Azizzadenesheli et al., 2018), and the possibility of incorporating expert knowledge during policy design (Ghavamzadeh and Engel, 2006), which can simplify the learning process and improve the efficacy, safety, and interpretability of the learned policy (Likmeta et al., 2020). PGs can be categorized into two key families depending on the way exploration is carried out in the policy space (Montenegro et al., 2024). Following their taxonomy, we distinguish between the action- based and the parameter-based exploration paradigms. The former, employed by REINFORCE (Williams, 1992) and GPOMDP (Baxter and Bartlett, 2001), focuses on directly learning the parameters of a parametric stochastic policy. The latter, employed by PGPE (Sehnke et al., 2010), is tasked with learning the parameters of a parametric stochastic hyperpolicy from which the parameters of the actual policy (often deterministic) are sampled.
Policy-based CRL has gained significant popularity in solving constrained control problems (Achiam et al., 2017). Within this field, algorithms are primarily developed using primal-dual methods (Chow et al., 2017: Tessler et al., 2019; Ding et al., 2020, 2021; Bai et al., 2022), which can be formulated through Lagrangian optimization of the primal (i.c., policy parameters) and dual variable (i.e., Lagrange multipliers). Even though the distinction between the exploration paradigms is well known in the PG methods literature, the current state of the art in Policy- CRL focuses only on the action-based exploration approach (Achiam et al., 2017: Stooke et al., 2020; Bai et al., 2023), while the cettmmeter-basee one remains unexplored. A critical challenge for policy- based Lagrangian optimization algorithms is ensuring convergence guarantees. Existing works have spent a notable effort in this direction (Ying et al., 2022: Gladin al., 2023; Ding et al., 2024). Recently, (Ying et al., 2022: Gladin et al., 2023; Ding et al., 2024) manage to ensure global last-iterate convergence guarantees. However, these approaches are affected by some notable limitations: (i) the provided convergence rates depend on the problem dimension (e.g., the cardinality of the state and action spaces), limiting their applicability to tabular CMPDs and preventing scaling to realistic continuous control problems; (éi) they focus on softmax policies only, disregarding other more realistic policy models; (iii) (Ding et al., 2024) ensure convergence when a single constraint only is present.
Original Contribution. The goal of this work is to introduce a framework for solving constrained continuous control problems using policy-based primal-dual algorithms that operate in both the action-based and parameter-based policy gradient exploration scenarios, while providing global last-iterate convergence guarantees with general (hyper)policy parameterization. Specifically, the main contributions of this work can be summarized as follows:
In Section 2, we introduce general constrained optimization problem, which is agnostic w.r.t or parameter-based paradigm.
both the
In Section 3, we introduce C-PG, general policy-based primal-dual algorithm optimizing the regularized Lagrangian function associated with the general constrained optimization problem shown in Section 2. We show that, under (weak) domination assumptions, it simultaneously achieves the following: (i) last-iterate convergence guarantees to a globally optimal feasible policy (i.e., satisfying all constraints): (ii) compatibility with CMDPs having continuous state and action spaces; (ii1) the ability to handle multiple constraints.
In Section 4, we introduce C-PGAE and C-PGPE, the action-based and parameter-based versions of C-PG. respectively. Both algorithms are designed to also handle constraints on risk measures, thus extending the applicability space of the father algorithm C-PG. This is achieved by employing
2

---

parametric unified risk measure formulation, for which we show the mapping to several risk measures of the unified one and we present the specific form of all the estimators.
In Section 5, we numerically validate our proposals against state-of-the-art baselines in constrained control problems. Related works are discussed in Appendix B. The proofs of all the statements reported in Appendix E.
2 Preliminaries
Notation. For measurable set X, we denote as 4(X) the set of probability measures over X. For P E A we denote with p its density function and we will interchangeably use x ~ P or p express that random variable is distributed according to P. For n, m E N with & m, we denote [n] := (1,2....., n} and with [n, m] := {n, n + 1, I,..., m]. For a vector æ E Rd, we denote z; the i-th component of For E R, define (a)-
max a} and we extend the notation to vectors as (x)* ((x1)* ..... (xa))()a))) Given set X' S Rd denote with Hx the Euclidean norm projection, i.e., Nxx E arg y lyy - æ||2 for any vectors æ, y Rd, we denote with (x, y) their inner product. A function
Rdd, For two
Rd R is L1- Lipschitz continuous if [f(x) f(x') | < LiIlæ - æ'1l2 and L2-smooth if it is differentiable and [V,f(>) - f=ff<'))2 < L2 x æ' 12|,, for every æ, x' E Rd
Constrained Markov Decision Processes. A Constrained Markov Decision Process (CMDP, Altman, 1999) with U constraints represented by Mc :- (S, (<))=( (bx [e (40, 7). where S E S and A S A are the measurable state and action spaces, p : S x A + A (S) is the transition model, where p(s'|s, a) is the probability density of getting to state s' E S given that action a E A is taken in state 8 E S, r x A [-1,0] 0] is the reward function, where r(8, a) is the instantaneous reward obtained by playing action in state 8, Q. S A [0, 1] is the i-th cost function, where (s, a) is the i-th instantaneous cost obtained by playing action a in state 8,
b, Jmax] with Jmax 1-2" is the threshold for the i-th cost for every [U]. No E A(S) is the 1-
initial state distribution, and 7 E [o, 1] is the discount factor. A trajectory r length T E N O (+0) is sequence of T state-action pairs:
(s+,0: ar,0:..., S,,T-1; dr, The discounted return over a trajectory T is R(T) == -iT-1 7"r(8,,t, a,,)), while the i-th discounted cumulative cost is C((T) - (8 ar.:). We define the additional cost function co a) := -r(s, a) and Co(T) = = R(F). Note that R(T), C2(T) E [max] for every E [U]] and trajectory т.
Action-based Policy Gradients. Action-basee (AB) PG methods focus on learning the parameters 0 E θ Rd of a parametric stochastic policy To S A(A), where To(a(s) represents the probability density of selecting action a A being in state s E S. At each step t of the interaction with the environment, the stochastic policy is employed to sample an action a, (-)x)). To assess the performance of To w.r.t. the i-th cost function, with e [0. UT. we employ the AB performance index JA,i O + R. which is defined as (O) := Ex-pa(10) [C((T)], where
PA(T,0) = (o((7.0) IT To Te(a,,1ss:))p( (0.r:s)))sss.ss151113 (r.,) is the density of trajectory 7 induced by policy me.
barameter-based Policy Gradients. Parameter- based (PB) PG methods focus on learning the parameters p E R S Rd of parametric stochastic hyperpolicy Up E A(O). The hyperpolicy Up is used to sample parameter configurations 0 ' to be plugged into underlying parametric policy To, that will be then used for the interaction with the environment. Notice that no can also be deterministic. To assess the performance of v/ w.r.t. the i-th cost function, with i [0, L: employ the PB performance index Jp,, : R I, which is defined as (p) == Eg [E [E--px((10) [T)(-
Constrained Optimization Problem. Having introduced the AB and PB performance indices, we formulate constrained optimization problem (COP) agnostic w.r.t. the exploration paradigm:
min Dey
J+,((v) s.t. (v) < b,, Vi [U].
(I)
where f E [A,P) and is generic parameter vector belonging to the parameter space V. When
A, we are considering the AB exploration paradigm, then V O. On the other hand, when R.
P. are in the PB exploration paradigm, then V
3

---

3 Last-Iterate Global Convergence of C-PG
In this section, we present C-PG, general primal-dual algorithm that optimizes regularized version of the Lagrangian function (Section 3.1) associated with the COP of Equation (1). After having introduced the necessary assumptions (Section 3.2), we show that C-PG exhibit dimension-free' last-iterate global convergence guarantees (Section 3.3). While C-PG designed be agnostic w.r.t. the exploration approach, we introduce two specific versions of C-PG in Section 4 for AB or PB, respectively. For notation convenience, in the rest of this section, we use J4 in place of J4,5.
3.1 Regularized Lagrangian Approach
To solve the COP of Equation (1) resort the method of Lagrange multipliers (Bertsekas, 2014) introducing the Lagrangian function Co A) = Jo(v) Σi-1 (J((v) b.) Jo(()) + (x, ((v) bb, where v E V is the primal variable and Ae Ry are the Lagrangian multipliers or dual variable, Equation (1) as a min-max max optimization problem min max, x 20 Lo(v, A) and we denote with Ho(v) == maX Co(v,>) the primal function and with Hg mingey Ho(v). To obtain last-iterate convergence guarantee. we make use of a regularization approach. Specifically, let be a regularization parameter, we define the w-regularized Lagrangian, function as follows:
(JI....: Ju) and b (bi..... .b) This allows to rephrase the COP in
Lv, = Jo(D) + Σ (J(())
w |1l2 Jo(u) + (A.J(v) - 2 - b.) 2
1212 (2)
The ridge regularization makes Cw A)) a strongly concave function of À at the price of bias that is quantified in Lemmas E.I, E.2 and E.3. Thus, we address the w-regularized min-max optimization problem mi maxxeл (v, A), where A == {} R ||ll2 & - Jmax), in replacement of the original (non-regularized) one. For this problem,
introduce the primal function Ha (v) = maxXEλ (u, A), that, thanks to the ridge regularization, admits the closed- form expression (v) = Jo(v) + X ()=(((i(v)) b)) = Jo(v) + 2u (J(()) 1 where the optimal values of the Lagrange multipliers is given by (*() T (J b)) (J(v) b)* that is guaranteed to have norm smaller than w -- /U Furthermore, we define H min (v). C-PG updates the parameters (vx, Aς) with an alternate gradient descent- ascent scheme for every k E N:
Primal Update
Dual Update
Uk+1 1ly (vx - So (us, Ac+1 11. (As + CA. (vi)
where Cu.k, SA > are the learning rates and Vo (Ux, As), (AC. AR) are estimators the gradients V V,,Cu Aa), (V,, AR) of the regularized Lagrangian function.
3.2 Assumptions
Before diving into the study of the convergence guarantees of C-PG, in this part, we list and motivate the assumptions necessary for our analysis.
Assumption 3.1 (Existence of Saddle Points). There exist v and X By such that
Lo(v) x²) = min maxteRy, Lo(v,A) A).
Assumption 3.1 ensures that the value of the min-max problem attained by a pair of primal-dual values v E V and A E Ry which, consequently, satisfy Lo Lo(vg A) & Lo(vg. >3) & Lo(v, Xi) for every U V and À E R² zg. Analogous assumptions have been considered by Yang et al. (2020) and Ying et al. (2022). Thus, (ut A5) is a saddle point of the Lagrangian function Co and, consequently, strong duality holds. Alternatively, commonly requested in CRL works, assuming
'The dimension free property (Liu et al., 2021: Ding et al., 2020, 2022, 2024) is achieved when the conver- gence rates do not depend on the cardinality of the state and/or action spaces.

---

Slater's condition combined with the requirement that the policy space covers all Markovian policies ensures strong duality (e.g., Paternain et al.. 2019; Ding et al., 2020, 2024).
Assumption 3.2 (Weak v-GGradient Domination). Let &b E [1. There exist 01 > and 31 > 0 such that, for every w V and XE A, it holds that:
Vo,ol 2)1 e an (Lo(v, () min Co 21) - B w'ev
(3)
Assumption 3.2 is customary in the convergence analysis of policy gradient methods and it is usually enforced on the objective Jn only (Yuan et al., 2022; Masiha et al., 2022: Fatkhullin et al., 2023). In particular, when 81 = O, we speak of (strong) vi-gradient domination. In this form, for a generic exponent vp E [1,2] 2]. this assumption has been employed by Masiha et al. (2022). Particular cases are when ف I, which corresponds to the standard (weak) gradient domination (GD), while for v 2. we have the so-called the non-regularized Lagrangian function Co (i.e., w = 0). However, it is easy to realize that it holds for the regularized one L., by simply computing the terms of Equation (3) replacing Lo with Lw..
(PL) condition. Notice that Assumption 3.2 is enforced on
Remark 3.1 (When does Assumption 3.2 holds?). As remarked by Ding et al. (2024), the Lagrangian function, for a fixed value of X, can be regarded as the expected return of a new reward function - -Cu- (X, C) where C (Ci....y Ct) As a consequence, sufficient condition for Assumption 3.2 is when the selected class of policies guarantees the e) -i-gradient domination regardless of the reward function. For instance, in tabular environments with natural policy parametrization, i.e., To(() O, for every 8 E S, the PL. condition (v) = 2 and 31 = 0) holds (Bhandari and Russo, 2024). Moreover, in tabular environments with softmax policy, i.e., To(a|s)cr exp(0(s. ()), GD (1é and B1 0) holds (Mei et al., 2020). This enables a meaningful comparison of our results with resorting to softmax policies (e.g.. Ding et al., 2020; Gladin et al., 2023; Ding et al., 2024). More in general, when (i) the Fisher information matrix induced by policy тe is non-degenerate for every 0 E θ i.e F(O)
E log To (a]ss ) Ve log Te(a) [a) s 2 1₂ for some pr > O and (ii) a compatible function approximation bias bound holds, i.e., Exg [[AT (s, a) - (1 7) Ve log Toe a { & Ebias being u = (VO)"VeJolf (0) and the advantage function A computed w.r.t. reward -Co - (A, C),
-1 and 31 = (1 7) V Ebiass where G is such that the weak GD (1/ = 1) holds with on = G
Vo log To ( (8) || & G (Masiha et al., 2022).
In principle, we could have enforced Assumption 3.2 on the primal function (v) only. However, this would come with two drawbacks: (i) the assumption would now depend explicitly on w; (ii) the considerations of Remark 3.1 would no longer hold. Nevertheless, in Lemma E.4, we prove that Assumption 3.2 induces an analogous property on the primal function Hw)v) in the regularized case.
Assumption 3.3 (Regularity of the Regularized Lagrangian Lw). There exists L1, L2, La > such that, every V, v' E V, for every X, X'E A, the following hold:
VxCol, A) Li-Lisschitz w.r.t.
VxCo(v, A) - VxLolv', A)112 < L1 v
(4)
Co(:, A) Lz-Smooth w.E.t V: V.Lo(v,-) Li-Liccchitz w.r. X:
VoColv,1 VoLole', a)][2 < L2/1U e'
(5)
V.,ool, A)- - V.Co(V, 1)1| < La/A- X/22.
(6)
Notice that, similarly to Assumption 3.2, we realize that if Assumptioo 3.3 holds for the non- regularized Lagrangian Lo, it also holds (with the same constants) for the regularized one L. for every w > O. The regularity conditions of Assumption 3.3 are common in the literature (Yang et al., 2020) and mild when regarded from the policy optimization perspective. Equation (4) is satisfied whenever the constraint functions Jj are Lipschitz continuous w.r.t. V. Indeed, VV A) VxCo(v', 2 [J(v)- - J(u')22 Equation (5) is fulfilled when the objec- tive function Jn and the constraint functions Jr are smooth w.r.t. V and the Lagrange multipliers are bounded (guaranteed thanks to the projection II,), since VoLolv, A) V.Lo(e' (V,, A) &
(v/h(v) V=.'(v'')+>"" Au \vV)).(( - VeeJ(vi) Finally, Equation (6) is fulfilled whenever functions J; admit bounded gradients, since VVColv, A) VoLo(v, X)Il2 & (v.J(v)(X-X) It is worth noting that Le depends on the norm of the Lagrange multipliers and, consequently, due
2 AAssumption 3.1 combined with Slater's condition, i.e, the existence of a parametrization ò E V for which there exists { > 0 such that (.) b < -E for all i E [0] (strictly feasible), allows providing an upper bound to the Lagrange multipliers |X la x E- (Jo( Jo( )) using standard arguments (see Ying et al., 2022).
5

---

to the projection operator, we have that L2 = =(w=)) whereas L1 and L3 are independent on w. Explicit conditions on the constitutive elements of the MDP and (hyper)policies to ensure Lipshitz- ness and smoothness of these quantities are reported in (Montenegro et al., 2024, Appendix E) for both the AB and PB cases. These regularity properties enforced on f are inherited by the primal - -smooth (Lemma E.7). Concerning the regularity of E w.r.t. X, we observe that it is a quadratic function and, therefore, it is w-smooth and satisfies the PL condition, i.e., Assumption 3.2 with 15 2, 31 O, and with 01 (Lemma E.S).
function H. which results to be (I2 + 1
Assumption 3.4 (Bounded Estimator Variance). For every V E V and X E A, the estimators > V.,C.W A) and V (v, A) are unbiased for V. = + - > >.V.J.(()) and (U, J(v) b wA with bounded variance, i.e., there exist V,, Vx < +00 such that:
Varl War(V (V, 2)] & Vos
VarlVxCu 2)] $ Vx.
(7)
Note that Vo typically depends on the Lagrange multipliers and, for standard sample mean estimators, it is of order V. Ou thanks to the projection operator. Contrary, Vx usually not affected by since the term w is not estimated and, thus, it does not impact on the variance of the sample mean estimator. In Section 4, explicit estimators are provided for both the AB and PB cases. The variance of such estimators can be easily controlled by leveraging on the properties of the score function as done in previous works (see Papini al. 2022 and Montenegro al. 2024, Appendix E).
3.3 Convergence Analysis
We are now ready to attack the convergence analysis of C-PG to the global optimum of the COP of Equation (1). To this end, we study the potential function defined as (x 0g xhg, where aj == (wH))))))) ) - Ho] and by == H[
L A+]] and E (0. will be specified we have that both ag. by 0 and, consequently,
later. Since ak by e O, intuitively, if Px()) convergence is achieved. Let us start relating Pk (x). with the solution of the COP in Equation (1).
Theorem 3.1 (Objective Function Gap and Constraint Violation). Let > O. Under Assumption 3.1, Px & 6, it holds that:
[[ Jo(va)] & c+
2 1812
[[(J.(n)) b,)* 4c 11
e [U].
(8)
Theorem 3.1 justifies the study of the potential Pa as technical tool to ensure convergence. Indeed, whenever Pk & both the (i) objective function gap and (ii) the constraint violation scale linearly with and with the regularization parameter of the regularized Lagrangian C. multiplied by the norm of the Lagrange multipliers of the non-regularized problem A 2. which are finite under Assumption 3.1. This expression also suggests choice of w O(e) to enforce an overall error on both quantities. Note that, from Theorem 3. 1, it is immediate to employ a conservative constraint (b/ < b; 4c- w/| x
to achieve zero constraint violation with modification of the algorithm.
We are now ready to state the convergence guarantees for the potential function.
Theorem 3.2 (Convergence of Pk). Under Assumptions 3.2, 3.3, 3.4, for X < 1/5, sufficiently small e and w. and a choice of constant learning rates Çui (x, we have Px(x) & e + B:/a1 whenever:
K = O(w log(e-3) if & = 2 and the gradients are exact (i.e., Vn = V\ = =0);
K Oww-le- - -1) i (1,2) and the gradients are exact (i.e., Vu Vx 0);
K = Olw-3e $ ++ if wb E [1,2] and the grudients are estimated (i.e., V, = ((w-2) and
VA O(1))
Some comments are in order. First, Theorem 3.2 holds for specific choice of the constant X (0, 1/5) defining the potential function Px. Second, the presented rates hold for sufficiently small values of and w. This just for presentation purposes, as the sample complexity can only improve if we increase the values of and w. Third, in the proof, an explicit expression of the learning rates is provided. Concerning their orders, for the case of exact gradients, we choose CA -1 and Go Oww), whereas for the estimated gradient case, we choose (A = ((we2f0) and Cu Ow3
We highlight the dependences on w since, as we shall see later, we will set w = (c)) having, consequently. an effect on the convergence rate.
'In the context this statement, the O(-) notation preserves dependences on e and w only.
'Theorem 3.2 provides an iteration peraatio-complexity guarantee. Concerning the estimated gradient case, this translates into sample complexity guarantee since we are allowed estimate gradients with single sample.

---

Exact Gradients
Estimated Gradients
yi 1 (GD)
(1,(1,2)
2 (PL)
- (GD)
(c
2/- (PL)
Fixed
w le E+1
log((=
3 log((=
w 3 3 (og(e=")
-6- (log(= ))
w- ((e)
")og(e"")
-lo((E-))
c ")og(e"))
e "log(e=))
Table Summary of the sample complexity results of C-PG when either keeping w fixed or setting as O(c).
Assuming w to be a constant, we observe that both learning rates display the same dependence on c and, consequently, they are in single-time scale. However, as we have seen in Theorem 3.1, in order to obtain guarantees on the original non-regularized problem, we have to set w (c), leading to fwo-time scales algorithm. Fourth, we observe that, for both exact and estimated gradients, the sample complexity degrades the constant &b of the gradient domination moves from 2 to 1, delivering the smallest sample complexity when the PL condition holds. Finally, we highlight that C-PG jointly: (i) converges to the global optimum of the COP problem of Equation (I); (éi) delivers a last-iterate guarantee; (iti) has no dependence on the cardinality of the state or action spaces, making it completely dimension-free free. Table and Figure I summarize the results of Theorem 3.2.
Exact gradients
Estimated gradients
1.2
1.4
1.6
1.8
2
Figure I: Plot of the exponents of in the cases of Table 1.
4 Action-based and Parameter-based Primal-Dual Algorithms
In this section, introduce C-PGAE and C-PGPE, the action-based and the parameter-based versions of C-PG, respectively. Both the algorithms have been designed to tackle continuous risk-constrained optimization problems (RCOP), generalizing the COP of Equation (1) and thus extending the appli- cability space of C-PG. This is done by employing parametric unified risk measure formulation, which leads to having framework for solving risk-constrained problems via policy- based primal- dual methods operating in both the action-bused and parumeter-buset PGs exploration scenarios. Moreover, this framework allows handle constraints enforced on several risk measures, which will be discussed below. We first introduce parametric unified risk measure and formulate an exploration-agnosti RCOP (Section 4.1). Then, we present both C-PGAE and C-PGPE (Section 4.2).
4.1 CisstConst Optimization Problem
We start presenting the notion of unified risk measure originally introduced by Bisi et al. (2022). For the AB case, to evaluate the performance of policy To w.r.t. the i-th cost, with i E [0, U]. given two functions Ji IR2 - I and gi R - IR, we define the AB-risk measure as:
min (0, TH)) where JA, Tk) == E 7.E
m)) + (()).
r-px(-10)
Similarly, for the PB case, to assess the performance of hyperpolicy up w.r.t. the i-th cost, with i e [0O, U1. we define the PB-risk measure as:
min (p.)(p.))) where Jp.(p.mk) = E E E [f((C((T) + 9.()). MER
(10)
0-up T-pa(-10)
Some observations are in order. First, by selecting the functions fa and gi. we generate different risk measures (Table 2). Details on the presented risk measures and on the mappings can be found in Appendix C. Second, the risk measure itself is defined as another minimization problem over the additional real variable n) In principle, if we replace the constraints on cost expectation of the COP in Equation (1) with the risk measures presented above, we are in the presence of a bilevel optimization problem. However, it is immediate to realize that we can merge variables with the primal variables v of the COP without changing the optimum. Finally, difference between enforcing risk-based constraints in the AB and PB cases. Indeed, while for AB the stochasticity inducing the risk is the one generated by the policy no and the environment, for PB we have the joint stochastic process of the hyperpolicy up- policy no (when stochastic), and the
us appreciate the semantic
7

---

AB GPOMDP-liK
Risk Measure
Parameter
Need for
f((C((r),))
9<(n)
Estimator
Expected Cost
Ci(7)
0
Yes
Mcan Variance
(1 - (xm) NC((T)?
Partial
CVaR.,.
I-a (C(rr)) -))*
No
Chance
7
1l (C,(T) e n.
No
Table 2: Mapping of the unified risk measure to risk measures.
environment. To the best of our knowledge, this paper is the first proposing to enforce risk-based constraints for parameter-based exploration.
Having introduced the notions of AB and PB unified risk measures, constrained optimization problem (RCOP) agnostic w.r.t. the exploration paradigm and the risk measure:
formulate a risk-
min VEV MERE
(p) s.t. Jt,(,, mi) < b, e [U]:
(11)
where E {A, V V is the parameter and 1 = (M....,, nO) E R are the auxiliary variables.
As for the COP of Equation (I), we define the regularized Lagrangian function for the RCOP
(Equation 11) as follows:
(u, = JT,olu,
Σ Au (J.aal - b..) | a-1
(12)
with t E (A, We assume that E,, is differentiable w.r.t. u and subdifferentiable' w.r.t. n, while, by construction, it is already differentiable w.r.t. A.
Remark 4.1 (Do the Convergence Guarantees of Section 3 Apply the RCOP?). When all the fr and Ii are selected in order to consider the expected values of the corresponding C. (i.e., (TC nk) C,(T) and gı (1()))) = 0), then E coincides with Lw, thus, all the theoretical results presented in Section hold, This is not true in general. For some risk measures Et may not smooth or even differentiable in v n, or it may violate the weak gradient domination assumption. Although out of the scope of the present paper, studying the preservation of the (weak) gradient domination for risk-based objectives is appealing future research direction.
4.2 Algorithms: C-PGAE and C-PGPE
Algorithms. Both algorithms. whose pseudo-codes are deferred to Appendix A, aim solving the RCOP of Equation (11), finding the best feasible (hyper)policy parameterization. The alternate ascent/descent primal-dual prototypical algorithm the same as described in Section In particular, at each iteration k e [K], the algorithms collect N trajectories (employing the chose exploration paradigm) to update the primal and dual variables as:
Primal Updates
Dual Update
Uk+1 < U/ Go.k v ( AE, Ms)
A++1 - R SA. V V ( AE, m++1),
76++1 77 Sr, V T,, (Uk, Ak. mx)
where the values are considered to projected into their spaces, and Co, CA. Sy.k are the learning rates at the k-tth iteration for v, X, and v), respectively. Notice that, since we use alternate ascent/descent, the update for AR+1 uses the updated primal values th++1 and m In practice, this requires collecting first batch of N/2 trajectories using the (hyper)policy uy to perform the primal updates, computing Us+1 and 77+1- Then, it is necessary to collect new batch of N trajectories using the updated (hyper)policy 1 in order to perform the dual update, computing A which also leverages 7-+11
Forr the sake of generality, we admit risk optimization also objective function. As illustrated in Appendix D. some risk measures (e.g., CVaR.,) deliver Lagrangian functions that admit subgradients and not gradients w.r.t. 77.
8

---

Estimators. Here, we provide the risk-agnostic form of the estimators used to perform the primal and dual updates. In particular, the gradient of CT. with respect to ny is closely related to the choices of fi and 9t- Therefore, the discussion is deferred to Appendix D, where we also explicitly derive all the estimators for the risk measures presented in Table 2 and for both exploration paradigms. The estimator of the gradient of L w.r.t. À has the same form for both C-PGAE and C-PGPE, that is:
V A n)
Σ (S(C(T)) 78+1) g(nx+)))))))))))))))))))(() 1)) b WhR: N
1
(13)
where the trajectories are collected with the AB or the PB exploration paradigm. F(C((),
=
(fi (Ci(r). fo (C)))))n))) and g(n) = (m))...... ..........nnnn (Nt)))
C-PGAE (Algorithm 1) is the action-based version of C-PG. At each iteration k E [K] the agent collects N trajectories by playing the policy To,, then it alternatively updates the policy parameter O and the risks parameter n, or the Lagrange multipliers X. The update relies on the estimator:
Vols (O.
1 Σ V Valogre, (an,alsr.)) (Jo(Co(T)))m..)) + Σ
which reduces to the prototypical basion-based algorithm REINFORCE (Williams, 1992) in the risk-neutral case. When allowed by the choice of St. we switch a GPOMDP-style estimator (Baxter and Bartlett, 2001) which suffers less variance. See Appendix D) for details.
C-PGPE (Algorithm 2) the parameter-based version of C-PG. At each iteration [K], the algorithm samples N parameter configurations (ei] from the hyperpolicy V'u. then collects a single trajectory Tú, obtained by playing the policy ne., for each sampled parameterization 0,. The sampled trajectories and parameters are then used to alternatively update the hyperpolicy parameter vector p and the risks parameter vector 17. or the vector of Lagrange multipliers X. In particular, the update relies on the following estimator:
U
A v (pe Ak. mk)
=
N _
Vp log (0:) (Jo (Co(T)), m,,0) +
Σ
Xufu (Cu(Ti): N6,.))
u=1
which reduces to the parameter-based algorithm PGPE (Schnke et al., 2010) in the risk-neutral case.
5 Numerical Validation
In this section, we empirically validate some of the theoretical results shown throughout this work. Ex- perimental details and additional results are provided in Appendix H. The code to run the experiments in this paper is available at https: //gt::///tttttt trub. wwt./cmm//////eeee http///onnnngoleeeeeeeeeeeeeeeee lessandro/Magiie
Comparison in DGWW. We compare our C-PGAE against the sample-based versions of NPG- PD (Ding et al., 2020, Appendix H) and RPG-PD (Ding et al., 2024, Appendix C.9) on a Discrete Grid World with Walls (DGWW, see Appendix H) with a horizon of T 100, and with a single constraint on the average trajectory cost. The methods are learning the parameters of tabular softmax policy and the learning phase considers constant step sizes. Figure 2a shows the average return and the average cost curves over the trajectories seen during the learning. As can be noticed, C-PGAE strikes the objective of the COP with fewer trajectories w.r.t. the competitors. Indeed, both NPG-PD and RPG-PD require additional O([S) [[) trajectories per iteration.
Comparison in LQR. We compare our C-PGAE and C-PGPE against the continuous sample-based version of NPG-PD2 (Ding et al., 2022, Algorithm 1), working with generic policy parameterizations. Additionally, we consider RPG-PD2, a ridge-regularized version of NPG-PD2. The environment is a bidimensional CostLQR (Appendix H) with a horizon T' = 50 and a single cost that the algorithms should keep below b 0.2 on average. C-PGAE, NPG-PD2, and RPG-PD2 learn the parameter of a linear gaussian policy, while C-PGPE the ones of a gaussian hyperpolicy over a linear deterministic policy. All the step sizes are chosen with Adam (Kingma and Ba, 2015) scheduler. Figure 2b reports the learning curves for the average return and the cost, confirming that our methods solve the COP with fewer trajectories. Indeed, being both NPG-PD2 and RPG-PD2 actor-critic methods, they suffer from the inner critic loop, which requires the collection of additional trajectories (500 here). We stress that the actor-critie methods were very sentitive to the hyperparameters selection, especially the length and the step size of the inner loop (see Appendix H).

---

-20
-40
Trojectopy
Aveeaggo Trajecoryy
-62
-10
-80
G-POAS
-15
C-POPE
NPG-PD RPG-PD
NPG-PD2
RPG-P172
5,000
10,000
15,000
20,000
25,000
30,000
3-10P
10
6-10"
6-101
Trooottoriss
Trajectories
C-POAE
0.6
C-POAE
Average Thajectory Cost
RPG-PD
NPG-PD2
3
RPG. FD2
Avenne
0.2
0-
0-
5,000
10,000
15,000
1010
100
3- 10P
4-
100
10
Trajontories
Trajestories
DGWW.
(b) CostLQR.
Figure 2: Average return and cost in CostLQR and DGWW environments (5 runs, mean +95% C.I.).
Chanee
20
Chanee
Risk
C-POPE
POAE
MV
MV
Prequnccy
20
CVaR
Frequeecy
15
CVaRR
Cost
26.91 + 0.09
25.80 i 0.14
Average Coet
10
Average Cost
CVaaR,
23.07 1. 0.26
23.08 1. 0.24
10
MV
24.23 1 0.23
0.75 0.26
26.34 0.16
23.07 0.26
Cast
Value
Cost Value
(a) C-PGPE
(b) C-PGAE.
(c) Avg. Ret. (5 runs, mean + std).
Figure 3: Cost distributions with (hyper)policies learned considering different risk measures (5 runs).
Risk constraints Swimmer. In Figure 3, show the empirical distributions of costs over 100 trajectories of the learned (hyper)policies via C-PGPE and C-PCAE. This experiment considers the cost-based version of the Swimmer-v4 MuJoCo (Todorov et al., 2012) environment, with single constraint over the actions (see Appendix H), for which we set b = 50. The experimental results show that C-PGPE learns hyperpolicy paying less when using risk measures compared to average cost, with the smallest costs attained by CVaR,, C-PGAE shows similar results, although the difference between CV the Chance constraints and average significant. Notice that, the minimum amount of cost is obtained using MV constraints even the learned policy exhibits poor performances (Table 3c). In all the other cases, both C-PGPE and C-PGAE learns (hyper)policiess exhibiting similar performance scores.
constraints
not very
6 Conclusions
In this work, we proposed a general framework address continuous CRL problems via primal-dual policy-based algorithms, leveraging on an alternate ascent-descent approach. Our exploration- agnostic proposal C-PG exhibits dimension-free global last-iterate convergence guarantees, under the standard (weak) gradient domination assumption. Furthermore, we introduced C-PGAE and C-PGPE, action and parameter-based versions of C-PG which enable embedding risk-based constraints, enlarging the capabilities of our framework in addressing constrained real-world problems. Future works should focus on matching the sample complexity lower bound prescribed by (Vaswani et al., 2022) and devising algorithms with the same rates of C-PG with single time-scale.
10

---

Acknowledgements
The authors acknowledge the project FAIR that has been funded by the European Union - Next Generation EU within the project NRPP M4C2, Investment 1.3 DD. 341 15 March 2022 - FAIR Future Artificial Intelligence Research Spoke 4 PE00000013 D53C22002380006 The authors acknowledge the CINECA award under the ISCRA initiative, for the availability of high-performance computing resources and support. The authors acknowledge AI4REALNET that has received funding from European Union's Horizon Europe Research and Innovation programme under the Grant Agreement No 101 119527. Views and opinions expressed are however those of the author(s) only and do necessarily reflect those of the European Union. Neither the European Union the granting authority can be held responsible for them.
References
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: an introduction. MIT Press, 2018.
Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, Riccardo Giol, Marcello Restelli, and Danilo Romano. Combining reinforcement learning with rule-based controllers for transparent and general decision-making in autonomous driving. Robotics Auton. Syst., 131:103566 2020.
Eiji Uchibe and Kenji Doya. Constrained reinforcement learning from intrinsic and extrinsic rewards. In IEEE International Conference on Development and Learning, pages 163-168. IEEE, 2007.
Eitan Altman. Constrained Markov Decision Processes. CRC Press, 1999.
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by PID lagrangian methods. In Proceedings of the International Conference Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 9133-9143, PMLR, 2020.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems (NeurIPS), 33:8378-8388 8390, 2020.
Donghao Ying, Yuhao Ding, and Javad Lavaei. A dual approach constrained markov decision processes with entropy regularization. International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pages 1887-1909. PMLR, 2022.
Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, and Alejandro Ribeiro. Last-iterate convergent policy gradient primal-dual methods for constrained mdps. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(1): 6070-6120, 2017.
Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of risk, 2:21-42, 2000.
Harry M Markowitz and G Peter Todd. Mean-variance analysis in portfolio choice and capital markets, volume 66. John Wiley & Sons, 2000.
Duan Li and Wan-Lung Ng. Optimal dynamic portfolio selection: Multiperiod mean-variance formulation. Mathematical Finance, 10(3):887-406 2000.
Mare Peter Deisenroth, Gerhard Neumann, and Jan Peters. survey on policy search for robotics. Foundations and Trends in Robotics, 2(1-2):1-142, 2013.
Jan Peters and Stefan Schaal. Policy gradient methods for robotics. JEFF/RSJ International Conference Intelligent Robots and Systems, pages 2219-2225 IEEE, 2006.

---

Benjamin Gravell, Peyman Mohajerin Esfahani, and Tyler Summers. Learning optimal controllers for linear systems with multiplicative noise via policy gradient. IEEE Transactions on Automatic Control, 66( ( 1):5283-5298 2020.
Kamyar Arizzadenesheli, Yisong Yue, and Animashree Anandkumar. Policy gradient in partially observable environments: Approximation and convergence. arXiv preprint arXiv: 1810.07900, 2018.
Mohammad Ghavamzadeh and Yaakov Engel. Bayesian policy gradient algorithms. Advances in Neural Information Processing Systems (NeurIPS), 19, 2006.
Alessandro Montenegro, Marco Mussi, Alberto Maria Metelli, and Matteo Papini. Learning opti- mal deterministic policies with stochastic policy gradients. Proceedings of the International Conference Machine Learning (ICML). PMLR, 2024.
Ronald Williams. Simple statistical
algorithms for connectionist reinforcement learning. Machine Learning, 8:229-256, 1992.
Jonathan Baxter and Peter L. Bartlett, Infinite-horizon policy-gradiens estimation. Journal of Artificial Intelligence Research, 15:319-350. 2001.
Frank Sehnke, Christian Osendorfer, Thomas Rückstieß, Alex Graves, Jan Peters, and Jürgen Schmid- huber. Parameter-exploring policy gradients. Neural Networks, 23(4)5551-559 2010.
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained policy optimization.
In Proceedings of the International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 22-31. PMLR, 2017.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations (ICLR), 2019.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang, and Mihailo R. Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, pages 3304-3312. PMLR, 2021.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In AAAI Conference on Artificial Intelligence, pages 3682-3689, AAAI Press, 2022.
Qinbo Bai, Amrit Singh Bedi, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm. In AAAI Conference on Artificial Intelligence, pages 6737-6744 AAAI Press, 2023.
Egor Gladin, Maksim Karmazn,, Karina Zainullina, Varvara Rudenko, Alexander V. Gasnikov, and Martin Takác. Algorithm for constrained markov decision process with linear convergence. In International Conference on Artificial Intelligence and Statisties (AISTATS), volume 206 of Proceedings of Machine Learning Research, pages 1 11506-11533, PMLR, 2023.
Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arXiv:2111.00552 2021.
Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Basar, and Mihailo R. Jovanovic. Convergence and sample complexity of natural policy gradient primal-dual methods for constrained mdps. CoRR, abs/2206.023.4 02346, 2022.
Dimitri P Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-nonconcave minimax problems. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 1153-1165, 2020.
12

---

Santiago Paternain, Luiz F. O. Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. In Advances Neural Information Processing Systems (NeurIPS), pages 7553-7563, 2019.
Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3332-3380. PMLR, 2022.
Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochastic second-order methods improve best-known sample complexity of sgd for gradient-dominated functions. Advances Neural Information Processing Systems (NeurIPS), 35: 10008822-1875,,, 2022.
Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for sssher-oondegeneee policies. In Proceedings of the International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 9827-9862 PMIR, 2023.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Opera- fions Research, 2024.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proceedings of the International Conference Machine Learning (ICML), pages 6820-6829. PMLR, 2020.
Matteo Papini, Matteo Pirotta, and Marcello Restelli. Smoothing policies and safe policy gradients. Machine Learning, 111(11):4081-44 -437,, 2022.
Lorenzo Bisi, Davide Santambrogio, Federico Sandrelli, Andrea Tirinzoni, Brian D. Ziebart, and Marcello Restelli. Risk-averse policy optimization via risk-neutral policy optimization. Artif. Intell., 311:103765, 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Emanuel Todorov, Tom Erez, and Yuval Tassa Mujoco: A physics engine for model-based control. In JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5026-5033. IEEE, 2012.
Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained mdps. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerík, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. CoRR, abs/1801 101 .0..57777 2018.
Yinlam Chow, Ofir Nachum, Edgar A. Duéñez-Guzmán, and Mohammad Ghavamzadeh. A lyapunov- based approach safe reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS). pages 8103-8112, 2018
Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 3121-3133, 2019.
Yongshuai Liu, Jiaxin Ding, and Xin Liu. IPO: interior-poine policy optimization under constraints. In AAAI Conference on Artificial Intelligence, pages 4940-4947, AAAI Press, 2020.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. CRPO: A new approach for safe reinforcement learning with convergence guarantee. In Proceedings of the International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 11480-118 11491. PMLR, 2021.
Felisa J. Vázquez-Abad, Vikram Krishnamurthy, Katerine Martin, and Irina Baltcheva. Self learning control of constrained markov chains- gradient approach. In IEFE Conference on Decision and Control (CDC), pages 1940-1945. IEEE, 2002.
13

---

Shalabh Bhatnagar and K. Lakshmanan. An online actor-critic algorithm with function approximation for constrained markov decision processes. J. Optim. Theory Appl., 153(3)6688-700 708, 2012.
Tianqi Zheng, Pengcheng You, and Enrique Mallada. Constrained reinforcement learning via dissipative saddle flow dynamics. In Asilomar Conference Signals, Systems, and Computers (ACSSC), pages 1362-13300 1366. IEEE, 2022.
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. In Proceedings of the International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 25303-25336. PMLR, 2023.
Yu-Guan Hsieh, Franck Iutzeler, Jéróme Malick, and Panayotis Mertikopoulos, On the convergence of single-call stochastic extra aitraggradiem methods. In Advances Neural Information Processing Systems (NeurIPS), pages
2019.
Yin-Lam Chow and Marco Pavone. Stochastic optimal control with dynamic, time-consistent risk constraints. In American Control Conference (ACC), pages 390-395, IEEE, 2013.
Vivek S. Borkar and Rahul Jain. Risk-constrained markov decision processes. IEEE Trans. Autom. Control., 59(9)22574 25799999995579 2014.
Qiyuan Zhang, Shu Leng, Xiaoteng Ma, Qihan Liu, Xueqian Wang, Bin Liang, Yu Liu, and Jun Yang. Cvar-constrained policy optimization for safe reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2024.
Aviy Tamar, Yonatan Glassner, and Shie Mannor. Policy gradients beyond expectations: Conditional value-at-risk. CoRR, abs/ 100.3666,,, 2014.
Lorenzo Bisi, Luca Sabbioni, Edoardo Vittori, Matteo Papini, and Marcello Restelli. Risk-averse trust region optimization for reward-volatility reduction. In Proceedings of the International Joint Conference Artificial Intelligence (IJCAI), pages 4583 4589. ijeai.org, 2020.
Yudong Luo, Guiliang Liu, Pascal Poupart, and Yangchen Pan. An alternative to variance: Gini deviation for risk-averse policy gradient. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Richard Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NeurIPS), pages 1057-1063. The MIT Press, 1999.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Brian DO Anderson and John B Moore. Optimal control: linear quadratic methods. Courier Corporation, 2007.
14

---

Appendix
Table of Contents
A Pseudo-codes
15
B Related Works
16
On the Unified Risk Measure
C.I Expected Cost and
18
C.2 Chance Constraints, Value Risk, and Conditional Value at Risk
18
C33 Unified Risk Measure Mapping
18
D Estimators
20
Parameter-hased Algorithm: C-PGPE
20
D.2 Action-baser Algorithm: C-PGAE
22
E Proofs
24
F Technical Lemmas
36
Recurrences
G.1 Analysis when 0
37
G.2 Analysis for b 0
38
H Experimental Details and Additional Results
38
H.1 Experimental Details
38
H.2 Details for the comparison against the basclines DGWW ................................
40
Details for the comparison against baselines in CostLQR
................................
40
H.4 Details for the risk-constrained experiment Swimmer-v4 ................................
41
H.5
Risk-constrained experiment Hopper-v4
43
H.6 Regularization Sensitivity Study
43
H.7
Computational Resources
47
Pseudo-codes
Algorithm 1: C-PGAE.
Algorithm 2: C-PGPE.
Input: Ilterations K; batch size N: regularization initial parameters: Go. Ao, and njo
Input :tteratonns K; batch size N: regularization w; initial parameters: po. Ao, and no: step sizes: Cp.ks CA.b. Sn.
step sizes: Ço.k. S2.b, Sn.
E [K] do Collect N trajectories (T:)se[M) with mee-.
for k e [K]
2
Sample parameters (0i)ee[ with Mpa-1
l is odd then
3 With each (Te, collect a trajectory T. if k odd then
0₂ 0x-1 Co. Co.4-1vo VoCr. (0 Ae-1 m--1)
- mh-1 GyA-1 VaRa, (D--1 De-1
Cunk D A. 1.71 1) Th - Th- - Gn.-n Vo (pa-s. Ae-t, Ma-1)
Pi
else
A + 1 VaRa. (0 1:-11:111 Ai 1. 1)
else
end
A Au Ca. V
end
end
end
Return 0g
Return PK
15

---

B Related Works
Policy Optimization Approaches for Constrained Reinforcement Learning. Policy Optimization- algorithms for Constrained Reinforcement Learning mostly follow primal-only or primal-dual approaches. Primal-only algorithms (Dalal et al., 2018; Chow et al., 2018; Yu et al., 2019; Liu et al., 2020; Xu et al., 2021) avoid considering dual variables by focusing on the design of the objective function and by designing the update rules for the policy at hand incorporating the constraint satisfaction part.
The main benefit of employing primal-only algorithms lies in the fact that there is no need to consider another variable to learn, and therefore, no need to tune its learning rate. However, few of the existing methods establish global convergence to an optimal feasible solution. For instance, Xu et al. (2021) propose CRPO, an algorithm employing an unconstruined policy maximization update taking into account the reward when all the constraints are satisfied, while leveraging on-policy minimization updates in the direction of violated constraint functions. Moreover, it exhibits average global convergence guarantees for the tabular setting. On the other hand, primal-dual algorithms (Chow et al., 2017: Achiam et al., 2017: Tessler et al., 2019; Stooke et al., 2020; Ding et al., 2020, 2021; Bai et al., 2022; Ying et al., 2022: Bai et al., 2023; Gladin et al., 2023; Ding et al., 2024) are the most commonly used and investigated. Indeed, the effectiveness of using the primal-dual approach is justified by Paternain al. (2019), which states that this kind of approach has zero duality gap under Slater's condition when optimizing over the space of all the possible stochastic policies. Among the reported works, Stooke al. (2020) propose PID Lagrangian, a method to update the dual variable, smoothing the oscillations around the threshold value of the costs during the learning. The practical strength of such method is that can be paired with any of the existing policy optimization methods. The other cited works are treated in details in the next paragraph.
Lagrangian-basse based Policy Search Convergence Guarantees. A lot of research effort has been spent in studying the convergence guarantees for primal-dual policy optimization methods. In this field, the goal is to ensure last-iterate convergence guarantees showing rates that are dimension-free i.e. not relying on the state and action spaces' dimensions, and working with multiple constraints. In the rest of this paragraph, we talk about single time- scal- algorithms when the methods at hand prescribe the usage of the same step sizes for both the primal and dual variables' updates. Vázquez- Abad et al. (2002) and Bhatnagar and Lakshmanan (2012) propose primal-dual policy gradient- methods built upon distinct time-scales and relying on nested loops. Such methods only show asymptotic convergence guarantees. Chow et al. (2017) propose two primal-dual methods ensuring asymptotic convergence guarantees. The peculiarity of those methods lies in the fact that their notion of CMDP encapsulates risk-based constraints, introducing an additional learning variable. Their algorithms have guarantees of asymptotic convergence to stationary points. The recent works by Zheng et al. (2022) and Moskovitz et al. (2023) also propose methods ensuring asymptotic global convergence guarantees. These methods exploit ceuupancy-measur iterates rather than policy iterates. Ding et al. (2020) propose NPG-PD, which relies on a natural policy gradient approach and, under Slater's assumption, ensures tiieeniion-depndder in the single-constrained setting with a single time-scale and with exact gradients. This work has been extended by Ding al. (2022), which strikes dimension-free rates, but still guaranteeing just average-rate convergence with exact gradients. However, sample-based versions of NPG-PD showing, under additional assumptions, the same convergence rates are provided by the authors. Another work ensuring an average-iterate rate is the one by Liu et al. (2021). The latter exhibits convergence rate of order Ö(e-)) considering to act in tabular CMDPs with softmax policies and having access to exact graidents and a generative model. Liu al. (2021) propose also sample-based version of their algorithm, keeping the same setting previously described, which ensures a convergence rate on average of order Ō Both Ying et al. (2022) and Gladin et al. (2023) propose algorithms involving regularization. The proposed methods rely on natural policy-based subroutines and show dimension- dependent last-iterate global convergence guarantees, relying on two time-scales. These methods work also with multiple constraints. Finally, Ding et al. (2024) propose RPG-PD and OPG-PD, exhibiting last-iterate global convergence guarantees under Slater's condition in single- constraint setting. The former is a regularized version of the algorithm proposed by Ding et al. (2020), showing last-iterate global convergence at a sublinear rate. The latter leverages on the optimistic gradient method (Hsieh et al., 2019) to unlock a faster linear convergence rate. These methods show single time-scale
average-itee itteate global convergence guarantees
rates and both leverage on exact gradients. However, for
16

---

Algoriihm
Dimension
Setting
Exploration Type
Gradients
Assumptions
Complesity
Cumplexity
leeration
Dual Descent (Ving et al. 2022)
T 50
2
AB
Inesact
Slater Sufficient Exploration
0 (e c-
о (log'e c
Softmax
Cutting Plane (Gladia al., 2023)
I 30
x+
AB
Inesact
Uniform Enpodicity
Slater
0 ( log" c
o (log' c-))
Softmax param.
Oracle
(Ding et 2024)
Exact
(x xoght""
param.
Inesact RPG (Ding
==1 T' Softmax param.
Inexact
Transt Br. Bounded
Stot. Err. Dounded
01-"" 1og"" (2)
OPG-PD (Ding et al., 2024)
T- 20
--11
AB
Exset
Slater
o (log"+-"))
Softmax
C-PS (Thia wack)
U TeNo [-2)
General param.
AB and PR
Exact Inesact
3.2, 3.3, 3.4
Aam. 3.1,
Table
Table
Bound
(er"))
Table 3: Comparison among primal-dual methods ensuring last-iterate global convergence guarantees.
RPG-PD there exists an inexaet version showing, under additional assumptions on the statistical and transfer errors and the relative condition number (Ding et al., 2024, Assumption 2), the same guarantees of the exact one. It is worth noticing that all the mentioned works just consider the action-based exploration approach for policy optimization, while the parameter-base one remains unexplored. For the sake of clarity, Table 3 shows a detailed comparison among our approach and the other presented methods exhibiting last-iterate global convergence guarantees.
Furthermore, Vaswani et al. (2022) have recently proposed a comeenioonddppnddee lower bound for the sample complexity of O (c-?), assuming to be under the Slater condition and considering single-constrained CMDPs with finite state and action spaces.
Coss-oonttr Reinforcement Learning. For safety-critical problems, it often insufficient to consider constraints solely expected costs utilities. Therefore, constraints sometimes applied to risk measures over cost or utility functions (Chow and Pavone, 2013; Borkar and Jain, 2014; Chow et al., 2017; Zhang al., 2024). The employed risk measures those most commonly applied in risk-averse RL (Tamar et al., 2014; Bisi et al., 2020, 2022: Luo et al., 2023). For instance, Tamar al. (2014) consider the Conditional Value Risk (CVaR,,, Rockafellar and Uryasev, 2000), while Bisi et al. (2022) consider a unified formulation embracing several risk measures, including Mean-Variance
the CVaR, and and the Mean- Variance (MV, Markowitz and Todd, 2000; Li and Ng. 2000). More details on risk measures are discussed in Appendix C. Among the works on Risk lisk-Constrained RL, the one by Chow et (2017) considers both CVaR, constraints and chance constraints over cost functions. In particular, the authors propose a trajectory- policy gradient algorithm and an actor-critic one, both primal-dual methods. For what concerns the CVaR, -conttrined problem, the authors incorporate into the constrained optimization problem the velluv variable associated with the CVaR... This leads three variables learn, requiring algorithms with three time-scales. Finally, the recent work by Zhang et al. (2024) considers an extension of the CPO algorithm (Achiam et al., 2017) imposing constraints over the Cf cost functions.
C On the Unified Risk Measure
In this section, we deepen the risk measures presented in our work, showing also how to select the functions f and g to obtain the desired risk measure. For what follows, we define Z as a finite-mean random variable that has Fz(.) as the cumulative distribution function. Formally:
Z < +00 and Fz(2) IPZZ < 2).
(14)
For what follows, let such random variable represent a loss.
17

---

C.1 Expected Cost and Mean- Variance
One of the most natural risk measures is represented directly by the expected cost on the trajectories induced by a (hyper)policy. This "risk neutral" risk measure was introduced in Section 2 for both the PG exploration paradigms as JAC.s and Jrc,i, where i is the cost function index.
However, in some scenarios, it may be desirable to minimize jointly the expected cost and its variance. To this end, is possible to consider the Mean-Variancs (MV, Markowitz and Todd, 2000; Li and Ng. 2000) risk measure which models this kind of objective. Indeed, the MV is a combination of the mean cost and its variance over the trajectories. The MV with parameter K the random variable Z, which represents a loss, is defined as follows:
MV (2)
IE [
Var [Z].
(15)
C.2 Chance Constraints, Value at Risk, and Conditional Value at Risk
Value at Risk (VaR.)) and Conditional Value at Risk (CVaR,,) are two popular and strongly connected risk measures. the following, we report their standard definition as provided by Rockafellar and Uryasev (2000) and Chow et al. (2017).
measurss risk as the maximum cost that might be incurred with respect to a given confidence level a E (0, 1). Such quantity models the potential loss and the probability that the loss will occur. In its classical definition, the VaR,, the worst-case loss associated with probability and a time horizon. This risk metric is particularly useful when there is well defined failure state. Formally:
VaR. Z) == min {=) (z) a).
(16)
measresss measures risk as the expected cost given that such cost is greater than or equal to VaR,. and provides number of theoretical and computational advantages. Such quantity represents the expected loss if the worst-case threshold is passed (i.e., beyond the VaR, breakpoint). Formally:
CVaR
min yeR
17
1
E [ - +1
(17)
1 a
Another risk measure, similar to the VaR, and the CVaR,,, is the chance one. Considering chance constraints means to consider constraints to hold with high probability. Indeed, constraints imposed on the probability that the loss random variable exceeds certain threshold n:
Chance,, (Z) IP(Z n).
(18)
C.3 Unified Risk Measure Mapping
Here we introduce objective for writing an optimization problem for different risk measures (Bisi et al., 2022). For every E [o, UI,, we introduce the functions ft IR2 - IR and gi R R order to express the unified risk-minimization objective function over risk measure on C. as:
min WeR
min 0Ee
E (-px(-10)
[A(C.(T), + 9x(m))
(19)
Thus, by fixing policy parameter configuration 0, obtain an AB unified risk measure over C; as follows:
A (0) :- min WeR
(f((C(()), n)] + +.()))
(20)
T=)px(10)
In order to switch to the PB exploration paradigm, need to consider also the expectation over the parameter configuration of the underlying policy. Indeed, by fixing a hyperparameter configuration p. we can define:
(p) = min meB
E
E P
[f((C.()).))
sm(m)).
(21)
O~up
By selecting the functions fa and gi we can consider distinct risk measures to minimize, as we show in Table 4.
18

---

The focus of this section is to derive the mapping between the functions f and and the desired risk measure as shown in Table In particular, we consider just the AB exploration scenario, since then passing to the PB one is straightforward. In this section, we consider generic cost function c : S 2 7'0(8,,, a. In what follows, with a little abuse of notation, we will write the risk measures with also dependence on the policy parameters which induce trajectories T.
[o, 1] with its cumulative cost index over a trajectory T which is C(T)
Mean Cost. This is the simplest case, indeed, we can express the minimization problem of the mean cost as:
min oc (-)A(-
E [C(TT].
(22)
Thus, suffices to select S(C(T): n) with the form of the unified cost minimization formulation.
C(T) and g(n)) to make the minimization problem fit
Conditional Value Risk.
For what concern the CVaRa. we can start from its formulation:
E (((())-n)]}} +]
min CVaR.
min dee
min nER
(23)
dee
1 T-PA(-10
1 (C(T) - .)) "/-B.
min yeeR
17 + min
E 0c p~1)
(24)
Thus, need to select f(C(T), the unified cost minimization objective.
1-a (C(T) -)) and g 17 to complete the mapping to
Mean Variance. For the (+) objective, we need to make some preliminary observations. In particular, for generic finite-mean random variable X, we have that:
Var [X] E [x]] - E [X]
(25)
Moreover, by Fenchel duality, we have the following:
E E
max B - -m²}. nEtR
(26)
Given that, we can start the derivation from the minimization of the Mean Variance:
min MV (C, A
(2
min
E (-pp(-10)
[C(T)}
E
[C(T)
E T-pal-10)
[CG)P
(28)
T-pa(-10)
min
E [C(T)]
E
[C(7)-]
max DEiR
21 (-pa(:10) [C(7)] -12
E
r²)
(29)
0=0
1>)))-10)
T-pa(100 10)
min
E (T-))-))0)
[C(T]]
+
E
[C(()
min MER
2n E
[C(T)] + +
(30)
050
p- 0)
Txpal-10)
min njR
RT)
min 0E
(1 (1-2xm)
2xm)
E
[C(T)
+ K
E
|C(
(31)
(-)
T-pa(-10)
Thus, to complete the mapping, we need to select
f(C(T),n)) = (1 2x7) --PA(-10)
[C(T)]
+
E T-pa(- 0)
[C(r)²]
and g(n) = =
Chance. For characterizing the chance constraints, we start by expressing the probability of an event the expected value of the indicator function:
P (A) = {AA].
(32)
Thus, having to minimize chance measure the cost with parameter n, we can rewrite it as:
min Chance,,(C
min E 0:0 T-px(-10)
[P(C(r) > n)]
(33)
060
min
E
[1 (C(r) > n|]
(34)
6E0 T-px(110
19

---

Thus, to complete the mapping to the unified cost minimization objective, it suffices to select f(C(T).n) = (C((r) i n) and g(n) = O.
D
Estimators
Here, provide all the explicit estimators' forms for both C-PGAE and C-PGPE and for each risk measure. For the sake of clarity, we report the mapping between the fa and go functions and the risk measures in Table 4.
AB CPOMDP-IL. Estimator
Risk Measure
Parameter
Need for
[:(C.(F).))
8x(r)
Expected Cost
x
C4(r)
0
Yes
Mean Variance
/
[1 2xn))((d) KC((r)²
Partial
CVaR,
a
/
- [C,(r) -n)
No
Chance
a
x
[Cz(r] 3 x].
0
No
Table 4: Mapping between Sú and and the cost measures.
The general Lagrangian function for the problem Equation (11) is the following:
(v,(),))))) m) JT,o(,, no) Σ Au (T.aal b,)) 2 |
(35)
For what follows we are going to compute the following gradients:
1. V n)):
2. (U, n))
3. V (v,
Before entering into the details of the estimators, we show the general forms the gradients of the Lagrangian.
General Gradient w.r.t v. Notice that the following holds:
Vo VoJT,(( Σ (o
(36)
u-1
thus, in what follows, for the gradient w.r.t. t we focus on the single terms Vo. (u) for every [0, U..
General Gradient w.r.f. X. The general gradient w.r.t. À has the form:
V X, = J (v, n) + w where J J+(u, m) (Jr, ()), .... JT. n)) and b (bI....,bt)
(37)
General Gradient w.r.t. As done for the gradient w.r.t. v, the following holds:
(o, V,,T,o( m0) Σ An M,,
(38)
Thus, also in this case, will focus on the single terms V T,, nu) for every [0,
D.1 Parameter-based Algorithm: C-PGPE
In the following we consider generic hyperpolicy "p and a generic parameterization p. Before starting with the derivations, we report the definition of (p.(
Je. n1) =
E
E T~PA(-10)
[(((C(()) + tg(())
(39)
8~up
20

---

for every ie U].
D.1.1 Gradients w.r.t. Parameters
The first step of the derivation can be done via the log-trick for the parameter-base exploration paradigm as stated by Sehnke al. (2010):
V pp. mR) V
p
E
R
[U((C((T),))]
(40)
P~MP
T-pA(-10)
E 0~vp
Pologuo(
E
(((C)(())
(41)
T-pa(-10)
To switch the sample-based versions of all the gradients, we consider the behavior of C-PGPE described in Section 4. In particular, we have the following:
Pp mi) =
V log up ( (())()()(()
(42)
N
Thus, to obtain the estimators for all the risk measures, it suffices map the selection of the fa functions in Equation (42).
D.1.2 Gradients w.r.t. Lagrangian Multipliers
Given the general gradient w.r.t. À of the regularized Lagrangian Ep the parameter- based scenario, the partial derivative w.r.t. X; is the following:
V.. (p, A, n) 0~uP (- (I(CC(T), m)) g((n)) - b, + w
(43)
This is defined for any i [U]]
In order to switch to the sample-based version of the partial derivative, we consider the behavior of C-PGPE described in Section 4. In particular, have the following:
N
V Er (p. n)
Σ f((C((T)) n.) 9:(m:) b, + wA.,
(44)
N
Thus, to obtain the estimator for all the risk measures, suffices to map the choices of fi and gi in Equation (44).
D.1.3 Gradients w.r.t Risk Parameters
For what concern the gradients w.r.t. 7,, have to enumerate the mappings shown in Table 4. Notice that, when the employed risk measure is the expected cost or the chance, the estimator of the gradient w.r.t. is not needed. Indeed, in the unified risk measure formulation such mappings do not depend on 77. As shown at the beginning of this section, we can just focus on the terms V Te,T, 1)). and in particular on the partial derivative V Vn, (p, my), that exhibits the common form:
Jr. m1)
V E Q~UP
E F T~PA (-10)
[f((C(T).m)]]
V (n.)(nn)
(45)
E
E T-pA(-
IV f(. mo)
vn...(m)
(46)
A~UP
Mean Variance. this case we have that fi(C((T), m) = (1 2mmm)) + K,C,(7) and that ((())) km.. Thus, from Equation (46), get the following:
V Fr.
E
E
[-2m;C((r]] + 2n;
(47)
8~MP
21

---

Considering the behavior of C-PGPE described in Section 4, we obtain the following sample-base version:
V In:Jps(pmm))
2 N
Σ Cd(Ts) + 28,7h
N
(48)
Conditional Value at Risk. In this case we have that fi(Ci(T), = 1-a; (C,(T) - -n) and that g:(n)) T/- As also shown by Chow et al. (2017), due the presence of the non-differentiable term (.)*, we need to resort to sub-differentiabbiity thcory. The following holds:
if (T) > ?
{ ge [0.1]
By (Ci(T) - m:)*
if ((()) NN elsewhere.
(49)
Thus, from Equation (46), we can write what follows:
By mp)
(50)
1
E
E T--p(-10)
Gn. (Ci(T) m +1
(51)
ai 0~Hip
1
E
Pa(TT1)) (C,(T)- n +m)+dr) dr
(52)
aj 0~up
1
E
p)( (C((T) m/) dr pa(T))) m:)d 1, (53)
Oi 0~Up
with y [0,
In particular, for q = we obtain the following partial derivative:
1
Tr..aa mk)
E
E (-PA(-10)
[1 (C((T) > ml] 1.
(54)
1 Oz 0~VP
Finally, according to the C-PGPE behavior described in Section we obtain the following sample- based version:
1 N Tp) = N
Σ 1(Ci(T)) > n² + 1.
(55)
With a little abuse notation, we will use & Jr. mk) = 2n Tp. m)) for the n update in the case in which the risk, measure is employed.
D.2 Action-based Algorithm: C-PGAE
In the following we consider generic policy mo and generic parameterization Before starting with the derivations, we report the definition of (0..
E
[fi(C((T) m)] + g(()),
(56)
--px(-10)
for every i [O.
D.2.1 Gradients w.r.t. Parameters
Also in this case, the first step of the derivation can be done via the log-trick, which provides an analogous result of the Policy Gradient Theorem (PGT, Sutton et al., 1999):
VoJA..(0, Ve
E
[((CC(T))m))
(57)
T-Pat-10)
=
E
Vo logpa(T (T)
(58)
T-pA(-10)
E
Vo log
(59)
T~Px(110)
t=0
22

---

To switch to the sample-based versions of all the gradients, we generally resort to the Monte Carlo version of VoJA,, n;), obtaining a REINFORCE-liK (Williams, 1992) estimator, that is:
1 (0.))) = N
Vo log (ar,,,: s.,,,) (((((())))))
(60)
Thus, to obtain the estimators for all the risk measures, it suffices to map the selection of the fi functions Equation (60).
It is worth noticing that some of the choices for fi and allow to switch to GPOMDP-lik (Baxter and Bartlett, 2001) estimator, which suffers from less variance. This holds for the expected cost and mean variance risk measures.
Expected Cost GPOMDP-ILK Estimator. In this case f((C.(T), = C,(T), thus we can obtain exactly the GPOMDP estimator:
VoJA, m.)
Σ
Σ 7 8r, (8), ary,))
Vo log ToggT(rr,a (arg, )rs1n)) (1
(61)
N
h-0
Mean Variance GPOMDP-LiK Estimator. In this case f((C((T),.)) (1 2x(m) k,C,(T),, thus we can obtain the GPOMDP estimator just for the (T( part:
+
V JA, (0,m)
(62)
N
Vo log π (ar,,,, (1,,)) ) ((1 2mmm) + +,,C((TT)))
(63)
N
1=1
1
2K
2' (rr,,, ary.))
Ve T(g 8r,
(64)
N
h=0
N
Ki
Vo log (a 8rgs))
Ci(Ty))
(65)
N
D.2.2 Gradients w.r.t. Lagrangian Multipliers
The result is the the one obtained for C-PGPE. The difference lies in the way in which trajectories are collected. The estimator for the partial derivative w.r.t. A is:
N Σ [(C.(TT))))) + (x)) + wA,.
ZA (,,
(66)
To obtain the estimator for all the risk measures, suffices to map the choices of and 9i as prescribed by Table 4.
D.2.3 Gradients w.r.t. Risk Parameters
As for the exploration-based case, also here we need to enumerate the mappings reported in Table 4. However, the expected cost and the chance risk measures do not depend on 77. thus they are not treated. As shown the beginning of the section, can just focus on the V, (0,7) terms and, in particular, we consider the partial derivative V V,, Tr. m.). For it, we can recover the common form:
V Vn, Tn.
E T-PA(-10)
IV (C, mb) + (n))).)
(67)
In this case we have that f((C m)) (1 (1- 2mam) + k,C.(T2 and that ge(n) k, Thus, from Equation (67), the following holds:
Mean Variance.
V qy Tn. (0, (0,m) = E
+ 2n;
(68)
--PA(-10)
23

---

Considering the behavior of C-PGAE described in Section 4, we obtain the following sample- based version:
N Ci(TT) + 2657)
V (n,
(69)
N
Conditional Value at Risk. In this case we have that fi(C((T),)) = (C,(T) (C,( n,) and that g:(n)) J)- Here face the same issues we have diseussed in the corresponding C-PGPE part. With the same procedure, we obtain the following partial derivative:
1 1- 04 (-0)(-10)
TA, nh)
E
(C(r)) & +1 +1
(70)
Finally, according to the C-PGAE behavior described in Section 4, we obtain the following sample- based version:
1 N N
8n Ts, mi) = Σ
( > ni +1.
(71)
1-1
Also in this case, we will use V n (p. = Ja. m.) for the n update in the case in which the ris measure is employed.
E Proofs
Lemma E.1 (Regularization Bias on Saddle Points 1). Under Assumption 3.1, for everyw e 0, let (v X be saddle point of Lw, it holds that:
0 E Lo(vō A - Lo(w
-
Proof. From the fact that (u. A is a saddle point of Lws we have for every w E V and Ae A:
Lulu, x > La x Lus (v
(72)
Colv, X 2
Lo(u
12 Co(u A)
w
||a|
(73)
2
w
(143122 - 1n12)
Colv, X > Lo (
Lo(u A) 2
(74)
From the fact that (2/² Xd) is saddle point of Lo. we have for every U V and dE A:
Lo A5) > Co up , Ap) > Lo( A).
(75)
By setting (v, - (v XD) in Equation (75) and () (vz XD) in Equation (74), we obtain:
Colu Xt) > Lo(ug: X3) Co X
(76)
= Lu x > Cu(v.t x*) > Lo(w X8) + 2 (12512 -
11511)
(77)
(14812- 14)1)).
> Lo(ug. (3) + 2
(78)
thus:
Coluū, Ao) > Lo(u x²) > Lo(ug. 25) + 2/2 (12311 - -
(79)
Lemma E.2 (Regularization Bias on Saddle Points 2). Under Assumption 3.1, for every w > 0, it holds that:
min max Colu, A) min max (U, A) < b 1118112
wev AEA
weV AEA
Proof. The first inequality follows from the observation that Lo(u, A) > Lw(v, A) for every w > O.
For the second inequality, let us denote as (v Ax) the saddle point for Eu and let A# = (2, )$).
We have:
Lo A3) Lu( X
min max Co(U,
min max (w, A) UEV AEA
(80)
WEV A
24

---

max
max Cu( 2)
max (U,
(81)
WEV
DEA*
AE
max VEV.
(Lo(U,)) -)
(82)
W
max
| :2: [
(83)
2
W
2:
(84)
2
where we used Lemma E. to conclude that |
Lemma E.3 (Objective bound and Constraint violation). Under Assumption 3.1, for every w ee 0,
letting (v X be a saddle point of Lw, it holds that:
0 = Jo( Jo(w swIl 1
(85)
[( - b)+11
(86)
Proof. Since (v) AD) is saddle point of Co. it holds that Un is feasible and, consequently,
Co Xa) = (o() Moreover, let w > 0: since (u )²) is a saddle point of L it holds
that x = (²()t) = II (+(J(v - b)) = +(J(v²) - b) since =I([(vt) b <
w Jmxx. Thus, we have:
Lu( x = Jo(v + J( b) = Jo( + -b)
-
(87)
From Lemma E.I, we have:
0 x Jo(uz) - Jo( - [|[ - b) & マ 1251
[(J( - -b) (88)
2
2w
By summing [ - b1 to all members, we have:
[[](c b) $13 & Jo( Jo(wz)
b)
2 11:1
- b) -
(89)
2w
Now taking the first and last member, conclude:
[[ b)
xi 3.
(90)
Since y [I(((z)) - b) +12 z 0 and plugging the latter inequality into the third member of (89) we obtain:
0 m Jo(vz) - Jo( & w1
(91)
Lemma E.4 (Weak --Grrdient Domination on HV)). Under Assumption 3.2, if for every v E V and XE A, it holds that:
(.H an (H)(v) - min Ho((')) -B2
(92)
w'eV
Proof. If w > O, the dual variable exist finite since the maximization problem over À is concave:
X (v) = arg max C. (v, A).
AeA
and by Assumption 3.2 we Thus, we have from Lemma E.7 that (v) V v. (((0,,))22-- {)12)>>(0) have the following:
HuHHll = VoLu A) A)1x~>*(11l1
(93)
> a1 (c.(v,>(v))
min Cu ('o)))())))) - B1
(94)
v'eN
> 0n HH(()) - min max Las (v', 21) - 31 w'eV AEλ
(95)
= on (H) - H - Bi.
(96)
Lemma E.5. Let > 0 and U E V. The following statements hold:
25

---

- is w-smooth, i.e., for every X, X'E A it holds that:
V X) V A) ||| x11
- satisfies the PL condition, i.e., for every XE A it holds that:
(U,
max (u, X) - (1,(1,))) X
(v,, satisfies the error bound (EB) condition, iee, for every X, NE A it holds that:
[V, W [10(v)) A/2
where (v) arg maxAeA Cw (v,
( satisfies the quadratic growth (QG) condition, for every X, Ne A it holds that: Ha(u) - (u, 2) 2
w
X* (x A/2.
4
where X (v) = arg maxAea (V,
Proof. For the first property, it is enough to observe that Lu is twice differentiable in À and that its Hessian is wI. For the second property, we observe that L quadratic in À and, consequently satisfies the PL condition with parameter wt
max (u, Lu( > w max Lw X) - Lu( -cu((:)))
VV 2) > w
WERR
A'EA
For the third and fourth properties, we refer to Lemma A.I of Yang et al. (2020).
Lemma E.6. Let > O. For every v V, it holds that:
(v) H > (x) x
(97)
Proof. Let consider the following derivation: (w) - H*
H (v) - Lu Ax)
(98)
(v) - Lu, A
(99)
(0)) 2812.
(100)
having exploited the fact that, from the saddle point property, Lu (u++ xt) & Lu (v,, x and, then, Lemma E.5.
Lemma E.7. Let O. The following statements hold: Hy is LH-smooth, i.e., for every v, v' E V, it holds that:
V.. & Lu|w' - w/12-
L2 w
where LH = L2 +
For every v V we have VoHo(D) VoLu(U, 2) where (*(v)
arg maxxes Lu (v, A).
Proof. The first and second statements follow from Lemma A.5 of Nouiehed et al. (2019).
L
Theorem 3.1 (Objective Function Gap and Constraint Violation). Let > 0. Under Assumption 3.1, P& & e, it holds that:
E[J((ua) Ju(u & c 1881
B[(J(vx) b,) 4c w A Vie [U]. (8)
Proof. Since PA & e, it follows that as and, consequently, 0 & E (H H31 < e. We start by bounding the norm of the dual variables:
X x (vx)ll2 & | + (x*(v)) 21
(101)
26

---

| + 4 (H.( H
(102)
where we applied the triangular inequality and Lemma E.6. The projection II is such that X* = TI (J - b)) = (J(v) b)+ and, consequently, we have:
(() - b)+1l 1l2 - (J(( b < (vH) - H
(103)
By the last inequality, together with Lemma E.3, having applied the expectation both sides:
[()()(v)) - [Ia] & [[ - b) *112 + 4 ( HW]
(104)
3 X 2 + 4c.
(105)
Recalling that:
([)() b [B,)) - b) > [[( - bl
(106)
For the objective function bound, us consider the following derivation. By definition of (w))
and X* (v) we have:
Jo(UK) - Jo( = (vx) - - 2
(1)* 12
(107)
Taking the expectation on both sides and upper bounding
| with ! from Lemma E.1:
E[Jo(U)) Jo(wD) E E(H)((x)) Hwl B
X (vx)1 |
(108)
< B (w)) Hw]
+ |
(109)
<ct 2 A
(110)
The result is obtained by applying Lemma E.3 follows: [(Jo(vn)) Jo(+))) [[)o(v))) Jo(w Jo(u - Jo(ez)
(111)
50
Theorem 3.2 (Convergence of Pk). Under Assumptions 3.2, 3.3, 3.4, for X <. 1/5, sufficiently small
and and choice of constant learning rates Cus S2. have Px(x) + /1/a whenever:
K Olw log(e-1) )) if u 2 and the gradients
exact (i.e., Vú V/2 0);
K -1--1e-5
ip (1,2) and the gradients are exact (i.e., V, Vx 0);
K = O(w 3 $ +1 if +b [1,2] and the gradients are estimated (i.e., V, = O(w and
VA = O(1)).
Proof. The proof is subdivided into several parts. We will omit the w subscript for notational easiness. Let us focus on a specific iteration k E N.
Part I: bounding the as term. Let us start with the a term:
(V H (wk))) H (1i+1 Uk VoHu(v))) + Lu | - vull (112)
< (Uk) - H - -Cui (VoLu Aa), VoHH(vu))
(113)
Lu S2.x (o 1
(114)
where the first line is due to the fact that the function H. is L (Lemma E.7), the last incquality due to the update rule of v. Now, we apply the expected value on both sides of the incquality and use the fact that the gradient estimation is unbiased and has variance bounded by V.:
E (v H H (UR) - H - -ou (V V..Cu Ac), V.HH((e)))
(115)
Lu 22 [| 2x) F
(116)
2
$In the context of this statement, the O(.) notation preserves dependences and only.
27

---

where Fk-1 is the filtration associated with all events realized to interaction k - 1. We recall that:
Volu(ues Ax) [rx-1 = Var Lu F + IV A Ab)
(117)
and that Var VoLu 2v) = Ve by Assumption 3.4. Thus, selecting Su,k & 1/LH, we have that:
E ()) -
H*
(118)
(u)) - HHth Su. (V V. (Uk, Ab) VoHu(vN))
(119)
Su,k (Vk. dx)l( 2
LH
Lo
(120)
2
2
(uk) H Lu.k (V (Uk )k) VoHn(va))
(121)
So.k VV (uk: x = V V. (ux)l
Lu
So Vo.
(122)
2
Consider that:
Su.k
V Vo An) V (v)) + (.Hl
(123)
2
Su.k (V), (.
Su.k | H.
(124)
Su.k ( (VoLu(uk An), VoHH(
(125)
Thus, the following holds:
E ( H*
(126)
Hu (U)) - -1- Gu. -uii (V AE), v.Hl((u)) Lu Vo
(127)
Su.k Vu.u AE) V.HL(ww)) Su.k (wx))
(128)
Soo V. Au); (oll((U))
(129)
Soik 2
Sonk Volu An) - V.Hl((v))1
(uu) - 1
(..HH 122
(130)
2
LH Lu. Vo.
(131)
2
Thus, we have obtained:
2 = ((+ H
(132)
< (w)(v)) 11--500 Suik (o.ll
Susk
Vulu(un, An) Voll((v))
(133)
Lu So.Vo. Vo,
(134)
holding via the selection of Su,k & 1/LH. Notice that, from A the following directly follows:
D = E3 [H - H (v))
(135)
Sa.k (wN)) Su.k (Uk, As) V.Hl
Tu 22 Vu.
(136)
2
Part II: bounding the by term. We are ready to analyze the by term. Recall that for ridge regularization of the Lagrangian function presented in the main paper, we have that C. is w-smooth and fulfills the PL condition with constant w, as shown in Lemma E.5. Since L is a quadratic function of X and (*(U++1) E A, we have that considering the non non-projected d&+1 can only increase the distance. Thus, we will ignore projection for the rest of the proof. We have:
Ho(wx+1) - (Wk+1, det1)
(137)
(Hu(U)+1) Cu(Uu=1, AR) - (AE+1 Au: VACu(URHL As)) 2 || AR112
(138)
=Ho(V (oLKNI Aa) - CA.E (VAL Ae), (UE+1,)
(139)
28

---

+ CR Frais/$aCuu. ( 2
(140)
that is possible under Assumption 3.3 (i.e., Lu is L22-mmothh and due to the update rules we are considering. Now, by applying the expectation on both sides, we obtain the following:
E (( - Lu (UR+1, Au+ F[-1]
(141)
$ B (HH(( Lul Fk-i] SA. V VXLu
(142)
| )x)) 12 [
+ & TB
(143)
$ E H (Ux+1) (uk+1 AK) FR-1] SA.k VXCu 2b)1 2
(144)
2
(U 2) 2
+ 2 &
(145)
< B [H -
Fk-1
CA.A V (
w
2 22 Vx.
(146)
2
where the last line follows by selecting SA.A < 1/W. Since Lw enjoys the PL condition w.r. À with constant w, for every pair (u, A) we have:
[V b w
max Cu X) Lu(v,))) 3 max (u, - -Cu(ee)))) (147) AERU
A=A
By applying the PI. condition:
E ((H+( (u
(148)
< H[HH(UU+H - (UK-HII Fx-1]
SA.i
V VXLa(Uk+ie Am011 w
(149)
2
=2"
SA.
< E (UHH() - (U6+1, A (U)641110)1Fa--11
w E (vx+1) (ub+1,
(150)
2
w R2 V/
(151)
2
SA 2
EE E[HH(UR++) - L.(EEII:
(152)
where we enforce Saytt w 2 i.i.c. SA & 2/w. However, we do not have proper recursive term, thus consider the following:
(uk+1)1) - (Uk+1, Ab) Hw(ww) (vk, )x)
(uk, Ax) Lu (UE+1, As)
(153)
Recursive Term
+ (=((k41) 1) H (Ux)
(154)
A bound on D has already been derived, so let us bound the term O
C. An) - Cu(UU- An) & (U8+1 Ukk Ve Au)) + La
2 1k- Uull2
(155)
< Go.k (v. (un, AR), (Vs, An) + 2 Se.k V, (uk, )k),)s))) >e)
La
(156)
again because of Assumption 3.3 and the update rule. Now, as usual, consider the expectation conditioned to the filtration Fx-1 and the properties of the variance, to obtain:
C : Le Aa) E. [L (e)+1,
(157)
La 1/2 Gu.k) VV Ax)1
L c2 Vo:
bu 1
(158)
having set bu.k & 1/L2. We are finally able to conclude the bound of the term B:
B = E. [HH - (. FF-1)
(159)
1 SA.K w) I. [H (Vk+:: Fc) (.)
2 2
(160)
2
29

---

CA.k
2 w
(HW( - Coki A6l)
(161)
San
1
2 w
(Lu(Uk) Ab) B[Cu FR-1I
(162)
+ 1 SA,k
2 w
(E[Hu
H + 22R.
(163)
Now we apply the bounds on 9 and D (the latter is from Eq. 136), obtaining: EE Hw (U&+1) f (R+1))
(164)
SA.R w (HUW(UK) Lu As))
(165)
(1 Sa. w)
(nmu (1+ L2 (2( ) Vulu Aw)1 2/2 Heaaki V.)
L2 22
(166)
SA. w
Su.k (V + Susk (olu((u) -vottu
(167)
2
LB 22 Vo
R2.V3. Vx:
(168)
2
that is the second fundamental term.
Part III: bounding the potential function (x)x). Before going on, recall that far enforced:
So.k & 1/LH (since LH 7 L2) and Cx.: & 1/w, for every t e [A]. What we want to bound here is the potential function PA+ (x) ax+1 + xbx+1. Using the final results of Part I and Part II:
ak++ + xdk+1 = E (vx-) H + E H (wx+1) - L Ak+1)]
(169)
Su.k E
E [HH (v6) H+1
V H.e (wx)) [1))
(170)
2
+
Sunk
An) V Volla [2|
+
Lu 22 So Vv
(171)
2
2
+X
Sa.l w)
B(HH((N))) - La Ax²1
(172)
2
+X
SA. ww)
(Sos (+
L2 L2
2
B[IVoouu Ax)1
E
+ -
L2 2
Vo
(173)
2
2
SA. w))
(-52
Su.k E [Vott(((1))
+X
w)
(174)
2
2
So.k E.
Lu 2 Vo
+
V (Wke Ao) - V. (1x))
+
(175)
2
2
+X
W
R V2
(176)
2
SA.
ak + X
2 w
by:
(177)
Su.k
+ X
1
Sa.t w
V (u
(178)
2
2
Su.k
Sa.t
+ x
1
1
2 w
Vo (Us, As) (1)
(179)
2
1+ L2
Shudew) E VVVoLulu 2w)leد
+ +Go.k
2 Gouk
x 1 -
2
(180)
2 Su.k
(aelww (LH + L2) Vo + Vx.
LH + x
(1-
(181)
2
30

---

Now we can re- ee-arrange the terms by noticing that:
(u Ac)l
(w )a) (v.H((Us) + V (v=H2
(182)
V (uk )a) (.HH(
(183)
+ Vo v l1 + 2 VV. )o) - vollw(ex), (oll((w))
(184)
V A²) (. 2 (
(185)
where the last inequality holds by Young's inequality. Then we can write what follows:
1 1 xbs+1
(186)
(1
1 Sa.t w be
a& + x
(187)
L2 So,k)
CA.t
1 2
x 1
(188)
2
Su
1+ x (1 1 Sa.l
(ww) ))) E
Hu H..H((())))
(189)
1 L2 took
x 1 SA.t w) + Su.k
1 x (1 SA. w ))
2
(190)
E V Wo (0k: (x))
(191)
So.k
LH (H +X x (1- skaveww (LH + (2) Vo + 2
-
+ 2
(192)
2
Let now proceed to bound VV Ax) - (vH)l By Lemma E.7, we have that (D) VoLu for every X (²) arg TeA few (u, (), thus write:
IV Ax) (. VV (Un. Ax) - vora (+w)))
(193)
L3 A (UL) Aml12.
(194)
since Assumption 3.3 holds.
For fixed value of v. by Lemma E.5 it follows that (w, .) satisfies the quadratic growth condition (since it satisfies the PL condition), for which the following holds:
[VA() - Aul 2
(Hw(wu)) - Cu(
(195)
and thus we have:
4L2 (Hu( -
(oke Ax) - V.HH 12 <
(196)
By applying the total expectation, it trivially follows:
4L2
4L3
E
Ve AR) - V V.HH( < (UH)(U)) - (.(2x,A))) bb.
(197)
Thus, we have:
ak+1 + Xhe+1
(198)
SA. 2 w
ak + x
1
by
(199)
1 L2
Sa.k
+
26m.
2 Sonk
x 1-
(200)
2
Su.k
1 x
1
Sa.i
2 w
()) IR.
H. 11.
(201)
+
25o
1
Lg
Sock
x (1 (1-
S2 SAmlww ()
Su.
1 11 x
1- (1-5an SA.k
2 w
4L2 bb (202)
2
31

---

+ bouk 2
x - 22 V2. Saeww (1- (Ln + L2) Vo
Ln + [
(203)
2
2
Part IV: apply the vi-gradient domination. Now need to bound the term VWH (vx)ll We consider Assumption 3.2 and we get: (/V.Hl i a1 (Hw H*) - 31. By defining f = H + 81/0n, we also have:
[v)lL( e max fo, Hw( -1
(204)
(v) 2 max fo. Hb(v) - ]
If we apply the total expectation on both sides of the inequality, we get:
E |.HLL
ai E max {0, H2( - }
(205)
E max f0, H Hw) f1* ]
(206)
max (o. (v) M
(207)
which is achieved by a double application of Jensen's inequality, since 2/1 is convex for &i E [1,2]
and O, and the maximum is convex. Let start from Equation (198):
a++1 + Xbs+11
(208)
< ox + x (1 (1-2))
(((WWW) bx
SA.i
(209)
2
+ 26,rk (1+ L So.
(1 (1-
Sa.k
Su.k
SA.k
w
1 ++X X
2 w
(210)
2
2
2
=
(211)
26o.k (I+
Ls
2 Soul
(1-
Sank (
Cu.k
1 x (1-
Sa. w
1)
4L2
bb
(212)
2
2
2
LH X (1- S2.k w
(I+H + T22)
Vo X2 R2 V2.
(213)
2
2
=V
We first enforce the negativity of -C. To this end:
La
Sx.i
Su (
1 + x x(1 {11
(1- Sa.i w ))
=
26
1+
Su.k
x 1
2 w)
(214)
2
2
x3/2
Sx,6 w
1
Cx. w )))
E So.k
3x
1
x 1-
(215)
2
2
Su,k
Sa.6
Su.k
<
5x
1
w
-1
(5x 1)
(216)
2
2
21
Thus, it is enough to enforce 5x - 1 < inequalities:
=
& 1/5. We now plug in the gradient domination
0k+1 x
(217)
32

---

11 Sa.t
2 w by - Cuf c max fo: E Hw( - -mr+]] a/2
$ Ox + x
+ +
(218)
1/2
2 Seck) x (1
S2.6 w
Sm.
1+ x [ -
w
4 bb.
+ k 1+
+
(219)
2
2
2
Now we introduce the symbol Tx
:m E
Hw - F/
= akk - B1/01, to get:
Tx+I 1 + Xbx+1
(220)
< ã - Ca. max (0, axk : V
(221)
(x
Sait
w
+
11
L2 Suik
x (1-
Ca,k
(222)
2
2
2
+
Son.k
1+ x
(1-
S2i1
w
4L3
bk.
(223)
2
2
For what follows, we call B the term that multiplying by:
( - Sa.k
L2
Sa.1
B x
2 ())
25u
1
Su,k
x
1
w
(224)
2
2
+ Su.k
1 [+ x (1
(1-S2
SA.k w
4L3
(225)
w
Let refer to ā. + xha as Pr(x) with x E (0, 1). For the sake of clarity, we re-write our main inequality as:
Pa(x) = ux+1 xb++1 & ãz Bb C max (0; āz} 2 + V.
(226)
Then, from Lemma F.I having set a - ãة and b - Xh,, we have:
Px+1(x) äp+1 xd++1 & ã BbN- C(xba) 3 - 2 3 C'ax {0, āz xbx c V. (227) By choosing X so that Xbx & 1, i... X < 1/ [a bb- we have:
Pi+1(x)= = äx-1 + xb++1 & ã + Bb + C(xbx) - - 2 C max (0, āk + xba} + V (228)
< क (B + XC),, -'- C max 10, ăz + xbx _ + +V
(229)
= P + xC) - -2'- 3 max (0. P(00)) + +V..
(230)
To unfold the recursion, we need to ensure that B + xC & X. which leads to a condition relating the two learning rates:
B + XC
(231)
SA. ))+
(1
Le
SA.K
= 1
+ 260,
Su,
1
2 w
(232)
2
2
$3/2
Sock
Sa.b
4L3
1 x
1
(233)
2
2
11 (1+ L2
Cx
Su.k
SA.
3
+ x
- 2Gu
Su.k)
X 1
w
+
1+ X
1
w
aj
(234)
2
2
2
2
80
< X X Cx
2122
1 +
X 2
3
w + -o
(1 7x)
+
ag
<x
(235)
2
w
33

---

w²
= So, E (1 x)way 4Tg((1 7x)
(236)
where we exploited Su & 1/L2 and Ga.1 < 2/w. Thus, we have:
max fo. pa(o0) a + V.
Px) & pa(x) - 2-- - max
(237)
Collecting all conditions on the learning rates, we have:
1
w² x²AAx
So, & min
(238)
LH L2 (1 + x)aa + +4L3(1 + +7x)
1 2
Sa. & min
(239)
As further simplification, let us observe that:
c=
-2uu,
1
L2 Su,k
x
Sa.k
w
+
So.k
(
1 x(
x(1
x11
(1-
Sa.i w))
))
ai
(240)
2
2
2
2
x3/2
Su.k
SA.K w
$24 2
Su.aor
1+5 5
1
x)
ai
(241)
2
2
2
V
S0.k
LH + X
(1-S2
Vo + x R. (LH + L2)
(242)
2
b0,k
(1 x) ( V, x V. (1+
(243)
Denoting with Ō=
=: 21- Suna we are going to study the recurrence:
Pat1 & (x()) Ò max f0, Fa(o)* & + V.
(244)
Part V: Rates Computation
Exact gradients We consider the case V Let us start with de 2. From Lemma G.3, we have:
Part V(a):
Pk(()= & (1-2)= K Po(E) E
(245)
log Po(e)
Po(e)
2log (o(
K
8-1 log
(246)
log I-Ō
2 Sp
The inequality on K holds under the conditions:
21+ 3
2
C &
Su &
(247)
po(o)
Va Po(x) $
1
1
w²xSx.
Su, min
(248)
T. Ta
3 (1 + ww + 4T + 7x)
w²
min
(249)
La L
3
(1 + x)wa + 4L3(1 + 7x)
1
Sa.6 & w
(250)
34

---

where the first one derives from the hypothesis of Lemma G.3 and the other two from the conditions on the learning rates derived in the previous parts. We set:
SA.k = =w --
2
WX
Su.k = min
=ww).
Po(x) 8 L2 Li
va
(1+ x)a 1 + 413 + 7x)
Thus, the sample complexity becomes K O (w log! log t)
Consider now &i E [1, We have from Lemma G.3:
2 (22
px(x) &
-
ČK
E
(251)
15
K
Ö-
+++
2
(252)
v
(2- )
a
holding under the same conditions as before. With the same choices of learning rates, we obtain the sample complexity K
O
(w - sample complexity.
Part V(b): Estimated gradients We consider V > In this case, from Lemma G.5, we have:
pk(x) & (1- (1- V K Po(x)
V
?
(253)
We enforce both terms to be smaller equal e/2. With the first one, we can evaluate the sample complexity:
(1 - 81
Polx)
(254)
2Px(x)
log
x K
(255)
p - C2
log 2/x(x)
(256)
Vo V.+ x2 1-
(1+ 22) + (1+ x) Li
2 2 Sukaa
Regarding the second one, have:
C 2
(1+ + (1 x) 17
V. + x X2
V
(257)
2
2 sa
By enforcing the relation between the two learning rates, we set = (( By enforeing the previous inequality, recalling that Ta & O(w-1) and V, O(w we obtain CA (wwe2
from which G. ((v)) Substituting these values into the sample complexity upper bound, get (highlighting the terms possibly depending on w):
log !
K
(258)
+ w w(2) 1-1 1//2 2//
log
0
(259)
(L2 + w -----11l 1VVo +
log w
0
(260)
having bounded the sum at the denominator with the second addendum.
35

---

Technical Lemmas
Lemma E1. Let a a R, b > O, and 1o E [1,2]. It holds that:
max a} & 2'- - max b) -63.
(261)
Proof. Let us consider the following derivation:
max a}
a
a > 0 otherwise
(262)
0
2 (a b)
-b if 0
(263)
0
otherwise
2' (a + b)
i 0 -0
if - - < a 0
(264)
otherwise
21 (a b) -
if 0
2 (a b) - if -b< -b
(265)
otherwise
2 2' (a
if b> otherwise
(266)
2 m a b) b
(267)
(268)
where the first inequality follows from (ar + v) $ < 2 (x 2 + y
for x, > 0, from Holder's
inequality; the second inequality from observing that 2 $ (a + b)
E (21- -1)
< 0 for
-b 0.
G Recurrences
In this section, we provide auxiliary results about convergence rate of a certain class of recurrences that will be employed for the convergence analysis of the proposed algorithms. Specifically, we study the recurrence:
Tk+1 & T rx)
+
(269)
for a > 0, b. 0, and o e [1,2]. To this end, we consider the helper sequence:
Pu = Tu
(270)
Pk+1 = Ph max(0, pk]* + b
The line of the proof follows that of Montenegro et al. (2024). Let us start showing that for sufficiently small the sequence Pk upper bounds Tk.
Lemma G.I. I - for every ls z 0, then, rk for every k > 0.
Proof. By induction on For the statement holds since Po ro- Suppose the statement holds for every j & k. we prove that it holds for l: + 1:
Ph+1 = a max (0, ) + b
(271)
> a m0 r +
(272)
Tk+1,
(273)
where the first inequality holds by the inductive hypothesis and by observing that the function
f(z) = x - max(0, 2 is non-decreasing in a when a & dr. II. Indeed, x < 0, then f(x) = x,
which is non-decreasing; if x > 0, have f(x) axd that can be proved to be non-decreasing
36

---

in the interval 0. (aΦ) 3-1 simply by studying the sign of the derivative. Thus, we enforce the following requirement to ensure that Ps: falls in the non-decreasing region:
Pk $ (ao)
(274)
PP
So does r3 by the inductive hypothesis.
Thus, from now on, we study the properties the sequence Pk. Let us note that, if Pi is convergent, then it converges to the exed-point p computed as follows:
p = p- - a (0, p. - p b
(275)
having retained the positive solution of the equation only, since the negative maximum max(0, p}. Let us now study the monotonicity properties of the sequence pk-
attains the
Lemma G.2. The following statements hold:
rf p and &
ar s-I, then for every l > 0 holds that: p & pk+1 Pk-
. If < p and a & o then for every k > 0 it holds that: p 2 Pk+1 Pk-
Proof. The proof is analogous to that of (Montenegro et al., 2024, Lemma F.3).
From now on, we focus on the case which ro > P, since, as we shall see later, the opposite case irrelevant for the convergence guarantees. We now consider two cases: b = 0 and b >> 0.
G.1 Analysis when b 0
From the policy optimization perspective, this case corresponds to the one which the gradients are exact (no variance). Recall that here p 0. We have the following convergence result.
Lemma G.3. Ifa & ord ro > 0, and b = 0 it holds that:
(1
i =
Pk-1 &
min ro, ((Ø - 1)a(k 1)) -))
i (1,2)
(276)
Proof. Since ro 2 0 = P. from Lemma G.2, we know that Pk 2 0 and, thus, max (0, pk] = Pk. For
1, have:
Pk+1
apk = (1 - a)pk (1 k+1 po = (1 kt
(277)
For (1,2), have:
Pk+1 Pk: app.
(278)
4-1 & We proceed by induction. For k = 0. the statement hold since Po ro and & (øa)
(( - 1)a) - from the condition on the learning rate. Suppose the thesis holds for j k, we prove it for + 1. ph+1 ro by monotonicity. and, from the inductive hypothesis:
Pk+1
Pk app & (oak) + al a(coak)) -
(279)
= (oak) + (da(k + 1))= otr - a(oak) - +(da + -- (280)
(+)
We now prove that (+) is non-positive:
(( 1)ak) -Fr ((Φ 1)a(k k: + 11)= -a(( - 1)ak) - #-
(281)
= ((o 1)a) - k -
k - (k + 1)
o-1
((0 1)k) -
(282)
b: +
% 4-1
37

---

(
<a aa p 1) p-1
E 0,
(283)
6-1
Φ - 1
having observed that:
1
sup k=1
k (k + 1)
lim 40+
h: (k + 1)
(284)
k+1
k+1
Ø 1
G.2
Analysis for b >>>
From the policy optimization perspective, this corresponds to the case in which the gradients are estimated, i.e., the variance is positive. this case, we proceed considering the helper sequence:
f10 = Po
(285)
+ = (1 - 1) 1/K +
if k: > 0
We show that the sequence m/ upper bounds Pk: when po To 2 p. Lemma G.4. ro > P aad a & or then, for every k > 0, it holds that The e pk-
Proof. The proof is analogous to that of (Montenegro et al., 2024, Lemma F:4).
Thus, we can provide the convergence guarantee.
Lemma G.5. Ifa & org -T. ro e 0, and b > 0 holds that:
M (1 (1-b'-ba +
(286)
Proof. By unrolling the recursion:
Mk- (1-ap
176 + b
(287)
(1 - (1-apt
k+1
ro
+
Σ
(1
1-ap 135
(288)
j-0
+x
< (1 ap
| k+1
ro
+
Σ
ap
(289)
j-0
k+1
b
b²
a
(290)
ap
1/4
h+1
bz $ #
(291)
H Experimental Details and Additional Results
H.1 Experimental Details
H.1.1 Employed Policies and Hyperpolicies
Linear Gaussian Policy. A linear parametric gaussian policy No : S A + A(AA) with variance
x² samples the actions as 0t ~ NNO 8t, Tt,a) where 8; is the observed state at time and 0 the parameter vector.
38

---

Tabular Softmax Policy. A tabular softmax policy Te S A - A(A) with a temperature constant such that:
exp
mo(a))8:))
(292)
Σ
0..E
exp
where fig is the parameter associated with the i-th state and the j-th action. Notice that the total number parameters for this kind of policy is |S|[A]]
Linear Deterministic Policy. A linear parametric deterministic policy μr S x A - A samples the actions a o0 St, where is the observed state at time t and is the parameter vector.
Gaussian Hyperpolicy.
parametric gaussian hyperpolicy "p R A()) with variance o² samples the parameters 9 for the underlying generic parametric policy Te 0₂ oZ where p is the parameter vector for the hyperpolicy.
H.1.2 Environments
Discrete Grid World with Walls. Discrete Grid World with Walls (DGWW) is simple discrete environment we employed to compare C-PGAE against the sample-based versions NPG-PD (Ding et al., 2020, Appendix H) and RPG-PD (Ding et al., 2024, Appendix C.9). DGWW is grid-like bidimensional environment in which an agent can assume only integer coordinate positions and in which agent play four actions stating whether to go up, right, left, down. The goal is to reach the center the grid performing the minimum amount of steps, begin the initial state uniformly sampled among the four vertices of the grid. The agent is rewarded negatively and proportionally to its distance from the center, where the reward is O. Around the goal state there is a "U-shaped" obstacle with opening the top side. In particular, when the agent lands in state in which the wall is present, it receives a cost of 1, otherwise the cost signal is always equal to 0. our experiments, we employed DGWW environment of such kind, with |S| 49, i.e., with each dimension with length equal to 7.
Linear Quadratic Regulator with Costs. The Linear Quadratic Regulator (LQR, Anderson and Moore, 2007) a continuous environment we employed in the regularization sensitivity study of C-PGAE and C-PGPE, and in the comparison among the same algorithms against the sample-based version of NPG-PD2 (Ding et al., 2022, Algorithm 1) and its ridge-regularized version RPG-PD2 (not provided by the authors, but designed by us). LQR is dynamical system governed by the following state evolution:
St+1 Ast + Bai
(293)
where A e Rdsxdd xds and B e Rda
In the standard version of the environment, the reward is computed at each step as:
Ft -s
s Rs; a. Qa:
(294)
where Rddx and Q E RdaadA,
We modified this version of the LQR environment introducing costs. In particular, in our CosILQR the state evolution is treated in the original case, while the reward step / is computed
Ti s Rst.
(295)
where R Rds Moreover, we added cost signal which is computed follows at every time step l:
c = a Qa.
(296)
where Q RRdaxdA
In our experiments, we consider CostLQQR environment whose main characteristics are reported in Table Additionally, we considered uniform initial state distribution in [-3,3] 3] and the following matrices:
1
0
0.9
0
0.1
0
= = = 0.9
0 1
Q
=
0.1
R
0
0.9
(297)
39

---

Environment
State Dimension ds
Action Dimension d
Action Range (Amin: Paaxx]
State Range (Suins Smax)
CostLQR
2
2
(-00, +00)
20, +00)
Swimmer-v4
8
2
[-1,1]
(-00, +-00
Hopper-v4
11
[-1,1]
(-00, +-0)
Table 5: Main features of CostI.QR, Swimmer-v4, and Hopper-v4.
MuJoCo with Costs. For our experiments on risk minimization, we utilized environments from the MuJoCo control suite (Todorov et al., 2012), which offers a variety of continuous control environments. To tailor these environments to our specific requirements. we introduced a cost function that represents the energy associated with the control actions. In standard MuJoCo environments, a portion of the reward is typically calculated as the cost of the control action, which is proportional to the deviation of the chosen action from predefined action bounds. In our MuJoCo modification, at each time step we make the environment return a cost computed as:
(298) where amin and amax are respectively the bounds for the minimum and maximum value for each component of the action vector. Then, the action min {max (at, Omin) 0mmax is passed to the environment. In our experiment we consider Swimmer-v4 and Hopper-v4 MuloCo environments, whose main features are summarized in 5.
aa min mmxx (az, Amin) 0max 1l2
H.2 Details for the comparison against the baselines in DGWW
In Section 5. we compare our proposal C-PGAE against the sample-based versions of NPG-PD (Ding et al., 2020, Appendix H) and RPG-PD (Ding et al., 2024, Appendix C9). The environment in which the methods are tested the Discrete Grid World with Walls (DGWW, see Appendix H) with a horizon of T 100. In this experiment, the methods aim at learning the parameters of tabular softmax policy with 196 parameters, maximizing the trajectory reward while considering a single constraint the average trajectory cost, for which we set threshold b 0.2. All the methods were run for = 3000 iterations with a batch size of N = 10 trajectories per iteration, and with constant learning rates. In particular, for both C-PGAE and NPG-PD,
employed Ço 0.01 and SA 0.1, while for RPG-PD we selected So- = 0.01 and CA = 0.01. For C-PGAE and RPG-PD we used a regularization constant
10-2 All the details about the experimental setting summarized in Table 6. We would like to stress that, as prescribed by the respective convergence theorems, we chose two time-scales learning rate approach for C-PGAE and single time-scale one for RPG-PD. Figure 2a shows the performance curves (i.e., the one associated with the objective function and the cost ones. As can be noticed, C-PGAE manages to strike the objective of the constrained optimization problem with less trajectories. Indeed, the sample-based NPG-PD requires to estimate the value and the action-value functions for all the states and state-action pairs, resulting in analyzing |S] + |S||-A] additional trajectories w.r.t. C-PGAE for every iteration of the algorithm. The sample- basee RPG-PD also requires additional trajectories to be analyzed, which in practice, for a correct learning behavior, result to be the same in number to the extra ones analyzed by NPG-PD.
H.3 Details for the comparison against baselines in CostLQR
In Section 5, we compare our proposals C-PGAE and C-PGPE against the continuous sample-based version of NPG-PD (Ding et al., 2022, Algorithm 1) with works with generic policy parameterizations. In the following, we refer to this version of NPG-PD as NPG-PD2. Moreover, we added ridge- regularized version of NPG-PD2, that we call RPG-PD2, to resemble the type of regularization we employed for our proposed methods. For all the regularized methods (i.e., C-PGAE, C-PGPE, and RPG-PD2) we selected as regularization constant w = 10-1, The setting for this experiment considers a bidimensional LQR environment with a single cost over the provided actions (see Appendix H) and with fixed horizon T 50. Here, the methods aim at maximizing the average reward over trajectories, while keeping the average cost over trajectories under the threshold 6 = 0.9. In particular, C-PGAE learns the parameters of linear gaussian policy with variance 0 10-3 and employing a learning rate schedule governed by the Adam scheduler (Kingma and Ba, 2015) with Ço.u- = 0.001 and (x, = 0.01. C-PGPE learns the parameters of a gaussian hyperpolicy, with a variance of = 10-3 which samples the parameters of a deterministic linear policy. It employs a learning rate schedule
40

---

Details for the Comparison in DGWW Experiment
Environment
DGWW
Horizon
T 100
Policy
Tabular Softmax
Constraint Threshold
b = 0.2
Iterations
K 3000
Batch Size
10
Learning Rates C-PGAE
So 0.01 and (A 0.1
Learning Rates NPG-PD
ço 0.01 and (x 0.1
Learning Rates RPG-PD
ço 0.01 and CA = 0.01
Regularization C-PGAE
w 10
Regularization RPG-PD
w 10-4
Table 6: Details for the comparison of C-PGAE against NPG-PD and RPG-PD in DGWW.
governed by Adam too with Sp.0 0.001 and Çx.0 0.01. Both C-PGAE and C-PGPE were run for 6000 iterations with a batch of 100 trajectories per iteration. NPG-PD2 and RPG- PD2 are both actor-critic methods which were run for K 1000 iterations with batch size of N 600 trajectories per iteration. In particular, among the trajectories of the reported batch size,
N1 500 were used for the inner critic-loop, while N₂ 100 for performance and cost estimations.
The inner loop step size was selected constant, as prescribed by the original algorithm, and with a discounted environments, we tested them on the same LQR as for C-PGAE and C-PGPE, but leaving and 7 0.98 (the effective horizon is (1 71- 50). The step sizes for the primal and dual variables updates were governed by Adam with Ço.0 = 0.003 and (x.p = 0.01. As for C-PGAE, both NPG-PD2 and RPG-PD2 aimed learning the parameters of linear gaussian policy, with variance x 10 All the details about this experiment are summarized in Table 7. Figure 2b reports the learning curves for the average return and the cost over trajectories. As can be seen, our methods manage to solve the constrained optimization problem at hand by leveraging on less trajectories. Indeed, NPG-PD2 and RPG-PD2 suffer the inner critic loop, which add additional trajectories to be analyzed per iteration (in this specific case N1 = 500). We would like to stress that the actor- actor-critic methods were very sensible to the hyperparameters selection, especially the length and the step size of the inner loop.
value 10 5 Furthermore, since such methods were designed for
+-0
H.4 Details for the risk-constrained experiment on Swimmer-y4
In Section we presented an experiment comparing what happens when considering the two explo- ration approaches of C-PGAE and C-PGPE and on different constcoostd optimization problems on the cost version of Swimmer-v4 (details in Appendix H). In particular, we considered such an environment with horizon of T 100. Both the algorithms were run for K 3000 iterations, with batch size of N 100 trajectories per iteration, and with step sizes governed by the Adam scheduler. Moreover, they had a regularization constant 10-4
C-PGAE employed a linear gaussian policy with variance 0 1. Table 8, we list the characteristies for all the experiments with all the risk measures.
On the other hand, C-PGPE employed a gaussian hyperpolicy with variance of 0.01. Such an hyperpolicy sampled parameters for an underlying linear deterministic policy. In Table 9, we list the characteristics for all the experiments with all the risk measures.
As also highlighted the main paper, C-PGPE delivers an hyperpolicy which samples (after having sampled the parameters for the underlying policy) actions whose costs are always under the fixed threshold. Moreover, by considering risk measures different from the average cost one, the empirical distribution of costs shows that these way lighter w.r.t. the ones associated with the deployment of
41

---

Details for the Comparison in CostLQQ Experiment
Environment
Bidimensional CostLQ
Horizon
T 50
(Hyper)Policy
Linear Gaussian with r² 10-3
Constraint Threshold
= 0.9
Iterations (C-PGPE and C-PGAE)
K 6000
Iterations (NPG-PD2 and RPG-PD2)
K 1000
Batch Size (C-PGPE and C-PGAE)
N = 100
Batch Size (NPG-PD2 and RPG-PD2)
N 600
Learning Rate (Adam) C-PGPE
Sp,0 = 10-3 3 and (a = 10-2
Learning Rates (Adam) C-PGAE
ç0.0 = 10 and (a 10-2
Learning Rates (Adam) NPG-PD2
Co 3 10 and 10
Learning Rates (Adam) RPG-PD2
ço 3 10
and CA -0
Regularization C-PGPE
w = 10
Regularization C-PGAE
10
Regularization RPG-PD2
10
Table 7: Details for the comparison C-PGPE and C-PGAE against NPG-PD2 and RPG-PD2 in bodomensional CostLQR.
Risk Measure
Risk Parameter
Ço.0
Sx,0
Sn.0
Average Cost
X
50
10 3
10 2
X
CVaR,
a 0.95
50
10
10-1
10-1
MV
0.5
50
10-4
10-1
10-1
Chance
n 50
0.05
10-4
10-1
10-1
Table Parameters of the risk measures employed in the experiment on Swimmer-v4 with C-PGAE.
Risk Measure
Risk Parameter
Sp.0
S7.0
Average Cost
X
50
10-3
10-2
X
CVaR.
a = 0.95
50
10-3
10-2
10-3
MV
A 0.5
50
10-3
10-2
10-3
Chance
50
0.05
10-3
10
1
Table 9: Parameters of the risk measures employed in the experiment on Swimmer-y4 with C-PGPE.
an hyperpolicy learned considering average cost constraints. C-PGAE also shows results of this kind. However, the displacement between the final empirical cost distributions is not as marked as the one shown with C-PGPE. The exception is from the MV risk measure side, which seems to make C-PGAE learn policy able to pay lighter costs, but resulting poor-performing policy. All the other found (hyper)policies, instead, provide similar performance scores.
42

---

H.S Risk-constrained experiment on Hopper-v4
Here, we present a similar experiment to the one shown on Swimmer-v4. Also in this case, we compare what happens when considering the two exploration approaches of C-PGAE and C-PGPE and on different risk-constrained optimization problems, but on the cost version of Hopper-v4 (details in Appendix H). The experimental setting is quite the same of the one considered above (i.e., T 100,
K 3000, N 100, 10-1).
C-PGAE employed linear gaussian policy with variance o = 1. The characteristics for all the risk measures' experiments are presented Table 10, For the learning rates schedules, employed the Adam scheduler.
Risk Measure
Risk Parameter
So.0
SA,0
Gy.0
Average Cost
x
100
10 2
10-1
x
CVaR,
0.95
100
10-3
10-1
10-1
MV
K 0.5
100
10-4
10-1
10-1
Chance
T2 100
0.05
10-4
10-1
10-1
Table 10: Parameters of the risk measures employed in the experiment on Hopper-v4 with C-PGAE.
C-PGPE employed a gaussian hyperpolicy with variance of 0.1 over an underlying linear deter- ministic policy. The characteristics for all the experiments with all the risk measures are summarized Table 11. For the learning rates schedules, we employed the Adam scheduler.
Risk Measure
Risk Parameter
b
Sp.0
SA.0
S,.0
Average Cost
x
100
10-2
10-1
X
CVaR
a 0.95
100
10-2
10-1
10-2
MV
K 0.5
100
10
10-1
10-2
Chance
100
0.05
10-2
10-1
10-2
Table 11: Parameters of the risk measures employed in the experiment Hopper-v4 with C-PGPE.
Figure 5 shows the empirical distributions of costs over 100 trajectories of the learned (hyper)pplicies via C-PGPE and C-PGAE. C-PGPE shows a behavior that is quite the same as the one shown in the Swimmer-vv environment. Indeed, by considering constraints Chance, the learned hyperpolicy selects parameters for the underlying policy selecting actions that pay way lighter cost w.r.t. the ones provided by hyperpolicy learned by considering constraints average costs. It is worth noticing that the lightest costs are observed when considering the C, or the MV risk measures. In this case, C-PGAE shows similar behavior C-PGPE for what concern the distance in costs between the ones observed by learning considering constraints on the average cost and the ones observed by learning with other risk measures. The lightest costs here can be observed by learning with chance constraints, while, by considering constraints on the MV, the observed costs exceed the ones observed under average leamed (hyper)policies (see Table 4c, C-PGPE exhibit high-performe performing hyperpolicies under average cost or chance constraints, while the ones under CVaR, MV shows similar (low) performance scores. On the other hand, for C-PGAE the learned policy under CVaR, exhibits the same good- performing behavior as the one of the policy learned under average cost constraints.
the the CVaRa, the MV,
constraints. For what concern the performances of the
H.6 Regularization Sensitivity Study
Here, we study the sensitivity of C-PGAE and C-PGPE w.r.t. the regularization term w. We tried the algorithms on a bidimensional I. LQR environment which has been modified to output a cost signal based on the selected action. For the environment at hand, considered horizon T = 50. We run
43

---

30
Chance
30
Chance
MV
MV
Frequency
CVaR
Frequency
CValt
20
20
Average Cost
Average Cost
10
10
20
40
60
80
100
60
80
100
Cost Value
Cost Value
(a) C-PGPE
(b) C-PGAE
Algo.
Cost
CVaR,
MV
Chance
C-PCPE
200.18 =
126.37 1.71
122.28
1.91
190.81 + 1.83
C-PGAE
228.04 0.48
216.81 0.46
136.45
1.35
159.25 t: 2.06
(c) Avg. Ret. (5 runs, mean = std).
Figure 5: Cost distributions with (hyper)policies learned considering different risk measures (5 runs).
Details for the Regularization Sensitivity Study in CostLQR Experiment
Environment
Bidimensional CostLQRR
Horizon
T 50
(Hyper)Policy
Linear Gaussian with o² = 10
Constraint Threshold
b 0.2
Iterations
K 10
Batch Size
N = 100
Learning Rate (Adam) C-PGPE
Sp,u 10-3 and (A 10-2
Learning Rates (Adam) C-PGAE
Ço.0 10-3 and (A = 10-2
Regularization
W E {0, 10-4,04,000 10 10 10
Table 12: Details for the reguarization sensitivity study of C-PGPE and C-PGAE in a bodomensional CostLQR.
both the algorithms for K 10 iterations, with batch size N 100 trajectories per iteration, and with a varying regularization term such that w e {0, 10 10 10-2). : We considered a single constraint on the average trajectory cost, for which we we employed Adam (Kingma and Ba, 2015) with initial rates Ç..0 Ça.0 = 10-3 and (x,0 10-2. Moreover, in this specific experiment C-PGAE employed linear gaussian policy with variance o 10-3 On the other hand, C-PGPE employed a linear gaussian hyperpolicy with a variance Op
threshold b 0.2. For the step size schedules,
10 10-3 over linear deterministic policy. The experimental environment summarized in Table 12. Figures 7 and 6 show the Lagrangian curves, the performance ones (i.c., the one associated with the objective function), and the cost-related ones. From the shown curves is possible notice that, for both C-PCAE and C-PGPE, a higher regularization (w 10-2) corresponds to higher bias w.r.t. the constraint satisfaction. This bias is compliant with what shown by Theorem 3. indeed, the higher the regularization, the higher the constraint threshold should be made stricter. Finally, we report in Figure 8 the evolution of the values of the Lagrangian multipliers À during the learning. As expected from the theory, for both C-PGAE and C-PGPE higher regularization leads to have smaller values of X. Moreover, we empirically notice that C-PGAE reaches higher value of w.r.t. the ones seen by C-PGPE.
44

---

C-PGPE: Lagrangian Curve
20
w =0 0
= 00.0001
Lagrangian Value
15
w =0.01
10
5
2,000
4,000
6,000
8,000
10,000
Iterations
C-PGPE: Performance Curve
Average Trajectory Return
-5
-10
-15
=0
3 0.0000
W =0.01
-20
0
2,000
1,000
6,000
8,000
10,000
Iterations
C-PGPE: Cost Curve
0.3
Average Trajectory Cost
0.2
0
0.1
0..001
-0.01 W
b
0
2,000
4,000
6,000
8,000
10,000
Iterations
Figure 6: Lagrangian, performance and cost curves for C-PGPE over CostLQR with regularization values (0, 10-1, 10022 (5 runs, mean + 95% C.I.).
45

---

C-PGAE: Lagrangian Curve
E =0 0
= 00.0001
Lagrangian Value
15
w =0.01
10
5
2,000
4,000
6,000
8,000
10,000
Iterations
C-PGAE: Performance Curve
Average Trajectory Return
-5
-10
=0
-15
3 0.0001
W =0.01
0
2,000
1,000
6,000
8,000
10,000
Iterations
C-PGAE: Cost Curve
Average Trajectory Cost
0.3
0.2
=0
0.0001
0.1
W
-0.01
b
0
2,000
4,000
6,000
8,000
10,000
Iterations
Figure 7: Lagrangian, performance and cost curves for C-PGAE over CostLQR with regularization values (0, 10-1, 10-22 (5 runs, mean + 95% C.I.).
46

---

C-PGPE: À Curve
10
Wi
0.0001
WO
0.01
X Value
5
0
0
2,000
4,000
6,000
8,000
10,000
Iterations
(a) C-PGPE
C-PGAE: À Curve
WO
WO = 0.0001
WO
0.01
À Value
5
0
0
2,000
4,000
6,000
8,000
10,000
Iterations
(b) C-PGAE
Figure 8: À curves for C-PGPE and C-PGAE over CostLQR with regularization values {0, 1004 4,10-211 2) (5 runs, mean 95% C.I.).
H.7
Computational Resources
All the experiments were run on a 2019 16-inches MacBook Pro. The machine was equipped as follows:
RAM Intel Core i7 (6 cores, 2.6 GHz) 16 GB 2667 MHz DDR4
CPU
GPU Intel UHD Graphics 630 1536 MB
In particular, N 100 trajectories of the MuJoCo environments with T 100 scored マ 2 iterations per second for C-PGAE, while 3 iterations per second for C-PGPE. N = 100 trajectories of the CostLQR environment with 7" 100 scored æ 5 and & iterations per second respectively for C-PGAE and C-PCPE. All the performances are to be considered with parallelization over 10 CPU cores.
47

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and the introduction reflect the original contribution of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work emerges in the final section of the work and the
related works section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
48

---

Justification: All the statements are correlated with proofs. The definitions and the quantity used are clearly presented.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the experimental settings are described, together with choices of all the parameters for the settings at hand.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
49

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The implemented code is provided in zip file which contains detailed instructions on how to use it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce
cnnolicyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpps.ccpppliiiiim wwtppccppccc///ccccccccccccccclt htppllc/ggiieee http//uudeeee/eeee https//oooSSuuiisseeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the experimental settings are described, together with choices of all the parameters for the settings at hand.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The plots of all the experiments are made over an average of different trials and we report, for each shown curve, the 95% confidence interval.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
50

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computational resources employed for th experiments are discussed.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: hww.rps.....//.. cc
Answer: [Yes]
Justification:
We checked the guidelines and we are compliant with them.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As a theoretical research paper, the authors do not see any negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
51

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The only existing asset employed is the MuJoCo (Todorov et al., 2012) control suite, that is properly mentioned.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
52

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. conddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: In order to run the experiments, we implemented a detailed code-base. This asset provided in an anonymized zip file and, conditionally on the paper acceptance, will be made public. The zip file includes a file explaining how to employ the code-base.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
53

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
54


Reviews:
[{"review_id": "6fsxcugXIM", "reviewer": "Reviewer_AKt3", "summary": "This paper studies the problem of constrained MDP. To solve this problem, this paper adopts the policy gradient methods, and specifically they considered the action-based policy gradient method and parameter-based policy gradient method. \n\nThe algorithm proposed in this paper is a type of primal-dual method. Under certain assumptions, this algorithm is shown to have last iterate convergence.\n\nThis paper also executes numerical experiments on various environment with their algorithm, and the experiments validate the results in this paper.", "questions": "Do you have lower bounds showing that these rates are tight?", "limitations": "Yes. The authors addressed all the limitations listed in the guidelines.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is a well-written paper. The description of problem setup, theorems, assumptions are clear. \n\nEven though this is mainly a theory paper, there are numerical experiments which validates the theoretical results.\n\nThis paper has results on the last iterate convergence, which is a property not possessed by most of stochastic optimization algorithms.", "weaknesses": "I don't see significant weaknesses in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for appreciating our work and recognizing its novelty. Below, we respond to the Reviewer's questions.\n\n> Do you have lower bounds showing that these rates are tight?\n\nThe derivation of a lower bound for Constrained MDPs with **continuous state and/or action spaces** is still an **open research problem**. Nevertheless, [1] presents a sample complexity lower bound for the *tabular case* under a generative model, which is of order ${\\Omega}(|\\mathcal{S}| |\\mathcal{A}| (1-\\gamma)^{-5} \\zeta^{-2} \\varepsilon^{-2})$, where $\\zeta$ is the Slater's constant. However, such a lower bound does not apply to our case, since it has been derived for the tabular setting.\n\n**Reference**\n[1] Vaswani, S., Yang, L., & Szepesvári, C. (2022). Near-optimal sample complexity bounds for constrained MDPs. Advances in Neural Information Processing Systems, 35, 3110-3122.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f98yD1VIac", "reviewer": "Reviewer_ZDP8", "summary": "This paper proposes a general framework for addressing safe RL problems via gradient-based primal-dual algorithms. The authors show that the proposed algorithm exhibit global last-iterate convergence guarantees under gradient domination assumptions. Additionally, the authors validate their algorithms on several constrained control problems.", "questions": "Please see the details in \"weakness\".", "limitations": "There is no potential negative social impact of this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and easy to follow.\n2. The paper is technically sound with most claims supported sufficiently.\n3. The theoretical analysis seems novel.", "weaknesses": "Quality:\n\n1. In Theorem 3.1, it requires w=O(\\epsilon) to enforce an overall \\epsilon error, but w should be a fixed number in C-PG algorithm. \n2. It is better to have some experimental results about cost constraints on MuJoCo and include more baselines, e.g., [Zhang et al., 2020, First Order Constrained Optimization in Policy Space].\n\nClarity:\n\n1. The range of reward value is [-1, 0], which is a bit weird compared to normal settings.\n2. The advantage of parameter-based hyperpolicy is not clearly mentioned in the paper.\n\nSignificance:\n\nOne relevant literature is missing. In [Liu et al. 2021, Policy Optimization for Constrained MDPs with Provable Fast Global Convergence], a fast convergence \\tilde{O}(1/\\epsilon) result is proved without multiple assumptions in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for reviewing our work and for appreciating the clarity, the soundness, and the theoretical novelty.\n\n**The role of $\\omega$.** The desired accuracy $\\varepsilon$ is **decided before** employing the algorithms. As prescribed by theory, $\\varepsilon$ appears in the expression of the **learning rates** for the variables to learn and of the **regularization** amount $\\omega$. Tuning hyperparameters based on $\\varepsilon$ is standard in convergence studies of PGs ([1, thr. C.2] for learning rate and horizon; [2, thr. 6.1] for learning rate) and primal-dual PGs ([3, cor. 3] for learning rate and regularization; [6, thr. 3] for algorithm parameters).\n\n**MuJoCo experiments and baselines.** We present experiments in MuJoCo envs. with costs in Sec. 5 and Apx H, focusing on comparing our algorithms under risk measures over costs. All the presented experiments aim to validate our theoretical results. Indeed, we chose as baselines state-of-the-art PGs for CMDPs [4, 5] coming with convergence guarantees comparable to our results. Specifically, [4] considers tabular CMDPs, while [5] addresses continuous CMDPs but loses last-iterate guarantees. Instead, the paper \"Zhang et al., 2020\" proposed by the Reviewer solves an approximated constrained optimization problem and its performance is characterized by worst-case policy improvement only and no convergence guarantee. It has a more practical perspective, thus we believe that a comparison with it is beyond the scope of our work.\n\n**Reward range.** This choice is based on formulating the constrained optimization problem for costs, which are positive. Thus, we use a cost $c_0$ in place of the reward $r$ for the optimization part of the problem. The cost function to minimize is defined at line 116 as $c_0(s,a) = - r(s,a)$. We consider $r$ ranging in $[-1,0]$, so that $c_0$ ranges in $[0,1]$. We stress that this choice for the range induces no loss of generality w.r.t. a range $[R_{\\min}, R_{\\max}]$.\n\n**Hyperpolicy advantage.** We are happy to clarify this point.\n1. **Trade-off between exploration approaches**. There is a trade-off between PB and AB explorations [2,5]. The PB approach struggles with **large parameterizations** (large $d_{\\Theta}$), but its gradient estimator has **lower variance** compared to AB. The AB approach struggles with **long-lasting interactions** (large $T$ or $\\gamma \\to 1$) and **large action vectors** (large $d_{\\mathcal{A}}$), but comes with a **higher variance** gradient estimator than PB. Thus, PB exploration can be preferable in some cases.\n2. **PB exploration and risk constraints**: In Sec. 5, we show that PB exploration, when considering risk constraints over costs, can learn policies **inducing safer behaviors compared to AB exploration**. This arises from the semantic differences in how the two approaches enforce risk constraints (lines 288-293).\n\nFinally, we note that PB exploration has not been addressed in the CRL literature (to our knowledge). We thank the Reviewer for pointing out this lack of clarity, will make it more explicit in the final version of the paper.\n\n**Comparison with Liu et al. 2021.** The paper proposed by the Reviewer considers mainly the setting of: (i) *tabular* CMDPs; (ii) *softmax* policies; (iii) *exact gradients* provided by an oracle; and (iv) provides an *average* (not last-iterate) convergence rate of order $\\tilde{\\mathcal{O}}(\\epsilon^{-1})$. As shown in Table 1, in the same setting, our convergence rate is $\\mathcal{O}(\\varepsilon^{-2})$, i.e., when: (1) GD condition holds $\\psi = 1$ (which happens under (i) *tabular* CMDPs; (ii) *softmax* policies; see Remark 3.1); (2) exact gradients are available; (3) the regularization $\\omega$ is $\\mathcal{O}(\\varepsilon)$. Liu et al. 2021 faster convergence is justified by the fact that their approach **relies to the softmax policy model**, indeed, **applies to tabular problems only**, and **does not reach a last-iterate convergence**.\nMoreover, Liu et al. 2021 propose a sample-based variant which requires $\\tilde{\\mathcal{O}}(\\varepsilon^{-3})$ (still for the tabular case and with an average convergence guarantee). As shown in Table 1, in such case (i.e., $\\psi=1$ and inexact gradients) our last-iterate rate is $\\tilde{\\mathcal{O}}(\\omega^{-4}\\varepsilon^{-3})$ (being $\\tilde{\\mathcal{O}}(\\varepsilon^{-7})$ with $\\omega=\\mathcal{O}(\\varepsilon)$). However, the setting considered by Liu et al. 2021 assumes the access to a **generative model generating independent trajectories from any arbitrary pair $(s,a)$**, a demanding requirement that we overcome.\nFinally, we stress that in the setting considered by Liu et al. 2021, most of our assumptions hold. Indeed, asm. 3.1 holds in the form of the Slater's condition; asm. 3.2 holds with $\\psi=1$ for tabular CMDPs with softmax policies (see Remark 3.1); asm. 3.3 holds for tabular softmax that is known to lead to bounded gradients and smooth objectives [7]; asm. 3.4 holds because the mentioned paper considers exact gradients or it uses good events considering the differences between the estimations and the real values of $V$ and $Q$ bounded (their Definition 3). We thank the Reviewer for suggesting this paper; we will add it in the final version of the paper, especially in the comparison table (Table 2).\n\n**References**\n[1] Yuan et al. (2022). A general sample complexity analysis of vanilla policy gradient.\n\n[2] Montenegro et al. (2024). Learning Optimal Deterministic Policies with Stochastic Policy Gradients.\n\n[3] Ding et al (2024). Last-iterate convergent policy gradient primal-dual methods for constrained mdps.\n\n[4] Ding et al. (2022). Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs.\n\n[5] Metelli et al. (2018). Policy optimization via importance sampling.\n\n[6] Liu et al. (2021). Policy optimization for constrained mdps with provable fast global convergence.\n\n[7] Papini et al. (2022). Smoothing policies and safe policy gradients.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "64vfHqdLsX", "reviewer": "Reviewer_Vs5i", "summary": "The paper studies policy-based methods in constrained RL. The author first establishes the last-iterate convergence of the algorithm C-PG under a form a gradient domination assumptions. Then, the author further designs action-based and parameter-based versions of C-PG to handle constraints defined in terms of risk measures over the costs. Finally, the proposed algorithms are validated by numerical examples of control problems.", "questions": "* I hope the author could further clarify the contribution/role of Section 4 in the paper.\n* Could the author also discusses how the techniques used in the paper different from that in Ding et al., 2024?", "limitations": "The paper has stated assumptions clearly in the paper. Yet, although the author mentions \"The limitations of the work emerges in the final section of the work\", I failed to find that section in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Despite not being the first paper to establish the last-iterate convergence of primal-dual type algorithms, I believe the convergence results for C-PG is also a meaningful contribution to the literature. \n* More general constrained RL formulations are studied in the paper, where constrains are defined in terms of risk measures. The author adapts C-PG to another two sample-based variants for these formulations.\n* Overall, the paper is well-written and easy to follow. The author uses highlights for the two different algorithms/settings, making them easy to distinguish.", "weaknesses": "* The role of Section 4 in the paper is unclear to me. Good theoretical results are established for Section 3, yet, there is no general theoretical results for Section 4, besides some cases where results from Section 3 can be directly applied. This makes Section 4 looks like an ''add-on'' to Section 3. \n* For theoretical results, e.g., Theorems 3.1 and 3.2, it would be better for the author to briefly discuss the proof idea in the main paper.\n\nMinor comments: it would be better to make figure legends exactly align with the names of algorithms, e.g., change CPGAE to C-PGAE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for having appreciated the contribution our work brings and its presentation. In the following, our answers to the Reviewer's concerns.\n\n**Section 4.** We thank the Reviewer for having raised this point. First of all, **Section 3** introduces the **exploration-agnostic** algorithm C-PG which exhibits global last-iterate convergence **guarantees** (Theorems 3.1 and 3.2). C-PG is thought to be employed for constrained RL problems in which the constraints are enforced in terms of **expected values over cost** functions.\nIn **Section 4**, we particularize C-PG in two versions, C-PGAE and C-PGPE, depending on the employed **exploration approach**. Moreover, in Section 4 we **extend** the **framework** presented in Section 3 to handle constraints formulated in terms of **risk measures** over cost functions, employing a **unified formulation** for risk measures. In Table 3 (that we will move to the main paper leveraging the additional page), we show the mapping of the functions $f$ and $g$ (which form the unified risk measure formulation) to several risk measures, in which also the **expectation over costs** is **included**. While we agree that no further theoretical guarantees are presented in Section 4, Remark 4.1 comments on whether the theoretical guarantees of Section 3 applies also for risk measures different from the expected values over costs.\nBesides making the framework more general, the introduction of the constraints over risk measures allow to (empirically) appreciate the **semantic difference** of enforcing constraints while considering different **exploration** approaches (parameter-based vs action-based). In this sense, Section 4 has the goal to highlight the generality of the approach beyond the constraints formulated as expected costs.\n\n**Thr. 3.1 and 3.2.** Thank you for the raising this point. We have deferred the proofs to Appendix E due to space constraints. We will leverage the additional page to add the **sketches of the proofs**.\n\n**Plot labels.** We agree with the Reviewer and we will fix these typos in the final version of the paper.\n\n**Comparison with Ding et al. 2024.** We are happy to clarify this point. \n* From a **technical** point of view, to achieve global last-iterate convergence guarantees, we employ the **$\\psi$-gradient domination** (Assumption 3.2) on the Lagrangian function w.r.t. the parameters of the (hyper)policy to be learned, rather than focusing on specific classes of policies or on approximation error assumptions (Assumption 2 of [1]). Moreover, we study the convergence of a different **potential function** $\\mathcal{P}_k$ (Section 3.3) and we prove that when it is bounded, then both the objective function gap and the constraint violations are bounded (**Theorem 3.1**). Finally, a new technical challenge we had to face was the study of the recursion appearing in Equation (215). For this, we derived the technical **Lemma F.1** and conducted a quite extensive study of the recurrences of the form $r\\_{k+1} \\le r\\_k - a \\\\max\\\\{0,r\\_k\\\\}^\\phi + b$ in **Appendix G**.\n* From an **algorithmic** perspective, we propose a *meta algorithm* C-PG that (i) requires a **regularization only on $\\lambda$** ([1] performs also entropy regularization w.r.t. the policy), (ii) that is able to handle **multiple constraints** ([1] handles the single constraint case only), (iii) that requires learning rates on **two different time scales** ([1] is single time scale), and (iv) that leverages on an **alternate ascent-descent** scheme. Moreover, [1] proposes also an optimistic method which works only with exact gradients. We particularize C-PG with **parameter-based** and **action-based** exploration approaches ([1] uses just the action-based one) both working with **generic parameterizations** and with **inexact gradients** in **continuous action** and **state** spaces.\n\n**Limitations.** The Reviewer is right, the reported sentence is misleading. We meant that the limitations of our work are to be considered as the points that future works should address (Section 6). For instance, the development of C-PG variants ensuring the same guarantees shown in this paper, but with a single time scale learning rates. We will make more explicit the limitations of our work in the final version of the paper.\n\n**References**\n[1] Ding, D., Wei, C. Y., Zhang, K., & Ribeiro, A. (2024). Last-iterate convergent policy gradient primal-dual methods for constrained mdps. Advances in Neural Information Processing Systems, 36.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EZYJJQ61Sl", "reviewer": "Reviewer_zSqV", "summary": "The paper targets the constrained RL problem and provides a primal-dual method C-PG to solve it. The proposed method is extended to C-PGAE and C-PGPE to handle the constraint cases with risk measures.  The paper provides a theoretical analysis of the global last-iterate convergence guarantees toward C-PG and empirically tests the C-PGAE and C-PGPE.", "questions": "As mentioned in Weaknesses, as the dimension-free property of the proposed algorithm is claimed many times in the paper, have you proven that the problem dimension is independent of the constants of assumptions 2, 3, and 4? What is the reason and the theoretical intuition that it is dimension-free?\n\nHow does the convergence rate change after introducing the regularization term for the last-iteration convergence? As it introduces an extra error term of $w$ in Theorem 3.1, it may deteriorate the convergence rate.\n\nI am willing to increase my score if weaknesses and questions are addressed.", "limitations": "No limitations of the paper are explicitly stated by the author.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written. All the assumptions are standard in literatures or justified. The theoretical result is rigorous.", "weaknesses": "The main weakness of the paper comes from the technical novelty. From the algorithm design, the primal-dual method is widely used in constrained optimization problems and constrained RL problems, and the regularization term is also not new in constrained optimization problems [1]. The proposed algorithm basically follows the existing methods without a significant novel design. The algorithm can be naturally adapted to C-PGAE and C-PGPE to handle the constraint cases with risk measures due to the well-established policy gradient for the case. From the theoretical analysis, assumptions 1,2, 3, and 4 are standard assumptions for constrained optimization problems. With these assumptions, the constrained RL problem is transferred to a pure constrained optimization problem. Although the assumptions are justified in RL, I believe there are lots of theoretical results for constrained optimization problems with these assumptions, and can be directly used in constrained RL. Therefore, the theoretical novelty may also be marginal.\n\nAlthough the paper claims that it addresses some theoretical limitations of previous works, these limitations are somehow avoided, rather than being addressed. For example, the paper does not require the softmax policy, but assumption 2 is verified under the softmax policy. The provided convergence rates do not depend on the problem dimension, but the problem dimension may be included in the constants of assumptions 2, 3, and 4.\n\nThe experiment scenarios are relatively simple, but it is acceptable if the theoretical result is sufficiently solid.\n\n\n\n\n\n[1] Khuzani, Masoud Badiei, and Na Li. \"Distributed regularized primal-dual method: Convergence analysis and trade-offs.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our paper and for recognizing that our work is well-written and that our theoretical results are rigorous. Below, we address the raised issues. \n\n**General novelty.** To the best of our knowledge, our paper is the first to introduce a **general framework** for CRL with primal-dual PGs, that is able to address simultaneously: (i) **continuous action and state spaces** (more general than the tabular case considered by some previous works), (ii) multiple constraints, (iii) **generic parameterizations of (hyper)policies** (strictly generalizing the approaches based on softmax), (iv) **inexact gradients** (avoiding irrealistic assumption of exact gradients of some previous works), (v) **parameter-based exploration** (action-based only was considered in previous works); (vi) delivering **global last-iterate convergence guarantees** (guarantee stronger than convergence *on average*).\n\n**Algorithmic novelty and assumptions role.** Algorithmically, while the primal-dual PG approach is well-explored [1,2,4,5], **PB exploration has not been addressed until now**. Our main contribution is the **theoretical analysis**, which provides state-of-the-art results and addresses some limitations discussed earlier.\nUnder our assumptions (which are standard as recognized by the Reviewer [1,4,5,6,7]), we remark that **CRL does not reduce to a \"pure constrained optimization\" problem**. Indeed, with inexact gradients, the problem remains a learning one due to the need for **gradient estimation**, which affects algorithmic choices like the learning rates tuning.\n\n**Technical novelty.** We stress that our paper provides novel technical contributions, which we comment on in the following.\nWe employ the **$\\psi$-gradient domination** (asm. 3.2) on the Lagrangian function w.r.t. the parameters of the (hyper)policy to be learned, rather than focusing on specific classes of policies or on approximation error assumptions (asm. 2 of [1]). Moreover, we study the convergence of a new and different **potential function** $\\mathcal{P}_k$ (Sec. 3.3) and we prove that when it is bounded, then both the objective function gap and the constraint violations are bounded (**thr. 3.1**). Finally, a new technical challenge we had to face was the study of the recursion appearing in Eq. (215). For this, we derived the technical **lem. F.1** and conducted a quite extensive study of the recurrences of the form $r\\_{k+1} \\le r\\_k - a \\\\max\\\\{0,r\\_k\\\\}^\\phi + b$ in **apx. G**. These results and theoretical tools are, in our opinion, novel and of potential *independent interest*.\n\n\n**Addressing of theoretical limitations of other works.** We address a **more general** setting than that of softmax policies. While our asm. 3.2, as noted by the Reviewer, is satisfied by the softmax policy, **Remark 3.1 shows that it applies beyond softmax policies**, thereby **generalizing and unifying** the setting of previous works. Additionally, we tackle other challenges, including the use of inexact gradients, handling multiple constraints, and operating in a continuous setting with $|\\mathcal{S}| = |\\mathcal{A}| = \\infty$.\n\n**Dimension-free property.** Thank you for highlighting this potential source of confusion. To clarify, dimension-free theoretical guarantees [1,4,5,8] mean our results apply to **continuous state and action spaces without dependence on the cardinality** of these spaces (i.e., $|\\mathcal{S}|$ and $|\\mathcal{A}|$). As shown by [3], in this setting, new problem dimensions must be considered: **$d_{\\Theta}$ (parameterization dimension), $d_{\\mathcal{A}}$ (action vector dimension), and $T$ or $(1-\\gamma)^{-1}$ (trajectory length)**. While the constants in our assumptions may depend on these dimensions, they do not depend on $|\\mathcal{S}|$ or $|\\mathcal{A}|$. We will clarify this in the final version of the paper.\n\n**Regularization and convergence rate.** The Reviewer is right. Introducing the regularization term with magnitude $\\omega$ affects convergence properties, indeed, Table 1 details complexities w.r.t. $\\varepsilon$ and $\\omega$. However, the ridge-regularization of the Lagrangian with respect to $\\lambda$ makes it **strongly convex (quadratic) in $\\lambda$**, allowing last-iterate convergence **without additional assumptions**. In contrast, existing works on CRL with **non-regularized Lagrangians provide convergence guarantees on average (not last-iterate)** [4,5,8].\n\n**References**\n[1] Ding et al. (2024). Last-iterate convergent policy gradient primal-dual methods for constrained mdps.\n\n[2] Khuzani et al. (2016). Distributed regularized primal-dual method: Convergence analysis and trade-offs.\n\n[3] Montenegro et al. (2024). Learning Optimal Deterministic Policies with Stochastic Policy Gradients.\n\n[4] Ding et al. (2020). Natural policy gradient primal-dual method for constrained markov decision processes.\n\n[5] Ding et al. (2022). Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs.\n\n[6] Bai et al. (2023). Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm.\n\n[7] Yang et al. (2020). Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems.\n\n[8] Liu et al. (2021). Policy optimization for constrained mdps with provable fast global convergence.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper makes a significant contribution to the field of constrained RL by establishing the last-iterate convergence of C-PG, a result that strengthens the theoretical foundation of policy-based methods in this domain. Furthermore, the authors extend their analysis to encompass more general constrained RL formulations, demonstrating the adaptability of their approach. Authors have done a amazing work presenting the paper in a clear and organized way, making the complex ideas accessible to readers. 

However, as reviewers pointed out, the theoretical contribution of Section 4 will benefit from additional revisions, with the authors enhancing the paper by providing a more thorough discussion of the proof techniques employed. While there is potential for further refinement, the paper's merits outweigh its shortcomings, justifying an acceptance decision. The reviewers anticipate that the authors will address the constructive feedback provided, leading to a stronger final version of the paper.
Decision: Accept (poster)