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.