Logarithmic Regret for Online Control with Adversarial Noise

Part of Proceedings of the International Conference on Machine Learning 1 pre-proceedings (ICML 2020)

Bibtex »Metadata »Paper »Supplemental »

Bibtek download is not availble in the pre-proceeding


Dylan Foster, Max Simchowitz


We consider the problem of online control in a known linear dynamical system subject to adversarial noise. Existing regret bounds for this setting scale as $\sqrt{T}$ unless strong stochastic assumptions are imposed on the noise. We give the first algorithm with logarithmic regret for arbitrary adversarial noise sequences, provided that the state and control costs are given by fixed quadratic functions. We propose a novel analysis that combines a new variant of the performance difference lemma with techniques from optimal control, allowing us to reduce online control to online prediction with delayed feedback. Unlike prior work, which leverages the so-called online convex optimization with memory framework, our analysis \emph{does not} need to bound movement costs of the iterates, leading to logarithmic regret. Our performance difference lemma-based analysis may be of broader interest beyond linear control.