Multi-Dueling Bandits and Their Application to Online Ranker Evaluation
  New ranking algorithms are continually being developed and refined,
necessitating the development of efficient methods for evaluating these
rankers. Online ranker evaluation focuses on the challenge of efficiently
determining, from implicit user feedback, which ranker out of a finite set of
rankers is the best. Online ranker evaluation can be modeled by dueling ban-
dits, a mathematical model for online learning under limited feedback from
pairwise comparisons. Comparisons of pairs of rankers is performed by
interleaving their result sets and examining which documents users click on.
The dueling bandits model addresses the key issue of which pair of rankers to
compare at each iteration, thereby providing a solution to the
exploration-exploitation trade-off. Recently, methods for simultaneously
comparing more than two rankers have been developed. However, the question of
which rankers to compare at each iteration was left open. We address this
question by proposing a generalization of the dueling bandits model that uses
simultaneous comparisons of an unrestricted number of rankers. We evaluate our
algorithm on synthetic data and several standard large-scale online ranker
evaluation datasets. Our experimental results show that the algorithm yields
orders of magnitude improvement in performance compared to stateof- the-art
dueling bandit algorithms.
