Preference-based Online Learning with Dueling Bandits: A Survey

By Róbert Istvan Busa-Fekete, Eyke Hüllermeier, Adil El Mesaoudi-Paul. 2018

149 citations recorded by the source corpus.

In machine learning, the notion of multi-armed bandits refers to a class of online learning problems, in which an agent is supposed to simultaneously explore and exploit a given set of choice alternatives in the course of a sequential decision process. In the standard setting, the agent learns from stochastic feedback in the form of real-valued rewards. In many applications, however, numerical reward signals are not readily available -- instead, only weaker information is provided, in particular relative preferences in the form of qualitative comparisons between pairs of alternatives. This observation has motivated the study of variants of the multi-armed bandit problem, in which more general representations are used both for the type of feedback to learn from and the target of prediction. The aim of this paper is to provide a survey of the state of the art in this field, referred to as preference-based multi-armed bandits or dueling bandits. To this end, we provide an overview of problems that have been considered in the literature as well as methods for tackling them. Our taxonomy is mainly based on the assumptions made by these methods about the data-generating process and, related to this, the properties of the preference-based feedback.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical Learning Theory

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

In Statistical Learning Theory

Citations in the corpus

MergeDTS (2018, background): “…p ji = 1 − p ij . form the entries of a K × K preference matrix P , which defines the dueling bandit problem but is cumulative regret , which is the total loss incurred by choosing suboptimal arms over time [5, 42]. arms, i.e., an arm a C , called the Condorcet winner , such that p Cj > 0 .”
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].”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “We adopt algorithms from the stochastic088 dueling bandits literature (Bengs et al., 2021) to089 decide which pair of NLG systems to compare at090 each time step.”
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…”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “Note both representations are equivalent as there exists a one to one mapping P = (2Q − 1) ∈ P [Dudík et al., 2015; Bengs et al., 2021]”