Black-Box Control for Linear Dynamical Systems

Xinyi Chen, Elad Hazan

Research output: Contribution to journalConference articlepeer-review

26 Scopus citations


We consider the problem of black-box control: the task of controlling an unknown linear time-invariant dynamical system from a single trajectory without a stabilizing controller. Under the assumption that the system is controllable, we give the first efficient algorithm that attains sublinear regret under the setting of online nonstochastic control. This resolves an open problem since the work of Abbasi-Yadkori and Szepesvári (2011) on the stochastic black-box LQR problem, and in a more general setting that allows for adversarial perturbations and adversarially chosen changing convex loss functions. We give finite-time regret bounds for our algorithm on the order of 2poly(d) + Õ(poly(d)T2/3) for general nonstochastic control, and 2poly(d) + Õ(poly(d)√T) for black-box LQR. To complete the picture, we investigate the complexity of the online black-box control problem and give a matching regret lower bound of 2Ω(d), showing that the exponential cost is inevitable. This lower bound holds even in the noiseless setting, and applies to any, randomized or deterministic, black-box control method.

Original languageEnglish (US)
Pages (from-to)1114-1143
Number of pages30
JournalProceedings of Machine Learning Research
StatePublished - 2021
Externally publishedYes
Event34th Conference on Learning Theory, COLT 2021 - Boulder, United States
Duration: Aug 15 2021Aug 19 2021

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Black-Box Control for Linear Dynamical Systems'. Together they form a unique fingerprint.

Cite this