Multi-dueling bandits and their application to online ranker evaluation
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Multi-dueling bandits and their application to online ranker evaluation. / Brost, Brian; Seldin, Yevgeny; Cox, Ingemar Johansson; Lioma, Christina.
Proceedings of the 25th ACM International Conference on Information and Knowledge Management. Association for Computing Machinery, 2016. s. 2161-2166 (ACM International Conference on Information and Knowledge Management).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Multi-dueling bandits and their application to online ranker evaluation
AU - Brost, Brian
AU - Seldin, Yevgeny
AU - Cox, Ingemar Johansson
AU - Lioma, Christina
N1 - Conference code: 25
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - cs.IR
KW - cs.LG
KW - stat.ML
U2 - 10.1145/2983323.2983659
DO - 10.1145/2983323.2983659
M3 - Article in proceedings
T3 - ACM International Conference on Information and Knowledge Management
SP - 2161
EP - 2166
BT - Proceedings of the 25th ACM International Conference on Information and Knowledge Management
PB - Association for Computing Machinery
Y2 - 24 October 2016 through 28 October 2016
ER -
ID: 167579172