Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning

Authors: alessandro  montenegro
marco  mussi
matteo  papini
alberto maria metelli
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:25:02

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.

Main paper: 
 introduction: 
 When applying Reinforcement Learning (RL, Sutton and Barto, 2018) to real-world scenarios, we are 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 autonomousdriving 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 to avoid damaging it (i.e., constraints) (Likmeta et al., 2020) . To pursue such an objective, it is necessary to extend the RL 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 RL 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 et al., 2022; Ding et al., 2024) . However, especially in safety-critical 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 a 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-Variance (MV, Markowitz and Todd, 2000; Li and Ng, 2000) . These risk measures offer a 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 continuouscontrol 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 to sensor and actuator noise (Gravell et al., 2020) , robustness in partially-observable 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 Ding et al., , 2021;; Bai et al., 2022) , which can be formulated through Lagrangian optimization of the primal (i.e., 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-based CRL focuses only on the action-based exploration approach (Achiam et al., 2017; Stooke et al., 2020; Bai et al., 2023) , while the parameter-based 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 et 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; (ii) 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 a general constrained optimization problem, which is agnostic w.r.t.both the action-based or parameter-based paradigm. • In Section 3, we introduce C-PG, a 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; (iii) 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 a 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 are reported in Appendix E.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 as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 Notation. For a measurable set X , we denote as ∆pX q the set of probability measures over X .For P P ∆pX q, we denote with p its density function and we will interchangeably use x " P or x " p to express that random variable x is distributed according to P . For n, m P N with n ď m, we denote n :" t1, 2, . . . , nu and with n, m :" tn, n `1, . . . , mu. For a vector x P R d , we denote as x i the i-th component of x. For a P R, we define paq `:" maxt0, au and we extend the notation to vectors as pxq `" ppx 1 q `, . . . , px d q `qJ . Given a set X Ď R d , we denote with Π X the Euclidean norm projection, i.e., Π X x P arg min yPX }y ´x} 2 for any x P R d . For two vectors x, y P R d , we denote with xx, yy their inner product. A function f : R d Ñ R is L 1 -Lipschitz continuous if |f pxq ´f px 1 q| ď L 1 }x ´x1 } 2 and L 2 -smooth if it is differentiable and }∇ x f pxq ´∇x f px 1 q} 2 ď L 2 }x ´x1 } 2 , for every x, x 1 P R d .Constrained Markov Decision Processes. A Constrained Markov Decision Process (CMDP, Altman, 1999) with U constraints is represented by M C :" `S, A, p, r, tc i u iP U , tb i u iP U , µ 0 , γ ˘, where S Ď R d S and A Ď R d A are the measurable state and action spaces, p : S ˆA Ñ ∆ pSq is the transition model, where pps 1 |s, aq is the probability density of getting to state s 1 P S given that action a P A is taken in state s P S, r : S ˆA Ñ r´1, 0s is the reward function, where rps, aq is the instantaneous reward obtained by playing action a in state s, c i : S ˆA Ñ r0, 1s is the i-th cost function, where c i ps, aq is the i-th instantaneous cost obtained by playing action a in state s, b i P r0, J max s with J max :" 1´γ T 1´γ is the threshold for the i-th cost for every i P U , µ 0 P ∆pSq is the initial state distribution, and γ P r0, 1s is the discount factor. A trajectory τ of length T P N Y t`8u is a sequence of T state-action pairs: τ " ps τ,0 , a τ,0 , . . . , s τ,T ´1, a τ,T ´1q. The discounted return over a trajectory τ is Rpτ q :" ř T ´1 t"0 γ t rps τ,t , a τ,t q, while the i-th discounted cumulative cost is C i pτ q :" ř T ´1 t"0 γ t c i ps τ,t , a τ,t q. We define the additional cost function c 0 ps, aq :" ´rps, aq and C 0 pτ q :" ´Rpτ q. Note that Rpτ q, C i pτ q P r0, J max s for every i P U and trajectory τ .Action-based Policy Gradients. Action-based (AB) PG methods focus on learning the parameters θ P Θ Ď R dΘ of a parametric stochastic policy π θ : S Ñ ∆pAq, where π θ pa|sq represents the probability density of selecting action a P A being in state s P S. At each step t of the interaction with the environment, the stochastic policy is employed to sample an action a t " π θt p¨|s t q. To assess the performance of π θ w.r.t. the i-th cost function, with i P 0, U , we employ the AB performance index J A,i : Θ Ñ R, which is defined as J A,i pθq :" E τ "pAp¨|θq rC i pτ qs, where p A pτ, θq :" µ 0 ps τ,0 q ś T ´1 t"0 π θ pa τ,t |s τ,t qpps τ,t`1 |s τ,t , a τ,t q is the density of trajectory τ induced by policy π θ .Parameter-based Policy Gradients. Parameter-based (PB) PG methods focus on learning the parameters ρ P R Ď R d R of a parametric stochastic hyperpolicy ν ρ P ∆pΘq. The hyperpolicy ν ρ is used to sample parameter configurations θ " ν ρ to be plugged into an underlying parametric policy π θ , that will be then used for the interaction with the environment. Notice that π θ can also be deterministic. To assess the performance of ν ρ w.r.t. the i-th cost function, with i P 0, U , we employ the PB performance index J P,i : R Ñ R, which is defined as J P,i pρq :" E θ"νρ rE τ "pAp¨|θq rC i pτ qss.Constrained Optimization Problem. Having introduced the AB and PB performance indices, we formulate a constrained optimization problem (COP) agnostic w.r.t. the exploration paradigm: min υPV J :,0 pυq s.t. J :,i pυq ď b i , @i P U ,where : P tA, Pu and υ is a generic parameter vector belonging to the parameter space V. When : " A, we are considering the AB exploration paradigm, then V " Θ. On the other hand, when : " P, we are in the PB exploration paradigm, then V " R.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 in 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
last-iterate global convergence of c-pg: 
 In this section, we present C-PG, a general primal-dual algorithm that optimizes a 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-free1 last-iterate global convergence guarantees (Section 3.3). While C-PG is designed to 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 J i in place of J :,i .To solve the COP of Equation ( 1) we resort to the method of Lagrange multipliers (Bertsekas, 2014) introducing the Lagrangian function L 0 pυ, λq :" J 0 pυq `řU i"1 λ i pJ i pυq ´bi q " J 0 pυq xλ, Jpυq ´by, where υ P V is the primal variable and λP R U ě0 are the Lagrangian multipliers or dual variable, J " pJ 1 , . . . , J U q J , and b " pb 1 , . . . , b U q J . This allows to rephrase the COP in Equation ( 1) as a min-max optimization problem min υPV max λPR U ě0 L 0 pυ, λq and we denote with H 0 pυq :" max λPR U ě0 L 0 pυ, λq the primal function and with H 0 :" min υPV H 0 pυq. To obtain a last-iterate convergence guarantee, we make use of a regularization approach. Specifically, let ω ą 0 be a regularization parameter, we define the ω-regularized Lagrangian function as follows:L ω pυ, λq :" J 0 pυq `U ÿ i"1 λ i pJ i pυq ´bi q ´ω 2 }λ} 2 2 " J 0 pυq `xλ, Jpυq ´by ´ω 2 }λ} 2 2 . (2)The ridge regularization makes L ω pυ, λq a strongly concave function of λ at the price of a bias that is quantified in Lemmas E.1, E.2 and E.3. Thus, we address the ω-regularized min-max optimization problem min υPV max λPΛ L ω pυ, λq, where Λ :" tλ P R U ě0 : }λ} 2 ď ω ´1?U J max u, in replacement of the original (non-regularized) one. For this problem, we introduce the primal function H ω pυq :" max λPΛ L ω pυ, λq, that, thanks to the ridge regularization, admits the closedform expression H ω pυq " J 0 pυq `1 2ω ř U i"1 ppJ i pυq ´bi q `q2 " J 0 pυq `1 2ω }pJpυq ´bq `}2 2 , where the optimal values of the Lagrange multipliers is given by λ ˚pυq " Π Λ `1 ω pJpυq ´bq ˘"1 ω pJpυq ´bq `that is guaranteed to have norm smaller than ω ´1?U J max . Furthermore, we define H ω :" min υPV H ω pυq. C-PG updates the parameters pυ k , λ k q with an alternate gradient descentascent scheme for every k P N:Primal Update Dual Update υ k`1 Ð Π V ´υk ´ζυ,k p ∇ υ L ω pυ k , λ k q ¯λk`1 Ð Π Λ ´λk `ζλ,k p ∇ λ L ω pυ k`1 , λ k q ¯,where ζ υ,k , ζ λ,k ą 0 are the learning rates and p ∇ υ L ω pυ k , λ k q, p ∇ λ L ω pυ k , λ k q are estimators of the gradients ∇ υ L ω pυ k , λ k q, ∇ λ L ω pυ k , λ k q of the regularized Lagrangian function.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.). There exist υ 0 P V and λ 0 P R U ě0 such that L 0 pυ 0 , λ 0 q " min υPV max λPR U ě0 L 0 pυ, λq.Assumption 3.1 ensures that the value of the min-max problem is attained by a pair of primal-dual values υ 0 P V and λ 0 P R U ě0 which, consequently, satisfy L 0 pυ 0 , λq ď L 0 pυ 0 , λ 0 q ď L 0 pυ, λ 0 q for every υ P V and λ P R U ě0 . Analogous assumptions have been considered by Yang et al. (2020) and Ying et al. (2022) . Thus, pυ 0 , λ 0 q is a saddle point of the Lagrangian function L 0 and, consequently, strong duality holds. Alternatively, as commonly requested in CRL works, assuming 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 Ding et al., , 2024)) . 2 Assumption 3.2 (Weak ψ-Gradient Domination). Let ψ P r1, 2s. There exist α 1 ą 0 and β 1 ě 0 such that, for every υ P V and λP Λ, it holds that:}∇ υ L 0 pυ, λq} ψ 2 ě α 1 ´L0 pυ, λq ´min υ 1 PV L 0 pυ 1 , λq ¯´β 1 .(3) Assumption 3.2 is customary in the convergence analysis of policy gradient methods and it is usually enforced on the objective J 0 only (Yuan et al., 2022; Masiha et al., 2022; Fatkhullin et al., 2023) . In particular, when β 1 " 0, we speak of (strong) ψ-gradient domination. In this form, for a generic exponent ψ P r1, 2s, this assumption has been employed by Masiha et al. (2022) . Particular cases are when ψ " 1, which corresponds to the standard (weak) gradient domination (GD), while for ψ " 2, we have the so-called Polyak-Łojasiewicz (PL) condition. Notice that Assumption 3.2 is enforced on the non-regularized Lagrangian function L 0 (i.e., ω " 0). However, it is easy to realize that it holds for the regularized one L ω by simply computing the terms of Equation ( 3) replacing L 0 with L ω .Remark 3.1 (When does Assumption 3.2 holds?). As remarked by Ding et al. (2024) , the Lagrangian function, for a fixed value of λ, can be regarded as the expected return of a new reward function ´C0 xλ, Cy, where C " pC 1 , . . . , C U q J . As a consequence, a sufficient condition for Assumption 3.2 is when the selected class of policies guarantees the ψ-gradient domination regardless of the reward function. For instance, in tabular environments with natural policy parametrization, i.e., π θ psq " θ s for every s P S, the PL condition (ψ " 2 and β 1 " 0) holds (Bhandari and Russo, 2024) . Moreover, in tabular environments with softmax policy, i.e., π θ pa|sq9 exppθps, aqq, GD (ψ " 1 and β 1 " 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 π θ is non-degenerate for every θ P Θ, i.e., Fpθq " E π θ r∇ θ log π θ pa|sq∇ θ log π θ pa|sq J s ľ µ F I for some µ F ą 0 and (ii) a compatible function approximation bias bound holds, i.e., E π θ ˚rpA π θ ps, aq ´p1 ´γqu J ∇ θ log π θ pa|sqq 2 s ď ϵ bias being u " Fpθq : ∇ θ J 0 pθq and the advantage function A π θ computed w.r.t. reward ´C0 ´xλ, Cy, the weak GD (ψ " 1) holds with α 1 " Gµ ´1 F and β 1 " p1 ´γq ´1? ϵ bias , where G is such that }∇ θ log π θ pa|sq} 2 ď G (Masiha et al., 2022) .In principle, we could have enforced Assumption 3.2 on the primal function H ω pυq only. However, this would come with two drawbacks: (i) the assumption would now depend explicitly on ω; (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 H ω pυq in the regularized case.Assumption 3.3 (Regularity of the Regularized Lagrangian L ω ). There exists L 1 , L 2 , L 3 ą 0 such that, for every υ, υ 1 P V, and for every λ, λ 1 P Λ, the following hold:EQUATIONEQUATIONEQUATION)Notice that, similarly to Assumption 3.2, we realize that if Assumption 3.3 holds for the nonregularized Lagrangian L 0 , it also holds (with the same constants) for the regularized one L ω for every ω ą 0. 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 J i are Lipschitz continuous w.r.t. υ. Indeed, }∇ λ L 0 pυ, λq ´∇λ L 0 pυ 1 , λq} 2 " }Jpυq ´Jpυ 1 q} 2 . Equation ( 5) is fulfilled when the objective function J 0 and the constraint functions J i are smooth w.r.t. υ and the Lagrange multipliers are bounded (guaranteed thanks to the projection Π Λ ), since }∇ υ L 0 pυ, λq ´∇υ L 0 pυ 1 , λq} 2 ď |∇ υ J 0 pυq ´∇υ J 0 pυ 1 q| `řU i"1 λ i |∇ υ J i pυq ´∇υ J i pυq|. Finally, Equation ( 6) is fulfilled whenever functions J i admit bounded gradients, since }∇ υ L 0 pυ, λq ´∇υ L 0 pυ, λ 1 q} 2 ď }∇ υ Jpυqpλ´λ 1 q} 2 . It is worth noting that L 2 depends on the norm of the Lagrange multipliers and, consequently, due 2 Assumption 3.1 combined with Slater's condition, i.e, the existence of a parametrization r υ P V for which there exists ξ ą 0 such that Jipr υq ´b ă ´ξ for all i P U (strictly feasible), allows providing an upper bound to the Lagrange multipliers }λ 0 }2 ď ξ ´1pJ0p r υq ´J0pυ 0 qq using standard arguments (see Ying et al., 2022) .to the projection operator, we have that L 2 " Opω ´1q, whereas L 1 and L 3 are independent on ω.3 Explicit conditions on the constitutive elements of the MDP and (hyper)policies to ensure Lipshitzness 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 L ω are inherited by the primal function H ω which results to be `L2 `L2 1 ω´1˘smooth (Lemma E.7). Concerning the regularity of L ω w.r.t. λ, we observe that it is a quadratic function and, therefore, it is ω-smooth and satisfies the PL condition, i.e., Assumption 3.2 with ψ " 2, β 1 " 0, and with α 1 " ω (Lemma E.5). Assumption 3.4 (Bounded Estimator Variance). For every υ P V and λ P Λ, the estimators p ∇ υ L ω pυ, λq and p ∇ λ L ω pυ, λq are unbiased for ∇ υ L ω pυ, λq " ∇ υ J 0 pυq `řU i"1 λ i ∇ υ J i pυq and ∇ λ L ω pυ, λq " Jpυq ´b ´ωλ with bounded variance, i.e., there exist V υ , V λ ă `8 such that:EQUATIONNote that V υ typically depends on the Lagrange multipliers and, for standard sample mean estimators, it is of order V υ " Opω ´2q thanks to the projection operator. Contrary, V λ is usually not affected by ω since the term ωλ 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 et al. 2022 and Montenegro et al. 2024 , Appendix E).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 P k pχq :" a k `χb k , where a k :" ErH ω pυ k q ´Hω s and b k :" ErH ω pυ k q ´Lω pυ k , λ k qs and χ P p0, 1q will be specified later. Since a k , b k ě 0, intuitively, if P k pχq « 0 we have that both a k , b k « 0 and, consequently, convergence is achieved. Let us start relating P k pχq, with the solution of the COP in Equation (1). Theorem 3.1 (Objective Function Gap and Constraint Violation). Let ϵ ą 0. Under Assumption 3.1, if P k ď ϵ, it holds that:ErJ 0 pυ k q ´J0 pυ 0 qs ď ϵ `ω 2 }λ 0 } 2 2 , ErpJ i pυ k q ´bi q `s ď 4ϵ `ω}λ 0 } 2 , @i P U . (8)Theorem 3.1 justifies the study of the potential P k as a technical tool to ensure convergence. Indeed, whenever P k ď ϵ both the (i) objective function gap and (ii) the constraint violation scale linearly with ϵ and with the regularization parameter ω of the regularized Lagrangian L ω multiplied by the norm of the Lagrange multipliers of the non-regularized problem }λ 0 } 2 , which are finite under Assumption 3.1. This expression also suggests a choice of ω " Opϵq to enforce an overall ϵ error on both quantities. Note that, from Theorem 3.1, it is immediate to employ a conservative constraint (b 1 i « b i ´4ϵ ´ω}λ 0 } 2 2 ) to achieve zero constraint violation with no modification of the algorithm. We are now ready to state the convergence guarantees for the potential function. Theorem 3.2 (Convergence of P K ). Under Assumptions 3.2, 3.3, 3.4, for χ ă 1{5, sufficiently small ϵ and ω, and a choice of constant learning rates ζ υ , ζ λ , we have P K pχq ď ϵ `β1 {α 1 whenever:4 • K " Opω ´1 logpϵ ´1qq if ψ " 2 and the gradients are exact (i.e., V υ " V λ " 0); • K " Opω ´1ϵ ´2 ψ ´1q if ψ P r1, 2q and the gradients are exact (i.e., V υ " V λ " 0); • K " Opω ´3ϵ ´4 ψ `1q if ψ P r1, 2s and the gradients are estimated (i.e., V υ " Opω ´2q and V λ " Op1q).Some comments are in order. First, Theorem 3.2 holds for a specific choice of the constant χ P p0, 1{5q defining the potential function P K . Second, the presented rates hold for sufficiently small values of ϵ and ω. This is just for presentation purposes, as the sample complexity5 can only improve if we increase the values of ϵ and ω. Third, in the proof, an explicit expression of the learning rates is provided. Concerning their orders, for the case of exact gradients, we choose ζ λ " ω ´1 and ζ υ " Opωq, whereas for the estimated gradient case, we choose ζ λ " Opωϵ 2{ψ q and ζ υ " Opω 3 ϵ 2{ψ q.Exact Gradients Estimated Gradients 1 .ψ"1 (GD) ψPp1,2q ψ"2 (PL) ψ"1 (GD) ψPp1,2q ψ"2 (PL) Fixed ω ω ´1ϵ ´1 ω ´1ϵ ´2 ψ `1 ω ´1logpϵ ´1q ω ´3ϵ ´3logpϵ ´1q ω ´3ϵ ´4 ψ `1logpϵ ´1q ω ´3ϵ ´1logpϵ ´1q ω"Opϵq ϵ ´2 ϵ ´2 ψ ϵ ´1logpϵ ´1q ϵ ´6logpϵ ´1q ϵ ´4 ψ ´2logpϵ ´1q ϵ ´4logpϵ ´1qAssuming ω to be a constant, we observe that both learning rates display the same dependence on ϵ 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 ω " Opϵq, leading to a two-time scales algorithm. Fourth, we observe that, for both exact and estimated gradients, the sample complexity degrades as the constant ψ 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 ( 1); (ii) delivers a last-iterate guarantee; (iii) has no dependence on the cardinality of the state or action spaces, making it completely dimension-free. Table 1 and Figure 1 summarize the results of Theorem 3.2.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
action-based and parameter-based primal-dual algorithms: 
 In this section, we 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 applicability space of C-PG. This is done by employing a parametric unified risk measure formulation, which leads to having a framework for solving risk-constrained problems via policy-based primaldual methods operating in both the action-based and parameter-based PGs exploration scenarios. Moreover, this framework allows to handle constraints enforced on several risk measures, which will be discussed below. We first introduce a parametric unified risk measure and formulate an exploration-agnostic RCOP (Section 4.1). Then, we present both C-PGAE and C-PGPE (Section 4.2).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 π θ w.r.t. the i-th cost, with i P 0, U , given two functions f i : R 2 Ñ R and g i : R Ñ R, we define the AB-risk measure as: min ηiPR J A,i pθ, η i q where J A,i pθ, η i q :" E τ "pAp¨|θq rf i pC i pτ q, η i qs `gi pη i q.(9)Similarly, for the PB case, to assess the performance of hyperpolicy ν ρ w.r.t. the i-th cost, with i P 0, U , we define the PB-risk measure as: min ηiPR J P,i pρ, η i q where J P,i pρ, η i q :" E θ"νρ r Eτ "pAp¨|θq rf i pC i pτ q, η i qss `gi pη i q.(10) Some observations are in order. First, by selecting the functions f i and g i , 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 η i . 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 η i with the primal variables υ of the COP without changing the optimum. Finally, let us appreciate the semantic 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 π θ and the environment, for PB we have the joint stochastic process of the hyperpolicy ν ρ , policy π θ (when stochastic), and theParameter Need for η f i pC i pτ q, ηq g i pηq AB GPOMDP-like Estimator J :,0 pυ, η 0 q s.t. J :,i pυ, η i q ď b i , @i P U ,Expected Cost - ✗ C i pτ q 0 Yes Mean Variance κ ✓ p1 ´2κηqC i pτ q `κC i pτ q 2 κη 2 Partial CVaR α α ✓ 1 1´α pC i pτ q ´ηq `η No Chance n ✗ 1 tC i pτ q ě nu 0 Nowhere : P tA, Pu, υ P V is the parameter and η " pη 1 , . . . , η U q P R U are the auxiliary variables.As for the COP of Equation (1), we define the regularized Lagrangian function for the RCOP (Equation 11) as follows:EQUATIONwith : P tA, Pu. We assume that r L :,ω is differentiable w.r.t. υ and subdifferentiable7 w.r.t. η, while, by construction, it is already differentiable w.r.t. λ. Remark 4.1 (Do the Convergence Guarantees of Section 3 Apply to the RCOP?). When all the f i and g i are selected in order to consider the expected values of the corresponding C i (i.e., f i pC i pτ q, η i q " C i pτ q and g i pη i q " 0), then r L :,ω coincides with L ω , thus, all the theoretical results presented in Section 3 hold. This is not true in general. For some risk measures r L :,ω may not be smooth or even differentiable in υ or η, 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 an appealing future research direction.Algorithms. Both algorithms, whose pseudo-codes are deferred to Appendix A, aim at solving the RCOP of Equation ( 11), finding the best feasible (hyper)policy parameterization. The alternate ascent/descent primal-dual prototypical algorithm is the same as described in Section 3. In particular, at each iteration k P K , the algorithms collect N trajectories (employing the chose exploration paradigm) to update the primal and dual variables as:Primal Updates 7 Dual Update υ k`1 Ð Ý υ k ´ζυ,k p ∇ υ r L :,ω pυ k , λ k , η k q λ k`1 Ð Ý λ k `ζλ,k p ∇ λ r L :,ω pυ k`1 , λ k , η k`1 q, η k`1 Ð Ý η k ´ζη,k p ∇ η r L :,ω pυ k , λ k , η k qwhere the values are considered to be projected into their spaces, and ζ υ,k , ζ λ,k , ζ η,k ą 0 are the learning rates at the k-th iteration for υ, λ, and η, respectively. Notice that, since we use alternate ascent/descent, the update for λ k`1 uses the updated primal values υ k`1 and η k`1 . In practice, this requires collecting a first batch of N {2 trajectories using the (hyper)policy υ k to perform the primal updates, computing υ k`1 and η k`1 . Then, it is necessary to collect a new batch of N {2 trajectories using the updated (hyper)policy υ k`1 in order to perform the dual update, computing λ k`1 , which also leverages η k`1 .Estimators. Here, we provide the risk-agnostic form of the estimators used to perform the primal and dual updates. In particular, the gradient of r L :,ω with respect to η is closely related to the choices of f i and g i . 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 r L :,ω w.r.t. λ has the same form for both C-PGAE and C-PGPE, that is:EQUATIONwhere the trajectories are collected with the AB or the PB exploration paradigm , f pCpτ q, ηq :" pf 1 pC 1 pτ q, η 1 q , . . . , f U pC U pτ q, η U qq J and gpηq :" pg 1 pη 1 q, . . . , g U pη U qq J .C-PGAE (Algorithm 1) is the action-based version of C-PG. At each iteration k P K , the agent collects N trajectories by playing the policy π θ k , then it alternatively updates the policy parameter θ and the risks parameter η, or the Lagrange multipliers λ. The θ update relies on the estimator:p ∇ θ r L A,ω pθ k ,λ k ,η k q:" 1 N N ÿ i"1 ´T ´1 ÿ t"0 ∇ θ logπ θk pa τi,t |s τi,t q ¯´f 0 pC 0 pτ i q,η k,0 q `U ÿ u"1 λ k,u pf u pC u pτ i q,η k,u qq ¯,which reduces to the prototypical action-based algorithm REINFORCE (Williams, 1992) in the risk-neutral case. When allowed by the choice of f i , we switch to a GPOMDP-style estimator (Baxter and Bartlett, 2001) which suffers less variance. See Appendix D for details.C-PGPE (Algorithm 2) is the parameter-based version of C-PG. At each iteration k P K , the algorithm samples N parameter configurations tθ i u iP N from the hyperpolicy ν ρ k , then collects a single trajectory τ i , obtained by playing the policy π θi , for each sampled parameterization θ i . The sampled trajectories and parameters are then used to alternatively update the hyperpolicy parameter vector ρ and the risks parameter vector η, or the vector of Lagrange multipliers λ. In particular, the ρ update relies on the following estimator:p ∇ ρ r L P,ω pρ k , λ k , η k q :" 1 N N ÿ i"1 ∇ ρ log ν ρ k pθ i q ´f0 pC 0 pτ i q, η k,0 q `U ÿ u"1 λ u f u pC u pτ i q, η k,u q ¯,which reduces to the parameter-based algorithm PGPE (Sehnke et al., 2010) in the risk-neutral case. 
numerical validation: 
 In this section, we empirically validate some of the theoretical results shown throughout this work. Experimental details and additional results are provided in Appendix H. The code to run the experiments in this paper is available at https://github.com/MontenegroAlessandro/MagicRL.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 a 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 Op|S| `|S||A|q 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-critic methods were very sentitive to the hyperparameters selection, especially the length and the step size of the inner loop (see Appendix H). ¨10 5 2 ¨10 5 3 ¨10 5 4 ¨10 5 5 ¨10 5 6 ¨10 Risk constraints on Swimmer. In Figure 3 , we show the empirical distributions of costs over 100 trajectories of the learned (hyper)policies via C-PGPE and C-PGAE. This experiment considers the cost-based version of the Swimmer-v4 MuJoCo (Todorov et al., 2012) environment, with a single constraint over the actions (see Appendix H), for which we set b " 50. The experimental results show that C-PGPE learns a hyperpolicy paying less cost when using risk measures compared to average cost, with the smallest costs attained by CVaR α . C-PGAE shows similar results, although the difference between CVaR α or the Chance constraints and average cost constraints are not very significant. Notice that, the minimum amount of cost is obtained using MV constraints even if the learned policy exhibits poor performances (Table 3c ). In all the other cases, both C-PGPE and C-PGAE learns (hyper)policies exhibiting similar performance scores.5 ´15 ´10 ´5 Trajectories Average Trajectory Return C-PGAE C-PGPE NPG-PD2 RPG-PD2 0 1 ¨10 5 2 ¨10 5 3 ¨10 5 4 ¨10 5 5 ¨10 5 6 ¨10 5 0 0.2 0.4 0.6 Trajectories Average Trajectory Cost C-PGAE C-PGPE NPG-PD2 RPG-PD2 b (b) CostLQR. 
conclusions: 
 In this work, we proposed a general framework to address continuous CRL problems via primal-dual policy-based algorithms, leveraging on an alternate ascent-descent approach. Our explorationagnostic 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, the 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 a single time-scale.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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.• 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), fairness 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 not tied to particular applications, let alone deployments. However, if there is a 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 as 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 not use 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 is used and, if 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.• 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. 
 
 Appendix: Algorithm 1: C-PGAE.Input :Iterations K; batch size N ; regularization ω; initial parameters: θ0, λ0, and η0; (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.step sizes: ζ θ,k , ζ λ,k , ζ η,k . 1 for k P K do 2 Collect N trajectories tτiu iP N with π θ k´1 3 if k is odd then 4 θk Ð Ý θk´1 ´ζθ,k´1 p ∇θ r LA,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 unconstrained 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 Ding et al., , 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 et 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 et 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 a 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-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-scale 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-based 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 occupancy-measure 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 dimension-dependent average-iterate global convergence guarantees in the single-constrained setting with a single time-scale and with exact gradients. This work has been extended by Ding et 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 a convergence rate of order Õpϵ ´1q, considering to act in tabular CMDPs with softmax policies and having access to exact graidents and to a generative model. Liu et al. (2021) propose also a sample-based version of their algorithm, keeping the same setting previously described, which ensures a convergence rate on average of order Õpϵ ´3q. 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 a singleconstraint 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 dimension-dependent rates and both leverage on exact gradients. However, for Risk-Constrained Reinforcement Learning. For safety-critical problems, it is often insufficient to consider constraints solely on expected costs or utilities. Therefore, constraints are sometimes applied to risk measures over cost or utility functions (Chow and Pavone, 2013; Borkar and Jain, 2014; Chow et al., 2017; Zhang et al., 2024) . The employed risk measures are those most commonly applied in risk-averse RL (Tamar et al., 2014; Bisi et al., 2020 Bisi et al., , 2022;; Luo et al., 2023) 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 F Z p¨q as the cumulative distribution function. Formally:E r|Z|s ă `8 and F Z pzq " PpZ ď zq. ( 14) For what follows, let such a random variable represent a loss.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 J AC,i and J PC,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, it is possible to consider the Mean-Variance (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 κ over the random variable Z, which represents a loss, is defined as follows:MV κ pZq :" E rZs `κ Var rZs . VaR α measures risk as the maximum cost that might be incurred with respect to a given confidence level α P p0, 1q. Such a quantity models the potential loss and the probability that the loss will occur.In its classical definition, the VaR α is the worst-case loss associated with a probability and a time horizon. This risk metric is particularly useful when there is a well defined failure state. Formally: VaR α pZq :" min tz|F Z pzq ě αu .CVaR α measures risk as the expected cost given that such cost is greater than or equal to VaR α , and provides a number of theoretical and computational advantages. Such a quantity represents the expected loss if the worst-case threshold is passed (i.e., beyond the VaR α breakpoint). Formally:EQUATIONAnother 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 are imposed on the probability that the loss random variable exceeds a certain threshold n:Chance n pZq :" PpZ ě nq.(18)Here we introduce an objective for writing an optimization problem for different risk measures (Bisi et al., 2022) . For every i P 0, U , we introduce the functions f i : R 2 Ñ R and g i : R Ñ R in order to express the unified risk-minimization objective function over a risk measure on C i as:EQUATION)Thus, by fixing a policy parameter configuration θ, we obtain an AB unified risk measure over C i as follows:EQUATION)In order to switch to the PB exploration paradigm, we need to consider also the expectation over the parameter configuration of the underlying policy. Indeed, by fixing a hyperparameter configuration ρ, we can define:EQUATION)By selecting the functions f i and g i we can consider distinct risk measures to minimize, as we show in Table 4 .The focus of this section is to derive the mapping between the functions f and g and the desired risk measure as shown in Table 4 . In particular, we consider just the AB exploration scenario, since then passing to the PB one is straightforward. In this section, we consider a generic cost function c : S ˆA Ñ r0, 1s with its cumulative cost index over a trajectory τ which is Cpτ q " ř T ´1 t"0 γ t cps τ,t , a τ,t q. In what follows, with a little abuse of notation, we will write the risk measures with also a dependence on the policy parameters θ which induce trajectories τ .Mean Cost. This is the simplest case, indeed, we can express the minimization problem of the mean cost as:EQUATIONThus, it suffices to select f pCpτ q, ηq " Cpτ q and gpηq " 0 to make the minimization problem fit with the form of the unified cost minimization formulation.Conditional Value at Risk. For what concern the CVaR α , we can start from its formulation:EQUATION)Thus, we need to select f pCpτ q, ηq " 1 1´α pCpτ q ´ηq `and gpηq " η to complete the mapping to the unified cost minimization objective.Mean Variance. For the MV κ pθq objective, we need to make some preliminary observations. In particular, for a generic finite-mean random variable X, we have that:EQUATIONMoreover, by Fenchel duality, we have the following:EQUATION)Given that, we can start the derivation from the minimization of the Mean Variance:EQUATION"EQUATION)Thus, to complete the mapping, we need to select f pCpτ q, ηq " p1 ´2κηqE τ "pAp¨|θq rCpτ qs `κ E τ "pAp¨|θq " Cpτ q 2 ‰and gpηq " κη 2 .Chance. For characterizing the chance constraints, we start by expressing the probability of an event A as the expected value of the indicator function:EQUATIONThus, having to minimize a chance measure on the cost with a parameter n, we can rewrite it as:EQUATIONThus, to complete the mapping to the unified cost minimization objective, it suffices to select f pCpτ q, ηq " 1 tCpτ q ě nu and gpηq " 0.Here, we 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 f i and g i functions and the risk measures in Table 4 .Risk Measure Parameter Need for η f i pC i pτ q, ηq g i pηq AB GPOMDP-like EstimatorExpected Cost - ✗ C i pτ q 0 Yes Mean Variance κ ✓ p1 ´2κηqC i pτ q `κC i pτ q 2 κη 2 Partial CVaR α α ✓ 1 1´α pC i pτ q ´ηq `η No Chance n ✗ 1 tC i pτ q ě nu 0 NoTable 4 : Mapping between f i and g i and the cost measures.The general Lagrangian function for the problem in Equation ( 11) is the following:EQUATION)For what follows we are going to compute the following gradients:1. ∇ υ r L :,ω pυ, λ, ηq; 2. ∇ λ r L :,ω pυ, λ, ηq; 3. ∇ η r L :,ω pυ, λ, ηq.Before entering into the details of the estimators, we show the general forms of the gradients of the Lagrangian.General Gradient w.r.t. υ. Notice that the following holds:EQUATIONthus, in what follows, for the gradient w.r.t. υ we focus on the single terms ∇ υ J :,u pυ, η u q for every u P 0, U .General Gradient w.r.t. λ. The general gradient w.r.t. λ has the form:EQUATIONwhere J : pυ, ηq " pJ :,1 pυ, η 1 q, ..., J :,U pυ, η U qq J and b " pb 1 , ..., b U q J .General Gradient w.r.t. η. As done for the gradient w.r.t. υ, the following holds:EQUATION)Thus, also in this case, we will focus on the single terms ∇ η J :,u pυ, η u q for every u P 0, U .In the following we consider a generic hyperpolicy ν ρ and a generic parameterization ρ. Before starting with the derivations, we report the definition of J P,i pρ, η i q:EQUATIONfor every i P 0, U .The first step of the derivation can be done via the log-trick for the parameter-based exploration paradigm as stated by Sehnke et al. (2010) :EQUATION)To switch to 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:p ∇ ρ J P,i pρ, η i q " 1 N N ÿ j"1∇ ρ log ν ρ pθ j qf i pC i pτ j q, η i q.(42)Thus, to obtain the estimators for all the risk measures, it suffices to map the selection of the f i functions in Equation (42).Given the general gradient w.r.t. λ of the regularized Lagrangian r L P,ω in the parameter-based scenario, the partial derivative w.r.t. λ i is the following:EQUATIONThis is defined for any i P U .In order to switch to the sample-based version of the partial derivative, we consider the behavior of C-PGPE as described in Section 4. In particular, we have the following:p ∇ λi r L P,ω pρ, λ, ηq " 1 N N ÿ j"1f i pC i pτ j q, η i q `gi pη i q ´bi `ωλ i .(44)Thus, to obtain the estimator for all the risk measures, it suffices to map the choices of f i and g i in Equation (44).For what concern the gradients w.r.t. η, we 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 η. As shown at the beginning of this section, we can just focus on the terms ∇ η J P,i pρ, η i q, and in particular on the partial derivative ∇ ηi J P,i pρ, η i q, that exhibits the common form:EQUATION)Mean Variance. In this case we have that f i pC i pτ q, η i q " p1 ´2κ i η i qC i pτ q `κi C i pτ q 2 and that g i pη i q " κ i η 2 i . Thus, from Equation ( 46), we get the following:EQUATION)Considering the behavior of C-PGPE described in Section 4, we obtain the following sample-based version:EQUATION)Conditional Value at Risk. In this case we have that f i pC i pτ q, η i q " 1 1´αi pC i pτ q ´ηi q `and that g i pη i q " η i . As also shown by Chow et al. (2017) , due to the presence of the non-differentiable term p¨q `, we need to resort to sub-differentiability theory. The following holds:EQUATION)Thus, from Equation ( 46), we can write what follows:EQUATIONwith q P r0, 1s.In particular, for q " 1, we obtain the following partial derivative:EQUATIONFinally, according to the C-PGPE behavior described in Section 4, we obtain the following samplebased version:p B ηi J P,i pρ, η i q " 1 N N ÿ j"11 tC i pτ j q ě η i u `1.(55)With a little abuse of notation, we will use p ∇ ηi J P,i pρ, η i q " p B ηi J P,i pρ, η i q for the η update in the case in which the CVaR α risk measure is employed.In the following we consider a generic policy π θ and a generic parameterization θ. Before starting with the derivations, we report the definition of J A,i pθ, η i q:J A,i pθ, η i q :" E τ "pAp¨|θq rf i pC i pτ q, η i qs `gi pη i q, (56)for every i P 0, U .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) :EQUATION)To switch to the sample-based versions of all the gradients, we generally resort to the Monte Carlo version of ∇ θ J A,i pθ, η i q, obtaining a REINFORCE-like (Williams, 1992) estimator, that is:p ∇ θ J A,i pθ, η i q " 1 N N ÿ j"1 ˜T ´1 ÿ t"0∇ θ log πpa τj ,t , s τj ,t q ¸fi pC i pτ j q, η i q.(60)Thus, to obtain the estimators for all the risk measures, it suffices to map the selection of the f i functions in Equation ( 60).It is worth noticing that some of the choices for f i and g i allow to switch to a GPOMDP-like (Baxter and Bartlett, 2001) estimator, which suffers from less variance. This holds for the expected cost and mean variance risk measures.Expected Cost GPOMDP-like Estimator. In this case f i pC i pτ q, η i q " C i pτ q, thus we can obtain exactly the GPOMDP estimator:EQUATION)Mean Variance GPOMDP-like Estimator. In this case f i pC i pτ q, η i q " p1 ´2κ i η i qC i pτ q κi C i pτ q 2 , thus we can obtain the GPOMDP estimator just for the C i pτ q part:p ∇ θ J A,i pθ, η i q (62) " 1 N N ÿ j"1 ˜T ´1 ÿ t"0∇ θ log πpa τj ,t , s τj ,t q ¸`p1 ´2κ i η i qC i pτ j q `κi C i pτ j q 2 ˘( 63)" 1 ´2κ i η i N N ÿ j"1 ˜T ´1 ÿ t"0 γ t c i ps τj ,t , a τj ,t q t ÿ h"0 ∇ θ log πpa τj ,h , s τj ,h q ¸(64) `κi N N ÿ j"1 ˜T ´1 ÿ t"0∇ θ log πpa τj ,t , s τj ,t q ¸Ci pτ j q 2 . (65)The result is the same as 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. λ i is:EQUATIONTo obtain the estimator for all the risk measures, it suffices to map the choices of f i and g i as prescribed by Table 4 .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 η, thus they are not treated. As shown at the beginning of the section, we can just focus on the ∇ η J A,i pθ, η i q terms and, in particular, we consider the partial derivative ∇ ηi J A,i pθ, η i q. For it, we can recover the common form: ∇ ηi J A,i pθ, η i q " E τ "pAp¨|θq r∇ ηi f i pC i pτ q, η i qs `∇ηi g i pη i q.(67)Mean Variance. In this case we have that f i pC i pτ q, η i q " p1 ´2κ i η i qC i pτ q `κi C i pτ q 2 and that g i pη i q " κ i η 2 i . Thus, from Equation (67), the following holds:EQUATIONConsidering the behavior of C-PGAE described in Section 4, we obtain the following sample-based version:EQUATIONConditional Value at Risk. In this case we have that f i pC i pτ q, η i q " 1 1´αi pC i pτ q ´ηi q `and that g i pη i q " η i . Here we face the same issues we have discussed in the corresponding C-PGPE part. With the same procedure, we obtain the following partial derivative:EQUATIONFinally, according to the C-PGAE behavior described in Section 4, we obtain the following samplebased version:EQUATIONAlso in this case, we will use p ∇ ηi J A,i pρ, η i q " p B ηi J A,i pρ, η i q for the η update in the case in which the CVaR α risk measure is employed.Lemma E.1 (Regularization Bias on Saddle Points -1). Under Assumption 3.1, for every ω ě 0, let pυ ω , λ ω q be a saddle point of L ω , it holds that:0 ď L 0 pυ 0 , λ 0 q ´L0 pυ ω , λ ω q ď ω 2 `}λ 0 } 2 2 ´}λ ω } 2 2 ˘.Proof. From the fact that pυ ω , λ ω q is a saddle point of L ω , we have for every υ P V and λP Λ:EQUATIONEQUATION)From the fact that pυ 0 , λ 0 q is a saddle point of L 0 , we have for every υ P V and λP Λ: L 0 pυ, λ 0 q ěL 0 pυ 0 , λ 0 q ě L 0 pυ 0 , λq.(75) By setting pυ, λq Ð pυ ω , λ ω q in Equation ( 75) and pυ, λq Ð pυ 0 , λ 0 q in Equation (74), we obtain: L 0 pυ ω , λ 0 q ě L 0 pυ 0 , λ 0 q ě L 0 pυ 0 , λ ω q (76)EQUATIONthus:EQUATION)Lemma E.2 (Regularization Bias on Saddle Points -2). Under Assumption 3.1, for every ω ě 0, it holds that:0 ď min υPV max λPΛ L 0 pυ, λq ´min υPV max λPΛ L ω pυ, λq ď ω 2 }λ 0 } 2 2 .Proof. The first inequality follows from the observation that L 0 pυ, λq ě L ω pυ, λq for every ω ě 0.For the second inequality, let us denote as pυ ω , λ ω q the saddle point for L ω and let Λ ˚" tλ 0 , λ ω u.We have: L 0 pυ 0 , λ 0 q ´Lω pυ ω , λ ω q " min υPV max " ω 2 maxEQUATIONwhere we used Lemma E.1 to conclude that }λ 0 } 2 2 ě }λ ω } 2 2 . Lemma E.3 (Objective bound and Constraint violation). Under Assumption 3.1, for every ω ě 0, letting pυ ω , λ ω q be a saddle point of L ω , it holds that: 0 ď J 0 pυ 0 q ´J0 pυ ω q ď ω}λ 0 } 2 2 , (85) }pJpυ ω q ´bq `}2 ď ω}λ 0 } 2 .(86)Proof. Since pυ 0 , λ 0 q is a saddle point of L 0 , it holds that υ 0 is feasible and, consequently, L 0 pυ 0 , λ 0 q " J 0 pυ 0 q. Moreover, let ω ą 0: since pυ ω , λ ω q is a saddle point of L ω it holds that λ ω " λ ˚pυ ω q " Π Λ `1 ω pJpυ ω q ´bq ˘" 1 ω pJpυ ω q ´bq `, since 1 ω }pJpυ ω q ´bq `}2 ď ω ´1? U J max . Thus, we have: L 0 pυ ω , λ ω q " J 0 pυ ω q `xλ ω , Jpυ ω q ´by " J 0 pυ ω q `1 ω }pJpυ ω q ´bq `}2 2 .(87)From Lemma E.1, we have:EQUATIONBy summing 1 ω }pJpυ ω q ´bq `}2 2 to all members, we have:EQUATIONNow taking the first and last member, we conclude:EQUATION)Since 1 ω }pJpυ ω q ´bq `}2 2 ě 0 and plugging the latter inequality into the third member of (89) we obtain: 0 ď J 0 pυ 0 q ´J0 pυ ω q ď ω}λ 0 } 2 2 .(91)Lemma E.4 (Weak ψ-Gradient Domination on H ω pυq). Under Assumption 3.2, if ω ą 0, for every υ P V and λP Λ, it holds that:EQUATIONProof. If ω ą 0, the dual variable exist finite since the maximization problem over λ is concave:λ ˚pυq " arg max λPΛ L ω pυ, λq.Thus, we have from Lemma E.7 that∇ υ H ω pυq " ∇ υ L ω pυ, λq| λ"λ ˚pυq and by Assumption 3.2 we have the following:EQUATION" α 1 pH ω pυq ´Hω q ´β1 . (96)Lemma E.5. Let ω ą 0 and υ P V. The following statements hold:• L ω pυ, ¨q is ω-smooth, i.e., for every λ, λ 1 P Λ it holds that:ˇˇ∇ λ L ω pυ, λ 1 q ´∇λ L ω pυ, λq ˇˇď ω › › λ ´λ1 › › 2 2• L ω pυ, ¨q satisfies the PL condition, i.e., for every λP Λ it holds that:}∇ λ L ω pυ, λq} 2 2 ě ω ˆmax λ 1 PΛL ω pυ, λ 1 q ´Lω pυ, λq ˙.• L ω pυ, ¨q satisfies the error bound (EB) condition, i.e., for every λ, λ 1 P Λ it holds that:}∇ λ L ω pυ, λq} ě ω 2 }λ ˚pυq ´λ} 2 ,where λ ˚pυq " arg max λPΛ L ω pυ, λq.• L ω pυ, ¨q satisfies the quadratic growth (QG) condition, i.e., for every λ, λ 1 P Λ it holds that:H ω pυq ´Lω pυ, λq ě ω 4 }λ ˚pυq ´λ} 2 ,where λ ˚pυq " arg max λPΛ L ω pυ, λq.Proof. For the first property, it is enough to observe that L ω is twice differentiable in λ and that its Hessian is ωI. For the second property, we observe that L ω is quadratic in λ and, consequently it satisfies the PL condition with parameter ω:}∇ λ L ω pυ, λq} 2 2 ě ω ˆmax λ 1 PR U L ω pυ, λ 1 q ´Lω pυ, λq ˙ě ω ˆmax λ 1 PΛL ω pυ, λ 1 q ´Lω pυ, λq ˙.For the third and fourth properties, we refer to Lemma A.1 of Yang et al. (2020) .Lemma E.6. Let ω ą 0. For every υ P V, it holds that:EQUATIONProof. Let us consider the following derivation: H ω pυq ´Hω " H ω pυq ´Lω pυ ω , λ ω q (98) ě H ω pυq ´Lω pυ, λ ω q (99)EQUATION)having exploited the fact that, from the saddle point property, L ω pυ ω , λ ω q ď L ω pυ, λ ω q and, then, Lemma E.5.Lemma E.7. Let ω ą 0. The following statements hold:• H ω is L H -smooth, i.e., for every υ, υ 1 P V, it holds that:}∇ υ H ω pυ 1 q ´∇υ H ω pυq} 2 ď L H }υ 1 ´υ} 2 .where L H :" L 2 `L21 ω . • For every υ, υ 1 P V we have ∇ υ H ω pυq " ∇ υ L ω pυ, λq| λ"λ ˚pυq , where λ ˚pυq " arg max λPΛ L ω pυ, λq.Proof. The first and second statements follow from Lemma A.5 of Nouiehed et al. (2019) .Theorem 3.1 (Objective Function Gap and Constraint Violation). Let ϵ ą 0. Under Assumption 3.1, if P k ď ϵ, it holds that:ErJ 0 pυ k q ´J0 pυ 0 qs ď ϵ `ω 2 }λ 0 } 2 2 , ErpJ i pυ k q ´bi q `s ď 4ϵ `ω}λ 0 } 2 , @i P U . (8)Proof. Since P k ď ϵ, it follows that a k ď ϵ and, consequently, 0 ď ErH ω pυ k q ´Hω s ď ϵ. We start by bounding the norm of the dual variables:EQUATION)where we applied the triangular inequality and Lemma E.6. The projection Π Λ is such that λ ˚pυq " Π Λ `1 ω pJpυq ´bq ˘" 1 ω pJpυq ´bq `and, consequently, we have: }pJpυ k q ´bq `}2 ´}pJpυ ω q ´bq `}2 ď 4pH ω pυ k q ´Hω q.(103) By the last inequality, together with Lemma E.3, having applied the expectation on both sides:Er}pJpυ k q ´bq `}2 s ď }pJpυ ω q ´bq `}2 `4 ErH ω pυ k q ´Hω s (104) ď ω}λ 0 } 2 `4ϵ.(105) Recalling that:EQUATIONFor the objective function bound, let us consider the following derivation. By definition of H ω pυq and λ ˚pυq we have:EQUATION)Taking the expectation on both sides and upper bounding }λ ω } with }λ 0 } from Lemma E.1:EQUATION)The result is obtained by applying Lemma E.3 as follows:ErJ 0 pυ k q ´J0 pυ 0 qs " ErJ 0 pυ k q ´J0 pυ ω qs `J0 pυ ω q ´J0 pυ 0 q looooooooomooooooooon ď0 .Theorem 3.2 (Convergence of P K ). Under Assumptions 3.2, 3.3, 3.4, for χ ă 1{5, sufficiently small ϵ and ω, and a choice of constant learning rates ζ υ , ζ λ , we have P K pχq ď ϵ `β1 {α 1 whenever:8 • K " Opω ´1 logpϵ ´1qq if ψ " 2 and the gradients are exact (i.e., V υ " V λ " 0);• K " Opω ´1ϵ ´2 ψ ´1q if ψ P r1, 2q and the gradients are exact (i.e., V υ " V λ " 0);• K " Opω ´3ϵ ´4 ψ `1q if ψ P r1, 2s and the gradients are estimated (i.e., V υ " Opω ´2q and V λ " Op1q).Proof. The proof is subdivided into several parts. We will omit the ω subscript for notational easiness.Let us focus on a specific iteration k P N.Part I: bounding the a k term. Let us start with the a k term:EQUATION)where the first line is due to the fact that the function H ω is L H -smooth (Lemma E.7), the last inequality is due to the update rule of υ. Now, we apply the expected value on both sides of the inequality and we use the fact that the gradient estimation is unbiased and has variance bounded by V υ :EQUATION)where F k´1 is the filtration associated with all events realized up to interaction k ´1. We recall that:EQUATIONand that Var " p ∇ υ L ω pυ k , λ k q ı ď V υ by Assumption 3.4. Thus, selecting ζ υ,k ď 1{L H , we have that:EQUATION)Consider that:ζ υ,k 2 }∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q `∇υ H ω pυ k q} 2 2 (123) " ζ υ,k 2 }∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q} 2 2 ´ζυ,k 2 }∇ υ H ω pυ k q} 2 2 (124) `ζυ,k ⟨∇ υ L ω pυ k , λ k q, ∇ υ H ω pυ k q⟩ .(125) Thus, the following holds:EQUATIONThus, we have obtained:EQUATIONholding via the selection of ζ υ,k ď 1{L H . Notice that, from A ⃝ the following directly follows:EQUATION)Part II: bounding the b k term. We are ready to analyze the b k term. Recall that for ridge regularization of the Lagrangian function presented in the main paper, we have that L ω is ω-smooth and fulfills the PL condition with constant ω, as shown in Lemma E.5. Since L is a quadratic function of λ and λ ˚pυ k`1 q P Λ, we have that considering the non-projected λ k`1 can only increase the distance. Thus, we will ignore projection for the rest of the proof. We have:EQUATION)that is possible under Assumption 3.3 (i.e., L ω is L 2 -smooth) and due to the update rules we are considering. Now, by applying the expectation on both sides, we obtain the following:EQUATION)where the last line follows by selecting ζ λ,k ď 1{ω. Since L ω enjoys the PL condition w.r.t λ with constant ω, for every pair pυ, λq we have:EQUATION)By applying the PL condition:EQUATIONwhere we enforce 1 ´ζλ,k 2 ω ě 0, i.e., ζ λ,k ď 2{ω. However, we do not have a proper recursive term, thus consider the following:EQUATION)A bound on D ⃝ has already been derived, so let us bound the term C ⃝:EQUATION)again because of Assumption 3.3 and the update rule. Now, as usual, we consider the expectation conditioned to the filtration F k´1 and the properties of the variance, to obtain:EQUATIONhaving set ζ υ,k ď 1{L 2 . We are finally able to conclude the bound of the term B ⃝:EQUATION)Now we apply the bounds on C ⃝ and D ⃝ (the latter is from Eq. 136), obtaining:E rH ω pυ k`1 q ´Lω pυ k`1 , λ k`1 q|F k´1 s (164) ď ˆ1 ´ζλ,k 2 ω ˙pH ω pυ k q ´Lω pυ k , λ k qq (165) `ˆ1 ´ζλ,k 2 ω ˙ˆζ υ,k ˆ1 `L2 2 ζ υ,k ˙}∇ υ L ω pυ k , λ k q} 2 2 `L2 2 ζ 2 υ,k V υ ˙(166) `ˆ1 ´ζλ,k 2 ω ˙ˆ´ζ υ,k 2 }∇ υ H ω pυ k q} 2 2 `ζυ,k 2 }∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q} 2 2(167)EQUATIONthat is the second fundamental term.Part III: bounding the potential function P k pχq. Before going on, we recall that so far we enforced:ζ υ,k ď 1{L H (since L H ě L 2) and ζ λ,k ď 1{ω, for every t P K . What we want to bound here is the potential function P k`1 pχq " a k`1 `χb k`1 . Using the final results of Part I and Part II:EQUATIONEQUATIONEQUATION)Now we can re-arrange the terms by noticing that:}∇ υ L ω pυ k , λ k q} 2 2 " }∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q `∇υ H ω pυ k q} 2 2 (182) " }∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q} 2 2 (183) `}∇ υ H ω pυ k q} 2 2 `2 ⟨∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q, ∇ υ H ω pυ k q⟩ (184) ď 2 }∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q} 2 2 `2 }∇ υ H ω pυ k q} 2 2 ,(185) where the last inequality holds by Young's inequality. Then we can write what follows:EQUATIONEQUATIONEQUATION)Let us now proceed to bound}∇ υ L ω pυ k , λ k q ´∇υ H ω pυ k q} 2 2. By Lemma E.7, we have that ∇ υ H ω pυq " ∇ υ L ω pυ, λ ˚pυqq for every λ ˚pυq P arg max λPΛ L ω pυ, λq, thus we can write: For a fixed value of υ, by Lemma E.5 it follows that L ω pυ, ¨q satisfies the quadratic growth condition (since it satisfies the PL condition), for which the following holds:EQUATIONEQUATIONand thus we have:EQUATION)By applying the total expectation, it trivially follows:EQUATION)Thus, we have:EQUATIONEQUATIONPart IV: apply the ψ-gradient domination. Now we need to bound the term }∇H ω pυ k q} 2 2 . We consider Assumption 3.2 and we get: }∇ υ H ω pυ k q} ψ 2 ě α 1 pH ω pυ k q ´H˚q ´β1 . By defining r H ˚:" H ˚`β 1 {α 1 , we also have:}∇ υ H ω pυq} ψ 2 ě α 1 max ! 0, H ω pυq ´r H ˚) (204) ùñ }∇ υ H ω pυq} 2 2 ě α 2 ψ 1 max ! 0, H ω pυq ´r H ˚) 2 ψ .If we apply the total expectation on both sides of the inequality, we get:EQUATIONwhich is achieved by a double application of Jensen's inequality, since z 2{ψ is convex for ψ P r1, 2s and z ě 0, and the maximum is convex. Let us start from Equation ( 198):EQUATIONEQUATION)We first enforce the negativity of ´C. To this end:EQUATIONEQUATIONThus, it is enough to enforce 5χ ´1 ď 0 ùñ χ ď 1{5. We now plug in the gradient domination inequalities:a k`1 `χb k`1 (217) ď a k `χ ˆ1 ´ζλ,k 2 ω ˙bk ´Cα 2 ψ 1 max ! 0; E " H ω pυq ´r H ˚ı) 2 ψ `V (218) `ˆ2ζ υ,k ˆ1 `L2 2 ζ υ,k ˙χ ˆ1 ´ζλ,k 2 ω ˙`ζ υ,k 2 ˆ1 `χ ˆ1 ´ζλ,k 2 ω ˙˙˙4 L 2 3 ω b k . (219)Now we introduce the symbol r a k :" E " H ω pυ k q ´r H ˚ı " a k ´β1 {α 1 , to get:EQUATIONEQUATIONEQUATIONFor what follows, we call B the term that is multiplying b k :EQUATIONEQUATIONLet refer to r a k `χb k as r P t pχq with χ P p0, 1q. For the sake of clarity, we re-write our main inequality as:r P t pχq " r a k`1 `χb k`1 ď r a k `Bb k ´C max t0; r a k u 2 ψ `V.(226) Then, from Lemma F.1 having set a Ð r a k and b Ð χb k , we have:r P t`1 pχq " r a k`1 `χb k`1 ď r a k `Bb k `Cpχb k q 2 ψ ´21´2 ψ C max t0, r a k `χb k u 2 ψ `V. (227)By choosing χ so that χb k ď 1, i.e., χ ď 1{ max kPrKs b k , we have:EQUATION" r P t pB `χCq ´21´2 ψ C max ! 0, r P t pχqEQUATIONTo unfold the recursion, we need to ensure that B `χC ď χ, which leads to a condition relating the two learning rates:EQUATIONEQUATIONwhere we exploited ζ υ,k ď 1{L 2 and ζ λ,k ď 2{ω. Thus, we have:EQUATIONCollecting all conditions on the learning rates, we have:ζ υ,k ď min $ & % 1 L H , 1 L 2 , ω 2 χζ λ,k p1 `χqωα 2 ψ 1 `4L 2 3 p1 `7χq, .-EQUATION)EQUATIONAs a further simplification, let us observe that:EQUATIONEQUATIONEQUATIONDenoting with r C ":2 1´1 ψ ζ υ,k α 2 ψ 1 2, we are going to study the recurrence:EQUATIONPart V: Rates Computation Part V(a): Exact gradients We consider the case r V " 0. Let us start with ψ " 2. From Lemma G.3, we have:EQUATIONThe inequality on K holds under the conditions:EQUATIONζ υ,k ď min $ & % 1 L H , 1 L 2 , ω 2 χζ λ,k p1 `χqωα 2 ψ 1 `4L 2 3 p1 `7χq, .-" min$ & % 1 L 2 `L2 1 ω , ω 2 χζ λ,k p1 `χqωα 2 ψ 1 `4L 2 3 p1 `7χq, .-EQUATION)EQUATIONwhere 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:ζ λ,k " ω ´1, ζ υ,k " min $ & % 2 1`2 ψ ψα 2 ψ 1 r P 0 pχq 2 ψ ´1 , 1 L 2 `L2 1 ω , ωχ p1 `χqωα 2 ψ 1 `4L 2 3 p1 `7χq, .-" Opωq.Thus, the sample complexity becomes K " O `ω´1 log 1 ϵ ˘.Consider now ψ P r1, 2q. We have from Lemma G.3:EQUATIONholding under the same conditions as before. With the same choices of learning rates, we obtain the sample complexityK " O ´ω´1 ϵ ´2 ψ `1¯as sample complexity.Part V(b): Estimated gradients We consider r V ą 0. In this case, from Lemma G.5, we have:EQUATION)We enforce both terms to be smaller or equal to ϵ{2. With the first one, we can evaluate the sample complexity:EQUATIONRegarding the second one, we have:EQUATIONBy enforcing the relation between the two learning rates, we set ζ υ,k " Opω 2 ζ λ,k q. By enforcing the previous inequality, recalling that L 2 ď Opω ´1q and V υ ď Opω ´2q, we obtain ζ λ " Opωϵ 2{ψ q, from which ζ υ " Opω 3 ϵ 2{ψ q. Substituting these values into the sample complexity upper bound, we get (highlighting the terms possibly depending on ω):EQUATIONhaving bounded the sum at the denominator with the second addendum.Lemma F.1. Let a P R, b ě 0, and ψ P r1, 2s. It holds that:EQUATIONProof. Let us consider the following derivation:EQUATIONwhere the first inequality follows from px `yq2 ψ ď 2 2 ψ ´1px 2 ψ`y 2 ψ q for x, y ě 0, from Holder's inequality; the second inequality from observing that 2 1´2 ψ pa `bq2 ψ ´b 2 ψ ď p2 1´2 ψ ´1qb 2 ψ ď 0 for ´b ă a ď 0.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:EQUATION) for a ą 0, b ě 0, and ϕ P r1, 2s. To this end, we consider the helper sequence:EQUATIONThe line of the proof follows that of Montenegro et al. (2024) . Let us start showing that for sufficiently small a, the sequence ρ k upper bounds r k .Lemma G.1. If a ď 1 ϕρ ϕ´1 kfor every k ě 0, then, r k ď ρ k for every k ě 0.Proof. By induction on k. For k " 0, the statement holds since ρ 0 " r 0 . Suppose the statement holds for every j ď k, we prove that it holds for k `1:EQUATIONwhere the first inequality holds by the inductive hypothesis and by observing that the function f pxq " x ´a maxt0, xu ϕ is non-decreasing in x when a ď 1 ϕρ ϕ´1 k . Indeed, if x ă 0, then f pxq " x, which is non-decreasing; if x ě 0, we have f pxq " x ´ax ϕ , that can be proved to be non-decreasing in the interval " 0, paϕq ´1 ϕ´1 ı simply by studying the sign of the derivative. Thus, we enforce the following requirement to ensure that ρ k falls in the non-decreasing region:EQUATION)So does r k by the inductive hypothesis.Thus, from now on, we study the properties of the sequence ρ k . Let us note that, if ρ k is convergent, then it converges to the fixed-point ρ computed as follows:EQUATIONhaving retained the positive solution of the equation only, since the negative one never attains the maximum maxt0, ρu. Let us now study the monotonicity properties of the sequence ρ k .Lemma G.2. The following statements hold:• If r 0 ą ρ and a ď 1 ϕr ϕ´1 0 , then for every k ě 0 it holds that: ρ ď ρ k`1 ď ρ k .• If r 0 ă ρ and a ď 1 ϕρ ϕ´1 , then for every k ě 0 it holds that:ρ ě ρ k`1 ě ρ k .Proof. The proof is analogous to that of (Montenegro et al., 2024, Lemma F.3) .From now on, we focus on the case in which r 0 ě ρ, since, as we shall see later, the opposite case is irrelevant for the convergence guarantees. We now consider two cases: b " 0 and b ą 0.G.1 Analysis when b " 0From the policy optimization perspective, this case corresponds to the one in which the gradients are exact (no variance). Recall that here ρ " 0. We have the following convergence result. Lemma G.3. If a ď 1 ϕr ϕ´1 0 , r 0 ě 0, and b " 0 it holds that:EQUATIONProof. Since r 0 ě 0 " ρ, from Lemma G.2, we know that ρ k ě 0 and, thus, maxt0, ρ k u " ρ k . For ϕ " 1, we have: ρ k`1 " ρ k ´aρ k " p1 ´aqρ k " p1 ´aq k`1 ρ 0 " p1 ´aq k`1 r 0 .(277) For ϕ P p1, 2s, we have:EQUATION)We proceed by induction. For k " 0, the statement hold since ρ 0 " r 0 and r 0 ď pϕaq ´1 ψ´1 ď ppϕ ´1qaq ´1 ψ´1 from the condition on the learning rate. Suppose the thesis holds for j ď k, we prove it for k `1. ρ k`1 ď r 0 by monotonicity, and, from the inductive hypothesis:EQUATION" pϕakq ´1 ϕ´1 ´pϕapk `1qq ´1 ϕ´1 ´apϕakq ´ϕ ϕ´1 looooooooooooooooooooooooooooomooooooooooooooooooooooooooooon p˚q `pϕapk `1qq ´1 ϕ´1 . (280)We now prove that p˚q is non-positive:p˚q " ppϕ ´1qakq ´1 ϕ´1 ´ppϕ ´1qapk `1qq ´1 ϕ´1 ´appϕ ´1qakq ´ϕ ϕ´1 (281)EQUATIONhaving observed that:EQUATIONG.2 Analysis for b ą 0From the policy optimization perspective, this corresponds to the case in which the gradients are estimated, i.e., the variance is positive. In this case, we proceed considering the helper sequence:EQUATION)We show that the sequence η k upper bounds ρ k when ρ 0 " r 0 ě ρ.Lemma G.4. If r 0 ą ρ and a ď 1 ϕr ϕ´1 0 , then, for every k ě 0, it holds that η k ě ρ k .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. If a ď 1 ϕr ϕ´1 0 , r 0 ě 0, and b ą 0 it holds that:EQUATIONProof. By unrolling the recursion:EQUATIONH.1 Experimental Details H.1.1 Employed Policies and Hyperpolicies Linear Gaussian Policy. A linear parametric gaussian policy π θ : S ˆA Ñ ∆pAq with variance σ 2 samples the actions as a t " N pθ J s t , σ 2 I d S q, where s t is the observed state at time t and θ is the parameter vector.Tabular Softmax Policy. A tabular softmax policy π θ : S ˆA Ñ ∆pAq with a temperature constant τ is such that:EQUATIONwhere θ i,j is the parameter associated with the i-th state and the j-th action. Notice that the total number of parameters for this kind of policy is |S||A|.Linear Deterministic Policy. A linear parametric deterministic policy µ θ : S ˆA Ñ A samples the actions as a t " θ J s t , where s t is the observed state at time t and θ is the parameter vector.Gaussian Hyperpolicy. A parametric gaussian hyperpolicy ν ρ : R Ñ ∆pΘq with variance σ 2 samples the parameters θ for the underlying generic parametric policy π θ as θ t " N pρ, σ 2 I d R q, where ρ is the parameter vector for the hyperpolicy.Discrete Grid World with Walls. Discrete Grid World with Walls (DGWW) is a simple discrete environment we employed to compare 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) . DGWW is a grid-like bidimensional environment in which an agent can assume only integer coordinate positions and in which an agent can play four actions stating whether to go up, right, left, or down. The goal is to reach the center of 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 0. Around the goal state there is a "U-shaped" obstacle with an opening on the top side. In particular, when the agent lands in a state in which the wall is present, it receives a cost of 1, otherwise the cost signal is always equal to 0. In our experiments, we employed a DGWW environment of such a 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) is 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 a dynamical system governed by the following state evolution:EQUATIONwhere A P R d S ˆdS and B P R d S ˆdA .In the standard version of the environment, the reward is computed at each step as:EQUATIONwhereR P R d S ˆdS and Q P R d A ˆdA .We modified this version of the LQR environment introducing costs. In particular, in our CostLQR, the state evolution is treated as in the original case, while the reward at step t is computed as:EQUATIONwhere R P R d S ˆdS . Moreover, we added a cost signal c which is computed as follows at every time step t:EQUATIONwhereQ P R d A ˆdA .In our experiments, we consider a CostLQR environment whose main characteristics are reported in Table 5 .Additionally, we considered a uniform initial state distribution in r´3, 3s and the following matrices:A " B " 0.9 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: }a t ´min tmax ta t , a min u , a max u} 2 , (298) where a min and a max are respectively the bounds for the minimum and maximum value for each component of the action vector. Then, the action min tmax ta t , a min u , a max u is passed to the environment. In our experiment we consider Swimmer-v4 and Hopper-v4 MuJoCo environments, whose main features are summarized in Table 5 .EQUATION)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 is 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 a tabular softmax policy with 196 parameters, maximizing the trajectory reward while considering a single constraint on the average trajectory cost, for which we set a threshold b " 0.2. All the methods were run for K " 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, we employed ζ θ " 0.01 and ζ λ " 0.1, while for RPG-PD we selected ζ θ " 0.01 and ζ λ " 0.01. For C-PGAE and RPG-PD we used a regularization constant ω " 10 ´4. All the details about the experimental setting are summarized in Table 6 . We would like to stress that, as prescribed by the respective convergence theorems, we chose a two time-scales learning rate approach for C-PGAE and a 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-based 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.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 a ridgeregularized 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 ω " 10 ´4. The setting for this experiment considers a bidimensional LQR environment with a single cost over the provided actions (see Appendix H) and with a 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 b " 0.9. In particular, C-PGAE learns the parameters of a linear gaussian policy with a variance σ 2A " 10 ´3 and employing a learning rate schedule governed by the Adam scheduler (Kingma and Ba, 2015) with ζ θ,0 " 0.001 and ζ λ,0 " 0.01. C-PGPE learns the parameters of a gaussian hyperpolicy, with a variance σ 2 P " 10 ´3, which samples the parameters of a deterministic linear policy. 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 a policy able to pay lighter costs, but resulting in poor-performing policy. All the other found (hyper)policies, instead, provide similar performance scores.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 ´4).C-PGAE employed a linear gaussian policy with variance σ 2 A " 1. The characteristics for all the risk measures' experiments are presented in Table 10 . For the learning rates schedules, we employed the Adam scheduler. Figure 5 shows the empirical distributions of costs over 100 trajectories of the learned (hyper)policies via C-PGPE and C-PGAE. C-PGPE shows a behavior that is quite the same as the one shown in the Swimmer-v4 environment. Indeed, by considering constraints on the CVaR α , the MV, or on the Chance, the learned hyperpolicy selects parameters for the underlying policy selecting actions that pay a way lighter cost w.r.t. the ones provided by an hyperpolicy learned by considering constraints on average costs. It is worth noticing that the lightest costs are observed when considering the CVaR α or the MV risk measures. In this case, C-PGAE shows a similar behavior to 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 cost constraints. For what concern the performances of the learned (hyper)policies (see Table 4c , C-PGPE exhibit high-performing hyperpolicies under average cost or chance constraints, while the ones under CVaR α and MV shows similar (low) performance scores. On the other hand, for C-PGAE the learned policy under CVaR α exhibits the same goodperforming behavior as the one of the policy learned under average cost constraints.Here, we study the sensitivity of C-PGAE and C-PGPE w.r.t. the regularization term ω. We tried the algorithms on a bidimensional LQR environment which has been modified to output a cost signal based on the selected action. For the environment at hand, we considered a horizon T " 50. We run both the algorithms for K " 10 4 iterations, with a batch size N " 100 trajectories per iteration, and with a varying regularization term such that ω P t0, 10 ´4, 10 ´2u. We considered a single constraint on the average trajectory cost, for which we set a threshold b " 0.2. For the step size schedules, we employed Adam (Kingma and Ba, 2015) with initial rates ζ ρ,0 " ζ θ,0 " 10 ´3 and ζ λ,0 " 10 ´2. Moreover, in this specific experiment C-PGAE employed a linear gaussian policy with a variance σ 2 A " 10 ´3. On the other hand, C-PGPE employed a linear gaussian hyperpolicy with a variance σ 2 P " 10 ´3 over a linear deterministic policy. The experimental environment is summarized in Table 12 . Figures 7 and 6 show the Lagrangian curves, the performance ones (i.e., the one associated with the objective function), and the cost-related ones. From the shown curves it is possible to notice that, for both C-PGAE and C-PGPE, a higher regularization (ω " 10 ´2) corresponds to a higher bias w.r.t. the constraint satisfaction. This bias is compliant with what shown by Theorem 3.1, 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 a higher regularization leads to have smaller values of λ. Moreover, we empirically notice that C-PGAE reaches higher value of λ w.r. All the experiments were run on a 2019 16-inches MacBook Pro. The machine was equipped as follows:CPU RAM GPU Intel Core i7 (6 cores, 2.6 GHz) 16 GB 2667 MHz DDR4 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 T " 100 scored « 5 and « 8 iterations per second respectively for C-PGAE and C-PGPE. All the performances are to be considered with a parallelization over 10 CPU cores.38th Conference on Neural Information Processing Systems (NeurIPS 2024).The dimension-free property(Liu et al.,2021;Ding et al., 2020Ding et al., , 2022Ding et al., , 2024) ) is achieved when the convergence rates do not depend on the cardinality of the state and/or action spaces.We highlight the dependences on ω since, as we shall see later, we will set ω " Opϵq having, consequently, an effect on the convergence rate.In the context of this statement, the Op¨q notation preserves dependences on ϵ and ω only.Theorem 3.2 provides an iteration-complexity guarantee. Concerning the estimated gradient case, this translates into a sample complexity guarantee since we are allowed to estimate gradients with a single sample.For the sake of generality, we admit risk optimization also for the 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. η.In the context of this statement, the Op¨q notation preserves dependences on ϵ and ω only. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 

The algorithm proposed in this paper is a type of primal-dual method. Under certain assumptions, this algorithm is shown to have last iterate convergence.

This paper also executes numerical experiments on various environment with their algorithm, and the experiments validate the results in this paper.
strength_weakness: strength_weakness: I don't see significant weaknesses in this paper.
questions: questions: Do you have lower bounds showing that these rates are tight?
limitations: limitations: Yes. The authors addressed all the limitations listed in the guidelines.
paper_summary: paper_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.
strength_weakness: strength_weakness: Quality:

1. 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. 
2. 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].

Clarity:

1. The range of reward value is [-1, 0], which is a bit weird compared to normal settings.
2. The advantage of parameter-based hyperpolicy is not clearly mentioned in the paper.

Significance:

One 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.
questions: questions: Please see the details in "weakness".
limitations: limitations: There is no potential negative social impact of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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. 
* 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.

Minor comments: it would be better to make figure legends exactly align with the names of algorithms, e.g., change CPGAE to C-PGAE.
questions: questions: * I hope the author could further clarify the contribution/role of Section 4 in the paper.
* Could the author also discusses how the techniques used in the paper different from that in Ding et al., 2024?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Although 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.

The experiment scenarios are relatively simple, but it is acceptable if the theoretical result is sufficiently solid.





[1] Khuzani, Masoud Badiei, and Na Li. "Distributed regularized primal-dual method: Convergence analysis and trade-offs."
questions: 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?

How 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.

I am willing to increase my score if weaknesses and questions are addressed.
limitations: limitations: No limitations of the paper are explicitly stated by the author.

Comments: comment: Thank you for your detailed responses. The main contribution of the paper is the derivation of theoretical results that simultaneously offer several advantages (i)-(vi). However, some of these advantages ((i)(ii)(iv)(vi)) have been addressed by previous works. A concern is that assumptions like gradient domination, regularity of the objective function, and the existence of saddle points are quite similar to those in standard (non-convex) optimization, which has been extensively studied in the field of optimization.

Overall, I think the theoretical results are solid, but the experiments and comparisons with baselines are relatively simple. As I am not fully familiar with the theory bar of this conference, I will finalize my score after discussing it with the AC. If the paper meets the requirements, I am inclined to vote for acceptance.
Thank you for your clarification! I have increased the score.
Thank you very much for your response. I do not have further questions.
I thank the reviewer for the explanations. I will maintain my score.