Low-complexity Learning of Linear Quadratic Regulators from Noisy Data

Claudio De Persis; Pietro Tesi

Source-linked AI summary

Low-complexity Learning of Linear Quadratic Regulators from Noisy Data

Claudio De Persis, Pietro Tesi

arXiv:2005.01082v1May 3, 2020eess.SY

TL;DR

The paper addresses how to compute infinite-horizon LQR controllers for linear systems with unknown dynamics from finite noisy data. It proposes a direct convex-programming method that avoids model identification and statistical noise assumptions, while providing stability and relative-error guarantees whose error scales with noise magnitude.

Problem
The paper studies finite-data LQR for linear time-invariant systems with unknown dynamics, where noisy measurements make non-asymptotic stability and performance guarantees difficult.
Method
The method directly designs an LQ controller from finitely many sufficiently exciting system-response samples using a convex semidefinite-program formulation, without estimating a model.
Results
The method returns a stabilizing controller with a quantitative relative-error bound that requires no assumptions on noise statistics and scales with the noise magnitude.
Takeaways & Limitations
The approach offers finite-sample, model-free LQR design with stability and performance guarantees while using parsimonious assumptions about noisy data.
Takeaways & Limitations
The alternative robust formulation trades a higher chance of robust stabilization for a coarser H2-norm bound, and its analogous quantitative error guarantee is not established.

Abstract

from arXiv · show

This paper considers the Linear Quadratic Regulator problem for linear systems with unknown dynamics, a central problem in data-driven control and reinforcement learning. We propose a method that uses data to directly return a controller without estimating a model of the system. Sufficient conditions are given under which this method returns a stabilizing controller with guaranteed relative error when the data used to design the controller are affected by noise. This method has low complexity as it only requires a finite number of samples of the system response to a sufficiently exciting input, and can be efficiently implemented as a semi-definite program. Further, the method does not require assumptions on the noise statistics, and the relative error nicely scales with the noise magnitude.

1 Introduction

The paper situates finite-data LQR within data-driven control, where unknown dynamics require controllers to be designed from data, and emphasizes the difficulty of obtaining non-asymptotic guarantees with noisy measurements.

Data-driven control: Data-driven control designs a controller from data when system dynamics are unknown, either through model identification or directly without identification.The latter approach is called direct or model-free control, while the former is indirect control.
The LQR problem: Finite-data LQR is studied as a central example of data-driven control because the controller must be computed from noisy system data.The problem concerns the infinite-horizon LQR for linear time-invariant systems.
Finite-data guarantees: Non-asymptotic methods seek stability and performance guarantees from only finitely many data points, rather than convergence solely as time tends to infinity.This motivates finite-sample analysis for data-driven control methods.
Prior approaches: Adaptive control and policy-iteration methods historically analyze convergence of an adaptive law to the optimal controller as time goes to infinity.The introduction contrasts these asymptotic approaches with later efforts on finite-data guarantees.
Finite-data guarantees: Deriving non-asymptotic guarantees becomes very difficult when the data are noisy.Many noisy-data approaches are indirect: they estimate a model with error bounds and then design or update the controller.

Our contribution

The paper proposes a direct, low-complexity approach for designing LQ controllers from noisy data, with stability and relative-error guarantees that do not require statistical noise models.

Contribution: The proposed method designs LQ controllers directly from noisy data and provides guaranteed performance.It builds on the framework introduced by De Persis and Tesi (2020).
Low complexity: The method uses a finite, pre-computable number of data points and can be implemented as a convex program.Data may come from a single or multiple system trajectories.
Guarantees: Under suitable inequalities on the noise, the method returns a stabilizing controller with a quantitative relative-error guarantee.The relative error measures the gap between the computed solution and the unknown optimal controller.
Noise assumptions: The error guarantee scales with the noise magnitude, without assumptions that the noise is white or a martingale.This avoids requiring a statistical noise model.
Motivation: The direct approach uses few prior assumptions and can handle data whose noise lacks convenient statistical structure.The paper notes that experimental data may exhibit correlation and dependence.

Outline of the paper

The paper develops a data-based convex formulation of LQR, establishes noisy-data stability and error results, studies more noise-tolerant variants, and evaluates practical extensions and simulations.

Foundations: A trajectory generated by a persistently exciting input is used as a data-based non-parametric model of the system.This result underpins the proposed model-free method.
Data-based formulation: The LQR problem is formulated as an H2 problem and solved from data through convex programming in the noise-free case.The noise-free result is stated as Theorem 1.
Main results: For noisy data, the paper derives stability properties and error bounds for a baseline solution, followed by two variants with greater noise tolerance.The variants may provide reduced performance bounds.
Extensions and evaluation: Later sections discuss practical aspects, nonlinear systems, denoising strategies, numerical simulations, and concluding remarks.The numerical evaluation appears in Section 7.1.

2 Notation and auxiliary facts

This section introduces finite-horizon signal notation and the data conditions that let persistently exciting input trajectories encode the system dynamics.

Signal notation: For a signal z, the notation z[k,r] denotes the finite sequence from z(k) through z(r).The paper uses this notation for experimentally collected data sequences.
Signal notation: Experiments are assumed to have length T, allowing Zi to be written without the second horizon index.This is a shorthand used throughout the paper.
System and data: The system is linear time-invariant, with state x and control input u, and the available data are T-long input-state sequences.The data consist of u[0,T−1] and x[0,T−1].
Data-based representation: Condition (2) means every T-long input-state trajectory can be represented by columns of W0, so W0 encodes the system dynamics.This provides the data-based representation used by the method.
Persistent excitation: If the system is controllable and the input is persistently exciting of order n+1, condition (2) is guaranteed.Persistent excitation is defined through the associated data matrix.

3 Problem definition and data-driven formulation

The section formulates the LQR as an H2-norm minimization and shows how, under a data-excitation condition, the optimal controller can be obtained directly from data through an SDP without identifying A and B.

3.1 The Linear Quadratic Regulator problem: The LQR designs a state-feedback controller that makes A + BK Hurwitz while minimizing the closed-loop transfer function's H2 norm from disturbance d to performance output z.This H2 objective also corresponds to the impulse-response 2-norm and the classic stochastic LQR formulation under white unit-covariance disturbances.
3.1 The Linear Quadratic Regulator problem: The problem seeks Kopt from finite noisy input-state data when a system model is unavailable, comparing the data-driven solution with the model-based optimum.The system is linear time-invariant, controllable, and uses positive-semidefinite state and positive-definite input weighting matrices.
3.2 A data-driven SDP formulation: Under the data-excitation condition, the LQR optimum is equivalently represented by a semidefinite program whose feasible variables encode stability and the H2 performance bound.The SDP constraints include a Lyapunov inequality, P ⪰ I, a controller-cost inequality, and trace(P) + trace(L) ≤ γ.
3.2 A data-driven SDP formulation: The noise-free formulation is a data-based counterpart of an established continuous-time SDP formulation and extends an earlier data-driven result that assumed D0 = 0.The formulation may have infinitely many optimal Q variables differing by matrices in the right kernel of W0, while producing the same controller.
3.2 A data-driven SDP formulation: The data-driven formulation replaces the unknown feedback interconnection A + BK with expressions involving the measured matrices D0, U0, X0, and X1.Under the excitation condition, the controller can be parametrized directly by these data matrices, and the resulting formulation only depends on data.
3.2 A data-driven SDP formulation: Every optimal SDP solution returns the unique optimal controller Kopt, so the data-driven formulation recovers the model-based LQR optimum in the noise-free case.The proof compares the SDP objective with the H2 optimum and uses uniqueness of the H2-minimizing controller.
3.2 A data-driven SDP formulation: Any feasible SDP solution yields a stabilizing controller K = U0QP^−1, while every stabilizing controller can be represented by a feasible tuple under the same condition.These two directions establish equivalence between feasible data-based variables and stabilizing state-feedback controllers.

4 Data-driven solution with noisy data

The noisy-data method omits the unmeasured disturbance term and analyzes when the resulting SDP is feasible, stabilizing, and close to the optimal controller. Under separate sufficient conditions, the performance error is quantitatively controlled without assumptions on noise statistics.

4 Data-driven solution with noisy data: When D0 is nonzero and unmeasured, the proposed data-only variant disregards the noise term and computes K = U0QP^−1 if the resulting SDP is feasible.The analysis asks whether a solution exists, whether its controller stabilizes the system, and how its performance compares with Kopt.
4 Data-driven solution with noisy data: A feasible noisy-data solution is not automatically guaranteed to exist, stabilize the system, or achieve performance close to Kopt.The method therefore separates feasibility, stability, and performance-gap questions.
4.1 Stability and performance analysis: A chain of inequalities parameterized by η1 and η2 compares the noisy-data objective and controller performance with their optimal noise-free counterparts.The first inequality controls the noisy-data solution relative to a feasible noise-free tuple, while the second relates a scaled optimal tuple to the noisy problem.
4.1 Stability and performance analysis: If conditions (2), (18), and (20) hold, the noisy-data problem is feasible and its controller has a quantitative relative error with respect to Kopt.Theorem 2 states the result for data generated with a possibly nonzero disturbance vector D0.
4.1 Stability and performance analysis: The relative-error bound requires no prior assumptions on noise statistics and scales with η1 and η2, converging to zero as D0 tends to zero.As D0 goes to zero, both η1 and η2 converge to one.
4.1 Stability and performance analysis: Condition (18) ensures that any optimal solution of the noisy-data problem produces a stabilizing controller.The condition can be checked from data when prior information about the disturbance bound d is available, whereas the additional performance condition depends on the unknown Kopt.

5 Noise robustness through soft constraints

The paper improves noise robustness by adding soft constraints that limit the controller-related matrix M, yielding data-driven stabilizing controllers with performance guarantees under suitable conditions.

Motivation: Small noise can produce non-stabilizing controllers when condition (18) is difficult to satisfy, motivating a constraint on M.The proposed modification targets M = QP −1Q⊤.
Soft-constrained formulation: The modified optimization penalizes M through a matrix V and a trace constraint, while preserving the baseline formulation's logical structure.The constraint V − QP −1Q⊤ ⪰ 0 bounds M, and trace(V) is minimized through the objective.
Guarantees: With conditions (2) and (20) also satisfied, problem (23) is feasible and its controller admits a quantitative performance bound relative to Kopt.Condition (20) cannot be checked from data because it depends on the unknown optimal controller.
Guarantees: Under condition (18), any optimal solution of problem (23) returns a controller that stabilizes the system.This stability guarantee is established by the theorem following the auxiliary lemmas.
Trade-off: The robust formulation adds an extra term η3 to the error bound, although the resulting conservatism can remain moderate.The paper compares this degradation with noise-robust indirect methods.
Alternative robust formulation: An alternative S-procedure formulation incorporates η1 directly into design, trading increased noise robustness for a coarser H2-norm bound and no currently established analogous error guarantee.Its implementation remains an SDP, obtainable through a line search on η1.

6 Stability and performance verification, nonlinear systems and de-noising

The paper explains how stability and performance conditions can be checked from data, extends the analysis to nonlinear systems near equilibria, and describes ensemble averaging for noise reduction.

Verification from data: The method requires prior assumptions about noise quality but does not require noise statistics.A known bound on disturbance magnitude can support data-checkable conditions for stability and H2-norm guarantees.
Verification from data: Larger assumed disturbance bounds increase the chance that the noise assumption holds but reduce the chance that the sufficient data conditions hold.The same prior-versus-conservativeness trade-off applies to both stability formulations.
Verification from data: Sufficiently rich data are needed for relative-error guarantees, whereas a stabilizing controller can generally be found without condition (2).In noisy experiments, condition (2) remains data-checkable and continues to hold when disturbance magnitude is sufficiently small.
Performance bounds: The relative-error condition is easier to satisfy than the corresponding stability condition, so the robust solution need not add much conservatism over the baseline.For the special optimal solution, increasing the norm of W0 drives Vo toward zero and reduces the added conservatism.
Nonlinear systems: Around a known equilibrium, the nonlinear dynamics equal their first-order approximation plus a higher-order disturbance, allowing Theorem 3 to carry over when the linearization is stabilizable.The resulting controller exponentially stabilizes the original nonlinear equilibrium under the stated conditions.
De-noising: Averaging N noisy trajectory ensembles reduces noise variance by a factor of N while preserving a valid input-output trajectory for applying the preceding results.The ensembles may come from one trajectory split into cycles or from multiple trajectories.

7 Monte Carlo simulations

Monte Carlo experiments evaluate the proposed methods on random linear systems and an inverted pendulum under several noise conditions. Performance is generally strong at moderate noise, while robustness depends on trajectory length, repeated experiments, and added robustness weighting.

Random linear systems: 100 random linear systems were tested with white Gaussian, constant-bias, and sinusoidal disturbances across multiple noise levels.Both methods were evaluated using the same systems and inputs for each noise type and level.
Random linear systems: Both methods perform well for SNR ≥25dB and often at 10–20dB, but performance drops for SNR ≤5dB.Method (23) has lower relative error but is slightly less robust; at SNR ≤−5dB both methods settle to S = 76%.
Random linear systems: N = 10 repeated experiments achieve S = 96% with M = 0.0034 for σ = 0.1 and S = 90% with M = 0.0296 for σ = 0.5.Averaging trajectories improves robustness without the performance loss associated with increasing the trace(V) penalty.
Random linear systems: For the Laplacian system, N = 10 trajectories of length T = 20 achieve S = 100% with M = 0.6569 over 100 experiments.Further reducing the median relative error requires increasing T and N.
Nonlinear inverted pendulum: For the inverted pendulum, ξ = 0 yields S = 100% with M = 0.0356, while WGN with σ = 1 reduces S to 12%.Reducing T or adding α > 1 to trace(V) can improve stabilization robustness at the expense of performance.

8 Concluding remarks

The paper addresses noisy-data LQR design through convex semidefinite formulations that explicitly favor noise-robust solutions. The methods provide finite-sample stability guarantees without requiring white-noise assumptions, while safety-constrained extensions remain an open direction.

Concluding remarks: The paper proposes two convex SDP methods that incorporate noise through an augmented cost function favoring noise-robust LQR solutions.Both methods provide finite-sample stability guarantees.
Concluding remarks: The methods do not require specific noise models such as white noise.This conclusion follows from the paper’s finite-sample, noise-robust formulation.
Concluding remarks: Extending the approach to state and input safety constraints is identified as a major remaining challenge.The authors describe set-invariance control as the direction being pursued for this extension.

A Appendix

The appendix establishes data-based links between feasible SDP variables, stabilizing controllers, and closed-loop controllability Gramians. It also connects the resulting matrix inequalities to stability and H2-related performance quantities.

Data-based controller construction: For a feasible tuple, P = X0Q and K = U0QP^−1 connect the data matrices to the controller returned by the SDP.These identities are used to express the closed-loop dynamics in terms of measured data.
Stability guarantee: The first SDP constraint is equivalent to a matrix inequality S ⪯ 0, and the proof concludes that K is stabilizing.The argument associates P with a controllability Gramian of an extended closed-loop system.
Feasibility and performance: The extended-system transfer function yields an H2-related bound through trace(P) and trace(L).The appendix uses Te(K) = [T(K) TΞ(K)] to relate the norm to these trace terms.
Feasibility and performance: For any stabilizing controller, the appendix constructs feasible variables Q, L, and γ from its controllability Gramian P.It sets Q = G∗P, L = U0QP^−1Q⊤U0⊤, and γ = trace(P) + trace(L).