Online Learning to Rank in Stochastic Click Models

Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, Zheng Wen
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:4199-4208, 2017.

Abstract

Online learning to rank is a core problem in information retrieval and machine learning. Many provably efficient algorithms have been recently proposed for this problem in specific click models. The click model is a model of how the user interacts with a list of documents. Though these results are significant, their impact on practice is limited, because all proposed algorithms are designed for specific click models and lack convergence guarantees in other models. In this work, we propose BatchRank, the first online learning to rank algorithm for a broad class of click models. The class encompasses two most fundamental click models, the cascade and position-based models. We derive a gap-dependent upper bound on the T-step regret of BatchRank and evaluate it on a range of web search queries. We observe that BatchRank outperforms ranked bandits and is more robust than CascadeKL-UCB, an existing algorithm for the cascade model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-zoghi17a, title = {Online Learning to Rank in Stochastic Click Models}, author = {Masrour Zoghi and Tomas Tunys and Mohammad Ghavamzadeh and Branislav Kveton and Csaba Szepesvari and Zheng Wen}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {4199--4208}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/zoghi17a/zoghi17a.pdf}, url = {https://proceedings.mlr.press/v70/zoghi17a.html}, abstract = {Online learning to rank is a core problem in information retrieval and machine learning. Many provably efficient algorithms have been recently proposed for this problem in specific click models. The click model is a model of how the user interacts with a list of documents. Though these results are significant, their impact on practice is limited, because all proposed algorithms are designed for specific click models and lack convergence guarantees in other models. In this work, we propose BatchRank, the first online learning to rank algorithm for a broad class of click models. The class encompasses two most fundamental click models, the cascade and position-based models. We derive a gap-dependent upper bound on the T-step regret of BatchRank and evaluate it on a range of web search queries. We observe that BatchRank outperforms ranked bandits and is more robust than CascadeKL-UCB, an existing algorithm for the cascade model.} }
Endnote
%0 Conference Paper %T Online Learning to Rank in Stochastic Click Models %A Masrour Zoghi %A Tomas Tunys %A Mohammad Ghavamzadeh %A Branislav Kveton %A Csaba Szepesvari %A Zheng Wen %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-zoghi17a %I PMLR %P 4199--4208 %U https://proceedings.mlr.press/v70/zoghi17a.html %V 70 %X Online learning to rank is a core problem in information retrieval and machine learning. Many provably efficient algorithms have been recently proposed for this problem in specific click models. The click model is a model of how the user interacts with a list of documents. Though these results are significant, their impact on practice is limited, because all proposed algorithms are designed for specific click models and lack convergence guarantees in other models. In this work, we propose BatchRank, the first online learning to rank algorithm for a broad class of click models. The class encompasses two most fundamental click models, the cascade and position-based models. We derive a gap-dependent upper bound on the T-step regret of BatchRank and evaluate it on a range of web search queries. We observe that BatchRank outperforms ranked bandits and is more robust than CascadeKL-UCB, an existing algorithm for the cascade model.
APA
Zoghi, M., Tunys, T., Ghavamzadeh, M., Kveton, B., Szepesvari, C. & Wen, Z.. (2017). Online Learning to Rank in Stochastic Click Models. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:4199-4208 Available from https://proceedings.mlr.press/v70/zoghi17a.html.

Related Material