Extreme bandits

Alexandra Carpentier 1 Michal Valko 2
2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : In many areas of medicine, security, and life sciences, we want to allocate limited resources to different sources in order to detect extreme values. In this paper, we study an efficient way to allocate these resources sequentially under limited feedback. While sequential design of experiments is well studied in bandit theory, the most commonly optimized property is the regret with respect to the maximum mean reward. However, in other problems such as network intrusion detection, we are interested in detecting the most extreme value output by the sources. Therefore, in our work we study extreme regret which measures the efficiency of an algorithm compared to the oracle policy selecting the source with the heaviest tail. We propose the ExtremeHunter algorithm, provide its analysis, and evaluate it empirically on synthetic and real-world experiments.
Type de document :
Communication dans un congrès
Neural Information Processing Systems, Dec 2014, Montréal, Canada
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01079354
Contributeur : Michal Valko <>
Soumis le : lundi 3 novembre 2014 - 09:58:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Fichier

carpentier2014extreme.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01079354, version 2

Citation

Alexandra Carpentier, Michal Valko. Extreme bandits. Neural Information Processing Systems, Dec 2014, Montréal, Canada. 〈hal-01079354v2〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

145