Thank you for your review. ​​We hope that our responses below will fully address your comments and questions.

You actually seem to appreciate the contributions of the paper, and in particular we are glad that you find the research question interesting and important, and that our results could be of interest to the broader TCS community. We have to ask that, if you tend to favor seeing the paper accepted, please consider upgrading your score. If any concern still remains, we will be glad to try and clarify further during the discussion period.

“The result only works for finite hypothesis classes. It is not clear what will happen when the hypothesis class is infinite”

While extending our results for infinite classes would definitely be interesting, the question of optimal sample complexity rates for infinite hypothesis classes is not well understood even in the simpler full-information version of the problem (see e.g. the discussion in [10,38]). That considered, characterizing the optimal rates in the more general bandit setting still seems quite formidable and falls beyond our scope in this paper.

Further note that even in the simpler single-label setting studied in [17], the upper bound provided for classes with finite Natarajan dimension is not known to be rate-optimal. We thus chose to focus on finite classes as a natural first and crucial step in studying the more challenging bandit version of the problem.

“The assumption that every call of the ERM oracle only spends constant time is not that benign when there is an infinite hypothesis class”

Our assumption that each call to the ERM oracle takes constant time was made solely for simplicity of presentation. If instead the computational cost of the ERM oracle to $\mathcal{H}$ is denoted by $T_{ERM}(\mathcal{H})$, the overall computational complexity of our PAC learner would be $O((K/m)^5) \cdot T_{ERM}(\mathcal{H})$.

Such computational assumptions about the oracle’s runtime are standard in the literature (see e.g. [1,2]), as a means to avoid additional structural assumptions and to allow for arbitrary hypothesis classes. We will revise our presentation to make all of this clear - thanks.

Questions:

“What if the reward function is submodular, or more generally, any set function?”:

You raise a very interesting question. In combinatorial semi-bandits, the reward functions exhibit an inherent structure as sums of the reward values of the $K$ basic actions, and in particular exhibit the additivity property which you mentioned. Our current approach in the semi-bandit setting heavily relies on this additive structural property as is the case with other methods proposed in the semi-bandit literature, and we do not know whether or not our results can be generalized to wider classes of reward functions such as submodular functions. All of this could make up a wonderful direction for future research, in bandit list classification but also in combinatorial bandits more generally!

References:

[1] Dudik, Miroslav, et al. "Efficient optimal learning for contextual bandits." arXiv preprint arXiv:1106.2369 (2011).

[2] Agarwal, Alekh, et al. "Taming the monster: A fast and simple algorithm for contextual bandits." International conference on machine learning. PMLR, 2014.

[17] Erez, Liad, et al. "Fast rates for bandit PAC multiclass classification." Advances in Neural Information Processing Systems 37 (2024): 75152-75176.

Dear Reviewer FW6h,

Please provide your feedback to the authors as early as possible after reading the rebuttal and other reviews, so there is enough time for back-and-forth discussion. Thank you!

Best, Area Chair

Thank you for your review. We hope that our responses below will alleviate your concerns and allow you to reconsider your low score. We are happy to answer any further questions during the discussion period.

”The paper provides lower bounds for the problem but does not include a proof…”:

While we do not provide a formal proof of the lower bound, converting the high-level intuition to a formal proof can be done using techniques which are standard in the bandits literature, see e.g. Theorem 5.1 in [1]. That being said, we do agree that including a formal proof would be of value, and we will do so in the final version.

“While the introduction and setting showcase the fact that the paper provides both a sample complexity and regret approach, only the sample complexity approach is addressed in the main paper”:

Indeed, our primary focus is on the PAC version of the problem, which also contains the bulk of the technical contributions of our work. We defer the regret minimization section to the appendix in order to allow space for providing more context and details on our contributions in the PAC setting. Space permitting, we will definitely include the result for the online setting in the main text of the final version.

”The paper does not address the case of infinite hypothesis classes. Providing this kind of result, even with restricting assumptions on the classes of hypotheses, would greatly improve the value of the contribution”;

While extending our results for infinite classes would definitely be interesting, the question of optimal sample complexity rates for infinite hypothesis classes is not well understood even in the simpler full-information version of the problem (see e.g. the discussion in [10,38]). That considered, characterizing the optimal rates in the more general bandit setting still seems quite formidable and falls beyond our scope in this paper.

Further note that even in the simpler single-label setting studied in [17], the upper bound provided for classes with finite Natarajan dimension is not known to be rate-optimal. We thus chose to focus on finite classes as a natural first and crucial step in studying the more challenging bandit version of the problem.

“Some literature was missed on combinatorial bandits with sparse rewards”:

Thank you for pointing out [1] to us, we will make sure to include and discuss it in our related work section. We remark however that [1] focuses on the special case of linear contextual bandits, which is quite different from our more general setting where the underlying mappings from contexts to rewards may be arbitrary (but bounded).

If you are aware of any additional references that we may have missed, we would appreciate it if you could let us know so that we can include them in the revision.

Questions:

“1. What do you think is the limiting factor to applying the current types of results to infinite hypothesis classes?”:

See our response above regarding infinite hypothesis classes.

“2. …it feels like in the paper, you sometimes switch notation from the ones of the classification problem to the CCSB. It is my understanding that the underlying assumption is that there is an equivalence between the two problem.”:

There is no equivalence between the two problems: the bandit list classification problem is, directly by definition, a special case of the more general contextual combinatorial semi-bandit (CCSB) setting. There is no assumption that needs to be made for this to hold. Since we are mainly dealing with algorithms, in most of the paper we focus on the more general CCSB problem and use the associated terminology. You are correct to note that hypotheses $h \in \mathcal{H}$ in the classification setting are then analogous to the policies $\pi \in \Pi$ in CCSB.

In any case, we will do our best to improve the clarity of our notation in the revision.

“3. Algorithm 1 uses a procedure that is based on two separate phases… Is there a particular reason for having two phases”:

You raise an interesting question. We are currently not sure whether a “fully adaptive” exploration method could result in better sample complexity bounds, and we ultimately chose to separate the algorithm into two phases as it makes the analysis conceptually simpler by breaking down the main result into two stages: first optimizing for a low-variance exploration distribution and then using this distribution to estimate rewards more effectively.

“4. …you do not provide any assumption regarding the space $\mathcal{X}$... Essentially, using the fact that both $\mathcal{H}$ and $\mathcal{Y}$ are finite, the problem reduces to one with finite $\mathcal{X}$. Does that seem correct?”

This is not correct in general: $\mathcal{X}$ could be infinite even when $\mathcal{H}$ is finite. Perhaps you meant that if $\mathcal{X}$ and $\mathcal{Y}$ are both finite, then the effective number of hypotheses (cardinality of $\mathcal{H}$) is finite? (This is a correct statement, since the number of possible mappings from $\mathcal{X}$ to $\mathcal{Y}$ is finite in this case.)

In any case, the cardinality of the space $\mathcal{X}$ plays no role at any point in the analysis, only the size of $\mathcal{H}$ does. This should not come as a surprise: even in classical classification settings such as binary classification, the cases where $\mathcal{H}$ is finite while $\mathcal{X}$ is possibly infinite are interesting well-studied regimes, and the complexity of the problem is determined by the cardinality/dimension of $\mathcal{H}$, regardless of the size of $\mathcal{X}$.

Typos:

Thank you for bringing these to our attention, we will make sure to correct them.

References:

[1] Perrault, P., Valko, M., & Perchet, V. (2020, July). Covariance-adapting algorithm for semi-bandits with application to sparse outcomes. In Conference on Learning Theory (pp. 3152-3184). PMLR.

[10] M. Charikar and C. Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1713–1726, 2023.

[17] Erez, Liad, et al. "Fast rates for bandit PAC multiclass classification." Advances in Neural Information Processing Systems 37 (2024): 75152-75176.

[38] S. Moran, O. Sharon, I. Tsubari, and S. Yosebashvili. List online classification. In The Thirty Sixth Annual Conference on Learning Theory, pages 1885–1913. PMLR, 2023.

Dear Reviewer f4D1,

Please provide your feedback to the authors as early as possible after reading the rebuttal and other reviews, so there is enough time for back-and-forth discussion. Thank you!

Best, Area Chair

Thank you for your review---we hope that our responses below will fully address your concerns. Reading your comments, you seem to appreciate the contributions of the paper, and in particular we are glad that you found our technique of constructing the log-barrier potential clever. If you tend to favor seeing the paper accepted, it is crucial that you kindly consider upgrading your score. If any concern still remains, we will be glad to try and clarify further during the discussion period.

“While the usage of Franke-Wolfe leads to non-trivial sample complexity bounds, the use of Franke-Wolfe itself is not novel as prior work (citation [17]) employs a similar procedure in the case of single-label bandit classification.…”:

While a variant of Frank-Wolfe was indeed used in [17] for the single-label setting, that paper employed a stochastic version (SPIDER-FW) that relies on variance-reduced gradient estimators. Instead, we use the more standard non-stochastic version of Frank-Wolfe, but on the empirical version of the potential, and then analyze its stochastic guarantees via novel Rademacher complexity arguments (see Appendix A.1). This modification not only introduces a different methodology, but also allows obtaining improved additive polynomial dependence on $K$ in the single-label setting.

“...there is still a somewhat sizeable gap between the two bounds.”:

We agree that the additive $K^9$ upper bound can be significant when the number of labels is large. As you recognized, the main point is that this is an additive term and the main $1/\epsilon^2$ term is independent of $K$ (disregarding log factors). That said, it is indeed very interesting for us to improve this additive term, even just in the standard multi-class setting, but we suspect this might require additional techniques.

“The writing of the paper is at times hard to understand, especially for an audience not well-versed in this specific literature”:

We appreciate the feedback. In the following revision, we will do our best in order to improve the clarity of the exposition, the problem setup and the proof sketch of our main result. If you have in mind any specific places where we should focus, we will be very glad to hear. Thanks!

“Can the authors elaborate on the optimality of the regret bounds in the case of agnostic online learning?”:

While we do not prove a formal lower bound, the prior work [18] established matching lower bounds in the single-label setting (see lines 958-959 in the supplementary). Their construction can be extended in a straightforward manner to the list classification setting, which would provide a matching lower-order term for the list classification setting. We add that the main term of the form $\sqrt{smT \log |\Pi|}$ can be formally shown to be tight via arguments analogous to the lower bound given in Theorem 2 which we sketch in the main text. A formal lower bound for the online regret minimization setting was not included in the paper as this setting is not our main focus.

References:

[17] Erez, Liad, et al. "Fast rates for bandit PAC multiclass classification." Advances in Neural Information Processing Systems 37 (2024): 75152-75176.

[18] Erez, Liad, et al. "The real price of bandit information in multiclass classification." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

Dear Reviewer KD2J,

Please provide your feedback to the authors as early as possible after reading the rebuttal and other reviews, so there is enough time for back-and-forth discussion. Thank you!

Best, Area Chair

Thank you for your review. We hope that our responses below will alleviate your concerns and will allow you to reconsider your score. We would be glad of course to answer any further questions during the discussion period.

“Can the authors give a more clear vision on why a PAC learning framework for the proposed problem is necessary? ”; “It feels too much effort to fit the problem in the PAC learning setting… it feels much more like a recommendation system problem or contextual combinatorial semi-bandit problems”

We do in fact formalize the bandit list classification problem as a contextual semi-bandit problem, but with an additional crucial structure: reward sparsity, that abstracts the fact there is only a small number of correct labels per example. By referring to this as a “PAC setting” we mean that this is a stochastic i.i.d. setup and the guarantees we establish are $\epsilon$-approximate with high probability $\geq 1-\delta$, independently of the data distribution. This is a customary jargon in the learning theory literature.

Further, previous work on both single-label and list multi-class classification [14,15,17] also focused on what we call here the “PAC framework”, so it is only natural to consider the list-bandit version of the problem in this framework as well.

“If the multiclass list classification with bandit (or semi-bandit) feedback is not explored before, why considering adversarial data in this paradigm is necessary in this study?”

Note that in the PAC framework, which is our main focus, the data (examples and labels / contexts and rewards) is assumed to be stochastic i.i.d., and not adversarial as you seemed to suggest. Since existing research on combinatorial semi-bandits also studies the setting of regret minimization with adversarial data, we also include additional results for the latter setting which we defer to the appendix/supplementary.

“the algorithm assumes having access to an ERM oracle, which is also less a PAC learning paradigm…How important the ERM oracle is? What if such oracle does not exist?”

Assuming access to an ERM oracle is only necessary for obtaining computationally efficient algorithms (that is, with runtime polynomial in $\log |\mathcal{H}|$ and not in $|\mathcal{H}|$). The rest of our claims, namely the sample complexity bounds, hold regardless---but the algorithm that achieves them is in general not efficient. Indeed, in the absence of an ERM oracle, in the finite hypothesis class setting we focus on, the algorithm can optimize over the class directly by enumerating over all hypothesis, which would result in a time complexity that scales with $|\mathcal{H}|$ which we do not consider as “efficient”.

We further note that in the vastly studied stochastic contextual bandit setting, such an ERM oracle assumption is standard in the literature (see e.g. [1,2]). Even in the classic (full-information) PAC learning setting, learning reduces in general to performing ERM over the hypothesis class which, without further structural assumptions, can only be done efficiently assuming access to an optimization/ERM oracle.

“The paper is generally hard to read, with many terminology remain unexplained.”

We believe our paper’s structure, jargon and level of detail is in accordance with existing literature in this area of research. That said, we would appreciate it if you could point out any specific unexplained terminology so that we can learn where we can perhaps include further explanation. Thank you.

References:

[1] Dudik, Miroslav, et al. "Efficient optimal learning for contextual bandits." arXiv preprint arXiv:1106.2369 (2011).

[2] Agarwal, Alekh, et al. "Taming the monster: A fast and simple algorithm for contextual bandits." International conference on machine learning. PMLR, 2014.

[14] Daniely, Amit, and Shai Shalev-Shwartz. "Optimal learners for multiclass problems." Conference on Learning Theory. PMLR, 2014.

[15] Daniely, Amit, et al. "Multiclass learnability and the ERM principle." J. Mach. Learn. Res. 16.1 (2015): 2377-2404.

[17] Erez, Liad, et al. "Fast rates for bandit PAC multiclass classification." Advances in Neural Information Processing Systems 37 (2024): 75152-75176.

Dear Reviewer ZLpc,

Please provide your feedback to the authors as early as possible after reading the rebuttal and other reviews, so there is enough time for back-and-forth discussion. Thank you!

Best, Area Chair

Thank you for the response. Based on discussion, I think this problem is less natural in a learning setting, as traditional learning problems study functions with only one distinct output. As Reviewer f4D1 also noticed, it is more natural to formulate this problem in one setting (in this case, maybe better in CCSB) and stick to it.