Extreme bandits

Carpentier, Alexandra; Valko, Michal

Type de document :

Communication dans un congrès avec actes

Titre :

Extreme bandits

Auteur(s) :

Carpentier, Alexandra [Auteur]
Statistical Laboratory [Cambridge]
Valko, Michal [Auteur]

Sequential Learning [SEQUEL]

Titre de la manifestation scientifique :

Neural Information Processing Systems

Ville :

Montréal

Pays :

Canada

Date de début de la manifestation scientifique :

2014-12-07

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :