The Influence of Shape Constraints on the ...
Type de document :
Communication dans un congrès avec actes
Titre :
The Influence of Shape Constraints on the Thresholding Bandit Problem
Auteur(s) :
Cheshire, James [Auteur]
Otto-von-Guericke-Universität Magdeburg = Otto-von-Guericke University [Magdeburg] [OVGU]
Ménard, Pierre [Auteur]
Scool [Scool]
Sequential Learning [SEQUEL]
Carpentier, Alexandra [Auteur]
Otto-von-Guericke-Universität Magdeburg = Otto-von-Guericke University [Magdeburg] [OVGU]
Otto-von-Guericke-Universität Magdeburg = Otto-von-Guericke University [Magdeburg] [OVGU]
Ménard, Pierre [Auteur]
Scool [Scool]
Sequential Learning [SEQUEL]
Carpentier, Alexandra [Auteur]
Otto-von-Guericke-Universität Magdeburg = Otto-von-Guericke University [Magdeburg] [OVGU]
Titre de la manifestation scientifique :
COLT 2020 - Thirty Third Conference on Learning Theory
Ville :
Graz / Virtual
Pays :
Autriche
Date de début de la manifestation scientifique :
2020-07-09
Date de publication :
2020
Discipline(s) HAL :
Mathématiques [math]/Statistiques [math.ST]
Résumé en anglais : [en]
We investigate the stochastic Thresholding Bandit problem (TBP) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means (µ k) k is monotonically ...
Lire la suite >We investigate the stochastic Thresholding Bandit problem (TBP) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means (µ k) k is monotonically increasing MTBP, (iii) the case where (µ k) k is unimodal UTBP and (iv) the case where (µ k) k is concave CTBP. In the TBP problem the aim is to output, at the end of the sequential game, the set of arms whose means are above a given threshold. The regret is the highest gap between a misclassified arm and the threshold. In the fixed budget setting, we provide problem independent minimax rates for the expected regret in all settings, as well as associated algorithms. We prove that the minimax rates for the regret are (i) log(K)K/T for TBP, (ii) log(K)/T for MTBP, (iii) K/T for UTBP and (iv) log log K/T for CTBP, where K is the number of arms and T is the budget. These rates demonstrate that the dependence on K of the minimax regret varies significantly depending on the shape constraint. This highlights the fact that the shape constraints modify fundamentally the nature of the TBP problem to the other.Lire moins >
Lire la suite >We investigate the stochastic Thresholding Bandit problem (TBP) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means (µ k) k is monotonically increasing MTBP, (iii) the case where (µ k) k is unimodal UTBP and (iv) the case where (µ k) k is concave CTBP. In the TBP problem the aim is to output, at the end of the sequential game, the set of arms whose means are above a given threshold. The regret is the highest gap between a misclassified arm and the threshold. In the fixed budget setting, we provide problem independent minimax rates for the expected regret in all settings, as well as associated algorithms. We prove that the minimax rates for the regret are (i) log(K)K/T for TBP, (ii) log(K)/T for MTBP, (iii) K/T for UTBP and (iv) log log K/T for CTBP, where K is the number of arms and T is the budget. These rates demonstrate that the dependence on K of the minimax regret varies significantly depending on the shape constraint. This highlights the fact that the shape constraints modify fundamentally the nature of the TBP problem to the other.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03001947v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03001947v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03001947v2/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- COLT2020.pdf
- Accès libre
- Accéder au document