Efficient Spectral Control of Partially Observed Linear Dynamical Systems
Authors: Anand Paresh Brahmbhatt
Gon Buzaglo
Sofiia Druchyna
Elad Hazan
Venue: NeurIPS 2025 poster ()
Keywords: Online Convex Optimization
Online Control
Linear Dynamical Systems
Primary area: theory
TL;DR: We give a new algorithm for online control of partially observed LDS based on spectral filtering with exponential improvement in running time.

Abstract: We propose a new method for the problem of controlling linear dynamical systems under partial observation and adversarial disturbances. Our new algorithm, Double Spectral Control (DSC),  matches the best known regret guarantees while exponentially improving runtime complexity over previous approaches in its dependence on the system's stability margin. Our key innovation is a two-level spectral approximation strategy, leveraging double convolution with a universal basis of spectral filters, enabling efficient and accurate learning of the best linear dynamical controllers.

Efficient Spectral Control of Partially Observed Linear Dynamical Systems
Anand Brahmbhatt Gon Buzaglo!
Sofiia Druchyna 1 Elad Hazan 1.2+
'Computer Science Department, Princeton University Google DeepMind Princeton
Abstract
We propose new method for the problem of controlling linear dynamical sys- tems under partial observation and adversarial disturbances. Our new algorithm, Double Spectral Control (DSC), matches the best known regret guarantees while exponentially improving runtime complexity over previous approaches in depen- dence on the system's stability margin. Our key innovation is two-level spectral approximation strategy, leveraging double convolution with a universal basis of spectral filters, enabling efficient and accurate learning of the best linear dynamical controllers.
Introduction
Control theory is a decades-old branch of applied mathematics concerned with designing systems that maintain desirable behavior over time, with applications ranging from robotics and aerospace to economics and biology. Recently, it has been adopted by the machine learning community through the lens of online learning, enabling new approaches to sequential decision making systems with latent state and feedback.
central model control theory, and increasingly in reinforcement learning and sequence prediction, is the linear dynamical system (LDS), where the hidden state X; E R evolves linearly in response to control inputs u, R" and adversarial disturbances we, and only partial observations yr E R are available:
X1+1 Ax; + Bu, + Wt y: Cx..
(I)
where E RD is the control input, w, E Rd is an adversarial disturbance, and E IR is partial observation of the latent state.
At each round t, the learner observes ye. selects control u, and incurs convex loss cv uz). where the loss functions e are chosen by an adaptive adversary. This setting extends the classical Linear Quadratic Regulator (LQR) and Linear Quadratic Gaussian (LQG) 22], which assumes known dynamics, full observation, and stochastic Gaussian noise. In contrast, our setting accounts for arbitrary time-varying convex losses, adversarial disturbances, and partial observations. This adversarial setup with partial information falls under the framework of online nonstochastic control, see e.g. [19]. We focus on the setting where the system matrices (A, B, C') are known and time- invariant.
AAthhors ordered alphabetically. Emails: (ab7728, gon. gon. buz.glo, sd0937, ehazann)@rrnnceton.ell
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Regret Minimization with Partial Observation. Since minimizing cumulative cost directly is infeasible in adversarial environments, we adopt the standard benchmark of regret. The goal is to compete with the best fixed policy л E TT in hindsight from comparator class II. Formally, the regret of an algorithm A is defined as
Regret, (A,
Σ coly u
min well
co u,).
where (yz", uzy) are the observation and control sequences induced by the algorithm, and (y7, u² are those induced by policy æ, Note that since the controller does not observe the full state, the losses have be defined over observations rather than full states, regret is meaningful only when costs depend on information available to the controller.
We consider comparator classes II consisting of linear dynamical controllers (LDCs), the standard benchmark for optimal control under partial observation [9]. These controllers maintain an internal linear state updated based incoming observations, and generate control actions via linear readout of this internal state. As such, LDCs are substantially more expressive than a linear map of the current observation. When the system dynamics and cost functions are known in advance and the disturbances are Gaussian, the optimal controller is computed by the classical Linear Quadratic Gaussian (LQG) algorithm 22 6 8) However, in the more general setting that we consider in this work, directly optimizing over LDCs is nonconvex and computationally intractable. To address this, we adopt improper learning. using convex relaxation that enables efficient competition with the best stable LDC in hindsight.
Marginal Stability and Spectral Filters. Linear Dynamical Controllers (LDCs) form the most ex- pressive class of linear policies in the online control literature, capturing systems with internal memory and feedback over partial observations [9] Unlike linear state-feedback linear action controllers, LDCs can implement rich temporal dependencies and adapt to long-horizon structure maaireemmainggg them the natural comparator class in the partially observed setting.
However, learning or competing with general LDCs is computationally hard without further assump- tions. We focus on the regime of marginal stability, where the spectral radius of the closed-loop dynamics is at most 1 - for small ς >> 0. This regime is both practically relevant, many systems are designed to retain memory over time, and analytically tractable, as ensures geometric decay of impulse responses. In practice, small stability margins occur in systems that require smooth, long-memory control such as robotics, thermal regulation, satellite attitude control, surgery, and structural damping. In these applications, aggressive control is infeasible or undesirable, and con- trollers must operate near the stability boundary to achieve robustness and precision. To make this structure exploitable, we restrict to (K. -ddiaagonalizably stable LDCs (Definition) (35), which admit vell-conditioned diagonalizations and bounded responses. Appendix presents an explicit control example where marginal stability yields poly(T") improvement in cumulative cost.
Our algorithm leverages this structure by expressing the disturbance- respppae map of LDCs in spectral basis. We construct a universal set of filters from the top eigenvectors of a Hankel matrix, enabling convex approximation of any such stable controller. This leads to computationally efficient reduction to online convex optimization, with near-optimal regret and exponential improvement in runtime dependence on the stability margin 7.
1.1 Our Contributions
Double Spectral Control (DSC). We propose Double Spectral Control, a novel algorithm for controlling partially observed linear dynamical systems (LDSss) with adversarial disturbances and convex losses. DSC constructs a two-level spectral approximation of the best stable linear dynamical controller (LDC): first approximating it by a long-memory open-loop controller, and then expressing that controller as a convolutional operator over the observable signal. This results in a convex parameterization over double-filtered outputs: spectral convolutions of spectral convolutions of past observations.
New algorithm:

---

Exponential runtime improvement in terms of condition number. the regret bound
We prove that DSC achieves
VT 11
Regret,-(DSC) O
where 7 is the closed-loop stability margin of the best diagonalizably stable LDC. Crucially, the per-step runtime is only polylog (T/7), exponentially improving over the polynomial dependence of prior work such as GRC [30]
Empirical Performance. Preliminary empirical evaluations, presented in Appendix provide support for our theoretical findings.
Method
Regret
Time
Disturbances
Costs
LQG
0 Ô poly (7-1) VT) (ppolylog(1))
O(d²)
i.id
Known Quadratic
GRC
30
Ô (poly (7-1) log
Adversarial
Online Convex
AdaptOn [24]
Old log
Stochastic
Strongly Convex
DSC (this work)
① poly (7 (7 VT)
polylog (T/y)
Adversarial
Online Convex
Table Comparison of algorithms for controlling linear dynamical systems under partial observation. Among methods that handle adversarial disturbances and general convex costs, DSC achieves the
same asymptotic Ö(VT) regret as prior work [30], while attaining exponentially faster runtime with respect to the stability margin y. For both GRC and DSC, runtime depends only polylogarihhiially on the hidden-state dimension d.
1.2 Related Work
Control of Linear Dynamical Systems. Classical control theory provides foundational tools for regulating dynamical systems under uncertainty, with early contributions such as state-space modeling [22 and Lyapunov stability analysis 26).. While optimal control methods like LQR assume full-state observation and stochastic disturbances, modern applications often require adapting to adversarial inputs and partial observability. The online LQG problem corresponds to the setting where the system driven by well-conditioned, independent Gaussian noise, and the losses le u) = y Qy + T Ru are fixed quadratic functions. LQR is the fully observed analogue of LQG, and the optimal solutions to these problems are known as H2-optimal controllers, which can be well- approximated by fixed feedback controllers (for LQRR) or linear dynamical controllers (for LQG)..
In the worst-case setting, the Hox framework 7 computes minimax controllers that optimal against adversarial disturbances and can likewise be represented as LDCs. Extensions such as mixed H2 control, risk-sensitive control, and regret-optimal control [33 [6] as well as recent minimax adaptive and output-feedback formulations (23). further explore the trade-off between robustness and performance. In contrast to these worst-case optimal control methods, low-regret algorithms offer instance-wis wise guarantees that adapt to each realized disturbance sequence. We emphasize that H2- and H.se -optimal controllers for partially observed systems correspond to LDCs, whereas state-feedback controllers suffice only in the fully observed case.
Online Control and Adversarial Disturbances. Early work in the machine learning literature on control focused on the online LQR setting [7] establishing vT regret with polynomial runtime. A related line of research [12] investigated online LQR with adversarially chosen quadratic losses, attaining the same VT rate, In all these works, the benchmark is the best linear controller in hindsight. Online control [19] extends the classical setting environments with unknown and potentially adversarial cost functions and disturbances. The Gradient Perturbation Controller (GPC) achieves sublinear regret against best linear policy under full state observation, its runtime scales polynomially with the inverse stability margin. Extensions to strongly convex costs k and known quadratic losses [55 have further improved regret bounds in specialized settings. Online control has seen applications in meta-optimization []] mechanical ventilation [32), and population
3

---

regulation [17]. Other recent directions include adaptive control for time-varying systems 29 and online control under bandit feedback 3T
Partial Observation. In the setting of fixed quadratic costs and gaussian noise with partial obser- vation of the states, known the solution can be derived using the estimation-control separation principle; see, for example, [8] [24] study online LQ control with partial observation of the state under stochastic assumptions, which is a more limited setting. In the adversarial case, (30] introduced the Gradient Response Controller (GRC), which parameterizes policies over latent "nature observation" signal decouple distur- bances from system dynamics. While GRC avoids explicit state estimation and achieves sublinear regret, it retains a polynomial runtime dependence on the stability margin. We propose new method for this setting, based on a double convolution over universal spectral filters, which achieves the same regret guarantees with exponentially faster runtime.
Setuuuuiae-aauusiiii (LQG) control problem, the optimal
Spectral Filtering. Spectral filtering has been widely used for learning linear dynamical systems from sequences of observations (20] [1 extended this approach systems with non-symmetric dynamics, and (28] recently eliminated dimension dependence using Chebyshev approximations. These techniques have been applied primarily in the context of sequence prediction. The only prior use of spectral filtering in control is by (5), who applied it in the offline LQR setting with unknown dynamics.
Convex Relaxations Control. Improper learning has emerged as powerful tool for bypassing the nonconvexity of optimal control, particularly when competing with rich policy classes. Early work introduced convex surrogates for strongly stable policies [12 2). and recent advances used spectral filtering to approximate develops a new convex relaxation for partial observation, based on a two-level spectral approximation of linear dynamical controllers. Unlike in prediction (20). where convolution with inputs can be directly evaluated using observed outputs, control lacks access to the comparator's actions. In the full observation case, disturbances can be reconstructed and filtered; under partial observation, this is infeasible, so we instead convolve the natural observation sequence (3) introducing additional structure and analytical challenges.
cetturrbnnc-respoone maps in the fully observed setting [9]. Our work
Online Convex Optimization. Our approach reduces online control to online convex optimiza- tion over spectral policy parameters. For background, we refer to standard references on regret minimization [0 18].
Our Method
We propose a convex relaxation the online control problem with partial observation, grounded in two-level spectral upproximation of linear dynamical controllers (LDCs). The central idea is to represent the input-output hehavior of marginally stable LDC as composition of spectral operations, enabling efficient improper learning through a compact, universal basis. To do so, we leverage the fact that the controllers in a LDC have the structure of convolution of the natural observations with vectors of the form [1, at a² ......... and spectral filters provide a compact, universal representation for such sequences. Formally, the filters used in our method are obtained from the top / cigenvectors of fixed Hankel matrix H E mmxx defined by
H. (1 - (1-7)+
itj-1
where is a known lower bound on the system's stability margin. These eigenvectors form universal basis, independent of the system dynamics, cost functions, or noise realizations, and are precomputed before learning. Figure shows examples of the resulting filter shapes.

---

spoctral Filters (y-0.001)
Spectral Fitters ly-0.01)
Spectral Fiiters 051
0.20
0.13
0.15
0.55
Mlar
Tber
Thar5
0.22
iiter
HRo
0.00
0.00
0.00
-0.03
-0.0
-0.55
-0.5
-0.5
-0.5
-0.20
-0.00
-0.20
200
520
102
300
030
590
300
300
400
Figure 1: Entries of the first six eigenvectors of H500- plotted coordinate-wist
The algorithm operates on a signal called the natural observation sequence, denoted yt which corresoonds to the output the system would have produced had the learner applied zero controls from the start. This sequence is computed online by maintaining a fictitious internal state Z₁ that tracks the contribution of the learner's own actions:
2++1 Az, But
Yt
Yr Cz--
Unlike the raw observations ys. the natural sequence y is independent of the learner's parameters. making it amenable to convex optimization.
y
LDS
u
nat
Naturalizer
Spectral Lifting
Projection
Σ Mj Q
Spectral Filtering
"., Vh
9i..., qñn
Figure 2: Illustration of the Double Spectral Control (DSC) method. The learner receives the observed signal yt. from which it computes the natural observation y in online manner by maintaining fictitious internal state. This signal is processed through two levels of spectral operations: spectral lifting stage using filters Φ, followed by spectral filtering stage using filters s. The resulting features are linearly combined to generate the control action u. which is applied to the lincar dynamical system (LDS).
Why Double Filtering. As illustrated in 2 our method consists of two stages: lifting and learning. and spectral filtering is applied both. spectral filtering were applied only during learning as in standard lifting approaches such as [19], the ambient dimension would remain polynomial in the stability margin, and the number of tunable parameters would not decrease. While one could, in principle, avoid explicit lifting by analyzing the composite effect of the two filtering operators directly, this would require substantially different assumptions and analysis. We found our houble-filtering approach to be both more direct and conceptually aligned with prior work.
5

---

Spectral Filtering vs. Fourier Basis. While the Fourier basis, used in methods like the Fourier Neural Operator (25]. is orthonormal and does not induce spectral decay, the Hankel spectral basis exhibits exponentially decaying eigenvalues. This decay enables logarithmic approximation guarantees in the number of retained components, which are crucial for improved dependence on the stability margin These guarantees are specific to the Hankel basis and do not directly carry over to Fourier-based representations.
2.1 Algorithm Overview
Algorithm D constructs the control u, through two-stage spectral transformation of the natural observation history. First, the past sequence y/-m:t convolved with a fixed set of spectral filters {Φ, " derived from the top eigenvectors of Hankel matrix H. This spectral lifting step produces a sequence intermediate signals that captures long-term dependencies in a compact representation. Crucially, this step enables dimensionality reduction: directly lifting the full history would require number of parameters that scales polynomially with the inverse stability margin 7- as detailed in previous work [19]. In contrast, our intermediate spectral approximation ensures only polylogarithmic
dependence on 7
Next, the lifted signal undergoes second spectral transformation. analogous to the spectral filtering technique of [20]. as adapted to the control setting by (9) but now applied to the already filtered and lifted natural observation sequence. Specifically,
convolve the lifted signal with second set of filters [ also obtained as eigenvectors of Hankel matrix. The resulting features are linearly combined using learnable matrices to produce the control u, Since this map is linear in the parameters,
we can apply Projected Online Gradient Descent over a convex K R (g(++1)xx (k+2)xxxX
The loss functions & are convex and memoryless (Definition 3.9p Moreover, by leveraging fast
online convolution methods [4] each step can be implemented in time polylogarithmic in the horizon
and the stability margin
Algorithm 1 Double Spectral Control Algorithm
1: Input: Horizon T, number lifting filters h, number of learning filters h, memories m, m, step size 7), constrains set K. C ((x=))xxx(++)))
2: Compute {(ajs / and {(),, 1 the top eigenpairs of matrices whose i, th entry
is - (1=2)(-3-1 of dimensions m and m respectively.
3: Initialize M E ( for all E (O...., .....,,, nj.
and 2o = Rd.
4: for = 0, ... T 1 do
5: Perform spectral lifting by computing
ynat
yynat
y4tt Oo
Tn 1/4 1/4ynna On
6: Define nat
[ynat
nat and compute control
Lit- m
M
natt M t:t t:t-mn
7: Update Z:+1 Az; + Bu:
8: Observe Yc+1 and record y = Yt+l C2
9: Set M Th [M' V (M')
10: end for
11: return M

---

Preliminaries
3.1
Notation
We use x to denote states, for control inputs, y for observations, and w for disturbances. The dimensions of the state, control and observation spaces are denoted by = dim n dim u) and dym respectively. Matrices related to the system dynamics and control policy are denoted by capital letters A, B, C, K, M. For convenience, write y?ar 0 for all
Given a policy и, we denote the state and control at time t by (x." u.) when following π. If is parameterized by set of parameters Q, and the context makes the inputs clear, we use (xf uz)) or (x, (O), u. (+)) to refer to the same quantities. For simplicity, we use (Xe, Uz) without any superscript argument to refer the state and control time under Algorithm
3.2 Setting
begin by making the following assumptions about our system. Non-stochasticity allows us to assume without loss of generality that Xy =
Definition 3.1. An LDS as in I is controllable if the noiseless LDS given by X = Axt + Bue can be steered to any target state from any initial state.
Assumption 3.2. The system matrices B and C' are bounded, i.e., |B S KB, ||C kg. The
powers of the system matrix A are bounded as || s x<1 7))" The disturbance at each time step is also bounded, i.e., |well S W.
Remark 3.3 (Measurement Noise). Adding bounded noise to the observations is equivalent to introducing additional bounded disturbance term, which is already captured in our formulation through the definition of y Due to Assumption 3.2 the same arguments apply when measurement noise is present, and all theoretical guarantees remain valid under this modification.
Assumption 3.4. The cost functions ci cy u) are convex. Moreover, as long as |/ll < D, the gradients are bounded:
V u)ll, V (y,u)l u)ll S GD.
As mentioned in [19, the most well-known class of controllers for partially observable linear dynamical systems is that of linear dynamical controllers due to its connection to Kalman filtering. We define - didagonaalizably stable LDCss as follows:
Definition 3.5. A linear dynamical controller has parameters (Az, Bi, C+) and chooses the the control at time as:
St41 AaS; Bay:
u. = C2
We say that this linear dynamical controller (s, diiionnnnalll stable if:
1. A H H where L is a real positive diagonal matrix such that || L S and
||>||, H k.
2. |
A
BCa A
3. Define A ==
Then, || S x²211 7)
BAC
4. Let ACL be the closed loop matrix for the policy defined in Lemma A.2 then ACL HLH-1 where L is a real positive diagonal matrix such that S ? and
|
We denote by S [(,,, (A,, Cx) (1,7))-iiin diagonalizaal stable) the set of such policies, and, with slight abuse of notation, also use S to refer to the class of LDC policies uā where (A (Ar, Br, C+) S.
"The requirement of nonnegative eigenvalues can be relaxed by integrating over larger set; it is imposed here for ease of presentation.

---

Assumption 3.6. The zero policy (Ax. BR, Cx) (0,0,0) lies in S.
For simplicity, we assume that R, RB, Ric. W 2 and y S 2/3, without loss of generality.
Algorithm| I learns a convex relaxation of the LDC policy class S from Definition 3.5 which we define follows:
Definition 3.7. (Double Spectral Controller] The class of Double Spectral Controllers with h lifting filters and h learning filters, memories (m, T and stability y is defined as:
mM( = Mojeat
Myy N
M E E ((((h+))xxx(b0220p
Et--tte- mPp
where:
1. y:aa==
[yper
fit-m do 00
2/aynat
1/aynat
Φn 1' @((+2)0
hh fil-m
2. Yrnat tit-i
[ymat
3. (a,, (.) E T and (As, (.)) E TK x R are the (i + 1)-th and i-th top eigenpairs of
E Rmxm and A TRix with the (1, entry being (1 (1-7)++311
14j-1 respectively.
To enable learning via online gradient descent, we require bounded set of parameters: Definition 3.8. We define the domain over which we optimize as
K. {M (R(4+1)xnx(4+2))
1|y
M
R. M|| &RM
where
4096x k Wh4
(2)
128k 1 KBKC V h
2
R
log 1/2
RM
log
74
75/2
We further note that in Algorithm I online gradient descent is not performed on the actual cost function, but on modified cost function, referred as the memory-less loss function: Definition 3.9. We define the memory-less loss function time
((M) = ce(y)(M), ur(M))
where (M) is as defined in 3.7 and (M) is observed by playing
u.
Our use of memory-less convex loss offers an alternative to (29], which formulates online control as optimization with memory. Our approach, inspired by (2]. yields a more direct analysis while still relying on surrogate losses that implicitly capture system memory.
4 Main Result and Analysis Overview
In this section, we present our main result and its proof:
Theorem 4.1 (Main Theorem). Let os be any sequence of convex Lipschitz cost functions satisfying Assumption 3.4 and let the LDS be controllable (Definition 3.1 and satisfy Assumption 3.2 Then,
Algorithm achieves the following regret bound:
VT I1
Regret, =)
where Ô hides poly-logane coly-logarithmic factors in T and constants, and S is the class of LDCs defined in Definition 3.5 This result holds under the following choice of inputs:
1. m log T//2

---

2. h
log T log
C3ymmr33 log T Tlog" 1/4
( ())
3. m
1 log
Cahler2 712
Volog" 3/4
4. h log T log
VT log T log 723/2
T'og
7
5. 1 do V Whhmm"
6. K is the set from Definition 3.8
where the constants are defined as follows:
C1 = CC KBK W C2 = CyGn. k = C3= = CoGn 56 W22
W
C== C3d, Cs 1024Gk 12 knn
and Co is some absolute constant.
The regret bound in Theorem matches the (VVT) rate that is optimal in the convex cost setting, while significantly improving the computational dependence on the stability margin 7, Specifically, the number of tunable parameters and the per-round runtime scale only as polylog(1/s) /7), whereas prior work (30) requires polynomial dependence on 1/7. Thus, our method preserves optimal asymptotic regret rate while achieving exponentially better scaling in both model size and runtime with respect to the stability margin, as emphasized Corollary 4.4
Before proceeding to the proof, we outline the key technical definitions and lemmas required to understand the main proof, while deferring their proof to the Appendix.
In Appendix A we prove that the spectral policy class can approximate up to arbitrary accuracy. Formally, state this as:
Lemma 4.2. For any LDC policy (An. Bx, Cx) S, there exists Double spectral controller with M E K such that:
T
(a())(M)) - a (y7, O(VT),
for m. h, m. h as defined in Theorem
4.1
Classical results in online gradient descent provide a regret bound with respect to loss functions L(M²)) However, our regret is defined in terms of the actual costs (x,,, uz). To overcome this
technicality, in Appendix B.3 we prove that ey (X,, ur) is well approximated by 4(M').. We formally state this result here:
Lemma 4.3. Algorithm
is executed with n, as defined in Theorem 4.1
Then for every E [T].
16GRR hiy mink k w
W
1e(y,, u.) ((MM) <
log!/2
log 1/2
/3T
Proof of Theurem 4.7
Observe that for our choice of m, h, n. h. using Lemma 4.2 and the Definition
3.9 we get:
T
T colyT u = O(VT),
min M
(((M))
min
(4)
TES
since the cost evaluated on the stationary approximating policy 1/* identical to the memory-less loss on that policy. To derive regret bound, we apply the standard guarantee for Online Gradient Descent (Theorem 3.1 18] Lemma B.I ensures that the set convex, and Lemma conffnirms confirms the convexity of the memory-less loss functions. Additionally, Lemma B.3 provides Lipschitz bound these losses, and together with the diameter bound of M, this yields regret guarantee under our step size choice 7). Instantiating this bound with our selected values of m, h, m, h, we obtain:

---

T
VT 7/1
Σ 4 (M²
min M
4 (M') =
(5)
Next, Lemma 4.3 gives the bound the difference between the memory-less loss (MM)) and the cost incurred by the algorithm cx(x,, u,) for every t E [T]. Summing over all t E [T] and for our selected values of m, h, f, h:
VT
Σ (.) w. Σ l (M =0
(6)
711
Finally, add equations 4..5 5
together obtain the result:
T
VT
(yt, up)
min FES
Ca (y7, uz
=
711
Finally, Algorithm maintains only polylog (T/h) parameters each step f. The spectral lifting step 55 at time E [2'] can be efficiently implemented by zero-padding each filter Φ, to length I' and applying online convolution to the natural observation stream {yt" He[m]- Likewise, the controller computation (line 66 involves convolving the lifted, filtered stream y with zero-padded filters 9r By leveraging the fast online convolution method presented in Theorem of [4], we obtain the following corollary:
Corollary 4.4. Each round of Algorithm 7 can be implemented with amortized runtime polylog (T/7).
5
Conclusions
We introduced Double Spectral Control (DSC), a new algorithm for controlling partially observed linear dynamical systems under adversarial disturbances and convex loss functions. Our method constructs a two-level spectral approximation of linear dynamical controllers, enabling efficient learning via convex relaxation. DSC achieves optimal regret while exponentially improving the runtime dependence on the stability margin compared to prior work. To our knowledge, this is the first algorithm combine partial observation, adversarial noise, and general convex losses with polylogarithmic runtime guarantees.
5.1 Limitations
Our method assumes access the system dynamics (A, B, C). which may not be available in many practical scenarios. Extending DSC to settings with unknown or partially known dynamics is an important direction for future work. We also assume aull-information feedback on the loss functions; extending the method to the bandit setting is a natural next step.
This work is primarily theoretical and serves proof of concept. Our analysis relies on Defini (.55 which assumes that certain system matrices are rial-diagonalizable. While this assumption simplifies the regret analysis, it excludes systems with oscillatory non-diagonalizable dynamics. The focus on positive real eigenvalues stems from Hankel-based spectral filtering method rather than an artifact of analysis. Extending the framework to oscillatory or Jordan-block systems remains an open challenge. Empirically, our experiments focused on symmetric systems satisfying these assumptions and therefore should not be interpreted as validating them. Extending the approach to more general dynamical systems, and exploring whether similar spectral compression arises under complex dynamics, presents important direction for future work. Finally, evaluating DSC on real-world control tasks remains an important step toward validating its practical effectiveness.
Acknowledgments
EH gratefully acknowledges support from the Office of Naval Research and Open Philanthropy.
10

---

References
[1] Y. Abbasi-- Yadkori and C. Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference Learning Theory, pages 1-26, 2011.
Abbasi-Yadkori
[]] N. Agarwal, B. Bullins, E. Hazan, S. M. Kakade, and K. Singh. Online control with adversarial disturbances, 2019. Utttttss://aaxxi wttp://..rrgab////////// 08721
[3] N. Agarwal, Hazan, and K. Singh. Logarithmic regret for online control, 2019. URL
https://arxiv. org/ abs/ 1909. 05062
[4] N. Agarwal, X. Chen, E. Dogariu, V. Feinberg, D. Suo, P. Bartlett, and E. Hazan. Futurefill: Fast generation from convolutional sequence models, 2024. /ttpsstts://axxxi. abs/
[5] S. Arora, E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang. Towards provable control for unknown linear dynamical systems, 2018. URL BygpQIbA-1
[6] K. Aström. Introduction to stochastic control theory, volume 70 of Mathematics science and engineering. Academic Press, United States, 1970. ISBN 0-12-065650-7.
[7] T. Basar and P. Bernhard. Optimal Control and Related Minimax Design Problems: A Dynamic Game Approach. Birkhäuser, Boston, MA, 2nd edition, 2008.
[8] S. Boyd. Lecture 10: Linear quadratic stochastic control with partial state observation. https 2009. Lecture notes for EE363: Convex
7/web. wsw.nfrr.....oo edu/ Optimization I, Stanford University, Winter 2008-09.
[9] A. Brahmbhatt, G. Buzaglo, S. Druchyna, and E. Hazan. A new approach to controlling linear dynamical systems, 2025. httttttts///xxx www.oogg/////eoeeooooot..oteaaet abaaaba//500 2504. 03952
[10] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[11] X. Chen and E. Hazan. Online control for meta-optimization. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[12] A. Cohen, A. Hassidim, T. Koren, N. Lazic, Y. Mansour, and K. Talwar. Online linear quadratic control, 2018, URL httpss/tt////aiii..ooo org/ 0ttp//886..000000
[13] A. Cohen, T. Koren, and Y. Mansour.
Learning lincar-quadratic regulators efficiently with only VT regret. In International Conference on Machine Learning, pages 1300-1309, 2019.
[14] Dean, Mania, N. Matni, B. Recht, and S. Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems, pages 4188 4197, 2018.
[15] D. Foster and M. Simehowitz. Logarithmic regret for adversarial online control. In H. D. III and A. Singh, editors. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3211-3221. PMLR, 13-18 Jul 2020. URL Bttl:ttss////:oceeeee
mlr press http//1119///////1 htmmmtmmmmmmmmmmmmm11m11mmm
[16] G. Goel and B. Hassibi. Regret-optimal estimation and control. IEEE Transactions on Automatic Control, 68(5):3041-3055 May 2023.
[17] N. Golowich, E. Hazan, Z. Lu, D. Rohatgi, and Y. J. Sun. Online control in population dynamics, 2024. URL https::: / wttp.orr//ab///..0rrrr 01799.
[18] E. Hazan. Introduction to online convex optimization, 2016.
1909. 05207
[19] E. Hazan and K. Singh. Introduction to online control, 2025. URL. https: http://axxvvoooo/ abs/ 22112211212 096119

---

[20] E. Hazan, K. Singh, and C. Zhang. Learning linear dynamical systems via spectral filtering. 2017. URthttps::/// //t////axvvvv... org httg/ab//7711..0 00946.
[21] E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang. Spectral filtering for general linear dynamical systems, 2018. URL (tLthttt:://at
org/obgg///.ooooooooooe aba/1802..00 1802.039811111188
[22] R. E. Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82. 2211:35-44 45, 1960.
[23] O. Kjellqvist and A. Rantzer. Output feedback minimax adaptive control. arXiv preprint arXiv:2403.0123: 2024.
[24] S. Lale, K. Azizzadenesheli, Hassibi, and A. Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems, 2020. URL atttps:/arxiv..ot org http///iii../////////////// 2003 11227
[25] Z. Li, Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and Anand- kumar. Fourier neural operator for parametric partial differential equations. arXiv preprint arXiv:2010.08895, 2020.
[26] A. M. Lyapunov. The general problem of the stability motion. International journal of control, 55(3):331-534, 1992.
[27] H. Mania, S. Tu, and B. Recht. Certainty equivalence is efficient for linear quadratic control. In Advances in Neural Information Processing Systems, pages 10154-10164, 2019.
[28) A. Marsden and E. Hazan. Dimension-frre regret for learning asymmetric linear dynamical systems, 2025. URL
06545
[29] E. Minasyan, P. Gradu, M. Simehowitz, and E. Hazan. Online control of unknown time-varying dynamical systems, 2022. URL https://arxivv arggabs//200// 07890
[30] M. Simchowitz, K. Singh, and E. Hazan. Improper URL
Improer learning for non-stochastic control, 2020.
[31] A. Suggala, Y. Sun, P. Netrapalli, and E. Hazan. Second order methods for bandit optimization and control, 2024. URL URL httpttt//aaaiii..rrgg.e.eee/ http://axxiv..r//abba///// http:/abs/222..0000 08929
[32] D. Suo, N. Agarwal, W. Xia, Chen, U. Ghai, Yu, P. Gradu, K. Singh, C. Zhang, F. Mi- nasyan, J. LaChance, T. Zajdel, M. Schottdorf, D. Cohen, and E. Hazan. Machine learning for mechanical ventilation control, 2022. Utt.httts::/arxxv.ooom httpg//bb/2122...ee5 06779
[33] K. Zhang, B. Hu, and Basar. Policy optimization for linear control with robustness guarantee: Implicit regularization and global convergence. SIAM Journal Control and Optimization, 59 (5):3644-3672, 2021.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The improvement in the running time is proven in Corollary 4.4 The re- gret bound is proven in Theorem 4.1 The empirical performance is demonstrated in our experiments.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The assumptions mentioned in The complete proof of Theorem 4.1 is in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
13

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, we describe our method completely in Algorithm will be open sourced and link will be provided in the final version.
|
Our code repository
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access 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 replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS 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
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 be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: A link the code will be provided in the final version. However, omit the GitHub repository with all our code at the moment in order not to violate the double blind policy and keep the paper anonymous.
Guidelines:
14

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc.
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https Cow.eeuumissioooooooooo
7/nips. http:cccpppppgggi.ueeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment details will be expansively explained the supplementary materi- als.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: Experiment details with the robust statistical significance measures will be reported in the supplementary materials.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We will completely describe the necessary computing resources in the supple- mentary materials.
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 as well as 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 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research does not involve human participants, and all experiments simulation-based without the use of any external datasets. Furthermore, the work does not raise concerns related safety, security, discrimination, surveillance, deception or harassment, environmental impact, human rights, or issues of bias and fairness.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances 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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is purely in the theoretical domain and hence it does not have any socictal implications.
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
We release the code for our simulations.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part 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 an anonymized URL or include an 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing experiments or research with human subjects have been performed for this paper.
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 much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No research with human subjects have been performed for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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.
18

---

16. Declaration of LLM usage
Question: 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.
Answer: [NA]
Justification: LLMs have only been used for formatting purposes for this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy httt:a/:/eaaarrsssec////ooeeeeee for what should or should not be described.
19

---

A Approximation Results
In this section, we present the proof of Lemma 4.2 approximated by a family of controllers that are linear in spectral projections of past observations, computed over a fixed memory window. The following definition formalizes this class.
We begin by showing that the class & can be
Definition A.1 (Spectral-Projection Linear Controller). Let h N denote the number of spectral components, m E N the memory length, and y E (0, 1) stability parameter. We define the class of Spectral-Projection Linear Controllers as:
u
1/4 o
K2 m
KYYK
K; Ruxp
where Y tm = [ut vt=1
y E Rex(m+1) denotes the matrix of past observations
under controller K, and (or, 0x) E R x Rm+1 are the top + eigenpairs (indexed from 0) of the Hankel matrix H [ (R(+1)x(m+t) with entries
Hy (1 (1-7)
i+j-1
In Section A.1 establish the following lemma, which shows that the class of linear dynamic controllers in can be approximated by the class of spectral-projection linear controllers, for appropriately chosen values of m and h.
Lemma A.2. Let LDC (Ax, Br, C+) E S. Then for
1 log
56Gx"*KBAE
"2 k W Vmnd T Flog T Tlog 1/4
(2))
(
2
h 2 log
7
Ey$
E7²
and 10, there exists spectral
spectral-projectionn projection linear controller with
K, - 1/4
Σ
C₂ H,H,,,e, H H B Mas)
where Ha [1, a.. aI R=+
such that
Σ dalyk u/) cctsT ST.
We now observe that any spectral- projection linear controller can be viewed as static linear controller acting on a lifted dynamical system. Define the lifted system as follows:
R; Â + Bu, + W.
ý: CX.
where
T
0
B
W 0
0
Á
R (m (1)
B
E R
(m 1)dxx
W.
E R
(m
1)d
:
0
0
(8)
The output matrix Ö is given by:
C
0
1/4
(o(1)
o 6 (m + 1)C
1/1
on(n
[ 2m
1/4
(1
o
1/4 on (m + 1)C
20

---

where 6; (o: @. + 1))² is the - 1-th eigenvector of the Hankel matrix in Definition A.
The control law defined by the spectral-projectionn linear controller corresponds to a static linear controller the lifted system:
Kg
K
Ki
E R 2k++2)
so that u, K
(10)
[KJ
The lifted state and lifted output can be written compactly as:
X x x
x E IR (m++1)dd
(11)
1/4 5 = ( oo (Y 00) Th (t (
Tn)
E BR(h22jp,
(12)
To evaluate performance, we define the lifted cost by applying the original cost function o to the first p coordinates of ye (i.e., the original observation y:) and to the control u
Finally, in the zero-input (natural) system, the lifted observation becomes:
ynat = [(
Unat Tn)T] Eg(++2p)
On (Y
Et Φo)
(13)
where Y tt-m is as defined in Algorithm 1
We now summarize key norm bounds for the lifted system components, which will be used in subsequent analysis.
The output dimension of the lifted system (h + 2)p.
The lifted input matrix satisfies [|| < and the lifted noise satisfies ||w/|| S W for all
1, by assumption.
By Assumption 3.6 the lifted dynamics matrix satisfies the exponential decay bound
|| x²2 7) for all 2 0.
The norm of the lifted output matrix Ō can be bounded as follows. Each spectral projection row block after the first block in is of the form
1/4 o, (xCC)C
of o. DJC
and since the eigenvectors o, E Rm+1 are orthonormal and the eigenvalues are bounded by o; S log 2 defining & as a matrix with o.¹ as its rows, we have
I & CII S Kc 1+ (1+vA Vh 1log 1/4 (2) < 4n 4nc Vi-lo 1/4 max
(2)
|O|| < ||C|++
1/4
The lifted cost function ē. which defined by applying the original cost function e to the first p coordinates of y:, and to u,, inherits the same Lipschitz constant as the original cost. That is, for all 1,
Lip(ã) SG. G.
Finally, for the control matrix K E R (k++2)pxx defined in the proof of Lemma A.2 the norm can be bounded as
2(h 11)
h
| < x
< 2k
In section A.2 we prove the following lemma that states that linear controllers can approximated by spectral controller defined as follows.
21

---

Lemma A.3. Consider a system with parameters (A, B, C) such that | S Rg. ||CT| S Rc. and || I (1 -)y² for all i E N. Let {ct be sequence of cost functions that are G- Lipschitz over the domain {lyy ||u|] & D}. Suppose K Ruxp is a linear controller such that A+BK-- HLHI), where L is diagonal matrix with nonnegative entries satisfying || - 1- and
S K.
Then, for any e E (0, 1), there exists spectral controller of form
u = Moyt nat Σ M
where (As, Pi)) are the top eigenpairs of the Hankel matrix E R with Hij = (1-9)145-1 such that
s-j-1
T
Σ
K u S 25T. la(y) -2( celyt
provided
m
log
6GR x- K. W
h 2og Tolog
4000 R W2 Vmdd
log T log 1/4
(
2
59.
e59/2
Moreover, the parameters M lie in the bounded
K= M E BRERRxxx gxxuxp
I| Iu,
S
4R 4 RB
Mo SR, |Mill < K KKKBRO (
Thus, complete the proof of Lemma 4.2 follows:
Proof of Lemma 4.2 Substituting the values of the bounds in Lemma A.3 and substituting e 1/VT
completes the proof.
A.1 Approximating LDC with spectral Surrogate Controller
In this section, prove Lemma A.2 We begin by deriving bounds on the observations and controls generated by any linear dynamic controller S, as well as by the corresponding spectral-projection projection linear controller constructed in Lemma These bounds
established in the following lemmas.
Lemma A.4. Let (Ax, Bu: C+) E S. for all t 2 0, the observation and control satisfy:
KC 7
/y ||
x s
Proof. Define the joint state z
with closed-loop dynamics
A B.C
BC
1
2 = Az + Bw
where
A =
B =
Ar
Since zī = 0, we have
A Bw
The outputs are yJ = [C' 0|27, u, = 00 C2 J2J Using definition 3.5
| S (1- =
||C]| S ko, || K. and |will < W. we get:
K2kWW
[-1 S
14 = w
|yžl $ kC Σ |1 ||
?
22

---

Lemma A.5. Let (Ax. Br. Br C+) S and let K be as mentioned in Lemma A.2 for (Ax, Bri Cr). Then, for any 0,
| - K K'
7
Proof.
Observe that our spectral-projectinn linear controller can be represented by the lifted system
defined in Equations (7) (8).
2 and (TO) for the choice of K; in Lemma A.2 By definition 3.5
Ä+ BRČ HLH and thus (Á + B < (1-17)) Moreover, observe that [.wll s W.
Thus,
R2W
Σ (A+ P
||* S
7
1=1
Using Eqn
it clear that y
|C
x and thus, || S n'RoW
We now complete the proof of Lemma A.2 follows:
Proof of Lemma
A.2 Observe that
Σ
C.y
2=0
Consider the following policy ni defined for some (O
E 1/4 K A
if T d,
u
ifl=T ift
C.
Observe that To is pure LDC policy and that TT+1 is purely spectral policy. In order to bound the difference of costs between these, we shall bound the difference of costs between πr and _,- for any (T).
Observe that for all & E 10, - 2). u, = u, Tr-1 and for definition of T.. Thus, y= --r--m-1 7-1o---- and this gives
[0, - 1), y2 yi ---1 by the
m
Σ A Buy
Σ
C.H Bay
Writing L' EE afejeJ. and defining Ha = a
am E mm+l we we get
m
ΣC,H, H
Σ
H Bay
C=H+eye H
B B. mma
1=0
Since ( [m] U [O}} form orthonormal basis,
d
- Σ CxHaeee H Br Y m-1
-
Σ 25 Maj = Σ
K.
5-1 Since, T. - projection linear policy. Using Lemma A.5 we know that | < ymm In"koW < 2x me vm Moreover,
v 1-1--m-1- and all (y It E [r- - 1]} are outputs of the spectral-
h
1/4 K; " 1=1-------00
1=0
Taking the difference, get that:
m
2x OxoKoW Vm
m
[ -i Σ
1/1
K;
V 1/
Σ Σ
Φ May
1=#11
i=+1i==
23

---

Using Lemma 7.4 of 191, we get that:
2x kc W Wdym
(
m
-
u -
log
1/4
exp
dj
16 log T
4x ki ne W Wddm m
T
log Tlog 1/4
exp
16 log T
4n Ki WcWddm
2 (2)) (14)
81
IA 2 2 log T' log
log T log 1/4
817
Now, observe that since the controls of T. and - are the same until time T - 2, x- x x Thus, using eqn. (14. get that:
||x x p--
|
11
S KB81
(15)
and
Iy -- I u -²=-') S KBkCōi
(16)
Again by using the fact that y = Yi-i 1 for all i21,
|u u
C A Σ
B T--
2=
< ||C By (y - --=--1)]
Σ B
S KBBCK 81
(1 - 7)
[choice of h]
1 [m 2 -
S 2x² 2BRK
log
(17)
k
7
Now, for any T, we have that
A
B
x X
A
B,C
x
x,+1
=
st
BC,
A,
s7-1 S
BC
A,
$7
8741
In order to compute the terms on the RHS,
|| = | (x - x--=-11 + (u, - -
< 2 ||x - x5- x + KB | -
S k KBōO + 2x² 2x22235001 S 3x2x3B0001
Eqns 15 and 17
(18)
and thus,
- 1 - x= S 3x. 3n:n2
(19)
Moreover, for L > r, the controller does behave like an LDC, however, the starting state is different
and must be calculated. Observe that if s²- == Ei= A Bay"=, for all i > т, then the control is correctly defined. Hence,
ss 1 " = ||A Br (y - - + Br (y - y
< O + 3x 2n222n200 S Un²R3RE00
Eqns 16 and 19
Putting this together, we have that
x x
S 3x Kgnkoo + 4x 222 S 7 T
$
s 8711
x,
Thus, we have
x x
< 2 (1 (1-1) ---1 1-11
x 71
S 7 23
s/
S
24

---

Observe that
X
x
X
x
yi Y6 - |C' 0]
Vi
Y1 -- [0
C+]
5
S
for all t > 7. Thus, for all t > T (and also for all E [T'] using the previous bounds) we have that
max y yt
1 Tr
u
||} - 7k N
Now, observe that:
11 || max {|ly?" 1l y
u To
max {lly? - Yt T. 11:111u. Un +1}
$ 14k K
out choice of 61 I W/14x
1/ TT, then the difference is upper bounded by x² ng =r+1
W/y and since
by lemma
A.4 ly? To - S x² kg W/n, we have that ||y?
11.
yr
u T.
S
2rc3 kc 2nc2Ko
kcW Using lipschitzness, this gives us
ce cy mr+ ) cely." _ < W
T
yt
+
1 x-+1 u
1=1
2G 2G W
T 28k OT
56Gk R 8, = ET
by picking 61 = = RE 2/ This completes the proof by substitut- ing the value of ō1 into the choosen expressions of and h.
A.2 Linear controllers
In the previous section, we have proven that any LDC controller in S can be approximated by spectral-projcctionn linear controller. As explained previously, this spectral-projection linear controller can be viewed as a linear controller over the lifted system defined in eqns 7 g
In this section, prove that the class of linear controllers can be approximated by spectral filtering. We begin by making certain assumptions only for this section, and defining the class of linear controllers that aim to compete against and the class of spectral controllers.
Assumption A.6. The system matrices B, C are bounded, i.e., ||B]| S RB, ||C| I Rc. The disturbunce at each time step is also bounded, i.e., ||well S W.
Assumption A.7. The cost functions cely, u) are convex. Moreover, as long as ||y||, ||||| < D, the gradients are bounded:
IV uill, Veceyy uill S &D.
Definition A.8. A linear satisfying A + BKC HLH-1, such that the following conditions hold:
K. is (Re, diigoooalllll stable if there exist matrices L,, H
1. L is diagonal with nonnegative entries.
2. The spectral norm of L is strictly less than one, i.e., ||]|| < 5%.
3. The controller and the transformation matrices are bounded, i.e., || [|] S
We denote by Š = [K K is (R, diddiogonalizably stable) the set of such policies, and, with slight abuse of notation, also use S to refer the class of linear policies u, Sy: where S S. Each policy in S is fully parameterized by the matrix K. E paxp.
25

---

Assumption A.9. The zero policy K 0 lies in S.
For simplicity, we assume that R, RB, W G 2 and 7 S 2/3, without loss of generality.
We define y! the observation at time /. assuming that all inputs the system from the beginning of time, i.e.
nat Axp
Wii
nat Cx.
We define our disturbance response controller with respect to these follows:
Definition A.10. [Spectral Controller] The class of Spectral Controllers with h parameters, memory m and stability 7y is defined as:
MM i
MoyE
Σ MY
where up, E Rmm X E are 7th top eigenvector and eigenvalue of Rmxm such that Any policy in this class is fully parameterized by the matrices M E Bxxxx
Hij (1-9)+--1 141-
The sequence (y.""he((T
hE([T] can be iteratively computed using the following:
y Yt C A Bu
Alternatvely, it can be carried out recursively, starting from Zg 0,
Ze+1 Az, + Bugi
y Yt Cz.
Lemma A.11. Under our assumptions, ||y?**|| < R W Proof. Unrolling the recursion, get that
7
yt
CA
wi-t
Taking norm on both sides,
R. 7) -1-7)--1
|| < R
7
Lemma A.12. For any K E S. the corresponding states x and control inputs u. are bounded by
2R & W
2 KB W
| <
|
K
42
Proof. As in many other parts of this paper, first write AK linear transformation of nature's observations:
A
Σ (A
BKC
BKy
RR Σ (1- ||y2=t11
5 KBRoW
72
Then, since yf y,at + CAK and u Ky we get result.
26

---

For convenience of notation, for a given policy we define A7 =x - -x We begin by defining the class of open-loop optimal controllers as follows: Definition A.13 (Open Loop Optimal Controller). The class of Open Loop Optimal Controllers of with memory m is defined as:
u
K.m
nat Kyt
+ KC (A+ (KC)* BKy nat
1=1
Any policy in this class is fully parameterized by the matrix K IR and the memory m E Z.
Next, we state and prove Lemma A.14, which shows that any linear policy in 5 can be approximated up to arbitrary accuracy with an open-loop optimal controller of suitable memory.
Lemma A.14. Let linear policy K E S. Then, for m 2 3 log
(66x kg R W
and E (0,1).
T
3 B W
cy, K,m K. u, k. - cy u SET,
|,
K.
Kmm
u
7/2
Proof. We begin by bounding the difference in the observation and the difference in the control inputs. The difference in cost is bounded using the fact that the cost functions are lipschitz in the control and observation. We begin by unrolling the expressions for A K in terms of y
A K = AA + BKy = (A+ BKO + BKy = I(A+ BKC) BKY
(20)
This gives us that:
u = =Ky,at + KCAR = -Ky +
Σ BKC)++ am1
Notice that for all 6 S m. u = uu
Kim and hence yt - Kim For > m,
K uu u,
K.m
Σ
KC(A+ AC(A+BKC)* BKy BKy
1=m+1
R F W
(1 (1-
A ineq., C-S)
i=
R KBR W
(1 mm
72
We also note that for any policy
nat CAJ
y + CA Bu
Using both the previous results and the fact that u u,
Kim
for any 5 m, we similarly get:
m
| y: K K.
Σ CA B K.m
Σ
-A B(u
u K,m
and by using Assumption A.9
write:
8
| - y. m
< RB E - 7)--
Km u
<
(1 - mm 33
km
27

---

Using the fact that RgRck? 15 > 1, we get the following uniform bound:
max {||u,
u,
kim
ye (k.m
B W
(1 51
73
Whenever m 2 log RRAnRe which is indeed true from our choice of e and m, this implies
that the 1/ yy Km
ju
u
Kim
S R R /52. Using Lemma A.12 y
|| -
2 & /52, by triangle inequality costs bounded using lipschitzness of &j as follows:
1 K.m
R K W / Thus, the sum of
T
3GR BBR
colyt ) - -cllve K.m
44 mm)
Σ
K.m
.k u, (
V1 Yz
+
72
1=1
6Gk k 25
KB KB
WV
(1 7)
T ST.
cchoice of m]
75
U
To enable learning via online gradient descent, require bounded set of parameters: Definition A.15. The set of bounded spectral parameters defined as
4 A W
2
K M RxXXXp
| ||
Moll S n. M| S R RBRBCC
722
We shall now prove that every open-loop optimal controller can be approximated up to arbitrary accuracy with a spectral controller.
Lemma A.16. For every open loop optimal controller
OLOC x KK.m such that K E $ and
||y || <
SC 3R W there exists an spectral controller A.M.A. with M E K. such
that:
ea (y M u - ce Kmm u k. SET.
for any E (0,1) and h 2 log Tlog
[100Gx 2 & W /mmd
log T Tlog' 1/4
553/2
Proof. Since K E S, there exists diagonal L E Rexn as in Definition A.8 so that:
m
K.m u,
Ky nat
KC(A+ BKO) -Ky nat KCHL 'H BBy,,,
Then write Li-1 Σラ= dj ejee and obtain
K,m u,
Ky
KCH aaj eze H ''BKy
m KCHeee H--BKK 2
-Ky
1=1
i=1
28

---

Recall Y
yy 1-1
y m E pd
define pa = [1, .,.a,..,aa__
R and get
1-1:t-m
ut
K.m
Kyyat +
KCHeje, BKY BKY t-int-maa
Kytat nat +
KCHeee H BKIGHHBBBBKK BKY i-lit-m Σ p Maj
Σ 0.9: = m
j=1
Kyyat nat
KCHeje, H BK, Mos
y t-littmmPi
Let Th A.M. be the spectral controller with Mo
K and Mf
KCH (Ei=1 sp. Ma, eyee H-1BK for all E [k). Note that we have
|M S R, ||47|| s RBAC
max X, 1//// Mai) v1 visis m, rEld]
and from the analysis of Lemma 7.4 of 99, we have that X3 1/4 (40;: 3/7 Thus, |M s
x BBRRROV 2 Then.
u
Kmm
u1
M-
Σ KCH
Σ
p. May eje]
H B.BYY
j=1
R RB W vm
m
wRRoW W
4p Moy
|| 5
m
i=++1 j=1
30k KBR W
73/2
v
log!/4
log"
1/4
2
exp
[1 logoo" T
x²j
Lemma 7.4 of 9
i1+1i==1
30k KBR W /md
(2)
ac
log"
1/4
exp
dx
73/2
16 log T
50% RB W md
2
²²h
73/2
log T log
1/4
exp
16 16 T
yM M"
K.ml
CA' 1 Blu K.m.
yt
S RBACk 2
(1 7)1-11
u K.ml
[Assumption A.9
1=1
R02 22 Rio
W
/md
2 16 log T
75/2
log T log
1/4
exp
Using the fact that RoR R2 /
1, we get uniform bound:
max {||y55mm y
||
K.m
50 22 R W /md
log Tlog 1/1
2
u
u,
exp
75/2
16 log T
(50BBRRR* ymdd log Tlog (2) (:)) which indeed the case for our choice Vi
Whenever h 2 log 7 log of e and h, this implies that y - y.
u
K.m
W
Hence, by triangle
29

---

inequality I|ye || ||]]1==]||
RR 32
Thus, the sum of costs is bounded as follows:
4GR W
T
(y( .u." cyt u m
Σ
M
K.m
yt
72
400G K BB
R55 W
/md
(
70/2
log Tlog"
1/4
exp
16 log T
T
S ET.
cchoice of h)
Using these lemmas, we complete the proof of Lemma A.3 as follows:
Proof of Lemma A.3
The proof follows directly from Lemmas A.14 and A.16
B Learning Results
B.1 Convexity of loss function and feasibility set
To conclude the analysis, we first show that the feasibility set K. is convex and the loss functions are convex with respect to the variables M. This follows since the states and the controls are linear transformations of the variables.
Lemma B.1. The set K. from Definition 3.8 convex.
Proof. Since M u are linear in M, from the convexity of the norm, the fact that the sublevel sets of convex function convex and that the intersection convex sets is convex, we are done.
Lemma B.2. The loss (MM) is convex in M.
Proof. The loss function & is given by (MM = (x,(MM,, (M)). Since the cost cs is a convex function with respect its arguments, simply need show that x and u.M depend linearly M. The control is given by
h
h
M u
nat Moy?""
1/4 [pil,
Myy nat
1/4 [ May
1=0 k=
m
(a12.) [ lseely May
(21)
which is linear function of the variables. Similarly, the observation y.M is given by
y
y: Σ CA. CA
Thus, we have shown that (M) and u, (M) are linear transformations M. composition of convex and linear functions is convex, which concludes our Lemma.
B.2 Lipschitzness of f.(-)
The following lemma states and proves the explicit lipschitz constant of 4.)). Lemma B.3. For any M, M' K. it holds that,
((M) - ((('M) 32GThh mmnk x
log 1/2 (2)
|| -M'll
722
30

---

Proof. Taking the difference in controls defined in eqn. 21
Sishhy/mmnn' Ric W
(
[u un (MM')l <
log" log!/2 1/2
|I
(7)
Taking the difference in the observations,
Σ CAS-1 (p(ue-g(10 - (M_)))
K
max { - ur ur-o
DE
16hh mink K x W
log log (2)
|| M'
Using the fact that KBtck /y > 1, we get a uniform bound:
W
(2) II
max - (xa((M)))) u. (M))ll S
log" 1/2
M'
-
7/2
Using the lipschizness the cost function from Assumption 3.4 the definition of K., we have
((MM) (MM') = (M) u. (M)) - co (MY)) (MM'))
S GR (I|x, - (M))l + [l - -u(MM)))
mmnx x log 1/2
(2)
2
IIM M'
B.3 Loss functions with memory
The actual loss at time / is not calculated on x,MM),, but rather on the true state x,, which in turn depends different parameters M for various historical times i t. Nevertheless, cx u,) is well approximated by (,M),, as stated in Lemma 4.3 and proven next.
Proof of Lemma 4.3 By the choice of step size 7) and by the computation of the lipschitz constant of le w.r.t M Lemma B.3 we have:
RM
LVT
where L is the lipschitz constant of le w.r.t M, computed in Lemma B.3
Thus, for each j E [h].
| - M Σ
-
< in iRM
TT
4=1--1
Observe that u, = (M Observe that y. and y²(M)) can be written as
(((M)) yhat + Σ CA Bu, Bu: (.
CAV-
yt =t= y Σ CAR-1 Bu---Buu
31

---

Evaluating the difference,
ly. - y.
Σ CA B(u BAu us- (M 92)
S KBtCc
( (1-
1 (M.) - u (M-
q=1
W
log!/2
2
Σ (1 1-))--111 | 00
9=1
16R mank WBR W
log
1/2
Σ
q(1 - 7)
WVT
9=1
16R M /oci KB BR W
log
1/2
23VT
By definition, ((M) (M u, (M*),, and by the definition of K. and the projection used in Algorithm 1 we have by Assumption 3.4
(e((*) co uz)l = (c0() u(()) - cy
S (R))). yell
16GRR hwa.hhhh/mmmmmmmmmmm mm/k B W
log 1/2
V
C Experiments
We present a series of synthetic experiments designed to evaluate the performance of the DSC, as specified in Algorithm [ We compare DSC against the gradient response controller (GRC) 30
and the linear quadratic gaussian controller (LQG) [8]. We analyze the performance of these three controllers under the following system settings: linear signal, where the initial state Xo randomly sampled from the Gaussian distribution; and a signal with the ReLU state transition. For each signal type, evaluate the performance of controllers under types of perturbations: (i) Gaussian noise, and (ii) sinusoidal disturbances; and provide 95% confidence intervals for each setting.
For each experiment, mension of p = 3, and a control dimension of n = 2. The system matrix A E IR Rdxd is diagonalizable, with the largest eigenvalue being 0.8, ensuring marginal stability. The control matrix B Rdxx consists of Normally distributed entries. For the described settings, we use h = h filters and m m 10 memory for both controllers.
consider LDS with a hidden state dimension of d 10, observation di-
Each figure reports the average quadratic loss computed over a sliding window, with its size set to 10% of the sequence length. Hyperparameters are selected to reflect representative and stable performance, though the experimental setup generalizes sigher-dimensional systems and alternative perturbation models.
The empirical results presented in Figures 3a demonstrate that the DSC controller outperforms the GRC controller, while LQG remains optimal for the setting with Gaussian perturbations. Furthermore, under sinusoidal perturbations, DSC maintains performance advantage over both LQG and GRC, as illustrated in Figure 3b Similar conclusions on the performance of the DSC controller hold for the experiments with ReLU state transition as shown in Figures 3c 3d The confidence intervals further substantiate that the performance gains of DSC over GRC are consistent and statistically robust across random system initializations.
32

---

GRC B9C
5-51e
(a) Linear Signal with Gaussian Noise
(b) Linear Signal with Simusoidal Noise
L00
GRC BSC
5:0 Angrog Uos
(c) ReLU State Transition with Gaussian Noise
(d) ReLU State Transition with Sinusoidal Noise
Figure 3: Comparison Controllers: LQG, GRC, and DSC with 95% Confidence Intervals over 100 trials under Different Input Signal and Perturbation Settings.
D Advantage of Smaller y
We provide a construction in the fully observed setting, i.e., C= 7, similar to the one in 99. Prior work typically assumes stability margin of 7 S2(1 (011ppoly (()) guarantee O(polylog runtime. In contrast, analysis shows that even when ((1/T<) for any k E (0, 1 1/33). one can maintain sublinear regret while still achieving an O(polylog(T)) runtime. This section illustrates that such smaller values of can lead to substantially lower aggregate cost compared to the standard choice 1 /ollylog(T).
Consider a noiseless scalar linear system with parameters a, b E R evolving as
It-1 az; + bu:
At each time step, the instantaneous loss is defined as
Vt E [T]. cx u) max xx, -1}.
Since the system is one-dimensional, for sufficiently large k, the set of (N, diadgoonnalizably stable controllers reduces to
S(>) = { 0 < a + bb: < - }}
With initial state Fo 1, the minimum total loss over the horizon is
min kES(1)
Σ
(xr, uz) min kES(T)
Ix))
max kES(T)
Σ
(a + bk)* t-1
T
--
Since $1 - S ?,,,, we obtain the bounds
--
Σ ca(x,,)) <
min
KES(T)
7
33

---

Applying the lower bound gives
SEs(ppooyylo((T ui) 2 -Tolylog(T),
while the upper bound yields
T
(x( S (1 e --Th 1
min (1/T)
2
Therefore, the difference between the two minimum cumulative costs satisfies
(x ue) 2 T 2 - -oolylog(T) = (2(T
Σ c(( u.)
min keS(1/polylog())
min (ES(1
In summary, setting = 1/7 results in a markedly smaller cost for the best controller in the class S(7) compared the 7 l/polylog(T) case. This demonstrates polynomial improvement in the achievable aggregate performance.
34


Reviews:
[{"review_id": "DzCUx45j45", "reviewer": "Reviewer_DfSy", "summary": "The paper proposes a new method for online control of partially observed linear systems that is amenable to efficient online updates. The setting of the paper is that of online non-stochastic control where the costs and (potentially adversarial) disturbances are revealed sequentially.\nThe main challenge with previous approaches ([22]) is that the run-time per step (one online update) scales inversely proportially ($O(1/\\gamma)$) with the stability margin $\\gamma$ of the system, as the margin approaches zero. In particular, the number of tunable parameters scales polynomially with $1/\\gamma$.  By following the proposed approach the run-time scales with the improved rate of $O(\\log(1/\\gamma))$, which is an exponentially better for very small $\\gamma$. In the meantime, we preserve the standard $O(\\sqrt{T})$ regret guarantees of the convex cost setting (where $T$ is the total number of steps taken).\n\nThe main idea is to pre-filter (convolution operator) the observations twice with appropriate filters that are selected as the top eigenvectors of specific Hankel matrices. Then, the controller is obtained as a (convex) linear combination of the pre-filtered observations,where the linear coefficients are tuned online. Under certain conditions on the system and controller class, these specialized Hankel eigenvectors compress the information of the observations. As a result, it is sufficient that the number of tunable parameters scale only logarithmically with $1/\\gamma$.\n\nThese conditions require the system to be stable, diagonalizable, with positive real eigenvalues in both open-loop and closed-loop.", "questions": "**Major comments**\n\nI am willing to improve my evaluation based on the authors response. To summarize, the limitations should be discussed more explicitly, comparison with prior work should be expanded, the literature review should be enhanced and some aspects of the analysis/contribution should be clarified.\n\n**1.** Dealing with weakness 1. In the limitations, it should be acknowledged that this assumption is unrealistic for actual physical systems. If the authors provide an example of a meaningful real-world physical system that satisfies the conditions I will improve my rating even further. The simulation should also include examples of systems that violate the conditions (in both open and closed loop) to support the claim of the footnote. In any case, there should be more discussion. Why are these assumptions needed? Is it an artifact of the proof? A fundamental limitation? What breaks in the case of complex or negative eigenvalues or in the case of Jordan blocks? Would we need a different Hankel matrix?\n\n**2.** Dealing with weakness 2. It should be clarified if the order of $1/\\gamma^{11}$ in Theorem 4.1 is worse/better/same compared to [22].  From this perspective, the claim \"optimal regret guarantees\" in the caption of Table 1 is currently unclear.\n\n**3.** Dealing with weakness 3. The paper would benefit from the addition of more papers from the control community. For example, the setting of Hinfinity control where the controller acts against adversarial disturbances seems quite relevant. Variations of this idea include mixed H2/Hinfty control, risk sensitive control, regret optimal control, minimax adaptive control. The following papers might be relevant and contain useful references\n\nT. Basar and P. Bernhard, $\\mathcal{H}_{\\infty}$, \"Optimal Control and Related Minimax\nDesign Problems — A dynamic Game Approach\", 2nd ed. Boston, MA,\nUSA: Birkhauser, 2008\n\nKaiqing Zhang, Bin Hu, Tamer Basar, \"Policy Optimization for $\\mathcal{H}_2$ Linear Control with $\\mathcal{H}\\_{\\infty}$ Robustness Guarantee: Implicit Regularization and Global Convergence\", SIAM, 2021 \n\nG. Goel and B. Hassibi, \"Regret-Optimal Estimation and Control,\" in IEEE Transactions on Automatic Control, vol. 68, no. 5, pp. 3041-3053, May 2023\n\nO. Kjellqvist and A. Rantzer, \"Output Feedback Minimax Adaptive Control\", arxiv, 2024\n\n**4.** Dealing with weakness 4. The paper could provide more intuition on how spectral filters work. I had to go to [15] to understand that the Hankel eigenvectors compress information. I recommend to include a brief discussion here as well. \n\nIt could also help to provide more intuition on what the main challenge in [22] is. Why does the run-time scale with $1/\\gamma$? It seems that a crucial component is studying the inequality $(1-\\gamma)^m\\le c$, where $m$ is the number of parameters and $c$ can be arbitrary. This inequality is equivalent to $m\\ge -\\log c/\\log(1-\\gamma)$. Although there is a logarithm, as the margin goes to $0$, we have $-1/\\log(1-\\gamma)\\sim 1/\\gamma$. I think the paper would benefit from such a discussion.\n\n**5.** Dealing with weakness 5. Please explain why we need double filtering in more detail. \n\n**6.** Convolution implementation. A naive implementation of the prefiltering steps would lead to a run-time that is polynomial with $1/\\gamma$. The reason is that naive convolutions involve $m,\\tilde{m}$ mutliplications. In turn, $m,\\tilde{m}$ scale polynomially with the inverse stability margin. The paper claims that this limitation can be lifted by implementing the convolutions efficiently.\nHowever, the paper does not provide enough details to understand how this is done. Unfortunately, the proof of Corollary 4.4 is informal and handwavy. Could you please provide more details? I suggest to make the proof of Corollary more precise by referring to specific results in [2] in a more principled way.\n\n**7.** Please provide more details about the simulations. Does matrix A satisfy all the restrictive stability assumptions including positive real eignevalues? Have you tried a matrix A that does not? What is the frequency of the sinusoid. Have you tried several frequencies? (Otherwise, it might be a matter of luck that the controller works well with a specific frequency.)\n\n**8.** In line 129 the following is stated \"– Appendix C reports preliminary empirical evaluations supporting our theoretical findings\". The theoretical results only claim that the proposed method has superior runtime. They do not claim anything regarding the performance or the regret order. The simulation results show that the proposed method is superior compared to [22] but they do not compare runtimes. Hence, I am quite confused since the theoretical claims and the simulations findings are about different things.\n\n**Other comments**\n**i)** Can we have measurement noise?\n\n**ii)** I couldn't find the definition of $\\mathcal{A}_{CL}$ (mentioned in line 194) anywhere. Could you clarify the definition?\n\n**iii)** What is the difference between frequency domain transformations and spectral filtering? Maybe the paper could include some discussion in the related work.\n\n**iv)**. I think $\\tau$ and $t$ mixed up in several steps in the proof of lemma A.2, e.g., between 746-747. \n\n**v)**. Please define $y_t(M)$ (line 216) formally. The current phrasing is ambiguous.\n\n**vi)**. Is $y^{nat}$ missing from $y_t(M^t)$, $y_t$ below line 882? In general the notation for the several versions of $y$ is quite confusing.", "limitations": "As I describe in the weaknesses and questions the limitations should be further clarified as they are only partially addressed. (There are only technical limitations no societal issues.)", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe idea of pre-filtering observations to improve dependencies on the stability margin is reasonable and interesting.  While I wouldn't rank it as the most important practical aspect it has theoretical interest. It can be impactful when the system exhibits long memory and slow attenuation. The analysis seems sound and correct. The strongest point of the paper is that the number of tunable controller parameters scales logarithmically with the inverse stability margin. The idea of pre-filtering has been studied before in prior work, e.g. in [7] for fully observed systems. Interestingly, here double filtering is used here for partially observed systems which is a non-trivial change. \n\n**Weaknesses**\nThe results are quite preliminary and lack generality. Moreover, little intuition is provided about why the method works. \nBased on the responses I am willing to improve my evaluation. To simplify the authors' response I included the actionable items in the questions section. \n\n**1.** Assumption 3.5 and Definition 3.4 seem extremely restrictive. They require the following: First, the controller itself is required to be implemented as a stable diagonalizable system with positive real eigenvalues. Second, the overall closed-loop dynamics should be stable diagonalizable with positive real eigenvalues. Third and perhaps more importantly, Assumption 3.5 requires the open-loop dynamical system itself to be stable, diagonalizable and to have positive real eigenvalues. \nThe limitations section should be expanded to discuss this in more detail. Currently, only issue 1 is discussed, while issue 3 is hidden; I only understood it while going through the proofs. \n\nAssuming stable and diagonalizable is ok. However, assuming systems with positive and real eigenvalues (both in open-loop and in closed-loop) is very peculiar. I have doubts that this can include meaningful systems. Almost all physical systems of interest exhibit oscillations, meaning they have complex eigenvalues. Even physical systems with positive real eigenvalues, like higher order integrators (which are excluded since they are not diagonalizable), will have complex eigenvalues in closed-loop. I couldn't find any evidence supporting footnote  1 \"This requirement is for tractability of analysis alone, and we show empricially that our method works regardless of it\".\n\n**2.** The paper does not compare the regret order (with respect to $\\gamma$) with that of prior work. It only compares run-times. \n\n**3.** The literature review is very biased with 16/24 references containing the same author. The paper lacks references to works from the control community. \n\n**4.** There is little intuition about how spectral filters work. \n\n**5.** The paper does not explain what the difference with [7] is and why we need double filtering instead of single.", "was_revised": true, "final_justification": "Although the weaknesses remain (restrictive assumptions, limited simulations), the authors have committed to clarifying their limitations in more detail. From this perspective, I am increasing my score. To summarize, the theoretical result is quite interesting and could inspire interesting future work directions where these limitations could be addressed. Moreover, I feel that overall the paper is well-written. Hence, the benefits outweigh the disadvantages.", "rebuttal": "We thank the reviewer for his thorough reading of our paper and proofs and giving educated comments about our work.\n\n**Response to Comment on Definition 3.4 and Assumption 3.5**  \nWe thank the reviewer for raising this important point.  \nDefinition 3.4 defines the comparator class, and we agree that the assumption that it must include the zero policy is a restrictive modeling choice. We will add this to the limitations section.  \nIndeed, Assumption 3.5 applies only to the comparator class, not to the learned policy itself. This assumption is an artifact of the analysis. Our theoretical regret bounds rely on this structure, but our experiments optimize loss rather than regret, and thus are independent of the comparator class. The fact that our algorithm performs well in practice even without satisfying Assumption 3.5 supports the view that this assumption is not fundamental to performance.  \nThat said, the requirement for real positive eigenvalues stems from the spectral filtering technique itself. The filters we use are based on Hankel matrices, whose structure relies on real, monotonic dynamics; complex eigenvalues would yield oscillatory behavior that breaks this structure. Therefore, this assumption reflects a fundamental limitation of our current approach. However, it may be possible to overcome it using recent advances such as those in:  \nMarsden & Hazan (2025), *Universal Sequence Preconditioning*, arXiv:2502.06545.  \nWe will consider discussing this direction in the camera-ready version.  \nFinally, we note that it is possible to relax the non-negativity requirement on eigenvalues and extend our analysis to systems with marginally stable real eigenvalues. In this case, the integration would start from $-1 + \\gamma$ rather than 0. We will clarify this technical point in a footnote.\n\n**Response to Comment on Regret Bound and Comparison with [22]**  \nWe appreciate the reviewer’s request for clarification on the regret dependence in our work versus [22].  \nIn our setting, the regret scales as $\\widetilde{O}(\\sqrt{T})$, and the number of tunable parameters scales as $O(\\log(1/\\gamma))$, where $\\gamma$ is the stability margin. In [22], while the regret is also $\\widetilde{O}(\\sqrt{T})$, the number of parameters scales polynomially with $1/\\gamma$. Unfortunately, [22] does not specify this exponent precisely, and it is nontrivial to extract from their analysis.  \nOur key contribution is that we achieve the same optimal regret dependence on $T$ while significantly improving the complexity dependence on the stability margin $\\gamma$ — from polynomial to logarithmic in the number of parameters and runtime. This is the basis for our use of the term “optimal regret” in Table 1, though we very much agree that the wording should be improved for clarity and will revise the paper accordingly.\n\n**Response to Comment on Related Work**  \nWe agree that the related work section is currently too narrow and appreciate the reviewer’s suggestions. We'll revise the section to better reflect contributions from the control community and include a more diverse set of references in the camera-ready version, including the ones mentioned by the reviewer.\n\n**Response to Comment on Spectral Filtering Intuition**  \nWe leverage the fact that the controllers in a LDC have the structure of convolution of the natural observations with vectors of the form $[1, \\alpha, \\alpha^2, \\ldots]$, and spectral filters provide a compact, universal representation for such sequences. This structure allows for an efficient low-dimensional approximation using the top eigenvectors of Hankel matrices. We will add a brief explanation of this intuition in the paper.  \nRegarding the comparison to [22], the key inequality used there is $(1 - \\gamma)^m \\leq e^{-\\gamma m}$, which implies $m \\geq \\log(c)/\\gamma$. This results in polynomial dependence on $1/\\gamma$. Our approach bypasses this by using a more refined analysis based on Hankel matrices, which leads to logarithmic dependence in the number of parameters. We will make this contrast clearer in the final version.\n\n**Response to Comment on Double Filtering**  \nOur method consists of two stages: lifting and learning. Spectral filtering is applied in both. The lifting stage enables us to define a comparator class with desirable structure; the learning stage operates in the lifted space. If we only applied filtering at the learning stage, following a standard lifting approach as in [15], the ambient dimension would still be $O(1/\\gamma)$, so spectral filtering would not reduce the number of parameters. Therefore, double filtering is necessary to obtain the improved dependence on $\\gamma$.  \nIt may be possible to avoid explicit lifting with an alternative analysis and assumptions by analyzing a complicated multiplication of matrices, but this would diverge significantly from the structure in prior work. We found our approach to be more direct and conceptually aligned with the literature. We will clarify this point in the paper.\n\n**Response to Comment on Corollary 4.4**  \nWe agree that Corollary 4.4 can be clarified. The key observation is that we compose two convolutions. Theorem 3 in [2] guarantees that each such convolution can be computed efficiently. We will revise Corollary 4.4 to explicitly cite this result and make the argument more rigorous.\n\n**Response to Comment on Experiments**  \nWe agree with the reviewer that including a broader set of experiments, both with a wider range of noise frequencies and with system matrices that do not satisfy the current stability assumptions, could provide additional insight and further test the robustness of our approach.  \nFor all conducted experiments, we ensured that the system matrix $A$ is symmetric with real eigenvalues between 0 and 0.8.  \nWe experimented with random frequencies of the sinusoidal noise and observed generally consistent controller behavior. For the results shown in Figure 3, a frequency of 0.1 was selected as it most clearly illustrated the observed patterns.\n\n**Response to Comment on Theory vs. Experiments**  \nWe agree that the theory focuses on runtime improvements, while the experiments evaluate loss. We will make this distinction clearer. Although we do not claim theoretical improvements in regret, the improved empirical performance may be explained by the fact that our method captures a longer effective history for the same number of parameters. We will add this discussion to the experimental section.\n\n**Other Comments**  \ni) Our analysis holds for bounded measurement noise as well. Adding noise to the measurements is equivalent to adding additional noise to the already existing disturbance. Since we use the disturbance in the definition of $y_{\\text{nat}}$, and as long as those are bounded, the analysis remains valid. We will add this clarification to the paper.  \nii) We chose to define $A_{\\text{CL}}$ implicitly, as its matrix form is very complex. It represents the closed-loop matrix of the policy defined in Lemma 2, and is effectively the induced matrix appearing in Definition A.8, corresponding to the spectral-lifted policy. We will consider whether it is feasible to write the definition explicitly.  \niii) The Fourier basis corresponds to a different set of eigenfunctions, and we are not aware of any logarithmic approximation guarantees using them. The guarantees we rely on are specific to the eigenvectors of the Hankel matrix. The reason is that the Fourier basis is orthonormal, i.e., all eigenvalues are one, whereas the SF basis has an exponential eigenvalue decay. This is a crucial point, and we will try to emphasize it in the camera ready version as well.  \niv) We thank the reviewer for pointing out the typo in Lemma A.2. The subscript in line 746 should be $\\tau - 1$, and the superscript should be $\\pi_\\tau$. The summation should also go up to $h$. This follows from the definition of the policies $\\pi_\\tau$, and line 747 then follows correctly.  \nv) $y_t(M)$ is defined by plugging $u_t(M)$ into the LDS equation (1), where $u_t(M)$ is defined in Definition 3.6. We will formally define $y_t(M)$ in the paper as well.  \nvi) The reviewer is also correct about the final typo. We will fix this in the camera-ready version; those terms cancel out."}, {"review_id": "PxVPikOivK", "reviewer": "Reviewer_iEgZ", "summary": "This paper proposes a novel algorithm for controlling linear dynamical systems under partial observation of the latent states and adversarial disturbances. The new algorithm (called DSC) can achieve comparable regret with some prior methods, but has a significant advantage on runtime at eat iteration. The authors show that the per-step runtime of DSC is only $polylog(T/\\gamma)$, where $\\gamma$  is the stability margin of the system. This improves prior art significantly for small $\\gamma$.", "questions": "- Can the authors provide examples/situations in practical applications so that $\\gamma$ is (very) small?\n- What is $poly(\\gamma^{-1})$ in each method in Table 1?\n- Can we trade off between the regret and per-step runtime?", "limitations": "The authors already discussed some limitations and tried to resolved, e.g. providing some experiments. There seems to be some limitations as pointed out above.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- The writing of the paper is clear and easy to understand about the problem setting, formulation, and related results.\n- The proposed method seems to have a significant advantage on per-step runtime in term of stability margin, but maintain the competitive regret.\n\n### Weaknesses:\n- This paper is mostly theoretical with limited validation on practical settings. The authors did a simulation with a simple setup and then compared with two other related methods. \n- The main benefit of the proposed method mostly bases on the concept of stability margin. However, the authors have a limited discussion about this concept. This could pose a concern on how practically significant their method is. It could be useful for the readers if the authors can provide examples/situations in practical applications so that $\\gamma$ is (very) small. Otherwise, the proposed method may not be practically beneficial.\n- Many references lack information.", "was_revised": true, "final_justification": "I have read the authors' response and the other reviews. Most of my concerns have been cleared. I encourage the authors to provide examples/situations in practical applications that may have small stability margin.", "rebuttal": "We thank the reviewer for their feedback and for acknowledging the clarity of the paper and the improved runtime dependence on the stability margin. We shall address the weaknesses first, then move on to the questions raised by the reviewer. \n\n**Weaknesses**  \n**Experiments:** We appreciate the reviewer’s observation regarding the scope of the experimental evaluation. Our primary aim in this work was to highlight and validate the theoretical contributions under well-controlled and interpretable conditions. That said, we fully acknowledge the importance of broader empirical validation, especially in settings that reflect more diverse and practical scenarios. While the current experiments are limited in scope, we view this as a foundation for future work that will explore a wider range of system dynamics and environments to further demonstrate the robustness and applicability of our approach.  \n**Stability margin:** We kindly refer the reviewer to Section 9 of [7], which discusses settings where the stability margin is small. We also mention the benefits of small $\\gamma$ in the introduction (see the paragraph titled *“Marginal Stability and Spectral Filters”*), and we will consider expanding this discussion. In general, our method is beneficial in situations where the system exhibits long memory and must be controlled smoothly. Examples include structural damping in buildings, thermal regulation systems, and high-precision automated surgery, among others.  \n**References:** We will expand and improve the descriptions of referenced works throughout the paper to ensure clarity and completeness.\n\n**Questions**  \n**Examples of small $\\gamma$:** Please see our response above and Section 9 in [7].  \n**$\\gamma$ dependence in Table 1:** In our work, the runtime exponent in $\\gamma$ is 11. In [22], the dependence is noted as polynomial but the exact power is not specified and is nontrivial to extract from their analysis. That said, our focus is not on the specific power but on the qualitative improvement: we achieve standard $\\widetilde{O}(\\sqrt{T})$ regret while reducing the runtime dependence on $\\gamma$ from exponential to polynomial.  \n**Tradeoff between regret and runtime:** We are not aware of a way to achieve such a tradeoff within our current framework. Our regret bound is already satisfactory given the complexity constraints, but exploring this tradeoff is an interesting direction for future work."}, {"review_id": "Qh8egFABkg", "reviewer": "Reviewer_tQzd", "summary": "This work studies the problem of online control of partially observed linear dynamical systems, where the cost function is convex and chosen at each time step by an adversary. In this adversarial setting, the authors propose an online optimization algorithm that matches the best known asymptotic regret, while considerably improving the dependency of the computational complexity with respect to the spectral radius. Theorem 4.1 provides the key theoretical results and leads to the claimed complexity bounds. Minimal experiments are included to empirically support the theoretical contributions.", "questions": "1. Comparing Equations (1) and (3), shouldn't Line 141 say: “the system would have produced had the learner applied zero disturbances”?\n\n2. What is meant in Line 144 by “natural observations are independent of the learner’s parameters”? How does this enable convex optimization?\n\n3. What does “learning” refer to in this context? Since the system matrices are known and the cost function is defined over known quantities, it is unclear in what sense this is an estimation or learning problem.\n\n4. What is the interpretation of the filter matrix $H$, and how does it help capture long-range dependencies?\n\n5. How could the proposed approach be adapted if the matrices $A$, $B$, and $C$ were unknown?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Overall, the paper is clearly written and presents a significant improvement over prior work in terms of computational efficiency. However, my main concern is the lack of motivation and contextualization of this main contribution, particularly in the introduction and broader discussion.\nI would also suggest providing more interpretative insight into the proposed method and to better contextualize the theoretical results by discussing potential practical applications or scenarios where such improvements could be impactful.\n\n\n\n### Strengths\n\n- The paper is clearly written, and the mathematical framework is well introduced.\n- The related work is appropriately referenced and contextualized.\n- The results are clearly presented, with intuitive explanations accompanying the formal statements.\n- The theoretical contributions are rigorously derived, with relevant definitions, lemmas, and theorems.\n- The limited experiments suggest that for a fixed memory budget, the proposed algorithm outperforms LQG and GRC controllers.\n- While I am not a specialist in this subfield, the mathematical arguments appear sound.\n\n### Weaknesses\n\n\n**Presentation and motivation of the main contribution**\n\n- The main contribution of the paper lies in the improved runtime complexity of the proposed algorithm.\nWhile I recognize that the focus of this work is theoretical, I believe that a brief discussion of the potential implications or contexts where improved complexity would improve the practical relevance of the work. For instance, it remains unclear in which settings compute becomes a primary bottleneck, especially the spectral radius dependence, or how this improvement could concretely benefit applications. \n- As noted in the Related Work section, convex parameterizations have been explored in other approaches. However, the paper does not clearly explain how the defined memory-less convex loss compares to others such as GRC. An intuitive explanation of why the proposed relaxation leads to runtime improvements would be valuable.\n\n**Modeling choices**\n\n- The motivation behind the choice of state-space model and convex loss is not sufficiently grounded in real-world examples. Applications are only briefly mentioned in the introduction.  \n- For example, many classical control problems involve tracking a desired state, where the cost function is a convex function of the state-input pair, $c_t(x, u)$, not the observation-input pair, $c_t(y, u)$. While I understand that the latter allows for theoretical tractability and follows conventions in the literature, it would be helpful to provide some discussion or illustrative examples of how such time-varying convex costs on observations and inputs arise in real-world settings.\n\n**Experimental validation**\n\n- The experimental section is minimal and relegated to the appendix. Key details, such as the explicit form of the time-varying cost function, are missing.\n- Importantly, although the computational improvement is the main contribution of the paper, the runtime is not reported in the experiments.\n- Including more extensive experiments in the main paper would enhance the impact and help readers assess the practical relevance of the method.\n\n\n\n**Technical clarification**\n\n- I believe that there is an issue in the definition of $\\gamma$. Indeed, $1-\\gamma$ is defined as the spectral radius of the closed loop matrix, which is denoted as $C_\\pi$ in the submission, and depends on policy $\\pi$. Rather, $1-\\gamma$ should be defined as the spectral radius $A$ for the definition to be consistent with the results reported in Table 1.", "was_revised": true, "final_justification": "As someone less familiar with the technical literature in this theoretical subfield of online control, I find the theoretical contributions clear and well executed. I have concerns regarding the applicability and practical motivation of the approach, which I hope the authors might further elaborate on in future revisions or discussions.\n\nI strongly encourage the authors to include a thorough discussion on the modeling choice and the applicability of the studied setup in a revised version of the submission, with simple concrete examples from control.", "rebuttal": "We thank the reviewer for their thoughtful comments and helpful suggestions. We will first address the pointed weaknesses:\n\n**Presentation and motivation of the main contribution.**  \n\nOur algorithm improves the runtime complexity of the full control procedure, which we expect to lead to practical runtime gains. Additionally, our method requires fewer parameters, which is often associated with better generalization in statistical learning settings.  \n\nWe discuss the significance of improved dependence on the stability margin in the introduction (see the paragraph titled *“Marginal Stability and Spectral Filters”*), where we explain that small margins arise in practical systems requiring smooth control inputs such as robotics, thermal regulation systems, and satellite dynamics, where aggressive control is not feasible and long-term memory must be preserved. We will consider expanding this discussion further to strengthen the motivation.  \n\nRegarding the choice of loss function: our use of a memoryless convex loss is simply an alternative analysis approach that we believe is clearer than the one in [22], which reduces online control to online convex optimization with memory. Our analysis is more direct and inspired by the approach taken in [15], and we will consider emphasizing this distinction in the camera-ready version. Both works rely on surrogate losses and implicitly manage effective memory.  \n\nOur main innovation is not in the loss presentation but in the convex relaxation: by projecting onto the eigenbasis of a particular Hankel matrix, we obtain a controller representation that depends on only $O(\\log(1/\\gamma))$ terms, as opposed to a polynomial number. This structural insight drives our improved runtime.\n\n**Modeling choices.**  \nState-space models with convex loss functions are standard in the control literature and arise in numerous applications (e.g., robotics, economics, mechanical systems). We will consider citing more concrete examples in the introduction.  \n\nRegarding the cost structure: since the controller only has access to observations and not the full state, it is not possible to directly minimize a cost function over the full state. While the underlying environment may depend on the full state, regret analysis (in the full-information setting) is meaningful only when the cost functions are defined over the observed quantities. This restriction could potentially be relaxed in a bandit setting, which we leave for future work. We will clarify this point in the paper.\n\n**Experimental validation.**  \nWe appreciate the suggestion to expand the experiments and agree that it would significantly strengthen the impact and practical relevance of our method. While we agree that demonstrating runtime improvement is important for our work, we chose to include only a preliminary empirical evaluation, intended as a first glimpse into the algorithm’s practical potential.  \n\nThe cost functions in our experiments are of quadratic form  \n$c_t(y_t, u_t) = y_t^\\top Q_{\\text{obs}} y_t + u_t^\\top R u_t$,  \ngiven the observation $y_t$ and the computed control $u_t$ at time step $t$. This choice is made to enable comparison with other methods that only work for quadratic forms.\n\nFor the implementing the training update step, we use the memoryless loss  \n$\\ell_t(M, \\bar{M}) = y_t(M)^\\top Q_{\\text{obs}} y_t(M) + u_t(M)^\\top R u_t(M)$  \nas in Definition 3.8.\n\n**Technical clarification.**  \nThe margin $1 - \\gamma$ in our work is defined with respect to both the system matrices and the comparator class of LDCs. This is consistent with how the stability margin $\\rho$ is defined in [22] (see their Assumption 4).\n\n**Responses to specific questions:**\n\n*Comparing Equations (1) and (3).*  \nThe learner controls the inputs, while disturbances are adversarially chosen by the environment. Equation (3) is taken directly from Lemma 12.7 in [15], where $y_{\\text{nat}}$ represents the output had the learner applied zero control.\n\n*Line 144 (independence of $y_{\\text{nat}}$).*  \nBecause $y_{\\text{nat}}$ is generated under zero control, it is independent of the learner’s parameters. This avoids circular dependencies that would otherwise introduce nonconvexities into the problem, e.g., via multiplicative parameter terms.\n\n*Use of “learning.”*  \nWe agree that this is fundamentally a control problem and will consider emphasizing this framing more clearly. That said, the decision-maker is learning in the sense of approximating the best policy in hindsight.\n\n*Interpretation of the filter matrix.*  \nThis matrix arises naturally in our analysis and is inspired by recent advances in prediction for linear dynamical systems, where similar Hankel-based constructions are used for convex relaxation. See [16] for context.\n\n*Unknown system matrices.*  \nIn the unknown dynamics setting, one could first perform system identification and then apply our method. This is similar in spirit to the approach taken in  \n*Chen & Hazan (2021), “Black-Box Control for Linear Dynamical Systems,” arXiv:2007.06650*.  \nWe can mention this extension further in the paper."}]

Author rebuttal:

Meta-review: This paper proposes a new method for controlling partially observed linear dynamical systems with known dynamics. In the considered setting, costs and potentially adversarial disturbances are revealed sequentially, and the goal is to design an efficient algorithm that also achieves desirable regret guarantees. The authors’ proposed method successfully accomplishes both.

Three reviews were received. All reviewers agreed that the paper provides interesting results and introduces a novel methodology. One reviewer noted that the idea of pre-filtering observations to improve dependencies on the stability margin is particularly interesting. The reviewers also confirmed that the paper is well written. On the critical side, however, some highlighted potentially restrictive assumptions (Assumption 3.5 and Definition 3.4). In addition, they noted that more references to relevant work in the control community would strengthen the paper, and they questioned the practical relevance of the proposed method given the very preliminary nature of the experiments.

Overall, the AC concurs with the reviewers that the strengths of the paper outweigh its weaknesses, but strongly encourages the authors to address the reviewers’ comments in their revision, as promised.
Decision: Accept (poster)