在线预测未知线性系统，实现对数级误差增长与多项式缩放。
Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction
- 基于条件分布推导最优预测策略，为未来输入、历史输入输出的线性函数。
- 算法达到与卡尔曼滤波相当的对数级后悔值，且不依赖固定失败概率。
- 后悔常数随预测时域呈多项式增长，由系统矩阵中特征值1的若尔当块决定。
本文研究未知线性随机系统的在线多步预测问题。利用条件分布理论，推导出最优预测策略为未来输入、历史输入和历史输出的线性函数。基于此表征，提出一种在线最小二乘算法来学习该策略，并分析其相对于最优模型预测器的后悔性能。结果表明，在多步设定下，该在线算法相对于最优卡尔曼滤波器可实现对数级后悔。此外，通过新的证明技术，建立了几乎必然的后悔界，无需依赖对足够大预测时域 $N$ 的固定失败概率假设。最后，分析还揭示：尽管后悔量在 $N$ 上保持对数增长，但其常数因子随预测时域 $H$ 呈多项式增长，其多项式阶数由系统矩阵中特征值1的最大若尔当块决定。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。