Contextual Dueling Bandits

By Miroslav Dud'ik, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi. 2015

162 citations recorded by the source corpus.

We consider the problem of learning to choose actions using contextual information when provided with limited feedback in the form of relative pairwise comparisons. We study this problem in the dueling-bandits framework of Yue et al. (2009), which we extend to incorporate context. Roughly, the learner's goal is to find the best policy, or way of behaving, in some space of policies, although "best" is not always so clearly defined. Here, we propose a new and natural solution concept, rooted in game theory, called a von Neumann winner, a randomized policy that beats or ties every other policy. We show that this notion overcomes important limitations of existing solutions, particularly the Condorcet winner which has typically been used in the past, but which requires strong and often unrealistic assumptions. We then present three efficient algorithms for online learning in our setting, and for approximating a von Neumann winner from batch-like data. The first of these algorithms achieves particularly low regret, even when data is adversarial, although its time and space requirements are linear in the size of the policy space. The other two algorithms require time and space only logarithmic in the size of the policy space when provided access to an oracle for solving classification problems on the space.

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

Direct Preference Optimization: Your Language Model is Secretly a Reward Model (2023, methodology): “First, in a well-controlled text-generation setting, we ask: how efﬁciently does DPO trade off maximizing reward and minimizing KL-divergence with the reference policy, compared to common preference learning algorithms such as PPO?”
Introduction to Multi-Armed Bandits (2019, methodology): “Further work on this model includes (Ailon et al., 2014; Zoghi et al., 2014; Dudı́k et al., 2015).”
Copeland Dueling Bandits (2015, methodology): “As these numbers demonstrate, the Copeland and the von Neumann winners are very likely to overlap, as are the Borda and Random Walk winners, while the first two definitions are more likely to be incompatible with the latter two.”
Active Ranking with Subset-wise Preferences (2018, background): “), and perhaps to extend this theory to newer formulations such as assortment selection [5, 16], revenue maximization with item prices [35, 1], or even in contextual scenarios [17] where every individual user comes with their own model parameter.”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “, with side information [22] or budget constraints [24]) is another interesting direction for future research.”
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.”
Bandit Algorithms (2020, methodology): “More details are in the bibliographic remarks in Chapter 38. 4 Economists have long recognized the role of time in the utility people place on rewards. Most people view a promise of pizza a year from today as less valuable than the same pizza tomorrow. Discounting rewards is one way to model this ki”
Optimal Algorithms for Stochastic Contextual Preference Bandits (2021, background): “In [15], authors considered a version of adversarial contextual dueling bandit problem, which only takes into account the special case of pairwise feedback (q = 2).”
Re-evaluating evaluation (2018, background): “Empirical game theory has been applied to domains like poker and continuous double auctions, and has recently been extended to asymmetric games [54–58]. von Neumann winners in the dueling bandit setting and NE-regret are related to Nash averaging [59–62].”
MergeDTS (2018, background): “ , C. There are numerous proposals in the literature for alternative notions of winners in the absence of a Condorcet winner, e.g., Borda winner [22, 38], Copeland winner [27, 43], von Neumann winner [12], with each definition having its own flaws as well as practical settings where its use is appro”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, methodology): “Indeed, this 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).”