Logarithmic Regret for Online Control
This provides a logarithmic regret bound for online control, which is a foundational improvement in control theory and reinforcement learning, though incremental in the context of known dynamics.
The paper tackles the problem of optimal regret bounds for control in linear dynamical systems with adversarially changing strongly convex cost functions, showing that regret can scale as O(poly(log T)), significantly improving over the state-of-the-art O(sqrt(T)).
We study optimal regret bounds for control in linear dynamical systems under adversarially changing strongly convex cost functions, given the knowledge of transition dynamics. This includes several well studied and fundamental frameworks such as the Kalman filter and the linear quadratic regulator. State of the art methods achieve regret which scales as $O(\sqrt{T})$, where $T$ is the time horizon. We show that the optimal regret in this setting can be significantly smaller, scaling as $O(\text{poly}(\log T))$. This regret bound is achieved by two different efficient iterative methods, online gradient descent and online natural gradient.