# Improper Learning for Non-Stochastic Control

Source: [Improper Learning for Non-Stochastic Control](<https://www.sota2.com/research/paper/68fa57171e209131ce9a25eb>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T14:32:44.520Z

Authors: Max Simchowitz, Karan Singh, Elad Hazan

Published: 2020-01-25T02:12:48.000Z

## Abstract

We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that applying online gradient descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. In the fully-adversarial setting, our controller attains an optimal regret bound of $\\sqrt{T}$-when the system is known, and, when combined with an initial stage of least-squares estimation, $T^{2/3}$ when the system is unknown; both yield the first sublinear regret for the partially observed setting.   Our bounds are the first in the non-stochastic control setting that compete with \\emph{all} stabilizing linear dynamical controllers, not just state feedback. Moreover, in the presence of semi-adversarial noise containing both stochastic and adversarial components, our controller attains the optimal regret bounds of $\\mathrm{poly}(\\log T)$ when the system is known, and $\\sqrt{T}$ when unknown. To our knowledge, this gives the first end-to-end $\\sqrt{T}$ regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Online Control on LQR/LQG theoretical settings](<https://www.sota2.com/research/sota/online-control-on-lqr-lqg-theoretical-settings.md>): Online Control; LQR/LQG theoretical settings; Regret: 1.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2001.09254>)

[PDF](<https://arxiv.org/pdf/2001.09254.pdf>)
