Preference-based Online Learning with Dueling Bandits: A Survey

Abstract

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.

108 pages

References in corpus (13)

• Further Optimal Regret Bounds for Thompson Sampling
• Stagewise Safe Bayesian Optimization with Gaussian Processes
• Reducing Dueling Bandits to Cardinal Bandits
• Contextual Dueling Bandits
• Maximum Selection and Ranking under Noisy Comparisons
• PAC Battling Bandits in the Plackett-Luce Model
• Combinatorial Bandits with Relative Feedback
• Correlational Dueling Bandits with Application to Clinical Treatment in Large Decision Spaces
• On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons
• Active Ranking with Subset-wise Preferences
• Optimal Learning of Mallows Block Model
• Thresholding Bandit Problem with Both Duels and Pulls
• Dueling Bandits With Weak Regret

Cited by in corpus (6)

• Human Preferences as Dueling Bandits
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Learning Personalized Thermal Preferences via Bayesian Active Learning with Unimodality Constraints
• MergeDTS: A Method for Effective Large-Scale Online Ranker Evaluation
• Online Preselection with Context Information under the Plackett-Luce Model
• Exploiting Transitivity for Top-k Selection with Score-Based Dueling Bandits