Multiple-Play Bandits in the Position-Based Model
Sequentially learning to place items in multi-position displays or lists is a task that can be cast into the multiple-play semi-bandit setting. However, a major concern in this context is when the system cannot decide whether the user feedback for each item is actually exploitable. Indeed, much of the content may have been simply ignored by the user. The present work proposes to exploit available information regarding the display position bias under the so-called Position-based click model (PBM). We first discuss how this model differs from the Cascade model and its variants considered in several recent works on multiple-play bandits. We then provide a novel regret lower bound for this model as well as computationally efficient algorithms that display good empirical and theoretical performance.
This paper studies a variant of the multi-armed bandit problem in the multi-position setting, that is when the learner is allowed to select a list of L actions - as opposed to a single action - to be displayed to an incoming user. In the variant that is considered, the user is not assumed to scan the list of selected actions entirely, rather it examines item in position l of the list with some unknown probability \kappa_l. Now, rewards are classically defined as Bernoulli random variables with unknown mean parameter.   In this novel setting that extends pervious works on ranking bandits, the authors provide a lower bound (Theorem 6) for this problem. In Section 4, two algorithms are introduced whose regrets are provided in Theorem 9 and Theorem 11, respectively. In Section 5, these algorithms are compared against two other algorithms directly inspired from the bandit literatute, both on simulated and real data sets. 
I have read the feedback from the authors, and maintain my score.  This is a strong paper, with a solid motivation, a well-grounded theoretical analysis, algorithmic contribution, and numerical experiments.  The setting is very natural and makes a lot of sense, as it focuses on a key feature of recommender systems little addressed in the literature: namely the examination probability.  The censored Bernoulli reward model does not reduce trivially to previous settings, and the paper is written in a clear way, with intuition given about contribution. It could be perhaps useful to provide similar intuitions in the appendix in the derivations of each result, as it is not always clear what is the role of each step/intermediate result.   Question: Theorem 9:  It may be useful to provide further intuition about the term C(\kappa): why it appears, exampel of scaling etc.  Algorithm 1: The choice of a probability 1/2 of choosing between \cal B() and \cal L_L(t) looks a bit arbitrary. Also, one would naturally consider that if \kappa is known, a more natural choice could depend on \kappa.  In Theorem 11, do you think one could improve on the "\kappa_L" factor that looks not needed when compared with the lower bound? Do you think playing on the 1/2 probability could help remove/reduce this factor?  The most important critic one can make regarding the contribution is that the \kappa vector is assumed to be perfectly known.  At the top of page 3, this assumption is discussed, and is essentially convincing. However, a natural question that is not addressed here is the effect of having only an approximate knowledge of \kappa to the final regret (Say, it is known up to some error epsilon in infinite or L2 norm).  Another point is when \kappa depends on the user and a user is not observed a lot, or when it depends on the user class but the class is unknown and must be estimated. In these cases, one may want to be able to estimate \kappa while solving the bandit problem. This is however not discussed. Can you give some insights about the main difficulties in order to handle such a case (beyond the identification problem of the B(\kappa_l\theta_k)) model ?    Minor comments: P.5, L. 182:  the letter "delta" is very often used as a confidence level in [0,1]. I thus advise you use a different letter here  for clarity. P.5,L.176 : "an simpler" P6., Algo 1: "\cal L_l(t)" is undefined. I guess this is the l-th component of \cal L(t).   ///////   Technical Quality: Good. The assumption that \kappa is perfectly may not always be a desirable assumption. Novelty/Originality: Good. Potential impact or usefulness: Very good. Clarity and presentation: Very good.