Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator

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

In the world of control theory, the Linear Quadratic Regulator (LQR) is a cornerstone. It provides a mathematically elegant way to steer a system (like a drone or a chemical plant) to a desired state while minimizing a quadratic cost (like fuel consumption or error). But there’s a catch: standard LQR assumes you know exactly how the system behaves—its "physics" or transition matrices.

In reality, we often don't. We have to learn the system while controlling it. This is the "Adaptive LQR" problem, and a recent paper from researchers at UC Berkeley provides a major breakthrough in making this process both computationally efficient and theoretically sound.

TL;DR

The authors present the first polynomial-time algorithm for adaptive LQR that provides high-probability guarantees of "sub-linear regret" (meaning the controller gets closer to optimal over time). By leveraging System Level Synthesis (SLS), they bypass the computational nightmares of previous methods, achieving a regret bound of $O(T^{2/3})$ while guaranteeing system stability at every step.

What Problem Does This Paper Address?

Adaptive control is a balancing act between exploration (trying new things to learn the system) and exploitation (using what you know to minimize cost). The "gold standard" for measuring success here is regret: the cumulative difference between the cost incurred by your learning algorithm and the cost incurred by an "oracle" that knew the system perfectly from the start.

Until now, researchers faced a frustrating trade-off:

  1. Optimism in the Face of Uncertainty (OFU): These methods achieve near-perfect regret ($O(\sqrt{T})$) but require solving a non-convex optimization problem at every step—a task that is computationally "intractable" (it could take forever).
  2. Thompson Sampling (TS): These are faster but often lack high-probability guarantees for general (non-scalar) systems or rely on unrealistic assumptions about knowing a "safe" set of controllers beforehand.

The gap was a practical, efficient algorithm that actually works for multi-dimensional systems without needing a supercomputer or a crystal ball.

Methods

The authors introduce a Robust Adaptive Control algorithm. Its secret sauce is a combination of three components:

  1. Epoch-based Learning: Instead of updating the controller at every millisecond, the algorithm works in "epochs" of increasing length. This allows for stable data collection before making a change.
  2. System Level Synthesis (SLS): This is the core innovation. Traditional LQR optimizes over the controller gain $K$, which makes the math non-convex and messy when uncertainty is involved. SLS instead optimizes over the closed-loop system responses. This "convexifies" the problem, allowing the authors to use standard, efficient Semidefinite Programming (SDP) to find the best robust controller.
  3. Coarse-ID with Exploration Noise: During each epoch, the algorithm injects a small amount of Gaussian noise to ensure the system is "excited" enough to reveal its true parameters through least-squares estimation.

Datasets

As a theoretical control paper, the evaluation is performed on simulated dynamical systems rather than static datasets:

  • Marginally Unstable Laplacian System: A 3-state system representing weakly connected nodes. This is a classic "hard" case because the system is on the edge of blowing up, testing the algorithm's stability guarantees.
  • Demand Forecasting Example: A more complex scenario involving an unknown autonomous system (representing job demand at a server farm) where the controller must manage temperature while respecting strict state constraints.

Key Insights and Ideas

  • Robustness = Stability: Unlike "optimistic" methods that pick the best-case scenario within their uncertainty bounds, this algorithm picks a controller that is robust to the worst-case scenario within those bounds. This ensures the system never becomes unstable during the learning process.
  • The $T^{2/3}$ Trade-off: The authors prove a regret bound of $O(T^{2/3})$. While this is theoretically "worse" than the $O(\sqrt{T})$ of intractable methods, they show it is a fundamental limit when you use a fixed exploration noise schedule.
  • Convexification is King: By shifting the perspective from "What is the best $K$?" to "What are the best system responses?", the authors turned a "hard" math problem into one that a standard laptop can solve in seconds.

Key Results

  • Efficiency: The algorithm is provably polynomial-time. It uses SDPs that grow only logarithmically with time $T$.
  • Estimation Rate: The algorithm identifies the unknown system matrices ($A$ and $B$) at a rate of $O(T^{-1/3})$.
  • Performance: In simulations, the robust adaptive method performed comparably to heuristic versions of OFU and Thompson Sampling in terms of regret, but it was significantly more stable and consistently achieved lower infinite-horizon costs.
Cumulative Regret and LQR Cost
  • Constraint Handling: The method successfully handled state constraints (e.g., "don't let the temperature exceed $X$"), a feat that standard LQR methods struggle with.
Server Farm Constraint Handling

Limitations and Future Work

The most obvious limitation is the gap between the $O(T^{2/3})$ regret achieved here and the $O(\sqrt{T})$ lower bound for the general LQR problem. The authors suggest that more sophisticated, time-varying exploration schedules might bridge this gap.

Additionally, the current analysis relies on a "stability margin" ($\rho$) that is assumed to be known or estimable. Future work could look into making the algorithm even more "blind" to these underlying constants. Finally, extending these robust guarantees to non-linear systems remains the "final frontier" for adaptive control.

Summary updated

Abstract

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 achieves 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.
BibTeX
@inproceedings{dean2018regret,
  author = {Sarah Dean and Horia Mania and Nikolai Matni and Benjamin Recht and Stephen Tu},
  title = {{Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=r1b3TLb_-r},
}
Figure