Safe Reinforcement Learning in Constrained Markov Decision Processes

Akifumi Wachi 1 Yanan Sui 2

Abstract
Safe reinforcement learning has been a promising
approach for optimizing the policy of an agent
that operates in safety-critical applications. In
this paper, we propose an algorithm, SNO-MDP,
that explores and optimizes Markov decision processes under unknown safety constraints. Specifically, we take a stepwise approach for optimizing
safety and cumulative reward. In our method, theagent first learns safety constraints by expanding
the safe region, and then optimizes the cumulative
reward in the certified safe region. We provide theoretical guarantees on both the satisfaction of thesafety constraint and the near-optimality of the cumulative reward under proper regularity assumptions. In our experiments, we demonstrate theeffectiveness of SNO-MDP through two experiments: one uses a synthetic data in a new, openlyavailable environment named GP-S AFETY-G YM,
and the other simulates Mars surface explorationby using real observation data.

1. Introduction
In many real applications, environmental hazards are firstdetected in situ. For example, a planetary rover exploring
Mars does not obtain high-resolution images at the time ofits launch. In usual cases, after landing on Mars, the rover
takes close-up images or observes terrain data. Leveraging the acquired data, ground operators identify whether
each position is safe. Hence, for fully automated operation,
an agent must autonomously explore the environment andguarantee safety.
In most cases, however, guaranteeing safety (i.e., surviving) is not the primary objective. The optimal policy forensuring safety is often extremely conservative (e.g., stay at
the current position). Even though avoiding hazards is an
1

IBM Research AI, Tokyo, Japan 2 Tsinghua University,
Beijing, China. Correspondence to: Akifumi Wachi <akifumi.wachi@ibm.com>, Yanan Sui <ysui@tsinghua.edu.cn>.
Proceedings of the 37 th International Conference on Machine
Learning, Vienna, Austria, PMLR 119, 2020. Copyright 2020 by
the author(s).

essential requirement, the primary objective is nonethelessto obtain rewards (e.g., scientific gain).
As a framework to solve this problem, safe reinforcement
learning (safe RL, Garcıa & Fernández (2015)) has recently
been noticed by the research community. The objective ofsafe RL is to maximize the cumulative reward while guaranteeing or encouraging safety. Especially in problem settings
in which the reward and safety functions are unknown apriori, however, a great deal of previous work (e.g., Wachiet al. (2018)) theoretically guarantees the satisfaction of
the safety constraint, but the acquired policy is not necessarily near-optimal in terms of the cumulative reward. In
this paper, we propose a safe RL algorithm that guarantees
a near-optimal cumulative reward while guaranteeing thesatisfaction of the safety constraint as well.

Related work. Conventional reinforcement learning literature has been agnostic with respect to safety, while pursuing efficiency and optimality of the cumulative reward.
Representatives of such work are probably approximately
correct Markov decision process (PAC-MDP) algorithms(Brafman & Tennenholtz, 2002; Kearns & Singh, 2002;
Strehl et al., 2006). Algorithms with the PAC-MDP property enable an agent to learn a near-optimal behavior witha polynomial number of samples. In addition, Kolter &Ng (2009) and Araya et al. (2012) proposed algorithms to
obtain an -close solution to the Bayesian optimal policy.
As the research community tries to apply RL algorithms
to real-world systems, however, safety issues have beenhighlighted. RL algorithms inherently require an agent to
explore unknown state-action pairs, and algorithms that areagnostic with respect to safety may execute unsafe actions
without deliberateness. Hence, it is important to develop
algorithms that guarantee safety even during training, atleast with high probability.
A notable approach is safe model-based RL (Berkenkamp
et al., 2017; Fisac et al., 2018). In this domain, safety is associated with a state constraint; thus, the resulting algorithm
is well suited for such contexts as a drone learning how tohover. The parameters of a drone are not perfectly knowna priori, but we have prior knowledge on what states areunsafe (e.g., a pitch angle of more than 50 degrees is unsafe).
In the field of control theory, constrained model predictiveSafe Reinforcement Learning in Constrained Markov Decision Processes

control (Mayne et al., 2000) has been popular. For example,
Aswani et al. (2013) proposed an algorithm for guaranteeing
robust feasibility and constraint satisfaction for a learned
model using constrained model predictive control.
On the other hand, safe model-free RL has also been successful, especially in continuous control tasks. For example, Achiam et al. (2017) proposed the constrained policy
optimization (CPO) algorithm while guaranteeing safety
in terms of constraint satisfaction. Moreover, Chow et al.
(2019) leveraged Lyapunov functions to learn policies withhigh expected cumulative reward, while guaranteeing thesatisfaction of safety constraints.
Finally, several previous studies have addressed how to explore a safe space in an environment that is unknown a priori(Sui et al., 2015; Turchetta et al., 2016). This type of problem setting is well-suited for cases such as a robot exploring
an uncertain environment (e.g., a planetary surface, a disaster site). In particular, under the safety constraint, Sui et al.
(2018) proposed a stepwise algorithm for finding the maximum value of the reward function in a state-less setting (i.e.,the bandit problem), while Wachi et al. (2018) proposed analgorithm for maximizing the cumulative reward in an MDP
setting (i.e., the planning problem).
Our contributions. We propose a safe near-optimal MDP,
SNO-MDP algorithm, for achieving a near-optimal cumulative reward while guaranteeing safety in a constrained MDP.
This algorithm first explores the safety function and then
optimizes the cumulative reward in the certified safe region.
We further propose an algorithm called Early Stopping of
Exploration of Safety (ES2 ) to achieve faster convergence
while maintaining probabilistic guarantees with respect toboth safety and reward. We examine SNO-MDP by applying PAC-MDP analysis and prove that, with high probability,
the acquired policy is near-optimal with respect to the cumulative reward while guaranteeing safety. We build an
openly-available test-bed called GP-S AFETY-G YM for synthetic experiments.1 The safety and efficiency of SNO-MDP
are then evaluated with two experiments: one in the GPS AFETY-G YM synthetic environment, and the other using
real Mars terrain data.

2. Problem Statement
A safety constrained MDP is defined as a tuple
M = hS, A, f, r, g, γi,where S is a finite set of states {s}, A is a finite set of actions{a}, f : S × A → S is a deterministic state transition
function, r : S → (0, Rmax ] is a bounded reward function,1
https://github.com/akifumi-wachi-4/safe_
near_optimal_mdp

g : S → R is a safety function, and γ ∈ R is a discountfactor. We assume that both the reward function r and thesafety function g are not known a priori. At every time stept ∈ N, the agent must be in a “safe” state. More concretely,
for a state st , the safety function value g(st ) must be above athreshold h ∈ R; that is, the safety constraint is represented
as g(st ) ≥ h.
A policy π : S → A maps a state to an action. The value ofa policy is evaluated according to the discounted cumulative
reward under the safety constraint. Let VM denote the valuefunction in the MDP, M. In summary, we represent our
problem as follows:
" ∞
#
X
π
τ
maximize: VM (st ) = E
γ r(st+τ ) st
τ =0

subject to: g(st+τ ) ≥ h,∀τ = [0, ∞].

Difficulties. In conventional safety-constrained RL algorithms, the safety function is assumed to be known a priori.
The key difference lies in the fact that we need to explore asafety function that is unknown a priori while guaranteeing
satisfaction of the safety constraint.
However, it is intractable to solve the above problem without
further assumptions. First of all, without prior informationon the state-and-action pairs known to be safe, an agent
cannot take any viable action at the very beginning. Second,
if the safety function does not exhibit any regularity, thenthe agent cannot infer the safety of decisions.
Assumptions. To overcome the difficulties mentioned
above, we adopt two assumptions from Sui et al. (2015)
and Turchetta et al. (2016). For the first difficulty, we simply assume that the agent starts in an initial set of states,
S0 , that is known a priori to be safe. Second, we assume
regularity for the safety function. Formally speaking, we
assume that the state space S is endowed with a positive
definite kernel function, k g , and that the safety function
has a bounded norm in the associated reproducing kernel
Hilbert space (RKHS, Schölkopf & Smola (2001)). The
kernel function, k g is employed to capture the regularityof the safety function. Finally, we further assume that thesafety function g is L-Lipschitz continuous with respect tosome distance metric d(·, ·) on S.
As with the safety function, we also assume that the reward
function has a bounded norm in the associated RKHS, andthat its regularity is captured by another positive definite
kernel function, k r .
The above assumptions allow us to characterize the reward
and safety functions by using Gaussian processes (GPs, see
Rasmussen (2004)). By using the GP models, the valuesof r and g at unobserved states are predicted according toSafe Reinforcement Learning in Constrained Markov Decision Processes

previously observed functions’ values. An advantage ofleveraging GPs is that we can obtain both optimistic andpessimistic measurements of the two functions by using
the inferred means and variances. A GP is specified by its
mean, µ(s), and covariance, k(s, s0 ). The reward and safetyfunctions are thus modeled asr(s) = GP(µr (s), k r (s, s0 )),g(s) = GP(µg (s), k g (s, s0 )).
Without loss of generality, let µ(s) = 0 for all s ∈ S. For
the reward and safety functions, we respectively model theobservation noise as y r = r(s) + nr and y g = g(s) + ng ,where nr ∼ N (0, σr2 ) and ng ∼ N (0, σg2 ). The posteriors
over r and g are computed on the basis of t observations
at states {s1 , . . . , st }. Then, for both the reward and safetyfunctions, the posterior mean, variance, and covariance arerespectively represented asµt (s) = kt> (s)(Kt + σ 2 I)−1 yt ,σt (s) = kt (s, s),kt (s, s0 ) = k(s, s0 ) − kt> (s)(Kt + σ 2 I)−1 kt (s0 ),where kt (s) = [k(s1 , s), . . . , k(st , s)]> , and Kt is the
positive definite kernel matrix.

3. BackgroundWe define two kinds of predicted safe spaces inferred by a
GP as in Turchetta et al. (2019). First, we consider a pessimistic safe space, which contains states identified as safewith a greater probability than a pre-defined confidence level.
Second, we derive an optimistic safe space that includes allstates that may be safe with even a small probability.
Predicted pessimistic safe space. We use the notion ofa safe space in Turchetta et al. (2016) as a predicted pessimistic safe space. For the probabilistic safety guarantee,
two sets are defined. The first set, St− , simply contains thestates that satisfy the safety constraint with high probability.
The second one, Xt− , additionally considers the ability toreach states in St− (i.e., reachability) and the ability to return−to the previously identified safe set, Xt−1
(i.e., returnability). The algorithm probabilistically guarantees safety byallowing the agent to visit only states in Xt− .
Safety is evaluated in terms of the confidence interval inferred by the GP, which is represented as1/2 g
σt−1 (s)],Qt (s) := [µgt−1 (s) ± βtwhere βt ∈ R is a scaling factor for the required level ofsafety. We consider the intersection of Qt up to iterationt, which is defined as Ct (s) = Qt (s) ∩ Ct−1 (s), whereC0 (s) = [h, ∞] for all s ∈ S0 . The lower and upperbounds on Ct (s) are denoted by lt (s) := min Ct (s) andut (s) := max Ct (s), respectively.
The first set St− contains states such that the safety constraint
is satisfied with high probability. It is formulated using
the lower bound of the safety function, l and the Lipshitz
constant, L, as follows:−
St− = {s ∈ S | ∃s0 ∈ Xt−1
: lt (s0 ) − L · d(s, s0 ) ≥ h}.

Next, the reachable and returnable sets are considered. Even
though a state is in St− , it might be surrounded by unsafe
states. Given a set X, the states reachable from X in one
step are given by Rreach (X) = X ∪ {s ∈ S | ∃s0 ∈ X, a ∈A : s = f (s0 , a)}. Even after arriving at a state with reachability, the agent may not be able to move to another statebecause of a lack of safe actions. Hence, before moving to astate s, we consider whether or not there is at least one viable
path from s. The set of states from which the agent can return to a set X̄ through another set of states X in one step isgiven by Rret (X, X̄) = X̄ ∪ {s ∈ X | ∃a ∈ A : f (s, a) ∈X̄}. Thus, an n-step returnability operator is given by
n−1
n
1
Rret
(X, X̄) = Rret (X, Rret
(X, X̄)), with Rret
(X, X̄) =Rret (X, X̄). Finally, the set containing all the states thatcan reach X̄ along an arbitrary long path in X is defined asnR̄ret (X, X̄) = limn→∞ Rret
(X, X̄).
Finally, the desired pessimistic safe space, Xt− is a subsetof St− and also satisfies the reachability and returnability
constraints; that is,−−
Xt− = {s ∈ St− | s ∈ Rreach (Xt−1) ∩ R̄ret (St− , Xt−1)}.

Predicted optimistic safe space. As defined in Wachiet al. (2018) and Turchetta et al. (2019), an optimistic safe
space has rich information for inferring the safety function.
Let Xt+ denote the predicted optimistic safe space. Similarly
to Xt− , the optimistic safe space, Xt+ , is defined as++
Xt+ = {s ∈ St+ | s ∈ Rreach (Xt−1) ∩ R̄ret (St+ , Xt−1)},

where St+ is the set of states that may satisfy the safety
constraint, which is written as+
St+ = {s ∈ S | ∃s0 ∈ Xt−1
: ut (s0 ) − L · d(s, s0 ) ≥ h}.

Intuitively, Xt+ contains all states that may turn out to besafe even if the probability is low. In other words, S \ Xt+contains states that are unsafe with high probability.
Confidence interval. The correctness of Xt+ and Xt− depends on the accuracy of the confidence interval inferred by
the GP. The conservativeness can be tuned by using the parameter β, and the choice of this parameter was well-studiedin Srinivas et al. (2010) and Chowdhury & Gopalan (2017).

Safe Reinforcement Learning in Constrained Markov Decision Processes

In the rest of this paper, we set the parameter toqβt = B g + σg 2(Γgt−1 + 1 + log(1/∆g )),where B g is a bound on the RKHS norm of g, ∆g is theallowed failure probability, and the observation noise is σg sub-Gaussian. Also, Γg quantifies the effective degrees of
freedom associated with the kernel function, which represents the maximal mutual information that can be obtained
about the GP prior.
Under the above definitions and assumptions, we have thefollowing lemma regarding the correctness of the confidence
intervals.
g2g
Lemma 1. Assume
q that kgkk ≤ B and nt ≤ σg , ∀t ≥ 1.

If βt = B g + σg2(Γgt−1 + 1 + log(1/∆g )), then1/2 g
σt−1 (s)|g(s) − µgt−1 (s)| ≤ βt

holds for all t ≥ 1 with probability at least 1 − ∆g .
The above paradigm for the safety function can also be
applied to the reward function. Hence, we have a similar
lemma for the reward function as well.

Algorithm 1 SNO-MDP with ES2
Input: states S, actions A, transition function f , kernel kr for
reward, kernel kg for safety, GP prior for reward, GP prior forsafety, safety threshold h, discount factor γ, Lipschitz constant L,
initial safe space S0 .
1: C0 (s) ← [h, ∞) for all s ∈ S0
2: // Exploration of safety
3: loop−
4: St− ← {s ∈ S | ∃s0 ∈ Xt−1
: lt (s0 ) − L · d(s, s0 ) ≥ h}++
0
5: St ← {s ∈ S | ∃s ∈ Xt−1 : ut (s0 ) − L · d(s, s0 ) ≥ h}−−
6: Xt− ← {s ∈ St− | s ∈ Rreach (Xt−1) ∩ R̄ret (St− , Xt−1
)}
+
+
+
+
+
7: Xt ← {s ∈ St | s ∈ Rreach (Xt−1 ) ∩ R̄ret (St , Xt−1 )}8: Gt ← {s ∈ Xt− | et (s) > 0}
9: ξ ← arg maxs∈Gt wt (s)10:Update GPs for both reward and safety on way to ξ11:t ← t + Tst−1 →ξ and st ← ξ
12: // ES2 algorithm
13:
Yt ← {s0 ∈ S + | ∀s ∈ Xt− : s0 = f (s, πy∗ (a | s))}14:
if Yt ⊆ Xt− then break15:// Typical termination condition16:
if maxs∈Gt wt (s) < g then break
17: end loop
18: // Exploration and exploitation of reward
19: loop
20:
Ut ← µrt + αt+1 · σtr 21:JY∗ (st ) ← maxst+1 ∈Yt Ut (st+1 ) + γJY∗ (st+1 )22:
st+1 ← arg maxst+1 ∈Yt JY∗ (st )23: end loop

Lemma 2. Assume
krk2k ≤ B r and nrt ≤ σr , ∀t ≥ 1.
p thatrr
If αt = B + σr 2(Γt−1 + 1 + log(1/∆r )), then
1/2

r|r(s) − µrt−1 (s)| ≤ αt σt−1(s)holds for all t ≥ 1 with probability at least 1 − ∆r .
These lemmas follow from Theorem 2 in Chowdhury &Gopalan (2017).
Optimal solution. Here, we define the optimal policy in
our problem setting. Under the optimal policy, π ∗ , the valuefunction, VM , satisfies the following Bellman equation:∗
VM(st ) =

max
st+1 ∈R̄g (S0 )∗[ r(st+1 ) + γVM(st+1 ) ] ,where R̄g (S0 ) is the largest set that can be safely learned
up to g accuracy (for a formal definition, see Appendix A or
Turchetta et al. (2016)). In our problem setting, in which thereward and safety functions are unknown a priori, the above
Bellman equation cannot be solved directly. Our ultimate∗
objective is to obtain a policy whose value is close to VM
while guaranteeing satisfaction of the safety constraint.

4. Algorithm
We now introduce our proposed algorithm, SNO-MDP, forachieving a near-optimal policy with respect to the cumulative reward while guaranteeing safety.

We first give an overview of SNO-MDP, which is outlined
as Algorithm 1. We extend a stepwise approach in Sui et al.
(2018) from state-less to stateful settings. Basically, our algorithm consists of two steps. In the first step, the agent expands the pessimistic safe region while guaranteeing safety(lines 2−17). Next, it explores and exploits the reward in
the safe region certified in the first step (lines 18−23). The
reason for this stepwise approach is that we can neglect
uncertainty related to the a priori unknown safety function
once the safe region is fixed.
However, a pure stepwise approach does not stop exploring
the safe region until the convergence of the GP confidence
interval (lines 15−16). This formulation often requires
the agent to execute a great number of actions for exploring safety. Hence, to achieve near-optimality while executing a smaller number of actions, we also propose theES2 algorithm.2 This algorithm checks whether the current
safe region is sufficient for achieving near-optimality (lines
12−14), which maintains the theoretical guarantee with respect to both the satisfaction of the safety constraint andthe near-optimality of the cumulative reward. We further
propose a practical ES2 algorithm, called P-ES2 , with better empirical performance, although it does not provide atheoretical guarantee in terms of the near-optimality of the
cumulative reward.
2

Both ES2 and P-ES2 do not affect the agent’s safety.

Safe Reinforcement Learning in Constrained Markov Decision Processes

4.1. Exploration of Safety (Step 1)

Unsafe space

Optimistic
safe spaceFirst, we consider how to explore the safety function. As ascheme to expand the safe region, we consider “expanders”
as in Sui et al. (2015) and Turchetta et al. (2016). Expanders
are states that may expand the predicted safe region, which
is defined as Gt = {s ∈ Xt− | et (s) > 0}, where et (s) =|s0 ∈ S \ St− | ut (s) − Ld(s, s0 ) ≥ h|.

Pessimistic
safe space

The efficiency of expanding the safe region is measured
by the width of the safety function’s confidence interval,
defined as
wt (s) = ut (s) − lt (s).

Figure 1. Illustration of My , used in the ES2 algorithm. The
yellow and blue regions represent Xt+ and Xt− , respectively. The
red region (i.e., X \ Xt+ ) is unsafe with high probability.

The agent safely and efficiently expands the safe region by
sampling the state with the maximum value of w among
the expanders, Gt . Hence, the agent sets the temporal goalaccording toξ = arg max wt (s).

In this reward setting, the second term on the right-handside corresponds to the exploration bonus. For balancing the
exploration and exploitation in terms of reward, we solve
the following Bellman equation:
JX∗ (st , brt , bgt ) = max − Ut (st+1 ) + γJX∗ (st+1 , brt , bgt ) ,s∈GtThen, within the predicted safe space Xt− , it chooses a pathto get to ξ from the current state st−1 so as to minimize thecost (e.g., the path length). In our experiment, we simply
minimized the path length. By defining the cost as related
to w (e.g., 1/w), however, the agent could explore safety
more actively on the way to ξ.
The previous work (Sui et al., 2015; Turchetta et al., 2016;
Sui et al., 2018) terminated safety exploration when thedesired accuracy was achieved for every state in Gt ; that is,
max wt (s) ≤ g .

s∈Gt

(1)

Unfortunately, this termination condition often requires a
great number of iterations. For the purpose of maximizing
the cumulative reward, it often leads to the loss of reward.
Therefore, in Section 4.3, we propose the ES2 algorithm toimprove this point.
4.2. Exploration and Exploitation of Reward (Step 2)
Once expansion of the safe region is completed, the agent
guarantees safety as long as it is in X − and does not have toexpand the safe region anymore. Hence, all we have to do
is optimize the cumulative reward in X − . As such, a simple
approach is to follow the optimism in the face of uncertainty
principle as in Strehl & Littman (2008) and Auer & Ortner(2007), then to consider the “exploration bonus” represented
by R-MAX (Brafman & Tennenholtz, 2002) and Bayesian
Exploration Bonus (BEB, Kolter & Ng (2009)).
Specifically, in accordance with Lemma 2, we optimize
the policy by optimistically measuring the reward with the(probabilistic) upper confidence bound,
1/2

Ut (s) := µrt (s) + αt+1 · σtr (s).

st+1 ∈Xt∗

where br = (µr , σ r ) and bg = (µg , σ g ) are the beliefs overreward and safety, respectively. Also, t∗ is the time stepwhen the termination condition (1) is satisfied. Note thatbr and bg are not updated; hence, we can solve the above
equation with standard algorithms (e.g., value iteration).
4.3. Early Stopping of Exploration of Safety (ES2 )We have proposed a stepwise approach for exploring andoptimizing the constrained MDP. In the first step when thesafe region is expanded, however, the existing safe exploration algorithms (Sui et al., 2015; Turchetta et al., 2016;
Sui et al., 2018) continue exploring the state space untilconvergence of the confidence interval, w, which generally
leads to a large number of iterations. Our primary objective
is to maximize the cumulative reward; hence, we shouldstop exploring safety if further exploration will not lead tomaximizing the cumulative reward.
While exploring the safety function, we check whether the
step can be migrated. As such, we consider the following
additional MDP,
My = hX + , A, f, r0 , g, γi.
As shown in Figure 1, the differences from the original MDP,
M, lie in the state space and the reward function. The state
space of My is defined as the optimistic safe space (i.e.,
X + ), while the reward function is defined as follows: rµ + α1/2 σ r
if s ∈ Xt+ \ Xt− ,
0
r :=
(2)
r
1/2 r
µ −α σif s ∈ Xt− .
In the pessimistic safe space, the reward is defined as thelower bound; otherwise, it is defined as the upper bound.
This definition of the reward function encourages the agent

Safe Reinforcement Learning in Constrained Markov Decision Processes

to explore outside the predicted safe space, Xt− . Using the
new MDP above, we consider the set of states that the agent
will visit at the next time step, defined as
Yt = {s0 ∈ S + | ∀s ∈ Xt− : s0 = f (s, πy∗ (a | s))},State space𝑠"𝑝(𝑠# ,𝑏 ) )max [ r0 (st+1 ) + γVMy (st+1 ) ].

st+1 ∈Xt+(3)

Finally, we stop exploring the safety function if the following equation holds:
Yt ⊆ Xt− .

𝑠$

1 − 𝑝(𝑠# , 𝑏 ) ) 1 − 𝑝(𝑠$ , 𝑏 ) )𝑧where πy∗ is the optimal policy for My , obtained by maximizing the following value function:
VMy (st ) =𝑠#𝑝(𝑠$ , 𝑏 ) )(4)

Intuitively, we stop expanding the safe space if the directionof the optimal policy for My heads for the inside of Xt− .
If the agent tries to stay in Xt− even under the condition
that the reward is defined as in (2), then we do not have toexpand the safe region anymore.
When the ES2 algorithm confirms satisfaction of the above
condition, we move on to the next step and then optimize
the cumulative reward in Yt ; that is,JY∗ (st , brt , bgt ) = max Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) .
st+1 ∈Yt

4.4. More Practical ES2 Algorithm (P-ES2 )As we will prove in Section 5, the ES2 algorithm provides us
with a theoretical guarantee with respect to the cumulative
reward. Unfortunately, this guarantee is achieved at theexpense of empirical performance. The issue with the pureES2 algorithm lies in the state constraint in (3); that is, thevalue function is calculated under the assumption that all
the states in the optimistic safe space, X + , will be identified
as safe. This assumption is necessary for the theoreticalguarantee, but, in practice, it would be more reasonable
to measure the probability of a state being identified assafe. Because the safety function is inferred as a Gaussian
distribution for each state, an example of such a probability
is a complementary error function; that is, we define thefollowing probability, g1µ (s) − h.
p(s, bg ) = Pr [g(s) ≥ h | bg ] ≈ 1 − erfc √2
2σ g (s)Here, we introduce a new virtual state, z. Concretely, for z,
the reward and transition probability are defined as r(z) = 0
and P (z | z, a, bg ) = 1 for all a and bg , respectively.
Hence, using z, we define a virtual transition probability
Pxz = Pr[x | st , at , bgt ] as follows:p(st+1 , bgt )if x = st+1 ,Pxz :=
1 − p(st+1 , bgt ) if x = z.

1.0

Figure 2. Illustration of Mz . This MDP is characterized by thevirtual state z and the virtual transition probability P z .

Hence, by introducing z and P z , we define the following
MDP with the smooth, continuous transition probability:
Mz = hX + ∪ {z}, A, P z , r0 , g, γi.
Figure 2 shows a conceptual image of this MDP. Intuitively,in Mz , the agent optimizes the policy under the virtual
condition that a state-action pair may lead to the extremely
undesirable state, z, with probability 1 − p. Then, we solve
the following equation instead of solving (3):VMz (st ) =max [Pszt+1 · {r0 (st+1 ) + γVMz (st+1 )}].

st+1 ∈Xt+

For this equation, we used r(z) = 0 and V (z) = 0. For
the optimal policy πz∗ obtained by solving the above equation, we stop exploring the safety function if the following
equation holds:
Zt := {s0 ∈ S + | ∀s ∈ Xt− : s0 = f (s, πz∗ (a | s))} ⊆ Xt− .
Then, we optimize the cumulative reward in Zt by solving
the following equation:
JZ∗ (st , brt , bgt ) = max Ut (st+1 ) + γJZ∗ (st+1 , brt , bgt ) .
st+1 ∈Zt

5. Theoretical Results
We now provide theoretical guarantees on the safety andnear-optimality of our proposed algorithm. Theorem 1 isassociated with the safe expansion stage (i.e., step 1), whichguarantees safety and convergence to the safe region. Theorem 2 ensures convergence toward the near-optimal cumulative reward. Theorem 3 ensures that SNO-MDP stillachieves the near-optimal cumulative reward even when
the ES2 algorithm is used. In the rest of this paper, let
Vmax = Rmax /(1−γ). Also, let D : M → R be a diameterof an MDP, defined as D(M) = minπ maxs1 6=s2 Tsπ1 →s2 ,where Tsπ1 →s2 is the expected number of time steps thatpolicy π takes to move from s1 to s2 .
5.1. Safety Guarantee and CompletenessWe first present a theorem related to the safety guarantee
and completeness.

Safe Reinforcement Learning in Constrained Markov Decision Processes

Theorem 1. Assume that the safety function g satisfies
kgk2k ≤ B g and is L-Lipschitz continuous. Also, assume that S0 6= ∅ and g(s) ≥ h for all s ∈ S0 .
Fix any g > 0 and ∆g ∈ (0, 1). Suppose that we
conduct the stage of “exploration of safety” with the
g
g
noise
q nt being σg -sub-Gaussian, and that βt = B +follows by adapting standard arguments from previous PACMDP results. The key condition that allows us to prove thenear-optimality of SNO-MDP is that, at every time step,
the agent is optimistic with respect to the reward, and thisoptimism decays given a sufficient number of samples. By
optimizing the cumulative reward in X − according to the
optimism in the face of uncertainty principle, the acquired
policy is ∗V -close to the optimal policy in the original safetyconstrained MDP.

t∗
Cg |R̄0 (S0 )|
D(M),
g ≥
βt∗ Γt∗2g

Finally, we present a theoretical result related to the ES2
algorithm. Specifically, we prove that ES2 maintains thenear-optimality of SNO-MDP.

σg 2(Γgt−1 + 1 + log(1/∆g )) until maxs∈Gt wt (s) < gis achieved. Finally, let t∗ be the smallest integer satisfying

with Cg = 8/ log(1 + σg−2 ). Then, the following statements
jointly hold with probability at least 1 − ∆g :• ∀t ≥ 1, g(st ) ≥ h,
• ∃t0 ≤ t∗ , R̄g (S0 ) ⊆ Xt−0 ⊆ R̄0 (S0 ).
A proof is presented in the supplemental material. Theorem 1 guarantees that SNO-MDP is safe in the stage of
exploration of safety (i.e., step 1), as well as in the stage of
optimization of reward (i.e., step 2), with high probability.
In addition, after a sufficiently large number of time steps,
X − is guaranteed to be a super-set of R̄g (S0 ).
5.2. Near-Optimality
We next present a theorem on the near-optimality with respect to the cumulative reward.
Theorem 2. Assume that the reward function r satisfies
krk2k ≤ B r , and that the noise is σr -sub-Gaussian. Let
πt denote the policy followed by SNO-MDP at time t,
and let st and brt , bgt be the corresponding state and beliefs, respectively. Let t∗ be the smallest integer satisfying
C |R̄ (S )|t∗≥ g 02 0 D(M), and fix any ∆r ∈ (0, 1). Fiβt∗ Γggt∗pnally, set αt = B r + σr 2(Γrt−1 + 1 + log(1/∆r )) and∗V = Vmax · (∆g + Σrt∗ /Rmax ),q
Cr αt∗ Γrt∗
1r
. Then, with high probability,with Σt∗ = 2t∗
V πt (st , brt , bgt ) ≥ V ∗ (st ) − ∗V— i.e., the algorithm is ∗V -close to the optimal policy —for all but t∗ time steps, while guaranteeing safety withprobability at least 1 − ∆g .
A detailed proof of Theorem 2 is presented in the supplemental material. The proof is based on the following idea.
After the agent fully explores the safe space, X − satisfies
R̄g (S0 ) ≤ X − ≤ R̄0 (S0 ), and states in X − are safe withhigh probability. Once X − converges, the probability ofleaving the “known” safe space is small; hence, Theorem 2

Theorem 3. Assume that the reward function r satisfies
krk2k ≤ B r , and that the noise is σr -sub-Gaussian. Let πtdenote the policy followed by SNO-MDP with the ES2 algorithm at time t, and let st and brt , bgt be the corresponding
state and beliefs, respectively. Let t̃ be the smallest integer
for which (4) holds,
and fix any ∆r ∈ (0, 1). Finally, setprr
αt = B + σr 2(Γt−1 + 1 + log(1/∆r )) and˜V = Vmax · (∆g + Σrt̃ /Rmax ),with Σrt̃ = 12qCr αt̃ Γrt̃. Then, with high probability,t̃V πt (st , brt , bgt ) ≥ V ∗ (st ) − ˜V— i.e., the algorithm is ˜V -close to the optimal policy — forall but t̃ time steps while guaranteeing safety with probability at least 1 − ∆g .
The proof of Theorem 3 is presented in the supplemental
material. The proof is based on the following idea. Whenthe condition in (4) is satisfied, the agent will not leave Y,
and a near-optimal policy is obtained by optimizing the cumulative reward only in Y with the optimistically measured
reward. Also, as long as the agent is in Y (⊆ X − ), safety
is guaranteed with high probability. The proof is similar tothat for Theorem 2.

6. Experiment
In this section, we evaluate the performance of SNO-MDP
through two experiments. One used a synthetic environment,
while the other simulated Mars surface exploration. We also
show the effectiveness of our ES2 and P-ES2 algorithms.
6.1. Synthetic GP-S AFETY-G YM Environment
Settings. We constructed a new open-source environment
for safe RL simulations named GP-S AFETY-G YM. This environment was built based on OpenAI Safety-Gym (Ray et al.,2019). As shown in Figure 3(a), GP-S AFETY-G YM represents the reward by a color (yellow: high; green: medium;blue: low), and the safety by height.

Safe Reinforcement Learning in Constrained Markov Decision Processes(a) GP-S AFETY-G YM.

(b) Performance comparison.

(c) Effects of ES2 and P-ES2 .

Figure 3. Experiment with synthetic data. (a) Example screen capture from the GP-S AFETY-G YM environment. (b) Average reward overthe episodes, comparing the performance of SNO-MDP with ES2 and the baselines. (c) Average reward over the episodes, showing theeffects of ES2 and P-ES2 . The colored circles represent when the transition from safe exploration to reward optimization happens foreach method. In both (b) and (c), the reward is normalized with respect to the S AFE /R EWARD KNOWN case.

Baselines. We empirically compared the performance of
our SNO-MDP with S AFE MDP (Turchetta et al., 2016)
and S AFE E XP O PT-MDP (Wachi et al., 2018), as well asa case called S AFE /R EWARD KNOWN. In S AFE MDP, theagent tries to expand the safe region without considering
the reward. In S AFE E XP O PT-MDP, the agent attempts
to maximize the cumulative reward while leveraging thedifference between the value function in Xt+ and that in
Xt− . Finally, S AFE /R EWARD KNOWN is a non-exploratory
case in which the safety and reward functions are known apriori.
Metrics. We used the cumulative reward and the numberof unsafe actions as comparison metrics.
Results. Figure 3(b) compares the performance of SNOMDP and the baselines in terms of the reward. For theseresults, the average reward was measured over the previous
50 time steps. SNO-MDP achieved the optimal reward after
shifting to the stage of reward optimization, which outperforms S AFE MDP and S AFE E XP O PT-MDP in terms of the
reward after a sufficiently large number of time steps. TheS AFE MDP agent did not aim to maximize the cumulative
reward, and the S AFE E XP O PT-MDP agent was sometimes

stucked in a local optimum when the expansion of the safe
region was insufficient. Figure 3(c) shows the empiricalperformance of the ES2 and P-ES2 algorithms. P-ES2
achieved faster convergence in terms of the reward than theoriginal ES2 did. Also, all methods, including the baselines,
did not take any unsafe actions.
6.2. Simulated Mars Surface Exploration
Settings. We then conducted an experiment based on aMars surface exploration scenario, as in Turchetta et al.
(2016) and Wachi et al. (2018). In this simulation, we useda publicly available Mars digital elevation model (DEM)
that was created from observation data captured by the highresolution imaging science experiment (HiRISE) camera(McEwen et al., 2007).
We created a 40 × 30
rectangular grid-world byclipping a region aroundlatitude 30◦ 6’ south andlongitude 202◦ 2’ east, asshown in Figure 4. At every time step, the rover
took one of five actions:stay, up, down, left, andright. We assumed that
Figure 4. Mars terrain data.
any state in which theslope angle was greater than 25◦ were unsafe. The safetyfunction g was defined as the slope angle calculated fromthe DEM, and the safety threshold was h = − tan(25◦ ).
10.0
7.5

25

5.0

20

2.5

y

We considered a 20 × 20 square grid in which the reward
and safety functions were randomly generated. At every
time step, an agent chose an action from stay, up, right,
down, and left. The agent predicted the reward and safetyfunctions by using different kernels on the basis of previous
observations. In this simulation, we allowed the agent toobserve the reward and safety function values of the current
state and neighboring states. The kernel for reward was aradial basis function (RBF) with the length-scales of 2 andprior variance of 1. The kernel for safety was also an RBF
with the length-scales of 2 and prior variance of 1. Finally,
we set the discount factor to γ = 0.99, and confidence
intervals parameters to αt = 3 and βt = 2 for all t ≥ 1.

15

0.0

−2.5

10

−5.0

5

0
0

−7.5

10

20
x

30

−10.0

The rover predicted the elevation by using a GP with aMatérn kernel with ν = 5/2. The length-scales were 15 m,
and the prior variance over elevation was 100 m2 . We assumed a noise standard deviation of 0.075 m. For the reward, we randomly defined a smooth, continuous reward.
To predict the reward function, the rover used a GP with
RBF kernel having length-scales of 2 and a prior varianceSafe Reinforcement Learning in Constrained Markov Decision Processes
Table 1. Experimental results with real Mars data.

2

SNO-MDP W / P-ES
SNO-MDP W / ES2
SNO-MDPS AFE MDP
S AFE E XP O PT-MDPS AFE /R EWARD KNOWNR EWARDU NSAFE ACTIONS

0.81
0.78
0.49
0.34
0.59
1.00

0
0
0
0
0
0

over the reward of 2. We set the confidence levels as αt = 3
and βt = 2, ∀t ≥ 0, and the discount factor as γ = 0.9.
Baselines and metrics. We used the same baselines andmetrics as in the previous synthetic experiment.
Results. Table 1 summarizes the results. The reward was
accumulated over the episode, which was normalized withrespect to the S AFE /R EWARD KNOWN case. Our SNOMDP with either P-ES2 or ES2 outperformed S AFE MDP
and S AFE E XP O PT-MDP in terms of the reward. This was
expected, because SafeMDP does not aim to maximize thecumulative reward, and S AFE E XP O PT-MDP does not guarantee the near-optimality of the cumulative reward. Also, nounsafe action was executed by any of the tested algorithms.

7. Conclusion
We have proposed SNO-MDP, a stepwise approach for
exploring and optimizing a safety-constrained MDP. Theoretically, we proved a bound of the sample complexity toachieve V -closeness to the optimal policy while guaranteeing safety, with high probability. We also proposed the ES2
and P-ES2 algorithms for improving the efficiency in obtaining rewards. We developed an open-source environment,
GP-S AFETY-G YM, to test the effectiveness of SNO-MDP .
We also demonstrated the advantages of SNO-MDP using
the real Mars terrain data.

Acknowledgement
This work is sponsored by IBM Research AI and ToyotaTsinghua joint project on health challenges for future cityand smart health system design (20203910025).

References

Aswani, A., Gonzalez, H., Sastry, S. S., and Tomlin, C. Provably safe and robust learning-based model predictive control.
Automatica, 49(5):1216–1226, 2013.
Auer, P. and Ortner, R. Logarithmic online regret bounds forundiscounted reinforcement learning. In Neural Information
Processing Systems (NeurIPS), 2007.
Berkenkamp, F., Turchetta, M., Schoellig, A., and Krause, A. Safemodel-based reinforcement learning with stability guarantees.
In Neural Information Processing Systems (NeurIPS), 2017.
Brafman, R. I. and Tennenholtz, M. R-max - a general polynomial
time algorithm for near-optimal reinforcement learning. Journalof Machine Learning Research (JMLR), pp. 213–231, 2002.
Chow, Y., Nachum, O., Faust, A., Duenez-Guzman, E., andGhavamzadeh, M. Lyapunov-based safe policy optimization forcontinuous control. arXiv preprint arXiv:1901.10031, 2019.
Chowdhury, S. R. and Gopalan, A. On kernelized multi-armed
bandits. In International Conference on Machine Learning(ICML), 2017.
Fisac, J. F., Akametalu, A. K., Zeilinger, M. N., Kaynama, S.,
Gillula, J., and Tomlin, C. J. A general safety framework forlearning-based control in uncertain robotic systems. IEEE Transactions on Automatic Control, 2018.
Garcıa, J. and Fernández, F. A comprehensive survey on safe
reinforcement learning. Journal of Machine Learning Research(JMLR), 16(1):1437–1480, 2015.
Kearns, M. and Singh, S. Near-optimal reinforcement learning in
polynomial time. Machine Learning, 49(2-3):209–232, 2002.
Kolter, J. Z. and Ng, A. Y. Near-Bayesian exploration in polynomial time. In International Conference on Machine Learning(ICML), 2009.
Mayne, D. Q., Rawlings, J. B., Rao, C. V., and Scokaert, P. O.
Constrained model predictive control: Stability and optimality.
Automatica, 36(6):789–814, 2000.
McEwen, A. S., Eliason, E. M., Bergstrom, J. W., et al. Mars
reconnaissance orbiter’s high resolution imaging science experiment (HiRISE). Journal of Geophysical Research: Planets, 112(E5), 2007.
Rasmussen, C. E. Gaussian processes in machine learning. In
Advanced Lectures on Machine Learning, pp. 63–71. Springer,
2004.
Ray, A., Achiam, J., and Amodei, D. Benchmarking safe exploration in deep reinforcement learning. 2019.
Schölkopf, B. and Smola, A. J. Learning with kernels: support
vector machines, regularization, optimization, and beyond. MITpress, 2001.

Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy
optimization. In International Conference on Machine Learning(ICML), 2017.

Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret andexperimental design. In International Conference on Machine
Learning (ICML), 2010.

Araya, M., Buffet, O., and Thomas, V. Near-optimal BRL using
optimistic local transitions. In International Conference on
Machine Learning (ICML), 2012.

Strehl, A. L. and Littman, M. L. A theoretical analysis of modelbased interval estimation. In International Conference on Machine Learning (ICML), 2005.

Safe Reinforcement Learning in Constrained Markov Decision Processes
Strehl, A. L. and Littman, M. L. An analysis of model-based
interval estimation for Markov decision processes. Journal ofComputer and System Sciences, 74(8):1309–1331, 2008.
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman,
M. L. PAC model-free reinforcement learning. In International
Conference on Machine Learning (ICML), 2006.
Sui, Y., Gotovos, A., Burdick, J. W., and Krause, A. Safe exploration for optimization with Gaussian processes. In International Conference on Machine Learning (ICML), 2015.
Sui, Y., Zhuang, V., Burdick, J. W., and Yue, Y. Stagewise safe
Bayesian optimization with Gaussian processes. In International Conference on Machine Learning (ICML), 2018.
Turchetta, M., Berkenkamp, F., and Krause, A. Safe exploration in
finite Markov decision processes with Gaussian processes. In
Neural Information Processing Systems (NeurIPS), 2016.
Turchetta, M., Berkenkamp, F., and Krause, A. Safe exploration forinteractive machine learning. In Neural Information Processing
Systems (NeurIPS), 2019.
Wachi, A., Sui, Y., Yue, Y., and Ono, M. Safe exploration andoptimization of constrained MDPs using Gaussian processes.
In AAAI Conference on Artificial Intelligence (AAAI), 2018.

Safe Reinforcement Learning in Constrained Markov Decision Processes

AppendicesA. Definitions
We repeat the relevant definitions in our paper.
A1. Safe Space: For more details, see Turchetta et al. (2016).
Set of the states identified as safe up to some confidence level of g :Rsafe(X) = X ∪ {s ∈ S | ∃s0 ∈ X : g(s0 ) − g − Ld(s, s0 ) ≥ h}.
g
Set of states with reachability from X:
Rreach (X) = X ∪ {s ∈ S | ∃s0 ∈ X, a ∈ A(s0 ) : s = f (s0 , a)}.
Set of states with returnability to X:
Rret (X, X̄) = X̄ ∪ {s ∈ X | ∃a ∈ A : f (s, a) ∈ X̄},
n
n−1
1
Rret
(X, X̄) = Rret (X, Rret
(X, X̄)), with Rret
(X, X̄) = Rret (X, X̄),nR̄ret (X, X̄) = lim Rret
(X, X̄).
n→∞

Set of safe states with reachability and returnability:Rg (X) = Rsafe(X) ∩ Rreach (X) ∩ Rret (Rsafe(X), X),gg
Rg (X) = Rg (Rn−1(X)), with R1g (X) = Rg (X),g
R̄g (X) = lim Rng (X).
n→∞Pessimistic safe space:−
St− = {s ∈ S | ∃s0 ∈ Xt−1
: lt (s0 ) − L · d(s, s0 ) ≥ h},−−
Xt− = {s ∈ St− | s ∈ Rreach (Xt−1) ∩ R̄ret (St− , Xt−1)}.

Optimistic safe space:+
St+ = {s ∈ S | ∃s0 ∈ Xt−1
: ut (s0 ) − L · d(s, s0 ) ≥ h},++
Xt+ = {s ∈ St+ | s ∈ Rreach (Xt−1) ∩ R̄ret (St+ , Xt−1)}.

A2. Optimization of Cumulative Reward
For optimal policy:∗
VM(st ) =

max

st+1 ∈Rg (S0 )∗[ r(st+1 ) + γVM(st+1 ) ] .

For balancing exploration and exploitation (neither ES2 nor P-ES2 is used):
1/2

Ut (s) = µrt (s) + αt+1 · σtr (s),JX∗ (st , brt , bgt ) = max − Ut (st+1 ) + γJX∗ (st+1 , brt , bgt ) .
st+1 ∈Xt∗

Safe Reinforcement Learning in Constrained Markov Decision Processes

A3. ES2 Algorithm
For checking whether the termination condition is satisfied:
VMy (st ) =max [ r0 (st+1 ) + γVMy (st+1 ) ],st+1 ∈Xt+

Yt = {s0 ∈ S + | ∀s ∈ Xt− : s0 = f (s, πy∗ (a | s))},Yt ⊆ Xt− .
For balancing exploration and exploitation in terms of reward:JY∗ (st , brt , bgt ) = max Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) .
st+1 ∈Yt

A4. P-ES2 Algorithm
For checking whether the termination condition is satisfied:
VMz (st ) =max [ P z · {r0 (st+1 ) + γVMz (st+1 )} ],st+1 ∈Xt+

Zt = {s0 ∈ S + | ∀s ∈ Xt− : s0 = f (s, πz∗ (a | s))},Zt ⊆ Xt− .
For balancing exploration and exploitation in terms of the reward:JZ∗ (st , brt , bgt ) = max Ut (st+1 ) + γJZ∗ (st+1 , brt , bgt ) .
st+1 ∈Zt

B. Preliminary Lemma
Lemma 3. For two arbitrary functions f1 (x) and f2 (x), the following inequality holds:
max f1 (x) − max f2 (x) ≥ min(f1 (x) − f2 (x)).
xxx

Proof. For two arbitrary functions f4 (x) and f5 (x), the following inequality holds:
max f4 (x) + max f5 (x) ≥ max{f4 (x) + f5 (x)}.
xxx

Let f2 (x) = f4 (x) + f5 (x) and f3 (x) = −f4 (x). Then,max{−f3 (x)} + max{f2 (x) + f3 (x)} ≥ max f2 (x),xxxmax{f2 (x) + f3 (x)} − max f2 (x) ≥ − max{−f3 (x)},xxxmax{f2 (x) + f3 (x)} − max f2 (x) = min f3 (x).
xxx

Finally, let f1 (x) = f2 (x) + f3 (x). Then, the desired lemma is obtained.

C. Near-optimality
Lemma 4. Let JX∗ (st , brt , bgt ) be the value function calculated by SNO-MDP without the ES2 algorithm. Then,
JX∗ (st , brt , bgt ) satisfies the following inequality:
JX∗ (st , brt , bgt ) ≥ V ∗ (st ).
Proof. Consider a state st and beliefs brt and bgt . Also, let I denote the following safety indicator function:1
if s ∈ R̄g (S0 ),I(s) :=
0otherwise.

(5)

Safe Reinforcement Learning in Constrained Markov Decision Processes

Then, the following chain of equations and inequalities holds:
JX∗ (st , brt , bgt ) − V ∗ (st )=max [ Ut (st+1 ) + γJX∗ (st+1 , brt , bgt ) ] −st+1 ∈Xt−∗≥

max
st+1 ∈R̄g (S0 )max
st+1 ∈R̄g (S0 )[ Ut (st+1 ) + γJX∗ (st+1 , brt , bgt ) ] −∗[ r(st+1 ) + γVM(st+1 ) ]max
st+1 ∈R̄g (S0 )∗[ r(st+1 ) + γVM(st+1 ) ]∗= max [ I(st+1 ) · {Ut (st+1 ) + γJX∗ (st+1 , brt , bgt )} ] − max [ I(st+1 ) · {r(st+1 ) + γVM(st+1 )} ]atat

≥ min [ I(st+1 ) · {Ut (st+1 ) − r(st+1 )} + γI(st+1 )JX∗ (st+1 , brt , bgt ) − γI(st+1 )V ∗ (st+1 ) ]at= min [ I(st+1 ) · {Ut (st+1 ) − r(st+1 )} + γI(st+1 ){JX∗ (st+1 , brt , bgt ) − V ∗ (st+1 )} ] .
at

The third line follows from Xt−∗ ⊇ R̄g (S0 ) in Theorem 1. Also, the fourth line follows from the definition of I, and thefifth line follows from Lemma 3. Because s is arbitrary in the above derivation, we havemin[ JX∗ (st , brt , bgt ) − V ∗ (st ) ] ≥ min [ I(st+1 ){Ut (st+1 ) − r(st+1 )} + γI(st+1 ){J ∗ (st+1 , brt , bgt ) − V ∗ (st+1 )} ] .
st

st+1

By Lemma 2, the following equation holds with probability at least 1 − ∆r :min[ JX∗ (st , brt , bgt ) − V ∗ (st , brt , bgt ) ] ≥ γ · min [I(st+1 ){JX∗ (st+1 , brt , bgt ) − V ∗ (st+1 )} ]
st

st+1

Repeatedly applying this equation proves the desired lemma. Therefore, we have
JX∗ (st , brt , bgt ) ≥ V ∗ (st )with high probability.
Lemma 5. (Generalized induced inequality) Let br , bg , r and b̂r , b̂g , r̂ be the beliefs (over reward and safety, respectively)
and reward functions (including the exploration bonus) that are identical on some set of states Ω — i.e., br = b̂r , bg = b̂g ,and r = r̂ for all s ∈ Ω. Let P (AΩ ) be the probability that a state not in Ω is generated when starting from state s andfollowing a policy π. If the value is bound in [0, Vmax ], thenV π (s, br , bg , r) ≥ V π (s, b̂r , b̂g , r̂) − Vmax P (AΩ ),where we now make explicit the dependence of the value function on the reward.
Proof. The lemma follows from Lemma 8 in Strehl & Littman (2005).
Lemma p
6. Assume that the reward function r satisfies krk2k ≤ B r , and that the noise nrt is σr -sub-Gaussian. If αt =r
B + σr 2(Γrt−1 + 1 + log(1/∆r )) and Cr = 8/ log(1 + σr−2 ), then the following holds:
12r

Cr αt∗ Γrt∗1/2
≥ αt∗ σtr∗ (s),t∗with probability at least 1 − ∆r .
Proof. The lemma follows from Lemma 4 in Chowdhury & Gopalan (2017).

D. ES2 algorithm
Lemma 7. Assume that Yt ⊆ Xt− holds. Suppose that we obtain the optimal policy, πy∗ on the basis of JY∗ (st , brt , bgt ) =maxst+1 ∈Yt Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) . Then, for all t, the following holds:st ∈ Yt =⇒ st+1 ∈ Yt .

Safe Reinforcement Learning in Constrained Markov Decision Processes

Proof. When Yt ⊆ Xt− holds, we have{s0 ∈ S + | ∀s ∈ Yt : s0 = f (s, πy∗ (a | s))} ⊆ {s0 ∈ S + | ∀s ∈ Xt− : s0 = f (s, πy∗ (a | s))}= Yt .
This means that the next state st+1 will be within Yt if the agent is in Yt and decides the action based on πy∗ . Therefore, wehave the desired lemma.
Lemma 8. Assume that Yt ⊆ Xt− holds, and let JY∗ (st , brt , bgt ) be the value function calculated by SNO-MDP with theg
ES2 algorithm. Then, for all st ∈ Xt− , JY∗ (st , brt , bt ) satisfies the following equation:
JY∗ (st , brt , bgt ) ≥ V ∗ (st ).
Proof. Consider a state st ∈ Xt− and beliefs br and bg . Also, we define the function I as in (5). Then, the following chainof the equations and inequalities holds:
JY∗ (st , brt , bgt ) − V ∗ (st )∗= max Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) − max [ I(st+1 ) · {r(st+1 ) + γVM(st+1 )} ]at
st+1 ∈Yt∗= max Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) − max + [ I(st+1 ) · {r(st+1 ) + γVM(st+1 )} ]st+1 ∈Yt

st+1 ∈Xt
Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) −∗max [ I(st+1 ) · {r(st+1 ) + γVM(st+1 )} ]∗≥ min Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) − I(st+1 ) · {r(st+1 ) + γVM(st+1 )}
st+1 ∈Yt∗≥ min Ut (st+1 ) + γJY∗ (st+1 , brt , bgt ) − {r(st+1 ) + γVM(st+1 )}
st+1 ∈Yt∗= min Ut (st+1 ) − r(st+1 ) + γJY∗ (st+1 , brt , bgt ) − γVM(st+1 ) .

= max



st+1 ∈Yt

st+1 ∈Yt

st+1 ∈Yt∗
The second and third lines follow from the definitions of I and VM. The forth line follows from the definition of Y and the−assumption of Yt ⊆ Xt . The fifth line follows from Lemma 3.

Then, by Lemma 2, the following equation holds with probability at least 1 − ∆r :




∗
min JY∗ (st , brt , bgt ) − V ∗ (st )} ≥ γ · min JY∗ (st+1 , brt , bgt ) − VM
(st+1 )
st+1 ∈Yt

st ∈Xt−2≥ γ · min

st+2 ∈Yt∗JY∗ (st+2 , brt , bgt ) − VM
(st+2 ) .

The second line follows from Lemma 7. Repeatedly applying this equation proves the desired lemma. Therefore, for allst ∈ Xt− , we have
JY∗ (st , brt , bgt ) ≥ V ∗ (st ).

E. Main Theoretical Results
Theorem 1. Assume that the safety function g satisfies kgk2k ≤ B g and is L-Lipschitz continuous. Also, assume that S0 6= ∅and g(s) ≥ h for all s ∈ S0 . Fix any g > 0 and ∆g ∈ (0, 1). Supposeq that we conduct the stage of “exploration of safety”
with the noise ngt being σg -sub-Gaussian, and that βt = B g + σg
is achieved. Finally, let t∗ be the smallest integer satisfying

2(Γgt−1 + 1 + log(1/∆g )) until maxs∈Gt wt (s) < gt∗
Cg |R̄0 (S0 )|≥· D(M),βt∗ Γgt∗2gwith Cg = 8/ log(1 + σg−2 ). Then, the following statements jointly hold with probability at least 1 − ∆g :

Safe Reinforcement Learning in Constrained Markov Decision Processes• ∀t ≥ 1, g(st ) ≥ h,
• ∃t0 ≤ t∗ , R̄g (S0 ) ⊆ Xt−0 ⊆ R̄0 (S0 ).
Proof. This is an extension of Theorem 1 in Turchetta et al. (2016) to our settings, where t represents not the number ofsamples but the number of actions.
Theorem 2. Assume that the reward function r satisfies krk2k ≤ B r , and that the noise is σr -sub-Gaussian. Let πt denotethe policy followed by SNO-MDP at time t, and let st and brt , bgt be the corresponding state and beliefs, respectively.
∗
C |R̄ (S )|Let t∗ be the smallest integer satisfying β ∗t Γg∗ ≥ g 02 0 D(M), and fix any ∆r ∈ (0, 1). Finally, set αt = B r +tgtpσr 2(Γrt−1 + 1 + log(1/∆r )) and∗V = Vmax · (∆g + Σrt∗ /Rmax ),q
Cr αt∗ Γrt∗with Σrt∗ = 21
. Then, with high probability,t∗
V πt (st , brt , bgt ) ≥ V ∗ (st ) − ∗V— i.e., the algorithm is ∗V -close to the optimal policy — for all but t∗ time steps, while guaranteeing safety with probability
at least 1 − ∆g .
Proof. Define r̃ as the reward function (including the exploration bonus) that is used by SNO-MDP. Let r̂ be a reward
function equal to r on Ω and equal to r̃ elsewhere. Furthermore, let π̃ be the policy followed by SNO-MDP at time t, that is,
the policy calculated on the basis of the current beliefs, (i.e., brt and bgt ) and the reward r̃. Finally, let AΩ be the event inwhich π̃ escapes from Ω. Then,V πt (r, st , brt , bgt ) ≥ V π̃ (r̂, st , brt , bgt ) − Vmax P (AΩ )1/2

by Lemma 5. In addition, note that, for all t ≥ t∗ , because r̂ and r̃ differ by at most αt∗ σtr∗ at each state,
1
1/2· αt∗ σtr∗ (s)1−γ≤ Vmax /Rmax · Σrt∗ .

|V π̃ (r̂, st , brt , bgt ) − V π̃ (r̃, st , brt , bgt )| ≤(6)

For the above inequality, we used Lemma 6. Here, consider the case of Ω = Xt−∗ . Once the safe region is fully explored,
P (AΩ ) ≤ ∆g holds after t∗ time steps. Then, the following chain of equations and inequalities holds:
V πt (R, s, b) ≥ V π̃ (R̂, s, b) − Vmax · P (AΩ )= V π̃ (R̂, s, b) − Vmax · P (AX − )≥ V π̃ (R̂, s, b) − Vmax · ∆g
≥ V π̃ (R̃, s, b) − Vmax · (∆g + Σrt∗ /Rmax )= JX∗ (R̃, s, b) − Vmax · (∆g + Σrt∗ /Rmax )≥ V ∗ (R, s) − Vmax · (∆g + Σrt∗ /Rmax ).
In this derivation, the second line follows from the assumption of Ω = X − , the third line follows from P (AX − ) ≤ ∆g , thefourth line follows from (6), the fifth line follows from the fact that π̃ is precisely the optimal policy for R̃ and b, and thefinal line follows from Lemma 4.
Theorem 3. Assume that the reward function r satisfies krk2k ≤ B r , and that the noise is σr -sub-Gaussian. Let πtdenote the policy followed by SNO-MDP with the the ES2 algorithm at time t, and let st and brt , bgt be the corresponding
state and beliefs,
Let t̃ be the smallest integer for which (4) holds, and fix any ∆r ∈ (0, 1). Finally, set
p respectively.
rr
αt = B + σr 2(Γt−1 + 1 + log(1/∆r )) and˜V = Vmax · (∆g + Σrt̃ /Rmax ),Safe Reinforcement Learning in Constrained Markov Decision Processes

with Σrt̃ = 21q

Cr αt̃ Γrt̃. Then, with high probability,t̃V πt (st , brt , bgt ) ≥ V ∗ (st ) − ˜V— i.e., the algorithm is ˜V -close to the optimal policy — for all but t̃ time steps while guaranteeing safety with probability atleast 1 − ∆g .
Proof. The proof of Theorem 3 is analogous to that of Theorem 2. Define r̃ as the reward function (including the exploration
bonus) that is used by SNO-MDP. Let r̂ be a reward function equal to r on Y and equal to r̃ elsewhere. Furthermore, let π̃be the policy followed by SNO-MDP with the ES2 algorithm at time t, that is, the policy calculated on the basis of thecurrent beliefs, (i.e., brt and bgt ) and the reward r̃. Finally, let AY be the event in which π̃ escapes from Y. Then,V πt (r, st , brt , bgt ) ≥ V π̃ (r̂, st , brt , bgt ) − Vmax P (AY )1/2

by Lemma 5. In addition, note that, for all t ≥ t̃, because r̂ and r̃ differ by at most αt̃ σt̃r at each state,
1
1/2· αt̃ σt̃r (s)1−γ≤ Vmax /Rmax · Σrt̃ .

|V π̃ (r̂, st , brt , bgt ) − V π̃ (r̃, st , brt , bgt )| ≤(7)

For the above inequalities, we used Lemma 6. Then, the following chain of equations and inequalities holds:
V πt (R, s, b) = V π̃ (R̂, s, b) − Vmax · P (AY )≥ V π̃ (R̂, s, b) − Vmax · ∆g
≥ V π̃ (R̃, s, b) − Vmax · (∆g + Σrt̃ /Rmax )= JY∗ (R̃, s, b) − Vmax · (∆g + Σrt̃ /Rmax )≥ V ∗ (R, s) − Vmax · (∆g + Σrt̃ /Rmax ).
In this derivation, the second line follows from P (AY ) ≤ ∆g , the third line follows from (7), the fourth line follows fromthe fact that π̃ is precisely the optimal policy for R̃ and b, and the final line follows from Lemma 8.