- MergeRUCB: A method for large-scale online ranker evaluation
- WSDM 2015: The Eighth International Conference on Web Search and Data Mining
- Book/source title
- WSDM'15: proceedings of the Eighth ACM International Conference on Web Search and Data Mining: Jan. 31-Feb. 6, 2015, Shanghai, China
- Pages (from-to)
- New York, NY: Association for Computing Machinery
- Document type
- Conference contribution
- Faculty of Science (FNWI)
- Informatics Institute (IVI)
A key challenge in information retrieval is that of on-line ranker evaluation: determining which one of a finite set of rankers performs the best in expectation on the basis of user clicks on presented document lists. When the presented lists are constructed using interleaved comparison methods, which interleave lists proposed by two different candidate rankers, then the problem of minimizing the total regret accumulated while evaluating the rankers can be formalized as a K-armed dueling bandit problem. In the setting of web search, the number of rankers under consideration may be large. Scaling effectively in the presence of so many rankers is a key challenge not adequately addressed by existing algorithms.
We propose a new method, which we call mergeRUCB, that uses "localized" comparisons to provide the first provably scalable K-armed dueling bandit algorithm. Empirical comparisons on several large learning to rank datasets show that mergeRUCB can substantially outperform the state of the art K-armed dueling bandit algorithms when many rankers must be compared. Moreover, we provide theoretical guarantees demonstrating the soundness of our algorithm.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.