Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity
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 Rank-with-Multiple-Oracles (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 O(N N i=2 H σ -1 (i),σ -1 (i-1) ), where N is the number of items to rank, H i,j is a problemdependent hardness factor for correctly comparing item i and item j, and σ -1 (i) represents the ith 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. Additionally, when the SST condition is satisfied, we propose an algorithm named RMO-SST, which can achieve a sample complexity of O( N i=1 H i log(N )), where H i = max j∈[N ],j̸ =i H i,j . 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on6
- Adversarial Dueling BanditsAadirupa Saha, Tomer Koren, Yishay MansourICML 2021 · 35 citations
- Elo-MMR: A Rating System for Massive Multiplayer CompetitionsAram Ebtekar, Paul LiuWWW 2021 · 21 citations
- Rank Aggregation via Heterogeneous Thurstone Preference ModelsTao Jin, Pan Xu, Quanquan Gu, Farzad FarnoudAAAI 2020 · 19 citations
- Listwise Learning to Rank Based on Approximate Rank IndicatorsThibaut Thonet, Yagmur Gizem Cinar, Éric Gaussier, Minghan Li et al.AAAI 2022 · 12 citations
- Active Ranking without Strong Stochastic TransitivityHao Lou, Tao Jin, Yue Wu, Pan Xu et al.NeurIPS 2022 · 11 citations
Related papers
- The Sample Complexity of Best-k Items Selection from Pairwise ComparisonsWenbo Ren, Jia Liu, Ness B. ShroffICML 2020 · 14 citations
- Sample Complexity Bounds for Active Ranking from Multi-wise ComparisonsWenbo Ren, Jia Liu, Ness B. ShroffNeurIPS 2021 · 5 citations
- Multi-Objective Ranking Optimization for Product Search Using Stochastic Label AggregationDavid Carmel, Elad Haramaty, Arnon Lazerson, Liane Lewin-EytanWWW 2020 · 48 citations
- Batched Dueling BanditsArpit Agarwal, Rohan Ghuge, Viswanath NagarajanICML 2022 · 12 citations
- Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity ModelsViktor Bengs, Aadirupa Saha, Eyke HüllermeierICML 2022 · 32 citations
