# Performance-Robustness Tradeoffs in Adversarially Robust Linear-Quadratic
Control

Bruce D. Lee , Thomas T.C.K. Zhang11footnotemark: 1 , Hamed Hassani, and
Nikolai Matni Equal contribution

(Department of Electrical and Systems Engineering, University of Pennsylvania)

###### Abstract

While $\mathcal{H}_{\infty}$ methods can introduce robustness against worst-
case perturbations, their nominal performance under conventional stochastic
disturbances is often drastically reduced. Though this fundamental tradeoff
between nominal performance and robustness is known to exist, it is not well-
characterized in quantitative terms. Toward addressing this issue, we borrow
from the increasingly ubiquitous notion of adversarial training from machine
learning to construct a class of controllers which are optimized for
disturbances consisting of mixed stochastic and worst-case components. We find
that this problem admits a stationary optimal controller that has a simple
analytic form closely related to suboptimal $\mathcal{H}_{\infty}$ solutions.
We then provide a quantitative performance-robustness tradeoff analysis, in
which system-theoretic properties such as controllability and stability
explicitly manifest in an interpretable manner. This provides practitioners
with general guidance for determining how much robustness to incorporate based
on a priori system knowledge. We empirically validate our results by comparing
the performance of our controller against standard baselines, and plotting
tradeoff curves.

##  1 Introduction

Modern dynamical systems, from mobile robotics to power plants, require
controllers that are simultaneously fast, efficient, and robust. Many control
schemes attempt to simultaneously achieve these desiderata by combining them
into a single objective function and optimizing it. By combining these
distinct goals into a single objective, a natural tradeoff arises. A
controller optimized for speed and efficiency may perform poorly in the face
of unmodeled phenomena. For instance, Linear-Quadratic Gaussian (LQG)
controllers (a special case of $\mathcal{H}_{2}$ controllers) explicitly
prioritize nominal performance by penalizing the expectation of a quadratic
function of the state and input. It has been shown, however, that such
controllers can be extraordinarily fragile to small perturbations of the
dynamics (Doyle, 1978). Replacing the LQG objective with one that considers
the response of the system to worst-case perturbations of the dynamics and
external disturbances results in robust control methods, such as
$\mathcal{H}_{\infty}$ methods. Such controllers are provably robust, however
they tend to be overly conservative.

Toward achieving a balance between the performance of nominal and robust
controllers, various approaches have been introduced, most notably mixed
$\mathcal{H}_{2}/\mathcal{H}_{\infty}$ methods. However, the resulting
controllers are often complicated to express and compute (Scherer, 1995), and
lack a priori quantitative guarantees on how much nominal performance must be
given up so as to attain a desired robustness level. Toward addressing these
issues, we take inspiration from the notion of adversarial robustness from
machine learning (Madry et al., 2017; Carlini and Wagner, 2017) in order to
formulate a controller synthesis that balances performance and robustness. The
goal of adversarial robustness is to minimize the expected error under the
presence of worst-case norm-bounded perturbations to the data, where the
perturbations can depend on the underlying stochasticity of the problem, such
as the data distribution and additive noise. We consider an analogous
adversarially robust state feedback control problem where we aim to minimize
the expected LQ cost where the process noise is composed of two components: a
zero-mean stochastic noise component and a norm-bounded adversarial
perturbation. We show that the solution to this problem admits a closed-form
expression in terms of discrete algebraic Riccati equation (DARE) solutions,
which in turn allows for novel quantitative performance-robustness tradeoff
bounds in which system parameters manifest in a natural and interpretable way.

###  1.1 Contributions

  * •

Toward analyzing the adversarially robust control problem we propose, we first
show that when viewed through the lens of dynamic games (Basar, 1991),
adversarially robust LQ control relates to a control problem introduced in
Doyle et al. (1989). We show that the optimal solution to the state feedback
version of this problem is given by a central static suboptimal
$\mathcal{H}_{\infty}$ controller, with suboptimality level $\gamma$ depending
on both the stochastic noise statistics and the budget given to the adversary.
Furthermore, both the worst-case adversary and the corresponding optimal
controller can be computed from the solution of a DARE.

  * •

We quantify the performance-robustness tradeoffs of adversarially robust LQ
control, both analytically and empirically, and show a clear and interpretable
dependence on underlying system theoretic properties such as controllability
and stability. In particular, we show that the cost gap incurred by the
adversarially robust controller in the nominal setting over the nominal
controller is upper bounded by $O(\sigma_{w}^{2}\gamma^{-4}\nu^{-1})$, where
$\sigma_{w}^{2}$ is the covariance of the additive noise distribution,
$\gamma$ is the suboptimality level of the suboptimal $\mathcal{H}_{\infty}$
controller, and $\nu$ is the smallest singular value of the controllability
gramian. On the other hand, the cost gap is lower bounded by
$\Omega\mathopen{}\left(\sigma_{w}^{2}\gamma^{-4}\eta^{2}\right)\mathclose{}$,
where $\eta=\left\|W_{\infty}(A+BK_{\star},I)\right\|$ is the largest singular
value of the controllability gramian for closed loop system under the nominal
LQ controller with disturbances as the input. These results show that systems
with uniformly good controllability have small performance-robustness
tradeoffs, while those that have a highly controllable mode in the nominal
closed-loop system (when viewing disturbances as inputs) lead to large
performance-robustness tradeoffs.

###  1.2 Related Work

The mixed stochastic/worst-case problem that we consider is not the only way
to strike a balance between the performance of stochastic and robust control
methods. Most closely related is Doyle et al. (1989), which considers
disturbances composed of both a bounded power component, and a bounded power
spectrum component, and approaches the problem through a deterministic
viewpoint. Paganini (1993) considers a set description of disturbances that
also interpolates between $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$
approaches. Glover and Doyle (1988) provide the class of all stabilizing
controllers subject to a $\mathcal{H}_{\infty}$ norm constraint, while
Bernstein and Haddad (1988) and Rotea and Khargonekar (1991) consider
minimizing $\mathcal{H}_{2}$ objective subject to a $\mathcal{H}_{\infty}$
constraint. These methods often lack a simple closed-form stationary solution.
Other recent work attempts to reduce the conservatism of robust control by
taking a regret-minimization approach (Goel and Hassibi, 2020, 2021; Hazan et
al., 2020). None of the aforementioned methods provide a characterization of
the cost incurred by enforcing robustness.

Analogous recent work in the machine learning community has analyzed
performance-robustness tradeoffs in adversarially robust learning, including
precise characterizations of the generalization errors of standard versus
adversarially trained models under the random features model Javanmard et al.
(2020); Hassani and Javanmard (2022), and “no free lunch” theorems for
obtaining adversarially robust models Tsipras et al. (2018); Dohmatob (2019);
Yin et al. (2019). The successful characterization of such performance-
robustness tradeoffs in machine learning motivates the control objective we
consider. However, the theoretical results from this area are largely intended
for the supervised learning setting and do not immediately apply to our
setting. Al Makdah et al. (2020) proves the existence of performance-
robustness tradeoffs in control but does not characterize them quantitatively.
The extension of adversarial robustness results in machine learning to various
control problems is an active area of research (Lee et al., 2021; Zhang et
al., 2021; Havens et al., 2022).

Notation: The Euclidean norm of a vector $x\in\mathbb{R}^{n}$ is denoted by
$\left\|x\right\|$. The spectral norm of a matrix $A\in\mathbb{R}^{m\times n}$
is denoted $\left\|A\right\|$, and the Frobenius norm of
$A\in\mathbb{R}^{m\times n}$ is denoted $\left\|A\right\|_{F}$. The spectral
radius of a square matrix $A\in\mathbb{R}^{n\times n}$ is denoted $\rho(A)$. A
symmetric, positive semidefinite (psd) matrix $A=A^{\top}$ is denoted
$A\succeq 0$. Similarly $A\succeq B$ denotes that $A-B$ is positive
semidefinite. A symmetric positive definite (pd) matrix $A=A^{\top}$ is
denoted $A\succ 0$. A sequence of vectors $x_{t}\in\mathbb{R}^{n}$ defined for
$t\geq 0$ will be denoted by
$\mathbf{x}=\mathopen{}\left\\{x_{t}\right\\}\mathclose{}_{t\geq 0}$. The
$\ell^{2}$ signal-norm of a sequence is denoted by
$\left\|\mathbf{x}\right\|_{\ell^{2}}$. The solutions to a discrete Lyapunov
equation and discrete algebraic Riccati equation are denoted
$\textnormal{{dlyap}}(A,Q)$ and $\textnormal{{DARE}}(A,B,Q,R)$, respectively.

##  2 Adversarially Robust Linear-Quadratic Control

Consider a fully observed discrete-time linear-time-invariant (LTI) system
with state disturbances composed of both stochastic and adversarial
components: let $x_{t}\in\mathbb{R}^{n}$ be the system state,
$u_{t}\in\mathbb{R}^{m}$ the input, $w_{t}\in\mathbb{R}^{n}$ and
$\delta_{t}\in\mathbb{R}^{n}$ the stochastic and adversarial components of the
process disturbance, respectively. The initial condition $x_{0}$ and
stochastic component of the process noise $w_{t}$ are assumed to be i.i.d.
zero-mean with covariance matrices $\Sigma_{0},\;\Sigma_{w}$, respectively,
and $\mathbb{E}\mathopen{}\left[x_{0}w_{t}^{\top}\right]\mathclose{}=0$ for
all $t\geq 0$. The LTI system is then defined by the following equation:

$\displaystyle x_{t+1}$ $\displaystyle=Ax_{t}+Bu_{t}+w_{t}+\delta_{t}.$ (1)

We assume that the adversarial perturbation sequence $\bm{\delta}$ is causal,
i.e., it can depend only on the states, inputs, and stochastic noise up to the
current timestep; in particular, it must be a measureable function of the
randomness $x_{0},w_{0:t}$. We let $Q\succeq 0$ be a weight matrix for the
state cost, and $R\succ 0$ be a weight matrix for the input cost. We consider
the infinite horizon objective

$\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}_{\mathbf{w},x_{0}}\mathopen{}\left[x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}\right]\mathclose{}$

subject to the dynamics (1). If the adversarial perturbation is set to zero,
$\bm{\delta}=0$, then the above objective is the nominal LQR problem. If the
stochasticity is set to zero, $\bm{w},x_{0}=0$, and $\bm{\delta}$ are worst-
case perturbations with average power bounded by $\varepsilon$, the above
objective is the $\mathcal{H}_{\infty}$ problem. When both stochastic noise
and worst-case perturbations are present, we define the resulting control task
as the adversarially robust LQR problem. We denote the three corresponding
objectives by $\operatorname{NC}$, $\operatorname{RC}$, and
$\operatorname{AC}$ respectively:

$\displaystyle\operatorname{NC}(K)$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}_{\mathbf{w},x_{0}}\mathopen{}\left[x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}\mathopen{}\left(Q+K^{\top}RK\right)\mathclose{}x_{t}\right]\mathclose{},\;\;x_{t+1}=(A+BK)x_{t}+w_{t}$
(2) $\displaystyle\operatorname{RC}(K)$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\max_{\begin{subarray}{c}\bm{\delta}\mbox{
causal}\\\ \left\|\bm{\delta}\right\|_{\ell_{2}}^{2}\leq
T\varepsilon\end{subarray}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}(Q+K^{\top}RK)x_{t},\;\;x_{t+1}=(A+BK)x_{t}+\delta_{t},\;x_{0}=0$
(3) $\displaystyle\operatorname{AC}(K)$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}_{\mathbf{w},x_{0}}\mathopen{}\left[\max_{\begin{subarray}{c}\bm{\delta}\mbox{
causal}\\\ \left\|\bm{\delta}\right\|_{\ell_{2}}^{2}\leq
T\varepsilon\end{subarray}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}(Q+K^{\top}RK)x_{t}\right]\mathclose{},\;\;x_{t+1}=(A+BK)x_{t}+w_{t}+\delta_{t}$
(4)

The adversarial budget $\left\|\bm{\delta}\right\|_{\ell^{2}}^{2}\leq
T\varepsilon$ is chosen such that the instance-wise adversarial budget
satisfies $\left\|\delta_{t}\right\|^{2}\leq\varepsilon$ on average. We note
that our attention is restricted to static state feedback control policies
$u_{t}=Kx_{t}$, as they are known to be optimal for $\operatorname{NC}$ and
$\operatorname{RC}$ (Zhou et al., 1996). We will show, as a consequence of
Lemma 2.1 and Theorem 2.1, that they are in fact also optimal for
$\operatorname{AC}$. In order to ensure that there exists a stabilizing
controller, and that minimizing either $\operatorname{NC}$ or
$\operatorname{RC}$ provides a stabilizing controller, we make the standard
assumption that $(A,B,Q^{1/2})$ is stabilizable and detectable (Zhou et al.,
1996). Under this assumption, there exists a stabilizing state feedback
control law $u_{t}=Kx_{t}$ minimizing $\operatorname{NC}$, where

$\displaystyle K=-(R+B^{\top}PB)^{-1}B^{\top}PA$ (5)

and $P$ is the solution to the Discrete Algebraic Riccati Equation (DARE)

$\displaystyle P=Q+A^{\top}PA-A^{\top}PB(R+B^{\top}PB)^{-1}B^{\top}PA.$ (6)

A solution minimizing $\operatorname{RC}$ may be found using Theorem 13.3.3 of
Hassibi et al. (1999).

The remainder of this section is devoted to finding a controller minimizing
$\operatorname{AC}$. Inspired by minimax dynamic games (Basar, 1991), we first
find a controller which minimizes a soft-constrained version of the
adversarial cost (4):

$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\bm{\delta}\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}.$
(7)

The following lemma provides necessary and sufficient conditions for the
existence of a stabilizing controller which minimizes the above objective.
Similar statements in continuous time may be extracted from a more general
result found in Doyle et al. (1989).

###### Lemma 2.1

A controller attaining a finite value for objective (7) exists if and only if
there exists a solution to the following discrete algebraic Riccati equation

$\displaystyle
P=Q+A^{\top}PA-A^{\top}P\begin{bmatrix}B&I\end{bmatrix}\mathopen{}\left(\begin{bmatrix}B&I\end{bmatrix}^{\top}P\begin{bmatrix}B&I\end{bmatrix}+\begin{bmatrix}R&0\\\
0&-\gamma^{2}I\end{bmatrix}\right)\mathclose{}^{-1}\begin{bmatrix}B&I\end{bmatrix}^{\top}PA$
(8)

satisfying $0\preceq P\prec\gamma^{2}I$. As long as the above condition is
true,

  1. 1.

The controller $u_{t}=Kx_{t}$ with $K$ given by

$\displaystyle K$ $\displaystyle=-(R+B^{\top}MB)^{-1}B^{\top}MA,$ (9)
$\displaystyle M$ $\displaystyle=P+P(\gamma^{2}I-P)^{-1}P.$

satisfies $\rho(A+BK)<1$, and minimizes the objective (7).

  2. 2.

The optimal adversarial perturbation under the controller $u_{t}=Kx_{t}$ is
given by

$\displaystyle\Delta$ $\displaystyle=(\gamma^{2}I-P)^{-1}P$ (10)
$\displaystyle\delta_{t}$ $\displaystyle=\Delta((A+BK)x_{t}+w_{t}).$

  3. 3.

The objective value (7) achieved under controller (9) and adversary (10) is
$\operatorname{Tr}(M\Sigma_{w})$.

The solution approach for the above problem follows that in Basar (1991) for
minimax games. The finite horizon version of the problem is solved by defining
a saddle point cost-to-go, then recursing backwards in time, solving both an
unconstrained concave maximization problem and convex minimization problem at
each time step to determine the optimal adversarial perturbation and control
input. The causality of $\bm{\delta}$ is necessary in the recursion to pull
$\delta_{t}$ out of an expectation over future noise terms. Taking the limit
as the horizon tends to infinity provides the steady state controller and
adversary in the above lemma statement. It should be noted that in contrast to
most adversarially robust machine learning problems, adversarially robust LQR
provides a closed form expression for the adversarial perturbation.

We now return our attention to the objective (4). We show via strong duality
that the hard-constrained problem may be solved by sequentially solving the
soft-constrained problem using Lemma 2.1. Note that in contrast to the
solution approach to minimize $\operatorname{RC}$, dualizing the constraint in
$\operatorname{AC}$ results in an optimal dual variable $\gamma(\varepsilon)$
that is a random variable. Therefore, it is nontrivial to exchange the order
of the minimization over the dual variable with the expectation (see Appendix
B for details). We propose Algorithm 1 to minimize the adversarial cost AC
(4).

Algorithm 1 Computing Adversarially Robust Controller:
AdvLQR$(A,B,Q,R,\varepsilon,\gamma_{LB},\gamma_{UB},\texttt{tol})$

1:Input: State matrices $A,B$, cost matrices $Q,R$, adversary budget
$\varepsilon>0$, binary search bounds $\gamma_{LB}<\gamma_{UB}$, tolerance
tol.

2:// _Do binary search on $\gamma\in[\gamma_{LB},\gamma_{UB}]$ to find optimal
adversary with average power $\varepsilon>0$_

3:while $\gamma_{UB}-\gamma_{LB}\geq\texttt{tol}$ do

4: $\gamma=(\gamma_{UB}+\gamma_{LB})/2$

5: Compute $P,M,K,\Delta$ at level $\gamma$ via (8)-(10)

6: $G=\textnormal{{dlyap}}((A+BK)^{\top}\Delta,\Delta\Sigma_{w}\Delta)$.

7: if
$\operatorname{Tr}(G(A+BK)^{\top}(I+\Delta)^{2}(A+BK)+\Delta\Sigma_{w}\Delta)<\varepsilon$
(11) then

8: $\gamma_{UB}=\gamma$

9: else

10: $\gamma_{LB}=\gamma$

11: end if

12:end while

13:Output: Adversarially robust LQR controller $K$, adversary gain $\Delta$,
optimal value of (4) $\operatorname{Tr}(M\Sigma_{w})+\gamma^{2}\varepsilon$.

###### Theorem 2.1

Suppose $(A,B,Q^{1/2})$ is stabilizable and detectable. Let $\gamma_{\infty}$
be the optimal closed-loop $\mathcal{H}_{\infty}$ gain of system (1). For any
$\varepsilon>0$, let $\gamma_{UB}>\gamma_{\infty}$ satisfy the following
condition: if $P,M,K,\Delta$ satisfy equations (8)-(10) at level $\gamma_{UB}$
and $G:=\textnormal{{dlyap}}((A+BK)^{\top}\Delta,\Delta\Sigma_{w}\Delta)$,
then for the disturbance $\delta_{t}$ in equation (10),

$\displaystyle\lim_{t\to\infty}\mathbb{E}\mathopen{}\left[\delta_{t}^{\top}\delta_{t}\right]\mathclose{}=\operatorname{Tr}(G(A+BK)^{\top}(I+\Delta)^{2}(A+BK)+\Delta\Sigma_{w}\Delta)<\varepsilon.$
(11)

Under these conditions, the output of Algorithm 1
AdvLQR$(A,B,Q,R,\varepsilon,\gamma_{\infty},\gamma_{UB},\textnormal{{tol}})$
satisfies

  1. 1.

The control policy $u_{t}=Kx_{t}$ minimizes $\operatorname{AC}(K)$.

  2. 2.

The optimal adversarial perturbation in equation (4) under the optimal policy
is $\delta_{t}=\Delta\mathopen{}\left((A+BK)x_{t}+w_{t}\right)\mathclose{}$
and satisfies
$\lim_{t\to\infty}\mathbb{E}\mathopen{}\left[\delta_{t}^{\top}\delta_{t}\right]\mathclose{}\leq\varepsilon$.

  3. 3.

The minimum value for the adversarial cost (4) is given by
$\operatorname{Tr}(M\Sigma_{w})+\gamma^{2}\varepsilon$.

We make the interesting observation from Theorem 2.1 that while the nominal
LQR controller is independent of the noise statistics, the adversarially
robust controller output by Algorithm 1 is dependent on the noise statistics
through the optimal choice of $\gamma$.

###### Remark 2.1

We note that the same results used to solve for the optimal controller
minimizing $\operatorname{AC}(K)$ may be adapted to evaluate
$\operatorname{AC}(K)$ under an arbitrary stabilizing controller $K$. In
particular, observe that $(A+BK,0)$ is stabilizable, and
$((Q+K^{\top}RK)^{1/2},A+BK)$ is detectable. Then considering the closed loop
system and cost matrices
$(A^{\prime},B^{\prime},Q^{\prime},R^{\prime}):=(A+BK,0,Q+K^{\top}RK,0)$, we
see that Lemma 2.1 implies that under controller $u_{t}=Kx_{t}$, equation (7)
evaluates to $\operatorname{Tr}(M\Sigma_{w})$, where
$M=P+P(\gamma^{2}I-P)^{-1}P$, and
$P=\textnormal{{DARE}}(A+BK,I,Q+K^{\top}RK,-\gamma^{2}I)$. Similarly, Theorem
2.1 tells us that for any $\varepsilon>0$, with properly selected
$\gamma_{UB},\gamma_{LB}$ and tol, $\operatorname{AC}(K)$ may be determined
via Algorithm 1 as
AdvLQR$(A+BK,0,Q+K^{\top}RK,0,\varepsilon,\gamma_{LB},\gamma_{UB},\texttt{tol})$.

##  3 Performance-Robustness Tradeoff Bounds

This section presents the main results of the paper: we study the tradeoffs
that arise in adversarial control by investigating the interplay between the
two objectives (2) and (4). This section will focus on bounding the tradeoffs
analytically. The next section will validate these analytical bounds by
empirically examining tradeoff curves for particular systems.

We begin by considering the gap between the nominal controller and the
$\gamma$-adversarially robust controller when applied in the nominal setting,
i.e., we seek to bound the gap
$\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K_{\star})$, where
$K_{\gamma}$ is the $\gamma$-adversarially robust controller given by Lemma
2.1, and $K_{\star}$ is the nominal LQR controller given by equation (5). Let
$P_{\star}$ be the nominal DARE solution given by the solution to equation
(6), and let $P_{\gamma}$ be the solution to equation (8). Also define

$\displaystyle
M_{\gamma}:=P_{\gamma}+P_{\gamma}(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}.$
(12)

Given an arbitrary stabilizing linear feedback controller $K$, results from
Mania et al. (2019) and Fazel et al. (2018) allow us to characterize the gap
in the cost between $K$ and the optimal LQR controller $K_{\star}$ as

$\displaystyle\operatorname{NC}(K)-\operatorname{NC}(K_{\star})=\operatorname{Tr}(\Sigma(K)(K-K_{\star})^{\top}(R+B^{\top}P_{\star}B)(K-K_{\star}))$
(13)

where $\Sigma(K)=\textnormal{{dlyap}}(A+BK,\Sigma_{w})$ is the steady state
covariance of the closed loop system under controller $K$. The following
bounds on the gap $\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K_{\star})$
then follow immediately:

$\displaystyle\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K_{\star})$
$\displaystyle\geq\sigma_{\min}(\Sigma_{w})\sigma_{\min}(R+B^{\top}P_{\star}B)\left\|K_{\gamma}-K_{\star}\right\|_{F}^{2}$
(14) $\displaystyle\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K_{\star})$
$\displaystyle\leq\left\|\Sigma(K_{\gamma})\right\|\left\|R+B^{\top}P_{\star}B\right\|\left\|K_{\gamma}-K_{\star}\right\|_{F}^{2}.$
(15)

We have therefore reduced the task of upper and lower bounding the cost gap
between the $\gamma$-adversarially robust controller and the nominal LQR
controller in the nominal setting to directly bounding the gap between the two
controllers. Recalling that
$\left\|K_{\gamma}-K_{\star}\right\|^{2}_{F}\leq\min\mathopen{}\left\\{m,n\right\\}\mathclose{}\left\|K_{\gamma}-K_{\star}\right\|^{2}$,
we use the following lemma to bound the difference
$\left\|K_{\gamma}-K_{\star}\right\|$ in terms of the difference between the
solutions to the corresponding adversarial and nominal DAREs.

###### Lemma 3.1

(Adapted from Lemma 2 of Mania et al. (2019)) Suppose that
$f_{1}(u;x)=\frac{1}{2}u^{\top}Ru+\frac{1}{2}(Ax+Bu)^{\top}M(Ax+Bu)$ and
$f_{2}(u;x)=\frac{1}{2}u^{\top}Ru+\frac{1}{2}(Ax+Bu)^{\top}P(Ax+Bu)$ with
$M\succeq P$. Furthermore, for any $x$, let
$u_{i}=K_{i}x=\operatorname*{argmin}_{u}f_{i}(u,x)$. Then we have that

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

For the rest of this paper, we assume for simplicity that
$\Sigma_{w}=\sigma_{w}^{2}I$. We also define $\gamma_{\infty}$ as the minimum
$\mathcal{H}_{\infty}$ norm for the closed loop system, i.e., the smallest
value of $\gamma$ for which the conditions of Lemma 2.1 hold. Similarly, we
define $\tilde{\gamma}_{\infty}$ as the $\mathcal{H}_{\infty}$ norm of the
closed loop system under the nominal LQR controller. Additionally, we define
the $\ell$-step controllability gramian as
$W_{\ell}(A,B):=\sum_{t=0}^{\ell}A^{t}BB^{\top}(A^{t})^{\top}$. If $\rho(A)<1$
we define the controllability gramian as
$W_{\infty}(A,B):=\lim_{\ell\to\infty}W_{\ell}(A,B)$.

###  3.1 Upper Bound

Applying Lemma 3.1 with $P=P_{\star}$ and $M=M_{\gamma}$ reduces our goal to
bounding the spectrum of $M_{\gamma}-P_{\star}$. From the definition of
$M_{\gamma}$ (12), we can write
$\left\|P_{\star}-M_{\gamma}\right\|\leq\left\|P_{\star}-P_{\gamma}\right\|+\frac{\left\|P_{\gamma}\right\|^{2}}{\gamma^{2}-\left\|P_{\gamma}\right\|}.$
For $\gamma>\gamma_{\infty}$ we have $P_{\gamma}\prec
P_{\gamma_{\infty}}\prec\gamma_{\infty}^{2}I$ (Lemma C.3), and thus
$\left\|P_{\star}-M_{\gamma}\right\|\leq\left\|P_{\star}-P_{\gamma}\right\|+\frac{\gamma_{\infty}^{4}}{\gamma^{2}-\gamma_{\infty}^{2}},$
reducing our task to bounding $\left\|P_{\star}-P_{\gamma}\right\|$, the gap
between solutions to the $\gamma$-adversarial and nominal DAREs.

Toward bounding the norm difference of solutions to DAREs, we show that the
closed loop dynamics under the adversary $\delta_{t}$ can be expressed as
perturbations of the nominal system matrices. In particular, recall that for
the a noiseless adversarial LQR instance at level $\gamma>0$, the adversary
can be represented as
$\delta_{t}=\mathopen{}\left(\gamma^{2}I-P_{\gamma}\right)\mathclose{}^{-1}P_{\gamma}\mathopen{}\left(Ax_{t}+Bu_{t}\right)\mathclose{},$
such that we may write
$x_{t+1}=Ax_{t}+Bu_{t}+\delta_{t}=\tilde{A}x_{t}+\tilde{B}u_{t}$, for
$\tilde{A}:=\mathopen{}\left(I+(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}\right)\mathclose{}A$
and
$\tilde{B}:=\mathopen{}\left(I+(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}\right)\mathclose{}B$.
This allows us to bound the gaps $||\tilde{A}-A||,\;||\tilde{B}-B||$ in terms
of $\gamma$. This is formalized in Lemma C.4 in Appendix C.2.

By bounding the gap between system matrices in the adversarial setting and in
the nominal setting, we derive perturbation bounds on the gap
$\left\|P_{\gamma}-P_{\star}\right\|$ between the adversarial and nominal DARE
solutions, which ultimately leads to the following upper bound on
$\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K_{\star})$.

###### Theorem 3.1

Suppose $(A,B,Q^{1/2})$ is controllable and detectable. Define the condition
number
$\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}}\tau\mathopen{}\left(A,\rho\right)\mathclose{}+\rho\right\\}\mathclose{}$,
where $\rho>\rho(A)$. Furthermore, let $\ell$ be any natural number
$1\leq\ell\leq n$. For $\gamma>0$ satisfying

$\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 upper bound holds:

$\displaystyle\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K)$
$\displaystyle\leq
O(1)\sigma_{w}^{2}\Big{(}\frac{\gamma_{\infty}^{4}}{\gamma^{2}-\gamma_{\infty}^{2}}\Big{)}^{2}m\ell^{5}\beta^{4(\ell-1)}\mathopen{}\left(1+\sigma_{\min}(W_{\ell}(A,B))^{-1/2}\right)\mathclose{}^{2}$
$\displaystyle\quad\cdot\left\|A+BK_{\star}\right\|^{2}\left\|W_{\infty}(A+BK_{\gamma},I)\right\|\tau(A,\rho)^{6}$
$\displaystyle\quad\cdot\frac{\left\|R+B^{\top}P_{\star}B\right\|}{\sigma_{\min}\mathopen{}\left(R+B^{\top}P_{\star}B\right)\mathclose{}^{2}}\kappa(Q,R)^{2}\left\|B\right\|^{2}\mathopen{}\left(\left\|B\right\|+1\right)\mathclose{}^{4}\left\|P_{\star}\right\|^{2}.$

As $\gamma\to\infty$, our upper bound decays to $0$ as expected, since the
adversarial controller converges to the nominal controller in the limit.
However, the steepness of this cost gap is affected by system properties such
as the minimum singular value of the $\ell$-step controllability gramian,
where poor controllability causes the upper bound to increase. We note that in
contrast to the perturbation gap requirements in Mania et al. (2019), our
condition on the perturbation gap via lower bounds on $\gamma$ are much less
stringent. We only require a lower bound on $\gamma$ to guarantee that the
controllability of the adversarially perturbed system $(\tilde{A},\tilde{B})$
is on the same order of magnitude as that of the nominal system $(A,B)$.

###  3.2 Lower Bound

Applying Lemma 3.1 with $M=M_{\gamma}$ and $P=P_{\star}$, we conclude that

$\displaystyle\left\|K_{\gamma}-K_{\star}\right\|$
$\displaystyle\geq\frac{\left\|B^{\top}(M_{\gamma}-P_{\star})(A+BK_{\star})\right\|}{\left\|R+BM_{\gamma}B\right\|}\geq\frac{\left\|B^{\top}(M_{\gamma}-P_{\star})\right\|\sigma_{\min}(A+BK_{\star})}{\left\|R+BM_{\gamma}B\right\|}.$
(16)

Next, we add and subtract a particular DARE solution to the
$M_{\gamma}-P_{\star}$ term in the above bound. Specifically, for
$\gamma\geq\tilde{\gamma}_{\infty}$, we let
$\tilde{P}_{\gamma}=\textnormal{{DARE}}(A+BK_{\star},I,Q,-\gamma^{2}I)$, and
note that $x^{\top}\tilde{P}_{\gamma}x$ represents the cost of applying
controller $K_{\star}$ in the adversarial setting at level $\gamma$ starting
from state $x$ with $w_{t}=0$ for all $t\geq 0$. Adding and subtracting
$\tilde{P}_{\gamma}$ in the lower bound in (16) yields

$\displaystyle\left\|K_{\gamma}-K_{\star}\right\|$
$\displaystyle\geq\frac{\left\|B^{\top}(M_{\gamma}-\tilde{P}_{\gamma}+\tilde{P}_{\gamma}-P_{\star})\right\|\sigma_{\min}(A+BK_{\star})}{\left\|R+BM_{\gamma}B\right\|}$
$\displaystyle\geq\frac{\sigma_{\min}(A+BK_{\star})}{\left\|R+BM_{\gamma}B\right\|}\mathopen{}\left(\left\|B^{\top}(P_{\gamma}(\gamma^{2}I-P_{\gamma})^{-1}P_{\gamma}+\tilde{P}_{\gamma}-P_{\star})\right\|-\left\|B^{\top}(\tilde{P}_{\gamma}-P_{\gamma})\right\|\right)\mathclose{}.$
(17)

To obtain a lower bound on the above expression, we can upper and lower bound
the spectra of $\tilde{P}_{\gamma}-P_{\gamma}$ and
$\tilde{P}_{\gamma}-P_{\star}$, respectively. To upper bound the spectrum of
$\tilde{P}_{\gamma}-P_{\gamma}$, we apply a result similar to equation (13)
for the noiseless setting. We may lower bound the spectrum of
$\tilde{P}_{\gamma}-P_{\star}$ by writing each as the solution to a Lyapunov
equation and observing that their difference may also be written as the
solution to a Lyapunov equation. This is stated formally and proven in Lemma
C.5. Combining the above leads to the following theorem.

###### Theorem 3.2

Suppose $(A,B,Q^{1/2})$ is stabilizable and detectable,
$\gamma\geq\tilde{\gamma}_{\infty}$, and

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

Then the following lower bound holds:

$\displaystyle\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K_{\star})$
$\displaystyle\geq\frac{\sigma_{w}^{2}}{2}\bigg{(}\frac{\sigma_{\min}(P_{\star})^{2}}{\gamma^{2}-\sigma_{\min}(P_{\star})}\bigg{)}^{2}\frac{\sigma_{\min}(R+B^{\top}P_{\star}B)}{\left\|R+B^{\top}M_{\gamma}B\right\|^{2}}\left\|B^{\top}W_{\infty}(A+BK_{\star},I)\right\|^{2}\sigma_{\min}(A+BK_{\star})^{2}.$

Keeping the nominal system fixed, both the upper and lower bounds decay at a
rate $\gamma^{-4}$. We note that instead of the $\ell$-step controllability
gramian that manifests in the upper bound, we have instead the system
parameter $W_{\infty}(A+BK_{\star},I)$, which can be seen as a “disturbability
gramian”, which is the controllability gramian of the closed loop system under
controller $K_{\star}$ with disturbances as inputs. That is, a large
$\left\|B^{\top}W_{\infty}(A+BK_{\star},I)\right\|$ implies that the nominal
closed-loop system is quantifiably more controllable by the distrubance input,
hence more susceptible to adversarial disturbances of fixed energy.

To apply the upper and lower bounds to the adversarial setting with fixed
adversarial budget $\varepsilon$, one may find the optimal corresponding
$\gamma$ via Algorithm 1.

##  4 Numerical Experiments

We now empirically study the trends suggested by our adversarially robust
controller synthesis and the subsequent performance-robustness tradeoff
bounds.

(a) Tradeoff curves

(b) Tradeoff envelope

Figure 1:  (a) For each value of the system parameter $\rho$, the tradeoff
curves are generated by synthesizing adversarially robust controllers for
adversarial levels $\varepsilon$ ranging from $[0,0.1]$, and then evaluating
both their nominal cost, and their adversarial cost at level
$\varepsilon=0.1$. (b) We plot the nominal vs. adversarial performance (at
level $\varepsilon=0.1$) of the nominal LQR controller and the adversarially
robust controller at level $\varepsilon=0.1$, as the system parameter $\rho$
ranges from $0.3$ to $1.2$. The value of $\rho$ increases in the directions of
the arrows.

(a) Gaussian noise

(b) Varying mean Gaussian

(c) Adversarial setting

Figure 2:  Simulations of the performance of $\mathcal{H}_{2}$,
$\mathcal{H}_{\infty}$, mixed $\mathcal{H}_{2}/\mathcal{H}_{\infty}$, and
adversarially robust controllers on a linearized Boeing longitudinal flight
control task. The average running cost at time $t$ is computed as
$\frac{1}{t}\sum_{k=0}^{t}x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k}$.

#### Impact of Controllability

To illustrate the dependence of the tradeoff severity on system
controllability, consider the simple integrator system defined by
$(A,B,Q,R,\Sigma_{w})=\mathopen{}\left(\begin{bmatrix}1&\rho\\\
0&1\end{bmatrix},\begin{bmatrix}0\\\ 1\end{bmatrix},I,I,I\right)\mathclose{}$
where we vary the controllability of the system by changing $\rho$. In
particular, when $\rho$ is very small, the system has poor controllability,
and as $\rho$ increases, controllability increases. In Figure 1a, we consider
the tradeoff curves traced out by evaluating the nominal cost and adversarial
cost (evaluated with budget $\varepsilon=0.1$) of adversarially robust
controllers with adversarial budget varying between
$\mathopen{}\left[0,0.1\right]\mathclose{}$, given a certain level of
controllability determined by $\rho$. We observe that as controllability
decreases, not only do the tradeoff curves shift upward, but the curves also
widen. This corroborates the trend described in Theorem 3.1, where we show the
bound on the nominal cost gap between adversarially robust and nominal
controllers (i.e. width of the tradeoff curve) grows larger as controllability
decreases. This trend is further illustrated in Figure 1b, where we plot the
nominal and adversarial ($\varepsilon=0.1$) costs attained by the
$\mathcal{H}_{2}$ and adversarially robust ($\varepsilon=0.1$) controllers as
a function of $\rho$, which we vary from $0.3$ to $1.2$. We observe that for
small $\rho$, the system has poor controllability, and thus the distance
between the $\mathcal{H}_{2}$ and adversarially robust controller costs is
large. As controllability increases, we see this gap decrease monotonically.
We note that the costs do not monotonically improve as $\rho$ increases after
some point, as the amplification of disturbances from the integrator will
outstrip the benefits of improved controllability.

#### Performance of Adversarially Robust Control

We compare the performance of the adversarially robust LQR controller against
$\mathcal{H}_{2}$, $\mathcal{H}_{\infty}$, and mixed
$\mathcal{H}_{2}/\mathcal{H}_{\infty}$ control for the longitudinal flight
control of the following linearized Boeing 747 system (see Hong et al. (2021)
for further details) with

$\displaystyle x_{t+1}$ $\displaystyle=\begin{bmatrix}0.99&0.03&-.02&-.32\\\
0.01&0.47&4.7&.00\\\ .02&-.06&.40&.00\\\
0.01&-.04&.72&.99\end{bmatrix}x_{t}\begin{bmatrix}.01&.99\\\ -3.44&1.66\\\
-.83&.44\\\ -.47&.25\end{bmatrix}u_{t}+w_{t},\quad Q=I,R=I$

under the presence of various disturbances $w_{t}$:
$w_{t}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,I)$,
$w_{t}\sim\mathcal{N}(\sin(0.01t),I)$, and $w_{t}$ given by zero mean,
identity covariance Gaussian noise plus the worst case adversarial
perturbation with power bounded by $\epsilon=0.5$. The initial condition is
set to zero in all cases.

The optimal adversarially robust controller is generated by running Algorithm
1 with $\varepsilon=0.5$, $Q=I,R=I$, $\Sigma_{w}=I$ and the mixed
$\mathcal{H}_{2}/\mathcal{H}_{\infty}$ controller was generated by fixing a
$\mathcal{H}_{\infty}$ norm bound of $\gamma=1000$, and approximately
minimizing the $\mathcal{H}_{2}$ norm via the approach outlined in de Oliveira
et al. (1999). The $\mathcal{H}_{\infty}$ norm bound $\gamma$ for mixed
$\mathcal{H}_{2}/\mathcal{H}_{\infty}$ was chosen to achieve performance
similar to the adversarially robust controller in the adversarial setting. We
observe that in Figure 2a under the pure zero-mean Gaussian setting, the
$\mathcal{H}_{2}$ controller performs best. We note that the adversarially
robust controller has performance comparable to $\mathcal{H}_{2}$.
Interestingly, the adversarially robust controller outperforms all three
controllers on the varying-mean Gaussian disturbance in Figure 2b, which we
note is an instance of a disturbance composed of both zero-mean stochastic and
deterministic components. Lastly, as expected, the adversarially robust
controller performs best in the adversarial setting of Figure 2c.

##  5 Conclusion

We proposed an adversarially robust LQ control problem, and demonstrated that
the optimal solution to this problem is given by a central static suboptimal
$\mathcal{H}_{\infty}$ controller. An interesting aspect of this solution is
that unlike pure $\mathcal{H}_{2}$ controllers, the adversarially robust
controller depends upon the noise statistics. Experiments show that the
adversarially robust controller performs similar to mixed
$\mathcal{H}_{2}/\mathcal{H}_{\infty}$ controllers on a simple system.

We used the adversarially robust control problem as a means to study
performance-robustness tradeoffs in control. In particular, we derived
quantitative upper and lower bounds on the performance gap between the nominal
controller the adversarially robust controller. The bounds show that systems
with uniformly good controllability will have small performance-robustness
tradeoffs, while those with a highly controllable mode in the closed-loop
system (viewing disturbances as inputs) will have a large performance-
robustness tradeoff. These trends are corroborated by experiments with a
simple linear system by tracing out tradeoff curves. Directions for future
work include the extension of the problem setting considered here to the
measurement feedback setting, and considering how other adversarial training
techniques can be translated to robust controller synthesis.

## Acknowledgements

Bruce D. Lee is supported by the Department of Defense through the National
Defense Science & Engineering Graduate Fellowship Program. The research of
Hamed Hassani is supported by NSF Grants 1837253, 1943064, 1934876, AFOSR
Grant FA9550-20-1-0111, and DCIST-CRA. Nikolai Matni is funded by NSF awards
CPS-2038873, CAREER award ECCS-2045834, and a Google Research Scholar award.

## References

  * Al Makdah et al. (2020) A. A. Al Makdah, V. Katewa, and F. Pasqualetti.  Accuracy prevents robustness in perception-based control.  In _2020 American Control Conference (ACC)_ , pages 3940–3946. IEEE, 2020.
  * Basar (1991) T. Basar.  _$\mathcal{H}_{\infty}$ Optimal Control and Related Minimax Design Problems_.  Birkhäuser, 1991.
  * Bernstein and Haddad (1988) D. S. Bernstein and W. M. Haddad.  Lqg control with an $\mathcal{H}_{\infty}$ performance bound: a riccati equation approach.  In _1988 American Control Conference_ , pages 796–802, 1988.  doi: 10.23919/ACC.1988.4789831.
  * Boyd and Vandenberghe (2004) S. P. Boyd and L. Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Carlini and Wagner (2017) N. Carlini and D. Wagner.  Towards evaluating the robustness of neural networks.  In _2017 IEEE symposium on security and privacy_ , pages 39–57. IEEE, 2017.
  * de Oliveira et al. (1999) M. de Oliveira, J. Geromel, and J. Bernussou.  An lmi optimization approach to multiobjective controller design for discrete-time systems.  In _Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No.99CH36304)_ , volume 4, pages 3611–3616 vol.4, 1999.  doi: 10.1109/CDC.1999.827913.
  * Dohmatob (2019) E. Dohmatob.  Generalized no free lunch theorem for adversarial robustness.  In _International Conference on Machine Learning_ , pages 1646–1654. PMLR, 2019.
  * Doyle (1978) J. Doyle.  Guaranteed margins for lqg regulators.  _IEEE Transactions on Automatic Control_ , 23(4):756–757, 1978.  doi: 10.1109/TAC.1978.1101812.
  * Doyle et al. (1989) J. Doyle, K. Zhou, and B. Bodenheimer.  Optimal control with mixed $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ performance objectives.  In _1989 American Control Conference_ , pages 2065–2070, 1989.  doi: 10.23919/ACC.1989.4790529.
  * Fazel et al. (2018) M. Fazel, R. Ge, S. Kakade, and M. Mesbahi.  Global convergence of policy gradient methods for the linear quadratic regulator.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1467–1476. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/fazel18a.html.
  * Glover and Doyle (1988) K. Glover and J. C. Doyle.  State-space formulae for all stabilizing controllers that satisfy an $\mathcal{H}_{\infty}$-norm bound and relations to relations to risk sensitivity.  _Systems & Control Letters_, 11(3):167–172, 1988.  ISSN 0167-6911.  doi: https://doi.org/10.1016/0167-6911(88)90055-2.  URL https://www.sciencedirect.com/science/article/pii/0167691188900552.
  * Goel and Hassibi (2020) G. Goel and B. Hassibi.  Regret-optimal control in dynamic environments.  _arXiv preprint arXiv:2010.10473_ , 2020.
  * Goel and Hassibi (2021) G. Goel and B. Hassibi.  Competitive control.  _arXiv preprint arXiv:2107.13657_ , 2021.
  * Hassani and Javanmard (2022) H. Hassani and A. Javanmard.  The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression.  _arXiv preprint arXiv:2201.05149_ , 2022.
  * Hassibi et al. (1999) B. Hassibi, T. Kailath, and A. H. Sayed.  _Indefinite-quadratic estimation and control: a unified approach to $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ theories_.  SIAM studies in applied and numerical mathematics, 1999.
  * Havens et al. (2022) A. Havens, D. Keivan, P. Seiler, G. Dullerud, and B. Hu.  Revisiting pgd attacks for stability analysis of large-scale nonlinear systems and perception-based control.  _arXiv preprint arXiv:2201.00801_ , 2022.
  * Hazan et al. (2020) E. Hazan, S. Kakade, and K. Singh.  The nonstochastic control problem.  In _Algorithmic Learning Theory_ , pages 408–421. PMLR, 2020.
  * Hong et al. (2021) J. Hong, N. Moehle, and S. Boyd.  Lecture notes in “introduction to matrix methods”, 2021.
  * Javanmard et al. (2020) A. Javanmard, M. Soltanolkotabi, and H. Hassani.  Precise tradeoffs in adversarial training for linear regression.  In _Conference on Learning Theory_ , pages 2034–2078. PMLR, 2020\.
  * Lee et al. (2021) B. D. Lee, T. T. Zhang, H. Hassani, and N. Matni.  Adversarial tradeoffs in linear inverse problems and robust stateestimation.  _arXiv preprint arXiv:2111.08864_ , 2021.
  * Madry et al. (2017) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Mania et al. (2019) H. Mania, S. Tu, and B. Recht.  Certainty equivalence is efficient for linear quadratic control.  _arXiv preprint arXiv:1902.07826_ , 2019.
  * Paganini (1993) F. Paganini.  Set descriptions of white noise and worst case induced norms.  In _Proceedings of 32nd IEEE Conference on Decision and Control_ , pages 3658–3663 vol.4, 1993.  doi: 10.1109/CDC.1993.325900.
  * Rotea and Khargonekar (1991) M. A. Rotea and P. P. Khargonekar.  $\mathcal{H}_{2}$-optimal control with an $\mathcal{H}_{\infty}$-constraint the state feedback case.  _Automatica_ , 27(2):307–316, 1991.  ISSN 0005-1098.  doi: https://doi.org/10.1016/0005-1098(91)90079-H.  URL https://www.sciencedirect.com/science/article/pii/000510989190079H.
  * Scherer (1995) C. Scherer.  Mixed $\mathcal{H}_{2}/\mathcal{H}_{\infty}$ control.  In A. Isidori, editor, _Trends in Control_ , pages 173–216, London, 1995. Springer London.  ISBN 978-1-4471-3061-1.
  * Tsipras et al. (2018) D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry.  Robustness may be at odds with accuracy.  _arXiv preprint arXiv:1805.12152_ , 2018.
  * Yin et al. (2019) D. Yin, R. Kannan, and P. Bartlett.  Rademacher complexity for adversarially robust generalization.  In _International conference on machine learning_ , pages 7085–7094. PMLR, 2019.
  * Zhang et al. (2021) T. T. Zhang, S. Tu, N. M. Boffi, J.-J. E. Slotine, and N. Matni.  Adversarially robust stability certificates can be sample-efficient.  _arXiv preprint arXiv:2112.10690_ , 2021.
  * Zhou et al. (1996) K. Zhou, J. Doyle, and K. Glover.  _Robust and Optimal Control_.  Feher/Prentice Hall Digital and. Prentice Hall, 1996.  ISBN 9780134565675.

##  Appendix A Proofs from Section 2

###  A.1 Proof of Lemma 2.1

Proof: First define the cost to go for a horizon $T$ at step $\tau$.

$V_{\tau,T}(x_{\tau}):=\min_{u_{\tau:T-1}}\mathbb{E}_{w_{\tau:T-1}}\mathopen{}\left[\max_{\begin{subarray}{c}\delta_{\tau:T-1}\\\
causal\end{subarray}}x_{T}^{\top}Qx_{T}+\sum_{t=\tau}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}.$

Note that for any $T$, $V_{T,T}(x)=x^{\top}Qx$. We will show inductively that
$V_{t,T}(x)=x^{\top}P_{t,T}x+q_{t,T}$ for any $t$. To do so, begin with the
inductive hypothesis $V_{t+1,T}(x)=x^{\top}P_{t+1,T}x+q_{t+1}$. Applying this
hypothesis, we have

$\displaystyle V_{\tau,T}(x_{\tau})$
$\displaystyle=x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\mathopen{}\left\\{u_{\tau}^{\top}Ru_{\tau}+\min_{u_{\tau+1:T-1}}\mathbb{E}_{w_{\tau:T-1}}\mathopen{}\left[\max_{\begin{subarray}{c}\delta_{\tau:T-1}\\\
causal\end{subarray}}x_{T}^{\top}Qx_{T}-\delta_{\tau}^{\top}\delta_{\tau}+\sum_{t=\tau+1}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}\right\\}\mathclose{}$
$\displaystyle=x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\bigg{\\{}u_{\tau}^{\top}Ru_{\tau}$
$\displaystyle+\min_{u_{\tau+1:T-1}}\mathbb{E}_{w_{\tau}}\mathopen{}\left[\max_{\delta_{\tau}}-\gamma^{2}\delta_{\tau}^{\top}\delta_{\tau}+\mathbb{E}_{w_{\tau+1:T-1}}\mathopen{}\left[\max_{\begin{subarray}{c}\delta_{\tau+1:T-1}\\\
causal\end{subarray}}x_{T}^{\top}Qx_{T}+\sum_{t=\tau+1}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}\right]\mathclose{}\bigg{\\}}$
$\displaystyle=x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\mathopen{}\left\\{u_{\tau}^{\top}Ru_{\tau}+\min_{u_{\tau+1:T-1}}\mathbb{E}_{w_{\tau}}\mathopen{}\left[\max_{\delta_{\tau}}-\gamma^{2}\delta_{\tau}^{\top}\delta_{\tau}+V_{\tau+1,T}(Ax_{\tau}+Bu_{\tau}+w_{\tau}+\delta_{\tau})\right]\mathclose{}\right\\}\mathclose{}$
$\displaystyle=x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\bigg{\\{}u_{\tau}^{\top}Ru_{\tau}$
$\displaystyle+\mathbb{E}_{w_{\tau}}\mathopen{}\left[\max_{\delta_{\tau}}-\gamma^{2}\delta_{\tau}^{\top}\delta_{\tau}+(Ax_{\tau}+Bu_{\tau}+w_{\tau}+\delta_{\tau})^{\top}P_{\tau+1,T}(Ax_{\tau}+Bu_{\tau}+w_{\tau}+\delta_{\tau})+q_{\tau+1,T}\right]\mathclose{}\bigg{\\}}$

Letting $\phi_{t}:=Ax_{t}+Bu_{t}+w_{t}$, we see that the maximization with
respect to $\delta_{\tau}$ is equivalent to

$\displaystyle\max_{\delta_{\tau}}\delta_{\tau}^{\top}\mathopen{}\left(P_{\tau+1,T}-\gamma^{2}I\right)\mathclose{}\delta_{\tau}^{\top}+2\phi_{\tau}^{\top}P_{\tau+1,T}\delta_{\tau}.$

If $P_{\tau+1,T}\prec\gamma^{2}I$, then there is a unique optimal solution
given by
$\delta_{\tau}=-(P_{\tau+1,T}-\gamma^{2}I)^{-1}P_{\tau+1,T}\phi_{\tau}$.
Substituting this back in, we see that

$\displaystyle V_{\tau,T}(x_{\tau})$
$\displaystyle=q_{\tau+1,T}+x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\bigg{\\{}u_{\tau}^{\top}Ru_{\tau}+\mathbb{E}_{w_{\tau}}\bigg{[}\phi_{\tau}^{\top}(-\gamma^{2}P_{\tau+1,T}(P_{\tau+1,T}-\gamma^{2}I)^{-2}P_{\tau+1,T}$
$\displaystyle\quad\quad+(I-P_{\tau+1,T}(P_{\tau+1,T}-\gamma^{2}I)^{-1})P_{\tau+1,T}(I-(P_{\tau+1,T}-\gamma^{2}I)^{-1}P_{\tau+1,T}))\phi_{\tau}\bigg{]}\bigg{\\}}$
$\displaystyle=q_{\tau+1,T}+x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\bigg{\\{}u_{\tau}^{\top}Ru_{\tau}+\mathbb{E}_{w_{\tau}}\bigg{[}\phi_{\tau}^{\top}(P_{\tau+1,T}+P_{\tau+1,T}(\gamma^{2}I-P_{\tau+1,T})^{-1}P_{\tau+1})\phi_{\tau}\bigg{]}\bigg{\\}}$

Defining
$M_{\tau+1,T}:=P_{\tau+1,T}+P_{\tau+1,T}(\gamma^{2}I-P_{\tau+1,T})^{-1}P_{\tau+1,T}$,
the above expression reduces to

$\displaystyle q_{\tau+1,T}$
$\displaystyle+x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\bigg{\\{}u_{\tau}^{\top}Ru_{\tau}+\mathbb{E}_{w_{\tau}}\bigg{[}\phi_{\tau}^{\top}M_{\tau+1}\phi_{\tau}\bigg{]}\bigg{\\}}$
$\displaystyle=q_{\tau+1,T}+x_{\tau}^{\top}Qx_{\tau}+\min_{u_{\tau}}\bigg{\\{}u_{\tau}^{\top}Ru_{\tau}+(Ax_{t}+Bu_{t})^{\top}M_{\tau+1,T}(Ax_{t}+Bu_{t})\bigg{\\}}+\operatorname{Tr}(M_{\tau+1,T}\Sigma_{w})$

Minimizing with respect to $u_{\tau}$ provides

$u_{\tau}=-(R+B^{\top}M_{\tau+1,T}B)^{-1}B^{\top}M_{\tau+1,T}Ax_{\tau}$

Substituting this back in, we have that

$\displaystyle V_{\tau,T}(x_{\tau})$
$\displaystyle=q_{\tau+1,T}+\operatorname{Tr}(M_{\tau+1,T}\Sigma_{w})+x_{\tau}^{\top}\mathopen{}\left(Q+A^{\top}M_{\tau+1,T}A-A^{\top}M_{\tau+1,T}B(R+B^{\top}M_{\tau+1,T}B)^{-1}B^{\top}M_{\tau+1,T}A\right)\mathclose{}x_{\tau}$
$\displaystyle=:q_{\tau,T}+x_{\tau}^{\top}P_{\tau,T}x_{\tau}$

Thus we see that the cost to go is given as

$\displaystyle V_{\tau,T}(x_{\tau})$
$\displaystyle=q_{\tau,T}+x_{\tau}^{\top}P_{\tau,T}x_{\tau}$

where

$\displaystyle P_{\tau,T}$
$\displaystyle=Q+A^{\top}M_{\tau+1,T}A-A^{\top}M_{\tau+1,T}B(R+B^{\top}M_{\tau+1,T}B)^{-1}B^{\top}M_{\tau+1,T}A$
$\displaystyle M_{\tau,T}$
$\displaystyle=P_{\tau,T}+P_{\tau,T}\mathopen{}\left(\gamma^{2}I-P_{\tau,T}\right)\mathclose{}^{-1}P_{\tau,T}$
$\displaystyle q_{\tau,T}$
$\displaystyle=q_{\tau+1,T+1}+\operatorname{Tr}(M_{\tau+1,T}\Sigma_{w})$
$\displaystyle q_{T,T}$ $\displaystyle=0$ $\displaystyle P_{T,T}$
$\displaystyle=Q$

Taking the limit as $T\to\infty$, and denoting $P_{\tau}:=P_{\tau,\infty}$ we
see that if the iteration

$\displaystyle P_{\tau}$
$\displaystyle=Q+A^{\top}M_{\tau+1}A-A^{\top}M_{\tau+1}B(R+B^{\top}M_{\tau+1}B)^{-1}B^{\top}M_{\tau+1}A$
$\displaystyle M_{\tau}$
$\displaystyle=P_{\tau}+P_{\tau}\mathopen{}\left(\gamma^{2}I-P_{\tau}\right)\mathclose{}^{-1}P_{\tau}$

converges to a fixed point $P$, then the fixed point must satisfy

$\displaystyle P$
$\displaystyle=Q+A^{\top}MA-A^{\top}MB(R+B^{\top}MB)^{-1}B^{\top}MA$
$\displaystyle M$
$\displaystyle=P+P\mathopen{}\left(\gamma^{2}I-P^{-1}\right)\mathclose{}P.$

We see that finding a pair $(P,M)$ that satisfy the above conditions is
equivalent to finding a $P$ such that

$\displaystyle
P=Q+A^{\top}PA-A^{\top}P\begin{bmatrix}B&I\end{bmatrix}\mathopen{}\left(\begin{bmatrix}B&I\end{bmatrix}^{\top}P\begin{bmatrix}B&I\end{bmatrix}+\begin{bmatrix}R&\\\
&-\gamma^{2}I\end{bmatrix}\right)\mathclose{}^{-1}\begin{bmatrix}B&I\end{bmatrix}^{\top}PA$
(18)

To see that this is the case, note that

$\displaystyle
P+P^{\top}\begin{bmatrix}B&I\end{bmatrix}\begin{bmatrix}B^{\top}PB+R&B^{\top}P\\\
PB&P-\gamma^{2}I\end{bmatrix}^{-1}\begin{bmatrix}B&I\end{bmatrix}^{\top}P$
$\displaystyle=P+P\begin{bmatrix}B^{\top}\\\
I\end{bmatrix}^{\top}\begin{bmatrix}\Psi^{-1}&\Psi^{-1}B^{\top}P(\gamma^{2}I-P)^{-1}\\\
(\gamma^{2}I-P)^{-1}PB\Psi^{-1}&(P-\gamma^{2}I)^{-1}+(\gamma^{2}I-P)^{-1}PB\Psi^{-1}P(\gamma^{2}I-P)^{-1}\end{bmatrix}\begin{bmatrix}B^{\top}\\\
I\end{bmatrix}P$ $\displaystyle=M+MB(B^{\top}MB^{\top}+R)^{-1}B^{\top}M$

where $\Psi=B^{\top}MB+R$. The first equality above follows from the inversion
formula for a block $2\times 2$ matrix.

By our assumption that there exists a positive semidefinite solution to (8),
the iterations converges to this quantity. This can be seen by verifying the
monotonicty of the sequence $P_{\tau}$, as in Lemma 3.3 of Basar (1991).

We thus have that in the limit, the cost converges to
$\operatorname{Tr}(M\Sigma_{w})$, where $M=P+P(\gamma^{2}I-P)^{-1}P$ and $P$
solves

$\displaystyle
P=Q+A^{\top}PA-A^{\top}P\begin{bmatrix}B&I\end{bmatrix}\mathopen{}\left(\begin{bmatrix}B&I\end{bmatrix}^{\top}P\begin{bmatrix}B&I\end{bmatrix}+\begin{bmatrix}R&\\\
&-\gamma^{2}I\end{bmatrix}\right)\mathclose{}^{-1}\begin{bmatrix}B&I\end{bmatrix}^{\top}PA.$

Thus a steady state adversarially robust LQR controller at level $\gamma$ is
given by

$\displaystyle u_{t}$ $\displaystyle=Kx_{t}$ $\displaystyle K$
$\displaystyle=-(R+B^{\top}MB)^{-1}B^{\top}MA$ $\displaystyle M$
$\displaystyle=P+P(\gamma^{2}I-P)^{-1}P$ $\displaystyle P$ solves (8)

and the optimal adversarial perturbation is given by

$\delta_{t}=(\gamma^{2}I-P)^{-1}P((A+BKx_{t})+w_{t}),$

To verify that the controller is stabilizing, it suffices to note that the
cost is finite. Leveraging the fact that $(Q^{1/2},A)$ is detectable thus
tells us that the state must converge to zero in the absence of noise.

For necessity of the given conditions, first note that if there is no PSD
solution to the Riccati equation, then the value does not converge. If the
condition $P\prec\gamma^{2}I$ is not satisfied, then the adversarial
maximization problem is not strictly concave, and it may supply arbitrarily
large perturbations. $\blacksquare$

##  Appendix B Proof of Theorem 2.1

The following lemma will be useful.

###### Lemma B.1

(Ergodicity)

Let our controller be given as $u_{t}=Kx_{t}$, and define

$P=\textnormal{{DARE}}(A+BK,I,Q,-\gamma^{2}I)$

As long as

$(\gamma^{2}I-P)^{-1}P(A+BK)$

has eigenvalues in the open unit disc,

$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}$
$\displaystyle=\limsup_{T\to\infty}\frac{1}{T}\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}.$

Proof: To see that this is so, recall that the optimal adversarial
perturbation was shown to be given by

$\delta_{t}=-(P-\gamma^{2}I)^{-1}P\mathopen{}\left((A+BK)x_{t}+w_{t}\right)\mathclose{}$

and under this perturbation, the dynamics become

$x_{t+1}=\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}\mathopen{}\left((A+BK)x_{t}+w_{t}\right)\mathclose{}$

Then $\begin{bmatrix}x_{t}\\\ w_{t}\end{bmatrix}$ is an ergodic process. In
this case, we have that

$\displaystyle=$
$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}$
$\displaystyle=$
$\displaystyle\limsup_{T\to\infty}\frac{1}{T}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}(Q+K^{\top}RK)x_{t}$
$\displaystyle\quad-\gamma^{2}((A+BK)x_{t}.+w_{t})^{\top}\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}^{\top}\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}(A+BK)x_{t}+w_{t})$ $\displaystyle=$
$\displaystyle\limsup_{t\to\infty}\mathbb{E}\bigg{[}x_{t}(Q+K^{\top}RK)x_{t}$
$\displaystyle\quad-\gamma^{2}((A+BK)x_{t}.+w_{t})^{\top}\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}^{\top}\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}(A+BK)x_{t}+w_{t})\bigg{]}$ $\displaystyle=$
$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\bigg{[}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}(Q+K^{\top}RK)x_{t}$
$\displaystyle\quad-\gamma^{2}((A+BK)x_{t}.+w_{t})^{\top}\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}^{\top}\mathopen{}\left[I-(P-\gamma
I)^{-1}P\right]\mathclose{}(A+BK)x_{t}+w_{t})\bigg{]}$ $\displaystyle=$
$\displaystyle\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\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}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}$

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}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}=\min_{\gamma}\gamma^{2}\varepsilon
T+\max_{\mathbf{\delta}\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}.$

Then (4) is equivalent to

$\displaystyle\operatorname*{minimize}_{u}\limsup_{T}\frac{1}{T}\mathbb{E}\mathopen{}\left[\min_{\gamma}\gamma^{2}\varepsilon
T+\max_{\mathbf{\delta}\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\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 the assumption that $(A,B)$ is stabilizable, and $(Q^{1/2},A)$ is
detectable, we have that

$\displaystyle\infty$ $\displaystyle>\min_{\gamma}\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}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}$
$\displaystyle=\min_{\gamma}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\min_{u_{0},\dots,u_{T-1}}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}.$

Now, for each $\gamma$ let $K_{\gamma}$ be the feedback controller defined in
Lemma 2.1, and let $u_{t}=K_{\gamma}x_{t}$. Then

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

Where the first equality is permitted by the fact that first line is not
random. The second line follow from ergodicity (Lemma B.1). 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}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}$
$\displaystyle=\mathbb{E}\mathopen{}\left[\min_{\gamma}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}\right]\mathclose{}$
$\displaystyle=\mathbb{E}\mathopen{}\left[\min_{\gamma}\gamma^{2}\varepsilon
T+\liminf_{T\to\infty}\frac{1}{T}\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}$
$\displaystyle\leq\liminf_{T\to\infty}\frac{1}{T}\mathbb{E}\mathopen{}\left[\min_{\gamma}\gamma^{2}\varepsilon
T+\max_{\delta\mbox{
causal}}x_{T}^{\top}Qx_{T}+\sum_{t=0}^{T-1}x_{t}Qx_{t}+u_{t}^{\top}Ru_{t}-\gamma^{2}\delta_{t}^{\top}\delta_{t}\right]\mathclose{}.$

Combining these results, we see that

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

Therefore, we see that the optimal solution is given by Lemma 2.1 for some
properly chosen $\gamma$. If $\gamma$ becomes smaller than $\gamma_{\infty}$,
the problem will be unbounded. 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 (7) will equal $\varepsilon$. Then
bisecting such that the adversarial power of the solution to Lemma 2.1
provides the proper level $\gamma$.

$\blacksquare$

##  Appendix C 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+K_{\gamma_{1}}^{\top}RK_{\gamma_{1}}\right)\mathclose{}x_{t}-\gamma_{1}^{2}\delta_{t}^{\top}\delta_{t}\right)\mathclose{}.$
(19)

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}$.

###  C.1 Proof of Lemma 3.1

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

###### Lemma C.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 C.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+BK_{2})x,$

and thus

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

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

$\displaystyle\frac{\left\|B^{\top}(M-P)(A+BK_{2})x\right\|}{\left\|R+B^{\top}MB\right\|}\leq\left\|(K_{1}-K_{2})x\right\|\leq\frac{\left\|B^{\top}(M-P)(A+BK_{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+BK_{2})\right\|}{\left\|R+B^{\top}MB\right\|}\leq\left\|K_{1}-K_{2}\right\|\leq\frac{\left\|B^{\top}(M-P)(A+BK_{2})\right\|}{\sigma_{\min}(R+B^{\top}PB)}.$

$\blacksquare$

###  C.2 Proofs for Section 3.1

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

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

where we recall $W_{\infty}(A,B)$ is the controllability gramian, and we are
guaranteed from Lemma 2.1 that $\rho(A+BK_{\gamma})<1$, since
$\gamma\geq\gamma_{\infty}$. We note that there exists a uniform constant
upper bound on $\left\|W_{\infty}(A+BK_{\gamma},I)\right\|$ independent of
$\gamma$, since $W_{\infty}(A+BK_{\gamma_{\infty}},I)$ and
$W_{\infty}(A+BK_{\star},I)$ are both well-defined. From the intuition that
$W_{\infty}(A+BK_{\gamma},I)$ represents the “disturbability” of the closed-
loop system $A+BK_{\gamma}$, i.e. the controllability of $A+BK_{\gamma}$
treating disturbances as inputs, one may conjecture some monotone behavior of
$\left\|W_{\infty}(A+BK_{\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+BK_{\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(K_{\gamma})\right\|$ as is.

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

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

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 C.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 (8) 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 (7) 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+K_{\gamma_{1}}^{\top}RK_{\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+K_{\gamma_{1}}^{\top}RK_{\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+K_{\gamma_{2}}^{\top}RK_{\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+K_{\gamma_{2}}^{\top}RK_{\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 C.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}}.$
(22)

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$
(23)

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 C.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 (23), 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 C.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 C.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}}\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}^{4}}{\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\|.$
(24)

The proof of Proposition C.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 (20) and (22), and Proposition C.1 together
yields the final upper bound on
$\operatorname{NC}(K_{\gamma})-\operatorname{NC}(K)$.

###  C.3 Proof of Theorem 3.2

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

###### Lemma C.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\|K_{\gamma}-K_{\star}\right\|^{2}\left\|R+B^{\top}M_{\gamma}B\right\|W_{\infty}(\tilde{A}+\tilde{B}K_{\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+BK_{\star},I)\right)\mathclose{}$

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 $K_{\star}$
in the noiseless adversarial setting at level $\gamma$ from initial state $x$,
while $P_{\gamma}$ is the cost of applying controller $K_{\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 $K_{\star}$ and $K_{\gamma}$ are deployed as
$\tilde{N}_{\gamma}$ and $N_{\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}K_{\star}\\\
\tilde{N}_{\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}K_{\gamma}\\\
N_{\gamma}\end{bmatrix},$

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}K_{\star}-K_{\gamma}\\\
\tilde{N}_{\gamma}-N_{\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}K_{\star}-K_{\gamma}\\\
\tilde{N}_{\gamma}-N_{\gamma}\end{bmatrix}x_{t}^{\prime}$

where $x_{0}^{\prime}=x$, and
$x_{t+1}^{\prime}=(A+BK_{\star}+\tilde{N}_{\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)^{-1}P_{\gamma}B&B^{\top}P_{\gamma}\\\
P_{\gamma}B&\gamma^{2}I-P_{\gamma}\end{bmatrix}\succeq 0.$

As $P_{\gamma}\preceq\gamma^{2}I$, 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}(K_{\star}-K_{\gamma})^{\top}\mathopen{}\left(R+B^{\top}M_{\gamma}B\right)\mathclose{}(K_{\star}-K_{\gamma})x_{t}^{\prime}$

or, by the fact thtat
$x_{t+1}^{\prime}=A+BK_{\star}+\tilde{N}_{\gamma}x_{t}^{\prime}=\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BK_{\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+BK_{\star})\right)\mathclose{}^{t}\right)\mathclose{}^{\top}(K_{\star}-K_{\gamma})^{\top}$
$\displaystyle\quad\quad\quad\mathopen{}\left(R+B^{\top}M_{\gamma}B\right)\mathclose{}(K_{\star}-K_{\gamma})\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BK_{\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+E)(A+BK_{\star}),Q+K_{\star}^{\top}RK_{\star}-\gamma^{2}(A+BK_{\star})^{\top}E^{\top}E(A+BK_{\star})\right)\mathclose{}$
$\displaystyle P_{\star}$
$\displaystyle=\textnormal{{dlyap}}\mathopen{}\left(A+BK_{\star},Q+K_{\star}^{\top}RK_{\star}\right)\mathclose{}$
$\displaystyle E$
$\displaystyle=(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}$

Then

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

However, we have that

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

and

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

Then

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

We can expand the Lyapunov solution as an infinite sum:

$\tilde{P}_{\gamma}-P_{\star}=\sum_{t=1}^{\infty}\mathopen{}\left((A+BK_{\star})^{t}\right)\mathclose{}^{\top}\tilde{P}_{\gamma}(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}P_{\gamma}(A+BK_{\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+BK_{\star})^{t}\right)\mathclose{}^{\top}(A+BK_{\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 C.6

As long as $\gamma$ satisfies

$\displaystyle\gamma^{2}$
$\displaystyle\geq\sigma_{\min}(P_{\star})+\sigma_{\min}(P_{\star})^{2}\sigma_{\min}(A+BK_{\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+BK_{\star}),I\right)\mathclose{}\right\|\left\|B^{\top}W_{\infty}(A+BK_{\star},I)\right\|,$

we have the following bound

$\displaystyle\left\|K_{\gamma}-K_{\star}\right\|\geq\frac{\sigma_{\min}(P_{\star})^{2}\left\|B^{\top}W_{\infty}(A+BK_{\star},I)\right\|\sigma_{\min}(A+BK_{\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 (17) and applying Lemma C.5, we find

$\displaystyle\left\|K_{\gamma}-K_{\star}\right\|$
$\displaystyle\geq\frac{\sigma_{\min}(A+BK_{\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+BK_{\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+BK_{\star}),I\right)\mathclose{}\right\|\left\|K_{\gamma}-K_{\star}\right\|^{2}\left\|R+B^{\top}M_{\gamma}B\right\|\bigg{)}$

In particular, by defining

$\displaystyle a$
$\displaystyle=\sigma_{\min}(A+BK_{\star})\left\|B^{\top}W_{\infty}\mathopen{}\left(\mathopen{}\left(I+(\gamma^{2}I-\tilde{P}_{\gamma})^{-1}\tilde{P}_{\gamma}\right)\mathclose{}(A+BK_{\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+BK_{\star},I)\right\|}{\left\|R+B^{\top}M_{\gamma}B\right\|}\sigma_{\min}(A+BK_{\star}),$

the above bound can be written

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

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

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

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

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