Reducing Dueling Bandits to Cardinal Bandits

By Nir Ailon, Zohar S. Karnin, Thorsten Joachims. 2014

157 citations recorded by the source corpus.

We present algorithms for reducing the Dueling Bandits problem to the conventional (stochastic) Multi-Armed Bandits problem. The Dueling Bandits problem is an online model of learning with ordinal feedback of the form "A is preferred to B" (as opposed to cardinal feedback like "A has value 2.5"), giving it wide applicability in learning from implicit user feedback and revealed and stated preferences. In contrast to existing algorithms for the Dueling Bandits problem, our reductions - named Doubler, MultiSBM and Sparring - provide a generic schema for translating the extensive body of known results about conventional Multi-Armed Bandit algorithms to the Dueling Bandits setting. For Doubler and MultiSBM we prove regret upper bounds in both finite and infinite settings, and conjecture about the performance of Sparring which empirically outperforms the other two as well as previous algorithms in our experiments. In addition, we provide the first almost optimal regret bound in terms of second order terms, such as the differences between the values of the arms.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, methodology): “Towards these goals, several algorithms have been proposed (Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019).”
Contextual Dueling Bandits (2015, methodology): “, 2014b); Doubler, MultiSBM and Sparring (Ailon et al., 2014) and mergeRUCB (Zoghi et al.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “In (Ailon et al., 2014b), two reduction techniques are proposed for a ﬁnite and an inﬁnite set of arms.”
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem (2015, methodology): “r the Condorcet assumption as well as the assumption that a portion of the preference matrix is informative (i.e., different from 1/2). They reported that mergeRUCB outperformed RUCBwhen K was large. Ailon et al. (2014) proposed three algorithms named Doubler, MultiSBM, and Sparring. MultiSBM is end”
Copeland Dueling Bandits (2015, result): “Since our results (see §5) establish bounds on the number of queries to non-Copeland winners, they can also be applied to other notions of regret.”
Dueling Posterior Sampling for Preference-Based Reinforcement Learning (2019, background): “is. While the preference-based bandit setting—in which the agent observes preferences between selected actions— has seen signiﬁcant theoretical progress (e.g., Yue et al. (2012); Zoghi et al. (2014); Ailon et al. (2014); Szor¨ enyi´ et al. (2015); Dud´ık et al. (2015); Zoghi et al. (2015); Ramamohan”
Battle of Bandits (2018, methodology): “Note that this model generalizes the linear-link based pairwise feedback model of [4] at k = 2, as for any S = (a, b), the probability Pr(a beats b) = (θa−θb+1)/2 becomes exactly equal to that of [4] used for modeling the dueling bandit feedback.”
Efficient Mechanisms for Peer Grading and Dueling Bandits (2018, background): “…dueling bandit problem has been studied before, previous works seem to focus on minimizing the total number of competitions (see for example Urvoy et al. (2013); Zoghi et al. (2014)) or minimizing some notion of regret (see for example Ailon et al. (2014); Yue et al. (2012); Zoghi et al. (2014)).”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, unknown): “Reduction to value-based MAB[2] Statistical models”
Bandit Algorithms (2020, background): “Anscombe [1963] considered exploration and commitment in the context of medical trials or other experimental setups.”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…comparisons (Yue et al., 2012; Zoghi et al., 2014b; Yue and Joachims, 2009, 2011; Saha and Krishnamurthy, 2022; Ghoshal and Saha, 2022; Saha and Gopalan, 2018a; Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019; Faury et al., 2020).”
Introduction to Multi-Armed Bandits (2019, methodology): “can measure which of the two slates is better in a much more reliable way using an approach called interleaving, see survey (Hofmann et al., 2016) for background. Further work on this model includes (Ailon et al., 2014; Zoghi et al., 2014; Dud´ık et al., 2015). Another model, termed partial monitori”
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].”
MergeDTS (2018, background): “We do not include RUCB [55] and Sparring [1] in our experiments since they have been outperformed by more than one of our baselines [16, 43, 54].”
Towards Conversational Recommender Systems (2016, background): “This can be seen as a variant of the “sparring” approach to dueling bandits [2], which samples item pairs and updates the model for both items as if an absolute reward were observed.”
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits (2022, background): “, 2013) with pairs of items (size-2 subsets) that can be played, and subsequent work on generalization to broader models both in terms of distributional parameters (Yue and Joachims, 2009; Gajane et al., 2015; Ailon et al., 2014; Zoghi et al., 2015) as well as combinatorial subset-wise plays (Mohaje”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “…optimal rate can be achieved here and in other related settings by sparring optimal adversarial bandit algorithms, such as Exp3 [Dudík et al., 2015; Ailon et al., 2014; Gajane et al., 2015; Sui et al., 2017] Unfortunately, all algorithms that achieve the optimal rate rely heavily on adversarial…”