Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
Authors: Yuval Filmus
Steve Hanneke
Idan Mehalel
Shay Moran
Venue: NeurIPS 2024 poster (2024)
Keywords: Online learning
multiclass classification
bandit feedback
Primary area: online_learning

Abstract: Consider the domain of multiclass classification within the adversarial online setting.  What is the price of relying on bandit feedback as opposed to full information? To what extent can an adaptive adversary amplify the loss compared to an oblivious one? To what extent can a randomized learner reduce the loss compared to a deterministic one? We study these questions in the mistake bound model and provide nearly tight answers.
We demonstrate that the optimal mistake bound under bandit feedback is at most $O(k)$ times higher than the optimal mistake bound in the full information case, where $k$ represents the number of labels. This bound is tight and provides an answer to an open question previously posed and studied by Daniely and Helbertal ['13] and by Long ['17, '20], who focused on deterministic learners.
Moreover, we present nearly optimal bounds of $\tilde{\Theta}(k)$ on the gap between randomized and deterministic learners, as well as between adaptive and oblivious adversaries in the bandit feedback setting. This stands in contrast to the full information scenario, where adaptive and oblivious adversaries are equivalent, and the gap in mistake bounds between randomized and deterministic learners is a constant multiplicative factor of $2$.
In addition, our results imply that in some cases the optimal randomized mistake bound is approximately the square-root of its deterministic parallel. Previous results show that this is essentially the smallest it can get.
Some of our results are proved via a reduction to prediction with expert advice under bandit feedback, a problem interesting on its own right. For this problem, we provide a randomized algorithm which is nearly optimal in some scenarios.

Bandit-Feedband Online Multiclass Classification: Variants and Tradeoffs
Yuval Filmus
Steve Hanneke
Faculty of Computer Science
Department Computer Science Purdue University, USA
Faculty of Mathematics
Technion, Israel
steve www.hhe@gmailll......... com
filmus. yuval @gmail. ggmalmmall.. com
Idan Mehalel
Shay Moran
Faculty of Computer Science
Faculty of Mathematics
Technion, Israel
Faculty of Computer Science
i idammehalel@@maii
Faculty of Data and Decision Sciences
Technion, Israel
Google research, Isracl
shaymoran1@gman com
Abstract
Consider the domain of multiclass classification within the adversarial online set- ting. What is the price of relying on bandit feedback opposed to full information? To what extent can an adaptive adversary amplify the loss compared to an obliv- ious one? To what extent can randomized learner reduce the loss compared a deterministic one? We study these questions the mistake bound model and provide nearly tight answers. We demonstrate that the optimal mistake bound under bandit feedback is at most (kk) times higher than the optimal mistake bound the full information case, where i represents the number of labels. This bound is tight and provides an answer to an open question previously posed and studied by Daniely and Helbertal [ [13] and by Long ['17," 200, who focused determin- istic learners. Moreover,
present nearly optimal bounds of (k) the gap between randomized and deterministic learners, as well as between adaptive and oblivious adversaries in the bandit feedback setting. This stands in contrast the full information scenario, where adaptive and oblivious adversaries are equivalent, and the gap in mistake bounds between randomized and deterministic learners is a constant multiplicative factor of 2. In addition, our results imply that in some cases the optimal randomized mistake bound is approximately the square-root of its deterministic paraliel. Previous results show that this is essentially the smallest it can get. Some of our results are proved via a reduction prediction with expert advice under bandit feedback, a problem interesting on its own right. For this problem, we provide randomized algorithm which is nearly optimal some scenarios.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
The primary focus of this work is the study of multiclass online learning of hypothesis classes in the realizable setting (in which some hypothesis perfectly labels the input). Online learning is a repeated game between learner and an adversary. Each round in the game proceeds as follows:
The adversary sends an instance xa E X' to the learner.
(ii)
The learner predicts in E y (possibly at random).
(iii The adversary provides information (feedback) to the learner.
This problem suggests wide and appealing landscape of possible different setups, each granting or preventing various resources from the learner or the adversary which generates the input. The resources discuss are the information provided by the adversary, the adaptivity of the adversary, and the randomness of the learner. Full-information feedback means that the learner learns the correct label Ye at the end of every round. Bandit feedback means that the learner only receives indication whether i): = or not. If the learner predicts d). deterministically for every I, then the learner is deterministic. See Section A for formal and self-contained definitions.
We are interested in how the optimal mistake bound is affected by granting or preventing each of those resources. Below, discuss these questions and present our results.
1.1 Main questions and results
We assume that a concept class H. E y is given, where X' is domain of instances and y is label ser. Unless stated otherwise, we restrict the learning scenario to the realizable case, in which the input provided by the adversary is consistent with a concept from H.
In order to state the results, we define some notation. For a concept class H. let opt (H) denote the optimal mistake bound for H achievable with full-information feedback. Let opt (H) denote the same as opt (7C). with the additional restriction that the learner is deterministic. In the bandit feedback model, define opt (H) analogously to opt (H). When the learner is allowed to be randomized, the mistake bound in the bandit feedback model might change if the game is played against an oblivious or adaptive adversary (we define these types of adversaries below) D Therefore, we define the notations opt (H) and opt adep (H) to denote the optimal mistake bounds of a randomized learner which receives bandit feedback on its predictions, when the adversary is oblivious or adaptive, respectively. Unless stated otherwise, O and Ω2 notations hide universal constants that do not depend on any parameter of the problem.
1.1.1 Information
In the hull-information feedback model, the learner learns the correct label at the end of each round, regardless of its prediction. In the bandit feedback model, significantly less information is provided at the end of each round: the adversary only reveals whether the learner's s prediction was correct or
incorrect. This raises the following natural question studied e.g. by Auer and Long 1999] Daniely and Helbertal (2013) Daniely, Sabato, Ben-Da and Shalev-Shward 2015 Long 2020
What is the price the learner pays for receiving only bandit feedback?
The answer for this question is known for deterministic learners. Auer and Long 1999 proved the upper bound
baudit (H) O det (H) [}*] log [!])
det
for every concept class H. A matching lower bound was given in [Long] 2020 Geneson 2021
which showed that for every natural > there exists a concept class H with label set of size
In the full inll-nffornttio model there no essential difference between oblivious and adaptive adversaries (as long as the learner uses fresh randomness in every round) [Cesa- Bianchi and Lugosi 2006 Lemma 4.1]. Essentially, the reason is that in the full- inffoooooooonnn model the feedback is deterministic, even if the learner is randomized.

---

[ = k such that
det (H) [D]] log [D]))- They also find tight guarantees on the constants hidden in the O, Q notations.
bandit. (H) (ulp
det
Finding an analogous result for randomized learners was raised as an open problem in [Daniely and
Helbertal 2013 We solve this open problem by proving the upper bound stated in the following theorem.
Theorem 1.1 (Full-information vs. Bandit-feedhack). For every concept class holds that
bandit (H) Oloptfull O(opttand(7)) (H) 1))))-
Furthermore, for every natural l 2 2 there exists concept class H. with [ = k such that
opt (H) = So(pphhlll
moud (H) -)))-
The lower bound was noted e.g. in Daniely and Helbertal 2013 We complement it by proving an upper bound that holds for all classes. We prove Theorem 1.1 in Section D Note that opt (H) is precisely characterized by combinatorial parameter of H. called the randomized Littlestone dimension [Filmus, Hanneke, Mehalel, and Moran [023 (and characterized up to a multiplicative factor of 2 by the standard Littlestone dimension [Littlestone] 1988))
The techniques developed to prove this upper bound include new bounds for prediction with expert advice with bandit feedback, which is the main technical contribution of this work. These bounds are presented in Section I.2] and a technical overview of the proof can be found in Section 2
generalization to the agnostic setting. We also generalize results in the spirit of Theorem to the agnostic case, in which the best hypothesis in class is inconsistent with the input in r* many rounds. Our results do not require that r* (or some bound r 2 r* on it) is given to the learner. However, throughout most of the paper assume the stronger r-realizability assumption, in which an upper bound r 2 r* is given to the learner. That is, under r-realizability assumption the learner knows in advance that some hypothesis will be inconsistent with the feedback in most many rounds. We explain in Section G how to remove this assumption using a standard "doubling trick". Bounds for various setups in the agnostic setting are summarized in Table [
In the agnostic setting, learning algorithms are often measured by their expected regrer (which is the mistake bound minus the number of mistakes made by the best hypothesis). While in this work we measure algorithms by their mistake bound, note that a mistake bound of an algorithm is always least as large as its regret. Therefore, since bounds demonstrate dependence the number of rounds T, in some cases they provide improvements over the known regret bound
δ V optlop (7)
of Daniely and Helbertal, 2013). Specifically, when r* ((opt/aa (H)).
our results imply a regret bound of O(D) optt
det (H)), for all T.
1.1.2 Adaptivity
In Section 1.1.1 we showed that randomness is necessary for obtaining optimal bounds on the cost of bandit feedback. However, within the setup of a randomized learner which receives bandit feedback, there are (at least) two types of adversaries to consider: oblivious adversary which must decide on entire input advance, and an adaptive adversary that can decide on the input on the fly. This raises the following natural question.
Within the bandit feedback model, what is the price the learner pays for playing against an adaptive adversary?
We solve this question up to logarithmic factors. However, our nearly tight lower bound uses pattern classes, which are generalization of concept classes. In more detail, a pattern class is a set of
"The setting considered in Daniely and Helbertal 2013 is, however, more general than the setting we consider. They consider an adversary which can decide on a few correct labels in each round, and not only one. Generalizing this work to their multilabel setting interesting direction for future work.

---

Adversary
Oblivious
Adaptive
Learner
(D')(opttall det (H) + r*))
Randomized
(ID'( (H) + r*))
2DD' opt (H) + +r))
O ( log (optt (H) + +r*))
Deterministic
(D)) (7) log [Y] +r*))
Table I: Worst-case mistake bounds for learning concept classes with bandit feedback in the agnostic setting, in which the best concept in class is inconsistent with the feedback in r* many rounds. No prior knowledge on f* is required. The bounds for the randomized setup are obtained by applying Theorem D.3 to the upper bound in Theorem D. and to the lower bounds in Lemma C.I1 and in [Daniely and Hclbertal 2013). The bounds for the deterministic setup are obtained by applying the same theorem to the upper bound Auer and Long [999]. and to the lower bounds of Lemma C.5 and Long (2020). The same (up constant) deterministic bounds were proved independently in
[enneson and Tang 2024 (however, their bounds are in terms of given bound 2 r*).
patterns p E (X y)" which downwards closed (i.e. closed under sub-patterns). Proving the lower bound in the theorem below using only concept classes or showing that this is not possible is an interesting and main problem left open by this work.
Theorem 1.2 (Oblivious vs. Adaptive Adversaries). For every concept class H. it holds that
baudie (H) O(opt (H)) [)]] log [)])).
Furthermore, for every natural k there exists a pattern class with | and so that
adap (P) Ω handit (P) (
((ppt
The upper bound is immediate corollary of the upper bound @I. We prove the lower bound in Section E The proof idea the lower bound is to consider the classic adversarial |)] bandit problem of Auurr Cesa- Bianchi, Freund, and Schapire (2022 with an r-realizability assumption. This setting can be simulated using a pattern class, but not using concept class. For this problem, an adaptive adversary can force a mistake bound of (r [D]),, while the best an oblivious adversary can do is Orr + [)]).
Remark 1.3 (Concept classes vs. Pattern classes). Pattern classes are more expressive general- ization of concept classes (see a formal definition in Section A). Most desirably, would like to prove upper bounds for all pattern classes, accompanied with tight lower bounds that hold for hard concept classes. We manage to do so all of our results (for the sake of simplicity, we omitted from the theorem statements), except for Theorem [.2 in which the upper bound does hold for all pattern classes, but the lower bound holds only for hard pattern classes.
1.1.3 Randomness
In Section 1.1.2 we discussed two different adversarial models within the setup randomized learners. However, what happens if the learner cannot use randomness? A folklore result on the full-information feedback model states that for every concept class with [}]| it holds that
opt
fand (H) < optdet (H) < opt
fand (H).
and that there are classes attaining each equality. Extending this | > is straightforward by noting the following randomized-to-dee to-deterministic full-information algorithm conversion: If A is randomized algorithm, then the mistake bound the deterministic algorithm A' who always predicts the most probable prediction of A is at most twice the mistake bound of A. Indeed, whenever A' makes a mistake, makes mistake with probability at least 1/2. This raises the following natural question, also asked in [Danicly and Hclbertal 2013

---

Within the bandit feedback model, what is the price the learner pays for not using randomness?
We resolve this question up to logarithmic factors.
Theorem 1.4 (Randomized vs. Deterministic). For every concept class holds that opt (H) O (HL) [}]] log (J1)..
Furthermore, for every natural & > 2 there exists concept class H. with [>]| lc such that
opt (H) (( Saap (H) (D9)).
The upper bound is an immediate corollary of the upper bound (T. The proof idea of the lower bound is to construct class which hard for a deterministic learner, but becomes easy if the learner may use randomness. Concretely, we prove the following result from which Theorem 1.4 follows, in Section F
Theorem 1.5. For every d 2 and 2 2 there exists a concept class H C y with y
{0, 1,..,... k} such that
1. optiall (H) = + 1.
2. opt
handit (H) O k).
3. opthandit (H) = O + k)).
adap
The lower bound in Theorem 1.4 has a significant consequence on the problem of finding a combi- natorial dimension that quantifies the optimal mistake bound of randomized learners in the bandit feedback model. In the full-information model, the optimal deterministic mistake bound, which is captured precisely by the combinatorial Littlestone dimension [Littlestone] 1988). quantifies the optimal mistake bound of randomized learners as well, as demonstrated in (3) In [Daniely, Sabato Ben-David, and Shalev-Shwarzz, 2015), new combinatorial dimension, coined the Bandii-Lütlestone dimension, is introduced and proved to capture the exact optimal mistake bound of deterministic learners within the bandit feedback model. In [Daniely and Helbertal [013). some hope is expressed for this dimension to quantify the mistake bound of randomized learners as well, similarly to the case of full-information feedback. However, our lower bound shows that this is not the case. As we show in Section the classes used in the lower bound may be chosen such that opt (H) 0(D))),
and thus opt bandit (Ht) is only roughly / /optgendii (H). On the other hand, the upper bound in Theorem 1 together with the bound opt bandit (H)) 2 | (e.g. by Daniely and Helbertal 2013
shows that handi (H) is roughly the smallest that opt (H) can get.
1.2 Bounds for prediction with expert advice
main technical result proved in this work, which is interesting in its own right, a nearly optimal randomized mistake bound for the problem of prediction with expert advice in the r-realizable setting. In this problem, n experts make deterministic predictions in every round, and is promised that the best expert is inconsistent with the feedback for at most r many times throughout the entire game. As in Scction I.I.I the knowledge of r is actually not required, and r can be replaced with the actual number of inconsistencies of the best expert, r* In Section G we explain how to remove the assumption that r is given to the learner.
The learner should aggregate the experts' predictions to make their own (possibly randomized) predictions, while minimizing the expected number of mistakes made. This problem was extensively studied in the binary (()) 2) setting, starting with the seminal works of Vovk 1990 Littlestone and Warmuth| 1994) who showed that the optimal mistake bound when [] 2 is Olog n + for both randomized and deterministic learners. Later, Cesa-Bianchi, Freund, Helmbold, and Warmuth
[1996] proved fine-grained bounds for deterministic learners. Cesa-Biannche Freund, Haussler Helmbold, Schapire, and Warmuth 1997), Abernethy, Langford, and Warmuth [2006). Filmus.

---

Adversary
Oblivious
Adaptive
Learnr
O(k(loga n +r*))
Randomized
(k((log n + r*))
Okk loga + r*)
Deterministic
(kk(log(n/k) + +r* +
Table Mistake bounds for prediction with expert advice. The size of the label set is 2 2, there n 2 k experts, and the best expert is inconsistent with the feedback for r* many times. No prior knowledge on r* is required. The randomized bounds are due to Theorem C.7 and Lemmas C.10 The deterministic bounds stated in Theorem C.I
and C.11
Hanneke, Mehalel, and Moran [2023 further refined and improved randomized mistake bounds. Mukherjee and Schapire [2010] studied a variation where the experts are randomized and the learner deterministic. Similarly this paper, Brånzei and Peres [2019) studied the multiclass scenario, but with full-information-feedaaee which is substantially easier to the learner.
In this work, consider this problem in the bandit feedback model. Most previous works on prediction with expert advice under bandit feedback studied the best achievable regret. obtaining results that depend the number of rounds T, dependence from which seek to avoid in this work (see Section 3.4 for more details).
The main tool used to prove Theorem 1.1 is the following optimal (up to constant factors) bound on adap
bandit (n, k r), which is the optimal mistake bound achievable by randomized learner which plays against an adaptive adversary that provides bandit feedback, when there are le 2 2 many labels, k many experts, and the best expert is inconsistent with the feedback for at most many times.
Theorem 1.6. For every n 2 k 2 2 and r 2 0 holds that
opt (n, k. r) = (Ik(log,, n + r)).
This bound generalizes the result optbaudic (n, r) Ollog n r) mentioned above In the case where the adversary is oblivious, we prove the inferior lower bound
opt (n, k) 22(k log,
which is tight as long as r r Oloog, n). Proving tight bounds against an oblivious adversary for all values of remains open.
We also consider this problem in the deterministic (learner) setting, for the sake of completeness (we do not use the deterministic bound prove any other results). We prove all bounds in Section C and summarize them in Table Similarly to the results in Section [.I.I] since our mistake bounds demonstrate dependence the number of rounds T' they improve over the known regret bound O( <Tk log of Auer,
Freund, and Schapire [2002) whenever = O(log
2 Technical overview
In this section, we explain the idea behind the proof of the upper bound adap (H) ( (H) (D7)) in Theorem which is our main technical contribution.
There are two main ingredients used in the proof of Theorem
1. A reduction from the problem of learning concept class H to an instance of prediction with expert advice with opttii (Pt) many experts, | many labels, and where the best expert is inconsistent with the feedback for at most opt (H) many rounds.
When there only labels, full-infoon inllrrfformttonn and bandit feedback the same.

---

2. The upper bound for prediction with expert advice stated in Theorem 1.6
Indeed, having both items, we take the upper bound of item (2) with the parameters specified in item (I), obtaining
opt handit (Dyjottan (Rt) |3/, opt (H)
opt det (H)).
By item (1), this bound holds also for the problem of learning the concept class H. Since opt (H) s 20pt/all (7C). we can replace optiull (H) with oul (H). It remains to sketch the ideas behind the proofs of items (1) and (2), which we do in the following subsections. Of the two items, the proof of Item (2) is the main technical novelty.
2.1 Proof idea of Item (1)
In the problem of prediction with expert advice, the expert predictions are generated in a completely adversarial fashion. That is, no assumptions are made on the way those predictions are generated. Therefore, any upper bound for prediction with experi advice holds in particular for the case where the expert predictions are determined by an algorithm chosen by the learner. We can exploit this property to reduce the problem of learning a concept class H. to instance of prediction with expert advice with [)/jott[ many experts, |}]| many labels, and where the best expert is inconsistent with the feedback for at most opt (H) many rounds. The idea, described below, is inspired by Long 2020), Hanneke, Livni, and Moran 2021].
Let A be an optimal deterministic algorithm for learning H given full-information feedback. We run in parallel several copies of arranged in tree form. These copies will function as the experts fed into an optimal algorithm for prediction with expert advice.
Initially, there is single copy of A. every round, for each copy of A, if its prediction is consistent with the bandit feedback, we do nothing. Otherwise, if the copy is at depth D < opt (H). we split into Y different copies at depth D + each "guessing" a different full-information feedback for the problematic example; if the copy is at depth D, we do nothing.
Since the tree has depth at most opt (H), there are at most [)]oott(ai many copies of A. The copy of which always guessed correctly corresponds to an expert whose predictions are inconsistent with the feedback for at most opt (H) many rounds.
formal statement (and proof) of this reduction be found in Proposition D.2
2.2 Proof idea of Item (2)
In the context of classification problems, the realizable case in which some concept from the learned class accurately explains the correct classification is often simpler than the agnostic case. Therefore. for the sake of understanding the proof of the upper bound optaadi (n, k r) stated in Theorem 1.6 we first outline a proof for the upper bound on opt (n, k) == opt adap bgudit (n, As 0). This proof has the same flavor of the proof for general but is simpler. We then explain how adapt the proof for general r.
When r = 0, all living experts (that is, experts which have been consistent with the feedback so far) are identical: every expert which is inconsistent with the feedback in some round is immediately eliminated, and its predictions need not be taken into account any longer. By applying the law of total expectation, the optimal mistake bound can thus be described by the following optimization problem. Fix & 2 2, and for every n 2 1, let (nn) = opte (n, k). We have
(nn = max min max BEY
(aynn) +
Σ Ty (1 + (1( (((1(1()))))) 8'
where ã E [0, 11k is k-ary vector whose y th entry specifies the fraction of living experts predicting y: n is the distribution used by the learner to draw the prediction; and y E y is the correct label chosen by the adversary.
7

---

Since all living experts are identical, the natural intuition suggests that the optimal choice of á is to let every entry in it be 1/k; in which case the optimal choice of π would be the uniform distribution. In this case, it does not matter which y the adversary chooses as the correct label. Applying this intuition to results in the recurrence relation
V(n) S ((n/k//K + (1 (1 1/b)( + V(1 1/k)n)).
Solving this recurrence relation gives (nn) 2 k loogoc)) n, where b(k) = (Ą-1)+ which implies the statement in Theorem 1.6 since ((k) 2 k. It remains to show that the intuition that led us from (4)
to (5) is indeed correct. A natural approach would be to directly prove that ((z), as defined in +.
satisfies V(n)= k <log(<)) by induction
However, note that 4 contains & different recursive calls, so an inductive proof seems complicated. To overcome this, we use minimax duality, which significantly simplifies as we now explain.
Observe that once á' is fixed, each round of the game is a zero-sum game between two randomized parties | Therefore, we can apply von Neumann's 's minimax theorem and obtain a dual game which is equivalent to the primal (original) game in terms of its optimal mistake bound In the dual game, the adversary first chooses a distribution over the labels from which the correct label is drawn, and then the learner chooses its prediction. When the dual game is considered, the definition of V(n) from (4) becomes
V(n) ā, yEy
max min (Ty ((ann) + +1 - 71) + ((1 -ky)n))]
(6)
The notation is the same in (4) except that now æ is the distribution used by the adversary to draw the correct label, and y E y is the learner's ' prediction. Eq. (6) contains only two recursive calls, making inductive proof much easier (but still quite technical).
We now explain how to adapt this approach to work for general r, when is given. In Section G we explain how to remove the assumption that r' is given to the learner. When r >> 0, there is an inherent difference between the experts: different experts have been inconsistent with the feedback for different number of rounds, and so can afford different number of future inconsistencies. Therefore, we need some mechanism that differentiates between experts with different inconsistency budgets.
Inspired by weighted prediction techniques (See [Cesa-Bianche and Lugosi 2006) Section 2.1] and bibliographic remarks of Section 2), we rely on the fact that experts with higher budgets have higher potential to damage the learner, so we choose an expert potential function that matches the potential of an expert damage the learner. As such, the potential should be an increasing function of the budget. Choosing the potential as a function of the budget is a known method (see, e.g., (Cesa-Bianchi and Lugosi 2006 Corollary 2.4]. We use exponential potentials and give an expert with budget i (corresponding to i more allowed inconsistencies) potential of k We now employ roughly the same argument outlined above for the realizable case. The main difference is that V(-) depends on the total potential rather than on the number of living experts. As result, the initial number of living experts n is replaced with the initial total potential n. h2",, which gives
V(n 2rr) < A logg (n 22r) = k log, + 2Kr,
as stated in Theorem 1.6
3
Related work
We outline connections between previous work to the problems in the focus of this work: the role of various resources in realizable multiclass online learning of concept classes, and prediction with expert advice with bandit feedback.
"The adversary described in 4 deterministic, but we can allow it to be randomized without changing the value of V (n).
"Similar usage of minimax duality appears in previous work. for example (Abernethy, Agarwal, Bartlett, and Rakhlin 2009.
8

---

3.1 Information
The role of information learning concept classes was previously studied [Auer and Long
1999
Daniely, Sabato, Ben-David, and Shalev-Shwartz 2015 Daniely and Helbertal 2013] Long 2020
To the best of our knowledge, [Auer and Long [999] was the first to show that opt (H)
O (H)) log [27] for every class H. Long 2020 Geneson [021] improved the constant in
the upper bound of Auer and Long [1999). and showed that it is in fact tight up 1 + o(1) factor
by finding a sequence of concept classes demonstrating matching separation between opt (?)
dot
and opt (H). Our work proves an analogous result for randomized learners (Theorem 1.1. with the exception that we do not identify the exact leading constant in the optimal mistake bound.
The agnostic case was studied in [Daniely and Helbertal 2013), which proved the upper bound
δ TTDioopee (H) on the optimal regret, where is the horizon, and showed that the upper
bound is best- pest-possibbe up to logarithmic factors. The PAC learning setting was studied in [Daniely] Sabato, Ben-David, and Shalev-Shwart/ 2015]. which showed that the price of bandit feedback O(D2)) in this setting as well.
3.2 Adaptivity
In the setting of call-information feedback, adaptive and oblivious adversaries are essentially equiva- lent
and Lugosi| [0066] Lemma 4.1]. Indeed, full-information feedback, in its essence, implies that the feedback never depends on the prediction drawn by the learner specific execution of the game. In the bandit feedback setting, to the best of our knowledge, the existing literature on adaptive adversaries focuses on the agnostic setting and analyze different notions of regret. Notable examples are MMerhav, Ordentlich, Seroussi, and Weinberger 2002 Farias and Megiddo 2006 Arora
Dekel, and Tewari 2012].
3.3 Randomness
Daniely, Sabato Ben-David, and Shalev-Shwart? 2015) captures opt (H) precisely, and opt (H) up to multi- plicative factor 2. The paper Daniely et al., 2015 suggests a new combinatorial dimension, the
In the full-information feedback model, the Littlestone dimension [Littestone] 1988
Bandit Littlestone dimension, and proves that it captures dpt (H) precisely. The paper [Raman|
Raman, Subedi, Mehalel, and Tewari 2023) shows that the Bandit Littlestone dimension qualitatively
characterizes learnability also in the agnostic and randomized setting, even when [}] 00.
The papers [Daniely and Helbertal 2013 Raman al. 2023 ask whether the Bandit Littlestone dimension is good quantitative proxy for bandit (H). Theorem 1.4 (and Theorem F.1 in more detailed version) shows that this dimension is far from quantifying even opthandit (H).
3.4 Prediction with expert advice
The problem of prediction with expert advice in the r-realizable setting was introduced in (Vokk 1990 Littlestone and Warmuth, 1994] for the binary case ([)) = 2). Since then, this problem has been well-studhed, with papers spanning the past 30 years
Freund, Helmbold and Warmuth 1996, Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire, and Warmuth| 1997 Abernethy, Langford, and Warmuth [006]] Mukherrjee and Schapire 2010 Filmus, Hanneke, Mehalel and Moran 2023 The full-information setting for [V] >> 2 and small r was studied in [rääzei and
Peres 2019
The bandit feedback variation of the problem was introduced in [Auer, Cesa-Bianchi, Freund, and Schapire 2002), in more general version that considers rewards instead of losses (or mistakes). However, there is a major difference between how they define r-realizability and how we define it (in the setting of an adaptive adversary). In their definition, there must be an expert which makes most r mistakes, whereas we only assume that there must be an expert whose predictions are inconsistent with the bandit feedback at most r times.
When the adversary is oblivious, both notions of r-realizability coincide (see Remark A. for more details). Therefore, it is possible that their techniques can be used to obtain tight bounds for the

---

oblivious setting for all values of our bounds for the adaptive setting are tight in the oblivious setting only for small values (see Theorem (
Unfortunately, to the best of our knowledge, when converting rewards to losses and applying the bounds of Auer, Cesa-Bianchi, Freund, and Schapire| 2002) dependence the number of rounds T' emerges (see for example [Bubeck and Cesa- Bianchi 2012 Theorem 3.1J and Desa-Biannch and Lugosi 2006 Theorem 6.10)), which is undesirable when studying the mistake bound model (rather than the regret model). In this work we are mainly interested in the experts setting as a means for proving Theorem I.I and our proof specifically requires the adaptive setting. We leave for future work the question of finding mistake bounds against oblivious adversaries which are tight for large
values r.
4
Open questions and future work
Our work leaves some interesting open questions and directions for future work.
4.1
Open questions
The price of adaptivity for concept classes. Our proof of Theorem F.
usess pattern classes. Can
we prove using only concept classes, similarly to Theorem F. If not, what is the price of adaptivity when learning concept classes?
The exact role of randomness. There is O(log k) gap between the lower and upper bounds in Theorem I.4 What the correct worst case price of not using randomness?
The agnostic setting with oblivious adversaries. Our mistake bounds in the agnostic setting are not tight for large r* when the adversary is oblivious, both for the problem of learning concept class (Table DT. and for prediction with expert advice (Table 2). It would be interesting to obtain bounds that tight for large r* against oblivious adversary for both problems. One possible approach towards proving such bounds for prediction with expert advice is to use the techniques of Auer, Cesa- Basa-Biinchi, Freund, and Schapire 2002), and specifically the Exp4 algorithm.
A natural algorithm for the experts setting. Our randomized algorithm for prediction with expert advice is optimal, but not very natural nor efficient, as it relies on the calculation of minimax values. While the analysis of our algorithm employs the well-known paradigm of potential-based weighted experts, the learning algorithm itself does not make any use of these weights to devise its predictions. This is in contrast many learning algorithms that integrate the weights into the prediction process (See (Cesa-Bianchi and Lugosi] 2006, Section 2. and bibliographic remarks in Section 2). Can design natural algorithm, the spirit of algorithms such weighted majority (Litllesoon] and Warmuth| 1994] and Exp4 [Auer, Cesa-Bianchi Freund, and Schapire 2002), that achieves the guarantees of Theorem C.7 up constant factors?
4.2 Future research
The multilabel setting. It would be interesting to generalize the results of this work to the multilabel setting considered in [Daniely and Helbertal [013). which the adversary allowed to choose several correct labels in each round. When the adversary is adaptive, it is not hard to see that this equivalent to the label setting considered in this work with a deterministic learner. What happens when the adversary is oblivious?
Other types of feedback. This work considers the full information and bandit feedback models. However, one can think of other types of feedback. Consider for example the comparison feedback model: if the true label is and the prediction is the adversary provides the feedback op E {<,- .>} such that z op y. An interesting direction for future research to prove results in the spirit of this work for comparison feedback, or for other natural types of feedback.
10

---

Acknowledgments and Disclosure of Funding
We thank Zachary Chase for many insightful discussions on the problems in the focus of this work.
Shay Moran is a Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by Azrieli Faculty Fellowship, by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
Jacob Abernethy, John Langford, and Manfred K. Warmuth, Continuous experts and the binning algorithm. In International Conference on Computational Learning Theory, pages 544-558. Springer, 2006.
Jacob D. Abernethy, Alekh Agarwal, Peter I.. Bartlett, and Alexander Rakhlin. A stochastic view of optimal regret through minimax duality. In COLT, 2009.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Conference on Machine Learning, pages 1503-1510. Omnipress, 2012. URL pattps://dl acm. herg/doi/10..o
0142273.30427999
Peter Auer and Philip M. Long. Structural results about on-line learning models with and without queries. Machine Learning, 36:147-181, 1999.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77, 2002.
Simina Brânzei and Yuval Peres. Online learning with an almost perfect expert. Proceedings of the National Academy of Sciences, 116(13)5999-5554, 2019.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Nicolo Bisa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Nicolo Cesa Bianch,, Yoav Freund, David P. Helmbold, and Manfred K. Warmuth. On-line prediction and conversion strategies. Machine Learning. 25(1)711-110, 1996.
Nicolo Cesa- BiinnBBinchh, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How use expert advice. Journal of the ACM (JACM), 44(3):4274855 1997.
Amit Daniely and Tom Helbertal. The price of bandit information in multiclass online classification. In Conference on Learning Theory, pages 904104. PMLR, 2013.
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shward Multiclass learnability and the ERM principle. Mach. Learn. Res., 16(1):2377-2444, 2015.
Daniela Pucci De Farias and Nimrod Megiddo. Combining expert advice in reactive environments. Journal of the ACM (JACM), 53(5):762-799, 2006.
Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal prediction using expert advice and randomized littlestone dimension. In COLT, volume 195 of Proceedings of Machine Learning Research, pages 773-836. PMLR, 2023.
Jesse Geneson. A note on the price of bandit feedhack for bounded online learning. Theoret- ical Computer Science, 874:42-45, 2021.

---

Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Jesse Geneson and Linus Tang. Bounds on the price of feedback for mistake-bounde online learning. arXiv preprint arXiv:2401.05794, 2024.
Steve Hanneke, Roi Livni, and Shay Moran. Online learning with simple predictors and a combi- natorial characterization of minimax in 0/1 games. In Conference on Learning Theory, pages 2289-2314, PMLR, 2021.
Nick Littlestone.
Learning quickly when irrelevant attributes abound: new linear-threshold algorithm. Machine learning, 2(4):285-318, 1988.
computation, 108(2):212-261, 1994.
Philip M. Long. New bounds on the price of bandit feedback for mistake- online multiclass learning. Theoretical Computer Science, 109-159-, 2020.
Neri Merhav, Erik Ordentlich, Gadiel Seroussi, and Marcelo Weinberger. On sequential strategies for loss functions with memory. IEEE Transactions on Information Theory, 48(7):1947-1958. 2002.
Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili.. List online classification. In The Thirty Sixth Annual Conference Learning Theory, pages 1885-1913. PMLR, 2023.
Indraneel Mukherjee and Robert E. Schapire. Learning with continuous experts using drifting games. Theoretical Computer Science, 41 411029-30)2670-2668,,, 2010.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances Neural Information Processing Systems, 23, 2010.
Sasha Rakhlin, Ohad Shamir, and Karthik Sridharan. Relax and randomize: From value to algorithms. Advances in Neural Information Processing Systems, 25, 2012.
Ananth Raman, Vinod Raman, Unique Subedi, Idan Mehalel, and Ambuj Tewari. Multiclass online learnability under bandit feedback. arXiv preprint arXiv:2308.04 04620, 2023.
John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-320, 1928.
Volodimir G. Vovk. Aggregating strategies. Proc. of Computational Learning Theory, 1990, 1990.
12

---

A Definitions
Let X be domain, and let y be a countable label set. Unless stated otherwise, we assume that y = [k] for some natural k 2 2. A pair (z, E X x D is called an example, and an element z E X'' called an instance or an unlabeled example. A function h: X + y is called a hypothesis or concept. A hypothesis class, or concept class, is a non-empty set H. C y We note here that it is generally assumed that there exists an instance E X such that for every y E Y there exists h E H satisfying h(z)= y. This assumption is reasonable since when this is not the case, the hypothesis class H has an essentially isomorphic class 't' with label set strictly smaller than y (see Raaaan
Raman, Subedi, Mehalel, and Tewari 2023
We will mostly consider the more general notion of pattern classes. A pattern p E (X' x Y)" is finite sequence of examples, A pattern class is non-empty set of patterns P which is downwards closed, meaning that for every p E P. every sub-pattern p' of p (obtained by removing examples arbitrarily) is in P as well. Let p. be sequences (which can be either patterns or some other type of sequences). we denote by Py the sub-sequence p consisting only of the indices in I. The set might be given by clear and well-known notation. For example, if p 21..... Zr. then for some t S T. the notation P&t represents the sub-sequence Z1,..., Zy. Denote the concatenation of p. q by p q. If p is sub-sequence of q, we denote C Cq.
Note that pattern classes generalize concept classes: for every concept class H we may define the induced pattern class
p P (X (X min Σ 1((x)) + f =0 0
P(H)
hEH (Z.
In words, P(H)) contains all patterns that are consistent with H. and thus from an online-learning perspective there is no essential difference between H. and P(H). Therefore, throughout this section we consider only pattern classes.
In this work, we consider multiclass online learning of pattern classes in the realizable setting. Online learning is repeated game between a learner and an adversary. Each round & in the game proceeds as follows:
The adversary sends an instance xy E X' to the learner.
(ii) The learner predicts d. E y (possibly at random).
(iii) The adversary provides (full-information bandit) feedback to the learner.
Full-information feedback means that the learner learns the correct label yı at the end of every round. Bandit feedback means that the learner only receives indication whether dt ys not. If the learner predicts dr deterministically for every t, then the learner is deterministic.
In the bandit feedback setting, we model learners as functions Lrn: ((X' x {-,, [+} x 3""" X²) - [T]] from the set of pairs of a feedback sequence and an instance, to the set [T] of all probability distributions over y. For E [T]) we denote the probability of y in by Ty. In a feedback sequence (I1, o 0i),,-. ...,, (IT, oPT: (r), the triplet (æ,, Ope: (t) represents the fact that round t the instance was 24, and that Dt = Yt if op =-, or dt * yt if op =/. The learner's predictions thus may depend on past feedback as well as on past and current instances. In the full-information feedback model, op = at all times, and we omit it and use the pair (x,,,), W1) instead of the triplet (x,, (x,,op,80 9c).
Given a learner Lrn and fixed input sequence of examples S = (I1,81)... v1).
(2T, Vr). we denote the expected number of mistakes that Lrn makes when executed on the sequence S by Maan (Lrn; S) it receives full-information feedback, and by Moandit (Lrn; S") if it receives bandit feedback. We define the optimal mistake bound of P when the adversary is oblivious to
gund (P) inf sup Maanl (Lrm; S), opt (P) inf sup Mhandit (Lrn; S), Lm SEP
(8)
Len SEP
in the full information and bandit feedback models, respectively.
Remark A.I (Strong vs. Weak Realizability). The restriction S E P that the supremum taken over is called strong realizability, which requires that the input sequence is taken from the class P. On
13

---

the other hand, unless stated otherwise, in this work we consider the weak realizability assumption. Under this assumption, is only required that for any learner, the feedback provided by the adversary is consistent with some pattern from P with probability 1. When the adversary is oblivious and the input sequence
chosen beforehand, strong and weak realizability coincide. Indeed, note that for any learner who never predicts label with probability O, strong realizability must hold in order to satisfy weak realizability.
The adversary in the above definition is indeed oblivious to the learner's actions, in the sense that it must choose the target pattern S E P before the beginning of the game. contrast, in the setting of the bandit feedback model we will also consider stronger adaptive adversary which is allowed to choose the target pattern on the fly, as long as satisfies the weak realizability assumption, meaning that the feedback provided to the learner is consistent with some p E P with probability 1. In addition, is allowed to choose the correct label at random 6
When the adversary is adaptive, the online learning game defined above operates as follows in every round
(i) The adversary sends an instance 2, E X' to the learner.
(ii) The learner chooses a probability distribution z²() over y and reveals to the adversary.
(iii) The adversary chooses a probability distribution 7(0) over V
(iv) The learnr draws a prediction ÿt E y from x1)) and reveals it to the adversary.
(v) The adversary draws the correct label from 7(1) and tells the learner if its prediction was correct or not.
We formalize an adaptive adversary as a pair of functions
Advz: (X' x A+, x 3²) + X, Advy: (X' x (-, 3'"" x X' x mD1 IT])
In every round I, Adv is used in the first step choose the instance Ft, and Adv,, is used in the third step to determine the distribution from which the correct label yt E y is drawn. In more detail, let F (X' A}} x y)* be the feedback sequence given to the learner before round t. The adversary sends the instance = (FF) to the learner in the first step. In the third step, the adversary computes the distribution -!!) = Adv,, AFv,,(F,,,,, (9)).
A feedback sequence F E {-, 3 is realizable by P if there exists a pattern in P that is consistent with F. An adaptive adversary is consistent with P if for every feedback sequence F E (X' x {-, A} )²" which is realizable by P and for every π E I1(7,, the following holds. Let x = Adv, (F). J. If Adv,((r F, x. T) т, then the feedback sequence o (2, -, ,,y) y) is realizable for every y in the support of 7.
Given a learner Lrn and an adaptive adversary Adv which provides bandit feedback, we denote the expected number of mistakes that Lrn makes against Adv by Moandit (Lrn; Adv). We define the optimal mistake bound of against an adaptive adversary which provides bandit feedback by
adap
(P) inf sup M(Lrn; Adv),
Lm Adv
where the supremum is taken over all adaptive adversaries which are consistent with P.
We denote by opt (P) and optget (P) the optimal deterministic mistake bounds of P with iill-infommatin and bandit feedback, respectively. That is, in these settings we require the additional restriction that Lrn must be deterministic. We may sometimes refer to mistake bounds as the learner's loss throughout the entire game. Unless stated otherwise, the notations O, 22 θ hide universal constants which do not depend on any parameter of the problem.
B The primal and dual games
In this section describe game-theoretic formulation of opt opteatiit and apply the minimax theorem to obtain a dual formulation which will be useful in Section C
We term the game defined in Section A
'It is explained in the sequel that being randomized does not really help the adversary
7 One can verify that in the deterministic case, oblivious and adaptive adversaries equivalent.
14

---

when played against an adaptive adversary as the primal game. In the dual game, we basically just switch the order of the second and third steps of the primal game (together with some other required but not meaningful minor changes). We can think of the primal and dual games as the same game, only that after the adversary chooses It, in the primal game the learner chooses distribution (over the labels) first, and in the dual game the adversary chooses a distribution first. Formally, the dual game operates as follows in each round t:
(i) The adversary picks an instance E X' and a probability distribution 7(() over y. It reveals both to the learner.
(ii) The learner chooses probability distribution x() over y draws a prediction f E y from 771), and reveals it to the adversary.
(iii) The adversary draws the correct label yt from 7(9) and tells the learner if its prediction was correct or not.
In this section, we show that the primal and dual games are equivalent in terms of their optimal mistake bounds. The motivation behind this that the target function of the optimization problem describing the optimal mistake bound in the dual game will turn out to be simpler. This will enable the analysis Section C and might be of further interest. The equivalence will mainly follow from von Neumann's minimax theorem [von Neumann, 1928] Using minimax duality to analyze minimax target functions of online learning problems has proved useful in previous works. Notable examples [Abernethy, Agarwal, Bartlett, and Rakhlin Shamir, and Sridharan 2012].
2009 Rakhlin, Sridharan, and Tewari 2010 Rakhlin
We now get into the details. In the dual game, n depends on the distribution 7(1) chosen by the adversary, and the distribution 7(t) does not depend on the distribution π((), Therefore we have to change the formal definitions of a learner and an adversary in the dual game. The adversary is defined as a single function Adv: (X' x {-,, A} x y)* + (X' x I[[]).. The learner is defined as a function Lrn: (X {+, y)* x X IDD + [D].. The optimal mistake bounds in the primal and
dual games are defined in a dual manner:
opt (P) = inf sup M(Lm; Adv), Adv
opt_ opt_dhane (P) = sup inf M(Lrn; Adv). Adv Lm
(10)
First, provide explicit definitions for opte (P) and opt _ dddap (P) in terms of simpler classes, based on the instance and feedback provided by the adversary in every round. For every instance x: define the class: P== - tw E P (x, v) op E P for some y E V).
Additionally, define the following classes for every pair of instance and label (x, v):
Pa-y tp E P: (z, y) o P}, Paty = PAPPa-g
To simplify presentation, we assume that in the primal game the adversary is deterministic, and in the dual game the learner is deterministic. This is reasonable since after the first player has made its choice, the optimal choice of the second player is deterministic. Let us now define adap (P) and opt _ (P) in terms of classes of the form Pa-ry and P Pattgi
(Petwi)) (11)
opt adap (P) = sup inf inf sup Ny opt (Pa-g) +
Σ Ty (1 +1+0ps opt adap v'Ky
vEy
opt_ dadap (P) sup inf x,7 yey
Fo opt godap (Pz-z) + (1 - TØ) + opt dadap (P (Patt))] (12)
For these equations to be well-defined, it is technically convenient to define opt (0) = opt_ dpdep (0) = -00 Now, by the law of total expectation, for every pattern class P the above equations indeed define the optimal losses in the primal and dual games. We can now prove the cquivalence.
15

---

Lemma B.1. For every pattern class P:
opt handit (P) =opt_ opt_d jot_dhaandi (P).
adap
Proof. For a horizon (number of rounds) T, let pppppp (P, T). opt ppt_dbaucic (P, T) be the analogue adap
notations to bandii (P), opt handit (P), with the additional restriction that the game is played for T' rounds. We adapt [II and (12) to those definitions in the obvious way. Note that
gadap
opt (P)
sup opt adep (Pa., T), TEN
and similarly for opt bandit (P). Therefore, to prove the lemma, it suffices to show that adap (P2, T) = opt_d dadap (Px: T') for all x, 7 such that Pa * 0 (when Pa = both are have opt (P 2, 0) 0
bandit
for all T). Let E X be such that P= + 0. For T
opt opt_dbandis dadap 0).
For the induction step, note that the expression for opt_dbandit (Pz, T) suggested by (12 describes zero-sum game in which the adversary goes first, and both the learner and adversary choose distributions over y to draw a label from: the learner draws a prediction and the adversary draws the correct label. The target function is the optimal loss to be suffered by the learner the sequel, after the distributions are fixed. The adversary's ' goal is to maximize it and the learner's 's goal is to minimize it. Since this zero-sum game, by the minimax theorem [von Neumann, 1928 we can dadap let the learner go first instead, without changing the value of o (PayT), Therefore we can write opt_ d (Pa, T) as:
inf sup yE
opt__dddap gadap Ty opt_dpppppp bandit T
Σ Tty opt_ o jadap
bandit (Pa , T 1))
3/ su
By the induction hypothesis, we can change every dddap to adap which gives:
inf sup x yEy
Ty oppp (P (P2+yy:2 T +)+
Σ
Ty (1 + bandit (P (Paty' T 1))
(13)
1/ /'
By applying
13 observe that opt__paamt (Pz. T) opt
opt
adap bandit
(Pz, as required.
B.1
An optimal learner for the primal game
The optimal randomized algorithm achieving adap (P) suggests itself from 11. For complete- ness, we explicitly write it in Figure The algorithm may be implemented using straightforward dynamic programming for finite hypothesis classes, even in the r-realizable case where the best hypothesis is inconsistent with the feedback in at most many indices.
Proposition B.2. The algorithm BanditRandSOA is well-defined and optimal.
Proof. The choice of (() is well defined because (4) feasible linear optimization problem, and as such it has a solution. The algorithm is optimal due to (1I).
C Prediction with expert advice
In this section we are interested in optimal mistake bounds for the bandit feedback setup of prediction with expert advice in the r-realizable setting. In this problem, n experts are making predictions in each round, and is promised that the best expert is inconsistent with the adversary's 's feedback in at most many rounds. An adversary following this limitation is called r-consistent. Nothing else is assumed about how the experts decide on their predictions. Furthermore, in Section G we explain how to remove the assumption that r is given to the learner with only constant factor degradation in the mistake bound. Based on the experts' predictions, the learner should make its own prediction for each round, while minimizing the expected number of mistakes it makes in the entire game. In
16

---

BanditRandSOA
Input: pattern class P.
For .......
1. Receive instance xa X.
2. Construct a distribution (1)) such that
x(1) E arg min max *ElD)) yEY/
Ty pppttaande (P2-v) + Σ Ty. (1 + Sataa (P (PtAy))
(14)
Draw the prediction St from (1)),
4. If the feedback is positive, update P == Pa-rii and otherwise update P Pa
Figure I: BanditRandSOA is an optimal randomized learner for online learning with bandit feedback of pattern classes, where the adversary is allowed to be adaptive. It is inspired by the RandSOA algorithm of Filmus, Hanneke, Mehalel, and Moran (2023), which randomized variant of Littlestnoe's Littlestone: 1988 well-known SOA algorithm.
the binary full-information feedback model, this problem is well-studied. and tight bounds were proved for both deterministic and randomized learners Vovk 1990 Littlestone and Warmuth [1944
Cesa-Bianchi, Freund, Helmbold, and Warmuth [996] Cesa-Bianchi, Freund, Haussler, Helmbold
Schapire, and Warmuth 1997 Abernethy Langford, and Warmuth 2006 Brânzei and Peres] 2019 Filmus, Hanneke, Mehalel, and Moran 2023].
In this work, we are mostly interested in the randomized (learner) and adaptive (adversary) setup with bandit feedback, and the bound prove for plays central role in the proof of Theorem [.] For the sake of better completeness and exhaustiveness, we consider the other deterministic (learner) and oblivious (adversary) setups as well. Our results for all three setups are summarized in Table 2
We adapt the notation for learning pattern classes. Suppose that there are k 2 2 many labels and 2 k many experts, where the best expert is inconsistent with the feedback in at most 2 0 many rounds. We assume that n 2 h since n < then having l labels is equivalent to having n labels. When the learner is deterministic, the optimal mistake bound is denoted by optdet (n, k; r). When the learner is randomized, the optimal mistake bound is denoted by opt (n, k r) or opt (n, k. r). depending on whether the adversary oblivious or adaptive, respectively. For the realizable case 0, we omit from the notation.
C.1 Warm-up: deterministic learners
In this section, we analyze opt (n, k r) and prove the following theorem.
Theorem C.I. Ler 2 k: 2 2, 2 0. Then:
optia
det
(n, k r) O(k(log(n/k) + 1)).
We first prove the upper bound and then the lower bound.
Lemma C.2. Let 2 k > 2, 2 0. Then for every a > 1:
det
(n, k, a
klnnn - a" /k) ()) 1
Proof. We describe a deterministic learner which makes at most the stated number of mistakes. We
use simple generalization of Weighted Majority [Littlestone and Warmuth, 1994). A similar idea appears also in [Long] 2020].
17

---

Every expert is given an initial weight of a", Let W2 be the total weight of experts in round t. In every round, predict the label that enjoys a weighted plurality. If we make a mistake, then the weight of every expert which voted for the predicted label is divided by a. If an expert reaches weight less than 1, we reduce its weight to O, since it must mean that it made more than mistakes. We split the analysis into two epochs. The first epoch is as long as W, > k, and the second is afterwards.
We begin by analyzing the first epoch. By assumption, W, k at all times. On the other hand, whenever the learner makes a mistake, at least 1/k of the weight is being divided by a. Therefore, a mistake occurs in round t then
)
(1-a-1)a
W4+1 $ (1-1/W)W, + We/(ak)
ak W
Now, if mi is the total number of mistakes the learner makes long as W, > k, then my must satisfy
at my nn.on me St
knn. n. a²
ak
After some manipulations, derive the bound
ak
m1 < a a-1 In(n a² /k).
We now analyze m2, which the number of mistakes in the second epoch. If W2 S then there are at most l experts which have not yet made more than mistakes. At least one of them will never err again, and therefore in the worst case, the learner will make mg S k more mistakes before climinating all experts apart from the target expert. Summing mi + m2 gives the stated bound. D
We may now deduce the upper bound.
Corollary C.3. Let k 2 2, 2 0. Then:
det
(n, k: s - - k(In(k/k)n)--a-ennmn +r) + 1.
c-
Proof. Apply Lemma C.2 with =
We can also deduce an improved upper bound for the realizable (r 0) case.
Corollary C.4. Let > & > 2. Then:
bandit (n, k) < k In(n/k) + + 1.
det
Proof. We can easily see that opt (n, k) < (1+ backkillin (n(n/k)= k k 1 for every > 0 by applying Lemma C.2 with a - co. There also an explicit optimal learner for which this holds with obtained by slightly changing the proof of Lemma
We now turn to the lower bounds. We begin with the realizable case.
Lemma C.5. Lern 2 k 2 3. Then:
det (n, 2 (k/2 - 1) In(n/k).
Proof. The adversary the following simple strategy. Let n,, be the number of alive experts (that is, experts which are consistent with the feedback given so far) at the beginning of round t. As long n, k, in every round /. the adversary splits the alive experts evenly possible among the k labels, and gives negative feedback to the learner. Note that the largest set in the partition consists of [n//k] n2/k < 2n,/ k experts, since n4 k. Therefore, every round at least (1 - 1--/kk-fraction of the experts make it to the next round. The adversary can thus force at least m many mistakes on the learner whenever m satisfies
(1 2m > k.
which holds if
2 (m 1) k,
18

---

by using the inequality 1 - > e that holds for all x < 1. After some manipulations, the inequality reads
m (k/2 - (n)/2/))))((/))+++++
which implies the stated bound.
To devise a lower bound for the r-realizable setting, we prove the following lemma. It was indepen- dently proved also by Geneson and Tang (022).
Lemma C.6. For every n 2 k 2 2, 2 0 we have:
bandit (n, k,, k(r 1) 1.
det
Proof. Suppose that there are n = experts. In every round for T = k(r + 1) rounds, the adversary lets expert predict the label i, and always provides negative feedback to the learner. Let i be the label that the learner predicts the least number of times, and let * i* Since 7 k(r+1)-1 must hold that i* is predicted by the learner at most r times. In every round which the learner predicts i", set the true label to 2'. In all other rounds set the true label to i*. By definition of the strategy, the best expert makes most mistakes.
We may now prove Theorem
C.1
Proof of Theorem C.I The stated bounds are known when & = 2 by e.g. [Vovk] 1990 Littlestone
and Warmuth 1994]. For k 2 3, the upper bound follows from Corollary C33 and the lower bound
follows from Lemmas C.5 and C.6
C.2 Randomized (Learner) and Adaptive (Adversary)
In this section we provide a tight upper bound on opt (n, r) by proving the following theorem. Theorem C.7. Let 2 k 2 2, r 0. Then:
bandit (n, k,) S & logs 2kr.
adep
We will prove the theorem by analyzing the mistake bound the equivalent dual game, as described in Section[B] B. The primal and dual games are described in Section B ii terms of pattern classes, so we first show that the problem of prediction with expert advice the r-realizable setting is in fact equivalent to learning appropriate specific pattern class.
For every hypothesis class and budget function B: H + R. define the pattern class
1(h(x) * v) S B(h) }
P(H, p P (x x)) 3h H
Σ (r.U)Ep
(15)
In words, P(H, B3 consists precisely of those patterns which are consistent with some h E H everywhere except for at most (h)) many places. We call B(h) the budget of h. Therefore, if B, is the budget function that gives budget all hypotheses, then learning the pattern class P(H, B,) under the assumption of realizability is equivalent to learning the hypothesis class H. under the assumption of r-realizability.
Observe that for fixed number of labels kt, the class of n experts simply the hardest concept class of size n, since every expert can predict any label in every round. Denote this class by Un,ks kc that prediction with expert advice with n experts and & labels in the r-realizable setting is equivalent to leamning the pattern class P(Un,k, B,) under the assumption of realizability. Therefore, have
opt bandit (n, k, r) = opt adap
bandit (P(un,,, B,)) = opt_dpppp.oo dddap (P(un,, B,))
due to Lemma B.I
For completeness, we formally define Un.k- This is the class of projection functions over the set of k-ary vectors of length n, X' [k]".. That is, if the n functions are (hi....,hh, then for every E X we have hz(x) 2ú, where æ; is the value of the i' th entry of x.
19

---

We now define some notation used in the proof. As observed in [Abernethy, Langford, and Warmuth 2006 Bränzei and Peres 2019). since the experts are identical, in every round the game we only care about how many of the experts are still alive (which means they have not been inconsistent with the feedback for more than r many rounds), and among those which are alive, how many have budget i, for each 0 S S Following [Abernethy, Langford, and Warmuth, 2006, Bränzei and Peres 2019), we represent this information by an (r + 1) J-arry vector ri (Mo. my), in which the number m, indicates the number of living experts with budget i. We call this vector the state of the game.
For any state m, let (m) be the optimal loss in the dual (or primal) game for the pattern class representing the state m. as defined in (15). That is, P(u,, Ba)) is the pattern class representing the state m, then (m) opt_dhaniit
dadap (P(Ln,, Ba))). We call (mm) the value of the state m. The goal is thus to upper bound the value of the initial state V
Towards this end, we use the following potential-base technique. An expert with budget will have potential of k.2 This will allow us to bound V ((m) in terms of the total potential of the experts, given by (m) = Ei=o my k
Let b(k:
g
We will prove the the following.
(k-1)
Lemma C.8. Let k: 2 be the number of labels. For any state holds that
V(ñ) & k logg(s) W(m).
In order to prove Lemma C.8 we will need the following technical claim, proved at the end of this section. Lemma C.9. Let k 2, and let
fx( = ((1- B)(8// + -11)))((--)))=-))) 1/k.
Then fx(3) S for all B E [0, 1].
We can now prove Lemma C.8
Proof of Lemma C.8 The proof is by induction on the state, ordered in the obvious way: the state (1, (1.0.....0) 0) is the lowest, and the state (O...., 0, n) is the highest.
In order to be able always apply the induction hypothesis, decreases between rounds. Indeed, the only case where the state does not decrease between rounds is when all experts predict the same label y. In this case, an optimal adversary must choose y as the correct label with probability 1, and thus an optimal learner must predict y. Nothing is changed in such rounds, and therefore they may be removed, ensuring that the induction hypothesis always be applied.
must assume that the state always
In the base case, 17 (1,0,... 0). Therefore
((m) = k logg()) = ls loga()) W(m).
For the induction step, consider the first round of the game, in which the adversary draws the correct label from a fixed distribution 7. Let Vg, (17) be the optimal number of mistakes made by the learner if it predicts y when the state of the game is m. Let m_ be the state of the game in the next round, in the current round the correct label is y. Define mAy in a similar way. Using 12) we may now write
V,,m) Ty (mñ + (1 (1 + (mū+))).
Since the learner is allowed to predict any y y (and specifically the y which minimizes Vy(m)). it suffices to bound Vg (m for some y of our choice. We now consider two cases.
Case 1. Suppose that there exists y E y which satisfies
(mm 2 1+ (m,+)
Then:
Vy,m) < V(m-,) < l loggR) W W(m-g) S ls klgg(()) W(m)
by the induction hypothesis, concluding the first case.
20

---

Case 2. Suppose that for every y E V.
V(m-ay 1 + Am)
Let y E y be such that Ty 2 1/k. Then by assumption.
(m)) Σ (1/k)V(m-y)) + (1 - 1/k)(1 + ((m+a))-
The induction hypothesis now implies that (m)) < 1 - 1/k + loga(k) Wm,+p)) (k= 1) logo(k) W Wm,
(16)
Let 3 E [0. 1] be the fraction of experts predicting y. weighted according to their potential. If the true label is y then a 8-fraction of the potential W (m) is untouched, and a (1 3)-fraction is multiplied by at most 1/k (experts with budget have their potential multiplied by 0), and so
W (m - ((1 B)/k² + (m)).
Similarly.
W (mmAy) S (B/k² (1 ()).
Plugging this into [6). we have
(m) S 1 1/k logs(e) ((1 3)/k² 3)W (m) (k- 1) l0go(1) (3/k² +(1 ()),
which after bit of manipulation reads as
(m) S (og(()) W( + loga( (((1 B)/h² + (3/11 + +(1 (1- 1/k.
To finish the proof, it remains to show that
f(3 == loga(1) (((1 3)/k² + 3)(/k²² + (1- 1/k
bounded from above by -1 for all [ E [0, 1], which is the statement of Lemma C.9
We can now prove Theorem
Proof of Theorem C.7 Clearly b(k) (O...., ,0, 12), we get
k. Applying Lemma C.8 on the initial state m
adap (n, k = opt_dhannii (P(un, B.)) = VO..... 0, n) s k &logo()) (n-k2r) S k logg 2+
as desired.
C.2.1 Proof of technical lemma
In this section we prove Lemma C.9
Let us first restate it in a more convenient way. Define
1 8
3
k-1
(3) =
+ 3
+1 +1
622
2
The lemma states that for all k: 2 and 8 E [0. 1].
we have
9b (B) < b(k)) where b(k)
(k: 1)k-11
Routine calculation shows that
k-1
1
(b) = 2 +1 B
[12 - + 1- -Io3 3 kk)B]
1-63
222
12
It follows that 9k (3) is maximized at
k22 +
Bx
13 k
at which point its value is Therefore we need to show that for all k: 2 2,
gk (Bc) (A:2 + 1) 1)
3.3k
(122 + 1)(k - 1)k
(I: - 1)(0-1)(1-1/A)
< b(k) (11-1/6)
A.3
h
Rearranging, we need to show that
(k2 + 1)(k 1)(k-1)/k < 22
This holds since k2 + +1 < 3 2k and (A- 1) 11)/ < k.
1)//
21

---

C.3 Lower bounds for randomized learners
In this section, we prove lower bounds for randomized learners. We prove lower bound which is tight when the adversary is adaptive for all triplets n, k. We also prove lower bound which is tight even when the adversary is oblivious, but only for all triplets n, k, satisfying r (log,, n).
We first prove near-optimal lower bound on opt (n, k).
Lemma C.10. Let n 2 k 2 2. Then
A --1
opt (n,
[logy nl.
Proof. Assume without loss of generality that km for some integer (otherwise replace with the largest power of k below it). We label the set of experts using the elements of [k]]",, that is, for each .1..... . Vm [k] there is expert hyv1..... ym)) We choose the correct expert at random.
We label the instances by $1..... Lm. where the prediction of h(y,, ......... ,ym) on 2; yi. The fixed sequence of instances is
For any randomized strategy of the learner, it will discover the correct label of x, after having made at least 1=d mistakes in expectation (see for example [Daniely and Helbertal 2013 Claim 2)). Therefore the expected number of mistakes incurred by the learner least 2 m. Consequently, for each learner there is an expert h1y11 (um) on which it makes at least as many mistakes in expectation.
Let us now prove lower bound for the r- r-realizable case. In contrast with the realizable case, this bound holds only against an adaptive adversary.
Lemma C.11. Let k 2, O. Then
bandii (n, k, (k 1)r/2.
Proof. For better readability assume that is even. Suppose that n k. In every round, the adversary let expert predict the label i. We describe an adversary which chooses the correct labels at random and forces the learner to make at least (k 1)r/2 mistakes in expectation. Therefore, there exists an adversary which chooses the correct labels deterministically and achieving that. Before the game starts, The adversary draws random sequence yı,... Ukr/ of kr labels independently and uniformly. In round f,, the adversary chooses y/2 as the correct label. The adversary ends the game when one of the following conditions hold:
The learner has predicted correctly in r/2 rounds.
2. The game was played for kr/2 many rounds.
First, we show that the learner makes at least the stated number of mistakes in expectation. There are two to consider. If the game is finished because kr/2 rounds have passed and the learner has not yet made r/2 correct predictions, then the learner has made at least (k 1)r/2 mistakes with probability one, concluding this case.
In the second case, we assume that the game is finished when the learner makes exactly r/2 correct predictions. Partition the rounds of the game into r/2 intervals: the first interval starts at the first round. Each interval ends when the learner makes a correct prediction. The expected number of rounds in each interval is stochatically dominated by Geom(1/6) random variable. Since in every interval there is exactly single correct prediction, the total expected number of mistakes in all intervals is (A= 1)r
remains to show that the adversary is r-consistent. Assume without loss of generality that best expert is not consistent with all correct predictions of the learner, which is at most r/2. Now, recall that the number of rounds in the game most kr/2. Therefore, there must be a label i* predicted by the learner in at most r/2 many rounds. The best expert is at least as good as the expert
22

---

i", which predicts 1* in all rounds. The adversary is thus r/2-consistent on rounds where the learner correct, and r/2-consistent on rounds where the learner is incorrect. In total, the adversary is r-consistent.
In the proof, we only used the adversary's adaptivity to decide on the number of rounds in the game, and not on the correct labels. Therefore, one might conjecture that it is possible to use the same technique for proving lower bound also against an oblivious adversary. However, it is not possible; as we show in Proposition F.2 it holds that opt (k: k. r) O + +r) for all k 2 2,r 2 0. The essential reason allowing Proposition E.2 is that oblivious adversary must be r-realizable in strong sense, as discussed in Remark A.1
C.4 Tight bounds for randomized learners
We can now deduce tight bounds on adap (n, k, r), and bounds on opt (n, k r) which are tight in the regime Ologg, n).
Theorem C.12. Let k 2,r 2 O. Then
opt (n, k OKo(log n + r)).
Furthermore, if S C. log n for some constant then
opt (n,, ki Oc logg n)
where Oc hides a constant that depends on C.
Proof. The bound opt bonddit (n, k, ((log + r)k is implied by putting together the upper bound of Theorem C.7 and the lower bounds of Lemmas C.10 and [.II The lower bound in optohl (n, r) Oc (k logg n) for C logg easily follows from Lemma C.10 and the upper bound from Theorem
D
The role of information
In this section, we prove the following theorem, which implies Theorem 1.1
Theorem D.1 (Full information vs. bandit feedback). For every pattern class P C (X' x y)* it holds that
opt baudic (P) < 6k opt
adap
rand (P).
Theorem D.I will also allow us to extend Theorem 1.1 (which is formulated for concept classes) to the r-realizable setting.
D.1 Reduction from bandit to full-information feedback
Given Theorem C.I. the main ingredient left in order to prove Theorem D. is the following reduction from learning with bandit feedback to learning with full-information feedback. Let briefly describe the idea, inspired by [Long] 2020 Hanneke, Livni, and Moran 2021].
The upper bound we prove on adap (n, k. r) makes no assumptions on the way the experts make their predictions. Therefore, it holds in particular for the where the experts' predictions determined by algorithms chosen by the learner. We can exploit this property to reduce learning with bandit feedback to learning with full-information feedback. Let A be deterministic full- information learning algorithm that is guaranteed to make at most r many mistakes against any adversary. Whenever A is consistent with the feedback, we do nothing. When A is inconsistent with the feedback, we can be sure that it has made mistake, We thus create & different copies of A, each guessing different full-information feedback, exactly one of which is correct. Given that A makes at most r many mistakes when provided with full-information feedback, an optimal randomized algorithm for the bandit feedback model will thus make at most opt (k'", k r) = O(k- r) mistakes against an adaptive adversary. The details are made precise in the proof of the proposition below.
23

---

Proposition D.2. Let A be deterministic learning algorithm, for pattern class P C. (X x V in the full inllrmiiforation setting, which makes at most r many mistakes on any sequence S P. Then,
bandit (P) S 3k T.
Proof. We employ an optimal algorithm for prediction with expert advice, where the experts result from running A and translating the bandit feedback into a full-information feedback all possibly ways.
At each round t we will maintain k-ary tree of depth at most r, each of whose leaves is labelled
by sequence of d < r tagged examples (+1, F ,t,, Vt....... (fa, Fea Nt.). Each internal node has its outgoing edges labelled by the elements of y. Initially, T consists of single node labelled by the empty sequence. Additionally, we communicate with an optimal learner B for the problem of prediction with expert advice in the r-realizable setting, with k" experts indexed by [A:].
At round i, the adversary sends an instance Iy to the learner. The learner uses A to generate a prediction for each leaf: if the leaf is labelled by the sequence o, then the corresponding prediction is A(a, xz), These predictions are converted to expert predictions as follows. A leaf at depth d has an "address" a E [k:] formed by the labels of the edges on the path from the root. All experts whose index extends make the same prediction as f. These expert predictions are sent to the optimal learner B, which provides a label ÿt- The label is forwarded to the adversary, which responds with either - or A.
The learner now updates the tree as follows. For each Ieaf in the tree, it checks whether it predicts a label which is inconsistent with the adversary's feedback. This can happen in two ways: either the leaf predicted dt and the adversary feedback was A, or the leaf"s prediction was different from d and the adversary feedback was -. For each such leaf, if the leaf is at depth r, then we mark it as bad (a leaf not marked as bad is a good leaf). Otherwise, suppose that the leaf labelled by a. We add to the leaf l children, and label the y "tt child by a (t, y). This completes the description of the algorithm.
Let S* E 'P be pattern that the adversary is consistent with at the end of the game. We say that a label (t1, Fi, Ft, Ut,)...., Sty Vt,)) consistent with S* S (art, Vt.) for [d]. The definition of the algorithm ensures that the following properties hold at the conclusion of each round
1. Each good leaf at depth d corresponds to an expert whose predictions are inconsistent with the bandit feedback for exactly rounds. This is because we add children to a leaf precisely when its prediction is inconsistent with the bandit feedback (unless it is already at maximal depth, which case we mark it as bad).
2.
For each good leaf whose label a is consistent with S" if we run A on the sequence a, then it makes mistake at every round. Indeed, when we add a new leaf labelled a o (t. xr, Vr). where S = (Iz, Ve), the prediction of A on Se must have been incompatible with the bandit feedback, and in particular, with yt. which is compatible with the bandit feedback.
3. There is always good leaf whose label is consistent with S*
Indeed, consider any leaf satisfying this at time t- 1, let its label be or, and let S = (Ir, Ve )- If é is at depth then A must output y, on input (a, 22,) due to the preceding item (it cannot make more than r mistakes on any sub-sequence of S*)). Consequently, doesn't 't become bad.
If l at lower depth and its prediction inconsistent with the bandit feedback, then its child labelled a (t, 2t, y1) satisfies the required properties.
In particular, due to items (1) and (3) there is an expert whose predictions are inconsistent with the bandit feedback for at most r rounds. Using the algorithm given by Theorem C.7 results in a learner whose loss is at most
band (k*,, k,r) S ls (k') + 2kr = 3kr,
as desired.
24

---

D.2 Proof of Theorem D.1
Proof of Theorem D.7 We use Proposition D.2 with Littlestone's Littlestone 1988 SOA algorithm for the class P as the full-information algorithm A. Originally, SOA was formulated in terms of concept classes rather than pattern classes, but adapting pattern classes is straightforward (see
e.g. [Moran, Sharon, Tsubari, and Yosebashvili 2023]). Since the adversary is consistent with P. is known that the SOA algorithm will make most 2opt (P) mistakes long as it receives full-information feedback. Proposition D.2 now provides the stated bound.
L
D.3
An extension to the agnostic setting
In Section C we considered the r-realizable setting, in which the adversary is only r-consistent with the class of experts. The exact same setting can be considered when learning concept classes in general. Furthermore, in Section G we explain how to remove the assumption that is given to the learner.
Our bounds hold for all pattern classes, allowing an immediate adaptation our results for concept classes to the r-realizable setting. Indeed, as mentioned also in Section for every concept class H. and budget function B: I we can define the pattern class appearing in (15):
{
P)H, = PE E (XXx))) 3h E H: Σ 1[h(x) + vl B(h) (u.y)Ep
Choosing Br. where B, gives the budget every h H. simulates the class H. in the r-realizable setting. To transform bounds for pattern classes in the realizable setting to bounds for concept classes in the r-realizable setting, only need the following bounds on opt B,)). which were originally proved for the binary case k = 2, but can be extended in straightforward manner to arbitrary k.
Theorem D.3 (Cesa-Biannhi al. 1996 Auer and Long 1999 Filmus al. 2023 ). For every
concept class H and r 2 it holds that
det opt
(P,,, B,)) = @(opt (7() + r)
The bounds obtained using Theorem D.3 are summarized in Table T
E
The role of adaptivity
In this section we prove the following result, which implies Theorem 1.2 Theorem E.1 (Oblivious vs. adaptive adversaries). For every natural k 2 2 there exists pattern class P C (X' 3)" with | = k and so that
adap (P) 12( optiandit (P)).
The proof employs the concept class H which consists of all constant functions. This corresponds to the classical bandit problem, in which there are only labels. We use the notation opt (H, r) for optobl bandit (P(H, B,)), and similarly for other setups.
Proposition E.2. H y be the hypothesis class consisting of all constans functionn, and let r 2 0. If k | 2 2 then
optobl (H, = O(k +r).
Proof. The lower bound follows easily from [Daniely and Helbertal 2013 Claim 2). For the upper bound, we describe learner which makes at most 34(k + r) mistakes in expectation:
First phase For 16(k + r) rounds, predict each label with probability 1/k. If there are at least 8(k r) correct predictions, set y to be the plurality vote among all rounds in which the learner guessed correctly, and move to the second phase. Otherwise, repeat the first phase.
25

---

Second phase In this phase, the learner always predicts y, switching back to the first phase once it makes r mistakes in the phase.
In order to analyze the expected number of mistakes, we assuming (without loss generality) that the input sequence is infinite, and let y E y be the hypothesis which is r-consistent with the input sequence chosen by the oblivious adversary.
Let us analyze the expected number of mistakes. In the first phase, we consider 16(k + r) rounds, and therefore the expected number of correct guesses is μ4 10(k+r) Let be random variable &
counting the number of correct predictions in the first phase. Since 2 16, and since X is a sum of independent random variables taking values in {0, 1}. applying Chernoff's bound implies that
Pr[X < 8(1 + +r/h)] & Pr[x & //2) 6 o < $1/e <1/4.
(17)
There are at most many examples which are not labeled by y². Therefore, in expectation, there are at most rostr/k many examples which are both correctly classified and whose label not given by h.. Let Y be random variable counting all examples that are not labeled by y from the correctly classified examples in the first phase. Using Markov's ' inequality, we have:
E
Y X/2
r/k
Pr(Y 2 X/2 X 2 8(1 + r//k]
1/4.
(18)
4r/k
If y y² then the learner will make at most
mistakes in the second phase.
In order to finish the proof we calculate the expected number of times this two phase process will occur until that y = y In the worst case, by 117 18 this number of times is dominated by Geom (3/4)²) random variable, which means that this process will occur at most (4/3)² < 2 times in expectation. Overall the expected number of mistakes is at most 2(16(k +r) < 34kk+r) O
We can now prove Theorem E.
Proof of Theorem E.1 Given & 2 2, we choose the pattern class P = P(H, (H, Bx), where H. consists of all constant functions.
Lemma C.11 shows that handit. (P) = =(k2)), while Proposition E.2 shows that opt (P)
adap
O(k). yielding the stated bound.
The proof of Lemma C.11 goes through with any hypothesis class of size k. where k | We conclude that the worst-case dependence on r in optbandia (H, r) is related the size of H. For example, every H with [H] satisfies opt (H,r) O + r). However, there classes H with H k- which satisfy opt
(H, 12(rr) due Lemma C.10 This is in contrast to opteane (H, r): for any class H (of size at least k) it holds that optean (H, r) = 1((r).. would be interesting to find tight bounds on the worst case opt (H, r) for the intermediate cases where [H| = = for E (1,r).
F
The role of randomness
In this section we prove the following result, which implies Theorem I.4 by applying it with d = k. Theorem F.1 (Restatement of Theorem 1.5p. For every 2 and 2 there exists a concept class H y with = {0, 1, 1....,k} such that
1. opt (H) d
2. dpt
bandit (H) (dd k))
3. bandit
adap
(H) O(d + k)).
26

---

Proof. We first define the class H. : H(d, k). The domain is X' fæi..... Zack For every y E (I....,ke k), define H, be the class of all functions that label all instances with y, except for set X" C X' of at most d many instances, which they label with 0. Let
H
Hy.
VE (E......
We start with Item 1 For the upper bound, the learner always answers 0 until it makes the first mistake and receives feedback a positive label y. Then always answers y and makes most more mistakes. For the lower bound, the adversary asks on 2,, Id and always tells the learner that it made a mistake. In the first round, the adversary determines the true label be either y = or y 2, depending on the learner's prediction. In the other d rounds, the adversary determines the true label to be either or y, depending on the learner's predictions.
We now prove Item 2 For the upper bound, the learner tries to answer 1 until it makes d + mistakes, then does the same with 2, and so on until it gets k. For the lower bound, the input sequence of instances the adversary asks on is 21,..... ddk., and the adversary always provides negative feedback to the learner. The number of mistakes made by the learner thus d k, and it remains to find an appropriate target function that realizes it. Since there are d k rounds, there must be label y* E [A] predicted by the learner for set X' of instances of size at most d. We choose the target hypothesis h" to be the hypothesis that gives the label O to the instances of X', and y" to all other instances. The hypothesis h belongs to H by definition.
Finally, we prove Item 3 The lower bound is straightforward by using Daniely and Helbertal 2013 Claim 2]. We prove the upper bound by describing randomized learner for H that makes at most 2(d + k) mistakes in expectation. The learner operates in two phases. In the first phase, for every instance for which it has not yet received positive feedback, picks 0 with probability half, and all other labels with probability 1/(2k) each. Once the learner receives positive feedback which is given on a prediction different from O, enters the second phase, in which will always predict this label, and will make at most d more mistakes on instances labeled with O.
It remains upper bound the expected number of mistakes in the first phase. There are two types of mistakes:
1. Rounds where the adversary chooses the label 0. We divide these rounds into d (or fewer) phases: the first one ends when the learner correctly guesses the first instance labeled O; the second one ends when the learner correctly guesses the second instance labeled O; and so on. Once the learner has found d instances labeled O, the remaining instances must have a positive label. Let X; (where S S d) be the number of mistakes made in the i'th phase.
2. Rounds where the adversary chooses positive label. Let Y be the number of mistakes in such rounds.
Each of XI...., X, is stochastically dominated by Geom (ccmm1122) (1/2) 1 random variable (that is, geometric random variable from which we subtract 1), and Y is stochastically dominated by a Geom(1 (1/2k) random variable. It follows that the expected number of mistakes is at most
d(2 1) + (2k - 1) < d 2k.
Together with the at most d additional mistakes in the second phase, we conclude that the learner makes most 2(d + k) mistakes in expectation.
Theorem provides a negative answer to an open question posed by Daniely and Helbertal (2013] who ask whether opt (H) do (H)) for every class H. For H defined in the proof of
Theorem F. with d k, we see that bandit opt
(H) 0
/pt (H)
This separation is tight
optdee (Pt)
up to logarithmic factor: the bounds banda (H) 52
(following from the upper
klog
bound Auer and Long 1999)) and opt
bandit (H) > 2 (e.g. by [Daniely and Helbertal 2013))
1-1
imply that opt (H)- = Ω oppteetdit (H)/ log opt (74) for every class H.
27

---

ALGORITHM DT
Input: A concept class H: learner A for H that when given /d enjoys mistake bound of di (r + d2), where d1, d2 2 1 does not depend on r. Initialize: TM- d2.
For: 1.2....
1. If the best hypothesis inconsistent with the feedback for at most TM many rounds:
(a) Predict as A predicts under the assumption that the best hypothesis inconsis- tent with the feedback for at most TM many rounds, and given all information gathered by in previous rounds.
2. Otherwise:
(a) Update FM 2 TM-
(b) Restart A.
Figure 2: The "doubling trick" algorithm DT.
Another interesting corollary of Theorem F.1 is that significant separation between full-information and bandit feedback holds, in some cases, for deterministic learners but not randomized learners. Indeed, as long while bandi (H) is of order ((d k))
(k), we have that both opt (H) and opt adap (H) are of the order O(d),
G Prediction without prior knowledge
When studying agnostic mistake bounds previous sections, we assumed the r-realizability assump- tion, in which the number of inconsistencies the best hypothesis (or expert) has with the feedback, r*, given to the learner (or some decent upper bound on it). In this section, we show how to remove this assumption, while suffering only constant factor degradation in the mistake bound. To achieve this goal. we use a "doubling trick" in the same spirit of the doubling trick used [Cesa-Bianchi ett al.) 1997] Section 4.6). The algorithm DT, described in Figure 2 for the r-realizable setting. That is, requires knowledge of a decent upper bound 2 r" to work well. Algorithm DT converts it to algorithm which works well without this prior knowledge, in the following way. It operates in phases, where in the beginning of each phase it resets the memory of A, and guesses bound I'M on r* which is larger than the value guessed the previous phase. When the best expert in this phase reaches тм + inconsistencies, we deduce that our guess of тM was incorrect, and move to the next phase. Thus, once TM 2 r", guaranteed that DT enters its last phase. The values we choose for T'M guarantee that the obtained mistake bound of DT is not much worse than of A, when given the knowledge of r*
receives input algorithm A
Let (T(A) denote DT when executed with the r-realizable algorithm
Proposition G.1. Let H. C. yx be concept class. Suppose that A is a bandit feedback learning algorithm for H, that when given bound r 2 r", enjoys a mistake bound of d,(r + d2), where di, d2 2 1 does not depend on r (but may depend on H). Then, algorithm DT(A), without any prior knowledge, enjoys a mistake bound of 10d,(r" + d2). Furthermore, if deterministic then so DT(A).
Proof. We split the execution of DT to phases according to the value of TM- That is, in phase i, have TM = 2' 2'dz, where 2
We now consider two cases. In the first case, suppose that r* < d2. Then the initial value rM d2 a correct guess, and thus DT simply runs with this assumption, and enjoys mistake bound of 2d,d2 2d, (r* + d2).
28

---

In the second case, let a* > 0 be such that 1" = d2. In the worst case, the values of PM chosen
by DT during its execution are 2 d2. 2' d2...., 2a- dz. 2 d2. where a = [a"]. Indeed, if h* is the best hypothesis, then it is inconsistent with the feedback for at most r' many times throughout the entire run, and in particular, throughout the last phase where TM 2 r*. Since DT resets A at the end of every phase, in each phase i, DT is guaranteed to make at most dj (2 + d2) mistakes in expectation. Between phases, when the best hypothesis inconsistent with the feedback for the (TM 1)'th th time, another mistake might be made by DT. By linearity of expectation, we see that the mistake bound DT is at most
d1
(2'd2 + d2) saa aata + d1 Σ 2 d2 S 5d, dd.
1=0
Now, since a - 1 a", we have r* 2 2 1d. Therefore:
5d d2 = 10d, 20 d2 S 10d1r".
The "furthermore" part of the proposition obvious from the definition of DT.
The mistake bounds proved in this work under the assumption that bound r 2 r is given are typically of the form f())))(r + g(opt/al (HO), ((I)), where f.g are functions R. Therefore, we can apply Proposition G.1 with d1 = f(D))) d2 g(opt (H), (1)) to our bounds, and remove the assumption that a bound r 2 r* is given.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims are proved in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Each result applies to the specified setting for which is proved.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
Complete proofs of all theorems may be found in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is 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 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 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 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset 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 reprodueibility. the case of closed-source models, 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 have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer: [NA]
Justification:
Theory paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpipps.ccppullc//uuuii wwwticccguie//eeieeeeeeii CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Theory paper.
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 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.
7. 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?
Answer: [NA]
Justification: Theory paper.
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, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

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 96% CI, if the hypothesis of Normality of enrors 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 range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Theory paper.
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 compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: htap:::////rrpps/p httpp//uriss.puuupp/pe/ppe http:/p......bbii/ittcccccceeeea
Answer: [Yes]
Justification: Theory paper.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Theory paper.
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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
33

---

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 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.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Theory paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whworee.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
34

---

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


Reviews:
[{"review_id": "s80DMzdcLe", "reviewer": "Reviewer_qJc1", "summary": "This paper studies online multi-class classification in the mistake bound model. It focuses on understanding how various resources affect the optimal mistake bounds of the learner. These resources concern feedback models (bandit feedback vs full information), adversarial models (adaptive vs oblivious), and learning strategies (randomized vs deterministic). The paper provides a collection of nearly tight upper and lower bounds and addresses some open problems. To prove one of the results, the paper also presents new results for the problem of prediction with expert advice under bandit feedback.", "questions": "- Are there any unique challenges in the multi-class setting as opposed to binary classification?\n\n- Can you further discuss the implication of the lower bound in Theorem 1.4?", "limitations": "The settings are properly discussed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses several important questions in online learning. Some of these questions have previously been studied for different settings, and this paper fills some of the gaps in the literature. The paper presents an interesting collection of nearly tight upper and lower bounds that are relevant to the learning theory community. In particular, it shows that in the bandit feedback setting, adaptivity of the adversary and randomness of the learner play a bigger role in the mistake bound, in comparison with the full feedback setting.\n\n- The results are both clean and thorough, and the paper generalizes some of them to the agnostic setting.\n\n- The new techniques for prediction with expert advice under bandit feedback can be interesting on its own.\n\n- The results lead to some interesting open questions and future directions.", "weaknesses": "- There are still some gaps in the provided upper and lower bounds. For example, in Theorem 1.2, the lower bound only applies to certain hard pattern classes. Also, the algorithm proposed for the prediction with expert advice problem does not seem practical.\n\n- The paper is highly technical and may be challenging for non-expert readers. Many important discussion are also deferred to the appendix. \n\n- The results are interesting from a learning-theoretic perspective; however, it would be nice if the paper can discuss the practical implications of the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to weakness #1:\n\nIt is indeed an interesting open question to find a more natural and efficient algorithm for the experts setting. This question is discussed in detail at the open questions section. \n\n\nResponse to weakness #2:\n\nWe agree that some important concepts and discussions appear only in the appendix. Since our paper studies various problems and variations, this is unfortunately unavoidable due to space constraints. We sincerely tried to keep the most important discussions in the main paper. In the next version of this paper, we will incorporate the suggestions of reviewer x7iL, and will make another pass to see if there are any other improvements that can be made to improve the paper’s readability.\n\n\nResponse to question #1:\n\nYes. Even with full-information feedback, multiclass learnability was only fully characterized recently, in [1]. Also, in binary classification there is no difference between bandit and full-information feedback, so the challenging nature of bandit-feedback is not manifested in binary classification.\n\n\nResponse to question #2:\n\nThe implications of the lower bound in Theorem 1.4 are explained in detail in lines 121-134. The significant consequence of this bound is the fact that for certain classes, while exactly quantifying the deterministic mistake bound, the bandit-Littlestone dimension can be quadratic in the randomized mistake bound. On the other hand, there are some classes for which this dimension quantifies both deterministic and randomized mistake bounds. The conclusion is that a combinatorial characterization of randomized learners (which are very common in online learning), if exists, cannot be obtained solely by the bandit-Littlestone dimension. \n\nReferences:\n\n[1] Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. Proceedings of the 36th Annual Conference on Learning Theory (COLT), 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VbE3kYw0f9", "reviewer": "Reviewer_x7iL", "summary": "This paper considers online multi class classification in the adversarial setting with a focus on the worst-case expected number of mistakes as a performance measure. The paper studies the effects of information (i.e. feedback provided to the learner), adaptivity (of the adversary) and randomness (of the learner), and derives new upper and lower bounds relevant to each of these considerations.\n\nFor information, the paper solves an open problem from Daniely and Helbental (2013) and provides results for showing the price of bandit versus full-information for randomised learners. The proof of this theorem is the main technical contribution of the paper and relies on a reduction of the problem to a particular instance of prediction with expert advice, and the derivation of new bounds for the prediction with expert advice problem. The results give upper and lower bounds on the mistakes which are tight to logarithmic factors.\n\nSimilarly, near-matching bounds are derived showing the cost of facing an adaptive adversary, rather than an oblivious one and for following a deterministic policy rather than a randomised one.", "questions": "Lines 21-29 would facilitate easier understanding for the subsequent sections if a more explicit detail of the problem setup could be given here. Perhaps some of the definition from lines 434-442 could be ported to here, or some additional details and a reference to Appendix A?\n\nLines 66-69 describe the concepts of inconsistency and realisability only very briefly, in a way that is likely to be challenging for the unacquainted reader. Can you perhaps add some further details here?\n\nLine 153: the list of related literature preceding this is dense and it is hard to parse which papers contribute what from it. It is then not absolutely clear what the precise novelty is at this point: is this the first paper to derive any bounds for multi-class prediction with expert advice and bandit feedback?\n\nLine 135: maybe these new results should also be highlighted in the abstract if they are of independent interest?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The paper answers a number of open questions in the area, providing a comprehensive piece of work which covers several important aspects of the important problem of online classification.\n\nThe theoretical contributions are non-trivial and well explained, particularly the sketches of the key ideas of Theorem 1.1 and 1.5 in section 2, which highlight the main novel contributions of the paper.\n\nThe connections to existing literature are very well established within the text.", "weaknesses": "The main weakness of the paper is its readability. A lot of key concepts are deferred to the appendices, presumably to highlight the most technically impressive contributions sooner, and I feel that the paper would be more accessible if more space were given to describing fundamental aspects of the problem in the introductory sections. See questions section for some specific suggestions, but a general commitment to making the paper easier to understand would be welcome.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Contribution of Theorem 1.1:\n\nWe first want to make sure that the contribution of Theorem 1.1 is completely clear.\nIn the summary, the following statement is made with respect to Theorem 1.1: “The results give upper and lower bounds on the mistakes which are tight to logarithmic factors.”\nHowever, Theorem 1.1 establishes a tight upper bound on the role of information. This is especially important because proving a bound which is tight up to a logarithmic factor is possible even without using randomness, as stated in Equation (1). It is also known that shaving this extra log factor is impossible if the learner is deterministic, as stated in Equation (2). The open question that we solve is, whether this extra log factor can be shaved by leveraging randomness in the prediction method. Theorem 1.1 answers this question affirmatively.\n\n\nResponse to Weakness:\n\nWe agree that some important concepts and discussions appear only in the appendix. Since our paper studies various problems and variations, this is unfortunately unavoidable due to space constraints. We sincerely tried to keep the most important discussions in the main paper. However, we completely agree with your valuable suggestions written in the questions section. We will incorporate those in the next version of this paper, and will also make another pass to see if there are any other improvements that can be made to improve the paper’s readability. We thank you for helping us to improve the paper!\n\nResponse to question/suggestion #3:\n\nMany previous works studied regret bounds for prediction with expert advice with bandit feedback. However, converting those regret bounds to mistake bounds (in which we are interested in this work) results in bounds which are generally extremely sub-optimal, as they depend on the number of rounds in the game. More details can be found in lines 306-310.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LLDNlqBY4f", "reviewer": "Reviewer_WVbQ", "summary": "This paper studies the mistake bounds of multiclass classification with adversaries. This paper provides the mistake bound gaps between the bandit feedback setting and full information setting, between the adaptive and oblivious adversaries for randomized learners under the bandit feedback setting, and between the randomized and deterministic learner.", "questions": "N/A", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- This work considers various settings.\n- The proposed gaps between adaptive and oblivious settings and between randomized and deterministic learners are nearly optimal.\n- Several future directions are discussed.", "weaknesses": "- For the agnostic setting with oblivious adversaries, the mistake bound is not tight for large $r^*$.\n- The randomized algorithm proposed for the expert setting involves minimax calculation, which is inefficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to weakness #1:\n\nAs stated in lines 310-313, we are mainly interested in the experts setting as a means for proving Theorem 1.1. We believe that the paper already explores a sufficient range of problems and variations within the setting of learning hypothesis classes. Therefore, we intentionally leave the oblivious adversary case of the experts setting for future work, as solving it may require a fundamentally different approach.\n\nResponse to weakness #2:\n\nIt is indeed an interesting open question to find a more natural and efficient algorithm for the experts setting. This question is discussed in detail at the open questions section.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "as6Yi8Ae7L", "reviewer": "Reviewer_qHYZ", "summary": "The work studies multiclass classification with a finite label set $\\mathcal{Y}$ and a model class $\\mathcal{H}$ of $\\mathcal{Y}$ -valued functions. The analysis focuses on optimal mistake bounds as opposed as optimal regret. In particular, the goal is to find tight relationships between optimal regret bounds, $\\mathrm{opt}(\\mathcal{H})$ for deterministic and randomized algorithms, against oblivious and randomized adversaries, in the full and bandit feedback models. The main contribution is an upper bound relating $\\mathrm{opt}(\\mathcal{H})$ for randomized algorithms and adaptive adversaries in the bandit model to $\\mathrm{opt}(\\mathcal{H})$ for randomized algorithms in the full feeedback model. The main result is proven through an auxiliary technical result proving a nearly optimal randomized mistake bound for the problem of prediction with expert advice in the $r$-realizable setting (where $r$ is the mistake bound of the best expert).", "questions": "Can you elaborate more on the relationship between mistake bounds and regret bounds for bandit multiclass classification? I am also referring to the extent to which proof techniques can be re-used in the other setting.\n\nCan you list the available bounds on the various $\\mathrm{opt}(\\mathcal{H})$ that only depend on the hypothesis class and the cardinality of the label class?", "limitations": "There is not an explicit section about limitations, but the authors adequately point out the open questions.\nThe work is theoretetical with no immediate societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work provides new results characterizing the price of bandit information in the optimal mistake boind for multiclass classification. The topic has been intensively studied in the literature on learning theory and is still of interest for the community. The technical contribution is original and nontrivial. The presentation is clear and the results are well placed in the context of previous works. It is obvious that the authors are very familiar with the topic. The connection with prediction with expert advice is interesting.", "weaknesses": "The contribution is more technical than conceptual. Many of the proof techniques are extensions of previous work, but the work is honest about it. The relationship between mistake bounds and regret bounds for the same setting could have been fleshed out better. It would be useful to mention absolute (as opposed to relative) upper and lower bounds on the various $\\mathrm{opt}(\\mathcal{H})$ whenever they are available.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to weakness:\n\nThe main goal of the paper is to measure the role of natural and well-studied  resources given to the learner/adversary, and such bounds are inherently relative. However, it is well-known that  $\\mathsf{opt}_{\\operatorname{full}}^{\\operatorname{det}}(\\mathcal{H})$ (and up to a factor of $2$ also its randomized parallel)\nis exactly quantitatively characterized by the Littlestone dimension [1,2], which is a combinatorial dimension depending only on the class $\\mathcal{H}$. Therefore, the bounds of Theorem 1.1 can be seen as absolute, and we agree that we should clarify it in the paper. Further, the upper bounds in Theorem 1.2 and 1.4  are also absolute,  as witnessed by Equation (1). The absolute bounds implying the lower bound of Theorem 1.2 are explicitly written in lines 93-97. The absolute bounds implying the lower bound of Theorem 1.4 are explicitly stated and proved in Appendix F (Theorem F.1). In the next version of the paper, we will add the statement of Theorem F.1 to the main text.\n\n\nResponse to question #1:\n\nThe relationship between a mistake bound and its matching regret bound is “regret bound = mistake bound - $r$”, where $r$ is the number of mistakes made by the best hypothesis in class. Therefore, every mistake bound can be converted to a regret bound and vice versa, via this equation. We will add this formal equation to the paper, to make this relationship more clear.\n\n\nResponse to question #2:\n\nSee response to weakness.\n\n\nReferences:\n\n[1] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold 390 algorithm. Machine learning, 2(4):285–318, 1988.\n\n[2] A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass learnability and the erm principle. In COLT, 2011.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for taking the time to carefully read our work, and for their thoughtful comments and suggestions to improve it. We will make our best efforts to incorporate their valuable suggestions in the next version of this paper. We respond to specific issues raised by each reviewer in a comment to each review.

Meta-review: This paper makes solid contribution. Please improve clarity by incorporating reviewer's comments.
Decision: Accept (poster)