Online Learning of the Kalman Filter With Logarithmic Regret

• 成果类型: Article
• 署名作者: Tsiamis, Anastasios; Pappas, George J.
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Pennsylvania
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3207670
• 发表日期: 2023
• 页码: 2774-2789
• 关键词: Kalman filters; Prediction algorithms; predictive models; stability analysis; System identification; Upper bound; regulators; Adaptive estimation; Kalman filter; online learning; Statistical learning

摘要

In this article, we consider the problem of predicting observations generated online by an unknown, partially observable linear system, which is driven by Gaussian noise. In the linear Gaussian setting, the optimal predictor in the mean square error sense is the celebrated Kalman filter, which can be explicitly computed when the system model is known. When the system model is unknown, we have to learn how to predict observations online based on finite data, suffering possibly a nonzero regret with respect to the Kalman filter's prediction. We show that it is possible to achieve a regret of the order of $\text{poly}\log (N)$ with high probability, where $N$ is the number of observations collected. This is achieved using an online least-squares algorithm, which exploits the approximately linear relation between future observations and past observations. The regret analysis is based on the stability properties of the Kalman filter, recent statistical tools for finite sample analysis of system identification, and classical results for the analysis of least-squares algorithms for time series. Our regret analysis can also be applied to other predictors, e.g., multiple step-ahead prediction, or prediction under exogenous inputs including closed-loop prediction. A fundamental technical contribution is that our bounds hold even for the class of nonexplosive systems (including marginally stable systems), which was not addressed before in the case of online prediction.