# Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons

arXiv: https://arxiv.org/abs/2110.04136 · HTML: https://mlsanity.com/paper/2110.04136/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 8 Oct 2021.

## Builds on (most cited first, 8 of 8)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Maximum Selection and Ranking under Noisy Comparisons](https://mlsanity.com/paper/1705.05366/) (2017)
- [Multiagent Evaluation under Incomplete Information](https://mlsanity.com/paper/1909.09849/) (2019)
- [Rank Aggregation via Heterogeneous Thurstone Preference Models](https://mlsanity.com/paper/1912.01211/) (2019)
- [On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons](https://mlsanity.com/paper/1909.03194/) (2019)
- [Learning Mixtures of Plackett-Luce Models from Structured Partial Orders](https://mlsanity.com/paper/1910.11721/) (2019)
- [Adversarial Online Learning with noise](https://mlsanity.com/paper/1810.09346/) (2018)
- [Adaptive Multiple-Arm Identification](https://mlsanity.com/paper/1706.01026/) (2017)

## Built on by (most cited first, 3 of 3)

- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem](https://mlsanity.com/paper/2310.02016/) (2023)

## Abstract (arXiv)

In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus a uniform querying strategy over users may not be optimal. To address this issue, we propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons from users and improves the users' average accuracy by maintaining an active set of users. We prove that our algorithm can return the true ranking of items with high probability. We also provide a sample complexity bound for the proposed algorithm which is better than that of non-active strategies in the literature. Experiments are provided to show the empirical advantage of the proposed methods over the state-of-the-art baselines.