On the Sample Complexity of the Linear Quadratic Regulator

Abstract

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. We provide end-to-end bounds on the relative error in control cost that are nearly 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.

Contains a new analysis of finite-dimensional truncation, a new data-dependent estimation bound, and an expanded exposition on necessary background in control theory and System Level Synthesis

References in corpus (9)

• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
• Occupy the Cloud: Distributed Computing for the 99%
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• A Tutorial on Thompson Sampling
• Learning-based Control of Unknown Linear Systems with Thompson Sampling
• Thompson Sampling for Linear-Quadratic Control Problems
• Spectral Filtering for General Linear Dynamical Systems

Cited by in corpus (44)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Simple random search provides a competitive approach to reinforcement learning
• Model-Based Value Estimation for Efficient Model-Free Reinforcement Learning
• Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees
• Learning the Globally Optimal Distributed LQ Regulator
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• Naive Exploration is Optimal for Online LQR
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• System-level, Input-output and New Parameterizations of Stabilizing Controllers, and Their Numerical Computation
• Online Linear Quadratic Control
• Online Data Poisoning Attack
• Spectral Filtering for General Linear Dynamical Systems
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• Approximate Robust Control of Uncertain Dynamical Systems
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• From self-tuning regulators to reinforcement learning and back again
• Verification of Neural Network Control Policy Under Persistent Adversarial Perturbation
• The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint
• Robust-Adaptive Control of Linear Systems: beyond Quadratic Costs
• Sample Complexity of Sparse System Identification Problem
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• Efficient Learning of Distributed Linear-Quadratic Controllers
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator
• No-Regret Prediction in Marginally Stable Systems
• Sample Complexity of Kalman Filtering for Unknown Systems
• Policy Learning of MDPs with Mixed Continuous/Discrete Variables: A Case Study on Model-Free Control of Markovian Jump Systems
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems
• Robust guarantees for learning an autoregressive filter
• Task-Optimal Exploration in Linear Dynamical Systems
• Global Convergence Using Policy Gradient Methods for Model-free Markovian Jump Linear Quadratic Control
• System Level Synthesis
• Sparsity Preserving Discretization With Error Bounds
• Robust Spectral Filtering and Anomaly Detection
• System Identification via Meta-Learning in Linear Time-Varying Environments
• Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
• Continuous Control with Contexts, Provably
• Linear System Identification Under Multiplicative Noise from Multiple Trajectory Data
• Alice's Adventures in the Markovian World
• Linear Dynamics: Clustering without identification
• Closed-loop Parameter Identification of Linear Dynamical Systems through the Lens of Feedback Channel Coding Theory