# On the Hardness of Learning to Stabilize Linear Systems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 18 Nov 2023.

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

- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (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)
- [Formulas for Data-driven Control: Stabilization, Optimality and Robustness](https://mlsanity.com/paper/1903.06842/) (2019)
- [Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergence](https://mlsanity.com/paper/1910.09496/) (2019)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Distributed Reinforcement Learning for Decentralized Linear Quadratic Control: A Derivative-Free Policy Optimization Approach](https://mlsanity.com/paper/1912.09135/) (2019)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [Analysis of the Optimization Landscape of Linear Quadratic Gaussian (LQG) Control](https://mlsanity.com/paper/2102.04393/) (2021)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019)
- [Reinforcement Learning with Fast Stabilization in Linear Dynamical Systems](https://mlsanity.com/paper/2007.12291/) (2020)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Sample Complexity of Linear Quadratic Gaussian (LQG) Control for Output Feedback Systems](https://mlsanity.com/paper/2011.09929/) (2020)
- [Optimism-Based Adaptive Regulation of Linear-Quadratic Systems](https://mlsanity.com/paper/1711.07230/) (2017)
- [Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds](https://mlsanity.com/paper/2111.07018/) (2021)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [How are policy gradient methods affected by the limits of control?](https://mlsanity.com/paper/2206.06863/) (2022)
- [On the Sample Complexity of Stabilizing LTI Systems on a Single Trajectory](https://mlsanity.com/paper/2202.07187/) (2022)

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

- [Learning Stabilizing Policies via an Unstable Subspace Representation](https://mlsanity.com/paper/2505.01348/) (2025)

## Abstract (arXiv)

Inspired by the work of Tsiamis et al. citetsiamis2022learning, in this paper we study the statistical hardness of learning to stabilize linear time-invariant systems. Hardness is measured by the number of samples required to achieve a learning task with a given probability. The work in citetsiamis2022learning shows that there exist system classes that are hard to learn to stabilize with the core reason being the hardness of identification. Here we present a class of systems that can be easy to identify, thanks to a non-degenerate noise process that excites all modes, but the sample complexity of stabilization still increases exponentially with the system dimension. We tie this result to the hardness of co-stabilizability for this class of systems using ideas from robust control.