Finding Safe Zones of Markov Decision Processes Policies
Authors: Lee Cohen
Yishay Mansour
Michal Moshkovitz
Venue: NeurIPS 2023 poster (2023)
Keywords: Theoretical guarantees
algorithms
learning theory
MDP
computational complexity
Interpretability

Abstract: Given a policy of a Markov Decision Process, we define a SafeZone as a subset of states, such that most of the policy's trajectories are confined to this subset. The quality of a SafeZone is parameterized by the number of states and the escape probability, i.e., the probability that a random trajectory will leave the subset. SafeZones are especially interesting when they have a small number of states and low escape probability. We study the complexity of finding optimal SafeZones, and show that in general, the problem is computationally hard. For this reason, we concentrate on finding approximate SafeZones. Our main result is a bi-criteria approximation learning algorithm with a factor of almost $2$  approximation for both the escape probability and \newprob size, using a polynomial size sample complexity.

Finding Safe Zones of Markov Decision Processes Policies
Lee Cohen TTI-Chicago
Yishay Mansour Tel-Aviv University
Michal Moshkovitz Bosch Center for AI
Google Research
Abstract
Given policy of Markov Decision Process, we define SAFEZONE subset of states, such that most of the policy's 's trajectories are confined to this subset.
The quality of SAFEZONE is parameterized by the number of states and the escape probability, i.c. the probability that a random trajectory will leave the subset. SAFEZONES are especially interesting when they have small number states and low escape probability. We study the complexity of finding optimal SAFEZONES, and show that in general, the problem is computationally hard. Our main result is bi-criteria approximation learning algorithm with factor of almost 2 approximation for both the escape probability and SAFEZONE size, using a polynomial size sample complexity.
Introduction
Most research in reinforcement learning (RL) deals with learning an optimal policy for some Markov Decision Process (MDP). One notable exception to that is Safe RL which addresses the concept of safety. Traditional Safe RL focuses on finding the best policy that meets safety requirements, typically by either adjusting the objective to include the safety requirements and then optimizing for it, or incorporating additional safety constraints to the exploration. safety requirements should be pre-specified. Anomaly Detection is the problem of identifying patterns in data that are unexpected, i.e., anomalies (see, e.g., Chandola et al. (2009) for survey). This paper introduces the SAFEZONE problem, which addresses the safety of specific Markov decision process (MDP) policy by detecting anomalous events rather than finding a policy that satisfies some pre-defined safety constraints.
both of these cases, the
Consider finite horizon MDP and policy (a mapping from states to actions). The policy induces Markov Chain (MC) on the MDP. Given a subset of states, a trajectory escapes it if at least one of its states not in the subset. The escape probability of subset is the probability that randomly sampled trajectory will escape it. A SAFEZONE is subset of states whose quality is measured by (1) its escape probability and (2) its size. If a SAFEZONE has low escape probability, we consider it safe (hence escaping is the anomaly). We emphasize that safety is policy-dependent and that different policies could have different SAFEZONES.
Trivial solutions for SAFEZONE include the entire states set (minimal escape probability of O. maximal size), and the empty set (minimal size, maximal escape probability of 1). The goal is to find a SAFEZONE with good balance: relatively small size but still safe enough (small escape probability). More precisely, given an upper bound the escape probability, p >>> O, the goal of the learner is to find the smallest SAFEZONE with escape probability at most using trajectory sampling. We address an unknown environment, by which we mean no prior knowledge of the transition function or the policy used. The learner is only given access to random trajectories generated by the induced Markov chain. For many applications, a small SAFEZONE exists, it is useful find it.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One such example is designing a policy for a smaller state space that performs well in most cases but is undefined for some states, or formally, imitation learning with compact policy representation Abel et al. (2018) 8); Dong et al. (2019). Suppose a company would like to automatically generate a "lite" edition of software or an app (e.g., Microsoft Office Lite, Facebook Lite) that contains only part of the system's 's states, finding SAFEZONE makes lot of sense- capturing popular users' trajectories. If instead of finding SAFEZONE, , one were to simply take the 90% most popular states of users using Office, they might not include the state that allows for the precious option of saving, which emphasizes the importance of the problem.
Another motivation for the problem is autonomous vehicles and specifically infrastructure design for them. Even though a lot of the progress in the field of autonomous driving credited to sensors installed on the vehicles, relying solely on the vehicles' sensors has its limitations (c.g.. Yang et al. (2020). ). In extreme weather, vehicle might unintentionally deviate from the current lane and the vehicle sensors might not trigger a response in time. communication network between vehicles and road infrastructures that are designed to fill the need for an extra layer of safety | An important part of the V2I communication is based on Road Side Units (RSUs), sensors that are installed alongside roads. Together with the sensors that are installed on the vehicles, they span the V2I communication. As the resources for RSUs distribution are limited and their enhanced safety is key for V2I and the autonomous vehicle adaptation, distributing RSUs in states of a (good) SAFEZONE could enhance the safety of popular commutes efficiently. Namely, given data regarding commutes (trajectories) in an area, installing RSUs in its' SAFEZONE states will ensure increased safety measures of major part of the commutes, from starting point to destination, and potentially increase the trust in the system. In addition, if regulation were to prevent people from making autonomous commutes outside of the SAFEZONE, having most of the autonomous commutes confined to the SAFEZONE implies that most commutes can still be driverless.
(V2I) is type of
Another useful application is automatic robotic arms that assemble products. If something unusual happened during the assembly of a product, it might result in a malfunctioning product, and that case, the operator should be notified (anomaly detection). On the other hand, it is not really autonomic the operator is notified too frequently. If we find a 'safe enough' SAFEZONE, we can make sure that we notify the operator only in the rare event the production process (trajectory) escapes it, which means that something went wrong with the product assembly. Furthermore, if the SAFEZONE is small, the manufacturer can potentially test the SAFEZONE states and verify their compliance, ensuring that the majority of products are well constructed for a significantly lower testing budget.
Finally, the SAFEZONE problem can be viewed through the lens of explainable RL, where the goal is to explain a specific policy. SAFEZONE is a new post-hoc explanation of the summarization type Alharin et al. (2020). For example, for the autonomous vehicle infrastructure design, governments could explain to their citizens the design that was chosen.
Our results include approximation algorithms for the SAFEZONE problem, which we show is NP-hard. We are interested in good trade-off between the escape probability of the SAFEZONE and its size. Our algorithms are evaluated based on two criteria: their approximation factors (w.r.t. the escape probability bound and the optimal set size for this bound), and their trajectory sample complexity bounds (e.g.. Even- -ar et al. (2006)).
In Section we formalize the SAFEZONE problem. In Section 3 we explore naive approaches, namely greedy algorithms that select SAFEZONES based on state distributions and trajectory sampling. In addition, we show particular cases in which their solutions are far from optimal. either in terms of high escape probability or significantly larger set size. In Section 4 we design FINDING SAFEZONE, an efficient approximation algorithm with provable guarantees. The algorithm returns a SAFEZONE which is slightly more than twice the size and twice the escape probability compared to the optimal. While the main focus of this work is the introduction of the problem and the aforementioned theoretical guarantees, we do demonstrate the problem empirically. to provide additional intuition to the readers. In Section 5 we compare the performance of the naive approaches to FINDING SAFEZONE and show that different policies might lead to completely different SAFEZONES. In Appendix A
Contribution:
we show that the problem is hard, even for known environment
'The 'V21 Deployment Coalition" is an initiative by the U.S Department Transportation with the vision of "An integrated national infrastructure that provides the country a connected, safe and secure transportation system taking full advantage of the progress being made in the Connected and Autonomous Vehicle arenas." http:/uuwwuuuuuaaoooooo////////o
2

---

setting, namely even when the induced Markov chain is given, finding SAFEZONE is NP-hard, even for horizon H = 2.
For brevity, some algorithms and (full) proofs are relegated to the appendix.
1.1 Related Work
MDPs have been studied extensively in the context of decision making in particular by the Reinforce- ment Learning (RL) community (see Puterman (994) for broad background on MDPs, and Sutton & Barto (2018) 8) for background on reinforcement learning).
Safe RL A related line of research is safe RI., where the goal of the learner is to find the best policy
that satisfies safety guarantees. The two main methodologies to handle such problems are: (1) altering
the objective include the safety requirement and optimizing over it, and (2) adding additional safety
constraints to the exploration part. See Pfrommer et al. (202 Emam et al. (2021) Xu et al. (2021)
Hendrycks et 2022]) HasanzadeZZonuzy
al. (2021 I ; Bennett
(2023 y Prajapat al. (2022) ;
Liu et al. (2022) for recent works and García & Fernández 20:5); Amodei et al. (2016) for surveys.
Recent work by Sootla et al. (2022) augments the environment accommodate some pre-specified
safety constraints and thus satisfies them almost surely. In our work, the goal is not to find the optimal
policy, but rather, given a policy, finding its SAFEZONE. The SAFEZONE is not characterized by
specific requirements, and might not be unique. Moreover, beyond the MDP, the solution very much depends on the policy.
Imitation Learning. In imitation learning, the learner observes a policy behavior and wants to imitate it (see Hussein al. (2017) for survey). Similar imitation learning, are given access to samples of a given policy. In contrast, rather than imitating the policy we find the policy's SAFEZONE, which is an important property of the policy.
Approximate MDP equivalence. Another related research line is that of finding an (almost) equivalent minimal model for given MDP, where the goal is that the optimal policy on the (almost) equivalent model induces an (approximately) optimal policy in the original MDP, e.g., Givan et al. (2003); Even- Dar& & Mansour (2003). This line of works and ours differ in that we do not try to modify the MDP (e.g.. cluster similar states), but rather to find a SAFEZONF, a property that is defined for the existing MDP and a specific policy.
Explainability. In explainability, the goal is to provide a post-hoc explanation to a specific (given) model Molnar (2019), e.g., using decision trees Blanc et al. 2022);; Moshkovitz et al. I) influential examples Koh & Liang (2017), or local approximation explanations Li et al. (2020). We focus explainabilityy for reinforcement learning, and specifically, suggest a new summarization explanation through our SAFEZONE (Amir & Amir 2018).
2 The Safe Zone Problem
We model the problem using a Markov model with a finite horizon H > 1. Formally, there Markov chain (MC) (S, P, where is the set of states, 50 S the initial state, and P: P:SK x S + [0, 1] is the transition function that maps pair of states into probability by P(s, s') Pr[se+1- = =s(s; = s). We assume the transition function P induced by a policy : S - Simplex
on an MDP (S, 80. P', .A) with transition function P' S x x S + [0, 1] such that s(s,s') = EaeA P'(s, a, s') (als) for all s, s E S (though any MC can be generated this way, thus our theoretical guarantees apply for general MCs).
8H) starts in the initial state so and followed by a sequence of H states generated by P, i.e., Pr Prisi+1 s'Is: s] = P(s, s') for all i E [H], where [H] := (1,..., H). For example, in the context of autonomous vehicles, the trajectory is a commute. We abuse the notation and regard a trajectory 7 both as a sequence and a set.
A trajectory T
Given a subset of states F C S, a trajectory T escapes F it contains at least one state s E T such that 8 & F, i.e., E F. For example, if commute passes through at least one area (state) that does not have an RSU sensor, it escapes the SAFEZONE. We refer to the probability that a random trajectory escapes F as escape probability and denote it by A(F) = Pr-[r g F). We call F p-safe (w.r.t the model (S, so: P)) if its escape probability, A (F)), is at most p. Formally,
Definition 2.1. A set F C S is pasafe if A(F) == [T Z F] S p, where is random trajectory.
3

---

A set F " S is called (p. SAPEZONE if F is p safe and |F| I k. Given a safety parameter p E (0, 1), we denote the smallest size p safe set by k- (p):
min k*))) rgs is p-
14
Whenever the discussed parameter p is clear from the context we use k* instead of k- (p). We remark that there might be multiple different (p. SAFEZOEE sets. The learner knows the set of states, S. the initial state, So, and the horizon H. However, the transition function P and the minimal size of the p-safe set, k., are unknown to the learner. Instead, the learner receives information about the model from sampling trajectories from the distribution induced by P.
Given P O, the ultimate goal of the learner would have been find (p, (p)))SAFEEZONE
However, as we show in Appendix A, finding a (p. k" (S))=SSAEZZONE is NP-hard, even when the transition function P is known. This is why we loosen the objective to find bi-criteria approximation - (Bi-criteria approximations are widely studied in approximation and online algorithms Vazirani (2001); Williamson & Shmoys (011T) ,) In our setting, given p the objective is to find a set /' which is - SAFEZONE with minimal size k' 2 k- and minimal escape probability p' 2 p. In addition, we are interested in minimizing the sample complexity.
Notice that the learner can efficiently verify, with high probability, whether a set F is approximately formalize in the next proposition. The following proposition follows directly
p --safe or not,
from Lemma C.2
Proposition 2.2. There exists an efficient algorithm such that for every set F C S and parameters e, x > O, the algorithm samples O 2 In }) random trajectories and returns (FF), such that with
probability at most we have [AF)) - ((F)
2.1 A Note on Trajectory Escaping
The SAFEZONE problem deals with escaping trajectories. In particular, given a SAFEZONE, a trajectory escapes it, no matter if only one of its states is outside the SAFEZONE or all of them. A related, yet very different problem, is that of minimizing a subset size, such that the expected number of states outside the set is minimized. This related problem, while significantly easier (as it is solved by returning the most visited states), does not apply to the applications we described earlier. For example, consider the infrastructure design for autonomous vehicles. We want passengers to have safe experience end-to-end. Hence the entire route must have that extra security layer provided by the RSUs. In Section 3 we show that the solution for the SAFEZONE does not necessarily overlap with the most visited states. Furthermore, simply returning states that appeared in trajectory samples could result set size far from optimal.
2.2 A Note on Multiple Policies
Our framework can accommodate an arbitrary number of policies, representing multiple agents. This is made feasible through the implementation of a single mixed policy. This mixed policy is designed to stochastically select a policy from this ensemble of policies, uniformly at random or according to any specified distribution over the participating agents and their respective policies.
2.3 Summary of Contributions
We summarize the results of all the algorithms that appear in the paper in Table The bounds of GREEDY BY THRESHOLD and GREEDY AT EACH STEP require the Markov Chain model as input, and a pre-processing step that takes O([S)²H) time. Additionally, the bounds for the first three algorithms (the naive approaches) require additional knowledge of l (p). The sample complexities of SIMULATION is bounded by poly(k" }), and of FINDING SAFEZONE Algorithm is bounded by
poly(k", H, 3, })) for some parameters e, E (0, 1).
Beyond the upper bounds, we provide each of the first three algorithms (the naive approaches) instances that show that they are tight up to a constant.
The following theorem is an informal statement of our main theorem, Theorem Theorem 2.3. For every p,E, > O, with probability > 0.99 there exists algoritim that returns set which is (2p + 2e, (2 + 8)k* - SAFEZONE.

---

In addition to the sample complexity, the run- ning time of the algorithm is also bounded by poly(k", H, 3:
Table 1: Upper bounds for safety and size. Only for layered MDPs.
We empirically evaluate the suggested algo- rithms on grid-world instance (where the goal is reach an absorbing state), show- ing that FINDING SAFEZONE outperforms the naive approaches. Moreover, we show that different policies have qualitatively dif- ferent SAFEZONES. Finally, an informal statement of Theorem [ which appears in Appendix A due to space limitations.
Algorithm
Safety
Set Size
Greedy by Threshold
2p
k² k'Hpp
Simulation
2p
O(k" H k*)
Greedy at Each Step*
pH
k*
Finding SAFEZONE
2p + 2c
(2 + 8)k*
Theorem 2.4. SAFEZONE is NP-hard.
Gentle Start
This section explains and analyzes various naive algorithms to the SAFEZONE problem. We show that even if the transition function is known in advance, these naive algorithms result in outputs that far from optimal. To describe the algorithms,
define for each state the probability to appear in a random trajectory and denote by p(s) = Pr E r] E [0, 1]. Note that >.es P(s) is a number between 1 and (e.g.. p(su) = 1), and can be estimated efficiently using dynamic programming the environment and policy known and sampling otherwise. To be precise, some of the algorithms assume the probabilities {p(s)>ees are received as input.
Greedy by Threshold Algorithm. The algorithm gets, addition p, the distribution p and parameter B > 0 as input. It returns a set F that contains all states with probability at least i, i.e., p(s) B. We formalize this idea Algorithm in Appendix B For 3 f. the output of the
algorithm is (2p. K" SAFEZONE. More generally, we prove the following lemma.
Lemma 3.1. For any p.3 3 E (0,1), the GREEDY BY THRESHOLD ALGORITHM returns a set that is (p + 33 ) SAFEZONE. In particular, for B f-, this set (2p, k'H
SAFEZONE.
While it is clear why there instances for which the safety is tight, Lemma B.1 in Appendix B shows that the set size is tight as well.
Simulation Algorithm. The algorithm samples O In with all the states in these trajectories. It is formalized in Appendix Blas Algorithm 4
"1 random trajectories and returns a set F
Lemma 3.2. Fix B. E (0, With probability at least 0.99, SIMULATION Algorithm returns a set that (p (p+ k 3,0(KK* pH =))))))) SAFEZONE. particular, for 3 = f.. this set is (2p, O(K H kn SAFEZONE.
While the algorithm achieves low escape probability, only 2p, in Lemma B.2 in the appendix we prove that the size of F is tight up to constant, i.e., we show an MDP instance where FF| = Ω(k* H In k*). The algorithms presented so far approximately safe (i.e., low escape probability). but the returned set size was large. Without any further assumptions, the following algorithm provides (pli, " -AFE-AEE thus not improving the previous algorithms. However, when considering MDPs with a special structure it provides an optimal sized SAFEZONE. at the price large escape probability.
Greedy at Each Step Algorithm. For the analysis of the next algorithm, we assume the MDP is layered, i.e., there are no states that appear in more than single time step and denote S U S, Le., the transitions P(s, 8') are nonzero only for s' E S.+1 and s E S,. The GREEDY AT EACH STEP ALGORITHM, sometimes simply called greedy, takes at each time step i the minimal number of states such that the sum of their probabilities is least p. It is formalized in Appendix B as Algorithm 5
5

---

Lemma 3.3. For any p E 1). if the MDP is layered, GREEDY AT EACH STEP ALGORITHM returns a set that is (pH, k-) SAFEZONE.
In Lemma B.3 in the appendix we provide a lower bound on the escape probability, matching up to a constant.
Weaknesses of the naive algorithms. We showed algorithms that identify SAFEZONE with escape probability much greater than p or size much greater than k*, and instances with tight lower bounds for each of them. This holds even when providing extra information about the model or the optimal size of the p-safe set, i.c., k..
4 Algorithm for Detecting Safe Zones
In this section, we suggest a new algorithm that builds upon and improves the added trajectory selection of the SIMULATTOO Algorithm. One reason for why SIMUL.ATION returns large set is that it treats every sampled trajectory identically, regardless of how many states are being added, which could be large as H. More precisely, fix any - trajectory r that escapes it, i.e., z F² If T was sampled, its states are added to the constructed set F, which might increase the size of F by up to states that are not in F", without significantly improving the safety. In contrast, when selecting which trajectory to add to F, we would consider the number of states adds to the current set. For the sake of readability, we refer to any state which is not in the current set F as new, and denote by newr(r) the number of new states in 7 w.r.t. F, i.e.,
set, F", and consider
newp(T) |r Fl.
Note that for every F S S, Pr, (n) 0] A(F).
The new algorithm does not sample each trajectory uniformly at random, but samples from new distribution, which will be denoted by Qr-
While favoring trajectories with higher probabilities, which we already get by the sampling process, another key idea would guide this new distribution: To prefer trajectories that gradually increase the size of F. To implement this idea, we will ensure that the probability of adding a trajectory T F should be inversely proportional to (Tw
Formally, the support of QF is the trajectories with new states, i.e., X (r|newp(T) # 0). For every 7 E X
QF(T) Pr[T] (T)
where Pr[r] is the probability of trajectory under the Markov Chain with dynamics P. Note that the new distribution depends on the current set F, and changes as we modify it. Intuitively, adding trajectories to F according to QF instead of adding trajectories sampled directly from the dynamics (as we do in SIMULATION) would increase the expected ratio between the added safety and the number of new states we add to F, thus improving the set size guarantee of the output set. We elaborate on this in Section 4.2
Our main algorithm FINDING AFFEZONE, Algorithm T The algorithm receives, in addition to the safety parameter p. parameters e, À (0, 1). and maintains set F' that is initiated to {so}. On high level, to implement the idea of adding trajectories to F' according to QF, we use rejection sampling. Namely, in each iteration of the while-loop we first sample trajectory т, and if new (T) o we accept it with probability 1 (/newp(T). If the trajectory is accepted, it is added to F. More precisely, if ((e)((T)))))) & O, we sample Bernoulli random variable, accept Br(1/ Br(1/neww( (n))w())) If accept 1, we add 7 to F. This process of adding trajectories to F generates the desired distribution, QF- Whenever a trajectory is added to F, we estimate the escape probability ((F) (W.rt. the updated set, F).
The algorithm stops adding states to F and returns it output when it becomes "safe enough". To be precise, let Â (F) denote the result of the escape probability estimation (by sampling trajectories as suggested in Proposition 2.2) If A (F) < 2p + e, means that F is (2p + 2+)-2)))) -sae with probability X, in which case the algorithm terminates and returns F as output.
> Xj
To implement the estimation Â(F), the algorithm calls EstimateSafery Subroutine. The subroutine samples N, = O In 2) trajectories, and returns the fraction of trajectories that escaped F.

---

and the For cases in which the transition function P is known to the learner we provide an alternative implementation for EstimateSafety which computes the exact probability (F)) (see Lemma E. in Appendix
Algorithm 1 FINDING SAFEZONE
Algorithm 2 EstSafery Subroutine
Input: E (0,1)
Input: subset F Parameters:
Parameters: 6, 10
(0,1)
F + {50).} - (FF) +-
((F)
while ((F) > 2p + do
1 In A trajectories T + sample N, = 22
7 + sample random trajectory
for E do
Compute (Tw
i g F then
if ( + then
+ N
sample accept ~ Br(1/newp(T))
end if end for return ((F)
if accept then
F UT
Aj - } (FF) + Est
end if end if end while
return
4.1 Algorithm Analysis
We define the event & = (Vi (P A(F;-1) S e),
which states that all our ExtimateSafety Subroutine estimations are accurate. show that holds with high probability using Hoeffding inequality. In most of the analysis, condition on & to hold.
The following theorem is the central component in the proof of the main theorem that follows it.
Theorem 4.1. Given p. e, E (0, 1), FINDING SAFEZONE Algorithm returns subset F C succh that:
1. The escape probability is bounded from above by A(F) 2p 2e, with probability - A.
2. The expected size of F given & is bounded by E| E] S 2k*
3. The sample complexity of the algorithm is bounded by O
k- In
Hk* ph
xe
running time bounded by O Hk" +
In Xe2
H²k') Aa with probability 1 X.
To obtain the main theorem, we run FINDING SAFEZONE, Algorithm several times and return the smallest output set, F, see the next section for more details.
Theorem 4.2. (main theorem) Given e, p,5 0, if we run FINDING SAFEZONE for O()) times and return the smallest output set, F C S, then with probability 2 0.99
1. The escape probability is bounded by 4(F) 2p 2c.
2. The size F is bounded from above by |F] < (2 + 5)k-
3. The total sample complexity and running time are bounded by O In k'
HK* 0 and
52.2 8
0 Hk 87
In K-" +
H²*" p8
respectively.
Finding an almost sa-e SAFEZONE. nearly 2 in size can be valuable. For example, it enhances the safety of popular commuting routes, promotes trust in autonomous vehicles, and aligns with potential regulatory restrictions, making most commutes driverless within this secure zone. Regarding sample complexity, we expect the dependency on he to be nearly optimal. The reason why the following, Consider an induced MC with A* trajectories of size 2, each starting from initial

---

state s", ends with unique corresponding state I,....k* 1, and has a probability of !ー If the MC has significantly more than & states with non-zero probability, it would take at least K - 1 samples find (p, S-AAAAZE As for the parameter this could be treated constant. For example, selecting 1/3 yields that we need to run the algorithm 6 In 300 times and solution of size 7/3k" w.h.p.
4.2 Proof Technique
Escape Probability Set Size Bounds. To case the presentation of the proof, we assume that ((P) A(P). For full proofs, we refer to Appendix C This case is interesting on its own since the policy and transition function
known, we can compute A(F) efficiently using dynamic programming (see Appendix E). As a result, event & always holds. In addition, is clear that the
termination of the algorithm implies that ((F)= (FF) v challenge bounding |F|-
2p, thus F is (2p + 26)- safe. The main
A few notations before we start. Let J denote a minimal p-safe set (of size k*), Consider iteration inside the while-loop. The random variable (F) is the number of states in F that are added to F in iteration i and (F) is the number of states added to F in iteration i that are not in F (G stands for good and for bad). For ease of presentation, from here on we write G, and B, instead of (F) and (F), respectively. Notice that the size of the output set is exactly Σ, B, + G, and that G.G. k.
The main idea of the proof technique is to show that by adding trajectories according to the new distribution Qr, ensure that, in expectation, there at least many good states that are added to F as bad states. Suppose the trajectory T was chosen to be added to F by the algorithm. If C F", then G; is equal to new (T) and B; O. If Z F*, then B; S new (T). Summarizing these observations, we have the following bounds
G Z newp(T) [[[T C F*) and B; S new 1/7 & F*),
where I[[| is the indicator function.
Moreover, direct consequence of the probability in which is added to F is that for any set of trajectories T.
By (T) -1[T T] Σ (F(())ewF(T)
Pr[r] newr(T)
Z Σ
(I)
neww(T))
TEl newTwww
1
Z Pr(r E T newF(() #0),
where Z is the normalization factor of QF.
To bound the size of F, we want to show that the algorithm does not add too many states outside of F. We therefore bound /BB.J/B[G,], where the expectations are over the trajectory that is added to F according to QF- Applying Equation ( twice, once with T = {r T F*} and once with
T = {T] T L F+), we bound the ratio between B, and G, by
B[B.J
Pr & F A newF(T) + 0]
C.G
Pr, C F* A newp(() # 0]
We know that Pr-[7 F*] is always smaller than p. so the numerator S p. lower bound for the denominator is Pr, [new * 0] Pr, E F*). In addition, whenever the algorithm is inside the
main loop, the safety is at least [ne[we + 0j = A(F) 2p. Thus, the denominator least
Hence, the RHS of 2 is less equal to 1, thus
[ < E[G.).
This completes the proof because we know that the algorithm does not add too many states outside of F* More precisely.
E E|
Σ
Bi
G
SE
2 2 G.
2k
8

---

algorithm sate-zona simulation
ho 1000 1o ege Couunia Addernne
50
100
150
200
250
300
350
Figure 1: Coverage percentage: difference from GREEDY Algorithm.
Sample Complexity. To discuss the sample complexity, we drop the assumption that the MC is known to the learner and use EstimateSafety Subroutine to approximate AFF). The number of calls to EstimateSafety is bounded by the size of the output set, F. Hence, this part of the sample complexity bounded by FI NIF Fi and we show that O =- log k*). Another source of sampling trajectories sampled for purposes of potentially adding them to F. Observe that at any iteration the set F has an escape probability of least 2p, and each trajectory that escapes F is accepted with probability of at least 1/H. This implies a lower bound for the probability that random trajectory is accepted is
2p/ 11. This gives an upper bound of Fl for the expected sample complexity. Amplification.TTeone
H. 4.1 shows that if & holds, then the set size, Fl,, is bounded in expectation |
by 2k. As Pr(E] 2 1 impies, from Markov's inequality, that the size (2 5)k² with small probability of about + À O66). If we want to make sure that the actual size is at most (2 + 8)k* with high probability, we can repeat the process about θ (!) times and take the smallest size set.
5 Empirical Demonstration
This section demonstrates the qualitative and guantitative performance of the described algorithms in the paper. For additional figures, we refer the reader Appendix D
The MDP. We focus on a grid of size N x N, for some parameter N. The agent starts off at mid-left state, (0, A }) and wishes to reach the (absorbing) goal state at 1, 1) with minimal number of steps. At each step, it can take one of four actions: up, down, right, and left by grid square. With probability 0.9, the intended action is performed and with probability 0.1 there is drift down. The agent stops either way after H = 300 steps.
5.1 FINDING SAFEZONE vs. naive approaches
To compare the FINDING SAFEZONE Algorithm to the naive approaches presented in Section we focus on the policy that first goes to the right and when it reaches the rightmost column, it goes up. The policy is described in the appendix, Figure ((d) We take N 30 and 2000 episodes.
We run the FINDING SAFEZONE GREEDY, and SIMULATION algorithms, and estimate their coverage based on test set containing 2000 random trajectories. Figure depicts the trajectories coverage of each algorithm minus the coverage the GREEDY algorithm. For a figure with absolute values, we refer the reader to Figure 6(b in the appendix. We see that the new algorithm exhibits better performance compared to its competitors. We also see that taking less than 30% of the states (k 250 out of 900 states) is enough to get coverage of more than 80% of the trajectories.
Figures 5(a) 5(b) show the sets found for k = 60 both by the Finding SAFEZONE Algorithm and GREEDY. We see that GREEDY chooses an unconnected set for this small h leading to a coverage of While the new algorithm chooses a few states which consist of several trajectories, thus leading to coverage larger than 0.

---

Discussion and Open Problems
In this paper, we have introduced the SAFEZONE problem. We have shown that is NP-hard, even when the model is known, and designed nearly (2p, 2k*) approximation algorithm for the case where the model and policy are unknown to the algorithm. Beyond improving the approximation factors (or showing that it cannot be done unless P N), natural direction for future work is the following. Given small p > 0 and a (known or unknown to the learner) MDP, find a policy with small p p-safe subset. If the value of the policy, when restricted the SAFEZONE states, is close to the optimal value of the original MDP, restricting the policy to the SAFEZONE states generates a compact policy representation with value close optimal, and most trajectories completed in the AFFEZONE.
Acknowledgement
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), and the Yandex Initiative for Machine Learning Tel Aviv University.
References
Abel, D., Arumugam, D., Lehnert, L., & Litttman, M. (2018). State abstractions for lifelong reinforcement learning. In International Conference Machine Learning. (pp. 10-19).
Alharin, A., Doan, T.-N., & Sartipi, M. (2020). Reinforcement learning interpretation methods: A survey. IEEE Access, 8, 171058-171077
Amir, D., & Amir, O. (2018). Highlights: Summarizing agent behavior to people. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, (pp. 1168- 1176).
Amodei, D., Olah, C.,, Steinhardt, J., Christiano, P. F., Schulman, J., & Mané, D. (2016). Concrete problems in Al safety. CoRR, abs/1606.06565.
Bennett, A., Misra, D., & Kallus, N. (2023). Provable safe reinforcement learning with binary feedback. In International Conference on Artificial Intelligence and Statistics, (pp. 10871-10900).
Blanc, G., Lange, J., & Tan, L.-Y. (2021). Provably efficient, succinet, and precise explanations. Advances in Neural Information Processing Systems, 34.
Brandes, U., Holm, E., & Karrenbauer, A. (2016). Cliques in regular graphs and the core-periphery problem in social networks. In International Conference on Combinatorial Optimization and Applications, (pp. 175-186). Springer.
Chandola, V., Banerjee, A., & Kumar, V. (2009). Anomaly detection: A survey, ACM Comput. Surv..
Dong. S., Van Roy, B., & Zhou, Z. (2019). Provably efficient reinforcement learning with aggregated states. arXiv preprint arXiv:1912.0633
Emam, Y., Glotfelter, P., Kira, Z., & Egerstedt, M. (2021). Safe model-based reinforcement learning using robust control barrier functions. CoRR, abs/21 10.05415.
Even-Dar, E., Mannor, S., Mansour, (2006). Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. JMLR, 7, 1079-1105.
Even-Dar, E., Mansour, Y. (2003). Approximate equivalence of markov decision processes. In COLT.
García, J., Fernández, F. (2015). comprehensive survey on safe reinforcement learning. J. Mach. Learn. Res., 16, 1437-1480.
10

---

Givan, R., Dean, T., & Greig, M. (2003). Equivalence notions and model minimization in markov decision processes. Artificial Intelligence.
HasanzadeZonuzy, A., Bura, A., Kalathil, D. M., & Shakkottai, (2021). Learning with safety
constraints: Sample complexity of reinforcement learning for constrained mdps. In AAAI.
Hendrycks, D., Carlini, N., Schulman, J., & Steinhardt, J. (2021). Unsolved problems in ML safety. CoRR, abs/2109.139
Hussein, A., Gaber, M. M., Flyan, E., & Jayne, C. (2017). Imitation learning: A survey of learning methods. ACM Comput. Surv.
Koh, P. W., Liang. (2017). Understanding black-box predictions via influence functions. In International Conference on Machine Learning. (pp. 1885-1894).
Li, J., Nagarajan, V., Plumb, G., & Talwalkar, A. (2020). A learning theoretic perspective local explainability. arXiv preprint arXiv:201 (tt:::201.0120000 1.01205.
Liu, Z., Cen, Z., Isenbaev, V., Liu, W., Wu, Z. S., Li, B., & Zhao, D. (2022). Constrained variational policy optimization for safe reinforcement learning. In International Conference Machine Learning, JCML 2022, Proceedings of Machine Learning Research.
Molnar, C. (2019). Interpretable Machine Learning.
Moshkovitz, M., Yang. Y.-Y., & Chaudhuri, K. (2021). Connecting interpretability and robustness in decision trees through separation. arXiv preprint arXiv:2102.07048.
Pfrommer, S., Gautam, T., Zhou, A., Sojoudi, S. (2021). Safe reinforcement learning with chance-constrained model predictive control. CoRR, abs/21 12.
Prajapat, M., Turchetta, M., Zeilinger, M. N., & Krause, A. (2022). Near-optimal multi-agent learning for safe coverage control. In NeurlPS.
Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series in Probability and Statistics.
Sootla, A., Nowen-Rivers I., Jafferjee, T., Wang, Z., Mguni, D. H., Wang. J., & Ammar, (2022). Saute RL: Almost surely safe reinforcement learning using state augmentation. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. Cambridge, MA, USA: A Bradford Book.
Vazirani, V. V. (2001). Approximation Algorithms. Berlin, Heidelberg: Springer- Verlag.
Epringer-Verlag.
Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
Xu, W. Xu, K., Bastani, H. Bastani, O. (2021). Safely bridging offline and online reinforcement learning. CoRR, abs/21 10. 13060.
Yang, J., Chen, T., Payne, B., Guo, P., Zhang, Y. & Guo, J. (2020). Generating routes for autonomous driving in vehicle-to-infrasttuttu communications, Digital Communications and Networks.

---

Supplementary Material
A Hardness
In this section, we show that SAFEZONE is NP-hard to solve, and this is why approximation is necessary. Moreover, SAFEZONE is hard even if the MC and the optimal p-safe size, k" are known. Our starting point is the NP-hardness of regular cliques. The REGULAR as an input (i) regular graph G with n nodes where each node has degree d. and (ii) an integer kig. It returns whether G contains clique of size ki- Whenever G and Kg are clear from the context simply write REGULARCLIQUE. The following fact follows, c.g., from Brandes et al. (2016).
k:)) problem gets
Fact A.1. REGULARCIIQUE is NP-hard.
Markoy chain (random walk). Fix a graph G GV, F)) and a starting vertex no E V. The graph induces Markov Chain (random walk) in the following way. The states of the process correspond to the vertices in the graph G. The transition function is defined as P(vlu) = ((,,))e where d is the degree of any node. The process starts from node uo and then proceeds according to the transition function P for I steps.
Reduction. To prove the hardness of SAFEZONE, solver to SAFEZONE. For each vertex e E V, run an algorithm for SAFEZONE with horizon H = 2, k ke, and 1 - 2 and as the starting state. If there is at least one run of the algorithm that returns YES, then the final answer is YES. Otherwise, the answer is NO. Note that this reduction efficient.
show how to solve REGULARCLIQUE given
Theorem A.2. For every graph G = (V, E) and an integer k. there exists a clique of size kig in G there exists v E V such that SAFEZONE
U, P, kes p) relurns YES.
Proof. (=) If there is a clique of size kn, then we can take the corresponding h states. The probability remain in this subset is at least (ساي for SAFEZONE must return YES.
(remember that H 2). Thus, an exact solver
(=) Suppose there is clique of size k. Assume by contradiction that the reduction (algorithm) returns YES. Let so be a vertex which was the starting state from the running instance which the YES came from and let F denote the output of SAFEZONE. We will show that the probability to remain in any subset of size i is smaller than (²
Since there no clique of size i in G, we know that F not a clique. It therefore follows that there exists at least two vertexes, 8a, 8b E V such that (8a; 8b) $ F.
We will now bound the probability of escape from state so by exhaustion.
1. If so # Sa. then
Pr(escape from sol 2 Pr(t = 1: (so. )'),s' s' & F
+ Pr(t = 1: (80, s), + sal
Pr(t = 2 (8, s' & Flc = 1 (so, 8), 8 # sal
Pr(l 1: (80, sa)]
Pr[[ 2: 2: (8.,8'), s' & Fu 1 (s0, sa)]
d - (k- - 1)
k 4-2 2 d
d (k: 1)
1
d
- (k- 2)
+ d
d
d
d
d
k
k
2-2
(k- - 2) - 1)
1
k-2
d2
+ d
d3
2
(k 1 1+ 1) = k(k 2)
d2
d2
Hence
k(k -2)
(k 112
Pr[staying]
<
d² <
d²
12

---

2. If 8o = Sa. then
Prlescape from so) 2 Pr(t 1 (50. ) & F)
Pr([ = : (80. 8), 8 E F. Pr( = 2: () $ F| = (50, P)
d -
(k
2)
k 2 d - (k-1)
d
d
d
k - 2
k-2
(k: - 2) 1)
d2
(k: 2) 1)
1
Hence
(k: - 2)(k - 1)
(k 1)2
Pr[staying] <
d²
d2
Given environment, policy, and SAFEZONE one could compute exactly how much safe it is (see Appendix for details), from which we deduce our following corollary.
Corollary A.3. SAFEZONE is NP-complete.
We note that for = 1, the GREEDY AT EACH STEP Algorithm optimal.
B Proofs of Section
B.1 Greedy by Threshold Algorithm
naive approach to the SAFEZONE problem to return all states 8 E with probability p(s) 2 B for some parameter / > 0, see Algorithm
Algorithm 3 Greedy by Threshold
Parameter: 3 0, {p(s))es return {s E S p(s) 2 B}
Lemma 3.1. For any p, 3 E (0, 1), the GREEDY THRESHOLD ALGORITHM returns set that (p + B 4) SAFEZONE. In particular, for B fr, this set (2p, k"
SAFFZONE.
p
Proof. There are most 8 states with probability p(s) 2 B. Thus |F| S 8
Denote by F* an optimal (p, k*) SAFEZONE set. By the law of total probability,
Pr(r g F < Pr(z @ F*) + Prlt C F).
Looking at the R.H.S of the inequality, the left term smaller than by the definition of SAFEZONE. The right term is equal to the probability of reaching a state in F that its probability is smaller than 3, i.e., state in F F.
Using union bound, this can be bounded by k*
Lemma B.1. For every p E (0, 1/2), H N, there exists an MDP and minimal integer k such that the MDP has a (p. -.k)-SAPPZONE but for 3 = p/k GREEDY BY THRESHOLD Algorithm returns F with escape probability < 2p and of size [ = (H/B3).
Proof. Fix p E (0, 1). For ease of the presentation, we will assume that 1-f is an integer (if not, should be rounded to the nearest integer). Define A contain 1-p H states, B contain k - 1 states, and = { U A U Consider the following MDP with states and starting state 8o- The transition function is defined follows:
13

---

For every i E A, Pr[s [so] = 3 and for every E [H - 1]. Pr(s 1.
For s E B, so] -
For s e B, Pr[s|s] =
The MDP is illustrated in Figure 2 Clearly, {5o} U B is (p, -)-FFEZOON In addition, GREEDY BY THRESHOLD ALGORITIMM returns the set of all states, as for every state E A we have that
p(s) = 3, p(0)) = > p 8, and for every E B we have that p(s) = x-1 > = B. Thus the
I-
size of the returned set is S is 01H/3)) which completes the proof.
(p, - Saaaafeeon
1
1
$
22
B
So
54
SK-1
7
7
Figure Lower bound for GREEDY By THRESHOLD Algorithm.
B.2 Simulation Algorithm
Algorithm Simulation Algorithm
Input: m 3 In
0.005
F - { for I...m m. do
+ choose a random trajectory
F FUT
end for return
Lemma 3.2. Fix p. E 10, With probability at least 0.99, SIMULATION Algorithm returns set that is (p+ 3*3, + pH In k SAFEZONE. In particular, for 3
P. this set is
(2p, O(K" (lk*)) SAFEZONE.
Proof. Denote by F* the optimal (p, k²) SAFEZONE set. By the law of total expectation, we can split [[] into two parts, depending on whether trajectories are entirely in F not:
Trajectories that entirely in F" contribute at most ke states to F.
A trajectory that is not contained in F* contributes most H states to F.
Thus,
(
A+
= - (k+ PH lnk"
B|[ < k* +p
0.005
B
14

---

We use Markov's ss inequality to get the desired bound on [F].
For the safety,
first denote the set of all states in Fx with probability least as T {s E F* p(s) 2 8}. We will show that with probability at least 0.9995, it holds that C F, which will prove our claim, similarly to Lemma 3.1
For a fixed state & E T, the probability that & is bounded by (1 (1-p(s)) + In one ee 0.005 Using union bound, the probability that there is state s r which is not in F is bounded by k'
0.005 k-
0.005.
In other words, with probability at least 0.995, I C F, thus implementing the greedy approach in Algorithm 3 and proving that the probability that random trajectory escapes F is bounded by
+ B...
Lemma B.2. For every P.Y E (0,1), H E N, and 3 = f. there is an integer r E N and MDP with (p. k)) -AFEZOOE,, but with probability 2 7, SIMULATION algorithm returns F of size
||| 2 kH In with escape probability (F) = (p)).
Proof. Fix 7, (0, 1). Recall that 3 In 0.005
k and take r m
Define A to contain r!l
states, to contain & states, and S { UAU LAUB. B.
Consider the following MDP with states and starting state so- The transition function is defined as follows:
For every i E A, Pr[s [sl = f and for every j E [H 17-1] 1], Pr[s 1, sl 1.
For s B, Pr[s|so] 1
For 8 E B, Pr[s|s] =
The MDP is illustrated in Figure 3
A
(p, SafeZone
B
$
1
B
s
So
B
A SH
A
1
A
SK-1
22
$1.
Figure 3: Lower bound for SIMULATION Algorithm.
The set B U {5o} } is safe with k states.
We will show that:
After adding 2 1 In In random trajectories, with probability 2 1 - -y we have that [F] 2 kHl ln
After adding m random trajectories, we have that with high probability F* C F, thus A(F) ((p).
15

---

To prove the first property, we claim that with probability - every time we add a trajectory such that T + 0, we add new states.
Notice that we ignore So. trajectories A are entirely unconnected, and each trajectory chosen randomly with probability Ps(s f. This yields that if sh, & F, then 83, & F for every j E [ As result, every time we add a new sy. to F, we add H more states to F. Let N denote the number of trajectories sampled with states from A. The probability that their intersection contains only 80 18
(r 1) (r -N)
r N
N
N =
2 1
N
From the structure of the MDP, we have that [ = pm. Therefore, with probability 2 1 -
1
FI]
E H m. H 2 Ink H kn
The second property follows from Lemma 3.2
B.3 Greedy at Each Step
Algorithm 5 Greedy Each Step
Input: > 0, {p(s))es
F + {80} for i = 1... H do
Sort states in St, p(s)) 2 ... 2 ((1
j + arg min E/=1 p(s;) 21-p
F F+FU
end for return
Lemma 3.3. For any p E 1), if the MDP is layered, GREEDY AT EACH STEP ALGORITHM returns a set that is (pHl, k*) SAFEZONE.
Proof. Take a random trajectory = (s1, $2.... For every 8 E the probability that & F is bounded by p. thus using union bound, the probability that 7 has state s; such that s; & F is at most pH.
The construction of F guarantees that F is the minimal subset of states such that for every the probability that 8; is in the subset at least there is time step such that Pr[s; F*1 1 - P. which is contradiction, since Pr(r E F*] s min; Pr(s; E F*).
Assume by contradiction that [F] > k=" Then
Lemma B.3. For any E (0,1), there is an MDP and an integer such that there is (p. SAFEEOO,,,,, but GREEDY AT EACH STEP Algorithm returns F with escape probability A(F) Z ((Hp).
Proof. Fix p E (0, and take is 3H + 1.
Consider the MDP illustrated in Figure 4 The set {os} (si) (st) U (sgh form a (p. 3H 1) UJ-SAPEZONE.
We will prove by induction that the for every time i,
p(st) = 1 - 2p.
p(s)) = p(st)) = =((s)) = S. and
For every j 15...., &o 4). p(s)) 26
16

---

p/26
P/2
p/2
32
s
s.
85
1-p
1 zo
1/2
1/2k
22
sJ
1/2k
1-
20
#-1
16-1
R-11
#-1
c1-1
11-1
Figure Lower bound for GREEDY EACH STEP Algorithm.
is easy to see that the two properties hold for
For > 1,
p(si) p1)) + p(s
-11- 111-((111pp)))
22)) -2p
12
p2 P
p(s))= = p:-i(s--11) + p + p(s 1-11 1 = (1 - (1-2
+
2
2 2
Similarly, p(s}) = P.
p(,))
50(61
1 1-1 +
p(s
p
+
P
2
4
4k
2
f=5
For every j E (5...., ., h 4].
p($))=
p 1
+
k+4
(
P
P
2h
2k
4k
41.2
2k
The algorithm might return {so) {s
{st) U (sah. i.e. instead of taking Ui(s)); it takes
) Finally, the observation (((50) U { (s))) 2 et completes the proof. O
C Proofs of Section
For convenience, we state here Hoeffding's 's inequality.
Lemma C.1. [Hoeffding's 's Inequality] Let y1..... Un be independent random variables such that V: E (a, for every yi with probability Then, for any >
y
Elyd
2 E
< 2e-2-- -2Ne 1(b-a)
17

---

C.1 Proof of Theorem 4.1
In this section, we provide a complete proof for Theorem 4.1 Throughout the section, we define few terms and notions. We will start with proving guarantees regarding single iteration of the while-loop.
Recall that F denotes a minimal s- set (of size k*). If there are multiple optimal solutions, choose one arbitrarily. For the convince of analysis, we denote the values of the algorithm variables at the end of each iteration i of the while-loop by Tú, Fi, accept;. Let j(t) denote the value of variable j during the i-th call EstimateSafety Subroutine. In addition, let N; denote the number of trajectories sampled for the j-th time of calling Subroutine EstimateSafery. i.e., N; = 2,2 In 2 X500
for j(i) - i.
For case of presentation, we recall some of the definitions from the proof technique description. We say that trajectory T good all the states are in F* and bad if it escapes I.e., a trajectory good if T C F and bad if r g F* Additionally, we say that state E S is good if it is in F and bad otherwise. Namely, a state is good if F and bad if s F*. Let (F,11 and B; (F,-1) be the number of good and bad states added to F;-1 in iteration i, respectively (notice that (R-1) and (F:-1) are random variables that depends on F3-1). For short, whenever clear from the context, we write G and B; respectively.
The following lemma bounds the error in approximating the escape probability.
Lemma C.2. Let Fj-1 S be subset of of states and c, > be some parameters. Let S be sample of N₂ 1 In 2 i.i.d. random trajectories. Then,
25(1)
Pr S.
(( ((B-)) 2 S Ag.
Also, as X,- 2(
3A
Pr 3i ((Fi-1)- 2 S A/4,
Where the last probability is over all the samples S; made by EstimateSafety Subroutine.
Proof. The first part follows directly from Hoeffding's 's inequality by taking y: = 11[7 & Fj.
Assigning
Xy= Чマ
3A and applying union bound, we get
Pr 3i -(FF-1)-((F)) 2
Pr
((F-))
2
31
X
S(4)
Σ A00) A
(T))²
4
((8
j=1
j=1
The inequality marked by (+) follows from the fact that A is estimated once for every time j increases.
We define the event that EstimateSafety always provides good estimations by
E= (vi -(F-1))A(EE s...
By the above, we have that Pr[E] 2 1 2/4.
In the following lemma we assume that if the current escape probability is at least 2p, then the fraction of bad trajectories that escape F--1 is bounded from above by the fraction of good trajectories that escape Fi-1.
Lemma C.3. Let 0 and assume that ((F 2 2p. Then,
? (F # & F*
where the probabilities are over random trajectories.
18

---

current set F larger or equal to the Proof. To prove the lemma, we will bound the probability Pr, PrylnewF_,(17 (T) * 00A 2 F*] from
above and the probability Pı,[newr,_.(T) + O F*) from below. Since ( S p.
Pr(newp,,1() + #0A & F S PriT & pp
(4)
The assumption A (F;-1) 2p implies that
2p & ((F-1) = Pr Pr|new (T) + 0] = Pr(mewR_ (T) + OAT & F*] (r(news, ( OA F*
< Prineewa_ii (T) x OAT F*] Pr/r & F 40A
hence
Pr[newr, O0A
(5)
Putting (4 and (5) together yields the statement.
Now, long the algorithm is inside the while-loop (i.e., the escape probability holds ((F) 2p + c), it follows that ((F) 2 2p with high probability from Lemma C.2 Combining with Lemma C33 would yield that with high probability F then in expectation, it at least as likely to be good as is to be bad.
random trajectory, if the trajectory escapes
We move to show the main ingredient of the proof, namely that for any iteration, with high probability, the expected number of good states added expected number of bad states.
For every iteration in which we sample ri both G, and B; depends on the following:
1. The realizations of the sampled trajectory, and in particular on new (Ti).
2. The probability of adding to F, i..., 1/newp,,,Ta (T)).
Next, prove Equation B
Lemma C.4. Assume event & holds. Thus, for all iterations i inside the while-loop we have
F|- < F(-,),
where the expectation is over the trajectory that is sampled from the MC dynamics and added to F;-1 according to QF
Proof. Since event & holds, have that A(F 2 2p long do not terminate in iteration i.
We can use to bound E, [B, 11-1 by
11 Pr, Pry[ner Pr-[newF (T)
h
h
Pr[newF_110 (T)
#OAT (1) FM)
Pr|newp_ # #0
Lemma
H
Pr, [newF, h h E.
h
Theorem 4.1. Given P. G, E (0, FINDING SAFEZONE Algorithm returns subset F S such
that:
1. The escape probability is bounded from above by 4(F) 2p 2e, with probability
2. The expected size F given bounded by E{ FI 33 S 2k*
3. The sample complexity of the algorithm bounded by O A In + Hk* od
and the
running time bounded by AC
In
1Pkx)) with probubility X.
19

---

Proof. Assume that the event & holds, and recall that
Pr[E] 2 2211-11 1 1/4.
(6)
We start with the first clause. Since the event & holds, Lemma C.2 in particular implies that A(F) I 2p + 2e, hence the first clause holds. For second clause, we will bound [[[F] E] from above by 2k Since & holds, we have that (F,-1) 2 2p, for every inside the while-loop, thus Lemma C.4 yields
F| < [-
This implies that
B| 8] S 2
EF B S 2k"
where the last inequality follows from the definition of G2, as Σ, G. S |F
We continue with the third clause of the theorem. Let M denote the sample complexity of the algorithm, namely M Mr ME where My is the expected total number of trajectories sampled within the FINDING SAFEZONE Algorithm (without the samples made by EstimateSafery Subroutine) and Mg is the total number of trajectories sampled using EstimateSafety. We will bound each term separately.
Since & holds, whenever are inside the while-loop, A(F) 2 2p, which implies that it takes at most 1/2p trajectories expectation to sample a trajectory that escapes F,, and such trajectory accepted with probability at least I/H.
Thus, from Wald's identity, it follows that
H 2p
H P
E MMp El
F
From Markov's inequality the above inequality, with probability at least 4.
4HK* pd
Pr
Mr
2
(8)
Moving on bound Mg. Since holds, it follows from Equation and Markov's inequality that
Pr
F
8k
3
Pr
|
2
4
3 Pr
| 2
4
3
S (9)
X
If FI S Sk* X. the number of calls for Subroutine EstimateSafety is also bounded by 8Tkk" / (we only
call SafimateSafety after we added states to F). also implies that 2(mm~ I >9 for every j 2
323
Thus, if [F < A
F
2
2
1
In 86(Tk*)²
ME
Σ
N
S
In
5
2
2
Xj
2e
3X
2
A
1=1
2(8ak*J
8k
86(rk*)2
4k
86(Tk*)²
In
In
2
A3
A3
Combining the above with Equation
we get
4k
86(
Pr
ME
(10)
As M = Mr + Mg. union bound over Equation with probability 2 1 3X/4
(6) Equation and Equation 10 implies that
b.
Hk*
M
In
+
(11)
A
pd
20

---

H²*") For each trajectory we sample we run in time O(H), e.g., by using lookup table for maintaining the current F. Consequently, if the event in Equation [T] holds then the running time of the algorithm is bounded by
pd
Overall, all the clauses in the lemma hold with probability
A.
C.2 Proof of Theorem 4.2
Theorem 4.2. (main theorem) Given p, p, > O, if we run FINDING SAFEZONE for (()) times and return the smallest output set, F C 8, then with probability 2 0.99
1. The escape probability is bounded by (FF) - 2p+ 2e.
2. The size of F is bounded from above by | S (2 + 6)k*
3. The total sample complexity and running time are bounded by O k' 622 8
In k'
Hk*
and
p5²
O Hk" 63,2
In k" +
poa ), respectively.
8
Proof. Assume we run FINDING SAFEZONE Algorithm for m 30n times and denote each algorithm output by F". Return the smallest set F = argmin p: [F]
It follows from Theorem 4.1 that for every À (0, 1), each F is of expected size [[[ s 2k", and
(2p + -sfe with probability 2 X. Choosing = 0.01 implies
3m
0.01
Pr Pr()(F) > 2p + 2c] <
(12)
3
In addition, from Markov's inequality it follows that for every 8 >>> 0.
Pr [[| + 8)k*
Pr [
(2 + o)k= [8 + Pr[E]
2k*
8)k* +1
8/2
+
1+6/2
5/2 - X - X8/2
1 8/2
From the independence of the algorithm runs, for m
2 l00 5 Pr[[F] > (2 + 5)6*] < Pr[Vi ([Fi) (2+ 8)k))
Pr[ Pr[[Fi|
5)k-]
<E(m]
8/2 - - X6/2
m
+ 8/2
< e ml 8/2- X3/2
0.01
1-5/2
3
Hence
0.01
Pr[[F| > (2 + 8)k*1 <
(13)
As for the sample complexity, let M, denote the (random) sample complexity of the i-th and let us denote
4k*
86(rk*)2
4Hk"
M
In
Xe
33
pd
21

---

From Theorem 4.1 M, > M with probability < X.
By taking the union bound the sample complexity bound per run, get
0.01
Pr M,
MJ
Σ
Pr
[, > M S m
3
[m(m]
Where the last inequality follows from Theorem 4.1 and 3m Assigning 2 and
0.01 3m
In
300
we get that with probability
3
mk
mHl"" In
kv
0
In k
Hk*
Σ M. =0
(14)
de
pd
82
p52
Since the algorithm runs in time O(H) for every trajectory sampled, if the sample complexity is bounded by the above term, then the total running time is bounded by O HH" 84,²
In
Hk*
+
Hk*
pd
Finally, from union bound over Equation Equation (13) and Equation (14) all the theorem properties hold with probability 2 0.99.
D
Additional Figures for Section
D.1
Comparing SAFEZONE of two policies
In this section, we empirically explore the SAFEZONE of two different policies within the same MDP. The first policy, described in the previous section, first goes right and then to middle, and the second policy first goes to the middle and then goes right. See Figure 6 in the appendix. These scemingly similar policies induce very different SAFEZONES as can be seen in Figure which depicts the number of visits in each state. It shows that the second policy requires fewer states to achieve the same level of safety, even though in terms of minimizing the number of steps to get to the goal state outperformed by the first policy (intuitively, the second policy has more fail attempts go up in expectation since the lowest row of the grid cannot get worst). In Figure 7 we see that already with 14% of the states, all three algorithms achieve trajectory coverage of more than 85%.
(a) Set chosen by GREEDY AT EACH STEP Algo- rithm.
(b) Set chosen by SAFEZONE Algorithm.
Figure 5: Empirical results regarding Coverage of the different algorithms, FINDING SAFEZONES and state visit frequency.
Figure depicts the two policies discussed in the paper when N
Figure 7 depicts coverage percentage for the different algorithms discussed in the paper when applied to the second policy.
22

---

algoritim
safe zone
coverage percentage
2
50
100
150
230
250
300
330
(a) &Coveraee: difference from GREEDY Algorithm.
100
algerithm simulation groedy
coverage percentage
40
(b) % &Coverage: absolute values.
10
102
10
10
(c) Total number of visits at each state from 2000 episodes. Zero visits in grey.
Figure ((c) depicts the number of total visits at each state using the described policy.
Figure shows the visits of the policies described in the main paper for N = 30. It is immediately clear that the SAFEZONE of the two policies are fundamentally different. As mentioned, this affects their SAFEZONE sizes. Namely, when trying to go right from current state in the lowest row it impossible to get to a square that is lower than that, and the first policy takes advantage of this. In contrast, the second policy keeps trying to go up from the lowest row, which implies that in expectation it goes down more times compared to the first.
E Exact Computation
In this section, we assume that the transition function known the algorithm and show how to compute A(F).
23

---

(d) Go right and then to the goal state.
+
+
+
+
(c) Go to the middle and then right.
Figure 6: Two policies for the same MDP with N 7. Starttin state, sp. blue, and the goal state in red.
Given a Markov Chain P, and set F C S we create a new Markov Chain (S', P', Sp) as follows. We add new state 8sink & S, and set S' FU {. For each transition from a state E F to state s' & F we modify and make the transition in P to the sink 8xink- In P', when we are in 8sink we always stay in 8sink. More formally: (1) if s, set Pl (Ssinkls) = E.' P(s' 8) and (3) P' (ssink) Saink) 1 and Pl $sink) for + Saink-
then P'(s'[s)= P(s'(s), (2) we

---

100
algorithm simulation greedy
coverage percentage
20
80
100
Figure 7: SAFEZONE coverage for the second policy.
Now we claim that A(F) = Prp [$H = ssink], since any trajectory that reaches a state not in will reach the sink in P' and stay there. We compute Pr (H Syink] using standard dynamics programming.
The running time of constructing (S', P', so) is (()S))) Computing the probability of Pr [sH Ssink] takes ({²)) Therefore we have established the following.
Lemma E.1. Given a Markov chain (8, P.)) and H()
S we can compute A(F) in time
Note that the above lemma implements an exact version of the EstimateSafety Subroutine.
25

---

10 3
102 2
10
10 0
(a) Number of visits at each state policy "Go right then the middle"
10
10 2
10
10 0
(b) Number of visits at each state for policy "Go to the middle and then right"
Figure 8: Total number of visits for the two policies.
26


Reviews:
[{"review_id": "i3TGzKby3F", "reviewer": "Reviewer_YYwR", "summary": "The paper proposes an innovative definition called the SAFEZONE and uses it to describe the escape probability of the sampled trajectory. This paper analyzes several naïve algorithms and proposes an algorithm to overcome the weaknesses in naïve algorithms, especially when considering the size of safety states. Finally, numerical experiments are conducted to evaluate the algorithm's performance compared to mentioned naïve algorithms.", "questions": "No more questions.", "limitations": "No.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think the paper is easy to follow.\n\nStrengths:\n\n1. The paper introduces the definition called the SAFEZONE to find the subset of ‘safe states’, i.e., the set that has low escape probability $\\rho$ and a small size $k$.\n2. Three naïve algorithms are clearly discussed with solid theoretical analysis and specific MDPs examples in the appendix.\n3. A new approach for solving an approximate SAFEZONE is proposed with complete analysis, and numerical comparisons show the algorithm's performance.", "weaknesses": "No obvious limitations, but this paper is not written well. The motivation for this work should be discussed more, and it would be helpful if the author discuss more concurrent works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your evaluation of our paper. We will address your valuable suggestions and enhance the clarity and motivation of our paper. We are grateful for your positive comments on our paper's concepts and algorithms.\n\nThe motivation of our paper, as discussed in the introduction and discussion sections, emphasizes the practical significance of our approach. By identifying SafeZones, we offer solutions to challenges in autonomous vehicles, manufacturing, and potentially compact policy design. \n\nWe will discuss more concurrent works (e.g., about other approaches for RL safety) to provide a comprehensive context for our contributions as you suggested. "}, {"review_id": "vU6qt4R69v", "reviewer": "Reviewer_JjfH", "summary": "The paper introduces a new problem that involves finding a SafeZone: given the possibility to interact with an MDP using a fixed policy, the learner as to find a subset of states F of minimal size s.t. the probability that a trajectory visits a state outside F is at most a given parameter \\rho. They show that the problem is NP-hard even when the transition matrix is known. They propose an approximate algorithm that finds near-optimal SafeZones with polynomial sample complexity (in the relevant variables). The approach is numerically tested on a toy problem.", "questions": "See above.", "limitations": "I did not found any discussion about limitations", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper introduces an interesting problem (though it may lack a bit of \"concrete motivation\", see below). The problem is definitely challenging from a theoretical perspective.\n2. While I haven't checked the proofs, the results seem sound\n3. The authors managed to derive a computationally-efficient algorithm computing near-optimal Safe Zones even though the base problem is NP-hard", "weaknesses": "1. Although the introduction presents some examples, I still wasn't fully convinced about the motivations behind studying this peculiar setting. In particular, it is still unclear to me what problems the proposed algorithm (or in general finding safe zones) enable solving. It would be good to provide a more \"concrete\" example, ideally some numerical results on a real-world problem (or a simulated variant) where it is clear that finding safe zones is the right thing to do\n2. Moreover, even in the context of the examples given in the introduction, the assumption that we can only interact with the MDP with a single policy seems a bit limiting. In those settings, it seems reasonable to observe trajectories collected by multiple policies, mostly because multiple agents are interacting with the environment and each displays learning behavior (so changing policies). How to extend the proposed setting and algorithms to such a context is not clear\n3. I found the core part of the paper (Sec. 3,4) a bit hard to read. In particular, if my understanding is correct, Sec. 3 tries to build some intuition which is later useful to explain the main algorithm in Sec. 4. However, that didn't really work for me: Sec. 4 starts with \"In this section, we suggest a new algorithm that builds upon and improves the added trajectory selection of the SIMULATION Algorithm\", but the SIMULATION algorithm was not explained at all in Sec. 3. The rest of Sec. 4, especially the first paragraphs, are also hard to follow, while Sec. 3 seems mostly to report a bunch of technical results rather than intuitions (so I did not really feel \"a gentle start\" to me).\n4. It is not clear how good the sample complexity of the main algorithm (Th. 4.2) is, especially in terms of dependences on the main variables (k^\\star, \\delta). It would be good to add some discussion about this. Do the authors think that the current dependences are optimal or improvable?\n5. The experiments are conducted on a very toy and low-scale domain. I would have like to see larger domains and also a comparison of the computational requirements (time complexity) of the different algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful and detailed review. We will address your comments below.\n\n**MDP with a single policy**\n\nOur setting does allow for any number of policies (multiple agents) by using a  single mixed policy as follows: each agent $i\\in\\{1,\\ldots,n\\}$ has some policy $\\pi^i$. The mixed policy is the one that selects a number uniformly at random from  $1,\\ldots,n$, then runs $\\pi^i$ (alternatively, we can consider any other distribution over the agents/policies). As a result, it is possible to observe trajectories collected by multiple policies and use the algorithms from the paper as is. Thank you for bringing it up! We will discuss it in the final version of the paper.\n\n**Sections 3+4 readability**\n\nSIMULATION is an intuitive algorithm that simply samples a certain amount of random trajectories and adds their states to a set, and then returns this set. It is described in line 207 and formalized in Appendix B as Algorithm 4. If anything is unclear regarding SIMULATION Algorithm 4 or Sections 3,4 we would be happy to answer further questions.\n\n**Sample complexity of the main algorithm (Th. 4.2)**\n\nWe expect the dependency on $k^\\star$ to be optimal. The reason why is the following. Consider a MC such that there are $k^*-1$ trajectories, each starts in an initial state $s^0$ and ends with a unique corresponding state $1,\\ldots,k^*-1$. Consider a case where the probability of each such trajectory is $\\frac{1-\\delta}{k^*-1}$. In this case, it would take at least $k^*$ samples to find a $k^*$-safezone.\nAs for the parameter $\\delta$, this could be treated as a constant. For example, selecting $\\delta=1/3$ yields that we need to run the algorithm $6\\cdot \\ln 300$ times and a solution of size $7/3k^*$ w.h.p..\n\nWe will add a discussion about this in the final version of the paper.\n\n**Experiments + Time complexity of the naive algorithms**\n\nAs we were the first to formalize the safezone problem, we focused on theoretical guarantees and provided some experiments just for demonstration.\nAs for time complexity of the naive algorithms:\n- In Greedy by Threshold, the running time is bounded by the maximum between the number of states reachable by the policy with probability $>0$ , i.e., by $|S|$.\n- Simulation Algorithm has a running time of $O(H/\\beta \\ln k^∗)$ as it samples $O(1/\\beta \\ln k^∗)$ trajectories and each has at most $H$ states.\n- In Greedy at Each Step, as there are MC with states reachable in every level, and it needs to rank each level, it has a running time of $O(H|S|\\log|S|)$ (using, e.g., mergesort as sorting algorithm).\n\n**Motivation**\n\nThe motivation of our paper, as discussed in the introduction and discussion sections, emphasizes the practical significance of our approach. By identifying SafeZones, we offer solutions to challenges in autonomous vehicles, manufacturing, and potentially compact policy design. \n"}, {"review_id": "0A2yCUm8Mj", "reviewer": "Reviewer_EfcG", "summary": "This paper introduces the SafeZone problem: Given an MDP and a policy, find the smallest set of states such that the probability of leaving this set of states (the escape probability) lies below a given threshold using trajectory samples. The authors provide various examples of applications of the SafeZone problem, such as imitation learning with compact policy representation and post hoc explainability of RL.\nThe authors provide proof that the SafeZone problem is NP-complete. The adjusted problem solved in this paper is to instead find a SafeZone with a larger but minimal escape probability than the threshold and a larger but minimal cardinality than the true optimal cardinality given the threshold.\nThree naive approaches are discussed, and one approximation algorithm for finding SafeZones. The authors provide upper bounds on each approach's escape probability and sample complexity. They give provable guarantees on their approximation algorithm. Finally, the paper compares three of the four approaches based on a grid world problem.\n\nPart of this work has been previously presented at the NeurIPS 2022 TSRML Workshop. The work did not appear in any proceedings, journals, or books, so according to NeurIPS' call for papers, this is not considered a dual submission.", "questions": "Why is Greedy by Threshold excluded from the empirical demonstration?\n\nHow should an escape probability threshold be chosen?\n\nWhat escape probability threshold value was used for the empirical demonstrations?\n\nHow often were the experiments of the empirical demonstration repeated?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper introduces a novel problem and gives extensive examples of situations where a solution to this problem could be useful. It shows the need for approximation by proving that the SafeZone problem is NP-complete, even if the induced MC and the minimal cardinality (of the corresponding escape probability threshold) are known.\n\nThe paper analyses four algorithms for finding SafeZones, provides upper bounds on the escape probability and sample complexity, and indicates the limitations of the three naive approaches.\n\nThe paper suggests an interesting future work direction, where the problem is moved from finding SafeZones of an induced MC to finding policies of an MDP with small SafeZones given an escape probability threshold.", "weaknesses": "The paper is challenging to follow because of two main reasons: a lot of information is only available in the appendices, and few (intuitive) examples are used after introducing the problem.\n\nThe first reason, limited information in the paper itself and reliance on the appendices can, for example, be seen in Section 3, where Appendix B contains the actual algorithms, MDP examples, and proof outlines, and in Section 5, which only contains one figure, with the rest all placed in Appendix E.\nFurthermore, what information is available in the appendices is also not always clear. For example, it is not mentioned in Appendix A that the proof of Theorem A.2 is given in Appendix D. Nor is it mentioned in Section 5 that more figures regarding the empirical demonstration are available in Appendix E, only four subfigures are referenced.\nMoreover, the information about the empirical demonstration section is incomplete. The escape probability threshold is not given for computing the results and the number of repetitions. Also, the paper only compares three of the discussed methods without mentioning the exclusion of the Greedy by Threshold algorithm.\n\nThe second reason, the lack of intuitive examples, concerns the sections after the introduction. The paper gives extensive and intuitive examples in the introduction but does not use these throughout the rest of the paper. Only the autonomous vehicle example is referenced once in Section 2.\nAlthough the paper proves why an approximation of the SafeZone problem is necessary, they give no argumentation as to why an almost 2 approximation is sufficiently tight to have a practical use still. An intuitive example where the size of the SafeZone is compared to an optimal SafeZone could illustrate this usefulness.\nAlso, the problem used in the empirical demonstration does not provide any intuition regarding the applications of the SafeZone problem, as given in the introduction. Some discussion on how this relates would be helpful.\n\nTypo in Section 3, line 208. theses -> these\nIncorrect reference in Section 5, line 355. Section 5 -> Figure 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful and detailed review. In what follows we address your comments:\n\n**Proof of Theorem A.2 is given in Appendix D** \nWe apologize for the confusion regarding the proof of Theorem A.2 and we will mention that it appears in Appendix D and that there are more figures in App E in the final version of the paper.\n\n**How should an escape probability threshold be chosen?**\nA feature of the algorithm is that the escape probability is a free parameter that can be tuned depending on the use case, or experimented to select the ideal one for the target (e.g., using binary search). \n\n**Escape probability threshold in demonstration**\n Rather than stopping the algorithm when it reaches some escape probability threshold, the implementation adds trajectories one after another until reaching a specific safezone size (the reason being that the x-axis is k).\n\n**Greedy by threshold**\nWe only implemented one type of greedy algorithm, as the MDP in the demonstration is not layered (i.e., there are states that appear in more than a single time step, see Line 220). \n\n**Intuitive examples**\nWe appreciate the advice and will use the autonomous vehicle example as a running example throughout the paper. \n\n**How often were the experiments of the empirical demonstration repeated?**\n We ran each experiment 2000 times (see line 353).\n"}, {"review_id": "kHPEidCAoE", "reviewer": "Reviewer_N6Et", "summary": "\nThe work introduces the SafeZone problem for safe reinforcement learning (RL). Instead of learning for the optimal policy under the constrained Markov Decision Process (MDP) as many traditional methods deal with a safe RL problem, the work attempts to search for a SafeZone, a subset of state space that is policy-dependent, balancing between minimizing the number of states contained in the subset and reducing the probability that a random trajectory goes out of the subset. If the probability of escaping the SafeZone is low with a randomly sampled trajectory, it is considered safe. The paper also proposes a new algorithm for detecting the SafeZone. The algorithm uses rejection sampling to decide whether a new random trajectory should be added to the SafeZone and keep updating the safety estimation once a new trajectory is added.\n\n", "questions": "My question is related to the concerns listed above. I would appreciate it if the authors could discuss whether the proposed method has the potential to outperform the constrained MDP methods, regarding the learning efficiency.\n", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The work proposes a new way of dealing with the safe reinforcement learning (RL) problem. In traditional safe RL, the problem is usually formulated as a constrained MDP, while in this work, the agent is trained to find the SafeZone for a given policy.\n\n2. The paper detailedly explains the formalization of the new problem setting and compares the new setting with the constrained MDP, it helps with understanding. \n\n3. The paper provides both theoretical analysis and empirical evidence, making the results more sound. Though solving the SafeZone problem is NP-Hard, the paper derives an algorithm and provides empirical results. These results suggest that the idea introduced in the paper is practical.\n", "weaknesses": "The main concern comes from the choice of baseline algorithms and the experiment design. The paper empirically tested methods on a $N \\times N$ grid, checking the quality of the SafeZone given by the new algorithm and baselines. A SafeZone with a smaller size but a larger coverage percentage on the trajectory (lower escape probability) is considered better. Although the new method is empirically shown to be better than the baseline algorithms regarding the above standard, I doubt whether the proposed algorithm can be sufficiently tested by the reported experiment, or, whether the advantage and shortage of SafeZone problem setting can be seen from this experiment.\n\nIn the introduction section, the paper points out that a new method is proposed for safe RL. One common idea used by the community is to formulate the problem as constrained MDP to solve the safe RL problem, as the paper points out. The proposed SafeZone method performs as the other path for solving safe RL, besides using constrained MDP. So, one thing remaining unclear is whether SafeZone is a better way of solving the safe RL problem than constrained MDP. \n\nThe paper focuses on comparing the quality of SafeZone detected by the proposed algorithm and baselines, but does not provide any empirical evidence about whether a good SafeZone output helps with improving the learning performance in safe RL problems, or whether a SafeZone method performs better than constrained MDP tasks. As SafeZone is a newly introduced problem setting and the proposed algorithm directly targets searching for a better SafeZone, I am not surprised that the new method outperformed baselines regarding the SafeZone quality. But the lack of learning performance in safe RL tasks makes it hard to say if detecting a SafeZone is a better way of solving the safe RL problem. It could be more convincing if the learning performance in safe RL tasks could be checked and empirically indicate that the SafeZone idea can learn safe RL tasks more efficiently than using the constrained MDP.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review! \n\nOur focus is theoretical, the experiments are a minor part of the paper and were only made for demonstration.\n\nWe don't offer an alternative solution to constrained MDP; instead, we approach a different problem and give a different solution.  As we explained in the introduction, the purpose of the SafeZone problem is to capture a new sort of safety and aims to capture popular events in the environment. "}]

Author rebuttal:
We would like to thank the reviewers for their valuable and informative reviews! We are glad you appreciate the new ֿSafeZone definition and our theoretical contribution. If we misunderstood any of the questions, we would be happy to clarify any further information during the discussion period.

Meta-review: Overall, I am suggesting to accept this paper. The reviewers consistently value the contributions of the paper, as well as the soundness of the analysis, and I agree with them. That said, the review team has also brought up a number of consistent concerns regarding the motivation (including the lack of clearly motivated and easy to follow examples) as well as the writing of the paper. I sincerely hope that the authors will follow through with their promises and improve upon those parts.
Decision: Accept (poster)