Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem

By Masrour Zoghi, Shimon Whiteson, R´emi Munos, Maarten de Rijke. 2013

164 citations recorded by the source corpus.

This paper proposes a new method for the K-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence Bound algorithm to the relative setting by using estimates of the pairwise probabilities to select a promising arm and applying Upper Confidence Bound with the winner as a benchmark. We prove a sharp finite-time regret bound of order O(K log T) on a very general class of dueling bandit problems that matches a lower bound proven in (Yue et al., 2012). In addition, our empirical results using real data from an information retrieval application show that it greatly outperforms the state of the art.

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

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Human Preferences as Dueling Bandits (2022, neutral): “Later algorithms such as RUCB [42], MergeRUCB [41] and MergeDTS [20] make weaker assumptions, but still require the existence of a Condorcet winner.”
Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, methodology): “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, methodology): “…(Yue and Joachims, 2011); Sensitivity Analysis of VAriables for Generic Exploration (SAVAGE) (Urvoy et al., 2013); Relative Confidence Sampling (Zoghi et al., 2014a); Relative Upper Confidence Bound (RUCB) (Zoghi et al., 2014b); Doubler, MultiSBM and Sparring (Ailon et al., 2014) and mergeRUCB…”
Dueling Posterior Sampling for Preference-Based Reinforcement Learning (2019, methodology): “This reward model is a solution to the temporal credit assignment problem (Akrour et al., 2012; Zoghi et al., 2014; Szörényi et al., 2015; Christiano et al., 2017; Wirth et al., 2016; 2017) and determines which of the encountered states and actions are responsible for the trajectory-level”
Learning to Rank (2005, unknown): “[56, 57, 58, 59] – Challenges associated with deciding which ranker is the best among a population, the concept of Condorcet winner and Relative Upper Confidence Bound algorithm.”
Battle of Bandits (2018, methodology): “Battling-Duel Regret with RUCB.”
A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits (2015, methodology): “Zoghi et al. (2014a) extend the Upper Confidence Bound (UCB) algorithm (Auer et al., 2002a) and propose an algorithm called Relative Upper Confidence Bound (RUCB) provided that the preference matrix admits a Condorcet winner.”
MergeDTS (2018, methodology): “MergeDTS, like most of the other dueling bandits algorithms [44, 46, 54–56], relies on the existence of a Condorcet winner, in which case the Condorcet winner is the clear choice for the best arm, since it is preferred to all other arms, and with respect to which regret can be defined.”
Bandit Algorithms (2020, methodology): “This has been investigated in the cascade model by Zong et al. [2016] and with a model resembling that of this chapter by Li et al.”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “In the literature of dueling bandit , one compares two actions and aims to minimize regret based on pairwise 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…”
PAC Battling Bandits in the Plackett-Luce Model (2018, background): “Though most work on dueling bandits has focused on the regret minimization goal (Zoghi et al., 2014; Ramamohan et al., 2016), there have been recent developments on the PAC objective for different pairwise preference models, such as those satisfying stochastic triangle inequalities and strong stocha”
Ordered Preference Elicitation Strategies for Supporting Multi-Objective Decision Making (2018, background): “Relative feedback [45, 55] is easier for humans to express (consider “I prefer film A over B”), and is typically more consistent over time [28].”
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits (2022, background): “…preference information (ordinal as opposed to cardinal feedback) has seen steady progress since the introduction of the dueling bandit framework (Zoghi et al., 2013) with pairs of items (size-2 subsets) that can be played, and subsequent work on generalization to broader models both in terms of…”
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem (2015, methodology): “Zoghi et al.(2013) first proposed RUCB with anO(K2 log T ) regret bound and later modified it by adding a randomization procedure to assureO(K log T ) regret inZoghi et al.(2014b). lyze this lower bound to obtain the optimal constant factor for models satisfying the Condorcet assumption.”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “Then for Condorcet dueling bandits, we refine the regret to O(K log T + K2 log log T ) with a simplified version of D-TS.”