Source-linked AI summary
Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
Alon Cohen, Tomer Koren, Yishay Mansour
TL;DR
The paper addresses adaptive LQ control with unknown dynamics, where learning must occur while avoiding costly instability. It introduces an optimistic, confidence-aware semidefinite-programming algorithm and obtains approximately sqrt(T) regret efficiently, resolving prior open questions.
Problem
Adaptive LQ control requires learning unknown dynamics while controlling states whose growth can make costs arbitrarily large.
Method
The algorithm solves confidence-aware relaxed semidefinite programs to compute optimistic policies that balance exploitation with exploration.
Results
The paper gives the first computationally efficient algorithm with a high-probability approximately sqrt(T) regret bound for learning LQ systems.
Takeaways & Limitations
The result resolves open questions on achieving approximately sqrt(T) regret computationally efficiently in LQ control with unknown dynamics.
Takeaways & Limitations
The analysis requires sequential strong stability, because switching among individually stable policies can otherwise cause states to grow polynomially in T.
Abstract
from arXiv · showhide
We present the first computationally-efficient algorithm with $\widetilde O(\sqrt{T})$ regret for learning in Linear Quadratic Control systems with unknown dynamics. By that, we resolve an open question of Abbasi-Yadkori and Szepesvári (2011) and Dean, Mania, Matni, Recht, and Tu (2018).
1 Introduction
Adaptive LQ control requires learning unknown dynamics while preventing instability and controlling regret. This paper gives the first computationally efficient algorithm with approximately sqrt(T) regret, resolving prior open problems.
- Adaptive control must learn unknown system parameters while regulating states whose uncontrolled growth can make costs arbitrarily large.
- Regret compares the learner’s total cost with T times the steady-state cost of the optimal policy computed using known dynamics.
- Earlier methods achieved polynomial-dimensional regret bounds but required computationally inefficient non-convex optimization at every step.
- Dean et al. (2018) obtained O(T^2/3) regret efficiently, while an efficient algorithm with approximately sqrt(T) regret remained open.
- The paper presents the first computationally efficient algorithm with approximately sqrt(T) regret for learning LQ systems.
- The approach uses optimism in the face of uncertainty, balancing exploitation of current estimates against exploration for better future estimates.
2 Preliminaries
LQ control models linear noisy dynamics with quadratic costs, while adaptive control learns unknown dynamics online. The preliminaries formulate optimal control through stability conditions and a semidefinite program.
- LQ control: In LQ control, dynamics are linear in state and action, Gaussian noise perturbs the system, and costs are quadratic.
- Problem setting: The learner observes each state, chooses an action, incurs a cost, and receives a successor state over T rounds.
- Optimal policy: The optimal controllable-system policy is linear, π⋆(x) = K⋆x, and minimizes the infinite-horizon steady-state cost J⋆.
- Stability: A policy K is stable when ρ(A⋆ + B⋆K) < 1, but stability of individual policies does not ensure safe switching between policies.
- Problem setting: The dynamics matrices A⋆ and B⋆ are unknown, whereas the positive-definite cost matrices Q and R are fixed and known.
- SDP formulation: The LQR planning problem can be written as a convex semidefinite program whose optimal value equals J⋆ and whose solution yields an optimal policy.
- Stability: Sequential strong stability controls expected state magnitudes across policy sequences, preventing switching-induced state blow-up.
3 Efficient Algorithm for Learning in LQRs
OSLO learns system parameters online and computes policies through confidence-aware relaxed SDPs. The resulting policies are used for both control and data collection.
- Algorithm structure: OSLO maintains improving dynamics estimates and a positive-definite confidence matrix, updating them in epochs when confidence-ellipsoid volume halves.
- Parameter estimation: The algorithm uses least squares to estimate the unknown dynamics from observations and constructs confidence bounds from their covariance matrix.
- Policy computation: It solves a relaxed semidefinite program using current estimates and confidence information to compute a stable policy.
- Policy computation: When estimates are sufficiently accurate, the relaxed SDP underestimates the optimal steady-state cost, implementing optimism under uncertainty.
- Control and updating: After extracting Kt, the algorithm applies ut = Ktxt, then updates its confidence matrix with the new state-action observation.
- Control and updating: Each policy serves as both a current best guess for the optimal policy and a mechanism for collecting samples that improve later estimates.
4 Overview of Analysis
The analysis establishes a high-probability regret bound under suitable initialization, while showing that each round runs in polynomial time. Its core argument combines parameter estimation, relaxed-SDP policy computation, sequential stability, and concentration bounds.
- Main result: Theorem 4 gives a high-probability regret bound for Algorithm 1 when its initial estimation error satisfies the stated condition.The bound applies with probability at least 1 − δ.
- Main result: The procedure has polynomial runtime per round in the relevant problem parameters and T, log(1/δ).
- Parameter estimation: Algorithm 1 repeatedly computes least-squares estimates of the unknown dynamics and uses confidence bounds to control estimation error.The analysis relies on a high-probability self-normalized martingale bound and on bounded visited states.
- Policy computation via a relaxed SDP: The relaxed SDP produces policies whose extracted gains are well defined and whose objective value is controlled by the optimal steady-state cost.The SDP also supplies a positive semidefinite dual matrix used in the analysis.
- Sequential strong stability: Repeated relaxed-SDP solutions yield a sequentially strongly stable policy sequence, ensuring the good event occurs with probability at least 1 − δ/2.The stability argument controls state growth across policy updates rather than only for each policy separately.
- Regret analysis: The regret proof combines SDP-based instantaneous-regret bounds, martingale concentration, telescoping across unchanged policies, and at most O(n log T) policy switches.The main theorem follows by combining these bounds with a union bound and algebraic simplification.
5 The relaxed SDP program
The paper repeatedly solves a relaxed semidefinite program that approximates the exact LQ control program and extracts deterministic linear policies. As the relaxations tighten, stability properties of the resulting policy sequence support the analysis.
- Relaxed SDP formulation: The relaxed program imposes a matrix inequality involving the estimated dynamics, process noise, and confidence matrix V.The dynamics error is constrained through Tr(∆V∆^T) ≤ 1.
- Relaxed SDP formulation: The relaxed SDP is a relaxation of the exact SDP when the dynamics estimates are sufficiently accurate.Its optimal value is at most the optimal infinite-horizon cost, with bounded primal and dual solution norms.
- Policy extraction: The SDP yields a deterministic linear policy K = Σ_uxΣ_xx^-1, provided Σ_xx is invertible.The analysis establishes positive definiteness of Σ_xx using primal-dual properties and rank arguments.
- Sequential stability: The sequence of policies generated by the relaxed SDPs is strongly stable under the stated conditions on V_t and µ.Theorem 17 requires V_t ⪰ 16κ^10µI, while Lemma 18 supplies uniform bounds on the associated factors.
- Sequential stability: The optimal SDP solutions remain close across rounds, helping ensure that successive extracted policies do not change drastically.Lemma 19 gives the comparison P_t ⪯ P⋆ ⪯ P_{t+1} + (α_0γ/2)I.
6 Warm-up Using a Stable Policy
The warm-up phase uses a known strongly stable policy with Gaussian exploration to collect samples and initialize the confidence matrix. A high-probability theorem provides the matrix bounds needed by the main algorithm.
- Warm-up procedure: The warm-up procedure assumes a known policy K_0 that is (κ_0, γ_0)-strongly stable.Starting from x_1 = 0, it runs for T_0 rounds under exploratory Gaussian actions.
- Warm-up procedure: Gaussian exploration actions are sampled independently around K_0x_t with covariance 2σ^2κ_0^2I.The collected vectors z_t = (x_t,u_t) determine the empirical covariance used to initialize V_0.
- Warm-up guarantee: The warm-up analysis adapts identification techniques for linear dynamical systems and concentration inequalities for Gaussian and martingale quantities.The proof invokes Hanson-Wright, Azuma, and self-normalized concentration tools.
A.3 Proof of Lemma 3
The proof bounds the state and regret processes along the sequentially strongly stable policy sequence. It combines confidence-matrix control, determinant updates, and concentration arguments to obtain the theorem’s high-probability conclusion.
- State control: Sequential strong stability ensures that expected state-vector magnitudes remain controlled.The dynamics are represented through uniformly bounded similarity transforms and contracting factors.
- State control: The proof introduces events E_t under which parameter estimates are accurate and state-feature norms remain bounded.These events are used to control the confidence matrices and associated regret quantities.
- Confidence and updates: Matrix norm bounds and the relaxed-SDP properties control the per-round regret contributions on the good events.The argument uses bounds on ∥z_t∥ and ∥P_t∥_* together with Lemma 27.
- Confidence and updates: The algorithm updates its policy when the determinant of the confidence matrix grows sufficiently, yielding a bounded number of policy changes.The proof uses det(V_t) ≤ 2 det(V_τ(t)) between update times.
- Conclusion: A union bound and algebraic simplification complete the high-probability regret argument.The final step plugs in the bounds from Lemmas 10–13.
B.2 Proof of Corollary 5
The proof of Corollary 5 transfers the warm-up covariance guarantee into the initial conditions required by the main theorem. It then combines the theorem and auxiliary lemma through a union bound to bound total regret.
- Initialization: The lower bound V ⪰ V_0 ⪰ (T_0σ^2/80)I makes the initial conditions of Theorem 4 hold when Theorem 20 succeeds.Thus, the warm-up duration supplies the required initialization scale.
- High-probability guarantee: With probability at least 1 − δ, Theorems 4 and 20 and Lemma 6 hold simultaneously after allocating failure probability across them.The proof applies a union bound with probability at least 1 − δ/3 for each component.
- High-probability guarantee: The total regret combines the warm-up regret with the remaining-round regret controlled by Theorem 4.The proof explicitly separates the initial exploration phase from the subsequent main-algorithm phase.
- Dynamics estimation: The dynamics estimator is analyzed by writing x_{s+1} = Θ⋆z_s + w_s and applying self-normalized concentration coordinatewise.A union bound then makes the coordinatewise bounds hold simultaneously.
- Dynamics estimation: The resulting estimation bounds ensure Tr(∆_tV_t∆_t) ≤ 1 under Algorithm 1’s conditions.This verifies the confidence condition needed by the relaxed-SDP analysis.
B.4 Proof of Lemma 7
The proof establishes the lemma by applying Lemmas 15 and 16 to bound the SDP quantities and connect them to the true parameters.
- Lemma 15 gives item (i) and bounds the SDP dual solution as ∥P_t∥_* ≤ ν/σ2.
- V_t is lower bounded by (νμ)/(α0σ2) times the identity, enabling Lemma 16 to establish item (ii).
- The dual matrix P_t is positive semidefinite by the SDP dual formulation, while Lemma 16 supplies an additional bound for item (iii).
- The proof links the resulting equation to the true parameters (A*, B*) by combining it with Lemma 24.
B.5 Proof of Lemma 8
The proof controls the algorithm’s policies, states, and SDP quantities on a high-probability event, using concentration inequalities, stability, and policy-update counting.
- A union bound combines Lemma 6 and Hanson-Wright concentration to obtain simultaneous validity with probability 1 − δ.
- The event ∥V_t∥ ≤ 4T ensures sequential strong stability and yields a bound on the state norms ∥z_t∥2.
- Theorem 17 applies to the policy sequence once μ ≥ 1 + 2ϑ∥V_t∥1/2 and V_t ⪰ 16κ10μI hold for every round.
- Algorithm 1 changes policy at most 2n log T times under the event E_N.
- A Gaussian martingale concentration argument bounds sums involving the SDP matrices by truncating quadratic forms and applying Azuma and Hanson-Wright inequalities.
- Applying the resulting concentration lemma with M_t = P_t I{E_t} uses the bound ∥P_t∥_* ≤ ν/σ2 on E_t.
C Proofs of Section 5
These proofs compare the SDP solution with the optimal Riccati solution and use matrix inequalities to establish ordering and norm properties of the resulting policies.
- Lemmas 16 and 24 provide the principal matrix inequalities used to compare the SDP quantities with the optimal solution.
- The assumption V ⪰ 2κ2μI allows Lemma 14 to control the policy-related quantities.
- The Riccati equation characterizes P*, whose associated optimal policy K* is strongly stable.
- Subtracting the derived matrix inequalities establishes the required ordering between P and P* and supports the final norm bound.
D Proofs of Section 6
The proofs establish high-probability state and covariance bounds, lower-bound the smallest eigenvalue of the covariance matrix, and use these properties to control estimation and regret arguments.
- Lemma 32 provides a high-probability uniform bound on the states over t = 1, . . . , T0 + 1.
- Under the strongly stable policy K0, the state process is analyzed as an LQR system with modified Gaussian noise B*η_t + w_t.
- For any unit vector n, Lemma 33 gives n^T V n ≥ T0 · σ2/40 when T0 ≥ 200 log(1/δ).
- The proofs use Gaussian tails, martingale differences, and Azuma’s inequality to control indicator events and their cumulative behavior.
- The main theorem proof begins by introducing Gaussian exploration noise η_t with variance 2σ2κ2 and then applies the preceding bounds.
- A 1/4-net argument yields ∥V^-1∥ ≤ 80/(T0σ2), provided T0 ≥ 400(n + log(1/δ)).