# Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 69 references that are in the map.
- First posted on arXiv 5 Jan 2022.

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

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Data Efficient Reinforcement Learning for Legged Robots](https://mlsanity.com/paper/1907.03613/) (2019)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator](https://mlsanity.com/paper/2003.07937/) (2020)
- [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Input Perturbations for Adaptive Control and Learning](https://mlsanity.com/paper/1811.04258/) (2018)
- [Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation](https://mlsanity.com/paper/2007.06482/) (2020)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [Model-Free Linear Quadratic Control via Reduction to Expert Prediction](https://mlsanity.com/paper/1804.06021/) (2018)
- [Minimal Expected Regret in Linear Quadratic Control](https://mlsanity.com/paper/2109.14429/) (2021)
- [On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix](https://mlsanity.com/paper/2011.09288/) (2020)

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

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [How are policy gradient methods affected by the limits of control?](https://mlsanity.com/paper/2206.06863/) (2022)
- [Active Learning for Control-Oriented Identification of Nonlinear Systems](https://mlsanity.com/paper/2404.09030/) (2024)
- [Nonasymptotic Regret Analysis of Adaptive Linear Quadratic Control with Model Misspecification](https://mlsanity.com/paper/2401.00073/) (2023)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Learning Decentralized Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2210.08886/) (2022)
- [Adversarially Robust Multitask Adaptive Control](https://mlsanity.com/paper/2511.05444/) (2025)
- [Optimistic Online LQR via Intrinsic Rewards](https://mlsanity.com/paper/2603.28938/) (2026)
- [Logarithmic Regret for Nonlinear Control](https://mlsanity.com/paper/2501.10261/) (2025)

## Abstract (arXiv)

TWe establish regret lower bounds for adaptively controlling an unknown linear Gaussian system with quadratic costs. We combine ideas from experiment design, estimation theory and a perturbation bound of certain information matrices to derive regret lower bounds exhibiting scaling on the order of magnitude √T in the time horizon T. Our bounds accurately capture the role of control-theoretic parameters and we are able to show that systems that are hard to control are also hard to learn to control; when instantiated to state feedback systems we recover the dimensional dependency of earlier work but with improved scaling with system-theoretic constants such as system costs and Gramians. Furthermore, we extend our results to a class of partially observed systems and demonstrate that systems with poor observability structure also are hard to learn to control.