Source-linked AI summary
Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, Stephen Tu
TL;DR
The paper addresses adaptive LQR when the system dynamics are unknown and seeks efficient guarantees for stability, performance, and regret. It combines linear-system estimation with robust controller synthesis to produce a polynomial-time adaptive algorithm. The method achieves high-probability sub-linear regret, establishes regret–estimation lower bounds, and performs comparably to heuristic alternatives while extending to constrained demand forecasting.
Problem
Adaptive LQR requires controlling an unknown linear system under quadratic costs while obtaining non-asymptotic performance and regret guarantees.
Method
The method combines linear-system estimation, robust controller synthesis, and convex optimization to construct an adaptive control algorithm.
Results
The algorithm is polynomial time, guarantees high-probability sub-linear regret, and achieves e O(T^2/3) regret with parameter estimation at e O(T^-1/3) rate.
Takeaways & Limitations
The robust adaptive method provides stability, robust performance, parameter estimation, and comparable regret to heuristic OFU and TS methods, while extending to demand forecasting with safety constraints.
Takeaways & Limitations
The regret bounds’ dependence on 1/(1 −ρ⋆) is an artifact of the perturbation analysis and remains to be sharpened.
Abstract
from arXiv · showhide
We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the estimation of linear systems and in robust controller synthesis, we present the first provably polynomial time algorithm that provides high probability guarantees of sub-linear regret on this problem. We further study the interplay between regret minimization and parameter estimation by proving a lower bound on the expected regret in terms of the exploration schedule used by any algorithm. Finally, we conduct a numerical study comparing our robust adaptive algorithm to other methods from the adaptive LQR literature, and demonstrate the flexibility of our proposed method by extending it to a demand forecasting problem subject to state constraints.
1 Introduction
Adaptive LQR research seeks non-asymptotic stability, performance, and regret guarantees when controlling unknown linear systems. This paper develops a polynomial-time robust adaptive method, establishes regret–estimation limits, and evaluates it numerically.
- The adaptive LQR literature studies regret as performance deviation from optimality over time, alongside non-asymptotic stability and performance guarantees.
- Existing OFU methods can achieve e O(T) regret, but require non-convex optimization to e O(T^-1/2) precision without a provably efficient implementation.
- Prior TS results include e O(T^2/3) high-probability regret for scalar systems, but their proof does not extend to non-scalar systems.
- A restrictive prior TS analysis assumes a known compact parameter set with cross-system stabilizing controllers, whose construction and efficient verification are unavailable.
- The proposed algorithm provides polynomial-time high-probability sub-linear regret, stability and near-optimal performance, with semidefinite programs logarithmic in T.
- The method estimates parameters at e O(T^-1/3), while its expected regret is lower bounded by Ω(T^2/3), sharp up to logarithmic factors.
- Numerically, the algorithm has comparable regret to heuristic OFU and TS methods, lower true-system infinite-horizon cost, and extends to demand forecasting with safety constraints.
2 Problem Statement and Preliminaries
The paper formulates adaptive LQR for an unknown discrete-time linear system and uses System Level Synthesis to express control through closed-loop responses. Robustness conditions connect estimated-system designs to stability and performance on the true system.
- Problem Statement: The problem is to control a discrete-time linear system with unknown transition matrices while minimizing quadratic LQR costs and maintaining a stable closed loop.
- Problem Statement: With known system matrices, the optimal policy is static state feedback derived from a discrete algebraic Riccati equation.
- Robust Adaptive Control: Unlike OFU’s non-convex optimization, the proposed method uses convex optimization and robust control.
- System Level Synthesis: SLS represents controllers through state and input system responses constrained by affine dynamics, making linear-system control optimization affine in those response elements.
- System Level Synthesis: The controller corresponding to response functions is K = ΦuΦx^-1, and SLS permits this representation using transfer functions.
- Robustness: Using estimated matrices, SLS defines model mismatch through b∆ and characterizes the resulting true-system responses.
- Robustness: If the estimated-system controller is stabilizing and (I + b∆)^-1 is stable, the same controller stabilizes the true system.
- Robustness: The H2 norm measures white-noise energy transfer and enters the objective, while the H∞ norm measures robustness and enters stability and performance constraints.
3 Algorithm and Guarantees
The paper develops a robust adaptive LQR algorithm with high-probability sublinear regret, consistent parameter estimation, and polynomial-time implementation. Its analysis balances exploration and model uncertainty while establishing a matching lower bound connecting regret to estimation.
- Algorithm: The robust adaptive algorithm uses system estimation, robust controller synthesis, and coarse-ID control to provide stability and near-optimal performance throughout operation.Its controller synthesis can be expressed as a finite-dimensional semidefinite program.
- Algorithm: The algorithm assumes an initial controller K(0) that stabilizes the true system and uses exponentially growing epochs with epoch-specific least-squares estimates.The paper notes that offline methods can find such a controller and that recursive least squares is practical.
- Guarantees: With probability at least 1 −δ, the parameter estimate is consistent and converges in operator norm at rate e O(T −1/3).The consistency guarantee is identified as absent from the cited OFU and Thompson Sampling approaches.
- Guarantees: With probability at least 1 −δ, the algorithm achieves regret bounded by e O(T 2/3), with additional o(T 2/3) terms hidden in the notation.The proof balances exploration noise and model uncertainty using α = 1/3 across a logarithmic number of epochs.
- Lower Bounds: The expected regret is lower bounded by Ω(T 2/3), showing that the algorithm’s regret scaling is sharp up to logarithmic factors.The lower bound also characterizes regret required to achieve a specified parameter-estimation rate.
- Lower Bounds: For algorithms with O(T^α) regret, the lower-bound analysis suggests an estimation rate of O(T^−α/2), while achieving ε error likely requires Ω(ε^−2) regret.The latter statement is presented as a conjectured extension from independent linear regression to this setting.
4 Experiments
The experiments compare robust adaptive control with Thompson sampling, heuristic OFU, and nominal control on a marginally unstable Laplacian system. They also show how constrained robust synthesis moderates state behavior in a demand-forecasting extension.
- Regret Comparison: The comparison evaluates robust adaptive control, non-Bayesian Thompson sampling, heuristic projected-gradient OFU, and nominal control on the LQR problem in Eq. (4.1).The nominal baseline optimizes the estimated system and uses the robust method’s noise schedule.
- Regret Comparison: The benchmark is a marginally unstable Laplacian system with Q = 10I, R = I, and σw = 1, where input size is penalized less than state.The paper identifies marginal instability and the cost ratio as factors that may hurt optimistic methods.
- Regret Comparison: Across 500 instances, Figure 1 reports median and 90th percentile regret over time and median and 90th percentile infinite-horizon LQR cost for epoch controllers.A stabilizing noisy rollout of length T0 = 100 initializes all methods and is excluded from regret.
- Regret Comparison: The methods have very similar regret performance overall, while robust adaptive control performs relatively better on the infinite-horizon cost of epoch controllers.This indicates greater suitability for early stopping by playing the current controller indefinitely.
- State-Constrained Extension: In Figure 2, median and maximum ||x_t||∞ are compared over 500 trials for unconstrained and constrained synthesis; constrained synthesis produces more moderate trajectories.The caption describes the plots, while the text reports large states for unconstrained synthesis and moderate behavior after adding a constraint on Φx.
- State-Constrained Extension: The demand-forecasting extension models correlated stochastic disturbances as the output of an unknown autonomous LTI system and adds state constraints through robust synthesis.The setup represents environmental uncertainty and safety constraints.
5 Conclusions and Future Work
The paper presents a polynomial-time robust adaptive LQR algorithm with high-probability sub-linear regret, stability, robust performance, and parameter estimation guarantees. It also identifies open questions concerning optimal polynomial-time regret and practical extensions to safety constraints and nonlinear dynamics.
- A polynomial-time robust adaptive method provides high-probability sub-linear regret while guaranteeing stability, robust performance, and parameter estimation.
- The paper identifies fundamental limits linking regret minimization and parameter estimation.
- Whether a polynomial-time algorithm can achieve e O(T) regret remains an open question.
- Finite-sample adaptive control remains open for safety constraints and nonlinear dynamics.
B Synthesis Results
The section develops robust SLS synthesis guarantees for estimated LQR models, first for an infinite-dimensional program and then for a finite-dimensional FIR approximation. It establishes feasibility, suboptimality, and true-system response guarantees under estimation-error and stability conditions.
- Synthesis formulation: The synthesis problem is initially formulated as an infinite-dimensional optimization problem, later relaxed to a finite-dimensional FIR approximation.The analysis assumes the infinite-dimensional problem is solvable before introducing FIR truncation to obtain an efficient finite-dimensional formulation.
- IIR synthesis guarantees: If the transition-matrix estimation error is at most ε and the stated stability conditions hold, program (B.1) is feasible and its optimal controller has a bounded relative LQR-cost error.The guarantee uses constants Cx, Cu, and ρ chosen according to the true optimal closed-loop stability parameters.
- Robustness mechanism: The SLS proof constructs a feasible response from the optimal controller of the estimated system and characterizes its true-system response through the model-mismatch operator.The mismatch is represented by ∆ = (∆A + ∆BK⋆)R_A⋆+B⋆K⋆, linking estimation error to robust response bounds.
- FIR synthesis guarantees: For FIR truncation lengths F ≥ F0, the finite-dimensional semidefinite program (B.3) is feasible and yields a controller whose performance and true-system response satisfy robust bounds.The construction truncates the estimated optimal response and uses the residual response V(F) to control truncation effects.
- Conditions and limitations: The feasibility and performance results require estimation error small relative to stability margins, including ε(Cx + Cu) ≤ O(1)(1 − ρ⋆)^2 in the FIR case.The constants used in the bounds are explicitly noted as non-optimized.
C.2 Stitching the epochs together
The epoch-stitching analysis shows that exponentially growing epochs and decaying injected-noise variance yield simultaneous high-probability bounds across all epochs. These bounds support recursive feasibility of the SLS programs and controlled growth of state and estimation errors.
- Recursive feasibility: Once the first-epoch estimation rate is small enough to meet the synthesis feasibility conditions, feasibility propagates recursively to subsequent epochs.The argument invokes the IIR and FIR synthesis theorems at each epoch under the required conditions on C_T.
- State control: With probability 1 − δ, the first state at the beginning of every epoch satisfies the theorem’s uniform norm bound.The proof obtains this through Gaussian concentration for the disturbance-driven state at epoch boundaries.
- Parameter estimation: With probability 1 − δ, the OLS estimates from all epochs satisfy the stated statistical-rate guarantee simultaneously.The proof combines per-epoch confidence allocations with the recursive feasibility argument.
- Schedule conditions: The theorem’s assumptions permit a sufficiently large finite C_T because the relevant right-hand sides decrease exponentially up to polynomial factors in the epoch index.The IIR and FIR cases use different decay exponents in the stated conditions.
D Regret Decomposition and Analysis
The analysis converts epoch-wise stability and sub-optimality guarantees into high-probability finite-horizon regret bounds for both IIR and FIR controllers. Summing the epochs yields an e O(T 2/3) regret rate, with matching lower-order sharpness up to logarithmic factors.
- Epoch aggregation: The regret is decomposed across logarithmically many epochs, with epoch lengths and exploration scales chosen to balance competing powers of T_i.The number of epochs satisfies E = O(log2 T), and the balancing choice is α = 1/3.
- Cost comparison: The method relates finite-horizon expected costs to infinite-horizon LQR costs through stabilizing system responses and block-Toeplitz truncations.The construction uses Φx and Φu truncations, block-diagonal cost matrices, and H∞ norm bounds.
- Epoch-wise analysis: The regret analysis conditions on estimation events and bounds each epoch’s finite-horizon cost with high conditional probability.The controller’s stability parameters and initial-state bounds are substituted into the finite-horizon cost lemma.
- Final bounds: e O(T 2/3) regret is obtained in both the IIR and FIR cases after ignoring o(T 2/3) terms.Separate bounds are stated for the IIR and FIR controller cases before simplification using the closed-loop H∞ bound.
E Lower bound
The lower-bound analysis models deviations from the optimal controller as an exploration schedule and proves that expected regret is strongly convex in those deviations. Under the stated signal condition, this yields a regret lower bound tied to the amount of exploration.
- System setup: The optimal closed-loop system is initialized at its stationary Gaussian distribution, with M = A⋆+B⋆K⋆ stable under the controllability assumption.The stationary covariance P∞ is defined through the Lyapunov equation for the optimal closed loop.
- Exploration model: The analysis represents inputs as u_t = K⋆x_t + ν_t, where ν_t denotes deviations from the infinite-horizon optimal input.The deviations are restricted to be independent of future process noise.
- Technical argument: The proof establishes positive definiteness of a block matrix using Schur complements and induction, supporting strong convexity of the finite-horizon objective.The matrix D(T) is positive definite for every horizon under N positive definite.
F Miscellaneous Results
This section collects stability, composition, concentration, and matrix inequalities used throughout the analysis. Together, these results control impulse-response norms, Gaussian quadratic costs, and positive-semidefinite constraints.
- System composition: Products and sums of RH∞ systems remain in the class with parameters obtained by combining their decay constants and coefficients.The product and sum rules use max{ρ1, ρ2} for sums and controlled coefficient growth for products.
- Composition proof: The composition argument repeatedly applies decay bounds and logarithmic inequalities to control the response of cascaded systems.The proof constructs an increasing sequence of decay parameters bounded below one over ρ.
- Stability bounds: Systems in RH∞(C, ρ) have H∞ norm at most C/(1−ρ), providing a direct bound on their frequency-domain gain.The result is stated as Lemma F.4.
- Probabilistic tools: Gaussian concentration and the Hanson-Wright inequality provide high-probability bounds for finite-horizon quadratic costs.The probabilistic lemma applies to fixed vectors and matrices with positive-definite Gaussian covariance.
G Implementation of Adaptive Methods
The implementation compares adaptive baselines and converts the robust controller design into finite-dimensional optimization problems. Epoch switching, confidence sets, FIR truncation, and semidefinite constraints make the numerical methods executable.
- OFU and confidence sets: The OFU method builds a confidence set for the dynamics and selects the dynamics with the smallest LQR cost.The associated optimal controller is then applied during the epoch.
- OFU and confidence sets: OFU requires solving a non-convex optimization problem, which the experiments approximate using projected gradient descent.The gradient is derived through the Lyapunov equation and projection uses eigendecomposition followed by scalar root finding.
- Thompson sampling: Thompson sampling replaces OFU’s optimization with a uniformly sampled model from the frequentist confidence set.The implementation samples a Gaussian direction and a uniform scalar to construct the model draw.
- Epoch scheduling: Epochs can be forced to switch after τ = 500 iterations or when the determinant-based information condition is met.The determinant rule also requires at least ten elapsed iterations before switching.
- Finite-dimensional synthesis: FIR truncation and an H∞ semidefinite representation reduce the infinite-dimensional controller design to an SDP solvable by an off-the-shelf solver.The implementation uses a transpose-system formulation to reduce decision-variable dimensions and realizes the controller in state space.
H.1 Large-Transient Dynamics
The large-transient experiment compares adaptive methods using regret and the infinite-horizon cost of each epoch’s controller. Methods show similar regret overall, while robustness helps especially at early stopping.
- H.1 Large-Transient Dynamics: The system is unstable with large transients, relatively low input penalties, and conditions that may hurt optimistic methods.
- H.1 Large-Transient Dynamics: Overall, the adaptive methods have very similar median and 90th percentile regret performance.
- H.1 Large-Transient Dynamics: Robustness guarantees stability and bounded infinite-horizon cost for every controller during operation.
- H.1 Large-Transient Dynamics: At small iteration counts, the robust method performs relatively better, indicating greater suitability for early stopping.
- H.1 Large-Transient Dynamics: 500 experiments compare adaptive methods on median and 90th percentile regret over time and infinite-horizon LQR cost.
H.2 Error Scaling
The error-scaling experiments examine adaptive control under correlated disturbances and state constraints. Enlarging synthesis error bounds produces only modest regret degradation, while the robust formulation supports safe controller synthesis under bounded or probabilistically bounded noise.
- H.2 Error Scaling: Inflating estimation-error bounds causes only modest regret degradation across OFU, TS, and robust methods.
- H.2 Error Scaling: The disturbance-forecasting model uses known system dynamics with disturbances generated by an unknown autonomous LTI system.
- H.2 Error Scaling: Explicit state constraints replace heuristic cost tuning when low input penalties could otherwise allow unsafe state growth.
- H.2 Error Scaling: The robust synthesis constraints ensure bounded closed-loop state when disturbance inputs are bounded.
- H.2 Error Scaling: Bounded-noise assumptions or finite-horizon high-probability noise bounds allow synthesis of safe controllers.