Double Thompson Sampling for Dueling Bandits
  In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for
dueling bandit problems. As indicated by its name, 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 by sampling twice from the posterior distribution.
This simple algorithm applies to general Copeland dueling bandits, including
Condorcet dueling bandits as its special case. For general Copeland dueling
bandits, we show that D-TS achieves $O(K^2 \log T)$ regret. For Condorcet
dueling bandits, we further simplify the D-TS algorithm and show that the
simplified D-TS algorithm achieves $O(K \log T + K^2 \log \log T)$ regret.
Simulation results based on both synthetic and real-world data demonstrate the
efficiency of the proposed D-TS algorithm.
