A New Approach to Controlling Linear Dynamical Systems

We present new algorithms for controlling linear dynamical systems subject to adversarial disturbances and cost functions, in both full and partial observation settings. Our methods match the best known regret guarantees while exponentially improving the runtime dependence on the system's stability margin. The core technique is a novel spectral filtering approach, which approximates desired controllers using convolution of certain history with eigenvectors of carefully constructed Hankel matrices. In the partially observed case, we introduce a two-level spectral approximation strategy that enables efficient and accurate policy learning via double convolution with a universal basis of spectral filters.