$\displaystyle=\Phi^{-1}(\tilde{D}_{11}^{\top}(\tilde{C}_{1}x_{\tau}+\tilde{D}_{10}w_{\tau})+\tilde{B}_{1}^{\top}Y_{\tau+1}\phi_{\tau}),$

where we have assumed that $\Phi$ is PD for all $\tau$. Substituting the above
quantities back into the objective, the quantity inside of the expectation
simplifies to

$\displaystyle($
$\displaystyle\tilde{C}_{1}x_{t}+\tilde{D}_{10}w_{t})^{\top}(\tilde{C}_{1}x_{t}+\tilde{D}_{10}w_{t})+\phi_{t}^{\top}Y_{\tau+1}\phi_{t}$
$\displaystyle+(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}x_{t}+\tilde{D}_{11}^{\top}\tilde{D}_{10}w_{\tau}+\tilde{B}_{1}^{\top}Y_{\tau+1}\phi_{\tau})^{\top}\Phi^{-1}(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}x_{t}+\tilde{D}_{11}^{\top}\tilde{D}_{10}+\tilde{B}_{1}^{\top}Y_{\tau+1}\phi_{\tau})+q_{\tau+1}.$

Substituting in $\phi_{\tau}=\tilde{A}x_{\tau}+\tilde{B}_{0}w_{\tau}$, we may
evaluate the expectation of the above quantity, recalling that $x_{\tau}$ and
$w_{\tau}$ are independent, and $w_{\tau}$ is zero mean.

$\displaystyle\mathbb{E}\bigg{[}($
$\displaystyle\tilde{C}_{1}x_{t}+\tilde{D}_{10}w_{t})^{\top}(\tilde{C}_{1}x_{t}+\tilde{D}_{10}w_{t})+\phi_{t}^{\top}Y_{\tau+1}\phi_{t}$
$\displaystyle+(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}x_{t}+\tilde{D}_{11}^{\top}\tilde{D}_{10}w_{\tau}+\tilde{B}_{1}^{\top}Y_{\tau+1}\phi_{\tau})^{\top}\Phi^{-1}(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}x_{t}+\tilde{D}_{11}^{\top}\tilde{D}_{10}+\tilde{B}_{1}^{\top}Y_{\tau+1}\phi_{\tau})+q_{\tau+1}\bigg{]}$
$\displaystyle=q_{\tau+1}+\operatorname{Tr}\mathopen{}\left(\Sigma_{w}\mathopen{}\left[\tilde{D}_{20}^{\top}\tilde{D}_{20}+\tilde{B}_{0}^{\top}Y_{\tau+1}\tilde{B}_{0}+(\tilde{D}_{10}^{\top}\tilde{D}_{11}+\tilde{B}_{0}^{\top}Y_{\tau+1}\tilde{B}_{1})\Phi^{-1}(\tilde{D}_{10}^{\top}\tilde{D}_{11}+\tilde{B}_{0}^{\top}Y_{\tau+1}\tilde{B}_{1})^{\top}\right]\mathclose{}\right)\mathclose{}$
$\displaystyle\qquad\qquad+\operatorname{Tr}\mathopen{}\left(\Sigma_{\tau}\mathopen{}\left[\tilde{C}_{1}^{\top}\tilde{C}_{1}+\tilde{A}^{\top}Y_{\tau+1}\tilde{A}+(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}+\tilde{B}_{1}^{\top}Y_{\tau+1}\tilde{A})^{\top}\Phi^{-1}(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}+\tilde{B}_{1}^{\top}Y_{\tau+1}\tilde{A})\right]\mathclose{}\right)\mathclose{}.$

Thus the optimal filter gain at time $\tau$ is given by the solution to

$\displaystyle\min_{L_{\tau},N_{\tau}}$
$\displaystyle\operatorname{Tr}\mathopen{}\left(\Sigma_{w}\mathopen{}\left[\tilde{D}_{20}^{\top}\tilde{D}_{20}+\tilde{B}_{0}^{\top}Y_{\tau+1}\tilde{B}_{0}+(\tilde{D}_{10}^{\top}\tilde{D}_{11}+\tilde{B}_{0}^{\top}Y_{\tau+1}\tilde{B}_{1})\Phi^{-1}(\tilde{D}_{10}^{\top}\tilde{D}_{11}+\tilde{B}_{0}^{\top}Y_{\tau+1}\tilde{B}_{1})^{\top}\right]\mathclose{}\right)\mathclose{}$
$\displaystyle\qquad\qquad+\operatorname{Tr}\mathopen{}\left(\Sigma_{\tau}\mathopen{}\left[\tilde{C}_{1}^{\top}\tilde{C}_{1}+\tilde{A}^{\top}Y_{\tau+1}\tilde{A}+(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}+\tilde{B}_{1}^{\top}Y_{\tau+1}\tilde{A})^{\top}\Phi^{-1}(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}+\tilde{B}_{1}^{\top}Y_{\tau+1}\tilde{A})\right]\mathclose{}\right)\mathclose{}.$

Note that the minimization problem is convex, as it is the result of a
pointwise supremum. Therefore, it can be solved efficiently using standard
solvers.

Under a gains which satisfies this, the cost function progresses according to

$\displaystyle Y_{\tau}$
$\displaystyle=\tilde{C}_{1}^{\top}\tilde{C}_{1}+\tilde{A}^{\top}Y_{\tau+1}\tilde{A}+(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}+\tilde{B}_{1}^{\top}Y_{\tau+1}\tilde{A})^{\top}\Phi^{-1}(\tilde{D}_{1,1}^{\top}\tilde{C}_{1}+\tilde{B}_{1}^{\top}Y_{\tau+1}\tilde{A})).$

This gives us a backwards recursion to find the cost matrices. Under these
adversarial perturbations and controller gains, the state dynamics progress
such that $x_{\tau}\sim\mathcal{N}(0,\Sigma_{\tau})$, where $\Sigma_{\tau}$
evolves according to

$\displaystyle\Sigma_{\tau+1}$
$\displaystyle=\mathopen{}\left[(I+\tilde{B}_{1}\Phi^{-1}\tilde{B}_{1}^{\top}Y_{t+1})\tilde{A}+\tilde{B}_{1}\Phi^{-1}\tilde{D}_{11}^{\top}\tilde{C}_{1}\right]\mathclose{}\Sigma_{\tau}\mathopen{}\left[(I+\tilde{B}_{1}\Phi^{-1}\tilde{B}_{1}^{\top}Y_{\tau+1})\tilde{A}+\tilde{B}_{1}\Phi^{-1}\tilde{D}_{11}^{\top}\tilde{C}_{1}\right]\mathclose{}^{\top}$
$\displaystyle\qquad\qquad+\mathopen{}\left((I+\tilde{B}_{1}\Phi^{-1}\tilde{B}_{1}^{\top}Y_{\tau+1})\tilde{B}_{0}+\tilde{B}_{1}\Phi^{-1}\tilde{D}_{11}^{\top}\tilde{D}_{10}\right)\mathclose{}\Sigma_{w}\mathopen{}\left((I+\tilde{B}_{1}\Phi^{-1}\tilde{B}_{1}^{\top}Y_{\tau+1})\tilde{B}_{0}+\tilde{B}_{1}\Phi^{-1}\tilde{D}_{11}^{\top}\tilde{D}_{10}\right)\mathclose{}^{\top}.$

Passing the same argument to an infinite horizon setting, we find that our
gains must satisfy the conditions given in the statement.

To verify that the restriction of the parameter search space to static
matrices of the form $\begin{bmatrix}L_{\gamma}\\\ N_{\gamma}\end{bmatrix}$ is
sufficient, observe the following fact, as in Doyle et al. (1989b):

$\displaystyle\inf_{K}\limsup_{T}$
$\displaystyle\frac{1}{T}\mathbb{E}_{w}\mathopen{}\left[\sum_{t=0}^{T-1}\left\|\nu_{t}\right\|^{2}-\left\|r_{t}\right\|^{2}|r\textrm{
given}\right]\mathclose{}$
$\displaystyle\leq\inf_{K}\limsup_{T}\frac{1}{T}\mathbb{E}_{w}\mathopen{}\left[\sup_{r\textrm{
causal}}\sum_{t=0}^{T-1}\left\|\nu_{t}\right\|^{2}-\left\|r_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle\leq\limsup_{T}\frac{1}{T}\mathbb{E}_{w}\mathopen{}\left[\sup_{r\textrm{
causal}}\sum_{t=0}^{T-1}\left\|\nu_{t}\right\|^{2}-\left\|r_{t}\right\|^{2}|K\textrm{
given}\right]\mathclose{}.$

With $K$ given by $\begin{bmatrix}L_{\gamma}\\\ N_{\gamma}\end{bmatrix}$,
where $L_{\gamma}$ and $N_{\gamma}$ satsify (41), the right hand side is equal
to the left hand side, where $r$ is given as
$r_{t}=\Phi^{-1}(\tilde{D}_{11}^{\top}\tilde{C}_{1}x_{t}+\tilde{B}_{1}^{\top}Y_{\gamma}(\tilde{A}x_{t}+\tilde{B}_{0}w_{t}))$.
To see that this is the case, note that under this adversarial perturbation,
the problem on the left reduces to a Kalman Filtering problem, where the
optimal gain is static. $\blacksquare$

The proof of Lemma 2.2 hinges on sequential integration of the results
presented in this section.

###  A.3 Proof of Theorem 2.1: Hard Constrained Output Feedback Solution

The following lemma will be useful.

###### Lemma A.4

Consider a stable system driven by noise

$x_{t+1}=Ax_{t}+Bw_{t},$

where $x_{0}\sim\mathcal{N}(0,I)$ and
$w_{t}\overset{(iid)}{\sim}\mathcal{N}(0,\Sigma_{w})$. Then for any quadratic
function $f(x_{t})=x_{t}^{\top}Vx_{t}+x_{t}^{\top}b+c$,

$\limsup_{T}\frac{1}{T}\sum_{t=0}^{T-1}f(x_{t})=\limsup_{t}\mathbb{E}\mathopen{}\left[f(x_{t})\right]\mathclose{}.$

Proof: Let $\tilde{x}_{0}\sim\mathcal{N}(0,\Sigma_{\infty})$, where

$\Sigma_{\infty}=\limsup_{t}\mathbb{E}\mathopen{}\left[x_{t}x_{t}^{\top}\right]\mathclose{}=\textnormal{{dlyap}}(A,BB^{\top}).$

Also let $\tilde{x}_{t}$ follow the same dynamics of $x_{t}$ rolled out under
the same noise realization. We have that $\tilde{x}_{t}$ is ergodic. Then we
may express

$\displaystyle\limsup_{T}$
$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}f(x_{t})=\limsup_{T}\frac{1}{T}\sum_{t=0}^{T-1}f(\tilde{x}_{t}+(x_{t}-\tilde{x}_{t}))$
$\displaystyle=\limsup_{T}\frac{1}{T}\sum_{t=0}^{T-1}f(\tilde{x}_{t}+(x_{t}-\tilde{x}_{t}))$
$\displaystyle=\limsup_{T}\frac{1}{T}\sum_{t=0}^{T-1}f(\tilde{x}_{t})+(x_{t}-\tilde{x}_{t})^{\top}V(x_{t}-\tilde{x}_{t})+2(x_{t}-\tilde{x}_{t})^{\top}V\tilde{x}_{t}+(x_{t}-\tilde{x}_{t})^{\top}b$
$\displaystyle=\limsup_{t}\mathbb{E}\mathopen{}\left[f(\tilde{x}_{t})\right]\mathclose{}+\limsup_{T}\sum_{t=0}^{T-1}\mathopen{}\left(A^{t}(x_{0}-\tilde{x}_{0})\right)\mathclose{}^{\top}VA^{t}(x_{0}-\tilde{x}_{0})+2\mathopen{}\left(A^{t}(x_{0}-\tilde{x}_{0})\right)\mathclose{}^{\top}V\tilde{x}_{t}+\mathopen{}\left(A^{t}(x_{0}-\tilde{x}_{0})\right)\mathclose{}^{\top}b$
$\displaystyle=\limsup_{t}\mathbb{E}\mathopen{}\left[f(x_{t})\right]\mathclose{},$

as $\rho(A)<1$ implies that the the quantity in the sum may be bounded by a
constant. $\blacksquare$

###### Lemma A.5

(Ergodicity) Let $K$ be any LTI controller that internally stabilizes the
system in the face of the optimal $\gamma$-soft-constrained adversarial
perturbations. Then

$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mathrm{causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}=\limsup_{T\to\infty}\frac{1}{T}\max_{\delta\mathrm{causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}.$

Proof: To see that this is so, observe that the optimal adversarial
perturbation may be expressed

$\displaystyle\delta_{t}=\Delta_{x}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+\Delta_{w}w_{t},$

for some $\Delta_{x}$ and $\Delta_{w}$ defined in terms of the closed loop
system and $\gamma$. Here $x_{t}^{(K)}$ denotes the state of the controller.
Under this perturbation, the dynamics of the closed loop system becomes

$\displaystyle\begin{bmatrix}x_{t+1}\\\ x_{t+1}^{(K)}\end{bmatrix}$
$\displaystyle=A_{cl}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+B_{cl}w_{t},$ $\displaystyle z_{t}$
$\displaystyle=C_{cl}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+D_{cl}w_{t},$

where $A_{cl}$ has eigenvalues in the open unit disc, by the fact that $K$ is
internally stabilizing. Then by Lemma A.4,

$\displaystyle\limsup_{T\to\infty}\max_{\delta\mathrm{causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}$
$\displaystyle=$
$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\left\|C_{cl}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+D_{cl}w_{t}\right\|^{2}-\gamma^{2}\left\|\Delta_{x}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+\Delta_{w}w_{t}\right\|^{2}$ $\displaystyle=$
$\displaystyle\limsup_{t\to\infty}\mathbb{E}\mathopen{}\left[\left\|C_{cl}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+D_{cl}w_{t}\right\|^{2}-\gamma^{2}\left\|\Delta_{x}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+\Delta_{w}w_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle=$
$\displaystyle\limsup_{t\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\sum_{t=0}^{T-1}\left\|C_{cl}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+D_{cl}w_{t}\right\|^{2}-\gamma^{2}\left\|\Delta_{x}\begin{bmatrix}x_{t}\\\
x_{t}^{(K)}\end{bmatrix}+\Delta_{w}w_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mathrm{causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}.$

$\blacksquare$

Now we are ready to prove Theorem 2.1.

Proof: First note that optimization problem

$\max_{\begin{subarray}{c}\mathbf{\delta}\mbox{ causal}\\\
\left\|\mathbf{\delta}\right\|_{\ell_{2}}^{2}\leq
T\varepsilon\end{subarray}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}$

is the maximization of a quadratic function subject to a quadratic constraint,
and therefore satisfies strong duality (see Boyd and Vandenberghe (2004),
Appendix B.1). Therefore, maximizing subject to the quadratic constraint is
equivalent to maximizing the Lagrangian, then minimizing over the dual
variable.

$\displaystyle\max_{\begin{subarray}{c}\mathbf{\delta}\mbox{ causal}\\\
\left\|\mathbf{\delta}\right\|_{\ell_{2}}^{2}\leq
T\varepsilon\end{subarray}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}=\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\max_{\mathbf{\delta}\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}.$

Then the minimization of objective (5) is equivalent to

$\displaystyle\operatorname*{minimize}_{u}\limsup_{T}\frac{1}{T}\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\max_{\mathbf{\delta}\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}.$

Our next step is to show that we may pull the minimization over $\gamma$
outside of the expectation. To see that this is the case, we will make use of
ergodicity.

By Assumption 2.1, we have that

$\displaystyle\infty$
$\displaystyle>\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\limsup_{T\to\infty}\min_{u_{0},\dots,u_{T-1}}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}.$

Now, for each $\gamma\geq\gamma_{LB}$ let $K_{\gamma}$ be the controller
defined in Lemma 2.2 and let $u_{t}=K_{\gamma}(y_{-\infty:t})$. Then

$\displaystyle\quad\quad\,\,\,\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle=\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}\right]\mathclose{}$
$\displaystyle=\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\limsup_{T\to\infty}\frac{1}{T}\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle\geq\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}.$

Where the first equality is permitted by the fact that first line is not
random. The second line follows from ergodicity (Lemma A.5). The inequality is
a result of Fatou’s Lemma and the $\min$-$\max$ inequality. We can similarly
obtain an upper bound:

$\displaystyle\quad\quad\,\,\,\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle=\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}\right]\mathclose{}$
$\displaystyle=\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\frac{1}{T}\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}$
$\displaystyle\leq\liminf_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\left\|\delta_{t}\right\|^{2}\right]\mathclose{}.$

Combining these results, we see that

$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon
T+\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}$
$\displaystyle=\min_{\gamma\geq\gamma_{LB}}\gamma^{2}\varepsilon+\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}\sum_{t=0}^{T-1}\left\|z_{t}\right\|^{2}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}.$

Therefore, we see that the optimal solution is given by Lemma 2.2 for some
properly chosen $\gamma$. Now, observe that i) the power of the optimal
adversary for the problem at some level $\gamma$,
$\lim_{t}\mathbb{E}\mathopen{}\left[\mathopen{}\left(\delta_{t}^{\gamma}\right)\mathclose{}^{\top}\delta_{t}^{\gamma}\right]\mathclose{}$
is decreasing as $\gamma$ increases, and ii) the power of the optimal
adversary for the hard constrained problem (10) will equal $\varepsilon$. Then
bisecting such that the adversarial power of the solution to Lemma 2.2 is
correct provides the proper level $\gamma$.

Algorithm 2 relies on the adversarial power computed in Algorithm 3. To verify
correctness of this algorithm we observe that for a closed-loop system
$G_{cl}=\left[\begin{array}[]{c|cc}A_{cl}&B_{0,cl}&B_{1,cl}\\\ \hline\cr
C_{cl}&D_{0,cl}&D_{1,cl}\end{array}\right]$, the optimal adversary found using
dynamic programming arguments as in the proofs of Lemma 2.1 and Lemma 2.2. In
particular, we have
$\delta_{t}^{\gamma}=\Phi^{-1}\Gamma_{x}x_{t}+\Phi^{-1}\Gamma_{w}w_{t}$, where
$\Phi$, $\Gamma_{x}$ and $\Gamma_{w}$ are as in Algorithm 3. Then

$\displaystyle\lim_{t}\operatorname{\textbf{E}}\mathopen{}\left[\delta_{t}^{\gamma}\mathopen{}\left(\delta_{t}^{\gamma}\right)\mathclose{}^{\top}\right]\mathclose{}=\operatorname{Tr}(\Gamma_{w}^{\top}\Phi^{-2}\Gamma_{w})+\operatorname{Tr}(\Gamma_{x}^{\top}\Phi^{-2}\Gamma_{x}\Sigma_{\gamma}),$

where $\Sigma_{\gamma}$ is the covariance of the state under the optimal
adversarial perturbation and may be computed as the solution to the lyapunov
equation appearing in Algorithm 3.

$\blacksquare$

##  Appendix B Proofs for Section 3

We introduce the following recurring fact: given a solution $P_{\gamma}$ to
the DARE in Lemma 2.1, we have

$\displaystyle x_{0}^{\top}P_{\gamma}x_{0}$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\mathopen{}\left(\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}\mathopen{}\left(Q+F_{\gamma}^{\top}RF_{\gamma}\right)\mathclose{}x_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right)\mathclose{}.$
(42)

In other words, $x_{0}^{\top}P_{\gamma}x_{0}$ is the soft-constrained cost of
the optimal adversarially robust controller against the optimal adversary at
level $\gamma$ in the noiseless setting, with initial condition $x_{0}$.

###  B.1 Proof of Lemma 3.1

The following lemma from Mania et al. (2019) will be helpful.

###### Lemma B.1

(Lemma 1 in Mania et al. (2019)) Let $f_{1}$ and $f_{2}$ be $\mu$-strongly
convex twice differentiable functions functions. Let
$x_{1}=\operatorname*{argmin}_{x}f_{1}(x)$ and
$x_{2}=\operatorname*{argmin}_{x}f_{2}(x)$. Suppose $\left\|\nabla
f_{1}(x_{2})\right\|\leq\varepsilon$. Then
$\left\|x_{1}-x_{2}\right\|\leq\frac{\varepsilon}{\mu}$.

We also consider an analogous lemma which provides a lower bound.

###### Lemma B.2

Suppose $f_{1}$ and $f_{2}$ are $L$-Lipschitz function, and let $x_{1}$
minimize $f_{1}$ and $x_{2}$ minimize $f_{2}$. If $\left\|\nabla
f_{1}(x_{2})\right\|\geq\varepsilon$, then
$\left\|x_{1}-x_{2}\right\|\geq\frac{\varepsilon}{L}$.

Proof: By a Taylor expansion of $\nabla f_{1}$ about $x_{1}$, we see that

$\displaystyle\nabla f_{1}(x_{2})=\nabla
f_{1}(x_{1})+\nabla^{2}f_{1}(\tilde{x})(x_{2}-x_{1})$

where $\tilde{x}=tx_{1}+(1-t)x_{2}$ for some $t\in[0,1]$. As $x_{1}$ minimizes
$f_{1}$, we must have $\nabla f_{1}(x_{1})=0$. Futhermore, by the fact that
$f_{1}$ is $L$ Lipschitz, we have that

$\displaystyle\left\|\nabla f_{1}(x_{2})\right\|=\left\|\nabla
f_{1}(x_{1})+\nabla^{2}f_{1}(\tilde{x})(x_{2}-x_{1})\right\|=\left\|\nabla^{2}f_{1}(\tilde{x})(x_{2}-x_{1})\right\|\leq
L\left\|x_{2}-x_{1}\right\|$

Dividing both sides of the above inequality by $L$ and leveraging the
assumption that $\left\|\nabla f_{1}(x_{2})\right\|\leq\varepsilon$ provides
the desired result. $\blacksquare$

Armed with these lemmas, we may prove Lemma 3.1.

Proof: First, note that both functions are strongly convex with parameter
$\sigma_{\min}(R+B^{\top}PB)$, and Lipschitz continuous with parameter
$\left\|R+B^{\top}MB\right\|$.

For any $x$, by the fact that $\nabla f_{2}(u_{2},x)=0$, we have

$\displaystyle\nabla f_{1}(u_{2},x)$ $\displaystyle=\nabla
f_{1}(u_{2},x)-\nabla f_{2}(u_{2},x)$
$\displaystyle=(R+B^{\top}MB)u_{2}+B^{\top}MAx-(R+B^{\top}PB)u_{2}-B^{\top}PAx$
$\displaystyle=B^{\top}(M-P)(A+BF_{2})x,$

and thus

$\displaystyle\left\|\nabla
f_{1}(u_{2},x)\right\|=\left\|B^{\top}(M-P)(A+BF_{2})x\right\|.$

Then by application of Lemma B.1 and Lemma B.2, we have that for any $x$,
$\left\|u_{1}-u_{2}\right\|=\left\|(F_{1}-F_{2})x\right\|$ satisfies

$\displaystyle\frac{\left\|B^{\top}(M-P)(A+BF_{2})x\right\|}{\left\|R+B^{\top}MB\right\|}\leq\left\|(F_{1}-F_{2})x\right\|\leq\frac{\left\|B^{\top}(M-P)(A+BF_{2})x\right\|}{\sigma_{\min}(R+B^{\top}PB)}.$

Taking the supremum over $\left\|x\right\|=1$, we find

$\displaystyle\frac{\left\|B^{\top}(M-P)(A+BF_{2})\right\|}{\left\|R+B^{\top}MB\right\|}\leq\left\|F_{1}-F_{2}\right\|\leq\frac{\left\|B^{\top}(M-P)(A+BF_{2})\right\|}{\sigma_{\min}(R+B^{\top}PB)}.$

$\blacksquare$

###  B.2 Proofs for Section 3.1

From the upper bound in Equation (28), we need to bound
$\left\|\Sigma(F_{\gamma})\right\|$ and $\left\|F_{\gamma}-F_{\star}\right\|$.
For $\left\|\Sigma(F_{\gamma})\right\|$, we have by definition:

$\displaystyle\left\|\Sigma(F_{\gamma})\right\|$
$\displaystyle:=\left\|\sum_{t=0}^{\infty}(A+BF_{\gamma})^{t}\Sigma_{w}{(A+BF_{\gamma})^{\top}}^{t}\right\|$
$\displaystyle=\sigma_{w}^{2}\left\|\sum_{t=0}^{\infty}(A+BF_{\gamma})^{t}{(A+BF_{\gamma})^{\top}}^{t}\right\|$
$\displaystyle=\sigma_{w}^{2}\left\|W_{\infty}(A+BF_{\gamma},I)\right\|,$ (43)

where we recall $W_{\infty}(A,B)$ is the controllability gramian, and we are
guaranteed from Lemma 2.1 that $\rho(A+BF_{\gamma})<1$, since
$\gamma\geq\gamma_{\infty}$. We note that there exists a uniform constant
upper bound on $\left\|W_{\infty}(A+BF_{\gamma},I)\right\|$ independent of
$\gamma$, since $W_{\infty}(A+BF_{\gamma_{\infty}},I)$ and
$W_{\infty}(A+BF_{\star},I)$ are both well-defined. From the intuition that
$W_{\infty}(A+BF_{\gamma},I)$ represents the “disturbability” of the closed-
loop system $A+BF_{\gamma}$, i.e. the controllability of $A+BF_{\gamma}$
treating disturbances as inputs, one may conjecture some monotone behavior of
$\left\|W_{\infty}(A+BF_{\gamma},I)\right\|$ between $\gamma=\gamma_{\infty}$
and $\gamma=\infty$ (i.e. going from the $\mathcal{H}_{\infty}$ robust closed-
loop system to the nominal closed-loop system), however proving such behavior
of the curve drawn by $\gamma$ is outside the scope of this work.
Alternatively, using norm bounds on the difference of block-Toeplitz matrices
(such as those in Mania et al. (2019)), one can show that for sufficiently
large $\gamma$, an upper bound on $\left\|W_{\infty}(A+BF_{\gamma},I)\right\|$
using only nominal system parameters can be derived, but these bounds tend to
be overly conservative, as they throw out the structure provided by the
adversarial LQ formulation. For illustrative purposes, we leave this
characterization of $\left\|\Sigma(F_{\gamma})\right\|$ as is.

We may use Lemma 3.1 to get an upper bound on
$\left\|F_{\gamma}-F_{\star}\right\|$:

$\displaystyle\left\|F_{\gamma}-F_{\star}\right\|$
$\displaystyle\leq\frac{\left\|B^{\top}(M_{\gamma}-P_{\star})(A+BF_{\star})\right\|}{\sigma_{\min}(R+B^{\top}P_{\star}B)}.$
(44)

This reduces our problem to upper bounding
$\left\|M_{\gamma}-P_{\star}\right\|$ As discussed in Section 3.1, this can be
further upper bounded by

$\displaystyle\left\|M_{\gamma}-P_{\star}\right\|$
$\displaystyle\leq\left\|P_{\gamma}-P_{\star}\right\|+\frac{\left\|P_{\gamma}\right\|^{2}}{\gamma^{2}-\left\|P_{\gamma}\right\|}.$

Therefore, our problem reduces to upper bounding $\left\|P_{\gamma}\right\|$
and $\left\|P_{\gamma}-P_{\star}\right\|$. For upper bounding
$\left\|P_{\gamma}\right\|$, we use the following lemma:

###### Lemma B.3

Given $(A,B,Q^{1/2})$ stabilizable and detectable, for
$\gamma_{1}>\gamma_{2}\geq\gamma_{\infty}$, we have

$\displaystyle 0\prec P_{\gamma_{1}}\prec P_{\gamma_{2}}\preceq
P_{\gamma_{\infty}}\preceq\gamma_{\infty}^{2},$

where $P_{\gamma_{1}}$ and $P_{\gamma_{2}}$ are the solutions to the DARE in
Lemma 2.1 Equation (11) at levels $\gamma_{1},\gamma_{2}$ respectively.

Proof: This lemma follows by observing that since a smaller $\gamma$
corresponds to a smaller penalty on the adversary, for any initial condition,
the corresponding adversarial LQ cost (10) will be larger. To see this, let
$\mathopen{}\left\\{\delta^{\gamma_{1}}_{t}\right\\}\mathclose{}$ be optimal
adversarial perturbations corresponding to level $\gamma_{1}$. Then
$\mathopen{}\left\\{\delta^{\gamma_{1}}_{t}\right\\}\mathclose{}$ are clearly
feasible adversarial perturbations to the adversarial LQ instance at level
$\gamma_{2}$, and since $\gamma_{1}>\gamma_{2}$, the corresponding adversarial
cost at level $\gamma_{2}$ must be larger. The maximal adversarial
perturbations at level $\gamma_{2}$,
$\mathopen{}\left\\{\delta^{\gamma_{2}}_{t}\right\\}\mathclose{}$, can only
incur higher cost than that, and thus we can show

$\displaystyle x_{0}^{\top}P_{\gamma_{1}}x_{0}$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\mathopen{}\left(\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}\mathopen{}\left(Q+F_{\gamma_{1}}^{\top}RF_{\gamma_{1}}\right)\mathclose{}x_{t}-\gamma_{1}^{2}\delta_{t}^{\top}\delta_{t}\right)\mathclose{}$
$\displaystyle=:\limsup_{T\to\infty}\frac{1}{T}\mathopen{}\left(x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}\mathopen{}\left(Q+F_{\gamma_{1}}^{\top}RF_{\gamma_{1}}\right)\mathclose{}x_{t}-\gamma_{1}^{2}{\delta^{\gamma_{1}}_{t}}^{\top}\delta^{\gamma_{1}}_{t}\right)\mathclose{}$
$\displaystyle<\limsup_{T\to\infty}\frac{1}{T}\mathopen{}\left(x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}\mathopen{}\left(Q+F_{\gamma_{2}}^{\top}RF_{\gamma_{2}}\right)\mathclose{}x_{t}-\gamma_{2}^{2}{\delta^{\gamma_{1}}_{t}}^{\top}\delta^{\gamma_{1}}_{t}\right)\mathclose{}$
$\displaystyle\leq\limsup_{T\to\infty}\frac{1}{T}\mathopen{}\left(\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}\mathopen{}\left(Q+F_{\gamma_{2}}^{\top}RF_{\gamma_{2}}\right)\mathclose{}x_{t}-\gamma_{2}^{2}\delta_{t}^{\top}\delta_{t}\right)\mathclose{}$
$\displaystyle=x_{0}^{\top}P_{\gamma_{2}}x_{0}.$

Thus, we have shown
$x_{0}^{\top}P_{\gamma_{1}}x_{0}<x_{0}^{\top}P_{\gamma_{2}}x_{0}$ for any
$x_{0}$, and thus $P_{\gamma_{1}}\prec P_{\gamma_{2}}$. From Lemma 2.1, this
further implies $P_{\gamma_{2}}\prec
P_{\gamma_{\infty}}\prec\gamma_{\infty}^{2}I$. $\blacksquare$

Therefore, Lemma B.3 immediately implies
$\left\|P_{\gamma}\right\|\prec\gamma_{\infty}^{2}$, and thus:

$\displaystyle\frac{\left\|P_{\gamma}\right\|^{2}}{\gamma^{2}-\left\|P_{\gamma}\right\|}\leq\frac{\gamma_{\infty}^{4}}{\gamma^{2}-\gamma_{\infty}^{2}}.$
(45)

Upper bounding $\left\|P_{\gamma}-P_{\star}\right\|$ is a bit more involved.
As previewed in Section 3.1, we show that defining

$\displaystyle\tilde{A}$
$\displaystyle=\mathopen{}\left(I+\mathopen{}\left(\gamma^{2}I-P_{\gamma}\right)\mathclose{}^{-1}P_{\gamma}\right)\mathclose{}A,\quad\tilde{B}=\mathopen{}\left(I+\mathopen{}\left(\gamma^{2}I-P_{\gamma}\right)\mathclose{}^{-1}P_{\gamma}\right)\mathclose{}B$
(46)

we can re-write the state update under the adversary as

$\displaystyle x_{t+1}$
$\displaystyle=Ax_{t}+Bu_{t}+\delta_{t}=\tilde{A}x_{t}+\tilde{B}u_{t}.$

We then show that the gaps
$\left\|\tilde{A}-A\right\|,\;\left\|\tilde{B}-B\right\|$ can be upper bounded
in terms of $\gamma$ in the following lemma, after which we may adapt some
techniques introduced in Proposition 3 from Mania et al. (2019) to get an
upper bound on $\left\|P_{\gamma}-P_{\star}\right\|$.

###### Lemma B.4

Given an arbitrary control sequence
$\mathopen{}\left\\{u_{t}\right\\}\mathclose{}_{t\geq 0}$, and an adversarial
noiseless LQR instance at level $\gamma>0$, we recall the adversary
$\delta_{t}$ can be expressed as:

$\displaystyle\delta_{t}$
$\displaystyle=\mathopen{}\left(\gamma^{2}I-P_{\gamma}\right)\mathclose{}^{-1}P_{\gamma}\mathopen{}\left(Ax_{t}+Bu_{t}\right)\mathclose{}.$

Defining $\tilde{A},\tilde{B}$ as in Equation (46), we have the following
perturbation bounds

$\displaystyle\left\|\tilde{A}-A\right\|$
$\displaystyle\leq\frac{\gamma_{\infty}^{2}}{\gamma^{2}-\gamma_{\infty}^{2}}\left\|A\right\|$
$\displaystyle\left\|\tilde{B}-B\right\|$
$\displaystyle\leq\frac{\gamma_{\infty}^{2}}{\gamma^{2}-\gamma_{\infty}^{2}}\left\|B\right\|.$

Therefore, given a desired level $\zeta>0$, choosing the adversarial level

$\displaystyle\gamma^{2}\geq\gamma_{\infty}^{2}+\frac{\gamma_{\infty}^{2}}{\zeta}\max\mathopen{}\left\\{\left\|A\right\|,\left\|B\right\|\right\\}\mathclose{},$

guarantees $||\tilde{A}-A||,||\tilde{B}-B||\leq\zeta$.

Proof: We can apply rudimentary matrix bounds combined with Lemma B.3 to get

$\displaystyle\left\|\tilde{A}-A\right\|$
$\displaystyle=\left\|\mathopen{}\left(P_{\gamma}-\gamma^{2}I\right)\mathclose{}^{-1}P_{\gamma}A\right\|$
$\displaystyle\leq\left\|\mathopen{}\left(P_{\gamma}-\gamma^{2}I\right)\mathclose{}^{-1}\right\|\left\|P_{\gamma}\right\|\left\|A\right\|$
$\displaystyle\leq\frac{\left\|P_{\gamma}\right\|}{\gamma^{2}-\left\|P_{\gamma}\right\|}\left\|A\right\|$
$\displaystyle\leq\frac{\gamma_{\infty}^{2}}{\gamma^{2}-\gamma_{\infty}^{2}}\left\|A\right\|,$

which we may repeat for $\left\|\tilde{B}-B\right\|$. Inverting

$\frac{\gamma_{\infty}^{2}}{\gamma^{2}-\gamma_{\infty}^{2}}\max\mathopen{}\left\\{\left\|A\right\|,\left\|B\right\|\right\\}\mathclose{}\leq\zeta,$

for $\gamma^{2}$, we get the desired result. $\blacksquare$

######  Proposition B.1 (Upper Bound on $\gamma$-Adversarial versus Nominal
DARE Solution)

Let $P_{\star}$ be the solution to
$\textnormal{{DARE}}\mathopen{}\left(A,B,Q,R\right)\mathclose{}$, and
$P_{\gamma}$ be the solution to
$\textnormal{{DARE}}\mathopen{}\left(A,\begin{bmatrix}B&I\end{bmatrix},Q,\begin{bmatrix}R&0\\\
0&-\gamma^{2}I\end{bmatrix}\right)\mathclose{}$, and let $(A,B,Q^{1/2})$ be
controllable and detectable. Define
$\kappa(Q,R)=\frac{\max\mathopen{}\left\\{\sigma_{\max}(Q),\sigma_{\max}(R)\right\\}\mathclose{}}{\min\mathopen{}\left\\{\sigma_{\min}(Q),\sigma_{\min}(R)\right\\}\mathclose{}}$,
$\tau(A,\rho):=\sup\mathopen{}\left\\{\left\|A^{k}\right\|\rho^{-k}:k\geq
0\right\\}\mathclose{}$, and
$\beta=\max\mathopen{}\left\\{1,\frac{\gamma_{\infty}^{2}}{\gamma^{2}-\gamma_{\infty}^{2}}\max\mathopen{}\left\\{\left\|A\right\|,\left\|B\right\|\right\\}\mathclose{}\tau\mathopen{}\left(A,\rho\right)\mathclose{}+\rho\right\\}\mathclose{}$,
where $\rho>\rho(A)$. Then for

$\displaystyle\gamma^{2}\geq\gamma_{\infty}^{2}+\frac{3}{2}\ell^{3/2}\beta^{\ell-1}\sigma_{\min}(W_{\ell}(A,B))^{-1/2}\tau(A,\rho)^{2}\mathopen{}\left(\left\|B\right\|+1\right)\mathclose{}\max\mathopen{}\left\\{\left\|A\right\|,\left\|B\right\|\right\\}\mathclose{}\gamma_{\infty}^{2},$

the following bound holds:

$\displaystyle\left\|P_{\gamma}-P_{\star}\right\|$ $\displaystyle\leq
16\frac{\gamma_{\infty}^{2}\max\mathopen{}\left\\{\left\|A\right\|,\left\|B\right\|\right\\}\mathclose{}}{\gamma^{2}-\gamma_{\infty}^{2}}\ell^{5/2}\beta^{2(\ell-1)}\mathopen{}\left(1+\sigma_{\min}(W_{\ell}(A,B))^{-1/2}\right)\mathclose{}\tau(A,\rho)^{3}\mathopen{}\left(\left\|B\right\|+1\right)\mathclose{}^{2}\kappa(Q,R)\left\|P_{\star}\right\|.$
(47)

The proof of Proposition B.1 is mostly similar to Proposition 3 in Mania et
al. (2019). However, we note that our requirement on the size of $\gamma$ is
much more lenient than the requirement on
$\left\|\tilde{A}-A\right\|,\left\|\tilde{B}-B\right\|$ in Proposition 3 of
Mania et al. (2019). In short, this is because in our setting we are
guaranteed $P_{\gamma}\succ P_{\star}$, and thus
$\left\|P_{\gamma}-P_{\star}\right\|=\lambda_{\max}(P_{\gamma}-P_{\star})$.
Therefore, upper bounding $\lambda_{\max}(P_{\gamma}-P_{\star})$ suffices.
Unlike the general case of perturbed DARE solutions, we do not need the gap to
be small enough for the upper bound on $\lambda_{\max}(P_{\gamma}-P)$ to be
less than $1/2$. Our only size requirement on $\gamma$ comes from guaranteeing
the minimum singular value of the $\ell$-controllability gramian of
$(\tilde{A},\tilde{B})$ to be at least $1/2$ that of the nominal system
$(A,B)$.

Combining Lemma 3.1, Equations (43) and (45), and Proposition B.1 together
yields the final upper bound on
$\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K)$.

###  B.3 Proof of Theorem 3.2

We start by stating and proving the spectral upper and lower bounds mentioned
in Section 3.2.

###### Lemma B.5

Under the assumption $(A,B,Q^{1/2})$ is stabilizable and detectable, and for
$\gamma\geq\tilde{\gamma}_{\infty}$, we have the following bounds:

$\displaystyle\tilde{P}_{\gamma}-P_{\gamma}$
$\displaystyle\preceq\left\|F_{\gamma}-F_{\star}\right\|^{2}\left\|R+B^{\top}M_{\gamma}B\right\|W_{\infty}(\tilde{A}+\tilde{B}F_{\star},I)$
$\displaystyle
P_{\gamma}(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}+\tilde{P}_{\gamma}-P_{\star}$
$\displaystyle\succeq\frac{\sigma_{\min}(P_{\star})^{2}}{\gamma^{2}-\sigma_{\min}\mathopen{}\left(P_{\star}\right)\mathclose{}}\mathopen{}\left(W_{\infty}(A+BF_{\star},I)\right)\mathclose{},$

where
$\tilde{A}=\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}A$
and
$\tilde{B}=\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}B$.

Proof: We start with the upper bound. Begin by recalling that for any $x$,
$x^{\top}\tilde{P}_{\gamma}x$ is the cost of applying controller $F_{\star}$
in the noiseless adversarial setting at level $\gamma$ from initial state $x$,
while $P_{\gamma}$ is the cost of applying controller $F_{\gamma}$ in the
noiseless adversarial setting at level $\gamma$ from initial state $x$. If we
denote the optimal map from the state to the adversary perturbation in the
cases where controller $F_{\star}$ and $F_{\gamma}$ are deployed as
$\tilde{E}_{\gamma}$ and $E_{\gamma}$ respectively, then we may consider this
as the cost gap of applying the controller

$\begin{bmatrix}u_{t}\\\ \delta_{t}\end{bmatrix}=\begin{bmatrix}F_{\star}\\\
\tilde{E}_{\gamma}\end{bmatrix}x_{t}$

to the system

$x_{t+1}=Ax_{t}+\begin{bmatrix}B&I\end{bmatrix}\begin{bmatrix}u_{t}\\\
\delta_{t}\end{bmatrix}$

with cost $x_{t}^{\top}Qx_{t}+\begin{bmatrix}u_{t}\\\
\delta_{t}\end{bmatrix}^{\top}\begin{bmatrix}R&0\\\
0&-\gamma^{2}I\end{bmatrix}\begin{bmatrix}u_{t}\\\ \delta_{t}\end{bmatrix}$.
Similarly, we can consider applying the controller

$\begin{bmatrix}u_{t}\\\ \delta_{t}\end{bmatrix}=\begin{bmatrix}F_{\gamma}\\\
E_{\gamma}\end{bmatrix}x_{t},$

which is optimal in this setting.

Then by Lemma 10 in Fazel et al. (2018), we have that

$\displaystyle
x^{\top}\tilde{P}_{\gamma}x-x^{\top}P_{\gamma}x=\sum_{t=0}\mathopen{}\left(x_{t}^{\prime}\right)\mathclose{}^{\top}\begin{bmatrix}F_{\star}-F_{\gamma}\\\
\tilde{E}_{\gamma}-E_{\gamma}\end{bmatrix}^{\top}\mathopen{}\left(\begin{bmatrix}R&0\\\
0&-\gamma^{2}I\end{bmatrix}+\begin{bmatrix}B&I\end{bmatrix}^{\top}P_{\gamma}\begin{bmatrix}B&I\end{bmatrix}\right)\mathclose{}\begin{bmatrix}F_{\star}-F_{\gamma}\\\
\tilde{E}_{\gamma}-E_{\gamma}\end{bmatrix}x_{t}^{\prime}$

where $x_{0}^{\prime}=x$, and
$x_{t+1}^{\prime}=(A+BF_{\star}+\tilde{E}_{\gamma})x_{t}^{\prime}$. Next,
observe that

$\displaystyle\begin{bmatrix}R&0\\\
0&-\gamma^{2}I\end{bmatrix}+\begin{bmatrix}B&I\end{bmatrix}^{\top}P_{\gamma}\begin{bmatrix}B&I\end{bmatrix}\preceq\begin{bmatrix}R+B^{\top}M_{\gamma}B&0\\\
0&0\end{bmatrix}.$

To see that this is the case, we will show that

$\displaystyle\begin{bmatrix}B^{\top}(P_{\gamma}-M_{\gamma})B&B^{\top}P_{\gamma}\\\
P_{\gamma}B&P_{\gamma}-\gamma^{2}I\end{bmatrix}\preceq 0.$

Expanding
$M_{\gamma}=P_{\gamma}+P_{\gamma}(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}$, and
multiplying the expression by $-1$, we can see that this is equivalent to
showing that

$\displaystyle\begin{bmatrix}B^{\top}P_{\gamma}(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}B&-B^{\top}P_{\gamma}\\\
-P_{\gamma}B&\gamma^{2}I-P_{\gamma}\end{bmatrix}\succeq 0.$

This follows from a Scur complement check for positive definiteness by the
fact that $\gamma^{2}I-P_{\gamma}\succ 0$. Then we have that

$\displaystyle
x^{\top}\tilde{P}_{\gamma}x-x^{\top}P_{\gamma}x\leq\sum_{t=0}\mathopen{}\left(x_{t}^{\prime}\right)\mathclose{}^{\top}(F_{\star}-F_{\gamma})^{\top}\mathopen{}\left(R+B^{\top}M_{\gamma}B\right)\mathclose{}(F_{\star}-F_{\gamma})x_{t}^{\prime},$

or, by the fact that
$x_{t+1}^{\prime}=A+BF_{\star}+\tilde{E}_{\gamma}x_{t}^{\prime}=\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BF_{\star})x_{t}^{\prime}$,

$\displaystyle\tilde{P}_{\gamma}-P_{\gamma}$
$\displaystyle\preceq\sum_{t=0}\mathopen{}\left(\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BF_{\star})\right)\mathclose{}^{t}\right)\mathclose{}^{\top}(F_{\star}-F_{\gamma})^{\top}$
$\displaystyle\quad\quad\quad\mathopen{}\left(R+B^{\top}M_{\gamma}B\right)\mathclose{}(F_{\star}-F_{\gamma})\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BF_{\star})\right)\mathclose{}^{t}$

as we wanted to show.

Moving on to the lower bound, note that we may express

$\displaystyle\tilde{P}_{\gamma}$
$\displaystyle=\textnormal{{dlyap}}\mathopen{}\left((I+H)(A+BF_{\star}),Q+F_{\star}^{\top}RF_{\star}-\gamma^{2}(A+BF_{\star})^{\top}H^{\top}H(A+BF_{\star})\right)\mathclose{}$
$\displaystyle P_{\star}$
$\displaystyle=\textnormal{{dlyap}}\mathopen{}\left(A+BF_{\star},Q+F_{\star}^{\top}RF_{\star}\right)\mathclose{}$
$\displaystyle H$
$\displaystyle=(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}$

Then

$\displaystyle\tilde{P}_{\gamma}-P_{\star}$
$\displaystyle=(A+BF_{\star})^{\top}(I+H)^{\top}\tilde{P}_{\gamma}(I+H)(A+BF_{\star})-\gamma^{2}(A+BF_{\star})^{\top}H^{\top}H(A+BF_{\star})$
$\displaystyle\quad\quad-(A+BF_{\star})^{\top}P_{\star}(A+BF_{\star})$
$\displaystyle=(A+BF_{\star})^{\top}(\tilde{P}_{\gamma}-P_{\star})(A+BF_{\star})+(A+BF_{\star})^{\top}\mathopen{}\left(H^{\top}\tilde{P}_{\gamma}+\tilde{P}_{\gamma}H+H^{\top}\tilde{P}_{\gamma}H-\gamma^{2}H^{\top}H\right)\mathclose{}(A+BF_{\star})$

However, we have that

$\displaystyle
H^{\top}\tilde{P}_{\gamma}=\tilde{P}_{\gamma}H=\tilde{P}_{\gamma}(\gamma^{2}I-\tilde{P}_{\gamma})\tilde{P}_{\gamma}$

and

$\displaystyle
H^{\top}\tilde{P}_{\gamma}H-\gamma^{2}H^{\top}H=\mathopen{}\left(\tilde{P}_{\gamma}-\gamma^{2}I\right)\mathclose{}H=\tilde{P}_{\gamma}^{\top}(\gamma^{2}I-\tilde{P}_{\gamma})\tilde{P}_{\gamma}.$

Then

$\tilde{P}_{\gamma}-P_{\star}=\textnormal{{dlyap}}(A+BF_{\star},(A+BF_{\star})^{\top}\tilde{P}_{\gamma}(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}(A+BF_{\star})).$

We can expand the Lyapunov solution as an infinite sum:

$\tilde{P}_{\gamma}-P_{\star}=\sum_{t=1}^{\infty}\mathopen{}\left((A+BF_{\star})^{t}\right)\mathclose{}^{\top}\tilde{P}_{\gamma}(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}P_{\gamma}(A+BF_{\star})^{t}.$

Next, note that

$\tilde{P}_{\gamma}(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\succeq\frac{\sigma_{\min}(\tilde{P}_{\gamma})^{2}}{\gamma^{2}-\sigma_{\min}\mathopen{}\left(\tilde{P}_{\gamma}\right)\mathclose{}}I\succeq\frac{\sigma_{\min}(P_{\star})}{\gamma^{2}-\sigma_{\min}\mathopen{}\left(P_{\star}\right)\mathclose{}}I$

and thus

$\tilde{P}_{\gamma}-P\succeq\frac{\sigma_{\min}(P_{\star})^{2}}{\gamma^{2}-\sigma_{\min}\mathopen{}\left(P_{\star}\right)\mathclose{}}\sum_{t=1}^{\infty}\mathopen{}\left((A+BF_{\star})^{t}\right)\mathclose{}^{\top}(A+BF_{\star})^{t}$

Adding in the term

$P_{\gamma}(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}\succeq\frac{\sigma_{\min}(P_{\gamma})^{2}}{\gamma^{2}-\sigma_{\min}\mathopen{}\left(P_{\gamma}\right)\mathclose{}}I\succeq\frac{\sigma_{\min}(P_{\star})}{\gamma^{2}-\sigma_{\min}\mathopen{}\left(P_{\star}\right)\mathclose{}}I$

allows us to start the sum from $0$, providing the desired result.
$\blacksquare$

###### Lemma B.6

As long as $\gamma$ satisfies

$\displaystyle\gamma^{2}$
$\displaystyle\geq\sigma_{\min}(P_{\star})+\sigma_{\min}(P_{\star})^{2}\sigma_{\min}(A+BF_{\star})^{2}\frac{1}{2\left\|R+B^{\top}M_{\gamma}B\right\|}$
$\displaystyle\quad\quad\quad\left\|B^{\top}W_{\infty}\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BF_{\star}),I\right)\mathclose{}\right\|\left\|B^{\top}W_{\infty}(A+BF_{\star},I)\right\|,$

we have the following bound

$\displaystyle\left\|F_{\gamma}-F_{\star}\right\|\geq\frac{\sigma_{\min}(P_{\star})^{2}\left\|B^{\top}W_{\infty}(A+BF_{\star},I)\right\|\sigma_{\min}(A+BF_{\star})}{2\left\|R+B^{\top}M_{\gamma}B\right\|(\gamma^{2}-\sigma_{\min}\mathopen{}\left(P_{\star}\right)\mathclose{})}$

Proof: Beginning with the lower bound in (30) and applying Lemma B.5, we find

$\displaystyle\left\|F_{\gamma}-F_{\star}\right\|$
$\displaystyle\geq\frac{\sigma_{\min}(A+BF_{\star})}{\left\|R+BM_{\gamma}B\right\|}\bigg{(}\frac{\sigma_{\min}(P_{\star})}{\gamma^{2}-\sigma_{\min}(P_{\star})}\left\|B^{\top}W_{\infty}(A+BF_{\star},I)\right\|$
$\displaystyle\quad\quad\quad-\left\|B^{\top}W_{\infty}\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BF_{\star}),I\right)\mathclose{}\right\|\left\|F_{\gamma}-F_{\star}\right\|^{2}\left\|R+B^{\top}M_{\gamma}B\right\|\bigg{)}.$

In particular, by defining

$\displaystyle a$
$\displaystyle=\sigma_{\min}(A+BF_{\star})\left\|B^{\top}W_{\infty}\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BF_{\star}),I\right)\mathclose{}\right\|$
$\displaystyle c$
$\displaystyle=\frac{\sigma_{\min}(P_{\star})^{2}}{\gamma^{2}-\sigma_{\min}(P_{\star})}\frac{\left\|B^{\top}W_{\infty}(A+BF_{\star},I)\right\|}{\left\|R+B^{\top}M_{\gamma}B\right\|}\sigma_{\min}(A+BF_{\star}),$

the above bound can be written

$\displaystyle
a\left\|F_{\gamma}-F_{\star}\right\|^{2}+\left\|F_{\gamma}-F_{\star}\right\|-c\geq
0$

which, considering that $\left\|F_{\gamma}-F_{\star}\right\|\geq 0$, implies
that

$\displaystyle
a\left\|F_{\gamma}-F_{\star}\right\|\geq\sqrt{\frac{1}{4}+ac}-\frac{1}{2}.$

Under the assumption that $ac\leq 2$, this may be simplified to
$\left\|F_{\gamma}-F_{\star}\right\|\geq\frac{1}{2}c$. $\blacksquare$

Theorem 3.2 then follows from the general lower bound in equation (27) and the
bound from Lemma B.6.

##  Appendix C Proofs for Section 4

###  C.1 Proofs for Section 4.1

###### Proposition C.1

Let $\Sigma_{\star}$ be the solution to

$\textnormal{{DARE}}\mathopen{}\left(A^{\top},C_{2}^{\top},B_{0}B_{0}^{\top},D_{20}D_{20}^{\top}\right)\mathclose{},$

and $\Sigma_{\gamma}$ be the solution to

$\textnormal{{DARE}}\mathopen{}\left(A^{\top}(I+\Lambda_{\gamma})^{\top},C_{2}^{\top}(I+\Lambda_{\gamma})^{\top},B_{0}B_{0}^{\top},D_{20}D_{20}^{\top}\right)\mathclose{},$

where

$\Lambda_{\gamma}=B_{1}(\gamma^{2}I-B_{1}^{\top}Y_{\gamma}B_{1})^{-1}B_{1}^{\top}Y_{\gamma}.$

Define $\bar{Y}$ such that $\bar{Y}\geq\left\|Y_{\gamma}\right\|$ for all
$\gamma$ such that the conditions of (31) are satisifed. Suppose that
$(A,C_{2})$ is observable. Define
$\kappa(B_{0}B_{0}^{\top},D_{20}D_{20}^{\top})=\frac{\max\mathopen{}\left\\{\sigma_{\max}(B_{0}B_{0}^{\top}),\sigma_{\max}(D_{20}D_{20}^{\top})\right\\}\mathclose{}}{\min\mathopen{}\left\\{\sigma_{\min}(B_{0}B_{0}^{\top}),\sigma_{\min}(D_{20}D_{20}^{\top})\right\\}\mathclose{}}$,
$\tau(A,\rho):=\sup\mathopen{}\left\\{\left\|A^{k}\right\|\rho^{-k}:k\geq
0\right\\}\mathclose{}$, and
$\beta=\max\mathopen{}\left\\{1,\frac{\left\|B_{1}\right\|^{2}\bar{Y}}{\gamma^{2}-\left\|B_{1}\right\|^{2}\bar{Y}}\max\mathopen{}\left\\{\left\|A\right\|,\left\|C_{2}\right\|\right\\}\mathclose{}\tau\mathopen{}\left(A,\rho\right)\mathclose{}+\rho\right\\}\mathclose{}$,
where $\rho>\rho(A)$. Then for

$\displaystyle\gamma^{2}\geq\left\|B_{1}\right\|^{2}\bar{Y}+\frac{3}{2}\ell^{3/2}\beta^{\ell-1}\sigma_{\min}(W_{\ell}(A^{\top},C^{\top}))^{-1/2}\tau(A,\rho)^{2}\mathopen{}\left(\left\|C\right\|+1\right)\mathclose{}\max\mathopen{}\left\\{\left\|A\right\|,\left\|C_{2}\right\|\right\\}\mathclose{}\left\|B_{1}\right\|^{2}\bar{Y},$

the following bound holds:

$\displaystyle\left\|\Sigma_{\gamma}-\Sigma_{\star}\right\|$
$\displaystyle\leq
16\frac{\left\|B_{1}\right\|^{2}\bar{Y}}{\gamma^{2}-\left\|B_{1}\right\|^{2}\bar{Y}}\max\mathopen{}\left\\{\left\|A\right\|,\left\|C_{2}\right\|\right\\}\mathclose{}\ell^{5/2}\beta^{2(\ell-1)}$
$\displaystyle\quad\cdot\mathopen{}\left(1+\sigma_{\min}(W_{\ell}(A^{\top},C_{2}^{\top}))^{-1/2}\right)\mathclose{}\tau(A,\rho)^{3}\mathopen{}\left(\left\|C_{2}\right\|+1\right)\mathclose{}^{2}\kappa(B_{0}B_{0}^{\top},D_{20}D_{20}^{\top})\left\|\Sigma_{\star}\right\|.$

As with Proposition B.1, the proof of Proposition C.1 follows the proof of
Proposition 3 in Mania et al. (2019). The modifications to reach Proposition
B.1 are the same as those to reach Proposition C.1.

See 4.2 Proof: Begin by observing that

$\displaystyle\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma}$
$\displaystyle=(I+\Lambda_{\gamma})\tilde{\Sigma}_{\gamma}(I+\Lambda_{\gamma})-\tilde{\Sigma}_{\gamma}$
$\displaystyle=(I+B_{1}(\gamma^{2}I-B_{1}^{\top}Y_{\gamma}B_{1})^{-1}B_{1}^{\top}Y_{\gamma})\tilde{\Sigma}_{\gamma}(I+B_{1}(\gamma^{2}I-B_{1}^{\top}Y_{\gamma}B_{1})^{-1}B_{1}^{\top}Y_{\gamma})^{\top}-\tilde{\Sigma}_{\gamma}.$

Letting $B_{1}^{\top}Y_{\gamma}^{1/2}=U\Sigma V^{\top}$, we find that

$\displaystyle\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma}$
$\displaystyle=(I+Y_{\gamma}^{-1/2}V\Sigma^{2}(\gamma^{2}I-\Sigma^{2})^{-1}V^{\top}Y_{\gamma}^{1/2})^{\top}\tilde{\Sigma}_{\gamma}(I+Y_{\gamma}^{-1/2}V\Sigma^{2}(\gamma^{2}I-\Sigma^{2})^{-1}V^{\top}Y_{\gamma}^{1/2})-\tilde{\Sigma}_{\gamma}$
$\displaystyle=Y_{\gamma}^{1/2}V\gamma^{2}I(\gamma^{2}I-\Sigma^{2})^{-1}V^{\top}Y_{\gamma}^{-1/2}\tilde{\Sigma}_{\gamma}Y_{\gamma}^{-1/2}V\gamma^{2}I(\gamma^{2}I-\Sigma^{2})^{-1}V^{\top}Y_{\gamma}^{1/2}-\tilde{\Sigma}_{\gamma}$
$\displaystyle=Y_{\gamma}^{1/2}V\mathopen{}\left[\gamma^{2}I(\gamma^{2}I-\Sigma^{2})^{-1}V^{\top}Y_{\gamma}^{-1/2}\tilde{\Sigma}_{\gamma}Y_{\gamma}^{-1/2}V\gamma^{2}I(\gamma^{2}I-\Sigma^{2})^{-1}-V^{\top}Y_{\gamma}^{-1/2}\tilde{\Sigma}_{\gamma}Y_{\gamma}^{-1/2}V\right]\mathclose{}V^{\top}Y_{\gamma}^{1/2}.$

Then

$\displaystyle\sigma_{\min}(\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma})$
$\displaystyle\geq\sigma_{\min}(Y_{\gamma})\mathopen{}\left(\sigma_{\min}(\gamma^{2}I(\gamma^{2}I-\Sigma^{2})V^{\top}Y_{\gamma}^{-1/2}\tilde{\Sigma}_{\gamma}Y_{\gamma}^{-1/2}V\gamma^{2}I(\gamma^{2}I-\Sigma^{2}))-\left\|Y_{\gamma}^{-1/2}\tilde{\Sigma}_{\gamma}Y_{\gamma}^{-1/2}\right\|\right)\mathclose{}$
$\displaystyle\geq\sigma_{\min}(Y_{\gamma})\mathopen{}\left(\mathopen{}\left(\frac{\gamma^{2}}{\gamma^{2}-\left\|B_{1}^{\top}Y_{\gamma}^{1/2}\right\|}\right)\mathclose{}^{2}\frac{1}{\left\|Y_{\gamma}\right\|}\sigma_{\min}(\tilde{\Sigma}_{\gamma})-\left\|\tilde{\Sigma}_{\gamma}\right\|/\sigma_{\min}(Y_{\gamma})\right)\mathclose{}.$

$\blacksquare$

###  C.2 Proofs for Section 4.2

See 4.3 Proof:  The problem may be expressed as finding a solution to

$ac\frac{\Sigma_{\gamma}Y_{\gamma}}{\gamma^{2}}L^{2}+\mathopen{}\left((a^{2}-c^{2})\frac{\Sigma_{\gamma}Y_{\gamma}}{\gamma^{2}}+(1+c^{2}\Sigma_{\gamma})\right)\mathclose{}L+ac\Sigma_{\gamma}-ac\frac{\Sigma_{\gamma}Y_{\gamma}}{\gamma^{2}}.$

Viewing this as a general quadratic formula $c_{1}L^{2}+c_{2}L+c_{3}=0$, the
solution of interest is

$\displaystyle L=\frac{-c_{2}+\sqrt{c_{2}^{2}-4c_{1}c_{3}}}{2c_{1}}$
$\displaystyle=\frac{c_{2}}{2c_{1}}\mathopen{}\left(-1+\sqrt{1-4\frac{c_{1}c_{3}}{c_{2}^{2}}}\right)\mathclose{}$

Taylor’s formula tells us that for some $c\in[0,x]$,

$\sqrt{1+x}=1+\frac{x}{2}-\frac{x^{2}}{8(1+c)^{3/2}}$

Therefore, if ${\left|x\right|}<\frac{1}{2}$,

$\sqrt{1+x}=1+\frac{x}{2}+\alpha x^{2},$

where ${\left|\alpha\right|}<\frac{1}{2}$. Substituting this in, we find that
as long as $4\frac{{\left|c_{1}c_{3}\right|}}{c_{2}^{2}}\leq\frac{1}{2}$, the
solution of interest for the quadratic formula is

$\displaystyle L$
$\displaystyle=\frac{c_{2}}{2c_{1}}\mathopen{}\left(-2\frac{c_{1}c_{3}}{c_{2}^{2}}+\alpha
16\frac{(c_{1}c_{3})^{2}}{c_{2}^{4}}\right)\mathclose{}$
$\displaystyle=-\frac{c_{3}}{c_{2}}\mathopen{}\left(1+8\alpha\frac{c_{1}c_{3}}{c_{2}^{2}}\right)\mathclose{}$

where ${\left|\alpha\right|}<\frac{1}{2}$. Substituting in values of $c_{1}$,
$c_{2}$ and $c_{3}$, we may therefore show that as long as (33) is satisfied,
then

$L=\frac{-ac\Sigma_{\gamma}}{1+c^{2}\Sigma_{\gamma}}+\xi,$

where

$\displaystyle\xi$
$\displaystyle=\mathopen{}\left(-\frac{c_{3}}{c_{2}}-\frac{-ac\Sigma_{\gamma}}{1+c^{2}\Sigma_{\gamma}}\right)\mathclose{}-8\frac{c_{1}c_{3}^{2}}{c_{2}^{3}}$
$\displaystyle=-\frac{ac\Sigma_{\gamma}(a^{2}-c^{2})\frac{Y_{\gamma}\Sigma_{\gamma}}{\gamma^{2}}}{(1+c^{2}\Sigma_{\gamma})(1+c^{2}\Sigma_{\gamma}+(a^{2}-c^{2})\frac{Y_{\gamma}\Sigma_{\gamma}}{\gamma^{2}})}+\frac{ac\frac{Y_{\gamma}\Sigma_{\gamma}}{\gamma^{2}}}{1+c^{2}\Sigma_{\gamma}+(a^{2}-c^{2})\frac{Y_{\gamma}\Sigma_{\gamma}}{\gamma^{2}}}$
$\displaystyle\qquad-8\alpha\frac{\frac{\Sigma_{\gamma}Y_{\gamma}}{\gamma^{2}}(ac)^{3}\Sigma_{\gamma}^{2}\mathopen{}\left(1-\frac{Y_{\gamma}}{\gamma^{2}}\right)\mathclose{}^{2}}{\mathopen{}\left((a^{2}-c^{2})\frac{\Sigma_{\gamma}Y_{\gamma}}{\gamma^{2}}+(1+c^{2}\Sigma_{\gamma})\right)\mathclose{}^{3}}.$

Again using (33), we may bound

$\displaystyle{\left|\xi\right|}$ $\displaystyle\leq
64{\left|a\right|}{\left|c\right|}\frac{\Sigma_{\gamma}Y_{\gamma}}{\gamma^{2}}\mathopen{}\left(\Sigma_{\gamma}{\left|a^{2}-c^{2}\right|}+1+(ac\Sigma_{\gamma})^{2}\right)\mathclose{}.$

$\blacksquare$

###### Proposition C.2

Let $\Sigma_{\star}$ be the solution to

$\textnormal{{DARE}}\mathopen{}\left(a,c,1,1\right)\mathclose{},$

and $\Sigma_{\gamma}$ be the solution to

$\textnormal{{DARE}}\mathopen{}\left(a(1+\Lambda_{\gamma}),c(1+\Lambda_{\gamma}),1,1\right)\mathclose{},$

where

$\Lambda_{\gamma}=\frac{Y_{\gamma}(1+L_{\gamma}^{2})}{\gamma^{2}-Y_{\gamma}(1+L_{\gamma}^{2})}$

Define $\bar{Y}$ such that $\bar{Y}\geq\left\|Y_{\gamma}\right\|$ for all
$\gamma$ such that the conditions of (31) are satisifed. Suppose that
${\left|c\right|}>0$. and
$\beta=\max\mathopen{}\left\\{1,\frac{\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}}{\gamma^{2}-\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}}\max\mathopen{}\left\\{{\left|a\right|},{\left|c\right|}\right\\}\mathclose{}+1\right\\}\mathclose{}$.
Then for

$\displaystyle\gamma^{2}\geq\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}+\frac{3}{2}{\left|c\right|}^{-1}\mathopen{}\left({\left|c\right|}+1\right)\mathclose{}\max\mathopen{}\left\\{\left\|a\right\|,\left\|c\right\|\right\\}\mathclose{}\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2},$

the following bound holds:

$\displaystyle\left\|\Sigma_{\gamma}-\Sigma_{\star}\right\|$
$\displaystyle\leq
16\frac{\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}}{\gamma^{2}-\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}}\max\mathopen{}\left\\{{\left|a\right|},{\left|c\right|}\right\\}\mathclose{}\mathopen{}\left(1+{\left|c\right|}^{-1}\right)\mathclose{}\mathopen{}\left({\left|c\right|}+1\right)\mathclose{}^{2}\left\|\Sigma_{\star}\right\|.$

As with Proposition B.1, the proof of Proposition C.2 follows the proof of
Proposition 3 in Mania et al. (2019). The modifications to reach Proposition
B.1 are the same as those to reach Proposition C.2, followed by substituting
in $\ell=1$.

See 4.3 Proof: Observe that if we denote
$\Lambda_{\gamma}=\frac{Y_{\gamma}(1+L_{\gamma}^{2})}{\gamma^{2}-Y_{\gamma}(1+L_{\gamma}^{2})}$,
then we may write

$\displaystyle\Sigma_{\gamma}=(1+\Lambda_{\gamma})^{2}(a+L_{\gamma}c)\Sigma_{\gamma}(a+L_{\gamma}c)^{\top}(1+\Lambda_{\gamma})+(a+\Lambda_{\gamma})^{2}(1+L_{\gamma}^{2}).$

Defining
$\tilde{\Sigma}_{\gamma}=\frac{\Sigma_{\gamma}}{(I+\Lambda_{\gamma})^{2}}$, we
have

$\displaystyle\tilde{\Sigma}_{\gamma}$
$\displaystyle=\textnormal{{DARE}}((a(1+\Lambda_{\gamma}),c(1+\Lambda_{\gamma}),1,1).$

By the triangle inequality,

$\displaystyle\left\|\Sigma_{\gamma}-\Sigma_{\star}\right\|\leq\left\|\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma}\right\|+\left\|\tilde{\Sigma}_{\gamma}-\Sigma_{\star}\right\|.$

As in Section 3.1, we may bound
$\left\|\tilde{\Sigma}_{\gamma}-\Sigma_{\star}\right\|$ when both
$A\Lambda_{\gamma}$ and $C\Lambda_{\gamma}$ are small. To bound
$\left\|\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma}\right\|$, note that

$\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma}=(\Lambda_{\gamma}^{2}+2\Lambda_{\gamma})\tilde{\Sigma}_{\gamma}$

Define $\bar{Y}$ such that $\bar{Y}\geq Y_{\gamma}$ for all $\gamma$ such that
the conditions of (31) are satisfied, and note that for all $L_{\gamma}$ that
render the closed loop system stable, we must have
${\left|L_{\gamma}\right|}\leq\frac{{\left|a\right|}+1}{{\left|c\right|}}$.
Then

$\left\|\Sigma_{\gamma}-\tilde{\Sigma}_{\gamma}\right\|\leq
4\frac{\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}}{\gamma^{2}-\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}}{\left|\tilde{\Sigma}_{\gamma}\right|},$

as long as
$\gamma^{2}\geq\frac{3}{2}\bar{Y}(1+(({\left|a\right|}+1)/{\left|c\right|})^{2}$.
Combining the above results with Proposition C.1 and the previous results in
section 4, the theorem follows. $\blacksquare$


$q^{\prime}(\vec{z},\vec{x})$ has no strong attack from $R$ to $S$; we need to
show that the attack graph of $q(\vec{z})$ has no strong attack from $R$ to
$S$.

If ${R}\stackrel{{\scriptstyle q^{\prime}}}{{\not\rightsquigarrow}}{S}$, then
${R}\stackrel{{\scriptstyle q}}{{\not\rightsquigarrow}}{S}$ by Lemma D.3, and
the desired result obtains. Assume from here on that
${R}\stackrel{{\scriptstyle q^{\prime}}}{{\rightsquigarrow}}{S}$, which must
be a weak attack. Assume for the sake of contradiction that $q(\vec{z})$’s
attack graph has a strong attack ${R}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{S}$.

Consequently,
$\mathcal{K}(q)\not\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(S)$ and
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(S)$.
We can assume a variable $y\in{\mathsf{Key}}(S)$ such that
$\mathcal{K}(q)\not\models{\mathsf{Key}}(R)\rightarrow y$ and
$\mathcal{K}(q^{\prime})\models{\mathsf{Key}}(R)\rightarrow y$. By Lemma D.2,
for some variable $x$ in $\vec{x}$, there is a path
$\pi=\langle{x,\ldots,y}\rangle$ in the query graph of $q$ such that for every
$u\in{\mathsf{vars}}(\pi)$,
$\mathcal{K}(q)\not\models{\mathsf{Key}}(R)\rightarrow u$. Consequently, for
every $u\in{\mathsf{vars}}(\pi)$,
$u\not\in{\mathsf{Key}}(R)\cup{\mathsf{frozen}}(q)$.

There is a witness $\langle{v_{1},\ldots,v_{n}}\rangle$ of
${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{S}$ with
$v_{n}\in{\mathsf{Key}}(S)$. It will be the case that
$v_{1}\in{\mathsf{notKey}}(R)$ and
$v_{1},\ldots,v_{n}\not\in{\mathsf{Key}}(R)$. By Lemma B.2,
$v_{1},\ldots,v_{n}\notin{\mathsf{frozen}}(q)$. Then
$\langle{x,\ldots,y}\rangle\cdot\langle{v_{n},v_{n-1},\ldots,v_{1}}\rangle$ is
a (not necessarily simple) path between a variable of $\vec{x}$ and a variable
of ${\mathsf{notKey}}(R)$ that uses no variable in
${\mathsf{Key}}(R)\cup{\mathsf{frozen}}(q)$. It follows that $\vec{x}$
violates condition (II)(2) of Definition 5.2, contradicting the lemma’s
hypothesis. ∎

##  Appendix E Proofs for Section 8

######  Lemma E.1.

Let $q(\vec{z})$ be a query in $\mathsf{Cforest}$, and let
$\langle{F_{1},\ldots,F_{n}}\rangle$ be a path in the Fuxman graph of
$q(\vec{z})$. Then,
$\mathcal{K}(q)\models{\mathsf{Key}}(F_{1})\rightarrow{\mathsf{Key}}(F_{n})$.

###### Proof.

By definition of a Fuxman graph, we have that for every
$i\in\\{1,\ldots,n-1\\}$,
${\mathsf{Key}}(F_{i+1})\setminus{\mathsf{free}}(q)\subseteq{\mathsf{notKey}}(F_{i})$.
This means that, for every $i\in\\{1,\ldots,n-1\\}$,
$\mathcal{K}(q)\models{\mathsf{Key}}(F_{i})\rightarrow{\mathsf{vars}}(F_{i+1})$.
By Armstrong’s transitivity axiom,
$\mathcal{K}(q)\models{\mathsf{Key}}(F_{1})\rightarrow{\mathsf{Key}}(F_{n})$.
∎

######  Lemma E.2.

Let $q(\vec{z})$ be a query in $\mathsf{Cforest}$. Let
$x,y\in{\mathsf{vars}}(q)$ be distinct variables that are connected in the
query graph of $q$. Let $R,S$ be two distinct atoms such that
$x\in{\mathsf{notKey}}(R)$ and $y\in{\mathsf{vars}}(S)$. Then, the Fuxman
graph of $q$ has a directed path from $R$ to $S$.

###### Proof.

We can assume a shortest path $\langle{v_{1},\ldots,v_{n}}\rangle$ in the
query graph, where $v_{1}=x$ and $v_{n}=y$. We can assume a sequence
$\langle{F_{1},\ldots,F_{n+1}}\rangle$ of atoms in ${\mathsf{body}}(q)$ such
that:

  * •

$F_{1}=R$;

  * •

$F_{n+1}=S$; and

  * •

for every $i\in\\{1,\ldots,n\\}$,
$v_{i}\in{\mathsf{vars}}(F_{i})\cap{\mathsf{vars}}(F_{i+1})$.

We will show by induction on increasing $i\in\\{1,\ldots,n\\}$, that
$\langle{F_{1},\ldots,F_{i+1}}\rangle$ is a path in the Fuxman graph of $q$.

_Basis $i=1$._ Since $v_{1}\notin{\mathsf{Key}}(F_{1})$ and
$v_{1}\in{\mathsf{vars}}(F_{1})\cap{\mathsf{vars}}(F_{2})$, there is a
directed edge from $F_{1}$ to $F_{2}$ in the Fuxman graph of $q$. _Induction
step $i-1\rightarrow i$._ The induction hypothesis is that
$\langle{F_{1},\ldots,F_{i}}\rangle$ is a path in the Fuxman graph of $q$. We
have that $v_{i}\in{\mathsf{vars}}(F_{i})\cap{\mathsf{vars}}(F_{i+1})$. Assume
for the sake of contradiction that $v_{i}\in{\mathsf{Key}}(F_{i})$. Then, by
definition of $\mathsf{Cforest}$, $v_{i}\in{\mathsf{vars}}(F_{i-1})$. Since we
also have $v_{i-2}\in{\mathsf{vars}}(F_{i-1})$, the query graph of
$q(\vec{z})$ contains an edge between $v_{i-2}$ and $v_{i}$. Then,
$\langle{v_{1},\ldots,v_{i-2},v_{i},\ldots,v_{n}}\rangle$ is a shorter path in
the query graph between $v_{1}$ and $v_{n}$, a contradiction. We conclude by
contradiction that $v_{i}\notin{\mathsf{Key}}(F_{i})$. It follows that the
Fuxman graph of $q$ has a directed edge from $F_{i}$ to $F_{i+1}$ and,
consequently, $\langle{F_{1},\ldots,F_{i+1}}\rangle$ is a path in the Fuxman
graph of $q$. By induction, we obtain that
$\langle{F_{1},\ldots,F_{n+1}}\rangle$ is a path in the Fuxman graph of $q$
from $R$ to $S$. ∎

######  Lemma E.3.

Let $q(\vec{z})$ be a query in $\mathsf{Cforest}$. Let $R,S$ be two distinct
atoms such that ${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{S}$. Then,
the Fuxman graph of $q$ has a directed path from $R$ to $S$.

###### Proof.

We can assume a sequence $\langle{v_{1},\ldots,v_{n}}\rangle$ that is a
witness of ${R}\stackrel{{\scriptstyle q}}{{\rightsquigarrow}}{S}$, where
$v_{1}\in{\mathsf{notKey}}(R)$ and $v_{n}\in{\mathsf{Key}}(S)$. This sequence
is obviously a path in the query graph of $q(\vec{z})$. The desired result
then follows by Lemma E.2. ∎

######  Lemma E.4.

Every query in $\mathsf{Cforest}$ has an acyclic attack graph.

###### Proof.

Fuxman [19] has shown that every query in $\mathsf{Cforest}$ has a consistent
first-order rewriting. From Theorem 3.1, it follows that every query in
$\mathsf{Cforest}$ has an acyclic attack graph. ∎

######  Lemma E.5.

If $q(\vec{z})\in\mathsf{Cforest}$, then every attack in $q(\vec{z})$’s attack
graph is weak.

###### Proof.

Let $q(\vec{z})\in\mathsf{Cforest}$. Let $R,S$ be two distinct atoms in
${\mathsf{body}}(q)$ such that ${R}\stackrel{{\scriptstyle
q}}{{\rightsquigarrow}}{S}$. By Lemma E.3, the Fuxman graph of $q$ has a
directed path $\langle{F_{1},\ldots,F_{n}}\rangle$ with $F_{1}=R$ and
$F_{n}=S$. By Lemma E.1,
$\mathcal{K}(q)\models{\mathsf{Key}}(R)\rightarrow{\mathsf{Key}}(S)$, and,
consequently, the attack from $R$ to $S$ is weak. ∎

######  Lemma E.6.

Let $q(\vec{z})\in\mathsf{Cforest}$. Let $\vec{x}$ be a $\subseteq$-minimal
tuple of bound variables such that for every root $R$ in the Fuxman graph of
$q(\vec{z})$, $\vec{x}$ contains every bound variable of ${\mathsf{Key}}(R)$.
Then, $\vec{x}$ verifies conditions (II)(1) and (II)(2) in Definition 5.2.

###### Proof.

We first show that $\vec{x}$ verifies condition (II)(1) in Definition 5.2.
Assume towards a contradiction that $q$’s attack graph has a component $C$
such that $\mathcal{K}(q)\not\models\vec{x}\rightarrow{\mathsf{Key}}(U)$ for
every unattacked atom $U$ that occurs in $C$. Since $q$’s attack graph is
acyclic by Lemma E.4, we can assume an atom $R$ in the component $C$ that is
unattacked. Consequently,
$\mathcal{K}(q)\not\models\vec{x}\rightarrow{\mathsf{Key}}(R)$. In the Fuxman
graph of $q$, let $S$ be the root of the tree that contains $R$. By the
hypothesis of the lemma, $\vec{x}$ contains every bound variable of
${\mathsf{Key}}(S)$. It follows:

$\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(S).$ (12)

If $R=S$, then it follows
$\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(R)$, a contradiction.
Assume next $R\neq S$. Since $S$ is the root of the tree in which $R$ appears,
there is a path from $S$ to $R$ in the Fuxman graph of $q$. By Lemma E.1, we
have $\mathcal{K}(q)\models{\mathsf{Key}}(S)\rightarrow{\mathsf{Key}}(R)$.
Using (12), we obtain
$\mathcal{K}(q)\models\vec{x}\rightarrow{\mathsf{Key}}(R)$, a contradiction.

We next show that $\vec{x}$ verifies condition (II)(2) in Definition 5.2.
Assume towards a contradiction that there is an atom $R$ in
${\mathsf{body}}(q(\vec{z}))$, and a path $\langle{v_{1},\ldots,v_{n}}\rangle$
in the query graph of $q(\vec{z})$ such that:

  * •

$v_{n}\in\vec{x}$;

  * •

$v_{1}\in{\mathsf{notKey}}(R)\setminus{\mathsf{free}}(q)$; and

  * •

for every $i\in\\{1,\ldots,n\\}$, $v_{i}\not\in{\mathsf{Key}}(R)$.

Since $\vec{x}$ is $\subseteq$-minimal, we can assume an atom $S$ that is a
root in $q$’s Fuxman graph such that $v_{n}\in{\mathsf{Key}}(S)$. Since
$v_{n}\not\in{\mathsf{Key}}(R)$, it follows $R\neq S$. By Lemma E.2, there is
a directed path from $R$ to $S$ in the Fuxman graph of $q$, contradicting that
$S$ is a root. ∎

###### Proof of Theorem 8.1.

From Lemmas E.4, E.5, and E.6, it follows that
$\mathsf{Cforest}\subseteq\mathsf{Cparsimony}$.

To show that $\mathsf{Cforest}$ is a strict subset, the query $q(z)=\exists
x\exists y\,R(\underline{x},y)\land S(\underline{x},y,z)$ is in
$\mathsf{Cparsimony}$ but not in $\mathsf{Cforest}$. ∎