#  Learning to Act Safely with Limited Exposure and Almost Sure Certainty

Agustin Castellano  Hancheng Min  Juan Bazerque  and Enrique Mallada A
preliminary version of this work was previously presented in
[castellano2021learning]. A. Castellano and J. Bazerque are with the
Department of Electrical Engineering at Universidad de la República, Uruguay
(e-mail: {acastellano, jbazerque}@fing.edu.uy). H. Min and E. Mallada are with
the Department of Electrical and Computer Engineering at Johns Hopkins
University, Baltimore, MD 21218 USA (e-mail: {hanchmin,mallada}@jhu.edu).

###### Abstract

This paper aims to put forward the concept that learning to take safe actions
in unknown environments, even with probability one guarantees, can be achieved
without the need for an unbounded number of exploratory trials, provided that
one is willing to navigate trade-offs between optimality, level of exposure to
unsafe events, and the maximum detection time of unsafe actions. We illustrate
this concept in two complementary settings. We first focus on the canonical
multi-armed bandit problem and seek to study the intrinsic trade-offs of
learning safety in the presence of uncertainty. Under mild assumptions on
sufficient exploration, we provide an algorithm that provably detects all
unsafe machines in an (expected) finite number of rounds. The analysis also
unveils a trade-off between the number of rounds needed to secure the
environment and the probability of discarding safe machines. We then consider
the problem of finding optimal policies for a Markov Decision Process (MDP)
with almost sure constraints. We show that the (action) value function
satisfies a barrier-based decomposition which allows for the identification of
feasible policies independently of the reward process. Using this
decomposition, we develop a Barrier-learning algorithm, that identifies such
unsafe state-action pairs in a finite expected number of steps. Our analysis
further highlights a trade-off between the time lag for the underlying MDP
necessary to detect unsafe actions, and the level of exposure to unsafe
events. Simulations corroborate our theoretical findings, further illustrating
the aforementioned trade-offs, and suggesting that safety constraints can
further speed up the learning process.

Uncertain systems, randomized algorithms, Markov processes, iterative learning
control, optimal control

##  1 Introduction

Motivated by the success of machine learning in achieving super human
performance, e.g., in vision [rawat2017deep], speech [hinton2012deep], and
video games [silver2016mastering], there has been recent interest in
developing learning-enabled technology that can implement highly complex
actions for safety-critical autonomous systems, such as self-driving cars,
robots, etc. However, without proper safety guarantees such systems will
rarely be deployed. There is therefore the need to develop analysis tools and
algorithms that can provide such guarantees during, and after, training.
Efforts to provide such guarantees can be broadly grouped in two lines of work
with somehow complementary success.

The first approach leverages model-based techniques, based on Lyapunov
stability [haddad2011nonlinear] and robust control [zhou1998essentials], to
provide (worst-case) safety guarantees based on a nominal model and
assumptions on uncertainty and disturbances [2017.Berkenkamp,
perkins2002lyapunov, 2018.Jinuua, 2018.Chow, 2019.Singh, 2005.Morimoto,
2007.Anderson, 2015.Berkenkamp, 2017.Friedrich, 2018.Busoniu, 2020.Dontisrl].
In such settings, safety is usually specified in terms of stability, robust
stability, or the existence of some invariant or control invariant sets.
Notably, such methods provide highly reliable guarantees, allowing the system
to operate without ever violating safety specifications. However, they require
an a priori fixed specification of the safety notion, e.g., a set or
stability, that is implicitly encoded by the controller/agent. Moreover, due
to the worst case approach to uncertainty, these methods tend to suffer poor
performance in the average case.

The second line of work, in which our work naturally lies in, seeks to provide
safety guarantees in model-free settings by adding constraints to the learning
problem [Garcia, 2006.Geibel, 2015.Junges, 2016.Turchetta, 2018.Dalal,
2018.Wachi, 2020.Xu, 2019.Paternainyfa, dxb, 2019.Ge, 2020.Wachi,
2020.HasanzadeZonuzy]. In this way, safety specifications can be further
extended, beyond typical control notions, at the expense of introducing
uncertainty, and risk, in the safety guarantees. This lack of certainty is
usually mitigated in different ways. For example, one can introduce soft
constraints to primal methods [2006.Geibel, 2020.Xu], or use primal-dual
methods [2019.Paternainyfa, dxb], that lead to asymptotic constraint
satisfaction. Such methods can indeed provide asymptotic a.s. guarantees, but
at the expense of incurring unbounded violations of the constraints during
training [dxb], an undesired feature for most control problems. A different
approach consists on introducing an initial stage in the algorithm, to be
executed before the optimization starts, that aims at learning an
approximation of the safety region [2020.Wachi, 2018.Dalal]. This approach
naturally leads to high probability guarantees on constraint satisfaction
(based on Probably Approximately Correct (PAC) sample complexity bounds).
However, due to the need to limit the running time of the safety assessment
stage, it is impossible to provide probability one guarantees, which can in
turn lead to catastrophic consequences.

The above discussion implicitly illustrates a complementary set of challenges
that one needs to overcome to develop reliable model-free learning algorithms
for safety critical applications.

  * •

_Exposure to Failures._ Due to the desire for limited constraint violations,
one is required to perform the learning task with limited information of the
unsafe region.

  * •

_Outcome Uncertainty._ Along the same line, making decisions with finite
number of samples intrinsically requires one to accept the possibility of
making errors.

  * •

_Assessment with Deferred Consequences._ The real-time nature of these
problems leads to settings where information is revealed sequentially and in a
delayed manner.

The goal of this paper is to develop a novel approach for model-free safety
assessment, considering the complementary benefits of the aforementioned
techniques, with the aim of overcoming these challenges. To achieve this goal,
we argue and demonstrate that, due to the logical (safe/unsafe) nature of
safety assessment, _the problem of finding safe actions is fundamentally
different from that of finding the best action._ As a result, safety
assessment can be achieved more efficiently and independently of the
optimization task. This motivates the need of a separate (logical) signalling
mechanism–akin to the reward in multi-armed bandits (MAB)
[lattimore2020bandit] and reinforcement learning (RL)
[sutton2018reinforcement]–dedicated to inform, either directly or indirectly,
about a violation of the safety specification. We call such signal here a
_damage indicator_ , denoted by $D_{t}\in\\{0,1\\}$.

Using this newly introduced safety signal $D_{t}$ we aim at developing safety
assessment algorithms that lead to actions $A_{t}$ that satisfy a safety
specifications of the from $D_{t}=0$ a.s. or $\prob(D_{t}=1)\leq\mu$
(conditioned on the action) for some nominal safety margin $\mu>0$. Our
approach leads to algorithms that can be implemented _sequentially_ and
_concurrently_ with other optimization algorithms (such as Q-learning
[watkins1989learning] or its variants [speedyq], [zapq]), can achieve
_probability one_ guarantees on the safety specification, and only incur a
_finite number of constraint violations_. Achieving such remarkable outcome
naturally requires to navigate trade-offs across multiple requirements. We
illustrate such trade-off by developing safety assessment methods for two
exemplary cases.

We first consider the problem of safety assessment in MABs, where the safety
specification is given by some $\mu\geq 0$ (Section 2). While the case $\mu=0$
is rather straightforward (Section 2.1), when $\mu>0$ requires to trade-off
between quickly discarding unsafe arms and accurately estimating
$\prob(D_{t}=1|A_{t})$. We thus make the conscious choice of focusing on
prioritizing the rapid (finite time) detection of unsafe actions almost
surely, which naturally requires to (mildly) give up optimality by possibly
discarding some safe arms (Section 2.2). We then move towards the problem of
RL for Constrained Markov Decision Processes (Section 3), wherein we seek to
develop algorithms that can rapidly discard unsafe state-action pairs. In this
setting decisions can have safety consequences that may only be realized after
some time. By focusing on the almost sure safety specification ($\mu=0$), we
develop a decomposition framework (Section 3.1), based on hard barrier
functions, that allows to decouple the safety assessment problem from the
problem of maximizing rewards. This leads to a novel barrier learner
algorithm, that is able to identify all state-action pairs that lead to unsafe
events (Section 3.2). Our analysis further shows the explicit role that the
delayed consequences have in the learning process (Section 3.3). Numerical
illustrations, in Section 4 verify our theoretical analysis and further
suggest that can further aid in the learning process.

##  2 Multi-armed bandits

We consider the setting of a stochastic bandit problem, with $K$ arms indexed
as $a\in\\{1,\ldots,K\\}$. In the standard bandit problem an agent aims to
devise an arm-pulling policy to optimize a reward. Here, we switch focus to
the safety problem, for which we consider that pulling some the arms could be
unsafe and lead to system damage or harm to the agent. Specifically, at each
round $t\geq 1$ the agent pulls an arm $A_{t}$ and obtains a binary-valued
_damage indicator_ $D_{t}$. If $D_{t}$ is zero (one) this means that the
action led to a safe (unsafe) result. We have that
$\mathbb{E}[D_{t}|A_{t}]=\mu_{A_{t}}$. Each machine is therefore characterized
by its _safety parameter_ $\mu_{a}$. The greater this value is, the more
likely it is that pulling the machine will lead to an unsafe event. The goal
of the player in this setup is to identify all the machines that are
$\mu$-unsafe, which is hereby defined.

######  Definition 1.

Given a _safety specification_ $\mu\in[0,1)$, a machine $a$ is said to be
$\mu$-unsafe if and only if $\mu_{a}>\mu$. Accordingly, a machine is
$\mu$-safe whenever $\mu_{a}\leq\mu$.

The safety requirement $\mu$ is a design parameter, and is the only data that
the player has access to along with the signal $D_{t}$. We will look at two
distinct cases:

  1. A)

_Flawless setting_ ($\mu=0$): in this setting we only allow for flawless
machines, and therefore would like to identify every machine whose probability
of damage is non-zero (albeit very small).

  2. B)

_Relaxed setting_ ($\mu>0$): In this setting we want to identify unsafe
machines with $\mu_{a}>\mu$. This means that we allow “somewhat defective”
machines.

We will focus first on the flawless setting, as it will allow us to build
intuition on how to devise a proper Algorithm and on the values of metrics
involved. The solution in this case is straightforward: let the agent pull
each arm and avoid arms that have led to an unsafe event $D_{t}=1$. For the
second case, we will rely on building a one-sided Sequential Probability Ratio
Test (SPRT) [wald1945], that will make us try each machine a sufficient number
of times; if the machine is _unsafe_ , the test will eventually decide on that
hypothesis.

In both cases, our goal is the same. We want to _detect_ all the machines that
are unsafe. To that end, let us define at each round $t\geq 1$ the candidate
safe set $\mathcal{A}_{t}$, which contains all the arms that haven’t been
classified as unsafe.

######  Assumption 1.

Given a safety requirement $\mu$, there are $M$ $\mu$-unsafe machines, where
$1\leq M\leq K$. Without loss of generality we will assume the the first $M$
arms to be $\mu$-unsafe (i.e. $\mu_{a}>\mu,~{}a=1,\ldots,M$)

######  Definition 2.

For each round $t\geq 1$ we define the _candidate safe set_ $\mathcal{A}_{t}$
as the set containing all the arms that have not been classified as unsafe.

Set $\mathcal{A}_{t}$ is initialized as $\mathcal{A}_{0}=\left\\{1,\ldots
K\right\\}$, and sequentially trimmed down whenever an arm is found to be
unsafe. To select which arm to pull at each round, we consider probability
distribution $\psi$, and select actions according to
$A_{t}\sim\psi(\mathcal{A}_{t})$.

Although we recognize that detecting unsafe machines necessarily implies
pulling from those unsafe arms, we want to have a notion of whether our
decision rules choose machines in an efficient manner. It is with that goal in
mind that we define at each round the _exposure_.

######  Definition 3.

For $t\geq 1$ we define the _exposure_ at round $t$ as

$E_{t}=\sum_{\tau=1}^{t}\mathds{1}\left(\mu_{A_{\tau}}>\mu\right).$ (1)

This metric counts the rounds in which $\mu$-unsafe machines have been pulled,
regardless of whether they led to an unsafe event or not. Notice that the
exposure inherits the randomness of the sequence of decisions $A_{t}$. Our
results throughout this section will deal then with the expected value
$\mathbb{E}[E_{t}]$. Ideally a good player would be one that attains low
exposure—meaning it selects unsafe machines infrequently.

######  Remark 1.

We define the notion of _exposure_ in the sense of “the condition of being
unprotected” as its definition states. This marks a stark contrast with the
notion of _regret_ , typically studied in Bandit settings
[lattimore2020bandit], where unbounded regret is unavoidable [1985.Lai].

At time $t$, the number of times an arm $a$ has been pulled is

$N_{a}(t)=\sum_{\tau=1}^{t}\mathds{1}(A_{\tau}=a)\,.$ (2)

The following lemma states that the expected exposure coincides with the sum
of the expected number of pulls over the unsafe machines.

######  Lemma 1.

$\mathbb{E}[{E_{t}}]=\sum_{a=1}^{M}\mathbb{E}[N_{a}(t)]$

###### Proof.

$\displaystyle\mathbb{E}[E_{t}]\\!=\\!\sum_{\tau=1}^{t}\mathbb{E}\left[\mathds{1}\left(\mu_{A_{\tau}}\\!>\\!\mu\right)\right]\\!=\\!\sum_{\tau=1}^{t}\sum_{a=1}^{K}P(A_{\tau}\\!=\\!a)\mathds{1}\left(\mu_{a}\\!>\\!\mu\right)$
$\displaystyle\\!=\\!\sum_{\tau=1}^{t}\sum_{a=1}^{M}P(A_{\tau}\\!=\\!a)\\!=\\!\sum_{a=1}^{M}\sum_{\tau=1}^{t}\mathbb{E}\left[\mathds{1}(A_{\tau}\\!=\\!a)\right]\\!=\\!\sum_{a=1}^{M}\mathbb{E}[N_{a}(t)]$

∎

######  Definition 4.

The _conservation ratio_ $C_{\varepsilon,t}$ is the proportion of safe
machines kept at time $t$

$C_{\varepsilon,t}=\frac{|\mathcal{A}_{t}\cap\mathcal{A_{\varepsilon}^{\star}}|}{|\mathcal{A}_{\varepsilon}^{\star}|}$
(3)

where $\mathcal{A}_{t}$ is the candidate safe set and
$\mathcal{A}_{\varepsilon}^{\star}$ is the set containing all arms that are
$\left(\mu-\varepsilon\right)$-safe:
$\mathcal{A}_{\varepsilon}^{\star}=\\{a\in\mathcal{A}:\mu_{a}\leq\mu-\varepsilon\\},$
where $0\leq\varepsilon\ll 1$ is a non-negative slack parameter.

This ratio gives the proportion of $(\mu-\varepsilon)$-safe machines present
in the candidate safe set at each time step. ($C_{\varepsilon,t}$ close to $1$
is desirable). The need for the conservativeness given by $\varepsilon$ is
that we want to detect unsafe machines in finite time. This will become
clearer when we discuss the _relaxed setting_ , for now it suffices to assume
$\varepsilon=0$.

###  2.1 Flawless setting ($\mu=0$)

We start with the simplest case imaginable, which is that of a rigorous safety
requirement of $\mu=0$. In this setting, any machine that has positive
probability of giving damage $D_{t}=1$ should be deemed unsafe. The strategy
for discarding these machines is pretty straightforward: at each round $t$
select an arm $A_{t}$ following strategy $\psi(\mathcal{A}_{t})$ and, if the
resulting damage is $D_{t}=1$, classify the machine as unsafe by taking it out
of the candidate safe set $\mathcal{A}_{t}$. This decision rule, summarized in
Algorithm 1 has two interesting properties: _i)_ all unsafe machines are
eventually found, and _ii)_ no safe machines are discarded along the way, as
the the following theorem states.

Input: Number of arms $K$, strategy $\psi$

/* Initialize candidate safe set */

$\mathcal{A}_{0}=\left\\{1,\ldots,K\right\\}$

for  _$t=1,2,\ldots,$_ do

Pick arm $A_{t}\sim\psi(\mathcal{A}_{t}$)

Observe damage $D_{t}$

if  _$D_{t}=1$_ then

/* trim unsafe arm */

$\mathcal{A}_{t}\leftarrow\mathcal{A}_{t-1}\setminus\\{A_{t}\\}$

end if

end for

Algorithm 1 Flawless Inspector

######  Theorem 1.

Under Algorithm 1, for every strategy $\psi$, the following (in)equalities
hold with probability 1 for all $t\geq 1$:

$\displaystyle\mathbb{E}[C_{0,t}]$ $\displaystyle=1$ (4)
$\displaystyle\mathbb{E}[E_{t}]$
$\displaystyle\leq\sum_{a=1}^{M}\frac{1}{\mu_{a}}$ (5)

###### Proof.

The proof for the safety ratio $C_{0,t}$ is immediate, since Algorithm 1 can
never discard a safe machine (the event $D_{t}=0$ has zero probability when
pulling from a flawless arm). For the remaining equalities, let $N_{a}$ be the
number of pulls of the $a$-th arm needed to classify it as unsafe, which is
well-defined for $a=1,\ldots,M$. We have that
$N_{a}\sim\mathrm{Geometric}(\mu_{a})$, hence

E[N_a]=∑_n=1^∞(N_a=n)n=∑_n=1^∞μ_a(1-μ_a)^n-1n=1μa Furthermore, for all $t$ we
have $N_{a}(t)\leq N_{a}$. Taking expectation on both sides and using (1)
yields $\mathbb{E}[N_{a}(t)]\leq\frac{1}{\mu_{a}}$. Combining this with the
result of Lemma 1 gives (5). ∎

We now state that under a uniform strategy, Algorithm 1 finds all unsafe
machines in expected finite time.

######  Theorem 2.

Consider the uniform strategy $\psi_{\texttt{unif}}$ which at each round $t$
samples uniformly from the candidate safe set $\mathcal{A}_{t}$. Let $T$ be
the time it takes for Algorithm 1 to detect all the unsafe machines under
$\psi_{\texttt{unif}}$. Then

$\mathbb{E}[T]\leq\frac{K}{\mu_{\mathrm{low}}}\left(\sum_{k=1}^{M}\frac{1}{k}\right)\,,$

where $\mu_{\mathrm{low}}\leq\mu_{a},~{}\forall a=1,\ldots,M$.

###### Proof.

The proof is in the Appendix .1. ∎

######  Remark 2.

The uniform strategy ($\psi_{\texttt{unif}}$) in Theorem 2 is only assumed to
simplify exposition. A finite bound on $\expc[T]$ can still be obtained
whenever $\psi_{\texttt{unif}}$ is replaced by any strategy that samples all
actions from the set $\mathcal{A}_{t}$ with positive probability.

###  2.2 Relaxed setting ($\mu>0$)

We next consider the _relaxed_ setting, in which we allow machines that give
damage $D_{t}$ with (possibly low) probability $\mu$. This means that in order
to identify unsafe machines we can no longer discard them at first sign of
damage, but must rather pull from each arm and observe multiple unsafe events
in order to be confident that the machine in question is defective. To check
whether an arm $a$ is defective or not we build the following hypothesis test
$\mathbb{H}_{a}$

$(\mathbb{H}_{a})~{}\begin{cases}\mathcal{H}_{0}:&\mu_{a}\leq\mu-\varepsilon\\\
\mathcal{H}_{1}:&\mu_{a}>\mu\end{cases}$ (6)

in which the alternative hypothesis is that the machine is $\mu$-unsafe, and
where we introduce the slack parameter $\varepsilon\in(0,\mu]$. In order to
solve (6), we will devise a Sequential Probability Ratio Test (SPRT) which is
based on Abraham Wald’s seminal work [wald1945] with the following properties:

  1. 1.

If the machine is unsafe —meaning $\mathcal{H}_{1}$ is true— the test will
terminate in expected finite pulls $\mathbb{E}[N_{a}]$.

  2. 2.

If the machine is safe, the probability that the test —incorrectly— decides on
$\mathcal{H}_{1}$ is upper bounded by $\alpha$, where $\alpha\in(0,1)$ is the
_failure tolerance_ of the test.

  3. 3.

Lowering failure tolerance $\alpha$ necessarily implies more pulls $N_{a}$ to
detect unsafe machines.

  4. 4.

If $\mu_{a}\in(\mu-\varepsilon,\mu)$ the test is inconclusive.

  5. 5.

The test is one-sided: it only decides on $\mathcal{H}_{1}$. Similar to
Algorithm 1, whenever a machine is classified as unsafe it is not pulled any
longer.

For a fixed arm $a$, let $\mathbf{d}_{a}(t)=\\{D_{\tau}:A_{\tau}=a,\tau\leq
t\\}$ be the (binary) sequence of outcomes of the $a$-th machine up to time
$t$. The sequential probability ratio test relies on computing the log-
likelihood ratio at each time step:

$\Lambda_{a}(t)=\log\frac{f_{\mu-\varepsilon}(\mathbf{d}_{a}(t))}{f_{\mu}(\mathbf{d}_{a}(t))}\,,$
(7)

where $f_{\mu}$ and $f_{\mu-\varepsilon}$ are the likelihood that the sequence
$\mathbf{d}_{a}(t)$ under $\mathcal{H}_{0}$), and $\mathcal{H}_{1}$,
respectively. The test terminates by declaring $\mathcal{H}_{1}$ whenever

$\Lambda_{a}(t)\geq\log(1/\alpha)\;.$ (8)

By means of sufficient statistics, $\Lambda_{a}(T)$ can be written as a
function of both $k$, the total number of outcomes of $D_{t}=1$ and
$N_{a}(T)$, the total number of pulls up to time $T$. Considering a single-
machine, the testing procedure is as follows. For each round $t\geq 1$ pull
the arm and (given $\mu$ and $\varepsilon$) update the log-likelihood in (7).
If (8) holds, then terminate the test, otherwise observe another sample
$D_{t}$ and repeat.

The following two lemmas state the desired behavior of the SPRT. Namely, that
_i)_ if the machine is unsafe, the SPRT will declare $\mathcal{H}_{1}$ with
probability 1, _ii)_ if the machine is safe, the SPRT will (incorrectly)
declare $\mathcal{H}_{1}$ with probability less than or equal to $\alpha$, and
_iii)_ the time of detection for unsafe machines is finite in expectation, and
is well characterized in terms of the design parameters $\mu$, $\varepsilon$
and $\alpha$.

######  Lemma 2.

For a fixed arm $a$ of parameter $\mu_{a}$, consider the sequential
probability ratio test defined by (6)–(8), where $\mu$, $\varepsilon$ and
$\alpha$ are given. Then:

  1. i)

If $\mathcal{H}_{1}$ is true, the test will (correctly) declare
$\mathcal{H}_{1}$ with probability 1.

  2. ii)

If $\mathcal{H}_{0}$ is true, the test will keep going indefinitely with
probability $\geq 1-\alpha$

###### Proof.

The proof is in the Appendix .2. ∎

######  Lemma 3.

For a fixed arm $a$ of parameter $\mu_{a}$, consider the sequential
probability ratio test defined by (6)–(8), where $\mu$, $\varepsilon$ and
$\alpha$ are given. Then, if the alternative $\mathcal{H}_{1}$ is true, the
test is expected to terminate after $T_{a}$ steps, with

$\mathbb{E}[T_{a}]\leq
1+\frac{\log\left(1/\alpha\right)}{\emph{kl}(\mu,\mu-\varepsilon)}\;,$ (9)

where $\emph{kl}(\mu,\mu-\varepsilon)$ is the Kullback-Leibler divergence
between Bernoulli distributions

$\emph{kl}(\mu,\mu-\varepsilon)=\mu\log\frac{\mu}{\mu-\varepsilon}+\left(1-\mu\right)\log\frac{1-\mu}{1-\mu+\varepsilon}\,.$
(10)

###### Proof.

The proof is in the Appendix .2. ∎

######  Remark 3.

The preceeding lemma elucidates the need of the slack parameter $\varepsilon$:
separating the two limiting distributions enables termination of the test
under $\mathcal{H}_{1}$ in finite time. It also unveils two fundamental trade-
offs. Firstly, if the distance between the limiting distributions increases
(by enlarging $\varepsilon$), then the test detects unsafe machines faster.
However, it becomes inconclusive over a larger proportion of the machines,
since nothing can be assured in the region $\mu_{a}\in(\mu-\varepsilon,\mu)$.
Secondly, $\alpha$ can be increased in order to detect unsafe machines faster,
though this comes at the cost of declaring $\mathcal{H}_{1}$ for a larger
proportion of the safe machines.

We build Algorithm 2 based on this SPRT, and state its main properties in the
following theorem.

Input: Number of arms $K$, strategy $\psi$

requirement $\mu$, slack $\varepsilon$, tolerance $\alpha$

/* Init. safe set and ratios */

$\mathcal{A}_{0}=\left\\{1,\ldots,K\right\\}$, $\Lambda_{a}=0~{}~{}\forall
a=1,\ldots,K$

for  _$t=1,2\ldots$_ do

Pick arm $A_{t}\sim\psi(\mathcal{A}_{t})$

Observe damage $D_{t}$

/* Update log-likelihood ratio */

$\Lambda_{A_{t}}\leftarrow\Lambda_{A_{t}}+\log\frac{f_{\mu}(D_{t})}{f_{\mu-\varepsilon}(D_{t})}$

if  _$\Lambda_{A_{t}}\geq\log(1/\alpha)$_ then

/* SPRT terminates, trim unsafe arm */

$\mathcal{A}_{t}\leftarrow\mathcal{A}_{t-1}\setminus\\{A_{t}\\}$

end if

end for

Algorithm 2 Relaxed Inspector

######  Theorem 3.

Under Algorithm 2, for every strategy $\psi$, the following inequalities hold
with probability 1 for all $t$:

$\displaystyle\mathbb{E}[C_{\varepsilon,t}]$ $\displaystyle\geq 1-\alpha$ (11)
$\displaystyle\mathbb{E}[E_{t}]$ $\displaystyle\leq
M\left(1+\frac{\log\left(1/\alpha\right)}{\emph{kl}(\mu,\mu-\varepsilon)}\right)$
(12)

where $\emph{kl}(\mu,\mu-\varepsilon)$ is the Kullback-Leibler divergence
between Bernoulli distributions (10).

###### Proof.

The proof follows from Lemma 2 and Lemma 3. ∎

In the same spirit as for the flawless setting, we now state that under a
uniform strategy Algorithm 2 finds all unsafe machines in expected finite
time.

######  Theorem 4.

Consider the uniform strategy $\psi_{\texttt{unif}}$ which at each round $t$
samples uniformly from the candidate safe set $\mathcal{A}_{t}$. Let $T$ be
the time it takes for Algorithm 2 to detect all the unsafe machines under
$\psi_{\texttt{unif}}$. Then

$\mathbb{E}[T]\leq{M}(K-M+1)\left(1+\frac{\log(1/\alpha)}{\emph{kl}(\mu,\mu-\varepsilon)}\right)\,.$

###### Proof.

The proof can be found in the Appendix .3. ∎

We end this section by _uniting_ the flawless and relaxed settings, arguing
that Algorithm 1 can be seen as a particular case of the SPRT used in
Algorithm 2.

######  Proposition 1.

Given fixed $\mu\in(0,1)$ and $\varepsilon=\beta\mu$. When $\beta\rightarrow
1^{-}$, Algorithm 2 with any $\alpha>0$ reduces to Algorithm 1.

###### Proof.

The flawless setting only allows for perfectly safe machines, discarding any
arm at first sign of damage $D_{t}=1$. We will show that this coincides with a
Sequential Probability Ratio Test that compares $\mathcal{H}_{0}:\mu_{a}\leq
0$ vs. $\mathcal{H}_{1}:~{}\mu_{a}>\mu$. This will hold for any $\mu\in(0,1)$
and for all $\alpha>0$.

For a fixed $\mu$, consider the test defined in (6) with
$\varepsilon=\beta\mu$. As $\beta\rightarrow 1^{-}$, the null hypothesis
$\mathcal{H}_{0}$ becomes $\mu_{a}=0$. We show that the log-likelihood ratio
$\Lambda_{a}(t)$ goes to infinity at first sign of damage, thus declaring
$\mathcal{H}_{1}$ and terminating the SPRT. A sufficient statistic for
computing the log-likelihood ratio $\Lambda_{a}(t)$ is counting the $k$
outcomes of $D_{\tau}=1$ in a total of $t$ pulls. Then
$\Lambda_{a}(t)=k\log\frac{\mu}{\mu-\varepsilon}+(t-k)\log\frac{1-\mu}{1-\mu+\varepsilon}$.
Writing $\varepsilon=\beta\mu$,
$\Lambda_{a}(T)=t\log\frac{1-\mu}{1-\mu(1-\beta)}+k\log\frac{1-(1-\beta)\mu}{(1-\beta)(1-\mu)}\underset{\beta\to
1^{-}}{\longrightarrow}\infty~{}\forall k>0$. Then the SPRT decides on the
alternative $\mathcal{H}_{1}$ at first sign of damage, no matter how small
$\alpha$ is. ∎

##  3 Assured Reinforcement Learning

This section builds on the insights given by the MABs to detect and discard
unsafe policies in the context of RL. In this new context, unsafe policies are
those which lead to a probable constraint violation, either immediately or
further along the trajectory. We focus on the _Flawless setting ( $\mu=0$)_,
identifying all unsafe actions with a nonzero probability of damage. We start
this section by defining the RL setup, including the underlying Markov
Decision Process and the constrained value maximization problem to solve.
Then, we proceed to write an equivalent unconstrained problem by adding a
hard-barrier index to the cost, which acts as a constraint enforcer. This
equivalent formulation allows us to derive a separation principle together
with our novel barrier function, which provides a certificate of safety for
the behavior policy. The barrier function stands alone, satisfying a Bellman
Equation that describes the set of feasible safe policies. Naturally, this
Bellman Equation yields a stochastic _Barrier learner_ algorithm, that uses
the damage signal observed from the system to detect and reveal unsafe
policies. We finish this section showing that all unsafe policies can be
detected in expected finite time, and present an Assured Q-learning Algorithm
that makes use of the Barrier-learner.

###  3.1 Value function decomposition

With the goal of defining our constrained RL problem, consider a Markov
Decision Process $\mathcal{M}$ with finite state space $\mathcal{S}$, finite
action space $\mathcal{A}$, a reward set $\mathcal{R}$, and a damage indicator
belonging to {0,1}. A transition kernel $p$, specifies the conditional
transition probability $p(s^{\prime},r,d\mid
s,a):=P(S_{t+1}=s^{\prime},R_{t+1}=r,D_{t+1}=d\mid S_{t}=s,A_{t}=a)$, from
state $s\in\mathcal{S}$ to state $s^{\prime}\in\mathcal{S}$ resulting in a
reward $r\in\mathcal{R}$ and a damage indicator $d$, all under action
$a\in\mathcal{A}$. Constraints must be satisfied so that the agent does not
receive damage along the trajectory, which amounts to imposing

$\displaystyle\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}D_{t+1}~{}\big{|}~{}S_{0}=s\right]\leq
0.$ (13)

In this context, our goal is to maximize the value function for each possible
starting state while ensuring the constraint satisfaction in the long run,
i.e.,

$\displaystyle V^{*}(s):=\max_{\pi}\mathbb{E}_{\pi}$
$\displaystyle\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t+1}~{}\big{|}~{}S_{0}=s\right]$
(14) s.t.:
$\displaystyle\quad\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}D_{t+1}~{}\big{|}~{}S_{0}=s\right]\leq
0.$ (15)

where both expectations are taken over the trajectories induced by $\pi$.
While this is a case of a cumulative constraint in expectation which could be
put in Lagrangian form (see e.g., [2019.Paternainyfa][2020.Ding]), we take an
alternative approach that will lead to finite time detection. Notice that
because $D_{t}$ is, by definition, non-negative, we can decouple this
constraint and force each damage indicator to be null, that is,

$\displaystyle\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}D_{t+1}~{}\big{|}~{}S_{0}=s\right]\leq
0\ \iff\ D_{t+1}=0\ a.s.\ \forall t.$ (16)

Notice that the factor $\gamma^{t}$ in the constraint of (15) is
unsubstantial. On the other hand, its presence in the cost is retained to
ensure that the sum of rewards remains bounded. However, $\gamma$ could be
also set to one in the cost of (15) if the number of times the system outputs
a non-zero reward is finite, as it would be the case of an MDP with an almost-
sure absorbent state with zero damage.

Given (16), we proceed to rewrite (14)–(15) as an equivalent problem with one
constraint per time period,

$\displaystyle V^{*}(s):=\max_{\pi}\mathbb{E}_{\pi}$
$\displaystyle\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t+1}~{}\big{|}~{}S_{0}=s\right]$
(17) s.t.: $\displaystyle\quad D_{t+1}=0\quad\textit{a.s.}~{}~{}\forall t$
(18)

We chose to work with (17)–(18) as our most general constrained RL problem to
solve, although we could specialized it further by shaping the transition
kernel $p(s^{\prime},r,d\mid s,a)$. For instance, we could define a feasible
set $\mathcal{F}\subset\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ so that
by setting
$P(D_{t+1}=0~{}\big{|}~{}(S_{t},A_{t},S_{t+1})\in\mathcal{F})=P(D_{t+1}=1~{}\big{|}~{}(S_{t},A_{t},S_{t+1})\notin\mathcal{F})=1$
we would model the damage indicator as being activated whenever the transition
triplet $(S_{t},A_{t},S_{t+1})$ transgresses $\mathcal{F}$. This particular
case could be further specialized to the case where the damage indicator is
turned on whenever $S_{t+1}$ breaks off from a feasible set
$\mathcal{F}_{S}\subset\mathcal{S}$, for instance if a navigation agent
crashes to a wall, or if the action $A_{t}$ violates a feasible set
$\mathcal{F}_{A}\subset\mathcal{A}$; e.g., when exceeding a maximum force.

Returning to our general formulation in (18), let us define the value function
$V^{\pi}$ for a specific policy $\pi$, in which the constraints are embedded
inside the expectation.

$\displaystyle V^{\pi}(s)$
$\displaystyle:=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\big{(}\gamma^{t}R_{t+1}+\mathbb{I}\left[D_{t+1}\right]\big{)}~{}\big{|}~{}S_{0}=s\right]$
(19)

where the hard barrier index function $\mathbb{I}\left[\cdot\right]$ takes the
form

$\mathbb{I}\left[D_{t+1}\right]=\log\left(1-D_{t+1}\right)=\begin{cases}0&\text{if
}D_{t+1}=0\\\ -\infty&\text{if }D_{t+1}=1\end{cases}$ (20)

so that it is null when the transition is safe and takes the value $-\infty$
in the event of an unsafe transition. Being (20) unbounded, expectations are
defined in the sense of the Lebesgue integral for functions in the extended
real line [1999.Folland].

The proposed value function definition (19) will prove useful in two senses:
firstly, we will show that maximizing (19) is the same as (17)–(18). Secondly,
the additional term in (19) will allow for a barrier-based decomposition of
the value function, which will aid in the learning of constraints.

######  Lemma 4 (Equivalence).

Problem (14) is equivalent to the maximization of (19), that is

$\displaystyle\max_{\pi}\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\big{(}\gamma^{t}R_{t+1}+\mathbb{I}\left[D_{t+1}\right]\big{)}~{}\big{|}~{}S_{0}=s\right]$
(21)

###### Proof.

If a policy $\pi_{0}$ is unfeasible for Problem (17)–(18), then $\exists
t:P\left(D_{t+1}=1\right)>0$. This non-zero probability renders the expected
value in (21) to $-\infty$ for $\pi_{0}$. Conversely, if a policy $\pi_{1}$ is
feasible for (21) then it must necessarily hold that $D_{t+1}=0$ almost surely
$\forall t$, and hence $\pi_{1}$ is feasible for (17)–(18) as well. Therefore
the feasible sets of both problems coincide. Lastly, for every feasible policy
it must hold $\log\left(1-D_{t+1}\right)=0~{}\forall t$, in which case the
function being maximized is the same. Then the optimal sets of the two
problems coincide. ∎

While solving (17)–(18) is of our utmost interest, we have just shown that, to
this end, we can solve (21) instead. In what follows we will take this one
step further, and show that (19) admits a barrier-based decomposition and can
be cast as the sum of two value functions: one that checks only whether the
policy in consideration is feasible (which will be the main focus of this
work) and one that optimizes the return, provided the policy is feasible. The
main idea behind this decoupling being that the search for feasible policies
will be, in practice, an easier task to undergo.
To this end we define an auxiliary hard-barrier value function $H^{\pi}$ that
will relate to $V^{\pi}$.

$\displaystyle H^{\pi}(s)$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\log\left(1-D_{t+1}\right)~{}\big{|}~{}S_{0}=s\right]$
(22)

We proceed similarly for the action-value function $Q^{\pi}$ and its barrier
counterpart $B^{\pi}$

$\displaystyle
Q^{\pi}(s,a)\\!=\\!\mathbb{E}_{\pi}\\!\left[\sum_{t=0}^{\infty}\big{(}\gamma^{t}R_{t+1}+\mathbb{I}\left[D_{t+1}\right]\big{)}\big{|}S_{0}=s,A_{0}=a\right]$
$\displaystyle
B^{\pi}(s,a)\\!=\\!\mathbb{E}_{\pi}\\!\left[\sum_{t=0}^{\infty}\log\left(1-D_{t+1}\right)\big{|}S_{0}=s,A_{0}=a\right]$
(23)

Searching for policies that are optimal for (21) for each possible state is
our original goal. By contrast, a problem such as maximizing (22) is one that
seeks to find safe policies, in the sense that they are feasible for (21). The
main idea underpinning our work is that we can jointly work on optimizing
(22), which reduces the search over the policy space, while at the same time
maximizing the return present in (21). In the following Theorem we establish a
fundamental decomposition relationship between the value functions and their
auxiliary counterparts.

######  Theorem 5 (Barrier-based decomposition).

Assume rewards $R_{t+1}$ are bounded almost surely for all $t$. Then, for
every policy $\pi$

$V^{\pi}(s)=V^{\pi}(s)+H^{\pi}(s)$ (24)
$Q^{\pi}(s,a)=Q^{\pi}(s,a)+B^{\pi}(s,a)$ (25)

###### Proof.

We shall prove (24) only, since the proof for (25) is alike. The following
identities hold, as explained below.

$\displaystyle
V^{\pi}(s)=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\big{(}\gamma^{t}R_{t+1}+\log\left(1-D_{t+1}\right)\big{)}~{}\big{|}~{}S_{0}=s\right]$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\big{(}\gamma^{t}R_{t+1}+\log\left(1-D_{t+1}\right)\big{)}~{}\big{|}~{}S_{0}=s\right]$
(26)
$\displaystyle+\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\log\left(1-D_{t+1}\right)\mid
S_{0}=s\right]$ (27)

To show that $V^{\pi}(s)$ can be separated in (26) and (27), first suppose
policy $\pi$ is feasible (for Problem (21)). This necessarily implies that
$D_{t+1}=0~{}~{}\textit{a.s.}~{}~{}\forall t$, which makes the second term in
(26) vanish. Conversely, suppose that the policy in consideration is
infeasible. This together with the fact that rewards are bounded almost surely
yields $V^{\pi}(s)=-\infty$, which is the same value attained by both (26) and
(27). ∎

The preceding result implies non-trivial consequences. If the learning agent
can interact with the environment and have access to rewards $R_{t+1}$ and
queries of whether a transition has been safe (i.e. $D_{t+1}=0$), then it can
separately learn both $Q^{\pi}(s,a)$ and $B^{\pi}(s,a)$. This is discussed in
the next remark.

######  Remark 4 (Properties of the optimal barrier function $B^{*}$).

$\displaystyle B^{*}(s,a)=\max_{\pi}B^{\pi}(s,a)$
$\displaystyle=\max_{\pi}\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\log\left(1-D_{t+1}\right)~{}\big{|}~{}S_{0}=s,A_{0}=a\right]$
(28)

By definition, the entries of $B^{\pi}(s,a)$ will either be $0$ or $-\infty$
for any policy $\pi$. Having $B^{*}(s,a)=-\infty$ means that if starting at
$s$ with action $a$ and then following any policy, there is an (albeit small)
non-zero probability that an unsafe event will be encountered. Conversely, if
$B^{*}(s,a)=0$ then following the optimal policy guarantees we will always
ensure constraints while starting from state $s$ and action $a$. Furthermore,
if $B^{*}$ is available, then any policy that chooses an action such that
$B^{*}(s,a)=0$ is a feasible policy for that state. If, on the other hand, the
policy chooses an action which leads to $B^{*}(s,a)=-\infty$, then that policy
can be deemed unsafe immediately, and can be discarded. Notice, however, that
this is a particular property of the optimal function $B^{*}$: for a sub-
optimal $\pi$, $B^{\pi}$ can be padded with lots of $-\infty$ in places where
$B^{*}$ has zeros. Intuitively, this would mean that the sub-optimal policy
starting from $(s,a)$ makes unsafe transitions along its trajectory. In this
sense, having access to the optimal action-value function $B^{*}$ helps
constraint the search of any other known algorithms (such as Q-Learning) to
only feasible policies. This becomes a joint work of optimizing the return
(using one of many possible techniques), while learning the feasible set of
actions at the same time.

###  3.2 Barrier learning

Given the previous discussion on the properties of the Barrier function
$B(s,a)$, we will focus on the feasibility problem aiming to learn the optimal
$B^{\star}(s,a)$ from data. Before that, we state the following optimality
condition, in the standard form of the Bellman’s equations.

######  Theorem 6 (Bellman equation for $B^{\star}(s,a)$).

The optimal barrier function satisfies

$\displaystyle B^{\star}(s,a)=\mathbb{E}\bigg{[}$
$\displaystyle\mathbb{I}\left[D_{t+1}\right]+\max_{a^{\prime}\in\mathcal{A}}B^{\star}(s^{\prime},a^{\prime})~{}\big{|}~{}S_{t}=s,A_{t}=a\bigg{]}.$
(29)

###### Proof.

It follows from Proposition 4.1.1 in [2012.Bertsekas, pp. 217] with the value
function being _minimized_ , and assuming possibly unbounded but non-negative
costs $C(S_{t},A_{t})=-\mathbb{I}[D_{t+1}]$. ∎

Besides providing a certificate for optimality, the Bellman Equations for
$B^{\star}(s,a)$ hint towards a stochastic iterative algorithm to optimize
(28) from data, the same way the Q-learning algorithm is derived from the
standard unconstrained value function [2012.Bertsekas]. We will elaborate on
this stochastic algorithm next. As introduced in (28), our goal is to learn a
_safe_ policy $\pi$ with an associated optimal Barrier function
$B^{\star}(s,a)$ that encodes the trajectories that satisfy the constraints at
all time steps almost surely. For this purpose we first devise an iterative
algorithm that attempts to reach a fixed point satisfying (29), that would be

$\displaystyle B_{k+1}(s,a)$
$\displaystyle=\mathbb{E}\left[\mathbb{I}\left[D_{t+1}\right]+\max_{a^{\prime}\in\mathcal{A}}B_{k}(s^{\prime},a^{\prime})~{}\big{|}~{}S_{t}=s,A_{t}=a\right].$
(30)

Next, we appeal to the stochastic approximation machinery [robbins_monro] to
drop the unknown expectations yielding a data driven version of (30). The
resulting stochastic update is given next.

Input: $B$-function and $(s_{t},a_{t},s_{t+1},d_{t+1})$ tuple

Output: Barrier-function $B$

$B(s_{t},a_{t})\leftarrow
B(s_{t},a_{t})+\log(1-d_{t+1})+\max_{a^{\prime}}B(s_{t+1},a^{\prime})$ return
_$B$_

Algorithm 3 barrier_update

The update in Algorithm 3 incorporates the information carried in $d_{t+1}$,
which signals whether the constraint has been violated or not during the
transition from time $t$ to $t+1$. Moreover, the update does not only consider
immediate violations, but also the future effect of the action $a_{t}$ that is
summarized in the second term $\max_{a^{\prime}}B(s_{t+1},a^{\prime})$. This
_bootstrapping_ mechanism leverages on stationarity to collect damage
information from all previous state transitions, and summarize it in
$B(s_{t+1},a^{\prime})$ which predicts long-run future effect of the state-
action pairs at time $t+1$. Thus, by repeating the update in Algorithm 3 with
new data coming from successive system interactions, an agent can synthesize
the whole information about all past constraint violations in the barrier
function $B(s,a)$ for unveiling the set of unsafe policies.

We leave the details of this iterative algorithm and its performance
guarantees for the next subsection. Now that we have introduced this data-
driven strategy for securing the environment, let us turn back our attention
to the implications of our decomposition result in Theorem 5. The identity
(25) can be used to embed the safety information provided by $B(s,a)$ in the
Q-function $Q(s,a)$. Hence, we identify that the condition $Q(s,a)=-\infty$ is
equivalent to $B(s,a)=-\infty$ and this propagates information about safety
from successor states. For those which do satisfy the constraints we have
$B(s,a)=0$, and then $Q(s,a)$ will carry the information of the observed
rewards. The following update is complementary to Algorithm
LABEL:alg:barrier_learner, and amounts to the standard Q-learning algorithm
for maximizing rewards at safe pairs of states and actions.

Data: Step size $\eta$, discount factor $\gamma$

Input: Functions $Q$, $B$, and $(s_{t},a_{t},s_{t+1},r_{t+1})$

Output: Q-function

$\displaystyle Q(s_{t},a_{t})$
$\displaystyle\\!\leftarrow\\!(1\\!-\\!\eta)Q(s_{t},a_{t})\\!+\\!\eta\\!\left(r_{t+1}\\!+\\!\gamma\max_{a^{\prime}}Q(s_{t+1},a^{\prime})\\!\right)$
$\displaystyle Q(s_{t},a_{t})$
$\displaystyle\\!\leftarrow\\!B(s_{t},a_{t})+Q(s_{t},a_{t})$ return _$Q$_

Algorithm 4 q_update

Next we specify how to use Algorithm 3 to ensure safety, and demonstrate the
sample complexity of the learning process. After that, we combine algorithms 3
and 4 with the goal of safely maximizing rewards. We will borrow the well-
known convergence results of Q-learning [1994.Tsitsiklis] together with our
separation principle in Theorem 5 to provide performance guarantees for our
novel Assured Q-learning algorithm.

###  3.3 Performance analysis of Barrier-Learner

##  4 Numerical Experiments

We now proceed to some numerical experiments that back up the results
presented throughout the paper. We first focus on the multi-armed bandit setup
and on the problem of detecting unsafe machines under a uniform strategy, then
we demonstrate the barrier learner and the characterization of a globally
unsafe MDP and how this can be achieved in finite time, and finally we compare
our Assured Q-learning algorithm against classic Q-learning on a grid-world.

###  4.1 Multi-armed bandits

We illustrate the performance of the Relaxed Inspector (Algorithm 2) on a
setup of $K=1000$ arms, with a safety requirement of $\mu=\frac{1}{10}$. Each
arm’s true safety parameter is uniformly sampled between $0$ and
$\frac{1}{5}$. This means that if $\epsilon\approx 0$, around half of the
machines are safe and the other half unsafe. We run the Relaxed Inspector on
this setting under a uniform strategy, for varying levels of both the failure
tolerance $\alpha$ and the slack $\epsilon$. After all unsafe machines have
been detected —which happens and is certified to be done in finite time in
virtue of Theorem 3— we consider $C_{\varepsilon,\infty}$, the final
conservation ratio and the normalized final exposure $\frac{1}{K}E_{\infty}$ .
Figures 1 and 2 show both this metrics for varying $\alpha$ and $\epsilon$.
The curves in these figures show the average value obtained after $16$
independent runs. Shaded intervals correspond to $\pm\sigma/\sqrt{16}$, with
$\sigma$ being the sample deviation.

These figures certify the intrinsic trade-off in our methodology: if a large
value of $\alpha$ is used, one can obtain low exposure $E_{t}$ (less pulls of
unsafe machines), but at the cost of discarding more safe machines (smaller
conservation ratio $C_{\varepsilon,t}$). For further examples we refer the
reader to [castellano2021learning].

Figure 1: Final safety ratio $C_{\varepsilon,\infty}$ for $\mu=0.1$ as a
function of $\epsilon$, for varying $\alpha$. More safe machines are kept when
using small values of $\epsilon$ and $\alpha$, but this in turn implies longer
training time (c.f. Figure 2) Figure 2: Normalized final exposure for
$\mu=0.1$ as a function of $\epsilon$, for varying tolerance level $\alpha$.
Larger values of $\alpha$ and $\epsilon$ achieve lower handicap (which implies
faster detection).

###  4.2 Barrier learner

We now turn to identification of unsafe states on MDPs via the barrier learner
algorithm. We will try our methodology in the _unstable grid-world_ shown on
the upper-left panel of Fig. 3. At each time step, the agent starts in one of
the white states and takes an action which is up, down, left or right. Moving
between white states is allowed. Bumping into walls —black states— is ok as
well, and leaves the agent at the same place he was in. Purple states are
_holes_ , and moving into a hole is _unsafe_ ($D_{t}=1$) Whenever an action is
taken, there is a probability $p=0.6$ that the agent moves to the
corresponding neighboring state. However, with probability $1-p=0.4$ he moves
to a random neighboring state instead. Given this _unstable_ nature of the
state transitioning, it is clear that states adjacent to the holes
$s_{\texttt{adj}}$ are unsafe. Indeed, the probability to be damaged at
$s_{\texttt{adj}}$ is at least $\frac{1-p}{4}=0.1$. Notice though that the
whole state-action space is unsafe, since with every action there is a
probability of transitioning to a random neighboring state. The question then
is how long it takes the barrier learner to characterize the whole state space
as unsafe.

The top section of Fig. 3 shows the evolution of the barrier learner algorithm
on this grid. At each step the starting state $s_{0}$ is taken uniformly, and
then a random action is sampled. When the agent is assured that
$B(s_{0},a)=-\infty~{}\forall a$ it marks that state as unsafe, and paints it
red in Fig. 3. At first, only the states close to the holes are classified as
unsafe. Soon enough, detection of unsafe states stems from the holes to the
edges of the grid. Near the $t=10000$ mark all states are correctly detected,
as is shown in the bottom plot of Fig. 3. There we show the proportion of
unsafe states detected by the barrier learner, along with the bound obtained
in Theorem LABEL:thm:sample_comp_barrier_learner, where we use
$\sum_{k=1}^{|\mathcal{S}||\mathcal{A}|}\frac{1}{k}\sim\log\left({|\mathcal{S}||\mathcal{A}|}\right)$
. In this case the non-zero transition probabilities of the MDP are lower-
bounded by $\mu=\frac{1-p}{4}=0.1$. The bound is admittedly loose as we
discussed in Section 2, but demonstrates our main claim in
LABEL:thm:sample_comp_barrier_learner about being able to detect unsafe
actions in finite time.

Figure 3: On the top: evolution of the Barrier Learner Algorithm on a 15 by 15
unstable grid. As time advances, detection of unsafe states (in red)
backpropagates from the immediately unsafe holes (purple), eventually
classifying the whole state space as unsafe. On the bottom: proportion of
states classified as unsafe as a function of time. All states are correctly
identified in finite time, respecting the bound of Theorem
LABEL:thm:sample_comp_barrier_learner.

###  4.3 Towards learning safely

Figure 4: Example grid-world: narrow corridor of length 15. An agent starts
each episode at the green state and must learn to reach the red state. Actions
are up-down-left-right, and they move the agent to the adjacent state
deterministically, if possible. Bumping into a purple wall is _unsafe_ , and
leads to episode termination. Transitioning to the red state has reward +100.
All other rewards are zero. Figure 5: Comparison between Assured Q-learning
(blue) and classic Q-learning (green) on the time taken to reach the goal
($s_{15}$) on the narrow corridor of Fig. 4. To build the histogram we train
$1000$ agents independently with each algorithm. Figure 6: Comparison between
Assured Q-learning (blue) and classic Q-learning (green) on the number of
bumps into walls (i.e. episodes) until first reaching the goal ($s_{15}$) on
the narrow corridor of Fig. 4. To build the histograms we train $1000$ agents
independently with each algorithm. Mind the difference on the x-axis between
graphs.

In this part we compare the performance of Classic Q-learning against a
modified version which makes use of the barrier learner, which we dub Episodic
Assured Q-learning. This algorithm works in the same fashion as Algorithm
LABEL:alg:assured_qlearning_onebyone, but it runs episodes following a
behavioral policy instead of drawing state-action pairs generatively.

Let us first describe the environment. Consider an agent that is bound to
navigate a narrow corridor, as shown in Fig. 4. Each episode starts on the
leftmost state and the goal is to reach the rightmost state. The agent can
move deterministically between adjacent states by taking actions up-down-left-
right. However, bumping into a wall is considered unsafe ($D_{t}=1$) and
terminates the episode. For a fair comparison, for the classic Q-learning
setup we let the reward be $-\infty$ whenever the agent bumps into a wall. In
both settings the agents follow a behavioral policy that is $\epsilon$-greedy
with respect to the policy derived by their learnt Q-function, that is to say,
selects $a=\operatorname*{argmax}_{a^{\prime}}Q(s,a^{\prime})$ with
probability $1-\epsilon$ or takes a uniformly random action with probability
$\epsilon$. We fix $\epsilon=0.1$ and the learning-rate $\alpha=0.1$.

As a metric of performance, we count the number of steps it takes for the
agent to reach the goal for the first time, which is shown in Fig. 5. Reaching
the goal is not as straightforward as it seems, since whenever the agent bumps
into a wall he gets sent to the leftmost state. A histogram depicting the
number of wall bumps before reaching the goal for the first time is show in
Fig. 6. Notice that this is exactly the same as counting the number of
episodes taken to reach the goal.

As is evident of both figures, the assured agents generally outperform their
classic counterparts. In particular, training time for the assured agents is
faster —see e.g. Fig. 5, where the total number of transitions for these
agents has both smaller sample mean and sample variance. The reason for this
performance improvement is the fact that the assured agents quickly _learn_
that there are actions that must not be taken again, while standard
$\epsilon$-greedy Q-learning keeps drawing poor actions indefinitely.

##  5 Conclusions

In this work we address the problem of learning to act safely in unknown
environments. We make the case that learning safe policies is fundamentally
different from learning optimal policies, and is a task that can be done
separately and in a more efficient manner. By incorporating in the model a
binary _damage signal_ that indicates constraint violations, our results show
that we can identify all unsafe actions (MABs) and state-action pairs (MDPs)
in expected finite time with probability one guarantees. These results imply
that the learner is not indefinitely exposed to damage, and could aid in the
design of new algorithms that rapidly learn to act safely while jointly
optimizing returns.

###  .1 Proof of Theorem 2

We prove Theorem 2 by induction.

###### Proof.

Each iteration of Algorithm 1 can be view as doing a Bernoulli trial with
success rate being the probability of detecting an unsafe machine.

When $M=1$, the algorithm repeats the same Bernoulli trial until a success,
the success rate for that Bernoulli trial is

$\displaystyle\;\prob\lp\text{``detecting an unsafe machine"}\rp$
$\displaystyle=$ $\displaystyle\;\prob\lp\text{``the unsafe machine is
selected and detected"}\rp=\frac{\mu_{1}}{K}\,,$

Then $T$ is a geometric random variable with parameter $\frac{\mu_{1}}{K}$,
hence $\expc T=\frac{K}{\mu_{1}}\leq\frac{K}{\mu_{\mathrm{low}}}$.

Now suppose Theorem 2 holds for $M=m$, consider detecting $m+1$ unsafe
machines among in total $K$ machines, the algorithm repeat the same Bernoulli
trial until one success, the success rate for that Bernoulli trial is

$\displaystyle\;\prob\lp\text{``detecting an unsafe machine"}\rp$
$\displaystyle=$ $\displaystyle\;\sum_{k=1}^{m+1}\prob\lp\text{``unsafe
machine $k$ is selected and detected"}\rp$ $\displaystyle=$
$\displaystyle\;\sum_{k=1}^{m+1}\frac{1}{K}\cdot\mu_{k}\,,$

Let $T_{1}:=\min\\{t:D_{t}=1\\}$ be the time epoch for the first success. Then
$T_{1}$ is a geometric random variable with parameter
$\sum_{k=1}^{m+1}\frac{\mu_{k}}{K}$, hence
[T_1]=∑_k=1^m+1μkK^-1≤∑_k=1^m+1μlowK^-1=Kμlow1M+1 . Now $T-T_{1}$ is exactly
distributed as the time Algorithm 1 takes to detect $m$ unsafe machines among
in total $K-1$ machines. By our induction assumption, we have
[T-T_1]≤K-1μlow(∑_k=1^m1k)≤Kμlow(∑_k=1^m1k) . Adding (.1) and (.1), we obtain
the desired result

$\expc[T]\leq\frac{K}{\mu_{\mathrm{low}}}\left(\sum_{k=1}^{m+1}\frac{1}{k}\right)\,,$

for the case $M=m+1$, which finishes the proof. ∎

###  .2 Proof of Lemmas 2–3

Figure 7: Visualization of the cylinder set $C(1,0,1,1)$. It contains all
trajectories $\\{x_{\tau}\\}_{\tau=1,\ldots,\infty}$ that start with
$1,0,1,1.$

In order to prove these lemmas we first review cylinder sets, which were first
described by Wald [wald1945]. Consider an infinite sequence
$\\{d_{\tau}\\},\tau\geq 1$ and define $C_{\infty}$ as the space of all such
sequences. The set $C(x_{1},\ldots,x_{t})$ is called a cylinder set of order
$t$, and is defined as the subset of $C_{\infty}$ which collects sequences
with $d_{1}=x_{1},\ldots,d_{t}=x_{t}$. A cylinder set will be said to be of
the _unsafe type_ if

$\Lambda_{t}=\log\frac{f_{\mu}\left(x_{1},\ldots,x_{t}\right)}{f_{\mu-\epsilon}\left(x_{1},\ldots,x_{t}\right)}\geq\log(1/\alpha)\,,$
(31)

and

$\Lambda_{\tau}=\frac{f_{\mu}\left(x_{1},\ldots,x_{\tau}\right)}{f_{\mu-\epsilon}\left(x_{1}\ldots,x_{\tau}\right)}<\log(1/\alpha)\quad\forall\tau<t\;.$
(32)

The first condition guarantees that all sequences $\\{d_{\tau}\\}$ belonging
to the unsafe cylinder $C(x_{1},\ldots,x_{t})$ will lead to the acceptance of
$\mathcal{H}_{1}$. This will occur at time $t$, regardless of the future
samples $d_{\tau},\tau>t$. The second condition states that the threshold is
not surpassed sooner than $t$. Conditions (31)–(32) imply that cylinders of
different orders are disjoint sets, since $\Lambda_{t}$ exceeds the threshold
for the first time at $t$ and no sooner than that, and this cannot be true for
different values of $t$.

The union of all unsafe cylinder sets (of any order) defines the set of
sequences that lead to deciding $H_{1}$. Let us name this (disjoint) union as
$Q_{U}$. Let us also define $Q_{S}$ as the complement of $Q_{U}$

$Q_{S}=Q_{U}^{\complement}\,.$ (33)

$Q_{S}$ is the set of all sequences for which $\Lambda_{t}<\log(1/\alpha)$ for
all $t$. Since the sets are complementary, it holds that

$P_{\mu_{a}}(Q_{U}+Q_{S})=1\quad\forall\mu_{a}\in[0,1]\,,$ (34)

with $P_{\mu_{a}}(Q)$ being the probability of any subset $Q$ of $C_{\infty}$,
under the assumption that the sequence is generated by i.i.d. Bernoulli random
variables with parameter $\mu_{a}$.

We now turn to the proof of Lemmas 2–3 by restating them in terms of the
cylinder sets just described.

######  Lemma 2 (Restated).

Let $P_{\mu_{a}}(Q)$ be the probability of $Q\subset C_{\infty}$, under the
assumption that the sequence of data is generated by i.i.d. Bernoulli random
variables of parameter $\mu_{a}$. Then the following statements hold:

  1. i)

Under $\mathcal{H}_{1}$ ($\mu_{a}>\mu$), i.i.d. sequences produced by such a
distribution are correctly classified almost surely, that is

$P_{\mu_{a}}(Q_{U})=1\,.$ (35)

  2. ii)

Under $\mathcal{H}_{0}$ ($\mu_{a}\leq\mu$), the probability that a trajectory
never rises above $\log(1/\alpha)$ is greater than $1-\alpha$, that is

$P_{\mu_{a}}(Q_{S})\geq 1-\alpha\,.$

###### Proof.

We start by showing i).
For a given sequence $(d_{1},\ldots,d_{t},\cdots)$ we have

$\Lambda_{t}=\log\prod_{i=1}^{t}\frac{f_{\mu}(d_{i})}{f_{\mu-\epsilon}(d_{i})}=\sum_{i=1}^{t}\log\frac{f_{\mu}(x_{i})}{f_{\mu-\epsilon}(x_{i})}\,.$
(36)

Dividing by $t$:

$\frac{\Lambda_{t}}{t}=\frac{1}{t}\sum_{i=1}^{t}\log\frac{f_{\mu}(x_{i})}{f_{\mu-\epsilon}(x_{i})}\,.$
(37)

By the Law of large numbers, as $t$ grows (37) converges to the expectation of
the right hand side under $\mu_{a}$:

$\displaystyle\frac{\Lambda_{t}}{t}$
$\displaystyle\rightarrow\mathbb{E}_{\mu_{a}}\left[\log\frac{f_{\mu}(x)}{f_{\mu-\epsilon}(x)}\right]$
$\displaystyle=\mu_{a}\left(\log\frac{\mu}{\mu-\epsilon}-\log\frac{1-\mu}{1-(\mu-\epsilon)}\right)+\log\frac{1-\mu}{1-(\mu-\epsilon)}$
$\displaystyle>\mu\left(\log\frac{\mu}{\mu-\epsilon}-\log\frac{1-\mu}{1-(\mu-\epsilon)}\right)+\log\frac{1-\mu}{1-(\mu-\epsilon)}$
$\displaystyle=\text{kl}(\mu,\mu-\epsilon)>0\,,$ (38)

where kl is the Kullback-Leibler divergence between two Bernoulli
distributions of parameters $\mu$ and $\mu-\epsilon$. The inequality holds
because $\mu_{a}>\mu$ and the expression in brackets is positive. It follows
that

$\lim_{t\rightarrow\infty}\Lambda_{t}=\infty,\quad a.s.$

Therefore there must exist a positive integer $t$ for which $\Lambda_{t}$
exceeds $\log(1/\alpha)$, so that the sequence $\\{d_{\tau}\\}$ belongs to an
unsafe cylinder of order $t$ and thus $\\{d_{\tau}\\}\in Q_{U}$, which is what
we wanted to show.∎

Next, we prove _ii)_. First, by showing that $P_{\mu-\epsilon}(Q_{S})\geq
1-\alpha$ for the limiting case $\mu_{a}=\mu-\epsilon$, and then by
generalizing it for $\mu_{a}\leq\mu-\epsilon$. For $\mu_{a}=\mu-\epsilon$, the
core of the proof relies in showing that when the threshold for declaring
$\mathcal{H}_{1}$ is set to $\log(1/\alpha)$, then

$P_{\mu}(Q_{U})\geq\frac{1}{\alpha}P_{\mu-\epsilon}(Q_{U})\;.$ (39)

Once we prove (39), we use the fact that $P_{\mu}(Q_{U})=1$ (see (35)) and
obtain

$P_{\mu-\epsilon}(Q_{U})\leq\alpha\Rightarrow P_{\mu-\epsilon}(Q_{S})\geq
1-\alpha\,,$ (40)

as desired. To prove (39) we start by decomposing $Q_{U}$ as the union across
time $t$ of the union of all unsafe cylinders of order $t$, that is

$Q_{U}=\bigcup_{t=1}^{\infty}\bigcup_{(x_{1},\ldots,x_{t})\in\mathcal{X}_{t}}C(x_{1},\ldots,x_{t})\,,$

where $\mathcal{X}_{t}$ collects the tuples $(x_{1},\ldots,x_{t})$ that define
unsafe cylinders of order $t$, i.e., those satisfying (31) and (32). By
construction all the cylinder sets are disjoint, hence

$\displaystyle P_{\mu}(Q_{U})$
$\displaystyle=\sum_{t=1}^{\infty}\sum_{(x_{1},\ldots,x_{t})\in\mathcal{X}_{t}}P_{\mu}\left(C(x_{1},\ldots,x_{t})\right)$
$\displaystyle=\sum_{t=1}^{\infty}\sum_{(x_{1},\ldots,x_{t})\in\mathcal{X}_{t}}f_{\mu}(x_{1},\ldots,x_{t})$
$\displaystyle\geq\sum_{t=1}^{\infty}\sum_{(x_{1},\ldots,x_{t})\in\mathcal{X}_{t}}\frac{1}{\alpha}f_{\mu-\epsilon}(x_{1},\ldots,x_{t})$
$\displaystyle=\frac{1}{\alpha}\sum_{t=1}^{\infty}\sum_{(x_{1},\ldots,x_{t})\in\mathcal{X}_{t}}P_{\mu-\epsilon}(C(x_{1},\ldots,x_{t}))$
$\displaystyle=\frac{1}{\alpha}P_{\mu-\epsilon}(Q_{U})\,,$

where the second identity follows from marginalizing over future trajectories
(see Fig. 7), and the inequality holds since $\mathcal{X}_{t}$ is defined so
as to satisfy (31).

Now that we have (39), (40) follows immediately, and we move to the second
part of the proof. We need to prove that $P_{\mu_{a}}(Q_{S})\geq
P_{\mu-\epsilon}(Q_{S})$, or equivalently $P_{\mu_{a}}(Q_{U})\leq
P_{\mu-\epsilon}(Q_{U})$, when $\mu_{a}<\mu-\epsilon$. This essentially means
that the probability of (incorrectly) classifying a safe machine as unsafe
decreases as $\mu_{a}$ lowers, which is intuitively true.

To show this, notice that the log-likelihood ratio $\Lambda_{t}$ can be put in
terms of $k$, the number of outcomes of $D_{\tau}=1$ over $t$ total pulls:

$\Lambda_{t}=k\log\frac{\mu}{\mu-\epsilon}+(t-k)\log\frac{1-\mu}{1-(\mu-\epsilon)}\,,$
(41)

and $k\sim\mathrm{Binomial}(t,\mu_{a})$. What we want to show is that as
$\mu_{a}$ lowers, the probability that $\Lambda_{t}\geq\log(1/\alpha)$ lowers
as well, which is to be expected since $k$ will likely be lower. Assume then
we declare $\mathcal{H}_{1}$, so departing from (41) we can write

$\Lambda_{t}=k\lambda_{0}+(k-t)\lambda_{1}\geq\log(1/\alpha)\;,$

where $\lambda_{0}=\log\frac{\mu}{\mu-\epsilon}$ and
$\lambda_{1}=\log\frac{1-\mu+\epsilon}{1-\mu}$ are both positive. Since
$\log(1/\alpha)$ is also positive we have
$k/t\geq\frac{\lambda_{1}}{\lambda_{0}+\lambda_{1}}=\left(1+\frac{\lambda_{0}}{\lambda_{1}}\right)^{-1}$.
From the definition of $\lambda_{0}$ and $\lambda_{1}$ it yields

$\displaystyle\frac{k}{t}$
$\displaystyle\geq\left(1+\frac{\lambda_{0}}{\lambda_{1}}\right)^{-1}=\left(1+\frac{\log\frac{\mu}{\mu-\epsilon}}{\log\frac{1-\mu+\epsilon}{1-\mu}}\right)^{-1}$
$\displaystyle\geq\left(1+\frac{\frac{\mu}{\mu-\epsilon}-1}{1-\frac{1-\mu}{1-\mu+\epsilon}}\right)^{-1}=\left(1+\frac{\frac{\epsilon}{\mu-\epsilon}}{\frac{\epsilon}{1-\mu+\epsilon}}\right)^{-1}$
(42)
$\displaystyle=\left(\frac{1}{\mu-\epsilon}\right)^{-1}=\mu-\epsilon>\mu_{a}\,,$
(43)

where the inequality in (42) follows from the usual bounds of the logarithm
$1-1/x\leq\log(x)\leq x-1$. Rearranging (43) we get $k-t\mu_{a}>0$. Then, the
derivative of $f_{\mu_{a}}(a_{1},\ldots,a_{t})$ takes the form

$\displaystyle\frac{d}{d{\mu_{a}}}f_{\mu_{a}}(a_{1},\ldots,a_{t})=\frac{d}{d\mu_{a}}{t\choose
k}\mu_{a}^{k}(1-\mu_{a})^{t-k}$ $\displaystyle={t\choose
k}\left(k\mu_{a}^{k-1}(1-\mu_{a})^{t-k}+\mu_{a}^{k}(-1)(t-k)(1-\mu_{a})^{t-k-1}\right)$
$\displaystyle={t\choose
k}\mu_{a}^{k-1}(1-\mu_{a})^{t-k-1}\left(k-t\mu_{a}\right)>0\,,$ (44)

where the last inequality stems from (43). Putting (34), (40), and (44)
together results in $P_{\mu_{a}}(Q_{S})\geq 1-\alpha$ for all
$\mu_{a}\leq\mu-\epsilon$. ∎

######  Lemma 3.

For a fixed arm $a$ of parameter $\mu_{a}$, consider the sequential
probability ratio test defined by (6)–(8), where $\mu$, $\epsilon$ and
$\alpha$ are given. Then, if the alternative $\mathcal{H}_{1}$ is true, the
test is expected to terminate after $T$ steps, with

$\mathbb{E}[T]\leq
1+\frac{\log\left(1/\alpha\right)}{\emph{kl}(\mu,\mu-\epsilon)}\;,$ (45)

where $\emph{kl}(\mu,\mu-\epsilon)$ is the Kullback-Leibler divergence between
Bernoulli distributions

$\emph{kl}(\mu,\mu-\epsilon)=\mu\log\frac{\mu}{\mu-\epsilon}+\left(1-\mu\right)\log\frac{1-\mu}{1-\mu+\epsilon}\,.$

###### Proof.

Let $T$ be the smallest integer for which the test leads to the acceptance of
$H_{1}$. Such variable is well defined and finite as a result of Lemma 2.
Consider the sequence of damage up to time t $(d_{t})_{t=1}^{T}$, and let
$\mathbb{E}_{\mu_{a}}[\cdot]$ be the expectation with respect to the true
distribution of the damage data (that is, $D\sim\text{Bernoulli}(\mu_{a})$).
Then

$\displaystyle\mathbb{E}_{\mu_{a}}[\Lambda_{T}]$
$\displaystyle=\mathbb{E}_{\mu_{a}}\left[\sum_{t=1}^{T}\log\frac{f_{\mu}(d_{t})}{f_{\mu-\epsilon}(d_{t})}\right]$
$\displaystyle=\mathbb{E}[T]\mathbb{E}_{\mu_{a}}\left[\log\frac{f_{\mu}(d)}{f_{\mu-\epsilon}(d)}\right]=\mathbb{E}[T]R_{a}\;,$
(46)

with
$R_{a}=\mathbb{E}_{\mu_{a}}\left[\log\frac{f_{\mu}(d)}{f_{\mu-\epsilon}(d)}\right]$.
Here we used Wald’s identity [wald-identity] in the second equality.
Furthermore

$\displaystyle\mathbb{E}_{\mu_{a}}\left[\Lambda_{T}\right]$
$\displaystyle=\mathbb{E}_{\mu_{a}}\left[\Lambda_{T-1}+\log\frac{f_{\mu}(d_{T})}{f_{\mu-\epsilon}(d_{T})}\right]$
$\displaystyle=\mathbb{E}_{\mu_{a}}\left[\Lambda_{T-1}\right]+R_{a}\leq\log(1/\alpha)+R_{a}\,.$
(47)

Combining (46) and (47):

$\mathbb{E}[T]\leq 1+\frac{\log\left(1/\alpha\right)}{R_{a}}\leq
1+\frac{\log\left(1/\alpha\right)}{\text{kl}(\mu,\mu-\epsilon)}\,,$

in virtue of $R_{a}\geq\text{kl}(\mu,\mu-\epsilon)$ for
$\mu_{a}>\mu-\epsilon$, as was shown in (38). ∎

###  .3 Proof of Theorem 3

By lemma 3, we have

$\expc[E_{T}]=\sum_{a=1}^{M}\expc[T_{a}]\leq{M}\left(1+\frac{\log(1/\alpha)}{\text{kl}(\mu,\mu-\epsilon)}\right)\,.$

Then by Wald’s identity [wald-identity], we have

$\expc[E_{T}]=\expc\lhp\sum_{t=1}^{T}\expc[\mathds{1}\\{\mu_{A_{t}}>\mu\\}]\rhp\geq\expc\lhp
T\frac{1}{K-M+1}\rhp\,,$

where the second inequality is due to the fact that before $T$, the
probability of sampling an unsafe machine is at least $1/(K-M+1)$. Recalling
the upper bound for $\expc[E_{T}]$ in Theorem 3, one obtain

$\mathbb{E}[T]\leq{M}(K-M+1)\left(1+\frac{\log(1/\alpha)}{\text{kl}(\mu,\mu-\epsilon)}\right)\,.$

###  .4 Proof of Theorem LABEL:thm:sample_comp_barrier_learner

We prove Theorem LABEL:thm:sample_comp_barrier_learner in three steps:

####  .4.1 Reformulation of Algorithm LABEL:alg:barrier_learner

We reformulate Algorithm LABEL:alg:barrier_learner as in Algorithm 5.

Data: Constrained Markov Decision Process $\mathcal{M}$

Initialize $B^{(0)}(s,a)=0,\forall(s,a)\in\mathcal{S}\\!\times\\!\mathcal{A}$

for  _$\tau=0,1,\cdots$_ do

Draw
$(s_{\tau},a_{\tau})\sim\mathrm{Unif}(\mathcal{S}\\!\times\\!\mathcal{A})$

Sample transition $(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau})$ according
to $\prob\lp
S_{1}=s^{\prime}_{\tau},D_{1}=d_{\tau}|S_{0}=s_{\tau},A_{0}=a_{\tau}\rp$

if  _$B^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty$_ then

$B^{(\tau+1)}\la\texttt{barrier\\_update(}B^{(\tau)},s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau}\texttt{)}$

else

$B^{(\tau+1)}\la B^{(\tau)}$

end if

end for

Algorithm 5 Barrier Learner Algorithm Reformulated

In the reformulated Algorithm 5, the sampling process is independent of
$B$-function: At each iteration $\tau$, an $(s_{\tau},a_{\tau})$ pair is drawn
uniformly from $\mathcal{S}\\!\times\\!\mathcal{A}$ and then a transition
$(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau})$ is sampled according to the
MDP, and the algorithm decides whether to accept such a sample depending on
the value of $B(s_{\tau},a_{\tau})$. When we restrict ourselves to the
trajectory of samples that are accepted, i.e.

$\\{(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau}):B^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty,\
\tau=0,1,\cdots\\}\,,$

this trajectory is also a sampled trajectory of original Algorithm
LABEL:alg:barrier_learner. More importantly, for such a trajectory, the
probability it appears in original Algorithm LABEL:alg:barrier_learner is the
same as the probability it appears as the accepted trajectory in Algorithm 5.
With that, we define T_r:=min{τ:B^(τ)=B^*} ,i.e. the earliest time when
Algorithm 5 detects all unsafe state-action pairs, then we have
[T]=∑_τ=1^T_r1{B^(τ)(s_τ,a_τ)≠-∞} , where $T$ is the earliest time when
Algorithm LABEL:alg:barrier_learner detects all unsafe state-action pairs, as
defined in Theorem LABEL:thm:sample_comp_barrier_learner. Expectations are
taken with respect to the respective sampling processes of Algorithm
LABEL:alg:barrier_learner and 5, which are different. With (.4.1), it suffices
to analyze the expected detection time of Algorithm 5.

####  .4.2 Construction of modified algorithm

As discussed in Section 3.3, an $(s,a)$ pair is unsafe if either it causes
damage immediately or it transitions to an unsafe state with non-zero
probability. If only the latter happens for such an unsafe $(s,a)$, then to be
able to declare it unsafe, one must have already declared one of its
succeeding states unsafe. To make such intuition precise, we recursively
define disjoint subsets $\mathcal{S}_{l},l=1,2,\cdots$ of the state space
$\mathcal{S}$ as follow,

$\displaystyle\mathcal{S}_{1}$ $\displaystyle:=\lb
s\in\mathcal{S}:\prob_{\pi}\lp D_{1}=1|S_{0}=s\rp>0,\forall\pi\rb\,,$
$\displaystyle\mathcal{S}_{l}$
$\displaystyle:=\begin{cases}\mathcal{S}_{l}^{\prime},&\mathcal{S}_{l}^{\prime}\neq\emptyset\\\
\mathcal{S}\setminus{\bigcup_{k<l}\mathcal{S}_{k}},&\mathcal{S}_{l}^{\prime}=\emptyset\end{cases}\,,$
(48) where $\displaystyle\mathcal{S}^{\prime}_{l}$ $\displaystyle=\lb
s\in\mathcal{S}\setminus{\bigcup_{k<l}\mathcal{S}_{k}}:\prob_{\pi}\lp
S_{1}\in\bigcup_{k<l}\mathcal{S}_{k}|S_{0}=s\rp>0,\forall\pi\rb$

It is clear that given any finite MDP,
$L:=\max\\{l>0:\mathcal{S}_{l+1}\neq\emptyset\\}$ is finite and we define $L$
to be the _lag_ of the MDP. Following the definition (48),
$\\{\mathcal{S}_{l},l=1,\cdots,L,L+1\\}$ is a partition of $\mathcal{S}$. Any
state $s_{0}\in\bigcup_{l=1}^{L}\mathcal{S}_{l}$ is unsafe because under any
policy $\pi$, with non-zero probability it happens that starting from $s_{0}$,
the MDP eventually reaches a state in $\mathcal{S}_{1}$ then causes damage.
Furthermore, any state
$s_{0}\in\mathcal{S}_{L+1}:=\mathcal{S}\setminus{\bigcup_{l=1}^{L}\mathcal{S}_{l}}$
is safe since $\mathcal{S}^{\prime}_{L+1}=\emptyset$ implies that there exists
$a_{0}\in\mathcal{A}$ such that
$\prob(S_{1}\in\bigcup_{k<L+1}\mathcal{S}_{k}|S_{0}=s_{0},A_{0}=a_{0})=0$,
i.e. taking action $a_{0}$ keeps the MDP away from the unsafe states in
$\bigcup_{l=1}^{L}\mathcal{S}_{l}$. However, we note that a safe state can
have unsafe actions and they can be detected by the Barrier Learner Algorithm.

More importantly, the unsafe state sets $\mathcal{S}_{l},l=1,2,\cdots,L$
satisfies that if all states in $\bigcup_{k<l}\mathcal{S}_{k}$ has been
declared unsafe, any state-action pair in
$\\{(s,a):s\in\mathcal{S}_{l},a\in\mathcal{A}\\}$, when sampled, can be
declared unsafe with non-zero probability. Base on this property, we construct
an modified barrier learning algorithm using the prior information on
$\mathcal{S}_{l},l=1,2,\cdots,L$. The modified algorithm is described in
Algorithm 6.

Data: Constrained Markov Decision Process $\mathcal{M}$,
$\mathcal{S}_{l},l=1,2,\cdots,L,L+1$ defined for $\mathcal{M}$

Initialize
$\hat{B}^{(0)}(s,a)=0,\forall(s,a)\in\mathcal{S}\\!\times\\!\mathcal{A}$

Initialize $l=1$

for  _$\tau=0,1,\cdots$_ do

Draw
$(s_{\tau},a_{\tau})\sim\mathrm{Unif}(\mathcal{S}\\!\times\\!\mathcal{A})$

Sample transition $(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau})$ according
to $\prob\lp
S_{1}=s^{\prime}_{\tau},D_{1}=d_{\tau}|S_{0}=s_{\tau},A_{0}=a_{\tau}\rp$

if  _$\hat{B}^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty$ and
$s_{\tau}\in\mathcal{S}_{l}$_ then

$\hat{B}^{(\tau+1)}\leftarrow\texttt{barrier\\_update(}\hat{B}^{(\tau)},s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau}\texttt{)}$

else

$\hat{B}^{(\tau+1)}\la\hat{B}^{(\tau)}$

end if

if  _$\hat{B}^{\tau+1}(s,a)=-\infty,\forall
s\in\mathcal{S}_{l},a\in\mathcal{A}$_ then

$l\la l+1$

end if

end for

Algorithm 6 Modified Barrier Learner Algorithm with Prior Information on
$\mathcal{S}_{l},l=1,2,\cdots,L,L+1$

The modified algorithm is similar to Algorithm 5 but it learns
$\mathcal{S}_{l},l=1,2,\cdots,L$ in order: At the beginning ($l=1$), it only
declares $(s,a)$ pairs associated with $\mathcal{S}_{1}$ unsafe until all
states in $\mathcal{S}_{1}$ are declared unsafe, after which $l$ increases to
$2$. Now the algorithm only declares $(s,a)$ pairs associated with
$\mathcal{S}_{2}$ unsafe. Finally after all states in
$\bigcup_{l=1}^{L}\mathcal{S}_{l}$ are declared unsafe ($l=L+1$), the
algorithm starts to learn the unsafe transitions for safe states in
$\mathcal{S}_{L+1}$. Similarly, we define ^T_r:=min{τ:^B^(τ)=B^*} ,i.e. the
earliest time when Algorithm 6 detects all unsafe state-action pairs.

Since the modified algorithm is more restrictive on declaring unsafe state-
action pair, the expected detection time of the modified algorithm is no less
than that of Algorithm 5, as stated in the following claim.

######  Claim 1.

Given an MDP, let $T_{r}$ and $\hat{T}_{r}$ be the earliest times when
Algorithm 5 and Algorithm 6, detect all unsafe state-action pairs in this MDP,
respectively, as defined in (.4.1) and (6). Then

$\displaystyle\;\expc\lhp\sum_{\tau=1}^{T_{r}}\mathds{1}\\{B^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty\\}\rhp$
$\displaystyle\;\qquad\qquad\leq\expc\lhp\sum_{\tau=1}^{\hat{T}_{r}}\mathds{1}\\{\hat{B}^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty\\}\rhp\,,$

where the expectation is taken with respect to the sampling of
$\\{(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau}),\tau=0,1,\cdots\\}$.

###### Proof.

Condition on a fixed sample trajectory
$\mathcal{T}:=\\{(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau})\\}_{\tau=0}^{\infty}\,,$
the functions $B^{(\tau)}$ and $\hat{B}^{(\tau)}$ are deterministic. We have

$\displaystyle
B^{(\tau)}(s,a)|\mathcal{T}\leq\hat{B}^{(\tau)}(s,a)|\mathcal{T},\forall\tau\\!\geq\\!0,\forall(s,a)\\!\in\\!\mathcal{S\\!\times\\!\mathcal{A}}\,,$
(50)

proved by induction: we have

$B^{(0)}(s,a)|\mathcal{T}\leq\hat{B}^{(0)}(s,a)|\mathcal{T},\forall(s,a)\in\mathcal{S\\!\times\\!\mathcal{A}}\,,$

at initialization. Suppose that (50) holds at time $\tau=t$. If
$(s_{t},a_{t},s^{\prime}_{t},d_{t})$ is accepted by both algorithms, or
rejected by both algorithms, we have
B^(t+1)(s,a)—T≤^B^(t+1)(s,a)—T,∀(s,a)∈S× A .

If $(s_{t},a_{t},s^{\prime}_{t},d_{t})$ is rejected by Algorithm 5 and
accepted by Algorithm 6, then we have

$B^{(t)}(s_{t},a_{t})=-\infty,\hat{B}^{(t)}(s_{t},a_{t})=0\,.$

(.4.2) still holds, since only $\hat{B}^{(t+1)}(s_{t},a_{t})$ is updated to
either $0$ or $-\infty$. If $(s_{t},a_{t},s^{\prime}_{t},d_{t})$ is accepted
by Algorithm 5 and rejected by Algorithm 6, then we have

$B^{(t)}(s_{t},a_{t})=\hat{B}^{(t)}(s_{t},a_{t})=0\,.$

(.4.2) still holds, since only $B^{(t+1)}(s_{t},a_{t})$ is updated to either
$0$ or $-\infty$. Now from (50), we immediately know that condition on the
fixed sample trajectory $\mathcal{T}$,

$\mathds{1}\\{B(s_{\tau},a_{\tau})\neq-\infty\\}\leq\mathds{1}\\{\hat{B}(s_{\tau},a_{\tau})\neq-\infty\\},\forall\tau=0,1,\cdots$

Notice that $T_{r}$ ($\hat{T}_{r}$) is the minimum $t$ such that $B^{(t)}$
($\hat{B}^{(t)}$) becomes exactly the same as $B^{*}$. Then
$T_{r}|\mathcal{T}\leq\hat{T}_{r}|\mathcal{T}\,.$ Therefore one have, by law
of total expectation,

∎

####  .4.3 Expected detection time of modified algorithm

Lastly, we prove the following Theorem regarding the expected detection time
of the modified algorithm.

######  Theorem 7.

Given an MDP with $\mathcal{S}_{l},l=1,2,\cdots,L,L+1$ defined as in (48).
Assume that exists $\mu>0$ such that the transition probability
$\prob(S_{1}=s^{\prime}|S_{0}=s,A_{0}=a)$, is either zero or lower bounded by
$\mu$, for all $s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}$. Let $\hat{T}_{r}$
be earliest time when Algorithm 6 detects all unsafe state-action pairs as
defined in (6), then we have

$\expc\lhp\sum_{\tau=1}^{\hat{T}_{r}}\mathds{1}\\{\hat{B}^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty\\}\rhp\leq\frac{|\mathcal{S}||\mathcal{A}|}{\mu}\sum_{l=1}^{L+1}\lp\sum_{k=1}^{|\mathcal{S}_{l}||\mathcal{A}|}\frac{1}{k}\rp\,.$

###### Proof.

Let $\hat{T}_{l},l=1,\cdots,L+1$ denote the earliest time when all unsafe
state-action pairs associated with $\mathcal{S}_{l}$ are detected by Algorithm
6, and we let $\hat{T}_{0}=0$. Then clearly

$\hat{T}_{l-1}<\hat{T}_{l},l=1,\cdots,L+1\,,\quad\hat{T}_{L+1}=\hat{T}_{r}\,,$

and
$\Delta_{l}:=\sum_{t=\hat{T}_{l-1}}^{\hat{T}_{l}-1}\mathds{1}\\{\hat{B}^{(t)}(s_{t},a_{t})\neq-\infty\\}$
is the number of accepted samples by Algorithm 6 between $\hat{T}_{l-1}$ and
$\hat{T}_{l}$.

Notice that we can view the barrier learning process between $\hat{T}_{l-1}$
and $\hat{T}_{l}$ as detecting unsafe machines in the safe multi-arm bandits
problem discussed in Section 2: At time $\hat{T}_{l-1}$, there are in total
$K_{l}:=\lv\lb(s,a):s\in\bigcup_{k=l}^{L+1}\mathcal{S}_{k},a\in\mathcal{A}\rb\rv$
machines, and the number of unsafe machines is

$M_{l}:=\lv\\{(s,a):s\in\mathcal{S}_{l},a\in\mathcal{A},B^{*}(s,a)=-\infty\\}\rv\,.$

We have $K_{l}\leq|\mathcal{S}||\mathcal{A}|\,,\
M_{l}\leq|\mathcal{S}_{l}||\mathcal{A}|\,.$ Furthermore, condition on such an
unsafe machine is pulled, i.e. an unsafe $(s,a)$ in $\mathcal{S}_{l}$ is
accepted by Algorithm 6, the probability of declaring it unsafe is at least
$\mu$. Because the $(s,a)$ pair either transitions to some
$s\in\bigcup_{k=1}^{l-1}\mathcal{S}_{k}$ that has been declared unsafe or
directly incurs damage with non-zero probability, and that probability is
lower bounded by $\mu$ according to our assumption.

The acceptance of sample $(s_{\tau},a_{\tau},s^{\prime}_{\tau},d_{\tau})$ is
equivalent to pulling a uniformly randomly drawn arm out of arms that have not
been declared unsafe. Theorem 2 suggests that the expected number of such
”pulling” is upper bounded as

$\expc[\Delta_{l}]\leq\frac{K_{l}}{\mu}\lp\sum_{k=1}^{M_{l}}\
\frac{1}{k}\rp\leq\frac{|\mathcal{S}||\mathcal{A}|}{\mu}\lp\sum_{k=1}^{|\mathcal{S}_{l}||\mathcal{A}|}\frac{1}{k}\rp\,.$

Finally, we have

$\displaystyle\;\expc\lhp\sum_{t=0}^{\hat{T}_{r}}\mathds{1}\\{\hat{B}^{(t)}(s_{t},a_{t})\neq-\infty\\}\rhp$
$\displaystyle=$
$\displaystyle\;\expc\lhp\sum_{l=1}^{L+1}\Delta_{l}\rhp\leq\frac{|\mathcal{S}||\mathcal{A}|}{\mu}\sum_{l=1}^{L+1}\lp\sum_{k=1}^{|\mathcal{S}_{l}||\mathcal{A}|}\frac{1}{k}\rp\,.$

∎

Now we are ready to prove Theorem LABEL:thm:sample_comp_barrier_learner.

###### Proof of Theorem LABEL:thm:sample_comp_barrier_learner.

Given any MDP, we have $|\mathcal{S}_{l}|\leq|\mathcal{S}|,\forall
l=0,1,\cdots,L+1$, then we have

$\displaystyle\expc[T]$
$\displaystyle\leq\\!\expc\lhp\sum_{\tau=1}^{\hat{T}_{r}}\mathds{1}\\{\hat{B}^{(\tau)}(s_{\tau},a_{\tau})\neq-\infty\\}\rhp$
$\displaystyle\leq\\!\frac{|\mathcal{S}||\mathcal{A}|}{\mu}\sum_{l=1}^{L+1}\lp\sum_{k=1}^{|\mathcal{S}_{l}||\mathcal{A}|}\frac{1}{k}\rp\leq\\!\frac{|\mathcal{S}||\mathcal{A}|(L+1)}{\mu}\lp\sum_{k=1}^{|\mathcal{S}||\mathcal{A}|}\frac{1}{k}\rp\,,$

where the first equality is from (.4.1) and Claim 1. ∎

[]Agustin Castellano is currently working towards the M.Sc. in Electrical
Engineering at Universidad de la República, Uruguay. He recieved his degree in
Electrical Engineering from the same university in 2017. His current research
interests include Learning Algorithms and their applications to power system
optimization.

[]Hancheng Min is currently working toward the Ph.D. degree at the Department
of Electrical and Computer Engineering, Johns Hopkins University. He received
the B.Eng. degree in Electrical Engineering and Automation from Tongji
University in 2016, and the M.S. degree in Systems Engineering from University
of Pennsylvania in 2018. His research interests include analysis and control
of large-scale networks, and theoretical analysis of learning dynamics in
machine learning.

[]Juan Andrés Bazerque received the B.Sc. degree in electrical engineering
from Universidad de la República (UdelaR), Montevideo, Uruguay, in 2003, and
the M.Sc. and Ph.D. degrees from the Department of Electrical and Computer
Engineering, University of Minnesota (UofM), Minneapolis, in 2010 and 1013
respectively. Since 2015 he is an Assistant Professor with the Department of
Electrical Engineering at UdelaR. His current research interests include
stochastic optimization and networked systems, focusing on reinforcement
learning, graph signal processing, and power systems optimization and control.
Dr. Bazerque is the recipient of the UofM’s Master Thesis Award 2009-2010, and
co-reciepient of the best paper award at the 2nd International Conference on
Cognitive Radio Oriented Wireless Networks and Communication 2007.

[] Enrique Mallada (S’09-M’13-SM’) is an Assistant Professor of Electrical and
Computer Engineering at Johns Hopkins University. Prior to joining Hopkins in
2016, he was a Post-Doctoral Fellow in the Center for the Mathematics of
Information at Caltech from 2014 to 2016. He received his Ingeniero en
Telecomunicaciones degree from Universidad ORT, Uruguay, in 2005 and his Ph.D.
degree in Electrical and Computer Engineering with a minor in Applied
Mathematics from Cornell University in 2014. Dr. Mallada was awarded the Johns
Hopkins Alumni Association Teaching Award in 2021, the Catalyst and Discovery
Awards in 2020 and 2021, respectively, from Johns Hopkins University, the NSF
CAREER award in 2018, the ECE Director’s Ph.D. Thesis Research Award for his
dissertation in 2014, the Center for the Mathematics of Information (CMI)
Fellowship from Caltech in 2014, and the Cornell University Jacobs Fellowship
in 2011. His research interests lie in the areas of control, dynamical
systems, and optimization, with applications to engineering networks.