Safe Policy Optimization with Local Generalized Linear Function Approximations
Year: 2021

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.

heading: 1 Introduction
text: 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.
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
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
(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.

heading: 2 Problem Formulation
text: We consider a safety-constrained MDP, defined as a tuple

heading: M = 〈S,A, f,H, r, g,φ,ψ〉,
text: 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 step t ∈ 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 safety functions 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 a d-dimensional feature vector, where Bd := {x ∈ Rd | ‖x‖ ≤ 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 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 φ 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 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 ( 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) + n g t , with independent zero-mean noises nrt and n g t . Far-sighted observation is more related to feature vectors. In this observation scheme, an agent 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 basis of 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
maximize: V πM(st) = E [ H∑ τ=0 γτr(st+τ ) ∣∣∣∣∣π ] subject to: g(st) ≥ 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 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.
1For 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].
Assumption 1. The reward and safety functions are respectively represented using GLMs that are characterized 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) = 11+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 θ̃r and θ̃g be the MLEs for reward and safety, respectively. Here, θ̃r and θ̃g are the unique solutions of the following equations.
t∑ τ=0 ( r(sτ )− µr(φ>sτ θr) ) φsτ = 0 and t∑ τ=0 ( g(sτ )− µg(φ>sτ θg) ) φsτ = 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 first and second order derivatives are respectively bounded by L and M . Also, the link function µ satisfies ξ = inf‖θ −θ∗ ‖≤1,‖φs‖≤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 σ ; that is, for all t, we have E [ eω n
t | F t−1 ] ≤ eω2 σ2 /2, where {F n} is increasing sequences of
sigma fields such that n t is F t -measurable with E [ n t | F t−1 ] = 0.

heading: 3 Preliminary: Defining True Safe Space
text: 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 ∈ R≥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 inM. First, we simply consider a set of states that satisfy the safety constraint with a margin of . Given the set of states X , the following region can be identified as safe based on the far-sighted observation.
Y (X) = X ∪ {s ∈ S | ∃s′ ∈ X, s ∈ ψ(s′) : g(s)− ≥ h}. Second, we define reachability. The agent may not be able to reach a state that is in Y (·) due to unsafe states in the middle of the pathway. Given a set X , the states in Ψ that are reachable from X in one step are given by Yreach(X) = X ∪ {s′ ∈ Ψ | ∃s ∈ X, a ∈ A : s′ = f(s, a)}. Hence, an n-step reachable operator is given by Y nreach(X) = Yreach(Y n−1 reach (X)), where Y 1 reach(X) = Yreach(X). Finally, the set containing all the states that are reachable from X along an arbitrary long path in Ψ is defined as Ȳreach(X) = limn→∞ Y nreach(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 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 set of states X in one step is given by Yreturn(X, X̄) = X̄ ∪ {s ∈ X | ∃a ∈ A : f(s, a) ∈ X̄}. Thus, with Y 1return(X, X̄) = Yreturn(X, X̄), an n-step returnability operator is given by Y n return(X, X̄) = Yreturn(X,Y n−1
return (X, X̄)). The set containing all the states from which the agent can return to X̄ along an arbitrary long path in X is defined as Ȳreturn(X, X̄) = limn→∞ Y nreturn(X, X̄).
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 Zn (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
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)← minCt(s), ut(s)← maxCt(s) 6: S−t ← {s ∈ S | lt(s) ≥ h} 7: S+t ← {s ∈ S | ut(s) ≥ h} 8: X−t ← (2), X+t ← (3) 9: J∗(st)← (4) 10: if arg maxs∈Yreach({st}) J ∗(s) ⊆ X−t then 11: st+1 ← arg maxs∈(X−t ∩Yreach({st})) J ∗(s) 12: else 13: J̄∗(st)← (5) 14: while st 6= arg maxs∈X−t J̄
∗(s) do 15: st+1 ← arg maxs∈Yreach({st}) J̄
∗(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 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 exploration of safety as necessary (lines 12− 17). Note that the proofs of the lemmas are in Appendix C.

heading: 4.1 Confidence Intervals
text: 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 Ψt. Hereinafter, let the design matrix be Wt = ∑t τ=1 φsτφ > sτ . Also, the weighted L2-norm of φ associated with W −1 t is given by ‖φ‖W−1t = (φ >W−1t φ)
1/2. Finally, the maximum and minimum singular values of a matrix 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 basis of Theorem 1 in Li et al. [20], we have the following lemma.
Lemma 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 θ̃ ) | ≤ β · ‖φs‖W−1t .
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 M2 ξ−4 ( d2 + log δ−1 ) . Then, with a probability of at least 1− δ , for any s ∈ S \Ψ, we have
0 ≤ (s) ≤ µ (‖θ̃ ‖) + β · λmax(W−1t ).
The next lemma is on the relation between the upper bound defined above and the threshold, h. Lemma 3. Assume λmin(Wt) ≥ 512 ·σ2gM2g ξ−4g ( d2 + log δ−1g ) . Then, with a probability of at least 1− δg , we have µg(‖θ̃g‖) + βg · λmax(W−1t ) ≥ h.
Efficiency metric of exploration. Because βr and βg are constants independent from s, the efficiency of the exploration of the reward and safety functions depends solely on ‖φ‖W−1t within Ψt and λmax(W−1t ) 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 the second is to prepare a sufficiently large S0 and prohibit the agent from going outside of S0, until the condition on λmin(Wt) holds. In our experiment, we simply took the first approach.

heading: 4.2 Prediction of Safe Space
text: 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
Qt(s) =
{ [µg(φ
> s θ̃g)± βg · ‖φs‖W−1t ] if s ∈ Ψt,
[ 0, µg(‖θ̃g‖) + βg · λmax(W−1t ) ] otherwise. (1)
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 by lt(s) := minCt(s) and ut(s) := maxCt(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 lt; that is, S−t := { s ∈ S | lt(s) ≥ h }. The desired pessimistic safe space, X−t is a subset of S−t and also satisfies the reachability and returnability constraints; that is,
X−t = S−t ∩ Ȳreach(X−t−1) ∩ Ȳreturn(S − t ,X−t−1). (2)
Predicted optimistic safe space. To optimize a policy, we need to incorporate the reward not only in 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 := { 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 terms of 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 and returnability. The resulting optimistic safe region is given by
X+t = S+t ∩ Ȳreach(X+t−1) ∩ Ȳreturn(S + t ,X+t−1). (3)

heading: 4.3 Safe Policy Optimization based on OFU Principle
text: As discussed in Section 4.1, we can efficiently explore reward and safety simultaneously by focusing on ‖φ‖W−1t and λmax(W −1 t ). 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:
J∗(st)= max s∈X+t
[ R(s) + γJ∗(s) ] where R(s) :=
{ µr(φ
> s θ̃r) + βr‖φs‖W−1t if s ∈ Ψt,
µr(‖θ̃r‖) + βrλmax(W−1t ) otherwise. (4)
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 max s∈(X−t ∩Yreach({st})) J∗(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 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 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 s∈Yreach({st})
J∗(s),
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 X−t , the agent can simply execute the next 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 st+1∈X−t
[ ‖φst+1‖W−1t + γJ̄ ∗(st+1) ] . (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).

heading: 5 Theoretical Analysis
text: 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
λmin(Σ)t− C1 √ td− C2 √ t log(δ−1g ) ≥ max { βg , 1 } with Σ = E[φtφ>t ]. Then, for all t > t∗, the following inequalities hold.
|µg(φ>θ∗g)− µg(φ>θ̃g) | ≤ and t+H∑ τ=t+1 ‖φsτ ‖W−1τ ≤
√ 2Hd log ( t+H
d
) .
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 · σ2gM 2 g ξ −4 g ( d2 + log δ−1g ) holds. Suppose that the next state is chosen from X−t . 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 X−t (⊆ S−t ), and S−t is characterized with l(s). Since g(s) is greater than l(s) with a probability of at least 1− δg, our algorithm guarantees that the agent will execute only safe actions.2
2Unlike 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∗ + |Z̄0(S0)| and
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= η 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 ε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 ∗.

heading: 6 Experiments
text: 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

heading: 6.1 Grid World
text: 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 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× 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 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.
3https://github.com/akifumi-wachi-4/spolf
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 SPOLF 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 nonoptimal reward. Figure 2(b) compares the performance of SPO-LF with different sizes of field of view (FOV) from 1 × 1 to 13 × 13. For a larger FOV, the convergence of the algorithm got faster. Given that SPO-LF (FOV 1× 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 × 150 states. In the GLM-based methods, most of the computational cost when obtaining confidence bounds is for calculating λmax(W−1t ). This computational complexity is O(d3), which does neither depend on the number of states nor samples. Finally, the average number of unsafe actions was 3.4 for UNSAFE GLM, 49.0 for RANDOM, and 0.0 for the other methods.

heading: 6.2 Safety-Gym
text: 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 ·∆goal when getting closer to the goal, where ∆goal is the amount of decrease in 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., 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 µ(x) = 11+e−x as the link function. As for implementing the three baselines, our experiments largely depended on the “safetystarter-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.

heading: 7 Conclusion
text: 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.

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

Review summaries:
This paper proposes SPO-LF, a safe learning algorithm for sequential decision making. The key idea is to predict a pessimistic safe space and an optimistic safe space based on the confidence intervals, and constrains the exploration in the safe space. The proposed algorithm is evaluated in the mini-grid and the safety-gym environments, compared with several baselines, and claimed to be able to handle large-scale problems, and behave more safely than the CMDP-based deep RL algorithms.

This paper studies the problem of safe exploration in reinforcement learning contexts. It develops a new algorithm which, by making several assumptions, can stay safe while exploring and achieves good sample efficiency. The proposed approach incorporates sensor measurements ("far-sighted observations") and estimates of safety based on those observations, as well as the idea of an optimistic and pessimistic safe set, to stay safe during exploration. It also introduces a novel way to ensure that the algorithm does not get stuck in a safe area by detecting this case and more aggressively expanding the set of considered exploration actions.