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

Pratik Gajane; Tanguy Urvoy; Fabrice Clérot

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

Pratik Gajane ^{1, 2} Tanguy Urvoy ² Fabrice Clérot ²

Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

2 Orange Labs [Lannion]

Abstract : 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 a new algorithm called Relative Exponential-weight algorithm for Exploration and Exploitation (REX3) to handle the adversarial utility-based formulation of this problem. This algorithm is a non-trivial extension of the Exponential-weight algorithm for Exploration and Exploitation (EXP3) algorithm. We prove a finite time expected regret upper bound of order O(sqrt(K ln(K)T)) for this algorithm and a general lower bound of order omega(sqrt(KT)). At the end, we provide experimental results using real data from information retrieval applications.

Keywords : MAB online learning dueling bandits

Document type :

Conference papers

Domain :

Computer Science [cs] / Other [cs.OH]

Complete list of metadatas

Cited literature [26 references] Display Hide Download

https://hal.inria.fr/hal-01225614
Contributor : Pratik Gajane <>
Submitted on : Thursday, January 14, 2016 - 1:37:23 PM
Last modification on : Friday, March 22, 2019 - 1:35:17 AM
Long-term archiving on : Friday, April 15, 2016 - 2:31:39 PM

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

Files

Identifiers

Collections

Citation

Export

Metrics

332

139

Contact

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

Files

Identifiers

Collections

Citation

Export

Share

Metrics

332

139

Contact