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: This paper proposes the Probe-Rank algorithm for exact ranking under the Weak Stochastic Transitivity assumption. For true tranking recovery problem, the proposed algorithm guarantees instance-wise upper bound on its sample complexity. This instance-wise upper bound only depends on the preference probabilities between items that are adjacent in the true ranking. This is an improvement upon existing sample complexity results that depends on the preference probabilities for all pairs of items. Experimental results show that the proposed Probe-Rank algorithm outperforms the IIR algorithm, which is state-of-the-art in the area. In addition, a constructive example is made to illustrate the advantage of the instance-wise bound in the worst case.
strengths_and_weaknesses: Strength:
- the writing is punchy with clear contributions and highlights
- the operational details are noted with clarity; giving readers strong confidence to reproduce the numerical results

Weakness:
- given the theoretical nature of the major contribution; the experiment focuses only on the verification of theoretical findings and lacks practical guidance on real-world data practices
questions: In Line 148, what would be the impact if the Partial order-preserving graph is not implemented? 
If the proposed algorithm is implemented without Partial order-preserving graph to guarantee the acyclic/transitive property, would it become a competing method with a different line of research that does not assume coherent ranking, i.e., methods derived from Borda score and Copeland score? 

In some other research, techniques to resolve the conflicts in non-coherent ranking is a practical problem. It is not in the scope of this research I believe but an interesting direction to look at if the proposed method is examined with noisy and non-coherent pairwise comparison data, which unfortunately is the case for many real-world datasets.
limitations: Given the theoretical focus, there is limited evidence of how the algorithm works on real-world data. This is acceptable but still a limitation given the presentation and length of the content.
review_title: null

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: This work designs an active ranking algorithm for WST. Authors also analyze the sample complexity and correctness of the algorithm. They propose conjecture on lower bound which if true implies the near optimality of their algorithm. They also provide numerical experiments contrasting their algorithm against SOTA algorithms under more restrictive settings and show pros and cons. 
strengths_and_weaknesses: Strengths:
The sample complexity analysis is quite unique and clever. They divide the complexity analysis into two parts and bound each part using simple arguments. This makes following the proof quite easy.


Weakness:
Even though motivation for WST is justified well, the authors didn't mention why one needs an ordering stronger than epsilon-ranking. 
Their algorithm has complexity of O(n^2) which is essentially same as that of the trivial epsilon-ranking. Having said that it is important to establish bounds for exact ranking and hence I lean towards accepting the paper.
questions: I think it might be better to present some examples where this algorithm is necessary and epsilon-ranking isn't sufficient.
limitations: Authors have adequately addressed the limitations
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: The paper analyzes the problem to identify the underlying ranking in dueling bandits under the assumption that the underlying preference probabilities fulfill weak stochastic transitivity. 
The authors introduce a novel algorithm that is able to solve the problem in a $\delta$-PAC manner and comes with an instance-wise sample complexity guarantee that depends only on the gaps of those arms, which are adjacent according to the underlying ranking, and not on the other gaps. 
strengths_and_weaknesses: Strengths:
1. The problem of ranking in dueling bandits is relevant for practical purposes and has already been studied in the literature. The algorithmic solution of the authors appears novel and apparently outperforms the current state-of-the-art methods in special cases, both empirically and in theory.
2. The authors prove an interesting upper bound on the sample complexity for Ranking under WST: In contrast to existing ones, theirs depends only on the gaps between adjacent arms (according to the ranking) and not on all gaps. 
3. The paper is well-written, the presentation of the algorithm is easily understandable and well illustrated with an example. The theoretical results appear reasonable. I did not check all the proofs in full detail, but at first sight they seem to be correct.

Weaknesses:
1. In the appendix, the authors present with Probe-Rank-SE an improved variant of their algorithm, which they do not mention in the main paper. In my opinion, the authors should either focus on this variant or at least mention it in the main part.
2. The authors only conjecture (and not prove) a lower bound that would show (log-)optimality of their result. Even though the authors discuss where this conjecture comes from, the final step still needs to be made. And I have my doubts that this final step is possible, as one would have to add up expected sample complexity lower bounds that are valid w.r.t. different instances. However, this might suffice as motivation for the conjecture.

Minor Weaknesses and Typos:
- 29: It should be ''$p_{i,k} \geq \max (p_{i,j},p_{j,k}) > 1/2$''.
- 42: You say you focus on pairwise comparisons, and before you have already said that you focus on WST. As far as I know, WST is only defined for pairwise comparisons. Maybe you could reformulate this.
- 115: and [] usually
- 118: In [the] PAC settings
- 140: the comparison should last
- 2 in Alg.1: $b_{\tau} = \lceil ... \rceil$? Then, adapt (13) apparantly.
- 196: The lower bound of order $\tilde{\Delta}^{-2} \log(n/\delta)$ is not stated in Sec. 2, but only in footnote 1. Maybe, you could also mention it next to (2).
- 210: Theorem 2 does not show tightness of its bound, it does not contain a lower bound result.
- 217: addition[al] factor
- 225: Why $\Delta_{d}$, what does $d$ stand for?
- 318: under[r]
- 466: $\Delta_{i,j}>\epsilon_{\tau}$
- 579: that [] at least
- 3 in Alg.5: SE italic
- 612: (Problem 3 in the main paper) = (Probl. 1 in the appendix)
- 617: Sometimes in this section, WST etc. in the index is italic, sometimes not.

Additional Remark:

In Sec.1 you mention that SST may be too strong in some scenarios and motivate this way the usage of WST. This naturally raises the question how strong the WST assumption itself is. 
Apart from [1], which detected violations of the Condorcet winner assumption (i.e., in particular of the WST assumption) in real-world examples and thus focused on identification of Copeland winners, [2] recently discussed testing whether the WST assumption is fulfilled or not. The authors showed that WST testing requires $\Omega(n^2 \Delta^{-2} \log (1/\delta))$ samples and, interestingly, they proved an instance-wise lower bound for corresponding solutions that depends on $\Omega(n^2)$ of the gaps and in particular not only on adjacent ones as your upper bound.

[1] $:=$ [30] in your main paper

[2] B. Haddenhorst et al., On testing transitivity in online preference learning. Machine Learning, 2021
questions: - Thm. 1 in [3] shows that maxing (and thus in particular ranking) in an $(\epsilon,\delta)$-PAC manner under WST requires in the worst-case $\Omega(n^{2})$ samples.  As their worst-case instance is similar to yours, you could potentially adapt their proof for proofing your conjecture. Did you try this?
- Thm 2: From looking at its proof, it appears that you could slightly strengthen Thm.2 and provide a more detailed bound without O-notation, i.e., you could explicitly provide the constant that is hidden in the O-term. Maybe you could state this constant for the sake of completeness in the appendix?
- Under SST $\Delta_i = \widetilde{\Delta}_i$  holds. You also mentioned RST in Sec. 3, and [3] e.g. discuss moderate stochastic transitivity. Could you say how $\Delta_i$ and $\tilde{\Delta}_i$ can differ under such transitivity assumptions? I.e., would Probe-Rank still be better than IIR in special cases under such assumptions?

[3] M. Falahatgar et al., The Limits of Maxing, Ranking, and Preference Learning, ICML 2018.
limitations: There do not seem to be any potential negative societal impacts of this work. The limitations of their theoretical results have adequately been addressed by the authors.
review_title: null

Meta-review: metareview: This is an interesting and solid paper in which the authors address the identification of a ranking in the setting of duelling bandits under the assumption that the underlying preference probabilities are weakly stochastic transitive. They introduce a novel algorithm which solves the problem in a delta-PAC manner and has an instance-wise sample complexity guarantee. All reviewers agree that this is a significant contribution. Questions and open points could be clarified in the discussion phase. 
confidence: Certain
Decision: Accept