Making Non-Stochastic Control (Almost) as Easy as Stochastic

Understand

Recent literature has made much progress in understanding \emph{online LQR}: a modern learning-theoretic take on the classical control problem in which a learner attempts to optimally control an unknown linear dynamical system with fully observed state, perturbed by i.i.d.

• Gaussian noise.
• It is now understood that the optimal regret on time horizon $T$ against the optimal control law scales as $\widetilde{\Theta}(\sqrt{T})$.
• In this paper, we show that the same regret rate (against a suitable benchmark) is attainable even in the considerably more general non-stochastic control model, where the system is driven by \emph{arbitrary adversarial} noise (Agarwal et al.