Stochastic Graphical Bilinear Bandits

Bandits Bilinéaires Graphiques Stochastiques 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.