Source-linked AI summary
Online Linear Quadratic Control
Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Yishay Mansour, Kunal Talwar
TL;DR
The paper addresses online control of known noisy linear systems when quadratic costs are chosen adversarially over time. It uses an SDP over steady-state distributions with online learning algorithms, achieving O(√T) regret against strongly stable policies while leaving tightness of the bound open.
Problem
Online LQ control must adapt to adversarially varying quadratic costs under known linear dynamics, with regret measured against fixed fast-mixing policies.
Method
The learner optimizes a novel SDP over steady-state distributions using Online Gradient Descent or Follow the Lazy Leader, then derives control policies.
Results
The algorithms achieve O(√T) regret against strongly stable policies, and every feasible SDP solution yields a strongly stable policy.
Takeaways & Limitations
The SDP enables online optimization while preserving exponentially fast mixing for the policies it produces.
Takeaways & Limitations
The paper leaves open whether its regret bounds are tight or can be improved.
Abstract
from arXiv · showhide
We study the problem of controlling linear time-invariant systems with known noisy dynamics and adversarially chosen quadratic losses. We present the first efficient online learning algorithms in this setting that guarantee $O(\sqrt{T})$ regret under mild assumptions, where $T$ is the time horizon. Our algorithms rely on a novel SDP relaxation for the steady-state distribution of the system. Crucially, and in contrast to previously proposed relaxations, the feasible solutions of our SDP all correspond to "strongly stable" policies that mix exponentially fast to a steady state.
1 Introduction
The paper studies online LQ control with known linear dynamics and adversarially varying quadratic costs, targeting low regret against fast-mixing linear policies. Its approach learns steady-state distributions through an SDP, whose feasible solutions correspond to strongly stable policies.
- Problem: The problem concerns online learning with fixed, known linear dynamics and adversarially chosen quadratic cost matrices.Regret compares the learner with the best fixed control policy in hindsight.
- Results: The algorithms guarantee O(√T) regret when compared with any fast-mixing linear policy.The benchmark class is formalized as strongly stable policies.
- Method: The paper applies Online Gradient Descent and Follow the Lazy Leader to the idealized steady-state-cost problem.The analysis then bounds the gap between idealized and actual costs.
- Method: Instead of predicting a policy directly, the learner predicts a steady-state distribution and derives a corresponding policy through an SDP.The SDP minimizes expected costs as a function of the joint steady-state distribution of states and controls.
- Open question: The paper leaves open whether its O(√T) regret bounds are tight or can be improved.Related work obtains O(log^2 T) regret under much stronger assumptions.
- Novelty: Every feasible solution of the proposed SDP is strongly stable, unlike formulations where only the optimal solution is guaranteed to stabilize.This property supports fast mixing for policies produced during online optimization.
2 Background
LQ control models continuous linear dynamics with Gaussian disturbances and quadratic state-action costs. In the online setting, known dynamics coexist with adversarially selected cost matrices, and the learner minimizes regret against strongly stable policies.
- LQ model: LQ control uses real-valued state and action vectors, linear dynamics with Gaussian noise, and quadratic costs.The infinite-horizon objective is the steady-state average cost.
- LQ model: For controllable systems, the optimal infinite-horizon policy is constant linear feedback derived from algebraic Riccati equations.A stable feedback matrix yields a stationary state distribution.
- Online setting: The online environment selects positive definite state and control cost matrices ahead of time, while the learner observes each state before acting.The dynamics are known and time-invariant, and the system starts from x0 = 0.
- Online setting: The learner chooses actions using the current state and previously observed cost matrices, then incurs the resulting quadratic cost.The algorithm may randomize its action selection.
- Objective: Regret is measured against a benchmark set, fixed here as the class of all strongly stable policies.This benchmark emphasizes policies with controlled mixing behavior.
3 Strong Stability
Strong stability strengthens ordinary stability by controlling both feedback magnitude and the contraction representation of closed-loop dynamics. It guarantees exponential convergence to steady state, while sequential strong stability additionally requires slowly changing policies for mixing across rounds.
- Strong stability: A strongly stable policy has bounded feedback and a similarity representation whose transformed dynamics contract by at least γ.The definition also bounds the conditioning of the similarity transform.
- Strong stability: Strong stability implies ordinary stability, although the closed-loop matrix itself need not have norm below one without a nontrivial transformation.The spectral radius remains below one.
- Mixing guarantee: ∥X̂_t − X∥ ≤ κ^2e^−2γt∥X̂_0 − X∥ gives exponentially fast convergence of state covariances to steady state.The same convergence holds for randomized policies with finite conditional action covariance.
- Covariance bounds: Strongly stable policies have bounded steady-state state and action covariance traces in terms of κ, γ, and the noise covariance.Specifically, Tr(X) ≤ (κ^2/γ)Tr(W) and Tr(U) ≤ (κ^4/γ)Tr(W).
- Sequential strong stability: For a sequence of policies, each policy must be strongly stable and the sequence must change slowly enough for mixing to occur.Sequential strong stability is analyzed together with bounded changes in successive steady-state covariances.
- Sequential strong stability: The covariance convergence analysis extends to randomized policy sequences when conditional action covariances are finite.The expected action remains K_t x at each round.
4 SDP Relaxation for LQ control
The paper formulates an SDP relaxation over steady-state state-control distributions, then shows feasible solutions yield stable—and under noise and trace conditions, strongly stable—policies with no greater cost.
- 4.1 The relaxation: The SDP optimizes expected quadratic cost over a positive semidefinite steady-state covariance matrix satisfying system dynamics and a trace bound.The covariance decomposes into state, control, and cross-covariance blocks.
- 4.1 The relaxation: Any stable policy whose steady-state state and control second moments satisfy the trace bound induces a feasible SDP solution.This establishes the relaxation's inclusion of bounded-cost stable policies.
- 4.2 Extracting a policy: From any feasible covariance Σ, the extracted policy K(Σ) is stable and has steady-state covariance E(K) no greater than Σ in the semidefinite order.E(K) is itself feasible and has cost at most that of Σ.
- 4.2 Extracting a policy: Without the trace constraint, the policy extracted from the SDP optimum is optimal for the original LQ problem.This recovers a classic control-theoretic result.
- 4.3 Strong stability of solutions: Under W ⪰ σ2I and κ = √ν/σ, every feasible solution produces a (κ, 1/2κ2)-strongly stable policy.The same guarantee extends to slowly changing feasible covariance sequences.
5 Online LQ Control
The online controller performs gradient-based updates directly on the SDP covariance, extracts policies, and randomizes actions to preserve fast mixing. Under stated noise, trace, feasibility, and comparator assumptions, it obtains an expected regret guarantee against strongly stable policies.
- Gradient-based online control: The gradient-based algorithm updates an ideal steady-state covariance on the SDP, then extracts a control matrix for prediction.The implementation maintains Σ_t and uses the extracted K_t to generate actions.
- Gradient-based online control: Randomized Gaussian predictions make observed covariances converge to those generated by the extracted policies, supporting faster mixing.The randomization is designed to match the required covariance structure in expectation.
- Regret guarantee: Theorem 5.1 gives an expected regret bound for Algorithm 1 against any (κ, γ)-strongly stable control matrix under Tr(W) ≤ λ2 and W ⪰ σ2I.The theorem specifies parameter choices for ν and η in terms of κ, γ, λ, σ, and T.
- Assumptions: The theorem assumes that the SDP is feasible; otherwise, the strongly stable policy set is empty and the guarantee is vacuous.This is an explicit feasibility assumption of the algorithm and theorem.
- Regret guarantee: The analysis decomposes regret into online-gradient, transient-cost, and comparator terms, bounded using OGD and strong-stability properties.The theorem follows by combining the bounds from Lemmas 5.2–5.4 with selected η and ν.
6 Oracle-based Algorithm
The Oracle-based Follow the Lazy Leader algorithm selects policies minimizing constrained steady-state costs, uses occasional resets after policy switches, and obtains a regret guarantee against strongly stable policies.
- Oracle and algorithm: The Oracle returns a control matrix minimizing steady-state cost subject to a covariance-and-control trace constraint.The constraint is Tr(X) + Tr(KXK^T) ≤ ν.
- Oracle and algorithm: Follow the Lazy Leader perturbs cumulative losses and changes policies only with small probability, yielding O(ηT) expected switches and resets.The perturbations are sampled dependently over time to create the laziness property.
- Resets: After each switch, the algorithm resets the system; under full column-rank B, one-step resetting leaves the next state equal to the process noise.The expected reset cost is at most Cν(1 + ∥B†A∥^2).
- Regret guarantee: Theorem 6.2 bounds expected regret against any (κ, γ)-strongly-stable control matrix when the noise trace and reset cost satisfy the stated assumptions.The theorem chooses ν = 2κ^4λ^2/γ and assumes Tr(W) ≤ λ^2.
- Regret guarantee: Once reset, the learner’s expected cost is always no greater than the steady-state cost of the newly selected policy.This property controls the transient cost after switching policies.
7 Experiments
The experiments evaluate Follow the Lazy Leader for data-center cooling with time-varying power costs, comparing it with a fixed controller and a recent-cost strategy under two cost processes.
- Setup: The experiment learns linear dynamics from real data-center measurements and evaluates controllers in simulation under varying costs.The system regulates server-floor cooling conditions with time-varying power costs.
- Setup: The cooling controller sets blower speeds and water-valve commands for 30 air-handling units every 30 seconds.The controlled variables are cold-aisle temperatures and differential air pressures.
- Results: FLL quickly approaches the fixed linear policy in both cost settings and outperforms the Recent strategy under uniform random costs.The Recent strategy performs better when costs vary slowly, while forgetting old costs may improve FLL in that case.
A.3 Proof of Lemma 4.4
The proof establishes that feasible SDP solutions produce a sequence of policies with sequential strong stability by controlling policy norms and successive covariance changes.
- Sequential strong stability: Feasibility of the SDP yields bounds on the policy norm and an associated matrix norm used to establish sequential strong stability.The proof reduces the stability argument to bounding successive normalized covariance matrices.
- Sequential strong stability: The successive covariance matrices satisfy ∥X_{t+1} − X_t∥ ≤ η, enabling a uniform bound on normalized covariance changes.This bound is the key step controlling how quickly consecutive policies may differ.
- Regret analysis: The Online Gradient Descent regret analysis uses a feasible-domain diameter at most 2ν and loss Lipschitz constant at most 2C.These quantities give the lemma’s regret bound when substituted into the standard OGD guarantee.
A.5 Proof of Lemma 5.3
The proof of Lemma 5.3 compares actual and steady-state covariances for the randomized policies and bounds their discrepancy using strong stability and slowly changing SDP solutions.
- Covariance comparison: The policy π_t(x) = K_t x + v_t is constructed so its action-state covariance matches the SDP solution Σ_t.The proof partitions Σ_t and the observed covariance into state and control blocks.
- Covariance comparison: The loss difference between actual and steady-state behavior decomposes into state-covariance and control-covariance discrepancies.It is written as Qt • (bX_t − X_t) + Rt • (bU_t − U_t).
- Stability bound: Strong stability and the bound ∥X_{t+1} − X_t∥ ≤ 4Cη control the cumulative covariance discrepancy for the changing policy sequence.The argument applies the stability lemma to the randomized policies π_1, …, π_T.
- Stability bound: The proof combines the covariance discrepancy bounds with the initial bound ∥bX_1 − X_1∥ ≤ 2ν to control the relevant regret term.The comparison is completed by combining the displayed inequalities and summing over time.
A.7 Proof of Theorem 5.1
The proof combines bounds on the algorithm’s terms with stability properties to establish the regret guarantee, while showing stable controllers admit finite strong-stability parameters and feasible SDP solutions under stated assumptions.
- Proof of Theorem 5.1: The proof selects η = σ^3/(2C√(νT)) subject to η ≤ σ^4/(4Cν), yielding the stated regret bound.The choice is valid for T ≥ 4ν/σ^2.
- Proof of Theorem 5.1: The theorem’s regret analysis accounts for switch resets through their cost and the expected number of policy switches.The reset cost enters through Cr, while the parameter choice uses ν = 2κ^4λ^2/γ.
- Strong stability: Stable controllers have finite parameters κ, γ > 0 for which they are (κ, γ)-strongly stable.This follows from a Lyapunov argument applied to the closed-loop matrix A + BK.
- SDP feasibility: When B is square and invertible and Q, R are bounded and positive definite, the SDP is feasible and its trace constraint is not binding.The feasibility argument bounds the trace of the constructed covariance and of the unconstrained optimum.
B.2 Controllability
This section connects controllability with bounded-cost state zeroing and uses that property to establish feasibility of the SDP under a trace bound.
- Controllability: Strong controllability means the controllability matrix Ck = (B AB ··· Ak−1B) has a quantitatively bounded inverse-related condition.It is introduced as a quantitative version of the standard condition that permits driving states to zero.
- Controllability: A (k, κ)-strongly controllable system can drive any initial state x0 to zero in k steps at cost at most C∥x0∥2.The bound holds when Q and R have spectral norm at most 1, with C depending on k, κ, ∥A∥, and ∥B∥.
- Proof technique: The controllability proof formulates zeroing as a constrained quadratic program and evaluates its optimum using a least-squares identity.For min_x x^T A x subject to Bx = c, the optimum is c^T(BA^-1B^T)†c.
- Trace bound: If states can be driven to zero in k steps at quadratic cost C∥x0∥2, the noisy system’s SDP is feasible with ν = C · Tr(W).The trace constraint is also not binding under the theorem’s assumptions.
C Bounding the Reset Cost
The reset-cost analysis bounds the cost of returning the system toward a steady state by combining state-zeroing with a stable policy’s stationary behavior.
- Strong-stability reset: A strongly stable policy can reduce a start state to norm at most 1/T^2 in O(log(T∥x0∥)/γ) steps at bounded cost.The argument uses the exponential decay of the noiseless closed-loop dynamics.
- Resetting: Under strong controllability or a strongly stable policy, the reset cost Cr in Follow the Lazy Leader can be bounded.The two assumptions provide alternative ways to control the cost of driving a state toward zero.
- Reset construction: The reset construction combines actions that drive the noiseless component to zero with feedback applied to a noise-driven component.After k rounds, the controlled component is zero while the remaining state is bounded by the steady-state covariance.
- Reset construction: The expected reset cost decomposes into the costs of the independently evolving controlled and noise-driven sequences.The decomposition follows because the noise-driven sequence has mean zero and the sequences are statistically independent.