Bandits Bilinéaires Graphiques Stochastiques
26/10/2022 à 14h00
M. Geovani RIZK présente ses travaux en soutenance le 26/10/2022 à 14h00
À l'adresse suivante : Université Paris Dauphine, Place du Maréchal de Lattre de Tassigny, 75016 Paris - Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Bandits Bilinéaires Graphiques Stochastiques
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
MM. Yann CHEVALEYRE et Rida LARAKI
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. YANN CHEVALEYRE | Professeur des universités | Université Paris Dauphine - PSL | Co-directeur de thèse |
| M. RIDA LARAKI | Directeur de recherche CNRS | Université Paris Dauphine - PSL | Co-directeur de thèse |
| Mme EMILIE KAUFMANN | Chargé de recherche CNRS | Université de Lille | Rapporteure |
| M. Panayotis MERTIKOPOULOS | Chargé de recherche | CNRS - INRIA/LIG | Rapporteur |
| Mme MARTA SOARE | Maître de conférences | Université d'Orléans | Examinatrice |
| M. VIANNEY PERCHET | Professeur des universités | ENSAE | Examinateur |
| M. GILLES STOLTZ | Directeur de recherche CNRS | Université Paris Saclay | Examinateur |
| M. IGOR COLIN | Senior Engineer | Huawei France | Invité |
| M. ALBERT THOMAS | Senior Research Engineer | Huawei France | Invité |
Résumé
Nous introduisons un nouveau modèle appelé Bandits Bilinéaires Graphiques où un apprenant (ou une entité centrale) alloue des bras aux noeuds d’un graphe et observe pour chaque arête une récompense bilinéaire bruitée représentant l’interaction entre les deux noeuds associés. Dans cette thèse, nous étudions le problème d’identification du meilleur bras et la maximisation des récompenses cumulées. Pour le premier, un apprenant veut trouver l’allocation du graphe maximisant la somme des récompenses bilinéaires obtenues à travers le graphe. Pour le second problème, au cours du processus d’apprentissage, l’apprenant doit faire un compromis entre l’exploration des bras pour acquérir une connaissance précise de l’environnement et l’exploitation des bras qui semblent être les meilleurs pour obtenir la récompense la plus élevée. Quel que soit l’objectif de l’apprenant, le modèle de bandits bilinéaires graphiques révèle un problème combinatoire sous-jacent qui est NP-Dur et qui empêche l’utilisation de tout algorithme existant pour l’identification du meilleur bras (BAI) ou pour la maximisation des récompenses cumulées. Pour cette raison, nous proposons tout d’abord un algorithme d’α-approximation pour le problème NP-Dur sous-jacent, puis nous nous attaquons aux deux problèmes mentionnés ci-dessus. En exploitant efficacement la géométrie du problème du bandit, nous proposons une stratégie d’échantillonnage aléatoire pour le problème BAI avec des garanties théoriques. En particulier, nous caractérisons l’influence de la structure du graphe (par exemple, étoile, complet ou cercle) sur le taux de convergence et proposons des expériences empiriques qui confirment cette dépendance. Pour le problème de la maximisation des récompenses cumulées, nous présentons le premier algorithme basé sur le regret pour les bandits bilinéaires graphiques utilisant le principe d’optimisme face à l’incertitude. L’analyse théorique de la méthode présentée borne l’α-regret par Õ(√T ) et souligne l’impact de la structure du graphe sur le taux de convergence. Enfin, nous démontrons par diverses expériences la validité de nos approches.