Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget
Authors: Jasmin Brandt
Viktor Bengs
Björn Haddenhorst
Eyke Hüllermeier
Venue: NeurIPS 2022 Accept (2022)
Keywords: Combinatorial Bandits
Preference-based Bandits
Online Learning
Algorithm Selection

Abstract: We consider the combinatorial bandits problem with semi-bandit feedback under finite sampling budget constraints, in which the learner can carry out its action only for a limited number of times specified by an overall budget. The action is to choose a set of arms, whereupon feedback for each arm in the chosen set is received. Unlike existing works, we study this problem in a non-stochastic setting with subset-dependent feedback, i.e., the semi-bandit feedback received could be generated by an oblivious adversary and also might depend on the chosen set of arms. In addition, we consider a general feedback scenario covering both the numerical-based as well as preference-based case and introduce a sound theoretical framework for this setting guaranteeing sensible notions of optimal arms, which a learner seeks to find. We suggest a generic algorithm suitable to cover the full spectrum of conceivable arm elimination strategies from aggressive to conservative. Theoretical questions about the sufficient and necessary budget of the algorithm to find the best arm are answered and complemented by deriving lower bounds for any learning algorithm for this problem scenario.

Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget
Jasmin Brandt", Viktor Bengs", Björn Haddenhorst", Eyke Hüllermeier
*Department of Computer Science, Paderborn University, Germany "Institute of Informatics, University of Munich (LMU), Germany
Munich Center for Machine Learning, Germany jasmin. brandt@upb.ccmm viktor. bengs@lmu de, bjoernhatmail. deb eyke@lmu.de
Abstract
We consider the combinatorial bandits problem with semi-bandit feedback under finite sampling budget constraints, in which the learner can carry out its action only for a limited number of times specified by an overall budget. The action to choose set of arms, whereupon feedback for each arm in the chosen set is received. Unlike existing works, we study this problem with subset-dependent feedback, i.e., the semi-bandit feedback received could be generated by an oblivious adversary and also might depend on the chosen set consider general feedback scenario covering both the
non-stochastic setting
arms. In addition, numerical-best setericcl--bsedddeeee as well as seferenceebbsee case and introduce a sound theoretical framework for this setting guaranteeing sensible notions of optimal arms, which a learner seeks to find. We suggest a generic algorithm suitable to cover the full spectrum of conceivable arm elimination strategies from aggressive to conservative. Theoretical questions about the sufficient and necessary budget of the algorithm to answered and complemented by deriving lower bounds for
find the best any learning al algorithm for this problem scenario.
Introduction
The multi-armed bandits (MAB) problem is an intensively studied problem class in the realm of machine learning, in which a learner is facing a sequential decision making problem under uncertainty [32] A decision (action) corresponds to making a choice between a finite set of specific choice alternatives (objects, items, etc.), also called arms in reference to the metaphor of gambling machines in casinos. After each decision to choose particular arm, the learner receives some form of feedback - typically a numerical reward determined by feedback mechanism of the chosen arm. The learner is not aware of the arms' feedback mechanisms and consequently tries to learn these in the course of time by performing actions according to its learning strategy. The concrete design of its learning strategy depends essentially on two main components of the learning setting: the assumptions on the feedback mechanisms and the learning task.
Traditionally, and even up to now the most prevalent assumption is that the feedback received by choosing one arm is generated by means of probability distribution of the chosen arm BI] In this way, any useful learning strategy revolves around learning specific probabilistic features of the arms' distributions such as the means. These features, in turn, quite naturally provide a way to define notion of (sub- Joptimalty of an arm as well as best arm. A relaxation of this stochastic setting is the non-stochastic setting, which no assumption made the form of probabilistic laws of the feedback mechanisms. Instead, either assumptions made the feedback mechanisms, that
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

these can also be generated by an adversary 77, or that the sequence of feedback observations (or transformation thereof) of an arm converges asymptotically to a fixed point [25]. In the latter case, the notion of an arm's (sub-)opp sutb-ooptm is again straightforward, given that the limit points can be ordered, while in the former usually the best action in hindsight plays the role of the best arm.
Regarding the learning task, the most prominent one is that of regret minimization, where in each learning round the learner suffers regret unless the optimal decision is made (determined by the feedback mechanisms). The main challenge for the learner is to manage the trade-off between exploration and exploitation, i.e., constantly balancing (i) the degree of new information acquisition about some arms' feedback mechanism in order to appropriately expand the current knowledge base (exploration), and (ii) the degree of choosing arms considered to be optimal given the current knowledge base in order to keep the overall regret low (exploitation), In many practical applications, however, the learning task is of quite different kind, as the focus is rather on finding the (approxi- mately) correct answer to a problem specific question, e.g., which arm is the (approximately) optimal one, within a reasonable time (number of learning rounds). This pure exploration learning task can be considered in two variants, namely the fixed confidence and the fixed budget setting. In the former the learner tries to find the answer within as few as possible learning rounds, while guaranteeing a given pre-determined confidence for the correctness of its returned answer. In the latter, it is the other way around, as the learner is provided with a limit on the possible number of learning rounds (budget) and the confidence for the returned answer should be high possible. In both variants the main challenge for designing a suitable learner is to specify a clever exploration strategy for finding the correct answer.
In order to model more complex learning settings in practice, the basic setup of MAB problems has been generalized in various ways, such as incorporating additional side information 3 6 2 or infinite number of arms [1138, just to name a few. Of special practical interest is the generalization of the basic setup, where the learner is allowed to choose specific sets of arms its action. Consider as an example the online algorithm selection problem with parallel runs, where for sequentially arriving problem instances one selects a subset of available algorithms (solvers) to be run in parallel in order to solve the current problem instance.
If the feedback received is of a numerical nature, this variant has manifested itself under the term combinatorial bandits 14] while for feedback of qualitative nature this variant can referred to as preference-busel bandits as put forward by [8) Combinatorial bandits are further distinguished with respect to the type of feedback between semi-bandit feedback, where feedback of each single arm in the selected subset is observed, and full bandit feedback, where only some aggregated value of the individual numerical feedback of the arms in the selected subset is observed, Although both combinatorial and preference-based bandits consider a similar action set and for both the learner needs to deal with the possibly exponential size of the action set, the process of learning is quite different due to the nature of the observed feedback. The main reason for this is that in preference- sefeereene-beeedd feedback the mutual correlations that may exist between the arms in the chosen subset play a major role in both the assumption about the feedback mechanisms and the learning task from the outset. In contrast to this, the standard setting in combinatorial bandits with semi-bandit feedback is that the individual reward generation mechanisms are independent of the chosen subsets. However, this modeling assumption is questionable in a couple of practical applications, especially when humans provide the feedback. For example, in opinion polls or rating systems where humans rate subset of objects (political parties/candidates, products, etc.), it is well known that the ratings of the objects may be affected by context effects, i.e., preferences in favor of an object may depend on what other objects are available. In the fields of economics and psychology, context effects are among others divided into compromise
attention 22 and similarity [48 effects.
In this paper, we take a step towards unifying these two variants for the best arm identification (BAI) problem in pure exploration learning setting with fixed budget and non-stochastic feedback mechanisms. The main motivation for this unification is to derive a general purpose learner, which can tackle the BAI problem in both feedback variants. In this way, for example, one can transform a learning problem with numerical signals into a preference-based learning problem and thus con- veniently apply such a general purpose learner. Recent works have demonstrated in two different learning scenarios with numerical feedback that such a transformation has great potential (37 27
Needless to say, the main challenge is to unify both feedback variants through suitable abstractions allowing them to be treated as instantiations of the same problem class. This bridge is built by dropping
2

---

the common independence assumption (of the chosen arm set) for the numerical combinatorial bandits and abstracting the nature of the observations. Additionally. we simply assume that the learner is provided with an appropriate statistic customized to the explicit nature of the feedback. By appropriate choice of the statistic one obtains the respective setting, e.g., the empirical mean for the case of numerical feedback and relative frequencies for the case of preference feedback.
Our contribution. Under mild assumptions on the asymptotic behavior of these statisties, we derive a proper definition of a best arm a learner seeks to find (Section 2 as well as lower bounds on the necessary budget for this task (Section B To the best of our knowledge, such lower bounds are novel for non-stochastic settings and the derivation is rather non- non-standard due to the combinatorial setup of the problem. We suggest a general algorithmic framework suitable to cover the full spectrum of conceivable arm elimination strategies from aggressive to conservative, which we analyze theoretically regarding the algorithms' sufficient and necessary budget to find the best arm (Section 4. As a consequence, we obtain to the best of our knowledge the first algorithm(s) for non-stochastic preference-based bandits as well as for combinatorial bandits under semi-bandit feedback, in which the individual (numerical) feedback received for arm depends on the chosen subset due to possibly existing mutual correlations between the arms in the chosen subset. The mild assumptions on the asymptotics of the statistics allow to transfer our theoretical results to the stochastic counterparts of the bani-b combinatorial and preference- based bandits (Section 5). We demonstrate the usefulness of the generality of our setting in an experimental study for an algorithm selection problem with parallel runs (Section (). where once again the transformation of numerical feedback to preference feedback plays key role. Additional experiments are given in the supplementary material, where also all proofs of the theoretical results are collected.
Related Work. A large body of literature considers the combinatorial bandit problem under preference-based feedback, see (8] for an overview. Although dueling bandits [52] has established as an overall agreed term for the scenario with actions of size two, the terminology for action sets of larger sizes is still discordant, e.g., multi-dueling [10], battling [42], choice 4 or preselection bandits [9] mainly due to subtle nuances of the motivating practical applications. While pure exploration settings with a stochastic preference- wefereence-based feedback haven been considered by a series of works [36 39 15 40 43 21], pure exploration setting under non-stochastic feedback mechanism as in our case has yet to be studied.
Pure exploration has been intensively studied in the basic multi-armed bandits (MAB) setting with stochastic feedback mechanisms as well, see Section 33.5 in [32 for detailed overview. The non-stochastic variant of the fixed budget MAB setting is considered in [25], which is the backbone for the well-known Hyperband algorithm (34) and additionally inspired in some part the assumptions we make for our work. Initiated by the work of [12] to design learners for regret minimization
frameworks which can perform well in both stochastic and non-stochastic settings, the fixed budget
framework has been the subject of research by [ and 45
Combinatorial bandits with numerical feedback have been introduced by [4 and 16 in a regret minimization framework. The fixed confidence setting for stochastic combinatorial bandits with semi-bandit feedback studied in 26), and full bandit feedback in [88 30 Finally, the best-of-k bandits game introduced in [66), which in some way unifies the combinatorial bandits with binary set-dependent feedback and preference- bbaed bandits in one joint framework similarly as we do in this work. However, they consider fixed confidence setting with stochastic feedback mechanisms and do not provide a learner for the dependent arm case, although they derive lower bounds on the worst case sample complexity for this case. The only work assuming set-dependent feedback mechanism in combinatorial bandits with semi-bandde feedback is in [50]. where, however, the regret minimization task is studied under stochastic feedback mechanisms. In summary, there seems to be existing work which considers a pure exploration setting for combinatorial bandits with non-stochastic or even stochastic aani-banditin feedback, where the (mean) rewards of the arms in the chosen subset of arms depends on the subset. Accordingly, our results provide new theoretical contributions to this field.
2 Problem Formulation
In our setup, we assume set A of n arms, which we simply identify by their indices, i.e., A [n] = (1..... n.. For some fixed l < n we denote the set of all possible subsets of arms with size
of at least 2 and at most & by Q (Q C A 2 < QI < k). Further, we assume that for any
3

---

Q E Qckk we can query some feedback, in the form of feedback vector oQ = (0.10)Ee E DI which in turn can be of numerical or qualitative nature specified by the domain D. If we query a subset of arms Q for i many times, then og (t) is the corresponding feedback vector. We suppose that we are given a suitable statistic s for the type of observation vectors, which maps a multiset of observations to some specific value relevant for the decision making. With this, sQ(() = (N)G(()))E is the statistic vector derived by the sequence of feedback (oo(t)), of the query set Q E Qçk, and sijo( (t) = (((o))) ..... (gjo(() is the relevant statistic for decision making about arm in the "context" Q after querying Q for t many times.
Examples. For combinatorial bandits with semi-bandit feedback, the observation (t (Qio(t))ieQ corresponds to the reward one obtains for each arm E Q by using Q for the t-th time, so that in particular D I.. The most natural statistic in this case is the empirical mean given 1 o:1o (t'),
for a multiset O of observations by s(O)= = O Ex 2, such that 8; q(t) which is also the arguably most prevalent statistic used in the realm of bandit problems for guiding the decision making process. However, other statistics such as quantiles or the expected shortfall are of interest as well [13].
bandit setting with winner feedback we observe after the t-th usage of the query set Q only a binary (winner) information, i.e., Q (t) = 1 arm is preferred over the other arms in Q "pull" i and (ti((1) 0 otherwise, mean of these binary observations is a quite intuitive choice for the statistic as in a stochastic feedback setting the corresponding statistic vector 8: (t))()) = + د (1l2(t) would converge to the probability vector determining how likely an arm will be preferred over all the other arms in the query set Q. For preference- -ased bandits with full ranking feedback we observe after the f-th usage of the query set Q an entire ranking of the arms in Q, i... (t) is arm i's rank among the arms in Q at "pull" so that D {1, (l....,k, k]. In such a case the statistic might be a positional scoring rule (28).
In the preference-basee
that D {0, }). Once again the empirical
Goal.
The goal of the learner in our setting is to find a or the best arm (specified below) within a fixed budget of at most B samples (numbers of queries). For any Q, write no (t) for the number of times Q has been queried until (including) time t. An algorithm, which tackles the problem, chooses time set Q Qgk and observes as feedhack oo (nQ, (1)) leading to update of the relevant statistic vector SQ. (nQ, (f)) = (sijQ, (mo, (1))
Best arm. Inspired by the theoretical groundings of Hyperband (25 34 for best arm identifica- tion problems in numerical bandit problems with non-stochastic rewards, we make the following assumption regarding the limit behavior of the statistics
(A1) : AQ Qck Vi Q S.q = lim, - (t exists.
This assumption is in general slightly looser than assuming (stationary) stochastic feedback mech- anisms, as (AI) is fulfilled for many prevalent statistics by means of a limits theorem such as the strong law of large numbers. Conceptionally, our Assumption (A1) is similar to the assumption on the sequence of losses in [25). as both have in common that the statistics (losses in (25)) converge to some fixed point, respectively. However, due to the difference of the action spaces (single arms vs. set of arms) and the nature of the feedback (scalar vs. vector observation), our assumption can be seen as a combinatorial extension of the one in (25
Given assumption (A1) a straightforward notion of a best arm is obtained by leveraging the idea of Borda winner from dueling bandits with pairs of arms as the possible subsets to more general subsets of arms. A generalized Borda winner (GBW) is then an arm which has on average the largest asympotical statistic, i.e.
EQeQ SiQ
is E arg max S.C = arg max EEA
[0)(1)]
where (_)(1)= = (Q 1 iie Q} and S are the asymptotic Borda scores, i... the limits accord- ing to (A1) of of = an arm i, which wins w.r.t. the asymptotic statistics on average on the most query sets, i.e.,
Ees (0) (t)(t) Similarly, a generalized Copeland winner (GCopeW) is [2-((i)
Eqee (1) 1 q = S(ya)
i E arg max S.. = arg max iEA
TEA
(0))

---

However, both these notions of best arm have two major drawbacks, as there might be multiple GBWs and GCopeWs Ws and due to averaging over all subsets in their definition, there is no way to identify a GBW or a GCopeW within a sampling budget of of ((=))) in the worst case (see Theorem 3.1.
In light of these drawbacks, we specify another reasonable notion of a best arm, for which we leverage the concept of the generulized Condorcel winner [ from the preference-based bandits literature. For this purpose, we introduce the following assumption
(A2) : 3i" E such that VQ E (Cx((") Vj Q {i*) it holds that S. a > Syje=
where (1) = (Q E Osk | Q for E [n]. We call i" the generalized Condorcet winner (GCW), which is the arm dominating all the other arms in each possible query set containing it. It is worth noting that such an arm may not exist, but it exists, then it is arguably the most natural way to define the optimal arm, even though it may differ from the GBW. Nevertheless, the existence of the generalized Condorcet winner (or simply the Condorcet winner for the case = 2) is a common assumption in the preference-based bandits literature 4 21 8) Additionally, we will show below that identifying a GCW is possible for a sampling budget of size Q(n/k) even in worst case scenarios.
Problem characteristics. In light of (A1) and (A2), there are two key characteristics which will determine the appeal of any learner in our setting. The first one is the speed of convergence of the statistics sisQ to their limit values Sijo. More precisely, the function 7Mi N + R. which is the point-wise smallest non- non-increasing function fulfilling [t) Sioo] S Hi (t) for any t E N, plays a major role in characterizing the difficulty of the learning problem. Moreover, the worst speed of convergence function of query set Q E Qg* given by (t(t) = maxieq (tip(t) and the overall worst speed of convergence function 7(t)= == maxqe 7g(() will be of relevance as well. Assuming a stochastic setting, the role of NiQ is played by the minimax rate of convergence
of the statistic to its population counterpart, e.g., 1/vl for the empirical mean and the expected value. Usually the speed of convergence functions will appear implicitly by means of their (quasi-) inverses given by Tiee (ax == min(!= E N (1))(1) S a). 30 (l) == minseQ (1) and 5- (() =
minge 1 (t).
The other relevant problem characteristic are the gaps of the limits statistics, i... 4iq = S - S for i E [n]] Q E (i) n (i*( Such gaps are prevalent in the realm of bandit problems, as they can be used to define a measure of (sub-)o jottiooptimaliy of an arm in the stochastic feedback case. Note that in our setting this is not straightforward, as the gaps are depending on the query set and more importantly the speed of convergence has decisive impact on the severeness of these gaps.
3 Lower Bounds
Let us abbreviate S = (SiiQ) and = (1) Given S and y, write
G(S y) for the set of all s = (sig(())gE that fulfill
(i) AQ E 2cK, E Q: S =
(t) exists,
(ii) VQ E Qçn, E Q 1 E N: (s) Shjel S mI(((),
(ii)) VQ Qgki 3πQ : Q + Q bijective such that S/1Q = Sa(11 for all i E Q.
For Q and E (1,..., |Q} write S(ajq for the I-th order statistic of (Sijheeq i.e., (Siihee = (SaiqheE and Sayy 2 2 Suiqpi If Alg a (possibly probabilistic) sequential algorithm, we denote by B(Alg, s) the number of queries made by Alg before termination when started on In the following, we provide lower bounds on E B Alg, 8)] for algorithms Alg, which identify, for any instance G), almost surely one GCW resp. GBW resp. GCope of
Theorem 3.1. Let S be such that Sayj > S(2) for all Q E Qsk- (i) There exists s G(S, 7) such that if Alg correctly identifies a GCW for any instance in G(S y), then
nn
Say1 - S(QQ114)
E. (((Agg
2
2
min QEQ
V
k
2
5

---

(ii) Assume (Stj)...... S(inno) does not depend on for any Q E Q=k. If Alg correctly identifies a GBW for any instance in G 7). then
E [B([Ag, s)] =9 (m-
sup (E)(S,7)
(iii) If Alg correctly identifies a GCopeW W for any instance in G(S 7), then it fulfills
E E| s)] -? =M(
sup xES(S,7)
The theorem is proven in Section B in the supplement, where we provide in fact slightly stronger versions of these bounds.
4 Algorithms
In this section, we present class of algorithms along with three possible instantiations solving the corresponding learning task for the case the generalized Condorcet winner being the best arm. In particular, budget to find the respective best arm. light of the results in Theorem 3.1 for GBW and GCopeW identification, it is straightforward that simple algorithm, which enumerates all possible subsets, pulls each of them equally often in a round-robin fashion, and returns the empirical GBW (or GC)peW) is already optimal. For sake of completeness, show this result for the of GBW identification in Section and also include this simple algorithm in the experimental study below (called ROUNDROBIN).
analyze all algorithms theoretically in terms of their sufficient and necessary
4.1 Generalized Condorcet Winner Identification
In the following we introduce a general class of algorithms Algorithm [T is instan- tiable with various different elimination strate- gies of the arms. Below, we present some instantiations which build on commonly used elimination strategies in the standard multi- armed bandit setting. The idea of Algorithm I is simply to maintain set of active arms, which is successively reduced by following specific arm elimination strategy (Algorithm 2) referred to elimination rounds. In each climination round r E ?1.2..... R} the set of active arms A, is partitioned into P, many sets size is (up to a possible remainder set) denoted by (Jrr,) for which the elimi- nation strategy is applied with a roundwise- dependent budget by. The budget allocated to a partition Ar..j in round r is of the form b, [B/ P.)1 following the idea split up the available budget equally first for each round and second for all partitions each round. The explicit arm climination strategy used in Algorithm [ specified by Algorithm and corresponds to pulling the chosen query set Q for a fixed number of times and after- wards keeping only the best f((Q1) arms of Q Here, f [k] - [k] is an arbitrary function with (x) < x for all æ which essentially determines the aggressiveness or conserva- tiveness of arm elimination strategy as we will see below.
Algorithm Combinatorial Successive Elimination
Input: set of arms [n]]. subset size k S n, sam- pling budget B, a function f [k] - [k]. sequence {Pr)r (number of partitions at round r), R (number
of rounds in total) Initialization: A +- [m], x-1
1: while | k 2
b, + B/(P,R]] J Pr A,, Ar. A t- Partition(Ar.h k)
3:
if |A, < then
5:
R + Ay,,, J t J
clse
7:
R <- 0
end
Ar+1 +- R
10:
for j E [J] do
11:
R t- ArmElimination (Argi br,
f(lAr,))
12:
A,+1 Art1 UR
13: end for
+1 15: end while
14:
16: Ar+1 <- 0
17: while |A, > 1 do
18: A,41 + Arm ArmEliimation (Ar br.
f(AA++1)) r r 19: end while
Output: The remaining item in A,

---

In the following we provide three possible instantiations of Algorithm [ inspired by commonly used elimination strategies in the standard multi-armed bandit setting for pure exploration tasks.
Combinatorial Successive Winner Stays. The most aggressive elimination strategy is to keep only the arm with the best statistic (the winner) of each partition in each round and discard all others from the set of active arms for the next round. Concretely, we use (csws (8) = for f in Algorithm 1 in this case.
Algorithm ArmElimination (A',b.
Use A' for times
2: For all i E A', update S3ta/ (b)
Choose an ordering 4pr of
(8; a' (b)))))))
4: return {
The resulting instantiation of Algorithm ! is called Combinatorial Successive Winner Stays (CSWS), which has at most RCSWS [logx (n)) many rounds in total (at most [log, (n:] rounds in the first while-loop and at most in the second). The total number of partitions in round r is at most PCSWS [n/sr]]
Combinatorial Suecessive Reject. On the other extreme regarding the aggressiveness of the arm elimination strategy is to dismiss only the worst arm of each partition in each round and keep all others in the set of active arms for the next round. More specifically, we use fCSR (s) 8 for this variant, which can be seen variant of the Successive Reject algorithm [5] for best arm identification adopted to the combinatorial bandit problem. Consequently, we call the resulting instantiation of Algorithm the Combinatorial Successive Reject (CSR) algorithm, whose number of rounds in the first while-loop is at most [loge-1/x (1/n] and in the second at most & - 1. Overall, we have maximal number of rounds RCSR = floge 1/4 (2/n]] + k and maximal number of partitions per round PCSR = [n(1- (0 ///-"/>)]
Combinatorial Successive Halving, As compromise between the aggressive elimination strategy of CSWS and the conservative elimination strategy of CSR one could discard in every elimination round the worse half of all arms in the partition, i.e., using (C)H(() (s) T for f in Algorithm
I. This can be seen as generalization of the successive halving algorithm 23 adopted to the combinatorial bandit problem we are considering. Thus, the instantiation of Algorithm in this spirit will be called the Combinatorial Successive Halving (CSH) algorithm. Note that we have at most [log2(n) rounds in the first while-loop and additional [log2 (k)] in the second while-loop resulting in at most ROSH- [log2(m)] [log(()) many rounds throughout a run of CSH. Furthermore, we partitions in round
have most PCSH = -
4.2 Theoretical Guarantees
In the following, we derive the sufficient budget for Algorithm I to return under assumptions (A I) and (A2) the best arm i", i.e., the generalized Condoreet winner. For this purpose, we write A, (i*) for the unique set A E {Ar,, A.. with i* E Aors and define Anni = S;1 - S(niQ for any Q S [n] with 1" E Q.
Theorem 4.1. Assume P., R are such that Algoritium 7 ccalled with B does not exceed B as total budget. Under Assumptions (Al) and (A2) Algorithm ? returns i if B is larger than
= =S, (...(risssn)) = R max,e.]) [R] Pr (T,..e)) (Prttee((ur0saaaaa) (A000,000)40000000)
The following theorem indicates optimality of in the theorem above (cf. Sec. D.2 for the proofs). Theorem 4.2. For any distinct asymptotic values S, there exists a family of statistics with (t) + SaqQ for all [n], Q E Qck such that if Algorithm 7 is used with budget B 2 , R, (Pr)iSeR)) then it does not return i*.
By means of Theorem 4.1 we can infer the following result regarding the sufficient sampling budget B for the three instantiations to output i" (cf. Sec. D.3 of the appendix for the proof).
Corollary 4.3. Under Assumptions (AI) and (A2), CSX E (CSWS, CSR, CSH) returns i" if it is executed with budget B 2 zCSX, where zcSx == z (feSX RCXX [ Jigggnex)..
By substituting the concrete values for P,, R and f of the corresponding instantiation into Corollary 4.3 and using a rough estimate for the inverse function of the speed of convergence, we that all of
7

---

the resulting sufficient budgets are essentially (*/ss) (see Table almos matching the dependency on n and k in Theorem 3.1 If we would allow the special case singleton sets of arms as query sets, i.e., k = 1, the sufficient budget for CSH matches the one derived in [25] for its non-combinatorial counterpart in the special case of numerical feedback.
Table I: Sufficient budget for CSWS, CSR and CSH. Here, π is as in (iii) in Section
[ (logs (n)] + +1) maxxeR maxicou((t) [5-1 (Srie--Sue
scSWs
[el [oog 1. (+) + k: 11) .maxQEQsNiEE minicou
7-11
81011 P1-10-8110
20SR
2
[#l ([lg2(n)] + (k)]) max [
[8110 Smione
#CSH
2
Regarding n and both lower and upper bounds coincide, but the gap-term in the lower bounds include min-term over Qck: while the gap-term in the upper bound are coming with a max-term over 2ck- The difference between these terms depends on the underlying hardness of the bandit problem in terms of 7 i..., how fast the considered statistics converge to their limit values. Due to the generality of our setting it is difficult to specify this difference more explicitly and would be worth considering this for special cases, i.e., the numerical bandits preference-based bandits separately.
Finally, it is worth mentioning that all of the three instantiations of Algorithm D have only been studied for the case single arm pulls, but not for pulls of subsets of arms, where additionally a dependency on the set might be present. Thus, the theoretical guarantees novel in this regard.
Applications Stochastic Settings
Numerical feedback. In stochastic combinatorial bandits (16), each arm-query set pair (i, Q) is associated with a probability distribution ViQQ and querying Q for the 1-th time results in the feedback (t) ~ ViQ. usually referred to as reward (i.e., = R). The sequence of rewards {t) is supposed to be independent and the statistic is the empirical mean such that (A1) holds by the law of large numbers with Q = Ex [ If the VijQ are Gaussaass,, an anytime confidence bound by [24] based on the law of iterated logarithm ensures (+)))(() -
Saol S cs(l) for all E with probability least 8 for some appropriate function ca) O ( (((TTI(((((())))) This implies the following result, the proof of which is deferred to Section
Corollary 5.1. Let S; R and (Pr)re(R) be as in Theorem butions ViQQ be a-sub-Gaussian and such that their means Sii satisfy (A2). There is function C(ō, k, R) O (o2E (KR/s in (kRR//66)) such that if i" is the optimal arm for (Sa12) QE and supqeR<a(1)) AuriD+1iiQ e, then Algorithm used with a budget B larger than C(ô,s, e, k, R, o). R max,e[m P. returns i" with probability at least 8-8.
and suppose the reward distri-
Other statistics for numerical feedback. A rich class of statistics can be obtained by applying linear functional U(F) = (x))dF(x)), where F is a cumulative distribution function (CDF) and r: R + R some measurable function [4), on the empirical CDF, i.e., 8(0, x) = 101-- 1 S o). for any x e IR and any multiset of (reward) observations O. This leads to the statistics
Σ 2== r(ogq()))
(t) U13(o::(()......
which converge to Sij = Ex~raq [r()) by the law of large numbers, provided these expected values exist. For this class of statistics can show quite similar result to Corollary [5. by generalizing the findings in [24] (see Section E}. However, the result is fact more general than Corollary 5.1 for being the identity function
recover the empirical mean.
Heer, Ô hides logarithmic factors.
8

---

Preference feedback. In the preference-batee based bandits, we observe when querying Q for the t-th time a categorical random variable with values in Q. i.e. (1jo(t) Cati (Po) for some underlying unknown parameter PQ (pI Let wij Eest (t) = i} be the number of times arm i has won in the query set Q until the f-th pull of Q. We consider as the relevant statistics "Ha((t) which converge to PitQ =: Suje by the law of large numbers. The Dvoretzky- Wolffo--Woloiitz inequality [19] ensures a concentration inequality on supieo [sij(()) - Saol which can be used to deduce the following result (ef. Sec. [ for the proof).
$10 (t) = f
Corollary 5.2. Let f.R and (Pr)re(m) be as in Theorem 4.1 and suppose preference- winner feedback with parameter (pilQ)QERsa.e C(,,e,k, R) E ( In (B/oe)) with the following property: If i the optimal arm and (())) A( S E, then Algorithm| 7 used with a budget B larger than C(ô, e, k; R) R max P. returns i* with probability at least 6.
which satisfies (A2). There is function
By substituting the concrete values for P., R and f of the corresponding instantiation of Algorithm I into the bound on the budget in Corollary [..2 (compare to Table []. we see that each of the three resulting bounds almost matches the optimal sample complexity bounds for identifying the (generalized) Condorcet Winner under fixed confidence in preference- based bandits 88 [1 indicating near optimality of the algorithms in stochastic settings. However, since stochastic counterpart of our combinatorial setting for the numerical case exists, it would he interesting to investigate whether the analogous implication by means of Corollary 5. for the three algorithms is nearly optimal as well. We leave this to future work, as it is beyond the scope of our work.
Experimental Section
In this section we present an experimental study for our proposed algorithms on an algorithm selection problem. Further experiments, also on synthetic data and with other statistics are provided in the supplementary material in Section G
Setting. In the following, we consider an algorithm selection problem, where the goal is to select the most efficient algorithm for solving instance of satisfiability (SAT) problem. For this, we randomly chose n = 20 parameterizations of the SAPS solver (23 which represent our candidate algorithms and correspond to the arms in terminology. Our possible problem instances are sampled from the first 5000 problem instances from the sat mat_SWGPP folder of the AClit We compare CSWS, CSR, CSH and ROUNDROBIN algorithm 225. To the best of our knowledge, there are no algorithms available as baselines, which designed for the pure exploration problem with finite budget and subsets of arms as the actions, e.g., 4 investigates a regret minimization problem, while (2 is dealing with a stochastic pure exploration setting with fxeedconfidence. However, Successive Halving serves as a baseline, which we included as a representative for the algorithms dealing with a pure exploration problem with finite budget and single arms as the actions. In each learning round, we randomly draw a problem instance from the 5000 problem instances without replacement and then start a parallel solution process with the SAPS parameterizations chosen by the corresponding learning algorithm (only one parameterization for the case of SH), where the process is stopped as soon as the first algorithm has solved the current instance. In particular, one obtains only for the "finisher" SAPS parameterization an explicit numerical value (its runtime) among the chosen set of SAPS parameterizations, as the others are right-censored. Since our proposed algorithms are designed for the case, which feedback for all arms in the pulled query set is observed, while SH is designed for the case in which only single arm is queried resulting in a single feedback, we enlarge the available budget for SH to B for fairer comparison.
this problem with the Successive Halving (SH)
Instantiation of CSE. Although we could consider the negative runtimes of the parameterizations as rewards (i.e., runtimes correspond to losses) and use statistic suitable for numerical feedback for the combinatorial successive elimination (CSE) approaches, there might be a major disadvantage due to the censored runtimes. Indeed, in order to apply a statistic suitable for numerical feedback, some sensible imputation technique is required to deal with the censored observations, which in turn could introduce severe bias. However, thanks to the generality of our framework, we can simply
hhtt://www.accib..ee
9

---

4
k=
1.0
100
Succesa rato
0.-
04
04
8.
CSR
RoundRobin
CPN tine
0.8
0.8
1.0
Successive Haiving
0.5
0.4
Budget
Budget
Budget
Figure 1: Success rates and runtimes for different subset sizes and budgets B.
interpret the observed feedback as a preference the sense that the "finisher" SAPS parameterization preferred over the others in the chosen set of parameterizations. In this way, using statistic based on preference- feedback defuses the bias issue. Quite naturally, we use the relative frequency statistic for preference feedback as specified in Section
Analysis. As the best arm (SAPS parameterization) we use the one having the smallest empirical runtime over all problem instances such that ROUNDROBIN and SH will tendentially return this arm the budget sufficiently large. The resulting success rates for our proposed algorithms and SH of identifying the best arm are illustrated in the top panel of Figure [ One can see, that the algorithms which follow our CSE strategy significantly outperform SH the budget is sufficiently large. In addition, CSWS, CSR and CSH identify the best arm more often than ROUNDROBIN if the subset sizes k are small, which a realistic situation practice. Moreover, the bottom panel Figure shows the overall runtimes of the algorithms revealing that SH takes much longer than CSWS, CSR and CSH and as expected the difference the runtimes gets larger with the subset sizes Quite interestingly, even ROUNDROBIN needs longer runtime than the CSE approaches, although queries the same number of subsets and also stops the respective run as soon as the "finisher" SAPS parameterization is clear. Thus, the differences in the runtimes of ROUNDROBIN and the CSE approaches are only due to the fact that the latter discard the slowest SAPS parameterizations quickly and do not them again, while ROUNDROBIN uses throughout all subsets the same amount of time, even they contain only bad performing parameterizations. In other words, the differences are due to the sophisticated strategies of the CSE approaches.
7 Future Work
For future work, it would be interesting to investigate whether switching the elimination strategy during the learning process leads any performance improvements both theoretically and empirically, A similar question could be asked regarding the considered statistic for numerical feedback variants. Further, the goal of identifying the best set of arms our scenario would also interesting. However, in the case where the observations depend on the chosen set of arms, it is far from obvious how to define suitable optimality term (cf. Sec. 6.3.2 88). Finally, a more extensive experimental study would definitely be relevant future direction of research, especially for hyperparameter optimization problems with possible parallelization options such as in [33 or for more general
algorithm configuration problems 44
Acknowledgments and Disclosure of Funding
This work was partially supported by the German Research Foundation (DFG) within the project "Online Preference Learning with Bandit Algorithms" (project no. 317046553) and by the research training group "Dataninja" (Trustworthy Al for Seamless Problem Solving: Next Generation Intelli- gence Joins Robust Data Analysis) funded by the German federal state of North Rhine- Westphalia.
10

---

References
[1] Yasin Abbasi- Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Proceedings of Annual Conference on Learning Theory (COLT), pages 918-949, 2018.
[2] Yasin Stochastic Bandits. In Proceedings of Advances in Neural Information Processing Systems (NeurlPS), pages 2312 2320, 2011.
Dávid Pál, and Csaba Szepesvári. Improved Algorithms for Linear
[3] Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In Proceedings of the International Conference on Machine Learning (ICML), pages 3-11, 1999.
[4] Arpit Agarwal, Nicholas Johnson, and Shivani Agarwal. Choice bandits. In Proceedings of Advances Neural Information Processing Systems (NeurlPS), 2020.
[5] Jean Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Proceedings of Annual Conference on Learning Theory (COLT), pages 41-53, 2010.
[6] Peter Auer. Using confidence bounds for exploitaiion-explortiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422) 2002.
[7] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 322-331. IEEE, 1995.
[8] Viktor Bengs, Róbert Busa-Fekete, Adil EI Mesaoudi-Pane and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22:1-108, 2021.
[9] Viktor Bengs and Eyke Hüllermeier. Preselection bandits. Proceedings of the International Conference on Machine Learning (ICML), pages 778-787, 2020.
[10] Brian Brost, Yevgeny Seldin, Ingemar J. Cox, and Christina Lioma. Multi-dueling bandits and their application to online ranker evaluation. In Proceedings of ACM International Conference on Information and Knowledge Management (CIKM), pages 2161-2166, 2016.
[11] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
[12] Sébastien Bubeck and Aleksandrs Slivkins. The best both worlds: Stochastic and adversarial bandits. In Proceedings of Annual Conference on Learning Theory (COL.T), pages 42. 12.1-22..3 2012.
[13] Asaf Cassel, Shie Mannor, and Assaf Zeevi. A general approach to multi-armed bandits under risk criteria. In Proceedings of Annual Conference on Learning Theory (COLT)), pages 1295-1306, 2018.
[14] Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1444)11444 2012.
[15] Wei Chen. Yihan Du, Longbo Huang, and Haoyu Zhao. Combinatorial pure exploration for dueling bandit. In Proceedings of the International Conference on Machine Learning (ICML), pages 1541- PMLR, 2020.
[16] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial aame bandit: General framework and applications. In Proceedings of the International Conference on Machine Learning (ICML), pages 151-159, 2013.
[17] Wei Chu, Lihong Li, Lev Reyzin, and Robert F. Schapire. Contextual bandits with linear payoff functions. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pages 208-214, 2011.
11

---

[18] Yihan Du, Yuko Kuroki, and Wei Chen. Combinatorial pure exploration with full-bandit or partial linear feedback. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 7262-7270, 2021.
[19] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sam- ple distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642 669, 1956.
[20] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Proceedings of Annual Conference on Learning Theory (COLT), pages
2016.
[21] Björn Haddenhorst, Viktor Bengs, and Eyke Hüllermeier. Identification of the generalized Condorcet winner in multi-dueling bandits. Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
[22] Joel Huber and Christopher Puto. Market boundaries and product choice: Illustrating attraction and substitution effects. Journal of Consumer Research, 10(1):31-44 44, 1983.
[23] Frank Hutter, Dave AD Tompkins, and Holger H Hoos. Scaling and probabilistic smoothing: Efficient dynamic local search for SAT. In International Conference on Principles and Practice of Constraint Programming, pages 233-248. Springer, 2002.
[24] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'UCB An optimal exploration algorithm for multi-armed bandits. In Proceedings of Annual Conference on Learning Theory (COLT), volume 35, pages 423 4394449.200 2014.
[25] Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparam- eter optimization. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pages 240-248, 2016.
[26] Marc Jourdan, Mojmír Mutny, Johannes Kirschner, and Andreas Krause. Efficient pure explo- ration for combinatorial bandits with semi-bandit feedback. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), pages
2021.
[27] Johannes Kirschner and Andreas Krause. Bias-robust Bayesian optimization via dueling bandits. In Proceedings of the International Conference on Machine Learning (ICML), pages 5595-5605, 2021.
[28] Anna Korba. Learning from ranking data: theory and methods. PhD thesis, Université Paris-Saclay (ComUE), 2018.
[29] Michael R. Kosorok. Introduction to Empirical Processes and Semiparametrie Inference. Springer, New York, USA, 2008.
[30] Yuko Kuroki, Liyuan Xu, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Polynomial- time algorithms for multiple-arm identification with full-bandit feedback. Neural Computation, 32(9):173311773 2020.
[31] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, 6(1):4 22, 1985.
[32] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[33] Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Jonathan Ben-tzur, Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. A system for massively parallel hyperparameter tuning. Proceedings of Machine Learning and Systems (MLSys), 2:230-246, 2020.
[34] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh. and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, (8(1):6765-6811 2017.
[35] Pascal Massart. The tight constant in the Droretaky-Kiefer-Woooon inequality. The Annals of Probability, 18(3):1269 1283, 1990.
12

---

[36] Soheil Mohajer, Changho Suh, and Adel Elmahdy. Active learning for top-k rank aggregation from noisy comparisons. In Proceedings of International Conference Machine Learning 2017.
(ICML), pages
[37] Felix Mohr, Viktor Bengs, and Eyke Hüllermeier. Single player Monte-Carlo tree search based on the Plackett-Luce Model. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), volume 35, pages 12373-12333 2021.
[38] Rémi Munos. From bandits Carle tree search: The optimistic principle applied to optimization and planning. Foundations and Trends@ in Machine Learning, 7(1):1-129, 2014.
[39] Wenbo Ren, Jia Liu, and Ness Shroff. On sample complexity upper and lower bounds for exact ranking from noisy comparisons. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 10014-10024, 2019.
[40] Wenbo Ren, Jia Liu, and Ness Shroff. The sample complexity of best-k items selection from pairwise comparisons. In Proceedings of the International Conference on Machine Learning (ICML), pages 8051-8072, 2020.
[41] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[42] Aadirupa Saha and Aditya Gopalan. Battle of bandits. In Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI), pages 805-814, 2018.
[43] Aadirupa Saha and Aditya Gopalan. From PAC to instance-optimal sample complexity in the Plackett-Luce model. In Proceedings of International Conference on Machine Learning (ICML), pages 8367-8376, 2020.
[44] Elias Schede, Jasmin Brandt, Alexander Tornede, Marcel Wever, Viktor Bengs, Eyke Hüller- meier, and Kevin Tiemey, A survey of methods for automated algorithm configuration. Journal of Artificial Intelligence Research, 75, 2022.
[45] Cong Shen. Universal best arm identification. IEEE Transactions on Signal Processing, 67(17):4464 4478, 2019.
[46] Max Simehowitz, Kevin Jamieson, and Benjamin Recht. Best-of-k- In Proceedings of Annual Conference on Learning Theory (COLT), pages 1440-1489, 2016.
[47] Itamar Simonson. Choice based on reasons: The case of attraction and compromise effects. Journal of Consumer Research, 16(2):158-1744 1989.
[48] Amos Tversky, Elimination by aspects: theory of choice. Psychological Review, (9())221,, 1972.
[49] Larry Wasserman. All of Statistics: A concise Course in Statistical Inference. Springer Science & Business Media, 2013.
[50] Shuo Yang, Tongzheng Ren, Inderjit S Dhillon, and Sujay Sanghavi. Combinatorial bandits without total order for arms. arXiv preprint arXiv:2103.02741, 2021.
[51] Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (SFCS), pages 222-227, 1977.
[52] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 7865):158 2012.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section !
(b) Did you describe the limitations of your work? [Yes] See Section S and also our
discussion about future work (Section 7).
(c) Did you discuss any potential negative societal impacts of your work? [No] The results are rather theoretical and do not have societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] In Section we describe and motivate our assumptions (AI) and (A2).
(b) Did you include complete proofs of all theoretical results? [Yes] See Section B for the proofs of the lower bounds results Section Section D for the results in Section 4.2
and finally Section E for the results in Section 5
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen-
tal material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The runs of the experiments are so fast, that the resources do not matter.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6
(b) Did you mention the license of the assets? [No] But assets cited.
(c) Did you include any new assets either in the supplemental material
URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] But the data is freely available.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] Not necessary, because the used data are runtimes of algorithms and does not contain personally identifiable information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [No] Not applicable.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [No] Not applicable.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [No]
14


Reviews:
[{"review_id": "hsxp1I3MUNl", "reviewer": "Reviewer_q5ks", "summary": "The authors consider a generalization of the best arm identification problem under a fixed budget setting. The agent seeks to identify the best base arm, but can take actions of subsets (up to cardinality $k$) each time and receive semi-bandit feedback.  The feedback’s properties (like base arm expected values for stochastic setting) can vary with the subset chosen, though some ordering (in the sense of a Condorcet winner) is assumed across all possible subsets.  Additionally, the authors generalize the domain of the feedback, encompassing both (numerical) reward feedback and preference feedback (like dueling bandits).  With this, the authors identify lower bounds on the sampling budget, propose several successive elimination type algorithms (varying in eliminating just the worst, all but the best, or the worst half) and identify their corresponding upper bounds on the sufficient budget.  The authors also run experiments on both numerical reward feedback and preference feedback problems.", "questions": "- lines 281-283 mention if $k=1$, sufficient budget for CSH matches that for [24], though is that is only if singletons are used (ie CSH can only pick individual arms as opposed to allowing it pick subsets of arms of cardinality $\\ell=1,\\dots,k$)?  For preference feedback it may be vacuous to consider allowing single arm actions (when $k>1$), but for numerical feedback there may be cases where it could be beneficial.  Though perhaps not helpful enough to affect bounds without additional assumptions.\n\nMinor clarifications\n- While the basic assumption that statistics have limits (A1) is general (allowing statistics for the same arm $i$ to vary considerable based on query set $Q$, under (A2) that there is a (generalized) Condorcet winner more or less reduce to the ‘Choice model’ proposed in [4]?\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths (major)\n- This paper addresses a novel setting – (oblivious) non-stochastic BAI with combinatorial actions under a fixed budget, and is general enough to cover both preference and numerical (reward) vector feedback.  [I think the contribution is especially significant for settings with preference feedback]   \n- Lower bounds on the budget are provided and upper bounds analyzed for three algorithms (all partition and remove arms, but vary in how aggressively remove arms) \n- Overall the paper is well-written\n- The supplementary material covers a number of additional helpful points\n- I did not carefully review proofs; that being said I did not spot any issues with the results\n\n\nStrengths (minor)\n- The allowance for statistics to vary based on the query set appears more general than (many) prior works that assuming latent parameterized preference models like Plackett-Luce or even randomized utility models.  (though assumption (A2) restricts the statistics to have important structure for making the problem tractable that is present in earlier models)\n\nWeaknesses (major)\n\n-[I did not identify any major weaknesses]\n\nWeaknesses (minor)\n- The setting considered appears well motivated for preference feedback, but I think needs more motivation for numerical feedback.  In particular, (1) the problem of looking for only a single base arm when actions can consist of subsets of arms, (2) the definitions of ‘best arms’ as a Borda, Copeland, or Condorcet winner (3) the feedback vector assumption, and (4) the agent cannot pick a single arm $Q={i}$, the minimum cardinality is 2, all appear to be natural properties for problems that motivate BAI with preference vector feedback.  For numerical feedback, however, works on pure exploration with combinatorial action spaces consider identifying the best action (ie subset), since subsets could have larger rewards than base arms.   \n- The baseline used in experiments, RoundRobin, does not exploit (A2)-- the experiments would have been stronger if other/additional baselines had been used.  In particular, using algorithms assuming stochastic feedback with preference vector feedback and that also exploit (A2), perhaps those of [4] or [21].  They may suffer against oblivious adversaries, but could provide much more informative baselines for experiments.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7QZsqC8gVZv", "reviewer": "Reviewer_pjkv", "summary": "This paper considers the combinatorial bandits problem with semi-bandit feedback and finite budget constraint, and introduces novelty by considering non-stochastic and subset-dependent feedback. Towards solving the problem the paper introduces algorithms based on successive elimination and provides corresponding lower bounds on the problem. Numerical experiments demonstrate the power of these algorithms in different contexts. ", "questions": "N/A. See weakness section for more details.", "limitations": "See weaknesses for more details.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is overall well-organized, with each section clearly stating what it does. Theoretical guarantees on upper bounds are also provided for each algorithm in discussion, and intuition is overall clear with corresponding lower bounds. \n2. The experiments are indicative of the theoretical claims made in the paper. Sufficient details have been provided to make reproduction possible.\n3. Related work and future work are also included with comprehensive discussion.\n\nWeaknesses:\n1.Some theorems could be better formatted in the paper. For instance, the section on lower bounds is a bit hard to read with the lack of paper spacing. \n2. It would be helpful if the authors could further explain the relationship between the lower bounds and the respective upper bounds the algorithms are able to achieve, as the statements in their current forms are not immediately clear.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6u4AggRODs4", "reviewer": "Reviewer_8B47", "summary": "This paper studies a bandit problem where at each time $t\\in\\left\\lbrace 1,...,B \\right\\rbrace$, the decision maker can query a subset of size  at least $2$ and at most $k$ from a collection of $n$ arms (naturally, $k \\leqslant n$). Upon query, a semi-bandit feedback is realized which comprises of an observable for each arm in the query set. This observable could be a real-valued reward, a 0/1-valued outcome indicating the ``winner,'' or the rank w.r.t. other arms in the query set. The semi-bandit feedback could be generated by an oblivious adversary.\n\nThe authors make two assumptions on the underlying dynamics. (A1) Fixing an arm and a query set, some test function (statistic) of the sequence of observations from said arm converges to a well-defined asymptotic limit. This is a fairly general condition that settings with, e.g., i.i.d. or ergodic rewards naturally satisfy. The second assumption (A2) posits the existence of a generalized Condorcet Winner (GCW), which is the arm dominating all the other arms in each possible query set containing it. Such an arm need not necessarily exist but the authors claim there are antecedents in the literature that rely on this assumption.\n\nSubject to this premise, the authors study the Best Arm (GCW) Identification problem in the fixed budget setting with $B$ samples. Lower and upper bounds are investigated for this problem setting (the latter for separate instantiations of a successive elimination-based meta-algorithm). Results are evaluated in the special case of stochastic combinatorial bandits; a more general setting is evaluated numerically.", "questions": "The paper is generally well-written, but it would really help readers who are not entirely abreast of developments in this area if the actual optimization problem that the authors set out to solve is stated formally and clearly at some point. This would also make it easier to interpret the lower and upper bounds derived in the paper.\n\nW.r.t. the algorithmic proposition, each of the three routines that the meta-algorithm can be instantiated with is well-studied in the literature. Other than that, am I missing any innovation? I would like to see the authors discuss the benefits of their framework (if any) other than providing a unified higher-level abstraction.", "limitations": "The paper is written in a way that this aspect appears to be generally well-addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To my knowledge, the BAI problem for combinatorial semi-bandits under (oblivious) adversarial feedback is certainly novel. However, I am not very well-positioned to evaluate the technical innovations in this work vis-\\`a-via the extant body of work in the area. Though I do have a couple of broad comments (see the next section).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept