Long-Term Safe Reinforcement Learning with Binary Feedback
Akifumi Wachi1 , Wataru Hashimoto2 , Kazumune Hashimoto2
1

LINE Corporation
Osaka University
akifumi.wachi@linecorp.com, hashimoto@is.eei.eng.osaka-u.ac.jp, hashimoto@eei.eng.osaka-u.ac.jp
2

Binary safety feedback

Abstract
Safety is an indispensable requirement for applying reinforcement learning (RL) to real problems. Although there
has been a surge of safe RL algorithms proposed in recent
years, most existing work typically 1) relies on receiving numeric safety feedback; 2) does not guarantee safety during
the learning process; 3) limits the problem to a priori known,
deterministic transition dynamics; and/or 4) assume the existence of a known safe policy for any states. Addressing theissues mentioned above, we thus propose Long-term Binaryfeedback Safe RL (LoBiSaRL), a safe RL algorithm for constrained Markov decision processes (CMDPs) with binary
safety feedback and an unknown, stochastic state transition
function. LoBiSaRL optimizes a policy to maximize rewards
while guaranteeing a long-term safety that an agent executes
only safe state-action pairs throughout each episode with highprobability. Specifically, LoBiSaRL models the binary safetyfunction via a generalized linear model (GLM) and conservatively takes only a safe action at every time step while inferring its effect on future safety under proper assumptions.
Our theoretical results show that LoBiSaRL guarantees thelong-term safety constraint, with high probability. Finally, ourempirical results demonstrate that our algorithm is safer thanexisting methods without significantly compromising performance in terms of reward.

1

Introduction

Safe reinforcement learning (RL) is a promising paradigm
for applying RL algorithms to real-world applications(Garcıa and Fernández 2015). Safe RL is beneficial
in safety-critical decision-making problems, such as autonomous driving, healthcare, and robotics, where safety
requirements must be incorporated to prevent RL policies
from posing risks to humans or objects (Dulac-Arnold et al.
2021). As a result, safe RL has received significant attention in recent years as a crucial issue of RL during both thelearning and execution phases (Amodei et al. 2016).
Safe RL is typically formulated as constrained policy
optimization problems where the expected cumulative reward is maximized while guaranteeing or encouraging thesatisfaction of safety constraints, which are modeled as
constrained Markov decision processes (CMDPs, Altman
Copyright © 2024, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

Instantaneous

Long-term

Safe Unsafe(Future trajectory)Time

Figure 1: Even if safety is guaranteed at time t based on
the instantaneous evaluation, safe behavior may not exist a
few steps ahead. This paper requires an agent to guarantee
long-term safety (i.e., constraint satisfaction from the time
the current time step t to the terminal time step T ) in CMDPs
with stochastic state transition and binary safety feedback.

(1999)). While there are various types of constraint representations, most of the existing studies formulated constraints using either expected cumulative safety-cost (Altman 1999) or conditional value at risk (CVaR, Rockafellar,
Uryasev et al. (2000)); thus, satisfying safety constraints almost surely or with high probability received less attention
to date. Imagine highly safety-critical applications (e.g., autonomous driving, healthcare, robotics) where even a single constraint violation may result in catastrophic failure. In
such cases, RL agents need to ensure safety at every time
step at least with high probability; thus, constraint satisfaction “on average” does not fit the purpose due to a large number of unsafe actions during the learning process (Stooke,
Achiam, and Abbeel 2020).
Several previous work on safe RL aimed to guarantee
safety at every time step with high probability, even during the learning process. Unfortunately, however, existing
work has room for improvement. First, most of the previous work (Wachi and Sui 2020; Amani, Thrampoulidis, andYang 2021; Roderick, Nagarajan, and Kolter 2021) assumes
numeric safety feedback. In many cases, however, the safety
feedback can only take binary values indicating whether astate-action pair is safe or unsafe, which is particularly true
when feedback comes from humans. As existing studies onsafe RL with binary safety feedback, Wachi, Wei, and Sui(2021) modeled the safety function via a generalized lin-

State transition
Wachi and Sui (2020)
Amani, Thrampoulidis, and Yang (2021)
Wachi, Wei, and Sui (2021)
Bennett, Misra, and Kallus (2023)
LoBiSaRL (Ours)

Known

D/S

Yes
Linear
Yes
No
No

D
S
D
S
S

SafetyAdditional assumption(s)GP
Linear
GLM
GLM
GLM

Known safe policy
Known safe policy
Lipschitz continuity & conservative policy

Table 1: Comparison among existing work regarding their assumptions on a state transition, safety function, and others. In theabove table, D means deterministic state transition, and S means stochastic state transition.
ear model (GLM) while they assume known and deterministic state transition function. Thus, this previous work cannot deal with general RL problems with unknown stochastic
state transition functions. Also, Bennett, Misra, and Kallus(2023) addressed safe RL problems with binary safety feedback and unknown stochastic state transition under the assumption that a known safe action always exists for any
state. This assumption is not valid in many safety-critical applications. For example, even an F1 driver cannot take a safe
action if a vehicle traveling at 100 km/h is 1 meter aheadof a brick wall; thus, to avoid such situations, we need toconsider “long-term” future safety under more reasonableassumptions, as shown in Figure 1.
Contributions. We propose an algorithm called Longterm Binary-feedback Safe RL, LoBiSaRL. This algorithm
enables us to solve safe RL problems with binary feedback
and unknown, stochastic state transition while guaranteeing the satisfaction of long-term safety constraints. LoBiSaRL guarantees safety by modeling the binary safety function via a GLM and then pessimistically estimating the future safety function values. Our theoretical analysis showsthat future safety can be pessimistically characterized by
1) inevitable randomness due to the stochastic state transition and 2) divergence between the current policy and areference policy to stabilize the state. Based on this theoretical result, we optimize the policy to maximize the expectedcumulative reward while guaranteeing long-term safety. Finally, we empirically demonstrate the effectiveness of the
LoBiSaRL compared with several baselines.

2

Related Work

Safe RL. In typical safe RL problems, an agent must maximize the expected cumulative reward while ensuring thatthe expected cumulative cost is less than a threshold. There
have been a number of algorithms for solving this type ofsafe RL problem, as represented by constrained policy optimization (Achiam et al. 2017), reward constrained policy optimization (Tessler, Mankowitz, and Mannor 2018),
Lagrangian-based actor-critic (Chow et al. 2017), primaldual policy optimization (Yang and Wang 2020). In the previous papers mentioned above, however, a safety constraint
is defined using the (expected) cumulative value and the constraint satisfaction is not guaranteed during the learning process (Stooke, Achiam, and Abbeel 2020). Hence, most of
the existing studies deal with less strict safety constraints

than our study that requires the agent to satisfy safety constraints at every time step. There has been research aimed
at guaranteeing safety at every time step, even during thelearning process. For example, Turchetta, Berkenkamp, andKrause (2016) proposed notable algorithms that satisfy thesafety constraint with high probability by inferring the safetyfunction via a Gaussian process (GP). Also, Wachi, Wei, andSui (2021) proposed its extended algorithm that models thesafety function via a GLM, which can also deal with safe
RL problems with binary feedback. Though they succeededin guaranteeing safety with high probability, their theoreticalresults are based on the assumptions of the known and deterministic state transition function. It is essentially difficult
to extend these algorithms to our problem settings with unknown and stochastic state transitions. As existing work onsafe RL with unknown stochastic transition, Amani, Thrampoulidis, and Yang (2021) proposed an algorithm for linear MDPs with safety constraints while Bennett, Misra, andKallus (2023) proposed an algorithm for safe RL problems
with binary safety feedback and stochastic transitions. Although such work proposed excellent algorithms for challenging problems, the existence of a known safe policy is
assumed for any state, which does not hold in many realworld applications as discussed in Section 1 (i.e., high-speed
vehicle example). Table 1 summarizes the problem settings
considered in existing work and this paper.

Long-term safety. In the control community, long-term
safety has been well-studied under the name of control barrier function (CBF, Ames et al. (2019)). For any state s, a
CBF is a continuously differentiable function h(s) that defines a safe set {s : h(s) ≥ 0}, i.e., an invariant set where
any trajectory starting inside the set remains within the set.
The CBF is to maintain safety during the learning process,which is particularly useful for keeping a manipulator withina given safe space or ensuring that a robot avoids obstacles.
This advantage is beneficial for RL settings, and Cheng et al.
(2019) proposed a safe RL algorithm to guarantee long-term
safety via CBFs. Unfortunately, however, humans need tomanually define proper CBFs and it is often hard to findthem. In addition, Koller et al. (2018) proposed a learningbased model predictive control scheme that provides highprobability safety guarantees during the learning process under the assumption that both a dominant term of the statetransition function and safe region are known a priori.

3

Problem Statement

We consider episodic finite-horizon CMDPs, which can beformally defined as a tuple
M := (S, A, P, T, r, g, s1 ),(1)where S is a state space {s}, A is an action space {a},P : S × A → ∆(S) is an unknown, stochastic state transition function to map a state-action pair to a probability distribution over the next states, T ∈ Z+ is a fixed length ofeach episode, r : S × A → [0, 1] is a (bounded) reward
function, g : S × A → {0, 1} is an unknown binary safetyfunction, and s1 ∈ S is the initial state.1 Crucially, in this paper, the safety feedback is provided as a binary value; that is,g(s, a) = 1 means that a state-action pair (s, a) is safe, andotherwise (s, a) is unsafe. At the time step t and the current
state st , the agent takes the next action at , receiving the next
state st+1 ∼ P (· | st , at ) as well as the safety observationg(st , at ), until the terminal time step T . We suppose thatsafety observations contain some independent zero-meannoise nt . We assume that the noise nt is sub-Gaussian with
fixed (positive) parameters σ ∈ R+ ; that is, for all t, we
2 2have E [ eωnt | Gt−1 ] ≤ eω σ /2 , where {Gt } is increasing sequences of sigma fields such that nt is Gt -measurablewith E [ nt | Gt−1 ] = 0. This assumption has been commonly made in previous work (e.g., Abbasi-yadkori, Pál,and Szepesvári (2011), Li, Lu, and Zhou (2017)).
A deterministic policy of an agent π : S → A represents
a function to return actions. A metric of the quality of thepolicy π is the following value function, i.e., the expectedvalue of cumulative rewards, which is defined as
" T
#
X
π
Vt (s) := Eπr(sτ , aτ ) st = s ,τ =t

for all s ∈ S and t ∈ [T ], where the expectation Eπ [·] istaken over the trajectories {(sτ , aτ )}Tτ=t induced by the policy π and true state transition dynamics P . We additionallydefine the following action-value function (i.e., Q-function)
which means the expected value of total rewards when theagent starts from state-action pair (s, a) at step t and follows
policy π, which is represented as
" T
#
X
π
Qt (s, a) := Eπr(sτ , aτ ) st = s, at = a ,τ =t

for all (s, a) ∈ S × A and t ∈ [T ].
A crucial point of this paper is that we wish the agent
to take only safe actions at every time step t; that is, theagent needs to take a safe action at at a state st that satisfies
the safety constraint; that is, g(st , at ) = 1. As discussed in
Section 1, however, at time t, the agent is required to execute
safe actions in the long run so that there also will be future
safe actions from time t + 1 to T . Hence, at every time stept, we impose the following safety requirement:noPr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ 1 − δ,(2)
1
We assume that reward function is known and deterministic,
but all results presented here extend to unknown stochastic cases.

where δ ∈ [0, 1] is a small positive scalar. Our safety constraint is probabilistic since it is extremely difficult to guarantee safety almost surely (i.e., probability of 1) due to theunknown stochastic state transition and safety functions.
Goal. Let us clearly describe the goal we wish to achievein this paper. The objective of the agent is to obtain the optimal policy π ⋆ : S → A to maximize the value function
Vtπ (st ) under the safety constraint (2) such thatnomax Vtπ (st ) s.t. Pr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ 1 − δ.
π

It is quite hard to guarantee the satisfaction of the aforementioned constraint. It is because even if the agent executes anaction at at time t and state st such thatno
Pr g(st , at ) = 1 ≥ 1 − δ,(3)there may not be any viable action at st+1 ∼ P (st , at ) andfurther future states. Thus, the agent must execute an action at to guarantee the constraint satisfaction not only for(st , at ) but also for (sτ , aτ ) for all τ ∈ [t + 1, T ]. Our safety
constraint (2) is challenging, which we will call the longterm safety constraint in the rest of this paper, while we willcall (3) the instantaneous safety constraint.
Difficulties and assumptions. The aforementioned problem we wish to solve has several difficulties. First, if thebinary safety function does not exhibit any regularity, it is
impossible to infer the safety of state-action pairs. For example, if the safety function value is totally random, we canneither foresee danger nor guarantee safety. In addition, we
suppose the state transition is stochastic and unknown a priori despite that the agent must guarantee the satisfaction of
the long-term safety constraint. This difficulty requires us to
explicitly incorporate the stochasticity of the state transition
and its influence on future safety.
For the first difficulty, we assume that the safety function can be modeled as a GLM to deal with binary safety
feedback. GLMs have been studied for sequential decisionmaking problems with binary feedback especially in (stateless) multi-armed bandit literature (Filippi et al. 2010; Li,
Lu, and Zhou 2017; Faury et al. 2020) under the name of logistic bandits. Also, in (stateful) RL settings, Wachi, Wei,
and Sui (2021) addressed a safe RL problem where thesafety function is subject to a GLM under the assumptionthat the state transition is a priori known and deterministic.
We now make the following assumption of the GLM structure of the safety function.
Assumption 1. There exists a known feature mapping function ϕ : S × A → Rm , unknown coefficient vectors w⋆ ∈Rm , and a fixed, strictly increasing (inverse) link functionµ : R → [0, 1] such thatE[ g(s, a) | s, a ] = µ f ⋆ (s, a) ,(4)
for all (s, a) ∈ S × A, where f ⋆ : S × A → R is a linear
predictor defined asf ⋆ (s, a) := ⟨ϕ(s, a), w⋆ ⟩,∀(s, a) ∈ S × A.

(5)

Without loss of generality, we further assume∥ϕ(s, a)∥2 ≤√1 for all (s, a) ∈ S × A and ∥w⋆ ∥2 ≤ m.

In the case of the binary safety function, a suitable choiceof the link function is µ(x) = exp(x)/(1 + exp(x)), leading to the logistic regression model. GLMs are more general models, and one can verify that linear and integervalued functions are special cases of GLMs with µ(x) = x
and µ(x) = exp(x) leading to the linear regression modeland the Poisson regression model, respectively; hence, ourmethod can be extended to other problem settings than thebinary safety function.
In addition to the boundedness assumption on the feature
vectors and safety function values, we make the following
assumption regarding the link function.
Assumption 2. The link function µ is twice differentiable, and the first and second-order derivatives are respectively bounded. Also, the link function µ satisfies ξ =inf ∥w−w⋆ ∥≤1,∥ϕ∥≤1 µ̇(⟨ϕ, w⟩) > 0.
By making Assumptions 1 and 2, it is possible to guarantee the satisfaction of the instantaneous safety constraint (3)at the current time step t if there are feasible actions, as conducted in Wachi, Wei, and Sui (2021). In this paper, however, the agent must guarantee safety until the terminal time
step T (i.e., long-term safety constraint) under stochastic
state transition, which requires us to make further assumptions. If the feature mapping function drastically changes
with minor differences in state-action pairs, it is extremely
difficult to continue to guarantee safety until T . Thus, we
assume the regularity of the feature mapping function as aform of Lipschitz continuity, which is written as follows:
Assumption 3. For all s, s̄ ∈ S and a, ā ∈ A, the feature
mapping function ϕ(·, ·) is Lipschitz continuous with a constant Lϕ ∈ R+ ; that is,∥ϕ(s, a) − ϕ(s̄, ā)∥2 ≤ Lϕ · dSA ((s, a), (s̄, ā)),(6)
where dSA (·, ·) is a distance metric on S ×A. For ease of exposition, we assume that dSA satisfies dSA ((s, a), (s̄, ā)) =dS (s, s̄) + dA (a, ā).
Intuitively, this assumption implies that, for similar stateaction pairs (s, a) and (s̄, ā), the features ϕ(s, a) and ϕ(s̄, ā)also exhibit similar values. This assumption is related to thecommon assumption in RL literature as represented by Lipschitz MDP (Asadi, Misra, and Littman 2018; Ok, Proutiere,and Tranos 2018).
Similarly, at a current state s, if the next state s′ ∼P (· | s, a) induced by an “insignificant” action a (that tries
to maintain the status quo) is far from s, the safety may
drastically changes. Hence, we assume the existence of a
Lipschitz-continuous conservative policy π ♯ : S → A to
suppress the state transition distance within a certain value.
We then assume that, as far as similar policies to the conservative policy are executed, the state-transition distance canbe suppressed. Specifically, for any policy π, we assume thatthe (one-step) state transition from time t to t + 1 is upperbounded according to the divergence between the actions
taken by π and π ♯ .
Assumption 4. Let L♯ ∈ R+ be a positive scalar. Thereexists a known L♯ -Lipschitz continuous policy π ♯ : S → A
such that, for any states s, s̄ ∈ S,
dA (π ♯ (s) − π ♯ (s̄)) ≤ L♯ · dS (s, s̄).

(7)

Also, with a positive scalar η ∈ R+ , for any policy π : S →A, the following inequality holds for all s ∈ S:
max

s′ ∼P (·|s,π(s))

dS (s, s′ ) ≤ d¯ + η · dA (π(s), π ♯ (s)).

Remark 1. Assumption 4 implies that the conservative policy π ♯ keeps the amount of the (one-step) state transition
within a certain distance d¯ ∈ R+ ; that is,max

s′ ∼P (·|s,π ♯ (s))¯
dS (s, s′ ) ≤ d.

In the case of stochastic policies, we can use Kantorovich
distance K(·, ·) to define the Lipschitz continuity of a policy; that is, K(π(· | s), π(· | s̄)) ≤ Lπ · dS (s, s̄). Thus, thefollowing theoretical analysis can be extended to stochastic
policy settings. This assumption is valid in many physicalsystems (e.g., control-affine systems). Intuitively, when thepolicy π is similar to the conservative policy π ♯ , the upperbound of the state transition is guaranteed to be small. Assumption 4 implies that when π = π ♯ , the state transition¯ Also, as π bedistance is always less than or equal to d.
♯comes far from π , the distance can be larger with respect
to the term η · dA (π, π ♯ ). The existence of π ♯ is not restrictive in practice for a number of applications, and similar notions have been adopted in many existing studies under thename of the stable or telescoping policies (Lin et al. 2021;
Tsukamoto, Chung, and Slotine 2021). For instance, withthe autonomous vehicle, one may select π ♯ as the one tomove it at a low constant speed, and π is optimized suchthat it can move faster under the safety constraint.

4

Characterizing Safety

Based on the problem settings and assumptions presented
in Section 3, we now present how to guarantee long-term
safety. Optimism and pessimism are essential notions in RL.
Conventionally, being optimistic has been well-adopted in
online RL literature under the name of optimism in the faceof uncertainty principle (Strehl and Littman 2008; Auer andOrtner 2007). In contrast, pessimism is also significant when
an RL agent is trained from offline data (Jin, Yang, and Wang
2021; Buckman, Gelada, and Bellemare 2020) or needs tosatisfy safety constraints (Bura et al. 2022). A natural way
to incorporate optimism and pessimism is to derive the upperand lower bounds of the functions of interest, which can be
conducted in a way backed by theory.
This paper expresses the upper and lower bounds in two
ways. The first is inferred by the GLMs. While the advantage of this approach is to provide accurate estimation oncea larger amount of dataset has been collected, the uncertainty
term tends to be loose in the early phase of the training.
The second is based on Lipschitz continuity. In contrast to
the GLM-based approach, this approach provides moderatebounds regardless of the amount of collected data, which
is typically useful in the early phase of training. Thus, intuitively, we aim to continue to derive tight bounds by deriving
them using the approach based on Lipschitz continuity in theearly phase and that based on the GLMs in the later phase.

4.1

Confidence Intervals Inferred by GLMs

We first present how to obtain theoretically-guaranteed
confidence bounds inferred by P
the GLMs. Hereinafter, letn⊤the design matrix be Wn =j=1 ϕ(sj , aj )ϕ(sj , aj ) ,where n ∈ Z+ is the total number of data. Also, the−1weighted L2 -norm
p of ϕ associated with Wn is given by−1∥ϕ∥Wn−1 := ϕ⊤ Wn ϕ. Here, the maximum-likelihood
estimators (MLE) denoted as ŵ is calculated by solving thefollowing equation:nXg(sj , aj ) − µ(⟨ ϕ(sj , aj ), w ⟩) ϕ(sj , aj ) = 0,
j=1

Based on Li, Lu, and Zhou (2017), the following lemma regarding the confidence bounds on f ⋆ holds.
q3
Lemma 1. Let ∆ > 0 be given and β = 3σlog ∆. Then,ξwith a probability of at least 1 − ∆, the MLE satisfies|f ⋆ (s, a) − ⟨ϕ(s, a), ŵ⟩| ≤ β · ∥ϕ(s, a)∥Wn−1 ,for all (s, a) ∈ S × A.
Therefore, at time t and state st , by choosing the next action
at such that ⟨ϕ(st , at ), ŵ⟩ − β · ∥ϕ(st , at )∥Wn−1 ≥ z, we
can also guarantee the satisfaction of f ⋆ (st , at ) ≥ z withhigh probability, where z ∈ R is a certain threshold.

4.2

Bounds by Lipschitz Continuity

We then present the upper and lower bounds inferred by the
Lipschitz continuity. Let us first define an important variable
xt ∈ R+ called maximum divergence from the conservative
policy (MDCP) such thatdA (π(st ), π ♯ (st )) ≤ xt , ∀t ∈ [T ].
(8)
The MDCP indicates how far the action taken by π is fromthat by π ♯ . Hereinafter, the summation of this new variable xt plays a critical role when dealing with P
the long-termtt2
safety constraint, and thus we define Xt1 := τ2=t1 xτ forany time steps t1 , t2 ∈ [T ] with t1 < t2 . We have the following two lemmas regarding the (true) safety linear predictor
f ⋆ . See Appendices A.2 and A.3 for the proofs.
Lemma 2. Suppose the policy π satisfies (8). Let L1 , L2 ,and L3 be constants that are respectively defined as√¯ L3 := 2 + η L̄♯ .
L1 := m · Lϕ , L2 := L̄♯ · d,
P −1
T −1
:= Tτ =t+1
Set t̄ := T −t and recall that Xt+1
xτ . Finally,
with xt:T := xt , xt+1 , . . . , xT , defineT −1F(t, xt:T ) := L1 L2 t̄ + (L3 − 1)xt + L3 Xt+1
+ xT .
Then, we have|f ⋆ (sT , π(sT )) − f ⋆ (st , π(st ))| ≤ F(t, xt:T ).
Intuitively, Lemma 2 characterizes the present-to-future difference in terms of f ⋆ , which provides us the lower boundof the future safety linear predictor.
Lemma 3. Define f ♯ (s) := f ⋆ (s, π ♯ (s)) for all s ∈ S. Also,
suppose the policy π satisfies (8). Then, we havef ⋆ (st , π(st )) − f ♯ (s1 ) ≤ L1 L2 t + L3 X2t−1 + xt .
In contrast to Lemma 2, Lemma 3 characterizes the past-topresent difference in terms of f ⋆ . Using this lemma, we infer
the lower bound of f ⋆ at the current time step t.

4.3

Resulting Lower Bound of f ⋆As we discussed previously, it is a simple yet powerful way
to use the safety lower bound for introducing pessimism insafe RL. Let ℓ : S ×A → R denote a lower bound of the true
safety linear predictor, f ⋆ . To obtain a tighter bound, this paper combines the two lower bounds presented in Section 4.1
and 4.2, respectively. Specifically, based on Lemma 1 and 3,
we obtain the following tighter bound:ℓ(st , at ) := max ℓGLM (st , at ), ℓLipschitz (st , at ) ,(9)where ℓGLM : S × A → R and ℓLipschitz : S × A → R
are pessimistic safety linear predictors inferred by GLM and
Lipshitz continuity, which are respectively defined asℓGLM (st , at ) := ⟨ϕ(st , at ), ŵ⟩ − β · ∥ϕ(st , at )∥Wn−1 ,ℓLipschitz (st , at ) := f ♯ (s1 ) − L1 L2 t + L3 X1t−1 + xt .

4.4

Long-term Safety Guarantee

We present theoretical results regarding the lower bound of
the safety linear predictor f ⋆ , which leads to the long-term
safety guarantee defined by (2). We now present a lemma
regarding the safety linear predictor at time t.
Lemma 4. At every time step t ∈ [T ], we havef ⋆ (st , at ) ≥ ℓ(st , at )(10)with a probability of at least 1 − ∆.
This lemma implies that we can guarantee the instantaneoussafety constraint (3) by choosing the next action such thatℓ(st , at ) ≥ z,with µ(z) = 1 − δ,(11)with a probability of at least 1 − ∆.
In this paper, however, we need to additionally require thesatisfaction of the long-term safety constraint; thus, we areparticularly interested in future safety. We now provide thefollowing lemma in terms of the pessimistic safety linear
predictor at the terminal time step T :Lemma 5. Recall T is the terminal time step and set t̄ =T − t. At every time step t ∈ [T ], we havef ⋆ (sT , aT ) ≥ ℓ(st , at ) − F(t, xt:T ),with a probability of at least 1 − ∆.
Corollary 1. Suppose, at state st , the agent with a policy π
executes the action at while tuning xt , xt+1 , . . . , xT so thatℓ(st , at ) − F(t, xt:T ) ≥ z(12)holds. Then, for all τ ∈ [t, T ], there exist safe state-action
pairs (sτ , aτ ) such that:f ⋆ (sτ , aτ ) ≥ z,

τ ∈ [t, T ],(13)

with a probability of at least 1 − ∆.
The proofs of Lemma 5 and Corollary 1 are written in Appendix A.4.
Finally, we present a main theorem on the long-term
safety constraint. Specifically, we guarantee that an agent
continues to take safe actions from time t to T with a higher
probability than a predefined threshold, by properly tuning
the MDCPs, xτ for all τ ∈ [t, T ].

Bounds by Lipchitz-continuity for 𝜋

Bounds by Lipchitz-continuity for 𝜋 #Bounds by GLM

Safety margin at time 𝑡

Safety margin decreases
by 𝑥! , 𝑥" , … , 𝑥#$!

Time

Safety margin may
increase as GLM-based
estimator gets accurateTime(a) Conservative policy(b) Early phase (Lipschitz)

Time(c) Later phase (GLM)

Figure 2: (a) Bounds by Lipschitz continuity for the conservative policy. (b) In the early phase of training, the lower boundof the safety linear predictor at time t is typically characterized by the Lipschitz continuity, which decreases depending on thex1 , x2 , . . . , xt−1 . Depending on the safety margin at time t, we need to control xt , xt+1 , . . . , xT for ensuring future safety. (c)As the training proceeds, the lower bound of the safety linear predictor can potentially be characterized by the GLMs, and thesafety margin may increase.
Theorem 1. Suppose, at state st , the agent executes the action at while tuning the MDCPs xt , xt+1 , . . . , xT so that(12) holds. Set δ := 1 − (1 − µ(z))t̄ . Then, we havenoPr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ 1 − δ, ∀t ∈ [T ],— i.e. the long-term safety constraint is satisfied — with aprobability of at least 1 − ∆.
This theorem guarantees that at every time step t, the agent
can take safe actions from t to T with high probability, despite unknown, stochastic state transition and binary safety
feedback. The proof sketch is as follows. By Corollary 1,
when (12) is satisfied, f ⋆ (xτ , aτ ) ≥ z holds for all τ ∈[t, T ] with high probability; that is, the existence of future
safe actions are guaranteed with high probability. Theorem 1
provides a stricter safety guarantee than the one in existing safe RL literature with instantaneous safety constraints
such as Wachi, Wei, and Sui (2021). If we tried to guarantee
safety while using the instantaneous constraint (3), the agent
would fall into worse situations and then lose the choices ofsafe actions due to the stochastic state transition.

5

LoBiSaRL Algorithm

We finally propose our LoBiSaRL algorithm. The algorithm
flow is shown in Algorithm 1. Based on Theorem 1, weshould solve the following policy optimization problem under a (conservative) long-term safety constraint:
max Vtπ (st )πAlgorithm 1: Long-term Binary Safe RL (LoBiSaRL)
1: Input: Initial Lagrange multiplier λ1 . Constants L1 , L2 , andL3 . conservative policy π ♯ .
2: for iteration i = 1, 2, . . . do3:for time t = 1, 2, . . . , T do
4:πt ← argmaxπ Vtπ (st ) − λi −xt + L3 XtT −1 + xT
5:At ← {a ∈ A | ℓ(st , a) − L1 {L2 t̄ + (L3 − 1)xt } ≥ z}
6:
if πt (st ) ∈ At then7:at ← πt (st )
8:
else
9:
at ← argmina∈At ∥a − πt (st )∥2
10:
Take at and then receive a next state st+1 ∼ P (st , at ),reward r(s, a), and (binary) safety g(s, a).
11:Update value function Vtπ
12:
Hi := mint (ℓ(st , π(st )) − z)13:Update the Lagrange multiplier to λi+1 based on Hi

A key to solving the aforementioned constrained policy
optimization problem is how we tune xτ for all τ = [t, T ].
Intuitively, we want to set x to be large in terms of reward
maximization while x should be small in terms of long-term
safety guarantee. Hence, we use a Lagrangian method tosimultaneously maximize the expected cumulative reward
while tuning the magnitude of x for the satisfaction of thesafety constraint. Specifically, with a Lagrange multiplier
λ ∈ R+ , we solve the following max-min problem:
max min Vtπ (st ) − λ · (−xt + L3 XtT −1 + xT ).
πsubject to ℓ(st , at ) − F(t, xt:T ) ≥ z.

Note that, the term F(t, xt:T ) can be transformed intoT −1F(t, xt:T ) = L1 · L2 t̄ + (L3 − 1)xt + L3 Xt+1
+ xT .
|{z} | {z } |
{z
}
(A)

(B)

(C)

The above inequality can be interpreted as follows. (A) is
an inevitable term that even the conservative policy π ♯ cannot avoid. (B) depends only on the current action at time t,and (C) depends on the future actions from time t + 1 to T .
We can make (B) and (C) terms zero by executing the sameactions as the conservative policy.

λ≥0

(14)

By setting λ large, we enforce the agent to make x small
and thus execute similar actions to the conservative policy.
When the conservative policy has much safety margin, theagent should explore the state and action spaces while taking
more different actions. The degree of freedom is optimized
by means of the Lagrange multiplier λ.
For the current policy π, the minimum safety requirementthat the agent needs to satisfy at every time step t isℓ(st , π(st )) − L1 {L2 t̄ + (L3 − 1)xt } ≥ z.
(15)
The aforementioned inequality is derived by setting the (C)term to be 0, which corresponds to executing the same actions to the conservative policy from time t+1 to T . In other

20
18
16
14
12
10
8
6
4
2
0

25
20
15
10
5
0 2 4 6 8 10 12 14 16 18 200(a) Reward function.

20
18
16
14
12
10
8
6
4
2
0

1.0
0.8
0.6
0.4
0.2
0 2 4 6 8 10 12 14 16 18 20

0.0

20
18
16
14
12
10
8
6
4
2
0

(b) Binary safety function.

250
200
150
100
0 2 4 6 8 10 12 14 16 18 2050(c) Value function with safety.

Figure 3: Example reward, binary safety, and value functions. In this paper, we consider a safe RL problem with binary safety
feedback; thus, there is an unsafe region (the white region in the (c)) where the agent is not allowed to visit.
words, at time step t, the next action at must be chosen withthe following “safe” action set:
At := {a ∈ A | ℓ(st , a) − L1 {L2 t̄ + (L3 − 1)xt } ≥ z}.
To optimize the Lagrange multiplier λ, we define the following minimum safety margin at i-th episode:
Hi := min (ℓ(st , π(st )) − z) .

R ANDOMU NSAFE
L INEARI NSTANTANEOUS
LoBiSaRL (Ours)

RewardUnsafe actions

0.32 ± 0.24
1.00 ± 0.00
0.73 ± 0.13
0.86 ± 0.10
0.76 ± 0.12

23.2 ± 10.3
26.8 ± 13.6
18.3 ± 5.7
3.3 ± 2.2
0.0 ± 0.0tWhen Hi is large, the agent is allowed to explore further bytaking different actions from the conservative policy. In contrast, when Hi is small, the agent needs to prioritize safety
without diverging from the conservative policy.

6

Experiments

In this section, we evaluate the performance of LoBiSaRL in
a synthetic grid-world environment.
Settings. This environment is 20 × 20 square grids inwhich reward and safety functions are randomly generated.
To avoid trivial situations where the optimal policy wanders
around the initial position (0, 0), we generate the reward
function so that the reward-rich region is far from the initial state. The safety function is generated so as to follow a
GLM, and the agent receives the binary safety feedback. At
every time step, the agent takes an action from four action
candidates (up, right, down, left). Also, the state transition
function is stochastic; thus, the agent can go in the intended
direction 80% of the time (if there is no wall). We provide
10 initial samples for initializing the GLM and set T = 50.
Baselines. We compare the performance of LoBiSaRL with four baselines. The first baseline is called R AN DOM agent, which randomly chooses the next action without any consideration of reward and safety. The second is a
U NSAFE agent. This agent purely maximizes the cumulative
reward while ignoring the safety issues. The third baseline is
a L INEAR agent. This algorithm is based on Amani, Thrampoulidis, and Yang (2021) to model the safety function via alinear model. The final baseline is a I NSTANTANEOUS agent.
This algorithm only considers the instantaneous safety constraint (3) as in Wachi, Wei, and Sui (2021) and cannot guarantee the satisfaction of the long-term constraint in an environment with the stochastic state transition.

Table 2: Experimental results. Reward is normalized withrespect to U NSAFE agent.

Results. Table 2 summarizes our experimental results. To
obtain the results, we run each algorithm while generating
100 different random environments. As for safety, LoBiSaRL is the only algorithm to guarantee the satisfaction of thesafety constraint in the long run. R ANDOM, U NSAFE, and
L INEAR execute a lot of unsafe actions. I NSTANTANEOUS
agent is much safer than the above three baselines but sometimes violates the safety constraint due to the stochasticityof the environment. In contrast, LoBiSaRL is often too conservative and the performance in terms of reward is worse
than I NSTANTANEOUS. Given that LoBiSaRL is an algorithm for safety-critical applications, however, it would be
more important to guarantee long-term safety if the performance degradation is minor in terms of reward.

7

Conclusion

We formulate a safe RL problem with stochastic state transition and binary safety feedback and then propose an algorithm called LoBiSaRL. This algorithm maximizes the expected cumulative reward while guaranteeing the satisfaction of the long-term safety constraint. Under the assumptions regarding the Lipschitz continuity of the feature mapping function and the existence of a conservative policy, LoBiSaRL optimizes a policy while ensuring that there is atleast one viable action until the terminal time step. We theoretically guarantee long-term safety and empirically evaluate the performance of LoBiSaRL comparing with several
baselines. Moving forward, it is an interesting direction to
improve performance in terms of reward.

References
Abbasi-yadkori, Y.; Pál, D.; and Szepesvári, C. 2011. Improved Algorithms for Linear Stochastic Bandits. In Neural
Information Processing Systems (NeurIPS).
Achiam, J.; Held, D.; Tamar, A.; and Abbeel, P. 2017. Constrained policy optimization. In International Conference on
Machine Learning (ICML).
Altman, E. 1999. Constrained Markov decision processes,
volume 7. CRC Press.
Amani, S.; Thrampoulidis, C.; and Yang, L. 2021. Safe reinforcement learning with linear function approximation. In
International Conference on Machine Learning (ICML).
Ames, A. D.; Coogan, S.; Egerstedt, M.; Notomista, G.;
Sreenath, K.; and Tabuada, P. 2019. Control barrier functions: Theory and applications. In European control conference (ECC).
Amodei, D.; Olah, C.; Steinhardt, J.; Christiano, P.; Schulman, J.; and Mané, D. 2016. Concrete problems in AI safety.
arXiv preprint arXiv:1606.06565.
Asadi, K.; Misra, D.; and Littman, M. 2018. Lipschitz continuity in model-based reinforcement learning. In International Conference on Machine Learning (ICML).
Auer, P.; and Ortner, R. 2007. Logarithmic online regretbounds for undiscounted reinforcement learning. In Neural
Information Processing Systems (NeurIPS).
Bennett, A.; Misra, D.; and Kallus, N. 2023. Provable Safe
Reinforcement Learning with Binary Feedback. In International Conference on Artificial Intelligence and Statistics(AISTAT).
Buckman, J.; Gelada, C.; and Bellemare, M. G. 2020. The
importance of pessimism in fixed-dataset policy optimization. arXiv preprint arXiv:2009.06799.
Bura, A.; HasanzadeZonuzy, A.; Kalathil, D.; Shakkottai,S.; and Chamberland, J.-F. 2022. DOPE: Doubly optimistic
and pessimistic exploration for safe reinforcement learning.
Neural Information Processing Systems (NeurIPS).
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).
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.
Dulac-Arnold, G.; Levine, N.; Mankowitz, D. J.; Li, J.;
Paduraru, C.; Gowal, S.; and Hester, T. 2021. Challenges ofreal-world reinforcement learning: definitions, benchmarks
and analysis. Machine Learning, 1–50.
Faury, L.; Abeille, M.; Calauzènes, C.; and Fercoq, O. 2020.
Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning (ICML).
Filippi, S.; Cappe, O.; Garivier, A.; and Szepesvári, C. 2010.
Parametric bandits: The generalized linear case. Neural Information Processing Systems (NeurIPS).

Garcıa, J.; and Fernández, F. 2015. A comprehensive survey
on safe reinforcement learning. Journal of Machine Learning Research (JMLR), 16(1): 1437–1480.
Jin, Y.; Yang, Z.; and Wang, Z. 2021. Is pessimism provably efficient for offline rl? In International Conference on
Machine Learning.
Koller, T.; Berkenkamp, F.; Turchetta, M.; and Krause, A.
2018. Learning-based model predictive control for safe
exploration. In IEEE conference on decision and control(CDC).
Li, L.; Lu, Y.; and Zhou, D. 2017. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning (ICML).
Lin, Y.; Hu, Y.; Shi, G.; Sun, H.; Qu, G.; and Wierman, A.
2021. Perturbation-based regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 34: 5174–5185.
Ok, J.; Proutiere, A.; and Tranos, D. 2018. Exploration in
structured reinforcement learning. Neural Information Processing Systems (NeurIPS), 31.
Rockafellar, R. T.; Uryasev, S.; et al. 2000. Optimization of
conditional value-at-risk. Journal of risk, 2: 21–42.
Roderick, M.; Nagarajan, V.; and Kolter, Z. 2021. Provably safe PAC-MDP exploration using analogies. In International Conference on Artificial Intelligence and Statistics(AISTAT).
Stooke, A.; Achiam, J.; and Abbeel, P. 2020. Responsive
safety in reinforcement learning by pid lagrangian methods.
In International Conference on Machine Learning (ICML).
Strehl, A. L.; and Littman, M. L. 2008. An analysis ofmodel-based interval estimation for Markov decision processes. Journal of Computer and System Sciences, 74(8):1309–1331.
Tessler, C.; Mankowitz, D. J.; and Mannor, S. 2018. Reward constrained policy optimization.
arXiv preprint
arXiv:1805.11074.
Tsukamoto, H.; Chung, S.-J.; and Slotine, J.-J. E. 2021.
Contraction theory for nonlinear stability analysis andlearning-based control: A tutorial overview. Annual Reviewsin Control, 52: 135–169.
Turchetta, M.; Berkenkamp, F.; and Krause, A. 2016. Safe
exploration in finite Markov decision processes with Gaussian processes. In Neural Information Processing Systems(NeurIPS).
Wachi, A.; and Sui, Y. 2020. Safe reinforcement learningin constrained Markov decision processes. In International
Conference on Machine Learning (ICML).
Wachi, A.; Wei, Y.; and Sui, Y. 2021. Safe Policy Optimization with Local Generalized Linear Function Approximations. Neural Information Processing Systems (NeurIPS).
Yang, L.; and Wang, M. 2020. Reinforcement Learning in
Feature Space: Matrix Bandit, Kernels, and Regret Bound.
In International Conference on Machine Learning (ICML).

A
A.1

ProofsPreliminary Lemmas

Lemma 6. For any states s, s̄ ∈ S and (deterministic) policies π, π̄, we have∥ϕ(s, π(s)) − ϕ(s̄, π̄(s̄))∥2 ≤ Lϕ · dS (s, s̄) + Lϕ · dA (π(s), π̄(s̄)).

Proof. By Assumption 3, for any states s, s̄ ∈ S and policies π, π̄, we have∥ϕ(s, π(s)) − ϕ(s̄, π̄(s̄))∥2 ≤ Lϕ · dSA ((s, π(s)), (s̄, π̄(s̄))).
By definition of dSA , we havedSA ((s, π(s)), (s̄, π̄(s̄))) = dS (s, s̄) + dA (π(s), π̄(s̄)).
In the above transformation, we used the assumption that policies π, π̄ are deterministic. In summary, the following inequality
holds:∥ϕ(s, π(s)) − ϕ(s̄, π̄(s̄))∥2 ≤ Lϕ · dS (s, s̄) + Lϕ · dA (π(s), π̄(s̄)).

Lemma 7. Suppose, at every time step t, the agent’s policy π satisfies π(st ) − π ♯ (st ) 2 ≤ xt . Then, for any policy π and two
succeeding states st and st+1 ∼ P (· | st , π(st )), we have∥ϕ(st+1 , π(st+1 )) − ϕ(st , π(st ))∥2 ≤ Lϕ · (1 + L♯ ) · dS (st , st+1 ) + Lϕ · (xt + xt+1 ).

(16)

Proof. By Lemma 6, for any policy π and two succeeding states st and st+1 ∼ P (· | st , π(st )), we have∥ϕ(st+1 , π(st+1 )) − ϕ(st , π(st ))∥2 ≤ Lϕ · dS (st , st+1 ) + Lϕ · dA (π(st ), π(st+1 )).
By applying the triangle inequality to the second term, we havedA (π(st ), π(st+1 )) ≤ dA (π(st ), π ♯ (st )) + dA (π ♯ (st ), π ♯ (st+1 )) + dA (π ♯ (st+1 ), π(st+1 ))≤ xt + L♯ · dS (st , st+1 ) + xt+1 .
In the above transformation, we used Assumption 4. In summary, the following desired inequality can be obtained:∥ϕ(st+1 , π(st+1 )) − ϕ(st , π(st ))∥2 ≤ Lϕ · dS (st , st+1 ) + Lϕ · (xt + L♯ · dS (st , st+1 ) + xt+1 )= Lϕ · (1 + L♯ ) · dS (st , st+1 ) + Lϕ · (xt + xt+1 ).

Lemma 8. Set L̄♯ := L♯ + 1. Suppose that, for any time step t ∈ [T ] and state st ∈ S, a policy π takes an action such thatdA (π(st ), π ♯ (st )) ≤ xt . Then, we have∥ϕ(st+1 , π(st+1 )) − ϕ(st , π(st ))∥2
≤ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xt + xt+1 }.
Proof. By Assumption 4, we havedS (st , st+1 ) ≤ d¯ + η · xt .
By applying the above inequality to (16), the following inequality holds:∥ϕ(st+1 , π(st+1 )) − ϕ(st , π(st ))∥2 ≤ Lϕ · {(1 + L♯ ) · d¯ + (1 + η + L♯ η) · xt + xt+1 }= Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xt + xt+1 }.
Then we have the desired lemma.

A.2

Proof of Lemma 2

Lemma 9. Suppose that Assumptions 3 and 4 hold. Also assume that, at every time step t, the agent’s policy π satisfies
π(st ) − π ♯ (st ) 2 ≤ xt . Then, we have
(
)
T
−1
X
∥ϕ(sT , π(sT )) − ϕ(st , π(st ))∥ ≤ Lϕ · L̄♯ · d¯ · (T − t) + (1 + η L̄♯ ) · xt + (2 + η L̄♯ ) ·xτ + xT .
2

τ =t+1

Proof. By triangle inequality, we have∥ϕ(sT , π(sT )) − ϕ(st , π(st ))∥2 ≤T−1X∥ϕ(si+1 , π(si+1 )) − ϕ(si , π(si ))∥2 .

(17)

i=t

By Lemma 8, the following inequalities hold for all i ∈ [t, T − 1]:∥ϕ(si+1 , π(si+1 )) − ϕ(si , π(si ))∥2 = Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xi + xi+1 }(18)

By summing the above inequality up from i = t, t + 1, . . . , T − 1,
∥ϕ(sT , π(sT )) − ϕ(st , π(st ))∥2 ≤ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xt + xt+1 }+ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xt+1 + xt+2 }+ ···+ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xT −1 + xT }
(
)
T
−1
X
xτ + xT .
= Lϕ · L̄♯ · d¯ · (T − t) + (1 + η L̄♯ ) · xt + (2 + η L̄♯ ) ·τ =t+1

Then we obtained the desired lemma.
Proof. (of Lemma 2) By Assumption 1 and Cauchy–Schwarz inequality,|f ⋆ (sT , π(sT )) − f ⋆ (st , π(st ))| ≤ ∥w⋆ ∥2 · ∥ϕ(sT , π(sT )) − ϕ(st , π(st ))∥2√
≤ m · ∥ϕ(sT , π(sT )) − ϕ(st , π(st ))∥2 .
By combining the above inequality and Lemma 9, we have
(
)
T
−1
X
√
xτ + xT .
|f ⋆ (sT , π(sT )) − f ⋆ (st , π(st ))| ≤ m · Lϕ · L̄♯ · d¯ · (T − t) + (1 + η L̄♯ ) · xt + (2 + η L̄♯ ) ·τ =t+1

Recall the definitions of L1 , L2 , and L3 ; that is, L1 :=inequalities holds:(⋆⋆|f (sT , π(sT )) − f (st , π(st ))| ≤ L1 ·√¯ and L3 := 2 + η L̄♯ . Then, the following
m · Lϕ , L2 := L̄♯ · d,

L2 · (T − t) + (L3 − 1) · xt + L3 ·

T
−1
X

)
xτ + xT.

τ =t+1T −1:=
By definitions of t̄ := T − t and Xt+1

PT −1

τ =t+1 xτ , we haveT −1|f ⋆ (sT , π(sT )) − f ⋆ (st , π(st ))| ≤ L1 · L2 · t̄ + (L3 − 1) · xt + L3 · Xt+1
+ xT .

A.3

Proof of Lemma 3

Lemma 10. Suppose that Assumptions 3 and 4 hold. Also assume that, at every time step t, the agent’s policy π satisfies
π(st ) − π ♯ (st ) 2 ≤ xt . Then, we have
(
)
t−1
X
∥ϕ(st , π(st )) − ϕ(s1 , π(s1 ))∥ ≤ Lϕ · L̄♯ · d¯ · t + (1 + η L̄♯ ) · x1 + (2 + η L̄♯ ) ·xτ + xt .
2

τ =2

Proof. Similarly to the proof of Lemma 2, we sum up the inequality (16) for i = 1, 2, . . . , t − 1 and then obtain∥ϕ(st , π(st )) − ϕ(s1 , π(s1 ))∥ ≤ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · x1 + x2 }2

+ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · x2 + x3 }+ ···+ Lϕ · {L̄♯ · d¯ + (1 + η L̄♯ ) · xt−1 + xt }
(
)
t−1
X
= Lϕ · L̄♯ · d¯ · t + (1 + η L̄♯ ) · x1 + (2 + η L̄♯ ) ·xτ + xt .
τ =2Then we obtained the desired lemma.
Lemma 11. Suppose the policy π takes the same action to the conservative policy π ♯ at the initial time step; that is, we set
π(s1 ) = π ♯ (s1 ) and then x1 = 0. We then have
(
)
t−1
X
♯
¯
ϕ(st , πt (st )) − ϕ(s1 , π (s1 )) ≤ Lϕ · L̄♯ · d · t + (2 + η L̄♯ ) ·xτ + xt .
2

τ =2

Proof. (of Lemma 3) By Assumption 1,f ⋆ (st , π(st )) − f ⋆ (s1 , π ♯ (s1 )) ≤ ∥w⋆ ∥2 · ϕ(st , πt (st )) − ϕ(s1 , π ♯ (s1 )) 2√
≤ m · ϕ(st , πt (st )) − ϕ(s1 , π ♯ (s1 )) 2 .
By combining Lemma 11 and the aforementioned inequality, we have
(
⋆

⋆

♯

⋆

f (st , π(st )) − f (s1 , π (s1 )) ≤ ∥w ∥2 · Lϕ ·L̄♯ · d¯ · t + (2 + η L̄♯ ) ·

t−1
X

)
xτ + xt.

τ =2√¯ and L3 := 2 + η L̄♯ , weDefine f ♯ (s) := f ⋆ (s, π ♯ (s)) for all s ∈ S. Based on the definitions of L1 := m · Lϕ , L2 := L̄♯ · d,havef ⋆ (st , π(st )) − f ♯ (s1 ) ≤ L1 L2 t + L3 X2t−1 + xt .

A.4

Proof of Lemma 4

Proof. (of Lemma 4) By Lemma 1, the following inequality holds regarding the lower-bound based on GLM:f ⋆ (st , at ) ≥ ℓGLM (st , at )(19)with a probability of at least 1 − ∆. Also, by Lemma 3, the following inequality holds (with a probability of 1) regarding thelower-bound based on the Lipschitz continuity:f ⋆ (st , at ) ≥ ℓLipschitz (st , at ).

(20)

By definition, ℓ(st , at ) := max(ℓGLM (st , at ), ℓLipschitz (st , at )); then, we havef ⋆ (st , at ) ≥ ℓ(st , at )with a probability of at least 1 − ∆.

A.5

Proofs of Lemma 5 and Corollary 1

Proof. (of Lemma 5) By Lemma 2,T −1
f ⋆ (sT , π(sT )) ≥ f ⋆ (st , π(st )) − L1 L2 t̄ + (L3 − 1)xt + L3 Xt+1
+ xT .
Also, by Lemma 4, at time step t, we havef ⋆ (st , at ) ≥ ℓ(st , at )By combining the above two inequalities, we haveT −1f ⋆ (sT , π(sT )) ≥ ℓ(st , at ) − L1 L2 t̄ + (L3 − 1)xt + L3 Xt+1
+ xT .

(21)

Proof. (of Corollary 1) For a scalar z ∈ R, suppose that the following inequality holds:T −1ℓ(st , at ) − L1 L2 t̄ + (L3 − 1)xt + L3 Xt+1
+ xT ≥ z
Then, by Lemma 5, the following inequality also immediately holds:f ⋆ (sT , π(sT )) ≥ z.
In addition, by definitions, we have L1 ≥ 0, L2 ≥ 0, L3 ≥ 1, and xτ ≥ 0, ∀τ ∈ [T ]. Thus, by Lemma 4, we havef ⋆ (st , π(st )) ≥ ℓ(st , π(st )) ≥ z.
The aforementioned inequalities hold for all τ ∈ [t, T ]; thus, we havef ⋆ (sτ , π(sτ )) ≥ z,

A.6

∀τ ∈ [t, T ].

Proof of Theorem 1

Proof. (of Theorem 1) Let Yt be the event that the following inequality is satisfied:f ⋆ (st , at ) ≥ z.

(22)

Also, Let Zt be the event that the following inequality holds:ℓ(st , at ) − L1 L2 t̄ − xt + L3 XtT −1 + xT
When (23) holds, we havef ⋆ (sτ , aτ ) ≥ z,

≥ z.

(23)

∀τ ∈ [t, T ],under Assumptions 3 and 4 as well as Corollary 1; hence, the above inequality means the satisfaction of
Pr Yt , Yt+1 , . . . , YT | Zt = 1.

By Lemma 4, the lower-bound ℓ is probabilistic; that is, Pr Zt ≥ 1 − ∆; hence,no
Pr Yt , Yt+1 , . . . , YT = 1 − ∆,(24)

which means thatnPr f ⋆ (sτ , aτ ) ≥ z∀τ ∈ [t, T ]o= 1 − ∆.

Finally, the binary safety feedback is stochastic per the GLM; that is, at every time step τ ∈ [t, T ], safety feedback of 1 can beobtained with a probability at least 1 − µ(z). In summary, we havenoPr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ (1 − µ(z))t̄ .