Cascading Bandits: Learning to Rank in the Cascade Model

Branislav Kveton, Csaba Szepesvari, Zheng Wen, Azin Ashkan
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:767-776, 2015.

Abstract

A search engine usually outputs a list of K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify K most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-kveton15, title = {Cascading Bandits: Learning to Rank in the Cascade Model}, author = {Kveton, Branislav and Szepesvari, Csaba and Wen, Zheng and Ashkan, Azin}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {767--776}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/kveton15.pdf}, url = {https://proceedings.mlr.press/v37/kveton15.html}, abstract = {A search engine usually outputs a list of K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify K most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.} }
Endnote
%0 Conference Paper %T Cascading Bandits: Learning to Rank in the Cascade Model %A Branislav Kveton %A Csaba Szepesvari %A Zheng Wen %A Azin Ashkan %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-kveton15 %I PMLR %P 767--776 %U https://proceedings.mlr.press/v37/kveton15.html %V 37 %X A search engine usually outputs a list of K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify K most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.
RIS
TY - CPAPER TI - Cascading Bandits: Learning to Rank in the Cascade Model AU - Branislav Kveton AU - Csaba Szepesvari AU - Zheng Wen AU - Azin Ashkan BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-kveton15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 767 EP - 776 L1 - http://proceedings.mlr.press/v37/kveton15.pdf UR - https://proceedings.mlr.press/v37/kveton15.html AB - A search engine usually outputs a list of K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify K most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated. ER -
APA
Kveton, B., Szepesvari, C., Wen, Z. & Ashkan, A.. (2015). Cascading Bandits: Learning to Rank in the Cascade Model. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:767-776 Available from https://proceedings.mlr.press/v37/kveton15.html.

Related Material