Efficient Spectral Control of Partially Observed Linear Dynamical Systems

We thank the reviewer for their thoughtful comments and helpful suggestions. We will first address the pointed weaknesses:

Presentation and motivation of the main contribution.

Our 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.

We 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.

Regarding 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.

Our 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.

Modeling choices.
State-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.

Regarding 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.

Experimental validation.
We 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.

The cost functions in our experiments are of quadratic form
$c_t(y_t, u_t) = y_t^\top Q_{\text{obs}} y_t + u_t^\top R u_t$,
given 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.

For the implementing the training update step, we use the memoryless loss
$\ell_t(M, \bar{M}) = y_t(M)^\top Q_{\text{obs}} y_t(M) + u_t(M)^\top R u_t(M)$
as in Definition 3.8.

Technical clarification.
The 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).

Responses to specific questions:

Comparing Equations (1) and (3).
The 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.

Line 144 (independence of $y_{\text{nat}}$).
Because $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.

Use of “learning.”
We 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.

Interpretation of the filter matrix.
This 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.

Unknown system matrices.
In 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
Chen & Hazan (2021), “Black-Box Control for Linear Dynamical Systems,” arXiv:2007.06650.
We can mention this extension further in the paper.

Thank you for your thorough rebuttal.

These clarifications, particularly those concerning the loss minimization formalism, improve understanding the theoretical framing. Including these explanations in the final version would definitely strengthen the paper.

That said, I still find it somewhat difficult to understand the motivation behind focusing specifically on the dependence in the stability margin. While the rebuttal mentions domains such as robotics, it would help to elaborate on when the spectral radius becomes a practical bottleneck in such settings. Are there concrete scenarios where this dependency dominates over other factors, such as model uncertainty or actuation constraints?

Similarly, I appreciate the discussion on the loss structure, but I would be interested in seeing examples, either synthetic or drawn from prior literature, where time-varying convex losses on observations, rather than state, arise in applications. The classical setting that I am aware of in online control is a trajectory optimization cost depending on unobserved states, from which the trajectory and the inputs are optimized for. In this case, the observations are only used to estimate the current state, which is used as an initial conditon for the trajectory optimization problem. How does the framework understudy relate to this setting?

As someone less familiar with the technical literature in this theoretical subfield of online control, I find the theoretical contributions clear and well executed. My questions primarily concern the broader applicability and practical motivation of the approach, which I hope the authors might further elaborate on in future revisions or discussions.

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.

Weaknesses
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.
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.
References: We will expand and improve the descriptions of referenced works throughout the paper to ensure clarity and completeness.

Questions
Examples of small $\gamma$: Please see our response above and Section 9 in [7].
$\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.
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.

We thank the reviewer for his thorough reading of our paper and proofs and giving educated comments about our work.

Response to Comment on Definition 3.4 and Assumption 3.5
We thank the reviewer for raising this important point.
Definition 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.
Indeed, 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.
That 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:
Marsden & Hazan (2025), Universal Sequence Preconditioning, arXiv:2502.06545.
We will consider discussing this direction in the camera-ready version.
Finally, 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.

Response to Comment on Regret Bound and Comparison with [22]
We appreciate the reviewer’s request for clarification on the regret dependence in our work versus [22].
In 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.
Our 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.

Response to Comment on Related Work
We 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.

Response to Comment on Spectral Filtering Intuition
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, \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.
Regarding 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.

Response to Comment on Double Filtering
Our 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$.
It 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.

Response to Comment on Corollary 4.4
We 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.

Response to Comment on Experiments
We 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.
For all conducted experiments, we ensured that the system matrix $A$ is symmetric with real eigenvalues between 0 and 0.8.
We 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.

Response to Comment on Theory vs. Experiments
We 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.

Other Comments
i) 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.
ii) 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.
iii) 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.
iv) 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.
v) $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.
vi) The reviewer is also correct about the final typo. We will fix this in the camera-ready version; those terms cancel out.