# Almost Surely $\sqrt{T}$ Regret Bound for Adaptive LQR

Yiwen Lu and Yilin Mo The authors are with the Department of Automation and
BNRist, Tsinghua University, Beijing, P.R.China. Emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The Linear-Quadratic Regulation (LQR) problem with unknown system parameters
has been widely studied, but it has remained unclear whether
$\tilde{\mathcal{O}}(\sqrt{T})$ regret, which is the best known dependence on
time, can be achieved almost surely. In this paper, we propose an adaptive LQR
controller with almost surely $\tilde{\mathcal{O}}(\sqrt{T})$ regret upper
bound. The controller features a circuit-breaking mechanism, which circumvents
potential safety breach and guarantees the convergence of the system parameter
estimate, but is shown to be triggered only finitely often and hence has
negligible effect on the asymptotic performance of the controller. The
proposed controller is also validated via simulation on Tennessee Eastman
Process (TEP), a commonly used industrial process example.

##  I Introduction

Adaptive control, the study of decision-making under the parametric
uncertainty of dynamical systems, has been pursued for decades [1, 2, 3, 4].
Although early research mainly focused on the the aspect of convergence and
stability, recent years have witnessed significant advances in the
quantitative performance analysis of adaptive controllers, especially for
multivariate systems. In particular, in the adaptive Linear-Quadratic
Regulation (LQR) setting considered in this paper, the controller attempts to
solve the stochastic LQR problem without access to the true system parameters,
and its performance is evaluated via _regret_ , the cumulative deviation from
the optimal cost over time. This adaptive LQR setting has been widely studied
in the past decade [5, 6, 7, 8, 9, 10, 11], but it has remained unclear
whether adaptive controllers for LQR can achieve
$\tilde{\mathcal{O}}(\sqrt{T})$ regret, whose asymptotic dependence on the
time $T$ is the best known (up to poly-logarithmic factors) 111It is known
that $\sqrt{T}$ is the optimal L1 rate of regret [9], and we suspect that it
is also the optimal almost sure rate., _almost surely_.

Existing regret upper bounds on adaptive LQR, summarized in Table I, are
either weaker than almost-sure in terms of the type of probabilistic
guarantee, or suboptimal in terms of asymptotic dependence on time. By means
of optimism-in-face-of-uncertainty [7], Thompson sampling [6], or
$\epsilon$-greedy algorithm [9], an $\tilde{\mathcal{O}}(\sqrt{T})$ regret can
be achieved with probability at least $1-\delta$. In other words, these
algorithms may not converge to the optimal one or could even be destablizing
with a non-zero probability $\delta$. In practice, such a failure probability
may hinder the application of these algorithms in safety-critical scenarios.
From a theoretical perspective, we argue that it is highly difficult to extend
these algorithms to provide stronger performance guarantees. To be specific,
despite different exploration strategies, the aforementioned methods all
compute the control input using a linear feedback gain synthesized from a
least-squares estimate of system parameters. Due to Gaussian process noise,
the derived linear feedback gain may be destabilizing, regardless of the
amount of data collected. For these algorithms, the probability of such
catastrophic event is bounded by a positive $\delta>0$, which is a
predetermined design parameter and cannot be changed during online operation.

Alternative methods that may preclude the above described failure probability
include introducing additional stability assumptions, using parameter
estimation algorithms with stronger convergence guarantees, and adding a layer
of safeguard around the linear feedback gain. Faradonbeh et al. [10] achieves
$\tilde{\mathcal{O}}(\sqrt{T})$ regret almost surely under the assumption that
the closed-loop system remains stable all the time, based on a stabilization
set obtained from adaptive stabilization [12]. Since the stabilization set is
estimated from finite data and violates the desired property with a nonzero
probability, this method essentially has a nonzero failure probability as
well. Guo [13] achieves sub-linear regret almost surely by adopting a variant
of ordinary least squares with annealing weight assigned to recent data, a
parameter estimation algorithm convergent even with unstable trajectory data.
However, the stronger convergence guarantee may come at the cost of less sharp
asymptotic rate, and it is unclear whether the regret of this method can
achieve $\tilde{\mathcal{O}}(\sqrt{T})$ dependence on time. Wang et al. [11]
achieves $\tilde{\mathcal{O}}(\sqrt{T})$ regret with a convergence-in-
probability guarantee, via the use of a switched, rather than linear feedback
controller, which falls back to a known stabilizing gain on the detection of
large states. However, the controller design of this work does not rule out
the frequent switching between the learned and fallback gains, a typical
source of instability in switched linear systems [14], which restricts the
correctness of their results to the case of commutative closed-loop system
matrices. Moreover, the regret analysis in this work is not sufficiently
refined to lead to almost sure guarantees.

TABLE I: Comparison with selected existing works on adaptive LQR

Work | Rate | Type of guarantee
---|---|---
[13] | Not provided | Almost sure
[7, 6, 9] | $\tilde{\mathcal{O}}(\sqrt{T})$ | Probability $1-\delta$
[10] | $\tilde{\mathcal{O}}(\sqrt{T})$ | Almost sure*
[11] | $\tilde{\mathcal{O}}(\sqrt{T})$ | Convergence in probability*
This work | $\tilde{\mathcal{O}}(\sqrt{T})$ | Almost sure

  * *

Requires non-standard assumptions; please refer to the main text for details.

In this paper, we present an adaptive LQR controller with
$\tilde{\mathcal{O}}(\sqrt{T})$ regret almost surely, only assuming the
availability of a known stabilizing feedback gain, which is a common
assumption in the literature. This is achieved by a “circuit-breaking”
mechanism motivated similarly as [11], which circumvents safety breach by
supervising the norm of the state and deploying the feedback gain when
necessary. In contrast to [11], however, by enforcing a properly chosen dwell
time on the fallback mode, the stability of the closed-loop system under our
proposed controller is unaffected by switching. Another insight underlying our
analysis is that the above mentioned circuit-breaking mechanism is triggered
only finitely often. This fact implies that the conservativeness of the
proposed controller, which prevents the system from being destabilized in the
early stage and hence ensures the convergence of the system parameter
estimates, may have negligible effect on the asymptotic performance of the
system. Although similar phenomena have also been observed in [15, 11], we
derive an upper bound on the time of the last trigger (Theorem 3, item 27)), a
property missing from pervious works that paves the way to our almost sure
regret guarantee.

### Outline

The remainder of this manuscript is organized as follows: Section II
introduces the problem setting. Section III describes the proposed controller.
Section IV states and proves the theoretical properties of the closed-loop
system under the proposed controller, and establishes the main regret upper
bound. Section V validates the theoretical results using a numerical example.
Finally, Section VI summarizes the manuscript and discusses directions for
future work.

### Notations

The set of nonnegative integers is denoted by $\mathbb{N}$, and the set of
positive integers is denoted by $\mathbb{N}^{*}$. The $n$-dimensional
Euclidean space is denoted by $\mathbb{R}^{n}$, and the $n$-dimensional unit
sphere is denoted by $\mathbb{S}^{n}$. The $n\times n$ identity matrix is
denoted by $I_{n}$. For a square matrix $M$, $\rho(M)$ denotes the spectral
radius of $M$, and $\operatorname{tr}(M)$ denotes the trace of $M$. For a real
symmetric matrix $M$, $M\succ 0$ denotes that $M$ is positive definite. For
any matrix $M$, $M^{\dagger}$ denotes the Moore-Penrose inverse of $M$. For
two vectors $u,v\in\mathbb{R}^{n}$, $\langle u,v\rangle$ denotes their inner
product. For a vector $v$, $\|v\|$ denotes its 2-norm, and
$\|v\|_{P}=\|P^{1/2}v\|$ for $P\succ 0$. For a matrix $M$, $\|M\|$ denotes its
induced 2-norm, and $\|M\|_{F}$ denotes its Frobenius norm. For a random
vector $x$, $x\sim\mathcal{N}(\mu,\Sigma)$ denotes $x$ is Gaussian distributed
with mean $\mu$ and covariance $\Sigma$. For a random variable $X$,
$X\sim\chi^{2}(n)$ denotes $X$ has a chi-squared distribution with $n$ degrees
of freedom. $\mathbb{P}(\cdot)$ denotes the probability operator, and
$\mathbb{E}[\cdot]$ denotes the expectation operator.

For non-negative quantities $f,g$, which can be deterministic or random, we
say $f\lesssim g$ to denote that $f\leq C_{1}g+C_{2}$ for some universal
constants $C_{1}>0$ and $C_{2}>0$, and $f\gtrsim g$ to denote that $g\lesssim
f$. For a random function $f(T)$ and a deterministic function $g(T)$, we say
$f(T)=\mathcal{O}(g(T))$ to denote that
$\limsup_{T\to\infty}f(T)/g(T)<\infty$, and $f(T)=\tilde{\mathcal{O}}(g(T))$
to denote that $f(T)=\mathcal{O}(g(T)(\log(T))^{\alpha})$ for some $\alpha>0$.

##  II Problem formulation

This paper considers a fully observed discrete-time linear system with
Gaussian process noise specified as follows:

$x_{k+1}=Ax_{k}+Bu_{k}+w_{k},\quad k\in\mathbb{N}^{*},\quad x_{1}=0,$ (1)

where $x_{k}\in\mathbb{R}^{n}$ is the state, $u_{k}\in\mathbb{R}^{m}$ is the
control input, and $w_{k}\stackrel{{\scriptstyle\text{ i.i.d.
}}}{{\sim}}\mathcal{N}(0,W)$ is the process noise, where $W\succ 0$. It is
assumed without loss of generality that $W=I_{n}$, but all the conclusions
apply to general positive definite $W$ up to the scaling of constants. It is
also assumed that the system and input matrices $A,B$ are unknown to the
controller, but $(A,B)$ is controllable, and that the system is open-loop
stable, i.e., $\rho(A)<1$. Consequently, there exists $P_{0}\succ 0$ that
satisfies the discrete Lyapunov equation

$A^{\top}P_{0}A-P_{0}+Q=0,$ (2)

and there exists a scalar $0<\rho_{0}<1$ such that

$A^{\top}P_{0}A\prec\rho_{0}P_{0}.$ (3)

######  Remark 1.

It has been commonly assumed in the literature [9, 11] that $(A,B)$ being
stabilizable by a known feedback gain $K_{0}$, i.e., $\rho(A+BK_{0})<1$. In
such case, the system can be rewritten as

$x_{k+1}=A^{\prime}x_{k}+Bu_{k}^{\prime}+w_{k},$ (4)

where $A^{\prime}=A+BK_{0},u_{k}^{\prime}=u_{k}-K_{0}x_{k}$, which reduces the
problem to the case of open-loop stable systems. Therefore, we may assume
without loss of generality that the system is open-loop stable, i.e.,
$K_{0}=0$, for the simplicity of notations.

The following average infinite-horizon quadratic cost is considered:

$J=\limsup_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\sum_{k=1}^{T}x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k}\right],$
(5)

where $Q\succ 0,R\succ 0$ are fixed weight matrices specified by the system
operator. It is well known that the optimal control law is the linear feedback
control law of the form $u(x)=K^{*}x$, where the optimal feedback gain $K^{*}$
can be specified as:

$K^{*}=-\left(R+B^{\top}P^{*}B\right)^{-1}B^{\top}P^{*}A,$ (6)

and $P^{*}$ is the unique positive definite solution to the discrete algebraic
Riccati equation

$P^{*}=A^{\top}P^{*}A-A^{\top}P^{*}B\left(R+B^{\top}P^{*}B\right)^{-1}B^{\top}P^{*}A+Q.$
(7)

The corresponding optimal cost is

$J^{*}=\operatorname{tr}\left(\mathbb{E}\left[w_{k}w_{k}^{\top}\right]P^{*}\right)=\operatorname{tr}(WP^{*})=\operatorname{tr}(P^{*}).$
(8)

The matrix $P^{*}$ also satisfies the discrete Lyapunov equation

$(A+BK^{*})^{\top}P^{*}(A+BK^{*})-P^{*}+Q+K^{\top}RK=0,$ (9)

which implies that there exists a scalar $0<\rho^{*}<1$ such that

$(A+BK^{*})^{\top}P^{*}(A+BK^{*})\prec\rho^{*}P^{*}.$ (10)

Since $A,B$ are unknown to the controller in the considered setting, it is not
possible to directly compute the optimal control law from (6) and (7).
Instead, the controller learns the optimal control law online, whose
performance is measured via the _regret_ defined as follows:

$\mathcal{R}(T)=\sum_{k=1}^{T}(x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k})-TJ^{*}.$
(11)

The goal of the controller is to minimize the asymptotic growth of
$\mathcal{R}(T)$.

##  III Controller design

The logic of the proposed controller is presented in Algorithm 1. It can also
be illustrated by the block diagram in Fig. 1. The remainder of this section
would be devoted to explaining the components of the controller:

1:$\hat{K}_{0}\leftarrow 0$

2:$\xi\leftarrow 0$

3:for $k=1,2,\ldots$ do

4: Update parameter estimates $\hat{A}_{k},\hat{B}_{k}$ using (12)

5: if $(\hat{A}_{k},\hat{B}_{k})$ is controllable then

6: Update $\hat{K}_{k}$ from (6)-(7), replacing $(A,B)$ with
$(\hat{A}_{k},\hat{B}_{k})$.

7: else

8: $\hat{K}_{k}\leftarrow 0$

9: $u^{ce}_{k}\leftarrow\hat{K}_{k}x_{k}$

10: if $\xi=0$ then

11: if $\|u^{ce}_{k}\|>M_{k}:=\log(k)$ then

12: $\xi\leftarrow t_{k}:=\lfloor\log(k)\rfloor$

13: $u^{cb}_{k}\leftarrow 0$

14: else

15: $u^{cb}_{k}\leftarrow u^{ce}_{k}$

16: else

17: $u^{cb}_{k}\leftarrow 0$

18: $\xi\leftarrow\xi-1$

19: $u^{pr}_{k}\leftarrow k^{-1/4}v_{k}$, where
$v_{k}\sim\mathcal{N}(0,I_{m})$

20: Apply $u_{k}\leftarrow u^{cb}_{k}+u^{pr}_{k}$

Algorithm 1 Proposed controller Figure 1: Block diagram of the closed-loop
system under the proposed controller. The control input is the superposition
of a deterministic input $u^{cb}$ and a random probing input $u^{pr}$. The
deterministic part $u^{cb}$ is normally the same as the certainty equivalent
input $u^{ce}$, but takes the value zero when circuit-breaking is triggered,
where $\xi$ is a counter for circuit-breaking. The certainty equivalent gain
is updated using the parameter estimator in the meantime.

The proposed controller is a variant of the certainty equivalent controller
[16], where the latter applies the input $u^{ce}_{k}=\hat{K}_{k}x_{k}$, where
the feedback gain $\hat{K}_{k}$ is calculated from (6)-(7) by treating the
current estimates of the system parameters $\hat{A}_{k},\hat{B}_{k}$ as the
true values. The differences of the proposed controller compared to the
standard certainty equivalent controller is that i) it includes a “circuit-
breaking” mechanism, which replace $u^{ce}_{k}$ with zero in certain
circumstances; ii) it superposes the control input at each step with a probing
noise $u^{pr}_{k}$.

The circuit-breaking mechanism replaces $u^{ce}_{k}$ with zero for the
subsequent $t_{k}$ steps when the norm of the certainty equivalent control
input $\|u^{ce}_{k}\|$ exceeds a threshold $M_{k}$. The intuition behind this
design is that a large certainty equivalent control input is indicative of
having applied a destabilizing feedback gain recently, and circuit-breaking
may prevent the state from exploding by leveraging the innate stability of the
system, and hence help with the convergence of the parameter estimator and the
asymptotic performance of the controller. The threshold $M_{k}$ is increased
with the time index $k$, so that the “false alarm rate” of circuit-breaking,
caused by the occasional occurrence of large noise vectors, decays to zero.
The dwell time $t_{k}$ is also increased with time, in order to circumvent the
potential oscillation of the system caused by the frequent switching between
$\hat{K}$ and $0$ (c.f. [17]). Both $M_{k}$ and $t_{k}$ are chosen to grow
logarithmically with $k$, which would support our technical guarantees.

Similarly to [9, 11], a probing noise $u_{k}^{pr}$ is superposed to the
control input at each step to provide sufficient excitation to the system,
which is required for the estimation of system parameters. Specifically, the
probing noise is chosen to be $u_{k}^{pr}=k^{-1/4}v_{k}$, where
$v_{k}\stackrel{{\scriptstyle\text{ i.i.d. }}}{{\sim}}\mathcal{N}(0,I_{m})$,
which would correspond to the optimal rate of regret.

The estimates of the system parameters $\hat{A}_{k},\hat{B}_{k}$ are updated
using an ordinary least squares estimator. Denote $\Theta=[A\quad B]$,
$\hat{\Theta}_{k}=[\hat{A}_{k}\quad\hat{B}_{k}]$, and
$z_{k}=[x_{k}^{\top}\quad u_{k}^{\top}]^{\top}$, then according to
$x_{k+1}=\Theta z_{k}$, the ordinary least squares estimator can be specified
as

$\hat{\Theta}_{k}=\left(\sum_{t=1}^{k-1}x_{t}z_{t}^{\top}\right)\left(\sum_{t=1}^{k-1}z_{t}z_{t}^{\top}\right)^{\dagger}.$
(12)

######  Remark 2.

In the presented algorithm, the certainty equivalent gain is updated at every
step $k$ (see line 6 of Algorithm 1), but it may also be updated
“logarithmically often” [11] (e.g., at steps $k=2^{i},i\in\mathbb{N}^{*}$),
which is more computationally efficient in practice. It can be verified that
all our theoretical results also apply to the case of logarithmically often
updates.

##  IV Main results

Underlying our analysis of the closed-loop system under the proposed
controller are two random times, defined below:

$\displaystyle T_{\text{stab}}:=\inf\left\\{T\vphantom{\left(A^{\lfloor\log
k\rfloor}\right)^{\top}}\right.\left|\left(A^{t_{k}}\right)^{\top}P^{*}A^{t_{k}}<\rho
P^{*},\right.$ $\displaystyle\mkern
10.0mu\left.\vphantom{\left(A^{t_{k}}\right)^{\top}}\left(A+B\hat{K}_{k}\right)^{\top}P^{*}\left(A+B\hat{K}_{k}\right)<\rho
P^{*},\forall k\geq T\right\\},$ (13)

where $\rho=(1+\rho^{*})/2$, and $t_{k}$ is the dwell time defined in line 12
of Algorithm 1. And

$T_{\text{nocb}}:=\inf\left\\{T\mid u_{k}^{cb}\equiv u_{k}^{ce},\forall k\geq
T\right\\}.$ (14)

With the above two random times, the evolution of the system can be divided
into three stages:

  1. 1.

From the beginning to $T_{\text{stab}}$, the adaptive controller gradually
refines its estimate of system parameters, and hence improves the performance
of the certainty equivalent feedback gain, until the system becomes stabilized
in the sense that there is a common Lyapunov function between the two modes
under circuit-breaking as indicated in (13).

  2. 2.

From $T_{\text{stab}}$ to $T_{\text{nocb}}$, the closed-loop system is stable
as is ensured by the aforementioned common Lyapunov function, and under mild
regularity conditions on the noise, an upper bound on the magnitude certainty
equivalent control input $\|u^{ce}_{k}\|$ eventually drops below the circuit-
breaking threshold $M_{k}$.

  3. 3.

From $T_{\text{nocb}}$ on, circuit-breaking is not triggered any more, and the
system behaves similarly as the closed-loop system under the optimal
controller, with only small perturbations on the feedback gain which stem from
the parameter estimation error and converge to zero.

In the following theorem, we state several properties of the closed-loop
system, based on which the above two random times are quantified:

######  Theorem 3.

Let $n,m$ be the dimensions of the state and input vectors respectively, and
$P_{0},\rho_{0},P^{*},\rho^{*}$ be defined in (2), (3), (7), (10)
respectively. Then the following properties hold:

  1. 1.

For $0<\delta\leq 1/2$, the event

$\displaystyle\mathcal{E}_{\text{noise}}(\delta):=\left\\{\max\\{\|w_{k}\|,\|v_{k}\|\\}\leq\vphantom{\sqrt{()}}\right.$
$\displaystyle\mkern 100.0mu\left.2\sqrt{n+1}\sqrt{\log(k/\delta)},\forall
k\in\mathbb{N}^{*}\right\\}$ (15)

occurs with probability at least $1-2\delta$.

  2. 2.

For $0<\delta\leq 1/(8n^{2})$, the event

$\displaystyle\mathcal{E}_{\text{cov}}(\delta):=\left\\{\left\|\sum_{i=1}^{k}(w_{i}w_{i}^{\top}-I_{n})\right\|\leq\right.$
$\displaystyle\mkern 100.0mu\left.7n\sqrt{k}\log(8n^{2}k/\delta),\forall
k\in\mathbb{N}^{*}\vphantom{\sum_{i}^{i}}\right\\}$ (16)

occurs with probability at least $1-\delta$.

  3. 3.

On the event $\mathcal{E}_{\text{noise}}(\delta)$, it holds

$\|x_{k}\|\leq C_{x}\log(k/\delta),\forall k\in\mathbb{N}^{*},$ (17)

where

$C_{x}=\frac{(\|B\|+1)(2\sqrt{n+1}+1)\|P_{0}\|\|P_{0}^{-1}\|}{1-\rho_{0}^{1/2}}.$
(18)

  4. 4.

For $0<\delta\leq 1/6$, the event

$\displaystyle\mathcal{E}_{\text{cross}}(\delta):=\left\\{\left\|\sum_{i=1}^{k}w_{i}^{\top}P^{*}(Ax_{i}+Bu^{cb}_{i})\right\|\leq\right.$
$\displaystyle\mkern
100.0mu\left.C_{\text{cross}}\sqrt{k}(\log(k/\delta))^{2},\forall
k\in\mathbb{N}^{*}\vphantom{\sum_{i}^{i}}\right\\}$ (19)

occurs with probability at least $1-6\delta$, where

$C_{\text{cross}}=4\sqrt{n+1}\|P^{*}\|(\|A\|C_{x}+\|B\|).$ (20)

  5. 5.

For $\delta$ satisfying

$0<\delta<\min\left\\{(800C_{V})^{-1},\exp\left(24(m+n)^{1/3}\right)\right\\},$
(21)

the event

$\displaystyle\mathcal{E}_{\text{est}}(\delta):=\left\\{\left\|\hat{\Theta}_{k}-\Theta\right\|^{2}\leq
C_{\Theta}k^{-1/2}\log(k/\delta),\right.$ $\displaystyle\mkern
100.0mu\left.\vphantom{\left\|\hat{\Theta}_{k}-\Theta\right\|^{2}}\forall
k\geq k_{0}\right\\},$ (22)

occurs with probability at least $1-6\delta$, where

$\displaystyle k_{0}=\lceil 600(m+n)\log(1/\delta)+5400\rceil,$ (23)
$\displaystyle C_{V}=C_{x}+2\sqrt{n+1}+1,$ (24) $\displaystyle
C_{\Theta}=(3200n/9)(5n/2+2).$ (25)

  6. 6.

On the event $\mathcal{E}_{\text{est}}(\delta)$, it holds

$T_{\text{stab}}\lesssim(\log(1/\delta))^{2}.$ (26)

  7. 7.

On the event
$\mathcal{E}_{\text{noise}}(\delta)\cap\mathcal{E}_{\text{est}}(\delta)$, for
any $\alpha>0$, it holds

$T_{\text{nocb}}\lesssim(1/\delta)^{\alpha}.$ (27)

######  Remark 4.

The conclusions of Theorem 3 can be explained as follows:

Items 1) and 2) defines two high-probability events on the regularity of
noise. Item 18) bounds the state norm under regular noise, based on which item
20) bounds the growth of a cross term between noise and state that would be
useful in regret analysis. Item 5) bounds the parameter estimation error,
based on which item 26) bounds $T_{\text{stab}}$. Finally, item 27) states
that the circuit-breaking mechanism is triggered only _finitely_ , and bounds
$T_{\text{nocb}}$, the time after which the circuit-breaking is not triggered
any more.

The following corollary characterizes the tail probabilities of
$T_{\text{stab}}$ and $T_{\text{nocb}}$, which follows directly from items 26)
and 27) of Theorem 3:

######  Corollary 5.

For $T_{\text{stab}}$ defined in (13) and $T_{\text{nocb}}$ defined in (14),
as $T\to\infty$, it holds

  1. 1.

$\mathbb{P}(T_{\text{stab}}\geq T)=\mathcal{O}(\exp(-c\sqrt{T})),$ (28)

where $c>0$ is a system-dependent constant.

  2. 2.

For any $\alpha>0$,

$\mathbb{P}(T_{\text{nocb}}\geq T)=\mathcal{O}(T^{-\alpha}).$ (29)

Building upon the properties stated in Theorem 3, a high-probability bound on
the regret under the proposed controller can be ensured:

######  Theorem 6.

Given a failure probability $\delta$, there exists a constant
$T_{0}\lesssim(1/\delta)^{1/4}$, such that for any fixed $T>T_{0}$, it holds
with probability at least $1-\delta$ that the regret defined in (11) satisfies

$\mathcal{R}(T)\lesssim(1/\delta)^{1/4}+\sqrt{T}(\log(T/\delta))^{3}.$ (30)

As corollaries of Theorem 30, one can obtain a bound on the tail probability
of $\mathcal{R}(T)$ (Theorem 7), and the main conclusion of this work, i.e.,
an almost sure bound on $\mathcal{R}(T)$ (Theorem 32):

######  Theorem 7.

For sufficiently large $T$, it holds

$\mathbb{P}\left(\mathcal{R}(T)\geq
C_{R}\sqrt{T}(\log(T))^{3}\right)\leq\frac{1}{T^{2}},$ (31)

where $C_{R}$ is a system-dependent constant.

###### Proof.

The conclusion follows from invoking Theorem 30 with $\delta=1/T^{2}$. ∎

######  Theorem 8.

It holds almost surely that

$\mathcal{R}(T)=\tilde{\mathcal{O}}\left(\sqrt{T}\right).$ (32)

###### Proof.

By Theorem 7, we have

$\sum_{T=1}^{\infty}\mathbb{P}\left(\mathcal{R}(T)\geq
C_{R}\sqrt{T}(\log(T))^{3}\right)<+\infty.$ (33)

By Borel-Cantelli lemma, it holds almost surely that the event

$\left\\{\mathcal{R}(T)\geq C_{R}\sqrt{T}(\log(T))^{3}\right\\}$ (34)

occurs finitely often, i.e.,

$\mathcal{R}(T)=\tilde{\mathcal{O}}\left(\sqrt{T}\right),\quad\text{a.s.}$
(35)

∎

The remainder of this section is dedicated to proving Theorems 3 and 30.

###  IV-A Proof of Theorem 3, item 1)

###### Proof.

Since $w_{k}\sim\mathcal{N}(0,I_{n})$, it holds
$\left\|w_{k}\right\|\sim\chi^{2}(n)$. Applying the Chernoff bound, for any
$a>0$, and any $0<t<1/2$, it holds

$\mathbb{P}(X\geq
a)\leq\mathbb{E}\left[\mathrm{e}^{tX}/\mathrm{e}^{ta}\right]=(1-2t)^{-n/2}\exp(-ta).$
(36)

Choosing $t=1/4$, we have

$\mathbb{P}(\|w_{k}\|\geq a)\leq 2^{n/2}\exp(-a^{2}/4)$ (37)

for any $k\in\mathbb{N}^{*}$ and $a>0$. Invoking (37) with
$a_{k}=2(\log(ck^{2}/\delta))^{1/2}$, where $c=2^{n/2}\pi^{2}/6$, we have

$\sum_{k=1}^{\infty}\mathbb{P}(\|w_{k}\|\geq
a_{k})\leq\sum_{k=1}^{\infty}2^{n/2}c^{-1}\delta/k^{2}=\delta,$ (38)

i.e., it holds with probability at least $1-\delta$ that

$\|w_{k}\|\leq 2(\log(ck^{2}/\delta))^{1/2}\leq
2\sqrt{n+1}\sqrt{\log(k/\delta)},\forall k\in\mathbb{N}^{*}.$ (39)

Similarly, it also holds with probability at least $1-\delta$ that

$\|v_{k}\|\leq 2\sqrt{n+1}\sqrt{\log(k/\delta)},\forall k\in\mathbb{N}^{*}.$
(40)

Combining (39) and (40) leads to the conclusion. ∎

###  IV-B Proof of Theorem 3, item 2)

We start with a concentration bound on the sum of product of Gaussian random
variables:

######  Lemma 9.

Let $X_{i}\stackrel{{\scriptstyle\text{ i.i.d. }}}{{\sim}}\mathcal{N}(0,1)$,
$Y_{i}\stackrel{{\scriptstyle\text{ i.i.d. }}}{{\sim}}\mathcal{N}(0,1)$, and
$\\{X_{i}\\},\\{Y_{i}\\}$ be mutually independent, then

  1. 1.

With probability at least $1-4\delta$,

$\left|\sum_{i=1}^{k}X_{i}^{2}-k\right|\leq 7\sqrt{k}\log(k/\delta),\forall
k\in\mathbb{N}^{*}.$ (41)

  2. 2.

With probability at least $1-8\delta$,

$\left|\sum_{i=1}^{k}X_{i}Y_{i}\right|\leq 5\sqrt{k}\log(k/\delta),\forall
k\in\mathbb{N}^{*}.$ (42)

###### Proof.

Since $\sum_{i=1}^{k}X_{i}^{2}\sim\chi^{2}(k)$, according to [18, Lemma 1],
for any $a>0$ and any $k\in\mathbb{N}^{*}$, it holds

$\mathbb{P}\left(\left|\sum_{i=1}^{k}X_{i}^{2}-k\right|\geq
2\sqrt{na}+2a\right)\leq 2\exp(-a).$ (43)

Fix $k$ and choose $a=\log(k^{2}/\delta)$, and it follows that with
probability at least $1-2\delta/k^{2}$,

$\displaystyle\left|\sum_{i=1}^{k}X_{i}^{2}-k\right|$ $\displaystyle\leq
2\sqrt{k\log(k^{2}/\delta)}+2\log(k^{2}/\delta)$ $\displaystyle\leq
7\sqrt{k}\log(k/\delta).$ (44)

Taking the union bound over $k\in\mathbb{N}^{*}$, one can show that (41) holds
with probability at least $1-2\delta\sum_{k=1}^{\infty}(1/k^{2})>1-4\delta$,
and hence claim 41) is proved.

Since $X_{i}Y_{i}=(X_{i}+Y_{i})^{2}/4+(X_{i}-Y_{i})^{2}/4$, and
$X_{i}+Y_{i}\stackrel{{\scriptstyle\text{ i.i.d. }}}{{\sim}}\mathcal{N}(0,2)$,
$X_{i}-Y_{i}\stackrel{{\scriptstyle\text{ i.i.d. }}}{{\sim}}\mathcal{N}(0,2)$,
claim 42) follows from applying claim 41) to $\\{(X_{i}+Y_{i})/\sqrt{2}\\}$
and $\\{(X_{i}-Y_{i})/\sqrt{2}\\}$ respectively and taking the union bound. ∎

Theorem 3, item 2) follows from the above lemma:

###### Proof.

Applying Lemma 9, item 41) to the diagonal elements, and Lemma 9, item 42) to
the off-diagonal elements of $\sum_{i=1}^{k}(w_{i}w_{i}^{\top}-I)$, and taking
the union bound, one can show that with probability at least $1-8n^{2}\delta$,

$\sum_{i=1}^{k}(w_{i}w_{i}^{\top}-I_{n})\leq 7\sqrt{k}\log(k/\delta),$ (45)

where the inequality holds component-wise. Hence, with probability at least
$1-8n^{2}\delta$,

$\displaystyle\left\|\sum_{i=1}^{k}(w_{i}w_{i}^{\top}-I_{n})\right\|^{2}$
$\displaystyle\leq\left\|\sum_{i=1}^{k}(w_{i}w_{i}^{\top}-I_{n})\right\|_{F}^{2}$
$\displaystyle\leq n^{2}(7\sqrt{k}\log(k/\delta)),$ (46)

and scaling the failure probability leads to the conclusion. ∎

###  IV-C Proof of Theorem 3, item 18)

###### Proof.

Notice

$x_{k}=A^{k-2}d_{1}+A^{k-3}d_{2}+\cdots+d_{k-1},$ (47)

where $d_{k}=B(u^{cb}_{k}+u^{pr}_{k})+w_{k}$. On
$\mathcal{E}_{\text{noise}}(\delta)$, it holds

$\displaystyle\|d_{k}\|$
$\displaystyle\leq\|B\|\log(k)+2(\|B\|+1)\sqrt{n+1}\sqrt{\log(k/\delta)}$
$\displaystyle\leq(\|B\|+1)(2\sqrt{n+1}+1)\log(k/\delta).$ (48)

Furthermore, from (2) and (47), it holds

$\displaystyle\|x_{k}\|_{P}$
$\displaystyle\leq\rho_{0}^{(k-2)/2}\|d_{1}\|_{P}+\rho_{0}^{(k-3)/2}\|d_{2}\|_{P}+\cdots+\|d_{k-1}\|_{P}$
$\displaystyle\leq\frac{1}{1-\rho_{0}^{1/2}}\|d_{k}\|_{P},$ (49)

from which the conclusion follows. ∎

###  IV-D Proof of Theorem 3, item 20)

This result is a corollary of a time-uniform version of Azuma-Hoeffding
inequality [19], stated below:

######  Lemma 10.

Let $\\{\phi_{k}\\}_{k\geq 1}$ be a martingale difference sequence adapted to
the filtration $\\{\mathcal{F}_{k}\\}$ satisfying $|\phi_{k}|\leq d_{k}$ a.s.,
then with probability at least $1-4\delta$, it holds

$\left|\sum_{i=1}^{k}\phi_{i}\right|\leq
2\sqrt{\sum_{i=1}^{k}d_{i}^{2}\log(k/\delta)},\forall k.$ (50)

###### Proof.

By Azuma-Hoeffding inequality [19], for a fixed $k$, it holds with probability
at least $1-2\delta/k^{2}$ that

$\left|\sum_{i=1}^{k}\phi_{i}\right|\leq\sqrt{2\sum_{i=1}^{k}d_{i}^{2}\log(k^{2}/\delta)}\leq
2\sqrt{\sum_{i=1}^{k}d_{i}^{2}\log(k/\delta)}.$ (51)

Taking the union bound over $k\in\mathbb{N}^{*}$, one can prove that (50)
holds with probability at least
$1-2\delta\sum_{k=1}^{\infty}(1/k^{2})>1-4\delta$. ∎

Theorem 3, item 20) follows from the above lemma:

###### Proof.

According to Theorem 3, item 1), we only need to prove

$\mathbb{P}(\mathcal{E}_{\text{cross}}(\delta)\mid\mathcal{E}_{\text{noise}}(\delta))\geq
1-4\delta.$ (52)

Therefore, we condition the remainder of the proof upon the event
$\mathcal{E}_{\text{noise}}(\delta)$. Let $\mathcal{F}_{k}$ be the
$\sigma$-algebra generated by $v_{1},\allowbreak w_{1},\allowbreak
v_{2},w_{2},\ldots,\allowbreak v_{k-1},\allowbreak w_{k-1},v_{k}$. Since
$x_{k}\in\mathcal{F}_{k-1}$, $u_{k}^{cb}\in\mathcal{F}_{k-1}$,
$\mathbb{E}[w_{k}\mid\mathcal{F}_{k-1}]=0$ due to symmetry, it holds

$\displaystyle\mathbb{E}\left[w_{k}^{\top}P^{*}\left(Ax_{k}+Bu_{k}^{cb}\right)\big{|}\mathcal{F}_{k}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[w_{k}\mid\mathcal{F}_{k-1}\right]^{\top}P^{*}\left(Ax_{k}+Bu_{k}^{cb}\right)=0,$
(53)

i.e., $\\{w_{k}^{\top}P^{*}(Ax_{k}+Bu_{k}^{cb})\\}$ is a martingale difference
sequence adapted to the filtration $\\{\mathcal{F}_{k}\\}$. Furthermore, by
Theorem 3, item 18, we have

$\displaystyle\left\|w_{k}^{\top}P^{*}\left(Ax_{k}+Bu_{k}^{cb}\right)\right\|$
$\displaystyle\leq$
$\displaystyle\|w_{k}\|\|P^{*}\|\left(\|A\|\|x_{k}\|+\|B\|\left\|u_{k}^{cb}\right\|\right)$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}C_{\text{cross}}\log(k/\delta).$
(54)

Hence, the conclusion follows from applying Lemma 50. ∎

###  IV-E Proof of Theorem 3, item 5)

This subsection is devoted to deriving the time-uniform upper bound on
estimation error stated in Theorem 3, item 5). Throughout this subsection, we
denote $\Theta=[A\quad B]$, $\hat{\Theta}_{k}=[\hat{A}_{k}\quad\hat{B}_{k}]$,
$z_{k}=[x_{k}^{\top}\quad u_{k}^{\top}]^{\top}$, and
$V_{k}=\sum_{i=1}^{k-1}z_{i}z_{i}^{\top}$.

The proof can be split into three parts: firstly, we characterize the
estimation error $\|\hat{\Theta}_{k}-\Theta\|$ in terms of the maximum and
minimum eigenvalues of the regressor covariance matrix $V_{k}$, using a result
in martingale least squares [5]. Secondly, an upper bound on the $\|V_{k}\|$,
which is a consequence of the non-explosiveness of states, can be derived as
an corollary of Theorem 3, item 18). Finally, an upper bound on
$\|V_{k}^{-1}\|$, or equivalently a lower bound on the minimum eigenvalue of
$V_{k}$, which is a consequence of sufficient excitation of the system, can be
proved using an anti-concentration bound on block martingale small-ball (BMSB)
processes [20]. The three parts would be discussed respectively below.

####  IV-E1 Upper bound on least squares error, in terms of $V_{k}$

######  Lemma 11 ([5, Corollary 1 of Theorem 3]).

Let

$S_{k}=\sum_{i=1}^{k}\eta_{i}m_{i-1},U_{k}=\sum_{i=1}^{k}m_{i-1}m_{i-1}^{\top},$
(55)

where $\\{\mathcal{F}_{k}\\}_{k\in\mathbb{N}^{*}}$ is a filtration,
$\\{\eta_{k}\\}_{k\in\mathbb{N}^{*}}$ is a random scalar sequence with
$\eta_{k}\mid\mathcal{F}_{k}$ being conditionally $\sigma^{2}$-sub-Gaussian,
and $\\{m_{k}\\}_{k\in\mathbb{N}^{*}}$ is a random vector sequence with
$m_{k}\in\mathcal{F}_{k}$. Then with probability at least $1-\delta$,

$\displaystyle\|S_{k}\|_{(U_{0}+U_{k})^{-1}}\leq 2\sigma^{2}\cdot$
$\displaystyle\quad\log\left(\det(U_{0})^{-1/2}\det(U_{0}+U_{k})^{1/2}/\delta\right),\quad\forall
k\in\mathbb{N}^{*},$ (56)

where $U_{0}\succ 0$ is an arbitrarily chosen constant positive semi-definite
matrix.

######  Proposition 12.

With probability at least $1-\delta$,

$\displaystyle\left\|\hat{\Theta}_{k}-\Theta\right\|^{2}\leq
2n\left\|V_{k}^{-1}\right\|\left[\log\left(\frac{n}{\delta}\right)+\frac{n}{2}\log(1+\|V_{k}\|)\right],$
$\displaystyle\forall k\geq m+n+1.$ (57)

###### Proof.

Let $\mathcal{F}_{k}$ be the $\sigma$-algebra generated by $v_{1},\allowbreak
w_{1},\allowbreak v_{2},\allowbreak w_{2},\allowbreak\ldots,\allowbreak
v_{k-1},\allowbreak w_{k-1},v_{k}$. From $x_{k+1}=\Theta z_{k}+w_{k}$, we have

$\hat{\Theta}_{k}-\Theta=\left(\sum_{i=1}^{k-1}w_{i}z_{i}^{\top}\right)\left(\sum_{i=1}^{k-1}z_{i}z_{i}^{\top}\right)^{\dagger},$
(58)

where $w_{k}|\mathcal{F}_{k}\sim\mathcal{N}(0,I_{n}),z_{k}\in\mathcal{F}_{k}$.
With $V_{k}=\sum_{i=1}^{k-1}z_{i}z_{i}^{\top}$, we have $V_{i}\succ 0$ a.s.
for $k\geq m+n+1$. Now we can apply Lemma 11 to each row of
$\hat{\Theta}_{k}-\Theta$: for each of $j=1,\ldots,n$, let
$S_{j,k}=\sum_{i=1}^{k-1}(e_{j}^{\top}w_{i})z_{i}$, where $e_{j}$ is the
$j$-th standard unit vector. By invoking Lemma 11 with $U_{k}=V_{k}$ and
$U_{0}=I_{m+n}$, we have: with probability at least $1-\delta$,

$\displaystyle\left\|e_{j}^{\top}(\hat{\Theta}_{k}-\Theta)\right\|^{2}=\left\|V_{k}^{-1}S_{j,k}\right\|\leq\left\|V_{k}^{-1}\right\|\|S_{j,k}\|_{(I+V_{k})^{-1}}$
$\displaystyle\leq
2\left\|V_{k}^{-1}\right\|\log\left(\det(I+V_{k})^{1/2}/\delta\right)$
$\displaystyle\leq
2\left\|V_{k}^{-1}\right\|\left[\log\left(\frac{1}{\delta}\right)+\frac{n}{2}\log(1+\|V_{k}\|)\right].$
(59)

Taking the union bound over $j=1,\ldots,n$, we have: with probability at least
$1-n\delta$,

$\displaystyle\left\|\hat{\Theta}_{k}-\Theta\right\|^{2}\leq\left\|\hat{\Theta}_{k}-\Theta\right\|_{F}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{n}\left\|e_{j}^{\top}(\hat{\Theta}_{k}-\Theta)\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
2n\left\|V_{k}^{-1}\right\|\left[\log\left(\frac{1}{\delta}\right)+\frac{n}{2}\log(1+\|V_{k}\|)\right].$
(60)

Scaling the failure probability results in the conclusion. ∎

####  IV-E2 Upper bound on $\|V_{k}\|$

######  Proposition 13.

On the event $\mathcal{E}_{\text{noise}}(\delta)$ defined in (15), it holds

$\|V_{k}\|\leq C_{V}k(\log(k/\delta))^{2},$ (61)

where $C_{V}$ is defined in (24).

###### Proof.

On $\mathcal{E}_{\text{noise}}(\delta)$, we have

$\|u_{k}\|\leq\log(k)+2\sqrt{n+1}\sqrt{\log(k/\delta)},$ (62)

and by Theorem 3, item 18), we have

$\|x_{k}\|\leq C_{x}\log(k/\delta).$ (63)

Hence,

$\|z_{k}\|\leq\|x_{k}\|+\|u_{k}\|\leq\sqrt{C_{V}}\log(k/\delta),$ (64)

which implies

$\|V_{k}\|\leq\sum_{i=1}^{k-1}\|z_{k}\|^{2}\leq C_{V}k(\log(k/\delta))^{2}.$
(65)

∎

####  IV-E3 Upper bound on $\|V_{k}^{-1}\|$

We shall borrow the techniques of analyzing BMSB processes from Simchowitz et
al. [20] to bound $\|V_{k}^{-1}\|$. The BMSB process is defined as follows:

######  Definition 14 ([20, Definition 2.1]).

Suppose that $\left\\{\phi_{k}\right\\}_{k\in\mathbb{N}^{*}}$ is a real-valued
stochastic process adapted to the filtration
$\left\\{\mathcal{F}_{k}\right\\}$. We say the process
$\left\\{\phi_{k}\right\\}$ satisfies the $(l,\nu,p)$ block martingale small-
ball (BMSB) condition if:

$\frac{1}{l}\sum_{i=1}^{l}\mathbb{P}\left(\left|\phi_{k+i}\right|\geq\nu\mid\mathcal{F}_{t}\right)\geq
p,\forall k\in\mathbb{N}^{*}.$ (66)

The following lemma verifies that $\\{z_{k}\\}$, projected along an arbitrary
direction, is BMSB:

######  Lemma 15.

For any $\mu\in\mathbb{S}^{m+n}$, the process $\\{\langle
z_{i},\mu\rangle\\}_{i=1}^{k-1}$ satisfies the $(1,k^{-1/4},3/10)$ BMSB
condition.

###### Proof.

Let $\mathcal{F}_{k}$ be the $\sigma$-algebra generated by $v_{1},\allowbreak
w_{1},\allowbreak v_{2},\allowbreak w_{2},\allowbreak\ldots,\allowbreak
v_{k-1},\allowbreak w_{k-1},v_{k}$. Since

$z_{i}=\begin{bmatrix}x_{i}\\\ u_{i}\end{bmatrix}=\begin{bmatrix}x_{i}\\\
u_{i}^{cb}+u_{i}^{pr}\end{bmatrix},$ (67)

and $x_{i+1}=A_{i}x_{t}+Bu_{i}^{pr}+w_{i}$, where $A_{i}$ takes value from
$\\{A,A+B\hat{K}_{i}\\}$ and belongs to $\mathcal{F}_{i}$, we have

$\displaystyle|\langle z_{i+1},\mu\rangle|$ $\displaystyle=|\langle
x_{i+1},\mu_{1}\rangle+\langle u_{i+1}^{cb},\mu_{2}\rangle+\langle
u_{i+1}^{pr},\mu_{2}\rangle|$ $\displaystyle\geq|\langle
A_{i}x_{i}+Bu_{i}^{pr}+w_{i},\mu_{1}\rangle+\langle
u_{i+1}^{pr},\mu_{2}\rangle|$
$\displaystyle=\left|\Big{\langle}\begin{bmatrix}A_{i}x_{i}+Bu_{i}^{pr}+w_{i}\\\
u_{i+1}^{pr}\end{bmatrix},\mu\Big{\rangle}\right|,$ (68)

where $\mu_{1}=[I_{n}\quad 0]\mu,\mu_{2}=[0\quad I_{m}]\mu$. Therefore, we
only need to verify

$\mathbb{P}\left(\left|\Big{\langle}\begin{bmatrix}A_{i}x_{i}+Bu_{i}^{pr}+w_{i}\\\
u_{i+1}^{pr}\end{bmatrix},\mu\Big{\rangle}\right|\geq
k^{-1/4}\Big{|}\mathcal{F}_{i}\right)\geq\frac{3}{10}.$ (69)

Since $A_{i}x_{i}\in\mathcal{F}_{i}$, and
$u_{i}^{pr}\mid\mathcal{F}_{i},w_{i}\mid\mathcal{F}_{i},u_{i+1}^{pr}\mid\mathcal{F}_{i}$
are all Gaussian,

$\Big{\langle}\begin{bmatrix}A_{i}x_{i}+Bu_{i}^{pr}+w_{i}\\\
u_{i+1}^{pr}\end{bmatrix},\mu\Big{\rangle},$ (70)

as an affine function of the above terms, is also
$\mathcal{F}_{i}$-conditionally Gaussian, whose mean and variance are:

$\displaystyle\mathbb{E}\left[\Big{\langle}\begin{bmatrix}A_{i}x_{i}+Bu_{i}^{pr}+w_{i}\\\
u_{i+1}^{pr}\end{bmatrix},\mu\Big{\rangle}\right|\left.\vphantom{\begin{bmatrix}1\\\
1\end{bmatrix}}\mathcal{F}_{i}\right]=\langle A_{i}x_{i},\mu_{1}\rangle,$
$\displaystyle\mathbb{E}\left[\left(\Big{\langle}\begin{bmatrix}A_{i}x_{i}+Bu_{i}^{pr}+w_{i}\\\
u_{i+1}^{pr}\end{bmatrix},\mu\Big{\rangle}-\langle
A_{i}x_{i},\mu_{1}\rangle\right)^{2}\right|\left.\vphantom{\left(\begin{bmatrix}1\\\
1\end{bmatrix}\right)^{2}}\mathcal{F}_{i}\right]$
$\displaystyle=\mathbb{E}\left[\Big{\langle}\begin{bmatrix}Bu_{i}^{pr}+w_{i}\\\
u_{i+1}^{pr}\end{bmatrix},\mu\Big{\rangle}^{2}\right|\left.\vphantom{\begin{bmatrix}1\\\
1\end{bmatrix}}\mathcal{F}_{i}\right]$
$\displaystyle=\mu^{T}\begin{bmatrix}i^{-1/2}BB^{\top}+I&0\\\
0&(i+1)^{-1/2}\end{bmatrix}\mu$ $\displaystyle\geq\mu^{T}\begin{bmatrix}I&0\\\
0&k^{-1/2}\end{bmatrix}\mu\geq k^{-1/2}.$ (71)

The conclusion (69) then follows from the fact that for any
$X\sim\mathcal{N}(\mu,\sigma^{2})$, it holds
$\mathbb{P}(|X|\geq\sigma)\geq\mathbb{P}(|X-\mu|\geq\sigma)\geq 3/10$. ∎

An upper bound on $\|V_{k}^{-1}\|$ can be obtained by applying an anti-
concentration property of BMSB, along with a covering argument in [20]:

######  Lemma 16.

For any fixed $k\geq 2$ and $0<\delta_{k}\leq 1/2$, it holds

$\displaystyle\mathbb{P}\left(\left\|V_{k}^{-1}\right\|\geq\frac{1600}{9}k^{-1/2}\right)\leq$
$\displaystyle\quad\delta_{k}+e^{-\frac{9}{800}k+(m+n)\log(800C_{V}k^{1/2}(\log(k/\delta_{k}))^{2})},$
(72)

where $C_{V}$ is defined in Theorem 3, item 5).

###### Proof.

Firstly, for any fixed $\mu\in\mathbb{S}^{m+n}$, applying [20, Prop. 2.5] to
the process $\\{\langle z_{i},\mu\rangle\\}_{i=1}^{k-1}$, which is
$(1,k^{-1/4},3/10)$-BMSB by Lemma 15, we have

$\mathbb{P}\left(\sum_{i=1}^{k-1}\langle
z_{i},\mu\rangle^{2}\leq\frac{k^{-1/2}(3/10)^{2}}{8}k\right)\leq
e^{-\frac{(3/10)^{2}k}{8}},$ (73)

i.e.,

$\mathbb{P}\left(\mu^{\top}V_{k}\mu\leq\frac{9}{800}k^{1/2}\right)\leq
e^{-\frac{9}{800}k}.$ (74)

Next, we shall choose multiple $\mu$’s and using a covering argument to lower
bound the minimum eigenvalue of $V_{k}$, and hence to upper bound
$\|V_{k}^{-1}\|$: let
$\overline{\Gamma}=C_{V}k(\log(k/\delta_{k}))^{2}I_{m+n}$, and
$\underline{\Gamma}=(9/800)k^{1/2}I_{m+n}$. Let $\mathcal{T}$ be a minimal
$1/4$-net of $\mathcal{S}_{\underline{\Gamma}}$ in the norm
$\|\cdot\|_{\overline{\Gamma}}$, then by [20, Lemma D.1], we have

$\displaystyle\log\left|\mathcal{T}\right|$
$\displaystyle\leq(m+n)\log(9)+\log\det(\overline{\Gamma}\underline{\Gamma}^{-1})$
$\displaystyle\leq(m+n)\log(800C_{V}k^{1/2}(\log(k/\delta_{k}))^{2}).$ (75)

According to (74) and (75), we have

$\displaystyle\mathbb{P}\left(\mu^{\top}V_{k}\mu\leq\frac{9}{800}k^{1/2},\;\forall\mu\in\mathcal{T}\right)\leq|\mathcal{T}|e^{-\frac{9}{800}k}$
$\displaystyle\leq
e^{-\frac{9}{800}k+(m+n)\log(800C_{V}k^{1/2}(\log(k/\delta_{k}))^{2})}.$ (76)

On the other hand, according to Proposition 13 and Theorem 3, item 1), we have

$\mathbb{P}\left(\|V_{k}\|\leq
C_{V}k(\log(k/\delta_{k}))^{2}\right)\leq\delta_{k},$ (77)

From (76), (77) and [20, Lemma D.1], it follows that
$\mathbb{P}\left(V_{k}\succ\underline{\Gamma}/2\right)$ is no greater than the
RHS of (72), which is equivalent to the conclusion. ∎

The next proposition converts Lemma 16 into a time-uniform bound:

######  Proposition 17.

For $\delta$ satisfying (21) and $k_{0}$ defined in (23), it holds

$\mathbb{P}\left(\left\|V_{k}^{-1}\right\|\leq\frac{1600}{9}k^{-1/2},\forall
k\geq k_{0}\right)\leq 3\delta.$ (78)

###### Proof.

For $k\geq k_{0}$, with $\delta_{k}=\delta/k^{2}$, it holds

$k\geq\left(1300(m+n)\right)^{4/3},$ (79)

and hence,

$\displaystyle(m+n)\log(800C_{V}k^{1/2}(\log(k/\delta_{k}))^{2})$
$\displaystyle\leq$
$\displaystyle(m+n)\left(3\log(1/\delta)+\frac{13}{2}\log(k)\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{200}k+\frac{13}{2}(m+n)k^{1/4}\leq\frac{1}{100}k.$ (80)

Substituting (80) into (72), we have

$\mathbb{P}\left(\left\|V_{k}^{-1}\right\|\geq\frac{1600}{9}k^{-1/2}\right)\leq\frac{\delta}{k^{2}}+e^{-\frac{1}{800}k}.$
(81)

Taking the union bound over $k=k_{0},k_{0}+1,\ldots$, we have

$\displaystyle\mathbb{P}\left(\left\|V_{k}^{-1}\right\|\geq\frac{1600}{9}k^{-1/2},\forall
k\geq k_{0}\right)$ $\displaystyle\leq$
$\displaystyle\frac{\pi^{2}}{6}\delta+801e^{-\frac{1}{800}k_{0}}\leq 3\delta.$
(82)

∎

Theorem 3, item 5) follows from Propositions 12, 13 and 78.

###  IV-F Proof of Theorem 3, item 26)

###### Proof.

Let

$\displaystyle
T_{1}=\inf\left\\{T\vphantom{\left(A^{t_{k}}\right)^{\top}}\right.\left|\left(A^{t_{k}}\right)^{\top}P^{*}A^{t_{k}}<\rho
P^{*},\forall k\geq T\right\\},$ (83) $\displaystyle
T_{2}=\inf\left\\{T\vphantom{\left(A+B\hat{K}_{k}\right)^{\top}}\right.\left|\left(A+B\hat{K}_{k}\right)^{\top}P^{*}\left(A+B\hat{K}_{k}\right)<\rho
P^{*},\right.$ $\displaystyle\left.\mkern
100.0mu\vphantom{\left(A+B\hat{K}_{k}\right)^{\top}}\forall k\geq T\right\\}.$
(84)

We shall bound $T_{1}$ and $T_{2}$ respectively:

  1. 1.

From the assumption $\rho(A)<1$, it holds

$\lim_{k\to\infty}\left(A^{k}\right)^{\top}PA^{k}=0,$ (85)

which, together with $t_{k}=\lfloor\log(k)\rfloor$, implies $T_{1}$ is a
finite constant independent of $\delta$, i.e., $T_{1}\lesssim 1$.

  2. 2.

Since $(A+B{K})^{\top}P^{*}(A+B{K})$ is a continuous function of $K$, from
(10), there exists a system-dependent constant $\epsilon_{K}$, such that
$(A+B{K})^{\top}P^{*}(A+B{K})<\rho P^{*}$ whenever $\|K-K^{*}\|<\epsilon_{K}$.
On the other hand, since $\hat{K}_{k}$ is a continuous function of
$\hat{\Theta}_{k}$ [9, Proposition 6], there exists a system-dependent
constant $\epsilon_{\Theta}$, such that $\|\hat{K}-K^{*}\|<\epsilon_{K}$ as
long as $\|\hat{\Theta}_{k}-\Theta\|<\epsilon_{\Theta}$. It follows from
Theorem 3, item 5) that $\|\hat{\Theta}_{k}-\Theta\|<\epsilon_{\Theta}$
whenever $k\geq(9C_{\Theta}^{2}/\epsilon_{\Theta}^{2})(\log(1/\delta))^{2}$,
and hence $T_{2}\lesssim(\log(1/\delta))^{2}$.

In summary, it holds
$T_{\text{stab}}=\max\\{T_{1},T_{2}\\}\lesssim(\log(1/\delta))^{2}$. ∎

###  IV-G Proof of Theorem 3, item 27)

This subsection is dedicated to bounding the time after which the circuit-
breaking is not triggered any more. The outline of the proof is stated as
follows: firstly, we define a subsequence notation to deal with the dwell time
$t_{k}$ of circuit breaking. Secondly, an upper bound on the state and the
certainty equivalent input after $T_{\text{stab}}$ is derived, which is shown
to be asymptotically smaller than the circuit-breaking threshold
$M_{k}=\log(k)$. Based on the above upper bound on the certainty equivalent
input, we can finally bound $T_{\text{nocb}}$, i.e., the time it takes for the
certainty equivalent input to stay below the threshold $M_{k}$, which leads to
the desired conclusion.

####  IV-G1 A subsequence notation

Consider the subsequence of states and inputs, where steps within the circuit-
breaking period are skipped, defined below:

$\displaystyle
i(1)=1,i(k+1)=\left\\{\begin{array}[]{ll}i(k)+1&{u}^{cb}_{i(k)}\neq 0\\\
i(k)+t_{i(k)}&{u}^{cb}_{i(k)}=0\end{array},\right.$ (88)
$\displaystyle\tilde{x}_{k}=x_{i(k)},\tilde{u}^{ce}_{k}=u^{ce}_{i(k)},\tilde{u}^{cb}_{k}=u^{cb}_{i(k)}.$
(89)

Consider $T_{\text{stab}}$ defined in (13). We can define
$\tilde{T}_{\text{stab}}$ as the first index in the above subsequence for
which the stabilization condition is satisfied, i.e.,

$\tilde{T}_{\text{stab}}=\inf\\{T\mid i(T)\geq T_{\text{stab}}\\}.$ (90)

####  IV-G2 Upper bound on state and certainty equivalent input after
$T_{\text{stab}}$

######  Proposition 18.

On the event
$\mathcal{E}_{\text{noise}}(\delta)\cap\mathcal{E}_{\text{est}}(\delta)$, it
holds

$\displaystyle\left\|\tilde{x}_{\tilde{T}_{\text{stab}}+k}\right\|\lesssim\rho^{k/2}\log(1/\delta)+\sqrt{\log(k/\delta)},$
(91)
$\displaystyle\left\|\tilde{u}^{ce}_{\tilde{T}_{\text{stab}}+k}\right\|\lesssim\rho^{k/2}\log(1/\delta)+\sqrt{\log(k/\delta)},$
(92)

where $\rho=(1+\rho^{*})/2$.

###### Proof.

We can expand $\tilde{x}_{\tilde{T}_{\mathrm{stab}}+k}$ as:

$\displaystyle\tilde{x}_{\tilde{T}_{\text{stab}}+k}=$
$\displaystyle\tilde{A}_{\tilde{T}_{\text{stab}}+k-1}\tilde{A}_{\tilde{T}_{\text{stab}}+k-2}\cdots\tilde{A}_{\tilde{T}_{\text{stab}}}\tilde{x}_{\tilde{T}_{\text{stab}}}+$
$\displaystyle\tilde{A}_{\tilde{T}_{\text{stab}}+k-1}\tilde{A}_{\tilde{T}_{\text{stab}}+k-2}\cdots\tilde{A}_{\tilde{T}_{\text{stab}}+1}\tilde{w}_{\tilde{T}_{\text{stab}}}+$
$\displaystyle\cdots+$ $\displaystyle\tilde{w}_{\tilde{T}_{\text{stab}}+k-1},$
(93)

where:

  * •

$\tilde{A}_{j}\in\\{A+B\hat{K}_{i(j)},A^{t_{i(j)}}\\}$, and must satisfy
$\tilde{A}_{j}^{\top}P\tilde{A}_{j}<\rho P$ for
$j\geq\tilde{T}_{\text{stab}}$, by definition of $\tilde{T}_{\text{stab}}$ in
(13);

  * •

$\tilde{w}_{j}\in\\{w_{i(j)},\sum_{\tau=0}^{t_{i(j)}-1}A^{\tau}w_{i(j-1)+\tau}\\}$,
and on the event $\mathcal{E}_{\text{noise}}(\delta)$, it must satisfy
$\|\tilde{w}_{j}\|\lesssim\mathcal{A}\sqrt{\log(j/\delta)}\lesssim\sqrt{\log(j/\delta)}$
for any $j$, where $\mathcal{A}=\sum_{\tau=0}^{\infty}\|A^{\tau}\|$.

Combining the above two items, we have

$\displaystyle\left\|\tilde{x}_{\tilde{T}_{\text{stab}}+k}\right\|\lesssim\rho^{k/2}\left\|\tilde{x}_{\tilde{T}_{\text{stab}}}\right\|+\sqrt{\log\left(i\left(\tilde{T}_{\text{stab}}+k\right)/\delta\right)}.$
(94)

We shall next bound $\left\|\tilde{x}_{\tilde{T}_{\mathrm{stab}}}\right\|$ and
$i(\tilde{T}_{\text{stab}}+k)$ respectively:

  1. 1.

According to the definition of $\tilde{T}_{\text{stab}}$ and $i(\cdot)$ in
(88) and (90), we have

$i\left(\tilde{T}_{\text{stab}}\right)\leq
T_{\text{stab}}+\log(T_{\text{stab}}).$ (95)

On $\mathcal{E}_{\text{est}}(\delta)$, according to Theorem 3, item 26, we
have $T_{\text{stab}}\lesssim(\log(1/\delta))^{2}$, and hence

$\displaystyle
i\left(\tilde{T}_{\text{stab}}\right)\lesssim(\log(1/\delta))^{2}+\log((\log(1/\delta))^{2})$
$\displaystyle\lesssim(\log(1/\delta))^{2}.$ (96)

Furthermore, according to Theorem 3, item 18, on
$\mathcal{E}_{\text{noise}}(\delta)$, we have
$\|x_{k}\|\lesssim\log(k/\delta)$ for any $k$, and hence

$\displaystyle\left\|\tilde{x}_{\tilde{T}_{\text{stab}}}\right\|=\left\|{x}_{i\left(\tilde{T}_{\text{stab}}\right)}\right\|\lesssim\log\left(\frac{(\log(1/\delta))^{2}}{\delta}\right)$
$\displaystyle=\log(1/\delta)+\log((\log(1/\delta))^{2})\lesssim\log(1/\delta).$
(97)

  2. 2.

By definition of $i(\cdot)$ in (88), we have

$i\left(\tilde{T}_{\text{stab}}+k+1\right)\leq\tilde{T}_{\text{stab}}+k+\log\left(\tilde{T}_{\text{stab}}+k\right),\forall
k\in\mathbb{N}^{*}.$ (98)

Applying induction to (95) and (98), we can obtain

$i\left(\tilde{T}_{\text{stab}}+k\right)\lesssim
k\log(T_{\text{stab}}k)+T_{\text{stab}}.$ (99)

Substituting $T_{\text{stab}}\lesssim(\log(k/\delta))^{2}$, which holds on
$\mathcal{E}_{\text{est}}(\delta)$ according to Theorem 3, item 26), into
(99), we have

$i\left(\tilde{T}_{\text{stab}}+k\right)\lesssim k(\log(k/\delta))^{2}.$ (100)

Hence, inequality (91) follows from substituting (97) and (100) into (94).
Moreover, since $\left\|\hat{K}_{i(\tilde{T}_{\text{stab}}+k)}\right\|$ is
uniformly bounded by definition of $T_{\text{stab}}$ in (13), we have

$\left\|\tilde{u}^{ce}_{\tilde{T}_{\text{stab}}+k}\right\|\leq\left\|\hat{K}_{i(\tilde{T}_{\text{stab}}+k)}\right\|\left\|\tilde{x}_{\tilde{T}_{\text{stab}}+k}\right\|\lesssim\left\|\tilde{x}_{\tilde{T}_{\text{stab}}+k}\right\|,$
(101)

which implies (92). ∎

####  IV-G3 Upper bound on $T_{\text{nocb}}$

Now we are ready to prove Theorem 3, item 27):

###### Proof.

For any $\epsilon>0$, according to (100), we have
$i(\tilde{T}_{\text{stab}}+k)\lesssim(1/\delta)^{\alpha+\epsilon}$ as long as
$k\lesssim(1/\delta)^{\alpha-\epsilon}$. Hence, we only need to prove

$u_{k}^{cb}\equiv u_{k}^{ce},\quad\forall k\geq
i\left(\tilde{T}_{\text{stab}}+k_{0}\right),$ (102)

for some $k_{0}\lesssim(1/\delta)^{\alpha-\epsilon}$.

Notice that (102) is equivalent to

$\tilde{u}^{cb}_{{\tilde{T}_{\text{stab}}+k}}\equiv\tilde{u}^{ce}_{{\tilde{T}_{\text{stab}}+k}},\quad\forall
k\geq k_{0},$ (103)

which is then equivalent to

$\left\|\tilde{u}^{ce}_{\tilde{T}_{\text{stab}}+k}\right\|\leq
M_{k}=\log(k),\quad\forall k\geq k_{0}.$ (104)

According to Proposition 18, we only need to verify

$\rho^{k/2}\log(1/\delta)+\sqrt{\log(k/\delta)}\lesssim\log(k),$ (105)

whenever $k\gtrsim(1/\delta)^{\alpha-\epsilon}$. In such case, we have

$\displaystyle\rho^{k/2}\log(1/\delta)+\sqrt{\log(k/\delta)}$
$\displaystyle\lesssim\log(1/\delta)+\sqrt{\log(k)+\log(1/\delta)}$
$\displaystyle\lesssim\log(k)+\sqrt{\log(k)}\lesssim\log(k),$ (106)

from which the conclusion follows. ∎

###  IV-H Proof of Theorem 30

In this subsection, we first decompose the regret of the proposed controller
into multiple terms, then derive upper bounds on the terms respectively to
obtain the high-probability regret bound stated in Theorem 30.

####  IV-H1 Regret decomposition

We first state a supporting lemma:

######  Lemma 19.

Let $K^{*},P^{*}$ be defined in (6), (7) respectively, and $K=K^{*}+\Delta K$,
then

$\displaystyle
Q+{K}^{\top}R{K}+\left(A+B{K}\right)^{\top}P^{*}\left(A+B{K}\right)-P^{*}$
$\displaystyle=$ $\displaystyle\Delta K^{\top}(R+B^{\top}P^{*}B)\Delta K.$
(107)

###### Proof.

Substituting the Lyapunov equation (9) into the LHS of (107), we have

$\displaystyle Q+{K}^{\top}R{K}+(A+B{K})^{\top}P^{*}(A+B{K})-P^{*}$
$\displaystyle=$
$\displaystyle{K}^{\top}R{K}-\left({K^{*}}\right)^{\top}RK^{*}+(A+B{K})^{\top}P^{*}(A+B{K})-$
$\displaystyle\quad\left(A+BK^{*}\right)^{\top}P^{*}\left(A+BK^{*}\right)$
$\displaystyle=$ $\displaystyle\Delta
K^{\top}\left(R+B^{\top}P^{*}B\right)\Delta K+G+G^{\top},$ (108)

where

$G=\Delta K^{\top}\left[(R+B^{\top}P^{*}B)K^{*}+B^{\top}P^{*}A\right].$ (109)

By definition of $K^{*}$ in (6), we have $G=0$, and hence the conclusion
holds. ∎

Now we are ready to state the decomposition of regret:

######  Proposition 20.

The regret of the proposed controller defined in (11) can be decomposed as

$\mathcal{R}(T)=\sum_{i=1}^{7}\mathcal{R}_{i}(T),$ (110)

with the terms $\mathcal{R}_{i}(T)$ defined as:

$\displaystyle\mathcal{R}_{1}(T)=\sum_{k=1}^{T}x_{k}^{\top}(K_{k}-K^{*})^{\top}(R+B^{T}P^{*}B)(K_{k}-K^{*})x_{k},$
(111)
$\displaystyle\mathcal{R}_{2}(T)=2\sum_{k=1}^{T}\left(u_{k}^{pr}\right)^{\top}B^{\top}P^{*}(A+BK_{k})x_{k},$
(112)
$\displaystyle\mathcal{R}_{3}(T)=2\sum_{k=1}^{T}w_{k}^{\top}P^{*}(A+BK_{k})x_{k},$
(113)
$\displaystyle\mathcal{R}_{4}(T)=\sum_{k=1}^{T}(s_{k}^{\top}P^{*}s_{k}-w_{k}^{\top}P^{*}w_{k}),$
(114)
$\displaystyle\mathcal{R}_{5}(T)=\sum_{k=1}^{T}w_{k}^{\top}P^{*}w_{k}-TJ^{*},$
(115)
$\displaystyle\mathcal{R}_{6}(T)=x_{1}^{\top}P^{*}x_{1}-x_{T+1}^{\top}P^{*}x_{T+1},$
(116)
$\displaystyle\mathcal{R}_{7}(T)=\sum_{k=1}^{T}2\left(u^{pr}_{k}\right)^{\top}Ru^{cb}_{k}+\left(u^{pr}_{k}\right)^{\top}Ru^{pr}_{k},$
(117)

where $K_{k},s_{k}$ are defined as:

$K_{k}=\begin{cases}\hat{K}_{k}&u^{cb}_{k}=u^{ce}_{k}\\\
0&\text{otherwise}\end{cases},s_{k}=Bu^{pr}_{k}+w_{k}.$ (118)

###### Proof.

From $u_{k}=u_{k}^{cb}+u_{k}^{pr}=K_{k}x_{k}+u_{k}^{pr}$, it holds

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum_{k=1}^{T}\left(x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k}\right)-TJ^{*}$
$\displaystyle=\sum_{k=1}^{T}\left[x_{k}^{\top}\left(Q+K_{k}^{\top}RK_{k}\right)x_{k}+2\left(u^{pr}_{k}\right)^{\top}Ru^{cb}_{k}+\right.$
$\displaystyle\qquad\left.\left(u^{pr}_{k}\right)^{\top}Ru^{pr}_{k}\right]-TJ^{*}$
$\displaystyle=\sum_{k=1}^{T}\left[x_{k}^{\top}\left(Q+K_{k}^{\top}RK_{k}\right)x_{k}+x_{k+1}^{\top}P^{*}x_{k+1}-\right.$
$\displaystyle\qquad\left.x_{k}^{\top}P^{*}x_{k}\right]-TJ^{*}+\mathcal{R}_{6}(T)+\mathcal{R}_{7}(T).$
(119)

We can further expand the summands in the RHS of the above inequality: from
$x_{k+1}=(A+BK_{k})x_{k}+s_{k}$, we have

$\displaystyle
x_{k}^{\top}\left(Q+K_{k}^{\top}RK_{k}\right)x_{k}+x_{k+1}^{\top}P^{*}x_{k+1}-x_{k}^{\top}P^{*}x_{k}$
$\displaystyle=$ $\displaystyle
x_{k}^{\top}\left[Q+K_{k}^{\top}RK_{k}+(A+BK_{k})^{\top}P^{*}(A+BK_{k})-P^{*}\right]x_{k}$
$\displaystyle\quad+2s_{k}^{\top}P^{*}(A+BK_{k})x_{k}+s_{k}^{\top}P^{*}s_{k}$
$\displaystyle=$ $\displaystyle
x_{k}^{\top}(K_{k}-K^{*})^{\top}(R+B^{\top}P^{*}B)(K_{k}-K^{*})x_{k}+$
$\displaystyle\quad 2s_{k}^{\top}P^{*}(A+BK_{k})x_{k}+s_{k}^{\top}P^{*}s_{k},$
(120)

where the last equality follows from Lemma 19. It follows from simple algebra
that

$\displaystyle\sum_{k=1}^{T}\left[x_{k}^{\top}\left(Q+K_{k}^{\top}RK_{k}\right)x_{k}+x_{k+1}^{\top}P^{*}x_{k+1}-x_{k}^{\top}P^{*}x_{k}\right]-TJ^{*}$
$\displaystyle=\sum_{i=1}^{5}\mathcal{R}_{i}(T),$ (121)

and hence the conclusion follows. ∎

####  IV-H2 Upper bound on regret terms

Next we shall bound the terms $\mathcal{R}_{i}(T)\,(i=1,\ldots,8)$
respectively:

######  Proposition 21.

The regret terms defined in (111)-(117) can be bounded as follows:

  1. 1.

On the event
$\mathcal{E}_{\text{noise}}(\delta)\cap\mathcal{E}_{\text{est}}(\delta)$, for
$T>T_{\text{nocb}}$, it holds

$\mathcal{R}_{1}(T)\lesssim(1/\delta)^{1/4}(\log(1/\delta))^{4}+\sqrt{T}(\log(T/\delta))^{3}.$
(122)

  2. 2.

On the event $\mathcal{E}_{\text{noise}}(\delta)$, it holds

$\left|\mathcal{R}_{2}(T)\right|\lesssim\sqrt{T}(\log(T/\delta))^{3/2}.$ (123)

  3. 3.

On the event $\mathcal{E}_{\text{cross}}(\delta)$, it holds

$\left|\mathcal{R}_{3}(T)\right|\lesssim\sqrt{T}(\log(T/\delta))^{2}.$ (124)

  4. 4.

On the event $\mathcal{E}_{\text{noise}}(\delta)$, it holds

$|\mathcal{R}_{4}(T)|\leq\sqrt{T}\log(T/\delta).$ (125)

  5. 5.

On the event $\mathcal{E}_{\text{cov}}(\delta)$, it holds

$|\mathcal{R}_{5}(T)|\lesssim\sqrt{T\log(1/\delta)}.$ (126)

  6. 6.

On the event $\mathcal{E}_{\text{noise}}(\delta)$, it holds

$|\mathcal{R}_{6}(T)|\lesssim(\log(T/\delta))^{2}.$ (127)

  7. 7.

On the event $\mathcal{E}_{\text{noise}}(\delta)$, it holds

$|\mathcal{R}_{7}(T)|\lesssim\sqrt{T}\log(T/\delta).$ (128)

###### Proof.

  1. 1.

Let

$r_{1k}=x_{k}^{\top}(K_{k}-K^{*})^{\top}\left(R+B^{\top}P^{*}B\right)(K_{k}-K^{*})x_{k}.$
(129)

We shall next bound $\sum_{k=1}^{T_{\text{nocb}}}r_{1k}$ and
$\sum_{k=T_{\text{nocb}+1}}^{T}r_{1k}$ respectively:

    1. (a)

For $k\leq T_{\text{nocb}}$, we have $\|x_{k}\|\lesssim\log(k/\delta)$ by
Theorem 3, item 18), and $\|K_{k}x_{k}\|=\|u_{k}^{cb}\|\leq\log(k)$.
Therefore, it holds

$r_{1k}\lesssim(\log(k/\delta))^{2},$ (130)

and hence,

$\sum_{k=1}^{T_{\text{nocb}}}r_{1k}\lesssim
T_{\text{nocb}}(\log(T_{\text{nocb}}/\delta))^{2}.$ (131)

Invoking Theorem 3, item 27 with $\alpha=1/4$, we get

$\sum_{k=1}^{T_{\text{nocb}}}r_{1k}\lesssim(1/\delta)^{1/4}(\log(1/\delta))^{4}.$
(132)

    2. (b)

For $k\leq T_{\text{nocb}}$, by definition of $T_{\text{nocb}}$, we have
$K_{k}=\hat{K}_{k}$. Hence, by definition of $\mathcal{E}_{\text{est}}$ and
the fact that $\hat{K}_{k}$ is a continuous function of $\hat{\Theta}_{k}$ [9,
Proposition 6], we have

$\displaystyle\left\|K_{k}-K^{*}\right\|=\left\|\hat{K}_{k}-K^{*}\right\|$
$\displaystyle\lesssim\left\|\hat{\Theta}_{k}-\Theta\right\|\lesssim
k^{-1/4}(\log(k/\delta))^{1/2}.$ (133)

Furthermore, by Theorem 3, item 18, we have $\|x_{k}\|\lesssim\log(k/\delta)$,
and hence,

$r_{1k}\lesssim\|K_{k}-K^{*}\|^{2}\|x_{k}\|^{2}\lesssim
k^{-1/2}(\log(k/\delta))^{3}.$ (134)

Therefore,

$\sum_{k=T_{\text{nocb}}+1}^{T}r_{1k}\lesssim\sqrt{T}(\log(T/\delta))^{3}.$
(135)

Summing up (132) and (135) leads to (122).

  2. 2.

Let

$r_{2k}=\left(u_{k}^{pr}\right)^{\top}B^{\top}P^{*}(A+BK_{k})x_{k},$ (136)

whose factors can be bounded as follows:

     * •

$\left\|u_{k}^{pr}\right\|=k^{1/2}\|v_{k}\|\lesssim
k^{-1/2}(\log(k/\delta))^{1/2}$ by definition of $\mathcal{E}_{\text{noise}}$;

     * •

$\|x_{k}\|\lesssim\log(k/\delta)$ by Theorem 3, item 18);

     * •

$\|K_{k}x_{k}\|=\left\|u_{k}^{cb}\right\|\leq M_{k}=\log(k)$ according to the
proposed controller.

Hence,

$|r_{2k}|\lesssim k^{-1/2}(\log(k/\delta))^{3/2},$ (137)

and summing up (137) from $k=1$ to $T$ leads to (123).

  3. 3.

The inequality (124) follows directly from the definition of
$\mathcal{E}_{\text{cross}}(\delta)$ in (19).

  4. 4.

Let

$r_{4k}=s_{k}^{\top}P^{*}s_{k}-w_{k}^{\top}P^{*}w_{k}.$ (138)

From $s_{k}=w_{k}+Bu_{k}^{pr}=w_{k}+k^{-1/2}Bv_{k}$, we have

$r_{4k}=2k^{-1/2}w_{k}^{\top}P^{*}Bv_{k}+k^{-1}v_{k}^{\top}B^{\top}P^{*}Bv_{k}.$
(139)

Hence, by definition of $\mathcal{E}_{\text{noise}}(\delta)$, we have

$|r_{4k}|\lesssim k^{-1/2}\log(k/\delta).$ (140)

Summing up (140) from $k=1$ to $T$ leas to (125).

  5. 5.

Since $J^{*}=\operatorname{tr}(P^{*})$ (see (8)), we have

$\displaystyle\left|\mathcal{R}_{5}(T)\right|$
$\displaystyle=\left|\sum_{k=1}^{T}\operatorname{tr}(w_{k}w_{k}^{\top}P)-T\operatorname{tr}(P)\right|$
$\displaystyle=\left|\operatorname{tr}\left(\left(\sum_{k=1}^{T}(w_{k}w_{k}^{\top}-I_{n})\right)P\right)\right|$
$\displaystyle\lesssim\left\|\sum_{k=1}^{T}(w_{k}w_{k}^{\top}-I_{n})\right\|\lesssim\sqrt{T\log(1/\delta)},$
(141)

where the last inequality follows from the definition of
$\mathcal{E}_{\text{cov}}(\delta)$, which proves (126).

  6. 6.

The inequality (127) is a direct corollary of Theorem 3, item 18).

  7. 7.

Let

$r_{7k}=2\left(u^{pr}_{k}\right)^{\top}Ru^{cb}_{k}+\left(u^{pr}_{k}\right)^{\top}Ru^{pr}_{k},$
(142)

where $u_{k}^{pr}$ and $u_{k}^{cb}$ satisfy:

     * •

$\left\|u_{k}^{pr}\right\|=k^{-1/2}\|v_{k}\|\lesssim
k^{-1/2}(\log(k/\delta))^{1/2}$ by definition of
$\mathcal{E}_{\text{noise}}(\delta)$;

     * •

$\left\|u_{k}^{cb}\right\|\leq M_{k}=\log(k)$ according to the proposed
controller.

Hence,

$|r_{7k}|\lesssim k^{-1/2}\log(k/\delta),$ (143)

and summing up (143) from $k=1$ to $T$ leads to (128).

∎

Theorem 30 follows from combining Propositions 118 and 21.

##  V Simulation

In this section, the proposed controller is validated on the Tennessee Eastman
Process (TEP) [21]. In particular, we consider a simplified version of TEP
similar to the one in [22], with full state feedback. The system is open-loop
stable, and has state dimension $n=8$ and input dimension $m=4$. The process
noise distribution is chosen to be $w_{k}\stackrel{{\scriptstyle\text{ i.i.d.
}}}{{\sim}}\mathcal{N}(0,I_{n})$. The weight matrices of LQR are chosen to be
$Q=I_{n}$ and $R=I_{m}$. The plant under the proposed controller is simulated
for 10000 independent trials, each with $T=3\times 10^{8}$ steps. As mentioned
in Remark 2, the certainty equivalent gain $\hat{K}_{k}$ is updated only at
steps $k=2^{i},i\in\mathbb{N}^{*}$ for the sake of fast computation.

The evolution of regret against time is plotted in Fig. 2. For the ease of
observation, we plot the _relative average regret_ $\mathcal{R}(T)/(TJ^{*})$
against the total time step $T$, where $J^{*}$ is the optimal cost. Fig. 2
shows 5 among the 10000 trials, from which one can observe a $1/\sqrt{T}$
convergence rate of the relative average regret (i.e., a 1 order-of-magnitude
increase in $T$ corresponds to a 0.5 order-of-magnitude decrease in
$\mathcal{R}(T)/(TJ^{*})$), which matches the $\sqrt{T}$ theoretical growth
rate of regret. To inspect the statistical properties of all the trials, we
sort them by the average regret at the last step, and plot the worst, median
and mean cases in Fig. 2(b). One can observe that the average regret converge
to zero even in the worst case, which validates the almost-sure guarantee in
Theorem 32.

(a) Five random sample paths

(b) Worst, median and best cases among all sample paths

Figure 2: Double-log plot of average regret against time step

An insight to behold on the performance of the proposed controller is that the
circuit-breaking mechanism is triggered only finitely, and the time of the
last trigger $T_{\text{nocb}}$, as stated in Corollary 5, has a super-
polynomial tail. This insight is also empirically validated: among all the
10000 trials, circuit-breaking is never triggered after step $1.4\times
10^{6}$, and a histogram of $T_{\text{nocb}}$ is shown in Fig. 3, from which
one can observe that the empirical distribution of $T_{\text{nocb}}$ has a
fast decaying tail.

Figure 3: Histogram of $T_{\text{nocb}}$ among all sample paths

##  VI Conclusion

In this paper, we propose an adaptive LQR controller that can achieve
$\tilde{\mathcal{O}}(\sqrt{T})$ regret almost surely. A key underlying the
controller design is a circuit-breaking mechanism, which ensures the
convergence of the parameter estimate, but is triggered only finitely often
and hence has negligible effect on the asymptotic performance. A future
direction would be extending such circuit-breaking mechanism to the partially
observed LQG setting.

## References

  * [1] K. J. Astrom, “Adaptive control around 1960,” _IEEE Control Systems Magazine_ , vol. 16, no. 3, pp. 44–49, 1996.
  * [2] K. J. Åström and B. Wittenmark, “On self tuning regulators,” _Automatica_ , vol. 9, no. 2, pp. 185–199, 1973.
  * [3] A. Morse, “Global stability of parameter-adaptive control systems,” _IEEE Transactions on Automatic Control_ , vol. 25, no. 3, pp. 433–439, 1980\.
  * [4] T. Lai and C.-Z. Wei, “Extended least squares and their applications to adaptive control and prediction in linear systems,” _IEEE Transactions on Automatic Control_ , vol. 31, no. 10, pp. 898–906, 1986.
  * [5] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Online least squares estimation with self-normalized processes: An application to bandit problems,” _arXiv preprint arXiv:1102.2670_ , 2011.
  * [6] M. Abeille and A. Lazaric, “Improved regret bounds for thompson sampling in linear quadratic control problems,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1–9.
  * [7] A. Cohen, T. Koren, and Y. Mansour, “Learning linear-quadratic regulators efficiently with only $\sqrt{t}$ regret,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 1300–1309.
  * [8] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu, “Regret bounds for robust adaptive control of the linear quadratic regulator,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [9] M. Simchowitz and D. Foster, “Naive exploration is optimal for online lqr,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 8937–8948.
  * [10] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis, “On adaptive linear–quadratic regulators,” _Automatica_ , vol. 117, p. 108982, 2020.
  * [11] F. Wang and L. Janson, “Exact asymptotics for linear quadratic adaptive control.” _J. Mach. Learn. Res._ , vol. 22, pp. 265–1, 2021.
  * [12] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis, “Finite-time adaptive stabilization of linear systems,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 8, pp. 3498–3505, 2018.
  * [13] L. Guo, “Self-convergence of weighted least-squares with applications to stochastic adaptive control,” _IEEE transactions on automatic control_ , vol. 41, no. 1, pp. 79–89, 1996.
  * [14] H. Lin and P. J. Antsaklis, “Stability and stabilizability of switched linear systems: a survey of recent results,” _IEEE Transactions on Automatic control_ , vol. 54, no. 2, pp. 308–322, 2009.
  * [15] L. Guo and H. Chen, “Convergence rate of an els-based adaptive tracker,” _System Sciece and Mathematical Sciences_ , vol. 1, no. 2, p. 131, 1988.
  * [16] H. Mania, S. Tu, and B. Recht, “Certainty equivalence is efficient for linear quadratic control,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [17] Y. Lu and Y. Mo, “Ensuring the safety of uncertified linear state-feedback controllers via switching,” _arXiv preprint arXiv:2205.08817_ , 2022.
  * [18] B. Laurent and P. Massart, “Adaptive estimation of a quadratic functional by model selection,” _Annals of Statistics_ , pp. 1302–1338, 2000.
  * [19] K. Azuma, “Weighted sums of certain dependent random variables,” _Tohoku Mathematical Journal, Second Series_ , vol. 19, no. 3, pp. 357–367, 1967.
  * [20] M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht, “Learning without mixing: Towards a sharp analysis of linear system identification,” in _Conference On Learning Theory_. PMLR, 2018, pp. 439–473.
  * [21] J. J. Downs and E. F. Vogel, “A plant-wide industrial process control problem,” _Computers & chemical engineering_, vol. 17, no. 3, pp. 245–255, 1993.
  * [22] H. Liu, Y. Mo, J. Yan, L. Xie, and K. H. Johansson, “An online approach to physical watermark design,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 9, pp. 3895–3902, 2020.


# Document Classification for COVID-19 Literature

Bernal Jiménez Gutiérrez, Juncheng Zeng, Dongdong Zhang, Ping Zhang, Yu Su
The Ohio State University
{jimenezgutierrez.1,zeng.671,zhang.11069,
<EMAIL_ADDRESS>
###### Abstract

The global pandemic has made it more important than ever to quickly and
accurately retrieve relevant scientific literature for effective consumption
by researchers in a wide range of fields. We provide an analysis of several
multi-label document classification models on the LitCovid dataset, a growing
collection of 23,000 research papers regarding the novel 2019 coronavirus. We
find that pre-trained language models fine-tuned on this dataset outperform
all other baselines and that BioBERT surpasses the others by a small margin
with micro-F1 and accuracy scores of around 86% and 75% respectively on the
test set. We evaluate the data efficiency and generalizability of these models
as essential features of any system prepared to deal with an urgent situation
like the current health crisis. Finally, we explore 50 errors made by the best
performing models on LitCovid documents and find that they often (1) correlate
certain labels too closely together and (2) fail to focus on discriminative
sections of the articles; both of which are important issues to address in
future work. Both data and code are available on GitHub
111https://github.com/dki-lab/covid19-classification.

##  1 Introduction

The COVID-19 pandemic has made it a global priority for research on the
subject to be developed at unprecedented rates. Researchers in a wide variety
of fields, from clinicians to epidemiologists to policy makers, must all have
effective access to the most up to date publications in their respective
areas. Automated document classification can play an important role in
organizing the stream of articles by fields and topics to facilitate the
search process and speed up research efforts.

To explore how document classification models can help organize COVID-19
research papers, we use the LitCovid dataset Chen et al. (2020), a collection
of 23,000 newly released scientific papers compiled by the NIH to facilitate
access to the literature on all aspects of the virus. This dataset is updated
daily and every new article is manually assigned one or more of the following
8 categories: General, Transmission Dynamics (Transmission), Treatment, Case
Report, Epidemic Forecasting (Forecasting), Prevention, Mechanism and
Diagnosis. We leverage these annotations and the articles made available by
LitCovid to compile a timely new dataset for multi-label document
classification.

Apart from addressing the pressing needs of the pandemic, this dataset also
offers an interesting document classification dataset which spans different
biomedical specialities while sharing one overarching topic. This setting is
distinct from other biomedical document classification datasets which tend to
exclusively distinguish between biomedical topics such as hallmarks of cancer
Baker et al. (2016), chemical exposure methods Baker (2017) or diagnosis codes
Du et al. (2019). The dataset’s shared focus on the COVID-19 pandemic also
sets it apart from open-domain datasets and academic paper classification
datasets such as IMDB or the arXiv Academic Paper Dataset (AAPD) Yang et al.
(2018) in which no shared topic can be found in most of the documents, and it
poses unique challenges for document classification models.

We evaluate a number of models on the LitCovid dataset and find that fine-
tuning pre-trained language models yields higher performance than traditional
machine learning approaches and neural models such as LSTMs Adhikari et al.
(2019b); Kim (2014); Liu et al. (2017). We also notice that BioBERT Lee et al.
(2019), a BERT model pre-trained on the original corpus for BERT plus a large
set of PubMed articles, performed slightly better than the original BERT base
model. We also observe that the novel Longformer Beltagy et al. (2020) model,
which allows for processing longer sequences, matches BioBERT’s performance
when 1024 subwords are used instead of 512, the maximum for BERT models.

We then explore the data efficiency and generalizability of these models as
crucial aspects to address for document classification to become a useful tool
against outbreaks like this one. Finally, we discuss some issues found in our
error analysis such as current models often (1) correlating certain categories
too closely with each other and (2) failing to focus on discriminative
sections of a document and get distracted by introductory text about COVID-19,
which suggest venues for future improvement.

##  2 Datasets

In this section, we describe the LitCovid dataset in more detail and briefly
introduce the CORD-19 dataset which we sampled to create a small test set to
evaluate model generalizability.

###  2.1 LitCovid

| LitCovid | CORD-19 Test
---|---|---
# of Classes | 8 | 8
# of Articles | 23,038 | 100
Avg. sentences | 74 | 109
Avg. tokens | 1,399 | 2,861
Total # of tokens | 32,239,601 | 286,065
Table 1: Dataset statistics for the LitCovid and Test CORD-19 Datasets.

The LitCovid dataset is a collection of recently published PubMed articles
which are directly related to the 2019 novel Coronavirus. The dataset contains
upwards of 23,000 articles and approximately 2,000 new articles are added
every week, making it a comprehensive resource for keeping researchers up to
date with the current COVID-19 crisis.

For a large portion of the articles in LitCovid, either the full article or at
least the abstract can be downloaded directly from their website. For our
document classification dataset, we select 23,038 articles which contain full
texts or abstracts from the 35,000+ articles available on August 1st, 2020. As
seen in table 1, these selected articles contain on average approximately 74
sentences and 1,399 tokens, reflecting the roughly even split between
abstracts and full articles we observe from inspection.

Each article in LitCovid is assigned one or more of the following 8 topic
labels: Prevention, Treatment, Diagnosis, Mechanism, Case Report,
Transmission, Forecasting and General. Even though every article in the corpus
can be labelled with multiple tags, most articles, around 76%, contain only
one label. Table 2 shows the label distribution for the subset of LitCovid
which is used in the present work. We note that there is a large class
imbalance, with the most frequently occurring label appearing almost 20 times
as much as the least frequent one. We split the LitCovid dataset into train,
dev, test with the ratio 7:1:2.

Class | LitCovid | CORD-19 Set
---|---|---
Prevention | 11,042 | 12
Treatment | 6,897 | 20
Diagnosis | 4,754 | 25
Mechanism | 3,549 | 70
Case Report | 1,914 | 2
Transmission | 1,065 | 6
Forecasting | 461 | 2
General | 368 | 7
Table 2: Number of documents in each category for the LitCovid and CORD-19
Test Datasets.

###  2.2 CORD-19

The COVID-19 Open Research Dataset (CORD-19) Wang et al. (2020) was one of the
earliest datasets released to facilitate cooperation between the computing
community and the many relevant actors of the COVID-19 pandemic. It consists
of approximately 60,000 papers related to COVID-19 and similar coronaviruses
such as SARS and MERS since the SARS epidemic of 2002. Due to their
differences in scope, this dataset shares only around 1,200 articles with the
LitCovid dataset.

In order to test how our models generalize to a different setting, we asked
biomedical experts to label a small set of 100 articles found only in CORD-19.
Each article was labelled independently by two annotators. For articles which
received two different annotations (around 15%), a third annotator broke ties.
Table 1 shows the statistics of this small set and Table 2 shows its category
distribution.

##  3 Models

In the following section we provide a brief description of each model and the
implementations used. We use micro-F1 (F1) and accuracy (Acc.) as our
evaluation metrics, as done in Adhikari et al. (2019a). All reproducibility
information can be found in Appendix A.

Model | Dev Set | Test Set
---|---|---
| Acc. | F1 | Acc. | F1
LR | 68.5 | 81.4 | 68.6 | 81.4
SVM | 71.2 | 83.4 | 70.7 | 83.3
LSTM | 69.0 $\pm$0.9 | 83.9 $\pm$0.1 | 68.9 $\pm$0.3 | 83.2 $\pm$0.2
LSTM${}_{\textbf{reg}}$ | 71.2 $\pm$0.5 | 83.9 $\pm$0.3 | 70.8 $\pm$0.7 | 83.6 $\pm$0.5
KimCNN | 69.9 $\pm$0.2 | 83.3 $\pm$0.3 | 68.8 $\pm$0.1 | 82.7 $\pm$0.1
XML-CNN | 72.9 $\pm$0.4 | 84.1 $\pm$0.2 | 71.7 $\pm$0.7 | 83.5 $\pm$0.3
BERT${}_{\textbf{base}}$ | 74.3 $\pm$0.6 | 85.5 $\pm$0.4 | 73.6 $\pm$1.0 | 85.1 $\pm$0.5
BERT${}_{\textbf{large}}$ | 75.1 $\pm$3.9 | 85.9 $\pm$1.9 | 74.4 $\pm$2.7 | 85.3 $\pm$1.4
Longformer | 74.4 $\pm$0.8 | 85.6 $\pm$0.5 | 73.9 $\pm$0.8 | 85.5 $\pm$0.5
BioBERT | 75.0 $\pm$0.5 | 86.3 $\pm$0.2 | 75.2 $\pm$0.7 | 86.2 $\pm$0.6

Table 3: Performance for each model expressed as mean $\pm$ standard deviation
across three training runs.

###  3.1 Traditional Machine Learning Models

To compare with simpler but competitive traditional baselines we use the
default scikit-learn Pedregosa et al. (2011) implementation of logistic
regression and linear support vector machine (SVM) for multi-label
classification which trains one classifier per class using a one-vs-rest
scheme. Both models use TF-IDF weighted bag-of-words as input.

###  3.2 Conventional Neural Models

Using Hedwig222https://github.com/castorini/hedwig, a document classification
toolkit, we evaluate the following models: KimCNN Kim (2014), XML-CNN Liu et
al. (2017) as well as an unregularized and a regularized LSTM Adhikari et al.
(2019b). We notice that they all perform similarly and slightly better
traditional methods.

###  3.3 Pre-Trained Language Models

Using the same Hedwig document classification toolkit, we evaluate the
performance of DocBERT Adhikari et al. (2019a) on this task with a few
different pre-trained language models. We fine-tune BERT base, BERT large
Devlin et al. (2019) and BioBERT Lee et al. (2019), a version of BERT base
which was further pre-trained on a collection of PubMed articles. We find all
BERT models achieve best performance with their highest possible sequence
length of 512 subwords. Additionally, we fine-tune the pre-trained Longformer
Beltagy et al. (2020) in the same way and find that it performs best when a
maximum sequence length of 1024 is used. As in the original Longformer paper,
we use global attention on the [CLS] token for document classification but
find that performance improves by around 1% if we use the average of all
tokens as input instead of only the [CLS] representation. We hypothesize that
this effect can be observed because the LitCovid dataset contains longer
documents on average that the Hyperpartisan dataset used in the original
Longformer paper.

We find that all pre-trained language models outperform the previous
traditional and neural methods by a sizable margin in both accuracy and
micro-F1 score. The best performing models is BioBERT which achieves a
micro-F1 score of 86.2% and an accuracy of 75.2% on the test set.

##  4 Results & Discussion

In this section, we explore data efficiency, model generalizability and
discuss potential ways to improve performance on this task in future work.

###  4.1 Data Efficiency

Figure 1: Data efficiency analysis. Pre-trained language models achieve their
maximum performance on only 20% of the training data.

Article | Label | Prediction
---|---|---
| Analysis on epidemic situation and spatiotemporal changes of COVID-19 in
Anhui.
---
… We mapped the spatiotemporal changes of confirmed cases, fitted the epidemic
situation by the population growth
curve at different stages and took statistical description and analysis of the
epidemic situation in Anhui province.
Forecasting |  | Prevention
---
Forecasting
| 2019 Novel coronavirus: where we are and what we know.
---
There is a current worldwide outbreak of a new type of coronavirus
(2019-nCoV), which originated from Wuhan in
China and has now spread to 17 other countries.
…  This paper aggregates and consolidates the virology, epidemiology, clinical
management strategies …
In addition, by fitting the number of infections with a single-term
exponential model …
| Treatment
---
Mechanism
Transmission
Forecasting
| Prevention
---
Forecasting
| Managing Cancer Care During the COVID-19 Pandemic: Agility and Collaboration
Toward a Common Goal.
---
The first confirmed case of coronavirus disease 2019 (COVID-19) in the United
States was reported on
January 20, 2020, in Snohomish County, Washington. …
Treatment | Prevention

Table 4: LitCovid Error Samples. Sentences relevant to the article’s category
are highlighted with blue and general ones with red.

During a sudden healthcare crisis like this pandemic it is essential for
models to obtain useful results as soon as possible. Since labelling
biomedical articles is a very time-consuming process, achieving peak
performance using less data becomes highly desirable. We thus evaluate the
data efficiency of these models by training each of the ones shown in Figure 1
using 1%, 5%, 10%, 20% and 50% of our training data and report the micro-F1
score on the dev set. When selecting the data subsets, we sample each category
independently to make sure they are all represented.

We observe that pre-trained models are much more data-efficient than other
models and that BioBERT is the most efficient, demonstrating the importance of
domain-specific pre-training.

###  4.2 CORD-19 Generalizability

To effectively respond to this pandemic, experts must not only learn as much
as possible about the current virus but also thoroughly understand past
epidemics and similar viruses. Thus, it is crucial for models trained on the
LitCovid dataset to successfully categorize articles about related epidemics.
We therefore evaluate some of our baselines on such articles using our
labelled CORD-19 subset. We find that the accuracy and micro-F1 metrics drop
by approximately 35 and 15 points respectively. This massive drop in
performance from a minor change in domain indicates that the models have
trouble ignoring the overarching COVID-19 topic and isolating relevant signals
from each category.

| Acc. | F1
---|---|---
SVM | 29.0 | 62.8
LSTM${}_{\textbf{reg}}$ | 32.7 $\pm$1.5 | 67.7 $\pm 0.7$
Longformer | 41.3 $\pm 6.4$ | 70.0 $\pm 2.9$
BioBERT | 36.0 $\pm 7.8$ | 69.7 $\pm 2.8$
Table 5: Performance on the CORD-19 Test Set expressed as mean $\pm$ standard
deviation across three training runs.

It is interesting to note that Mechanism is the only category for which
BioBERT performs better in CORD-19 than in LitCovid. This could be due to
Mechanism articles using technical language and there being enough samples for
the models to learn; in contrast with Forecasting which also uses specific
language but has far fewer training examples. BioBERT’s binary F1 scores for
each category on both datasets can be found in Appendix B.

###  4.3 Error Analysis

We analyze 50 errors made by both highest scoring BioBERT and the Longformer
models on LitCovid documents to better understand their performance. We find
that 34% of these were annotation errors which our best performing model
predicted correctly. We also find that 10% of the errors were nearly
impossible to classify using only the text available on LitCovid, and the full
articles are needed to make better-informed prediction. From the rest of the
errors we identify some aspects of this task which should be addressed in
future work.

We first note these models often correlate certain categories, namely
Prevention, Transmission and Forecasting, much more closely than necessary.
Even though these categories are semantically related and some overlap exists,
the Transmission and Forecasting tags are predicted in conjunction with the
Prevention tag much more frequently than what is observed in the labels as can
be seen from the table in Appendix C. Future work should attempt to explicitly
model correlation between categories to help the model recognize the
particular cases in which labels should occur together. The first row in Table
4 shows a document labelled as Forecasting which is also incorrectly predicted
with a Prevention label, exemplifying this issue.

Finally, we observe that models have trouble identifying discriminative
sections of the document due to how much introductory content on the pandemic
can be found in most articles. Future work should explicitly model the gap in
relevance between introductory sections and crucial sentences such as thesis
statements and article titles. In Table 4, the second and third examples would
be more easily classified correctly if specific sentences were ignored while
others attended to more thoroughly. This could also increase interpretability,
facilitating analysis and further improvement.

##  5 Conclusion

We provide an analysis of document classification models on the LitCovid
dataset for the COVID-19 literature. We determine that fine-tuning pre-trained
language models yields the best performance on this task. We study the
generalizability and data efficiency of these models and discuss some
important issues to address in future work.

## Acknowledgments

This research was sponsored in part by the Ohio Supercomputer Center Center
(1987). The authors would also like to thank Lang Li and Tanya Berger-Wolf for
helpful discussions.

## References

  * Adhikari et al. (2019a) Ashutosh Adhikari, Achyudh Ram, Raphael Tang, and Jimmy Lin. 2019a.  Docbert: Bert for document classification.  _ArXiv_ , abs/1904.08398.
  * Adhikari et al. (2019b) Ashutosh Adhikari, Achyudh Ram, Raphael Tang, and Jimmy Lin. 2019b.  Rethinking complex neural network architectures for document classification.  In _NAACL-HLT_.
  * Baker (2017) Simon Baker. 2017.  Corpus and Software.
  * Baker et al. (2016) Simon Baker, Ilona Silins, Yufan Guo, Imran Ali, Johan Högberg, Ulla Stenius, and Anna Korhonen. 2016.  Automatic semantic classification of scientific literature according to the hallmarks of cancer.  _Bioinformatics_ , 32 3:432–40.
  * Beltagy et al. (2020) Iz Beltagy, Matthew E. Peters, and Arman Cohan. 2020.  Longformer: The long-document transformer.  _arXiv:2004.05150_.
  * Center (1987) Ohio Supercomputer Center. 1987.  Ohio supercomputer center.
  * Chen et al. (2020) Q. Chen, A. Allot, and Z. Lu. 2020.  Keep up with the latest coronavirus research.  _Nature_ , 579(7798):193.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _ArXiv_ , abs/1810.04805.
  * Du et al. (2019) Jingcheng Du, Qingyu Chen, Yifan Peng, Yang Xiang, Cui Tao, and Zhiyong Lu. 2019\.  Ml-net: multi-label classification of biomedical texts with deep neural networks.  _Journal of the American Medical Informatics Association : JAMIA_.
  * Kim (2014) Yoon Kim. 2014.  Convolutional neural networks for sentence classification.  In _EMNLP_.
  * Lee et al. (2019) Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang. 2019.  BioBERT: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinformatics_.
  * Liu et al. (2017) Jingzhou Liu, Wei-Cheng Chang, Yuexin Wu, and Yiming Yang. 2017.  Deep learning for extreme multi-label text classification.  _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Gilles Louppe, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jacob VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay. 2011\.  Scikit-learn: Machine learning in python.  _J. Mach. Learn. Res._ , 12:2825–2830.
  * Wang et al. (2020) Lucy Lu Wang, Kyle Lo, Yoganand Chandrasekhar, Russell Reas, Jiangjiang Yang, Darrin Eide, Kathryn Funk, Rodney Michael Kinney, Ziyang Liu, William. Merrill, Paul Mooney, Dewey A. Murdick, Devvret Rishi, Jerry Sheehan, Zhihong Shen, Brandon Stilson, Alex D. Wade, Kuansan Wang, Christopher Wilhelm, Boya Xie, Douglas M. Raymond, Daniel S. Weld, Oren Etzioni, and Sebastian Kohlmeier. 2020.  Cord-19: The covid-19 open research dataset.  _ArXiv_ , abs/2004.10706.
  * Yang et al. (2018) Pengcheng Yang, Xu Sun, Wei Li, Shuming Ma, Wei Wu, and Houfeng Wang. 2018.  Sgm: Sequence generation model for multi-label classification.  In _COLING_.

**APPENDIX**
Document Classification for COVID-19 Literature

##  Appendix A Experimental Set-up

We split the LitCovid dataset into train, dev, test with the ratio 7:1:2.

We adopt micro-F1 and accuracy as our evaluation metrics, same as Adhikari et
al. (2019a). We use scikit-learn Pedregosa et al. (2011) and Hedwig evaluation
scripts to evaluate all the models. For preprocessing, tokenization and
sentence segmentation, we use the NLTK library.

All the document classification models used in the paper, logistic regression
111https://scikit-learn.org/stable/modules/generated/
sklearn.linear_model.LogisticRegression.html SVM 222https://scikit-
learn.org/stable/modules/generated/sklearn.svm.SVC.html DocBERT
333https://github.com/castorini/hedwig/blob/master/models/bert, Reg-LSTM
444https://github.com/castorini/hedwig/blob/master/models/reg_lstm, Reg-LSTM
555https://github.com/castorini/hedwig/blob/master/models/reg_lstm, XML-CNN
666https://github.com/castorini/hedwig/blob/master/models/xml_cnn, Kim CNN
777https://github.com/castorini/hedwig/blob/master/models/kim_cnn are run
based on the implementations listed here and strictly followed their
instructions. We used the following pre-trained language models, BioBERT
888https://huggingface.co/monologg/biobert_v1.1_pubmed, BERT base
999https://huggingface.co/bert-base-uncased, BERT large
101010https://huggingface.co/bert-large-uncased and the Longformer
111111https://github.com/allenai/longformer.

For reproducibility, we list all the key hyperparameters, the tuning bounds
and the # of parameters for each model in Table A1. For the logistic
regression and the SVM all hyperparameters used were default to scikit-learn
and therefore are excluded from this table. For all models we train for a
maximum of 30 epochs with a patience of 5. We used micro-F1 score for all
hyperparameter tuning. All models were run on NVIDIA GeForce GTX 1080 GPUs.

Model | Hyperparameters | Hyperparameter bounds | Number of Parameters
---|---|---|---
Kim CNN |  | batch size: 32
---
learning rate: 0.001
dropout: 0.1
mode: static
output channel: 100
word dimension: 300
embedding dimension: 300
epoch decay: 15
weight decay: 0
| batch size: (16, 32, 64)
---
learning rate: (0.01, 0.001, 0.0001)
dropout: (0.1, 0.5, 0.7)
362,708
XML-CNN |  | batch size: 32
---
learning rate: 0.001
dropout: 0.7
dynamic pool length: 8
mode: static
output channel: 100
word dimension: 300
embedding dimension: 300
epoch decay: 15
weight decay: 0
hidden bottleneck dimension: 512
| batch size: (32, 64)
---
learning rate: (0.001, 0.0001, $1\times 10^{-5}$)
dropout: (0.1, 0.5, 0.7)
dynamic pool length: (8, 16, 32)
1,653,716
LSTM |  | batch size: 8
---
learning rate: 0.001
dropout: 0.1
hidden dimension: 512
mode: static
output channel: 100
word dimension: 300
embedding dimension: 300
number of layers: 1
epoch decay: 15
weight decay: 0
bidirectional: true
bottleneck layer: true
weight drop: 0.1
embedding dropout: 0.2
temporal averaging: 0.0
temporal activation regularization: 0.0
activation regularization: 0.0
| learning rate: (0.01, 0.001, 0.0001)
---
hidden dimension: (300, 512)
3,342,344
LSTM${}_{\textbf{Reg}}$ |  | batch size: 8
---
learning rate: 0.001
dropout: 0.5
hidden dimension: 300
temporal averaging: 0.99
mode: static
output channel: 100
word dimension: 300
embedding dimension: 300
number of layers: 1
epoch decay: 15
weight decay: 0
bidirectional: true
bottleneck layer: true
weight drop: 0.1
embedding dropout: 0.2
temporal activation regularization: 0.0
activation regularization: 0.0
| batch size: (8,16)
---
learning rate: (0.01, 0.001, 0.0001)
hidden dimension: (300, 512)
dropout: (0.5, 0.6)
1,449,608
BERT${}_{\textbf{base}}$ |  | learning rate: $2\times 10^{-5}$
---
max sequence length: 512
batch size: 6
model: bert-base-uncased
warmup proportion: 0.1
gradient accumulation steps: 1
| learning rate: (0.001, 0.0001,
---
$2\times 10^{-5}$, $1\times 10^{-6}$)
maximum sequence length: (256, 512)
110M
BERT${}_{\textbf{large}}$ |  | learning rate: $2\times 10^{-5}$
---
max sequence length: 512
batch size: 2
model: bert-large-uncased
warmup proportion: 0.1
gradient accumulation steps: 1
| learning rate: (0.001, 0.0001,
---
$2\times 10^{-5}$, $1\times 10^{-6}$)
maximum sequence length: (256, 512)
336M
BioBERT |  | learning rate: $2\times 10^{-5}$
---
max sequence length: 512
batch size: 6
model: monologg/biobert_v1.1_pubmed
warmup proportion: 0.1
gradient accumulation steps: 1
| learning rate: (0.001, 0.0001,
---
$2\times 10^{-5}$, $1\times 10^{-6}$))
maximum sequence length: (256, 512)
108M
Longformer |  | learning rate: $2\times 10^{-5}$
---
max sequence length: 1024
batch size: 3
model: longformer-base-4096
warmup proportion: 0.1
gradient accumulation steps: 1
| learning rate: (0.001, 0.0001,
---
$2\times 10^{-5}$, $1\times 10^{-6}$))
maximum sequence length: (1024, 3584)
148M

Table A1: Hyperparameters, tuning bounds and number of parameters for each
method.

##  Appendix B Performance by Category

Category | Binary F1 Score
---|---
|  | LitCovid
---
Dev
CORD-19 Set
Prevention | 92.7 $\pm 0.7$ | 66.7 $\pm 2.5$
Case Report | 87.9 $\pm 1.5$ | 66.7 $\pm 0.0$
Treatment | 85.6 $\pm 0.9$ | 53.9 $\pm 9.0$
Diagnosis | 82.1 $\pm 0.5$ | 63.0 $\pm 3.3$
Mechanism | 81.5 $\pm 2.1$ | 86.8 $\pm 0.8$
Forecasting | 70.3 $\pm 2.3$ | 0.0 $\pm 0.0$
General | 35.5 $\pm 33.9$ | 0.0 $\pm 0.0$
Transmission | 60.9 $\pm 1.6$ | 56.4 $\pm 3.2$
Table A2: BioBERT Binary F1 scores per category on the LitCovid dev set and
the CORD-19 test set. Scores are given as mean $\pm$ standard deviation across
three BioBERT training runs.

##  Appendix C Category Correlation

Category | Full Label |  | Percentage of Docs
---
with Category
Label | Prediction
Forecasting | Single Label | 34.9 | 8.5
\+ Prevention | 62.7 | 88.0
Transmission | Single Label | 16.4 | 16.2
\+ Prevention | 45.4 | 49.0
Table A3: This table shows how the Longformer model predicts (Forecasting &
Prevention) and (Transmission & Prevention) much more frequently than can be
found in the labels. The numbers are percentages of total number of documents
with that category label.