Adaptive versus Oblivious Adversaries in Bandit Online Multiclass Classification - Concept Classes Can Separate

In online multiclass classification with bandit feedback, the learner observes only whether its prediction was correct. Filmus, Hanneke, Mehalel and Moran (NeurIPS 2024) proved that for every class the optimal expected mistake bound against an adaptive adversary exceeds the one against an oblivious adversary by at most an O(k log k) factor (k = |Y|), and constructed pattern classes witnessing an Ω(k) gap; whether any gap at all is possible for genuine concept classes was left open (their Remark 1.3). We resolve the existence direction of this question. First, we exhibit a concept class of five functions on a two-point domain with k = 3 labels whose adaptive value is 16/11 and whose oblivious value is 7/5: a strict separation of ratio 80/77; a companion four-function class on two points separates as well (35/29 versus 7/6), giving the smallest known witness. Second, we determine the exact first-order asymptotics of a natural family of “multi-shield towers” H_r = {0,1}^{[r]} ∪ {2̄,…,(r+1)̄}: we prove a closed-form recursion for the adaptive value of every reachable state, deduce A(H_r) = 5r/8 + O(√r) and B(H_r) = r/2 + log₂ r − log₂ log₂ r + O(1), and conclude lim as r→∞ of A(H_r)/B(H_r) = 5/4 exactly. Third, we develop a capping theory that sharply delimits where any larger separation could live: a uniform first-hit principle shows that unions of classes with disjoint label blocks satisfy A ≤ (C₀ + 2)B regardless of nesting depth; a localization-rank refinement handles label reuse; and an exact closed form A = n/2 − E[(Bin(n,1/2) − d)₊] for threshold classes shows that the additive localization surcharge can grow like Θ(√n) even for two overlapping layers, ruling out any bound in terms of the overlap degree alone. All exact rational values reported here were verified by at least three independently implemented exact solvers with strong-duality certificates. The original Ω(k) question of Remark 1.3, and more generally whether sup_H A(H)/B(H) grows with k, remains open; our necessary conditions confine any linear Ω(k) separation to a narrowly characterized regime.