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_cc_2024_Conference
Published: 2024-05-14 20:22:46

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).

Main paper: 
 introduction: 
 Sequential probability assignment is a fundamental problem with connections to information theory [Ris84; MF98; XB00], machine learning [CL06; Vov95; RST15; FKLMS18; 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 is now known as the Shtarkov sum, and subsequently described 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-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. [RS15; BFR20; WHGS23]) under the framework of online supervised learning formalized by Rakhlin, Sridharan, and Tewari [RST10] . In this setup, the problem is modeled as a T -round game between a learner and the nature: On each round t = 1, . . . , T , the learner observes a context x t from nature and predicts a distribution pt over some finite label space Y. Then nature reveals a label y t ∈ Y and the learner incurs a logarithmic loss ℓ(p t , y t ) = -log(p t (y t )), where pt (y t ) is the probability assigned to label y t by pt . The performance of the learner is measured by the regret with respect to a class F 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 adaptive 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: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 a tight analysis in online learning problems with convex Lipschitz losses, like absolute loss [RST15] 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 a 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 a 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 on 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 state-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 datagenerating 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 as redundancy with respect to a set of codes. This has been studied in both stochastic and adversarial settings [Fre96 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 to 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  
preliminaries: 
 Notation. For a positive integer K, let [K] := {1, 2, . . . , K}. For a finite set K with |K| = K, we use ∆(K) to denote the set of all distributions on K. We may identify K with [K] (under arbitrary enumeration of elements in K) and treat elements of ∆(K) as vectors in R K . For a vector p ∈ R K and i ∈[K], let p(i) be the i-th coordinate of p. Let ∆ + (K) = {p ∈ ∆(K) : p(k) > 0, ∀k ∈ K}.For a general finite sequence (a i ) N i=1 , we will use a n:m to denote the sub-sequence (a n , . . . , a m ) for any n ≤ m and the empty sequence for n > m. For any set A, let A * = ∪ k≥0 A k 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 t ∈ [T ] during the game of sequential probability assignment, the learner receives a context x t ∈ X from nature and assigns a probability distribution pt ∈ ∆(Y) to the possible labels. Then nature reveals the true label y t ∈ Y and the learner incurs a loss ℓ(p t , y t ) = -log(p t (y t )). Throughout, the learner is required to predict nearly as well as the best expert from an expert class, which is modeled as an arbitrary hypothesis class F ⊆ {(X × Y) * × X → ∆(Y)}. More formally, the goal of the learner is make their regret with respect to F, R T (F; p1:T , x 1:T , y1:T ) = T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f (x 1:t , y 1:t-1 ), y t ),as small as possible for all sequences x and y generated by nature, possibly in an adversarial manner. Here f (x 1:t , y 1:t-1 ) ∈ ∆(Y) can be understood as the prediction made by expert f at round t using past observations (x 1:t-1 , y 1:t-1 ) as well as the fresh context x t . The main focus is to study the minimax regret R T (F), which can be written as the following extensive formR T (F) = sup x1 inf p1 sup y1 • • • sup x T inf pT sup y T R T (F; p1:T , x 1:T , y 1:T ), where x t ∈ X , pt ∈ ∆(Y) and y t ∈ Y, ∀t ∈ [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 f as mappings from (X ×Y) * ×X to ∆(Y) are sometimes called fully sequential experts [WHGS23] due to their ability to predict based on the past history. However, the literature (e.g. [RS15; BFR20; WHGS23]) often considers the more limited notion of non-sequential experts, modeled as F ⊆ {X → ∆(Y)}, reflecting the fact that prediction made by each expert f is simply f (x t ) in each round t. In contrast, our results are more general as our novel techniques can be applied to the more flexible sequential experts.Multiary trees. The complexity of online learning problems stems from the sequential and adaptive nature of the adversary, which we can 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 a sequence of mappingsv t : K t-1 → A for t ∈ [d]. A path in a depth-d tree is a sequence ε = (ε 1 , . . . , ε d ) ∈ K d .We use the notation v t (ε) to denote v t (ε 1 , . . . , ε t-1 ) for t ∈ [d] and the boldface notation v(ε) to denote (v 1 (ε), . . . , v d (ε)) ∈ A d . Throughout we will only consider Y-ary trees valued in either X or ∆(Y), where the paths are denoted by the boldface y. We refer to X -valued trees as context trees and ∆(Y)-valued trees as probabilistic trees.Time-varying context sets. So far we consider the context set X to be constant over time. But all of our results can be extended easily to allow for time-varying context spaces. Details of this generalization can be found in Appendix C.Before introducing our complexity measure that characterizes R T (F), we review some prior settings where the minimax regret can be characterized by the well-studied Shtarkov sum. First we introduce the notion of likelihood of a hypothesis f with respect to a context and label sequence, which plays a key role in defining complexity measures and optimal algorithms.Definition 2.2 (Likelihood) For f : (X × Y) * × X → ∆(Y) and length-d sequences x 1:d ∈ X d , y 1:d ∈ Y d , the likelihood P f (y 1:d |x 1:d ) is defined as P f (y 1:d |x 1:d ) = d t=1 f (x 1:t , y 1:t-1 )(y t ),where we use the compact notation f (x 1:t , y 1:t-1 ) for f (x 1 , y 1 , . . . , x t-1 , y t-1 , x t ).In the classical context-free setting where X can be thought of as a singleton, any sequential expert f degenerates to a joint distribution over label sequences. Indeed, given any label sequence y 1:t-1 , f (y 1:t-1 ) ∈ ∆(Y) can be interpreted as the conditional distribution f assigns to the next label y t . We use P f (y 1:d ) = d t=1 f (y 1:t-1 )(y t ) to denote this distribution. Similarly, the learner's strategy is also specified by a joint distribution that is decomposed to a sequence of conditional distributions pt = pt (•|y 1:t-1 ) ∈ ∆(Y). In this setup the minimax regret R T (F) is characterized by the Shtarkov sum [Sht87] .Proposition 2.3 ([Sht87]) In the context-free setting, for any hypothesis class F and horizon T , the Shtarkov sum S T (F) is defined asS T (F) = y 1:T ∈Y T sup f ∈F P f (y 1:T ).Moreover, the minimax regret is given by R T (F) = log S T (F), and the unique minimax optimal strategy is the normalized maximum likelihood (NML) distribution given byp nml (y 1:T ) = sup f ∈F P f (y 1:T ) y ′ 1:T ∈Y T sup f ∈F P f (y ′ 1:T ) , ∀y 1:T ∈ Y T .To go beyond this classical context-agnostic setting and incorporate contextual information, prior work (e.g. [JSS21] ) also considered an easier problem than the aforementioned sequential probability assignment, by forcing nature to reveal the context sequence x 1:T to the learner at the start of the game. This is known as the fixed design setting or transductive online learning [WHGS23] , where the goal is to characterize the so-called fixed design maximal minimax regretR FD T (F) := sup x 1:T ∈X T inf p1 sup y1 • • • inf pT sup y T R T (F; p1:T , x 1:T , y 1:T ).It is straightforward to see that after projecting on x 1:T , the hypothesis class F again collapses to a set of joint distributions over Y T 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 be more specific, for any f ∈ F, it induces an expert in the context-free setting after being projected on x 1:T , which is denoted by f | x 1:T andf | x 1:T (y 1:t-1 ) := f (x 1:t , y 1:t-1 ) ∈ ∆(Y), ∀t ∈ [T ], y 1:t-1 ∈ Y t-1 ,and let F| x 1:T := {f | x 1:T : f ∈ F}. Then given any predetermined x 1:T , the learner is equivalently competing with F| x 1:T in the context-free setting. With the following natural variant of the Shtarkov sum, we can easily characterize R FD T (F). Definition 2.4 (Conditional Shtarkov sum) Given a context sequence x 1:T ∈ X T , the Shtarkov sum of F conditioned on x 1:T isS T (F|x 1:T ) := y 1:T ∈Y T sup f ∈F P f (y 1:T |x 1:T ).In fact, S T (F|x 1:T ) is just the Shtarkov sum of the projected class F| x 1:T 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 hypothesis class F and horizon T , the fixed design maximal minimax regret isR FD T (F) = sup x 1:T ∈X T log S T (F|x 1:T ),and, given any context sequence x 1:T , the minimax optimal response is NML with respect to F| x 1:T . 
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 of contextual Shtarkov sum, which is a natural generalization of Shtarkov sum in the context-free setting.Definition 3.1 (Contextual Shtarkov sum) The contextual Shtarkov sum S T (F|x) of a hypothesis class F on a given context tree x of depth T is defined asS T (F|x) := y∈Y T sup f ∈F P f (y|x(y)).Just like the conditional Shtarkov sum, the contextual Shtarkov sum S T (F|x) can be interpreted as the Shtarkov sum of the projected class F| x := {f | x : f ∈ F} where f | x is the induced context-free expert specified byf | x (y 1:t-1 ) := f (x(y 1:t-1 ), y 1:t-1 ) ∈ ∆(Y), ∀t ∈ [T ], y 1:t-1 ∈ Y t-1 ,where we have slightly abused the notation to use x(y 1:t-1 ) to denote the length-t context sequence obtained by tracing tree x through the (partial) path y 1:t-1 . Next we show that the minimax regret R T (F) is characterized by the worst-case contextual Shtarkov sum:Theorem 3.2 (Main result: minimax regret) For any hypothesis class F ⊆ {(X × Y) * × X → ∆(Y)} and horizon T , R T (F) = sup x log S T (F|x),where the supremum is taken over all X -valued context trees x of depth T .Since any context sequence x 1:T can be thought as a special context tree x that is constant in each level t ∈ [T ] (i.e., x t (y) = x t , ∀y), 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 we can see the separation between R T (F) and R FD T (F) is clearly exhibited. The full proof of Theorem 3.2 as well as an overview are provided in Appendix A.To illustrate the utility of our characterization in Theorem 3.2, we 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 a start, we provide a short proof in Appendix A.6 of the classical regret bound for a finite hypothesis class. Proposition 3.3 (Finite classes) For any F ⊆ [0, 1] X and horizon T , R T (F) ≤ log |F|.Let us go back to the binary label setting with non-sequential experts, that is, Y = {0, 1} and F ⊆ [0, 1] X , and f (x) ∈ [0, 1] is interpreted as the probability assigned to label 1 by this expert f . We will show a regret bound that outperforms the state-of-the-art ones in [BFR20; WHGS23] with a surprisingly simple proof. To proceed, we need the following notation. Given a context tree x of depth T , letF • x = {f • x : f ∈ F}, where f • x is the [0, 1]-valued tree such that (f • x) t (y) = f (x t (y)), ∀y ∈ Y T .Next we introduce the definitions of sequential ℓ ∞ covers and entropy. Definition 3.4 (Sequential ℓ ∞ cover and entropy) Given a hypothesis class F ⊆ [0, 1] X and a context tree x of depth T , we say a collection of R-valued trees V x,α is a sequential cover of F • x at scale α > 0 if for any f ∈ F, y ∈ Y T , there exists some v ∈ V x,α such that|f (x t (y)) -v t (y)| ≤ α, ∀t ∈ [T ].Let the sequential ℓ ∞ covering number N ∞ (F • x, α, T ) be the size of the smallest such cover. The sequential ℓ ∞ entropy of F at scale α and depth T is defined as the logarithm of the worst-case sequential covering number:H ∞ (F, α, T ) := sup x log N ∞ (F • x, α, T ).Definition 3.5 (Global sequential ℓ ∞ cover and entropy) Given a hypothesis class F ⊆ [0, 1] X , we say a collection of mappings G α ⊆ [0, 1] X * is a global sequential cover of F at scale α > 0 and depth T if for any f ∈ F, x 1:T ∈ X T , there exists some g ∈ G α such that|f (x t ) -g(x 1:t )| ≤ α, ∀t ∈ [T ].Let the global sequential ℓ ∞ covering number N G (F, α, T ) be the size of the smallest such cover. The global sequential ℓ ∞ entropy of F at scale α and depth T is defined asH G (F, α, T ) := log N G (F, α, T ). Proposition 3.6 ([BFR20; WHGS23]) For any F ⊆ [0, 1] X and horizon T , R T (F) ≤ min inf α>0 4T α + cH ∞ (F, α, T ) [BFR20] , inf α>0 T log(1 + 2α) + H G (F, α, T ) [WHGS23],where c = 2-log(2) log(3)-log(2) ∈ (3, 4).It is easy to show that H ∞ (F, α, T ) ≤ H G (F, α, T ), but, in general, the two bounds in Proposition 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 to derive a bound that combines the best of these two bounds:Theorem 3.7 (Main result: sequential entropy bound) For any F ⊆ [0, 1] X and horizon T ,R T (F) ≤ inf α>0 T log(1 + 2α) + H ∞ (F, α, T ) .Proof For any scale α > 0 and depth-T context tree x, let V x,α be a sequential cover of F • x at scale α with size N ∞ (F • x, α, T ). We can always assume V x,α to be [0, 1]-valued without loss of generality because otherwise we can just truncate it without violating its coverage guarantee. Define the smoothed covering set Ṽx,α = ṽ : ∀t ∈[T ], ṽt (•) = vt(•)+α 1+2α , v ∈ V x,α , inspired by [BFR23; WHGS23]. Then for any f ∈ F, y ∈ Y T , there exists some v ∈ V x,α such that |f (x t (y))-v t (y)| ≤ α, ∀t ∈ [T ] and hence ṽ satisfies f (x t (y)) ṽt (y) ≤ 1 + 2α, 1 -f (x t (y)) 1 -ṽt (y) ≤ 1 + 2α. Hence P f (y|x(y)) = T t=1 f (x t (y)) yt (1 -f (x t (y))) 1-yt ≤ (1 + 2α) T T t=1 ṽt (y) yt (1 -ṽt (y)) 1-yt ,andy sup f ∈F P f (y|x(y)) ≤ (1 + 2α) T y sup ṽ∈ Ṽx,α T t=1 ṽt (y) yt (1 -ṽt (y)) 1-yt ≤ (1 + 2α) T ṽ∈ Ṽx,α y T t=1 ṽt (y) yt (1 -ṽt (y)) 1-yt = (1 + 2α) T | Ṽx,α |,where the last equality follows from Lemma D.1, treating ṽ as sequential experts. Finally,R T (F) = sup x log y sup f ∈F P f (y|x(y)) ≤ sup x log (1 + 2α) T | Ṽx,α | = T log(1 + 2α) + H ∞ (F, α, T ).Since our choice of α is arbitrary, the result follows. ■We conclude this section with a discussion on the suboptimality of 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 = B 2 :EQUATIONWe can see that the sequential ℓ ∞ covering numbers of F Lin and F AbsLin are of the same order for all scales, thus the aforementioned results will yield the same regret bound for these two classes. However, we haveR T (F Lin ) = Õ( √ T ) while R T (F AbsLin ) = Θ(T 2/3 ) [RS15; WHGS23], which implies that the sequential ℓ ∞ covering number, in its current form within the regret bound, cannot characterize the minimax regret.It is worth mentioning that an Ω( √ T ) lower bound on R T (F Lin ) is achievable, via an Ω(1/α 2 ) lower boundR T (F Lin ) ≥ R FD T (F Lin ) ≥ √ T /4.The proof of Lemma 3.8 is based on lower bounding the conditional Shtarkov sums (and hence the contextual Shtarkov sums) of F Lin . From Theorem 3.2 we know that the Õ( √ T ) upper bound holds for the log of contextual Shtarkov sums as well but we do not have a direct proof of this fact so far.EQUATIONand otherwise set pt to be an arbitrary member of ∆ + (Y) 3. Receive label y t ∈ Y End for 4 Contextual NML, the minimax optimal algorithm So far we have settled the minimax regret of sequential probability assignment in a nonconstructive way. Now we switch to the algorithmic lens to study the optimal strategy that achieves the minimax regret. Remarkably, we show that the minimax optimal algorithm can be described by a 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 x 1:t ∈ X t , y 1:t ∈ Y t , t ∈ [T ] and a context tree x of depth T -t, the contextual Shtarkov sum S x1:t,y1:t T (F|x) of F on x with prefix x 1:t , y 1:t is defined asS x1:t,y1:t T (F|x) = y∈Y T -t sup f ∈F P f (y 1:t , y|x 1:t , x(y)).Now we present our prediction strategy, contextual normalized maximum likelihood (cNML), which is summarized in Algorithm 1. In each round t, with x 1:t , y 1:t-1 as past observations, the learner first checks whether sup f ∈F P f (y 1:t-1 |x 1:t-1 ) > 0 since if that is not the case and sup f ∈F P f (y 1:t-1 |x 1:t-1 ) = 0, the cumulative losses of all experts in F have already blown up to +∞ and the learner only needs to predict any p ∈ ∆ + (Y) in all remaining rounds. On the other hand, if sup f ∈F P f (y 1:t-1 |x 1:t-1 ) > 0, then max y∈Y sup x S x1:t,(y1:t-1,y) T (F|x) > 0 and the pt given by Eq. ( 2) is indeed a valid member of ∆(Y) (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 B. Theorem 4.2 (Main result: optimal algorithm) The contextual normalized maximum likelihood strategy (Algorithm 1) is minimax optimal.To see that cNML is reduced to NML in the context-free setting, it suffices to consider the case where sup f ∈F P f (y 1:T ) > 0 since otherwise NML will simply assign 0 probability on this sequence y 1:T and during the actual round-wise implementation of NML, it also predicts an arbitrary element from ∆ + (Y) in those rounds t where sup f P f (y 1:t-1 ) = 0. Now for any y 1:T such that sup f ∈F P f (y 1:T ) > 0, the prediction by cNML in each round t ispt (y) = y∈Y T -t sup f ∈F P f (y 1:t-1 , y, y) y ′ ∈Y T -t+1 sup f ∈F P f (y 1:t-1 , y ′ ), ∀y ∈ Y which can be summarized into a joint density over y 1:T byp(y 1:T ) = sup f ∈F P f (y 1:T ) y ′ 1:T ∈Y T sup f ∈F P f (y ′ 1:T ).Recall that this is exactly the NML prediction p nml (y 1:T ).Remark 4.3 (Relaxations and efficient algorithms) One may wonder if more efficient algorithms are available when it is not easy 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 at 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, we provide further insight into contextual Shtarkov sums, defined in Sections 3 and 4.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 byR T (F; x) := E ε sup f ∈F T t=1 ε t f (x t (ε)) ,where x is a depth-T binary context tree and ε = (ε 1 , . . . , ε T ) ∈ {±1} T is a sequence of i.i.d. Rademacher random variables. A notable feature of R T (F; x) is that it is the expected supremum of the sum of a martingale differences, i.e., for any f,E[ε t f (x t (ε))|ε 1 , . . . , ε t-1 ] = 0. Likewise, S T (F|x) also admits a martingale interpretation. To see this, let F ⊆ {(X × Y) * × X → ∆(Y)}and rewrite S T (F|x) for any context tree x:S T (F|x) = y∈Y T sup f ∈F P f (y|x(y)) = E y sup f ∈F T t=1 |Y| • f (x 1:t (y), y 1:t-1 )(y t ) ,where y = (y 1 , . . . , y T ) is a sequence of i.i.d. variables following the uniform distribution over Y.It is easy to check that E[|Y| • f (x 1:t (y), y 1:t-1 )(y t )|y 1 , . . . , y t-1 ] = 1, and thust s=1 |Y| • f (x 1:s (y), y 1:s-1 )(y s ) t∈[T ]is a martingale with respect to filtration F t = σ(y 1 , . . . , y t ), t ∈ [T ]. It would be of independent interest to study the contextual Shtarkov sums more quantitatively by developing new tools for such product-type martingales.We can also interpret contextual Shtarkov sums as an instance of general Shtarkov sums, which are defined over sub-probability measures.Definition 5.1 (Sub-probability measure)A set P = {p : K → [0, 1]} is a class of sub-probability measures over a finite set K if k∈K p(k) ≤ 1, ∀p ∈ P.Due to Lemma D.1, it is easy to see that for any hypothesis class F ⊆ {(X × Y) * × X → ∆(Y)} and depth-T context tree x, they induce a classP F |x := {P f (•|x(•)) : f ∈ F}that is a class of sub-probability measures over Y T . Moreover, for any F, depth-(T -t) context tree x and sequences x 1:t ∈ X t , y 1:t ∈ Y t , the inducedP F x 1:t ,y 1:t |x := {P f (y 1:t , •|x 1:t , x(•)) : f ∈ F} is a class of sub-probability measure over Y T -t since y∈Y T -t P f (y 1:t , y|x 1:t , x(y)) = P f (y 1:t |x 1:t ) ≤ 1.Next we introduce the notion of general Shtarkov sum over classes of sub-probability measures.Definition 5.2 (General Shtarkov sum) Given any class P of sub-probability measures over K, the general Shtarkov sum of P is defined asS(P) = k∈K sup p∈P p(k).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 of general Shtarkov sums:Proposition 5.3 For any horizon T, t ∈ [T ], data sequence x 1:t ∈ X t , y 1:t ∈ Y t , and context trees x, x ′ of depth T, T -t respectively, we haveS T (F|x) = S(P F |x ), S x1:t,y1:t T (F|x ′ ) = S(P F x 1:t ,y 1:t |x ′ ).It would be interesting to find out other instances of general Shtarkov sums that capture the complexities of other online learning problems with log loss.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Justification: There is no data or code.Guidelines:• The answer NA means that paper does not include experiments requiring code. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussions: 
 In this paper, we characterize the minimax regret and the optimal prediction strategy for sequential probability assignment, generalizing the classical results in the context-free setting. Moreover, our 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; BFR20]).For future works, it would be interesting to study the minimax regret of specific classes more quantitatively 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, a more systematic study is needed. On the practical side, it is important to develop algorithms that are more computationally efficient than cNML and with provable guarantees.A Proofs for Section 3Notations. When the context and label sequences x 1:T , y 1:T are clear from the context, we may use f t to denote the probability vector f (x 1:t , y 1:t-1 ) ∈ ∆(Y) produced by hypothesis f at time t for notational convenience. We also adopt the notation for repeated operators in [RST15; BFR20],denotingOpt 1 • • • Opt T [• • • ] by ⟪Opt t ⟫ T t=1 • • • .For any discrete distribution P and discrete random variables X, Y , let H(P ) be the entropy of P and H(X|Y ) 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 a 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 R T (F) to move to 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 R T (F), and after rearranging we get that the value of the swapped game = supx,pE y∼p [R T (F; p(y), x(y), y)] ≤ R T (F),where the supremum is taken over all context trees x and probabilistic trees p, of depth T . Also E y∼p means the nested conditional expectationsE y1∼p1(y) E y2∼p2(y) • • • E y T ∼p T (y) .Similar to the proof of Lemma 6 in [BFR20] for the binary label setting, we apply the minimax theorem with a tweak that we devise to handle multiary labels to derive thatEQUATIONunder some mild regularity condition for F. A key observation is that the supremum over depth-T probabilistic trees p is equivalent to the supremum over joint distributions P over Y T . Based on this observation and some algebra, for a fixed context tree x, the supremum over p in Eq. ( 3) is supP ∈∆(Y T ) H(P ) + E y∼P sup f ∈F log P f (y|x(y)) .The value of this maximization problem can be easily computed to be logy sup f ∈F P f (y|x(y)) = log S T (F|x). Thus, R T (F) = sup x,p E y∼p [R T (F; p(y), x(y), y)] = sup x sup P ∈∆(Y T ) H(P ) + E y∼P sup f ∈F log P f (y|x(y)) = sup x log S T (F|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 a particular hypothesis is included in F such that the enlarged class allows for the minimax swap [RS15; BFR20]. Nevertheless, even adding a mere hypothesis may lead to suboptimal analysis for some classes F, say when R T (F) is of constant order. To completely get rid of any regularity assumption and obtain a unified characterization of the minimax regret for arbitrary class F, we provide a novel argument as follows. For an arbitrary class F, we study a smooth truncated version of it, denoted by F δ for any level δ ∈ (0, 1/2), such that F δ always validates the use of the minimax theorem and hence R T (F δ ) = sup x log S T (F δ |x).Then we give a series of refined analysis comparing the minimax regrets and contextual Shtarkov sums of F and F δ that yieldsR T (F) ≤ R T (F δ ) + T log(1 + |Y|δ) = sup x log S T (F δ |x) + T log(1 + |Y|δ) ≤ log sup x S T (F|x) + δ • C(T, |Y|) + T log(1 + |Y|δ),where C(T, |Y|) < ∞ is a positive constant that only depends on T and |Y|. Sending δ → 0 + will conclude that R T (F) ≤ sup x log S T (F|x), which finishes the whole proof as we already have R T (F) ≥ sup x log S T (F|x) from the start.As standard in online learning literature, we will first move to a dual game after applying a 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 x 1:T ∈ X T , yEQUATIONwe have thatEQUATIONwhere the supremum is taken over all X -valued Y-ary trees x and ∆(Y)-valued Y-ary trees p, of depth T . Also E y∼p means the nested conditional expectationsE y1∼p1(y) E y2∼p2(y) • • • E y T ∼p T (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. Proof of Lemma A.1 Fix δ ∈ (0, 1/2). By restricting the learner's prediction pt to ∆ δ (Y), we get an upper bound on R T (F):R T (F) ≤ ⟪sup xt inf pt∈∆ δ (Y) sup yt ⟫ T t=1 T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) = ⟪sup xt inf pt∈∆ δ (Y) sup yt ⟫ T -1 t=1 sup x T inf pT ∈∆ δ (Y) sup p T E y T ∼p T T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) .Now we can apply Sion's minimax theorem [Sio58] to the functionA(p T , p T ) = E y T ∼p T T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) to derive that inf pT ∈∆ δ (Y) sup p T ∈∆(Y) A(p T , p T ) = sup p T ∈∆(Y) inf pT ∈∆ δ (Y)A(p T , p T ).1. A(p T , p T ) is convex and continuous in pT over the compact ∆ δ (Y) and 2. A(p T , p T ) is concave and continuous in p T over the compact ∆(Y), which is further due to that A(p T , p T ) is linear in p T and is bounded given Eq. (4).HenceR T (F) ≤ ⟪sup xt inf pt∈∆ δ (Y) sup yt ⟫ T -1 t=1 sup x T sup p T inf pT ∈∆ δ (Y) E y T ∼p T T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) = ⟪sup xt inf pt∈∆ δ (Y) sup yt ⟫ T -2 t=1 sup x T -1 inf pT -1 ∈∆ δ (Y) sup p T -1 E y T -1 ∼p T -1 T -1 t=1 ℓ(p t , y t ) + sup x T sup p T inf pT ∈∆ δ (Y) E y T ∼p T ℓ(p T , y T ) -E y T ∼p T inf f ∈F T t=1 ℓ(f t , y t ) .Again the order of inf pT -1 ∈∆ δ (Y) and sup p T -1 ∈∆(Y) with respect toB(p T -1 , p T -1 ) = E y T -1 ∼p T -1 T -1 t=1 ℓ(p t , y t ) + sup x T sup p T inf pT ∈∆ δ (Y) E y T ∼p T ℓ(p T , y T ) -E y T ∼p T inf f ∈F T t=1 ℓ(f t , y t )can be swapped due to the same reason as above, leading toR T (F) ≤ ⟪sup xt inf pt∈∆ δ (Y) sup yt ⟫ T -2 t=1 sup x T -1 sup p T -1 inf pT -1 ∈∆ δ (Y) E y T -1 ∼p T -1 T -1 t=1 ℓ(p t , y t ) + sup x T sup p T inf pT ∈∆ δ (Y) E y T ∼p T ℓ(p T , y T ) -E y T ∼p T inf f ∈F T t=1 ℓ(f t , y t ) = ⟪sup xt inf pt∈∆ δ (Y) sup yt ⟫ T -3 t=1 sup x T -2 inf pT -2 ∈∆ δ (Y) sup p T -2 E y T -2 ∼p T -2 T -2 t=1 ℓ(p t , y t ) + sup x T -1 sup p T -1 inf pT -1 ∈∆ δ (Y) E y T -1 ∼p T -1 ℓ(p T -1 , y T -1 ) + E y T -1 ∼p T -1 sup x T sup p T inf pT ∈∆ δ (Y) E y T ∼p T ℓ(p T , y T ) -E y T ∼p T inf f ∈F T t=1 ℓ(f t , y t ) .Repeating this procedure through all T rounds yieldsR T (F) ≤ ⟪sup xt sup pt E yt∼pt ⟫ T t=1 sup f ∈F T t=1 inf pt∈∆ δ (Y) E yt∼pt [ℓ(p t , y t )] -ℓ(f t , y t ) .By Lemma A.7, we know that we do not lose too much by restricting learner's prediction to ∆ δ (Y):R T (F) ≤ ⟪sup xt sup pt E yt∼pt ⟫ T t=1 sup f ∈F T t=1 inf pt E yt∼pt [ℓ(p t , y t )] -ℓ(f t , y t ) + |Y|δT.Sending δ → 0 + on the RHS of the above inequality, we getR T (F) ≤ ⟪sup xt sup pt E yt∼pt ⟫ T t=1 sup f ∈F T t=1 inf pt E yt∼pt [ℓ(p t , y t )] -ℓ(f t , y t ) .It is easy to see that on the RHS of the above inequality, the inner infimum over pt ∈ ∆(Y) is achieved at pt = p t due to the nature of log loss. SoR T (F) ≤ ⟪sup xt sup pt E yt∼pt ⟫ T t=1 sup f ∈F T t=1 E yt∼pt [ℓ(p t , y t )] -ℓ(f t , y t ) = sup x,p E y∼p [R T (F; p(y), x(y), y)],where in the last equality we use the compact notation of trees to further simplify our expression and this concludes the proof. ■ Lemma A.3 For any hypothesis class F and horizon T , supx,p E y∼p [R T (F; p(y), x(y), y)] = supEQUATIONIt is implied that whenever F satisfies Eq. (5), we have R T (F) = supx log S T (F|x).Proof of Lemma A.3 First we can see that the outcome sequence y 1:T generated under any tree p is the same thing as y 1:T generated by its associated joint distribution over Y T , and vice versa. So we can replace the supremum over trees p in the LHS of Eq. ( 6) by the supremum over joint distributions P over Y T . Hence, supx,pE y∼p [R T (F; p(y), x(y), y)] = sup inf f ∈F T t=1 ℓ(f t , y t ) = inf f ∈F (-log P f (y 1:T |x 1:T )) = -sup f ∈F log P f (y 1:T |x 1:T ).So naturally we define the mapF x : Y T → R ∪ {-∞} by F x (y) = sup f ∈F log P f (y|x(y)),and then we see thatE y∼P T t=1 ℓ(P t , y t ) -inf f ∈F T t=1 ℓ((f (x t (y)), y t ) = H(P ) + E y∼P [F x (y)].For any given tree x, notice that the optimization problem supP ∈∆(Y T ) H(P ) + E y∼P [F x (y)]is actually a maximization problem in the form of max P ∈∆(Y T ) H(P ) + ⟨P, v⟩, where v is some |Y| T -dimensional vector. According to the conjugacy between negative entropy function and logsum-exp function, the optimal P * is given byP * (y) = exp(F x (y)) y ′ exp(F x (y ′ )) = sup f ∈F P f (y|x(y)) y ′ sup f ∈F P f (y ′ |x(y ′ )), ∀y ∈ Y T .Note that the above formula for P * is also valid when F x (y) = -∞ for some y, since P * should be supported on {y ∈ Y T : F x (y) > -∞}, and F x (y) cannot be -∞ for all y due to Lemma D.1. The associated value of this maximization problem is log y exp(F x (y)) = log y sup f ∈F P f (y|x(y)) .In the proof of Lemma A.1, 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 ,EQUATIONProof of Lemma A.4 To get Eq. ( 7), we simply need to reverse the order of sup and inf at each time in the extensive formulation of minimax regret and produce an inequality:R T (F) = sup x1 inf p1 sup y1 • • • sup x T inf pT sup y T R T (F; p1:T , x 1:T , y 1:T ) = ⟪sup xt inf pt sup yt ⟫ T t=1 T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f (x 1:t , y 1:t-1 ), y t ) = ⟪sup xt inf pt sup yt ⟫ T -1 t=1 sup x T inf pT sup p T E y T ∼p T T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) ≥ ⟪sup xt inf pt sup yt ⟫ T -1 t=1 sup x T sup p T inf pT E y T ∼p T T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) = ⟪sup xt inf pt sup yt ⟫ T -1 t=1 T -1 t=1 ℓ(p t , y t ) + sup x T sup p T inf pT E y T ∼p T ℓ(p T , y T ) -E y T ∼p T inf f ∈F T t=1 ℓ(f t , y t ) .Iterating the argument and rearranging terms as above, we will get thatR T (F) ≥ ⟪sup xt sup pt E yt∼pt ⟫ T t=1 sup f ∈F T t=1 inf pt E yt∼pt [ℓ(p t , y t )] -ℓ(f t , y t ) = ⟪sup xt sup pt E yt∼pt ⟫ T t=1 sup f ∈F T t=1 E yt∼pt [ℓ(p t , y t )] -ℓ(f t , y t ) = sup x,pE y∼p [R T (F; p(y), x(y), y)].To remove the reliance on Eq. ( 4), we introduce a smooth truncated version of F that always satisfies Eq. ( 4) and study its minimax regret as well as 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 δ ∈ (0, 1/2) and f : (X × Y) * × X → ∆(Y), we use f δ to denote its smooth truncated counterpart τ δ • f ; for any hypothesis class F, we use F δ to denote the corresponding smooth truncated classτ δ • F = {τ δ • f : f ∈ F}.It is easy to verify that any smooth truncated class F δ satisfies Eq. ( 4) and henceR T (F δ ) = sup x log S T (F δ |x).Next we control the effect of truncation on the minimax regret.Lemma A.5 For any F, T and δ ∈ (0, 1/2),R T (F) ≤ R T (F δ ) + T • log(1 + |Y|δ).Proof of Lemma A.5 Fix threshold δ ∈ (0, 1/2) and hypothesis f . By Lemma A.7, for any given sequences x 1:T , y 1:T , there isEQUATIONThen, for any sequence of predictions p1:T , R T (F; p1:T , x 1:T , y1:T ) = T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f t , y t ) ≤ T t=1 ℓ(p t , y t ) -inf f δ ∈F δ T t=1 ℓ(f δ t , y t ) + T • log(1 + |Y|δ) = R T (F δ ; p1:T , x 1:T , y 1:T ) + T • log(1 + |Y|δ), which concludes the proof. ■ Lemma A.6There exists a constant M (T ) < ∞ that only depends on T such that for any f, x 1:T ∈ X T , y 1:T ∈ Y T and δ ∈ (0, 1/2),P f δ (y 1:T |x 1:T ) ≤ P f (y 1:T |x 1:T ) + δ • M (T ).Proof of Lemma A.6 Fix threshold δ ∈ (0, 1/2), hypothesis f and sequences x 1:T , y 1:T . ThenP f δ (y 1:T |x 1:T ) = T t=1 f δ t (y t ) = t f t (y t ) + δ 1 + |Y|δ ≤ t (f t (y t ) + δ) = t f t (y t ) + δ • t t ′ ̸ =t f t ′ (y t ′ ) + • • • + δ T ≤ t f t (y t ) + δ • M (T ) = P f (y 1:T |y 1:T ) + δ • M (T ),where we can set M (T ) = T + T 2 + T 3 + • • • + T T since f t (y t )'s are bounded by 1. ■Now we are fully prepared to finish the proof of Theorem 3.2, our main result in Section 3.Proof of Theorem 3.2 By Lemma A.6, we have that for any context tree x of depth T ,y∈Y T sup f δ ∈F δ P f δ (y|x(y)) ≤ y∈Y T sup f ∈F P f (y|x(y)) + δ • M (T ) • |Y| T . Thus R T (F δ ) = sup x log S T (F δ |x) = sup x log   y∈Y T sup f δ ∈F δ P f δ (y|x(y))   ≤ sup x log   y∈Y T sup f ∈F P f (y|x(y)) + δ • M (T ) • |Y| T   = log   sup x y∈Y T sup f ∈F P f (y|x(y)) + δ • M (T ) • |Y| T   .Together with Lemma A.5, we get that for any δ ∈ (0, 1/2),EQUATIONAfter sending δ → 0 + on the RHS of Eq. ( 9),R T (F) ≤ log   sup x y∈Y T sup f ∈F P f (y|x(y))   = sup x log S T (F|x).Recall that we have R T (F) ≥ sup x log S T (F|x) from Lemma A.4 and Lemma A. Starting from Theorem 3.2 that R T (F) = sup x log S T (F|x), we haveR T (F) = sup x log y sup f ∈F P f (y|x(y)) ≤ sup x log   y f ∈F P f (y|x(y))   = sup x log   f ∈F y P f (y|x(y))   = log |F|,where the last equality is due to Lemma D.1.It suffices to show that R FD T (F Lin ) ≥ √ T /4. In particular, we only need to find some context sequence x 1:T such that log S T (F Lin |x 1:T ) ≥ √ T /4 due to Proposition 2.5. Here we pick x 1:T such that x t are unit vectors and x t ⊥ x t ′ whenever t ̸ = t ′ . Such sequence exists because the dimension of B 2 is no smaller than T . In this way, for each possible label sequence y 1:T ∈ {0, 1} T , we can see that the f w ∈ F Lin that is indexed byw = T t=1 2y t -1 √ T x t achieves likelihood P fw (y 1:T |x 1:T ) = ( 1+1/ √ T 2 ) T . Therefore, S T (F Lin |x 1:T ) = y 1:T ∈{0,1} T sup f ∈F Lin P f (y 1:T |x 1:T ) ≥ y 1:T ∈{0,1} T 1 + 1/ √ T 2 T = 1 + 1/ √ T T , which implies that R FD T (F Lin ) = log S T (F Lin |x 1:T ) ≥ T log(1 + 1/ √ T ) ≥ √ T /4 for all T ≥ 1.Notations. Again we may use f t to denote the probability vector f (x 1:t , y 1:t-1 ) ∈ ∆(Y) produced by hypothesis f at time t when the context and label sequences x 1:T , y 1:T are clear from the context. For a context tree x of depth T -t and a path y ∈ Y T -t , we re-index x(y) as (x t+1 (y), . . . , x T (y)) whenever it takes the last T -t entries of the entire context sequence. And we do the same for the probabilistic tree p as well. That is, whenever y = (y t+1 , . . . , y T ) ∈ Y T -t takes the last T -t entries of the whole label sequence and y ∼ p, then we will denote this label generating process by y t+1 ∼ p t+1 (y), . . . , y T ∼ p T (y).Recall that the minimax regret isR T (F) = ⟪sup xt inf pt sup yt ⟫ T t=1 T t=1 ℓ(p t , y t ) -inf f ∈F T t=1 ℓ(f (x 1:t , y 1:t-1 ), y t ) .Through this extensive form of the minimax regret, we know that given x 1:t , y 1:t-1 , the minimax prediction p * t at round t is the one that minimizes the following expression over all pt ∈ ∆(Y): sup yt ℓ(p t , y t ) + G(F, x 1:t , y 1:t ) .The crux of the proof is to show the following:Lemma B.1 For any hypothesis class F and sequences x 1:t ∈ X t , y1:t ∈ Y t , G(F, x 1:t , y 1:t ) = sup x log S x1:t,y1:t T (F|x).The proof of Lemma B.1 is done by essentially following the same strategy in Appendix A since G(F, x 1:t , y 1:t ) admits a similar extensive form with the minimax regret R T (F). For completeness we provide its proof in Appendix B.2. Given Lemma B.1, we have .p * t = argmin pt∈∆(Y)We apply the following result to solve the above program:EQUATIONwhere the infimum in Eq. (11) spans over all probability densities p : Y → [0, +∞) with respect to µ, and the infimum is reached at p * = g Y g(y)dµ .Letting g(y) = sup x S x1:t,(y1:t-1,y) T(F|x) ∈ [0, 1] and µ be the counting measure on the finite space Y, we can apply Lemma B.2 whenever not all g(y)'s are 0. In this case, we solve thatp * t (y) = g(y) y ′ ∈Y g(y ′ ) = sup x S x1:t,(y1:t-1,y) T (F|x) y ′ ∈Y sup x S x1:t,(y1:t-1,y ′ ) T (F|x), ∀y ∈ Y.On the other hand, if g(y) = 0, ∀y ∈ Y, then any pt such that pt (y) > 0, ∀y ∈ Y, is an minimax optimal prediction. Moreover, it implies that P f (y 1:t-1 |x 1:t-1 ) = 0, ∀f ∈ F. This is because for arbitrary context tree x, 0 = yt y∈Y T -t P f (y 1:t , y|x 1:t , x(y))= yt P f (y 1:t |x 1:t ) = P f (y 1:t-1 |x 1:t-1). So the cumulative loss for each expert f up to round t -1 already blows up to +∞ and the learner only needs to predict an arbitrary p ∈ ∆ + (Y) in all remaining rounds to achieve R T (F; p1:T , x 1:T , y 1:T ) = -∞.Overall, we can see that the minimax optimal prediction p * t ∈ ∆(Y) at round t given x 1:t , y (F|x) > 0. Otherwise, select p * t to be an arbitrary element in ∆ + (Y) (and so do all remaining rounds).Recall that for any hypothesis class F and sequences x 1:t ∈ X t , y1:t ∈ Y t , G(F, x 1:t , y 1:t ) = ⟪sup xs inf ps sup ys ⟫ T s=t+1 T s=t+1 ℓ(p s , y s ) -inf f ∈F T s=1 ℓ(f (x 1:s , y 1:s-1 ), y s ) = ⟪sup xs inf ps sup ps E ys∼ps ⟫ T s=t+1 T s=t+1 ℓ(p s , y s ) -inf f ∈F T s=1 ℓ(f (x 1:s , y 1:s-1 ), y s ) .To prove Lemma B.1, we need the following lemmas.EQUATIONAnd whenever for everyEQUATIONthenEQUATIONProof of Lemma B.3 First we see that similar to the proof of Lemma A.4, we can reverse every pair of sup over p s and inf over ps in the extensive formulation of G(F, x 1:t , y 1:t ) and rearrange terms to obtainG(F, x 1:t , y 1:t ) ≥ ⟪sup xs sup ps E ys∼ps ⟫ T s=t+1 T s=t+1 inf ps E ys∼ps [ℓ(p s , y s )] -inf f ∈F T s=1 ℓ(f s , y s ) ,and again due to the nature of log loss,G(F, x 1:t , y 1:t ) ≥ ⟪sup xs sup ps E ys∼ps ⟫ T s=t+1 T s=t+1 E ys∼ps [ℓ(p s , y s )] -inf f ∈F T s=1 ℓ(f s , y s ) = sup x,p E y∼p T s=t+1 E ys∼ps(y) [ℓ(p s (y), y s )] -inf f ∈F T s=1 ℓ(f s , y s ) ,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 ps to ∆ δ (Y) for any threshold δ ∈ (0, 1/2) which yieldsG(F, x 1:t , y 1:t ) ≤ ⟪sup xs sup ps E ys∼ps ⟫ T s=t+1 T s=t+1 inf ps∈∆ δ (Y) E ys∼ps [ℓ(p s , y s )] -inf f ∈F T s=1 ℓ(f s , y s ) ≤ ⟪sup xs sup ps E ys∼ps ⟫ T s=t+1 T s=t+1 inf ps E ys∼ps [ℓ(p s , y s )] -inf f ∈F T s=1 ℓ(f s , y s ) + |Y|δT.So Eq. ( 14) is proved by sending δ → 0 + on the RHS of the last inequality and the established Eq. ( 12). ■ Lemma B.4 For any hypothesis class F and sequences x 1:t ∈ X t , y1:t ∈ Y t , sup x,p E y∼p T s=t+1 E ys∼ps(y) [ℓ(p s (y), y s )] -inf f ∈F T s=1 ℓ(f s , y s ) = sup x log S x1:t,y1:t T (F|x).Proof of Lemma B.4 The proof follows that of Lemma A.3. By replacing the probabilistic tree p by the joint distributionP ∈ ∆(Y T -t ), we get sup x,p E y∼p T s=t+1 E ys∼ps(y) [ℓ(p s (y), y s )] -inf f ∈F T s=1 ℓ(f s , y s ) = sup x,P E y∼P T s=t+1 ℓ(P s , y s ) -inf f ∈F T s=1 ℓ(f s , y s ) = sup x sup P ∈∆(Y T -t ) H(P ) + E y∼P sup f ∈F log P f (y 1:t , y|x 1:t , x(y)) .Similarly, for any fixed x, define the map F x1:t,y1:tx : Y T -t → R ∪ {-∞} by F x1:t,y1:t x (y) = sup f ∈F log P f (y 1:t , y|x 1:t , x(y)),and now we solvesup P ∈∆(Y T -t ) H(P ) + E y∼P [F x1:t,y1:t x (y)].If there exists some y ∈ Y T -t such that F x1:t,y1:t x (y) > -∞, then the optimal P * is given by P * (y) = exp(F x1:t,y1:t x (y))y ′ exp(F x1:t,y1:t x (y ′ )) = sup f ∈F P f (y 1:t , y|x 1:t , x(y)) y ′ sup f ∈F P f (y 1:t , y ′ |x 1:t , x(y ′ )), ∀y ∈ Y = supx log S x1:t,y1:t T (F|x).However, if F x1:t,y1:t x (y) = -∞ for all y, then it implies that for any context tree x, path y, and f ∈ F, P f (y 1:t , y|x 1:t , x(y)) = 0 and hence, sup x,p E y∼p T s=t+1 E ys∼ps(y) [ℓ(p s (y), y s )] -inf f ∈F T s=1 ℓ(f s , y s ) = sup x sup P ∈∆(Y T -t ) H(P ) + E y∼P [F x1:t,y1:t x (y)] = -∞ = sup x log y sup f ∈F P f (y 1:t ,) + T • log(1 + |Y|δ) = sup x log S x1:t,y1:t T (F δ |x) + T • log(1 + |Y|δ) = sup x log y∈Y T -t sup f δ ∈F δ P f δ (y 1:t , y|x 1:t , x(y)) + T • log(1 + |Y|δ) ≤ sup x log y∈Y T -t sup f ∈F P f (y 1:t , y|x 1:t , x(y)) + δ • M (T ) • |Y| T + T • log(1 + |Y|δ) = log sup x y∈Y T -t sup f ∈F P f (y 1:t , y|x 1:t , x(y)) + δ • M (T ) • |Y| T + T • log(1 + |Y|δ),where we have applied Lemma A.7, Lemma B.3, Lemma B.4, and Lemma A.6 accordingly. Similarly, we send δ → 0 + on the RHS of the last inequality and get G(F, x 1:t , y 1:t ) ≤ sup In this section we generalize our analysis to the setting where the context space can evolve over time.We model time-varying context sets by a sequence of maps X t : X t-1 × Y t-1 → 2 X , t ∈ [T ] as in [RS15; BFR20] . In each round t, instead of picking any context from X , the nature is now required to only choose x t from X t (x 1:t-1 , y 1:t-1 ) ⊆ X . Then the minimax regret with respect to (X t ) t∈[T ] is rewritten asR T (F) = ⟪ sup xt∈Xt(x1:t-1,y1:t-1) inf pt sup yt ⟫ T t=1R T (F; p1:T , x 1:T , y 1:T ).A context tree x is consistent with respect to (X t ) t∈[T ] if for all t ∈ [T ] and y ∈ Y T , x t (y) ∈ X t (x 1:t-1 , y 1:t-1 ). Then our results in Section 3 and Section 4 can be generalized simply by replacing the supremum over all context trees (of depth T ) by the supremum over all consistent context trees. For example, we will have In fact, the gap between them is at most a polylog factor, as we state and prove below. 1 The proof of H ∞ (F, α, T ) ≤ H G (F, α, T ) is also included for completeness. Before stating the results, we introduce the definition of sequential fat-shattering dimension.R T (F) = sup x:x is consistent log S T (F|xDefinition C.1 We say an X -valued binary tree x of depth d is α-shattered by a class F ⊆ [0, 1] X for some α > 0, if there exists a [0, 1]-valued binary tree s of depth d such that∀y ∈ {0, 1} d , ∃f ∈ F, s.t. (2y t -1) • (f (x t (y)) -s t (y)) ≥ α 2 , ∀t ∈ [d].In this case, s is called the witness of the shattering. The sequential fat-shattering dimension of F at scale α, denoted by sfat α (F), is the largest d such that some depth-d context tree is α-shattered by F.Proposition C.2 For any scale α > 0, we haveH ∞ (F, α, T ) ≥ min{T, sup α ′ >α sfat 2α ′ (F)} • log(2).Therefore, together with H ∞ (F, α, T ) ≤ H G (F, α, T ) and the folklore H G (F, α, T ) ≤ O(sfat α (F) log(T /α)), we conclude that the regret upper bounds O(inf α>0 {αT + H(F, α, T )}), H ∈ {H ∞ , H G }, differ by at most a polylog factor.Proof of Proposition C.2 Fix any α ′ > α > 0 and let d α ′ denote min{T, sfat 2α ′ (F)}. Then there exists a context tree x and a witness tree s, both of depth d α ′ , such that for any path y ∈ {0, 1} d α ′ , there exists an f ∈ F such thatEQUATIONLet V x,α be an arbitrary sequential ℓ ∞ covering of F on x. Now we select a path y and a sequence of subsets V (t)x,α ⊆ V x,α , t ∈ [d α ′ ] in the following recursive way. Define V (0)x,α = V x,α . For each t ∈ [d α ′ ], choose y t ∈ {0, 1} such that 2y t -1 ∈ {-1, +1} is the minority among all sgn(v t (y 1:t-1 ) -s t (y 1:t-1 )), v ∈ V (t-1) x,α (ignoring those of 0's). Finally update V (t)x,α = {v ∈ V (t-1) x,α : sgn(v t (y 1:t-1 ) -s t (y 1:t-1 )) = 2y t -1}.First we argue that, if there is any timet ′ ∈ [d α ′ ] such that V (t ′ -1) x,α ̸ = ∅, V (t ′ )x,α = ∅, then V x,α is not a valid cover of F on x. Otherwise, recall we have selected y 1 , . . . , y t ′ -1 . Now pick an arbitrary y t ′ ∈ {0, 1}. By Eq. ( 15) we can find some f ∈ F such that (2y t -1) • (f (x t (y 1:t-1 ))s t (y1:t-1 )) > α, ∀t ∈ [t ′ ]. Since V x,α is a covering at scale α, there is v ∈ V x,α such that |v t (y) - f (x t (y))| ≤ α, ∀t ∈ [t ′ ]. This implies that sgn(f (x t (y)) -s t (y)) = sgn(v t (y) -s t (y)) = 2y t -1, ∀t ∈ [t ′ ]. So we can always find some member of V(t ′ -1) x,αto match the minority sign ofv t ′ (y 1:t ′ -1 ) -s t ′ (y 1:t ′ -1 ), v ∈ V (t ′ -1) x,α , which means that V (t ′ )x,α ̸ = ∅ and yields a contradiction.(t) x,α | ≥ 1, ∀t ∈ [d α ′ ]. By design |V (t) x,α | ≤ |V (t-1) x,α |/2, ∀t ∈ [d α ′ ], so we must have |V x,α | = |V (0) x,α | ≥ 2 d α ′ . As the choice of covering is arbitrary, the covering number N ∞ (F • x, α, d α ′ ) is also lower bounded by 2 d α ′ and hence H ∞ (F, α, d α ′ ) ≥ d α ′ • log(2). If sup α ′ >α sfat 2α ′ (F) ≤ T , then we get that H ∞ (F, α, T ) ≥ sup α ′ >α H ∞ (F, α, sfat 2α ′ (F)) ≥ sup α ′ >α sfat 2α ′ (F) • log(2). If there is some α ′ > α such that sfat 2α ′ (F) ≥ T , then H ∞ (F, α, T ) = H ∞ (F, α, d α ′ ) ≥ T • log(2).Combining these two cases together, we have Proof of Proposition C.3 Fix arbitrary context tree x. For any g ∈ G α , define the [0, 1]-valued tree v g by v g t (y) = g(x 1:t (y)), ∀t ∈ [T ], y ∈ Y T . Now let V x,α = {v g : g ∈ G α } and we will show that V x,α is indeed a sequential cover of F • x at scale α.H ∞ (F, α, T ) ≥ min{T, sup α ′ >α sfat 2α ′ (F)} • log(2).For any f ∈ F and y ∈ Y T , tree x yields a length-T sequence x 1:T (y) and by definition of the global sequential covering, there exists g ∈ G α such that|f (x t (y)) -g(x 1:t (y))| ≤ α, ∀t ∈ [T ]. So by our construction of V x,α , v g ∈ V x,α holds |f (x t (y)) -v g t (y)| = |f (x t (y)) -g(x 1:t (y))| ≤ α, ∀t ∈ [T ], which yields our claim after observing |V x,α | ≤ |G α |. ■Lemma D.1 For any X -valued Y-ary context tree x of depth T , and f : (X × Y) * × X → ∆(Y), we haveEQUATIONwhere we recall that x(y) denotes the context sequence (x 1 (y), . . . , x T (y)).• 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 a 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 to 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 is 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 the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors 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 be possible for other researchers to have some path to reproducing or verifying the results.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to 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 be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Justification: There are no experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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 a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is 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 are 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Justification: There are no experiments.Guidelines:• The answer NA means that the paper does not include experiments.• 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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We have read the code and do not see any violation. Our work relates to the mathematical foundations of a basic task in ML.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 probabilistic forecasting, and a (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 or 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards38th Conference on Neural Information Processing Systems (NeurIPS 2024).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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The 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. 

Moreover, 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.
questions: questions: Has a contextual algorithm similar cNML been introduced before ? If so what are the benefits ? 

Any specific example of the multiary tree would be appreciated.
limitations: limitations: Nothing significant.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. Could the authors more clearly explain the novelty in technical contributions in their work?

2.  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.

3. 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.

4. 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?

5. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: The paper does not include experimental results to support the theoretical findings.
questions: 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not see any significant weaknesses in the paper. However, I would like to outline a few minor remarks as follows:

1. 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.)

2. 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.)

3. 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.)

4. 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.

[BHS23] Bhatt, A., Haghtalab, N., and Shetty, A. (2023). Smoothed analysis of sequential probability assignment. NeurIPS 2023.

[RSS12] Rakhlin, S., Shamir, O., & Sridharan, K. (2012). Relax and randomize: From value to algorithms. NeurIPS 2012.
questions: 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})$.

Can the characterization introduced in the current paper provide an alternative (perhaps simpler) derivation of this $\tilde{O}(\sqrt{T})$ regret?
limitations: limitations: N/A

Comments: title: Thank you!
Thank you!
Thank you!
Thank you for the response.
comment: Thank you for the positive comment. We are happy to see that some of your concerns are addressed.
Thank you for the encouraging comment. We will revise our paper as suggested.
Thank you for the clarification. We will incorporate all your suggestions into the final revision.
Thank you for your response. Parts of my concerns have been addressed and I would be happy to increase my score.
Thank you for the detailed response.  

To clarify, my score is not based on the presentation as the issues I raised are minor.  I personally find the observation that the contextual Shtarkov sum can be realized as the expected supremum of a martingale to be quite cool; I simply was making the minor point that the section did not seem to be connected to the rest of the paper in a natural way.

On the subject of improved bounds, I would encourage you to include a detailed discussion of the linear vs absolute-linear example in the paper.  What is the difference in the rates of online learning these classes with log loss and just how loose is a covering number or Dudley based bound here?

Regarding the global rebuttal, I agree with you that the problem studied is an important one, but I remain somewhat confused as to the specific claimed novel techniques applied and am not yet fully convinced that the assumed regularity properties of the class $\mathcal F$ that are required by earlier cited works could not be avoided with very minor tweaks to the proofs, certainly if one is willing to pay a constant factor on the regret.  I will raise my score on the assumption that the authors will include a detailed discussion of at least one example, such as the linear vs absolute linear case, where their new complexity measure improves on the local covering number based bound beyond constant factors.
I thank the authors for the detailed response. After reading the rebuttal and checking the feedback from other reviewers, I have decided to confirm my strong accept recommendation. This is a clear significant result that resolves a long-standing problem, and I will argue for acceptance.