Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Overlapping Multi-Bandit Best Arm Identification
 
conference paper

Overlapping Multi-Bandit Best Arm Identification

Scarlett, Jonathan
•
Bogunovic, Ilija
•
Cevher, Volkan  orcid-logo
2019
2019 IEEE International Symposium On Information Theory (Isit)
The 2019 IEEE International Symposium on Information Theory (ISIT)

In the multi-armed bandit literature, the multi-bandit best-arm identification problem consists of determining each best arm in a number of disjoint groups of arms, with as few total arm pulls as possible. In this paper, we introduce a variant of the multi-bandit problem with overlapping groups, and present two algorithms for this problem based on successive elimination and lower/upper confidence bounds (LUCB). We bound the number of total arm pulls required for high-probability best-arm identification in every group, and we complement these bounds with a near-matching algorithm-independent lower bound. In addition, we show that a specific choice of the groups recovers the top-k ranking problem.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1109/ISIT.2019.8849327
Web of Science ID

WOS:000489100302128

Author(s)
Scarlett, Jonathan
Bogunovic, Ilija
Cevher, Volkan  orcid-logo
Date Issued

2019

Publisher

IEEE

Publisher place

New York

Published in
2019 IEEE International Symposium On Information Theory (Isit)
ISBN of the book

978-1-5386-9291-2

Total of pages

11

Series title/Series vol.

IEEE International Symposium on Information Theory

Start page

2544

End page

2548

Subjects

Computer Science, Information Systems

•

Computer Science, Theory & Methods

•

Computer Science

•

complexity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Event nameEvent placeEvent date
The 2019 IEEE International Symposium on Information Theory (ISIT)

Paris, France

July 7-12, 2019

Available on Infoscience
April 1, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/155827
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés