$\displaystyle=\prod_{i=1}^{\min\mathopen{}\left\\{n,d\right\\}\mathclose{}}\mathbb{E}\mathopen{}\left[\exp\mathopen{}\left(\lambda\sigma_{i}^{2}g_{i}^{2}\right)\mathclose{}\right]\mathclose{}$
$\displaystyle\leq\prod_{i=1}^{\min\mathopen{}\left\\{n,d\right\\}\mathclose{}}\exp\mathopen{}\left(3\lambda\sigma_{i}^{2}\right)\mathclose{},\quad\lambda\leq\frac{1}{3\sigma_{i}^{2}}\;\forall
i$
$\displaystyle=\exp\mathopen{}\left(3\lambda\sum_{i}\sigma_{i}^{2}\right)\mathclose{},\quad\lambda\leq\frac{1}{3\sigma_{i}^{2}}\;\forall
i$
$\displaystyle=\exp\mathopen{}\left(3\lambda\left\|R\right\|_{F}^{2}\right)\mathclose{},\quad\lambda\leq\frac{1}{3\left\|R\right\|^{2}},$

which completes the proof.

Now, leveraging Lemma C.2: for $\lambda>0$, we write

$\displaystyle\exp\mathopen{}\left(\lambda\mathbb{E}\mathopen{}\left[\max_{t=0,\dots,T-1}z_{t}^{\top}R^{\top}Rz_{t}\right]\mathclose{}\right)\mathclose{}$
$\displaystyle\leq\mathbb{E}\mathopen{}\left[\exp\mathopen{}\left(\lambda\max_{t}z_{t}^{\top}R^{\top}Rz_{t}\right)\mathclose{}\right]\mathclose{}$
Jensen’s
$\displaystyle=\mathbb{E}\mathopen{}\left[\max_{t}\exp\mathopen{}\left(\lambda
z_{t}^{\top}R^{\top}Rz_{t}\right)\mathclose{}\right]\mathclose{}$ monotonicity
$\displaystyle\leq\sum_{t=0}^{T-1}\mathbb{E}\mathopen{}\left[\exp\mathopen{}\left(\lambda
z_{t}^{\top}R^{\top}Rz_{t}\right)\mathclose{}\right]\mathclose{}$

We note that in the last line, we are taking the expectation of each $z_{t}$
over its population distribution, such that $z_{t}\sim\mathcal{N}(0,I)$. Thus,

$\displaystyle\exp\mathopen{}\left(\lambda\mathbb{E}\mathopen{}\left[\max_{t=0,\dots,T-1}z_{t}^{\top}R^{\top}Rz_{t}\right]\mathclose{}\right)\mathclose{}$
$\displaystyle\leq\sum_{t=0}^{T-1}\exp\mathopen{}\left(3\lambda\left\|R\right\|_{F}^{2}\right)\mathclose{}=T\exp\mathopen{}\left(3\lambda\left\|R\right\|_{F}^{2}\right)\mathclose{},\quad\lambda\leq\frac{1}{3\left\|R\right\|^{2}}.$

Taking the logarithm of both sides, re-arranging, and taking the infimum over
$\lambda$, we have

$\displaystyle\mathbb{E}\mathopen{}\left[\max_{t=0,\dots,T-1}z_{t}^{\top}R^{\top}Rz_{t}\right]\mathclose{}$
$\displaystyle\leq\inf_{\lambda\in\Big{[}0,\frac{1}{3\left\|R\right\|^{2}}\Big{]}}\frac{\log(T)}{\lambda}+3\left\|R\right\|_{F}^{2}$
$\displaystyle=3\left\|R\right\|^{2}\log(T)+3\left\|R\right\|_{F}^{2}$
$\displaystyle\leq
3\mathopen{}\left(1+\log(T)\right)\mathclose{}\left\|R\right\|_{F}^{2}.$

Substituting back
$R=(K-K^{(H+1)})\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}^{1/2}$,
and observing

$\displaystyle\left\|R\right\|_{F}^{2}=\left\|(K-K^{(H+1)})\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}^{1/2}\right\|_{F}^{2}$
$\displaystyle=\operatorname{Tr}\mathopen{}\left((K-K^{(H+1)})\Sigma_{x}^{(H+1)}(K-K^{(H+1)})^{\top}\right)\mathclose{}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\mathopen{}\left[\left\|Kx_{\star}[t]-K^{(H+1)}x_{\star}[t]\right\|^{2}\right]\mathclose{},$

the proof of Proposition C.2 is complete.

With the maximal inequality in hand, and defining
$A_{\mathsf{cl}}:=A+BK^{(H+1)}$, we may now bound:

$\displaystyle\mathbb{E}_{\hat{}\mathcal{P}_{1:T}}\mathopen{}\left[h(\hat{\bm{x}}_{1:T})\right]\mathclose{}-\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[h(\bm{x}^{\star}_{1:T})\right]\mathclose{}$
$\displaystyle\leq\;$ $\displaystyle
L\mathbb{E}_{\mathopen{}\left(\bm{x}^{\star}_{1:T},\hat{\bm{x}}_{1:T}\right)\mathclose{}\sim\overline{\gamma}}\mathopen{}\left[\max_{1\leq
t\leq T}\left\|x_{\star}[t]-\hat{x}[t]\right\|\right]\mathclose{}$
$\displaystyle\leq\;$ $\displaystyle
L\sqrt{\mathbb{E}_{\mathopen{}\left(\bm{x}^{\star}_{1:T},\hat{\bm{x}}_{1:T}\right)\mathclose{}\sim\overline{\gamma}}\mathopen{}\left[\max_{1\leq
t\leq T}\left\|x_{\star}[t]-\hat{x}[t]\right\|^{2}\right]\mathclose{}}$
$\displaystyle\leq\;$ $\displaystyle
L\sqrt{\mathbb{E}_{\mathcal{P}^{\star}_{0:T-1}}\mathopen{}\left[\max_{0\leq
t\leq
T-1}4\mathcal{J}(A_{\mathsf{cl}})^{2}\left\|B\right\|^{2}\left\|\mathopen{}\left(\hat{K}-K^{(H+1)}\right)\mathclose{}x_{\star}[t]\right\|^{2}\right]\mathclose{}}$
$\displaystyle\leq\;$ $\displaystyle
2\sqrt{3}L\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|\sqrt{1+\log(T)}\sqrt{\mathbb{E}_{\mathcal{P}^{\star}_{0:T-1}}\mathopen{}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\|(K-K^{(H+1)})x_{\star}[t]\right\|^{2}\right]\mathclose{}}$
$\displaystyle\leq\;$ $\displaystyle
2\sqrt{3}L\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|\sqrt{1+\log(T)}\sqrt{\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})}.$

###  C.1 Tightness of Dependence on Spectral Radius in Theorem 3.2

Consider the following scalar LTI system

$\displaystyle x[t+1]=ax[t]+u[t]+w[t],\quad w[t]\sim\mathcal{N}(0,1),$

where $a>0$ without loss of generality. We are given the expert controller
$u^{\star}[t]=k^{\star}x[t]$ that stabilizes the above system, such that we
have

$0<a+k^{\star}<1.$

Let’s say our learned controller $\hat{k}$ attains an $\varepsilon>0$ error
with respect to $k^{\star}$: $\hat{k}=k^{\star}+\varepsilon$, and
$a+\hat{k}<1$. We recall a couple of facts: the stationary distribution
induced by $k^{\star}$ can be derived by solving the scalar Lyapunov equation

$\displaystyle\sigma^{2}=(a+k^{\star})^{2}\sigma^{2}+1\iff\sigma^{2}=\frac{1}{1-(a+k^{\star})^{2}}.$

Therefore, akin to the setting considered in our paper, we assume the initial
state distribution is the expert stationary distribution. We now study the
tracking between the expert and learned states evolving in the coupled manner
analogous to (26)

$\displaystyle x_{\star}[t+1]$
$\displaystyle=(a+k^{\star})x_{\star}[t]+w[t],\quad
x_{0}\sim\mathcal{N}\mathopen{}\left(0,\frac{1}{1-(a+k^{\star})^{2}}\right)\mathclose{}$
$\displaystyle\hat{x}[t+1]$
$\displaystyle=(a+k^{\star}+\varepsilon)\hat{x}[t]+w[t],\quad
x_{0}\sim\mathcal{N}\mathopen{}\left(0,\frac{1}{1-(a+k^{\star})^{2}}\right)\mathclose{}.$

In particular, we show the following lower bound on the tracking error

###### Proposition C.3

Given the proposed scalar system, the tracking error satisfies the following
lower bound for sufficiently large $T$,

$\displaystyle\mathbb{E}\mathopen{}\left[\max_{1\leq t\leq
T}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}\right]\mathclose{}$
$\displaystyle\gtrsim\;$
$\displaystyle\frac{1}{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}}\underbrace{\frac{1}{T}\mathbb{E}\mathopen{}\left[\sum_{t=0}^{T-1}{\left|(\hat{k}-k^{\star})x_{\star}[t]\right|}^{2}\right]\mathclose{}}_{\text{excess
risk of }\hat{k}\text{ on expert
data}}=:\frac{1}{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}}\mathrm{ER}(\hat{k}).$

We note that instantiating the in-expectation upper bound using the maximal
inequality in Proposition C.2 yields

$\displaystyle\mathbb{E}\mathopen{}\left[\max_{1\leq t\leq
T}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}\right]\mathclose{}$
$\displaystyle\leq
12\mathcal{J}(a+k^{\star})^{2}\left\|B\right\|^{2}(1+\log(T))\mathrm{ER}(\hat{k})$
$\displaystyle=\frac{12}{(1-(a+k^{\star}))^{2}}(1+\log(T))\mathrm{ER}(\hat{k}).$

Therefore, Proposition C.3 states that up to a log-factor in horizon length
$T$, the polynomial dependence on the expert system’s spectral radius
$a+k^{\star}$ matches that in the upper bound.

Proof  We can immediately compute the excess risk in closed form

$\displaystyle\mathrm{ER}(\hat{k}):=\frac{1}{T}\mathbb{E}\mathopen{}\left[\sum_{t=0}^{T-1}{\left|(\hat{k}-k^{\star})x_{\star}[t]\right|}^{2}\right]\mathclose{}$
$\displaystyle=(\hat{k}-k^{\star})^{2}\mathbb{E}\mathopen{}\left[\frac{1}{T}\sum_{t=0}^{T-1}{x_{\star}[t]}^{2}\right]\mathclose{}$
$\displaystyle=\frac{\varepsilon^{2}}{1-(a+k^{\star})^{2}}\quad\text{by
stationarity}.$

Therefore, in addition to the spectral radius showing up in the excess risk,
we need to show the tracking error accrues another factor of the spectral
radius on top of that. We observe

$\displaystyle\max_{1\leq t\leq T}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}$
$\displaystyle\geq{\left|x_{\star}[{T}]-\hat{x}[{T}]\right|}^{2}$
$\displaystyle\implies\mathbb{E}\mathopen{}\left[\max_{1\leq t\leq
T}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}\right]\mathclose{}$
$\displaystyle\geq\max_{t\leq
T}\mathbb{E}\mathopen{}\left[{\left|x_{\star}[T]-\hat{x}[T]\right|}^{2}\right]\mathclose{}$
$\displaystyle=\max_{t\leq
T}\mathbb{E}\mathopen{}\left[{x_{\star}[{T}]}^{2}\right]\mathclose{}+\mathbb{E}\mathopen{}\left[\hat{x}[{T}]^{2}\right]\mathclose{}-2\mathbb{E}\mathopen{}\left[x_{\star}[{T}]\hat{x}[{T}]\right]\mathclose{}$
$\displaystyle=\max_{t\leq
T}\frac{1}{1-(a+k^{\star})^{2}}+\frac{(a+\hat{k})^{2T}}{1-(a+k^{\star})^{2}}+\sum_{t=0}^{T-1}(a+\hat{k})^{2(T-t)}$
$\displaystyle\qquad-\frac{2(a+k^{\star})^{T}(a+\hat{k})^{T}}{1-(a+k^{\star})^{2}}-2\sum_{t=0}^{T-1}(a+k^{\star})^{T-t}(a+\hat{k})^{T-t},$

where the summations come from the fact that the initial condition is drawn
from the stationary distribution induced by the expert, not the learned
controller, in conjunction with the formula
$x[t]=a^{t}x_{0}+\sum_{k=0}^{t-1}a^{t-1-k}w[t]$ for system
$x[t+1]=ax[t]+w[t]$. Since in the limit we have

$\displaystyle\lim_{T\to\infty}\mathbb{E}\mathopen{}\left[{\left|x_{\star}[{T}]-\hat{x}[{T}]\right|}^{2}\right]\mathclose{}$
$\displaystyle=\frac{1}{1-(a+k^{\star})^{2}}+\frac{1}{1-(a+\hat{k})^{2}}-\frac{2}{1-(a+k^{\star})(a+\hat{k})},$

we simply take $T$ large enough such that

$\displaystyle\mathbb{E}\mathopen{}\left[{\left|x_{\star}[{T}]-\hat{x}[{T}]\right|}^{2}\right]\mathclose{}$
$\displaystyle\geq\frac{1}{2}\mathopen{}\left(\frac{1}{1-(a+k^{\star})^{2}}+\frac{1}{1-(a+\hat{k})^{2}}-\frac{2}{1-(a+k^{\star})(a+\hat{k})}\right)\mathclose{}.$

We now bound

$\displaystyle\frac{1}{1-(a+k^{\star})^{2}}+\frac{1}{1-(a+\hat{k})^{2}}-\frac{2}{1-(a+k^{\star})(a+\hat{k})}$
$\displaystyle=\;$
$\displaystyle\sum_{t=0}^{\infty}(a+k^{\star})^{2t}+(a+\hat{k})^{2t}-2(a+k^{\star})^{t}(a+\hat{k})^{t}$
$\displaystyle=\;$
$\displaystyle\sum_{t=0}^{\infty}((a+\hat{k})^{t}-(a+k^{\star})^{t})^{2}$
$\displaystyle=\;$
$\displaystyle\sum_{t=0}^{\infty}\mathopen{}\left((\hat{k}-k^{\star})\mathopen{}\left((a+k^{\star})^{t-1}+(a+k^{\star})^{t-2}(a+\hat{k})+\cdots+(a+k^{\star})(a+\hat{k})^{t-2}+(a+\hat{k})^{t-1}\right)\mathclose{}\right)\mathclose{}^{2}$
$\displaystyle\geq\;$
$\displaystyle\varepsilon^{2}\sum_{k=0}^{\infty}\mathopen{}\left(t(a+k^{\star})^{t-1}\right)\mathclose{}^{2}$
$\displaystyle=\;$
$\displaystyle\varepsilon^{2}\frac{1+(a+k^{\star})^{2}}{(1-(a+k^{\star})^{2})^{3}},$

where we used the algebraic identity

$u^{t}-v^{t}=(u-v)(u^{t-1}+u^{t-2}v+\cdots+uv^{t-2}+v^{t-1}),$

and the inequality (assuming $u\leq v$)

$u^{t-1}+u^{t-2}v+\cdots+uv^{t-2}+v^{t-1}\geq nu^{t-1},$

setting $u:=a+k^{\star}$ and $v:=a+\hat{k}=a+k^{\star}+\varepsilon$. Now
recalling that the empirical risk by stationarity is given by

$\mathrm{ER}(\hat{k})=\frac{\varepsilon^{2}}{1-(a+k^{\star})^{2}},$

we can immediately infer

$\displaystyle\mathbb{E}\mathopen{}\left[{\left|x_{\star}[{T}]-\hat{x}[{T}]\right|}^{2}\right]\mathclose{}$
$\displaystyle\geq
0.5\varepsilon^{2}\frac{1+(a+k^{\star})^{2}}{(1-(a+k^{\star})^{2})^{3}}$
$\displaystyle=0.5\mathrm{ER}(\hat{k})\frac{1+(a+k^{\star})^{2}}{(1-(a+k^{\star})^{2})^{2}}$
$\displaystyle>\frac{0.5}{(1-(a+k^{\star})^{2})^{2}}\mathrm{ER}(\hat{k}).$

In short, we have established a lower bound on the expected imitation gap:

$\displaystyle\mathbb{E}\mathopen{}\left[\max_{0\leq t\leq
T-1}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}\right]\mathclose{}$
$\displaystyle\geq\max_{t\leq
T-1}\mathbb{E}\mathopen{}\left[{\left|x_{\star}[{T-1}]-\hat{x}[{T-1}]\right|}^{2}\right]\mathclose{}$
$\displaystyle\gtrsim\frac{1}{(1-(a+k^{\star})^{2})^{2}}\mathrm{ER}(\hat{k}).$

We now claim that $\frac{1}{(1-(a+k^{\star})^{2})^{2}}$ matches the dependence
on the spectral radius in the upper bound. Combining Proposition C.1 and
Proposition C.2, we have the following upper bound on the expected tracking
error:

$\displaystyle\mathbb{E}\mathopen{}\left[\max_{0\leq t\leq
T-1}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}\right]\mathclose{}$
$\displaystyle\leq\frac{12}{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}}(1+\log(T))\mathrm{ER}(\hat{k}).$

Comparing $\frac{1}{(1-(a+k^{\star})^{2})^{2}}$ to
$\frac{1}{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}}$, we get

$\displaystyle\frac{\frac{1}{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}}}{\frac{1}{(1-(a+k^{\star})^{2})^{2}}}$
$\displaystyle=\frac{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}\mathopen{}\left(1+(a+k^{\star})\right)\mathclose{}^{2}}{\mathopen{}\left(1-(a+k^{\star})\right)\mathclose{}^{2}}=\mathopen{}\left(1+(a+k^{\star})\right)\mathclose{}^{2}\geq
1,$

which essentially states the dependence on the spectral radius in the lower
and upper bounds match up to a constant factor:

$\displaystyle\frac{0.5}{(1-(a+k^{\star}))^{2}}\mathrm{ER}(\hat{k})\leq\mathbb{E}\mathopen{}\left[\max_{0\leq
t\leq
T-1}{\left|x_{\star}[t]-\hat{x}[t]\right|}^{2}\right]\mathclose{}\leq\frac{12}{(1-(a+k^{\star}))^{2}}(1+\log(T))\mathrm{ER}(\hat{k}),$

which completes the result.

##  Appendix D In-Expectation Bounds for LQR via the Tracking Error

As previewed in Remark 3.2, the generalization bounds on the excess risk and
tracking error are strong enough to directly imply in-expectation bounds on
the LQR costs of the closed-loop expert and learned systems. However, this
does not trivially follow an application of Lipschitzness with respect to the
trajectory-wise metric
$d(\bm{x}_{1:T},\bm{y}_{1:T})=\max_{t}\left\|x[t]-y[t]\right\|$, due to the
input cost $u^{\top}Ru$ depending on different controllers $\hat{K}$ and
$K^{(H+1)}$, which cannot be captured purely as a metric on trajectory states.
Therefore, some massaging is required to get the analogous bounds.

Let us define the (root) LQR cost defined on
$\mathopen{}\left(\bm{x}_{1:T},K\right)\mathclose{}$

$\displaystyle\begin{split}h\mathopen{}\left(\mathopen{}\left(\bm{x}_{1:T},K\right)\mathclose{}\right)\mathclose{}&:=\max_{1\leq
t\leq
T}\sqrt{x[t]^{\top}\mathopen{}\left(Q+K^{\top}RK\right)\mathclose{}x[t]}\\\
&=\max_{1\leq t\leq T}\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K\end{bmatrix}x[t]\right\|\end{split}$ (32)

Our goal is to show that $h(\cdot)$ is somewhat Lipschitz with respect to the
trajectory (pseudo)metric

$\displaystyle
d\mathopen{}\left(\mathopen{}\left(\bm{x}_{1:T},K_{1}\right)\mathclose{},\mathopen{}\left(\bm{y}_{1:T},K_{2}\right)\mathclose{}\right)\mathclose{}$
$\displaystyle:=\max_{1\leq t\leq T}\left\|x[t]-y[t]\right\|,$ (33)

such that using the tools we developed for bounding the tracking error imply
an in-expectation bound for LQR. This culminates in the following result.

###### Proposition D.1

Let $(\hat{\Phi},\hat{F}^{(H+1)})$ denote the learned representation and
target task weights, and $\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})$ denote the
corresponding excess risk. Define $A_{\mathsf{cl}}:=A+BK^{(H+1)}$. As in
Theorem 3.2, assume that the excess risk satisfies:

$\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})\lesssim\frac{\lambda_{\min}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}{\mathcal{J}\mathopen{}\left(A_{\mathsf{cl}}\right)\mathclose{}^{2}\left\|B\right\|^{2}}.$

Let the cost $h(\cdot)$ be the LQR cost (32). The following in-expectation
bound on the gap between the closed-loop LQR costs induced by the expert
$K^{(H+1)}$ and learned controller $\hat{K}$ holds:

$\displaystyle\begin{split}&{\left|\mathbb{E}_{\hat{}\mathcal{P}_{1:T}}\mathopen{}\left[h\mathopen{}\left(\mathopen{}\left(\bm{\hat{}}x_{1:T},\hat{K}\right)\mathclose{}\right)\mathclose{}\right]\mathclose{}-\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[h\mathopen{}\left(\mathopen{}\left(\bm{x}^{\star}_{1:T},K^{(H+1)}\right)\mathclose{}\right)\mathclose{}\right]\mathclose{}\right|}\\\
\lesssim\;&\mathcal{C}^{(H+1)}\sigma_{z}\sqrt{\log(T)}\sqrt{\frac{kn_{x}\log\mathopen{}\left(N_{1}T\frac{\bar{\lambda}}{\underline{\lambda}}\right)\mathclose{}}{cN_{1}TH}+\frac{kn_{u}+\log(\frac{1}{\delta^{\prime}})}{N_{2}T}},\end{split}$

where

$\mathcal{C}^{(H+1)}:=\lambda_{\max}(Q)^{1/2}\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|+\lambda_{\max}(R)^{1/2}\mathopen{}\left(\left\|K^{(H+1)}\right\|+\sqrt{\frac{\operatorname{Tr}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}{\lambda_{\min}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}}\right)\mathclose{},$

is an expert system and LQ cost-dependent constant.

Proof  First, consider the following elementary inequality:

$\displaystyle\left\|M_{1}x_{1}\right\|-\left\|M_{2}x_{2}\right\|$
$\displaystyle=\left\|M_{1}x_{1}\right\|-\left\|M_{1}x_{2}\right\|+\left\|M_{1}x_{2}\right\|-\left\|M_{2}x_{2}\right\|$
$\displaystyle\leq\left\|M_{1}(x_{1}-x_{2})\right\|+\left\|(M_{1}-M_{2})x_{2}\right\|$
$\displaystyle\leq\left\|M_{1}\right\|\left\|x_{1}-x_{2}\right\|+\left\|x_{2}\right\|\left\|M_{1}-M_{2}\right\|$

Applying this to
$h\mathopen{}\left(\mathopen{}\left(\bm{x}_{1:T},K_{1}\right)\mathclose{}\right)\mathclose{}-h\mathopen{}\left(\mathopen{}\left(\bm{y}_{1:T},K_{2}\right)\mathclose{}\right)\mathclose{}$,
for fixed $K_{1}$, $K_{2}$ we get

$\displaystyle\begin{split}&h\mathopen{}\left(\mathopen{}\left(\bm{x}_{1:T},K_{1}\right)\mathclose{}\right)\mathclose{}-h\mathopen{}\left(\mathopen{}\left(\bm{y}_{1:T},K_{2}\right)\mathclose{}\right)\mathclose{}\\\
=\;&\max_{1\leq t\leq T}\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{1}\end{bmatrix}x[t]\right\|-\max_{1\leq t\leq
T}\left\|\begin{bmatrix}Q^{1/2}\\\ R^{1/2}K_{2}\end{bmatrix}y[t]\right\|\\\
\leq\;&\max_{1\leq t\leq T}\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{1}\end{bmatrix}x[t]\right\|-\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{2}\end{bmatrix}y[t]\right\|\\\ \leq\;&\max_{1\leq t\leq
T}\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{1}\end{bmatrix}\right\|\left\|x[t]-y[t]\right\|+\left\|y[t]\right\|\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{1}\end{bmatrix}-\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{2}\end{bmatrix}\right\|\\\ \leq\;&\left\|\begin{bmatrix}Q^{1/2}\\\
R^{1/2}K_{1}\end{bmatrix}\right\|\max_{1\leq t\leq
T}\left\|x[t]-y[t]\right\|+\lambda_{\max}(R)^{1/2}\left\|K_{1}-K_{2}\right\|\max_{1\leq
t\leq T}\left\|y[t]\right\|\end{split}$ (34)

we can take the expectation of the inequality (LABEL:eq:_cost_gap_term_split)
to yield for any coupling of the learned and expert trajectory distributions
$\Gamma(\hat{}\mathcal{P}_{1:T},\mathcal{P}^{\star}_{1:T})$

$\displaystyle\begin{split}&{\left|\mathbb{E}_{\hat{}\mathcal{P}_{1:T}}\mathopen{}\left[h\mathopen{}\left(\mathopen{}\left(\bm{\hat{}}x_{1:T},\hat{K}\right)\mathclose{}\right)\mathclose{}\right]\mathclose{}-\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[h\mathopen{}\left(\mathopen{}\left(\bm{x}^{\star}_{1:T},K^{(H+1)}\right)\mathclose{}\right)\mathclose{}\right]\mathclose{}\right|}\\\
\leq\;&\lambda_{\max}\mathopen{}\left(Q+\hat{K}^{\top}R\hat{K}\right)\mathclose{}^{1/2}\mathbb{E}_{\Gamma(\hat{}\mathcal{P}_{1:T},\mathcal{P}^{\star}_{1:T})}\mathopen{}\left[\max_{t\leq
T}\left\|\hat{x}[t]-x_{\star}[t]\right\|\right]\mathclose{}\\\
\quad\quad&+\lambda_{\max}(R)^{1/2}\left\|\hat{K}-K^{(H+1)}\right\|\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[\max_{1\leq
t\leq T}\left\|x_{\star}[t]\right\|\right]\mathclose{}.\end{split}$ (35)

Setting $\Gamma(\hat{}\mathcal{P}_{1:T},\mathcal{P}^{\star}_{1:T})$ to be the
coupling described in (26) where the learned and expert trajectories are
evaluated on the same realizations of randomness, we may apply the tools
developed in Theorem C.2 to bound the first term. As for the second term, we
may apply a maximal-type inequality akin to Proposition C.2. In particular,
from earlier computations we have

$\displaystyle\mathbb{E}_{\Gamma(\hat{}\mathcal{P}_{1:T},\mathcal{P}^{\star}_{1:T})}\mathopen{}\left[\max_{t\leq
T}\left\|\hat{x}[t]-x_{\star}[t]\right\|\right]\mathclose{}$
$\displaystyle\leq
2\sqrt{3}\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|\sqrt{1+\log(T)}\sqrt{\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})},$
(36)

and adapting Proposition C.2 we get

$\displaystyle\begin{split}\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[\max_{1\leq
t\leq
T}\left\|x_{\star}[t]\right\|\right]\mathclose{}&\leq\sqrt{\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[\max_{1\leq
t\leq T}\left\|x_{\star}[t]\right\|^{2}\right]\mathclose{}}\\\
&\leq\sqrt{3}\sqrt{1+\log(T)}\sqrt{\mathbb{E}\mathopen{}\left[\left\|x_{\star}[0]\right\|^{2}\right]\mathclose{}}\\\
&\leq\sqrt{3}\sqrt{1+\log(T)}\sqrt{\operatorname{Tr}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}.\end{split}$

Lastly, from the definition of the excess risk we have

$\displaystyle\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})$
$\displaystyle=\frac{1}{2}\operatorname{Tr}\mathopen{}\left((\hat{K}-K^{(H+1)})\Sigma_{x}^{(H+1)}(\hat{K}-K^{(H+1)})^{\top}\right)\mathclose{}$
$\displaystyle\implies\left\|\hat{K}-K^{(H+1)}\right\|$
$\displaystyle\leq\lambda_{\min}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}^{-1/2}\sqrt{\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})}.$
(37)

Therefore, plugging expressions (36) and (D) back into the bound (35), we have
essentially written the bound on the expected cost gap to scale with

$\sqrt{\log(T)\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})},$

modulo the system/LQ cost-related parameters. The rest of the proof follows by
instantiating the generalization bound on
$\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})$ from Theorem 3.1, and combining the
problem-related parameters. In particular, the first term of (35) involves the
learned controller:
$\lambda_{\max}\mathopen{}\left(Q+\hat{K}^{\top}R\hat{K}\right)\mathclose{}$.
This can be crudely upper bounded by

$\displaystyle\lambda_{\max}\mathopen{}\left(Q+\hat{K}^{\top}R\hat{K}\right)\mathclose{}^{1/2}$
$\displaystyle\leq\lambda_{\max}(Q)^{1/2}+\lambda_{\max}(R)^{1/2}\left\|\hat{K}\right\|$
$\displaystyle\leq\lambda_{\max}(Q)^{1/2}+\lambda_{\max}(R)^{1/2}\mathopen{}\left(\left\|K^{(H+1)}\right\|+\frac{1}{2\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|}\right)\mathclose{},$

where the last line comes from reverse triangle inequality on the burn-in
requirement (8). A tighter bound can be derived by using (D), but the scaling
of the final bound is the same. Therefore, we have

$\displaystyle\begin{split}&{\left|\mathbb{E}_{\hat{}\mathcal{P}_{1:T}}\mathopen{}\left[h\mathopen{}\left(\mathopen{}\left(\bm{\hat{}}x_{1:T},\hat{K}\right)\mathclose{}\right)\mathclose{}\right]\mathclose{}-\mathbb{E}_{\mathcal{P}^{\star}_{1:T}}\mathopen{}\left[h\mathopen{}\left(\mathopen{}\left(\bm{x}^{\star}_{1:T},K^{(H+1)}\right)\mathclose{}\right)\mathclose{}\right]\mathclose{}\right|}\\\
\lesssim\;&\mathcal{C}^{(H+1)}\sqrt{\log(T)\mathrm{ER}(\hat{\Phi},\hat{F}^{(H+1)})}\\\
\lesssim\;&\mathcal{C}^{(H+1)}\sigma_{z}\sqrt{\log(T)}\sqrt{\frac{kn_{x}\log\mathopen{}\left(N_{1}T\frac{\bar{\lambda}}{\underline{\lambda}}\right)\mathclose{}}{cN_{1}TH}+\frac{kn_{u}+\log(\frac{1}{\delta^{\prime}})}{N_{2}T}},\end{split}$

where

$\displaystyle\mathcal{C}^{(H+1)}$
$\displaystyle=\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|\mathopen{}\left(\lambda_{\max}(Q)^{1/2}+\lambda_{\max}(R)^{1/2}\mathopen{}\left(\left\|K^{(H+1)}\right\|+\frac{1}{2\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|}\right)\mathclose{}\right)\mathclose{}$
$\displaystyle\quad\quad+\lambda_{\max}(R)^{1/2}\sqrt{\frac{\operatorname{Tr}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}{\lambda_{\min}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}}$
$\displaystyle\cong\lambda_{\max}(Q)^{1/2}\mathcal{J}(A_{\mathsf{cl}})\left\|B\right\|+\lambda_{\max}(R)^{1/2}\mathopen{}\left(\left\|K^{(H+1)}\right\|+\sqrt{\frac{\operatorname{Tr}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}{\lambda_{\min}\mathopen{}\left(\Sigma_{x}^{(H+1)}\right)\mathclose{}}}\right)\mathclose{}.$

This completes the proof.