Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs

Authors: yuval  filmus
steve  hanneke
idan  mehalel
shay  moran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 08:54:49

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.

Main paper: 
 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 a learner and an adversary. Each round t in the game proceeds as follows:(i) The adversary sends an instance x t ∈ X to the learner. (ii) The learner predicts ŷt ∈ Y (possibly at random). (iii) The adversary provides information (feedback) to the learner. This problem suggests a 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 we 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 y t at the end of every round. Bandit feedback means that the learner only receives an indication whether ŷt = y t or not. If the learner predicts ŷt deterministically for every t, 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, we discuss these questions and present our results.We assume that a concept class H ∈ Y X is given, where X is a domain of instances and Y is a label set. 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 rand full (H) denote the optimal mistake bound for H achievable with full-information feedback. Let opt det full (H) denote the same as opt rand full (H), with the additional restriction that the learner is deterministic. In the bandit feedback model, define opt det bandit (H) analogously to opt det full (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). 1 Therefore, we define the notations opt obl bandit (H) and opt adap bandit (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 Ω notations hide universal constants that do not depend on any parameter of the problem.In the full-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 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-David, and Shalev-Shwartz [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 opt det bandit (H) = O(opt det full (H) • |Y| log |Y|)(1) for every concept class H. A matching lower bound was given in [Long, 2020 , Geneson, 2021] , which showed that for every natural k ≥ 2 there exists a concept class H with label set of size |Y| = k such that opt det bandit (H) = Ω(opt det full (H) • |Y| log |Y|).(2) They also find tight guarantees on the constants hidden in the O, Ω notations.Finding an analogous result for randomized learners was raised as an open problem in [Daniely and Helbertal, 2013] . 2 We solve this open problem by proving the upper bound stated in the following theorem. Theorem 1.1 (Full-information vs. Bandit-feedback). For every concept class H it holds that opt adap bandit (H) = O(opt rand full (H) • |Y|). Furthermore, for every natural k ≥ 2 there exists a concept class H with |Y| = k such that opt obl bandit (H) = Ω(opt rand full (H) • |Y|).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 rand full (H) is precisely characterized by a combinatorial parameter of H called the randomized Littlestone dimension [Filmus, Hanneke, Mehalel, and Moran, 2023] (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 1.2, and a technical overview of the proof can be found in Section 2.A generalization to the agnostic setting. We also generalize results in the spirit of Theorem 1.1 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 ≥ r ⋆ on it) is given to the learner. However, throughout most of the paper we assume the stronger r-realizability assumption, in which an upper bound r ≥ 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 at most r 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 1 .In the agnostic setting, learning algorithms are often measured by their expected regret (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 at least as large as its regret. Therefore, since our bounds demonstrate no dependence on the number of rounds T , in some cases they provide improvements over the known regret bound Õ T |Y|opt det full (H) of [Daniely and Helbertal, 2013] . Specifically, when r ⋆ = O(opt det full (H)), our results imply a regret bound of O(|Y|opt det full (H)), for all T .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: an oblivious adversary which must decide on the entire input in 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. 1 : 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 r ⋆ is required. The bounds for the randomized setup are obtained by applying Theorem D.3 to the upper bound in Theorem D.1 and to the lower bounds in Lemma C.11 and in [Daniely and Helbertal, 2013] . The bounds for the deterministic setup are obtained by applying the same theorem to the upper bound of Auer and Long [1999] , and to the lower bounds of Lemma C.5 and Long [2020] . The same (up to constant) deterministic bounds were proved independently in [Geneson and Tang, 2024] (however, their bounds are in terms of a given bound r ≥ r ⋆ ). The upper bound is an immediate corollary of the upper bound (1). We prove the lower bound in Section E. The proof idea of the lower bound is to consider the classic adversarial |Y|-armed bandit problem of Auer, Cesa-Bianchi, Freund, and Schapire [2002] with an r-realizability assumption. This setting can be simulated using a pattern class, but not using a concept class. For this problem, an adaptive adversary can force a mistake bound of Ω(r • |Y|), while the best an oblivious adversary can do is O(r + |Y|).Remark 1.3 (Concept classes vs. Pattern classes). Pattern classes are a more expressive generalization of concept classes (see a formal definition in Section A). Most desirably, we 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 in all of our results (for the sake of simplicity, we omitted it from the theorem statements), except for Theorem 1.2, in which the upper bound does hold for all pattern classes, but the lower bound holds only for hard pattern classes.In Section 1.1.2 we discussed two different adversarial models within the setup of 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 H with |Y| = 2 it holds thatEQUATIONand that there are classes attaining each equality. Extending this to |Y| > 2 is straightforward by noting the following randomized-to-deterministic full-information algorithm conversion: If A is a randomized algorithm, then the mistake bound of 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, A makes a mistake with probability at least 1/2. This raises the following natural question, also asked in [Daniely and Helbertal, 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. (H) = d + 1. 2. opt det bandit (H) = Θ(d • k). 3. opt adap bandit (H) = Θ(d + k).The lower bound in Theorem 1.4 has a significant consequence on the problem of finding a combinatorial 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-Shwartz, 2015] , a new combinatorial dimension, coined the Bandit-Littlestone dimension, is introduced and proved to capture the exact optimal mistake bound of deterministic learners within the bandit feedback model. In [Daniely and Helbertal, 2013] , 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 F, the classes used in the lower bound may be chosen such that opt adap bandit (H) = O(|Y|), and thus opt adap bandit (H) is only roughly opt det bandit (H). On the other hand, the upper bound in Theorem 1.4 together with the bound opt obl bandit (H) ≥ |Y|-1 2 (e.g. by Daniely and Helbertal [2013] )shows that opt det bandit (H) is roughly the smallest that opt obl bandit (H) can get.A main technical result proved in this work, which is interesting in its own right, is 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 it is promised that the best expert is inconsistent with the feedback for at most r many times throughout the entire game.As in Section 1.1.1, 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 (|Y| = 2) setting, starting with the seminal works of Vovk [1990] , Littlestone and Warmuth [1994] who showed that the optimal mistake bound when |Y| = 2 is Θ(log n + r) for both randomized and deterministic learners. Later, Cesa-Bianchi, Freund, Helmbold, and Warmuth [1996] proved fine-grained bounds for deterministic learners. Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire, and Warmuth [1997] , Abernethy, Langford, and Warmuth [2006] , Filmus,Randomized The main tool used to prove Theorem 1.1 is the following optimal (up to constant factors) bound on opt adap bandit (n, k, r), which is the optimal mistake bound achievable by a randomized learner which plays against an adaptive adversary that provides bandit feedback, when there are k ≥ 2 many labels, n ≥ k many experts, and the best expert is inconsistent with the feedback for at most r ≥ 0 many times. Theorem 1.6. For every n ≥ k ≥ 2 and r ≥ 0 it holds thatO(k(log k n + r ⋆ )) Ω(k log k n + r ⋆ ) Θ(k(log k n + r ⋆ )) Deterministic Θ(k(log(n/k) + r ⋆ + 1))opt adap bandit (n, k, r) = Θ(k(log k n + r)).This bound generalizes the result opt adap bandit (n, 2, r) = Θ(log n + r) mentioned above. 3 In the case where the adversary is oblivious, we prove the inferior lower bound opt obl bandit (n, k, r) = Ω(k log k n + r) which is tight as long as r = O(log k n). Proving tight bounds against an oblivious adversary for all values of r remains open.We also consider this problem in the deterministic (learner) setting, for the sake of completeness (we do not use the deterministic bound to prove any other results). We prove all bounds in Section C, and summarize them in Table 2 . Similarly to the results in Section 1.1.1, since our mistake bounds demonstrate no dependence on the number of rounds T , they improve over the known regret bound O √ T k log n of Auer, Cesa-Bianchi, Freund, and Schapire [2002] whenever r = O(log n). 
technical overview: 
 In this section, we explain the idea behind the proof of the upper bound opt 2), which we do in the following subsections. Of the two items, the proof of Item (2) is the main technical novelty.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 expert 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 an instance of prediction with expert advice with |Y| opt det full (H) many experts, |Y| many labels, and where the best expert is inconsistent with the feedback for at most opt det full (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 A arranged in tree form. These copies will function as the experts fed into an optimal algorithm for prediction with expert advice.Initially, there is a single copy of A. At 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 det full (H), we split it into |Y| different copies at depth D + 1, 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 det full (H), there are at most |Y| opt det full (H) many copies of A. The copy of A which always guessed correctly corresponds to an expert whose predictions are inconsistent with the feedback for at most opt det full (H) many rounds. A formal statement (and proof) of this reduction can be found in Proposition D.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 on opt adap bandit (n, k, r) stated in Theorem 1.6, we first outline a proof for the upper bound on opt adap bandit (n, k) := opt adap bandit (n, k, 0). This proof has the same flavor of the proof for general r, but is simpler. We then explain how to 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 k ≥ 2, and for every n ≥ 1, let V (n) = opt adap bandit (n, k). We haveEQUATIONwhere ⃗ α ∈ [0, 1] k is a k-ary vector whose y'th entry specifies the fraction of living experts predicting y; π is the distribution used by the learner to draw the prediction; and y ∈ Y is the correct label chosen by the adversary. 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 (4) results in the recurrence relationV (n) ≤ V (n/k)/k + (1 -1/k)(1 + V ((1 -1/k)n)).(5)Solving this recurrence relation givesV (n) ≤ k log b(k) n, where b(k) = k k (k-1) k-1, which implies the statement in Theorem 1.6 since b(k) ≥ 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 V (n), as defined in (4), satisfies V (n) ≤ k log b(k) n by induction on n. However, note that (4) contains k different recursive calls, so an inductive proof seems complicated. To overcome this, we use minimax duality, which significantly simplifies (4), as we now explain.Observe that once ⃗ α is fixed, each round of the game is a zero-sum game between two randomized parties. 4 Therefore, we can apply von Neumann's minimax theorem and obtain a dual game which is equivalent to the primal (original) game in terms of its optimal mistake bound. 5 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 ofEQUATION)The notation is the same as in ( 4), except that now π is the distribution used by the adversary to draw the correct label, and y ∈ Y is the learner's prediction. Eq. ( 6) contains only two recursive calls, making an inductive proof much easier (but still quite technical).We now explain how to adapt this approach to work for general r, when r 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 a different number of rounds, and so can afford a 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-Bianchi 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 to 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) a potential of k 2i . 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 a result, the initial number of living experts n is replaced with the initial total potential n • k 2r , which givesV (n • k 2r ) ≤ k log k (n • k 2r ) = k log k n + 2kr,as stated in Theorem 1.6. 
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 role of information in learning concept classes was previously studied in [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, 1999] was the first to show that opt det bandit (H) = O(opt det full (H)|Y| log |Y|) for every class H. Long [2020] , Geneson [2021] improved the constant in the upper bound of Auer and Long [1999] , and showed that it is in fact tight up to a 1 + o(1) factor by finding a sequence of concept classes demonstrating a matching separation between opt det bandit (H) and opt det full (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 Õ T |Y|opt det full (H) on the optimal regret, where T is the horizon, and showed that the upper bound is best-possible up to logarithmic factors. The PAC learning setting was studied in [Daniely, Sabato, Ben-David, and Shalev-Shwartz, 2015] , which showed that the price of bandit feedback is Õ(|Y|) in this setting as well.In the setting of full-information feedback, adaptive and oblivious adversaries are essentially equivalent [Cesa-Bianchi and Lugosi, 2006, Lemma 4.1] . Indeed, full-information feedback, in its essence, implies that the feedback never depends on the prediction drawn by the learner in a 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 [Merhav, Ordentlich, Seroussi, and Weinberger, 2002 , Farias and Megiddo, 2006 , Arora, Dekel, and Tewari, 2012] .In the full-information feedback model, the Littlestone dimension [Littlestone, 1988, Daniely, Sabato, Ben-David, and Shalev-Shwartz, 2015] captures opt det full (H) precisely, and opt rand full (H) up to a multiplicative factor of 2. The paper [Daniely et al., 2015] suggests a new combinatorial dimension, the Bandit Littlestone dimension, and proves that it captures opt det bandit (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 |Y| = ∞.The papers [Daniely and Helbertal, 2013, Raman et al., 2023] ask whether the Bandit Littlestone dimension is a good quantitative proxy for opt obl bandit (H). Theorem 1.4 (and Theorem F.1 in a more detailed version) shows that this dimension is far from quantifying even opt adap bandit (H).The problem of prediction with expert advice in the r-realizable setting was introduced in [Vovk, 1990, Littlestone and Warmuth, 1994] for the binary case (|Y| = 2). Since then, this problem has been well-studied, with papers spanning the past 30 years [Cesa-Bianchi, Freund, Helmbold, and Warmuth, 1996 , Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire, and Warmuth, 1997 , Abernethy, Langford, and Warmuth, 2006 , Mukherjee and Schapire, 2010 , Filmus, Hanneke, Mehalel, and Moran, 2023 ]. The full-information setting for |Y| > 2 and small r was studied in [Brânzei and Peres, 2019] .The bandit feedback variation of the problem was introduced in [Auer, Cesa-Bianchi, Freund, and Schapire, 2002] , in a 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 at 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.1 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 r; our bounds for the adaptive setting are tight in the oblivious setting only for small r values (see Theorem C.12).Unfortunately, to the best of our knowledge, when converting rewards to losses and applying the bounds of Auer, Cesa-Bianchi, Freund, and Schapire [2002] , a dependence on the number of rounds T emerges (see for example [Bubeck and Cesa-Bianchi, 2012, Theorem 3.1] and [Cesa-Bianchi 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 1.1, 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 of r.4 Open questions and future workOur work leaves some interesting open questions and directions for future work. 
open questions: 
 The price of adaptivity for concept classes. Our proof of Theorem E.1 uses pattern classes. Can we prove it using only concept classes, similarly to Theorem F.1? If not, what is the price of adaptivity when learning concept classes?The exact role of randomness. There is a Θ(log k) gap between the lower and upper bounds in Theorem 1.4. What is 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 a concept class (Table 1 ), and for prediction with expert advice (Table 2 ). It would be interesting to obtain bounds that are tight for large r ⋆ against an 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-Bianchi, 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 to many learning algorithms that integrate the weights into the prediction process (See [Cesa-Bianchi and Lugosi, 2006 , Section 2.1] and bibliographic remarks in Section 2). Can we design a natural algorithm, in the spirit of algorithms such as weighted majority [Littlestone and Warmuth, 1994] and Exp4 [Auer, Cesa-Bianchi, Freund, and Schapire, 2002] , that achieves the guarantees of Theorem C.7, up to constant factors?The multilabel setting. It would be interesting to generalize the results of this work to the multilabel setting considered in [Daniely and Helbertal, 2013] , in which the adversary is allowed to choose several correct labels in each round. When the adversary is adaptive, it is not hard to see that this is equivalent to the single-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 y and the prediction is z, the adversary provides the feedback op ∈ {<, = , >} such that z op y. An interesting direction for future research is to prove results in the spirit of this work for comparison feedback, or for other natural types of feedback.Let X be a domain, and let Y be a countable label set. Unless stated otherwise, we assume that Y = [k] for some natural k ≥ 2. A pair (x, y) ∈ X × Y is called an example, and an element x ∈ X is called an instance or an unlabeled example. A function h : X → Y is called a hypothesis or a concept. A hypothesis class, or concept class, is a non-empty set H ⊂ Y X . We note here that it is generally assumed that there exists an instance x ∈ X such that for every y ∈ Y there exists h ∈ H satisfying h(x) = y. This assumption is reasonable since when this is not the case, the hypothesis class H has an essentially isomorphic class H ′ with label set strictly smaller than Y (see [Raman, Raman, Subedi, Mehalel, and Tewari, 2023] ).We will mostly consider the more general notion of pattern classes. A pattern p ∈ (X × Y) ⋆ is a finite sequence of examples. A pattern class is a non-empty set of patterns P which is downwards closed, meaning that for every p ∈ P, every sub-pattern p ′ of p (obtained by removing examples arbitrarily) is in P as well. Let p, q be sequences (which can be either patterns or some other type of sequences). we denote by p I the sub-sequence of p consisting only of the indices in I. The set I might be given by a clear and well-known notation. For example, if p = x 1 , . . . , x T , then for some t ≤ T , the notation p ≤t represents the sub-sequence x 1 , . . . , x t . Denote the concatenation of p, q by p • q. If p is a sub-sequence of q, we denote p ⊂ q.Note that pattern classes generalize concept classes: for every concept class H we may define the induced pattern classEQUATIONIn 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 a repeated game between a learner and an adversary. Each round t in the game proceeds as follows:(i) The adversary sends an instance x t ∈ X to the learner.(ii) The learner predicts ŷt ∈ Y (possibly at random).(iii) The adversary provides (full-information or bandit) feedback to the learner.Full-information feedback means that the learner learns the correct label y t at the end of every round.Bandit feedback means that the learner only receives an indication whether ŷt = y t or not. If the learner predicts ŷt deterministically for every t, then the learner is deterministic.In the bandit feedback setting, we model learners as functions Lrn :((X × {→, ̸ →} × Y) ⋆ × X ) → Π[Y]from the set of pairs of a feedback sequence and an instance, to the set Π[Y] of all probability distributions over Y. For π ∈ Π[Y] we denote the probability of y in π by π y . In a feedback sequence (x 1 , op 1 , ŷ1 ), . . . , (x T , op T , ŷT ), the triplet (x t , op t , ŷt ) represents the fact that in round t the instance was x t , and that ŷt = y t if op =→, or ŷt ̸ = y t 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 so we omit it and use the pair (x t , y t ) instead of the triplet (x t , op, ŷt ).Given a learner Lrn and a fixed input sequence of examples S = (x 1 , y 1 ), . . . , (x T , y T ), we denote the expected number of mistakes that Lrn makes when executed on the sequence S by M full (Lrn; S) if it receives full-information feedback, and by M bandit (Lrn; S) if it receives bandit feedback. We define the optimal mistake bound of P when the adversary is oblivious to beEQUATIONin the full information and bandit feedback models, respectively. Remark A.1 (Strong vs. Weak Realizability). The restriction S ∈ P that the supremum is taken over is called strong realizability, which requires that the input sequence is taken from the class P. On the other hand, unless stated otherwise, in this work we consider the weak realizability assumption.Under this assumption, it 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 S is chosen beforehand, strong and weak realizability coincide. Indeed, note that for any learner who never predicts a label with probability 0, 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 ∈ P before the beginning of the game. In contrast, in the setting of the bandit feedback model we will also consider a stronger adaptive adversary which is allowed to choose the target pattern on the fly, as long as it satisfies the weak realizability assumption, meaning that the feedback provided to the learner is consistent with some p ∈ P with probability 1. In addition, it is allowed to choose the correct label at random. 6When the adversary is adaptive, the online learning game defined above operates as follows in every round t:(i) The adversary sends an instance x t ∈ X to the learner.(ii) The learner chooses a probability distribution π (t) over Y and reveals it to the adversary.(iii) The adversary chooses a probability distribution τ (t) over Y.(iv) The learner draws a prediction ŷt ∈ Y from π (t) and reveals it to the adversary.(v) The adversary draws the correct label y t from τ (t) and tells the learner if its prediction was correct or not.We formalize an adaptive adversary as a pair of functionsAdv x : (X × {→, ̸ →} × Y) ⋆ → X , Adv y : (X × {→, ̸ →} × Y) ⋆ × X × Π[Y] → Π[Y].In every round t, Adv x is used in the first step to choose the instance x t , and Adv y is used in the third step to determine the distribution from which the correct label y t ∈ Y is drawn. In more detail, let F ∈ (X × {→, ̸ →} × Y) ⋆ be the feedback sequence given to the learner before round t. The adversary sends the instance x t = Adv x (F ) to the learner in the first step. In the third step, the adversary computes the distribution τ (t) = Adv y (F, x t , π (t) ).A feedback sequence F ∈ (X × {→, ̸ →} × Y) ⋆ 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 ∈ (X × {→, ̸ →} × Y) ⋆ which is realizable by P and for every π ∈ Π[Y], the following holds. Let x = Adv x (F ). If Adv y (F, x, π) = τ , then the feedback sequence F • (x, →, y) is realizable for every y in the support of τ .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 M bandit (Lrn; Adv). We define the optimal mistake bound of P against an adaptive adversary which provides bandit feedback byEQUATIONwhere the supremum is taken over all adaptive adversaries which are consistent with P.We denote by opt det full (P) and opt det bandit (P) the optimal deterministic mistake bounds7 of P with full-information 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, Ω, Θ hide universal constants which do not depend on any parameter of the problem.In this section we describe a game-theoretic formulation of opt adap bandit , 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 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 x t , in the primal game the learner chooses a 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 x t ∈ X and a probability distribution τ (t) over Y. It reveals both to the learner.(ii) The learner chooses a probability distribution π (t) over Y, draws a prediction ŷt ∈ Y from π (t) , and reveals it to the adversary.(iii) The adversary draws the correct label y t from τ (t) 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 is 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 in 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 are [Abernethy, Agarwal, Bartlett, and Rakhlin, 2009 , Rakhlin, Sridharan, and Tewari, 2010 , Rakhlin, Shamir, and Sridharan, 2012] .We now get into the details. In the dual game, π (t) depends on the distribution τ (t) chosen by the adversary, and the distribution τ (t) does not depend on the distribution π (t) . 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 × {→, ̸ →} × Y) ⋆ → (X × Π[Y]). The learner is defined as a functionLrn : (X × {→, ̸ →} × Y) ⋆ × X × Π[Y] → Π[Y].The optimal mistake bounds in the primal and dual games are defined in a dual manner: opt adap bandit (P) = infFirst, we provide explicit definitions for opt adap bandit (P) and opt_d adap bandit (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 x = {p ∈ P : (x, y) • p ∈ P for some y ∈ Y}.Additionally, define the following classes for every pair of an instance and a label (x, y):P x→y = {p ∈ P : (x, y) • p ∈ P}, P x̸ →y = P x \P x→y .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 opt adap bandit (P) and opt_d adap bandit (P) in terms of classes of the form P x→y and P x̸ →y :opt adap bandit (P) = sup For these equations to be well-defined, it is technically convenient to define opt adap bandit (∅) = opt_d adap bandit (∅) = -∞. 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 equivalence.Lemma B.1. For every pattern class P: opt adap bandit (P) = opt_d adap bandit (P).Proof. For a horizon (number of rounds) T , let opt adap bandit (P, T ), opt_d adap bandit (P, T ) be the analogue notations to opt adap bandit (P), opt_d adap bandit (P), with the additional restriction that the game is played for T rounds. We adapt ( 11) and ( 12) to those definitions in the obvious way. Note thatopt adap bandit (P) = sup T ∈N,x∈Xopt adap bandit (P x , T ), and similarly for opt_d adap bandit (P). Therefore, to prove the lemma, it suffices to show that opt adap bandit (P x , T ) = opt_d adap bandit (P x , T ) for all x, T such that P x ̸ = ∅ (when P x = ∅ both are -∞ for all T ). Let x ∈ X be such that P x ̸ = ∅. For T = 0 we have opt adap bandit (P x , 0) = 0 = opt_d adap bandit (P x , 0). For the induction step, note that the expression for opt_d adap bandit (P x , T ) suggested by ( 12) describes a 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 in the sequel, after the distributions are fixed. The adversary's goal is to maximize it and the learner's goal is to minimize it. Since this is a zero-sum game, by the minimax theorem [von Neumann, 1928] we can let the learner go first instead, without changing the value of opt_d adap bandit (P x , T ). Therefore we can write opt_d adap bandit (P x , T ) as:inf π sup y∈Y   π y • opt_d adap bandit (P x→y , T -1) + y ′ ̸ =y π y ′ (1 + opt_d adap bandit (P x̸ →y ′ , T -1))   .By the induction hypothesis, we can change every opt_d adap bandit to opt adap bandit , which gives: By applying (13), observe that opt_d adap bandit (P x , T ) = opt adap bandit (P x , T ), as required.The optimal randomized algorithm achieving opt adap bandit (P) suggests itself from (11). For completeness, we explicitly write it in Figure 1 . 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 r many indices. Proposition B.2. The algorithm BanditRandSOA is well-defined and optimal.Proof. The choice of π (t) is well defined because ( 14) is a feasible linear optimization problem, and as such it has a solution. The algorithm is optimal due to (11).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 it is promised that the best expert is inconsistent with the adversary's feedback in at most r 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 a 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 BanditRandSOA Input: A pattern class P.For t = 1, 2, . . . (14) 3. Draw the prediction ŷt from π (t) . 4. If the feedback is positive, update P := P x→ŷt , and otherwise update P := P x̸ →ŷt .1. Receive instance x t ∈ X . 2. Construct a distribution π (t) such that π (t) ∈ arg min π∈Π[Y]Figure 1 : 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 is a randomized variant of Littlestnoe's [Littlestone, 1988] well-known SOA algorithm.the binary or 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, 1994 , Cesa-Bianchi, Freund, Helmbold, and Warmuth, 1996 , 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 we prove for it plays a central role in the proof of Theorem 1.1. 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 many labels and n ≥ k many experts, where the best expert is inconsistent with the feedback in at most r ≥ 0 many rounds. We assume that n ≥ k, since if n < k then having k labels is equivalent to having n labels. When the learner is deterministic, the optimal mistake bound is denoted by opt det bandit (n, k, r). When the learner is randomized, the optimal mistake bound is denoted by opt obl bandit (n, k, r) or opt adap bandit (n, k, r), depending on whether the adversary is oblivious or adaptive, respectively. For the realizable case r = 0, we omit r from the notation.In this section, we analyze opt det bandit (n, k, r) and prove the following theorem. Theorem C.1. Let n ≥ k ≥ 2, r ≥ 0. Then:opt det bandit (n, k, r) = Θ(k(log(n/k) + r + 1)).We first prove the upper bound and then the lower bound.Lemma C.2. Let n ≥ k ≥ 2, r ≥ 0. Then for every α > 1:opt det bandit (n, k, r) ≤ α α -1 k ln(n • α r /k) + k -1.Proof. We describe a deterministic learner which makes at most the stated number of mistakes. We use a simple generalization of Weighted Majority [Littlestone and Warmuth, 1994] . A similar idea appears also in [Long, 2020] .Every expert is given an initial weight of α r . Let W t 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 α. If an expert reaches weight less than 1, we reduce its weight to 0, since it must mean that it made more than r mistakes. We split the analysis into two epochs. The first epoch is as long as W t > k, and the second is afterwards.We begin by analyzing the first epoch. By assumption, W t > 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 α. Therefore, if a mistake occurs in round t thenW t+1 ≤ (1 -1/k)W t + W t /(αk) = 1 - α -1 αk W t .Now, if m 1 is the total number of mistakes the learner makes as long as W t > k, then m 1 must satisfyk < n • α r 1 - α -1 αk m1 ≤ n • α r e -m1 α-1 αk .After some manipulations, we derive the boundm 1 < αk α -1 ln(n • α r /k).We now analyze m 2 , which is the number of mistakes in the second epoch. If W t ≤ k then there are at most k experts which have not yet made more than r mistakes. At least one of them will never err again, and therefore in the worst case, the learner will make m 2 ≤ k -1 more mistakes before eliminating all experts apart from the target expert. Summing m 1 + m 2 gives the stated bound.We may now deduce the upper bound.Corollary C.3. Let n ≥ k ≥ 2, r ≥ 0. Then: opt det bandit (n, k, r) ≤ e e -1 k(ln(n/k) + r) + k -1.Proof. Apply Lemma C.2 with α = e.We can also deduce an improved upper bound for the realizable (r = 0) case.Corollary C.4. Let n ≥ k ≥ 2. Then:opt det bandit (n, k) ≤ k ln(n/k) + k -1.Proof. We can easily see that opt det bandit (n, k) ≤ (1 + ϵ)k ln(n/k) + k -1 for every ϵ > 0 by applying Lemma C.2 with α → ∞. There is also an explicit optimal learner for which this holds with ϵ = 0, obtained by slightly changing the proof of Lemma C.2.We now turn to the lower bounds. We begin with the realizable case. Lemma C.5. Let n ≥ k ≥ 3. Then:opt det bandit (n, k) ≥ (k/2 -1) ln(n/k).Proof. The adversary uses the following simple strategy. Let n t 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 as n t > k, in every round t the adversary splits the alive experts as evenly as possible among the k labels, and gives negative feedback to the learner. Note that the largest set in the partition consists of ⌈n t /k⌉ ≤ n t /k + 1 < 2n t /k experts, since n t > k. Therefore, in every round at least a (1 -2/k)-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 -2/k) m-1 n > k, which holds if e -2 k-2 (m-1) n > k,by using the inequality 1 -x > e -x x-1 that holds for all x < 1. After some manipulations, the inequality reads m ≤ (k/2 -1) ln(n/k) + 1, which implies the stated bound.To devise a lower bound for the r-realizable setting, we prove the following lemma. It was independently proved also by Geneson and Tang [2024] .Lemma C.6. For every n ≥ k ≥ 2, r ≥ 0 we have:opt det bandit (n, k, r) ≥ k(r + 1) -1.Proof. Suppose that there are n = k experts. In every round for T = k(r + 1) -1 rounds, the adversary lets expert i 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 ′ ̸ = i ⋆ . Since T = k(r +1)-1, it must hold that i ⋆ is predicted by the learner at most r times. In every round in which the learner predicts i ⋆ , set the true label to i ′ . In all other rounds set the true label to i ⋆ . By definition of the strategy, the best expert makes at most r mistakes.We may now prove Theorem C.1.Proof of Theorem C.1. The stated bounds are known when k = 2 by e.g. [Vovk, 1990, Littlestone and Warmuth, 1994] . For k ≥ 3, the upper bound follows from Corollary C.3, and the lower bound follows from Lemmas C.5 and C.6.In this section we provide a tight upper bound on opt adap bandit (n, k, r) by proving the following theorem. Theorem C.7. Let n ≥ k ≥ 2, r ≥ 0. Then:opt adap bandit (n, k, r) ≤ k log k n + 2kr.We will prove the theorem by analyzing the mistake bound of the equivalent dual game, as described in Section B. The primal and dual games are described in Section B in terms of pattern classes, so we first show that the problem of prediction with expert advice in the r-realizable setting is in fact equivalent to learning an appropriate specific pattern class.For every hypothesis class H and budget function B : H → R, we define the pattern classEQUATIONIn words, P(H, B) consists precisely of those patterns which are consistent with some h ∈ H everywhere except for at most B(h) many places. We call B(h) the budget of h. Therefore, if B r is the budget function that gives budget r to all hypotheses, then learning the pattern class P(H, B r ) under the assumption of realizability is equivalent to learning the hypothesis class H under the assumption of r-realizability.Observe that for a fixed number of labels k, the class of n experts is simply the hardest concept class of size n, since every expert can predict any label in every round. Denote this class by U n,k , so that prediction with expert advice with n experts and k labels in the r-realizable setting is equivalent to learning the pattern class P(U n,k , B r ) under the assumption of realizability. Therefore, we haveopt adap bandit (n, k, r) = opt adap bandit (P(U n,k , B r )) = opt_d adap bandit (P(U n,k , B r )) due to Lemma B.1.For completeness, we formally define U n,k . This is the class of projection functions over the set of k-ary vectors of length n, X = [k] n . That is, if the n functions are {h 1 , . . . , h n } then for every x ∈ X we have h i (x) = x i , where x i is the value of the i'th entry of x.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 of 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 ≤ i ≤ r. Following [Abernethy, Langford, and Warmuth, 2006, Brânzei and Peres, 2019] , we represent this information by an (r + 1)-ary vector ⃗ m = (m 0 , . . . , m r ), in which the number m i indicates the number of living experts with budget i. We call this vector the state of the game.For any state ⃗ m, let V ( ⃗ 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, ifP(U n,k , B ⃗ m ) is the pattern class representing the state ⃗ m, then V ( ⃗ m) = opt_d adap bandit (P(U n,k , B ⃗ m )). We call V ( ⃗ m) the value of the state ⃗ m.The goal is thus to upper bound the value of the initial state V (0, 0, . . . , n).Towards this end, we use the following potential-based technique. An expert with budget i will have a potential of k 2i . This will allow us to bound V ( ⃗ m) in terms of the total potential of the experts, given byW ( ⃗ m) = r i=0 m i • k 2i . Let b(k) = k k (k-1) k-1 .We will prove the the following. Lemma C.8. Let k ≥ 2 be the number of labels. For any state ⃗ m it holds thatV ( ⃗ m) ≤ k • log b(k) 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 letf k (β) := log b(k) (((1 -β)/k 2 + β)(β/k 2 + (1 -β)) k-1 ) -1/k. Then f k (β) ≤ -1 for all β ∈ [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, 0, . . . , 0) is the lowest, and the state (0, . . . , 0, n) is the highest.In order to be able to always apply the induction hypothesis, we must assume that the state always 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 can always be applied.In the base case, ⃗ m = (1, 0, . . . , 0). ThereforeV ( ⃗ m) = 0 = k log b(k) 1 = k log b(k) 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 τ . Let V y ( ⃗ m) be the optimal number of mistakes made by the learner if it predicts y when the state of the game is ⃗ m. Let ⃗ m →y be the state of the game in the next round, if in the current round the correct label is y. Define ⃗ m ̸ →y in a similar way. Using (12), we may now writeV y ( ⃗ m) = τ y V ( ⃗ m →y ) + (1 -τ y )(1 + V ( ⃗ m ̸ →y )).Since the learner is allowed to predict any y ∈ Y (and specifically the y which minimizes V y ( ⃗ m)), it suffices to bound V y ( ⃗ m) for some y of our choice. We now consider two cases.Case 1. Suppose that there exists y ∈ Y which satisfiesV ( ⃗ m →y ) ≥ 1 + V ( ⃗ m ̸ →y ).Then:V y ( ⃗ m) ≤ V ( ⃗ m →y ) ≤ k log b(k) W ( ⃗ m →y ) ≤ k log b(k) W ( ⃗ m)by the induction hypothesis, concluding the first case.Case 2. Suppose that for every y ∈ Y,EQUATIONLet β ∈ [0, 1] be the fraction of experts predicting y, weighted according to their potential. If the true label is y then a β-fraction of the potential W ( ⃗ m) is untouched, and a (1 -β)-fraction is multiplied by at most 1/k 2 (experts with budget 1 have their potential multiplied by 0), and soW ( ⃗ m →y ) ≤ ((1 -β)/k 2 + β)W ( ⃗ m). Similarly, W ( ⃗ m ̸ →y ) ≤ (β/k 2 + (1 -β))W ( ⃗ m). Plugging this into (16), we have V y ( ⃗ m) ≤ 1 -1/k + log b(k) ((1 -β)/k 2 + β)W ( ⃗ m) + (k -1) log b(k) (β/k 2 + (1 -β))W ( ⃗ m), which after a bit of manipulation reads asV y ( ⃗ m) ≤ k log b(k) W ( ⃗ m) + 1 + log b(k) (((1 -β)/k 2 + β)(β/k 2 + (1 -β)) k-1 ) -1/k. To finish the proof, it remains to show that f (β) := log b(k) (((1 -β)/k 2 + β)(β/k 2 + (1 -β)) k-1 ) -1/kis bounded from above by -1 for all β ∈ [0, 1], which is the statement of Lemma C.9.We can now prove Theorem C.7.Proof of Theorem C.7. Clearly b(k) ≥ k. Applying Lemma C.8 on the initial state ⃗ m = (0, . . . , 0, n), we getopt adap bandit (n, k, r) = opt_d adap bandit (P(U n,k , B r )) = V (0, . . . , 0, n) ≤ k log b(k) (n•k 2r ) ≤ k log k n+2kr, as desired.In this section we prove Lemma C.9. Let us first restate it in a more convenient way. Defineg k (β) = 1 -β k 2 + β β k 2 + 1 -β k-1.The lemma states that for all k ≥ 2 and β ∈ [0, 1], we haveg k (β) ≤ b(k) 1/k-1 , where b(k) = k k (k -1) k-1 .Routine calculation shows thatg ′ k (β) = β k 2 + 1 -β k-1 1 k 2 1 - 1 k 2 k 2 -k + 1 -(k 3 -k)β . It follows that g k (β) is maximized at β k = k 2 -k + 1 k 3 -k ,at which point its value isg k (β k ) = (k 2 + 1)(k -1) k-1 k 3k .Therefore we need to show that for all k ≥ 2, (k2 + 1)(k -1) k-1 k 3k ≤ b(k) -(1-1/k) = (k -1) (k-1)(1-1/k) k k-1 .Rearranging, we need to show that (k 2 + 1)(k -1) (k-1)/k ≤ k 2k+1 . This holds since k 2 + 1 ≤ 2k 2 ≤ k 3 ≤ k 2k and (k -1) (k-1)/k ≤ k. i ⋆ , which predicts i ⋆ in all rounds. The adversary is thus r/2-consistent on rounds where the learner is 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 a lower bound also against an oblivious adversary. However, it is not possible; as we show in Proposition E.2, it holds that opt obl bandit (k, k, r) = Θ(k + r) for all k ≥ 2, r ≥ 0. The essential reason allowing Proposition E.2 is that an oblivious adversary must be r-realizable in a strong sense, as discussed in Remark A.1.We can now deduce tight bounds on opt adap bandit (n, k, r), and bounds on opt obl bandit (n, k, r) which are tight in the regime r = O(log k n). Theorem C.12. Let n ≥ k ≥ 2, r ≥ 0. Then opt adap bandit (n, k, r) = Θ(k(log k n + r)). Furthermore, if r ≤ C • log k n for some constant C thenIn 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 ⊂ (X × Y) ⋆ it holds that opt adap bandit (P) ≤ 6k • opt rand full (P).Theorem D.1 will also allow us to extend Theorem 1.1 (which is formulated for concept classes) to the r-realizable setting.Given Theorem C.1, the main ingredient left in order to prove Theorem D.1 is the following reduction from learning with bandit feedback to learning with full-information feedback. Let us briefly describe the idea, inspired by [Long, 2020, Hanneke, Livni, and Moran, 2021] .The upper bound we prove on opt adap bandit (n, k, r) makes no assumptions on the way the experts make their predictions. Therefore, it holds in particular for the case where the experts' predictions are 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 a deterministic fullinformation 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 a mistake. We thus create k different copies of A, each guessing a 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 adap bandit (k r , k, r) = O(k • r) mistakes against an adaptive adversary. The details are made precise in the proof of the proposition below.Proof of Theorem D.1. 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 it to pattern classes is straightforward (see e.g. [Moran, Sharon, Tsubari, and Yosebashvili, 2023] ). Since the adversary is consistent with P, it is known that the SOA algorithm will make at most 2opt rand full (P) mistakes as long as it receives full-information feedback. Proposition D.2 now provides the stated bound.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 r is given to the learner.Our bounds hold for all pattern classes, allowing an immediate adaptation of our results for concept classes to the r-realizable setting. Indeed, as mentioned also in Section C, for every concept class H and a budget function B : H → R we can define the pattern class appearing in (15):P(H, B) =    p ∈ (X × Y) ⋆ :   ∃h ∈ H : (x,y)∈p 1[h(x) ̸ = y] ≤ B(h)      .Choosing B = B r , where B r gives the budget r to 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, we only need the following bounds on opt det full (P(H, B r )), which were originally proved for the binary case k = 2, but can be extended in a straightforward manner to arbitrary k. Theorem D.3 ( [Cesa-Bianchi et al., 1996 , Auer and Long, 1999 , Filmus et al., 2023] ). For every concept class H and r ≥ 0 it holds that opt det full (P(H, B r )) = Θ(opt det full (H) + r).The bounds obtained using Theorem D.3 are summarized in Table 1 .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 there exists a pattern class P ⊂ (X × Y) ⋆ with |Y| = k and so that opt adap bandit (P) = Ω(k • opt obl bandit (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 obl bandit (H, r) for opt obl bandit (P(H, B r )), and similarly for other setups. Proposition E.2. Let H ⊂ Y X be the hypothesis class consisting of all constant functions, and letr ≥ 0. If k = |Y| ≥ 2 then opt obl bandit (H, r) = Θ(k + r).Proof. The lower bound follows easily from [Daniely and Helbertal, 2013, Claim 2] . For the upper bound, we describe a 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)/k 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.Second phase In this phase, the learner always predicts y, switching back to the first phase once it makes r + 1 mistakes in the phase.In order to analyze the expected number of mistakes, we assuming (without loss of generality) that the input sequence is infinite, and let y ⋆ ∈ 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 µ = 16(k+r) k . Let X be a random variable counting the number of correct predictions in the first phase. Since µ ≥ 16, and since X is a sum of independent random variables taking values in {0, 1}, applying Chernoff's bound implies that EQUATIONEQUATIONIf y = y ⋆ then the learner will make at most r more 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 ( 17),( 18) this number of times is dominated by a Geom (3/4) 2 random variable, which means that this process will occur at most (4/3) 2 < 2 times in expectation. Overall the expected number of mistakes is at most 2(16(k + r) + r) < 34(k + r).We can now prove Theorem E.1.Proof of Theorem E.1. Given k ≥ 2, we choose the pattern class P = P(H, B k ), where H consists of all constant functions.Lemma C.11 shows that opt adap bandit (P) = Ω(k 2 ), while Proposition E.2 shows that opt obl bandit (P) = O(k), yielding the stated bound.The proof of Lemma C.11 goes through with any hypothesis class of size k, where k = |Y|. We conclude that the worst-case dependence on r in opt obl bandit (H, r) is related to the size of H. For example, every H with |H| = k satisfies opt obl bandit (H, r) = Θ(k + r). However, there are classes H with |H| = k r which satisfy opt obl bandit (H, r) = Ω(kr) due to Lemma C.10. This is in contrast to opt adap bandit (H, r): for any class H (of size at least k) it holds that opt adap bandit (H, r) = Ω(kr). It would be interesting to find tight bounds on the worst case opt obl bandit (H, r) for the intermediate cases where |H| = k w for w ∈ (1, r).In this section we prove the following result, which implies Theorem 1.4 by applying it with d = k.Theorem F.1 (Restatement of Theorem 1.5). For every d ≥ 1 and k ≥ 2 there exists a concept class H ⊂ Y X with Y = {0, 1, . . . , k} such that1. opt det full (H) = d + 1. 2. opt det bandit (H) = Θ(d • k). 3. opt adap bandit (H) = Θ(d + k).In the second case, let a ⋆ > 0 be such that r ⋆ = 2 a ⋆ d 2 . In the worst case, the values of r M chosen by DT during its execution are2 0 • d 2 , 2 1 • d 2 , . . . , 2 a-1 • d 2 , 2 a • d 2, 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 r M ≥ r ⋆ . Since DT resets A at the end of every phase, in each phase i, DT is guaranteed to make at most d 1 (2 i d 2 + d 2 ) mistakes in expectation. Between phases, when the best hypothesis is inconsistent with the feedback for the (r M + 1)'th time, another mistake might be made by DT. By linearity of expectation, we see that the mistake bound of DT is at mosta + d 1 a i=0 (2 i d 2 + d 2 ) ≤ a + d 1 a i=0 2 i+1 d 2 ≤ 5d 1 2 a d 2 .Now, since a -1 ≤ a ⋆ , we have r ⋆ ≥ 2 a-1 d 2 . Therefore:5d 1 2 a d 2 = 10d 1 2 a-1 d 2 ≤ 10d 1 r ⋆ .The "furthermore" part of the proposition is obvious from the definition of DT.The mistake bounds proved in this work under the assumption that a bound r ≥ r ⋆ is given are typically of the form f (|Y|)(r + g(opt Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Theory paper. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or 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? 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?In the full-information model there is 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-information model the feedback is deterministic, even if the learner is randomized.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 is an interesting direction for future work.When there are only 2 labels, full-information and bandit feedback are the same.The adversary described in (4) is 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].It is explained in the sequel that being randomized does not really help the adversaryOne can verify that in the deterministic case, oblivious and adaptive adversaries are equivalent. 
 
 Appendix:  


Decision: This paper makes solid contribution. Please improve clarity by incorporating reviewer's comments.

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

- The paper is highly technical and may be challenging for non-expert readers. Many important discussion are also deferred to the appendix. 

- 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.
questions: questions: - Are there any unique challenges in the multi-class setting as opposed to binary classification?

- Can you further discuss the implication of the lower bound in Theorem 1.4?
limitations: limitations: The settings are properly discussed.
paper_summary: paper_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.

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

Similarly, 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.
strength_weakness: strength_weakness: 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.
questions: 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?

Lines 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?

Line 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?

Line 135: maybe these new results should also be highlighted in the abstract if they are of independent interest?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: - For the agnostic setting with oblivious adversaries, the mistake bound is not tight for large $r^*$.
- The randomized algorithm proposed for the expert setting involves minimax calculation, which is inefficient.
questions: questions: N/A
limitations: limitations: No potential negative societal impact.
paper_summary: paper_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).
strength_weakness: strength_weakness: 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.
questions: 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.

Can 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: limitations: There is not an explicit section about limitations, but the authors adequately point out the open questions.
The work is theoretetical with no immediate societal impact.

Comments: title: Response to Rebuttal
Response to Rebuttal
comment: Thanks for your response, and I have no further questions.
Thank you for the responses. I intend to maintain my score. The results seem interesting, but it would be really nice if the paper can be made more readable.
Thank you for your response and clarifications. I am inclined to retain my score and confidence score for the paper, as it remains the case that I am not the most familiar with the setting it studies (so am not fully versed on its significance and some technical details) but what I have been able to verify appears accurate and substantive and will be suitably well explained with the promised clarifications.
Thank you for responding and clarifying.

In the context of prediction with expert advice, we discuss this in detail in lines 296-313.
The main message of those lines is that to the best of our knowledge, known regret bounds are proved for a different, easier in some sense (for the learner) definition of $r$-realizability than ours. Our definition only requires that the best expert is inconsistent with the adversary's feedback for at most $r$ many rounds. Known bounds use a definition requiring that the best expert makes at most $r$ many mistakes. In our definition, even the best expert might make much more than $r$ many mistakes. This definition is useful when proving Theorem 1.1, as explained in Section 2.1.

However, if the adversary is oblivious, then both definitions of $r$-realizability coincide. The reason we can not simply convert a regret bound in this setting to a tight mistake bound, is that known regret bounds depend on the number of rounds in the game. Mistake bounds obtained from such regret bounds could only be tight in specific regimes where $r$ is relatively large.

As for learning concept classes, our mistake bounds, as well as known regret bounds [1] are proved via a reduction to prediction with expert advice, so a similar discussion holds for this problem as well.

[1] Amit Daniely and Tom Helbertal. The price of bandit information in multiclass online classification.
374 In Conference on Learning Theory, pages 93–104. PMLR, 2013.
Thanks for addressing my questions.

Your "response to weakness" is addressing very well my comment.

Your "Response to question #1" is missing the point: I wanted to know the extent to which existing proof techniques for bounding regret may be re-used for proving your mistake bounds. I am asking this because it would help relate your results with the existing results for regret in bandit multiclass classification.