Title: High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems Show Chinese title

Title: 高努力，低收益：线性动态系统主动学习的基本限制

Abstract: 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. Show Chinese abstract

Abstract: 在本工作中，我们考虑在给定有限假设类的情况下识别未知线性动态系统的問題。 特别是，我们分析了激励输入对以高概率识别真实系统样本复杂度的影响。 为此，我们提出了样本复杂度下界，这些下界捕捉了所选激励输入的选择。 样本复杂度下界引出了一个系统理论条件，用于确定实验设计的潜在优势。 基于样本复杂度下界的分析，我们提出了一种针对所考虑设置的持续激励（PE）条件，然后我们利用该条件建立样本复杂度上界。 值得注意的是，\acs{PE}条件比无限假设类情况下的条件更弱，并允许模块化分析不同的激励输入。 关键的是，下界和上界在关键问题参数上的依赖关系相同。 最后，我们利用这些见解提出了一种主动学习算法，该算法根据当前估计值依次最优地激励系统，并为所提出的算法提供了样本复杂度保证。 最后的模拟结果展示了所提出算法的有效性。