# Bilevel Online Deep Learning in Non-stationary Environment

Ya-nan Han  Jian-wei Liu<EMAIL_ADDRESS>Bing-biao Xiao  and Xiong-lin Luo
Department of Automation, College of Information Science and Engineering,
China University of Petroleum, Beijing Campus (CUP), Beijing, China

###### Abstract

Recent years have witnessed enormous progress of online learning. However, a
major challenge on the road to artificial agents is concept drift, that is,
the data probability distribution would change where the data instance arrives
sequentially in a stream fashion, which would lead to catastrophic forgetting
and degrade the performance of the model. In this paper, we proposed a new
Bilevel Online Deep Learning (BODL) framework, which combine bilevel
optimization strategy and online ensemble classifier. In BODL algorithm, we
use an ensemble classifier, which use the output of different hidden layers in
deep neural network to build multiple base classifiers, the important weights
of the base classifiers are updated according to exponential gradient descent
method in an online manner. Besides, we apply the similar constraint to
overcome the convergence problem of online ensemble framework. Then an
effective concept drift detection mechanism utilizing the error rate of
classifier is designed to monitor the change of the data probability
distribution. When the concept drift is detected, our BODL algorithm can
adaptively update the model parameters via bilevel optimization and then
circumvent the large drift and encourage positive transfer. Finally, the
extensive experiments and ablation studies are conducted on various datasets
and the competitive numerical results illustrate that our BODL algorithm is a
promising approach.

###### keywords:

Online Deep Learning · Bilevel Optimization · Concept Drift.

††journal: arXiv

##  1 Introduction

Deep learning techniques have achieved enormous success in a wide range of
artifi-cial intelligence (AI) and machine learning applications in recent
years[1, 2]. However, most of these existing deep learning approaches suppose
that the models often work in a batch learning setting or offline learning
fashion, where the entire training dataset must be available to train a model
by some learning techniques. Such learning ap-proaches are poorly scalable for
many real-word tasks, where the data instances arrive in a sequential manner.
Thus, making deep learning available for the streaming data is a desideratum
in the field of machine learning.
Unlike traditional batch learning, online learning represents a significant
family of learning algorithms that are designed to optimize and learn models
incrementally over streaming data sequentially[3]. Online learning shows the
tremendous ad-vantages that the models can be updated efficiently in an online
manner compared with traditional offline learning fashion when the new data
instance comes. Similar to batch learning algorithms, online learning can also
be applied for various real-word tasks, such as supervised classification
task[4], unsupervised learning task[5], and so on.
However, in general, online learning algorithms cannot be directly employed to
deep neural network. They have to cope with the intractable convergence
problems, such as vanishing gradient. Besides, the traditional shallow or
fixed neural network structure is poorly scalable for the most real-world
applications where the data in-stances arrive in a sequential order and the
probability distribution of data is non-stationary. Therefore, a promising
online deep learning framework should be devel-oped that can effectively and
rapidly learn knowledge in non-stationary.
It should also be noted that the probability distribution obeyed by streaming
data could occur the concept drift, in other words, the data probability
distribution chang-es. In this circumstance, the leaning algorithms must take
some actions to prevent the large drift and encourage positive transfer, in
other words, the learner should make a trade-off between both the new and old
knowledge and alleviate the catastrophic forgetting. The classical algorithms
for catastrophic forgetting are Elastic Weight Consolidation (EWC)[6] and
their variants[7], but this kind of algorithms attempt to address catastrophic
forgetting by augmenting objective function and then control the whole
network, that is, let the learning model’s weights balance between these two
factors, rather than directly take actions to cope with catastrophic
forgetting. Based on the above fact, therefore this reminds us of the
importance to enhance the differ-ent-depth latent representations and the
ability to rapidly adapt to dynamic changing situations.
To achieve this, in this work, we devise a novel Bilevel Online Deep Learning
(BODL) framework, which consists of three major components: online ensemble
classifier, concept drift detection and bilevel online deep learning. Our BODL
frame-work can effectively utilize the different abstract level latent feature
representations to build classifiers via the online ensemble framework, where
the important weights of the base classifiers would be updated by online
exponential gradient descent strat-egy. consider the convergence problem of
online ensemble framework, we apply the similar constraint to generate the
favorable latent representation. Besides, a concept drift detected mechanism
is devised according to the error rate of base classifiers. When the concept
drift is detected, our BODL model can adaptively update the model parameters
via bilevel optimization and then prevent the large drift and en-courage
positive transfer.
In a summary, our main contributions in this paper are listed below:
1) We design an effective bilevel learning strategy. Specifically, if the
concept drift is detected, the model would adaptively adjust the parameters
for all base classi-fiers and of the different-depth feature representation
mentioned in section 2 using bilevel optimization, where this process is
achieved based on a tiny episodic memory. After that, the model can circumvent
the large drift and encourage positive transfer in non-stationary environment.
2) In this work, consider the convergence problem of online ensemble
framework, we impose the similar constraint between the shallower and the
deeper layer’s fea-ture, which would be beneficial to generate the favorable
feature representations.
3) The comparative experiments are devised to verify the effectiveness of the
pro-posed BODL algorithm, and we analysis the experimental results of a
variety of algo-rithms from different perspectives in terms of accuracy,
precision, recall-score and F-1 score, and then we can see that our BODL
algorithm can exploit the different-depth feature representations and adapt to
rapidly changing environment.
The remainder of this paper is organized as follows. In Section 2, we
introduce our BODL algorithm in details, which consists of three parts: online
ensemble classifier, concept drift detection mechanism, bilevel learning for
concept drift. In Section 3 we empirically compare BODL algorithm with several
state-of-the-art online learning algorithms. In Section 4 we elaborate related
works. In Section 5 we summarize the whole work and the interested directions
in the future.

##  2 Bilevel Online Deep Learning(BODL)

In this work, we present bilevel online deep learning, a conceptually novel
framework for online learning based on bilevel optimization[8] and online
ensemble framework. Our BODL architecture can be divided into three main
parts: online ensemble classi-fier, concept drift detection mechanism, bilevel
learning for concept drift. The online deep ensemble classifier can make a
trade-off among the different-level base classi-fiers and improve the
performance of classification; Concept drift detection mecha-nism is used to
monitor the change in non-stationary environment; When the concept drift is
detected, bilevel learning is designed to adaptively adjust the parameters
$\theta_{n}^{t}$ and $W_{n}^{t}$ , then the model can adapt to the change in
non-stationary environment.

###  2.1 Online Ensemble Classifier

We illustrate the online deep ensemble classifier in Fig.1, where
${\omega^{t}}=[\omega_{1}^{t},...,\omega_{N}^{t}]$ represents the importance
of the N base classifiers. The online deep ensemble classifi-er can make a
trade-off among the different-level base classifiers via Exponential Gradient
Descent(EGD) algorithm in an online manner[4].
More specifically, we character a Deep Neural Network (DNN) with hidden
layers, and the final ensemble classifier can be achieved by dynamically
updating the weight parameters of the base classifiers for each hidden layer
based on their classifi-cation loss. The specific ensemble prediction function
can be written as Eq.(1).

$\begin{array}[]{c}F(x)=\sum\limits_{n=0}^{N}{{\omega_{n}}{f_{n}}}\\\
{f_{n}}=soft\max({h_{n}}{\theta_{n}}),\forall n=0,...,N\\\
{h_{n}}=\sigma({W_{n}}{h_{n-1}}),\forall n=1,...,N\\\ \end{array}$ (1)

Compared to the traditional network, in which the feature representation con-
structed by outputs of the final hidden layer is used as input of the
classifier, here we can make a favorable classifier by an online ensemble
framework, which can benefit from the different depth feature representation
and improve the prediction perfor-mance of the whole model. It is noted that
the parameters $\omega_{n}^{t}$ ,$\theta_{n}^{t}$ and $W_{n}^{t}$ in Eq.(1)
can be learned in an online flavor.

Figure 1: Online deep ensemble classifier.

Update the parameters ${\omega_{n}}$ We update the weights ${\omega_{n}}$ for
base classifiers using exponential gradient descent11. Firstly, the weights
${\omega}$ are initialized using a uniform
distribution:${\omega_{n}}=\frac{1}{{N+1}},n=0,...,N$ i.e., each base
classifier has equal probability to be picked. At each iteration, the
prediction loss of the n-th base classifier ${f_{n}}$ can be written as ${\cal
L}(\hat{y}_{n}^{t},y_{n}^{t})$ , where $\hat{y}_{n}^{t}$ and $y_{n}^{t}$
represent the base classifier prediction and the target variable respectively.
Then, the weight of each base classifier can be learned according to the loss
suffered and the update rule is given by follow:

$\omega_{n}^{t+1}\leftarrow\omega_{n}^{t}{e^{-\eta{\cal
L}(\hat{y}_{n}^{t},y_{n}^{t})}}$ (2)

where $\eta\in(0,+\infty)$ and $\eta$ is set to 0.01 in our work. After that,
the trained base clas-sifier’s important weight is discounted by an
exponential weight $e^{-\eta{\cal L}(\hat{y}_{n}^{t},y_{n}^{t})}$.
Update the parameters ${\theta_{n}^{t}}$ The parameters ${\theta_{n}^{t}}$ for
all base classifiers are updated using Stochastic Online Gradient Descent
(SOGD), and this process is analogical to the traditional feedforward
networks.
Update the parameters $W_{n}^{t}$ The update rule about the parameters
$W_{n}^{t}$ of the dif-ferent-depth feature representation is different from
the traditional backpropagation framework. The objective function includes two
parts: the adaptive loss function and similar constraint, which are defined as
follow:

${\cal L}(F(x),y)=\sum\limits_{n=0}^{N}{{\omega_{n}}}{{\cal
L}_{pre}}({f_{n}}(x),y)+\lambda{{\cal L}_{sim}}({h_{se}},{h_{de}})$ (3)

where, the first part in loss function represents the adaptive prediction
loss. Note that, the parameters of shallower layer tend to converge faster
than the ones of deeper layer, which can lead to deeper base classifiers learn
slowly[2]. Thus, we incorporate the similar constraint between the shallower
and deeper layer’s features, which can be beneficial to generate the favorable
feature representations and improve the conver-gence rate and the prediction
performance of the deeper layer. In this work, $\lambda$ is a tradeoff
parameter and is set to 0.1. Note that, the similarity can be modelled in mul-
tiple manners and we choose the squared distance metric in this paper.

###  2.2 Bilevel Online Deep Learning

As the streaming data comes gradually and the data probability distribution
could change. We monitor the change of the data probability distribution
utilizing the error rate of classifier. This concept drift detection mechanism
is similar to the drift detec-tion method in [9] but the warning phase is not
arranged in this paper in order to avoid the use of slide window methods. In
this section, we describe our adaptive online deep learning based on bilevel
optimization in detail. Figure 2 shows a flowchart of the bilevel online deep
learning framework.

Figure 2: The bilevel online deep learning framework. BODL utilizes the memory
replay weights $\Theta$ and the episodic memory to optimize the base
classifiers’ weights $\Phi$ in the non-stationary environ-ment, where the
episodic memory is obtained by reservoir sampling.

####  2.2.1 Bilevel Learning

For each arriving instance in online learning scenario, we detect the concept
drift uti-lizing the error rate of classifier. If the concept drift is
observed, the learning algorithm obviously needs to takes some actions to
prevent large drift and achieve online in-cremental learning. Specifically,
when the concept drift occurs, BODL initializes a memory weight $\Theta$ to
replay the knowledge in the memory. Then we apply the trained memory weight
$\Theta^{*}$ to update $\Phi$ such that it can prevent large drift and weight
the new and old knowledge in a non-stationary environment as shown in the
Fig.2.
Bearing this in mind, the objective function can be defined as the following
bilevel optimization problem:

$\begin{array}[]{c}\mathop{\min}\limits_{\Phi}{{\cal
L}^{outer}}(\Theta*(\Phi),\beta_{train}^{t};\Phi)\\\
s.t.{\Theta^{*}}=\arg\mathop{\min}\limits_{\Theta}{{\cal
L}^{inner}}({\Theta^{*}},{{\cal M}^{memory}})\end{array}$ (4)

where $\beta_{train}^{t}$ denotes the current training data that exists
concept drift. We parame-terize each $\Phi$ as an inner optimization problem
${\cal L}_{\Phi}^{memory}$ , which the learner optimiz-es the corresponding
$\Theta$ . During the bilevel learning, firstly the agent learns the memory
weight $\Theta^{*}$ about the inner problem. After that, the agent learns the
outer problem with respect to $\Phi$ . In this process, we apply the cross-
entropy loss as objec-tive function for the inner and outer problems
respectively.

####  2.2.2 First Order Approximation

Generally, the data comes gradually in non-stationary environment and the
concept drift mechanism will monitor the change in online manner. When the
concept drift occurs, the learner can adaptively adjust the model parameters
and weight the new and old knowledge in a non-stationary environment via
bilevel learning.
Specifically, assume that for an incoming training data $\beta_{train}^{t}$
reported as concept drift, the inner problem is settled by:

${\Theta_{i}}\leftarrow{\Theta_{i}}-\mu{\nabla_{{\Theta_{i}}}}{\cal
L}({\Theta_{i}},\beta_{train}^{t};\Phi)where{\Theta_{0}}\leftarrow\Phi$ (5)

After receiving $\Theta^{*}$ via Eq. (5), the outer learning for the
parameters $\Phi*$ can be solved by the chain rule.

$\begin{array}[]{c}{\Phi_{t}}\leftarrow{\Phi_{t}}-\gamma{\nabla_{\Phi}}{\cal
L}({\Theta^{*}},{{\cal M}^{memry}})\\\
\leftarrow{\Phi_{t}}-\gamma\frac{{\partial{\Theta^{*}}}}{{\partial\Phi}}\cdot\frac{\partial}{{\partial{\Theta^{*}}}}{\cal
L}({\Theta^{*}},{{\cal M}^{memry}})\end{array}$ (6)

Note that solving the Eq. (6) is a cumbersome problem in real word scenario
be-cause of the Hessian vector product in the second term[10]. In order to
improve the efficiency of the computation, we apply first-order approximation
to simplify the Eq.(6) in this work[11, 12]. Thus, the outer learning is given
by interpolating only in the parameter space:

$\begin{array}[]{c}{\Phi_{t}}={\Phi_{t}}+\gamma({\Theta^{\prime}}-{\Phi_{t}})\\\
where{\Theta^{\prime}}={\Theta^{*}}-\mu{\nabla_{{\Theta^{*}}}}{\cal
L}({\Theta^{*}},{{\cal M}^{memory}})\end{array}$ (7)

We apply Eq.(7) to obtain a one-step look-ahead parameter $\Theta^{\prime}$
from $\Theta^{*}$ . After that, we can adjust $\Phi$ by linearly interpolate
between the current parameters $\Phi$ and $\Theta^{\prime}$ . It is noted that
we only maintain the parameters of the main model $\Phi$,i.e., once the
parameters $\Phi$ is obtained and then we discard it after every outer update.
In this process, the inner optimization should be carried out via tiny
experience memory[13].

####  2.2.3 Bilevel Online Deep Learning Algorithm

In this section, we show that our BODL algorithm can effectively learn in non-
stationary environment by an online manner.
Our proposed BODL algorithm is shown in Algorithm 1.

Algorithm 1 Bilevel Online Deep Learning algorithm(BODL)

Input:Discounting coefficient $\eta\in(0,+\infty)$ ; Learning Rates:
$\mu$,$\gamma$ ,

Require:Memory management strategy for ${\cal M}^{memry}$

Initialize: $F(x)=DNN$ with $N+1$ hidden
layers;$\omega_{n}^{t}=\frac{1}{{N+1}},\forall n=0,...,N;\Phi;$

${\cal M}^{memry}\leftarrow\Phi$

for $t\leftarrow 1$ to $T$ do

Receive instance: $x_{t}$

Predict ${\hat{y}_{t}}=F(x)=\sum\limits_{n=0}^{N}{{\omega_{n}}}{f_{n}}$ as
Eq.(1)

Reveal ground truth $y_{t}$ and Update $\omega_{n}^{t}+1$ according to Eq.(2)

Concept Drift Detection

if concept drift is True, then

Update network via bilevel optimization

else

Update network via single backpropagation

end if

Update ${\cal M}^{memry}$ via Reservoir Sample

end for

In BODL algorithm, firstly we present an online ensemble framework that at-
tempts to dynamically weight the different depth classifiers and the base
classifier’s weights for each hidden layer are update based on the exponential
gradient descent algorithm in an online manner. In particular, we impose the
similar constraint be-tween the shallower and the deeper layer’s features,
which would be beneficial to generate the favorable feature representations
and improve the performance of the convergence.
In addition, consider that the data probability distribution would change in
real-world scenarios. Thus, a concept drift detection mechanism is used to
monitor the data changes according to the error rate of classifier. Once the
drift is detected, the learner would update the model parameters via bilevel
optimization. Thus, the learner would effectively prevent the large drift and
alleviate the catastrophic forgetting.

##  3 Experiments

In this section, we evaluate the baselines and our proposed BODL algorithm on
vari-ous stationary and non-stationary datasets. We report and analysis the
experimental results in detail.

####  3.0.1 Experiment Setup

We use the neural network architecture with 15 hidden layers of 30 units with
ReLU nonlinearities. In all experiments, the entire network parameters are
updated by Ad-am optimizer with a learning rate of 0.01. When the drift is
detected, the model would adaptively learn the parameters via the tiny memory
budge and this process is achieved using the bilevel optimization strategy. It
is well worth note that we apply a test-then-train strategy for evaluating the
learning algorithms to cast this as a classifi-cation task.
We compare against with several state-of-the-art baselines: Perceptron, the
Re-laxed Online Maximum Margin(ROMMA)[14], OGD[15], the recently proposed Soft
Confidence Weighted algorithms(SCW) [16], the Adaptive Regularization of
Weight Vectors(AROW) [17], the Confidence-Weighted (CW) learning
algorithm[19]. Here, the BODL-Base algorithm is regarded as an online learning
approach without the bilevel optimization strategy.

####  3.0.2 Datasets

The learning performance of BODL algorithm is numerically validated on
stationary and non-stationary data, but evolving data stream usually
characterize non-stationary properties in real-word task. Thus, in our
experiments, we select three non-stationary datasets and two stationary
datasets for experimental comparison. Here, the datasets are obtained from UCI
repositories and the properties are shown in de-tails in Table1.

Table 1: Batch Datasets Properties. Dataset | Size | Features | Type
---|---|---|---
MNINST | 70000 | 786 | Stationary
Magic | 19020 | 10 | Stationary
PIMA | 768 | 8 | Non-stationary
Weather | 18140 | 8 | Non-stationary
KDDCUP | 1036241 | 127 | Non-stationary

####  3.0.3 Experimental Results

In this section, the experimental comparative results of all baselines and the
proposed BODL algorithm with four different metric criteria: average accuracy,
average preci-sion, F1-Score and recall-score are reported in Table 2. In
additional, in order to study the contribution of each component, a complete
ablation studies are conducted in our work where BODL-2: the model is trained
using the bilevel learning and the simi-lar constrain, BODL-1: the model is
trained using the similar constrain alone, BODL-Base: the model is trained
without the bilevel learning and the similar constrain.

Table 2: Numerical results of different algorithms on different datasets. Method | Average Accuracy
---|---
MNIST | Magic | PIMA | Weather | KDDCUP
BODL-2 | 92.00% | 78.73% | 74.36% | 74.90% | 99.68%
BODL-1 | 91.99% | 78.49% | 73.84% | 73.28% | 99.44%
BODL-Base | 90.80% | 78.31% | 71.69% | 72.34% | 99.35%
Perceptron | 84.77% | 70.60% | 64.45% | 65.85% | 99.31%
ROMMA | 83.22% | 66.67% | 64.45% | 65.63% | 99.34%
OGD | 90.10% | 78.72% | 72.78% | 72.70% | 99.61%
SCW | 88.98% | 78.64% | 70.31% | 76.12% | 99.75%
AROW | 89.04% | 78.71% | 72.14% | 75.15% | 99.58%
CW | 86.88% | 67.90% | 63.41% | 36.81% | 99.62%
PA | 85.68% | 70.13% | 66.41% | 65.74% | 99.41%
Method | Average precision
MNIST | Magic | PIMA | Weather | KDDCUP
BODL-2 | 91.91% | 74.65% | 54.83% | 77.35% | 98.55%
BODL-1 | 91.89% | 73.96% | 54.38% | 75.76% | 97.46%
BODL-Base | 90.70% | 73.80% | 51.88% | 76.06% | 96.99%
Perceptron | 84.61% | 67.77% | 64.03% | 60.78% | 98.96%
ROMMA | 82.99% | 64.16% | 63.74% | 60.69% | 99.08%
OGD | 89.99% | 77.66% | 71.77% | 67.91% | 99.35%
SCW | 88.83% | 76.75% | 69.18% | 74.90% | 99.55%
AROW | 88.92% | 77.62% | 70.84% | 71.13% | 99.31%
CW | 86.70% | 64.75% | 62.55% | 53.55% | 99.56%
PA | 85.45% | 67.19% | 65.06% | 59.95% | 99.01%
Method | F1-score
MNIST | Magic | PIMA | Weather | KDDCUP
BODL-2 | 91.97% | 65.81% | 60.83% | 82.62% | 99.21%
BODL-1 | 91.97% | 65.73% | 63.30% | 81.80% | 98.61%
BODL-Base | 90.78% | 65.70% | 59.66% | 81.69% | 98.38%
Perceptron | 84.78% | 70.61% | 65.27% | 66.07% | 99.31%
ROMMA | 83.21% | 67.05% | 65.27% | 65.95% | 99.33%
OGD | 90.08% | 78.02% | 73.39% | 71.04% | 99.61%
SCW | 88.97% | 78.41% | 70.96% | 77.53% | 99.75%
AROW | 88.98% | 78.16% | 72.73% | 74.28% | 99.66%
CW | 86.87% | 67.86% | 64.24% | 29.00% | 99.67%
PA | 85.66% | 70.08% | 67.12% | 65.58% | 99.41%

The experiment results show that our BODL-2 algorithm enjoys competitive per-
formance on different datasets implementing different evaluation criteria.
BODL-2 is slightly better than BODL-1 with the help of bilevel learning since
it can alleviate the catastrophic forget when the concept drift occurs. BODL-
Base have lower accuracy than BODL-1, which means the similar constrain would
be beneficial to generate the favorable feature representations.
Compared to the state-of-the-art methods, we can draw several conclusions. In
terms of average accuracy, first but not surprise, traditional online learning
tech-niques, such as Perceptron and CW, achieve relatively poor performance on
almost all datasets. Next, we also note that the algorithms, such as OGD,
could obtain relatively competitive numerical results on MNIST datasets.
However, lacked the ability to further explore the power of depth or
adaptively adjust the model parameters when concept drift occurs, so they
receive poor performance on weather and PIMA da-taset. SCW and AROW achieve
favorable accuracy in concept drift datasets such as weather and KDDCUP, but
they product poor results in PIMA dataset which features highly imbalance and
non-stationary. In contrary, our BODL-2 algorithm can exploit the different-
level favorable feature representation base on the deep learning frame-work,
besides, when the concept drift is observed, the learner can adaptively adjust
the model parameters via bilevel optimization strategy based on memory replay
and then encourage positive transfer and prevent the large drift.
In additional, BODL-2 algorithm outperform all other approaches on Magic,
MNIST and KDDCUP dataset under accuracy evaluation criteria. It is noted that
our method can produce good performance from highly imbalance data streams
with concept drift, such as PIMA. Only 1.22% less than the highest one in
terms of accu-racy on weather dataset but achieve highest results under the
average precision, F1-Score and recall-score evaluation criteria and so on. To
conclude, the experimental results demonstrate that our BODL-2 algorithm is a
promising online learning ap-proach comparing to the state-of-the-art online
methods.

##  4 Related Works

Recent years we have witnessed enormous success in the deep neural network.
Com-pared to traditional off-line learning, online learning is more suitable
in many real-word tasks. Online learning algorithms represents a class of
scalable algorithms which are devised to optimize the models incrementally
where the data instance comes gradually. Perceptron based on maximum-margin
classification is the earliest online learning algorithm, which is primarily
developed to learn linear models. However, the class of perceptron algorithm
is fragile to the samples that are linearly inseparable. Thus, perceptron
algorithm with the kernel functions are developed [18], which give a solution
to online learning techniques with nonlinear models. While such approaches are
able to solve the non-linear classification, determining the type and number
of kernel function is an open challenge. Moreover, these approaches are not
explicitly built to extract the different-depth feature representations for
the data instances. Base on this fact, Sahoo et al et al present an online
algorithm with different depth network for evolving data streams[4]. However,
they neglect the intractable problem of catastrophic forgetting, or cannot
cope with the non-stationary environment very well. Recently, there are some
specific algorithms handle for concept drift in non-stationary environment.
These methods concentrate on incrementally update the model as long as the
data instance arrives in a stream, such as dynamic combination model; the
online Gradient Descent Algorithm(OGD)[15]; the relaxed online maxi-mum margin
algorithm and its aggressive version aROMMA, ROMMA, and aROM-MA[14]; the
Adaptive Regularization of Weight Vectors(aROW) [17]; the Confi-dence-Weighted
(CW) learning algorithm[19]; The recently proposed Soft Confidence Weighted
algorithms(SCW) [16]. However, these methods characterize the constant
updating of their models, which would make the model evolve in an extremely
regu-lar manner regardless of the concept drift.

##  5 Conclusion and future work

Concept drift is an inevitable problem with learning from evolving data
streams, which must be handled for data instances to be practically useful. In
this work, we proposed a novel Bilevel Online Deep Learning (BODL) framework
to learn in non-stationary environment in an online manner. BODL creates an
ensemble classifier using the different depth feature representations, where
the important weights of each classifier would be updated by online
exponential gradient descent strategy. In order to make the deeper layers
converge faster and generate the favorable feature repre-sentation, we impose
the similar constraint between the shallower and the deeper layer’s features.
Besides, a concept drift detected mechanism is devised according to the error
rate of classifier. When the concept drift is detected, our BODL algorithm can
adaptively update the model parameters via bilevel optimization based on tiny
episodic memory and then prevent the large drift and encourage positive
transfer.
At last, we validated the proposed BODL algorithm through extensive
experiments on various stationary and non-stationary datasets and the
competitive numerical results show our BODL algorithm is a promising online
learning approach.
In the future work, we would consider the online learning problem for class
incre-mental learning. Besides, in order to obtain the more favorable feature
representa-tion, we also consider incorporating the recently proposed self-
supervised learning and data augment methods.

##  6 Acknowledgements

This work was supported by the Science Foundation of China University of
Petroleum, Beijing(No. 2462020YXZZ023)

## References

  * [1] Y. Bengio, A. Courville, P. Vincent, Representation learning: A review and new perspectives, IEEE transactions on pattern analysis and machine intelligence 35 (8) (2013) 1798–1828.
  * [2] T. Chen, I. Goodfellow, J. Shlens, Net2net: Accelerating learning via knowledge transfer, arXiv preprint arXiv:1511.05641 (2015).
  * [3] N. Cesa-Bianchi, G. Lugosi, Prediction, learning, and games, Cambridge university press, 2006.
  * [4] D. SAHOO, H. Q. PHAM, J. LU, S. C. HOI, Online deep learning: Learning deep neural networks on the fly.(2018), in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence IJCAI 2018, July 13-19, Stockholm, pp. 2660–2666.
  * [5] S. C. Hoi, D. Sahoo, J. Lu, P. Zhao, Online learning: A comprehensive survey, arXiv e-prints (2018) arXiv–1802.
  * [6] J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, et al., Overcoming catastrophic forgetting in neural networks, Proceedings of the national academy of sciences 114 (13) (2017) 3521–3526.
  * [7] A. Chaudhry, P. K. Dokania, T. Ajanthan, P. H. Torr, Riemannian walk for incremental learning: Understanding forgetting and intransigence, in: Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 532–547.
  * [8] S. Jenni, P. Favaro, Deep bilevel learning, in: Proceedings of the European conference on computer vision (ECCV), 2018, pp. 618–633.
  * [9] D. Kifer, S. Ben-David, J. Gehrke, Detecting change in data streams, in: VLDB, Vol. 4, Toronto, Canada, 2004, pp. 180–191.
  * [10] Q. Pham, D. Sahoo, C. Liu, S. C. Hoi, Bilevel continual learning, arXiv preprint arXiv:2007.15553 (2020).
  * [11] A. Nichol, J. Achiam, J. Schulman, On first-order meta-learning algorithms, arXiv preprint arXiv:1803.02999 (2018).
  * [12] M. R. Zhang, J. Lucas, G. Hinton, J. Ba, Lookahead optimizer: k steps forward, 1 step back, arXiv preprint arXiv:1907.08610 (2019).
  * [13] A. Chaudhry, M. Rohrbach, M. Elhoseiny, T. Ajanthan, P. K. Dokania, P. H. Torr, M. Ranzato, Continual learning with tiny episodic memories (2019).
  * [14] Y. Li, P. M. Long, The relaxed online maximum margin algorithm, Machine Learning 46 (1) (2002) 361–387.
  * [15] M. Zinkevich, Online convex programming and generalized infinitesimal gradient ascent, in: Proceedings of the 20th international conference on machine learning (icml-03), 2003, pp. 928–936.
  * [16] S. C. Hoi, J. Wang, P. Zhao, Exact soft confidence-weighted learning, in: ICML, 2012\.
  * [17] K. Crammer, A. Kulesza, M. Dredze, Adaptive regularization of weight vectors, Machine learning 91 (2) (2013) 155–187.
  * [18] J. Kivinen, A. J. Smola, R. C. Williamson, Online learning with kernels, IEEE transactions on signal processing 52 (8) (2004) 2165–2176.
  * [19] K. Crammer, M. Dredze, F. Pereira, Exact convex confidence-weighted learning, in: Advances in Neural Information Processing Systems, Citeseer, 2008, pp. 345–352.


# Patching Neural Barrier Functions Using Hamilton-Jacobi Reachability

Sander Tonkens, Alex Toofanian, Zhizhen Qin, Sicun Gao, and Sylvia Herbert The
authors are with University of California, San Diego {sander, atoofanian,
zhq005, sicung<EMAIL_ADDRESS>
###### Abstract

Learning-based control algorithms have led to major advances in robotics at
the cost of decreased safety guarantees. Recently, neural networks have also
been used to characterize safety through the use of barrier functions for
complex nonlinear systems. Learned barrier functions approximately encode and
enforce a desired safety constraint through a value function, but do not
provide any formal guarantees. In this paper, we propose a local dynamic
programming (DP) based approach to “patch” an almost-safe learned barrier at
potentially unsafe points in the state space. This algorithm, HJ-Patch,
obtains a novel barrier that provides formal safety guarantees, yet retains
the global structure of the learned barrier. Our local DP based reachability
algorithm, HJ-Patch, updates the barrier function “minimally” at points that
both (a) neighbor the barrier safety boundary and (b) do not satisfy the
safety condition. We view this as a key step to bridging the gap between
learning-based barrier functions and Hamilton-Jacobi reachability analysis,
providing a framework for further integration of these approaches. We
demonstrate that for well-trained barriers we reduce the computational load by
2 orders of magnitude with respect to standard DP-based reachability, and
demonstrate scalability to a 6-dimensional system, which is at the limit of
standard DP-based reachability.

##  I Introduction

Robotics has seen major advances in the past decade in several areas,
including manipulation [1] and locomotion [2] in unstructured environments.
Machine learning and improvements in simulation engines have been key enablers
in this progress [3]. Namely, machine learning has enabled learning and
representation of the complex interaction between robots and their environment
implicitly. However, progress in domains where failures have major
consequences has been hampered by a need for quantitative safety assurances
[4]. Obtaining such strict assurances is very challenging when including
learning-based components in the autonomy stack [5]. A popular method to
guarantee safety for a task is through the use of value functions that encode
and enforce safety, for example (control) barrier functions (CBFs) [6].
Critically, this enables enforcing safety through an independent module in the
autonomy stack. Concretely, fixed-policy barrier functions (BFs) can be used
to provide guaranteed maximum error bounds around a planned path to validate
whether a planned path is safe _post hoc_. CBFs can be used to minimally
modify a safety-agnostic or otherwise unsafe control policy, using an
optimization-based safety filter, to ensure a trajectory remains safe [7].

For many realistic autonomy settings, suitable (safe, yet not too
conservative) value functions cannot be derived analytically. In the
following, we use value functions to denote the wide class of safety functions
that encode and enforce set invariance, including BFs and CBFs. Numerical
methods for synthesizing barrier functions include solving a partial
differential equation (PDE) through spatial discretization [8] and sum-of-
squares (SoS) techniques [9]; These both scale poorly to higher dimensional
systems. A popular recent line of work proposes leveraging neural networks to
learn approximate value functions [10, 11, 12]. However, these do not readily
come with any formal guarantees.

Figure 1: HJ-Patch iteratively (above) modifies an almost-barrier (unsafe
region in red), e.g., a learned barrier, at states near the 0-level set
(active set, blue) until convergence. This set represents the potentially
unsafe boundary states at that iteration. For each iteration (below, zoomed),
we compute the updated value (center) for the states in the active set. Next,
we identify the new active set (right) by adding states that neighbor (dark
blue) the value decreasing states and discard states far from the boundary
(light blue). See Algorithm 1 for details.

Independently, neural network verification techniques have been developed to
check whether a network satisfies certain input-output properties. We refer to
[13] for an overview of verification methods. In the context of verifying
safety (for the learned value functions) these methods typically employ
robustness analysis [14] to provide point-wise, i.e. single time-step,
guarantees [15]. However, as they rely on over-approximations or sampling,
they can generally not be used to satisfy safety properties, such as forward
invariance, for the entire system.

In this work, we propose taking advantage of the scalability of neural value
function techniques to generate an initial high-dimensional approximate value
function. We then selectively and locally refine this value function using a
formal safety analysis technique that leverages spatially discretized local
dynamic programming. Critically, we update only potentially unsafe regions
around the value function’s safety boundary. Upon convergence of our proposed
iterative algorithm, we obtain a set that is guaranteed to be forward
invariant and a value function that encodes and enforces safety.

Related work: Hamilton-Jacobi (HJ) reachability analysis, a formal method, can
be used to compute the viability kernel, i.e. the largest feasible control
invariant set for a given initial constraint set. For the infinite-horizon
safety problems considered in this paper, HJ reachability uses dynamic
programming (DP) to solve a value function whose 0-superlevel set denotes the
viability kernel, and whose gradients prescribe the direction of safe control
actions [16]. While constructive, DP methods rely on spatial discretization of
the state space, and hence scale exponentially with the dimensionality of the
system. In practice, direct use of this method is tractable only for systems
up to 5D offline, and 2D-4D online (depending on the application) [17]. To
circumvent the computational complexity (both memory and compute) of DP,
learning-inspired methods have been introduced to approximately characterize
the DP solution. However, directly learning HJ value functions by leveraging
neural networks for supervised approximate DP does not provide hard guarantees
[18]. Another approach, which leverages the similarity of HJ reachability and
reinforcement learning does not necessarily encode safety [19].

CBFs are another popular approach for safe control of autonomous systems. If a
valid CBF for the system and environment can be found, it can be used as a
safety filter to enforce safety online via a point-wise inequality constraint
on the input through the derivative of the CBF [7]. Crucially, for control-
affine systems, this inequality constraint is linear in the control input,
turning the safety filter optimization problem into a quadratic program (QP);
this can be solved efficiently, enabling online implementation. However, for
general complex systems with control bounds and disturbances, analytical
closed-form functions that define a CBF do not exist or are highly non-trivial
to synthesize. As such, recent work has leveraged learning-based function
approximations to characterize CBFs, e.g, using safe expert trajectories [11]
or labeled state-action pair samples [20, 21]. Imitation learning-inspired
approaches can lead to undesired and/or overly conservative behavior in
practice, whereas sampling-based approaches do not provide strict safety
assurances.

For dynamics with a fixed policy, recent work has focused on learning
certificate functions [22]; these are barrier functions (BFs) in the context
of set invariance. Notably, recent work has paired learned BFs with a neural
network verification technique to provide point-wise safety guarantees for
states on the boundary of the safe set [15]. However, as they rely on sampling
and do not guarantee safety of every boundary state, the BF is not guaranteed
to be safe and we cannot ensure that trajectories will remain safe
indefinitely.

Recently, Tonkens and Herbert [23] showed that warm-starting (i.e.
initializing) DP with an approximate value function will lead to a safer value
function at each iteration and converge to a guaranteed safe value function.
However, this work updates the entire state-space to converge to the locally
(i.e. initialization dependent) optimal value function with respect to an _a
priori_ known constraint function $\ell$. Its 0-superlevel set corresponds to
the locally largest invariant set of the constraint set
${\mathcal{C}_{\ell}}$. As it converges to the optimal value function, a good
initialization only partially aids in convergence. Methods that recover the
optimal value function greatly inhibit scalability.

Locally updating a DP-based value function has been proposed by Bajcsy et al.
[24] in the context of updating the safe region when new sensor measurements
become available. However, the method is applicable solely to expanding the
safe set, and it similarly finds the locally largest invariant set (and
optimal value function) for a known constraint set, again limiting
scalability. In summary, while several methods have proposed techniques that
reduce the computational effort to find a valid value function using an
appropriate initialization, such as a learned barrier, these methods only
provide limited scalability advantages and do not leverage the quality of the
approximately learned value function (which often roughly characterizes an
invariant set) to its full extent.

Contributions: This work proposes locally modifying an approximate learned
value function to obtain a valid value function. We present an algorithm, HJ-
Patch, that is guaranteed to find the largest containing invariant set with a
very limited (comparatively) number of total queries of the recursive DP-based
reachability computation. Our experiments demonstrate $(i)$ the necessity of
refining learned value functions and $(ii)$ the computational benefit
(yielding $10-100$x speedup) of only selectively updating potentially unsafe
states around the boundary of the learned barrier. Specifically, we deploy our
algorithm on a 4 and 6-dimensional quadrotor model, warmstarting HJ-Patch with
the learned barrier and deploying these as a CBF within a safety filter.

Organization: We proceed with a brief overview of (control) barrier functions
and learning almost-barrier functions in Section II. Next, we present HJ-
Patch, an algorithm for minimally updating approximate value functions and its
theoretical guarantees in Section III. We present case studies in simulation
in Section IV and conclude with the merits of our approach and avenues of
future work in Section V.

##  II Preliminaries

We consider a dynamical system $\dot{x}=f(x,u)$, with state
$x\in\mathcal{X}\subseteq\mathbb{R}^{n}$, input
$u\in\mathcal{U}\subseteq\mathbb{R}^{m}$, and function
$f:\mathcal{X}\times\mathcal{U}\to\mathbb{R}^{n}$ assumed to be Lipschitz
continuous on its domain. Given a fixed continuous policy $u=\pi(x)$ that is
locally Lipschitz in $x$, we consider the nonlinear closed-loop system
$\dot{x}=f_{\pi}(x)$. We define system trajectories at time $t$ starting at
$x_{0},t_{0}$ under control signal $u(\cdot)$ by
$\xi_{x_{0},t_{0}}^{u(\cdot)}(t)$. The Lipschitz continuity of $f$ (and $\pi$)
provides a sufficient condition on the existence and uniqueness of solutions
to the system.

A set $\mathcal{C}$ with closed-loop dynamics is considered forward invariant
if for any trajectory starting at $x_{0}\in\mathcal{C}$,
$\xi_{x_{0},t_{0}}^{\pi}(t)\in\mathcal{C}$ indefinitely. By extension, a set
$\mathcal{C}$ is considered control invariant if for any trajectory starting
at $x_{0}$ there exists an admissible control signal that the keeps the system
inside $\mathcal{C}$, i.e. $\exists u(\cdot)\in\mathcal{U}$ s.t.
$\xi_{x_{0},t_{0}}^{u(\cdot)}(t)\in\mathcal{C}$. The largest (control)
invariant subset of a given set $\mathcal{C}$ is referred to as the viability
kernel, denoted by $\bar{\mathcal{C}}$.

Additionally, we define safety using a real-valued bounded Lipschitz
continuous value function $h:\mathcal{X}\to\mathbb{R}$. Common value functions
include HJ reachability value functions, barrier functions, and control
barrier functions. We define the value function in this work such that its
0-superlevel set ${\mathcal{C}_{h}}=\\{x\mid h(x)\geq
0\\}\subseteq\mathcal{X}$ is the set of states in which we wish to stay, i.e.
the safe set. For example, for avoiding a set of failure states $\mathcal{L}$,
we aim to synthesize $h$ such that (1)
${\mathcal{C}_{h}}\cap\mathcal{L}=\emptyset$ and (2) ${\mathcal{C}_{h}}$ is
invariant.

###  II-A Control Barrier Functions

In the following, we define barrier functions for fixed policy systems and
control barrier functions for controlled systems.

######  Definition 1 (Barrier Function).

Let ${\mathcal{C}_{h}}$ denote a 0-superlevel set of a continuously
differentiable value function $h:\mathcal{X}\to\mathbb{R}$, then $h$ is a
barrier function for $f_{\pi}(x)$ if there exists an extended class
$\mathcal{K}$ function $\alpha$ such that for all $x\in{\mathcal{C}_{h}}$:

$\dot{h}(x):=L_{f_{\pi}}h(x)\geq-\alpha(h(x)),$ (1)

where $L$ is the lie derivative. A barrier function defines a forward
invariant set ${\mathcal{C}_{h}}$. It can be used to certify safety.

######  Definition 2 (Control Barrier Function).

Let ${\mathcal{C}_{h}}$ denote a 0-superlevel set of a continuously
differentiable value function $h:\mathcal{X}\to\mathbb{R}$, then $h$ is a
control barrier function for $f(x,u)$ if there exists an extended class
$\mathcal{K}$ function $\alpha$ such that:

$\sup_{u\in\mathcal{U}}\dot{h}(x):=\sup_{u\in\mathcal{U}}L_{f}h(x)\geq-\alpha(h(x)).$
(2)

A control barrier function defines a control invariant set
${\mathcal{C}_{h}}$. Specifically, any control that satisfies the inequality
in (2) will result in the system remaining in the set ${\mathcal{C}_{h}}$
(indefinitely). CBFs, in contrast to BFs, are typically defined with respect
to a given environment, e.g., a set of obstacles. Online, at each time step, a
nominal policy is then passed through a filter that solves the following
optimization problem:

$\begin{split}u^{*}(x)=\>\arg\min\limits_{u}\quad&\lVert
u-\hat{\pi}(x)\rVert_{R}^{2}\\\ \text{subject
to}\quad&\dot{h}(x)+\alpha(h(x))\ \geq 0\\\ &u\in\mathcal{U},\end{split}$ (3)

where $\hat{\pi}$ is the nominal, safety-agnostic policy. The obtained control
$u^{*}$ is guaranteed to retain safety while minimally modifying the nominal
policy.

###  II-B Learned Almost-Barrier Functions

Learning-based methods have recently been introduced for using expressive
function approximators such as neural networks to represent barrier functions
to handle systems with nonlinearity and uncertainty [10, 11]. Because
sampling-based learning methods are inherently approximate, the notion of
almost-barrier functions have been defined. It is a relaxation of the standard
notion of barrier functions by allowing small regions on the safety barrier to
be uncertified. Almost-barrier functions can be parameterized by an explicit
numerical tolerance bound $\varepsilon>0$, referred to as
$\varepsilon$-barrier functions, defined as:

######  Definition 1 ($\varepsilon$-Barrier Functions [15]).

Let $h$ be a value function over the state space $\mathcal{X}$ of the system
$f_{\pi}(x)$, and denote it’s 0-level set as
$\partial{\mathcal{C}_{h}}=\\{x\in\mathcal{X}:h(x)=0\\}$, and let
$\varepsilon\in[0,1)$ be a parameter. Suppose there exists a measurable
$\mathcal{S}\subseteq\mathcal{X}$ and the ratio of the areas between
$\mathcal{S}\cap\partial{\mathcal{C}_{h}}$ and $\partial{\mathcal{C}_{h}}$ is
less than $\varepsilon$. Namely,
$A(\mathcal{S}\cap\partial{\mathcal{C}_{h}})/A(\partial{\mathcal{C}_{h}})\leq\varepsilon$,
where $A(B)=\iint_{B}\mathrm{d}A$ indicates surface areas. We say $h$ is an
almost $\varepsilon$-barrier function with respect to safe state set
$X_{s}\subseteq\mathcal{X}$ and unsafe state set $X_{u}\subseteq\mathcal{X}$,
if $h(x)\geq 0$ for all $x_{s}\in X_{s}$, $h(x)<0$ for all $x_{u}\in X_{u}$,
and $L_{f}h(x)>0$ for all
$x\in{\mathcal{S}^{c}}\cap\partial{\mathcal{C}_{h}}$, where
$\mathcal{S}^{c}=X\setminus\mathcal{S}$.

In other words, an almost-barrier function satisfies the standard barrier
function conditions Eq.(1) or (2), almost everywhere other than in the region
of $\mathcal{S}\cap\partial{\mathcal{C}_{h}}$. Clearly, this relaxed notion of
barrier functions no longer implies safety in the standard sense. There is now
a “leaking” area of the 0-level set (i.e.
$\mathcal{S}\cap\partial{\mathcal{C}_{h}}$) from which the system may cross
over to the unsafe area $X_{u}$.

This relaxation of the original definition enables us to use sampling-based
methods train a neural network representation of almost-barrier functions.
Some works [25] additionally propose a falsifier accompanying the learning to
find counterfactuals. More generally, sampling-based methods rely on expert
policies [11], learn a policy independently [15], or jointly learn a policy
with the barrier using actor-critic methods [20]. In this work, we
independently learn a policy and find a neural almost-barrier and its
potentially unsafe region with the 3 following steps:

####  II-B1 Training control policy and sampling safe and unsafe states

We can use standard policy optimization algorithms such as soft actor-critic
(SAC) [26] to learn a control policy $\pi:\mathcal{X}\rightarrow\mathcal{U}$
using a reward function that encourages goal reaching and penalizes constraint
violations. After training concludes, we collect safe and unsafe samples based
on whether sampled trajectories reach the goal or violate the constraints.

####  II-B2 Training neural barriers

After labeling the safe and unsafe states, we train the barrier function using
the following loss function (see also [15]):

$\ell(\theta)=w_{s}\frac{1}{N_{s}}\sum_{i=0}^{N_{s}}\phi(-h(x_{s}^{(i)}))+w_{u}\frac{1}{N_{u}}\sum_{i=0}^{N_{u}}\phi(h(x_{u}^{(i)}))\\\
+w_{l}\frac{1}{N_{s}}\sum_{i=0}^{N_{s}}\phi(-L_{f}h(x_{s}^{(i)})-\gamma
h(x_{s}^{(i)})))$ (4)

where $\phi(x)=\max(x,0)$ and $N_{(s,u)}=|X_{(s,u)}|$. Positive parameters
$w_{s},w_{u},w_{l},\gamma$ balance the weights of the different components of
the loss. $\ell(\theta)$ reaches a global minimum $\ell(\theta)=0$ if and only
if the barrier conditions in 1 are completely satisfied at each training
sample.

####  II-B3 Evaluating neural barrier

The evaluation process identifies “leaky” areas on the boundary through a
certification process to bound the Lie derivative
$L_{f}h(x)=\sum_{i=1}^{n}\frac{\partial h}{\partial x_{i}}f_{i}(x,u)$. For a
small local neighborhood around state $x$, the term $\frac{\partial
h}{\partial x_{i}}$ is bounded by using neural network analysis tools, and the
term $f_{i}(x,u)$ is bounded by estimating the Jacobian of the dynamics
through sampling the dynamics of states that are close to $x$ in each
dimension. This procedure enables us to have certifiable upper and lower
bounds in the local neighborhood of $x$. In particular, if the lower bound is
greater than $0$, this neighborhood region is certifiably safe for the current
value function. We denote the set of such safe neighborhoods by $C$.

In many cases, the control policy and neural value function may be suboptimal
(i.e. potentially unsafe) in regions of the state space. Obtaining a neural
barrier with no leaky areas is a challenging task. Moreover, even if we
retrain the barrier with additional samples in leaky areas, the updated neural
network may produce new leaky areas. Therefore, it is crucial to be able to
quantify where the potential “leaky” areas are. A readily available almost-
barrier with potentially unsafe regions identified motivates the need to
locally patch these “leaky” areas without modifying the global structure of
the function. As detailed in Section III, we propose to do this using local
DP-based reachability analysis.

###  II-C Hamilton-Jacobi Reachability

Assume we are given a set ${\mathcal{C}_{h}}\subseteq\mathcal{X}$
characterized as the 0-superlevel set of a cost function $h$. We define the
associated HJ reachability value function:

$V_{h}(x,t)=\max_{u\in\mathcal{U}_{[t,0]}}\min_{s\in[t,0]}h(\xi_{x,t}^{u}(s)),$
(5)

which finds a control sequence $u(\cdot)$ that maximizes the minimum value of
$h$ obtained over its trajectory $\xi$. By definition, (as $t\to-\infty$), the
0-superlevel set of $V_{h}^{*}(x)=\lim_{t\to-\infty}V_{h}(x,t)$,
${\mathcal{C}^{*}_{h}}$, characterizes the infinite-time viability kernel of
${\mathcal{C}_{h}}$, i.e. ${\bar{\mathcal{C}}_{h}}={\mathcal{C}^{*}_{h}}$
[27]. For the purposes of this work, we are only interested in persistent
safety and hence drop the explicit time dependence.

In practice, we spatially discretize the state space and solve for the value
function $V_{h}$ recursively using dynamic programming on this grid [28]:

$\begin{split}{V^{(k+1)}}(x)={V^{(k)}}(x)+{\Delta^{(k)}}\min\\{0,\max_{u\in\mathcal{U}}L_{f}{V^{(k)}}(x)\\},\end{split}$
(6)

where we use superscript $(k)$ to denote the iteration of the algorithm. In
practice, ${\Delta^{(k)}}$ is dynamically updated based on the size of the
Hamiltonian, $\mathcal{H}=\max_{u\in\mathcal{U}}L_{f}{V^{(k)}}(x)$. By
extension, for closed-loop dynamics $f_{\pi}(x)$, we consider
$\mathcal{U}=\pi(x)$ to be a point-value.

HJ reachability can be used to generate the largest containing (control)
invariant set of a set defined by some cost function. Hence, given an almost-
barrier function, HJ reachability can be initialized with this cost function
such that the resulting function’s 0-superlevel set is invariant. In previous
work [23], we presented a formulation to refine CBFs, but we considered the
general case of both conservative or unsafe CBFs. In this work, we solely
consider (potentially) unsafe barrier functions, as we limit ourselves to
finding the largest control invariant subset for the value function. As we
will present in Section III, this assumption allows for significant
improvement in computational speed by leveraging local updating, which we
exploit in our algorithm introduced below.

##  III Locally Updating the Barrier Boundary

In this section, we present HJ-Patch (Algorithm 1), an efficient algorithm to
obtain the viability kernel of a given set by minimally and locally updating
the corresponding spatially-discretized value function. Specifically, our
algorithm obtains the viability kernel of the almost-barrier and associated
value function by updating a very limited cumulative number of grid cells. As
highlighted in Section IV, for reasonably accurate almost-barrier functions,
our proposed algorithm provides significant speedups, allowing to scale formal
safety analysis by up to $2$ orders of magnitude. In this section we denote
$x^{d}$ as the discretized grid states. Additionally, we refer to the value
function obtained when updating over the entire state space with Eq. 6 as the
global HJ reachability value function.

###  III-A Algorithm overview

Leveraging the structure of infinite-time HJ reachability problems, the
0-level set of the value function obtained with our proposed approximate
dynamic programming algorithm will correspond to the global HJ reachability’s
value function’s 0-level set, see Theorem 1 for details. A visual depiction of
the steps of Alg. 1 is provided in Figure 1, which we refer to in the step-by-
step description below. Our algorithm takes in an almost-barrier function
$h(x)$ and optionally a set of certified cells $C$, from e.g., neural network
verification methods, see Section II-B3. Then (1-3), we initialize the to-be-
updated grid cells (active cells) as the cells around the 0-level set of the
initial value function which are not certified to ${Q^{(0)}}$ (top left).
$\zeta$ is a user-specified threshold value for the size of the boundary of
interest around the 0-level set. At each iteration (5, bottom left), we
compute the lie derivative (for closed-loop systems) or the Hamiltonian (for
controlled systems) at these active cells ${Q^{(k)}}$ and update the value
function using the discrete-time HJ update equation (6) (bottom center). We
form the new temporary active set (6) as the states at which the values
decreased. Next (7, bottom right), we pad this active set with its neighbors,
and lastly discard any states far from ${\hat{V}^{(k+1)}}$’s 0-level set. We
repeat this procedure (8) until convergence. Upon termination (10, top right),
the 0-superlevel set of $\hat{V}^{*}$, ${\hat{\mathcal{C}}^{*}_{h}}$, is
invariant (or empty).

Algorithm 1 HJ-Patch

0: $h(x):$ Initial value function (almost-barrier) $C:$ Oracle-certified safe
cells (Optional)_// Active set is set of potentially unsafe states_

1: ${Q^{(0)}}\leftarrow\\{x^{d}\mid\lvert h(x^{d})\rvert\leq\zeta\\}$
$\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}\pgfsys@color@gray@stroke{0.4}\pgfsys@color<EMAIL_ADDRESS>_Initialize active set_

2: ${Q^{(0)}}\leftarrow{Q^{(0)}}\setminus C$
$\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}\pgfsys@color@gray@stroke{0.4}\pgfsys@color<EMAIL_ADDRESS>_Remove oracle-certified cells_

3: ${Q^{(k)}}\leftarrow{Q^{(0)}},~{}~{}{\hat{V}^{(k)}}\leftarrow h$ _//
Boundary is certified once ${Q^{(k)}}$ is empty_

4: while ${Q^{(k)}}$ is not empty do

5:
${\hat{V}^{(k+1)}}(x^{d})\leftarrow\text{Eq.~{}\eqref{eq:dp}}~{}\forall~{}x^{d}\in{Q^{(k)}}$_//
Value-decreasing states form updated active set_

6:
${Q^{(k+1)}}\leftarrow\\{x^{d}\mid{\hat{V}^{(k+1)}}<{\hat{V}^{(k)}},~{}\forall~{}x^{d}\in{Q^{(k)}}$
}_// Add neighboring cells to active set and exclude states far from
${\hat{V}^{(k+1)}}$’s 0-level set_

7:
${Q^{(k+1)}}\leftarrow\mathbf{pad}({Q^{(k+1)}})\cap\\{x^{d}\mid\lvert{\hat{V}^{(k+1)}}(x^{d})\rvert\leq\zeta\\}$

8:
${Q^{(k)}}\leftarrow{Q^{(k+1)}},~{}~{}{\hat{V}^{(k)}}\leftarrow{\hat{V}^{(k+1)}}$

9: end while

10: return ${\hat{V}^{(k)}}$
$\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}\pgfsys@color@gray@stroke{0.4}\pgfsys@color<EMAIL_ADDRESS>HJ-Patch’s converged barrier function_

###  III-B Theoretical guarantees

The theoretical guarantees underpinning our proposed algorithm, Alg. 1, hold
solely for the discretized states on the grid and an appropriate choice of
numerical solver parameters (e.g., terminal convergence threshold, finite
difference, and forward integration scheme). Standard HJ reachability [17] and
any other space-discretized schemes have the same properties. To highlight
this, we empirically demonstrate that the obtained (control) invariant set for
both standard HJ reachability and HJ-Patch recover an almost (control)
invariant set. The theory below generally holds solely at the discretized
states on the grid, $x^{d}$. Solving over a discretized grid is the standard
approach for HJ reachability [12], for details on discretization see [29].

We first demonstrate that Alg. 1 recovers an invariant set, if such a set
exists:

######  Lemma 1 (Algorithm 1 converges to a control-invariant set).

The 0-superlevel set of the value function $\hat{V}^{*}$,
${\hat{\mathcal{C}}^{*}_{h}}$, obtained upon termination of Alg. 1, is either
(1) (control) invariant for the discretized states $x^{d}$ or (2) is empty,
i.e. ${\hat{\mathcal{C}}^{*}_{h}}=\emptyset$, implying that either (a)
${\mathcal{C}_{h}}$ has no invariant subset or (b) the current resolution of
the grid does not admit an invariant subset.

###### Proof.

Without loss of generality, we consider $C=\emptyset$, i.e. no cells are
oracle-certified. In addition to Eq. (6) we have the following equation that
relates the current value function to the Lie derivative:

$\begin{split}L_{f}\hat{V}(x)=\langle\nabla\hat{V},f\rangle\approx\langle\delta^{p}_{\Delta}[\hat{V}],f\rangle,\end{split}$
(7)

with $\delta^{p}_{\Delta}[\hat{V}]$ a finite difference operator of order $p$,
which is a function of $\hat{V}(x^{d})$ and the values $\hat{V}$ of $p$
neighbors of $x^{d}$ in every dimension. We denote this set of grid states as
$x^{d,p}$. Hence, for a boundary cell at iteration $k$,
$L_{f}{\hat{V}^{(k)}}(x^{d})\neq L_{f}{\hat{V}^{(k-1)}}(x^{d})$ if and only if
${\hat{V}^{(k-1)}}(x^{d,p})\neq{\hat{V}^{(k-2)}}(x^{d,p})$. Therefore, when
including all $p$ neighbors in the march algorithm, we have
$L_{f}{\hat{V}^{(k)}}(x^{d})\neq L_{f}{\hat{V}^{(k-1)}}(x^{d})$ if and only if
$x^{d}\in{Q^{(k)}}$. Hence, a boundary cell $x^{d}\notin{Q^{(k)}}$, if and
only if $L_{f}{\hat{V}^{(k)}}(x^{d})\geq 0$. By extension,
${Q^{(k)}}=\emptyset$ implies $L_{f(x,u)}\hat{V}(x^{d})\geq 0~{}\forall
x^{d}\in\partial\hat{\mathcal{C}}=\\{x^{d}\mid\hat{V}(x^{d})=0\\}$. ∎

Essentially, we show that when the active set is empty, its associated
0-superlevel set is invariant. In particular, we show that when including all
neighbor cells that are used for calculating the spatial derivative of $V(x)$
in the march, i.e. the neighbors of active cells, the lie derivative of
boundary cells ${V^{(k)}}(x^{d})$ at iteration $k$ can be negative if and only
if $x^{d}$ is part of the active set at iteration $k$, $x\in{Q^{(k)}}$.

In addition to being an invariant set, we assert that
${\hat{\mathcal{C}}^{*}_{h}}$ is the viability kernel
${\bar{\mathcal{C}}_{h}}$ of the candidate set ${\mathcal{C}_{h}}$. To show
this, we first recall the following lemma from global warmstarting of HJ
reachability [30]. We drop the argument $(x)$ from the value functions for
readability.

######  Lemma 2 (Optimistic global warm-start HJ reachability recovers the
viability kernel [30]).

If we warmstart Eq. (6) with ${V^{(0)}}\geq V^{*}~{}\forall x$, then
${V^{(\infty)}}=V^{*}.$

In words, if HJ reachability is initialized optimistically (i.e. over-
approximates the safe set), the global analysis will converge to the value
function $V^{*}(x)$ associated with the viability kernel.

To extend this result to the local method described in this paper, we prove
the theorem below.

######  Theorem 1 (Alg. 1 recovers the viability kernel
${\bar{\mathcal{C}}_{h}}$ of the initial set ${\mathcal{C}_{h}}$).

Assume an optimistic intialization, i.e. ${\hat{V}^{(0)}}(x)\geq V^{*}(x)$.
Upon convergence, the computed set ${\hat{\mathcal{C}}^{*}_{h}}$ from Alg. 1
recovers the viability kernel ${\bar{\mathcal{C}}_{h}}$ of the initial set
${\mathcal{C}_{h}}$ defined by the almost-barrier function $h$.

###### Proof.

Alg 1 updates the value function at only a subset of the state compared to
global reachability, hence for ${\hat{V}^{(0)}}={V^{(0)}}$,
${\hat{V}^{(1)}}\geq{\hat{V}^{(0)}}$. In particular, given an active set
${Q^{(0)}}$, we have
${\hat{V}^{(1)}}(x^{d})={V^{(1)}}(x^{d})\>\forall\>x^{d}\in{Q^{(0)}}$ and
${\hat{V}^{(1)}}(x^{d})\geq{V^{(1)}}(x^{d})\>\forall\>x^{d}\notin{Q^{(0)}}$.
This holds for subsequent iterations, as a single global update starting from
${\hat{V}^{(1)}}$ will be an upper-bound to global updating after 2
iterations, ${V^{(2)}}$, and henceforth. Upon convergence, $\hat{V}^{*}\geq
V^{*}$, with $V^{*}=V^{*}$, by Lemma 2, so $\hat{V}^{*}\geq V^{*}$. Hence, the
obtained 0-superlevel set
${\hat{\mathcal{C}}^{*}_{h}}\supseteq{\bar{\mathcal{C}}_{h}}$. From Lemma 1 we
know that ${\hat{\mathcal{C}}^{*}_{h}}$ is invariant. By definition, the
viability kernel ${\bar{\mathcal{C}}_{h}}$ is the largest invariant set,
therefore ${\hat{\mathcal{C}}^{*}_{h}}={\bar{\mathcal{C}}_{h}}$. ∎

In summary, the proof utilizes that we update solely on a subset of the states
$x^{d}$ at every iteration. We then use this to demonstrate that upon
convergence the obtained value function from Alg. 1 is an upper bound to
global HJ reachability, i.e. $\hat{V}^{*}\geq V^{*}$. Invoking Lemma 1, we
additionally know that ${\hat{\mathcal{C}}^{*}_{h}}$ is invariant, hence we
recover the viability kernel.

For control invariant sets, invariance by itself is not a sufficient condition
to use $\hat{V}^{*}$ in a safety filter (Eq. 3).

######  Remark 1.

The obtained value function $\hat{V}^{*}(x)$, is a (potentially non-smooth)
CBF for an appropriately chosen class $\mathcal{K}$ function $\alpha$ inside
its 0-superlevel set, ${\hat{\mathcal{C}}^{*}_{h}}$. In practice, the obtained
value function has relatively large gradients in the interior of the safe set.
If these are problematic, we can reconstruct a signed distance function to the
obtained viability kernel $\hat{\mathcal{C}}$ or consider a large threshold
$\zeta$ in Alg. 1 for the size of the boundary considered for updating at each
iteration.

##  IV Results

TABLE I: Quantitative comparison of HJ-Patch compared to learned barrier and global reachability for the 4D quadrotor. We provide a quantitative comparison of the performance of the safety filter through random rollouts and quantify the speedup of HJ-Patch by comparing the total number of cells that have been updated to obtain the value function. We observe that HJ-Patch drastically reduces the rate of unsafe trajectories compared to the learned almost-CBF while being moderately more unsafe than when applying reachability on the full grid. However, applying reachability globally comes with a $13$x increase in computational cost. | Empirical safety when deployed within safety filter | Computational cost
---|---|---
| Neural nominal policy | LQR nominal policy |  Hamiltonians computed [#] |  Share of grid labeled safe [%]
|  | Share of states visited
---
that are unsafe [%]
| Share of rollouts
---
that are unsafe [%]
| Share of states visited
---
that are unsafe [%]
| Share of rollouts
---
that are unsafe [%]
Learned almost-CBF | 39.8 | 66.1 | 36.2 | 52.7 | 31.5
Warm-started global HJR | 0.2 | 2.0 | 0.3 | 2.4 | 9.5e7 | 21.7
HJ-Patch (Ours) | 1.3 | 4.4 | 1.3 | 4.2 | 7.3e6 | 22.7

We evaluate the performance of our algorithm on 2 different systems, a
4-dimensional quadrotor that ignores lateral motion and a 6-dimensional planar
quadrotor. For both environments we train a neural barrier to self-right from
a random initial state and consider vertical constraints, the floor and
ceiling (for 4D and 6D), and additionally horizontal constraints, 2 walls (for
6D). The dynamics for the planar quadrotor models are adopted from [31]. The
results include a comparison to standard HJ reachability (here considered to
be ground truth), both in terms of the viability kernel obtained and the
speed-up obtained from using our patching algorithm. Additionally, for both
the 4D and 6D environments we provide an empirical validation of the obtained
CBF on a large number of rollouts compared to the almost-neural barrier.

We provide an open-source implementation of our approach at
https://github.com/UCSD-SASLab/HJ-Patch, which builds wrappers around the
OptimizedDP toolbox [32] and the jax-based HJReachability toolbox.

Figure 2: 0-superlevel set (left) and value function (right) on different 2D
projections, 0 velocities (top) and negative velocities (bottom). The patched
value function is in blue, the global HJR value function in green, and the set
associated with the original neural almost-CBF in black. The patched CBF is a
good approximation of the global solution near the boundary, but has a
flattened value function, corresponding to small gradients, outside the safe
set.

###  IV-A 4D Quadrotor: Ground truth comparison

The 4D dynamics model enables us to compare against standard HJ reachability,
where all cells are updated at every iteration. As seen from Fig. 2, left, we
see that for different 2D projections of the 4D viability kernel, the solution
from our algorithm and global reachability match closely (although we obtain
an overapproximation of the global viability kernel). As expected the value
function (see Fig. 2, right) matches closely to the global solution far from
the boundary and at the boundary, whereas the local solution has steeper
(flatter) gradients near the boundary within (outside) the viability kernel.

In addition, we demonstrate the need for patching neural almost-barriers by
rolling out trajectories ($n=1000$, $t=10s$) that start within the safe set
and employ said almost-barrier as a CBF in a safety filter. This equally
enables us to quantify the performance of the obtained value functions, both
global and local, when used as CBFs in a safety filter with a nominal policy
that is potentially unsafe, see Table I for a quantitative comparison. We
observe that the share of unsafe trajectories of HJ-Patch and global HJR are
on the same order of magnitude, while HJ-Patch provides a $14$x computational
speedup. The large amount of unsafe trajectories for the neural almost-barrier
highlight the need for formal safety methods. We also visualize the
trajectories in Fig. 3 in the vertical position-vertical velocity plane. We
additionally observe that although the share of unsafe trajectories of HJ-
Patch and global HJR are on the same order of magnitude, HJ-Patch’s value
function does not provide an exponential return to safety. This is likely due
to the flattened gradients outside the safe set. Fitting a signed-distance
function to the obtained 0-superlevel set can mitigate this behavior.

Figure 3: Rollouts of $1000$ trajectories over $10s$. The learned policy acts as the nominal controller, regulated with a CBF-based safety filter using the neural almost-CBF (left), the HJ-Patch value function (center), and the warm-started global HJ value function (right). The large number of unsafe trajectories (red; green is safe) for the almost-CBF highlights the need for patching neural barrier functions. As detailed in Section III-B, invariance is only guaranteed at the discretized states, hence resulting in non-zero unsafe trajectories for both HJ-Patch and the global HJ value function. Additionally, we observe that once a trajectory becomes unsafe, HJ-Patch’s value function, unlike the warm-started global HJ value function, does not provide an exponential return to safety. TABLE II: Quantitative comparison of HJ-Patch compared to the learned barrier and global reachability for 6D planar quadrotor. We provide a quantitative comparison of the performance of the safety filter through random rollouts and quantify the speedup of HJ-Patch by comparing the total number of cells that have been updated to obtain the value function. We observe that HJ-Patch drastically reduces the rate of unsafe trajectories compared to the learned almost-CBF and has a lower unsafe rate than global reachability. Additionally, HJ-Patch has an $100$x lower computational cost. | Empirical safety when deployed within safety filter | Computational cost
---|---|---
| Neural nominal policy | LQR nominal policy |  Hamiltonians computed [#] |  Share of grid labeled safe [%]
|  | Share of states visited
---
that are unsafe [%]
| Share of rollouts
---
that are unsafe [%]
| Share of states visited
---
that are unsafe [%]
| Share of rollouts
---
that are unsafe [%]
Learned almost-CBF | 0.4 | 2.3 | 38.6 | 57.3 | 4.2
Warm-started global HJR | 0.7 | 6.1 | 7.0 | 16.2 | 1.6e9 | 2.8
HJ-Patch (Ours) | 0.0 | 0.5 | 0.1 | 0.7 | 1.6e7 | 3.7

###  IV-B 6D Quadrotor: Scaling reachability

To provide a valid comparison to the global solution, we consider a 6D grid
with relatively large spacing between grid cells to retain computational
tractability. Again, like for the 4D vertical quadrotor, we quantitatively
compare HJ-Patch to the global HJR solution and the learned almost-CBF. We
observe that the learned almost-CBF requires only limited “patching” (see
Table II, the share of cells labeled as safe upon convergence of HJ-Patch
overlaps with the learned barrier for $>90$%). Additionally, using the same
convergence criteria, we see that HJ-Patch obtains a speedup of 2 orders of
magnitude. In line with our expectations, the speedup of HJ-Patch becomes
larger for higher dimensional systems, although the learned barrier for the
6-dimensional quadrotor is significantly better (i.e. almost-barrier with
lower $\varepsilon$) than the 4-dimensional quadrotor. For the empirical
safety quantification of the CBF, we observe that both global HJR and HJ-Patch
improve safety, but that HJ-Patch has a lower failure rate (see Table II). We
attribute the higher failure rate for global HJR to the limited resolution of
the grid (although we use the same grid as for HJ-Patch).

##  V Conclusion

In this work, we propose HJ-Patch, a constructive approach to patching neural
almost-barriers using local dynamic programming. Our method guarantees
convergence to a control invariant subset of the neural almost-barrier’s safe
set, and the resulting value function can be used within to enforce safety
using, e.g., a safety filter. As highlighted in the results, HJ-Patch enables
scaling HJ reachability by $2$ orders of magnitude, enabling scaling HJ
reachability by $1-2$ dimensions. Additionally, we observe that we converge to
a close over-approximation of the viability kernel that is obtained with
global HJ reachability. Nonetheless, due to the local nature of the updating,
once a trajectory leaves the safe set, our method does not provide an
exponential return to safety, unlike global reachability methods.

Future work: We are interested in further speedups for locally updating value
functions using more intelligent updating strategies and leveraging techniques
from computational physics such as adaptive grids. Additionally, for barrier
functions, the “nearest” invariant set will often be a superset of the learned
barrier. We plan to extend our algorithm to converge to the smallest invariant
superset of a given initial learned almost-barrier.

## Acknowledgements

We would like to thank Minh Bui for assisting in the implementation of our
work.

## References

  * [1] O. Kroemer, S. Niekum, and G. Konidaris, “A review of robot learning for manipulation: Challenges, representations, and algorithms,” _Journal of Machine Learning Research_ , vol. 22, no. 1, pp. 1395–1476, 2021.
  * [2] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,” _Science Robotics_ , vol. 7, no. 62, 2022.
  * [3] C. K. Liu and D. Negrut, “The role of physics-based simulators in robotics,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 4, no. 1, pp. 35–58, 2021.
  * [4] J. García and F. Fernández, “A comprehensive survey on safe reinforcement learning,” _Journal of Machine Learning Research_ , vol. 16, no. 1, pp. 1437–1480, 2015.
  * [5] L. Brunke, M. Greeff, A. W. Hall, Y. Zhaocong, S. Zhou, J. Panerati, and A. P. Schoellig. (2021) Safe learning in robotics: From learning-based control to safe reinforcement learning. Available at https://arxiv.org/abs/2108.06266.
  * [6] A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada, “Control barrier functions: Theory and applications,” in _European Control Conference_ , 2019.
  * [7] A. D. Ames, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs with application to adaptive cruise control,” in _Proc. IEEE Conf. on Decision and Control_ , 2014.
  * [8] J. J. Choi, D. Lee, K. Sreenath, C. J. Tomlin, and S. L. Herbert, “Robust control barrier-value functions for safety-critical control,” in _Proc. IEEE Conf. on Decision and Control_ , 2021.
  * [9] A. A. Ahmadi and A. Majumdar, “Some applications of polynomial optimization in operations research and real-time decision making,” _Optimization Letters_ , vol. 20, no. 4, pp. 709–729, 2016.
  * [10] C. Dawson, S. Gao, and C. Fan, “Safe control with learned certificates: A survey of neural lyapunov, barrier, and contraction methods for robotics and control,” _IEEE Transactions on Robotics and Automation_ , pp. 1–19, 2023\.
  * [11] L. Lindemann, A. Robey, L. Jiang, S. Tu, and N. Matni. (2021) Learning robust output control barrier functions from safe expert demonstrations. Available at https://arxiv.org/abs/2111.09971.
  * [12] S. Bansal and C. J. Tomlin, “Deepreach: A deep learning approach to high-dimensional reachability,” in _Proc. IEEE Conf. on Robotics and Automation_ , 2021.
  * [13] C. Liu, T. Arnon, C. Lazarus, C. Strong, C. Barrett, and M. J. Kochenderfer, “Algorithms for verifying deep neural networks,” _Foundations and Trends in Optimization_ , vol. 4, no. 3–4, pp. 244–404, 2021.
  * [14] H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel, “Efficient neural network robustness certification with general activation functions,” in _Conf. on Neural Information Processing Systems_ , 2018.
  * [15] Z. Qin, T.-W. Weng, and S. Gao, “Quantifying safety of learning-based self-driving control using almost-barrier functions,” in _IEEE/RSJ Int. Conf. on Intelligent Robots & Systems_, 2022.
  * [16] I. M. Mitchell, A. M. Bayen, and C. J. Tomlin, “A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 7, pp. 947–957, 2005.
  * [17] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin, “Hamilton-Jacobi reachability: A brief overview and recent advances,” in _Proc. IEEE Conf. on Decision and Control_ , 2017.
  * [18] A. Lin and S. Bansal. (2022) Generating formal safety assurances for high-dimensional reachability. Available at https://arxiv.org/abs/2209.12336.
  * [19] K.-C. Hsu, V. Rubies-Royo, C. J. Tomlin, and J. F. Fisac, “Safety and liveness guarantees through reach-avoid reinforcement learning,” in _Robotics: Science and Systems_ , 2021.
  * [20] C. Dawson, Z. Qin, S. Gao, and C. Fan, “Safe nonlinear control using robust neural lyapunov-barrier functions,” in _Conf. on Robot Learning_ , 2021\.
  * [21] S. Liu, C. Liu, and J. Dolan, “Safe control under input limits with neural control barrier functions,” in _Conf. on Robot Learning_ , 2022.
  * [22] S. M. Richards, F. Berkenkamp, and A. Krause, “The Lyapunov neural network: Adaptive stability certification for safe learning of dynamical systems,” in _Conf. on Robot Learning_ , 2018.
  * [23] S. Tonkens and S. Herbert, “Refining control barrier functions through hamilton-jacobi reachability,” in _IEEE/RSJ Int. Conf. on Intelligent Robots & Systems_, 2022.
  * [24] A. Bajcsy, S. Bansal, E. Bronstein, V. Tolani, and C. J. Tomlin, “An efficient reachability-based framework for provably safe autonomous navigation in unknown environments,” in _Proc. IEEE Conf. on Decision and Control_ , 2019.
  * [25] Y.-C. Chang, N. Roohi, and S. Gao, “Neural Lyapunov control,” in _Conf. on Neural Information Processing Systems_ , 2019.
  * [26] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor,” in _Int. Conf. on Machine Learning_ , 2018.
  * [27] F. Blanchini, “Set invariance in control,” _Automatica_ , vol. 35, pp. 1747–1767, 1999.
  * [28] S. Herbert, “Safe real-world autonomy in uncertain and unstructured environments,” Ph.D. dissertation, Dept. of EECS, Univ. of California, Berkeley, 2020.
  * [29] J. C. Strikwerda, _Finite Difference schemes and partial differential equations_. SIAM, 2004.
  * [30] S. L. Herbert, S. Bansal, S. Ghosh, and C. J. Tomlin, “Reachability-based safety guarantees using efficient initializations,” in _Proc. IEEE Conf. on Decision and Control_ , 2019.
  * [31] S. Singh, S. M. Richards, V. Sindhwani, J.-J. E. Slotine, and M. Pavone, “Learning stabilizable nonlinear dynamics with contraction-based regularization,” _Int. Journal of Robotics Research_ , 2020.
  * [32] M. Bui, G. Giovanis, M. Chen, and A. Shriraman. (2022) Optimizeddp: An efficient, user-friendly library for optimal control and dynamic programming. Available at https://arxiv.org/abs/2204.05520.