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

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

ECML-PKDD 2017 pp. 389-404

doi:10.1007/978-3-319-71246-8_24 /ecmlpkdd/2017/achab2017ecmlpkdd-max/

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.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Achab et al. "Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017. doi:10.1007/978-3-319-71246-8_24

Markdown

[Achab et al. "Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017.](https://mlanthology.org/ecmlpkdd/2017/achab2017ecmlpkdd-max/) doi:10.1007/978-3-319-71246-8_24

BibTeX

@inproceedings{achab2017ecmlpkdd-max,
  title     = {{Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond}},
  author    = {Achab, Mastane and Clémençon, Stéphan and Garivier, Aurélien and Sabourin, Anne and Vernade, Claire},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2017},
  pages     = {389-404},
  doi       = {10.1007/978-3-319-71246-8_24},
  url       = {https://mlanthology.org/ecmlpkdd/2017/achab2017ecmlpkdd-max/}
}