Exploiting Transitivity for Top-k Selection with Score-Based Dueling Bandits
This work provides a more efficient method for top-k selection in dueling bandit problems for researchers and practitioners dealing with pairwise ranking data that includes quantitative scores and exhibits transitivity.
This paper addresses top-k subset selection in Dueling Bandit problems by introducing a Thurstonian-style model that leverages transitivity in pairwise rankings, specifically when sampling outcomes provide quantitative information. They adapt the POCBAm sampling method to utilize this model, demonstrating improved empirical performance compared to standard POCBAm and other algorithms.
We consider the problem of top-k subset selection in Dueling Bandit problems with score information. Real-world pairwise ranking problems often exhibit a high degree of transitivity and prior work has suggested sampling methods that exploit such transitivity through the use of parametric preference models like the Bradley-Terry-Luce (BTL) and Thurstone models. To date, this work has focused on cases where sample outcomes are win/loss binary responses. We extend this to selection problems where sampling results contain quantitative information by proposing a Thurstonian style model and adapting the Pairwise Optimal Computing Budget Allocation for subset selection (POCBAm) sampling method to exploit this model for efficient sample selection. We compare the empirical performance against standard POCBAm and other competing algorithms.