Double Thompson Sampling for Dueling Bandits

By Huasen Wu, Xin Liu. 2016

103 citations recorded by the source corpus.

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.

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Human Preferences as Dueling Bandits (2022, positive): “the DTS algorithm for further consideration because experiments have shown that DTS outperforms the other two [34].”
Dueling Posterior Sampling for Preference-Based Reinforcement Learning (2019, background): “The bandit setting (Yue et al., 2012; Zoghi et al., 2014; Ailon et al., 2014; Szörényi et al., 2015; Dudı́k et al., 2015; Zoghi et al., 2015; Ramamohan et al., 2016; Wu and Liu, 2016; Sui et al., 2017, 2018b) is closest, as it is essentially a single-state variant of RL.”
MergeDTS (2018, methodology): “Furthermore, to answer RQ5, we use the MSLR-non-Condorcet dataset from [47], which is a subset of the MSLR dataset that does not contain a Condorcet winner.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “…last two decades, several algorithms have been proposed for dueling bandit problems [Ailon et al., 2014; Zoghi et al., 2014; Komiyama et al., 2015; Wu and Liu, 2016] and generalizations to subset-wise preference feedback [Sui et al., 2017; Brost et al., 2016; Saha and Gopalan, 2019a; Ren et al.,…”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, background): “Most others (Zoghi et al., 2014b,a; Komiyama et al., 2015; Zoghi et al., 2015; Wu and Liu, 2016) focus on information retrieval applications that involve evaluating search retrieval algorithms (Radlinski et al.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “…conﬁdence bound (Zoghi et al., 2015a) Copeland winners relative minimum empirical divergence (Komiyama et al., 2016) Double Thompson sampling (Wu and Liu, 2016) Sparse Sparring (Balsubramani et al., 2016) Generic tournament solutions (Ramamohan et al., 2016) Active ranking (Heckel et al.,…”
Optimal Algorithms for Stochastic Contextual Preference Bandits (2021, background): “Above notion of learner’s regret is motivated from the definition of classical K-armed dueling bandit regret introduced by [44] which is later adopted by the dueling bandit literature [46, 23, 3, 43, 45, 38, 31].”
Battle of Bandits (2018, methodology): “3) with Double-Thompson Sampling [21] as the DBM D.”