mlsanityData to 7 Oct 2026

Learning to Control Linear Systems can be Hard

arXiv 2205.14035 ↗First posted 27 May 2022cs.LG cs.SY eess.SYcited by 10

Not on the map. Why?

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.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 32 of its 50 references that are in the map. First posted on arXiv 27 May 2022.

Builds on

32 of 50 references.

References · 32

  1. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  2. 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
  3. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  4. 2018A Tour of Reinforcement Learning: The View from Continuous Controlcited by 129
  5. 2020Naive Exploration is Optimal for Online LQRcited by 111
  6. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  7. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  8. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  9. 2018Non-asymptotic Identification of LTI Systems from a Single Trajectorycited by 77
  10. 2019Finite Sample Analysis of Stochastic System Identificationcited by 67
  11. 2017Finite Time Identification in Unstable Linear Systemscited by 66
  12. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
20 more
  1. 2018Online Linear Quadratic Controlcited by 55
  2. 2020Logarithmic Regret Bound in Partially Observable Linear Dynamical Systemscited by 46
  3. 2020Black-Box Control for Linear Dynamical Systemscited by 43
  4. 2020Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectoriescited by 38
  5. 2020Active Learning for Identification of Linear Dynamical Systemscited by 33
  6. 2018On Adaptive Linear-Quadratic Regulatorscited by 21
  7. 2019Sample Complexity Lower Bounds for Linear System Identificationcited by 20
  8. 2019Learning Sparse Dynamical Systems from a Single Sample Trajectorycited by 20
  9. 2021Linear Systems can be Hard to Learncited by 20
  10. 2019A Tutorial on Concentration Bounds for System Identificationcited by 19
  11. 2020Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxationcited by 18
  12. 2013Online Regret Bounds for Undiscounted Continuous Reinforcement Learningcited by 17
  13. 2019From self-tuning regulators to reinforcement learning and back againcited by 17
  14. 2017Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identificationcited by 16
  15. 2019Certainty Equivalence is Efficient for Linear Quadratic Controlcited by 13
  16. 2021Minimal Expected Regret in Linear Quadratic Controlcited by 13
  17. 2013Controllability Metrics, Limitations and Algorithms for Complex Networkscited by 10
  18. 2018Model-Free Linear Quadratic Control via Reduction to Expert Predictioncited by 10
  19. 2019Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reductioncited by 9
  20. 2021Sparsity in Partially Controllable Linear Systemscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 1; 2025: 1; 2026: 1.

10 papers.

  1. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 52
  2. 2023Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Datacited by 12
  3. 2023Maximum diffusion reinforcement learningcited by 8
  4. 2022How are policy gradient methods affected by the limits of control?cited by 6
  5. 2023Nonasymptotic Regret Analysis of Adaptive Linear Quadratic Control with Model Misspecificationcited by 6
  6. 2025Learning Stabilizing Policies via an Unstable Subspace Representationcited by 3
  7. 2023Suboptimality analysis of receding horizon quadratic control with unknown linear systems and its applications in learning-based controlcited by 1
  8. 2023On the Hardness of Learning to Stabilize Linear Systemscited by 1
  9. 2024End-to-end guarantees for indirect data-driven control of bilinear systems with finite stochastic datacited by 1
  10. 2026A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systemscited by 0