Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond

Mastane Achab; Stephan Clémençon; Aurélien Garivier; Anne Sabourin; Claire Vernade

doi:10.1007/978-3-319-71246-8_24

Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond

Mastane Achab
, Stephan Clémençon
, Aurélien Garivier
, Anne Sabourin
, Claire Vernade

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper is devoted to the study of the max K-armed bandit problem, which consists in sequentially allocating resources in order to detect extreme values. Our contribution is twofold. We first significantly refine the analysis of the ExtremeHunter algorithm carried out in Carpentier and Valko (2014), and next propose an alternative approach, showing that, remarkably, Extreme Bandits can be reduced to a classical version of the bandit problem to a certain extent. Beyond the formal analysis, these two approaches are compared through numerical experiments.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings
Editors	Michelangelo Ceci, Jaakko Hollmen, Ljupco Todorovski, Celine Vens, Saso Dzeroski
Publisher	Springer Verlag
Pages	389-404
Number of pages	16
ISBN (Print)	9783319712451
DOIs	https://doi.org/10.1007/978-3-319-71246-8_24
Publication status	Published - 1 Jan 2017
Externally published	Yes
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2017 - Skopje, Macedonia, The Former Yugoslav Republic of Duration: 18 Sept 2017 → 22 Sept 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10535 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2017
Country/Territory	Macedonia, The Former Yugoslav Republic of
City	Skopje
Period	18/09/17 → 22/09/17

Access to Document

10.1007/978-3-319-71246-8_24

Cite this

Achab, M., Clémençon, S., Garivier, A., Sabourin, A., & Vernade, C. (2017). Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond. In M. Ceci, J. Hollmen, L. Todorovski, C. Vens, & S. Dzeroski (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings (pp. 389-404). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10535 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-71246-8_24

Achab, Mastane ; Clémençon, Stephan ; Garivier, Aurélien et al. / Max K-Armed Bandit : On the ExtremeHunter Algorithm and Beyond. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings. editor / Michelangelo Ceci ; Jaakko Hollmen ; Ljupco Todorovski ; Celine Vens ; Saso Dzeroski. Springer Verlag, 2017. pp. 389-404 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a6df772d0dd64f969d94389e0a961fd7,

title = "Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond",

abstract = "This paper is devoted to the study of the max K-armed bandit problem, which consists in sequentially allocating resources in order to detect extreme values. Our contribution is twofold. We first significantly refine the analysis of the ExtremeHunter algorithm carried out in Carpentier and Valko (2014), and next propose an alternative approach, showing that, remarkably, Extreme Bandits can be reduced to a classical version of the bandit problem to a certain extent. Beyond the formal analysis, these two approaches are compared through numerical experiments.",

author = "Mastane Achab and Stephan Cl{\'e}men{\c c}on and Aur{\'e}lien Garivier and Anne Sabourin and Claire Vernade",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2017 ; Conference date: 18-09-2017 Through 22-09-2017",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-71246-8\_24",

language = "English",

isbn = "9783319712451",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "389--404",

editor = "Michelangelo Ceci and Jaakko Hollmen and Ljupco Todorovski and Celine Vens and Saso Dzeroski",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings",

}

Achab, M, Clémençon, S, Garivier, A, Sabourin, A & Vernade, C 2017, Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond. in M Ceci, J Hollmen, L Todorovski, C Vens & S Dzeroski (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10535 LNAI, Springer Verlag, pp. 389-404, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2017, Skopje, Macedonia, The Former Yugoslav Republic of, 18/09/17. https://doi.org/10.1007/978-3-319-71246-8_24

Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond. / Achab, Mastane; Clémençon, Stephan; Garivier, Aurélien et al.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings. ed. / Michelangelo Ceci; Jaakko Hollmen; Ljupco Todorovski; Celine Vens; Saso Dzeroski. Springer Verlag, 2017. p. 389-404 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10535 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Max K-Armed Bandit

T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2017

AU - Achab, Mastane

AU - Clémençon, Stephan

AU - Garivier, Aurélien

AU - Sabourin, Anne

AU - Vernade, Claire

PY - 2017/1/1

Y1 - 2017/1/1

N2 - This paper is devoted to the study of the max K-armed bandit problem, which consists in sequentially allocating resources in order to detect extreme values. Our contribution is twofold. We first significantly refine the analysis of the ExtremeHunter algorithm carried out in Carpentier and Valko (2014), and next propose an alternative approach, showing that, remarkably, Extreme Bandits can be reduced to a classical version of the bandit problem to a certain extent. Beyond the formal analysis, these two approaches are compared through numerical experiments.

AB - This paper is devoted to the study of the max K-armed bandit problem, which consists in sequentially allocating resources in order to detect extreme values. Our contribution is twofold. We first significantly refine the analysis of the ExtremeHunter algorithm carried out in Carpentier and Valko (2014), and next propose an alternative approach, showing that, remarkably, Extreme Bandits can be reduced to a classical version of the bandit problem to a certain extent. Beyond the formal analysis, these two approaches are compared through numerical experiments.

U2 - 10.1007/978-3-319-71246-8_24

DO - 10.1007/978-3-319-71246-8_24

M3 - Conference contribution

AN - SCOPUS:85040258068

SN - 9783319712451

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 389

EP - 404

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings

A2 - Ceci, Michelangelo

A2 - Hollmen, Jaakko

A2 - Todorovski, Ljupco

A2 - Vens, Celine

A2 - Dzeroski, Saso

PB - Springer Verlag

Y2 - 18 September 2017 through 22 September 2017

ER -

Achab M, Clémençon S, Garivier A, Sabourin A, Vernade C. Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond. In Ceci M, Hollmen J, Todorovski L, Vens C, Dzeroski S, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Proceedings. Springer Verlag. 2017. p. 389-404. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-71246-8_24

Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this