Copeland Dueling Bandits

By Masrour Zoghi, Zohar S. Karnin, Shimon Whiteson, Maarten de Rijke. 2015

100 citations recorded by the source corpus.

A version of the dueling bandit problem is addressed 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 guaranteed 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(K2 log T) without requiring such assumptions. Our results offer the best of both worlds: O (K log T) bounds without restrictive assumptions.

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

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Over the last two decades the problem of learning from preference feedback in bandits, known as dueling bandits, has gained much attention (Yue et al., 2012; Zoghi et al., 2014b, 2015).”
Contextual Dueling Bandits (2015, background): “…2011); Sensitivity Analysis of VAriables for Generic Exploration (SAVAGE) (Urvoy et al., 2013); Relative Conﬁdence Sampling (Zoghi et al., 2014a); Relative Upper Conﬁdence Bound (RUCB) (Zoghi et al., 2014b); Doubler, MultiSBM and Sparring (Ailon et al., 2014) and mergeRUCB (Zoghi et al., 2015).”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “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.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “Beyond ﬁxed-benchmark regret, notions involving Borda [Busa-Fekete and Hüllermeier, 2014; Jamieson et al., 2015; Falahatgar et al., 2017] and Copeland scores [Zoghi et al., 2015a; Komiyama et al., 2016; Wu and Liu, 2016] have also been considered.”
MergeDTS (2018, background): “Instead, the dataset contains two Copeland winners and this dueling bandit setup is called the Copeland dueling bandit [47, 53].”
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, background): “Several algorithms have been proposed for this problem which are designed to learn to play the best arm as often as possible over time [22, 4, 24, 25, 23, 16].”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “The algorithm then samples θ(1)ij (t) from the posterior beta distribution, and the first candidate a(1)t is chosen by “majority voting”, i.e., the arm within Ct that beats the most arms according to θ(1)ij (t) will be selected (Lines 7 to 11).”
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.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “…gradient descent (Zhao and King, 2016) Stochastic mirror descent (Kumagai, 2017) Voting bandits (Urvoy et al., 2013) Copeland conﬁdence bound (Zoghi et al., 2015a) Copeland winners relative minimum empirical divergence (Komiyama et al., 2016) Double Thompson sampling (Wu and Liu, 2016)…”