On the Sample Complexity of the Linear Quadratic Regulator

By Sarah Dean, Horia Mania, Nikolai Matni, B. Recht, Stephen Tu. 2017

642 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Control and Systems Engineering, Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Control and Systems Engineering

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Recent works in this line of research include (Alaeddini et al., 2018; Arora et al., 2018b; Dean et al., 2017; 2018; Hardt et al., 2018; Hazan et al., 2017; 2018; Marecek & Tchrakian, 2018; Oymak & Ozay, 2018; Simchowitz et al., 2018).”
When to Trust Your Model: Model-Based Policy Optimization (2019, methodology): “Prior work has also constructed complexity bounds for model-based approaches in the tabular setting (Szita & Szepesvari, 2010) and for the linear quadratic regulator (Dean et al., 2017), whereas we consider general non-linear systems.”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, methodology): “…Lakshmanan et al., 2015; Hinderer, 2005; Pirotta et al., 2015; 2013), or the linear parametrization of the dynamics, policy, or value function (Abbasi-Yadkori & Szepesvári, 2011; Simchowitz et al., 2018; Dean et al., 2017; Sutton et al., 2012; Tamar et al., 2012), but not much on non-linear models.”
Simple random search provides a competitive approach to reinforcement learning (2018, methodology): “Consider the LQR instance deﬁned introduced by Dean et al. [4] as a challenging low-dimensional instance for LQR with unknown dynamics.”
Model-Based Value Estimation for Efficient Model-Free Reinforcement Learning (2018, neutral): “In contrast, model-based (MB) methods can quickly arrive at near-optimal control with learned models under fairly restricted dynamics classes (Dean et al., 2017).”
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “For instance, many require that the MDP admits a linear approximation [6–8], or that the model is precisely Linear Quadratic Regulator (LQR) [9–11].”
Behavioral systems theory in data-driven analysis, signal processing, and control (2021, methodology): “We refer to (Dean et al., 2019; Umenberger et al., 2019; Treven et al., 2020; Mania et al., 2019) for recent analysis, performance estimates for finite sample size, as well as various comparisons.”
Robust Spectral Filtering and Anomaly Detection (2018, background): “Subsequently, a number of authors [11, 1, 14, 15, 3, 7] have applied them to the (Linear-Quadratic, LQ) control of an unknown system, which underlies much of reinforcement learning.”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, background): “More recently, Dean et al. (2017) expands on an explicit system identiﬁcation process, where a robust control synthesis procedure is adopted that relies on a coarse model of the plant matrices ( A and B are estimated up to some accuracy level, naturally leading to a “robust control” setup to then…”
From Noisy Data to Feedback Controllers: Nonconservative Design via a Matrix S-Lemma (2020, background): “This is an advantage over closed-loop system parameterizations [37], [39], which become computationally intractable when applied to big data.”
Safely Learning to Control the Constrained Linear Quadratic Regulator (2018, background): “The appendix of [1] presents this reformulation in terms of system responses for Gaussian process noise, but the argument applies unchanged to any distribution satisfying our assumptions.”
Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification (2018, background): “In future, we hope to develop sharp error rates for A∗ and B∗ individually, similar to Dean et al. [2017] in the independent covariates setting.”
Data-Enabled Predictive Control: In the Shallows of the DeePC (2018, background): “In this spirit, an end-to-end ID and control pipeline is given in [6] and arrives at a data-driven control solution with guarantees on the sample efficiency, stability, performance, and robustness.”
Linear Model Regression on Time-series Data: Non-asymptotic Error Bounds and Applications (2018, methodology): “This can be due to a range of factors from the unpredictable nature of the environment to perturbations and uncertainties in the complex system [5], [14].”
Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator (2018, methodology): “[6] to provide non-asymptotic bounds for LQR in the offline “estimate-and-then-control” setting.”
Finite-Data Performance Guarantees for the Output-Feedback Control of an Unknown System (2018, methodology): “There have been many recent results (see for example [1, 2, 3, 4, 5, 6] and the references within) that apply state-of-the-art machine learning techniques to the control of systems with continuous action spaces.”