2020/01/25 by Max Simchowitz, Karan Singh, Simchowitz, Max +3 · 5 citations
Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Control Systems Optimization #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2001.09254
openalex publication_date 2020/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 √(T)-when the system is known, and, when combined with an initial stage of least-squares estimation, T2/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 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 poly(log T) when the system is known, and √(T) when unknown. To our knowledge, this gives the first end-to-end √(T) regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.