acceptodds
Under review as a conference paper at ICLR 2027

The Price of Adaptivity in Bandit Multiclass Classification: Minimal Separation and Sharp Tower Asymptotics

Abstract

We resolve the existence component of a foundational open problem posed at NeurIPS 2024 concerning the price of adversarial adaptivity in bandit multiclass classification. The optimal expected mistake bound against an adaptive adversary is at most a multiplicative above the oblivious bound, where . We prove that genuine concept classes can incur a strict adaptive–oblivious gap. First, a four-function class on two points with has adaptive value and oblivious value . No class of at most three functions separates, so four is optimal. Second, for the multi-shield towers , we prove a closed-form recursion for the adaptive value of every reachable state. We obtain and , hence exactly. Third, our capping theory bounds natural amplification constructions. For atoms whose adaptivity ratios are uniformly bounded by , unions with disjoint label blocks obey at any finite nesting depth. An exact Hamming-ball formula shows that the additive localization surcharge already reaches for two overlapping layers. Every exact value has a certificate: primal–dual certificates at each game state for adaptive play, and explicit priors and sequences for oblivious play. The included standard-library script re-checks them all. We also establish necessary conditions for linear separation: , and the concept class must have at least exponential size.

Primary area:
learning theory
Keywords:
online learning, bandit multiclass classification, adaptive adversaries, oblivious adversaries, mistake bounds, learning theory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_5HZLOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the optimal expected number of mistakes in realizable multiclass classification with bandit feedback, comparing adaptive adversaries that preserve feedback consistency with oblivious adversaries that commit to a realizable sequence. It constructs a four-function class with adaptive value 35/2935/29 and oblivious value 7/67/6, and proves that fewer functions cannot separate the two models. For the rr-point binary cube augmented with rr distinct constant-label shields, denoted HrH_r, it derives an exact adaptive-state recursion and proves A(Hr)=5r/8+O(r)A(H_r)=5r/8+O(\sqrt r) and B(Hr)=r/2+log⁡2r−log⁡2log⁡2r+O(1)B(H_r)=r/2+\log_2 r-\log_2\log_2 r+O(1), giving a limiting ratio of 5/45/4. Further results bound amplification through specified forms of class union and give necessary conditions for a linear-in-kk separation. The evidence consists of proofs and finite exact or interval certificates. The worst-case adaptivity ratio as a function of the number of labels remains open.

Critical strengths

S1. A precise answer to the existence question. The four-function witness establishes that adaptivity can increase the optimal mistake bound for genuine concept classes, while the cardinality argument proves that the witness is minimal. Matching learner and adversary arguments make the separation convincing; in particular, the oblivious upper bound covers every fixed target and instance sequence. This answers the existence aspect of the question raised by Filmus et al. (2024).

S2. A substantive analysis beyond the finite witness. Diagnostic invariance reduces the tower games to a two-parameter recursion, and separate adaptive and oblivious analyses establish the exact limiting ratio 5/45/4. The all-negative-path lower bound and threshold learner also identify the logarithmic correction on the oblivious side. These results explain the behavior of an explicit growing family rather than relying only on small numerical examples.

Critical weaknesses

No critical weakness. The following concerns are minor.

W1. Some quantitative bounds remain loose. The composition framework has limited quantitative precision. Remark 5.6 (p. 8) explains that its multiplicative caps for nontrivial atoms do not rule out ratios between 5/45/4 and 33. Remark E.1 (pp. 20–21) gives a concrete example where the localization-rank bound charges an additional 2m−12m-1, while the actual additional cost is only Θ(m)\Theta(\sqrt m). These acknowledged limitations restrict how precisely the framework characterizes composition costs. Separately, Section 4.2 (p. 6) leaves the tightness of the adaptive O(r)O(\sqrt r) remainder unresolved. This limits the precision beyond the leading term without weakening the exact limiting ratio 5/45/4.

W2. A notation change interrupts the central example. Section 3 (p. 4) names the hypotheses z,e,f,gz,e,f,g, then uses m,qm,q and Follow(m)\mathrm{Follow}(m) in its explanation and table. The renaming and subroutines are explained in Appendix B.1 (p. 13), but consulting the appendix is necessary to follow this part of the main-text example.

Questions for authors
  1. Composition bounds (W1): What is the main source of slack in the localization-rank bound for the Hamming-cover example of Remark E.1?

  2. Future-direction interpretation (W1): How do you interpret the finite-range excess doubling ratios reported in Section 4.2? Although they do not establish an asymptotic order, do they motivate a conjecture about the growth of A(Hr)−5r/8A(H_r)-5r/8?

4 comments
AuthorsOpenReview ↗

Response (1/3): the open problem is closed

Thank you very much for the careful and review, and in particular for the close reading of the four-function witness and the tower analysis. As the summary of the review notes, the worst-case adaptivity ratio as a function of the number of labels was left open; we have now resolved this question.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

The revised version completely resolves the open problem of Filmus et al. (NeurIPS 2024): in its default weakly realizable model, the worst-case price of adaptivity for concept classes is Θ(log⁡k)\Theta(\log k), where kk is the number of labels.

The open problem reads in full (Filmus et al., Section 4.1): "The price of adaptivity for concept classes. Our proof of Theorem E.1 uses pattern classes. Can we prove it using only concept classes, similarly to Theorem F.1? If not, what is the price of adaptivity when learning concept classes?" The revised version answers both questions with two new results. Section 3 shows that for every concept class, finite or infinite, the optimal adaptive mistake bound A(H)A(H) is at most (1+o(1))ln⁡k(1+o(1))\ln k times the optimal oblivious bound B(H)B(H), so the Ω(k)\Omega(k) separation of their Theorem E.1 cannot be achieved with concept classes. Sections 4 and 5 construct explicit finite concept classes with ratio (2/3−o(1))ln⁡k(2/3-o(1))\ln k; for instance, ratios at least 2, 3 and 4 are reached with 6364, 71922 and 628217 labels (p. 9 and Appendix E.6). Hence the price for concept classes is Θ(log⁡k)\Theta(\log k) (Theorem 2.1). As with the linear price for pattern classes, the price is thus determined up to constant factors. The exact constant in front of ln⁡k\ln k, between 2/32/3 and 11, remains open and is a natural direction for future work.

The table below sums up, for the three questions behind this open problem, where the submitted version stood and what the revised version proves.

Submitted versionRevised version
Gap growing with kk?Open (ratios 30/29 and 5/4)Yes: (2/3−o(1))ln⁡k(2/3-o(1))\ln k (Theorem 5.1)
Linear gap possible?OpenNo: at most (1+o(1))ln⁡k(1+o(1))\ln k (Theorem B.1)
Order of the priceOpenΘ(log⁡k)\Theta(\log k) (Theorem 2.1): resolved

The revised version keeps all theorems, propositions and examples of the submitted version, together with their proofs, techniques and certificates; in particular, the four-function witness and the tower analysis are kept in full (Section 6 and Appendices H–I). In addition, the two new results resolve the question the submitted version left open (its Open Problem 6.1): how the price grows with kk. Together with what the submitted version established, that concept classes can separate at all, with exact minimal examples, they completely resolve the open problem of Filmus et al.

The localization results of the submitted version, which the review discusses under W1, fit this picture: nesting classes on disjoint label blocks keeps the ratio at most C0+2C_0+2 at every finite depth when the innermost classes have ratio at most C0C_0 (Theorem J.2; Theorem 5.2 of the submitted version), and the construction of Sections 4–5 is not subject to this bound, since its tails reuse one label alphabet.

AuthorsOpenReview ↗

Response (2/3): how the open problem is solved

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

How the upper and lower bounds are obtained. In a concept class, every function is fixed in advance on the whole domain. An adaptive adversary may still decide, as the game unfolds, which function it is following, but every label it declares correct must be supported by some function consistent with all feedback so far. Both bounds rest on the same harmonic-sum mechanism, used once by the learner and once by the adversary; this is why the answer is logarithmic.

Upper bound: adaptivity costs at most a factor of about ln⁡k\ln k.

  1. Measuring what remains to be learned. An oblivious adversary can force two kinds of cost: searching for the correct label among the feasible ones, and resolving binary splits of the class (does the target take label aa at instance xx?). We combine both into one potential, which never exceeds (1+o(1))B(H)(1+o(1))B(H).
  2. Paying for each mistake. In every round, the learner chooses its prediction distribution so that, whichever feasible label the adversary then declares correct, the expected mistake is at most (1+o(1))ln⁡k(1+o(1))\ln k times the expected drop of the potential (inequality (9)). Summing over the rounds, the total expected number of mistakes is at most (1+o(1))ln⁡k(1+o(1))\ln k times the initial potential, which gives A(H)≤(1+o(1))ln⁡k⋅B(H)A(H) \le (1+o(1))\ln k \cdot B(H).
  3. Where ln⁡k\ln k comes from. A label whose correct guess lowers the potential a lot needs only a small probability, roughly inversely proportional to that drop. The search cost keeps too many labels from having small drops. Leaving out the smallest drop, the jj smallest of the others add up to at least about j2/2j^2/2, much as an oblivious search reaches the jjth label only after about jj mistakes. A label that makes little progress when guessed correctly makes substantial progress when guessed wrongly, and the proof uses this as well. Comparing the drops with the sequence 12,32,…\frac12,\frac32,\dots then gives the factor Q(k)=∑j=1k−11j−1/2=ln⁡k+O(1)Q(k)=\sum_{j=1}^{k-1}\frac{1}{j-1/2}=\ln k+O(1) in the cost.

Lower bound: a factor of order ln⁡k\ln k cannot be avoided.

  1. The construction. We build one finite class from blocks of functions, called worlds. All worlds share a set of top instances, where a correct prediction identifies the world, and each world then continues on its own tail class. On the top instances, heavy worlds take all binary patterns of two private labels, and light worlds take one constant label.
  2. Keeping every fixed target cheap. Against a fixed target, a learner first searches for the target's world, trying heavy labels for a bounded number of rounds and then the light worlds in a fixed order, and then learns its tail. Light worlds that come later in this order receive tails that are cheaper by exactly the extra search cost, and a heavy target is found before the light scan except with small probability. So every fixed target costs at most the same budget, which bounds BB.
  3. Keeping many targets alive. An adaptive adversary need not commit to a target. While it forces mistakes among the heavy worlds, it keeps many light worlds feasible.
  4. Why the learner cannot protect all of them. During the search on the top instances, suppose that every feasible label led to an adaptive cost below the bound the construction maintains at that stage. Then each light label would claim a share of the learner's probability, set by weighing the mistake on a miss against the cheaper tail after a hit; this share is roughly of order 1/(ρj)1/(\rho j), where ρ\rho is the target ratio and jj is the number of mistakes an oblivious search makes before reaching that label. With enough light labels these shares add up to more than one, so they cannot all be met: some feasible label still forces the bound, and the adversary declares it. Once the adversary's surplus is used up, a surviving heavy world's tail carries the bound.
  5. From the mechanism to the constant 2/32/3. Summing 1/(ρj)1/(\rho j) over the light labels gives about 1ρln⁡(jlast/jfirst)\frac1\rho\ln(j_{\mathrm{last}}/j_{\mathrm{first}}), so keeping enough light worlds multiplies the number of labels by about eρe^{\rho}. In our parameter choice, the heavy part contributes a further factor of about eρ/2e^{\rho/2}, since it uses about that many worlds to supply the adaptive gain. Hence about e3ρ/2e^{3\rho/2} labels suffice, up to factors polynomial in ρ\rho (Theorem 5.1), and nesting the construction on the same labels attains ratio ρ\rho; inverting gives (2/3−o(1))ln⁡k(2/3-o(1))\ln k.
AuthorsOpenReview ↗

Response (3/3): W1, W2, Q1 and Q2

We are grateful for the positive assessment of the paper, and we thank the reviewer for the thoughtful comments on the quantitative bounds and the central example, as well as for the two careful questions.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

W1 (loose quantitative bounds). We agree with these observations: the composition bounds leave room for sharper constants, and the tower remainder is not yet determined. These bounds are not needed for the proof of Theorem 2.1 (Appendix A), and the growth question they bear on is now settled by Theorem 2.1. In detail:

  • The multiplicative composition bounds discussed in Remark J.6 (Remark 5.6 of the submitted version) are unchanged: when some layer is nontrivial, each of them is at least 3B3B, so they limit growth but do not determine the constants of small separations.
  • For the localization-rank bound (Remark E.1, now Remark J.8), the revised remark identifies two sources of slack; see Q1.
  • The order of the O(r)O(\sqrt r) remainder for the towers is still open. It concerns the tower family only and is recorded as a direction for future work at the end of Appendix I.3 and in Section 7.

W2 (notation change in the central example). Thank you for this helpful observation. The main text now presents the four-function class only by its value pairs (Section 6), so no renaming occurs there. In Appendix H.1 (p. 51), the paragraph that contains the table opens with the renaming and its correspondence to the original names: q=fq=f and m=gm=g if the first point played is x1x_1, and q=gq=g and m=fm=f if it is x2x_2. The subroutines Pair and Follow are defined in the same paragraph.

Q1 (source of slack in the localization-rank bound). Two effects add up, and the first one accounts for the factor m\sqrt m. Theorem J.5 charges for localizing and then adds the full value of a layer, but in the two-layer Hamming cover these costs overlap: the coordinates fixed while localizing also count toward that layer's cost. Fair labels on fresh coordinates keep the version space in neither layer for m−1m-1 rounds, so every learner makes at least (m−1)/2(m-1)/2 expected mistakes before localizing, already a factor of order m\sqrt m above the true surcharge Wm=Emax⁡(Z−m,0)=Θ(m)W_m=\mathbb{E}\max(Z-m,0)=\Theta(\sqrt m), where Z∼Bin(2m,1/2)Z\sim\mathrm{Bin}(2m,1/2) (Theorem J.7). Second, the rank itself is large: a valid rank must decrease after every correct prediction at an informative point while it is positive, although such feedback costs nothing, and a history that confirms m−1m-1 predictions of each label on fresh coordinates leaves the version space in neither layer, so every valid rank is at least 2m−12m-1. This costs a further constant factor. Remark J.8 now states both effects, and we thank the reviewer for prompting this clarification.

Q2 (the finite-range doubling ratios). This is an interesting question. In our view, the ratios do not yet support a conjecture. For r=400,800,1600r=400, 800, 1600 the excess E(r)=A(Hr)−5r/8E(r)=A(H_r)-5r/8 satisfies E(2r)/E(r)≈1.284,1.271,1.262E(2r)/E(r)\approx 1.284, 1.271, 1.262 (base-2 logarithms of these ratios: about 0.36, 0.35 and 0.34). An excess E(r)∼crE(r)\sim c\sqrt r would make the ratios approach 2≈1.414\sqrt 2\approx 1.414; the observed values are smaller and still decreasing, so they do not determine the order of E(r)E(r). Since the trend has not stabilized, we do not state a conjecture; the revised version records the comparison with 2\sqrt 2 at the end of Appendix I.3 (p. 56). We agree that the growth of E(r)E(r) is a natural question; as noted under W1, it concerns the tower family only, and we see it as a direction for future work.

Correspondence with the submitted version. To make it easy to compare the two versions, the items discussed in this review appear in the revised version as follows; the general comment contains a reading guide and the full table.

Submitted versionRevised version
Section 3 and Appendix B.1 (four-function example)Section 6 and Appendix H.1
Theorems 4.1–4.4 (tower family)Theorems I.1, I.4, I.5, I.6
Section 4.2 (asymptotics, doubling ratios)Appendices I.3–I.5 (ratios at the end of I.3.2)
Remark 5.6Remark J.6
Remark E.1Remark J.8

Thank you again for the kind words about the witness and the tower analysis, and for the careful questions; we enjoyed thinking about them. We hope Theorem 2.1 answers the open question noted in the review, and we would be glad to clarify anything further.

Thank you for the response and revised manuscript. I keep my positive rating: 4.

To the AC: Given how substantially the paper has changed from the original submission (26 to 68 pages), I don't have enough time to carefully check the added content.

Reviewer_kqxtOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the price of adversarial adaptivity in online multiclass classification with bandit feedback. An oblivious adversary commits to a realizable sequence in advance, whereas an adaptive adversary can respond to the learner’s publicly announced prediction distribution, subject to a consistency requirement ensuring that every feedback history remains realizable. A previous NeurIPS 2024 work established an O(k)O(k) upper bound on the ratio between the optimal adaptive and oblivious mistake bounds and showed that an Ω(k)\Omega(k) separation is achievable for pattern classes. Whether a comparable separation exists for genuine concept classes remained open.

The authors establish that a strict separation is possible for genuine concept classes. They first construct a four-function class on two instances, with adaptive and oblivious values 35/2935/29 and 7/67/6, respectively, and prove that four functions are necessary for any separation. They then introduce a multi-shield tower family and establish that its adaptive-to-oblivious ratio converges to 5/45/4. Finally, they develop upper bounds on the amplification of adaptivity gaps under several class-composition schemes and derive necessary conditions for achieving a linear-in-kk separation. Thus, the paper resolves the existence question but leaves open whether genuine concept classes can achieve a superconstant gap, let alone match the Ω(k)\Omega(k) separation known for pattern classes.

Critical strengths
  • Establishing that adaptivity can strictly increase the optimal mistake bound even for genuine concept classes is a meaningful theoretical contribution. The distinction between pattern classes and fixed concept classes makes the result more than a straightforward transfer of existing constructions.

  • The paper provides exact finite-class separations, a closed-form recursion for the adaptive values of the tower family, asymptotic bounds for both adversary models, and explicit certificates for the finite computations. The combination of analytical arguments and independently checkable computational certificates is a strength.

  • The localization and capping results explain why several natural attempts to amplify small adaptivity gaps fail. The necessary conditions for linear separation also help characterize what a successful construction would need to achieve.

Critical weaknesses
  • The central quantitative question remains unresolved. The tower construction achieves only a constant asymptotic ratio of 5/45/4, rather than the conjectured Ω(k)\Omega(k) separation. Consequently, although the existence component of the open problem is resolved, the paper makes limited progress toward determining the actual price of adaptivity as a function of the number of labels. The authors appropriately acknowledge this limitation, but it substantially constrains the significance of the main result.

  • The paper resolves a specific existence question and rules out several natural amplification strategies, but neither establishes a superconstant separation nor provides an impossibility result that rules one out. Whether these advances alone constitute a sufficiently substantial contribution for ICLR is therefore debatable.

  • The paper introduces numerous constructions, auxiliary bounds, exact finite certificates, and technical frameworks across its main sections and appendices. Although many of these results are individually interesting, their relationship to the central question is not always sufficiently clear. A more focused narrative distinguishing the essential results from secondary technical contributions would improve readability and make the paper's overall significance easier to assess.

Questions for authors
  1. What is the strongest evidence that the techniques developed here can lead to a superconstant separation for genuine concept classes? In particular, can the localization and capping results be used to identify a plausible construction beyond the multi-shield tower family, or do they primarily rule out existing natural approaches?

  2. The asymptotic separation achieved by the tower family is 5/45/4, while a finite instance has a certified ratio exceeding 1.26171.2617. Is there evidence that a different family of genuine concept classes can achieve a superconstant ratio, or are there structural reasons to expect a constant-factor separation?

  3. Could the authors clarify which of the auxiliary composition and localization results are essential to resolving the existence question, and which are independent contributions? This would help readers better assess the paper's central novelty and broader implications.

4 comments
AuthorsOpenReview ↗

Response (1/4): W1 and W2, the open problem is closed

We sincerely thank the reviewer for the thoughtful review and for the questions on where the techniques could lead. We are particularly grateful for W1 and W2, which pointed out that our submission had settled only the existence part of the open problem of Filmus et al., and not how the price grows with the number of labels. We have now resolved this problem.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

The revised version completely resolves the open problem of Filmus et al. (NeurIPS 2024): in its default weakly realizable model, the worst-case price of adaptivity for concept classes is Θ(log⁡k)\Theta(\log k), where kk is the number of labels.

The open problem reads in full (Filmus et al., Section 4.1): "The price of adaptivity for concept classes. Our proof of Theorem E.1 uses pattern classes. Can we prove it using only concept classes, similarly to Theorem F.1? If not, what is the price of adaptivity when learning concept classes?" The revised version answers both questions with two new results. Section 3 shows that for every concept class, finite or infinite, the optimal adaptive mistake bound A(H)A(H) is at most (1+o(1))ln⁡k(1+o(1))\ln k times the optimal oblivious bound B(H)B(H), so the Ω(k)\Omega(k) separation of their Theorem E.1 cannot be achieved with concept classes. Sections 4 and 5 construct explicit finite concept classes with ratio (2/3−o(1))ln⁡k(2/3-o(1))\ln k; for instance, ratios at least 2, 3 and 4 are reached with 6364, 71922 and 628217 labels (p. 9 and Appendix E.6). Hence the price for concept classes is Θ(log⁡k)\Theta(\log k) (Theorem 2.1). As with the linear price for pattern classes, the price is thus determined up to constant factors. The exact constant in front of ln⁡k\ln k, between 2/32/3 and 11, remains open; it lies outside their question and is a natural direction for future work.

The table below sums up, for the three questions behind W1 and W2, where the submitted version stood and what the revised version proves.

Submitted versionRevised version
Gap growing with kk?Open (ratios 30/29 and 5/4)Yes: (2/3−o(1))ln⁡k(2/3-o(1))\ln k (Theorem 5.1)
Linear gap possible?OpenNo: at most (1+o(1))ln⁡k(1+o(1))\ln k (Theorem B.1)
Order of the priceOpenΘ(log⁡k)\Theta(\log k) (Theorem 2.1): resolved

The revised version keeps all theorems, propositions and examples of the submitted version, together with their proofs, techniques and certificates. In particular, the tower family with limit 5/45/4 is kept as a structured example (Section 6, Theorem I.6). In addition, the two new results resolve the question the submitted version left open (its Open Problem 6.1): how the price grows with kk. Together with what the submitted version established, that concept classes can separate at all, with exact minimal examples, they completely resolve the open problem of Filmus et al.

AuthorsOpenReview ↗

Response (2/4): W1 and W2, how the open problem is solved

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

How the upper and lower bounds are obtained. In a concept class, every function is fixed in advance on the whole domain. An adaptive adversary may still decide, as the game unfolds, which function it is following, but every label it declares correct must be supported by some function consistent with all feedback so far. Both bounds rest on the same harmonic-sum mechanism, used once by the learner and once by the adversary; this is why the answer is logarithmic.

Upper bound: adaptivity costs at most a factor of about ln⁡k\ln k.

  1. Measuring what remains to be learned. An oblivious adversary can force two kinds of cost: searching for the correct label among the feasible ones, and resolving binary splits of the class (does the target take label aa at instance xx?). We combine both into one potential, which never exceeds (1+o(1))B(H)(1+o(1))B(H).
  2. Paying for each mistake. In every round, the learner chooses its prediction distribution so that, whichever feasible label the adversary then declares correct, the expected mistake is at most (1+o(1))ln⁡k(1+o(1))\ln k times the expected drop of the potential (inequality (9)). Summing over the rounds, the total expected number of mistakes is at most (1+o(1))ln⁡k(1+o(1))\ln k times the initial potential, which gives A(H)≤(1+o(1))ln⁡k⋅B(H)A(H) \le (1+o(1))\ln k \cdot B(H).
  3. Where ln⁡k\ln k comes from. A label whose correct guess lowers the potential a lot needs only a small probability, roughly inversely proportional to that drop. The search cost keeps too many labels from having small drops. Leaving out the smallest drop, the jj smallest of the others add up to at least about j2/2j^2/2, much as an oblivious search reaches the jjth label only after about jj mistakes. A label that makes little progress when guessed correctly makes substantial progress when guessed wrongly, and the proof uses this as well. Comparing the drops with the sequence 12,32,…\frac12,\frac32,\dots then gives the factor Q(k)=∑j=1k−11j−1/2=ln⁡k+O(1)Q(k)=\sum_{j=1}^{k-1}\frac{1}{j-1/2}=\ln k+O(1) in the cost.

Lower bound: a factor of order ln⁡k\ln k cannot be avoided.

  1. The construction. We build one finite class from blocks of functions, called worlds. All worlds share a set of top instances, where a correct prediction identifies the world, and each world then continues on its own tail class. On the top instances, heavy worlds take all binary patterns of two private labels, and light worlds take one constant label.
  2. Keeping every fixed target cheap. Against a fixed target, a learner first searches for the target's world, trying heavy labels for a bounded number of rounds and then the light worlds in a fixed order, and then learns its tail. Light worlds that come later in this order receive tails that are cheaper by exactly the extra search cost, and a heavy target is found before the light scan except with small probability. So every fixed target costs at most the same budget, which bounds BB.
  3. Keeping many targets alive. An adaptive adversary need not commit to a target. While it forces mistakes among the heavy worlds, it keeps many light worlds feasible.
  4. Why the learner cannot protect all of them. During the search on the top instances, suppose that every feasible label led to an adaptive cost below the bound the construction maintains at that stage. Then each light label would claim a share of the learner's probability, roughly of order 1/(ρj)1/(\rho j), where ρ\rho is the target ratio and jj is the number of mistakes an oblivious search makes before reaching that label. With enough light labels these shares add up to more than one, so they cannot all be met: some feasible label still forces the bound, and the adversary declares it. Once the search phase is over, a surviving heavy world's tail carries the bound.
  5. From the mechanism to the constant 2/32/3. Summing 1/(ρj)1/(\rho j) over the light labels gives about 1ρln⁡(jlast/jfirst)\frac1\rho\ln(j_{\mathrm{last}}/j_{\mathrm{first}}), so keeping enough light worlds multiplies the number of labels by about eρe^{\rho}. In our parameter choice, the heavy part contributes a further factor of about eρ/2e^{\rho/2}, since it uses about that many worlds to supply the adaptive gain. Hence about e3ρ/2e^{3\rho/2} labels suffice, up to factors polynomial in ρ\rho (Theorem 5.1), and nesting the construction on the same labels attains ratio ρ\rho; inverting gives (2/3−o(1))ln⁡k(2/3-o(1))\ln k.
AuthorsOpenReview ↗

Response (3/4): W3, a reading guide and correspondence with the submitted version

Thank you very much for the comment on the focus of the paper (W3). The suggestion was very helpful to us, and following it we have organized the presentation around the main theorem. In line with this suggestion, we polished the writing with great care. The changes and a short reading guide are given below, and we would welcome any further suggestions.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

W3. The paper is now organized around Theorem 2.1: Sections 2–5 prove it, and Section 6 explains in half a page what the earlier constructions show and why simple compositions cannot amplify a gap by more than an additive constant. Appendix A states that the proof of Theorem 2.1 uses only Appendices B–F, and its dependency graph (Figure 1) shows the main steps of that proof. The results of the submitted version are kept in Appendices G–K as independent contributions.

To make a second reading easier, here is how the revised version unfolds.

Sections 1 and 2 (pp. 1–3) set out the question, the definitions with a small example, and the answer (Theorem 2.1), and explain why both bounds are logarithmic. Section 3 proves the upper bound; Section 4 constructs the class with different continuation budgets, and Section 5 amplifies its ratio on one alphabet. The example on p. 9 (6364 labels, ratio at least 2) is perhaps the quickest way to see the construction at work, and Corollary 5.2 gives bounds for every kk. Section 6 places the results of the submitted version in this picture, and Section 7 discusses the model and open questions. Appendix A is the proof guide; Appendices B–F prove Theorem 2.1, G–K contain the results of the submitted version, L the certificates and scripts, and M related work.

Correspondence with the submitted version. To make it easy to compare the two versions, the items discussed in this review appear in the revised version as follows; the necessary conditions are now stated in terms of the attained ratio.

Submitted versionRevised version
Section 3, Theorem 3.1, Proposition 3.2 (four-function example)Section 6; Theorem H.1, Proposition H.2
Appendix B.1 (full proof)Appendix H.1
Theorem B.1, Remark B.2 (five-function example)Theorem H.3, Remark H.4
Section 4, Theorems 4.1–4.4 (tower family)Section 6; Theorems I.1, I.4, I.5, I.6
Section 4.2, Appendices C–D (recursion, asymptotics)Appendices I.1, I.3–I.5
Section 5.1, Lemma 5.1, Theorems 5.2–5.5 (capping)Lemma J.1, Theorems J.2–J.5
Remark 5.6; Theorem 5.7Remark J.6; Theorem J.7
Section 5.2, Theorem 5.8 (necessary conditions)Appendix J.4, Theorem J.9
Remark E.1Remark J.8
Appendix F (further families, comparison tools)Appendices I.2, K.1, K.2
Appendix G (verification)Appendix L
Open Problem 6.1 (a), (b)Answered by Theorem 2.1

The general comment contains the full table.

AuthorsOpenReview ↗

Response (4/4): Q1, Q2 and Q3

We thank the reviewer for the three thoughtful questions.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

Q1 (evidence that the techniques lead to a superconstant separation). A superconstant separation is now proved rather than conjectured (Theorem 5.1). The localization and capping results do not produce a construction by themselves; they act as constraints that any successful construction must satisfy. Nesting classes of ratio at most C0C_0 on disjoint label blocks keeps the ratio at most C0+2C_0+2 at every finite depth, because one correct prediction identifies the block (Theorem J.2). A large ratio also forces a large local alphabet, a large full-information value and, for suitable covers, a large localization rank (Theorem J.9). The construction of Sections 4–5 meets these constraints: its worlds share one label alphabet, so the block bound does not apply, and their tails receive unequal continuation budgets that pay for the oblivious learner's search, while the adaptive adversary keeps many worlds alive.

Q2 (a different family, or structural reasons for a constant). A different family does reach a superconstant ratio: the composite classes of Section 4, iterated on one alphabet in Section 5, have ratio at least (2/3−o(1))ln⁡k(2/3-o(1))\ln k. So there is no structural reason for a constant bound in general. The towers and their finite nested generalizations stay bounded for a structural reason of their own: their parts use private label blocks, so one correct prediction localizes the relevant part, which caps the ratio at every finite depth (Theorem J.2 bounds the towers by 3; the exact limit 5/45/4 comes from Appendix I). The construction of Sections 4–5 is not of this form, since its tails reuse one label alphabet; its growth then comes from the unequal continuation budgets and the recursion of Section 5.

Q3 (which auxiliary results are essential). None of the composition and localization results of the submitted version (now Appendix J) is needed for the main theorem: Theorem 2.1 uses only Appendices B–F (Appendix A, Figure 1). For the existence question alone, the four-function witness (Theorem H.1) suffices. The composition and localization bounds of Appendix J are independent contributions that explain why simpler amplification strategies cannot produce growth.

Thank you again for the careful review and the questions about where this line of work leads. We hope the revised version answers them, and we would be glad to clarify anything further.

Reviewer_YVn9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper partially solved an open problem proposed by Filmus et al. (NeurIPS 2024) about the price of adversarial adaptivity in online multiclass classification with bandit feedback. The authors construct a concept class with a strict gap between the optimal expected mistake bounds against adaptive and oblivious adversaries, and prove that 4 functions are necessary. They further analyze a family of multi-shield towers and establish an asymptotic adaptivity ratio of 5/4. The paper also derives upper bounds for compositions of concept classes and necessary conditions for a linear adaptivity gap.

Critical strengths
  1. The paper resolves the existence component of an open problem posed by Filmus et al. (NeurIPS 2024). It proves that adaptive adversaries can cause strictly more expected mistakes than oblivious adversaries for genuine concept classes.
  2. The paper establishes that four functions are sufficient and necessary for a strict separation. This provides a precise characterization of the smallest possible example.
  3. The theoretical analysis is technically nontrivial. The authors establish an exact recursion for the adaptive value and derive matching asymptotic bounds.
Critical weaknesses
  1. The paper only partially resolves the main open problem. Although it establishes a strict separation, the demonstrated gaps remain constant factors. Whether a gap that grows with kk is possible for concept classes remains open.
  2. The presentation is overly dense and difficult to follow. For example, the Introduction directly lists numerous technical results and bounds without sufficient background or explanation. It also uses many notations (e.g., opt⁡banditadap\operatorname{opt}^{\mathrm{adap}}_{\mathrm{bandit}}, opt⁡banditobl\operatorname{opt}^{\mathrm{obl}}_{\mathrm{bandit}}, AA, BB, DD, FF, YY, D2D_2, D3D_3, D4D_4, DmD_m, CaC_a, etc.) without defining them. Similar issues occur throughout the paper. Readers are required to be familiar with Filmus et al., 2024, and have to repeatedly go back and forth between different sections and appendices to find the definitions needed to understand the results. Many technical results are presented without sufficient intuition. Overall, the presentation quality is far below the standards of ICLR.
  3. The writing contains noticeable signs of AI-generated text, such as substantial repetition, unnecessary explanations, and unnatural expressions. Although the authors disclose the use of generative AI in drafting the manuscript, the writing still needs substantial improvement.
Questions for authors
  1. The paper mentions recommendation and reasoning systems as potential applications. Could the authors explain how these applications fit the specific adaptive adversary model considered in the theoretical analysis?
  2. What are the main new technical contributions of Theorems 4.1-4.4 beyond existing Bellman recursion and minimax techniques?
4 comments
AuthorsOpenReview ↗

Response (1/4): W1, the open problem is now closed

We sincerely thank the reviewer for the careful reading and the detailed, constructive comments. We are particularly grateful for W1, which pointed out that our submission had not fully resolved the open problem of Filmus et al. We have now closed this problem.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

The revised version completely resolves the open problem of Filmus et al. (NeurIPS 2024): in its default weakly realizable model, the worst-case price of adaptivity for concept classes is Θ(log⁡k)\Theta(\log k), where kk is the number of labels.

The open problem reads in full (Filmus et al., Section 4.1): "The price of adaptivity for concept classes. Our proof of Theorem E.1 uses pattern classes. Can we prove it using only concept classes, similarly to Theorem F.1? If not, what is the price of adaptivity when learning concept classes?" The revised version answers both questions with two new results. Section 3 shows that for every concept class, finite or infinite, the optimal adaptive mistake bound A(H)A(H) is at most (1+o(1))ln⁡k(1+o(1))\ln k times the optimal oblivious bound B(H)B(H), so the Ω(k)\Omega(k) separation of their Theorem E.1 cannot be achieved with concept classes. Sections 4 and 5 construct explicit finite concept classes with ratio (2/3−o(1))ln⁡k(2/3-o(1))\ln k; for instance, ratios at least 2, 3 and 4 are reached with 6364, 71922 and 628217 labels (p. 9 and Appendix E.6). Hence the price for concept classes is Θ(log⁡k)\Theta(\log k) (Theorem 2.1). As with the linear price for pattern classes, the price is thus determined up to constant factors. The exact constant in front of ln⁡k\ln k, between 2/32/3 and 11, remains open; it lies outside their question and is a natural direction for future work.

The table below sums up, for the three questions behind W1, where the submitted version stood and what the revised version proves.

Submitted versionRevised version
Gap growing with kk?Open (ratios 30/29 and 5/4)Yes: (2/3−o(1))ln⁡k(2/3-o(1))\ln k (Theorem 5.1)
Linear gap possible?OpenNo: at most (1+o(1))ln⁡k(1+o(1))\ln k (Theorem B.1)
Order of the priceOpenΘ(log⁡k)\Theta(\log k) (Theorem 2.1): resolved

The revised version keeps all theorems, propositions and examples of the submitted version, together with their proofs, techniques and certificates. In addition, the two new results resolve the question the submitted version left open (its Open Problem 6.1): how the price grows with kk. Together with what the submitted version established, that concept classes can separate at all, with exact minimal examples, they completely resolve the open problem of Filmus et al.

AuthorsOpenReview ↗

Response (2/4): W1, how the open problem is solved

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

How the upper and lower bounds are obtained. In a concept class, every function is fixed in advance on the whole domain. An adaptive adversary may still decide, as the game unfolds, which function it is following, but every label it declares correct must be supported by some function consistent with all feedback so far. Both bounds rest on the same harmonic-sum mechanism, used once by the learner and once by the adversary; this is why the answer is logarithmic.

Upper bound: adaptivity costs at most a factor of about ln⁡k\ln k.

  1. Measuring what remains to be learned. An oblivious adversary can force two kinds of cost: searching for the correct label among the feasible ones, and resolving binary splits of the class (does the target take label aa at instance xx?). We combine both into one potential, which never exceeds (1+o(1))B(H)(1+o(1))B(H).
  2. Paying for each mistake. In every round, the learner chooses its prediction distribution so that, whichever feasible label the adversary then declares correct, the expected mistake is at most (1+o(1))ln⁡k(1+o(1))\ln k times the expected drop of the potential (inequality (9)). Summing over the rounds, the total expected number of mistakes is at most (1+o(1))ln⁡k(1+o(1))\ln k times the initial potential, which gives A(H)≤(1+o(1))ln⁡k⋅B(H)A(H) \le (1+o(1))\ln k \cdot B(H).
  3. Where ln⁡k\ln k comes from. A label whose correct guess lowers the potential a lot needs only a small probability, roughly inversely proportional to that drop. The search cost keeps too many labels from having small drops. Leaving out the smallest drop, the jj smallest of the others add up to at least about j2/2j^2/2, much as an oblivious search reaches the jjth label only after about jj mistakes. A label that makes little progress when guessed correctly makes substantial progress when guessed wrongly, and the proof uses this as well. Comparing the drops with the sequence 12,32,…\frac12,\frac32,\dots then gives the factor Q(k)=∑j=1k−11j−1/2=ln⁡k+O(1)Q(k)=\sum_{j=1}^{k-1}\frac{1}{j-1/2}=\ln k+O(1) in the cost.

Lower bound: a factor of order ln⁡k\ln k cannot be avoided.

  1. The construction. We build one finite class from blocks of functions, called worlds. All worlds share a set of top instances, where a correct prediction identifies the world, and each world then continues on its own tail class. On the top instances, heavy worlds take all binary patterns of two private labels, and light worlds take one constant label.
  2. Keeping every fixed target cheap. Against a fixed target, a learner first searches for the target's world, trying heavy labels for a bounded number of rounds and then the light worlds in a fixed order, and then learns its tail. Light worlds that come later in this order receive tails that are cheaper by exactly the extra search cost, and a heavy target is found before the light scan except with small probability. So every fixed target costs at most the same budget, which bounds BB.
  3. Keeping many targets alive. An adaptive adversary need not commit to a target. While it forces mistakes among the heavy worlds, it keeps many light worlds feasible.
  4. Why the learner cannot protect all of them. During the search on the top instances, suppose that every feasible label led to an adaptive cost below the bound the construction maintains at that stage. Then each light label would claim a share of the learner's probability, roughly of order 1/(ρj)1/(\rho j), where ρ\rho is the target ratio and jj is the number of mistakes an oblivious search makes before reaching that label. With enough light labels these shares add up to more than one, so they cannot all be met: some feasible label still forces the bound, and the adversary declares it. Once the search phase is over, a surviving heavy world's tail carries the bound.
  5. From the mechanism to the constant 2/32/3. Summing 1/(ρj)1/(\rho j) over the light labels gives about 1ρln⁡(jlast/jfirst)\frac1\rho\ln(j_{\mathrm{last}}/j_{\mathrm{first}}), so keeping enough light worlds multiplies the number of labels by about eρe^{\rho}. In our parameter choice, the heavy part contributes a further factor of about eρ/2e^{\rho/2}, since it uses about that many worlds to supply the adaptive gain. Hence about e3ρ/2e^{3\rho/2} labels suffice, up to factors polynomial in ρ\rho (Theorem 5.1), and nesting the construction on the same labels attains ratio ρ\rho; inverting gives (2/3−o(1))ln⁡k(2/3-o(1))\ln k.
AuthorsOpenReview ↗

Response (3/4): W2 and W3, a reading guide and correspondence with the submitted version

Thank you very much for the comments on the writing (W2, W3). The suggestions were very helpful to us, and following them we have carefully revised the presentation of the paper. The changes and a short reading guide are given below, and we would welcome any further suggestions.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

W2 (presentation). The introduction now explains the problem, the global consistency constraint behind it and the answer before any technical statement, and it explains why both bounds are logarithmic (p. 2). Section 2 defines the protocol, version spaces, the consistency condition, the two optimal values and the price from scratch, with a small example, so the main text can be read without Filmus et al. Notation in the main text is introduced where it is first needed, and Appendix A explains how the two game values and the recursion value used in the lower bound are related. In each technical section the key steps are explained in words before the details: the information-leakage paragraph and the one-step inequality in Section 3, the minimax meaning of the reserve condition in Section 4, and the budget accounting in Section 5, followed by a fully explicit numerical example. Appendix A also gives a proof guide with a dependency graph, so a reader can see which results each step uses without searching through the appendices.

W3 (writing style). Repetitions and unnecessary explanations were removed, sentences were shortened, and each section is now organized around the step it proves. We hope the text now reads more naturally, and we would be grateful to hear about any passage that still does not.

We have simplified the notation as far as we could; since the paper is long and technical, some passages remain dense, and we are grateful for the reviewer’s patience with these denser passages. We would be very grateful if the reviewer could take another look at the revised version, and we will gladly answer any question at any time during the discussion. To make a second reading easier, here is how the revised version unfolds.

Sections 1 and 2 (pp. 1–3) set out the question, the definitions with a small example, and the answer (Theorem 2.1), and explain why both bounds are logarithmic. Section 3 proves the upper bound; Section 4 constructs the class with different continuation budgets, and Section 5 amplifies its ratio on one alphabet. The example on p. 9 (6364 labels, ratio at least 2) is perhaps the quickest way to see the construction at work, and Corollary 5.2 gives bounds for every kk. Section 6 places the results of the submitted version in this picture, and Section 7 discusses the model and open questions. Appendix A is the proof guide; Appendices B–F prove Theorem 2.1, G–K contain the results of the submitted version, L the certificates and scripts, and M related work.

Correspondence with the submitted version. To make it easy to compare the two versions, the items discussed in this review appear in the revised version as follows; the necessary conditions are now stated in terms of the attained ratio.

Submitted versionRevised version
Section 3, Theorem 3.1, Proposition 3.2 (four-function example)Section 6; Theorem H.1, Proposition H.2
Appendix B.1 (full proof)Appendix H.1
Theorem B.1, Remark B.2 (five-function example)Theorem H.3, Remark H.4
Section 4, Theorems 4.1–4.4 (tower family)Section 6; Theorems I.1, I.4, I.5, I.6
Section 4.2, Appendices C–D (recursion, asymptotics)Appendices I.1, I.3–I.5
Section 5.1, Lemma 5.1, Theorems 5.2–5.5 (capping)Lemma J.1, Theorems J.2–J.5
Remark 5.6; Theorem 5.7Remark J.6; Theorem J.7
Section 5.2, Theorem 5.8 (necessary conditions)Appendix J.4, Theorem J.9
Remark E.1Remark J.8
Appendix F (further families, comparison tools)Appendices I.2, K.1, K.2
Appendix G (verification)Appendix L
Open Problem 6.1 (a), (b)Answered by Theorem 2.1

The general comment contains the full table.

AuthorsOpenReview ↗

Response (4/4): Q1 and Q2

We thank the reviewer for the two thoughtful questions.

Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.

Q1 (applications and the adaptive model). The applications supply the feedback model, and the adaptive adversary is the worst-case form of an environment that responds to the learner. In recommendation, an instance is the current context, the labels are the candidate items, and the feedback bit says whether the selected item is the accepted one. In answer verification for reasoning systems, an instance is a question, the labels are candidate answers, and the bit is the verifier's acceptance decision. Adaptivity means that the acceptance rule may respond to the selection probabilities the learner announces, before the current choice is sampled; condition (1) requires every label that the environment may accept to be supported by some function in the class that is consistent with all feedback so far (Section 2). The model does not assert that deployed recommenders or verifiers behave in this way; it measures how much such responsiveness can cost in the worst case. Section 7 states this connection and its limits: a finite candidate set, one correct label and realizable feedback. Within that idealization, Theorem 2.1 shows that responsiveness can raise the optimal expected number of mistakes by at most a factor of order ln⁡k\ln k for kk candidates, and Theorem 5.1 shows that this order can occur.

Q2 (Theorems 4.1–4.4 of the submitted version). Beyond the Bellman recursion, three steps are specific to the tower family (now Theorems I.1, I.4, I.5 and I.6), and each needs its own argument.

  • Diagnostic invariance: every reachable state, including states created by repeated queries at constrained coordinates, has the value of a state described by two numbers (unknown binary coordinates and surviving shields). A coordinate whose binary value is already known stays informative while shields survive, so this reduction does not follow from the recursion alone; it yields a closed two-parameter recursion (Theorem I.1).
  • Adaptive asymptotics: exchange arguments along the all-negative path (the history in which every prediction is wrong) give the lower bound 5r/85r/8, and a shifted quadratic potential gives the upper bound 5r/8+6r−35r/8+\sqrt{6r-3}. The leading constant 5/85/8 is fixed by these two matching arguments, not by the recursion itself.
  • Oblivious asymptotics: a ranking argument for the first shield probes, together with a threshold learner, gives B(Hr)=r/2+log⁡2r−log⁡2log⁡2r+O(1)B(H_r)=r/2+\log_2 r-\log_2\log_2 r+O(1).

The limit ratio 5/4=(5/8)/(1/2)5/4=(5/8)/(1/2) of Theorem I.6 then follows by combining the two asymptotic results, which is why four theorems correspond to three steps.

The techniques added in the revised version are in Sections 3–5: the two oblivious certificates, the second proved with an information-conservation identity (Lemma B.7); the harmonic comparison that turns them into one adaptive learner; and the composite class with unequal continuation budgets on a fixed alphabet.

Thank you again for the time and care spent on our paper. We hope the revised version answers the concerns raised, and we would be glad to clarify anything further.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Summary of the revision (3/3): continuity with the submitted version and reading guide

Continuity with the submitted version. The problem, the protocol and the two optimal values are unchanged, and all theorems, propositions and examples of the submitted version are kept in the revised version of paper, together with their proofs, techniques and certificates. The new lower-bound class uses the same two kinds of blocks as the tower family (binary blocks and constant shields, Table 1), and the localization results explain its design: nesting classes of ratio at most C0C_0 on disjoint label blocks keeps the ratio at most C0+2C_0+2 (Theorem J.2), and the new class escapes this bound by letting all worlds share one label alphabet.

We thank the reviewers again for pointing out where our writing fell short; it could indeed have been better. Following their comments, we have carefully polished the presentation to make the paper easier to read. The revised version now unfolds as follows.

Sections 1 and 2 (pp. 1–3) set out the question, the definitions with a small example, and the answer (Theorem 2.1), and explain why both bounds are logarithmic. Section 3 proves the upper bound; Section 4 constructs the class with different continuation budgets, and Section 5 amplifies its ratio on one alphabet. The example on p. 9 (6364 labels, ratio at least 2) is perhaps the quickest way to see the construction at work, and Corollary 5.2 gives bounds for every kk. Section 6 places the results of the submitted version in this picture, and Section 7 discusses the model and open questions. Appendix A is a proof guide with a dependency graph; Appendices B–F prove Theorem 2.1, G–K contain the results of the submitted version, L the certificates and scripts, and M related work.

To make it easy to compare the two versions, we give the following correspondence of structure and content between the submitted version and the revised version.

Submitted versionRevised version
Title: "The Price of Adaptivity in Bandit Multiclass Classification: Minimal Separation and Sharp Tower Asymptotics""The Price of Adaptivity in Bandit Multiclass Classification Is Logarithmic" (first part unchanged)
AbstractLeads with the main result (Theorem 2.1) and still describes the four-function witness, the 5/4 tower asymptotics and the composition bounds
Section 3: four-function example, Theorem 3.1, Proposition 3.2Section 6, first paragraph; Theorem H.1, Proposition H.2
Appendix B.1: full proof for the four-function classAppendix H.1
Theorem B.1 and Remark B.2: five-function exampleTheorem H.3 and Remark H.4
Section 4: tower family, Theorems 4.1, 4.2, 4.3, 4.4Section 6, second paragraph; Theorems I.1, I.4, I.5, I.6
Section 4.2 and Appendix D: asymptotics and doubling ratiosAppendices I.3–I.5 (ratios at the end of I.3.2)
Appendix C: exact recursionAppendix I.1
Appendix F.1: single-shield familyTheorem I.2 and Proposition I.3
Section 5.1: Lemma 5.1, Theorems 5.2–5.5Lemma J.1, Theorems J.2–J.5
Remark 5.6Remark J.6
Theorem 5.7: Hamming-ball classesTheorem J.7
Section 5.2, Theorem 5.8: necessary conditionsAppendix J.4, Theorem J.9 (stated in terms of the attained ratio)
Remark E.1: the rank bound is not tightRemark J.8
Appendices F.2–F.3, Proposition F.3: thirteen-function classAppendix K.1, Proposition K.1
Appendix F.4: comparison toolsAppendix K.2
Lemma 2.3 and Remark 2.2Lemma G.2 and Remark G.1 (the comment on almost-sure consistency is omitted)
Appendix A.1: related workAppendix M (short version in Section 1)
Appendix G: verification; Remark G.1 (note on Lemma C.11 of Filmus et al.)Appendix L; Remark L.1
Open Problem 6.1 (a), (b): superconstant ratio? linear ratio?Answered by Theorem 2.1
(not in the submitted version)Section 3 and Appendix B: upper bound for every concept class; Sections 4–5 and Appendices C–E: lower-bound classes on one alphabet; Appendix F: bounds for every kk
Supplementary code: supplementary/ with three scriptssupplementary/ with the same three scripts, updated, and two further scripts; verification/ (added) with five scripts for the parameters of Section 5, the constant centc_{\mathrm{ent}} and Corollary 5.2

The first part of the title is unchanged; we would gladly restore the original title if the area chair prefers.

We thank the reviewers and the area chair again for their time, and we would be glad to answer any question during the discussion.

AuthorsOpenReview ↗

Summary of the revision (2/3): how the open problem is closed

To close the open problem of Filmus et al., the revised version introduces two results:

  1. Upper bound. Every concept class HH, finite or infinite, satisfies A(H)≤(1+o(1))ln⁡k⋅B(H)A(H) \le (1+o(1))\ln k \cdot B(H) (Section 3, Theorem B.1).
  2. Lower bound. Explicit finite concept classes reach ratio (2/3−o(1))ln⁡k(2/3-o(1))\ln k (Sections 4–5, Theorem 5.1), with explicit bounds for every kk (Corollary 5.2).

Together they show that the worst-case price is Θ(log⁡k)\Theta(\log k) (Theorem 2.1).

How these results are obtained. In a concept class, every function is fixed in advance on the whole domain. An adaptive adversary may still decide, as the game unfolds, which function it is following, but every label it declares correct must be supported by some function consistent with all feedback so far. Both bounds rest on the same harmonic-sum mechanism, used once by the learner and once by the adversary; this is why the answer is logarithmic.

Upper bound: adaptivity costs at most a factor of about ln⁡k\ln k.

  1. Measuring what remains to be learned. An oblivious adversary can force two kinds of cost: searching for the correct label among the feasible ones, and resolving binary splits of the class (does the target take label aa at instance xx?). We combine both into one potential, which never exceeds (1+o(1))B(H)(1+o(1))B(H).
  2. Paying for each mistake. In every round, the learner chooses its prediction distribution so that, whichever feasible label the adversary then declares correct, the expected mistake is at most (1+o(1))ln⁡k(1+o(1))\ln k times the expected drop of the potential (inequality (9)). Summing over the rounds, the total expected number of mistakes is at most (1+o(1))ln⁡k(1+o(1))\ln k times the initial potential, which gives A(H)≤(1+o(1))ln⁡k⋅B(H)A(H) \le (1+o(1))\ln k \cdot B(H).
  3. Where ln⁡k\ln k comes from. A label whose correct guess lowers the potential a lot needs only a small probability, roughly inversely proportional to that drop. The search cost keeps too many labels from having small drops: leaving out the smallest drop, the jj smallest of the others add up to at least about j2/2j^2/2, as if an oblivious search reached the jjth label only after about jj mistakes. The proof combines this constraint with the drop after a wrong guess, which is substantial whenever a correct guess makes little progress, and compares the drops with the sequence 12,32,…\frac12,\frac32,\dots; this is where the factor Q(k)=∑j=1k−11j−1/2=ln⁡k+O(1)Q(k)=\sum_{j=1}^{k-1}\frac{1}{j-1/2}=\ln k+O(1) in the cost comes from.

Lower bound: a factor of order ln⁡k\ln k cannot be avoided.

  1. Keeping every fixed target cheap. We build one finite class from blocks of functions, called worlds. All worlds share a set of top instances, where a correct prediction identifies the world, and each world then continues on its own tail class. On the top instances, heavy worlds take all binary patterns of two private labels, and light worlds take one constant label. Against a fixed target, a learner first searches for the target's world, trying heavy labels for a bounded number of rounds and then the light worlds in a fixed order, and then learns its tail. Light worlds that come later in this order receive tails that are cheaper by exactly the extra search cost, and a heavy target is found before the light scan except with small probability. So every fixed target costs at most the same budget, which bounds BB.
  2. Keeping many targets alive. An adaptive adversary need not commit to a target. While it forces mistakes among the heavy worlds, it keeps many light worlds feasible.
  3. Why the learner cannot protect all of them. During the search on the top instances, suppose that every feasible label led to an adaptive cost below the target, ρ\rho times the budget. Then each light label would claim a share of the learner's probability of order 1/(ρj)1/(\rho j), where jj is the number of mistakes an oblivious search makes before reaching it. With enough light labels these shares add up to more than one, so they cannot all be met: some feasible label still forces the target cost, and the adversary declares it. Once the search phase is over, a surviving heavy world's tail carries the bound. This is the same harmonic-sum mechanism, now working for the adversary.
  4. From the mechanism to the constant 2/32/3. Summing 1/(ρj)1/(\rho j) over the light labels gives about 1ρln⁡(jlast/jfirst)\frac1\rho\ln(j_{\mathrm{last}}/j_{\mathrm{first}}), so keeping enough light worlds multiplies the number of labels by about eρe^{\rho}. In our parameter choice, the heavy part contributes a further factor of about eρ/2e^{\rho/2}, since it uses about that many worlds to supply the adaptive gain. Hence about e3ρ/2e^{3\rho/2} labels suffice, up to factors polynomial in ρ\rho (Theorem 5.1), and nesting the construction on the same labels attains ratio ρ\rho; inverting gives (2/3−o(1))ln⁡k(2/3-o(1))\ln k.
AuthorsOpenReview ↗

Summary of the revision (1/3):the open problem is now solved

We sincerely thank all reviewers and the area chair for their time and careful reading, and in particular for two comments: that the open problem had not been fully resolved, and that the writing should be improved. In response, we have uploaded a revised version.

The revised version completely resolves the open problem of Filmus et al. (NeurIPS 2024): in its default weakly realizable model, the worst-case price of adaptivity for concept classes is Θ(log⁡k)\Theta(\log k), where kk is the number of labels.

The open problem reads in full (Filmus et al., Section 4.1): "The price of adaptivity for concept classes. Our proof of Theorem E.1 uses pattern classes. Can we prove it using only concept classes, similarly to Theorem F.1? If not, what is the price of adaptivity when learning concept classes?" The revised version answers both questions with two new results. Section 3 shows that for every concept class, finite or infinite, the optimal adaptive mistake bound A(H)A(H) is at most (1+o(1))ln⁡k(1+o(1))\ln k times the optimal oblivious bound B(H)B(H), so the Ω(k)\Omega(k) separation of their Theorem E.1 cannot be achieved with concept classes. Sections 4 and 5 construct explicit finite concept classes with ratio (2/3−o(1))ln⁡k(2/3-o(1))\ln k. Hence the price for concept classes is Θ(log⁡k)\Theta(\log k) (Theorem 2.1). The exact constant in front of ln⁡k\ln k, between 2/32/3 and 11, remains open; it lies outside their question and is a natural direction for future work.

Unless stated otherwise, "the revised version" below is the PDF uploaded with this comment, "the submitted version" is the version submitted at the paper deadline, and all numbers refer to the revised version.

The revised version keeps all theorems, propositions and examples of the submitted version, together with their proofs, techniques and certificates. In addition, the two new results resolve the question the submitted version left open (its Open Problem 6.1): how the price grows with kk. Together with what the submitted version established, that concept classes can separate at all, with exact minimal examples, they close the open problem of Filmus et al.

We sincerely thank all reviewers and the area chair for the time and care they devoted to our submission, and for their constructive comments. The main concern in the reviews was that the submitted version resolved only part of the open problem of Filmus et al. (NeurIPS 2024): it answered the existence question, showing that adaptivity can strictly increase the optimal mistake bound even for concept classes, but left open the price of adaptivity as a function of the number of labels kk, including whether the gap can grow with kk at all. In response, we have uploaded a revised version of paper that settles this remaining question and resolve the open problem; the comments below describe the result and the revision in detail.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.