2017

On the Sample Complexity of the Linear Quadratic Regulator

Dean, Sarah, Mania, Horia, Matni, Nikolai et al.

Understand

This paper addresses the optimal control problem known as the Linear Quadratic Regulator in the case when the dynamics are unknown.

We propose a multi-stage 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 convex optimization problem.

Built on

Modern Wiener-Hopf design of optimal controllers–Part II: The multivariable case
D. Youla, H. Jabr, and J. Bongiorno · 1976
Earlier work this paper cites.
Bootstrap Methods: Another Look at the Jackknife
B. Efron · 1979
Earlier work this paper cites.
Analysis of feedback systems with structured uncertainties
J. Doyle · 1982
Earlier work this paper cites.
Robustness in the presence of mixed parametric uncertainty and unmodeled dynamics
M. K. H. Fan, A. L. Tits, and J. C. Doyle · 1991
Earlier work this paper cites.
Control Oriented System Identification: A Worst-Case/Deterministic Approach in
A. J. Helmicki, C. A. Jacobson, and C. N. Nett · 1991
Earlier work this paper cites.
μ \mu Analysis with Real Parametric Uncertainty
P. M. Young, M. P. Newlin, and J. C. Doyle · 1991
Earlier work this paper cites.
The Carathéodory-Fejér Problem and
J. Chen and C. N. Nett · 1993
Earlier work this paper cites.
The Complex Structured Singular Value
A. Packard and J. Doyle · 1993
Earlier work this paper cites.
Computational Complexity of
R. P. Braatz, P. M. Young, J. C. Doyle, and M. Morari · 1994
Earlier work this paper cites.
Adaptive linear quadratic control using policy iteration
S. J. Bradtke, B. E. Ydstie, and A. G. Barto · 1994
Earlier work this paper cites.
Control of Uncertain Systems: A Linear Programming Approach
M. A. Dahleh and I. J. Diaz-Bobillo · 1994
Earlier work this paper cites.
Rates of Convergence for Empirical Processes of Stationary Mixing Sequences
B. Yu · 1994
Earlier work this paper cites.
Necessary and Sufficient Conditions for Robust
F. Paganini · 1995
Earlier work this paper cites.
A formula for computation of the real stability radius
L. Qiu, B. Bernhardsson, A. Rantzer, E. J. Davison, P. Young, and J. Doyle · 1995
Earlier work this paper cites.
Optimal LQG performance of linear uncertain systems using state-feedback
F. Wu and A. Packard · 1995
Earlier work this paper cites.
Robust and Optimal Control
K. Zhou, J. C. Doyle, and K. Glover · 1995
Earlier work this paper cites.
Weak Convergence and Empirical Processes
A. W. Van Der Vaart and J. A. Wellner · 1996
Earlier work this paper cites.
Analysis of Robust
E. Feron · 1997
Earlier work this paper cites.
PAC Adaptive Control of Linear Systems
C.-N. Fiechter · 1997
Earlier work this paper cites.
System analysis via integral quadratic constraints
A. Megretski and A. Rantzer · 1997
Earlier work this paper cites.
Nonparametric Estimation of Transfer Functions: Rates of Convergence and Adaptation
A. Goldenshluger · 1998
Earlier work this paper cites.

Similar

System Identification: Theory for the User
L. Ljung · 1999
Cited alongside, same era.
Control-Oriented System Identification: An ℋ ∞ \mathcal{H}_{\infty} Approach
J. Chen and G. Gu · 2000
Cited alongside, same era.
Nonasymptotic bounds for autoregressive time series modeling
A. Goldenshluger and A. Zeevi · 2001
Cited alongside, same era.
Finite Sample Properties of System Identification Methods
M. C. Campi and E. Weyer · 2002
Cited alongside, same era.
A convex approach to robust
M. Sznaier, T. Amishima, P. A. Parrilo, and J. Tierno · 2002
Cited alongside, same era.
Iterative Linear Quadratic Regulator Design for Nonlinear Biological Movement Systems
W. Li and E. Todorov · 2004
Cited alongside, same era.
YALMIP : A toolbox for modeling and optimization in MATLAB
J. Löfberg · 2004
Cited alongside, same era.
Positive trigonometric polynomials and signal processing applications
B. Dumitrescu · 2007
Cited alongside, same era.
Time Series Analysis: Forecasting and Control
G. E. P. Box, G. M. Jenkins, and G. C. Reinsel · 2008
Cited alongside, same era.
A learning theory approach to system identification and stochastic adaptive control
M. Vidyasagar and R. L. Karandikar · 2008
Cited alongside, same era.
Learning Networks of Stochastic Differential Equations
J. Bento, M. Ibrahimi, and A. Montanari · 2010
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
Original
R. Vershynin · 2010
Cited alongside, same era.

Then

Mastering the game of go with deep neural networks and tree search
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershevlvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis · 2016
Later among the works it cites.
A System Level Approach to Controller Synthesis
Original
Y.-S. Wang, N. Matni, and J. C. Doyle · 2016
Later among the works it cites.
Thompson Sampling for Linear-Quadratic Control Problems
M. Abeille and A. Lazaric · 2017
Closest in time.
Structured State Space Realizations for SLS Distributed Controllers
J. Anderson and N. Matni · 2017
Closest in time.
Predictive Control for Linear and Hybrid Systems
F. Borrelli, A. Bemporad, and M. Morari · 2017
Closest in time.
Learning Linear Dynamical Systems via Spectral Filtering
E. Hazan, K. Singh, and C. Zhang · 2017
Closest in time.
Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire · 2017
Closest in time.
Occupy the Cloud: Distributed Computing for the 99%
E. Jonas, Q. Pu, S. Venkataraman, I. Stoica, and B. Recht · 2017
Closest in time.
Generalization bounds for non-stationary mixing processes
V. Kuznetsov and M. Mohri · 2017
Closest in time.
Scalable system level synthesis for virtually localizable systems
N. Matni, Y.-S. Wang, and J. Anderson · 2017
Closest in time.
Nonparametric Risk Bounds for Time-Series Forecasting
D. J. McDonald, C. R. Shalizi, and M. Schervish · 2017
Closest in time.
Control of Unknown Linear Systems with Thompson Sampling
Y. Ouyang, M. Gagrani, and R. Jain · 2017
Closest in time.
Stability Analysis of Discrete-Time Infinite-Horizon Optimal Control With Discounted Cost
R. Postoyan, L. Buşoniu, D. Nešić, and J. Daafouz · 2017
Closest in time.
A Tutorial on Thompson Sampling
Original
D. Russo, B. V. Roy, A. Kazerouni, and I. Osband · 2017
Closest in time.
Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
Original
S. Tu, R. Boczar, A. Packard, and B. Recht · 2017
Closest in time.
Improved Regret Bounds for Thompson Sampling in Linear Quadratic Control Problems
M. Abeille and A. Lazaric · 2018
Closest in time.
Safely Learning to Control the Constrained Linear Quadratic Regulator
Original
S. Dean, S. Tu, N. Matni, and B. Recht · 2018
Closest in time.
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
M. Fazel, R. Ge, S. M. Kakade, and M. Mesbahi · 2018
Closest in time.
Spectral Filtering for General Linear Dynamical Systems
Original
E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang · 2018
Closest in time.
Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht · 2018
Closest in time.
High-dimensional Statistics: A Non-Asymptotic Viewpoint
M. J. Wainwright · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…