Timezone: »

 
Poster
Optimal Dynamic Regret in LQR Control
Dheeraj Baby · Yu-Xiang Wang

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #827
in Poster Session 3 »
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 $\tilde{O}(n^{1/3} \mathcal{TV}(M_{1:n}^{2/3} \vee 1)$, where $\mathcal{TV}(M_{1:n})$ is the total variation of any oracle sequence of \emph{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 $\tilde{O}(\sqrt{n (\mathcal{TV}(M_{1:n})+1)} )$ for general convex losses and is information-theoretically optimal for LQR. Main technical components include the reduction of LQR to online linear regression with delayed feedback due to Foster & Simchowitz 2020, as well as a new \emph{proper} learning algorithm with an optimal $\tilde{O}(n^{1/3})$ dynamic regret on a family of "minibatched'' quadratic losses, which could be of independent interest.
Keywords: Online Learning · Individual sequence prediction · Dynamic regret · Online linear regression · Online non-paramteric regression · LQR control

Author Information

Dheeraj Baby (UC Santa Barbara)
Yu-Xiang Wang (UC Santa Barbara)

More from the Same Authors