%0 Conference Paper %1 citeulike:14333284 %A Kveton, Branislav %A Szepesvári, Csaba %A Wen, Zheng %A Ashkan, Azin %B Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37 %D 2015 %I JMLR.org %K click-model social-search %P 767--776 %T Cascading Bandits: Learning to Rank in the Cascade Model %U http://portal.acm.org/citation.cfm?id=3045201 %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 Cascade KL-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 Cascade KL-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.

@inproceedings{citeulike:14333284, 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 Cascade KL-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 Cascade KL-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.}}, added-at = {2017-11-15T17:02:25.000+0100}, author = {Kveton, Branislav and Szepesv\'{a}ri, Csaba and Wen, Zheng and Ashkan, Azin}, biburl = {https://www.bibsonomy.org/bibtex/2d11afa887ecf6f221cb229d89a103b9f/brusilovsky}, booktitle = {Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37}, citeulike-article-id = {14333284}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=3045201}, interhash = {784fc83fc72ee31efdf48472533e400e}, intrahash = {d11afa887ecf6f221cb229d89a103b9f}, keywords = {click-model social-search}, location = {Lille, France}, pages = {767--776}, posted-at = {2017-04-07 04:55:28}, priority = {2}, publisher = {JMLR.org}, series = {ICML'15}, timestamp = {2020-03-05T22:25:22.000+0100}, title = {{Cascading Bandits: Learning to Rank in the Cascade Model}}, url = {http://portal.acm.org/citation.cfm?id=3045201}, year = 2015 }