High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems
This work addresses the challenge of efficient system identification for researchers in control theory and machine learning, offering incremental improvements in active learning for linear dynamical systems.
The authors tackled the problem of identifying unknown linear dynamical systems with a finite hypothesis class, establishing sample complexity lower bounds that depend on the excitation input and proposing an active learning algorithm with matching upper bounds. They demonstrated the algorithm's effectiveness through simulations.
In this work, we consider the problem of identifying an unknown linear dynamical system given a finite hypothesis class. In particular, we analyze the effect of the excitation input on the sample complexity of identifying the true system with high probability. To this end, we present sample complexity lower bounds that capture the choice of the selected excitation input. The sample complexity lower bound gives rise to a system theoretic condition to determine the potential benefit of experiment design. Informed by the analysis of the sample complexity lower bound, we propose a persistent excitation (PE) condition tailored to the considered setting, which we then use to establish sample complexity upper bounds. Notably, the \acs{PE} condition is weaker than in the case of an infinite hypothesis class and allows analyzing different excitation inputs modularly. Crucially, the lower and upper bounds share the same dependency on key problem parameters. Finally, we leverage these insights to propose an active learning algorithm that sequentially excites the system optimally with respect to the current estimate, and provide sample complexity guarantees for the presented algorithm. Concluding simulations showcase the effectiveness of the proposed algorithm.