Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions
Recent work on deriving O(log T ) anytime regret bounds for stochastic dueling bandit problems has considered mostly Condorcet winners, which do not always exist, and more recently, winners defined by the Copeland set, which do always exist. In this work, we consider a broad notion of winners defined by tournament solutions in social choice theory, which include the Copeland set as a special case but also include several other notions of winners such as the top cycle, uncovered set, and Banks set, and which, like the Copeland set, always exist. We develop a family of UCB-style dueling bandit algorithms for such general tournament solutions, and show O(log T ) anytime regret bounds for them. Experiments confirm the ability of our algorithms to achieve low regret relative to the target winning set of interest.
This paper deals with the dueling bandit problem in situations where the goal is to find other notions of winners than the Condorcet one (which is not guaranteed to exist) or the Copeland one (which does always exist, but has certain flaws). Unlike the MAB problem, the question of what constitutes the best arm(s) is not completely straightforward to answer in the dueling setting, in particular when there is no single arm that is preferred to all other arms (aka the Condorcet winner).  Indeed, the field of social choice theory has devised a near infinite supply of such notions of winners: the reason for this overabundance of definitions is that in the absence of a Condorcet winner, it is difficult to find a definition that satisfies all reasonable properties that one might hope for, so various definitions have been proposed that satisfy various sets of desirable properties. Given that, it is natural to seek algorithms that can find these other winners, since depending on the application domain, it might very well be that the Condorcet winner does not exist and that the Copeland winner is undesirable.  With this in mind, the authors propose a flexible algorithm that is capable of accommodating such needs, given certain rather weak assumptions on the sought after notion of winner. In plain terms, the algorithm can find solution concepts that are stable with respect to optimistic estimates of the underlying preference matrix. This result can be seen as a refinement of the ideas in reference [3] in the paper. The main difference is that while the SAVAGE algorithm in [3] was restricted to the finite horizon setting, the algorithm in this paper does not need knowledge of the horizon of the experiment in advance.  Moreover, the authors conduct experiments on three examples comparing their algorithm adapted to three specific notions of winners against three existing algorithms, although the description of the experiments is lacking in some important details. First of all, it is unclear whether the comparison is being carried out against the Condorcet or the Copeland version of SAVAGE, and if the former is the case, why was there no comparison against Copeland SAVAGE? Secondly, I do not understand how RUCB could have sublinear regret on the Sushi and MSLR examples, since it crucially assumes the existence of a Condorcet winner, which is absent in those examples. Finally, it is rather disappointing that the authors do not compare against the state of the art duleing bandit algorithm(s) in the Condorcet case, proposed in reference [9] in the paper. 
Overall, the theoretical/algorithmic portions of the paper are written reasonably clearly and the arguments seem correct to me. On the issue of novelty, the domain into which the paper is venturing is relatively novel, but the proofs techniques are not extremely original, although there is definitely value in using existing ideas to solve a new problem.  There are also some issues with the experiments (as I mentioned above), so I urge the authors to revisit that portion of the paper.