# Online Learning of the Kalman Filter with Logarithmic Regret

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2020.

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

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Can Transformers Learn Optimal Filtering for Unknown Systems?](https://mlsanity.com/paper/2308.08536/) (2023)
- [Kalman Filter for Online Classification of Non-Stationary Data](https://mlsanity.com/paper/2306.08448/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Fairness in Forecasting of Observations of Linear Dynamical Systems](https://mlsanity.com/paper/2209.05274/) (2022)
- [Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret](https://mlsanity.com/paper/2505.08982/) (2025)
- [The Fragility of Noise Estimation in Kalman Filter: Optimization Can Handle Model-Misspecification](https://mlsanity.com/paper/2104.02372/) (2021)
- [Learning and Concentration for High Dimensional Linear Gaussians: an Invariant Subspace Approach](https://mlsanity.com/paper/2304.01708/) (2023)
- [From Spectral Theorem to Statistical Independence with Application to System Identification](https://mlsanity.com/paper/2310.10523/) (2023)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)
- [Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction](https://mlsanity.com/paper/2511.12467/) (2025)
- [The Power of Second Order Methods for Sequence Preconditioning](https://mlsanity.com/paper/2605.08390/) (2026)
- [Spectral Statistics of the Sample Covariance Matrix for High Dimensional Linear Gaussians](https://mlsanity.com/paper/2312.05794/) (2023)
- [Differentiable Adaptive Kalman Filtering via Optimal Transport](https://mlsanity.com/paper/2508.07037/) (2025)
- [Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares](https://mlsanity.com/paper/2605.04364/) (2026)
- [A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems](https://mlsanity.com/paper/2607.02050/) (2026)

## Abstract (arXiv)

In this paper, we consider the problem of predicting observations generated online by an unknown, partially observed linear system, which is driven by stochastic noise. For such systems the optimal predictor in the mean square 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 non-zero regret with respect to the Kalman filter's prediction. We show that it is possible to achieve a regret of the order of polylog(N) with high probability, where N is the number of observations collected. Our work is the first to provide logarithmic regret guarantees for the widely used Kalman filter. 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 for state prediction of the hidden state, in the case of unknown noise statistics but known state-space basis. A fundamental technical contribution is that our bounds hold even for the class of non-explosive systems, which includes the class of marginally stable systems, which was an open problem for the case of online prediction under stochastic noise.