{"ID":2840917,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.12467","arxiv_id":"2511.12467","title":"Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction","abstract":"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.","short_abstract":"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 prop...","url_abs":"https://arxiv.org/abs/2511.12467","url_pdf":"https://arxiv.org/pdf/2511.12467v1","authors":"[\"Jiachen Qian\",\"Yang Zheng\"]","published":"2025-11-16T05:49:44Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"eess.SY\"]","methods":"[]","has_code":false}