Flipping-based Policy for Chance-Constrained Markov Decision Processes

Authors: xun  shen
shuo  jiang
kazumune  hashimoto
sebastien  gros
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 04:37:23

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.

Main paper: 
 introduction: 
 In safety-critical decision-making problems, such as healthcare, economics, and autonomous driving, it is fundamentally necessary to consider safety requirements in the operation of physical systems to avoid posing risks to humans or 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 of 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 [1, 15, 32, 49] . The safety constraints have various types of representations (e.g., expected cumulative safety constraint [4, 5, 7] , instantaneous hard constraint [36, 45] , almost surely safe [9, 44] , joint chance constraint [29] [30] [31] ). In many real applications, such as drone trajectory planning [40] and planetary exploration [8] , 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 or with hard constraints is deterministic policy [10, 20, 39] . Introducing stochasticity into the policy can facilitate exploration [11, 38] and fundamentally alter the optimization process during training [16, 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 [12] . In [35] , an algorithm was proposed to compute a stochastic policy that outperforms a deterministic policy under chance constraints, given a known dynamical model. In more general settings for safe reinforcement learning, such as 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-based policy selects the next action by tossing a potentially 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 RL algorithms, such as Constrained Policy Optimization (CPO, [1] ). Thus, we establish a 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-based policy using existing safe RL algorithms. Finally, we show that our proposed flipping-based policy can improve the performance of the existing safe RL algorithms under the same limits of safety constraints on Safety Gym benchmarks. Figure 1 summarizes the main contributions.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 flippingbased 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, we delineate the scope within the initial two paragraphs and subsequently detail the contribution in 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 as long as it is clear that these goals are not attained by the paper. 
preliminaries: markov decision process: 
 A standard Markov decision process (MDP) is defined as a tuple, ⟨S, A, r, T , µ 0 ⟩. 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 Euclidean space, which can be continuous or discrete. Let B(•) be the Borel σ-algebra on a metric space and M (•) be the set of all probability measures defined on the corresponding Borel space. The state transition model T : S × A → M (S) specifies a probability measure of a successor state s + defined on B (S) conditioned on a pair of state and action, (s, a) ∈ S × A, at the previous step. Specifically, we use p(•|s, a) to define a conditional probability density associated with the state transition model T (s, a). Finally, µ 0 is the distribution of the initial state s 0 ∈ S. A stationary policy κ : S → M (A) is a map from states to probability measures on (A, B (A)). We use π (•|s) to define a conditional probability density associated with κ(s), which specifies the stationary policy. Define a trajectory in the infinite horizon by τ ∞ := {s 0 , a 0 , s 1 , a 1 , ..., s k , a k , ...} . An initial state s 0 and a stationary policy π defines a unique probability measure Pr π s0,∞ on the set (S × A) ∞ of the trajectory τ ∞ [22] . The expectation associated with Pr π s0,∞ is defined as E τ∞∼Pr π s 0 ,∞ . Given a policy π ∈ Π, the value function at an initial state s 0 = s is defined by V π (s) := E τ∞∼Pr π s 0 ,∞ {R(τ ∞ ) | s 0 = s} with R(τ ∞ ) := ∞ k=0 γ k r (s k , a k ) , where γ ∈ (0, 1) as the discount factor. Also, the action-value function is defined as Q π (s, a) := r(s, a) + γE τ∞∼Pr π s 0 ,∞ {V π (s + ) | s 0 = s, a 0 = a} .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We give a separate "Limitations" part in Appendix A.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
flipping-based policy with chance constraints: 
 A constrained Markov decision process (CMDP) is an MDP equipped with constraints restricting the set of policies. Let S be the "safe" region of the state specified by a continuous function g : S → R in the following way: S := {s ∈ S : g(s) ≤ 0}. Let T ∈ N + be the episode length. As suggested in [30, 31] , the following joint chance constraints is imposed:EQUATIONwhere α ∈ [0, 1) denotes a safety threshold regarding the probability of the agent going to an unsafe region and [T ] := {1, ..., T } is the index set. The left side of the chance constraint ( 1) is a conditional probability, specifying the probability of having states of future T steps in the safe region when s k 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 a 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 (1) as Chance Constrained Markov decision processes (CCMDPs). It refers to the problem with almost surely safe constraint when α = 0. The set of feasible stationary policies for a CCMDP is defined byEQUATIONholds} . Chance constrained reinforcement learning (CCRL) for a CCMDP is to seek an optimal constrained stationary policy by solvingmax π∈Πα V π (s). (CCRL)Define optimal solution set of Problem CCRL byΠ ⋆ α := {π ∈ Π α : V π (s) = max π∈Πα V π (s)} . Let π ⋆ α ∈ Π ⋆ α be an optimal solution of Problem CCRL. Associated with π ⋆ α , we denote V ⋆ α (s) := V π ⋆ α (s) and Q ⋆ α (s, a) := Q π ⋆ α (s, a)for the optimal value and value-action functions.Define a function P ⋆ (s, a):= Pr π ⋆ α s,∞ {s k+i ∈ S, ∀i ∈ [T ] | s k = s, a k = a} .The continuity of P ⋆ (s, a) is guaranteed under mild conditions giving as Assumptions 1 and 2 (pp. 78-79 of [25] ). Besides, the upper semicontinuity of Q ⋆ α (s, a) is from Assumption 1. Assumption 1. Suppose that A is compact and r(s, a) is continuous1 on S × A. Besides, assume that the state transition model T can be equivalently described by s + = f (s, a, w), where w ∈ W ⊆ R s is a random variable and f (•) is a continuous function on S × A × W. The probability density function is p W (w) .Assumption 1 is natural since it only requires that the reward function is continuous and the state transition can be specified by a 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 ∈ S and a ∈ A, we haveEQUATION)Assumptions 1 and 2 are essentially assuming the regularities of g and T (s, a), which is not a strong assumption. With P ⋆ (s, a), we define a probability measure optimization problem (PMO) bymax µ∈M (A) A Q ⋆ α (s, a) dµ s.t. A P ⋆ (s, a) dµ ≥ 1 -α. (PMO)We have the following theorem for the optimal constrained stationary policy π ⋆ α of Problem CCRL: Theorem 1. The optimal value of Problem PMO equals V ⋆ α (s) for any s ∈ S. The probability measure µ ⋆ α associated with π ⋆ α (•|s) is an optimal solution of Problem PMO for any s ∈ S.The proof is based on the following idea. After showing that V ⋆ α (s) is not larger than the optimal value of Problem PMO, 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 1, we know that the solution of Problem PMO gives the probability measure associated with the action's probability distribution π ⋆ α (•|s) given by the optimal stationary policy, which is Bellman equation for CCMDPs. Problem PMO is difficult to solve since we must optimize a probability measure, an infinitedimensional variable. We further reduce Problem PMO into the following flipping-based policy optimization problem (FPO):EQUATIONs.t. wP ⋆ s, a (1) + (1 -w)P ⋆ s, a (2) ≥ 1 -α.(FPO)We have the following theorem for Problem FPO: Theorem 2. Suppose that Assumptions 1 and 2 hold. The optimal objective value of Problem FPO equals to V ⋆ α (s) for every s ∈ S. Let the solution of Problem FPO be z ⋆ α (s) := a ⋆(1) (s), a ⋆ (2) (s), w ⋆ (s) . Define a stationary policy πw α (•|s) that gives a discrete binary distribution for each s, taking a = a ⋆(1) (s) with probability w ⋆ (s) and a = a ⋆ (2) (s) with probability 1 -w ⋆ (s). The policy πw α (•|s) is an optimal stationary policy with chance constraint, namely, πwα (•|s) ∈ Π ⋆ α .The proof is based on the following idea. We first show that Problem PMO has an optimal solution that is a discrete probability measure (Proposition 1 in Appendix C). We then apply the supporting hyperplane theorem and Caratheodory's theorem to show further that the discrete probability measure can be focused on two points. See Appendix C for the proof details. Theorem 2 simplifies the optimizing of the policy in a probability measure space for each s into an optimization problem in finite-dimensional 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-based policy since it is similar to the process of random coin flipping, taking a = a ⋆ (1) (s) with probability w ⋆ (s) and a = a ⋆(2) (s) with probability 1-w ⋆ (s). We summarize one condition that the deterministic policy is enough for the optimality of Problem CCRL in Theorem 3. See Appendix D for the proof. Theorem 3. Suppose that Assumptions 1 and 2 hold. There exists a deterministic policy that achieves the optimality of Problem CCRL when α = 0.some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
practical implementation of flipping-based policy: 
 This section introduces the practical implementation of flipping-based policy. Obtaining the optimal flipping-based policy for CCMDP is 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 is resolved by conservative approximation. The common conservative approximation for joint chance constraint is the linear combination of instantaneous 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 [1] to find a conservative approximation of Problem CCRL's optimal flipping-based policy. We show the optimal and finite-sample safety of the flipping-based policy for MDP with the expected cumulative safety constraint.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 flippingbased 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-based policy to MDP with a single expected cumulative safety constraint. The problem is formulated byEQUATIONwhere γ unsafe ∈ (0, 1) is the discount factor and I (z) defines an indicator function with I (z) = 1 if z > 0 and I (z) = 0 otherwise. The following theorem for Problem ECRL holds: Theorem 4. A flipping-based 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-based policy can also be extended to the safety constraint function with an additive structure in a finite horizon, written byT i=1 Pr π θ s,∞ {s i ∈ S | s 0 = s}.This safety constraint refers to affine chance constraints [13] . We summarize the extension to problems with affine chance constraints in Appendix J. Remark 1. Theorem 4 can be extended to a more general case where the cumulative safety constraint is not limited to an indicator function but can be any Lipschitz continuous function, thereby broadening the applicability of our theory to more practical scenarios.We resolve the curse of dimensionality by searching for the optimal policy within a set Π θ ⊆ Π of parametrized policies with parameters θ ∈ Θ ⊂ R n θ , for example, neural networks of a fixed architecture. Here, we use π θ to specify a policy parametrized by θ. If the assumption of the existence of the universal approximator holds, we can approximate the optimal flipping-based policy by using a neural network with state s as input and z ⋆ α (s) as output. Another representation of the flipping-based policy is using Gaussian mixture distribution, written by π(•|s) = w(s)N ā(1) (s), Σ (1) (s) + (1 - w(s))N ā(2) (s), Σ (2) (s) . The output is ā(1) (s), ā(2) (s), w(s), Σ (1) (s), and Σ (2) (s). If we have w(s) = w ⋆ (s), ā(1) (s) = a ⋆(1) (s), and ā(2) (s) = a ⋆ (2) (s) for every s, the flipping-based policy using Gaussian mixture distribution can approximate the flipping-based policy with binary distribution when the covariances Σ (1) (s) and Σ (2) (s) 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 a ⋆(1) (s) and a ⋆ (2) (s) during implementation. Rewrite the joint chance constraint (1) with s 0 = s for parametrized policy byEQUATIONIn local parametrized policy search (LPS) for CCMDPs, θ is updated by solving max Here, D(•) denotes a similarity metric between two policies, such as Kullback-Leibler (KL) divergence, and δ > 0 is a step size. The updated policy π θ k+1 is parametrized by the solution θ k+1 of Problem LPS. The updating process considers the joint chance constraint. Problem LPS is challenging 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 RL algorithm to obtain a conservatively approximate solution of Problem CCRL. First, we introduce the formal definition of the conservative approximation:EQUATIONLet H unsafe (θ, s):= E τ∞∼Pr π θ s 0 ,∞ ∞ i=1 γ i unsafe I (g(s i)) |s 0 = s be a 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 a function C unsafe (θ, s) by C unsafe (θ, s) := H unsafe (θ, s) -α. There exist large enough γ unsafe and small enough T such that C unsafe (θ, s) ≤ 0 is a conservative approximation of (3).The proof of Theorem 5 is summarized in Appendix F. We formulate a conservative approximation of Problem LPS (CLPS) as follows:max θ∈Θ V π θ (s) s.t. H unsafe (θ, s) ≤ α, D(π θ ∥π θ k ) ≤ δ. (CLPS)By Theorem 5, the optimal solution of Problem CLPS is a feasible solution of Problem LPS and thus the corresponding parametric policy is within Π ⋆ α . We have a remark on Theorem 5 as follows: Remark 2. By the same procedure of proving Theorem 5, we can show that Problem ECRL is a conservative approximation of Problem CCRL.Then, we present a 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-based stochastic policies. We take the parameterized deterministic policies as an example, which is specified by π d θ . The parameter θ is within a compact set Θ. We write the reinforcement learning of parameterized deterministic policy (PDPRL) for CCMDPs bymax θ∈Θ J(θ) := E τ∞∼π d θ {R(τ ∞ )} s.t. F d (θ) ≥ 1 -α. (PDPRL)Here, the constraint function F d (θ) is defined byF d (θ) := E s0∼µ0 Pr π d θ s,∞ {s i ∈ S, ∀i ∈ [T ]|s 0 } .Let J * α and Θ * α 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 s 0 instead of considering the problem for each s 0 . The reason is that the provided tools in OmniSafe, for example, CPO [1] 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 B(Θ) be the Borel σ-algebra (σ-field) on Θ ⊂ R n θ with Euclidean distance. Let ν ∈ M (Θ) be a probability measure on (Θ, B(Θ)). With the above notation, associated with Problem PDPRL, a reinforcement learning of parameterized stochastic policy (PSPRL) is formulated as:max ν∈M (Θ) Θ J(θ)dν s.t. Θ F d (θ) dν ≥ 1 -α. (PSPRL)Let M α (Θ) := µ ∈ M (Θ) : Θ F d (θ)dν ≥ 1 -α be the feasible set of Problem PSPRL. The optimal objective value and the optimal solution set of Problem PSPRL are J * α := max ν∈Mα(Θ) Θ J(θ)dν and A α := µ ∈ M α (Θ) : Θ J(θ)dν = J * α . A probability measure ν * α ∈ A α is called an optimal probability measure for Problem PSPRL. Define (1) , θ (2) be a variable in the set Z m := V m × Θ 2 . Consider an optimization problem on ζ m , reinforcement learning of parameterized flipping-based policy (PFPRL), written asV m := ν m ∈ [0, 1] 2 : 2 i=1 ν m (i) = 1 . Let ζ m := ν m (1), ν m (2), θmax ζm∈Zm 2 i=1 J(θ (i) )ν m (i) s.t. 2 i=1 ν m (i)F d (θ (i) ) ≥ 1 -α. (PFPRL) Define Z m,α := ζ m ∈ Z m : 2 i=1 F d (θ (i))ν m (i) ≥ 1 -α as the feasible set of Problem PFPRL. In addition, define the optimal objective value and optimal solution set of Problem PFPRL by J w α := min2 i=1 J(θ (i) )ν m (i) : ζ m ∈ Z m,α and D α := ζ m ∈ Z m,α : 2 i=1 J(θ (i) )ν m (i) = J wα , respectively. We have Theorem 6 for parameterized flipping-based policy. Theorem 6. The optimal values of Problems PFPRL and PSPRL are equal, J * α = J w α . If J * α is a strictly convex function of α on an interval (α, α), then, ∀α ∈ (α, α), J * α > J * α holds.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. In Problem CCRL, the optimal policy for each state is derived based on a revised Bellman equation, ensuring that the joint chance constraint is satisfied pointwise for every state. On the other hand, Problem PSPRL focuses on 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 state-dependent nature of the constraint to disappear.There is no existing tool to solve Problem PFPRL and we can only apply them to solve Problem PDPRL for any given α.Let Z S = {α i } S i=1 , αi ∈ [0, 1], ∀i ∈ [S]be a set of probability levels. For each αi , define θi be the optimal solution of Problem PDPRL with α = αi . Consider the linear program (LP):max νs(1),...,νs(S)∈[0,1] S S i=1 J( θi )ν s (i) s.t. S i=1 ν s (i)F d ( θi ) ≥ 1 -α, S i=1 ν s (i) = 1.(LP)Define the optimal objective value and optimal solution set D α (Z S ) of Problem LP by J k α (Z S ) and D α (Z S ), respectively. The optimal flipping-based policy is characterized byν s (j * 1 ), ν s (j * 2 ), θj * 1 , θj * 2, where j * 1 and j * 2 are the index for the non-zero elements of the optimal solution of linear program LP The following theorem holds for J k α (Z S ) and D α (Z S ). Theorem 7. There exists an optimal solution in D α (Z S ) such that the number of non-zero elements does not exceed two. Besides, if αi is extracted independently and identically (uniform distribution), as S → ∞, we have J k α (Z S ) → J * α with probability 1.See Appendix H for the proof. Theorem 6 shows that there exists an optimal solution to Problem PSPRL that is a linear combination of two deterministic policies. Theorem 7 clarifies that we could obtain an approximate flipping-based policy to Problem PSPRL by 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 distribution-based 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 a general algorithm for approximately training the flipping-based policy based on the existing safe RL algorithms in Algorithm 1. With ν s (j * 1 ), ν s (j * 2 ), θj * 1 , θj *, we implement the flipping-based policy by Algorithm 2. In the practical implementation, the weight is constant instead of a function of the initial state since Problems PDPRL and PSPRL consider the expectation of the initial state. Besides, αi in (1) is replaced by cost limit when using CPO or PCPO to obtain a conservative approximation of (3).The update by solving Problem CLPS is difficult to implement practically since the evaluation of the constraint function H unsafe (θ, s) ≤ α is necessary to clarify whether a policy π is feasible, which is challenging in high-dimensional cases. Here, we apply the surrogate functions proposed in [1] to replace the objective and constraints of Problem CLPS. With a probability α s ∈ [0, α), the CPO-based approximation of Problem CLPS (CPOS) is written bymax θ∈Θ E s ini ∼π θ k ,a∼π θ {r(s ini , a)} s.t. H unsafe (θ k , s) + 1 1 -γ unsafe E a∼π θ s ini ∼π θ k I(g(s + )) ≤ α s , D(π θ ∥π θ k ) ≤ δ.(CPOS)Note that the optimal solution θ k+1 of Problem CPOS may differ from the one of Problem CLPS. Proposition 2 of [1] gives the upper bound of CPO update constraint violation. The upper bound depends on the values of the step size δ, probability level α s , discount factor γ unsafe , and the maximal expected risk defined by ηθ k+1 αs := max s ini ∈S E a∼π θ k+1 {I(g(s + ))} .The upper bound can be written byH unsafe (θ k+1 , s) ≤ α s + √ 2δγ unsafe η θ k+1 αs (1-γ unsafe ) 2 .By choosing sufficiently small step size δ, discount factor γ unsafe , and probability level α s , it is able to ensure that H unsafe (θ k+1 , s) ≤ α.In practical implementation, the exact value of E s∼π θ k ,a∼π θ {I(g(s + ))} is unavailable and samples of s ini ∼ π θ k and a ∼ π θ are used to approximate the CPO update. The data set is defined byD N := (s (i) , a (i) , s +,(i) ) N i=1, where N ∈ N + is the sample number and s +,(i) is a sample of successor with previous state s (i) and action a (i) . Instead of directly solving Problem CPOS, the following sample average approximate of Problem CPOS (S-CPOS) is solved:max θ∈Θ 1 N N i=1 r(s (i) ini , a (i) ) s.t. H loc unsafe (θ k , s, γ unsafe , D N ) ≤ αs , D(π θ ∥π θ k ) ≤ δ. (S-CPOS)Here,H loc unsafe (θ k , s, γ unsafe , D N ) := H unsafe (θ k , s) + 1 (1-γ unsafe )N N i=1 I(g(s +,(i) )) and αs ∈ [0, α s )is a probability level. The extraction of sample set D N is random, and thus the optimal solution θαs (s, θ k , D N ) of Problem S-CPOS is a random variable due to the independence on the sample set D N . We need to investigate the probability that θαs (s, θ k , D N ) admits a feasible policy for Problem CCRL. We have Theorem 8 for the safety with finite sample number. See Appendix I for the proof. Theorem 8. Suppose that the step size δ > 0 and α s ∈ [0, α) are adjusted to ensure that H unsafe (θ k+1 , s) ≤ α. There exist T and γ unsafe such that, if αs ∈ [0, α s ), γ unsafe > γ unsafe , and T < T , such that θαs (s, θ k , D N ) admits a feasible policy for Problem CCRL with a probability larger than1 -exp -2N (α s -αs ) 2 (1 -γ unsafe ) 2 .Note that Theorems 5 and 8 only show the existence of the parameters for safety but do not show an explicit way to choose γ unsafe for specified T . If a conservative safety is desired for practical applications, we recommend using a γ unsafe close to 1. 
numerical example: 
 We conduct a numerical example to illustrate how the flipping-based policy outperforms the deterministic 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 a required value. The uncertainties come from the disturbances to the implemented actions. The metric for evaluating the performance is the cumulative inverse distance to 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 to a sideway in front of the dangerous regions since crossing the middle space violates the violation probability constraint. Figure 2 (b) shows trajectories by flipping-based 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 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 2 has a convex shape until 22%. Theorem 6 points out that the strict convexity implies the better reward performance of the flipping-based policy.We conduct experiments on Safety Gym [34] , where an agent must maximize the expected cumulative reward under a 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] , a 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, we only present the experimental results of the test processes for CPO and PCPO on PointGoal2. The details of the experimental setup, all four algorithms' training process results on PointGoal2 and their test process results on CarGoal2 are provided in Appendix L.Baselines and metrics. We implement the practical algorithms presented in Section 4.3 to obtain the flipping-based policy. We modified Algorithm 1 to train the flipping-based policy based on CPO and PCPO. In Algorithm 1, the sample set Z S consists of samples of violation probabilities. Since CPO and PCPO consider the expected cumulative safety constraints, the sample set Z S includes the samples of cost limits of the expected cumulative safety constraints. Instead of using the training 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 a flipping-based policy without any other changes. We employ the expected cumulative reward and the expected cumulative safety as metrics to evaluate the flipping-based policy and the aforementioned baselines.We execute CPO and PCPO with five random seeds and compute the means and confidence intervals.Results. The experimental results are summarized in Figure 3 . As shown in the figure, for CPO and PCPO, the expected reward increases as 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 at intervals without convexity, the flipping-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 performance. Essentially, the flipping mechanism is a linear combination of a performance policy (risky but highperforming) and a safety policy (safe but lower-performing) designed to increase the reward while maintaining the required level of risk. One concern regarding the results in Figure 3 is that the flipping-based policy introduces broader confidence intervals. In theory, however, the flipping-based policy does not increase the size of the confidence intervals. This is demonstrated in the numerical example in Section 5.1, where the policy achieves solutions closer to the optimal ones as outlined in Theorem 2. 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.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 flipping-based policy outperforms the deterministic policy under joint chance constraint. With the same expected cumulative safety, a larger T introduces a larger violation probability, which validates Theorem 5.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusions: 
 In this article, we first introduce the Bellman equation for CCMDP and prove that a flipping-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 constraints 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 RL algorithms. Finally, we demonstrated that a flipping-based policy can improve the performance of safe RL algorithms under the same safety constraints limits on the Safety Gym benchmark. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper does not include any data or models with a high risk for misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors 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 to 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 was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A Limitations and Potential Negative Societal ImpactsLimitations. The practical algorithm (Algorithm 1) for training the flipping-based policy is adaptable to any safe RL algorithms. However, it has the following limitations. First, there is a gap in the scenarios with non-smooth functions. The results should be extended to more practical scenarios with non-smooth functions. Second, training a couple of 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 in the practical algorithm is not state-dependent. Although it achieves the optimality of the parameterized flipping-based policy when considering the expectation of the initial state, optimality by Theorem 2 has not yet been achieved. Future work should focus on designing a practical algorithm to obtain the flipping-based policy, for example, training a neural network to take action candidates and the probability of flip as output and the state as input. If we could develop an efficient algorithm to 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 is crucial to remain vigilant about the ethical implications and potential risks associated with their application.The proof sketch is summarized as follows:(a) Show that V ⋆ α (s) is not larger than the optimal value of Problem PMO; (b) Assume that V ⋆ α (s) is 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 V ⋆ α (s) is the optimal value function, V ⋆ α (s) cannot be smaller than the optimal value of Problem PMO and only equality holds. From the equality, we prove Theorem 1.Following the above sketch, the proof of Theorem 1 is as follows:Proof of Theorem 1. For a state s, let µ * α ∈ M (A) be the solution of Problem PMO and the associated probability density function is p * α (•). Note that π ⋆ α is a stationary policy and π ⋆ α ∈ Π α . Thus, the probability measure associated with π ⋆ α (•|s) is a feasible solution of Problem PMO. By the definitions of V ⋆ α (s) and Q ⋆ α (s, a), we haveEQUATIONThus, by implementing µ * α when the state is s, the probability of having s k+i ∈ S, ∀i ∈ [L] is larger than 1 -α.α by• The state is s:π * α = p * α (•); • The state is not s: π * α = π ⋆ α .Share same optimal value Theorem 2Optimal value Theorem 1Share same optimal value Proposition 1Share same optimal value Proposition 2• Proposition 1• Supporting hyperplane theorem • Caratheodory's theoremShare same optimal value Proposition 2Combine these two points and obtain Due to (5) and π ⋆ α ∈ Π α , we have that π * α ∈ Π α since π * α satisfies the chance constraint (1). Therefore, we haveEQUATIONNote that (6) contradicts with the fact that π ⋆ α is the optimal stationary policy, which completes the proof.To help understand the proof of Theorem 2, we illustrate the proof sketch by Figure 5 .Let L ∈ N + be a positive integer and [L] := {1, ..., L} be the set of the index. Consider the augmented space A L and define an element of S L by C L = a (1) , ..., a (L) . For an arbitrarily given C L , we define a set of discrete probability measures byEQUATIONThe set C L becomes a sample space with finite samples if it is equipped with a discrete probability measure µ d,L ∈ U d,L , where the i-th element µ d,L (i) denotes the probability of taking decision a (i) , i.e., µ d,L (a(i) ) = µ d,L (i), i ∈ [L].In this way, µ d,L and C L essentially defines a finite linear combination of Dirac measures. We then define a reduced problem of Problem PMO as follows: s, L ) is also a compact set. As a result, Problem B α (s, L)'s optimal solution exists. We have the following proposition for the relationship between Problems PMO and B α (s, L): Proposition 1. Suppose that Assumptions 1 and 2 hold. Then, there exists a finite and positive integer L < ∞ such that makes each optimal solution of Problem B α (s, L) be an optimal solution of Problem PMO.max µ d,L ∈U d,L ,C L ∈A L L i=1 Q ⋆ α s, a (i) µ d,L (i) s.t. L i=1 P ⋆ (s, a (i) )µ d,L (i) ≥ 1 -α, a (i) ∈ C L , ∀i ∈ [L]. ( B α (s, L)) Define U α (s, L) := (µ d,L , C L ) : L i=1 P ⋆ (s, a (i) )µ d,L (i) ≥ 1 -α as the feasible set of Problem B α (s, L). Since the constraint function L i=1 P ⋆ (s, a (i) )µ d,L (i) : U d,L × A L → R is continuous, and its domain U d,L × A L is compact, we have the feasible set U α (s, L) of Problem B α (Proof of Proposition 1. By Assumption 1, We know that A is compact and Q ⋆ (s, a) is continuous on S × A (from the one that r(s, a) is continuous on S × A). Besides, by Assumption 2, we know that P ⋆ (s, a) is continuous on S × A [25] . Then, the conclusion of Proposition 1 can be directly obtained by applying Theorem 1.3 of [26] .For L = 1, Problem B α (s, L) becomes a chance-constrained optimization problem in A:max a∈A Q ⋆ α (s, a) s.t. P ⋆ (s, a) ≥ 1 -α. (C α (s))Let J ⋆ α (s) be the optimal solution of Problem C α (s). For a given number L ∈ N + , let E L := α(1) , ..., α(L) be an element of [0, 1] L , defining as a set of violation probabilities, where each α(i) is a threshold of violation probability in Problem C α (s) when α = α(i) . For a violation probability set E L , we have a corresponding optimal objective value set {J ⋆ α(1) (s), ..., J ⋆ α(i) (s), ..., J ⋆ α(L) (s)}, where J ⋆ α(i) (s) is the optimal objective value of Problem C α (s) when α = α(i) . Let V d,L := {ν d,L ∈ [0, 1] L : L i=1 ν d,L (i) = 1} be a set of discrete probability measures that defined on E L . By determining a violation probability set E L and assigning a discrete probability ν d,L to E L , we get a probabilistic decision in which the threshold of violation probability is randomly extracted from E L obeying the discrete probability ν d,L . The corresponding expectation of the optimal objective value isL i=1 J ⋆ α(i) ν d,L (i).Another discrete probability measure optimization problem with chance constraint is formulated asmax ν d,L ∈V d,L ,E L ∈[0,1] L L i=1 J ⋆ α(i) (s)ν d,L (i) s.t. L i=1 (1 -α(i) )ν d,L (i) ≥ 1 -α, α(i) ∈ E L , ∀i ∈ [L]. ( V α (s, L))We have the following proposition regarding the optimal values of Problems B α (s, L) and V α (s, L). Proposition 2. For every L ∈ N + and s ∈ S, the optimal value of Problem V α (s, L) is equal to the one of Problem B α (s, L).Proof of Proposition 2. For an arbitrary L ∈ N + and an arbitrary s ∈ S, let μd,L , CL be an optimal solution of Problem B α (s, L), where CL = a (1) , ..., a (i) , ..., a (L) . Notice that μd,L , CL is feasible for Problem B α (s, L) and thus we haveEQUATIONDefine the optimal value of Problem B α (s, L) by J α (s, L) and thusEQUATIONDefine a set of violation probabilities asEQUATIONwhereEQUATIONwhich implies that (ν d,L , E L ) is a feasible solution of Problem V α (s, L). Let J v α (s, L) be the optimal value of Problem V α (s, L). Then, we haveEQUATIONOn the other hand, for an arbitrary L ∈ N + and an arbitrary s ∈ S, let νd,L , E L be an optimal solution of Problem V α (s, L), where E L = ᾱ(1) , ..., ᾱ(i) , ..., ᾱ(L) . We haveEQUATIONEQUATIONFor E L , define a set of decision variables as C L = {â (1) , ..., â(L) }, where â(i) is an optimal solution of Problem C α (s) with α = ᾱ(i) . Note that we have P ⋆ (s, â(i) ) ≥ 1 -ᾱ(i) and Q ⋆ (s, â(i) ) = J ⋆ ᾱ(i) (s). Define a discrete probability vector μd,L = νd,L . Since it holds thatEQUATIONwe have that μd,L , C L is a feasible solution of Problem B α (s, L). Therefore,EQUATIONBy ( 12) and ( 16), we have J b α (s, L) = J v α (s, L), which completes the proof.Based on Theorem 1, Propositions 1 and 2, we give the proof of Theorem 2 as follows:Proof of Theorem 2. We first show that the optimal objective value J w α (s) of Problem W α (s) satisfiesEQUATIONTo attain (17), we will showEQUATIONEQUATIONFor (18) , it can be directly obtained since J w α (s) = J b α (s, 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 toJ w α (s) = J b α (s, L) ≤ V ⋆ α (s).It remains to prove (19) . We prove (19) in the following steps:(a) We apply Proposition 1, supporting hyperplane theorem (p. 133 of [27] ), and Caratheodory's theorem [17] to prove that J v α (s, L) ≥ V ⋆ α (s) with L = 2;(b) By Proposition 2, we obtainJ w α (s) = J b α (s, L) = J v α (s, L) ≥ V ⋆ α (s), which is (19).Since (b) is obvious if (a) holds, we here focus on proving (a).Define a set H(s) := [0, 1] × R. Let (α, -J * α(s)) ∈ H(s) be a pair of violation probability threshold α and the negative of the corresponding optimal value of Problem C α (s) with α = α. Let conv (H(s)) be the convex hull of H(s).min ( αh,α ,-J h )∈conv(H(s)) -J h (H α (s)) s.t. αh,α ≤ α.Let α⋄ h,α (s), -J ⋄ h,α (s) be an optimal solution of Problem H α (s). We will show that J ⋄ h,α (s) ≥ V ⋆ (s) for any s ∈ S, and J ⋄ h,α (s) ≤ J v α (s, L) with L = 2, which leads to (a).First, we show that J ⋄ h,α (s) ≥ V ⋆ (s) for any s ∈ S. For any L ∈ N + , let θL := νd,L , ᾱ(1) , ..., ᾱ(L) be an optimal solution of Problem V α (s, L) and we haveEQUATIONEQUATIONBy the definition of convex hull, we know thatEQUATIONDue to (20) , α mean ( θL ), -J ⋆ mean ( θL ) is a feasible solution of Problem H α (s) and thus we haveEQUATION)Note that (23) holds for an arbitrary L ∈ N + , which includes the one that satisfies J b α (s, L) = V ⋆ α (s) (by Proposition 1, there exists one L that attains the equality). Therefore, we haveEQUATIONThen, we show thatJ ⋄ h,α (s) ≤ J v α (s, L) with L = 2.To attain this, we first show that ( α⋄ h,α (s), -J ⋄ h,α (s)) is one boundary point of conv (H(s)). Suppose on the contrary that (α ⋄ h,α (s), -J ⋄ h,α (s)) is an interior point. Thus there exists a neighborhood of (α ⋄ h,α (s), -J ⋄ h,α (s)) such that is within conv(H(s)). Suppose that B ε (α ⋄ h,α (s), -J ⋄ h,α (s)) ⊂ conv(H(s)), where ε > 0. For any ε < ε, we have thatEQUATIONs) holds and it contracts with that α⋄ h,α (s), -J ⋄ h,α (s) is an optimal solution of Problem H α (s). Thus, α⋄ h,α (s), -J ⋄ h,α (s) is a boundary point.By supporting hyperplane theorem (p. 133 of [27] ), there exists a line L that passes through the boundary point α⋄ h,α (s), -J ⋄ h (s) and contains conv(H(s)) in one of its closed half-spaces. Note that L is a one-dimensional linear space. Therefore, we can also say α⋄ h,α (s), -J ⋄ h (s) is within the convex hull of L H(s), conv(L H(s)), namely, α⋄ h,α (s), -J ⋄ h ) ∈ conv(L H(s) . By Caratheodory's theorem [17] , we have that α⋄EQUATIONm , α(2) m } ∈ [0, 1] 2 such that -J ⋄ h,α (s) = -J ⋆ α(1) m (s)ν ⋄ m (1) -J ⋆ α(2) m ν ⋄ m (2), α⋄ h,α = α(1) m ν ⋄ m (1) + α(2) m ν ⋄ m (2).It holds thatEQUATIONm is a feasible solution of Problem V α (s, L) when L = 2. Therefore, we haveEQUATION)From J ⋄ h,α (s) ≤ J v α (s, L) and J ⋄ h,α (s) ≥ V ⋆ α (s) (by ( 24)), we haveEQUATIONs) also holds. Note that J w α (s, L) = J b α (s, L), we have (17) . The rest of Theorem 2 can be shown by applying Theorem 1, which completes the proof of Theorem 2.As preparation for proving Theorem 3, we first give the following proposition on the optimal solution of Problem FPO.EQUATION) (s), w ⋆ (s) be an optimal solution of Problem FPO. Let α(1) = 1 -P ⋆ (a ⋆(1) (s)) and α(2) = 1 -P ⋆ (a ⋆ (2) (s)). We haveEQUATION)Proof of Proposition 3. By repeating the proof of Theorem 1, we can show that V d α (s) equals to the optimal value of the following problem:EQUATIONBy Theorem 2, we haveEQUATION)Based on Proposition 3, we give the proof of Theorem 3.Proof of Theorem 3. If α = 0, the optimal solution of Problem V α (s, L) with L = 2 has to set α(1) = α(2) = 0, which leads toEQUATIONThen, by Proposition 2 and Theorem 2, we haveEQUATIONwhich can be attained by an optimal solution of Problem C α (s) referring to a deterministic policy.Proof. Define the discounted return of a specific trajectory with γ unsafe ∈ (0, 1) byEQUATION)Define a function G ⋆ (s, a) byEQUATION)Here, π ⋆ sec is an optimal solution of Problem ECRL. From the definition of G(τ ∞ ) in (31) , we can rewrite G ⋆ (s, a) in the following way:EQUATION)The continuity of each Pr π ⋆ sec s0,∞ {I(g(s i ))|s 0 = s, a 0 = a} is guaranteed by Assumption 2 and the continuity of g(•) (pp. 78-79 of [25] ), which naturally leads to the continuity of G ⋆ (s, a). With G ⋆ (s, a), a probability measure optimization problem is defined as follows:max µ∈M (A) A Q ⋆ α (s, a) dµ s.t. A G ⋆ (s, a) dµ ≤ α. (B sec α (s))By just repeating the proof of Theorem EQUATIONs.t. wG ⋆ s, a (1) + (1 -w)G ⋆ s, a (2) ≤ α. (W sec α (s))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 ⋆ (s, a).Proof. Define a violation probability function V joint (θ, s) byEQUATION)Note that the constraint V joint (θ, s) ≤ α is equivalent toPr π θ s,∞ {s i ∈ S, ∀i ∈ [T ] | s 0 = s ∈ S} ≥ 1 -α.By using Boole's inequality, we haveEQUATIONEQUATION)Due to (35), V T unsafe (θ, s) ≤ α, ∀s ∈ S implies V joint (θ, s) ≤ α, ∀s ∈ S. By replacing s by s k , we obtain (4) by setting C(θ, s) = V T unsafe (θ, s) -α. Then, V T unsafe (θ, s) -α is a conservative approximation of joint chance constraint (3) .Then, we will show that we can find γ unsafe and T to make the following equality holds:EQUATIONThen, we give the proof of Theorem 6 as follows:Proof of Theorem 6. For J * α = J w α , it can be obtained by repeating the proof of Theorem 2. EQUATIONEQUATION)Since J * α is a strictly convex function of α on (α, α), we haveJ * α < ν * m (1) * J * α(1) + ν * m (2) * J * α(2) α(1) , α((2) ∈ (α, α) ≤ ν * m (1) * J * α(1) + ν * m (2) * J * α(2)= J * α , which completes the proof.Proof of Theorem 7. Since Problem LP is a special case of Problem PSPRL, Theorem 6 implies the existence of an optimal solution in Dα (Z S ) with no more than two non-zero elements.Since θi is the optimal solution of Problem PDPRL with α = αi , Problem LP has the same optimal value with the following optimization problem:max νs(1),...,νs(S)∈[0,1] S S i=1 J * αi ν s (i) s.t. S i=1 ν s (i)α i ≤ α, S i=1 ν s (i) = 1. ( K α (Z S ))Define another optimization problem as:max νc∈M ([0,1]) [0,1] J * αdν c s.t. [0,1] αdν c ≤ α. ( K α)Let J k α and D α be the optimal solution and optimal solution set of Problem K α. Note that Z S = {α i } S i=1 is extracted according to uniform distribution. By applying Theorem 6 of [35] , we have• J k α (Z S ) ≤ J k α ; • J k α (Z S ) → J k α with probability 1 as S → ∞.Then, if we show that J k α = J * α , it leads to J k α (Z S ) → J * α with probability 1 as S → ∞. By Proposition 4, we haveEQUATIONwhere θ (i) * is one optimal solution of Problem PDPRL with α = α(i) , i = 1, 2. We further haveEQUATIONThus, the probability measure νflip c defined byνc flip α(1) = ν * m (1), νc flip α(2) = ν * m (2) (45)is a feasible solution of Problem K α, which implies thatEQUATION)On the other hand, by applying Theorem 6, we have that Problem K α has a flipping-based optimal solution νflip c ,EQUATIONIt leads toEQUATIONEQUATIONwhich implies that J k α equals an objective value of a feasible solution of Problem PSPRL. Thus,EQUATIONDue to 46 and (50), we have J k α = J * α , which completes the proof.Proof. First, we show that θαs (s, θ k , D N ) is a feasible solution of Problem CPOS with probability larger than 1 -exp -2N (α s -αs ) 2 (1 -γ unsafe ) 2 . Define two functions byF (θ) := 1 -E s ini ∼π θ k ,a∼π θbad I(g(s + )) , F (θ, D N ) := 1 - 1 N N i=1I(g(s +,(i) )).Here, we simplify the notation by omitting s and θ k since it claims the same conclusion for all s and θ k . Besides, define two probability α trf s and αtrf s transformed from α s and αs byα trf s := (α s -H unsafe (θ k , s)) (1 -γ unsafe ). αtrf s := (α s -H unsafe (θ k , s)) (1 -γ unsafe ). Note that α trf s -αtrf s = (α s -αs )(1 -γ unsafe ).Let θbad be an infeasible solution of Problem CPOS. Then, we haveEQUATIONThe probability of θbad being a feasible solution of Problem S-CPOS isEQUATIONwhere Y i is defined by Y := 1 -I(g(s +,(i) )). According to Hoeffding's inequality [23] , (52) impliesPr F ( θbad , D N ) ≥ 1 -αtrf s ≤ exp - 2N 2 (α trf s -αtrf s ) 2 N i=1 (1 -0) 2 = exp -2N (α s -αs ) 2 (1 -γ unsafe ) 2 .(53) Here, (53) means that the probability of θbad being a feasible solution of Problem S-CPOS is smaller than exp -2N (α s -αs ) 2 (1 -γ unsafe ) 2 , which implies that a feasible solution of Problem S-CPOS has a probability larger than 1 -exp -2N (α s -αs ) 2 (1 -γ unsafe ) 2 to be a feasible solution of Problem CPOS. The optimal solution θαs (s, θ k , D N ) of Problem S-CPOS is also included. When θαs (s, θ k , D N ) is feasible for Problem CPOS, it is feasible for Problem CLPS. By applying Theorem 5, we have that θαs (s, θ k , D N ) is also feasible for Problem LPS and thus the policy admitted by θαs (s, θ k , D N ) satisfies the joint chance constraint in Problem CCRL.Firstly, we will show that an affine chance constraint exists to approximate the joint chance constraint conservatively. The approximate problem also has a flipping-based 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 it, which gives the approximate solution of Problem CCRL.Let H acc (θ, s) be a unsafety function defined byEQUATIONNotice that H acc (θ, s) satisfiesH acc (θ, s) = 1 - T i=1 Pr π θ s,∞ {s i ∈ S | s 0 = s} .Thus, the constraint H acc (θ, s) ≤ φ is equivalent toT i=1 Pr π θ s,∞ {s i ∈ S | s 0 = s} ≥ 1 -φ,which is a special case of affine chance constraint [13] . The theorem of conservative approximation of joint chance constraint based on affine chance constraint is as follows: Theorem 9. Suppose that S is compact and Assumption 2 holds. Define a function C acc (θ, s) as follows:C acc (θ, s, φ) := H acc (θ, s) -φ. (55) If φ ≤ α, C acc (θ, s, φ) is a conservative approximation of joint chance constraint (3).Proof. From the definition of H acc (θ, s) as (54), we haveEQUATIONDue to Boole's inequality (p. 14 of [10] ), we further haveEQUATIONThus, by (57), the following holdsEQUATIONSince the left side of (58) is equivalent toEQUATIONimplies that C acc (θ, s, φ) is a conservative approximation of joint chance constraint (3).MDP with affine chance constraint can be written bymax π∈Π V π (s) s.t. T i=1 Pr π s0,∞ {s k+i / ∈ S | s k ∈ S} ≤ α, ∀k = 0, 1, 2, ..., (A α (s))where the constraint of Problem A α (s) is a conservative approximation of (1), which can be proved following the same flow of Theorem 9. The following theorem for Problem A α (s) holds: Theorem 10. A flipping-based policy exists in the optimal solution set of Problem A α (s).Proof. Define a function H ⋆ acc (s, a) byEQUATIONHere, π ⋆ acc is an optimal solution of Problem A α (s). The continuity of H ⋆ acc (s, a) is guaranteed by Assumption 2 and the continuity of g(•) (pp. 78-79 of [25] ). With H ⋆ acc (s, a), a probability measure optimization problem is defined as follows:max µ∈M (A) A Q ⋆ α (s, a) dµ s.t. A H ⋆ acc (s, a) dµ ≤ α. (B acc α (s))By just repeating the proof of Theorem 1, we can obtain that the optimal objective value of Problem B acc α (s) equals the one of Problem A α (s) for any s ∈ S. A flipping-based version of Problem B acc α (s) is written byEQUATIONs.t. wH ⋆ acc s, a (1) + (1 -w)H ⋆ acc s, a (2) ≥ 1 -α. (W acc α (s))Since the continuity of H ⋆ acc (s, a) holds and it is bounded within [0, 1], Theorem 10 can be proved by following the same process of proving Theorem 2 after replacing P ⋆ (s, a) by H ⋆ acc (s, a).We present the details of our numerical example. The system dynamics is described byx k+1 y k+1 = 1 0 0 1 x k y k + dt u k + δ k v k + ζ k .Here, dt is the sampling time, the system state is 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 40-180, 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, we selected the policy network at an appropriate cost limit as the base network for the Flipping-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.s k := [x k y k ] ⊤ representingCollision Probability Analysis. We monitored whether the agent encountered collisions under each single-step condition across all 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 in 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 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 a clear positive correlation, affirming the validity and reliability of our experimental outcomes. Our analysis further supports that the flipping-based 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 policy can also enhance the performance of P3O and CUP. Additionally, experiments were conducted for the four baselines-CPO, PCPO, P3O, and CUP-under the CarGoal2 environment, with the results summarized in Figure 8 .The findings in CarGoal2 are consistent with those in PointGoal2.Figures 9 and 10 summarize reward and cost profiles of the training processes for each baseline algorithm on PointsGoal2. The training results further confirm that combining a performance policy with a safe policy yields a flipping-based policy that outperforms the policy trained by the original algorithm, while adhering to the required cost limit.NeurIPS Paper ChecklistIn this paper, we refer to uniform continuity. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The typo in the abstract: expected cumulative safety constraints (ESCSs) should be ECSCs.
2. The typo in Algorithm 2, line 2: Remove one of the redundant as in the statement.
3. 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.
4. 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.
5. 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.
6. 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.
7. The authors should ensure that at least two environments are considered in experiments for broader applicability.
8. This paper should add a related work section to compare and contextualize the current research within the broader field.
questions: questions: 1. What is the cause of the sudden change behavior observed in the experimental results of the "origin" group in Figure 2?
2. 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?
3. 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: limitations: The authors thoroughly discussed the limitations and potential negative societal impacts in the Appendix.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The algorithm involves multiple layers of optimization and probability adjustments which might be difficult to tune in real-world applications.
2. 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
questions: questions: 1. Could we possibly use neural networks to predict action candidates and flip probabilities?
2. What is the difference between flip-based policy and reject sampling?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.
2. 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.
3. In 4.3, is there a distinction between \Theta and \boldsymbol{\Theta}?
4. In 5.2, I think you mean to say the reward INCREASED with the flipping policy
5. 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: 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.
paper_summary: paper_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
strength_weakness: strength_weakness: 1. Some of the theoretical results would benefit from explanations and intuitions behind them. For instance, why do they work? See questions
1. 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.
1. 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.
questions: 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? 
1. What is the intuition behind the possibility of using only two policies and not L as Proposition 1 suggests? 
1. 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?
1. What steps one has to take to adapt say safe PPO to a flipping-based policy?
1. How did you reformulate the PointGoal problem as a chance constrained problem?
limitations: limitations: limitations are discussed

Comments: title: Reply to the Official Comment by Reviewer 7QvG
Thank you for your additional comments
Thank you for your additional reply
comment: Thanks for your additional comment! It is helpful. We will add some descriptions of the additional insight in the new version. Thank you again for your time and comments!
Many thanks for the response! I apologise for the typos, but you did answer my question!

I think it's an interesting observation that the degrees of freedom in the number of policies ($L$) is related to the problem complexity. It seems that in the considered case one needs two policies dealing with the constraint violations (almost like a performance policy and a safety policy). If an additional insight can be drawn from your experiments, I think it's worth adding a few lines on to the final version of the paper.
We appreciate your valuable advice and comments. Thank you for increasing the score! We ensure that all reviewers’ feedback will be reflected in the new version of our paper. The question about the number of policies in the official comment is very important and interesting. According to our recent results, more complex problem formulations will need more policies. We would like to share the conclusion about the expected cumulative safety constraints. The number of necessary policies equals the number of constraints plus one. Namely, we have $l=m+1$, where $l$ is the number of necessary policies and $m$ is the number of expected cumulative safety constraints. It also works for the chance constraint in this manuscript since the joint chance constraint is essentially one constraint for the probability of an event. 

Thank you again for your patience and time for our manuscript!
Thank you for a detailed response. 

Re $L = 2$. If I followed your explanation, the fact that we use chance constraint with one parameter $\alpha$ implies that we need to policies to find the optimal value of $V$. Could that imply that in others more complex problem formulations, we may need to choose more than one policy?
We would like to express our sincere gratitude to the reviewer for reading through our responses and having raised the score. We believe that the valuable comments from Reviewer 7qnc are very helpful for us to improve our paper. Thank you very much for your considerable comments.

We will add a short but clear remark in the new version to highlight the subtle distinction between Problem CCRL and Problem PSPRL.

Solving Problem LP naturally gives us a solution that is a mixture of two deterministic policies. 
To show that a mixture of more deterministic policies doesn't help exactly, we think it is necessary to propose an algorithm to solve PSPRL directly instead of obtaining an approximate solution by solving Problem LP. 
We leave this as future work. It is a very interesting point.

Thank you again for your patience and helpful comments!
Thm 6 / Q5: This is very helpful, thank you for the clarification! I would say that, even with your response and going back through the paper, it took me a while to see this subtle (but apparently important) distinction between CCRL and PSPRL--maybe the authors could try to highlight it more?

For your experimental results--I agree with the bolded statement about your *theoretical* results, and indeed this is a surprising and nice result precisely because one's baseline expectation is that a mixture of more deterministic policies should be better than a mixture of fewer deterministic policies! My point was that your *empirical* results only confirm this expectation for one versus a mixture of two deterministic polices (and hence are not very surprising), not the surprising part that mixing in *more* deterministic policies *doesn't* help.

Your examples with "dangerous regions" are quite compelling--thank you for clarifying this!

I have raised my score to a 7.