Our NIPS 2015 paper “Copeland Dueling Bandits” by Masrour Zoghi, Zohar Karnin, Shimon Whiteson and Maarten de Rijke is available online now:

  • Masrour Zoghi, Shimon Whiteson, Zohar Karnin, and Maarten de Rijke. Copeland dueling bandits. In NIPS 2015, page 307–315, December 2015. Bibtex, PDF
    author = {Zoghi, Masrour and Whiteson, Shimon and Karnin, Zohar and de Rijke, Maarten},
    booktitle = {NIPS 2015},
    date-added = {2015-09-04 16:45:01 +0000},
    date-modified = {2017-02-18 15:22:54 +0000},
    month = {December},
    pages = {307--315},
    title = {Copeland dueling bandits},
    year = {2015}}

In the paper we address a version of the dueling bandit problem 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 guar- anteed 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.