A New Approach to Controlling Linear Dynamical Systems

Anand Brahmbhatt, Gon Buzaglo, Sofiia Druchyna, Elad Hazan

Introduction

In classical control theory, such as the Linear Quadratic Regulator (LQR), researchers typically assume that noise is well-behaved (random and zero-mean) and cost functions are fixed. However, real-world applications like robotics or thermal management often face "adversarial" disturbances that do not follow neat distributions, alongside costs that fluctuate over time.

The paper introduces Online Spectral Control (OSC), a new algorithm designed for controlling linear systems under these unpredictable conditions. Its primary breakthrough is a massive efficiency gain: while previous methods slowed down significantly as systems approached instability, OSC’s runtime scales only logarithmically with the stability margin, making it both faster and more effective for complex, real-world control tasks.

The Problem: Breaking the "Polynomial Wall"

Online Control aims to minimize regret—the difference between the cost incurred by an algorithm and the cost of the best possible fixed policy in hindsight. A major bottleneck in current state-of-the-art methods, such as the Gradient Perturbation Controller (GPC), is their dependence on the stability margin ($\gamma$).

When a system is "marginally stable" (meaning it takes a long time to recover from a disturbance), previous algorithms required a polynomial explosion in the number of parameters and runtime. OSC aims to break this "polynomial wall" by achieving logarithmic scaling.

Methods: Online Spectral Control

Instead of learning a direct mapping from every past disturbance to a control input, OSC uses a mathematical shortcut based on spectral components:

  1. Spectral Filtering: The algorithm constructs "universal" spectral filters using the top eigenvectors of a specific Hankel matrix. These filters depend only on the desired stability margin, not the specific system or cost function.
  2. Convex Relaxation: By convolving past disturbances with these spectral filters, the authors create a convex relaxation of the control problem, allowing for efficient learning via Projected Online Gradient Descent (OGD).
  3. Fast Convolution: OSC leverages modern online convolution techniques to process disturbances in $O(\log^4 (T/\gamma))$ time, a significant leap over the previous $O(1/\gamma)$ benchmarks.
Spectral filters for different stability margins (γ), showing how the filter response changes as the system approaches instability.

Key Results and Theoretical Impact

OSC maintains strong theoretical guarantees while providing a massive speedup in runtime. As shown in the comparison below, OSC is the first method to achieve logarithmic time complexity relative to the stability margin while handling adversarial disturbances and online convex costs.

Comparison of OSC with existing control methods, highlighting the logarithmic runtime and competitive regret bounds.

Empirical Performance

The researchers evaluated OSC using synthetic benchmarks (Linear Signal, ReLU State Transition, and STU Signal) with a state dimension of $d=100$ and a control dimension of $n=40$. In head-to-head tests against GPC, OSC consistently incurred lower cumulative loss across all benchmarks while using significantly fewer parameters.

Key Insights

  • The Power of Hankel Matrices: The complex history of a dynamical system can be compressed into a few spectral components. By focusing on the top eigenvectors of a Hankel matrix, optimal control policies can be approximated with very few learnable parameters.
  • Universality: You don't need to know the exact system dynamics to build the filters; you just need to know the target stability margin.
  • Logarithmic Scaling: By moving from polynomial to logarithmic dependence on $1/\gamma$, the algorithm remains performant even when the system has "long memory" and disturbances persist.

Limitations and Future Work

While OSC represents a significant step forward, several areas remain for future exploration:

  • Known Dynamics: The current algorithm assumes system matrices ($A$ and $B$) are known. Future work could extend this to settings where dynamics must be learned on the fly.
  • Partial Observation: Adapting OSC for output feedback, where only a noisy or incomplete version of the state is visible, is a natural next step.
  • Regret Factor: Future research may investigate if the $\gamma^{-4}$ dependence in the regret bound can be tightened without sacrificing the logarithmic runtime.

Summary updated

BibTeX
@inproceedings{brahmbhatt2026new,
  author = {Anand Brahmbhatt and Gon Buzaglo and Sofiia Druchyna and Elad Hazan},
  title = {{A New Approach to Controlling Linear Dynamical Systems}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=BQIzu1T6F0},
}
Figure