Safe Policy Optimization with Local Generalized
Linear Function Approximations

Akifumi Wachi
IBM Researchakifumi.wachi@ibm.com

Yunyue Wei
Tsinghua University
weiyy20@mails.tsinghua.edu.cn

Yanan Sui
Tsinghua University
ysui@tsinghua.edu.cn

Abstract
Safe exploration is a key to applying reinforcement learning (RL) in safety-criticalsystems. Existing safe exploration methods guaranteed safety under the assumptionof regularity, and it has been difficult to apply them to large-scale real problems.
We propose a novel algorithm, SPO-LF, that optimizes an agent’s policy whilelearning the relation between a locally available feature obtained by sensors andenvironmental reward/safety using generalized linear function approximations. We
provide theoretical guarantees on its safety and optimality. We experimentallyshow that our algorithm is 1) more efficient in terms of sample complexity and computational cost and 2) more applicable to large-scale problems than previous safe
RL methods with theoretical guarantees, and 3) comparably sample-efficient andsafer compared with existing advanced deep RL methods with safety constraints.

1

Introduction

Applying reinforcement learning (RL) to applications with unknown safety constraints is challenging
as RL is inherently an exploratory process and requires agents to learn the whole environment first.
Though there has been a surge of attempts to incorporate safety in RL [3, 6, 11, 16], it is essentiallydifficult for most of the algorithms to guarantee safety, especially in the exploration phase. If a single
mistake could lead to catastrophic failures, conventional algorithms cannot be directly applied.
To guarantee safety while learning an environment, safe exploration problems have been actively
studied as a sub-field of safe RL [17]. A mainstream safe-exploration method is to utilize a Gaussian
process (GP, [24]) under problem settings in which the agent can observe only the safety function
value of its current state. Since the agent cannot get any information on the neighboring states, itis necessary to assume desirable properties for the function. Specifically, Sui et al. [31] assumed
that a safety function is Lipschitz continuous and has regularity that can be captured by appropriate
kernel functions. However, these assumptions do not hold in many environments. For example, inthe context of autonomous driving, the degree of safety varies steeply depending on the presence orabsence of other vehicles and pedestrians. Also, previous work on GP-based safe exploration suffersfrom inconsistency between their theoretical guarantees and computational cost. Previous work has
proved the completeness of the predicted safe region [34] and the optimality of the acquired policy[36], after a large number of samples. However, the computational cost of GP is known to be large.
Hence, it is hard to achieve theoretically guaranteed performance in a large environment.
Based on the fact that robots are equipped with sensors, it is more reasonable to formulate theproblem assuming that robots can obtain “feature vectors” for inferring the degree of safety of the35th Conference on Neural Information Processing Systems (NeurIPS 2021).

Non-smooth point

Feature

State

State
: Safety ✔

SafetySafety function

Safety function

Non-smooth point: Feature ✔ , Safety ✔
: Feature ✗ , Safety ✗: Safety ✗(a) Existing safe exploration.

: Feature ✔ , Safety ✗(b) Proposed safe exploration.

Figure 1: (a) Previous GP-based safe exploration under regularity assumptions, which fails to handle
non-smooth changes. (b) Our proposed feature-based safe exploration. In this problem setting, anagent predicts safety function value while using feature vector obtained by far-sighted observations.
(observable) states of their neighbors. This problem formulation is realistic for real-world robots, andit also allows us to deal with safety that changes steeply, which previous research could not handle(see Figure 1). Under this new problem setting, we aim to propose a theoretically guaranteed andempirically efficient safe RL algorithm that is applicable to real, large-scale problems.
Related Work
RL with (generalized) linear function approximation. Function approximation, especially thatbased on deep neural networks (DNNs), has been one of the main reasons for the success of RL
in recent years, and it has attracted more attention in both theory and practice [10, 32]. Given the
difficulty of theoretical analysis of DNNs, linear MDPs [19, 22] characterized by linear transition
kernels and reward are frequently used due to their tractability. The main interest of the theoreticalanalysis in existing studies has been the efficiency of RL algorithms. In fact, under the assumption of
linear MDPs, recent studies (e.g., Jin et al. [18], Yang and Wang [39]) have proposed algorithms witha theoretical guarantee regarding sample efficiency. Wang et al. [38] then extended Jin et al. [18] togeneralized linear model (GLM) settings and presented a practical and provably efficient algorithm
under strictly weaker assumptions.
Safe RL. A constrained MDP (CMDP, [4]) is a popular model for formulating safe RL problems.
In the CMDP formulation, an agent needs to maximize the expected cumulative reward while
ensuring that the expected cumulative cost is less than a threshold. There has been a number ofattempts to solve CMDPs [26], as represented by constrained policy optimization (CPO [2]), reward
constrained policy optimization [33], Lagrangian-based actor-critic [7, 9, 13], primal-dual policy
optimization [23, 39], and interior-point policy optimization [21]. As a recent, closely related work,
Ding et al. [14] proposed an algorithm with theoretical guarantees in regard to regret and constraint
violation for CMDPs with linear structures of transition, reward, and safety. In the previous papers
mentioned above, however, a safety constraint is defined over a horizon; hence, they deal with lessstrict safety constraints than our paper that requires the agent to satisfy safety constraints at every
time step. There has been research aimed at guaranteeing safety at every time step in both state-lessand stateful settings. For state-less settings, S AFE O PT [31] and S AFE -LUCB [5] were respectively
proposed for Bayesian optimization problems and linear stochastic bandit problems. For statefulsettings, Turchetta et al. [34] proposed a GP-based S AFE MDP algorithm that extends S AFE O PT tostateful settings. Under the assumptions of the deterministic transition and regularity of safety, while
Turchetta et al. [34] aimed to fully explore the safe region, Wachi et al. [37] proposed a GP-basedalgorithm for maximizing the cumulative reward under safety constraint.
Our Contributions
We model a new class of safe exploration problems where features are locally available within alimited sensor range. This is a realistic formulation for some real-world robots with sensors, andit allows us to get rid of the regularity and Lipschitz assumptions that previous safe exploration2

algorithms relied on. We develop safe policy optimization with a local feature (SPO-LF), an RL
algorithm that maximizes the cumulative reward under safety constraints while predicting reward andsafety function values on the basis of local features via GLMs. We analyze the theoretical propertiesof SPO-LF and prove that an agent will achieve a near-optimal policy with high probability whilesatisfying safety constraints at every time step. Finally, we evaluate our algorithm in two experiments.
In the first experiment using Gym-MiniGrid [12], we show that our algorithm is 1) more efficient interms of sample complexity and computational cost and 2) more applicable to large-scale problems
than previous, highly-theoretical GP-based methods. In the second experiment using Safety-Gym[25], we show that our algorithm achieves comparable performance in terms of the reward to several
notable safe RL baselines (e.g., CPO [2]) without executing even a single unsafe action.

2

Problem Formulation

We consider a safety-constrained MDP, defined as a tuple
M = hS, A, f, H, 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 the deterministic
state transition, and H ∈ N is the finite horizon. Also, r : S → [0, 1] and g : S → [0, 1] are bounded
reward and safety functions. We assume that both r and g are not known a priori.1 At every time stept ∈ N, the agent must be in a safe state. Specifically, for a state st , the safety function value g(st )must be above a threshold h ∈ (0, 1]; that is, the safety constraint is represented as g(st ) ≥ h.
In real applications, a robot is equipped with sensors and can infer the values of reward or safetyfunctions by using such measurements as “hints.” To formulate this mechanism, M contains two
additional functions. First, φ : S → Bd is an a priori unknown function for mapping a state s to ad-dimensional feature vector, where Bd := {x ∈ Rd | kxk ≤ 1}. For convenience, let φs := φ(s)denote the feature vector for a state s. Second, we define a function ψ : S → S for returning a set ofstates within the sensor range from a certain state. Note that, while conventional methods for solving
MDPs with linear function approximation assume the prior availability of the feature map for a wholestate space, we consider the problem where features are locally obtained upon observation.
Near-sighted and far-sighted observations. On the basis of the two functions φ and ψ, we
model two types of observation: near-sighted observation and far-sighted observation. Near-sighted
observation is associated with direct observations of reward and safety, which is commonly usedin typical RL settings including previous GP-based safe exploration studies. Using near-sighted
observations, the agent obtains a set of environmental information that contains noisy observationsof the reward and safety function values along with the feature vector for the current state. Thatis, the agent obtains ( st , φst , yr , yg ), where yr and yg are noisy observations of reward and safety,
which are represented as yr = r(s) + nrt and yg = g(s) + ngt , with independent zero-mean noises
nrt and ngt . Far-sighted observation is more related to feature vectors. In this observation scheme, anagent obtains features for ψ(s). For convenience, let Ψt ⊆ S denote the set of states that have been
observed at least once until time t; that is, Ψt := ψ(s0 ) ∪ ψ(s1 ) ∪ . . . ∪ ψ(st ). Intuitively, the agent
needs to predict the reward and safety function values by improving the internal GLMs on the basisof near-sighted observations and applying them to the features obtained by far-sighted observations.
Goal. The quality of a policy π : S → A is evaluated in terms of the cumulative reward achieved by
the agent under the safety constraint. The problem is formally written as
" H
#
X
π
maximize: VM(st ) = Eγ τ r(st+τ ) π
subject to: g(st ) ≥ h.
τ =0There are a number of previous studies on solutions to CMDPs, but most of them violate safety
constraints during training (e.g., [2]). In contrast, we require the agent to learn a policy in M
without even a single constraint violation. Without assumptions, it is intractable to solve the problem
mentioned above. In the following, we list assumptions in this paper.
Generalized linear function approximation. The first assumption is on the structure of the
reward and safety functions. In this paper, we are concerned with generalized linear models (GLMs)
regarding the reward and safety functions that are characterized by a feature vector.
1

For simplicity, we assume that the state transition function, f is known a priori. Note that it is not difficult
to extend our setting to a priori unknown f by referring to Biyik et al. [8].

3Assumption 1. The reward and safety functions are respectively represented using GLMs that arecharacterized by unknown coefficient vectors θr∗ , θg∗ ∈ Rd and fixed, strictly increasing link functionsµr , µg : R → [0, 1] such that∗
> ∗r(s) = µr (φ>s θr ) and g(s) = µg (φs θg ).

Note that linear and logistic models are the special cases of GLM with µ(x) = x and µ(x) = 1+e1−x ,respectively. To predict the coefficients, we obtain maximum likelihood estimators (MLEs) for
reward and safety functions as in Filippi et al. [15]. Let θ̃r and θ̃g be the MLEs for reward and safety,
respectively. Here, θ̃r and θ̃g are the unique solutions of the following equations.
tXr(sτ ) − µr (φ>sτ θr ) φsτ = 0 and

τ =0

t
X


g(sτ ) − µg (φ>sτ θg ) φsτ = 0.

τ =0

The optimal solutions of the above equations can be found efficiently using such standard algorithms
as Newton’s method. We additionally make an assumption on the properties of the link functions.
Assumption 2. Let  denote either r or g. The link function µ is twice differentiable, and the firstand second order derivatives are respectively bounded by L and M . Also, the link function µ
satisfies ξ = inf kθ −θ∗ k≤1,kφs k≤1 µ̇ (φ>s θ ) > 0.
Prior knowledge on safety. Without prior information on the states known to be safe, an agent
cannot guarantee safety at the first step. Hence, we make the following assumption.
Assumption 3. The agent is initially in a set of states, S0 ⊆ S, that is known to be safe a priori.
Sub-Gaussian noise. The final assumption is on the properties of the observation noise, which has
been commonly made in previous work (e.g., Abbasi-yadkori et al. [1]).
Assumption 4. Let  be either r or g. The noise nt is sub-Gaussian with fixed (positive) parameters



2 2

σ ; that is, for all t, we have E eω nt | Ft−1
≤ eω σ /2 , where{Fn } is increasing sequences of
sigma fields such that nt is Ft -measurable with E nt | Ft−1
= 0.

3

Preliminary: Defining True Safe SpaceIn this section, we ask and describe what the true safe space is. Since the agent observes noisy
measurements of reward and safety functions, it is impossible to know the exactly true reward andsafety functions. This is particularly critical when dealing with safety; thus, we aim to conservatively
estimate the safety function value up to a certain confidence  ∈ R≥0 . As discussed in Turchetta
et al. [34], to identify the safety of a state, we incorporate the safety constraint, reachability, andreturnability. Under our settings, however, an agent is allowed to observe the feature vector for
multiple neighboring states; hence, the existing definition of the true safe space cannot be directly
used. Hereinafter, we explain how to represent the true safe space in M.
First, we simply consider a set of states that satisfy the safety constraint with a margin of . Given theset of states X, the following region can be identified as safe based on the far-sighted observation.
Y (X) = X ∪ {s ∈ S | ∃s0 ∈ X, s ∈ ψ(s0 ) : g(s) −  ≥ h}.
Second, we define reachability. The agent may not be able to reach a state that is in Y (·) due tounsafe states in the middle of the pathway. Given a set X, the states in Ψ that are reachable fromX in one step are given by Yreach (X) = X ∪ {s0 ∈ Ψ | ∃s ∈ X, a ∈ A : s0 = f (s, a)}. Hence, ann−1n1n-step reachable operator is given by Yreach(X) = Yreach (Yreach(X)), where Yreach(X) = Yreach (X).
Finally, the set containing all the states that are reachable from X along an arbitrary long path in Ψ isndefined as Ȳreach (X) = limn→∞ Yreach(X). Finally, even after arriving at a state with reachability,
the agent may not have even a single option from among the viable actions for moving to anothersafe state. Hence, before moving to a state s, we should 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 setof states X in one step is given by Yreturn (X, X̄) = X̄ ∪ {s ∈ X | ∃a ∈ A : f (s, a) ∈ X̄}. Thus,
1nwith Yreturn(X, X̄) = Yreturn (X, X̄), an n-step returnability operator is given by Yreturn(X, X̄) =n−1
Yreturn (X, Yreturn (X, X̄)). The set containing all the states from which the agent can return to X̄ alongnan arbitrary long path in X is defined as Ȳreturn (X, X̄) = limn→∞ Yreturn(X, X̄).
4

To guarantee safety, all the above requirements must be satisfied. As such, we define Z(·):
Z (X) = Y (X) ∩ Ȳreach (X) ∩ Ȳreturn (Y (X), X).
The safe set after repeating such expansions n-times is Zn (X) = Z (Zn−1 (X)) with Z1 (X) =Z (X). Finally, the true safe space, Z̄ (X) is obtained by taking the limit in terms of n; that is,Z̄ (X) = limn→∞ Zn (X).

4

SPO-LF Algorithm

Our SPO-LF algorithm is outlined in Algorithm 1. On the basis of near-sighted andfar-sighted observations, an agent first calculates the upper and lower bounds of reward andsafety function values and predicts a safe region (lines 3 − 8). The agent then optimizes
its policy such that the cumulative reward ismaximized while guaranteeing safety. For thispurpose, the agent chooses the next state within
the pessimistically identified safe space though
this choice is basically based on the optimism
in the face of uncertainty (OFU) principle interms of reward (lines 9 − 11). However, weobserved a problem in that this pure approach
often causes the agent to get stuck in a rewardpoor state. As a work-around for this propose,
we additionally propose an algorithm, called
event-triggered safe expansion (ETSE) that encourages the agent to focus on the explorationof safety as necessary (lines 12 − 17). Note thatthe proofs of the lemmas are in Appendix C.
4.1

Algorithm 1 SPO-LF with ETSE
1: C0 (s) ← [h, ∞) for all s ∈ S0
2: loop
3: Ψt ← Ψt−1 ∪ O(st )4: Qt (s) ← (1), Ct (s) ← Qt (s) ∩ Ct−1 (s)5: lt (s) ← min Ct (s), ut (s) ← max Ct (s)6: St− ← {s ∈ S | lt (s) ≥ h}
7: St+ ← {s ∈ S | ut (s) ≥ h}
8: Xt− ← (2), Xt+ ← (3)9: J ∗ (st ) ← (4)10:
if arg maxs∈Yreach ({st }) J ∗ (s) ⊆ Xt− then11:
st+1 ← arg maxs∈(X − ∩Yreach ({st })) J ∗ (s)
t
12:
else
∗
13:
J¯ (st ) ← (5)14:while st 6= arg maxs∈X − J¯∗ (s) dot
15:
st+1 ← arg maxs∈Yreach ({st }) J¯∗ (s)16:
end while
17:
end if
18: end loop

Confidence Intervals

Since the reward and safety function values need to be “estimated” on the basis of the observations,
we aim to achieve a provably safe and optimal RL algorithm by calculating their upper and lower
bounds. Hence, we first derive theoretically guaranteed confidence intervals in terms of reward andsafety. Since the accuracy of the predictions depends on the availability of the feature vector, we
obtain the confidence bounds
letPtaccording to whether a state is inside or outside Ψt . Hereinafter, −1
the design matrix be Wt = τ =1 φsτ φ>
.
Also,
the
weighted
L
-norm
of
φ
associated
with
W
2
t
sτ
is given by kφkW −1 = (φ> Wt−1 φ)1/2 . Finally, the maximum and minimum singular values of atmatrix are denoted as λmax (·) and λmin (·).
Confidence intervals inside Ψt . For all s in Ψt , the agent has an observed feature vector; hence,
the reward and safety function values can be estimated more accurately by leveraging it. On the basisof Theorem 1 in Li et al. [20], we have the following lemma.
pLemma 1. (Thm. 1 in [20]). Let δ > 0 be given and β = 3Lξσ log(3/δ ). Assume λmin (Wt ) ≥512σ2 M2 ξ−4 d2 + log δ−1 . Then, with a probability of at least 1 − δ , the MLE satisfies|  (s) − µ (φ>s θ̃ ) | ≤ β · kφs kW −1 .
t

The symbol  denotes either r or g; that is, Lemma 1 respectively holds for reward and safety.
Confidence intervals outside Ψt . For s outside Ψt , the agent does not know even the feature vector.
To obtain the confidence intervals outside Ψt , we should incorporate any possible feature vector;
hence, confidence bounds are rather loose as presented below.
Lemma 2. Let  denote either r or g. Assume λmin (Wt ) ≥ 512 · σ2 M2 ξ−4 d2 + log δ−1 . Then,with a probability of at least 1 − δ , for any s ∈ S \ Ψ, we have0 ≤ (s) ≤ µ (kθ̃ k) + β · λmax (Wt−1 ).
5The next lemma is on the relation between the upper bound defined above and the threshold, h.
Lemma 3. Assume λmin (Wt ) ≥ 512 · σg2 Mg2 ξg−4 d2 + log δg−1 . Then, with a probability of at least
1 − δg , we have µg (kθ̃g k) + βg · λmax (Wt−1 ) ≥ h.
Efficiency metric of exploration. Because βr and βg are constants independent from s, theefficiency of the exploration of the reward and safety functions depends solely on kφkW −1 within Ψttand λmax (Wt−1 ) outside Ψt . Hence, useful actions for exploring the reward also contribute to the
exploration of safety. This is an advantage in leveraging feature vectors in safe RL problems, and it
leads to more efficient policy optimization compared with previous work such as Wachi and Sui [36]that requires the agent to explore the two functions separately.
Assumption on λmin (Wt ). As discussed in Li et al. [20], the assumption on λmin (Wt ) is satisfied
under mild conditions. However, since we consider a safe exploration problem, it is extremely
important to know how to ensure that the assumption on λmin (Wt ) is valid. This paper presents two
methods; the first is to provide (typically a small number of) data for initializing GLMs, and thesecond is to prepare a sufficiently large S0 and prohibit the agent from going outside of S0 , until thecondition on λmin (Wt ) holds. In our experiment, we simply took the first approach.
4.2

Prediction of Safe Space

We now define two types of predicted safe space where safety is identified either optimistically or
pessimistically, as discussed in Turchetta et al. [35]. First, we define the lower and upper bounds ofsafety. By Lemma 1 and 2, the confidence bounds on safety are represented as([ µg (φ>if s ∈ Ψt ,s θ̃g ) ± βg · kφs kWt−1 ]Qt (s) =(1)−1[ 0, µg (kθ̃g k) + βg · λmax (Wt ) ] otherwise.
We consider the intersection of Qt up to iteration t, which is defined as Ct (s) = Qt (s) ∩ Ct−1 (s),where C0 (s) = [h, ∞] for all s ∈ S0 . The lower and upper bounds on Ct (s) are denoted bylt (s) := min Ct (s) and ut (s) := max Ct (s), respectively.
Predicted pessimistic safe space. We now define the predicted pessimistic safe space. We firstconsider a set of states such that the safety constraint is satisfied with high probability. It is formulatedusing lt ; that is,St− := { s ∈ S | lt (s) ≥ h }.
The desired pessimistic safe space, Xt− is a subset of St− and also satisfies the reachability andreturnability constraints; that is,−−
Xt− = St− ∩ Ȳreach (Xt−1) ∩ Ȳreturn (St− , Xt−1).

(2)

Predicted optimistic safe space. To optimize a policy, we need to incorporate the reward not onlyin Xt− but also in a region that contains all the states that may turn out to be safe even with a small
probability. We consider the set of states that may satisfy the safety constraint even with a small
probability, which is represented as
St+ := { s ∈ S | ut (s) ≥ h }.
Note that, by Lemmas 2 and 3, for all states in S \ Ψt , the upper and lower confidence bounds in termsof safety satisfy lt (s) < h ≤ ut (s). Hence, all states in S \ Ψt are identified as pessimistically unsafe
but optimistically safe. Similarly to the pessimistic safe region, we again incorporate reachability andreturnability. The resulting optimistic safe region is given by++
Xt+ = St+ ∩ Ȳreach (Xt−1) ∩ Ȳreturn (St+ , Xt−1
).

4.3

(3)

Safe Policy Optimization based on OFU Principle

As discussed in Section 4.1, we can efficiently explore reward and safety simultaneously by focusing
on kφkW −1 and λmax (Wt−1 ). Hence, it turns out that we only need to balance exploration andt6exploitation in terms of reward. For balancing 1) the exploration of reward and safety and 2) the
exploitation of reward, we solve a Bellman equation on the basis of the OFU principle:(µr (φ>
if s ∈ Ψt ,s θ̃r ) + βr kφs kWt−1∗∗
J (st ) = max+ R(s) + γJ (s) where R(s) :=(4)µr (kθ̃r k) + βr λmax (Wt−1 ) otherwise.
s∈Xt
Note that R(s) represents the upper confidence bound with regard to reward. The next state to visit
should be pessimistically safe and reachable from st with one step; that is,s∗t+1 =
arg maxJ ∗ (s).
s∈(Xt− ∩Yreach ({st }))Problem with this approach. We observed that the above algorithm often causes the agent to getstuck in a state with a (relatively) small reward. The reason for this problem is as follows. Whenthe state with the maximum J ∗ is outside Xt− , the agent must execute the “second-best” action. The
second-best solution is often the one where the agent tries to take the stay action and then visit s∗t+1 ;then, the agent continues to stay at the current state.
Event-triggered safe expansion. To address the above problem, we propose an algorithm called
event-triggered safe expansion (ETSE). We first defineη := arg max J ∗ (s),s∈Yreach ({st })meaning the state that the agent will visit if there is no safety constraint. The ETSE algorithm
is triggered only when s∗t+1 6= η. Intuitively, if η is within Xt− , the agent can simply execute thenext optimal action to visit s∗t+1 ; hence, the above problem arises only if s∗t+1 6= η is satisfied.
This algorithm focuses on expanding the pessimistic safe region by visiting the states with a large
uncertainty.
J¯∗ (st ) = max − kφst+1 kW −1 + γ J¯∗ (st+1 ) .
(5)t

st+1 ∈Xt

On the basis of (5), the agent plans the trajectory so as to gain a lot of information, and the ETSE continues until the agent arrives at the state with the highest uncertainty. Once the ETSE finishes being
applied, the agent aims to handle the exploration and exploitation dilemma by solving (4).

5Theoretical Analysis

In this section, we present the theoretical results obtained for our SPO-LF. As a preliminary for the
results, let us define the time step t∗ , which can be used as an indicator that the agent has sufficiently
understood the models of reward and safety. We now present the following lemma regarding t∗ .
Lemma 4. Let C1 and C2 be positive, universal constants. Also, let t∗ denote the smallest integer
satisfying


q
√
βg
,1
λmin (Σ)t − C1 td − C2 t log(δg−1 ) ≥ max
∗with Σ = E[ φt φ>
].
Then,
for
all
t
>
t
,
the
following
inequalities
hold.
t
s


t+H
X
t+H
> ∗
>
| µg (φ θg ) − µg (φ θ̃g ) | ≤  andkφsτ kWτ−1 ≤ 2Hd log.
dτ =t+1
Finally, we present two main theorems. The first theorem is on the satisfaction of the safety constraint,
and the second is on the near-optimality of the acquired policy.
Theorem 1. Assume that the noise of safety is σg -sub-Gaussian and λmin−(Wt ) ≥ 512 ·
2
2 −4
2
−1
σg Mg ξg d + log δgholds. Suppose that the next state is chosen from Xt . Then, the following statement holds with a probability of at least 1 − δg :∀t ≥ 0, g(st ) ≥ h.
The proof is in Appendix E. The agent chooses the next state to visit within Xt− (⊆ St− ), and St−
is characterized with l(s). Since g(s) is greater than l(s) with a probability of at least 1 − δg , ouralgorithm guarantees that the agent will execute only safe actions.2
2
Unlike Turchetta et al. [34] or Wachi and Sui [36], this paper does not provide a theory on the completeness(i.e., convergence to the true safe region) of the predicted safe region. This is because our algorithm explores
safety as a result of balancing exploration and exploitation for reward, which contributes to its sample-efficiency.

7

Theorem 2. Set T ∗ = t∗ + |Z̄0 (S0 )| andsV = Vmax · δg + βr (δr ) 2Hd log


t+H
,
d

where Vmax is the upper bound of the value function. Assume that the noise of reward and safety is
sub-Gaussian and H > T ∗ . Then, with high probability,
V πt (st ) ≥ V ∗ (st ) − εV ,— i.e., the algorithm is εV -close to the optimal policy — for all but T ∗ time steps while guaranteeing
safety with a probability of at least 1 − δg .
The proof is in Appendix E. An outline of the proof is as follows. At each iteration, the agent
encounters one out of the following two events. In one event, the ETSE algorithm is not triggered,and the agent can execute an action to purely optimize its policy. In the other event, s∗t+1 6= η issatisfied, and the agent focuses on exploring the safe regions. The worst case scenario for the sample
efficiency is when the second event continues to occur; that is, the agent is required to explore thewhole safe space. However, after a sufficiently large number of time steps greater than T ∗ , the agent
can achieve an εV -close policy by deciding the next action on the basis of the OFU principle in a
fully-explored safe region. Note that, in the case of a short horizon, the agent cannot achieve thenear-optimal policy; hence, we assume H > T ∗ .

6

Experiments

We evaluate the performance of our SPO-LF in two experiments. In the first experiment using GymMiniGrid [12], we show that our algorithm is better than existing ones backed by theory including [36]in terms of sample efficiency and scalability. In the second experiment based on Safety-Gym [25],we compare our algorithm with advanced deep RL algorithms incorporating constraints. We also
demonstrate the effectiveness of the ETSE algorithm. For future research, our code is open-sourced.3
6.1

Grid World

Settings. We constructed a simulation environment based on Gym-MiniGrid [12]. We considered a
25 × 25 grid in which each grid was associated with a randomly generated feature vector with thedimension d = 5. Coefficients for reward and safety were also randomly generated; thus, true reward
and safety function values were allocated to each grid along with a feature vector. At every time
step, an agent chose the next action from five candidates: stay, up, right, down, and left. The agent
predicted the reward and safety functions while learning the relationship between the feature vector
and the two functions with GLMs. In this simulation, we allowed the agent to 1) observe the feature
vector in the 7 × 7 neighboring grids that are in the front of the agent and 2) obtain the feature vector
and noisy measurements of the reward and safety values at the current state. As prior information,
the agent received 10 samples of (φ, g), to initialize the internal GLM model regarding safety. We
considered a linear model with µ(x) = x for both reward and safety. Finally, we set γ = 0.999,
δr = δg = 0.05, and h = 0.1, and optimized a policy with policy iteration.
We compared our SPO-LF with the following six baselines. The first is called O RACLE, and it
has a non-exploratory agent who knows the true reward and safety functions a priori. The second
is called U NSAFE GLM, in which a safety-agnostic agent maximizes a cumulative reward on thebasis of GLMs. The third is called R ANDOM, in which an agent randomly chooses the next action.
The last three baselines are all stepwise approaches as in Wachi and Sui [36]. The fourth baseline isS TEP SAFE GLM, in which an agent first expands the safe region and then optimizes the cumulative
reward in the certified safe region while learning the reward and safety function structures via GLMs.
The fifth is GP ( FEATURE ), which is a GP-based stepwise safe exploration and optimization where
the inputs of GP are d-dimensional feature vectors. The final baseline is called GP ( STATE ), a
stepwise approach proposed in Wachi and Sui [36] under the assumption that the reward and safetyfunctions have regularity with regard to state. We used the reward and the number of unsafe actions
as evaluation metrics.
3

https://github.com/akifumi-wachi-4/spolf

8

SPO-LF (FOV 1 x 1)
SPO-LF (FOV 3 x 3)
SPO-LF (FOV 7 x 7)(feature)

SPO-LF (FOV 10 x 10
10)
SPO-LF (FOV 13 x 13)
Oracle(a)(b)

Figure 2: (a) Comparison of performance of SPO-LF and baselines. Standard error is shown as
shaded area. (b) Comparison of performance of the SPO-LF with different sizes of field of view.

Results. Figure 2(a) compares the performance with regard
to the cumulative reward of each algorithm. SPO-LF,
U NSAFE GLM, S TEP SAFE GLM, and GP ( FEATURE )achieved a near-optimal policy. The convergence of SPOLF was faster than S TEP SAFE GLM and GP ( FEATURE )but slower than U NSAFE GLM. This is because SPO-LF
could not always execute the optimal action for maximizing
the cumulative reward to guarantee safety. Also, without
ETSE, the agent often got stuck in a state with a nonoptimal reward. Figure 2(b) compares the performance of
SPO-LF with different sizes of field of view (FOV) from Figure 3: Computational time of GLM1 × 1 to 13 × 13. For a larger FOV, the convergence of based SPO-LF and GP-based algothe algorithm got faster. Given that SPO-LF (FOV 1 × 1) rithm (i.e., Wachi and Sui [36]).
corresponding to previous work (e.g., [34, 36]) dealt with
only near-sighted observations, it is useful to incorporate
far-sighted observations as in our new framework. Figure 3 compares the computational time fordifferent environment sizes. SPO-LF is more scalable and applicable to large-scale problems giventhat the GP-based algorithms did not run in a reasonable amount of time for large environments
such as that with 150 × 150 states. In the GLM-based methods, most of the computational costwhen obtaining confidence bounds is for calculating λmax (Wt−1 ). This computational complexity isO(d3 ), which does neither depend on the number of states nor samples. Finally, the average numberof unsafe actions was 3.4 for U NSAFE GLM, 49.0 for R ANDOM, and 0.0 for the other methods.
6.2

Safety-Gym

Settings. The second experiment was based on Safety-Gym [25] with continuous state and action
spaces. The objective of this experiment was to compare our SPO-LF with several notable safe
RL algorithms including CPO [2], PPO-Lagrangian, and TRPO-Lagrangian. The last two baselines
are ones that introduce that Lagrangian method into a safety-agnostic algorithm (i.e., PPO [29] andTRPO [28]) to incorporate constraints (for more details, see Section 5 in Ray et al. [25]). In thisexperiment, as shown in Figure 4(a), one goal (in green) and multiple hazards (in blue) were randomly
placed, and the agent (in red) needed to reach the goal without visiting hazards. For encouraging
the agent to reach the goal, we set two kinds of reward: 1) a reward of 1.0 when arriving at the goaland 2) a reward of 0.01 · ∆goal when getting closer to the goal, where ∆goal is the amount of decreasein distance from the goal. To implement SPO-LF, we discretized the environment into 50 × 50
grids and used a computationally inexpensive policy iteration algorithm proposed in Scherrer et al.
[27] for policy optimization. The feature vector φ was constructed by LiDAR observations (i.e., thedistance from the goal or hazards). Since reward and safety function values vary steeply according
to the existence of the goal or hazards, we use the sigmoid function µ(x) = 1+e1−x as the linkfunction. As for implementing the three baselines, our experiments largely depended on the “safetystarter-agent” repository (https://github.com/openai/safety-starter-agents.git). For
9(a) Environment(b) Reward(c) Number of unsafe actions

Figure 4: Experiment with Safety-Gym. (a) Example screen capture from our simulation environment
with a goal and hazards. (b) Average reward over episodes. (c) Number of unsafe actions per episode.
Note that our SPO-LF did not execute even a single unsafe action.

the initialization, we provided all the agents with 40 reward and safety samples as prior information.
For more detailed experimental settings, see Appendix F.
Results. Figures 4(b) and 4(c) show the experimental results. We used the reward and the number ofunsafe actions as evaluation metrics and calculated the mean and standard error after running eachmethod 200 times. As shown in Figure 4(b), our SPO-LF exhibited comparable performance to thebaselines with regard to the sample efficiency. However, our algorithm did not execute even a single
unsafe action, while the other three methods optimized their policies while making mistakes.

7

Conclusion

We formulated a new problem characterized by safety-constrained MDPs with local feature and thenproposed the SPO-LF algorithm for safely optimizing a policy in an a priori unknown environment.
SPO-LF efficiently and safely optimizes a policy by leveraging feature information while expanding
the safe space as necessary by using the ETSE algorithm. Theoretical analysis showed that ouralgorithm obtains a near-optimal policy while guaranteeing safety, with a high probability. Our
experiments showed that our algorithm 1) achieved better efficiency and scalability than previous safe
exploration methods with theoretical guarantees and 2) behaved more safely than existing advanced
deep RL methods with constraints.
We consider that our proposed method compensates for the shortcomings of safe RL methods withtheoretical guarantees (e.g., [34], [36]) and advanced deep RL methods (e.g., [2]), which potentiallysets out a research direction to bridge the gap between two distinct methods. However, there areseveral neglected problems we as the community should address in future work. One of the biggest
problems is that our proposed algorithm (that is more scalable than highly-theoretical ones) is
still far from practical in real applications with continuous state and action spaces. It would be
an interesting direction to develop as scalable algorithm as advanced deep RL algorithms while
maintaining theoretical safety guarantee.
Finally, we believe that safety is an essential requirement for applying RL in many real problems andhave not found any negative societal impact of our algorithm. However, we need to remain awarethat any sequential decision-making algorithms are vulnerable to misuse and ours is no exception.

Acknowledgments
We deeply appreciate the anonymous reviewers for constructive comments. This work is partially
funded by Tsinghua GuoQiang Research Institute.

References[1] Abbasi-yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic
bandits. In Neural Information Processing Systems (NeurIPS).
10[2] Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017). Constrained policy optimization. In
International Conference on Machine Learning (ICML).
[3] Alshiekh, M., Bloem, R., Ehlers, R., Könighofer, B., Niekum, S., and Topcu, U. (2018). Safe
reinforcement learning via shielding. In AAAI Conference on Artificial Intelligence (AAAI).
[4] Altman, E. (1999). Constrained Markov decision processes, volume 7. CRC Press.
[5] Amani, S., Alizadeh, M., and Thrampoulidis, C. (2019). Linear stochastic bandits under safety
constraints. In Neural Information Processing Systems (NeurIPS).
[6] Berkenkamp, F., Turchetta, M., Schoellig, A., and Krause, A. (2017). Safe model-based reinforcement learning with stability guarantees. In Neural Information Processing Systems (NeurIPS).
[7] Bhatnagar, S. and Lakshmanan, K. (2012). An online actor–critic algorithm with function
approximation for constrained markov decision processes. Journal of Optimization Theory andApplications, 153(3):688–708.
[8] Biyik, E., Margoliash, J., Alimo, S. R., and Sadigh, D. (2019). Efficient and safe exploration in
deterministic markov decision processes with unknown transition models. In American Control
Conference (ACC). IEEE.
[9] Borkar, V. S. (2005). An actor-critic algorithm for constrained markov decision processes.
Systems & control letters, 54(3):207–213.
[10] Bradtke, S. J. and Barto, A. G. (1996). Linear least-squares algorithms for temporal difference
learning. Machine learning, 22(1):33–57.
[11] Cheng, R., Orosz, G., Murray, R. M., and Burdick, J. W. (2019). End-to-end safe reinforcement
learning through barrier functions for safety-critical continuous control tasks. In AAAI Conferenceon Artificial Intelligence (AAAI).
[12] Chevalier-Boisvert, M., Willems, L., and Pal, S. (2018). Minimalistic gridworld environment
for OpenAI gym. https://github.com/maximecb/gym-minigrid.
[13] Chow, Y., Ghavamzadeh, M., Janson, L., and Pavone, M. (2017). Risk-constrained reinforcement
learning with percentile risk criteria. Journal of Machine Learning Research (JMLR), 18(1):6070–
6120.
[14] Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M. (2021). Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligenceand Statistics (AISTAT).
[15] Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The
generalized linear case. In Neural Information Processing Systems (NeurIPS).
[16] Fulton, N. and Platzer, A. (2018). Safe reinforcement learning via formal methods: Toward safe
control through proof and learning. In AAAI Conference on Artificial Intelligence (AAAI).
[17] Garcıa, J. and Fernández, F. (2015). A comprehensive survey on safe reinforcement learning.
Journal of Machine Learning Research (JMLR), 16(1):1437–1480.
[18] Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learningwith linear function approximation. In Conference on Learning Theory (COLT).
[19] Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). A contextual-bandit approach topersonalized news article recommendation. In International Conference on World Wide Web(WWW).
[20] Li, L., Lu, Y., and Zhou, D. (2017). Provably optimal algorithms for generalized linear
contextual bandits. In International Conference on Machine Learning (ICML).
[21] Liu, Y., Ding, J., and Liu, X. (2020). Ipo: Interior-point policy optimization under constraints.
In AAAI Conference on Artificial Intelligence (AAAI).
11[22] Osband, I., Van Roy, B., and Wen, Z. (2016). Generalization and exploration via randomized
value functions. In International Conference on Machine Learning (ICML).
[23] Paternain, S., Calvo-Fullana, M., Chamon, L. F., and Ribeiro, A. (2019). Safe policies forreinforcement learning via primal-dual methods. arXiv preprint arXiv:1911.09101.
[24] Rasmussen, C. E. (2004). Gaussian processes in machine learning. In Advanced Lectures on
Machine Learning, pages 63–71. Springer.
[25] Ray, A., Achiam, J., and Amodei, D. (2019). Benchmarking safe exploration in deep reinforcement learning. OpenAI.
[26] Satija, H., Amortila, P., and Pineau, J. (2020). Constrained markov decision processes via
backward value functions. In International Conference on Machine Learning (ICML).
[27] Scherrer, B., Ghavamzadeh, M., Gabillon, V., and Geist, M. (2012). Approximate modified
policy iteration. In International Conference on Machine Learning (ICML).
[28] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015). Trust region policy
optimization. In International Conference on Machine Learning (ICML).
[29] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy
optimization algorithms. arXiv preprint arXiv:1707.06347.
[30] Strehl, A. L. and Littman, M. L. (2005). A theoretical analysis of model-based interval
estimation. In International Conference on Machine Learning (ICML).
[31] Sui, Y., Gotovos, A., Burdick, J. W., and Krause, A. (2015). Safe exploration for optimization
with Gaussian processes. In International Conference on Machine Learning (ICML).
[32] Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machinelearning, 3(1):9–44.
[33] Tessler, C., Mankowitz, D. J., and Mannor, S. (2018). Reward constrained policy optimization.
arXiv preprint arXiv:1805.11074.
[34] Turchetta, M., Berkenkamp, F., and Krause, A. (2016). Safe exploration in finite Markov
decision processes with Gaussian processes. In Neural Information Processing Systems (NeurIPS).
[35] Turchetta, M., Berkenkamp, F., and Krause, A. (2019). Safe exploration for interactive machinelearning. In Neural Information Processing Systems (NeurIPS).
[36] Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained Markov decision
processes. In International Conference on Machine Learning (ICML).
[37] Wachi, A., Sui, Y., Yue, Y., and Ono, M. (2018). Safe exploration and optimization of constrained
MDPs using Gaussian processes. In AAAI Conference on Artificial Intelligence (AAAI).
[38] Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2019). Optimism in reinforcement
learning with generalized linear function approximation. In International Conference on Learning
Representation (ICLR).
[39] Yang, L. and Wang, M. (2020). Reinforcement learning in feature space: Matrix bandit, kernels,
and regret bound. In International Conference on Machine Learning (ICML).

12

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper’s
contributions and scope? [Yes](b) Did you describe the limitations of your work? [Yes] Please see the second paragraphin Conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Please see
the third paragraph in Conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms tothem? [Yes]2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions
are listed in Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] Proof sketches are in
the main paper and full proofs are in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] We attached
the source-code as supplementary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they
were chosen)? [Yes](c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes](d) Did you include the total amount of compute and the type of resources used (e.g., typeof GPUs, internal cluster, or cloud provider)? [Yes]4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes](b) Did you mention the license of the assets? [Yes](c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
The source code is attached as a supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you’reusing/curating? [N/A](e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if
applicable? [N/A](b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A](c) Did you include the estimated hourly wage paid to participants and the total amountspent on participant compensation? [N/A]13

AppendicesA. Summary of Upper and Lower Bounds.
For easy understanding, we summarize the upper and lower bounds in terms of reward and safety,
inferred by GLMs.
Table 1: Confidence bounds of reward and safety functions.
s ∈ Ψt ( FEATURE AVAILABLE )s∈/ Ψt ( FEATURE UNAVAILABLE )[ µ(φ>s θ̃r ) ± βr · kφs kWt−1 ][ µ(φ>s θ̃g ) ± βg · kφs kW −1 ][ 0, µ(kθ̃r k) ± βr · λmax (Wt−1 ) ][ 0, µ(kθ̃g k) + βg · λmax (Wt−1 ) ]R EWARDS AFETYt

B. Preliminary Lemma
Lemma 5. 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 f1 (x) and f2 (x), the following inequalities hold:max{f2 (x) − f1 (x)} + max f1 (x) ≥ max f2xxx

max f1 (x) − max f2 (x) ≥ − max{f1 (x) − f2 (x)}xxx= min{f1 (x) − f2 (x)}.
xThen, the desired lemma is obtained.

C. Lemmas on GLMs
C.0. Preliminary lemma on GLMs
Lemma 6. Let θg∗ be the true coefficient for safety. Then, we have µg (kθg∗ k) ≥ h.
Proof. By Cauchy–Schwarz inequality, for all φs such that kφs k ≤ 1, the following inequality
holds:∗kθg∗ k ≥ φ>s θg .
By Assumption 1, µg (·) is a strictly increasing function; that is,∗µg (kθg∗ k) ≥ µg (φ>s θg ).

Assumption 3 implies that there exists φs such that∗µg (φ>s θg ) ≥ h.

Therefore, we obtained the desired lemma.
C.1. Proofs of Lemma 1
Proof. See Theorem 1 in Li et al. [20].
14C.2. Proof of Lemma 2
Proof. First, we obtain the upper bound of (s) for any s ∈ S. Let φ∗,s be the feature for achieving
the maximum value of . Then, the following chain of equations hold, with a probability of at least
1 − δ :max (s) = µ (hφ∗,s , θ∗ i)s∈S≤ µ (hφ∗,s , θ̃ i) + β · kφ∗,s kWn−1≤ µ (kθ̃ k) + β · kφ∗,s kWn−1≤ µ (kθ̃ k) + β · λmax (Wn−1 ).
In the above chain of inequalities, we used Cauchy–Schwarz inequality and kφ∗,s k ≤ 1 in the secondline and then used kφ∗,s kWn−1 ≤ λmax (Wn−1 ) in the third line.
The lower bound can be simply obtained by definition; that is,min (s) ≥ 0.
s∈S

Then, we have the desired lemma.
C.3. Proof of Lemma 3
Proof. By Lemma 2, with a probability of at least 1 − δg , we have the following inequality in termsof the confidence bounds of the safety function:
0 ≤ max g(s) ≤ µg (kθ̃g k) + βg · λmax (Wn−1 ).
s∈SAlso, by combining Lemma 6 andµg (kθg∗ k) ≤ µg (kθ̃g k) + βg · λmax (Wn−1 ),we haveh ≤ µg (kθg∗ k) ≤ µg (kθ̃g k) + βg · λmax (Wn−1 ).
Finally, we obtained the desired lemma.
C.4. Proof of Lemma 4
Proof. For all t > t∗ , the following chain of inequalities hold:


−1

q
√

−1
, 1 ≥ λmin (Σ)t − C1 td − C2 t log(δg )minβg≥ λmax (Wn−1 ).
In the above calculation, we used Lemma 1 in Li et al. [20] and λmax (Wn−1 ) = λmin1(Wn ) . Therefore,
the following two statements are satisfied. First, because we have βg λmax (Wn−1 ) ≤ , the following
inequalities hold:| µg (φ> θg∗ ) − µg (φ> θ̃g ) | ≤ βg λmax (Wn−1 )≤ .
Second, by Lemma 2 in Li et al. [20], the following inequality holds under the condition that
λmax (Wn−1 ) ≤ 1:
s


t+H
X
t+H
kφsτ kWτ−1 ≤ 2Hd log.
dτ =t+115

D. Lemmas on Near-optimality
Lemma 7. Let J ∗ (st ) be the value function calculated by our algorithm. Then, J ∗ (st ) satisfies thefollowing inequality:J ∗ (st ) ≥ V ∗ (st ).
Proof. Let IZ : S → {0, 1} denote the following safety indicator function:1
if s ∈ Z̄g (S0 ),IZ (s) :=0
otherwise.

(6)

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

max
st+1 ∈Z̄g (S0 )max
st+1 ∈Z̄g (S0 )[ R(st+1 ) + γJ ∗ (st+1 ) ] −∗[ r(st+1 ) + γVM(st+1 ) ]max
st+1 ∈Z̄g (S0 )∗[ r(st+1 ) + γVM(st+1 ) ]∗= max [ IZ (st+1 ){R(st+1 ) + γJ ∗ (st+1 )} ] − max [ IZ (st+1 ){r(st+1 ) + γVM(st+1 )} ]
st+1

st+1

≥ min [ IZ (st+1 ){R(st+1 ) − r(st+1 )} + γIZ (st+1 ){J ∗ (st+1 ) − V ∗ (st+1 )} ] .
st+1

The second line follows from Xt+ ⊇ Z̄g (S0 ), and the third line follows from the definition of IZ .
Also, the fourth line follows from Lemma 5. By definition of R(s), the following equation holdswith a probability of at least 1 − δ r :min[ J ∗ (st ) − V ∗ (st ) ] ≥ γ · min [ IZ (st+1 ){J ∗ (st+1 ) − V ∗ (st+1 )} ]
st

st+1

Repeatedly applying this equation proves the desired lemma. Therefore, we haveJ ∗ (st ) ≥ V ∗ (st )with high probability.
Lemma 8. (Generalized induced inequality) Let φ, r, g and φ̂, r̂, ĝ be the feature and reward
function (including the exploration bonus) and safety function that are identical on some set of statesΩ — i.e., φ = φ̂, r = r̂, and g = ĝ for all s ∈ Ω. Let P (AΩ ) be the probability that a state not in Ω
is generated when starting from state s and following a policy π. Assume value is bound in [0, Vmax ],then
V π (r, s, φ, g) ≥ V π (r̂, s, φ̂, ĝ) − 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 and Littman [30].
Lemma 9. Suppose that the agent optimizes the policy based on our SPO-LF. After T ∗ time step,
let AΩ be the event in which the agent escapes from Ω. Then, for all t > T ∗ , we have
P (AX − ) ≤ δg .
t

Proof. Hereinafter, let q̄t be the sequence of states planed by the policy πt obtained by the algorithm
at time t: that is,q̄t := { s̄t , s̄t+1 , . . . , s̄t+H },where s̄t = st and s̄t+τ +1 = f (s̄t+τ , πt (s̄t+τ )) for all τ ∈ [0, H − 1].
First, let us consider the case that prediction of the safety function values are collect, which occurs
with a probability of at least 1 − δg (we call E VENT A). While the agent optimizes its policy, one of
the following two events happens.
• E VENT A-1: q̄t ⊆ Xt− .
16• E VENT A-2: q̄t * Xt− .
When E VENT A-1 occurs, the optimal policy calculated based on the current information can beobtained only in Xt− . Hence, the agent will not go outside Xt− as far as it follows the current policy.
The worse-case for the agent is when E VENT A-2 continues to occur and the ETSE algorithm
is triggered at every time step. Even under this worst condition, however, after t∗ time steps, theconfidence interval on safety is bounded by  and then the agent can identify whether or not a state issafe immediately on the basis of far-sighted observations. After the agent learns the safety function
model up to -accuracy, it takes at most T ∗ − t∗ = |R0 (S0 )| time steps until Xt− is sufficiently
expanded.
Second, if the prediction of safety is wrong, we cannot avoid the situation that the agent escapes fromXt− , which occurs with a probability of at most δg .
In summary, for all t > T ∗ , only if the prediction of safety is inaccurate, the agent may go outsideof Xt− . This event (i.e., Event B) happens with a (small) probability at most δg . Hence, the desired
lemma is now proved.

E. Main Theorems
E.1. Proof of Theorem 1
Proof. By Lemma 1 and Lemma 3, for all s ∈ S, with a probability of at least 1 − δg , we haveg(s) ≥ l(s).
Our SPO-LF requires the agent to visit only the state satisfying l(s) ≥ h; hence, the safety constraintg(s) ≥ his satisfied with a probability of at least 1 − δg .
E.2. Proof of Theorem 2
Proof. Define r̃ and g̃ as the reward function (with the exploration bonus) and safety function, which
are used by the SPO-LF. Let r̂ be a reward function equal to r on Ω and equal to r̃ elsewhere.
Furthermore, let π̃ be the policy followed by the SPO-LF at time t, that is, the policy calculated on
the basis of the feature φ and predicted reward r̃ and safety g̃ inferred by the predicted coefficients,(i.e., θ̃r and θ̃g ). Finally, let AΩ be the event in which π̃ escapes from Ω. Then, by Lemma 8, we haveV πt (r, st , φst , g) ≥ V π̃ (r̂, st , φst , g) − Vmax P (AΩ ).
In addition, note that, for all t ≥ t∗ and st ∈ Xt− , because r̂ and r̃ differ by at most βg kφst kW −1 ateach state,
HX| V π̃ (r̂, st , φst , g̃) − V π̃ (r̃, st , φst , g̃) | ≤βr kφst+τ kW −1τ =1= βr ·

HX

kφst+τ kW −1τ =1≤ βr ·

p
2Hd log ((t + H)/d).

(7)Here, consider the case of Ω = Xt−∗ . Once the safe region is fully explored, P (AX −∗ ) ≤ δg holdst∗after T time steps. Then, the following chain of equations and inequalities holds:
V πt (r, st , φst , g) ≥ V π̃ (r̂, st , φst , g) − Vmax · P (AΩ )= V π̃ (r̂, st , φst , g) − Vmax · P (AX − )≥ V π̃ (r̂, st , φst , g) − Vmax · δgp
2Hd log ((t + H)/d)p∗= JX (r̃, st , φst , g) − Vmax · δg − βr · 2Hd log ((t + H)/d)p≥ V ∗ (r, st , φst , g) − Vmax · δg − βr · 2Hd log ((t + H)/d)≥ V π̃ (r̃, st , φst , g) − Vmax · δg − βr ·17

In this derivation, the second line follows from the assumption of Ω = X − , the third line follows
from P (AX − ) ≤ δg , the fourth line follows from (7), the fifth line follows from the fact that π̃ isprecisely the optimal policy for R̃ and b, the sixth line follows from Lemma 7, and the final line
follows from the definition of V .

F. Additional Information on Experiments
Note that the source code we used for our experiment is in the supplemental material. Also, a video
to illustrate how our SPO-LF works is in the supplementary material.
F.1. Grid World
The source code for this experiment is contained in “grid_world” directory. In this experiment, weused Intel(R) Xeon(R) Gold 6248 CPU with 512 GB RAM. The number of iteration was 400. We
used the following parameters as mentioned in the main paper, which are same throughout every
method: γ = 0.999, δr = 0.05, δg = 0.05, h = 0.1, d = 5. For getting the results in Figure 2, we
ran the simulation 100 times and calculated the mean and standard error for every method. Whenobtaining the Figure 3, due to the computational cost, we reduced γ and number of simulation to 0.98
and 5, respectively. Example screen shot of our simulation environment is shown in Figure 5.

Figure 5: Example screenshot of our grid world experiment.
F.2. Safety-Gym
We present the detailed information regarding our experiments using Safety-Gym [25]. In thisexperiment, we used Intel(R) Xeon(R) Platinum 8180 CPU with 1 TB RAM. We conducted anexperiment using Safety-Gym environment with a goal and multiple hazards. The objective of theagent is to reach the goal without visiting hazards using a LiDAR sensor with 16 bins around a fullcircle for sensing.
For fair comparison, we used as many same parameters as possible for every method. The followings
are the examples of the common parameters.
• Number of (different) environments for Monte-Carlo simulation: 200• Discount factor: γ = 0.99
• Number of samples for initialization: 40
Reward and safety samples for initialization were created by letting agents observe “test environment”
with only one goal and one hazard. This (small number of) samples are particularly significant for18

our proposed method to initialize the GLM and enable the agent to guarantee safety. Note that, forfair comparison, we also provided prior information for other methods.
Implementation of CPO, PPO-Lagrangian, and TRPO-Lagrangian. Our baseline implementations are heavily dependent on the safety-starter-agent repository (https://github.com/openai/
safety-starter-agents.git) as mentioned in the main paper. We used the following parameters.
• Number of epochs: 600• Max. length of episode: 1000
• Optimizer: Adam
• hidden size: (64, 64)
Implementation of SPO-LF. Safety-Gym is a benchmark originally developed for deep RL
algorithms. Unlike the three baselines, our algorithm is basically based on dynamic programming
methods such as policy iteration to solve Bellman equations. Hence, when we test our proposed
method, we discretized the state space into 50 × 50 = 2, 500 grids and the action space into five (i.e.,
go north, go east, go south, go west, and stay). We converted discrete actions to a series of continuous
actions to navigate the agent in Safety-Gym environment.
We constructed the feature vector using LiDAR observations for the goal and hazards. Specifically,
the feature vector concatenate such observations and bias constant of 1, which is represented as
φ = [ ogoal , ohazard , 1 ],where ogoal and ohazard are respectively the LiDAR observations for the closest goal and hazards. We
used the following parameters in our experiment.
• Algorithm to solve Bellman equation: Approximate Modified Policy Iteration [27]• Link function: sigmoid function• Safety threshold: h = 0.7

19