e-COP : Episodic Constrained Optimization of Policies
Authors: Akhil Agnihotri
Rahul Jain
Deepak Ramachandran
Sahil Singla
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
policy optimization
constrained MDPs
Primary area: reinforcement_learning
TL;DR: a policy optimization algorithm for episodic constrained MDPs

Abstract: In this paper, we present the e-COP algorithm, the first policy optimization algorithm for constrained Reinforcement Learning (RL) in episodic (finite horizon) settings. Such formulations are applicable when there are separate sets of optimization criteria and constraints on a system's behavior. We approach this problem by first establishing a policy difference lemma for the episodic setting, which provides the theoretical foundation for the algorithm. Then, we propose to combine a set of established and novel solution ideas to yield the e-COP  algorithm that is easy to implement and numerically stable, and provide a theoretical guarantee on optimality under certain scaling assumptions. Through extensive empirical analysis using benchmarks in the Safety Gym suite, we show that our algorithm has similar or better performance than SoTA (non-episodic) algorithms adapted for the episodic setting. The scalability of the algorithm  opens the door to its application in safety-constrained Reinforcement Learning from Human Feedback for Large Language or Diffusion Models.

e- e-COP: Episodic Constrained Optimization of Policies
Akhil Agnihotri University of Southern California agnihotri. akhil@gmail. sommail.com com
Rahul Jain Google DeepMind and USC
rahulaj ainggoogle..coooooooooo com
Deepak Ramachandran
Sahil Singla
Google Deep ramachandrran@ggogle..co
Google Deep.Mind sasingla@google.. com
Abstract
In this paper, we present the e-COP algorithm. the first policy optimization algorithm for constrained Reinforcement Learning (RL) in episodic (finite horizon) settings. Such formulations are applicable when there are separate sets of optimization criteria and constraints on a system's behavior. We approach this problem by first establishing a pol- icy difference lemma for the episodic setting, which provides the theoretical foundation for the algorithm. Then, we propose to combine a set of established and novel solution ideas to yield the e-COP algorithm that is easy to implement and numerically stable, and provide theoretical guarantee on optimality under certain scaling assumptions. Through extensive empirical analysis using benchmarks in the Safety Gym suite, show that our algorithm has similar or better performance than SoTA (non-episodic) algorithms adapted for the episodic setting. The scalability of the algorithm opens the door to its application in cafety-constrained Reinforcement Learning from Human Feedback for Large Language Diffusion Models.
Introduction
RL problems may be formulated in order satisfy multiple simultaneous objectives. These include performance objectives that we want to maximize, and physical, operational or other objectives that wish constrain rather than maximize. For example, robotics, we often want optimize task completion objective while obeying physical safety constraints. Similarly, in generative Al models, we want optimize for human preferences while ensuring that the output generations remain safe (expressed perhaps as a threshold on an automatic safety score that penalizes violent or other undesirable content). Scalable policy optimization algorithms such as TRPO [31]. PPO [33], etc have been central to the achievements of RI over the last decade [34, 38, 7]. In particular, these have found utility in generative models, e.g., in the training Large Language Models (L.LMs) be aligned to human preferences through the RL with Human Feedback (RLHF) paradigm [2]. But these algorithms are designed primarily for the unconstrained infinite-horizon discounted setting: Their use for constrained problems via optimization of the Lagrangian often gives unsatisfactory constraint satisfaction results. This has prompted development of a number of constrained policy optimization algorithms for the infinite-horizon discounted setting [3, 39, 43, 41, 19, 6, 5], and for the average setting [4].
However, many RL problems are more accurately formulated as episodic, i.c., having finite time horizon. For instance, in image diffusion models [10, 21]. the denoising sequence is really a finite step trajectory optimization problem, better suited to be solved via RL algorithms for the episodic setting, When existing algorithms for infinite horizon discounted setting are used for such problem, they exhibit sub-optimal performance or fail to satisfy task-specific constraints by prioritizing short-term constraint satisfaction over episodic goals [1 28, 17]. Furthermore, the episodic setting allows for objective functions to be time-dependent which the infinite-horizon formulations do not. Even when the objective functions are
38th Conference on Neural Information Processing Systems PP 2024).

---

time-invariant, there is a key difference: for non-episodic settings, a stationary policy that is optimal exists whereas for episodic settings, the optimal policy is always non-stationary and time-dependent. This necessitates development of policy optimization algorithms specifically for the episodic constrained setting. We note that such policy optimization algorithms do not exist even for the unconstrained episodic setting.
In this paper, we introduce e-CDP, a policy optimization algorithm for episodic constrained RL problems. Inspired by PPO, it uses deep barning-based function approximation. a KL divergence-basce proximal trust region and gradient clipping, along with several novel ideas specifically for the finite horizon episodic and constrained setting. The algorithm is based on a technical lemma (Lemma 3.1) on the difference between two policies, which leads new loss function for the episodic setting. We also introduce other ideas that obviate the need for matrix inversion thus improving scalability and numerical stability. The resulting algorithm improves performance over state-of- of-tth-rrt baselines (after adapting them for the episodic setting). In sum, the e-COP algorithm has the following advantages: (i) Solution equivalence: We show that the solution set of our e-COP loss function is same as that of the original CMDP problem, leading to precise cost control during training and avoidance of approximation errors (see Theorem 3.3); (ii) Stable convergence: The e-COP algorithm converges tightly to safe optimal policies without the oscillatory behavior seen in other algorithms like PDO [13] and FOCOPS [43]; (iii) Easy integration: e-COP follows the skeleton structure of PPO-style algorithms using clipping instead of steady state distribution approximation, and hence can be easily integrated into existing RL pipelines; and (iv) Empiricial performance: the e-COP algorithm demonstrates superior performance on several benchmark problems for constrained optimal control compared to several state-of-the art baselines.
Our Contributions and Novelty. We introduce the first policy optimization algorithm for episodic RL problems, both with and without constraints (no constraints is a special case). While some of the policy optimization algorithms can be adapted for the constrained setting via a Lagrangian formulation, as we show, they don't 't work so well empirically in terms of constraint satisfaction and optimality. The algorithm based on policy difference (technical) lemma, which is novel. We have gotten rid of Hessian matrix inversion, a common feature of policy optimization algorithms (see, for example. PPO [33], CPO [3], P30 [41], etc.) and replaced it with a quadratic penalty term which also improves numerical stability near the edge of the constraint set boundary- a problem unique to constrained RL problems. We provide an instance mnstance-dependent hyperparameter tuning routine that generalizes to various testing scenarios. And finally, our extensive empirical results against an extensive suite of baseline algorithms (e.g., adapted PPO [33], FOCOPS [43], CPO [3], PCPO [39], and P3O [41]) show that e-COP performs the best or near-best on range of Safety Gym [12] benchmark problems.
Related Work. A broad view of planning and model-free RL techniques for Constrained MDPs provided in [27] and [18]. The development of SOTA policy optimization started with the TRPO algorithm [31], which used a trust region to update the current policy, and was further improved in PPO by use of proximal ideas [33]. This led to works like CPO [3], RCPO [36]. and PCPO [39] for constrained RL. problems in
the infiitt-hhorion discounted setting. ACPO [4] extended CPO to the aifnite-horizon average setting. These methods typically require inversion of a compuuttiioalll-expenss
Fischer information matrix at each update step, thus limiting scalability. Lagrangian-basse bbased algorithms [29, 30] showed that you could incorporate constraints but constrained satisfaction remained concern. Algorithms like PDO [13] and RCPO [36] also use Lagrangian duality but to solve risk-constrained RL problems and suffer from computational overhead. Some other notable algorithms include IPO [26]. P3O [41], APPO [15], etc. that use penalty terms, and hence do not suffer from computational overhead but have other drawbacks backs. For example, IPO assumes feasible intermediate iterations, which cannot be fulfilled in practice, P3O requires arbritarily large penalty factors for feasibility which can lead to significant estimation errors. We note that all the above algorithms are for the infinite-horizz horizon discounted (non-episodic) setting (except ACPO [4), which is for the average setting). We are not aware of any policy optimization algorithm for the episodic RL problem, with or without constraints.
Preliminaries
An episodic, or fixed horizon Markov decision process (MDP) is a tuple, M = (S, H),
where S is the set of states, A the set of actions, r : *S A 5 - T. is the reward function, P: S x A x S - [0, 1] is the transition probability function such that P(s"|s, a) is the probability of transitioning to state s' from state & by taking action a, p : S - [0, 1] is the initial state distribution, and H is the time horizon for each episode (characterized by a terminal state s
2

---

Notation. [N] denotes (I....,N} for some N N. Th refers to the policy at time step h within an episode. Denote Tes := (T,, Ts-.:..... TT) for some & L with 8, L [H]. We shall only write Te when necessary to differentiate policies from different episodes but at the same time then naturally follows to define akt to be the sequence Rat in episode k. We will denote Th Tr,1: and policy :: - ((4) is a mapping from states to probability distributions over the actions, with x (<a denoting the probability of selecting action in state 8, and A(A) is the probability simplex over the action space A. However, due to the temporal nature of episodic RL, the optimal policies are generally not stationary, and we index the policy at time h by Tht and denote 1: (TT))-- Then, the total undiscounted reward objective within an episode is defined as
H Σ
J [TT:H)
E T-
r(sh ahe sh+1)
where r refers to the sample trajectory (81, 01 82, .2,...,, generated when following a policy se- quence, i.e., O4 TT(-188), 8h+1 P(-[sh, ap), and 81 J..
811)
Let (T) denote the total reward of trajectory starting from time h until episode terminal time H generated by following the policy sequence Th... We also define the state-value function of state at step h as Vyt == -ー [R) 8s = s] and the action-value function as Q7 (s, a) :=
E (R 8n = 8, ab = a]. The advantage function is (s, a) == (T - (s). We also T-M
define P7, (s] $1) = Eaea A P7, (s, a 81), where the term (s, a $1) is the probability of reaching (s. a) at time step h following π and starting from $1.
Constrained MDPs. A constrained Markov decision process (CMDP) is an MDP augmented with constraints that restrict the set of allowable policies for that MDP. Specifically, we have m cost functions, C, Cm (with each function C, : S A x S R mapping transition tuples to costs, similar the reward function), and bounds di.... dm. And similar to the value function for the reward objective. we define the expected total cost objective for each cost function C (called cost value for the constraint)
H Σ
(TIH) =
C,(sh, ag. 8h+1)
The goal then, in each episode, is find a policy sequence Ti.H such that
J(Ti.H) := max (IIHH), where 1l == ( E Il : (o,(T))) & di, [ie (1)
T.helle
is the set of feasible policies for a CMDP for some given class of policies II. Lastly, analogous to V,," O and AT, we can also define quantities for the cost functions C-(-) by replacing, and denote them by C... QT and AT, Proofs of theorems and statements, if not given, are available in Appendix A.
where not needed drop the index for the episode so that π = Tkk
3 Episodic Constrained Optimization of Policies (e-COP)
In this section, propose constrained policy optimization algorithm for episodic MDPs. Policy optimization algorithms for MDPs have proven remarkably effective given their ability to computationally scale up to high dimensional continuous state and action spaces [31-33]. Such algorithms have also been proposed for infinite-horizon constrained MDPs with discounted criterion [1] as well as the average criterion [4] but not for the finite horizon (or as it often called, the episodic) setting.
We note that finite horizon is not simply a special case of aefinite-horizon discounted setting since the reward/cost functions in the former can be varying while the latter only allows for time-invariant objectives. Furthermore, even with time-ine -nvviriat objectives, the optimal policy is time-dependent, while for the latter setting there optimal policy that is stationary exists.
Policy Difference Lemma for Episodic MDPs. Most policy optimization RL algorithms are based on value or policy difference technical lemma [23]. Unfortunately, the policy difference lemmas that have been derived previously for the dnfinite-horizon discounted [31] and average case [4] are not applicable here and hence, derive new policy difference lemma for the episodic setting.
3

---

Lemma 3.1. For an episode of length H and two policies, a and n², the difference in their performance assuming identical initial state distribution jr (i.e., 81 (1) is given by
H
J(x)- - J(T')
E
[A (Sh:an]]
The proof can be found in Appendix A.1. A key difference to note between the above and similar results for unfinite-horizon settings [31, 4] is that considering stationary policies (and hence corresponding occupation measures) is not enough for the episodic setting since, in general, such a policy may be far from optimal. This explains why Lemma 3.1 looks so different (e.g., see (2) in [31], and Lemma 1.1 in [4]). Indeed, the lemma above indicates that policy updates do not have to recurse backwards from the terminal time dynamic programming algorithms do for episodic settings, which is somewhat surprising.
Constrained Policy Optimization Algorithm for Episodic MDPs. Iterative policy optimization algorithms achieve state of the art performance [33, 36, 39] on RL problems. Most such algorithms maximize the advantage function based on a suitable policy difference lemma, solving an unconstrained RL problem. Some additionally ensure satisfaction of infinite horizon expectation constraints [3, 4]. However, given that our policy lemma for the episodic setting (Lemma 3.1) is significantly different, need to re-design the algorithm based it. A first attempt is presented Algorithm 1, where each iteration corresponds to an update with a full horizon H episode.
Algorithm Iterative Policy Optimization for Constrained Episodic (IPOCE) RL
1: Input: Initial policy To: number of episodes K, episode horizon H.
2: for k 1,2,-.. K do
3: Run π to collect trajectories T.
4: Evaluate k- and A c, for h [H] from
5: for t H, H- 1, 1.....I do
6: The
arg min
Σ
I-A A.- (s, s.t. Jc, (T,(TT=)))
Σ hut
[A < & (3)
me,t
end for
8: Set IT&
T ... TK.H.
9: end for
The iterative constrained policy optimization algorithm introduced above uses the current iterate of the policy Ty to collect a trajectory т, and use them to evaluate A, and A for h E [H]. At the end of the episode, we solve H optimization problems (one for each h [H] that result in a new sequence of policies ग. As natural in episodic problems, we do backward iteration in time, i.e., solve the problem in step (6) at h H, and then go backwards towards h 1.
Note that the expectation of advantage functions in equation (3) is with respect the policy æ (the optimization variable) and its corresponding rime-dependent state occupation distribution Px.. In the infinite-horizon settings, the expectation with respect to the steady state stationary distribution, but that does not exist in the episodic setting.
Using current policy for action selection. Algorithm represents exact principled solution tothe constrained episodic MDP, but the intractable optimization performed in (3) makes it impractical (as in the case of infinite horizon policy optimization algorithms [31, 39]). We proceed to introduce a sequence of ideas that make the algorithm practical (e.g.. by avoiding computationally expensive Hessian matrix inversion for with trust-region methods [33, 14, 41]). However, getting rid of trust regions leads to large updates on policies, but PPO [33] and P3O [41] successfully overcome this problem by clipping the advantage function and adding ReLU-like penalty term the minimization objective. Motivated by this, we rewrite the optimization problem in (3) as follows by parameterizing the policy The in episode k and time step by Og.
Thtt = arg min
Σ
(- (v.aa] [aa]+]]] + Σ Ars max oo, Σ
m
[p(H))AT (8, + Jo, (mx-)) - dd
(4)

---

m0 is the importance sampling ratio, A a penalty factor for constraint C₁, and Th.0, = Tg.h = A. Note that the ReLU-like penalty term above is different from the traditional first-order and second-order gradient approximations that are employed in trust-region methods [3, 39]. In essence, the penalty is applied when the agent breaches the associated constraint, while the objective remains consistent with standard policy optimization when all constraints are satisfied.
where p(O,)=
1.g-1.h
has been noted in such iterative policy optimization algorithms that the behaviour of the learning agent when it nears the constraint threshold is quite volatile during training [3, 39, 42). This because the penalty term is active only when the constraints are violated which results in sharp behavior change for the agent. To alleviate this problem, quadratic damping term to the objective above, which provides stable cost control to compliment the lagged Lagrangian multipliers. This has proved effective in physics- based control applications [16, 25, 20] resulting in improved convergence since the damping term provides stability, while keeping the solution set the same for the original Problem (3) and the adapted Problem (4) (as prove later).
Introducing quadratic damping penalty.
introduce additional
For brevity, we denote the constraint term in Problem (4) as
V ( TR) = Ih-e
[p, (s, [s + Jo, (TT-1) d,.
emPEK. a a-
Now introduce a slack variable Tt,s (Vc,,(:;-)) 0) equality by letting
> O for each constraint to convert the inequality constraint
(T,)(TT == V. (TR-, TT) + Ft,i O.
With this notation, we restate Problem (4) as:
T5 min L.T.. A) = Ex
E ((0 [ss,a)= + Σ." Au, max(0, (
sMPEAA a-Ta--th
Now we introduce the quadratic damping term and the intermediate loss function then takes the form,
H
8 wt (T() 1- A(0n) (s, + > (
2
x,,
E 5
a a.-
Then,
(Ti. Xi,
max min Le (TT, A, x. (3),
A x3,
where / is the damping factor, X, = (Ar,s -11 and xe = (=+,)) We can then construct a primal-dual solution to the max-min optimization problem. The need for slack variable æ can be obviated by setting the partial derivative of (-)(-) with respect to x equal to O. This leads to a ReLU-like solution:
27,, max (0, V TT)) ). The intermediate problem then takes the form as below.
Proposition 3.2. The inner optimization problem in (5) with respect is a convex quadratic program with negatie constraints, which can be solved to yield the following intermediate problem:
(T Xi)
max min Li(Ts, (, A) A35 Wass
where
H
max (0 0, (
Ar.
(6)
L.(T.. A,
E a-me-rA
((,)) - (s,a))
82
The proof can be found in Appendix A.1. One can see that the cost penalty is active when Ars 3" -
(C., TT) >
rather than when (C,,((TT-I,TT)) > O. This allows the agent to act in show next, the introduction of
constrained manner even before the constraint is violated. Further, the damping factor and the RELU-like penalty does not change the solution of the problem (under some suitable assumptions):
Theorem 3.3. Let (6" be a solution to Problem (3), and let (х (()) be a solution to Problem (6). Then, for sufficiently large 3 > 3 and X > X Vi, 200"" is a solution to Problem (6), and (6" is solution to Problem (3).
We refer the reader to Appendix A. for the proof. This theorem implies that we can search for the optimal feasible policies of the CMDP Problem (1) by iteratively solving Problem (6). Next, we make some further modifications to Problem (6) that give our final tractable algorithm.
5

---

Removing Lagrange multiplier dependency. Problem (6) requires a primal-dual algorithm that will iteratively solve over the policies and the dual variable X. But from the Lagrangian, can actually take derivative with respect to X, and then solve for it, which yields the following update rule for it:
max (0, X
(k-1) (T -x-
(7)
This update rule simplifies the optimization problem and updates the Lagrange multipliers in the kth episode based on the constraint violation in the (k - 1)th episode.
Clipping the advantage functions. Solving the optimization problem presented in equation (6) is intractable since we do not know Pr beforehand. Hence, we replace Pr by the empirical distribution observed with the policy of the previous episode, k I.e., PTe, P h. Similar to [33] for PPO, we also use clipped surrogate objective functions for both the reward and cost advantage functions.
Thus, the final problem combining equation (4) and equation (6) can be constructed follows.
If we let
((
Σ h-t
min (o00))/4 1444) (s, and,
H
(o),(0)
I
[- m-min (s0))))) 1) (8,0)]
Pee Jum1 amill1ik
then, the final loss function L((-) of the final problem is:
N2. arg min LN A, arg min L.(()= Rh,t
Av max (0, (0,, (Jc.(Te))) d:))
Thtt
(8)
8 2 Σ max U. +
(Jx (Jcc)))+(J.((/))))) di) + de.
X ga
Usually for experiments, Gaussian policies with means and variances predicted from neural networks are used [31, 3, 33, 39]. We employ the same approach and since we work in the finite horizon setting, reward and constraint advantage functions can easily calculated from any trajectory T ~ т. The surrogate problem in equation (8) then includes the pessimistic bounds Problem (6), which is unclipped.
Adaptive parameter selection. The value of is required to be larger than the unknown 3 according to Theorem 3.3, but we also know that too large a 3 decays the performance (as seen in harmonic oscillator kinetic energy formulations [25, 20, 40]). To manage this tradeoff, we provide an instance-dependers adaptive way to adjust the damping factor as hyperparameter. In each episode k, we update the damping parameter whenever a secondary constraint cost value denoted by ((T,)) ) is larger than some threshold cg. Using Proposition 3.2, we provide the following definitions.
# C(TT)) = Σ Σ max Jc, (TTx) - de,
(k)
and
Ck := v /m
max [
|
(k)
lb
B
Algorithm Episodic Constrained Optimization of Policies (e-COP)
1: Input: Initial policy Op := To := Te, critic networks V and V V i, penalty factor B, number of episodes K, episode horizon H, learning rate a, penalty update factor p.
2: for k: = 1, 1,2...., K do Collect a set of trajectories Dx-1 with policy πk- and update the critic network. 4: Get updated (k) using equation (7).
5: to H, H 1,.... 1 do
6: Update the policy tx.t Gx.t11 - a (W), using equation (8).
end for
8:
if ((x)) 3 then
9:
min (Bixx p(3)
10: end if
11: end for

---

(a) Humanoid
(b) Circle
(c) Reach
(d) Grid
(e) Bottleneck
(f) Navigation
Figure 1: The Humanoid, Circle, Reach, Grid, Bottleneck, and Navigation tasks. See Appendix A.2.1 for details.
Hence, increase by constant factor p 1 after every episode if C(TT)) > c until stopping iterations that are more
condition is fulfilled, typically a constant 9max- This leads to constraint-satisfyye stable, and show that it enables a fixed 33 to generalize well across various tasks. The initial 3 can simply be selected by a quantified line-search to obtain a feasible 3 > 3 [3, 4].
We note that the final loss function in equation (8) is differentiable almost everywhere, solve it via any first-order optimizer [24]. The final practical algorithm, e e-COP given in Algorithm 2.
could easily
4 Experiments
We conducted extensive experimental evaluation on the relative empirical performance of the e-COP algorithm arrive at the following conclusions: (i) The e-COP algorithm performs better or nearly as well as all baseline algorithms for infinite-horizon discounted safe RL tasks in maximizing episodic return while satisfying given constraints. (ii) It is more robust stochastic and complex environments [30], even where previous methods struggle. (iii) It has stable behavior and more accurate cost control compared to other baselines near the constraint threshold due to the damping term.
Environments. For a comprehensive empirical evaluation, we selected eight scenarios from well- known safe RL benchmark environments Safe MuloCo [43] and Safety Gym [30], as well as MuloCo environments. These include: Humanoid, PointCircle, AntCircle, PointReach, AntReach, Grid, Bottleneck, and Navigation. See Figure I for an overview of the tasks and scenarios. Note that Navigation is a multi-constraint task and for the Reach environment, we set the reward as a function of the Euclidean distance between agent's position and goal position. In addition, we make it impossible for the agent to reach the goal before the end of the episode. For more information see Appendix 1.2.
Baselines. We compare our e-COP algorithm with the following bascline algorithms: CPO [3], PCPO [39], FOCOPS [43], PPO with Lagrangian relaxation [33, 35], and penalty-based P3O [41]. Since the above kate-of-the-ar baseline algorithms are already well understood to outperform other algorithms such as PDO [13], IPO [26], and CPPO-PID [35] in prior benchmarking studies, we do not compare against them. Moreover, since PPO does not originally incorporate constraints, for fair comparison, introduce constraints using a Lagrangian relaxation (called PPO-L). In addition, for each algorithm, we report its performance with the discount factor that achieves the best performance. See Appendix A.3.1 for more details.
Evaluation Details and Protocol. For the Circle task, use a point- with S c R A R² and for the Reach task, an ant robot with = 16 A C R8. The Grid task has S S 5 A R We use two hidden layer neural networks represent Gaussian policies for the tasks. For Circle and Reach, size is (32,32) for both layers, and for Grid and Navigation the layer sizes are (16, 16) and (25,25). We set the step size 8 to 10-4, and for each task, we conduct independent runs of K 500 episodes each of horizon H 200. Since there are two objectives (rewards in the objective and costs in the constraints), show the plots which maximize the reward objective while satisfying the cost constraint.
4.1 Performance Analysis
Table I lists the numerical performance of all tested algorithms in seven single constraint scenarios, and one multiple constraint scenario. We find that overall, the e-COP algorithm in most cases outperforms (green) all other baseline algorithms in finding the optimal policy while satisfying the constraints, and in other cases comes a close second (light green).
From Figure 2, we can see how the e-COP algorithm is able to improve the reward objective over the baselines while having approximate constraint satisfaction. We also see that updates of e-COP are faster and smoother than other baselines due to the added damping penalty, which ensures smoother
7

---

Task
e-COP
FOCOPS
P30-L]30]
[39]
P30
CPO
APPO
IPO [26]
R
1652.5
13.4 1734.1
27.4 1431.2
25.2 1602.3
10.1
13.7 1465.1 55.3 1488.2 29.3 1578.6 25.2
Humancid
C (20.0)
17.3 1 0.3
19.7 1 0.6
18.8 1 1.5
16.3 1 1.4
20.1 1 3.3
18.5 = 2.9
20.0 1 1.3
19.1 1
R
110.5 9.3
81.6 1 8.4
57.2 1 9.2
68.2 1.
89.1 1 7.1
65.3 5.3
91.2 1. 9.6
68.7 15.2
PuiniCircle
C (10.0)
0.9
10.0 1 0.4
0.5
0.4
10.2 1 0.6
0.5
161.9 1:
134.4 1:
168.3 1:
182.6 1:
155.5 1
1.
AnCCrclle
C (10.0)
9.5
0.2
10.1 = 0.7
10.0 = 0.5
R
81.5 10.2
65.1 :: 9.6
46.1 14.8
73.2 :: 7.4
76.3 1: 6.4
89.2 8.1
74.1 1 6.7
49.1 10.6
PointReach
C (25.0)
24.5 - 6.1
24.8 = 7.6
25.1 = 6.1
24.9 5.6
26.3 = 6.9
33.3 10.7
26.3 = 8.1
24.7 11.3
70.8
4: 5.6
+: 9.5
+:
102.3
61.5 +
45.2
AntReach
(25.0)
24.2 + 8.4
25.1 11.9
21.9 10.7
27.9 1 12.2
24.8 = 7.3
35.1 + 10,9
24.5 = 6.4
24.9 - 9.2
R
258.1 + 33.1
215.4 +: 45.6
276.3 + $7.9
226.5 +: 29.2
201.5 + 39.2
178.1 23.8
184.4 +: 21.5
229.4 32.8
C (75.0)
71.3 26.9
76.6 29.8
71.8 25.1
72.6
16.5
79.3 19.3
69.3 19.8
79.5 35.8
74.2 24.6
345.1 + 251.3 +
298.3 + 71.2
264.2 +:
+
= 36.6
+
279.3 +
Bottleneck (50.0)
49.7 15.1
46.6 19.8
41.4 17.6
49.8 10.5
45.3 1: 8.2
54.3 13.5
47.4 1: 12.3
48.2 14.6
R
217.6 + 11.5
175.1 + 3.7
153.5 + 25.2
135.7 + 19.2
164.1 1 = 12.8
Navigation (10.0)
9.9
9.9 1 2.1
10.0 i 0.5
C2 (25.0)
+
= 2.1
24.5 =
+ 3.8
24.6 3.1
Table 1: Mean performance with normal 95% confidence interval over independent runs on some tasks.
Episodic Rewards:
250
200
50
320
1200
900
100
40
160
80
0
100
200
300
100
200
300
000
500
100
200
300
400
500
100
200
500
400
500
Constraint Costs:
E-COP
FOCOPS
PPO-L
PCPO
P30
20
16
12
24
16
100
400
500
300
400
100
300
500
100
500
Humanoid
(b) Ant Circle
(c) Point Reach
(d) Bottleneck
Figure 2: The cumulative episodic reward and constraint cost function values vs episode learning curves for some algorithm-task pairs. Solid lines in each figure are the means, while the shaded area represents standard deviation, all over 5 runs. The dashed line in constraint plots is the constraint threshold.
convergence with only a few constraint-violatin behaviors during training. In particular, e-COP is the only algorithm that best learns cowprss-ooootttnttsstsiifff maximum reward policies across all tasks: in simple Humanoid and Circle environments, e-COP is able almost exactly track the cost constraint values to within the given threshold. However, for the high dimensional Grid environment we have more constraint violations due to complexity of the policy behavior, leading to higher variance in episodic rewards as compared to other environments. Regardless, overall in these environments, e-COP still outperforms all other baselines with the least episodic constraint violation. For the multiple constraint Navigation environment, see Figure
4.2 Secondary Evaluation
In this section, we take a deeper dive into the empirical performance of e-COP. We discuss its dependence on various factors, and try to verify its merits.
Generalizability, From the discussion above, it's clear that e-COP demonstrates accurate safety satis- faction across tasks of varying difficulty levels. From Figure 4, we further see that e-COP satisfies the
8

---

comstrained
CI constrained
C2 constrained
PPO-L
200
26
100
14
9
300
%
500
(a) Rewards
(b) Costl (hazards)
(c) Cost2 (pillars)
Figure 3: Navigation environment with multiple constraints:
Episodic Rewards (left), Costl (center, for hazards) and Cost2 (right, for pillars) of e-COP The dashed line in the cost plots is the cost threshold (10 for Cost1 and 25 for Cost2). C1/C2 constrained means only taking Cost1/Cost2 into the e-CDP loss function and ignoring the other one.
constraints in all cases and precisely converges to the specified cost limit. Furthermore, the fluctuation observed in the baseline lagrangian-basee algorithms is shown not to be tied to specific cost limit.
We also conducted a set of experiments wherein we study how e-COP effectively adapts to different cost thresholds. For this, we use the hyperparameters of pre-trained e-COP agent, which is trained with particular cost threshold in an environment, for learning on different cost thresholds within the same environment. Figure 6 in Appendix A.3.4 illustrates the training curves of these pre-trained agents, and we see that while e e-COP can generalize well across different cost thresholds, other baseline algorithms may require further tuning to accommodate different constraint thresholds.
200
100
40-
20-
%
300
100
500
500
(a) Ant Circle Rewards
(b) Ant Circle Costs
(c) Point Reach Rewards
(d) Point Reach Costs
Figure 4: Cumulative episodic rewards and costs baselines in two environments with two constraint thresholds.
eCCPP
Task
P30
Ø 5, fixed
8 5, adoptive
10, fixed
10, adaptive
PointCirele
11.1
1
145.2
11.4
(20.0)
17.3
19.7 + 0.6
18.8
18.3
19.1
R
48.2 3.5
58.6 1: 5.1
53.2 5.3
65.2 8.1
61.1 1: 5.6
AmRReach
C. (20.0)
19.8 5,9
20.0 1 4.4
20.6 1 4.5
19.2 6.2
18.9
Table 2: Performance of e-COP for different 33 settings on two tasks. Values are given with normal 95% confidence interval over independent runs.
Sensitivity. The effectiivneess and performance of e-COP would not be justified if it was not robust to
the damping hyperparameter 3, which varies across tasks depending on the values of C(-) and сд- Since this damping penalty enables e-COP have stable continuous cost control, we update adaptively as described in Algorithm 2. As seen in Table 2, damping penalty indeed stabilizes the training process and helps in converging to an optimal safe policy.
Conclusion
In this paper, we have introduced an easy to implement, scalable policy optimization algorithm for episodic RL problems with constraints due to safety or other considerations. It is based on a policy difference lemma for the episodic setting, which surprisingly has quite a different form than the ones for infinite- horizon discounted or average settings. This provides the theoretical foundation for the algorithm, which is designed by incorporating several time-tested, practical as well as novel idcas. Policy optimization algorithms for Constrained MDPs tend to be numerical unstable and non-scalable due to the need for inverting the Fisher information matrix. We sidestep both of these issues by introducing quadratic damping penalty term that works remarkably well. The algorithm development well supported by theory, well with extensive empirical analysis range of Safety Gym and Safe MuJoco benchmark environments against suite of baseline algorithms adapted from their non non-episodic roots.

---

References
[1] Achiam. UC Berkeley CS 285 (Fall 2017), Advanced Policy Gradients, 2017. URL: http://aill ppf............................. Last
eecs, berkeler beecs.erkelee..dddddeeee visited on 2020/05/24.
[2] J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt,
S. Altman, S. Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
[3] Achiam, D. Held, A. Tamar, and Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 22-31. JMLR. org, 2017.
[4] A. Agnihotri, R. Jain, and H. Luo. ACPO: A policy optimization algorithm for average MDPs with constraints. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 397-415. PMLR, 21-27 Jul 2024.
[5] A. Agnihotri, Jain, D. Ramachandran, and Wen. Online bandit learning with offline preference data. arXiv preprint arXiv:2406.099: 0957.,9974, 2024.
[6] A. Agnihotri, P. Saraf, and K. R. Bapnad. A convolutional neural network approach towards self- driving cars. In 2019 IEEE 16th India Council International Conference (INDICON), pages 1-4, 2019.
[7] I. Akkaya, M. Andrychowicz, M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's s cube with a robot hand, arXiv preprint arXiv:1910.07113 2019.
[8] D. Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
[9] E. G. Birgin and J. M. Martínez. Practical augmented Lagrangian methods for constrained opti- mization. SIAM, 2014.
[10] K. Black, M. Janner, Y. Du, I. Kostrikov, and S. Levine. Training diffuuson models with reinforcement learning. arXiv preprint arXiv:2305. 13301, 2023.
[11] H. Bojun. Steady state analysis of episodic reinforcement learning. Advances in Neural Information Processing Systems, 53:9335-9345 2020.
[12] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym, 2016.
[13] Y. Chow, M. Ghavamzadeh, L. Janson, and M. Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-6120, 2017.
[14] Y. Chow, O. Nachum, A. Faust, E. Duznez-Guzman, and M. Ghavamzadeh. Lyapunov-based safe policy optimization for continuous control. arXiv preprint arXiv: 1901:.000.10111 2019.
[15] Dai, J. Ji, L. Yang, Q. Zheng, and G. Pan. Augmented proximal policy optimization for safe reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 37:7288- 7295, Jun. 2023.
[16] A. Dowling and A. Morgans. Feedback control of combustion oscillations. Annu. Rev. Fluid Mech., 37:151-182, 2005.
[17] I. Greenberg and S. Mannor. Detecting rewards deterioration in episodic reinforcement learning. In International Conference Machine Learning, pages 3842-3853, PMLR, 2021.
[18] S. Gu. L. Yang, Y. Du, G. Chen, F. Walter, J. Wang, Y. Yang, and A. Knoll. A review of safe reinforcement learning: Methods, theory and applications. arXiv preprint arXiv:2205.103: 103.0 2022.
[19] H. Hu, Z. Liu, S. Chitlangia, A. Agnihotri, and D. Zhao. Investigating the impact of multi-lidar placement on object detection for autonomous driving. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2550-2559, June 2022.
[20] I. Imayoshi, A. Isomura, Y. Harima, K. Kawaguchi, H. Kori, H. Miyachi, T. Fujiwara, F. Ishidate, and R. Kageyama. Oscillatory control of factors determining multipotency and fate in mouse neural progenitors. Science, 342(6163): 203-11088, 2013.
[21] M. Janner, Y. Du, J. B. Tenenbaum, and S. Levine. Planning with diffusion for flexible behavior synthesis. arXiv preprint arXiv:2205.0998 099911 2022.
[22] J. Ji, J. Zhou, B. Zhang, J. Dai, X. Pan, R. Sun, W. Huang, Y. Geng, M. Liu, and Y. Yang- Omnisafe: An infrastructure for accelerating safe reinforcement learning research, arXiv preprint 203.00200, 2023.
10

---

[23] S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, volume 2, pages 267-274, 2002.
[24] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900 2014.
[25] W. Klimesch. Alpha-band oscillations, attention, and controlled access to stored information. Trends in cognitive sciences, (6(12):606-611, 2012.
[26] Y. Liu, J. Ding, and X. Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4940-4947, 2020.
[27] Y. Liu, A. Halev, and X. Liu. Policy learning with constraints in model-free reinforcement learning:
A survey. In The 30th international joint conference on artificial intelligence (ijcai), 2021.
[28] G. Neu and C. Pike-Burke. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392 2020.
[29] A. Ray, J. Achiam, and D. Amodei. Benchmarking Safe Exploration in Deep Reinforcement Learning. arXiv preprint arXiv:1910.0117
2019.
[30] A. Ray, J. Achiam, and D. Amodei. Benchmarking safe exploration in deep reinforcement learning. arXiv preprint arXiv:1910.01 000.00170.... 7, 2019.
[31] Schulman, S. Levine, Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897, 2015.
[32] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. International Conference on Learning Representations (ICLR), 2016.
[33] Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint 1 2017.
[34] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L., Baker, M. Lai, A. Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676)3354-
359, 2017.
[35] A. Stooke, J. Achiam, and P. Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference on Machine Learning, pages 9133-9143. PMLR, 2020.
[36] C. Tessler, D. J. Mankowitz, and S. Mannor. Reward constrained policy optimization. International Conference on Learning Representation (ICLR), 2019.
[37] E. Vinitsky, A. Kreidieh, I.. Le Flem, Kheterpal, K. Jang, Wu, R. Liaw, E. Liang, and A. M. Bayen. Benchmarks for reinforcement learning in mixed-autonomy traffic. In Proceedings of Conference on Robot Learning, pages 399-409, 2018.
[38] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3300-35 2019.
[39] T.-Y. Yang, J. Rosca, K. Narasimhan, and P. J. Ramadge. Projection-based constrained policy optimization. In International Conference on Learning Representation (ICLR), 2020.
[40] J. Yuan and A. Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018
[41] L. Zhang, L. Shen, L. Yang, S. Chen, B. Yuan, X. Wang, and D. Tao. Penalized proximal policy optimization for safe reinforcement learning. arXiv preprint arXiv:2205. 2022.
[42] S. Zhang, Y. Wan, R. S. Sutton, and S. Whiteson. Average-reward off-policy policy evaluation with function approximation. arXiv preprint arXiv:2101.02808 2021.
[43] Y. Zhang, Q. Vuong, and K. W. Ross. First order constrained optimization in policy space. arXiv preprint arXiv:2002.06506, 2020.

---

A Appendix
A.1 Proofs
Lemma A.1. For an episode of length H and two policies, a and w', the difference in their performance assuming identical initial state distribution (i.e., 1)) is given by
H
- ((x))((²²) =
E
[AA (sh, an)]
Proof. Let us consider ~ μ and categorize the value function difference between the two policies. Also define (s $1) = E A ( (s, a 81), where the term P [1)) the probability of reaching (s, a) at time step h following π and starting from S1.
- -s
= E [r(s) a1) + (32
+ E V (52) - V35 [s2)[s1] - VT (s1)
1
01.52
V (82) V2 (s2)]s1]
+ E [ 0n) + V3r (82) Vi (81) [1
#2
01.02
= [[V[" (52) - V. (+2)]= + I (s), a1) ViT (s1)|si]
V (82) Vi2 (s2)]s1
+ E L (s1, [1)[
where (1)-) ~ P( (s1))) and $1 μ. the initial state distribution.
Now recursively apply the same procedure to the term V (sk) (sw) V e f H} to obtain the following:
H
(s) V (3) = Σ
E
[A (sh, [s]
Now know that J(T)) = -1= (V) this means that we combine this with the above to obtain the final result.
Proposition A.2. The inner optimizution problem in (5) with respect to is convex quadratic program with non-tigative constraints, which can solved to yield the following intermediate problem:
(Kh 23)
max min Li(TT,,,55 3) What
where
H
max fU. V. Vo. Ar.i 12
Ni.
(6)
L.(TT.
E 1-
[- ((.)) ()) Σ
82
Proof: As in Equation (4), we have the following equivalent problem:
(lo())) (a + Nr max (0. Σ
m
F arg min T6.
(1 (Jo,(ma-1) di)
Letting Ve..lTTT TT)
E
E Pre.
A a) + (Jc, (TK-1) - d;), and introducing
amTi-11h
slack variables Fe,; > and defining Wr (TR) = (c, TT) + Zt, 0, we get the quadratic damped problem same as Equation (5) below.
(TT xū) = max min L'(TTK X, x X Th....
3 ((00) as) + Σ de (Tx) + E 2 (TL)
max min X T2.
S
Like the Lagrangian method, we can alternately update w, X, and to find the optimal triplet. Consider updating and x by minimizing Li(TT, X, x, 8) at any iteration:
12

---

(7))))))))
min min 2,30
E (-,() [s,a1]
[-
Σ
(veaaa ma))
(eau() aca)
1-1
The inner optimization problem with respect to æ is convex quadratic programming problem with non-negative constraints,
m Σ (T, TT)) x(,))
8 m
z; arg min 2,50
Σ
v C,, xt,e)
The optimal solution is ot. max {0. {0,- 3 (T nx)} Then,
Aes
Aea
(TT) = V (C,,((TR-I,, T&) + oi.; = v (TT-1I TT.) + max
0,
V
(T nk))
B
Aed B
Ae,i
+ V (TC. Th) + max
0,
(Tx,
B
max 0, Aes + (T,, Tkb)
de,
1
Substituting back into Equation (9), we get
m + "22
3 m
x, 1-
E
Σ Ae,
w (TT)
E Prg.h A TT- 1.A.
H
Σ 1=1
dep max f0, de.
v V... Vc..((Te-1.T)))
Ae.
3 m
max 0, dri + 1 +V.., (T,,
de. 2
11
E
[- p(0)) -a-1 (8,a)) a)]
8 2
max (0, dei
Vo (TL-,,,,, mp))
)²
22
g
132
A mo 1.A.
i-1
Hence, finally get
min La (TE X. (3) Khit
H min
9 Σ + (s,
Aoil² >uil²_X;
X7.
E
1-
max 0, (o)
8 ga
This
1-1
Lemma A.3, Consider two problems, Problem (P) and Problem (Q) below. For sufficiently large A X y i and 3 3 for some finite X and finite 3, the optimal solution set of Problem (Q) (equivalent version of Problem (6) is identical to the optimal solution set of Problem (P).
Problem (P):
H
m
3 m
,, =
Σ
E
[-
"(8, P(x)))
+ Σ A (e
Σ w (TT))
h-ta-re-1.
Then,
(Th Ni, 20)
max min Li (TT: X, 3)) A Nk.
Problem (Q)
13

---

m
Li xx,
E
[- p(O))A (s,
(-p(0h)A7--(saa))))) + Σ de,
V Ve.
(T,
P.k.
am Ti 1.A
8
+ 2
C, k Tk, 0)
;
Then,
(Tite Ni. max min L. (TT 29
(Q)
Ne,1.
where x== max(0, and
V
= Σ E
Th- (s, + (TE-) - -d,).
Pak.
h-
Proof. This proof uses some ideas given in [41] for Part below.
Part 1 Solution of Problem (P) is solution of Problem (Q).
Suppose 0, is the optimum of the constrained Problem (P) augmented with the quadratic penalty. Let r be the corresponding Lagrange multiplier vector for its dual problem, and be the additive quadratic penalty coefficient. Then for A > || A i and B > || O is also minimizer of its ReLU ReLU-penalized optimization Problem (Q) as below. Let (2(+)) = >HI E
[- P(0 as. Then it follows
a-Tk-1A
that:
2 ((0.)) + Ar. (1 2 2
Σ v ( ((0))
A. C Re.
Σ c. n Tx. 8)2
> (()))) + Σ ( 11
c, 1 0).
By assumption, 0, is Karush-Kue BhiisshKKKh---- Kuhn-Tucker point the constrained Problem (P), at which KKT conditions are satisfied with the Lagrange multiplier vector À and B. We then have:
((0.) D M.
W 1T.. mA 0)² > ((0))
> ( m.
8
V VC,
2
= =90(0
Σ A. C (
C. (T2-1, mg
2
_
m
((,)) V 8)
Σ a 1 Tx.
where the first line holds because 0, minimizes the Lagrange function, and the second line is derived from the complementary slackness. Thus, we conclude that for the objective function of Problem (Q), call (0c). we have (0.) > (L)()) for all 0, O, which means 0 is minimizer of the quadratic damped optimization Problem (Q).
Part 2 Solution of Problem (Q) is solution of Problem (P).
Let 0g be optimal point of the quadratic damped Problem (Q), with 0g and Ā being the same as defined above. Then, if 0, is in the of feasible solutions Stensible {0 M Th, 0) V i), have:
8 Σ
2(0)) = -(())) + Σ Xe. t C. (TA,1, Th. +)
v C. (T (T Tk,
2
8 m
(((0.)
Σ
Ne, V.V.eeTTT Th,
Σ
V
C. (T T
-(0))
14

---

The inequality above indicates 0g also optimal in the constrained Problem (P). Now, if if not feasible, have:
8 Σ ( ((())) + Σ de, ( The 0)
mr m². =Q(0,)
Σ C. ma 0)
Σ C. m 0).
Σ A. n2. 0)+ =2((6))
Σ
W Vo T2,
< <0(0)
AeVaLa TA. 0)+
Σ
1 (o 0)
* =(()))
Σ J. (TT n2. 8)
Σ
v V. ( 0)2
2(0)) ( m.
(Tk-1, 0y
which is contradiction to the assumption that Bg is minimizer of the penalized optimization Problem (Q). Thus, 0g can only the feasible optimal solution for Problem (P).
Lemma A.A. Consider two problems, Problem (P") and Problem (R). For sufficiently large B > B for some finite B, the feasible optimal solution set of Problem (R) (equivalent version of Problem (3)) is identical to the solution set of Problem (P").
Problem (P)):
H L. (T 2)
1- p(On) (-- (s, Σ (
B m
2
w
(Tk)
PEL.h 1o
2
Then,
(Th 22,
= max min LiP (T x0 A30 ne....
(P')
Problem (R):
L x)) =
1- ((O))) as) aattk-ilh
(ss.(h) + > (esee,
Then,
(Th,e 2;) max min Li L (, AsO
(R)
Proof. Recall that using parameterized policies, hence overload notation as 0 = frequently. Sh-t
For brevity, denote (T)
E
[p(Os) (s, a)]. We will also go back and forth between
Po-. 1.h
the equivalent problems Problem (P") and Problem (6) of the main paper in Section 3.
Part 1. Solution of Problem (R) is solution of Problem (P").
Suppose that x is the optimal feasible policy for the primal Problem (R), which is a Lagrangian version of Problem (3). Consider the corresponding Langrangian dual parameter X of x², which satisfies the KKT conditon,
V VaLii (Ti X", x²) = -
(mt,))
+
X V Wr,s (TT) = 0
and the second-order sufficient condition that for all non-zero vectors u that satisfy uu" T u (TT 0, we have
n LVV L. (mi X', x²)
0
(A)
Compare Equation (R) and Equation (P'), we have,
15

---

V Vadi = x
(Tr..) + 1 V Wi (TT) + 3
Wei (T) V (TT
V (T x3 x²) + 3 Σ
W4s (T W (x²
i=1
where we use (T))(TT)) = (TR,I(T TT') + -/.5 = 00 with the feasible policy n. Moreover,
Vi = Vi (TR..)
+ Σ X V Wiss (TT) + BV we (Λ)) Vaw, (T+)²
-
we (Tz V w (TT))² (Tk,e) X x²) + ,
To prove that ( X*) is strict minimum solution to L. (TT,, X, xz, (3,, we only need to prove the following is true for sufficiently large 3,
ViLi (T X", x", B) > O.
If the above is not true, then for any large 3, there exists u, such that ||ue|| = 1 and satisfies
V u, x
(T X", x²
ue 1/)
u, V. R (T X x²) us + 3 V (Tx T uel" < 0
V (TT T ui I' -u, V (T x²) us 3
Therefore, {un is a bounded sequence and there must be limit point, denoted by û. Then
V We (TT T á V L ( X x²) x = 0.
The above contradicts Equation (A), so the conclusion. Hence, Th is also the optimal feasible policy for the primal-dual Problem (P").
Part 2. Solution of Problem (P') solution of Problem (R).
This part is straightforward since is a standard result. Please see Chapter 2 and Chapter 9 of [9], and Chapter and Chapter 4 of [8] for the proof. For completeness, we provide the result below.
Suppose Th. in the feasible optimal solution set of the primal-dual Problem (P'). Let X* be the corre- sponding dual parameter of -ं.-- Consider Problem (6), which an equivalent version of Problem (P'). For any feasible Ty, we have
L, (T X B) < L, (T. Xr
Now have two cases:
Case 1. When Xi 3
+ (C,, 0, we have
16

---

m
Li (T 3)) - (TRO) +
Σ
%r, C, (T-- (T., TT)) +
Σ
v
C, (
Ni. (*)
8
- +
+ (T
(TE1,,
2
< (fk(
where the last step uses 3 > O, (T T&) < O, and
Aig B
+ (T) 0.
Xid B (T,,((TT-I, O, we have
Case 2. When
(TK, - (T(T) 1 m
x < -
23
Now, combining both cases above, we have Le (TT; 3) 3) & (TA,)) On the other hand, Li [ X3, B) = Li (TT. x" - Thus, the combining all of the above we get
(((aa) La ( X
.) B) & Li (T B) (T2()
Theorem 3.3. Let (3) be solution to Problem (3), and let (v'0² _100' be solution Problem (6).
Then, for sufficiently large > and Ae,; > X V i, 700" is a solution to Problem (6), and x(0 is solution to Problem (3).
Proof. We prove this result as two-step process.
First, we show that the solution sets of the below problems are identical. See Lemma A.3 for the proof.
Problem (P).
H
((n) (8, a)] + Σ de we Wr, + 8
Li ( k X, x.
Σ
E.
Σ w (Tx))
Then,
(Th x;, = max min L. (Tk: A, 3
(P)
X n4,2,000
Problem (Q).
(s, + m
L (T,,,,
E
--
(T- 0).
PmPkt l=s
Th-1.
Σ
Cia T T2, 0)2
2
Then,
(T N xt) = max min L, (,,, 2.
(Q)
Xs0
Second, we show that the solution sets of the below problems are identical. See Lemma A.4 for the proof. Problem (P'):
H
B (TK)
LP (TT A x, 3)
1 - (( + Σ Ne, +
(s,
2 > w (T())
Then,
(Th 2i,
= max min Li (T x3,)
(P')
A te.
17

---

11100
(a) Humanoid
(b) Circle
(c) Reach
(d) Grid
(e) Bottleneck
(f) Navigation
Figure 5: The Humanoid, Circle, Reach, Grid, Bottleneck, and Navigation tasks. (a) Humanoid: The agent is
fast possihle on flat surface, while exceeding a specified speed limit i.c. the cost constraint. (h) Circle: The agent is rewarded for moving a specified circle is penalized if the diameter the circle is larger than some value [3]. (c) Reach: The agent is rewarded for reaching goal while avoiding obstacles (cost constraints) that are placed to hinder the agent [30]. (d) Grid: The agent controls traffic lights in 3x3 road network and is rewarded for high traffic throughput but is constrained to let lights be red for most consecutive seconds [37]. (e) Bottleneck: The agent controls vehicles (red) a merging traffic situation
is rewarded for maximizing the number of vehicles that pass through but is constrained to ensure that white vehicles (not controlled by agent) have "low" speed for no more than 10 seconds [37]. (f) Navigation: The agent is rewarded for reaching the target area (green) but is constrained to avoid hazards (light purple) and impassible pillars (dark purple). The cost for hazards and pillars is different [30].
Problem (R):
[- p(O)) *(s,a)] + + m Σ (m,
Li (kk x:)
x))
Σ
E
Prkkh (Th xz)
Then,
max min L (T x))
(R)
A #e,e.
Now, it follows from equivalency that the optimal solution of Problem (Q) and Problem (R), and hence
Problem (6) and Problem (3), is the same.
A.2 Experiments Revisited
Below detail the experimental attributes that used in benchmarking. See Figure 5 for the environ- ment details. All our experiments are run in the omnisafe module [22].
A.2.1 Environment Details
Comprehensively, our experiments consist of eight tasks ranging from more superficial (Run and Circle tasks) to relatively more stochastic and sophisticated (Bottleneck and Grid tasks), each training different robots. They come from three well-known safe RL benchmark environments, Safe MuloCo, Bullet-Safety- Gym, and Safety-Gym For agents maneuvering on a two-dimensional plane, the cost is calculated as
C(s, a) V
2 + o For agents moving along straight line, the cost is calculated C(s, a) |ual- where Up and , the velocities of the agent in the x and y directions.
Circle This environment is inspired by [3]. Reward is maximized by moving along a circle radius d:
R e o=I_y.2) y,
2 + y² d)
but the safety region Zim is smaller than the radius d : = 1[x > ruml
Navigation This environment is inspired by [30]. Reward is maximized by getting close to the des- tination R = Dist( target, st st-1) Dist (target, st), ), but it yields a cost of +1 when the agent hits the hazard the pillar. The two different types of cost functions returned separately and have different thresholds. In out setting, d, = 25 for the hazard constraint and de 20 for the pillar constraint.
Since the main goal in MuJoCo is to train the robot to locomote on the plane, we call it the "Run" task in our article. Our chosen two robots are the relatively complex types MuJoCo: Ant and Humanoid. OpenAl Gym is open source https://gitubbcoo/oeenagggg
and has documentation
18

---

Hyperparameter
APPO
PDO
FOCOPS
CPPO-PID
TPO
P30
CPO
TRPO-1.
PCPO
Actor Net layers
(32, 32)
(32, 32)
(32, 32)
(32, 32)
(32, 32)
(32, 32)
(32, 92)
(32, 32)
(32; 32)
Critic Ner layers
[32, 32)
(32, 32)
(32, 32)
(32, 32)
(32,
(32, 32)
(32, 32)
(32, 32)
(32, 32)
Activation
tanh
tanh
tanb
tanh
tanh
tanh
tanh
tanh
tanb
Initial sid
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
Diseount
0.99
0.95
0.995
0.995
0.99
0.99
0.99
0.99
0.99
Policy
3e
3e
3e
3e 4
3e
Critic le
3
episodes
500
Steps per epochs
300
Target KL
0.01
0.01
0.01
0.01
0.01
0.01
0.01
KL early slop
True
True
True
True
True
True
False
Fabse
False
Line Search Times
N/A
N/A
NIA
N/A
N/A
N/A
25
25
25
Line Scarch Decay
N/A
N/A
N/A
N/A
N/A
N/A
0.8
0.8
0.8
Proximal clip
0.2
0.2
0.2
0.2
0.2
0.2
N/A
N/A
N/A
Max borizon
200
200
200
200
200
200
200
200
200
Table 3: Hyperparameters used for each baseline.
http::/wwww.gmmibbrrr..... Bullet Safety Gym. The implementation of the Circle task comes from Bullet-safety-Gie -ym (Gronauer 2022), which Stooke, Achiam, and Abbeel (2020) first proposed. The reward dense and increases by the agent's velocity and the proximity the boundary of the circle. Costs are received when the agent leaves the safety zone defined by the two yellow boundaries. The environment open source at
Safety Gym The remaining two tasks, Goal and Button, are from Safery-Gym (Ray, Achiam, and Amodei 2019). Compared Run and Circle tasks, they more stochastic and sophisticated in that agents challenged to maximize the return while satisfying the constraints.
The environment is open source at http://hhhhuooooopppaaaaaatette/
and readers can see OpenAl's
blog at http:///ppenaicccoboooo////st/t/ gyypyygggy//yyyy for more details.
A.3 Agents
For single-constraint scenarios, Point agent is a 2D mass point(A S ) and Ant is an quadruped robot(A S IR).. For the multi-constraint scenario which is modified from OpenAI SafetyGym [30], Sc 228+16-m where in is the number of pseudo-radar (one for each type of obstacles and we two different types of obstacles in the Navigation task) and A S IR2 for a mass point or a wheeled car.
A.3.1 Experimental Details
To be fair in comparison, the proposed e-CPP algorithm and FOCOPS [43] are implemented with same rules and tricks on the code-base of [30].
A.3.2 Hyperparameters
Table 3 shows the hyperparameters of baseline algorithms.
A.3.3 Runtime Environment
All experiments were implemented in Pytorch 1.7 .0 with CUDA 11.0 and conducted on an Ubuntu 20.04.2 LTS with 8 CPU cores (AMD Ryzen Threadripper PRO 3975WX 8-Coresz), 127G memory and GPU cards (NVIDIA GeFFrce RTX 4060 Ti Cards).
A.3.4 Robustness Cost Thresholds
We conducted a set of experiments wherein we study how e-COP effectively adapts to different cost thresholds. For this, use pre-trained e-COP agent, which is trained with particular cost threshold in
19

---

an environment, and test its performance on different cost thresholds within the same environment. Figure 6 illustrates the training curves of these pre-trained agents, and we that while e-COP generalize well across different cost thresholds, other baseline algorithms may require further tuning to accommodate different constraint thresholds.
E-COP
FOCOPS
P30
2100
1100
1000
%g
(a) Humanoid Rewards
(h) Humanoid Costs
(c) Point Circle Rewards
(d) Point Circle Costs
Figure 6: Cumulative episodic rewards and costs of baselines in two enviromments with two different constraint cost
thresholds: 10 and 50 in Humanoid, and and 15 in Point Circle. The hyperparameters tuned at constraint limit of 20 Humanoid and 10 in Point Circle.
20

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We make claims on developing the theory for episodic policy optimization for CMDPs and on presenting experimental validation of our approach. Please see Sections 3 and 4.
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 contri- butions 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 motivation long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: While there are no algorithmic limitations, potential limitations can occur while applying work to very high dimensional real-life scenarios, for instance, in large language models or the denoising process in image and video diffusion tasks. We have developed this work with the above two applications in mind, and plan to explore that direction of future research.
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 encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results 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 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex: system might not 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, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We have provided the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https:/nnips cc/ cc/public/
Saallss/CodSSubmsssionnn
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: (CodeSummissionnnnn
//nips. httppssccppullc///eeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We detail our experimental procedure and details in Sections 4 and A.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report eтror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All results reported with standard deviation across multiple seeds. Please see Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
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 (c.g., Normally distributed errors).
23

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 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.
8. 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: In Section A.2 we detail the compute resources used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //nerrip cctppubiie/tthiiceelddddd..eeeed
Answer:
[Yes]
Justification:
We have read the code of ethics and our work satisfies it in every respect.
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 deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
In the Introduction Section we detail the potential applications of our work.
Guidelines:
The answer NA means that there 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 unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairesss 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, alone deployments. However, if there 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 that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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, mecha- nisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our work needs no such safeguards for responsible release of assets.
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: [NA]
Justification: We do not use existing assets. Proper references for existing results and algorithms are provided throughout the main text.
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.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi wwwwwetthod..... com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
25

---

Answer: [NA]
Justification: We do not release new assets. Our results, both theoretical, algorithmic, and empirical, are properly referenced and explained in the main text.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
We do not use crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
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 this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
26


Reviews:
[{"review_id": "kj4k5cN3G1", "reviewer": "Reviewer_kuft", "summary": "The authors introduce a policy optimization algorithm for episodic constrained RL problems, e-COP. In general, Lagrangian formulation is used for constrained optimization problems, however, the constraints are not always satisfied in real world applications. The solution approach avoids Hessian matrix inversion. The algorithm approach uses deep learning-based function approximation, a KL divergence-based proximal trust region and gradient clipping popular in improving the generalization and avoiding vanishing gradients in proximal policy optimization algorithms. The authors use SafeGym to benchmark their algorithm against the state-of-the-art algorithms such as PPO, FOCOPS, CPO, PCPO, and P3O.", "questions": "I would like to know whether any hyper-parameter tuning has been done for the baseline algorithms? It is possible that the Lagrangian formulation may perform better after tuning.", "limitations": "The authors do not adequately address limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The e-COP algorithm in most cases outperforms all other baseline algorithms but fails on Humanoid, AndReach, and Grid where it provides the second best optimal results. The authors used an extensive set of baselines -- few using Lagrangian approximations. \n\nThe idea is original. In general, the paper is well-written and clear. There are few grammatical errors and typos.", "weaknesses": "The authors do not talk about the limitations of the algorithms. There is a mention on the complexity of the Grid environment resulting the e-COP not to perform as best. It will be good for the completion of the paper to have a short section on limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments on originality, and well-written exposition. We will fix any grammatical issues and typos. We do want to point out that while the algorithm does not perform the best on Humanoid, AntReach, and Grid, it still performs the second best on these three while performing the first best on the other five environments. Response to concerns below:\n\nWith regards to the weaknesses, while there are no fundamental weaknesses, we shall include a section on limitations in the next version, wherein we will discuss the scalability issues we faced in the Grid environment. Since the application in mind for this paper is in diffusion models, we plan to conduct research and experiments in this direction to ascertain e-COP’s capabilities.\n\nFor the baselines, some hyperparameter tuning has indeed been done, and we provide the hyperparameter values in the Appendix, which are set based on the best performing parameters for each algorithm. We refer to standard codebases that are widely used for benchmarking algorithms [1], [2]. Note that we have done similar hyperparameter tuning for the Lagrangian formulation, PPO-L (and the other algorithms) as well. The gains in performance are not because of hyperparameter tuning but from the fact that the constrained problem formulation is the right fit for the problem. \n\nWe thank the reviewer for their review, and the many comments that have helped improve the paper substantially. If the reviewer is satisfied, we would appreciate reconsideration of their current score.\n\n\n[1] omnisafe: https://github.com/PKU-Alignment/omnisafe\n\n[2] FSRL: https://github.com/liuzuxin/FSRL/", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8M6ei1hvbL", "reviewer": "Reviewer_4GCx", "summary": "The paper proposes a new algorithm for finite-horizon constrained RL problems. The algorithm is based on three ideas: PPO-like updates for the finite-horizon setting, P3O-like treatment of constraints with adaptive penalty coefficient, and quadratic damping penalty. The proposed algorithm outperformed previous algorithms in some benchmark tasks.", "questions": "- Does the proposed algorithm what Algorithm 2 states? Algorithm 2 suggests to save policy parameters for each time step, which sounds to be unusual.\n- I looked into the code, but it seems it will not run since `_episodic_reward_loss` and `_get_surr_cadv` methods  are undefined. I checked if the Github repo of omnisafe, but I cannot find those functions. Is the code intended only for reference? (Indeed the code is provided as a text file, not python file.)\n- I currently think the main contribution of the paper is the introduction of quadratic penalty dumping to safe RL. Therefore I would like to see results of ablation studies to prove the importance of quadratic penalty dumping. Is there any result? (Or am I missing?)", "limitations": "If the proposed algorithm really does what Algorithm 2 states, there is an issue of huge memory requirement as the horizon gets larger. I think it should be discussed. Otherwise I do not see any potential negative societal impact.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "A strong empirical performance of the proposed algorithm. The introduction of quadratic damping penalty to safe RL seems to be a new idea. The paper is easy to follow except some typos.", "weaknesses": "Performance difference lemma for the finite-horizon setting is already known. See Kakade's thesis. Since PPO-like update is based on the performance difference lemma and PPO's idea, I do not see it is novel. P3O-like treatment of constraints with adaptive penalty coefficient is also not novel.\n\nThere are some parts I do not really understand. In particular I wonder if the proposed algorithm really does what Algorithm 2 states. Concretely Algorithm 2 suggests to save policy parameters for each time step, which sounds to be unusual. (Also I guess Line 6 of the algorithm has a type: $\\pi_{k, t} \\gets \\pi_{k, t+1}$ should be $\\pi_{k, t} \\gets \\pi_{k-1, t}$.)\n\nIf the algorithm is implemented as above, it is unfair to compare to previous algorithms, because previous algorithms use a much fewer number of parameters. If the algorithm is not implemented as above, there is a serious issue in presentation.\n\nEq 8 seems to contain many typos. For example $\\min_{\\pi_{k, t}} L(\\theta, \\lambda, \\beta)$ does not make sense since the loss do not have $\\pi_{k, t}$. (Sorry for the sloppy notation, but I believe the authors can understand what I mean.) Also $\\pi_{k, t}^\\star = \\min_{\\pi_{k, t}} L(\\theta, \\lambda, \\beta)$ does not make sense since $\\min_{\\pi_{k, t}} L(\\theta, \\lambda, \\beta)$ is a scalar.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for comments on the novelty of the theory and strong empirical performance. Responses below:\n\nFirst please note that as far as we know this is the first policy optimization algorithm for the constrained or unconstrained setting as far as we know. Second, all policy optimization algorithms are based on a policy difference lemma, and so ours is not novel: we weren’t aware that for the episodic setting, it was already available in Kakade’s thesis. We will acknowledge and cite. We acknowledge that the penalty based constraints treatment is not novel. However, how to incorporate this treatment into episodic settings was unknown, as was how to update the policy network in the finite horizon setting. \n\nNote that we have a time-dependent policy (hence parameters are saved at each step). This is not a bug but a feature as stationary policies for the episodic setting are known to be sub-optimal. Line 6 of Algorithm 2 is correct, since we use the idea of backward recursion as is done in the classical dynamical programming algorithms. So, while it is true that our model stores a higher number of parameters, it is because this is needed for the episodic setting (stationary policies are suboptimal, nevertheless, if any one wishes to use our algorithm to find a stationary policy (with fewer parameters, it is quite straightforward to do so). \n\nThe concern of fairness of comparison to these other algorithms designed for non-episodic settings is valid. Nevertheless, these are the closest baselines available and we show that their usage in the episodic setting will result in subpar performance (Also, we anticipated that reviewers will want to see comparison to such baselines even if they are not designed for this setting.). No other PO algorithms, with fewer or more parameters can perform as well as e-COP. \n\nThe loss indeed has the minimizing variable, which is hidden in the importance sampling ratio as defined after Equation (4). We can make this distinction clear in the next draft. You are right in saying that the $\\texttt{min}$ is incorrect, it is a typo, and it should be $\\texttt{argmin}$, which we will also fix. Thank you for pointing this out.\n\n*Ques 1*: Yes, Algorithm 2 as stated is correct. Please see above.\n\n*Ques 2*: Yes, we had to code the two functions you mentioned, and we use commit SHA $\\texttt{d55958a011df7800f256452e07811832cd2524d2}$ of omnisafe to run our experiments. The implementation of $\\textunderscore get \\textunderscore surr \\textunderscore cadv$ function is based on the docs module in omnisafe.\n\n*Ques 3*: We have included ablation studies on the effect of the quadratic penalty in Section 4.2 with further details in Appendix A.3.4.\n\nWe thank the reviewer for their review, and the many comments that have helped improve the paper substantially. If the reviewer is satisfied, we would really appreciate reconsideration of their current score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MVehUpXppw", "reviewer": "Reviewer_p2dY", "summary": "In this paper, the authors propose a policy optimization algorithm for constrained Reinforcement Learning (RL) problem in a finite horizon setting. First, the authors develop a policy difference lemma for the finite horizon MDP problem. Following that, the authors combine a set of ideas to propose the e-COP algorithm. The authors show that the proposed algorithm is numerically much stable compared to the state-of-the-art solutions. Optimality of the proposed scheme is established under certain assumptions. Extensive simulations have demonstrated that the performance of the algorithm is better than existing methods.", "questions": "1. The idea of using a quadratic penalty term to improve the stability near the edge of the constraint set boundary is a purely heuristic based approach. Is there any strong theoretical argument supporting such a choice?\n\n2. In the related work section, the authors have discussed about drawbacks of using penalty terms in existing methods. Are these drawbacks applicable to the scheme proposed in the paper?\n\n3. It is not clear how the time-dependent state occupation distribution is computed. The idea of approximating $\\rho_{\\pi}$ by the empirical distribution from the policy of the previous episode does not appear to be a good approximation. Although such approach may work well in infinite horizon problems where the optimality of stationary policy holds, it may not work well in the finite horizon setting.\n\n4. The approach of using the second order penalty is not very novel and is widely used in practice for practical RL algorithms. What is the novelty of the proposed approach?\n\n5. The idea of allowing the agent to act in a constrained manner even before the constraint is violated may lead to suppression in the original objective function. In other words, when the constraint is not too tight, the proposed scheme may unnecessarily impose additional level of constraint on the system.\n\n6. How to ensure that we have sufficiently large $\\beta$ and $\\lambda_{t,i}$ which are well above the given lower bounds? The adaptive parameter selection process is just a heuristic.\n\n7. The symbol in the last term of equation (7) is not clearly defined.\n\n8. The algorithm proposed in the paper is an amalgamation of many ideas. Many of these ideas involve approximation and many are just driven from intuition without any formal guarantee of optimality. It is hard to see how this fusion work together in theory (e.g., satisfying the conditions given in Theorem 3.3).", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-written and easy to follow. The results and claims presented in the paper appears to be correct.", "weaknesses": "The idea of using a quadratic penalty term to improve the stability near the edge of the constraint set boundary is a purely heuristic based approach. The idea of approximating $\\rho_{\\pi}$ by the empirical distribution from the policy of the previous episode does not appear to be a good approximation. The idea of allowing the agent to act in a constrained manner even before the constraint is violated may lead to suppression in the original objective function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for comments on exposition and correctness. Responses below:\n\nWe disagree with the reviewer on the weakness mentioned:\n\n(i) Calling introduction of quadratic penalty as purely heuristic minimizes the utility of such ideas that have proven to be central in making optimization algorithms practically useful. In optimization literature, it is a well known technique to improve numerical stability, and in fact our theoretical analysis for Theorem 3.3 accounts for it. See more under Q1. \n\n(ii) The idea of approximating $\\rho_{\\pi}$ by empirical distribution from the previous episode’s policy is again in the same spirit: Following a principled approach and yet introducing a series of good approximations that make the algorithm practical and yet, result in good or better performance. This is what has made PO algorithms so powerful that they are at the heart of most training of GenAI models (LLMs or Diffusion models) and find widespread usage on a daily basis.\n\n(iii) We have difficulty understanding the reviewer’s comment “ ... acting in a constrained manner even before the constraint is violated ... ”. Since the constraints depend on the entire episode, if you do not design policies that account for the constraints, then it may be too late to act to enforce them if you see the constraints are getting violated. Please do note that once the policy is designed as per our algorithm, there is no need for `constraint enforcement’. We have a guarantee (Theorem 3.3) that they will be satisfied.\n\n*Q1.* We respectfully, and strongly disagree that the introduction of quadratic penalty is purely heuristic. Our main result (text leading up to Theorem 3.3 and the theorem itself) talks about this very point. We theoretically prove that this attached quadratic penalty is an exact penalty from the primal problem in the constructed primal-dual problem. Thus, the constructed multiplier-penalty function is equivalent to the primal constrained problem to provide continuous and precise cost control. We mention in Lines 191-195 how the addition of the quadratic penalty theoretically helps the agent in more effective constraint control than its counterpart, the post-violation penalty approach.\n\n*Q2.* No they are not applicable. The only possible bottleneck in e-COP is the scalability, which can potentially be seen in some experiments. e-COP still promises to be a strong candidate for a safe RL baseline.\n\n*Q3.* You are correct in raising this concern. This has already been addressed in [1], which allows us to use such an approximation. Our extensive experiments on many environments showcase the ability of e-COP to outperform other SOTA baselines, so this approximation is even empirically proven to work.\n\n*Q4.* We do not use a second order penalty in our approach, we only deal with the expectation, which is first order. We have addressed the novelty of our work in Lines 57-68. Please see.\n\n*Q5.* To address this concern, we use an adaptive damping penalty that is instance dependent, adapts to the environment, and does not act “too safely”. This approach is discussed starting on Line 219, and ablation studies in Section 4.2 are also performed that show the effectiveness of our approach.\n\n*Q6.* For initial feasible parameters, we do a linesearch [2]. After initial feasible parameters, we update them as in Algorithm 2. Please go through the Appendix to see the theoretical justification, which we have provided in plenty. For your convenience, we provide it here as well:\n\nThe gradient of $\\mathcal{L}\\_{t}(\\mathbf{\\pi}_{k}, \\mathbf{\\lambda}, \\beta)$ takes the form \n\n$\\nabla\\_{\\pi}\\mathcal{L}\\_{t}(\\mathbf{\\pi}\\_{k},\\mathbf{\\lambda},\\beta)=\\nabla\\_{\\pi}\\sum\\_{h=t}^{H}\\mathbb{E}\\_{s\\sim\\rho\\_{\\pi\\_{k,h}};a\\sim\\pi\\_{k-1,h}}\\big[-{\\rho(\\theta\\_{h})}A^{\\mathbf{\\pi}\\_{k-1}}\\_{h}(s,a)\\big]+\\Sigma\\_{\\Psi\\_{C\\_{i},t}(\\mathbf{\\pi}\\_{k-1},\\mathbf{\\pi}\\_{k})\\geq-\\frac{\\lambda\\_{t,i}}{\\beta}}\\left(\\lambda\\_{t,i}+\\beta\\Psi\\_{C_{i},t}(\\mathbf{\\pi}\\_{k-1},\\mathbf{\\pi}\\_{k})\\right)\\nabla\\_{\\pi}\\Psi\\_{C_{i},t}(\\mathbf{\\pi}\\_{k-1},\\mathbf{\\pi}\\_{k})$\n\nSuppose $(\\pi^{\\star},\\mathbf{\\lambda}^{\\star})$ is the optimal policy and its corresponding dual parameters. Consider KKT condition to $(\\pi^{\\star},\\mathbf{\\lambda}^{\\star})$ of the undamped problem (Eq. (5) with $\\beta=0$):\n\n$\\nabla\\_{\\pi}\\mathcal{L}\\_{t}(\\pi^{\\star},\\mathbf{\\lambda}^{\\star})=\\nabla\\_{\\pi}\\sum\\_{h=t}^{H}\\mathbb{E}\\_{s\\sim\\rho_{\\pi_{k,h}};a\\sim\\pi_{k-1,h}}\\big[-{\\rho(\\theta_{h})}A^{\\mathbf{\\pi}\\_{k-1}}\\_{h}(s,a)\\big]+\\Sigma\\_{i}\\lambda\\_{t,i}^{\\star}\\nabla\\_{\\pi}\\Psi\\_{C_{i},t}(\\mathbf{\\pi}\\_{k-1},\\mathbf{\\pi}^{\\star})$.\n\nSince the above two equations are consistent for the optimal point $(\\pi^{\\star},\\mathbf{\\lambda}^{\\star})$ as shown in Theorem 3.3, we can relate the constraint violation nearby this optimal point as $\\max\\left(\\Psi\\_{C_{i},t}(\\mathbf{\\pi}\\_{k-1},\\mathbf{\\pi}\\_{k-1}),-\\frac{\\lambda_{t,i}^{(k-1)}}{\\beta^{(k-1)}}\\right)\\approx\\frac{\\lambda\\_{t,i}^{\\star}-\\lambda\\_{t,i}^{(k-1)}}{\\beta^{(k-1)}}$.\n\nThis means we can reduce the constraint violations of the policy iteration close to the optimal point by reasonably increasing $\\beta$. Based on this, we remove the Lagrange dependency in Eq. (7) and postulate the adaptive parameter selection procedure.\n\n*Q7.* It is clearly defined, please see Line 181.\n\n*Q8.* Most if not all SOTA PO safe RL algorithms require approximations (please see the related works section). We don’t understand what you mean by “hard to see in theory”? We have provided theoretical justifications for the development of e-COP (Section 3) and our main result Theorem 3.3 exactly deals with the feasibility of our approach, which is extensively validated by our experiments.\n\nWe hope these answers address your concerns, and really hope that you consider raising your score.\n\n[1] Bojun, Huang. \"Steady state analysis of episodic reinforcement learning.\" NeurIPS 2020. \n\n[2] Achiam, Joshua, et al. \"Constrained policy optimization.\" ICML 2017", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The manuscript presents e-COP a novel policy optimization algorithm for constraint episodic Reinforcement Learning (RL). e-COP combines ideas from constrained numerical optimization and proposes a practical algorithm. Overall, the paper is well-written, extensive experiments are provided and the performance of e-COP is solid.

A few minor issues:
- The authors should discuss the limitations of their approach in more detail in the text
- A few words about fairness of comparisons in the text would be appreciated
- Releasing the source code is important

Despite the above minor issues and some novelty issues, most reviewers (and myself) believe that e-COP can be a valuable contribution to the RL community. As such I recommend "Accept (poster)".
Decision: Accept (poster)