Copeland Dueling Bandits
A version of the dueling bandit problem is addressed in which a Condorcet winner may not exist. Two algorithms are proposed that instead seek to minimize regret with respect to the Copeland winner, which, unlike the Condorcet winner, is guaranteed to exist. The first, Copeland Confidence Bound (CCB), is designed for small numbers of arms, while the second, Scalable Copeland Bandits (SCB), works better for large-scale problems. We provide theoretical results bounding the regret accumulated by CCB and SCB, both substantially improving existing results. Such existing results either offer bounds of the form O(K log T ) but require restrictive assumptions, or offer bounds of the form O(K 2 log T ) without requiring such assumptions. Our results offer the best of both worlds: O(K log T ) bounds without restrictive assumptions.
This paper tackles the dueling bandits problem, focusing on the scenarios where a Condorcet winner does not exist. In particular it focuses on finding the Copeland winner (i.e., the arm that beats maximal number of other arms) and proposes two algorithms for this task. The paper provides theoretical bounds on these algorithms which indicate better asymptotic regret performance than previous approaches for identifying the Copeland winner.Overall the paper (with the supplementary material) was quite solid in terms of material. However I did have some significant concerns.I wanted to start my critique with the informativeness and "quality" of the actual 9 page material. I recognize that this is a matter of principle to which the authors may object, but in my honest opinion I would like to reward the authors and NIPS submissions that took the extra effort of making a paper self-contained and informative within the 9 page limit, although that may have meant leaving out certain interesting results/analysis/experiments. At the end of the day what gets published is the 9 pager, which is what I believe should be the determining factor of a paper's quality. After all the NIPS guidelines clearly state that I reserve the right to do so:"Note that the reviewers and the program committee reserve the right to judge the paper solely on the basis of the 9 pages of the paper; looking at any extra material is up to the discretion of the reviewers and is not required."With this in mind, I actually find the overall quality and clarity of the 9 pager itself fairly lacking. Most of the interesting analysis and all the other empirical evidence are hidden away in the 20+ page appendix. In fact the overall analysis of the algorithms itself is fairly hard to understand as the 9-pager itself presents it in a rather hard-to-understand manner. Most of the paper constantly makes forward references to the supplementary material to complete the story, though its' purpose is to "supplement" the main content not serve as a continuation of it.Some of the things which I would have liked to see in the actual 9-pager itself would include:a) Significance: Why is this work significant? Lately the work on dueling bandits is becoming increasingly incremental with different approaches improving marginally over the previous on different metrics. So why is the Copeland winner what we should really be interested in as compared to the Borda winner or the von Neumann winner or some yet-to-be-published winner? Because at the end of the day what a practitioner cares about is the method that works best in practice not the specific metric that was used to get to that method. Towards this, I don't really find this paper providing any compelling evidence that the Copeland winner is the right one to aim for.b) (Quality+Significance) Related to the above, but why would Condorcet methods not work well in cases such as this (even though the Condorcet winner may not exist). The authors mention that these methods may fail for these problems, but the 9 pager itself does not contain any evidence (theoretical or empirical) indicating the same.c) (Quality+Clarity) Providing empirical evidence in the main material (even a small study whose setup can be detailed in the appendix) could convince a practitioner to switch such a method. A set of involved hard-to-gauge theoretical results alone do not constitute a compelling enough set of evidence in my opinion.Again while I understand that the authors have addressed some of these criticisms in the supplementary material, I am basing this review on the 9 page material to be fair to all the other papers I review which have relied on me reading just the 9 pages and not a 32 pager.