Human Preferences as Dueling Bandits

Xinyi Yan, Chengxi Luo, Charles L. A. Clarke, Nick Craswell, Ellen M. Voorhees, Pablo Castells

TL;DR

As information retrieval systems become incredibly good, distinguishing between top-performing rankers is challenging. This paper proposes framing the task of identifying the "best" search results using human preference judgments as a dueling bandits problem. They find that existing dueling bandit algorithms often fail to meet the practical requirements of human evaluation, leading them to adapt and validate a specific algorithm for this purpose.

What Problem Does This Paper Address?

Modern information retrieval (IR) systems, particularly those using neural rankers, are achieving remarkable performance. This success creates a new problem: when all rankers return highly relevant results at the top, it becomes difficult to discern meaningful differences between them and to build robust test collections for further evaluation. Traditional methods rely on pointwise relevance judgments (e.g., "perfect," "highly relevant"), but these can be subjective and hard to differentiate at the top tier. The authors propose using pairwise preference judgments – where human assessors choose the better of two results for a given query – as a more sensitive alternative. The core challenge is how to efficiently collect and interpret these preferences to identify the truly best items, especially given the cost and potential noise in human judgments.

Methods

The paper frames the problem of identifying the best search results from a pool of candidates as a dueling bandits problem. In this framework, each search result is an "arm," and the goal is to identify the best arm(s) through pairwise comparisons. The authors highlight specific requirements for this application: tolerance for ties (since humans might find results equally good), efficiency (minimizing the number of judgments), and near-linearity in the number of comparisons with respect to the number of candidate items.

They review existing dueling bandit algorithms from machine learning and IR literature. Crucially, they note that many algorithms' theoretical guarantees rely on assumptions (like strict transitivity or no ties) that don't hold well for human preference data. To bridge this gap, they:

  1. Simulate selected algorithms on artificial test cases designed to mimic scenarios with and without ties.
  2. Identify the Clarke et al. [9] algorithm as the most promising candidate due to its practical approach to handling pools of items and its focus on finding top items.
  3. Modify and validate the Clarke et al. algorithm, particularly by introducing an "extra finalization phase" to improve robustness against ties.
  4. Collect a large-scale dataset of over 10,000 human preference judgments using their modified algorithm.

Datasets

The primary dataset used for evaluation is a newly collected set of over 10,000 human preference judgments. These judgments were collected for pools of search results derived from submissions to the TREC 2021 Deep Learning Track's passage retrieval task. The initial set of queries was 50, with 46 ultimately used. The pools were constructed from runs submitted to the track, focusing on passages deemed relevant by TREC assessors. The paper also uses artificial datasets (Case A and Case B) for simulation purposes to test algorithm behavior under different conditions (total order vs. many ties).

Key Insights and Ideas

  • Neural rankers make traditional evaluation hard: When systems are "too good," subtle differences matter, and standard evaluation metrics struggle to capture them.
  • Human preferences are noisy but valuable: While human judgments can have ties and errors, they offer a more nuanced signal than traditional graded relevance, especially for distinguishing top-tier results.
  • Existing dueling bandit theory doesn't perfectly fit human data: Assumptions like strict transitivity and no ties are often violated, making direct application of theoretical guarantees problematic.
  • The Clarke et al. [9] algorithm is a strong foundation: Its focus on finding top items and its practical approach make it a good starting point for human preference evaluation.
  • An "extra finalization phase" significantly improves robustness: Adding a second round of judgments for the final candidate set helps reduce ties and improve the reliability of identifying the best items.
  • "Best item" evaluation is viable: Focusing on identifying the single best item (or a small set of best items) per query is a practical and meaningful evaluation strategy, especially in sparse label scenarios.

Key Results

  • Simulations showed that most existing dueling bandit algorithms performed poorly on test cases with many ties, failing to reliably identify the best items.
  • The Clarke et al. [9] algorithm, particularly with the added finalization phase, demonstrated better performance in simulations and was chosen for real-world evaluation.
  • The collected dataset of over 10,000 preference judgments validated the suitability of the modified Clarke et al. algorithm for human evaluation tasks.
  • The study found a strong correlation (Kendall's τ > 0.8) between the proposed preference graph compatibility metric and official TREC NDCG@10 scores on experimental runs, suggesting the preference-based approach aligns well with established evaluation.
  • The cost of collecting these judgments was approximately $0.36 per judgment.

Limitations and Future Work

  • Algorithm limitations: While the Clarke et al. algorithm was chosen, it still lacks explicit theoretical guarantees for human preference scenarios. The authors suggest further theoretical investigation, potentially drawing from work on non-dueling bandits.
  • Finalization phase: The "extra finalization phase" was a heuristic improvement. The authors hope to discover and validate a more principled method for this phase.
  • Duplicate passages: The study discovered exact duplicate passages in the test collection, which could have impacted results. While they found their approach was somewhat robust to this, it highlights the need for careful dataset curation.
  • Dynamic pruning: The paper suggests extending theoretical understanding to dynamically choose the number of comparisons during pruning phases, rather than using fixed parameters.
  • Sparse labels: The work supports the idea of using "best known items" as sparse labels for evaluation, but further exploration of this paradigm is suggested.

Summary updated

Abstract

The dramatic improvements in core information retrieval tasks engendered by neural rankers create a need for novel evaluation methods. If every ranker returns highly relevant items in the top ranks, it becomes difficult to recognize meaningful differences between them and to build reusable test collections. Several recent papers explore pairwise preference judgments as an alternative to traditional graded relevance assessments. Rather than viewing items one at a time, assessors view items side-by-side and indicate the one that provides the better response to a query, allowing fine-grained distinctions. If we employ preference judgments to identify the probably best items for each query, we can measure rankers by their ability to place these items as high as possible. We frame the problem of finding best items as a dueling bandits problem. While many papers explore dueling bandits for online ranker evaluation via interleaving, they have not been considered as a framework for offline evaluation via human preference judgments. We review the literature for possible solutions. For human preference judgments, any usable algorithm must tolerate ties, since two items may appear nearly equal to assessors, and it must minimize the number of judgments required for any specific pair, since each such comparison requires an independent assessor. Since the theoretical guarantees provided by most algorithms depend on assumptions that are not satisfied by human preference judgments, we simulate selected algorithms on representative test cases to provide insight into their practical utility. Based on these simulations, one algorithm stands out for its potential. Our simulations suggest modifications to further improve its performance. Using the modified algorithm, we collect over 10,000 preference judgments for pools derived from submissions to the TREC 2021 Deep Learning Track, confirming its suitability. We test the idea of best-item evaluation and suggest ideas for further theoretical and practical progress.
BibTeX
@inproceedings{yan2022human,
  author = {Xinyi Yan and Chengxi Luo and Charles L. A. Clarke and Nick Craswell and Ellen M. Voorhees and Pablo Castells},
  title = {{Human Preferences as Dueling Bandits}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2022},
  url = {https://openreview.net/forum?id=_Xeb2lu8HZ},
}
Figure