The strategy of pre-training a large model on a diverse dataset, then fine-tuning for a particular application has yielded impressive results in computer vision, natural language processing, and robotic control. This strategy has vast potential in adaptive control, where it is necessary to rapidly adapt to changing conditions with limited data. Toward concretely understanding the benefit of pre-training for adaptive control, we study the adaptive linear quadratic control problem  in the setting where the learner has prior knowledge of a collection of basis matrices for the dynamics. This basis is misspecified in the sense that it cannot perfectly represent the dynamics of the underlying data generating process. We propose an algorithm that uses this prior knowledge, and prove upper bounds on the expected regret after $T$ interactions with the system. In the regime where $T$ is small, the upper bounds are dominated by a term scales with either $\texttt{poly}(\log T)$ or $\sqrt{T}$, depending on the prior knowledge available to the learner.  When $T$ is large, the regret is dominated by a term that grows with $\delta T$, where $\delta$ quantifies the level of misspecification. This linear term arises due to the inability to perfectly estimate the underlying dynamics using the misspecified basis, and is therefore unavoidable unless the basis matrices are also adapted online. However, it only dominates for large $T$, after the sublinear terms arising due to the error in estimating the weights for the basis matrices become negligible. We provide simulations that validate our analysis. Our simulations also show that offline data from a collection of related systems can be used as part of a pre-training stage to estimate a misspecified dynamics basis, which is in turn used by our adaptive controller.

§ INTRODUCTION

Transfer learning, whereby a model is pre-trained on a large dataset, and then finetuned for a specific application, has exhibited great success in computer vision [Dosovitskiy et al., 2020] and natural language processing [Devlin et al., 2018]. Efforts to apply these methods to control have shown exciting preliminary results, particularly in robotics [Dasari et al., 2019].
The principle underpinning the success of transfer learning is to use diverse datasets to extract compressed, broadly useful features, which can be used in conjunction with comparatively simple models for downstream objectives. These simple models can be finetuned with relatively little data from the downstream task. However, errors in the pre-training stage may cause this two-step strategy to underperform learning from scratch when ample task-specific data is available. Such a tradeoff can be acceptable in settings such as adaptive control, where the learner must rapidly adapt to changes with limited data.

Driven by the potential of pre-training in adaptive control, we study the adaptive linear quadratic regulator (LQR) in a setting where imperfect prior information about the system is available. The adaptive linear LQR problem consists of a learner interacting with an unknown linear system

\begin{align}
\label{eq: dynamics}
x_{t+1} = A^\star x_t + B^\star u_t + w_t,
\end{align}

with state $x_t$, input $u_t$, and noise $w_t$  assuming values in $\R^{\dx}$, $\R^{\du}$, and $\R^{\dx}$, respectively. The learner is evaluated by its ability to minimize its regret, which compares the cost incurred by playing the learner for $T$ time steps with the cost attained by the optimal LQR controller. Prior work has studied the adaptive LQR problem in the settings where $A^\star$, $B^\star$, or both $A^\star$ and $B^\star$ are fully unknown to the learner and with either stochastic or bounded adversarial noise processes [Abbasi-Yadkori and Szepesvári, 2011, Hazan et al., 2020, Cassel et al., 2020]. In this work, we analyze a setting where the learner has a set of basis matrices for the system dynamics; however, $\bmat{A^\star & B^\star}$ is not in the subspace spanned by this basis, leading to misspecification.

§.§ Related Work

Adaptive Control Originating from autopilot development for high-performance aircraft in the 1950s [Gregory, 1959], adaptive control addressed the need for controllers to adapt to varying altitude, speed, and flight configuration [Stein, 1980]. Interest in adaptive control theory grew over the subsequent decades, notably advanced by the landmark paper by [Åström and Wittenmark, 1973], who studied self tuning regulators.
The history of adaptive control is documented in numerous texts [Åström and Wittenmark, 2013, Ioannou and Sun, 1996, Narendra and Annaswamy, 2012].

Nonasymptotic Adaptive LQR The non-asymptotic study of the adaptive LQR problem

was pioneered by [Abbasi-Yadkori and Szepesvári, 2011]. Subsequent works [Dean et al., 2018, Cohen et al., 2019, Mania et al., 2019] developed computationally efficient algorithms with upper bounds on the regret scaling with $\sqrt{T}$. [Simchowitz and Foster, 2020] provide lower bounds which show that the rate $\sqrt{\du^2\dx T}$ is optimal when the system is entirely unknown.
The dependence of the lower bounds on system theoretic constants is refined by [Ziemann and Sandberg, 2022], enabling [Tsiamis et al., 2022] to show the regret may depend exponentially on the $\dx$ for specific classes of systems. If either $A^\star$ or $B^\star$ are known, then the regret bounds may be improved to $\texttt{poly}(\log T)$ [Cassel et al., 2020, Jedra and Proutiere, 2022]. Alternative formulations of the adaptive LQR problem consider bounded non-stochastic disturbances [Hazan et al., 2020, Simchowitz et al., 2020] and minimax settings [Rantzer, 2021, Cederberg et al., 2022, Renganathan et al., 2023].
In contrast to existing work studying the adaptive LQR problem from a nonasymptotic perspective, we consider bounded misspecification between a representation estimate for the dynamics and the data generating process.

Multi-task Representation Learning The source of mispecification we consider is inspired by theoretical work studying multi-task representation learning in the linear regression setting [Du et al., 2020, Tripuraneni et al., 2020]. These papers have been followed by a collection of work studying the use of multi-task representation learning in the presence of data correlated across time, which arises  in system identification [Modi et al., 2021, Zhang et al., 2023] and imitation learning [Zhang et al., 2023]. All of these theoretical works show that by pre-training a shared representation on a set of source tasks, the sample complexity of learning the target task may be reduced.

§.§ Contributions

We introduce a notion of misspecification between an estimate for the basis of the dynamics and the data generating process. We then propose an adaptive control algorithm that uses this misspecified basis, and subsequently analyze the regret of this algorithm. This leads to the following insights:

* Our results generalize the understanding of when logarithmic regret is possible in adaptive LQR beyond the cases of known $A^\star$ or $B^\star$ studied by [Cassel et al., 2020, Jedra and Proutiere, 2022].

* When misspecification is present, the regret incurs a term that is linear in $T$. The coefficient for this term decays gracefully as the level of misspecification diminishes. As a result, small misspecification means the regret is dominated by sublinear terms in the low data regime of interest for adaptive control. These terms are favorable to those possible in the absence of prior knowledge.

We validate our theory with numerical experiments, and show the benefit using a dynamics representation determined  by pre-training on offline data from related systems for adaptive control.

§.§ Notation

The Euclidean norm of a vector $x$ is denoted $\norm{x}$. For a matrix $A$, the spectral norm is denoted $\norm{A}$, and the Frobenius norm is denoted $\norm{A}_F$. We use $\dagger$ to denote the Moore-Penrose pseudo-inverse. The spectral radius of a square matrix is denoted $\rho(A)$. l4dc>0A symmetric, positive semi-definite (psd) matrix $A = A^\top$ is denoted $A \succeq 0$.  Similarly $A \succeq B$ denotes that $A-B$ is positive semidefinite. The minimum eigenvalue of a symmetric, positive definite matrix $A$ is denoted $\lambda_{\min}(A)$.
For $f,g :D \to \mathbb{R}$, we write $f \lesssim g$ if for some $c > 0$, $f(x) \leq c g(x)\,\forall x \in D$. We denote the solutions to the discrete Lyapunov equation by $\dlyap(A,Q)$ and the discrete algebraic Riccati equation by $\dare(A,B,Q,R)$. l4dc>0We use $x \vee y$ to denote the maximum of $x$ and $y$.

§ PROBLEM FORMULATION

§.§ System model

We consider the system (<ref>) where the noise $w_t$ has independent identically distributed elements that are mean zero and $\sigma^2$-sub-Gaussian for some $\sigma^2\in \R$ with $\sigma^2 \geq 1$. We additionally assume that the noise has identity covariance: $\E \brac{w_t  w_t^\top} = I$.[Noise that enters the process through a non-singular matrix $H$ can be addressed by rescaling the dynamics by $H^{-1}$.]
We suppose the dynamics admit the  decomposition

\begin{align}
\label{eq: low dim structure}
\bmat{A^\star & B^\star} &= \VEC^{-1}\paren{\Phi^\star \theta^\star},
\end{align}

where $\Phi^\star\in \R^{\dx(\dx+\du)\times \dtheta}$ specifies the model structure, and has orthonormal columns. Meanwhile, $\theta^\star \in\R^{\dtheta}$ specifies the parameters. The operator $\VEC^{-1}$ maps a vector in $\R^{\dx(\dx+\du)}$ into a matrix in $\R^{\dx \times (\dx+\du)}$ by stacking length $\dx$ blocks of the the vector into columns of the matrix, working top to bottom and left to right.
We can write this as a linear combination of basis matrices:

\begin{align*}
\bmat{A^\star & B^\star} = \sum_{i=1}^{\dtheta} \theta^\star_i \bmat{\Phi^{A,\star}_i & \Phi^{B,\star}_i}, \mbox{ where } \bmat{\Phi^{A,\star}_i & \Phi^{B,\star}_i} = \VEC^{-1} \Phi^\star_i,
\end{align*}

and $\Phi^\star_i$ is the $i^{\mathrm{th}}$ column of $\Phi^\star$. This decomposition of the data generating process is a natural extension of the low-dimensional linear representations considered in [Du et al., 2020] to the setting of multiple related dynamical systems with shared structure determined by $\Phi^\star$. A version of this model for autonomous systems was considered by [Modi et al., 2021] for multi-task system identification.

We assume that both $\Phi^\star$ and $\theta^\star$ are unknown; however, we have an estimate $\hat \Phi \in \R^{\dx(\dx+\du)\times \dtheta}$, also with orthonormal columns, for $\Phi^\star$. Such an esimate may be obtained by performing a pre-training step

on offline data from a collection of systems related to (<ref>) by the shared matrix $\Phi^\star$ in (<ref>). Due to the noise present in the offline data, this esimate will be imperfect, resulting  in misspecification[Sample complexity bounds for learning $\hat \Phi$ are provided by [Zhang et al., 2023], so this step is not studied here.]. To quantify the level of misspecification between this estimate and the underlying data generating process, we use the following subspace distance metric.

Let $\Phi^\star_\perp$ complete the basis of $\Phi^\star$ such that $\bmat{\Phi^\star & \Phi^\star_\perp}$ is an orthogonal matrix. Then the subspace distance between $\Phi^\star$ and $\hat \Phi$ is
d(\Phi^\star, \hat \Phi) \triangleq \norm{\hat \Phi^\top \Phi^\star_\perp}.

Note that the above distance is small when the range of the matrices $\hat \Phi$ and $\Phi^\star$ is similar. In particular, the above distance may be small even when $\norm{\hat \Phi - \Phi^\star}$ is large.

As long as $d(\Phi^\star, \hat \Phi)$ is sufficiently small and the dimension $\dtheta < \dx (\dx+\du)$, the estimate $\hat \Phi$ allows the learner to fit a model with less data than would be required to estimate $\bmat{A^\star & B^\star}$ from scratch. This benefit comes at the cost of a bias in the learner's model that grows with $d(\Phi^\star, \hat \Phi)$.

§.§ Learning objective

The goal of the learner is to interact with system (<ref>) while keeping the cumulative cost small, where the cumulative cost is defined for matrices $Q \succeq I$ and $R = I$ as[Generalizing to arbitrary $Q\succ 0$ and $R\succ 0$ can be performed by scaling the cost and changing the input basis. ]

\begin{align}
\label{eq: cost}
C_T \triangleq \sum_{t=1}^T c_t, \mbox{ where } c_t \triangleq x_t^\top Q x_t  + u_t^\top R u_t.
\end{align}

To define an algorithm that keeps the cost small, we first introduce the infinite horizon LQR cost:

\begin{align}
\label{eq: lqr cost}
\calJ(K) \triangleq \limsup_{T\to\infty} \frac{1}{T} \E^K C_T,
\end{align}

where the superscript of $K$ on the expectation denotes that the cost is evaluated under the state feedback controller $u_t = Kx_t$. To ensure that there exists a controller such that (<ref>) has finite cost, we assume $(A^\star, B^\star)$ is stabilizable. Under this assumption,

(<ref>) is minimized by the LQR controller $K_{\infty}(A^\star,B^\star)$, where

K_{\infty}(A,B) \triangleq - (B^\top P_{\infty}(A,B) B + R)^{-1} B^\top P_{\infty}(A,B) A,

and $P_{\infty}(A, B) \triangleq \dare(A,B,Q,R)$. We define the shorthands $P^\star \triangleq P_{\infty}(A^\star, B^\star)$ and $K^\star \triangleq K_\infty(A^\star, B^\star)$. To characterize the infinite horizon LQR cost of an arbitrary stabilizing controller $K$, we additionally define the solution $P_K$ to the lyapunov equation for the closed loop system under an arbitrary $K$ such that $\rho(A^\star + B^\star K) < 1$: $P_K \triangleq \dlyap(A^\star + B^\star K, Q+ K^\top R K)$.
For a controller $K$ satisfying $\rho(A^\star + B^\star K) < 1$, $\calJ(K) = \trace(P_K)$. We have that $P_{K^\star} = P^\star$.

The infinite horizon LQR controller provides a baseline level of performance that our learner cannot surpass in the limit as $T \to \infty$. Borrowing the notion of regret from online learning, as in [Abbasi-Yadkori and Szepesvári, 2011], we quantify the performance of our learning algorithm by comparing the cumulative cost $C_T$ to the scaled infinite horizon cost attained by the LQR controller if the system matrices $\bmat{A^\star & B^\star}$ were known:

\begin{align}
\label{eq: regret}
R_T \triangleq C_T - T \calJ(K^\star).
\end{align}

In light of the above reformulation, the goal of the learner is to interact with the system (<ref>) to maximize the information about the relevant parameters for control while simultaneously regulating the system to minimize $R_T$. A reasonable strategy to do so is for the learner to use its history of  interaction with the system to construct a model for the dynamics, e.g. by determining estimates $\hat A$
and $\hat B$. It may then use these estimates as part of a certainty equivalent (CE) design by synthesizing controllers $\hat K = K_\infty(\hat A, \hat B)$. Prior work has shown that if the model estimate is sufficiently close to the true dynamics, then the cost of playing the controller $\hat K$ exceeds the cost of playing $K^\star$ by a quantity that is quadratic in the estimation error [Mania et al., 2019, Simchowitz and Foster, 2020].

Define $\varepsilon \triangleq \frac{1}{2916 \norm{P^\star(A^\star, B^\star)}^{10}}$. If

\norm{\bmat{\hat A & \hat B}-\bmat{A^\star & B^\star}}_F^2 \leq \varepsilon,
then $\calJ(\hat K)  - \calJ(K^\star) \leq 142 \norm{P^\star}^8 \norm{\bmat{\hat A & \hat B}-\bmat{A^\star & B^\star}}_F^2$.

§.§ Algorithm description

Certainty Equivalent Control with Continual Exploration

[1]
Input:  Stabilizing controller $K_0$, initial epoch length $\epoch$, number of epochs $k_{\fin}$, exploration sequence $\sigma_1^2, \sigma_2^2, \sigma_3^2, \dots \sigma_{k_{\fin}}^2$, state bound $x_b$, controller bound $K_b$
Initialize:  $\hat K_1 \gets K_0$,  $\tau_0 \gets 0$, $T \gets \tau_1 2^{k_{\fin}-1}$.
$k=1,2, \dots, k_{\fin}$
$t=\tau_{k-1}+1, \dots, \tau_{k}$
$\norm{x_t}^2 \geq x_b^2 \log T$ or $\norm{\hat K_k}\geq K_b$
Abort and play $K_0$ forever
Play $u_t = \hat K_k x_t + \sigma_k g_t$, where $g_t \sim \calN(0,I)$
$\hat \theta_{k}, \Lambda  \gets \texttt{LS}(\hat \Phi, x_{\tau_{k-1}+1:\tau_k+1}, u_{\tau_{k-1}+1: \tau_k})$ <Ref>
$\bmat{\hat A_{k} & \hat B_{k}} \gets \VEC^{-1} \paren{\hat \Phi \hat \theta_{k}} $
$\hat K_{k+1} \gets K_\infty(\hat A_{k}, \hat B_{k})$
$\tau_{k+1} \gets 2 \tau_k$

Our proposed algorithm, <Ref>, is a CE algorithm akin to that proposed in [Cassel et al., 2020]. The algorithm takes a stabilizing controller $K_0$ as an input.[While providing a stabilizing controller is common in prior work, not all analyses require it. [Lale et al., 2022].]

Starting from this controller, <Ref> follows a doubling epochs strategy. At the end of each epoch, it uses the data collected during the epoch along with the estimate for $\hat \Phi$ to obtain an estimate for $\hat \theta$ by solving a least squares problem (as detailed in <Ref>). The estimated parameters $\hat \theta$ are combined with the estimate $\hat \Phi$ to obtain the dynamics estimate $\bmat{\hat A & \hat B}$. This estimate is used to synthesize a CE controller $\hat K = K_\infty(\hat A, \hat B)$. In the next epoch, the learner plays the resultant controller with exploratory noise added. Before playing each input, the algorithm checks whether the state or the controller exceed bounds determined by algorithm inputs $x_b$ and $K_b$. If they do, it aborts the certainty equivalent scheme, and plays the initial stabilizing controller for all time. Doing so enables bounding of the regret during unlikely events where the CE controller fails. The key difference from the CE algorithms proposed in prior work is that the system identification step solves a least squares problem defined in terms of the estimate $\hat \Phi$ to estimate the unknown parameters.

Least squares: $\texttt{LS}(\hat \Phi, x_{1:t+1}, u_{1:t+1})$

[1]
Input: Model structure estimate $\hat \Phi$, state data $x_{1:t+1}$, input data $u_{1:t}$
Return:  $\hat \theta, \Lambda$, where

\begin{align*}
\hat \theta = \Lambda^\dagger \paren{\sum_{s=1}^{t} \hat \Phi^\top \paren{ \bmat{x_s \\ u_s} \otimes I_{\dx}} x_{s+1} },  \quad \mbox{and} \quad \Lambda = \sum_{s=1}^{t } \hat \Phi^\top \paren{ \bmat{x_s \\ u_s}\bmat{x_s \\ u_s} ^\top \otimes I_{\dx}}\hat \Phi.
\end{align*}

§ REGRET BOUNDS

We now present our bounds on the expected[In contrast to high probability regret bounds, expected regret provides an understanding of what happens in the unlikely events where controller performs poorly.]
regret incurred by <Ref>. l4dc>0Further discussion and complete proofs may be found in <cit.>.

Consider running <Ref> for $T = \tau_1 2^{k_\fin-1} $ timesteps, where $\tau_1$ is the initial epoch length and $k_{\fin}$ is the number of epochs. To bound the regret incurred by this algorithm, we decompose the regret into that achieved by the algorithm under a high probability success event, and that incurred during a failure event under which the state or controller bound in line 5 of <Ref> are violated. To ensure the failure event occurs with a small probability, we make the following assumption on the state and controller bounds, which uses the shorthand $\Psi_{B^\star} \triangleq \max\curly{1,\norm{B^\star}}$.

We assume that $x_b   \geq 400 \norm{P_{K_0}}^2 \Psi_{B^\star} \sigma \sqrt{\dx+\du} \mbox{ and }
K_b   \geq \sqrt{2 \norm{P_{K_0}}}$.

We make additional assumptions about the remaining arguments supplied as inputs to the algorithm in two cases: one in which no additional assumptions about the dynamics are made (<Ref>), and one in which we assume that the system structure estimate is such that the initial stabilizing controller and the optimal controller provide sufficient excitation to identify the unknown parameters (<Ref>).

§.§ Certainty equivalent control with continual exploration

To ensure an estimate satisfying the condition in <Ref> is attainable, the gap between the model structure estimate and the ground truth cannot be too large, leading to the following assumption.

\beta_1 \triangleq C_{\mathsf{bias},1} \sigma^4 \norm{P_{K_0}}^{12} \Psi_{B^\star}^8 \norm{\theta^\star}^2 (\dx+\du) \sqrt{\frac{\dtheta}{\du}}

for a sufficiently large universal constant $C_{\mathsf{bias},1}$.
We assume our representation error satisfies $
d(\hat \Phi, \Phi^\star) \leq \frac{\varepsilon }{2 \beta_1 \log T}.$

The requirement above arises from the way that misspecification enters our bounds on the estimation error $\norm{\bmat{\hat A & \hat B} - \bmat{A^\star & B^\star}}_F^2$. See the definition of $\calE_{\mathsf{est},1}$ in <Ref>.

In this setting, we run <Ref> with exploratory inputs injected to ensure identifiability of the unknown parameters. Doing so provides the regret guarantees in the following theorem.

Consider applying <Ref> with initial stabilizing controller $K_0$ for $T = \tau_1 2^{k_{\fin}-1}$ timesteps for some positive integers $k_{\fin}$, and $\tau_1$.

Suppose that for some $\exploration \geq d(\hat \Phi, \Phi^\star)$, the exploration sequence is given by
$\sigma_k^2 = \max\curly{\frac{\sqrt{\du/\dtheta}}{\sqrt{\epoch 2^{k-1}}} , \exploration} \, \forall k \geq 1.$ Suppose the state bound $x_b$ and the controller bound $K_b$ satisfy <Ref> and that $\hat \Phi $ satisfies <Ref>.
There exists a universal positive constant $C_{\mathsf{warm\,up}}$ such that if $\tau_1 = \tau_{warm\,up} \log^2 T$ for some

$$\tau_{\mathsf{warm\,up}}\geq  C_{\mathsf{warm\,up}} \sigma^4 \norm{P_{K_0}}^3\max\curly{ \Psi_{B^\star}^2 (\dx+\du), x_b^2, \frac{\log \frac{1}{\norm{P^\star}}}{\log\paren{1- \frac{1}{ \norm{P^\star}}}}, \paren{\frac{\sqrt{\dtheta \du} }{\varepsilon}}^2},$$

then the expected regret satisfies

\begin{align*}
\E \brac{ R_T }  \leq  c_0 \log^2(T) + c_1 \sqrt{\dtheta \du} \sqrt{T} \log T + c_2 \exploration T \log T,
\end{align*}

$c_0 = \texttt{poly}(\dx, \du,\norm{P_{K_0}}, \Psi_{B^\star},\tau_{\mathsf{warm\,up}}, x_b, K_b)$,

$c_1 =\texttt{poly}(\norm{P_{K_0}}, \Psi_{B^\star}, \sigma)$

$c_2 = \texttt{poly}(\du, \dx, \dtheta, \norm{P_{K_0}},\Psi_{B^\star},  \norm{\theta^\star}, \sigma).$

First consider the above result in the absence of misspecificaion: $\exploration = d(\hat \Phi, \Phi^\star) = 0$. In this case, the dominant term grows with $\sqrt{\dtheta \du}\sqrt{T} \log T$. As long as $\dtheta \leq \dx\du$, this is smaller than the dependence of $\sqrt{\du^2 \dx}$ which appears in the lower bounds of for the regret of learning to control a system with entirely unknown $A^\star$ and $B^\star$ [Simchowitz and Foster, 2020]. If the misspecification is nonzero, then the regret bound incurs an additional term that grows linearly (up to $\log$ factors) with $T$. However, as long as $d(\hat \Phi, \Phi^\star)$ is sufficiently small, there exists a regime of $T$ for which the $\sqrt{T}$ term dominates, and using the misspecified basis provides a benefit over learning from scratch.

§.§ Certainty equivalent control without additional exploration

In this section, we analyze the regret attained under the additional assumption that the process noise fully excites the relevant modes of the system under $K^\star$ and $K_0$. This may be guaranteed as follows.

Let $\alpha \geq \frac{1}{3 \norm{P^\star}^{3/2}}$. Assume that

$\min_{v: \norm{v}=1} \norm{\sum_{i=1}^{\dtheta} v_i(\hat \Phi^A_i + \hat \Phi^B_i K)}_F^2 \geq \alpha^2 \quad$ for  $K = K_0, K^\star,$

where $\bmat{\hat \Phi^A_i & \hat \Phi^B_i} = \VEC^{-1}\hat \Phi_i$, and $\hat \Phi_i$ is the $i^{\mathsf{th}}$ column of $\hat \Phi$.

Under the above assumption, we may run <Ref> without an additional exploratory input injected. As in <Ref>, we require that the representation error is small enough to guarantee the closeness condition in <Ref> may be satisfied with our estimated model.

Define $
\beta_2 \triangleq C_{\mathsf{bias},2} \frac{\varepsilon \norm{P_{K_0}}^9 \Psi_{B^\star}^8 \norm{\theta^\star}^2 (\dx+\du)}{\dtheta \min\curly{\alpha^2, \alpha^4}}$
for a sufficiently large universal constant $C_{\mathsf{bias},2}$. Our representation error satisfies $
d(\hat \Phi, \Phi^\star) \leq \sqrt{\frac{\varepsilon }{2 \beta_2}}.$

This requirement again arises from dependence of the estimation error bounds on the misspecification.  See the definition of $\calE_{\mathsf{est},2}$ in <Ref>.

Under these assumptions, our regret bound may be improved to that in the following theorem.

Consider applying <Ref> with initial stabilizing controller $K_0$ for $T = \tau_1 2^{k_{\fin}}$ timeteps for some positive integers $k_{\fin}$, and $\tau_1$.
Additionally suppose the exploration sequence is zero for all time: $\sigma_k^2 = 0$ for $k = 1, \dots, k_{\fin}$. Suppose the state bound $x_b$ and the controller bound $K_b$ satisfy <Ref>, and that $\hat \Phi$ satisfies <Ref> and <Ref>. There exists a positive universal constant $C_{\mathsf{warm\,up}}$ such that if $\tau_1 = \tau_{\mathsf{warm\,up}} \log T$, for

$$\tau_{\mathsf{warm\,up}}\geq  C_{\mathsf{warm\,up}}\sigma^4 \norm{P_{K_0}}^3 \Psi_{B^\star}^2 \max\curly{ (\dx+\du), x_b^2,\frac{\log \frac{1}{8 \sqrt{\norm{P^\star}}}}{\log\paren{1- \frac{1}{2 \norm{P^\star}}}},\frac{ \dtheta}{2 \varepsilon \alpha^2}},$$

then the expected regret satisfies

\begin{align*}
\E \brac{R_T} \leq  c_1 \log^2(T) + c_2 d(\hat \Phi, \Phi^\star)^2 T,
\end{align*}

$c_1 = \texttt{poly}(\dx,\du, \dtheta,\norm{P_{K_0}},\Psi_{B^\star},\norm{\theta^\star}, \sigma,  \alpha^{-1},\tau_{\mathsf{warm\,up}},K_b, x_b)$

$c_2 = \texttt{poly}( \dx,\du,\dtheta,\norm{P_{K_0}}, \Psi_{B^\star}, \norm{\theta^\star}, \alpha^{-1}).$

When the misspecification is zero, the expected regret grows with $\log^2 T$. Prior work [Cassel et al., 2020, Jedra and Proutiere, 2022] has shown that such rates are possible if either $A^\star$ or $B^\star$ are known to the learner.
See l4dc>0<Ref> of <cit.> <Ref> for details about how to obtain logarithmic regret in these settings using <Ref>. The above result expands on prior work by generalizing conditions for prior knowledge that are sufficient to achieve logarithmic regret.

With misspecification present, the above theorem has a term growing linearly $T$. In contrast to <Ref>, the coefficient for this term is proportional to the level of misspecification squared, which is smaller than the linear dependence on misspecification in <Ref>. This result shows that if some coarse system knowledge depending on a few unknown parameters is available in advance and the unknown parameters are easily identifiable in the sense of <Ref>, then there exists a substantial regime of $T$ for which the regret incurred is much smaller than that attained by learning to control the system from scratch with fully unknown $A^\star$ and $B^\star$ (where the regret scales as $\sqrt{T}$).

§.§ Proof sketch

Our main result proceeds by first defining a success events for which the certainty equivalent control scheme never aborts, and generates dynamics estimates $\bmat{\hat A_k & \hat B_k}$ which are sufficiently close to the true dynamics $\bmat{A^\star & B^\star}$ at all times. The success events for <Ref> and <Ref> are $\calE_{\mathsf{success},1} =  \calE_{\mathsf{bound}} \cap  \calE_{\mathsf{est},1}$ and $\calE_{\mathsf{success},2}= \calE_{\mathsf{bound}} \cap \calE_{\mathsf{est},2}$ respectively, where

\begin{align*}
\calE_{\mathsf{bound}} &= \curly{\norm{x_t}^2  \leq x_b^2 \log T \quad \forall t=1,\dots , T} \cap \curly{\norm{\hat K_k} \leq K_b \,, \forall k=1,\dots, k_{\fin}}, \\
\calE_{\mathsf{est},1} &= \curly{\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 \leq C_{\mathsf{est},1} \frac{\sigma^2 \sqrt{\dtheta \du} \norm{P_{K_0}}}{\sqrt{\tau_{k}}} \log T + \beta_1 d(\hat \Phi, \Phi^\star) \log T}, \\
\calE_{\mathsf{est},2} &= \curly{\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 \leq C_{\mathsf{est},2} \frac{\sigma^2  \dtheta   }{ \tau_{k} \alpha^2 }\log T+ \beta_2 d(\hat \Phi, \Phi^\star)^2 },
\end{align*}

and $C_{\mathsf{est},1}$ and $C_{\mathsf{est},2}$ are positive universal constants.

We use the success events to decompose the expected regret as in [Cassel et al., 2020]:

\E \brac{R_T} = R_1 + R_2+ R_3 - T\calJ(K^\star), %\underbrace{\sum_{t=1}^{\epoch} x_t^\top Q x_t  + u_t^\top R u_t - \epoch \calJ^\star}_{\mbox{First round regret}} + \underbrace{\sum_{t=\epoch+1}^T \paren{ x_t^\top Q x_t  + u_t^\top R u_t} - (T-\epoch) \calJ^\star.}_{\mbox{Subsequent round regret}}

where for $\calE_{\mathsf {success}} = \calE_{\mathsf{success},1}$ or $\calE_{\mathsf {success}} =\calE_{\mathsf{success}, 2}$,

\begin{align}
\label{eq: regret decomposition}
R_1 = \E \brac{\mathbf{1}(\calE_{\mathsf{success}}) \sum_{k=2}^{k_\fin} J_k}, \quad R_2 =  \E \brac{\mathbf{1}(\calE_{\mathsf{success}}^c) \sum_{t=\tau_1 + 1}^{T} c_t}, \quad  \mbox{ and } \quad R_3 = \E \brac{\sum_{t=1}^{\tau_1} c_t},
\end{align}

are the costs due to success, failure, and the first epoch respectively. Here, $J_k$ are the epoch costs defined as $J_k = \sum_{t=\tau_k}^{\tau_{k+1}} c_t$. In the settings of both <Ref> and <Ref>, $R_3$ is given by $\tau_1 \trace\paren{P_{K_0} (I+ \sigma_1^2 B^\star (B^\star)^\top)}$, while $R_2$ is controlled using the upper bounds on the state and controller to obtain a bound on the cost, which is then multiplied by the small probability of the failure event. To control $R_1$, we show that under the success event, the closeness condition <Ref> is satisfied. As a result, the cost of each epoch $J_k$ is $(\tau_k-\tau_{k-1}) \calJ(K^\star)$ in addition to a term proportional to $(\tau_k-\tau_{k-1})\paren{ \norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 + \sigma_k^2}.$ Using the estimation error bounds of events $\calE_{\mathsf{est},1}$ and $\calE_{\mathsf{est},2}$ along with the choices for $\sigma_k^2$ in the two settings, we find that the quantity $R_1 - T\calJ(K^\star)$ is proportional to $\sqrt{T} \log T + d(\hat \Phi, \Phi^\star) T \log T$ in the setting of <Ref>, and $ \log^2{T} + d(\hat \Phi, \Phi^\star)^2 T$ in the setting of <Ref>. Combining terms provides the expected regret bounds in Theorems <ref> and <ref>l4dc>0[High probability estimation error bounds are proved in <Ref>. These are used to establish high probability bounds on the success events in <Ref>. The bounds on $R_1$, $R_2$ and $R_3$ are established in <Ref>. ].

§ NUMERICAL EXAMPLE

To validate our bounds, we run <Ref> on the system (<ref>) where $A^\star$ and $B^\star$
are  obtained by linearizing and discretzing the cartpole dynamics defined by the equations

$(M + m) \ddot{x} + m\ell(\ddot{\theta}\cos(\theta) - \dot{\theta}^2\sin(\theta)) = u,$ and $
m(\ddot{x}\cos(\theta) + \ell\ddot{\theta} - g\sin(\theta)) = 0,$

for cart mass $M=1$, pole mass $m=1$, pole length $\ell=1$, and gravitiy $g=1$. Discretization uses Euler's approach with stepsize $0.25$. The disturbance signal is generated as $w_t \sim \calN(0, 0.01 I)$.

We consider various inputs for the representation estimate $\hat \Phi$ and the exploration sequence $\sigma_1^2, \dots, \sigma_{k_{\fin}}^2$. The remaining parameters are discussed in l4dc>0<Ref> of <cit.>. <Ref>.

Regret of <Ref> with various choices for $\hat\Phi$.

No Misspecification:  In <Ref>, we plot the regret of <Ref>  in the absence of misspecification, i.e. $d(\hat\Phi, \Phi^\star)=0$. We consider several instances for the representation: one for fully unknown $A^\star$ and $B^\star$, one which encodes a setting where the $A^\star$ matrix is known up to an unknown scaling, and one which captures a lumped parameter model where the discretized and linearized cartpole structure is known up to scale, but the values of the entries which vary with cart mass, pole mass, and pole length are unknown. We additionally consider extending the lumped parameter representation by adding a basis vector that ensures the condition in <Ref> is violated. For the representation capturing fully unknown $A^\star$ and $B^\star$, and the extended lumped parameter representation, the condition in <Ref> is not satisfied, so we run <Ref> with exploration noise scaling as $\sigma_k^2 \propto \frac{1}{\sqrt{2^k}}$, and incur $\sqrt{T}$ regret, as predicted by <Ref>.  The extended lumped parameter representation incurs regret at a slower rate than the setting when the system is fully unknown. This is predicted by <Ref> due to the fact that the extended lumped parameter model has $\dtheta = 6 < 20 = \dx(\dx+\du)$, so the coefficient on the $\sqrt T$ term is smaller. For the remaining settings, <Ref> is satisfied, so we run the algorithm with no additional exploration and incur logarithimic regret, as predicted in <Ref>.

[Continual exploration]

[No exploration]

We plot the regret of <Ref> with $\hat \Phi$ describing a lumped parameter model (right), or a lumped parameter model and extended such that the condition <Ref> is violated (left). In both settings the representations are perturbed, resulting in a misspecification between the true representation $\Phi^\star$ and the representation estimate $\hat \Phi$. The regret is compared to that incurred by running <Ref> with a fully unknown $A^\star$ and $B^\star$.

Artificial Misspecification:  In <Ref>, we compare the regret from the fully unknown setting to the regret with a misspecified lumped parameter representation. <Ref>  considers the lumped parameter representation that is extended such that <Ref> is violated. Therefore the learner must continually inject noise to the system in order to explore. We artificially create misspecification by adding small perturbations to the true representation such that $d(\hat \Phi, \Phi^\star) > 0$. We see that in the low data regime, the regret incurred is less than that incurred when the model is fully unknown. When the misspecification level is $0.05$, the bias in the identification due to the misspecification causes the regret to rapidly overtake the regret from the fully unkown setting. When the misspecification is small, the regret remains less than that from the fully unknown setting for the entire horizon of $T$ values that are plotted. <Ref> considers the lumped parameter setting without the extension, for which <Ref> is satisfied. As in <Ref>, we add a perturbation to the representation to create misspecification. In this setting, we consider much larger perturbations, such that $d(\hat \Phi, \Phi^\star)$ is $0.1$, $0.15$, or $0.20$. For all three such situations, the regret begins much smaller than that of the fully unknown model, but overtakes it as $T$ becomes large.

Regret of Alg. <ref> with $\hat \Phi$ learned offline from related systems.

Learned Representation:  In <Ref>, we consider a setting motivated by multi-task learning, in which a representation is learned using offline data from several systems related to the system of interest. In particular, we collect trajectories of length $1200$ from five discretized and linearized cartpole systems generated with various values of the parameters $(M, m,\ell)$. The resulting data is in turn used to fit a a representation $\hat \Phi$.[See l4dc>0<Ref> of <cit.> <Ref> for details.] Once the representation is obtained, we run <Ref> in the absence of exploratory input. We see that the regret incurred is much lower than the setting in which the dynamics are fully unknown for the small data regime, but overtakes it as $T$ becomes large. This aligns with the results from the artificial misspecification experiment. By computing the distance between the learned and true lumped parameter representations, we find that $d(\hat \Phi, \Phi^\star) = 0.2041$.

§ CONCLUSION

We studied adaptive LQR in the presence of misspecification between the learner's simple model structure for the dynamics, and the true dynamics. Our proposed algorithm performs well in both experiments and theory as long as this misspecification is sufficiently small. Our analysis shows a phase shift in the problem that depends on whether the learner's prior knowledge  enables identification of the unknown parameters without additional exploration, thus allowing regret that is logarithmic in $T$.
There are many interesting avenues for future work, including extending the analysis to settings where a collection of nonlinear basis functions for the dynamics are misspecified, e.g., by modifying the model studied in [Kakade et al., 2020]. Another direction is to analyze the setting where the learner's simple model is updated online by sharing data from a collection of related systems, as in recent work on federated learning in dynamical systems [Wang et al., 2023].

[Abbasi-Yadkori and Szepesvári, 2011]
Yasin Abbasi-Yadkori and Csaba Szepesvári.
Regret bounds for the adaptive control of linear quadratic systems.
In Proceedings of the 24th Annual Conference on Learning
Theory, pages 1–26. JMLR Workshop and Conference Proceedings, 2011.

[Åström and Wittenmark, 2013]
Karl J Åström and Björn Wittenmark.
Adaptive control.
Courier Corporation, 2013.

[Åström and Wittenmark, 1973]
Karl Johan Åström and Björn Wittenmark.
On self tuning regulators.
Automatica, 90 (2):0 185–199, 1973.

[Cassel et al., 2020]
Asaf Cassel, Alon Cohen, and Tomer Koren.
Logarithmic regret for learning linear quadratic regulators
In International Conference on Machine Learning, pages
1328–1337. PMLR, 2020.

[Cederberg et al., 2022]
Daniel Cederberg, Anders Hansson, and Anders Rantzer.
Synthesis of minimax adaptive controller for a finite set of linear
In 2022 IEEE 61st Conference on Decision and Control (CDC),
pages 1380–1384. IEEE, 2022.

[Cohen et al., 2019]
Alon Cohen, Tomer Koren, and Yishay Mansour.
Learning linear-quadratic regulators efficiently with only $\sqrt t$
In International Conference on Machine Learning, pages
1300–1309. PMLR, 2019.

[Dasari et al., 2019]
Sudeep Dasari, Frederik Ebert, Stephen Tian, Suraj Nair, Bernadette Bucher,
Karl Schmeckpeper, Siddharth Singh, Sergey Levine, and Chelsea Finn.
Robonet: Large-scale multi-robot learning.
arXiv preprint arXiv:1910.11215, 2019.

[Dean et al., 2018]
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu.
Regret bounds for robust adaptive control of the linear quadratic
Advances in Neural Information Processing Systems, 31, 2018.

[Devlin et al., 2018]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.
Bert: Pre-training of deep bidirectional transformers for language
arXiv preprint arXiv:1810.04805, 2018.

[Dosovitskiy et al., 2020]
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn,
Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg
Heigold, Sylvain Gelly, et al.
An image is worth 16x16 words: Transformers for image recognition at
arXiv preprint arXiv:2010.11929, 2020.

[Du et al., 2020]
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei.
Few-shot learning via learning the representation, provably.
arXiv preprint arXiv:2002.09434, 2020.

[Gregory, 1959]
PC Gregory.
Proceedings of the Self Adaptive Flight Control Systems
Symposium, volume 59.
Wright Air Development Center, Air Research and Development Command,
United …, 1959.

[Hazan et al., 2020]
Elad Hazan, Sham Kakade, and Karan Singh.
The nonstochastic control problem.
In Algorithmic Learning Theory, pages 408–421. PMLR, 2020.

[Ioannou and Sun, 1996]
Petros A Ioannou and Jing Sun.
Robust adaptive control, volume 1.
PTR Prentice-Hall Upper Saddle River, NJ, 1996.

[Jedra and Proutiere, 2020]
Yassir Jedra and Alexandre Proutiere.
Finite-time identification of stable linear systems optimality of the
least-squares estimator.
In 2020 59th IEEE Conference on Decision and Control (CDC),
pages 996–1001. IEEE, 2020.

[Jedra and Proutiere, 2022]
Yassir Jedra and Alexandre Proutiere.
Minimal expected regret in linear quadratic control.
In International Conference on Artificial Intelligence and
Statistics, pages 10234–10321. PMLR, 2022.

[Kakade et al., 2020]
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun.
Information theoretic regret bounds for online nonlinear control.
Advances in Neural Information Processing Systems,
33:0 15312–15325, 2020.

[Lale et al., 2020]
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar.
Logarithmic regret bound in partially observable linear dynamical
Advances in Neural Information Processing Systems,
33:0 20876–20888, 2020.

[Lale et al., 2022]
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Animashree Anandkumar.
Reinforcement learning with fast stabilization in linear dynamical
In International Conference on Artificial Intelligence and
Statistics, pages 5354–5390. PMLR, 2022.

[Mania et al., 2019]
Horia Mania, Stephen Tu, and Benjamin Recht.
Certainty equivalence is efficient for linear quadratic control.
Advances in Neural Information Processing Systems, 32, 2019.

[Modi et al., 2021]
Aditya Modi, Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George
Joint learning of linear time-invariant dynamical systems.
arXiv preprint arXiv:2112.10955, 2021.

[Narendra and Annaswamy, 2012]
Kumpati S Narendra and Anuradha M Annaswamy.
Stable adaptive systems.
Courier Corporation, 2012.

[Peña et al., 2009]
Victor H Peña, Tze Leung Lai, and Qi-Man Shao.
Self-normalized processes: Limit theory and Statistical
Springer, 2009.

[Rantzer, 2021]
Anders Rantzer.
Minimax adaptive control for a finite set of linear systems.
In Learning for Dynamics and Control, pages 893–904. PMLR,

[Renganathan et al., 2023]
Venkatraman Renganathan, Andrea Iannelli, and Anders Rantzer.
An online learning analysis of minimax adaptive control.
arXiv preprint arXiv:2307.07268, 2023.

[Simchowitz and Foster, 2020]
Max Simchowitz and Dylan Foster.
Naive exploration is optimal for online lqr.
In International Conference on Machine Learning, pages
8937–8948. PMLR, 2020.

[Simchowitz et al., 2020]
Max Simchowitz, Karan Singh, and Elad Hazan.
Improper learning for non-stochastic control.
In Conference on Learning Theory, pages 3320–3436. PMLR,

[Stein, 1980]
Gunter Stein.
Adaptive flight control: A pragmatic view.
In Applications of Adaptive Control, pages 291–312. Elsevier,

[Stewart and Sun, 1990]
Gilbert W Stewart and Ji-guang Sun.
Matrix perturbation theory.
(No Title), 1990.

[Tilli, 1998]
Paolo Tilli.
Singular values and eigenvalues of non-hermitian block toeplitz
Linear algebra and its applications, 2720
(1-3):0 59–89, 1998.

[Tripuraneni et al., 2020]
Nilesh Tripuraneni, Michael Jordan, and Chi Jin.
On the theory of transfer learning: The importance of task diversity.
Advances in neural information processing systems,
33:0 7852–7862, 2020.

[Tsiamis et al., 2022]
Anastasios Tsiamis, Ingvar M Ziemann, Manfred Morari, Nikolai Matni, and
George J Pappas.
Learning to control linear systems can be hard.
In Conference on Learning Theory, pages 3820–3857. PMLR,

[Tsiamis et al., 2023]
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas.
Statistical learning theory for control: A finite-sample perspective.
IEEE Control Systems Magazine, 430 (6):0
67–97, 2023.

[Vershynin, 2020]
Roman Vershynin.
High-dimensional probability.
University of California, Irvine, 2020.

[Wang et al., 2023]
Han Wang, Leonardo F Toso, Aritra Mitra, and James Anderson.
Model-free learning with heterogeneous dynamical systems: A federated
lqr approach.
arXiv preprint arXiv:2308.11743, 2023.

[Zhang et al., 2023]
Thomas T Zhang, Katie Kang, Bruce D Lee, Claire Tomlin, Sergey Levine, Stephen
Tu, and Nikolai Matni.
Multi-task imitation learning for linear dynamical systems.
In Learning for Dynamics and Control Conference, pages
586–599. PMLR, 2023a.

[Zhang et al., 2023]
Thomas TCK Zhang, Leonardo F Toso, James Anderson, and Nikolai Matni.
Meta-learning operators to optimality from multi-task non-iid data.
arXiv preprint arXiv:2308.04428, 2023b.

[Ziemann and Sandberg, 2022]
Ingvar Ziemann and Henrik Sandberg.
Regret lower bounds for learning linear quadratic gaussian systems.
arXiv preprint arXiv:2201.01680, 2022.

[Ziemann et al., 2023]
Ingvar Ziemann, Anastasios Tsiamis, Bruce Lee, Yassir Jedra, Nikolai Matni, and
George J. Pappas.
A tutorial on the non-asymptotic theory of system identification,

§ ADDITIONAL EXPERIMENTAL DETAILS

The matrices $A^\star$ and $B^\star$ considered in <Ref> are given as follows:

\begin{align}
% \label{eq: lin cartpole}
% x_{t+1} = \bmat{1 & 0.25 & 0 & 0 \\ 0 & 1 & -0.25 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0.5 & 1} x_t + \bmat{0 \\ 0.25 \\ 0 \\ -0.25} u_t + \sqrt{0.01} I w_t \triangleq Ax_t + Bu_t + \Sigma_w^{1/2} w_t,
A^\star = \bmat{1 & 0.25 & 0 & 0 \\ 0 & 1 & -0.25 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0.5 & 1}, \, B^\star = \bmat{0 \\ 0.25 \\ 0 \\ -0.25}.
\end{align}

We consider $Q=I$, and $R=I$. We keep the values of $K_0$, $\tau_1$, $x_b$, and $K_b$ fixed across all experiments as $\bmat{0.37 & 1.64 & 4.49 & 3.89}$, $1024$, $50$, and $15$. We replace the condition $\norm{x_t}^2 \geq x_b^2 \log T$ from line 5 of <Ref> with $\norm{x_t}^2 \geq x_b$. These modifications are made because the guarantees in <Ref> are not anytime, but rather require the number of timesteps $T$ which the algorithm is to be run as an input to the algorithm. For sake of efficiently plotting the regret against time, we remove the dependence of the algorithm on $T$, and keep these parameters fixed across time. Despite the discrepancy, we observe that the predicted trends still hold.

Learned Representation
The parameter values used for the systems which generate the offline data are
$(M,m,\ell) =(0.4, 1.0, 1.0)$, $(1.6, 1.3, 0.3)$, $(1.3, 0.7, 0.65)$, $(0.2, 0.06, 1.36)$ and, $(0.2, 0.47, 1.83)$. The data from the is collected with process noise $w_t\sim\calN(0,0.01 I)$, and inputs $u_t = K_0 x_t + \eta_t$, where $\eta_t \sim \calN(0, I)$. The representation is determined by jointly optimizing $\Phi$ along with the system specific parameter values $\theta$ to solve the least squares problem

\begin{align*}
\hat \Phi, \hat \theta^{(1)}, \dots, \hat \theta^{(5)} = \argmin_{\Phi, \theta^{(1)}, \dots, \theta^{(5)}} \sum_{i=1}^5 \sum_{t=1}^{1199} \norm{x_{t+1}^{(i)} - \VEC^{-1} \paren{\Phi \theta^{(i)}} \bmat{x_t^{(i)} \\ u_t^{(i)}} }^2,
\end{align*}

where the superscript $(i)$ indicates which of the five systems the data is collected from.

§ ESTIMATION ERROR BOUNDS

We begin by considering a general estimation problem in which the system is excited by an arbitrary stabilizing controller $K$ and excitation level defined by $\sigma_u$.  In particular, we consider the evolution of the following system:

\begin{equation}
\label{eq: rollout under K}
\begin{aligned}
x_{t+1} &= A^\star x_t + B^\star u_t +  w_t \\
u_t &= K x_t + \sigma_u g_t,
\end{aligned}
\end{equation}

where $g_t \overset{i.i.d.}{\sim} \calN(0,I)$, and $w_t$ is a random variable with $\sigma^2$-sub-Gaussian entries satifying $\E[w_t w_t^\top] =I  $. We assume that $\sigma_u^2\leq 1$ and that $x_1$ is a random variable.
We consider generating the estimates $\hat \theta, \Lambda = \texttt{LS}(\hat \Phi, x_{1:t+1}, u_{1:t})$.
We present a bound on the estimation error $\norm{\hat \Phi \hat \theta - \Phi^\star \theta^\star}^2$ in terms of the true system parameters as well as the amount of data, $t$.

Before presenting our main estimation result, we define the shorthand $A_K  \triangleq A^\star + B^\star K$. We also use the $\calH_\infty$ norm, defined below.

The $\calH_\infty$ norm of a stable matrix $A$ is given by

\begin{align*}
\norm{A}_{\calH_{\infty}} = \sup_{z \in \mathbb{C}, \abs{z} = 1} \norm{\paren{zI - A}^{-1}}.
\end{align*}

Let $\delta\in(0,1/2)$. Suppose $t \geq c \tau_{\mathsf{ls}}(K, \norm{x_1}^2, \delta)$ for

\begin{align*}
\tau_{\ls}(K, \bar x, \delta) & \triangleq  \max\bigg\{\sigma^4  \norm{P_K}^3 \Psi_{B^\star}^2 \paren{\dx+\du + \log \frac{1}{\delta}},  \bar x \times \norm{P_K} + 1\bigg\}
\end{align*}

and a sufficiently large universal constant $c>0$. There exists an event $\calE_{\ls}$ which holds with probability at least $1-\delta$ under which the estimation error satisfies

\begin{align*}
&\norm{\hat \Phi \hat \theta  - \Phi^\star \theta^\star}^2 \lesssim \frac{\dtheta \sigma^2  }{t \lambda_{\min} \paren{\bar \Delta^t(\sigma_u, K)}} \log\paren{ \frac{1}{ \delta} } \\
&+ \paren{1+\frac{\sigma^4 \norm{P_K}^7 \Psi_{B^\star}^6 \paren{\dx+\du + \log \frac{1}{\delta}}}{t\lambda_{\min}(\bar \Delta^t(\sigma_u, K))^2 } } \frac{\norm{P_K}^2 \Psi_{B^\star}^2 d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2}{\lambda_{\min}(\bar \Delta^t(\sigma_u, K))} .
\end{align*}

\begin{align*}
\bar \Delta^t(\sigma_u, K) \triangleq \hat \Phi^\top \paren{\frac{1}{t}\sum_{s=0}^{t-2} \sum_{j=0}^s \bmat{I \\ K} A_{K}^j (\sigma_u^2 B^\star \paren{B^\star}^\top + I)   \paren{A_K^j}^\top \bmat{I \\  K}^\top + \bmat{0 & 0 \\ 0 & \sigma_u^2 I_{\du}}} \hat \Phi.
\end{align*}

Toward proving the above theorem, we first define a mapping from the noise sequence and the state $x_1$ to the stacked sequence of states that is be used throughout the section. In particular,

\begin{align}
\label{eq: state sequence}
\bmat{x_1 \\ x_2\\ \vdots \\ x_t} = \left[\begin{array}{c|c} F_1^t(K,\sigma_u) & F_2^t(K,\sigma_u) \end{array} \right]  \left [\begin{array}{c} x_1 \\ \hline \eta_t \end{array} \right],
\end{align}

where $\eta_t \triangleq  \bmat{\bmat{w_1^\top & g_1^\top} & \dots &\bmat{w_{t-1}^\top & g_{t-1}^\top}}^\top$ and

\begin{align*}
\left[\begin{array}{c|c} F_1^t(K,\sigma_u) & F_2^t(K,\sigma_u) \end{array} \right] &\triangleq
\left[\begin{array}{c|cccc} I & 0 & 0 & \dots & 0 \\ A_K & \bmat{ I& B^\star \sigma_u} & 0 &  \dots & 0 \\ \vdots & & \ddots \\ A_K^{t-1} &  A_K^{t-2} \bmat{ I& B^\star \sigma_u}  & \dots & & \bmat{ I & B^\star \sigma_u} \end{array} \right].
\end{align*}

Using the fact that $\bmat{x_t \\ u_t} = \bmat{I \\ K} x_t + \bmat{0 \\ \sigma_u g_t}$, we may express the stacked states and inputs as

\begin{align}
\nonumber
\bmat{x_1 \\ u_1 \\ \vdots \\ x_t \\ u_t} &= \paren{I_{t} \otimes \bmat{I \\ K}} F_1^t(K,\sigma_u) x_1 +  \paren{\paren{I_t \otimes \bmat{I \\ K}} F_2^t(K,\sigma_u)   + \paren{I_t \otimes \bmat{0 & 0 \\ 0 & \sigma_u I_{\du}}}} \eta \\
&\triangleq \Xi_1^t(K,\sigma_u) x_1 + \Xi_2^t(K,\sigma_u) \eta.
\label{eq: state and input sequence}
\end{align}

We additionally define two quantities related to the empirical covariance matrix. In particular, we define the expected value of the empirical covariance matrix conditioned on the state at the start of the sequence, $x_1$, along with the centered counterpart:

\begin{align*}
\Sigma^t(K,\sigma_u,x_1) &\triangleq \E \brac{ \frac{1}{t} \sum_{s=1}^t \bmat{x_s \\ u_s} \bmat{x_s \\ u_s}^\top \vert x_1} \mbox{ and }  \\
\bar \Sigma^t(K,\sigma_u,x_1) &\triangleq \E \brac{ \frac{1}{t} \sum_{s=1}^{t} \paren{\bmat{x_s \\ u_s} - \E \brac{\bmat{x_s \\ u_s} \vert x_1} }\paren{\bmat{x_s \\ u_s} - \E \brac{\bmat{x_s \\ u_s }\vert x_{1} }}^\top}.
\end{align*}

For $t \geq 2$, we have

* $\bar \Sigma^t(K,\sigma_u,x_1) = \frac{1}{t}\sum_{s=0}^{t-2} \sum_{j=0}^s \bmat{I \\ K} A_{K}^j (\sigma_u^2 B^\star \paren{B^\star}^\top +  I)   \paren{A_K^j}^\top \bmat{I \\  K}^\top + \bmat{0 & 0 \\ 0 & \sigma_u^2 I_{\du}}$

* $ \Sigma^t(K,\sigma_u,x_1) = \bar \Sigma_k + \frac{1}{t} \sum_{s=0}^{t-1} \bmat{I \\ K} A_{K}^{s} x_1 x_1^\top \paren{A_K^{s}}^\top \bmat{I \\  K}^\top$

* $\Sigma^t(K,\sigma_u,x_1)  \succeq \bar \Sigma^t(K,\sigma_u,x_1)  \succeq \frac{\sigma_u^2 }{2(1+2\norm{K}^2 + \sigma_u^2)}  I$

* $ \Sigma^t(K,\sigma_u,x_1)  \preceq (1+  \norm{P_K}\frac{\norm{ x_1^2}}{ t-1 }) \bar \Sigma^t(K,\sigma_u,x_1)$

* $\norm{\bar \Sigma^t(K,\sigma_u,x_1)} \leq 5 \norm{P_K}^2  \Psi_{B^\star }^2$.

Points 1 and 2:  These results follow by expressing the states and inputs in terms of the noise sequence and $x_1$, then using the fact that the noise terms are independent, with mean zero and identity covariance.

Point 3: The first inequality is immediate from point one by the fact that

\[
\frac{1}{t} \sum_{s=0}^{t-1} \bmat{I \\ K} A_K^{s} x_1 x_1^\top \paren{A_K^{s}}^\top \bmat{I \\ K}^\top \succeq 0.
\]

For the second inequality, note that

\begin{align*}
\bar \Sigma^t(K,\sigma_u, x_1)&=\frac{1}{t}\sum_{s=0}^{t-2} \sum_{j=0}^s \bmat{I \\ K} A_{K}^j (\sigma_u^2 B^\star \paren{B^\star}^\top + I)   \paren{A_K^j}^\top \bmat{I \\  K}^\top + \bmat{0 & 0 \\ 0 & \sigma_u^2 I_{\du}}  \\
&\succeq \frac{1}{2} \bmat{I \\ K} \bmat{I \\ K}^\top + \bmat{0 & 0 \\ 0 & \sigma_u^2 I_{\du}}.
\end{align*}

By Lemma F.6 of [Dean et al., 2018],

\begin{align*}
\lambda_{\min}\paren{\frac{\sigma_w^2}{2}\bmat{I \\ K} \bmat{I \\ K}^\top + \bmat{0 & 0 \\ 0 & \sigma_u^2 I_{\du}}} \geq  \sigma_u^2 \min\curly{\frac{1}{2}, \frac{1}{4  \norm{K}^2 + 2 \sigma_u^2}}.% \geq \sigma_u^2 \min\curly{\frac{1}{2}, \frac{1}{2 \norm{K}^2 + 2 \sigma_u^2}}
\end{align*}

To conclude, we pull out $\frac{1}{2}$, and we see that $\min\curly{1, \frac{1}{2\norm{K}^2 +\sigma_u^2}} \geq \frac{1}{1+2 \norm{K}^2 + \sigma_u^2}$.

Point 4:  Using the fact that for $vv^\top \preceq \norm{v}^2 I$, we find

\begin{align*}
&\frac{1}{t} \sum_{s=0}^{t-1} \bmat{I \\ K} A_K^{s} x_1 x_1^\top \paren{A_K^{s}}^\top \bmat{I \\ K}^\top \\
&\preceq \norm{x_1}^2 \frac{1}{t} \sum_{s=0}^{t-1} \bmat{I \\ K} A_K^{s} \paren{A_K^{s}}^\top \bmat{I \\ K}^\top \\
& \preceq \norm{x_1}^2 \norm{\sum_{s=0}^{t-1}  A_{K}^{s} \paren{A_{K}^{s}}^\top} \frac{1}{t}  \bmat{I \\ K}\bmat{I \\ K}^\top \\
& \preceq  \frac{\norm{x_{1}^2}}{t-1} \norm{\dlyap[A_K]} \frac{t-1}{t}  \bmat{I \\ K}\bmat{I \\ K}^\top \\
&\preceq  \frac{\norm{x_{1}^2}}{ t-1 } \norm{P_K} \bar \Sigma^t(K,\sigma_u, x_1).% \\
%&\precsim  \frac{\norm{x_{1}^2}}{t-1} \norm{P^\star} \bar \Sigma^t(K,\sigma_u, x_1)
\end{align*}

Point 5:
By the fact that $\sigma_u^2 \leq 1$ we have from the triangle inequality and submultiplicativity that

\begin{align*}
\norm{\bar \Sigma^t(K,\sigma_u, x_1)} &= \norm{ \frac{1}{t-1}\sum_{s=0}^{t-2} \sum_{j=0}^s \bmat{I \\ K} A_{K}^j (\sigma_u^2 B^\star \paren{B^\star}^\top +   I)   \paren{A_K^j}^\top \bmat{I \\  K}^\top + \bmat{0 & 0 \\ 0 & \sigma_u^2 I_{\du}}} \\
&\leq 1 + \paren{1 + \norm{K}^2} \paren{\norm{B^\star}^2 + 1 } \norm{\frac{1}{t}\sum_{t=0}^{t-2}\sum_{j=0}^t A_K^j    \paren{A_K^j}^\top} \\
&\leq 1 + \paren{1 + \norm{K}^2} \paren{\norm{B^\star}^2 + 1} \norm{\sum_{j=0}^\infty A_K^j    \paren{A_K^j}^\top}\\
&= 1 + \paren{1 + \norm{K}^2} \paren{\norm{B^\star}^2 + 1} \norm{\dlyap[A_K]} \\
&\leq 1 + \paren{1 + \norm{K}^2} \paren{\norm{B^\star}^2 + 1} \norm{P_K} \\
& \leq  5 \norm{P_K}^2  \Psi_{B^\star }^2,
\end{align*}

where the final point follows from the fact that $\norm{K}^2 \leq \norm{Q+ K^\top R K} \leq \norm{P_K}$, $\norm{P_K}\geq 1$, and the definition of $\Psi_{B^\star }$.

To analyze the estimate $\hat \theta$, we first verify that it solves the least squares problem of interst.

Consider applying <Ref> to an estimated model structure $\hat \Phi$, state data $x_{ 1:t+1}$ and input data $u_{ 1: t}$: $\hat \theta , \Lambda  = LS(\hat \Phi, x_{ 1:t+1}, u_{1:t})$. As long as
$  \Lambda   \succ 0,$ then $\hat \theta $ is the unique solution to

\begin{align}
\label{eq: ls problem}
\argmin_{\theta} \sum_{s=1}^{t} \norm{x_{s+1} - \VEC^{-1}(\hat \Phi \theta) \bmat{x_s \\ u_s}}^2.
\end{align}

By the vectorization identity $\VEC(XYZ) = (Z^\top \otimes X)\VEC(Y)$, we may write

\begin{align*}
\VEC^{-1}(\hat \Phi \theta) \bmat{x_s \\ u_s} = \paren{\bmat{x_s \\ u_s}^\top \otimes I_{\dx} }\hat \Phi \theta.
\end{align*}

Minimizing $
\sum_{s= 1}^{t} \norm{x_{s+1} - \paren{\bmat{x_s \\ u_s}^\top \otimes I_{\dx}}\hat \Phi \theta }^2$
over $\theta$ yields $\hat \theta $.

We now split the estimation error into a part arising from the variance and a part arising from the bias. The variance decays as $t$ grows sufficiently large. The bias is due to the misspecificiation between the model structure estimate $\hat \Phi$ and the true model structure $\Phi^\star$.

Consider applying <Ref> to an estimated model structure $\hat \Phi$, state data $x_{1:t+1}$ and input data $u_{1:t}$: $\hat \theta, \Lambda = LS(\hat \Phi, x_{1:t+1}, u_{1:t})$. Suppose that $\Lambda \succ 0$. Let

\begin{align}
\label{eq: optimal projection}
\bar \theta = \argmin_{\theta} (\hat \Phi \theta - \Phi^\star \theta^\star)^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} (\hat \Phi \theta - \Phi^\star\theta^\star).
\end{align}

We have that

\begin{align}
\label{eq: bias variance decomposition}
\norm{\hat \Phi \hat \theta - \Phi^\star \theta^\star}^2 \leq \underbrace{2 \norm{\hat \Phi \hat \theta - \hat \Phi \bar \theta}^2}_{\mbox{variance}} + \underbrace{2 \norm{\hat \Phi \bar \theta - \Phi^\star \theta^\star}^2}_{\mbox{bias}}.
\end{align}

The lemma folllows by application of the triangle inequality.

The variance term in the above lemma is bounded in <Ref>, while the bias term is bounded in <Ref>. Before presenting these lemmas, we present several covariance concentration guarantees that will be useful in obtaining presenting the variance bound.

§.§ Covariance Concentration

The following $\varepsilon$-net argument is standard. A proof may be found in Chapter 4 of [Vershynin, 2020].

Let $W$ be and $d\times d $ random matrix, and $\varepsilon \in [0, 1/2)$. Furthermore, let $\calN$ be an $\varepsilon$-net of $\calS^{d-1}$

with minimal cardinality. Then for all $\rho > 0$,

\[
\P\brac{\norm{W} > \rho} \leq \paren{\frac{2}{\varepsilon} + 1}^d \max_{x \in \calN} \P\brac{\abs{x^\top W x} > (1-2\epsilon)\rho}.
\]

The following lemma helps to bound system constants in term of a few key quantities.

For a stabilizing controller $K$, we have that for any $t$, $\norm{A_K^t} \leq \sqrt{\paren{1 - \frac{1}{\norm{P_K}}}^t \norm{P_K}}$ and $\sum_{t=0}^\infty \norm{A_K^t} \leq 2 \norm{P_K}^{3/2}$. As a consequence, we also have $\norm{A_K}_{\calH_\infty} \leq 2 \norm{P_K}^{3/2}$.

For the first point, observe that

\begin{align*}
\norm{A_K^t} &= \sqrt{\norm{(A_K^t)^\top A_K^t}} \leq \sqrt{\norm{(A_K^t)^\top P_K A_K^t}}  \leq \sqrt{\paren{1 - \frac{1}{\norm{P_K}}}^t \norm{P_K}}.
\end{align*}

For we may use the first point to show that

\begin{align*}
\sum_{t=0}^\infty \norm{A_K^t}
&\leq \norm{P_K}^{1/2} \sum_{t=0}^\infty \paren{\sqrt{1-\frac{1}{\norm{P_K}}}}^t \\ & = \norm{P_K}^{1/2} \frac{1}{1-\sqrt{1 - \frac{1}{\norm{P_K}}}} \\
&= \norm{P_K}^{1/2} \frac{1 + \sqrt{1 - \frac{1}{\norm{P_K}}}}{1/\norm{P_K}} \\&\leq 2 \norm{P_K}^{3/2}.
\end{align*}

The result on the $\calH_\infty$ norm of $A_K$ follows from the previous point by noting that $\norm{A_K}_{\calH_\infty} \leq \sum_{t=0}^\infty \norm{A_K^t}$.

We now a result about the concentration of the empirical covariance to the true covariance. The result is adapted from Lemma 2 of [Jedra and Proutiere, 2020] and Lemma A.2 of [Zhang et al., 2023], which generalized the approximate isometries argument in [Jedra and Proutiere, 2020] to account for projecting the covariance onto a lower dimensional space by hitting it on either side with a low rank orthonormal matrix. The primary difference of the below result from that in [Zhang et al., 2023] is the inclusion of a nonzero initial state, resulting in an additional sub-gaussian concentration step.

Let data $x_{1:t}$, $u_{1:t}$ be generated by (<ref>).
Let $G \in \R^{\dc (\dx+\du)\times d_G}$ be a matrix with orthonormal columns. Define

\begin{align*}
M \triangleq\paren{G^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dc}} G}^{-1/2}.
\end{align*}

Then for some positive universal constant $C$, and for any $\rho<1$, the inequality

\begin{align*}
\norm{M G^\top \paren{\frac{1}{\tau_{k-1}} \sum_{t=\tau_{k-1}}^{\tau_k - 1} \bmat{x_t \\ u_t} \bmat{x_t \\ u_t}^\top \otimes I_{\dc}} G M - I} > \rho
\end{align*}

holds with probability at most

\begin{align*}4 \times 9^{d_G} \exp\paren{-C \frac{ \min\curly{\rho,\rho^2} t}{\sigma^4 \norm{P_K}^3  \Psi_{B^\star}^2}},
\end{align*}

Define the shorthand

\[
X \triangleq \frac{1}{\sqrt{t}} \bmat{x_1^\top & u_1^\top \\ \vdots & \vdots \\ x_t^\top  & u_t^\top } \otimes I_{\dc}
\]

such that

\[
\paren{\frac{1}{t} \sum_{s=1}^{t} \bmat{x_s \\ u_s} \bmat{x_s \\ u_s}^\top \otimes I_{\dc}} =  X^\top X.
\]

First note that $\E\brac{G^\top X^\top X G \vert x_1} = M^{-2}$.

\begin{align}
\label{eq: quadratic form quantity of interest}
\norm{M G^\top X^\top X G M - I}
&= \sup_{v \in \calS^{d_G}} \abs{v^\top \paren{M G^\top X^\top X G M - I}v }\\
\nonumber
&= \sup_{v \in \calS^{d_G}} \abs{v^\top M G^\top X^\top X G M v - \E \brac{v^\top M G^\top X^\top X G M v \vert x_1  } } \\
\nonumber
&= \sup_{v \in \calS^{d_G}} \abs{ \norm{X G M v}^2 - \E \brac{\norm{X G Mv}^2 \vert x_1 }}.
\end{align}

Using the identity $\VEC(WYZ) = (Z^\top \otimes W) \VEC(Y)$, we may write

\begin{align}
\label{eq: vectorizing quadratic form}
\VEC\paren{v^\top M^\top G^\top X^\top} &= (I_{t \times \dx}\otimes (G M v)^\top ) \VEC(X^\top ) \triangleq \sigma_{GM v}  \VEC(X^\top ).
\end{align}

Next, we construct matrices $\Gamma_1^t(K,\sigma_u)$ and $\Gamma_2^t(K,\sigma_u)$ such that $\VEC(X^\top)=\Gamma_1^t(K,\sigma_u) x_1 + \Gamma_2^t(K,\sigma_u) \eta_t$.
To construct these matrices, first recall the definition of $\Xi_1^t(K,\sigma_u)$ and $\Xi_2^t(K,\sigma_u)$ given in (<ref>) and of $F_1^t(K,\sigma_u)$ and $F_2^t(K,\sigma_u)$ given in (<ref>). To reach $\VEC\paren{X^\top} $ from the vector of stacked states and inputs, we can apply the following transformation:

\begin{align*}
\VEC(X^\top) = \frac{1}{\sqrt{t}} \paren{I_t \otimes \bmat{I_{\dx+\du} \otimes e_1 \\ \vdots \\I_{\dx + \du} \otimes e_{\dc}}}   \bmat{x_1 \\ u_1 \\ \vdots \\ x_t \\ u_t} \triangleq \frac{1}{\sqrt{t}} H\bmat{x_1 \\ u_1 \\ \vdots \\ x_t \\ u_t}.
\end{align*}

Combining the above sequence of transformation implies that by defining $ \Gamma_1^t(K,\sigma_u) \triangleq \frac{1}{t} H \Xi_1^t(K,\sigma_u)$ and $\Gamma_2^t(K,\sigma_u) \triangleq \frac{1}{t}H \Xi_2^t(K,\sigma_u)$, we have $\VEC(X^\top)=\Gamma_1 x_1 + \Gamma_2^t(K,\sigma_u) \eta_t$.

Using the above expression, our quantity of interest in (<ref>) may be expressed as

\begin{align*}
&\norm{M G^\top X^\top X G M - I}  \\
&=\sup_{v \in \calS^{d_G}} \abs{\norm{\sigma_{GM v} \paren{\Gamma_1^t(K,\sigma_u) x_1  + \Gamma_2^t(K,\sigma_u) \eta_t}}^2
-\E \brac{ \norm{\sigma_{GM v} \paren{\Gamma_1^t(K,\sigma_u) x_1  + \Gamma_2^t(K,\sigma_u) \eta_t}}^2 \vert x_1}} \\
&=  \sup_{v \in \calS^{d_G}} \Big|\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2  + \norm{ \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1}^2  + 2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle\\
&\quad  -\E \brac{ \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2  + \norm{ \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1}^2 + 2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle \vert x_1} \Big| \\
&\overset{(i)}{=} \sup_{v \in \calS^{d_G}} \abs{\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u \eta_t}^2  + 2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u \eta_t \rangle  -\E \brac{ \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2 }} \\
&\overset{(ii)}{=} \sup_{v \in \calS^{d_G}} \abs{\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2  + 2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle  - \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) }_F^2}\\
&\leq  \sup_{v \in \calS^{d_G}} \underbrace{\abs{\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2   - \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) }_F^2}}_{\mbox{quadratic form concentration}} +\underbrace{\abs{2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle}}_{\mbox{cross term}}
\end{align*}

where $(i)$ follows from linearity of expectation and the substition rule of conditional expectation, combined with the fact that $\eta$ has mean zero and is independent of $x_1$. Equality $(ii)$ follows from the fact that $\eta_t$ is mean zero with identity covariance.

To bound the concentration of the quadratic form, we invoke Theorem 6.3.2 of [Vershynin, 2020]. In particular, there exists a universal constant $C>0$ such that

\begin{equation}
\label{eq: quadratic form concentration}
\begin{aligned}
&\Pr\brac{\abs{\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2   - \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) }_F^2} \geq \frac{\rho}{2}} \\
&\qquad \leq 2 \exp\paren{-C \frac{\min\curly{\rho^2/\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}_F^2, \rho}}{\sigma^4 \norm{\sigma_{GM_k v} \Gamma_2^t(K,\sigma_u)}^2 }}.
\end{aligned}
\end{equation}

For the cross term, we invoke a standard sub-Gaussian tail bound [Vershynin, 2020] to show that for any fixed $v \in \calS^{d_G}$,

\begin{equation}
\begin{aligned}
\label{eq: cross term concentration}
&\Pr\brac{\abs{2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle} > \frac{\rho}{2}} \\
&\qquad \leq 2 \exp\paren{-\frac{1}{16} \rho^2 \frac{1}{\sigma^2 \norm{\Gamma_2^t(K,\sigma_u)^\top  \sigma_{GM v}^\top  \sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1 }^2}}.
\end{aligned}
\end{equation}

We now seek to simplify the denominators appearing in the exponents for each of the probability bounds above. First,  note that we have

\begin{align*}
& \norm{\sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1 }^2 + \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}_F^2 \\
&= \trace\paren{\sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1x_1^\top \Gamma_1^t(K,\sigma_u)^\top \sigma_{GM v}^\top } + \trace\paren{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)  \Gamma_2^t(K,\sigma_u)^\top \sigma_{GM v}^\top} \\
&= \trace\paren{\sigma_{GM v} \paren{\Gamma_1^t(K,\sigma_u) x_1x_1^\top \Gamma_1^t(K,\sigma_u)^\top  + \Gamma_2^t(K,\sigma_u)  \Gamma_2^t(K,\sigma_u)^\top } \sigma_{GM v}^\top } \\
%&\overset{(i)}{=} \E \brac{\trace\paren{\sigma_{GM v} \paren{\Gamma_1^t(K,\sigma_u) x_1x_1^\top \Gamma_1^t(K,\sigma_u)^\top + \sym\paren{\Gamma_1^t(K,\sigma_u) x_1\eta_t^\top \Gamma_2^t(K,\sigma_u)^\top}  + \Gamma_2^t(K,\sigma_u) \eta_t \eta^_t\top \Gamma_2^t(K,\sigma_u)^\top } \sigma_{GM v}^\top } \vert x_1} \\
&=  \E \brac{\trace\paren{\sigma_{GM v} \VEC(X^\top) \VEC(X^\top)^\top  \sigma_{GM v}^\top }\vert x_1 },
\end{align*}

where the final equality follows from the fact that $\eta_t$ is mean zero with identity covariance and independent form $x_1$ combined with the construction of $\Gamma_1^t(K,\sigma_u)$ and $\Gamma_2^t(K,\sigma_u)$. Employing the identity in (<ref>), we find

\begin{align*}
\E \brac{\trace\paren{\sigma_{GM v} \VEC(X^\top) \VEC(X^\top)^\top  \sigma_{GM v}^\top }\vert x_1} =  \E \brac{ v^\top M G^\top X^\top X G M v\vert x_1} = 1,
\end{align*}

where the final equality follows by the definition of $M$ and the fact that $\norm{v}^2=1$. The above computations provide identity $
\norm{\sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1 }^2 + \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}_F^2  = 1.$
We therefore have $
\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}_F^2  \leq 1$ and $\norm{\sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1 }^2 \leq 1$.
As a result, the quantity in the denominator of the exponential in (<ref>) is bounded as

\begin{align*}
\norm{\Gamma_2^t(K,\sigma_u)^\top  \sigma_{GM v}^\top  \sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1 } & \leq  \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)} \norm{\sigma_{GM v} \Gamma_1^t(K,\sigma_u) x_1 } {\leq}   \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}.
\end{align*}

Therefore, the probability bounds in (<ref>) and (<ref>) may be modified to read

\begin{align*}
\Pr\brac{\abs{\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2   - \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) }_F^2} \geq \frac{\rho}{2}} &\leq 2 \exp\paren{-C \frac{\min\curly{\rho, \rho^2}}{\sigma^4 \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}^2}} \\
\Pr\brac{\abs{2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle} > \frac{\rho}{2}} &\leq 2 \exp\paren{-\frac{1}{16} \rho^2 \frac{1}{\sigma^2 \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}^2}}.
\end{align*}

Union bounding over the above two events, and using the assumption that $\sigma^2 \geq 1$ implies that for some universal constant $C > 0$,

\begin{align*}
&\Pr\brac{\abs{\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t}^2   - \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u) }_F^2} + \abs{2 \langle \sigma_{GM v} \Gamma_1^t(K,\sigma_u)  x_1, \sigma_{GM v} \Gamma_2^t(K,\sigma_u) \eta_t \rangle} > \rho } \\
&\leq 4 \exp\paren{-C\frac{\min\curly{\rho, \rho^2}}{\sigma^4 \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}^2}}.
\end{align*}

We may now invoke the covering argument in <Ref> with $\varepsilon=\frac{1}{4}$ to show that there exists a universal positive constant $C$ such that

\begin{align}
\label{eq: prob bound on QI}
&\Pr\brac{\norm{M G^\top X^\top X G M - I} > \rho} \leq 4 \times 9^{d_G} \exp\paren{-C  \frac{\min\curly{\rho,\rho^2}}{\sigma^4 \norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}^2}}.
\end{align}

To conclude, we must bound the term $\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)}$. To do so, we write

\begin{align*}
\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)} &= \frac{1}{t}\norm{\sigma_{GM v} H \Xi_2^t(K,\sigma_u)} \\
&= \frac{1}{\sqrt{t}}\norm{\sigma_{GM v} H \paren{\paren{I_t \otimes \bmat{I \\ K}} F_2^t(K,\sigma_u)   + \paren{I_t \otimes \bmat{0 & 0 \\ 0 & \sigma_u I_{\du}}}} } \\
&\leq \frac{1}{\sqrt{t}}\paren{\underbrace{\norm{\sigma_{GM v} H \paren{I_t \otimes \bmat{I \\  K}} F_2^t(K,\sigma_u)}}_{\mbox{state term}} + \underbrace{\norm{ \sigma_{GM v} H \paren{I_t \otimes \bmat{0 & 0 \\ 0 & \sigma_u I_{\du}}}}}_{\mbox{input noise term}} }.
\end{align*}

For the state term, we have

\begin{align*}
\norm{\sigma_{GM v} H \paren{I_t \otimes \bmat{I \\ K}} \Psi_1} \leq \norm{\sigma_{GM v} H \paren{I_t \otimes \bmat{I \\ K}}} \norm{F_2^t(K,\sigma_u)}.
\end{align*}

The second term quantifies the system's amplification of an exogenous input, and is bounded by the $\calH_\infty$ norm of the system $\norm{\left[\begin{array}{c|c} A_K & \bmat{  I & \sigma_u B^\star} \end{array}\right]}_{\calH_\infty}$ <cit.>. This, in turn,  is bounded by the $\calH_\infty$ norm of the matrix $A_K$ multiplied by the spectral norm of the input matrix, yielding

\begin{align*}
\norm{F_2^t(K,\sigma_u)} \leq \norm{A_K}_{\calH_\infty} \paren{ \norm{B^\star} + 1} % \leq 4 \norm{P^\star}^{3/2} \paren{1 + \norm{B^\star}} \leq 4 \norm{P^\star}^{3/2} \Psi_{B^\star}.
\end{align*}

We may bound the first quantity as

\begin{align*}
&\norm{\sigma_{GM v} H \paren{I_t\otimes \bmat{I \\ K}}} \\
&=\norm{(I_{t \times \dc} \otimes (G M v)^\top ) \paren{I_t \otimes \bmat{I_{\dx+\du} \otimes e_1 \\ \vdots \\I_{\dx + \du} \otimes e_{\dc}}} \paren{I_t \otimes \bmat{I \\ K}}} \\
&\overset{(i)}{=} \norm{(I_{\dc} \otimes (G M v)^\top )  \bmat{I_{\dx+\du} \otimes e_1 \\ \vdots \\I_{\dx + \du} \otimes e_{\dc}}  \bmat{I \\ K}} \\
&\overset{(ii)}{=} \sup_{w \in \calS^{\dx}} \norm{(I_{\dc} \otimes (G M v)^\top )  \bmat{I_{\dx+\du} \otimes e_1 \\ \vdots \\I_{\dx + \du} \otimes e_{\dc}}  \bmat{I \\ K}w} \\
&\overset{(iii)}{=} \sup_{w \in \calS^{\dx}} \norm{\VEC v^\top M G^\top \VEC^{-1} \paren{\bmat{I_{\dx+\du} \otimes e_1 \\ \vdots \\I_{\dx + \du} \otimes e_{\dc}}  \bmat{I \\ K}w}} \\
&\overset{(iv)}{=}\sup_{w \in \calS^{\dx}} \norm{\VEC v^\top M G^\top\paren{\paren{\bmat{I \\ K}w} \otimes I_{\dc}}}
\end{align*}

where $(i)$ follows by the following kronecker product identities: $I_{a + b} \otimes W = I_a \otimes \paren{I_b \otimes W}$, $(A \otimes B)(C \otimes D) = AC \otimes BD$, and $\norm{I \otimes W} = \norm{W}$. Equality $(ii)$ follows by definition of the operator norm, and equality $(iii)$ follows by the vectorization identity $\VEC(WYZ) = (Z^\top \otimes W) \VEC(Y) $. Equality $(iv)$ follows by the definition of the inverse vectorization operation.  The quantity in the norm above may now be written as the inner product of a vector with itself. In particular, we have

\begin{align*}
&\sup_{w \in \calS^{\dx}} \norm{\VEC v^\top M G^\top\paren{\paren{\bmat{I \\K}w} \otimes I_{\dc}}} \\  &=\sup_{w \in \calS^{\dx}} \sqrt{ v^\top M G^\top\paren{\paren{\bmat{I \\ K}ww^\top \bmat{I \\K}^\top} \otimes I_{\dc}} GM v }\\
&\overset{(i)}{\leq}\sup_{w \in \calS^{\dx}} \sqrt{ v^\top M G^\top\paren{\paren{\bmat{I \\ K} \bmat{I \\ K}^\top} \otimes I_{\dc}} GM v } \\
&\overset{(ii)}{\leq} 2 \sup_{w \in \calS^{\dx}} \sqrt{ v^\top M G^\top\paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dc}} GM v }\leq 2,
\end{align*}

where inequality $(i)$ follows by the fact that $ww^\top \preceq I$, and inequailty $(ii)$ follows from the fact that $\bmat{I \\K}\bmat{I \\ K}^\top \preceq 2 \Sigma^t(K,\sigma_u,x_1)$, as may be verified by examining the expression for $\bar \Sigma^t(K,\sigma_u,x_1)$ in <Ref>.
We may similarly show that the input term is bounded by one:

\begin{align*}
\norm{ \sigma_{GM v} H \paren{I_t \otimes \bmat{0 & 0 \\ 0 & \sigma_u I_{\du}}}} \leq 1.
\end{align*}

Combining results we have the bound $\norm{\sigma_{GM v} \Gamma_2^t(K,\sigma_u)} \leq \frac{1}{\sqrt{t}} \paren{1 + 2 \norm{F_2^t(K,\sigma_u)}} \leq \frac{5}{  \sqrt{t}} \norm{P_K}^{3/2} \Psi_{B^\star,\sigma_w}$, where we used the result of <Ref> to bound $\norm{A_K}_{\calH_\infty}$ in terms of $\norm{P_K}$. Substituting this result into the bound in (<ref>), we find that for some universal constant $C$,

\begin{align*}
\Pr\brac{\norm{M G^\top X^\top X G M - I} > \rho} \leq 4 \times 9^{d_G} \exp\paren{-C \frac{d \min\curly{\rho,\rho^2} t}{\sigma^4 \norm{P_K}^3  \Psi_{B^\star }^2}},
\end{align*}

which concludes our proof.

For a sufficiently large universal positive constant $c$, we have that as long as $t \geq c \sigma^4 \norm{P_K}^3 \Psi_{B^\star}^2 \paren{ \dtheta + \log\frac{1}{\delta}}$, the event

\begin{align*}
\calE_{\mathsf{conc}} = \curly{\frac{1}{2} \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \preceq \frac{1}{t} \sum_{s=1}^{t} \hat \Phi^\top \paren{\bmat{x_s \\ u_s}\bmat{x_s \\ u_s}^\top \otimes I_{\dx}} \hat \Phi \preceq 2 \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}
\end{align*}

holds with probability at least $1-\frac{\delta}{2}$.

The result follows by invoking <Ref> with $G\gets \hat \Phi$ and $\rho \gets \frac{1}{2}$. We invert the probability bound by setting $
\frac{\delta}{2} = 4 \times 9^{\dtheta} \exp\paren{- C \frac{t}{\sigma^4 \norm{P_K}^3 \Psi_{B^\star}^2}}.$
As long as $t\geq c \sigma^4 \norm{P_K}^3 \Psi_{B^\star}^2 \paren{ \dtheta + \log\frac{1}{\delta}}$
for a sufficiently large universal  constant $c>0$, the event holds with probability at least $1-\frac{\delta}{2}$.

§.§ Self-Normalized Martingales

To present the self-normalized martingale bound we first recall the definitions of a filtration and an adapted process.

(Filtration and Adapted Process)
A sequence of sub-$\sigma$-algebras $\curly{\calF_s}_{s=1}^t$ is said to be a filtration if $\calF_s \subseteq \calF_k$ for $s\leq k$. A stochastic process $\curly{w_s}_{s=1}^t$ is said to be adapted to the filtration $\curly{\calF_s}_{s=1}^t$ if for all $s\geq 1$, $w_s$ is $\calF_s$-measurable.

The following theorem is a modification of Theorem 3.4 in [Abbasi-Yadkori and Szepesvári, 2011] and is a consequence of Lemma 14.7 in [Peña et al., 2009].

Let $\curly{\calF_s}_{s=0}^{t}$ be a filtration and let $\curly{z_s}_{s=1}^t$ be a matrix valued stochastic process assuming values in $\R^{\dx \times \dtheta}$ which is adapted to $\curly{\calF_{s-1}}_{s=1}^t$ and $\curly{w_s}_{s=1}^t$ a vector valued stochastic process assuming values in $\R^{\dx}$ which is adapted to $\curly{\calF_s}_{s=1}^t$. Additionally suppose that for all $ 1\leq s \leq  t$, $w_t$ is $\sigma^2$-conditionally sub-Gaussian with respect to $\calF_s$. Let $\Sigma$ be a positive definite matrix in $\R^{\dtheta\times\dtheta}$. Then for $\delta \in (0,1)$, the following inequality holds with probability at least $1-\delta$:

\begin{align*}
\norm{\paren{ \Sigma + \sum_{s=1}^t z_s^\top z_s}^{-1/2} \sum_{s=1}^t z_s^\top w_s}^2 \leq \sigma^2 \log\paren{\frac{\det\paren{\Sigma + \sum_{s=1}^t z_s^\top z_s}}{\det(\Sigma)}} + 2 \sigma^2 \log\frac{1}{\delta}.
\end{align*}

The proof follows by applying Lemma 4.1 from [Ziemann et al., 2023] with $P \gets \sum_{s=1}^t \frac{z_s^\top w_s}{\sigma}$ and $Q \gets \sum_{s=1}^t z_s^\top z_s$. To verify the conditions for this lemma to hold, we must verify that

\max_{\lambda \in \R^{\dtheta}} \E \exp \paren{\lambda^\top P - \frac{1}{2}\lambda^\top Q \lambda} \leq 1.

To verify this condition, we define the quantity

\begin{align*}
M_s(\lambda) \triangleq \exp\paren{\sum_{k=1}^{s} \brac{\frac{\lambda^\top z_k^\top w_k}{\sigma} - \frac{1}{2} \lambda^\top z_k^\top z_k \lambda}}.
\end{align*}

Observe that for any $\lambda\in\R^{\dtheta}$, $M_0(\lambda) = 1$. For any $0 < s \leq t$,

\begin{align*}
\E M_s(\lambda) &= \E \E \paren{M_s(\lambda \vert \calF_s} = \E \paren{M_{s-1}(\lambda) \E\paren{\exp\paren{\frac{\lambda\top z_s^\top w_s}{\sigma} - \frac{1}{2} \lambda^\top z_s^\top z_s \lambda} \vert \calF_s}}.
\end{align*}

Note that by the fact that $w_s$ is $\sigma^2$-conditionally sub-Gaussian with respect to $\calF_s$,

\begin{align*}
\E\paren{\exp\paren{\frac{\lambda^\top z_s^\top w_s}{\sigma} - \frac{1}{2} \lambda^\top z_s^\top z_s \lambda} \vert \calF_t} &= \E\paren{\exp\paren{\frac{\lambda^\top z_s^\top w_s}{\sigma}\vert \calF_s}} \exp\paren{ - \frac{1}{2} \lambda^\top z_s^\top z_s \lambda} \\
&\leq \exp\paren{\lambda^\top z_s^\top z_s \lambda}\exp\paren{ - \frac{1}{2} \lambda^\top z_s^\top z_s \lambda} = 1.
\end{align*}

Therefore $\E M_t \leq \E M_{t-1}(\lambda) \leq \dots \leq  \E M_{1}(\lambda)\leq \E M_0(\lambda) =  1$, which verifies the requisite condition.

§.§ Variance Bound

Let $\Sigma \in \R^{\dtheta\times\dtheta}$ be positive definite. Suppose data $x_{1:t+1}, u_{1:t}$ is generated by (<ref>). Consider generating the least squares estimate $\hat \theta, \Lambda = \texttt{LS}(\hat \Phi, x_{1:t+1}, u_{1:t})$. Suppose that $\Lambda \succeq \Sigma$. There exists an event $\calE_{\mathsf{var}}$ that holds with probability at least $1-\delta/2$ under which the variance satisfies

\begin{align*}
&\norm{\hat \Phi \hat \theta - \hat \Phi \bar \theta}^2 \lesssim \frac{\sigma^2}{\lambda_{\min}(\Sigma)} \log\paren{ \frac{\det(\Sigma+\Lambda)}{\det(\Sigma) \delta^2} }+  \frac{\mathrm{Conc}_{\mathsf{cov}}(\delta)^2}{\lambda_{\min}(\Sigma)^2} \norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta}^2,
\end{align*}

\begin{align*}
\mathrm{Conc}_{\mathsf{cov}}(\delta) = \norm{\Sigma^t(K,\sigma_u,x_1)} \max \bigg\{&\sqrt{t}  \sigma^2  \norm{P_K}^{3/2} \Psi_{B^\star} \sqrt{\dx+\du + \log \frac{1}{\delta}}, \\
&\sigma^4  \norm{P_K}^3 \Psi_{B^\star}^2 \paren{\dx+\du + \log \frac{1}{\delta}} \bigg\}.
\end{align*}

By <Ref>, $\hat \theta$ solves (<ref>). Therefore,

\begin{align*}
\sum_{s=1}^t \norm{x_{s+1} - \VEC^{-1}(\hat \Phi \hat \theta) \bmat{x_s \\ u_s}}^2 \leq \sum_{s=1}^{t} \norm{x_{s+1} - \VEC^{-1}(\hat \Phi \bar \theta) \bmat{x_s \\ u_s}}^2.
\end{align*}

Inserting $x_{s+1} = \VEC^{-1} (\Phi^\star \theta^\star) \bmat{x_s \\ u_s} + w_s$, we may rearrange the above inequality to read

\begin{align*}
&\sum_{s=1}^t \norm{\VEC^{-1} \paren{\hat \Phi \bar \theta - \hat \Phi \hat \theta}\bmat{x_s \\ u_s}}^2 \leq  \\
&2 \sum_{s=1}^t\bigg \langle \VEC^{-1}\paren{ \hat \Phi \paren{\hat \theta - \bar \theta}}\bmat{x_s \\ u_s}, \VEC^{-1} \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta}\bmat{x_s \\ u_s} \bigg\rangle \\
&+ 2 \sum_{s=1}^t \bigg\langle \VEC^{-1}\paren{ \hat \Phi \paren{\hat \theta - \bar \theta}}\bmat{x_s \\ u_s}, w_s \bigg \rangle.
\end{align*}

Multiplying the above inequality by two, and bringing one of the sums from the right side to the left leaves us with

\begin{equation}
\label{eq: variance decomposition}
\begin{aligned}
&\sum_{s=1}^t \norm{\VEC^{-1} \paren{\hat \Phi \bar \theta - \hat \Phi \hat \theta}\bmat{x_s\\ u_s}}^2 \leq \\
&\underbrace{4 \sum_{s=1}^t\bigg \langle \VEC^{-1}\paren{ \hat \Phi \paren{\hat \theta - \bar \theta}}\bmat{x_s \\ u_s}, \VEC^{-1} \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta}\bmat{x_s \\ u_s} \bigg\rangle}_{\mbox{variance from misspecification}} \\
&+ \underbrace{4 \sum_{s=1}^t \bigg\langle \VEC^{-1}\paren{ \hat \Phi \paren{\hat \theta - \bar \theta}}\bmat{x_s \\ u_s}, w_s \bigg \rangle - \sum_{s=1}^t \norm{\VEC^{-1} \paren{\hat \Phi (\bar \theta  -\hat \theta)}\bmat{x_s \\ u_s}}^2 }_{\mbox{self-normalized process}}.
\end{aligned}
\end{equation}

Bound on Self-normalized Process:  We first bound the self-normalized process above. To simplify notation, we denote $z_s = \paren{\bmat{x_s \\ u_s}^\top \otimes I_{\dx}} \hat \Phi$. By using the identity $\VEC(XYZ) = (X^\top \otimes Z) \VEC(Y)$, we may therefore write the self-normalized process term above as

\begin{align*}
4  \sum_{s=1}^t \bigg\langle z_t (\hat \theta - \bar \theta ), w_s \bigg \rangle - \sum_{s=1}^t\norm{z_s (\bar \theta   -\hat \theta )}^2 &\leq \sup_{\theta}  \curly{4 \sum_{s=1}^t \bigg\langle z_s \theta, w_s \bigg \rangle - \sum_{s=1} ^t \norm{z_s \theta}^2} = 4\norm{\Lambda ^{-1/2} \sum_{s=1}^t z_s^\top w_s}^2.
\end{align*}

Using the lower bound $\Lambda  \succeq \Sigma$, we have

\begin{align*}
4 \norm{\Lambda ^{-1/2} \sum_{s=1}^t z_t^\top w_s}^2 \leq 8
\norm{\paren{\Lambda +\Sigma}^{-1/2} \sum_{s=1}^t z_s^\top w_s}^2.
\end{align*}

Invoking the self-normalized martingale bound in <Ref> we find that there exists an event $\calE_{\mathsf{noise}}$ that holds with probability at least $1-\delta/4$ such that under the event $\calE_{\mathsf{noise}}$,

\begin{align*}
\norm{\paren{\Lambda  + \Sigma}^{-1/2} \sum_{s=1}^t z_s^\top w_s}^2 \leq \sigma^2 \log\paren{ \frac{ 16 \det(\Sigma+\Lambda) }{\det(\Sigma) \delta^2} }.
\end{align*}

Bound on Variance from misspecification:
We now proceed to bound the term in (<ref>) arising due to variance from the model mispecification. To do so, note that

\begin{align*}
&\sum_{s=1}^t\bigg \langle \VEC^{-1}\paren{ \hat \Phi \paren{\hat \theta   - \bar \theta }}\bmat{x_s \\ u_s}, \VEC^{-1} \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta  }\bmat{x_s \\ u_s} \bigg\rangle \\
&= \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^\top \paren{\sum_{s=1}^t \paren{\bmat{x_s\\ u_s} \bmat{x_s \\ u_s}^\top \otimes I_{\dx}}} \paren{\hat \Phi (\hat \theta  - \bar \theta )} \\
&= t \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \paren{\hat \Phi (\hat \theta - \bar \theta)} \\
&+ \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^\top \paren{\paren{\sum_{s=1}^t\bmat{x_s\\ u_s} \bmat{x_s \\ u_s}^\top - t \Sigma^t(K,\sigma_u,x_1)} \otimes I_{\dx}}\paren{\hat \Phi (\hat \theta - \bar \theta)}.
\end{align*}

By the optimality of $\bar \theta$ in (<ref>),

\[
\paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^\top \paren{\sum_{s=1}^t \paren{\Sigma^t(K,\sigma_u) \otimes I_{\dx}}} \paren{\hat \Phi (\hat \theta  - \bar \theta )} = 0.
\]

Therefore, we are left with

\begin{align*}
& \sum_{s=1}^t\bigg \langle \VEC^{-1}\paren{ \hat \Phi \paren{\hat \theta  - \bar \theta }}\bmat{x_s \\ u_s}, \VEC^{-1} \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta }\bmat{x_s \\ u_s} \bigg\rangle \\
&=  \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta_k}^\top \paren{\paren{\sum_{s=1}^t\bmat{x_s\\ u_s} \bmat{x_s \\ u_s}^\top - t \Sigma^t(K,\sigma_u,x_1)} \otimes I_{\dx}}\paren{\hat \Phi (\hat \theta  - \bar \theta )} \\
&\leq \norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta  }\norm{\hat \Phi (\hat \theta   - \bar \theta )} \norm{\sum_{s=1}^t\bmat{x_s\\ u_s} \bmat{x_s \\ u_s}^\top - t \Sigma^t(K,\sigma_u,x_1)}.
\end{align*}

Invoking <Ref> with $G = I_{\dx+\du}$, we find that there exists an event $\calE_{\mathsf{cov}}$ that holds with probability at least $1-\delta/4$ such that under $\calE_{\mathsf{cov}}$,

\begin{align*}
\norm{\sum_{s=1}^t\bmat{x_s\\ u_s} \bmat{x_s \\ u_s}^\top - t \Sigma^t(K,\sigma_u,x_1)} \lesssim \mathrm{Conc}_{\mathsf{\mathsf{cov}}}(\delta).
\end{align*}

Combining bounds:
In light of the bounds on the self-normalized process and the variance from misspecification above, we define the event $\calE_{\mathsf{var}} = \calE_{\mathsf{noise}} \cap \calE_{\mathsf{cov}}$. This event holds with probability at least $1-\delta/2$ by a union bound. We may substitute the bounds arising under these events into into (<ref>), we find

\begin{align*}
\sum_{s=1}^t \norm{\VEC^{-1} \paren{\hat \Phi \bar \theta  - \hat \Phi \hat \theta }\bmat{x_s \\ u_s}}^2 &\lesssim \sigma^2 \log\paren{ \frac{\det(\Sigma+\Lambda) }{\det(\Sigma) \delta^2} } +\mathrm{Conc}_{\mathsf{cov}}(\delta)\norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta }\norm{\hat \Phi (\hat \theta - \bar \theta )},
\end{align*}

where we absorbed the $16$ from the $\log$ in the first term into a universal constant.
The left side of the above inequality may be lower bounded by $\lambda_{\min}(\Sigma) \norm{\bar \theta  - \hat \theta }^2$. which may in turn be lower bounded by $\lambda_{\min}(\Sigma ) \norm{\hat \Phi \bar \theta  - \hat \Phi \hat \theta }^2$, by the fact that $\hat \Phi$ has orthonormal columns. We therefore obtain the following bound:

\begin{align*}
\norm{\hat \Phi \bar \theta  - \hat \Phi \hat \theta }^2 \lesssim \frac{\sigma^2}{\lambda_{\min}(\Sigma )} \log\paren{ \frac{ \det(\Sigma+\Lambda )}{\det(\Sigma) \delta^2} } + \frac{\mathrm{Conc}_{\mathsf{cov}}(\delta)}{\lambda_{\min}(\Sigma )} \norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta }\norm{\hat \Phi (\hat \theta  - \bar \theta )}.
\end{align*}

Now, if we define

\begin{align*}
a &\triangleq \frac{\mathrm{Conc}_{\mathsf{cov}}(\delta)}{\lambda_{\min}(\Sigma)} \norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta}, \quad
b \triangleq \frac{\sigma^2}{\lambda_{\min}(\Sigma )} \log\paren{ \frac{ \det(\Sigma+\Lambda )}{\det(\Sigma) \delta^2} }, \quad
x \triangleq \norm{\hat \Phi \hat \theta  - \hat \Phi \bar \theta },
\end{align*}

then the above inequalities may be combined to read $x^2 \leq ax + b$, from which we can conclude $ x \leq \frac{1}{2} \paren{ a + \sqrt{a^2 + 4b}}$,
or equivalently,

\begin{align*}
x^2 &\leq \frac{1}{4}\paren{2 a^2 + 4b + 2 \sqrt{a^4 + 4a^2 b}} \leq \frac{1}{4}\paren{2 a^2 + 4b + 2 a^2 + 4 a^2 + 4 b} = 2a^2 + 2 b.
\end{align*}

Subtituting in the original quantities of interest and absorbing the factor of two into the universal constant concludes the proof.

Suppose $t \geq c \tau_{\ls}$ for $c$ and $\tau_{\ls}$ defined in <Ref>.

Then there exists an event $\calE_{\ls}$ that holds with probability at least $1 - \delta$ under which

\begin{align*}
&\norm{\hat \Phi \hat \theta  - \hat \Phi \bar \theta }^2 \lesssim \frac{ \dtheta \sigma^2  }{t \lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}} \log\paren{ \frac{1}{ \delta} } \\
&+  \frac{\sigma^4 \norm{\Sigma^t(K,\sigma_u, x_1)}^2 \norm{P_K}^3 \Psi_{B^\star}^2  }{ t\lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}^2 } \paren{\dx+\du + \log \frac{1}{\delta}}\norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^2.
\end{align*}

By the lower bound on $t$, the event $\calE_{\mathsf{conc}}$ defined in <Ref> holds with probability at least $1-\delta/2$. Denoting $\Sigma \gets t \frac{1}{2} \hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi$, we may invoke <Ref> to show that there exists an event $\calE_{\mathsf{var}}$ that holds with probability at least $1-\delta/2$ such that conditioned on $\calE_{ls} = \calE_{\mathsf{conc}}\cap\calE_{\mathsf{var}}$,

\begin{align*}
\norm{\hat \Phi \hat \theta  - \hat \Phi \bar \theta }^2 &\lesssim \frac{\sigma^2}{\lambda_{\min}(\Sigma)} \log\paren{ \frac{\det(\Sigma+\Lambda)}{\det(\Sigma) \delta^2} }+  \frac{\mathrm{Conc}_{\mathsf{cov}}(\delta)^2}{\lambda_{\min}(\Sigma)^2} \norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta}^2.
\end{align*}

By a union bound, $\calE_{\ls}$ holds with probability at least $1-\delta$.
Subsituting the definition of $\mathrm{Conc}_{\mathsf{cov}}$ from <Ref>, we may simplify the above bound to find

\begin{align*}
\norm{\hat \Phi \hat \theta  - \hat \Phi \bar \theta }^2 &\lesssim
\frac{\sigma^2}{\lambda_{\min}(\Sigma )} \log\paren{\frac{ \det(\Sigma+\Lambda )}{\det(\Sigma) \delta^2} } \\
&+  \frac{ \sigma^4 \norm{\Sigma^t(K,\sigma_u,x_1)}^2 \norm{P_K}^3 \Psi_{B^\star}^2 t}{\lambda_{\min}(\Sigma   )^2} \paren{\dx+\du + \log \frac{4}{\delta}}\norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^2,
\end{align*}

where we have used the fact that
$$t \geq c\tau_{\ls} \geq  \sigma^4  \norm{P_K}^3 \Psi_{B^\star}^2 \paren{\dx+\du + \log \frac{1}{\delta}},$$
to show that $\mathrm{Conc}_{\mathsf{cov}}$  assumes the quantity that grows with $t$.

The upper bound from the event $\calE_{\conc}$ provides

\[
\Lambda  \preceq 2 t \hat \Phi^\top \paren{ \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \preceq 2 t (1 + \norm{P_K}\frac{\norm{x_1}^2}{t-1}) \hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi,
\]

where the final inequality follows from <Ref> point 4.
The $\log$ term may then be bounded as

\begin{align*}
\log\paren{\frac{ \det(\Sigma+\Lambda)}{\det(\Sigma) \delta^2}} \leq \dtheta \log\paren{4 \frac{1 + \norm{P_K} \frac{\norm{x_1}^2}{t-1}}{\delta^2}}
\end{align*}

By the fact that $t \geq c \tau_{\ls} \geq \norm{x_1}^2 \norm{P_K} + 1$, we have $\frac{\norm{P_K} \norm{x_1}^2}{t-1} \leq 1$. Therefore, the above quantity is bounded by $\dtheta \log\frac{8}{\delta^2} \lesssim \dtheta \log \frac{1}{\delta}$.

Substituting the expression for $\Sigma$ tells us that

\begin{align*}
\lambda_{\min}(\Sigma ) =  \frac{t}{2}\lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}. %\frac{t\sigma_u^2 }{2(1+\norm{K}^2 + \sigma_u^2).}
\end{align*}

Substituing this into the bound on $\norm{\hat \Phi \hat \theta - \hat \Phi \bar \theta}^2$ along with the upper bound on $\log\paren{\frac{\det(\Sigma+\Lambda)}{\det (\Sigma) \delta^2}}$ completes the proof.

§.§ Bias Bound

The bias of the estimate arising in <Ref> is bounded as

\begin{align*}
\norm{\hat \Phi \bar \theta - \Phi^\star \theta^\star}^2 \leq 4 \frac{\norm{\Sigma^t(K,\sigma_u,x_1)}}{\lambda_{\min}(\hat \Phi^\top (\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}) \hat \Phi)} d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2.
\end{align*}

We first left multiply the quantity in the norm by the identity defined in terms of the matrix $\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top$ left multiplied by its inverse:

\begin{align*}
&\norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta}^2 =\bigg\|(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \\
&\quad \times\paren{\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top} \paren{\Phi^\star \theta^\star- \hat \Phi \bar \theta }\bigg\|^2.
\end{align*}

To simplify the above quantity, firstly observe that the term

\begin{align}
\label{eq: bias term orthogonal reduction}
\hat \Phi_\perp \hat \Phi_\perp^\top \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta } = \hat \Phi_\perp \hat \Phi_\perp^\top \Phi^\star \theta^\star
\end{align}

by the fact that $\hat \Phi_\perp^\top \hat \Phi = 0$. Second, note that the term

\begin{align*}
&\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta} \\&= \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top \Phi^\star \theta^\star - \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \bar \theta
\end{align*}

by the fact that the columns of $\hat \Phi$ are orthonormal. We now substitute the optimal projection

\[
\bar \theta  = \paren{\hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}^{-1}\hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \Phi^\star \theta^\star
\]

into the above to find that

\begin{align*}
\hat \Phi \hat \Phi^\top &\paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top \paren{\Phi^\star \theta^\star - \hat \Phi \bar \theta } \\
&=\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top \Phi^\star \theta^\star \\&\quad- \hat \Phi \hat \Phi^\top \paren{\Sigma_k \otimes I_{\dx}} \hat \Phi  \paren{\hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}^{-1}\hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \Phi^\star \theta^\star \\
&=  \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top \Phi^\star \theta^\star - \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \Phi^\star \theta^\star \\
&=  \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx }} \paren{ \hat \Phi \hat \Phi^\top  - I_{\dx}} \Phi^\star \theta^\star  \\
&=  -\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi_\perp \hat \Phi_\perp^\top  \Phi^\star \theta^\star.
\end{align*}

Combining the above result with (<ref>), we find that

\begin{equation}
\label{eq: bias bound main ineq}
\begin{aligned}
&\norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^2 \\
&= \norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \paren{I - \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}}} \hat \Phi_\perp \hat \Phi_\perp^\top \Phi^\star \theta^\star}^2 \\
& \leq \norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \paren{I - \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}}} \hat \Phi_\perp}^2 \norm{\hat \Phi_\perp^\top \Phi^\star}^2 \norm{\theta^\star}^2.
\end{aligned}
\end{equation}

Application of the triangle inequality and Cauchy-Schwarz yields

\begin{equation}
\label{eq: decompose orthogonal and nonorthogonal}
\begin{aligned}
&\norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \paren{I - \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}}} \hat \Phi_\perp}^2 \\
&\qquad \leq 2 \norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \hat \Phi_\perp}^2 \\
&\qquad + 2 \norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi_\perp}^2.
\end{aligned}
\end{equation}

The first term may be simplified as follows:

\begin{equation}
\label{eq: orthogonal component bias bound}
\begin{aligned}
&\norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \hat \Phi_\perp}^2 \\
&= \norm{\paren{\bmat{\hat \Phi & \hat \Phi_\perp} \bmat{\hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \\ &  I} \bmat{ \hat \Phi & \hat \Phi_\perp}^\top }^{-1} \hat \Phi_\perp}^2 \\
&= \norm{\bmat{\hat \Phi & \hat \Phi_\perp} \bmat{\hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \\ &  I}^{-1} \bmat{ \hat \Phi & \hat \Phi_\perp}^\top  \hat \Phi_\perp}^2 \\
&= 1.
\end{aligned}
\end{equation}

For the second term, we may similarly show that

\begin{align*}
&\norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi \hat \Phi^\top  + \hat \Phi_\perp \hat \Phi_\perp^\top)^{-1} \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I} \hat \Phi_\perp}^2 \\
&= \norm{(\hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx} } \hat \Phi \hat \Phi^\top)^{\dagger} \hat \Phi \hat \Phi^\top \paren{\Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi_\perp}^2 \\
&\leq \frac{\norm{\Sigma^t(K,\sigma_u,x_1)}}{\lambda_{\min}(\hat \Phi^\top (\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}) \hat \Phi)},
\end{align*}

where the final inequality follows from submultiplicativity, the fact that $\hat \Phi$ has orthonormal columns and the fact that $\Sigma^t(K,\sigma_u,x_1) \preceq \bar \Sigma^t(K,\sigma_u,x_1)$.

The lemma follows by substituting the above inequality along with (<ref>) into (<ref>). The result is then substituted into (<ref>), where we recall the definition <Ref>.

§.§ Proof of <Ref>

Combining the results of <Ref> with <Ref>, we find that under the event  $\calE_{\ls}$ of <Ref>,

\begin{align*}
&\norm{\hat \Phi \hat \theta  - \hat \Phi \bar \theta }^2 \lesssim \frac{ \dtheta \sigma^2  }{t \lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}} \log\paren{ \frac{1}{ \delta} } \\
&+ \paren{1+ \frac{\sigma^4 \norm{\Sigma^t(K,\sigma_u, x_1)}^2 \norm{P_K}^3 \Psi_{B^\star}^2  }{ t\lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}^2 } \paren{\dx+\du + \log \frac{1}{\delta}}}\norm{\Phi^\star \theta^\star - \hat \Phi \bar \theta }^2.
\end{align*}

Using <Ref>, the above may be bounded as

\begin{align*}
&\norm{\hat \Phi \hat \theta  - \hat \Phi \bar \theta }^2 \lesssim \frac{ \dtheta \sigma^2  }{t \lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}} \log\paren{ \frac{1}{ \delta} } \\
&+ \paren{1+ \frac{\sigma^4 \norm{\Sigma^t(K,\sigma_u, x_1)}^2 \norm{P_K}^3 \Psi_{B^\star}^2  }{ t\lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}^2 } \paren{\dx+\du + \log \frac{1}{\delta}}} \\
&\times \frac{\norm{\Sigma^t(K,\sigma_u,x_1)}}{\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi)} d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2.
\end{align*}

To conclude, we use the upper bounds on $\norm{\Sigma^t(K,\sigma_u,x_1)}$ from <Ref>:

\begin{align*}
\norm{\Sigma^t(K,\sigma_u,x_1)} &\leq (1+  \norm{P_K}\frac{\norm{ x_1^2}}{t-1})  \norm{\bar\Sigma^t(K,\sigma_u,x_1)}\leq 5 (1+  \norm{P_K}\frac{\norm{ x_1^2}}{t-1})   \norm{P_K}^2 \Psi_{B^\star}^2.
\end{align*}

By the fact that $t \geq c \tau_{\ls}$, the above quantity is bounded as $\norm{\Sigma^t(K,\sigma_u,x_1)} \leq 10 \norm{P_K}^2 \Psi_{B^\star}^2$.

Therefore we find that

\begin{align*}
&\norm{\hat \Phi \hat \theta  - \Phi^\star \theta^\star}^2 \lesssim \frac{\dtheta \sigma^2  }{t \lambda_{\min} \paren{\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi}} \log\paren{ \frac{1}{ \delta} } \\
&\quad+ \paren{1+ \frac{\sigma^4 \norm{P_K}^7 \Psi_{B^\star}^6 \paren{\dx+\du + \log \frac{1}{\delta}}}{t\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi)^2 } } \frac{\norm{P_K}^2 \Psi_{B^\star}^2 d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2}{\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi)} .
\end{align*}

§ HIGH PROBABILITY BOUNDS ON THE SUCCESS EVENTS

We first state a more complete counterpart of <Ref> that also
characterize the error in the learned controller gain and the Lyapunov equation solution $P_{\hat K}$ under this controller.

Define $\varepsilon \triangleq \frac{1}{2916 \norm{P^\star(A^\star, B^\star)}^{10}}$. As long as

\norm{\bmat{\hat A & \hat B}-\bmat{A^\star & B^\star}}_F^2 \leq \varepsilon,
we have that $P_{\hat K} \preceq \frac{21}{20} P^\star$, $\norm{\hat K - K^\star}\leq \frac{1}{6 \norm{P^\star}^{3/2}}$, and

\begin{align*}
\calJ(\hat K)  - \calJ(K^\star) \leq 142 \norm{P^\star}^8 \norm{\bmat{\hat A & \hat B}-\bmat{A^\star & B^\star}}_F^2.
\end{align*}

Let $\delta \in (0,1)$. With probability at least $1-\delta$

\begin{align*}
\max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \leq 4\sigma \sqrt{ (\dx+\du) \log\frac{T}{\delta}}.
\end{align*}

The vectors $w_t$ and $g_t$ have $\sigma^2$-sub-Gaussian components. Therefore, a sub-Gaussian tail bound tells us that for any unit vector $v \in \mathbb{R}^{\dx+\du)}$

\begin{align*}
\P\brac{ v^\top \bmat{w_t \\ g_t} \geq \rho} \leq \exp\paren{-\frac{\rho^2}{2\sigma^2}}.
\end{align*}

By a covering argument, we therfore conclude

\begin{align*}
\P\brac{ \norm{\bmat{w_t \\ g_t}} \geq \rho} \leq 5^{\dx+\du} \exp\paren{-\frac{\rho^2}{8\sigma^2}}.
\end{align*}

Union bounding over the $T$ timesteps yields

\begin{align*}
\P\brac{\max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \geq \rho} \leq T 5^{\dx+\du} \exp\paren{-\frac{\rho^2}{8\sigma^2}}.
\end{align*}

Setting $\rho = 4\sigma \sqrt{ (\dx+\du) \log\frac{T}{\delta}}$, the above probability becomes

\begin{align*}
T 5^{\dx+\du} \exp\paren{-2 (\dx+\du) \log \frac{T}{\delta}} &\leq T 5^{\dx+\du} \exp\paren{-2 (\dx+\du) -\log \frac{T}{\delta}} \\
&\leq \delta 5^{\dx+\du} \exp(-2)^{\dx+\du} \leq \delta.
\end{align*}

Consider rolling out the system $x_{s+1} = A^\star x_s + B^\star u_s +w_s$ from initial state $x_1$ for $t$ timesteps under the control action $u_s = K x_s + \sigma_u g_s$ where $K$ is stabilizing and $\sigma_u \leq 1$. Then the following bound holds:

\begin{align*}
\norm{x_t} &\leq \sqrt{\paren{1 - \frac{1}{\norm{P_K}}}^t \norm{P_K}} \norm{x_1} + 2\norm{P_{K}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T } \norm{\bmat{w_t \\ g_t}}
\end{align*}

The states may be expressed as $x_{t} = A_K^{t-1} x_1 +  \sum_{k=0}^{t-1} A_{K}^{t-1-k} \bmat{I & \sigma_u B^\star} \bmat{w_k \\ g_k}$. Therefore, by <Ref>,

\begin{align*}
\norm{x_t} &\leq \norm{A_K^{t-1}} \norm{x_1} + \sum_{k=0}^{t-1} \norm{A_{K}^{t-1-k}} \norm{\bmat{I & \sigma_u B^\star}} \max_{1\leq t \leq T } \norm{\bmat{w_t \\ g_t}} \\
&\leq \sqrt{\paren{1 - \frac{1}{\norm{P_K}}}^{t-1} \norm{P_K}} \norm{x_1} + 2\norm{P_{K}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T } \norm{\bmat{w_t \\ g_t}}.
\end{align*}

Consider rolling out the system $x_{s+1} = A^\star x_s + B^\star u_s +w_s$ from initial state $x_1$ for $t$ timesteps under the control action $u_s = K x_s + \sigma_u g_s$ where $K$ is stabilizing and $\sigma_u \leq 1$. Suppose

* $\norm{x_1} \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}$

* $\norm{P_K} \leq 2 \norm{P_{K_0}}$

* $t \geq \log_{\paren{1 - \frac{1}{\norm{P_K}}}}\paren{\frac{1}{4\norm{P_K}}}+1$.
Then for $s=1, \dots, t$

\begin{align*}
\norm{x_s} \leq 40 \norm{P_{K_0}}^2  \Psi_{B^\star} \max_{1 \leq t \leq T} \norm{\bmat{w_t \\ g_t}}.
\end{align*}

\begin{align*}
\norm{x_t} \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}.
\end{align*}

By <Ref>,

\begin{align*}
\norm{x_s} &\leq \norm{P_K}^{1/2} \norm{x_1} + 2 \norm{P_K}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \\
&\leq 2 \norm{P_{K_0}}^{1/2} \norm{x_1} + 8 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1 \leq t \leq T} \norm{\bmat{w_t \\ g_t}}
\end{align*}

The bound in the first point then follows by substituting in the bound for $\norm{x_1}$. For the second point, note that by <Ref>, and the fact that $t \geq \log_{\paren{1 - \frac{1}{\norm{P_K}}}}\paren{\frac{1}{4 \norm{P_K}}} + 1$,

\begin{align*}
\norm{x_t} &\leq \frac{1}{2} \norm{x_1} + 2 \norm{P_K}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \\
&\leq  \frac{1}{2} \norm{x_1} +  8 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \\
& \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}.
\end{align*}

Running <Ref> with the arguments defined in <Ref>, the event $\calE_{\mathsf{success},1} $ holds with probability at least $1-T^{-2}$.

By <Ref>, we have that with probability at least $1-\frac{1}{2}T^{-2}$,

\begin{align*}
\max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \leq 4\sigma\sqrt{3 (\dx + \du) \log 2 T}.
\end{align*}

Denote the event that the above inequality holds by $\calE_{\mathsf{w\,bound}}$.
We show by induction that the requisite conditions of $\calE_{\mathsf{success},1}$ hold for all epochs.
A key step in this argument is instantiating the result of <Ref> for every epoch. The rate of decay in this bound is the determined by minimum eigenvalue of the state and input covariance,
$\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi)$.
We control this quantity by invoking point 3 of <Ref> along with the facts that 1) $\hat \Phi$ has orthonormal columns and 2)  $\sigma_u = \sigma_k \leq 1$ for all epochs due to the lower bound on $\tau_1$. In particular, we may show that

\begin{align}
\label{eq: covariance lower bound continual exploration}
\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi) \geq \frac{\sigma_u^2}{2(2 + 2 \norm{K}^2)} \geq \frac{\sigma_u^2}{8 \norm{P_K}},
\end{align}

where the final inequality follows by noting that $2 + 2\norm{K}^2 \leq 2 + 2\norm{P_K} \leq 4 \norm{P_K}$ by the fact that $\norm{P_K} \geq 1$.

Base Case: For the first epoch, observe that our lower bound on $\tau_1$ ensures that $\tau_1 \geq c \tau_{\ls}(K_0, 0, \frac{1}{2}T^{-3})$ for a sufficiently large constant $c$. Therefore applying <Ref> along with (<ref>) implies that there exists an event $\calE_{\ls,1}$ which holds with probability at least $\frac{1}{2}{T^{-3}}$ such that under $\calE_{\ls,1}$,

\begin{align*}
&\norm{\bmat{\hat A_1 & \hat B_1} - \bmat{A^\star & B^\star}}_F^2 \lesssim \frac{\dtheta \sigma^2 \norm{P_{K_0}} }{\tau_1 \sigma_1^2} \log\paren{ T} \\
&\quad+ \paren{1+ \frac{\sigma^4 \norm{P_{K_0}}^9 \Psi_{B^\star}^6 \paren{\dx+\du + \log\paren{T}}}{\tau_1 \sigma_1^4 } } \frac{\norm{P_{K_0}}^3 \Psi_{B^\star}^2 d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2}{\sigma_1^2}.
\end{align*}

Using the fact that $\sigma_1^2 \geq \frac{\sqrt{\dtheta/\du}}{\sqrt{\tau_1}}$ to simplify the first two appearances of $\sigma_1$, and $\sigma_1^2 \geq d(\hat \Phi, \Phi^\star)$ for the final appearance, the above bound simplifies to

\begin{align*}
&\norm{\bmat{\hat A_1 & \hat B_1} - \bmat{A^\star & B^\star}}_F^2 \lesssim \frac{\sqrt{\dtheta \du} \sigma^2 \norm{P_{K_0}} }{\sqrt{\tau_1}} \log\paren{ T} \\
&\quad+ \sigma^4 \frac{\dtheta}{\du} \norm{P_{K_0}}^{12} \Psi_{B^\star}^8 \paren{\dx+\du + \log\paren{T}}  d(\hat \Phi, \Phi^\star) \norm{\theta^\star}^2.
\end{align*}

By recalling the definition of $\beta_1$ from <Ref>, the above bound can be simplified to

\begin{align*}
\norm{\bmat{\hat A_1 & \hat B_1} - \bmat{A^\star & B^\star}}_F^2 \leq C_{\mathsf{est},1} \sigma^2 \frac{\sqrt{\dtheta \du} \norm{P_{K_0}}  }{\sqrt{\tau_1}} \log\paren{T} + \beta_1  \log(T) d(\hat \Phi, \Phi^\star).
\end{align*}

Meanwhile, <Ref> tells us that under the event $\calE_{\mathsf{w\,bound}},$ $\norm{x_t}^2 \leq x_b^2\log T$ for $t=1,\dots, \tau_1$, and that $\norm{x_{\tau_1}} \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}$.  Finally, we have $\norm{K_0} \leq K_b$.

Induction step:  Suppose
$$\norm{x_{\tau_k}} \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}$$

\begin{align*}
\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 &\leq C_{\mathsf{est},1}  \sigma^2 \frac{\sqrt{\dtheta \du} \norm{P_{K_0}}  }{\sqrt{\tau_1 2^{k-1}}} \log\paren{T} + \beta_1  \log(T) d(\hat \Phi, \Phi^\star).
\end{align*}

By the assumptions that $\tau_1 \geq c\paren{ \frac{ \sigma^2 \sqrt{\dtheta \du} \norm{P_{K_0}} }{2\varepsilon}}^2 $ for a sufficiently large constant $c$ and that  $d(\hat \Phi, \Phi^\star) \leq \frac{\varepsilon}{2 \beta_1 \log(T)}$, we have that $\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 \leq \varepsilon$. Then the conditions of <Ref> are satisfied, and consequently, $\norm{P_{\hat K_{k+1}}} \leq 1.05 \norm{P^\star}$. Therefore

\begin{align*}
\tau_{\ls}(\hat K_{k+1}, x_b^2\log T, \frac{1}{2}T^{-3}) &\leq  2\tau_{\ls}(K^\star, x_b^2\log T, \frac{1}{2} T^{-3}) \quad \mbox{ and } \quad \norm{P_{\hat K_{k+1}}}  \leq 1.05 \norm{P_{K_0}} \leq 2 \norm{P_{K_0}}.
\end{align*}

We may use our lower bound on $\tau_1$ to conclude that $\tau_1 \geq c \tau_{\ls}(K^\star, x_b^2 \log T, \frac{1}{2}T^{-3})$ for a sufficiently large universal constant $c$. This guarantees that the conditions of <Ref> are satsified. As a result, there exists an event $\calE_{\ls,k+1}$ that holds with probability at least $1-\frac{1}{2}T^{-3}$ under which

\begin{align*}
&\norm{\bmat{\hat A_{k+1} & \hat B_{k+1}} - \bmat{A^\star & B^\star}}_F^2 \lesssim \frac{\dtheta \sigma^2 \norm{P_{\hat K_{k+1}}} }{(\tau_{k+1}-\tau_k) \sigma_{k+1}^2} \log\paren{T} \\
&\quad+ \paren{1+ \frac{\sigma^4 \norm{P_{\hat K_{k+1}}}^9 \Psi_{B^\star}^6 \paren{\dx+\du + \log\paren{T}}}{(\tau_{k+1}-\tau_k) \sigma_{k+1}^4 } }  \frac{\norm{P_{\hat K_{k+1}}}^3 \Psi_{B^\star}^2 d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2}{\sigma_{k+1}^2},
\end{align*}

where we have again used (<ref>) to simplify the bound. Observing that $\tau_{k+1} - \tau_k = \frac{1}{2}\tau_{k+1}$, and using the lower bounds $\sigma_{k+1}^2 \geq \frac{\sqrt{\dtheta/\du}}{\sqrt{\tau_1 2^{k}}} = \frac{\sqrt{\dtheta/\du}}{\sqrt{\tau_{k+1}}}$ and $\sigma_{k+1}^2 \geq \exploration \geq d(\hat \Phi, \Phi^\star)$, the above bound simplifies to

\begin{align*}
&\norm{\bmat{\hat A_{k+1} & \hat B_{k+1}} - \bmat{A^\star & B^\star}}_F^2 \lesssim  \frac{ \sqrt{\dtheta \du}\sigma^2 \norm{P_{\hat K_{k+1}}} }{\sqrt{\tau_{k+1}}} \log\paren{ T} \\
&\quad+  \sqrt{\dtheta/\du}\sigma^4 \norm{P_{\hat K_{k+1}}}^{12} \Psi_{B^\star}^8 \paren{\dx+\du + \log\paren{T}}  d(\hat \Phi, \Phi^\star) \norm{\theta^\star}^2.
\end{align*}

Using the fact that $\norm{P_{\hat K_{k+1}}} \leq 1.05 \norm{P^\star} \leq 1.05 \norm{P_{K_0}}$, the above bound may be simplified to

\begin{align*}
&\norm{\bmat{\hat A_{k+1} & \hat B_{k+1}} - \bmat{A^\star & B^\star}}_F^2 \leq C_{\mathsf{est},1}
\sigma^2 \frac{\sqrt{\dtheta \du}  \norm{P_{K_0}}  }{\sqrt{\tau_{k+1}}} \log\paren{T} + \beta_1   d(\hat \Phi, \Phi^\star) \log(T),
\end{align*}

where the powers of $1.05$  are absorbed into the universal constants, and $\beta_1$ is as defined in <Ref>.

Furthermore, <Ref> (which applies due to the inductive hypothesis, the lower bound on $\tau_1$, and the fact that $\norm{P_{\hat K_{k+1}}} \leq 2 \norm{P_{K_0}}$) informs us that under the event $\calE_{\mathsf{w\,bound}}$,

\begin{align*}
\norm{x_t}^2 \leq x_b^2 \log T \quad \forall t =\tau_{k}+1, \dots, \tau_{k+1}, \mbox{ and } \norm{x_{\tau_{k+1}}}  \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}.
\end{align*}

Also observe that $\norm{\hat K_{k+1}}^2 \leq \norm{P_{\hat K_{k+1}}} \leq 2 \norm{P_{K_0}}$, which ensures that $\norm{\hat K_{k+1}} \leq 2 \norm{K^\star} \leq K_b$.
In particular, we have verified that the algorithm does not abort on this epoch, and we have verified that the inductive hypothesis holds to start the next epoch.

Union bounding over the events The bounds on the norm of the state and the controller gain ensure that the algorithm does not abort. The estimation error bounds ensure that

\begin{align*}
\norm{\bmat{\hat A_{k} & \hat B_{k}} - \bmat{A^\star & B^\star}}_F^2 &\leq C_{\mathsf{est},1} \sigma^2 \frac{\sqrt{\dtheta \du} \norm{P_{K_0}}  }{\sqrt{\tau_{1}}} \log\paren{T} + \beta_1  \log(T) d(\hat \Phi, \Phi^\star) \quad \forall k \geq 1.
%\norm{\bmat{\hat A_{k} & \hat B_{k}} - \bmat{A^\star & B^\star}}_F^2 &\leq C \sigma^2 \frac{\sqrt{\dtheta \du} \norm{P_{K^\star}}  }{\sqrt{\tau_{k}}} \log\paren{T} + \beta_1  \log(T) d(\hat \Phi, \Phi^\star) \quad \forall k \geq 2
\end{align*}

Therefore, $\calE_{\mathsf{success},1} \subseteq\calE_{\mathsf{w\, bound}} \cap \calE_{\ls,1} \cap \dots \cap \calE_{\ls, k_{\fin}}$. Union bounding over the good events $\calE_{\mathsf{w\, bound}}, \calE_{\ls,1}, \dots, \calE_{\ls, k_{\fin}}$, we find that $\calE_{\mathsf{success},1}$ holds with probability at least $1-T^{-2}$.

Running <Ref> with the arguments defined in <Ref>, the event $\calE_{\mathsf{success},2} $ holds with probability at least $1-T^{-2}$.

By <Ref>, we have that with probability at least $1-\frac{1}{2}T^{-2}$,

\begin{align*}
\max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}} \leq 4\sigma\sqrt{3 (\dx + \du) \log 2 T}.
\end{align*}

Denote the event that the above inequality holds by $\calE_{\mathsf{w\,bound}}$.
We show by induction that the requisite conditions of $\calE_{\mathsf{success},2}$ hold for all epochs.
A key step in this argument is instantiating the result of <Ref> for every epoch. The rate of decay in this bound is the determined by minimum eigenvalue of the state and input covariance,
$\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi)$.
We control this quantity by observing that for any unit vector  $v$

\begin{equation}
\begin{aligned}
\label{eq: excitation reduction}
v^\top \hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi v &\geq \frac{1}{2}  v \hat \Phi^\top \paren{\bmat{I \\ K} \bmat{I \\ K}^\top \otimes I_{\dx}} \hat \Phi v \\
&=\frac{1}{2} \paren{\sum_{i=1}^{\dtheta} v_i \hat \Phi_i}^\top \paren{\bmat{I \\ K} \bmat{I \\ K}^\top \otimes I_{\dx}}\paren{\sum_{i=1}^{\dtheta} v_i \hat \Phi_i} \\
&= \frac{1}{2} \norm{\sum_{i=1}^{\dtheta} v_i \VEC^{-1}\paren{ \hat \Phi_i} \bmat{I \\ K}}_F^2 \\
&= \frac{1}{2} \norm{\sum_{i=1}^{\dtheta} v_i \bmat{\hat \Phi^A_i + \hat \Phi^B_i K}}_F^2.
\end{aligned}
\end{equation}

We use this result along with <Ref> to show a lower bound $\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^t(K,\sigma_u,x_1) \otimes I_{\dx}} \hat \Phi) \geq \frac{\alpha^2}{8}$, and in turn show that the event $\calE_{\mathsf{success},2}$ holds with high probability. This result will proceed by induction.

Base Case: For the first epoch, observe that our lower bound on $\tau_1$ guarantees that $\tau_1 \geq c \tau_{\ls}(K_0, 0, \frac{1}{2}T^{-3})$ for  a sufficiently large universal constant $c$. Therefore applying <Ref> along with (<ref>) and <Ref> implies that there exists an event $\calE_{\ls,1}$ which holds with probability at least $\frac{1}{2}{T^{-3}}$ such that under $\calE_{\ls,1}$,

\begin{align*}
&\norm{\bmat{\hat A_1 & \hat B_1} - \bmat{A^\star & B^\star}}_F^2 \lesssim \frac{\dtheta \sigma^2  }{\tau_1 \alpha^2} \log  T \\
&\quad+ \paren{1+ \frac{\sigma^4 \norm{P_{K_0}}^7 \Psi_{B^\star}^6 \paren{\dx+\du + \log T}}{\tau_1 \alpha^4 } }  \frac{\norm{P_{K_0}}^2 \Psi_{B^\star}^2 d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2}{\alpha^2}.
\end{align*}

Using the fact that $\tau_1 = \tau_{\mathsf{warm\,up}}\log T$, we can cancel the $\log T$ in the numerator in the second term. We can further use the fact that $\tau_{\mathsf{warm\,up}} \geq c \frac{\sigma^4 \dtheta}{\epsilon \alpha^2}$ for some universal positive constant $c$ to simplify the second term to $\beta_2 d(\hat \Phi, \Phi^\star)^2$, where $\beta_2$ is as in <Ref>. Then the above bound may be simplified to

\begin{align*}
\norm{\bmat{\hat A_1 & \hat B_1} - \bmat{A^\star & B^\star}}_F^2 \leq C_{\mathsf{est},2} \frac{\sigma^2 \dtheta \log T}{\tau_1 \alpha^2} + \beta_2 d(\hat \Phi, \Phi^\star)^2.
\end{align*}

where $C_{\mathsf{est},2}$ is a sufficiently large universal constant.
Meanwhile, <Ref> tells us that under the event $\calE_{\mathsf{w\,bound}},$ $\norm{x_t}^2 \leq x_b^2 \log T$ for $t=1,\dots, \tau_1$, and that $\norm{x_{\tau_1}} \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}$.  Finally, we have $\norm{K_0} \leq K_b$.

Induction step:  Suppose
$$\norm{x_{\tau_k}} \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}$$

\begin{align*}
\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 &\leq C_{\mathsf{est},2} \frac{\sigma^2 \dtheta \log T}{\tau_1 \alpha^2} + \beta_2 d(\hat \Phi, \Phi^\star)^2.
\end{align*}

By the lower bound on $\tau_1$, we have that $\tau_1 \geq c \frac{ \sigma^2 \dtheta \log T}{2\varepsilon \alpha^2} $ for a sufficiently large universal constant $c$. Combining this with the condition in assumption <Ref>, which says $d(\hat \Phi, \Phi^\star) \leq \sqrt{\frac{\varepsilon}{2 \beta_2 }}$, we find $\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 \leq \varepsilon$. Then the conditions of <Ref> are satisfied, and consequently, $\norm{P_{\hat K_{k+1}}} \leq 1.05 \norm{P^\star}$. Therefore

\begin{align*}
\tau_{\ls}(\hat K_{k+1}, x_b^2 \log T, \frac{1}{2}T^{-3}) &\leq 2 \tau_{\ls}(K^\star, x_b^2 \log T, \frac{1}{2} T^{-3}) \quad \mbox{ and } \quad \norm{P_{\hat K_{k+1}}}  \leq 1.05 \norm{P_{K_0}} \leq 2 \norm{P_{K_0}}.
\end{align*}

We may guarantee from our lower bound on $\tau_1$ that $\tau_1 \geq c \tau_{\ls}(K^\star, x_b^2\log T, \frac{1}{2}T^{-3})$ for a sufficiently large universal constant $c$, which ensures that the conditions of <Ref> are satisfied. As a result, there exists an event $\calE_{\ls,k+1}$ that holds with probability at least $1-\frac{1}{2}T^{-3}$ under which

\begin{align*}
&\norm{\bmat{\hat A_{k+1} & \hat B_{k+1}} - \bmat{A^\star & B^\star}}_F^2 \lesssim \frac{\dtheta \sigma^2  }{(\tau_{k+1}-\tau_k) \alpha^2} \log  T \\
&\quad+ \paren{1+ \frac{\sigma^4 \norm{P_{\hat K_{k+1}}}^7 \Psi_{B^\star}^6 \paren{\dx+\du + \log  T}}{(\tau_{k+1}-\tau_k) \alpha^4 } } \frac{\norm{P_{\hat K_{k+1}}}^2 \Psi_{B^\star}^2 d(\hat \Phi, \Phi^\star)^2 \norm{\theta^\star}^2}{\alpha^2},
\end{align*}

where we lower bounded $\lambda_{\min}(\hat \Phi^\top \paren{\bar \Sigma^{\tau_{k+1}-\tau_k}(\hat K_{k+1}, ) \otimes I_{\dx}} \hat \Phi)$ using (<ref>) along with the following reverse triangle inequality combined with <Ref> and <Ref>:

\begin{align*}
\norm{\sum_{i=1}^{\dtheta} v_i \paren{\hat \Phi^A_i + \hat \Phi^B_i K^\star } +\sum_{i=1}^{\dtheta} v_i \hat \Phi^B_i (\hat K_{k+1} - K^\star) }_F \geq \alpha - \norm{\hat K_{k+1} - K^\star} \geq \alpha - \frac{1}{6\norm{P^\star}^{3/2}} \geq \frac{\alpha}{2}.
\end{align*}

Observing that $\tau_{k+1} - \tau_k = \frac{1}{2}\tau_{k+1}$, and
again using the fact that $\hat K_{k+1} = K^\star(\hat A_k, \hat B_k)$ where $\norm{\bmat{\hat A_k & \hat B_k} - \bmat{A^\star & B^\star}}_F^2 \leq \varepsilon$, we have that $\norm{P_{\hat K_{k+1}}} \leq 1.05 \norm{P^\star}$. Therefore by absorbing powers of $1.05$ into the universal constants, and following the same simplifications taken in the base case, the estimation error bound may be simplified to

\begin{align*}
&\norm{\bmat{\hat A_{k+1} & \hat B_{k+1}} - \bmat{A^\star & B^\star}}_F^2 \leq C_{\mathsf{est},2} \frac{\sigma^2 \dtheta \log T}{\tau_{k+1} \alpha^2} + \beta_2  d(\hat \Phi, \Phi^\star)^2.
\end{align*}

Furthermore, <Ref> (which applies due to the inductive hypothesis, the lower bound on $\tau_1$, and the fact that $\norm{P_{\hat K_{k+1}}} \leq 2 \norm{P_{K_0}}$) informs us that under the event $\calE_{\mathsf{w\,bound}}$,

\begin{align*}
\norm{x_t}^2 \leq x_b^2 \log T \quad \forall t =\tau_{k}+1, \dots, \tau_{k+1}, \mbox{ and } \norm{x_{\tau_{k+1}}}  \leq 16 \norm{P_{K_0}}^{3/2} \Psi_{B^\star} \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}.
\end{align*}

Also observe that $\norm{\hat K_{k+1}}^2 \leq \norm{P_{\hat K_{k+1}}} \leq 2 \norm{P_{K_0}}$, which ensures that $\norm{\hat K_{k+1}} \leq 2 \norm{K^\star} \leq K_b$.
In particular, we have verified that the algorithm does not abort on this epoch, and we have verified that the inductive hypothesis holds to start the next epoch.

Union bounding over the events The bounds on the norm of the state and the controller gain ensure that the algorithm does not abort. The estimation error bounds ensure that

\begin{align*}
\norm{\bmat{\hat A_{k} & \hat B_{k}} - \bmat{A^\star & B^\star}}_F^2 &\leq C_{\mathsf{est},2} \frac{\sigma^2 \dtheta \log T}{\tau_{k+1} \alpha^2} + \beta_2  d(\hat \Phi, \Phi^\star)^2 \quad \forall k \geq 1.
%\norm{\bmat{\hat A_{k} & \hat B_{k}} - \bmat{A^\star & B^\star}}_F^2 &\leq C \sigma^2 \frac{\sqrt{\dtheta \du} \norm{P_{K^\star}}  }{\sqrt{\tau_{k}}} \log\paren{T} + \beta_1  \log(T) d(\hat \Phi, \Phi^\star) \quad \forall k \geq 2
\end{align*}

Therefore, $\calE_{\mathsf{success},1} \subseteq\calE_{\mathsf{w\, bound}} \cap \calE_{\ls,1} \cap \dots \cap \calE_{\ls, k_{\fin}}$.  Union bounding over the good events $\calE_{\mathsf{w\, bound}}, \calE_{\ls,1}, \dots, \calE_{\ls, k_{\fin}}$, we find that $\calE_{\mathsf{success},1}$ holds with probability at least $1-T^{-2}$.

§ PROOF OF MAIN RESULT

Consider rolling out the system $x_{s+1} = A^\star x_s + B^\star u_s +w_s$ from initial state $x_1$ for $t$ timesteps under the control action $u_s = K x_s + \sigma_u g_s$ where $K$ is stabilizing and $\sigma_u \leq 1$. We have that

\begin{align*}
\E \brac{\sum_{s=1}^t \norm{x_t}_Q^2 + \norm{u_t}_R^2 \vert x_1} \leq  t J(K) + 2t \sigma_u^2\du \Psi_{B^\star}^2 \norm{P_K})  +  \norm{x_1}^2 \norm{P_K}
\end{align*}

Begin by writing

\begin{align*}
\E \brac{\sum_{s=1}^t \norm{x_t}_Q^2 + \norm{u_t}_R^2 \vert x_1} &= \sum_{s=1}^t \E\brac{\norm{x_t}_{Q+K^\top R K}^2 + \norm{\sigma_u g_t}^2 \vert x_1} \\
&= t \sigma_u^2 + \sum_{s=1}^t \trace\paren{(Q+K^\top R K) \E\brac{ x_t x_t^\top \vert x_1}}.
\end{align*}

We have that

\begin{align*}
&\E\brac{x_t x_t^\top \vert x_1} = \E\brac{  (A^\star + B^\star K) x_{t-1} x_{t-1}^\top (A^\star + B^\star K) + \sigma_u^2 B^\star (B^\star)^\top + I \vert x_1} \\
&= (A^\star + B^\star K)^{t-1} x_1 x_1^\top \paren{(A^\star + B^\star K)^{t-1}}^\top \\
&\qquad+ \sum_{k=1}^{t-1} (A^\star + B^\star K)^k \paren{\sigma_u^2 B^\star (B^\star)^\top + I} \paren{(A^\star + B^\star K)^k}^\top \\
&\preceq  (A^\star + B^\star K)^{t-1} x_1 x_1^\top \paren{(A^\star + B^\star K)^{t-1}}^\top + \dlyap(A^\star + B^\star K, \sigma_u^2 B^\star (B^\star)^\top + I).
\end{align*}

Substituting this above, we find,

\begin{align*}
\E \brac{\sum_{s=1}^t \norm{x_t}_Q^2 + \norm{u_t}_R^2 \vert x_1} &\leq t \sigma_u^2 + t \trace\paren{(Q+K^\top R K) \dlyap(A^\star + B^\star K, \sigma_u^2 B^\star (B^\star)^\top + I)} \\
&+ \sum_{s=1}^t  \trace\paren{(Q+K^\top R K)(A^\star + B^\star K)^{s-1} x_1 x_1^\top \paren{(A^\star + B^\star K)^{s-1}}^\top} \\
&\leq  t J(K) + t \sigma_u^2 (1 + \du \Psi_{B^\star}^2 \norm{P_K}) +  \norm{x_1}^2 \norm{P_K}.
\end{align*}

In the settings of both <Ref> and <Ref>,

\begin{align*}
R_3 = \E\brac{\sum_{t=1}^{\tau_1} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } \leq 3  \tau_1  \max\curly{\dx, \du} \norm{P_{K_0}} \Psi_{B^\star}^2  .
\end{align*}

This result follows from <Ref> by noting that $x_1 = 0$, and therefore

\begin{align*}
\E\brac{\sum_{t=1}^{\tau_1} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } \leq \tau_1   J(K_0)   + 2 \tau_1  \du \norm{P_{K_0}} \sigma_1^2 \Psi_{B^\star}^2 \leq 3  \tau_1 \max\curly{\dx, \du} \norm{P_{K_0}} \Psi_{B^\star}^2
\end{align*}

Let $\calE_{\mathsf{success}} \gets \calE_{\mathsf{success},1}$ or $\calE_{\mathsf{success}} \gets \calE_{\mathsf{success},2}$ in the settings of <Ref> and <Ref> respectively. Then in either setting

\begin{align*}
R_2 &= \E\brac{\mathbf{1}\paren{\calE_{\mathsf{success}}^c} \sum_{t=\tau_1+1}^{T} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } \\ &\leq T^{-1} \paren{\norm{Q} + 2 K_b^2} x_b^2 \log T + T^{-1}J(K_0) + 24\norm{P_{K_0}} \Psi_{B^\star}^2 (\dx+\du)\sigma^2 T^{-2} \log 3T\\
&+ 2 T^{-2} \norm{P_{K_0}} \norm{\theta_\star}_F^2 K_b^2 x_b^2 \log T+ \sum_{k=1}^{k_{\fin}}  2 (\tau_k - \tau_{k-1}) \du \sigma_k^2.
\end{align*}

In the setting of <Ref>, this reduces to

\begin{align*}
R_2 &\leq T^{-1} \paren{\norm{Q} + 2 K_b^2} x_b^2 \log T + T^{-1}J(K_0) + 24\norm{P_{K_0}} \Psi_{B^\star}^2 (\dx+\du)\sigma^2 T^{-2} \log 3T\\
&+ 2 T^{-2} \norm{P_{K_0}} \norm{\theta_\star}_F^2 K_b^2 x_b^2 \log T+ 6\sqrt{T} \sqrt{\dtheta \du} + 2\du \gamma T.
\end{align*}

In the setting of <Ref>, this reduces to

\begin{align*}
R_2 &\leq T^{-1} \paren{\norm{Q} + 2 K_b^2} x_b^2 \log T + T^{-1}J(K_0) + 24\norm{P_{K_0}} \Psi_{B^\star}^2 (\dx+\du)\sigma^2 T^{-2} \log 3T\\
&+ 2 T^{-2} \norm{P_{K_0}} \norm{\theta_\star}_F^2 K_b^2 x_b^2 \log T.
\end{align*}

Let $t_{\mathsf{abort}}$ be the first time instance where $\norm{x_t}^2 \geq x_b^2 \log T$ or $\norm{\hat K_k} \geq K_b$.

\begin{align*}
R_2 &= \E\brac{\mathbf{1}\paren{\calE_{\mathsf{success}}^c} \sum_{t=\tau_1+1}^{T} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } \\
& \leq \E\brac{\mathbf{1}\paren{\calE_{\mathsf{success}}^c} \sum_{t=1}^{T} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } \\
&\leq \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq T) \sum_{t=1}^{t_{\mathsf{abort}} -1} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } + \E\brac{\sum_{t=t_{\mathsf{abort}}}^{T} \norm{x_t}_Q^2 + \norm{u_t}_R^2 }.
\end{align*}

By the fact that $u_t = \hat K_k x_t + \sigma_k g_t$ for $g_t \sim \calN(0,I)$, we have that $\norm{u_t}^2 \leq 2 \norm{\hat K_k x_t}^2  + 2 \norm{\sigma_u g_t}^2$. By the definition of $t_{\mathsf{abort}}$ and the fact that $R=I$, for $t < t_{\mathsf{abort}}$

\begin{align*}
\norm{x_t}^2_Q + 2\norm{\hat K_{k} x_t}_R^2 \leq x_b^2\log T \paren{\norm{Q} + 2 K_b^2}.
\end{align*}

\begin{align*}
&\E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq T) \sum_{t=1}^{t_{\mathsf{abort}} -1} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } \\
&\leq \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq T) \sum_{t=1}^{t_{\mathsf{abort}} -1} x_b^2 \paren{\norm{Q} + 2 K_b^2} \log T + 2 \sum_{k=1}^{k_{\fin}} \sum_{t=\tau_{k-1}+1}^{\tau_k} 2 \sigma_k^2 \norm{g_t}^2 } \\
&\leq \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq T) \sum_{t=1}^{t_{\mathsf{abort}} -1} x_b^2\paren{\norm{Q} + 2 K_b^2} \log T} + \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq T)  \sum_{k=1}^{k_{\fin}} \sum_{t=\tau_{k-1}+1}^{\tau_k} 2 \sigma_k^2 \norm{g_t}^2 } \\
&\leq \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq T) T x_b^2 \paren{\norm{Q} + 2 K_b^2} \log T} + \E\brac{ \sum_{k=1}^{k_{\fin}} \sum_{t=\tau_{k-1}+1}^{\tau_k} 2 \sigma_k^2 \norm{g_t}^2 } \\
&= \mathbf{P}(t_{\mathsf{abort}} \leq T) T x_b^2 \paren{\norm{Q} + 2 K_b^2} \log T +  \sum_{k=1}^{k_{\fin}} \sum_{t=\tau_{k-1}+1}^{\tau_k} 2 \du \sigma_k^2   \\
&\leq T^{-1} x_b^2 \paren{\norm{Q} + 2 K_b^2} \log T +  \sum_{k=1}^{k_{\fin}}  2 (\tau_k - \tau_{k-1}) \du \sigma_k^2.
\end{align*}

For the second term, we have from <Ref>

\begin{align*}
\E\brac{\sum_{t=t_{\mathsf{abort}}}^{T} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } &= \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq  T)\sum_{t=t_{\mathsf{abort}}}^{T} \E\brac{\norm{x_t}_Q^2 + \norm{u_t}_R^2 \vert t_{\mathsf{abort}}, x_{t_{\mathsf{abort}}}}} \\
&\leq \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq  T) \paren{T J(K_0) + \norm{P_{K_0}} \norm{x_{t_{\mathsf{abort}}}}^2}}. %\\
% &\leq T^{-1} J(K_0) + \norm{P_{K_0}} \E\brac{\mathbf{1}(t_{\mathsf{abort}} \leq  T) \norm{x_{t_{\mathsf{abort}}}}^2}.
\end{align*}

We have that $x_{t_{\mathsf{abort}}} = (A^\star + B^\star K) x_{t_{\mathsf{abort}}-1} + \bmat{I & \sigma_u B^\star} \bmat{w_t \\ g_t} $ for some $K$ satisfying $\norm{K} \leq K_b$ and $\sigma_u \leq 1$. Then we may write

\begin{align*}
x_{t_{\mathsf{abort}}} &\leq 2 \norm{A^\star +B^\star K}^2 \norm{x_{t_{\mathsf{abort}}-1}}^2 + 2 \Psi_{B^\star}^2 \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}^2 \\
&\leq 2 \norm{\theta_\star}_F^2 K_b^2 x_b^2 \log T + 2 \Psi_{B^\star}^2 \max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}^2.
\end{align*}

\begin{align*}
\E\brac{\sum_{t=t_{\mathsf{abort}}}^{T} \norm{x_t}_Q^2 + \norm{u_t}_R^2 } &\leq \mathbf{P}(t_{\mathsf{abort}}\leq T) (TJ(K_0)+2 \norm{P_{K_0}} \norm{\theta_\star}_F^2 K_b^2 x_b^2 \log T) \\
&+ 2\norm{P_{K_0}} \Psi_{B^\star}^2 \E\brac{\mathbf{1}\paren{t_{\mathsf{abort}}\leq T}\max_{1\leq t \leq T} \norm{\bmat{w_t \\ g_t}}^2}.
\end{align*}