Optimal Dynamic Regret in LQR Control
share
We consider the problem of nonstochastic control with a sequence of quadratic losses, i.e., LQR control. We provide an efficient online algorithm that achieves an optimal dynamic (policy) regret of Γ(max{n^1/3π―π±(M_1:n)^2/3, 1}), where π―π±(M_1:n) is the total variation of any oracle sequence of Disturbance Action policies parameterized by M_1,...,M_n β chosen in hindsight to cater to unknown nonstationarity. The rate improves the best known rate of Γ(β(n (π―π±(M_1:n)+1)) ) for general convex losses and we prove that it is information-theoretically optimal for LQR. Main technical components include the reduction of LQR to online linear regression with delayed feedback due to Foster and Simchowitz (2020), as well as a new proper learning algorithm with an optimal Γ(n^1/3) dynamic regret on a family of βminibatchedβ quadratic losses, which could be of independent interest.
READ FULL TEXT