Routine Bandits: Minimizing Regret on ...
Type de document :
Communication dans un congrès avec actes
Titre :
Routine Bandits: Minimizing Regret on Recurring Problems
Auteur(s) :
Saber, Hassan [Auteur]
Scool [Scool]
Saci, Léo [Auteur]
École normale supérieure - Paris [ENS-PSL]
Maillard, Odalric-Ambrym [Auteur]
Scool [Scool]
Durand, Audrey [Auteur]
Université Laval [Québec] [ULaval]
Scool [Scool]
Saci, Léo [Auteur]
École normale supérieure - Paris [ENS-PSL]
Maillard, Odalric-Ambrym [Auteur]
Scool [Scool]
Durand, Audrey [Auteur]
Université Laval [Québec] [ULaval]
Titre de la manifestation scientifique :
ECML-PKDD 2021
Ville :
Bilbao
Pays :
Espagne
Date de début de la manifestation scientifique :
2021-09-13
Titre de l’ouvrage :
ECML-PKDD 2021
Mot(s)-clé(s) en anglais :
Multi-armed bandits
Transfer Learning
KL-UCB
Transfer Learning
KL-UCB
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Mathématiques [math]/Statistiques [math.ST]
Mathématiques [math]/Statistiques [math.ST]
Résumé en anglais : [en]
We study a variant of the multi-armed bandit problem in which a learner faces every day one of B many bandit instances, and call it a routine bandit. More specifically, at each period h ∈ [1, H] , the same bandit b^h is ...
Lire la suite >We study a variant of the multi-armed bandit problem in which a learner faces every day one of B many bandit instances, and call it a routine bandit. More specifically, at each period h ∈ [1, H] , the same bandit b^h is considered during T > 1 consecutive time steps, but the identity b^h is unknown to the learner. We assume all rewards distribution are Gaussian standard. Such a situation typically occurs in recommender systems when a learner may repeatedly serve the same user whose identity is unknown due to privacy issues. By combining banditidentification tests with a KLUCB type strategy, we introduce the KLUCB for Routine Bandits (KLUCB-RB) algorithm. While independently running KLUCB algorithm at each period leads to a cumulative expected regret of Ω(H log T) after H many periods when T → ∞, KLUCB-RB benefits from previous periods by aggregating observations from similar identified bandits, which yields a non-trivial scaling of Ω(log T). This is achieved without knowing which bandit instance is being faced by KLUCB-RB on this period, nor knowing a priori the number of possible bandit instances. We provide numerical illustration that confirm the benefit of KLUCB-RB while using less information about the problem compared with existing strategies for similar problems.Lire moins >
Lire la suite >We study a variant of the multi-armed bandit problem in which a learner faces every day one of B many bandit instances, and call it a routine bandit. More specifically, at each period h ∈ [1, H] , the same bandit b^h is considered during T > 1 consecutive time steps, but the identity b^h is unknown to the learner. We assume all rewards distribution are Gaussian standard. Such a situation typically occurs in recommender systems when a learner may repeatedly serve the same user whose identity is unknown due to privacy issues. By combining banditidentification tests with a KLUCB type strategy, we introduce the KLUCB for Routine Bandits (KLUCB-RB) algorithm. While independently running KLUCB algorithm at each period leads to a cumulative expected regret of Ω(H log T) after H many periods when T → ∞, KLUCB-RB benefits from previous periods by aggregating observations from similar identified bandits, which yields a non-trivial scaling of Ω(log T). This is achieved without knowing which bandit instance is being faced by KLUCB-RB on this period, nor knowing a priori the number of possible bandit instances. We provide numerical illustration that confirm the benefit of KLUCB-RB while using less information about the problem compared with existing strategies for similar problems.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03286539/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp1cumulative.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp1regret.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp2cumulative.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp2regret.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp3cumulative.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp3regret.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurescritical_settingsetting.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurescritical_settingT_100.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurescritical_settingT_500.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditsnu_1.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditsnu_2.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditssetting_nu_1.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditssetting_nu_2.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_1000xp_a.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_1000xp_b.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_1000xp_c.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_100xp_a.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_100xp_b.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_100xp_c.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmultiple_opt_armsrun_100.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuressimilar_arms_orderingnu.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuressimilar_arms_orderingone_bandit.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuressimilar_arms_orderingsetting_nu.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunealpha_0.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_a.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_a_.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_b.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_b_.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_c.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_c_.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesrates_10000.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesrates_500.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesrates_5000.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_500.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_5000.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_10000.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_10000.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_500.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_500.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_5000.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_5000.png
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/main%20%282%29.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/main.synctex%20%281%29.gz
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/main.synctex%20%281%29.gz
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_500.jpg
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03286539/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- ECML2021_RoutineBandits%20%28Camera-Ready%29.pdf
- Accès libre
- Accéder au document
- figuresadditionalfour_banditsxp1cumulative.png
- Accès libre
- Accéder au document
- figuresadditionalfour_banditsxp1regret.png
- Accès libre
- Accéder au document
- figuresadditionalfour_banditsxp2cumulative.png
- Accès libre
- Accéder au document
- figuresadditionalfour_banditsxp2regret.png
- Accès libre
- Accéder au document
- figuresadditionalfour_banditsxp3cumulative.png
- Accès libre
- Accéder au document
- figuresadditionalfour_banditsxp3regret.png
- Accès libre
- Accéder au document
- figurescritical_settingsetting.png
- Accès libre
- Accéder au document
- figurescritical_settingT_100.png
- Accès libre
- Accéder au document
- figurescritical_settingT_500.png
- Accès libre
- Accéder au document
- figuresfive_banditsnu_1.png
- Accès libre
- Accéder au document
- figuresfive_banditsnu_2.png
- Accès libre
- Accéder au document
- figuresfive_banditssetting_nu_1.png
- Accès libre
- Accéder au document
- figuresfive_banditssetting_nu_2.png
- Accès libre
- Accéder au document
- figuresmore_armsT_1000xp_a.png
- Accès libre
- Accéder au document
- figuresmore_armsT_1000xp_b.png
- Accès libre
- Accéder au document
- figuresmore_armsT_1000xp_c.png
- Accès libre
- Accéder au document
- figuresmore_armsT_100xp_a.png
- Accès libre
- Accéder au document
- figuresmore_armsT_100xp_b.png
- Accès libre
- Accéder au document
- figuresmore_armsT_100xp_c.png
- Accès libre
- Accéder au document
- figuresmultiple_opt_armsrun_100.png
- Accès libre
- Accéder au document
- figuressimilar_arms_orderingnu.png
- Accès libre
- Accéder au document
- figuressimilar_arms_orderingone_bandit.png
- Accès libre
- Accéder au document
- figuressimilar_arms_orderingsetting_nu.png
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunealpha_0.jpg
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunexp1_a.png
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunexp1_a_.jpg
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunexp1_b.png
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunexp1_b_.jpg
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunexp1_c.png
- Accès libre
- Accéder au document
- figurestwo_armsgamma_tunexp1_c_.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tunefalse_positive_ratesrates_10000.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tunefalse_positive_ratesrates_500.pdf
- Accès libre
- Accéder au document
- figurestwo_armsT_tunefalse_positive_ratesrates_5000.pdf
- Accès libre
- Accéder au document
- figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tunefalse_positive_ratesT_500.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tunefalse_positive_ratesT_5000.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tuneT_10000.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tuneT_10000.png
- Accès libre
- Accéder au document
- figurestwo_armsT_tuneT_500.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tuneT_500.png
- Accès libre
- Accéder au document
- figurestwo_armsT_tuneT_5000.jpg
- Accès libre
- Accéder au document
- figurestwo_armsT_tuneT_5000.png
- Accès libre
- Accéder au document
- main%20%282%29.pdf
- Accès libre
- Accéder au document
- main.synctex%20%281%29.gz
- Accès libre
- Accéder au document