# Sample Complexity Bounds for Linear System Identification from a Finite Set

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 17 Sep 2024.

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

- [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)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [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)
- [A Tutorial on Concentration Bounds for System Identification](https://mlsanity.com/paper/1906.11395/) (2019)
- [Minimax Adaptive Control for a Finite Set of Linear Systems](https://mlsanity.com/paper/2011.10814/) (2020)

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

- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems](https://mlsanity.com/paper/2509.11907/) (2025)
- [Frequency Response Identification of Low-Order Systems: Finite-Sample Analysis](https://mlsanity.com/paper/2508.17142/) (2025)

## Abstract (arXiv)

This paper considers a finite sample perspective on the problem of identifying an LTI system from a finite set of possible systems using trajectory data. To this end, we use the maximum likelihood estimator to identify the true system and provide an upper bound for its sample complexity. Crucially, the derived bound does not rely on a potentially restrictive stability assumption. Additionally, we leverage tools from information theory to provide a lower bound to the sample complexity that holds independently of the used estimator. The derived sample complexity bounds are analyzed analytically and numerically.