Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator

By Sarah Dean, Horia Mania, Nikolai Matni, B. Recht, Stephen Tu. 2018

304 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Michael I. Jordan
2. Tengyu Ma
3. Yuanzhi Li
4. B. Recht
5. Chi Jin
6. Jason D. Lee
7. Alekh Agarwal
8. Stephen Tu

In Management Science and Operations Research

1. Alekh Agarwal
2. Akshay Krishnamurthy
3. Wen Sun
4. Nan Jiang
5. Chi Jin
6. Zhuoran Yang
7. Zhaoran Wang
8. J. Langford

Citations in the corpus

• Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “For example, estimated models (Levine & Koltun, 2013; Gu et al., 2016; Kalweit & Boedecker, 2017) On the control theory side, Dean et al. (2018; 2017) provide strong finite sample complexity bounds for solving linear quadratic regulator using model-based approach.”
• Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “This is a key difference from the linear quadratic regulator [1, 18, 4, 3, 15] or the recent work of Yang and Wang [50], whose transition models are completely specified by a finite-dimensional matrix such that the degrees of freedom are bounded.”
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, background): “With rich observations, many prior works either focus on structured control settings like LQRs (Abbasi-Yadkori and Szepesvári, 2011; Dean et al., 2018) or Lipschitz-continuous MDPs (Kakade et al., 2003; Ortner and Ryabko, 2012; Pazis and Parr, 2013; Lakshmanan et al., 2015).”
• Safely Learning to Control the Constrained Linear Quadratic Regulator (2018, methodology): “[7] provide a robust online method that guarantees parameter estimation and stability throughout.”
• Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis (2019, background): “Finally, we would like to mention another related line of work: learning-based control [44, 45, 46, 47, 48].”