  A search engine recommends to the user a list of web pages. The user examines
this list, from the first page to the last, and clicks on all attractive pages
until the user is satisfied. This behavior of the user can be described by the
dependent click model (DCM). We propose DCM bandits, an online learning variant
of the DCM where the goal is to maximize the probability of recommending
satisfactory items, such as web pages. The main challenge of our learning
problem is that we do not observe which attractive item is satisfactory. We
propose a computationally-efficient learning algorithm for solving our problem,
dcmKL-UCB; derive gap-dependent upper bounds on its regret under reasonable
assumptions; and also prove a matching lower bound up to logarithmic factors.
We evaluate our algorithm on synthetic and real-world problems, and show that
it performs well even when our model is misspecified. This work presents the
first practical and regret-optimal online algorithm for learning to rank with
multiple clicks in a cascade-like click model.
