Révéler les bandits de graphe pour maximiser l'influence locale

Nous étudions un cadre de bandit de graphe où l'objectif de l'apprenant est de détecter le nœud le plus influent d'un graphe en demandant le moins d'informations possible sur ce graphe. L'une des applications pertinentes de ce cadre est le marketing dans les réseaux sociaux, où le marketeur vise à trouver et à tirer parti des clients les plus influents. Les approches existantes pour les problèmes de bandit sur les graphes nécessitent soit une connaissance partielle, soit une connaissance complète du graphe. Dans cet article, nous ne supposons aucune connaissance préalable du graphe, mais nous considérons un cadre où il peut être découvert de manière progressive, séquentielle et active. À chaque tour, l'apprenant choisit un nœud du graphe et la seule information qu'il reçoit est un ensemble stochastique des nœuds que le nœud choisi influence actuellement. Pour aborder ce cadre, nous proposons BARE, une stratégie de bandit pour laquelle nous prouvons une garantie de regret qui évolue avec la dimension détectable, une quantité dépendante du problème qui est souvent beaucoup plus petite que le nombre de nœuds.