Flipping-based Policy for Chance-Constrained Markov Decision Processes
Authors: Xun Shen
Shuo Jiang
Akifumi Wachi
Kazumune Hashimoto
Sebastien Gros
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
Chance constraints
Stochastic policy
Primary area: reinforcement_learning
TL;DR: We present a flipping-based policy for safe reinforcement learning and provide theoretical foundations for its optimality and practical implementation.

Abstract: Safe reinforcement learning (RL) is a promising approach for many real-world decision-making problems where ensuring safety is a critical necessity. In safe RL research, while expected cumulative safety constraints (ECSCs) are typically the first choices, chance constraints are often more pragmatic for incorporating safety under uncertainties. This paper proposes a \textit{flipping-based policy} for Chance-Constrained Markov Decision Processes (CCMDPs). The flipping-based policy selects the next action by tossing a potentially distorted coin between two action candidates. The probability of the flip and the two action candidates vary depending on the state. We establish a Bellman equation for CCMDPs and further prove the existence of a flipping-based policy within the optimal solution sets. Since solving the problem with joint chance constraints is challenging in practice, we then prove that joint chance constraints can be approximated into Expected Cumulative Safety Constraints (ECSCs) and that there exists a flipping-based policy in the optimal solution sets for constrained MDPs with ECSCs. As a specific instance of practical implementations, we present a framework for adapting constrained policy optimization to train a flipping-based policy. This framework can be applied to other safe RL algorithms. We demonstrate that the flipping-based policy can improve the performance of the existing safe RL algorithms under the same limits of safety constraints on Safety Gym benchmarks.

Flipping-based Policy for Chance-Constrained Markov Decision Processes
Xun Shen
Shuo Jiang
Osaka University
Osaka University
shenxun@eei.c eng. osaka-u.ac.Jp jc.jp
u316354h0ecs. osaka-u.akk ac jp
Akifumi Wachi
LY Corporation
aki fumi wwwhi@@yyoorp.co...
Kazumune Hashimoto
Sebastien Gros
Osaka University
Norwegian University of Science and Technology sebastien, .ot..iinn..oosttnu.noooo
hashimoto@eei. eng. osaka-u.ac. jp.
Abstract
Safe reinforcement learning (RL) is a promising approach for many real-world decision decision-making making problems where ensuring safety is a critical necessity. In safe RL research, while expected cumulative safety constraints (ECSCs) are typically the first choices, chance constraints often more pragmatic for incorporating safety under uncertainties. This paper proposes flipping-baat policy for Chance- Constrained Markov Decision Processes (CCMDPs). The flipping-bas -based policy selects the next action by tossing potentially distorted coin between two action candidates. The probability of the flip and the two action candidates vary depending on the state. We establish Bellman equation for CCMDPs and further prove the existence of flipping-basee policy within the optimal solution sets. Since solving the problem with joint chance constraints is challenging in practice, we then prove that joint chance constraints can be approximated into Expected Cumulative Safety Constraints (ECSCs) and that there exists flipping- baaeeng-based policy in the optimal solution sets for constrained MDPs with ECSCs. As specific instance of practical implementations, we present framework for adapting constrained policy optimization train a flipping-based policy. This framework can be applied other safe RL algorithms. We demonstrate that the flipping- -baed policy can improve the performance
existing safe RL algorithms under same limits of safety constraints Safety Gym benchmarks.
Introduction
In safety-critical madiiinnn-mainnggg problems, such healthcare, economies, and autonomous driving, it is fundamentally necessary to consider safety requirements in the operation of physical systems to avoid posing risks to humans other objects [14
19 43 Thus, safe reinforcement learning (RL), which incorporates safety in learning problems 19] has recently received significant attention for ensuring the safety learned policies during the operation phases. Safe RL is typically addressed by formulating a constrained RL problem in which the policy is optimized subject to safety constraints The safety constraints have various types of representations (e.g., expected cumulative
I5 32 49]
safety constraint 4 5 7 instantaneous hard constraint [36] 45), almost surely safe [9] 44), joint
chance constraint
29
In many real applications, such as drone trajectory planning 40 and
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Problem CCRL
Problem ECRL
Hlipping-hased policy - Optimality Theorem Existing safe RL algoritum Optimal flipping- based policy Theorem 6. Theorem 7
will.
may (+())
Conservative approsinaation Theorem
maa
(*())
Share the same optimal value Theorem
S.t.
P Sp
Traat (ills)) N80
50
Share the same optimal value Theorem 2
Problem PMO
Problem FPO
Flipping-hased pollcy
J. 1% (s.
2x2 (s, acs)) + w/22 (e.aaz)
MEAIAA)
J (s.)ddp
K.S. at?" (e, squ) (1 w/T" (s. Res)) 1-a.
Figure I: Summary of the relations among main theorems and problems in this paper.
planetary exploration [ safety requirements must be satisfied at least with high probability for a finite time mission, where joint chance constraint is the desirable representation 33 43
Related work. The optimal policy for RL without constraints with hard constraints is deterministic policy [10] [9]] Introducing stochasticity into the policy can facilitate exploration [ 38 and fundamentally alter the optimization process during training [66 21 37], affecting how policy gradients are computed and how the agent learns to make decisions. It has been shown that the optimal policy for a Markov decision process with expected cumulative safety constraints is always stochastic when the state and action spaces are countable [3]. Policy-splitting method has been proposed to optimize the stochastic policy for safe RL with finite state and action spaces [[2]. In 35. an algorithm was proposed to compute a stochastic policy that outperforms deterministic policy under chance constraints, given known dynamical model. In more general settings for safe reinforcement learning, such with uncountable state and action spaces, the theoretical foundation regarding whether and how a stochastic policy can outperform a deterministic policy under chance constraints remains an open problem. Developing practical algorithms to obtain optimal stochastic policies with chance constraints requires further investigation.
Contributions. We present a Bellman equation for CCMDPs and prove that a flipping- based policy archives the optimality for CCMDPs. Flipping- -baed policy selects the next action by tossing poten- tially distorted coin between two action candidates where the flip probability and the two candidates depend on the state. While solving the problem with joint chance constraints is computationally challenging, the problem with the Expected Cumulative Safe Constraints (ECSCs) can be effectively solved by many existing safe RI. algorithms, such as Constrained Policy Optimization (CPO, I). Thus, we establish theory of conservatively approximating the joint chance constraints by ECSCs. We further show that a flipping-based policy achieves optimality for MDP with ECSCs. Leveraging the existing safe RL algorithms to obtain a conservative approximation of the optimal flipping-based policy with chance constraints is possible. Specifically, we present a framework for adapting CPO to train a flipping- tipping-based based policy using existing safe RL algorithms. Finally. show that our proposed flipping-base based policy can improve the performance of the existing safe RL algorithms under the same limits of safety constraints Safety Gym benchmarks. Figure] summarizes the main contributions.
2 Preliminaries: Markov Decision Process
A standard Markov decision process (MDP) is defined as a tuple. A,, ,.))- Here, S is the set of states, A is the set of actions, r S A R is the reward function. This paper considers the general case with state and action sets in finite-dimension Fuclidean space, which can be continuous or discrete. Let B(-) be the Borel o-algebra on metric space and (-) be the set of all probability measures defined on the corresponding Borel space. The state transition model T : SS A + (S) specifies a probability measure of a successor state s+ defined on B (8) conditioned on a pair of state and action, (s. E S x A, at the previous step. Specifically, we use p(-|s, a) define conditional probability density associated with the state transition model T(s, a). Finally, Ao is the distribution of the initial state So E S. A stationary policy S (AA a map from states to probability measures on (A, B (A)). We use π (-Is) to define a conditional probability density associated with n(s), which specifies the stationary policy. Define trajectory in the infinite horizon by T == (So, ag, 81, a1,,...., Sk, ......) An initial state So and a stationary policy defines unique probability measure Pr the set (S x A) of the trajectory To

---

22 The expectation associated with Pr is defined as B Given a policy π E II, the value function at an initial state So is defined by (*(s) Bra-Prt { So - s} with R(T:o)= == Σx=o r (Sk, ax), where y E (0,1) as the discount factor. Also, the action-value function is defined as (s, a) == r(s, a) + +. (V*(s*) 80 S, a = a}
3 Flipping-based Policy with Chance Constraints
constrained Markov decision process (CMDP) is MDP equipped with constraints restricting the set of policies. Let 3 be the "safe" region of the state specified by continuous function S - IR in the following way: $ == {s E S g(s) S 0}. Let T E N+ be the episode length. As suggested in 30 31, the following joint chance constraints is imposed:
Pr {Sk+1 E Vi E [T] Sk E S} 2 1 a, AA 0, 2,
(1)
where a E 1) denotes a safety threshold regarding the probability of the agent going to an unsafe region and (7] == T? is the index set. The left side of the chance constraint [ is a conditional probability, specifying the probability of having states of future 7 steps in the safe region when 85 is inside the safe region. When the system is involved with unbounded uncertainty w, it is impossible to ensure the safety with a given probability level in infinite-time scale [18]. Instead, ensuring safety in future finite time when the current state is within the safety region is reasonable and practical [20]. This paper calls the MDP equipped with chance constraint ( as Chance Constrained Markov decision processes (CCMDPs). refers to the problem with almost surely safe constraint when a = 0. The set of feasible stationary policies for a CCMDP is defined by II := { II Vs& E S, ① holds} Chance constrained reinforcement learning (CCRL) for CCMDP is to seek an optimal constrained stationary policy by solving
max TEI
(s).
(CCRL)
Define optimal solution set of Problem CCRL by II: == E V*(()= max V (s*(s)
Let n. E I,; be an optimal solution of Problem CCRL Associated with n. we denote (s == V (s) and Q; (s, a) = Q (s. for the optimal value and value-action functions.
Define a function F* (s. a) = Pro..o (Sk+* E E,,, Vi E [7] 8& = 8, = =a}. The continuity of
Pd as is guaranteed under mild conditions giving as Assumptions and 2 (pp. 78-79 of (5)).
Besides, the upper semicontinuity of Q (s. a) is from Assumption |
Assumption 1. Suppose that A is compact and r(s, a) is continuous on S A. Besides, assume that the state transition model T can be equivalently described by s = [s, a, w). where w E W C R. is random variable and f(-) is continuous function S x W. The probability density function is pw (w).
Assumption I is natural since it only requires that the reward function is continuous and the state transition can be specified by state space model with a continuous state equation, which is general in many applications. We do not require f() to be available.
Assumption 2. The constraint function g(-) is continuous. For every s E S and a E A, we have
Pr
max g($k+s) = 0 s = =,,a; = a = 0. (E(T]
8,50
Assumptions and 2 are essentially assuming the regularities of and T(s, a), which is not a strong assumption. With 1st a), we define probability measure optimization problem (PMO) by
/ 100% (s, a)
(s. f
max (.M(
S.l.
du 2 1-
(PMO)
We have the following theorem for the optimal constrained stationary policy nद of Problem CCRL Theorem 1. The optimal value of Problem PMO equals Vz (s) for any S. The probability measure ph associated with T (-Is) is an optimal solution of Problem PMO for any s E S.
In this paper, we refer to uniform continuity.
3

---

The proof is based on the following idea. After showing that (s) is not larger than the optimal value of Problem PMM]lemPMMO]p we then prove that V (s) can only equal to the optimal value of Problem PMO by contradiction. See Appendix B for the proof details. From Theorem D we know that the solution of Problem PMQ gives the probability measure associated with the action's 's probability distribution T (-ss given by the optimal stationary policy, which is Bellman equation for CCMDPs.
Problem PMO difficult to solve since we must optimize a probability measure, an infinite- dimensional variable. We further reduce Problem PMO into the following flipping-based policy optimization problem (FPO):
max ((1) (
w (s, a(1) + (1 w)Qa (s, a(2))
(FPO)
S.L. wP* (s, (1)) + (1 - w) (s, a2))) 2 1- - Ct.
We have the following theorem for Problem FPO
Theorem Suppose that Assumptions and
2 hold. The optimal objective value of Prob-
lem FPO equals (s) for every E S. Let the solution of Problem [FPO be zs ==
((1) (s), a (s), w (s) Define stationary policy (-ss) that gives discrete binary distribution
for each s, laking a ((1)(s) (s) with probability (s) and a 22z) (8) with probability 1 - w ws)).
The policy (-1s)) is an optimal stationary policy with chance constraint, namely, #- E 11a
The proof based on the following idea. We first show that Problem PMO an optimal solution that is a discrete probability measure (Proposition T in Appendix C). We then apply the supporting hyperplane theorem and Caratheodory's 's theorem to show further that the discrete probability measure simplifies the optimizing of the policy in a probability measure space for each into an optimization problem in finiteddimensional vector space. An optimal stationary policy gives a discrete binary distribution for each state s. This paper calls the stationary policy with discrete binary distribution as fllipping- bassed policy since it is similar to the process of random coin flipping, taking
can be focused on two points. See Appendix C for the proof details. Theorem 2
{ (s) with probability
w" (s) and a = a/2) (s) with probability 1- (s). We summarize one condition that the deterministic policy enough for the optimality of Problem [CRL Theorem 3
See Appendix for the proof.
Theorem 3. Suppose that Assumptions 7 and 2 hold. There exists deterministic policy that achieves the optimality of Problem CCRL
when when
4 Practical Implementation of Flipping-based Policy
This section introduces the practical implementation of flipping-based policy. Obtaining the optimal flipping-based policy for CCMDP intractable due to the curse of dimensionality (38] and joint chance constraints 43 The parametrization can tackle the curse of dimensionality. The issue by joint chance constraint resolved by conservative approximation. The common conservative approximation for joint chance constraint is the linear combination of instantancous chance constraints. We further show that it is possible to find an expected cumulative safety constraint to conservatively approximate the joint chance constraint, which enables Constrained Policy Optimization (CPO) proposed in I to find a conservative approximation of Problem [CRL optimal flipping-bar based policy. We show the optimal and sample safety of the flipping- expected cumulative safety constraint.
flipping-based based policy for MDP with the
4.1 Extensions to Other Safety Constraints
Except for the joint chance constraints, several other formulations of safety constraints exist, such as expected cumulative [6] and instantaneous constraints [46). We extend the optimality of flipping- based policy to other safety constraints to show the generality of our result, which may stimulate further study of designing flipping-based policy for other safe RL formulations.
We introduce the extension of the flipping-base based policy to MDP with single expected cumulative safety constraint. The problem is formulated by
max mEll
(T) 8.t. E
Vunsate (g(s:)) |so = S a,
(ECRL)
4

---

where Yunsafe E 10. is the discount factor and I (z) defines an indicator function with (2) = 1 if
2 > 0 and II (z) otherwise. The following theorem for Problem holds:
Theorem 4. A Hipping-basee policy exists in the optimal solution set of Problem ECRL
See Appendix E for the proof. The proof follows the same pattern of Theorem 2
We first construct
the Bellman recursion with the expected cumulative safety constraint and then prove the existence of a flipping- based policy as optimal policy. The optimality of flipping-base based policy can also be
extended to the safety constraint function with an additive structure in a finite horizon, written by
Ex=1 Pr {s, e S so s}. This safety constraint refers to affine chance constraints [13. We summarize the extension problems with affine chance constraints Appendix
Remark 1. Theorem can be extended to a more general case where the cumulative safety constraint
not limited an indicator function but can be any Lipschitz continuous function, thereby broadening the applicability of our theory to more practical scenarios.
4.2 Conservative Approximation of Joint Chance Constraint
We resolve the curse of dimensionality by searching for the optimal policy within a set II C II of parametrized policies with parameters E θ C R" for example, neural networks of a fixed architecture. Here, use To to specify a policy parametrized by 0. If the assumption of the existence of the universal approximator holds, we can approximate the optimal flipping-basee based policy by using a neural network with state input and z (s) as output. Another representation of the flipping- baaedd policy is using Gaussian mixture distribution, written by (-Is) = w(s) (s), (s) + (1 (s)) (āp2) (s), (s)) The output is (s)) ((2) (s); wss), [s) and (s))
If we have w(s) w² (s), (s) = = (s), and a(2) (s) = 212)(6 for every s, the flipping- based policy using Gaussian mixture distribution can approximate the flipping-based policy with binary distribution when the covariances E{1)(s) and E(2)()) vanish for every s (35]. To simplify the
implementation, we can use the neural network that outputs z (s) and achieve the random search by adding a small Gaussian noise on (11) (s) and (2) (s) during implementation.
Rewrite the joint chance constraint |I with So =s s for parametrized policy by
Pr {sx+s E S, E [T] Ss E $) 2 1 - a, Vk- = 0, 1,
(3)
In local parametrized policy search (LPS) for CCMDPs, updated by solving
max V (s) s.t. (3) and D ((TTOITTO)) S 5.
(LPS)
EE
Here, D(-) denotes a similarity metric between two policies, such Kullback-Leibler (KL) diver- gence, and 8 > O is a step size. The updated policy To.., is parametrized by the solution 0 0x+1 of Problem LPS] The updating process considers the joint chance constraint. Problem LPS is chal- lenging to solve directly due to joint chance constraint. Since MDP with the expected discounted safety constraint can be solved by the existing safe RL algorithm (e.g. CPO). Thus, by introducing the conservative approximation of joint chance constraint, we enable the existing safe RI. algorithm
to obtain conservatively approximate solution of Problem CCRL First, we introduce the formal definition of the conservative approximation:
Definition 1. A function C θ S + R is called conservative approximation of joint chance constraint (3) if we have
C(O, s) < 0, V Pr {sk+* S, [T] Sy E [} 2 1-a, Vk = 0,,,,, ...
(4)
Let Hunsafe (0,s) = E ~Pr (Ein T (g(st)) (So 5} } be value function for unsafety starting with state s. We have theorem of conservative approximation of joint chance constraint:
Theorem 5. Suppose that θ and S are compact and Assumption 2 holds. Define function
Cunsate (0, (0,5 s) by Cunsate (0, 5) = Hunsate (0,s) a. There exist large enough Jiunsañe and small enough T such that Cunsafe (0,s) < 0 is conservative approximation of (
The proof of Theorem 5 is summarized in Appendix of Problem LPS (CLPS) as follows:
F We formulate conservative approximation
max V n (s) s.t. Hunsafe (0,s) S a, D(TTO][TT.) S 5. #
(CLPS)
5

---

the optimal solution of Problem CLPS is feasible solution of Problem LPS and thus the corresponding parametric policy is within 1. We have remark on Theorem 5 as follows:
By Theorem 5
Remark 2. By the same procedure of proving Theorem
S
show that Problem ECRL is
conservative approximation of Problem CCRL
4.3 Practical Algorithms
Then, we present practical way to train the optimal flipping-based policy using existing tools in the infrastructural frameworks for safe reinforcement learning research, such as OmniSafe [24]. The provided tools can train the deterministic or Gaussian distribution-base stochastic policies. We take the parameterized deterministic policies as an example, which is specified by πÿ. The parameter is within a compact set @ We write the reinforcement learning of parameterized deterministic policy (PDPRL) for CCMDPs by
max (() := B wag (R((x s.t. (0) 2 2--a. d
(PDPRL)
Here, the constraint function pd (0) is defined
F 0 = Ber (przée {st E, Vi [T]so)]
Let J and O be the optimal value and optimal solution set of Problem PDPRL Different from the previous discussions, we here consider the expectation of the initial state So instead of considering the problem for each So. The reason is that the provided tools in OmniSafe, for example, CPO [ and PCPO 48) address the problems in which the reward functions consider the expectation of the initial state. We extend the previous results of the flipping-based policy to this case.
Let (()) be the Borel o-algebra (a-field) on O " with Euclidean distance. Let M ( be a probability measure on (θ, ())). With the above notation, associated with Problem PDPRL a reinforcement learning of parameterized stochastic policy (PSPRL) is formulated as:
/ J(O)dR s.t. (
1 F (F) (0) dv 2--21-- 1-a
max
(PSPRL)
Let M. = fm E (()) J0 (O)ddv 2 1 - a be the feasible set of Problem
PSPRL The optimal objective value and the optimal solution set of Problem PSPRL are
Ta maxveM.(e) fo J(0)dz and A. {u E Ma Se J(eddv = J: A proba-
bility measure va E Aa is called an optimal probability measure for Problem PSPRL Define
Vm == I'm E [0, 112 E (i) 1}. Let Sm == (1m(1), pm 0(1,, ((2) be a variable in
the set Zm == Vm x O Consider an optimization problem on Sm. reinforcement Iearning of parameterized flipping-basee based policy (PFPRL), written
Es(0())m max 6m Elim
s.t. Σ (0 21-a
(PFPRL)
i=1
Define Zm.o. := (mm Zm Σ Fd(0 2 21-00 a as the feasible set of Problem PFPRL
In addition, define the optimal objective value and optimal solution set Problem PFPRL by J" min+ J((())
Sm Zm,a and D. := { E Zm,a Σ.= J((( (m)())))())))))))))))))))))))))) J respectively. We have Theorem for parameterized flipping- based policy.
Theorem 6. The optimal values of Problems PFPRL and [SPPL are equal, J = Tw If J is on an interval (a, .), then, Va E a)) Th >> J holds.
strictly convex function
See Appendix G for the proof. Note that Theorem 6 clarifies the existence of a parameterized flipping-based policy achieving optimality and the condition under which it performs better than deterministic policies.
Remark 3. Theorems 6 and have different results on the flipping probability. Theorem 2 claims state nute-dependdnt flipping probability while the flipping probability in Theorem 6 is fixed. The

---

Algorithm 1 General training algorithm for flipping-base bbaend policy
1: Set a positive integer S E + and obtain the sample set 2ş = {ā:):= by randomly sampling
E [0, II, Vi [S] according to uniform distribution
2: Optimize policy parameter 0, for each å, via an existing safe RL algorithm
3: Solving linear program LP and obtain (14()T), 03; 00;
Algorithm 2 Flipping-baser policy implementation
1: Observe the state 8ę at time step 0, 2,
2: Randomly generate number from [0. obeying uniform distribution
3:
If S v,(ii), generate aş by T0 Otherwise, generate ag implement
Problem CCRL the optimal policy for each state is derived based revised Bellman equation, ensuring that the joint chance constraint is satisfied pointwise for every state. On the other hand, Problem [SSPLL focuses the expectation of the joint chance constraint, evaluated over the probability distribution of the initial state. This formulation eliminates the need for pointwise satisfaction across the state space, causing the dependeen nature of the constraint disappear.
distinction arises from subtle difference between Problem CCRL and Problem PSPRL
There is no existing tool to solve Problem PFPRL and we can only apply them to solve Problem PDPRL for any given Let 2s- = {ār â; E 1]. Vi E [S] be set of probability levels. For each dx, define 0 be the optimal solution of Problem PDPRL with dg. Consider the linear program (LP):
S ((0))u s.t. (2( a, Σ (1) =1 (LP)
max (g(1) (5)
Define the optimal objective value and optimal solution set (Zs) of Problem LP by (Zs) and Da())), respectively. The optimal flipping-based policy is characterized by v((5)) 0z: 0/: where j7 and j² are the index for the non-zero elements of the opti-
mal solution of linear program
LP The following theorem holds for (2s)s and (2s).
Theorem There exists an optimal solution (2s)s) such that the number of non-zero elements does not exceed two. Besides, ã4 is extracted independently and identically (uniform distribution). as S + oc, we have (Zs) + Ja with probability 1.
See Appendix H for the proof. Theorem 6 shows that there exists an optimal solution to Problem PSPRL that is linear combination of two deterministic policies. Theorem 7 clarifies that could obtain an approximate flipping-based policy to Problem Problem|PSPRL]p optimizing the linear combination of multiple trained optimal deterministic policies. One is the linear combination of two policies among all possible linear combinations. The above conclusions can be extended to the Gaussian besibbuutonbbbseee stochastic policies. Besides, the above conclusions still hold after replacing the chance constraint with the expected cumulative safe constraint in CPO and PCPO. We summarize general algorithm for approximately training the flipping-baser policy based on the
existing safe RL algorithms in Algorithm With (vs(iT), (5)),, 0,;00, .0;) we implement the flippin-basee policy by Algorithm 2 In the practical implementation, the weight is constant instead of a function of the initial state since Problems (PDRLL and PSPRL] consider the expectation of the initial state. Besides, â; in (1) is replaced by cost limit when using CPO or PCPO to obtain a conservative approximation of
4.4 Safety with Finite Samples
The update by solving Problem CLPS
difficult to implement practically since the evaluation of the constraint function Hunsafe (,s) a is necessary clarify whether a policy π is feasible,
7

---

which is challenging in high- niigh-dimensionaa cases. Here, we apply the surrogate functions proposed in [ replace the objective and constraints of Problem Problem[CLPS) With a probability as 00 a), the CPO-based approximation of Problem CLPS (CPOS) is written by
To max Ro ar- (r(Sini: a}} 8
(CPOS)
1
s.t. Hunsafe (0,, s) +
me Mail Tog
(I(g(s S ass ((TTOl 5 So.
TYunsafe
Note that the optimal solution 0 of Problem CPOS may differ from the one of Problem CLPS Proposition of [ gives the upper bound of CPO update constraint violation. The upper bound depends on the values of the step size d, probability level Ols, discount factor Yumsafe: and the maximal BL+1
expected risk defined by IJa,
ma Ea- [U(g(s+))} The upper bound can be written
28 Nunsale 06+1
by Hunsafe (0 S Ot + factor Yunsafe: and probability level ag, it is able to ensure that Hunsafe (0k-1, a.
(T-aanat)? By choosing sufficiently small step size 6, discount
In practical implementation, the exact value of Eg a~o {I(g(s ))} is unavailable and samples of Sini TT, and a Te are used approximate the CPO update. The data is defined by DN == ((s() ( st((0) i== where N E N+ is the sample number and s+0(0 is sample of successor with previous state s(0) and action ( Instead of directly solving Problem CPOS the following sample average approximate of Problem CPOS (S-CPOS) is solved:
1 N
max BEE
(9) (m
s.t.
Hloe unsafe (0k, 8, Junsafe; DN) S ã. ((TTO S. (S-CPOS)
1=1
Here, Fl (fx: 8, Yunsafe: Dx) == Husafe (0,, + [1- NN E ((g(st(0)) and a E [0, os) is a probability level. The extraction of sample set DN is random, and thus the optimal solution 0a, (s, 0x, Dx) of Problem[S-PPOSi is a random variable due to the independence on the sample set Dr. We need to investigate the probability that 0z, (s, 02. Dx) admits a feasible policy for Problem CCRL We have Theorem X for the safety with finite sample number. See Appendix for the proof.
Theorem 8. Suppose that the step size 6 O and as [0, are adjusted ensure that Hunsafe (0)+1,8) S There exist T and "unsafe such that, if ō, E [0,cx,,, Yunsafe "Tusaaee and T < T, such that 0z, (s. 0x, DN) admits a feasible policy for Problem CCRLL with a probability larger than - exp - (a, -
Note that Theorems 5 and 8 only show the existence of the parameters for safety but do not show an explicit way to choose Tunsafe for specified T. If a conservative safety is desired for practical applications, recommend using TTunsafe close to 1.
5 Experiments
5.1 Numerical Example
We conduct numerical example to illustrate how the flipping-based policy outperforms the deter- ministic policy in CCMDPs. The numerical example considers driving a point from the initial point (0, 0) to the goal (15, 15) with the probability of entering dangerous regions smaller than required value. The uncertainties come from the disturbances to the implemented actions. The metric for evaluating the performance is the cumulative inverse distance the goal, a reward function. Due to the page limit, we summarize the details of the model and heuristic method for obtaining the neural network-based policy in Appendix K Figure 2 (a) shows trajectories by the deterministic policy in one thousand simulations with mean reward as 0.8667 and violation probability as 17%. The red trajectories have intersections with the dangerous region. The deterministic policy led sideway in front of the dangerous regions since crossing the middle space violates the violation probability constraint. Figure (b) shows trajectories by flipping-basee policy. The mean reward was reduced to 1.8259 while the violation probability is 17%, the same as the deterministic policy. The reason is that the flipping-based policy sometimes took the risk of crossing the middle space to improve the mean reward. To balance the violation probability, the sideway root taken by the flipping- based policy was
8

---

(i) Desjectories by deterministte poliry
(b) Prajectories by fipping-busse buused polley
(c) Roward v.s. vinlation proissiiliny
2.5
Mesu
Orgikal
Plyyng base!
0.5
15
10 15
20
0.05
0.1
0.15
0.2
0.25
0.3
0.55
0.4
Violation probability o
Figure 2: Results on the numerical example. Blue dashed lines are feasible trajectories that reach the goal set (grey shaded circle) and avoid dangerous regions (red shaded circles)). Red dashed lines mean that the constraint of avoiding dangerous regions is violated.
(a) Trajectories by the deterministic policy with = 17%. The mean reward is 0.8667: (b) Trajectories by the flipping-based policy with a = 17%. The mean reward is 1.8259; (c) Profile of the mean reward along with the violation probability. Error bars represent the minimal and maximal values across five different simulation sets.
(a) CPO
(b) PCPO
30
25
25
Reward
20
20
1.5
10
-Original
Original
- Flipping- beannng--seddddddd Mean
Flipping- baaenng---eeedddoe Mcan
80
160
180
Cost Limit
Cost Limit
Figure 3: Experimental results on Safety Gym (PointGoal2). Adopting the flipping-base based policy increases the expected reward under the same expected cost for CPO and PCPO at intervals where the reward profile convex. Error bars represent la confidence intervals across five different random seeds.
more conservative than the deterministic policy. Figure 2 (c) gives the profile of the mean reward along with the violation probability. Until around 22%, the flipping-based policy outperformed the deterministic policy since the violation probability of crossing the middle space is larger than that, and the deterministic policy can cross it. The profile in Figure@lnn has convex shape until 22%. Theorem 6 points out that the strict convexity implies the better reward performance of the flipping-hase hased policy.
5.2
Safety Gym
where an agent must maximize the expected cumulative reward under safety constraint with additive structures. The reason for choosing Safety Gym is that this benchmark is complex and elaborate and has been used to evaluate various excellent algorithms. The infrastructural framework for performing safe RL algorithms is OmniSafe (24). The proposed method has been validated in two environments: PointGoal2 and CarGoal2. Four algorithms are used as baselines. The first is CPO [1. well-known algorithm for solving CMDPs. The other three algorithms are PCPO [48), P3O [50]. and CUP [47]. recent algorithms that achieve superior performance compared to CPO. Due to space limitations, only present the experimental results of the test processes for CPO and PCPO on PointGoa12. The details of the experimental setup, all four algorithms' training process results PointGoal2 and their test process results on CarGoal2 are provided in Appendix L
We conduct experiments on Safety Gym 34
Baselines and metrics. We implement the practical algorithms presented in Section 4.3 to obtain the flipping-based policy. We modified Algorithm| [ to train the flipping-based policy based on CPO and PCPO. In Algorithm []] the sample set 2g consists of samples of violation probabilities. Since CPO and PCPO consider the expected cumulative safety constraints, the sample set 2s includes the samples of cost limits of the expected cumulative safety constraints. Instead of using the training

---

(a) CPO
Oraginal (data)
(b) PCPO
Original (data)
Original (Atted)
Original (litee)
0.4
Fapping (froed)
Fliping (talls)
0.4
Flzppigg (data)
Flipping (Bitad)
Vio. Prob.
Vio. Peob.
0.2
0.2
150
100
30
150
100
20
30
Cost Limit
50
10
T
Cost Limit
50
Figure 4: Experimental results on Safety Gym (PointGoal2). The relationship between expected
cumulative safety and violation probabilities.
process, we compared the performance of the testing process, where we implemented the trained policy with new randomly generated initial states and goal points and evaluated the expectations of the reward and cost for each trained policy. We investigate whether the expected reward of each baseline under the same expected cost limit can be improved by transforming the policy into flipping- -baidd policy without any other changes. We employ the expected cumulative reward and the expected cumulative safety as metrics to evaluate the flpping-basee policy and the aforementioned baselines. We execute CPO and PCPO with five random seeds and compute the means and confidence intervals.
The experimental results are summarized in Figure 3 As shown in the figure, for CPO and PCPO, the expected reward increases the expected cost limit rises, and it exhibits convexity at some intervals. At intervals with convexity, the flipping-based policy significantly increases the expected reward. While intervals without convexity, the tipping-based policy does not increase the expected reward. The above observation fits Theorem 6 From the experiments including more details in Appendix [L] we also observe that our flipping-based policy can generally enhance existing safe RL algorithms, although the degree of improvement depends on the original algorithm's 's performance. Essentially, the flipping mechanism is a linear combination of a performance policy (risky but high- performing) and a safety policy (safe but lower-perfone (ever-eeffrming) designed to increase the reward while maintaining the required level of risk. One concern regarding the results in Figure 33 is that the flipping-bat based policy introduces broader confidence intervals. In theory, however, the flippin-bbase based policy does not increase the size of the confidence intervals. This is demonstrated the numerical example in Section 5.1 where the policy achieves solutions closer to the optimal ones outlined in Theorem The practical implementation described in Section 4.3 however, may experience broader confidence intervals due to the presence of two sources of Gaussian noise. It is possible to mitigate this issue by reducing the degree of stochasticity in the policy, for instance, by using smaller variances for the Gaussian noise. This adjustment would not negatively impact the performance in terms of mean reward and cost.
Results.
On the other hand, we summarize the results of the relation between expected cumulative safety and the violation probability in Figure 4 Expected cumulative safety and violation probability follows a linear causality, indicating that the flppingg based policy outperforms the deterministic policy under joint chance constraint. With the same expected cumulative safety, larger T introduces a larger violation probability, which validates Theorem 5
6 Conclusions
In this article, we first introduce the Bellman equation for CCMDP and prove that a flipping-bate based polity exists that achieves optimality. We then proposed practical implementation of approximately training the flipping-based policy for CCMDP. Conservative approximations of joint chance con- straints were presented. Specifically, we introduced a framework for adapting Constrained Policy Optimization (CPO) to train a flipping-based policy. This framework can be easily adapted to other safe RI. algorithms. Finally, we demonstrated that flipiig-bbsed policy can improve the performance of safe RL algorithms under the same safety constraints limits on the Safety Gym benchmark.
10

---

Acknowledgements and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. This work is partially supported by LY Corporation, JSPS Kakenhi (24K16752) Research Organization of Information and Systems via 2023-SRP-06, Osaka University Institute for Datability Science (IDS interdisciplinary Collaboration Project), JST CREST JPMJCR201, and NFR project SARLEM.
References
[1] Achiam, J., Held, D., Tamra, A., and Abbeel, P. (2017). Constrained policy optimization. Proceedings of the 34th International Conference on Machine Learning, PMLR 70: 22-31.
[2] Alshiekh, M., Bloem, R., Ehlers, R., Konighofer, B., Niekum, S., and Topcu, U. (2018). Safe re- inforcement learning via shielding. Proceedings of the AAAI conference on Artificial Intelligence, 32(1).
[3] Altman, (1995). Constrained Markov Decision Processes, RR-2574, INRIA.
[4] Amani, S., Alizadeh, M., and Thrampoulidis, C. (2019). Linear stochastic bandits under safety constraints, Advances in Neural Information Processing Systems, 32: 9256-9266.
[5] Amani, S., Thrampoulidis, C., and Yang, L.. (2021). Safe reinforcement learning with linear function approximation. Proceedings of the 38th International Conference Machine Learning, PMLR 139: 243-253.
[6] Arnb, G., Zhou, X, and Shroff, N. (2022). Provably efficient model-free constrained RL with linear function approximation. Advances Neural Information Processing Systems 35: 13303- 13315.
[7] As, Y., Usmanova, I., Curi, S., and Krause, A. (2022). Constrained policy optimization via Bayesian world models. 2022 International Conference on Learning Representations.
[8] Bajracharya, M., Maimone, M. W., and Helmick, D. (2008). Autonomy for mars rovers: Past, present, and future. Computer, (12)) 44 44-50.
[9] Bennett, A., Misra, D., and Kallus, N. (2023). Provable safe reinforcement learning with bi- nary feedback. Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, PMLR
[10] Bertsekas, D.P. and Tsissiklis, J.N. (2008). Introduction to Probability, Second Edition, Athena Scientific, Belmont, Massachusetts.
[11] Bravo, M. and Faure, M. (2015). Reinforcement learning with restrictions on the action set. SIAM Journal Control and Optimization, 53(1): 287-312.
[12] Chen, H., Lam, H., Li, F., and Meisami, A. (2020). Constrained reinforcement learning via policy splitting. Proceedings The 12th Asian Conference on Machine Learning, 129:209-224.
[13] Cui, Y., Liu, J., and Pang, J.S. (2022). Nonconvex and nonsmooth approaches for affine chance- constrained stochastic programs. Set- Valued and Variational Analysis, 30: 1149-1211.
[14] Dulac-Amold. G., Levine, N., Mankowitz, D.J., Li, J., Paduraru, C., Gowal, S., and Hester, T. (2021). Challenges real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 110: 2419-2468.
[15] Ding, D., Zhang, K., Basar, T., and Jovanovic, M. (2020). Natural policy gradient primal-dum method for constrained Markov decision processes. Advances in Neural Information Processing Systems, 33; 8378-8390.
[16] Ding, Y., Zhang, J., and Lavaei, J. (2022). On the global optimum convergence of momentum- based policy gradient. Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, PMLR 151: 1910-1934.

---

[17] Eckhoff, J. (1993). Helly, Radon, and Caratheodory type theorems. Handbook of Comvex Geometry, A: 389-448.
[18] Gao, Y., Johansson, K.H., and Xie, L. (2021). Computing probabilistic controlled variant sets. IEEE Transactions Automatic Control, 66(7): 3138-3151.
[19] Garcia, and Fernandez, (2015). A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480)
[20] Gros, G. and Zanon, M. (2020). Data-driven economic NMPC using reinforcement learning. IEEE Transactions on Automatic Control, 65(2): 636-648.
[21] Gu, S., Sel, B.. Ding, Y., Wang, L., Lin, Q., Jin, M., and Knoll, A. (2024). Balance reward and safety optimization for safe reinforcement learning: A perspective of gradient manipulation. Proceedings of the AAAI Conference on Artificial Intelligence, 38(19): 21099-211066 106.
[22] Hermandez-Lerma, O. and Lasserre, J. (1996). Discrete-Time Markov Control Processes: Basic Optimality Criteria, Springer.
[23] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58: 13-30.
[24] Ji, J., Zhou, J., Zhang, B., Dai, J., and et al (2023). Omnisafe: An infrastructure for accelerating safe reinforcement learning research, arXiv preprint arXiv:2305.09304.
[25] Kibzun, A., and Kan, Y. (1997). Stochastic Programming Problems with Probability and Quantile Functions. Journal of the Operational Research Society, 48: 846-856.
[26] Lasserre, J. (2010). Moments, Positive Polynomials and Their Applications, Imperial College Press, London.
[27] Luenberger, D.G. (1969). Optimization by Vector Space Methods, John Wiley & Sons, New York.
[28] Melcer, D., Amato, C., and Tripakis, S. (2022). Shield decentralization for safe multi-agent reinforcement learning, Advances in Neural Information Processing Systems, 35: 13367-
[29] Mowbray, M. and al (2022). Safe chance constrained reinforcement learning for batch process control. Computers & chemical engineering, 157: 107630.
[30] Ono, M. (2012). Joint chance-constrained model predictive control with probabilistic resolvabil- ity. Proceedings of 2012 American Control Conference (ACC), 435-441.
[31] Ono, M., Pavone, M., Kuwata, Y., and Balaram, (2015). Chance-constrained dynamic programming with application to risk-aware robotic space exploration, Autonomous robots, 39(4): 555-571.
[32] Paternain, S., Chaman, L., Calvo-Fullana, M., and Ribeiro, A. (2019). Constrained reinforcement learning has zero duality gap. Advances in Neural Information Processing Systems, 32.
[33] Pfrommer, S., Gautam, T., Zhou, A, and Sojoudi, S. (2022). Safe reinforcement learning with chance-constrained model predictive control. Proceedings of the 4th Annual Learning for Dynamics and Control Conference, PMLR 168: 391-303.
[34] Ray, A., Achiam, J., and Amodei, D. (2019). Benchmarking safe exploration in deep reinforce- ment learning. OpenAI.
[35] Shen, X. and Ito, S. (2024). Approximate Methods for Solving Programs in Probability Measure Space. Journal of Optimization Theory and Applications, 200: 150-177.
Linear
[36] Shi, M., Liang, Y., and Shroff, N. (2023). A near-optimal algorithm for safe reinforcement learning under instantaneous hard constraints. Proceedings of the 40th International Conference Machine Learning, PMLR 202:31243-31288
12

---

[37] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and P. Moritz, P. (2015). Trust region policy optimization. Proceedings of the 32nd International Conference on Machine Learning. PMLR 37:1 37:1889-1897.
[38] Sutton, R.S. and Barto, A.G. (2018). Reinforcement Learning: An Introduction, Second Edition, MIT Press, Cambridge, MA.
[39] Seel, K., Gros, S., and Gravdahl, J.T. (2023). Combining Q-learning and deterministic policy gradient for learning- -based MPC. Proceedings of the 62th IEEE Conference Control (CDC), 610-617.
[40] Thorp, A.., Lew, T.. Oishi, M.M.K,, and Pavone, M. (2022), Data-driven chance constrained control using kernel distribution embeddings. Proceedings of Machine Learning Research, 144: 1-13.
[41] Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained Markov decision processes, Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR 119; 9797-9806.
[42] Wachi, A., Hashimoto, W. Shen, X., and Hashimoto, K. (2023). Safe exploration in rein- forcement learning: a generalized formulation and algorithms. Advances in Neural Information Processing Systems, 36: 29252-29272.
[43] Wachi, A., Shen, X., and Sui, Y. (2024). A survey of constraint formulations in safe reinforce- ment learning. In 2024 International Joint Conference on Artificial Intelligence.
[44] Wang. Y., Zhan, S., Jiao, R., Wang. Z., Jin, W., Yang, Z., Wang. Z., Huang, C., and Zhu, Q. (2023). Enforcing hard constraints with soft barriers: safe reinforcement learning in unknown stochastic environments. Proceedings of the 40th International Conference Machine Leurning, PMLR 202:36593-36604.
[45] Wei, H., Liu, X., and Ying, L. (2024). Safe reinforcement learning with instantaneous constraints: the role of aggressive exploration. Proceedings of the AAAI Conference Artificial Intelligence. 38(19): 11708-21716.
[46] Xiong, N., Du, Y., and Huang, L. (2023). Provably safe reinforcement learning with step-wise violation constraints. Advances in Neural Information Processing Systems, 36(2366):5434]- 54353.
[47] Yang, L., Ji, J., Dai, J., Zhang, L., Zhou, B., Li, P., Yang, Y., and Pan, G. (2022). Constrained up- date projection approach to safe policy optimization. Advances in Neural Information Processing Systems, 35(662):911199124
[48] Yang, T.Y., Rosca, J., Narasimhan, K., and Ramadge, P.J., (2020). Projection based constrained policy optimization. 2020 International Conference on Learning Representations.
[49] Ying, D., Ding. Y., and Lavaei, J. (2022). A dual approach to constrained Markov decision processes with entropy regularization. Proceedings of the 25th International Conference Artificial Intelligence and Statistics, PMLR 151: 1887-1909.
[50] Zhang, L., Shen, L., Yang, L., Chen, S., Wang, X., Yuan, B., and Tao, D. (2022). Penalized prox- imal policy optimization for safe reinforcement learning. In 2022 International Joint Conference on Artificial Intelligence.
13

---

Appendix
A Limitations and Potential Negative Societal Impacts
Limitations. The practical algorithm (Algorithm for training the flipping-based policy is adaptable to any safe RI. algorithms. However, it has the following limitations. First, there gap in the scenarios with non-smooth functions. The results should be extended to more practical scenarios with non-smooth functions. Second, training couple policies is required to find an optimal combination for each cost limit. We could not figure out the convexity after getting enough pairs of expected rewards and costs. Third, the probability of the flip the practical algorithm is not state-dependent. Although it achieves the optimality of the parameterized flipping-base baaiinng policy when considering the expectation the initial state, optimality by Theorem 2 has not yet been achieved. Future work should focus designing practical algorithm to obtain the flipping- baaeg policy, for example, training a neural network to take action candidates and the probability of flip as output and the state input. If could develop efficient algorithm learn the flipping-based policy given by Theorem 2] there is no need to consider the tradeoff between performance and computational complexity.
Potential negative societal impacts. We believe that safety is an essential requirement for applying reinforcement learning (RL) in many real-world problems. While we have not identified any potential negative societal impacts of our proposed method, we must acknowledge that RL algorithms, including ours, are vulnerable to misuse. It crucial to remain vigilant about the ethical implications and potential risks associated with their application.
B Proof of Theorem 1
The proof sketch is summarized as follows:
(a) Show that (s) not larger than the optimal value Problem PMO
Assume that Va (s) smaller than the optimal value of Problem PMO
(c) From (b), we can construct a better policy than which implies that V (s) is not the optimal value function;
(d) Since (c) contradicts the fact that (s) is the optimal value function, V. cannot be smaller than the optimal value Problem PMO and only equality holds. From the equality, we prove Theorem |
Following the above sketch, the proof of Theorem is as follows:
Proof of Theorem 7 For state s, let μt (AA) be the solution of Problem PMO and the associ- ated probability density function is (-). Note that π a stationary policy and π E Il Thus, the probability measure associated with nú (-Is) is feasible solution of Problem PMO By the definitions of V (s) and Qa (s, a), we have
V (s) Ensn; (r(s. a) + +
{Va (s+) |so s. an = =a}}
Earn; (s, a)} < Ea-pz 10t (s, a)}
Suppose V (s) < Ea-ps (Qa a)) Since n²a is feasible solution of Problem PMO
we have
[ IP* (s. du aa
(5)
Thus, by implementing H4, when the state is s, the probability of having Skit S, Vi [L] is larger than a.
Construct new policy मे by
The state is म; (:);
The state is not मे T
14

---

Same problem when 1=2
Ve (
Problen PMO
Share same optimall value
Problem FPO
Combine points and obtain
heorem 1
Theurem
Share same optimal valuee
Share same optimal value Proposition
Proposition
Problem B, (s. L)
Share same oprimal value
Proposition
Problem (a L)
Supperting hyperplane theorem Carihhoddory' theurem
Proposition
Achieves (( with
Optimizing diserete distribution
Linear program
Figure 5: Proof sketch of Theorem 2
Due to and π E Ia. we have that nं E Ia since मe satisfies the chance constraint T Therefore, we have
v*a Eawa; (s, = Eavp; (Qr (s,a)} V (s).
(6)
Note that 6 contradicts with the fact that T. is the optimal stationary policy, which completes the proof.
C Proof of Theorem
To help understand the proof of Theorem 2 we illustrate the proof sketch by Figure
Let L E + be a positive integer and [4] := {I,..., L} be the set of the index. Consider the augmented space A and define an element of S by Cr. = (tu))...,((() For an arbitrarily given Cr., define set of discrete probability measures by
Ua == Taa E 10 Σ (1)
(7)
The set C₁ becomes a sample space with finite samples if it equipped with a discrete probability measure J E Ma,L. where the i-th element (t) denotes the probability of taking decision a(t), i.c., L (a = (i), E [L]. In this way, fa.z and C₁ essentially defines a finite linear combination of Dirac measures. We then define reduced problem of Problem PMO as follows:
L Σ Qa (s, a(s)) (1)
max C.L
i=1
(s, L))
s.t.
IP* Σ
(s. a (1) 2 a- a E Cr,, Vi [4].
Define (s L) (- E Pr (() 11 as the feasible set of Problem
(s. L.) Since the constraint function Σl P' (s, a ( (a, Va,L L. AL + IR is continuous, and its domain Ud x A is compact, we have the feasible set (s, L) of Problem B. (s. L is also compact set. As result, Problem (s, L) optimal solution exists. We have the following proposition for the relationship between Problems PMO and B. L)
Proposition 1. Suppose that Assumptions | and 2 hold. Then, there exists a finite and positive integer L oc such that makes each optimal solution of Problem B (s, L) be an optimal solution of Problem PMO
Proof of Proposition By Assumption | know that compact and Q* a) is continuous on S x A (from the one that r(s. a) is continuous on S x A). Besides, by Assumption 2 we know that IP* (s, a) continuous on S 25). Then, the conclusion of Proposition can be directly
obtained by applying Theorem 1.3 of 26).
15

---

For L = 1, Problem B (s. L) becomes caunce-constrained optimization problem in A:
max Qa (s. a)
aEA
(C.
s.t. (s, a) 2 a.
Let (s) be the optimal solution of Problem (s) For a given number L E N+, let & == (e("),..,ā()))) be an element of [0, _]", defining as a set of violation probabilities, where each a
a For violation probability is threshold of violation probability in Problem (s) when
set Et., we have a corresponding optimal objective value set {J (s). Ja (8), ..),,..., Jauz) (8))
where J (s) is the optimal objective value of Problem (s) when = ā Let Va := (
[0, 11- Ei= Pá. } be set of discrete probability measures that defined on ε7. By determining a violation probability set & and assigning a discrete probability Pa,L to &r. we get a probabilistic decision in which the threshold of violation probability is randomly extracted from EL obeying the discrete probability Va,L. The corresponding expectation of the optimal objective
value is Σx 1=1 Jo (a. Another discrete probability measure optimization problem with chance constraint is formulated as
Σ Ja (s)
max M4 &.
V.. L))
s.t. Σ (1 -1 (1-a
a va. 2 σ.0) E EL, Vi [T..
We have the following proposition regarding the optimal values of Problems Ba L Proposition 2. For every I. E N4 and s E S, the optimal value of Problem (a L) is equal to the one of Problem B. (s. L)
and V Va (s. L.)
Proof of Proposition For an arbitrary L E N+ and an arbitrary s E S, let (pos, Ce) be an optimal solution of Problem (s, L) where č₁ = (a a(t). ..., a(2)). Notice that (ãs Ci)
feasible for Problem B L) and thus we have
p (s, a (a, 2
(8)
Define the optimal value of Problem
(s, L) by Ja L) and thus
Js, I.) Σ 0a (s, a(1) (f).
(9)
1=1
Define set of violation probabilities
ε, = (1) ,..., a(())
(10)
where a06) = TP* (s. a())) Let Va E Va, a probability measure that satisfies Va.z
(i), E [L]. Then, by replacing ā(()) = p. (s, a()) and (a) = (1) into (8) we have
1.
a (a.aa 21 1-a,
(11)
1=1
which implies that (Va.L, Er, is a feasible solution of Problem (., L)
Let (s L) be the optimal
value of Problem V (s. I.) Then, we have
L
(s. L)
Jac (s)va,((i)
L
Σ
Q: (s)) (1)
(From (s) 2 Q (s) ,Ys)
1=1
L).
(12)
16

---

On the other hand, for an arbitrary L N4 and an arbitrary s E S, let (P..L,E)) be an optimal solution of Problem V (s, L) where Er, = (a ...,, a00) ...,) We have
L
Jano (s) Jz L) = Σ
(13)
E - -01-50001 P.. (t) 2 21 1
(14)
For E., define set of decision variables as C2 {ā ... â(z) } where ( is optimal solution of (()) and Q" (s, â()) Ja (s).
Problem C. (s) with a = (9) Note that we have (s, a(1))
Define discrete probability vector Td,I Vd.L. Since it holds that
(s) Σ (1-
(a. 21 a,
(15)
1=1
we have that (ia.L. Ct.
is a feasible solution of Problem Ls)
Therefore,
1
fa L) 2
Σ
Qa (s, a (i)
Σ Jan Pa.L()))
(From (s, ((0) (s), Ad,L Ds.L)
= Td T.).
(16)
By 12 and 16 we have F.0 (s, (s, L), which completes the proof.
Based on Theorem Propositions
and we give the proof of Theorem as follows:
Proof of Theorem We first show that the optimal objective value J (s) of Problem (a(s) satisfies
J*)(s) = (s)
(17)
To attain we will show
Tr S (s), TM 2 (s).
(18)
(19)
For 11
be directly obtained since (s) To L) with L 2 and the feasible region of Problem B (s, L) is a subset of the feasible region of Problem PMO with L = 2, which leads to (s) = J. L)= < (s). It remains to prove 19 We prove 19 in the following steps:
(a) We apply Proposition supporting hyperplane theorem (p. 133 of 27 ), and Caratheodory's theorem [17 to prove that [x L) 2 (s) with L
(b) By Proposition we obtain (s) F2 L) Tz L) Va (s). which is 19
Since (b) is obvious if (a) holds, here focus proving (a).
Define set H(s) [0, 1] IR. Let (ā, (s)) H(ss) be pair of violation probability threshold â and the negative of the corresponding optimal value of Problem C, with = â. Let conv (H(s)) be the convex hull of H()).
Construct new optimization problem as
min
Jh
(H, (s))))
(ā) - J. 1.) (H()))
s.t. Ōh.a S a.
17

---

Let (ag (s), (s) be an optimal solution of Problem (s) We will show that Ih (s) 2
(*)s) for any s E S, and Ja (s) S (s L) with L = 2, which leads to (a).
First, show that R.a (s) (s) for any S. For any I. N+, let 0r. (vd,1, a11) (..
be optimal solution of Problem V (s, L) and we have
Cimean ( (0..) = Σ ② Da. 201
(20)
1
-ean -0 = Σ (-J (i) = -s, L).
(21)
1=1
By the definition of convex hull, we know that
(Omean (0s). - -mean (f1)) E conv (H(s)).
(22)
Due to 20 (Cimean (0L); -J mean (01)) is feasible solution Problem (s) and thus we have
- -hha (s) 2 - -mean (0z)
-T L)
(By (2T)
- L).
(By Proposition
(23)
Note that (23 holds for an arbitrary L E N+. which includes the one that satisfies J. L) = (s) (by Proposition I there exists one L that attains the equality). Therefore, we have
(s) (s). -h (s) S vV)
(24)
Then, show that (s) S (s L) with L 2. To attain this, we first show that (s) is one boundary point of conv (H(())..
Suppose the contrary that (s) -Jh (s)) is interior point. Thus there ists neighborhood of (áh,a (s), -h,a such that is within conv(H(ss)). Suppose that Be ( (s), -hhn(s))) C conv(H(ss), where 8
For any < E, we have that (Ah. (8), - Jh.a (s) - E) E Be (ā (s), - Jh. (5)) (s)) C conv(H(s)). Since - ah (s) 2 1 - a, Ha (s)
(s), -Jh - E(()) is a feasible solution of Problem
However, J (s) < J (s) holds and it contracts with that (a (s). Jh (s) is an optimal solution of Problem
(s) Thus, (s). - Jh (s) is boundary point.
By supporting hyperplane theorem (p. 133 of (27)), there exists a line C that passes through the boundary point (ag,a (s), (s) and contains conv(H(s)) in one of its closed half-spaces. Note that L is one-dimensional linear space. Therefore,
also say ( (s), -J(ss) is within the convex hull of 2N H(s), conv(CN namely, (āp (s), - (R) E conv(C(H(ss)) By Caratheodory's 's theorem we have that (s),
(s). JJ conv(CN)((s)) is within the convex combination of at most two points in LN H, namely, Eug Va.2, 3(a!) a 10, such that
Jh (s)= = - om
(s) - J 0%
ah. = =(( in (1) + ((2) (12) (2).
holds that
1 - (1) U (1) + 2 v2)
=1 =1 1--
Uh.a 2 1
18

---

Thus, (IN(L), amm amm) is feasible solution of Problem
Va L) when L =2 2. Therefore,
we have
2
Jh (s)
Σ
(s)
vnn()) -T L), L=
(25)
om
1=1
From Jn (8) < (s, L) and (s) 2 (s) (by (2 we have J' L) 2 (s). Since
Ja L) = (s, L) by Proposition 2 we have Th L) 2 (s), which leads to Tu L) (s) since (s, L) < (s) also holds. Note that J. (s, L) (s, L), have (7 The rest of Theorem 2 can shown by applying Theorem which completes the proof of Theorem
D Proof of Theorem
As preparation for proving Theorem 3 we first give the following proposition on the optimal solution of Problem [FO
Proposition Let (s) = (a (s), at) (s), w (s)) an optimal solution of Problem FPO
Let
a()) 11-PPM
IP (at) and (22) 1 PP (a(e) (s)). We have
(s) w² (s) a (s) + (1 (1-w"(6 (s)s a(2) (s).
(26)
Proof of Proposition By repeating the proof of Theorem we can show that (s) equals to the optimal value of the tollowing problem:
max aEA
(s, s.l. PM (s. 2 a.
(27)
By Theorem 2 have
V= = w=)))= (s. + +(1 (1 - ws)) Q: (s. (s))
(28)
Based on Proposition
we give the proof of Theorem 3
Proof Theorem If a 0, the optimal solution of Problem V. with L has set ã()) ((2) 0, which leads
Js( = (s).
(29)
Then, by Proposition 2 and Theorem have
Vi( (x) TT 7 J.(s).
(30)
which can be attained by optimal solution of Problem (s) referring to deterministic policy.
E Proof of Theorem
Proof. Define the discounted return of specific trajectory with "unsaae E 10 by
G(Txo) = nunsate (g(s:)).
(31)
Define function G* (s. a) by
C* (s, E
Toc PPr (G(Txx) 8, a0 a)
(32)
19

---

Here, see is an optimal solution of Problem ECRL From the definition of G( in we can
rewrite G* (s, a) in the following way:
(8, a)
Tunsafe E
(T(g(s))) s. a}
To ~ PPa..
tie
Yunsafo Pro (T(g(s:))[s) = =, a, =a}.
(33)
50,00
The continuity of each Pr (L(g S, ag a} is guaranteed by Assumption 2 and the continuity of g(-) (pp. 78-79 of (25)), which naturally leads the continuity of G (s, a). With G* (s, a), probability measure optimization problem is defined as follows:
/ Qi (s, 1, du
max (EM(A)
(s))
s.t. / (s.aa.))
By just repeating the proof of Theorem B equals the of Problem ECRL
we can obtain that the optimal objective value Problem for any S. A flipping-based version of Problem sec
is written by
max (a P w
wQa (s, a())
+ (1 w) Q (s. a(2))
(W
s.t.
wG (s, a(1)) (1 - w) (s, a(2)) S a.
The continuity of G* (s, a) holds and it is bounded within [0, 1]. Thus, Theorem 4 can be proved by following the same process of proving Theorem 2 after replacing P (s. a) by G as.
F
Proof of Theorem 5
Proof. Define a violation probability function Vjoint (0,8) by
so = 8). Vjoint (0.s) To {st $ S. 3i e [T]
(34)
Note that the constraint V Joint (0,s) S equivalent
Pr 8,00 (s: E S, Vi E [7] 8o =s 2
By using Boole's s inequality, we have
T
Wjoint (0,s) <
Prate {st & | so E ES}
i=1
T
Σ
I8
(I(o((s))))
Pr
1=1
EE
(o((s))))
(35)
Define VT
unsafe by
V (0, ; E Po
((((s))))
(36)
Due to 35
V
Vi (,s)) < a, Vs E implies Vjoint (0,s) S a, Vs E S. By replacing s by
Sg. we obtain by setting C(O,s) s) VT umafe (0.s. s) a. Then, VT (0.s) s) is conservative approximation of joint chance constraint (3)
Then, we will show that we can find Tunsafe and T' to make the following equality holds:
H Hunsafe(O V (0, s), 40 E θ SE S.
(37)
20

---

Define V Ui (0,s) by
T Munsate (o((s))))
Vlliitues (0,s) = E
Toc Pro
(38)
Define the error between V Ttinads
(0,s) and Hunsafe (), by
unsafe
gnn CV (T, Yumsafe: 0,s) == Hunsafe (0,s) V
Turanto
(0,s).
(39)
unsafe
Note that 2id (T, Junsafe 0. is positive for any 0 E θ S, Yunsafe (0, 1] and it decreases monotonically as increases. It increases monotonically as "Junsafe increases to
On the other hand, define the error between V
TTrinsate (0,s) and V unsafe (0,s) by
unsafe
(T, Yunsafe; 0,
V unsafe (0,s)
unsafe (0,s).
T Tumood
(40)
The emror (T, Tunsafe 0, decreases monotonically as "Yunsafe increases to 1. It decreases monoton- ically as 7 decreases.
give error between H Hunsofe(O,5) (0,s) and V Vunsate (0, s) as follows:
Ey (T, Tunssfe: S, Hunsafe (0,s) s) V (0, s) EV (I' Tunsafe 0, -0- - (I, Tunsafe: 0, s).
(41)
For any given 0, s. it is able to decrease T and meanwhile increase Tunsafe simultaneously achieve:
increasing 2े (T, Yunsafe: 0,s);
decreasing ēt (T", Yunsafe: S)
Then, there is small enough T and large enough Yunsafe to ensure that (v Tunsafe, 0,s) > 0.
T:iamat Besides, since and S are compact and functions Hunsafe (),s), V (0, and unsafe (0, S) are continuous (yielded by Assumption 2 and Yunsafo such that, if Tunsafe > Lunsafo and T T. (I', Yunsafe, 0, 0, v0 E O,s E S. Then, we have
Hunsafe (,,)) a < Thus, by replacing s by Sk; we obtain by setting C(0, s) ( s) - a if Yunsafe > "unsafe and T T. Then, Hunsafe (0. is conservative approximation of joint chance constrain
Virsate
(0,s) Ev Yunsafee
Tunsafe: 0,s) - 5 7
V (0.s) - S 0.
G Proof of Theorem
As a preparation for proving Theorem we first give the following proposition for the optimal solution of Problem [PFPRL]
Proposition 4. Let Sm (um (1), v (2), 0. ,0!2) E Da be an optimal solution of Problem
PFPRL
Let (1)
pdd (o and ( =1 rd( We have o! O amy= 0! O aa
Proof of Proposition Suppose that 0.!)) aay. Then, )( < Jaas holds. Let @(1) A kmy
Then, Fd (0(1)) 21 21 (0) = () and J(Ø(1)) L > -( We have
2
(d( + ad 0 |n (2)
Fd ( (1) 2 a,
>
i=1
V/m (2) > Σ J( k
Thus. &. (M 0. feasible solution of Problem PFPRL and has a larger objective function value than St which contradicts 5t E Da. Therefore, have ( O g0) Follow the above procedures, we could also prove that (2) + (12)
21

---

Then, we give the proof of Theorem 6 as follows:
Proof of Theorem
For Jj Tn. it can be obtained by repeating the proof of Theorem
Let Sm = (1), (2), _ ,0.2) E Da be an optimal solution of Problem PFPRL
Let 6(1)
=
(=( and ((2) F (0.")) By Theorem and Proposition we have
Jn (1) )))))))))))))))) J Jaco (2) Jam
(42)
Since Já is strictly convex function of on (ar, a) we have
JØ < (1) a0) + (m J &
(at),a(13)
(((3) E (a,
- (1) Jan + (2) * J
Ta:
which completes the proof.
H Proof of Theorem 7
Proof of Theorem Z Since Problem LP is a special case Problem PSPRL Theorem implies the
existence of an optimal solution D, 2s) with no more than two non-zero elements.
Since 0, is the optimal solution of Problem PDPRL with a = ai, Problem LP has the same optimal
value with the following optimization problem:
max (S)E)
Ja vi(()
101
(Ka (Zs))
s.t. (a(i)ā; Sa. Σ
us(i) 1.
i=1
Define another optimization problem as:
max ((.,)
Jă
[0.1]
(Ra)
s.t. ādv: S
[0.1]
Let Fh and D,, be the optimal solution and optimal solution set of Problem Ka
Note that Zs S is extracted according to uniform distribution. By applying Theorem 6 of we have
351
Jh(Zs) S Tk:
Jh(Zs) Th with probability 1 as S -
Then, if we show that Ft Tá. it leads to F:(ss) + Jh with probability 1 as S co.
By Proposition we have
2 J(O (m) Σ Jon Jan (1),
(43)
1=1
where o!!) is one optimal solution of Problem
PDPRL
with a _((1, == 1,2. We further have
v (1) Sa
(44)
22

---

Thus, the probability measure ih defined by
Ve
flip v (1), v/c Hlip {a()) = 1/m (2)
(2))
(45)
a feasible solution of Problem
which implies that
To S Ja
(46)
On the other hand, by applying Theorem 6 have that Problem Ka has flipping-based optimal solution S
ve flpp { (111)
4m (1), De tlpp {a(e)) }
- fm (2)
(47)
It leads to
Fh
Σ Jan mm = Σ ((0.)imm()
(48)
i=1
Σ (m) 2
(49)
which implies that Fo equals an objective value of a feasible solution of Problem PSPRL Thus.
T. z To
(50)
Due to 46 and 50
have Ta Ja which completes the proof.
I Proof of Theorem 8
Proof. First, we show that 0.,, (s, 0x. DN) is feasible solution of Problem CPOS with probability
larger than exp { {-2N (as )²)²(1 Vunsafe) Define two functions by
F(O) == 1 -Es Esa~Ro
Ro a {I(g(s+))}
: Dx0
N Σ [(g(st(()))
Here, simplify the notation by omitting and 0₂ since it claims the same conclusion for all and Og. Besides, define two probability trf and a transformed from Os and og by
trf = (a, - Hunsafe (0c, s)) (1 Yunsafe):
ag = (ā, Hunsafe (0k,s)) (1 Yunsafe
ttf
Note that a. - ā = (a. 0z)(1 11 Tunsafe).
Let Opad be an infeasible solution of Problem CPOS Then, we have
F(Ouad) < 1 0=
(51)
The probability of Öbad being a feasible solution of Problem Pr F(Orad: DN) ž 1 ātr which satisfies that
S-CPOS is
Pr F(O Dx) 2 5 Pr F(Obadi Dx) F()bad) 2 -aa srf
+ ta, ā - F(Ooad)
trf
S Pr { F(Obad, Dx) F(ioad) 2 ag.
str
Pr { (F(Ohad, DN) - F(Obad))
N2 (a str )
Pr
Σ
Y; E(Yi) 2 (a - -oarf)
(52)
1=1
23

---

where Y; is defined by
Y; = (()(s
According to Hoeftding's inequality
23
52) implies
2. (a 2zrf)²
Pr [(Ooeed: Dx) 2 ātr
s exp
exp (-2N(a, - -ās) (1 Tunsafe )
Σ (1 0)2
(53)
Here, 53 means that the probability of Qoad being feasible solution of Problem S-CPOS is smaller than exp 2NN - ā ) } which implics that feasible solution of Problem S
CPOS has a probability larger than 1 - exp - 2N (as- ās) (1 Nunsafe )2 to be a feasible solution The optimal solution 0.., (s, 22. Dx) of Problem S-CPOS ProblemSSCPPS is also included.
of Problem CPOS
When 0 (s. kk. Dx) is feasible for Problem CPOS it is feasible for Problem CLPS By applying
Theorem 5 have that O., (s, 0s, Dv) is also feasible for Problem LPS and thus the policy admitted
by 0.,, (s, 0,. Dv) satisfies the joint chance constraint in Problem CCRL
Conservative approximation by affine chance constraint
Firstly, we will show that an affine chance constraint exists to approximate the joint chance constraint conservatively. The approximate problem also has flipping- policy in the optimal solution set. Since the problem with affine chance constraint can be transformed into the generalized safe exploration (GSE) problem 42.. MASE and shielding methods 2 28 can be applied to solve
which gives the approximate solution of Problem CCRL
Let Hace (0,s) be unsafety function defined by
Hac (0,s) == B -o Pra0
Σ (((
(54)
Notice that Hace (0,s) satisfies
T
Hacc (0,s)=1- = Σ
Po {st ES =}.
Thus, the constraint Hace (0,s) S y is equivalent to
T
Σ
Prese {s, S =8] > - 9,
which is special case of affine chance constraint [3] The theorem of conservative approximation of joint chance constraint based on affine chance constraint as follows:
Theorem 9. Suppose that S is compact and Assumption 2 holds. Define a function Cace s) as follows:
(0, up) Hace (0,s)
(55)
If S a, (acc(O,s,4)) (,), (p) conservative approximation of joint chance constraint
Proof. From the definition of (O.c(O.s) as 54 we have
Hacc 8) E To
(g((s))) 1op =
To Prap (T()s))) =
1=1
T
(I(ss)) Su = =} = Σ
Pr {s; $5 so =s.
(56)
Ta
Po
1=1
1=1
Due to Boole's inequality (p. 14 of [10 we further have
Hace
To (s: $ So = s} 2 Proc. (s. 18. E [T] so = =SE
(57)
3,00
24

---

Thus, by 57 the following holds
( s) S 0 (s, &,ViE So = s E $} - sp,
(58)
Since the left side of (58) is equivalent to
acc 0, s) vp S 0 = Pr 8,30 E 8o = s 2 +
(58) implies that Cace ( s, 8, (p) is conservative approximation of joint chance constraint
MDP with affine chance constraint can be written by
max TEll
(*())
(A)
s.t. Pr oo (8k44 #
[s ES] S a, Vk 0,1,2,...
where the constraint of Problem (s) is conservative approximation of (T). which can be proved following the same flow of Theorem 9
The following theorem for Problem Aa holds:
Theorem 10. A ffipping--aatt based policy exists in the optimal solution set of Problem Aa (S)
Proof. Define a function Hicc (s,a) by
H acc (s, a) Σ 1=1
Pr
(8k+4 E Sa = = = aa}
(59)
Here, Ticc is optimal solution of Problem A.
The continuity of Hice (s, a) is guaranteed by 78-79 of (25). With Hicc (s, a), a probability measure
Assumption 2 and the continuity of g(-) (pp. optimization problem is defined as follows:
/ Qi as
max (AA(
(Bcc((s)
s.t. [ TH (s, dp a.
By just repeating the proof of Theorem I can obtain that the optimal objective value of Problem Back s equuls the one of Problem (s for any s S. flipping- version of Problem acc
written by
wQa (s. a(1) + (1 w)Qa (s, a(2))
(Wace(s)
s.t. wHi (s. a()) (1 w W (s. ax2))
2
Since the continuity of H; (s, a) holds and it is bounded within [0. 1]. Theorem 10 can be proved by following the same process of proving Theorem after replacing P* (s, a) by H a).
K Details of Numerical Example
We present the details of our numerical example. The system dynamics is described by
Fi++1
1
0
xx yk
+
dt
Ugg
0% + Ck
3k++1
0
1
Here, d/ the sampling time, the system state is Ss : the action is ag : [ux vx]" representing the velocity on each direction, and the disturbance vector is d, [& [+] T representing the system disturbance. Both ôt. ÇA are random variables with zero means and standard deviations as 0.6. The initial point is [0 The goal point is 8g [15 15)T. The instantanuous loss function at step & is É(Sa) = ||s sgl1.. For a given time-horizon T, we
[x* yk representing the position of the point,
consider the joint chance constraint Pr (r{(AZ Sy & O₂) A (AT 1 & 0,) } 2 1 a, where the dangerous regions O and Og are defined by O = {s So1 ll2 < 2.5). So1 [7.5 10] T
25

---

A value of 8
Solving optimization problem Opan
Data set
Train neural networks
Deterministic policy
Sampling (1)
(N)
D
iini ... ini
Figure 6: The framework of heuristically obtaining the optimal deterministic policy.
cra
1et ncno
cur
Origeni
256
156 34C
350
330
100
120
21
120
140
304
140
371
Figure 7: Experimental results on Safety Gym (PointGoal2). The flippin-based policy improves the performance of (a) CPO, (b) PCPO, (c) P30, and (d) CUP. Error bars represent la confidence intervals across 5 (CPO, PCOP) or (P30, CUP) different random seeds.
and O2 = (s: - S 2.5], So2 = [10 5] This numerical example investigates whether and when optimal flipping-based policy outperforms optimal deterministic policy under the same violation probability constraint. Therefore, instead of validating the algorithms of optimizing the policy, we implemented a heuristic method to obtain an optimal deterministic policy for each violation probability limit Then, following Algorithm[[] we obtained the optimal flipping-base policy for each a. The framework of heuristically obtaining the optimal deterministic policy summarized in F The heuristic method to obtain an optimal deterministic policy includes two steps. First, for
a given initial state mi we solve the following optimization problem (Orrain):
(2)
T
min
(Sk)
(Otriin)
s.t. Sk+1 = As + df(az + dx), Sp = S
(1)
8k & Oxt l,k: 8k 2 Vk 1,..., T.
Here, A is two-dimensional identity matrix and the extended dangerous regions Ö and Öext are defined by Öcxt = {s ||s So1 ||2 < 2.5 0.63vTdl ). So1 [7.5 10] and Õ
So2 [10 5]T Here, 3 is coefficient to regulate the vi- olation probability. Note that the disturbance obeys Gaussian distribution with zero covariance and the same deviation, and the confidence region for any given probability can be described by circle. Thus, by regulating B, we can ensure the probability confidence of the obtained solution. For a given 3, if we solve problem ( for any s
{s: ||s 5 22 s 2.5 + 0.6.3
1,..., N and extract the first one al of the solution sequence, we can obtain set D = { (s mi
(i)
i=1 Then, we can use D to train a neural network-basee policy with the state as input and the action as output. We obtain neural network-based policies with different violation probability thresholds by varying 3 from 1 to 2.2 with 0.05 as an increment. In the test, we use the inverse distance as a metric for evaluating performance, which is defined by r(sk)= := 1/ (lsa 1 + 0.1). . We tested each neural network with five times simulation sets. each simulation set, one thousand simulations were conducted to calculate the violation probability and the mean reward.
L Details of Safety-Gym Experiment
We used a machine with Intel(R) Core(TM) 17-14700 CPU, 32GB RAM, and NVIDIA 4060 GPU. We present the details our experiments using Safety Gym. Our experimental setup differs slightly from the original Safety Gym in that we deterministically replace the obstacles (i.e., unsafe regions). This modification ensures that the environment solvable and that a viable solution exists. Details of experiments using Safety Gym are as follows. To ensure the generalization of the algorithm,
26

---

Table 1:
for Safety Gym experiments.
NAME
VALUE
NETWORK ARCHITECTURE
664, 64]
ACTIVATION FUNCTION
tanh
LEARNING RATE (CRITIC)
2 X 10
LEARNING RATE (POLICY)
3 x 10 8
LEARNING RATE (PENALTY)
0.0
COMMON PARAMETERS
DISCOUNT FACTOR (REWARD)
0.99
DISCOUNT FACTOR (SAFETY)
0.995
STEPS PER EPOCH
40, 000
NUMBER OF CONJUGATE GRADIENT ITERATIONS
20
NUMBER OF ITERATIONS TO UPDATE THE POLICY
10
NUMBER OF EPOCHS
500
TARGET KL
0.01
BATCH SIZE FOR EACH ITERATION
1024
DAMPING COEFFICIENT
0.1
CRITIC NORM COEFFICIENT STD UPPER BOUND, AND LOWER BOUND
0.001
CPO & PCPO
[0.425, 0. 0.125]
LINEAR LEARNING RATE DECAY
TRUE
Table Test settings for Safety Gym experiments.
NAME
VALUE
DAMPING COEFFICIENT
STEPS PER EPOCH
10, 000
TEST SETTING
NUMBER OF EPOCHS
60
Note: Same training parameters as in training process except for training scale.
used the original SafetyPointGoal2-v0 environment. In the initial stage, we identified parameters with good convergence properties according to specified criteria. Using these parameters, we trained the CPO and PCPO algorithms at 10 cost limit intervals within the range of 1801 continuing until the policy network converged. In the testing experiments, we utilized the saved parameters from these converged networks, loading them into the policy network and sampling data under different seeds. Finally, selected the policy network at appropriate cost limit the base network for the Flipping- "lipping-based policy. When the two base networks output different actions at each step, we chose different actions according to the flip probability, sampling the results under various seed environments to obtain the final results for the Flipping-based policy.
Collision Probability Analysis. We monitored whether the agent encountered collisions under each single-step condition across tests. Subsequently, we computed the collision probabilities for T 3, 10, 30 by assessing the presence of collisions across every T consecutive step. The findings are presented Figure 4 It is important to acknowledge that, despite utilizing a trained and converged stable policy network during the collision testing phase, the collision probability and
cin
I8 ArlO
PR
68 CH
uegi vi Hein
8
25
25
Crogral Moze
Org Mean
70.
120 180
180
180
120 180
180
120 226
150
130
142
Figure 8: Experimental results on Safety Gym (CarGoal22. The flipping-based policy improves the performance of (a) CPO, (b) PCPO, (c) P3O, and (d) CUP. Error bars represent 1a confidence intervals across 3 different random seeds.
27

---

131
10750
Oel
unb-33
Figure 9: Experimental results Safety Gym (PointGoal2). Reward profiles during the training processes of (a) CPO, (b) PCPO, (c) P3O, and (d) CUP. Error bars represent l confidence intervals across 5 (CPO, PCOP) or 3 (P30, CUP) different random seeds.
Jar EPO Cost Best- 1003
PORO Ood Inchee1 129
I33 Cost Lenit
IN Coot trett
F22 Call ne Jm
Splese
Boal Envessment Stops
Toaal Enwrroment Stees
Total bewneement 9069s
10.88
Figure 10: Experimental results on Safety Gym (PointGoal2). Cost profiles during the training processes of (a) CPO, (b) PCPO, (c) P3O, and (d) CUP. Error bars represent lo confidence intervals across 5 (CPO, PCOP) or 3 (P30, CUP) different random seeds.
cost limit curves might exhibit some instability, attributed to the relatively small sample size of 25 trajectories. This variability is likely because the CPO and PCPO algorithms were not primarily designed to minimize collision probabilities. Nonetheless, the curves demonstrate clear positive correlation, affirming the validity and reliability of our experimental outcomes. Our analysis further supports that the flipping-base method effectively enhances reward performance without increasing collision risks.
We also conducted experiments for two more baselines, P3O and CUP on PointGoal2. Figure 7 presents the experimental results, showing that the flipping-based baaing policy can also enhance the performance of P3O and CUP. Additionally, experiments were conducted for the four baselines-CPP PCPO, P3O, and CUP-Uupee under the CarGoal2 environment, with the results summarized in Figure g The findings CarGoal2 are consistent with those in PointGoal2.
Figures 9 and 10 summarize reward and cost profiles of the training processes for each baseline algorithm PointsGoa12. The training results further confirm that combining a performance policy with a safe policy yields flipping-based policy that outperforms the policy trained by the original algorithm, while adhering to the required cost limit.
28

---

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

---

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

---

reproducible, they some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We have provided the code in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips. wttpcccpppbbcc.c hwpppulllciiiiieeeeeeeeppebeeeee guides/ (ooeeeumisssiino ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the numerical example's details in Appendix K and the experimen- tal details in Appendix L
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in the appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: We provide the error bars to show the statistical significance of the experiments, which are given Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the information on the computer resources the beginning of Section 5.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:pppp...aappo.o.oc//////aaaa
Answer: [Yes]
Justification: We conducted the research conforming in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: the final paragraph of the Introduction and the Conclusion, we discuss the societal impacts of our work. Our approach enhances the performance of existing safe reinforcement learning (RI.) algorithms while adhering to the same safety constraints. This advancement promotes the adoption of safe RL in safety-critical decision-makinn
32

---

applications, such as healthcare, economics, and autonomous driving. Besides, we have not yet found the negative societal impacts of the work. The details given in Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper does not include any data or models with a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We conducted experiments using the Safety Gym environment (34] The experimental framework of Safe RL algorithms was facilitated by OmniSafe 24 These details are disclosed at the beginning of Section 5.2) Both Safety Gym and OmniSafe are accessible online, and further information can be found in the aforementioned references.
Guidelines:
The answer NA means that the paper does not existing assets.
33

---

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

---

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


Reviews:
[{"review_id": "f3w3oAmh1x", "reviewer": "Reviewer_g2rG", "summary": "This paper introduces a new policy called the flipping-based policy for Chance-Constrained Markov Decision Processes (CCMDPs), which is useful in safe reinforcement learning. The policy uses a coin flip to choose between two actions, depending on the state. The authors establish a Bellman equation for CCMDPs and show that this flipping-based policy can be part of the optimal solution. To provide a practical algorithm, they also demonstrate how joint chance constraints can be approximated into Expected Cumulative Safety Constraints (ECSCs). The paper presents a framework for integrating this policy into existing safe RL algorithms like CPO and PCPO, showing improvements in performance on Safety Gym benchmarks while maintaining safety constraints.", "questions": "1. What is the cause of the sudden change behavior observed in the experimental results of the \"origin\" group in Figure 2?\n2. Figure 2 serves as a clear and intuitive example. However, in more complex scenarios involving more than two possible safety areas, how is the behavior of the flipping-based policy?\n3. The statement \"Gaussian distribution-based stochastic policies are essentially deterministic policies disturbed by noise for exploration\" may oversimplify the role and impact of Gaussian distribution-based policies. Is there some related work or more detailed explanations? While these policies (e.g. classical PPO and SAC) do indeed introduce stochasticity to facilitate exploration, they also fundamentally alter the optimization process during training. This change is not merely superficial but influences how the policy gradients are computed and how the agent learns to make decisions.", "limitations": "The authors thoroughly discussed the limitations and potential negative societal impacts in the Appendix.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper presents an extensive detailed theoretical analysis, with the entire analytical and proof process vividly illustrated in Figure 1 and Figure 5.\n2. The concept of employing a flipping policy is quite novel, offering a simple yet potent perspective to solve the problem PMO.\n3. This paper delivers a comprehensive framework from theoretical analysis to practical general safety RL algorithms, providing mathematically insightful and practically effective solutions. The experimental section and visualizations are designed to complement the core theorems, ensuring a cohesive understanding.", "weaknesses": "1. The typo in the abstract: expected cumulative safety constraints (ESCSs) should be ECSCs.\n2. The typo in Algorithm 2, line 2: Remove one of the redundant as in the statement.\n3. The assumption regarding the reward and state transition function, as mentioned by the author, is not inherently natural or generalizable across various applications. This is particularly evident in decision-making environments within robotics and autonomous driving, where reward signals are often non-continuous, and state transitions can be abrupt. This limitation significantly constrains the potential impact of the paper.\n4. The paper, as indicated by its title and abstract, aims to approximate the solution to CCRL problems with ECRL. However, the text frequently shifts focus to extending CCRL to ECRL for generalization, which only serves to complicate the narrative and blur the paper's primary objective. It is recommended that the author refocus the discussion on the application of ECRL to CCRL for a clearer and more coherent presentation.\n5. The experimental section exclusively presents the results of the test process, which, although demonstrating positive outcomes, fails to provide any insights into the training process itself. It is crucial for the author to include at least some intermediate results from the training process to validate that the process does not incur significant overheads.\n6. The utilization of a flipping-based policy introduces broader confidence intervals in the results, a concern that may be particularly relevant in safety RL applications.\n7. The authors should ensure that at least two environments are considered in experiments for broader applicability.\n8. This paper should add a related work section to compare and contextualize the current research within the broader field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's valuable feedback and comments. We will answer the questions first and then address the comments about the weakness. All the concerns are addressed in a point-to-point way as follows. \n\n**Sudden change behavior [Question 1].** \nThank you for the interesting question! The sudden change comes from the weakness of the original policy (deterministic policy). For a deterministic policy, if we set a small threshold of violation probability, passing the space between the two red-shaded circles will be infeasible since the violation probability will be larger than the threshold. Therefore, when increasing the threshold of violation probability from a very small value, the mean reward increases relatively slowly since the deterministic policies can only take the sideway in front of the two red-shaded circles. When the threshold of violation probability surpluses the lowest violation probability value of passing the middle space between the two red-shaded circles, passing the middle space will be feasible as this turning point, and the mean reward has a jump here. Note that the flipping-based policy can balance the violation probability by flipping between passing the middle space (high risk) and going the sideway (low risk). With the same mean risk, flipping can further improve the mean reward. **You can regard the flipping as a linear combination to establish a slope for the jumping**. \n\n**More complex scenarios [Question 2].** \nThank you for this valuable comment. Due to our theoretical results (particularly Theorems 2 and 6), even in more complex scenarios involving more than two possible safety areas, **there exists an optimal solution, passing two of them randomly. These chosen \"two\" will be the optimal \"two.\" The random choice will be made only from these chosen \"two,\" depending on the flip probability.** In the PointGoal environment, there are far more than two possible safety areas. the flipping-based policy still improves the performance of CPO and PCPO. To validate the generality of adapting the flipping-based policy to the existing methods, we added the results of two new methods, CUP [Ref-1-1] and P3O [Ref-1-2]. Besides, for all four methods, we added the validations in another environment, CarGoal. The new results are summarized in a new One-Page PDF file attached to the global response. Please kindly check it. \n\n**Statement [Question 3].**\nIndeed, as the reviewer mentioned, the statement on Gaussian distribution-based stochastic policies is improper. Facilitating exploration is one of the benefits of introducing stochasticity. We want to emphasize the part of facilitating exploration and use the improper expressions that oversimplify the stochasticity's role. Thanks for pointing out this improper statement. We apologize for this improper statement and will correct it in the new version. \n\n**Typos [Weakness 1 and 2].** \nThanks for pointing out the typos. We will correct them in the new version and check the whole manuscript to find and correct the other typos.  \n\n**Assumption on reward and state transition function [Weakness 3].**\nThank you for this insightful comment about the gap between the theoretical results and the general applications. The main contribution of this paper is theoretical. Currently, there is a gap in the scenarios with non-smooth functions. In future work, we will extend the results to more practical scenarios. \n\n**CCRL and ECRL [Weakness 4].**\nThanks for your constructive advice on improving the coherence of the manuscript's presentation. When preparing the new version, we would like to follow your suggestion of focusing the discussion on the application of ECRL to CCRL. We will add one short paragraph in the introduction to emphasize this point and provide a short guide to help readers read the rest of the parts. To avoid misunderstanding, several changes will be made in the text, especially the part shifting focus to extending CCRL to ECRL. \n\n**Training process [Weakness 5].**\nAs the reviewer mentioned, it is crucial to provide the training process. In a new One-Page PDF file attached to the global response, we have added the training process profile for each method. We will add these new results in the appendix in the new version.  \n\n**Broader confidence intervals [Weakness 6].**\nThank you for pointing out this critical point. From the experiment results in Omnisafe, the flipping-based policy introduces broader confidence intervals. For the numerical example in Section 5.1, the flipping-based policy does not give broader confidence intervals. The numerical example in Section 5.1 is closer to the optimal solution of the flipping-based policy. Thus, in theory, the flipping-based policy does not increase the size of the confidence interval. However, the practical implementation may have this issue. We think that it is possible to keep the confidence interval as the original one by using smaller variances in Gaussian noises, which may not hurt the performance of the mean reward and cost. The reviewer's observation is very important. We want to reflect this by a remark in the new version.\n\n**More environments [Weakness 7].**\nWe added experimental validation results in a new One-Page PDF file attached to the \"global\" response. Except for the PointGoal environment, every method was validated in the CarGoal environment. The performance in the CarGoal environment is the same as that of the PointGoal environment. \n\n**Related work section [Weakness 8].**\nIndeed, having an independent part of related work can clearly explain how the current research fills the gap. We will extract parts of related work in the introduction and extend it into a related work section in the new version. \n\n\n[Ref-1-1]  Yang, L., et al, Constrained update projection approach to safe policy optimization. In NeurIPS, 2022. \n\n[Ref-1-2]  Zhang, L., et al, Penalized proximal policy optimization for safe reinforcement learning. In IJCAI, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hZFerN0EfS", "reviewer": "Reviewer_GDWH", "summary": "The study proposes a flipping-based policy for managing chance constraints in Markov Decision Processes (MDPs). It introduces a probabilistic approach where actions are selected by flipping a \"distorted coin\", which is helpful in handling uncertainties in safety-critical environments. The authors establish a theoretical framework, including a Bellman equation adaptation for this setup and proofs of optimality under given constraints.", "questions": "1. Could we possibly use neural networks to predict action candidates and flip probabilities?\n2. What is the difference between flip-based policy and reject sampling?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The flipping-based approach is a potentially impactful method for addressing uncertainty in decision-making processes.\n2. The paper provides rigorous theoretical backing for the proposed method, including detailed proofs.", "weaknesses": "1. The algorithm involves multiple layers of optimization and probability adjustments which might be difficult to tune in real-world applications.\n2. The experimental section primarily focuses on simulated environments (Safety Gym benchmarks), and the performance is not significantly improvement compared with CPO and PCPO. There are some new methods that significantly better than CPO and PCPO, e.g., https://arxiv.org/pdf/2405.05890 and https://arxiv.org/pdf/2405.01677", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's helpful comments and insightful questions. The questions and comments raised by the reviewer are addressed point-to-point as follows.\n\n**Neural networks for action and flip probability [Question 1].** \nThank you for this good question! As the reviewer mentioned, it is possible to approximate the optimal flipping-based policy by using a neural network that takes the state as input and outputs the action candidates and flip probability. We can add Gaussian noises to each action candidate to introduce stochasticity and further enhance the exploration. We can also include the added Gaussian noises' covariances into the neural network output. Then, the neural network output becomes the parameters for a Gaussian mixture distribution. It becomes a mixture density network. We intend to train the flipping-based policy with the existing tools in safe reinforcement learning research's infrastructural frameworks, such as OmniSafe. In OmniSafe, the single Gaussian distribution-based stochastic policies can be trained directly without any adaptions. Thus, we have proposed practical algorithms (Section 4.3) to train the flipping-based policy directly using existing algorithms without adjustment. It is worth proposing a new efficient algorithm to train the mixture density network for safe RL. Particularly, with the theory in this paper, the Gaussian mixture distribution only needs two Gaussian kernels to ensure optimality.\n\n**Flipping-based policy and Reject sampling [Question 2].** \nIn flipping-based policy, similar to the general stochastic policy, reject sampling are usually used to generate the input. When using the exact flipping-based policy, the neural network outputs two action candidates and flip probability. Then, the implemented action is chosen from two action candidates by checking a random value generated by the uniform distribution within $[0,1]$. The first candidate is chosen if the generated value surpluses the flip probability value. Otherwise, the second candidate will be chosen. A more complicated case is using a mixture density network to approximate the flipping-based policy. Then, the implemented action will be decided in two ways. The first is to use reject sampling directly for the Gaussian mixture distribution. Or we can sample two samples from two Gaussian distributions and then repeat the process for the case of the exact flipping-based policy. However, sampling from the Gaussian distribution is often achieved by reject sampling. \n\n**Complexity of algorithm [Weakness 1].** \nThanks for pointing out this weakness in our research. The current algorithm's weakness is that it uses multiple layers of optimization and probability adjustments. This limitation of our method (mentioned in the Appendix) may stimulate new work on designing efficient algorithms to obtain the flipping-based policy, in which the neural network outputs two action candidates and the flip probability. The flipping-based policy has a structure that is much simplified compared to the general stochastic policy, but it can still ensure optimality. \n\n**Compare with new methods [Weakness 2].** \nThank you for the useful comments and the wonderful papers. Although the methods presented in the recommended papers are very interesting and useful, we do not find the toolbox in Omnisafe, and the time is limited for us to implement them. Instead, we added CUP [Ref-2-1] and P3O [Ref-2-2] into the comparison. We will first claim our main contributions and then explain why our choices support our main contributions. Although we do not include the recommended methods, we will add the references to the new version of our paper since they are excellent related work of safe RL.\n\nFirst, please let us emphasize that our main contributions include **proving the optimality of flipping-based policy and one practical algorithm to realize it**. The practical algorithm can be CPO, PCPO, or any other safe RL algorithm. How much flipping-based policy can improve the existing algorithm depends also on the original algorithm's performance. To show the generality of our proposed policy and practical algorithm, we add its applications to CUP and P3O. We conducted additional experiment results with CUP and P3O as well. We also added another environment (Cargo) to validate all methods. In any case, using a flipping-based policy can improve the expected reward at the same cost. We would like to ask the reviewer to see the new result in a new One-Page PDF file attached to the global response. We consider it more important to **show the performance of improving existing algorithms by flipping-based policy**. We will add the new figures in the new version.\n\nWe sincerely thank the reviewer for taking the time to review our paper.\n\n[Ref-2-1] Yang, L., et al, Constrained update projection approach to safe policy optimization. In NeurIPS, 2022.\n\n[Ref-2-2]  Zhang, L., et al, Penalized proximal policy optimization for safe reinforcement learning. In IJCAI, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RhZyOpH6RS", "reviewer": "Reviewer_7qnc", "summary": "The paper presents a number of optimality results for flipping-based policies in safe reinforcement learning. It first establishes that flipping-based policies are overall optimal for joint chance constrained MDPs, which represents a significant reduction of the original optimization formulation. Then, acknowledging that even this formulation is practically intractable, it provides a number of relaxations and principled approximations to get to a computationally tractable procedure, and show that one can find flipping-based policies that outperform the best deterministic policies that one can find.", "questions": "1. line 91: are there \\alpha subscripts missing in a couple places here? I don’t think, e.g., \\pi^* has been defined without an \\alpha subscript.\n2. Line 204: I think there’s a conditioning on s_k=s missing in the definition of F^d. Or otherwise I don’t know what the s in the subscript means.\n3. In 4.3, is there a distinction between \\Theta and \\boldsymbol{\\Theta}?\n4. In 5.2, I think you mean to say the reward INCREASED with the flipping policy\n5. Theorem 6 seems far stronger than Theorem 2, and I feel this gap is quite counterintuitive and unacknowledged by the authors, though maybe I’m missing something; if this point could be clarified, I would raise my score. In particular, Theorem 2 says that in the current state, the controller can select from just two (state-dependent) actions (with a state-dependent flipping probability) at the current time point while remaining optimal. But Theorem 6 seems to say that the entire optimal policy can be written as a (fixed, not-state-dependent) mixture of two policies. Perhaps most surprising is the fact that the flipping weight between the two policies is not state-dependent, whereas in Theorem 2 it was allowed to depend on state. Is there an easy way to see why it’s not so surprising? For instance, if the parameterized deterministic policy class is a universal approximating (deterministic) function class, then the PSPRL optimum should essentially be the same as the original CCRL optimum, right (I can see that if PSPRL can implement any policy via \\theta and then arbitrarily mix between them, and by having a continuous mixture of policies that can take the same action at some states and different actions at others, the PSPRL optimum can, e.g., implement a switching policy with a different weight for every state)? But then Theorem 6, if I’m reading it right, says there’s an optimal policy for the original problem with a switching weight that doesn’t depend on state at all! What am I missing?", "limitations": "The experimental results certainly support the rest of the paper, but are somewhat unsurprising, since they basically just show that there can be a mixture of two deterministic policies that beats the best deterministic policy—no surprise there since mixtures of two deterministic policies is a larger class than deterministic policies. And the actual flipping policy found in figure 2 seems a bit troubling to me—in practice would one want a policy that improves upon another safe policy by with some probability taking a marginally unsafe shortcut? For, e.g., a self-driving car, I would probably say no, but maybe this is a weakness of the joint chance constraint formulation, which only conditions on safety, but not the state itself, when demanding joint safety for the next T time steps. I have to agree that, for the problem as formulated, the flipping policy in Figure 2 is indeed better than the deterministic policy. Perhaps a bit more discussion of the problem formulation is merited, as opposed to just referencing other works that use the same formulation.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Safe RL is a very important and challenging problem.\n2. Theorem 2 (and 4 and 6 and 7) is quite interesting and, at least to me, surprising!\n3. The authors take a methodical and principled approach to connect their main theory in section 3 with a practical algorithm that can be used for RL by the end of section 4.", "weaknesses": "1. Theorems 5 and 8 don’t seem very strong or useful since they don’t specify the constraints on \\gamma_unsafe and T (just say they exist), so in particular it may not hold at all for a given user-specified T, and even if it does, it doesn’t provide a way for the user to find a \\gamma_unsafe that makes the approximation conservative for their specified T.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's constructive comments and insightful questions. We feel the reviewer has been patient and given many suggestions to help us improve the quality of our manuscript and questions to guide us in reflecting on our research. Except for your professional advice, your patience and kind heart also mean a lot to us.\n\nWe will answer the questions first and then address the weaknesses and limitations. All responses are given point-to-point. \n\n**Typos [Question 1, 2, 3, 4].**\nThank you for pointing out the typos. We apologize for the typos, which made it difficult for you to read this manuscript. For the typo at line 91, indeed, $\\alpha$ is missing in a couple of places. For the typo at line 204, it should include the conditional part and then take a probability integration on the initial state. We will explain the reason in the response **Theorem 6 [Question 5].** In 4.3, we intend to only use $\\boldsymbol{\\Theta}$ (with boldsymbol). In 5.2, exactly, we mean INCREASED. \nWe will correct the typos in the new version. \n\n**Theorem 6 [Question 5].** \nWe deeply appreciate this valuable comment. The content of this comment is about the core part of our theoretical contribution. We acknowledge this gap between Theorem 6 and Theorem 2 very much. First, let us explain why Theorem 6 and Theorem 2 have different results on the flipping probability. The difference is caused by **a subtle difference between Problem CCRL and Problem PSPRL**. Problem CCRL relies on a revised Bellman equation (Theorem 1) to deliver the optimal policy for every possible state in the state space. The joint chance constraint also needs to be satisfied for every possible state in the pointwise way. In Problem PSPRL, the expectations of reward and constraint also consider the initial state's probability distribution, which is a usual way in the safe RL community. They are not for a specific state. Thus, the obtained flip probability is not state-dependent. Namely, **the subtle difference is the joint chance constraint should be satisfied pointwisely in Problem CCRL while it only needs to be satisfied in a sense of mean value regarding the initial state in Problem PSPRL.** Of course, as the reviewer mentioned, when the PSPRL optimum is the same as the original CCRL optimum, we can conclude that Problem CCRL also has an optimal policy with state-independent switching weight. Then, we have to prove that, for safe RL with joint chance constraint or expected cumulative safety constraints, the policy delivered by the revised Bellman equation (pointwise) and the policy delivered by taking the expectations with the initial state's probability distribution is equivalent. For RL without constraints, they are equivalent. Maybe there is a way to find some conditions, for example, constraining the initial state in a compact set, and then find some equivalent reformations between pointwise constraint and expected constraint on the initial state distribution. \n\n**Theorem 5 and 8 [Weakness 1].**\nThanks for pointing out this weakness. As the reviewer mentioned, Theorems 5 and 8 only show the existence but do not show an explicit way to choose $\\gamma_{\\mathsf{unsafe}}$ for specified $T.$ One important information is that, for specified $T,$ if $\\gamma_{\\mathsf{unsafe}}$ is increased, the approximation for safety can be more conservative. If a conservative safety is desired, we recommend to use a $\\gamma_{\\mathsf{unsafe}}$ that is close to $1$.\n\n**Experimental results [Limitations 1].**\nThanks for the insightful and helpful comments. \nFirst, let us emphasize that our theoretical results show that **the mixture of two deterministic policies can achieve optimality**. We do not need a mixture of three or more deterministic policies. Even if a mixture of three or more deterministic policies is a larger class than a mixture of two deterministic policies, it cannot further improve the expected reward for Problem PMO. \n\nAs the reviewer mentioned, it is necessary to discuss the problem formulation more, especially in the cases where joint chance constraint formulation makes sense. If we understand the reviewer's point correctly, Figure 2 seems troubling because a high threshold of violation probability will be unacceptable for fatal collisions and does not make sense in a self-driving car. That is why we chose the word \"dangerous regions\" instead of \"obstacles.\" It is dangerous but not fatal. Namely, we agree with the point that using joint chance constraints with a relatively high threshold is more suitable for some \"soft\" constraints but not fatal, for example, the risk of meeting traffic jams in the path planning of express delivery services, battery capacity in energy systems with renewable energy. For fatal constraints, safety should almost surely be guaranteed. Then, according to Theorem 3, a deterministic policy should be enough if it can be exactly found. However, for enhancing exploration, computing policy gradients, learning to make decisions, and other reasons, a stochastic policy is still needed for practical applications.   \n\nBesides, Theorem 4 shows that the flipping-based policy can achieve optimality for expected cumulative safety constraints, which is generally used in safe RL. Although Theorem 4 uses the indication function and probability level to show the connection between Problem ECRL and Problem CCRL, the theoretical result can be directly adapted to the general expected cumulative safety constraints, which can extend our theory to more practical scenarios. We should emphasize this by a remark after Theorem 4 in the new version. \n\nThank you again for your constructive comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FSClGeCDgQ", "reviewer": "Reviewer_7QvG", "summary": "The paper is dealing with a chance constrained MDP problem, where the authors constrain the probability of staying in the safe set throughout an episode. The authors show that the original problem can be recast using a flipping-based policy, where the optimal decision to satisfy the constraint is conditioned on the current state (regardless if it is in the safe set or not). The authors proceed to develop a practical algorithm that can be applied to standard RL algorithms such as CPO and demonstrate the utility of their approach. In particular they show that the flipping based policy can outperform significantly a deterministic policy", "questions": "1. Proposition 1 seems like a very strong result and I don’t have access [21]. Could the authors restate Theorem 1.3 from [21] and explain the intuition behind it. For example, how is it possible to cast an infinite dimensional problem to finite dimensions? \n1. What is the intuition behind the possibility of using only two policies and not L as Proposition 1 suggests? \n1. If I understand correctly the problem LP solves a number of PDPRL problems for a number of different safety levels $\\alpha_i$ and then compares it with a predefined safety level $\\alpha$. Then chooses only two values of $\\alpha_i$ for the final flipping policy. Could you explain the intuition behind it. Why does this approach work?\n1. What steps one has to take to adapt say safe PPO to a flipping-based policy?\n1. How did you reformulate the PointGoal problem as a chance constrained problem?", "limitations": "limitations are discussed", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper is rigorous and the maths seem to be correct, however, I have a few questions and clarifications and to be honest I didn’t have time to validate the proofs.\n1. The “secret” of many practical safe RL research is that, in fact, that many algorithms are shown to train well a deterministic policy. The authors demonstrate that there is a possibility to train a truly stochastic policy as well. I find this line of research very valuable.", "weaknesses": "1. Some of the theoretical results would benefit from explanations and intuitions behind them. For instance, why do they work? See questions\n1. I found the discussion of the practical algorithm confusing (but keep in mind time limitation for reviews). For example, the problem LP is not clear. See questions.\n1. The paper is heavy on the theory side, which is not necessarily a weakness, but the experimental side could be improved. For example, I am not sure how, in fact, easy it is to adapt, e.g., safe PPO to a flipping-based policy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's encouraging comments. Your feedback and suggestions are valuable and help us improve the quality of our manuscript. All responses are given in a point-to-point way.\n\n**Proposition 1 [Question 1 and Weakness 1].**\nWe will restate Theorem 1.3 from [21]. We proved a weak version by ourselves and will present it to help the reviewer understand it. \n\nFirst, we restate Theorem 1.3 of [21], which gives the following two results about Problem PMO:\n(a) The optimal solution to Problem PMO exists;\n(b) An optimal solution is a finite linear combination of Dirac measures.\n\nThe result (b) implies a discrete probability measure in the optimal solution set of Problem PMO. It does not give the exact number $L$ of the finite dimension, which can be extremely close to infinite but countable. It does not clarify which points should be given the discrete probability measure. The points and the weights of linear combinations should be optimized. \n\nThen, we explain the intuition behind Theorem 1.3 of [21] by introducing a sketch of how we prove a weak version of it. The existence of the optimal solution can be easily proved using the Prokhorov Theorem. Here, we focus on the weak version of result (b). We prove that Problem $B_\\alpha(s, L)$'s optimal value converges to Problem PMO's optimal value when $L\\rightarrow\\infty.$ Since Problem $B_\\alpha(s, L)$'s feasible set is a subset of Problem PMO for any $L$, Problem $B_\\alpha(s, L)$'s optimal value should be no more than the one of Problem PMO. If Problem $B_\\alpha(s, L)$'s optimal value converges to a value equal to or larger than Problem PMO's optimal value, the proof is done. We can show that there will be a sequence of measures converging to the optimal solution of Problem PMO from inside by using Prokhorov Theorem. All the measures in the sequence are feasible and not on feasible region's boundary. Each measure in the sequence can be approximated by finite measures. Each measure in the sequence has the objective value as the limit of finite measures's objective value. These finite measures are feasible for Problem $B_\\alpha(s, L)$ and should be smaller than Problem $B_\\alpha(s, L)$'s optimal value. Thus, in the sequence, each measure's objective value is smaller than Problem $B_\\alpha(s, L)$'s optimal value. Therefore, the limit, Problem PMO's optimal value, should be smaller than Problem $B_\\alpha(s, L)$'s optimal value, which completes the proof.  \n\n**Why only two policies [Questions 2 and 3, Weakness 2].**\nBased on Theorem 1, Propositions 1 and 2, we proved Theorem 2. **Proposition 2 is the first transition from Proposition 1 to Theorem 2.** Proposition 1 suggests that $L$ policies should be enough. Proposition 2 claims that another problem (Problem $V_\\alpha(s, L)$) that optimizes the discrete probability measure of violation probability's interval has the same optimal objective value as Problem $B_\\alpha(s, L)$ for any $L$. We further can show that Problem $V_\\alpha(s, L)$ has the optimal value whose negative is Problem $H_\\alpha(s)$'s optimal value for any given $L$. **Problem $H_\\alpha(s)$ is a linear program in a two-dimension plane, which is the second transition from Proposition 1 to Theorem 2.** Intuitively, we use some geometric properties (Supporting hyperplane theorem and Caratheodory’s theorem) of the solution Problem $H_\\alpha(s)$ to prove that Problem $V_\\alpha(s, L)$'s optimal value does not increase when $L\\geq 2.$ Which is equivalent to say that Problem $B_\\alpha(s, L)$'s optimal value does not increase when $L\\geq 2.$ Note that Proposition 1 says that $L$ is enough to get optimality for Problem PMO and we show $L\\geq 2$ does not increase the objective value. Thus, two policies are enough. The same process can be repeated to explain Question 3. Problem PSPRL is a special case of Problem PMO, and Problem PFPRL is a special case of Problem $V_\\alpha(s, L)$. Thus, we have Theorem 6 to show that Problem PFPRL and Problem PSPRL share the same optimal value. Then, Problem PSPRL can attain the optimality by two policies. Note that Problem LP's feasible region is a subset of the one of Problem PSPRL. Problem PSPRL considers all possible measures defined on the interval $[0,1]$. Problem LP only considers discrete measures defined on a finite subset of $[0,1]$. Since Problem PSPRL attains the optimality with two policies by Theorem 6, Problem LP also attains the optimality with two policies as its special case. **Since Problem LP only considers finite samples from the interval $[0,1]$ and these finite samples are randomly chosen instead of being optimized, thus we can only show that the optimal value of Problem LP converges to the one of Problem PSPRL with probability 1 when $L\\rightarrow\\infty$**. \n\n**Adapt Safe PPO [Question 4 and Weakness 3].**\nThanks for your question. Adapting safe PPO to a flipping-based policy includes two steps. The first step is to use Algorithm 1 (Page 7 of our manuscript) to train the flipping-based policy using safe PPO in step 2. \nThen, implement the flipping-based policy according to Algorithm 2 (Page 7 of our manuscript). We added P3O [Ref-4-1] into the comparison, which we think is an effective safe PPO method. We also conducted additional experiments in another environment (Cargo) to validate all the methods. In any case, using a flipping-based policy can improve the expected reward under the same expected cost. The new results are summarized in a new One-Page PDF file attached to the global response. Please kindly check the One-Page PDF file. \nWe will add the new results in the new version. \n\n**PointGoal Chance Constrained Problem [Question 5].**\nThe chance constraint for the PointGoal is that the collision probability in the future $T$ steps should be less than $\\alpha$. \n\n[Ref-4-1] Zhang, L., et al, Penalized proximal policy optimization for safe reinforcement learning. In IJCAI, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers and AC,

The authors deeply thank all the reviewers for their insightful comments and constructive suggestions. 

1. We have conducted new experiments based on the reviewers' comments. Additional experimental results are provided in a One-Page PDF file containing new figures. The One-Page PDF file is attached in this global response;
2. We have provided our detailed response to each reviewer with a separate response. 

We hope our responses have addressed all the concerns and questions of the reviewers. 
We are willing to answer any of the reviewers' concerns about our work and sincerely wish the reviewers to value our paper's theoretical and technical contributions.

Best regards,

Authors

Meta-review: This paper considers the problem of Chance-Constrained Markov Decision Processes (CCMDPs). The paper proposes a flipping-based policy that selects the next action by tossing a potentially distorted coin between two action candidates and the probability of the flip and the two action candidates vary depending on the state. The paper shows that a Bellman equation exists for CCMDPs, and using this, the paper shows the existence of a flipping-based policy within the optimal solution sets.  In terms of practical implementation, the paper proposes a framework for adapting constrained policy optimization to train a flipping-based policy. Using this framework, the proposed approach is demonstrated in Safety Gym benchmarks.

We received four expert reviews, with the scores, 5, 5, 7, 7, and the average score is 6.00. The reviewers are positive about the technical contribution and algorithmic novelty.  

Reviewer g2rG and Reviewer GDWH have some questions about the simulation experiments, and I believe that the authors have addressed these questions satisfactorily in the rebuttal. Reviewer 7qnc and Reviewer 7QvG have commended the theoretical contributions. All the reviewers have some suggestions about improving the presentation of the paper. Please update the manuscript according to these comments while preparing the final version.
Decision: Accept (poster)