Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Authors: Tao Jin
Yue Wu
Quanquan Gu
Farzad Farnoud
Venue: ICML 2025 poster (2025)
Keywords: active ranking
stochastic transitivity
rank aggregation
dueling bandits
lower bound
upper bound
Primary area: theory->online_learning_and_bandits

Abstract: We study the problem of efficiently aggregating the preferences of items from multiple information sources (oracles) and infer the ranking under both the weak stochastic transitivity (WST) and the strong stochastic transitivity (SST) conditions. When the underlying preference model satisfies the WST condition, we propose an algorithm named RMO-WST, which has a bi-level design: at the higher level, it actively allocates comparison budgets to all undetermined pairs until the full ranking is recovered; at the lower level, it attempts to compare the pair of items and selects the more accurate oracles simultaneously. We prove that the sample complexity of RMO-WST is $ \tilde O( N\sum_{i=2}^{N}H_{\sigma^{-1}(i),{\sigma^{-1}(i-1)}} )$, where $N$ is the number of items to rank, $H$ is a problem-dependent hardness factor, and $\sigma^{-1}(i)$ represents the $i$-th best item. We also provide a tight lower bound that matches the upper bound of approximate ranking under the WST condition, answering a previously open problem. In addition, when the SST condition is satisfied, we propose an algorithm named RMO-SST, which can achieve an $\tilde{O}(\sum_{i=1}^{N} H_i \log(N))$ sample complexity. This outperforms the best-known sample complexity by a factor of $\log(N)$. The theoretical advantages of our algorithms are verified by empirical experiments in a simulated environment.

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Tao Jin
Yue Wu"
Quanquan Gu 22 Farzad Farnoud
Abstract
1. Introduction
The problem of learning to rank with multiple oracles, some- times known rank aggregation, is ubiquitous in many applications, such as the recommendation system (Oliveira ct al. 2020: Batchanowski and Boryczka (023)) user classi- fication (Minka et al. 20188) Ebtekar and Liu 2021) and drug discovery (Agarwal al. 2010: Ru et al. (021). More re- cently, learning-to-rank has regained attention the context of evaluating large language models (LLM). For example, human feedback is used to rank the performance of LLMs across different tasks. Each task can be seen as oracle, where two LLMs generate responses to a given prompt for that task, and the human annotator indicates which one is more helpful or informative.
We study the problem of efficiently aggregat- ing the preferences of items from multiple in- formation sources (oracles) and infer the rank- ing under both the weak stochastic transitiv- ity (WST) and the strong stochastic transitivity (SST) conditions. When the underlying pref- erence model satisfies the WST condition, we propose an algorithm named Rank-wilh-Muliple: Oracles (RMO-WST)) which has a bi-level design: at the higher level, it actively allocates compar- ison budgets to all undetermined pairs until the full ranking is recovered; the lower level, it attempts to compare the pair of items and selects the more accurate oracles simultaneously. We prove that the sample complexity of RMO-WST is Ö(N EN H. *()).o 1(--1)). where N is the number of items to rank, Hig a problem- dependent hardness factor for correctly compar- ing item and item j. and (i) represents the i- th best item. We also provide tight lower bound that matches the upper bound of approximate ranking under the WST condition, answering a previously open problem. Additionally, when the SST condition is satisfied, we propose an algo- rithm named IMO-SST, which can achieve sam- ple complexity of Ô(Σ i=1 H, log()))) where H, Maxje Hi,. This outperforms the best-known sample complexity by a factor of log(N)) The theoretical advantages of our algo- rithms are verified by empirical experiments in a simulated environment.
In many applications, the oracles that provide preference feedback are usually human annotators, who may provide inherently noisy feedback. Moreover, oracles may show varying accuracy for different pairs of responses. For ex- ample, the performance gap between two LLMs may be negligible one task but quite obvious in another. One nat- ural question is then how to identify the underlying ranking of different LLMs efficiently, especially by taking advantage of those more accurate oracles (i.e., tasks). For example, when creating an LLM leaderboard, we have two different criteria or "tasks": honesty and helpfulness. When ranking two LLMs, we may ask a human annotator to rate which LLM more honest and which LLM is more helpful. The two tasks/criteria may exhibit different preference behav- iors.
N
Our goal is to accurately determine the ranking with as few queries as possible. To ensure the problem well defindd and an underlying ranking exists, it is commonly postu- lated (Falahatgar et al. 2017: Ren al.. 2018 Saha and Gopalan 2019) that ranking exists and it is harder to dif- ferentiate between items that rank in adjacent compared to those that rank apart. Formally speaking, if i > j > k, then Pt, 2 max Py > 1. where Pt.j denotes the winning probability of over j. This principle known as Strong Stochastic Transitivity (SST). Notably, Saad et al. (202)) solves the multi-oracle learning-to-rant tasks under special case of the SST condition. In particular, they as- sume numerical feedback with sub-Gaussian noise, which satisfies the SST condition. Saad et al. (2023) established
'Equal contribution' Co-corresponding Authors 'Department of Computer Science, University of Virginia 'Department of Com- puter Science, University of California, Los Angeles. Correspon- dence to: Quanquan Gu <qgu @es, uula. Farzad Farnoud <farzad zfarzad@virgiia..oo virginia.eduz.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
tight results for comparing two items, and directly swapped it with the deterministic comparison in classic binary in- sertion sort algorithm to establish an upper bound for the noisy ranking problem.
(inne.))eNNxx( l 1/2 is the gap of the comparison probability from 1/2. Our lower bound answers this open question raised by Lou et al. (2022) and shows that our algorithm can attain the lower bound in terms of the number of candidates N.
Nevertheless, the application of SST can be overly restric- tive in contexts where preference probabilities do not hinge on single numerical attribute. Items can possess multi- faceted attributes, leading people to evaluate different pairs based on different attributes. For example, LLM A is fa- vored over LLM B because A produces longer responses, although both are equally informative. LLM B preferred over LLM C' because B's response is short and informa- tive, while C's response is long and less informative. While human annotators can identify A > B and B > C easily, they may find it difficult to compare A and C for the long responses from both LLMs.
3.
We also propose an algorithm for learning to rank with multiple preference oracles in the presence of SST condition, namely RMO-SST. It can achieve a sam- ple complexity of 0 H; log(N)), where H; = max Hi.-- Compared with the existing result Saad et al. (023), ) our algorithm enjoys an improved sample complexity by factor of log N and matches the lower bound of the sample complexity.
2. Related work
This phenomenon is pervasive in human behaviors and is defined as Weak Stochastic Transitivityy (WS7) (Feige al. 1994 Mohajer et al. 2017 Falahatgar et al.) 2018 Lou et al. 2022). It only assumes that if item i > J, then Pt,j > 2' Therefore, a pair that is closely ranked might not always be more challenging to compare than one with a wider disparity. Driven by these real-world scenarios, this paper mainly focuses on the challenge of identifying the complete ranking of N items in broader context, where only WST is applicable and SST is not requirement. Our primary goal is to minimize the number of comparisons while ensuring high level of confidence.
Rank aggregation with preference data. Rank aggrega- tion generally refers to the combination of multiple stochas- tic pairwise or listwise comparison results into a ranking that is considered a consensus (Negahban et al.) 2012] [Thonet et al.] 2022). Each aggregation method usually assumes underlying model. Maystre and Grossglauser (2015) discovers the connection between the maximum likelihood estimate of the Plackett-Luce model with the stationary distribution of a Markov chain, vastly accelerating the infer- ence time given the pairwise preference data. For general estimation that also contains listwise comparisons, maxi- mum likelihood is common practice (Vojnovic and Yun 2016). For Mallow's model, a recent work proposed using partition scheme for a ranked item to discover the ranker quality and produce a ranking simultancously (Zhu et al. 2023
In this paper, we study the problem of learning-to-rank with multiple oracles, where a set of oracles provides noisy pair- wise comparisons for the items. We propose an algorithm that queries comparisons for pairs of items from an adap- tively chosen user set. We summarize our contributions as follows:
Heterogeneous ranking and multi-task ranking. With the rise of crowdsourcing, data scientists are motivated to design algorithms adapted to this scenario to account for the variable quality of workers to achieve cost-efficient data acquisition rather than assigning tasks uniformly to workers regardless of their performance (Niu et al. 2015). When data is already given and the algorithm is unable to affect the collection process, due to the varying precision of the workers, model that considers or estimates the quality of the source while ranking shows significant benefit over those that do not (Takanobu et al., 2019] Jin et al.) 2020). In practical cases, the data collection has not happened yet: then an adaptive algorithm can be chosen to optimize query collection. Existing methods usually maintain two sets of estimates: one for ranking and one for worker quality (Wul et al. 2022 Saad al. 2023). Low-accuracy workers are usually gradually eliminated, leaving high-quality responses to be collected more efficiently. A low-rank assumption can be made when the similarity between two parties within a subset of tasks can also be extrapolated to a broader set of tasks. Methods derived from probability matrix factorization
1. We study dearning-to-rane with multiple preference or- acles. We assume all oracles obey the same underlying ranking but demonstrate various accuracy and there is no "best' oracle for all pairs of comparisons. We pro- pose an algorithm named Sounk--wthh-uuliipe--rraaad (RMO-WST) that can efficiently rank N candidates given that each oracle satisfies the weak stochastic transitivity (WST) condition. The achieved sample complexity up- per bound is Ö(N Σ ( where N is the number of items to rank, Hi,, is a problem-dependent hardness factor for correctly comparing item and item j. and o -i)) represents the i-th best item.
2. We provide a lower bound on the query complexity of solving multi-oracle ranking under the WST condition. In particular, Lou et al. (2022) studied the single-oracle ranking under the WST condition and conjectured that the lower bound of order ((22/??) where A :=
2

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Table I: A comparison among the related works and the proposed method. The table is divided into two major sections. The upper section mainly shows the sample complexities of three related algorithms under the SST condition. The lower section of the table shows the result under the WST condition.
Algorithm
Sample Complexity
Multi-Oracle
1IR
E E A (1og (oggloogA7)00 log log()))))
No
(Ren et al.
2019
Binary ry S Search
δ E EIENN Hi (log (H.) + (NV) + 1og (1/60))))
Yes
(Saad et al. 2023
RMO SST
δ EVEIN) H. log H.) H (H.)oo((H.))oog(NN//))
Yes
(this work, Algorithm
Probe-Ma Max
δ N NEW A-2 100, 2(i-1)
No
(oou et al. 2022
RMO-W31
N Ei= (1)000))0 (i-1) Ö
Yes
(this work, Algorithm|
Lower Bound for WST (this work, Theorem 5.8
0(N² min; H 110.0 11-1))
Yes
are usually adopted in this case (Wang et al., 2016 Jun et al. 2019).
feedback is a single value tied the pulled arm (Yue et al. 2012). As in the common case in bandits, not only must the rankings be inferred correctly, but also the optimization of regret (reward) must be taken into account. Contextual dueling bandits usually imply strong stochastic transitivity if the reward is defined on the actual utility gained from arm pulls (Dudík et al.) 2015). Methods developed for these settings are ideal for online user interaction systems, where the collection of the reward is on-the-fly and cannot be postponed until the whole ranking is derived. Stochastic transitivity assumptions rarely hold in real-world situations, since the "rock seock-scisoorpppee"" relationship happens quite often in tournaments and preferences in real life. To cover these conditions, methods targeted for rewards defined on Copeland score Σ 1(pi.j > 2)) or the Borda score N Σ EEINN Pt.j are widely studied in the dueling bandits lit- erature (Wu and Liu 2016 Zoghi et al. 2015 Saha et al.) 202T).
Active ranking. Online ranking from noisy comparisons requires a careful algorithm design to ensure that the es- timations of the relative order of the two items are cor- rect ensure accuracy and make few comparisons as possible. With the objective of ranking items according to their Borda score, the Active Ranking (AR) algorithm (Heckel et al. 2019) divides items into partitions accord- ing to the estimated score of uniformly sampling an op- ponent item. This sampling method matches directly that of the definition of Borda score. Partitions group items into the same set if their confidence interval overlaps. After- wards, items in disjoint sets are considered correctly ordered with high confidence. With slightly stronger imposed as- sumption of stochastic transitivity. Ren et al. (019) pro- pose the Iterat vie Insert Mon-Rankinn in (IIR) al- gorithm that uses preference interval trees to perform binary search to sequentially insert items into an already ranked list. It achieves a provable optimal upper bound when the instance satisfies the SST condition. However, if only WST is assumed, the algorithm may fail to terminate in extreme cases.
We summarize our contributions and compare them with the related work in Table Due to the lengthy form of the exact result of Binary-Search and RMO-SST that does not fit in one line. We use Ô in the table to omit insignificant terms. In addition, we keep relevant log terms inside the Ô showcase the improvement obtained by the proposed method.
In light of this, the Probe- Brobe-Rank algorithm (Lou et al. 2022) solves this problem by sampling uniformly over the unranked pairs until the order of pair is revealed. Af- terwards, this order information is added as an edge of a directed acyclic graph. Then a transitive closure is com- puted to take advantage of stochastic transitivity when the order of unranked pairs can be inferred so that there can be some savings in sample complexity.
3. Preliminaries
In this paper, we consider actively ranking N items, with M oracles (also known as users or experts). We assume there exists an ordering "x" over these items which is character- ized as a mapping (-)) [N] + [N] indicating the position of a given item in the ranking in descending order. Equiva- lently, the inverse mapping o -1-) lists the items in order: -=((1) > o (2) > o (n.) For two items and
Dueling bandits. In the context of dueling bandits, the agent can only request pair to be compared and get prefer- ential feedback as opposed to stochastic bandits where the
3

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
j. we assume that the result of the comparison is sampled independently from the Bernoulli distribution with mean Pi.. More specifically, we denote Pi,, as the probability that the response is "i is preferred over when a query is sent to oracle u. In particular, PN, >> 1 is considered as the item 2
probability 1/2, the harder it is to estimate the prefer- ence of the two items since the collected responses more noisy. In our multi-oracle setting, a trivial method would be querying one oracle at time in a uniformly random fash- ion and aggregating them as if from a single oracle, which leads to an average gap of Σ., == Σu=1 / M. In other words, any single-oracle algorithm can be trivially applied to the multi- setting as if one oracle has a gap of A.,.
i is preferred over the item j by the oracle u. We will omit u in př, if the discussion is restricted to a single oracle.
For a fixed pair of items i and j. each oracle exhibits its preference, represented by the probability p.... It is yet to decide how to aggregate them into a "consensus preference'. If the consensus is defined as an average over P,, or a majority vote over s - 1/2), it is required that all oracles must be queried for each pair. In this case, there is no point to identify a more accurate expert to save queries. Instead, we make the following assumption that all oracles show a consistent preference for any item pair.
Ranking under WST condition Given that the hardness of inferring the rank of a pair is inversely proportional to the (squared) gap, we introduce the average hardness for a given pair (i as Hi, = 1/(A.,)) Another definition that we will use frequently is Ha, == M/ (A which is the hardness of a given pair (i. It is straightforward to prove that Hi, S His by the Cauchy-Schwarr inequality, so any algorithm that can achieve a sample complexity re- lated to H instead of Hy, is strict improvement over the trivially adapted single-oracle algorithm.
Assumption 3.1 (Consistency)). For any item pair (), the preferences of all oracles are the same. More formally, for any two oracles u and v, we always have:
Ranking under SST condition For ranking under the SST condition, the hardness depends on each item's most difficult pair. Here, for each item i, we define the minimum gap A minje(M]. As. and maximum hardness H; := max He.--
sign(p 1/2) = sign 1/2).
This assumption states that the oracles can show different levels of noise but must agree with the same underlying true ranking. This assumption also enables us to only se- lect the more accurate oracles to recover the ranking with fewer comparisons. An equivalent assumption named the 'monotonicity" assumption made by /Saad et al. (2023).
Finally, we define a 8-correct ranking algorithm as an algo- rithm that returns the true ranking with probability 1 8 within finite number of queries.
Additional notations Let a V b = max(a, b). We use standard asymptotic notations, including O(-), (()) O(), and (()) ((-) will hide logarithmic factors. For a positive integer N, [N] == {1,2,..., NN). For a set of items S, denote the set of all possible pairs of items as S² == ((i,) i.j E S,i j}.
O(),
We study the ranking problem under two different assump- tions: Weak Stochastic Transitivity (WST) and Strong Stochastic Transitivity (SST) (Falahatgar et al. 2017):
Assumption 3.2 (Weak Stochastic Transitivity). For given oracle u. for any item pairs (1, and (j. k),, if p 2 2 and PjA 2 2 then x² 2
4. Main algorithms
WST implies that if i > and j > k, then i > k. which eliminates the possible cyclic order dependency and guaran- tees that an exact order of items can be inferred.
In this section, we propose algorithms called Rank-with- Multiple-Oracles (RMO) under both WST and SST condi- tions.
Assumption 3.3 (Strong Stochastic Transitivity). For each oracle u and for any pair of items (i,j) and (j, kt), if pÑ, 2 and k 2 2- then p 2 max max(p"; Pp. 2 2-2
4.1. Proposed algorithm under WST condition
The ranking algorithm under the WST condition is called RMO-WST, which displayed in Algorithm and has a bi-level design. At the high level, it calls P Probe-Ma x (AI- gorithm to select the maximal item from the pool of candi- dates repeatedly. After N - 1 rounds of finding the maximal item, the algorithm finds the ranking of all the items. At the low level, the Compare re algorithm (Algorithm 3 perform comparisons that are necessary to rank a pair of items i and j. which also accounts for the heterogeneous quality of oracles that provide preferential feedback. Try-Compa re (Algorithm 4 is where the actual comparison takes place and the order of pairs of items is determined.
SST implies that items that are more distant in the ranking are easier to compare. Combining the consistency assump- tion and either of the stochastic transitivity assumptions, we conclude that there must exist a ground-trutt ranking a on which all oracles agree. We use (1) to denote the rank of item and -1 (A)) to denote the index of the k-th best item.
Ranking two items The hardness of estimating the prefer- ence of two items and j under oracle u can be captured by the gap between their preferential probability and 1/2: A = IP", - 1/2]. Intuitively, the closer the preferential
4

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
In detail, RMO-WST (Algorithm
variant of Probe-Sord in Lou et al. (2022) takes set of items labeled by ing of them.
binary indicator for a pair of items rather than bounded scalar value for single item as described in Saad al. (2023). After comparison, a Bernoulli parameter estimate is calculated for each individual oracle as Pi, and a joint
... 1.2, NN input and outputs 8-correct rank-
The set St contains the items to be ranked, each of which corresponds node in the directed graph T. It is also called "partial order preserving graph" in prior work (Lou et al. 2022). The graph starts with empty, where each node represents an item (Line 3p. A directed edge is created between the two items, originating from the winning item, once the pair's order is determined. The maximal items are nodes of the current graph T such that there is no incoming edge towards them, which means they have not yet lose to any other items in comparison.
=(()) estimate as Pi. (Line 7 In L the order of the pair is called when the confidence threshold is reached. If not, it continues to the elimination phase (Line [T), where oracles with accuracy lower than the medium of the group in the common statistical sense according to the estimate are removed from the active set S and S.
Algorithm 1 RMC-WST (N,6): Rank-with-Multippe Oracles
1: input: number of items to rank N. confidence level 5 2: initialize: Si = [N], ans = [o]% a directed graph T
The WST assumption can also be employed to introduce additional edges during this process by getting the transitive closure of the graph. Furthermore, Ti. records factor that determines the number of comparisons required confi- dently determine the direction of pair (i, It is initialized at and its value will increase by one each time to deter- mine the number of comparisons required throughout the algorithm. Inside each loop, the maximal item is found by Probe-Ma with confidence level of 25/N² and then removed from the graph T. This process repeats and finds the top items in the set of unranked items S, sequentially.
with N nodes and no edges, for (i. E St set Ta. = 1
3: define: {T. {T.
4: for 1, 1 to N do
5: mmax: T, +- Probe Probe-Max(Ss,) 255,-,.
6: remove xmax from T
7: ans(1 - 1] = imax
8: S = S \ {mmax)
9: end for
10: ans(N 1] = Sx return ons
Algorithm 2 2 Prrobe-Max(S5 (S, T,)
Next, in Pr PMa. let U be the set that contains all the possible maximal items (i.e., all maximal items). Each item in U is paired with items whose order between them is not yet revealed (Line new pair using the Compare method, the losing item is removed from the set of possible maximal items U, and the graph I's is also updated to include this directional edge and any other possible edges according to transitivity by running a standard method to compute the transitive closure of the graph (Line 9.. The sub-routine Compare (Algorithm 3 modified from [aadd et al. (2023) is designed to account for the multiple-oracles situation. The high-level idea is to enumerate different possible parameters: the subset size s, and the gap width h,. In Line 3 Line the guessed subset size 8, and the gap width ht will be sent to Cry-Compare re (Algorithm(H) 4. until both reach the actual quantities. Then Try- Compare will return the correct comparison result with high probability (Line 8)
1: input: set of unranked items S, confidence level 6,
partial order preserving graph T,, exponential factors
2 Line 6). After revealing the order of
Tra.she.))e as T.
2: Let U be the set of possible maximal items in T.
while |U| > do
P ((,)))(( ( EUVjEE
(4,)).) $
T}
5:
for (i,j) in arg min (x,))) Ta.y do
ans Compare ,मं T(s), Tuj = Ti.j +
68
7:
if ans * unsure then w. | = ans, T = TransClosure(TT U (w > 1))
8:
9:
if [U] > 1 and 1 E U then U = U (i({)) (1
10: end if
11: end for
12: end while
13: return U(0),T, T,
Try-Compare (Algorithm is where the actual query and estimation for the pair direction takes place. In Line a query size of m is determined by the subset size 8 given from the argument. Note that this value halves each time since is doubled each time this subroutine is called on the same pair.
Then, a total number of nom comparisons is evenly as- signed to the set of oracles that has not been eliminated yet (Line 6. Note that in our setting, the feedback is
5

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Algorithm 3 (..)
5. Main theoretical results
1: input: pair (i, confidence level 6, precision factor T
In this section, we present the upper bound on the sample complexity of the proposed algorithms, as well as new lower bound.
2: initialize: Tmax = 1, E, = 2_ ans = unsure.
3: while ans unsure and et M22 "mox do
4: for 0.... mmaxx do
5.1. Upper bound of sample complexity under WST condition
5: 8, 2rmar h4 2-
2" M
6:
0raa 810 (Tmm)))mm)))))))))))))mm)))))( log(M))
To start with, we introduce the following theorem, which guarantees the performance of Compare (Algorithm B
7:
ans = Try re (1, maxx 8r, ht))
8:
anss + unsure, break.
9: end for
Theorem 5.1. (Restatement of Theorem 4.1 from Saad et al. (023 For any given T, 6 and any pair (i,3) with probu- bility at least 1 - 6, Algorithm 3
Tmax Tmax + 1
11: end while
satisfies:
12:
return ans
It outputs the correct order or unsure any given T and >
Algorithm Try-Compar S,
1: input: pair to query (i, confidence level 6, subset
size s, estimated gap width h.
2. IsT > - log(M/HL.) the correct order is returned.
2: m = =2[1og,(261og)) (og()/))))))) M6)M)))) no = 64/h².
3. When the correct order is returned, the sample com- plexity is (llog(1/8)H.
3: Sample a set of m oracles with replacement from all M
oracles as S1.
4: Let 517 54¹ S and L [Mos))
To obtain the above theorem, we replace the in the original theorem with 2 suit our application. A detailed reason- ing is available in Appendix [B.T] This theorem guarantees the pairwise comparisons are correct with desired accuracy.
5: for l 0, 0.................... , do
6: Request to = nom//s comparisons for pair (i,j) S U S. Denote cy as the
from each oracle
number of times i > j.
(u.e)
che (u,0)
- (n.e) (2) Pi.
With a robust routine to return the correct order for each queried pair, carefully designed ranking algorithm (Algo- rithm I orchestrates such pairwise comparisons to recover the ranking with high probability. In RMO-WST, the max- imal item in the candidate set is identified and removed iteratively to rank all items. Thus, the total sample complex- ity is the summation of the sample complexity to identify each maximal item. And such cost can be upper bounded by N times the hardness to compare it with the item imme- diately smaller than it. We present the following theorem characterize the total sample complexity upper bound of Al- g The detailed proof is deferred to Appendix [B.2 Theorem 5.2. (Instanceddepndeer sample complexity up- per bound for RMO-WST For a given set of items [N] and desired confidence level 5, Algorithm Aterminates with sam- ple complexity bounded by
7: Pij
to Bia
1871 E Euespi Pijj
(1,0)
8:
if Pij 1/2 2 (2gog(2// (2/0) n then return j
(1)
9: if Pij - 1/2 --v2 2og 2/0) / nom then return < j
(). E S41 + (v s (v.0) medium of PL
10:
5/
11: $4 (u e pp medium of plu? uu E
S/O
12: end for
13: return unsure.
4.2. Proposed algorithm under SST condition
We propose another algorithm that works under the SST condition called RMO-SST, which is derived from the Iterat wewee-nnseriion--ee
O(NEN (No ((61))
(IIR) routine by Ren et al. 2019). It also has bi-level design like the algo- rithm discussed in the previous subsection. The low-level component is Compare (Algorithm 3). The detailed algo- rithm description is deferred to Appendix D due to space limit.
With probability at least 8, Algorithm Twill output a ranking that exactly matches the true ranking.
Remark 5.3. A baseline algorithm is to uniformly randomly choose one oracle and apply the Probe-Rars algorithm with the average oracle. This leads to an averaged oracle with average gap Ái,j or average hardness His as described near the end of Section 3 The resulting sample complexity is Ö(N ΣM² (0)- than our sample complexity, since HI, & Hag.
which is strictly worse
6

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
5.2. Upper bound of sample complexity under SST condition
Solving the instance class above can be reduced to solving the one-sided instance class described below in Problem 2 The reduction is done by query (i,j) and (j,i) on ZWST equally likely to simulate the same environment as in IWST- Therefore, IWST is at least as hard as IWST, up to constants. Problem (IWST)). Consider N items with an underlying ordering a. For all i,j.
We state the sample complexities resulting from running the RMO-SST as follows:
Theorem 5.4. (Instance-dependent sample complexity upper bound for RMO-SST) For given set of items [N] and desired confidence level 6, Algorithm 7 in Ap- pendix D terminates with sample complexity bounded by (i log(H;) + log(N/6)))
2e, ifa and o(j) 2,
0
p² (1.
otherwise.
2
A sketch of proof of the theorem is deferred to Ap- pendix B33
For any (2e, 8)-coreect ranking algorithm that outputs 2e- correct ranking under ZWST with probability at least 1 - 5, we have that the algorithm must correctly rank between the largest item o (1) and the second- -lrgesst one o (2). Intuitively, this implies that the algorithm has to go over almost all pairs to correctly identify o =1) and (2), which is signified by biased coin among N2 fair coins. We have the following result:
Remark 5.5. Theorem 5.1 in Saad et al. (2023) presented an algorithm with upper bound of Ö(Eiemy) (log H.. + Iog)(N) + log(1/5)) which suffers an extra log N factor compared with ours. The two log N factors come from assigning failure probability of 6/N insert one item into the sorting tree and adding the number of queries over log N comparisons. This gives approximately H,log(N (/)) x log N total comparisons. The last log N is removable by applying a more sophisticated insertion procedure we presented here. Also, Ren et al. (2019, Theorem 2) suggests that the lower bound is of order ? EiGIN] H1 (log log( (lg(HH)))o((N/)))) which tightly matches our result.
Theorem 5.6. For any (e, -)-orretttt algorithm A, there exist a ranking a and corresponding p(i, such that with probability at least 5, Σi, = S2 [ log(1/8)
where
Ci. denotes the queries made at (i.
The lower bound is tight up to logarithmic factors because a simple algorithm that allocates comparisons evenly to each pair will guarantee an e-approximate estimation of p(i. j), thus ensuring the ranking is (c, 5) -correct.
5.3. Lower bound of sample complexity
Since the lower bound for the SST case is well-established, this section will focus on the lower bound for the WST case. This remains an open problem to the best of our knowledge.
Further, we define the (c, d) coorreecssss for multiple oracles:
Definition 5.7. An algorithm A is called (c, --coreec,, if with probability at least 1 8, will output a ranking ² such that for all i >a but j > Eu (Ar,) <e?
To solve the single-oracle ranking problem. Lou al. (022) proposed class of hard instances for any (e, 5) -oorrett algorithm. The definition of (c, (c, -oooreretsss is that, with probability at least 1 - 5, the algorithm will output a ranking ā such that for all i >a j. j) 2 e. Intuitively, this means the algorithm will only mis-rank those pairs satisfying p(i.j) - 1/2] <.
Ad
Intuitively, the equivalent probability margin V EE (A must be small for any mis-ranked pair (i
We have the following result:
Theorem 5.8. For any (e, o)corrett algorithm A, there exist ranking a and corresponding (p"(i.))vE(M such that with probability at least 5,
Lou et al. 2022) conjectured that any (e, ()corrct algo- rithm must query at least ?(N log(1/))) ()) but did not formally prove it. We will first present a proof that fills this gap, and then extend the results into the multi-oracle setting.
EnsC. = SONN2 M (og))//)/e²) = ( (1)0000000111))))
Single Oracle Similar to Lou et al. (2022). we construct class of hard instances for the single-oracle setting. Each instance is indexed by ranking o.
where Ct,5 denotes the queries made at (1.
Again, the lower bound is tight and can be reached by allo- cating the comparison budget evenly to each pair and call Algorithm 3
Problem 1 (IWST). Consider N items with an underlying ordering a. For all >a J.
cc, ifo(i) = 1 and o(j) 2,
6. Experiments
(i.g)
2
otherwise,
2:
We study the practical performance of the proposed algo- rithm and compare with existing methods. We compare
and for to j. p(i.j) 1 i))
7

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
10
10%
10%
Sample complexity
Sample complexity
Sample complexity
10
10
10"
10a
10
10
10a
Probe-Mo Max RWO-WST
109
Probe Max RWO-WST
10%
Prebe-Mas Max
RWO-WST
10
10
10
20
40
60
20
40
60
0
20
40
60
N
N
N
.MM+
b MM
.M
6
Figure I: Sample complexities of ranking N E {2,4, 16, 16, 32, 64) items with M - oracles have low accuracy and one oracle has high accuracy.
two methods in the experiment !
We tested N E {2, 4, 4, 32, 64} to explore how the sam- ples grow with the size of the problem. The mix of accurate responses can also affect the performance gain. The average sample complexity of 32 runs with one standard deviation error bar calculated by Python numpy library is plotted in Figure Ia Figure Ib and Figure Ic for the case where M = 2, M = 4 and M = 6, respectively. In general, it is harder to derive estimated rankings while the majority of the information is noisy (M = 6), as in this case the sample complexity much higher for both algorithms. However, regardless of the noisiness of oracles, the proposed method always beats the baseline. In addition, if the proportion of the noisy oracles are high, then our proposed method bene- fits more which is illustrated by the wider gap compared to the baseline method from M = 2 to M = 6.
Probe-Max: the main algorithm proposed (Lou et al. 2022), however, their algorithm does not account for multi- ple oracles. In this case, as a naive implementation, when- ever a pair is requested, it chooses an oracle from [M] uniformly at random.
RMC-WST: Algorithm 1 proposed in this work. However, we notice that due to multiple uses of the union bound, excessive sampling can occur, which is unrealistic in real- world scenarios.
For instance, repetitive sampling of m tasks as seen in Al- 2 can enhance the precision of the overall (a.6) However, since s diminishes at an exponen- tial rate, the quantities m and & also increase exponentially, Our hypothesis is that setting S [M] in other words, maintaining constant size of m at M-can lead to greater efficiency. Additionally, the distribution of the accuracy of active candidates is the same with or without the sampling without replacement in Line 6 Furthermore, note that the confidence interval used from Line X to Line still holds af- ter the change. We also notice that, in Line 7 the individual estimate and the global estimate depend only on the samples collected within single iteration of the for loop starting Line 4 This can also be improved by reusing the statis- ties collected in previous rounds. We present the improved algorithm in Algorithm 5 in supplementary material.
gorithm F at Line
estimate P.j
7. Conclusion and future work
In this work, we introduce an active ranking algorithm that works in the WST setting when there are multiple experts with different degrees of precision in multiple tasks. An instence-indepeedeet upper bound is proven for this case. We also solved an open problem for the lower bound in this setting. In addition, we extend a state-of-the- active rank- ing algorithm under SST conditions into the multi-oracle setting. Whether there is an instance-dependent lower bound remains an open question.
We also conjecture that for the single oracle WST algorithm, its search efficiency could be improved with a better worse case sample complexity by redesigning the graph construc- tion method. After which this can be extended into the multi-oracle case. It is also of great interest to design an algorithm that works for both WST and SST conditions to achieve hest-of-both-wood
To start with, we randomly generate the comparison matrix according to the following rules: a) There are N items to rank and random permutation of [N] is generated as the ground truth ranking. There are M oracles that can conduct pairwise evaluation each with a comparison matrix for Pt.j- b) One of the M oracles is very accurate and we assign a probability value for Pij sampled from [0.85, 0.95] uniformly at random if i > for every pair of items. e) For the rest of M oracles, we assign a value to Pt, sampled uniformly at random from [0.55, 0.65] if j.
result.
Limitations The monotonic assumption might not hold in general. The empirical experiments are performed assuming only one such user is more accurate. If the set of experts have uniform accuracy level, our method may have addi- tional overhead.
Upon acceptance of the paper, the code will be posted GitHub.
8

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Impact Statement
JUN, K.-S., WILLETT, R., WRIGHT, S. and NOWAK, R. (2019). Bilinear bandits with low-rank structure. In International Conference on Machine Learning. PMLR.
This work can potentially increase the efficiency of data collection. With the constantly rising cost of data acquisition and model training, savings on data make sense not only financially but also environmentally, and thus this reduction can thereby raise its own societal value.
LOU, H., JIN, T., WU, Y., XU, P., GC, Q. and FARNOUD, F. (2022). Active ranking without strong stochastic transi- tivity. Advances in neural information processing systems
Acknowledgments
MAYSTRE, L. and GROSSGL M. (2015). Fast and accurate inference of plackett- luce models. Advances in neural information processing systems 28.
We thank the anonymous reviewers and area chair for their helpful comments. YW and QG are supported part by the NSF grant CIF-1911 168. TJ and FF are supported in part by the NSF grant contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
The views and conclusions
MINKA, T. P., CLEVEN, R. and ZAYKOV, Y. (2018). Trueskill 2: An improved bayesian skill rating system.
MOIIAJRR, S., SUII, C. and ELMAIIY,, A. (2017), Active learning for top-k rank aggregation from noisy compar- isons. In International Conference on Machine Learning. PMLR.
References
AGARWAL, S., DUGAR, D. and SENGUPTA, S. (2010). Ranking chemical structures for drug discovery: A new machine learning approach. Journal of chemical informa- tion and modeling.
NEGAHBAN, S., OH, S. and SHAH, D. (2012). Iterative ranking from pair- wise comparisons. Advances in neural information processing systems 25.
BALCHANOWSKKI M. and BORYCZKA, U. (2023). A com- parative study of rank aggregation methods in recommen- dation systems. Entropy 25.
NIU, S., LAN, Y., GUO, J., CHENG, X., YU, L. and LONG, G. (2015). Listwise approach for rank aggregation in crowdsoureing. In Proceedings of the Eighth ACM Inter- national Conference on Web Search and Data Mining.
DUDíK, M., HOFMANN, K., SCHAPIRE, R. E., SLIVKINS, A. and ZOGIII, M. (2015). Contextual dueling bandits. In Conference on Learning Theory. PMLR.
OLIVEIRA, E., DINIZ, V., LACERDA, A., MER- SCHMANM, L. and PAPPA, G. (2020). Is rank aggrega- tion effective in recommender systems? an experimental analysis. ACM Transactions Intelligent Systems and Technology (TIST) 11 1-26.
EBTEKAR, A. and LIU, P. (2021). Elo-mmr: A rating sys- tem for massive multiplayer competitions. Proceedings of the Web Conference 2021.
FALAHATGAR, M., HAO, Y., ORLITSKY, A., PICHAP- ATI, V. and AAVINDRAKUMAN V. (2017). Maxing and ranking with few assumptions. Advances in Neural Infor- mation Processing Systems 30.
REN, W., LIU, J. and SHROFF, N. B. (2018). Pac ranking from pairwise and listwise queries: Lower bounds and upper bounds. arXiv preprint arXiv:1806.02990
FALAHATGAR, JAIN, A., ORLITSKY, A., PICHAPATI, V. and RAVINDRAKUMAR V. (2018). The limits of max- ing, ranking, and preference learning. In International conference on machine learning. PMLR.
REN, W., LIU, K. and SHROFF, N. (2019). On sample complexity upper and lower bounds for exact ranking from noisy comparisons. Advances in Neural Information Processing Systems 32.
FEIGE, U.. RAGHAVAN, P., PELEG, D. and UPFAL, E. (1994). Computing with noisy information. SIAM Journal on Computing 23 1001-1018.
RU, X., YE, X., SAKURAI, T. and Zou, Q. (2021). Appli- cation of learning to rank in bioinformatics tasks. Brief- ings in bioinformatics.
HECKEL, R., SHAH, N. B., RAMCHANDRAN, K. and WAINWRIGHT, M. J. (2019). Active ranking from pair- wise comparisons and when parametric assumptions do not help. The Annals of Statisties 47 3099-3126.
SAAD, E. M., VERZELEN, N. and CARPENTIER, A. (2023). Active ranking of experts based on their per- formances many tasks.
JIN, T., XU, P., GU, Q. and FARNOUD, F. (2020). Rank aggregation via heterogeneous thurstone preference mod- cls. In Proceedings of the AAAI Conference on Artificial Intelligence.
SAHA, A. and GOPALAN, A. (2019). Active ranking with subset-wise preferences. In The 22nd International Con- ference on Artificial Intelligence and Statistics. PMLR.
9

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
SAHA, A., KOREN, Т. and MANSOUR, (2021). Adver- sarial dueling bandits. In International Conference Machine Learning. PMLR.
TAKANOBU, R., ZHUANG, T., HUANG, M., FENG, J., TANG, H. and ZHENGG, B. (2019). Aggregating e- commerce search results from heterogeneous sources via hierarchical reinforcement learning. In The World Wide Web Conference.
THONET, T., CINAR, Y. G., GAUSSIER, E., LI, M. and RENDERS, J.-M. (2022). Listwise learning rank based approximate rank indicators. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36.
VOJNOVIC, M. and YUN, S. (2016). Parameter estimation for generalized thurstone choice models. In International Conference Machine Learning. PMLR.
WANG, S., HUANG, S., LIU, T.-Y., MA, J., CHENN, Z. and VELJALIINEN (2016). Ranking-oriented oriented collaborative filtering: A listwise approach. ACM Transactions on Information Systems (TOIS) 35 1-28.
WU, H. and LIU, X. (2016). Double thompson sampling for dueling bandits. Advances in neural information pro- cessing systems 29.
WU, Y., JIN, T., LOU, H., XU, P., FARNOUD, F. and GU, Q. (2022). Adaptive sampling for heterogeneous rank aggregation from noisy pairwise comparisons. In International Conference on Artificial Intelligence and Statistics. PMLR.
YUE, Y., BRODER, J., KLEINBERG, R. and JOACHIMS, T. (2012). The k-armed dueling bandits problem. Journal of Computer and System Sciences 78 1538-1556.
ZIIU, W., JIANG, Y., LIU, J. S. and DENG, K. (2023). natiiion-mallooss mallows model and its inference for rank aggre- gation. Journal of the American Statistical Association
Partition
118 343-359.
ZOGHI, M., KARNIN, Z. S., WHITESON, S. and DE RUKE, M. (2015). Copeland dueling bandits. Advances in neural information processing systems 28.
10

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
A. Proof of technical lemmas
We first show that Compare (Algorithm 3 returns the correct outcomes between the given two items with high probability, In the following, without loss of generality, follows those done similarly by (Saad et al. 2023), except that we deal with binary feedback representing the preference instead of numerical feedback for i and respectively.
assume the correct ordering between item i and item is > j. The proof
We first present the following lemma that characterizes the behavior of Try Cry-Comer (Algorithm Lemma A.1. In Algorithm 1 for each iteration for any fixed pair of items > have that probability of getting incorrect probability estimation bounded as:
10) [u
1
log(1 (1/5)
P
See ne
where St is the subset of active oracles and no is the number of repeated comparisons.
Proof. According to the assumption that i > j. B
1 Enese Pi,
1.4 Then we have
P
( Pi V
1
2 log( (1/6)
Pij
(0)
EI
2 log log (1/6) See Ino
S
|S mmo
The last inequality is due to Chernoff's inequality given that (i is summation of [Se|ng bounded independent random variables in (0, 1].
Then we have the following lemma stating the correctness Try-Compare (Algorithm
Lemma A.2. In Algorithm 4 the probability of returning an incorrect result or order bounded by:
Prrrturn x) s 1.75 log().)
Proof. If <3 is returned, then in Algorithm there exists some l such that the condition in Line is true. Formally, have
P(return i () < IP 36 E [logs/a(M/mm] p11 1/2 2 (2llog22/))mm/
s (log//3MM/m)bl
1.75 1o75 (
The first inequality holds due to the reasoning above; the second inequality comes from the union bound and Lemma A. the last inequality we drop m and rearrange terms.
Lemma A.3, Assume > j. Algorithm the wrong result will appear with probability P(return () S 0.68.
Proof. Let ans r denote the output of Algorithm 4 when it is called with arguments (Frmox : 8r, hp). We have
Preturn 5) < P 3rmax 2 1,3r S Fmax 0.88 (i <s})
P(ans if (i x())
Tmax =1 r=0
1.75
10(r max) )3 log log(MM)
Tiaa=
r=0
1.756 Faax +1 (2)
< 0.65,
10
T
Tmax
where (1) is due to Lemma A.2 and the definition 8 = 680(11(maa)) log(MM)) and (2) holds because Em
00
147mgg Tinax"

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
B. Proofs of theorems
B.1. Full statement of Theorem 5.1
Our restatement also follows the structure of three conclusion claims towards the end of the proof by Saad et al. 2023 Theorem 4.1, Section B).
Note that one difference between our version of Compare (Algorithm B and their original algorithm is that their is replaced with by us control the desired accuracy gap of one pairwise comparison. More specifically, in Line 2 of Algorithm 3 we calculated an equivalent 6, = 2- based on the input argument
In their notation, d is the number of experts (oracles), which is equivalent to M our notation.
The problem hardness factor Hi is similarly defined. The setting is slightly different in that Saad et al. (2023) considered the difference of two A-sub-Gaussinn variables while we consider a Bernoulli variable shifted by 1/2. The central problem to identify the sign of the expectation of the said random variables (which determines the order between i and j), and thus the problem hardness factors are defined the same spirit.
Now, we are ready restate the theorem.
Claim 1: The first part of the theorem can be directly derived from Lemma A.3 or Saad et al. (2023) Lemma B.3). Indeed, since Lemma A.3 states that Algorithm 3 will return the wrong result with probability most 0.65. Therefore, Algorithm returns either unsure or the correct order with probability at least 6. 6.
The second part of the theorem states that when r is sufficiently large, the algorithm will return the correct result with a high probability of at least
Claim 2:
To see this, when e 2- M/H.j, that is, when > (oggMMH,,,) the algorithm returns unsure with probability less than 0.40 by the same argument as in Saad et al. (2023 Eq.5 and Lemma B.8). And by Lemma A.3 it
returns the wrong order with probability less than 0.65. In total, the probability of returning the incorrect result is less than 8.
The third part deals with the sample complexity. is calculated under two conditions regarding the relationship between (hence e7) and M/ H. where e₁ a constant, According the end of the proof of [Sad et (2023 Theorem 4.1, Section B) and replace it with our notation have the following two cases:
Claim 3:
1. When ? 2 H. Algorithm finishes with a sample complexity of
(2g( 27
2 1olog(2M)) 2r)
-ō -0110(1/8)) 2-2r
M
M
ci (2M) log
log
(B.1)
2-2r
2. When e, < M/Hi.j. the total sample complexity is:
c log (Mg log(H log log(M)))))) Ha, ((log(1/))(1..)
(B.2)
B.2. Proof of Theorem 5.2
Proof. As stated in Theorem 5.1 for any pair (i,j) and T, with probability 5, the following event will hold for Compare(i,.i0..)
1. (ompare(i.j..ú7) outputs the correct order or unsure.
2. If Logo Compare(i.j.6.77 outputs the correct order.
3. The sample complexity is Ō(H.)).
For each i,j and r, denote (T) as the high-probability event described above regarding Compare (6. 77 Te.s)
in Algorithm 4 which is called within Probe-Max(S,, 25, 2 T,r) Algorithm Then, we have that
126
(T),)(T)) 2
N2
12

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
By union bound, the probability that there exists one pair (i,j) that is compared wrongly by Compare(1.5.8/f2 T(.) for some Ti.j is
N
128
P
U
U
(T)
S 6,
(B.3)
2
n N222
(4.))[[N1 r=1
where the last inequality comes from E = In the following proof, we assume that Compare 66/mm///, Te.s) always runs successfully. Now, using Equation B.1 Equation (..2). define the following two terms:
1. When & M/H for any > O,
(4) c1 log 2 (2M) log [log(2.) 4-1
N2 log (M/4
M
log
4-t = O4
(B.4)
128
2. When & < M/H that is T < M/ H.j. which is applied in the first inequality below:
Ti. log (H.,)) log(
3 = log (M) log H, log
Hi, S ((H.)).
(B.5)
120
Given the fact that RMO-WST only compares the pair contains at least one maximal element. In this case, for every call of Compare on pair (i,j) if i maximal, we say that item initializes the comparison, and the number of comparisons charged to i. both i are maximal, then the cost charged to both items. We denote the total number of charged comparisons as e(i), [N]. And the sample complexity of RMC-WST is most EiE[N] e(i).
Without loss of generality, assume the ranking of items is 1 2 2> value of Ti,-1 when the order between i and 1 is revealed. Let Tî = O. The order of adjacent items of i under WST condition can only be revealed when Compa re(i, 1, 1,28/N² N2 +;?) returns value other than unsure. According to < 2 log Hes-1]. ].
N. Given i [N] we use 7, to denote the
Lemma A.3 T
Define (7) as follows, where (T) defined in Equation (B.4)
(r) EE (0)
if < < otherwise
For each j * i, let Thy be the value of Tij when last time Compare is initialized by i and called before Probe-Max: (S; 25/N2). For any t > Tīj. if Compare(i, 22/N2,1 is called in Probe-Max(St,25)) for some < i, then it must not be initialized by i. In light of this, let TH be the value of Tıj after completion of Probe- (rx, 25/N3). We break down c(i) into two parts as follows:
c(1)
ΣΣ T=1
Σ j7i TE
6
(B.6)
We now move on bound the first summation term on the right- side of Equation (B.6). Before Probe-Max 25/N2) terminates, item i --1 is in T. Therefore, whenever i is maximal item, the order be- tween and i 1 is not revealed. So when initializes the comparison Compare(i,j, 28/N2, Tī,y), the item pair (i, 1) is also in the set of legitimate pairs P. Therefore, ग. is no larger than the value of Ti,-- at that point, and is further no larget than :
T
N
b < N
(B.7)
r=
13

---

which Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
We then continue bound the second summation term in c(i) in Equation (B66.. Consider the last group of Compare called in Probe-Max(S;; 26,,3) here the groups mean that there might be multiple item pairs whose values the minimum in P. Denote their t values by r². There must be some Compare 6,, 26/N2, r²) returning b; > a, such that a; is a maximal item, otherwise no maximal item is removed from U and P Probe-Max will not terminate. When every Compa re call is returning the correct order, a, is not the maximal in S; so a, > i. Thus, item 0g 1 is also in St and before the call of Compare(a,, b,. 26/N2, r"), the order between a, and a, - is not revealed, that is, T S Ta. Moreover, Th S because we always compare pairs items with the smallest T values, it follows that
Σ jtt
Σ
S N
(B.8)
11-11
+1
In summary, the total sample complexity is
N 7
Σ
(1)
2N
2N
(B.9)
5,2-1
i=
where the last equality is due to rî O. Plug in T; 1 [ log
-1,-1 M
into the above equation to get:
N
2N
N
Σ o (log (M) log 111 log (1g(HH).-)))og(AM))) H1,
(B.10)
N
Σ 1=2
log 2 (2M ) log (log(MM)
His-1
log
4N2 log(
Hi
M)18
0
His M)
(B.11)
M
M
M
N
= Ō N
H
(B.12)
1
Given we assumed w.l.ogg. that the correct ranking is 1 3 ... and the sample complexity is Equation B.
Now we conclude without this assumption the sample complexity would be Ō N Wi H Ho-1
B.3. Sketch of Proof of Improved Sample Complexity Upper Bound with SST Assumption
The proof of the upper bound of the sample complexity is similar to Theorem 11 in (Ren et al. 2019). Notice that our algorithm listed in Appendix D differs from theirs by switching the all the usage of ATC to Compare (Algorithm 3). The rest of the procedure does not change. We establish our claim by stating the equivalence this exchange in terms of algorithm guarantee.
First of all, note that Lemma in (Ren al. 2019) ATC states that
1. With probability 1 - 6, ATC returns the correct order or unsure.
2. If Ai.j, ATC returns the correct order.
3. The sample complexity is O(c log(1/8)).
In Algorithm 6 notice that it differs with Algorithm in that is no longer supplied through input arguments and
= 2 is calculated outside of this subroutine. In this case, e, in Algorithm 3 equivalent to in Algorithm 6 turns out to be slight change in notation.
With this in mind, we can restate the Theorem 5.1 as follows:
1. With probability
Compare returns the correct order or unsure.
2. If < / Hr.g/Ma Compare re returns the correct order.
14

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
3. The sample complexity is (())
Define H2 max]zi.eeN] Hij- With this established claim, plugin the condition v H and sample complexity O (logg(16)))))) for single pair to be correctly compared to the proof of Lemman 10 and Theorem 11 in (Ren ct al. 2019) to get the sample complexity as:
Σ Hi lo.) H,) log (og( VE[N]
(B.13)
B.4. Proof Theorem 5.6
Let A be d-correct algorithm. For any ranking o, it correspond problem instance in IwSr We denote PA the canonical bandit distribution of algorithm A under environment with p(i.j) = 2 + when (i.j) (a, b) and p(i, j) otherwise. We also denote Po as the canonical bandit distribution algorithm under environment with p(i,j) = everywhere.
Since A is an d-correct algorithm, its prediction on the ranking between and b, denoted as Ō(a) and @()), must align with the true ranking (a)) > o(b) with probability at least 1 - 6:
Pr. (o(a) (b)) V, [N], b.
Denote X = == Ci. the total number of queries made by A before it stops. Define the constant
f = inf x max P. (X > x) S 60.
a,b
Here, F serves as probabilistic lower bound of the total number of queries for all instances. This is the quantity we aim to bound from below in the coming reasoning. Lemma B.1. For the fixed F, we have that
PO X > T) 2 1 25.
Proof of Lemma B.1 We define two new distributions F2,2 and Pyg, where PP1, denotes the canonical bandit distribution of algorithm A under environment with p(i.j) = when (i.j) (1, and p(i.j) otherwise. P2,1 is defined similarly.
We have that
PA Φ)
and for
< i), we have for any
PT a(2,, x < < T4 (011) > 0(2), z)
+
sup
IP n (w: x x iFn fw x
(3:
< 8 + sup
[P X < क)) (FN
(w: X E])]
Fn(m:(53)
div PA (x
where the first inequality comes from the definition of total variance distance; the second inequality comes from A being 5-correct so that (7(1) > (2)) < Let a converge to 0, we have that the total variance distance will also converge to 0 when X < F. Therefore, the above inequality implies that (P > @ X < 2) < 8.
Applying the same argument (T(1 a(2), < F), we then conclude with TAA(X > F) 2 28.
15

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Consider new algorithm A' that performs exactly the same A, until A stops its total number of queries reaches E. In the latter case, A'' will stop and return 'null". We have that A' is an algorithm such that:
Pr (ā "null') - 6, Va, b [M] + b; 1P (ā 'null') - 26,
where 26 comes from two cases of failure: 1. outputting a wrong ranking as A with probability at most 6; 2. outputting 'null' when the queries exceed limit ë with probability at most 8.
By the Bretagnolle- Huber inequality, we have exp ( - dxl (T2'" (IP S 6Ó. Further, denoting we have
exp (- N(N 1)
ΣΣ
Ci (L (llpp(t)))llaaslt...)
a. 1
N(N - 1) Σ
(-Ioh
exp
a.b
(ddk( (1Pab))
exp
N(N - 1)
a,b
S 65,
where the first inequality comes from Jensen's inequality and Ci,, denotes the queries made by A' at (i, the first equation comes from the decomposition of KL-divergence for the canonical bandit model. (L denotes the KL-divergence between two Bernoulli random variables with expectation and q. Note that for (f, * (a, b). po(i, = (t. = 1/2.
Rearranging the terms and remove those terms with po(t, j) (a, gives
N(N - 1) log(l/g (66(1 Ω E
N2 log(110))
2²
Notice that, C,2, denotes the queries made by A' at (i, which satisfies that Easb Ca,b S which defined, serves as high-probability lower bound on the sample complexity of A.
B.5. Proof of Theorem 5.8
We define the following multi-oracle problem class:
Problem 3 (Iwsr)). Consider N items with an underlying ordering 'a'. For any items i, and oracle u,
ifo(i)) = and o(i) = 2,
VM
otherwise.
2>
For any (e, 8)-orrettt ranking algorithm that outputs a e-correct ranking under IWST with probability at least ō, we have that the algorithm must correctly rank between the largest item o (1) and the second-larges one 12)..
Because all oracles have the same comparison probability, the problem is equivalent to ranking with a single oracle, with the lower bound being 2 N M (og(1/8)
C. Improved Algorithm in Empirical Study
In this section, present the algorithm that is modified for practical usage. Instead of using estimator رo. that only depends on the data collected in the same iteration of the for loop. A global estimator is derived from the statistics collected from multiple iterations to save sample complexity (Line 6)
D. Improved Algorithm with SST Assumption
In this section, we display the improved algorithm that can lead to a log factor improvement of the BinarySearch algorithm that is proposed by [Sadd et al. (202)) for active ranking problems. We replace the Attemmt-to-Compare
16

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Algorithm 5 (Improved version for practical adoption) Try-Compare s, h)
1: input: pair to query (i, confidence level 6, subset size 8, estimated gap width h.
2: m M.
3: S1 [M].
4: Let 59 = S S1 and I. (084/3(MM/S)
5: for t= 0,... I do
6: Request 11 nomm || comparisons for pair (i,j) from each oracle 5 U U.S Denote oi as the number of
times -
(u.0) (1 E,Ew Euest Pi,j Pij Ene for Pjá
(u.e) Eren ct
(u.() = -1 Pij 1821
(u.e)
8:
if (()
Mij
1
v 1og (og(2/8)/nggm) then
9:
return
j
10:
end if
11:
if p
2 - 2ogg((/)))) then jj
12:
return
13:
end if
14:
Se11 + {u E 1
medium of ala.)) u E S/¹ }
S441 + {ue E spimpt
medium (a.() u Sp
15:
end for
17:
return unsure.
(ATC) subroutine in the Iterative Inerative--nsettioon-eetd (IIR) by Ren et al. (2019) with the Compare (Algorithm) proposed in this work achieve this.
Algorithm 7 Main Procedure: RMO-SST
input: N, T.M.8
initialize: C = N = 0
C1 + list containing only
2: for i
N do
3: C, + 1A - 1))
b Algorithm g
4: end for
Output: LN
Algorithm 8 Subroutine: sterrative-Attens-------sss ([AI)
input: i, 6 initialize: t == 0, Flag t- unsure
1: repeat
2:
t= 1, 2--(-1), 8, 66
x²
Flag, ATI(i, L, cz. 86)
D Algorithm
4: until Flag inserted
5: return C
17

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Algorithm 6 ATC(i, (modified version Compare in Algorithm 3)
1: input: pair (i,j), confidence level ó, precision factor
2: initialize: Tmax = ans = unsure.
3: while ans unsure and c² < 4 (2g) Tmax do
4: for 0,... mmax do
5: S, 2" h2 2
6: 8rmex m10mm log(M))
7: ans t Try-Compar (i, Tmax Sr, hy)
8: anss o unsure, break.
9:
end for
Tmax <- Tmax +1
end while
12: if ans = - j then
13: ans <- i
14: end if
15: if ams = j > then
16: ans j
end if
return ans
18

---

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
Algorithm 9 Subroutine: Toteempt-T--nnee Insert (ATT)
input: i, e, initialize: Let 7 be PIT constructed from L. h + log, (1 + [I), the depth of T
For all leaf nodes of T, initialize Gu 0; Set ymax mmax (4h, 512 log } and q
1: X + the root node of T
2: for <- to fmax do
3:
if X is the root node then
4:
q ATC(i, X.cdd,
Algorithm 6
5:
if q then
6:
X < X.rchild
7:
else
8:
X < X.Ichild
9:
end
10:
else if X a leaf node then
91 ATC(i, X.left, e, 49)
Q2 ATC(i, X.right, e,
/9)
13:
gt iA Q2
X X.right then
14:
- cx +
15:
cx > b' := 1
x² log 34 + then
16:
Insert into the corresponding interval of X and return inserted end if
17:
18:
19:
else if' cx > 0 then
20:
cx - cx -
21: else
X + X.parent
23:
end if
24:
else
25:
ATC(i, X. X.left,
4/1)
26:
- ATC(i, X. ririhht e,
(/)
27:
93 - ATC(i, X.mid, e, (7)
28:
if q1 = X.left V 92 = then
X < X. papere
30:
else if (3 then
31:
X < X.rchild
32:
else
33:
X - X.Ichild
34:
end if
35: end if
end for
37: if there is leaf node with cu 21 mmax then
38: Insert i into the corresponding interval of u
39: return inserted
40: else
41:
return wnsure
42: end if
19


Reviews:
[{"review_id": "0IoBPW7yWx", "reviewer": "Reviewer_itcx", "summary": "This paper addresses the problem of efficiently aggregating preferences from multiple oracles to determine rankings under different stochastic transitivity conditions. The authors propose two main algorithms: RMO-WST for the Weak Stochastic Transitivity (WST) setting, and RMO-SST for the Strong Stochastic Transitivity (SST) setting. Experimental results validate the theoretical advantages of these algorithms, showing consistent improvement over a baseline method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thanks for your positive and constructive comments. We address your questions below: \n\n**Q1**: The consistency assumption (Assumption 3.1) seems quite strong in practical settings. Have you considered a relaxed version where oracles can disagree on some small fraction of pairs? How would this affect your theoretical guarantees?  \n**A1**: Great suggestion! It is possible to generalize to a broader, more flexible case where oracles can disagree on a small group of pairs. However, without a strict consistency guarantee, we can only define an objective ranking using numerical indicators like win rate. For example, one may use the Copeland/Borda score to determine a ground-truth ranking when there is inconsistency among oracles.\nAdditionally, these methods typically involve examining all oracles with the same accuracy and then concluding with a majority voting, which usually leads to a less efficient algorithm (introducing an additional factor of $M$). \n\n\n**Q2**: Your RMO-SST algorithm achieves a log(N) factor improvement over prior work. Is this improvement purely analytical, or does it correspond to a specific algorithmic innovation that wasn't present in previous approaches?  \n**A2**: The improvement comes from applying new algorithm design that wasn't present in Saad’s work. In the previous work by Saad, when inserting an item into the sorting tree, their algorithm simply divided the confidence budget into $\\log N$ pairwise comparisons, leading to an additional $\\log N$ factor. Our improvement comes from treating the insertion as a whole process and carefully assigning the budget when inserting an item into the tree. \n\n**Q3**: For the WST setting, you provide matching upper and lower bounds. Do you believe similar tight bounds exist for the SST setting? If there's a gap, where might the improvement come from?  \n**A3**: For the SST case, the lower bound is order-wise tight given the proof presented in Ren et al. 2019, which is briefly mentioned in Remark 5.5, line 339. Ren’s lower bound is for a single oracle, but can be easily modified to multiple oracles.\n\n**Q4**: The empirical evaluation focuses on synthetic data with a specific pattern. How would performance change with more complex accuracy distributions, such as when different oracles have expertise on different subsets of items?  \n**A4**: The algorithm and theoretical analysis cover this case where different oracles have expertise on different subsets of items. For each subset of the items (or a specific pair in the context of this paper), the best oracles are elected from scratch for that specific pair. In this regard, our proposed algorithm will continue to enjoy at least the efficiency that a non-RMO version of the algorithm (e.g. Probe-Max) has. \n\n**Q5**: Your algorithms require the number of oracles M as an input parameter. In crowdsourcing scenarios, this number might grow over time. Is there a natural way to adapt your algorithms to an online setting where new oracles can join?  \n**A5**: That’s a great question. Our algorithm can be viewed as selecting the best oracles for different pairs. Thus, when new oracles (crowd-source labellers) come in, they can wait until the algorithm attempts to compare the next new item pair. In this way, the algorithm can work without any modification.", "claims_and_evidence": "The claims in this paper are supported by evidence:\n- The sample complexity bounds for both algorithms are derived through detailed mathematical proofs\n- The lower bound for WST ranking matches the upper bound, providing a complete characterization\n- Experimental results confirm the theoretical advantages, showing that RMO-WST consistently outperforms the Probe-Max baseline\nThe evidence is provided for the theoretical contributions. The empirical evaluation, while supporting the claims, is somewhat limited in scope (only synthetic data with one specific pattern of oracle accuracies).", "methods_and_evaluation_criteria": "The proposed methods are well-designed for the ranking problem:\n- The bi-level design effectively separates the ranking strategy from the comparison mechanism.\n- The oracle selection approach intelligently adapts to varying oracle accuracies.\n- The WST and SST conditions appropriately model different real-world preference scenarios.", "theoretical_claims": "The theoretical analysis appears sound:\n- Theorem 5.1 (Compare algorithm guarantees): Builds on Saad et al. (2023) with appropriate modifications\n- Theorem 5.2 (RMO-WST sample complexity): Relies on an accounting method that tracks and bounds the total number of comparisons made by the algorithm.\n- Theorem 5.4 (RMO-SST sample complexity): Replaces the Attempt-to-Compare (ATC) subroutine from Ren et al. (2019) with their improved Compare algorithm (Algorithm 3) while keeping the overall structure of the Iterative-Insertion-Ranking (IIR) framework.\n- Theorem 5.8 (Lower bound): Uses a reduction to a hard instance and information-theoretic arguments.", "experimental_designs_or_analyses": "The experimental design compares RMO-WST against Probe-Max across various settings (number of ranking items and number of oracles). The experiments are sound but limited in scope. Testing with different oracle accuracy distributions or real-world preference data would have provided more comprehensive validation.", "relation_to_broader_scientific_literature": "The work extends and connects to several research areas: single-oracle active ranking, and multi-oracle ranking approaches.", "essential_references_not_discussed": "Based on my assessment, the authors have thoroughly addressed the key findings present in existing literature on this topic.", "other_strengths_and_weaknesses": "Strengths and weaknesses have been highlighted in other questions.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. The consistency assumption (Assumption 3.1) seems quite strong in practical settings. Have you considered a relaxed version where oracles can disagree on some small fraction of pairs? How would this affect your theoretical guarantees?\n2. Your RMO-SST algorithm achieves a log(N) factor improvement over prior work. Is this improvement purely analytical, or does it correspond to a specific algorithmic innovation that wasn't present in previous approaches?\n3. For the WST setting, you provide matching upper and lower bounds. Do you believe similar tight bounds exist for the SST setting? If there's a gap, where might the improvement come from?\n4. The empirical evaluation focuses on synthetic data with a specific pattern. How would performance change with more complex accuracy distributions, such as when different oracles have expertise on different subsets of items?\n5. Your algorithms require the number of oracles M as an input parameter. In crowdsourcing scenarios, this number might grow over time. Is there a natural way to adapt your algorithms to an online setting where new oracles can join?", "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": "", "extra_scores": {}}, {"review_id": "lxkZ09EvsS", "reviewer": "Reviewer_NsPH", "summary": "The paper studies the problem of identifying the ranking of a set of items by querying pairwise preferences from several oracles. In particular, they study two settings: (1) weak stochastic transitivity (WST), where there exists a ranking (permutation) of items such that items ranked higher has higher probability of being preferred by all oracles; (2) strong stochastic transitivity, where in addition to (1), if an item i ranks higher than j, and j ranks higher than item k, then it is easier (probability of preference is further away from 0.5) to identify i is better than k than the other two comparisons.  They measure the performance of an algorithm by the number of times needed to query oracles. \n\nIn the WST setting, they provided a lower bound on the number of queries, and proposed an algorithm that achieves an upper bound that matches the lower bound. In the SST setting, they proposed an algorithm that improves upon prior best-known sample complexity by log factors, and matches the lower bound of the problem.\n\n\"## update after rebuttal\n\nI would like to keep my evaluation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thanks for your positive comment. We address your question raised below: \n\n**Q1**: Some assumptions might not hold in practical real-world applications. For instance, different people might rank different LLMs differently.  \n**A1**: It is possible to consider more general cases. Without a strict consistency guarantee, we need to define a ground-truth ranking using numerical indicators like win rate. For example, one may use the Copeland/Borda score to determine a ground-truth ranking when there is inconsistency among oracles. Additionally, these methods typically involve examining all oracles with the same accuracy and then concluding with a majority voting, which usually leads to a less efficient algorithm (introducing an additional factor of $M$).\n\n**Q2**: In the bounds, the confidence term $\\delta$ is missing. I guess they are in the log term. It might be good to present it to the readers to see how that affects the bound.  \n**A2**: We might omit some of the terms in the main text to reduce clutter for ease of reading. In Table 1, we included the log dependence on $\\delta$.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not check proofs.", "experimental_designs_or_analyses": "I did not find problems.", "relation_to_broader_scientific_literature": "The paper studies a problem of rank aggregation, which is a problem studied by many prior works. \n\nThe paper specifically focuses on the setting where there are multiple oracles, where there is only one work that studies it under the SST condition. The paper proposed an algorithm that achieves better theoretical guarantees than the prior work under the SST setting. The paper also studies the problem under the WST setting. \n\nThe proposed method borrows some ideas from prior works.", "essential_references_not_discussed": "I am not aware of any", "other_strengths_and_weaknesses": "Strengths\n\n1. The paper is a well-written and a pleasure to read.\n\n2. The paper presents a theoretical analysis of the problem, providing both upper and lower bound on the WST setting and improved upon prior works under the SST setting and matches the lower bound of the problem. \n\nWeaknesses:\n\n1. Some assumptions might not hold in practical real-world applications. For instance, different people might rank different LLMs differently.", "other_comments_or_suggestions": "In the bounds, the confidence term \\delta is missing. I guess they are in the log term. It might be good to present it to the readers to see how that affects the bound.", "questions_for_authors": "no", "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": "", "extra_scores": {}}, {"review_id": "FUakJEvQR9", "reviewer": "Reviewer_h6RV", "summary": "This paper studies the problem of ranking items using noisy pairwise comparisons from multiple oracles under both the weak stochastic transitivity (WST) and strong stochastic transitivity (SST) conditions. While previous work has explored ranking under SST with single and multiple oracles and WST for a single oracle, this paper extends the study to WST with multiple oracles, completing the literature in this area. Secondly, the authors derive a lower bound for the WST setting, which also holds for SST, resolving a prior conjecture. As a third contribution, they propose an improved algorithm for SST that reduces the sample complexity by a logarithmic factor compared to previous methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thanks for your positive comment. We address your question raised below:\n\n**Q1**: ``medium'' in Algorithm 4 should be defined in the text.  \n**A1**: medium follows the definition in conventional statistics, where it’s the number(item) that is ranked in the middle of all numbers in the set of interest. We will add an explanation to the main text.\n\n**Q2**: Assumptions 3.2 and 3.3 can be named as definitions.  \n**A2**: Thanks for pointing it out. Indeed, we can define the two settings first.  We will modify them in our revision.\n\n**Q3**: Page 3, Lines 138 -139: ``Iterative-Insertion-Ranking (IIR) [Ren et al., 2019] proposes an algorithm ...'' requires rewording.   \n**A3**: That’s a great catch, we would revise it into: Ren et al. propose the Iterative-Insertion-Ranking (IIR) algorithm that uses preference interval trees to perform binary search to sequentially insert items into an already ranked list. \n\n**Q4**: The notations $H_i$,$H_{i,j}$ cause confusion (especially in the table and main contributions) since it is not defined until page 4, and I had to refer to the reference papers to determine their precise definition. Also, in Table 1, $\\Delta_i$ is not defined, even in text (I believe).    \n**A4**: To improve the readability of the paper, we consider moving the “Preliminaries” section right after the “Introduction”, where $H$ can be defined a bit earlier. For $H$ we used in the ‘’Abstract’’ and ‘’Introduction’’ section, we revised the wording so that understanding it as a Hardness Factor is enough to proceed with reading. $\\Delta_i$ is defined on the right column of line 174, based on the definition of $\\Delta$.\n\n**Q5**: The authors assume there is no ‘best’ oracle for all pairs of comparisons. If there is a single best oracle, does the algorithm quickly detect that oracle and is able to reduce the complexity that closely matches the single oracle case?  \n**A5**: That is right, if there is indeed a single best oracle, the algorithm can be slightly modified to only keep those decent oracles found in previous rounds, and eventually only one best oracle will be left to perform all of the rest pairs.  \nLine 96, right column, mentions an algorithm that maintains two sets of estimates globally: one for items and one for oracles (Wu et al., 2022). This paper studies exactly the setting you mentioned under SST, which can be easily extended to the WST setting as well.  We will revise the original text to incorporate this.", "claims_and_evidence": "1. The notation $\\tilde{O}$ hides logarithmic factors. It is not specified which logarithmic factors are hidden. Therefore, it is difficult to verify the third claim in the contributions, where the authors claim to reduce the sample complexity by a logarithmic factor.\n\nSee questions", "methods_and_evaluation_criteria": "Yes, the problem is standard and with well-defined evaluation criteria.", "theoretical_claims": "Essentially correct.", "experimental_designs_or_analyses": "The experiments are fine, considering the main contribution of the work is primarily theoretical.", "relation_to_broader_scientific_literature": "The work is well positioned with respect to the other works in literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Other minor comments\n\n1. ``medium'' in Algorithm 4 should be defined in the text.\n\n2. Assumptions 3.2 and 3.3 can be named as definitions.\n\n3. Page 3, Lines 138 -139: ``Iterative-Insertion-Ranking (IIR) [Ren et al., 2019] proposes an algorithm ...'' requires rewording. \n\n4. The notations $H_i, H_{i,j}$ cause confusion (especially in the table and main contributions) since it is not defined until page 4, and I had to refer to the reference papers to determine their precise definition. Also, in Table 1, $\\Delta_i$ is not defined, even in text (I believe).", "questions_for_authors": "In addition to the question in claims and evidence, I have an additional question\n\n2. The authors assume there is no ‘best’ oracle for all pairs of comparisons. If there is a single best oracle, does the algorithm quickly detect that oracle and is able to reduce the complexity that closely matches the single oracle case?", "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": "", "extra_scores": {}}, {"review_id": "O08yrQP6GR", "reviewer": "Reviewer_N84J", "summary": "This paper considers the problem of estimating the ranking of $N$ items using pairwise comparisons. . Two different assumptions are considered: weak stochastic transitivity (if $p_{ij} \\ge 1/2$ and $p_{jk} \\ge 1/2$, then $p_{ik} \\ge 1/2$) and strong stochastic transitivity ($p_{ik} \\ge \\max (p_{ij}, p_{ik})$), where $p_{ij}$ is the probability that the oracle answers $i \\succ j$ when comparing $i$ and $j$. There are multiple oracles that return the correct answer with different probabilities. This paper proposes an approach with improve sample complexity that combines Probe-Max proposed by Lou et al. (2022) for ranking estimation and Compare proposed by Saad et al. (2023) for oracle selection. They also prove a lower bound on the sample complexity.\n\n## update after rebuttal\nI keep my positive score based on the authors' rebuttal. I hope that the authors update the manuscript so that the two independent components of the proposed algorithm are clearly presented.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer thanks for your time and effort for the review and suggestions, we address your concern below:\n\n**Q1**: Since the proposed method is a combination of high-level ranking algorithm and a low-level oracle selection algorithm, it is possible to consider benchmarks based on existing methods given in Table 1, even if they are for the single-oracle setting.  \n**A1**: Thanks for the suggestion. The main difficulty in including more benchmarks is that most such benchmarks are offline datasets. There are no widely acknowledged benchmarks for online, interactive algorithms. This is the main reason why we use a synthetic environment with multiple oracles. Ren et al. also used a synthetic environment for the single-oracle setting.\n\n**Q2**: I believe it can be simplified by separately describing building blocks. In my understanding, the proposed method is a combination of ranking estimation and oracle selection, and both of them can be independently combined with other methods.  \n**A2**: Thanks for your suggestion. You are correct that the algorithms can be broken down into two major pieces. We will revise and restructure the text to make it easier to read.", "claims_and_evidence": "The contribution of the paper is clearly stated, and all the theoretical results are provided with the full proofs.", "methods_and_evaluation_criteria": "The empirical results use only randomly generated datasets. It is not fully satisfactory, but reasonable just for complementing the theoretical results.", "theoretical_claims": "I did not check the details of the proofs, but briefly checked them and found no fatal errors.", "experimental_designs_or_analyses": "In my opinion, the experiments could be improved by adding more benchmark algorithms. Currently, the experiments compare the proposed method with a single competitor, which is a naive extension of Probe-Max originally developed for the single-oracle setting. Since the proposed method is a combination of high-level ranking algorithm and a low-level oracle selection algorithm, it is possible to consider benchmarks based on existing methods given in Table 1, even if they are for the single-oracle setting. If the authors add more benchmark algorithms to the experiments, the empirical contribution of this paper would be increased.", "relation_to_broader_scientific_literature": "The proposed method in this paper is built on the existing algorithms for the single-oracle setting such as Probe-Max by Lou et al. (2022) and IIR by Ren et al. (2019) and the one for the multiple-oracle setting by Saad et al. (2023). The sample complexity upper bound is improved and lower bound is newly proved.", "essential_references_not_discussed": "To my knowledge, all related works are clearly discussed.", "other_strengths_and_weaknesses": "Not particularly.", "other_comments_or_suggestions": "The introduction and problem setting are clearly written, but the algorithm description is complicated. I believe it can be simplified by separately describing building blocks. In my understanding, the proposed method is a combination of ranking estimation and oracle selection, and both of them can be independently combined with other methods.", "questions_for_authors": "Not particularly.", "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": "", "extra_scores": {}}, {"review_id": "oXm9w0rCr9", "reviewer": "Reviewer_uH7J", "summary": "The paper studies the problem of ranking a set of $N$ items using $M$ ranking oracles under weak or strong stochastic transitivity conditions. Each oracle $u$, when queried with a pair of items $i$ and $j$, independently returns an indicator of its preference, represented by a probability $p_{i,j}^u$. The objective is to determine the ranking of all items while minimizing the total number of queries to the oracles.  \n\nThe paper establishes tight bounds under both weak and strong stochastic transitivity conditions. The upper bound under the strong stochastic transitivity condition matches existing lower bounds, whereas the upper bound under the weak stochastic transitivity condition matches the lower bound presented in the paper.  \n\nExperiments justify the theoretical findings of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer thanks for your time and effort for the review and suggestions, we address your concern below:\n\n**Q1**: Line 104–105, $\\Delta := | p_{i,j} - \\frac12 | $. Something may be missing here, e.g., min or sum.  \n**A1**: thanks for spotting this, the correct definition should be $\\Delta := \\min_{(i,j) \\in [N] \\times [N]} | p_{i,j} - \\frac12 | $\n\n**Q2**: Line 247, “After N-1 rounds of finding the maximal item…” Why are there N−1 rounds here? Does U contain N items?  \n**A2**: This sentence “After N-1 rounds of finding the maximal item…” actually refers to Algorithm 1, where it finds the current maximal item and deletes it. After $N-1$ rounds, the remaining item will be the minimum item out of the N items. We will move it to the correct place. We apologize for the confusion.  \nAs for Algorithm 2, the candidate set $U$ has at most $N$ items. Every time a new pairwise relation is revealed, one of the two items cannot be the maximum item, so we remove it from $U$. After at most $N$ rounds, the maximum item will be found. \n\n**Q3**: Assumption 3.1 seems strong, as it requires all oracles to have consistent ratings for all pairs of items. This assumption may not hold in practice—for example, when evaluating two LLMs, some users may favor one model over the other, while others may not. Is it possible to relax this assumption?  \n**A3**: It is possible to consider more general cases. Without a strict consistency guarantee, we need to define a ground-truth ranking using numerical indicators like win rate. For example, one may use the Copeland/Borda score to determine a ground-truth ranking when there is inconsistency among oracles.  \nAdditionally, these methods typically involve examining all oracles with the same accuracy and then concluding with a majority voting, which usually leads to a less efficient algorithm (introducing an additional factor of $M$).\n\n**Q4**: What are the logarithmic factors hidden in Theorem 5.4?    \n**A4**: \n$ \\log^2 (M) \\log(H_i)$ is the hidden factor.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I didn’t go through the proofs.", "experimental_designs_or_analyses": "The experimental section discusses an improved algorithm presented in the Appendix.", "relation_to_broader_scientific_literature": "Ranking with multiple noisy oracles should have applications in many fields.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "1. The paper is well written overall.  \n\n2. The problem studied is of practical importance and could have applications in multiple fields.", "other_comments_or_suggestions": "1. Line 104–105, $\\Delta := |p_{i,j} – 1 / 2|$. Something may be missing here, e.g., min or sum.  \n\n2. Line 247, “After N-1 rounds of finding the maximal item…” Why are there $N-1$ rounds here? Does $U$ contain $N$ items?", "questions_for_authors": "1. Assumption 3.1 seems strong, as it requires all oracles to have consistent ratings for all pairs of items. This assumption may not hold in practice—for example, when evaluating two LLMs, some users may favor one model over the other, while others may not. Is it possible to relax this assumption?  \n\n2. What are the logarithmic factors hidden in Theorem 5.4?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the sample complexity bounds for ranking from pairwise comparisons from multiple oracles. The theoretical results include tight bounds when weak stochastic transitivity holds and an algorithm with same upper bound for strong stochastic transitivity holds (improving by a logN factor of what was previously known). The experimental validation shows the proposed algorithms performs better than the baselines.

All the reviewers agree that the theoretical contributions are well-rounded. However, few raised concerns about novelty of the results as it relies on previously known algorithms with single oracle, but the authors justified that the improved results are obtained due to new algorithmic ideas not present in previous works. A few raised concerns about the experimental validation but the authors have sufficiently justified the concerns. Since the theoretical contributions are significant, I think this is a good enough contribution to appear in ICML. The authors are advised to udpate the final version of the paper according to reviewers' suggestions about writing.
Decision: Accept (poster)