# Learning to Control Linear Systems can be Hard arXiv: https://arxiv.org/abs/2205.14035 ยท HTML: https://mlsanity.com/paper/2205.14035/ ## Key facts - Cited by 11 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 50 references that are in the map. - First posted on arXiv 27 May 2022. ## Builds on (most cited first, 30 of 32) - [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017) - [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017) - [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) - [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (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) - [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018) - [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019) - [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017) - [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019) - [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018) - [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020) - [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020) - [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020) - [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020) - [On Adaptive Linear-Quadratic Regulators](https://mlsanity.com/paper/1806.10749/) (2018) - [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019) - [Learning Sparse Dynamical Systems from a Single Sample Trajectory](https://mlsanity.com/paper/1904.09396/) (2019) - [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021) - [A Tutorial on Concentration Bounds for System Identification](https://mlsanity.com/paper/1906.11395/) (2019) - [Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation](https://mlsanity.com/paper/2007.06482/) (2020) - [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013) - [From self-tuning regulators to reinforcement learning and back again](https://mlsanity.com/paper/1906.11392/) (2019) - [Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification](https://mlsanity.com/paper/1707.04791/) (2017) - [Model-Free Linear Quadratic Control via Reduction to Expert Prediction](https://mlsanity.com/paper/1804.06021/) (2018) - [Certainty Equivalence is Efficient for Linear Quadratic Control](https://mlsanity.com/paper/1902.07826/) (2019) - [Minimal Expected Regret in Linear Quadratic Control](https://mlsanity.com/paper/2109.14429/) (2021) - [Controllability Metrics, Limitations and Algorithms for Complex Networks](https://mlsanity.com/paper/1308.1201/) (2013) ## 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) - [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) - [Maximum diffusion reinforcement learning](https://mlsanity.com/paper/2309.15293/) (2023) - [Nonasymptotic Regret Analysis of Adaptive Linear Quadratic Control with Model Misspecification](https://mlsanity.com/paper/2401.00073/) (2023) - [Learning Stabilizing Policies via an Unstable Subspace Representation](https://mlsanity.com/paper/2505.01348/) (2025) - [Suboptimality analysis of receding horizon quadratic control with unknown linear systems and its applications in learning-based control](https://mlsanity.com/paper/2301.07876/) (2023) - [On the Hardness of Learning to Stabilize Linear Systems](https://mlsanity.com/paper/2311.11151/) (2023) - [End-to-end guarantees for indirect data-driven control of bilinear systems with finite stochastic data](https://mlsanity.com/paper/2409.18010/) (2024) - [To Learn or Not to Learn: A Litmus Test for Using Reinforcement Learning in Control](https://mlsanity.com/paper/2604.11463/) (2026) - [A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems](https://mlsanity.com/paper/2607.02050/) (2026) ## Abstract (arXiv) In this paper, we study the statistical difficulty of learning to control linear systems. We focus on two standard benchmarks, the sample complexity of stabilization, and the regret of the online learning of the Linear Quadratic Regulator (LQR). Prior results state that the statistical difficulty for both benchmarks scales polynomially with the system state dimension up to system-theoretic quantities. However, this does not reveal the whole picture. By utilizing minimax lower bounds for both benchmarks, we prove that there exist non-trivial classes of systems for which learning complexity scales dramatically, i.e. exponentially, with the system dimension. This situation arises in the case of underactuated systems, i.e. systems with fewer inputs than states. Such systems are structurally difficult to control and their system theoretic quantities can scale exponentially with the system dimension dominating learning complexity. Under some additional structural assumptions (bounding systems away from uncontrollability), we provide qualitatively matching upper bounds. We prove that learning complexity can be at most exponential with the controllability index of the system, that is the degree of underactuation.