Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors are interested in the combinatorial pure exploration problem, in which one aims at identifying the best "super arm" (a subset of "base arms") among a decision class that can arise from a certain combinatorial structure. In this paper, they focus on the combinatorial pure exploration problem in the specific case where the reward of a super arm is the minimum of the rewards of the base arms it contains. This very specific function -- called the bottleneck reward function -- raises very specific challenges when solving the combinatorial pure exploration problem. 
The authors explain that none of the existing work on pure exploration or on multi armed bandits give good guarantees in the specific case of the bottleneck function, and propose tailor-made algorithms that exploit the specificities of the said function to reach optimal guarantees, both in the fixed-confidence setting and in the fixed-budget setting.
main_review: —  Strengths
The paper is overall very well written and easy to follow, as is the supplement with very clear and well guided proofs.

The problem is well explained and related works -- to my knowledge -- adequately cited. 
The studied problem — combinatorial pure exploration with bottleneck function (CPE-B) is part of the more general combinatorial pure exploration problem (CPE), for which there exists several published works in the case of several classes of reward functions (linear, continuous and separable).
This work however focuses on the combinatorial pure exploration problem in the specific case where the reward function is the bottleneck function — i.e. the reward of a super arm is the minimum of the rewards of the base arms it contains — for which classical algorithms do not give significant guarantees. The author clearly explicit the specific challenges associated with CPE-B, namely, (1) the fact that the optimal sample complexity relies on base arm gaps which are tighter than super arm gaps, (2) the existence of unnecessary base arms which do not contribute to the reward of super arms.

The authors then propose several contributions to solve these problems. In the fixed-confidence setting, the authors propose the BLUCB algorithm which uses the specificities of the bottleneck function (e.g. its monotonicity) to focus on promising “critical” arms (i.e. the arms on which the reward on super arms relies) and solve the first challenge [Theorem 1], while BLUCB-parallel offers a solution to the second problem [Theorem 2]. The authors propose a lower bound [Theorem 3] which shows the optimality of their previous results.
In the fixed-budget setting, the authors propose the BSAR algorithm which provides optimal error probability [Theorem 4].

As far as I understand, the claims and associated proofs are correct, and all these contributions are novel. The authors therefore provide a very complete and realistically implementable solution to the CPE-B problem.

The proposed algorithms rely on several offline procedures/oracles, which complexity the authors adequately discuss in the supplement, removing any possible interrogation regarding the realistic implementability of the proposed methods.


— Minor remarks
There are a few typos here and there (e.g. L72 "in *an* online environment", L84 "for *the* bottleneck identification task", L137 "denote*s* the set", L159 "has *a* higher bottleneck value than \tilde{M}_t")

The authors solve a very specific instance of a problem that they themselves introduce. While I absolutely do not think that this is a rejection argument since pioneer work is crucial, I think that the motivation for the problem -- given its specificities -- could be better brought forward. The authors motivate the study of CPE with the bottleneck reward function by its natural occurence in communication networks, traffic scheduling and neural architectural search, I am however not aware in any prior interest in this reward function in the “theoretical” MBA/PE community, and would have liked a more detailed theoretical motivation, or experiments that reflect the applied motivation (by using data simulating one of the mentioned application fields for example). 
Another possibility would be to give more insights in the main text concerning how solving the CPE-B problem could be a stepping stone to solving the CPE problem with a larger class of non-linear reward functions (as mentioned in the future work section and in the supplement) -- which I believe would be a significantly more impactful contribution.

The complexity of all proposed algorithms is polynomial in E and V. My understanding is however that in some combinatorial problems, E and V might me exponential in n (i.e. subset selection problem), in which case the algorithms would not run in polynomial time with respect to n. This is not an important issue but I find the text of the first sections a little ambiguous concerning which quantities the "polynomial time" refers to.

The reliance on small delta (<0.1, <0.01), both for Theorem 2 and 3 could be explained in a clearer way in the main text.

---- POST-REBUTTAL UPDATE
After reading the other reviews, the author responses to these reviews and the additional comments from reviewer 69qt, I wish to keep my original score of 7. I agree that the paper is densely written and packs a lot of information, but I believe that the authors managed to present the material in a structured and clear way nevertheless, which in my opinion makes it a strength of the paper in the end. The "experiments" section could benefit from additional results in a "real-world" setup that would help with the motivation of the problem introduced in the paper, which the author propose to do in their revised version.
limitations_and_societal_impact: The authors provided some research directions arising from their work, one of which being the investigation of general non-linear reward functions (going beyond the bottleneck reward function and its specificities). They did not discuss the potential negative societal impact of their work, which I do believe is absolutely minimal due to its very theoretical nature.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers a combinatorial bandit problem, where the reward of super arm (a subset of base arms) is determined by the minimum of rewards from the individual base arms, while only base arm is played in exploration, i.e., semi-bandit feedback. The authors propose two algorithms for pure exploration in fixed-confidence and fixed-budget settings, with asymptotical optimality.

main_review: The proposed method is proven to be efficient as it matches the asymptotical order of lower bound of sample complexity (Theorems 2 & 3). The simulation results support the superiority of the proposed methods. In what follows, I leave some concerns and comments on this work.

- The analysis in the fixed budget setting (Theorem 4) seems a straightforward extension of existing work [10], c.f., line 311. Please elaborate differences and challenges. In addition, it is unfortunate that there is no lower bound analysis for the fixed budget setting. It would be great if the paper includes some conjectures.

 - The paper studies semi-bandit feedback setting, where each base arm is individually explored. This needs to be justified. In addition, if the lower bound of sample complexity in Theorem 3 works for only semi-bandit feedback setting, it needs to be clearly stated.

- I'm not sure if the experiment on the fixed budget setting shows a clear dominance of the proposed method over the others.
limitations_and_societal_impact: .
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the extension of a combinatorial bandits problem studied by S. Chen et al, NeurIPS 2014. The extension here is to consider  (expected) reward as the minimum reward of the elements of a set rather than a linear combination as studied in Chen et al. 

We are given a set of super-arms (which may overlap). The reward function associated with each super-arm is the minimum expected value of the reward associated with each of the base-arms in that super-arm. The problem is to find the best super-arm, the one with the maximal expected reward. 

The paper provides algorithms, and upper and lower bounds on sample complexity for a given confidence bound, and error probability bound for a given budget.  

The paper (including the supplemental material) is densely written with sparse discussion of the results. A table of notations would considerably help the reader. 

Reported simulation results are limited. 

Some of the motivating examples need better articulation (e.g. bottleneck path problem). 
main_review: The paper provides an extension of [10], extending the results from linear rewards considered in [10] to bottleneck or minimum rewards. It  provides algorithms to find the bottleneck arm and corresponding super-arm(s), upper and lower bounds on sample size, under fixed confidence level, and error probability under fixed budget. 

The suggested use-case of bottleneck shortest path needs further clarification. The shortest path, for example in a communications network, is chosen so as to transfer information from a source node to a destination node; what does sampling a base arm mean in this context? Given a collection of S-D paths, it makes sense to sample the paths (or super-arms); during the exploration phase, this will achieve the goal of information transfer (even if it is inefficient). Sampling base arms is wasteful in this context. Further this implies that the routing must be global rather than distributed which is the practical case in a large network.  In theory, the number of paths may be exponential in the network size; but in practice, many constraints are impose which limit the number of paths, and hence the number of super-arms to be considered. 

The experimental section is weak. The main paper says “we defer detailed setup description and more results to the supplementary material” (line 320). But the supplementary material does not provide details, and hence the experiments cannot be replicated.  Given the lack of details, it is not possible, for example, to assess if a gap of 0.04 (Fig 2) is significant. The simulation results are limited and comparisons are only to algorithms defined in this paper, not to competing algorithms. Simulation results are thus limited and provide limited insights.  This is a significant weakness. 

The paper is densely written with sparse discussion of the results. A table of notations would considerably help the reader. The paper contains very little in the way of discussion of the 4 theorems stated in the paper, and the main body of the paper does not even contain an outline of the proofs.  (As noted elsewhere, the paper does not even describe the brand-new techniques that are claimed to be needed.) The supplemental material contains proofs of theorems and attendant lemmas, but is also lacking in any discussion. As a specific example, after the formal statements of the Theorems, slightly looser versions could have been provided in terms of min / max of the weights directly. 

Time-complexity of the offline procedures (Table 1, Supplementary material) is O(E^3 \sqrt{V}) which can be prohibitive for large graphs, even for a single call. It is hard to call this “fast”.  It is not clear how often these algorithms are invoked. 

What is the ‘family of instances’ for which BLUCB and BLUCB-Parallel achieve optimal sample complexity (L 134, L 179); BTW isn’t this ‘order optimal’ vs. ‘optimal’? 

In a typical on-line setting, such as the bottleneck path problem, what does running BLUCB in parallel mean? How many instances are run in parallel? 

Theorem 2 strengthens the results of Theorem 1 by separating base arms into arms that are better / worse than the optimal arm. However, the specific numbers provided for the example of Figure 1 are not convincing \tilde{O} (245 \log(1/\delta)) and \tilde{O} (211 \log(1/\delta)). 

The paper repeatedly assumes the existence of “efficient oracles”, which is troubling (it is stated that such oracles exist for paths, bipartite matchings, and spanning trees; but it does not state how efficient they are). 

What are the brand-new techniques introduced in this paper (line 75)? This should have been included in the summary of contributions. 

Footnote 2: is this element-wise minimization? 

The sub-Gaussian parameter R must be defined. 

Grammar, syntax, and spelling demand careful attention. 

 -- - --- 
====== Comments added after author rebuttal and discussion =====  
MO, the paper is densely written, and would definitely have improved considerably with added discussion. The authors could have used the extra pages for this.

The authors have provided detailed responses to many, but not all, of my comments. For example, the response to my 'gap' comment is weak. I still do not know if a difference of 0.04 is significant enough to claim that the new method works better.

The authors' response partially but not fully eliminates my concerns regarding the experimental section: lack of detail (addressed), and limited experimentation.

Based on the author responses (to my comments as well as those of other reviewers), I have raised my rating from '4' to '6' 
limitations_and_societal_impact: 
 The paper does not discuss limitations / potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors focus on the Combinatorial Pure Exploration problem with bottleneck rewards (CPE-B) and consider two settings: fixed-confidence (FC) and fixed-budget (FB). They argue that the existing CPE algorithms cannot be adapted to solve the challenges arisen in CPE-B.  Then, for the FC setting, the paper proposes two algorithms, called BLUCB and BLUCB-Parallel, that provides optimal (within a logarithmic factor) sample-complexity for several important instances. Moreover, a lower-bound is also deduced that matches the guarantee of BLUCB-Parallel. For the FB setting, the authors provide an algorithm, called BSAR, that achieves the same error probability guarantee as that of the state-of-the-art work. The authors also claim that BLUCB-Parallel and BSAR are efficiently implementable in several important instances such as $s$-$t$ path, maximum cardinality matchings, spanning trees, etc. 
main_review: + Originality: The model is relatively new and well-motivated: although combinatorial pure exploration problem has been studied before, none of the previous works focuses on the case with bottleneck reward functions. Concerning the involved techniques, the main algorithms proposed in this paper are (non-trivial) adaptations of previous known approaches/frameworks (i.e., explore-verify-parallel scheme in the FC setting and accept-reject scheme in the FB setting) into the context of CPE-B. Bottleneck reward function poses novel challenges and to overcome them, the authors provide several efficient oracles (such as Bottlenecksearch, ExistOracle, AR-Oracle) specifically designed for the bottleneck setting. In my opinion, these oracles are novel and they seem to be the contributions that stand out the most in this paper. Unfortunately, these oracles are not shown/discussed very clearly (due to the organization and writing flows of the paper). Most of related work is adequately cited (except for the literature on the guarantees’ lower-bounds in the FC setting).

+ Quality: The main results on the performance guarantees of BLUCB, BLUCB-Parallel and BSAR algorithms seem technically sound: I do not spot any obvious error (note that I did not check through all details in the proofs). Several numerical experiments are conducted but it lacks adequate discussions. The paper also claims that the proposed algorithms are efficiently implementable. However, this claim is not shown clearly, especially on the efficiency of the oracles (see below). The results in the FC setting feel quite complete; on the other hand, the ones in the FB setting is less so: BSAR does not provide significant improvements in comparison to the benchmark CSAR and no lower-bound is available. 

+ Clarity: The texts itself is quite well-written. Overall, the technical discussions are relatively adequate for readers to follow. Nevertheless, the organization of the paper should be revised. Particularly, in my opinion, the oracles designed for Bottleneck reward are the novelties that really differ this work to the literature and should be analyzed with details in the main text (currently in the appendix). To do this, probably the authors should find a way to trim down the main algorithms given that the explore-verify-parallel and accept-reject schemes are previously known. 

As mentioned above, my main concern is the claim on efficiency. Particularly, the proof on the running time of ExistOracle (Appendix C.2.1) is vague and rushed toward conclusions (this is the core result for the proofs on Bottlenecksearch, AR-Oracle and eventually, the running time of the algorithms). How is $s$-$t$ path reduced to 2-vertex connectivity problem? When no super arm in $M_{\geq w(e)}$ contains the base arm $e$, how can one check this efficiently, given that $M_{\geq w(e)}$ might contain exponentially many elements? Maybe I misunderstood something here. 

+ Significance: The paper provides the (first-ever) results for the CPE-B framework. They can be used as the foundation for other analyses on CPE-B and probably can be generalized to cases different from bottleneck rewards.  

+ Other comments and questions:

1/ Page 7: BLUCB-parallel is better than BLUCB when $\delta \le \exp(-H_{E}/(H_{E}-H_{V}))$. Therefore, is it true that before running the algorithm, we cannot compute (efficiently) $\Delta^C_e$ and thus, no way to know if this condition on $\delta$ will hold? Neither can we tune a priori this $\delta$ in BLUCB-parallel?
2/ Page 5: line 4 of Algorithm 2, does this mean that ONLY when $t$ is an even number, we execute Verify_k? Why should we do this and is this a “wasteful” way of using odd iterations $t$?
3/ Line 293: Which CPE-L algorithm of [10] is discussed here? CSAR?
4/ Line 311: This sentence is very confusing. Result of BSAR in Theorem 4 matches with the bound of CSAR presented in Theorem 3 of [10] on the linear case; do the authors imply that even in the bottleneck case, CSAR will have the same guarantee? What is precisely the novelty of BSAR?
5/ Line 313: if $\Delta^B_i$ is the same order with $\Delta_{\textrm{min}}$, $H^B$ is also $\mathcal{O}(n/\Delta_{\textrm{min}})$; given this, how do the authors claim that BSAR’s guarantee is “significantly” better than that of the uniform sampling algorithm?
6/ Page 9: In Figure 2(a), it looks like the sample complexity of BLUCB and BLUCB-Parallel have a better order (in terms of $n$) than that of CLUCB. In Figure 2(b), this difference (in order) is much smaller. Why does this happen (the theoretical guarantees of CLUCB (in [10]) and BLUCB, BLUCB-Parallel have the same order in terms of $n$)? In Figure 2c and 2d, when the gap is large, CSAR can outperform BSAR; do we have a condition for when this will happen (based on the precise bound provide by [10])?
Can the authors also report the elapsed time of these algorithms in the experiments?

+ Some (possible) typos: line 137: denote  -> denotes; line 180” bottlenck -> bottleneck;  line 193: propose algorithm BLUCB-parallel -> propose the BLUCB-parallel algorithm;  Line 285: avoid them disturbing -> avoid disturbing

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper examines a combinatorial exploration problem in which the learner aims to identify the best "slate" of arms, with a "bottleneck" criterion that defines the reward of each slate as the minimum possible reward of its constituent elements. The authors propose a series of tailor-made algorithms that exploit the problem's bottleneck structure to achieve optimal guarantees, both in a fixed-confidence and fixed-budget setting.

One of the reviewers expressed concerns about the writing style of the paper and the strength of the authors' experiments. During the discussion committee phase, these concerns were, to a large extent, alleviated by the authors' replies, so a decision was reached to accept the paper. At the same time, I would urge the authors to implement a version of their exchanges the reviewers and adjust the denser parts of the paper accordingly, as this would significantly strengthen their contribution.
Decision: Accept (Poster)