PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Sample Complexity of the Linear Quadratic Regulator

Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, Stephen Tu

arXiv:1710.01688v3math.OCcs.LGstat.ML

TL;DR

The paper asks how to control an LQR system when its dynamics are unknown and data come from experiments. Coarse-ID control estimates a model and its uncertainty, then uses robust System Level Synthesis for controller design. It proves small relative cost and stability guarantees for sufficient observations, and experiments show stabilization where uncertainty-ignoring schemes can fail.

  • Problem

    The paper studies what control cost is achievable for LQR with unknown dynamics and addresses the difficulty that nominal model-based synthesis can fail to stabilize the true system.

  • Method

    Coarse-ID control estimates a nominal dynamical model, constructs probabilistic error bounds, and solves a robust controller-design problem using System Level Synthesis.

  • Results

    For sufficient observations, the approach guarantees small relative LQR cost and asymptotic closed-loop stability, while simulations find stabilizing controllers where nominal synthesis can be unstable.

  • Takeaways & Limitations

    Accounting for model uncertainty during synthesis provides an end-to-end route to robustly stabilizing unknown linear systems and extends beyond LQR to other response norms.

  • Takeaways & Limitations

    The stated estimation guarantees require independent samples, whereas practical rollouts contain dependent measurements and are not covered by those guarantees.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies LQR with unknown linear dynamics and proposes Coarse-ID control, which couples model estimation, uncertainty quantification, and robust controller synthesis. It provides stability and cost guarantees, while experiments show uncertainty-aware synthesis can stabilize systems where nominal synthesis fails.

  • Motivation: The method addresses the failure of nominal identify-then-control schemes, which can fail to find a stabilizing controller despite sufficient data.The paper emphasizes that uncertainty in estimated dynamics must be incorporated into control synthesis.
  • Coarse-ID framework: Coarse-ID control learns a nominal model, estimates its distance from the true dynamics, and solves a robust controller-design problem.The procedure uses supervised learning, bootstrap or prior-based uncertainty bounds, and robust optimization over controllers.
  • Analysis and synthesis: The analysis combines non-asymptotic random-matrix tools for estimation with System Level Synthesis, which enables robust control design through a convex formulation.SLS lifts the system description so robust stability and performance can be analyzed in terms of admissible perturbations.
  • Guarantees: For sufficient observations, the approach guarantees a control policy with small relative LQR cost and asymptotic closed-loop stability.The paper also gives an end-to-end relative-cost bound for robust SLS controllers.
  • Empirical result: In simulation, Coarse-ID finds a stabilizing controller with few observations, whereas nominal synthesis frequently produces unstable closed-loop behavior.The comparison targets settings where the nominal system is used without accounting for model uncertainty.
  • Problem setting: Unknown-dynamics LQR asks what infinite-horizon control cost is achievable from experimentally collected system data.The setting assumes linear dynamics, measured responses to chosen inputs, and repeated independent experiments.

2 System Identification through Least-Squares

The paper estimates unknown linear dynamics using least squares, then derives theoretical and data-dependent uncertainty guarantees. Its analysis relies on independent samples, random-matrix tools, and bootstrap estimation, while noting limitations for dependent rollout data.

  • Estimation procedure: The identification procedure collects Gaussian-input rollouts and estimates the linear dynamics from observed states and inputs using least squares.The estimator is constructed from rollout data, with a modified version using one final sample per rollout to obtain independent rows.
  • Estimation procedure: The analysis replaces the dependent full-rollout estimator with a single-sample-per-rollout estimator whose data rows are independent.This modification makes the estimation error amenable to random-design regression analysis.
  • Theoretical analysis: Random-matrix results bound the estimation error by combining Gaussian matrix-product and minimum-singular-value inequalities with random-design regression analysis.The proof applies these lemmas to the least-squares error for the estimated dynamics.
  • Theoretical analysis: The theoretical guarantee has an apparently optimal dependence on the number of parameters: O(n + p) measurements, each providing n values, for n(n + p) parameters.The bound also reflects system-dependent estimation difficulty, including how system excitability affects estimation of A but not B.
  • Uncertainty estimation: The paper supplements data-independent bounds with data-dependent confidence sets and a vanilla bootstrap for estimating bounds on the errors in A and B.The bootstrap targets probabilities of the form P(∥A − bA∥2 ≤ bϵA) ≈ 1 − δ and P(∥B − bB∥2 ≤ bϵB) ≈ 1 − δ.
  • Limitations: The theoretical guarantees require independent samples, so they do not directly apply when all measurements from ordinary rollouts are used because those measurements are dependent.The paper therefore studies a different procedure for estimating error size in that practical setting; dependent-data guarantees are described as follow-up work.

3 Robust Synthesis

This section formulates robust LQR synthesis through System Level Synthesis, representing closed-loop behavior with system responses and optimizing against model uncertainty. Stability follows from norm-based robustness conditions, while the resulting controller can be obtained through convex optimization.

  • System Level Synthesis: System Level Synthesis represents closed-loop state and control responses as transfer functions constrained by affine system-response equations.These constraints are necessary and sufficient, and make optimization affine in the response elements rather than non-convex in the controller.
  • System Level Synthesis: The controller recovered from feasible responses is K = ΦuΦx^-1 and internally stabilizes the system when the responses satisfy the SLS constraints.The parameterization covers all achievable stable responses under internally stabilizing state-feedback controllers.
  • Robust synthesis: Robust SLS incorporates estimated transition-matrix errors by optimizing nominal LQR performance while penalizing worst-case uncertainty.The uncertainty is represented through perturbations ∆A and ∆B around estimated dynamics.
  • Robust synthesis: A controller stabilizes the true system when the induced uncertainty satisfies a small-gain condition, including ∥ˆ∆∥H∞ < 1 and Hα(Φx, Φu) < 1.These conditions provide sufficient robustness guarantees for controllers synthesized from estimated dynamics.
  • Robust synthesis: The robust LQR formulation is computationally intractable under real-parametric uncertainty, motivating tractable convex formulations and their performance bounds.The paper frames robust synthesis as an equivalent worst-case optimization problem over uncertainty.

4 Sub-optimality Guarantees

This section bounds the sub-optimality of robust SLS controllers under transition-matrix estimation errors and connects those bounds to independent-data sample complexity. The complexity term reflects both controllability and closed-loop difficulty.

  • Infinite-horizon guarantees: Theorem 4.1 bounds the relative LQR-cost error of the robustly synthesized controller using operator-norm bounds ϵA and ϵB on transition-matrix errors.The result assumes synthesis through optimization (3.18) with α = 1/2.
  • End-to-end guarantees: The guarantee applies to any estimation procedure, while combining it with independent-data identification yields an end-to-end sample-complexity bound.The identification result holds with probability 1 − δ when N ≥ 8(n + p) + 16 log(4/δ), subject to the stated robustness condition.
  • Infinite-horizon guarantees: The estimation-error condition requires (ϵA + ϵB∥K⋆∥2)∥RA+BK⋆∥H∞ < 1/5 for the sub-optimality theorem to apply.This combines model uncertainty, optimal control magnitude, and closed-loop sensitivity.
  • Complexity term: CLQR decreases with the minimum eigenvalue of the input-and-noise controllability Gramians and increases with ∥K⋆∥2 and ∥RA+BK⋆∥H∞.The bound therefore reflects how readily the system is excited, how large optimal actions are, and how sensitive the closed loop is.
  • Scope of guarantees: The bounds remain valid under additional controller constraints, including restriction to static controllers, relative to the best constrained controller with true dynamics.This preserves the guarantee’s scope while changing the comparator from unrestricted optimal LQR cost.

5 Computation

This section develops polynomial-time approximations to the semi-infinite robust synthesis problem. FIR truncation yields exponentially decaying approximation error, while a common-Lyapunov relaxation provides a simpler static-controller SDP.

  • Computational formulations: The main robust optimization is semi-infinite and lacks a known efficient solution, so the paper introduces polynomial-time upper-bounding formulations.The alternatives target computational tractability rather than exact solution of the original formulation.
  • FIR approximation: FIR approximation restricts the response transfer functions to their first L elements, replacing the infinite-horizon search with finitely many variables.The truncation is justified because the response maps are stable.
  • FIR approximation: The truncated formulation expresses the H2 objective as a second-order cone constraint and the H∞ constraint as a semidefinite program.The chosen linear-matrix-inequality formulation exploits the FIR structure.
  • FIR approximation: FIR truncation causes only a small performance degradation relative to the infinite-horizon solution, with degradation decaying exponentially in horizon L.The decay rate is determined by the spectral decay of the optimal closed-loop response.
  • Static-controller relaxation: A common-Lyapunov relaxation provides a simpler semidefinite-program formulation for static controllers, extracting K = ZX^-1 from its solution.The compact SDP is simpler than the truncated FIR approximation, though the text notes a performance cost for this simplification.

6 Numerical Experiments

The experiments evaluate Coarse-ID identification and robust controller synthesis on a marginally unstable graph Laplacian system, comparing uncertainty-aware controllers with nominal and computationally simplified alternatives.

  • Experimental setup: The example is a marginally unstable graph Laplacian system with B = I, Q = 10^-3I, and R = I.Adjacent nodes are weakly connected, each node receives direct input, and input size is penalized relatively more than state.
  • Estimation: With rollout length T = 6, increasing the number of rollouts decreases least-squares estimation errors, while bootstrap estimates become comparable in magnitude to true errors for large N.The bootstrap uses M = 2,000 trials and confidence parameter δ = 0.05.
  • Controller synthesis: Robust synthesis compares FIR and common Lyapunov controllers against nominal LQR controllers using either true or bootstrap-estimated model errors.The FIR filters have length L = 32, and the common Lyapunov method is a static synthesis relaxation.
  • Controller synthesis: The common Lyapunov controller performs slightly worse than the more complex FIR controller, while conservative bootstrap errors cause only modest additional degradation.Both robust synthesis procedures still achieve reasonable control performance.
  • Stability and performance: Nominal controllers often outperform robust controllers when stabilizing, but stabilize only roughly 80 of 100 instances after N = 60 rollouts.Robust synthesis reports infeasibility when uncertainties are too high, whereas nominal instability provides no default user warning.
  • Complexity trade-offs: For smaller rollout counts, increasing FIR complexity provides negligible benefit in actual cost and upper bounds, while static controllers achieve costs of similar magnitude.Figure 3 examines the performance-complexity trade-off using true errors.

7 Conclusions and Future Work

The paper positions Coarse-ID control as a bridge between nonasymptotic system identification and robust control, then identifies extensions and limitations involving analysis, conservatism, task-aware estimation, and broader control settings.

  • Conclusions: Coarse-ID control merges nonasymptotic system identification with System Level Synthesis for robust control.The paper describes this as a foundation for combining these approaches in unknown-dynamics LQR.
  • Future work: The framework is proposed for extension to other norms, adaptive control, nonlinear control, and Model Predictive Control.The paper specifically discusses task-directed data collection, optimistic exploration, iterative LQR, and MPC.
  • Improving the end-to-end analysis: The analysis is data inefficient because the estimator uses only each rollout’s final time step, although empirically accuracy improves when all data are included.Analyzing the full least-squares estimator is difficult because its design matrix depends strongly on the data being estimated.
  • Improving the end-to-end analysis: The uncertainty characterization uses only contraction properties, leaving stronger bounds that exploit linearity and time-invariance as a route to less conservative control schemes.Integral Quadratic Constraints are identified as one possible source of tighter bounds.
  • Improving the end-to-end analysis: The performance loss from the common Lyapunov relaxation remains insufficiently understood, despite experiments suggesting good performance and limited conservatism.Experiments also suggest that optimizing nominal cost under robust stability constraints performs better than directly optimizing the SLS upper bound.
  • Lower bounds: The paper provides worst-case upper bounds but no lower bounds for unknown-model control, leaving achievable performance with limited system knowledge unresolved.Such lower bounds would benchmark performance without priors on the linear dynamics.
  • Future work: A central open problem is making identification depend on the desired control task rather than keeping estimation and control completely decoupled.Task-informed identification may improve sample complexity.

A Proof of Lemma 2.1

The proof bounds a random matrix’s spectral norm by discretizing the unit spheres with ε-nets, controlling finitely many bilinear forms, and applying a union bound.

  • Concentration step: The proof begins with Bernstein’s lemma for independent zero-mean sub-exponential random variables under an Orlicz norm bound.The concentration statement holds with probability at least 1 − δ when the sample count meets the logarithmic condition.
  • ε-net reduction: An ε-net is constructed for each unit sphere, and arbitrary unit vectors are approximated by net points.The proof uses separate nets for the m- and n-dimensional ℓ2 balls.
  • ε-net reduction: The spectral norm is bounded by the largest net-point bilinear form after accounting for approximation error.The displayed inequality introduces the factor 1/(1 − 2ε).
  • Covering numbers: Setting ε = 1/4 yields covering-number bounds Mε ≤ 9^m and Nε ≤ 9^n via volume comparison.These bounds control the number of net-point pairs in the subsequent union bound.
  • Union bound: Each net-point bilinear form is treated as a zero-mean sub-exponential random variable, enabling a per-pair tail bound.The proof then controls all pairs simultaneously by a union bound.

B Proof of Proposition 2.4

The proof of Proposition 2.4 analyzes the least-squares error through a Gaussian noise matrix and the singular value decomposition of the design matrix.

  • Gaussian matrix bound: The proof invokes a standard Gaussian random-matrix lemma for an N × n matrix with independent N(0, σ_w^2) entries.This lemma supplies the needed spectral control for the transformed noise matrix.
  • Least-squares error: The design matrix Z contains the experiment regressors, while W collects the disturbance vectors as columns.The ordinary least-squares error matrix is expressed using these matrices.
  • Singular-value analysis: When Z has rank n + p and N ≥ n + p, its singular value decomposition Z = UΛV^⊤ is used with invertible Λ.The decomposition isolates the geometry of the design matrix in the least-squares analysis.
  • Gaussian matrix bound: Because U has orthonormal columns, U^⊤W retains independent Gaussian entries, so the Gaussian matrix lemma applies.This transfers the random-matrix bound to the transformed least-squares noise term.

C Derivation of the LQR cost as an H2 norm

The section recasts infinite-horizon LQR as an equivalent H2 optimal-control problem using system response variables. Stable achievable responses describe the closed-loop mapping from disturbances to states and controls.

  • Infinite-horizon LQR is recast as an equivalent H2 optimal-control problem using system response variables.
  • Stable achievable responses (Φx, Φu) describe the closed-loop map from disturbance w to state x and control u.
  • The controller is represented as K = ΦuΦx^-1 through the system responses.
  • Parseval’s Theorem supplies the frequency-domain step used in the cost derivation.

D Proof of Theorem 5.1

The proof shows that sufficiently small identification errors preserve stability and make the robust synthesis problem feasible. It then relates the resulting FIR controller’s performance to the optimal controller through truncated system responses.

  • Stability under identification error: If the optimal closed loop decays as C⋆ρ⋆^t, then sufficiently small perturbations preserve comparable stability for the estimated system.The perturbation is bounded by ϵA + ϵB∥K⋆∥2 ≤ 1−ρ⋆.
  • Robust synthesis feasibility: The uncertainty scale ζ combines identification error, optimal control magnitude, and the optimal closed-loop H∞ sensitivity.It is defined as ζ = (ϵA + ϵB∥K⋆∥2)∥RA+BK⋆∥H∞.
  • Robust synthesis feasibility: The robust optimization is feasible when ϵA + ϵB∥K⋆∥2 ≤ 1−ρ⋆, using truncated responses of K⋆ as a feasible construction.The construction uses eΦx and eΦu truncated to L steps and a residual term eV.
  • Performance comparison: The estimated-system response is controlled by a factor 1/(1−ζ) relative to the true-system response.
  • Performance comparison: The FIR approximate controller is analyzed on the true system by combining robust optimization, response truncation, and system-response performance bounds.
  • Theorem conclusion: When ζ ≤ 1/10, the proof reaches the stated conclusion of Theorem 5.1.

E A Common Lyapunov Relaxation for Proportional Control

The common Lyapunov relaxation converts robust proportional-control constraints into a tractable semidefinite program. It identifies the state covariance with the Lyapunov variable and uses Z = KX to recover convexity.

  • Robust constraints: The H∞ constraint is expressed as a linear matrix inequality through the KYP Lemma.
  • H2 cost: Under proportional control, the average cost is Trace((Q + K∗RK)X2), where X2 satisfies a Lyapunov equation for the estimated closed loop.
  • H2 cost: Relaxing the Lyapunov equation to a matrix inequality preserves an upper bound on the squared H2 norm.
  • Common Lyapunov relaxation: The common Lyapunov relaxation imposes X2 = X∞, making the first LMI redundant and leaving a semidefinite program.
  • Convexification: The substitution Z = KX transforms the apparently nonconvex formulation into the convex formulation used for the cost.

F Numerical Bootstrap Validation

The numerical study evaluates whether bootstrap uncertainty estimates track actual model errors and whether the resulting uncertainty regions contain the true dynamics. The bootstrap bounds approximate the true errors far more closely than the theoretical bounds.

  • Bootstrap validation: The study evaluates bootstrap error estimates because theoretical bounds are valid but can be highly conservative for dependent data.
  • Simulation setup: The simulations generate upper-triangular A matrices with spectral radius ρ and clipped Gaussian B entries, using fixed process-noise variance.
  • Bootstrap validation: The validation estimates how often the true A and B lie inside bootstrap spectral-norm balls centered at their estimates.
  • Results: The bootstrap bounds offer a good approximation to the true ϵA and ϵB, whereas the theoretical bounds would be orders of magnitude larger.
  • Figure 5: Figure 5 compares spectral distances with bootstrap estimates and reports empirical containment probabilities for A and B over 2000 trials.

G Experiments with Varying Rollout Lengths

With six rollouts fixed, longer rollout lengths reduce identification errors and improve the observed stabilizing performance of synthesized controllers.

  • Estimation errors: The A-estimation errors decrease more quickly as rollout length increases.This is consistent with longer rollouts improving identification in easily excitable systems through a higher signal-to-noise ratio.
  • Bootstrap assessment: Figure 6 compares spectral distances to A and B with bootstrap estimates and reports containment probabilities estimated from 2000 trials.The simulations use n = 6, p = 2, ρ = 1.01, and M = 2000.
  • Controller performance: Longer rollouts yield somewhat better nominal stabilizing performance than the fixed-rollout-length setting.The improvement is likely related to the smaller errors in estimating A.
  • Estimation errors: With N = 6 rollouts, the median least-squares estimation error decreases as rollout length T increases.Figure 7 also reports the ratio of bootstrap estimates to true estimates, with shaded quartile regions.
  • Controller performance: Figure 8 compares nominal and robust-controller suboptimality and shows how often each synthesis method finds stabilizing controllers as rollout length varies.Quartile regions extend to infinity when stabilizing controllers are not frequently found.
Loading 1710.01688v3…