$[\sigma]=A_{n}(\sigma)+B_{n}(\sigma)x_{n}+C_{n}(\sigma)x_{n+1}+D_{n}(\sigma)x_{n}x_{n+1}$.
\- Let us first prove (19d) for the pair $[\omega_{P}]$ and
$[\tau_{n}\circ\omega_{P}]$. It amounts to show that
$\nabla_{n}\nabla_{n+1}[\tau_{n}\circ\omega_{P}]=\nabla_{n}\nabla_{n+1}[\omega_{P}]$.
For any $\sigma$ we have

$D_{n}(\sigma)=\sum_{j=1}^{n-2}x_{1}\cdots
x_{j}\nabla_{n}\nabla_{n+1}[\sigma]_{j+1}^{o}+\sum_{j=n+1}^{P}\nabla_{n}\nabla_{n+1}x_{1}\cdots
x_{j}\,[\sigma]_{j+1}^{o}.$

The last terms with $j\geq n+1$ coincide for $\sigma=\omega_{P}$ and
$\sigma=\tau_{n}\circ\omega_{P}$, thanks to (44a). The terms with $j\leq n-2$
for $\sigma=\tau_{n}\circ\omega_{P}$ reads

$\nabla_{n}\nabla_{n+1}[\tau_{n}\circ\omega_{P}]_{j+1}^{o}=\sum_{k=1}^{j}D_{j+1-k|0}\nabla_{n}\nabla_{n+1}D^{(n+k-j-1)}_{k|P-j-1}({\bm{x}}_{\geq
j+2}).$

But $D^{(n+k-j-1)}_{k|P-j-1}({\bm{x}}_{\geq
j+2})=\nabla_{1}\cdots\nabla_{k}[\tau_{n+k-j-1}\circ\mathfrak{c}_{P-j-1}]$ by
definition. Hence,

$\nabla_{n}\nabla_{n+1}D^{(n+k-j-1)}_{k|P-j-1}({\bm{x}}_{\geq
j+2})=\nabla_{n}\nabla_{n+1}D_{k|P-j-1}({\bm{x}}_{\geq j+2})$

and
$\nabla_{n}\nabla_{n+1}[\tau_{n}\circ\omega_{P}]_{j+1}^{o}=\nabla_{n}\nabla_{n+1}[\omega_{P}]_{j+1}^{o}$
for $j\leq n-2$.
\- Let us now prove (19c,19b) for the pair $[\omega_{P}]$ and
$[\tau_{n}\circ\omega_{P}]$. For any $\sigma$ we have,

$\displaystyle B_{n}(\sigma)=\sum_{j=1}^{n-2}x_{1}\cdots
x_{j}\nabla_{n}[\sigma]_{j+1}^{o}|_{x_{n+1}=0}+x_{1}\cdots
x_{n-1}[\sigma]_{n+1}^{o},$ $\displaystyle
C_{n}(\sigma)=\sum_{j=1}^{n-2}x_{1}\cdots
x_{j}\nabla_{n+1}[\sigma]_{j+1}^{o}|_{x_{n}=0}+x_{1}\cdots
x_{n-1}\nabla_{n+1}[\sigma]_{n}^{o}.$

Thanks to the expression (44d) of $[\tau_{n}\circ\omega_{P}]_{j+1}^{o}$ in
terms of $D^{(n+k-j-1)}_{k|P-j-1}({\bm{x}}_{\geq j+2})$, for $j\leq n-2$, the
contributions of the terms $x_{1}\cdots,x_{j}$ in this decomposition fulfil
the moves (19c,19c) by the induction hypothesis.
Proving (19c,19b) for the terms $x_{1}\cdots x_{n_{1}}$ in this decomposition
amounts to verify that

$\displaystyle~{}[\tau_{n}\circ\omega_{P}]_{n+1}^{o}=\nabla_{n+1}[\omega_{P}]_{n}^{o}+D_{1|0}D_{n|P-n-1}({\bm{x}}_{\geq
n+2}),$ (64a)
$\displaystyle\nabla_{n+1}[\tau_{n}\circ\omega_{P}]_{n}^{o}=[\omega_{P}]_{n+1}^{o}-D_{1|0}D_{n|P-n-1}({\bm{x}}_{\geq
n+2}).$ (64b)

To prove (64a), recall that
$[\omega_{P}]_{j+1}^{o}=\sum_{k=1}^{j}D_{j+1-k|0}D_{k|P-j-1}({\bm{x}}_{\geq
j+2})$ so that

$\displaystyle\nabla_{n+1}[\omega_{P}]_{n}^{o}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}D_{n-k|0}\nabla_{n+1}D_{k|P-n}({\bm{x}}_{\geq
n+1})$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}D_{n-k|0}D_{k+1|P-n-1}({\bm{x}}_{\geq n+2})$
$\displaystyle=$
$\displaystyle[\tau_{n}\circ\omega_{P}]_{n+1}^{o}-D_{1|0}D_{n|P-n-1}({\bm{x}}_{\geq
n+2}),$

where in the last line we use formula (44b) expressing
$[\tau_{n}\circ\omega_{P}]_{n}^{o}$ in terms of the $D_{k|P-k}$’s.
To prove (64b), we notice that, from (44c) and
$\nabla_{n+1}D_{n-k|1}(x_{n+1})=D_{n+1-k|0}$, we have

$\displaystyle\nabla_{n+1}[\tau_{n}\circ\omega_{P}]_{n}^{o}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}D_{n+1-k|0}D_{k|P-n-1}({\bm{x}}_{\geq n+2})$
$\displaystyle=$
$\displaystyle[\omega_{P}]_{n+1}^{o}-D_{1|0}D_{n|P-n-1}({\bm{x}}_{\geq n+2}).$

\- Finally, we have to prove (19a) for the pair $[\omega_{P}]$ and
$[\tau_{n}\circ\omega_{P}]$. For any $\sigma$ we have,

$A_{n}(\sigma)=\sum_{j=1}^{n-1}x_{1}\cdots
x_{j}\,[\sigma]_{j+1}^{o}|_{x_{n}=0=x_{n+1}}.$

Again the contribution of the terms $x_{1}\cdots x_{j}$ for $1\leq j\leq n-2$
in this decomposition fulfil (19a) thanks to the induction hypothesis and the
formula (44d) for $[\tau_{n}\circ\omega_{P}]_{j+1}^{o}$ for $1\leq j\leq n-2$.
Let thus look at the term $x_{1}\cdots x_{n-1}$. Using
$D_{n-k|1}(x_{n+1})=-D_{n+1-k|0}(1-x_{n+1})$, we have

$\displaystyle~{}[\tau_{n}\circ\omega_{P}]_{n}^{o}|_{x_{n+1}=0}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}D_{n-k|1}(x_{n+1})|_{x_{n+1}=0}D_{k|P-n-1}({\bm{x}}_{\geq
n+2}),$ $\displaystyle=$
$\displaystyle-\sum_{k=1}^{n-1}D_{n+1-k|0}D_{k|P-n-1}({\bm{x}}_{\geq n+2}).$

On the other hand, since
$[\omega_{P}]_{j+1}^{o}=\sum_{k=1}^{j}D_{j+1-k|0}D_{k|P-j-1}({\bm{x}}_{\geq
j+2})$ and $D_{k|P-n}(x_{n+1},{\bm{x}}_{\geq
n+2})=[\omega_{P+k-n}]_{k+1}^{o}$, we have

$\displaystyle[\omega_{P}]_{n}^{o}|_{x_{n+1}=0}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}D_{n-k|0}D_{k|P-n}({\bm{x}}_{\geq
j+2})|_{x_{n+1}=0}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n-1}D_{n-k|0}\sum_{l=1}^{k}D_{k+1-l|0}D_{l|P-n-1}({\bm{x}}_{\geq
j+2})$ $\displaystyle=$
$\displaystyle-\sum_{k=1}^{n-1}D_{n+1-k|0}D_{k|P-n-1}({\bm{x}}_{\geq
n+2})=[\tau_{n}\circ\omega_{P}]_{n}^{o}|_{x_{n+1}=0},$

where we used $D_{m|0}=-\sum_{n=1}^{m-1}D_{n|0}D_{m-n|0}$ in the last line.
Thus we proved the exchange relations (19) for the pair $[\omega_{P}]$ and
$[\tau_{n}\circ\omega_{P}]$. $\square$

###  8.2 Examples of extractions

In order to make the notations from Section 7 clear, we illustrate the
different cases pictured in Figure 3 on specific examples. For a deformation
$\mu_{n}$, let $\hat{\mu}_{n}=\mu_{n}\circ\omega_{P}$ with $\omega_{P}$ the
regular with $P$, as in the main text.

I. For $N\leq n-3$, $l\leq N+1$,
let $P=10,n=7,l=2,N=4,|\mu|=2$.

$\displaystyle\mu$ $\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}\\\
\bm{2}&\bm{1}\end{pmatrix},$ $\displaystyle\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&3&4&5&6&\bm{7}&\bm{8}&9&10\\\
1&\underset{l}{2}&\underset{l+1}{3}&4&5&\underset{N+2}{6}&\bm{8}&\bm{7}&9&10\end{pmatrix},$
$\displaystyle\tau_{l+1}\cdots\tau_{N+1}\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&3&4&5&6&\bm{7}&\bm{8}&9&10\\\
1&\underset{l}{2}&4&5&\underset{N+2}{6}&\underset{l+1}{3}&\bm{8}&\bm{7}&9&10\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle=\begin{pmatrix}\underset{l}{2}&4&5&\underset{N+2}{6}\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$
$\displaystyle=\begin{pmatrix}1&\underset{l+1}{3}&\bm{8}&\bm{7}&9&10\end{pmatrix}.$

II. For $N\geq n+|\mu|-2$, $N+1\geq l\geq n+|\mu|$,
let $P=10,n=3,l=6,N=7,|\mu|=2.$

$\displaystyle\mu$ $\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}\\\
\bm{2}&\bm{1}\end{pmatrix},$ $\displaystyle\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&\bm{3}&\bm{4}&5&6&7&8&9&10\\\
1&2&\bm{4}&\bm{3}&5&\underset{l}{6}&\underset{l+1}{7}&8&\underset{N+2}{9}&10\end{pmatrix},$
$\displaystyle\tau_{l+1}\cdots\tau_{N+1}\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&\bm{3}&\bm{4}&5&6&7&8&9&10\\\
1&2&\bm{4}&\bm{3}&5&\underset{l}{6}&8&\underset{N+2}{9}&\underset{l+1}{7}&10\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle=\begin{pmatrix}\underset{l}{6}&8&\underset{N+2}{9}\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$
$\displaystyle=\begin{pmatrix}1&2&\bm{4}&\bm{3}&5&\underset{l+1}{7}&10\end{pmatrix}.$

III. For $N\geq n+|\mu|-2$, $n\leq l\leq n+|\mu|-1$,
let $P=10,n=3,l=4,N=7,|\mu|=4$,

$\displaystyle\mu$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\underset{j_{*}}{\bm{3}}&\bm{4}\\\
\bm{3}&\bm{4}&\bm{2}&\bm{1}\end{pmatrix},$ $\displaystyle\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&\bm{3}&\bm{4}&\underset{j_{*}}{\bm{5}}&\bm{6}&7&8&9&10\\\
1&2&\underset{l+1}{\bm{5}}&\bm{6}&\underset{l}{\bm{4}}&\bm{3}&7&8&\underset{N+2}{9}&10\end{pmatrix},$
$\displaystyle\tau_{l+1}\cdots\tau_{N+1}\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&\bm{3}&\bm{4}&\bm{5}&\bm{6}&7&8&9&10\\\
1&2&\bm{6}&\bm{7}&\underset{l}{\bm{4}}&\bm{3}&8&\underset{N+2}{9}&\underset{l+1}{\bm{5}}&10\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle=\begin{pmatrix}\underset{l}{\bm{4}}&\bm{3}&8&\underset{N+2}{9}\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$
$\displaystyle=\begin{pmatrix}1&2&\bm{6}&\bm{7}&\underset{l+1}{\bm{5}}&10\end{pmatrix}.$

IV. For $N\geq n+|\mu|-2$, and $1\leq l\leq n-1$,
let $P=10,l=2,n=4,N=8,|\mu|=2$,

$\displaystyle\mu$ $\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}\\\
\bm{2}&\bm{1}\end{pmatrix},$ $\displaystyle\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&3&\bm{4}&\bm{5}&6&7&8&9&10\\\
1&\underset{l}{2}&\underset{l+1}{3}&\bm{5}&\bm{4}&6&7&8&9&\underset{N+2}{10}\end{pmatrix},$
$\displaystyle\tau_{l+1}\cdots\tau_{N+1}\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&3&\bm{4}&\bm{5}&6&7&8&9&10\\\
1&\underset{l}{2}&4&\bm{6}&\bm{5}&7&8&9&\underset{N+2}{10}&\underset{l+1}{3}\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle=\begin{pmatrix}\underset{l}{2}&4&\bm{6}&\bm{5}&7&8&9&\underset{N+2}{10}\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$
$\displaystyle=\begin{pmatrix}1&\underset{l+1}{10}\end{pmatrix}.$

V. For $N+1\geq l\geq n$, $M-1\geq m\geq 1$,
let $P=10,n=3,l=4,N=5,M=N+2-(n-1)=5,m=l-(n-1)=2,|\mu|=7$.

$\displaystyle\mu$
$\displaystyle=\begin{pmatrix}\underset{i_{*}}{\bm{1}}&\bm{2}&\bm{3}&\bm{4}&\bm{5}&\bm{6}&\underset{I_{*}}{\bm{7}}\\\
\bm{2}&\bm{6}&\bm{4}&\bm{7}&\bm{3}&\bm{1}&\bm{5}\end{pmatrix},$
$\displaystyle\tau_{m+1}\cdots\tau_{M-1}\mu=\omega_{M}^{m+1}\mu$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\bm{3}&\bm{4}&\bm{5}&\bm{6}&\bm{7}\\\
\bm{2}&\bm{6}&\bm{5}&\bm{7}&\bm{4}&\bm{1}&\bm{3}\end{pmatrix},$
$\displaystyle\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&\bm{3}&\bm{4}&\bm{5}&\bm{6}&\bm{7}&\bm{8}&\bm{9}&10\\\
1&2&\underset{l}{\bm{4}}&\bm{8}&\bm{6}&\bm{9}&\underset{l+1}{\bm{5}}&\bm{3}&\underset{N+2}{\bm{7}}&10\end{pmatrix},$
$\displaystyle\tau_{l+1}\cdots\tau_{N+1}\mu_{n}$
$\displaystyle=\begin{pmatrix}1&2&\bm{3}&\bm{4}&\bm{5}&\bm{6}&\bm{7}&\bm{8}&\bm{9}&10\\\
1&2&\underset{l}{\bm{4}}&\bm{8}&\underset{N+2}{\bm{7}}&\bm{9}&\bm{6}&\bm{3}&\underset{l+1}{\bm{5}}&10\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle=\begin{pmatrix}\underset{l}{\bm{4}}&\bm{8}&\underset{N+2}{\bm{7}}&\bm{9}&\bm{6}&\bm{3}\end{pmatrix},$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$
$\displaystyle=\begin{pmatrix}1&2&\underset{l+1}{\bm{5}}&10\end{pmatrix}.$
$\displaystyle\mu_{\varpi}^{(m,M)}$
$\displaystyle=\omega_{M}^{m+1}\begin{pmatrix}\mu{}^{-1}(m)&\mu{}^{-1}(m)+1&\cdots&\mu{}^{-1}(M)-1\\\
m&\mu(\mu{}^{-1}(m)+1)&\cdots\mu(&\mu{}^{-1}(M)-1)\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\bm{3}&\bm{4}&\bm{5}&\bm{6}\\\
\bm{2}&\bm{6}&\bm{5}&\bm{7}&\bm{4}&\bm{1}\end{pmatrix}\equiv\begin{pmatrix}\bm{3}&\bm{4}&\bm{5}&\bm{6}&\bm{7}&\bm{8}\\\
\underset{l}{\bm{4}}&\bm{8}&\underset{N+2}{\bm{7}}&\bm{9}&\bm{6}&\bm{3}\end{pmatrix}$
$\displaystyle\implies(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle(\mu_{\varpi}^{m)(M})_{n}$
$\displaystyle=\Big{(}\omega_{M}^{m+1}\begin{pmatrix}1&\cdots&\mu{}^{-1}(m)-1&\mu^{(-1)}(M)&\cdots&|\mu|\\\
\mu(1)&\cdots&\mu(\mu^{-1}(m)-1)&M&\cdots&\mu(|\mu|)\end{pmatrix}\Big{)}_{n}$
$\displaystyle=\Big{(}\begin{pmatrix}\bm{7}\\\
\bm{3}\end{pmatrix}\Big{)}_{n}=\begin{pmatrix}1&2&\bm{9}&10\\\
1&2&\bm{5}_{l+1}&10\end{pmatrix}$
$\displaystyle\implies(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$

VI. For $1\leq l\leq n-1$,
let $P=14,n=6,l=3,N=7,M=N+2-(n-1)=4,|\mu|=7$ :

$\displaystyle\mu$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\bm{3}&\bm{4}&\underset{I_{*}}{\bm{5}}&\bm{6}&\bm{7}\\\
\bm{2}&\bm{5}&\bm{7}&\bm{6}&\bm{4}&\bm{1}&\bm{3}\end{pmatrix}$
$\displaystyle\tau_{1}\cdots\tau_{M-1}\mu=\omega_{M}^{1}\mu$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\bm{3}&\bm{4}&\bm{5}&\bm{6}&\bm{7}\\\
\bm{3}&\bm{5}&\bm{7}&\bm{6}&\bm{1}&\bm{2}&\bm{4}\end{pmatrix}$
$\displaystyle\mu_{n}$
$\displaystyle=\setcounter{MaxMatrixCols}{14}\begin{pmatrix}1&2&3&4&5&\bm{6}&\bm{7}&\bm{8}&\bm{9}&\bm{10}&\bm{11}&\bm{12}&13&14\\\
1&2&\underset{l}{3}&\underset{l+1}{4}&5&\bm{7}&\bm{10}&\bm{12}&\bm{11}&\underset{N+2}{\bm{9}}&\bm{6}&\bm{8}&13&14\end{pmatrix}$
$\displaystyle\tau_{l+1}\cdots\tau_{N+1}\mu_{n}$
$\displaystyle=\setcounter{MaxMatrixCols}{14}\begin{pmatrix}1&2&3&4&5&\bm{6}&\bm{7}&\bm{8}&\bm{9}&\bm{10}&\bm{11}&\bm{12}&13&14\\\
1&2&\underset{l}{3}&5&\bm{6}&\bm{8}&\bm{10}&\bm{12}&\bm{11}&\underset{l+1}{4}&\bm{7}&\underset{N+2}{\bm{9}}&13&14\end{pmatrix}$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle=\begin{pmatrix}3_{l}&5&\bm{6}&\bm{8}&\bm{10}&\bm{12}&\bm{11}\end{pmatrix}\equiv\begin{pmatrix}1&3&\bm{4}&\bm{6}&\bm{8}&\bm{10}&\bm{9}\end{pmatrix}$
$\displaystyle(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$
$\displaystyle=\begin{pmatrix}1&2&\underset{l+1}{4}&\bm{7}&\underset{N+2}{\bm{9}}&13&14\end{pmatrix}$
$\displaystyle\mu^{M]}$
$\displaystyle=\begin{pmatrix}1&\cdots&\mu^{-1}(M)-1\\\
\mu(1)&\cdots&\mu(\mu^{-1}(M)-1)\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\bm{3}&\bm{4}\\\
\bm{2}&\bm{5}&\bm{7}&\bm{6}\end{pmatrix}$
$\displaystyle\omega_{M}^{1}\mu^{M]}$
$\displaystyle=\begin{pmatrix}\bm{1}&\bm{2}&\bm{3}&\bm{4}\\\
\bm{3}&\bm{5}&\bm{7}&\bm{6}\end{pmatrix}$
$\displaystyle(\mu_{\varpi}^{M]})_{n-l+1}$
$\displaystyle=\begin{pmatrix}1&2&3&\bm{4}&\bm{5}&\bm{6}&\bm{7}\\\
1&2&3&\bm{6}&\bm{8}&\bm{10}&\bm{9}\end{pmatrix}\equiv\begin{pmatrix}3&4&5&\bm{6}&\bm{7}&\bm{8}&\bm{9}\\\
3_{l}&5&\bm{6}&\bm{8}&\bm{10}&\bm{12}&\bm{11}\end{pmatrix}$
$\displaystyle\implies(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{-}$
$\displaystyle\mu^{[M}$
$\displaystyle=\begin{pmatrix}\mu^{-1}(M)+1&\cdots&|\mu|\\\
\mu(\mu^{-1}(M)+1)&\cdots&\mu(|\mu|)\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\bm{6}&\bm{7}\\\ \bm{1}&\bm{3}\end{pmatrix}$
$\displaystyle\omega_{M}^{1}\mu^{[M}$
$\displaystyle=\begin{pmatrix}\bm{6}&\bm{7}\\\ \bm{2}&\bm{4}\end{pmatrix}$
$\displaystyle(\mu_{\varpi}^{[M})_{l+1}=(\omega_{M}^{1}\mu^{[M})_{l+1}$
$\displaystyle=\begin{pmatrix}1&2&3&\bm{9}&\bm{10}&13&14\\\
1&2&3&\bm{5}&\bm{7}&13&14\end{pmatrix}\equiv\begin{pmatrix}1&2&\bm{10}&\bm{11}&\bm{12}&13&14\\\
1&2&\underset{l+1}{4}&\bm{7}&\underset{N+2}{\bm{9}}&13&14\end{pmatrix}$
$\displaystyle\implies(\tau_{l+1}\cdots\tau_{N+1}\circ\hat{\mu}_{n})_{l}^{+}$

## References

  * [1] C. Kipnis and C. Landim, Scaling limits of interacting particle systems, Springer, Berlin, (1999).
  * [2] T. Liggett, Stochastic interacting systems: contact, voter and exclusion processes, Fund. Principles Math. Sciences 324, Springer, Berlin (1999).
  * [3] H. Spohn, Large scale dynamics of interacting particles, Springer, Berlin, (1991).
  * [4] C. Kipnis, S. Olla and S. Varadhan, Hydrodynamics and large deviation for simple exclusion processes, Commun. Pure Appl. Math. 42, 115-137 (1989).
  * [5] B. Derrida, Non-equilibrium steady states: fluctuations and large deviations of the density and of the current, J. Stat. Mech., P07023, (2007).
B. Derrida, Microscopic versus macroscopic approaches to non-equilibrium
systems, J. Stat. Mech. 2011, P01030 (2011).

  * [6] K. Mallick, The Exclusion Process: A paradigm for non-equilibrium behaviour, Physica A: Stat. Mech. and Appl., 418, 1-188 (2015).
  * [7] G. Gallavotti and E.G.D. Cohen, Dynamical ensembles in non-equilibrium statistical mechanics, Phys. Rev. Lett. 74, 2694 (1995).
  * [8] C. Jarzynski, Nonequilibrium equality for free energy differences, Phys. Rev. Lett. 78, 2690-2693 (1997).
  * [9] G.E. Crooks, Entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences, Phys. Rev. E 60, 2721-2726 (1999).
  * [10] C. Maes, The Fluctuation Theorem as a Gibbs Property., J. Stat. Phys. 95, 367-392, (1999).
  * [11] C. Maes and K. Natocny, Time reversal and entropy, J. Stat. Phys. 110, 269-310, (2003).
  * [12] L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, and C. Landim, Current fluctuations in stochastic lattice gases, Phys. Rev. Lett. 94, 030601 (2005).
L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio and C. Landim,
Macroscopic fluctuation theory, Rev. Mod. Phys. 87(2), 593 (2015).

  * [13] O. A. Castro-Alvaredo, B. Doyon and T. Yoshimura, Emergent Hydrodynamics in Integrable Quantum Systems Out of Equilibrium, Phys. Rev. X 6, 041065 (2016).
  * [14] B. Bertini, M. Collura, J. De Nardis and M. Fagotti, Transport in Out-of-Equilibrium XXZ Chains: Exact Profiles of Charges and Currents, Phys. Rev. Lett. 117, 207201 (2016).
  * [15] M. Mezei, Membrane theory of entanglement dynamics from holography, Phys. Rev. D 98, 106025, (2018).
  * [16] T. Zhou and A. Nahum. Emergent statistical mechanics of entanglement in random unitary circuits. Physical Review B, 99(17):174205, (2019).
  * [17] M.J. Gullans and D. A. Huse, Entanglement Structure of Current-Driven Diffusive Fermion Systems, Phys. Rev. X 9, 021007 (2019).
  * [18] C. A. Agon and M. Mezei, Bit threads and the membrane theory of entanglement dynamics, arXiv:1910.12909, (2019).
  * [19] T. Zhou and A. Nahum. The entanglement membrane in chaotic many-body systems, arXiv:1912.12311, (2019).
  * [20] M. Bauer, D. Bernard and T. Jin, Equilibrium Fluctuations in Maximally Noisy Extended Quantum Systems. SciPost Phys. 6:45, (2019).
  * [21] D. Bernard and T. Jin, Open quantum symmetric simple exclusion process, Phys. Rev. Lett. 123, 080601 (2019).
  * [22] T. Jin, A. Krajenbrink and D. Bernard, From stochastic spin chains to quantum Kardar-Parisi-Zhang dynamics, arXiv:2001.04278.
  * [23] M. Znidaric, Exact solution for a diffusive non-equilibrium steady state of an open quantum chain, J. Stat. Mech. 2010, L05002 (2010).
V. Eisler, Crossover between ballistic and diffusive transport: The Quantum
Exclusion Process, J. Stat. Mech. P06007 (2011).
M.V. Medvedyeva, F.H.L. Essler, and T. Prosen, Exact Bethe Ansatz Spectrum of
a Tight-Binding Chain with Dephasing Noise, Phys. Rev. Lett. 117, 137202
(2016).

  * [24] S. Devadoss and J. O’Rourke, Discrete and Computational Geometry, Princeton University Press, (2011).
  * [25] N. Arkani-Hamed, Y. Bai, S. He and G. Yan, Scattering Forms and the Positive Geometry of Kinematics, Color and the Worldsheet, JHEP 05, 096 (2018).
  * [26] See e.g. B.A. Dubrovin, I.M. Krichever, S.P. Novikov, Integrable systems. I. , in: Arnold V.I., Novikov S.P. (eds), Dynamical Systems IV. Encyclopaedia of Mathematical Sciences, vol 4. Springer, (2001).
O. Babelon, D. Bernard, M. Talon, Introduction to classical integrable
systems, Cambridge University Press (2003).
A.R. Chowdhury, A.G. Choudhury, Quantum integrable systems, Research Notes in
Mathematics Series 435, Chapman $\&$ Hall, (2004).

  * [27] S. Fomin and A. Zelevinsky, Cluster algebras. I: Foundations, J. Am. Math. Soc. 15, 497-529 (2002).
S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification,
Invent. Math.154, 63-121 (2003).

  * [28] S. Fomin and N. Reading, Root systems and generalized associahedra, Geometric combinatorics, 63-131, IAS/Park City Math. Ser., 13, Amer. Math. Soc., (2007).
  * [29] Y. Brenier, Permutations and PDE, Oberwolfach Seminar October 2018, http://www.math.ens.fr/-brenier/
  * [30] T. Bodineau and B. Derrida, Current Fluctuations in Non-equilibrium Diffusive Systems: An Additivity Principle, Phys. Rev. Lett. 92, 180601 (2004).
  * [31] We thank Michel Bauer for pointing out this connexion.


11institutetext: Rochester Institute of Technology 11email<EMAIL_ADDRESS>22institutetext: Stanford University 22email<EMAIL_ADDRESS>

# Joint Falsification and Fidelity Settings Optimization for Validation of
Safety-Critical Systems:
A Theoretical Analysis

Ali Baheri 11 Mykel J. Kochenderfer 22

###### Abstract

Safety validation is a crucial component in the development and deployment of
autonomous systems, such as self-driving vehicles and robotic systems.
Ensuring safe operation necessitates extensive testing and verification of
control policies, typically conducted in simulation environments. High-
fidelity simulators accurately model real-world dynamics but entail high
computational costs, limiting their scalability for exhaustive testing.
Conversely, low-fidelity simulators offer efficiency but may not capture the
intricacies of high-fidelity simulators, potentially yielding false
conclusions. We propose a joint falsification and fidelity optimization
framework for safety validation of autonomous systems. Our mathematical
formulation combines counterexample searches with simulator fidelity
improvement, facilitating more efficient exploration of the critical
environmental configurations challenging the control system. Our contributions
encompass a set of theorems addressing counterexample sensitivity analysis,
sample complexity, convergence, the interplay between the outer and inner
optimization loops, and regret bound analysis. The proposed joint optimization
approach enables a more targeted and efficient testing process, optimizes the
use of available computational resources, and enhances confidence in
autonomous system safety validation.

###### Keywords:

Falsification Fidelity Optimization Safety-Critical Systems

##  1 Introduction

In the development of autonomous systems, such as autonomous vehicles (AVs),
ensuring their safe and efficient operation is critical. AVs must navigate
various complex urban driving scenarios, including intersections, highway
merges, and lane changes, with their control systems being based on learning-
enabled policies. These policies must undergo rigorous testing and
verification before deployment. Simulators that can generate different traffic
scenarios are employed for testing the AV control systems. However, extensive
tests using high-fidelity simulators can be computationally expensive, time-
consuming, and may not cover all possible scenarios [8].

The joint falsification and simulator optimization approach addresses these
challenges by introducing a joint learning framework that streamlines the
exploration process for identifying potential failure scenarios. This
framework concentrates on the most critical environmental configurations that
pose difficulties for the control system. The joint learning framework, which
concurrently optimizes simulator fidelity and carries out falsification,
facilitates more effective use of computational resources during the search
process.

One key advantage of jointly learning falsification and simulator optimization
is the adaptive control of simulator fidelity settings. The simulator can
adjust its fidelity based on the specific scenario or region of the
environment, leading to more targeted and efficient testing. As the
simulator’s fidelity increases, it becomes better at replicating the behavior
of the high-fidelity simulator, allowing for a more accurate representation of
the environment. This enables the falsification process to focus on the
regions of the environment space where the system is more likely to fail,
which are the most critical areas to explore.

The joint learning framework integrates the search for failure scenarios with
the enhancement of simulator fidelity. This synergy allows for efficient
exploration by utilizing information gathered from both processes. For
instance, if a low-fidelity simulator displays a substantial discrepancy
compared to the high-fidelity simulator in a particular region, a joint
optimization approach can prioritize refining the simulator fidelity in that
area. This not only aids in more accurate identification of potential failure
scenarios but also conserves computational resources by preventing unnecessary
exploration in less relevant regions. Generalization is another important
aspect to consider when developing a joint optimization method. By
incorporating multiple tasks during the optimization process, such an approach
can identify fidelity settings that excel across various scenarios. This
ensures that the optimized fidelity settings are not overly specialized for a
single task, but rather strike a balanced trade-off between computational
efficiency and accuracy over a wider range of situations.

Related Work. Falsification of learning-enabled systems has garnered
considerable interest recently due to the growing complexity and safety-
critical nature of such systems [1]. The primary goal of falsification is to
pinpoint scenarios that could lead to system failure or breaches in safety
specifications. Various techniques have been proposed to tackle the
falsification problem, including optimization-based methods [11, 19, 6],
search-based algorithms [12, 15, 20], and reinforcement learning approaches
[18, 16, 10]. These methods strive to efficiently explore the state and
parameter space in order to discover potential failure scenarios, ultimately
enabling system design refinement and enhanced safety assurances. Researchers
have also recently developed algorithms that consider the fidelity of
simulators when identifying failure scenarios due to the computational expense
of high-fidelity simulators [9, 13, 4]. These methods trade between the
accuracy of high-fidelity simulators and the computational efficiency of low-
fidelity simulators to decrease the overall cost of safety validation. While
there has been notable progress in falsification of learning-enabled systems,
the literature on joint falsification and fidelity setting optimization
remains scarce. Our work aims to bridge this gap by presenting an approach
that _jointly_ conducts falsification alongside simulation fidelity
optimization. By combining these two aspects, our objective is to improve the
efficiency of safety validation in learning-enabled decision-making systems.

Contributions. We present a mathematical formulation for joint falsification
and fidelity setting optimization for the safety validation of autonomous
systems. Our primary contribution is the development of a theoretical
framework that _unifies_ the two key aspects of the problem: falsification of
learning-enabled systems and optimization of simulator fidelity settings. The
main contributions of this paper are as follows:

  * •

We propose a mathematical formulation that jointly addresses falsification and
fidelity setting optimization, enabling a more efficient exploration strategy
to search for potential failure scenarios.

  * •

We prove six key theorems that establish the fundamental properties and
relationships in the joint optimization problem. These theorems cover a range
of important aspects, including sensitivity analysis, sample complexity,
convergence, the interplay between the outer and inner loops, and the regret
bound analysis when employing Bayesian optimization for the outer loop. The
insights gained from these theorems provide a foundation for the joint
falsification and fidelity optimization framework.

##  2 Problem Formulation

Our objective is to efficiently combine falsification and fidelity
optimization for safety-critical systems, aiming to minimize computational
cost while preserving accuracy. We aim to identify environment configurations
that violate safety specifications while simultaneously optimizing the
fidelity settings to minimize discrepancies between low-fidelity and high-
fidelity simulators. This joint optimization problem is formulated as a nested
optimization framework with two components: an inner loop and an outer loop
optimization [5].

###  2.1 Inner Loop Optimization (Falsification)

The inner loop optimization aims to identify environment configurations that
minimize the robustness value of a given safety specification $\varphi$ under
a specific fidelity setting $f$. The simulator operates within a given
environment $e\in\mathcal{E}$. It takes a configuration $e$ as input and
produces a finite-horizon trajectory denoted by $\xi$. If a trajectory
satisfies the safety specification, the robustness function $\rho_{\varphi}$
evaluates to a positive value; otherwise, it returns a negative value. As a
result, the falsification problem can be formulated as the following
optimization problem:

${e}^{*}({f})=\underset{{e}\in\mathcal{E}}{\mathrm{argmin}}\
\rho_{\varphi}(e;f)$ (1)

The goal is to search for an environment configuration $e^{*}(f)$ that
minimizes the robustness value within the considered environment space
$\mathcal{E}$, given the fidelity setting $f$.

###  2.2 Outer Loop Optimization (Fidelity Setting Optimization)

The outer loop optimization focuses on finding the optimal fidelity settings
$f^{*}$ that minimize discrepancies between high-fidelity and low-fidelity
simulators across a variety of tasks while considering the environment
configurations obtained from the inner loop optimization. To efficiently
explore the search space, we sample from the space of tasks and their
parameters. Let $T$ denote the number of sampled tasks, and $M_{i}$ represent
the number of sampled parameter configurations for each task. For each task
$T_{i}$, we have access to a high-fidelity simulator generating ground-truth
trajectories, denoted as $\xi_{i}^{H}\left(t_{i};p_{ij}\right)$. Additionally,
a low-fidelity simulator produces approximate trajectories, represented by
$\xi_{i}^{L}\left(t_{i};p_{ij},f\right)$. The outer loop optimization problem
can be formulated as:

$f^{*}=\arg\min_{f\in\mathcal{F}}\sum_{i=1}^{T}\sum_{j=1}^{M_{i}}\ell\left(\xi_{i}^{H}\left(t_{i};p_{ij}\right),\xi_{i}^{L}\left(t_{i};p_{ij},f\right)\right),$
(2)

where $\mathcal{F}$ represents the set of possible simulator fidelity
settings, $t_{i}$ is the $i$th sampled task, and $p_{ij}$ is the $j$th sampled
parameter configuration for task $i$. The optimization objective is to
minimize the discrepancy, measured by the loss function $\ell$, between high-
fidelity simulator $\xi_{i}^{H}$ and low-fidelity simulator $\xi_{i}^{L}$ for
the sampled tasks and parameter configurations. The loss function
$\ell(\cdot,\cdot)$ measures discrepancies between the high-fidelity and low-
fidelity simulators. One option for the loss function is the mean squared
error (MSE) between both sets of trajectories over a fixed time interval:

$\ell(\xi^{H},\xi^{L})=\frac{1}{N}\int_{0}^{N}\left|\xi^{H}(t;p)-\xi^{L}(t;p,f)\right|^{2}dt$
(3)

where $N$ is the length of the time interval over which the MSE is computed.

##  3 Theoretical Insights and Results

After establishing the problem formulation for the joint optimization of
falsification and fidelity settings, we now delve deeper into the theoretical
results that guide our approach. In this section, we present a series of
theorems that offer insights into the joint optimization framework, providing
an understanding of the interplay between the inner and outer loop
optimizations, sensitivity analysis of counterexamples, sample complexity, and
convergence properties.

###  3.1 Lipschitz continuity of inner and outer loop objectives

In this section, we investigate the Lipschitz continuity of the inner and
outer loop objectives. Lipschitz continuity is a crucial property that
guarantees the stability of an optimization algorithm and enables us to derive
convergence guarantees. We begin by introducing a theorem that establishes
Lipschitz continuity for both inner and outer loop objectives under certain
conditions.

Theorem 1. Let $\rho_{\varphi}(e;f)$ and $\ell(\xi^{H},\xi^{L})$ be the inner
and outer loop objective functions, respectively. Suppose that there exist
constants $L_{\rho}>0$ and $L_{\ell}>0$ such that

$\displaystyle|\rho_{\varphi}(e_{1};f)-\rho_{\varphi}(e_{2};f)|\leq
L\rho\lVert e_{1}-e_{2}\rVert,$ (4)
$\displaystyle|\ell(\xi^{H}_{1},\xi^{L}_{1})-\ell(\xi^{H}_{2},\xi^{L}_{2})|\
\leq
L_{\ell}(\lVert\xi^{H}_{1}-\xi^{H}_{2}\rVert+\lVert\xi^{L}_{1}-\xi^{L}_{2}\rVert),$
(5)

for any $e_{1},e_{2}\in\mathcal{E}$, $f\in\mathcal{F}$, and
$\xi^{H}_{1},\xi^{H}_{2},\xi^{L}_{1},\xi^{L}_{2}\in\mathcal{X}$, where
$\mathcal{X}$ represents the space of all possible trajectories generated by
the high-fidelity and low-fidelity simulators.

Proof. The proof of Theorem 1 follows from the definitions of Lipschitz
continuity and the properties of the inner and outer loop objective functions.
We need to show that the conditions stated in the theorem hold for the given
objective functions.

For the inner loop objective function $\rho_{\varphi}(e;f)$, we assume that it
is Lipschitz continuous with respect to the environment configurations $e$.
This property can be established by showing that the specification robustness
value changes smoothly with respect to changes in the environment
configurations, given a fixed fidelity setting $f$. This assumption is
typically valid where the system behavior is continuous with respect to the
environment configurations. Similarly, for the outer loop objective function
$\ell(\xi^{H},\xi^{L})$, we assume that it is Lipschitz continuous with
respect to the trajectories $\xi^{H}$ and $\xi^{L}$. The Lipschitz continuity
of $\ell$ implies that the discrepancy measure changes smoothly with respect
to the trajectories obtained from high-fidelity and low-fidelity simulators.
The basis for this property lies in the smooth dynamics of the simulator and
the continuous dependency of the discrepancy measure on the trajectories.
Assuming the Lipschitz continuity of both inner and outer loop objective
functions, we can establish Theorem 1. $\square$

The Lipschitz continuity of the inner and outer loop objectives, as
established in Theorem 1, has significant implications for the convergence
properties of the joint optimization algorithm. In particular, it enables us
to derive convergence guarantees for both the inner and outer loop
optimization problems, which we will explore in the following sections.

###  3.2 Convergence of Joint Optimization

Now we study the convergence properties of the joint optimization problem for
falsification and fidelity optimization. We present a theorem that shows the
convergence of the joint optimization problem under specific conditions,
leveraging the Lipschitz continuity properties from Theorem 1.

Theorem 2. Suppose that the inner and outer loop objectives are Lipschitz
continuous with constants $L_{\rho}$ and $L_{\ell}$, respectively, as stated
in Theorem 1. Under suitable conditions on the optimization algorithm, the
joint optimization problem converges to an optimal solution.

Proof. The proof of Theorem 2 relies on the properties of the optimization
algorithm and the Lipschitz continuity of the inner and outer loop objectives.
For the inner loop optimization problem, we assume that the optimization
algorithm converges to a stationary point under suitable conditions. This is a
standard assumption for many optimization algorithms, such as gradient-based
methods, when applied to Lipschitz continuous objective functions. Since the
inner loop objective function $\rho_{\varphi}(e;f)$ is Lipschitz continuous,
the convergence of the inner loop optimization can be guaranteed under
suitable conditions. In a similar vein, for the outer loop optimization
problem, we assume that the optimization algorithm converges to a stationary
point under standard conditions. The Lipschitz continuity of the outer loop
objective function $\ell(\xi^{H},\xi^{L})$ ensures that the optimization
algorithm converges when applied to this objective function. By combining the
convergence properties of the inner and outer loop optimization problems, we
can establish the convergence of the joint optimization problem to an optimal
solution. $\square$

Theorem 2 provides a convergence guarantee for the joint optimization problem,
which is essential for the practical application of the proposed joint
optimization framework. The convergence properties ensure that the algorithm
will find an optimal solution, given that the optimization algorithm and the
objective functions satisfy the required conditions.

###  3.3 Interplay between Inner and Outer Loop Optimization

The joint optimization framework for falsification and fidelity optimization
involves a nested structure, with an inner loop optimization focused on
finding counterexamples and an outer loop optimization aiming to identify
optimal fidelity settings. In this section, we discuss the interplay between
these two optimization problems and the implications for the design and
analysis of joint optimization algorithms.

The nested optimization dynamics of the inner and outer loop problems are
intrinsically linked due to their shared dependence on environment
configurations and fidelity settings. The outer loop relies on the
counterexamples generated by the inner loop to evaluate the performance of
different fidelity settings, as shown in the objective function. In turn, the
fidelity settings chosen by the outer loop influence the search space and
complexity of the inner loop optimization, as reflected by the inner loop
objective function $\rho_{\varphi}(e;f)$. As a result, the interplay between
these two optimization problems creates a complex search process, where
improvements in one loop can potentially impact the performance of the other.

The joint optimization framework must balance the need for exploration and
exploitation in both the inner and outer loop optimization problems. In the
inner loop, exploration involves searching for new environment configurations
that can potentially lead to counterexamples, while exploitation focuses on
refining the current counterexamples to maximize their impact on the outer
loop optimization. Similarly, in the outer loop, exploration entails
experimenting with different fidelity settings to identify promising
configurations, whereas exploitation aims to fine-tune the fidelity settings
to minimize the discrepancy between high-fidelity and low-fidelity
simulations, as measured by the loss function $\ell$.

The interplay between the inner and outer loop optimization problems also
enables the development of _adaptive fidelity management_ strategies. By
monitoring the progress of the inner loop optimization and the quality of the
generated counterexamples, the outer loop can adaptively adjust the fidelity
settings to focus on regions of the search space where the discrepancies
between high-fidelity and low-fidelity simulations are the most significant.
This adaptive fidelity management can lead to more efficient joint
optimization algorithms that _dynamically_ allocate computational resources to
the most critical aspects of the problem.

Understanding the interplay between the inner and outer loop optimization
problems is crucial for the design and analysis of joint optimization
algorithms for falsification and fidelity optimization. Leveraging the
insights gained from the interplay between the inner and outer loop
objectives, such as the Lipschitz continuity established in Theorem 1 and the
convergence properties from Theorem 2, enables the development of algorithms
that effectively balance exploration and exploitation. These algorithms can
adaptively manage fidelity settings, leading to more efficient and effective
solutions for safety-critical systems. The relationship between the quality of
counterexamples and fidelity settings, as analyzed in Theorem 3, along with
the relationship between fidelity settings and counterexamples quality, as
explored in Theorem 4, further enhance our understanding of the complex
dynamics present in the joint optimization framework.

###  3.4 Sensitivity analysis of counterexamples to fidelity settings

We analyze the relationship between the quality of counterexamples and
fidelity settings in the context of the joint optimization framework for
falsification and fidelity optimization. The quality of a counterexample is
typically characterized by the robustness of the system specification
violation, as measured by the robustness value $\rho_{\varphi}(e;f)$. We aim
to understand how the choice of fidelity settings affects the quality of
counterexamples generated by the inner loop optimization.

Theorem 3. Given a set of fidelity settings $f\in\mathcal{F}$ and environment
configurations $\mathbf{e}\in\mathcal{E}$, there exists a constant $C>0$ such
that:

$\lvert\rho_{\varphi}(e_{1};f_{1})-\rho_{\varphi}(e_{1};f_{2})\rvert\leq
C\lVert f_{1}-f_{2}\rVert,$ (6)

for any $e_{1}\in\mathcal{E}$ and $f_{1},f_{2}\in\mathcal{F}$.

Proof. The proof of this theorem relies on the Lipschitz continuity of the
inner loop objective function $\rho_{\varphi}(e;f)$ with respect to fidelity
settings, as established in Theorem 1. Given the Lipschitz continuity
property, the difference in robustness values between two fidelity settings
$f_{1}$ and $f_{2}$ can be upper-bounded by a constant $C$ times the distance
between the fidelity settings in the fidelity space. This result highlights
the sensitivity of counterexample quality to the choice of fidelity settings,
which has important implications for the joint optimization process. Let us
denote the Lipschitz constant of the inner loop objective function with
respect to fidelity settings as $L_{f}>0$. Then, according to the Lipschitz
continuity of $\rho_{\varphi}(e;f)$, we have:

$\lvert\rho_{\varphi}(e_{1};f_{1})-\rho_{\varphi}(e_{1};f_{2})\rvert\leq
L_{f}\lVert f_{1}-f_{2}\rVert,$ (7)

for any $e_{1}\in\mathcal{E}$ and $f_{1},f_{2}\in\mathcal{F}$. This inequality
establishes an upper bound on the difference in robustness values for a fixed
environment configuration $\mathbf{e}_{1}$ and two different fidelity settings
$f_{1}$ and $f_{2}$. Now, let $C=L_{f}$, where $C>0$. Then, we can rewrite the
inequality as:

$\lvert\rho_{\varphi}(e_{1};f_{1})-\rho_{\varphi}(e_{1};f_{2})\rvert\leq
C\lVert f_{1}-f_{2}\rVert,$ (8)

for any $e_{1}\in\mathcal{E}$ and $f_{1},f_{2}\in\mathcal{F}$. This completes
the proof of Theorem 3. $\square$

This Theorem highlights the sensitivity of counterexample quality to the
choice of fidelity settings by providing an upper bound on the difference in
robustness values for different fidelity settings.

###  3.5 Sensitivity analysis of fidelity settings to counterexamples

This section focuses on understanding the sensitivity of the counterexamples
obtained by the inner loop optimization to changes in the fidelity settings.
This sensitivity analysis will provide insights into how the joint
optimization process is affected by the fidelity settings and the trade-offs
between fidelity and counterexample quality.

Theorem 4. Given the Lipschitz properties of the inner loop objective function
$\rho_{\varphi}(e;f)$ and the outer loop objective function $\ell$, the
sensitivity of the counterexamples obtained by the inner loop optimization to
changes in the fidelity settings can be characterized by sensitivity function
$S(f)$.

Proof. Let $S(f)$ be a sensitivity function defined as:

$S(f)=\frac{\partial\rho_{\varphi}(e^{*}(f);f)}{\partial f},$ (9)

where $e^{*}(f)$ represents the optimal environment configuration obtained by
the inner loop optimization for a given fidelity setting $f$. The sensitivity
function $S(f)$ quantifies the rate of change of the robustness value with
respect to the fidelity settings. A high sensitivity indicates that the
quality of counterexamples is significantly affected by changes in fidelity
settings, whereas a low sensitivity implies that the counterexamples are
relatively insensitive to such changes.

To understand the relationship between the sensitivity function and the
optimization process, we can analyze the gradient of the outer loop objective
function with respect to the fidelity settings:

$\frac{\partial\ell}{\partial
f}=\sum_{i=1}^{T}\sum_{j=1}^{M_{i}}\frac{\partial\ell\left(\xi_{i}^{H}\left(t_{i};p_{ij}\right),\xi_{i}^{L}\left(t_{i};f{p}_{ij},f\right)\right)}{\partial
f}.$ (10)

Studying the gradient of the outer loop objective function and its relation to
the sensitivity function $S(f)$ provides insights into the influence of
changes in fidelity settings on the optimization process and the quality of
counterexamples produced by the inner loop optimization. This information can
be useful for understanding the trade-offs between fidelity and counterexample
quality in the joint optimization framework.

###  3.6 Sample Complexity of Joint Optimization

In this section, we analyze the sample complexity of the joint optimization
problem, focusing on the relationship between the number of samples and the
convergence properties of the optimization process. Sample complexity is an
important consideration in optimization problems, as it quantifies the number
of samples required to achieve a desired level of accuracy or convergence.

Theorem 5. Given the strong convexity and Lipschitz continuity properties of
the inner and outer loop optimization problems, the total number of samples
$N$ required for the joint optimization problem can be expressed as a function
of the number of iterations in both loops and the number of samples per
iteration: $N=nK_{1}K_{2}$

Proof. The number of iterations required for the inner and outer loop
optimization problems to converge depends on the strong convexity and
Lipschitz continuity properties of the objective functions. However, we cannot
directly derive a closed-form expression for $K_{1}$ and $K_{2}$ based on
these properties. To determine the total number of samples required, we
consider the number of iterations in both the inner and outer loop
optimization problems. Suppose the inner loop optimization takes $K_{1}$
iterations to converge, and the outer loop optimization takes $K_{2}$
iterations to converge. Then, the total number of iterations, $K$, is the
product of the iterations in both loops: $K=K_{1}K_{2}$. Now, if we assume
that the number of samples per iteration is constant and equal to $n$, then
the total number of samples required, $N$, can be expressed as a function of
the total number of iterations, $K$. We have: $N=nK=nK_{1}K_{2}$.

Now we apply concentration inequalities to bound the deviation between the
true objective function and its empirical estimate. For simplicity, we will
assume that both the inner and outer loop optimization problems have finite
domains, and their objective functions are Lipschitz continuous. Let
$\hat{\rho}_{\varphi}(e;f)$ and $\hat{\ell}$ be the empirical estimates of the
inner loop objective function and the outer loop objective function,
respectively, computed using $n$ samples. By Lipschitz continuity, we have:

$\displaystyle|\rho_{\varphi}(e;f)-\hat{\rho}_{\varphi}(e;f)|$
$\displaystyle\leq L_{\rho}\|e-\hat{e}\|$ (11)
$\displaystyle|\ell\left(\xi^{H},\xi^{L}\right)-\hat{\ell}\left(\xi^{H},\xi^{L}\right)|$
$\displaystyle\leq
L_{\ell}\|\xi^{H}-\hat{\xi}^{H}\|+L_{\ell}\|\xi^{L}-\hat{\xi}^{L}\|$ (12)

Applying Hoeffding’s inequality, we can bound the probability that the
deviation between the true objective function and its empirical estimate is
larger than a given threshold. Specifically, we can show that:

$\displaystyle\mathbb{P}\left(\left|\rho_{\varphi}(e;f)-\hat{\rho}_{\varphi}(e;f)\right|>\epsilon\right)\leq
2\exp\left(-\frac{n\epsilon^{2}}{2L_{\rho}^{2}}\right)$ (13)
$\displaystyle\mathbb{P}\left(\left|\ell\left(\xi^{H},\xi^{L}\right)-\hat{\ell}\left(\xi^{H},\xi^{L}\right)\right|>\epsilon\right)\leq
2\exp\left(-\frac{n\epsilon^{2}}{2L_{\ell}^{2}}\right)$ (14)

To achieve an $\epsilon$-approximate solution with probability at least
$1-\delta$, we can set the right-hand side of these inequalities to be less
than or equal to $\delta$ and solve for $n$. This gives us:

$n\geq\frac{2L_{\rho}^{2}}{\epsilon^{2}}\log\left(\frac{2}{\delta}\right)\quad\text{
and }\quad
n\geq\frac{2L_{\ell}^{2}}{\epsilon^{2}}\log\left(\frac{2}{\delta}\right)$ (15)

These bounds can be used to inform the choice of the number of samples per
iteration, $n$. However, we cannot directly derive a closed-form expression
for the total number of samples from these bounds. Instead, we can use these
bounds as guidelines to choose the number of samples per iteration, and then
use the relationship $N=nK_{1}K_{2}$ to compute the number of samples required
for joint optimization.

##  4 Regret Bounds Analysis for Bayesian Optimization

Building upon the theoretical foundations discussed previously, we will now
further explore the performance of our approach, with a particular emphasis on
using Bayesian optimization for the outer loop optimization problems. The
selection of an optimization algorithm can greatly impact the efficiency of
the proposed joint optimization framework. [7, 14]. Its utilization of a
probabilistic model to estimate the objective function and an acquisition
function to guide the search makes it particularly effective when dealing with
costly or noisy evaluations. This has led to its successful application in
various domains, including hyperparameter tuning in machine learning [17],
design optimization in engineering [3], and decision-making under uncertainty
[2].

Theorem 6. When using Bayesian optimization with the GP-UCB acquisition
function for the outer loop optimization (fidelity settings optimization), the
optimization process converges to the optimal fidelity settings $f^{*}$ with
high probability, and the cumulative regret after $T$ iterations is bounded by
$\mathcal{O}(\sqrt{T})$.

Proof. We begin by stating the GP-UCB acquisition function as follows:

$\alpha_{t}(f)=\mu_{t}(f)+\sqrt{\beta_{t}}\sigma_{t}(f)$ (16)

where $\mu_{t}(f)$ and $\sigma_{t}^{2}(f)$ are the posterior mean and variance
of the Gaussian process at fidelity settings $f$ after $t$ iterations, and
$\beta_{t}$ is the exploration parameter. We define the instantaneous regret
at iteration $t$ as the difference between the optimal objective function
value and the value obtained at the chosen fidelity settings:

$r_{t}=\ell\left(f^{*}\right)-\ell\left(f_{t}\right)$ (17)

where $f^{*}$ is the optimal fidelity settings and $\mathbf{f}_{t}$ is the
fidelity settings chosen by Bayesian optimization at iteration $t$. The
cumulative regret after $T$ iterations is given by:
$R_{T}=\sum_{t=1}^{T}r_{t}$. To bound the cumulative regret, we use the
following inequality based on the GP-UCB acquisition function:

$r_{t}\leq\sqrt{\beta_{t}}\sigma_{t}\left(f_{t}\right)+\frac{1}{2}\left(\mu_{t}\left(f^{*}\right)-\mu_{t}\left(f_{t}\right)\right)$
(18)

This inequality follows from the fact that the GP-UCB acquisition function
balances exploration and exploitation. By summing both sides of this
inequality over $t=1,\dots,T$, we obtain a bound on the cumulative regret:

$R_{T}\leq\sum_{t=1}^{T}\left(\sqrt{\beta_{t}}\sigma_{t}\left(f_{t}\right)+\frac{1}{2}\left(\mu_{t}\left(f^{*}\right)-\mu_{t}\left(f_{t}\right)\right)\right)$
(19)

Now, we use the following properties of Gaussian processes:

  1. 1.

The posterior variance of the Gaussian process at the optimal fidelity
settings $f^{*}$ decreases monotonically with the number of iterations:
$\sigma_{t+1}(f^{*})\leq\sigma_{t}(f^{*})$.

  2. 2.

The posterior mean of the Gaussian process converges to the true objective
function value at the optimal fidelity settings
$\lim_{t\rightarrow\infty}\mu_{t}\left(f^{*}\right)=\ell\left(f^{*}\right)$

Using these properties, we can show that
$\sum_{t=1}^{T}\left(\sqrt{\beta_{t}}\sigma_{t}(f_{t})+\frac{1}{2}\left(\mu_{t}(f^{*})-\mu_{t}(f_{t})\right)\right)$
converges to a finite value as $T\to\infty$. Specifically, we can upper-bound
the sum by $\mathcal{O}(\sqrt{T})$. This implies that the cumulative regret is
bounded by:

$R_{T}\leq\mathcal{O}(\sqrt{T})$ (20)

This result shows that, with high probability, the Bayesian optimization
process converges to the optimal fidelity settings $f^{*}$, and the cumulative
regret is bounded by $\mathcal{O}(\sqrt{T})$ after $T$ iterations.

##  5 Additional Insights

In this section, we will delve further into the insights we have gained from
our nested optimization framework. Specifically, we will explore three key
areas: adaptive fidelity management, stability analysis, and robustness
analysis. Together with the theorems we have discussed, these insights help us
better comprehend the intricate dynamics at play within our joint optimization
framework.

###  5.1 Adaptive Fidelity Management

One important feature of our joint optimization approach is its ability to
dynamically adjust fidelity settings. During the optimization process, our
algorithm adapts the fidelity based on information from both the inner and
outer loop optimizations. This flexibility helps the algorithm balance between
exploring new options and making the most of known options, all while keeping
computational costs low. In practice, this means the algorithm focuses on
parts of the search space that seem promising or uncertain.

###  5.2 Stability Analysis

We could also analyze stability to learn more about the convergence and
stability of our joint optimization framework. The insights from Theorem 1 and
Theorem 2, which deal with Lipschitz continuity and convergence properties,
help us understand the stability of our proposed approach. With these
insights, we can study the stability of both the inner and outer loop
optimization processes under different conditions, such as changes in fidelity
settings and different environment configurations. In the end, this analysis
helps us create algorithms that are more robust against uncertainties.

###  5.3 Robustness Analysis

Robustness analysis is about evaluating how our joint optimization framework
performs when faced with varying levels of uncertainty and environmental
noise, both in terms of configurations and simulator dynamics. By studying how
our framework behaves under these conditions, we can pinpoint potential
vulnerabilities to bolster its robustness. To carry out this analysis, we
assess the impact of noise and uncertainty on the performance of both the
inner and outer loop optimization processes. This might involve deriving
robustness bounds or establishing worst-case performance guarantees, as well
as exploring how fidelity settings affect the sensitivity of the optimization
process to noise and uncertainty. Through comprehensive robustness analysis,
we can confidently assert that our proposed approach is well-equipped to
handle uncertainties in environment configurations and simulator dynamics.

##  6 Conclusions

We presented a mathematical formulation for joint falsification and fidelity
setting optimization, which addresses the challenge of efficiently validating
the safety of autonomous systems. The proposed framework brings together the
two critical aspects of the problem, namely, the falsification of learning-
enabled systems and the optimization of simulator fidelity settings. Our
approach enables a more efficient exploration strategy for searching potential
failure scenarios by focusing on the most critical environmental
configurations that challenge the control algorithms. We have derived a set of
six key theorems to establish the fundamental properties and relationships in
the joint optimization problem. These theorems encompass a range of important
aspects, including sensitivity analysis, sample complexity, convergence, the
interplay between the outer and inner loops, and the regret bound analysis
when employing Bayesian optimization. The insights gained from these theorems
provide a foundation for the development of efficient algorithms in this
domain. As a future direction, we aim to conduct extensive empirical
evaluations of our approach on various autonomous systems to demonstrate its
practical applicability and effectiveness in improving safety validation.

## References

  * [1] Abbaspour Asadollah, S., Inam, R., Hansson, H.: A survey on testing for cyber physical system. In: International Conference on Testing Software and Systems. pp. 194–207. Springer (2015)
  * [2] Baheri, A., Bin-Karim, S., Bafandeh, A., Vermillion, C.: Real-time control using Bayesian optimization: A case study in airborne wind energy systems. Control Engineering Practice 69, 131–140 (2017)
  * [3] Baheri, A., Ramaprabhu, P., Vermillion, C.: Iterative 3D layout optimization and parametric trade study for a reconfigurable ocean current turbine array using Bayesian optimization. Renewable Energy (2018)
  * [4] Beard, J.J., Baheri, A.: Safety verification of autonomous systems: A multi-fidelity reinforcement learning approach. arXiv preprint arXiv:2203.03451 (2022)
  * [5] Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Annals of Operations Research 153, 235–256 (2007)
  * [6] Deshmukh, J., Horvat, M., Jin, X., Majumdar, R., Prabhu, V.S.: Testing cyber-physical systems through Bayesian optimization. ACM Transactions on Embedded Computing Systems (TECS) 16(5s), 1–18 (2017)
  * [7] Frazier, P.I.: A tutorial on Bayesian optimization. arXiv preprint arXiv:1807.02811 (2018)
  * [8] Koopman, P., Wagner, M.: Challenges in autonomous vehicle testing and validation. SAE International Journal of Transportation Safety 4(1), 15–24 (2016)
  * [9] Koren, M., Nassar, A., Kochenderfer, M.J.: Finding failures in high-fidelity simulation using adaptive stress testing and the backward algorithm. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 5944–5949 (2021)
  * [10] Lee, R., Kochenderfer, M.J., Mengshoel, O.J., Brat, G.P., Owen, M.P.: Adaptive stress testing of airborne collision avoidance systems. In: 2015 IEEE/AIAA 34th Digital Avionics Systems Conference (DASC). pp. 6C2–1. IEEE (2015)
  * [11] Mathesen, L., Yaghoubi, S., Pedrielli, G., Fainekos, G.: Falsification of cyber-physical systems with robustness uncertainty quantification through stochastic optimization with adaptive restart. In: IEEE International Conference on Automation Science and Engineering (CASE). pp. 991–997 (2019)
  * [12] Ramezani, Z., Claessen, K., Smallbone, N., Fabian, M., Åkesson, K.: Testing cyber–physical systems using a line-search falsification method. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 41(8), 2393–2406 (2021)
  * [13] Shahrooei, Z., Kochenderfer, M.J., Baheri, A.: Falsification of learning-based controllers through multi-fidelity Bayesian optimization. arXiv preprint arXiv:2212.14118 (2022)
  * [14] Snoek, J., Larochelle, H., Adams, R.P.: Practical Bayesian optimization of machine learning algorithms. Advances in neural information processing systems 25 (2012)
  * [15] Tuncali, C.E., Fainekos, G.: Rapidly-exploring random trees for testing automated vehicles. In: 2019 IEEE Intelligent Transportation Systems Conference (ITSC). pp. 661–666. IEEE (2019)
  * [16] Wang, X., Nair, S., Althoff, M.: Falsification-based robust adversarial reinforcement learning. In: IEEE International Conference on Machine Learning and Applications (ICMLA). pp. 205–212 (2020)
  * [17] Wu, J., Chen, X.Y., Zhang, H., Xiong, L.D., Lei, H., Deng, S.H.: Hyperparameter optimization for machine learning models based on bayesian optimization. Journal of Electronic Science and Technology 17(1), 26–40 (2019)
  * [18] Yamagata, Y., Liu, S., Akazaki, T., Duan, Y., Hao, J.: Falsification of cyber-physical systems using deep reinforcement learning. IEEE Transactions on Software Engineering 47(12), 2823–2840 (2020)
  * [19] Zhang, Z., Arcaini, P., Hasuo, I.: Hybrid system falsification under (in)equality constraints via search space transformation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39(11), 3674–3685 (2020)
  * [20] Zhang, Z., Lyu, D., Arcaini, P., Ma, L., Hasuo, I., Zhao, J.: Effective hybrid system falsification using Monte Carlo tree search guided by QB-robustness. In: Computer Aided Verification: 33rd International Conference, CAV 2021, Virtual Event, July 20–23, 2021, Proceedings, Part I. pp. 595–618. Springer (2021)