Extreme bandits - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Extreme bandits

Alexandra Carpentier
  • Fonction : Auteur
  • PersonId : 961172
Michal Valko

Résumé

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.
Fichier principal
Vignette du fichier
carpentier2014extreme.pdf (361.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01079354 , version 1 (01-11-2014)
hal-01079354 , version 2 (03-11-2014)

Identifiants

  • HAL Id : hal-01079354 , version 1

Citer

Alexandra Carpentier, Michal Valko. Extreme bandits. Advances in Neural Information Processing Systems 27, Dec 2014, Montréal, Canada. ⟨hal-01079354v1⟩
230 Consultations
229 Téléchargements

Partager

Gmail Facebook X LinkedIn More