TopRank: A Practical Algorithm for Online Stochastic Ranking
Online learning to rank is a sequential decision-making problem where in each round the learning agent chooses a list of items and receives feedback in the form of clicks from the user. Many sample-efficient algorithms have been proposed for this problem that assume a specific click model connecting rankings and user behavior. We propose a generalized click model that encompasses many existing models, including the position-based and cascade models. Our generalization motivates a novel online learning algorithm based on topological sort, which we call TopRank. TopRank is (a) more natural than existing algorithms, (b) has stronger regret guarantees than existing algorithms with comparable generality, (c) has a more insightful proof that leaves the door open to many generalizations, and (d) outperforms existing algorithms empirically.
This paper tackles the problem of learning to rank items in the online setting. This paper proposes a new algorithm that uses confidence intervals on items preferences ordering in order to decide which item to assign to each position. Results show that the proposed approach empirically outperforms the current state-of-the-art in the re-ranking setting. The paper also provides an upper bound on the regret for the proposed approach, and a lower bound on the regret in ranking problems.   Quality:  I found the paper of overall good quality. Considering that there is some space left at the end, the paper could benefit from some more details to backup its claims:  The abstract (line 8) claims that the proposed approach is "more natural than existing algorithms". Though I agree that this approach feels natural, other models are not discussed here. This makes it difficult to judge of how natural (or not) they are compared in comparison.  The abstract (lines 8-9) and conclusion (line 241) claim that the proposed algorithm "enjoys stronger regret guarantees" than existing models, but the bounds of other algorithms are not reported nor discussed. How does the theoretical result of Thm. 1 compare with the bounds of other models (e.g. CascadeUCB, BatchRank)?   Clarity:  The paper reads well.  It would be good to remind the reader what are K and L at the beginning of Sec. 2.  Figures used to illustrate the model (in Sec. 3) and the algorithm (in Sec. 4) do not have a caption. I understand that this was meant to save space and/or alleviate the general presentation but there is empty space at the end of the paper.  Nitpicking: - Reference [22] is a duplicate of [21].   Originality:  This work addresses an existing problem with a novel approach. The proposed algorithm is intuitive and compares really well to the state of art.  The consfidence intervals in Lem. 6 hold simultaneously for all times, which could be interesting for further analysis.  Thm. 2 appears to be the first lower bound obtained by unifying different existing results.   Significance:  While the paper does not address a new problem, the learning to (re-)rank problem is still of interest for many people. The proposed algorithm empirically outperforms existing approaches, it would become one of the state-of-the-art baselines to consider. However, the significance of its regret upper bound (Thm. 1) is hard to evaluate without comparison with similar results of existing models. Thm. 2, on the other hand, might be the only current regret lower bound instance in the ranking problem.