Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction
This addresses prediction accuracy for control or forecasting applications, but it is incremental as it builds on existing online learning and Kalman filter frameworks.
The paper tackles online multi-step-ahead prediction for unknown linear stochastic systems by proposing an online least-squares algorithm, achieving logarithmic regret relative to the optimal Kalman filter, with the regret constant growing polynomially with the prediction horizon based on system matrix properties.
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.