Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares
Provides the first logarithmic regret guarantee for online prediction in marginally stable systems under nonstochastic disturbances, addressing a key limitation of standard online learning methods.
The paper achieves logarithmic regret for online prediction in marginally stable linear dynamical systems with nonstochastic disturbances, using predictive hints to stabilize learning despite unbounded trajectories.
We study online prediction for marginally stable, partially observed linear dynamical systems under nonstochastic disturbances. Our objective is to minimize the cumulative squared prediction loss and compete with the best-in-hindsight Luenberger predictor. Standard online learning methods typically rely on bounded domains/gradients, and thus their guarantees may fail to deal with potentially unbounded trajectories in marginally stable systems. In this paper, we introduce an unconstrained online least squares method that stabilizes the learning process via tailored predictive hints. With model knowledge, we prove that hints constructed from any stabilizing Luenberger predictor render the hint residuals uniformly bounded, achieving logarithmic regret despite unbounded trajectory growth. We also discuss model-free prediction and introduce a simple universal hint for symmetric systems, under which logarithmic regret is maintained without model knowledge. Our results provide an adaptive, instance-wise optimal online predictor compared to classical fixed-gain observers under nonstochastic disturbances.