Timezone: »

 
Oral
Logarithmic Regret for Online Control
Naman Agarwal · Elad Hazan · Karan Singh

Tue Dec 10 10:05 AM -- 10:20 AM (PST) @ West Exhibition Hall A
in Track 2 Session 1 »

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 influential frameworks such as the Kalman filter and the linear quadratic regulator. State of the art methods achieve regret which scales as T^0.5, where T is the time horizon.

We show that the optimal regret in this fundamental setting can be significantly smaller, scaling as polylog(T). This regret bound is achieved by two different efficient iterative methods, online gradient descent and online natural gradient.

Author Information

Naman Agarwal (Google)
Elad Hazan (Princeton University)
Karan Singh (Princeton University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors