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(T)$, where $T$ is
the time horizon.
We show that the optimal regret in this setting can be significantly smaller,
scaling as $O(poly(T))$. This regret bound is achieved by two
different efficient iterative methods, online gradient descent and online
natural gradient.
Description
[1909.05062] Logarithmic Regret for Online Control
%0 Journal Article
%1 agarwal2019logarithmic
%A Agarwal, Naman
%A Hazan, Elad
%A Singh, Karan
%D 2019
%K bounds convergence optimization readings
%T Logarithmic Regret for Online Control
%U http://arxiv.org/abs/1909.05062
%X 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(T)$, where $T$ is
the time horizon.
We show that the optimal regret in this setting can be significantly smaller,
scaling as $O(poly(T))$. This regret bound is achieved by two
different efficient iterative methods, online gradient descent and online
natural gradient.
@article{agarwal2019logarithmic,
abstract = {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.},
added-at = {2019-09-20T13:49:01.000+0200},
author = {Agarwal, Naman and Hazan, Elad and Singh, Karan},
biburl = {https://www.bibsonomy.org/bibtex/24ea9b19a65fc29ba0591860c8565d1f4/kirk86},
description = {[1909.05062] Logarithmic Regret for Online Control},
interhash = {21360c83df50acfe92e8a26d4394217f},
intrahash = {4ea9b19a65fc29ba0591860c8565d1f4},
keywords = {bounds convergence optimization readings},
note = {cite arxiv:1909.05062},
timestamp = {2019-11-04T11:39:12.000+0100},
title = {Logarithmic Regret for Online Control},
url = {http://arxiv.org/abs/1909.05062},
year = 2019
}