Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: 
Strengths (major)
- 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]   
- 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) 
- Overall the paper is well-written
- The supplementary material covers a number of additional helpful points
- I did not carefully review proofs; that being said I did not spot any issues with the results


Strengths (minor)
- 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)

Weaknesses (major)

-[I did not identify any major weaknesses]

Weaknesses (minor)
- 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.   
- 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.

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.

Minor clarifications
- 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]?

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

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

Subject 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.
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).
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.

W.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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:
1. 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. 
2. The experiments are indicative of the theoretical claims made in the paper. Sufficient details have been provided to make reproduction possible.
3. Related work and future work are also included with comprehensive discussion.

Weaknesses:
1.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. 
2. 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.


questions: N/A. See weakness section for more details.
limitations: See weaknesses for more details.
review_title: null

Meta-review: metareview: The reviewers came to consensus that this paper has a good contribution to the study of pure exploration for the combinatorial bandits. On the other hand, several minor concerns such as the motivation, experiments and algorithmic novelty, are raised. I agree that these concerns are reasonable and please polish the manuscript by addressing these points in the final version.
confidence: Certain
Decision: Accept