![[2602.16236] Online Prediction of Stochastic Sequences with High Probability Regret Bounds](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.16236] Online Prediction of Stochastic Sequences with High Probability Regret Bounds
Summary
This paper explores high-probability regret bounds for online prediction of stochastic sequences, proposing new bounds that improve upon existing expectation-based limits.
Why It Matters
Understanding high-probability regret bounds is crucial for advancing machine learning models that predict stochastic sequences. This research enhances theoretical foundations and practical applications in areas like algorithm design and predictive modeling, making it relevant for researchers and practitioners in machine learning.
Key Takeaways
- Introduces high-probability regret bounds for stochastic sequence prediction.
- Proposes a convergence rate of O(T^{-1/2} δ^{-1/2}) compared to existing bounds.
- Demonstrates that improving the exponent of δ requires additional assumptions.
- Enhances understanding of universal prediction in machine learning.
- Provides a theoretical basis for future research in prediction algorithms.
Computer Science > Machine Learning arXiv:2602.16236 (cs) [Submitted on 18 Feb 2026] Title:Online Prediction of Stochastic Sequences with High Probability Regret Bounds Authors:Matthias Frey, Jonathan H. Manton, Jingge Zhu View a PDF of the paper titled Online Prediction of Stochastic Sequences with High Probability Regret Bounds, by Matthias Frey and Jonathan H. Manton and Jingge Zhu View PDF Abstract:We revisit the classical problem of universal prediction of stochastic sequences with a finite time horizon $T$ known to the learner. The question we investigate is whether it is possible to derive vanishing regret bounds that hold with high probability, complementing existing bounds from the literature that hold in expectation. We propose such high-probability bounds which have a very similar form as the prior expectation bounds. For the case of universal prediction of a stochastic process over a countable alphabet, our bound states a convergence rate of $\mathcal{O}(T^{-1/2} \delta^{-1/2})$ with probability as least $1-\delta$ compared to prior known in-expectation bounds of the order $\mathcal{O}(T^{-1/2})$. We also propose an impossibility result which proves that it is not possible to improve the exponent of $\delta$ in a bound of the same form without making additional assumptions. Comments: Subjects: Machine Learning (cs.LG); Information Theory (cs.IT) Cite as: arXiv:2602.16236 [cs.LG] (or arXiv:2602.16236v1 [cs.LG] for this version) https://doi.org/10.48550/arXiv...
