Logarithmic regret for online control

Naman Agarwal, Elad Hazan, Karan Singh

Research output: Contribution to journalConference articlepeer-review

52 Scopus citations


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(vT), where T is the time horizon. We show that the optimal regret in this setting can be significantly smaller, scaling as O(poly(log T)). This regret bound is achieved by two different efficient iterative methods, online gradient descent and online natural gradient.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
StatePublished - 2019
Event33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 - Vancouver, Canada
Duration: Dec 8 2019Dec 14 2019

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Logarithmic regret for online control'. Together they form a unique fingerprint.

Cite this