# Online Prediction of Stochastic Sequences with High Probability Regret Bounds

arXiv: https://arxiv.org/abs/2602.16236 · HTML: https://mlsanity.com/paper/2602.16236/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 7 of 7)

- [On Adversarial Robustness of Trajectory Prediction for Autonomous Vehicles](https://mlsanity.com/paper/2201.05057/) (2022)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [DANSE: Data-driven Non-linear State Estimation of Model-free Process in Unsupervised Learning Setup](https://mlsanity.com/paper/2306.03897/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023)

## Abstract (arXiv)

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 O(T-1/2 δ-1/2) with probability as least 1-δ compared to prior known in-expectation bounds of the order O(T-1/2). We also propose an impossibility result which proves that it is not possible to improve the exponent of δ in a bound of the same form without making additional assumptions.