A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits

By Pratik Gajane, Tanguy Urvoy, Fabrice Clérot. 2015

54 citations recorded by the source corpus.

We study the K-armed dueling bandit problem which is a variation of the classical Multi-Armed Bandit (MAB) problem in which the learner receives only relative feedback about the selected pairs of arms. We propose an efficient algorithm called Relative Exponential-weight algorithm for Exploration and Exploitation (REX3) to handle the adversarial utility-based formulation of this problem. We prove a finite time expected regret upper bound of order O(√Kln(K)T) for this algorithm and a general lower bound of order Ω(√KT). At the end, we provide experimental results using real data from information retrieval applications.

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

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, methodology): “Towards these goals, several algorithms have been proposed (Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019).”
MergeDTS (2018, methodology): “Another extension of Sparring is REX3 [16], which is designed for the adversarial setting.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “…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] Unfortunately, all algorithms that achieve the optimal rate rely heavily on adversarial online learning…”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “Their study reveals that the REX 3 algorithm (Gajane et al., 2015) for adversarial utility-based dueling bandits with a regret of ˜ ( √ KT ) is the only optimal algorithm with respect to T and K , and that the SAVAGE algorithm (Urvoy et al., 2013) for general stochastic dueling bandits with a…”
PAC Battling Bandits in the Plackett-Luce Model (2018, background): “, 2016, Zhou and Tomlin, 2017], feature-based preference information and adversarial choice feedback [Gajane et al., 2015].”
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits (2022, background): “, 2013) with pairs of items (size-2 subsets) that can be played, and subsequent work on generalization to broader models both in terms of distributional parameters (Yue and Joachims, 2009; Gajane et al., 2015; Ailon et al., 2014; Zoghi et al., 2015) as well as combinatorial subset-wise plays (Mohaje”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…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 al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019; Faury et al., 2020).”