# Safe Policy Optimization with Local Generalized Linear Function
Approximations

Akifumi Wachi
IBM Research
<EMAIL_ADDRESS>
&Yunyue Wei
Tsinghua University
<EMAIL_ADDRESS>
Yanan Sui
Tsinghua University
<EMAIL_ADDRESS>
###### Abstract

Safe exploration is a key to applying reinforcement learning (RL) in safety-
critical systems. Existing safe exploration methods guaranteed safety under
the assumption of 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 while learning the relation between a locally
available feature obtained by sensors and environmental reward/safety using
generalized linear function approximations. We provide theoretical guarantees
on its safety and optimality. We experimentally show 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 and safer 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
essentially difficult 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, it is 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, in the context of autonomous driving, the degree of safety varies
steeply depending on the presence or absence of other vehicles and
pedestrians. Also, previous work on GP-based safe exploration suffers from
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.

(a) Existing safe exploration. (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, an agent predicts safety function value
while using feature vector obtained by far-sighted observations.

Based on the fact that robots are equipped with sensors, it is more reasonable
to formulate the problem assuming that robots can obtain “feature vectors” for
inferring the degree of safety of the (observable) states of their neighbors.
This problem formulation is realistic for real-world robots, and it 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 and empirically efficient safe RL algorithm
that is applicable to real, large-scale problems.

### Related Work

RL with (generalized) linear function approximation.  Function approximation,
especially that based 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 theoretical analysis 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 with a theoretical guarantee regarding sample efficiency. Wang et
al., [38] then extended Jin et al., [18] to generalized 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 of attempts 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 less strict 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-less and stateful settings. For state-
less settings, SafeOpt [31] and Safe-LUCB [5] were respectively proposed for
Bayesian optimization problems and linear stochastic bandit problems. For
stateful settings, Turchetta et al., [34] proposed a GP-based SafeMDP
algorithm that extends SafeOpt to stateful 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-
based algorithm 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 a limited sensor range. This is a realistic formulation for
some real-world robots with sensors, and it allows us to get rid of the
regularity and Lipschitz assumptions that previous safe exploration 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 and safety function values on the basis of local
features via GLMs. We analyze the theoretical properties of SPO-LF and prove
that an agent will achieve a near-optimal policy with high probability while
satisfying 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 in terms 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

$\mathcal{M}=\langle\mathcal{S},\mathcal{A},f,H,r,g,\bm{\phi},\bm{\psi}\rangle,$

where $\mathcal{S}$ is a finite set of states $\\{\bm{s}\\}$, $\mathcal{A}$ is
a finite set of actions $\\{\bm{a}\\}$,
$f:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ is the deterministic
state transition, and $H\in\mathbb{N}$ is the finite horizon. Also,
$r:\mathcal{S}\rightarrow[0,1]$ and $g:\mathcal{S}\rightarrow[0,1]$ are
bounded reward and safety functions. We assume that both $r$ and $g$ are not
known a priori.111For 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]. At every
time step $t\in\mathbb{N}$, the agent must be in a safe state. Specifically,
for a state $\bm{s}_{t}$, the safety function value $g(\bm{s}_{t})$ must be
above a threshold $h\in(0,1]$; that is, the safety constraint is represented
as $g(\bm{s}_{t})\geq h$.

In real applications, a robot is equipped with sensors and can infer the
values of reward or safety functions by using such measurements as “hints.” To
formulate this mechanism, $\mathcal{M}$ contains two additional functions.
First, $\bm{\phi}:\mathcal{S}\rightarrow\mathbb{B}^{d}$ is an a priori unknown
function for mapping a state $\bm{s}$ to a $d$-dimensional feature vector,
where $\mathbb{B}^{d}:=\\{\bm{x}\in\mathbb{R}^{d}\mid\|\bm{x}\|\leq 1\\}$. For
convenience, let $\bm{\phi}_{\bm{s}}:=\bm{\phi}(\bm{s})$ denote the feature
vector for a state $\bm{s}$. Second, we define a function
$\bm{\psi}:\mathcal{S}\rightarrow\mathcal{S}$ for returning a set of states
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 whole state 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
$\bm{\phi}$ and $\bm{\psi}$, 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
used in 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 observations of the reward and
safety function values along with the feature vector for the current state.
That is, the agent obtains
$(\,\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},y_{r},y_{g}\,)$, where $y_{r}$ and
$y_{g}$ are noisy observations of reward and safety, which are represented as
$y_{r}=r(\bm{s})+n_{t}^{r}$ and $y_{g}=g(\bm{s})+n_{t}^{g}$, with independent
zero-mean noises $n_{t}^{r}$ and $n_{t}^{g}$. Far-sighted observation is more
related to feature vectors. In this observation scheme, an agent obtains
features for $\bm{\psi}(\bm{s})$. For convenience, let
$\Psi_{t}\subseteq\mathcal{S}$ denote the set of states that have been
observed at least once until time $t$; that is,
$\Psi_{t}:=\bm{\psi}(\bm{s}_{0})\cup\bm{\psi}(\bm{s}_{1})\cup\ldots\cup\bm{\psi}(\bm{s}_{t})$.
Intuitively, the agent needs to predict the reward and safety function values
by improving the internal GLMs on the basis of near-sighted observations and
applying them to the features obtained by far-sighted observations.

Goal.  The quality of a policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$ is
evaluated in terms of the cumulative reward achieved by the agent under the
safety constraint. The problem is formally written as

maximize: $\displaystyle\quad
V_{\mathcal{M}}^{\pi}(\bm{s}_{t})=\mathbb{E}\left[\,\sum_{\tau=0}^{H}\gamma^{\tau}r(\bm{s}_{t+\tau})\,\middle|\,\pi\,\right]\quad\text{subject
to:}$ $\displaystyle\quad g(\bm{s}_{t})\geq h.$

There 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 $\mathcal{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.

######  Assumption 1.

The reward and safety functions are respectively represented using GLMs that
are characterized by unknown coefficient vectors
$\bm{\theta}_{r}^{*},\bm{\theta}_{g}^{*}\in\mathbb{R}^{d}$ and fixed, strictly
increasing link functions $\mu_{r},\mu_{g}:\mathbb{R}\rightarrow[0,1]$ such
that

$r(\bm{s})=\mu_{r}(\bm{\phi}_{\bm{s}}^{\top}\bm{\theta}_{r}^{*})\quad\text{and}\quad
g(\bm{s})=\mu_{g}(\bm{\phi}_{\bm{s}}^{\top}\bm{\theta}_{g}^{*}).$

Note that linear and logistic models are the special cases of GLM with
$\mu(x)=x$ and $\mu(x)=\frac{1}{1+e^{-x}}$, respectively. To predict the
coefficients, we obtain maximum likelihood estimators (MLEs) for reward and
safety functions as in Filippi et al., [15]. Let $\tilde{\theta}_{r}$ and
$\tilde{\theta}_{g}$ be the MLEs for reward and safety, respectively. Here,
$\tilde{\theta}_{r}$ and $\tilde{\theta}_{g}$ are the unique solutions of the
following equations.

$\displaystyle\sum_{\tau=0}^{t}\left(r(\bm{s}_{\tau})-\mu_{r}(\bm{\phi}_{\bm{s}_{\tau}}^{\top}\theta_{r})\right)\bm{\phi}_{\bm{s}_{\tau}}=0\quad\text{and}\quad\sum_{\tau=0}^{t}\left(g(\bm{s}_{\tau})-\mu_{g}(\bm{\phi}_{\bm{s}_{\tau}}^{\top}\theta_{g})\right)\bm{\phi}_{\bm{s}_{\tau}}=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 $\diamond$ denote either $r$ or $g$. The link function $\mu_{\diamond}$ is
twice differentiable, and the first and second order derivatives are
respectively bounded by $L_{\diamond}$ and $M_{\diamond}$. Also, the link
function $\mu_{\diamond}$ satisfies
$\xi_{\diamond}=\inf_{\|\theta_{\diamond}-\theta^{*}_{\diamond}\|\leq
1,\|\bm{\phi}_{\bm{s}}\|\leq
1}\dot{\mu}_{\diamond}(\bm{\phi}_{\bm{s}}^{\top}\theta_{\diamond})>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, $S_{0}\subseteq\mathcal{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 $\diamond$ be either $r$ or $g$. The noise $n^{\diamond}_{t}$ is sub-
Gaussian with fixed (positive) parameters $\sigma_{\diamond}$; that is, for
all $t$, we have
$\mathbb{E}\left[\,e^{\omega_{\diamond}n^{\diamond}_{t}}\mid\mathcal{F}^{\diamond}_{t-1}\,\right]\leq
e^{\omega_{\diamond}^{2}\sigma_{\diamond}^{2}/2}$, where
$\\{\mathcal{F}^{\diamond}_{n}\\}$ is increasing sequences of sigma fields
such that $n^{\diamond}_{t}$ is $\mathcal{F}^{\diamond}_{t}$-measurable with
$\mathbb{E}\left[\,n^{\diamond}_{t}\mid\mathcal{F}^{\diamond}_{t-1}\,\right]=0$.

##  3 Preliminary: Defining True Safe Space

In 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 and safety functions. This is
particularly critical when dealing with safety; thus, we aim to conservatively
estimate the safety function value up to a certain confidence
$\epsilon\in\mathbb{R}_{\geq 0}$. As discussed in Turchetta et al., [34], to
identify the safety of a state, we incorporate the safety constraint,
reachability, and returnability. 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 $\mathcal{M}$.

First, we simply consider a set of states that satisfy the safety constraint
with a margin of $\epsilon$. Given the set of states $X$, the following region
can be identified as safe based on the far-sighted observation.

$\displaystyle
Y_{\epsilon}(X)=X\cup\\{\bm{s}\in\mathcal{S}\mid\exists\bm{s}^{\prime}\in
X,\bm{s}\in\bm{\psi}(\bm{s}^{\prime}):g(\bm{s})-\epsilon\geq h\\}.$

Second, we define reachability. The agent may not be able to reach a state
that is in $Y_{\epsilon}(\cdot)$ due to unsafe states in the middle of the
pathway. Given a set $X$, the states in $\Psi$ that are reachable from $X$ in
one step are given by
$Y_{\text{reach}}(X)=X\cup\\{\bm{s}^{\prime}\in\Psi\mid\exists\bm{s}\in
X,a\in\mathcal{A}:\bm{s}^{\prime}=f(\bm{s},a)\\}$. Hence, an $n$-step
reachable operator is given by
$Y^{n}_{\text{reach}}(X)=Y_{\text{reach}}(Y^{n-1}_{\text{reach}}(X))$, where
$Y^{1}_{\text{reach}}(X)=Y_{\text{reach}}(X)$. Finally, the set containing all
the states that are reachable from $X$ along an arbitrary long path in $\Psi$
is defined as
$\bar{Y}_{\text{reach}}(X)=\lim_{n\rightarrow\infty}Y^{n}_{\text{reach}}(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 another
safe state. Hence, before moving to a state $\bm{s}$, we should consider
whether or not there is at least one viable path from $\bm{s}$. The set of
states from which the agent can return to a set $\bar{X}$ through another set
of states $X$ in one step is given by
$Y_{\text{return}}(X,\bar{X})=\bar{X}\cup\\{\bm{s}\in X\mid\exists
a\in\mathcal{A}:f(\bm{s},a)\in\bar{X}\\}$. Thus, with
$Y^{1}_{\text{return}}(X,\bar{X})=Y_{\text{return}}(X,\bar{X})$, an $n$-step
returnability operator is given by
$Y^{n}_{\text{return}}(X,\bar{X})=Y_{\text{return}}(X,Y^{n-1}_{\text{return}}(X,\bar{X}))$.
The set containing all the states from which the agent can return to $\bar{X}$
along an arbitrary long path in $X$ is defined as
$\bar{Y}_{\text{return}}(X,\bar{X})=\lim_{n\rightarrow\infty}Y^{n}_{\text{return}}(X,\bar{X}).$

To guarantee safety, all the above requirements must be satisfied. As such, we
define $Z(\cdot)$:

$Z_{\epsilon}(X)=Y_{\epsilon}(X)\cap\bar{Y}_{\text{reach}}(X)\cap\bar{Y}_{\text{return}}(Y_{\epsilon}(X),X).$

The safe set after repeating such expansions $n$-times is
$Z^{n}_{\epsilon}(X)=Z_{\epsilon}(Z^{n-1}_{\epsilon}(X))$ with
$Z^{1}_{\epsilon}(X)=Z_{\epsilon}(X)$. Finally, the true safe space,
$\bar{Z}_{\epsilon}(X)$ is obtained by taking the limit in terms of $n$; that
is, $\bar{Z}_{\epsilon}(X)=\lim_{n\rightarrow\infty}Z^{n}_{\epsilon}(X)$.

##  4 SPO-LF Algorithm

Algorithm 1 SPO-LF with ETSE

1: $C_{0}(\bm{s})\leftarrow[h,\infty)$ for all $\bm{s}\in S_{0}$

2: loop

3: $\Psi_{t}\leftarrow\Psi_{t-1}\cup O(\bm{s}_{t})$

4: $Q_{t}(\bm{s})\leftarrow(\ref{eq:Q_s})$, $C_{t}(\bm{s})\leftarrow
Q_{t}(\bm{s})\cap C_{t-1}(\bm{s})$

5: $l_{t}(\bm{s})\leftarrow\min C_{t}(\bm{s})$, $u_{t}(\bm{s})\leftarrow\max
C_{t}(\bm{s})$

6: $S^{-}_{t}\leftarrow\\{\bm{s}\in\mathcal{S}\mid l_{t}(\bm{s})\geq h\\}$

7: $S^{+}_{t}\leftarrow\\{\bm{s}\in\mathcal{S}\mid u_{t}(\bm{s})\geq h\\}$

8: $\mathcal{X}^{-}_{t}\leftarrow$ (2), $\mathcal{X}^{+}_{t}\leftarrow$ (3)

9: $J^{*}(\bm{s}_{t})\leftarrow$ (4)

10: if $\operatorname*{arg\,max}_{\bm{s}\in
Y_{\text{reach}}(\\{\bm{s}_{t}\\})}J^{*}(\bm{s})\subseteq\mathcal{X}_{t}^{-}$
then

11:
$\bm{s}_{t+1}\leftarrow\operatorname*{arg\,max}_{\bm{s}\in(\mathcal{X}_{t}^{-}\cap
Y_{\text{reach}}(\\{\bm{s}_{t}\\}))}J^{*}(\bm{s})$

12: else

13: $\bar{J}^{*}(\bm{s}_{t})\leftarrow$ (5)

14: while
$\bm{s}_{t}\neq\operatorname*{arg\,max}_{\bm{s}\in\mathcal{X}_{t}^{-}}\bar{J}^{*}(\bm{s})$
do

15: $\bm{s}_{t+1}\leftarrow\operatorname*{arg\,max}_{\bm{s}\in
Y_{\text{reach}}(\\{\bm{s}_{t}\\})}\bar{J}^{*}(\bm{s})$

16: end while

17: end if

18: end loop

Our SPO-LF algorithm is outlined in Algorithm 1. On the basis of near-sighted
and far-sighted observations, an agent first calculates the upper and lower
bounds of reward and safety function values and predicts a safe region (lines
$3-8$). The agent then optimizes its policy such that the cumulative reward is
maximized while guaranteeing safety. For this purpose, 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
in terms of reward (lines $9-11$). However, we observed a problem in that this
pure approach often causes the agent to get stuck in a reward-poor 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 exploration of safety as necessary (lines $12-17$). Note that the proofs
of the lemmas are in Appendix C.

###  4.1 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 and safety.
Since the accuracy of the predictions depends on the availability of the
feature vector, we obtain the confidence bounds according to whether a state
is inside or outside $\Psi_{t}$. Hereinafter, let the design matrix be
$W_{t}=\sum_{\tau=1}^{t}\bm{\phi}_{\bm{s}_{\tau}}\bm{\phi}_{\bm{s}_{\tau}}^{\top}$.
Also, the weighted $L_{2}$-norm of $\bm{\phi}$ associated with $W_{t}^{-1}$ is
given by
$\|\bm{\phi}\|_{W_{t}^{-1}}=(\bm{\phi}^{\top}W_{t}^{-1}\bm{\phi})^{1/2}$.
Finally, the maximum and minimum singular values of a matrix are denoted as
$\lambda_{\max}(\cdot)$ and $\lambda_{\min}(\cdot)$.

Confidence intervals inside $\Psi_{t}$.  For all $\bm{s}$ in $\Psi_{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 basis of
Theorem 1 in Li et al., [20], we have the following lemma.

######  Lemma 1.

(Thm. 1 in [20]). Let $\delta_{\diamond}>0$ be given and
$\beta_{\diamond}=\frac{3L_{\diamond}\sigma_{\diamond}}{\xi_{\diamond}}\sqrt{\log(3/\delta_{\diamond})}$.
Assume $\lambda_{\min}(W_{t})\geq
512\sigma_{\diamond}^{2}M_{\diamond}^{2}\xi_{\diamond}^{-4}\left(d^{2}+\log\delta_{\diamond}^{-1}\right)$.
Then, with a probability of at least $1-\delta_{\diamond}$, the MLE satisfies

$\displaystyle|\,\diamond(\bm{s})-\mu_{\diamond}(\bm{\phi}_{\bm{s}}^{\top}\tilde{\theta}_{\diamond})\,|\leq\beta_{\diamond}\cdot\|\bm{\phi}_{\bm{s}}\|_{W_{t}^{-1}}.$

The symbol $\diamond$ denotes either $r$ or $g$; that is, Lemma 1 respectively
holds for reward and safety.

Confidence intervals outside $\Psi_{t}$.  For $\bm{s}$ outside $\Psi_{t}$, the
agent does not know even the feature vector. To obtain the confidence
intervals outside $\Psi_{t}$, we should incorporate any possible feature
vector; hence, confidence bounds are rather loose as presented below.

######  Lemma 2.

Let $\diamond$ denote either $r$ or $g$. Assume $\lambda_{\min}(W_{t})\geq
512\cdot\sigma_{\diamond}^{2}M_{\diamond}^{2}\xi_{\diamond}^{-4}\left(d^{2}+\log\delta_{\diamond}^{-1}\right)$.
Then, with a probability of at least $1-\delta_{\diamond}$, for any
$\bm{s}\in\mathcal{S}\setminus\Psi$, we have

$\displaystyle
0\leq\diamond(\bm{s})\leq\mu_{\diamond}(\|\tilde{\theta}_{\diamond}\|)+\beta_{\diamond}\cdot\lambda_{\max}(W_{t}^{-1}).$

The next lemma is on the relation between the upper bound defined above and
the threshold, $h$.

######  Lemma 3.

Assume $\lambda_{\min}(W_{t})\geq
512\cdot\sigma_{g}^{2}M_{g}^{2}\xi_{g}^{-4}\left(d^{2}+\log\delta_{g}^{-1}\right)$.
Then, with a probability of at least $1-\delta_{g}$, we have
$\mu_{g}(\|\tilde{\theta}_{g}\|)+\beta_{g}\cdot\lambda_{\max}(W_{t}^{-1})\geq
h$.

#### Efficiency metric of exploration.

Because $\beta_{r}$ and $\beta_{g}$ are constants independent from $\bm{s}$,
the efficiency of the exploration of the reward and safety functions depends
solely on $\|\bm{\phi}\|_{W_{t}^{-1}}$ within $\Psi_{t}$ and
$\lambda_{\max}(W_{t}^{-1})$ outside $\Psi_{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 $\bm{\lambda_{\min}(W_{t})}$.

As discussed in Li et al., [20], the assumption on $\lambda_{\min}(W_{t})$ 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 $\lambda_{\min}(W_{t})$ is valid. This paper presents two methods; the
first is to provide (typically a small number of) data for initializing GLMs,
and the second is to prepare a sufficiently large $S_{0}$ and prohibit the
agent from going outside of $S_{0}$, until the condition on
$\lambda_{\min}(W_{t})$ 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 of safety. By Lemma 1 and 2,
the confidence bounds on safety are represented as

$\displaystyle Q_{t}(\bm{s})=\begin{cases}\
[\,\mu_{g}(\bm{\phi}_{\bm{s}}^{\top}\tilde{\theta}_{g})\pm\beta_{g}\cdot\|\bm{\phi}_{\bm{s}}\|_{W_{t}^{-1}}\,]\quad\quad\quad\
\text{if}\quad\bm{s}\in\Psi_{t},\\\ \
[\,0,\mu_{g}(\|\tilde{\theta}_{g}\|)+\beta_{g}\cdot\lambda_{\max}(W_{t}^{-1})\,]\quad\
\ \text{otherwise}.\end{cases}$ (1)

We consider the intersection of $Q_{t}$ up to iteration $t$, which is defined
as $C_{t}(\bm{s})=Q_{t}(\bm{s})\cap C_{t-1}(\bm{s})$, where
$C_{0}(\bm{s})=[h,\infty]$ for all $\bm{s}\in S_{0}$. The lower and upper
bounds on $C_{t}(\bm{s})$ are denoted by $l_{t}(\bm{s}):=\min C_{t}(\bm{s})$
and $u_{t}(\bm{s}):=\max C_{t}(\bm{s})$, respectively.

Predicted pessimistic safe space.  We now define the predicted pessimistic
safe space. We first consider a set of states such that the safety constraint
is satisfied with high probability. It is formulated using $l_{t}$; that is,

$S^{-}_{t}:=\\{\,\bm{s}\in\mathcal{S}\mid l_{t}(\bm{s})\geq h\,\\}.$

The desired pessimistic safe space, $\mathcal{X}^{-}_{t}$ is a subset of
$S^{-}_{t}$ and also satisfies the reachability and returnability constraints;
that is,

$\mathcal{X}^{-}_{t}=S^{-}_{t}\cap\bar{Y}_{\text{reach}}(\mathcal{X}^{-}_{t-1})\cap\bar{Y}_{\text{return}}(S_{t}^{-},\mathcal{X}^{-}_{t-1}).$
(2)

Predicted optimistic safe space.  To optimize a policy, we need to incorporate
the reward not only in $\mathcal{X}_{t}^{-}$ 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

$S^{+}_{t}:=\\{\,\bm{s}\in\mathcal{S}\mid u_{t}(\bm{s})\geq h\,\\}.$

Note that, by Lemmas 2 and 3, for all states in
$\mathcal{S}\setminus\Psi_{t}$, the upper and lower confidence bounds in terms
of safety satisfy $l_{t}(\bm{s})<h\leq u_{t}(\bm{s})$. Hence, all states in
$\mathcal{S}\setminus\Psi_{t}$ are identified as pessimistically unsafe but
optimistically safe. Similarly to the pessimistic safe region, we again
incorporate reachability and returnability. The resulting optimistic safe
region is given by

$\mathcal{X}^{+}_{t}=S^{+}_{t}\cap\bar{Y}_{\text{reach}}(\mathcal{X}^{+}_{t-1})\cap\bar{Y}_{\text{return}}(S_{t}^{+},\mathcal{X}^{+}_{t-1}).$
(3)

###  4.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 $\|\bm{\phi}\|_{W_{t}^{-1}}$ and
$\lambda_{\max}(W_{t}^{-1})$. Hence, it turns out that we only need to balance
exploration and 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:

$\displaystyle\\!J^{*}(\bm{s}_{t})\\!=\\!\max_{\bm{s}\in\mathcal{X}_{t}^{+}}\bigl{[}R(\bm{s})+\gamma
J^{*}(\bm{s})\bigr{]}\ \ \text{where}\ \
R(\bm{s})\\!:=\\!\begin{cases}\mu_{r}(\bm{\phi}_{\bm{s}}^{\top}\tilde{\theta}_{r})+\beta_{r}\|\bm{\phi}_{\bm{s}}\|_{W_{t}^{-1}}\quad\
\text{if}\ \ \bm{s}\in\Psi_{t},&\\\
\mu_{r}(\|\tilde{\theta}_{r}\|)+\beta_{r}\lambda_{\max}(W_{t}^{-1})\ \
\text{otherwise}.\end{cases}$ (4)

Note that $R(\bm{s})$ represents the upper confidence bound with regard to
reward. The next state to visit should be pessimistically safe and reachable
from $\bm{s}_{t}$ with one step; that is,

$\bm{s}^{*}_{t+1}=\operatorname*{arg\,max}_{\bm{s}\in(\mathcal{X}_{t}^{-}\cap
Y_{\text{reach}}(\\{\bm{s}_{t}\\}))}J^{*}(\bm{s}).$

Problem with this approach.  We observed that the above algorithm often causes
the agent to get stuck in a state with a (relatively) small reward. The reason
for this problem is as follows. When the state with the maximum $J^{*}$ is
outside $\mathcal{X}_{t}^{-}$, 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 $\bm{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

$\eta:=\operatorname*{arg\,max}_{\bm{s}\in
Y_{\text{reach}}(\\{\bm{s}_{t}\\})}J^{*}(\bm{s}),$

meaning the state that the agent will visit if there is no safety constraint.
The ETSE algorithm is triggered only when $\bm{s}_{t+1}^{*}\neq\eta$.
Intuitively, if $\eta$ is within $\mathcal{X}_{t}^{-}$, the agent can simply
execute the next optimal action to visit $\bm{s}^{*}_{t+1}$; hence, the above
problem arises only if $\bm{s}_{t+1}^{*}\neq\eta$ is satisfied. This algorithm
focuses on expanding the pessimistic safe region by visiting the states with a
large uncertainty.

$\bar{J}^{*}(\bm{s}_{t})=\max_{s_{t+1}\in\mathcal{X}_{t}^{-}}\bigl{[}\,\|\bm{\phi}_{\bm{s}_{t+1}}\|_{W_{t}^{-1}}+\gamma\bar{J}^{*}(\bm{s}_{t+1})\,\bigr{]}.$
(5)

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).

##  5 Theoretical 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 $C_{1}$ and $C_{2}$ be positive, universal constants. Also, let $t^{*}$
denote the smallest integer satisfying

$\lambda_{\min}(\Sigma)t-C_{1}\sqrt{td}-C_{2}\sqrt{t\log(\delta_{g}^{-1})}\geq\max\left\\{\frac{\beta_{g}}{\epsilon},1\right\\}$

with $\Sigma=\mathbb{E}[\,\bm{\phi}_{t}\bm{\phi}_{t}^{\top}\,]$. Then, for all
$t>t^{*}$, the following inequalities hold.

$|\,\mu_{g}(\bm{\phi}^{\top}\theta_{g}^{*})-\mu_{g}(\bm{\phi}^{\top}\tilde{\theta}_{g})\,|\leq\epsilon\quad\text{and}\quad\sum_{\tau=t+1}^{t+H}\|\bm{\phi}_{\bm{s}_{\tau}}\|_{W_{\tau}^{-1}}\leq\sqrt{2Hd\log\left(\frac{t+H}{d}\right)}.$

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 $\sigma_{g}$-sub-Gaussian and
$\lambda_{\min}(W_{t})\geq
512\cdot\sigma_{g}^{2}M_{g}^{2}\xi_{g}^{-4}\left(d^{2}+\log\delta_{g}^{-1}\right)$
holds. Suppose that the next state is chosen from $\mathcal{X}^{-}_{t}$. Then,
the following statement holds with a probability of at least $1-\delta_{g}$:

$\forall t\geq 0,\quad g(\bm{s}_{t})\geq h.$

The proof is in Appendix E. The agent chooses the next state to visit within
$\mathcal{X}^{-}_{t}$ ($\subseteq S_{t}^{-}$), and $S_{t}^{-}$ is
characterized with $l(\bm{s})$. Since $g(\bm{s})$ is greater than $l(\bm{s})$
with a probability of at least $1-\delta_{g}$, our algorithm guarantees that
the agent will execute only safe actions.222Unlike 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.

######  Theorem 2.

Set $T^{*}=t^{*}+|\bar{Z}_{0}(S_{0})|$ and

$\epsilon_{V}=V_{\max}\cdot\delta_{g}+\beta_{r}(\delta_{r})\sqrt{2Hd\log\left(\frac{t+H}{d}\right)},$

where $V_{\max}$ 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^{\pi_{t}}(\bm{s}_{t})\geq V^{*}(\bm{s}_{t})-\varepsilon_{V},$

— i.e., the algorithm is $\varepsilon_{V}$-close to the optimal policy — for
all but $T^{*}$ time steps while guaranteeing safety with a probability of at
least $1-\delta_{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,
$\bm{s}_{t+1}^{*}\neq\eta$ is satisfied, 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
the whole safe space. However, after a sufficiently large number of time steps
greater than $T^{*}$, the agent can achieve an $\varepsilon_{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 the near-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 Gym-MiniGrid [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.333https://github.com/akifumi-wachi-4/spolf

###  6.1 Grid World

#### Settings.

We constructed a simulation environment based on Gym-MiniGrid [12]. We
considered a $25\times 25$ grid in which each grid was associated with a
randomly generated feature vector with the dimension $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\times 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 $(\bm{\phi},g)$, to initialize the internal GLM model
regarding safety. We considered a linear model with $\mu(x)=x$ for both reward
and safety. Finally, we set $\gamma=0.999$, $\delta_{r}=\delta_{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
Oracle, and it has a non-exploratory agent who knows the true reward and
safety functions a priori. The second is called Unsafe GLM, in which a safety-
agnostic agent maximizes a cumulative reward on the basis of GLMs. The third
is called Random, 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 is Step 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 safety functions have
regularity with regard to state. We used the reward and the number of unsafe
actions as evaluation metrics.

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. Figure 3: Computational time of GLM-
based SPO-LF and GP-based algorithm (i.e., Wachi and Sui, [36]).

Results.  Figure 2(a) compares the performance with regard to the cumulative
reward of each algorithm. SPO-LF, Unsafe GLM, Step safe GLM, and GP (feature)
achieved a near-optimal policy. The convergence of SPO-LF was faster than Step
safe GLM and GP (feature) but slower than Unsafe 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 non-optimal reward. Figure 2(b) compares the performance of SPO-
LF with different sizes of field of view (FOV) from $1\times 1$ to $13\times
13$. For a larger FOV, the convergence of the algorithm got faster. Given that
SPO-LF (FOV $1\times 1$) 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
for different environment sizes. SPO-LF is more scalable and applicable to
large-scale problems given that the GP-based algorithms did not run in a
reasonable amount of time for large environments such as that with $150\times
150$ states. In the GLM-based methods, most of the computational cost when
obtaining confidence bounds is for calculating $\lambda_{\max}(W_{t}^{-1})$.
This computational complexity is $\mathcal{O}(d^{3})$, which does neither
depend on the number of states nor samples. Finally, the average number of
unsafe actions was $\bm{3.4}$ for Unsafe GLM, $\bm{49.0}$ for Random, and
$\bm{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] and TRPO
[28]) to incorporate constraints (for more details, see Section 5 in Ray et
al., [25]). In this experiment, 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 goal and 2) a reward of $0.01\cdot\Delta_{\text{goal}}$ when
getting closer to the goal, where $\Delta_{\text{goal}}$ is the amount of
decrease in distance from the goal. To implement SPO-LF, we discretized the
environment into $50\times 50$ grids and used a computationally inexpensive
policy iteration algorithm proposed in Scherrer et al., [27] for policy
optimization. The feature vector $\phi$ was constructed by LiDAR observations
(i.e., the distance 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 $\mu(x)=\frac{1}{1+e^{-x}}$ as the link
function. As for implementing the three baselines, our experiments largely
depended on the “safety-starter-agent” repository
(https://github.com/openai/safety-starter-agents.git). For 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 of unsafe actions as evaluation metrics and calculated
the mean and standard error after running each method $200$ times. As shown in
Figure 4(b), our SPO-LF exhibited comparable performance to the baselines 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.

(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.

##  7 Conclusion

We formulated a new problem characterized by safety-constrained MDPs with
local feature and then proposed 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 our algorithm 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 with theoretical guarantees (e.g., [34], [36]) and advanced deep RL
methods (e.g., [2]), which potentially sets out a research direction to bridge
the gap between two distinct methods. However, there are several 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 and have not found any negative societal impact of our
algorithm. However, we need to remain aware that 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

  * Abbasi-yadkori et al., [2011] Abbasi-yadkori, Y., Pál, D., and Szepesvári, C. (2011).  Improved algorithms for linear stochastic bandits.  In Neural Information Processing Systems (NeurIPS).
  * Achiam et al., [2017] Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017).  Constrained policy optimization.  In International Conference on Machine Learning (ICML).
  * Alshiekh et al., [2018] 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).
  * Altman, [1999] Altman, E. (1999).  Constrained Markov decision processes, volume 7.  CRC Press.
  * Amani et al., [2019] Amani, S., Alizadeh, M., and Thrampoulidis, C. (2019).  Linear stochastic bandits under safety constraints.  In Neural Information Processing Systems (NeurIPS).
  * Berkenkamp et al., [2017] Berkenkamp, F., Turchetta, M., Schoellig, A., and Krause, A. (2017).  Safe model-based reinforcement learning with stability guarantees.  In Neural Information Processing Systems (NeurIPS).
  * Bhatnagar and Lakshmanan, [2012] Bhatnagar, S. and Lakshmanan, K. (2012).  An online actor–critic algorithm with function approximation for constrained markov decision processes.  Journal of Optimization Theory and Applications, 153(3):688–708.
  * Biyik et al., [2019] 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.
  * Borkar, [2005] Borkar, V. S. (2005).  An actor-critic algorithm for constrained markov decision processes.  Systems & control letters, 54(3):207–213.
  * Bradtke and Barto, [1996] Bradtke, S. J. and Barto, A. G. (1996).  Linear least-squares algorithms for temporal difference learning.  Machine learning, 22(1):33–57.
  * Cheng et al., [2019] 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 Conference on Artificial Intelligence (AAAI).
  * Chevalier-Boisvert et al., [2018] Chevalier-Boisvert, M., Willems, L., and Pal, S. (2018).  Minimalistic gridworld environment for OpenAI gym.  https://github.com/maximecb/gym-minigrid.
  * Chow et al., [2017] 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.
  * Ding et al., [2021] 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 Intelligence and Statistics (AISTAT).
  * Filippi et al., [2010] Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010).  Parametric bandits: The generalized linear case.  In Neural Information Processing Systems (NeurIPS).
  * Fulton and Platzer, [2018] 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).
  * Garcıa and Fernández, [2015] 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.
  * Jin et al., [2020] Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020).  Provably efficient reinforcement learning with linear function approximation.  In Conference on Learning Theory (COLT).
  * Li et al., [2010] Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010).  A contextual-bandit approach to personalized news article recommendation.  In International Conference on World Wide Web (WWW).
  * Li et al., [2017] Li, L., Lu, Y., and Zhou, D. (2017).  Provably optimal algorithms for generalized linear contextual bandits.  In International Conference on Machine Learning (ICML).
  * Liu et al., [2020] Liu, Y., Ding, J., and Liu, X. (2020).  Ipo: Interior-point policy optimization under constraints.  In AAAI Conference on Artificial Intelligence (AAAI).
  * Osband et al., [2016] Osband, I., Van Roy, B., and Wen, Z. (2016).  Generalization and exploration via randomized value functions.  In International Conference on Machine Learning (ICML).
  * Paternain et al., [2019] Paternain, S., Calvo-Fullana, M., Chamon, L. F., and Ribeiro, A. (2019).  Safe policies for reinforcement learning via primal-dual methods.  arXiv preprint arXiv:1911.09101.
  * Rasmussen, [2004] Rasmussen, C. E. (2004).  Gaussian processes in machine learning.  In Advanced Lectures on Machine Learning, pages 63–71. Springer.
  * Ray et al., [2019] Ray, A., Achiam, J., and Amodei, D. (2019).  Benchmarking safe exploration in deep reinforcement learning.  OpenAI.
  * Satija et al., [2020] Satija, H., Amortila, P., and Pineau, J. (2020).  Constrained markov decision processes via backward value functions.  In International Conference on Machine Learning (ICML).
  * Scherrer et al., [2012] Scherrer, B., Ghavamzadeh, M., Gabillon, V., and Geist, M. (2012).  Approximate modified policy iteration.  In International Conference on Machine Learning (ICML).
  * Schulman et al., [2015] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015).  Trust region policy optimization.  In International Conference on Machine Learning (ICML).
  * Schulman et al., [2017] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017).  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347.
  * Strehl and Littman, [2005] Strehl, A. L. and Littman, M. L. (2005).  A theoretical analysis of model-based interval estimation.  In International Conference on Machine Learning (ICML).
  * Sui et al., [2015] 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).
  * Sutton, [1988] Sutton, R. S. (1988).  Learning to predict by the methods of temporal differences.  Machine learning, 3(1):9–44.
  * Tessler et al., [2018] Tessler, C., Mankowitz, D. J., and Mannor, S. (2018).  Reward constrained policy optimization.  arXiv preprint arXiv:1805.11074.
  * Turchetta et al., [2016] Turchetta, M., Berkenkamp, F., and Krause, A. (2016).  Safe exploration in finite Markov decision processes with Gaussian processes.  In Neural Information Processing Systems (NeurIPS).
  * Turchetta et al., [2019] Turchetta, M., Berkenkamp, F., and Krause, A. (2019).  Safe exploration for interactive machine learning.  In Neural Information Processing Systems (NeurIPS).
  * Wachi and Sui, [2020] Wachi, A. and Sui, Y. (2020).  Safe reinforcement learning in constrained Markov decision processes.  In International Conference on Machine Learning (ICML).
  * Wachi et al., [2018] 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).
  * Wang et al., [2019] 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).
  * Yang and Wang, [2020] Yang, L. and Wang, M. (2020).  Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.  In International Conference on Machine Learning (ICML).

Appendices

## A. 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. |  $\bm{s}\in\Psi_{t}$ (feature available) |  $\bm{s}\notin\Psi_{t}$ (feature unavailable)
---|---|---
Reward | $[\,\mu(\bm{\phi}_{\bm{s}}^{\top}\tilde{\theta}_{r})\pm\beta_{r}\cdot\|\bm{\phi}_{\bm{s}}\|_{W_{t}^{-1}}\,]$ | $[\,0,\mu(\|\tilde{\theta}_{r}\|)\pm\beta_{r}\cdot\lambda_{\max}(W_{t}^{-1})\,]$
Safety | $[\,\mu(\bm{\phi}_{\bm{s}}^{\top}\tilde{\theta}_{g})\pm\beta_{g}\cdot\|\bm{\phi}_{\bm{s}}\|_{W_{t}^{-1}}\,]$ | $[\,0,\mu(\|\tilde{\theta}_{g}\|)+\beta_{g}\cdot\lambda_{\max}(W_{t}^{-1})\,]$

## B. Preliminary Lemma

######  Lemma 5.

For two arbitrary functions $f_{1}(x)$ and $f_{2}(x)$, the following
inequality holds:

$\displaystyle\max_{x}f_{1}(x)-\max_{x}f_{2}(x)\geq\min_{x}(f_{1}(x)-f_{2}(x)).$

###### Proof.

For two arbitrary functions $f_{1}(x)$ and $f_{2}(x)$, the following
inequalities hold:

$\displaystyle\max_{x}\\{f_{2}(x)-f_{1}(x)\\}+\max_{x}f_{1}(x)$
$\displaystyle\geq\max_{x}f_{2}$
$\displaystyle\max_{x}f_{1}(x)-\max_{x}f_{2}(x)$
$\displaystyle\geq-\max_{x}\\{f_{1}(x)-f_{2}(x)\\}$
$\displaystyle=\min_{x}\\{f_{1}(x)-f_{2}(x)\\}.$

Then, the desired lemma is obtained. ∎

## C. Lemmas on GLMs

### C.0. Preliminary lemma on GLMs

######  Lemma 6.

Let $\theta_{g}^{*}$ be the true coefficient for safety. Then, we have
$\mu_{g}(\|\theta_{g}^{*}\|)\geq h$.

###### Proof.

By Cauchy–Schwarz inequality, for all $\bm{\phi}_{\bm{s}}$ such that
$\|\bm{\phi}_{\bm{s}}\|\leq 1$, the following inequality holds:

$\|\theta_{g}^{*}\|\geq\bm{\phi}_{\bm{s}}^{\top}\theta_{g}^{*}.$

By Assumption 1, $\mu_{g}(\cdot)$ is a strictly increasing function; that is,

$\mu_{g}(\|\theta_{g}^{*}\|)\geq\mu_{g}(\bm{\phi}_{\bm{s}}^{\top}\theta_{g}^{*}).$

Assumption 3 implies that there exists $\bm{\phi}_{\bm{s}}$ such that

$\mu_{g}(\bm{\phi}_{\bm{s}}^{\top}\theta_{g}^{*})\geq h.$

Therefore, we obtained the desired lemma. ∎

### C.1. Proofs of Lemma 1

###### Proof.

See Theorem 1 in Li et al., [20]. ∎

### C.2. Proof of Lemma 2

###### Proof.

First, we obtain the upper bound of $\diamond(\bm{s})$ for any
$\bm{s}\in\mathcal{S}$. Let $\bm{\phi}^{*}_{\diamond,\bm{s}}$ be the feature
for achieving the maximum value of $\diamond$. Then, the following chain of
equations hold, with a probability of at least $1-\delta_{\diamond}$:

$\displaystyle\max_{\bm{s}\in\mathcal{S}}\diamond(\bm{s})$
$\displaystyle=\mu_{\diamond}(\langle\bm{\phi}^{*}_{\diamond,\bm{s}},\theta_{\diamond}^{*}\rangle)$
$\displaystyle\leq\mu_{\diamond}(\langle\bm{\phi}^{*}_{\diamond,\bm{s}},\tilde{\theta}_{\diamond}\rangle)+\beta_{\diamond}\cdot\|\bm{\phi}^{*}_{\diamond,\bm{s}}\|_{W_{n}^{-1}}$
$\displaystyle\leq\mu_{\diamond}(\|\tilde{\theta}_{\diamond}\|)+\beta_{\diamond}\cdot\|\bm{\phi}^{*}_{\diamond,\bm{s}}\|_{W_{n}^{-1}}$
$\displaystyle\leq\mu_{\diamond}(\|\tilde{\theta}_{\diamond}\|)+\beta_{\diamond}\cdot\lambda_{\max}(W_{n}^{-1}).$

In the above chain of inequalities, we used Cauchy–Schwarz inequality and
$\|\bm{\phi}^{*}_{\diamond,\bm{s}}\|\leq 1$ in the second line and then used
$\|\bm{\phi}^{*}_{\diamond,\bm{s}}\|_{W_{n}^{-1}}\leq\lambda_{\max}(W_{n}^{-1})$
in the third line.

The lower bound can be simply obtained by definition; that is,

$\displaystyle\min_{\bm{s}\in\mathcal{S}}\diamond(\bm{s})\geq 0.$

Then, we have the desired lemma. ∎

### C.3. Proof of Lemma 3

###### Proof.

By Lemma 2, with a probability of at least $1-\delta_{g}$, we have the
following inequality in terms of the confidence bounds of the safety function:

$\displaystyle
0\leq\max_{\bm{s}\in\mathcal{S}}g(\bm{s})\leq\mu_{g}(\|\tilde{\theta}_{g}\|)+\beta_{g}\cdot\lambda_{\max}(W_{n}^{-1}).$

Also, by combining Lemma 6 and

$\mu_{g}(\|\theta^{*}_{g}\|)\leq\mu_{g}(\|\tilde{\theta}_{g}\|)+\beta_{g}\cdot\lambda_{\max}(W_{n}^{-1}),$

we have

$h\leq\mu_{g}(\|\theta^{*}_{g}\|)\leq\mu_{g}(\|\tilde{\theta}_{g}\|)+\beta_{g}\cdot\lambda_{\max}(W_{n}^{-1}).$

Finally, we obtained the desired lemma. ∎

### C.4. Proof of Lemma 4

###### Proof.

For all $t>t^{*}$, the following chain of inequalities hold:

$\displaystyle\min\left\\{\frac{\epsilon}{\beta_{g}},1\right\\}$
$\displaystyle\
\geq\left(\lambda_{\min}(\Sigma)t-C_{1}\sqrt{td}-C_{2}\sqrt{t\log(\delta_{g}^{-1})}\right)^{-1}$
$\displaystyle\ \geq\lambda_{\max}(W_{n}^{-1}).$

In the above calculation, we used Lemma 1 in Li et al., [20] and
$\lambda_{\max}(W_{n}^{-1})=\frac{1}{\lambda_{\min}(W_{n})}$. Therefore, the
following two statements are satisfied. First, because we have
$\beta_{g}\lambda_{\max}(W_{n}^{-1})\leq\epsilon$, the following inequalities
hold:

$\displaystyle|\,\mu_{g}(\bm{\phi}^{\top}\theta_{g}^{*})-\mu_{g}(\bm{\phi}^{\top}\tilde{\theta}_{g})\,|$
$\displaystyle\ \leq\beta_{g}\lambda_{\max}(W_{n}^{-1})$ $\displaystyle\
\leq\epsilon.$

Second, by Lemma 2 in Li et al., [20], the following inequality holds under
the condition that $\lambda_{\max}(W_{n}^{-1})\leq 1$:

$\displaystyle\sum_{\tau=t+1}^{t+H}\|\bm{\phi}_{\bm{s}_{\tau}}\|_{W_{\tau}^{-1}}\leq\sqrt{2Hd\log\left(\frac{t+H}{d}\right)}.$

∎

## D. Lemmas on Near-optimality

######  Lemma 7.

Let $J^{*}(\bm{s}_{t})$ be the value function calculated by our algorithm.
Then, $J^{*}(\bm{s}_{t})$ satisfies the following inequality:

$J^{*}(\bm{s}_{t})\geq V^{*}(\bm{s}_{t}).$

###### Proof.

Let $I_{Z}:\mathcal{S}\rightarrow\\{0,1\\}$ denote the following safety
indicator function:

$\displaystyle I_{Z}(\bm{s}):=\left\\{\begin{array}[]{ll}1&\quad\text{if}\ \
\bm{s}\in\bar{Z}_{\epsilon_{g}}(S_{0}),\\\
0&\quad\text{otherwise}.\end{array}\right.$ (8)

Then, the following chain of equations and inequalities holds:

$\displaystyle\ J^{*}(\bm{s}_{t})-V^{*}(\bm{s}_{t})$ $\displaystyle=$
$\displaystyle\ \max_{s_{t+1}\in\mathcal{X}_{t}^{+}}\left[\
R(\bm{s}_{t+1})+\gamma J^{*}(\bm{s}_{t+1})\
\right]-\max_{s_{t+1}\in\bar{Z}_{\epsilon_{g}}(S_{0})}\left[\
r(\bm{s}_{t+1})+\gamma V_{\mathcal{M}}^{*}(\bm{s}_{t+1})\ \right]$
$\displaystyle\geq$ $\displaystyle\
\max_{s_{t+1}\in\bar{Z}_{\epsilon_{g}}(S_{0})}\left[\ R(\bm{s}_{t+1})+\gamma
J^{*}(\bm{s}_{t+1})\
\right]-\max_{s_{t+1}\in\bar{Z}_{\epsilon_{g}}(S_{0})}\left[\
r(\bm{s}_{t+1})+\gamma V_{\mathcal{M}}^{*}(\bm{s}_{t+1})\ \right]$
$\displaystyle=$ $\displaystyle\ \max_{s_{t+1}}\left[\
I_{Z}(\bm{s}_{t+1})\\{R(\bm{s}_{t+1})+\gamma J^{*}(\bm{s}_{t+1})\\}\
\right]-\max_{s_{t+1}}\left[\ I_{Z}(\bm{s}_{t+1})\\{r(\bm{s}_{t+1})+\gamma
V_{\mathcal{M}}^{*}(\bm{s}_{t+1})\\}\ \right]$ $\displaystyle\geq$
$\displaystyle\ \min_{s_{t+1}}\left[\
I_{Z}(\bm{s}_{t+1})\\{R(\bm{s}_{t+1})-r(\bm{s}_{t+1})\\}+\gamma
I_{Z}(\bm{s}_{t+1})\\{J^{*}(\bm{s}_{t+1})-V^{*}(\bm{s}_{t+1})\\}\ \right].$

The second line follows from
$\mathcal{X}_{t}^{+}\supseteq\bar{Z}_{\epsilon_{g}}(S_{0})$, and the third
line follows from the definition of $I_{Z}$. Also, the fourth line follows
from Lemma 5. By definition of $R(\bm{s})$, the following equation holds with
a probability of at least $1-\delta^{r}$:

$\displaystyle\min_{\bm{s}_{t}}[\,J^{*}(\bm{s}_{t})-V^{*}(\bm{s}_{t})\,]\geq\gamma\cdot\min_{\bm{s}_{t+1}}\left[\,I_{Z}(\bm{s}_{t+1})\\{J^{*}(\bm{s}_{t+1})-V^{*}(\bm{s}_{t+1})\\}\,\right]$

Repeatedly applying this equation proves the desired lemma. Therefore, we have

$J^{*}(\bm{s}_{t})\geq V^{*}(\bm{s}_{t})$

with high probability. ∎

######  Lemma 8.

(Generalized induced inequality) Let $\bm{\phi},r,g$ and
$\hat{\bm{\phi}},\hat{r},\hat{g}$ be the feature and reward function
(including the exploration bonus) and safety function that are identical on
some set of states $\Omega$ — i.e., $\bm{\phi}=\hat{\bm{\phi}}$, $r=\hat{r}$,
and $g=\hat{g}$ for all $\bm{s}\in\Omega$. Let $P(A_{\Omega})$ be the
probability that a state not in $\Omega$ is generated when starting from state
$\bm{s}$ and following a policy $\pi$. Assume value is bound in
$[0,V_{\max}]$, then

$V^{\pi}(r,\bm{s},\bm{\phi},g)\geq
V^{\pi}(\hat{r},\bm{s},\hat{\bm{\phi}},\hat{g})-V_{\max}P(A_{\Omega}),$

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_{\Omega}$ be the event in which the agent escapes from
$\Omega$. Then, for all $t>T^{*}$, we have

$P(A_{\mathcal{X}_{t}^{-}})\leq\delta_{g}.$

###### Proof.

Hereinafter, let $\bar{q}_{t}$ be the sequence of states planed by the policy
$\pi_{t}$ obtained by the algorithm at time $t$: that is,

$\bar{q}_{t}:=\\{\,\bar{\bm{s}}_{t},\bar{\bm{s}}_{t+1},\ldots,\bar{\bm{s}}_{t+H}\,\\},$

where $\bar{\bm{s}}_{t}=\bm{s}_{t}$ and
$\bar{\bm{s}}_{t+\tau+1}=f(\bar{\bm{s}}_{t+\tau},\pi_{t}(\bar{\bm{s}}_{t+\tau}))$
for all $\tau\in[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-\delta_{g}$ (we
call Event A). While the agent optimizes its policy, one of the following two
events happens.

  * •

Event A-1: $\bar{q}_{t}\subseteq\mathcal{X}_{t}^{-}$.

  * •

Event A-2: $\bar{q}_{t}\nsubseteq\mathcal{X}_{t}^{-}$.

When Event A-1 occurs, the optimal policy calculated based on the current
information can be obtained only in $\mathcal{X}_{t}^{-}$. Hence, the agent
will not go outside $\mathcal{X}_{t}^{-}$ as far as it follows the current
policy. The worse-case for the agent is when Event 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, the confidence interval on
safety is bounded by $\epsilon$ and then the agent can identify whether or not
a state is safe immediately on the basis of far-sighted observations. After
the agent learns the safety function model up to $\epsilon$-accuracy, it takes
at most $T^{*}-t^{*}=|R_{0}(S_{0})|$ time steps until $\mathcal{X}_{t}^{-}$ is
sufficiently expanded.

Second, if the prediction of safety is wrong, we cannot avoid the situation
that the agent escapes from $\mathcal{X}_{t}^{-}$, which occurs with a
probability of at most $\delta_{g}$.

In summary, for all $t>T^{*}$, only if the prediction of safety is inaccurate,
the agent may go outside of $\mathcal{X}_{t}^{-}$. This event (i.e., Event B)
happens with a (small) probability at most $\delta_{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 $\bm{s}\in\mathcal{S}$, with a probability of
at least $1-\delta_{g}$, we have

$g(\bm{s})\geq l(\bm{s}).$

Our SPO-LF requires the agent to visit only the state satisfying
$l(\bm{s})\geq h$; hence, the safety constraint

$g(\bm{s})\geq h$

is satisfied with a probability of at least $1-\delta_{g}$. ∎

### E.2. Proof of Theorem 2

###### Proof.

Define $\tilde{r}$ and $\tilde{g}$ as the reward function (with the
exploration bonus) and safety function, which are used by the SPO-LF. Let
$\hat{r}$ be a reward function equal to $r$ on $\Omega$ and equal to
$\tilde{r}$ elsewhere. Furthermore, let $\tilde{\pi}$ be the policy followed
by the SPO-LF at time $t$, that is, the policy calculated on the basis of the
feature $\bm{\phi}$ and predicted reward $\tilde{r}$ and safety $\tilde{g}$
inferred by the predicted coefficients, (i.e., $\tilde{\theta}_{r}$ and
$\tilde{\theta}_{g}$). Finally, let $A_{\Omega}$ be the event in which
$\tilde{\pi}$ escapes from $\Omega$. Then, by Lemma 8, we have

$V^{\pi_{t}}(r,\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)\geq
V^{\tilde{\pi}}(\hat{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}P(A_{\Omega}).$

In addition, note that, for all $t\geq t^{*}$ and
$\bm{s}_{t}\in\mathcal{X}_{t}^{-}$, because $\hat{r}$ and $\tilde{r}$ differ
by at most $\beta_{g}~{}\|\bm{\phi}_{\bm{s}_{t}}\|_{W^{-1}}$ at each state,

$\displaystyle|\,V^{\tilde{\pi}}(\hat{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},\tilde{g})-V^{\tilde{\pi}}(\tilde{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},\tilde{g})\,|$
$\displaystyle\leq\sum_{\tau=1}^{H}\beta_{r}~{}\|\bm{\phi}_{\bm{s}_{t+\tau}}\|_{W^{-1}}$
$\displaystyle=\beta_{r}\cdot\sum_{\tau=1}^{H}\|\bm{\phi}_{\bm{s}_{t+\tau}}\|_{W^{-1}}$
$\displaystyle\leq\beta_{r}\cdot\sqrt{2Hd\log\left((t+H)/d\right)}.$ (9)

Here, consider the case of $\Omega=\mathcal{X}_{t^{*}}^{-}$. Once the safe
region is fully explored, $P(A_{\mathcal{X}_{t^{*}}^{-}})\leq\delta_{g}$ holds
after $T^{*}$ time steps. Then, the following chain of equations and
inequalities holds:

$\displaystyle V^{\pi_{t}}(r,\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)\geq$
$\displaystyle\
V^{\tilde{\pi}}(\hat{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}\cdot
P(A_{\Omega})$ $\displaystyle=$ $\displaystyle\
V^{\tilde{\pi}}(\hat{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}\cdot
P(A_{\mathcal{X}^{-}})$ $\displaystyle\geq$ $\displaystyle\
V^{\tilde{\pi}}(\hat{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}\cdot\delta_{g}$
$\displaystyle\geq$ $\displaystyle\
V^{\tilde{\pi}}(\tilde{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}\cdot\delta_{g}-\beta_{r}\cdot\sqrt{2Hd\log\left((t+H)/d\right)}$
$\displaystyle=$ $\displaystyle\
J_{\mathcal{X}}^{*}(\tilde{r},\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}\cdot\delta_{g}-\beta_{r}\cdot\sqrt{2Hd\log\left((t+H)/d\right)}$
$\displaystyle\geq$ $\displaystyle\
V^{*}(r,\bm{s}_{t},\bm{\phi}_{\bm{s}_{t}},g)-V_{\max}\cdot\delta_{g}-\beta_{r}\cdot\sqrt{2Hd\log\left((t+H)/d\right)}$

In this derivation, the second line follows from the assumption of
$\Omega=\mathcal{X}^{-}$, the third line follows from
$P(A_{\mathcal{X}^{-}})\leq\delta_{g}$, the fourth line follows from (Proof.),
the fifth line follows from the fact that $\tilde{\pi}$ is precisely the
optimal policy for $\tilde{R}$ and $\bm{b}$, the sixth line follows from Lemma
7, and the final line follows from the definition of $\epsilon_{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, we used 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: $\gamma=0.999$,
$\delta_{r}=0.05$, $\delta_{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. When obtaining the Figure 3, due to the
computational cost, we reduced $\gamma$ 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 this experiment, we used Intel(R) Xeon(R) Platinum 8180 CPU with 1 TB
RAM. We conducted an experiment using Safety-Gym environment with a goal and
multiple hazards. The objective of the agent is to reach the goal without
visiting hazards using a LiDAR sensor with 16 bins around a full circle 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: $\gamma=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 for our proposed method to
initialize the GLM and enable the agent to guarantee safety. Note that, for
fair 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\times
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

$\phi=[\,o_{\text{goal}},o_{\text{hazard}},1\,],$

where $o_{\text{goal}}$ and $o_{\text{hazard}}$ 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$