%0 Conference Paper %1 KKSzw16:DCM %A Katariya, S. %A Kveton, B. %A Szepesvári, Cs. %A Wen, Z. %B ICML %D 2016 %K bandits, cascading information, learning, multiclick nonlinear online partial stochastic theory, %P 1215--1224 %T DCM Bandits: Learning to Rank with Multiple Clicks %X Search engines recommend a list of web pages. The user examines this list, from the first page to the last, and may click on multiple attractive pages. This type of user behavior can be modeled by the dependent click model (DCM). In this work, we propose DCM bandits, an online learning variant of the DCM model where the objective is to maximize the probability of recommending a satisfactory item. The main challenge of our problem is that the learning agent does not observe the reward. It only observes the clicks. This imbalance between the feedback and rewards makes our setting challenging. We propose a computationally-efficient learning algorithm for our problem, which we call dcmKL-UCB; derive gap-dependent upper bounds on its regret under reasonable assumptions; and prove a matching lower bound up to logarithmic factors. We experiment with dcmKL-UCB on both synthetic and real-world problems. Our algorithm outperforms a range of baselines and performs well even when our modeling assumptions are violated. To the best of our knowledge, this is the first regret-optimal online learning algorithm for learning to rank with multiple clicks in a cascade-like model.

@inproceedings{KKSzw16:DCM, abstract = {Search engines recommend a list of web pages. The user examines this list, from the first page to the last, and may click on multiple attractive pages. This type of user behavior can be modeled by the dependent click model (DCM). In this work, we propose DCM bandits, an online learning variant of the DCM model where the objective is to maximize the probability of recommending a satisfactory item. The main challenge of our problem is that the learning agent does not observe the reward. It only observes the clicks. This imbalance between the feedback and rewards makes our setting challenging. We propose a computationally-efficient learning algorithm for our problem, which we call dcmKL-UCB; derive gap-dependent upper bounds on its regret under reasonable assumptions; and prove a matching lower bound up to logarithmic factors. We experiment with dcmKL-UCB on both synthetic and real-world problems. Our algorithm outperforms a range of baselines and performs well even when our modeling assumptions are violated. To the best of our knowledge, this is the first regret-optimal online learning algorithm for learning to rank with multiple clicks in a cascade-like model. }, added-at = {2020-03-17T03:03:01.000+0100}, author = {Katariya, S. and Kveton, B. and Szepesv{\'a}ri, {Cs}. and Wen, Z.}, biburl = {https://www.bibsonomy.org/bibtex/2c9cd7fb29e2a27ed8dc47e6a0c4bb84b/csaba}, booktitle = {ICML}, date-added = {2016-05-09 08:26:00 +0000}, date-modified = {2016-07-29 14:17:51 +0000}, interhash = {4eec36ba1c7f8c914b830ce99cb9ec49}, intrahash = {c9cd7fb29e2a27ed8dc47e6a0c4bb84b}, keywords = {bandits, cascading information, learning, multiclick nonlinear online partial stochastic theory,}, pages = {1215--1224}, pdf = {papers/ICML16-DCMBandits.pdf}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {DCM Bandits: Learning to Rank with Multiple Clicks}, year = 2016 }