Online Prediction of Stochastic Sequences with High Probability Regret Bounds
Authors: Matthias Frey
Jonathan H. Manton
Jingge Zhu
Venue: ICLR 2026 Poster (2026)
Keywords: online prediction
learning theory
high-probability bound
regret
stochastic sequences
Primary area: learning theory
TL;DR: We propose high-probability regret bounds for online prediction of stochastic sequences.

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.

Published as a conference paper at ICLR 2026
ONLINE PREDICTION OF STOCHASTIC SEQUENCES WITH HIGH PROBABILITY REGRET BOUNDS
Matthias Frey, Jonathan H. Manton, and Jingge Zhu Department of Electrical and Electronic Engineering, The University of Melbourne
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 very similar form the prior expectation bounds. For the case of universal prediction of stochastic process over a countable alphabet, our bound states a convergence rate of O(T-1/28-11)) with probability least - 8 compared to prior known in-expectation bounds of the order (/23) We also propose 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.
INTRODUCTION
classical question in online learning, information theory, and several related fields is how to make predictions about the outcome Z₁ of process time given some knowledge of the past outcomes
Zi...., Z. Its appearance in the early works by [Shannon| [955]; Bellman (1954); Hannan (197))
reflects the central role plays in several pure and applied research areas of mathematics, computer science, and engineering. This basic question comes in many variations such as: (i) The process (Z,) can follow a fixed, but unknown probability distribution, which even includes the possibility that it is chosen adversarially given the learner's strategy (Merhay Feder 1998). (ii) The learner can have access to the advice of experts (Weissman & Merhav (000)) or other side information about the process, or it can make its predictions without access to such information (Bellman 1954). (iii) The learner can make its predictions only for Zi..... Zr, where T can be a fixed time horizon known to the learner (Bellman 1954) a random stopping time (Morvai & Weiss 2007); or the learner can make predictions indefinitely for (ee) (Gyorfi et al. 1999). (iv) The learner can have access only past outcomes Z Zi...., Ze-1 (Bellman 1954). it have access to infinite past (Ze 1-- )== (Gyorfi et al. 1999)
it can be deterministic and unknown,
In this paper, we focus on a particular one of these scenarios, which is, however, still general enough to be considered a fundamental question. Namely, we assume that the learner makes predictions about a random process Zi,..., Zr where T is a deterministic time horizon known to the learner. We further assume that Zz...., Zr follows joint probability distribution P which does not need to have identical or independent components, but is not influenced by the predictions (B.)² the learner makes each time instant / based on full knowledge of Zi,.... Zt-1 (we use the common convention in this paper that Zi.... Zo is the empty sequence). The quality of the learner's decisions measured in terms of a loss É(B,, Z,). The main quantity of interest is the regret of the learner in hindsight, i..... the difference between the cumulative loss incurred by the learner and the cumulative loss incurred by a prediction strategy that would have been optimal given full knowledge of P. This scenario has been proposed in this form by Merhav & Feder (1998) and solved in expectation: that is, the authors analyze the expectation the learner's 's regret. To the best of our knowledge, our paper is the first that studies high-probability bounds of the learner's regret for this particular scenario, i.c., we propose bounds that the learner's 's regret surpasses only with a small probability 8. Such grobbbrobabylity bounds hold enormous promise for practical applications where reliability is key, such as accident prediction in air traffic control (Amin et al. 2024). trajectory prediction in autonomous driving (Zhang et al. )022), and sepsis prediction in health care (Boussina et al., 2024).

---

Published as a conference paper at ICLR 2026
The contribution of this paper can be summarized following:
For the problem of universal prediction of stochastic sequences under general. bounded loss, we propose high-probability regret bound (Theorem 4 that complements existing in-expectation bounds in the literature. Our high-probability bound matches the prior expectation bound in terms of convergence order in the time horizon T'. To the best of our knowledge, figh-probability bounds for this scenario have not appeared in previous works.
We show with an impossibility result (Theorem 55) that our proposed piobabbbbybllity regret bound cannot be significantly improved regarding the order of the permissible error probability that appears in the bound without making additional assumptions.
In contrast with Merhav & Feder 1998), our results do not necessarily require that the underlying spaces are finite. Instead, we use much milder technical assumptions.
The remainder of the paper is structured as follows: In Section 2 we survey relevant prior works on the topic of prediction of sequences. In Section B introduce the universal prediction problem and give high-level overview of our high-probabilig result and compare it to the most closely related expectation bound found in prior works. We fully formalize a simplified version of the problem. which we call the mismatched prediction problem, in Section 4 and introduce all notations and definitions that are necessary to state and discuss our results in Section [S] In Section [6] we show how our result on mismatched prediction can be applied in conjunction with known techniques from the literature to yield high-prohe probbabiiyy convergence rates for the universal prediction problem. In Section 7 we describe the numerical experiments we have run to illustrate the promise of the schemes studied in this paper for practical applications, and we report on their results. The paper is concluded in Section & with a discussion of limitations and future research directions.
2 RELATED WORKS
The wider question of prediction of sequences is classical research area. The distinct but related bandit problem has first been studied by Thompson (1933) (see, e.g.. [attimore & Szepesvári (2020) for overview of more recent developments). A scenario that is very closely related the one we study in this paper was to the best of our knowledge first described by [Shannon [15I].. He posed the question of how well a stochastic process could be predicted given past observations and related the prediction quality to an information quantity, namely what is now called Shannon entropy. He used this connection to estimate the entropy contained in expressions in the English language based on how accurately human test subject would be able to predict the next letter in an incomplete sentence. The first works concerned with strategies for optimum prediction of future realizations of a sequence were Bellman (1954); Hannan (1957) for the case of a deterministic process unknown to the learner (and potentially selected by an adversary with knowledge of the learner's 's strategy). The further development of the various flavors of prediction of processes throughout the remainder of the 20th century is summarized by MMerha & Feder (1998) which is also the earliest work we are aware of that proposes the exact version of the problem which we study in this work (but provides bounds only for expected regret).
Prediction with expert advice. In this version of the problem, the learner has access advice given by so-called experts, where at each time step, it can decide which expert's ' advice to follow. The regret in this case is typically the difference between the loss incurred by the learner and the loss incurred by the best available expert in hindsight. Examples of works considering this version of the problem include Deesa-Bianchi & Lugosi| (200T): Weissman & Merhav| (200T): Wu et al.) (2023b); [Hanneke et al. (203)) for deterministic sequences and Weissman & Merhav (2004) for stochastic sequences.
Prediction deterministic sequences. The most prevalent version of the sequential prediction problem does not make any stochastic assumptions about the underlying process that has to be predicted and studies bounds on the worst-case regret. That is, the predicted sequence is assumed deterministic and could in principle be chosen by adversary with knowledge of the leamne's s prediction strategy. Early works on this include Bellman (1954); Hannan (1957). the problem is also studied and surveyed by MMrrha & Feder (1998). and very comprchensive treatment can be found in Dasa-Bianccii & Lugosi| (2006). More recent developments include Aberneetyy et al. (2012);
Hanneke et al. (2023): Cutkosky & Mhammedi (0244)
2

---

Published as a conference paper at ICLR 2026
It is worth noting that an unknown deterministic sequence can be viewed as a stochastic sequence that follows an unknown Dirac distribution. So results for the prediction of stochastic sequences can potentially be relevant for deterministic sequences as well. However, if the underlying sequence follows a Dirac distribution, this means in particular that if the learner's predictions are deterministic conditioned on the part of the sequence that has already been observed (as is the case in the strategy analyzed in this paper), the instantaneous regret is almost surely equal to the average regret. Hence, our ghgp-prbbbbility results do not offer any advantage over the known bounds in expectation in the case of deterministic sequences.
Prediction of stochastic sequences. Under the assumptions of access to an infinite past and stationarity, ergodicity, or Markovness of the underlying process, this problem was studied by AAgget Weiss (007) for a survey of more results along these lines). The assumption of access to an infinite past was lifted by Morvai & Weiss (201T) who proved almost sure convergence of regret quantities, but did not provide quantitative high-probabiiltyy bounds. Bounds on expected regret were studied by Merhav & Feder (1998). Hutter
Cyorfi et al. (1999): Gyorfi & Ottuesak (2007) (see |Morvai (see|Morvai
(2003). Watanabe & Roos (2135) (under an i.i.d. assumption), and Wu et al. (2023a) (with the additional complication that the underlying process may change its distribution a certain number of times). High- peesh-rrbbbbiityy bounds for stochastic scenarios have been investigated by Mehtal (2017) (under the assumption of log-coneave loss and an i.i.d. underlying process) and (van der Hoeven eet al. (2023) (for an online-to-batch conversion scenario, i.e., it is shown that high-probabilityy bounds on regret can imply high-probability bounds on generalization error of a batch version of the learner). The very recent works Ghosh et al. (2024); Qin et al. (2025) deal with a signal processing application of the sequential prediction problem and employ fecurrent neural networks (RNNs) in their predictors.
To the best of our knowledge, there are no prior works that study high-probabiligg bounds for the regret in prediction of non-i.i.d, stochastic sequences in the absence of expert advice.
3 THE UNIVERSAL AND THE MISMATCHED PREDICTION PROBLEMS
In the universal prediction problem with stochastic sequences (Merhav & Feder 1998 Section I-A), the learner observes the initial part Zi...., ,, ZT-1 of some sequence (Z)...., ZT) E g which follows joint probability distribution P. After it makes prediction B, E B, the next realization Z, is revealed, and the learner incurs a loss E B(B Z,). The objective is to find a prediction strategy which is universal in the sense that it does not depend on P (and hence requires no knowledge of it) but still approaches - for large enough T - the performance of a strategy that is optimized for P. The performance is evaluated in the following way: we consider the difference between the average loss the learner's 's strategy incurs up to time I' and the average loss that a strategy optimized for P incurs up to time T. This difference is called the regret and denoted A (for a formal definition see (4) and (5) below). A universal strategy will have vanishing A as T grows, regardless of what distribution P (within a certain known class of probability distributions) the sequence Zz...., Zr follows.
It is often assumed that P = Pe for some O E θ where θ is a measurable space and (Pa)ege is parametrized family of probability distributions known to the learner. The idea case very little is known about P is to use family (Po)oee that is so large that it will contain (almost) all P that are reasonably possible. One example of theoretical interest is investigated by Hutter (2003): let θ be the set of all programs on universal Turing machine that compute probability distribution on n to arbitrary precision, and let Po be the distribution computed by 0 E O. Then, any prediction strategy that is universal for (Po (Po)see guarantees vanishing regret for every sequence Zi.... that follows probability distribution which is computable (in the sense that there exists a program on a universal Turing machine that computes it to arbitrary precision). This is not directly applicable to practical problems, of course, but it is a very powerful theoretical illustration of a basic idea that can also be useful in practice: based on very limited knowledge of properties of P. make the family (Po)oeo so large that it can be guaranteed it contains P. We do not make a contribution about how (Po)eee can be chosen and how such a family induces a universal prediction strategy, but since this is essential to understand the consequences of our results, we briefly survey the literature on this in Section O
We next give an idea of the nature of the implications of our results by informally stating prior result on universal prediction and one of the consequences of our technical results.
Theorem (Merhav& & Feder (1998); Hutter (2003). If Z is countable, there a strategy which is universal for all computable P in the sense that we have EA S 001VVT.
3

---

Published as a conference paper at ICLR 2026
While this is the best rate result for general bounded losses the best of our knowledge, it is for instance possible in the case of self-information loss to get the better rate (1/TT) (Merhav & Feder 1998:
Hutter 2003).
Our main results imply the following pee--pobbbblliyy version of Theorem !
Theorem 2. If is countable, there is a strategy which is universal for all computable P in the sense that for every 8 (0, 1). we have P 0(1/VT))
2 21-6.
Theorem follows from 18) of Theorem 4 proposed in Section S in conjunction with the considera- tions by Hutter (2003) sketched above and discussed in more detail in Section The simplifying assumption that Z is countable can be replaced by alternative assumptions. Therefore, we have similar results for some cases in which
a general measurable space. However, this comes at a small cost in terms of order of convergence. For details, see Dection|Jand Table contained therein.
In the technical problem statement in Section and our main results Section 5 we consider a simplified problem which we call mismatched prediction. In this scenario, we assume that the learner's strategy can be mathematically represented as a probability measure Q (which is mismatched to the problem in the sense that it is possibly different from P, but is still "reasonable" approximation of it) and analyze the regret incurred by such strategies. This is the same stepping stone used by Merhay & Feder (1998) to tackle the universal prediction problem, and results for the universal prediction problem follow from results for mismatched prediction via known results from the literature.
Specifically, the distribution Q is usually chosen parametrized family of all distributions that are "reasonably possible" and w is probability distri- bution on O does need to accurately represent some prior knowledge of the distribution of w. in fact is sufficient for Theorems I Therefore, it is common in practice to choose w as uniform distribution when possible. In Section we return to the universal prediction problem, formalize it fully, and explain how results for universal prediction follow from results for mismatched prediction.
Se Pow(dd), where (Po)oee is
and [ to hold that P Pe for some 0 in the support of O
NOTATIONS AND TECHNICAL STATEMENT OF THE MISMATCHED PREDICTION PROBLEM
Let (2, (P be probability space and .,.....2 Zr be (not necessarily independent) random variables each taking values in a measurable space (Z, G). The joint distribution of Zi...., Zr is described by a probability measure P on (2 "GOT) where geT
& 6) ... e 9 denotes the T}. we denote with Pr the
product r-algebra with T copies o as factors. For T S [T] marginal distribution of (Zi)eT. We assume that for every t E [7] (1), the distribution P admits
Markov kernel k(O) z x g
+ [0, 1] such that for all GI,...,CC. G. Eg
(G G.)
KP ( (Zl Zt-1 G.)- 1z.
(I)
GIX-XG,-1
We further adopt the convention k.O) := P1 and the convention that integration over a tuple of length 0 returns the integrand, that (1) also holds for t= 1.
(Prediction of stochastic sequences). The prediction problem P (2, 9), P. (B. () is characterized by the time horizon T E N, a measurable space (2,9), a probability measure P on (2T, . which describes the joint distribution of a tuple Zi...., Zr of random variables, a measurable space (B,H) (the prediction domain), and measurable loss function &. B x Z + [0, L), where L E 00). The learner's 's policy b (be)tet2 consists of measurable (deterministic) functions by
Problem
Nature first draws a tuple Zi....,
.i....,,yy Zr randomly from the distribution P. At each time t E [T]:
The learner makes a prediction which is determined by its policy and the past observations of the process as B, := by (o,
All subsets of the real numbers are implicitly understood to be endowed with the standard Borel r-algebra unless otherwise specified.
4

---

Published as a conference paper at ICLR 2026
Nature reveals Z₁ to the learner and the learner incurs the loss BBB,, Zi).
We will compare the learner's policy to one that is optimal in the sense that it minimizes the expected loss at each time instant under full knowledge of the underlying distribution P. That is, an optimal prediction at time instant / any measurable function bū 2 - such that
by (Z1..... 2x-1) E arg min (p(b Z1 21. - 21-1:
(2)
DEB
where Ep(-IZı 21,...; Z 2+-1)
denotes expectation with respect to the measure for t the function b7 takes the tuple , 20 as an argument which by convention we regard as an empty tuple and denote as 0.
K ( (21, 21-1. )) Note that according
In this section, study mismatched prediction problem where the learner is not assumed to know P. Instead, we assume that the learner knows some distribution Q which is assumed to be "sufficiently similar to P. For Q, make the same technical assumption regarding disintegration into kernels
as we do for P. That is, we assume that Q also admits Markov kernels K 2 x & + [0, 1] so that the analog ( holds. In this paper, we study learner's policies that are optimal with regard to Q. That is, we study policy that satisfies, for each t [T']. that
by (21, 21-1) arg min Eq (E(b, Z1 21,.... Ze-1 21-1).
BEB
Remark 1. Restricting the analysis algorithms that can be represented (3) is less restrictive than it might seem. To illustrate this, we provide detailed arguments in Appendix A that in the following cases, every possible learner's policy has a representation of the form (3)
1. B = 2 is a finie set and the loss function E(b, 2) == 1byz is the classification loss.
2. Z is finite, B is the space of all probability mass functions on Z and the loss function is the self-information loss {(b, 2) == log(b(z)).
The results in this paper hold under the assumption that measurable maps (bz) (b)))(()) and (be (e()) which satisfy (2) and (3) exist; implicitly fix suitable choices of these maps. In Appendix [B] we show that this is indeed the case as long as mild technical assumptions on (B, X) and é are satisfied.
If the learner executes the policy given in (3), this will yield three random processes embedded in the probability space (2, P): the sequentially observed process Zı,..., Zr distributed according the sequence B1 == bj (0), BT == (Z ZT-1) of predictions made by the learner, and the sequence Bi := bj (0), optimal at each time instant [T] had the learner known P. In the following we use EE (without an index) to denote expectation with respect to P.
B7 == by (Z..... ZT-1) of predictions that would have been
In this work, we analyze the regret that incurred by the policy given 3 The cumulative regret after t rounds is defined as
A, Σ (M(Br, E(B,,, Zz)):
(4)
P=1
and our main quantity of interest is the average per-round regret
T AT.
(5)
Clearly, if Q = P, we can choose bū = by for all L E [7] that satisfy 2 and G3. which yields A = 0 almost surely.
We will be considering two main ways of measuring the similarity between two probability dis- tributions P and Q. The variational distance between P and Q is defined as ||P Ql
"See Section 6 for a discussion on how the learner can choose suitable Q even in the absence specific knowledge about P.
use measure the similarity in this paper the quantities Vr defined in 8 and Dr defined in (TT). For Dr, it worth noting that it simply normalized version of the Kullback-Leebhe divergence D (PTQ) via (15) of Lemma
'The technical notions
'Altemnative definitions found in the literature are equivalent to this one, however, sometimes additional
factor of 1 is included in front of the supremum.
5

---

Published as a conference paper at ICLR 2026
supFE [PFF) Q(F)) This can, the notation suggests, be understood signed measures, however, for the purposes of this paper sufficient to think of as a met- ric of probability measures. The Kullback-Leibler divergence between P and Q is defined as D (PIl)) == Ep log (d)) where dP denotes the Radon-Nikodym derivative, and all in- stances of the functions log and exp that appear in this paper are understood with Fuler's number as their base. We write P < Q if P is absolutely continuous with respect to Q. i.e., if every Q-null set also a P-null set. If the Radon-Nikodym derivative that appears in the definition of D (PIIQ does not exist because P * Q, we use the convention D (PII)) = oc.
norm of
We define the following notions of similarity of the distributions P and Q which are based on variational distance and Kullback-Leible divergence and will play a central role in the proofs of our technical results:
(1) p
(Z....., 71-1:-)- -K( (2 ..... Z-11;)
(instantaneous
(6)
variational distance)
1 1/ T 4t
Σ
(average instantaneous variational distance)
Vr = ErVT,
(expected variational distance)
(8)
de = D ( [I,..., 2.,,,,111333 )1k ( Z0-1;))
(instantaneous divergence)
(9)
DT T
1
Σde de
(average instantaneous divergence) (10)
t=1
Dr = Dr
(expected divergence) (11)
is worth noting that the instantaneous notions defined above are random variables while the expected notions are deterministic quantities. This means in particular that instantaneous notions can only be computed given observations process Zz,... while expected notions can be computed without such observations.
5 RESULTS FOR THE MISMATCHED PREDICTION PROBLEM
This problem has been solved for expected regret by Merhav & Feder 1998). Namely, the authors implicitly prove the following bound:
Theorem 3 (Merhav & Feder (1998), eq. (23)). Consider the prediction problem P defined in
Problem 7 The expected average per-round regret A defined (5) can be bounded as EA < LVT, where V is defined in (8)
This result can be stated in a slightly weaker (but potentially easier handle) form with the obser- vation that via Pinsker's inequality, the variational distance that appears in Theorem3can be upper bounded in terms of Kullback-Leible divergence which has much nicer tensorization properties. We summarize the relevant connections in the following lemma:
Lemma 1. We have the following relations between the quantities defined in
1
V S 1//2 Dr
01
2
(12)
(13)
Vr
Dr.
(14)
P < Q we also have
Dr = 1 -
(15)
These (fairly straightforward) facts are implicitly proved for finite by Merhav & Feder 1998).
For the sake of completeness, we provide full proofs for Lemma a as it is stated here in Appendix
In light of (14p and (15) Lemma I we arrive at the following corollary Theorem 3 which was proposed by Merhav & Feder (1998).
'Note that the additional factor that appears in Merhav & Feder 1998) is due the fact that the paper uses base 2 logarithm in the definition of Kullback-Leei Lebber divergence.

---

Published as a conference paper at ICLR 2026
Corollary 1 (Merhav & Feder (1998), eq. (23)). Consider the prediction problem P defined in Problem 7 The expected average per-round regret defined in (5) can be bounded as EA 1 LVD Q) (2T
In this paper, we study bounds of the same kind as Theorem B aand Corollary Iacilaryyhhie Which hold with high probability over P. The main technical result is the following:
Lemma 2. Consider the prediction problem P defined in Problem 1 probability least 6 over P, we have
For every 8 E (0, 1], with
2V21 VT
1 log
A < 2LV
(16)
8"
where VT is the random variable defined in
This lemma can be proved by identifying a suitable supermartingale and applying the Azuma- Hoeffding inequality. For full details, we refer the reader Appendix D
problem with the applicability of Lemma 2 is the appearance of the random variable V in the bound. In order compute Vr, we need full knowledge not only of P and Q. but also of Zi...., Zr. However, we can derive the following high-probability bounds as consequence of Markov's s inequality and the preceding lemmas:
Theorem 4. Consider the prediction problem defined in Problem For every 8 (0, 1]. each of the following inequalities holds with probability at least 1 - 8 over
(where Vr is given in (8))
1
2V2L VT
2 log
D Q T
2 22
2 log 8"
A < 4LVT
(17)
2< 2L
(18)
5
We include the full technical details of the proof in Appendix The usefulness of Theorem immediately clear from its statement since computation of the bounds requires knowledge of P and Q and the learner is in general not expected to know P. However, these quantities can conceivably be upper bounded in case the learner has knowledge that Q is sufficiently high-quality approximation of P. One case which is particularly relevant and for which it is known how to construct a suitable Q alongside a bound for D (PI[Q) is the universal prediction scenario. We describe this scenario, survey the literature on how to choose Q. bound D (PI]Q), and obtain high-probability regret bound from 18 in Section 6
4 is not
Since these concentration results are obtained from Lemma 2 with the Markov bound (which is known not be tight in many cases), this begs the question of whether would be possible to improve upon Theorem 4 by using more advanced techniques. It is not unheard of that learning algorithms perform well in expectation but general pick up factors that are polynomial in the tail probability when viewed through the nigh-probability lens. This was for instance shown by Adee-AAi et al. (2023) for a class of binary classification problems, With the following impossibility result, we show that this is also the case here and this aspect of the bound cannot be improved without making additional assumptions.
Theorem 5. For every C' E (0, oc), a e 1). B e [0, 1/2), and every E x (0, 1] + J0, 20) such that for every fixed d [0, e(T. + 0 as T + oc, there is prediction problem P = (T, (2, (B, H.).) E) with the following properties: (i) 2,B = {0, 1,2] (with discrete o-algebras), and E(b, 2) 16z2 is the classification loss; (ii) there exist a probability distribution Q on (ZT .98T) and 8 10,1) well as learner's policy satisfying (3) such that with probability at least under P, the average per-round regret A defined in (5) satisfies the following lower bounds
(B.H))
with probability at least 5 under P (where Vr is defined in (8))
AZC / |
(PIIQ) T
1 33 + (T,,))
+T( A VT 8a
(19)
(20)
To prove Theorem 5 we construct prediction problem in which the regret is 0 in most cases, but there is a non-negligible probability that the average per-round regret is close to (which is the maximum value for the classification loss function given in the theorem statement). We then
7

---

Published as a conference paper at ICLR 2026
argue that because have this non-negligible probability of high regret, it is not possible to give a brog--robability bound that converges to a value significantly below 1. The full details of this construction are relegated to the proof in Appendix [
We can see from Theorem 5 that Theorem 4 cannot be improved the sense that the factor 1/6, respectively 1/vō, that appears in the bounds cannot be replaced with an expression that grows significantly more slowly (order-wise) as + without making additional assumptions. This remains true even if we are willing to sacrifice convergence speed of the second summand that appears in the bound.
APPLYING MISMATCHED PREDICTION RESULTS TO UNIVERSAL PREDICTION
In this section, we discuss the relevance of the results proposed in Section and how they could be applied to online learning problems. The most obvious way our results can be used is if a good approximation Q of P known, in which case, as long as we can bound D (PIIQ) or Vr, Theorem is immediately applicable. In this section, we consider the case that a suitable Q is not available
to the learner a priori, focusing on the rate at which A converges to as T - 30. To formulate
this precisely, we need the following asymptotic notion of the problem of prediction of stochastic sequences:
Problem (Asymptotic prediction of stochastic sequences). An asymptotic prediction problem A (Z,9)) Pr. HY), E) is characterized by measurable space (2,9), probability distribution Pa on (Z Of ()&N), a measurable space (B.H)) (the prediction domain), and a measurable loss function L : B x Z + [0, where L E [0, o0). The learner's policy b = (b:)te consists of measurable (deterministic) functions b, 2 B.
For each T E N. asymptotic prediction problem A ((2,9) 9) PR. (B, (8, E) induces prediction problem (as defined Problem 1 Pr = (T, [2, )) PIT]. (5, X), ),{) and a learner's policy (be eaE for A induces a policy (be)uefr for Pr.
We consider learner's policy that satisfies, similarly to 3
by 21-1) E arg min Equ (l(b, Z,) = 21...., Ze-1 = 2-1). bEB
(21)
I' clear from context, we will sometimes write P instead of Pizj and Q instead of Q(7 match notation in the rest of the paper. Because no random variables other than Zi..... ... Z, appear in (2I) and T, any policy function b, satisfies (1 iff it satisfies making the results in Section applicable.
We are interested in whether the average per-round regret A defined in converges to 0 as T oo and if it does, what the convergence order is. It clear from Corollary and Theorem 4 that whenever D (PI[)) grows sublinearly T, the average per-round regret A converges to both expectation and with high probability.
The scenario usually considered in the literature the one proposed by Merhav & Feder (1998) where there is some parametrized family (Pe)eee (where θ is a measurable space) that is known to the learner and it is further known that PN = Pa, for some 0g E θ (where 6g does not need to be known by the learner). Under this assumption, was proposed by Merhav & Feder (1998) that the learner chooses a learner's 's policy which satisfies (2T) with respect to the universal measure
QN Powldd),
(22)
where w is a probability distribution on θ
There are two main cases describes a policy that has a regret which vanishes at a known rate: (i) θ is countable, or (ii) ( (Po)oee satisfies suitable smoothness conditions and all Po are i.i.d. or Markov chains with finite memory.
aware of in which is well-defined and yields QN which
In case (i), it is observed by Hutter 2003) that D (PII)) I log w (((f))) independently of T. Therefore, as long as w( (0) for all 0 θ (which is always possible for countable +), our Theorem 4 yields (TT 1/26- 1/2) convergence rate with probability least 1 å compared to
8

---

Published as a conference paper at ICLR 2026
In expectation MMehavv & Feder 1998
With probability 2 6
(this work)
2 countable (Hutter 2003
O(T-1/2) ( (TT//ogT)-1/ 1/2)
((T))1128-112
Ps i.i.d. (Clarke & Barron 1990)
( log 1)-1 10-1/28-1122
Py Markov with memory
((TT/ log 1)-1
O Pog/log 7) 11
(Atteson 1999)
Table 1: Summary of the convergence behavior of the average per-round regret A for different assumptions about Ps. respectively Z in the case where Py comes from parametrized family.
the (T3 convergence rate of the expected regret guaranteed by Corollary It was further noted by Hutter 2003) that the learner's knowledge not very restrictive assumption at all: it is possible to enumerate all probability distributions on 2 that are computable to arbitrary precision on a universal Turing machine. Although this has no impact the convergence rate, the constant that appears in the regret bound could be extremely large this is done. Therefore, Hutter (2003) suggested to assign higher probabilities in w to distributions with lower Kolmogorov complexity. In this way, as long as the distribution PN is of sufficiently low Kolmogorov complexity, the constant in the regret bound would not be overly large.
suitable parametrized family (Pa (Paee actually
Next, discuss case (ii). Merhav & Feder (9988 point that Clarke & Barron 1990) show for the case in which Px is an i.i.d. distribution that the distribution Qh defined in (22) has the property that D (PIIQ) grows (logg(T). This holds if is supported additional smoothness assumptions are satisfied. Consequently, A converges as ((T) log T") - in expectation by Corollary | and our Theorem 4yields convergence order of (((T) log - with probability at least T T- 6. was later shown by Atteson (1999) that the same holds not just for the i.i.d. case, but also for the more general case of Markov chains with memory of a fixed order.
all of θ and some
The convergence rates of A are summarized in Table | In multiple relevant cases, Corollary [ and Theorem 4 yield vanishing average per-round regret and an upper bound on the convergence order. This is assuming that PN comes from known parametrized family (Po)oge but as noted by Hutter (2003), often this not an overly limiting assumption.
NUMERICAL EXPERIMENTS
In this section, apply the algorithm 21 with choice of Qh of the form given in (22 Markov chain with memory and finite state space. Specifically, 2 = (1,...,S} where denotes the number states the Markov chain can take. The probability distribution Ps of the underlying process Zi,... is then the unique distribution that satisfies (I) for all t e N with
(EI, 1, {=x)) 12-PP m
for all 21...., 21 E Z, where for simplicity we use the convention that 2; whenever S (i.e.. the initial few realizations of the process are though the missing realizations were all in state 1) and (Pela )s,s)..... EZ are parameters with the property
S Vs, $1..... Sm E Z Pajs 2 0, Vss..... sm E 2:
Σ Pa Palss =
(23)
The learner's prediction task is to predict the next realization of the Markov chain, i.e., B = 2, and its performance is evaluated with the classification loss, E(b, 2) == 1042-
The parameters in (23) where the set of all possible tuples (p=lst....... s............. ez which satisfy (23). We relegate the details of how θ is constructed and how the expectation over the resulting probability distribution Q is minimized to Appendix H
unknown the learner, which will instead rely on Qx defined in 22
In Figure I show the mean regret of the learner's 's policy well the observed regret quantiles in 4, 000 simulation runs of this policy. can be seen that the average regret gets close to for long enough sequence lengths, and do the quantiles (which can be understood empirical observations

---

Published as a conference paper at ICLR 2026
mamm
min mas
0.20
quantile
95% quantile
10% 90% quantile
average regret per round
20% 80% quantile
0.16
30% to 20% quantile
40% to 60% quaniile
0.10
0.05
0.00
200
250
300
sequence length
Figure I: Average regret per round for Markov chain with memory order m = 3 and S = 2 states. Shown are the mean and selected quantiles for 4, 000 runs.
of the high-probability regret), albeit quite bit more slowly than the average, would be expected from our theoretical results.
In this example, have chosen to enumerate all possible probability distributions for = 3 and = our family e. As can be seen in the definition (47) of in Appendix HH the dimension of long the memory order is small and the state
θ is (S 1) ST which remains manageable space moderately sized. However, the framework also offers the flexibility to incorporate additional side information about the distribution of the observed sequence by choosing to include only certain probability distributions in O. In this way, the convergence time can be improved, computing the predictions can be made more efficient, and using larger (or continuous) state spaces can become algorithm are appropriately tuned, we
tractable. If the hyperparameters of the Metropolis-Hastee expect roughly a linear dependence of the computational complexity on the dimension of O. As rough orientation for the complexity of this example, it takes between a few seconds and a few minutes generate single prediction on a standard laptop without parallelization (depending on length of the already observed sequence). It it also worth noting that does not need to accurately represent prior belief to guarantee a vanishing regret - indeed, the convergence rates in Table [ are guaranteed to hold long the true 0 is in the support of With that being said, it is possible to incorporate prior belief into the design of w by assigning more weight to more likely While that will not affect the convergence rate, it does affect the constants that are hidden in the O expressions and can therefore be attractive in practice.
LIMITATIONS AND FUTURE RESEARCH DIRECTIONS
While the mismatched prediction results of Theorem need very few assumptions and can therefore be expected to be immediately applicable to wide range of practical problems, their usefulness for universal prediction scenarios would crucially depend on the construction of suitable parametric family (Po Po0 The literature we summarize in Section has several examples of how to do this that are quite satisfying from a mathematical perspective, and even the idea enumerating all possible probability distributions can sometimes be feasible as we show in Section 7 However, this might not be feasible in every practical scenarios, so additional research might needed for specific scenarios to find suitable approximations of the minimization
when the parametric family is very large.
is also interesting that the error probability in the upper bound Lemma appears only in the form /log(1/ (1)), but the scaling behavior the error terms Theorem is much worse. We show in Theorem that it is not possible to derive better result in general, but would be worthwhile to investigate in future research if there are suitable additional assumptions that would yield bound akin to the one in Theorem 4 but with logarithmic scaling in comparable the bound of Lemma
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported in part by the Australian Research Council under Project DP230101493.
REFERENCES
Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Interior-point methods for full-information and bandit online learning. IEEE Transactions on Information Theory, 5877)441444417, 2012.
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. The one- inclusion graph algorithm is not always optimal. In The Thirty Sixth Annual Conference on Learning Theory, pp. 72-88. PMIR, 2023.
P.H. Algoet. The strong law of large numbers for sequential decisions under uncertainty. IEEE Transactions on Information Theory, 40(3):609 6333,,3,,,,, 1994. doi: 10. 10.1109/18.335877
Charalambos D. Aliprantis and Kim C. Border. Infinite Dimensional Analysis. A Hitchhiker's Guide. Beiinger-Verlage Berlin Heidelberg New York, 3 edition, 2006.
Maryam Amin, Umara Noor, Manahil Fatima, Zahid Rashid, and Jörn Altmann. Towards trustworthy aircraft safety: Explainable ai for accurate incident and accident predictions. In International Conference on the Economics of Grids, Clouds, Systems, and Services, pp. 197-211. Springer, 2024.
Kevin Atteson. The asymptotic redundancy of Bayes rules for Markov chains. IEEE Transactions on Information Theory, 45(6):2104-2109 1999.
Richard Bellman. Decision making in the face of uncertainty II. Naval Research Logistics Quarterly, 1(4):327-332 1954. doi: https://doi.org/ http://d...rrr.1....//a//a...110 10022/ha.33000014411..
Aaron Boussina, Supreeth P Shashikumar, Atul Malhotra, Robert L. Owens, Robert EI-Kareh, Christopher Longhurst, Kimberly Quintero, Allison Donahue, Theodore C Chan, Shamim Nemati, et al. Impact of deep learning sepsis prediction model on quality of care and survival. upj Digital Medicine, 7(1):14, 2024.
Nicolo Cesa-Bianchi and Gabor Lugosi. Worst-case bounds for the logarithmic loss of predictors. Machine Learning, 43:247-264, 2001.
Nicolo Press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge University
Erhan Çinlar. Probability and stochastics, volume 261 of Graduate Texts in Mathematics. Springer, New York Dordrecht Heidelberg London, 2011.
Bertrand S Clarke and Andrew R Barron. information--heoreti asymptotics of bayes methods. IEEE Transactions on Information Theory, 36(3):453-471, 1990.
Ashok Cutkosky and Zak Mhammedi. Fully unconstrained online learning. Advances in Neural Information Processing Systems, 37: 172110148-10000 2024.
Anubhab Ghosh, Antoine Honoré, and Saikat Chatterjee. DANSE: Data-driven non-linear state
estimation of model-free process in unsupervised learning setup. IEEE Transactions Signal Processing, 12:4888-8888 2024. doi: 10.1109/T9922024338377..
Gyorfi, Gábor Lugosi, and Gusztáv Morvai. A simple randomized algorithm for sequential prediction of ergodic time series. IEEE Transactions on Information Theory, 45(7):2642-263 1999.
Lszl Gyorfi and Gyrgy Ottesaak. Sequential prediction of unbounded stationary time series. IEEE Transactions on Information Theory, 1365):1866-1872. 2007.
James Hannan. Approximation to bayes risk in repeated play. In M. Dresher, A. W. Tucker, and P. Wolfe (eds.), Contributions to the Theory of Games vol. III, number 39 in Annals of Mathematics Studies, pp. 97-139, Princeton University Press, Princeton, NJ, 1957. doi: https: //doi.org/10.151//9998 400882151 1-000
11

---

Published as a conference paper at ICLR 2026
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. In The Thirty Sixth Annual Conference on Learning Theory, pp. 5682-5696. PMLR, 2023.
W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97-109, 1970.
Marcus Hutter. Optimality of universal bayesian sequence prediction for general loss and alphabet. Journal of Machine Learning Research, 4(Nov):971-100) 2003.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Nishant Mehta. Fast rates with high probability in exp-concave statistical learning. In Artificial
Intelligence and Statistics, pp. 1085-1093. PMLR, 2017.
Neri Merhav and Meir Feder. Universal prediction. IEEE Transactions on Information Theory, 44(6): 2124 114-2147,11 1998.
Gusztav Morvai and Benjamin Weiss. On sequential estimation and prediction for discrete time series. Stochastics and Dynamics, 7(04):417-437, 2007.
Gusztáv Morvai and Benjamin Weiss. Nonparametric sequential prediction for stationary processes. The Annals of Probability, pp. 137-1160, 2011.
Hang Qin, Anubhab Ghosh, and Saikat Chatterjee. iDANSE: Iterative data-driven nonlinear state estimation of model-free hidden sequences. In 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2025. doi: 10.11000CASSP44460022222 200.S/44496660222228888888666
Malempati Madhusudana Rao. Measure Theory and Integration. Pure and Applied Mathematics.
Marcel Dekker, New York Basel, 2 edition, 2004.
Sebastien Roch. Modern discrete probability: An essential toolkit. Cambridge University Press, 2024.
Claude E Shannon. Prediction and entropy of printed English. Bell System Technical Journal, 30(1): 50-64, 1951. doi: https://doi.org/ org.//....r/....... 100.00002..11100. 1538-7305. 1355..951..t01 1666.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4))285-294 1933.
Dirk van der Hoeven, Nikita Zhivotovskiy, and Nicolò Cesa-Bianchi. High-probability risk bounds via sequential predictors. arXiv preprint arXiv:2308.0758g 2023.
Kazuho Watanabe and Teemu Roos. Achievability of asymptotic minimax regret by horizon- dependent and horizon-independent strategies. Journal of Machine Learning Research, 16(1): 2357-2375, 2015.
Tsachy Weissman and Neri Merhav. Universal prediction of individual binary sequences in the presence of noise. IEEE Transactions on Information Theory, 47(6)22151-2173, 2001.
Tsachy Weissman and Neri Merhav, Universal prediction of random binary sequences in a noisy environment. The Annals of Applied Probability, 14(1):54-89, 2004.
Changlong Wu, Ananth Grama, and Wojciech Szpankowski. Online learning in dynamically changing environments. The Thirty Sixth Annual Conference on Learning Theory, pp. 325-358. PMLR, 2023a.
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojeiech Szpankowski. Regret bounds for log-loss via bayesian algorithms. IEEE Transactions on Information Theory, 6999)5997-55989, 2023b.
Qingzhao Zhang, Shengtuo Hu, Jiachen Sun, Qi Alfred Chen, and Z Morley Mao. On adversarial robustness of trajectory prediction for autonomous vehicles. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15168, 2022.
12

---

Published as a conference paper at ICLR 2026
A DETAILED ARGUMENTS FOR REMARK 1
Item 1 Consider learner's policy which for all & E [2], having seen realizations 21,.... 2 We design Q such that conditioned under 21..... žt- assigns large probability to (2(2...... 2t-1) and smaller but nonzero probabilities (so that singularities in the definition conditional probability occur) to the other possible outcomes. More precisely, pick qrr (0, 1) such that q > r 2| 1) and q + r Define, for each
makes the prediction by
q: 1r/(12)- -)),
= b= ..,,,...., Zt-1)
K (ZI.................... ................................ Rt-1, {z})
otherwise,
and construct Q such that it satisfies the analog of 1 Then the policy (be).e(T)) which was arbitrary above, satisfies 33)
Item
Given learner's policy (be)εE(T),
define ( 2-11 (z})
(2 1z). We then have
Eq (e(b, [1),,
Z-11 21-1) = - log((((2)))
= (bb 2 + (b((2)...,,
where D (-I1-) denotes dallback-Leibles divergence and H denotes Shannon entropy. Since Kullback- Leibler divergence takes its minimum value the two arguments are identical, we can conclude that this expression is minimized for b (2(21, 2t,),, showing that the policy is indeed represented in the form
B EXISTENCE OF MEASURABLE (bi)<e(r AND (be)te(r)
In this appendix, we give sufficient conditions under which there exist measurable maps (6ā ke(r) and (be)eetz such that and are satisfied.
The measurable maximum theorem (Aliprantis Border 2006 Theorem 18.19) ensures that such maps exist if (B, H)) is metrizable in such a way that the following are satisfied:
(B, H) is separable and compact.
For every b 13, the function E(b, -) 2 - [0, T.] is measurable.
The function E(., 2) B [0, L. is continuous.
An important special case of this is that of finite B with the discrete o-algebra the choice for H.
C PROOF OF LEMMA
First, we observe that 12
is simply an application of Pinsker's inequality.
For 13
we argue
1
T
de
2
d
Dr:
where (a) is due to Jensen's 's inequality and concavity of the square root.
For we make the very similar argument
VT
EpVT
Dr
(a)
V
Er
11
Dr,
where (a) is again due Jensen's 's inequality and concavity of the square root.
13

---

Published as a conference paper at ICLR 2026
For (15), we first note that since P < Q, it follows by induction from Raa 2004
Section 6.3,
Proposition 1) that P-almost surely for all t [T], KP (Zi...., 2, and we can decompose, for P-almost all (z1,..., .r) =Z¹
(Z1..... 7-
dP dQ
T dk (t)
21,.. 2ا-1, (zt).
11
2T)
(24)
dk Q (Z1 21-1,-)
So have
1 D(P1Q))
(4)
T Ep log
1
dP
(Z,,..., 7T)
dQ
d
dk (t) (Z,,..., 20-11-) (2,)
24
E p
log
dk@ (Z).... (1-1,:)
log dk (Zi..... Zi Z(-1,") (Zi)
(
BPI i1 1 (2m..)
T
dk() (t)
(Z1.... 21-
T
Eps
1 de
T
T
(c)
E
de
T
Dr.
where in both steps labeled (a) we have used the definition of Kullback-Leible divergence, in (b) we have used ( in conjunction with the linearity of expectation, and in (d) we have used the linearity of expectation.
D PROOF OF LEMMA 2
Property (3) of be = implies in particular that for every E [T] and 21. 2t-1.
(eb (2,, 21 1), Z = 21. Z--1 = 21-1)
- (2). 21, Zt) = 21, Z-- = 21-1). (25)
We can further bound the left-hand side as
(((((((()....,..)))) 21-1), Z;)l 21,..., Z 2t-1)
K(00 22 2- (2) (2 Z {(by ((bx(21 (2.. .2, 2111), 20) 21 dx
(4)
21..., a2 3 (bb((21......................... .-1)) > >x) dr
1.
2
((()
(2) 2-1 (2e E 2 (2),) 2x) > >x}>
24
- [2(0) (s),..., k(d (21, ) do
=
21)12r ...... Z 20-1)
(26)
- L ( (z), (2),...,.-11.)))
.-1.))) k(6) (2), )0)1;)
14

---

Published as a conference paper at ICLR 2026
where (a) is due to the loss being bounded in [0, LJ. With the argument, can bound the right-hand side of 25 as
BQl (E(b) (21...... 24 1111) 2,,12 - 21....; Zo-1 = 2
2 Ep 1Ep (Z). -t- 1), 21,2111111111 2...... 2--1 = =2--1
L K (1) (211..,,2--11) 1/2 (21,... (31,..,,, ( (27)
Combining 225). 26). and 27 we obtain
Ep(((b,(Z))..... =z- 1), 2,) = ..,..., 2--1 = 22-1)
- (1( Zi)lZi = ,, ,1....,Z-11 = -1-1= =2-1)
-2L k (z1 (3-1)).,.2111))) - ( (21...., 50. (28)
Note that if we define
B B(e(B,, Zol ... Zo-1) (w)
/ (Z))) (00))...,,,,(())) Z
21 KP (Z)(w)... Z dzt),
then EE (BB,, Z,,,. Z--1) is (as the notation suggests) a version the conditional expectation
due to Cinlar 2011 Section IV, Theorem 2.19). Clearly, the analog for the conditional expectation E (B; Z,
Zz-1) ,
holds as well. Also noting 66 we can therefore rewrite
28 as
..... E (B,, 2,) Zr-1) E (( 2.),, Zz-1
2L 00
(29)
almost surely. Next, we define an auxiliary process A6r ..... D/ via A :- and
A
- Zv) 2Le0
mml
for E (T). We calculate
E ZA 7-11)
Ai- + ((Br, Zz) E(B,, Z,) - 21, 21-1)
1 E (((B(, ,.) ..-1) B ((((L) ZI), ((1),,)))... -2-10 2L
A/11
where in step (a) we have used the linearity of conditional expectation and the fact that A as well as the variational distance term are measurable in o (Zz,.... Z,-1). It follows that A ... A7 is supermartingale. Next, we observe that for every t E [T). we have
A A = {(B,, Z.) e {(B, Z,) 2Lv E [-3L, L).
An application of the version of the Azuma- Hoeffding inequality stated in Theorem of Appendix G yields, for any E (0, oc),
2=a exp
(() exp
(4LY))
8T
With the definition
8: 2V log z'
which can be equivalently written as
5 = exp
8T12
15

---

Published as a conference paper at ICLR 2026
obtain that with probability at least - å over P, we have
1/ <222222 log 8
(30)
To conclude the proof of the lemma, we observe that
7 TA 21
7 11 Σ
T
A
-211)
t=1
which substitute into 330 and solve for A.
E
PROOF OF THEOREM 4
Lemma 3. Consider the prediction problem P defined in Problem and the quantities defined in (6)
For every E (0, 1]. each of the following holds with probability at least - 8 over P:
Vf < VT
(31)
1 28
VT <
DT-
(32)
Proof. (31) is a direct consequence of the definition of VT in (8) and Markov's inequality. For (32) we use Lemma alongside definitions ( -III) and Markov's inequality. Specifically, we observe that due to Markov's s incquality, we have
P(D
EDT 8. Dr
P
Dr
(33)
With this, we can argue that with probability at least 1 over P.
De
Dr
Dr
2
2
28
where step (a) due to Jensen's inequality and concavity of the square root.
Proof of Theorem
We first observe that the implication
21 2 8 VT
2 V Vog A2LV 2LV,
3 = <
2
2/21.
2
A < 2LV +
log
(34)
8
VT
holds. With this, we argue
21
P
A
2LV
V Vlog
VT
2V
2 22LV 2 2LV. 3)
P
A > 2L +
log 5
VT
(b)
2/2L
2
+ P (2LVr 2 2LV7 2
< P
A
2 +
log g
VT
(4) 8 2 2'
where (a) is by monotonicity of probability using the contrapositive of (34), (b) is due to the union bound, and (c) we have used Lemma 2 the first summand and (3I of Lemma 3 in the second summand, where 5/2 has been substituted for 8 in both cases.
16

---

Published as a conference paper at ICLR 2026
For (18) first note that if P & Q, the bound trivially holds since the right- side is infinite in this case. For the case P < Q, the proof proceeds along very similar lines as before. Namely, we observe that the implication
2/2L VT
1 Tô
A 2
V log A
Vor
D (PIIQ)
I
2/2L VT
2 V log 8" (35)
+ A 211
((PI))+
T8
holds. Hence, we can argue, for every 8 e (0,1).
D (PIIQ)
1
2/21
2
P
A 2 2L
log
T
V8
VT
2/2L
2
1
P
A 2 21 +
log
V
VT 2
D (PIIQ)
VT
T8
2V2L
2
1
K P
A 2 21 +
log
+ P
VT 2
D (PIIQ)
VT
8
T8
2/2L.
2
P
A
2LV +
log
+
P
Vr 2
V
8 Dr
Dr
VT
(e) 8 5 2 2
where in (a) have used the contrapositive of 35 with the monotonicity of probability, in (b) we have used the union bound, and in (c) we have used Lemma[2 in the first summand and (32) of Lemma 3 in the second summand, where 6/2 is substituted for ō in both cases.
F PROOF OF THEOREM 5
This proof is structured as follows: we first construct two probability distributions Ps and Q? on 2 with two free parameters yp and vb. This done with the understanding that once I' is fixed, P : Pr1 and Q = Q are the marginals on the first T components. We then proceed to calculating Vr and D (PIIQ) in dependence of sp, th, and T. Next, we determine predictors BI..... By that are associated with learner's policy that satisfies (3). as well as the predictors Bi...., By, associated with an optimal prediction rule that satisfies (2) (which also exists since B is finite and H discrete). Based on this, determine the average per-round regret A. Finally, we specialize this general construction to specific choices of ip, vb T, and 5 depending on C, a, B, and E that satisfy (19) and 20)).
Choices of Ps and Qu. Let E (0, 1/2) and eb E (0, - sp) be two parameters to be further specified later. We pick Q2 == Q1 ..... with
8,
2 = 2 =
Qc((=)) =
1 - - 1b
(36)
2
for every E N. The choice of Ps is given by Pi = Qi and for t >>> 1,
1,
21 0, 2t 2
8 1b
21 - 0, 21
KP (21...., 24-1, fz()) =
1- 6
21 + 0, 21 = 1
(37)
db.
+ 0, 21 2
otherwise.
PN is then defined via ( matching up with the corresponding technical assumption conditional probability. These choices ensure in particular that under P. Zz...., , ZT are all almost surely whenever Z, 0 and follow the same distribution as under conditioned on the event Zn (1,2).
17

---

Published as a conference paper at ICLR 2026
Computation of divergence and variational distance terms. For the variational distance term, have Vir 0 if 1 # 0 because in that case all the conditional probabilities under P and Q are equal by definition. For the event Z1 = O, we can compute the variational distance term as
(Z Z.-1,)) KQ (Zi, ...; Z0-1, ITV
K
T
(a)
KP (1) (Zi,... (2)) K2 (Z,...., Z 24. (2}
T T (1 4))
where in (a) we have observed that the first summand is since Pi = Qi and for the other summands, we have identified the event Z: = 2 which realizes the supremum in the definition of variational distance. In step (b), we have correspondingly substituted the choices (36) and (37). For the expected variational distance term, obtain
T T
VT = Pi((O))
(1 v)
4(1 - +)
(38)
T
The KL divergence term can be computed
(
(c)
P((( log
P( 2(((
Q(((21,...,,
2 I K (21 12))
P([(z)....., 2T))) log
IT, K (1)
....,........................... 2-11 (z))
2
KP (10)) II
K 22 ................................ 2 (2))
P([(0, 22..... (2,,,,, log
KQ ({0))
(T
(0, 22
2
Q
1I
K (t) (2), ( (211
P([(Z),..... (T)) log
I1 Ke ( (2))
Eg....
KD ((O)) K( (0,2. ........2.. (2})
P([(0, 2)1) log
K2 ((O))
K 0, (2})
K p (121))
Σ
Σ 21))
log
Ko (121))
(1)
=1=
IT K( (21 ........ 2 (2+))
+ log
II, K (21 2-11 (2+))
K/ (10)) IT p
2, (2})
K 11) ((0)
K 10 (0,2, ...,, (2) log
K
(10))
K (0. 2, (2})
(1)
2=2
36
37
4p
log
1
= =
1)pp log
(39)
where in (a) we have used the definition of Kullback- divergence, in (b) we have used in the first summand that P([(0, :2..... 2T)) fact that due to the definitions of P and Q, all logarithm arguments in the second summand are 1, while the first summand, we have applied (I).
unless 22 27 2, and (c) we have used the
Computation of regret. It is clear from and 336 (also recall + 1 < 1)) that
B
Br
(40)
18

---

Published as a conference paper at ICLR 2026
and it is clear from 2 and (37) that
1, 21
=
(41)
2. 21
= 0.
We can calculate the average per-round regret from
(5).
(37
40
and (41) as
T
1 T
[0
Z1 + 0
Z.))
(c(B,, - (B) 2.)) =
(42)
T
T-1
Z1 0.
Choice of parameters. We first define sequence (dx)NEN via 8, +/(n+3) 3) for all N. This choice ensures that the sequence takes values of most 1/4 and
lim 8n = n-
(43)
(which are the only properties implied by this choice that we will need). We next define a sequence (Tu)ee via
To min { T E N. =(T,8,) 1m= Tn-1)
Am
This is possible since by assumption, s(T, - for any fixed 8 as - oc. Again, this specific choice is only given to ensure that we have well-defined (Tn)neN. The only properties we will need are that the sequence is strictly increasing and
lim <(T,, 8n) n-
(44)
We now specify v == 1/8, := Substituting these choices as well as the calculations (38) and (3).. we can rewrite (I9 and (00 as
= Tn and 6, = on, where the choice of n. is left open for now.
A C 7 T, -
T 61-0 + (T 8n) =: Rı
(45)
Tn -
log8 -8 +e(TTn 5n) R2, Tn
A
(46)
where we have introduced Ri and R2 to denote the right-hand side of these inequalities. Note that under the choices we have made in this proof, R₁ and Rg are also equal to the right-hand sides of (19) and (20), respectively. Recalling the assumptions a < 1, < 1/2 from the theorem statement and the properties (43), 44 ensured by our construction as well the fact that (Tn)neN chosen as strictly increasing sequence, we observe that
Tn -
lim R. = 0, lim R2 = 0, lim 1+000
1.
+0000
n-
Tn
These limiting behaviors ensure that we able pick n in such way that
Tn -1
R1.
R2
Ta
This concludes the specification all the parameters we have used in our construction. We can now bound (for 1, 2)
Tn
P ( R₂) 2
P
A
>
8,1
T
which concludes the proof of the theorem.
G THE HZOMA-HOG INEQUALITY
In this appendix, state the Szuma-HHoffddle inequality in the form in which we need it in this paper. Since we are not aware of a reference that states and proves this exact form, we prove it as straightforward consequence of (Roch) 2024 Theorem 3.2.
19

---

Published as a conference paper at ICLR 2026
Theorem 6. Let $ = (Fi)tzo be a filtration, (X1){-o be supermartingale with respect F, and
(Xi)=n, (2)) be & prredictable processes such that for all t E [T], we have almost surely
Y Xx XL-1 S Ze Ze - Y S
where C Cr.,rrr R. Then, for all E (0, 20).
2ga
P (XT Xo 2 k) S exp
Σ/=1 CT
Proof. We write (Xi)=11 in terms of its Doob decomposition (see, e.g.,
Cinlar 2011
Theorem 3.2))
X = M2 + Xt,
where (M.)== is martingale and (X.) is --predictable and nonincreasing. Then we have for all t [2] the identity Mr MM-1- X, X X, -X,-1 and hence
+ X, X,-1 1 S M₁ M s Zz X, X,-1-
Clearly, both (Y X, xx and (Z + Xx - are predictable processes and we have
2 + X, - X.-1) Yi + X, Xx-1)
Y₁ S
almost surely for every E [7]. We can therefore bound
(( Xo 2 26) = P Mr 10-pp/(--
Mo + Xx 80 -x)2e)
5 P (M
Mo 2))
(b)
25
x exp
Σt=
2
where (a) is because (Xt) is nonincreasing and (b) is due to (Roch 2024 Theorem 3.2.1).
H IMPLEMENTATION DETAILS FOR THE NUMERICAL EXPERIMENTS IN SECTION 7
Due the summation constraint 23
can parametrize the parameter
= { [0, [0, (0
(Pi)s (Pils) Ps PS---Ps 1181......m ) Sm......
V8i,... Sm E 2 Pile + + Ps
$ <1}.
(47)
In this example, do not assume any prior knowledge the part of the learner other than the true distribution of the process described by one the parameters contained in (i.c., it is some Markov chain with memory at most m.) As in we use uniform distribution e.
Our implementation of the learner's 's policy needs to compute
Eqx (E(b, Z,) = 21. Zi-1 21-1) = EQn [1 11 21
Z--1 -2-1)
- k 2-
for all b and then choose minimum. For the Markov kernel, we have
Kff (zi...., 21-1, (b})
Q 01=_((((),,.,,--__)))
Se (1
Jo [(. (8')
post ,,, p. (21, ... , 2t (b)
(48)
20

---

Published as a conference paper at ICLR 2026
where Po.[c] denotes the marginal of Po for the first components and
w(0)
(0, Se Po. (2(,,,,............. 21 (w dd Po. Pos1-1](((2...............
(49)
clearly is a probability density function on θ. Since w()) does not depend on 0 (as we have chosen be uniform density), only 1 (1(=1..... z(-1)) in (49) depends 0 while the fraction in front of it is normalization factor not dependent on B. Hence. we can approximate the integration (48) using the Metropolis- Hasttnol algorithm (Hastings 1970). which only requires us evaluate
the unnormalized density Po.te Pe. + and the integrand K ( (EI,.... 2t-1 {b}) and generally well-behaved for high-dimensional parameter spaces θ.
DISCLOSURE OF LLM USAGE
large language model (LLM)) used for coding assistance while writing the simulation code for conducting the numerical experiments described in Section 7 The LLM was used to assist with routine programming tasks including code completions, finding bugs, and refactoring code. was not used for development of algorithms and all code involving the generation of results reported in the paper, including Figure was carefully checked by the authors.
21


Reviews:
[{"review_id": "gS4HysDJVP", "reviewer": "Reviewer_QjcE", "summary": "This paper revisits the classical problem of universal prediction of stochastic sequences and aims to complement existing in-expectation regret bounds in (Merhav and Feder, 1998) by deriving high-probability bounds. The setting involves a learner predicting stochastic outcomes over a known finite horizon with losses measured by a bounded function. They show $O(T^{-1/2}\\delta^{-1/2})$ convergence rate with probability at least $1-\\delta$, compared to the classical $O(T^{-1/2})$ rate in expectation. The authors also establish an impossibility result, proving that the bounds cannot be improved significantly without stronger assumptions.", "questions": "- The paper extends classical expected regret guarantees to high-probability bounds. Could the authors better illustrate practical scenarios or domains (e.g., time-series prediction, online compression, or universal coding) where such high-probability guarantees provide tangible benefits over expected bounds?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper studies a fundamental problem.\n- The paper is well-written and has a clear related-work section.\n- The paper presents an impossibility theorem clarifying the optimality of the proposed dependence on $\\delta$", "weaknesses": "- The paper heavily focusses on theoretical analysis while leaving numerical experiments as future research directions.\n- The related work section could be tightened. Citations to multi-armed bandit and MDP literature feel tangential since those problems involve decision-making and exploration-exploitation tradeoffs whereas the present paper studies passive sequence prediction. Such citations distract from the main focus on universal prediction although there might be possible methodological overlap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9wi5o16eUD", "reviewer": "Reviewer_dppa", "summary": "This paper studies the universal prediction problem of stochastic sequences. Given a sequence $Z_1, \\ldots, Z_{T}$, the goal is to give a prediction at every step $t$ based on the previous observations $Z_1, \\ldots, Z_{t-1}$ that achieves a small error compared to the optimal strategy that has prior knowledge about the underlying distribution of the sequence. The authors show that $(T\\delta)^{-1/2}$ regret can be achieved with probability $1-\\delta$, and the polynomial dependence on $\\delta^{-1}$ cannot be improved in the algorithm analysis.", "questions": "1. It would be great if the authors could confirm whether Theorem 5 generally holds for all algorithms, or only algorithms that satisfy certain structures or assumptions. If it is the latter case, why would it be reasonable to focus on these algorithms?\n3. For what distribution families do the authors think could achieve $log(1/\\delta)$ dependence?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Prediction of stochastic sequences is a fundamental problem, and a high-probability guarantee is often more relevant for practitioners than expected error. This work fills a gap in previous work in that only an expected regret was known.\n2. The authors show that in the high-probability setting, the same convergence rate of $T^{-1/2}$ w.r.t the time horizon can be achieved. The algorithmic framework has some generality, in that similar bounds are also obtained for other settings with different assumptions on the input domain.", "weaknesses": "1. The main weakness is that the dependence on $\\delta$ is not ideal, and it seems that the lower bound result does not hold generally for all algorithms. Specifically, Theorem 5 appears to be specific to some class of policies satisfying equation (3) in the paper. Thus, it only shows that the *error analysis* for the proposed algorithm is in a way optimal, but does not seem to be a fundamental limit that generally applies to all algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qSTIMAE6Zs", "reviewer": "Reviewer_KtRv", "summary": "This paper studies universal online prediction of stochastic sequences with a known horizon and upgrades classic in-expectation guarantees to high-probability bounds under general bounded losses. It analyzes a mismatched predictor under a reference law and then transfers the results to universal prediction via Bayesian mixtures. The main results give pathwise and distributional high-probability bounds with the same $1/\\sqrt{T}$ scaling as expectation bounds, plus an impossibility result that explains the sharp dependence on the confidence parameter. The paper also summarizes consequences for countable alphabets and standard i.i.d./finite-memory Markov families.", "questions": "Please address the concerns raised above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear modular proof strategy (martingale concentration around an empirical TV term, plus information-distance control) that feels broadly reusable\n- First high-probability regret guarantees in this stochastic-sequence setup with general bounded loss and non-i.i.d. data\n- Useful universal-prediction corollaries via mixtures; the rate summary is easy to parse.", "weaknesses": "- I find the dependence on the confidence parameter heavy: once the random pathwise term is de-randomized, the bounds pick up $1/\\delta$ or $1/\\sqrt{\\delta}$ factors. I get that the impossibility result shows this is unavoidable in full generality, but for practical confidence targets the guarantees feel conservative. Readers would be curious to see whether under mild added assumptions (mixing, exp-concavity/log-loss) one can recover something closer to $\\log(1/\\delta)$.\n- From a practicality angle, calibration seems missing. The universal consequences rely on large mixtures, which are intractable and may hide large constants. I’d feel more confident with a small synthetic study (finite-alphabet, or simple parametric families) that reports actual constants and clarifies the assumptions behind the rate table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kyv3bH0Q6a", "reviewer": "Reviewer_imv5", "summary": "This paper studies online prediction of stochastic sequences over a known finite horizon T and derives high-probability regret bounds that complement prior in-expectation results. The authors establish a bound of order $O(T^{-1/2} \\delta^{-1/2})$ holding with probability at least $1−\\delta$, which mirrors the form of earlier expectation bounds (e.g., $O(T^{-1/2})$). They further prove an impossibility result showing that the dependence on $\\delta$ cannot be improved without additional assumptions.", "questions": "1. Can the authors provide a concrete example to construct a tractable $Q$ for a non-i.i.d. process and analyze how the regret bounds perform in practice?\n\n2. Can the results be extended to more general settings, i.e. the loss functions are unbounded but may have heavy-tail or light-tail distribution?\n\n3. This paper does not discuss the dependence on the constant $L$. Is it necessary to consider the improvement of $L$ and is it possible to achieve a tighter regret bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. To the best of my knowledge, it’s the first work to provide high-probability regret bounds for the universal prediction of stochastic sequences without i.i.d. assumption or expert advice.\n\n2. The paper is well-organized with a clear statement of problems and a structured presentation of results.\n\n3. It is nice to see that the dependence on $\\delta$ is already tight in their high probability bound.", "weaknesses": "1. Practical Applicability: Although the mismatched prediction results are general, their application to universal prediction relies on the construction of a suitable parametric family and may be intractable for a concrete problem.\n\n2. This paper assumpts that the learner should know some distribution $Q$ which is assumed to be “sufficiently similar” to the unknown distribution $P$. I think it is quite a strong assumption. It would be better if the authors can add some discussions about how to learn $Q$.\n\n3. Limited Discussion about Computation: The paper does not address how to computationally implement the proposed strategies. It may be computationally complex to apply the methods in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QExODnjhYw", "reviewer": "Reviewer_eMgE", "summary": "This paper studies the classical universal prediction problem as in Merhav & Feder (1998). \nHere, we assume some underlying distribution (random process) $P$ that generates a sequence $Z_1, \\cdots, Z_T$. \nWe are given an approximating distribution $Q$ of $P$, so that at each time step, the learner predicts the Bayesian-optimal decision under $Q$. \nIt is known (and fairly straightforward) that the expected regret between the Bayesian-optimal rule under $Q$ and the (unobservable) Bayesian strategy under $P$ is bounded above by $O(\\sqrt{T \\cdot D(P\\|Q)})$. \nThis paper strengthens the result by establishing a high-probability bound of the form $O(\\sqrt{T D(P\\|Q)/\\delta})$, where $\\delta$ is the confidence parameter. \nThe paper further demonstrates that the $1/\\sqrt{\\delta}$ dependency (and for total variation, the $1/\\delta$ dependency) cannot be improved if no additional structure is known between $Q$ and $P$.", "questions": "I think the negative result in this paper is similar in spirit to the work of I. Aden-Ali, Y. Cherapanamjeri, A. Shetty, and N. Zhivotovskiy, *“The One-Inclusion Graph Algorithm is Not Always Optimal,”* in COLT 2023. It would be helpful for the authors to discuss it, as both works highlight cases where polynomial rather than logarithmic dependencies are unavoidable.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. In my opinion, the main technical contribution of the paper is the lower bound (Theorem 5), which shows that with only a global bound on the divergence between the approximate $Q$ and the underlying true $P$, the dependency on $\\delta$ cannot be better than polynomial. This bound contrasts with much of the prior results in learning with expert advice and bandit settings, where the dependency is typically polylogarithmic.\n\n2. The paper instantiates their upper bound in several settings where an approximate $Q$ is obtainable, such as countable $Z$, i.i.d., and Markov settings.", "weaknesses": "1. The upper bound proof is fairly simple and follows from a straightforward application of martingale concentration inequalities.\n\n2. I'm not sure how significant this result is, as in many natural settings we already have high-probability bounds that depend logarithmically on $\\delta$. The lower bound in this paper feels more like a pathological example. For instance, the examples in Section 6 only show the upper bounds; if the authors could demonstrate any **natural** settings where a polynomial dependency on $\\delta$ is inevitable, the significance of the paper would be substantially boosted.\n\n3. All the results in this paper are based on the hypothetical approximating distribution $Q$. It would be better to have some results that depend on the specific problem structure or on particular algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)