Actions
  • shareshare
  • link
  • cite
  • add
add
auto_awesome_motion View all 3 versions
Publication . Article . Preprint . 2013 . Embargo end date: 01 Jan 2013

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

Zoghi, M.; Whiteson, S.; Munos, R.; de Rijke, M.;
Open Access
Published: 11 Dec 2013
Publisher: arXiv
Abstract
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 finite-time regret bound of order O(log t). In addition, our empirical results using real data from an information retrieval application show that it greatly outperforms the state of the art.
Comment: 13 pages, 6 figures
Subjects

Machine Learning (cs.LG), FOS: Computer and information sciences, Computer Science - Learning

Related Organizations
Funded byView all
NWO| Modeling and Learning from Implicit Feedback in Information Retrieval
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300171779
,
EC| LIMOSINE
Project
LIMOSINE
Linguistically Motivated Semantic aggregatIon engiNes
  • Funder: European Commission (EC)
  • Project Code: 288024
  • Funding stream: FP7 | SP1 | ICT
,
NWO| Digging archaeology data: image search and markup (DADAISM)
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300186891
,
NWO| Building Rich Links to Enable Television History Research
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300153702
Related to Research communities
Digital Humanities and Cultural Heritage DH-CH communities : CLARIN
Download fromView all 3 sources
lock_open
NARCIS
Article . 2014
Providers: NARCIS
moresidebar