A Caltech Library Service

On the Sample Complexity of the Linear Quadratic Regulator

Dean, Sarah and Mania, Horia and Matni, Nikolai and Recht, Benjamin and Tu, Stephen (2020) On the Sample Complexity of the Linear Quadratic Regulator. Foundations of Computational Mathematics, 20 (4). pp. 633-679. ISSN 1615-3375.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper addresses the optimal control problem known as the linear quadratic regulator in the case when the dynamics are unknown. We propose a multistage procedure, called Coarse-ID control, that estimates a model from a few experimental trials, estimates the error in that model with respect to the truth, and then designs a controller using both the model and uncertainty estimate. Our technique uses contemporary tools from random matrix theory to bound the error in the estimation procedure. We also employ a recently developed approach to control synthesis called System Level Synthesis that enables robust control design by solving a quasi-convex optimization problem. We provide end-to-end bounds on the relative error in control cost that are optimal in the number of parameters and that highlight salient properties of the system to be controlled such as closed-loop sensitivity and optimal control magnitude. We show experimentally that the Coarse-ID approach enables efficient computation of a stabilizing controller in regimes where simple control schemes that do not take the model uncertainty into account fail to stabilize the true system.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Matni, Nikolai0000-0003-4936-3921
Additional Information:© 2019 SFoCM. Received 08 February 2018; Revised 03 December 2018; Accepted 22 February 2019; First Online 05 August 2019. This work was generously supported in part by NSF award CCF-1359814, ONR awards N00014-14-1-0024 and N00014-17-1-2191, the DARPA Fundamental Limits of Learning Program, a Sloan Research Fellowship, and a Google Faculty Award. SD is additionally supported by an NSF Graduate Research Fellowship under Grant No. DGE 1752814. NM is additionally supported by grants from the AFOSR and NSF, and by gifts from Huawei and Google. We thank Ross Boczar, Qingqing Huang, Laurent Lessard, Michael Littman, Manfred Morari, Andrew Packard, Anders Rantzer, Daniel Russo, and Ludwig Schmidt for many helpful comments and suggestions. We also thank the anonymous referees for making several suggestions that have significantly improved the paper and its presentation.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-14-1-0024
Office of Naval Research (ONR)N00014-17-1-2191
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
NSF Graduate Research FellowshipDGE-1752814
Subject Keywords:Optimal control; Robust control; System identification; Statistical learning theory; Reinforcement learning; System level synthesis
Issue or Number:4
Classification Code:Mathematics Subject Classification: 49N05; 93D09; 93D21; 93E12; 93E35
Record Number:CaltechAUTHORS:20190806-130716007
Persistent URL:
Official Citation:Dean, S., Mania, H., Matni, N. et al. On the Sample Complexity of the Linear Quadratic Regulator. Found Comput Math 20, 633–679 (2020).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97674
Deposited By: Tony Diaz
Deposited On:07 Aug 2019 15:01
Last Modified:03 Aug 2020 22:29

Repository Staff Only: item control page