Dealing With Misspecification In ...
Type de document :
Communication dans un congrès avec actes
Titre :
Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification
Auteur(s) :
Réda, Clémence [Auteur]
Maladies neurodéveloppementales et neurovasculaires [NeuroDiderot (UMR_S_1141 / U1141)]
Tirinzoni, Andrea [Auteur]
Scool [Scool]
Degenne, Rémy [Auteur]
Scool [Scool]
Maladies neurodéveloppementales et neurovasculaires [NeuroDiderot (UMR_S_1141 / U1141)]
Tirinzoni, Andrea [Auteur]
Scool [Scool]
Degenne, Rémy [Auteur]
Scool [Scool]
Titre de la manifestation scientifique :
35th Conference on Neural Information Processing Systems
Ville :
Virtual
Pays :
France
Date de début de la manifestation scientifique :
2021
Date de publication :
2021
Mot(s)-clé(s) en anglais :
misspecification
linear bandits
fixed-confidence top-m identification
pure exploration
recommendation systems
multi-armed bandits
linear bandits
fixed-confidence top-m identification
pure exploration
recommendation systems
multi-armed bandits
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Informatique [cs]/Apprentissage [cs.LG]
Mathématiques [math]/Statistiques [math.ST]
Informatique [cs]/Apprentissage [cs.LG]
Mathématiques [math]/Statistiques [math.ST]
Résumé en anglais : [en]
We study the problem of the identification of m arms with largest means under a fixed error rate δ (fixed-confidence Top-m identification), for misspecified linear bandit models. This problem is motivated by practical ...
Lire la suite >We study the problem of the identification of m arms with largest means under a fixed error rate δ (fixed-confidence Top-m identification), for misspecified linear bandit models. This problem is motivated by practical applications, especially in medicine and recommendation systems, where linear models are popular due to their simplicity and the existence of efficient algorithms, but in which data inevitably deviates from linearity. In this work, we first derive a tractable lower bound on the sample complexity of any δ-correct algorithm for the general Top-m identification problem. We show that knowing the scale of the deviation from linearity is necessary to exploit the structure of the problem. We then describe the first algorithm for this setting, which is both practical and adapts to the amount of misspecification. We derive an upper bound to its sample complexity which confirms this adaptivity and that matches the lower bound when δ → 0. Finally, we evaluate our algorithm on both synthetic and real-world data, showing competitive performance with respect to existing baselines.Lire moins >
Lire la suite >We study the problem of the identification of m arms with largest means under a fixed error rate δ (fixed-confidence Top-m identification), for misspecified linear bandit models. This problem is motivated by practical applications, especially in medicine and recommendation systems, where linear models are popular due to their simplicity and the existence of efficient algorithms, but in which data inevitably deviates from linearity. In this work, we first derive a tractable lower bound on the sample complexity of any δ-correct algorithm for the general Top-m identification problem. We show that knowing the scale of the deviation from linearity is necessary to exploit the structure of the problem. We then describe the first algorithm for this setting, which is both practical and adapts to the amount of misspecification. We derive an upper bound to its sample complexity which confirms this adaptivity and that matches the lower bound when δ → 0. Finally, we evaluate our algorithm on both synthetic and real-world data, showing competitive performance with respect to existing baselines.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Commentaire :
Virtual conference
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03409205/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/2111.01479
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03409205/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03409205/document
- Accès libre
- Accéder au document
- reda2021dealing.pdf
- Accès libre
- Accéder au document
- 2111.01479
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- reda2021dealing.pdf
- Accès libre
- Accéder au document