The K-armed Dueling Bandits Problem

By Yisong Yue, Josef Broder, Robert D. Kleinberg, Thorsten Joachims. 2012

454 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Direct Preference Optimization: Your Language Model is Secretly a Reward Model (2023, background): “Contextual bandit learning using preferences or rankings of actions, rather than rewards, is known as a contextual dueling bandit (CDB; [47, 14]).”
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): “In other words, prior to choosing its actions, the learner is allowed to observe some value x , the context, selected by Nature from some unspeciﬁed space X .”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “An interesting variation of stochastic bandits was recently studied by Yue et al. [2009]. The model considered in that paper is called dueling bandits.”
Interactive machine learning for health informatics: when do we need the human-in-the-loop? (2016, methodology): “In their work, they applied the bandits problem [77].”
Relative confidence sampling for efficient on-line ranker evaluation (2014, methodology): “501 so that RUCB’s theoretical guarantees [38] hold.”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, background): “Dueling bandits [33, 10] is essentially the one-state version of PbRL, and has been extensively studied in the literature [34, 17, 16, 32].”
Preference-based Evolutionary Direct Policy Search (2013, background): “[31] introduced a multi-armed bandit setup where feedback is provided in the form of pairwise comparisons between options, just like in our approach.”
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)).”
Beat the Mean Bandit (2011, methodology): “The K-armed Dueling Bandits Problem (Yue et al., 2009) is an iterative learning problem on a set of bandits B = {b 1 , . . . , b K } (also called arms or strategies).”
PAC Battling Bandits in the Plackett-Luce Model (2018, background): “The dueling bandit problem has recently gained attention in the machine learning community (Yue et al., 2012; Ailon et al., 2014; Zoghi et al., 2014; Sz¨or´enyi et al., 2015).”
Reducing Dueling Bandits to Cardinal Bandits (2014, methodology): “While specific algorithms for specific cases of the Dueling Bandits problem already exist (Yue et al., 2012; Yue & Joachims, 2011; 2009), our reductions provide a general approach to solving the UBDB.”
Dueling Posterior Sampling for Preference-Based Reinforcement Learning (2019, methodology): “Compared to the preferencebased bandit setting, which has seen significant theoretical progress (Yue et al., 2012; Dudík et al., 2015; Wu & Liu, 2016; Sui et al., 2017; 2018b), one major challenge is how to address credit assignment when only receiving feedback at the trajectory level compared to th”
Generic Exploration and K-armed Voting Bandits (2013, methodology): “The exploration time at horizon T with δ “ 1{T provides an upper bound for the expected cumulative regret (see Yue et al., 2012, section 4).”
Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (2023, background): “The theoretical understanding of RLHF can be traced back to research on dueling bandits (e.g., Yue et al., 2012; Saha, 2021; Bengs et al., 2021 is that instead of optimizing against an external preference oracle, they adopt a clever idea by using the LLM itself as the reward model to provide…”
Graph Resistance and Learning from Pairwise Comparisons (2019, background): “For example, the papers (Yue et al., 2012; Szörényi et al., 2015) considered the online version of this problem with corresponding regret, (Chen & Suh, 2015) considered recovering the top K ranked items, (Falahatgar et al.”