# Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 16 Nov 2025.

## Builds on (most cited first, 13 of 13)

- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [Long Short-Term Memory Kalman Filters:Recurrent Neural Estimators for Pose Regularization](https://mlsanity.com/paper/1708.01885/) (2017)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [Learning Accurate Long-term Dynamics for Model-based Reinforcement Learning](https://mlsanity.com/paper/2012.09156/) (2020)
- [SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory](https://mlsanity.com/paper/2010.05899/) (2020)
- [Learning the Kalman Filter with Fine-Grained Sample Complexity](https://mlsanity.com/paper/2301.12624/) (2023)
- [DeeP-LCC: Data-EnablEd Predictive Leading Cruise Control in Mixed Traffic Flow](https://mlsanity.com/paper/2203.10639/) (2022)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Learning with Imperfect Models: When Multi-step Prediction Mitigates Compounding Error](https://mlsanity.com/paper/2504.01766/) (2025)
- [Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret](https://mlsanity.com/paper/2505.08982/) (2025)

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

- [Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares](https://mlsanity.com/paper/2605.04364/) (2026)

## Abstract (arXiv)

This letter studies the problem of online multi-step-ahead prediction for unknown linear stochastic systems. Using conditional distribution theory, we derive an optimal parameterization of the prediction policy as a linear function of future inputs, past inputs, and past outputs. Based on this characterization, we propose an online least-squares algorithm to learn the policy and analyze its regret relative to the optimal model-based predictor. We show that the online algorithm achieves logarithmic regret with respect to the optimal Kalman filter in the multi-step setting. Furthermore, with new proof techniques, we establish an almost-sure regret bound that does not rely on fixed failure probabilities for sufficiently large horizons N. Finally, our analysis also reveals that, while the regret remains logarithmic in N, its constant factor grows polynomially with the prediction horizon H, with the polynomial order set by the largest Jordan block of eigenvalue 1 in the system matrix.