The Complexity of Sequential Prediction in Dynamical Systems

Vinod Raman, Unique Subedi, Ambuj Tewari
Proceedings of the 7th Annual Learning for Dynamics \& Control Conference, PMLR 283:124-138, 2025.

Abstract

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 settings respectively. By doing so, we find that in the realizable setting, the total number of mistakes can grow according to \emph{any} increasing function of the time horizon $T$. In contrast, we show that in the agnostic setting under the commonly studied notion of Markovian regret, the only possible rates are $\Theta(T)$ and $\tilde{\Theta}(\sqrt{T})$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v283-raman25a, title = {The Complexity of Sequential Prediction in Dynamical Systems}, author = {Raman, Vinod and Subedi, Unique and Tewari, Ambuj}, booktitle = {Proceedings of the 7th Annual Learning for Dynamics \& Control Conference}, pages = {124--138}, year = {2025}, editor = {Ozay, Necmiye and Balzano, Laura and Panagou, Dimitra and Abate, Alessandro}, volume = {283}, series = {Proceedings of Machine Learning Research}, month = {04--06 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v283/main/assets/raman25a/raman25a.pdf}, url = {https://proceedings.mlr.press/v283/raman25a.html}, abstract = {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 settings respectively. By doing so, we find that in the realizable setting, the total number of mistakes can grow according to \emph{any} increasing function of the time horizon $T$. In contrast, we show that in the agnostic setting under the commonly studied notion of Markovian regret, the only possible rates are $\Theta(T)$ and $\tilde{\Theta}(\sqrt{T})$.} }
Endnote
%0 Conference Paper %T The Complexity of Sequential Prediction in Dynamical Systems %A Vinod Raman %A Unique Subedi %A Ambuj Tewari %B Proceedings of the 7th Annual Learning for Dynamics \& Control Conference %C Proceedings of Machine Learning Research %D 2025 %E Necmiye Ozay %E Laura Balzano %E Dimitra Panagou %E Alessandro Abate %F pmlr-v283-raman25a %I PMLR %P 124--138 %U https://proceedings.mlr.press/v283/raman25a.html %V 283 %X 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 settings respectively. By doing so, we find that in the realizable setting, the total number of mistakes can grow according to \emph{any} increasing function of the time horizon $T$. In contrast, we show that in the agnostic setting under the commonly studied notion of Markovian regret, the only possible rates are $\Theta(T)$ and $\tilde{\Theta}(\sqrt{T})$.
APA
Raman, V., Subedi, U. & Tewari, A.. (2025). The Complexity of Sequential Prediction in Dynamical Systems. Proceedings of the 7th Annual Learning for Dynamics \& Control Conference, in Proceedings of Machine Learning Research 283:124-138 Available from https://proceedings.mlr.press/v283/raman25a.html.

Related Material