On the Sample Complexity of Stabilizing LTI Systems on a Single Trajectory
Authors: Yang Hu
Adam Wierman
Guannan Qu
Venue: NeurIPS 2022 Accept (2022)
Keywords: linear time-invariant systems
sample complexity
stability
learning-based control

Abstract: Stabilizing an unknown dynamical system is one of the central problems in control theory. In this paper, we study the sample complexity of the learn-to-stabilize problem in Linear Time-Invariant (LTI) systems on a single trajectory. Current state-of-the-art approaches require a sample complexity linear in $n$, the state dimension, which incurs a state norm that blows up exponentially in $n$. We propose a novel algorithm based on spectral decomposition that only needs to learn ``a small part'' of the dynamical matrix acting on its unstable subspace. We show that, under proper assumptions, our algorithm stabilizes an LTI system on a single trajectory with $O(k \log n)$ samples, where $k$ is the instability index of the system. This represents the first sub-linear sample complexity result for the stabilization of LTI systems under the regime when $k = o(n)$.

On the Sample Complexity of Stabilizing LTI Systems on a Single Trajectory
Yang Hu SEAS, Harvard University Massachusetts, USA
Adam Wierman
CMS, California Institute of Technology California, USA
yanghugg www.aaaradd.....
adam@calteech.edi
Guannan Qu
ECE, Carnegic Mellon University
Pennsylvania, USA
gqu@andrew cmu. cmu.edu
Abstract
Stabilizing unknown dynamical system is one of the central problems in con- trol theory. In this paper, we study the sample complexity of the learn-to-stabliize problem in Linear Inveriavariant (LTT) systems tfate-of-the-aa approaches require sample complexity linear in n, the state di- mension, which incurs state norm that blows up exponentially in We propose a novel algorithm based on spectral decomposition that only needs to learn "a small part" of the dynamical matrix acting its unstable subspace. We show that, under proper assumptions, our algorithm stabilizes an LTI system on single trajectory with Ok log n) samples, where & is the instability index of the system. This represents the first sub-linear sample complexity result for the stabilization of LTI systems under the regime when k o(n).
single trajectory. Current
Introduction
Linear Time-Invariant (LTI) systems, namely T++1 = As, + Bu, where 2, E IR" is the state and ur R is the control input, are one the most fundamental dynamical systems control theory, and have wide applications across engineering, economics and societal domains. For systems with known dynamical matrices (A, B), there well-developed theory for designing feedback con- trollers with guaranteed stability. robustness, and performance [ 2]. However, these tools cannot be directly applied when (A, B) is unknown.
Driven by the success of machine learning 43, there has been significant interest learning- based (adaptive) control, where the learner does not know the underlying system dynamics and learns to control the system in an online manner, usually with the goal of achieving low regret [5
Despite the progress, an important limitation in this line of work is common assumption that the learner has a priori access to known stabilizing controller. This assumption simplifies the learning task, since ensures bounded state trajectory in the learning stage, and thus enables the learner to learn with low regret. However, assuming a known stabilizing controller is not practical, as stabi- lization itself is nontrivial and considered equally important any other performance guarantee.
To overcome this limitation, in this paper we consider the Ctarn-to-stabilee problem, i.e., learning to stabilize an unknown dynamical system without prior knowledge of any stabilizing controller.
"This work is supported by NSF Grants CNS-2146814, 14,, CPS-2136197, CNS-2106403, NGSDI-2105648, EPCN-215417 with additional support from Amazon AWS.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Understanding the Saurn-to-stablice problem is of great importance to the learning- based control literature, as it serves as a precursor to any learning-basee control algorithms that assume knowledge of stabilizing controller.
The learn-to-stabilize problem has attracted extensive attention recently. For example, 14 and [5] adopt a model-based approach that first excites the open-loop system to learn dynamical matrices (A, 13), and then designs a stabilizing controller, with sample complexity scaling linearly in n, the state dimension. However, a linearly-scaling sample complexity could be unsatisfactory for some specific instances, since the state trajectory still blows up exponentially when the open-loop system is unstable, incurring a 20(") state norm, and hence a 2 regret (in LQR settings, for example). Another recent work [16] proposes a policy-gradient-
discount annealing method that solves a series of discounted LQR problems with increasing discount factors, and shows that the control policy converges to near-optimal policy. However, this model-free approach only guarantees poly(n) sample complexity. In fact, to the best of our knowledge, state-of of-teoff-the-at learn-to-stabilinn algorithms with theoretical guarantees always incur state norms exponential in n.
has been shown in [T5) that all general-purpose control algorithms are doomed to suffer a worst- case regret of 2(((m) This result is intuitive, since from an information- -tttorrnt perspective, a complete recovery of A should take (n) samples since A itself involves n. parameters. However, this does not rule out the possibility that we can achieve better regret in specific systems. Our work motivated by the observation that it is not always necessary to learn the whole matrix A to stabilize an LTI system. For example, if the system is open-loop stable, we do not need to learn anything to stabilize it. For general LTI systems, it is still intuitive that open-loop stable "modes" exist and need not be learned for the learn-to-stabilia problem. So, we focus on learning a controller that stabilizes only the unstable "modes", making it possible to learn stabilizing controller without exponentially exploding state norms. The central question of this paper is:
Can we exploit mastance-specifte properties of an LTT system to learn to stabilize it on a single trajectory, without incurring a state norm exponentially large in n?
Contribution. In this paper, we answer the above question by designing an algorithm that stabilizes an LTI system with only O log n2) state samples along single trajectory, where le is the instability index of the open-loop system and is defined as the number of unstable "modes" (i.e., eigenvalues with moduli larger than 1) of matrix A. Our result significant in the sense that k can be consid- erably smaller than for practical systems and, in such cases, our algorithm stabilizes the system using asymptotically fewer samples than prior work; specifically, it only incurs a state norm (and regret) in the order of 20 (og n), much smaller than 20(n) of prior state of the art when ie < n.
To formalize the concept of unstable "modes" for the presentation of our algorithm and analysis, formulate a novel framework based on the spectral decomposition of dynamical matrix A. More specifically, we focus on the unstable subspace En spanned by the eigenvectors corresponding to unstable eigenvalues, and consider the system dynamies "restricted" to it states are orthogonally projected onto Eu, and we only have to learn the effective part of A within subspace En. which takes only Okk) samples. The formulation is explained in detail in Section [.1 and Appendix [A] We comment that this idea of decomposition is in stark contrast to prior work, which in one way or another seeks to learn the entire (or other similar quantities).
Related work. Our work contributes to and builds upon related works described below.
Learning for control assuming known stabilizing controllers. There has been large literature on learning-basee control with known stabilizing controllers. For example, one line of research utilizes model-free policy optimization approaches to learn the optimal controller for L.T systems (577 17 30 All of these works require a known stabilizing controller as an initializer for the policy search method. Another line of research uses model-based methods, i.c.. learning dynamical matrices (A, B) first before designing a controller, which also require a known stabilizing controller (c.g., B1-)9)). ). Compared to these works, we focus on the learn-to- -ttt-to-ttabilize problem without knowledge of an initial stabilizing controller, which can serve as a precursor to existing cearning-for-conten works that require known stabilizing controller.
Learning to stabilize on a single trajectory. Stabilizing linear systems over infinite horizons with asymptotic convergence guarantees is a classical problem that has been studied extensively in wide range of papers such as 42] On the other hand, the problem of system stabilization over finite horizons remains partially open and has not seen significant progresses. Algorithms incurring

---

20(m) regret have been proposed in settings that rely on relatively strong assumptions of controllability and strictly stable transition matrices [3 43 which has recently been improved to 20()) + (ppoll(())))))) 'T) [4
Another model-based approach that merely assumes stabilizability introduced in [4]] though it does not provide guarantees on regret or sample complexity. A more recent model-free approach based on policy gradient [16] provides a novel perspective into this problem, yet can only guarantee poly(n) sample complexity. Compared these previous works, our approach requires only Olk log n)) samples, incurring a sub-exponential state norm.
Another recent work [45 proposes to do partial system identification via projecting the state onto lower-dimensional subspace, which is similar in intuition with our work. However, the problem con- sidered there is system stabilization with fixed initial state Zo. and their approach only eliminates the unstable component along that specific trajectory in k steps when zo lies in a k-dimensional sub- space. In contrast, our approach finds stabilizing controller for the system with sub-linear sample complexity along an arbitrary trajectory regardless of the initial state.
Learning to stabilize multiple trajectories. There are also works 12 46 that do not assume known stabilizing controllers and learn the full dynamics before designing an optimal stabilizing controller. While requiring ((n) samples which is larger than (k) of our work, those approaches do not have the exponentially large state norm issue they allow multiple trajectories; i.e. the state can be "reset" to so that won't get too large. In contrast, we focus on the more challenging single-trajectory scenario where the state cannot be reset.
System Identification. Our work is also related to the system identification literature, which focuses on learning the system parameters of dynamical systems, with early works like [47] focusing on asymptotic guarantees, and more recent works such as [48 focusing on finite-time guarantees. Our approach also identifies the system (partially) before constructing a stabilizing controller, but we only identify a part of A rather than the entire A.
2 Problem Formulation
We consider a noiseless LTI system Fe+1 = Arx + But, where Ia E R² and us E R are the state and control input at time step 1, respectively. The dynamical matrices A Raxn and B E Raxm are unknown to the learner. The learner is allowed to learn about the system by interacting with it on a single trajectory - the initial state is sampled uniformly random from the unit hyper-sphere surface in R", and then, at each time step f. the learner is allowed to observe Ie and freely determine Ur. The goal of the learner is learn stabilizing controller, which is defined follows.
Definition 2.1 (Stabilizing Controller). Control rule u, = fe( Tr-1.-.. 220) is called stabiliz- ing controller if and only the closed-loop system T++1 Ax, + Bu, is asymptotically stable; i.e., 0 is guaranteed in the closed-loop system.
for any To E R", lim arlll
To achieve this goal, simple strategy is to let the system run in open loop to learn (A, B) via least squares, and then design a stabilizing controller based on the learned dynamical matrices. However, as has been discussed in the introduction, such simple strategy inevitably induces exponentially large stage norm that is potentially improvable A possible remedy for this is to learn "a small part" of (A, B) that is crucial for stabilization. Driven by such intuition, the core problem of this paper is to characterize what is the "small part" and design an algorithm to learn it.
Note that, although it is common to include an additive disturbance term in the LTI dynamics, the introduction of stochasticity does not provide additional insights into our decomposition- algorithm, but rather, merely makes the analysis more technically challenging. Therefore, here we simply omit the noise in theoretical results for the clarity of exposition, and will show by numerical experiments that our algorithm can also handle disturbances (see Appendix Hy.
Notation. For E C. |2| the modulus of 2. For a matrix A E R AT denotes the transpose of A: ||A|] is the induced 2-norm of A (equal to its largest singular value), and mmin (AA) is the smallest singular value of A; when A square, p( A) denotes the spectral radius of A, and (A) denotes the condition number of the matrix consisting of A's eigenvectors as columns. The space spanned by
Mooee sophisticated exploration strategies might be adopted to leam (A, B) B3 15 44 but as long as the control inputs do not completely cancel out the "dominant part" of the states, the above intuition still holds to a large extent as the 'dominant part" of the state is still blowing up exponentially.
3

---

{ui,-.. " two subspaces U, V of IR", U- is the orthogonal complement of U, and U @ V is the direct sum of U and V. The zero matrix and identity matrix are denoted by respectively.
} is denoted by span(U1,... Up), and the column space of A is denoted by col(A). For
3 Learning to Stabilize from Zero (LTS))
The core of this paper is a novel algorithm, Learning to Stabilize from Zero (LTSg). that utilizes a decomposition the state space based characterization of the notion of unstable "modes". The decomposition and other preliminaries for the algorithm are first introduced in Section 3.1 and then proceed describe LTSg in Section 3.2
3.1 Algorithm Preliminaries
We first introduce the decomposition of the state space in Section 3.1.1 which formally defines "small part" of A mentioned in the introduction. Then, introduce 7-hop control in Section B.1.2. so that we can construct a stabilizing controller based only on the "small part" of (as opposed to the entire A). Together, these two ideas form the basis of LTSg-
3.1.1 Decomposition of the State Space
Consider the open-loop system T++1 Ar,. Suppose that diagonalizable, and let "1, An denote the eigenvalues of A, which are assumed to be distinct and satisfy
| 2 Aal 2
| > |A++
We define the eigenspaces associated these eigenvalues: for real eigenvalue X; R corre- sponding to eigenvector v E RR,, we associate with a 1-dimensional space E; span(e;) for a complex eigenvalue X; C IR corresponding to eigenvector v; C", there must exist some j such that X = > (corresponding to eigenvector Bj = ūz), and we associate with them a 2-dimensional space F, F, = span((1; ((1; ú.), i(u; ú:)). Further, define the unstable subspace F., Digk Fg and stable subspace Eg : + E,
As discussed earlier, we only need to learn "a small effective part" of associated with the un- stable "modes". the unstable eigenvectors of A. For this purpose, in the following formally define a decomposition based on the orthogonal projection onto the unstable subspace Eg, This decomposition forms the foundation of algorithm.
The Eu + E decomposiiionn Suppose the unstable subspace E, and its orthogonal complement E are given by orthonormal bases P1 E Bunk and P2 E [n= respectively, namely
E = col(P:), E = (22.
Let P= [Pr Pa), which also orthonormal and thus p-1 PT = P Pa]T. For convenience, let II : and II, P2P be the orthogonal projectors onto E,, and E,I respectively. With the state space decomposition, we proceed to decompose matrix A. Note that F., is invariant subspace with regard to A (but Ey not necessarily is), there exists M1 E kg A A [k and M2 E (===-))((=-), such that
Mi
A M2
M
AP
M
PP M2
In the decomposition, the top-left block M1 R represents the action of A on the unstable subspace. Matrix M1. together with P1. is the "small part" we discussed in the introduction. Note that M, (Pi) is only k-by-k (n-by-k) and thus takes much fewer samples to learn compared to the entire A. It is also evident that Mj inherits all unstable eigenvalues of A, while M2 inherits all stable eigenvalues. Finally, we provide the system dynamics in the transformed coordinates. Let y [v] 1 be the coordinate representation of in the basis formed by column vectors of P (i.e., x Py). The system dynamics in y-coordinates is
|1.+1
= P
V1,t
+ P-1 Bu,
M1
A M2
V1, V2.4
+
P P
u:-
(I)
12,1+1
V2.1
The E, + Ee-cccooooiiiinn.. In the above E, 4 F. -eccoooopoiiiion, Fy in general not an invariant subspace with respect to A. This can be seen from the top-right 4 block in M, which

---

represents how much of the state is "moved" by A from E into Eu in one step. The absence of invariant properties in F is sometimes inconvenient in the analysis. Hence, we introduce another invariant decomposition that used in the proof as follows. Specifically, R" can be naturally decom- posed into Eu + Es. and further both En and Es are invariant with respect to A. We also represent
E. = (Q)(Q1) and E. col(Q2) by their orthonormal bases, and define Q = [ Q2]. Note that, these two subspaces are generally not orthogonal, so additionally define Q =: [R] R Details are deferred to Appendix[A.]
Lastly, we comment that when A is symmetric, the Fy ( F and E., @ Fe-decompoosiions are identical because - = E in such symmetric cases. While E * E' in general cases, the "close- ness" between E and Eg also contributes to the sample complexity bound in Section 4 For that reason, we formally define such "closeness" between subspaces in Definition 3.1 We point out that the definition has clear geometric interpretations and leads to connections between the bases of Eg and E which is technical and thus deferred to Appendix A.2
Definition 3.1 (f- (g-Close Subspaces). For & E (0, 1}, the subspaces E, col(P2), Es col(Q2)
are called É-close to each other, if and only if T (P2 Q2) > -.
3.1.2 h-hop Control
This section discusses the design of controller based only on the "small part" of A, i.e., the P and M1 matrices discussed in Section 3.1.I as opposed to the entire A matrix. Note that the main objective of this subsection is to introduce the idea of our controller design when M1 and Pi are known without errors, whereas in Section 3.2 we fully introduce Algorithm|] I that learns M1 and Pi before constructing the stabilizing controller.
As discussed in Section 3.1.1 we can view M1 as the "restriction" of A onto the unstable subspace Eu (spanned by the basis in P1) and it captures all the unstable eigenvalues of A. Since only M1 and P1 are known while M2 and P2 are unknown, a simple idea is to "restrict" the system trajectory entirely to E, such that the effect of A is fully captured by M1. the part of A that is known. However, such a restriction is not possible because, even if the current state T, is in F, (so Az; also F.,), Tz-1 Ax; + Bu, is generally not in Fy with non-zero u4. To address this issue, recall that desirable property of the stable component is that it spontaneously dies out in open loop. Therefore, propose the following r-hop controller design, where the control input is only injected every T steps - in this way, we let the stable component die out exponentially between two consecutive control injections. Consequently, when we examine the states every steps, we could expect that the trajectory appears approximately "restricted to" the unstable subspace E
E N. Let = var and ü, == Usr to be the state and input every T time steps. We can write the dynamies of the r-hop control system as ēz+1= = AT R. + Bü, We also let ÿs to denote the state under E., @ F decomposition, i.c. U= = PP Z.. Then the state evolution can be written as
More formally, a r-hop controller only injects non-zero u, for / =
N1,0+1 12,,++1
= 1-11-110 A
y2.s
PP -P--A---AA Bū, = M
V1 y2,
+
P A
[P
A 1 B
A
B
(2)
where we define B, == P.T A
B for simplicity, and
M = Mi
+ 0
P
A
MT ELD M MJ
MI
4.
M2
=:
M5
Now we consider a state feedback controller ū, = -Ki in the T h-hop control system that only acts on the unstable component s1,,, the closed- dynamics of which can then be written as
jo-1 M PTT - BK,
A-
V..
33)
PS BKi
Mj
In (3, the bottom-left block becomes P. AT-IKK,,, which is exponentially small in 7. Therefore, with a properly chosen T, the closed-loop dynamical matrix in (3) is almost block-upper-triangula
with the bottom-right block very close to (recall that M, is a stable matrix). As a result, if we select K₁ such that MT + P, A BK1 is stable, then (3) will become stable as well. There are different ways to select such K₁. and in this paper, we focus on the simple case that B is an n-by-k matrix and P.T A B is an invertible square matrix (see Assumption 4.3' in which case selecting
K1 - A B) '
(4)
5

---

will suffice. Note that such controller design will also need the knowledge of P/ ATA-B has the same dimension as M1 (a k-by-k matrix) and takes only (kk) additional samples to leam. For the case that B is not n-by-k: similar controller design can be done (but in a slightly more involved way), and we defer the discussion to Appendix C
B, which
We also point out that, for the case where A is symmetric, selecting 7 = should work well. This because A,
in (3) for the symmetric case, and therefore, the matrix in (3) will be triangular even for 7 = 1. This will result in a simpler algorithm and controller design, and hence a better sample complexity bound, which we will present as Theorem 4.2 in Section
We end this subsection with some comments on the role of r-hop stabilizing controllers. One may wonder if the controller design proposed here would be compatible with many downstream tasks, since the closed-loop system stabilized by a 7-hop controller will still experience periodical fluctua- tions in state norms (although in bounded manner). However, we want to emphasize again that the r-hop controller can serve as a precursor to any online control algorithm that assumes a known sta- bilizing controller, which includes system identification from stable trajectories (see, e.g., [48] (50) and controller designs using the identified system. In this way the state norm fluctuation is only transient, and does not harm to the overall performance significantly.
3.2 Algorithm
Our algorithm, LTS,, is divided into 4 stages: (i) learn an orthonormal basis P1 of the unstable subspace E,, (Stage 1); (ii) learn M1, the restriction of onto the subspace Eu (Stage 2); (iii) learn B, = PT A B (Stage 3); and (iv) design a controller that seeks to cancel out the "unstable" Mi matrix (Stage 4). This is formally described as Algorithm I below.
Algorithm LTS:: Learning a 7-hop Stabilizing Controller
1: Stage I: learn the unstable subspace of A.
2: Run the system in open loop for to steps for initialization.
3: Run the system in open loop for k more steps and let D + [+oo+1 Ztotk]-
4: Calculate 17, <- D(D DT-1DT.
5: Calculate the top (normalized) eigenvectors .., .g of 17, and let PÚ x- [0] -.)..
6: Stage 2: approximate M1 on the unstable subspace.
7: Solve the least squares M1 < arg min Mi E ((Mi) = Listot1 || x1+1 - x.
totb
8: Stage restore B, for 7-hop control.
9: for + 1.... do
10: Let the system run in open loop for time steps.
11: Run for r more steps with initial ue, a | le,, where 4 = to + h + iw + (i - 1)T.
12: Let B, ( bx]. where the thh column b, t all || (PT D1,+T Mi PT 21.)-
13: Stage 4: construct a r-hop stabilizing controller K.
14: Construct the Thhop stabilizing controller K + 1
In the remainder of this section we provide detailed descriptions of the four stages in LTSg.
Stage 1: Learn the unstable subspace of A. It suffices to learn an orthonormal basis of E,. We notice that, when A is applied recursively, it will push the state closer to Eu. Therefore, when let the system run in open loop (with control input 4, = 0) for to time steps, the ratio between the norms of unstable and stable components will be magnified exponentially, and the state lies "almost" in E., As a result, the subspace spanned by the next k states, i.c. the column space of tk) is very close E,, This motivates us to the orthogonal projector
D = [xto+1 onto cD), namely II D(D -D as an estimation of the projector II, = P.P,T onto En Finally, the columns P1 are restored by taking the top & eigenvectors of ii, with largest eigenvalues (they should be very close to 1), which form basis of the estimated unstable subspace.
Stage 2: Learn M1 on the unstable subspace. Recall that M, is the "dynamical matrix" for the Eu Eu-component under the E, @ E,I decompositiin. Therefore, to estimate M1, we first calculate the coordinates of the states 4:do under basis Pi; that is, $1.0 P zc, for t to + I,..., to + k.

---

Then, we use least squares to estimate Mi, which minimizes the square loss over M1
Bottl
butt
((M))
l1
Mibi.el
Σ
P| Jx+1
2
(5)
(=f+1
1=/++1
can be shown that the unique solution to 5 is MI= AAP (see Appendix B
Stage 3: Restore B- for T-hop control. In this step, we restore the B, that quantifies the "effective component" of control inputs restricted Eu (see Section 3.1.2 for detailed discussion). Note that equation (2) can be rewritten in terms of V1,, as
V1,4+ = MMV1. + Ar32,1. + B,
Hence, for the purpose of estimation, we simply ignore the 4, term, and take the 7th column as
6
(P) xe,tr MPTTa.)
where ue is parallel to eú, and the magnitude of Ut, is set to be large enough as al| || amplify its effect so that the estimation error of A is comparatively negligible. Here we introduce an adjustable constant a guarantee that the commoomee still constitutes non-negligible proportion of the state after injecting U4,, so that the iterative restoration of columns could continue.
evident that the ignored A, PJ di, term will introduce an extra estimation error. Since 4, contains a factor of MT A that explodes with respect to r, this part can only be bounded if I| mx is sufficiently small. For this purpose, we introduce heat-up steps (running in open loop with 0 control input) to reduce the ratio to an acceptable level, during which time the projection of state onto E automatically diminishes over time since p(M2) | < 1.
I
Stage 4: Construet a r-hop stabilizing controller K. Finally, we can design a controller that cancels out MT in the r-hop system. As mentioned in Section 3.1.2 we shall focus on the case where is an n-by-k matrix for the sake of exposition (the case for general B will be discussed in Appendix C.. The invertibillity of B, can be guaranteed under certain conditions (Assumption 4.3' further, B, is also invertible as long as it is close enough to B,. In this case, the r-hop stabilizing controller can be simpliy designed K₁ - -B,'M; in y-coordinates where replace B, and Mj in (4) with their estimates. When we return to the original u-coordinates, the controller becomes K- = B- M P,T. Note that K (and K,) appears with a hat to emphasize the use of estimated projector P1, which introduces an extra estimation error to the final closed-loop dynamics.
It is evident that the algorithm terminates in + k[1 + + r) time steps. In the next section, show how to choose the parameters to guarantee both stability and sub-linear sample complexity.
Finally, we remark that, although for the ease of exposition we have assumed here the instability index known, it is fine to use an estimate of that is larger than its true value in practice i.e, the algorithm still outputs a stabilizing controller since the performance analysis only relies on the ratio between cigenvalues and the stability of AR+1, and the complexity only suffers little if the guess of k is close to its true value.
Stability Guarantee
In this section, we formally state the assumptions and show the sample complexity for the proposed algorithm to find stabilizing controller. Our first assumption is regarding the spectral properties of A, where we require all eigenvalues to appear without multiplicity (so that we can learn a com- plete basis of each eigenspace), and marginally stable eigenvalues (i.e., those with moduli 1) eliminated (so that eigenspaces are either stable or unstable). We would like to point out that it is common practice (c.g.. (50)) to discuss marginally stable eigenvalues separately, since it obscures the distinction between stable and unstable components and is thus technically challenging.
Assumption 4.1 (Spectral Property). is diagonalizable with instability index k with distinct eigenvalues X1, ... An satisfying |r1 2 Aae
|& > 1> D > ... 1nnl.
The assumption is mild the sense that matrices satisfying Assumption 4.1 are dense Raxx, and our final complexity bound only depends logarithnically on the condition number of eigenvectors
7

---

(A( and the eigen-gap gap A1e A (see Theorem 4.1 and the discussion below). Thus any matrix A that violates Assumption 4.1 can be handled via small perturbations.
Our second assumption is regarding how to choose the initial state, which again is standard. The ini- tialization must be randomized eliminate the coincidence where zo has zero (oblique) projection onto some eigenvector v/ in which case we cannot learn about e and thus D is not invertible.
Assumption 4.2 (Initialization). The initial state of the system is sampled uniformly at random on the unit hyper-sphere surface in I.
Lastly, we assume the system to be (d, σ) )tttonngyy controllable, which is standard in literature. Assumption 4.3 (VV,0) --Stoong Controllability). The system is (v, a) --strongyyy controllable: i.e., miin (C,) > where Cv == [A--1B 2 ... AB B] is the v-step controllability matrix.
Above are all the assumptions we need. However, we remind the readers that, when we introduce the 7-hop controller design in Section 3.1.2] B is assumed to have & columns and certain assumptions are needed to guarantee the invertibility of B₁. Indeed, for the ease of exposition, we first consider this special case in presenting Assumption 4.3' regarding the controllability within the unstable subspace E, instead of the more general Assumption 4.3 (recall that R2 is defined in the En @ Ex-decomposition in Section T.I.T.
main result (Thcorem[4.. 4.1) below, where we impose the following
Discussions on how to handle the more general Assumption 4.3 case (where Assumption 4.3 holds) are deferred to Appendix
via a transformation to the special
Assumption 4.3' (c-Effective Control in Unstable Subspace), B E BRaK - (iiin(B > c|
Note that Assumption 4.3' has clear intuition - every direction in the unstable subspace receives at least proportion of from the influence of any control input. This assumption is reasonable in that, if amin (R, B) Rs O, the control input u has to be very large to push the state along the direction corresponding to the smallest singular value, which could induce excessively large control cost. We can also interpret the lower bound on miin R2 B) as a special case of Assumption 4.3 (i.e., Bl)) controllablility). Details can be found in Appendix C
In the following we present the main performance guarantees for our algorithm.
Theorem 4.1 MMain Theorem). Given noiseless LTI system Tt+1 Axx + Bu, subject to As-
sumptions 4.1 4.2 and 4.3' and additionally |>+1212 < | by running LTS, with parameters == 011), w = ( (fg k)), a = 0(1), to = Olglogn)
O (k log n) time steps, the closed-loop system is exponen- tially stable with probability 1- Olk over the initialization of no for any E N. Here the big-O notation only shows dependence on ks and n, while hiding parameters like Da1) [Ael. [ ||Al],
that terminates within to +k
c, a, E (recall that F.y and F,g are E-close), x(f..) (see Lemma D.1 and (+)) (see Lemma and details can be found in equations 41 through 466.
G.I
Theorem 4.1 shows the proposed LTSp algorithm can find stabilizing controller in Ö(k) steps, which incurs state norm of 20()), significantly smaller than the state-of-the-art 29(() in the k < regime. We would like to point out that this does not violate the lower bound shown in [15), since the state norm degenerates to ( when k = (n). and might degrade arbitrarily for systems with adversarially designed parameters. Still, for a large proportion of systems with is < and favorable constants, our algorithm achieves better performance than the naive ones. The theoretical result is also verified by numerical experiments, the details of which can be found in Appendix H
Discussion on constants. Curious readers can refer to Appendix (cquations (4T) through (46) for detailed expressions of the constants hidden behind the big-O notation in the theorem; Table also summarizes all instance-specific constants appearing in the bound. Here we provide brief overview how the bound depends on the system parameters. It is evident that, for a system with larger & (i.e., when F, and E, are "less orthogonal" to each other) or smaller e (i.e., when it costs more to control the unstable subspace), we a larger in (4I), smaller a in (43). and larger to and in (45) and (46). respectively, which altogether incur a larger constant term in the sample complexity. This is in accordance with our intuition of the state space decomposition and Assumption 4.3' respectively.
The bound also relies heavily on the spectral properties of A. The constraint |> 2 PP < [ ensures validity of (41). which is necessary for cancelling out the combined effect of non-orthogonal
8

---

subspaces Eu and E, (resulting in 4, in the top-right block) and inaccurate basis P1 (resulting in projection error in the bottom-left block) - a system with larger ratio |^1 A suffers from more severe side-effects, and thus requires larger 7 and higher sample complexity. Nevertheless, we believe that this assumption not essential, and we leave future work to relax
Another important parameter is the eigen-gap stable and unstable components become separable in magnitude when the system runs in open loop, which is utilized in the to initialization steps of Stage I and w heat-up steps of Stage 3. Consequently, a system with smaller aagengga Ax // | requires a larger to (see (10) and (see (46) and therefore higher sample complexity.
around 1 that determines how fast the
The condition number of cigenvectors Ke (A) also contributes to the bound of to. the number of initialization steps. It is intuitive that, a large Re(A) (A) indicates less orthogonal eigenspaces, which in turn requires a more distinct separation among the magnitudes of different eigen-components of Stg so that the stable components interfere less with the unstable ones.
Finally, we would like to point out that all these quantities appear in the bound logarithmic terms, indicating that the sample complexity only degrades mildly when the constants become worse.
A warm-up case. Despite the generality of Theorem 4. its proof involves technical difficulties. In Theorem 4.2 we include results for the special case where is real symmetric, which leads to simpler choice of algorithm parameters and a cleaner sample complexity bound.
Theorem 4.2. Given a noiseless LTI system T++1 Au, + Bu, subject to Assumplions 4. 4.2
and 4.3" with symmetric A, by rumning LTSg with parameters T = 1, w = 0, O(k log n) that terminates within to + + +11+## +7) O log n) time steps, the closed-loop system exponentially stable with probability over the initialization of ag. Here the big-O notation only shows dependence on k and while hiding parameters like AAg Ddel (4kta), |||], [[]], c, and
to
x(,)) (see Lemma D.1 and details can be found in equation
18
Although Theorem 4.2 takes simpler form, its proof still captures the main insight of our analysis. For this reason, we use the proof of Theorem 4.2 as a warm-up example in Appendix before we present the proof ideas of the main Theorem
Proof Outline
In this section we will give high-level overview of the key proof ideas for the main theorems. The full proof details can be found in Appendices F and as indicated below.
Proof Structure. The proof is largely divided into two steps. In Step 1, we examine how accurate the learner estimates the unstable subspace E, Stage and 2. We will show that Ih, Pi and Mi can be estimated up to an error of 8 within 4 O(k log n - log 8) steps. In Step 2, we examine the estimation error of Mj and B, in Stage 2 and 3 (and thus K based which will eventually show that the r-hop controller output by Algorithm makes the system asymptotically stable. The proof is based on a detailed spectral analysis of the closed-loop dynamical matrix.
Overview of Step 1. To upper bound the estimation emrors in Stage and 2, we only have to notice that the estimation error of !/, completely captures how well the unstable subspace is estimated, and all other bounds should follow directly from it. The bound on ||,, 1I, is shown in Theorem 5.1
together with a bound on I Pi presented in Corollary 5.2
Theorem 5.1. For noiseless linear dynamical system Zi+1 Ax,, let E, be the unstable subspace of A, k dim En be the instability index of the system, and IT be the orthogonal projector onto subspace F,. Then for any e > O, by running Stage of Algorithm 7 an arbitrary initial state that terminates in (Fa + k) time steps, where
k &logn - logg + log (A())
to 0
[Avl 2 2 Tattal
the matrix DJ D is invertible with probability (where D [xto+1 F(o+&)) and in such cases we shall obtain an estimated fI, D(D (DDDD)-11 DT with error [|
II1ll <.

---

Corollary 5.2. Under the premises of Theorem 5.1 for any orthonormal basis P1 of coo((ff) (where II is obtained by Algorithm [], there exists corresponding orthonormal basis P1 of col((H)),, such that [|P] Pi 2 =: M| M1 || < A|
The proofs are deferred to Appendix E due to limited length.
Overview of Step 2. To analyze the stability of the closed-loop system, we shall first write out the closed-loop dynamics under the -hoop controller. Recall in Section 3.122 we have defined ū, Exs Us to be the control input, state in z-coordinates, and state in y-coordinates in the r-hop control system, respectively. Using these notations, the learned controller can be written as
u = KH, P.P.TPp Pū. = [ Pi K2P P2
Us
in g-coordinates (as opposed to K( Therefore, the closed-loop 7-hop dynamics should be A, + A AT P2 M + P3 PP
M + BR Pi y
V1.a [2..
L,ge.
(6)
Ps PT
and we will show it to be asymptotically stable (i.e., p(L.)) < 1). Note that L,, is given by a 2-by-2 block form, we can utilize the following lemma to assist the spectral analysis of block matrices, the proof of which is deferred to Appendix
Lemma 5.3 (Block Perturbation Bound). For 2-by-2 block matrices = the spectral radii of A and A + differ by at most (p(A + E) p(A) S ((A + E where x(A E) is a constant (see Appendix D
E
Em F
Az
E12 E21
The above lemma shows clear roadmap for proving p(L.) 1. First, need to guarantee stabil- ity of the diagonal blocks - the top-left block stable because K2 is designed to (approximately) eliminate it to zero (which requires the estimation error bound on B-), and the bottom-right block stable because is almost M3 with negligible error induced by inaccurate projection. Then, we need to upper-bound the norms of off-diagonal blocks via careful estimation of factors appearing in these blocks. Complete proofs for both cases can be found in Appendices and G respectively.
6 Conclusions
This paper provides new perspective into the learn-to-stabilizz problem. We design novel al- gorithm that exploits instance-specific properties to learn to stabilize an unknown LTT system on a single trajectory. We show that, under certain assumptions, the sample complexity of the algorithm is upper bounded by O(k Olglog log which avoids the 29(1) state norm blow-up of existing methods in the & < n regime. This work initiates a new direction in the dearn-to-stabllit literature, and many interesting and challenging questions remain open, including handling noises, eliminating the assumptions on spectral properties, and developing better ways to learn the unstable subspace.
References
[1] John C. Doyle, Bruce A. Francis, and Allen R. Tannenbaum. Feedback Control Theory. Courier Corporation, 2013.
[2] Geir E. Dullerud and Fernando Paganini. A Course in Robust Control Theory: A Convex Approach, volume 36. Springer Science & Business Media, 2013.
[3] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. arXiv preprint (oXXvx1504.0077 2015.
[4] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learn- ing, pages 1329-13388 2016.
[5] Maryam Fazel, Rong Ge. Sham M. Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. arXiv preprint arXiv: I 1801055039, 2018.
10

---

[6] Jingjing Bu, Afshin Mesbahi, Maryam Fazel, and Mehran Mesbahi. LQR through the lens of first order methods: Discrete-time case. arXiv preprint arXiv: 1XXiv:907.00921, 2019.
[7] Yingying Li, Yujie Tang, Runyu Zhang, and Na Li. Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach. arXiv preprint wTXh:1112.09113. 2019.
[8] Steven J. Bradtke, B. Erik Ydstie, and Andrew G. Barto. Adaptive linear quadratic control us- ing policy iteration. In Proceedings of 1994 American Control Conference-ACC""94 volume 3, pages 3475-3479. IEEE, 1994.
[9] Stephen Tu and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. arXiv preprint arXiv:1712.086422 2017.
[10] Karl Krauth, Stephen Tu, and Benjamin Recht. Finite-time analysis of approximate policy iteration for the linear quadratic regulator. In Advances in Neural Information Processing Systems, pages 3512-8522, 2019.
[11] Kemin Zhou, John Comstock Doyle, Keith Glover, et al. Robust and Optimal Control, vol- ume 40. Prentice Hall New Jensey, 1996.
[12] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sam- ple complexity of the linear quadratic regulator. Foundations of Computational Mathematics, pages 1-47, 2019.
[13] Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26, 2011.
[14] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Explore more and improve regret in linear quadratic regulators, 2020.
[15] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. arXiv preprint arXiv:2007.06650 2021.
[16] Juan C. Perdomo, Jack Umenberger. and Max Simchowitz. Stabilizing dynamical systems via policy gradient methods. arXiv preprint arXiv:21 10.06418, 2021.
[17] Tankred Rautert and Ekkehard W. Sachs. Computational design of optimal output feedback controllers. SIAM Journal on Optimization, 7(3):837-852, 1997.
[18] Karl Märtensson and Anders Rantzer. Gradient methods for iterative distributed control syn- thesis. In Proceedings of the 48h IEFE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 549-554. IEEE, 2009.
[19] Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Mar- tin J. Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. arXiv preprint arXiv:
2018.
[20] Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R. Jovanović. Con- vergence and sample complexity of gradient methods for the model-free linear quadratic regu- lator problem. arXiv preprint arXiv: 1889, 2019.
[21] Benjamin Gravell, Peyman Mohajerin Esfahani, and Tyler Summers. Learning robust con- trollers for linear quadratic systems with multiplicative noise via policy gradient. arXiv preprint arXiv: 13547, 2019.
[22] Zhuoran Yang. Yongxin Chen, Mingyi Hong, and Zhaoran Wang. On the global conver- gence of actor-critic; A case for linear quadratic regulator with ergodic cost. arXiv preprint 197.0:190..06244. 2019.
[23] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges Nash equilibria zero-sum linear quadratic games. In Advances Neural Information Processing Systems, pages 11602-11614, 2019.

---

[24] Kaiqing Zhang, Bin Hu, and Tamer Basar. Policy optimization for H2 linear control with He robustmess guarantee: Implicit regularization and global convergence. In Learning for Dynamics and Control, pages 179-190, 2020.
[25] Luca Furieri, Yang Zheng, and Maryam Kamgarpour. Learning the globally optimal distributed LQ regulator. In Learning for Dynamics and Control, pages 287-297, 2020.
[26] Joao Paulo Jansch-Porto, Bin Hu, and Geir Dullerud. Convergence guarantees of policy op- timization methods for Markovian jump linear systems. arXiv preprint arXiv:2002.04090, 2020.
[27] Joao Paulo Jansch-Porto, Bin Hu, and Geir Dullerud. Policy learning of MDPs with mixed continuous/discrete variables: case study on model-free control of Markovian jump systems. arXiv preprint arXiv:2006.03//6, 2020.
[28] lyas Fatkhullin and Boris Polyak. Optimizing static lincar feedback: Gradient method. arXiv preprint a0Xiv:2004.09875, 2020.
[29] Yujie Tang, Yang Zheng, and Na Li. Analysis of the optimization landscape of linear quadratic Gaussian (LQG) control. In Learning for Dynamics and Control, pages 599-610. PMLR, 2021.
[30] Asaf B. Cassel and Tomer Koren. Online policy gradient for model free learning of linear quadratic regulators with vT regret. In International Conference on Machine Learning, pages 1304-1313. PMLR, 2021.
[31] Mohamad K. S. Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time analysis of optimal adaptive policies for linear-quadratic systems. arXiv preprint arXiv: 1:Xiv:/711.072.:50 2017.
[32] Yi Ouyang, Mukul Gagrani, and Rahul Jain. Learning- Learning-based control of unknown linear systems with Thompson sampling. arXiv preprint arXiv:1709.04047. 2017.
[33] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems, pages 4188-4197, 2018.
[34] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear- linear-quadratic regulators effi- ciently with only VT regret. arXiv preprint 1XXv:1902.06223: 2019.
[35] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalent control of LQR is effi- cient. arXiv preprint arXiv: 1902.07892. 2019.
[36] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online LQR. arXiv preprint arXiv:2001.09576 2020.
[37] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. arXiv preprint arXhv:2001.09254 2020.
[38] Yang Zheng. Luca Furieri, Maryam Kamgarpour, and Na Li. Sample complexity of linear quadratic Gaussian (LQG) control for output feedback systems. In Learning for Dynamies and Control, pages 559-570. PMLR, 2021.
[39] Orestis Plevrakis and Elad Hazan. Geometric exploration for online control. Advances in Neural Information Processing Systems, 33:7637-7647, 2020.
[40] Tze Leung Lai. Asymptotically efficient adaptive control in stochastic regression models. Advances in Applied Mathematics, 7(1):23 1986.
[41] Han-Fu Chen and Ji-Feng Zhang. Convergence rates in stochastic adaptive tracking, Interna- tional Journal of Control, 1915)19 1989.
[42] Tze Leung Lai and Zhiliang Ying. Parallel recursive algorithms in asymptotically efficient adaptive control of linear stochastic systems. SIAM Journal on Control and Optimization, 199 1991.
12

---

[43] Morteza Ibrahimi, Adel Javanmard, and Benjamin Van Roy. Efficient reinforcement learning for high dimensional linear quadratic systems. arXiv preprint arXiv:1333.5984, 2013.
[44] Mohamad K. S. Faradonbeh, Ambuj Tewari, and George Michailidis. Finite-time adaptive stabilization of linear systems. IEEE Transactions Automatic Control, 64(8):3498-3555 2019.
[45] Shahriar Talebi, Siavash Alemzadeh, Niyousha Rahim, and Mehran Mesbahi. Online regu- lation of unstable linear systems from single trajectory. In Proceedings of the 59th IEEE Conference on Decision and Control (CDC), pages 4784-4789, 2020.
[46] Yang Zheng and Na Li. Non-asymptotic identification of linear dynamical systems using mul- tiple trajectories. IEEE Control Systems Letters, 5(5):1693-1695 2020.
[47] Lennart Juung. System identification. Wiley Encyclopedia of Electrical and Electronics Engi- neering, pages 1-19, 1999.
[48] Max Simchowitz, Horia Mania, Stephen Tu, Michael Jordan, and Benjamin Recht. Learn- ing without mixing: Towards a sharp analysis of linear system identification. arXiv preprint arXiv:1802.08334. 2018.
[49] Samet Oymak and Necmiye Ozay. Non-asymptotic identification of LTI systems from single trajectory. In 2019 American Control Conference (ACC), pages 5655-5661. IEEE, 2019.
[50] Tuhin Sarkar, Alexander Rakhlin, and Munther A. Dahleh. Finite-time system identification for partially observed LTI systems of unknown order. arXiv preprint ArX2v:1902.01888 2019.
[51] Salar Fattahi. Learning partially observed linear dynamical systems from logarithmic number of samples. In Learning for Dynamics and Control, pages 60-72. PMLR, 2021.
[52] Han Wang and James Anderson. Large-scale system identification using randomized svd. arXiv preprint arXiv:2109.02700) 2021.
[53] Yu Xing, Benjamin Gravell, Xingkang He, Karl Henrik Johansson, and Tyler Summers. Identi- fication of linear systems with multiplicative noise from multiple trajectory data, arXiv preprint arXiv:2106. 16078, 2021.
[54] Yuji Nakatsukasa. Off diagona perturbation, first-order approximation and quadratic residual bounds for matrix eigenvalue problems. Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing (EPASA), Lecture Notes in Computer Science, pages 233-249. Springer, 2015.
[55] E. A. Rawashdeh. A simple method for finding the inverse matrix of Vandermonde matrix. Matematicki Vesnik: MV19303, 2019,
[56] F. L. Bauer and C. T. Fike. Norms and exclusion theorems. Numerische Mathematik, 2:137- 141, 1960.
[57] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2nd edition, 2013.
[58] Ioannis Chatzigeorgiou. Bounds on the Lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 17(8):1505 -508, 2013.
13

---

Checklist
(1) For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the "future work" part of the conclusions in Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We don't 't see any potential societal impacts such theoretical results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them?
[Yes]
(2) If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix D Ap-
pendix D. Appendix F and Appendix
(3) If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experimen- tal results (either in the supplemental material or as URLY? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
(4) If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
(5) If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if appli- cable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "eFoiMO9UkqC", "reviewer": "Reviewer_ytQe", "summary": "The paper provides an algorithm for stabilizing a noiseless LTI system on a single trajectory with sample complexity scaling in the number of unstable modes of the dynamics matrix rather than the state-dimension.", "questions": "Noise definitely makes the analysis more challenging/messy, but is there a path to prove similar results for the noise setting?\n\nCan the results easily be generalized to unknown $k$?", "limitations": "Limitation of known $k$ could be addressed directly.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- At it's core, this is an important problem.  LTI systems are one of the most important primitive in control and exponential state blow-up in the state dimension is a critical problem in all existing work in this area as far as I know.  \n- Writing is generally quite clear and well organized. The assumptions are presented clearly in section 4 and for the most part are reasonable (see weaknesses).  Breakdown of the algorithm and exposition into stages also is very nice for clarity.\n- Work seems technically correct and strong.\n\nWeaknesses:\n- While the algorithm is empirically justified in the presence of noise in App. H, no provable results for the noised case significantly weaken the result.  As mentioned in the paper, many existing methods first need a stabilizing controller.  This will need to be found in the presence of noise, which for some applications even needs to be adversarial.\n- It appears that the instability index $k$ needs to be known for the algorithm, which probably is not reasonable in general.\n- The algorithm outputs a $\\tau$-hop stabilizing controller, which may not be suitable for certain downstream control tasks.\n- Assumption 4.1 seems reasonable but may actually be difficult to deal with without handling noise.  Many physical systems do have repeated eigenvalues and small perturbations to the system parameters would require some form of noise tolerance.  Ideally, robustness in the $H_{\\infty}$ sense would be involved as these perturbations depend on the state.\n\n\nWhile there are limitations, I think this is result still would be a worthwhile addition to the conference.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N7WAVZ_bkc5", "reviewer": "Reviewer_fVVW", "summary": "The paper studies the number of samples for learning to stabilize a noiseless linear control system. Under a set of assumptions, it is shown that with O(k log n) samples the system can be stabilized, where n is the state dimension and k is the instability dimension. An algorithm is presented for that purpose too.", "questions": "See above", "limitations": "See above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper discusses different steps and explain them. Also, the technicalities and the assumptions are stated in a way the reader can follow.\n\nWeaknesses:\nI like to see how the authors can discuss the following items. \n- Overall, the writing is repetitive in multiple places. \n- I think connections to some relevant stabilization algorithms in the literature (mostly subject to stochasticity and/or using that) are missing.\n- In the abstract, 'instability index' needs a (high level) definition, and the rates are not correctly written (the current one seems like k log k).\n- The assumptions are strong. The open loop matrix is diagonalizable, does not have any unit eigenvalue and even has a significant eigen-gap (Theorem 4.1), the unstable and stable eigenspaces are assumed almost orthogonal, the dimension of the control input is exactly the same as the number of unstable eigenvalues, etc. \n- On top of the above, having an undisturbed dynamics is a very important and strong assumption. Although, the authors correctly claim that it is not consequential in terms of stability, it is important for learning the unknown matrices by letting the observations be noisy or noiseless, and also as mentioned in line 196, the stable modes all die out in undisturbed systems. Importantly, most of the assumptions here are not needed in the existing literature, and some are proven to be satisfiable through designing the control input properly, rather than being given.\n- Along the same axis, for extending to stochastic systems and having high probability results, it is not clear how this work helps as the authors claim in line 120.\n- Some sample presentation points to improve are as follows. In Def 3.1, I think orthonormality of the matrices is crucial and needs to be emphasized and mentioned explicitly. In line 5 of Algorithm 1, I think it should be 'ortho-normalized'. The range of i is not clear in line 11. Line 258 and invertibility needs more concrete explanation. R_1 in Assumption 4.3 is better to be referred to where defined. I could not find the 'recall' in Theorem 4.1, and it might be added to the assumptions. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "98URclpnD8", "reviewer": "Reviewer_v7qW", "summary": "The paper deals with stabilization of an unknown LTI system from an trajectory of the system, thus learning and stabilization of the system must be done simultaneously. This is a timely problem and an current active research area. In the paper, the states/modes of the system are divided into stable/unstable, and only the unstable modes are identified and controlled.", "questions": "Can the weaknesses above (1 and 2) be addressed? By including a larger \"k\" in the algorithm compared to the number of unstable modes it may be possible to overcome or weaken these two limitations.\n\nCan you state the theorems so that is clear what the assumptions are on the system parameters? Are all these parameters independent of the number of states?", "limitations": "Not applicable. This is basic science. I see no potential negative societal impact related to this work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper well written, it deals with a timely problem, and as far as I know the main results are novel and improves on the state of the art.\n\nWeakness: \n1) There are several assumptions on the systems that restricts the applicability. Assumptions 4.1, 4.2, 4.3, seem rather harmless, however, the assumption on the eigenvalues |\\lambda_1|^2 | |\\lambda_k|<|\\lambda_{k+1} restricts the applicability. Especially if |\\lambda_1| is large. \n\n2) The algorithm uses k, so one need to know the number of unstable modes. \n\n3) In the key results, only dependence in k and n is stated but it is noted that the constant depends on other parameters as well. It seems to me difficult (and strange) to find a sequence of systems where all hidden parameters are constant (even for the ones listed). Here I think it is important to state exactly which parameters the assumptions on the parameters. In particular, when the number of states and unstable modes changes, the parameters need to be well defined and cannot, e.g., depend on the size of the system.\n\nI did not read the supplementary material.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "82uzmExv6bO", "reviewer": "Reviewer_JYWD", "summary": "The paper studies the problem of stabilization from data in the case of linear control systems, in the noiseless setting. A new algorithm is proposed, where instead of identifying the whole state space, it is sufficient to identify only the unstable part. Under certain assumptions, this is sufficient for designing a stabilizing control, requiring fewer samples than the case when everything is identified. The paper provides some sample complexity bounds with high probability, where the randomness comes from the initial condition. If some special conditions are satisfied, then the complexity is linear with k, i.e. the total number of unstable eigenvalues, and depends logarithmically on n, i.e. the dimension of the state space. \n\n​", "questions": "Please compare with the two papers listed above, Talebi, Alemzadeh, Rahimi, Mesbahi, \"Online Regulation of Unstable Linear Systems from a Single Trajectory\", CDC 2020 and Tsiamis, Ziemann, Morari, Matni, Pappas \"Learning to control linear systems can be hard\", 2022.\n​\nThere should be more intuition/discussion about what types of systems satisfy Assumption 4.3 , k=m.\n​\nPlease provide more details for the case of general matrices B (when m is less than k) and clarify Section C.  What would Assumption 4.3 look like in this setting? How would the result of Theorem 4.1 depend on the index d? To my understanding, in the worst case, we might need to unroll the state d=theta(n), not theta(k/m), times to achieve controllability and stabilize the system. I believe, this d can be as high as the controllability index of the system, which in the worst case can be linear with n, even if the number of unstable modes is as small as one (unless further assumptions are imposed).   For example, see system (14) in Tsiamis, Ziemann, Morari, Matni, Pappas \"Learning to control linear systems can be hard\", 2022. For that system, tilde B (projected on the unstable subspace) would be equal to zero unless d=n-1. \n​\nThere seems to be a problem with the invertibility of matrix D'D. In particular, if matrix A is singular, then D'D should also be singular. Probably the results still go through since a projection is considered. But the proofs of section E should be updated.\n​\nCould you please provide more intuition why u has this particular form in line  11 of the algorithm? Why does the input scale with the norm of x? Since x is unstable, this might lead to very large control inputs. Please clarify that in the text since this seems to be another limitation of the algorithm. The naive algorithm would work with small inputs.\n​\nPlease provide more discussion on which assumptions seem necessary and which assumptions seem removable.  ", "limitations": "See comment above. \n", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As mentioned in the summary, if certain special conditions hold, then the complexity is linear with k, i.e. the total number of unstable eigenvalues, and depends logarithmically on n, i.e. the dimension of the state space.\nThis is a novel and interesting result that was not established before. Hence, the benefit of this algorithm is that we can stabilize the system much faster compared to the standard algorithm, where we identify the whole state space.\nIt would be interesting to compare the results of this paper to the paper by Talebi, Alemzadeh, Rahimi, Mesbahi, \"Online Regulation of Unstable Linear Systems from a Single Trajectory\", CDC 2020, where a similar topic is explored, under similar assumptions.\n​\nThe main weakness  of the paper is that it relies on several restrictive assumptions that should be explained upfront and in more detail. More intuition should be provided; for example it would help to provide a discussion on what types of systems satisfy these assumptions. Also it should be explained whether the algorithm still works or fails in the absence of these assumptions.\nThe most crucial assumption is that all unstable modes are directly driven/controllable by the input matrix B (Assumption 4.3 along with k=input dimension m). In other words, it is assumed that we have a lot of inputs and all of them directly affect any possible unstable mode. This assumption is quite restrictive since it rules out the possibility of underactuated systems, systems with network structure or systems with integrator-like structure, which in general are hard to control, see the paper by Tsiamis, Ziemann, Morari, Matni, Pappas \"Learning to control linear systems can be hard\", 2022.\nThe material of Section C does not explicitly address the case when we might have k larger than the number of inputs (m less than k)-see also questions. \nThere are three more assumptions that are somewhat restrictive yet crucial for obtaining the result. i) There should be no noise in the system, ii) The initial condition should be non-zero, iii) the stable eigenvalues cannot be arbitrary; they should be small enough to cancel the effect of the unstable ones (in the cross-term entries of matrix M tau). The paper provides technical reasons why we need them, but it would be nice to also see some discussion whether they are necessary or not. For example, having stochastic noise might affect sample complexity in a dramatic way; in deterministic systems it is always possible to identify everything with zero error and finite samples while this is not possible in the case of stochastic systems. The assumption of the stable part cancelling the unstable one seems artificial, would the algorithm work if it was removed? \n\n​", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept