Routine Bandits: Minimizing Regret on ...
Document type :
Communication dans un congrès avec actes
Title :
Routine Bandits: Minimizing Regret on Recurring Problems
Author(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]
Conference title :
ECML-PKDD 2021
City :
Bilbao
Country :
Espagne
Start date of the conference :
2021-09-13
Book title :
ECML-PKDD 2021
English keyword(s) :
Multi-armed bandits
Transfer Learning
KL-UCB
Transfer Learning
KL-UCB
HAL domain(s) :
Informatique [cs]/Intelligence artificielle [cs.AI]
Mathématiques [math]/Statistiques [math.ST]
Mathématiques [math]/Statistiques [math.ST]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-03286539/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp1cumulative.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp1regret.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp2cumulative.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp2regret.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp3cumulative.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresadditionalfour_banditsxp3regret.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurescritical_settingsetting.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurescritical_settingT_100.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurescritical_settingT_500.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditsnu_1.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditsnu_2.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditssetting_nu_1.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresfive_banditssetting_nu_2.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_1000xp_a.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_1000xp_b.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_1000xp_c.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_100xp_a.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_100xp_b.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmore_armsT_100xp_c.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuresmultiple_opt_armsrun_100.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuressimilar_arms_orderingnu.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuressimilar_arms_orderingone_bandit.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figuressimilar_arms_orderingsetting_nu.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunealpha_0.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_a.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_a_.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_b.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_b_.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_c.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsgamma_tunexp1_c_.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesrates_10000.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesrates_500.pdf
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesrates_5000.pdf
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_500.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_5000.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_10000.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_10000.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_500.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_500.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_5000.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tuneT_5000.png
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/main%20%282%29.pdf
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/main.synctex%20%281%29.gz
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/main.synctex%20%281%29.gz
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/file/figurestwo_armsT_tunefalse_positive_ratesT_500.jpg
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03286539/document
- Open access
- Access the document
- document
- Open access
- Access the document
- ECML2021_RoutineBandits%20%28Camera-Ready%29.pdf
- Open access
- Access the document
- figuresadditionalfour_banditsxp1cumulative.png
- Open access
- Access the document
- figuresadditionalfour_banditsxp1regret.png
- Open access
- Access the document
- figuresadditionalfour_banditsxp2cumulative.png
- Open access
- Access the document
- figuresadditionalfour_banditsxp2regret.png
- Open access
- Access the document
- figuresadditionalfour_banditsxp3cumulative.png
- Open access
- Access the document
- figuresadditionalfour_banditsxp3regret.png
- Open access
- Access the document
- figurescritical_settingsetting.png
- Open access
- Access the document
- figurescritical_settingT_100.png
- Open access
- Access the document
- figurescritical_settingT_500.png
- Open access
- Access the document
- figuresfive_banditsnu_1.png
- Open access
- Access the document
- figuresfive_banditsnu_2.png
- Open access
- Access the document
- figuresfive_banditssetting_nu_1.png
- Open access
- Access the document
- figuresfive_banditssetting_nu_2.png
- Open access
- Access the document
- figuresmore_armsT_1000xp_a.png
- Open access
- Access the document
- figuresmore_armsT_1000xp_b.png
- Open access
- Access the document
- figuresmore_armsT_1000xp_c.png
- Open access
- Access the document
- figuresmore_armsT_100xp_a.png
- Open access
- Access the document
- figuresmore_armsT_100xp_b.png
- Open access
- Access the document
- figuresmore_armsT_100xp_c.png
- Open access
- Access the document
- figuresmultiple_opt_armsrun_100.png
- Open access
- Access the document
- figuressimilar_arms_orderingnu.png
- Open access
- Access the document
- figuressimilar_arms_orderingone_bandit.png
- Open access
- Access the document
- figuressimilar_arms_orderingsetting_nu.png
- Open access
- Access the document
- figurestwo_armsgamma_tunealpha_0.jpg
- Open access
- Access the document
- figurestwo_armsgamma_tunexp1_a.png
- Open access
- Access the document
- figurestwo_armsgamma_tunexp1_a_.jpg
- Open access
- Access the document
- figurestwo_armsgamma_tunexp1_b.png
- Open access
- Access the document
- figurestwo_armsgamma_tunexp1_b_.jpg
- Open access
- Access the document
- figurestwo_armsgamma_tunexp1_c.png
- Open access
- Access the document
- figurestwo_armsgamma_tunexp1_c_.jpg
- Open access
- Access the document
- figurestwo_armsT_tunefalse_positive_ratesrates_10000.jpg
- Open access
- Access the document
- figurestwo_armsT_tunefalse_positive_ratesrates_500.pdf
- Open access
- Access the document
- figurestwo_armsT_tunefalse_positive_ratesrates_5000.pdf
- Open access
- Access the document
- figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg
- Open access
- Access the document
- figurestwo_armsT_tunefalse_positive_ratesT_500.jpg
- Open access
- Access the document
- figurestwo_armsT_tunefalse_positive_ratesT_5000.jpg
- Open access
- Access the document
- figurestwo_armsT_tuneT_10000.jpg
- Open access
- Access the document
- figurestwo_armsT_tuneT_10000.png
- Open access
- Access the document
- figurestwo_armsT_tuneT_500.jpg
- Open access
- Access the document
- figurestwo_armsT_tuneT_500.png
- Open access
- Access the document
- figurestwo_armsT_tuneT_5000.jpg
- Open access
- Access the document
- figurestwo_armsT_tuneT_5000.png
- Open access
- Access the document
- main%20%282%29.pdf
- Open access
- Access the document
- main.synctex%20%281%29.gz
- Open access
- Access the document