# Minimal Expected Regret in Linear Quadratic Control

arXiv: https://arxiv.org/abs/2109.14429 · HTML: https://mlsanity.com/paper/2109.14429/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 31 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 5 of 5)

- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Reinforcement Learning with Fast Stabilization in Linear Dynamical Systems](https://mlsanity.com/paper/2007.12291/) (2020)
- [Input Perturbations for Adaptive Control and Learning](https://mlsanity.com/paper/1811.04258/) (2018)
- [From self-tuning regulators to reinforcement learning and back again](https://mlsanity.com/paper/1906.11392/) (2019)
- [Optimism-Based Adaptive Regulation of Linear-Quadratic Systems](https://mlsanity.com/paper/1711.07230/) (2017)

## Built on by (most cited first, 13 of 13)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [Nonasymptotic Regret Analysis of Adaptive Linear Quadratic Control with Model Misspecification](https://mlsanity.com/paper/2401.00073/) (2023)
- [Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems](https://mlsanity.com/paper/2111.03772/) (2021)
- [Regret Analysis of Multi-task Representation Learning for Linear-Quadratic Adaptive Control](https://mlsanity.com/paper/2407.05781/) (2024)
- [Implications of Regret on Stability of Linear Dynamical Systems](https://mlsanity.com/paper/2211.07411/) (2022)
- [Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics](https://mlsanity.com/paper/2202.05799/) (2022)
- [Finite Time Regret Bounds for Minimum Variance Control of Autoregressive Systems with Exogenous Inputs](https://mlsanity.com/paper/2305.16974/) (2023)
- [Sub-linear Regret in Adaptive Model Predictive Control](https://mlsanity.com/paper/2310.04842/) (2023)
- [Logarithmic Regret for Nonlinear Control](https://mlsanity.com/paper/2501.10261/) (2025)
- [The Cost of Learning Under Multiple Change Points](https://mlsanity.com/paper/2602.11406/) (2026)
- [Geometric structures and deviations on James' symmetric positive-definite matrix bicone domain](https://mlsanity.com/paper/2603.02483/) (2026)

## Abstract (arXiv)

We consider the problem of online learning in Linear Quadratic Control systems whose state transition and state-action transition matrices A and B may be initially unknown. We devise an online learning algorithm and provide guarantees on its expected regret. This regret at time T is upper bounded (i) by widetildeO((du+dx)√dxT) when A and B are unknown, (ii) by widetildeO(dx2log(T)) if only A is unknown, and (iii) by widetildeO(dx(du+dx)log(T)) if only B is unknown and under some mild non-degeneracy condition (dx and du denote the dimensions of the state and of the control input, respectively). These regret scalings are minimal in T, dx and du as they match existing lower bounds in scenario (i) when dx≤ du [SF20], and in scenario (ii) [lai1986]. We conjecture that our upper bounds are also optimal in scenario (iii) (there is no known lower bound in this setting). Existing online algorithms proceed in epochs of (typically exponentially) growing durations. The control policy is fixed within each epoch, which considerably simplifies the analysis of the estimation error on A and B and hence of the regret. Our algorithm departs from this design choice: it is a simple variant of certainty-equivalence regulators, where the estimates of A and B and the resulting control policy can be updated as frequently as we wish, possibly at every step. Quantifying the impact of such a constantly-varying control policy on the performance of these estimates and on the regret constitutes one of the technical challenges tackled in this paper.