The Nonstochastic Control Problem
This addresses a fundamental challenge in robust control for systems with adversarial noise, offering a novel regret-based approach for nonstochastic settings.
The paper tackles the problem of controlling an unknown linear dynamical system with adversarial perturbations and convex losses, where traditional optimal control is infeasible due to unknown future inputs. It presents an efficient algorithm achieving sublinear regret of T^{2/3} against an optimal linear policy in hindsight.
We consider the problem of controlling an unknown linear dynamical system in the presence of (nonstochastic) adversarial perturbations and adversarial convex loss functions. In contrast to classical control, the a priori determination of an optimal controller here is hindered by the latter's dependence on the yet unknown perturbations and costs. Instead, we measure regret against an optimal linear policy in hindsight, and give the first efficient algorithm that guarantees a sublinear regret bound, scaling as T^{2/3}, in this setting.