Online Rank Elicitation for Plackett-Luce: A Dueling Bandits Approach
We study the problem of online rank elicitation, assuming that rankings of a set of alternatives obey the Plackett-Luce distribution. Following the setting of the dueling bandits problem, the learner is allowed to query pairwise comparisons between alternatives, i.e., to sample pairwise marginals of the distribution in an online fashion. Using this information, the learner seeks to reliably predict the most probable ranking (or top-alternative). Our approach is based on constructing a surrogate probability distribution over rankings based on a sorting procedure, for which the pairwise marginals provably coincide with the marginals of the PlackettLuce distribution. In addition to a formal performance and complexity analysis, we present first experimental studies.
In the setting of dueling bandits and under the PL model assumption, the authors consider two tasks: finding an approximate best arm and finding an approximate ranking of the arms. Both tasks relates to the estimations of the pairwise marginals of the underlying PL model, which is done with an early-stopped version of the QuickSort. This Budgeted QuickSort allows to build algorithms which sample complexity is O(M log^2 M). Experiments compare the sample complexity of the proposed algorithms against state-of-art methods.The problem is not well-motivated, which is even more visible by the lack of experiments based on real-world dataset. This been said, I like the algorithms for their simplicity and the theoretical study that support them is correct. I didn't check proofs in appendix, but the results seems realistic. I would have appreciated a little discussion about the choice of the method to build confidence intervals in PLPAC -- e.g. is the algorithm sensitive to the method ?The paper is correctly organized and reasonably easy to follow. I still find a bit curious to put an algorithm (AMPR-PLPAC) in supplementary material.As I was saying, the problem is not well-motivated but the gain in terms of sample conplexity over existing algorithms is significant.