Online Prediction of Stochastic Sequences with High Probability Regret Bounds

Conference: ICLR 2026
arXiv: 2602.16236
Code: None
Area: Reinforcement Learning / Online Learning Theory
Keywords: Online prediction, stochastic sequences, high-probability regret bounds, universal prediction, countable alphabets

TL;DR

This work revisits the classic problem of universal prediction for stochastic sequences under a finite time horizon \(T\). It provides the first vanishing regret bound that holds with high probability (in the form of \(O(T^{-1/2}\delta^{-1/2})\)), which is highly consistent with existing expected regret bounds of \(O(T^{-1/2})\). Furthermore, it proves that the exponent of \(\delta\) cannot be improved without additional assumptions.

Background & Motivation

Universal prediction is a classic problem in information theory and online learning: given a sequence generated by an unknown stochastic process, the learner's goal is to perform optimal prediction for each step's next observation, making the cumulative loss (regret) as close as possible to an "oracle" strategy that knows the true distribution.

In existing literature, universal prediction regret bounds are primarily provided in the form of expectation. For example, for stochastic processes on countable alphabets, classic results provide an expected regret convergence rate of \(O(T^{-1/2})\). However, expected bounds have inherent limitations:

• Uncontrollable tail risk: Expected bounds only guarantee good "average" performance and do not exclude extreme regret on certain realization paths (which may occur with non-negligible probability).
• Unsuitable for risk-sensitive scenarios: In safety-critical applications or financial risk control, stronger high-probability guarantees are required—specifically, that regret will not exceed a certain threshold except in extremely low-probability events.
• Theoretical gap: Whether it is possible to upgrade expected bounds to high-probability bounds without significantly sacrificing the convergence rate remained an unsolved question.

The core contribution of this paper is answering this question: Yes—and it provides a high-probability bound formally consistent with the expected bound, at the cost of only an additional \(\delta^{-1/2}\) factor.

Method

Overall Architecture

Within a known finite time horizon \(T\), the learner sequentially observes a sequence \(X_1,\dots,X_T\) generated by an unknown stationary ergodic process \(P\) (where the alphabet \(\mathcal{X}\) is a countable set, potentially infinitely countable). At each step, the learner uses \(\hat{q}_t(\cdot\mid X^{t-1})\) to predict the conditional distribution of the next observation. Performance is measured by the cumulative regret in the form of log-loss/KL divergence: \(R_T=\sum_{t=1}^T D_{\text{KL}}(p_t\,\|\,\hat{q}_t)\), where \(p_t\) is the true conditional distribution. The entire work is dedicated to elevating this regret from "small in expectation" to "small with high probability" through mathematical analysis without involving training or optimization: first, a high-probability upper bound is derived using martingale concentration; second, an adversarial construction is used to prove the \(\delta\) exponent is unimprovable; finally, the conclusions are extended from finite alphabets to general countable alphabets.

Key Designs

1. High-probability upper bound: Replacing "Average Goodness" with "Reliable Goodness" via Martingale Concentration

Existing literature only provides an expected regret bound \(E[R_T]=O(\sqrt{T})\) (normalized as \(E[R_T/T]=O(T^{-1/2})\)) for universal prediction on countable alphabets. A small expectation does not rule out very large \(R_T\) on a few paths. For risk-sensitive scenarios, tail control like \(P(R_T/T\ge\epsilon)\le\delta\) is necessary. A naive application of Markov's inequality to the expected bound would only yield \(\epsilon=O(T^{-1/2}\delta^{-1})\), where the \(\delta\) exponent stops at \(-1\), making the bound loose for high-confidence requirements (small \(\delta\)). The paper instead decomposes the cumulative regret into a martingale sequence and employs mixing properties alongside Azuma-Hoeffding-type concentration inequalities to control terms individually, improving the exponent to \(-1/2\):

\[P\!\left(R_T/T \ge O(T^{-1/2}\delta^{-1/2})\right)\le\delta.\]

This means that with probability at least \(1-\delta\), the normalized regret does not exceed \(O(T^{-1/2}\delta^{-1/2})\). This step, while seemingly a minor modification, is the core technical achievement distinguishing the result from the trivial Markov inference.

2. Matching lower bound: Adversarial construction proving \(\delta^{-1/2}\) is the inherent limit of the problem

An upper bound alone does not confirm tightness—is \(\delta^{-1/2}\) a result of imprecise analysis or an inherent cost? Without additional assumptions (such as stronger mixing conditions or exponential moment conditions), the authors construct adversarial instances to prove that no predictor can suppress the \(\delta\) exponent to anything better than \(-1/2\). The root cause lies in the inherent variability of stochastic processes: unlike the i.i.d. setting which allows for stronger concentration, the inherent fluctuations of ergodic processes naturally limit high-probability concentration. The upper and lower bounds thus match exactly regarding \(\delta\) dependence.

3. Extension to countable (including infinitely countable) alphabets: Removing the "Finite Alphabet" assumption

If the results only held for finite alphabets, their applicability would be significantly limited. Compared to the finite case, countable alphabets involve richer model classes and require handling uniform convergence in infinite-dimensional distribution spaces. The authors ensure both the martingale concentration and the lower bound construction directly cover this more general setting, allowing the final bound to remain consistent with the finite alphabet case without relying on the convenience of a finite alphabet.

Loss & Training

This is a purely theoretical paper with no training process. The core is mathematical analysis rather than optimization. The prediction loss is the standard log-loss, and regret is measured by KL divergence. High-probability analysis relies on martingale concentration inequalities, while the characterization of stochastic processes utilizes information-theoretic tools such as mutual information and conditional entropy.

Key Experimental Results

Main Results

As this is a pure theory contribution, the primary results are in the form of theorems and propositions:

Result Type	Bound Form	Prob. Guarantee	Alphabet	Remarks
Prev. Expected Bound	\(E[R_T/T] = O(T^{-1/2})\)	Expectation	Countable	Known in literature
Ours (High Prob.)	\(R_T/T \leq O(T^{-1/2}\delta^{-1/2})\)	\(\geq 1-\delta\)	Countable	New result
Markov Inequality	\(R_T/T \leq O(T^{-1/2}\delta^{-1})\)	\(\geq 1-\delta\)	—	Trivial conversion
Ours (Lower Bound)	\(\delta^{-1/2}\) exponent unimprovable	—	—	Matches upper bound

Ablation Study

Method/Condition	δ Exponent	Optimal?	Description
Expected Bound + Markov	\(-1\)	No	Too coarse of a conversion
Ours (High-Prob Analysis)	\(-1/2\)	Yes	Improved via refined analysis
Strengthened Assumptions (e.g., strong mixing)	Potentially better	Condition-dependent	Requires extra assumptions

Key Findings

1. The cost of moving from expectation to high probability is a square root: Moving from \(O(T^{-1/2})\) to \(O(T^{-1/2}\delta^{-1/2})\) requires an additional \(\delta^{-1/2}\) factor that is both necessary and sufficient.
2. Fundamental cause of impossibility results: The inherent variability of stochastic processes limits high-probability concentration, unlike the stronger concentration phenomena observed in i.i.d. settings.
3. Comparison with finite alphabet results: Results for countable alphabets are formally identical to those for finite alphabets, though the proof techniques are more complex.

Highlights & Insights

1. Extremely Concise Main Theorem: The \(O(T^{-1/2}\delta^{-1/2})\) bound is highly consistent with the expected bound \(O(T^{-1/2})\), where the \(\delta^{-1/2}\) factor elegantly captures the "cost of probabilistic assurance."
2. Matching Upper and Lower Bounds: Not only is a high-probability bound provided, but its optimality is proven via an impossibility result, which is rare and valuable in theoretical research.
3. Revisiting a Classic Problem: Providing a perfect answer to a natural, unanswered question in a field with extensive existing literature demonstrates deep theoretical insight.
4. Bridging Research Traditions: Effectively combines universal prediction from information theory with high-probability analysis from online learning.

Limitations & Future Work

1. Requirement of Knowing \(T\): The learner needs to know the time horizon \(T\) in advance; extensions to anytime settings (valid for any \(t\)) are worth exploring.
2. Stationarity Assumption: Generalization to non-stationary or adversarial environments is an important direction.
3. Practical Algorithm Efficiency: Whether the theoretical results correspond to computationally efficient prediction algorithms requires further discussion.
4. General Loss Functions: This work focuses on log-loss/KL divergence; whether results generalize to other losses (e.g., squared loss, absolute loss) remains to be studied.
5. Finite Sample Constants: The impact of constants hidden by \(O(\cdot)\) notation on practical applications deserves analysis.

Related Work & Insights

• Rissanen's Stochastic Complexity Theory: The deep connection between universal prediction and data compression; the regret bound here can be interpreted as a bound on code length.
• Coverage & Online Learning: Techniques like PAC-Bayes bounds and martingale methods in online learning provided key technical tools.
• Cesa-Bianchi & Lugosi's Online Convex Optimization: This work migrates high-probability analysis techniques from that field to the universal prediction problem.
• The impossibility result techniques in this paper may inspire lower bound proofs in other online learning problems.

Rating

• Novelty: ⭐⭐⭐⭐ — New answers to a classic problem; technically non-trivial even if the concept is focused.
• Experimental Thoroughness: ⭐⭐⭐ — Purely theoretical work with no experiments, but the theorems themselves serve as the "evidence."
• Writing Quality: ⭐⭐⭐⭐ — High-level clarity required for presenting complex theoretical proofs.
• Value: ⭐⭐⭐⭐ — Fills a theoretical gap; matching upper and lower bounds provide mathematical perfection.

Related Papers

• [ICML 2026] Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
• [ICLR 2026] Towards High Data Efficiency in Reinforcement Learning with Verifiable Reward
• [ICLR 2026] Solving General-Utility Markov Decision Processes in the Single-Trial Regime with Online Planning
• [ICLR 2026] Post-training Large Language Models for Diverse High-Quality Responses
• [NeurIPS 2025] Bandit and Delayed Feedback in Online Structured Prediction