Non-Uniform Multiclass Learning with Bandit Feedback
Authors: Steve Hanneke
Amirreza Shaeiri
Hongao Wang
Venue: NeurIPS 2025 poster ()
Keywords: Non-Uniform Learning
Bandit Feedback
Multiclass Learning
Primary area: theory

Abstract: We study the problem of multiclass learning with bandit feedback in both the i.i.d. batch and adversarial online models. In the *uniform* learning framework, it is well known that no hypothesis class $\mathcal{H}$ is learnable in either model when the effective number of labels is unbounded. In contrast, within the *universal* learning framework, recent works by (Hanneke et al., 2025b) and (Hanneke et al., 2025a) have established surprising exact equivalences between learnability under bandit feedback and full supervision in both the i.i.d. batch and adversarial online models, respectively. This raises a natural question: What happens in the *non-uniform* learning framework, which lies between the uniform and universal learning frameworks? Our contributions are twofold: (1) We provide a combinatorial characterization of learnable hypothesis classes in both models, in the realizable and agnostic settings, within the non-uniform learning framework. Notably, this includes elementary and natural hypothesis classes, such as a countably infinite collection of constant functions over some domain that is learnable in both models. (2) We construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model (and thus also not in the adversarial online model). This serves as our main novel technical contribution that reveals a fundamental distinction between the non-uniform and universal learning frameworks.

Non-Uniform Multiclass Learning with Bandit Feedback
Steve Hanneke
Amirreza Shaeri
Department of Computer Science Purdue University
Department of Computer Science
Purdue University
West Lafayette, IN 47907
West Lafayette, IN 47907 amirreza, www.ssssswerriiileeeecoommmmm
steve haaneeeeaaneeemmml......m
Hongao Wang
Department of Computer Science
Purdue University
West Lafayette, IN 47907
wang5270@purdue edu
Abstract
We study the problem of multiclass learning with bandit feedback both the i.idd. batch and adversarial online models. In the uniform learning framework, it is well known that no hypothesis class H. is learnable in either model when the effective number of labels is unbounded. In contrast, within the universal learning framework, recent works by Hanneke et al.] 2025b) and Hanneke et al. [2025a] have established surprising exact equivalences between learnability under bandit feedback and full supervision both the i.i.d. batch and adversarial online models, respectively. This raises natural question: What happens in the non- uniform learning framework, which lies between the uniform and universal learning frameworks? Our contributions are twofold: (1) We provide combinatorial characterization of learnable hypothesis classes in both models, in the realizable and agnostic settings, within the non- non- onn-unfform learning framework. Notably, this includes elementary and natural hypothesis classes, such as a countably infinite collection of constant functions over some domain that learnable in both models. (2) We construct hypothesis class that is non-uniformly learnable under full supervision the adversarial online model (and thus also the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model (and thus also not in the adversarial online model). This serves as our main novel technical contribution that reveals a fundamental distinction between the non-uniform and universal learning frameworks.
1 Introduction
Learnability lies at the core of learning theory. Intuitively, it explores the conditions under which there exists an algorithm that can accurately predict unseen instances based on a finite of examples. To rigorously study this phenomenon. various abstract learning frameworks, including uniform, non-uniform, and universal learning frameworks, have been proposed in the literature so far. This manuscript focuses on the non-uniform learning framework.
The classical work of Benedek and Itai 1988 introduced the non-uniform learning framework. Moreover, they gave a combinatorial characterization of non-uniform PAC learnability for the binary classification setting. The recent contribution of Lu (0024 gave a combinatorial characterization of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

non-uniform online learnability also for the binary classification setting. However, many important tasks involve a large prediction space. For instance, consider a quantum experiment with E N qubits, where the goal is to predict measurement outcomes, each of which can be one of 2 possible states. Meanwhile, many significant tasks involve bandít feedback, where the only information that can be received is whether the prediction is correct. For example, physicist might propose a prediction based on a discovered law of nature and then observe only whether it holds true.
In response, we consider the framework called "Non-Uniform Multiclass Learning under Bandit Feedback". Roughly speaking, in this framework, a learner aims to infer an unknown hypothesis h* from a known hypothesis class H consisting of functions from some instance space X' (e.g., space of images) some label space y (e.g., categories of images), through an interaction with nature, with a guarantee that may depend on h*.
Subsequently, we provide more precise, yet still informal, description of the framework. In the i.i.d. batch model, nature initially selects an unknown data distribution similar to classical multiclass learning, but the learner does not directly observe the correct labels of the i.i.d. training examples. Instead, during each round, the learner first receives an unlabeled example, makes a prediction for its label, and receives bandit feedback. Despite this restriction, the goal remains the same as in classical multiclass PAC learning, where the primary objective is to output a function that correctly classifies most future examples generated by the same underlying data distribution. In addition, in the adversarial online model, during each round, nature first presents an instance to the learner. Next, the learner must predict label for the given instance. After making prediction, nature reveals the bandit feedback. Crucially, this setting differs from the full supervision setting, where, at the end of each round, the true label is revealed by nature. Again, despite this restriction, the goal remains the same as in classical multiclass online learning, where the primary objective is to correctly predict in most rounds. Furthermore, in the realizable setting, we assume that the data distribution or the sequence of instance-label pairs played by the adversary is consistent with some ht E H. On the other hand, in the agnostic setting, we do not make such an assumption. Moreover, the non-uniform learning framework allows for error regret bounds, possibly depending on ht, in the i.i.d. batch and adversarial online models, respectively.
In this manuscript, our first main contribution is to algorithmically address the following question in the non-uniform multiclass learning under bandit feedback framework across both the i.i.d. batch and adversarial online models, in both the realizable and agnostic settings:
What is the necessary and sufficient condition for hypothesis class H. C yx that admits non-um ton--ufform learnability?
In particular, we provide a combinatorial characterization of hypothesis classes for which learnability is possible. We note that, for simplicity at this stage of the introduction, several details about the definitions in the framework have been omitted, such as the possibility of allowing randomized learners in the adversarial online model. For more details, see Section [.] and Section 3
Previous research on the problem of multiclass learning under bandit feedback mostly considered the uniform learning framework. In essence, the uniform learning framework seeks theoretical guarantee that is true for all data distributions or all adversarial sequences, without any dependence on the distribution sequence itself. This line of study was initiated by the seminal work of Daniely et al.
[011] and continued by Erez et al. [2024b]a a] in the PAC model, and by Daniely and Helbertal] [2013],
Long 2017)) Geneson 2021 J. Raman et al. 2023). Hanneke and Yangl [2023] in the adversarial online model. If the effective label space is infinite-thhe is, there exists at least one instance in
the instance space for which hypotheses in the hypothesis class can assign infinitely many distinet
labels-no deterministic online learning algorithm can guarantee a uniformly bounded number of mistakes against the worst-case realizable adversary. To see this, consider a scenario in which the adversary repeatedly selects the same specific instance in every round. In this case, the predictions of the online learning algorithm can be consistently incorrect, even though a hypothesis within the hypothesis class remains consistent with all previous feedback. In particular, this happens because the feedback received only indicates whether the prediction was correct or not. Moreover, this conclusion can be easily generalized to randomized algorithms as well. In addition, similar limitation arises in the PAC model due to the need to guess an unknown natural number while keeping the number of guesses uniformly bounded over the choices of the target number. Notably, this limitation applies even to elementary and natural hypothesis classes, such as a countably infinite collection of constant functions over some domain.
2

---

The recent contributions by Hanneke et al. [2025b] and Hanneke et al. (222a are the only works that diverge from the uniform learning framework by considering the universal learning framework of Bouuquet et al. [2021] J. This framework enables the study of theoretical guarantees that are still true for all data distributions or all adversarial sequences, but crucially without placing a uniform bound on the error rate in the i..dd. batch model or regret in the adversarial online model. In particular, the error rate may depend on the distribution itself, and the number of mistakes may depend on the infinite sequence of instance-label pairs. These works demonstrated surprising exact equivalences between learnability under bandit feedback and full supervision the i.i.d. batch and adversarial online models, respectively. As result, it is possible to learn the hypothesis class of a countably infinite collection of constant functions over some domain in the universal multiclass learning under bandit feedback framework in both i..d. batch and adversarial online models opposed to the uniform learning framework.
This raises natural question: what happens in the non-uniform learning framework, which lies between the uniform and universal learning frameworks? In particular, in the former, learnability is essentially impossible under bandit feedback, whereas in the latter, there is an exact equivalence between learnability under full supervision and learnability under bandit feedback.
The non-uniform learning framework also allows one to escape the aforementioned theoretical limitation in the uniform learning framework. To illustrate this, we again focus on the hypothesis class of countably infinite constant functions over some domain. Suppose that we are in the adversarial online model and the realizable setting. Now, consider the following online learning algorithm: In each round i E N. it predicts the label i until it receives feedback confirming the prediction is correct. Once the correct label is identified, consistently predicts that label all subsequent rounds. This online learning algorithm makes a finite number of mistakes, depending on h", against any realizable adversary. It is not hard to see that this class is non-uniform online learnable in the agnostic setting as well as non-uniform PAC learnable in both realizable and agnostic settings. However, we construct hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the ii.d. batch model (and thus also not in the adversarial online model). This serves as our main novel technical contribution that reveals fundamental distinction between the non-uniform and universal learning frameworks.
To summarize, our main contributions in the current manuscript are follows. Therefore, we complete the picture of the problem of multiclass learning, which is presented in the following table.
Adversarial
L.I.. with Bandit Feedback
Adversarial
with
Bandit
LLD.
Feedback
bandit Little-
finite
DS
finite effecive label space and Natarajan dimension Daniely et 2011 2011
Littlestone
stone classes
Dimension Brukhim ct al. [002]]
Uniform
classes Danielyy ct al. 2011
Daniely et al. 2011
countable union of classes with finite ef- fective label space and Natarajan dimen- sion [Theorem I.3
countable union of Littlestone classes [Theo- rem D.I
countable union of bandit Lit- tlestone classes [Theorem
countable union of DS
Non- Uniform
classes Theo-
rem
no
infinite
infinite Littlestone Tree
Littlestone Tree
All Hanneke
All Blanchard et al.
Universal
Hannekke et al.)
[aaneeee et al.)
ct 2021
2022
2025a]
2025a
Table The Learnable classes in different multiclass learning settings.
We also provide several interesting examples that show the separations among different learning settings:
We construct a hypothesis class that is non-uniformly learnable under full supervision the adversarial online model (and thus also in the i.idd. batch model), but not non-uniformly
3

---

learnable under bandit feedback in the PAC model (and thus also not in the adversarial online model). in Proposition B.T
2. We give two examples of hypothesis classes to show other separations between uniform, non-uniform, and universal learning frameworks for the problems of multiclass learning under bandit feedback and full supervision Appendix
1.1
Overview of the Main Results
In the following subsection, we provide detailed summary of the key results and findings presented in our paper.
1.1.1 Non-Uniform Multiclass Online Learning
We define the problem as a repeated game between the learner and the adversary. At each round t E N. the adversary selects an instance X; from arbitrarily non-empty instance space X' and label Y, from a possibly countably infinite non-empty label space D then, reveals X, to the learner. Subsequently, the learner predicts a (potentially randomized) label Y, from J. Following this, the learner receives feedback. If we are in the full supervision setting, the feedback is Yú: and if we are in the bandit feedback setting, the feedback is I[ * Y2), only indicating whether the prediction is correct. Following standard learning theory conventions, we define a hypothesis class H. as a set of functions from X' to y. This class is known the learner before the game begins. For additional details, see Section
In the realizable setting, assume that the sequence {(X,, Yi) chosen by the adversary, is consistent with at least one hypothesis in H. In this setting, we focus on the standard notion of the expected number of mistakes made by the learner over time. We say that hypothesis class H S y realizable non-uniform multiclass online learnable under bandit feedback there exists an online learning rule A receiving bandit feedback such that for every ht E H there exists constant E N such that for every sequence {(x,, 22) consistent with h", the online learning algorithm A only makes number of mistakes in expectation. We have a similar definition for the full supervision setting. See Section 3 for further details. The main result of this part is the following theorem.
Theorem 1.1. Let H. C y be a hypothesis class. Then, the following statements are equivalent.
H can be represented as a countable union of hypothesis classes with finite bandit Littlestone dimension.
* H is realizable non-uniform multiclass online learnable under bandit feedback.
To prove the upper bound of the above theorem, we design a novel online learning algorithm called the non-uniform bandit standard optimal algorithm. Furthermore, the proof of the lower bound is based on the original work of Benedek and Itai [1988]. As an immediate implication, consider the hypothesis class of countably infinite collection of constant functions over some domain. Indeed, one can view each hypothesis in this class as part of the countable union of hypothesis classes with finite bandit Littlestone dimension. Thus, this hypothesis class is realizable non-uniform multiclass online learnable under bandit feedback. See Section for further details. Notably, we also prove a similar theorem for the full supervision setting. The proof of this theorem is based on the arguments of the recent work of Lu 20 See Appendix D for further details.
In the agnostic setting, we make no assumptions about the sequence {(X,, Y,) chosen by the adversary. In this setting, our focus shifts to minimizing the standard notion of expected regret, which compares the expected number of mistakes made by the learner to those made by the best hypothesis in the hypothesis class H over the sequence. We say that the hypothesis class 7. C y is agnostic non-uniform multiclass online learnable under bandit feedback if there exists an online learning rule A receiving bandit feedback such that for every h² E H there exists a constant e E N such that for every T E N and every sequence {(x,, (=))== the online learning algorithm A has o(c T) expected regret. We have a similar definition for the full supervision setting. See Section for further details. The main result of this part the following theorem.
If we consider randomized learning algorithms, the associated o-algebra is of little consequence, except that singleton sets {u} should be measurable.

---

Theorem 1.2. Let H. C yy* be a hypothesis class. Then, the following statements are equivalent.
can be represented as a countable union of hypothesis classes with finite bandit Littlestone dimension.
. H is agnostic non-uniform multiclass online learnable under bandit feedback.
To establish the upper bound of the above theorem, we comprise several components. First, we prove structural lemma for bandit Littlestone classes. Second, we adopt the technique from the original work of [enedek and Itai 1988]. Third, we use an ingredient from the recent work Raman et al. [2023. Finally, we employ the standard doubling trick. As immediate implication, again consider the hypothesis class of countably infinite collection of constant functions over some domain. Based similar argument as before, this hypothesis class is agnostic non-uniform multiclass online learnable under bandit feedback. See Appendix|A.. [A.1 for further details, including the exact rate, which (vT)). Notably, we also prove a similar theorem for the full supervision setting. The proof of See Appendix for further details.
this theorem is similar to the proof of Theorem 1.2
1.1.2 Non-Uniform Multiclass PAC Learning
Here, initially, nature selects an unknown data distribution D over x y. Fix a sample size n E N. Subsequently, the learner and nature interact sequentially in rounds. In particular, during each round E (1.2..... n nature first independently samples an example (z), ~ D and reveals z to the learner. The learner is then tasked with predicting út E Y for the received instance. Upon the learner's prediction, nature only reveals whether the prediction is correct. Eventually, the learner must output function from instance space to label space that correctly classifies most future examples generated by the same unknown data distribution. Roughly speaking this called PAC learnability. Again, following standard learning theory conventions, we consider hypothesis class H. consisting of functions mapping X' to y. We assume standard measurability assumptions on X' and C as well.
We say that a data distribution D is realizable by hypothesis class H if there exists h² E H such that the samples are consistent with it almost surely. For additional details, see Section 3
Theorem 1.3. Let H. C yx be a hypothesis class. Then, the following statements are equivalent.
H can be represented space and finte Natarajan dimension.
countable union of hypothesis classes with finite effective label
is realizable non-unt uniform multiclass PAC learnable under bandit feedback.
is agnostic non-uniform multiclass PAC learnable under bandit feedbbakk
1988 To prove the above theorem, we generalize the argument of the work of Benedek and Itai
for the binary classification setting under full supervision using the results of Daniely et al. 2011 on PAC learnability under bandit feedback. As an immediate implication, consider the hypothesis class of a countably infinite collection of constant functions over some domain. Indeed, one can view each hypothesis in this class part of the countable union of hypothesis classes with finite effective label space and finite Natarajan dimension. Thus, this hypothesis class is realizable non-uniform multiclass online learnable under bandit feedback. See Section for further details. Notably, we also prove a similar theorem for the full supervision setting. See Appendix C for further details.
1.1.3 Examples
We present three examples of hypothesis classes that demonstrate the separation between related learnability notions. Formally, we have the following results.
Proposition 1.4. There exists a hypothesis class H. C yx that uniform multiclass online learnable under full supervision, but not non-uniform multiclass PAC learnable under bandit feedback.
The above proposition reveals a fundamental distinction between the non-uniform and universal learning frameworks, where in later we have surprising exact equivalences between multiclass learnability under bandit feedback and full supervision. Indeed, if hypothesis class is uniform
"The effective label sapce is the label space of one instance, that is. V = {A(z) h E H). We say concept class H has finite effective label space, if and only if Yi, is finite for every X.
5

---

multiclass online learnable under full supervision, it is also uniform multiclass PAC learnable under full supervision, non-unifome multiclass online learnable under full supervision, and con-uniform multiclass PAC learnable under full supervision. In addition, if a hypothesis class is not non-uniform multiclass PAC learnable under bandit feedback, it not also non-uniform multiclass online learnable under bandit feedback, uniform multiclass PAC learnable under bandit feedback, and uniform multiclass online learnable under bandit feedback. As a result, our theorem is stated in the most extreme case.
This serves as our main novel technical contribution. To prove it, the idea is as fol- lows: Let X' be the set of all non-empty countable sequences of distinct real numbers. Also, let y
V.y E. VSEx (y) = y isn'tt i in the sequence S; otherwise hy( = where Sli] = y}. The cru-
N U {+].
In addition, let H. fhy hy : X
cial observation that we prove is that any countable representation of this class contains a class with infinite effective label space.
Propusition 1.5. There exists hypothesis class Hi S. yd that is universal multiclass online learnable under bandit feedback, but not non- multiclass PAC learnable under supervision. Also, there exists a hypothesis class H2 S yd that is non-uniform multiclass online learnable under bandit feedback but not uniform multiclass PAC learnable under full supervision.
The above proposition demonstrates a separation between uniform, non-uniform, and universal learning frameworks, particularly under bandit feedback and full supervision.
2
Related Work
PAC Learning. The Probably Approximately Correct (PAC) learning framework, introduced by
Valiant (1984), has been a cornerstone the field of statistical learning theory. [Blumer et al. [1989]. Vapnik and Chervonenkis] 2013)) Valiant 1984), Vapnik (2006) characterizes learnable classes within the binary PAC learning framework in the realizable setting via a combinatorial parameter called the VC dimension. This result was later extended to the agnostic setting by Haussler (1992). Since then, PAC learning has been extensively studied in various learning theoretic settings.
Online Learning. Online learning has been a subject of study for over half century. The seminal work of Litlestone| [1988] marked the beginning of its formal exploration within the computer science community. Since then, online learning has been studied across diverse settings, including learning under bandit feedback Daniely et al. (201 Daniely and Helbertal] [2013), Long] [017]. (.017).,Geneeee Geneson R
[021]] |Raman et al. [2023], Hanneke and Yang [023]. Additionally, it closely linked to wide set of fundamental problems, such as differential privacy, as explored Alon et al. (2019), |Bun et al..
22020). Alon et al. [2022] Given its foundational nature, it is not surprising that online learning has also found many practical applications.
Bandit Feedback. The bandit setting plays a pivotal role in statistical decision-making Its conceptual foundation was first established by Thompson [933]. Later, the field was popularized by the mathematician and statistician Herbert Robbins, whose seminal work [Robbins| [1952 introduced the multi-armed bandit problem. In recent years, bandit scenarios have attracted substantial attention, driven by foundational contributions such as Auer et al. [2002a]b] For a comprehensive review of the literature, the reader may refer to the recent work of Foster et al. 2021
Multiclass Learning. A substantial body of theoretical research has explored multiclass classification in various frameworks, with notable contributions from Natarajan and Tadepalli (1988). Natarajan (189). Ben-David et al. [992], Haussler and Long [1995], Rubinstein et al. Danicly et al.
[2021]. However, a combinatorial characterization of multiclass classification within Valiant's s PAC learning framework, particularly
2011 2012, Daniely and Shalev-Shwariz [2014], Brukhim et al.
when the number of labels unbounded, remained unresolved until recently, even in the realizable setting. This gap was addressed in the seminal work of Brukhim et al.] [2022]. which also extended to the agnostic setting as well [Daid et al. (0166). The study of multiclass classification with unbounded label spaces is motivated by several factors. First, in multiclass settings, it is preferable for guarantees to remain independent of the number of labels, even when finite. Second, mathematical frameworks involving infinity mostly provide clearer insights.

---

3 Notations, Definitions, and Preliminaries
In this section, we provide the model setting and formal definition of the problem.
PAC Learning. In this paper, we investigate the PAC learning with bandit feedback, which is defined in the work of Daniely et al.] (201T], in non-uniform setting. Formally, A' is non-empty instance space and y is a non-empty label space. H S y is the hypothesis class, which is a non-empty set of functions from X to Jr. In this paper, we focus on learning under the 0-1 loss. In other words, the loss function Ily o 3/) defined in y x y and [[[]] is the indicator function. For distribution D over X' x V, define the emror of concept h with respect to the distribution D as (h = (a [h(x) # y/. We also denote errp (H) = inf MD(h). A learning algorithm A under this setting is function A 1 3) th + y It takes multiple samples, ii.dd sampled from distribution D, Sm. then outputs concept h. For the PAC learning with bandit feedback version, we first generate multiple samples, i.i.d. sampled from distribution D, then the learner sees the instance sequence without labels and makes prediction for each instance. After that, whether this prediction is correct is sent to the learner as feedback. Then the learner can use that information to output the concept h. To unify the definitions, we also use Sm to stand for the samples and feedback in the bandit feedback setting.
If there is a concept E H. such that (hr = O, we say the distribution D realizable by H. Then we can define the non-uniform PAC learnability as follows.
Definition 3.1 (Non- Uniform PAC Learnability). If for every h" H. there is number m(h", e, 8). such that for every m > m(h". e, 8), we have non-uniform (c, 6 learnable.
(A( > el I 8. We say H. is
Then similarly, for the agnostic case, Definition 3.2 (Agnostic Non-Uniform PAC Learnability). If for every h E H. there is number m(h", (),), such that for every m m(h', e, we have Prsm. (A())()(Sm)) eTr + S 5. We say H is agnostic non-uniform (c,5)-PAC learnable.
Online Learning. this paper, we investigate multiclass online learning in a non-uniform setting. Here, the definition of X, y and H. keeps the same previous. We also focus the 0-1 loss in this setting. X = heN is a sequence of instances and Y {Yi is a sequence of labels.
Online learning is sequential game between the leamer and the adversary. In round t, the adversary reveals an instance X, to the learner and the learner makes prediction Y; based on the history ((-1) {(X,, Yi)lige-1, where Y; is the feedback given to the learner. After that, the adversary gives the learner feedback Y, of its prediction, which may be used inform future predictions. In this paper, we focus on two types of feedback: full supervision and bandit feedback. In the full supervision setting, the learner receives the true label Y, of the instance X, and incurs
loss I Y + Y: In the bandit feedback setting, the learner only receives the loss I Yr * & and does not observe the true label Y..
In the realizable setting, the adversary chooses a concept h E H. which is unknown to the learner, and generates the labels Y, = h*,))). The learner aims minimize the cumulative number of mistakes,
T
Mh 7) = Σ 1
We use MA ()* to stand for MA (h" ,
Unlike the classic online learning problem, aim to build a mistake bound for each concept instead of a uniform mistake bound for the whole concept class. Formally speaking,
Definition 3.3 (Non-uniform Online Learnabilit.). We say concept class H is non-uniform online learnable in the realizable setting, if there exists an online learning algorithm A, such that
3m H N. vh* H, VX, MA (h", X) S m(h").
In the agnostic setting, we release the restriction that the adversary chooses target concept from the concept class. Instead, the adversary can choose any sequence of labels Y e yos In this case,
7

---

use the notion of regrer to measure the performance of the learner. The regret of the learner compared concept ht is defined the difference between the total loss of the learner and the total loss of the function h". Formally speaking,
regret (h",
Σ
Yo
Σ I (X, + Yil
Remark. Here the expectation is taken the randomness of the learner. We do not need to consider the randomized learner for the realizable cases.
Then, can define online learnability in the agnostic setting follows.
Definition 3.4 (Agnostic Non-Uniform Online Learnability.). We say concept class H. is agnostic non-uniform online learnable, if there exists an online learning algorithm A, such that
3m x N - N, m(h", T) = o(T), vh E H, AX, and regret, (h", X,Y, S m(h",
We then introduce several useful combinatorial dimensions to describe our characterization.
3.1 Combinatorial Complexity Parameters
In this paper, we define H|s = {(yi..... vn) 3h E H. Vi S n,y; = h(x;)), where S (#1,-..,,rn)
Definition 3.5 (Pseudo-cuble Brukhim et al. 2022 ). class H S ydd is called pseudo-cube of
dimension d if it is non-empty, finite and for every h H and i E [d], there is an i-neighbor g E H
of h (i.e., g(i) * h(i) and g(i) h(j) for all i).
Definition 3.6 (DS dimension [Daniely and
2014).. We say that S X is DS- shattered by H S yx if H|s contains an ni-immnnional pseudo-cube. The DS dimension dns (H)
the maximum size of a DS-shattered sequence.
Definition 3.7 (Natarajan dimension [Natarajan 1989 ). We say that E X is N-shattered by H C yd if there exist f.g : [r] + y such that for every i E [n]] we have [(i) # g(i), and
s 2 (f(1).
(f(2). o()) x x... x {f(n),
The Natarajan dimension x (H) is the maximum size of an N-shattered sequence.
Definition 3.8 (Multiclass Littlestone Tree and Littlestone Dimension (Daniely et al. 2011 A multiclass Littlestone tree for a concept class 7 is a perfect binary tree with depth d S co. The internal nodes of that tree are labeled with elements of X' and the edges connecting node and its two children are labeled by two different labels from V so that each finite path emanating from the root is consistent with concept / E H. (Meaning that for each non-leaf node on the path, the concept h labels the corresponding element of with the label the edge the path follows from that node.)
We say the Littlestone dimension of concept class H. Ldim (t) d, if there exists multiclass Littlestone tree of depth shattered by H. but there no multiclass Littlestone tree of depth + shattered by H.
Definition 3.9 (Bandit Littlestone Tree and Bandit Littlestone Dimension DDniclly et al. 2011
A bandit Littlestone tree (BL-tree for brevity) for a concept class H perfect tree T', with depth d < co. The internal nodes of that tree are labeled with elements of X' and the edges connecting node and its children are labeled with elements V, without repetition. By saying a tree "perfect", we mean that for every element shattered by concept class H. if for every path P from the root to any leaf of T, there exists concept h E H such that for every internal node in P, h(xx) is not equal to the label of the edge connecting v and its child.
V, there exists an edge labeled y. We say that BL tree T is
The bandit Littlestone dimension of a concept class H. BLdim (H) = d, if there exists bandit Littlestone tree of depth d for H. but there no bandit Littlestone tree of depth d for H.
If a concept class H has finite (bandit) Littlestone dimension, call it (bandit) Littlestone class.

---

4 PAC Learning
In this section, we investigate the non-uniform PAC multiclass learning with bandit feedback. Basi- cally, we combine the tools from the work of Beendeek and Itai 1988] and the work of Daniely et al. 2011 to get non-uniform PAC learner for the bandit feedback setting.
First, we show a property of the Natarajan dimension and the size of the effective label space, The proof appears in Appendix [A]
Lemma 4.1. If Ha has the size of effective label space 1 and dy (H1) = d1, and H2 has the size of effective label space ly and dy (H2) d2. Let H = Hi U22 the size of the effective label space of H is at most kn + 22 and y (H) S (d) + d2)² +1.
To prove the main theorem in this section, we need the following result from Doniely et al. 2011
Theorem 4.2 ([Daniely et al., 2011D. Let H. C yd be a hypothesis class. H is uniformly PAC learnable with bandit feedback, if and only if H has finite Natarajan dimension and finite size of effective label space. More specifically, if the size of the effective label space of H. is k. Then,
(f 8) = -0(x (O.NN(H)) dx(H) log In (:) + In()))
and mi (e, =000000( (m(te.)=0(..
(H) log + In(
62
Here, (e, 8) is the number of samples required for the realizable case, and my (E, 8) is the number of samples required for the agnostic case.
Proof of Theorem 1.3 In this proof, we provide way to transform uniform PAC learning algorithm
to monnonnniietn non-uniform PAC learning algorithm. As this method can be used to realizable algorithms and agnostic algorithms,
use the realizable case example in the proof.
First, we show that if is non-uniform PAC learnable, can be represented as a countable union of hypothesis classes with finite effective label space and Natarajan dimension. By definition, for every h" E H. there a number m(h", e, 6). such that if we have more than that number of samples, we can learn that concept. Therefore, by taking 100 and 8 Too we can set the following concept classes:
H4 (h' m(h", 1 1
100' 100' =
For every i, we know that there is a learning algorithm which only takes finite samples and can learn 1 h H4 with e Too and 1. Due to Theorem (42 we know H4 has finite Natarajan dimension and finite size of effective label space. And also we know that for every h E H. there is an i, h E H., thus, H. U, H..
Then we show how to non-uniformly learn a concept class H if it is countable union of hypothesis classes with finite effective label space and Natarajan dimension. Assume H U, H4. Due to
Lemma 4.1 we assume the size of effective label space of U 1 H4 is k2 and d (U H.) = dy. Then we describe the non-uniform learning algorithm. If we given m samples, compute the largest j. such that m ky [dd log ky In j + inj), then we run the uniform learner on U Hi with yn samples, if there is a concept consistent with all samples, output it. Otherwise, output a prescribed concept lgg
Then we show the algorithm works. For every concept h e H. we know there is a such that h e H,, According to the algorithm above, we have m(h", 8, = O(ky j'ly log ky In + In j")). where j' maxj, 1
5 Adversarial Online Learning
In this section, we investigate the non-uniform online multiclass learning in the realizable setting. By using the generic non-uniform learning algorithm and the bandit standard optimal algorithm (BSOA) from the work of Daniely et al. [001]], we prove that a concept class H. is non-uniform online learnable if and only if it can be represented as a countable union of bandit Littlestone classes.
Proof of Theorem L.7
We first prove that if H can represented as countable union of bandit Littlestone classes, then H. is non-uniform online learnable with bandit feedback by using the

---

Algorithm 1 Generic Non-uniform Online Learning Algorithm
1: Input: A concept class H = UmENt Hn with d, = BLdim(Hn) < oc, Vn E N
2: Initialize BSOA An for each bandit Littlestone class Ha, and number of mistakes for each algorithm 6n = 0.
3: for ( 1, ... do
4: Receive instance X1.
5: Compute Je arg minn {en + n).
6: Predict Y, as A.
Receive feedback 1 [Y, Y:
7:
8: ifT Y1 + Y.
then
9: eJ,- en, + 1.
10: end if
11:
end for
following generic non-uniform online learning algorithm (Algorithm DT. Recall the result from the work of Daniely et al. [2011] that if concept class H has BLdim(H)) = d. the BSOA has a mistake bound of d. Then we can prove that Algorithm [ has a mistake bound of m(h") is O((k + d&)?), if ht E H4 and BLdim = dg. Notice that for all t, Je + eJ, S k + d2. Also, notice that the number of mistakes made by Algorithn equal to the sum of the number of mistakes made by each An. That is,
00
k+dd
OG
MA
Σ
C
C
Σ
e (k. da)² + - (k+ dx)2
+ +1
We then prove that if H. is non-uniform online learnable with bandit feedback, then H can be represented as a countable union of bandit Littlestone classes. Because H is non-uniform online learnable with bandit feedback, there exists an online learning algorithm A such that for all he E H. MA X) < m(h)). Then we can define H. {h H m(h) n). Because H non-uniform online learnable with bandit feedback, we know that for every h E H. m(h) is finite, and we can assume that the learning algorithm is A. Thus, H. UnEN Hn. We then prove that Hy is bandit Littlestone class. In order to do this. we need the result from the work of Daniely et al.) [201T) that any deterministic algorithm makes at least BLdim(H) mistakes against the worst adversary for concept class H. Notice that for any concept h" E Hn. A can learn it with at most n mistakes, thus, BLdim (H,) S n. Therefore, Hi is a bandit Littlestone class.
We provide the results for the agnostic setting, which is more technical in Appendix A
6 Conclusion, Discussion, and Future Directions
In this paper, we study the fundamental problem of multiclass learning under bandit feedback when the number of labels can be unbounded within the non-uniform learning framework in both PAC and online models, in the realizable and the agnostic settings. We have shown a first theoretical result in this context, stating that PAC learnability is possible if and only if the hypothesis class can be represented as countable union of classes with finite effective label space and finite Natarajan dimension, and online learnability is possible if and only if the hypothesis class can be represented as a countable union of classes with finite bandit Littlestone dimension. This includes elementary and natural hypothesis classes, such as the class of a countably infinite collection of constant functions over some domain, which is not learnable provide a construction of hypothesis class that is uniform online learnable under full supervision but not non-uniform PAC learnable under bandit feedback. This implies a key distinction between the non-uniform and universal learning frameworks.
the uniform learning framework. In addition, we
At this point, we outline a suggestion for future research. We believe exploring alternative forms of feedback beyond bandit feedback in multiclass learning within the non-uniform learning framework an avenue for future research. Do we have such difference between uniform, non-uniform, and universal learning frameworks in any of them?
10

---

References
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private pac learning implies finite littlestone dimension. In Proceedings of the st Annual ACM SIGACT Symposium Theory of Computing, pages 852-860, 2019.
Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. ACM Journal of the ACM (JACM), 19(4):1334, 2022.
Patrick Assouad. Densité dimension. Annales de I'Inttitul Fourier, 33(3):233-282, 1983. doi: 20.5802/aif.933. URL http::tt::////
/ http::://wwx www.annmdaa...mmmmm org/ hataaaaticlssssee 10. http:///eeee.....//a........ 9988
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing,
2002b.
Shai Ben-David, Nicolo Cesa-Bianchi, and Philip M Long. Characterizations of learnability for classes of (O.... ---valued functions. In Proceedings of the fifth annual workshop on Computa- tional learning theory, pages 333-340, 1992.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume 3, page 1, 2009.
Gyora M Benedek and Alon Itai. Nonuniform learnability. In Automata, Languages and Programming: 15th International Colloquium Tampere, Finland, July 11-15, 1988 Proceedings 15, pages 82-92. Springer, 1988.
Moise Blanchard, Steve Hanneke, and Patrick Jaillet. Contextual bandits and optimistically universal learning. 2022. httpp://///// org/ abs 002241
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenke dimension. Journal of the ACM (JACM), 36(4):929-965, 1989.
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. A theory of universal learning. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532-541, 2021.
Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E Schapire. Multiclass boosting and the cost of weak learning. Advances in Neural Information Processing Systems, 34: 3057-3067, 2021.
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability, 2022.
Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 402-402. IEEE, 2020.
Amit Daniely and Tom Helbertal. The price of bandit information in multiclass online classification. In Conference Learning Theory, pages 104. PMLR, 2013.
Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287-316. PMLR, 2014.
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
Amit Daniely, Sivan Sabato, and Shai Shwartz. Multiclass learning approaches: A theoretical comparison with implications. Advances in Neural Information Processing Systems, 25, 2012.
Ofrr David, Shay Moran, and Amir Yehudayoff. Supervised learning through the lens of compression. Advances in Neural Information Processing Systems, 29, 2016.
11

---

Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour. and Shay Moran. Fast rates for bandit pac multiclass classification. arXiv preprint arXiv:2406. 12406. 2024a.
Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran. The real price of bandit information in multiclass classification. arXiv preprini arXiv:2405. 10027, 2024b.
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint urXiv:2112.13448 2021.
Jesse Geneson. A note the price of bandit feedback for mistake-bounded online learning. Theoret- ical Computer Science, 874:42-45, 2021.
Steve Hanneke and Liu Yang. Bandit learnability can be undecidable. In The Thirty Sixth Annual Conference on Learning Theory, pages 5813-5849. PMLR, 2023.
Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Universal Bayes consistency in metric spaces. The Annals of Statistics,, 49(4)21129 2150, 2021, doi: 00.111420-A0S2000 URL https::/:///o org/ 10. 1214/20
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. In The Thirty Sixth Annual Conference on Learning Theory, pages 5682-5696. PMLR, 2023.
Steve Hanneke, Amirreza Shaciri, and Hongao Wang. For universal multiclass online learning, bandit feedback and full supervision are equivalent. In 36th International Conference on Algorithmic Learning Theory (ALT 2025), 2025a.
Steve Hanneke, Amirreza Shaeiri, and Qian Zhang. Universal rates for multiclass learning with bandit feedback. In 38th Annual Conference Learning Theory (COLT 2025), 2025b.
David Haussler. Decision theoretic generalizations of the pac model neural net and other learning applications. Information and compulation, 100(1):78-150, 1992.
David Haussler and Philip M Long. A generalization of sauer's lemma. Journal of Combinatorial Theory, Series A, (122)219,, 1995.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285-318, 1988.
Philip M Long. New bounds on the price of bandit feedback for mistake-bounded online multiclass learning. In International Conference on Algorithmic Learning Theory, pages 3-10. PMLR, 2017.
Zhou Lu. When is inductive inference possible? In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Balas K Natarajan. On learning sets and functions. Machine Learning. 4:67-97, 1989.
Balas K Natarajan and Prasad Tadepalli. Two new frameworks for learning. In Machine Learning Proceedings 1988, pages 402 402-415. Elsevier, 1988.
Ananth Raman, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learnability under bandit feedback, 2023.
Herbert E. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery, 58:527-535, 1952.
Benjamin Rubinstein, Peter Bartlett, and Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. Advances in Neural Information Processing Systems, 19, 2006.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294 1933.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11): 1984.
12

---

Vladimir Vapnik. Estimation of dependences based on empirical data. Springer Science & Business Media, 2006.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence relative frequencies of events to their probabilities. In Measures of complexity; festschrifi for alexey chervonenkis, pages 11-30. Springer, 2015.
13

---

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 abstract and introduction, we claim that we provide combinatorial characterization of learnable hypothesis classes in both models, in the realizable and agnostic settings, within the non-uniform learning framework, and we construct some examples of concept classes showing separations. We prove these results in the subsequent sections.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
This is discussed in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, 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 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 prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: We make all of the assumptions clear in Section 3 Also, the paper contains complete proof in the subsequent sections.
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 or referenced 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 to provide intuition.
Inversely, any informal proof provided in the core of the paper should be 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:
This paper is purely theoretical.
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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 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 reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper is purely theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeedSuuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is purely theoretical.
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: This paper is purely theoretical.
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, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but 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 errors 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 of 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: This paper is purely theoretical.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:////ww...g..cccccccltt/ttta
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and ensured that our paper conforms, in every respect, with the NeurIPS Code of Ethics. We have also made sure to preserve anonymity.
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification; As this paper completely theoretical in nature, there does not seem be any societal impact of the work performed.
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 why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 generate deepfakes for disinformation. On the other hand, it is not needed to point out that 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification:
This paper is thcoretical and poses no such risks.
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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does 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 used and, 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 (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 package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of 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 anonymized URL or include 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: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, 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 the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We only use LLM for writing, and editing purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy hattaa/a/aaaarrsssec////ofeereee for what should or should not be described.
20

---

A Remaining Proofs
Proof of Lemma 4.1 First, it is obvious that the size of the effective label space of H is smaller than or equal to k + k2, because otherwise, there is a function E H and instance æ such that h((x)) + h/ (x) for every h' E Hi and h E H2. Here is obvious contradiction.
Then we prove the statement about Natarajan dimension by contradiction. Suppose dy (H) > (d1 d2)² + Thus, we have sequence S (I1 I2,, "d + +2))) that is N- shattered by H. Therefore, there are at least 2(d++da) different label sequences in the intersection of H|s and {EL' 3 {u2. X ... {u +2, Mia +42) where yf A yt for all i. However, there are at most ( ((11=d))²+2) different label sequences in the intersection of Hils and (vi, 3i x (u2. w2) x...X [u(d, +dz) +2; vid, 22)2 and there are most (1d different label sequences in the intersection of H2ls and {v9. wt) (ul: v/) x (u +22)2 Mad +d)) Notice that ((d)+ + (dds (d)) +2) - ((d1 + d2) + 2) + ((d1 + d2)² + +2)dz < 222)+
Therefore, it is a contradiction.
A.1 Agnostic Setting
In this section, discuss the result for the agnostic setting. We use the uniform online multiclass learning algorithm with bandit feedback from the work Raman et al. (2023) to design a non-uniform online learning algorithm with bandit feedback. We then prove that concept class H. is non-uniform online learnable in the agnostic setting if and only if it can be represented as a countable union of bandit Littlestone classes. Formally,
Theorem A.1. The following two statements are equivalent:
H is non-uniform online learnable with bandit feedback in the agnostic setting.
* H can be represented as a countable union of bandit Littlestone classes.
In order prove this theorem, we need the following theorem from the work of Raman al. [2023] Theorem A.2 (Raman et al. 2023), Theorem 2). For any H C y there exists an agnostic online learner whose expected regret, under bandit feedback, is at most
Sv Ldim (L)))) log
To simplify this upper bound, we want to show Ldim(H) S BLdim(Hl for all H. This is true because we can transfer a Littlestone tree bandit Littlestone tree using the following method. For each node in the Littlestone tree, if its two children are v1 and v2 and the label of the two edges are y1 and 3/2, we can create node v in the bandit Littlestone tree and then add nodes by for every y ) and label edge (v, vy) with Then we label Uyy U1 and Un2 v2, for other y E Y, we label vy = U1- Then we can prove that this bandit Littlestone tree can be shattered by H. Thus, we have Ldim (H) < BLdim (H) for all H. Therefore, the regret bound for the agnostic online learner with bandit feedback is upper bounded by SBLdim(H) /T
Then we need the following lemma:
Lemma A.3. If dim(())) = d1. Bldim((H)) d2. Bldim(HH U H2) S di + d2
Proof. Suppose for sake of contradiction that (71 U H2) 2 d1 + d2 + 3. Then there exists bandit Littlestone tree T of depth d1 + dg + that can be shattered by H4 U H2. Then consider all subtrees at depth d, 1, all of those subtrees have depth da + 2. Then because the bandit Littlestone dimension of Ha d2, the version space at the root of the subtree must contain some h Hi. Therefore, the subtree from the root to every node at the depth d1 + 1 can be shattered by Hi, which contradicts the fact that BLdim H1) = d1. That finishes the proof.
Then we can use the above lemmas and theorems to prove Theorem
A.I
Proof of Theorem A.7 We first show that if H can represented as countable union of bandit Littlestone classes, then H. is non-uniform online learnable with bandit feedback in the agnostic
21

---

setting. First, as H. can be represented as countable union of bandit Littlestone classes, we can represent it the following way: H = U H., such that BLdim U,= H4) S k. Then we can use the doubling trick to handle the changing time horizon. Set T& = ビド 2 then run the non-uniform online learning algorithm with bandit feedback in the agnostic setting with reference concept class _ Mi in the time slot [Tx, T-+1l-
Then we analyze this algorithm A, notice that for every h", there is a k, such that h" E Hg. In the meanwhile, by using Theorem [A.2, we can get a regret bound for each time slot. Thus, we can compute the regret of the algorithm as follows:
regret (h" X, Y)
Σ
11h *
rıl
log T
T3+1
Tz+1
P * Yo
Σ (X,, # Yil
1=1
I=Ty+1
1=
[log TJ
Ty+1
T[ Y, - (x,) # XY
$ ST
E
j=
1=
+
Σ
Yr Yo] - (Xx) + Yal
[log T
(
< Tk +
8BLdim
V32i
J=k
[log U Hi i=1
+ 8BLdim
V (T- Jlog -2 7))
[log TJ
= T' + Σ
8jv j21
+ 8(1log T] 1) IT 1---2114 221og 21)ooTT) Togl 2 TI)
- Th + 8( [og T ) /22 /1 +1+1 + 8(1log T] + 1) VT
$ Ty + 8(1log T 1)
Notice that T3 is constant related to h²" thus, we have m(h", T) = O(V log T), which is o(T). Therefore, this algorithm non-uniform online learning algorithm with bandit feedback in the agnostic setting.
Then we need to prove that if H. cannot be represented as a countable union of bandit Littlestone classes, no non-uniform online learning algorithm with bandit feedback can learn H. in the agnostic setting. It is equivalent to prove that if H cannot be represented as a countable union of bandit Littlestone classes, no non-uniform online learning algorithm with bandit feedback can learn 7. with a (TT) mistake bound, that is, for all h" H. m(h", T) o(T). We prove the contrapositive of this statement. In other words, if there is a non-uniform online learner A for a concept class H. with mistake bound (T)), H can be represented as a countable union of bandit Littlestone classes. By definition, we define
H, = (h E H WHH:VX,VY VX E, (h, X,T)) < T 3
Notice that i E N and H. - Hi. Define C; sup, [h(x)) h E H.H. Then refer to the Lemma 18 in the work of Raman et al. 2023 and notice that we have E.M (h, X,] < T for all
22

---

T 2 i and all X. Thus, by taking T = i, we have the following two inequalities:
i
C C-11
3
i BLdim(H,,
3
4C, log C
Therefore, we have (Ld) I 4/(2++1) log( ( ) which is finite. So. He is bandit Littlestone
9
class for all i, which implies that H. can be represented as a countable union of bandit Littlestone classes. That finishes the proof.
B Examples
In this section, we provide three examples of hypothesis classes revealing separations between related learnability notions. The main innovation constructing the first example. The second example based on the work of Bousquet et al. [02T] Also, the third example uses ideas from the second example.
Proposition B.1 (Non-Uniform Multiclass Online Learnable but not Non-Uniform Multiclass PAC Learnable under Bandit Feedback). There exists hypothesis class H C y* such that can be represented as a countable union of classes with finite Littlestone dimension, but cannot be represented countable union of classes with finite effective label space.
Proof. Let X' be the set of all non-empty countable sequences of distinct real numbers. Also, let ) = N U (+). In addition, let H = by I by X' + y. y E IR, Vsex if y in the sequence S; otherwise (S)
i, where S. = y). First, Vsexh, (S) cannot be represented as a countable union of classes with finite effective label space. Suppose by contradiction that H U H, such that for every i E N, have: the effective label space of H: is finite. Then, there exists i' E N such that HHa. = cc. This is because H is uncountable as R is uncountable. Now, we claim that the effective label space of H4 is infinite. To this, let H = ( ........ } C H₂. such that H' is countable. Based on that, let S" = (21, ........ Then, observe that the set {y y E IR, 3RCH h(S") 3} infinite. As result, we should have: the effective label space of H.- is infinite. This is contradiction. Second, we claim that Ldim To show this, we prove that the following online learning algorithm makes at most one mistake against any realizable adversary. The algorithm predicts until the first mistake, after which there is only one concept consistent with the true label. This is because if the mistake was made on (S,i). then the target function is hg, where = S.. This finishes the proof.
claim that H
1.
Proposition B.2 (Universal Multiclass Online Learnable under Bandit Feedback but not Non- Uni- form Multiclass PAC Learnable). There exists hypothesis class H S yx such that it does not have an infinite Littlestone tree, but cannot be represented as a countable union of classes with finite finte VC dimension.
Proof. Let = S < x.). Also, let y {0, 1). In addition, let 7 (hy hy : X V,y E R, VSEX hy = Myy E S]}. First, we claim that H cannot be represented as a countable union of classes with finite VC dimension. Suppose by contradiction that H. - H, such that for every i E N. we have: VC(H') < co. Then, there exists i* E N such that 77,- = co. This is because H is uncountable R is uncountable. Now, we claim that VC(H,.)) 0o. This is because the dual class of H4- is the class of all finite subsets of an uncountable set. In particular, note that for every hypothesis class H' C {0. 1)x"", we have: VC(H') < oo if and only if VC* (?') < co. This is a contradiction. Second, we claim that H does not have an infinite Littlestone tree. This is because once we fix root S E X' of a Littlestone tree, the class [h] h E H. h(S) = 1} is finite, so the corresponding subtree must also be finite. This finishes the proof.
Proposition B.3 (Non-Uniform Multiclass Online Learnalee under Bandit Feedback but not Uniform Multiclass PAC Learnalle). There exists a hypothesis class H C y such that it can be represented as countable union of classes with finite bandit Littlestone dimension, but VC(H)) co.
23

---

< co). Also, let let {0, 1). In addition, let H. = {hy hy : X - Y.y y E N, V5E hy = Hl S]}. First, we claim that VC(H) oc. This because the dual class of H is the class of all finite subsets of N. In particular, note that for every hypothesis class H' S {0,1) we have: VC(H") < co if and only if VC*(H") oo. Second, we claim that H can be represented as a countable union classes with finite bandit Littlestone dimension. This is because H is countable. In particular, note that each single hypothesis has both Littlestone dimension and bandit Littlestone dimension equal to zero. This finishes the proof.
Proof. Let X' = (
We note that, above, Assouad [983] for the proof of the result that we used.
(C*() as the dual VC dimension. We refer the readers to the work of
C Non-Uniform Multiclass PAC Learning
In this section, investigate the non-uniform PAC multiclass learning. Basically, combine the tools from the work of Benedek and Itai 1988) and the work of Brukhim et al. [2022] to get non-uniform PAC learner.
First, we have the following property of DS dimension. Lemma C.1. dfd))(H() d1, (H2) d2, dDs H2) S d1 + d2 + 1.
Proof. We can prove this by contradiction. Suppose dns H1 U H2) 2 di + d2 + 2. We have S f-r1--... -o------- #d2 such that HIs contains d1 + d2 + 2-dimension pseudo-cube. Without loss of generality, assume 5 = {=1,..... Fdd such that Hils, contains a di-diimnsionn pseudo-cube. However, for any +l, ................................ +2 let S (z4) then H. |s; does not contain di +1 pseudo-cube. Therefore, for all h Hi. they all agrees the label of S2 { +1 11.... d2 d2+2)- However, H|ss contains a d2 + 2 dimension pseudo-cube. Therefore, Hl 92 H/s H1 Sa which must contains d2 + 1-dimension pseudo cube. Here is contradiction, and that finishes the proof.
In order to prove the main theorem in this section, Theorem 1.3 We need the following results about the uniform PAC learnability with bandit feedback.
Theorem C.2 (Brukhim et al. 2022).. Let C y be a hypothesis class. is uniformly PAC
learnable, and only if H has finie DS dimension.
Then we have the main theorem here.
Theorem C.3. The following three statements are equivalent:
H can be represented as a countable union of hypothesis classes whose DSS dimension is finite.
H is non-uniform PAC learnable in the realizable setting.
H. is non-uniform PAC learnable in the agnostic setting.
Recall the proof of Theorem same.
1.3 we only need Lemma C.I and the rest the proof is exactly the
D Non-Uniform Multiclass Adversarial Online Learning
In this section, we provide the results for non-uniform multiclass online learning with full supervision. The results here new, but easily be obtained by extending the methods in the work of Lu 2024).
D.1 Realizable Setting
In the realizable setting, concept class H is non-uniformly online learnable, if and only if H is countable union of Littlestone classes. The proof extends the algorithm from the work Lf 2024 to multiclass setting. Formally.

---

Theorem D.1. The following two statements are equivalent:
H. is non-uniform online learnable with full supervision.
H. can be represented as a countable union of Littlestone classes.
Proof. We first prove that if H can be represented countable union of Littlestone classes, then H is non-uniform online learnable with full supervision by using the following non-uniform online learning algorithm (Algorithm 2 Recall that the SOA algorithm has mistake bound of for
Algorithm 2 Non- Non-uniform Online Learning Algorithm with Full Supervision
1: Input: A concept class H UnENt Hi, with d, BLdim(HH)) oo, Vn N+
2: Initialize an SOA An for each bandit Littlestone class Hn. and number of mistakes for each algorithm En 0.
3: for = 1, ......... do
4: Receive instance X,.
5: Compute Je = arg min, fen + n).
6: Predict Y, as A.,
7: Receive true label Y,
8: for 1,2,... ... do
9: The prediction of A, is not equal to Y; then
10: Cn cn + 1.
11: end if
12: end for
13:
end for
Then if the target concept ht H4, where Ldim(H4) = d.. Then notice that for all i, we have Je S d + k. Thus, the algorithm will stick to the A₂ after at most (d& k))2 rounds and will make no more mistakes. So we have m(h") S (dæ + k)2 and that finishes the proof of the first part.
Littlestone class H. with Ldim(H))
Then prove that if H is non-uniform online learnable with full supervision, then H can be represented as a countable union of Littlestone classes. Because H is non-uniform online learn- able with full supervision, there exists an online learning algorithm A such that for all h" E H. MA (h* X) < m(h"). Then we can define
H, (h E H m(h) = n).
Because H is non-uniform online learnable with full supervision, know that for every h E H. m(h) is finite, and we can assume that the learning algorithm is A. Thus, 7 = UnEN+ Hn. We then prove that Hi is a Littlestone class. In order to do this, need the result from the work of Daniely et al. [201]] that any deterministic algorithm makes at least Ldim(H) mistakes against the worst adversary for concept class H. Notice that for any concept ht Hn. A learn it with most mistakes, thus, Ldim(H..) < n. Therefore, H., is Littlestone class. That finishes the proof. O
D.2 Agnostic Setting
In the agnostic setting, a concept class H. is non-uniformly online learnable, if and only if H. is countable union of Littlestone classes. We use the doubling trick on the uniform online learning algorithm to show this result. Formally,
Theorem D.2. The following two statements are equivalent:
H. non-uniform online learnable with full supervision in the agnostic setting.
H can be represented as a countable union of Littlestone classes.
In order to prove this theorem, we need the uniform online learning algorithm in the agnostic setting and the following theorem from the work of Hanneke et al. 2203).
Theorem D.3 (Hanneke al. 2023], Theorem 4). For any concept class H and T -2Ldim(H))
we have an agnostic online learning algorithm, whose regret is at most
O Ldim log T).
25

---

We can use the doubling trick and the uniform online learning algorithm above to design the non- uniform online learning algorithm. To do this, need to notice that the property of having finite Litrlestone dimension is closed under finite union. This is true due to the same reasoning as Lemma A.3 Then we can prove Theorem D.2
Proof. We first show that if H. can be represented as countable union of Littlestone classes, H. is non-uniform online learnable in the agnostic setting. Because H can be represented as a countable union of Littlestone classes, we can write H. = U Hi such that Ldim(U, :=1 H4) S k. Let
Th 1 20-1, Run the uniform agnostic online learning algorithm on U Hi in time slot [2% + 1,1,+1],, we restart the algorithm time T: for every
Notice that for every h" there a such that h E Mk. and use Theorem D.3 we can analyze the regret of the algorithm above:
regret ( X, E
Σ
[h'(())) Yil
log
T
Tz+1
E
Ye Yg
Σ
(X,, Yıl
j=1
t=Ty +-
+=
log T
T,+1 Σ t=
T
Y1 Y/
Thhh (X,) # Yi]
+I
Σ T Thr T|M # Yo] mx,(),)) Yi]
f=
(=I Log xJ+1
[]
j Un.
[log
$ Th +
Ldim
j2r +c Ldim
U i=1
Hi
(T (T- 21 (T-21loRT)) log(T 2 71)
j=k
[log T'
$ Th +
Σ
cjv2i + collog T| + +11 (T 2]1oxT])
j=k
$ Th + e(llog T + 1)2VT
This inequality holds for some constant c. Thus, we notice that m(h", T) Th c(logT)2VV which is o(T). Therefore, this is non- non-uniform agnostic online learning algorithm.
To prove the necessity, it is equivalent show that if there non-uniform online learner A can learn a concept class H with expected mistake bound m(h, T) = oTT), H can be represented as countable union of Littlestone classes.
By definition, we define
T H4 (h HX E,M X, (h, < 7
Notice that E and = U H., Referring to the work Ben-BeDDvvi et al. (2009), we know there exists sequence X, such that L (h, x,
[dim(H.) for all algorithm A. Then take 3. which is finite. So, H; is a Littlestone class
T= i, we can get & > 2 for all i, which implies that H can be represented as a countable union of Littlestone classes. That finishes the proof.
Idim(H.) Thus, Ldim (H.) S 2:
26


Reviews:
[{"review_id": "FGid2Adbvb", "reviewer": "Reviewer_sVPb", "summary": "The paper studies multiclass prediction when only bandit feedback is available, and the number of possible labels may be infinite. Under the uniform framework no class is learnable once labels are unbounded, and prior work show that under the universal framework bandit feedback is as powerful as full supervision. This work studies the non-uniform setting, and relate to learnability to Natarajan dimension in the PAC setting and bandit Littlestone dimension in the online learning setting.", "questions": "The algorithm based on BSOA is used to learn non-uniformly under bandit feedback in the online setting. How does the algorithm perform in terms of computational complexity? \n\nCan the results be generalized to other forms of feedback?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "As someone not closely following this line of work, the result in this paper seemed interesting and substantial to me. In particular, they give a nice exact characterization of the learnability in the non-uniform setting. The theoretical results seem very clean. \n\nWhile the results are new, the proofs are relatively simple, and does not seem to lead to new techniques or insights. Hence, I am not quite sure how surprising the results should be considered. To me, the results feel more or less direct analogs to some of the classical results in non-uniform learnability, for example, Chapter 7 in the book [1]. As such, I think some of the classical results in non-uniform learning should be mentioned somewhere, and a comparison should be made. \n\nThe paper is structured oddly in places. For example, it seems weird that the definition for various complexity measures only appears in the appendix. This makes reading the paper somewhat difficult. \n\nIn the introduction, a table summarizing and juxtaposing the three frameworks and learnability criteria, and highlighting some key examples, could be helpful. A more concrete illustration and examples around the key definitions and theorems would also be helpful. \n\n[1] Understanding machine learning, Shalev-Shwartz and Ben-David. \n\nOther comments:\n- Apperances of section X should be capitalized (Section X).\n- Section 5 have just one subsection and nothing else. If only one subsection, just present as a section.", "was_revised": true, "final_justification": "The results the paper presented are interesting and new (in the sense that no one has claimed them before), but technically not very surprising. Some revision is needed to make it more accessible. I keep my score to an accept.", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer found our results interesting, and moreover, mentioned that our proofs are clean. We will make sure to correct typos and incorporate minor suggestions for the camera-ready version. Below, we address major comments provided by the reviewer.\n\n\n> \"While the results are new, the proofs are relatively simple, and does not seem to lead to new techniques or insights. Hence, I am not quite sure how surprising the results should be considered. To me, the results feel more or less direct analogs to some of the classical results in non-uniform learnability, for example, Chapter 7 in the book [1]. As such, I think some of the classical results in non-uniform learning should be mentioned somewhere, and a comparison should be made.\"\n\nWe construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model (and thus also not in the adversarial online model). We strongly believe this construction is novel, as the hypothesis class differs significantly from natural or commonly considered classes. In summary, this serves as our main novel technical contribution that reveals a fundamental distinction between the non-uniform and universal learning frameworks.\n\nWe appreciate the reviewer's feedback. We completely agree with the reviewer's comment on the comparison. Following your suggestion, we will make sure to add such a discussion for the camera-ready version.\n\n\n> \"The paper is structured oddly in places. For example, it seems weird that the definition for various complexity measures only appears in the appendix. This makes reading the paper somewhat difficult.\"\n\nWe appreciate the reviewer's feedback. We completely agree with the reviewer's comment on the paper structure. Following your suggestion, we will make sure to change the structure of the paper for the camera-ready version.\n\n\n> \"In the introduction, a table summarizing and juxtaposing the three frameworks and learnability criteria, and highlighting some key examples, could be helpful.\"\n\nWe appreciate the reviewer's feedback. We completely agree with the reviewer's comment about the table. Following your suggestion, we will make sure to include a table for the camera-ready version.\n\n\n> \"The algorithm based on BSOA is used to learn non-uniformly under bandit feedback in the online setting. How does the algorithm perform in terms of computational complexity?\"\n\nRegarding the computational complexity of our algorithms, we note that our algorithms are not efficient for general concept classes. However, this is an issue for both PAC and adversarial online learning even in the binary setting. For instance, in the case of adversarial online learning, SOA involves computing the Littlestone dimension of concept classes defined by the online learner in the course of its interaction with the adversary, which is a challenging computation, even when the concept class and the set of features are finite [1]. Notably, no efficient algorithm can achieve finite mistake bounds for general Littlestone classes [2].\n\n\n> \"Can the results be generalized to other forms of feedback?\"\n\nWe appreciate the reviewer's feedback. It is a very interesting question whether these results can be generalized to other forms of feedback. We believe this is a meaningful question and have listed it as one of the future directions.\n\n\nFinally, once again, we thank the reviewer for dedicating their time to assess our work. We hope this rebuttal addresses the points that you mentioned.\n\n\n[1] P. Manurangsi and A. Rubinstein. Inapproximability of VC Dimension and Littlestone’s Dimension. In Proceedings of the 30th Conference on Learning Theory (COLT), 2017.\n\n[2] A. Assos, I. Attias, Y. Dagan, C. Daskalakis, and M. K. Fishelson. Online Learning and Solving Infinite Games with an ERM Oracle. In Proceedings of the 36th Conference on Learning Theory (COLT), 2023."}, {"review_id": "ib03YYxBNE", "reviewer": "Reviewer_fkCf", "summary": "The paper studies when multiclass hypothesis classes remain learnable from bandit-only feedback in the “non-uniform” setting that sits between classic PAC learning and universal learning. Learnability in the i.i.d. (PAC) regime occurs iff the class can be decomposed into countably many subclasses, each with finite effective label space and finite Natarajan dimension. In the adversarial online regime, learnability occurs iff the class is a countable union of subclasses with finite bandit Littlestone dimension. To match these information-theoretic conditions, the authors present a generic Bandit-SOA algorithm as well as separation examples, showing the non-uniform and universal frameworks fundamentally diverge.", "questions": "Are the non-uniform learners implementable in polynomial time for finite-label classes with small BLdim/Natarajan dim? If not, is there any hope of an efficient surrogate?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper proves tight if-and-only-if characterizations for non-uniform multiclass learning under bandit feedback in both PAC and online settings (Theorems 1.1 - 1.3). Proofs are mostly self-contained and appear to build correctly on previous lines of work.\n2. Resolves an open question left by Hanneke et al. (2025). The negative separation example (Prop 1.4) shows a fundamental distinction between bandit learning and full supervised learning in the non-uniform framework.\n3. Extends non-uniform learnability from binary to multiclass and bandit feedback, which (to the best of my knowledge) has not been done; the combinatorial conditions seem new.\n\nWeakness:\n1. Practical relevance is indirect: all algorithms rely on full knowledge of countable decompositions and invoke BSOA sub-routines with exponential overhead. The paper does not discuss computational complexity or whether efficient learners exist even for finite-label subclasses.\n2. It seems the generic “countable union + mistake/sample budget allocator” technique is adapted from Benedek and Itai (1988); novelty mainly lies in multiclass extension. Would like to see more clarity on what new proof ideas are required beyond existing reductions.", "was_revised": true, "final_justification": "I am still not quite sure about whether the novelty of the hypothesis class construction for separating full information and bandit setting has enough broader relevance. Aside from that, I am OK with the paper.", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer mentioned that our work involves a fundamental distinction and new results, and moreover, found our proofs self-contained and sound. Below, we address comments provided by the reviewer.\n\n\n> \"Practical relevance is indirect: all algorithms rely on full knowledge of countable decompositions and invoke BSOA sub-routines with exponential overhead. The paper does not discuss computational complexity or whether efficient learners exist even for finite-label subclasses.\"\n\n> \"Are the non-uniform learners implementable in polynomial time for finite-label classes with small BLdim/Natarajan dim? If not, is there any hope of an efficient surrogate?\"\n\nWe appreciate the reviewer's feedback. We completely agree with the reviewer's comment. Following your suggestion, we will make sure to add such a discussion for the camera-ready version.\n\nRegarding the computational complexity of our algorithms, we note that our algorithms are not efficient (not polynomial time) for general concept classes. However, this is an issue for both PAC and adversarial online learning even in the binary setting. For instance, in the case of adversarial online learning, SOA involves computing the Littlestone dimension of concept classes defined by the online learner in the course of its interaction with the adversary, which is a challenging computation, even when the concept class and the set of features are finite [1]. Notably, no efficient algorithm can achieve finite mistake bounds for general Littlestone classes [2].\n\n\n> \"It seems the generic \"countable union + mistake/sample budget allocator\" technique is adapted from Benedek and Itai (1988); novelty mainly lies in multiclass extension. Would like to see more clarity on what new proof ideas are required beyond existing reductions.\"\n\nWe construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model (and thus also not in the adversarial online model). We strongly believe this construction is novel, as the hypothesis class differs significantly from natural or commonly considered classes. In summary, this serves as our main novel technical contribution that reveals a fundamental distinction between the non-uniform and universal learning frameworks.\n\n\nFinally, once again, we thank the reviewer for dedicating their time to assess our work. We hope this rebuttal convinces you of the novelty of our contribution and addresses your question.\n\n\n[1] P. Manurangsi and A. Rubinstein. Inapproximability of VC Dimension and Littlestone’s Dimension. In Proceedings of the 30th Conference on Learning Theory (COLT), 2017.\n\n[2] A. Assos, I. Attias, Y. Dagan, C. Daskalakis, and M. K. Fishelson. Online Learning and Solving Infinite Games with an ERM Oracle. In Proceedings of the 36th Conference on Learning Theory (COLT), 2023."}, {"review_id": "H0WjM8vHbv", "reviewer": "Reviewer_fKQT", "summary": "The paper studies learnability under uniform, non-uniform and universal learning frameworks, as recently investigated by Hanneke et al 2025a,b. Among the contributions: (i) the paper gives a combinatorial characterization in the non-uniform learning framework, and (ii) the authors are able to construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model but not non-uniformly learnable under bandit feedback, revealing a separation between the non-uniform and universal learning settings (in the universal setting we have an exact equivalences between multiclass learnability under bandit feedback and full feedback).", "questions": "- What is the universal learning setting ?\n- What is the effective label space ?\n- Please articulate the applicability of your setting to real-world problems. E.g., why is it more appealing to rely on an algorithm that also works on infinite label spaces when the label space is finite but large, if we only have bandit feedback available.", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "On the positive side, I praise the authors' efforts to try and explain the frameworks and the scope of their results.\n\nOn the negative side, I'm not sure how compelling or widely interesting such results are (in general), and in particular for the Neurips audience. In this respect, I am not buying the authors' motivations in L. 271 of the paper: \"in multiclass settings, it is preferable for guarantees to remain independent of the number of labels, even when finite. [...] mathematical frameworks involving infinity mostly provide clearer insights.\" I don't see practical motivations behind such a line of research nor do the authors attempt to provide any.\n\nPresentation-wise, the paper leaves a lot to be desired. It is a bit awkward that, up until page 6, there is not a clear explanation of the specifics of the learning frameworks the authors are alluding to. Though I am very much aware of the basics, I am not familiar with the difference between non-uniform and universal, and I don't see any clear explanation of that in the paper, despite the lengthy (and quite redundant) introductory sections. Moreover, as I go over Sect. 4 (e.g., Lemma 4.1) I stumble into undefined concepts (like ``effective label space\"), that the authors seem to take for granted.\n\nMinor points:\n-  l. 58, \"addressing\" --> \"address\" ?\n- L. 106 \"unless\": is it \"until\" rather than \"unless\" ?\n- L. 150 \"bandit feedback setting's feedback\": how about just \"bandit feedback\" ? \n- L. 159-160: upper bound and lower bound: which upper and lower bound, exactly ?\n- L. 164 \"bounded littlestone dimension\": this comes out of the blue, frankly, at this point ...\n- L. 199: what is C ?\n- L. 203 \"finite effective label space\": same issue, it comes out of the blue in the flow of the presentation\n- L. 307: I assume the history also contains $X_t$ ?\n- L. 341 \"we need the following a result\" (typo). Btw, what is ``the following result\" you are alluding to here ? Is it Thm B.1 from Daniely et al. 2011 ? If so, you cannot write things this way... you should recall the content of the theorem on the spot.", "was_revised": true, "final_justification": "Reasonable but perhaps not groundbreaking contribution on a line of research that is somewhat a niche. The paper should be made more accessible through an improved presentation to a wider Neurips audience.", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer mentioned that our work involves clear explanations. We will make sure to correct typos and incorporate minor suggestions for the camera-ready version. Below, we address comments provided by the reviewer.\n\n\n> \"On the negative side, I'm not sure how compelling or widely interesting such results are (in general), and in particular for the Neurips audience. In this respect, I am not buying the authors' motivations in L. 271 of the paper: \"in multiclass settings, it is preferable for guarantees to remain independent of the number of labels, even when finite. [...] mathematical frameworks involving infinity mostly provide clearer insights.\" I don't see practical motivations behind such a line of research nor do the authors attempt to provide any.\"\n\n> \"Please articulate the applicability of your setting to real-world problems. E.g., why is it more appealing to rely on an algorithm that also works on infinite label spaces when the label space is finite but large, if we only have bandit feedback available.\"\n\n\nIn practice, tasks such as image object recognition and next-word prediction involve a large number of classes. Therefore, it is desirable for theoretical guarantees to avoid dependence on the number of labels, which can be very large. For more details, we shall suggest that the reviewer see, for example, [1].\n\n\n> \"Presentation-wise, the paper leaves a lot to be desired. It is a bit awkward that, up until page 6, there is not a clear explanation of the specifics of the learning frameworks the authors are alluding to. Though I am very much aware of the basics, I am not familiar with the difference between non-uniform and universal, and I don't see any clear explanation of that in the paper, despite the lengthy (and quite redundant) introductory sections. Moreover, as I go over Sect. 4 (e.g., Lemma 4.1) I stumble into undefined concepts (like ``effective label space\"), that the authors seem to take for granted.\"\n\nWe appreciate the reviewer's feedback. We completely agree with the reviewer's comments. Following your suggestion, we will make sure to incorporate relevant changes for the camera-ready version.\n\n\n> \"What is the universal learning setting ?\"\n\n\nThe \"universal\" terminology of [2] refers to the \"$\\forall$\" universal quantifier: for all realizable distributions, the error converges at some rate (though perhaps not uniformly so over distributions); analogously, in the adversarial online setting we are interested in whether, for all realizable data sequences, the number of mistakes is finite (though perhaps not uniformly so over data sequences).\n\n\n> \"What is the effective label space ?\"\n\nThe size of the effective label space is defined as follows: $\\sup_{x\\in\\mathcal{X}} |\\{h(x):h\\in\\mathcal{H}\\}|$. \n\n\nFinally, once again, we thank the reviewer for dedicating their time to assess our work. We hope this rebuttal addresses the points that you mentioned.\n\n\n[1] Brukhim, N., Carmon, D., Dinur, I., Moran, S., & Yehudayoff, A. (2022). A Characterization of Multiclass Learnability. In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 943–955.\n\n[2] O. Bousquet, S. Hanneke, S. Moran, R. van Handel, and A. Yehudayoff. A Theory of Universal Learning. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021."}, {"review_id": "2vryFbvPrM", "reviewer": "Reviewer_Y85r", "summary": "The authors consider multiclass classification in the non-uniform learning framework. They establish structural results showing that in contrast to the uniform and universal learning framework, the non-uniform learning framework exhibits a separation between learning under full supervision and learning with bandit feedback; that is, when the learner only observes whether or not the prediction is correct. In more detail, the authors characterize the hypothesis classes which are non-uniformly learnable under bandit feedback in both the online and PAC settings by presenting them as countable unions of classes with bounded dimensions which are known to characterize learnability in the corresponding uniform framework. The authors also exhibit a strict separation between bandit feedback and full supervision in the non-uniform framework by exhibiting a specific hypothesis class which is learnable under full supervision (even in the uniform learning framework) but not learnable with bandit feedback in the non-uniform framework.", "questions": "I would appreciate it if the authors could elaborate on the technical novelties of their results, specifically, what additional techniques are needed which are not present in more classical results relating uniform and non-uniform learnability. As it stands, it seems to me like a quite general statement could be proven: A class $H$ is non-uniformly learnable in the X setting if and only if $H$ is a countable union of classes which are uniformly learnable in the X setting (in which case there is most likely a known dimension characterizing such classes). Is my intuition correct? Do the authors believe such a general statement could be proven formally?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* This work proves several open questions in the literature of learnability under bandit feedback, of which previous works considered only the uniform and the universal learning frameworks. As the non-uniform learning framework is well-studied in the learning theory literature, studying the role of bandit feedback in this framework seems natural.\n* The results are presented clearly and are easy to understand.\n* The fact that in the non-uniform learning framework there is a strict separation between full supervision and bandit feedback is surprising given that such a separation does not exist in the uniform and the universal learning frameworks.\n\nWeaknesses:\n\n* From a technical perspective, the results established in this work are obtained in a fairly straightforward manner from existing results in the learning theory literature. For example, showing the equivalence of non-uniform learnability under bandit feedback with the structural property of being a countable union of classes with finite BL-dim seems quite analogous to the corresponding result from binary classification - where a hypothesis class is non-uniformly learnable if and only if it is a countable union of classes with finite VC dimension. The structural properties presented in this paper seem to follow very similar concepts.", "was_revised": true, "final_justification": "It seems that the major technical contribution of this paper was to \"construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model\". While I believe this result is interesting, the rest of the results presented in the paper seem to follow from standard arguments from the learning theory literature and are not very technically interesting. I am still leaning towards acceptance, though I do feel like the technical contribution are a bit lacking. I therefore maintain my overall score and I will not champion this paper.", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer mentioned that our work answers several natural open questions in the literature, found our results clear and easy to understand, and moreover, highlighted that our separation is surprising. Below, we address comments provided by the reviewer.\n\n\n> \"From a technical perspective, the results established in this work are obtained in a fairly straightforward manner from existing results in the learning theory literature. For example, showing the equivalence of non-uniform learnability under bandit feedback with the structural property of being a countable union of classes with finite BL-dim seems quite analogous to the corresponding result from binary classification - where a hypothesis class is non-uniformly learnable if and only if it is a countable union of classes with finite VC dimension. The structural properties presented in this paper seem to follow very similar concepts.\"\n> \"I would appreciate it if the authors could elaborate on the technical novelties of their results, specifically, what additional techniques are needed which are not present in more classical results relating uniform and non-uniform learnability.\"\n\nWe construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model (and thus also not in the adversarial online model). We strongly believe this construction is novel, as the hypothesis class differs significantly from natural or commonly considered classes. In summary, this serves as our main novel technical contribution that reveals a fundamental distinction between the non-uniform and universal learning frameworks.\n\n\n> \"As it stands, it seems to me like a quite general statement could be proven: A class  is non-uniformly learnable in the X setting if and only if  is a countable union of classes which are uniformly learnable in the X setting (in which case there is most likely a known dimension characterizing such classes). Is my intuition correct? Do the authors believe such a general statement could be proven formally?\"\n\nYes, we share the same intuition. Moreover, we believe that such a general statement can indeed be formally proven. However, we found it challenging to define a sufficiently general learning framework within which this result can be elegantly established.\n\n\nFinally, once again, we thank the reviewer for dedicating their time to assess our work. We hope this rebuttal convinces you of the novelty of our contribution."}, {"review_id": "1UBF5g8bIh", "reviewer": "Reviewer_wMkv", "summary": "Studies the non-uniform model for multiclass classification with unbounded number of labels under bandit feedback. Considers both PAC and online learning settings. Provides a characterization of learnability in realizable/agnostic versions of PAC and online settings. Further unlike universal learning, there is a separation between bandit feedback and full feedback in the non-uniform setting. The non-uniform setting is in between uniform and universal learning settings. In uniform setting, sample complexity/regret should only depend on the hypothesis class. In non-uniform, it can depend on hypothesis as well. In universal learning, it can depend on hypothesis and distribution/individual sequence as well.", "questions": "What is truly novel in your algorithms and proofs?\nWhy should the broader ML community be interested in these result as opposed to a more specialized theory-focused conference?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\nConsider a very natural question that was left unaddressed by previous work. Last few years have seen a lot of work on unbounded label spaces and bandit feedback. Makes the paper timely.\n\nWeakness:\nNovelty is very limited. The characterization is exactly what one would expect. In standard online or PAC learning, we know that non-uniformly learnable classes are exactly those that are countable unions of uniformly learnable classes. This is exactly what the authors show here too: countable unions of classes that are learnable uniformly. While the paper fills a gap technically speaking, the answer and the methodology used to provide the answer does not provide sufficiently novel insights into learnability in general. As a result, the paper is not appropriate for a broad audience conference like NeurIPS. It might be more suitable for a theory focused conference. This is especially so since the focus on unbounded label spaces and the subtle differences between uniform and non-uniform learnability, while fully justified from a theoretical point of view, are of limited relevance to the broad ML community.", "was_revised": true, "final_justification": "The authors clarified both the contribution and why it should appeal to the neurips community.", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer found our paper timely, and moreover, mentioned that we considered a very natural question. Below, we address comments provided by the reviewer.\n\n\n> \"What is truly novel in your algorithms and proofs?\"\n\n> \"Novelty is very limited. The characterization is exactly what one would expect. In standard online or PAC learning, we know that non-uniformly learnable classes are exactly those that are countable unions of uniformly learnable classes. This is exactly what the authors show here too: countable unions of classes that are learnable uniformly. While the paper fills a gap technically speaking, the answer and the methodology used to provide the answer does not provide sufficiently novel insights into learnability in general.\"\n\nWe construct a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model), but not non-uniformly learnable under bandit feedback in the i.i.d. batch model (and thus also not in the adversarial online model). We strongly believe this construction is novel, as the hypothesis class differs significantly from natural or commonly considered classes. In summary, this serves as our main novel technical contribution that reveals a fundamental distinction between the non-uniform and universal learning frameworks.\n\n\n> \"Why should the broader ML community be interested in these result as opposed to a more specialized theory-focused conference?\"\n> \"the paper is not appropriate for a broad audience conference like NeurIPS. It might be more suitable for a theory focused conference. This is especially so since the focus on unbounded label spaces and the subtle differences between uniform and non-uniform learnability, while fully justified from a theoretical point of view, are of limited relevance to the broad ML community.\"\n\nTo the best of our knowledge, NeurIPS encompasses multiple sub-communities, each with specific interests that may not necessarily align with those of others. We believe that our results are particularly relevant and of interest to the ML theory sub-community within NeurIPS.\n\n\nFinally, once again, we thank the reviewer for dedicating their time to assess our work. We hope this rebuttal convinces you of the novelty of our contribution."}]

Author rebuttal:

Meta-review: The authors study the problem of multiclass non-uniform learning with bandit or full supervision in i.i.d. batch and adversarial online models. A key contribution is constructing a hypothesis class that is non-uniformly learnable under full supervision in the adversarial online model (and thus also in the i.i.d. batch model) but not non-uniformly learnable under bandit feedback in the i.i.d. batch model. This separation is an interesting result on a well defined problem. The problem is rather niche (within the theory community) and it is not clear if the proofs have take home messages for other problems. Nevertheless, the paper offers a nice resolution to a well defined problem and therefore I recommend acceptance.
Decision: Accept (poster)