Human Preferences as Dueling Bandits (2022-04-21T00:00:00.000000Z)

TL;DR

This work frames the problem of finding best items as a dueling bandits problem, and simulates selected algorithms on representative test cases to provide insight into their practical utility, suggesting modifications to further improve its performance.

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.

References44 items

Overview of the TREC 2021 Deep Learning Track

Preferences on a Budget: Prioritizing Document Pairs when Crowdsourcing Relevance Judgments

Shallow pooling for sparse labels

Evaluation Measures Based on Preference Graphs

MS MARCO: Benchmarking Ranking Models in the Large-Data Regime

Towards Meaningful Statements in IR Evaluation: Mapping Evaluation Measures to Interval Scales

Good Evaluation Measures based on Document Preferences

Preference-based Evaluation Metrics for Web Image Search

Assessing Top- Preferences

The Sample Complexity of Best-k Items Selection from Pairwise Comparisons

Bandit Algorithms in Information Retrieval

MergeDTS

Pairwise Crowd Judgments: Preference, Absolute, and Ratio

Efficient Mechanisms for Peer Grading and Dueling Bandits

Preference-based Online Learning with Dueling Bandits: A Survey

A System for Efficient High-Recall Retrieval

On Fine-Grained Relevance Scales

Maximum Selection and Ranking under Noisy Comparisons

Low-Cost Preference Judgment via Ties

On Crowdsourcing Relevance Magnitudes for Information Retrieval Evaluation

Double Thompson Sampling for Dueling Bandits

Feeling lucky?: multi-armed bandits for ordering judgements in pooling-based evaluation

Document Comprehensiveness and User Preferences in Novelty Search Tasks

Copeland Dueling Bandits

MergeRUCB: A Method for Large-Scale Online Ranker Evaluation

Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem

Information Retrieval for E-Discovery

Almost Optimal Exploration in Multi-Armed Bandits

The K-armed Dueling Bandits Problem

Beat the Mean Bandit

Empirical justification of the gain and discount function for nDCG

On information retrieval metrics designed for evaluation with incomplete relevance assessments

Evaluation measures for preference judgments

Retrieval evaluation with incomplete information

Measuring Retrieval Effectiveness Based on User Preference of Documents

Determining the effectiveness of retrieval algorithms

Overview of TREC 2021

On the effect of relevance scales in crowdsourcing relevance assessments for Information Retrieval evaluation

Newnailsforoldhammers:AnseriniandPyseriniatTREC2021

Maxing and Ranking with Few Assumptions

Alon Orlitsky, Venkatadheeraj Pichapati, and Vaishakh Ravindrakumar

The simple scalability of documents

Equality tolerance: The algorithm must gracefully handle cases where values of Δ 𝑖,𝑗 are close or equal to zero

Human Preferences as Dueling Bandits search