# Regret Analysis of Certainty Equivalence Policies in Continuous-Time Linear-
Quadratic Systems

Mohamad Kazem Shirani Faradonbeh

###### Abstract

This work theoretically studies a ubiquitous reinforcement learning policy for
controlling the canonical model of continuous-time stochastic linear-quadratic
systems. We show that randomized certainty equivalent policy addresses the
exploration-exploitation dilemma in linear control systems that evolve
according to unknown stochastic differential equations and their operating
cost is quadratic. More precisely, we establish square-root of time regret
bounds, indicating that randomized certainty equivalent policy learns optimal
control actions fast from a single state trajectory. Further, linear scaling
of the regret with the number of parameters is shown. The presented analysis
introduces novel and useful technical approaches, and sheds light on
fundamental challenges of continuous-time reinforcement learning.

###### Index Terms:

Adaptive control, Reinforcement learning, Optimal policies, Stochastic
differential equations, Regret bounds, Learning-based control.

##  I Introduction

Linear state-space models are of the most popular settings for decision-making
in continuous-time environments. A canonical problem is to minimize quadratic
costs subject to state-dynamics that follow stochastic differential equations
driven by control actions and Brownian noise. While applications are enormous
[1, 2, 3, 4, 5], little is known about data-driven methods for decision-making
under uncertainty. A natural candidate is the randomized certainty equivalent
policy that utilizes randomizations together with the Certainty Equivalence
principle, and will be the subject of this work.

While the existing literature is rich about reinforcement learning policies
for systems following a _discrete-time_ dynamics [6, 7, 8, 9, 10, 11, 12],
study of efficient policies for _continuous-time_ systems is immature. Early
works focus on asymptotic consistency and propose some control policies with
linearly growing regrets [13, 14, 15]. Further, offline reinforcement learning
algorithms that rely on multiple state trajectories are considered in some
settings [16, 17, 18, 19]. However, performance analysis of _online_ policies
that learn from a _single_ trajectory of system state to design the control
law, are currently sparse [20].

A fundamental challenge (compared to offline methods) is that an online policy
needs to _simultaneously_ minimize the cost and estimate the unknown dynamics.
The dichotomy of these two contradicting, yet mutually necessary objectives is
prevalent in data-driven decision-making. On one hand, we need learning,
estimation, and exploration, as apposed to earning, control, and exploitation
on the other hand. Importantly, accurate estimation is necessary for good
control and for efficiency, while sub-optimal control actions are required in
order to have rich data for estimating accurately.

This work establishes that the popular randomized certainty equivalent
reinforcement learning policy balances the trade-off between the exploration
and exploitation. We present Algorithm 1, which is an episodic randomized
certainty equivalent policy for stochastic continuous-time linear systems. We
provide its regret analysis indicating efficiency; it learns the optimal
control actions fast so that the regret at time $T$ is
$\widetilde{\mathcal{O}}\left({T}^{1/2}\right)$. Therefore, the per-unit-time
sub-optimality gap shrinks with the rate
$\widetilde{\mathcal{O}}\left(T^{-1/2}\right)$ as time proceeds. The presented
bound is tight and is obtained under minimal technical assumptions.

To obtain the results, we need to address important challenges. First,
analysis of estimation error is needed for sample observations with ill-
conditioned information matrices. Further, anti-concentration of singular
values of random matrices, and full characterization of sub-optimalities in
terms of model uncertainties are required. Thus, we develop novel techniques
for establishing the rates of identifying the unknown system dynamics matrices
based on the data of a single state-input trajectory. Leveraging that together
with the effect of diminishing randomizations applied to the parameter
estimates, we tightly bound the rates of narrowing down the sub-optimality
gap. We also utilize useful results about Ito integrals and random matrices to
precisely capture the additional cost of sub-optimal control actions. En
route, different tools from stochastic control, Ito calculus, and stochastic
analysis are used, including Hamilton-Jacobi-Bellman equations, Ito Isometry,
and martingale convergence theorems [1, 2, 5].

The outline of the subsequent sections is provided next. In Section II, we
discuss the problem under investigation. Section III contains the randomized
certainty equivalent Algorithm 1, followed by its theoretical and empirical
analyses in Section IV. Technical proofs are provided in the appendices.

##  II Problem Formulation: Continuous-Time Reinforcement Learning

We study reinforcement learning algorithms for an uncertain controlled
multidimensional Ito stochastic differential equation [5]. The state of the
plant at time $t$ is denoted by $x_{t}\in\mathbb{R}^{p}$, while the control
input is $u_{t}\in\mathbb{R}^{q}$, and we have

$\mathrm{d}x_{t}=A_{\star}x_{t}\mathrm{d}t+B_{\star}u_{t}\mathrm{d}t+C\mathrm{d}\mathbb{W}_{t}.$
(1)

In the above dynamics equation of the system state, the stochastic disturbance
$\left\\{\mathbb{W}_{t}\right\\}_{t\geq 0}$ is a Brownian process.
Technically, $\mathbb{W}_{t}$ has independent normal increments: for all
$0\leq t_{1}\leq t_{2}\leq t_{3}\leq t_{4}$, the vectors
$\mathbb{W}_{t_{2}}-\mathbb{W}_{t_{1}}$ and
$\mathbb{W}_{t_{4}}-\mathbb{W}_{t_{3}}$ are statistically independent, and

$\mathbb{W}_{t_{2}}-\mathbb{W}_{t_{1}}\sim\boldsymbol{N}\left(0,\left(t_{2}-t_{1}\right)I_{p}\right),$

where $\boldsymbol{N}\left(\cdot,\cdot\right)$ is the multivariate normal
distribution. The ${p\times p}$ matrix $C$ might amplify the stochastic
disturbance.

For the plant under consideration, $A_{\star}$ is the state evolution matrix
and $B_{\star}$ reflects the influence if the control signal. While
$A_{\star},B_{\star},C$ are _unknown_ , we aim to design efficient algorithms
to minimize the quadratic cost function averaged over time;

$\min\limits_{\left\\{u_{t}\right\\}_{t\geq
0}}\limsup\limits_{T\to\infty}\frac{1}{T}\int\limits_{0}^{T}{\left(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}\right)}\mathrm{d}{t},$
(2)

where the symmetric positive definite matrices $Q,R$ have proper dimensions.
Above, the minimum is taken over non-anticipating closed-loop reinforcement
learning policies, as elaborated below. The policy determines $u_{t}$
according to the information available at the time, which comprise the state
observations $\left\\{x_{s}\right\\}_{0\leq s\leq t}$ and the previously taken
actions $\left\\{u_{s}\right\\}_{0\leq s<t}$. Importantly, the policy faces
the fundamental exploration-exploitation dilemma, because the plant matrices
$A_{\star},B_{\star}$ are unknown. The details of this challenge will be
discussed in Section III. It is standard to focus on the setting that $Q,R$
are known, the rationale being that the decision-maker is aware of the
objective. We also assume plant stabilizability:

######  Assumption 1.

There is a matrix $K_{\star}\in\mathbb{R}^{q\times p}$, such that all
eigenvalues of ${A_{\star}+B_{\star}K_{\star}}$ have negative real-parts.

Assumption 1 expresses that by applying $u_{t}=K_{\star}x_{t}$, the system can
operate without unbounded growth in the state. Technically, if we apply the
above feedback control law, and solve the differential equation in (1), it
holds that

$x_{t}=e^{\left(A_{\star}+B_{\star}K_{\star}\right)t}x_{0}+\int\limits_{0}^{t}{e^{\left(A_{\star}+B_{\star}K_{\star}\right)(t-s)}C}\mathrm{d}{\mathbb{W}_{s}}.$
(3)

According to the above equation, if an eigenvalue of
${A_{\star}+B_{\star}K_{\star}}$ has a non-negative real-part, the state
$x_{t}$ grows unbounded with $t$. Thus, Assumption 1 is required for a well-
posed problem. Otherwise, state explosion renders the cost infinite for all
policies [1, 2]. Note that $A_{\star},B_{\star}$, and so $K_{\star}$, are
unknown.

In the sequel, we examine effects of uncertainties about $A_{\star},B_{\star}$
on the increase in cost compared to its optimal value. The common assessmet
criteria in reinforcement learning is to compare the policy under
consideration to the optimal control law $u^{\star}_{t}$ that is decided
according to $A_{\star},B_{\star}$. Namely, for generic dynamics matrices
$A,B$, define the feedback matrix $\boldsymbol{K}_{A,B}$ based on
$\boldsymbol{P}_{A,B}$, that solves

$A^{\top}\boldsymbol{P}_{A,B}+\boldsymbol{P}_{A,B}A-\boldsymbol{P}_{A,B}BR^{-1}B^{\top}\boldsymbol{P}_{A,B}+Q=0.$
(4)

######  Definition 1.

For generic dynamics matrices $A,B$, define
$\boldsymbol{K}_{A,B}=-R^{-1}B^{\top}\boldsymbol{P}_{A,B}$, where
$\boldsymbol{P}_{A,B}$ satisfies (4).

So, the unique existence of $\boldsymbol{P}_{A_{\star},B_{\star}}$ and
optimality of the following control law are proven in the literature [1, 2]:

$u^{\star}_{t}=\boldsymbol{K}_{A_{\star},B_{\star}}x^{\star}_{t},~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{for
all }~{}~{}t\geq 0.$ (5)

######  Theorem 1.

The matrix $\boldsymbol{P}_{A_{\star},B_{\star}}$ in (4) uniquely exists, and
the linear feedback policy in (5) is optimal.

To see the intuition of (4) for obtaining the optimal policy in (5), note that
the control action $u_{t}$ directly influences the current cost value, and
indirectly affects the future costs according to (1). So, the effects of
control actions in the future need to be considered for minimizing the cost
function in (2), and this consideration is performed by
$\boldsymbol{P}_{A_{\star},B_{\star}}$ [1, 2].

Next, we formulate sub-optimalities and increase in cost due to lack of
knowledge about the optimal actions $u^{\star}_{t}$. For a reinforcement
learning policy, its _regret_ is the total increase in the cost by the time.
That is, the gap between the cost the adaptive control law incurs and that of
the optimal feedback in (5) is integrated over the interval
$\left[0,T\right]$:

$\mathrm{\bf
Reg}\left(T\right)=\int\limits_{0}^{T}{\left(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}-{x^{\star}_{t}}^{\top}Qx^{\star}_{t}-{u^{\star}_{t}}^{\top}Ru^{\star}_{t}\right)}\mathrm{d}{t}.$

Note that the stochastic state $x_{t}$ and control signal $u_{t}$ make the
regret a random variable. We perform worst-case analysis and bound
$\mathrm{\bf Reg}\left(T\right)$ in terms of $T,p,q$. If the increasing
observations of state and action over time will be effectively leveraged, the
policy eventually takes near-optimal actions. So, $\mathrm{\bf
Reg}\left(T\right)$ is expected to scale sub-linearly with $T$. However,
design of efficient policies with
$\widetilde{\mathcal{O}}\left(\sqrt{T}\right)$ regret and proving performance
guarantees for them is challenging, as will be discussed shortly.

##  III Randomized Certainty Equivalent Policy: Algorithm and Intuition

Now, we discuss how randomization of control inputs that are designed
according to the Certainty Equivalence principle suffices for learning based
control of the plant in (1). We aim to have computationally fast algorithms
with efficient performance guarantees for minimizing the cost function defined
in (2). That is, low-regret control laws that can deal with uncertainties
about $A_{\star},B_{\star}$.

First, we explain the challenge of balancing exploration (i.e., estimation)
versus exploitation (i.e., control). Then, we study a useful method for
estimating the system matrices according to the applied control law and the
generated state signal. Based on them, the randomized certainty equivalent
adaptive control law that randomizes the parameter estimates to balance
estimation and control is discussed, as shown in Algorithm 1. Finally, we
provide theoretical and empirical performance analyses for the proposed
algorithm.

In order to have a policy whose regret is not very large, we need
$u_{t}\approx\boldsymbol{K}_{A_{\star},B_{\star}}x_{t}$. Furthermore, since
$A_{\star},B_{\star}$ are unknown, the control policy needs to estimate them
according to the available trajectory by the time, which is
$\left\\{x_{s},u_{s}\right\\}_{0\leq s\leq t}$. However, if it holds that
$u_{s}\approx\boldsymbol{K}_{A_{\star},B_{\star}}x_{s}$, then the coordinates
$u_{s}$ of the data $x_{s},u_{s}$ cannot significantly contribute to the
estimation procedure; roughly speaking, because they are nothing but linear
functions of the state coordinates $x_{s}$. Accordingly, accurate estimation
of $A_{\star},B_{\star}$ becomes infeasible, defeating the original purpose.
Note that $A_{\star},B_{\star}$ need to be precisely estimated for actuating
the plant with near-optimal control inputs. The above-mentioned dilemma is an
important challenge and indicates the fact that a good adaptive control law
must _randomize_ the control inputs $u_{s}$, and so unavoidably it _deviates_
from the optimal feedback policy
$u^{\star}_{s}=\boldsymbol{K}_{A_{\star},B_{\star}}x^{\star}_{s}$.

Next, we derive an estimator for the unknown dynamics matrices
$A_{\star},B_{\star}$. Intuitively speaking, a framework similar to linear
regression is used to estimate ${A},{B}$ using the observed trajectories of
the state and the input signal. To proceed, suppose that we aim to use samples
of the trajectory at $\epsilon$-apart discrete time points;
$\left\\{x_{k\epsilon},u_{k\epsilon}\right\\}_{k=0}^{n}$. So, for small
$\epsilon$, the stochastic differential equation of the system dynamics in (1)
gives

$x_{(k+1)\epsilon}-x_{k\epsilon}\approx\left(A_{\star}x_{k\epsilon}+B_{\star}u_{k\epsilon}\right)\epsilon+C\left(\mathbb{W}_{(k+1)\epsilon}-\mathbb{W}_{k\epsilon}\right).$

Fitting a linear regression, the least-squares estimate is

$\arg\min\limits_{{A},{B}}\sum\limits_{k=0}^{n-1}{\left|\kern-1.29167pt\left|x_{(k+1)\epsilon}-x_{k\epsilon}-\left({A}x_{k\epsilon}+{B}u_{k\epsilon}\right)\epsilon\right|\kern-1.29167pt\right|}^{2},$

which, letting $y_{s}=\left[x_{s}^{\top},u_{s}^{\top}\right]^{\top}$, leads to

$\left[{A},{B}\right]=\sum\limits_{k=0}^{n-1}\left(x_{(k+1)\epsilon}-x_{k\epsilon}\right)y_{k\epsilon}^{\top}\left(\sum\limits_{k=0}^{n-1}y_{k\epsilon}y_{k\epsilon}^{\top}\epsilon\right)^{-1}.$

Therefore, letting $\epsilon\to 0$, we get the continuous-time estimator in
(7) that estimates $A_{\star},B_{\star}$ at the end of every episode of
Algorithm 1, as explained below.

To introduce the episodes of the algorithm, we use the sequence
$\left\\{\tau_{n}\right\\}_{n=0}^{\infty}$ that contains the time points at
which the adaptive control law renews its estimates of the unknown system
matrices. Namely, during the episode $\tau_{n}\leq t<\tau_{n+1}$, Algorithm 1
applies the adaptive feedback policy
$u_{t}=\boldsymbol{K}_{{A}_{n},{B}_{n}}x_{t}$, where ${A}_{n},{B}_{n}$ are the
above-mentioned estimates for $A_{\star},B_{\star}$. The episode lengths
satisfy

$\underline{\beta}\leq\inf\limits_{n\geq
1}\frac{\tau_{n+1}-\tau_{n}}{\tau_{n}}\leq\sup\limits_{n\geq
1}\frac{\tau_{n+1}-\tau_{n}}{\tau_{n}}\leq\overline{\beta},$ (6)

for some constants $\underline{\beta}>0,\overline{\beta}<\infty$. The
rationale for freezing the parameter estimates during the episodes is that the
learning procedure can be deferred until collecting enough new observations.
Clearly, smaller $\underline{\beta},\overline{\beta}$ mean shorter episodes
and more frequent updates in parameter estimates, which gives better
exploration. Still, the episode lengths $\tau_{n+1}-\tau_{n}$ grow large to
preclude unnecessary updates.

Further, to ensure that the policy is sufficiently committed to explore the
environment, a random matrix $\Phi_{n}$ is added to the least-squares
estimate, as shown in (7), where $\left\\{\Phi_{n}\right\\}_{n=0}^{\infty}$
are $p\times\left(p+q\right)$ random matrices, independent of everything else
and of each others, and has independent standard Gaussian entries. The
randomized certainty Equivalent reinforcement learning policy is provided in
Algorithm 1.

Algorithm 1 Randomized Certainty Equivalent Policy

1:Let ${A}_{0},{B}_{0}$ be the initial estimates and
$\left\\{\tau_{n}\right\\}_{n=1}^{\infty}$ satisfy (6)

2:for $n=1,2,\cdots$ do

3: while $\tau_{n-1}\leq t<\tau_{n}$ do

4: Apply the feedback $u_{t}=\boldsymbol{K}_{{A}_{n-1},{B}_{n-1}}x_{t}$

5: end while

6: Let $y_{s}=\left[x_{s}^{\top},u_{s}^{\top}\right]^{\top}$ and calculate
$\left[{A}_{n},{B}_{n}\right]={\left[\int\limits_{0}^{\tau_{n}}{y_{s}}\mathrm{d}{x_{s}^{\top}}\right]^{\top}\left(\int\limits_{0}^{\tau_{n}}{y_{s}y_{s}^{\top}}\mathrm{d}{s}\right)^{-1}}+\frac{\Phi_{n}}{\tau_{n}^{1/4}}.$
(7)

7:end for

The coefficients $\tau_{n}^{-1/4}$ of the sequence of random matrices are
employed to serve a two-fold purpose. On one hand, the scaled random matrix
$\tau_{n}^{-1/4}\Phi_{n}$ is large enough to significantly randomize the
estimates and _explore_. At the same time, $\tau_{n}^{-1/4}\Phi_{n}$ is
sufficiently _small_ to prevent significant deviations from the least-squares
estimates and from the optimal actions. Otherwise, large randomizations
deteriorate the _exploitation_.

Note that implementation of Algorithm 1 is fast and requires minimal memory,
as one needs to only update the integrals in (7) in an online fashion.

##  IV Performance Analysis: Regret Bound

Next, we establish Theorem 2 that expresses efficiency of Algorithm 1 in the
sense that its regret is $\widetilde{\mathcal{O}}\left(\sqrt{T}\right)$.

We suppose that when running Algorithm 1, the system evolves in a stable
manner. That can be equivalently stated as follows: in the plane of complex
numbers, all eigenvalues of
$A_{\star}+B_{\star}\boldsymbol{K}_{{A}_{n},{B}_{n}}$ belong to the left half-
plane, excluding the imaginary axis. This stability can be ensured in
different ways. First, it suffices to find an initial stabilizing policy [21,
14, 15]. If such initial stabilizer is available, one can apply it and devote
a (relatively short) time period to exploration, such that the collected data
provide a coarse approximation of the true matrices $A_{\star},B_{\star}$.
Then, it is shown that such coarse-grained approximations are sufficient for
stabilization [14, 22]. Otherwise, to find an initial stabilizer, we can
employ Bayesian learning algorithms for a short time period to form a
posterior belief about $A_{\star},B_{\star}$. Then, it is known that samples
from the posterior belief guarantee high probability stabilization [22]. Since
the sampling procedure can be repeated, we can assume that Algorithm 1 remains
stable. Further details can be found in the references, as well as in the
papers on discrete-time stabilization [6, 23, 24, 25, 26].

To establish regret bounds for Algorithm 1, we assume that the Brownian noise
influences all state variables:

######  Assumption 2.

The matrix $C$ in (1) is full-rank.

This assumption is standard to ensure that the optimal actions can be learned
over the course of interactions with the environment [27, 28, 15, 29, 19, 22].
Intuitively, it indicates that all state variables have significant roles and
a smaller subset of them is _insufficient_ for capturing the dynamics of the
environment. Now, we present a theoretical performance guarantee for the
randomized certainty equivalent policy.

######  Theorem 2.

The adaptive control law in Algorithm 1 gives

$\mathrm{\bf Reg}\left(T\right)=\mathcal{O}\left(d^{2}\sqrt{T}\log T\right),$

where $d=p+q$ is the total dimension of the system.

Above, note that $d^{2}$ scales linearly with the number of unknown parameters
in $A_{\star},B_{\star}$, which is $p(p+q)$.

Figure 1: The above graph presents curves of the normalized regret
$T^{-1/2}\mathrm{\bf Reg}\left(T\right)$ vs $T$, for Algorithm 1. Multiple
replicates of the system are simulated, all of them corroborate Theorem 2 that
the normalized regret remains bounded as time grows.

We experiment Algorithm 1 for adaptive control of an airplane [30]. It is
known that the lateral-directional state-space model is of dimensions $p=4$,
$q=2$:

$\displaystyle A_{\star}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}-0.185&0.1475&-0.9825&0.1120\\\
-0.347&-1.710&0.9029&-0.58\times 10^{-6}\\\ 1.174&-0.0825&-0.1826&-0.44\times
10^{-7}\\\ 0.0&1.0&0.1429&0.0\end{bmatrix},$ $\displaystyle B_{\star}$
$\displaystyle=$ $\displaystyle\begin{bmatrix}-0.4470\times
10^{-3}&0.4020\times 10^{-3}\\\ 0.3715&0.0549\\\ 0.0265&-0.0135\\\
0.0&0.0\end{bmatrix}.$

Moreover, we let $C=0.2\times I_{4}$, $Q=I_{p}$, $R=0.1\times I_{q}$,
$\tau_{n}=25\times 1.2^{n}$, and run Algorithm 1 for the system in (1), where
$A_{\star},B_{\star}$ are unknown to the algorithm.

Figure 1 depicts the normalized regret versus time for Algorithm 1. The
horizontal axis is $T$, while the vertical one corresponds
$T^{-1/2}\mathrm{\bf Reg}\left(T\right)$. It shows the result of Theorem 2
that the normalized regret is almost bounded.

##  V Concluding Remarks and Future Work

This work studies the randomized certainty equivalent reinforcement learning
policy in continuous-time stochastic linear systems with quadratic operating
cost functions. We presented theoretical performance analysis of the
randomized certainty equivalent algorithm showing that it is efficient. More
precisely, we established a regret bound that its growing rate as time
proceeds is square-root. Further, dependence on the problem dimension is
quadratic indicating that the regret grows as a linear function of the number
of system parameters.

The presented results motivate interesting directions in the study of
reinforcement learning algorithms for continuous-time environments. Finding
regret bounds that hold uniformly over time, and deriving performance
guarantees in high-dimensional systems with sparse or low-rank dynamics
matrices, are interesting problems for future work. Moreover, extension of the
presented analysis to reinforcement learning policies under imperfectly
observed state, and control laws for nonlinear systems, can be listed as
problems of interest for future investigations.

## Outline of the Appendices

In the first appendix, we prove Theorem 2. Then, the auxiliary lemmas used in
the proof are provided.

##  Appendix A Proof of Theorem 2

Let $y_{s}=\left[x_{s}^{\top},u_{s}^{\top}\right]^{\top}$ and
$V_{n}=\int\limits_{0}^{\tau_{n}}{y_{s}y_{s}^{\top}}\mathrm{d}{s}.$ Replace
for $\mathrm{d}x_{t}$ from (1) to obtain

$\int\limits_{0}^{\tau_{n}}{y_{s}}\mathrm{d}{x_{s}^{\top}}=\int\limits_{0}^{\tau_{n}}{y_{s}y_{s}^{\top}\left[A_{\star},B_{\star}\right]^{\top}}\mathrm{d}{s}+\int\limits_{0}^{\tau_{n}}{y_{s}}\mathrm{d}{\mathbb{W}_{s}^{\top}}C^{\top}.$

So, we have

$\left[\int\limits_{0}^{\tau_{n}}{y_{s}}\mathrm{d}{x_{s}^{\top}}\right]^{\top}V_{n}^{-1}=\left[A_{\star},B_{\star}\right]+\left[V_{n}^{-1}\int\limits_{0}^{\tau_{n}}{y_{s}}\mathrm{d}{\mathbb{W}_{s}^{\top}}C^{\top}\right]^{\top}.$

The above, the triangle inequality, and (7), yield to

${\left|\kern-1.1625pt\left|\left[{A}_{n},{B}_{n}\right]-\left[A_{\star},B_{\star}\right]\right|\kern-1.1625pt\right|}\leq{\left|\kern-1.1625pt\left|V_{n}^{-1}\int\limits_{0}^{\tau_{n}}{y_{s}}\mathrm{d}{\mathbb{W}_{s}^{\top}}C^{\top}\right|\kern-1.1625pt\right|}+{\left|\kern-1.1625pt\left|\tau_{n}^{-1/4}\Phi_{n}\right|\kern-1.1625pt\right|}.$

Since entries of $\tau_{n}^{-1/4}\Phi_{n}$ have
$\boldsymbol{N}\left(0,{\tau_{n}}^{-1/2}\right)$ distribution, for $\beta>0$
we have

$\log\mathbb{P}{\left({\left|\kern-1.1625pt\left|\tau_{n}^{-1/4}\Phi_{n}\right|\kern-1.1625pt\right|}\geq
p^{1/2}\left(p+q\right)^{1/2}{\tau_{n}}^{-1/4}\beta\right)}=\mathcal{O}\left({-\beta^{2}}\right).$

This, by Borel-Cantelli Lemma and $\tau_{n}\to\infty$, gives

${\left|\kern-1.29167pt\left|\tau_{n}^{-1/4}\Phi_{n}\right|\kern-1.29167pt\right|}=\mathcal{O}\left(d{\tau_{n}}^{-1/4}\log^{1/2}\tau_{n}\right).$

Thus, by Lemma 2,
${\left|\kern-1.29167pt\left|\left[{A}_{n},{B}_{n}\right]-\left[A_{\star},B_{\star}\right]\right|\kern-1.29167pt\right|}$
is at most

$\mathcal{O}\left(d\left(\frac{\log\boldsymbol{\lambda}_{\max}\left(V_{n}\right)}{\boldsymbol{\lambda}_{\min}\left(V_{n}\right)}\right)^{1/2}+d\tau_{n}^{-1/4}\log^{1/2}\tau_{n}\right).$
(8)

Now, Lemma 4 provides
${\log\boldsymbol{\lambda}_{\max}\left(V_{n}\right)}=\mathcal{O}\left(\log\tau_{n}\right)$.
On the other hand, we will establish in the sequel that:

$\liminf\limits_{n\to\infty}\tau_{n}^{-1/2}\boldsymbol{\lambda}_{\min}\left(V_{n}\right)>0.$
(9)

Thus, (8) and (9) lead to

${\left|\kern-1.29167pt\left|\left[{A}_{n},{B}_{n}\right]-\left[A_{\star},B_{\star}\right]\right|\kern-1.29167pt\right|}=\mathcal{O}\left(d\tau_{n}^{-1/4}\log^{1/2}\tau_{n}\right).$
(10)

Next, Lemma 3 implies that

${\left|\kern-1.29167pt\left|\boldsymbol{K}_{{A}_{n},{B}_{n}}-\boldsymbol{K}_{A_{\star},B_{\star}}\right|\kern-1.29167pt\right|}^{2}=\mathcal{O}\left(d^{2}\tau_{n}^{-1/2}\log\tau_{n}\right).$

Since during the episode $\tau_{n-1}\leq t<\tau_{n}$ the parameter estimates
are not updated; $K_{t}=\boldsymbol{K}_{{A}_{n-1},{B}_{n-1}}$, by Lemma 4, we
have

$\displaystyle\int\limits_{0}^{\tau_{n}}{{\left|\kern-1.29167pt\left|\left(K_{t}-\boldsymbol{K}_{A_{\star},B_{\star}}\right)x_{t}\right|\kern-1.29167pt\right|}^{2}}\mathrm{d}{t}$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\sum\limits_{k=1}^{n}\frac{\tau_{k}-\tau_{k-1}}{\tau_{k-1}^{1/2}}d^{2}\log\tau_{k-1}\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\sum\limits_{k=1}^{n}\left(\tau_{k}^{1/2}-\tau_{k-1}^{1/2}\right)d^{2}\log\tau_{n}\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(\tau_{n}^{1/2}d^{2}\log\tau_{n}\right),$

where in the last two equalities above we used (6).

Moreover, considering the matrix
$A_{\star}+B_{\star}\boldsymbol{K}_{A_{\star},B_{\star}}$, since all of its
eigenvalues are negative-real, the matrix denoted by $E_{t}$ in Lemma 1 decays
exponentially with $t$. So, we have

${\int\limits_{0}^{T}{\left(x_{t}^{\top}E_{T-t}\left(K_{t}-\boldsymbol{K}_{A_{\star},B_{\star}}\right)x_{t}\right)}\mathrm{d}{t}}=\mathcal{O}\left(\log^{2}T\right).$

Thus, plugging the above two results in Lemma 1, it implies that the statement
of Theorem 2 holds.

As such, to finish this proof, we can prove (9). To do so, note that (6)
together with Lemma 4 give

$\liminf\limits_{k\to\infty}\tau_{k}^{-1}\boldsymbol{\lambda}_{\min}\left(\int\limits_{\tau_{k-1}}^{\tau_{k}}{x_{t}x_{t}^{\top}}\mathrm{d}{t}\right)>0.$
(11)

Thus, for getting (9), it is enough to establish

$\liminf\limits_{n\to\infty}\boldsymbol{\lambda}_{\min}\left(\sum\limits_{k=\ell}^{n-1}\frac{\tau_{k}}{\tau_{n}^{1/2}}\begin{bmatrix}I_{p}\\\
\boldsymbol{K}_{{A}_{k},{B}_{k}}\end{bmatrix}\begin{bmatrix}I_{p}\\\
\boldsymbol{K}_{{A}_{k},{B}_{k}}\end{bmatrix}^{\top}\right)>0,$ (12)

for some $0\leq\ell<n-1$.

For $\epsilon>0$, consider the case of the above-mentioned least eigenvalue
being strictly smaller than $\epsilon$. Further, denote by
$\mathcal{M}_{n}(\epsilon)$, a set that contains all matrices such as
$\left[{A}_{k},{B}_{k}\right]_{k=\ell}^{n-1}$, for which the upper bound
$\epsilon$ on the least eigenvalue in (12) occurs. More precisely, define the
${(p+q)\times p(n-\ell)}$ matrix $P_{\ell,n}$ as

$\left[\tau_{\ell}^{1/2}\tau_{n}^{-1/4}\begin{bmatrix}I_{p}\\\
\boldsymbol{K}_{{A}_{\ell},{B}_{\ell}}\end{bmatrix},\cdots,\tau_{n-1}^{1/2}\tau_{n}^{-1/4}\begin{bmatrix}I_{p}\\\
\boldsymbol{K}_{{A}_{n-1},{B}_{n-1}}\end{bmatrix}\right].$

Then, let

$\mathcal{M}_{n}(\epsilon)=\left\\{\left[{A}_{\ell},{B}_{\ell},\cdots,{A}_{n-1},{B}_{n-1}\right]:\boldsymbol{\lambda}_{\min}\left(P_{\ell,n}P_{\ell,n}^{\top}\right)\leq\epsilon\right\\}.$

Now, note that the set of all matrices

$F_{n}=\begin{bmatrix}\tau_{\ell}^{1/2}\tau_{n}^{-1/4}I_{p}&\cdots&\tau_{n-1}^{1/2}\tau_{n}^{-1/4}I_{p}\\\
\tau_{\ell}^{1/2}\tau_{n}^{-1/4}K_{\ell}&\cdots&\tau_{n-1}^{1/2}\tau_{n}^{-1/4}K_{n-1}\end{bmatrix},$

for which there is $v\in\mathbb{R}^{p+q}$ satisfying
${\left|\kern-1.29167pt\left|v\right|\kern-1.29167pt\right|}=1\text{,
}F_{n}^{\top}v=0,$ is of dimension $p+q-1+(n-\ell)(q-1)$, as follows:

  1. 1.

The set of unit $p+q$ dimensional vectors is (a sphere) of dimension $p+q-1$.

  2. 2.

Write $v=\left[v_{1}^{\top},v_{2}^{\top}\right]^{\top}$, for
$v_{1}\in\mathbb{R}^{p}$ and $v_{2}\in\mathbb{R}^{q}$. So, $F_{n}^{\top}v=0$,
if and only if $K_{k}^{\top}v_{2}=-v_{1}$, for all $k=\ell,\cdots,n-1$. This
means every column of $K_{k}$ is in a certain hyperplane in $\mathbb{R}^{q}$.

According to Lemma 5, the dimension of $\mathcal{M}_{n}(0)$ is at most

$p+q-1+(q-1)(n-\ell)+(n-\ell)p^{2},$

and it lives in a $p(p+q)(n-\ell)$ dimensional space. So, the difference
between the dimensions is

$m=\left(pq-q+1\right)(n-\ell)-p-q+1.$

Further, if $\ell$ is sufficiently large so that
$\tau_{\ell}^{-1}\tau_{n}^{1/2}\epsilon<1$, then for every
$\left[{A}_{k},{B}_{k}\right]_{k=\ell}^{n-1}\in\mathcal{M}_{n}(\epsilon)$,
there exists some
$\left[\widetilde{A}_{k},\widetilde{B}_{k}\right]_{k=\ell}^{n-1}\in\mathcal{M}_{n}(0)$,
such that

$\max\limits_{\ell\leq k\leq
n-1}{\left|\kern-1.29167pt\left|\left[{A}_{k},{B}_{k}\right]-\left[\widetilde{A}_{k},\widetilde{B}_{k}\right]\right|\kern-1.29167pt\right|}=\mathcal{O}\left(\tau_{k}^{-1/2}\tau_{n}^{1/4}\epsilon^{1/2}\right).$

Next, we use the above result to bound the probability of
$\mathcal{M}_{n}(\epsilon)$. Note that the random matrices
$\left\\{\Phi_{k}\right\\}_{k=0}^{n-1}$ are independent, and entries of
$\tau_{k}^{-1/4}\Phi_{k}$ are independent identically distributed
$\boldsymbol{N}\left(0,\tau_{k}^{-1/2}\right)$ random variables. Recall that
the difference between the dimensions of $\mathcal{M}_{n}(0)$ and the space it
is in, is $m$, as defined above. Hence, since $\tau_{\ell}\leq\tau_{k}$, we
have

$\mathbb{P}{\left(\mathcal{M}_{n}(\epsilon)\right)}=\left[\mathcal{O}\left(\tau_{\ell}^{1/4}\tau_{\ell}^{-1/2}\tau_{n}^{1/4}\epsilon^{1/2}\right)\wedge
1\right]^{m}.$

Letting $\ell=n-5$, we have $m\geq 5$. Further, if $\epsilon$ is small enough
to satisfy
$\mathcal{O}\left(\tau_{n}^{1/4}\tau_{\ell}^{-1/4}\epsilon^{1/2}\right)<1,$ we
have

$\sum\limits_{n=5}^{\infty}\mathbb{P}{\left(\mathcal{M}_{n}(\epsilon)\right)}<\infty.$

The above, by Borel-Cantelli Lemma, implies (12), which completes the proof.

##  Appendix B Auxiliary Results

This appendix presents the lemmas used in the proof of Theorem 2 in the
previous appendix. First, Lemma 1 expresses the regret in terms of the
deviations of the control input from the optimal feedback control law. Then,
in Lemma 2 we present the growth rates of stochastic integrals normalized by
the empirical state-input covariance matrix. Lemma 3 establishes that
$\boldsymbol{K}_{{A},{B}}$ is a (Lipschitz) continuous function of ${A},{B}$.
Next, the state empirical covariance matrix is shown to converge to a positive
definite limit in Lemma 4. Finally, the result of Lemma 5 provides the
dimension of the optimality manifold. Proofs are omitted here due to limited
space, but they are available in [31].

######  Lemma 1.

Suppose that $K_{t}$ is piecewise continuous and $u_{t}=K_{t}x_{t}$ is applied
to the system in (1). Define
$\boldsymbol{K}_{\star}=\boldsymbol{K}_{A_{\star},B_{\star}}$,
$D_{\star}=A_{\star}+B_{\star}\boldsymbol{K}_{\star}$,
$E_{t}=e^{D_{\star}^{\top}t}\boldsymbol{P}_{A_{\star},B_{\star}}e^{D_{\star}t}B_{\star}$,

$\displaystyle\alpha_{T}=\int\limits_{0}^{T}{\left({\left|\kern-1.1625pt\left|\left(K_{t}-\boldsymbol{K}_{\star}\right)x_{t}\right|\kern-1.1625pt\right|}^{2}-2x_{t}^{\top}E_{T-t}\left(K_{t}-\boldsymbol{K}_{\star}\right)x_{t}\right)}\mathrm{d}{t}.$

Then, we have $\mathrm{\bf
Reg}\left(T\right)=\mathcal{O}\left(\alpha_{T}\right)$.

######  Lemma 2.

For $y_{t}=\left[x_{t}^{\top},u_{t}^{\top}\right]^{\top}$, let
$V_{t}=\int\limits_{0}^{t}{y_{s}y_{s}^{\top}}\mathrm{d}{s}$. Then, it holds
that

${\left|\kern-1.29167pt\left|\left(I+V_{t}\right)^{-1/2}\int\limits_{0}^{t}{y_{s}}\mathrm{d}{\mathbb{W}_{s}^{\top}}\right|\kern-1.29167pt\right|}^{2}=\mathcal{O}\left(d^{2}\log\boldsymbol{\lambda}_{\max}\left(V_{t}\right)\right).$

######  Lemma 3.

There exists $\beta_{\star}<\infty$, such that

${\left|\kern-1.29167pt\left|\boldsymbol{K}_{{A},{B}}-\boldsymbol{K}_{A_{\star},B_{\star}}\right|\kern-1.29167pt\right|}\leq\beta_{\star}{\left|\kern-1.29167pt\left|\left[{A},{B}\right]-\left[A_{\star},B_{\star}\right]\right|\kern-1.29167pt\right|}.$

######  Lemma 4.

In Algorithm 1, suppose that all eigenvalues of
$A_{\star}+B_{\star}\boldsymbol{K}_{{A}_{n},{B}_{n}}$ have negative real-
parts. Then, the following matrix is deterministic and positive definite:

$\displaystyle\lim\limits_{n\to\infty}\frac{1}{\tau_{n+1}-\tau_{n}}\int\limits_{\tau_{n}}^{\tau_{n+1}}{x_{t}x_{t}^{\top}}\mathrm{d}{t}.$

######  Lemma 5.

For some fixed ${A}_{0},{B}_{0}$, consider

$\displaystyle\mathcal{N}_{0}=\left\\{\left[{A},{B}\right]\in\mathbb{R}^{p\times\left(p+q\right)}:\boldsymbol{K}_{{A},{B}}=\boldsymbol{K}_{{A}_{0},{B}_{0}}\right\\}.$

The set $\mathcal{N}_{0}$ is a manifold of dimension $p^{2}$.

## References

  * [1] R. F. Stengel, _Optimal control and estimation_. Courier Corporation, 1994.
  * [2] J. Yong and X. Y. Zhou, _Stochastic controls: Hamiltonian systems and HJB equations_. Springer Science & Business Media, 1999, vol. 43.
  * [3] H. Schmidli, _Stochastic control in insurance_. Springer Science & Business Media, 2007.
  * [4] N. D. Lawrence, M. Girolami, M. Rattray, and G. Sanguinetti, _Learning and inference in computational systems biology_. MIT press, 2010.
  * [5] B. Oksendal, _Stochastic differential equations: an introduction with applications_. Springer Science & Business Media, 2013.
  * [6] Y. Abbasi-Yadkori and C. Szepesvári, “Regret bounds for the adaptive control of linear quadratic systems,” in _Proceedings of the 24th Annual Conference on Learning Theory_. JMLR Workshop and Conference Proceedings, 2011, pp. 1–26.
  * [7] Y. Ouyang, M. Gagrani, and R. Jain, “Posterior sampling-based reinforcement learning for control of unknown linear systems,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 8, pp. 3600–3607, 2019.
  * [8] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis, “On adaptive linear–quadratic regulators,” _Automatica_ , vol. 117, p. 108982, 2020.
  * [9] ——, “Input perturbations for adaptive control and learning,” _Automatica_ , vol. 117, p. 108950, 2020.
  * [10] A. Cassel, A. Cohen, and T. Koren, “Logarithmic regret for learning linear quadratic regulators efficiently,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 1328–1337.
  * [11] S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar, “Logarithmic regret bound in partially observable linear dynamical systems,” _arXiv preprint arXiv:2003.11227_ , 2020.
  * [12] I. Ziemann and H. Sandberg, “On uninformative optimal policies in adaptive lqr with unknown b-matrix,” in _Learning for Dynamics and Control_. PMLR, 2021, pp. 213–226.
  * [13] P. Mandl, T. E. Duncan, and B. Pasik-Duncan, “On the consistency of a least squares identification procedure,” _Kybernetika_ , vol. 24, no. 5, pp. 340–346, 1988.
  * [14] T. E. Duncan, L. Guo, and B. Pasik-Duncan, “Adaptive continuous-time linear quadratic gaussian control,” _IEEE Transactions on automatic control_ , vol. 44, no. 9, pp. 1653–1662, 1999.
  * [15] P. E. Caines and D. Levanony, “Stochastic $\varepsilon$-optimal linear quadratic adaptation: An alternating controls policy,” _SIAM Journal on Control and Optimization_ , vol. 57, no. 2, pp. 1094–1126, 2019.
  * [16] T. Bian, Y. Jiang, and Z.-P. Jiang, “Adaptive dynamic programming for stochastic systems with state and control dependent noise,” _IEEE Transactions on Automatic control_ , vol. 61, no. 12, pp. 4170–4175, 2016.
  * [17] K. Doya, “Reinforcement learning in continuous time and space,” _Neural computation_ , vol. 12, no. 1, pp. 219–245, 2000.
  * [18] H. Wang, T. Zariphopoulou, and X. Y. Zhou, “Reinforcement learning in continuous time and space: A stochastic control approach.” _J. Mach. Learn. Res._ , vol. 21, pp. 198–1, 2020.
  * [19] M. Basei, X. Guo, A. Hu, and Y. Zhang, “Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon,” _Available at SSRN 3848428_ , 2021.
  * [20] M. K. S. Faradonbeh, M. S. S. Faradonbeh, and M. Bayati, “Thompson sampling efficiently learns to control diffusion processes,” _arXiv preprint arXiv:2206.09977_ , 2022.
  * [21] P. Caines, “Continuous time stochastic adaptive control: non-explosion, $\varepsilon$-consistency and stability,” _Systems & control letters_, vol. 19, no. 3, pp. 169–176, 1992.
  * [22] M. K. S. Faradonbeh and M. S. S. Faradonbeh, “Bayesian algorithms learn to stabilize unknown continuous-time systems,” _arXiv preprint arXiv:2112.15094_ , 2021.
  * [23] 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.
  * [24] ——, “Randomized algorithms for data-driven stabilization of stochastic linear systems,” in _2019 IEEE Data Science Workshop (DSW)_. IEEE, 2019, pp. 170–174.
  * [25] S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar, “Explore more and improve regret in linear quadratic regulators,” _arXiv preprint arXiv:2007.12291_ , 2020.
  * [26] X. Chen and E. Hazan, “Black-box control for linear dynamical systems,” in _Conference on Learning Theory_. PMLR, 2021, pp. 1114–1143.
  * [27] D. Levanony and P. E. Caines, “On persistent excitation for linear systems with stochastic coefficients,” _SIAM journal on control and optimization_ , vol. 40, no. 3, pp. 882–897, 2001.
  * [28] A. Subrahmanyam and G. P. Rao, _Identification of Continuous-time Systems: Linear and Robust Parameter Estimation_. CRC Press, 2019.
  * [29] Z.-P. Jiang, T. Bian, and W. Gao, “Learning-based control: A tutorial and some recent results,” _Foundations and Trends® in Systems and Control_ , vol. 8, no. 3, 2020.
  * [30] J. T. Bosworth, _Linearized aerodynamic and control law models of the X-29A airplane and comparison with flight data_. National Aeronautics and Space Administration, Office of Management …, 1992, vol. 4356.
  * [31] M. K. S. Faradonbeh and M. S. S. Faradonbeh, “Efficient estimation and control of unknown stochastic differential equations,” _arXiv preprint arXiv:2109.07630_ , 2021.