Finite Sample Analyses for Continuous-time Linear Systems: System Identification and Online Control
Authors: Hongyi Zhou
Jingwei Li
Jingzhao Zhang
Venue: NeurIPS 2025 poster ()
Keywords: online control
system identification
continuous-time linear system
Primary area: theory

Abstract: Real world evolves in continuous time but computations are done from finite samples. Therefore, we study algorithms using finite observations in continuous-time linear dynamical systems. We first study the system identification problem, and propose a first non-asymptotic error analysis with finite observations. Our algorithm identifies system parameters without needing integrated observations over certain time intervals, making it more practical for real-world applications. Further we propose a lower bound result that shows our estimator is provably optimal up to constant factors. Moreover, we apply the above algorithm to online control regret analysis for continuous-time linear system. Our system identification method allows us \textcolor{blue}{to} explore more efficiently, enabling the swift detection of ineffective policies. We achieve a regret of $\mathcal{O}(\sqrt{T})$ over a single $T$-time horizon in a controllable system, requiring only $\mathcal{O}(T)$ observations of the system.

Finite Sample Analyses for Continuous-time Linear Systems: System Identification and Online Control
Hongyi Zhou"
Jingwei Li' III, Tsinghua University
IIIS, Tsinghua University
Shanghai Qizhi Institute
Shanghai Qizhi Institute
zhouhong240mails tsinghua.edie edu.
1jw220mails tsinghua. edu. cn
Jingzhao Zhang
IIS. Tsinghua University
Shanghai Qi zhi Institute
j jingzhaoz@mail tsinghua. edu. cn
Abstract
Real world evolves in continuous time but computations are done from finite samples. Therefore, we study algorithms using finite observations in continuous- time linear dynamical systems. We first study the system identification problem, and propose a first non-asymptotic error analysis with finite observations. Our algorithm identifies system parameters without needing integrated observations over certain time intervals, making it more practical for real-world applications. Further we propose a lower bound result that shows our estimator is provably optimal up to constant factors. Moreover, we apply the above algorithm online control regret analysis for continuous-time linear system. Our system identification method allows us to explore more efficiently, enabling the swift detection of ineffective policies. We achieve a regret of ((VT) over single T-iime horizon in a controllable system, requiring only O(T) observations of the system.
Introduction
Finding optimal control policies requires accurately modelling the system 18]. However, real- world environments often involve unknown system parameters. In such cases. estimating unknown parameters from exploration becomes essential to identify the unseen dynamics. This process is recognized as system identification, fundamental tool employed in various research fields, including
time-series analysis (20). control theory (2I. robotics
[6]]. and reinforcement learning (28)
The identification of linear systems has long been studied because linear systems, fundamental systems in both theoretical frameworks and practical applications, has wide applications ranging from natural physical processes roboties. Most classical results provide only asymptotic
of the most
convergence guarantees for parameter estimation 3 24 5)
On the other hand, with the rapid increase in data scale. there is growing concern for statistical efficiency. Consequently, the non-asymptotic convergence of discrete-time linear system identifi- cation has emerged as another pivotal topic in this field. Investigations into this matter delve into understanding how estimation confidence is influenced by the sample complexity of trajectories ( Furthermore, many of these studies operate
the running time single trajectory [33 29
Equual Contribution "oorresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

under the common assumption of stochastic noise, there has been a parallel exploration into the identification of discrete-time linear dynamical systems with diverse setups. This includes scenarios where perturbations are adversarial [13] or when only black-box access is available 7
In contrast to studies in discrete time system, there have been relatively fewer non-asymptotic results addressing parameter identification for continuons-ting systems. Two problems exist for continuous time analysis. First, nonasymptotic analysis in continuous system without noise can be degenerate, as a short time interval can contain infinite pieces of information. Second, if we consider the non- degenerate case when finite noisy observations are available. then the analyses require concentration results that become known only as in [33 9 29]. Recently [4] provides novel analyses for estimating system parameters, which relies on continuous data collection and interaction with the environment. Motivated by progress in these works, our first goal is to answer the question below:
Can we design continuous-tinn time stochastic system identification algorithm that provides nonasymptotic error bounds with only a finite number of samples?
We will introduce our system identification algorithms tailored to meet the above requirements. As expected, we discretize time into small intervals, thereby reducing the problem to discrete system. The interesting part involves ensuring that the discretization remains bijective and that the inversion is unbiased. Our algorithm identifies the continuous system using only finite number of samples from the discrete system. We further propose a information theoretic lower bound that shows our algorithm is optimal.
As an application of our system identification methods, we study an online continuous-tine linear control problem as introduced in (0). In this context, exploration is essential for estimating unknown parameters, with the goal of identifying a more optimal control policy that narrows the performance gap. The primary challenge involves finding the right balance between exploration and exploitation. Leveraging our identification method for more efficient parameter estimation allows us to effectively manage exploration and exploitation, achieving an expected regret ((vT) over a single trajectory with only (I') samples in time horizon T. This surpasses the previously best known result of O(VT lTg) which needs continuous data collection from the system.
We summarize our contributions below.
1. When the system be stabilized by known controller, we establish algorithm with (TT) samples that achieves estimation error O(V1/T) on single trajectory with running time T, which is shown in Theorem 2 We also provide Theorem 4 which shows that the estimation error of our system identification method is optimal up constant factors.
2. When stable controller is not available, obtain estimators with error OVVI/N), is shown in Theorem
N independent short trajectories to
3. We apply our system identification method an online continuous linear control algorithm, which only requires O(T) samples and achieves ((VT) regret single trajectory with lasting time T (Theorem 6). improving upon the best known result O Oogglog(T) in 30
2 Related Works
Control of both discrete and continuous linear dynamical systems have been extensively studied in various settings, such as linear quadratic optimal control [27]. H, stochastic control [10]. H. robust control [34] [7 and system identification [2T 24]. Below we introduce some of the important results on both system identification and optimal control for linear dynamical systems.
System Identification Earlier literature focused primarily on the asymptotic convergence of system identification 66 (2). Recently, there has been resurgence of interest in non-as -smmmtottoiic system identification for discrete-time systems. [9] studied the sample complexity of multiple trajectories, with O (V//N) estimation error on N independent trajectories. For systems with dynamics J++11 = Ax; + wo (without controllers), 33 established an analysis for O(vI/T) estimation error single stable trajectory with running time T, while [33 and 29 extended to more general discrete-time systems.

---

Non- as--mmtmmtticc analyses for continuous-time time linear system are less studied. Recently, 4 examined continuous- time linear quadratic control systems with standard brown noise and unknown system dynamics. Our algorithm is specifically designed for finite observations, achieving error rate that cannot be attained through the direct discretization of integrals as done
Regret Analysis of Online Control In online control, if the system's parameters are known, achieving the optimal control policy in this setup can be straightforward [34 35). However, when the system parameters are unknown, identifying the system incurs regret. M achieved an O (vTT) regret for discrete-time online linear control, which has been proven optimal in I under that setting [2]. Subsequent works have extended this setup, focusing on worst-case analysis with adversarial noise and cost, including [26] 8 22
32 2]
These analyses are limited discrete systems. For
continuous- time systems, works of [3 30 23 established algorithms for online continuous control
that achieves O (VTlog(T)) regret.
3
Problem Setups and Notations
In this section, we introduce the background and notation for linear dynamical systems and online control.
3.1 Linear Dynamical Systems
We first introduce discrete-time linear dynamical systems as follows: Let 2h E Rd represent the state of the system time k. and let ug RR denote the action at time k. Then, for some linear time-invariant dynamics characterized by A E Rdxd and B E pdxp, the transition of the system to the next state can be represented as:
Tk+1 Ar Bug
Wks
where w/ E Rdd are i.i.d. Gaussian random vectors with zero means and certain covariance.
Similarly, continuous linear dynamical system with stochastic disturbance at time f is defined by differential equation, instead of recurrence relation:
dX, AX,dt + BU,dt + dW..
In this context, system, distinguishing them from 2n and u, in discrete-time systems. W, denotes the stochastic noise, which is modeled by standard Brownian motion.
X, and U, to represent the state and action in the continuous time linear
For a continuous control problem, an important question a linear dynamical system is whether such system can be stably controlled. Below define the concepts of stable dynamics and stabilizers.
Definition 1. For any square matrix A, define ((AA) = max, {3{(A)]),, E X(A)), where R(AA represents the real part of complex number X, X(A) the set of all eigenvalues of A.
Definition 2. A matrix
gaxd is stable (44) < 0. A control matrix E ixx is said to be a stabilizer for system (A, B) if A BK is stable.
Under the above definition, a stable dynamic guarantees that the state can automatically go to the origin when external forces are added, while applying stabilizer as the dynamic for controller will also ensure that the state does not diverge.
3.2
Continuous-time LQR Problems and Optimal Control
For continuous-tin linear systems disturbed by stochastic noise, introduced in 3.1 we denote the strategy of applying control to such systems through a specific causal policy, f X + U. This policy maps states X control inputs U, where the policy at time can only depend on the states and actions prior to t.
The optimal controls in linear systems often linear
34
35
which takes the following form
U, K,X,,
3

---

where K2 E Rexd represents the linear parameterization at time under some policy f(X) KX. Additionally, we define the cost function of applying the action U, X,X; with linear quadratic regulator (IQQR) control. Given predefined symmetric positive definite matrices Q E Rdxd and R E RRxx, along with the initial state Xo. the cost during & [0, 7] denoted by Jr, as represented in the following equation:
J-e (xxXX UU dt
JT B
Here the expectation is taken over the randomness of Xt.
Among all the polices there exists an optimal mapping f. which minimizes Jr. When the system is dominated by dynamics (A, B), with the state transits according to (2), such optimal Kg can be computed via the Lyapunov matrix Pe that solves the Ricatti differential equation [35]
d - P: PR
A - P. Q, P-
di
Then, under fo the action dynamic is set to be K, = - PT
When T + too, the starting dynamic Po converges to some special dynamic P. satisfying
BR P.
P.
Q 0
(5)
and the optimal control policy for infinite time horizon is by setting K, - R--1 B and apply the action by U, K,X,
Online Control Problems. Online learning aims to find strategy to output sequence of controls {U,} that minimizes the cost Jr without knowing the system parameters A, B. In this scenario, the algorithms explore to obtain valuable information, such as estimators (Å, B) for (A, B), while simultaneously exploit gathered information avoid large instantaneous cost.
To quantify the progress an online learning problem with horizon T, one quantity of interest is the regret Rr. which quantifies the performance gap between the control taken U, = f(X,) and a baseline optimal policy which takes U, K, X = R- R P. X,, where K, defined in (5). Formally, by denoting Jr be the expected cost under f. and J7. be the expected cost under the baseline optimal policy, the regret Hy is represented as:
R Jr J7.
(6)
Other Notations Denote the d-dimensional unit sphere S {or R ||0|| = 1}, where || 11122 the L2 norm. For any matrix Rmxn denote ||A|| be the spectral norm A, or equivalently,
|||||
sup --
||Au||2
sup uES"-1,DES""
w Av.
4 The Proposed System Identification Method
In this section we propose our system identification method. Before presenting our method, we first introduce the formal definition of system identification and the finite observation setting.
4.1 System Identification and Finite Observation
We start with the definition of system identification.
Definition 3 (System Identification). The system identification task aims recover the true system dynamics matrices A and B by observing the system's 's response over time. Specifically, one selects a time horizon T and sequence of actions U, observes the resulting states X, and computes estimates À and B of the true dynamics. The goal is design an effective algorithm that achieves the following non-asymptotic estimation bound:
| A/. 1 B| < fTT),
for some function f depending on particular, as T - co, we expect the estimation error [(T) to converge to zero.

---

Next, we introduce the finite observation assumption. Under this setting, the number of observed states N grows most linearly with the trajectory running time T. In other words, for any trajectory of length T, we can only access a finite set of states (X1, X2,..., Xx) to identify the system, where N O(T) and does not exhibit superlinear growth.
To analyze the continuous- tim system, we need to discretize it. Prior works 4 31 30 commonly approximate the dynamies using
Xe+h (I hA) + hBU, + (We+n- - W.).
However, this approximation introduces a discretization error between the approximated and true dynamics. The error term, characterized by (chA l)/h A, is of order O(h). Consequently, the sampling interval à must be chosen as O(1/VT) to ensure that discretization error does not dominate. This leads super-linear sampling complexity of m T/h h 12(79/2), which violates the finite observation assumption and significantly increases computational demands.
In contrast, our method overcomes this limitation by directly estimating the matrix exponential eA in Lemmal) ! and subsequently recovering (4, B) from this estimate. As a result, our approach avoids discretization error entirely, allowing the sampling interval to depend solely system parameters rather than the total sampling time T. This innovation reduces the sampling complexity to grow linearly with T, offering significant computational advantages.
4.2 Algorithm Design
Then we introduce our algorithm. We choose a small sampling time interval across a single trajectory of time length T. We then divide the time into small intervals and consider the state evolution within each interval. We get the following Lemma:
Lemma 1. In the time interval [t, +
hl. the following transition function holds:
I" h
X1th = e Ab X, Ahx,
A(h-a) x) BUc+s + We
==
ds. The formal proof of this Here, w2 is Gaussian noise (0, Σ) with covariance E -S A "d Lemma is deferred to the Appendix A.2
This transition equation connects continuous-tine time and discrete- time systems. In method, the whole trajectory is partitioned into intervals with proper determined length h. During time t E [kch, (k: 1)h], we observe state 24 at time kh, and fix the action U, = uı in this interval. Denoting A' Ah and B' [ f ()
B, then the set of observations {æ.// = 0, 1, 2.....
and actions {ux jk = 0, 1, follow the standard discrete-time linear dynamical system:
F++1 A x
B ug
Wi-
Then we can apply the system identification method of discrete-time system 33 9 However, different from classical discrete-time systems, continuous-time systems present new challenges. The crucial one is that knowing Ah is not sufficient to determine A, because the matrix exponential function fXX = x is not one-to-one. This means we might obtain an incorrect estimator Á by solving Åh M, where M is the estimate of Ah, From the above analysis, we introduce our
assumptions of the algorithm.
Assumption (Assumptions for Algorithm T and Theorem 2. We assume
1. The linear dynamic A is stable, with a(A) < 0 (see Definition I. This is equivalent to assuming the existence of a stable controller K and then set A + A BK.
2. ||a|| < KA. |B|| < KB for some known K,, Kg (KA, KB need not be closed to ||A|], [B]).
3. The sample interval h is chosen to
Ibma
With the above assumptions, we design our algorithm as described in Algorithm I In the k-th interval of length h, the state Ią is observed at the beginning, and randomly selected action uq is applied
5

---

Algorithm System identification algorithm for stable system
Input: Running time T, sample interval h satisfying the condition in Assumption Define the number of samples To [T/b].
for k = ..... To : do
Sample the action uAk iid. Use the action U, Observe the new state # time (k + 1)h.
(0, 1,).
during the time period i E [kh, (k 1)h].
end for
Compute system estimates (A, B) via (
uniformly throughout the interval. The state-action pair Ik, up is then used to estimate the discretized dynamics via:
To
To Σ
To
To-1
T
(A)
TATE
,
uguig
Σ k=0
ue
[k+1
Arkk
k=
k=0
The continuous-time dynamics (A, B) are then recovered from (Ā, B). Under the condition |||]/ <<
1, we employ Taylor expansion to compute Åh = log(A), approximating Ah. The estimators (Á, B) given by:
1 k
(A- (A-1)*, = [r cdu
À
B.
(8)
A21
We now establish the efficiency of our algorithm and derive the main theorem as follows.
Theorem (Upper bound). Algorithm 1 there exists constant e poly (la(A))- NA, KB) such that, 40 < < 1 2. when T 2 C ool + log" 1/6), with probability at least - 6, we have:
log(1/6)
| - All, B B S CV
T
We defer the proof of the theorem Appendix A.4 and highlight the key idea below. The key idea of the proof is to analyze the error transformation from the discrete system to the original system. We prove Lemma 3 which shows that the errors in the discrete and original systems differ only by a constant factor. This allows us to focus solely the discrete system identification problem.
Lemma 3. In Algorithmss 1
suppose we obtain the relative error I| A'I., | B' S c for some < 15 and ||Ah|] < I5. Then, the relative error in the original system satisfies:
- A [ B
1 h
2
KB
(10)
KAA
From this lemma, it follows that if we develop a system identification algorithm for the discrete system that produces dynamics estimates Á and B with minimal error, we can obtain accurate estimates for the original system. The remaining task is to analyze the discrete system with the transition function Ik+1
Az + Bug + Wk. which has been discussed in previous works such as 33
4.3 Lower Bound
In this section, discuss the lower bound of the problem. We prove Theorem 4 and establish that this method has already attained the optimal convergence rate for parameter estimation. The theorem primarily asserts that, given single trajectory lasting for time T. any algorithm that estimates system parameters solely based on an arbitrarily large number of finite observed states cannot guarantee an estimation error of of v1/T).
Theorem 4 (Lower bound). Suppose T 1 be the running time of single trajectory of continuous- time linear differential system, represented in ② Then there exist constants C1 C2 independent

---

of d such that, for any finite set of observed points {to = 0, 11, t2...., tx = T,, and any (possibly randomized) estimator function Φ {Xtor X Xty...., N + Raxd, there exists system parameter
A, B satisfying P [ HEN) All Z VT 2 cz. Here the probability is with respect to noise.
e
In Theorem the mapping & can refer to the output of any algorithm that exclusively relies on the finite set of states Xt...... Xtx. The interesting observation is that the lower bound does nor decrease with a larger observation number N.
We defer the proof of the theorem to the Appendix A.6]and provide a proof sketch below. We consider Two sets of dynamics, (A,0) and (A, 0), where both A and A are stable, and | A
Appendix(A.6jand
2e1 Our
key observation is that for the two distributions of observed states S& = {X X Xt...., X1,} and Se {X to: Xt,, ...y )= where X corresponds to the linear dynamic A and X corresponds A, the KI. divergence between S and S increases by at most & (1++11 - [g). Here, is universal constant independent of 44 and 1-+1- Thus, regardless of how the observation times are selected, the KL divergence between the observed states remains bounded.
Remark (The Discussion of Lower Bound), The construction in Theorem Saaremm@invlle invollvss matrices A and Á that depend T, specifically with || All
201 One might be concerned that such T deeeendennt construction lacks interpretabilitt since the true system parameters are independent of T. However, as shown in Appendix A.6 the matrices are taken as A = - La and A = la U, where U has only one nonzero entry at position (1, equal to 5vT For these matrices, the key constants in the upper bound remain uniformly bounded: the inverse stability margin |a(A]] equals for IIa and is at most
vT
S 1 for A; the condition number ((A) equals for A La and is at most
TYT 1 < 2 for A. Thus both quantities are controlled by universal constants, independent of T, 1+ 5/T ensuring that the lower and upper bounds are comparable up constant factor.
4.4 Finding an Initial Stable Controller
While previous work on continuous-timg system identification 4 30 always assumes a known stable controller, our method extends cases where stabilizer is not known in advance. For general (A, B), where a stabilizer is not predetermined, relying on a single trajectory is not feasible, as the state may diverge rapidly before obtaining stable controller is obtained. Instead, we first find stable controller K using multiple short-interval trajectories and then employ it in Algorithm 3 for online control. Below, we list the assumptions on system parameters.
Assumption 2 (Assumptions for Algorithm 2 and Theorem 5).
We assume
1. The constants K,, KB, h follow the same assumptions as in
2. The running time T for each trajectory is small, say, 7 = Toh where To E and To S 10.
Then, we employ multiple short trajectories to identify A and B outlined in Algorithm 2 Similar to what is demonstrated in (9. this procedure results in (HH11/2 estimation error the trajectory number H.
Theorem 5. In Algorithm 2 there exists a constant E poly(KA, KB) such that w.p. at least 1 the estimation error of A, B) from H trajectories satisfies:
log( (1/8)
Á - All. B|| < CV
H
The proof details are shown in the Appendix A.5
5 A Continuous Online Control Algorithm with Improved Regret
In this section, we apply our system identification method to a continuous LQR online control algorithm. Recall the setup introduced in Section 3.2 where we want to minimize the regret Rt defined in 6). We will show in this section that with (TT) samples, our algorithm achieves O(VT)
7

---

Algorithm 2 Multi-trajectory system identification algorithm
Input: T. To. h as in Assumption 2 number of trajectories H. for 1 1. 1...., H do for k = , To
do Sample the action u iid. N (0, Ip), use the action U, = ude during E [kh, (k + 1)h) Observe the new state 2241 at time (k + 1)h. end for end for
Compute (A, B) by (A, E arg mi,() 1/2 Et= | A Buly - =112
Compute A, as in (8. let (Á, B) = (A, B) be estimates for system dynamics (A, B).
expected regret on a single trajectory, thereby improving upon the previous O (VTlog(T)) result.
We list the assumption for the online LQR problems below.
Assumption 3 (Assumptions for Algorithm 3 and Theorem
We assume that:
1. A stabilizer K for (A, B) (see Definition 2 with (AA + BK) < 0 is known in advance.
2. Sample distance h satisfies h = T5x where x 2 || + BII| K 2 || BK] is known.
3. Denote P. be the solution 55) and K, - T P. be the bascline control dynamic.
4. Q, are positive-definit symmetric matrices with bounded spectral norms and for some > 0, μT N Q, I R.
||Q]I, S M
5.1 An ((VT) Regret Algorithm for Continuous Online Control
Our online continuous control algorithm is outlined in Algorithm and provide detailed description below. Algorithm iis divided into two phases, exploration and exploitation. For the first exploration phase, previously known stabilizer K is applied to prevent the state from diverging. During the k-th interval, by setting U. = KX2, + ug. the state X, transits according to
dX,- = (A+ BK)X,dl + Bugdl + dW..
Since A + BK is stable, through replacing A in Theorem 2 by A + BK in Algorithm 3. we can obtain set of estimators (A, B) for (A, B) with small error. This further allows us to accurately estimate (A, B), thereby controller K -R- ----((()) ( P closed to K, is obtained.
During exploitation phase, the near-optimal controller deployed minimize the cost, resulting in a regret of O ((VT) (see Theorem 6). However, as we lack direct feedback on whether K is stabilizer, we need to detect its stability. Our approach involves replacing it with the known stabilizer K whenever the state deviates too far. Then we introduce the theorem of the regret analysis:
Theorem 6. Let JT be the expected LQR cost introduced in ( that takes the action U, as in Algorithm 3. Then.for some constant C' E poly (R, M, 1, (A + BK) [a(A + BK.) the regret satisfies:
= J
Proof Sketch of Theoremip We analyze the two phases of our algorithm. During the exploration phase, the stabilizing controller K effectively bounds the trajectory's 's radius, ensuring the average cost per unit time within (()), resulting in total exploration cost of CVT. In the subsequent exploitation phase, we analyze two scenarios separately. The first scenario occurs when the estimators (Á, B) have large errors or when |Xe]l2 2 1/5 for some f. E [VT,7] T). This situation is rare and contributes limited expected cost that can be bounded by a constant. The second scenario occurs when (A, B) are accurately estimated, and the control U, = (B) is applied throughout the exploitation phase. In this case, the trajectory's performance is straightforward to analyze, and the expected cost is bounded by ((VT) + J7.

---

Algorithm 3 Continuous online control algorithm
Input: K, which follows Assumption 3 running time T
for k 0, -,....: ( [ do
(0, 1)). For f E [kh, (A: + 1)h], set U, = KX, + up. Observe the new state 26+1 time (k + 1)h. end for
Sample the action uk
Lid.
Do system identification and estimate dynamics:
Compute (Ā, B) according to 7 by using {Zg, wx..
Compute A, B by (8) with A, B, and estimators (A, B) by À -= A- BK, = B. If Å is stable, compute P by (5) with estimated A, B, and set K = - (B) If Á is not stable P computed above satisfies || Tà, then set K K. Perform exploitation:
For E [VT, 7). set U2- = K
Detect bad policy and prevent the trajectory from diverging:
If for some to vT, [ 2 TT, then set U. K XX, for / (lo, 7).
By summing the expected costs, the total exploration cost bounded by O(VT), and the exploitation cost is bounded by J7- + ((VT). By the definition of regret, Rr = Jr Jj. the total regret is (VVT), leading to the result of Theorem
Our result is closely related to the result in 100 along with its similar version 12 They achieve
O(VT log(Z)) regret. However, they further assumes known stabilization set for obtaining stable controller, which is stronger compared with ours. Such difference exists because our approach detects divergence and avoids sticking to a controller which is not stable. Morever, in (30], the exploration and exploitation is simultaneous, where random matrix is added to the near-optimal controller so that both A and B can be identified. This causes extra log(T) factor to the regret. In contrast, our algorithm follows an explore-ther sesorr-then-ccoee then-commit structure, which enabled by the efficient system identification results presented previously. Finally, additionally considered the setup of finite observation, which is not discussed in [30
5.2 Experiments
In this section, conduct simulation experiments for the baseline algorithm and our proposed algorithm. The baseline algorithm follows the work of [30]. We set d = p = 3 for simplicity. Each element of A is sampled uniformly from [-1, 1). making A unstable with high probability. The
matrix B, Q, R are set as the identity matrix 73. The sampling interval is set to 30
First, we run Algorithm| D for system identification. We plot the expected Frobenius norms of the error matrices || A); and || B The results demonstrate that our algorithm can identify A and B within sufficient rumning time or number of trajectories.
Next. we compare Algorithm 3 with the bascline algorithm. We analyze the normalized regret R(T)/T1/2 for different E [600, 10000] and plot the results in Figure The results show that our online control algorithm with system identification achieves constant normalized regret (i.c., O(VT) regret) and outperforms the baseline algorithm when T is sufficiently large.
6 Conclusions, Limitations and Future Directions
In this work, we establish novel system identification method for continuous- linear dynamical systems. This method only uses finite number of observations and can be applied to an algorithm for online LQR continuous control which achieves O(vT) regret single trajectory. Compared with existed works, our work not only eases the requirement for data collection and computation, but achieves fast convergence rate in identifying the unknown dynamics well.

---

Estimation Error
40
Estimation Error
Estmation Error
Normalized Regret
30
20
10
Our Algorithm Baseline Algorithm
Running Time
Running
Figure The empirical validation of our algorithm. Left: Identification of system dynamies using a single trajectory. Right: The normalized regret R of the baseline algorithm and our algorithu. The results show that algorithm achieves small identification and is more efficient than the baseline algorithm.
Although our method achieves near-optimal results in system identification and LQR online control for continuous systems with stochastic noise, many questions remain unsolved. First, it is unclear whether our system identification approach can be extended more challenging setups, such as deterministic or adversarial noise. Additionally, many practical models are non-linear, raising the question of under what conditions discretization methods are effective. We believe these questions are crucial for real-world applications.
References
[1] Yasin Abbasi-Yadkori Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages JMLR Workshop and Conference Proceedings, 2011.
1-26.
[2] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. International Conference on Machine Learning, pages 11-119. PMLR, 2019.
[3] Karl Johan Áström and Peter Eykhoff. System identification-a survey, Automatica, 7(2):123- 162, 1971.
[4] Matteo Basei, Xin Guo, Anran Hu, and Yufei Zhang. Logarithmic regret for episodic continuous- time linear-quadratic reinforcement learning over finite-time horizon, 2022.
[5] Marco C Campi and PR Kumar. Adaptive linear quadratic gaussian control: the cost-biased approach revisited. SIAM Journal on Control and Optimization, 36(6):1890-190) 1998.
[6] Marco C Campi and PR Kumar. Adaptive linear quadratic gaussian control: the cost-biased approach revisited. SIAM Journal on Control and Optimization, 1890) 1998.
[7] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference on Learning Theory, pages 1114-1143. PMLR, 2021.
[8] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only /T regret. In International Conference on Machine Learning, pages 1309, PMLR, 2019.
[9] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator, 2018
[10] Vasile Dragan, Toader Morozan, and Adrian Stoica. H2 optimal control for linear stochastic systems. Automatica, 40(7): 100-1113,, 2004.
[11] Durrett. Probability: Theory and examples, cambridge series statistical and probabilistic mathematics, 2010.
10

---

[12] Mohamad Kazem Shirani Faradonbeh. Regret analysis of certainty equivalence policies in continuous-tim enear-quadratic systems. In 2022 26th International Conference on System Theory, Control and Computing (ICSTCC), pages 368 373. IEEE, 2022.
[13] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identification in unstable linear systems. Automatica, 96:342-355 353, 2018.
[14] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[15] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorithmic Learning Theory, pages 408-421. PMLR, 2020.
[16] Rolf Johansson, Anders Robertsson, Klas Nilsson, and Michel Verhaegen. State-space system identification of robot manipulator dynamics. Mechatronics, 10(3):403-41 418, 2000.
[17] IS Khalil, JC Doyle, and K Glover. Robust and optimal control. Prentice hall, 1996.
[18] Donald E Kirk. Optimal control theory: introduction. Courier Corporation, 2004.
[19] David Kleinman. On an iterative technique for riccati equation computations. IEEE Transactions on Automatic Control, (3(1):114-115, 1968.
[20] Michael Korenberg. robust orthogonal algorithm for system identification and time-series analysis. Biological cybernetics, 60(4):267-776, 1989.
[21] PR Kumar. Optimal adaptive control of linear-quadratic -uaaraaati-gauuusiinnn systems. SIAM Journal Control and Optimization, 21(2):163-178 1983.
[22] Sahin Lale, Kamyar Arizzadenesheli, Babak Hassibi, and Anima Anandkumar. Explore more and improve regret in linear quadratic regulators. arXiv, 2020.
[23] Jingwei Li, Jing Dong, Can Chang, Baoxiang Wang, and Jingzhao Zhang. Online control with adversarial disturbance for continuous-time linear systems. Advances in Neural Information Processing Systems, 37:48130-481 2024.
[24] Lennart Ljung. System identification. In Signal analysis and prediction, pages 163-173. Springer, 1998.
[25] Lennart Ljung. System identification. Springer, 1998.
[26] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
[27] Volker Ludwig Mehrmann. The autonomous linear quadratic control problem: theory and numerical solution. Springer, 1991.
[28] Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based rein- forcement learning, arXiv preprint 1203:1000.000 2012.
[29] Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, pages 5610-5618. PMLR, 2019.
[30] Mohamad Kazem Shirani Faradonbeh and Mohamad Sadegh Shirani Faradonbeh. Online reinforcement learning stochastic continuous-time systems. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings Thirty Sixth Conference Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 612-656. PMLR, 12-15 Jul 2023.
[31] Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh, and Mohsen Bayati. Thompson sampling efficiently learns to control diffusion processes. Advances in Neural Information Processing Systems, 35:3871-3884, 2022.
[32] Max Simchowitz and Dylan J. Foster. Naive exploration is optimal for online Iqr, 2023.
[33] Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification, 2018.
11

---

[34] Robert F Stengel. Optimal control and estimation. Courier Corporation, 1994.
[35] Jiongmin Yong and Xun Yu Zhou. Stochastic controls: Hamiltonian systems and HJB equations. volume 43. Springer Science & Business Media, 1999.
12

---

A System Identification for Continuous-time Linear System
In this section, we analysis our system identification method in Algorithm I and Algorithm 2 As preparation, we establish some properties of matrix exponentials and their inverses.
A.1 Matrix Exponential
For a matrix exponential eAt, where the largest real component of A's eigenvalues is denoted by (AA), the spectral norm of eAt can be well-bounded [14), as demonstrated in Lemmal 7
Lemma 7. Suppose an n. n matrix A satisfies that > a(A) max max(3((A.) (R((2,)Ae ((A}3- Let
Q# AQ diag(A:) + N be the Schur decomposition of A, and ler Ms(() 2
I Then for
t > 0, we have:
||E4||| S (((A)MM))))
(11)
|e(A+E) JelatBy- EAIl
t (l1 (M) (MM))))1
(12)
|ede1l
In special case where a(A) S 0, since (t) 2 1 for all t, we obtain |e S c((rr
We also show some properties of matrix inverse in the following Lemma 8 Lemma 8 (Matrix inverse). For any A _axd and t such that Ab]] S To we have the following estimation of At:
| - Tall S ellAell 1,
and if we denote A, = ct, then A also satisfies that
1-1)
A
(A1 - Ia)*
k
k21
Proof. We expand et by
(Ar)+
E20
which follows that
1e Lall =
(At)*
|tt 1h = elAelll -15
121
Since ||A, Tall < 1, the progression A2
Ex>1
(-1)++1
(A1 Ia)* converges, and thus e
AM, Furthermore, can be computed that
(Ai Ia)
| <
8
121
A21
Now we show that A = A. We have already known that ||At|| and ||A2t|| are small. We also note that the function f X + x (||XII s }) constitutes one-to-one mapping. This assertion is supported by the observation that for any X1, X2 such that || ||, + X2ll I $.4. we have |aal < 1. implying that
Xitxx 10xx2__00 -ex1 -x2|
Σ
(X1
+
X²)x
X
(13)
K!
122
2
X22
(14)
k! -
k22
X2ll
(15)
2
13

---

Then
[x2ll, which means f is one-to-one, and thereby leading that A2 A.
A.2 Proof of Lemma
Lemma 1. In the time interval [t, + hb, the following transition function holds:
/ h
X4th = Ah X, +
cA(h-a) 6) BUt+, + wt
==
Proof. Using Newton-Leibniz formula, we have
Xith = X1 S AXe+u + BUtt + dt
dWe+th des
dWiy have:
Let We44, BU--,
de
X1th = X,+ (/' AXite + We+e,
=(1 (L++Ah)X++ ("' [weten dt A Jn
l' (X1t41-A0 -x)ddt
-I+ Ah) + ('¹ witen dt + A J
1// AX + dete,ddde
+1+ Ah + - A / Ah
(1 A(h (1)=tt)) di + A2 S/² 1-" (t)
(Xe+12 Xt)dt
where the last equality use the Fubini theorem to change the integral order of and ty to calculate the second term.
Suppose we already have the following equality for integer m (The case 2 has been checked above):
(hA)*
+x++ + / T+
((h - A))
X1th = (T
|weten dha
h!
k!
A=1
A
(Xetem Xt) dtt....g..........
JOSt Sh..h
Then, replace Xettm
X2 by [ [AX, A(Xettm4s Xi) + Vemtaldemen we get:
{
am
(Xittm - Xi)dtydtz...de
Ustmm..sh
= =m++xx X,
dt ddd2...dem + Am
Jostmtis...s Whitm dt dt
JostmtiS...
m++
(Xetem4s -x)ddtydte..de diy dtd.
JStmi1s...sh
Using the property that
Jucn Sesss
hm dxy dx
Sam
m!
14

---

We finally get
n
(Xitem - (x))dtdtt...d dt2...d.m
OStm Stm.m.tmmss5551 Stish
hm+1
1m X1 + A 1 nt (h tm+1)
We+em- dtm+
(m + 1)!
ml!
A
(Xe+em+1 i.)dtt
J0Stmi15...5
In the calculation of the second term we use the Fubini theorem to change the integral order of 4m+1 and (1, 12...mm So the induction hypothesis is true. For any positive integer m, we have the following equality:
(hA))*
(hh - +*)4)*
X4th (I+
)x,
+
[1+
k!!
k!
k=1
=1=0
1=1
+ n
(Xetem - Xe) de..ddde...
For the time interval / E it, hl, by the continuity X; we know that X, uniformly bounded by some constant C. Therefore we have the convergence of the third term in the RHS:
lim ||Amh {
(0(aah)m 0.
Justm...hh (Xe+em (d)dl,dl2...dd
lim
m--000
m!
Therefore, we finally get:
Xeth A/h X, chx 1 ellh-s)
(16)
Now, we use W+++ BU++s + dWe+e
we get:
de
1th A(h-e) BU++ 1 calh-o)
Xith A
Xx
(17)
50
("a ((h- BU++s B) we:
= Ab Xx +
(18)
where is Gaussian noise NO, Σ) with covariance E 1o cAs dds.
A.3 Proof of Lemma 3
We restate Lemma 3 and provide the proof here.
Lemma 3 Algorithm suppose we have obtained the relative error || - A' |
B'I Se
for some
and AAh
Is then we have the following relative enror of the primal system:
C
Á All. 18 - B| S
h e,
(19)
where C' is a constant independent of h.
Proof. Firstly, according to Lemma
8 the estimated is not too far away from Ia. as we have:
| La| < an
1 + ||e Ab - Iall s e ell AljA 15 7
15

---

Then, from (8) we can bound the matrix norm
by
1)*-1
|
(Ā 1)*
A21
Now, let's denote A1 = Ah and Ag = Åh- - A1. satisfying the relations A' e and Ā = eAitAs
It is given that ||| S T3 and || - | + ||Ab|| - 1 so by (3), we obtain that || - Alhh-
|2ll s 2 A A' ||. which follows that || A = I All 5 k.c
Next, will upper bound the estimation enror of B. Let An Se At and An 11= ede satisfying
1
||
hT
(e
I)dt
11dr - -1| -rl
(cllalk -1)dt S h,
1=0
1=
-1=
20
||A
Anll =
edt
Exict dt
S |-m
cetr -ett dt S
3 h
3 1| All S 1 he.
1=
2 rc
This follows that
| 1
An
A
20
+
h
h
h
19h"
k20
(1(Aa)) - 1
|4,''l || (An (An - An)
1 S $14
1
(An
An)
S
he
Since B and its estimator ß satisfy that
== (An) B3 B = (An)-
we can upper bound the estimation error | 13| by
[B'| |
|
B - B
B s [| -7 B' + [1A,)) -1 B B'
S
+ $ (2)
+ 2 )
h
h
where the last inequality is because
B' < || B|| S BII
Since B||
< 2kg S 1
2nB I6NA
<
ER we obtain Lemma 3 Kx
A.4 Proof of Theorem
In this section, we derive the proof of Theorem 2 We upper bound the estimation errors of inter- mediate dynamics (A', B ). obtained as in 77). We first prove Lemma below, providing system identification results on single trajectory with stable controller.
Lemma 9. Consider the trajectory Ik+1 Ar + Bu, + we with A E Raxd, ||||| < 1, B E Rdxp; uk ~ (0, Ip) and wi NN Σ) are i..dd. random variables. Suppose we compute (Å, B) by
To
To
To
To-1
(Ā)T
Σ A=
T &
Σ k=O
Inu T ++1
(B)
=
u
T
Σ k=
uA (MR+1 - Aua) -Aun)
(20)
k=
Then there exists a constant C (depending only on A, B, d, p and Σ)) such that for z C (I1.ooll3 [||Xoll2+1og" +lo2( w.p. at least 1 8:
Á AII, 1 BlI S CC ())(
(21)
16

---

We first provide Lemma
10 which is used as the base of Lemma 9
Lemma 10. Consider A E Raxd such that p(A) < 1 and the system X&+1 AXx + wi. with
wk No. Σ) be ii.dd random variables. Suppose we estimate A as in (7). Then there exists
constant C depending on A, E and d such that for T C(I + log(1/0)), w.p, at least 1 6. we have:
A All S &V log(1/8)
The work of 33 has discussed such systems in their Theorem 2.4, and we list it below:
Theorem 11. Fix e, E (0, T N and 0 < T < r. Then if (X1, Yo)e21 E (RR x )T is random sequence such that (a) Y, A, + To where Th Fe -es--suu-assss and mean zero, (b) X1,... XT satisfies the (R;, sb. p)- -mmllll ball condition, and (c) such that TP E X,X! 1 TT s
Then if
10k p²
T Z
(log(1/6) + 2d log(10/p) log det((
we have
10 + log det (TTT)) + log()) ) d log
90g
P
A.ll
p T min ab)
S 36.
p
Here, the (k, st. -mmlll ball condition is defined as follows. Let (Zi)e21 be an adaated random process taking values in TR. We say (Ze)121 satisfies the (ks U, p) b)-block martingale small-ball (BMSB) condition if. for any j 2 O, one has 1o2 Ei=zP((Iz5+) 2 v)J,) ) 2 p almost surely. Given a process (Xt)121 taking values in RRd, we say that it satisfies the (k: T sthh PBMSSB condition for ab > 0 if. for any fixed sa- the process Z₁ == (w, Xi) satisfies (k, v TT. -BBSBB
In the work of (33), they have discussed the case when Xo = 0. and now we modify it to general starting state Xo. From we derive the estimation error of A as
AT AT
Σ X
X k41 - AA
Xx
Σ XA + ww) AT
X
Σ X
For the first term, consider any v E Sd-1, we lower bound T
IT-I Xx.TT) v. Let az = TTx
then dg = o'' A + wk. We claim that for any Z 1, P ||ax| 2 X 2 1.2 Let by =
of "e. which is independent of Xg-1- It suffices to show that for any E P E [c, 1]] 5
Since ||o||2 1 and wh (0, Ia), we have by NN 1), from which we estimate the probability as
E bba t dx <
lbb E [c 1]]
2 /2T 2
(22)
amc /2T
Based on (22 we can simply choose D.b La and p 2. then the random sequence
(X.):20 satisfies the (k, T sh: BM-BB condition. It remains to choose proper I that meets the condition (c) in Theorem 11
17

---

Since Xx = X0 + E/=1
A we have:
T --1
T-1
- wi )
Σ X
= E
A Xo + Σ
A
Xo +
EA A 200
k
Am
1=1
T
T *
A Xo X0 (A + E
A Xow? ( igh
k=
A=0 Y=0
T-1 k
+ E
A (A
+
A wo, W (AR-
k=0 t=0
k=0 x===
T-1
A Xo X (At)T
ΣV
ΣΣA k=0 1=0
A (AA--))
Le = Exz0 A ( which is bounded and C₁ be a constant such that C1 2 Σ 4
||
We then show that for T
C. (all dla + dz|lT>>l l1 /5, the condition (c) in Theorem 11
satisfied. This because E
Ei= xxxx) =t tr
E xxXT - tr(() so that
S Furthermore, a necessary condition for IT XxXX) 2 [tr((T)
E X A TT is tr k== XxXT) [TTr(T).
Now, we apply such I' to Theorem 11 It can be computed that
log det log (4d(C) X / + Il)) + dlog(1/6).
Then when T C2llXo/1 well T 2 40 (2d log (20) ddlog(Ad(( + [| 2dloo(1/8))
we have:
d d (200 d (lo((4 (|T)=l))) + 2d
J All /
S 35.
T
This implies our Lemma 10
Proof of Lemma As for the estimation error Á - All, let w/. = Bux + wy ~ N(O, Σ+ BB"), which form a sequence of i.i.d random variables. With the results in Lemma 10, there exist some constants C1, C2 such that, as long as T 2 C1 (o1xx + log(1/6)) we have:
log(1/8)
|| All s C2y
Now we upper bound the estimation error B B||. With the expression in
we obtain:
L B
Σ u
(A
A)Xx + wk
< 1
Σ
Uk X
A
k=0
For the quantities A k= uguu T and IE Uy n.wn [|. we apply Lemma 2.1. and Lemma 2.2. in the work of [9, where they present the following results.
Lemma 12. Let N > 2 log(1/5). Suppose fa E _T 99 R are independent vectors such that fa ~ (0, En) and gk ~O, 2ng) for 1 I k < N. With probability at least
Σ fagi
I <4 / 12,12/2
VN(m + n) log()))
18

---

Lemma 13. Ler X E RN have i.i.d. ( 1) entries. With probability at least 1 - 8,
A (XTX) 2 VN- vn 22
With these two lemmas, we can conclude that if 2 32 p) log(4/6), then both Amin (ux 2
T and k u = 4//211/ VT(d + p) (og((8/6)) w.p. at least
Now we concentrate on the term
E X
Since wi Bu, + we VO BB"), can
be directly computed that, w.p. at least - 8/T,
1/2 [ - 2 22||d(= 22 BB
l v /log(T/8). Then
by union bound we get P
suPosigT-1
5
2 1BTL / V Vdlog(T/0/ S 6. Furthermore,
2
when suposisT-1
2
2|| - BBT|
1/2
/dlog(T/o), must have
R-1
|xxl12 = 1 XxX0
+ Σ
1 16-1-in w/
|||4||||Xo11 + 1- |A|
E + BB 1/2 1B Vdlog(T/6).
(23)
For any E 8P-1 and v Sd-1, let x; = uFu(( sis Then, 2, follows normal
distribution 24 ~ (0, 1) and {at] a sequence of independent random variables. Furthermore, b
also independent of (Ki)osisk- On the other hand, denote yk Xfv, (3) implies that w.p. at
least 1 - 8, for all l we have 1yal ||Xoll2 + i-iAT |
BBT 1/2 (Tlog((/0) = Y. Let
Zk
Σ TH (uxX²) v. IIxlSS Σ t=
T&VK
1xxllas.
1=0
and let Fo: Fl..... FT be the filtration Xo, X1, XT, then for any a 2 0,
a
uZt Y
oryk+1 1ixx:1lss
)] <etaa abe
Fi
Ex
exp
implying that E
uZet1
S edaa1 10 ee y
So we have: E [ "d
S eda²r
By choosing
= + /V/ t. we obtain that
P Zr-1l 28 /TTogg//4 58
For Ta be a 1 w.p. at least 8
1 net of S and Tp be a t-net of SP-1, we use union bound on them and obtain that,
Zrr-1 < 2Y T log (oTgo//(,lllT///////
2Y VT|A(d log (4/5)
Where the last incquality is because
[pl
< 9" and
Tal < gd
Next we upper bound
DT ux x
For any u, E 1 and v, E S with some u E Tp and
E Ta s.t. |lu
uz
12,
1/2
us lll I
2. we have:
T
Xx )
k=
T
T-1
u
Ukg X y
+
(u. 1)
T
Uk
X
v.
+ w
uk. ux (F v.)
k=
k=
k=
T-1
T Σ
sup
T
Ug XTT )u
+ 2
" TET,,EET
km=0
k=0
19

---

This leads
Ek=o ux
< 2uuupue
u ""(Ek= --1 uxxx / Therefore, for any 8 E (0, (0. 2).
we have:
T Σ
P
2 4Y +) log(4//)]
k=0
u Σ u LIxxllerr) )o1 2 2Y /T]((d p) log(4/6))
$
sup
TT
30 k
|x Y]
$ 20
We choose constant C depending on A, B, d. p such that for all T 2 (1Ixoll2+ log (1/8)).
4Y T[4 p) + log 4/0)] S
and we further have: whenever T C (1l 12 log (l/6)))))) w.p. least 1--33 -35.
Σ ug xx
| All C22/oog(1/0))
Finally, when T 2 max (C (11 3 + (1/8)) 32 + p) log( 4/8)), we combine this upper
bound with IP Ammin(E T-1 y S ) S 6. and obtain Lemma
A.5 Proof of Theorem
Now, we aim to establish Theorem The analysis of system identification for discrete-time linear dynamical systems with multiple trajectories has been thoroughly investigated by [9]. We hereby cite their findings, denoting the relevant result as Lemmal [4
Lemma 14. Suppose we have N i.i.d. trajectories X each is defined by Xik+1yA Ax Bud + wie where To is any integer, ut ~N Ip) and w ~ N),,E are two sets i.i.d. random variables. Then, for the estimator (A, B) of
N Σ
(Å, B) arg min
|
AX
BuG,
(24)
(A,B)
2
1=1
with probability at least 1 5, we have:
log(1/8) (V
A - -1. -|] 50
N
Combining Lemma
14 with Lemma
3 we directly obtain Theorem 5
A.6 Lower Bound of System Identification with Finite Observation
We restate and provide the proof Theorem
Theorem 4
Suppose T 2 be the running time single trajectory of continuous-time linear differential system, represented as in (2). Then there exist constants c₁ C2 independent of d such that, for any finite set of observed points (lo = 0, l1, 12,,.. IN T}, and any (possibly random- ized) estimator function ò {Xtor X..r.., X(x} gdxd there exists bounded A, B satisfying
P [1x((X)))s)) All Z } 2 C2 Here the probability corresponds the dynamical system dominated by (A,
20

---

Proof. Firstly, we consider special case where d = 1, and let A = |-1] 1| and A [-1 8). We show that when 5VT for the two dynamical systems 4 dx, AX,at dW, and
Y0 dX,-- AX,dt + dWe, e. any algorithm A that outputs according only to (Xto: Xe, Xex satisfies:
max
P
||A(Xio= "......,,, All 2 10vT ,P
X All 2 10
4e
note that this special case can be easily generalized to any dimension d, since we can consider
A = l and À satisfies A1,1 A1,1 6, and for any (i, j) o (1, Ar, A... In this case the last - 1 dimension is independent of the first dimension, so it is essentially the same as the simplest onc-dimensional case.
Denote X (Xt, X ,...... Xtw) } and (X). ((X) be the probability density of tho and thg respec- tively. For these two probability densities we have:
N II
exp (- (-2r(ts - t(-1)
(Xe, - e-1-- -(tii-ha)) x )(rr)))))
((X)
2t 1(-1)
and
O(X)
1
exp (-2r(t: (t: t:-1)
(Xt: -e -1-0) X1; )2)
/ 2Tl - (4-1)
Where
T(t) = f" e 2
2 c 20) I(t) f (222-20) ds
1
1 (1 c -2422)))
==0
2
0=0
2+ 26
Denote a; V ( (Xe: (41-4-1) X(-1)
B1 ((1-b-11) (e (1:44-11 - e -1++5))( -4- --1++)(()---1))) X and v = -(t Then -(4-
In
g(X)
In())) + 2 2 + 0,) 207
1
g(X)
Next we show that In [((X) [(x))
is not large with high probability when X follows the probability den-
sity of Consider the following subsets of X: & = { x Σ In(x)) + ( 1)a s }}
E = {x EN 22 < 1 and &g = {x ΣN 32 = 1 When lies in the intersection
((())
of these three sets,
is guaranteed to be not very large. [(X)
Let be the probability with respect to density g. We will explicitly show that P[X E Ex] 2 [ 1, 3,
Lower bound P E Ed] following inequality:
Firstly, we estimate ΣN (n? 1) -In(x). We first prove the
S ?/ -1 28 min -
(25)
21

---

Let ( = 1 - 1.11. Then 7/ (1 + 8)
1-c
I-c 123.
The left hand side of this inequality because T3 2 H,, due to the reason that e 2a 2 e (2426)) for all 8 2 0 and when [(x) 2 g(z) for any x E 7 we have: Saes f(x)da 2 Szer ((z)dr. Now we consider the right hand side of the inequality.
Case 1: When 2 directly use the fact that 1 c c22226)) and obtain 7 S 8.
Case 2: When E (0, 1]. suffices to show that
(1 - - - (1 28t)(1 -2(+26)))
Let h()) = (1 + +0 - (1 - (1 + 251 - E e (2+26))), then
h(t) = 6(1 2t) e [1
+ [1+
(1 2 28t
< 6(1 2t - c 21)
$ 0.
Where for the first inequality we use the relation that e 26t < 14266"
The second inequality is
obtained by the relation that e-2 2 21.
Now bound ( 1) In(7)). We first show that
0 s 2 (1# - -1 -nn)n( s 7 - 1)3.
1
Let 7/- - and we obtain
2 (1² - 1) In(7)) = [ In(1 + x)). and the inequality is obtained
directly since have x 2 In(1 + x) 2 x 2x 1 0).
Then we can bound N i= (n 1) - In(7;) as
5
(1 1) in(7)) S
(7) 1)²
82 min (1, (ta - t+-1))²
8ttt - :1-1)
1=1
$ 8T
$ 25
Now bound Σn 1 (n2 - (a 1). Notice that this variable has zero mean, bound its variance and then apply Markov inequality to obtain a high probability bound.
At first, consider the variance of at - 1, denoted as Var(a 1). By noticing that a; ~N(00 1), we can directly calculate that
Var - 1) JUER V2m e 202 2 (2² 1)2 dx = 2.
Since all the at's are independent, we have:
22

---

N
1
Var
Σ 2 (1 1) -1)
Σ
(1
V) - 1)
N
-
(1
1)
N
S 26
min (1, 4 - 4-11²
1=1
2
$ 25
By Markov inequality, we have:
N
2
P
Σ 2 (1? 1) 11 2
Var
Σ i=1
20 1)(a -
1
/
5
Finally, for the subset El { - Im(x)) ()? - 1)a
s $1 we have:
N 1)(0) -
P Pir E1 21 -P P
Σ -
z 8
7
Lower bound P[X E Eg] Since all the ag 's are independent, and a; is independent of (31, ..., 3.. and {?1.... YN we obtain that
N
27
N
E
3n
=
Σ
h an
N
Σ
(7) 3:)2
Σ
E [6723)9]
1=1
We have shown that 73 < + 26. Then for T > 1 obtain:
we have: 75 < (1 g)² 2. Therefore,
N
27
N
E
Σ
r
as
<
E
[89]
1=1
Now we upper bound E [$?]. where Br = V r(a-- 1) (1;--)))))) -1+00
1
Firstly, we show that
1 I(t: t-11)
(e (ti-t 1) (14+6)(;- 1)) S S,t,, t.-1.
(26)
23

---

Again denote t = t, - -1. By using I, = 2/11 - e -2,,, it suffices to show that
e- -e < à 2 1( (01----1)
By multiplying e' on both sides, the inequality is equivalent to
E dt s 86 1 11(22-11 1).
This is true since e 8t 2 1 öt, and 2t 2 1 + 2t, implying that
1 e S S 8/ 5((e2-
With this result, we can upper bound 2 2 N
E [B?]] by
N
N
E
|
28 (t: (t:
1 1B x2
1=1
Finally, since X, ~N(,,(()) for all
E
[x]]
T, = 2 (1 e 22) 1.
Therefore, obtain
N
27
N
N
N
Σ
E
SA
- Σ 28 1
$ Σ
28
(ta - t4-1) = 2T82
25
iml
Again by using Markov inequality, we obtain:
2
P
2 Brl >1
25
Which follows that
23
P P & =1
- P
Σ 71 a 31|
2
25
Lower bound P| Ea]
We have shown that 72 < 2, Vi and Σ
[3? S ST. Therefore,
N
2
E
22
88 <
2
25
And we also have
N
23
P X E Eg]
1- - P
Σ
>
2
25
24

---

Now we come back to prove the theorem. With lower bounds of P[x F E & E &s). we have
-1 -1- -
&al) 2
With this bound, have:
1 (10(2)- - 10vT )
)}
+ Exxg [1 (0((X) - -A12 10VT)
Ex~g
{()B [ (161X)) All z
10VT |x]
1
+ + [
(166(X) - -Al 10VT |x
1
dx
XEEineanes
[ IxEEinEnns
min(g(X).
(X)dx
XEEEnennes
2
Where the second inequality is because (xx(X) All + ol((x) - A 2 ||A A
5VT so we
cannot have both [[x(X) - All S 1vv7 and |lx(X) - All S 10vT The third inequality is because
for any X E & & & we have
In 9(X) x(X)
1 In(%))
2 + +,,)² 2
1m(%))
+ 2 (7g 1)a?
1
+
2
33,
implying that g(X) 2 1 (X). Therefore, we have:
1 max Px-g [0(X) A N 10
1 4e3
Px [x(X) A
10vT
This means that for any algorithm, cannot achieve 10vT estimation error with success probability 1 4es for at least one the systems controlled by (A, 0) and (A, 0).
B Regret Analysis
Having demonstrated the results of system identification for continuous-time linear systems, we leverage these findings to establish upper bounds on the regret for Algorithm Flaborations on the details will be presented in the subsequent sections.
25

---

B.1 Convergence of P and the Estimation Error of K
In this section we provide the following Lemma 15 along with its proof, which shows that P| P.ll converges at the same speed as || - All + B BlI.
Lemma 15. There exist constants <o > 0 and C2 > 0 such that as long as | AlI,
B| S
for some eQ, with P obtained from ( we have:
P P.ll S C2c.
(27)
Recall that the optimal dynamic is K, - -R--RBBT with P. obtained from equation (5) Now we consider the distance between it and the sub-optimal dynamic K R- B3 p with P obtained from (5) with (A, B). Denote AA =
and AB = B B. along with || ||B||| e where E [0, co] with some determined later. We establish the proof by constructing a sequence of matrices (Px)220. and we will prove that such sequence converges to the unique symmetric solution P satisfying
=0
At first we introduce solution a particular kind of matrix equation 19
Lemma 16. Suppose A satisfies (x(A) max(R(()) X(A)) < Q is symmetric matrix. Consider such function
(28)
Then, the unique symmetric solution X of this equation can be expressed as:
X x= / A² 'e
(29)
112
Now consider the relation between P and P.. The core is iteratively constructing sequence of matrices Ps such that Po = P. and lim Ps P. Such matrices follows the relation
Pk+1 Ps AP, where APR converges rapidly. As for the starting case, consider the expansion
( + A (B) AP)
-A+
- = =(B+ (B0 AA) AP
AA) Q
+ +AP (BB
AAI
BP. P,A P [A (R- (B- AB)*) +BR P.
+ AP(B + AB)R AB.
Define
Ag = A + AA (B + AB [ AB)
Fb - P. AB R (B AB) BR AB] P.
We set AP, be solution of
A APo + APA + =
which satisfies that (see Lemma 16
AP, /
1,20 AT' Fot
JAPol < 2alAA)) Folldtt
Foll 5 -a(Ao)
|P, [[ l|ee + || 1
-2a(An)
120
26

---

This APo also satisfies
( AB+ AB) + AP) AA) -Q
- -A+
AP (B+ AB)
An important thing is to guarantee that Ao is stable, and |a (A())) can not be too closed to zero.
For any E1 E (0, 1) and C1 = |R| + 1 BR [+ ll. as long
- E1. || (A
BR P.) I C.e. Furthermore, there exists 62 > such that if || (A - R RR B P.) S E2.
then (xX) $ 20(A- R- B P. (the work of [30] shows this result). We can further let this c2
satisfies that, as long as AA|| , BI) || C2. we always have:
(A (A+ (B AB)R (B AB) + AP)) -
2 2a(A-BR
(30)
Now we additionally set E satistying S
L .C; E2 and || | S 1, then for all S E1.
2
| - aa(A - BR P.)
(1 + ||R '|)c.
|P |BR= and set some constant C3 ||- We then inductively define Pk+1 and A (k 2 1). For defined AP we set Ps P AP which satisfies
Denote P1 Po + APo. C2
2
satisfying C3 2 || || + 2/| || || R-
(R + AB) R (B+ (A+ A - PA(A+((A)) Q
= A B +
Then we denote A&- = A+ A (B AB)R BB + AB) and set APr satisfying:
AP + AP AP. (B AB)R (B AP
By the hypothesis of E2, as long as |/ P.ll S E2, we have (AA)) 2 aa(A BR- BP.... By
using
29 we obtain that AP&ll S C 113, where C4 -old BR- BTP.) STp.,Css
Cz. Now if
define
Pa+1 = Pk + & Pa+1 also satisfies:
Pa+1 (B + AB) R (B A
PA+1 (A+ AA) - - A(A)) ((4))-4 - Q
= AP AB)R AB)
Then these sequences PPk and Ps are well defined, along with the relation that PA+1 = Pa + APr. Furthermore, when Pr P. < 62, we havel AP Ca|/APP||2 Note that for the base case we have |oll < O2c.
Finally, it remains to constrain Pr P+ll. By choosing S min( 20.C, 20, E2, 1), obtain ||aPol| < Cye. We can also see that if for all 0 < k < m, 2(1 - 1----+++C Cge I e2 that | that || < 2 * Cze for any k.
< 2 C2e, then Pm - P. < C. AP | 2 Cze. So by induction see
||P
On the other hand, since A < 2 A limg-+to Ps = Pos exists, and such Poo is the unique symmetric solution of
P(B AB) R (B AB) (A
Q 0,
such that - AB)R (B AB) is stable (recall the stable margin in 30 which implies that (A+ AA) (B + AB)R R- (B + AB)T Po is stable).
So Pa is exactly P. satisfying | P < 2C2e.
Therefore, we conclude that there exists some cp > 0 and constant C, both depending on A, B, K, d,p such that for any E [0, co). P P. S C. as long as A - A|I, 1 B|| S
Then apply results for system identification to establish upper bound for || - K,ll.
27

---

Based on Lemma 15 fix constant > 0 and constant C1 2 0 so that we have ||P P.l 1
Ci (IA - All + |B Bl) whenever || All + |
B S E1
We C2 2 1 be two times the constant C in Lemma and obtain that, when log6
T
C2
and 71/2 2 C2 Xo we have:
log(1/5) 71/2
P
|
All + I
B S V
2 21-8
Then, for log(1/0) I min
T 102
Tat4
T 203
we have:
C2
10g(1/0)
P
|| Pall S 22C1C2V
21-6.
(31)
T1/2
Finally, since = - (B)T K, - R- BTP.. we have:
K, S ||-11| || B|B||||||||
|B|||| ||B|||||++|IIIPPPPPPPP P.ll]
We can reset C₁ such that ||K- S C₁ (I All | BlI whenever ||Â- | Bl s
TV
éI, and combine this with
31 we have: for any log(1 1/6) -
4G3
log(1/8)
PP IK K.1l < 2
2 1-
(32)
T1/2
With this probability bound on IK - K+ll. we can further upper bound the regret, shown in the following part.
B.2
Key Lemmas
We first upper bound the radius of a single trajectory with stable controller, for which we introduce and provide proof for the following lemma:
Lemma 17. Consider the continuous system d.,, = AX,dt + dW, such that a(A) < 0 where a(A) the largest real component of A and W is a standard Brownian noise. Then, w.p. least ò:
(V/llo((11 T)/8))
sup 0StST
Then we concentrate on how the error ||P - P.]l will influence the regret during the exploitation phase. For dynamic U with a(A BU) < O, we define cost function:
CUst(U)= tr (/ (elA+BUU)) + U RU RU)
1120
The convergence rate of this cost function is stated in the following lemma: Lemma 18. Let U, minimize cos)(U). Then, there exists 2 0 such that for any |AU|| = and e [0, co we have;
cost(U. + eAU) cost(U.) < C
The above result shows the average per unit time when applying fixed controller for infinite time.
Then we further consider the case when the running time finite. We derive the following lemma: Lemma 19. Let U. follows the same definition as in Lemma 18 Then, for some e > 0, there exist constants C2 and C3 (independent of UU such that for all T > 0 and any U such that U U. S 6,
Jr (U)) S C211a112 + C3-
Here Jr the expected cost of the policy that takes action by U. = UX, (L E (0, TJ), with initial state Xo
28

---

With this lemma, by definition of U=, we actually have U. = Ku, where K, = - P. and P.
the solution of Since such C2 C3 also satisfy:
J cost(U.)T) C2112111 C3.
so it follows that
Rr Jr J - 2C2112112 2C3
(33)
B.3 Proof of Lemma 17
We first upper bound the radius of a single trajectory with stable controller, for which introduce and provide a proof for the following lemma:
Lemma 17. Consider the continuous system d.,, = AX, + dWe such that of () < O where a(AA) the largest real component of A and W is standard Brownian noise. Then, w.p. at least 6:
(1xall2- ([(111 C (1 (1+T)/8)
sup OSIST
Proof. The trajectory X, with differential equation dx, AX, + dW, can be derived
x, Al Xo +
Al1-o)
==0
Lemma 7 tells that when A is stable, ||ea Xoll2 S (((())
Xooll2 So it suffices to show that
P sup LOSEST
Alt-s)) dW,
( 88.
Let T Toh with To be an integer. We first consider the set of points {Xaa]. Denote we kh () then wi ~N(0, Σx) with Σ₁ - eAe dt. This Σ,, also satisfies Je
| < /"h 1=0
|e di <
(th 20lAB) S
kh
1
2/a(A)I
1=0
Which follows that SUPoSkST, ||wx|l2 S 2 (a(A) log((1 + To)/5), w.p. at least 8.
Next we consider any Xas++ with t
h0 Bounding such terms requires the Doob's martingale
inequality [11), stated in Lemma 20
We denote of S eA(t-)) d with corresponding
d ll with A 2 Then 2 is a submartingale under the
filtration F, We also define 2 ==
filtration Fr, since for any 2
E 1 E exp {
(Alo-Meat
f c- e
WolddWitts Wittee {
> Ale 20 Z
11=0
Where we notice that E
- fi A-A k
Lonk
|ee As and apply
Jensen's inequality on the non-decreasing convex function ((x) xx to obtain the above inequality.
Now we apply Lemma
20 and get
P
sup (E(o,h]
lle
2 2 C - ACO E
(34)
We next estimate (B(,)) Since e - -Ah = S c where
At WWWdWe. we obtain that e Ahh ~ ~N(0,
h
Σ =
1=0
29

---

By setting A
1 it can be computed that 4|/2i|
Telle ah s
Jeen (2 /ot//)/
1 12 qua Lave lav da da
V det(2i) det(22 2ALa)
1
del - 21E)
- 2d/2,
where the last inequality is because L1 We combine this result with 34 and obtain:
22Σ = Ldd.
P
sup 10stch
1
2el 2el-Alh ||_|1/2 \log(24/2To/8)
TS
To 11
z 2 20/2 To
sup
[E(0,.)
k=0
To B(Zz) 8
P
sup [E|O,A]
z
k=0
< 6.
Finally, since Xah+t ((kh+()) Xo + e At xx it follows that
A(hh Xo /1, + wee'wall, aulllll + ||0:11/
||
S cc(())())+t))
[ + |wwll22 + 1|
By applying union bound on ||w=|12 and || we finally obtain Lemma
17
Lemma 20 (Doob's martingale inequality). Let XI,..., X, be discrete-timet submartingale relative to a filtration FI....,Fy, of the underlying probability space, which is to say:
X, $ E [X+1 [F).
The submartingale inequality says that
maxx (Xa, 0)]
P max X; Isisn
C
S
for any positive number C.
Moreover, let X, be submartingale indexed by an interval [0, T] of real numbers, relative filtration Fe of the underlying probability space, which is to say:
X, 5 EXx
for all < t. The submartingale inequality says that if the sample paths of the martingale are almost-suret, right-contimuuus, then
sup X 2 c < LOSIST
E max (Xx, 0)]
P
C
for any positive number C.
30

---

B.4 Proof of Lemma 18
In this section, we proof Lemma 18 which refers to the convergence rate of the cost function:
Lemma 18. Let U. minimize cost(U). Then, there exists cy 2 0 such that for any ||U 1 and
c C [0, col. we have:
cost(U, + +AU) cost(U-.) < Cie².
Proof. For any ||U 1 and 0, consider U2 + eAU, we show that O, there exists V E Rd such that tr(V) 0, and
/ c(A+BU)) (Q C U RU) ( - ((++BU.) U2 RU.)) dl 120
120
=cV+((2).
Let D(e, t) = - The most important intuition is that D(e, t) can be represented by the form of t)c,t)= = (Di (c,, t), where D1 (t) does not depend c, and the residual D2(c, t) can be well bounded. Now we find such (t) and upper bound || [2(c,, f)ll For S to max IA+BUU |II3 and < 1, the Taylor expansion of BBl+BBUU-AAA can be represented as follows:
D(c,t)=
= Σ k!
[AA+ BU, eBAU)* (A+ B
Σ k
Σ (A BU.) BUJ
c+ Dile,A)e th
where Di, k) is the residual of (A + BU + <BAU)* - (A + BU)* with order at least e². This sequence matrices are expressed and bounded as follows.
Di(k,)) = Σe 1=2
E
(A+ (B
+ BU.
in +ht.+ =k-
k!
[Di(k,))) S
Σ
||A MA++BU.1** BU.
BU.
il(k: - i)!
Thus have:
$ ΣΣΣ, 1
e) e)
ilk i)! 4.
Define E(t) and (e, t) as follows: for 0 5tt S to. let
Σ th
E(t) (A+ (BAU. BU,)- -
(e,
Di(ke)).
and for / E [3 10). 2 1, we inductively define E(2 and E, (2'1) as follows:
E(2't) e (.4+..)2'"''E 1t) E(2' "
Ee 2't) -e (A+BU)22 ' 2'- Ei(c, 2'- (11), 2
+ +F + ( (Fi 21,)))))))
Then we have the relation that e (A= - (A+BU.)) eE(t) + E,,,ett)
31

---

Now we upper bound [E())] and [[E When & S to:
|E(M S
(IA (U.) BU.) 6-1-11
-
(k:
1)!
R21
=
R21
For 12 2 40 let 1 = 2214 /1 with 2 be an integer and / E (2/0, fol. then
(2) -|le ((A+BUU)2) tt E(t) + E(t) ((t)c(A+BU.)) tc.
I 2c BAA+BU))) t4 | t2)l
3 2 Ba.
4
a(A + BU.)to
where the last inequality is because for any z, a > 0, De ox I L. and thus for any t 2 0, ||(()]] _ C = -o(A M0
When
2 -a(A.BB.J we additionally have
|E()] 2e3a(A+BU.)) E )
4t caa(A+BU..)
8
aa(A+BU.)
S
to
-a( A + BU.)L0
Now consider ti, When t to.
th Di(ke, 54.
[E
S
A21
When > to, with t 2tt, and t (2tt,tol, tol, we obtain:
[i((, =
((A++B.))2* 1 Ee
(EE2
teEi(e,2"-
< (A+ '1 < (OA
2e,,,, [| tei ( 21 + 4)ll + 2 26 | (1]]"
Now, we show that || (e, 211)) converges exponentially eventually. The proof consists of two parts: first, for which is not too large, || t) can be bounded uniformly over all possible AU and any constrained c. Then, for larger we can utilize the construction of || (c,t)) to estimate its convergence speed.
Let < -a(A+BU. Mag (640)²
lo = + [log2 =a(A+BU, J. We first inductively show that for any I S lo.
2441 < (2t+3_ - 2) The base case where = 0 is certainly true. Suppose we already have ( s (2 - -2 Then for the case of I, we obtain:
(e. (e,
[e, 214i)l < (e, 21-1 + 40 s (2 4)C²
where for the first inequality we use the inductive hypothesis that
64
2E, +1)l s 200+3 -a(A+ BU.)to
C $ C,
along with facts that 1 < C and (A4BBU 1 4t, < 2. Specifically, we have
Fi 2/11i)1 S =a(A+BU.)
6
32

---

Now, we consider > lo. We first show that for all such 1, [e,
(e, 2/ S -0, Since
64C
21 2 20 2 -a(++BU.) have 2e )2' 2 and thus
|1((,, - 220 11
E1
+ E(2 b1)l 26 || 2' bt
I 2e 2 Bi(e, 2t)0),
1) + 40
64C
-a(A BU.)to
which holds for all / lo with induction on 1. Now reuse the above expression and obtain that
[[ 2/
3 2ea BA+
11
(t)]l
+ 26"
El,
2e 20-
64C
128
22- +
2
aa(A+ BU.)Lo
a² BU )g
Let 4, be the smaller integer greater than + which satisfies:
2e 22-2'
640²
128
10-1
-a(A+ BU.
a²(A+ BU.)
4
Then by using the relation that 2c²
11))
< 26²
640
2 we have:
-a(d+BU.)a
2"))) - 2
Now we inductively show that for all h: 2 0,
E (c, +i)l ||| 2--
By using the hypothesis for l and 2c < 4. we obtain:
(e, 2 [1)l S 262 |[ (1,,2t 2l_+& +
1 je-
12-2
1 2 2+1
1 2212
4
< 2 --++
g++1
leading to the claim. This means there exist some constants Ci depending on a(A BU.) such that for all / 2 0, | (e, I)ll & aat
Finally, we consider Jiz0 el ((A+BUU* (QQ + UT BUA+BU.+aUU): = BUA+ -
Since
BU.
with |[(()]] S -a(A+BU.) cla(A+BU)) and
8
bounded Ej te, we obtain:
clA+BU)"+ + U RU)c(A+BUU
120
(e +ET (e, UTT (T +.E( + + (e,
120
(A+BU.)
(Q (Q + U.. RU, RU.) (A+BU)))
J120
(T(I)(+ + U. RU.) ( (A-BU.) BU.)t + (AABBU)) '(Q UTT
+
120
(A+RU.) (AUT RU, + U. (TTRUU) (1++BU dt
+e
120
+0(2).
33

---

Where the last term O contains any terms with order at least c², whose norm is at most Cze²
for any E [0, 6o) and | 1, where the constant C₂ depends on A, B, a(A + BU.) and en some small constant.
For any
| 1, define V by
(T())(Q + U. RU. RU.)e(A+BUU..) + ((A+RE"" RU)
=
120
(A+BU.)*+ (AUTRUS RU, + + UURAAA)) (A (A-BU.>ddt
+
120
then cost(U) cost(U.) + etr( O
Since U. minimizes (U) tr(V) c (cost(U, cAU) cost(U.)) 0. Therefore, we obtain that cost(U) = cost(U.) + O
B.5 Proof of Lemma 19
In this section, we proof Lemma 19
Lemma 19. Let U. follows the same definition in Lemma 18 Then, for some 0, there exist constants C2 and C3 (independent of U) such that for all > 0 and any U such that U U.| S e,
Jr cost(U)T) S C211=112 Cs.
Here Jr is the expected cost of the policy that takes action by U. = UX2 (t E [o, TT), with initial state Xo x.
Proof. By definition of Jy, we have:
JT l + dt [ xF + UT RU,dt
Since the state transits according to dX, AX,dt + BU + dW,, we can derive the expression of X₂ by X. (U)+BU)NN) Xo + f (1++B))(t-s) dW, Then by utilizing this expression we obtain:
E [ RU)
= -clA+BUTe TT) + U. RU)c(A-BUTeE
(clA+BO)s (cla+Bo)xx))1100 (0)"(Q+UUU ( clatBura-oldw.)
+ 2E
T (MW (Q (Q+ 1 RUU ( c(A+BU) c(AtBuy6-
+E
-TeCA4BB) (Q T. RU)e(A+BUXS BUB Xa
t ( clA+BUT" (Q U RU e
= XTCCABBO) (Q T. RU (A+ (A+BU Xo
+ I tr (c(A+BU)*=( (Q + UT RU)e(A+BU)s) ds.
==0
34

---

Then, the expected cost on a trajectory lasting for time T can be computed as:
E
XT + U RU RU)
E (x + T RU) RU) dt
LED
Xo ( BU)" : (Q 1 +U UTRUUUR (A BUY Xndt
(T t)tr (clA+Bu) (Q + U RU RU)c(A+BUU)) dt
1=
X (Te(A+BUU" (Q U +UURUU) (A (1- BUB Xodl + cost(UU)?
1=
tr (c(A+BU)+ (Q U RU RURRURDRR (U tdt
tr (clAtRU)) 1Q + U RU) RU))(A+ dt.
T=
Here the first term satisfies
Vid X XeelatBu''(00++ U RU (U)) Xodt $ 2a((A+BU}e
|xoll2 dt
-12
I -2 A + BU)
11
and the latter two integral terms can be bounded as follows.
1' tr (clAtBU> + U RUU))RU) (4 tdt
$ { d. 2allBBBB
1Q+ U RU|| tåt
120
d d + U RU
4a (A + BU)
(clAtBUT U U""")""(COO" de
1=T
T
d.e 2a2aABBB
Q + UJ RU di
J12T
T' [ + UT UTRUU 22a(A+BUyr
-2a(A + BU)
d a11Q CUQUUUTRR
4a2 (A+ + -BU)
Therefore, for C22 2 2a(A+ BUT and C3 2 d d||Q+UTT RD
[A= we have
JJ - (Us) - C2|1=113 + Cs.
B.6 Proof of Lemma 21
Finally, we prove Lemma 21 In this part we suppose T> > To. where Ty 2 1 is constant depending on some hidden constants and | ll2
35

---

we can find some constant Co depending on Lemma 21. regret Let U2 be the action applied as in Algorithm 3 Then there exists constant C' E poly(K, M, p la(A BK) a(A+ BK.) ") such that for sufficiently large T:
E
(XTQX, + U, RU,) dt CC.
1=0
E
(XFQx, + U2 dt SC.
l=VT
Define the following events where the stabilizing controller K might ever be applied during the exploitation phase. Let E wTllz / [|xell2 2 7 for some t E [VT,T]] f. and {I K.
|| S. ea), where e3 depends on the constant en in Lemma 18 which will be determined later. In this part, we again let C1, C2 be the same as in 332 and denote C3 be the constant C₁ in Lemma 18 We firstly analyze these three events.
Upper Bound of [ By Lemma 17 || B|I,, [[,]], d, p. such that
PP XX Tll
56.
This is because we have the recursive function of {XEa] that
X(k+1yA = ((A+BK) Xah + 1 cl4+BB)(h-0 WW + 1 c(A+BK)( 1
1=
from which we can derive that
Xkh
kh c(A+BKiRh Xo + 1 1=
(1' c(at-Ksed c(t.EKr u.
(A+BK)(kh () dW,
(A+ (A++B))---DA
1=0
Then, for sufficiently large T, |c(++KKVT Xo
can be bounded by and from the proof in Lemma 17 we apply similar idea to upper bound the norm of the last two terms. So obtain the probability bound on ||
T1/5 4c.
1/5
By setting 8 = 2T
obtain that [PE]] < 2T e 40g
Upper Bound of P
By 31 obtain that, for c3
Cjel
have:
T1/9403
T1/2
PP [[[K K.
Se
VI E3
T1/2,3 iefez
and we also have: IP[E]] S
T1/1,2
By setting E3
Cig TV/AA3
we have: P[E Se
1403
Upper Bound of [[E2] Consider any ||x la s 1/15 and any |R -. S eg, we claim that X K] < e -2(2
As what have discussed Lemma (see the discussion about stable margin near such K satisfies a(A + BK) < fa(AA + BK.)
36

---

Then by Lemma 17 we can derive that, for some constant C,
sup (E(vT.T]
|
|X || S TL/5
3 CTe
21/0
c S -6-R(T1/))
Therefore,
P F - 1 - IP [Ef ]Eg] - [&f n&)
3 [ + [ e (
S Se- -(T1)))
Now we come estimate the expected cost of Algorithm as well as bound the regret. We separately calculate the cost during the two phases.
Cost During Exploration Phase
For + 1)h I T and E [0. hl. we have:
kkttt
c(A+BR)(M+++- dW, (fr c(A+BR)-ds) ux.
Xuh+t = (A+BBK) Xuh +
s=hh
Then
gh+ QXkn+ URh++ U kh+t] RUkh++]
E
X kh+ (Q (TKKK)A XK) + uu Ruu
21E [X [ K" Reu
E Rh (Q + K RK) X + ue Run
T c(A+BK)sds KJ Run 5=0
+ 2E
uk
where the inequality because uy independent of Xah and W.(s [kh, kh t)). For the first term, first upper bound EE [||Xx++el@]]
Denote Wk,t = / B()-B))(A++t-)) dW, + (Jem e(A+BK)=ds) ug. which is a Gaussian variable with zero mean and independent of Xxh. Then
c(A+BB) Xxh + Wket
E
E
E
[(L+BK) X
+ E
[[
E [1] | 222]
1 E
For E [||X 12) since
kh
(4+BK)( (1e clat us.
Xa1. (4+B)) Xo +
(1) d.,,
11=
We have
[( Xo
+
( dW.
==
(A+ BA+
(A+BKW
us
kh (1/r
|xol +tr tr 2a(A+BK))
clA+BKI (A+BBK)(A+BBK"* dt
===
[eln-Rraa (1e c(AtBRYE
c(A+BK)u (1r c(AABBK/a))
37

---

Therefore, we have
f d c20(A+BK)) +
E Xkh [2] x 22((AtBK))
1xo +
d 20(A+BK)ih h??
1=0
2
d
di?
( 1
2a BK)
(2
5 +e 2 X
Where C3 is a constant depending on (AA BK) and d.
For the second term E [| can follow the same process of the above bound and obtain E [13] I C3. Therefore, E XRn++ll [| 1 2C3.
Now upper bound E
X + QXkn+z + URh+ RURh++) We have
Me K RK) XxN++ < E ||Q + K RK [| 1|@+
[|
We also have IE [ Ruxl tr()t) and the following inequality:
E Uk (L"
T e((tBK)sds ds) KT Rux s (d+
[C. clAtBKidds)
T KT R S +d+
We can conclude that there exists constant C4 depending on A, B, K, Q, R d, p, h such that
E [ kh++ QX + Ukht RUnn+e] s C4 20(A (1+e2a(A RK) (K)-(B)))))) (kh++) (xo13) vk, L.
Therefore, the cost during exploration phase can be bounded as
[ (XTL+ + RWnte) dt s C4
(V
|Xoo 22(AA + BK)
(35)
Cost During Exploitation Phase first concentrate on Eg, which the hardest event for analysis of the cost. Consider the following two cases:
Case 1: Tll2 2 1/5 In this case, the action is applied by U, = KX,t [VT,]].
Case 2: ||X TTll < T1/5, In this case, the trajectory is unfortunately controlled by bad controller, and suffers from large risk of diverging.
We first consider Case 1. By (??) we can derive that
X X,= ((=(BBB))t-- X S
C(A+BK)(--)dW..
Then, we have:
E +U
= + KTRK)XX
< <|Q0K* [TRKK]]]]] RK|
[11
| + fd -=EV tr (644281--) (t- dt
< ||Q K RK]
| l" - d. call-BBBK)
Q + KT RK||
Therefore, for some constants Cs, Co. we have:
E [xFQx, U/ RU:]
< Cc. Co.
38

---

Now we consider Case 2. Let to infell 2 T 2 vT), then |X = / almost surely.
Fort t E [VT, to], since always have
||U|l|2 I max (I[ ( PlI) |Xell2 S (IK + ||| T2/s,
the cost satisfies:
XTQX, + Up RU, CF14/5,
Where C7 is constant depending B, R. K, P.
Fort t E [to,T], the trajectory Xt satisfies
X; ((A+BK)(- Xto S s
c(A+BK)(-dd
Similar to the analysis sis for Case 1, we have:
E B + Uf RU,] S C + Co
Combining them, we can conclude that for some constant Cs, no matter whether &g happens, we always have:
E X Qx OX RU,] s Css I + IX + WE [VT.M]
Now we establish the upper bound for the regret. Since
1 lefines + læ, + Egfney
Then we can rewrite [ (x, + U, RU;) dt as
E
(XF + U2 RU:) dt
L=VT
E
(XTQx, + U, RU:) dt Lefrea
+ E
(XTQX,+ U UU di la,
l=VT
+ E
+ U
dt lefree
L=VT
For the first term, we can upper bound it by
[ V=VT
E
(xTQx,+ U. R,.) di lefnes
< E
+ UX; RU,) dt Lefrefnes
L=VT
+ EE
(XTQX, + Uf RU:) dt Lefnes
E
(cost (R-' p) T C (13) lspres]
+ E Ccs (TT/5 + ||x T lepnes]
< 2/ + cosl cost P.YT CI [|| K. 11. + 2//5 E 1 [efnes]
39

---

Here the first inequality is because Lefnes Lefnefnes + Lngnenn and Lefreanes S nes For the second inequality, the first term is because we can assume situation that we do not change the dynamic when Eg happens, and that will not make the expectation smaller. By applying the results of Lemma [8 and Lemma 19 we can get this term, where the constant Cg is related to constants in these two lemmas. The last inequality is obtained from these two lemmas and the definitions of Ei, &2, Ez. As for E [IIK K.I12 leal,
the bound that
T1/2 20t0s
P [[IK
Kg
2 2
Se
Se
Vr
S
and compute that
E
||| K.I12. 1891
[1|K K.l' 2 dr
2=
Td/2 10900' dx
$
122
4CRC2
T1/2
For E
Legnes we directly have E
[efnea)
$ S S (0(11/)) Combining these results and
Lemma 19 we obtain that for some constant C,
E [[ (X.QX,+ U.. di lefiees
S +
For the second term E [ (x7 QX, + RU*) dt 1s.] given any XVT, we always have
[XQQX,+ + U. RU:] s Css (T// + 1 V (V.T].
E
So we upper bound E [__ (XFQx, Uf RUi) dt 1e,] by
1' (XFQX, + UU RU)) dt 18, LEVT
E
< CCTT/5p(81) + TEE [|XX 1 la] |||X 12 1s,]
< +
where for the last inequality we apply the upper bound of P[E1] shown before.
For E [[IX 1s we can apply Lemma 17 and obtain that for some constant > 0, for any
2 //5 we have
P
||| 7ll2 2 x) se -c0
Thus have:
TE
[[|X /r 12 LE,]
7 7
/Tll2 2 /
T//
+T
P P MIX,Tli
2 x] dr
22/79/5
< 0(1)
Therefore, we have E T + UF RU,) dl 18 S 00)
40

---

Finally, for the last term E ST (XTQX, RUi) dt Legneg when condition on any
||X vrlle I 1T estimator (A, B) and Xto where to = 12vr (1-xellll 2 T2/5), we still have:
E XX s Cs [141 [14/0+10111 11x 11 [1] S 220 [VT.T]
So we can upper bound it by
E
L=VT Qx, + U RU)) dt lepneg
20 [&f nEgl
- 20
0().
Combining them we finally obtain Lemma
41

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clarify our contributions and basic problem setups in both abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
42

---

Justification:
Assumptions can be found just near the main theorems. The complete proof is contained our Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We disclose the experiment details in Section 5.3.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
43

---

Answer: [No]
Justification: Our code is very simple, just use a simulation experiment of 3 matrix. Our main contribution is the theoretical analysis.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
public/guides/ https//Soooeeuubssssoooooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https http://oooouuuisss.ooeee
//nips. //nips.cc/ppl wwcppblicgguticcccccccceeeooo.ee
htt.SSbbbiiiiooooiiiiiooooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details in Section 5.3.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We compute the average regret in our experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
44

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: Our code is very simple, which can run on CPU of a computer.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw..aaar.....o//////////a
Answer: [Yes]
Justification:
We conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is about the theory on online control and system identification, which does not seem to have evident societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
45

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
46

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
47

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [No]
Justification:
The LLM is used only for editing the paper of grammar mistake.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: /00p:////c...eceeeeee/e////////0 for what should or should not be described.
48


Reviews:
[{"review_id": "IKCn8Y9GH9", "reviewer": "Reviewer_YKfn", "summary": "This paper develops non-asymptotic system-identification algorithms for continuous-time linear dynamical systems using only a finite number of noisy state observations. By discretizing at carefully chosen intervals and directly estimating the matrix exponential, the authors recover the continuous-time parameters without incurring discretization bias, achieving an estimation error of $O(1/\\sqrt{T})$. They also prove a matching lower bound showing this rate is optimal up to constants. They also apply the above algorithm to online control regret analysis for continuous-time linear system.", "questions": "My main concern is the linear model specification. As the authors note in Section 6, many practical models are nonlinear. To what extent can the results in this paper be extended to nonlinear settings? It would also be useful to run robustness checks to assess the proposed method’s performance under nonlinear models.\n\nThe simulation study is limited. Adding simulations for higher-dimensional systems would help evaluate the stability of the proposed method.\n\nHow should one choose the sampling interval $h$? In theory, it can be set according to Assumption 1, but $\\kappa_A$ is unknown in practice. Is there a data-driven procedure for selecting $h$? \n\nMinor typo\n\nPage 6, line 208: “we proof Theorem …”.", "limitations": "See the weaknesses and questions for details.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThe paper provides the provable error bound for continuous-time system identification, which also matches information-theoretic lower bound. It applies the identification scheme to online LQR, achieving $O(\\sqrt{T})$ regret. \n\nWeaknesses\n\nExperiments are restricted to small, simulated 3-dimensional systems; the performance and numerical stability of the method in higher dimensions or on real-world data remain untested. It would be helpful to comment/provide further simulations in higher dimensional setups. \n\nExtension to adversarial or non-Gaussian noise: As mentioned in the paper, the analysis assumes stochastic (Brownian) disturbances; it is unclear how the method performs under adversarial or heavy-tailed noise models.", "was_revised": true, "final_justification": "The authors have successfully addressed my concerns. Thus I increase my score.", "rebuttal": "We sincerely appreciate the reviewer’s insightful comments and suggestions. The minor typos have been corrected in the revised manuscript. Below, we provide responses to the main questions.\n\n>Q1: It would be helpful to provide further simulations in higher dimensional setups.\n\n**A1:** We appreciate the reviewer’s feedback. To address this, we conduct an experiment in a higher-dimensional setting with $d = p = 10$. Each entry of $A$ is sampled uniformly from $[-1, 1]$. The matrices $B$, $Q$, and $R$ are set as identity matrices.\n\nSince figures are not permitted in the rebuttal, we present the estimation errors $\\Vert\\hat{A} - A\\Vert_F^2$, $\\Vert\\hat{B} - B\\Vert_F^2$, and the normalized regret $R(T)/T^{1/2}$ in the tables below.\n\n|Running Time|Estimation Error of $A$|Estimation Error of $B$|\n|:----:|:----:|:----:|\n|5|2.80|1.06|\n|10|1.99|0.67|\n|15|1.62|0.53|\n|20|1.40|0.45|\n|25|1.25|0.40|\n|30|1.14|0.37|\n|35|1.07|0.34|\n|40|1.00|0.32|\n|45|0.91|0.29|\n|50|0.85|0.27|\n\n|Running Time|Normalized Regret of Our Algorithm|Normalized Regret of Baseline Algorithm([6])|\n|:----:|:----:|----:|\n|500|61.7|18.5|\n|1000|70.9|28.5|\n|1500|65.6|43.9|\n|2000|64.7|53.5|\n|2500|65.8|51.3|\n|3000|62.4|66.4|\n|3500|59.9|71.8|\n|4000|57.1|79.2|\n\nThese results show that in high-dimensional settings, our algorithm achieves low estimation error and $\\mathcal{O}(\\sqrt{T})$ regret, outperforming the baseline algorithm which achieves $\\mathcal{O}(\\sqrt{T}\\log T)$ regret when $T$ is large.\n\n>Q2: It is unclear how the method performs under adversarial noise models.\n\n**A2:** We thank the reviewer for this insightful question. While many online control works focus on adversarial noise [1,2,3,4], our research addresses stochastic noise. However, only stochastic noise models readily extend to continuous-time systems [5,6,7] (e.g., by modeling Gaussian noise as Brownian motion). Currently, a formal definition of adversarial noise in continuous systems is lacking, which precludes such an analysis in the continuous setting. We agree that extending adversarial noise setup to continuous-time systems is an important future direction.\n\n>Q3: It would also be useful to run robustness checks to assess the proposed method’s performance under nonlinear models.\n\n**A3:** We appreciate the reviewer’s suggestion. The key difference between linear and nonlinear models lies in the transition dynamics: linear systems admit explicit solutions, while general nonlinear transitions typically cannot be computed in closed form and must be approximated. \n\nThe main contribution of our method compared to known ones is estimating the underlying state transition rule from discretized samples. This may still help reduce discretization bias when applied to mildly nonlinear systems. However, the accuracy then depends heavily on the convergence rate of this approximation, which is generally hard to quantify for nonlinear systems. Extending our method to nonlinear settings is an important direction and we leave it for future work.\n\n>Q4: How should one choose the sampling interval $h$? In theory, it can be set according to Assumption 1, but $\\kappa_A$ is unknown in practice. Is there a data-driven procedure for selecting $h$?\n\n**A4:** We thank the reviewer for the insightful question. In practice, $\\kappa_A$ can often be estimated based on physical insights or prior system knowledge—an assumption commonly made in system identification. Prior works on continuous-time identification also adopt assumptions on system parameters. For example, [5] assumes H.1, and [6] assumes the initial estimates $(A,B)$ are within specific error bounds of the true parameters $(A*, B*)$ (see Equation 7).\n\nWhen $\\kappa_A$ is unknown, a conservative sampling interval $h$ can be used. In our experiments, we set $h = \\frac{1}{30}$, which, while not necessarily optimal, guarantees convergence for both single and multiple trajectories. Different choices of $h$ affect only the constant factor, not the order of $T$. We clarify that $\\kappa_A$ in Assumption 1 acts as a theoretical upper bound, and choosing a sufficiently small $h$ ensures $h < \\frac{1}{15\\kappa_A}$ is satisfied.\n\n\nFinally, we thank the reviewer once again for the effort in providing us with valuable and helpful suggestions. We will continue to provide clarifications if the reviewer has any further questions.\n\n**References**\n\n[1] Agarwal, Naman, et al. \"Online control with adversarial disturbances.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Hazan, Elad, Sham Kakade, and Karan Singh. \"The nonstochastic control problem.\" Algorithmic Learning Theory. PMLR, 2020.\n\n[3] Simchowitz, Max, Karan Singh, and Elad Hazan. \"Improper learning for non-stochastic control.\" Conference on Learning Theory. PMLR, 2020.\n\n[4] Agarwal, Naman, Elad Hazan, and Karan Singh. \"Logarithmic regret for online control.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[5] Basei, Matteo, et al. \"Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon.\" Journal of Machine Learning Research 23.178 (2022): 1-34.\n\n[6] Faradonbeh, Mohamad Kazem Shirani, and Mohamad Sadegh Shirani Faradonbeh. \"Online Reinforcement Learning in Stochastic Continuous-Time Systems.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[7] Shirani Faradonbeh, Mohamad Kazem, Mohamad Sadegh Shirani Faradonbeh, and Mohsen Bayati. \"Thompson sampling efficiently learns to control diffusion processes.\" Advances in Neural Information Processing Systems 35 (2022): 3871-3884."}, {"review_id": "fE0j4wXUWp", "reviewer": "Reviewer_nQK5", "summary": "This paper developed a system identification algorithm for continuous-time stochastic linear systems. The proposed method is based on time-discretization with a properly designed sampling interval. The estimation accuracy is guaranteed by an upper bound (Theorem 2). Moreover, based on the established result for the system identification, the authors devised an online control algorithm for continuous-time systems. Its performance is guaranteed by $O(\\sqrt{T})$ regret upper bound (Theorem 6). The effectiveness of the proposed methods is verified through numerical experiments.", "questions": "- In Theorem 4, the system parameters $A$ and $B$ are allowed to depend on the time horizon $T$. In fact, in the proof sketch, the authors consider stable matrices $A$ and $\\bar{A}$ satisfying $ |A - \\bar{A}| = 2c_1 / \\sqrt{T} $. However, the true system parameters are independent of $T$. Therefore, deriving a lower bound based on $A$ depending on $T$ appears to lack meaningful interpretation. If there is a valid reason why such a $T$-dependent construction of A is relevant or meaningful in the context of this work, it should be explained clearly and convincingly in the manuscript. Otherwise, a lower bound should be derived under the assumption that $A$ is independent of $T$.\n\n- In Section 4.4, the authors consider the situation where a stabilizer is not known in advance. Then, they propose to first find a stable controller. However, Theorem 5 only gives the estimation error of system parameters and does not establish a result about stability. Therefore, it is unclear how Theorem 5 is useful. I suggest using Theorem 5 for finding a stabilizer for online control of unstable systems and establishing $O(\\sqrt{T})$ regret bound without Assumption 3-1, which assumes knowledge of a stabilizer $K$. Then, the usefulness of Theorem 5 is clarified.\n\nThe usefulness of two theorems (Theorems 4, 5) is unclear in the current version.\nIf this issue is properly addressed, I would gladly raise my review score.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\nThe proposed algorithm can attain an expected regret of $O(\\sqrt{T})$ with only $O(T)$ samples in time horizon $T$.\nEven when a stabilizing controller for an unstable, unknown system is not known in advance, the authors establish an upper bound of the estimation error by using multiple short-interval trajectories.\n\n\n### Weaknesses:\nI would like to point out that your paper adopts the pseudo regret in Theorem 6, while the existing studies [23,30,31] on continuous-time online control instead used the regret definition based on trajectory-wise comparisons, namely $$ \\int_0^T [c(x_t,K_t x_t) - c(x_t^{\\star}, K_{\\star} x_t^{\\star})] dt, $$\nwhere $x_t^{\\star}$ is the optimal trajectory and $c(x_t,u_t)$ denotes the cost function. The analysis of the regret is generally more challenging than that of the pseudo-regret as it requires accounting for trajectory deviations under the learned and optimal policies. Therefore, the fact that the proposed method achieves $O(\\sqrt{T})$ upper bound of the pseudo-regret, does not imply that it surpasses the performance guarantees of the existing studies [23,30,31]. The authors should clarify this distinction and carefully position their results in relation to those earlier studies.", "was_revised": true, "final_justification": "The authors have addressed my concerns. Therefore, I increase my score.", "rebuttal": "We thank the reviewer for the comments and constructive suggestions. We address the reviewer's questions in more detail as follows:\n\n>Q1: This paper adopts the pseudo regret in Theorem 6, while the existing studies[1,2] on continuous-time online control instead used the regret definition based on trajectory-wise comparisons. The proposed method achieves $\\mathcal{O}(\\sqrt{T})$ upper bound of the pseudo-regret, does not imply that it surpasses the performance guarantees of the existing studies[1,2]. The authors should clarify this distinction and carefully position their results in relation to those earlier studies.\n\n**A1:** We appreciate the reviewer’s comment. This is a very helpful point and we will add the clarifications below in our updated manuscript. \n\n\nWe first clarify that existing results [1,2] achieve an $\\mathcal{O}(\\sqrt{T} \\log T)$ bound for both the exact regret and the pseudo-regret. The cost over $[0,T]$ is defined as: $$Cost_{T}=\\int_{t=0}^{T}X_{t}^TQX_{t}+U_{t}^TRU_{t}dt ,$$\n\nwhich can be decomposed as:\n\n$$\nCost_{T}=J_{T}+\\int_{t=0}^{T}X_{t}^{T}QX_{t}+U_{t}^{T}RU_{t}-\\mathbb{E}[X_{t}^{T}QX_{t}+U_{t}^{T}RU_{t}]dt ,\n$$\nwhere $J_{T}=\\mathbb{E}\\left[\\int_{t=0}^{T}X_{t}^{T}QX_{t}+U_{t}^{T}RU_{t}dt\\right]$ is the pseudo-cost used in our analysis.\n\nThe total regret can then be written as: $R_{T}=(J_{T}-J_{T}^{*})+(Cost_{T}-J_{T})$, \nwhere the first term is the pseudo-regret and the second term captures the randomness due to noise.\n\nPrior works only obtained $\\mathcal{O}(\\sqrt{T} \\log T)$ bounds for the pseudo-regret term $J_T - J_T^*$, while we improve this to $\\mathcal{O}(\\sqrt{T})$. The second term, $\\text{Cost}_T - J_T$, has zero mean and variance $\\mathcal{O}(T)$ under any fixed stabilizing controller, and can be bounded by $\\mathcal{O}(\\sqrt{T})$ with high probability, or $\\mathcal{O}(\\sqrt{T} \\log T)$ uniformly over $T$.\n\nWe believe that the main analytical challenge lies in controlling the first term, and our method can be directly applied to derive a bound on the total regret. In contrast, the second term arises from the inherent randomness of the noise process and is unavoidable. Therefore, our improvement in the pseudo-regret term represents an improvement over previous methods under the same regret decomposition framework.\n\n>Q2: In Theorem 4, the system parameters $A$ and $B$ are allowed to depend on the time horizon $T$. In fact, in the proof sketch, the authors consider stable matrices $\\bar{A}$ and $\\bar{A}$ satisfying $|\\bar{A} - A| = 2c_1 / \\sqrt{T}$. However, the true system parameters are independent of $T$. Therefore, deriving a lower bound based on $A$ depending on $T$ appears to lack meaningful interpretation. \n\n**A2:** We thank the reviewer for the comment. Our upper bound shows that for fixed $T$, any transition matrix $A$ with bounded norm can be estimated with error $\\mathcal{O}(1 / \\sqrt{T})$. The lower bound establishes that for fixed $T$, there exists some $A$ satisfying the assumptions for which no algorithm can achieve estimation error better than $\\mathcal{\\Omega}(1 / \\sqrt{T})$. The purpose of Theorem 4 is to demonstrate that our method is near-optimal, and allowing the adversarial choice of $(A, B)$ to depend on $T$ does not break the above message. \n\n\n>Q3: In Section 4.4, the authors consider the situation where a stabilizer is not known in advance. Then, they propose to first find a stable controller. However, Theorem 5 only gives the estimation error of system parameters and does not establish a result about stability. Therefore, it is unclear how Theorem 5 is useful.\n\n**A3:** We thank the reviewer for the helpful suggestion and we will add the following details in our updated manuscript. When a stabilizer is not known in advance, we can first apply Algorithm 2 using multiple independent trajectories to estimate $\\hat{A}, \\hat{B}$. With enough samples, the estimation errors $\\Vert\\hat{A} - A\\Vert$ and $\\Vert\\hat{B} - B\\Vert$ can be made sufficiently small. Based on these estimates, we can compute a controller $\\hat{K}$ that stabilizes $(\\hat{A}, \\hat{B})$, i.e., $\\text{Re}(\\lambda(\\hat{A} + \\hat{B}\\hat{K})) \\leq c$ for some constant $c < 0$. When the estimation errors are small enough, $\\hat{K}$ will also stabilize the true system $(A, B)$. Therefore, Algorithm 2 can be used to construct a stabilizing controller. We appreciate the reviewer’s suggestion and will clarify in the next version of our manuscript how Theorem 5 supports the construction of a stabilizer.\n\n\nWe thank the reviewer once again for the valuable and helpful suggestions. We would be happy to provide further clarifications if the reviewer has any additional questions.\n\n\n**References**\n\n[1] Faradonbeh, Mohamad Kazem Shirani, and Mohamad Sadegh Shirani Faradonbeh. \"Online Reinforcement Learning in Stochastic Continuous-Time Systems.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[2] Shirani Faradonbeh, Mohamad Kazem, Mohamad Sadegh Shirani Faradonbeh, and Mohsen Bayati. \"Thompson sampling efficiently learns to control diffusion processes.\" Advances in Neural Information Processing Systems 35 (2022): 3871-3884."}, {"review_id": "6h7Rxpb97g", "reviewer": "Reviewer_tEBy", "summary": "**Setting**. This paper studies the system identification and online control problems for continuous-time linear systems. Specifically, the system dynamics are given by: $d X_t = A X_t d t + B U_t d t + d W_t$, where $X_t$ and $U_t$ represent the state and action respectively, and $A, B$ are unknown system parameters. The control objective is to minimize the following continuous-time loss function:\n\n$$\nJ_T = \\mathbb{E}\\left[\\int_{t=0}^T \\left(X_t^{\\mathrm{T}} Q X_t + U_t^{\\mathrm{T}} R U_t\\right) d t\\right]\n$$\n\nwhere $Q, R$ are known. Since the system is unknown, the parameters $A, B$ must be estimated online from observed data, and actions must be selected based on these estimates to optimize the loss. The whole process is interactive and online, so the objective is rewritten as minimizing the regret $R_T = J_T - J_T^*$.\n\n**Methods**. The overall strategy consists of two parts. First, the continuous-time system is transformed into a discrete linear system:\n\n$x_{k+1} = A^{\\prime} x_k + B^{\\prime} u_k + w_k$.\n\nSecond, the remaining problem can be viewed as a bandit problem: on one hand, exploration is needed to estimate the parameters more accurately; on the other hand, we need to select optimal actions based on the estimated system.\n\nThus, an explore-then-commit strategy is adopted: during the initial phase, a known stable controller $K$ is used to sample data. Then, based on the collected data, the system is estimated, and the optimal actions are selected using the estimated system and the known loss function.", "questions": "- In the second figure of the Experiments section, the red line is flat by normalization, but was the regret also flat during the early exploratory phase? That seems a bit strange— the regret should increase rapidly at the beginning and then stabilize later, due to the exploration then commit.", "limitations": "As mentioned in the weaknesses, I have concerns about the assumptions and setup of this work. The proposed method relies on a known stable controller for an unknown system, which seems contradictory. In an unknown environment, obtaining a stable controller typically requires some form of exploration or trial-and-error. This paper essentially ignores the impact of that exploration phase on the overall finite-sample analysis. A direct question would be: if we include the sampling used for exploration, is it still possible to achieve sub-linear finite-sample regret? Or does the analysis only hold in the asymptotic sense?", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n- The theoretical development appears solid and the content is detailed.\n- It provides finite-time theoretical guarantees for continuous-time linear systems, while most prior work in control theory typically focuses on asymptotic convergence.\n\n**Weakness**\n\n- Assumption 3 seems a bit questionable: if the system dynamics are unknown, how can one find a stabilizing controller $K$? This implicitly requires Assumption 1 — namely, that the system matrix $A$ is already stable — otherwise finding such a controller would be very difficult. Therefore, this assumption feels rather strong.\n- Although Section 4.4 proposes a strategy to find a stabilizing controller, this procedure itself involves estimating $A, B$, which is also part of exploration. However, this is not clearly discussed or accounted for as part of the exploration strategy.\n- While the paper emphasizes its focus on continuous-time systems and providing theoretical guarantees in that setting, the core methodology still relies on first discretizing the system and then applying techniques from discrete-time analysis. The approach is not purely continuous in nature.", "was_revised": true, "final_justification": "My initial concern was that the paper assumes a known stable controller for an unknown system, whereas in practice, obtaining such a controller also requires learning and can be viewed as part of the exploration process. The theoretical analysis in the paper did not initially account for the impact of this exploration phase on the overall performance. However, the authors’ rebuttal clarified that the cost of this phase is essentially of order $\\log(T)$, and thus does not affect the final regret bounds. As a result, my main concern has been addressed. Thus I increase my score.", "rebuttal": "We express our gratitude to the reviewer for the insightful comments. We address the reviewer's questions in more details as follows:\n\n\n>Q1: Assumption 3 seems a bit questionable: if the system dynamics are unknown, how can one find a stabilizing controller $K$? This implicitly requires Assumption 1 --- namely, that the system matrix $A$ is already stable --- otherwise finding such a controller would be very difficult. Therefore, this assumption feels rather strong.\n\n**A1:** We appreciate the reviewer’s comment. As noted in our manuscript (see Subsection 4.4, line 229), assuming access to a known stabilizing controller is standard in control with a single trajectory, and also in previous works[1][2]. \n\nMoreover, our analysis in Section4.4 is dedicated to the problem when such a controller is not available. One can first apply Algorithm 2 using multiple independent trajectories to estimate $A, B$. With enough samples, the estimation errors $\\Vert\\hat{A} - A\\Vert$ and $\\Vert\\hat{B} - B\\Vert$ can be made sufficiently small. Using these estimates, we can compute a stabilizing controller $\\hat{K}$ for $(\\hat{A}, \\hat{B})$ such that $\\text{Re}(\\lambda(\\hat{A} + \\hat{B}\\hat{K})) \\leq c$ for some $c < 0$. When the estimation errors are small enough, $\\hat{K}$ also stabilizes the true system $(A, B)$. Therefore, Assumption 3 is practically feasible and does not require $A$ to be stable.\n\n\n\n\n>Q2: Although Section 4.4 proposes a strategy to find a stabilizing controller, this procedure itself involves estimating $A, B$, which is also part of exploration. However, this is not clearly discussed or accounted for as part of the exploration strategy.\n\n**A2:** We thank the reviewer for the suggestion. As discussed in A1, the procedure in Section 4.4 offers an alternative way to obtain a stabilizing controller through exploration using multiple trajectories. We will add the explanation as the reviewer suggested.\n\nIn our main analysis, we assume a known stabilizer, which is standard in the literature and allows for a direct comparison with prior works [1][2] under the same assumption. Importantly, under this assumption, our algorithm achieves significantly lower regret than existing methods, as demonstrated both theoretically and empirically.\n\n>Q3: While the paper emphasizes its focus on continuous-time systems and providing theoretical guarantees in that setting, the core methodology still relies on first discretizing the system and then applying techniques from discrete-time analysis. The approach is not purely continuous in nature.\n\n**A3:** We thank the reviewer for the question. As computation can be only done with discrete samples, our work aim to close the gap between a continous world and a implementable estimation algorithm using discretely sampled data.\n\nWe also note that our method performs an exact transformation, not an approximation, unlike prior work. In existing approaches to continuous-time system identification [1][2], discretization is typically based on approximations (see Section 5.1 of [1]):\n$$X_{t+h} \\approx (I + hA)X_t + hBU_t + (W_{t+h} - W_t). $$ \nThis introduces a discretization error between the approximated and true dynamics. The error term, given by $(e^{hA} - I)/h - A$, is of order $\\mathcal{O}(h)$. To ensure the discretization error does not dominate, $h$ must be set as $\\mathcal{O}(\\frac{1}{\\sqrt{T}})$, leading to a super-linear sampling complexity $m = T/h = \\mathcal{\\Omega}(T^{3/2})$, and thus higher computational cost (see discussion in Section 4.1 of our manuscript).\n\nIn contrast, our method avoids such approximations by using an identity-based transformation (see Lemma 1), eliminating the discretization error entirely. As a result, the sampling interval $h = \\frac{1}{15}\\kappa_A$ depends only on system parameters, not on $T$. This allows the sampling complexity to scale linearly with $T$, offering substantial computational benefits. \n\nMoreover, our regret analysis in Section 5 is carried out entirely in the continuous-time domain, and the proof of Theorem 6 uses tools specifically designed for continuous systems.\n\n\n\n\n>Q4: In the second figure of the Experiments section, the red line is flat by normalization, but was the regret also flat during the early exploratory phase? That seems a bit strange— the regret should increase rapidly at the beginning and then stabilize later, due to the exploration then commit.\n\n**A4:** We thank the reviewer for the insightful comment. The reason the red curve appears flat is due to the structure of the regret, which consists of two main phases: exploration and exploitation. The exploration phase incurs a large, dominant regret of order $O(\\sqrt{T})$. Crucially, this regret is accumulated over a very short period relative to the total time horizon $T$. On the plot, this brief but steep increase is visually compressed into what appears as a large, near-vertical jump at the very beginning. This initial jump establishes a high baseline for the cumulative regret. Consequently, the subsequent, much slower growth during the exploitation phase appears negligible in comparison, rendering the overall curve relatively flat.\n\n\n>Q5: The proposed method relies on a known stable controller for an unknown system, which seems contradictory. In an unknown environment, obtaining a stable controller typically requires some form of exploration or trial-and-error. This paper essentially ignores the impact of that exploration phase on the overall finite-sample analysis. If we include the sampling used for exploration, is it still possible to achieve sub-linear finite-sample regret? \n\n**A5:** We thank the reviewer for the thoughtful question. First, the assumption of a known stabilizing controller is made for simplicity. As discussed in our manuscript (particularly in Section 4.4), a stabilizing controller can also be obtained by estimating system parameters using multiple independent short trajectories. This procedure effectively serves as an exploration phase.\n\nWe now evaluate the regret incurred during this exploration phase. From Theorem 5, we know that with $\\mathcal{O}(\\kappa_A^2 \\kappa_B^2 (d + p) \\gamma^{-2} \\log T)$ independent trajectories, we can ensure, with probability at least $1 - T^{-10}$, that the estimation error $\\Vert\\hat{A} - A\\Vert + \\Vert\\hat{B} - B\\Vert$ is at most $\\gamma$. By choosing $\\gamma$ to be the stability margin, we can guarantee that the controller computed for $(\\hat{A}, \\hat{B})$ also stabilizes the true system $(A, B)$ with high probability.\n\nFrom Assumption 2 in our paper, we know that each trajectory has a $T' = \\mathcal{O}(1)$ run time. From the state transition formula (line 428), we have\n$$\nX_{t}=\\int_{s=0}^{t}e^{A(t-s)}(BU_{s}ds+dW_s) ,\n$$ \nand it follows that $\\mathbb{E}[\\Vert X_{t}\\Vert^{2}_{2}]\\leq e^{2\\Vert A\\Vert T'}\\cdot(1+\\Vert B\\Vert^{2})T'h$. Hence, the expected cost per trajectory is at most$$\\mathcal{O}\\left(e^{2\\Vert A\\Vert T'}\\cdot (1+\\Vert B\\Vert^{2})(\\Vert Q\\Vert +\\Vert R\\Vert)T'\\right),$$which is $\\mathcal{O}(1)$ and independent from the total run time $T$ in regret analysis.\n\nCombining this with the number of required trajectories, we conclude that the total cost of the initial exploration phase is sublinear in $T$. Therefore, the overall regret, including this phase, remains sublinear. We thank the reviewer again for raising this important question and will revise the manuscript accordingly to include this analysis.\n\nWe thank the reviewer once again for the valuable and helpful suggestions. We would be happy to provide further clarifications if the reviewer has any additional questions.\n\n\n**References**\n\n[1] Faradonbeh, Mohamad Kazem Shirani, and Mohamad Sadegh Shirani Faradonbeh. \"Online Reinforcement Learning in Stochastic Continuous-Time Systems.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[2] Shirani Faradonbeh, Mohamad Kazem, Mohamad Sadegh Shirani Faradonbeh, and Mohsen Bayati. \"Thompson sampling efficiently learns to control diffusion processes.\" Advances in Neural Information Processing Systems 35 (2022): 3871-3884."}, {"review_id": "ac3rfE71xo", "reviewer": "Reviewer_ZczL", "summary": "The paper studies continuous time linear dynamical systems and makes the following contributions. Firstly, for the system identification problem with time horizon $T$, and assuming that the system is stable, an algorithm is obtained that achieves an estimation error of  $O(1/\\sqrt{T})$ with only $O(T)$ samples. This method is also shown to be optimal up to constant factors. When a stabilizer is not known in advance, it is shown that $N$ independent short trajectories can be used  to obtain an estimate with error $O(1/\\sqrt{N})$. These results lead to an online continuous linear control algorithm which is shown to achieve $O(\\sqrt{T})$ regret.", "questions": "1. I do not see the dependence on the dimensions of $A,B$ appearing in the results, is this hidden inside the constant terms? If so, then I think it would be more clear if this could be explicitly shown. For discrete-time autonomous linear systems (with B = 0), we know that $T$ needs to be of the order $poly(n)$ where n is the dimension of $A$. Is it the same  for continuous time systems?\n\n2. The system identification results require A to be stable. For discrete time autonomous linear systems, recent results have shown that consistent identification is possible even when the spectral radius of A is only required to be less than or equal to 1. Is it possible to use those techniques here as well?", "limitations": "Yes these have been discussed towards the end", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros\n---------\n\n1.  The paper is written well overall with a clearly defined problem, notation, and summary of existing works. The writing is clear for the most part, and makes it easy to follow the ideas. \n\n2.  The technique used for the system identification part (Alg. 1) seems quite natural, but it’s still non-trivial to carry out the full error analysis. The results are overall substantial, as upper and lower bounds are provided for system identification, along with an algorithm for online control. To my knowledge, these results appear to be novel as most recent works have addressed discrete-time linear systems. I think the results would be of interest for researchers working in this domain.\n\nCons\n---------\n\nIt would have been helpful to provide the full dependence on the problem parameters in the statements of the theorems/lemmas. For e.g., in Theorem 2, $T$ is required to be polynomial in the parameters, but it would be worth displaying the actual dependence (hiding only the absolute constants). This is the case in other statements as well.\n\nI also have some other questions which are separately outlined below.", "was_revised": true, "final_justification": "The authors have clarified all the technical questions I had related to some parts of the paper. I am satisfied with the response and believe the paper is a good theoretical contribution towards the problem of learning continuous-time linear dynamical systems", "rebuttal": "We extend our gratitude to the reviewer for the constructive suggestions and questions. We address the reviewer's concerns belows:\n\n>Q1: It would have been helpful to provide the full dependence on the problem parameters in the statements of the theorems/lemmas. For e.g., in Theorem 2, $T$ is required to be polynomial in the parameters, but it would be worth displaying the actual dependence (hiding only the absolute constants). This is the case in other statements as well.\n\n**A1:**  We thank the reviewer for the helpful suggestion. The dependencies on problem parameters in our theorems and lemmas are indeed polynomial, all with degrees less than 5. In the current version, we presented simplified statements in the main text. In the next revision, we will revise the main theorems to explicitly include the parameter dependencies to improve clarity and completeness.\n\n>Q2: I do not see the dependence on the dimensions of $A, B$ appearing in the results, is this hidden inside the constant terms? If so, then I think it would be more clear if this could be explicitly shown. For discrete-time autonomous linear systems (with $B=0$), we know that $T$ needs to be of the order $\\text{poly}(n)$ where $n$ is the dimension of $A$. Is it the same for continuous time systems?\n\n**A2:** We thank the reviewer for the question. Regarding the dependence on the dimensions of $A \\in \\mathbb{R}^{d \\times d}$ and $B \\in \\mathbb{R}^{d \\times p}$, we assume $p \\geq d$ to ensure the existence of a stabilizing controller. The required sample length $T$ is not simply a low-degree polynomial in $d$ and $p$, but must satisfy $T \\geq \\mathcal{\\Omega}((d + p) \\cdot h)$, where $h$ is the sampling interval. This ensures that the system parameters can be reliably recovered. In practice, $T$ should also be sufficiently large to guarantee small estimation errors. We agree that making the dimensional dependence more explicit would improve clarity, and we will revise our manuscript in the next version accordingly.\n\n\n>Q3: The system identification results require $A$ to be stable. For discrete time autonomous linear systems, recent results have shown that consistent identification is possible even when the spectral radius of $A$ is only required to be less than or equal to $1$. Is it possible to use those techniques here as well?\n\n\n**A3:** We thank the reviewer for the insightful question. Our approach establishes a bridge between continuous-time and discrete-time linear systems, which allows certain techniques developed for discrete-time settings to be adapted to the continuous-time case.\n\nTo clarify the relationship: in the continuous-time system $$dX_{t}=AX_{t}dt+Bu_{t}dt+dW_{t}.$$ \n\nThe sign of $\\text{Re}(\\lambda(A))$ corresponds to different regimes in discrete-time systems. Specifically:\n\n$\\text{Re}(\\lambda(A)) < 0$ corresponds to a discrete system with spectral radius strictly less than 1 (i.e., stable),\n\n$\\text{Re}(\\lambda(A)) = 0$ corresponds to marginal stability (spectral radius 1),\n\n$\\text{Re}(\\lambda(A)) > 0$ corresponds to instability (spectral radius greater than 1).\n\nIn our analysis, the asymptotic convergence rate remains the same across these regimes, up to constant factors, provided the system remains controllable and observable. Thus, while we assume stability for simplicity and to align with standard assumptions in continuous-time identification, we believe our framework could be extended to accommodate marginally stable systems by incorporating techniques from recent discrete-time literature.\n\n\nFinally, we thank the reviewer once again for the effort in providing us with valuable suggestions. We will continue to provide clarifications if the reviewer has any further questions."}]

Author rebuttal:

Meta-review: This paper considers control and identification of continuous time linear systems, which however may only be observed at discrete points in time. Here, one must decouple the number of observations allowed (N) from horizon (T). The first result is that the lower bound on the estimation error scales as 1/T^1/2 even if the number of observations is allowed to scale arbitrarily. This is largely a comment about the sampling model/oracle being appropriate. With nonstandard sampling models, some past results can learn a system from arbitrary T by increasing N. The work also provides a 1/T^1/2 accurate estimator of the system matrices given N=O(T) observations. Here the main novelty is correctly inverting the discretization of induced discrete-time linear system, whereas the tradition first-order approximation results in N=T^3/2. The control result is relatively less impressive, improving upon past work by logarithmic factors, by essentially a consequence of the estimation result.

This paper has unanimous support from all reviewers. So we are happy to recommend to accept this paper.
Decision: Accept (poster)