Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator

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

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 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.

Introduction

In control theory, the Linear Quadratic Regulator (LQR) is a fundamental problem focused on controlling a linear system to minimize a quadratic cost function. When the system's dynamics—defined by the matrices $A$ and $B$—are known, the solution is well-understood and computationally efficient. However, in many real-world applications, these dynamics are unknown and must be learned through interaction, a process known as adaptive control.

Adaptive control introduces a classic exploration-exploitation dilemma: the controller must move the system to learn its dynamics (exploration) while simultaneously attempting to minimize costs and maintain stability (exploitation). Previous research has largely been split between two approaches: "Optimism in the Face of Uncertainty" (OFU), which achieves optimal regret but is computationally intractable, and Thompson Sampling, which is easier to compute but often lacks rigorous theoretical guarantees for general systems. This paper bridges that gap by introducing the first polynomial-time algorithm for the adaptive LQR problem that provides high-probability, sub-linear regret guarantees.

Methodology: System Level Synthesis and Robust Control

The core innovation of this work is the integration of System Level Synthesis (SLS) with robust control techniques. Traditionally, searching for an optimal controller $K$ is a non-convex optimization problem, making it difficult to solve efficiently. SLS bypasses this by parameterizing the closed-loop responses of the system instead of the controller itself. This change of variables transforms the optimization into an affine, and therefore convex, problem.

The proposed algorithm operates through an epoch-based learning structure:

  1. Estimation: At the conclusion of each epoch, the algorithm uses a Least Squares approach to estimate system parameters based on the data collected.
  2. Robust Synthesis: Rather than relying solely on a point estimate, the algorithm constructs a "confidence set" of possible systems. It then solves a robust optimization problem to find a controller that performs reliably across all systems within that set, ensuring stability even under model uncertainty.
  3. Exploration Noise: To ensure the system is sufficiently "excited" for accurate parameter estimation, the algorithm injects carefully calibrated Gaussian noise.

Theoretical Contributions and Regret Bounds

A primary contribution of this research is the proof of a high-probability regret bound of $\tilde{O}(T^{2/3})$. While OFU methods can theoretically achieve $\sqrt{T}$ regret, they remain computationally intractable for general systems. This paper demonstrates that by using a specific exploration schedule to maintain tractability, the $T^{2/3}$ bound is actually the best achievable rate. This reveals a fundamental trade-off between computational efficiency and theoretical regret limits.

Furthermore, the authors prove that system parameters are learned at a rate of $\tilde{O}(T^{-1/3})$. This rigorous mathematical framework ensures that the controller remains stabilizing throughout the entire learning process, a critical requirement for physical engineering systems where instability can lead to catastrophic failure.

Numerical Evaluation

The algorithm was evaluated using several simulated dynamical systems designed to test different aspects of control performance:

  • Marginally Unstable Laplacian System: A 3-state system with weakly connected nodes, testing the algorithm's ability to stabilize challenging dynamics.
  • Large-Transient System: A system characterized by large spikes in state values, used to demonstrate the robustness of the controller under extreme conditions.
  • Demand Forecasting: A practical application involving a server farm. In this scenario, the controller managed "temperature" (state) subject to stochastic job arrivals and safety constraints, showcasing the method's flexibility in handling state constraints.

In these simulations, the robust adaptive algorithm performed comparably to heuristic versions of OFU and Thompson Sampling. Crucially, it demonstrated significantly lower worst-case costs and maintained guaranteed stability where other methods might fail.

Conclusion and Future Work

This work provides a computationally efficient and mathematically rigorous path forward for adaptive LQR control. By leveraging SLS and robust optimization, the authors have created an algorithm that is both implementable for real-world engineering tasks and backed by provable performance guarantees.

Future research may address the remaining gap between the $T^{2/3}$ regret achieved here and the $T^{1/2}$ theoretical limit of intractable methods. Additionally, while this work focuses on linear systems, extending these robust, convex-optimization-based guarantees to non-linear dynamics remains a significant and necessary challenge for the field.

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 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.
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