State-wise Constrained Policy Optimization
Authors: Weiye Zhao
Rui Chen
Yifan Sun
Feihan Li
Tianhao Wei
Changliu Liu
Venue: Accepted by TMLR ()

Abstract: Reinforcement Learning (RL) algorithms have shown tremendous success in simulation environments, but their application to real-world problems faces significant challenges, with safety being a major concern. In particular, enforcing state-wise constraints is essential for many challenging tasks such as autonomous driving and robot manipulation. However, existing safe RL algorithms under the framework of Constrained Markov Decision Process (CMDP) do not consider state-wise constraints. To address this gap, we propose State-wise Constrained Policy Optimization (SCPO), the first general-purpose policy search algorithm for state-wise constrained reinforcement learning. SCPO provides guarantees for state-wise constraint satisfaction in expectation. In particular, we introduce the framework of Maximum Markov Decision Process, and prove that the worst-case safety violation is bounded under SCPO. We demonstrate the effectiveness of our approach on training neural network policies for extensive robot locomotion tasks, where the agent must satisfy a variety of state-wise safety constraints. Our results show that SCPO significantly outperforms existing methods and can handle state-wise constraints in high-dimensional robotics tasks.

Published in Transactions on Machine Learning Research (04/2024)
State-wise Constrained Policy Optimization
Weiye Zhao
wekyesha eduu
Robotics Institute
Carnegie Mellon University
Rui Chen
ruicSSandreus cmnu. edu
Robotics Institate
Carnegic Mellon University
Yifan Sun
vifanssn22@nndveu.cmm.c.
Robotics Institute
Cornegie Mellon University
Feihan Li
feihan/Sanddrew. cmau. edu
Robotics Institute
Cornegie Mellon University
Tianhao Wei Robotics Institute
twei2Sandrew. www. edu
Cornegie Mellon University
Changliu Liu
diub@onnree.cmm..o
Robotics Institute
Curnegie Mellon Universily
Reviewed on OpenReview: https: openrewiewww net/ forun? id= NgNggtttm
Abstract
Reinforcement Learning (RL) algorithms have shown tremendous success simulation environments, but their application real-world problems faces significant challenges, with safety being major concern. In particular, enforcing state-wise constraints is essential for many challenging tasks such as autonomous driving and robot manipulation. However, existing safe RL algorithms under the framework of Constrained Markov decision process (CMDP) do not consider stale-wise constraints. To address this gap, we propose State-wise Constrained Policy Optimization (SCPO), the first general-purpost policy search algorithm for state-wise constrained reinforcement learning. SCPO provides guarantees for stato-wisc constraint satisfaction in expectation. In particular, we introduce the framework of Maximum Markov decision process, and prove that the worst-case safety violation is bounded under SCPO. We demonstrate the effectiveness of our approach on training neural network policies for extensive robot locomotion tasks, where the agent must satisfy a variety of state-wise safety constraints. Our results show that SCPO significantly performs existing methods and can handle state-wiss constraints high-dimensional robotics tasks.
1 Introduction
Reinforcement learning (RL) has achieved remarkable progress in games and control tasks (Mnih et al. 2015 Vinyals et al. 2019 Brown & Sandholm 2018). However, one major barrier that limits the application RL algorithms real-world problems the lack of safety assurance. RL agents learn to make mwward-mxiimiiing decisions, which may violate safety constraints. For example, an RL agent controlling self-driving car may receive high rewards by driving high speeds but will be exposed to high chances of collision. Although the

---

Published in Transactions on Machine Learning Research (04/2024)
reward signals can be designed to penalize risky behaviors, there is no guarantee for safety. In other words, RL agents may sometimes prioritize maximizing the reward over ensuring safety, which can lead to unsafe or even catastrophic outcomes (Gu et al., 2022).
Emerging in the literature, safe RL aims to provide safety guarantees during or after training. Early attempts have been made under the framework of constrained Markov decision process, where the majority of works enforce cumulative constraints or chance constraints (Ray et al. 2019 Achiam et al. 2017 Liu et al., 2021). In real-world applications, however, many critical constraints are instantaneous. For instance, collision avoidance must be enforced at all times for autonomous cars (Zhao et al., 2023 Another example is that when robot holds a glass, the robot can only release the glass when the glass is on a stable surface. The violation of those constraints will lead to irreversible failures of the task. In this work, we focus on state-wise (instantaneous) constraints.
The State-wise Constrained Markov decision process (SCMDP) is novel formulation in reinforcement learning that requires policies to satisly slate-wise constraints. Unlike cunulative or probabilistic constraints, state-wise constraints demand full compliance at each time step as formalized by Zhao et all (2023). Existing state-wise safe RL methods can be categorized based on whether safety is ensured during training. There is a fundamental limitation that it is impossible to guarantee hard state-wise safety during training without prior knowledge of the dynamic model. In a model-free setting, the more feasible approach is to statistically learn to satisfy state-wise constraints using as few samples as possible. Our paper concentrates on achieving state-wise constraint satisfaction in expectation.
We aim to provide theoretical guarantees on expected state-wise safety violation and worst case reward degradation during training. Our approach is underpinned by key insight that constraining the maximum violation is equivalent to enforcing state-wise safety. This insight leads to novel formulation of MDP called the Mazimum Markov decision process (MMDP). With MMDP, we establish a new theoretical result that provides a bound on the difference between the maximum cost of two policies for episodic tasks. This result expands upon the cumulative discounted reward and cost bounds for policy search using trust regions, as previously documented in literature (Achiam et al. 20177. We leverage this result to design a policy improvement step that not only guarantees worst-case performance degradation but also ensures state-wise cost constraints. Our proposed algorithm, State-wise Constrinedd Policy Optimization (SCPO), approximates the theoretically-justfieee updale, which achieves state-of-the-arl trade-off between safety and performance. Through experiments, we demonstrate that SCPO effectively trains neural network policies with thousands of parameters on high-dimensional simulated robot locomotion tasks; and is able to optimize rewards while enforcing state-wise safety constraints. This work represents a significant step towards developing practical safe RT, algorithms that can be applied to many real-world problems. Our code is available on Githul
2
Related Work
2.1 Cumulative Safety
Cumulative safety requires that the expected discounted return with respect to some cost function is upper- bounded over the entire trajectory. One representative approach is constrained policy optimization (CPO) (Achiam et al. 2017), which builds on a theoretical bound on the difference between the costs of different policies and derives a policy improvement procedure to ensure constraints satisfaction. Another approach is interior-point policy optimization (IPO) (Liu et al., 2019), which augments the reward-naximizing objective with logarithmic barrier functions penalty functions to accommodate the constraints. Other methods include Lagrangian methods (Ray et al. 2019) which use adaplive penalty coelficients to enforce constraints and projection-basee based constrained policy optimization (PCPO) (Yang et al. 2020a) which projects trust-region policy updates onto the constraint set. Although our focus is on a different setting of constraints, existing methods are still valuable references for illustrating the advantages of our SCPO. By utilizing MMDP, SCPO breaks the conventional safety-reward trade-off, which results stronger convergence of state-wise safety constraints and guaranteed performance degradation bounds.
2

---

Published in Transactions on Machine Learning Research (04/2024)
2.2 state-wise Safety
Hicrarchical Policy One way enforce state-wise safcty constraints to use hicrarchical policies, with an RL policy generating ewwrdd-aximmzing actions, and safety monitor modifying the actions to satisfy state-wise safety constraints (Zhao et al., 2023). Such approach often requires perfect safety critic to function well. For example, conservative safety critics (CSC) [Bharadhwaj et al. 2020) propose safe critic Qc(s, a), providing conservative estimate of the likelihood of being unsafe given a state-action pair. If the safely violation exceeds a predefined threshold, a new action is re-sampled from the policy until it passes the safety critic. However, this approach is consumin.....g. On the other hand, optimization based methods such as gradient descent or quadratic programming can be used to find a safe action that satisfics the constraint while staying close the reference action. Unrolling safety layer (USL) (Zhang et al., 2022b) follows a similar hierarchical structure as CSC but performs gradient descent on the reference action iteratively until the constraint is satisfied based on learned safety critic Qc(s, a).. Finally, instead of using gradient descent, Lyapunov-bass policy gradient (LPG) (Chow et al., 2019) and SafeLayer (Dalal et al. 2018) directly solve quadratic programming (QP) to project actions to the safe action set induced by the linearized versions of some learned critic Qc(s, a). All these approaches suffer from safety violations due to imperfect critic Qc(s, a), while those solving QPs further suffer from errors due to the linear approximation of the critic. To avoid those issues, we propose SCPO as an end-to-end policy which does not explicitly maintain a safety monitor.
End-to-End Policy End-to-end policies maximize task rewards while ensuring safety at the same time. Related work regarding siste-wise safely aller convergence has been explored recently. Some approaches (Liang et al. 2018 Tessler et al. 2018) solve a primal-dual optimization problem to satisfy the safety constraint in expectation. However, the associated optimization is hard in practice because the optimization problem changes at every learning step. Bohez et al. (2019) approaches the same setting by augmenting the reward with the sum of the constraint penalty weighted by the Lagrangian multiplier. Although claimed state-wise safety performance, the aforementioned methods do not provide theoretical guarantee and fail to achieve near-zero safety violation in practice. He et al. (2023) proposes AutoCost to automatically find appropriate cost function using evolutionary search over the space of cost functions as parameterized by simple neural network. It is empirically shown that the evolved cost functions achieve ncar-zero safcty violation, however, no theoretical guarantee is provided, and extensive computation is required. FAC (Ma et al. 2021 does provide theoretically guaranteed state-wise safety via parameterized Lagrange functions. However, FAC replics on strong assumptions and performs poorly in practice. To resolve the above issues, we propose SCPO as an casy-to-implement and thcoretically sound approach with no prior assumptions on the underlying safety functions.
3 Problem Formulation
3.1 Preliminaries
In this paper, we are especially interested in guaranteeing safety for episodic tasks, which falls within in the scope of finite-horizon Markov decision process (MDP). An MDP is specified by tuple AS,A,7 R, P, P),, where S is the state space, and A is the control space, R S x A + IR is the reward function, 0 S Y 1 is the discount factor, u:: u:S. S + R is the initial state distribution, and P S x A x S + R is the transition probability function. P(s'ls,a) a) is the probability of transitioning to state s' given that the previous state was s and the agent took action a at state s. A stationary policy π : S + P(A) is a map from states to a probability distribution over actions, with (a]s) denoting the probability of seleeting action in state s. We denote the set of all stationary policies by II. Subsequently, we denote Ty as the policy that is parameterizod by the parameter 0.
3

---

Published in Transactions on Machine Learning Research (04/2024)
The standard goal for MDP is to learn policy that maximizes performance measure To( which is computed via the discounted sum of reward:
To(m) = BTTT
r R(si, 04, 8+11)
(1)
where H E N is the horizon, 7 (80, d0, 81, "1."..
.... and ~ is shorthand for that the distribution over trajectories depends on 30 ,,, ar ~ TT- (t))s)), sc+1 ~ P(-(sc,
3.2 Stste-wise Constrained Markov Decision Process
A constrained Markov decision process (CMDP) is an MDP augmented with constraints that restrict the set of allowable policies. Specifically, CMDP introduces set of cost functions, C1, ,., Cm, where C; :::S S x A S + maps the state action transition tuple into a cost value. Analogous to equation we denote
H
= =
Σ
7iisss ae, S1-1) ......... m.
(2)
1==
as the cost measure for policy и with respect to cost function C. Hence, the set of feasible stationary policies for CMDP is then defined as follows, where d; E R::
Ic { E II ViE 1, ,,, mc, s d.).
(3)
In CMDP, the objective is to select feasible stationary policy To that maximizes the performance measure:
max Jo(T), s.t. E ITc.
(4)
In this paper, interested in special type of CMDP where the safety specification is to persistently satisfy a cost constraint at every step (as opposed to constraint of cumulative discounted cost sum over trajectories), which we refer to as Slate-wise Constrained Markov decision process (SCMDP). Like CMDP, SCMDP uses the set of cost functions C2,C2, CC to evaluate the instantaneous cost state action transition tuples. Unlike CMDP, SCMDP requires the cost. for every state action transition to satisfy a constraint. Hence, the set of feasible stationary policies for SCMDP is defined
Ic (a E Vi 1,...,m. B(s [Ci(st, at s(+1)] S w/}
55)
where E R. Then the objective for SCMDP is to find feasible stationary policy from He that maximizes the performance measure. Formally,
max Jo(T), s.t. π E Te
(6)
1+70+ The validity of Ic Ic is demonstrated through the selection of d, w. 1-7 in Equation 44 This indicates that stationary policies feasible for SCMDP are also applicable to CMDP: however, the re- verse is not assured. As a result, policies within II offer a higher level of safety, ensuring that (eonaneee [C((se, at $1+1)] for each state bounded- a condition not guarantoed by CMDP.
3.3 Maximum Markov Decision Process
Note that for equation 6 each state-action transition pair introduces a constraint, leading to a complexity that increases nearly cubically as the MDP horizon (H) grows, even when tackled by the fastest algorithms (Cohen et al.) 2021 (The detailed SCMDP complexity analysis is summarized in Appendix A Thus it's
intractable solve using conventional reinforcement learning algorithms. Our intuition is that, instead of directly constraining the cost of each possible state-action transition, we can constrain the expected maximum state-wise cost along the trajectory, which is much easier solve.
4

---

Published in Transactions on Machine Learning Research (04/2024)
M
Do
M
Do
4
Cost
Cost
Cost
D
DD5
D4
D4
D3
D3
M
D2
D2
D2
D
D
D
Time Step
Time Step
Time Step
Figure 1: Intuition of the maximum state wise cost: The three figures above illustrate the evolution of the maximum state-wise cost, denoted as M (shown by the red line), across a single episode. The orange curve represents the state-wise cost, while the green lines with arrows labeled as D indicate the increments of M at each step. Steps with D = 0 are not labeled in the figures.
The key challenge lies efficiently computing the maximum state-wise cost, leveraging the cumulative summation nature inherent MDP. To achieve this, we introduce a tag (M) that travels along the trajectory, logging the maximun state-wise cost encountered so far. Whenever higher state-wise cost identified, M is updated by adding an increment (D), ensuring it consistently reflects the maximum state-wise cost. This tagging mechanism maintains desirable summation characteristic, facilitating subsequent solutions based on established theoretical results from MDP. This intuition is illustrated in Figure D
Following that intuition, we define a novel Macimam Markov decision process (MMDP), which further exlends CMDP via (i) a set of up-to-now maximum state-wise costs M [M1 ... .MM] where M, E M, C R, and (ii) a set of cost increment functions, D1, D2. Dm, where D; (S,,,) A x S - [o, maps the augmented state action transition tuple into non-negative cost increment. We define the augmented state á = (s,M) E (S,MT)= = S, where S is the augmented state space with M (M1 .MM) Formally,
Di( ar S441) = max(Ci(ss ae, 8141)
Mr. E m.
By setting (5 expected marimum stote-wise cost (or D.-return) for n:
ao, o,, 81) Cs(su, ao, $1), we have Ma = Ek= Dr ($ ax, $x+1) for t 2 1. Hence, we define
H Σ
(T) ETAT
Di , ii......
(8)
Importantly, equation [is the key componiet of MMDP and differs our work from existing safe RL approaches that are based on CMDP cost measure equation 2 With equation g equation G can be rewritten as:
maxJ(x), s.t. ViE 1, ",,,,, Jm.JD.
wi.
(9)
where J(x)= = E Ei 7d a( Se+1) and R(8, a, 8') = R(s,a, With R(T) being the discounted return of trajectory, we define the on-policy value function (T = E [R(r)]&o $), the on- policy action-value function AT a) = ()) (S) Lastly, we define on-policy value functions, action-value functions, and advantage functions for the cost increments in analogy to V", Q=, and A5, with D, replacing R, respectively. We denote those by Vg, Q7, and AT.
(), = Er>r(
8,40 a), and the advantage function
4 State-wise Constrained Policy Optimization
To solve large and contimuus MDPs, policy search algorithms scarch for the optimal policy within a set HI C II of parametrized policies. In local policy search (Peters & Schaal 2008), the policy is iteratively updated by maximizing [(T) over a local neighborhood of the most recent. policy Zg- In local policy search
5

---

Published in Transactions on Machine Learning Research (04/2024)
for SCMDPs, policy iterates must be feasible, optimization is over IIg Nile. The optimization problem is:
argmax J(T), Felly
(10)
#k+1
s.t. Dist(a, T&k S 8, JD. (T) S Wi, 1, m.
where Dist is some distance measure, and
a slep size. For actual implementation, we need evaluate the constraints first in order to determine the feasible set. However, is challenging to evaluate the constraints using samples during the learning process. In this work, we propose SCPO inspired by trust region optimization methods (Schulman al. 2015). SCPO approximates equation 10 using (i) KL divergence distance metric Dist and (ii) surrogate functions for the objective and constraints, which can be easily estimated from samples on тk. Mathematically, SCPO requires the policy update at each iteration to be bounded within a trust region, and updates policy via solving the following optimization:
Th+1 = argmax E [A (s,a))
(11)
"Ells
Brud
s.t. Egadi (TKI(TT||TA) S
[n.
E Srud awn
Ap, (8) +HH 1)EB, V 2
[ wi, ,
where Dxz(= is KT. divergence between two policy (It', TT) at state 8, the set for e Ho Ex [T]((T][m)(8]] 8} called trust region, d = (1 - (1-7))D PP P(s. 8)m)), d= = Et P and D. ( [4 (8, a)]l- We then show that SCPO guarantees (i) worst case maximum state-wise cost violation, and (ii) worst case performance degradation for policy update, by establishing new bounds on the difference in returns between two stochastic policies æ and x' for MMDPs.
Theoretical Guarantees for SCPO We start with the thcoretical foundation for our approach, i.c. a new bound the difference in state-wise maximum cost between two arbitrary policies. The following theorem connects the difference in maximum state-wisc cost between two arbitrary policies to the total variation divergence between them. Here total variation divergence between discrete probability distributions p, q is defined as (pll)) = Σ, Ip: - %l. This measure can be easily extended to continuous states and actions by replacing the sums with integrals. Thus, the total variation divergence between two policy (7', T) at state defined as: Drv(rt [I = Drv (I' (-18)
Theorem 1 (Trust Region Update State-wise Maximum Cost Bound). For any policies x', ,,, with en max; Ea-z' (S, a)]l, and define d= ΣH P(s. 8/m) the non- non-discounted augmented state distribution using n,, then the following bound holds:
Jo(w') -TD(T)
< E &nd"" axx"'
a7(8 + +1c Dr
(12)
The proof for Theorem is summarized in Appendix C Next, note the following relationship be- tween the total variation divergence and the KT. divergence (Boyd et al. 2003 Achiam et al.) 2017
E E (Drv (pll)))) V / [Pkr(ella](]], The following bound then follows directly from Theorem
/ Bendr (P
Jo(n') JD(m (b(6.a)+
E Srdd
(13)
By Equation 13 have guarantee for satisfaction of maximum state-wise constraints:

---

Published in Transactions on Machine Learning Research (04/2024)
Proposition 1 (SCPO Update Constraint Satisfaction). Suppose Tas th+1 related by equation 11 De-return for Tk+1 solisfies
then
ViE ,, JD. To, (T++1) $ wi-
Proposition 1 is the first finitehhrrionn variant of the policy improvement theorem, and it also presents the first. constraint satisfaction guarantee under MMDP. Unlike trust region methods such as CPO and TRPO, which assume a discounted infinite horizon sum characteristic, MMDP's non-discounted finite horizon sum characteristic invalidates these theories and separate treatment is required. As the maximum state-wise cost is calculated through summation of non-discounted increments, analysis must be performed on finite horizon upper bound the worst-case summation.
Next, we provide the performance guarantee of SCPO. Previous analyses of performance guarantees have focused on infinite-horizon MDP. We generalize the analysis to finite-horizon MDP, inspired by previous work (akade & Langford 2002 Schulman et al. 2015 Achiam et al., 2017). and prove it in Appendix The infinite-horizon case can be viewed as a special case the fnite-horizon setting.
Proposition 2 (SCPO Update Worst Performance Degradation). Suppose Wh, Th+11 are related by equalion 11 with **+1 = max; Ee [A (3, a)]l, then performance return for Th+1 satisfies
V2077
((T++1)~ [(TT]
1-7
Proposition establishes a fundamental result that bounds the performance degradation when policy updates are carried out via solving equation [0] which ensures satisfaction of the trust region step size constraint and the state-wise maximun cost constraints. Intuitively, this proposition assures that when our policy is updated within these specified constraints, the degradation in reward performance will be limited. This means that our approach strikes balance between improving the policy's 's performance and satisfying the state-wise safety constraints.
5 Practical Implementation
In this section, show how to (a) implement an elficient approximation to the update equation 11 encourage learning even when equation I1 becomes infeasible, and (c) handle the difficulty of fitting augmented value VB, which is unique to our novel MMDP formulation. The full SCPO pseudocode is given as algorit in appendix
Practical implementation with sample-based estimation We first estimate the objective and con- straints in equation 11 using samples. Note that we can replace the expected advantage on rewards using an importance sampling estimator with a sampling distribution
AAciam et al. 2017 as
(a(s)
Ryndr ava (ATH a)] Rgndd awitt
A ATH (8, Tx (a(8)
(14)
equation 14 allows to replace T with empirical estimates each state-action pair (8,a) from rollouts by the previous policy Thk The empirical estimate of reward advantage is given by R(3, a') +>)+> ( VT V** can be computed at cach augmented state by taking the discounted future return. The same can be applied to the expected advantage with respect lo cost increments, with the sample estimates given by D.(S, a, 8') + (s') - (s). VJ, (8) is computed by taking the non-discounted future D,-return. To procood, we convexify equation [] by approximating the objective and cost constraint via first-order expansions, and the trust region constraint via second-order expansions. Then, equation II can be efficiently
solved using duality (Achiam et al. 2017
7

---

Published in Transactions on Machine Learning Research (04/2024)
Infeasible constraints An update to f is computed every time equation 11 is solved. However, due to approximation errors, sometimes equation 11 can become infeasible. In that case, we follow Achiam et. al. (2017) to propose an recovery update that only decreases the constraint value within the trust region. In addition, approximation errors can also cause the proposed policy update (either feasible or recovery) to violate the original constraints in equation [1] Hence, each policy update is followed by a backtracking line search to ensure constraint satisfaction. If all these fails, we relax the search condition by also accepting decreasing expected advantage with respect to the costs, when the cost constraints are already violated. Denoting e; = JD. (TR) + 2(H 1)6 Wa, the above criteria can be summarized
Band (T]((T|(TTE)) S 6
(15)
E B
[A (8. a)]
E Br awaa [A a) 0)
(16)
Note that the previous expected advantage Es aamm [A (6, a)] is also estimated from rollouts by T& and converges to zero asymptotically, which recovers the original cost constraints in equation
Imbalanced cost value targets A critical step in solving equation 11 is to fit the cost increment value functions V. (&t). By definition, V. (8e) is equal to the maximum cost increment in any future state over the maximal state-wise cost so far. In other words, the true VD, will always be zero for all & when the maximal state-wise cost has already occurred before time t. In practice, this causes the distribution of cost increment value function to be highly zero-skewed and makes the fitting very hard. To mitigate the problem, we sub-sample the zero-valued targets to match the population of non-zero values. We provide more analysis on this trick in Q3 in section 6.2
6 Experiments
In our experiments, we aim to answer these questions:
Q1 How does SCPO compare with other ttaee-of-the-art methods for safe RL?
50
Nowon perfomance
DeNe Perfommace
g 15 5
Q2 What benefits are demonstrated by constraining the maximum state-wise cost?
19/011
(90
1000-00
1000
Q3 How does the sub-sampling trick of SCPO impact its performance? Does sub-sampling work for other baselines?
2.0
32
3.5
Wialersfiteraco acla
Tenn
500
Q4 How tight is our derived surrogate function?
CooL Peffomarcee
Perfumercs
Q5 How does the resource usage of our algorithm compare to other algorithms?
6.1 Experiment Setups
2.0
TotalEnorrterat
New Safety Gym To showcase the effectiveness of our state-wise constrained policy optimization approach, we enhance the widely recognized safe reinforcement learning benchmark environment, Safety Gym (Ray al.) 2019).
Cort San, formance
by incorporating additional robots and constraints. Sub-
sequently, we perform a series of experiments on this augmented environment.
000 10Etrttt 200
(a) Ant-Hazard-8
(b) Walker-Hazardse
Our experiments are based on five different robots: (i)
Figure 2: Comparison of results from two representative
Point:
Figure 3a A point-mass robot (A C IR2 that test suites in high dimensional systems (Ant and Walker).
can move on the ground, (ii) Swimmer: Figure 3b A
three-link robot (A C R²) that can move on the ground.
(iii) Walker: Figure 3d A bipedal robot ('o) that can move on the ground. (iv) Ant: Figure 3c
A quadrupedal robot. (A R$) that can move on the ground.
(v) Drone: Figure 3el quadrotor robot.
8

---

Published in Transactions on Machine Learning Research (04/2024)
X
(a) Point
(b) Swimmer
(c) Ant
(d) Walker
(e) Drone
(f) Arm3
(g) Humanoid
Figure Robots for benchmark problems upgraded Safety Gym.
(a)
Hazard
(b) 3D Hazard
(c) Pillar
Figure 4: Constraints for benchmark problems in upgraded Safety Gym.
(A C I)*) that can move in the air. (vi) Arm3: Figure 3f A fixed three-joint robot arm(.A C R2) that can move its end effector around with high flexibility. (vii) Humanoid: Figure 3g bipedal robot(A C RR))) that has torso with pair of legs and arms.
All of the experiments are based the goal task where the robot must navigate to goal. Additionally, since are interested in episodic tasks (fiiteehhrizon MDP), the environment will be reset once the goal is reached. For the robots that can move in 3D spaces (e.g, the Drone robot, Arm3 robot), we also design a new 3D goal task with a sphere goal floating in the 3D space. Three different types of constraints are considered: (i) Hazard: Dangerous areas as shown in Figure 4a Hazards are trespassable circles on the ground. The agent is penalized for entering them. (ii) 3D Hazard:
Dangerous areas as shown in Figure 4b 3D
Hazards trespassable spheres in the air. The agent penalized for entering them. (iii) Pillar: Fixed obstacles as shown in Figure 4c The agent is penalized for hitting them.
Considering different robots, constraint types, and constraint difficulty levels, we design 14 test suites with 5 types of robots and 9 types of constraints, which are summarized in Table in Appendix. We name these test suites as (lobot)-(Constraiin Type)-(Constraiin Number).
Comparison Group The methods in the comparison group include: (i) unconstrained RL algorithm TRPO (Schulman et al. 22055) (ii) end-to-end constrained safe RL algorithms CPO (Achiam al. 2017):
TRPO- Lagranginn (Bohez al.) 2019), TRPO-FAC (Ma al.) 2021), TRPO-IPO (Liu et al. 2020
PCPO Yang et al.) 2020b), and (iii) hierarchical safe RL algorithms TRPO-SL SL (TRPO-Satee Layer)
[Dalal
ct al. 2018h, TRPO- USL EERPO-Unrolinng Safcty Layer) (Zhang et al. 2022a). We select TRPO as our baseline method since it is state-of ohate-of-the-att and already has safety-constrainet derivatives that can be tested off-the-shelf. For hierarchical safe RL algorithms, we employ a warm-up phase (1/3 of the whole epochs) which does unconstrained TRPO training, and the generated data will be used to pre-train the safety critic for future epochs. For all experiments, the policy n, the value (V*, VT)) are all encoded in foodforward neural networks using two hidden layers of size (64,64) with tanh activations. More details are provided in Appendix
Evaluation Metrics For comparison, evaluate algorithm performance based on (i) reward perfor- mance, (ii) average episode cost and (iii) cost rate (state-wise cost). Comparison metric details are provided in Appendix F.3 We set. the limit of cost to 0 for all the safe RL algorithms since we aim to avoid any violation the constraints. For our comparison, we implement the baseline safe RL algorithms exactly following the policy update / action correction procodure from the original papers. We emphasize that order for the comparison to be fair, we give bascline safe RL algorithms every advantage that is given SCPO, including equivalent trust. region policy updates.

---

Published in Transactions on Machine Learning Research (04/2024)
Reward Performanze
Rewwrd Perfor mancee
Rawand Performance
2.5
1.5
-4
1.
0.5
Loggangnn
2009
TRYS Laplangerr
PCOP
TRFO Lagergan
TRAO io
FCDP
RcalEnvinteracts
Totalnnvineeracts
1:6
TotaEnninteeeets
18/0
TEPO TR/O-4
TRPO-Lag sngien
2008
TRPO-AC
5070
500
Cost Perfomance
25
Cost Performance
2.0
1.0
0.5
1n6
Enuintaraatss
1eb
IntalEnddntrrats
1e6
Ie-2
Ie-3
1x-3
1944
TAPO IS
6NO
1973
DP
Cost Rate, Performance
11P0 AMC
3010
Cost Pate Performnnc
TPPD St
Rate Performance
6.2
TotalEnvinterads
106
IntalEndntteartss
Iec
106
(a) Point- Point-Hazard-6
(b) Point- Pilla-Pilla--
(c) 8
Hazard-8
Rawart Performance
Reward rnffommnnc
Nerfomance
1770
1970 0SL
CP0
CPO
1900
14/0440
TEPO-5L
1979
5010
0.0
19013
1942
160
IottrEncitteactss
1e6
Enuinteracts
167
1st
Tann-Lag snglie
1940 80
2009
1i0 PC
K00
10.0
Cost, Performanc
mance
Eoot
Tot Inteitrriiteeatts
166
1e0
TotalEnvinteracts
167
1o-2
Ic-2
Cost Rato perfomance
TINO
renourng
100
Cost Performence
Burfomante
3.1
13X00L
0.9
0.7
0.5
6
3,0
3mB
100
ToltrEniinteratts
187
(d) Drona-3D
(c) Ama3-Haz
(I) Humanoid- Humanuid-Hoozard---
Figure 5: Comparison of results from (i) four representative test suites in low dimensional systems (Point, Swimmer, Dronc), (ii)
Arm reaching, and (iii) Humanoid locomotion.
10

---

Published in Transactions on Machine Learning Research (04/2024)
6.2 Evaluating SCPO and Comparison Analysis
Low Dimension System We select. four representative test suites low dimensional system (Point, Swimmer, Drone) and summarize the comparison results on Figure which demonstrate that SCPO is successful at approximately enforcing zero constraints violation safety performance in all environments after the policy converges. Specifically, compared with the baseline safe RL methods, SCPO is able to achieve (i) near zero average episode cost and (ii) significantly lower cost rate without sacrificing reward performance. The baseline end-to-end safe RL methods (TRPO- Lagrangian, TRPO-FAC, TRPO-IPO, CPO, PCPO) fail to achieve the near sero cost performance even when the cost limit is set to be O. The baseline hierarchical safe RL methods (TRPO-SL, TRPO-USL) also fail to achieve near zero cost performance even with an explicit safety layer
Valor
Maximum State-wise Cost
1:50
1:24
1.00
0.75
0.50
0.25
0.00
2.0
2.5
3,0
Total Envinterats
167
Figure 6:
Maximum state-wisc cost
to correct the unsafe action at every time step. End-to-end safe RL algorithms fail since all methods rely on CMDP to minimize the discounted cumulative cost while SCPO directly work with MMDP to restrict the state-wise maximum cost by Proposition ! We also observe that TRPO-SL fails to lower the violation during training, due to the fact that the linear approximation of cost function C($,, a, $e+1) (Dalal et al. 2018) becomes inaccurate when the dynamics are highly nonlinear like the ones we used in MuJoCo (Todorov et al. 2012). More detailed metrics for comparison and experimental results on test suites with low dimension systems are summarized in Appondix
High Dimension System To demonstrate the scalability and performance of SCPO in high-dimensional systemss, conducted tests the Anl-Hazard-8 Walker-Hazard-8 suites, with 8-dimensional and 10- dimensional control spaces, respectively. The comparison results for high-dimensional systems are summarized in Figure 2 which show that SCPO outperforms all other basclines enforcing zero safety violation without compromising performance in terms of return. SCPO rapidly stabilizes the cost return around zero and significantly reduces the cost rate, while the other baselines fail to converge to a policy with near-zero cost.
Furthermore, we tackled more scenarios involving robot arm goal reaching and humanoid locomotion. The com- parative results for these tasks are detailed in Figure 5e and Figure 5i respectively. Notably, SCPO consistently achieves the lowest cost rate sstate-wise cost) in both assignments. It's essential to highlight an observation in the humanoid task: while the episodic cost is higher compared to several baseline methods, the cost rate is the most favorable. This discrepancy arises because SCPO intentionally takes more cautions paths around hazards to ensure safety, leading to an increased number of time steps per episode. Consequently, although the state-wise cost is minimized, the average episodic cost riscs due to the longer average opisodic horizon.
The comparison results of both low dimension and high dimension systems answer Q1.
Maximum State-wise Cost As pointed in Section 3.3 the underlying magic for enabling near-zero safety viola- tion is to restrict the maximum state-wise cost to stay around zero. To have a better understanding of this pro- cess, we visualize the evolution of maximum state-wise cost. for SCPO on the challenging high-dimensional Ant-Hazard-8 and Hazlrdd-- test suites in Figure G which answers Q2. Within Figure 6 each data point is obtained by averaging the maximum state-wise cost across all episodes within the current epoch. To facilitate better comparisons with other works, we consistently employ the cost rate a metric to illustrate the state-wise cost performance in our results.
Figure 7: Cost value function target of five randomly sempled episode different tasks
Ablation on Sub-sampling Imbalanced Cost Increment Value Targets One critical step in SCPO involves learning the cost increments value functions V (8.). These functions represent the maximum cost in- crement in any future state relative the maximal state-wise cost encountered so far. In simpler terms, V7,, ($t) is non-increasing step function. In particular, it resembles staircase, with many steps locating at zero after
11

---

Published in Transactions on Machine Learning Research (04/2024)
CPO
GPU Resources
TRPO
(crrs)urs)
CPO
CPU Resources
TRPO
SCPO(ours)
CPO
Wall-Clock Time
TRPO
SCPO(ours)
30
60
80
90
100
101
102
103
Ratio TRPO Resources (96)
Figure 10: Resource usage compared to other algorithms under the Goal-Hazard-8 task, where TRPO is sct as the bascline
the point where the maximum state-wise cost over the trajectory has been reached. This characteristic gives the cost increment value target a skewed distribution with a high frequency of zeros, as illustrated in Figure 7
Sub-sampling is employed bring down the zero gets population to match the population of non-zero tar- gets. This adjustment is unique to SCPO, other safe RL baselines try to fit. cost value function Va (sk)
Cass Seroom
By,,, 7 at, 8++1)]- In these baselines, the population of zero-cost value targets (only after encoun- tering the last cost) is usually much smaller than the population of non-zero targets, rendering sub-sampling unnocessary. We also visualize (sa) targets in the left hand side of Figure 7 Consequently, applying sub- sampling to reduce the zero Vē, (&p) target population is irrelevant and has no impact on their performance.
doomarping vthed symtorrd by
Figure SCPO sub-sampling ablation study with Drone- 3DHazard-8
Next, to demonstrate the necessity of sub-sampling for solving this chal- lenge, we compare the performance of SCPO with and without sub- sampling trick on the aerial robot test suite, summarized in Figure It evident that with sub-sampling, the agent achieves higher rewards and more importantly, converges to near-zero costs. That is because sub-sampling elfectively balances the cost increment value targets and improves the fitting of VTT (&c). We also attempted to solve the imbalance issue via over-sampling non-zero targets, but did not obscrve promising results. This ablation study provides insights into Q3.
2.0
394
332
281
spocts
Figure 9: Visualization of cost function surrogate function
Tightness of State-wise Maximum Cost. Bound To assess the
tightness of the state-wise maximum cost bound in equation 12 (surrogate
cost function in equation I1 track and visualize the true values and surrogate values (bound estimates using the policy from the previous iteration) of JD throughout policy training in the Point-Hazard-8 testing suite, as depicted in Figure g Duc to approximation errors, minor overlap between true values and surrogate values noticeable at the initial stages of training. However, this overlap is quickly resolved, and thereafter, the surrogate cost consistently functions as a precise upper bound for the true value. The deviation, approximately 1c-3, remarkable considering the scale of the true value, which ranges from 1c-2 56-2. This observation underscores the good tightness in the theoretical state-wiss maximum cost bound and answers Q4.
12

---

Published in Transactions on Machine Learning Research (04/2024)
Resources Usage Situation We conduct tests comparing GPU and CPU memory usage, as well wall- clock time, for CPO, TRPO, and SCPO, all allocated with identical system resources in the Goal-Hazard-8 task. As illustrated in Figure I0. it is observed that CPO and SCPO exhibit nearly identical GPU occupancy and time consumption, with SCPO utilizing slightly more CPU resources. Notably, when considering the scale change on the horizontal axis, the three algsrithms demonstrate comparable performance across all three metrics. This suggests that our algorithm achieves improved performance without noticeable increasod system load consuming additional time, affirming its superior overall efficiency. The results provide answer to Q5.
7 Conclusion and Future Work
This paper proposed SCPO, the first general-purpose policy search algorithm for state-wise constrained RL. Our approach provides guarantees for state-wise constraint satisfaction at each iteration, allows training of high-dimensional neural network policies while ensuring policy behavior, and is based on new theoretical result on Maximum Markov decision process. We demonstrate SCPO's effectiveness on robot locomotion tasks, showing its significant performance improvement compared to existing methods and ability to handle state-wise constraints.
Limitation and future work One limitation of work is that, although SCPO satisfies stale-wise constraints, the theoretical results are valid only in expectation, meaning that constraint violations are still possible during deployment. To address that, will study absolute state-wise constraint satisfaction, i.e. bounding the marimal possible state-wise cost, which is even stronger than the current result (satisfaction in expectation).
References
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeol. Constrained policy optimization. In International conference machine learning, pp. 22 31. PMLR, 2017.
Homanga Bharadhwaj, Aviral Kumar, Nicholas Rhinehart, Sergey Levine, Florian Shkurti, and Animesh Garg. Conservative safety critics for exploration. arXiv preprint arXio:2010.14497, 2020.
Steven Bohez, Abbas Abdolmaleki, Michael Neunert, Jonas Buchli, Nicolas Heess, and Raia Hadsell. Value constrained model-free continuous control. arXiv preprint orXiv:1902.04 046623 2019.
Stephen Boyd, Lin Xiao, and Almir Mutapeic. Subgradient methods. lecture notes of EF3920, Stanford University, Autumn Quarter, 2004:2004 2005, 2003.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 444444444 2018.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman and Mohammad Ghavanzadeh. Lyapunov-based safe policy optimization for continuous control. ICML 2019 Workshop abss/1901.00031, 2019.
Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication
time. J. ACM, 68(1), jan 2021. ISSN 0004-5411. doi: 10.1145/3422305. URL https:://ot..rrg/// 1145/
3424305
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. CoRR, abs/1801.0875// 2018.
Shangding Gu, Long Yang, Yali Du, Guang Chon, Florian Walter, Jun Wang, Yaodong Yang, and Alois Knoll. A review of safe reinforcement learning: Methods, theory and applications. arxiv preprint 2r..22205.008300 2022.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Tairan He, Weiye Zhao, and Changliu Liu. Autocost: Evolving intrinsic cost for zero-violation reinforcement learning. Proceedings of the AAAT Conference on Artificial Intelligence, 2023.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp- 267-274, 2002.
Qingkai Liang, Fanyu Que, and Eytan Modiano. Accelerated primal-dual policy optimization for safe reinforcement learning. arXiv preprint arXiv:1802.06453 2018.
Yongshuai Liu, Jiaxin Ding, and Xin Liu. TPO: interior-point policy optimization under constraints. CoRR, abs/1910.09615,, 2019. URL http://arxiv
Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 4940-4947, 2020.
Yongshuai Liu, Avishai Halev, and Xin Liu. Policy learning with constraints in model-free reinforcement learning: A survey. In The 30th International Joinl Conference on Artificial Intelligence (IJCAT), 2021.
Haitong Ma, Yang Guan, Shegnbo Eben Li, Xiangteng Zhang, Sifa Zheng, and Jianyu Chen. Feasible actor- critic: Constrained reinforcement. learning for ensuring statewise safety. arXiv preprint or arXin:2105. 10122155.1000 10682, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7000):529 533, 2015.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural networks, 21(4):682-68) 697, 2008.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchuarkkngg safe exploration in deep reinforcement learning. CoRR, abs/ 19100090.001088 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. arXiv preprint 1rXic.1805.110P1 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEFE/RSS /RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. TEEE, 2012.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7382)3350 354, 2019.
Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Projection-based constrained policy optimization. CoRR, abs/2010.03115,, 2020a. URL
Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Projection-based constrained policy optimization. arXiv preprint rrXii:2010.03152 2020b.
Linrui Zhang, Qin Zhang, Li Shen, Bo Yuan, and Xueqian Wang. Saferl-kit: Evaluating efficient reinforcement learning methods for safe autonomous driving. arXiv preprint arXi::2266.0880 08528, 2022a.
Linrui Zhang, Qin Zhang, Li Shen, Bo Yuan, Xueqian Wang, and Dacheng Tao. Evaluating model-free reinforcement learning toward safety-critical tasks. arXiv preprint 2xXiv:2212.057e1 2022b.
Weiye Zhao, Tairan He, Rui Chen, Tianhao Wei, and Changliu Liu. State-wise safe reinforcement learning: A survey. The 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2023.
14

---

Published in Transactions on Machine Learning Research (04/2024)
A Complexity analysis for SCMDP
The complete form of equation B is:
max Jo( s.t.
(TTT~)), ViE 1, m, E(C,(se, ae s(+1) S wi.
(17)
where each state-action transition pair corresponds to constraint. Consider there's only one constraint function C₁ equation 17 is transformed
max Jo(T),
s.t. (I(T)
E (e0.00.3 JovT
(0,
W1 S
G2(T)
W1 S (#1 (e1.01.92 JUTT pm
E
(1))
GH =
E (#n-1-n-1::01) 700
((SH-1100-11881)
01 $
(18)
Suppose is parameterized by 1 E R With KKT conditions, equation 18 be optimized via solving the following program:
aC(n.)) = 0, 1,2, ... R2
Om:
(T) = 0, 1,2, ...
(19)
x 1,2, H
where C(T, =) Jo(T)+ E (T).
To understand the time complexity of equation 19
we can treat To and G, as linear functions with respect So that equation 19 represents linear program, which can be solved by the fastest algorithm (Cohen
et al.
2021 in time
O O'((nn HY + (n 2.555-/22 (nz H)2+1/6)
(n) + H)/5)
(20)
where w is the exponent of matrix multiplicatoin, a is the dual exponent of matrix multiplication, and 8 is the relative accuracy. For the current value of w ~ 2.37 and a ~ 0.31, the state-of-the-arl algorithm takes O O'n + log((n, + H)/8)) time (Cohen et al. 2021
Consider (i) there are multiple cost functions C₁, and (ii) Tu and 9, are nonlinear functions with respect to n, the complexity of solving equation 17 with good accuracy, iee. solving SCMDP, will be larger than O 0((+++H)3) 3)
Preliminaries
NEW
To facilitate the proof of Theorem we begin by establishing key preliminaries that underpin the foundations of finite-horizon variations the performance improvement bound, considering the discounted sum nature. The subsequent scction, Appendix [ will clucidate the policy improvement of finite-horizon undiscounted sum Markov decision process (MDP). Our preliminary groundwork draws inspiration from [Appendix 10.1, Achiam et al. (2017)), extending the theoretical framework for finite-horizon scenarios.
15

---

Published in Transactions on Machine Learning Research (04/2024)
dt we used is defined as
H Σ x P() 8/
d'
(21)
which has little difference with d" and is used ensure the contimuity of function used for proof later. Then it allows us to express the expected discounted total reward or cost compactly as:
IT( E [0(8, a, a, and a
(22)
8'PP
where by a ~ n, we mean a ~ x(-18), and by ~ w, mean 8' ~ P(118, a)- g(8, a, 8') represents the cost or reward function. We drop the explicit notation for the sake of reducing clutter, but it should be clear from context. that a and depend on
Define P(5 a) is the probability of transitioning state S' given that the previous state was & and the agent took action a at state 8, and ft $ + [0. 1] is the initial augmented state distribution. Let p E RRI denote the vector with components p (8) P(s. $|π), and let Ps E | 81 denote the transition matrix with components (=((()) = f P(s 8, a) ( (a) 8 )da; then p Park" Pa and
de
Σ (7P=)'a 1=
(23)
(1 - -->++ (1 - 7PP)
-1-
Noticing that the finite MDP ends up at step H, thus (Px) should be set to zero matrix.
This formulation helps us easily obtain the following lemma. Lemma 1. For any function S R and any policy n,,
E [() + E E [S())] 0.
(24)
8m4
and
Bmnd
8~P
Proof. Multiply both sides of equation 23 by (I-yPa) and take the inner product with the vector f E RISI.
j
Combining Lemma with equation 22 we obtain the following, for any function f and any policy
[g(TT) = E [f($)] + E
[g(8, xf((s) f()]
(25)
s~A
and
Lemma 2. For any function f + and any policies Tt' and x, define
('((6) ([al))
-1) a''), 7 ((8))
La. =
(26)
and 8~P
and e = maxx [Easn', & R(3, a, 8¹) + 78(')) - f(a)]]. Then the following bounds hold:
J,(T') [,( 2 Txns((²) 57 Jr' - dz
(27)
J₂(T') - < (x)( + of | l d="1.-
(28)
where Dry is the total variational divergence. Furthermore, the bounds are tight wwenn n' nT the LHS and RHS are identically zero).
16

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. First, for notational convenience, let (3, = a(,, + f(8). By equation 25 obtain the identity
- -g(TT)= E 15, 87) brud"
E (8, a, 8)]
(29)
a-d
amaa" 8'~P
amm d'P
Now, we restrict our attention to the first term equation 29 components, where 167 (8) , 30 (8, 18). Observe that
Let to7 E R255 denote the vector of
E ( (r'' t87
8'mPP
=
= dd + ( (d' -d- toy
1 + - =, we have
With the Hölder's inequality; for any p, q [1, oo] such that
p
dr,, (o,to77) + | - d= 1=11, 100
2 E (,,6 a, 8')1 2 (d", (d", - -1|00 11:00--100
3o"'-d'' -c 107
(30)
drnd"
8'-P
We choose p = and q = oo; With 100
ry and by the importance sampling identily, we have
dt, to7
E s-dd 8'mP
(8, a, 8')]
(31)
[a(a8)) T(al3)
E snd gow d'mP
a,
A After bringing equation 31
|tay
into equation then substract
(5y(8, a, 8')] the bounds are obtained. 8-dd
The lower bound leads to equation
27 and the upper bound leads to equation 28
Lemma 3. The divergence between discounted future state visitation distributions, I|d - d= is bounded by average divergence of the policies n¹ and w:
H < Σ t=
l/d=' d=
1+1 E srdd
[Drv (8]]
(32)
where Drv [T][ = / En (a(s)) [[a(8\]-
Proof. Firstly, we introduce an identity for the vector difference of the discounted future state visitation
distributions on two different policies, n' and n. Define the matrices G = (1 - -Pa)) -, = (1 - >P..) and A P Pr. Then:
G-I-6-1- 7P,) - ( (I-)Pk)
(33)
=>A
17

---

Published in Transactions on Machine Learning Research (04/2024)
left-multiplying by G and right-multiplying by G, obtain
G-G GGAGG
(34)
Thus, the following equality holds:
-'' = (1- (G-
(35)
7(11 -))AGP
= =GGAd
Using equation 35
we obtain
Id' - 11= = >
(36)
S
where ||G||2 is bounded by:
|| = [1(1 - 71=-)
= Σr.
(37)
1=0
t=0
Next, we bound | as following:
Ad 11
Σ
Σ
((s1(s)
(38)
8
A (8' (d)
(z(((a3)) (z)
8
Σ
( a)
(a -(a))))
8,0,8'
Σ (c]))))(((()))))
2 E Drv (3)) douda
By taking equation 38 and equation
37 into equation 36 this lemma is proved.
The new policy improvement bound follows immediately.
18

---

-D(T') + ID(T) with the Published in Transactions on Machine Learning Research (04/2024)
Lemma 4. For any function f S + R and any policies x' and n, define a, 81) = -(f,a..)==f(())--)))))
=
Lx, =
6, (8, a, 83) and
foud ameat 8f
T(als)
H1 D a. (T') = (xt) + 2
y +
[Drv (T]][))))]
t=0
where Dr - | (als) [<al()) the total variational divergence between action distributions at The following bounds hold:
(x)) 2 [g( Ig(x)))))))))))))))))(())) 2 (T.)(")).
Furthermore, the bounds are tight (when xt' n, all three expressions are identically zero)
Proof. Begin with the bounds from lemma and bound the divergence Drv I|d²) by lemma
C Proof for Theorem
Proof. The choice of f VB.g D in lemma leads to following inequality:
Jo(74) ID((T) S E dndtt
ab) + 2 Σ ) D' Drv
(39)
t=
where JT(T)= = Eyon Σ# 72 (8e, az, 8441) need to distinguish from JD(T). And Vy Åb are also the discounted version of Vø and AD- Note that according to Lemma one only get this the inequality holds when 7 E (0, 1).
Then we can define F(r)
E annd
following condition holds:
F(7) 2 0, when E (0,1)
(40)
F(r)'s 's domain of definition is R
F()) is a polynomial function
Because F()) is polynomial function and coefficients are all limited, thus lim F(7) exists and F(1) is
continuous at point (1))(1)). So F(1) = lim F(7) 2 0, which equals to: 2-1 7-1
JD(m') JD(T) E annd"
Ab(3, + + 1)e7 (rv(((()
where d't DH P(s+ 3/
19

---

Published in Transactions on Machine Learning Research (04/2024)
D Proof for Proposition 2
Proof. Here we first present a new bound on the difference in returns between two arbitrary policies in the context of finite-horizon MDP:
Theorem 2 (Trust Region Update Performance). For any policies n', n, with c-' = max; (AT a)ll; and define d' = (1 (1-7)
H
Σ
yt P(s 8)) as the discounted augmented state distribution using x, then the
1=0
following bound holds:
2ye"
J(x') - -(x))
Drv (7 [|]]
(41)
Boutt ama
1
We provide the proof for Theorem in Appendix D.2 The following bound then follows directly from Thcorem using the relationship between the total variation divergence and the KL divergence:
2
27c - Lsnnd [TK[(T]|+>[3]]
J(z') - J(T)
E Brud
as,
(42)
In equation 11 the reward performance between two policies is associated with trust region, i.e.
7k+1 argmax E [AT* (S) rEll,
(43)
àoud
s.t. Rand [=xL([]|= <
Due to Lemma 3 (proved in Appendix with the following optimization:
D.1 if two policies are related with Equation
43
they are related
Tk+1 argmax [ATH TEIl,
(G, (5,
(44)
& a~x
s.t. Es [T) $
By equation 42 and equation 44 if Thy Th+1 related by equation satisfies
then performance return for T&41
220
J(Tk+1) J(TR)
?
D.1 KL Divergence Relationship Between t and Tm
Lemma 5. F. [Pxz(=][TT(3]] drdd,
< E, [DKI(T'|<>)1) Soud,
20

---

Published in Transactions on Machine Learning Research (04/2024)
Proof.
H
E (PLL(T|TT)) = E - 7) Σ P(s. D()))
8mdl
3
tmo
7 P(s (TT))x((T((>]]
H
P(s = 8|
E [Px[(T||T>(3]] drdd
D.2 Proof for Theorem
The choice of = 9 = R in lemma leads to following inequality:
For any policies x', nT, with ct' mars Ea [A (8, a)]l, the following bound holds:
1
- 2 E and aro
a)) - -
y Je Drv(F'1
1=0
27E
Ax
Dr Drv (T(|
1 1-7
At this point, the theorem
is proved.
21

---

Published in Transactions on Machine Learning Research (04/2024)
E SCPO Pseudocode
Algorithm State-wise Constrained Policy Optimization
Input:
Initial policy xo llg.
for == 0,2, do
Sample trajectory T ~ TT Ti&
Estimate gradient g <- V a (A a))l==0
8=06
D section section
Estimate gradient b; -- Vo [AD, (8, a)] 0=
Vi 1,2,...,,
Estimate Hessian H BB D (T (T& [$]] 0=
Solve convex programming
Achiam al. 2017
g T 0k)
K+1 argmax
s.t.
2 (0 8₂) H(O 0x) 5
c + b (0 0s) S 0, 1,2, ,..,
Get search diroction AP" + 1 02 for j 0, 0, do 0' - 02 ~00000
Line search
E E (0, is the backtracking coefficient
if Exrr [Dr (T Tk [$]] S d and
Trust region
Es
[AD (8, a) - Es
[ ($) < max(-c, 0), Vi and
Costs
(Ra ao (8, a)) 2 Eg
_A (8, or infeasible equation
11 then
D. Rewards
0k+1 0r
> Update policy
break
end if
end for
end for
22

---

Published in Transactions on Machine Learning Research (04/2024)
Tahle 1: The test suites environments our experiments
Ground robot
Aerial robot
Task Setting
Low dimension
High dimension
Point
Swimmer
Arm3
Walker
Ant
Humanoid
Drone
Hazard-1
Hazard-4
Hazard-8
v
Pillar-1
Pillar-4
Pillar-8
8DHazard-1
3DHazard-4
3DHazard-8
F Expeiment Details
F.1
Environment Settings
Goal Task In the Goal task environments, the reward function is:
(( + 1[g Rd)
where d3 is the distance from the robot to its closest goal and Ro is the size (radius) of the goal. When a goal achieved, the goal location is randomly reset to someplace new while keeping the rest the layout the same. The test suites of our experiments are summarized in Table [
Hazard Constraint In the Hazard constraint environments, the cost function is:
c(x,) = max(0, R²h d:)),
where df is the distance to the closest hazard and R is the size (radius) of the hazard.
Pillar Constraint In the Pillar constraint environments, the cost c. if the robot contacts with the pillar otherwise a =.
The state space composed of two parts. The internal state spaces describe the state of the robots, which can be obtained from standard robot sensors (accelerometer, gyroscope, magnetometer, velocimeter, joint position sensor, joint velocity sensor and touch sensor). The details of the internal state spaces of the robots in test suites are summarized in Table 2 The external state spaces are describe the state of the environment observed by the robots, which can be obtained from 2D lidar or 3D lidar (where each lidar sensor perceives objects single kind). The state spaces of all the test suites are summarized in Table 3 Note that Vase and Gremlin are two other constraints in Safety Gym (Ray et al. 2019) and all the returns of vase lidar and gremlin lidar are zero vectors (i.e., [0, 0, 10,00,,00000 0] E R16) in our experiments since none of our test suites environments has vases.
State Space
Control Space For all the experiments, the control space of all robots are continuous, and lincarly scaled to [-1, +1].
F.2 Policy Settings
The hyper-parameters used in experiments are listed in Table 4 default.
23

---

Published in Transactions on Machine Learning Research (04/2024)
Table The internal state space components different test suites environments.
Internal State Space
Point
Swimmer
Walker
Ant
Drone
Arm3
Humanoid
Accelerometer (IR*)
v x5
Gyroscope (R.3)
V
v x5
Magnetometer (R*)
/
V
v
V
v x5
Velocimeter (R-3)
V
V
V
v
v x5
v
Joint position sensor (RR")
TI =
n1 = 2
n
11
n
Joint velocity sensor (RR")
0
n
10
n1
71
N
Touch sensor (R.)
0
n=4
=
=
Table 3: The external state space components of different test suites euvironments.
External State Space
Goal-Hazard
MaGGol--Haarr
Goal-Pillar
Goal Compass (R²)
Goal Lidar (R 1))
X
3D Goal Lidar (Ro0)
x
X
Hazard Lidar 1G)
X
X
3D Hazard Lidar (R)
X
V
x
Pillar Lidar (6)
X
X
Vase Lidar (R16)
x
Gremlin Lidar (R216
X
Our experiments use separate multi-layer perception with tanh activations for the policy network, value network and cost network. Each network consists of two hidden layers of size (64,64). All of the networks are trained using Adam optimizer with learning rate of 0.01.
We apply an on-policy framework our experiments. During each epoch the agent interact B times with the environment and then perform a policy update based on the experience collected from the current epoch. The maximum length of the trajectory is set to 1000 and the total epoch number N is set to 200 default. In our experiments the Walker and the Ant were trained for 1000 epochs due to the high dimension.
The policy update step is based on the scheme of TRPO, which performs up to 100 steps of backtracking with a coefficient of 0.8 for line searching.
For all experiments, we use a discount factor of y 0.99, an advantage discount factor À 0.95, and a KL-divergence step size of åKL= 0.02.
For experiments which consider cost constraints adopt target cost 5 0.0 to pursuc zero-violation policy.
Other unique lyper-parameters for each algorithms are hand-tuned to attain reasonable performance.
Each model is trained on a server with 48-core Intel(R) Xeon(R) Silver 4214 CPU 2.2.GHz, Nvidia RTX A4000 GPU with 16GB memory, and Ubuntu 20.04.
For low-dinensional tasks, we train each model for 6e6 steps which takes around seven hours. For high- dimensional tasks, train each model for 3e7 steps which takes around 60 hours.
F.3 Metrics Comparison
In Tables we report all the 14 results of our test suites by three metrics:
24

---

Published in Transactions on Machine Learning Research (04/2024)
SCPO
201
30000
1000
(64, 64)
0.90
0.97
100
0.8
0.02
(64, 64)
80
Adam
0.001
(64, 64)
80
Adam
00.001
0.0
0.0
PCPO
200
30000
1000
(64, 64)
0.90
0.97
0.02
(04, 64)
80
Adam
0.001
(64, 64)
80
Adam
0.001
0.0
(64, 64)
(64, 64)
(64, 64)
CPO
200
30000
1000
0.99
0.97
100
0.8
0.02
80
Adam
0.001
80
Adam
0.001
0.0
0.0
TRPO-FAC FAC
200
30000
1000
(64, 64)
0.99
0.97
100
0.8
0.02
(04, 64)
80
Adam
0.001
80
Adam
0.001
0.0
Adam
0.0001
(64,
Table 4: Important hyper- parerpparmeterss different algorithms in our experiments
TRPO-USI TRPOOIPO
(644, 64)
(64, 64)
200
30000
1000
0.99
0.97
100
0.8
0.02
80
Adam
0.001
0.0
0.01
200
30000
1000
(64. 64)
0.99
0.97
100
0.8
0.02
(64. 64)
Adam
0.001
(64, 64)
80
Adam
0.001
0.0
20
0.05
1/3
TRPO [18' Dalai]
(64, 64)
(64, 64)
(64, 64)
200
30000
1000
1.90
0.97
100
0.8
0.02
80
Adam
0.001
80
Adam
0.001
0.0
1/3
TRPO- Lagrangian
200
30000
1000
(64, 64)
0.99
0.97
100
0.8
0.02
(64, 64)
80
Adam
0.001
(641 64)
80
Adam
0.001
0.0
0.005
(64, 64)
(64, 64)
TRPO
200
30000
1000
1.90
0.97
100
0.8
0.02
Adam
0,001
N
B
L
6
Maximun length of trajectory
TRPO wrcckrakking coellicienl
Policy network hidden layers
Value network hidden layers
Advantage discount factor
TRPO backtracking steps
Cost net work hidden layors
Value network iteration
Value network optimizer
Cost network iteration
Cost net work optimizer
Lagrangian learning rate
USL correction iteration
Target Cost Lograngian optimizer
Policy Parameter
Value learning rate
USL correction rale
Cost learning rabe
Steps per epoch
Discount factor
IPO parameter
Cosl reduction
Warmup ratio
Target KL
Epochs
25

---

Published in Transactions on Machine Learning Research (04/2024)
The average episode return Jr-
The average episodic sum of costs Me.
The average state-wise cost over the entircty of training Pc-
All of the three metrics were obtained from the final epoch after convergence, Each metric was averaged over two random seed.
The learning curves of all experiments are shown in Figures 11 to 15
A lew general trends can be observed:
All methods can converge lo good reward performance under different lask settings afler about le6 time steps. However, it often takes more time for the cost performance to get converge.
The reward learning speed and the cost learning rate trade off against each other because the algorithms without state-wisc constraints are more likely to explore unsafe state to gather more rewards.
F.4 Ablation study on large penalty for infractions
We used adaptive penalty coefficient our experiments with the Lagrangian method. Thus, we scale it up by cer- tain amount À to perform tion of the balance between reward and satisfying constraints. We name the ex- periment TRPO-LAG-(A) and compare it with SCPO in Figure I6 We can see that the cost rate and cost. value of the Lagrangian method decreases significantly when lambda increases. But the same time, the speed of convergence of the reward is grcatly reduced. On the contrary, SCPO achieves the fastest convergence speed and the best convergence value in terms of both reward convergence and cost value decrease, and at the same time, it is not inferior in terms of cost rate. This shows that the simple coefficient adjustment of the Lagrangian method is not comparable to the superiority of our algorithm.
beternae
investiga-
2004
COST
3002
Figure TRPO-Lagrangian method ablation study with Roint-Hazard-8
G Broader Impact
Our SCPO algorithm has been theoretically proven to effectively enforee state-wise instantancous constraints, including safety-critical ones such as collision avoidance. However, achieving zero constraint violation practical applications requires careful fine-tunigg the implementation and training process. Factors such as neural network structure, Icarning rate, and cost limits need be properly adjusted to the specific task hand. It important to note that improper implementation and training of SCPO can still result in constraint violations, posing potential safety risks. Therefore, when deploying SCPO policies in safety-critical applications, it is strongly recommended to incorporate explicit safety monitor, such control saturation, to completely eliminate any potential safety issues.
26

---

Published in Transactions on Machine Learning Research (04/2024)
Table 5: Metrics of three Point-Hazare environments obtained from the final epoch.
(a) Point- 1
(b) Point -ant--Ha
(c) Point-Hazard-2
Algorithun
Algorithm
Algorithm
14.
TRPO
2.5779
6.7300
0.0096
TRPO
2.5925
0.2112
0.0037
TRPO
2.5701
0.5113
0.0071
TRPO Loganglan
0,5017
0,0058
TRPO Legrangion
2.54%4
TRPO Logrondion
2,5851
0.5119
0.0064
TRPO-SL
TRPO-SL
2.3174
0.3115
TRFO-SL
0.8681
0.0071
TRPO-USE
TRPO-PO
TRPO-IPO
TRPO-IPO
0.3047
0,0071
TRPO-FAC
2.531
0,000
TRPO-FAC
2.3596
TRPO-FAC
0:4819
0.0099
CPO
2.098
0.1713
0.0063
CEO
2.3925
01188
0.0254
CPO
2.6430
0.291
0.011
POPO
2,4928
0.5763
0.0061
PCPO
2.5075
0.1521
0.0225
PCPO
2.0249
0.5843
0.0052
SCPD
2.5822
0.0407
0.0013
SCPO
2.5977
0.0887
0.0000
SCPO
2,5733
0.1427
0.0020
Table Metrics three Point-Pillat experiments obtained from the final epoch.
(a) Point-Pillar-1
(b) Point-Pillar-
(c) Point-Pillard
Algorithu
31.
P1
Algorithm
J.
32.
Algueitha
14.
A
TRPO
2.5038
TRPO
0.0212
2.5772
0.3218
01022
TRPO-Lagrangan
20000
012775
0,0.00
LagooLagoooo
2.0164
0.0632
0.012
TRPO-SL
2,5049
0.1191
0.0044
TRPO-SL
2.5177
0.2548
0.008L
TRPO-LL
2.5585
1,5200
0,0074
TRPQ-1SI
2.5921
0.1853
010211
TRPO-USI.
2.5025
0.2977
0.043
TRPO-USE
2,5896
0.6713
0.0122
TRPQ-PP
2,0500
0.2858
0.026
TRPO-IPO
2.5858
0.1281
0.066
TRPO-IPO
2,6085
3.4806
0.0212
TRPO-FAC
2.6362
01013
TRPO-FAC
2,6105
0.3215
TRPO-FAC
0.4257
0.008
CPO
2.5720
0.9323
0,5655
0.0166
PCPO
2,5700
2,3022
0.0003
SCPO
2.3307
SCPO
0.2589
0.0024
Table Metrics of three Swimmer- experiments obtained from the final epoch.
(a) Swimmer- Hazard-1 1
(b) Swimmer-Hazard-4
(c) Swimmer Hazard-8
Algorithun
Algorithm
Algoritham
11.
TRPO
2.00822
0.5395
0.0070
TRPO
2.5897
(12315
0.0K33
TRPO
2,0322
0:4843
0.0087
TRPO Logaagian
2,8044
0.0066
TRPO Legrangion
TRFO Logrondion
0.4216
0.0058
TRPO-SL
2.5200
TRPO-SI
2,5056
TRFO-SE
9.0948
0.0010
TRPO-IPO
2.3844
TRPO-IPO
0.4843
0.0057
TRPO-FAC
2.5755
0.3139
0.051
TRPO-FAC
2.3886
0.1387
TRPO-FAC
2.037
0.560)
0.0050
C20
2.8185
0.4115
0.0099
CPO
20023
0.1368
0.022
CPO
2:6333
0.4201
0,0045
POPO
2.5741
0.4670
0.0061
PCPO
2,5922
0.4365
0.0083
PCPO
2.6895
0.7420
0.2063
SCPD
2.0001
0.0743
0.0009
SCPO
2.6317
0.1082
0.0012
SCPO
2,5011
0.1527
0.0030
Table 8: Metrics of three Drone-3DHazarr experiments obtained from the final epoch.
(a) 1rane-3Dazarrd-1
(b) Drone-3DHazari-
(c)
Algucithu
34,
Algorithm
J.
.2.
Algusitha
M4.
R
0.0011
TRPO
2.1668
TRPO
0.4561
0.0057
TRPO Lagrangian
2,1149
0,0206
010077
TRPO- Lagrangannn
2.4175
011990
0.0022
TRPO Lagrongion
2.42377
0.3982
0.0033
TRPO-SL
2,4000
0.0044
0.000
TRPU-SL
2.3748
0.0529
0
TRPO-SL
2.4555
0.1655
0,0022
TRPO- USL
2.3700
0.0030
0.9088
TRPO USL
2.4658
0.1264
0.0017
TRPO-USL
2.4485
0,2052
0.3637
TRPO-IPO
2.5721
0.3032
0.011
TRPO-IPO
2.1168
0.3305
0.022
TRPO-IPO
2.4206
0.4561
0.3057
TRPO-FAC
2.3556
TRPO-FAC
2:3800
01887
TRPO-FAC
0.309)
0.022
CPO
2.3906
PCPO
0.5179
0.0002
SCPO
2,4034
SCPO
0.0012
Table 9: Metrics of Ant-Hazard and Walker- Hazard experiments obtained from the final epoch.
(a) Ant-Hazard-8
(b) Walker-Hazarde Hazard-8
Algoeithm
17.
2:
Algorithm
M2.
6:
TRPO
2.6203
0.1850
0.0054
TRPO
2.6771
0.8274
0.0095
TRPO- TRPO-Lagmagenn
2.6336
0.1017
0/0038
TRPO-Lagrangnt
2.1107
0.2151
0/0071
TRPO SL
2.5522
4.1250
RUS510
TRPO-SL
2.6476
0.9563
0.0224
TRPO-USL
2.6533
0.2138
0.063
TRPO-USE.
2.6239
0.3145
0.0095
TRPO IPO
TRPO JPO
03115
0.0066
TRPO-FAC
0,0011
TBPO-FAC
0.004
0.1133
0.1379
PCPO
2.0281
0.0059
0.077
SCPO
2.5873
0.03227
0.0021
SCPO
23751
0.0546
0.0029
27

---

Published in Transactions on Machine Learning Research (04/2024)
Reward, Performance
Roward Performance
Reward Performence
2.
TRPO
cRS
187D
marc-sL
TRPO
TRPO
CPO
INPO Lagrangion
INPO Po
PCOP
TRFO Lagrangon
19P0-1P3
Eoro-Legrnnge Legranginn
IntaiEnvinterracts
166
TotalEnvinteracts
166
TotalEnvinteracts
105
TRPO
TRRO-U3
TAPO
TIP
09
Legrangann
3.0
TRPO -aamnngn
TRPO-10
RC0P
TRPO-LL
mro-Ac
50h0
Cost Performance
Pertomranc
2.5
Cost. Performance
2.0
0.0
TotelEnvinteracts
166
TotalEnvinteracts
leG
ToteaEnninteracts
1c6
TRPO-PO
TRF-PFC
Performance
TRPO-5L
TAFO Po
mrc-MA
5300
RCP
Cost Rate. Performance
miho
TpP APC
5cr0
2.6
pate
3.1
TotelEnwinteracts
TetalEnvinteracts
1eb
TotaIEniinteracss
Point-Hazard-1
Figure 11: Point-Hazard (b) Höint-Hazard-4
(c) Point-Hazatee
28

---

Published in Transactions on Machine Learning Research (04/2024)
Reward Performance
Reward Performance
Reward Performance
-2
1R-0
TePO USL
CP0
TIPO
TRP0 USL
GPO
TRPO
TSPO
CPO
TEPO- aagraagggnnnn
roon
RotatEnvinteracts
1c6
Eninttanittssactts
106
TotalEnvinteracts
1e5
TRPO-U9
TAPO
TRPO
CP0
unghnn
3.0
Lapo
IMPC-19
Cost Perfornanc
Cost Bortomrang
2.5
Cost Performance
0.6
3.5
0.4
1.0
0.2
0.5
0.0
0.0
Inttarn
166
TotatEniinteracts
le6
TetelEnvinteracts
165
TRPO-SL SL
TRPO-Lag
TRA0 P0
T110-ACC
RCP 5CN
Performance
TRPO-SL
TAFO Po
5300
RCP
Cost Rate Performancs
TRPO-Lagrangie
TARO
3.0
1.5
0ost Rate
3.0
1.0
0.5
3.0
TntalEnvinteracs
1eb
TetalEnvinteracts
1eb
TollEniinteesats
Poilt-Pillar-1
(b) Point-Pillar-4
(c) Point-Pillats
Figure 12: Soint-Pillar
29

---

Published in Transactions on Machine Learning Research (04/2024)
3.0
3.0
Reward Perfomance
2.5
Reward Performance
2.5
Reward Performance
2.5
2.0
2.0
1.5
1.0
1.0
1.0
0.5
0.5
0.5
0.0
mano-aggaaga angian
US
TAPO
anglan
TAPO
GPO
roon
9.0
TAPO
srggann
CPO
TotalEnvinteracts
1c6
Tottalnninteraatss
166
TotalEnvinteracts
166
TRPO
TAPO
TRPO
C20
Laporay
2.0
TSPO-SL
Cost Performance
Cost Cost_Perte Performance
Cost Performance
2.5
0.5
TotelEnvinteracts
166
TotalEnvinteracts
leG
TotalEnvinteracts
1e5
Cost nate, Performance
TT/OO-LL SL
TRPO
Cost Performance
TRPO-SL
TRPO-Lagnno
TAFO-PO
mrc.AAc
RCOP
53N
Cost Rate Performance
TRNO
TRPO
TRPO-AM
TocalEnvinteracts
TetelEnvinteracts
1eb
TetlEnniinterecs
(a) Helmmmrr-Hazarde
(b) Swimmer-Hazze
(c) Swimmer Hazard-8 Swimmer-Hazzrd-88
Figure 13: Swimmer- Hazard
30

---

Published in Transactions on Machine Learning Research (04/2024)
161
161
Rewerd Performncc
0.0
Reward Performance
0.0
Rewradd Performance
-0.2
-0.2
-0.4
--06
-0.6 14
0.8
-1.0
TIRO
US
CP0
-1.0
TAPO
US
TRPO
TRPO
CPO
TRPOALegaane Leggangann
-1.2
TotalEnvinteracts
1c6
Total Envinteracts
le6
TocalEnvinteracts
165
TRRO-USI
CPO
3.0
TAPO
TRPO
C20
Lapo-ag
1.2
2.5
Cos perforance
dertommance
Cost Performance
2.0
0.8
3.5
0.4
0.5
0.9
0.0
TotalEnvinteratts
1e6
TotalEnvinteracts
leG
TotalEnvinteracts
1e5
Cost Date Perforance
1.50
TIr PAC
Performance
TRPO-SL
TAFO PO
TIC-MA MC
530
RCP
Cost Rate Performance
TEPO-SL
TRPO-P0 TIP AAC
1.00
0.50
0.00
Ettlnnvitteeacts
TotalEnvinteracts
1eb
TotlEnniitteeets
(a) Drone-3D 3DHazard-1
(b) Drome-3DHazardd4
(c) Drone-3DHazane
Figure 14: Drone-3DHazard
31

---

Published in Transactions on Machine Learning Research (04/2024)
3.0
Reward Performacce
2.5
Reward Performance
1.0
0.5
Layhtngaa
Layring
0.5
16
15
2.0
2.5
30
0.5
1.
15
2.0
2.5
3,0
Total Enviinerrtss
167
Total Envinteracts
167
Lag--aggnnggt TRPO
TRPO
TRa
5090
Cost. Performance
0.5
3.0
1.5
2.0
2.5
3.0
0.5
1.0
1.5
2.0
2.5
3,0
TotalEnvinteracts
107
TotalEnvinteracts
ln?
1c-2
TEPO
TRP0-U5L
620
TiPO
TRPO-UE
020
Cost Rate Performanc
-20 Lagraniion
PPO
TEPO INC
18P0 P0
5CT0
KCP
Performance
2.4
3.2
TAPO Lig
T1Po ANC
T8PO P0
5cT0
KOP
1.0
0.6
1.4
0.2
0.0
TotalEnvinteracts
107
TotalEnvinteracts
167
(a) Ant- Eat-Hazard-8
Walker Walker-Hazarda
Figure 15: High dimensional hazard tasks
32


Reviews:
[{"review_id": "tC7aTwgHBq", "reviewer": "Reviewer_qZLB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[S1] The SCPO formulation is well-motivated and has theoretical analysis (although I did not extensively check the proofs).\n\n[S2] Good performance on SafetyGym benchmark\n- Consistent but often marginal gains, in rewards and episodic costs, over all tasks.\n- Definitively beats methods in average cost over training. \n\n[S3] Contributes harder tasks to the SafetyGym benchmark, although they still seem too easy (see below).\n\n[W1] **Importance of under-sampling trick  for value function learning**: This value function training trick can be applied to the other baselines right? It would be good to see some more ablations into this trick. The authors show an ablation for SCPO without undersampling for one environment. It would be good to show this ablation for all other environments. \n\nThis could be an important empirical contribution for safe RL actor-critic methods if it turns out to be helpful in general. It would also more clearly show the contribution of the SCPO update rule\n\n[W2] **Benchmark seems too easy:** Benchmark seems rather easy. The authors claim they solve high-dimensional tasks giving the impression of difficulty, but I think this is inaccurate. For the 2 hardest tasks, nearly all methods achieve very similar reward and episodic cost metric values. This doesn't seem very hard to me.\n\nIt would be interesting to see some harder higher dimensional tasks like humanoid. The benchmark is also overfit to simple mujoco locomotion tasks, which is well-known to be \"easy\" in terms of exploration and dynamics. Adding more complex tasks, like dexterous manipulation, quadrupedal / humanoid locomotion, would be very interesting.\n\n[W3] **No discussion on resource usage and computational complexity.** Please report GPU / CPU resources needed for the method, baselines, time for experiments, etc. Next, what algorithmic and runtime differences does SCPO have with baselines?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose SCPO, a policy optimization algorithm for solving RL tasks with state constraints. They propose a new formulation that constrains the expected maximum cost incurred over the trajectory rather than expected cumulative cost. Theoretical analysis is provided for this formulation. Their empirical algorithm solves a convex approximation of the objective, and use some implementation tricks like under-sampling to improve  cost value function learning. SCPO shows gains over baselines in robotic tasks in the benchmark SafetyGym.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Requested Changes\nSee above for details.\n- More through analysis / ablation of the under-sampling trick wrt baselines and SCPO itself. I ask this because I don't want to have a method whose claimed algorithmic gains come primarily through an implementation trick. \n- It would be nice to show (positive or negative) results on harder tasks. The current tasks are just barely over the bar (marginal but consistent gains) for demonstrating SCPO's effectiveness. Even negative results for SCPO or methods in general will be useful, since I think the SafetyGym tasks seem too easy. This would outline a good future direction for future work; I do not want future work to waste their efforts chasing marginal gains on a saturated benchmark. \n\n## Clarification Questions\n**Why does maximum cost formulation result in empirically lower average cost over expected cost formulation baselines?** SCPO seem to have lower average cost (cost rate) over training. Since SCPO constrains the expected maximum cost over the trajectory, it could pick policies that have relatively high average cost per timestep but low maximum cost over the entire trajectory.  For example, it could have a trajectory with costs (1, 1, 1, 1 .... 1.01). The maximum cost of this trajectory is 1.01, but all other steps still have high costs. Would this trajectory be considered equal to a trajectory with all zeros but one step with 1.01 cost? \n\nCan this work with costs with negative values? The method seems to assume non-negative cost increments.\n\nEq 2 / 3 seem to use the same left hand variable, but have different right hand definitions? Are they equivalent?\n\nSec 3.3 is rather laconic in setting up its definitions in the first paragraph. Could the authors attempt to add a bit more explanation in the MMDP explanation, considering the importance of this setup?\n\nFollowing that intuition, we define a novel Maximum Markov-Decision Process (MMDP), ...\nThe cost increment functions definition should it be: $D_i : (S, M^i) \\ldots$?\n\nAugmented state definition seems a bit imprecise. Is it only part of $\\mathcal{M}^m$ or any arbitrary $\\mathcal{M}$?", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3EstqvnXAi", "reviewer": "Reviewer_VjA5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: the problem is important, the method seems novel and interesting (as far as I could understand it) and the results look promising.\n\nWeaknesses: The main difficulty is that there seems to be a discrepancy between what is promised in the text, and what the equations actually seem to do. Briefly, the text suggests that the method can provide hard guarantee on the maximum state-size cost ever encountered, but in practice the equations are all about expectations (i.e. averages) over multiple trajectories. \n\nTop of p. 4, we are told that the goal is \"to persistently satisfy a hard cost constraint *at every step* (as opposed to cumulative costs over trajectories)\"... (emphasis original!).\n\n....but then Eq. 6 (and following) denote the *expected* cost over all transitions from all trajectories from a given policy! This should be equal to the \"cumulative costs\" (not just within an episode, but over all encountered episodes) divided by sample size.\n\nSimilarly,  Eq. 9 is an expectation (of maximum cost) over all trajectories! A policy could keep this quantity under a maximum w_i (as in Eq. 10), while still encountering arbitrarily high costs (much larger than w_i) in rare transitions/trajectories. Thus it is not clear exactly what guarantee is provided - about absolute maximum, or about expectations over many trajectories.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new RL algorithm for constrained policy optimization, which aims to minimize constraint violations while preserving high performance. \n\nThe method relies on modifying the standard Markov Decision Process formulation to include a term for the maximum cost encountered so far in a trajectory - or more precisely, for statewise increments in this maximum (if any). The aim is to maximize expected discounted returns, while keeping maximum costs encountered under a minimum.\n\nThe algorithm also includes a trust-region penalty. Theoretical guarantees on the constraint violations and performance are derived. Experiments show that the method can reduce constraint violations in comparison to various alternative methods, while preserving high performance. \n\nMore detailed summary:\n\nThe introduction specifies the goal: \"design a policy improvement step that not only guarantees worst-case performance degradation but also ensures state-wise cost constraints.\"\n\nThe language is that the method provides hard guarantees on the maximum cost at each individual step, but the equations are all about expectations. This poses a difficulty in interpreting the paper. See below.\n\nEq. 4: d_i is a maximum acceptable [either max or sum-of-discounted] cost (as estimated by function C_i) over an episode.\n\nM seems to represent \"the maximum transition cost encountered so far in a given trajectory\" (That's how I interpret Eq. 8 and the definition of M_it just below it). Di represent \"how much larger the cost at this particular transition is than the previous maximum\", thresholded at 0. \n\nEq. 9 suggests that the goal is to keep the expected sum of D below a certain maximum. \n\nEq. 11: you want the new policy to satisfy the constraint *and* to be within a small Dist (to be defined) of previous policy.\n\nEq. 12 is the actual equation for the proposed method (IIUC), including a trust-region penalty.\n\nProp 1 seems to say that a policy found by satisfying Eq. 12 will meet the maximum-cost-increment criterion (again, in expectation!) (Presumably this assumes that the previous policy pi_k also met the criterion).\n\nEnd of section 5 discusses some approximations that make the method practical.\n\nFigure 4 seems to show that SCPO minimizes the costs better, while achieving competitive returns.  Figure 5 shows actual \"state-wise costs\".", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There should be a clarification in the main text of what exactly the objective is. The text of the article suggests that the method seeks to provide constraints on the maximum cost encountered so far in any given trajectory - in the authors' own words, \"\"to persistently satisfy a hard cost constraint *at every step* (as opposed to cumulative costs over trajectories)\". However, the equations are all about  expected average over many trajectories, which is precisely equal to these \"cumulative costs\" up to a divisive constant. This apparent discrepancy should be resolved in the main text.\n\nOther requested changes:\n\np.1 degredation -> degradation\n\nEq. 2 and 3 define the same quantity J_Ci(pi) as two different things!\n\nSecond paragraph of p.5 has the Schulman citation with parenthesis in the wrong place (pro-tip: define \\cite as \\citep in your latex file). (Nitpick: TRPO isn't very \"recent\"!)\n\n\"is bounded\" -> \"to be bounded\". \"solving following\" -> \"solving the following\".\n\nIn Eq. 12, in the last line, why does it include a term for the expected advantage? The equation seems to say that candidate policies with high advantages must have a lower expected cost J_D to be accepted - why is that?\n\nP. 7: Citation to Ray et al. again has wrong parenthesis. There should be parentheses around the \"Figure XX\" references.\n\nFigure 4 seems to show that SCPO minimizes the costs better, while achieving competitive returns. Though again, these are some averages.  Figure 5 shows \"state-wise cost\", which would better match what the text of the article proposes (in the authors' words, \"hard cost constraint at every step (as opposed to cumulative costs over trajectories\"). How exactly is it computed? That is, for each point in Fig.5, what is the sample over which we take the maximum?", "broader_impact_concerns": "I do not see any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "n1UhJzpyS5", "reviewer": "Reviewer_u6rH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- The paper is very well written.\n- The problem formulation _seems_ novel, and, more importantly, could be a useful adjustment to existing formulations.  \n- The method seems to perform well, and has nice tie-ins to existing results (e.g. TRPO).  \n- The paper as a whole is about the right level and tone for TMLR. \n\n## Weaknesses\n\n1.  I don't know if the formulation in (6) does really does correspond to the intended objective.  (6) states that the policy only needs to satisfy the constraint in expectation at each timestep.  This is a small and slightly disappointing departure from the setup, eg the final paragraph of the introduction.  \n    - For tasks that have different intermediate \"horizons\" as well, this per-timestep interpretation gets a little warped, e.g. if one environment is completed in H/2, whereas another is completed in H, then comparing rewards/costs-to-go on a per-timestep basis is a little tricky. \n\n2.  Beyond this, the technical contribution is minor, in my opinion.  The MMDP (and even CMDPs) is just an MDP under some constraints on the policy set.  I don't really see that as a ``contribution''.  The bound in (12) is similar in its construction to the TRPO bound.  I expect this bound to be _very_ loose (this is not checked in the empirical evaluation).  The reformulation to allow function approximations to be used tractable is nice, but the accuracy or sensitivity to these function approximations isn't really established or investigated.  \n\n3. I'm also not sure if the empirical evaluation really zeroes in on the actual pre-existing deficiency.  They sort of just seem to show that the proposed algorithm ``works''.  Extra evaluation of small-scale failcases that can be really well understood and analyzed would have helped convince me that the proposed formulation is unequivocally addressing the deficiency.  Maybe an extra experiment where there is a hazard that appears at a specific timestep and hence amortizing infractions over the trajectory leads to more infractions?\n\n## Minor Weaknesses.\n- Only proper nouns should be capitalized (\"Markov Decision Process\" -> \"Markov decision process\").\n- Use \\citet and \\citep where appropriate. \n- It is not clear in a lot of the expressions what the subscripts are indexing.  More consistent inclusion of $i \\in 1,\\ldots,m$ would be helpful.\n- Figures and tables (e.g. Fig 3) should be floated to the top of pages.  \n- \"Cost Rate\" in Figure 4 is undefined.\n- The transition from (2) to (3) is unclear -- please be more precise.\n- (maybe personal preference) I don't especially like for formatting/content of Remarks 1 and 2.  If these are important points, then maybe they should be included in the proposition or theorem somehow?  If these are direct results of the proposition, then they probably should be just normal text.  Remarks are often reserved for non-obvious follow-ons.  RIght now they disrupt the flow.\n\n## Summary.\nI think this paper is at the requisite level for TMLR.  I don't think the contribution is huge, but i think is relatively self-contained and is a useful method/exposition to have in the public domain.  The results are sufficient, even if they don't bowl me over.  I have a number of small requests that need to be fixed prior to inclusion.  I then have a few small suggestions, but these are not hard conditions for inclusion. \n\nGood work, and good luck.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper tackles reinforcement learning in Markov decision processes with (soft) constraints that must be satisfied at each point in time.  This is as opposed to existing ``constrained'' methods, where the (soft) constraints must only be met in expectation across time.  A new formalism, bound, and learning method are introduced for operating in this regime.  The constraints are re-formulated so that they can be efficiently estimated.  Some results on a safety-oriented benchmark are shown, and the algorithm appears to perform as desired on these tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.  Fix all Minor Weaknesses.\n2.  If you could evaluate/probe the tightness of the bounds then that would be super helpful. \n3.  More evaluation/reflection on whether imposing constraints per-timestep is (a) well-founded mathematically (c.f. 2),  (b) actually corresponds to something better than alternatives (e.g. including just a large negative reward penalty for infractions),  (c)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As detailed above, the paper now makes a clear and consistent case for its proposal of a new algorithm suited to a specific notion of safety in reinforcement learning. It is not without limitations as pointed out above in the "claims and evidence", but it is the AE's opinion that the findings remain valuable to share to the TMLR audience.
Decision: Accept (poster)