Double Thompson Sampling for Dueling Bandits
In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for dueling bandit problems. As its name suggests, D-TS selects both the first and the second candidates according to Thompson Sampling. Specifically, D-TS maintains a posterior distribution for the preference matrix, and chooses the pair of arms for comparison according to two sets of samples independently drawn from the posterior distribution. This simple algorithm applies to general Copeland dueling bandits, including Condorcet dueling bandits as a special case. For general Copeland dueling bandits, we show that D-TS achieves O(K 2 log T ) regret. Moreover, using a back substitution argument, we refine the regret to O(K log T + K 2 log log T ) in Condorcet dueling bandits and most practical Copeland dueling bandits. In addition, we propose an enhancement of D-TS, referred to as D-TS + , to reduce the regret in practice by carefully breaking ties. Experiments based on both synthetic and real-world data demonstrate that D-TS and D-TS + significantly improve the overall performance, in terms of regret and robustness.
The paper develops Thompson-sampling style algorithms for the interesting and relevant problem of dueling bandits, where the best arm has to  be learnt using only pairwise preference feedback. The key idea in the main algorithm is to sample twice, and independently, the unknown model from the posterior distribution over models, and essentially pit the best arms for both models against each other. This has the advantage of promoting exploration in early phases and converging to playing the optimal arm against itself in later phases. The authors derive detailed regret bounds for the algorithm for both the Condorcet winner and the more general Copeland winner ground truth models, and perform numerical comparisons of the proposed algorithm with existing, Upper-Confidence-Bound (UCB) style strategies. 
EDIT: I have read the author response.  The paper takes on the challenging task of adapting Thompson sampling-style Bayesian-inspired approaches to the dueling bandit problem, and thus I feel that its contributions are significant. The dueling bandit problem, being a true partial monitoring problem (not all actions give nonzero statistical information), is in a sense harder than standard bandits, and hence requires more care in designing the exploration-exploration tradeoff. Although this is not the first time Thompson sampling has been proposed for the problem (e.g., RCS is an earlier attempt), the smart idea of sampling twice and following it up by a UCB-elimination step is quite novel, and supplemented by fairly competitive analytical guarantees. I believe this would open up paths for more in-depth looks at Thompson sampling approaches to solve classes of dueling bandit problems.   Detailed comments and observations are as follows.   *    Without the Condorcet winner assumption, the algorithm is shown to give a O(K^2logT) regret bound, where as the CCB algorithm of Zoghi et al. gives O(K^2 + KlogT) regret, and SCB gives an even better regret bound of O(KlogKlogT) with certain restrictive assumptions.  Yet, in the experiments, these algorithms seem to be performing quite poorly w.r.t. the proposed algorithm which is counter intuitive, even for 500-armed case D-TS seems to be performing better than CCB/SCB (Fig. 4(d)). Could the authors suggest an explanation for this observation?  * Comparing with existing algorithms with different notions of regret for the dueling bandit problem: Are the regret definitions used in this paper directly comparable to that of some of the existing dueling bandit algorithms (e.g. RUCB, Merge-RUCB, RMED, specially those which are based on Condorcet winner assumptions)? It seems that the notion of regret used in this paper is not directly reducible to that used in these other papers with a Condorcet winner assumption.  * One wonders how the regret performance gets affected if one just uses double Thompson sampling for pulling the two arms (a^(1) and a^(2) in Algorithm 1) from the whole set of K arms, instead of selecting them from the restricted set as described in line 11 and 14 of Algorithm 1. In other words, how much significant is the restrictive sampling (that is used for pulling the pair of arms) in terms of bounding the regret?   * Experiments:                  -It might be worth comparing how the algorithm's performance scales w.r.t. other algorithms, e.g. Merge-RUCB, CCB/SCB etc. with increasing K.   -It might also be worth comparing different algorithms with certain other class of pairwise preference matrices, e.g. pairwise preferences with a Borda winner, with total ordering, or preferences generated from random utility model etc.   - It is not clear why ECW-RMED has higher standard deviations of regret in comparison to the proposed method since in the later case both the arms are sampled from some posterior distribution.