# Black-Box Safety Validation of Autonomous Systems: A Multi-Fidelity
Reinforcement Learning Approach

Jared J. Beard1 and Ali Baheri2 1Jared J. Beard is a Ruby Distinguished
Doctoral Fellow with the Mechanical and Aerospace Engineering Department at
West Virginia University, Morgantown, WV 26505, USA<EMAIL_ADDRESS>Baheri is with the Mechanical Engineering Department at Rochester Institute of
Technology, Rochester, NY 14623, USA<EMAIL_ADDRESS>
###### Abstract

The increasing use of autonomous and semi-autonomous agents in society has
made it crucial to validate their safety. However, the complex scenarios in
which they are used may make formal verification impossible. To address this
challenge, simulation-based safety validation is employed to test the complex
system. Recent approaches using reinforcement learning are prone to excessive
exploitation of known failures and a lack of coverage in the space of
failures. To address this limitation, a type of Markov decision process called
the knowledge MDP has been defined. This approach takes into account both the
learned model and its metadata, such as sample counts, in estimating the
system’s knowledge through the knows what it knows framework. A novel
algorithm that extends bidirectional learning to multiple fidelities of
simulators has been developed to solve the safety validation problem. The
effectiveness of this approach is demonstrated through a case study in which
an adversary is trained to intercept a test model in a grid-world environment.
Monte Carlo trials compare the sample efficiency of the proposed algorithm to
learning with a single-fidelity simulator and show the importance of
incorporating knowledge about learned models into the decision-making process.

##  I INTRODUCTION

The process of safety validation checks if a system meets performance
standards or identifies the nature of potential failures. This is crucial in
situations where human safety is at risk or significant harm to expensive
equipment may occur, such as in aircraft autopilots, driverless cars, and
space-flight systems. Formal verification, which is a commonly used method,
builds a detailed mathematical or computational model of the system being
tested to ensure it meets safety specifications. However, a major challenge in
using formal methods for safety validation is the large and complex design
space of decision-making models, which makes it difficult for formal
verification techniques to work effectively.

Figure 1: The MF-RL-falsify algorithm is applied to a grid world scenario
where the aim is to train an adversary to intercept a system under test, which
is defined as _failure_ in this study. The lowest fidelity having an unknown
policy is selected and the corresponding simulator is sampled at each time
step. Information about learned models is used to augment the reward
structure, preventing early convergence of the algorithm and ensuring
continued exploration for failures.

Another way of performing safety validation is through black-box and grey-box
safety verification, where the system is either not known well enough or only
provides limited information for analysis, respectively [1]. These methods can
include planning algorithms [2, 3], optimization tools [4, 5], and
reinforcement learning [6]. From a reinforcement learning viewpoint, the goal
of adaptive stress testing (AST) is to determine the most probable failure
scenarios by treating the problem as a Markov decision process (MDP) and
finding an adversarial policy that associates environmental states with
disturbances that result in system failure. AST has been applied in various
real-world domains, from aircraft collision avoidance [6] to autonomous
vehicles [7]. Despite its overall success, sampling-based methods such as
reinforcement learning have two main limitations. They may not be able to find
rare failures [8], and they rely on data collected from high-fidelity
simulators, which may not be feasible due to computational constraints [9].

The requirement of relying solely on samples from high-fidelity simulators can
be reduced by incorporating reinforcement learning techniques that utilize
multiple levels of simulator fidelity [10]. The degree of accuracy of a
simulator is referred to as its fidelity, with the level of fidelity
representing how much the system model and assumptions are simplified. Low-
fidelity simulators make strong assumptions, leading to faster execution, but
may not exhibit realistic behavior and dynamics. On the other hand, high-
fidelity simulators aim to closely approximate reality, but their execution
may be slower due to more complex system models and fewer assumptions.

Related work. To date, there has been only one study on multi-fidelity (MF)
safety validation, as described in [11]. This work serves as the only existing
MF alternative to our proposed approach, where information is only passed from
low to high-fidelity simulators in a unidirectional manner. However,
unidirectional techniques limit the amount of information that can be passed,
which affects their efficiency. On the other hand, bidirectional approaches
like the one presented in this paper, which pass information in both
directions, have been found to have lower sample complexity. The upper bound
of high-fidelity samples in bidirectional approaches is equivalent to the
unidirectional case [10]. Although this bidirectional approach is not used for
safety validation, it provides valuable insights into the problem.

The bidirectional approach in this paper uses the knows what it knows (KWIK)
framework to evaluate the relative worth of a sample in a given fidelity. The
KWIK framework is a concept in reinforcement learning (RL) that involves
explicitly tracking the uncertainty and reliability of learned models in the
decision-making process. The RL algorithm in the KWIK framework is equipped
with metadata about the learned models, such as sample counts, and uses this
information to estimate the system’s knowledge. This knowledge is then used to
guide the exploration-exploitation trade-off in the RL algorithm.

Statement of contributions. The objective of this work is to develop a
framework that minimizes the simulation cost while maximizing the number of
failure scenarios discovered. In contrast to previous safety validation
techniques, we propose a learner that uses knowledge about itself to
reformulate the safety validation problem and present a bidirectional
algorithm MF-RL-falsify to solve this problem (Fig. 1). The contributions of
this work are as follows:

  * •

We propose a novel knowledge Markov decision process (KMDP) framework, which
factors knowledge (i.e., metadata) of the learned model into the decision
making process and explicitly distinguishes the system model from the
knowledge of this model;

  * •

We demonstrate MF-RL-falsify an algorithm using the KWIK framework to train
learners from _multiple fidelities of simulators in a bidirectional manner_.
MF-RL-falsify also uses a knowledge-based update to prevent early convergence
of the learned model and encourage further exploration.

Paper structure. The paper is structured as follows: Section II briefly
outlines preliminaries, as well as introduces the KMDP. Section III details
the MF-RL-falsify algorithm. Section IV covers the experimental setup,
results, and some limitations of the implementation. Lastly, Section V
presents concluding remarks and future directions of work.

##  II Problem setup and Preliminary

The objective of this work is to find the most likely failure scenarios for a
(decision-making/control) system under test $\mathcal{M}$. Here, failure
scenarios are defined as the sequence of transitions that lead to some failure
condition (e.g., midair collision). The system under test is placed in a
black-box (usually high-fidelity) simulator $\Sigma$, so the learner (with
planner $P$) does not have direct access to the internal workings of the
system. The learner then samples scenarios iteratively to learn and uses the
planner to apply disturbances (e.g., control agents in the environment, supply
noise, or adjust parameters of the environment). More specifically, the
learner uses the simulations to minimize the distance to a failure metric. The
work presented here seeks to reduce the need for computationally expensive
simulations by using MF simulations with bidirectional information passing to
improve the overall sample efficiency.

###  II-A Markov Decision Process

This work relies on MDP’s so it is useful to introduce notation which will
form the foundation of this work. MDP’s are defined by the tuple
$\langle\mathcal{S},\mathcal{A},T,R,\gamma\rangle$. Here, $\mathcal{S}$ is the
set of all states $s$ and $\mathcal{A}$ the set of all actions $a$. The
stochastic transition model is $T(s^{\prime}\mid s,a)$, where $s^{\prime}$
represents a state outcome when taking $a$ from $s$. $R(s,a,s^{\prime})$ is
the reward for some transition. Lastly, $\gamma$ is a temporal discount
factor. By solving an MDP, an optimal control policy $\pi^{*}(s)\ \forall
s\in\mathcal{S}$ can be achieved. Here, the optimal policy is defined as
follows:

$\pi^{*}(s)=\arg\max_{a}Q(s,a),$ (1)

where $Q^{*}(s,a)$ the corresponding optimal state-action value function is

$Q^{*}(s,a)=\\\ \max\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)[R(s,a,s^{\prime})+\gamma Q^{*}(s^{\prime},a^{\prime})].$ (2)

###  II-B Knows What It Knows Learner

Use of MF simulators in reinforcement learning has come about from the desire
to reduce the number of samples in and expense incurred by high-fidelity
simulators used to get reliable performance. To this end, [10] leveraged the
concept of KWIK learners [12]. The fundamental idea of KWIK is to use
information about the learned model to provide output indicating its
confidence in said model. When the learner is not confident in the model, it
reports relevant state-action pairs as unknown ($\perp$) [12]. In particular,
Cutler, et al. uses the number of samples to assert a model is known to some
degree of confidence specified by the Hoeffding inequality (parameterized by
$\epsilon$, $\delta$) [10].

In the multi-fidelity case, the knowledge is used to decide when to _switch_
between the $D$ fidelities of simulators. The knowledge $\mathcal{K}$ is
defined for this work as both estimates of the transition and reward models
($\mathcal{K}.\hat{T}$, $\mathcal{K}.\hat{R}$), as well as the confidence in
these models ($\mathcal{K}_{d,T}(s,a)$, $\mathcal{K}_{d,R}(s,a)$). Here, the
subscript $d$ indicates the specific fidelity. The lower fidelities aim to
guide search in higher fidelity simulators, while knowledge from higher
fidelities is used to improve the accuracy of lower fidelity models.
Mathematically, two simulators are said to be in fidelity to each other if
their $Q$ values are sufficiently close according to:

$f(\Sigma_{i},\Sigma_{j},\rho_{i},\beta_{i})=\\\
\begin{cases}\Delta=-\max_{s,a}|Q^{*}_{i}(s,a)-Q^{*}_{j}(\rho_{j}(s),a)|,\\\
\hfill\forall s,a~{}\text{if}~{}\Delta\leq\beta_{i}\\\ -\infty,\
\mathrm{else.}\end{cases}$ (3)

Note, $\beta$ indicates a user specified bound on how dissimilar two
simulators can be and $\rho$ is a mapping of states from the fidelity of $i$
to fidelity $j$. In this work, this mapping is applied on a state-by-state
basis, as the decision process only needs to model one decision at a time, not
the whole system.

###  II-C Knowledge Markov Decision Process

Whereas this learning problem has classically been represented as an MDP,
doing so assumes the model is known with sufficient accuracy. This may not
always be the case (as in reinforcement learning). When the decision maker can
quantify its lack of information about the model, it should be able to use
this information to its benefit. Thus, we introduce the KMDP as
$\langle\mathcal{S},\mathcal{A},T,R,\mathcal{K},\gamma\rangle$. Here,
$\mathcal{K}$ represents the knowledge about the decision maker’s model of the
system (e.g., estimates of the other terms
$\langle\mathcal{S},\mathcal{A},T,R\rangle$, confidence in those estimates,
and other assumptions of the learned model). Consequently, $\hat{T}$ and
$\hat{R}$ are used to solve the underlying MDP as the agent learns. Note from
Sec. II-B these estimates of the model are considered part of $\mathcal{K}$.
In doing so, the learner is explicitly aware that it is making decisions based
on an estimated model of its environment and that it has some domain knowledge
regarding the quality of these estimates. Thus this information can factor
into decisions, such as through the reward which is now defined as
$\hat{R}(s,a,s^{\prime},\mathcal{K})$. As an example, knowledge about the lack
of information for some subset of states could necessitate a reward that
encourages exploration in those regions.

The KMDP is related to the concepts of maximum likelihood model MDPs and
reward shaping. The maximum likelihood model MDP and KMDP share similar update
rules for the learned reward and transition models [13]. However, KMDP
generalizes these concepts to include estimates of $\mathcal{S}$ and
$\mathcal{A}$, as well as providing a more broad use of the information gained
from sampling. As an example, the agent may not be aware of all states if it
is required to explore its environment, thus the estimated state space would
be a subset of $\mathcal{S}$. Furthermore knowledge may now capture concepts
such as whether a state has been visited, which is not inherently captured by
the underlying state. It is important to note that this would break the Markov
property, but such an approximation has been used to break explicit temporal
dependencies [14]. The second concept is reward shaping, where the additional
reward terms guide learning as a function of the system state [15]. The
difference being that here the learner is deciding based on learned
information or knowledge about the model, not only the underlying state.
Following from this, $Q^{*}$ cannot actually be achieved, and the best $Q$
given $\mathcal{K}$ becomes

$Q_{\mathcal{K}}(s,a)=\max_{a}\sum_{s^{\prime}}\\\
\mathcal{K}.\hat{T}(s^{\prime}\mid
s,a)[\mathcal{K}.\hat{R}(s,a,s^{\prime},\mathcal{K})+\gamma
Q_{\mathcal{K}}(s^{\prime},a^{\prime})].$ (4)

##  III Falsification using multi-fidelity simulators

Here, the functionality of the MF-RL-falsify algorithm (Alg. 1) is described.
The approach centers on three functionalities: search, evaluateState, and
marginalUpdate. The search function is tasked with iterating through trials
and collecting failure information. As part of search, evaluateState simulates
trajectories and updates the learned models. Lastly, marginalUpdate, given
confidence information, updates the reward function to bias search away from
trajectories for which the models are known (sampled a sufficient number of
times). The proposed algorithm is initialized with a set of simulators,
fidelity constants, and state mappings $\langle\Sigma,\beta,\rho\rangle$, the
system under test $\mathcal{M}$, and the planner $P$ of choice (this work uses
value iteration). Additionally, the confidence parameters ($\epsilon,\delta$),
and minimum samples to change fidelity ($m_{known}$, $m_{unknown}$) are
supplied. For more information on the choice of these parameters, see [10].
With no samples, $\mathcal{K}$ is initialized with a uniform distribution over
transitions and rewards set as $R_{max}$ of the KMDP. The $Q$ values are set
to 0 and the current fidelity $d$ is declared as the lowest fidelity. Lastly,
it is assumed there are no changes to the model estimate, and no known or
unknown samples $(m_{k},m_{u})$.

input: _$\langle\Sigma,\beta,\rho\rangle$ , $\mathcal{M}$, $R_{inc}$, $P$,
$(\epsilon,\delta)$, $(m_{known},m_{unknown})$_

initialize: _ $\mathcal{K}$, $Q_{d}$_

initialize: _ $change_{d}=false$, $d=1$, $m_{k},m_{u}=0$_

Procedure  _search( $s$,$n$)_

$\mathcal{\hat{F}}\leftarrow\\{\\}$

for  _$i=1,...,n$_ do

$reinitialize(\Sigma)$

$\mathcal{\hat{F}}\leftarrow\mathcal{\hat{F}}\cup evaluateState(s)$

for  _$f\in\mathcal{\hat{F}}$_ do

if  _$\neg isPlausible(f,D)$_ then

$\mathcal{\hat{F}}\leftarrow\mathcal{\hat{F}}\setminus f$

return $\mathcal{\hat{F}}$

Procedure  _evaluateState(s)_

initialize: _$f\leftarrow\\{\\}$_

while  _$\neg terminal(s)$_ do

$a\leftarrow\\{P.\pi(s),\mathcal{M}.\pi(s)\\}$

if  _$d >1$ and $change_{d}$ and
$\mathcal{K}_{d-1}(\rho_{d-1}(s),a_{P})=\perp$ and $m_{u}\geq m_{unknown}$_
then

$Q_{d-1}\leftarrow plan(d-1)$

$d\leftarrow d-1$

else

$s^{\prime},r\sim T_{\Sigma}(s^{\prime}\mid s,a)$

if  _$\mathcal{K}_{d}(s,a)=$ $\perp$_ then

$update\big{(}\mathcal{K}_{d}(s,a)\big{)}$

if  _$\mathcal{K}_{d}(s,a)\not=$ $\perp$ _ then

$Q_{d}\leftarrow plan(d)$

$f\leftarrow f\cup\langle s,a,s^{\prime}\rangle$, $s\leftarrow s^{\prime}$

if  _$d <D$ and $m_{k}\geq m_{known}$_ then

$Q_{d+1}\leftarrow plan(d+1)$

$d\leftarrow d+1$

if  _isConverged( $f)$_ then

$marginalUpdate(f)$

if  _$isFailure(f)$_ then

return $f$

Procedure  _plan(d)_

for  _all $\langle s,a\rangle$_ do

$d^{\prime}\leftarrow\\{max(d^{\prime})\,\mid\,d^{\prime}\geq
d,\,\mathcal{K}_{d^{\prime}}(s,a)\not=\perp\\}$

$\mathcal{K}_{d}(s,a)\leftarrow\mathcal{K}_{d^{\prime}}(s,a)$

return
$P.train(\mathcal{K}.\hat{T},\mathcal{K}.\hat{R},Q_{d},Q_{d-1}+\beta_{d-1})$

Procedure  _marginalUpdate( $f$)_

$m_{max}\leftarrow 0,\,t\leftarrow\langle\rangle$

for  _$\langle s,a,s^{\prime}\rangle\in f$_ do

$m=Q_{\mathcal{K}}(s,a)-Q_{\mathcal{K}^{\prime}}(s,a^{\prime})$

if  _$m >m_{max}$_ then

$m_{max}\leftarrow m$

$t\leftarrow\langle s,a,s^{\prime}\rangle$

$R(t)\leftarrow R(t)-R_{inc}$

$Q_{d}\leftarrow plan(d)$

Algorithm 1 MF-RL-falsify

###  III-A Search

The $search$ algorithm serves primarily to initiate the learning process. MF-
RL-falsify looks at failures from a single initial condition. As such, a state
$s$ is passed in along with a desired number of trajectories $n$. The estimate
of the set of failure modes, $\mathcal{\hat{F}}$ is initialized as empty. For
every iteration, the simulators are reset and $evaluateState$ is called.
Failure scenarios found by $evaluateState$ are added to $\mathcal{\hat{F}}$.
Due to the nature of sampling, policies may come from more than one fidelity.
Thus, after the search has concluded, it is necessary to evaluate whether
failure modes are viable in the highest fidelity; those not meeting this
condition are rejected. The remaining set is returned to the user.
Plausibility checks may manifest in a few ways: for simulators with relatively
simple transition models, these can be checked directly to exist or not; for
more complex, stochastic systems, this may involve a Monte Carlo sampling to
determine if a transition occurs in the model. Fortunately, due to the Markov
assumption, this can be broken down to a state-by-state basis, as opposed to
looking at the entire trajectory at once.

###  III-B State Evaluation

At every iteration of the $search$ algorithm, the evaluateState function
attempts to find a failure scenario given the current model estimate. The
process begins by initializing the trajectory $f$. Then actions are
iteratively selected from the current policy $\pi$ and the decision is made to
increment the fidelity or sample the current one. This continues until a
terminal state is found; terminal states can be a failure event, exceeding the
maximum number of time steps, or reaching some state where failure cannot
occur. Whenever the fidelity is incremented, both $m_{k}$ and $m_{u}$ are
reset. Otherwise, if a known state-action is reached, $m_{k}$ is incremented,
while $m_{u}$ is reset. The converse occurs when an unknown state is reached.
Similarly, $change_{d}$ is set to false when the state is incremented and set
to true when a state-action becomes known.

The fidelity is decremented if a known state has not recently been reached and
the lower fidelity states are also unknown. This permits more efficient search
by using the less expensive simulator to carry out uncertain actions. Along
with the decrement, the planner is updated using the current model. Otherwise,
a simulation is performed to gather data from the model. If the current state
is considered unknown, this information is used to update the learned model
and knowledge. The knowledge about the transition is incremented by one (the
distribution is generated by normalizing the sampled outcomes for each $s,\,a$
pair). The reward is updated as a weighted average of the reward estimate and
sampled reward. Lastly, the knowledge about each, being the number of samples
for a state-action, is incremented by one. If a state-action becomes known,
the planner is updated. The transition is added to the trajectory and the
current state is updated. Subsequently, the fidelity is incremented and re-
planning occurs if enough known samples have been visited. The algorithm
concludes with the marginal update if the trajectory has converged (all
$(s,a)\in f$ considered known). If a failure state has been achieved by the
trajectory, the trajectory is deemed a failure scenario and returned.

When planning, the algorithm must pass information to lower fidelities to
improve the performance of future samples. The $plan$ function does this by
finding the highest fidelity ($\geq d$) for which a state-action pair is
known. This model estimate is then used to update the knowledge of the current
fidelity. Similarly, to pass information up, if states from the current $d$
and next lower $d-1$ model estimates are deemed to be in fidelity
($\Delta\leq\beta$), the lower fidelity model estimate is used in place of the
current fidelity. The planner is then run to update $Q$.

###  III-C Marginal Update

The marginal update incorporates knowledge into the decision making process.
Here, the marginal is defined as the difference in the best state-action value
$Q_{\mathcal{K}}$ and the second best state-action value
$Q_{\mathcal{K}^{\prime}}$ for a given state. When the system is known to be
converged, the state having the largest marginal (along the trajectory) is
selected. Using this state, the reward is decreased by $R_{inc}$ and the
planner updated. The underlying idea is that if the learner has converged on a
trajectory, it will cease to explore the solution space, exploiting an action
repeatedly. By finding the state where the best action is significantly
greater than its neighbors, exploration can erode the most functionally
important actions for a given trajectory. As training continues, this cuts off
search in more fragile trajectories (hence less likely trajectories early) and
encourages exploration along the entirety of more robust failure trajectories.

##  IV RESULTS

We evaluate the effectiveness of the proposed algorithm by answering the
following research questions:

  * •

RQ1: Does the proposed multi-fidelity algorithm improve the overall sample
efficiency?111Sample efficiency refers to the ability of the RL agent to learn
effectively from a relatively small number of environment interactions.

  * •

RQ2: Does the proposed multi-fidelity algorithm result in the identification
of more failure scenarios compared to the single-fidelity scenario?

Before presenting the simulation setup, we define two key terms in our
experiments.

Definition 1. (Fidelity). In this context fidelity refers to the accuracy of
the model being used, with a high-fidelity model having a higher level of
accuracy, capturing more details and nuances, while a low-fidelity model may
not capture all the relevant information and result in less accuracy. In our
experiments, the low-fidelity model does not accurately capture the impact of
puddles on the transition model (see Fig. 2).

Definition 2. (Failure). Here, failure is defined as the scenario where the
red dot (MF-RL learner) intersects the blue dot (system under test).

###  IV-A Simulation

The experiment involved a 4$\times$4 grid world environment with puddles (as
depicted in Fig. 2). The goal of the system under test was to reach a specific
location in the grid world, while the learner’s objective was to cause
failures by either blocking the system under test or causing a collision. The
system under test was designed to be myopic, meaning it would take the closest
unobstructed action towards its goal. The states were defined by the
coordinates of both the system under test $(x,y)_{\mathcal{M}}$ and the
learner $(x,y)_{P}$. Both agents were able to move one cell in any of the
cardinal directions or remain in place. If an agent was in a puddle, it had a
20% chance of reaching the desired cell; otherwise, it would not move. The
learner was penalized based on its distance from the system under test,
receiving a penalty of $-5$ when in a puddle and $-25$ when the system under
test reached the goal. If the learner induced a failure, it received a reward
of $50$. The discount factor $\gamma$ was set to $0.95$ for the experiment.

Figure 2: 4$\times$4 Grid worlds under test (left) low-fidelity, (right) high-
fidelity. Here, fidelity is demonstrated by accuracy of the model, where the
low-fidelity does not capture the impact of puddles on the transition model.
The blue dot indicates the system under test, the red the MF-RL learner, and
the green “$\times$” the system under test’s goal. Puddles are indicated by
black and grey regions.

###  IV-B Monte Carlo Trials

To evaluate the approach, $25$ Monte Carlo trials were conducted for both the
single-fidelity (SF) and MF learners. To evaluate the performance of the
marginal update, each of five values for $R_{inc}=[0,0.25,1,2,5]$ at up to
$1000$ iterations were used in both simulators. Note that $R_{inc}=0$
indicates no marginal update. Each trial, the initial coordinates of the
system under test and learner were uniformly sampled; samples that obviously
could not cause failures or scenarios initialized to failure states were
removed. Other parameters were set as follows: $\beta=1250$, $t_{max}=20$,
$\epsilon=0.25$, $\delta=0.5$, $m_{known}=10$, and $m_{unknown}=5$.

Given the relatively simple scenario, it is helpful to understand where the MF
simulator converges in the highest fidelity. Much larger examples involve
sparse scenarios, so the area of interest are those regions where the ratio of
high-fidelity to low-fidelity samples (Fig. 3) is relatively low and likely
far below this convergence estimate. For context, the optimal high-fidelity
policy could be found at a high- to low-fidelity sample ratio of less than
$\sim$ 0.4. Notice that the marginal update does not appreciably impact the
ratio, except for $R_{inc}=5$, where the search reached under-explored states
in low fidelities. Naturally, as the algorithm converges, return to lower
fidelities is prevented and the samples grow at approximately the same rate as
the SF case, hence the near linear behavior after convergence (Fig. 4) (RQ1).
In the SF scenario, increasing $R_{inc}$ led to further search, though in the
MF scenario the behavior was unclear, likely due to interactions from changing
fidelities.

Figure 3: Mean ratio of high-fidelity samples to low-fidelity samples against
iterations of $search$; notice that $R_{inc}=5$ encourages more exploration as
samples increase. Legend indicates values of $R_{inc}$.

Figure 4: Mean number of high-fidelity samples for (left) single-fidelity and
(right) Multi-fidelity learners. Notice the MF approach accumulates
significantly fewer samples until convergence, at which samples are
accumulated at similar rates. Legend indicates values of $R_{inc}$.

With respect to the number of failures, the MF simulator quickly accumulates
failures from low-fidelity samples, while the earliest high-fidelity samples
in the SF simulator are wasted (Fig. 5) (RQ2). Around convergence, their
performance is comparable. Without the marginal update, search in SF ceases at
convergence; a large $R_{inc}$ yields $\sim 15\%$ increase in failures found.
In the MF scenario, small updates perform similarly to no update, however,
$R_{inc}=5$ yields a significant improvement, as much as $15\%$ with almost no
HF samples, supporting use of the marginal update. The improvements of the MF
scenario are further realized in Fig. 6. The MF scenario finds as many as 6
times more failures per sample than the SF case early on, with their
performance approaching unity after convergence.

Overall, results are promising, indicating the MF algorithm significantly
improves the sample efficiency in finding failure scenarios over the SF
approach. Additionally, the marginal update for large values of $R_{inc}$
enhances exploration consistently with growth in samples, leading to more
failure scenarios and greater sample efficiency, particularly when the model
has been sampled insufficiently (as in more complicated scenarios).

Figure 5: Mean number of high-fidelity failures for the (left) single- and
(right) multi-fidelity approaches. The MF approach immediately makes use of
underlying information, while the SF approach wastes early samples in the
high-fidelity simulator. Additionally, $R_{inc}=5$ increases the number of
failures found relative to no or a small update. Legend indicates values of
$R_{inc}$.

Figure 6: Ratio of failures per sample for the (left) single- and (right)
multi-fidelity cases. The MF approach is approximately 6 times more efficient
for few samples; their efficiency converges as samples increases. Additionally
$R_{inc}=5$ appears to provide an upper bound on the performance. Legend
indicates values of $R_{inc}$.

###  IV-C Limitations

The implementation has two main drawbacks. One is that it is only created for
discrete problems and handling representations of knowledge and continuous
domains can be challenging within the KWIK framework. The second limitation is
that value iteration, which is used to find solutions to MDPs, is not very
efficient and thus limits the number of Monte Carlo trials and the size of the
environment. This issue could potentially be resolved by using an anytime
solver such as Monte Carlo tree search [16].

##  V CONCLUSIONS

The purpose of this study was to enhance the effectiveness of reinforcement
learning techniques in detecting failure scenarios in autonomous systems. The
study introduced the knowledge MDP, which incorporates a learner’s
understanding of its own model estimates into the decision-making process,
through the KWIK framework. The resulting algorithm, called MF-RL-falsify
showed improved performance compared to single-fidelity (SF) approaches. The
inclusion of knowledge through marginal updates was also found to increase
exploration in converged scenarios and enhance early exploration of the
solution space.

However, further development is needed for the technique to become a viable
alternative to existing methods. This includes increasing scalability by
utilizing learned models with anytime planners and applying the framework to
continuous state and action spaces. Additionally, further research is
necessary to test the KMDP formulation in various contexts and more complex
scenarios.

## References

  * [1] A. Corso, R. Moss, M. Koren, R. Lee, and M. Kochenderfer, “A survey of algorithms for black-box safety validation of cyber-physical systems,” _Journal of Artificial Intelligence Research_ , vol. 72, pp. 377–428, 2021\.
  * [2] E. Plaku, L. E. Kavraki, and M. Y. Vardi, “Hybrid systems: from verification to falsification by combining motion planning and discrete search,” _Formal Methods in System Design_ , vol. 34, no. 2, pp. 157–182, 2009.
  * [3] C. E. Tuncali and G. Fainekos, “Rapidly-exploring random trees for testing automated vehicles,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 661–666.
  * [4] G. E. Mullins, P. G. Stankiewicz, R. C. Hawthorne, and S. K. Gupta, “Adaptive generation of challenging scenarios for testing and evaluation of autonomous vehicles,” _Journal of Systems and Software_ , vol. 137, pp. 197–215, 2018\.
  * [5] J. Deshmukh, M. Horvat, X. Jin, R. Majumdar, and V. S. Prabhu, “Testing cyber-physical systems through Bayesian optimization,” _ACM Transactions on Embedded Computing Systems (TECS)_ , vol. 16, no. 5s, pp. 1–18, 2017.
  * [6] R. Lee, O. J. Mengshoel, A. Saksena, R. W. Gardner, D. Genin, J. Silbermann, M. Owen, and M. J. Kochenderfer, “Adaptive stress testing: Finding likely failure events with reinforcement learning,” _Journal of Artificial Intelligence Research_ , vol. 69, pp. 1165–1201, 2020.
  * [7] M. Koren, S. Alsaif, R. Lee, and M. J. Kochenderfer, “Adaptive stress testing for autonomous vehicles,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2018, pp. 1–7.
  * [8] A. Corso, R. Lee, and M. J. Kochenderfer, “Scalable autonomous vehicle safety validation through dynamic programming and scene decomposition,” in _2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2020, pp. 1–6.
  * [9] R. J. Moss, R. Lee, N. Visser, J. Hochwarth, J. G. Lopez, and M. J. Kochenderfer, “Adaptive stress testing of trajectory predictions in flight management systems,” in _2020 AIAA/IEEE 39th Digital Avionics Systems Conference (DASC)_. IEEE, 2020, pp. 1–10.
  * [10] M. Cutler, T. J. Walsh, and J. P. How, “Real-world reinforcement learning via multifidelity simulators,” _IEEE Transactions on Robotics_ , vol. 31, no. 3, pp. 655–671, 2015.
  * [11] M. Koren, A. Nassar, and M. J. Kochenderfer, “Finding failures in high-fidelity simulation using adaptive stress testing and the backward algorithm,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 5944–5949.
  * [12] L. Li, M. L. Littman, T. J. Walsh, and A. L. Strehl, “Knows what it knows: A framework for self-aware learning,” _Machine learning_ , vol. 82, no. 3, pp. 399–443, 2011.
  * [13] M. Wiering and J. urgen Schmidhuber, “Learning exploration policies with models,” _Proc. CONALD_ , 1998.
  * [14] J. J. Beard, _Environment Search Planning Subject to High Robot Localization Uncertainty_. West Virginia University, 2020.
  * [15] A. D. Laud, _Theory and application of reward shaping in reinforcement learning_. University of Illinois at Urbana-Champaign, 2004.
  * [16] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of Monte Carlo tree search methods,” _IEEE Transactions on Computational Intelligence and AI in games_ , vol. 4, no. 1, pp. 1–43, 2012.

##  VI APPENDIX

The KWIK formulation (Alg. 2) was generated by stripping MF-RL-falsify of its
dependence on fidelity. As such, supplying MF-RL-falsify with a SF simulator,
will have the same performance. In spite of this, the KWIK algorithm was used
for experiments. Notice, there is no longer a need to check the veracity of
failures since all samples are from a single fidelity. Furthermore, planning
is accomplished using the models for $\hat{T}$ and $\hat{R}$ as there is no
longer information to pass. This reduces the $plan$ step to training as would
be done in classical approaches.

input: _$\Sigma$ , $\mathcal{M}$, $R_{inc}$, $P$, $(\epsilon,\delta)$_

initialize: _ $\mathcal{K}$, $Q$_

Procedure  _search( $s$,$n$)_

$\mathcal{\hat{F}}\leftarrow\\{\\}$

for  _$i=1,...,n$_ do

$reinitialize(\Sigma)$

$\mathcal{\hat{F}}\leftarrow\mathcal{\hat{F}}\cup evaluateState(s)$

return $\mathcal{\hat{F}}$

Procedure  _evaluateState(s)_

initialize: _$f\leftarrow\\{\\}$_

while  _$\neg terminal(s)$_ do

$a\leftarrow\\{P.\pi(s),\mathcal{M}.\pi(s)\\}$

$s^{\prime},r\sim T_{\Sigma}(s^{\prime}\mid s,a)$

if  _$\mathcal{K}(s,a)=$ $\perp$_ then

$update\big{(}\mathcal{K}(s,a)\big{)}$

if  _$\mathcal{K}(s,a)\not=$ $\perp$ _ then

$Q\leftarrow P.train(\mathcal{K}.\hat{T},\mathcal{K}.\hat{R},Q)$

$f\leftarrow f\cup\langle s,a,s^{\prime}\rangle$, $s\leftarrow s^{\prime}$

if  _isConverged( $f)$_ then

$marginalUpdate(f)$

if  _$isFailure(f)$_ then

return $f$

Procedure  _marginalUpdate( $f$)_

$m_{max}\leftarrow 0,\,t\leftarrow\langle\rangle$

for  _$\langle s,a,s^{\prime}\rangle\in f$_ do

$m=Q_{\mathcal{K}}(s,a)-Q_{\mathcal{K}^{\prime}}(s,a^{\prime})$

if  _$m >m_{max}$_ then

$m_{max}\leftarrow m$

$t\leftarrow\langle s,a,s^{\prime}\rangle$

$R(t)\leftarrow R(t)-R_{inc}$

$Q\leftarrow P.train(\mathcal{K}.\hat{T},\mathcal{K}.\hat{R},Q)$

Algorithm 2 KWIK