Paper ID: 2402.06614

The Complexity of Sequential Prediction in Dynamical Systems

Vinod Raman, Unique Subedi, Ambuj Tewari

We study the problem of learning to predict the next state of a dynamical system when the underlying evolution function is unknown. Unlike previous work, we place no parametric assumptions on the dynamical system, and study the problem from a learning theory perspective. We define new combinatorial measures and dimensions and show that they quantify the optimal mistake and regret bounds in the realizable and agnostic setting respectively.

Submitted: Feb 9, 2024