publication . Article . Preprint . 2013 . Embargo end date: 01 Jan 2013

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

Zoghi, Masrour; Whiteson, Shimon; Munos, Remi; de Rijke, Maarten;
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
Persistent Identifiers
Subjects
free text keywords: Machine Learning (cs.LG), FOS: Computer and information sciences, Computer Science - Learning
Related Organizations
Communities
Communities with gateway
OpenAIRE Connect image
Other Communities
  • CLARIN
  • Digital Humanities and Cultural Heritage DH-CH communities : CLARIN
Funded by
NWO| Semantic Search in E-Discovery
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300168486
,
NWO| Building Rich Links to Enable Television History Research
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300153702
,
EC| COMPLACS
Project
COMPLACS
Composing Learning for Artificial Cognitive Systems
  • Funder: European Commission (EC)
  • Project Code: 270327
  • Funding stream: FP7 | SP1 | ICT
,
NWO| SPuDisc: Searching Public Discourse
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300176811
,
NWO| Digging archaeology data: image search and markup (DADAISM)
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300186891
Any information missing or wrong?Report an Issue