Stabilizing LTI Systems under Partial Observability: Sample Complexity and Fundamental Limits
Authors: Ziyi Zhang
Yorie Nakahira
Guannan Qu
Venue: NeurIPS 2025 poster ()
Keywords: Linear dynamical system
Learning-based control
Learn-to-stabilize
Sample complexity
Unknown system
Primary area: theory
TL;DR: We design a novel algorithm to stabilize an unknown partially observable LTI system with a complexity bound independent of the state dimension.

Abstract: We study the problem of stabilizing an unknown partially observable linear time-invariant (LTI) system. For fully observable systems, leveraging an unstable/stable subspace decomposition approach, state-of-art sample complexity is independent from system dimension $n$ and only scales with respect to the dimension of the unstable subspace. However, it remains open whether such sample complexity can be achieved for partially observable systems because such systems do not admit a uniquely identifiable unstable subspace. In this paper, we propose LTS-P, a novel technique that leverages compressed singular value decomposition (SVD) on the ''lifted'' Hankel matrix to estimate the unstable subsystem up to an unknown transformation. Then, we design a stabilizing controller that integrates a robust stabilizing controller for the unstable mode and a small-gain-type assumption on the stable subspace. We show that LTS-P stabilizes unknown partially observable LTI systems with state-of-the-art sample complexity that is dimension-free and only scales with the number of unstable modes, which significantly reduces data requirements for high-dimensional systems with many stable modes.

Stabilizing LTI Systems under Partial Observability: Sample Complexity and Fundamental Limits
Ziyi Zhang, Yorie Nakahira, Guannan Qu
Department of Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213
riyizhan, geuuridreguunnrr...rr cmu edu
Abstract
We study the problem of stabilizing an unknown partially observable linear time- invariant (LTI) system. For fully observable systems, the statc-of-the-au approaches leverage an unstable/stable subspace decomposition to achieve sample complexity that depends only on the number of unstable modes, independent of the dimension of the system state. However, it remains open whether such sample complexity can be achieved for partially observable systems because such systems do not admit uniquely identifiable unstable subspace. In this paper, propose LTS-P, a novel technique that leverages compressed singular value decomposition (SVD) on the "lifted" Hankel matrix to estimate the unstable subsystem up to unknown transformation. Then, we design a stabilizing controller that integrates a robust stabilizing controller for the unstable mode and small-gain-type assumption the stable subspace. We show that LTS-P achieves state-of-the-ard dimension free sample complexity that scales only with the number of unstable modes. This substantially reduces data requirements for stabilizing high-dimensional systems, particularly those dominated by stable dynamics.
Introduction
Learning-baid baseed control of unknown dynamical systems of critical importance for many autonomous
24 12). Despite recent advances, many existing methods make strong assumptions such as open-loop stability, availability of an initial stabilizing controller, and fully observable systems [15] 41. However, these assumptions may not hold in practice. Motivated by this gap, this paper studies the problem of stabilizing an unknown, partially-observablee unstable system without access to initial stabilizing controller. In particular, we consider the following linear time-invariant (LTI) system:
control systems 3 30
T++1 Ar, + Bu:
Y1 = Cx, + Du: + Vt:
where 2, E R" and un E Rd. Dt. E Rd are the state, control input, and observed output at time step E (O...., T 1}. respectively. The system also has additive observation noise 2 (0 I While there are works studying system identification for partially observable LTI systems
34 5T). they do not address the problem of stabilization, and many assume the system is owwn-peeooooooooo loop stable [15 41 34). Other adaptive control approaches can address the cearn-to-stabilize problem for fully observable systems based on Lyapunov methods B7), but there are few systematic approaches to construct a Lyapunov function in way that optimizes sample complexities or transient performance during learning.
In the special case of fully-observable LTI system (C = /), Chen and Hazan 9 reveals that the transient performance during the Cearn-to-stabllia process suffers from exponential blow-up. i.c. the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

system state can blow up exponentially in the state dimension. This phenomenon arises because stabilization requires accurate identification of the full system dynamies. which in turn necessitates at least samples along a single trajectory. During this identification phase, the system can remain unstable and grow exponentially. To relieve this problem, Hu et al. [19] proposed framework that separates the unstable component and focuses on stabilizing these subsystems. This reduces the sample complexity to only grow with the number of unstable eigenvalues, rather than the full state dimension This result was later extended to noisy setting in Zhang et al. [50]. To date, this dependence on the number of unstable eigenvalues remains the best sample complexity for the leam-tt-sstaillie problem in the fully observable case.
In contrast, we address a more challenging setting of partially observable systems, and answer the following research question: Is it possible to stabilize a partially observable LTI system by only identifying an unstable component (to be properly defined) with sample complexity independent of the overall state dimension? This question introduces two key technical challenges. First, partially observable systems typically require a dynamic controller, which renders the stable feedback con- trollers in the existing approach inapplicable [19] Second, the construction in "unstable subspace" in Hu et al. [9] is not uniquely defined in the partially observable case. This is because the state and the A, B, C matrices are not uniquely identifiable from the learner's perspective, as any similarity transformation of the matrices can yield the same input-output behavior.
Contribution. In this paper, we answer the above question in the affirmative. Firstly, we propose a novel definition of "unstable component" to be a low-rank version of the transfer function of the original system that only retains the unstable eigenvalues. Based on this unstable component, we propose L. which leverages compressed singular value decomposition (SVD) on a "lifted" Hankel matrix to estimate the unstable component. Then, we design a robust stabilizing controller for the unstable component, and show that it stabilizes the full system under a amall-gain-type assumption on the Hox norm of the stable component. Importantly, our theoretical analysis shows that the sample complexity of the proposed approach only scales with the dimension of unstable component, i.e. the number of unstable eigenvalues, opposed to the dimension of the full state space. We also conduct simulations to validate the effectiveness of LTS-P, showcasing its ability to efficiently stabilize partially observable LTI systems with reduced samples (Figures and 2).
Moreover, the technical innovations underlying our approach are of independent interest. We show that by using compressed singular value decomposition (SVD) on properly defined lifted Hankel matrix, we can estimate the unstable component of the system. While this is conceptually related to classical model reduction techniques [13 Chapter 4.6], our setting departs significantly: unlike prior work for stable dynamics and bounded Hankel matrices [3], we address systems with unstable modes, where the associated Hankel matrices may grow unboundedly over time. This distinction renders standard identification and reduction techniques inapplicable [15] (34]. Interestingly, the Ho norm condition on the stable component, derived from the small gain theorem, is necessary and sufficient condition for stabilization. This characterization reveals the exact subspace of the system that must be estimated for stabilization to be possible. As a result, our analysis not only supports the optimality of L-TSP in terms of sample complexity but also informs the fundamental limit of stabilizability.
Related Work. Our work is closely related to -ottabiittaaili on multiple trajectories and learn-to- control with known stabilizing controllers. In addition, we will also briefly cover existing literature in learn-to-stabilize on a single trajectory, adaptive control, and system identification.
Learn-to-stabilize on multiple trajectories. There are also works that do not assume open-loop stability and learn the full system dynamics before designing stabilizing controller, typically incurring a sample complexity of (ppoly(n)) [12 45 51] Recently, a model-free approach via the policy gradient method offers novel perspective with the same sample complexity [36]. While these techniques are developed for fully observable systems, the proposed algorithm, LTS-P, tackles a significantly more challenging setting of partially observable, unstable systems. As detailed above, this setting introduces fundamental technical challenges that require novel algorithmic and analytical tools beyond those used in fully observable systems. Moreover, compared with those works, the sample complexity of the proposed algorithm does not depend on n and only scales with the number of unstable modes.
Learn to control with known stabilizing controller. Extensive research has been conducted on stabilizing LTI systems under stochastic noise [5]
22
25 30
One branch of research uses the

---

Those algorithms typically require a known stabilizing controller as an initialization policy for the learning process. Another line of research utilizes model-based approaches, which require an initial stabilizing controller to learn the system dynamies before designing the controllers [10 32 38 52 On the other hand, we focus on learn-to-stabilize. Our method can be used as the initial policy in these methods to remove their requirement for initial stabilizing controllers.
model-free approach to learn the optimal controller [16 21 30
46
49).
Leam-to-stabillie on a single trajectory. Learning to stabilize linear system in an infinite time Early works achieved the regret bounds of 20(n) O(VT), which rely on assumptions of observability and strictly stable transition matrices 20]
horizon is a classic problem in control 7 26 27
Subsequent work improved the regret to 20(") + (ppoly(n)
[ 28 Recently, Hu et al. [19
proposed an algorithm that requires (kk) samples, where k is the number of unstable modes. While these techniques are developed for fully observable systems using a single trajectory, we consider a
different problem of learning to stabilize a partially observable system using multiple trajectories.
Adaptive control. Adaptive control is well-established methodology for controlling systems with uncertain or time-varying parameters g 35 377. Existing literature has established techniques for stabilizing unknown systems with asymptotic stability (9
14 29
45]. Other works use past
trajectory to estimate the system dynamics and then design the controller [4] [ 31. While these works often assume stability, fully observable systems and are based on Lyapunov methods, we focus on partially observable, unstable systems and build our algorithm based on compressed SVD on the lifted Hankel matrix.
System identificatio.. Existing literature has developed a variety of techniques to estimate system 42 47 Hankel matrix are also used in techniques such Eigensystem Realization Algorithm (ERA), subspace identification, etc 23 39]. Our work utilizes a similar approach to partially determine the system parameters before constructing the stabilizing controller. While these works focus on identifying the system dynamics, we close the loop and establish state-of-the-art and optimal sample complexity guarantees for the stabilization problem.
parameters 33 40 43
2 Problem Statement
Notations. We use ||-|| denote the - for vectors and the spectral norm for matrices. We use M' to represent the conjugate transpose of M. We use m-in(-) and o masx(.) (-) to denote the smallest and largest singular value of matrix, and x(.) to denote the condition number of matrix. We use the standard big O(),, ((-). O()) notation to highlight dependence on a certain parameter, hiding all
other parameters. We use f S g. I Z g. I x g to mean f = O(g), ʃ =(gg), f O(y) respectively while only hiding numeric constants. We provide an indexing of notations at Appendix !
For simplicity, we primarily deal with the system where D) 0. For the case where A 0, we can casily estimate D in the process and subtract Du, to obtain a new observation measure not involving control input. We briefly introduce the method for estimating 1) and how to apply the proposed algorithm in the case when D a O in Appendix F
Learn-to-stabilize. As the unknown system defined in (I can be unstable, the goal of the cearn-to-stabliiz problem is to return a controller that stabilizes the system using data collected from interacting with the system M rollouts. More specifically, in each rollout, the learner can determine u, and observe ye for a rollout of length T starting from Lo. which we assume Zig = 0 for simplicity of proof.
Goal. The sample complexity of stabilization is the number of samples, MT, needed for the learner to return a stabilizing controller. Standard system identification and certainty equivalence controller design need at least ((n) samples for stabilization, as ((n) is the number of samples needed to learn the full dynamical system. In this paper, our goal is to study whether it is possible stabilize the system with sample complexity independent from n.
2.1 Background on Hoo control
In this section, we briefly introduce the background of H-infinity control. First, we define the open loop transfer function of system (1) from ue to y/ to be
full C(zl A)- B,
(2)
3

---

which reflects the cumulative output of the system in the infinite time horizon. Next, we introduce the Hos space on transfer functions the z-domain.
Definition 2.1 -Space). Let H denote the Banach space of matrix-valued functions that are analytic and bounded outside of the unit sphere. Let R2 denote the real and rational subspace of Hoc The oox -norm is defined as
Il = sup max (f(z)) = sup max (f(z))
=EC,|=21
=EC||a|=1
where the second equality is simple application of the Maximum modulus principle. We also denote C21 = {= E C | 2 1) be the complement of the unit disk the complex domain. For any transfer function G, say it is internally stable if G E RHo..
The H. norm of transfer function is crucial in robust control, as it represents the amount of modeling error the system can tolerate without losing stability, due to the small gain theorem [53] Abundant research has been done in H control design to minimize the Ho norm of transfer functions [53] In this work, Ho control play an important role as we treat the stable component (to be defined later) the system as a modeling error and show that the control we design can stabilize despite the modeling error.
3 Algorithm Idea
In this paper, we assume the matrix A does have marginally stable eigenvalues, and the eigenvalues are ranked in decreasing order of magnitude, i.c. |vı 2 \>2 2 ... 2 A > 1 | 2 [An]- The high-level idea of the paper to first decompose the system dynamics into the unstable and stable components (Section 3.1 estimate the unstable component via a low-rank approximation of the lifted Hankel matrix (Section 3.2) and design a robust stabilizing for the unstable component
that stabilizes the whole system (Section 3.3
3.1 Decomposition of Dynamics
Given the eigenvalues, we have the following decomposition for the system dynamics matrix:
N1
R1
A = Q1Q2
N₂
R₂
==Q
R
where R Q-1 and the columns of Q1 E Bank of the unstable eigenvalues Ai...., Ag. with N1 inheriting eigenvalues . 0 from A. Similarly, columns of Q2 E [p=x(n=k) form an orthonormal basis for the invariant subspace of the unstable eigenvalues . An and N2 inherit all the stable cigenvalues Ag+1,.... An.
orthonormal basis for the invariant subspace
......,gg
Given the decomposition the matrix A, our key idea is to only estimate the unstable component of the dynamics, which we define below. Consider the transfer function of the original system:
Ffull (2) C(2l A)- BB B
[0
N1
0
R1
)
-1
B
0
N₂
R₂
= =c(1Q100)
=1 - N₁
Rı
-1
B
0
21 - N2
R
=QQ Ni) R
CQ2(2I N2)
RR F(z)+
(4)
==((x)
:=)(=)
Therefore, the original system is an additive decomposition into the unstable transfer function F(z). which we refer to as the unstable component, and the stable transfer function ((z), which we refer to the stable component.
3.2 Approximate low-rank factorization of the lifted Hankel matrix
In this section, we define a "lifted" Hankel matrix, show admits a rank & approximation, based on which the unstable component can be estimated.

---

If each rollout has length T, we can decompose T := -++-++++++ 2 and estimate the following "lifted" Hankel matrix where the (i.j)-th block is [ C. where ......P.. :....:0 : In other words,
CA CA B
CAm+1B B
CA
CAm+2B
CA
H
(5)
CA"+P-IB
CA
CAmtpto-2B
for some m, P. that we will select later. We call this Hankel matrix "lifted" as it starts with CAa B. This "lifting" is essential to our approach, as raising to the power of m can separate the stable and unstable components and facilitate better estimation of the unstable component, which will become clear later on.
Define
CA
CAT/2+1
[Am/2 B,m/2B,a Am/2+1 B.... Am/2+a-11p
(6)
CAm/2+p-1
Then we have the factorization = OC, indicating that H is of rank at most n.
Rank & approximation. We now show that H has a rank k approximation corresponding to the unstable component. Given the decomposition of 3). we can write each block of the lifted Hankel matrix as
CA B = cQQ
Nf
0 N
R1 R2
B (CQ1 cQal
Nf 0 N
0
R
R₂B
If is resonably large, using the fact that N Therefore, we know that when is reasonably large, we have H can be approximately factorized as H OC where:
>> N2 ~ O, we can have CA N C
CQINT/2
CQINT/211
δ
Č [N[Nim/2p B...., 22/2+0-1 Rg B).
CQ
As Ô has ie columns, OC has (at most) rank-k: We also use the notation
H = =ĆC
(8)
to denote this rank-k approximation of Hankel. As from H to H, the only thing that are omitted are of order O(NT)), , it is reasonable to expect that H #1 S (( i.e. this rank l approximation has exponentially decaying error m, as shown in Lemma C.3
Estimating unstable component of dyamics. In the actual algorithm (to be introduced in Section 4 Herfectly.Howevee A is to be estimated and therefore not known perfectly. However, to illustrate the methodology of the proposed method, for this subsection, we consider to be known perfectly and show that the unstable component F=2) can be recovered perfectly.
Suppose have the following factorization of H for some Ô E Rdy*k Rexd. (which has infinite possible solutions), H OC. We show in Lemma D.I there exists invertible S, such that O = ÔS, C= Therefore, from the construction of Ô and Č in 7 see that O CiINII// where O represent the first block submatrix of O Solving for N₁ for the equation O2.p -O1--1N11, we can get N1 = SN'SS.. After which we can get C = N,N, = CQ1S, and B- N1 /2 = S-1R summary, we get the following realization of the system:
N,S,, S Bug 2t+1 = CQ1S2.
(9a)
(9b)
whose transfer function is exactly F(2), the unstable component of the original system.
For row block or column block matrics M, we use M, to denote its i'th block, and Mej to denote the submatrix formed by the i I,..., block.
5

---

Algorithm LTS-P: learning the Hankel Matrix
1: for =111 M do
2: Generate and apply T Gaussian control inputs [uo
uT NO0 o.)). Collect y
iid
"uo",...,, -f-
3: end for
4: Compute & with
5: Recover H with 18
6: Compute it from H with 19
7: Compute O and C with (20).
8: Recover N1, NN 1,0 N 1,C with
23 respectively.
9: Compute B with 24
10: Design Ho controller with (N1, C, B).
3.3 Robust stabilizing controller design
After the unstable component F2) estimated, we can treat the unobserved part of the system as disturbance (2) and then synthesize a robust stabilizing controller. Suppose we design controller u(z) = (=))((>) for F()), and denote sensitivity function as:
Fx = (I (2))
Now let's look at what if we applied the same (2)) to the full system Ffull (2) in (4. this case, the closed loop system is stable if and only the transfer function F (z) (1 piall (=)
is analytic for all |2| 2 1, see e.g. Chapter 5 of (53] Note that,
F fffull p-ull (x)) (3) A(2)
(2) (z))
(x) :
(10)
The Small Gain Theorem shows necessary and sufficient condition for the system to have stabilizing controller:
Lemma 3.1 (Theorem 8.1 of 53 Given the closed loop transfer function defined in 10
internally stable for any A H.. I if and only if (z) (2))l <
Since A (2) is stable and therefore has bounded Ho norm, suffices to find a controller such that
| [=x))
(11)
|=)
in order to stabilize the original full system.
4 Algorithm
Based on the ideas developed in Section we now design algorithm that learns stabilize from data. The pseudocode is provided in Algorithm !
Step 1: Approximate Low-Rank Lifted Hankel Estimation. Section shows that if ÿ defined in design controller satisfying (11) stabilize the system. In this section,
(8) is known, then discuss method estimate H with singular value decomposition (SVD) of the lifted Hankel metrix.
Data collection and notation. Consider we sample M trajectories, each with length T. To simplify notation, for each trajectory E (l,..., ......,,, M). we organize input and output data as
(i)
Vo
Vr -T-1
(1)
(9
1---1
(12)
where each N(0,, ? are independently selected. We also define the a new matrix for the observation noise as
(
[ (K)
(13)
T

---

Substituting the above into
we obtain
y
Ca
+ ( = CA (BuL)-1
(14)
We further define an upper-triangull Toeplitz matrix and matrix of observed system dynamics:
U
U
My
0
CB
CAB
CA
(15)
Note that the lifted Hankel matrix H in (5) be recovered from 4 above they contain the same block submatrices. The measurement data [4 in each rollout can be written as
ΦT() + v())
(16)
Therefore, we can estimate & by the following ordinary least square problem:
M
X
==
arg
min X da
(17)
We then estimate the lifted Hankel matrix as follows:
224m
43+m
2+
3m
444m
H
(18)
42
Let = ÜH V denote the singular value decomposition of A, and we define the k-th order estimation of H:
-==-.V
(19)
where i (V) is the matrix of the top i left (right) singular vector in Un (Vn), and E is the matrix of the top & singular values in En.
Esitmating unstable transfer function F. With the SVD â = ÚΣV* we further do the following factorization:
Step 2:
Ô = 0'/
(20)
With the above, we can estimate Nı, C, similar the procedure introduced in Section 3.2
N1 = (Ōi 1p 10pp-100--11--00
O2p
(21)
To reduce the error of estimating CQ₁ and R₂ B and avoid compounding error caused by raising Ni to the m/2' th power, we also directly estimate N from both Ô and č.
N Ni, ( 7 1:p
1:p T ①
+1:ps
(22)
Ni. = - (Cr.p- Cr Ci.-- )-1
Cip
(23)
In practice, the estimation obtained from (22) and 23 are very similar, and can use either one estimate N1 Lastly, we estimate O and B as follows:
Č=
B:
(24)
where for simplicity, we use NT.0 1.C to denote the invserse of N N
1.0- We will provide
accuracy bounds for those estimations in Appendix B With the above estimations, we are ready to design controller with the following transfer function,
F(x) Ó - B.
(25)
7

---

Step 3: Designing robust controller. After estimating the system dynamics and obtain the estimated transfer function (25) as discussed in Section
3.3 we can design a stabilizing controller by existing Ho control methods to minimize [ (x I The details on designing the robust controller
can be found in robust control documentations, e.g. Chapter of Dullerud and Paganini [13].
What if k is not known a priori? The proposed method requires knowledge of k. the number of unstable eigenvalues.
is not known, we show Lemma B.1 and Lemma C.3 that the first singular values of H and H increase exponentially with m, and the remaining singular values decrease exponentially with m. Therefore, with a reasonably sized m and if are chosen to be larger than k there will be a large spectral gap among the singular values of H. The learner can use the location of the spectral gap to determine the value of k.
Main Results
In this section, we provide the sample complexity needed for the proposed algorithm to return stabilizing controller. We first introduce standard assumption on controllabilty and observability,
Assumption 5.1. The LTT system (A, B) is controllable, and (4, C) is observable.
We also need an assumption on the existence of a controller that meets the small gain theorem's criterion (IT..
Assumption 5.2. There exists a controller ((2) that stabilizes plant F(z), such that for some fixed 6 > 0, [=)) < [T(=))) R... +36."
To state our main result, we introduce some system theoretic quantity.
Cantrollabiltyyooeerrrbbbt Gramian for unstable subsystem.
For the unstable subsystem N1, N1,R1B CQ1, its a-observability Gramian is Gob ((Q1)) (CQIN1)*
and its a-controllability Gramian is Gron B, Ná- B). Per Lemma H.1 and Assumption 5.1 the N1, R1 B, CQ1 subsystem is both controllable and observable, and hence we can select a to be the smallest integer such that both Gob, Jcon are rank-k. Note that always have a k. Our main theorem will use the following system-theoretic parameters: a, n(Gor)) <(Goon) ) (the condition numbers of Gob. Geon respectively), and Tmin (Gob), mmin (Goon) (the smallest singular values of Gob, Geon, respectively).
(CQ,NT-1)1)
know
Umbrella upper bound L. We
constant L to upper bound the norms ||||], Bl], |[C]], || BI, We will use the Jordan form decomposition for Nj = PAPP- and let L upper bound ||| = x(P)). We also use in sup|=/=1 [1 - NN) S - Lastly, we use L to upper bound the constant in Gelfand's formula (Lemma H.2 for N2 and
L
NT Specifically we will use ||
[ II(NT S
Vt 2
With the above preparations, we are ready to state the main theorem.
Theorem 5.3. Suppose Assumption 5.7 Assumption 5.2 holds and Ni is diagonalizable. In the regime where [Aal - 1, 1 - |1641), e, are small we set (recall throughout the paper x only hides numerical constants)
log L
)
X max
Da+iI
Aul
log min( (Gob), mmin (Geon)) () I)E,
and we set p = q = m (hence each trajectory' 's length T = 3m 2) and the number of trajectories
Tu ( dy) log g + d.m.
M
for some E (0, 1). Then, with probability at least 1 8, k(x) obtained by Algorithm i stabilizes the original dynamical system 2
"This regime is the most interesting and challenging regime. For more general values of [Au] - 1. - -14411 C., the bound in (106 which takes complicated form.

---

The total number of samples needed for the algorithm is MT = (3m + 2)M. In the bound in Theorem [.3 the only constant that explicitly grows with is the controlaaiiityyoosrrabbii
index a (k) which appears in the bound for m. Therefore, the sample complexity MT (m²) = O(a²) = -KkP) grows quadratically with and independent from system state dimension In the regime l < n, this significantly reduces the sample complexity of stabilization compared to methods that estimate the full system dynamics. To the best of our knowledge, this is the first result that achieves stabilization of an unknown partially observable LTI system with sample complexity independent from the system state dimension n. To validate the claim in Theorem [.3] we use the LTS-P to stabilize a randomly generated partially observable system and compare the result with two state-of-the the benchmarks [43] 51] in Appendix A In Appendix B we provide a high-level
overview of the proof of Theorem 5.3 with detailed proof steps in Appendices to
Dependence on system theoretic parameters. As the system becomes less observable and controllable, k(Gcon)) (Gob)) increases and "min((Con) (9ab)) decreases, increasing m and x(Gat)n(GGun))
More- Aul are closer to 1, the sample complexity also increases in the order of (max(I-TXe__] 1- |T log x))= This makes sense as the unstable and stable components of the system would become closer to marginal stability and harder to distinguish apart. Lastly, if the 6. in Assumption 5.2 becomes smaller, we have smaller margin for stabilization, which also increases the sample complexity in the order of (log 2,0
the sample complexity MT grows in the order of (log miin("Tiillttttt)ee Tiin (fooa)
over, when | |
(.22
Non-diagonalization case. Theorem 5.3 assumes Ni is diagonalizable, which is only used in single place in the proof in Lemma D More specifically, we need to upper bound J'(J") for some Jordan block J and integer t. and in the diagonalizable case an upper bound is 1 as the Jordan block is size 1. In the case that N1 is not diagonalizable, a similar bound can still be proven with dependence on the size of the largest Jordan block of NN. denoted as 7. Eventually, this will lead to an additional multiplicative factor y in the sample complexity on m (cf. (124), whereas the requirements for p, 9, M is the same. The derivations can be found in Appendix G
Necessity of Assumption 5.2, Assumption 5.2 needed if one only estimates the unstable component of the system, treating the stable component as unknown. This is because the small gain theorem is an if-and-only-if condition. If Assumption 5.2 is not true, then no matter what controller K K(2) one designs, there must exist an adversarially chosen stable component Azz) (not known to the learner) causing the system to be unstable, even if Fz)) is perfectly learned. For specific construction of such a Zhou and Doyle [53]. Although Hu et al. [9]. Zhang et al. [50] do not explictly impose this assumption, they impose similar assumptions on the eigenvalues, e-g. the | < 1 in Theorem 4.2 of Zhang et al. [50], and we believe the small gain theorem and Assumption 5.2 is the intrinsic reason underlying those eigenvalue assumptions in Zhang et al. [50]. We believe this requirement of Assumption i. the fundamental limit of the unstable + stable decomposition approach. One way to break this fundamental limit is that instead of doing unstable + stable decomposition, we learn a larger component corresponding to eigenvalues , A for some 1 > k, which effectively means we learn the unstable component and part of the stable component of the system. Doing so, | Fr.. will approach 0.
-breaking A(2), see the proof of the small gain theorem, c.g. Theorem 8.1 of
Assumption 5.2 will be easier to satisfy as when & approaches
Relation to hardness of control results. Recently, there has been related work on the hardness of the Icarn-to-stabilen to-sbbiieize problem 9 48). Our setting does not conflict with these hardness results for the following reasons. Firstly, our result focuses on the < n regime. In the regime k n, our result does not improve over other approaches. Secondly, our Assumption 5.2 is related to the co-stabilizability concept in Zeng et al. [48], as Assumption [5.2] effeetively means the existence of a controller that stabilizes the system for all possible A(z). In some sense, our results complements these results showing when is -asn--t--ttbiiiiee easy under certain assumptions.
6 Conclusion
In this paper, we examined the necessary and sufficient conditions for the stabilization of a partially observable LTT system and proposed a novel SVD-based robust controller design framework. Future work includes studying the transfer function from the process noise wy to yt, and improving the complexity bound in Theorem 5.3

---

7 Acknowledgement
This work is supported in part by NSF 2154171, NSF CAREER 2339112, CMU CyLab seed funding, in part by by grant from the Commonwealth of Pennsylvania, Department of Community and Economic Development, in part by National Science Foundation under Grant No. 2442948, and in part by the Department of the Navy, Office of Naval Research, under award number N00014-23-I 2252. The views expressed are those of the authors and not reflect the official policy or position of the US Navy, Department of Defense or the US Government.
References
[1] Yasin Abbasi-Yadees and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 1-26, Budapest, Hungary, 09-11 Jun 2011. PMLR.
[2] L. V. Ahlfors. Complex Analysis. McGraw-Hie Hill Book Company, 2 edition, 1966.
[3] Randal W. Beard, George N. Saridis, and John T. Wen. Galerkin approximations of the generalized hamiiton-jacobi--ellnna equation. Automatica, 3312222119-22777, 1997. ISSN 0005- 1098. doi:
1098(97)00128--)
[4] Julian Berberich, Johannes Köhler, Matthias Muller, and Frank Allgöwer. Data-driven model predictive control with stability and robustness guarantees. IEEE Transactions on Automatic Control, PP:1-1, 06 2020. doi: 10. 10.1109/AAC.22203000011
[5] Leila Bouazza, Benjamin Mourllion, Abdenacer Makhlouf, and Abderazik Birouche. Controlla- bility and observability of formal perturbed linear time invariant systems. International Journal of Dynamics and Control, 9, 12 2021. doi: 000077/404330021-00777888
[6] Steven Bradtke, B.Erik Ydstie, and Andrew Barto. Adaptive linear quadratic control using policy iteration. Proceedings of the American Control Conference, 3, 09 1994. doi: 10.1109/ 199.1999.735224
[7] Han-Fu Chen and Ji-Feng Zhang. Convergence rates in stochastic adaptive tracking. Interna- tional Journal of Control, 49(6): 1989. doi: 10. 10.188000201139085597722
[8] Kaiwen Chen and Alessandro Astolfi. Adaptive control for systems with time-varying parameters. IEEE Transactions on Automatic Control, 66(5):1986-2001, 2021. doi:
10.1109/TAC.2000..00
[9] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. CoRR, abs/2007.06650, 2020.
[10] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only VT regret. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 1300-1309, PMLR, 09-15 Jun 2019.
[11] Claudio De Persis and Pietro Tesi. Formulas for data-driven control: Stabilization, optimality, and robustness. IEEE Transactions on Automatic Control, (5(3):909-922) 2020. doi: 10. 109/ TAC.2019.2959924
[12] N. al. Dean S. Mania, H. Matni. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20:633-679, 2020. doi: https://doi.or//1111007/ s (0008-019-09426-2
[13] Geir E. Dullerud and Fernando Paganini. A Course in Robust Control Theory. Springer, New York. NY, 2000.
[14] Mohamad Kazem Shirani Faradonbeh. Non-Asymptotic Adaptive Control of Linear-Quadren Systems. PhD thesis, University of Michigan, 2017.
10

---

[15] Salar Fattahi. Learning partially observed linear dynamical systems from logarithmic number of samples. In Ali Jadbabaie, John Lygeros, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire J. Tomlin, and Melanie N. Zeilinger, editors, Proceedings of the 3rd Conference on Learning for Dynamics and Control, volume 1 144 of Proceedings of Machine Learning Research, pages 60-72. PMLR, 07 -08 June 2021.
[16] Maryam Fazel, Rong Ge. Sham M. Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator, 2019.
[17] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
[18] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, USA, 2nd edition, 2012. ISBN 0521548233.
[19] Yang Hu, Adam Wierman, and Guannan Qu On the sample complexity of stabilizing systems on single trajectory. In Neurips, pages 1-2, 2022. doi: 10.1 1..11199//1/rre M10///lllloo44933322229999444449
[20] Morteza Ibrahimi, Adel Javanmard, and Benjamin Van Roy. Efficient reinforcement learning for high dimensional linear quadratic systems. In Neural Information Processing Systems, 2012.
[21] Joao Paulo Mansch-Porto, Bin Hu, and Geir E. Dullerud. Policy learning of mdps with mixed continuous/discrete variables: A case study model-free control of markovian jump systems. CoRR, abs/2006.03116, 2020. URL /ttptttt/////tttt/ /ttp::::///aiiiioo////aabsas/ bbsgg/bb///ue /206 03116
[22] Zhong-Ping Jiang and Yuan Wang. A converse Iyapunov theorem for discrete-time systems with disturbances. Systems & Control Letters, 45(1):49 58, 2002. ISSN 0167-6911. doi:
[23] Joe Juang and Richard Pappa. An eigensystem realization algorithm for modal parameter identification and model reduction. Journal of Guidance Control and Dynamics, 8, 11 1985. doi: 10.2514/3.2003.
[24] Karl Krauth, Stephen Tu, and Benjamin Recht. Finite-time analysis of approximate policy iteration for the linear quadratic regulator. Advances in Neural Information Processing Systems, 32, 2019.
[25] S.M. Kusii. Stabilization and attenuation of bounded perturbations in discrete control systems. Journal of Mathematical Sciences, 2018. doi: http:///....g//1100000//01050010
[26] T.L. Lai. Asymptotically efficient adaptive control in stochastic regression models. Advances in Applied Mathematics, 7(1):23 45, 1986. ISSN 0196-8858. doi: https://doi.or//10.101 0196-888 1196-8858(86)9000473
[27] Tze Leung Lai and Zhiliang Ying. Parallel recursive algorithms in asymptotically efficient adaptive control of linear stochastic systems. SIAM Journal on Control and Optimization, 29 (5):1091-1127, 1991.
[28] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Explore more and improve regret in linear quadratic regulators. CoRR, abs/2007.12291 2020. URL https://arxiv org/ abs/2001 12291
[29] Bruce D. Lee, Anders Rantzer, and Nikolai Matni. Nonasymptotic regret analysis adaptive linear quadratic control with model misspecification, 2023.
[30] Yingying Li, Yujie Tang, Runyu Zhang, and Na Li. Distributed reinforcement learning for decentralized linear quadratic control: A derivative- free policy optimization approach. IEEE Transactions Automatic Control, 67(1)):6429 6444, 2022. doi: 10.1109/TAC.2221.3
[31] Wenjie Liu, Yifei Li, Jian Sun, Gang Wang, and Jie Chen. Robust control of unknown switched linear systems from noisy data. ArXiv, abs/23 1 1. 1300, 2023.
[32] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
11

---

[33] Samet Oymak and Necmiye Ozay. Non-asympiotic identification of Iti systems from a single trajectory. 2019 American Control Conference (ACC), pages 5655-5661, 2018.
[34] Samet Oymak and Necmiye Ozay. Non-asymptotic identification of Iti systems from single trajectory. 2019 American Control Conference (ACC), pages 5655-5661, 2018. URL https
//api. Seppi.semanticom www.wlar...c.cc.cccooooo..oa.... org/ Terg/CorpusIDD 492750779
[35] B. Pasik-Duncan. Adaptive control [second edition, by karl j. astrom and bjorn wittenmark, addison wesley (1995)]. IEEE Control Systems Magazine, 16(2):87-, 1996.
[36] Juan C. Perdomo, Jack Umenberger, and Max Simchowitz. Stabilizing dynamical systems via policy gradient methods. ArXiv, abs/21 10.06418, 2021.
[37] Jing Sun Petros A. Ioannou. Robust adaptive control. Autom., 3765):793-795,2000
[38] Orestis Plevrakis and Elad Hazan. Geometric exploration for online control. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 97817 7781713829546.
[39] Mehran Pourgholi, Mohsen Mohammadzadeh Gilarlue, Touraj Vahdaini, and Mohammad Azarbonyad. Influence of hankel matrix dimension on system identification of structures using stochastic subspace algorithms. Mechanical Systems and Signal Processing. 186: 109893, 2023. ISSN 0888-3270. doi: https://doi.org// 10. wttp///0..0116j.....o (016///ymssspp wwsp.mmsspppp....mmmmmmm 2222. 109893.
[40] Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, 2018.
[41] Tuhin Sarkar, Alexander Rakhlin, and Munther A. Dahleh. Finite-time system identification for partially observed Iti systems of unknown order. ArXiv, abs/1902.01848, 2019.
[42] Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system identification. Annual Conference Computational Learning Theory, 2018.
[43] Yue Sun, Samet Oymak, and Maryam Fazel. Finite sample system identification: Optimal rates and the role of regularization. In Alexandre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 16-25. PMLR, 10-11 Jun 2020.
[44] Anastasios Tsiamis and George J. Pappas. Linear systems can be hard to learn. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2903-2910, 2021. doi: 10.1109/
[45] Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Annual Conference Computational Learning Theory, 2018.
[46] Wei Wang, Xiangpeng Xie, and Changyang Feng. Model-free hnriz-oorizon optimal tracking control of discrete-time linear systems. Appl. Math. Comput., 433(C), nov 2022. ISSN 0096- 3003. doi: 10. 002. 127400.
[47] Yu Xing, Benjamin Gravell, Xingkang He, Karl Henrik Johansson, and Tyler H. Summers. Iden- tification of linear systems with multiplicative noise from multiple trajectory data. Automatica, 144: 10486, 2022. ISSN 0005-1098. doi: https://doi.orr// 10.10/66...ooaatica. 12200011222222 10486.
[48] Xiong Zeng, Zexiang Liu, Zhe Du, Necmiye Ozay, and Mario Sznaier. On the hardness of learning stabilize linear systems. 2023 62nd IEEE Conference on Decision and Control (CDC), pages 6622-6628, 2023.
[49] Kaiqing Zhang, Bin Hu, and Tamer Basar. Policy optimization for H2 linear control with Hoc robustness guarantee: Implicit regularization and global convergence. In Alexandre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 179-190. PMLR, 10-11 11 Jun 2020.
12

---

[50] Ziyi Zhang, Yorie Nakahira, and Guannan Qu. Learning to stabilize unknown LTI systems on single trajectory under stochastic noise. In The 41st Conference on Uncertainty Artificial Intelligence, 2025.
[51] Yang Zheng and Na Li. Non-asymptotic identification of linear dynamical systems using multiple trajectories. IEEE Control Systems Letters, PP:1-1, 12 2020. doi: 10.1109/LCSYS. 2020.3042924.
[52] Yang Zheng, Luca Furieri, Maryam Kamgarpour, and N. Li. Sample complexity of linear quadratic gaussian (lgg) control for output feedback systems. Conference on Learning for Dynamics & Control, 2020.
[53] K. Zhou and J. C. Doyle. Essentials of Robust Control. Prentice-Hall, 1998.
13

---

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: The main claims in the abstract and introduction accurately reflects the main contributions, which is later more formally stated in main theorem and justified by proofs and simulations in the appendices.
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 be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper extensively discusses the limitations of this branch of studies and discusses each assumption separately.
Justification:
Guidelines:
The answer NA means that the paper has 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 separate "I "Limitations" section in 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
The paper offers an explicit statement of assumptions as well as a full proof.
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 be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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 not)?
Question:
Answer: [Yes]
Justification: The code is attached to the submission, which exactly reproduces the desired result. In the simulation section, we also extensively discuss how to reproduce the result.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is attached in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httpa///guddeee/eeeeabiiissssss /Cc////oddiiisssseeeeeee ssi.soliccyyyyyc.ccc for more details.
The authors should provide instructions on 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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 understand the results?
Answer: [NA]
Justification: This paper does not include experiments using outside dataset.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, 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: The graphs contain shaded areas reflecting standard deviation above and below average.
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 error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
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 enror 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 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 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: [Yes]
Justification:
The experiment simple and not device-dependent.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of 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 or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////aaaaap.cc.cooppo///ttta
Answer: [Yes]
This is a general-purpont paper and does not have any immediate ethical interpretation.
Justification:
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: This paper is for general control theory and does not have any immediate social impact.
Guidelines:
The answer NA means that there is 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.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper contains no risky data.
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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:
This 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/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This 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 in the main paper.
According the NeurIPS Code of Bthies, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does 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 on 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper does not involve LLM usage.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpar////eeippppeeeeee hwt/o//oeeeennce///22202200 for what should or should not be described.
A
Simulations
length ofeample Fraedory
500
Mo Kulrran Spm
length of cample trajectory
250
Ka
of trajectory
250
San
250
Sua
200
200
150
150
1:0
100
100
100
50
20
0
dimonsion [n]
climension (h)
state dimenalon (1)
(a) a 0.4
(b) σ = 0.6
(c) 0.8
The above figure shows the length of rollouts needed to identify and stabilize an unstable system with the unstable dimension k- = 5. The solid line shows the average length of rollouts the learner takes to stabilize the system. The shaded area shows the standard deviation of the length of rollouts. The proposed method requires the shortest rollouts and has the smallest standard deviation.
Figure 1:
number sample Irojedtoy
500
propceed govitm
30033966 akg//fmm
number trajectory
propooed siportrr
600
Sun
500
800
500
400
600
200
600
number
200
200
16
20
30
16
20
25
15
20
state cimension (n)
state dimmnsion (n)
state dimersion [n]
(a) 0.4
(b) 0.6
(c) 0.8
Figure 2: The above figure shows the number of rollouts needed to identify and stabilize an unstable system with the unstable dimension & The solid line shows the average number of rollouts the learner takes to stabilize the system. The shaded area shows the standard deviation of the number of rollouts. The proposed method requires the least number rollouts and has small standard deviation.
In this section, we compare our algorithm to the two existing benchmarks: nuclear norm regularization in Sun et al. 43 and the Ho- Ho-Kalman algorithm in Zheng and Li [51). We use more complicated system than
Ti+1 = Ax, + Bu: + We
(26)
3/2 = Cx, + Du: + Vt.
where there are both process noise w. and observation noise Us. we fix the unstable part of the LTT system to dimension 5, i.e. k 5, and observe the effect of increasing dimension n on the system. For each dimension n, randomly generate matrix with & unstable eigenvalues X; unif(1.1,2)
20

---

and n - k stable eigenvalues A, un, 0.5). The basis for these eigenvalues is also initialized randomly. In both parts of the simulations, we fix m 4 and = 9 T-4 for the proposed algorithm, LTS-P.
In the first part of the simulations, we fix the number of rollouts to be 4 times the dimension of the system and let the system run with an increasing length of rollouts until stabilizing controller is generated. The system is simulated in three different settings, each with noise Wt, 0t ~ (N0,, o), with o = 0.4. 0.6, 0.8. For each of the three algorithms, the simulation is repeated for 30 trials, and the result is shown in Figure] I The proposed method requires the shortest rollouts. The algorithm 4 roughly have the same length of rollouts across different dimensions. This is to 43 only uses the last data point of each rollout, so a longer trajectory does not generate more data. However, unlike the proposed algorithm, Sun et al. [43] still needs to estimate the entire system, which is why it still needs a longer rollout. The length of the rollouts of Zheng and Li [51] grows linearly with the dimension of the system. We also see fluctuations of the length of rollouts required for stabilization in Figure I because the matrix generated for each has a randomly generated eigenbasis, which influences the amount of data needed for stabilization, as shown in Theorem 5.3 Overall, this simulation shows that the length of rollouts of the proposed algorithm remains (poly(k)) regardless of the dimension of the system n.
in Sun et al. be expected, as Sun et al.
In the second part of the simulation, we fix the length of each trajectory to 70 and examine the number of trajectories needed before the system stabilizes. We do not increase the length of trajectory in this part of the simulation with increasing n, since Sun et al. does not show significant performance improvement with longer trajectories, as shown in the first part of the simulation, so it would be an unfair comparison if the trajectory is overly long. Similar to the first part, the system is simulated three different settings and the result shown in Figure 2 Overall, the proposed method requires the least number of trajectories. When the 2 k, the proposed algorithm requires a similar number of data with Zheng and Li [5T], as the proposed algorithm the same to that in Zheng and Li [5]] when k n. When n > k, the proposed algorithm outperforms both benchmarks.
4 only uses the last data point, and
Stabilization probability
55
0.9
50
0.8
length of trajectories
40
08
35
0.5
30
0.4
15
0.1
10
10
20
40
50
60
number trajectories
Figure 3: The above figure shows the probability of stabilization for randomly generated matrix with n = 15 and 5.
In the last simulation, we fix a randomly generated matrix with dimension n. = 15 and an unstable subspace of dimension = 5. We further set the variance of the process and observation noise to = 0.4. As shown in Figure 3 the stabilization probability is most enhanced by adding more trajectories, but longer trajectories also demonstrate a significant effect for stabilization, as proven in Theorem 5
21

---

B Proof Outline
In this section, we will give high-level overview of the key proof ideas for the main theorem. The full proof details can be found in Appendix C (for Step 1), Appendix (for Step 2), and Appendix E (for Step 3).
The proof is largely divided into three steps following the idea developed in In the first step, examine how accurately the learner can estimate the low-rank lifted Hankel matrix H. In the second step, examine how accurately the learner estimates the transfer function of the unstable component from H. In the last step, we provide stability guarantee.
Proof Structure.
Section 3
Step 1. We show that i/ obtained in 19 is an accurate estimate of H.
Lemma B.I. With probability at least - 8, the estimation H obtained in 19 satisfies
| = û -1-1i ii| < : + 2
where ē is the estimation error for || Hll that decays in the order of O vM): ; the enror
11 H1 that decays in the order of O(( (Autala ym²). See Theorem C.2 and Lemma C.3 for the exact constants.
We later (in Step 2. 3) will show that for sufficiently small e, the robust controller produced by the algorithm will stabilize the system ( We will invoke Lemma at the end of the proof in Step 3 to pick m, P. 9, M values that achieve the required (in Appendix
Step 2. In this step, we will show that N1. R, CQ1 can be estimated up an error of Oe)) and up
similarity transformation, given that I H <.
Lemma B.2. The estimated system dynamics N₂ satisfies the following bound for some invertible
matrix S:
4LczE
C10min (m) EN-
where 02 Ci are constants depending on system theoretic parameters, and Ōmin (m) is quantity that grows with m. See Lemma for the definition of these quantities.
Lemma B.3. Up to transformation Š (same as the one in Lemma B.2 we can bound the difference between C and the unstable component of the system CQ1 as follows:
||q, [cs <2
4c
Emin (m) CC.
C1 c10min (m)
where Eain (m) is a quantity that grows with m defined in Lemma D.I Lemma B.4. Up to transformation 5-2 ($ is the same as the one in Lemma B.2 we can bound the difference between B and the unstable component of the system R2 B as follows:
(- O2L
Rí B 5- <8
Ci (m) (())mi))))
+ Ounin Omnnn(m)
e e
Step 3. We show that, under sufficiently accurate estimation, the controller (x) returned by the algorithm stabilizes plant F(2) and hence (=))) is well defined. This is done via the following helper proposition.
Proposition B.5. Recall the definition of the estimated transfer function in 25 Suppose the estimation errors EN, EC,EB EB are small enough such that sup F(2) F(z) c.. Then, the following two statements hold: (a) If K(2) stabilizes F(z) and [2<2)) < 2.2 then K(2)
stabilizes plant F()) well; (b) similarly, (22) stabilizes F(2) with [1) (=))ll c.'
then K(2) stabilizes plant F(z) as well.
22

---

Then, we upper bound [ and use small gain theorem (Lemma 3.1 to show that the
stable mode (z) does affect stability either, and therefore, the controller K (z) stabilizes the full
system, F (2) in (4). Leveraging the error bounds in Step 2 and Step 1, we will also provide the final sample complexity bound. The detailed proof can be found in Appendix
C Proof of Step 1: Bounding Hankel Matrix Error
To further simplify notation, define
Y (y(0)
g(m))
(27)
U (U()
(28)
[w())
(29)
so 17 can be simplified to
+ arg
min XER
YY - XU
(30)
respectively. An analytic solution to 330 is क
yut, where U U (UU*)~1 is the right
psuedo-inverse of U. In this paper, will use + recover H, and bound the error between M and fr.
① - + YU"
(Y (Y-) -DU*(U?)~
(31)
where the third equality used [6). We can bound the estimation error (31 by
i Φb $ ((U0*) ||U*
(32)
We then prove a lemma that links the difference between and Hankel matrix H.
Lemma C.1. Given two Hankel matrices H H. constructed from t Φ with respectively, then
H <
Vmin(p.g)
$
2+m:T
2+
Proof. From the construction in 4
18 we see that each column of H H is submatrix of
m+ then
2+meT
H
/
$ 2+m:T
(33)
2+m:
Similarly, each row of H
H is submatrix of t
$ o 2+m:T.
Therefore,
2+m.T
H H
$ 2+m:2
(34)
24m:T
Combining 333 and 34) gives the desired result.
then bound the gap between (k) and Å by adapting Theorem 3.1 of Zheng and Li [5]] For completeness, put the theorem and proof below:
Theorem C.2. For any 8 > 0, the following inequality holds when M > 8d,,T + 4(d, + dy + 4) (3T(3)88) with probability at least
80, 80, TTT T(T
() dry min q) log (777/))
| 11 A <
oa V
23

---

Proof. By Lemma
C.I
we have
H Ht
S /miinp. of
@2+m: 1 2
Bounding |I(UU*)|| and ||oU*||| with Proposition 3.1 and Proposition 3.2 of [5]] gives the result
in the theorem statement.
Lemma C.3.
11 -1-11 -1 S Vap S L3( M + )m ;=
2
Proof. We first bound H and A entry-wise,
Has Hig =CAm+itj-2 - CQ1 B
=C(Q) R1 + Q2 N2 N22 N R2) CQ1 C N R B
=CQ2N2 2 R2b
Applying Gelfand's 's formula (Lemma H.2 we obtain
Hii Mus s |B | (N22 + E4) m < L3( Ae+1l / m (35)
Moreover, we have the following well- dell-known inequality (see, for example, [7]), for A E R Rm1x*e,
||||
||lll S vT2 //
(36)
n1
Applying (36 to (35) gives the desired inequality.
We are now ready to prove Lemma B.1
We first provide a bound on A -. As H is the rank-k approximation of H,
Proof of Lemma B.1
we have
||
f
H S
then
H A 7
(37)
where we use Theorem C.2
and Lemma C.3
Therefore, we obtain the following bound
H
H
H
+
A H
H H ||| 28
(38)
D Proof of Step 2: Bounding Dynamics Error
In the previous section, proved Lemma B.1 and provided bound for || HI. In this section, we use this bound to derive the error bound for our system estimation. We start with the following lemma that bounds the difference between Ô and Ó and the difference between and Ć up to transformation.
Lemma D.1. Given N1 is diagnalizable, and recall N1 = PIAPT' denotes the eigenvalue de- composition of N₁, where = diag(Ai,.... Xx) is the diagonal matrix of eigenvalues. Consider Å ÔC and A ÖC, where we recall Ô,C are obtained by doing SVD A Ú$:²* and setting Ô 12 č $3/25" (cf. (0 Suppose ||A = H H < e, then there exists an invertible k-by-k matrix such that
(a) 0 05| < @ and l
<
Janin (
24

---

(b) there exists c1, > 0 such that 0j1 1 I 02l, where given a, Jg in 49
et =
2v2
0, min P1))
2 max (2))2
(c) we can bound minn (Ö) and Omin (C) as follows:
min (Ö) 2 min (Ō1aa) 2 mmin (oob) min (NTr/3) = Ōmin (m); (m).
min (C) min (C1:a) 2 Omin ( u (NT"/²) == Euii (
Proof. Proof of part(a). Recall the definition of H
A II +i4s Rí (.e.0....-11).E110....
NT
CQIN
N R
+4-1 N
B
CQIN +T-1
We can represent Ô and é as follows:
CQ1R
A
CQ1P
=
PTL.
(39)
-
CQ P1
PT B
Č = [A
A
(40)
B
:=G
Next, note that
- -c 0C AH = G Ah.
(41)
Therefore, we have
G.G.G2 US+ P AnG2
00 V AnG + = G.P. = (G -GG
(42)
where we have defined the matrix above. We can also expand as follows:
= -=
-CC
(43)
Further, the last term in the last equation (42 can be written as,
AnG2(G,,2) -1p-1
APC
-
(44)
25

---

Putting (2 44
together, we have
0 0s 1 mC)
G
(45)
which proves one side of part (a). To finish part(a), are left to bound | - 8-10/ With the
expression of in 43 we obtain
- - - =1Ic
Let E = 0$ Ó 0 = 0$
E. By
42 and 44
obtain
E AnC" (
(46)
and
Ec| A S..
Therefore, can obtain the following inequalities:
< 00 - oc| |0s E)č E)Č-óć] 1 C) Eē| 2 00(sc- [c]
+ - 5-0-
2E
+ ||e 5-1c|
2
2
m (Ö$)
Omin (0)
- Ö O$
Substituting (45). get
- 5
2c
Minn (Õ)
Mmin (O)
(c)
where the last inequality requires
<<
2 7 (omin(O)onna mm)o (C).
(47)
which we will verify at the end of the proof of Theorem 5.3 that our selection of algorithm parameters guarantees is true.
Proof of part(b). We first examine the relationship between G1 and G2. Recall a is the maximum of the controllability and observability index. Therefore, the matrix
B B
B (P.
du a
B' (P (1
which is exactly Poon (Pt)-1, is full column rank. For any full column rank matrix Т, let's = -I' "T" denote its Moore-Penrose inverse that satisfies I&r I. With this, for non- negative integer j we define the following matrix, which essentially [Gl]jo-f+1)o--1 "divided by" [G2)sar(++)a-11 the Poore-Penrose sense:
CQ PAA tja CQ +j041
B' B
(AA
26

---

CQI CQIPA
( B' (PT P'
A t 13 (A-3
(48)
B (
Po
=9 (P)-1)-!
As in the main Theorem 5.3 we assumed the Ni is diagonalizable, A is diagonal matrix with possibly complex entries. As such, 2 +Jo (A "10" is a diagonal matrix with all entries having modulus I Therefore, we have
mmin
(5
( CB
max (Goon) min (P1)2 == Cs
(9ob)
(49)
max (9bb)
max
(S
CB
miin (Gcon)
max (P1)2 0.
for all j. Recall the condition in the main theorem 5.3 requires p q. Without loss of generality, can assume a divides and then G1 and G2 can be related the following way:
CB
((1)
G1
CB
G2.
(50)
S CB
SeB
With the above relation, we are now ready to bound the norm S. We calculate
(51)
If examine the middle term VÊVV expand it as
-(VSÚ- -(A A
=((H + AH) (H + An))
(52)
Using Lemma H.3 on 52
we obtain
1 f VIVe
(,ayya ) > (2(( Am) subsitute
(GGGG AMAA) RVVV~ 3 (2G,G C A2
C 4MAH >V 2 AAA
substitute 50
Therefore, we can bound V
2 el VVV* /20 + V2eT
(53)
'This the only place where the diagonalizability of N, used the proof Theorem 5.3 If N is not diagonalizable. A will be block diagonal consisting of Jordan blocks, and still bound A m
(A m -jay
with dependence on the size of the Jordan block. See Appendix for more details. 'I' does not divide or g. then the last block in (5)) will take a slightly different form but can still be bounded similarly.
27

---

where we used I N SCBBBB I and min (SCB) 2 o, as SeB is the Block-diagonal matrix
of (() (ef. 449.. 50
Therefore, plugging (3) into b1p we are ready bound S S has follows:
S-5 PP
- (CC
20 2 + V2((C)))
(54)
J
2c
I.
Mmin (Pi)2
min (C)2
Similarly,
5-52
a 20 (P))
I.
(55)
Jmin mmin(C)2
If we further pick such that
0 m min (c)2
σ T (c)2
6 S min(
=cgomin
(56)
2020 max (P))2*
2 min (P))²
54 and 55 can be simplified as
2
S* 2222
0x m Pi )
(57)
2 20 max P1)
o
Proof of part (c). Observe that Ö1..- Gob NTm/ Therefore,
min (Ö) min (01:a) 2 Jmin (G (NTH == Ōmin 0m))
Similarly, we have
Umin (C) 2 Tuin (C1:a) 2 Tmiu (Ccom) J
m (NTT)/2) == Eaiin (m).
We are now ready to prove Lemma B.2
Proof of Lemma B.2 Let F. = Ô ÔS, by Lemma D.I
|||
<
Moreover, Ö1.p-1
(C)
11 + Fi.p-1 and Oz. O2.5 + E2.p- Given that Ö2.p O1p-1N1 we have N1
( 1:p--)) i.p-- O2.p. where we have used by the condition in the main theorem,
122
(58)
so that Ö1.p-1 is full column rank. Recall N₁ is estimated by
Ñ = (::0--100)11) 1'0pp
(59)
Given that Öz.p = Ö1:p 01:p-1N1 we have
Ō2 F2, 101 Frisp-1) N₂
(60)
+ O2.p + E2, 3-1 = 0 11.--15N11- + E1.--1N,8-1
(61)
+ 2:p O 1.p-111 1
$-1 +
(62)
where E. : S E2, 8-1 Substituting 62 into 59
we obtain
Ni 11.p-101.--1) ) Oi.p-1 ( SN + E)
= - + (0 01pp1111p-11 :
28

---

Therefore,
| - s-S
3 8 3 -0 (1p-1) - -
8-
1) O -- (ki:p- -
mm (01 (1 + L)
2Le
(S (m²)
Ö - 08
4Loze
C10min (m)
where the last inequality requires 47
Following similar arguments from the above proof for the estimation of N following collarary.
1,0
in
we have the
Corollary D.2. We have
1 1- N- T
4cze
S
CJ Cimmin (m)
Proof. Let E = = - ÔS, then |
Moreover, 11:p- -1.--7
7 S Eig- 7
mmild))
and Ô 4 +l: = Ö st 11:p + Exp +1p-- Given that ② = O1p- y N we have N₂²
(Oi ÖLP- 4) - 1sp- 5
① tlpps where we have used by the condition the main theorem,
p 2 2
(63)
so that Ó1p-3 v is full column rank. Recall in 22 we estimate N ~ by
N No, ( y δ 1pp )
Ó m -1pp
(64)
Given that θ T 1:pp Ô bp y N1¹ we have
Ô 4 1: $ + E (01p- 4 S + E1.p 4 N1
(65)
* 0 7 11p + E - 1 5-1 = =01 r SN S-1 + Elp- y N S-1
(66)
0 7 11p = 6 o SN t S + E,
(67)
where E. : Eip- 7 N₂²
7 S
E + +1:p و 1. Substituting 67 into 64
we obtain
N (Ó θ Ó 4) )
- -
ip- m (0 4 SN 2 S- + E)
(68)
SN 8-1 + (0; i T
Ö x - -'0 E.
(69)
Therefore,
1 - 8-1 S T
= | 1:p- 4 3 -
1:p- ESN "
$ ( 1:p- T Ó ( 1
(Er.p- yp NN, m
5-1 - E 1 J'N 77
1:p-- 7
Avl +1 1
1 L(
4
01 min (Ô (1ppp-g)) 4)
2 C1 mmi (Orsp- )
(70)
29

---

2f e| O (5-i)) (m) - - ō
2
C1 min -
Omin (C) C)
4c26 C1 mmin (m)
(71)
where 770 requires
log L)
m
(72)
log(
which we will verify at the end of the proof of Theorem 5.3 and (71)
requires (47)
By using an idental argument, we can also prove similar corollary for N 1,C
The proof is omitted.
Corollary D.3. Assuming p, > 2 + I, we have
r N1 $ N
4cge
C1 Emin (m)
With the above two corallaries, we are now ready to prove Lemma B.3
Proof of Lemma B.3 By the definition of Ô in 7 we have
Ô CQ
(73)
Furthermore, we recall by the way Ć is estimated in 24 obtain
Ö CN
(74)
Let Eo, = Ó, Substituting it in 74 leads to
= 0 Eo, CN + Eo.
Substituting in 77 we have
CQINT = CN + Eo.
+ CQQ C-Š--S11 SN Eo,
(75)
By Corollary D.2 we obtain
|CQ -00--sh
< C$
8 -N S.NNSNN m/2
+11..111 / /
||
|
402e
+ +||E,
aimia (m)
OS
402
+
Eaita (m))
1
(76)
(1ōmin(m)
4oz (| CQ:
c$ + 1+0Q11ll)
1
(77)
C| Ciōmin (m1)
Emin Emin
4czL
(78)
CJ Ömin (m)
Emin (m)
where 766 is by Lemma D.I and requires (22). and
78
requires
C1 Cmiin (m)
(79)
802
30

---

The proof of Lemma B.4 undergoes a very similar procedure.
Proof of Lemma B.4
By the definition of Ć in we have
C N1² B.B.
(80)
Further, by
24 have
č = N N....
(81)
Let Ec, = Ei - S--CC, Substitute in (81). we get
c= + Ec, = SN-IN B + Ec.
Substitute in 80
we obtain
N 3 R.B = S- N1, + Eci
=yB=N " 5- N N S B + N1 7 Ec.
(82)
By Corollary D.3
we obtain
B 5-18
< Ni #S-1N 1,0
S
- f|||5-18)
+ Ni 7
| |Ecll
C2 S-1 B
1
4
+
(83)
e)Cmin (m)
Ōmin (m)
c2( RiB - S
+ +1IBBB
1
S 4
(84)
C (m)
m (m)
C2L
< 8
(85)
C1 Emiu (m)
mmin (m)
where
83 is by Lemma D.I and requires
(72). and 85
requires
C1 Emi (m)
(86)
8C2
E
Proof of Step 3
Before we analyze the analytic condition of the transfer functions, we need to analyze the values of F(z) and F()) on the unit circle through the following lemma: Lemma E.1. We have
sup ( Ax - (SL'EC+ + 4L |=|=1
+ +L
Ax -1
Proof. We have that
sup
F(x) F(z)
sup
(1|oŠ(21-
< sup 1=|-1
+ || + -0000/1111000-3---000-0---------
R1
- [|e3--colllaa----k333331111111
< sup |==1
31

---

+ +I(CQ((#T-N1) || B
(87)
Moreover,
N - -||ss N1 -1=
-1)
(88)
Substituting (8) into 887
we obtain
[())
F(=)
sup
[| lew S-'Ni -1
cc
Mo
|=|=1
+ca +c11|(Q((21-N1)))
I sup
- ||lp::/|||aaailo---00//0/11111-- -[ No) N11
[(1 -1(08)
|=|-1
(89)
- N1) N1) || 4|0Q, 1 N:) - (=1
$ sup |=|=|
(90)
where
89
requires
(zl (zl-Ni, N1 No S-1N
Ni - N,
m mmin (=1-NN = 2 (z) -N)-1111 I|| which in turn requires, by Lemma B.2
Omin (=I N1.
(1mmiu( (m)
inf o min (2l NN) E 0min (m) |x|=1
EN S inf min (=l N1)
E E 8L0z
(|>x)
-1),
|1|=1
8L202
(91)
where the last step uses inf[ miia (mi N1)
11 Eq.
90 uses
sup/s/-1 (aI- 1T
-
[R.
+ teB S 2L, which requires
e < min( (m) L
EB S L
Omin mmin(m)) (m)).
(92)
16 12l.
16
We will verify (11 and our choice of algorithm parameters. Lastly, substituting max(] [ [CQill) s L and using
92 at the end of the proof of Theorem 5.3 to make sure it is met by
sup|=/=1 [[ N S i give the desired result.
We are now ready to prove Proposition
B.5
Proof of Proposition B.5 We only prove part (a). The proof of part (b) is similar and is hence omitted. Suppose K(2) is a controller that satisfies the condition in part(a). Our goal is to show this K (=) stabilizes F()), or in other words, Fx (z) is analytic on C21- Let Ar(=) = F(z) - F(z), we have
I (()) =I -()))(()) (()))((=))
+
(())
Note that to show that (1- (())(=)(=)))++ is analytic on C21, we only need to show (1 (I-F(z)) (=) has the same number of zeros on C21 as that of I (())))((2)) because we know (I (I-F(z)K(z)) is non-singular (i.e. has no zeros) on C21. Given (Р)). we also know 1 - F(2) (2) and 1 - (2) has the same number of poles on C=1. By Rouche's Theorem (Theorem H.4. - F(2) has the same number of zeros on Cz1 as (2)) if
II(T F(=)K(z)) (I (()) < - (()
sup |=|-1
<1
||Ar())]| (=)( [() S sup [[(:) <1, |-|=|
sup
|=|=1
where the last condition is satisfied by the condition in part (a) of this proposition. Therefore, 1- - [()) has no zeros on C21 and the proof is concluded.
32

---

We are now ready to prove Theorem 5.3
Proof of Theorem 5.3
Suppose for now the number of samples is large enough such that the condition
in Proposition B.5 holds: sup|:/=1 [(2) - F()) E.. At the end of the proof we will provide
sample complexity bound for which this holds.
By Assumption
5.2 there exists (=)) that stabilizes F(2) with
1
(=)))<<=)l I [a(=)] Ho + +c.
Therefore, by Proposition B.5 (2) stabilizes plant F(z) as well. Therefore, || [|{()) is well defined and can be evaluated by only taking sup over |z| = 1:
(())) = <(=)(T - (()()-)())(())--11))) Hxx
- |(=) (()) -()))-)))))
sup
|=|=1
[K{)(T - P(OK)
sup
|+|=1
||<()(I - (2))
sup
|=|=1
(I-) ( F())
sup
|=|=1
Fx(E)
FR(:)
sup |=|=1
[K<()) (=)11 Σ IK(
S sup
|=|-|
sup 1 - (x(=)) |=|-1
(=)
Fx
(93)
I))))l + +
where we substituted in Assumption 5.2 in the last inequality. In Algorithm we find controller
(x) that stabilizes F()) and minimizes [2) (=) As K (22) stabilizes F(() and satisfies
the upper bound in (93. the R(=) returned by the algorithm must stabilize F(2) and such that
(=)( (((s))F(((e)) (=)]l H.. is upper bounded by the RHS of (93 By Proposition B.5 we know (x)
stabilizes F22) as well. Therefore, [2 (x)))) is well defined and can be evaluated on taking
the sup over |2| 1:
= | (())- H
[(()(T - F())
sup
|=|=1
|K(=)(I ((())))))
sup
|x|=1
sup
|+|=1
33

---

(T= (())- ( (2))
sup |||=1
Fx(e)
(2(x)
sup ==|=
[(=) (2)
sup Σ
Mo0
[<=))((()
(94)
[R())
1 1-
100
As K (2) is such that x satisfies the upper bound by the RHS in 93 we have
A1=)
+2c.
(95)
1 1
((()) Fx(2)
[3(=)] Hoo
+2c.
|A(2)] Hz + E
|
Ho0
Therefore, by small gain theorem (Lemma 3.1, we know the controller (2) stabilizes the original full system.
For the remaining of the proof, we analyze the number of samples required to satisfy the condition in Proposition B.5 i.c.
F(z) F(2) <E
sup |=|=1
(8T2c0 + 4L-EN
Pdel - + (.ee)) < c.
A
1)
EN
121.
[L -iles
EB
3T
(1 -1le.
EC
24
where the middle step is by Lemma following sufficient condition,
E.1
By Lemma B.2
Lemma B.4 and Lemma B.3
we obtain the
4Lc²
(1al 1)2c.
Cj mmin (m)
1214
CaL
(111l 1)c.
C1êmin (m)
Omin (m))
312
2
402L
1
(1Abl -)e.
C10min (m)
Omin (m)
24T.2
By simple computation, we obtain the following sufficient condition:
ei Emin (m))(Au 1) Ciômin (66min(m)(A4))) - 1)E. Ōmin (m) (1ARl 1)e,
ei c (m) du - I)e.
e < min
1.c2
48c² T33
481,2
384cz T,3
Emin (m) -)e,
961,3
which can be simplified into the following sufficient condition:
min(ōmin (m), 6min(m) min minn(()=]- 11) |Aul - 1)e,
(96)
384c2L5
Moreover, we also need to satisfy 47
56
79
86
91
92
which requires
C1 2mii (m)
CiCmaa (m)
min (m) (m), of Emin (m)²
e
8c2
8c2
(97)
C1 Emmmial ())
ci Ōmiu (m)
L
(DMel 1),
Ōmin (m)
8L2c2
16
C2L
16
34

---

A sufficient condition that merges both 996 and 997 is:
3.5 min(ōmin (m), Emin (m]) minn([Ax|1-)) 112,, |Axl 1) min(e., 1).
(98)
amin (Pa)a, 80 (P1)
Plugging in the definition of eı, 02; Ominn (m), Emin(() have
mini (P. Mo (Gab) (Grom)
<<P2 B where we recall x(.) means the con-
man (P)) 1 ( Junx (Noon)
dition number of a matrix. Further, as I S L 2 jm/2, we have a (NT (NT
{ 2 /m/2 Therefore, the condition (98 can be replaced with the following sufficient condition AM
2/
< V L. min(Cmin (Gob), Jmin (Geon)) (
ym/2 min((1eel -1)², |Ael 1) min(e,, 1).
Au +
(99)
where the I above only hides numerical constants.
To meet (88) 63 we set = = max(a + m m). We also set m large enough so that the
right hand side of (99) is lower bounded by Vm3. Using the simple fact that for 1, am/2 a sufficient condition for
va mam/22 Vami²
m/2 2 1.5 1 ( log loga)".. and replacing a with 2 Ax/+I*
such an m is
VK(Gob)) (Goon)))
m
log
A| |A,l+1
log
min (Gob), o min (Geon) (log [A, )33/2 min 1)2, |Axl min(c.,) 1)
2|
(100)
Recall that = 28 + 2 With the above condition on m. it now suffices to require max(é, é) 2 vm3.
Plugging in the definition of é, 8 Theorem C.2 Lemma we need
M Sd. + 4(d, + d, + 4) log(3T/0)
(101)
80, / T(T () + dy) min(p, o) log (7TT/))
x Vm3
(102)
ou M M
Ak+1 +
L3
m x Vm
(103)
2
To satisfy 102 recall T - + 9 + 2. Let us also require
m 2 2a
(104)
so that q= max aa
, m) m, have T(T + min(p. 9) S m². Therefore, it suffices
to require M 2 [wx) )² (du - dly) log T satisfy [02)
To satisfy
103 we need
log 1
T
(105)
A 2
log
To summarize, collecting the requirements on m 100 complexity on m:
104
105)
and also (72). we have the final
log 1 I | 2
log( ()))t)
m 2 max(a,
(106)
log
log(
2
/m(Goo ) (9oon)))
log
2|Aa| log
min(omia (Sob), mmiu (log 2
3332 min((1A4 1)2, [Awl m)nin 1)
Dx
+1
[x.
(107)
The final requirement on p. 9 is,
q
(108)
35

---

The final complexity on the number of trajectories is
M M - (du + dy) log m
+ d.m
(109)
5
Lastly, in the most interesting regime that A 1, 1,1 - 1 c, is small, we have log 2| x
[a1+1
|& - 1, min(()A
1)2, - 1) (1^xl 1)2. min(er, 1) = cx In this case, (066 can be
simplified:
log L
1
min min (Bob), 0 min (9oon (12x 1)c.) -)..) (110)
x(Gob)
2 max
a,
1x++1 128l -1
log
F System identification when D 0
In the case when D 0 in ① the transfer function becomes
F(z) = D (Q
(111)
and the estimated transfer function becomes F(z) = D + CŠ(=I - S- - so the gap between estimated transfer function and the ground-truth transfer function can be bounded as follows
-(=))f(2)) $ ||p=b]l+|cCr(c N1) B -S
(112)
The second term (112) can be bounded by Lemma E.
Therefore, this section, we focus on providing bound for D D The recursive relationship of the process and measurement data
will change from 14 to the following:
-C( + Dut +
yi
T EC'' (Bul +
(113)
(0) ( + Dut + tuz
1=0
Therefore, we can estimate each block of the Hankel matrix follows:
D
D
CB
CAB
CAT-2B)
(114)
D
0 +
from which we can easily obtain the D matrix and use to design the controller, as in the rest the main text. Fortunately, from 113 we see that t can also be estimated via (17 i.e.
$ arg
min XER dde
-
XUO
(115)
In particular, we see that even the case where D * O. the estimation error of does not affect the estimation of or $. Therefore, the enror bound of N1. N1, R, Lemma B.2 Lemma B.3 Lemma B.4 still holds. The error of estimating D can be bounded as follows:
Lemma F.1 (Corollary 3.1 of (T). Let D denote the first block submatrix in 115 then
1 1D-
L
VM
where L is a constant depending on A,B.C, D, the dimension constants n., m. dus dy and the variance of control and system noise Tu,
Therefore, we have proved a bound in the place of Lemma
E.
The rest of the proof will follow the
same line Appendix
36

---

G Bounding S when Nj is not diagonalizable
In proving Theorem 5.3 we used the diagonalizability assumption in Lemma D.I More specifically, was used in (48) to upper and lower bound A +A - -aa* for j 0, ...., 2. which is reflected the value ss C.- the diagonalizable case, A # (A - is diagonal matrix with all entries having modulus I regardless of the value of j. Now in the non-diagonalizable case, we bound 2 +Ja -Ja)", provide new values for o C.. and analyze how affect the final sample complexity.
Consider
J1
0
0
0
0
J2
0
0
A
0
0
J3
0
(116)
Jky
where ky the number of Jordan blocks, and each J4 is a Jordan block that is either scalar or square matrix with cigenvalues on the diagonal, I's on superdiagonal, and zeros everywhere else.
Without loss of generality, assume J1 is the largest Jordan block with eigenvalue À satisfying [k] 1 and size y, then J1 = Ai + r, where is the nilpotent super-diagonal matrix of I's such that I = for all 2 y. Therefore, we have
J + = (AI +I T+ja
+ja
m 2
+ ja
D X
i
and
3Jay = - - ja
r.) - = =x ja
m +
2
ja
X
where is the conjugate of A. Because A A 4 ja has modulus 1, we have
max E 33 (3+ 5i
maax (J (J )
(117)
Σ7 ( (*t 5i
o min
We then calculate,
+ ja 1
7
m ja
< Σ
2
max
x
1=0
2 + jo
$
$ 7( 2 + ja)
S 72m)²
where the second inequality requires m 4y, and the last inequality uses ja Sp= m. To calculate the smallest singular value, note that Σ (3 +ja) ),xi is an upper triangular matrix with diagonal entries being 1, therefore its smallest singular value is lower bounded by 1. Therefore, we have
Fmax (J (J - S (2m)"
(118)
(J
+ (J _ - 72mm)
(119)
As such, the constants o. C. in need to be modified
σ¹ {2m
(120)
L = a, 7 722))
(121)
37

---

This will affect the sample complexity calculation step in (99) which will become
Ax ym/2 min(([Ax] - 1)² 1Axl min(e.; 1):
V=(0))))((ecm)) (in()min(Goo)) Fmin (
(122)
where the only difference is the additional factor in the denominator highlighted in blue. As this
factor is only polynomial in can merge it with the exponential factor 211xl ym/2 such that
[Axl+I/
2 Acl ym/2 |
2|Ax| log
2/1a| Ax +1
m/2
Pxx
)7
(2m))
8y
Therefore, 100)
will be changed into:
15 Gobb (ro(
m
log
1>g
log
min(Camin (Sab), Amin (Goon) )) (
18g
21
21 )7 (log |AN+T
3//2 min(()Aa] 1)3, Ax 1) min(er,1) (123)
B7
and lastly, the final simplified complexity on m will be changed into
log I
1c ((Gob)) Ly min(Cmiin (Gor), m (9emn) ()(( I)e.
m Z max(a, 1- D
log
(124)
-1
which only adds multiplicative factor in y and the additional in the log, Given such change in the bound for m, the bound for other algorithm parameters p, q, M is the same (except for the changes caused by their dependance m))
H Additional Helper Lemmas
Lemma H.1. Given Assumption 5.1 lable.
( is satisfied, then N1, CQ1 is observable, N1, R2 B is control-
Proof. Let w denote any unit eigenvector of N₁ with eigenvalue X, then
New
Aw
AQ N X(Q1w).
Therefore, Qiw is eigenvector of A. As A, C observable, PBH test, this leads
||CQww]] >
By PBH Test, this directly leads to (N1, CQ1) is observable. The controllability part is similar.
Lemma H.2 (Gelfand's s formula). For any square matrix X, we have
p(X) lim [x| 1/e
[
In other words, for any > 0, there exists a constant (X) such that
T T (X') |X||| - (x)( + e)
Further, if X is invertible, let Amin (X) denote the eigenvalue of X with minimum modulus, then
Dmmin (X)
Gmin (x') 2 (x(x-1)
(1+el el emmin (X)I
The proof can be found in existing literatures (c.g. 18
Lemma H.3. For two matrices H, E. 3
3H 2 2E" E.
38

---

Proof. For the upper bound, notice that
2H" H + + E - + -3
Therefore, we have
(H + (H + E) 3 2H' H + E.
(125)
For the lower bound, we have
H'H = -H+ B)
E) ー 2 Ey (H + +
where in the last inequality, used (25).. Rearrange the terms, we get the lower bound.
Theorem H.4 (Rouche's theorem). Let C. C be a simply connected domain, f and two meromorphic functions D with finite set of zeros and poles F. Let be positively oriented simple closed curve which avoids and bounds a compact set K. If If gi < [g] along % then
Nj Pj Ng Pg
where N, (resp. denotes the number zeros (resp. poles) of I within K, counted with multiplicity (similarly for g).
For proof, see e.g.
I Indexing
For the convenience of readers, provide a table summarizing all constants appearing in the bounds.
39

---

Table 1: Lists parameters and constants appearing in the bound.
Constant
Appearance
Explanation
Section
Length of each roll out.
M
Section
Number of roll outs.
Section
number of open-loop steps for converging to unstable state space. dimension of Hankel matrix to be estimated.
p.
Section
Table 2: System theoretic parameters.
Constant
Appearance
Explanation
H O,C Ō,č
Ground truth Hankel matrix factorization of H.
rank-k approximation of O,C, respectively. rank-k approximation of H.
H
numerical approximation H.
fr
rank-k approximation of H.
6,C
20
factorization of ff.
Gob
Section 5
Observability Gramian Controllability Gramian positive real number such that Fmin
Goon
Section
Ōmin (m)
Lemma
Ömin (m).
Cmin (m)
Lemma
positive real number such that amin
(C) Emin (m)
Appendix 48
Controllability index.
Cc, Cp
modified controllability and observability matrices.
(e(-)
Lemma H.2
Gelfand constant for the norm of matrix exponents
Table 3: Shorthand notations (introduced in proofs).
Constant
Appearance
Explanation
Lemma D.1
Gmax (Rron) Tmin (B)²
Tmin (Goh)
T
Lemma
T. mmin (oonn Tmmx (P))
Gmax (Gole)
CN
Lemma B.2
EN = 016mmtn (ms)
4h.ce
EC
Lemma
B.3
60 2
c) Cinin (m)
E (m)
6B
Lemma B.4
EB =
2j Fanin (m))
cal
T (m))
Assumption
5.2
Lemma B
== 22 + 2
T(T + 1),d. t.y)) (vva) 1og(277/8)
Thcorom
Lemma
7 3
40


Reviews:
[{"review_id": "wHJPeol1J1", "reviewer": "Reviewer_sNGj", "summary": "This paper presents a novel method for obtaining a stabilizing controller for a partially observed discrete-time LTI system, and analyzes the sample complexity of the resulting algorithm. The method is based on estimating the parameters of a lifted Hankel matrix for the system using multiple trajectories with iid control inputs. The estimated Hankel matrix allows for estimating the open-loop transfer function for only the unstable part of the system, which is then used to construct a stabilizing controller for the entire system. In the case where the number of unstable eigenvalues $k$ is much smaller than the state dimension $n$, this decomposition into unstable and stable parts yields better sample complexity than applying previous results on system identification to this problem. Experiments on randomly generated systems validate that the proposed method learns a stabilizing controller with less data in practice.", "questions": "- In the case when $k$ is unknown, the paper describes a procedure for finding $k$ based on the singular values of the estimated Hankel matrix which assumes that the lifting parameters $p$, $q$, and $m$ are sufficiently large with respect to $k$. What happens when this is not the case? Is it possible to mistakenly believe that the true $k$ has been identified (i.e. find a large spectral gap in the singular values that does not correspond to $k$)? I would be inclined to raise my score if I have misunderstood this limitation.\n\n- Do the simulations in appendix A use constant $B$, $C$, and $D$ matrices while randomizing $A$? \n\n- If the simulation results instead plotted the fraction of randomized systems that are successfully stabilized for a given amount of data, can we recover $\\delta$ in theorem 5.3?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: This is a strong paper with a good motivation and clear development of the technical ideas underlying the proposed method. It tackles a problem of practical interest that has not been targeted in prior works to the best of my knowledge. It is also very well-organized and relatively easy to follow. I especially appreciated the notation index that not only defines each term but cites the equation / lemma where each appears! Providing a code repository will make it easy for other researchers to use the method in their own applications. \n\nWeaknesses: One important limitation of the paper is that the method assumes $k$ is known. A procedure for estimating it is presented in the paper, but this method only works when the lifting parameters $p$, $q$, and $m$ are sufficiently large with respect to $k$, which is problematic when $k$ is truly unknown. \n\nMinor weaknesses:\n- Above equation (24), I believe “$\\bar{C}$ and $\\bar{B}$” should read “$\\hat{C}$ and $\\hat{B}$”\n- It would be helpful if the captions in figure 1 and figure 2 were more detailed, including phrases like “at different noise levels $\\sigma$” and “with rollouts of length $T=4n$” (figure 1) or “with rollouts of length $T=70$ (figure 2)\n- Line 498: trails -> trials", "was_revised": true, "final_justification": "The authors did a nice job of rebutting my questions/concerns as well as those of the other reviewers. This is a strong paper and I recommend that it should be accepted.", "rebuttal": "We thank the reviewer for the careful and thorough review and provide the explanation below:\n\n- $\\bar{C}$ and $\\bar{B}$: The notation $\\bar{C}$ and $\\bar{B}$ above Equation (24) are defined in line 202 and 203, which are our estimates for $C,B$ if the Hankel were exactly known. As the Hankel itself is estimated in the actual Algorithm, Eq. (24) are estimated versions of $\\bar{C},\\bar{B}$. \n\n- Unknown $k$: What we can prove is that (a) the difference between the lifted Hankel $H$, and $\\tilde{H}$ is exponentially small (Lemma C.3); (b) $\\tilde{H}$ is formed by a product of a $d_y p\\times k$ and a $k\\times d_u q $ matrix, so its rank is at most $\\min(d_y p, d_u q,k)$; (c) All non-zero singular values of $\\tilde{H}$ is exponentially large in $m$. Therefore, when $p,q,m$ are large, from (b) (c) we know $\\tilde{H}$ will have $k$ exponentially large (in $m$) singular values and other singular values are zero. Then from (a) we know $H$ will have $k$ exponentially large singular values, and all other singular values are exponentially small. This is the singularvalue gap our paper was referring to and how $k$ can be identified from this gap. For your question where $m,p,q$ are not large enough, there are two cases. Case I: If $p,q$ are not large enough such that the rank of $\\tilde{H}$ is smaller than $k$ (i.e. $d_yp<k$ or $d_u q<k$), then by (a) (c) all singular values of $H$ will be exponentially large, and the singular value gap will not be observed. Case II: In the second case, where $m$ is not large enough, then the distinction between the ''exponentially large in $m$'' terms and ``exponentially small in $m$'' will not be obvious, so a large gap is not obvious. To conclude: when $p,q,m$ are not large enough, the singular value gap will not be obvious so one won't mistakenly believe the true $k$ would be identified. Actually, the above discussion also sheds light on how to tune $p,q,m$ to identify the gap.\n\n- Simulation setup: We thank the reviewer for pointing out the issue with the setup in the simulation. In the simulation, $B$ and $C$ are both initialized randomly, where each entry is sampled from an independent uniform distribution between 0 and 1. we still assumed $D = 0$ as discussed in Section 2. Although we discussed how to tackle the case when $D \\neq 0$ in Appendix $F$, We did not have non-zero $D$ in the simulation. \n\n- Regarding $\\delta$: Yes, if we run the simulation a sufficient number of times for fixed $m,p,q$, we can recover the value of $\\delta$. In Theorem 5.3 and Theorem C.2, we use $\\delta$ to show that longer trajectories would have better chances of finding accurate Hankel estimation. \n\nWe hope the above have answered your questions and provided some more context. Please let us know if you have further questions or suggestions."}, {"review_id": "siqn4ZJKDh", "reviewer": "Reviewer_H1gh", "summary": "This paper gives an algorithm for learning stabilizing controllers for an unstable LTI systems. The key insight is that the unstable dynamics can be learned via a specialized subspace identification algorithm. Then, as long as the stable part has a sufficiently small $H_{\\infty}$ norm,  a robust controller designed for the unstable component will stabilize the system with high probability.", "questions": "- What happens if there are marginally stable eigenvalues?\n- Can you do the simulations with the theoretical choices for $m$, $p$, and $q$?\n- Do you run into numerical problems when $m$ is large?\n- Can Assumption 5.2 be removed completely?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- This gives at least a partial solution to a long-standing problem in learning-based control: learning a stabilizing controller for partially observed systems.\n- The writing is reasonably clear. \n\n# Weaknesses\n- Theorem 5.3 appears to be stated incorrectly. Namely, I'm guessing (based on Lemma B.1 and Theorem 3.2) it should be that for all $\\delta\\in (0,1)$ the system is stabilized with probability at least $1-\\delta$. The theorem is currently stated as \"for some $\\delta$\" the system is stabilized with probability at least $\\delta$. \n- The work doesn't give a full solution to the stabilization problem: It really only works for sufficiently small stable parts. (I.e. Assumption 5.2 is required.) While an argument about how to extend the method is sketched, a complete solution that works for all stabilizable and detectable LTI systems would be desirable. \n- The paper is somewhat inconsistent in the treatment of process noise. Namely, process noise is included in (14) and (26), but is  not used in the (1) or the main theory.  My guess is that the problem would be substantially harder with process noise.  Namely, (31) would include terms that get amplified through the unstable dynamics, leading to substantially larger errors in the Hankel matrix estimation.\n- Similarly, the paper assumes that the state can be reset to 0 at the beginning of each trajectory. If this were not the case, similar to  the problem with process noise, unobserved, non-zero initial conditions would make the Hankel matrix errors much larger.\n- The choices of $m$, $p$, and $q$ used in the simulations are inconsistent with the theory.\n- The choice of $m$ in Theorem 5.3 requires knowledge of the eigenvalues, and properties of various Gramians. As written, this does not appear to be very useful, since it requires choosing a parameter of the algorithm, $m$, based on properties of  the unknown system. The result could be stated a bit differently, so that for a given $m$, the algorithm can stabilize the system provided the bounds on the eigenvalues and Gramians holds. I.e. for a given $m$, the algorithm would work for all systems of a particular class.", "was_revised": true, "final_justification": "The authors did a good job convincing me that the contribution was reasonably strong. \n\nHowever, there are still issues remaining that were not adequately addressed:\n- Assumption 5.2 does not appear to be necessary. Only necessary when the stable part is not identified.\n- I still think the presentation of the parameter choices in the theorem is not good.  \n- The work does not not adequately address issues of non-zero initial conditions and process noise. \n\nBased on the limitations above, I don't really want to raise beyond a weak accept.", "rebuttal": "We thank the reviewer for the careful and thorough review and provide the explanation below:\n\n- Regarding $\\delta$: We thank the reviewer for pointing out the typo in the statement of Theorem 5.3. It should have been \"with probability at least $1-\\delta$\", instead of \"with probability at least $\\delta$\".\n\n- Assumption 5.2 and no marginally stable eigenvalue: Both assumptions are necessary for this unstable+stable decomposition to work. As discussed at the end of Section 5, Assumption 5.2 comes from the Small Gain Theorem, which is an if and only if condition. If Assumption 5.2 is not true, it can be shown that no matter what control law $K(z)$ the user picks, there always exists some $\\Delta(z)$ that would make the system unstable [53]. Regarding marginal stable eigenvalues, as our results depend on the separation of the unstable and stable components, we do not allow marginal eigenvalues. That being said, we do allow the eigenvalue to be arbitrarily close to $1$, and its impact on sample complexity is characterized in our sample complexity bounds, discussed under the ''Dependence on system theoretic parameters'' paragraph after Thm 5.3. \n\n    Regarding your point ''The work doesn't give a full solution to the stabilization problem:'', we wish to point out that the learn-to-stabilize problem has been shown as a challenging problem with various exponential lower bounds proven in [9] [48] and further in paper ''Learning to Control Linear Systems can be Hard''. Our result essentially carved out a significant subset of problems (those satisfying assumptions in the paper) for which learning-to-stabilze can be easy. In fact, our assumptions is minimal in order to break the hardness of stabilization proposed in [9,48] if one only stabilizes the unstable subspace of the system. While we do acknowledge there is more to do towards ``full solution to the stabilization problem'', our results already make a significant step towards this problem as all prior results actually show learn-to-stabilize is hard.\n\n- Process noise: The paper's theoretical guarantee works when there is no process noise, but observation noise is allowed (Equation (1), (14), (26) all include the observation noise $v_t \\sim \\mathcal{N}(0,\\sigma_v)$).  Process noise is only included in Equation (26) as $w_t$ to show that the proposed method works under process noise in simulation. As the reviewer points out, introducing process noise would enlarge the error of estimating $\\mathcal{H}$ with an additional error term in Equation (31). \n    \n    We clarify that the main technical novelty of the paper is the stable + unstable decomposition (including techniques to separate the unstable component from the lifted Hankel), whereas the system ID part to get the Hankel is not the main focus. We chose to assume process noise is $0$ to keep the system ID part cleaner, avoiding complicating the paper with unnecessary details. \n    If process noise are to be included, then as long as the Hankel estimation error can be bounded, the rest of the proof would work in a similar way. Here is the outline of what the proof would look like:\n    \n    If there is process noise $w_t$, a matrix $\\Psi = [0, A, A^2, \\dots,A^T]$ will have to appear in the proof, so the estimation error of $\\hat{\\tilde{H}}$ will contain a term that increases exponentially with $T$. \n    This is to be expected, as process noise would be amplified by the unstable part of $A$. Once we bound the Hankel estimation, the rest of the proof will be exactly the same as in this paper. In order to finish proof in this direction, a fine balance of $T$ needs to be selected, so that it needs to minimize the current terms in (109), but also not make a term containing $\\Psi$ blow-up, so more weight needs to be applied to the number of trajectories $M$, instead of $T$. However, this fine balance seems only to be present on the above theoretical analysis, as in simulation, we do include process noise we see that (a) the number of samples needed for stabilization does not increase with $n$, confirming our approach works under process noise; (b) a longer trajectory still helps with stabilization even with process noise, meaning the fine-balance regarding the choice of $T$ is not present in our simulation. We leave how to improve the theoretical analysis to incorporate process noise as a future direction of this paper. \n\n- Initial condition: The paper does assume the system is reset to $0$ at the start of each trajectory, but this is merely for the simplicity of proof. For simplicity, we will set $D = 0$ again in this part of the discussion. If $x_0 \\neq 0$, then $y_{t+1} = CA^t x_0 + \\sum_{i=0}^{t}CA^{t-i}B u_i$, with the additional term $CA^t x_0$ known as the free-response term. We can pick some $p$ such that $k < p <T$ and define $U_p = [u_0,\\dots, u_{T-p}], U_f = [u_p, \\dots, U_T]$ and $Y_p = [y_0, \\dots, y_{T-p}], Y_f = [y_p \\dots, y_T]$. We can then project the future outputs orthogonally to the row space of $Y_p$ by $\\Pi^{\\perp} = I- Y_p^\\top (Y_p Y_p^{\\top})Y_p$. Then, we can use the observation $\\tilde{Y}_f = Y_f \\Pi^\\perp$ for the proposed algorithm. This is a quite popular method used in conventional control methods, such as N4SID. For details on how and why it works, please refer to Section 3 of ''N4SID: Subspace Algorithms for the Identification of Combined Deterministic-Stochastic System'' by Peter Van Overschee and Bart De Moor. This is indeed an important issue; we have added more discussion on it in the paper. \n\n- Inconsistencies in $m,p,q$ btw theory and simulation: Theorem 5.3 offers the order of $m,p,q$, not the exact value we should pick (the $\\asymp$ means only ignoring numeric constant as defined at the start of Section 2 ). \n    These expressions provide theoretical insights, showing how $m,p,q$ should depend on system size $n$, unstable subspace $k$, observability, and contrability of the system. Making an exact computation of the omitted numerical constants might offer conservative values, as throughout the proof, many terms are relaxed and merged with the leading order term, making the final order-wise dependence clean at the cost of a conservative numerical constant. For this reason, in experiments, we do not follow the exact theoretical values, but follow trial and error instead. This is common practice in many theoretical literature in control and optimization, where the parameters chosen in the Theorems are conservative, and simulations use much more relaxed parameters.\n\n- Usefulness of bounds for $m$: We disagree that ``the choice of $m$ ... does not appear to be very useful''. The choice of $m$ eventually translates to the sample complexity requirements $ (3m+2)M$, which answers fundamental questions of how the sample complexity of stabilization depends on system theoretic parameters like $n,k$, eigenvalue gap, controllability gramian etc. These bounds provide insights like some systems are inherently easier to stabilize than others. For example, we see it is harder to separate the stable system from the unstable system if there are marginally stable eigenvalues. This is why $m$ is proportional to $\\frac{1}{1-|\\lambda_{k+1}|}$ and $\\frac{1}{|\\lambda_{k}|-1}$. Moreover, the less observable or controllable a system is, the smaller $\\sigma_{\\min}(\\mathcal{G}\\_{\\text{ob}})$ or $\\sigma_{\\min}(\\mathcal{G}\\_{\\text{con}})$ is, respectively, and the larger $\\kappa(\\mathcal{G}\\_{\\text{ob}})$ or $\\kappa(\\mathcal{G}\\_{\\text{con}})$ is, respectively. Therefore, the less observable or controllable a system is, the harder it is to stabilize the system. \n    \n    We acknowledge that in practice, the theoretical values for $m$ cannot be exactly computed, as it depends on the parameter of the unknown system. However, we point out that as long as we plug in conservative estimates of those parameters into $m$ (e.g. lower bounds for $\\sigma_{\\min}(\\mathcal{G}\\_{\\mathrm{ob}}),\\sigma_{\\min}(\\mathcal{G}\\_{\\mathrm{con}})$), the theorem still works. Further, as in many theoretical papers, the selection of those parameters in experiments may differ from those in theory. \n     In fact, in our experiments, the choice of $m$ is very forgiving. Unless $m$ is too small (so we did not converge to unstable subspace enough) or too close to $T$ (so we did not leave enough samples for system estimation), we generally get quite good system estimation. Throughout the simulation, we did not need to do much hand-picking on $m,p,q$. We have added more discussions on this issue in the paper. \n\nWe hope the above have answered your questions and provided some more context. Please let us know if you have further questions or suggestions."}, {"review_id": "PS0nuX6urC", "reviewer": "Reviewer_EFNX", "summary": "This paper studies the problem of stabilizing unknown *partially observable* LTI systems, a natural and necessary extension of previous results in the *fully observable* setting. The authors propose **LTS-P**, a novel algorithm that efficiently stabilizes the system via isolation of  the unstable system modes using compressed SVD on a \"lifted\" Hankel matrix, and via a robust controller design under a small-gain-type assumption on the stable residue. The algorithm features a reduced sample complexity that only depends on the number of unstable modes and is thus independent of the system dimension. Preliminary simulation results confirm its outperformance over existing algorithms.", "questions": "1. How do system parameters ($\\epsilon_*$, $L$) scale with the system dimension $n$? See above for details.\n2. Additional experimental results would be appreciated.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The paper is overall well-written and well-organized. It provides an abundance of intuition via simplified settings and comparisons against known results in the main text, while retaining mathematical rigor in the appendix by providing additional technical details.\n2. The research question is of great theoretical interest, as it's a natural follow-up of several recent works in the fully observable setting.\n3. The algorithm design idea builds upon a solid ground that isolates the unstable modes of the system, but also provides new insights that leverages the transfer function, \"lifted\" Hankel matrix and small-gain-type arguments to properly handle partially observable systems.\n4. The theoretical results are significant, and the proofs are checked to be sound.\n\nWeaknesses:\n1. Assumption 5.2, though coming with a detailed comment on its necessity, still seems a little suspicious. Specifically, it is unclear how $\\epsilon_*$ scales with the system dimension $n$. The order of sample complexity could be made more convincing if the growth rate of $\\log \\frac{1}{\\epsilon_*}$ (and also $L$) is, at least, illustrated with a representative family of systems with increasing dimensions.\n2. The simulation results presented in Appendix A is, at best, preliminary and illustrative. Since $MT$ is selected as the complexity metric, it is natural to ask if there are any potential tradeoffs between $M$ and $T$, which is not reflected in the simulations. Instead, performance is only compared in a restrictive setting, with either $M$ or $T$ fixed. The experimental results could be more convincing through more settings and more results.\n3. Some notations, though easy to judge from context, are not defined before first use. For example, $\\hat{\\Phi}_i$ in eq. (18) seems to be the $i$th block of $\\hat{\\Phi}$.\n4. A few typos are observed, including \"ovservable\" -> \"observable\" (line 32), \"folloing\" -> \"following\" (line 175), etc.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful and thorough review and provide the explanation below:\n\n- Scale of constants: The constant $\\epsilon_*$ is a stability margin linking the necessary condition for the existence of a stabilizing controller, i.e. $\\Vert K(z)F_K(z)\\Vert_{H\\_{\\infty}} < \\frac{1}{\\Vert \\Delta(z)\\Vert_{H\\_{\\infty}}}$ as in Lemma 3.1 and the actual bound on $\\Vert K(z)F_K(z)\\Vert_{H\\_{\\infty}}$ in Assumption 5.2 which requires some margin on top of Lemma 3.1. If we interpret $\\epsilon_*$ to be in the same order as $\\Vert\\Delta(z)\\Vert_{H_{\\infty}}$, then it does not inherently scale with $n$ as $\\Vert \\Delta(z)\\Vert_{H_{\\infty}}$ characterizes the input-output frequency response, related to the input-output dimension, not directly related to the internal state dimension. \n    On the other hand, $L$ covers all other constants needed in Theorem 5.3, it upper bounds the matrix norm of all of the following matrices $\\Vert A\\Vert, \\Vert B\\Vert,\\Vert C\\Vert, \\Vert N_1\\Vert, \\Vert R_1 B\\Vert, \\Vert CQ_1\\Vert$. If we take $A$ to be from a large-scale networked LTI systems, i.e. with very large $n$ but $A$ admits a sparsity pattern to a sparse graph, then $\\Vert A\\Vert$ scales with the maximum degree of the graph (assuming each entry of $A$ is $O(1)$). \n    \n    The dependence on $n$ is also shown in simulation, i.e. as we increased the state dimension $n$ with randomly generated matrices, the length of trajectories $T$ and number of trajectories $M$ stayed the same. \n\n    Finally, we point out that even if $\\epsilon_*, L$ depends on $n$ polynomially, its effect on the final complexity bound is only $\\log n$ as $\\epsilon_*,L$ only shows up in $\\log$ terms. \n\n- $M,T$ tradeoff: Thanks for your suggestions. The $M$ and $T$ trade off is indeed the idea we want to analyze in the simulation. Although the preliminary result shows that fewer trajectories (smaller $M$) requires longer trajectories (larger $T$) and shorter trajectories (smaller $T$) requires more trajectories (larger $M$), we did only include one simulation for a single fixed $T$ and varying $M$ and another simulation for a single fixed $M$ and varying $T$. We did not include more results because it seems the trend of the plots look similar to what is present. However, the reviewer is right in pointing out that there might be value in collecting the percentage of successful stabilization for a fixed $n$ across different $M,T$ pairs. We are currently completing this simulation and will include that in the final version.\n\nWe hope the above have answered your questions and provided some more context. Please let us know if you have further questions or suggestions."}, {"review_id": "IisIw9p7f1", "reviewer": "Reviewer_HW5z", "summary": "The paper proposes an approach to designing a stabilizing controller for partially observable linear time-invariant systems with disturbances. Based on a number of (partially) observed trajectories, obtained by applying random Gaussian control inputs, the unstable system components are approximated for a given rank. By raising the system matrix to a given power, the influence of the unstable eigenvalues is amplified, which is crucial for their identification. This is referred to in the paper as lifting the Hankel matrix. The resulting approximation is then used to design the stabilizing controller. The paper provides probabilistic guarantees that the derived controller actually stabilizes the system, and clearly identifies the influence of the system parameters as well as the hyperparameters of the algorithm.", "questions": "In practice, an unstable system will be only be observed or simulated over a short time horizon. This situation seems to merit some discussion. In my understanding, it suffices, roughly speaking, that m is as large as the unstable dimension k and T is larger than 3m. Then any probability can be guaranteed by making M large enough.\n\nThe claim about boundedness in line 67 could be clarified: In a strictly finite observation scenario (which is considered here), Hankel matrices are finite and bounded.", "limitations": "I did not see any discussion of numerical difficulties that might arise from observations of unstable systems, the inversion of the matrices used in the algorithm, etc. In fairness to the authors, I must admit that the paper is already heavily packed and I have no suggestions on how to make more room for such an analysis.\n\nNote that I did not check the lengthy math appendix in detail, but I have no reason to doubt its correctness.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper extends existing work from fully observable to partially observable systems. \n- The probabilistic guarantees are clear and expose the influence of critical parameters, both of the system and the algorithm.\n- The sample complexity is relatively low. As in prior related work, the system dimension does not directly influence it. In particular, even modest increases in the number of trajectories substantially raise the probability of success.\n\nWeaknesses:\n- The paper is somewhat technical and compact. I admit this is somewhat in the nature of the contribution and not easy to improve. For example, it took me a while to remember what m,M,p,q stand for. Since the result at the end proposes p=q=m, this could be mentioned earlier to ease some of the cognitive load. Reading Algorithm 1 requires referring to 8 equations that are listed on the next page. An intuitive explanation would be just as useful.\n- The paper is largely inspired by [50], where, thanks to full observability, only a single trajectory is required.", "was_revised": true, "final_justification": "The author response answered my questions. I maintain my judgement that this is a paper that should be accepted.", "rebuttal": "We thank the reviewer for the careful and thorough review and provide the explanation below:\n\n- Trajectory length: The reviewer is absolutely correct that by picking a minimally satisfactory $T$ with $m \\approx k$ and $T \\approx 3m$, simulations have shown we can increase the probability of getting accurate system identification and stabilization policy almost surely by increasing $M$. This roughly matches the order in the theorem ($m$ scales linearly with $k$), though we do acknowledge that the theorem has very large numerical constants and $m$ needs to depend on other constants as well. We have added discussions on this in the paper. \n\n- Bounded Hankel around line 67: The reviewer is right that we should have been more careful with word choice. While it is true that in a strictly finite observation scenario, Hankel matrix is always finite and bounded, estimating Hankel matrices accrately becomes much more difficult when the system is unstable. As the $(i,j)$-th entry of the Hankel matrix is $CA^{m+i+j-2} B$ for some $i,j \\in \\mathbb{N}$, if $A$ is stable, $\\Vert CA^{m+i+j-2} B\\Vert$ decreases with increase in $i,j$, so the error of each entry decreases as the trajectory gets longer. However, if $A$ is unstable, $\\Vert CA^{m+i+j-2} B\\Vert$ increases, so any error in system estimation of $A$ (and by extension $B,C$) would be amplified, making the problem more difficult. We will clarify this in the revision. \n\nWe hope the above have answered your questions and provided some more context. Please let us know if you have further questions or suggestions."}]

Author rebuttal:

Meta-review: The authors give a provable algorithm for stabilizing an unknown partially observable linear time-invariant system, scaling only with respect to the dimension of the unstable subpsace.

Reviewers agreed that this is a technically sound and novel contribution to an important problem, and after discussion, all were in favor of acceptance. As pointed out by H1gh, the result could potentially be technically improved in some ways (more general setting with initial conditions and process noise); though the paper is still significant in carving out a first family of problems where "learn-to-stabilize" is provably efficient.

I remind the authors to incorporate the suggestions and clarifications into the final paper.
Decision: Accept (poster)