Routine Bandits: Minimizing Regret on Recurring Problems

Hassan Saber; Léo Saci; Odalric-Ambrym Maillard; Audrey Durand

Communication Dans Un Congrès Année : 2021

Routine Bandits: Minimizing Regret on Recurring Problems

(1) , (2) , (1) , (3)

1
2
3

Hassan Saber

Fonction : Auteur

Scool

Léo Saci

Fonction : Auteur

École normale supérieure - Paris

Odalric-Ambrym Maillard

Fonction : Auteur

Scool

Audrey Durand

Fonction : Auteur

Université Laval [Québec]

Résumé

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.

Mots clés

Multi-armed bandits Transfer Learning KL-UCB

Domaines

Intelligence artificielle [cs.AI] Statistiques [math.ST]

Fichier principal

ECML2021_RoutineBandits (Camera-Ready).pdf (1.23 Mo)

figuresadditionalfour_banditsxp1cumulative.png (53.58 Ko)

figuresadditionalfour_banditsxp1regret.png (53.81 Ko)

figuresadditionalfour_banditsxp2cumulative.png (53.31 Ko)

figuresadditionalfour_banditsxp2regret.png (67.36 Ko)

figuresadditionalfour_banditsxp3cumulative.png (48.57 Ko)

figuresadditionalfour_banditsxp3regret.png (56.42 Ko)

figurescritical_settingT_100.png (47.17 Ko)

figurescritical_settingT_500.png (41.53 Ko)

figurescritical_settingsetting.png (47.47 Ko)

figuresfive_banditsnu_1.png (34.82 Ko)

figuresfive_banditsnu_2.png (34.98 Ko)

figuresfive_banditssetting_nu_1.png (53.24 Ko)

figuresfive_banditssetting_nu_2.png (47.41 Ko)

figuresmore_armsT_1000xp_a.png (45.28 Ko)

figuresmore_armsT_1000xp_b.png (31.63 Ko)

figuresmore_armsT_1000xp_c.png (38.75 Ko)

figuresmore_armsT_100xp_a.png (43.56 Ko)

figuresmore_armsT_100xp_b.png (36.11 Ko)

figuresmore_armsT_100xp_c.png (29.14 Ko)

figuresmultiple_opt_armsrun_100.png (37.25 Ko)

figuressimilar_arms_orderingnu.png (33.56 Ko)

figuressimilar_arms_orderingone_bandit.png (41.65 Ko)

figuressimilar_arms_orderingsetting_nu.png (50.29 Ko)

figurestwo_armsT_tuneT_10000.jpg (87.09 Ko)

figurestwo_armsT_tuneT_10000.png (34.15 Ko)

figurestwo_armsT_tuneT_500.jpg (111.93 Ko)

figurestwo_armsT_tuneT_500.png (48.11 Ko)

figurestwo_armsT_tuneT_5000.jpg (79.41 Ko)

figurestwo_armsT_tuneT_5000.png (34.44 Ko)

figurestwo_armsT_tunefalse_positive_ratesT_10000.jpg (64.4 Ko)

figurestwo_armsT_tunefalse_positive_ratesT_500.jpg (89.39 Ko)

figurestwo_armsT_tunefalse_positive_ratesT_5000.jpg (65.43 Ko)

figurestwo_armsT_tunefalse_positive_ratesrates_10000.jpg (105.48 Ko)

figurestwo_armsT_tunefalse_positive_ratesrates_500.pdf (90.16 Ko)

figurestwo_armsT_tunefalse_positive_ratesrates_5000.pdf (225.67 Ko)

figurestwo_armsgamma_tunealpha_0.jpg (105.95 Ko)

figurestwo_armsgamma_tunexp1_a.png (40.58 Ko)

figurestwo_armsgamma_tunexp1_a_.jpg (111.02 Ko)

figurestwo_armsgamma_tunexp1_b.png (37.91 Ko)

figurestwo_armsgamma_tunexp1_b_.jpg (88.79 Ko)

figurestwo_armsgamma_tunexp1_c.png (34.07 Ko)

figurestwo_armsgamma_tunexp1_c_.jpg (89.05 Ko)

main (2).pdf (84.93 Ko)

main.synctex (1).gz (8.7 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Hassan SABER : Connectez-vous pour contacter le contributeur

https://hal.science/hal-03286539

Soumis le : jeudi 9 septembre 2021-13:50:03

Dernière modification le : mercredi 17 avril 2024-11:15:22

Archivage à long terme le : vendredi 10 décembre 2021-18:02:12

Dates et versions

hal-03286539 , version 1 (09-09-2021)

Identifiants

HAL Id : hal-03286539 , version 1

Citer

Hassan Saber, Léo Saci, Odalric-Ambrym Maillard, Audrey Durand. Routine Bandits: Minimizing Regret on Recurring Problems. ECML-PKDD 2021, Sep 2021, Bilbao, Spain. ⟨hal-03286539⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

ENS-PARIS CNRS INRIA CRISTAL INRIA2 PSL UNIV-LILLE CRISTAL-SCOOL ANR

153 Consultations

142 Téléchargements

Routine Bandits: Minimizing Regret on Recurring Problems

Résumé

Mots clés

Domaines

Dates et versions

Identifiants

Citer

Exporter

Collections

Partager