Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes the notion of a "generalised Condorcet winner"  (GCW) among contestants in a tournament (or candidates in an election). Every subset of contestants is associated with a probability distribution over the contestants in the subset; a GCW is the most probable choice in every subset. The authors propose a sampling algorithm for determining a GCW of a tournament with sufficiently high probability, and provide both lower and upper bounds on the sample complexity. They consider special cases based on the number of contestants (m) and the size of the queried subset (k).
main_review: In my opinion, the paper has two major weaknesses.

1. The paper is premised on the assumption that the input tournament will indeed have a GCW--which, as the authors themselves acknowledge, is not guaranteed. It is not clear how the proposed algorithms will fare when run on a tournament that is without a GCW. Moreover, I do not find sufficient motivation for the query model (in which subsets of size k, k being arbitrary, are queried). The experiments provided are on a synthetic data set: they do not bring out the practical relevance of the query model and the algorithms--how they can benefit real-world applications. In short, I am unable to attribute any practical significance to this paper. It must be assessed solely for its theoretical merit.

2. The paper is very hard to read. To be fair to the authors, the contents are technically dense: multiple problems, multiple parameters, and so on. And I do believe that their presentation is CORRECT. However, substantive portions of the paper contain dense notation interspersed with the commentary (starting with Section 3, wherein the problem is introduced), hindering CLARITY. I do not expect readers who are not already familiar with this problem and associated notation to be able to follow the paper.

I have two specific questions for the authors.

- The case of m = k, which amounts to mode estimation, has recently been studied in the following paper, which provides an algorithm, as well as upper and lower bounds that match up to a logarithmic factor.

Sequential Mode Estimation with Oracle Queries. Dhruti Shah, Tuhinangshu Choudhury, Nikhil Karamchandani, and Aditya Gopalan. In Proc. AAAI 2020, pp. 5644—5651. AAAI Press, 2020.

Could the authors please compare/distinguish their own problem and bounds from the one in this paper? Also, to the best of my understanding, the authors have not shown experimental results related to mode estimation, and comparisons with other mode estimation algorithms. Why not?

- Could the authors please explain the qualitative interpretation of the parameter h? I was under the impression while reading the paper that it was similar in spirit to the usual tolerance parameter epsilon in PAC formulations, but the authors seem to indicate in the conclusion that there is room for a "margin" epsilon over and above h.

Post-rebuttal: Based on the authors' response and the discussion among the reviewers, I am now more positive about both the theoretical merit of the paper and its readability. I update my score accordingly.
limitations_and_societal_impact: I do not see any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of identifying the generalized condorcet winner (GCW) of the multi-dueling bandits. In multi-dueling bandits, each time the learner chooses a set with size $k$ to sample, and the sample returns an arm as the winner according to a distribution. The GCW is an arm that has the largest probability to win for any set that contains it. The focus on this problem is to find the sample complexity (aka number of samples needed) bounds for finding the GCW of a set of arms with confidence $1-\gamma$. This problem can be viewed as a generalization of the "top item selection from noisy comparisons" problems or the "best arm identification from dueling bandits" problems. The model considered in this paper is very general and covers the popular  Plackett-Luce model as well as most of the cases that have been studied in the literature. 

Under this general model, the authors developed the sample complexity upper bounds and lower bounds and the bounds are optimal up to at most a log factor. Numerical results also show the improvements of the proposed algorithm. 
main_review: This paper studies a novel and interesting abstraction of the long existing problems of dueling bandits or ranking from comparisons, and this abstraction is general and reasonable enough to cover most of the cases that would be met in the literature and in practice. The algorithm proposed in this work is non-trivial, and its sample complexity upper bound is close enough to the lower bound with only a log factor. 

The results of this work are good enough for an acceptance in my opinion. 

The paper is well written, with good mathematical definitions as well as verbal explanations. 

The results are significant for understanding the theoretical limits for best arm/item identification from multi-wise comparisons or multi-dueling bandits.

Therefore, I tend to give a score 7.
limitations_and_societal_impact: There are two main limitations in this work.

First, the algorithm and the lower bounds only work for worst cases, while in practice, we may expect instance-wise bounds that depend on the actual gaps of differences of the winning probabilities. There are instances where some of the gaps are very small but most of the gaps are very large. For these instances, the bounds in this paper may be much larger than those utilizing the unequal gaps. 

Second, for the PL model, it is interesting to discuss whether and to what degree the value of $k$ can influence the sample complexity if the parameters remain the same.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies the BAI problem in the multi-dueling bandits. 
It proposes algorithms with theoretical guarantee and provides related lower bounds.
There are detailed comparisons to existing works.
Moreover, it compare the proposed algorithm with other existing algorithms numerically.
main_review: In general, the paper is well organized.
It involves rich amount of results and the amount of notations is a bit heavy. It would be easier for the readers to understand if there can be a table to compare all the upper and lower bounds.

However, I have one major concern regarding the single bandit case $m=k$. What is the difference from this case to the standard multi-arm bandits --- the problem where the agent aims to find $1$ best arm among $m$ arms?



=========

Thanks for the detailed response from the author(s). I have read them and all other discussions. Though I tend to remain my score, I am more favor to accept the paper for the time being.
limitations_and_societal_impact: There is one suggestion for future work: if the query size can be different at different time step $t$, does the algorithm still work? Can there be any theoretical guarantee?
review_title: null

Meta-review: The reviewers came to consensus that the theoretical strength overtakes the concerns such as the assumption on the existence of GCW and the heaviness of the technical materials. I agree with these opinions and please sincerely address the concerns raised by the reviewers in the final version such as the relation with the previous work pointed out by NPR2. In particular, though I agree that the dense notation of this paper might be somewhat unavoidable, I expect that the authors make the best effort to improve the readability with more intuitions for them so that the paper becomes a good starting point for multi-dueling setting.
Decision: Accept (Poster)