Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
Authors: Ziyi Liu
Idan Attias
Daniel M. Roy
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
log loss
probabilistic forecasting
Primary area: online_learning
TL;DR: We define a notion of complexity for a class of probability kernels and show it is the minimax regret of sequential probability assignment, and allows us to describe the minimax algorithm.

Abstract: We study the fundamental problem of sequential probability assignment, also known as online learning with logarithmic loss, with respect to an arbitrary, possibly nonparametric hypothesis class. Our goal is to obtain a complexity measure for the hypothesis class that characterizes the minimax regret and to determine a general, minimax optimal algorithm. Notably, the sequential $\ell_{\infty}$ entropy, extensively studied in the literature (Rakhlin and Sridharan, 2015, Bilodeau et al., 2020, Wu et al., 2023), was shown to not characterize minimax regret in general. Inspired by the seminal work of Shtarkov (1987)
    and Rakhlin, Sridharan, and Tewari (2010), we introduce a novel complexity measure, the \emph{contextual Shtarkov sum}, corresponding to the Shtarkov sum after projection onto a multiary context tree, and show that the worst case log contextual Shtarkov sum equals the minimax regret. Using the contextual Shtarkov sum, we derive the minimax optimal strategy, dubbed \emph{contextual Normalized Maximum Likelihood} (cNML). Our results hold for sequential experts, beyond binary labels, which are settings rarely considered in prior work. 
    To illustrate the utility of this characterization, we provide a short proof of a new regret upper bound in terms of sequential $\ell_{\infty}$ entropy, unifying and sharpening state-of-the-art bounds by Bilodeau et al. (2020) and Wu et al. (2023).

Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
Ziyi Liu
Idan Attias
University of Toronto & Vector Institute kevind. liu@mail. wtw.onto.ocomm ca
Ben-Gurion University & Vector Institute i idanatti@post. bgu. ac. i1
Daniel M. Roy
University of Toronto Vector Institute ramiee.roy@@toronte..
Abstract
We study the fundamental problem of sequential probability assignment, also known as online learning with logarithmic loss, with respect to an arbitrary, pos- sibly nonparametric hypothesis class. Our goal to obtain a complexity measure for the hypothesis class that characterizes the minimax regret and determine a general, minimax optimal algorithm. Notably, the sequential loo. entropy, ex- tensively studied in the literature (Rakhlin and Sridharan, 2015, Bilodeau et al., 2020, Wu et al., 2023), was shown to not characterize minimax regret in general. Inspired by the seminal work of Shtarkov (1987) and Rakhlin, Sridharan, and Tewari (2010), we introduce a novel complexity measure, the contextual Shtarkov sum, corresponding
the Shtarkov tree, and show that the worst case log contextual Shtarkov sum equals the mini- regret. Using the contextual Shtarkov sum, derive the minimax optimal strategy, dubbed contextual Normalized Maximum Likelihood (cNML). Our re- sults hold for sequential experts, beyond binary labels, which settings rarely considered in prior work. To illustrate the utility of this characterization, we pro- vide short proof of new regret upper bound in terms of sequential foo entropy, unifying and sharpening state-of-the offthhe-rtt art bounds by Bilodeau et al. (2020) and Wu al. (2023).
after projection onto multiary context
Introduction
Sequential probability assignment is fundamental problem with connections to information theory [Ris84; MI99; XBO0J, machine learning [CL06; Vov95; RSTI5; FKLMS1 Sha20], and portfolio optimization [Kel56; Cov74; Cov91; CO96; Fed91]. In the original non-contextual setup, the learner aims to assign probabilities to a series of labels, which are revealed sequentially. The goal is to offer probabilistic forecasts over the label set such that the probability assigned to any observed sequence is comparable to that assigned by the best model in any fixed class of models.
The celebrated work of Shtarkov [Sht87] characterized minimax regret for context-free sequential probability assignment in terms of what now known as the Shtarkov sum, and subsequently de- scribed the minimax algorithm, Normalized Maximum Likelihood (NML). NML represents the ideal probabilistic forecast in the sense of minimax regret, providing a benchmark for universal coding and prediction strategies. While often not used directly due to its computational complexity. NML has guided the design of practical algorithms and informed the development of efficient approxima-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

tion methods. The principles underlying NML have inspired advances in both information theory and online learning, establishing fundamental limits and serving as a critical benchmark.
In this work, we study the problem of sequential probability assignment with contexts, which has been analyzed in recent works (e.g. [R$15; BFR20; WHGS23]) under the framework of on- line supervised learning formalized by Rakhlin, Sridharan, and Tewari [RST10]. In this setup, the problem is modeled as a T T-round game between learner and the nature: On each round the learner observes a context d4 from nature and predicts distribution fr over some finite label space V/ Then nature reveals a label y/ E J and the learner incurs a logarithmic loss lfpr, ve) = log(E, (ve)), where Pr (1)) is the probability assigned to label Ye by Pt- The perfor- mance of the learner is measured by the regret with respect to class FF of experts, defined as the difference between the total loss of the learner and that of the best expert in F. The value of primary interest is the minimax regret, that is, the worst-case regret by the best learner over arbitrarily adap- tive data sequences. The minimax regret serves as a benchmark for all algorithms and as a target for studies of adaptivity. Our goal is to address several fundamental questions:
I t= ...,...? T,
Can we find a natural complexity measure of F that characterizes the minimax regret, enabling us to analyze the minimax regret in new ways? And can we identify, in view of this complexity measure, a general, minimax optimal algorithm?
Notably, the sequential covering number of F, a well studied measure of complexity, has been shown not to characterize the minimax regret on its own [RS15: BFR20; WHGS23]. This fact distinguishes sequential probability assignment and log loss: while sequential covering numbers enable tight analysis in online learning problems with convex Lipschitz losses, like absolute loss [RSTI5] and square loss [RS14a], they do not yield minimax rates for log loss on some classes. Tackling such classes evidently requires new techniques.
Main contributions.
1. We introduce a new complexity measure, which we call the contextual Shtarkov sum, that serves as natural generalization of the Shtarkov sum from the context-free setting. We show that the minimax regret is characterized by the worst-case contextual Shtarkov sum.
2. We derive the minimax optimal algorithm, dubbed contextual Normalized Maximum Likelihood (cNML), using data-dependent variant of the contextual Shtarkov sum, thereby generalizing NML from the context-free setting.
3. We apply contextual Shtarkov sums to the study of sequential entropy bounds minimax. Doing so, we provide a short proof of a new regret upper bound in terms of sequential entropy that unifies and even improves on otale-of-the-arts bounds by [BFR20] and [WHGS23]. Our results extend beyond the binary label setting studied by recent work to arbitrary finite label sets.
Related work. Sequential probability assignment has been studied extensively. Various aspects of this problem have been investigated, including sequences with and without side information (contexts), parametric and nonparametric hypothesis classes, and stochastic or adversarial data- generating mechanisms. This problem has a long history in the machine learning community, see [CL06, Ch. 9] and the references therein. In the information theory community, this problem is also known as universal prediction [MF98], where the regret is also referred to redundancy with respect to a set of codes. This has been studied in both stochastic and adversarial settings [Fre96; Ris86; Ris96; Sht87; XB97; DS04; MF98; OS04; Sha06; Szp98J. where the focus was primarily on the parametric classes of experts. Closely related topics include universal source coding [Kol65; Sol64; Fit66; 73], data compression with arithmetic coding [Ris76; RL81; ZL77; ZL78; FMG92), and the minimum description length (MDL) principle [Ris78; Ris84; Ris87; BRY98; GrüO5; HY01]. Lastly, this topic is intimately tied with sequential gambling and portfolio optimization, pointed out by [Ke556; Cov74; Cov91; CO96; Fed91].
A classical result in context-free sequential probability assignment is that the minimax regret is equal to the log contextual Shtarkov sum [Sht87], and the minimax algorithm is the well-known Normalized Maximum Likelihood. When the set of contexts is known in advance to the forecaster, namely, a fixed design setting, the minimax regret is equivalent to the log Shtarkov sum of the function class when projected onto the known set of contexts [JSS21; WHGS23).

---

A long line of work has focused on controlling minimax regret for rich classes in terms of covering numbers. [CL99; OH99] upper bounded the regret in terms of the (non-sequential) uniform covering number of the class. However, this complexity measure proved to be insufficient for obtaining optimal rates. [RS15] improved regret upper bounds by proposing a sequential covering measure. Thereafter, by utilizing the self-concordance property and the curvature of the log loss, [BFR20] further improved the upper bound in terms of the sequential covering number for nonparametric Lipschitz classes, through a non-constructive proof. [WHGS23] proposed a Bayesian algorithmic approach in order upper bound the regret using a global notion of sequential covering. Notably, both the global and local sequential covering numbers do not fully characterize the regret, and the algorithm in [WHGS23] is not minimax optimal. By relaxing the worst-case analysis, [BHS23] studied this problem within the smoothed analysis framework, where nature is not fully adversarial but constrained.
Online learning with respect to arbitrary hypothesis classes and the zero-one loss, in the realizable case, is known to be characterized by the Littlestone dimension [Lit88]. The agnostic case was ad- dressed by [BPS09; ABDMNY2IJ. Understanding sequential complexities in online learning with Lipschitz losses was extensively studied by 10; RS1 4a; RS14b; RST15]. Note that the logarith- mic loss is neither Lipschítz nor bounded. Recently, [AHKKV23] characterized online regression in the realizable case, for any approximate pseudo-metric, such as the lp loss.
2 Preliminaries
Notation. For positive integer K, let [K] == 21. K.. For fimite set K. with [C]] = K, we use A(K) denote the set of all distributions on K. We may identify K. with [K] (under arbitrary enumeration of elements in AC) and treat elements of A as vectors in R.K For a vector
R
and E [K]. let p(i) be the i-th coordinate of p. Let A A+ (K))
{p E A(K) p(k) > 0, K). For a general finite sequence (a:) i. we will use anmm to denote the sub-sequence (An..... am for any n S m and the empty sequence for > m. For any set A, let A = Uk20A be the set of all finite length sequences over A.
Sequential probability assignment and minimax regret. Let X be the context space and y' be the finite label space. In each round [7'] during the game of sequential probability assignment, the learner receives context F2 E X' from nature and assigns probability distribution Pe: E ()) to the possible labels. Then nature reveals the true label y/2 ) and the learner incurs a loss {pp, y:) = (é: (8.)). Throughout, the learner is required to predict nearly as well as the best expert from an expert class, which modeled as an arbitrary hypothesis class C {(X' x y)* x X + A())). More formally, the goal of the learner is make their regret with respect to F.
Rr(Fi TA. V1rT) Σ (()..v)) inf Σ (1.1).))))1)))))) FEF
as small as possible for all sequences x and y generated by nature, possibly in an adversarial manner. Here f V1:1-1) E A()) can be understood as the prediction made by expert f at round t using past observations (I1:--1, 11) as well as the fresh context di. The main focus is to study the minimax regret (F),), which can be written as the following extensive form
RT(F)=
sup inf sup- saup.... P 31 27 pr
sup inf sup (F:
where I, E X. E A()) and y E V.VE E [T. In light of this formulation, we can see that the minimax regret concerns both the learner and the nature to be adaptive, meaning that their actions can rely on the revealed history so far.
Remark 2.1 (Sequential vs non-sequential experts) Experts / as mappings from (X' x )²) x X' to (())) are sometimes called fully sequential experts [WHGS23] due to their ability to predict based on the past history. However, the literature (c.g. [RS15; BFR20; WHGS23]) often considers the more limited notion non-sequential experts, modeled as F C (X + A())), reflecting the fact that prediction made by each expert f is simply f(x) in each round t. In contrast, our results more general as our novel techniques can be applied to the more flexible sequential experts.
3

---

Multiary trees. The complexity of online learning problems stems from the sequential and adap- tive nature of the adversary, which we capture with multiary trees. Formally, for a general space A and a finite set K, an A-valued K-ary tree v of depth d is sequence of mappings V, -²-1 7 A for t [d]. A path in depth-d tree is sequence e (E1,...,EE)) E K!'. We use the notation Ve(E) to denote Ve(E1..... E(-1 1 for t E [d] and the boldface notation v(E) to denote (vi(e),.... v=())) E AA. Throughout we will only consider V-ary trees valued in either X or A ())), where the paths are denoted by the boldface We refer to valuul trees as context trees and -vauuul trees as probabilistic trees.
T'me-vvrying context sets. So far we consider the context set A' to be constant over time. But all of our results can be extended easily to allow for time-varying context spaces, Details this generalization can be found in Appendix C.
2.1 Prior work: the Shtarkov sum in context-free and fixed designs
Before introducing our complexity measure that characterizes (r), we review some prior set- tings where the minimax regret can be characterized by the well-studied Shtarkov sum. First we introduce the notion of likelihood of a hypothesis with respect context and label sequence, which plays key role in defining complexity measures and optimal algorithms.
Definition 2.2 (Likelihood) For (X y)" x X + A()) and length-d sequences 2nd X Vi.d E )dd the likelihood ((ui:l/rrdd)) is defined as
(r II (xia Vi (36),
where we use the compact notation f(FL 11 for f(1 .1........ T4 11
the classical context- free setting where X' can be thought of as a singleton, any sequential expert degenerates joint distribution over label sequences. Indeed, given any label sequence 11a--1 I+ [ ()) E (()) can be interpreted as the conditional distribution / assigns to the next label y/- We use (vi.a) I (1) to denote this distribution. Similarly, the learner's strategy also specified by joint distribution that is decomposed to sequence of conditional distributions P: (- AQ)). In this setup the minimax regret (FF is characterized by the Shtarkov sum [Sht87].
Proposition 2.3 ([Sht87)) In the context-free setling, for any hypothesis class F and horizon T, the Shtarkov sum Sy (F) is defined as
ST(F) Σ sup (((nr)) VETEYT feF
Moreover, the minimax regret is given by RF(F)= = log (T.F), and the unique minimax optimal strategy the normalized maximum likelihood (NML)) distribution given by
supSer (V(TT)
(omm(()1:T) EvirEy" supjer P)(K)r)'
YOuT E yr
To go beyond this classical context- aggiostcc setting and incorporate contextual information, prior work (e.g. [JSS21]) also considered easier problem than the aforementioned sequential probabil- ity assignment, by forcing nature to reveal the context sequence æ15 to the learner at the start of the game. This is known as the fixed design setting transductive online learning [WHGS23], where the goal to characterize the so-called fixed design maximal minimax regret
RDD (F)(F)== = sup inf sup... copp...inf inf sup Rr FITEET P1 Vi
gr
It is straightforward to see that after projecting on 31.7, the hypothesis class F again collapses to set of joint distributions over y specified by the likelihood function in Definition 2.2. Moreover, this set of distributions can be accessed by the learner from the start, so the fixed design setting can

---

be essentially reduced to the context-free setting. To more specific, for any f F,F, induces an expert in the context-free setting after being projected on I1.T, which is denoted by floir and
far (1)=+-1) = (( E A()), E (h=-1
and let Flar. == [/|m E Then given any predetermined 21.r, the learner is equivalently competing with F war the context-free setting. With the following natural variant of the Shtarkov sum, we can easily characterize RTD (F)).
Definition 2.4 (Conditional Shtarkov sum) Given a context sequence F1. E X", the Shtarkov sum of conditioned on Z1.7
ST (F(T))))
Σ sup Pr(y..(am.r)
MITEET fer
In fact, (r(((x1:r) is just the Shtarkov sum of the projected class Flayr in the context-free setting. The following result characterizes the fixed-design setting:
Proposition 2.5 (Minimax regret, fixed design [JSS21]) In the fixed design setting, for any hy- pothesis class F and horizon T, the fixed design maximal minimax regret is
RFD sup log ST(F(ILT)
ZITENT
and, given any context sequence Fır, the minimax optimal response is NML with respect to F Flaver
3 Minimax regret via contextual Shtarkov sum
Now we state one of our main results about the characterization of the minimax regret of sequential probability assignment. First we introduce the key concept contextual Shtarkov sum, which is natural generalization of Shtarkov sum in the context-free setting.
Definition 3.1 (Contextual Shtarkov sum) The contextual Shtarkov sum ST(Flx a hypothesis class F given context tree of depth T is defined
Sr(Fxx
Σ sup Py(y(x(y)). yeyr fEF
Just like the conditional Shtarkov sum, the contextual Shtarkov sum Sy (Flx) can be interpreted as the Shtarkov sum of the projected class Flx {flx : E F} where flx the induced context-free expert specified by
f := f(x(f((xxx)))) 11a-1) E A()), Vt E V1a )
where we have slightly abused the notation use x( x((1:t-1) denote the length-t context sequence obtained by tracing tree x through the (partial) path V1:1-1. Next we show that the minimax regret (F) is characterized by the worst-case contextual Shtarkov sum:
Theorem 3.2 (Main result: minimax regret) For any hypothesis class F. C {(X x 3)" X
(())) and horizon T,
RT RT(F) = sup log (F(x)
where the supremum is taken over all X-valued context trees x of depth T.
Since any context sequence Fi.r can be thought each level E [T] (i.e., x = 2,, Vy), we can find that the supremum over context trees in Theorem 3.2 strictly subsumes the supremum over context sequences in Proposition 2.5. Thus can see the separation between (TFF) and RED (F) is clearly exhibited.
special context tree that is constant in
The full proof of Theorem 3.2 as well as an overview are provided in Appendix A.

---

3.1 Applications: an improved regret upper bound in terms of sequential entropy
To illustrate the utility of our characterization in Theorem 3.2, walk through some examples where we are able to recover and sharpen existing regret upper bounds with relatively short proofs via contextual Shtarkov sum. As start, provide short proof in Appendix A.6 of the classical regret bound for a finite hypothesis class.
Proposition 3.3 (Finite classes) For any F C [0, 1]x and horizon T, RT(F) S log [F
Let us go back to the binary label setting with non-sequential experts, that is,
{0, 1} and
F [0, 1] and f(x) E [0, 1] is interpreted as the probability assigned to label by this expert f. We will show a regret bound that oupperforms the
tf-t---rt ones in [BFR20; WHGS23] with surprisingly simple proof. To proceed, we need the following notation. Given context tree x of {f ox: : F), where f ox the [0, valued such that
depth T, let Fox
(fox),(y) = f(x( Vy E y".
Next we introduce the definitions sequential lo covers and entropy.
Definition 3.4 (Sequential foc cover and entropy) Given hypothesis class F S [0, 1] and context tree x of depth T, we say a collection of R-valued trees Vx,a is a sequential cover of F x at scale a > 0 if for any ʃ E F,y E y²² there exists some v E Vx,a such that
[x(x((y)) - vy S a, Vt E [7].
Let the sequential Lo covering number Noo (F o x, a, 7) be the size of the smallest such cover. The sequential foo entropy of F at scale and depth T is defined as the logarithm of the worst-case sequential covering number: (F, == sup, log Nox (F ox,a,
Definition 3.5 (Global sequential Lo cover and entropy) Given a hypothesis class F [0, 1] we say collection of mappings Go C [0, 1|x² is globul sequential cover of F at scale a >> 0 and depth for any f E FITT E X", there exists some g E Ga such that
If(x)) g(Zx:)) S a, Vt [T].
Let the global sequential for covering number (F, a, T') be the size of the smallest such cover. The global sequential lxo entropy of F at scale a and depth T is defined as
HolF, a) =
a,,
Proposition 3.6 ([BFR20; WHGS23]) For any F C [0, 1)xt and horizon T, inf { (TTa + (F, aso
RT(F) < min
inf [ log(1 + 2a) + Ho(F or TT)
[BFR20]
[WIGS223]
where c 1og(3) (2) (3, 4).
2- (2)
It is easy to show that Hos (F, a") < Ho(F, but, in general, the two bounds in Propo- sition 3.6 are incomparable due to constants and different dependence on (more discussions on these bounds are deferred to Appendix C). Starting from the contextual Shtarkov sum, we are able derive a bound that combines the best of these two bounds:
Theorem 3.7 (Main result: sequential entropy bound) For any F S [0, 1|x and horizon T,
(F) < inf Tlog(1 + 2a) + Hoc (F, (F,
a>0

---

Proof For any scale a > and depth-T' context tree x, let Vx.a be a sequential cover of F x at scale with size No (FF x, a, T.. We can always assume Vx,a to be j0, 1]-valued without loss of generality because otherwise we can just truncate it without violating its coverage guarantee. Define the smoothed covering set Vx,c
i Vt [T], (x())
=(++a 1+2a e E Vx,a inspired by [BFR23;
WHGS23]. Then for for any f E Fyy E yT, there exists some u Vx such that (xxx a, vt E (T) and hence ë satisfies
f(xx(y)) (y)
1 - --f(xx(y))
20.
I 1 20.
1 (x
Hence
T Py(y|x(y)) = II - ((xxx)))( (1+ 2a)"
II [=1
and
Σ sup P)(y)x(y)) (1+ 2a)² y feF
Σ sup II (1-66)))
y
Be Vxca t=1
$ (1+ 2a)
Σ E (y)) (1 2a) 2 TEVxa
tm1
where the last equality follows from Lemma D.I, treating as sequential experts. Finally,
RT(F)= = sup
Σ
sup Pr(r|(()))
feF
S sup log (1 2a) | Tlog(1 + 2a) + (F, a. T)T).
Since our choice of a is arbitrary, the result follows.
3.2 The inadequacy of sequential &o covering number
We conclude this section with a discussion on the suboptimality regret bounds based on sequential covering numbers as in Proposition 3.6 and Theorem 3.7. Let us consider the binary label setting and the following hypothesis classes over the unit Hilbert ball X' IB2;
(w, x) + w E IB
Lin
JrAbaLin := {x + (w,, E B2}.
2
We can see that the sequential too covering numbers of FLin and JAbbLLin are of the same order for scales, thus the aforementioned results will yield the same regret bound for these two classes. However, we have (FFFLi Õ(vT) while (TAAbbaLi = (TT2/3) [RS15; WHGS23), which implies that the sequential for covering number, in its current form within the regret bound, cannot characterize the minimax regret.
worth mentioning that 5((TT) lower bound on (FLii) is achievable, via an i11/a²)
lower bound on the sequential fat-shattering dimension sfat, (FT.i)) combined with Proposition in [WHGS23]. The same lower bound also holds in the dimee--imeiiinall case, where IB is a unit d-dimensional Euclidean ball with d 2 /T [WHGS23, Footnote 6]. Our proof (Appendix A.7) of the next result works in both the infinite and finite dimensional (with T) cases.
Lemma 3.8 (S(VT) lower bound for the linear class Flin) For Flin defined as in Eq. (1) with Bi being the unit Hilbert ball or the unit d-dimensional Euclidean ball with d T, then
( > (RP((L 2 VT/4.
The proof of Lemma 3.8 is based on lower bounding the conditional Shtarkov sums (and hence the contextual Shtarkov sums) of FLin From Theorem 3.2 we know that the Õ(VT) upper bound holds for the log of contextual Shtarkov sums well but we do not have direct proof of this fact so far.
7

---

Algorithm Contextual Normalized Maximum Likelihood (cNML)
Input: Hypothesis class F, horizon T Fort t 1,2,... ..., T do
1. Observe context Ia E X
2. If sup (1 > 0, predict Ps E A()) with
supx ST (8 (Flx) by E
p.(v)
Eyey supx ST
Sz (F(x)
and otherwise set Pe to be an arbitrary member of (+)) 3. Receive label y/ E y/
End for
4
Contextual NML, the minimax optimal algorithm
So far we have settled the minimax regret of sequential probability assignment in a nonconstruc- tive way. Now switch the algorithmic lens study the optimal strategy that achieves the minimax regret. Remarkably, we show that the minimax optimal algorithm can be described by data-dependent variant of the contextual Shtarkov sum, which is named contextual Shtarkov sum with prefix.
Definition 4.1 (Contextual Shtarkov sum with prefix) Given sequences F1a E N yia E (7) and context tree x of depth T f, the contextual Shtarkov sum S S (F(x) Fon x with prefix Fıa, is defined as
t yY,tE
SP14 Mia (Flx) = E sup ST
yEyT-
Now we present our prediction strategy, contextual normalized maximun likelihood (cNML), which is summarized Algorithm the learner first checks whether sup ( > O since if that is not the case and sur (r( = 0, the cumulative losses of all experts in F have already blown up to +o0 and the learner only needs to predict any á E A+())) in all remaining rounds. On the other O, then
each round I, with Ti:t: V1;-11 as past observations,
hand, if sup P/ P/
max sup ST (M 1)) (Flx) > 0
yEy
and the P. given by Eq. (2) is indeed a valid member of A (shown in Appendix B) and is used as the learner's prediction. The following theorem shows that cNML is the minimax optimal algorithm, with proof deferred to Appendix
Theorem 4.2 (Main result: optimal algorithm) The contextual normalized maximum likelihood strategy (Algorithum 1) is minimax optimal.
To see that cNML is reduced to NML in the context-free setting, it suffices consider the case where sur Py (y1rr) > 0 since otherwise NML will simply assign O probability on this se- quence yırr and during the actual round-wise implementation of NML, it also predicts an arbitrary element from A (+)) in those rounds where sup, Py (11:111) = Now for any yır such that sup Py(yIr) > O, the prediction by eNML in each round is
Everr- sup Pf(y1x-1.8,))
pv()) Eyeyt ei1 SuP (3 Vy y
which can be summarized into joint density over y1.r by sup (y(TT) p(yIT) Eyi SUP (y()))
Recall that this is exactly the NML prediction Print (y).))

---

Remark 4.3 (Relaxations and efficient algorithms) One may wonder more efficient algorithms available when it is not casy to compute contextual Shtarkov sums with prefix. One solution is to apply the framework of admissible relaxation in [RSS12], which provides a systematic way of constructing efficient algorithms the cost of worse regret guarantees. Notice that the worst-case log contextual Shtarkov sums with prefix constitute a trivially "admissible relaxation" since they are the exact conditional game values.
Perspectives on contextual Shtarkov sums
In this section, provide further insight into contextual Shtarkov sums, defined in Sections 3 and 4.
5.1 Contextual Shtarkov sums through martingales
We can relate our characterization of the minimax regret to the more extensively studied sequential Rademacher complexity, which arises in online learning problems with hypothesis class F [0, 1]x and bounded convex losses like absolute loss. Specifically, the (conditional) sequential Rademacher complexity [RST15] is defined by
T faf (x((x)))))
My (F:x) = Ee sup Σ SEF
t=1
where x is depth-I' binary context tree and ε = (E1,..., .T) E {=1]" is a sequence of i.dd.
Rademacher random variables. A notable feature of (F; is that it the expected supremum of the sum of martingale differences, i.e., for any f. B (x,,(((x((()) (1.))) ....................... (r xx) also admits martingale interpretation. To see this, let F S ((X y)* x X A()))
0. Likewise,
and rewrite (FFx) for any context tree x:
Sr(Fix)
E sup Ps(r(((y) = By sup YEYT JEF
[((1 f(x)o(y), (ia)))))) fEF
where y .......;/7 ,.TT) ) is sequence of i.idd variables following the uniform distribution over V. Bna) Mt-1 = 1, and thus
(......,
is easy to check that B|
i (DI (Di-s((x:ss))) yıs (v.)) EE(T]
martingale with respect to filtration F. olui,... M)) 1 E (T). It would be of independent interest to study the contextual Shtarkov sums more quantitatively by developing new tools for such product-type martingales.
5.2 General Shtarkov sums
We can also interpret contextual Shtarkov sums as an instance of general Shtarkov sums, which are defined over sub- -uborbbbability measures.
Definition 5.1 (Sub-probability measure) set {p: [0, 1]3 a class of sub-probability
measures over finite set K. if
Σ p(k) 1 KEK
Due Lemma D.I, it easy that for any hypothesis class F ((X 31" X - A(2)) and depth-T' context tree they induce a class
Pxx = (P/()x())
that is class of sub--uuuueeee cubb-robability measures over ST Moreover, for any F, de -T- context tree x and sequences Ti:4 E X², V1st E Dt. the induced
P Promaveee = (Py(1i, ITLA 1pa x(-)) ff F

---

a class of sub-probability measure over yr since
((en = (111:/21a) S 1. yE)
Σ
Next introduce the notion of general Shtarkov over classes of babb-bbbbbblityy measures.
Definition 5.2 (General Shtarkov sum) Given any class of sub-probability measures over K, the general Shtarkov sum of P is defined as
S(P)
Σ sup ((k). KER PEp
With the notion of general Shtarkov sum, it is not hard to verify that the contextual Shtarkov sums with & without prefix can be interpreted as instances general Shtarkov sums:
Proposition 5.3 For any horizon T, E [T'] data sequence E X², ,3is E yt, and context trees x, of depth T, T respectively, we have
Sr(Flx) - S(PF)x),
ST S (Flx') - S(P (a)
It would be interesting to find out other instances of general Shtarkov sums that capture the com- plexities other online learning problems with log loss.
Discussions
In this paper. characterize the minimax regret and the optimal prediction strategy for sequen- tial probability assignment, generalizing the classical results in the context-free setting. Moreover, results are general enough to subsume the setting of multiary labels and sequential hypothesis classes, which has not been sufficiently explored before. Remarkably, our characterization holds for arbitrary hypothesis classes that may not admit the regularity assumptions implicitly required by prior works (e.g. [RST15; BFR20J).
For future works, it would be interesting study the minimax regret of specific classes more quan- titatively using our contextual Shtarkov sums. It is also intriguing to consider the setting of infinite labels. Although most of our arguments would go through under sufficient regularity conditions, more systematic study is needed. On the practical side, is important to develop algorithms that are more computationally efficient than cNML and with provable guarantees.
Acknowledgements
We are grateful to Changlong Wu for telling us about Proposition C.2 and to Zeyu Jia for insights leading to Lemma 3.8. We would also like thank Blair Bilodeau and Sasha Voitovych for helpful discussions and comments on earlier drafts of this work. ZL is supported by the Vector Research Grant at the Vector Institute. IA supported by the Vatat Scholarship from the Israeli Council for Higher Education. DMR is supported by an NSERC Discovery Grant and funding through his Canada CIFAR AI Chair the Vector Institute.
References
[ABDMNY2I]
N. Alon, O. Ben-Eliezed Y. Dagan, S. Moran, M. Naor, and E. Yogev. "Adver- sarial laws of large numbers and optimal regret in online classification". In: Pro- ceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing. 2021, pp. 447-455 (cit. on p. 3).
[AHKKV23]
I. Attias, S. Hanneke, A. Kalavasis, A. Karbasi, and G. Velegkas. "Optimal Learn- ers for Realizable Regression: PAC Learning and Online Learning". In: Thirty- seventh Conference on Neural Information Processing Systems. 2023 (cit. on p. 3). A. Barron, J. Rissanen, and B. Yu. "The minimum description length principle in coding and modeling". In: IEFE transactions on information theory 44.6 (1998), pp. 2763-2760 (cit. on p. 2).
[BRY98]
10

---

[BPS09]
S. Ben-David, D. Pál. and S. Shalev-Shwartz. "Agnostic Online Learning." In: COLT. Vol. 3. 2009, p. 1 (cit, on p. 3).
[BHS23]
A. Bhatt, N. Haghtalab, and A. Shetty. "Smoothed Analysis of Sequential Prob- ability Assignment". In: Thirty-seventh Conference on Neural Information Pro- cessing Systems. 2023 (cit. on p. 3).
[BFR20]
B. Bilodeau, Foster, and D. Roy. "Tight bounds on minimax regret under logarithmic loss via self-concordance" In: International Conference on Machine Learning. PMLR. 2020, pp. 919-929 (cit. on pp. 2, 3, 6, 10, 14, 15, 25).
[BFR23]
B. Bilodeau, D. J. Foster, and D. M. Roy. "Minimax rates for conditional den- sity estimation via empirical entropy". In: The Annals of Statistics 51.2 (2023), pp. 762-790 (cit. on pp. 7, 15).
[CL06]
N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge uni- versity press, 2006 (cit. on pp. 1.2).
[CL99]
Cesa-Bianchi and G. Lugosi. "Minimax regret under log loss for general classes of experts". In: Proceedings of the Twelfth annual conference on com- putational learning theory. 1999. pp. 12-18 (cit. on p. 3).
[Cov74]
T. M. Cover. "Universal gambling schemes and the complexity measures of Kol- mogorov and Chaitin". In: Technical Report, no. 12 (1974) (cit. on pp. 1, 2). T. M. Cover. "Universal portfolios". In: Mathematical finance 1.1 (1991), pp. I-
[Cov91]
29 (cit. pp. 1, 2).
[CO96]
T. M. Cover and E. Ordentlich. "Universal portfolios with side information". In: IEEE Transactions on Information Theory 42.2 (1996), pp. 348-363 (cit. on pp. 1,
[Dav73]
L. D. Davisson. "Universal noiseless coding". In: IEEE Trans. Inf. Theory 19 (1973), pp. 783-795 (cit. on p. 2).
[DS04]
M. Drmota and W. Szpankowski. "Precise minimax redundancy and regret". In:
IEEE Transactions on Information Theory 50.11 (2004), pp. 2686-2707 (cit. on
p. 2).
[Fed91]
M. Feder. "Gambling using finite state machine". In: JEEE Transactions on Information Theory 37.5 (1991), pp. 1459-1465 (cit. on pp. 1, 2).
[FMG92]
M. Feder, N. Merhav, and M. Gutman. "Universal prediction of individual se- quences". In: IEEE transactions on Information Theory 38.4 (1992), pp. 1258- 1270 (cit. p. 2).
[Fit66]
B. Fitingof. "Optimal encoding with unknown and variable message statistics".
In: Probl. Inform. Transm. (1966), pp. 3-11 (cit. on 2).
[FKLMS18]
D. J. Foster, S. Kale, H. Luo, M. Mohri, and K. Sridharan. "Logistic regression: The importance of being improper". In: Conference on learning theory. PMLR. 2018, pp. 167-208 (cit. on 1).
[Fre96]
Y. Freund. "Predicting binary sequence almost as well the optimal biased coin". In: Proceedings of the ninth annual conference on Computational learning theory. 1996, pp. 89-98 (cit. on p. 2).
[Grä05]
P. Grünwald. "Minimum description length tutorial". In: (2005) (cit. on p. 2).
[HY01]
M. H. Hansen and B. Yu. "Model selection and the principle of minimum descrip- tion length". In: Journal of the American Statistical Association 96.454 (2001), pp. 746-774 (cit. on p. 2).
[JSS21]
P. Jacquet, G. Shamir, and W. Sypankowski. "Precise minimax regret for logis- tic regression with categorical feature values".. In: Algorithmic Learning Theory.
PMLR. 2021, pp. 755-771 (cit. on pp. 2, 5).
[Ke156]
J. L. Kelly. "A new interpretation of information rate". In: the bell system techni- cal journal 35.4 (1956), pp. 917-926 (cit. on pp. 2).
[Ko165]
N. Kolmogorov. "Three approaches to the definition of the concept "quantity of information"" In: Problemy peredachi informatsii 1.1 (1965), pp. 3-11 (cit. on
p. 2).
[Lit88]
N. Littlestone. "Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm". In: Machine learning 2 (1988), pp. 285-318 (cit. on p. 3).
11

---

[MP98]
N. Merhay and M. Feder. "Universal prediction". In: IEEE Transactions on Infor- mation Theory 44.6 (1998), pp. 2124-2147 (cit. pp. 1)..
[MG22]
J. Mourtada and S. Gaiffas. "An improper estimator with optimal excess risk in misspecified density estimation and logistic regression". In: Journal of Machine Learning Research 23.31 (2022), pp- 1-49 (cit. on p. 22).
[OH99]
M. Opper and D. Haussler. "Worst case prediction over sequences under log loss". In: The Mathematics of Information Coding, Extraction and Distribution. Springer, 1999, pp. 81-90 (cit. on p. 3).
[OS04]
A. Orlitsky and N. P. Santhanam. "Speaking of infinity [iid strings]". In: IEEE Transactions on Information Theory 50.10 (2004), pp. 2215-2230 (cit. on p. 2).
[RS14a]
A. Rakhlin and Sridharan. "Online non non-parametric regression", In: Conference on Learning Theory. PMLR. 2014, pp. 2232-1264 (cit. on pp. 2, 3).
[RS14b]
A. Rakhlin and K. Sridharan. "Statistical Learning and Sequential Prediction". In:
2014 (cit. on p. 3).
[RS15]
A. Rakhlin and K. Sridharan. "Sequential probability assignment with binary al- phabets and large classes of experts". In: arXiv preprint arXiv:1501.072 (2015)
(cit. on pp. 2, 3, 7, 14, 25).
[RSTI0]
A. Rakhlin, K. Sridharan, and A. Tewari. "Online learning: Random averages, combinatorial parameters, and learnability", In: Advances in Neural Information Processing Systems 23 (2010) (cit. on pp. 3).
[RST15]
A. Rakhlin, K. Sridharan, and A. Tewari. "Sequential complexities and uniform martingale laws of large numbers". In: Probability theory and related fields 161 (2015), pp. 111-153 (cit. pp. 1-3, 9, 10, 14).
[RSS12]
S. Rakhlin, O. Shamir, and K. Sridharan. "Relax and randomize: From value to algorithms". In: Advances in Neural Information Processing Systems 25 (2012)
(cit. on p. 9).
[Ris78]
J. Rissamen. "Modeling by shortest data description". In: Automatica 14.5 (1978), pp. 465-471 (cit. p. 2).
[Ris84]
J. Rissanen. "Universal coding, information, prediction, and estimation". In: IEEE Transactions on Information theory 30.4 (1984), pp. 629-636 (cit. on pp. 1, 2). J. Rissanen. "Complexity of strings in the class of Markov sources". In: IEEE Transactions on Information Theory 32.4 (1986), pp. 526-532 (cit. on p. 2). J. Rissanen. "Stochastic complexity". In: Journal of the Royal Statistical Society: Series (Methodological) 49.3 (1987), pp. 223-239 (cit. on p. 2).
[Ris86]
[Ris87]
[RL81]
J. Rissanen and Langdon. "Universal modeling and coding". In: IEEE Trans- actions on Information T'heory 27.1 (1981), pp. 12-23 (cit. on 2).
[Ris76]
J. J. Rissanen. "Generalized Kraft incquality and arithmetic coding". In: IBM Journal of research and development 20.3 (1976). pp. 198-203 (cit. on p. 2). J. J. Rissanen. "Fisher information and stochastic complexity", In: IEEE transac- tions on information theory 42.1 (1996), pp. 40-47 (cit. on p. 2).
[Ris96]
[Sha06]
G. I. Shamir. "On the MDI. principle for iid sources with large alphabets". In: IEEE transactions on information theory 52.5 (2006), pp. 1939-1955 (cit. on p. 2).
[Sha20]
G. I. Shamir. "Logistic regression regret: What's the catch?" In: Conference on Learning Theory. PMLR. 2020. pp. 3296-3319 (cit. on p. 1).
[Sht87]
Y. M. Shtarkov. "Universal Sequential Coding of Single Messages", In: Problems of Information Transmission 23 (3 1987), pp. 3-17 (cit. pp. 1,
[Sio58]
M. Sion. "On general minimax theorems". In: Pacific Journal of Mathematics 8 (1958), pp. 171-176 (cit. on p. 15).
[So164]
R. Solmonoff. "A formal theory of inductive inference. I", In: Il Information and Control (1964), pp. 224-254 (cit. p. 2).
[Szp98]
W. Sypankowski. "On asymptotics of certain recurrences arising in universal cod- ing". In: PROBLEMS OF INFORMATION TRANSMISSION C/C OF PROBLEMY PEREDACHI INFORMATSII 34 (1998), pp. 142-146 (cit. on p. 2).
12

---

[Vov95]
V. G. Vovk. "A game of prediction with expert advice". In: Proceedings of the eighth annual conference Computational learning theory. 1995, pp. 51-60 (cit. on p. 1).
[WHGS23]
C. Wu, M. Heidari, A. Grama, and W. Szpankowski. "Regret Bounds for Log-loss via Bayesian Algorithms". In: IEEE Transactions Information Theory (2023)
(cit. on pp. 2-4, 6, 7, 15, 25,26) 26).
[XB97]
Q. Xie and A. R. Barron. "Minimax redundancy for the class of memoryless sources". In: IEEE Transactions on Information Theory 43.2 (1997), pp. 646
657 (cit. on 2).
[XB00]
Q. Xie and A. R. Barron. "Asymptotic minimax regret for data compression, gam- bling, and prediction". In: IEEE Transactions on Information Theory 46.2 (2000), pp. 431-445 (cit. on p. 1).
[ZL77]
J. Ziv and A. Lempel. "A universal algorithm for sequential data compression".
In: IEFE Transactions on information theory 23.3 (1977), pp. 337-343 (cit. on p. 2).
[ZL78]
J. Ziv and A. LLempel "Compression of individual sequences via variable-rate coding". In: IEEE transactions Information Theory 24.5 (1978), pp. 530-536
(cit. on p. 2).
13

---

A Proofs for Section
Notations. When the context and label sequences I:77 71:7 are clear from the context, we may use ft denote the probability vector / [ V/tt- E A()) produced by hypothesis for notational convenience. We also adopt the notation for repeated operators in [RSTI5; BFR20),
time
denoting Opt ... Optr!'--] by (Opt,)?- :.. For any discrete distribution P and discrete random variables X,Y, let 11 (P) be the entropy of P and (X be the conditional entropy of X given Y.
A.1 Proof overview of Theorem 3.2
Before presenting the proof of Theorem 3.2 in full details in Appendices A.2 to A.4, we give high-level overview here.
The proof starts from swapping the pairs of inf and sup (after randomizing the labels revealed by the nature) in the extensive formulation of (F) move the dual game, where the learner predicts after seeing the action of the nature. Trivially the value of this swapped game is a lower bound for (F), and after rearranging we get that the value of the swapped game = sup (rr::((R((:::()) x(y), S (F()),
x.P
where the supremum is taken over all context trees x and probabilistic trees p. of depth T. Also Ey~p means the nested conditional expectations (y))) p3>>))( ... pp
Similar to the proof of Lemma in [BFR20] for the binary label setting, apply the minimax theorem with a tweak that we devise to handle multiary labels to derive that
(F) sup (F- p(y), x()),
(3)
x.P
under some mild regularity condition for F. A key observation is that the supremum over depth-T' probabilistic trees p is equivalent the supremum over joint distributions P over y", Based on this observation and some algebra, for a fixed context tree x, the supremum over p in Eq. (3) is
H(P) + Ey~p[ sup log Py (y)x(y))) PEA(T))
sup
feT
The value of this maximization problem can be easily computed to be
log
Σ sup Pr(y|x(y)) = log (F
FEF
Thus,
RF(F) sup E Eymp RT (F; p(y), x(y)
x.p
=sup sup H(P) + By-rl sup log Py (y(y)x(y))] = sup log ST (Flx).
x PEA(YT)
FEF
x
However, Eq. (3) is not guaranteed when there is no assumed regularity condition for F. To get away from this, prior works have assumed particular hypothesis is included in F such that the enlarged class allows for the minimax swap [RS15; BFR20J. Nevertheless, even adding a mere hypothesis may lead suboptimal analysis for some classes F. say when R2 (F) of constant order. To completely get rid of any regularity assumption and obtain unified characterization of the minimax regret for arbitrary class F, we provide a novel argument as follows. For an arbitrary class F, we study smooth truncated version of it, denoted by J for any level 8 E (0, 1/2), such that F6 always validates the use of the minimax theorem and hence RT supx log ST (F=1)x (x). Then we give a series of refined analysis comparing the minimax regrets and contextual Shtarkov sums of F and F that yields
(T(F) < RT Toog(1 + (216 = sup log Sr ST (x) + T log(11 + (D16))
log
sup sup (F
C(T, (1)) + T log((1 + (D/)))
where C(T.1)) < oo is a positive constant that only depends on T and | Sending 8 0+
will conclude that (TFF) suup log (rFF) which finishes the whole proof as we already have (F) 2 supx log (F(x) from the start.
14

---

A.2 Minimax swap
As standard in online learning literature, we will first move to dual game after applying minimax swap at each round of the game. Under mild assumptions, the value of the original game coincides with the that of the swapped game. More specifically, we have:
Lemma A.1 Whenever F satisfies that for every sequence Fur E X Uir E y?.
T
inf JEF
((
< 00,
(4)
we have that
(r) = sup Eypp Rr P (F
(5)
X.D
where the supremum is taken over all X-valued Y-ary trees x and A())- V'ary trees p, of depth T. Also Ey-p means the nested conditional expectations Egiopily) E (y)>)2())
Eyrrspr(y)
To deal with the unboundedness of log loss in the proof, we introduce the following truncation method inspired by [BFR23; WHGS23), generalizing the one in [BFR20] which was specific to binary labels.
Definition A.2 (Smooth truncation) The general smooth truncation map A()) - A(Y) is defined such that for all p E A()) and y e V
p(v) + 6 (v) 1 1/18'
given threshold 5 E (0, 1/2).
is easy to check that rp()) is indeed valid member in A()) and 73 (v) ( ())8), (1+ 6)/(1 + D/ Moreover, it is not hard to verify that To (a()))) = {p E A()) p(y) E 16/(1+ (D15), (1 + 5)((1 + [D([6)], vy E V). We will use ()) denote this image set (a())))).
Proof of Lemma A.1 Fix å E (0, 1/2). By restricting the learner's prediction P. to A (d(),, get an upper bound on (F):
T
T
RT(FF) < sup inf
sup me ())
Σ 1=1
inf JEF
Σ e(fe.
de
t=1
T-1
T inf feF
sup æt ())
inf
sup de
sup
inf (2) pr
sup E upr
Σ
Elpe, vz)
Σ
1=1
or
Now we can apply Sion's minimax theorem [Sio58] to the function
T E(ec. v)) - inf Σ JeF t=1
A(pr. pr) = Eyropr
v0)
derive that
inf ()) p)e
sup
A(pr,Pr)
sup prEA()) (
inf A(pr,Pr)
This is because:
1. A(rr, Pr) is convex and continuous in pr over the compact A A and
2. A(TT,P7 concave and continuous in pr over the compact A())), which is further due to that A(fr, .P) is linear in pr and is bounded given Eq. (4).
15

---

Hence
T-1
Rr(FF) -
sup inf #e (E)
sup
supsup inf oT pr (rEA
Byr
inf SEF
e(tt, vt)
T-2
sup inf ze (2)
sup
sup
inf
sup E 1mr
2T-1 pr ())
T
[
Elpe, Br) + sup sup zr
inf ())
Evr E(pr, - Eur
inf Σ [ffi
JEF 1=1
Pr
Again the order of inf pr- and sup
pr 1EA()) with respect
B(pr-1,Pr-2) = E can be swapped due to the same reason as above, leading to
Ber---pp- llpr Ue) supsupl inf
Bvropr l(pr, yr)
Eyr
inf
Σ
[ft,
2T (rE)
JEF
T-2
RF( <
sup inf Iy (D)
sup
sup sup inf
E Byr-irer-1
Ve
1=1 -T - po -r- EA)
Efpe Me) + supsup 2T
inf (rE
inf Epr ((T, VT) Eyr upr JEF Σ [(f.vv)]
T-3
(suu inf MEEA
sup
sup
sup Eyr 2-P 2 pT-2
in
()) de
c=1 2T
E(pr, ye)
sup sup ør-1
PT 1T-))))(3) Evr- ((pr-1.
inf
E Eyr-pr ((pr, Eyropr inf JEF > ((fe. 3.]].
E sup sup
inf (rE
Repeating this procedure through all T rounds yields
RT(F) S
suussup Ey mp
sup t=1 SEF
Σ
inf $EE (2)
Ens.n yr)] e(Jes wr)
By Lemma A.7, we know that we do not lose too much by restricting learner's prediction to A ()):
1 sup SEF
T
(x) < /sppsup Eyeup
Σ
inf
E up (( we)1 - E(Sc. + 12//8T.
Ze Pt
t=1
1=1
Sending 8 + a++ on the RHS of the above inequality, we get
RT(F) < suup Eys-p ze Pt
inf Ey, -p (e v:)] E(fe, e(Se.vi)) vi) P.
sup 1e1--fe FEF
It is easy to that the RHS of the above inequality, the inner infimum Pe A()) is achieved at P. = pt due to the nature of log loss. So
T
T
Rx(F) <
sup sup Ey, Pe 5t no
sup SEF
Bygep [e(pe, e(fe. v01
sup Expp RT (F:p()))))x()))
x.p
where the last equality we use the compact notation of trees further simplify our expression and this concludes the proof.
16

---

Lemma A.3 For any hypothesis class F and horizon T, sup (F: x(y). sup log ST (F(x).
(6)
x.p
is implied that whenever F satisfies Eq. (5), we have
RT(F) sup log (F(x).
Proof of Lemma A.3 First
that the outcome sequence V1.r generated under any tree is the same thing as y1.r generated by its associated joint distribution over y"" and vice versa. So we can replace the supremum over trees p the LHS of Eq. (6) by the supremum over joint distributions P over )z2 Hence, sup Ey-p (FF() x.p
sup Ey ((T((FiP())) ((x)))))
x.P
sup ((Po v1) inf Σ (fr. 86) FET
x.P
where Pt denotes the conditional distribution Pi(-IV1:-11 E A()) of y under P given V1.-11 Now fix the context tree and distribution P. Then H ((yl 1). So Ey- P ((Pt. = Ei= (Vveliia = H (P). Further notice that Σ ((e.vv))
that Ey-p)e(P,,)) 9t)]
inf JEF
inf (-log (U1:T(aar = sup log ((ViT(laT:))) SEF
JEF
So naturally we define the map Fx :TT R U (-00] by
Fx(y) = sup log (y(xx(y)), /EF
and then we see that
Ey P
Σ ((PL,)))
Σ (((f(= H(P) -(P)) By-r/Fyy)) fEF
inf
For any given tree x, notice that the optimization problem sup
H(P) + Ey-
PEA(Y))
is actually maximization problem in the form of maxpe H(P) + (P, v), where is some D dimenninaa vector. According to the conjugacy between negative entropy function and log- sum-exp function, the optimal P* is given by
exp(Fx(y))
SUP Pr(yix(y)) Vy YT.
Pd (y(y) Ey exp((x(y'))
Ey sup P (
Note that the above formula for pa also valid when Fx(y) be supported on (y E y Fx(y) > -o), and (y()) cannot be -o for all due to Lemma D.I. The associated value of this maximization problem is
for some y, since P should
log Σ exp cxxp(F(()) = loog Σ
sup Pr(y)x(s11) fEF
Therefore,
T
T ((se.v))
sup E Ey-p
sup Eynr x.P
((Pt.v)) inf JEF
Σ
x.P
supsup P
H(P) + Ey pl [Bx()))]
ssup log
Σ
sup sup (xyp((()))())
fEF
= sup log (xxx).
17

---

the proof of Lemma A. if we do not restrict the learner's prediction and simply swap the order of inf and sup to produce an inequality at each time t, we will reach the following folklore result.
Lemma A.4 For any hypothesis class F and horizon T,
RT(F) 2 sup Pupply-ppTTrppa
Proof of Lemma A.4 To get Eq. (7), simply need to reverse the order of sup and inf at each time in the extensive formulation of minimax regret and produce an inequality:
RF)
sup sup- 21
suup inf sup Ry (F; FI:TI, V1:T) or
P1
Pr
yr
sup inf sup Pr 8
( we)
inf FEF
Σ
T-1
sup inf sup P
sup inf sup Eyr -pp or pr pr
E(pe, vb)
inn fer effr
ge
t=1
T-1
T
T
sup inf sup Se
supsup inf Ey upr
Σ
Elpe, v1)
inf fEF t=1
Σ
fir
Be
or pr
sup inf sup Pt
E(pr, we) + supsup sup inf Byrorr llfr, vr) 27 pr
inf Eaer ppr
pr
PEF
Iterating the argument and rearranging terms as above, will get that
T
T
RT(F)> 2
sup sup E 1ef
sup JEF
inf E pp [e(pe, e(fe. vi)
Pt
[=1
T
sup sup Eg Pp:
stpp 1=1 fEF
Eycre [e v))l - E(fe.80)
sup Ey-p P (F)))))))((()))) x(y,,)) x.p
A.3 Smooth truncated hypothesis class
To remove the reliance on Eq. (4), we introduce a smooth truncated version of J that always satisfies Eq. (4) and study its minimax regret well contextual Shtarkov sums, compared to those of the untruncated class F. To be more specific, we will apply the smooth truncation map to hypotheses: for any d (0, 1/2) and f (X' x ")* X A(D),, use f to denote its smooth truncated counterpart
f: for any hypothesis class F. we use F to denote the corresponding smooth truncated class Tş o F = [Ts :f: E FJ. easy to verify that any smooth truncated class J satisfies Eq. (4) and hence
RT(F*) = sup log ST (T(F
Next we control the effect of truncation on the minimax regret.
Lemma A.5 For any F, T and E 102),
Rr(F) S (F* T log(1 + (2)1)).
18

---

Proof of Lemma A.5 Fix threshold ò E (0,1/2) and hypothesis f. By Lemma A.7, for any given sequences 2TT VI,, there is
T
Σ
(mia Via Va--1). vb)
Σ Vi- S T -log(1 + (316)).
(8)
Then, for any sequence of predictions pi:r.
E(pr, Ve)
inf fEJ
Σ (t)
T
E(pr, Vo)
inf Me
Σ
Elft vr) + T log(1 + (2]6)
t=1
1=1
Rí (F PIIT,, FIT, (1:T)
+T log + (216))
which concludes the proof.
Lemma A.6 There exists constant M() < oo that only depends on T such that for any frau
X², yur D" and 8 (0, 1/2). Ps (VITTTET))) S (y - (.T
Proof of Lemma A.6 Fix threshold 8 (0, 1/2), hypothesis f and sequences zı.r, Vr.r Then
fe(y)) +
II (wx)
II
1+ D/18
t=1
(felv) +
II f(())) + EII fe( + ... 8" e't
< II fA(ve) +8.M((T
(y ( + 5 M()),
where we set M(T T
( + 9
( since (3())'s are bounded by 1.
A.4 Putting together
Now we are fully prepared to finish the proof of Theorem 3.2, our main result Section 3.
Proof of Theorem 3.2 By Lemma A.6, we have that for any context tree of depth T,
Σ sup (y)())((y)) < Σ sup Py(vix(y)) + M(T) -
vEyT fEES
yEyT JEF
Thus
Rr(F*) = sup log Sy (F (x)
ssup
sup py((y((())) vEyT fer
Σ
< <suplog
Σ sup P/ +8 D weyr JeF
= log
sup Σ sup Py(y(((y)) +8 + D yeyr fEF
19

---

Together with Lemma A.5, we get that for any å (0,1/2),
RT(F) & log
sup Σ sup ( + M(T) 12977) + 1og(1 + ())6).
(9)
x yEyT ler
After sending 8 + 0+ the RHS of Eq. (9),
RT(F) S log
sup Σ sup Pr(x(x(y)) sup log (F YE)T fer
Recall that we have RT(F) 2 supx log Sr x) from Lemma A.4 and Lemma A.3. So finally,
Rr = sup log Sr
A.5 Additional proofs
Lemma A.7 For any E A()) and E (0,
((Ta(p).v) & E(p, y) + log(1 - (316] s E(p, v) + 1316, Vy E y.
Proof of Lemma A.7 By direct computation, for any y E V
ply)
((TT(p).g) - E(p,)) log
p(y) + (1+ + (216))
log(1 [)188
A.6 Proof of Proposition 3.3
Starting from Theorem 3.2 that (F sup, log (F)x), we have
(F) log
Σ sup Prlyix(t)) FEF
S sup log
Σ Σ Py(y|x(y)) y FEF
sup log
ΣΣ ΣΣ Py(yl((y))
-log [F].
JEF y
where the last equality is due to Lemma D.I.
A.7 Proof of Lemma 3.8
suffices show that (FLLi)) 2 VT/4. In particular, we only need find some context sequence F1.7 such that log (T(Tiin (m).)) 2 vT/4 due to Proposition 2.5. Here we pick Tur such that I; are unit vectors and 1 whenever t * t'. Such sequence exists because the
20

---

dimension of Bg no smaller than this way, for each possible label sequence V1. E {0,1)" can that the fw E Jelin that is indexed by
2 VT
w
Ft
achieves likelihood Psu (V1TT/21:))
1+1/VT Therefore,
1+1/vT - -(1+1/VT),
(r (1:T)
Σ
sup (y
Σ
31 E fEFLin
which implies that R (FFin) log ST (T(Fiin (TT)
T log( + 1/v/)) 2 VT/4 for all 7 1.
B Proofs for Section 4
Notations. Again we may use fi to denote the probability vector f( 01---1 E A produced by hypothesis f at time when the context and label sequences T1:7; V1.r are clear from the context. For context tree of depth - and path y E yT we re-index x(y) as (y).. XT (y)) whenever it takes the last 7 t entries of the entire context sequence. And we do the same for the probabilistic tree p as well. That is, whenever y (ge+1...... ./) E y takes the last entries of the whole label sequence and 9t+1 ~ Pt+1(y)..... yr ~ Pr
then we will denote this label generating process by
B.1 Proof of Theorem 4.2
Recall that the minimax regret is
Rr-(F) =
suppiff inf sup Pe
Σ :=1 t=1
E(pe v.)
Σ (ff(f11 ((..aa.,.--)),.....). v)) JEF
inf
01:-1))
Through this extensive form of the minimax regret, know that given Titt V11-11 the minimax prediction pt at round t is the one that minimizes the following expression over all P. E A()):
sup
sup inf sup Pa Vo
Σ (p..wa))
inf Σ FEF
(10)
Define
T
G(F, V1a)
sup inf sup De
a(p.. Vo)
inf feF
Σ
smt++11
8=1+1
and now
it argmin sup ((pr, ve) + G(F, v1:))
(EE(Y) d1
The crux of the proof is to show the following:
Lemma B.1 For any hypothesis class F and sequences Fia E X', V1a E e
G(F, JF,, B1.e) = sup Spaiiii (Flx).
The proof of Lemma 1.1 is done by essentially following the same strategy in Appendix A since G(F, (1:1) admits similar extensive form with the minimax regret RFF. For completeness we provide its proof in Appendix B.2. Given Lemma 1.I, have
07 = argmii sup E(pe, W.) sup log ST S wis (FIx)) A.EA()) g+
sup ST S (F(x)
argmin sup log (EA())) B:
pe(y))
We apply the following result to solve the above program:
21

---

Lemma B.2 /MG22, Lemma 15] Let 9 y + [0, +ool be a measurable function such that lyg(y)d E (0, +o0). Then,
s(v)
log (og((,,())w(d))))
inf sup log
(11)
P yEy
ply)
where the infimum in Eg. (11) spans over all probability densities p y - [0, +00) with respect to μs, and the infimum is reached at
p
Sy gly)du
Letting g(y) supx ST STmnooe-111) (Flx) [0, 1] and j be the counting measure on the finite space ), we can apply Lemma B.2 whenever not all g(y)'s 's are O. In this case, we solve that
g(v)
supx St Cl (1 (Flx)
(v) Eveyg(o") EVER supx
(Flx) Vy E V.
ST Stm
On the other hand, if g(v) 0, Vy E y, then any P such that (r()) 0, vy V, is an minimax optimal prediction. Moreover, implies that P/ = 0, vf E F. This is because for arbitrary context tree x,
Σ Σ Dt yEyТ-
Σ
Py(VialFaa)
(y (1+-1)-
So the cumulative loss for each expert f up round t 1 already blows up too and the learner only needs to predict an arbitrary ò E A+()) in all remaining rounds to achieve (r: Fi.r, (1.r) -00
Overall, we can see that the minimax optimal prediction Pt A()) at round & given Ti.t V1a-1
supx ST
(Vi (Flx)
(v)
Vy E
Eneyy supx ST
(Flx)
if there exists y E y such that supx ST (V (Flx) 0. Otherwise, select of to be an arbitrary element A *))) (and so do all remaining rounds).
B.2
Auxiliary lemmas
Recall that for any hypothesis class F and sequences 214t E X' Bia E yt,
I
T
((F, V1:)) =
/sup inf sup F. de +=t+1
((p.))a)
inf fEF ==1
Σ
(( 11:
s=t+1
sup inf sup E Bys P.
(pe.
inf feF
((
a=t+1
s=t+1
To prove Lemma B.1, we need the following lemmas.
Lemma B.3 For any hypothesis class F and sequences aia X Viat y
T
T
C(F,Iuu VIa) 2 sup E Eymp
Σ
E y. <v
(x) ((p.)))
inf Σ fef
Elfof E(foryz)
(12)
x.p
==1-1
8=1
And whenever for every I+ XT-1
W141 -t-,, it holds
T
inf
e(f(I1:: V1: (1:s-1). < so,
(13)
JEF
1
22

---

then
T Ho)
sup By~p
Σ ==
E
(
inf fer
Σ
((fs
(14)
x.p
Proof of Lemma B.3 First we that similar to the proof of Lemma A.4, we can reverse every pair of sup over ps and inf over P. in the extensive formulation of G(F, Tias y1:)) and rearrange terms to obtain
T
T Σ
Uad) 2
supsup Ey Fympp,
inf yp, [e(fs. Uo)]
inf JEF s=1
(Uss.aa)
2o
Pa
sme+1
and again due to the nature of log loss,
T
T
G(F,Tia: 2
sup sup E Zo
E Bp ((pp Σ inf JEF
{(fx Bal
pp
Po
s=1
sup
Σ
inf JEF
Σ
([anvaa))
x.P
where in the last step we compress the expression using trees (of depth T t) and Eq. (12) is proved.
To show that the minimax swap is valid under Eq. (13), we follow the same strategy as in the proof of Lemma A.1 by restricting the learner's prediction P. to ()) for any threshold 10,) which yields
G(F, S sup E Eysrps
Σ
inf (>)
[((ps) I
inf JeF
Σ
{ffs Uo)
8=1+1
s=1+1
s=1
I
sup E Eyenps pp
inf En [e)( - inf
Σ
E(f.: vo) + 1218T.
P.
e=(+1
==1+1
feF ==1
So Eq. (14) is proved by sending d + 0+ on the RHS of the last inequality and the established Eq. (12).
Lemma B.4 For any hypothesis class F and sequences Fiat E X Via E yt,
T
sup E x.P
E
feF Σ ((S.)He) = St Stini (Flx).
inf
Symp
a=t+1
Proof of Lemma B.4 The proof follows that of Lemma A.3. By replacing the probabilistic tree by the joint distribution P E -t) we get
T
T inf
sup Ey x.p
Ey (v)))(((ppP)))...))))))
Σ [Va fEF am1
y
sup Ey P x.P
e(Ps, ys)
inf FEF
Σ
smt+1
=sup sup PE)
H(P) + Eynp
sup log Py (yins yl x(x)) fEF
Similarly, for any fixed x, define the map FELaMt
yT - U (-cc) by
F (y) = sup log y
JeF
23

---

and now we solve
sup PEA(Y 9)
H(P) + Ey-PPFF Fanun (y)].
If there exists some y E y² such that Ex (y) > -0, then the optimal Pa is given by supser y
exp( F (y))
P'(y) Ey exp( Fx (y)))
"xy sup sup P/ (11::) Flyxx(y))) vy )²-
and then
sup By
E ~p (y)
Σ (o)e SEF
inf
x.P
==++1
sup =su
(P)) + Ey p Fr (y))
P
=sup log Σ
sup
P ((rr,,(()))
JEF
=sup log (F(x)
However, if ( (y) -0 for all y, then it implies that for any context tree x, path y, and F, Ploss 0 and hence,
sup Ey-p x.p
SupEy~D
Σ s=t+1
E (y) vo)] inf [llerraa))
fEF a=1
= sup PE)()T-1)
sup
H(P) +
00
sup log
sup Plyy, Σ JEF
sup log ST
S (Flx),
which finishes our proof.
Now we are able to prove the key result Lemma B.1.
Proof of Lemma B.1 Fix any hypothesis class F and sequences 3ia E X , Uha E yr, First we know
G(F, Tiat Via)) 2 sup log ST S (Flx)
due to Eq. (12) and Lemma B.4. For the other direction, let fix any threshold value ō E (0,1/2) and then
G(F, vr.) s G(F F1.1 T log(1 + (D/18)
sup log ST
s (F x) + T log(1 (218)
sup log
Σ
sup Pp Ppol T -ogg[1 (1 (218)
yeyT fEFFS
I sup log
Σ
sup Pf P/(ena + M(T) (D1T) + T log(1 + (1())
-E JEF
=
log
sup Σ
sup feF
8 M(T) D2FT + + log(1 + (1))),
yEyT
where we have applied Lemma A.7. Lemma B.3, Lemma B.4, and Lemma A.6 accordingly. Simi- larly, we send 8 + o+ on the RHS of the last incquality and get
G(F, 01., V1.) < sup log
Σ
sup Pr(yia, ylura, sup log S a (Flx),
-EyT-
which concludes the proof.
24

---

C Additional discussions
C.1 On the time-variant context space
In this section we generalize our analysis the setting where the context space can evolve over time.
We model time-varying context sets by sequence of maps X4 : X x y + 2 t E [T] as in [RS15: BFR20]. In each round t, instead of picking any context from X, the nature now required to only choose from X₂ (2 1;:a-11)) C X. Then the minimax regret with respect to (X, rewritten as
Ry = ( sup
T Rr Z1. F1-ry/rr)).
inf sup Pe
(
1=1
A context tree x consistent with respect to (Ke).etT) for all e [T] and y E y", xy)
X (21--11 1/1--1) Then our results in Section 3 and Section 4 can be generalized simply by replac- ing the supremum over all context trees (of depth 7) by the supremum over all consistent context trees. For example, we will have
(1
sup
log (F(x).
X:X is consistent
C.2 On the global and non-global sequential cover
Now go back to consider the usual setting of binary label and constant experts, i.e., y = {0, 1} and F S [0, 1| As mentioned in Section 3, previous works [BFR20; WHGS23) provided re- gret upper bounds based on Lx sequential entropy. More specifically, both of their bounds are in the form of ((infaso(a'' + HFF ar T))), with H(F a, T) being either the non-global entropy Hoo () the global entropy (F a, T". is then natural to ask which one of these two bounds is tighter.
is straightforward to prove that (J a, I') is no larger than Hg a, T'). In fact, the gap between them is at most polylog factor, as state and prove below.' The proof of (F, a. 7) < (F a, T) is also included for completeness. Before stating the results, we introduce the definition of sequential fat-shattering dimension.
Definition C.1 We say an X'-uuleed binary tree x depth is a-shattered by a class F S 1] for some >> 0, if there exists a [0, va-lud binary tree of depth d such that
vy E (0. 1)", ff E F, s.t. (2gr - 1) (f sy 2
a vt Ed] [d. 2
In this case, is called the witness of the shattering. The sequential fat-shattering dimension of F scale a, denoted by (fat,(F), is the largest d such that some depth-d context tree is a-shattered by F.
Proposition C.2 For any scale a > 0, we have
(o a, T) 2 minfT, sup sfatza (F)) log(2). a'>a
Therefore, together with Hor Ha, & Ho(F,a, and the folklore No(F,a,77 < (sffat (F) (og((T/));, we conclude that the regret upper bounds O(ifasolaT + H(F a, T)}), H (Hoo, Ho), differ by at most polylog factor.
Proof of Proposition C.2 Fix any a' > a > and let da denote sTat22 (F)). Then there exists context tree x and a witness tree s, both of depth do', such that for any path y {0,1)
there exists an f E JF such that
Vt [d (2v-- 1) (f(x sy())) a'
(15)
'This result and its detailed proof sketch were communicated to the first author by Changlong Wu. The argument here differs only in minor details that we introduced, perhaps unnecessarily, to arrive at a rigorous proof.
25

---

Let Vx be an arbitrary sequential lo covering of F on x. Now we select a path y and a sequence of subsets V2d S Vx,at [da]] in the following recursive way. Define V2,0 Vx.a. For each 1 E [da'], choose yt E {0, 1 such that 2t, - E {-1,+1} is the minority among all (gn(t1())=11) sc(vnc-1)); E X.a
(tt-)) (ignoring those of 0's). Finally update Vadd {ur
Vila=)) sggg( (1 - sc(vi=-1)) = 2y/ -1.. 13.
First argue that, if there is any time t' [da'] such that (-(--1) * 0, vilt) 0, then Vx,a not a valid cover of F on x. Otherwise, recall we have selected yi...., y2 arbitrary Ye E {0, ]]. By Eq. (15) can find some f F such that (2y, - 1) (f(z,
Now pick an
s((yaa1)) > a, Vl E [t"]. Since Vx,a is a covering at scale a, there is v E Vx such that (vr(y) sr()))
x,a to match the minority sign of (x)( I a, Vi [d*]. This implies that (xn(s((x+()))
sgu(v.(y) sx(y))
2ye- - 1, E [t]. So we can always find some member of v(('-1) ve (Vi=' Sy
vilt'-), which means that Vi(() * 0 and yields a contradiction.
Now we know that |V2,0 2 vt E [dar]- By design |V S IV2t="11 1122, Vt E [day], so we must have |Vxnl |V2,a 2 24 As the choice covering is arbitrary, the covering number (F x, a, a, day) is also lower bounded by 2d and hence (S, a, dar) 2 da' log(2). If
su sfatza (F) - T, then we get that
Hox (F, N sup Ho0 (F, a. stat (F)) sup sfatza (F) 1og(2).
a'sa
a'sa
If there is some a' > such that saat (F) 2 T, then
Ho, a, Hox (F, a day) T log(2).
Combining these two cases together, we have HF, a, 2 min sup sfatz (F) log(2). a'sa
Proposition C.3 Let Ga be global sequential c-covering of F defined in (WHGS23). Then for any context tree x, there exists a sequential cover Vx of F o x at scale a with |Vx,al S (Ga This implies that Ho a, s log Gaal-
Proof of Proposition C.3 Fix arbitrary context tree For any g E Ga. define the [0, ]]-alued tree 2dl by (y) = (y)r+(y)), vt E [T]y E yT" Now let Vx,a= = (v9 g Ga and we will show that Vx,a is indeed sequential cover of
scale a.
For any e F and y y", tree yields a length-T sequence (yr(() and by definition of the global sequential covering, there exists g E Ga such that (f()) - g(xr+(y)) & a, a
So by our construction of Vx.., v E Vx.x holds (xx of (y) (x) g(x1:(y))) a, a [T].
which yields our claim after observing Vx,al S (aa).
D Additional proofs
Lemma D.I For any X-valued Y-ary context free of depth T, and f: (X x V)* x X A()),
we have
Σ P)(y|((y)) = 1,
(16)
YEyT
where recall that x(y) denotes the context sequence (x1 (x)()....))
26

---

Proof of Lemma D.1 This is done by induction on the depth T. The key observation is that for any label sequence y, xx(y) = Xx (., only depends on the first t labels. For T 1, any context tree is represented by its root node x-)+) X1 E X and hence
Ponllii) = I(xi)(nn =1.
Suppose Eq. (16) holds for all context trees of depth T' S d and all sequential functions f. Now given any context tree x = (x1,..., Xa+1) of depth
+ 1, we denote its depth d subtree
(X1, (XI,...,Xa) Xa) by x(4- Then
E Ps(y)x(y))
ΣD ED
Pylmrati (x1, Xe+ (yi:a)
YEUE+1
Wi 10++1
f(x1,..., xa+1((1:d)) yi:d) (1dd) 1)
Di Me++
Py(mnalx Prlonal)i.....xxaaaaaa. xa(via-1) Σ
f(x1,... Xa+ (V):a), vn (Ja+1)
9011
Σ
Σ P =1,
yEVA
where the last step is due to induction. We are done.
27

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, ad- dressing issues of reproducibility, transparency. research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA]
[NA] means either that the question is Not Applicable for that particular paper the relevant information is Not Available.
Please provide short (1-2 sentence) justificatinn right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evalu- ation. While "[Yes] " generally preferable to "[No] is perfectly acceptable answer "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Abstract summarizes theorems we have proven.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Ys]]
28

---

Justification:
We discuss limitations in the Discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We don't 't see how to justify this without machine checkable proofs, which we have not provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided or not)?
Answer: [NA]
Justification: There experiments.
29

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recogmize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
There is no data code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr cc/
Suuidess/CodeSumissss
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips //nips.cc/publll wttpcccccccpccccccccceeeoo httpi///ggiide//deeuueuuuuee Sow///udeeeeeeeeeeeeeeeee www.dduuumissssonnin.. ssionPolicy: for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
30

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: There experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
31

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https http:///eeipppppe cc/ htc//pblic/Bchccccudeeeeeeeeee
Answer:
[Yes]
Justification: We have read the code and do not see any violation. Our work relates to the mathematical foundations of basic task in MI..
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper presents a mathematical characterization of the limits of probabilis- tic forecasting. and (meta)algorithm that achieves these limits. For any class of interest, there remains significant work to realize that algorithm in an efficient way. As such, our impact is most directly on the theoretical community, who might then have direct societal impact by producing an minimax optimal algorithm. As such, our societal impact may be great, but it will always be quite indirect.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, Ict alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
32

---

Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We are not releasing models or data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We use no such assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide help determine the li- cense of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer:
[NA]
Justification:
No new assets are introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
33

---

At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No such experiments were performed.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "sZXN7IsrT1", "reviewer": "Reviewer_rqqz", "summary": "This paper studies minimax regret in the online learning setup. The paper extends prior works to nonbinary labels and proves improved bounds on the regret. The analysis is through studying the Shtarkov sum that characterizes the minimax regret.  The authors develop a data-dependent variant of the contextual Shtarkov sum and introduce a variant of the Normalized Maximum Likelihood. Moreover, the paper takes an information-theoretic approach and studies sequential $\\ell_\\infty$ entropy terms to give upper bounds on regret.", "questions": "Has a contextual algorithm similar cNML been introduced before ? If so what are the benefits ? \n\nAny specific example of the multiary tree would be appreciated.", "limitations": "Nothing significant.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper is solid and presents a nice mathematical framework to prove bounds on the regret in online learning. The frameworks allows one to study a broader class of online learning problems including non binary labels. In addition it makes the proof a bit nicer with slightly improved bounds on the regret. Overall I liked the technical contributions of the paper as a framework to study various online learning problems.", "weaknesses": "On the negative, side it seems that the novelty of the work is somewhat limited, given the cited prior works. It looks like that the authors extend the Sharkov sum and its analysis to the contextual case.\n\nThe presentation of the paper could be better. It starts with elementary definitions and explanations of the problem but jumps to the technical parts without a smooth transition. \n\nMoreover, the seemed that the paper is dry and lacks giving enough motivation and explanation.  For instance, the authors introduce multiary trees without explaining the high-level picture. It is not clear why and how this concept is used in the proofs. As another example, it is not clear at the beginning why the proposed algorithm (cNML) is useful.  Perhaps a discussion on this matter helps the reader kept interested in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and, in particular, your recognition of our technical contributions. To begin, we address your concern about the novelty in our global rebuttal. We will address your remaining comments on the weaknesses of our paper and answer your questions.\n# On cNML\nIndeed, [WGHS23] gave a contextual algorithm based on the global sequential covering, which has been shown to be sub-optimal in some cases. In contrast, our cNML is provably minimax optimal, that is, it attains the optimal regret for any hypothesis class. \nMore specifically, if we compare the worst-case regret of all possible algorithms, then our Thm 4.2 shows that cNML will achieve the minimum, which is exactly the worst-case log contextual Shtarkov sum (see our Thm 3.2). \nMoreover, we expect that the cNML will lead to the development of new practical algorithms for the contextual setting, similar to the NML in the context-free case. \n\nRegarding the novelty of cNML, we are not aware of any similar algorithm in the contextual setting from the literature. It’s a novel and non-trivial contextual generalization of NML (established in [Sht87]). Just like NML is minimax optimal in the context-free setting, cNML is minimax optimal in the more general and complicated contextual setting. Above all, we consider designing the cNML algorithm as one of our major contributions.\n# On the presentation\nThank you for useful suggestions on the improvement of our presentation. We will gladly incorporate them into our final revision. \nWe agree that some intuitions behind multiary trees can be helpful. To see how multiary trees show up in the proof, we would like to note that after rewriting the minimax regret via the minimax swap (which is standard in the theoretical online learning papers but needs additional care for the log-loss here), multiary trees arise as a natural notion that can be used to further simplify this new expression of the minimax regret. For example, see section 4.1 of [BFR20] for reference. A direct visualization of a multiary tree with value in the context space $\\mathcal X$ is a complete rooted multiary tree each of whose nodes are labeled by an element of $\\mathcal X$.\n\n\n[Sht87] Shtarkov. (1987). Universal Sequential Coding of Single Messages.\\\n[BFR20] Bilodeau, Foster, and Roy. (2020). Tight bounds on minimax regret under logarithmic loss via self-concordance.", "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": "dsHxzpNouh", "reviewer": "Reviewer_upYt", "summary": "In this work, the authors consider the problem of sequential probability assignment, also known as online learning with the log-loss.  While earlier results have shown that in the context-free or transductive settings, the Shtarkov complexity is minimax optimal (and attained with normalized maximum likelihood), the contextual analogue was bounded only in terms of sequential covering numbers.  The authors propose a new complexity measure, the contextual Shtarkov sum, that is precisely equal to the minimax regret.  The authors then bound this complexity in terms of the sequential covering numbers in a way that improves marginally on prior work.", "questions": "1. Could the authors more clearly explain the novelty in technical contributions in their work?\n\n2.  When invoking the Sion's minimax theorem in the proof of Theorem 3.2, the compactness of the space should be mentioned as it is a necessary condition.  The proof is correct, however.\n\n3. I assume that the $H(P)$ in line 206 is entropy, but I have a hard time seeing where this notation is introduced in the paper.\n\n4. While section 3.2 seems like an interesting interpretation of the Shtarkov sum, it seems like a bit of a non sequitur.  How does it relate to the rest of the paper?\n\n5. Much is made of the fact that the approaches in this paper address the multi-label setting, beyond binary $\\mathcal Y$, but it is not clear why this is technically more challenging.  Indeed, do the earlier works of BFR20 not immediately generalize beyond binary $\\mathcal Y$?", "limitations": "The discussion of limitations is adequate, although mention of the computational challenges of their algorithm even in the case of convex classes (due to the necessity of optimizing over the space of trees, which is exponentially large) would be good to include.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper discusses an important problem (that of sequential probability assignment) and provides a new bound on the minimax regret.  This new bound depends on a new notion of complexity that acts as the analogue of the sequential Rademacher complexity for log loss.  The paper is presented well and explains its technical details clearly.", "weaknesses": "The paper's contributions are somewhat incremental.  The Shtarkov complexity is well-known for case of transductive learning and the introduction of contexts uses techniques introduced and used in many earlier works on sequential Rademacher complexity.  This is not helped by the fact that the Shtarkov complexity itself is almost tautalogically equal to the minimax regret.  This weakness would be somewhat mitigated if the new complexity measure led to improved bounds on the minimax regret, but the claimed improvement over BFR20 is only at the level of a constant as, asymptotically as $\\alpha \\downarrow 0$, the upper bound still scales like $\\inf_\\alpha \\{ 2 T \\alpha + \\mathcal H_\\infty(\\mathcal F, \\alpha, T) \\}$.  Furthermore, on the question of depth of technical contribution, it is not clear to me what is really novel.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and, in particular, acknowledging the importance of the problem being studied and praising our presentation. To begin, we address your concern about the novelty in our global rebuttal. We will address your remaining comments on the weaknesses of our paper and then answer your questions.\n\n# On improved bounds on the minimax regret\nTo see that our new complexity leads to improved bounds, first we would like to emphasize that the worst case log contextual Shtarkov sum **equals** the minimax regret, which means that on every instance where the bound in [BFR20] is loose, our result will be provably better. \nFor example, the linear class {$\\frac{\\langle w,x\\rangle + 1}{2}: w\\in B_2 $} and the absolute linear class {$|\\langle w,x\\rangle|: w\\in B_2 $}  (where contexts $x$ are also from $B_2$) have the same sequential covering numbers (up to constants) but admit different rates of minimax regret. Our goal is to come up with a precise characterization (that is not based on covering) to circumvent this negative result. Another benefit from our characterization is to realize the product-type martingale structure embedded in contextual Shtarkov sums, which can motivate the development of new math tools and regret bounds in the future (for more details, see the later discussion on section 3.2). \n\nSo overall we don’t aim to follow the bound in terms of sequential covering numbers too closely. Our purpose of giving a quick proof of the bound in [BFR20] (with better constants) is to showcase that starting from our new complexity, it is **easy** to get a covering-based bound as in [BFR20] but with **optimal** constants. See the argument at the bottom of page 6 in [WGHS22] for the optimality of our constants, where their bound is in terms of the global covering number that is no smaller than the local covering number in our bound. \n\nMoreover, our bound is the **first constructive** one (meaning it’s achieved by our cNML algorithm) that is optimal in terms of the local sequential entropy: \nThe upper bound on the regret in [BFR20] is non-constructive (no algorithm is provided).\nWhile [WGHS22; WGHS23] provided a concrete algorithm, their bound depends on the worse global covering number, as opposed to the local covering numbers in our bound. \n\n# On generalizing [BFR20] beyond binary labels​\nFirst, we want to clarify that the bound in [BFR20] is already loose for some classes. So despite the possible generalization, we don’t expect it to give us a tight bound in the multi-label setting. More specifically,  we can similarly upper bound the regret by an offset process using self-concordance and control this offset process using a nice enough cover. However, there is always an issue with the tightness of such covering-based upper bounds: the one in [BFR20] has been proved to be loose for some cases, and for other Dudley’s entropy-like bounds (e.g. Prop 7 in [RST10] and Thm 1.1 in [DG22]), they don’t admit matching lower bounds as well.\n\n\n# On the presentation\nThank you for pointing out the missing explanations about the entropy function and the use of Sion’s minimax theorem. In our final revision, we will introduce the notation of the entropy function in the main body and mention the compactness of relevant spaces in the proof of Theorem 3.2.\n\nRegarding our section 3.2, our purpose is to establish a connection between our new complexity and the well-studied sequential Rademacher complexity through the lens of martingales. In this way, we hope to inspire future research that develops new tools suited to the product-type martingale embedded in contextual Shtarkov sums, following a similar path of the quantitative study of sequential Rademacher complexity (see [RST15] for example). \n\n[RST10]: Rakhlin, Sridharan, and Tewari. (2020). Online learning: Random averages, combinatorial parameters, and learnability.\\\n[RST15] Rakhlin, Sridharan, and Tewari. (2015). Sequential complexities and uniform martingale laws of large numbers.\\\n[DG22]: Daskalakis and Golowich. (2022). Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games.\\\n[BFR20]: Bilodeau, Foster, and Roy. (2020). Tight bounds on minimax regret under logarithmic loss via self-concordance.\\\n[WGHS22]: Wu, Heidari, Grama, and Szpankowski. (2022). Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm.\\\n[WHGS23]: Wu, Heidari, Grama, and Szpankowski. (2023). Regret Bounds for Log-loss via Bayesian Algorithms.", "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": "gy0NIQr3p1", "reviewer": "Reviewer_ZwzX", "summary": "The authors explore the fundamental problem of sequential probability assignments, specifically focusing on log-loss online learning with an arbitrary, possibly non-parametric hypothesis class. They introduce a new complexity measure and demonstrate that the worst-case contextual Shtarkov sum equals minimal regret. With this, they derive a minimal optimal strategy, called cNML, which extends beyond binary labels.", "questions": "Perhaps the authors could conduct some experiments to compare the performance of different algorithms, so as to visually demonstrate the effectiveness of the newly proposed cNML algorithm compared to other algorithms (e.g., traditional NML, Bayesian methods, etc.) on real datasets, especially when dealing with multi-label and complex sequence prediction problems.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper successfully generalizes classical results in sequential probability assignment to contexts that involve multiary labels and sequential hypothesis classes. \nAnother strength of this paper is its robust characterization of minimax regret and optimal prediction strategies holds for arbitrary hypothesis classes. This is particularly good as it relaxes the assumptions often required in earlier works.", "weaknesses": "The paper does not include experimental results to support the theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review. Below, we address your comments on experimental results and our cNML algorithm.\n# On experimental results and our cNML\nWe would like to elaborate on the statement of our results. Theorem 3.2 says that if we compute the worst-case regret of all algorithms, then the minimal worst-case regret that any algorithm can achieve is exactly the worst-case log contextual Shtarkov sum. Then Theorem 4.2 shows that cNML is the exact algorithm that achieves this minimal worst-case regret, meaning that cNML is the minimax optimal algorithm. So if we compare the regrets of cNML and any other algorithm (say any Bayesian method) on their respective worst-case sequences, then cNML will have minimal such regret. Hence, if we really want to witness the gap between cNML and other algorithms, we have to first find out their respective worst-case data sequences (which can be different for different algorithms). In our view, it is not instructive to compare the regrets of algorithms on real datasets since such real data is not guaranteed to be the worst-case data for our algorithms of interest. \n\nWe also want to clarify that cNML is a novel and highly non-trivial generalization of the NML algorithm which is suitable for the context-free setting. So basically NML cannot run in the more general and complicated contextual setting that we studied in this paper.", "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": "Zk7ON7YoNl", "reviewer": "Reviewer_qSjy", "summary": "This paper studies the problem of sequential probability assignment under logarithmic loss with context and assumes that both the contexts and labels are generated adversarially. The main contribution is a complete characterization of the minimax regret via a new complexity measure named \"contextual Shartkov sum.\" In particular, this allows the authors to recover and improve several previously known bounds with simpler proofs. The authors further demonstrate that such minimax regret can be achieved via a contextual normalized maximum likelihood predictor.", "questions": "Although the contextual Shtarkov sum representation can be used to recover the upper bounds of [BFR20] and [WHGS23], potentially with improved constants, it would be beneficial to see some explicit examples demonstrating the benefits. For example, consider the expert class $\\mathcal{F}=\\left\\\\{\\frac{\\langle w,x\\rangle+1}{2} : w \\in B_2\\right\\\\}$, where $B_2$ is the unit $L_2$ ball. Assume the contexts are also selected from $B_2$. We know that the bounds in [BFR20] and [WHGS23] can only provide an $\\tilde{O}(T^{2/3})$ upper bound. However, it is known from [RS15] that a Follow-the-Regularized-Leader predictor achieves regret upper bounded by $\\tilde{O}(\\sqrt{T})$.\n\nCan the characterization introduced in the current paper provide an alternative (perhaps simpler) derivation of this $\\tilde{O}(\\sqrt{T})$ regret?", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Sequential probability assignment is a fundamental problem that finds many applications, such as universal compression, portfolio optimization, interactive decision making, and even the famous next-token prediction in LLMs. This is a clear significant result, which provides the first precise minimax regret of adversarial sequential probability assignment under log-loss and provides an explicit algorithm achieving such regrets. Given the importance and foundational nature of the problem, I would expect the paper to have a broad impact on the community.\n\nAlthough most of the proof ideas, such as the switching order of inf and sup, follow from prior literature, the truly novel technique that bypassed the difficulties faced by prior results is Lemma A.3. This allows the authors to characterize the minimax value directly (leveraging properties of log-loss) without resorting to the offset Rademacher complexity as in [RS15]. I also find the optimization problem in line 206 to be of independent interest. Although the paper is fairly preliminary (see point 4 in the Weakness section), it would serve as a stepping stone for important future research.\n\nOverall, this is a significant result that would inspire follow-up research. Therefore, I recommend a \"Strong Accept.\"", "weaknesses": "I do not see any significant weaknesses in the paper. However, I would like to outline a few minor remarks as follows:\n\n1. I believe the characterization in the current paper is similar in spirit to that of [BHS23], who provides a general reduction from the smoothed adversarial to the fixed design regret that also leverages the minimax switches. (Although I believe the techniques developed in the current paper could also recover this result.)\n\n2. I think Algorithm 1 can be fit into the relaxation-based algorithmic framework introduced by [RSS12]. (This does not mean the current algorithm is not novel.)\n\n3. It would be good if the authors could provide a short argument to explain why the P^* in line 507 attains the optimal of line 506. (This is clear to experts but is not immediately obvious for non-expert readers.)\n\n4. Section 3.2 could have been developed in much more detail, for example, by providing some (simple) examples to demonstrate the non-triviality. See also the Question section for more concrete examples.\n\n[BHS23] Bhatt, A., Haghtalab, N., and Shetty, A. (2023). Smoothed analysis of sequential probability assignment. NeurIPS 2023.\n\n[RSS12] Rakhlin, S., Shamir, O., & Sridharan, K. (2012). Relax and randomize: From value to algorithms. NeurIPS 2012.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and knowledgeable review. We appreciate your recognition of our main results, and hope you will help us defend the merit of our work. We first address your comments on the weaknesses of our paper and then answer your questions. \n# Clarification on our technical contribution\nWe appreciate that the reviewer appreciates the true novelty of Lemma A.3. It is the true workhorse of our analysis. However, we would also like to clarify some other parts that are novel and not just following the literature. First, the idea of minimax swap is indeed standard in online learning, but for log-loss we need a truncation argument as in the proof of Lemma 6 in [BFR20]. More specifically, we applied a smooth truncation that works for multi-labels. Second, we were able to generalize our characterization of the minimax regret for classes that may not enable minimax swaps, via a novel approximation argument that is also powered by our smooth truncation. Notably, previous results, like Thm 2 in [BFR20] and Lemma 10 in [RS15], implicitly assumed some regularity condition that validated the minimax swap.\n\nWe also want to explain a bit about the optimization problem in line 206 and 506. It is basically of the form $\\sup_{P} H(P)+ \\langle P, x \\rangle$ where $P$ ranges over all $d$-dimensional probabilistic vectors and $H$ is the entropy function. The value of this optimization problem is exactly the Fenchel conjugate of $-H$ on $x$, which is the log-sum-exp function $\\log(\\sum_i \\exp(x_i))$, and the maximum is obtained by $P^*$ with $P^*_i=\\exp(x_i)/\\sum_j \\exp(x_j)$.\n\n# On the relation to [BHS23] and the relaxation framework\nThanks for pointing us to this relevant work of [BHS23]. We will cite it clearly in our final revision. We agree that the spirits of the two papers are similar: the minimax swap in our paper helps reduce the original game to the dual game, and the coupling lemma in [BHS23] helps reduce their problem to transductive learning. A minor difference is that minimax swaps would yield equalities (under certain regularity assumption of the hypothesis class), while the reduction in [BHS23] would produce inequalities.\n\nWe also thank the reviewer for raising the question of whether cNML fits into the relaxation framework in [RSS12]. We agree that the worst-case log contextual Shtarkov sum with prefix can be viewed as a (trivially) admissible relaxation, now that we've established that it is exactly the conditional game value. What's nice about this perspective is that we can cite [RSS12] and suggest that (further) admissible relaxations of our contextual sum may yield new algorithms.\n# On section 3.2 and the linear class\nIn section 3.2, we connect our new complexity measure and the well-studied sequential Rademacher complexity, through the lens of martingales. The quantitative study of sequential Rademacher complexity greatly benefits from its martingale structure, see for example [RST15]. So we hope to inspire future work on developing new tools suitable for the product-type martingale embedded in contextual Shtarkov sum. Indeed, the linear class is a great example exhibiting the inadequacy of sequential covering numbers as the right complexity measure, so it automatically justifies our new complexity, although currently, we lack the right math tools to give a tight bound for it directly from contextual Shtarkov sum. We believe it is an important future direction to study our contextual Shtarkov sums in a systematic and quantitative way, as has been done for sequential Rademacher complexity.\n\n[RSS12] Rakhlin, Shamir, and Sridharan. (2012). Relax and randomize: From value to algorithms.\\\n[RS15]: Rakhlin and Sridharan. (2015). Sequential probability assignment with binary alphabets and large classes of experts.\\\n[RST15] Rakhlin, Sridharan, and Tewari. (2015). Sequential complexities and uniform martingale laws of large numbers.\\\n[BFR20] Bilodeau, Foster, and Roy. (2020). Tight bounds on minimax regret under logarithmic loss via self-concordance.\\\n[BHS23]: Bhatt, Haghtalab, and Shetty. (2023). Smoothed analysis of sequential probability assignment.", "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:
Multiple reviewers question the novelty of this work, but also express some uncertainty by not expressing complete confidence. Here we give a full throated defense of our work's significance and novelty. We hope this settles the matter.
# On the significance of the problem
First, we want to highlight the significance of the fundamental problem studied in this paper. The problem of sequential probability assignment (with contexts/side information) was raised no later than 2006 in the online learning "bible" [CL06] (see sec 9.9). Since then, this problem has been studied under the framework of online supervised learning, formalized e.g. by [RST10], with the objective of characterizing the minimax regret w.r.t general hypothesis classes. Prior works (including [RS15; BFR20; WGHS23]) focused on upper bounding the regret by sequential covering number, which turns out NOT to be the right complexity measure: there exist two natural hypothesis classes such that their sequential covering numbers are of the same order, but there is a polynomial gap between their rates of minimax regret (see sec 3.2.2 in [BHS23]). Previous attempts by colleagues to perform a general minmax swap had not succeeded and so the problem of identifying a general complexity measure that characterized minimax regret has stubbornly remained open for nearly 20 years, nevermind a minimax algorithm for general hypothesis classes, which was also missing. This was a key open problem in machine learning theory.
# On our technical contribution
Now we highlight that our technical contribution is non-trivial and novel in the following senses: \
**Novelty of the notion of contextual Shtarkov sums:** Our definition of contextual Shtarkov sum is very much different from those in the non-contextual and transductive settings and serves as a novel generalization. It's important to not lose track of the fact that, after we show that it characterizes the minimax regret, it will of course seem to be the natural and right complexity measure in our contextual and fully adaptive setting. To be more specific, the Shtarkov sum in the non-contextual setting was introduced in 1987 by [Sht87]. It is immediate to derive a Shtarkov sum for the transductive setting and to show that it characterizes the minimax (fixed-design) regret there, since knowing the context sequence to be revealed reduces the problem to the non-contextual setting! This is not the case in the adaptive setting! In contrast, prior to our work, the right generalization of the Shtarkov sum to our setting was entirely absent (for 20 years!). For example, in chapter 9 of [CL06], the traditional Shtarkov sum is extensively exhibited (see Thm 9.1) and the problem of sequential probability assignment with contexts is clearly introduced (see sec 9.9). The long list of researchers who have worked on this problem have all been aware of Shtarkov sums, and several have since reported to us trying this approach, but failing. \
**Novelty of our proof techniques:**
- The techniques we applied to derive that the minimax regret is characterized by contextual Shtarkov sums are very (!) different from those for sequential Rademacher complexity, which have dominated studies of online supervised learning. As reviewer qSjy points out, we are able to characterize the minimax regret by leveraging properties of log-loss, thanks to our novel Lemma A.3. More specifically, we make an important observation that probabilistic trees are equivalent to joint distributions, which further enables us to derive that the expected cumulative loss of learner (after the minimax swap) is actually the entropy of this joint distribution. Therefore, we reduce the minimax regret into an entropic-regularized optimization problem whose value can be computed explicitly. In light of this, we are able to characterize the minimax regret by (the worst-case log of) contextual Shtarkov sums.
- Another non-trivial part of our analysis is the minimax swap. This is due to the fact that log loss is non-Lipschitz and unbounded, unlike absolute and square losses. So we applied a truncation method that works for multi-labels to apply minimax swaps. Moreover, previous works implicitly assumed that minimax swaps always hold and they required a regularity assumption for the hypothesis class ([RS15] for their lower bound and [BFR20] for their upper bound), so their regret bounds are all conditional on this assumption. However, we apply a novel approximation argument to show that contextual Shtarkov sums continue to characterize the minimax regret w.r.t all hypothesis classes that don’t necessarily validate minimax swaps. In this way, we are able to get rid of any regularity assumption.

**Novelty of cNML algorithm:** Our second major contribution is the design of the cNML algorithm, which we show is minimax optimal for sequential probability assignment with contexts. Thus, cNML can be thought of as the contextual generalization of NML (which dates back to [Sht87]) from the context-free setting. Also, cNML is the first minimax algorithm for this problem. Previous ones like the Bayesian algorithm in [WGHS23] only admit suboptimal regret guarantees. Moreover, we believe cNML is the starting point of more practical algorithms in future works, just like NML.

[Sht87] Shtarkov. (1987) Universal Sequential Coding of Single Messages\
[CL06] Cesa-Bianchi & Lugosi. (2006) Prediction, learning, and games\
[RST10] Rakhlin, Sridharan, & Tewari. (2020) Online learning: Random averages, combinatorial parameters, and learnability\
[RS15] Rakhlin & Sridharan. (2015) Sequential probability assignment with binary alphabets and large classes of experts\
[BFR20] Bilodeau, Foster, & Roy. (2020) Tight bounds on minimax regret under logarithmic loss via self-concordance\
[BHS23] Bhatt, Haghtalab, & Shetty. (2023) Smoothed analysis of sequential probability assignment\
[WHGS23] Wu, Heidari, Grama, & Szpankowski. (2023) Regret Bounds for Log-loss via Bayesian Algorithms

Meta-review: The paper studies the minimax regret in the online adversarial setting (with contexts) when one uses log loss and arbitrary class of functions/predictors. They introduce a complexity measure they refer to as contextual Shtarkov sum that provides a minimax regret bound for the problem in the multi alphabet outcome case. The paper improves upon previous results in [RS15],  [BFR20] and [WHGS23] and provides the right rate for the problem. The work is definitely worth publishing at Neurips. Majority of the reviewers agree with this view.
Decision: Accept (poster)