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.

Clarification on our technical contribution

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

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

On the relation to [BHS23] and the relaxation framework

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

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

On section 3.2 and the linear class

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

[RSS12] Rakhlin, Shamir, and Sridharan. (2012). Relax and randomize: From value to algorithms.
[RS15]: Rakhlin and Sridharan. (2015). Sequential probability assignment with binary alphabets and large classes of experts.
[RST15] Rakhlin, Sridharan, and Tewari. (2015). Sequential complexities and uniform martingale laws of large numbers.
[BFR20] Bilodeau, Foster, and Roy. (2020). Tight bounds on minimax regret under logarithmic loss via self-concordance.
[BHS23]: Bhatt, Haghtalab, and Shetty. (2023). Smoothed analysis of sequential probability assignment.

We thank the reviewer for their constructive review. Below, we address your comments on experimental results and our cNML algorithm.

On experimental results and our cNML

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

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

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.

On improved bounds on the minimax regret

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

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

Moreover, 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: The upper bound on the regret in [BFR20] is non-constructive (no algorithm is provided). While [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.

On generalizing [BFR20] beyond binary labels​

First, 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.

On the presentation

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

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

[RST10]: Rakhlin, Sridharan, and Tewari. (2020). Online learning: Random averages, combinatorial parameters, and learnability.
[RST15] Rakhlin, Sridharan, and Tewari. (2015). Sequential complexities and uniform martingale laws of large numbers.
[DG22]: Daskalakis and Golowich. (2022). Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games.
[BFR20]: Bilodeau, Foster, and Roy. (2020). Tight bounds on minimax regret under logarithmic loss via self-concordance.
[WGHS22]: Wu, Heidari, Grama, and Szpankowski. (2022). Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm.
[WHGS23]: Wu, Heidari, Grama, and Szpankowski. (2023). Regret Bounds for Log-loss via Bayesian Algorithms.

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.

On cNML

Indeed, [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. More 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). Moreover, 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.

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

On the presentation

Thank you for useful suggestions on the improvement of our presentation. We will gladly incorporate them into our final revision. We 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$.

[Sht87] Shtarkov. (1987). Universal Sequential Coding of Single Messages.
[BFR20] Bilodeau, Foster, and Roy. (2020). Tight bounds on minimax regret under logarithmic loss via self-concordance.