Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithms
Authors: Akifumi Wachi
Wataru Hashimoto
Xun Shen
Kazumune Hashimoto
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Safety Exploration
TL;DR: We present a generalized safe RL problem and propose an algorithm that is practically useful and supported by theoretical foundations.

Abstract: Safe exploration is essential for the practical use of reinforcement learning (RL) in many real-world scenarios. In this paper, we present a generalized safe exploration (GSE) problem as a unified formulation of common safe exploration problems. We then propose a solution of the GSE problem in the form of a meta-algorithm for safe exploration, MASE, which combines an unconstrained RL algorithm with an uncertainty quantifier to guarantee safety in the current episode while properly penalizing unsafe explorations before actual safety violation to discourage them in future episodes. The advantage of MASE is that we can optimize a policy while guaranteeing with a high probability that no safety constraint will be violated under proper assumptions. Specifically, we present two variants of MASE with different constructions of the uncertainty quantifier: one based on generalized linear models with theoretical guarantees of safety and near-optimality, and another that combines a Gaussian process to ensure safety with a deep RL algorithm to maximize the reward. Finally, we demonstrate that our proposed algorithm achieves better performance than state-of-the-art algorithms on grid-world and Safety Gym benchmarks without violating any safety constraints, even during training.

Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithms
Akifumi Wachi
Wataru Hashimoto
LINE Corporation akifumi. waw.....ehe...eec...ooom
Osaka University
hashimoto@is eei eng. osaka-u.a..].
Xun Shen
Kazumune Hashimoto
Osaka University
Osaka University
shenxun@eei. eng osaka-u.ac. jp.
hashimoto@eei. eng. osaka-u.
Abstract
Safe exploration is essential for the practical use reinforcement learning (RL) many real-world scenarios. In this paper, present generalized safe exploration (GSE) problem as a unified formulation of common safe exploration problems. We then propose solution of the GSE problem in the form of a meta-algorithm for safe exploration, MASE, which combines an unconstrained RL algorithm with uncertainty quantifier guarantee safety in the current episode while properly penalizing unsafe explorations before actual safety violation to discourage them in future episodes. The advantage of MASE is that we can optimize a policy while guaranteeing with a high probability that no safety constraint will be violated under proper assumptions. Specifically, we present two variants of MASE with different constructions of the uncertainty quantifier: one based on generalized linear models with theoretical guarantees of safety and near-optimality, and another that combines a Gaussian process to ensure safety with deep RI. algorithm to maximize the reward. Finally, we demonstrate that our proposed algorithm achieves better performance than state-of-the-arr algorithms on grid-world and Safety Gym benchmarks without violating any safety constraints, even during training.
Introduction
Safe reinforcement learning (RL) is a promising paradigm that enables policy optimizations for safety-critical decision-making problems (e.g., autonomous driving, healthcare, and robotics), where is necessary to incorporate safety requirements prevent RL policies from posing risks humans or objects [14]. As a result, safe exploration has received significant attention in recent years as crucial issue for ensuring the safety of RL during both the learning and execution phases (6]
Safe exploration in RL. has typically been addressed by formulating a constrained RL problem in which the policy optimization is subject to safety constraints p 18] While there have been many attempts under different types constraint representations (e.g.. expected cumulative cost [3], CVaR (29),, satisfying constraints almost surely with high probability received less attention date. Imagine safety-critical applications such as planetary exploration where even a single constraint safety least with high probability [8] thus, constraint satisfaction "on average" does not fit their purpose.
violation may result in catastrophic failure. NASA's engineers hope Mars rovers
While several algorithms have addressed this problem with this stricter notion of safcty, there several formulations in terms of how the constraints are represented, including cumulative [32 state (39], and instantaneous constraints 41, which respectively correspond to Problems and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

as we will discuss shortly in Section 2 Unfortunately, there has been limited discussion on the relationships between these approaches, making it challenging for researchers to acquire systematic understanding of the field as a whole. If generalized problem were to be formulated, then the research community could pool their efforts to develop suitable algorithms.
A closer examination of existing algorithms that span the entire theory-to-practice spectrum reveals several areas for improvement. Practical algorithms using deep RL (e.g.. [32]. (39 (40) may provide satisfactory performance after convergence, but do not usually guarantee safety during training. In contrast, theoretical studies (e.g.. training often have limitations, such as relying on strong assumptions (e.g., known state transition) or experiencing decreased performance in complex environments. In summary, many algorithms have been proposed in various safe RL formulations, but the creation of a safe exploration algorithm that both practically useful and supported by theoretical foundations remains an open problem.
that guarantee safety with high probability during
Contributions. We first present a generalized safe exploration (GSE) problem and prove its generality compared with existing safe exploration problems. By taking advantage of the tractable form of the safety constraint in the GSE problem, we establish a meta-algorithm for safe exploration, MASE. This algorithm employs an uncertainty quantifier for a high-probabiiltty guarantee that the safety constraints are not violated and penalizes the agent before safety violation, under the assumption that the agent has access to an "emergency stop" authority. Our MASE both practically useful and theoretically well- well-founded, which allows us to optimize a policy via an arbitrary RL algorithm under the high-probability safety guarantee, even during training. We then provide two specific variants of MASE with different uncertainty quantifiers. One is based on generalized linear models (GLMs), for which we theoretically provide high-probability guarantees of safety and near-optimallty. The other is more practical, combining a Gaussian process (GP, (77) ) to ensure safety with a deep RL algorithm to maximize the reward. Finally, we show that MASE performs better than state-of of-th-rr----rtt algorithms on the grid-world and Safety Gym 228 without violating any safety constraints, even during training.
2 Preliminaries
Definitions. We consider an episodic safe RL problem in a constrained Markov decision process (CMDP, (3)), M = (S, H,, rr, g, $1 ), where S is state space, A is an action space, H/ E E (fixed) length of each episode, P 8 A x S + [0, 1] is a state transition probability, r: S x A + j0. 1] is a reward function, g S x A + [0. 1] is a safety (cost) function, and 81 E S is an initial state. At each discrete time step. with given fuulyy-bberrvabe) state s, the agent selects an action a with respect to its policy π S + A. receiving the new state s', reward r, and safety cost g. Though we assume a deterministic policy, our core ideas can be extended to stochastic policy settings. Given policy æ, the value and action-value functions in a state s at time h are respectively defined as
H
(+)(() E
M' r(sw:aw)) 7/
8h =
h'=h
1 |s, = 8, 02 = where the expectation E3 taken over the random state-action sequence {(ss, )) induced by the policy n. Additionally, Y E (0, 1] is discount factor for the reward function. In the remainder of this paper, define VIax = I->r
and (s, E, -m 2h r(s ax)
1- and let To (S x A R. - (S x A + R) denote the Bellman update operator (Q) a) T.. [r(sh, a,)) + 7r V. (8(+++1) 8h 8, 04. a). where V*( == max (s, a).
Three common safe RL problems. We tackle safe RL problems where constraints must be satisfied almost surely, even during training. While such problems have garnered attention in the research community, there are several types of formulations, and their relations are yet to be fully investigated.
One of the most popular formulations for safe RL problems involves maximizing V," = V (st) under the constraint that the cumulative cost is less than a threshold, which described as follows: Problem 1 (Almost surely safe RL with cumulative constraint
(32). )
max V
subject to Pr
h gg an) S E1 P, 1,
A=1
where & E R2o is a constant representing threshold, and 7g (0. 1] is discount factor for g.
2

---

Observe that, the expectation is nor taken regarding the safety constraint in Problem | was studied in [32), which stricter than the conventional one where the expectation is taken with respect to the cumulative safety cost function (i.e., Ex E 7 ( an) ] - &1).
This problem
Another popular formulation involves leveraging the state constraints so that safety corresponds to avoiding visits to set of unsafe states. This type of formulation has been widely adopted by previous studies on safe-critical robotics tasks 40 45,,
which is written as follows:
Problem 2 (Safe RL with state constraints).
max V
subject to
E
Σ A=1
T(sk E Sunsate) P. S E2.
where &2 R20 is a threshold, I(-) is the indicator function, and Sunsafe C S is set of unsafe states.
Finally, some existing studies formulate safe RL problems via an instantaneous constraint, attempting ensure safety even during the learning stage while aiming for extremely safety-critical applications such as planetary exploration 42 or healthcare [36]. Such studies typically require the agent to satisfy the following instantaneous safety constraint at every time step.
Problem 3 (Safe RL with instantaneous constraints).
max V subject to Pr g(( an)
P =1,
P,
vh E [1,
where ε3 E 1gg a time-invariant safety threshold.
Problem Formulation
This paper also requires agent optimize policy under safety constraint, in the three common safe RL problems. We seek to find the optimal policy л¹ S A of the following problem, which will hereinafter be referred as the "generalized" safe exploration (GSE) problem:
Problem 4 (GSE problem). Let by E R denote a time-varying threshold.
max V subject to Pr[9(Sh, an) bn P. 1, wh [1.
This constraint is instantaneous, which requires the agent to learn policy without single constraint violation not only after convergence but also during training. We assume that the threshold is myopically known; that is, by is known at time h, but unknown before that. Crucially, at every time step h, since 8h is fully observable state and the agent's 's policy is deterministic, we will use a simplified inequality represented as ((A,, an) by in the rest of this paper. This constraint is akin to that in Problem 3 with the difference that the safety threshold is time-varying.
Importance of the GSE problem. Though our problem may not seem relevant to Problems I andd 2 we will shortly present and prove theorem on the relationship between the GSE problem and the three common safe RI. problems.
Theorem 3.1. Problems and can be transformed into the GSE problem (i.e., Problem
See Appendix B for the proof. In other words, the feasible policy space the GSE problem can be identical to those in the other three problems by properly defining the safety cost function y and threshold by Crucially, Problem iis a special case of the GSE problem with b; = 7m for all h, where 7h++1 Yg (m. g(s,, an)) with no &1. It is particularly beneficial to convert Problems and 2 which have additive constraint structures, to the GSE problem, which has an instantancous constraint. The accurate estimation of the cumulative safety value in Problems [ and 2 is difficult because they depend on the trajectories induced by a policy. Dealing with the Instantaneous constraint in the GSE problem is easier, both theoretically and empirically. Also, especially when the environment is vime-varying (e.g., there are moving obstacles), the GSE problem is more useful than Problem 3
Typical CMDP formulations with expected cumulative (safety) cost are out of the scope of the GSE problem. In such problems, the safety notion is milder; hence, although many advanced deep RI. algorithms have been actively proposed that perform well in complex environments after convergence,
3

---

their performance in terms of safety during learning is usually low, as reported by Stooke et al. [3 or Wachi al. [43]. Risk-constrained MDPs are also important safe RL problems that are not covered by the GSE problem; they have been widely studied by representing risk as a constraint on some conditional value-at-risk
or using chance constraints [24 26
Difficulties and Assumptions. Theorem 3.1 insists that the GSE problem covers a wide range of safe RL formulations and is worth solving, but the problem is intractable without assumptions. We now discuss the difficulties in solving the GSE problem, and then list the assumptions in this paper.
The biggest diffieulty with the GSE problem lies in the fact that there may be no viable safe action given the current state Sn, safety cost g. and threshold by. When bn = 0.1 and g(s), a) = 0.5, Va E A. the agent has viable action for ensuring safety. The agent needs guarantee safety, even during training, where little environmental information is available; hence, it is significant for the agent to avoid such situations where there is action that guarantees safety. Another difficulty is related to the regularity of the safety cost function and the strictness of the safety constraint. In this paper, the safety cost function is unknown a priori.; thus, when the safety cost does not exhibit any regularity, the agent can neither infer the safety of decisions nor guarantee safety almost surely.
To address the first difficulty mentioned above, we use Assumptions and 3.3
Assumption 3.2 (Safety margin). There exists Ç E R such that Pr g(sh, an) S by - PPP, 1, vh E [1, H].
Assumption 3.3 (Emergency stop action). Let @ be an emergency stop action such that P(() | s, a) 1 for all S. The agent is allowed to execute the emergency stop action and reset the environment if and only if the probability of guaranteed safety is not sufficiently high.
Assumption 3.2 is mild; this is similar to the Slater condition, which is widely adopted in the CMDP literature 1 25 We consider Assumption B.3 also natural for safety-critical applications because it is usually better to guarantee safety, even with human interventions, if the agent requires help in emergency cases. In some applications (e.g., the agent is in a hazardous environment), however, emergency stop actions should often be avoided because of the expensive cost of human intervention. In such cases, the agent needs to learn a reset policy allowing them to return to the initial state as in Eysenbach et al. (15), rather than asking for human help, which we will leave to future work.
As for the second difficulty, we assume that the safety cost function belongs to a class where uncer- tainty can be estimated and guarantee the satisfaction of the safety constraint with high probability. We present an assumption regarding an important notion called an uncertainty quantifier:
Assumption 3.4 (6 (6-uncertainty quantifier). Let fu: : SS A -> R denote the estimated mean function of safety. There exists a 5-uncertainty quantifier P: S x A -> TR such that g(s a) - =u(s, a) S T(s, a) for all (s, a) E S A, with probability of at least 8.
4 Method
We propose MASE for the GSE problem, which combines an unconstrained RI. algorithm with addi- tional mechanisms for addressing the safety constraints. The pseudo-code is provided in Algorithm [ and a conceptual illustration can be seen Figure
The most notable feature of MASE is that safety is guaranteed via the d-uncertainty quantifier and the emergency stop action (lines 3 - 9). The ö-uncertainty quantifier is particularly useful because we can guarantee that the confidence bound contains the true safety cost function, that is, g(s, a) E (usss a) + T[ss, a) for all s E S and a E A. This means that, if the agent chooses actions such that p(sa, an) + I(sh; an) bn, then g( an) < by. holds with a probability of at least 1 8. Regarding the first difficulty mentioned in Section 3 it is crucial that there is at least one safe action. Thus, every time step h. the agent computes set of actions that are considered satisfy the safety constraints with a probability at least 8 given the state 8,, and threshold by. This is represented as
A = a E A min 1, 1. a) + [(sh, a) } < by }.
Whenever the agent identifies that at least one action will guarantee safety, the agent is required to choose an action within A (line 3). The emergency stop action is executed if and only if there is no
'The solution in the GSE problem is guaranteed to be conservative approximation of that in safe RL problems with chance constraints. For more details, see Appendix C

---

Algorithm Meta-Algorithm for Safe Exploration (MASE)
1:
for episode / 1, ,. do for time h 1, ..... H do
2:
3:
Take "safe" action Receive reward r(s,, an). safety cost (Sh, an). and next state 8h+1
(sn) within A
>> Execute only safe actions
4:
5:
Update safety threshold PN+1
6:
if A = 0 then
7:
Compute F(sh, anh minge (1) Append (sh, ah: f(sh, an), 8h+1) to D
Penalty for the emergency stop action
8:
9:
break (i.e., take action @)
b Execute the emergency stop action
10:
else
Append (sh, az r(sh, an), 8h+1)
12:
Optimize a policy x based on 'D via an (unconstrained) RL algorithm
Update the uncertainty quantifier I' and rewrite D
viable action satisfying the safety constraint (i.e., A 0); that is, the agent is allowed execute à and start new episode from an initial safe state (lines 6 9). The safety cost upper-bounded by I because E [o, 1] by definition. Note that MASE proactively avoids unsafe actions by selecting the emergency stop action to take beforehand; this is in contrast to Sun et al. (37, whose method terminates the episode immediately after the agent has already violated safety constraint.
When safety is guaranteed in the manner described above, the question remains to how to obtain policy that maximizes the expected cumulative reward. As such, we first convert the original CMDP M the following unconstrained MDP
M = (S.
The changes from M lie in the action space and the reward function, as well as in the absence of the safety cost function. First, the action space augmented that the agent can execute the emergency stop action, a. The second modification concerns the reward function. When executing the emergency stop action à, the agent is penalized as its sacrifice so that the same situation will not occur in future episodes; hence, we modify the reward function as follows:
cf minae ((8441, if A 0.
F(sh, an)
r(sh, ax)
otherwise,
where c Ry0 is positive scalar representing penalty for performing the emergency stop. This penalty assigned to the state-action pair (8), ax) that placed the agent into the undesirable situation time step h + 1, represented as A = (see Figure
To show that MASE is reasonable safe RL algorithm, we express the following intu- itions. Consider the ideal situation in which the safety cost funetion is accurately es- timated for any state-action pairs; that is, ass.
F F.
viahle (i.c., Ar+1 ()
as
Ski1
for all (s, a). In this case, all emergency stop actions are properly exe- cuted, and the safety constraint will be vio- lated at the next time step if the agent exe- cutes other actions. It reasonable for the agent to receive penalty of f(s, because this state-action pair surely causes a safety violation without the emergency stop action. Unfortunately, however, the safety cost is uncertain and the agent conservatively executes à although there still actions satisfying the safety constraint, especially in the early phase of training; hence, we increase or reduce the penalty according to the magnitude of uncertainty in (1) avoid excessively large penalty.
Oh+1
Skil
Sk12
Figure 1: Conceptual illustration of MASE. At every time step ht the agent chooses action an within A there is no safe action at state 81+11 satisfying the constraint, the emergency stop action is executed and the agent receives a large penalty for (sh, on).
We must carefully consider the fact that the quality of information regarding the modified reward function f is uneven in the replay buffer D. Specifically, in the carly phase of training, the 8-
5

---

uncertainty quantifier is loose. Hence, the emergency stop action is likely to be executed even if viable actions remain; that is, the agent will receive unnecessary penalties. In contrast, the emergency stop actions in later phases are executed with confidence, as reflected by the tight d-uncertainty quantifier. Thus, as in line 15, we rewrite the replay buffer D while updating T depending on the model in terms of the safety cost function (as for specific methods to update r, see Sections and
Connections to shielding methods. The notion of the emergency stop action akin to shielding [2] 20 which has been actively studied in various problem settings including partiall--bservabbe
environments [0] or multi-agent settings (23]. Thus, MASE can be regarded
variant of shielding
methods (especially, preemptive shielding in (2) that is specialized for the GSE problem. On the other hand, MASE does not only block unsafe actions but also provides proper penalties for executing the emergeney stop actions based on the uncertainty quantifier, which leads to rigorous theoretical guarantees presented shortly. Such theoretical advantages can be enjoyed in many safe RI. problems because of the wide applicability of the GSE problem backed by Theorem 3.1
Advantages of MASE. Though certain existing algorithms for Problem (i.e., the closest problem to the GSE problem) theoretically guarantee safety during learning, several strong assumptions are needed, such as known and deterministic state transition and regular safety function as in 41 and known feature mapping function that is linear with respect to transition kernels, reward, and safety as in [5] Such algorithms have little affinity with deep RL; thus, their actual performance in complex environments tends to be poor. In contrast, MASE is compatible with any advanced RL algorithms, which can also handle various constraint formulations while maintaining the safety guarantee.
Validity of MASE. We conclude this section by presenting the following two theorems to show that MASE produces reasonable operations in solving the GSE problem.
Theorem 4.1. Under Assumption
3.4 MASE guarantees safety with a probability of at least 1 - 5. Theorem 4.2. Assume that the safety cost function is estimated for any state-action pairs with an accuracy of better than S; that is, T(s, a) S for all (8,a), a). Set e E TR be sufficiently large scalar such that CYmus. Then, the optimal policy in M is identical to that in M. 27
See Appendix for the proofs. Unfortunately, obtaining a --uncertainty qualifier that works in general cases is highly challenging. To develop a feasible model for the uncertainty quantification, we assume that the safety cost can be modeled via GLM in Section 5 via a GP in Section
5 A Provable Algorithm under Generalized Linear CMDP Assumptions
In this section, we focus on CMDPs with generalized linear structures and analyze the theoretical properties of MASE. Specifically, we provide a provable algorithm to use a class of GLMs denoted as F for modeling Qr,, == Q and g, and then provide theoretical results on safety and optimality.
5.1 Generalized Linear CMDPs
We extend the assumption in Wang et al. 44 from unconstrained MDPs to CMDPs settings. Our assumption is based on GLMs as with 44 that makes a strictly weaker assumption than their Linear MDP assumption [19 46). As preliminaries, we first list the necessary definitions and assumptions.
Definition 5.1 (GLMs). Let d Z= be feature dimension and let Bd {x Rd ||x||2 < 1} be the le ball in Rd. For a known feature mapping function & S x A + Bd and a known link 1, 1], the class of generalized linear model is denoted as F = {(s, a) +
function f : [[1, 1]
[(( 0)) : 0 E Bdd where ds,a == a(s, a).
Assumption 5.2 (Regular link function). The link function f((-) is twice differentiable and is either monotonically increasing or decreasing. Furthermore, there exist absolute constants 0 < g < R < co and M < co such that K < [x( < R and (x) < M for all |x| < 1.
This assumption on the regular link function is standard in previous studies (e.g., 16 21).. Linear
and logistic models are the special cases of the GLM where the link functions are defined as f(x) = x and f(x) 1/(1 xx) In both cases, the link functions satisfy Assumption 5.2
We finally make the assumption of generalized linear CMDPs (GL-CMDPs)) which extends the notion of the optimistic closure for unconstrained MDP settings in Wang et al. [4

---

Assumption 5.3 (GL-CMDP). For any 1 1 h < H and u E Fup, we have Th(2) F and E F.
Recall that Th is the Bellman update operator. Assumption 5.3 with a positive semi-definite matrix
A E IRdxd > 0 and fixed positive constant O'max E Rgo, we define
Fup = {(s,a) + miin(Vmax: f(los,a , 0)) + a: a:lo,,alla) 0 Bd, ,,, O'max ||A||ap 1},
where | = vx Ax is the matrix Mahalanobis seminorm, and || is the matrix operator norm. For simplicity, we suppose the same link functions for the Q-function and the safety cost function, but it is acceptable to use different link functions. Note that Assumption [.3 is more general assumption than Amani et [5] that assumes linear transition kernel, reward, and safety cost functions or Wachi et al. 43 that assumes known transition and GLMSs in terms of reward and safety cost functions.
5.2 GLM-MASE Algorithm
We introduce an algorithm GLM-MASE under Assumptions 5.2 and 5.3 Hereinafter, we explicitly denote the episode for each variable. For example, we let % or i denote a state or action at the time step h of episode t. We also let ,7 == (ss) a% for more concise notations.
Uncertainty quantifiers. To actualize MASE in the generalized linear CMDP settings, we first need to consider how to obtain the 5-uncertainty quantifier in terms of the safety cost function. Since assume E F, we can define the ô-uncertainty quantifier based on the existing studies on GLMs, especially in the field of multi-armed bandit [22 16). Based on Assumptions 5.2 and 5.3
we now
provide a lemma regarding the d-uncertainty quantifier on safety.
Lemma 5.4. Suppose Assumptions 5.2 and 5.3 hold. Ser 5 = TH
With a universal constant
C' E Rso let Cg CFK V M - R d2 In (1+ Define
(F) 2h T(s,a)= = Cg. Il with An,E == Erst
11 +1,
where T is the identity matrix. Let h2 E Rdd be the ridge estimate, which is computed by 0 arg min 101 Erso (olsh _a -f(()((()
..))) ()=)(())),,))) 7(1) s (t) 19(s (0) (00) f((2)t
((T)
Then, the following inequality holds
for all (s,a) E A. with a probability least 6.
For the purpose of qualifying uncertainty in GLMs, the weighted l2-norm of o (i.e., (ol,all,, :) plays an important role. Because we assume that the Q-function and safety cost function share the same feature, we have a similar lemma on the uncertainty quantifier regarding the Q-function as follows:
Lemma 5.5. Suppose Assumptions
5.2 and 5.3 hold.
Let 0 E IRd denote the ridge esti- ,00)) where yn
mate; that is, 02 == arg min |0]1_51 Erst Un
(T) = r(s), .0) (1)
max.'EA (TT) 07 (5/t1) a') for all S with
0.0% (s, = mmi
( {VILxes Flmxx a( (2.)) + Caj ((s,a)))))
that is initialized with Q,0) 0 for all h S H and Q10) for all 1 S LLST T. Then, with
universal constant Coj, E R2o, the following inequalities holds
(7 ( f(( 7(1) (R,)) (2.))1 < Cojs [(6 .0
(1)
for all (s,a) S. X.x. A. with a probability least 6.
Note that (( (1) is the --uncertainty quantifier with respect to the safety cost function. One of the biggest advantages of the generalized linear CMDPs that the magnitude of uncertainty for the Q-function is proportional to that for the safety cost function. Hence, by exploring the Q-function
7

---

based on the optimism in the face of the uncertainty principle 35], the safety cost function is also explored simultaneously. which contributes the efficient exploration of state-action spaces.
Integration into MASE. The GLM-MASE is an algorithm to integrate the --uncertainty quantifiers inferred by the GLM into the MASE sequence. Detailed pseudo code is presented in Appendix E
To deal with the safety constraint, GLM-MASE leverages the upper bound inferred by the GLM; that is, for all h and t, the agent takes only actions that satisty
( (1 0h.,)) +
f
S bn.
(0)) S bn for all By Lemma 5.4, such state-action pairs satisfy the safety constraint, i.e. g(sh (0) h and t, with a probability at least 1 8. If there is action satisfying the safety constraint (i.e.. A = 0), the emergency stop action ā is taken, and then the agent receives a penalty defined in (T).
As for policy optimization, we follow the optimism in the face of the uncertainty principle. Specifi- cally, the policy æ is optimized so that the upper-confidence bound of the Q-function characterized by f is maximized; that is, for any state E S. the policy is computed as follows:
(t) K
8 arg max 7.P. (s,
aE.A
Intuitively, this equation enables us to 1) solve the exploration and exploitation dilemma by incorpo- rating the optimistic estimates of the Q-function and 2) make the agent avoid generating trajectories to violate the safety constraint via the modified reward function.
Theoretical results. We now provide two theorems regarding safety and near-optimality. For both theorems, see Appendix for the proofs.
Theorem 5.6. Suppose the assumptions in Lemma 5.4 hold. Then, the GLM-MASE satisfies
g(s)) an (1)) < by. for all t E [1,7] and h E [1, H). with probability at least 1-
Theorem 5.7. Suppose the assumptions in Lemmas 5.4 5.3) hold. Let C1 and C2 be positive, universal constants. Also. with a sufficiently large T. let t" denote the smallest integer satisfying Amin (E)tH CivtHd C2VtH In 5-1 2 2Cg 5-1 where Amin (E) is the minimum eigenvalue of the second moment matrix E. Then, the policy π (1) obtained by GLM-MASE episode satisfies
Σ I=
V
| zō (T
with probability at least 1
Theorem shows that the GLM-MASE guarantees safety with high probability for every time step and episode, which is a variant of Theorem 4.1 under the generalized linear CMDP assumption and corresponding 5-uncertainty quantifier. Theorem 5.7 demonstrates the agent's ability to act near-optimally after a sufficiently large number of episodes. The proof is based on the following idea. After t" episodes, the safety cost function and the Q-function are estimated with an accuracy better than $ Then, based on Theorem 4.2 the optimal policy in M is identical to that in M; thus, the agent achieves a near-optimal policy by leveraging the (well-estimated) optimistic Q-function.
6 A Practical Algorithm
Though we established an algorithm backed by theory under the generalized linear CMDP assumption in Section 55] it is often challenging to obtain proper feature mapping functions in complicated environments. Thus, in this section, we propose a more practical algorithm combining a Ga-based estimator guarantee safety with unconstrained deep RL algorithms to maximize the reward.
Guaranteeing safety via GPs. As shown in the previous sections, the 8-uncertainty quantifier plays a critical role in MASE. To qualify the uncertainty in terms of the safety cost function we consider modeling as a GP: g(z) ~ GP(p(=), k(zz where z == [s, a), pu=)) is a mean function, and k(z, z') is a covariance function. The posterior distribution over g(; is computed based on n E Z observations at state-action pairs (21, (2,,22,... ...,, Zn) with safety measurements yn { V1, 3/. ................................ Fo }, where yn = g(2n) + N,, and Nn. No(0 is zero-mean Gaussian noise
8

---

with standard deviation of w Rzo. We consider episodic RL problems, and so = tH + h for episode and time step h, although the equality does not hold because of the episode cutoffs. Using the past measurements, the posterior mean, variance, and covariance are computed analytically as kn (2, 2). and kn (z, 2") = k(2, z') k (=)(K, + 1 - kn (z'), where (z) [k(21, 2), ...... (z,, =)]" and Kn, is the positive definite kernel matrix. We now present a theorem on the safety guarantee.
Ne (2) = K (2) + w I) --nyyynnn- yn. (n(z)
Theorem 6.1. Assume l191l = and N₂ S for all 2 1. Set 3112= = B+ un + 1 + and construct the 8-umcertainty quantifier by
ass,a)= == Bn. an(s,)), V(s,a)
(2)
where Vo is the information capacity associated with kernel k. Then, MASE based on 2 satisfies the safety constraint g( ) < ba all t and h with a probability of at least 1 - 8.
See Appendix F for the proofs. Theorem 6. combining the GP-based 6-uncertainty quantifier in ( and the emergency stop action.
guarantees that the safety constraint is satisfied by
Maximizing reward via deep RL. The remaining task is to optimize the policy via the modified reward function f in (T), whereby the agent is penalized for emergency stop actions. This problem is decoupled from the safety constraint and can be solved the following unconstrained RL problem:
== arg max V.
There are many excellent algorithms for solving 3 such as trust region policy optimization (TRPO, RI) and twin delayed deep deterministic policy gradient (TD3, [17). One of the key benefits of our MASE is such compatibility with a broad range of unconstrained (deep) RI. algorithms.
7 Experiments
We conduct two experiments. The first is Safety Gym 288 where agent must maximize the
expected cumulative reward under a safety constraint with additive structures as in Problems [ and 2 The safety cost function g is binary (i.e., for unsafe state-action pair and 0 otherwise), and the
safety threshold is set to & = 20. The reason for choosing Safety Gym is that this benchmark is complex and elaborate, and has been used evaluate variety of excellent algorithms. The second is
a grid world where a safety constraint is instantancous as in Problem 3 Due to the page limit, we present the settings and results of the grid-world experiment in Appendix
To solve the Safety Gym tasks, we implement the practical algorithm presented in Section follows.
First, we convert the problem into a GSE problem by defining 6) == 2 -E1 -EI- =o==0= ?g g(s,, axy )) and enforcing the safety constraint represented as g ox.) < by for every time step /a in each episode. Second, to infer the safety cost, we use deep GP to conduct training and inference, in (30 when dealing with high sigh-dimensional input spaces. Finally, as for the policy optimization in M, we leverage the TRPO algorithm. We delegate other details to Appendix G
Baselines and metrics. We use the following four algorithms as baselines. The first is TRPO, which is a pafety-agnostic deep RL algorithm that purely optimizes a policy without safety consideration. The second and third are CPO I and TRPO-Lagrangian (28). which are well-known algorithms for solving CMDPs. The final algorithm is Sauté RL [32, which is recent, ttate-of-the-art algorithm for solving safe RL problems where constraints must be satisfied almost surely. We employ the following three metrics to evaluate our MASE and the aforementioned four baselines: 1) the expected cumulative reward, 2) the expected cumulative safety, and 3) the maximum cumulative safety. We exccute each algorithm with five random seeds and compute the means and confidence intervals.
Results. The experimental results are summarized in Figure 2 The figures show that TRPO, TRPO-Lagrangian, and CPO successfully learn the policies, but violate the safety constraints during training and even after convergence. Sauté RL is much safer than those three algorithms, but the safety constraint is not satisfied in some episodes, and the performance of the policy significantly deteriorates in terms of the cumulative reward during training. Our MASE obtains better policies in a smaller number of samples compared with Sauté RI, while also satisfying the safety constraints with respect to both the average and the worst-case. Note that, after convergence, the policy obtained by MASE performs worse than those obtained by the baseline algorithms in terms of reward, as shown in

---

CPO
So.ia TRIP
19P0
1e
VAG2
Couch
Couoh
(a) Average episode return.
(b) Average episode safety.
(c) Maximum episode safety.
1981
TWPP
24
TRPPO Lin
140-
TRPOLLS
20
Saura
130-
Soude TRAPO
NAGE
14-
Sality
10
0.5
TRPO
00
Sauce
20-
35
105
400 300
300
403 500
(d) Average episode return.
(e) Average episode safety.
(1) Maximum episode safety.
PointGoall, Bottom: CarGoal1). The proposed MASE satisfies the safety constraint every episode and achieves better performance in terms of the reward than the state-of-the-ee method called Sauté RL. Conventional methods (i.e., TRPO, TRPO-Lagrangian, and CPO) repeatedly violate the safety constraint, especially in the early phase of training. Shaded areas represent la confidence intervals across five different random seeds.
Figure 2: Experimental results on Safety Gym (Top:
3/6
Sulddy Direchadi
Saledy mensdwii
255
200
240
240
Traoo
(a) Average episode return.
(b) Average episode safety.
(c) Maximum episode safety.
Figure 3: Experimental results on Safety Gym (CarGoall) with the epoch of 1000. The box plots show the converged performance. Though MASE performs worse than other baselines in terms of reward, the acquired policy is still near-optimal. As for safety, while baselines violate the safety constraint in most of the episodes, MASE guarantees the satisfaction of the severe safety constraint.
Figure The emergency stop action is variant of resetting actions that common in episodic RL settings, which prevent the agent from exploring the state-action spaces since the uncertainty quantifier is sometimes quite conservative. We consider that this is reason why the converged reward performance of MASE is worse than other methods. However, because we require the agent to solve difficult problems where safety is guaranteed at every time step and episode, we consider that this result is reasonable, and further performance improvements are left to future work.
8 Conclusion
In this article, we first introduced the GSE problem and proved that it is more general than three common safe RL problems. We then proposed MASE to optimize a policy under safety constraints that allow the agent to execute an emergency stop action at the sacrifice of a penalty based on the 5-uncertainty qualifier. As a specific instance of MASE, we first presented GLM-MASE to theoretically guarantee the near-optimality and safety of the acquired policy under generalized linear CMDP assumptions. Finally, we provided a practical MASE and empirically evaluated its performance in comparison with several baselines on the Safety Gym and goid-world.
10

---

Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. This work is partially supported by JST CREST JPMJCR201 and by JSPS KAKENHI Grant 21K14184.
References
[1] Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017). Constrained policy optimization. In International Conference on Machine Learning (ICML).
[2] Alshiekh, M., Bloem, R., Ehlers, R., Könighofer, B., Niekum, S., and Topeu, U. (2018). Safe reinforcement learning via shielding. In AAAI Conference on Artificial Intelligence (AAAI).
[3] Altman, E. (1999). Constrained Markov decision processes, volume 7. CRC Press.
[4] Amani, S., Alizadeh, M., and Thrampoulidis, C. (2019). Linear stochastic bandits under safety constraints. Neural Information Processing Systems (NeurIPS).
[5] Amani, S., Thrampoulidis, C., and Yang, I.. (2021). Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning (ICML).
[6] Amodei, D.,, Olah, C., Steinhardt, J., Christiano, P., Schulman, J., and Mané, D. (2016). Concrete problems in Al safety, arXiv preprint weXiv:1606.0656
[7] Auer, and Ortner, R. (2007). Logarithmic online regret bounds for undiscounted reinforcement learning. In Neural Information Processing Systems (NeurlPS).
[8] Bajracharya, M., Maimone, M. W., and Helmick, D. (2008). Autonomy for rovers: Past, present, and future. Computer, 41 41(12):44-50.
[9] Brunke, L.,, Greeff, M., Hall, A. W., Yuan, Z., Zhou, S., Panerati, J., and Schoellig, A. P. (2022). Safe learning in roboties: From learning-basse based control safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5:411-444.
[10] Carr, S.. Jansen, N., Junges, S., and Topcu, U. (2023). Safe reinforcement learning via shielding under partial observability. In AAAI Conference on Artificial Intelligence.
[11] Chow, Y., Ghavamzadeh, M., Janson, L., and Pavone, M. (2017). Rist-constr reinforcement learning with percentile risk criteria. Journal of Machine Learning Research (JMLR), 1861):6070- 6120.
[12] Chowdhury, S. R. and Gopalan, A. (2017). On kernelized multi-armed bandits. International Conference Machine Learning (ICML).
[13] Ding, D., Zhang, K., Basar, T., and Jovanovic, M. (2020). Natural policy gradient primal-dual method for constrained Markov decision processes. In Neural Information Processing Systems (NeurIPS).
[14] Dulac-Amold, G., Levine, N., Mankowitz, D. J., Li, J., Paduraru, C., Gowal, S., and Hester, T. (2021). Challenges of real-world reinforcement learning: definitions, henchmarks and analysis. Machine Learning.
[15] Eysenbach, B., Gu, S., Ibarz, J., and Levine, S. (2018). Leave no trace: Learning reset for safe and autonomous reinforcement learning. In International Conference on Learning Representations (ICLR).
[16] Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The generalized linear case. In Neural Information Processing Systems (NeurIPS).
[17] Fujimoto, S., van Hoof, H., and Meger, D. (2018). Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning (ICML).
[18] Garcia, and Fernández, (2015). comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research (JMLR), 16(1):1437-1480

---

[19] Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory (COLT).
[20] Könighofer, B., Bloem, R., Junges, S., Jansen, N., and Serban, A. (2020). Safe reinforce- ment learning using probabilistic shields. International Conference on Concurrency Theory: CONCUR.
[21] Li, L.. Chu, W., Langford. J., and Schapire, R. E. (2010). A contextual- approach to personalized news article recommendation. In International Conference World Wide Web (WWW).
[22] Li, I.., Lu, Y., and Zhou, D. (2017). Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning (ICML), pages 2071-2080.
[23] Melcer, D., Amato, C., and Tripakis, S. (2022). Shield decentralization for safe multi-agent reinforcement learning. In Neural Information Processing Systems (NeurIPS).
[24] Ono, M., Pavone, M., Kuwata, Y., and Balaram, (2015). Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots, 5954):555-571
[25] Paternain, S., Chamon, L.,, Calvo-Fullana, M., and Ribeiro, A. (2019). Constrained reinforce- ment learning has zero duality gap. Neural Information Processing Systems (NeurIPS).
[26] Pfrommer, S., Gautam, T., Zhou, A., and Sojoudi, S. (2022). Safe reinforcement learning with chance-constrained model predictive control. Learning for Dynamics and Control Conference (L4DC), pages 291-303.
[27] Rasmussen, C. E. (2003). Gaussian processes in machine learning. In Summer school on machine learning, pages Springer.
[28] Ray, A., Achiam, J., and Amodei, D. (2019). Benchmarking safe exploration in deep reinforce- ment learning. OpenAl.
[29] Rockafellar, R. T., Uryasev, S., et al. (2000). Optimization of conditional value-at-risk. Journal risk, 2:21-42.
[30] Salimbeni, H. and Deisenroth, M. (2017). Doubly stochastic variational inference for deep Gaussian processes. Neural Information Processing Systems (NeurIPS).
[31] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015). Trust region policy optimization. In International Conference on Machine Learning (ICML).
[32] Sootla, A., Cowen-Rivers, A. I., Jafferjee, T., Wang. Z., Mguni, D. H., Wang, J., and Ammar, H. (2022). Sauté RL: Almost surely safe reinforcement learning using state augmentation. In International Conference on Machine Learning (ICML).
[33] Stooke, A., Achiam, J., and Abbeel, P. (2020). Responsive safety in reinforcement learning by pid Lagrangian methods. In International Conference Machine Learning (ICML), pages 9133-9143.
[34] Strehl, A. L. and Littman, M. L.. (2005). A theoretical analysis of model-based interval estimation. In International Conference on Machine Learning (ICML).
[35] Strehl, L. and Littman, M. (2008). An analysis of model-based interval estimation for Markov decision processes. Journal of Computer and System Sciences, 1309-1130
[36] Sui, Y., Gotovos, A., Burdick, W., and Krause, (2015). Safe exploration for optimization with Gaussian processes. In International Conference on Machine Learning (ICML).
[37] Sun, H., Xu, Z., Fang, M., Peng, Z., Guo, J., Dai, B., and Zhou, B. (2021). Safe exploration by solving early terminated MDP. arXiv preprint
12

---

[38] Thananjeyan, B., Balakrishna, A., Nair, S., Luo, M., Srinivasan, K., Hwang, M.. Gonzalez, J. E., Ibarz, J., Finn, C., and Goldberg, K. (2021). Recovery RL: Safe reinforcement learning with learned recovery zones, IEEE Robotics and Automation Letters, 6()):4155-492..
[39] Thomas, G., Luo, Y., and Ma, T. (2021). Safe reinforcement learning by imagining the near future. In Neural Information Processing Systems (NeurIPS).
[40] Turchetta, M., Kolobov, A., Shah, S., Krause, A., and Agarwal, A. (2020). Safe reinforce- ment learning via curriculum induction. In Neural Information Processing Systems (NeurIPS), volume 33, pages 12151-12162.
[41] Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained Markov decision processes. In International Conference on Machine Learning (ICML).
[42] Wachi, A., Sui, Y., Yue, Y., and Ono, M. (2018). Safe exploration and optimization of constrained MDPs using Gaussian processes. In AAAI Conference on Artificial Intelligence (AAAI).
[43] Wachi, A.. Wei, Y., and Sui, Y. (2021). Safe policy optimization with local generalized linear function approximations. In Neural Information Processing Systems (NeurIPS).
[44] Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2020). Optimism in reinforcement learning with generalized linear function approximation. In International Conference on Learning Representations (ICLR).
[45] Wang, Y., Zhan, S. S., Jiao, R., Wang, Z., Jin, W., Yang. Z., Wang, Z., Huang, C., and Zhu, Q. (2023). Enforeing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In International Conference on Machine Learning, pages PMLR.
[46] Yang, L. and Wang. M. (2019). Sample-optimal parametric Q-earrnng using linearly additive features. In International Conference Machine Learning (ICML).
13

---

Appendices
A Limitations and Potential Negative Societal Impacts
We will first discuss limitations and potential negative societal impacts regarding our work.
A.1 Limitations
One of the major limitations of this study is that emergency stop actions are allowed for agents. Emergency stop actions should often be avoided because of the expensive cost of human intervention in many applications (e.g., the agent is in a hazardous or remote environment). will investigate algorithm that requires the agent to learn reset policy allowing them return the initial state as in [5], rather than asking for human intervention via emergency stop actions.
future work, we
Another limitation is how to construct the uncertainty quantifier. In experiment, because we used a computationally inexpensive deep GP algorithm (30] and the uncertainty quantifier is updated at the end of the episode (see Line 13 in Algorithm[]] [ the computational time of the GP part much smaller than the RL part in our experiment settings. However, since GP is generally computationally expensive algorithm, GP can be computational bottleneck in some cases.
A.2 Potential Negative Societal Impacts
We believe that safety is an essential requirement for applying RL in many real problems. While we have not found any potential negative societal impact of our proposed method, must remain aware that RL algorithms are vulnerable to misuse and ours no exception.
B Proof of Theorem 3.1
We first present lemmas regarding the relationship between the GSE problem and Problems | and 3 After that, we present the proof for the Theorem 3.1 in Appendix B.4 by combining them.
B.1
Relationship between the GSE problem and Problem 1
Lemma B.1. Problem 7 can be transformed into the GSE problem.
Proof. We first utilize safety state augmentation technique presented in Sootla al. 32 by defining a new variable Mh such that
= == ( (11- Σ 2o g(sw. aw)) vh E H].
(4)
hmml
This new variable nh means the remaining safety budget associated with the discount factor Yg. which updated as follows:
1 = 7/=1 (Th g an)) with To = E1.
(5)
By the necessary and sufficient condition for satisfying the constraint in Problem is
Th 2 O, Vh HI.
(6)
By 5 we have
7h+1 2 O, vh E [1, n/ g( an) 2 0, Vh E [].
In summary, by introducing the new variable Th. Problem iss rewritten to the following problem:
max V subject to Prig(sk, an) S mh P. 1, vh H).
(8)
The aforementioned problem is a special case of the GSE problem with b, = Th- Therefore, we obtain the desired lemma.
D
14

---

B.2 Relationship between the GSE problem and Problem 2
Lemma B.2. Problem 2 can be transformed into the GSE problem.
Proof. The following chain of inequalities holds:
E
ig
h 1(sh E Sunsafe)
P,
S
E
9
I(sw Suncate)
P, क
S E2,
wh E [1,
E
[n I(sh E Sunsate)
P
I E2
M I[sw E Sunsate)
P,
vh 12,
M==1
E
[ss Sunsafe) PT
E
g I1(s Sunsafe)
P,
vh [2, HI
Because assume Markov property, we simply define the safety cost function S x A - R as
g(sh, a) = [[ E Sunsafe)
P,T], Va E A.
We now
bn = 7g h E2 E
M I(s E Sunsate) %
P,
h'=1
then the Problem Can be transformed into
Pr(g(s,a) by P, 11
Finally, we obtained the desired lemma.
B.3 Relationship between the GSE problem and Problem 3
Lemma B.3. Problem 3 can be transformed into the GSE problem.
Proof. Set by = Eo for all h. Then, the GSE problem is identical to Problem 3
B.4 Summary
Proof. Combining Lemma B.1
B.2 and B.3 we obtain the desired Theorem 3.1
C Connections to Safe RL Problems with Chance Constraints
As strongly related formulation to Problem 2 policy optimization under joint chance-constraints has been studied especially in the field of control theory such Ono et al. 24 and Pfrommer et al. 26), which is written as
Problem (Safe RL with joint chance constraints). Let Es E R be constant representing safety threshold. Also, let Sunsafe C denote set of unsafe states. Find the optimal policy Æ* such that
Vi A 8h
max, V
subject
Pr
Sunsafe
P, S Es.
Lemma C.1. Problem is conservative approximation Problem
5
15

---

Proof. This lemma mostly follows from Theorem 1 in Ono et al. 224 Regarding the constraint in we have the following chain of equations:
Problem
H Pr [s(sn E Sunsafe
Pr
V h=1
Sunsafe
P,
P.
h=1
E [I(sk Sunsafe)
P,
(9)
H
Σ h=1
(sh E Sunsate)
P, π
(10)
In the first step, used Boole's inequality (i.e., B] P + Pr(B). The final term
in (0)) is the LHS of the constraint in Problem 2 which implies that Problem 2 approximation of Problem Therefore, the GSE problem is also a conservative approximation of Problem
is conservative
n
Corollary C.2. Suppose we solve the GSE problem by properly defining the safety function g(..) and the threshold by- Then, the obtained policy is conservative solution of Problem
Remark C.3. extremely challenging to directly solve the Problem characterized by joins chance-constraints without approximation, discussed in Ono al. (24). Practically, it would be promising and realistic approach to solve Problem by converting it into the GSE problem.
More detailed explanations for the aforementioned remark are follows. It is extremely challenging Most the previous work approximations assumptions. For example, Pfrommer et al. [26] assume known linear time-invariant dynamics. Also, Ono et [24] approximate the joint chance constraint in the above procedure and obtain
to directly solve the Problem characterized by joint does not directly deal with this type of constraint and
H
H
Pr
V
8/ E Sunsafe
P
<
Σ h=1
(ssh E Sunsaate)
P, क
A=1
This is conservative approximation with additive structure, which is casier to solve than the original joint chance constraint. Ono et al. [24] deals with the above constraints with additive safety problem into the GSE
structure. By additionally transforming the problem, the problem would become easier to handle because the safety constraint instantaneous.
D Proof of Theorems 4.1 and 4.2
D.1 Proof of Theorem 4.1
Proof. Recall that, at every time step h, the MASE chooses actions satisfying
p(8n, (n) + [(8h; on.) S by-
(11)
By definition of the d-uncertainty quantifier, the actions that are conservatively chosen based on [1 also satisfy the safety constraint, with probability of least 1 5; that is,
g(5h, an) S b).
(12)
In addition, when there is no action satisfying (II. the emergency stop action is executed; that is, safety is guaranteed with a probability of 1. Hence, the desired theorem now obtained.
D.2 Proof of Theorem 4.2
Proof. Assumption 3.2 implics that there exists a policy that satisfics a more conservative safety constraint written as
g( aA) < bn C, vh E [].
(13)
By combining and the assumption r(s, < ((s E x A, we have p(sh, an) I' an) S g(h, )x) + - bn. wh [1, H),
(14)
16

---

Algorithm 2 GLM-MASE
1:
for episode - 1, do do
2:
for time h = ..... do
Take action an - π (8n) within A 4: Receive reward r(sh, an) and next state sh+1
3:
5:
Receive safety cost (Sh, an) and update safety threshold b
6:
if A = ( then Compute F(5h, an) minsE (3141.a)
7:
8:
Append (sh, ah: F(8h, an), 8h+1) to
9:
break (i.e., emergency stop action a)
10:
else
Append (sh, ah, r(sh, an), 8h+1)
12:
Update 0% and 0% Compute the optimistic Q-estimate
13:
(s, min(V f((0s,a; (R,,)) (s)
Optimize the policy by
(0) Th
(5) = arg max P (8,a).
aEA
15:
Update a(s,a) Cg 11 A7, and then rewrite D
which guarantees that there exists policy that conservatively satisfies the safety constraint via the 5-uncertainty quantifier r) :) at every time step h, with a probability of at least
When we set to be sufficiently large scalar such that c >
V Vmaxx the penalty F satisfies
27
F(8,, an)
-C
mingEA ((sh+1,
15 7 Vina
<->r V Viax-
This means that, when the constraint violation happens even single time, the value by policy obtained in M becomes negative because max, (,7 S Viaax
Under Assumption 3.2 after convergence, the optimal policy in M will not violate the safety constraint, and thus the emergency stop action à will not be executed. In this case, the modified (unconstrained) MDP M is identical to the original CMDP M. Therefore, we now obtain the desired theorem.
E
Supplementary materials regarding GLM-MASE
E.1 Pseudo-code for GLM-MASE
We first present the pseudo-code for GLM-MASE in Algorithm
E.2 Proofs of Lemmas 5.4 and 5.5
Proof. See Lemma 1 (and Lemma 7) in Wang et al. 44
E.3
Preliminary Lemmas
Suppose the assumptions in Lemma 5.4 and 5.3 hold. Let C1 and C2 be positive, universal constants. Also, with sufficiently large T. let t denote the smallest integer satisfying
Lemma E.1.
Anin())H - C1 Ct C2 Cn 2 2. .5-
(15)

---

where Amin(2) is the minimum eigenvalue of the second moment matrix E. Then, we have
r(sh 0/
(0) 11)
1 2 :..
(16)
Proof. By Proposition 1 of Li et. 22
Amin (An,t) 2 Amin -
-
By combining the aforementioned inequality with (15), have
Amin (An,e) 2 Cg 5-1
Using the definition of Amax A
Amnn (' the following chain of equations hold for all
t E ["] and & E H]:
10) : o T(
(1)) C. ||
Cg Amax mit))
C
X (An,))
1
5.
2
Therefore, we have the desired lemma.
E.4 Proof of Theorem 5.6
Proof. By definition, the GLM-MASE chooses actions satisfying f((2))) (h.,)) 1 (0) a,
S bn-
(17)
By Lemma 5.4 the actions that are conservatively chosen based on 17 also satisfy the actual safety constraint, with a probability least ó; that is,
( 2 < by.
(18)
In addition, when there is no action satisfying 17 the emergency stop action is executed where no unsafe action will executed. Hence, the desired theorem is now obtained.
E.5 Proof of Theorem 5.7
By Assumption
3.2 the optimal policy π² satisfies
g(sh, x" (s*)) bn -, Vh E [1. Thus, the set of state-action pairs that are potentially visited by x² are written as
(19)
{ a) E S x g(s.a) s bn - c}.
which satisfies the following chain of inequalities:
{ (s, a) g(s, < by - {} S { (s, p(s,a) a) r(s, a) < bn }} C { (8,a) p(s, a) + [x a) < by }.
The state and action spaces in the last line represent the set of state-action pairs that may be visited by the policy obtained by the MASE algorithm. We used Lemma 5.4 in the first line and I'(s, a) < the second line.
By Lemma 8 in Strehl and Littman
34 the total regret can be decomposed into two parts as follows:
T
Σ
V=
VRL = R(T) + Σ Vmax
(20)
(=)-
where the first term is the regret under the condition that the confidence bound based on 8-uncertainty quantifier successfully contains the true safety function. Also, the second term is the regret under the opposite condition, which occurs with a probability 8.
18

---

The first term in 20 is upper- bounded based on Wang et al. 44 as follows:
R(T) 50 H / (T 8*) In((T - H)
+ Omax
1+ (T t*)
+ HRk
M + K de In
(T +d)dnn
(T - --
d
s S0H ((
As for the second term in (20 set 8 TH
and then we have
Vmx
V
mmax
TH
t=
Σ n
1
?
TH
T Σ H
TH
f= S 0().
In summary, the regret can be upper bounded by Õ(H (T We now obtain the desired
-
theorem.
F Proof of Theorem 6.1
Lemma F.1 (6-uncertainty quantifier). Assume |1g11 < B and N,, for all n 2 Ser
a() Bn (s) a(s.a) S
(21)
with 81/2 = B A Ind where vn is the information capacity associated with kernel k. Then, is 6-uncertainty quantifier.
Proof. Recall the assumption that ||ا1| < B and N, I w, Vn 2 1. Also, set
B1/2 = B 4w Vn Ino-1.
By Theorem 2 in Chowdhury and Gopalan [12]. we have
19(s, a) - nr, (s, a) S 8n, a), (s for all n 2 with probability at least Now, define
a((s.a) Bn (s) V(s.a) ES A
(22)
then we interpret that : A R is 8-uncertainty quantifier based on GP.
F.1 Proof of Theorem 6.1
Proof. Based on Lemma when there least one safe action (i.e., At * 0), the satisfaction of
the safety constraint is guaranteed based on the --uncertainty quantifier with probability at least
8. Also, if there is safe action (i.e., A 0), the emergency stop action is executed. both
cases, MASE guarantees the satisfaction of the safety constraint with probability at least 1 8. D
19

---

Table 1: Hyper- paperrparameters for Safety Gym experiments.
NAME
VALUE
NETWORK ARCHITECTURE
64, 64]
ACTIVATION FUNCTION
tanh
LEARNING RATE (CRITIC)
5 X 10
LEARNING RATE (POLICY)
x
LEARNING RATE (PENALTY)
3 x 10
COMMON PARAMETERS
DISCOUNT FACTOR (REWARD)
0.99
DISCOUNT FACTOR (SAPETY)
0.99
STEPS PER EPOCH
10, 000
NUMBER OF GRADIENT STEPS
80
NUMBER OF EPOCHS
500
TARGET KL
0.01
DAMPING COEFFICIENT
0.1
BACKTRACK COFFFICIENT
0.8
TRPO & CPO
BACKTRACK ITERATIONS
10
LEARNING MARGIN
FALSE
PENALTY FOR EMERGENCY STOP ACTIONS
-1
DEEP GP NETWORK ARCHITECTURE
[16, 16)
MASE
NUMBER INDUCING POINTS
128
KERNEL FUNCTION
RADIAL BASIS FUNCTION
G
Details of Safety-Gym Experiment
We present the details regarding our experiments using Safety-Gym. Our experimental setting is based on Sootla et al. [32], which is slightly different from the original Safety Gym in that the obstacles (i.e., unsafe region) are replaced deterministically so that the environment is solvable and there is a viable solution. In this experiment, we used a machine with Intel(R) Xeon(R) Silver 4210 CPU, 128GB RAM, and NVIDIA A100 GPU. For fair comparison, we basically used the same hyper-parameter as in Sootla et al.
32 which is summarized Table
In our experiment, when the agent identified that there was no safe action based on the GP-based uncertainty quantifier, we simply terminated the current episode (i.e.. resetting) immediately after the emergency stop action and started the new episode. The frequency of the emergency stop actions is shown in Table 2
Table 2: Frequency of the emergency stop actions.
TASK
TOTAL
LAST 100 EPISODES
POINTGOALI
154/500
24/100
CARGOALI
397/500
46/100
The emergency stop action is variant of so-called resetting actions that are common in episodic RL settings, which prevent the agent from exploring the state-action spaces since the uncertainty quantifier is sometimes quite conservative. We consider that this is the reason why the reward performance of our MASE worse than other methods (c.g., TRPO-Lagrangian, CPO). However, because require the agent solve more difficult problems where safety is guaranteed at every time step and episode, we consider that this result is reasonable to some extent. Though it is better for algorithm for such severe safety constraint to have comparable performance CPO, we will leave for future work.
We also conducted an experiment to compare the performance of MASE with the early-terminated MDP (ET-MDP, (37) algorithm. The ET-MDP is an algorithm to execute emergency stop actions immeddaately after safety constraints are violated. Figure shows the experimental results. The ET-MDP and MASE exhibit similar learning curves on the average episode reward and average episode safety. However, while ET-MDP violated the safety constraint in most episodes (i.c., almost
20

---

1852
TRPO
40
(PPO
FTaee
FT MTD
FTuuhe
15
Rean
30
Souan
MAde
25
-22
Opcch
Opczh
Spech
(a) Average episode return.
(b) Average episode safety.
(c) Maximum episode safety.
3.
1#11
165
mino
25
mer
140
25
ETA2P
Saue TRPO
25
Souia TEPO
MDP
120
Soule TRPO
ETAOP
MAGE:
Spech
Spech
(d) Average episode return.
(e) Average episode safety.
(1) Maximum episode safety.
Figure Experimental results on Safety Gym (Top: PointGoall, Bottom: CarGoall) with an additional implementation of the Early-terminated MDP (ET-MDP) algorithm (Sun et al. (77).
all episodes are terminated after an unsafe action is executed), MASE did not violate any safety constraint.
H Grid-world Experiment
We also conduct an experiment using the grid-world problem as in Wachi and Sui [41). Experimental settings based their original implementation battps://githi Safe_near, catearr_pptmammmmaeeeeee
com/ akifumi weshi-wwchh44) We consider 20 x 20 square grid in which reward and safety functions randomly generated. There are two types regarding the safety threshold: one is time-invariant as in [4] and the other is time-variant as in the GSE problem.
We SNO-MDP 41 and MASE in 100 randomly generated environments, and compute the reward collected by the algorithms and count the number episodes which the safety constraint is violated at least once. The reward is normalized with respect to that by SNO-MDP.
Table Experimental results for grid experiments.
TIME-INVARIANT SAFRTY THRESHOLD
TIME-VARIANT SAFETY THRESHOLD
REWARD
SAFETY VIOLATION
REWARD
SAFETY
SNO-MDP 41
1.0 + 0.0
0
1.0 0.0
87
MASE (OURS)
1.000.00 0.0
2.4 1.0
The experimental results are shown in Table 3 When the safety threshold is time- invaiinnai,nt, MASE be- haves identically with SNO-MDP: thus, the performance of the MASE is comparable with that of SNO-MDP. When the safety threshold is time-variant SNO-MDP cannot deal with it by nature: hence, the safety constraint is not satisfied most of the episodes. contrast, our MASE satisfies the safety constraint in every episode, which also contributes to the larger reward.
21


Reviews:
[{"review_id": "NNqSvFZO0J", "reviewer": "Reviewer_sDLd", "summary": "This paper addresses the problem of safe reinforcement learning, in particular safe exploration. In a nutshell, the authors provide an algorithm that is supposed to go beyond standard 'safety' measures in safe RL, such as the constrained MDP setting. There, an agent is bound to satisfy an additional (expected) cost constraint. Here, the authors postulate that an agent must satisfy a constraint almost surely or with high probability. As a key feature of their approach, the authors assume that a so-called  'emergency stop action' is available that allows the agent to always have a fallback. The authors provide a general framework in the form of an algorithm, prove its theoretical guarantees, and evaluate the method on a set of standard benchmarks.", "questions": "1. Compare your approach to the shielding framework.\n\n2. How is the emergency action affecting the agent, please discuss in line with the experiments. \n\n3. How is the 'blocking' of actions realized for an RL agent on a technical level?", "limitations": "The limitations are not properly addressed, see my earlier comments on the evaluation.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The authors tackle a very important problem, safe exploration in RL. Moreover, they identify correctly that the standard constrained RL (or constrained MDP) setting is generally insufficient to ensure safety during exploration. In principle, the constrained RL setting provides just an incentive to act safely during training, and even after training, safety depends on an expectation to satisfy a safety constraint. Generally, the paper is well-written and easy to follow.", "weaknesses": "I like the paper in general, but in its current state cannot be accepted, in my opinion. The reason is a severe lack of related work. Most importantly, the authors seem unaware of a flavor of safe RL that is often referred to as 'shielding.' In these settings, a so-called shield 'blocks' unsafe actions according to some pre-defined safety measure. [1] was the first paper to introduce this aspect, [2] introduced shields for almost-sure properties in partially observable environments, [3] provides shields that satisfy a property with a certain probability, [4] provides a shielding mechanism for multi-agent settings. There are many more relevant works. The general shielding framework depends on varying assumptions, but the general procedure looks like the MASE algorithm. Note that safety during exploration/training is the most important motivation for shielding. I encourage the authors to thoroughly compare these (and more) works to explain the contribution and novelty better.  \n\n[1] Alshiekh et al.: Safe Reinforcement Learning via Shielding. AAAI 2018\n\n[2] Carr et al.: Safe Reinforcement Learning via Shielding for POMDPs. AAAI 2023\n\n[3] Jansen et al.: Safe Reinforcement Learning Using Probabilistic Shields. CONCUR 2020\n\n[4] Melcer et al.: Shield Decentralization for Safe Multi-Agent Reinforcement Learning. NeurIPS 2022\n\nMoreover, I am not convinced by the experimental evaluation. The emergency action seems central to the approach, but I fail to see how it has been integrated into the standard benchmarks. Then, how often is it called during training by the agent? How does it impede an agent's exploration rate? \n\n\nminor comments\n\nl92: In the definition of a policy, it seems to be non-stochastic. In such a multi-objective setting, it might be beneficial to use stochastic policies. Have you considered this? \n\nl 125/126: in a probabilistic setting, there might be states with a high probability of violating a safety constraint but do not already violate it. It could be interesting to consider such information in the value function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer for helpful and thoughtful comments and questions.\n\nFirst of all, please let us emphasize that **our main contributions include the formulation of the GSE problem and its theoretical result (i.e., Theorem 3.1)** as well as the proposal of the MASE algorithm. Our contribution regarding the MASE algorithm is not only on the soundness or novelty of the algorithm itself but also the applicability to a wide range of safe RL problems such as Problems 1, 2, and 3, which is supported by the good theoretical property of the GSE problem backed by Theorem 3.1.\n\nWe will first answer the Questions and then address the comments in Weakness. We will provide responses together for the similar Questions and comments written in Weakness.\n\n**Shielding method [Question 1 and Weakness 1].** Thank you for pointing out related work. We have read all the papers the reviewer raises as examples and notable ones on shielding. As the reviewer mentions, the notion of emergency stop actions is akin to the shielding. We now consider that it would be reasonable to regard our MASE algorithm as a variant of shielding methods (especially, preemptive shielding in [Ref-1]) that is specialized for the GSE problem. On the other hand, the MASE algorithm does not only block unsafe actions but also provides proper penalty for executing the emergency stop actions based on the uncertainty quantifier. Thus, this algorithm provides rigorous theoretical guarantees on optimality (e.g., Theorems 4.2 and 5.7) as well as safety (e.g., Theorems 4.1, 5.6, and 6.1). In particular, under the generalized linear CMDP assumption, our proposed MASE algorithm provides theoretical guarantees on both safety and optimality, which is a unique property from the perspective of safe RL research based on shielding. We can enjoy this theoretical advantage in many safe RL problems because of the wide applicability of the GSE problem. We will discuss the relationship between the shielding method and our MASE algorithm, while properly citing the papers mentioned by the reviewer (i.e., [Ref-2], [Ref-3], [Ref-4]). \n\nIn addition, thanks to the reviewer’s comments, we found that our GSE problem may contribute to bridging the gap between shielding methods and other safe RL methods. We appreciate the constructive feedback.\n\n**Experiment [Question 2-3 and Weakness 2]**. In our experiment, when the agent identified that there was no safe action based on the GP-based uncertainty quantifier, we simply terminated the current episode (i.e., resetting) immediately after the emergency stop action and started the new episode. Also, the frequency of the emergency stop actions is:\n\n|  Task |  total  |  Last 100 epochs  |\n| ---- | ---- | ---- | \n|  PointGoal1  |  154/500  |  24/100  |\n|  CarGoal1  |  397/500  |  46/100  |\n\nThe emergency stop is a variant of so-called resetting actions that are quite common in episodic RL settings, which actually prevent the agent from exploring the state-action spaces since the uncertainty quantifier is sometimes quite conservative. We consider that this is the reason why the reward performance of our MASE is worse than other methods (e.g., TRPO-Lagrangian, CPO) in Figures 2a and 2d. However, because we require the agent to solve more difficult problems where safety is guaranteed at every time step and episode, we consider that this result is reasonable to some extent. Though it is better for an algorithm for such a severe safety constraint to have a comparable performance as CPO, we will leave it for future work. The aforementioned discussion will be useful for the readers, so we will add it to the experiment section in the camera-ready version. \n\n\n**Stochastic policy [Minor comments 1]**. To clarify the contributions of our paper, we focus on the deterministic policy. As the reviewer mentions, however, stochastic policy settings would be beneficial in many cases. We consider that our two core ideas (the GSE problem and the MASE algorithm) are quite simple and intuitive, which can be extended to stochastic policy settings, but the mathematics would be much more complicated.\n\n**Value function incorporating safety [Minor comments 2]**. Thank you for the great advice! It seems a promising idea to pessimistically estimate the value function for the states that are likely to violate the safety constraint. \n\nWe will improve our paper in the final version based on the reviewer’s comments especially on the connections with the shielding method.\n\n---\nReferences\n\n[Ref-1] Alshiekh et al.: Safe Reinforcement Learning via Shielding. AAAI 2018\n\n[Ref-2] Carr et al.: Safe Reinforcement Learning via Shielding for POMDPs. AAAI 2023\n\n[Ref- 3] Jansen et al.: Safe Reinforcement Learning Using Probabilistic Shields. CONCUR 2020\n\n[Ref-4] Melcer et al.: Shield Decentralization for Safe Multi-Agent Reinforcement Learning. NeurIPS 2022"}, {"review_id": "NxQ82zriwN", "reviewer": "Reviewer_Q24U", "summary": "Paper considers the generalized safe exploration problem (problem 4) and compares it to the other safe exploration problems in the literature, leading to Thm 3.1 that concludes that it is more general than the others. The authors then introduce MASE, a meta-algorithm for safe exploration, that attempts to solve the GSE problem with the ability to execute an emergency stop \"beforehand\" as opposed to others that have done it afterwards. Section 6 then presents a more practical algorithm using GP models, which is then used in section 7 to compare the new approach with several baselines.", "questions": "Does the comment about safe RL problems with chance constraints suggest that there is a better answer available already? The text says that problem 5 in App B is hard to solve, but presumably the authors of [20] and [22] did so? Can their results be compared to the ones here?", "limitations": "See little discussion of this point in the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well presented, with several technical results about the safety analysis, culminating in Thms 5.6 and 5.7 which show that GLM-MASE guarantees safety with high probability for every time step.\n\nSeveral numerical experiments are presented to compare with unconstrained and SOA constrained RL algorithms.", "weaknesses": "The development in the paper assumes access to an emergency stop action that enables the agent to avoid violating a safety constraint. This assumptions seems difficult to achieve in practice as for many agents of interest, stopping is not a safe state. Further, the action would typically be state dependent, requiring at a minimum a emergency action policy (rather than action). Finding either action or policy seems non trivial and could possibly be overly simplifying most problems of interest.\n\nGiven the comment about [33] at the bottom of page 4, I would have expected to see a comparison of these approaches to imposing an action to avoid an unsafe state before/after a training epoch in the numerical results. If that is included in section 7, suggest highlight that discussion point more.\n\nThe footnote on page 3 makes reference to this being a conservative approximation of that in safe RL problems with chance constraints, and consigns the discussion Appendix B. It would seem like more clarification than that is needed here. Also, the more recent work by Pavone in this area will be of interest:\n* Lucas Janson, Edward Schmerling, and Marco Pavone, “Monte Carlo motion planning for robot trajectory optimization under uncertainty.” In Robotics Research, pages 343–361. Springer, 2018.\n* Anirudha Majumdar and Marco Pavone “How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics,” https://doi.org/10.48550/arXiv.1710.11040\n\nFig 2 shows that MASE satisfies the constraints, but if I understand the plot correctly, this is achieved with very conservative margins (constraint at 20, values are typical ≤ 5). This is similar to Saute TRPO, but perhaps suggest why the performance (episode return) is so weak compared to the unconstrained solutions (that don’t violate the constraints by much). Is there a way to trade off  this conservatism to achieve better performance?\n\nVery hard to see the frequency with which TRPO Lagrangian violates the constraints given the lines/colors on fig 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer’s valuable comments and feedback. \n\nWe will answer the Questions first and then address the comments provided in Weakness.\n\n**Chance constraint [Question and Weakness 3].** Thank you for the good question! In general, it is known that joint chance constraints represented in Problem 5 are hard to handle. Most of the previous work does not directly deal with this type of constraint and uses some approximations or assumptions. For example, Pfrommer et al. [22] assume a known linear time-invariant dynamics. Also, One et al. [20] approximates the joint chance constraint as follows:\n\n\n\\begin{align}\n        \\Pr \\left[ \\bigvee_{h=1}^{H} s_h \\in S_\\text{unsafe} \\mid P, \\pi \\right] \\le \\mathbb{E} \\left[ \\sum_{h=1}^H  \\mathbb{I}(s_h \\in S_\\text{unsafe}) \\mid P, \\pi \\right].\n\\end{align}\n\nThis is a conservative approximation with an additive structure, which is easier to solve than the original joint chance constraint. One et al. [20] deals with the above constraints with additive safety structure. Remark B.3 implies that, by additionally transforming the conservatively-approximated problem into the GSE problem, the problem would become easier to handle because the safety constraint is instantaneous. As for the comparison with [20] and [22], they assume (partially) known system dynamics; thus, it is not possible to directly compare our method and theirs. We appreciate the reviewer’s comments and questions and the good pointers. We will add more discussion mentioned above in the next version based on the reviewer’s comments.\n\n**Emergency stop action [Weakness 1].** As discussed in Appendix I, emergency stop actions should be avoided in some cases. However, the biggest objective of this paper is to 1) formulate the GSE problem and 2) propose the MASE algorithm for solving it. Emergency stop action is a variant of resetting actions, which have been commonly used in episodic RL literature. The issue in the resetting action has been discussed in general RL problem settings, which have been addressed by many existing RL studies as being represented by [13]. We consider that it is not very difficult to combine our proposed method with such previous work (although we additionally need to incorporate the safety budget to return to the initial state). To clearly convey the core ideas or contributions of our approach, we consider that it is necessary and reasonable to introduce the emergency stop action.\n\n**Early termination [Weakness 2].** Thank you for the good comments. **We conducted an experiment and presented new results in a PDF provided in the global response.** The early-terminated MDP (ET-MDP, [33]) and our MASE exhibit similar learning curves on the average episode reward and average episode safety. However, while ET-MDP violated the safety constraint in most episodes (i.e., almost all episodes are terminated after an unsafe action is executed), our MASE did *not* violate any safety constraint.\n\n**Performance [Weakness 4].** We appreciate valuable comments. As the reviewer mentions, our proposed algorithm is sometimes very conservative since it seeks to guarantee the safety constraint at every time step and episode, while leveraging the uncertainty quantifier. This is the reason why our algorithm performs worse than CPO or TRPO-Lagrangian that encourages safety in a more loose manner, in terms of reward. However, we consider that the main objective of the experiment is to show the validity of our GSE problem and MASE algorithm for which we need to prove that the safety constraint is satisfied empirically consistently with the theory. As the reviewer points out, it would be an important and interesting direction to consider how to balance the trade-off between safety and reward in our GSE problem and MASE algorithm. Although we provide a theoretical result on optimality (Theorem 5.5) under the generalized linear CMDP assumption, we have observed that it is difficult to achieve comparable reward performance to safety-agnostic RL algorithms (e.g., TRPO) or safe RL algorithms with loose constraints (e.g., CPO, TRPO-Lagrangian) in complicated tasks. We would like to leave this issue in the future work. We deeply appreciate the reviewer’s valuable comments.\n\n**TRPO in Figure 2 [Weakness 5].** Thank you for the advice to improve the presentation. We will modify the color and line width so that it is easier to see the result of TRPO-Lagrangian.\n\nWe thank the reviewer for the time and effort on reviewing our paper.\n\n---\nReferences\n\n[13] Eysenbach, B, et al. \"Leave no trace: Learning to reset for safe and autonomous reinforcement learning.\" ICLR (2017).\n\n[20] Ono, M., Pavone, M., Kuwata, Y., and Balaram, J. (2015). Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots,39(4):555–571.\n\n[22] Pfrommer, S., Gautam, T., Zhou, A., and Sojoudi, S. (2022). Safe reinforcement learning with chance-constrained model predictive control. In Learning for Dynamics and Control Conference (L4DC), pages 291–303.\n\n[33] Sun, H., Xu, Z., Fang, M., Peng, Z., Guo, J., Dai, B., and Zhou, B. (2021). Safe exploration by 455 solving early terminated MDP. arXiv preprint arXiv:2107.04200.\n"}, {"review_id": "VNYJpDUixu", "reviewer": "Reviewer_zpL1", "summary": "The authors present a novel safe RL algorithm for safety constraints with probability one. First, the authors present a problem formulation that can be used to derive different common safe RL formulation (state constraints, accumulated constraints etc). Then the authors leverage a sophisticated technique to reshape the reward accounting for safety information. In particular, they predict if the following actions will be safe by learning the action safety state similar to safety shield techniques. Their shields are learning using Gaussian processes and offer safety predictions with uncertainty estimates.`\n", "questions": "1. Please provide details on the safety gym environment. This does not seem like a standard one. \n1. How the algorithm scales with a number of epochs/states? My concern is that the GP is not the most scalable model for RL\n", "limitations": "There are two limitations of the approach: 1) the scalability of the algorithm and 2) the restrictiveness of the problem definition. While the authors discuss the latter limitation and show that this problem formulation is important, I didn’t find a discussion on scalability. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The algorithm is technically sound, novel and quite interesting as an idea.\n1. The authors present an extensive analysis for the case of generalized linear CMPDs. The theoretical results seem to be correct, but I have a few minor concerns regarding the statements \n2. The numerical results are impressive but shown only for one environment. \n", "weaknesses": "1. The statement of Theorem 3.1 reads there are instances of the GSE problem that are not equivalent and cannot be transformed into Problem 1, 2 or 3. This is not shown. \n1. The fact that Problem 2 can be transformed into the GSE problem does not mean the GSE problem is more general than Problem 2. If the GSE problem can be transformed to Problem 2 as well, then they are equivalent. Furthermore, if the accumulated cost is used as a state as in Lemma A.1, then the problems cannot truly be equivalent. I think the authors should rephrase these results and make more accurate claims. \n1. The method does remind me of safety layer techniques [Dalal 18] and [28] with a more sophisticated reward-shaping approach. Can the authors provide a short discussion on the relation to these papers?\n1. The numerical results can be improved \n     * I recommend adding boxplots to the simulation results to see the distributions of the traces. For instance the boxplots of the trajectories for the final epoch as in [28]\n     * I recommend providing more epochs in the experiments. I suspect that the algorithms generally achieve similar performance, but the algorithms with probability one constraint simply converge slower.\n\n* [Dalal 18] Dalal, G., Dvijotham, K., Vecerik, M., Hester, T., Paduraru, C., & Tassa, Y. (2018). Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.08757.\n* [Yu 22] Yu, Haonan, Wei Xu, and Haichao Zhang. \"Towards safe reinforcement learning with a safety editor policy.\" Advances in Neural Information Processing Systems 35 (2022): 2608-2621.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer’s encouraging comments. Your thoughtful comments are valuable and help us to improve the quality of the manuscript.\n\nWe will answer the Questions first and then address the comments in Weakness.\n\n**Safety-Gym [Question 1].** Thank you for the very important question! Our experimental setting is based on the SOTA paper [28]. The Safety-gym environment is slightly different from the original one in that the obstacles (i.e., unsafe region) are replaced deterministically so that the environment is solvable and there is a viable solution. Because this information is important for reproducing our work, we will add the above explanations in the camera-ready version.\n\n**Scalability [Question 2].** Thank you for the valuable question! As the reviewer mentions, in general, GP is a computationally-expensive algorithm. However, computationally scalable GP algorithms have been proposed such as [Ref-1] or [Ref-2]. For example, KISS-GP (w/ LOVE) [Ref-1] requires $\\mathcal{O}(k(n + m \\log m))$, where $n$ is training points, $m$ inducing points, $k$ Lanczos/CG iterations. In our experiment, we used a scalable deep GP algorithm [26] and the computational time of the GP part was much smaller than the RL part in our experiment settings. This is also because of the algorithm setup that the uncertainty quantifier is updated at the end of the episode (see Line 13 in Algorithm 1). As the reviewer points out, since GP can be a computational bottleneck in some cases, we will discuss its potential issue in Limitation.\n\n**Terminology issue in Theorem 3.1 [Weakness 1 and Weakness 2].** We apologize that Theorem 3.1 is miss-leading. We provide Theorem 3.1 to insist that *\"Problems 1, 2, and 3 can be transformed into the GSE problem.\"* Notice that the MASE algorithm can solve the GSE problem. By Theorem 3.1, we can further claim that the MASE algorithm can also solve Problems 1, 2, and 3 since they can be transformed into the GSE problem. Namely, Theorem 3.1 implies that the MASE algorithm is useful in many safe RL problems. The current statement is confusing and over-claiming more than necessary, which hides our real implications; hence, we will rephrase the statement around Theorem 3.1 and make more accurate claims. Thank you for your helpful comments.\n\n**Comparison with [Ref-3], [Ref-4], and [28] [Weakness 3].** As the reviewer mentions, [Ref-3] solves a similar problem to ours. The biggest difference between [Ref-3] and our paper is that [Ref-3] basically assumes that there is always at least one safe action at every time step while our MASE incorporates situations where there is no safe action. Because our MASE algorithm is developed for solving the GSE problem characterized by a time-varying (potentially decreasing) safety threshold $b_h$, we need to carefully consider the case where there is no safe action. The advantage of the MASE compared to [Ref-3] is that it can deal with such hopeless cases by the emergency stop action and reward penalty based on the uncertainty quantifier, while maintaining the theoretical guarantees on safety and (optimality under the Generalized linear CMDP assumption). Next, [Ref-4] tries to solve typical safe RL problems with expected cumulative safety constraints; thus, it is essentially difficult to guarantee the safety constraint in the GSE problem and Problems 1, 2, and 3. Finally, while [28] deals with the so-called probability one constraints (i.e., Problem 1 in our paper), their algorithm heavily penalizes the agent after the constraint violation. Their proposed algorithm is nice in that safety after convergence is guaranteed, but safety is not guaranteed during the learning phase by nature. An advantage of our MASE compared to theirs is that safety is guaranteed even during learning, which is evidenced by both theoretically and empirically.\n\nNote that, we thought the reviewer may have miswritten [Ref-4] as [28] and gave the above response.\n\n**Numerical results [Weakness 4].** Thank you for the useful comments. We conducted an additional experiment results with boxplots for a larger epoch (500 $\\rightarrow$ 1000). **We would like to ask the reviewer to see the new result in a new PDF file attached in the global response.** Because we consider that it is more important to show the performance in terms of reward and safety during learning, we show the current learning curve. As the reviewer mentions, however, the boxplots would be definitely useful to see the final performance and we will add such plots as the new figure (i.e. Figure 4 in a PDF attached in the global response). \n\nWe sincerely thank the reviewer for taking the time to review our paper.\n\n---\nReferences\n\n[26] Salimbeni, H. and Deisenroth, M. Doubly stochastic variational inference for deep Gaussian processes. In Neural Information Processing Systems, 2017.\n\n[28] Sootla, Aivar, et al. \"Sauté rl: Almost surely safe reinforcement learning using state augmentation.\" International Conference on Machine Learning. PMLR, 2022.\n\n[Ref-1] Wilson, A, and Hannes N. \"Kernel interpolation for scalable structured Gaussian processes (KISS-GP).\" International conference on machine learning. 2015.\n\n[Ref-2] Pleiss, G, et al. \"Constant-time predictive distributions for Gaussian processes.\" International Conference on Machine Learning. 2018.\n\n[Ref-3] Dalal, G., Dvijotham, K., Vecerik, M., Hester, T., Paduraru, C., & Tassa, Y. (2018). Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.08757.\n\n[Ref-4] Yu, Haonan, Wei Xu, and Haichao Zhang. \"Towards safe reinforcement learning with a safety editor policy.\" Advances in Neural Information Processing Systems 35 (2022): 2608-2621\n"}, {"review_id": "V8iaFEZZDH", "reviewer": "Reviewer_pGdw", "summary": "This paper studies the safe RL problem with a generalized stepwise safety chance (probability) constraint, essential for many safety-critical systems with RL. The authors propose a meta-algorithm to solve this problem (MASE), by combining unconstrained RL with an uncertainty quantifier to guarantee safety with probability. They study two variants for MASE, one for the linear model and the other for GP. Experiments on grid-world and safety gym show that MASE with GSE formulation achieves SOTA compared to the baselines. ", "questions": "1. Page 3 Lines 96 to 98, although I can understand what the authors mean, we should always keep in mind that s_h (a_h) are random variables, you cannot let a random variable be less than a value. It has to be in Pr() format, even if the probability is 1.  ", "limitations": "I would like to see the authors' opinions on the limitations in their responses. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow. The proposed GSE problem is more general than the CMDP formulation with an additive expectation constraint. Especially, the GSE problem is an important problem to study for many real-world safety-critical systems, such as autonomous cars and cars. \nThe proposed method looks sound and correct to me. \nThe MASE algorithm essentially builds on Assumption 3.4 (uncertainty quantifier) which could also be a potential bottleneck or limitation, but the author did a good job by proposing a general linear model and GP for it. \nThe experimental results show better results in terms of safety violations, compared to other CMDP-based approaches. ", "weaknesses": "1. The author may want to at least discuss this ICML paper in their related work. The hard safety chance constraint is highly relevant to the GSE problem in this paper, although it is indeed using different approaches to solve the problem. \nWang, Y., Zhan, S. S., Jiao, R., Wang, Z., Jin, W., Yang, Z., ... & Zhu, Q. (2022). Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments. arXiv preprint arXiv:2209.15090.\n\n2. The authors should discuss the limitations of this work\n\n3. In Method, MASE needs to compute a safe action set, how complex this computation is? In order to compute it, what kind of assumptions of the underlying environments do you acquire? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer’s encouraging comments. Your feedback and suggestions are valuable and help us improve the quality of the manuscript.\n\nWe will first answer the Question and then address the comments regarding Weakness.\n\n**Lines 96 - 98 [Question].** Thank you for the important question! As the reviewer mentions, we should have paid more attention to the fact that $s_h$ and $a_h$ are random variables. We will fix them in the camera-ready version.\n\n**Missing reference [Weakness 1].** Thank you for pointing out the closely-related work. Indeed, the existing work [Ref-1] the reviewer points out formulates their problem in a highly-relevant manner to the GSE problem. We will discuss this existing work as a closely-related research.\n\n**Limitations of the work [Weakness 2].** Due to the severe page limit, we discuss the limitations of our paper in the supplementary material (Appendix I). As the reviewer mentioned, however, the limitations should be discussed in the main paper and it would be better to discuss other limitations such as computational cost. We will move this part to the main paper in the camera-ready version while adding more descriptions.\n\n**Complexity [Weakness 3].** In our proposed method, a safe action set is computed based on the inference by uncertainty quantifier (e.g., GP). In our practical implementation, since each GP inference is computationally inexpensive and we require the agent to update the GP model only at the end of the episode (see Line 13 in Algorithm 1), dominant computational time depends on the number of actions used for the GP inference. In the case of RL problems with discrete action, the computational cost is proportional to $|A|$. When the action space is continuous, it would be more difficult to compute the safe action set and a sampling technique is a simple yet powerful solution. In fact, when we conducted our experiment, we randomly sampled next actions and checked whether or not there were actions that conservatively guarantee the safety constraint. The computational cost of this process is practically smaller than the main RL process. We should have explained the details of the practical implementation, so we will address the reviewers’ comments in the next version.\n\nWe sincerely thank the reviewer for taking the time to review our paper.\n\n---\nReference\n\n[Ref-1] Wang, Yixuan, et al. \"Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments.\" International Conference on Machine Learning (ICML)., 2023."}]

Author rebuttal:
Dear reviewers and AC,

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

- We have conducted new experiments based on the reviewers' comments. Additional experimental results are provided in a one-page PDF containing new figures attached in this "global" response. 

- We have provided our detailed response to each reviewer with a separate response.

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

Best regards,

Authors.


Meta-review: The paper defines a novel "generalized safe exploration" problem and gives a meta-algorithm for the problem that combines an unconstrained RL algorithm with an uncertainty quantifier. The problem is interesting and the technical results are sound and novel. While there were some concerns about the discussion of related work and experiments in the original paper, the new results and clarifications added during the discussion period addressed them. Given all this, I am recommending acceptance.  Please incorporate the reviewers' feedback carefully in the final version.
Decision: Accept (poster)