From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
Authors: Liad Erez
Tomer Koren
Venue: NeurIPS 2025 poster ()
Keywords: multiclass
classification
bandit
combinatorial
online
pac
exploration
Primary area: theory
TL;DR: We design a PAC-learner for contextual combinatorial semi-bandits with sparse rewards, with a sample complexity bound that primarily scales with the sparsity parameter rather than the number of arms.

Abstract: We study the problem of contextual combinatorial semi-bandits, where input contexts are mapped into subsets of size $m$ of a collection of $K$ possible actions. In each round of the interaction, the learner observes feedback consisting of the realized reward of the predicted actions. Motivated by prototypical applications of contextual bandits, we focus on the $s$-sparse regime where we assume that the sum of rewards is bounded by some value $s \ll K$. For example, in recommendation systems the number of products purchased by any customer is significantly smaller than the total number of available products. Our main result is for the $(\varepsilon,\delta)$-PAC variant of the problem for which we design an algorithm that returns an $\varepsilon$-optimal policy with high probability using a sample complexity of $\widetilde{O}\big( (\mathrm{poly}(K/m) + sm / \varepsilon^2) \log (|\Pi|/\delta) \big)$ where $\Pi$ is the underlying (finite) class and $s$ is the sparsity parameter. This bound improves upon known bounds for combinatorial semi-bandits whenever $s \ll K$, and in the regime where $s = O(1)$, the leading terms in our bound match the corresponding full-information rates, implying that bandit feedback essentially comes at no cost. Our PAC learning algorithm is also computationally efficient given access to an ERM oracle for $\Pi$. Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors. In the special case of single-label classification corresponding to $s=m=1$, we prove an $O \big((K^7 + 1/\varepsilon^2)\log (|\mathcal{H}|/\delta)\big)$ sample complexity bound for a finite hypothesis class $\mathcal{H}$, which improves upon recent results in this scenario. Additionally, we consider the regret minimization setting where data can be generated adversarially, and establish a regret bound of $\widetilde O(|\Pi| + \sqrt{smT \log |\Pi|})$, extending the result of Erez et al. ('24) who consider the simpler single label classification setting.

From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
Liad Erez
Tomer Koren
Blavatnik School of Computer Science and AI Tel-Aviv University
Blavatnik School of Computer Science and AI Tel Aviv University and Google Research tkoren@tauex, tau. ac. i1l
1iaderez@mail. Pau.ac.1a
Abstract
We study the problem of contextual combinatorial semi- mani-bandits, where input con- texts are mapped into subsets of size m of collection of K possible actions. each round of the interaction, the learner observes feedback consisting of the realized reward the predicted actions. Motivated by prototypical applications of contextual bandits, we focus on the s-sparse regime where we assume that the sum of rewards bounded by some value s < K. For example, in recom- mendation systems the number of products purchased by any customer is sig- nificantly smaller than the total number of available products. Our main result is for the (c, 6) -PC variant of the problem for which design algorithm that returns an o-optimll policy with high probability using a sample complexity of ((pol(((())))))) /m) + sm/ E²) log( [[]] where II is the underlying (finite) class and is the sparsity parameter. This bound improves upon known bounds for combinatorial semi-bandits whenever < K, and in the regime where 0 the leading terms in our bound match the corresponding full-information rates, implying that bandit feedback essentially comes algorithm is also computationally efficient given access to an ERM oracle for II. Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen special case with binary reward vectors. In the special case of single-label classification corresponding an O((K 1/E²) log( (H)/5)) sample complexity bound for finite hypothesis class H. which improves upon recent results in this scenario. Additionally, we consider the regret minimization setting where data can be generated adversarially, and establish a regret bound of O[III++ smm' log [T],, extending the result of [18 who consider the simpler single label classification setting.
cost. Our PAC learning
m we prove
Introduction
In the contextual combinatorial semi-bandit (CCSB) problem, learner is tasked with mapping input contexts from a (possibly infinite) context space X to subsets of a fixed size of a collection of K available actions. The learner's 's reward is defined as the sum of the rewards of the predicted actions, and the feedback revealed to the learner consists of the individual reward values of those actions; namely, semi-bane bandit feedback. The primary objective in this problem is to compete with the best policy in underlying policy class II which is collection of mappings from X to subsets of actions of size m.
A natural application of this problem, and in fact, one of the classical motivating applications for studying contextual bandits (34) is a recommendation system visited sequentially by users (each arriving with side information playing the role of context), where upon each visit the system is
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tasked with presenting a user with set of m recommended products (or ads) available for purchase, after which the system observes the purchased products as feedback. This is naturally viewed as a bandit scenario in the sense that the system only observes the user's behavior with respect to the recommended products and not others. That is, the only way to obtain feedback on a given product by actively recommending it to a user.
In such an application, it is natural assume that each user will only be purchasing up to s s K products, where s is considerably smaller than the total number of products K, which can be very large. This assumption culminates in a sparsity property of the rewards in the underlying combinatorial semi- bandit problem, which raises the question of whether or not sparsity can result in better performance guarantees. More specifically, we are interested in obtaining performance bounds whose leading terms scale primarily with rather than K.
Prior work combinatorial semi-bandits focuses for the most part on the regret minimization objective, with the rate of O (T) obtained by K for the vanilla non-contextual variant, and as remarked in the same paper, is optimal for non-sparse losses. The work of [40] provides first-order regret bounds of the form Om ( where , is the cumulative loss of the best arm in hindsight, and while it may be a significant improvement in cases where the cumulative loss of the best arm is sublinear in T, the bound still contains a polynomial dependence on K. To our knowledge, no prior works on either the vanilla or the contextual variants prove regret bounds which scale with the sparsity s of the losses instead of directly with K.
An important special case of CCSB is the (agnostic) bandit multiclass list classification problem, in which contexts, actions and policies correspond to examples, labels and hypotheses, respectively. In this CCSB variant, the rewards exhibit special structure; namely, the reward of a predicted label is the zero-one reward. Existing work on multiclass list classification focuses on the full-information single-label setting, where given example has a single correct label which is revealed to the learner after each prediction. The primary focus on this literature is on characterizing properties of the underlying hypothesis class H under which various notions of learnability can be achieved; e.g.. PAC learnability [I0), uniform convergence [24] and online learnability (39]. In bandit multiclass list classification, upon predicting list of labels of size m S K, the learner observes partial, a.k.a. "bandit" feedback consisting only of the predicted labels which belong to the collection of s correct labels for the given example|
In the context of traditional multiclass classification (that is, when m = s = 1), extensive research has studied the bandit variant of the problem, starting with the work of [30] who consider linear classification. Follow-up works study various questions of learnability of general hypothesis classes 11 13 44 [9] and other recent works [17 [8] study optimal rates for both the regret minimization and PAC objectives with a focus on finite hypothesis classes. It is thus natural to study the extension of the problem to list multiclass classification with bandit feedback which, to our knowledge, our work is the first to tackle.
For contextual bandits (m = 1) with finite policy classes II, the recent work of [88] characterized the optimal regret; that is, the cumulative reward of the learner compared to that of the best policy in II, and showed that it is of the form O (min + VST, VK7 log [I]),, implying that for relatively small policy classes the classical VKT rate of EXP4 (5) can be improved if < K. In subsequent work. [17 study the PAC objective in single-label bandit multiclass classification (s = m 1) where the goal is to learn a near-optimal hypothesis with respect to some unknown data distribution, and establish sample complexity bound of O(KK* + 1/ log({H1/8)) for (s, 8)-PAC learning in the single-label setting using computationally efficient algorithm given an ERM oracle to H. One of the key takeaways from both of these works that the single-label setting, bandit feedback essentially comes at no additional cost compared to full feedback in the asymptotic regimes where
T co and &
We are thus motivated to investigate the following more general question: what is the role of reward sparsity in contextual combinatorial semi- remi-bandis?? In this work, we provide an answer to this question by designing PAC learning and regret minimization algorithms for CCSB with finite policy classes, and prove that they attain sample complexity and regret bounds whose dominant terms scale with the sparsity parameter s rather than K.
In the wider context of CCSB, this feedback actually corresponds to semi-bandit feeddbbaa defined earlier.

---

To illustrate the challenge in answering this question, let consider the naive approach for PAC learning in CCSB by which subsets of actions of size are sampled uniformly at random, and bandit feedback is used to estimate the rewards of policies in II via importance sampling. Since the variance of such reward estimators scales polynomially with K, this approach ultimately results in a sample complexity of = Km/s². This bound is far from optimal since, as we will show, the leading term in the optimal sample complexity bound in fact scales with instead of K.
1.1 Summary of Contributions
We summarize results for contextual combinatorial semi semi-bandits over finite policy class II:
where we design an algorithm that with probability least 1 1-6 5 outputs a policy Tout that e-optimal with respect to the population reward, using a sample complexity of at most
Our main result involves the PAC setting (see Section B
o(
poly
K
sm
log
8
Moreover, our algorithm is computationally efficient given an ERM oracle for IT. We also present the high-level construction of sample complexity lower bound of (2mm/ which holds even for a single context, showing that the dominant term in our bound is in fact optimal. As an immediate corollary, the above results hold in the special case of bandit multiclass list classification with s-sparse rewards over finite hypothesis class.
In the special case of single label bandit multiclass classification corresponding m = 1. we show that a slight variation of our approach results in a sample complexity of O(KK² + 1//²) log()H(18)), which has improved dependence on K compared to the exist- ing bounds in [17]
We also consider the online regret minimization setting, where we design an algorithm achieving an expected regret bound of [ ssm7 log [I],, which holds even when the input and reward sequence is adversarial. See Appendix for more details.
Our starting point for addressing the PAC setting in CCSB is the recent work of who study the single-label (s m 1) classification setting. Following the general scheme they proposed, our algorithm operates in two stages by first computing a low-variance exploration distribution over policies in II and then using this distribution to uniformly estimate the policies' expected rewards. Generalizing the single-label classification setting to CCSB, however, comes with some nontrivial technical challenges. First, [17 use the single-label assumption in order to collect labeled dataset by uniformly sampling labels. In the general setting, however, this approach cannot work effectively, since the full reward function cannot be inferred unless the predicted set contains all correct labels, which a very unlikely event. We circumvent the issue by introducing additional importance sampling estimation with appropriate modification of the convex potential in use. Moreover, means to compute a fow-variance exploration distribution, rather than using a stochastic optimization scheme suggested in [17]. we optimize empirical objective and use Rademacher complexity arguments in order to establish its uniform convergence to the expected objective given sufficient samples. This approach allows us in particular improve the overall dependence K in the single- label classification setting, leveraging refined Las vector-contraction results for the Rademacher complexity (1
1.2 Additional Related Work
Combinatorial semi-bandits. The non-contextual variant of the combinatorial semi-bandit problem was introduced by (33 in the framework of online shortest paths. This problem has been extensively studied in the bandit literature, mostly in the context of regret minimization [3]
48
33
40
47 27
etc.]. A regret bound of O O(vmK7) was shown by for adversarial losses, and was proven by [36] to be optimal in the multiple-play setting in which the available combinatorial actions are all subsets of size m of the action set (which is the setting considered in this paper). The contextual combinatorial semi-bandit (CCSB) problem is considerably less explored, with some existing works
46 49 focusing on the case where rewards are noisy linear functions of the inputs, and others
45
48
31 32 which consider setting similar to ours with finite unstructured policy classes, and
3

---

establish regret bounds of the form O(ymKT log [T].. To our knowledge, all previous results on combinatorial semi-bandits exhibit a polynomial dependence on K in the leading term, thus leaving open the question of adaptivity to reward sparsity.
Combinatorial (full-)bandits. Another well-studied variant of CCSB is known as combinatorial bandits (also referred to as bandit combinatorial optimization, [38 61), where the feedback is limited only to the realized reward, that is, the sum of rewards of predicted actions. For the non-sparse version of the problem, regret bounds of (m have been established in several previous
works 12 I 8 9 (5) and have subsequently been shown to be optimal [1] (8). In the context of multiclass classification, while perhaps not as natural as semi-bandit feedback, full-bandit feedback is well-motivated in some applications, for example, in cases where recommendation system is interested in protecting the users' privacy by only observing the amount of products purchased rather than the products themselves. While our results apply in the semi-bandit model, examining the full-bandit variant raises some very interesting questions and generalizing our results to this setting seems highly non-trivial; see Section 4 for further discussion.
List multiclass Classification. The theoretical framework of multiclass list classification was originally introduced by 17]. (10) provide characterization of PAC learnability for multiclass list classification by generalizing the DS-dimension [4]. (39] consider the regret minimization setting and characterize learnability by a generalization of the Littlestone dimension, and [24] study the notions of uniform convergence and sample compression in the context of multiclass list classification. A praression-variann of list learning has also been studied in 442 who provide characterization of learnability for this problem. Notably, all of these works on multiclass list classification focus on the single-label setting.
Bandit multiclass classification. The setting of bandit multiclass classification was originally introduced by [30, with (IS] showing that learnability of deterministic learners in the realizable setting is characterized by the bandit Littlestone dimension. [13] generalize those results by showing that the bandit I. Littlestone dimension characterizes online learnability whenever the label set finite,
and [44] generalize this result to infinite label sets. Several previous works 4 15 37 study the price of bandit feedback in the realizable setting, with the recent work of 19 showing that this price
bounded by a factor of (K) over the mistake bound in the full-information setting for randomized learners.
2 Problem Setup
We study a learning scenario where a learner has to map contexts from a domain X to subsets of size of collection of K 2 m possible actions, denoted by y & [K]. We denote by A A {a E {0. 13KK ||a||| = m) } the set of available combinatorial actions. In the remiibandit setting, the learner iteratively interacts with environment according to the following, for r = 1.2....
(i) The environment generates a context-reward vector pair (x,,r;) where x, E X and r, E [0. 1] the learner receives xy;
(ii) The learner predicts a, E A;
(iii) The learner gains reward r, (namely the sum of rewards of predicted actions) and observes
semi-bandit feedback consisting of the rewards of the predicted actions (rr(y) y E ar).
We assume that there is a known bound s K on the Lı-norm of all reward vectors, that is, ||r: s s for all F We remark that since ()) E [0. 1]. this sparsity condition also implies that ||r; S s. In the settings we consider, the learner's performance measured with respect to an underlying policy class II C (X + A); focusing in this work on the case where II is finite.
PAC setting. In the (s, 6)- setting, the context-reward pairs (xy, ry) are generated in an i.i.d manner by some unknown distribution D. The learner's goal is compute, using as few samples as possible, a policy Rout E II such that with probability at least - (over all randomness during the
PI some formulations, the available actions come from a fixed, arbitrary subset of A; here we facus the setting where all subsets of y of size m are valid. Thiss notion of sparsity is weaker than striet sparsity, where the rewards have most nonzero coordinates.

---

interaction with the environment).
TD (D ( rD (ouut) S 8,
where (T) [(, xx)) and x² argmax æEll P2 (πt) is the population reward of and r a argmax=e11 (z) ) the best policy in the class w.r.t. D. The learner's performance this setting is measured in terms of sample complexity, that is, the number of samples (xt, generated by the environment during the interaction as function of (s, 6) after which the learner outputs a policy You satisfying the guarantee above.
Regret minimization setting. In the online regret setting, the pairs (X,, 12) are generated by an oblivious adversary The interaction lasts for 7 rounds, where in each round I, after predicting a, E A, the learner gains reward rr(a,) - dr E [0, s]. and the objective is to ultimately minimize regret with respect II, defined
Ry - sup xlell
r n (x,)
ar.
F=1
ERM oracle. To discuss the computational efficiency of our PAC learning algorithm. we assume access to an empirical risk minimization (ERM) oracle for II. This oracle, denoted by ERMm, gets as input a collection of pairs = {(x1.)) f.). fn)) S X x R and returns
1
ERMI (S) E argmax xell
Σ
Σ (EX(X)
P.ly).
This is a natural gencralization of the optimization oracle used in previous works on contextual bandits [16, 2]. When we refer to the computational complexity of our algorithm, we assume that each call to ERMI takes constant time.
The semi-bandit multiclass list classification problem is special case of CCSB, with the following specialized notation: The set of all lists (subsets)) of y of size is denoted by L. and instead of policy class refer to hypothesis class H C (X L). In every round f of the interaction, the environment generates pair (X,, Y,) where x, E X and Y, s y where Y, corresponds the set of all true labels at round We assume that [Y,] for all for some known bound which corresponds to reward sparsity in this setting. Upon predicting a list L, L. the learner observes semi-bandit feedback consisting of Y, which corresponds the zero-one reward values for all labels in dr.
Bandit Multiclass List Classification.
Main Result: Agnostic PAC Setting
In this section we design and analyze PAC learning algorithm for CCSB with s-sparse rewards. Our algorithm is displayed in Algorithm D and our main result is detailed in the following theorem:
k Theorem If we set y 1. N₁ ã m
log((11166)), N₂
@((K/mi [ms + sm/e") log((
T (((K(m())))))))) /m)m) then with probability at least 1 ô Algorithm outputs Tout E II with En (x*) TD (out) I & using a sample complexity of
00(
K m8
sm
||I
N1 *1+No N1+N2=
log
82
Furthermore, Algorithm makes a total of T OO(K/((K//// ((((K))) )) calls to ERM1-
In Appendix A.3 show that in the special case of single-label classification (corresponding to = m = and zero-one rewards), specialized version of Algorithm results in a sample complexity bound of
olx
[H]
k"
log
We consider oblivious adversary throughout, though most of our results extend to adaptive adversary.
5

---

Algorithm PAC-COMBAND N2, (0, $1, T N.
Parameters:
Phase 1:
for
I...,,, do
// Environment generates (x) D, algorithm receives Xy. Predict a, E A uniformly at random and receive feedback (n(() | a.). end for
Initialize E Ån to be delta distribution.
for I.. do
Let qr E An be the delta distribution on q, ERMM ((xx,)))) where
(1- K K (lyyaa)))))))
(()) N1
vi (M
(xi)
Update Pi+1 = p) 1/4 where 77 = =2(221)).
end for
Let 0 Pr+1.
Phase 2:
for =rri=l. aari=,......
N2 do
// Environment generates (x), D, algorithm receives xy-
With prob. pick E A uniformly at random; otherwise sample ~ á and set aj = (x)). Predict a, and receive feedback (ri(y) e a.).
end for Return:
Tout ERMM ((xx)))))) where P.()) 1( Hyaa)))) Vyey.
(%.,
which has an improved dependence on K compared to the bound obtained by [17 which scales as K
Given context-action pair yx,y) X x y and p E An & {pp |pE
Σ |T| Pi 1/ denote
(xy(p) &
Σ xell
((T)((yExxx)),
i.e., the probability that y belongs to xxx when sampling x p. and given (0, 1) we define
(p) (1 y)xx(( + ym/ K,
that is, the distribution induced by mixing p with a uniform distribution over A.
At a high level, our algorithm initially uses the Frank- Wolfe algorithm to approximately solve the following convex optimization problem:
1 N
minimize F(p) A
Σ f(ptz) p An. Ni
(1)
where
10;:2=xx,,,
K
Σ r(y) log((%))))) yea
(2)
Here D' is the product distribution over Z - X [0, K| A defined as D' & Un) that is, a pair (x, E X x [0, 1] is sampled from D and a A is sampled independently uniformly at random. The random objective f(::2) is defined according to Eq. (2). and we note that even though the full reward function is not observed, z(: depends only on the reward of the actions in A and can thus fully accessed. The K/m factor Eq. 2 is necessary due the random sampling of A used for importance-weighted estimation of the reward function, and it is straightforward to

---

see that the expected objective has the following form:
F(p) -====> (
[rb)log((i,
yey
This form F is of crucial importance as its gradient at point is proportional to the variance of appropriate unbiased reward estimator for the policies in II:
OF
Var Var[Rp(Cr ( s
(p) Öpj
Vx EI.
As we will show, poly(K/m) samples suffice in order for the empirical objective F to approximate the expected objective F()) with sufficient accuracy uniformly over An. resulting in the fact that an approximate minimizer á E An of F(.) satisfies ||VF())]l>> $ This fact generalizes the key insight from the previous works of [16 2 17 in the sense that the reward estimators induced by have variance bounded by C sm, where
an absolute constant. Crucially, this variance bound doesn't I depend directly on the number of actions K, implying that we can use á to estimate the expected rewards of the policies in II with only sm/e² samples by Bernstein's variance-sensitive concentration inequality.
3.1 Analysis
Here detail the main steps in the analysis of Algorithm and in particular, outline the main challenges compared to the single-label setting where s m
Initial exploration. While in the single label classification setting it is possible to collect a dataset containing poly(K) K) i.i.d samples from D by simply predicting labels uniformly, this approach does not work in the multilabel classification setting (i.e. rewards. The reason that in these settings a uniform prediction of a list of actions will simply not yield full observation of the reward vector, collecting a dataset, we use semi-bandi feedback directly in order to estimate the convex objective of interest using importance sampling, as detailed in Algorithm [ These random objectives are unbiased with respect to F(-) defined in Eq. 33, while importance weighting adds a scaling factor of K/m. An additional noteworthy difference
1) and neither in CCSB with s-sparse
after poly(K) (K) such predictions. Thus, instead of
our approach is the fact that rather than using stochastic optimization procedure to minimize the stochastic objective in Eq. (3) directly, we optimize the empirical version of this objective and use a uniform convergence argument to show that an approximate empirical minimizer also achieves nearly optimal expected function value. Our uniform convergence analysis of the underlying function class leverages Loo vector-contraction properties of Rademacher complexities introduced in 20 see Appendix A. for more details.
Optimizing for low-variance exploration. In order to approximately solve the convex optimization problem defined in Eq. (T), we employ the Frank-Wolr (FW) algorithm [22], and make use of properties of the objective. In more detail, we run Frank- Wolfe on the objective defined in Eq. (I) over samples generated by the distribution D', where crucially the gradients of the random objectives defined in Eq. (2) can be calculated exactly via
convergence result by [29 which allows us take advantage of L felLL=-Smothhn
0 (f(p;x,r,a) = -1
16 (x) Σ
[[]].
0p;
(k,(p)
VEG
The FW algorithm uses these gradients with a linear optimization oracle LOOn, defined by
LOOn(v) - argmin
Vy W
peán
Importantly, each call to LOOn can be implemented by a call to ERMI (see Appendix A.2 for the proof). The analysis 29) applied to the objective Eq. ① shows that with an appropriate choice of parameters, the Frank-Wolfe algorithm outputs μ=aaproximate minimizer of Eq. (T) after
((s22/(ym²))) iterations. This follows from L---smoothness properties of the functions defined in Eq. 2 with smoothness parameter = sk3 ( For more details, see Appendix A.2
7

---

Low-variance reward estimation. In the second phase of Algorithm we use the low-variance exploration distribution P e Ån computed the first phase in order estimate the expected reward of all policies in IT using sepportance-weigheee estimators, defined as
my)](ye ai) ie [N2].
Σ ye (p)
(x(T)=
The guarantee on á provides us with the ability to bound the variance of these estimators by O(sm) (with no explicit dependence K) which is why, using Bernstein's 's inequality, ((K/(m)) sm sm/e²) samples in the second phase are sufficient for the average estimated rewards to constitute g- approximations of the true rewards uniformly over all policies in II, thus implying the PAC guarantec for the policy which maximizes the average estimated reward.
Proof of Theorem 7 (sketch). We now give overview of the proof of Theorem [ following key lemma which shows that a sufficienlly approximate optimum P of the convex objective defined in Eq. (3) is point at which the gradient is bounded in Loo norm by The proof of this lemma can be found in Appendix A
We rely the
Lemma 1. Suppose S and let P E An be an approximate minimizer of the objective F(.) defined in Eq. up additive error of u. Then,
2spk2
IVF()) S
y2m2
In particular, setting m² /2K² gives ||V(()) s 2s.
order to apply Lemma we make use uniform convergence argument which implies that given sufficiently many samples, an approximate minimizer of the empirical objective defined in Eq. (T) is also an approximate minimizer of the stochastic objective defined in Eq. (3). This lemma is also proven in Appendix
[II log 5.) and that phase I of Algorithm 7 results in P E An which minimizes F-) defined in Eq. up an additive error of p/3, Then probaaibiy least
Lemma 2. Assume N1 = O 5 g2
minimizes F..) defined in Eq. up to additive error of μ.
In Appendix A.2
prove that T Ols ((sK2/(y2m²xp) p)) iterations of FW result in E An that minimizes F (-) up to accuracy 3/3. Setting μ sy"mm² m2'mm//2K /2K?, Lemma and Lemma imply that Mrrrithhmmyilsss... yields distribution p Δд satisfying
phase of Algorithm
(xxr)
Σ
r(y)
4s EI
(5)
2x,
yEx(X)
In phase 2, Algorithm I uses samples from P estimate the expected rewards of policies in with the following estimators:
Ri(T) & Σ m ie [N2].
(t)
yER(x)
straightforward to see that this is an unbiased estimator for (z),,, and moreover, using the Cauchy-Schwer inequality and Eq. (5) its variance can be upper bounded by
Tz(y) (n)
Var (T)] S mE
Σ yYE(())
S 4sm.
Using Bernstein's inequality and the fact that the random variables (,T) are bounded by K K/(ym) we deduce that the following sample complexity suffices for (8, -PAC:
Ni N₂ @
K
K
sm
n log
8
mE
8
and second term can be dropped since the sum of the other two terms dominates the bound.

---

2 below, see the formal statement and proof in 3.2 Lower Bound
conclude this section with presenting lower bound, according to which the dependence on m and in Theorem iis tight even in the non-contextual setting.
Theorem 2. For wny combinatorial semi-bundit algorithm Alg over K actions and combinatorial actions of size m K/2, there exists an s-sparse instance for which in order for Alg to output à A which is e-optimal for < K/K with constant probability, Alg requires sample complexity of at least (sm/66²)
We provide a sketch of the proof of Theorem Appendix A.4
Proof of Theorem (sketch). Consider instance specified by Berouuli arms with expected reward *+ + & each while the other K m arms have expected reward g K-mi Denote the set of m arms with highest expected reward by S. Now, note that in order find an 5-optimal subset, Alg must identify at least half the arms in S, and thus required to estimate of the arms' rewards up accuracy of E Since each arm's reward distribution has variance of x. the number of
is Var(r,) [s/m)² * . mx" Since
samples required to make such estimation of the reward for each
such an estimation needs to be performed for all K arms and each time step gives Alg samples for m arms via semi-bandit feedback, the total sample complexity is of order at least
8
m²
sm
K
E g
4 Conclusion and Open Problems
In this work, we provide sample complexity bounds for contextual combinatorial semi-bandits whose dominant terms scale with an underlying sparsity parameters rather than with the number of actions K. We also give regret bounds for the online (adversarial) version of the problem. Our results apply the special case of bandit multiclass list classification, and constitute generalization of previous work on the single-label classification setting [17 [8].
Our works leaves several compelling open questions, such as the extension of our results to the full-bandit setting, improving the dependence on K the sample complexity bound, and extending our results to infinite policy classes, For further discussion of future directions, see Appendix C
Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council. Neither the Europcan Union nor the granting authority can be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant numbers 2549/19 and 3174/23), grant from the Tel Aviv University Center for Al and Data Science (TAD) and from the Len Blavatnik and the Blavatnkk Family foundation.
References
[1] J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263-274. Citeseer, 2008.
[2] A. Agarwal, D. Hsu, S. Kale, J. Langford, I. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages
PMLR, 2014.

---

[3] J.-Y. Audibert, S. Bubeck, and G. Lugosi. Regret in online combinatorial optimization. Mathe- maties of Operations Research. 39(1):31 2014.
[4] Auer and P. M. Long. Structural results about on-line learning models with and without queries. Machine Learning, 36:147-181, 1999.
[5] Auer, N. Cesa- Bisa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77 2002.
[6] B. Awerbuch and R. D. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 45-53, 2004.
[7] N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Ychudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943-99999 955. IEEE, 2022.
[8] S. Bubeck. N. Cesa-Bianchi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings, 2012.
[9] N. Desa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 40401422, 2012.
[10] M. Charikar and C. Pabbaraju. A characterization list learnability, In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1713-1726, 2023.
[11] A. Cohen, T. Hazan, and Koren. Tight bounds for bandit combinatorial optimization. In Conference on Learning Theory, pages 629-642. PMLR, 2017.
[12] V. Dani, S. M. Kakade, and T. Hayes. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007.
[13] A. Daniely and T. Helbertal. The price of bandit information in multiclass online classification. In Conference on Learning Theory, pages 93-104. PMLR, 2013.
[14] A. Danicly and S. Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287-316. PMLR, 2014.
[15] A. Daniely. S. Sabato, S. Ben-David and S. Shalev-Shwartz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
[16] M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXiv:1106.254: 2011.
[17] L. Erez, A. Cohen, T. Koren, Mansour, and S. Moran. Fast rates for bandit pae multiclass classification. arXiv preprint arXiv:2406. 12406, 2024.
[18] L. Erez, A. Cohen, T. Koren, Y. Mansour, and S. Moran. The real price of bandit information in multiclass classification. arXiv preprint arXiv:2405.10027 2024.
[19] Y. Filmus, S. Hanneke, I. Mehalel, and S. Moran. Bandit-feedback online multiclass classifica- tion: Variants and tradeoffs. arXiv preprint arXiv:2402.07453, 2024.
[20] D. Foster and Rakhlin. f_(ea) vector contraction for rademacher complexity. arXiv preprint 1xXiv
2019.
[21] D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan, and B. Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, pages 1319-1345. PMLR, 2019.
[22] M. Frank, Wolfe, et An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2)995-110, 1956.
10

---

[23] A. György, T. Linder, G. Lugosi, and G. Ottucsák. The on-line shortest path problem under partial monitoring, Journal of Machine Learning Research, 8(10), 2007.
[24] S. Hanneke, S. Moran, and W. Tom. List sample compression and uniform convergence. The Thirty Seventh Annual Conference on Learning Theory, pages 2360-2388. PMLR, 2024.
[25] E. Hazan and Z. Karnin. Volumetric spanners: an efficient exploration basis for learning. Journal of Machine Learning Research, 2016.
[26] E. Hazan et al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):1573355, 2016.
[27] S. Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. Advances Neural Information Processing Systems, 34:2654-2667, 2021.
[28] Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-I. Kawarabayashi Improved regret bounds for bandit combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[29] M. Jaggi. Revisiting foofk-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pages 427-435. PMLR, 2013.
[30] S. M. Kakade, S. Shalev-Shwartz, and A. Tewari. Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th international conference on Machine learning. pages 440-447, 447, 2008.
[31] S. Kale, L. Reyzin, and R. E. Schapire. Stn-stochastic bandit slate problems. Advances in Neural Information Processing Systems, 23, 2010.
[32] A. Krishnamurthy, A. Agarwal, and M. Dudik. Contextual semibandits via supervised learning oracles. Advances In Neural Information Processing Systems, 29, 2016.
[33] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combina- torial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543, PMLR, 2015.
[34] J. Langford and T. Zhang. The information. Advances in neural information processing systems, 20, 2007.
algorithm for multi-armed bandits with side
[35] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[36] Lattimore, B. Kveton, Li, and Szepesvari. Toprank: A practical algorithm for online stochastic ranking, Advances in Neural Information Processing Systems, 31, 2018.
[37] M. Long. New bounds the price of bandit feedback for mistake-bounded online multiclass 1.007.
learning. Theor. Comput. Sci., 808: 608:159-163, 2020. doi:
[38] H. B. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In Learning Theory: 17th Anmual Conference on Learning Theory, COLT 2004, Banff. Canada, July 1-4, 2004. Proceedings 17, pages 109-123. Springer, 2004.
[39] Moran, O. Sharon, I. Tsubari, and S. Yosebashvili. List online classification. The Thirty Sixth Annual Conference on Learning Theory, pages 1885-1913, PMLR, 2023.
[40] G. Neu. First-order regret bounds for combinatorial semi-bandits. In Conference on Learning Theory, pages 1360-1311 PMLR, 2015.
[41] F. Orabona. A modern introduction to online learning. arXiv preprint arXiv: 1912. 2019.
[42] C. Pabbaraju and S. Sarmasarkar. characterization of list regression. arXiv preprint arXiv:2409. /9218, 2024.
[43] L. Qin, S. Chen, and X. Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. Proceedings of the 2014 SIAM International Conference on Data Mining, pages 461-469. SIAM, 2014.

---

[44] A. Raman, V. Raman, U. Subedi, and A. Tewari. Multiclass online learnability under bandit feedback. arXiv preprint arXiv:2308.046220 04620, 2023.
[45] Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[46] K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga, N. Kakimura, and K.-i. Kawarabayashi. Near-optimal regret bounds for contextual combinatorial semi-bandits with linear payoff func- tions. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 9791-9798, 2021.
[47] C.-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR, 2018.
[48] Wen, Kveton, and Ashkan. Efficient learning in large-scale combinatorial semi-bandits. In International Conference on Machine Learning, pages 1113-1122. 122. PMLR, 2015.
[49] L. Zierahn, D. van der Hoeven, N. Cesa-Bianchi. and G. Neu. Nonstochastic contextual combinatorial bandits. In International Conference on Artificial Intelligence and Statistics, pages 8771-8813. PMLR, 2023.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
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 theoretical claims made the abstract and introduction are all rigorously proven in the paper, and the scope of the paper's contributions is accurately reflected in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
13

---

The limitations of the work are thoroughly discussed both in the introduction and throughout the text, and the assumptions made are formally stated in the problem definition.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors 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 on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Every theoretical result is rigorously proven either in the main text or in the supplementary material. All assumptions are formally stated in the problem setup.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged 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 it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theoretical paper and does not contain any experimental results.
14

---

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 urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
This is theoretical paper and does not contain any experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS 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, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
hhipss.c//ublic/uuudds htwpee///oooeSeeeeeoeoooooo
www.obiiiiiiioooooooiiooo for more details.
The authors should provide instructions 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 are omitted from the script and why.
15

---

At submission time, to 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 is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
This is theoretical paper and does not contain any experimental results.
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, 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 is theoretical paper and does not contain any experimental results.
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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or 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 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 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 the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is theoretical paper and does not contain any experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics atttps://neur// cttppp/blce.tiiiicc....eleeellll
Answer: [Yes]
Justification: The research conducted in the paper is purely theoretical and conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The research conducted in the paper is purely theoretical is not tied to any specific applications with societal impacts.
Guidelines:
The answer NA means that there 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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
17

---

Answer:
[NA]
Justification:
This is theoretical paper and does not contain any experimental results.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do 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 is theoretical paper that does not contain any experimental results and does not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
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.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pwpprswithhaeecoc thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pan se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out 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 is theoretical paper that does not contain any experimental results and does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
18

---

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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper is purely theoretical and does not involve crowdsoureing 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 to the NeurIPS Code of Ethics, workers involved 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
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper is purely theoretical and 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.
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 the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The research conducted the paper does not involve LLMs as any non- standard component.
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 our LLM policy http://///errreccc/////oeerrrers for what should or should not be described.
19

---

A Proofs for Section 3
To prove Lemma T we will need the following auxiliary result:
Lemma 3. Suppose y $ 2 and let p* = argminpean F(P). Then it holds that [VF(p))lla s.
Proof. First note that the gradient of F(.) is given by
(y
(VF()), =E Σ
(p)
yey
Thus, using first-order convex optimality conditions, the following holds that for any p E An.
VF(p") (p-p*) 0,
which with the explicit form of the gradient becomes
Σ yEy
(1- y)(y)
(2,)(1*)
or equivalently, after dividing by 1 - y,
(p) (x*)
E
S0,
(xn)(
yEy
which rearranges to
E
Σ yey
SE Σ r(v) = E[]]]]] s.
(x*(
yEy
Letting An be the distribution concentrated some II, get
(1-M) Σ (()
yEy (xy(pt) E
S..
and the claim follows since the left-hand side equals (-VF(p*)), and is nonnegative.
Proof of Lemma] 1 Using Lemma 3 and the triangle inequality, it suffices to show that
2suK² y2m²
||V(()) - -F(p")l = V
and by the assumption on & this clearly holds if
2sK² (VF(()) VF(p")
(F( F(p*)).
y²m²
20

---

To prove this inequality, we start with the left-hand side and use the explicit form of VF(()::
(() 2
x())
(VF( - VF(p")
max
y)²
E Σ
E Σ
NEll
(xy(1)
2xy(p*)
YEy
yey
r(y)
Σ
r(y)
yey 2x. (f)
yey (pt)((*))
E |r|l]
Σ
r(y)
vEy ||]||
(% (p*)
$ ||r||
Σ r())
(2)) (pt)
yey
S s E
Σ
r())
(6)
(2)
(x.)(**))
yey
where we used Jensen's 's inequality twice and the fact that |||||| S Now, for any (x,y) E X x y it holds that
2
-
(0)
(2)(()) (p*)
(0%, ( (p²))
K2
|1
ex Ck)(())
2
( (x*)
s y²m²
min
(x*)
2x (0)
where we have used the fact that O% 2 ym/k K. Using the fact that 1 (1- 1/2)² s
log + z 1 with z = 2% ( (p*) (see e.g. [17]. Lemma 4) we obtain, after combining the
above with Eq. (6) and taking expectations:
2sK2 y2m²
(ly(P) (p) - (p) (xy(
(VF( - VF(P") =
E
Σro) log
(xy((*))
yE.
2sK²
Ex-D' [f(p,)) - f(p", -Vf(p" - (p-p")
2sK²
(F(p) -(p==(((===F)
vF(p") p^))
y2m
2sK² (F()) F(P*))
s y
where in the second inequality used first-order optimality conditions.
Proof of Theorem] 7 By Lemma
Theorem and Lemma
2 phase of Algorithm I results in
distribution & An satisfying
(V)(yEx(()) yey (2
(1 (
Σ
S 2s Vx II,
and since y = 1/2 we get
Σ
r(y)
E(xr))D
4s
Vx E II.
(
(x)())
21

---

Fix π E II and for i E [N2] define the induced importance- reward estimator by R₁(x) = (yea))
Σyea(x) 22 (p) This is unbiased estimator of r (x)), since for given y y the probability that y a; equals (x.)()), and thus
[[R =
r()) yEx(())
Σ
E(r x()x=(xx]==))))) = ro)
Moreover, Rí (z),...... RN.............. (r)) are i.i.d and exhibit the following variance bound:
(ar[R((T) (x)] (x)
Ty) e
Σ
(
yER(X))
m
y
r E a (x)
Σ
mE
(
rily)
Σ
mE
S 4sm,
e 2
yER(X)
where in the first inequality use Jensen's inequality. With the variance bound, Bernstein's inequality (e.g. (35), page 86) and the fact that the random variables (x) are bounded by K/ K/(ym) to deduce that the following sample complexity suffices to have rD D I with probability
at least 1
@
K 8
K
sm g2
Ni N2
log
8
and the proof is concluded once we note that the second term can be dropped via Young's inequality which shows that the sum of the other two terms dominates the bound.
A.1 Uniform Convergence via Rademacher Complexity
Consider the ERM objective F An - R defined as
F(p) 1 Σ (ptz)), p An. i=1
where 2(p;z) is defined Eq. (2) and Z1... In are sampled i.i.d. from the distribution D' over Z. Denote by T Z + R.} the underlying class of models, that is,
F (++ f(; p E An).
For each z = (x,r, a) Z we define the binary matrix Z E (0, 1 by
Zy,x - 1(y π(x)), Vy M II.
With this notation, we note that the objective can be written as
f(p:== (x,r,
K
Σ ((y)
log
ym +1- (1)))
K
yea
Thus, given y y, we define the function
(-) R.
R by + - )uy))
(u)
log
ym K
u E R
22

---

so that
f(p:2) = [ r
yEa
Note that for each E y, the function class Ly defined by
Ly =z + (Zp) p An).
is class of generalized linear models, as (Zp) only depends on the inner product between and the y'th row of the matrix Z. Now, given a dataset (zn 2n) complexity of F with respect to S is defined by
Z", the Rademacher
" Σ o
R(F 5) E
sup Peòn
where Up.....Or are i.i.d Rademacher random variables (that is, #1 with probability f). make use of the following uniform convergence result over the function class F in terms of its Rademacher complexity (see e.g. (45)).
Lemma 4. Assume that If(] B for all f F. Then with probability at least - over S (D')",
for all p E An it holds that
2 (4g/)4
F(p) - F(p) s 2R(F o 5) 4B
Note that for our function class of interest F, we have B s sK log
K
ym
The following key lemma will allow us to obtain bound on the Rademacher complexity of F by presenting the functions in the class as linear combinations of -ep-iscchi functions, and using the result given 20 to relate its Rademacher complexity to that of generalized linear models.
Lemma 5.
Let S E Z" where log [[]. Then,
sK2.5
log III
R(F 5) 0
log? n
m²
n
Proof. Fix dataset S E Z" We first write the Rademacher complexity of T with respect to S as follows:
RR(F S) = E.r
sup Pελn
Err
sup PeAn
(Zip))
where $1..... On R defined by
(u) = Σ (,))),( HER K
yEa,
Using the L.s contraction argument given by Theorem I of 20 it holds that
Eg sup Σ (io((Zip) s o(GVK) max sup E sup Σ (Z log n, peAn
yey S' PEán
where 11, ......, Ane are G-Lipschitz with respect to the norm. Moreover, the expectation on the right-hand side is the worst-case Rademacher complexity of a linear model that bounded by in Ln-mo over data which is bounded by in Lorm. Using standard Rademacher complexity arguments (e.g. Lemma 26. 11 in (45), this expression bounded by
max sup Er sup oi P $ log(2)I)
ye.y S Z PeAn Fa1
23

---

It is now left to bound the Lao -ipsschch constant of the functions .I,..., on. For all ut v R and i [n], we have
1di(u)
0;(1)==
Σ (M))) -
year
Σ (u) - |,((1)
year
max
y (1) (r)l/
yay
where we used the fact that ||ra|| S s. Now, for each y y, it holds that
à
K
y
K²
(w)l1
Juy w (
ym K
+ (1 y)
ym²
Therefore, using Hölder's inequality.
K² ym?
( (v)] s
||u vll
and we deduce that G z *k ym?
which concludes the proof.
We can now use Lemma and Lemma 5 to prove Lemma
Proof of Lemma Let Ån be the output of Algorithm 2 when run on F()) using the dataset
S of i..d. samples from D' and assume that F(p) F(p) n/3 for all An- Let p. argmin peAn F(p). Then with probability at least 6,
F()) - F(p) F(D) F(p) + F(t) F(p)
F(p) - F(p)+ F(p) F(p) + 2
log log(2/0)
F()) F()) 4/3 B
2n
where the first inequality uses the fact that -apprxxxmmte minimizer of F(-) and the second inequality follows from Hoeffding's s inequality with B = = log(K/( (ym)) being a bound on both the empirical and the expected function values. We now use Lemma to further bound the suboptimality of by
2log(4/8) P
F( F(p) 2R(FF a 5 S)+ 5B
The proof is now concluded using Lemma once we note that if T above is bounded by μ.
then the m
s'K*
log((11166))
A.2
The Frank-Wolfe Algorithm
We now present the details of the Frank-Wolff optimization algorithm used to obtain approximate minimizer of the objective defined in Eq. (I) The algorithm operates under the classical convex optimization model:
minimize
F(w), NEW.
where W S Rd is convex domain. We assume that the algorithm has access the full gradients of the objective, that is, it has access to (F(w) for each w E W. We assume the objective satisfies the following L Smmoothhsss condition:
For all u, w W and it holds that F(w) F(n) VF(1) u) fll =Il
Applying the generic result of given Theorem of [29] the objective defined in Eq. (T) we
obtain the following result stating the rate of convergence and oracle complexity of Algorithm

---

Algorithm 2 Frank-Woo Wolfe
Parameters: Objective F: An B,, step sizes (nch- Initialize p1 E An- for 2.. do
Let 8: VF(p:). Compute 4, LOOn(
Update p++1 (1 - 7h)p; + 4/4
end for
Theorem 3. Let p² = argmin pedn F(p). Then Algorithm Ån with F s μ within iterations, where
with step sizes = 22(2+11 ( 1) outputs
T= 0 sK3
In particular, Algorithm
2 makes most 0 (sK3/(y2mm m(y²m/()) x)) calls LOO.
Proof. Using Theorem of [29]. it suffices to prove that the objective F(-) defined in Eq. the following L, -moothhnsss property: propettt
| satisfies
sK3
[VF(p)) - VF(g))l
y2m3 1lp 9ll1-
Indeed, observe that for all II:
((F(P)) -VF(())
K Σ r(y)
sup
(x)(()
(%,((1)
Z yEa
y) K
Σ r(y)
sup ==(x.r,a)EZ m
(1 y)-
0 (p)(())0))0)))
yea
sK3
llp
4/11.
m
where we have used the fact that ||r|| 1 s.
The following lemma asserts that each call the linear optimization oracle in Algorithm can in fact be implemented by call to the ERM oracle ERMI-
Lemma 6. Algorithmm 2 with the objective defined in Eq. (T. each call to LOOn can be imple- mented via a single call to ERMI-
Proof. For each 1,2.... holds that
LOOn(g:) argmin peλa
v ((())
argmin
N
pcdn
i=1
Ni
argmin
(f
N
argmax nell
Σ
P((r)
(xx(
where Pr(y) (1, y) K ((yeat)r))) by Eq.
(p.)(Pt)
25

---

A.3 Improved Rate for the Single-Label Setting
We now present version of Algorithm | specialized for the single-label classification setting, and show that it enjoys sample complexity guarantee whose dependence on K is better than that obtained by 17].
Algorithm Bandit PAC for Single Label Classification
Parameters: N2, (0, }], T N.
Phase 1:
Initialize 5
for .I....NI do
Environment generates (xy, yr) D, algorithm receives X/. Predict uniformly random yi E y and receive feedback ( yy)) If f1 yı. update S SU (x,, end for Initialize P1 E Ar to be a delta distribution. for .,..., do
Let qı E An be the delta distribution on h, = ERMMI [(x,, P [5) where
(1 x 1(): 1();=;; y
P,(y) = IS]
Vi [[S]],y e y.
(p.)
Update pr+1 (1 7;,P, , 11q, where 17 = (2+
end for
Let 0 = PT+1. Phase 2:
for i I..... N2 do
Environment generates (x), D, algorithm receives X7.
With prob. y pick 9, E y uniformly at random; otherwise sample h; - and set 8r (x)).
Predict 9; and receive feedback 11 [[;;; yr).
end for Return:
haut ERMH E (())))))) where A(v)) 16; : y.
2 (
At a high level, the difference between the specialized version given in Algorithm and the more general approach (Algorithm]) []] lies in the fact that in the single label setting, we are able collect fully-labeled dataset by predicting random labels, and once every = K rounds we are guaranteed to add sample our dataset with high probability, as the approach of [17]. This removes the need to estimate the objective given in Eq. (3) via importance sampling, which would result in scaling factor of in the objective and thus an additional K2 factor in the total sample complexity due to the Rademacher complexity arguments. Instead, collecting the dataset S results in one extra factor K the total sample complexity. The improvement the sample complexity bound over that of [18] arises from the usage of the empirical FW optimization algorithm instead of the stochastic variant. Indeed, in our approach, the sample complexity depends on the Lipschitz constant of the objective which scales with K, and not on its smoothness parameter which scales with K2, The result is stated formally the following.
Theorem 4. Consider the single-label bandit multiclass classification setting. If we set = } Ni = O x2 (gg(H)/)))) N₂ ((/// 1/82) log({H//)) and T @(K*) in Algorithm 3 then with probability at least 8 Algorithm Boutputs hout H with r (h*) rD (hou) S & using a sample complexity of
N₁ + N2 -No==0(2
H log
8
Furthermore, Algorithm makes total of T = OKK*) calls to ERM
26

---

Proof. The analysis of the second phase is identical to that of the more general setting of combinatorial cani-bandits with s-sparse rewards (see the proof of Theorem D.. where in this case we have
s m = 1. Now, note that the first phase of Algorithm 3 is an implementation of the FW algorithm on the following objective:
minimize
F(p)
Σ 1og( (p)),, E ΔH.
[S|
(x,y)ES
Thus, it suffices to show that in the first phase, O(K log(1H1/6) samples suffice in for uniform
converges of F()) with rate jr 1 1/8K2. Indeed, straightforward concentration argument shows that with probability at least 6, the number of samples after the data collection process least
|S| [5==2/ 22 K K log
|74] 5
Now, note that the realized objectives optimized in the first phase come from a generalized linear model of the form
T = f - - - log/// ( ppl AH)-
Since the function v R R defined by (xxx) log(y/K (1 y)x) is G-Lipschitz with
G = K/y, simple contraction argument (see c.g. Lemma 26.9 in (45) together with bound on the Rademacher complexity of L,/los-bounded linear models (see e.g. Lemma 26.11 in [45). shows
that the Rademacher complexity of F with respect to S is bounded by
2 llg(()
K
2 log((1
R(T S) SC
[S]
[S]
Using Lemma as in the proof of Lemma we deduce that with probability least 1 8 it holds that
-(p)) s.
where μ 1/8K2. The bound on the number of iterations of FW follows from the fact that the objective is O(K2)-(mook with respect to the L₁ norm, and similar arguments as those in the proof of Theorem 3
A.4 Lower Bound for Sparse Combinatorial Semi-Bandits
We now provide formal proof of the sample complexity lower bound given in Theorem 2 (and more formally restated below) for combinatorial semi-bandits with s-sparse rewards. We construct hard instances for the problem denoted by Is for all subsets S C y of size m. In Is. the reward distribution constructed as follows: The rewards of all actions y E are Bernoulli random variables x with parameter 2K parameter 2K K-m The rewards are sampled in an i.i.d. manner between actions, and is easily seen that ths of expected rewards of actions is exactly 3. Using standard binomial concentration arguments, we will show that with high probability all realized reward vectors are s-sparse, and so conditioning the event in which all reward realizations are s-sparse will not substantially affect the lower bound. We also limit our analysis to deterministic algorithms, which suffices in general due to Yao's 's principle the instances construct do not depend the decisions of the algorithm. The formal lower bound is established in the following theorem:
x m and the rewards of all actions y y S are Bernoulli random variables with
Theorem 5 (restatement of Theorem 2). Let Alg be a deterministic combinatorial semi-bandir algorithu over action set y of size K with combinatorial actions being subsets of y of size m s K/ X/12. Then for sufficiently small rounds over rewards sampled according Is, then Alg outputs an E/ e/2-suboptimal subset with probability at least 1/4.
am there exists an instance Is for which if we run Alg for T S 3072g3
Proof. For the analysis, we define an additional problem instance denoted by In which the expected reward of all actions is I -- For a given S S y of size we denote by IP's and PP the probability distributions over length sequences (u1,r1...... aT, FT) where a, the subset produced
by Alg round 1, conditioned the instance Is Io. respectively. We also denote the history up
27

---

to round by ,, (Q...1........111 -1--1, and note that since Alg is assumed to be deterministic, deterministically chosen conditioned on h, For an action y E y denote by Ny the number of times Alg chooses subset containing y during the 7 rounds.
We claim that there is some subset y' y of size least K/3 such that for all y y' it holds that
3T and Poly E arl K
3m
Eo[N,] & K
Indeed, by the fact that each action may be chosen at most T times, for at least (2/3) actions y y it holds that
37
Eo[N,] <
K
Similarly, since at each round Alg picks m actions, for at least (2/3) actions y E y it holds that
3m
Poly ar) s
Therefore, both conclusions hold for the intersection the two subsets of actions, denoted by y', which must be of size least K/3. Let S S y' be some subset of y' of size m. We now show that the theorem holds with the instance Is.
Now, by construction of Is. in order to prove the theorem it suffices to upper bound the probability that at least half of the actions in belong to ar by 3/4. By Markov's inequality, it then suffices to prove that the expected number of arms of S which belong to ar is at most 3m/8 /8. Fix S. By Pinsker's inequality and the chain rule for KI.-divergence, it holds that
2(Poly E ar] - Psly E ar))² z KL(Po Ps)
I
KL(Polr, h.] Pstr, I h,))
Σ
Pola, SSJ
Σ y'En'S
KL(Polr, h.] (Psl)))))) h.)).
where KL q) = Σ. log p(z) is the KL-divergence between distributions. Now, note that q()) the KL terms in the last expression are all equal to the KL divergence between Bernoulli random and & respectively, and thus can be bounded for sufficiently 2K m
variables with biases I K m small & by
KL Ber
Ber
+ 8
(2e/m)
32 K m²
2K
2K
s
2K
K-m
2K
K-m
Therefore, the above is further bounded by
32c² K m²s
2(Poly e erl-Psle E arl)
Pola, = S'ISS' nsl.
1=1 S' S'S.. =m
32e² K
Σ Eo[Ny.]
m²s
y'es
ms
32'
where we used the fact that Eo[Ny.] S 37/K for each y' E S and the choice of T. Simplifying the above inequality and using the fact that Poly E ar] 3m/ K, we have
3m
3
Psly E ar]
+
8
K
8
4
8"
28

---

where we used the fact that m & K/12. Summing over S, we obtain
Σ yES
ssly arl s 3m
which concludes the proof.
In order to obtain valid lower bound for instances in which the reward realizations are s-spars, use a multiplicative Chernoff bound together with a union bound over [7) to deduce that for every
instance Is:
Ps [T] s.t. ||r/ s) Te
Te- s/4
2'
where the last inequality holds for s 2 4 1og(2 Note that conditioned on the event that ||r, & for all I, the rewards are still i.i.d. across rounds, and thus their conditional distribution defines s-Sparse instance on which Alg outputs an s/2-suboptimal subset with probability at least 2.
B Online Regret Minimization Setting
In this section we present regret minimization algorithm for CCSB with rewards that satisfy I|rall which is slightly relaxed version of the assumption ||r, s. Instead of rewards in
[0, I]. it will be convenient for us to instead consider losses, so we introduce the following negative loss vectors:
-n,) V [T).yy.
is obvious that the losses satisfy ||G112 I and that the transformation from rewards to losses does affect the regret. A natural approach for regret minimization in CCSB would be to the EXP4 algorithm (5) over the policy class II, which amounts to Follow-tteerrgulaiize--eedd (FTRL) using negative entropy regularization, defined
H(p) Σ Pi log Pi. p An.
However, as been observed by 18 since loss vectors are negative, this approach alone would not suffice to achieve a regret bound that is adaptive to the sparsity level and would instead yield regret bound of the form O O log [I].. In order adapt sparsity, they introduce additional log-barrier regularization, defined as
((p) log Pi p E An-
(8)
We adopt this approach and generalize it to the combinatorial setup with Algorithm
We prove the following result for Algorithm 4
Theorem 6. Assume that the loss vectors 4 satisfy ||G|12 s s for all i e [7]. Then Algorithm with
16 and (m) attains the following expected regret bound w.E.t. finite policy class II:
E E[Ry] s O log((11)))))) + log [TI]
We remark that the linear dependence on [[]] is essentially tight we require the leading term to depend rather than K, as shown in (18 for the single-label setting.
Theorem 6 primarily stems from the following the following result which is consequence of generic analysis of FTRL (see e.g. (26). 41 (Lemma 7.14)):

---

Algorithm EXP4-COMB-SPARSE
Parameters: K,T,s, finite policy class II (X - A), step sizes ll < Initialize P1 E An as the uniform distribution over II.
for 1,....... do
Obtain X, E E.
Sample n, Pr and let = (x,) E A. Observe (G()) E a,) and construct importance-weighted loss estimators for policies in II
via
40) ar) 2,(y)
(1(1
Σ
Vi [[]]].
(x)
where Qy(y) = Σ (1) E (x)) is the probability that belongs to when sampling
policy using Pt- Update Pr via
êr HH(p) + )
Ee,
Pr+1
argmin PEAn
r=1
where H(-) and ((-) are defined in Eq. end for
and Eq. g
respectively.
Lemma 7. For all p* An, the following regret bound holds for Algorithm
T
Σ
c. (p, C
(p--p") pp*)
S R(p") R(pi) " Σ Σ p,()),
where R(p) = H()) (p), and 5, E [Pr, Pi+1] is some point which lies on the line segment
connecting Pt and Pr+1-
In order to relate Pr given in the bound pr. we use the following result which is where make use of the properties of the log-barrier regularization ((.).
Lemma 8. Assuming that
T6 it holds that Ps+1 (i) s (1) for all i e [[[]].
18 prove this claim for the single-label setting, for completeness we include the proof for the multilabel setting. The proof requires the following preliminary definition:
Local and dual norms. Given a strictly convex wwice-differentiable function F : where W S Rd is a convex domain, we define the local norm of vector E 'W about a point E ' with respect F by
1| V2
and its dual norm by
llg lglli; & Vg V2F(()-11
Proof of Lemma
Fix E [T] and define F, An R by
F((p)
E. p R(p).
where R(p) - (p) + +p)
,, H round of Algorithm Now, by the form of the Hessian of ((-), for all p', E An it holds that
+ ,
(p). That is, F, the function minimized by Pr at
III (p(1) 2()))
|pp - 1p'1'1
9()2
im1
30

---

and thus it suffices to prove that l1 pell s c
where c
2 1, since in this case for By
1
all i E [[T]]] we will have
(1)+(()) Pr
8y 1 pr(i).
implying the result. Note that sufficient condition for the above is that for q E An for which llq Pello,..P = holds that Fi+1 (q) 2 (pr) Indeed, in this case, if we define the convex set & - {p E An I llp Prllo..p. s $ (which in particular contains Pr), since Fi+l is strictly convex, the condition that Fr-1 (q) 2 Fi+1 (pr) for all on the relative boundary of implies that its minimizer, Pr+1. must belong to &. With that in mind, fix An with ll Prlla..p. $ Using second-order Taylor approximation of F,+1 around Pt. we have
(4) 2 (i+) (Fi+l(P)) p.) p))+ P P
where p point on the line segment connecting Pr and q. Using the definition of Fi+s and the fact that V²R(-) E (-),(() since H, is convex, we get
1 (g)1(g) Fr+1(p:) (Fr(p:) (q- p,) é (q pr) + ++5111 ---PPlle prlle..p
and using first-order convex optimality conditions for p, as a minimizer of F,, we obtain
(g) 2 +7 pr) 2 114 prlle..r
Starting with the local norm term, we note that since - cº it holds that q(i) (r for all [[][]]. and since p lies on the segment connecting q and pr, the same holds for p instead of Therefore,
(q(1) Pr))2
llq - -rlllo...
p(i)2
(q(1) (i)))
2 64v
Pr(12
1=1
644 - prllè..p
24vc
Thus, to conclude the proof, we need to show that (7 P.) -32vc? Indeed, since the losses are non non-positive, we have
(a,))
(g-pi))
(g(1) (m()) a,
(a,)
(ar)
(x))))))))) a.)
(a,)
Using the fact that q(i) s 1
8y (i) we further lower bound this term as
1 ((a))
(T (()) 2
(m) = =
8y (a),
1
(ar))
8y
1
2 8y'
where we used the fact that 4() E [-1,0] 0]. The proof is concluded once we note that 3 and only c² > 256y2, which clearly holds since 256v²
>
if
Ky
1 c
31

---

With Lemma 7 and Lemma 8 in hand, we can prove the following result:
Theorem 7. Algorithm with v S and 1j > 0 attains the following expected regret bound:
Σ m
E[Ry] s 1+ [ log (IIT) log [TI|
+,
(1)
Proof of Theorem
Fix p* E Ån and for y गम let (0) - (1- -1-1-))ppp00))))11 y for all [[]]].
In addition, let c
[-1,0] defined by c,(i) (Ti (x+)). We have,
T
Σ ct 1---p") Σ
(pr (pr- p.
Σ
pp p*)
c
cr
T
r |
=
Σ
Ct-
ci 111ly~1111pp000000
1=1
E=l 21
Σ
Cr (pr Py-PPy pt}
y|[l|
1=1
T
Σ cr
Ppr p3
where have used the fact that (7) E [-1,0]. Taking expectations and using Lemma and
Lemma & together with the fact that E, [& = Cz, we obtain
T
(p- pp))
E[Rr] S E
E
r=1
é Pt p3))
= + E
Σ
1=1
T Σ
$ R(P3) R(p1) + 17EE
$ 1 0(p7)
1 H((p)) 1
Σ
(0),()))
17
7-1l
m
$ log( [1[7)
log [II|
Pr (.E,
r/E
as claimed.
Proof of Theorem 6 holds that
Using Theorem 7 and considering the stability term, for all E [7] and e [[]]]]
(() e ar)
E, [c,(1)) = EE,
Σ
2x(y)
(x)
40)1iy a.)
m E
m
2+(r
(x.
(G)) at) 2r(r)
S mE,
(N.)
(())
m
2r(y))
(x)
32

---

where the third line uses Jensen's 's inequality, and the last equality uses the fact that E, [1 E Ea))= 2 (y). Thus, the stability term is bounded by
T
m
T
m
46)
7
Pr (())),,,,)
& qumE
Σ
(1(1)
Σ
2x(r)
r=1
2
ye (X,)
K
m
4(y)
Pr ((
2,(y)
2,(y)
= mmm
Σ
IIGI
S nsmT,
and plugging in the specified values for 17 and gives the desired bound.
C
Open Problems
Full-bandit feedback. Our results for PAC learning in the semi-bandit setting raise a natural question regarding the full-bandit feedback model, which is characterized by the fact that the observation upon predicting a, E A consists a single number r, a, Specifically, it is unclear given our results whether adapting to reward sparsity and obtaining improved sample complexity bounds of the form poly(s, m)/e² m))/ is possible in the full-bandit model. While we do not fully know how to extend may provide initial directions towards answering this question. We focus on the question of how should modify the log-barrier potential given in Eq. (T) to accommodate full-bandit feedback, that is, such that its gradient would correspond to the variance of an appropriate full-bandit reward estimator. Indeed, importance-weiglhe weighted reward estimators for combinatorial bandits are widely used in the literature [see, e.g.. and it is straightforward to construct such an unbiased estimator R(T) and show that its variance can be bounded as
techniques to the full-bandit setting,
present
interesting ideas which
Var [x)) s 22. x(x)" " (x),,,).
where C is the covariance matrix associated with sampling a policy from p. Interestingly, the latter quantity can be shown be proportional to the gradient of the following log-determinant potential:
fp;:)) A log det x(p:x)) = log det Σ p(K)aa())aa))))
which would seem like natural generalization of the log-barrier potential used in Eq. ( This variance bound, however, contains no dependence on the reward function r, and in turn the existing analysis would result sample complexity of K/s², which we would like avoid.
Improving the dependence on K. A natural question which is also left open in 17 for the single- label setting concerns improving the dependence on K in the additive term of the sample complexity bound. We strongly believe that this term could be significantly improved, potentially reaching K/s which would result in minimax optimal sample complexity bound. The high polynomial degree in the current bound mostly stems from requiring the approximate minimization F(:) as a means to obtain a point which the gradient small. Intuitively, minimizing the objective F(-) itself is not our primary goal, but rather we are interested in finding a point at which the gradient of F(.) is small. This naturally leads us look for an optimization procedure which would minimize the norm of the gradient of F(.) directly, which can be done in various unconstrained optimization problems [see, e.g.. 21. using a sample complexity which only depends logarithmically on the objective's smoothness. The constrained nature of our problem of interest, though, poses a significant challenge to adopting this approach directly. Nevertheless, we conjecture that leveraging specific properties of the objective function (such self-concordance) may enable extending these methods to constrained settings. Such results would not only improve the sample complexity bounds for bandit multiclass classification but could also be of independent interest to the convex optimization research community.
33

---

Extension to infinite classes. Another natural research direction is to extend our result given in Theorem to hypothesis classes which could be infinite, but exhibit certain properties which allow for replacing the dependence on log [H] with some combinatorial dimension. For the single-label setting, [7 show that a finite Natarajan dimension is indeed such property. We thus expect that for list classification, an appropriate generalization of the Natarajan dimension would give such results, a similar manner to how the Littlestone dimension is generalized by [39] to list classification the online setting.
34


Reviews:
[{"review_id": "1YzZj7YgAB", "reviewer": "Reviewer_ZLpc", "summary": "This paper studies multiclass list classification where the learner only receives semi-bandit feedback. That is, it assumes for each object $x$, there exist a set of $s$ true labels. Upon receiving $x$, the learner is to predict a list of $m$ labels and receives all correct labels among the $m$ labels. The paper establishes a PAC learning variant of the problem and proposes an algorithm with sample complexity of $\\tilde{O}(\\text{poly}(K/m)+sm/\\epsilon^2)\\log(\\lvert{H}\\rvert/\\delta)$, improving on its previous work on a special case when $m=s=1$. The paper also considers a regret minimization setting with adversaries, and establishes a regret bound of $\\tilde{O}(\\lvert{H}\\rvert+\\sqrt{smT\\log{\\lvert{H}\\rvert}})$.", "questions": "Can the authors give a more clear vision on why a PAC learning framework for the proposed problem is necessary?\nIf 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?\nHow important the ERM oracle is? What if such oracle does not exist? If without such an oracle, is bandit multiclass list learning possible?", "limitations": "The authors shall discuss the necessity of the ERM oracle.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "First of all, I have a question on whether it is necessary to pose this problem in the multiclass and list learning paradigms, especially with (semi)-bandit feedback, plus adversarial data and online learning scenarios. It feels too much effort to fit the problem in the PAC learning setting. Given the motivative application mentioned in this paper, it feels much more like a recommendation system problem or contextual combinatorial semi-bandit problems. Moreover, the algorithm assumes having access to an ERM oracle, which is also less a PAC learning paradigm. I am not convinced that this is a reasonable and well-posed problem. The paper is generally hard to read, with many terminology remain unexplained.", "was_revised": true, "final_justification": "This paper studies a contextual combinatorial semi-bandit problem, and designs an algorithm with improved sample bound when the problem is restricted to a special cases of multiclass learning problem. When viewing the problem in a learning/classification scenario, it is very close to multilabel classification. The reviewer feels the reduction of the bandit problem to a traditional learning/classification problem was less natural. However, after discussing with the authors and area chair, the reviewer can appreciate the proposed algorithm that works both for bandit and multilabel problems with improved sample complexity, hence changing my recommendation from rejection to a borderline.", "rebuttal": "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.\n\n> “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” \n\n**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.\n\nFurther, 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.\n\n>  “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?”\n\nNote 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.\n\n> “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?”\n\nAssuming 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}|$). \nThe 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”. \n\nWe 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. \n\n> “The paper is generally hard to read, with many terminology remain unexplained.” \n\nWe 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.\n\n\n**References:**\n\n[1] Dudik, Miroslav, et al. \"Efficient optimal learning for contextual bandits.\" arXiv preprint arXiv:1106.2369 (2011).\n\n[2] Agarwal, Alekh, et al. \"Taming the monster: A fast and simple algorithm for contextual bandits.\" International conference on machine learning. PMLR, 2014.\n\n[14] Daniely, Amit, and Shai Shalev-Shwartz. \"Optimal learners for multiclass problems.\" Conference on Learning Theory. PMLR, 2014.\n\n[15] Daniely, Amit, et al. \"Multiclass learnability and the ERM principle.\" J. Mach. Learn. Res. 16.1 (2015): 2377-2404.\n\n[17] Erez, Liad, et al. \"Fast rates for bandit PAC multiclass classification.\" Advances in Neural Information Processing Systems 37 (2024): 75152-75176."}, {"review_id": "YWJ6MmrTag", "reviewer": "Reviewer_KD2J", "summary": "The paper tackles the setting of bandit multi-label list classification from a learning-theoretic perspective and analyze it under the agnostic PAC and agnostic online learning setting. In addition, the authors show that their results for the agnostic online learning setting can also apply in the combinatorial semi-bandit setting.\n\nMulti-label list classification is understood as predicting a list of labels for each instance, and each instance is allowed to have multiple true labels. In the bandit version of this scenario (or semi-bandit as the authors note), the learner receives a response that explains which subset of the labels are correct but not necessarily the set of all true labels for that instance. The reward function is designed to be the count of number of true labels for a given instance that occur in the list predicted by the learner. In all settings considered, the hypothesis class $\\mathcal{H}$ is assumed to be finite with a finite label space $\\mathcal{Y}$ that has $|\\mathcal{Y}|=K$.\n\nIn agnostic PAC learning, the authors develop an algorithm (Algorithm 1) that returns an $\\epsilon$-optimal hypothesis with probability $1 - \\delta$ with a sample complexity on the order of $O(\\mathrm{poly}(\\frac{K}{m}) + \\frac{sm}{\\epsilon^2})$ and show a lower bound with $\\Omega(\\frac{sm}{\\epsilon^2})$. The main algorithmic technique consists of employing a learner to run a Frank-Wolfe procedure on a specially-designed convex potential whose gradient effectively estimates the variance of the reward estimator of any single policy. When the setting is simplified to single-label classification, the bound has an improved dependence on $K$ ($K^9$ to $K^7$) compared to previous work. In agnostic online learning, the authors devise an algorithm that has expected regret at most growing $O(\\sqrt{KT})$ where $T$ is the number of rounds.", "questions": "- For the case of agnostic online learning, there doesn't seem to be a lower bound on the regret showing that the regret achieved by Algorithm $4$ is in fact optimal or loose. Can the authors elaborate on the optimality of the regret bounds in the case of agnostic online learning?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- This setting is analyzed in both agnostic PAC learning and agnostic online learning where upper and lower bounds are proven in the agnostic PAC setting.\n- The paper generalizes their work to the setting of contextual combinatorial semi-bandits with a bound that directly relies on the sparsity of rewards rather than the size of the label set.\n- The authors introduce a clever twist of constructing a convex potential whose gradient is exactly related to the variance of reward estimators. By employing the Franke-Wolfe procedure, the resulting mixed policy distribution has guarantees on the maximum value of the reward estimators allowing the algorithm to effectively estimate the reward estimators for all policies.\n\nWeaknesses:\n- 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. As a result, the innovation is more about tweaking the methodology rather than introducing a new optimization paradigm.\n- While the authors do provide upper and lower bounds in the agnostic PAC setting showing the importance of the $\\frac{sm}{\\epsilon^2}$ term, the hidden polynomial factor $(K^9)$ is pretty large signifying that there is still a somewhat sizeable gap between the two bounds.\n- The writing of the paper is at times hard to understand, especially for an audience not well-versed in this specific literature. The paper could benefit from having an improved exposition of the learning setting itself and provide a better proof sketch of Theorem $1$ that elaborates the core technical ideas in a clearer fashion.", "was_revised": true, "final_justification": "I thank the authors for answering all my questions with detailed explanations during the rebuttal period. I recommend that the authors make the necessary revisions to the paper to make the more readable. As a result, I retain my original rating of a 4 for this paper.", "rebuttal": "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.\n\n> “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.…”:\n\nWhile 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.\n\n> “...there is still a somewhat sizeable gap between the two bounds.”:\n\nWe 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.\n\n> “The writing of the paper is at times hard to understand, especially for an audience not well-versed in this specific literature”:\n\nWe 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!\n\n> “Can the authors elaborate on the optimality of the regret bounds in the case of agnostic online learning?”: \n\nWhile 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.\n\n**References:**\n\n[17] Erez, Liad, et al. \"Fast rates for bandit PAC multiclass classification.\" Advances in Neural Information Processing Systems 37 (2024): 75152-75176.\n\n[18] Erez, Liad, et al. \"The real price of bandit information in multiclass classification.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024."}, {"review_id": "CnGUEpjomK", "reviewer": "Reviewer_f4D1", "summary": "The paper studies the bandit multiclass list-classification problem, an extension of bandit multiclass classification when multiple labels can be predicted for each example. The paper considers how to build an algorithm that aims to approximate the best classification hypothesis out of a finite hypothesis class $|\\mathcal{H}|$. Formally, at each time $t$, the environment draws a sample $(x_t,y_t) \\sim \\mathcal{D}$, after observing $x_t$, the algorithm predicts a set of labels and receives feedback indicating which of the predicted labels were correct. The paper draws a strong connection between this classification problem and the contextual combinatorial semi-bandit (CCSB) framework, which is leveraged to design the algorithm to approximate the best hypothesis with a small number of samples. A sample complexity of $\\mathcal{O} \\left ( \\left (\\frac{K^9}{m^8} + \\frac{sm}{\\epsilon^2} \\right )\\log \\frac{|\\Pi |}{\\delta} \\right )$ is then proven for this algorithm. The paper then provides a lower bound which matches their sample complexity asymptotically for small $\\epsilon$. In the appendix, the paper provides an analysis of a similar setting with an objective of regret minimization and provides an upper bound on the regret of $\\mathcal{O} \\left ( \\sqrt{sm T \\log |\\Pi|} \\right ) $.", "questions": "1. What do you think is the limiting factor to applying the current types of results to infinite hypothesis classes? \n\n2. In the CCSB setting, and in algorithm 1, the main problem at hand is to choose the right policy $\\pi \\in \\mathcal{\\Pi}$. In the framework of the paper, my understanding is that it is related to the hypothesis class $\\mathcal{H}$, is that correct? Could you clarify that? Furthermore, 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. I feel that having one set of homogeneous notation would make navigating the paper easier.\n\n3. Algorithm 1 uses a procedure that is based on two separate phases. The first phase explores uniformly, while the second one uses the previously acquired information to focus the exploration. Is there a particular reason for having two phases (in contrast with having an algorithm that starts by exploring uniformly but performs a focused exploration similar to phase 2 gradually, while incrementally refining its estimates )?  \n\n\n4. In the paper, you do not provide any assumption regarding the space $\\mathcal{X}$. It is my understanding that this comes at no additional cost from a discrete space $\\mathcal{X}$ because you assume that the hypothesis classes are finite. 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?", "limitations": "yes", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Overall, the paper proposes a technically interesting algorithm for list-based classification in a bandit setting, but a clearer exposition and complete proofs are required. Furthermore, this work would benefit from broader generalization. \n\n # Strengths \n\n- The paper is well-written and describes the related literature clearly. \n\n- The paper provides lots of insight into the motivation and key elements of their algorithm, as well as the main technical elements necessary to prove the results. \n\n # Weaknesses\n\n- The paper provides lower bounds for the problem but does not include a proof. While some very high-level intuition is provided, the proof does not appear in the appendices. Considering this, it is difficult to consider Theorem 2 as more than an intuition. This makes it difficult to gauge whether their approach is optimal or if more progress can be expected. \n\n- 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. Consider presenting both the sample complexity and regret minimization settings (the algorithms and main results) in the main paper to clarify the full scope of contributions. If space is an issue, consider reducing the amount of technical details in the main paper and stick to high-level ideas and/or main differences with existing techniques, and provide further insight in the appendix. \n\n- 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. \n\n- Some literature was missed on combinatorial bandits with sparse rewards. Please consider extending the related work, especially since you claim to provide new results in that line of work. ( see [1] for instance)\n\n- The paper mostly uses the notation introduced when describing the Contextual Combinatorial Semi-Bandit setting. I understand that the algorithm used is based on CCSB literature, and I appreciate the fact that the link is explicitly stated, as it makes understanding the whole thing easier, yet it is counterintuitive to introduce the problem you are trying to solve and to switch notations right away afterwards. Furthermore, using different notation in the algorithms makes it difficult to follow. See, for instance, question 2. \n\n\n[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.", "was_revised": true, "final_justification": "My main concern is the following: While they state it as a theorem, no formal proof is provided for the lower bound. While they provide a proof sketch, I believe it is not sufficient. Without any formal proof, this is, in my opinion, mostly a claim. \n\nThe two other points are secondary. I detail them below.\n\nI do believe their argument that CCSB is more general than BMLC is true. For now, there is no proof or sketch on how to reduce BMLC to CCSB but the authors mentioned to improve the transition between problems, which i believe should clear that up. My point for the issue in formulating the result in terms of CCSB is more related to the lack of clear translation between the notations used in both settings. As the results are stated with notation for the CCSB problem and no clear correspondence is provided, it is not straightforward to even read the results for BMLC. If the interesting problem to make the paper compelling is indeed BMLC, it is not great to rely on an implicit reduction to present the results.\n\nI believe their result is an extension of [1], where after reducing list-classification to multiclass classification (on a bigger class set resulting for the combinatorial set of lists of classes) the similarity between these combinatorial classes is leveraged. While this surely does not straightforwardly follow, even only for notational complexity and because a proper setting is required, the result is not very surprising and does not answer a very compelling and general question.\n\n[1] Erez, L., Peled-Cohen, A., Koren, T., Mansour, Y., & Moran, S. (2024). Fast rates for bandit PAC multiclass classification. Advances in Neural Information Processing Systems, 37, 75152-75176.", "rebuttal": "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.\n\n> ”The paper provides lower bounds for the problem but does not include a proof…”: \n\nWhile 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.\n\n> “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”: \n\nIndeed, 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.\n\n> ”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”;\n\nWhile 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.\n\nFurther 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.\n\n> “Some literature was missed on combinatorial bandits with sparse rewards”:\n\nThank 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). \n\nIf 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.\n\n**Questions:**\n\n> “1. What do you think is the limiting factor to applying the current types of results to infinite hypothesis classes?”: \n\nSee our response above regarding infinite hypothesis classes. \n\n> “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.”: \n\nThere 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. \n\nIn any case, we will do our best to improve the clarity of our notation in the revision.\n\n> “3. Algorithm 1 uses a procedure that is based on two separate phases… Is there a particular reason for having two phases”:\n\nYou 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.\n\n> “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?”\n\nThis 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.)\n\nIn 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}$.\n\n**Typos:** \n\nThank you for bringing these to our attention, we will make sure to correct them.\n\n\n**References:**\n\n[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.\n\n[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.\n\n[17] Erez, Liad, et al. \"Fast rates for bandit PAC multiclass classification.\" Advances in Neural Information Processing Systems 37 (2024): 75152-75176.\n\n[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."}, {"review_id": "8jAvwQ4yrb", "reviewer": "Reviewer_FW6h", "summary": "This paper investigates the $(\\epsilon,\\delta)$-PAC learnability of multiclass list classification with semi-bandit feedback. In this model, at each round, the nature generates an instance $X$ and a list of $s$ labels $Y = \\{y_1,y_2,\\ldots,y_s\\}$, where $y_i \\in [K]$, from a distribution $D$ and shows the instance $X$ to the learner. Then, the learner predicts a list of $m$ labels $\\hat{Y}$ and gets the feedback $\\hat{Y} \\cap Y$. After $T$ rounds, the learner will output a concept $h \\in \\mathcal{H}$ that maps the instance $X$ to a list of $m$ labels. They investigate the sample complexity of learning the $\\epsilon$-optimal hypothesis with the probability of at least $1-\\delta$ and get an upper bound of $\\tilde{O}((\\text{poly}(K/m)+sm/\\epsilon^2)\\log(|\\mathcal{H}|/\\delta))$, when the concept class $\\mathcal{H}$ is finite. They also provide an $\\Omega(sm/\\epsilon^2)$ lower bound. \n\nFor the $s=m=1$ case, they get a $O((K^7+1/\\epsilon^2)\\log(|\\mathcal{H}|/\\delta))$ upper bound. For the regret minimization setting, they get an expected regret bound of $\\tilde{O}(|\\mathcal{H}|+\\sqrt{smT\\log|\\mathcal{H}|})$ for the adversarial setting.", "questions": "In the contextual combinatorial semi-bandit problem, your algorithm works under the case that the reward function is additive, that is, $r(A\\cup B) = r(A) + r(B)$. What if the reward function is submodular, or more generally, any set function? Is it possible to get the same sample complexity?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The PAC learnability of multiclass classification with bandit feedback is an interesting and important problem. There are significant connections between this problem and the long-standing multi-armed bandit problem. This paper considers multiclass list classification with semi-bandit feedback, and the result can be applied to solve the contextual combinatorial semi-bandit problem. Their algorithm also provides the regret bound for the contextual combinatorial semi-bandit problem. \n2. The algorithm provided by this paper is computationally efficient with an efficient ERM oracle. Therefore, this result may be interesting in both the statistical learning theory community and the broader TCS community. \n3. The presentation of this paper is quite good.\n\nWeakness:\n\nThe result only works for finite hypothesis classes. It is not clear what will happen when the hypothesis class is infinite.\nThe assumption that every call of the ERM oracle only spends constant time is not that benign when there is an infinite hypothesis class.", "was_revised": true, "final_justification": "I think this problem is reasonable and meaningful from a theoretical perspective. The result is solid, but under some common assumptions. This paper also focuses on the case where the concept class is finite. Therefore, I give this paper a borderline accept.", "rebuttal": "Thank you for your review. ​​We hope that our responses below will fully address your comments and questions. \n\nYou 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.\n\n\n> “The result only works for finite hypothesis classes. It is not clear what will happen when the hypothesis class is infinite”\n\nWhile 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.\n\nFurther 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.\n\n> “The assumption that every call of the ERM oracle only spends constant time is not that benign when there is an infinite hypothesis class”\n\nOur 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})$. \n\nSuch 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.\n\n**Questions:**\n\n> “What if the reward function is submodular, or more generally, any set function?”:\n\nYou 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!\n\n**References:**\n\n[1] Dudik, Miroslav, et al. \"Efficient optimal learning for contextual bandits.\" arXiv preprint arXiv:1106.2369 (2011).\n\n[2] Agarwal, Alekh, et al. \"Taming the monster: A fast and simple algorithm for contextual bandits.\" International conference on machine learning. PMLR, 2014.\n\n[17] Erez, Liad, et al. \"Fast rates for bandit PAC multiclass classification.\" Advances in Neural Information Processing Systems 37 (2024): 75152-75176."}]

Author rebuttal:

Meta-review: The paper tackles bandit list multiclass classification where in each round, the learner receives a context and choose a set of m labels. The ground truth has s labels, and the learner observes the correctness of the label they choose.  The paper casts this as a contextual combinatorial semi-bandit (CCSB) problem and design two algorithms for this problem: one with stochastic reward (PAC setting) and one with adversarial reward (regret setting). 

During the author-reviewer discussion phase, reviewers ZLpc, KD2J, and f4D1 raised clarity concerns. First, the switch between bandit list multiclass classification and CCSB is confusing for Reviewer ZLpc and f4D1: the paper could be framed just under the CCSB, and make bandit list multiclass classification as an important application, but the paper first states the latter and transitions to the former.  As f4D1 noted, the notation switch is too quick. Second, as KD2J pointed out, the paper is hard to read at times --- lacking sufficient high-level explanation for the algorithm and the proofs.  

Based on my reading, technically, this looks like a standard contribution in a conference like NeurIPS, though not ground-breaking given the previous results of Erez et al's "Fast rates for bandit PAC multiclass classification" and "The real price of bandit information in multiclass classification".  The paper did make algorithmic and analysis advance in obtaining explorative distribution and low-variance reward estimator: for the potential function used to obtain low-variance estimator, they directly optimize the empirical version of the potential (instead of using an stochastic optimization procedure as in prior work), and use Rademacher complexity argument to establish uniform convergence. This allows an improved sample complexity bound, even in the single-label special case considered by [Erez et al, 2024]. As far as I can see, similar observations could be useful in other bandit problems involving solving a regularized objective.  Another contribution is the importance weight technique specific for the multilabel setting. 

After author-reviewer and AC-reviewer discussions, there is still no consensus. The concerns of ZLpc and f4D1 still remain. After deeper discussions with them on these concerns, I conclude that the concerns are relatively minor compared to the main contribution. ZLpc connects the "PAC setting" in the paper to the "list PAC learning" framework in [7,10], which seems to be an overinterpretation in my opinion. ZLpc perhaps also overlooks the fact that list classification and multi-label classification are interchangeable ideas. The main concern of f4D1 is the missing formal proof of the lower bound.  However, it seems to me that the lower bound is a minor part of the contribution, and the proof sketch seems to be standard enough (except for the argument "in order to find an eps-optimal subset, Alg must identify at least half of the arms in S, and thus is required to estimate all of the arms’ rewards eps/2m" which definitely require additional explanation) to be converted to a formal proof.  Another concern of f4D1 is the novelty.  However, the reviewer did not provide more concrete evidence to support this concern. 

Overall, I appreciate the main contribution --- the first sparsity-adaptive bound for contextual bandits, and other analysis/algorithmic contributions made by this work, so still recommend acceptance despite the negative evaluations by ZLpc and f4D1. However, the revised version of this paper needs to provide much more explanations than the current version for readers to easily understand it. Also, the authors should definitely write a formal proof for the lower bound.
Decision: Accept (poster)