Finite-Time Identification of Linear Systems: Fundamental Limits and Optimal Algorithms

We investigate the linear system identification problem in the so-called fixed budget and fixed confidence settings. In the fixed budget setting, the learner aims at estimating the state transition matrix A from a random system trajectory of fixed length, whereas in the fixed confidence setting, the learner also controls the length of the observed trajectory - she can stop when she believes that enough information has been gathered. For both settings, we analyze the sample complexity in the probably approximately correct (PAC) framework defined as the length of the observed trajectory required to identify the system parameters with prescribed accuracy and confidence levels (e, d). In the fixed budget setting, we first establish problem-specific sample complexity lower bounds. We then present a finite-time analysis of the estimation error of the least-squares estimator (LSE) for stable systems, and show that in the high-accuracy regime, the sample complexity of the LSE matches our lower bounds. Our analysis of the LSE is sharper and easier to interpret than existing analyzes, and relies on novel concentration results for the covariates matrix. In the fixed confidence setting, in addition to the estimation objective, the learner also has to decide when to stop the collection of observations. The sample complexity then corresponds to the expected stopping time. For this setting, we also provide problem specific sample complexity lower bounds. We also propose a stopping rule which combined to the LSE enjoys a sample complexity that matches our lower bounds in the high-accuracy and high-confidence regime.