Par Baoxiang Wang
Présentation
Plus tôt cette année, j'ai pris un congé de l'Université chinoise de Hong Kong à Shenzhen pour me joindre à l'Institut Vector en tant que chercheur invité. Le programme de chercheurs invités s'adresse aux chercheurs en début de carrière ainsi qu'aux chercheurs confirmés travaillant dans le domaine de l'apprentissage automatique et de l'apprentissage profond, ainsi que sur leurs applications. Il leur offre jusqu'à un an pour venir à Vector, accéder à nos ressources et collaborer avec notre communauté. De janvier à août, j'ai travaillé avec les plus grands experts en intelligence artificielle et j'ai cherché à repousser les limites de ce que l'IA peut accomplir.
Mes recherches portent sur l'apprentissage machine au sein d'agents stratégiques. Au lieu de considérer des agents et des données statiques, nous étudions des scénarios où l'agent apprenant ne peut pas dicter le comportement des autres « composantes » du processus d'apprentissage. Par exemple, lors de la collecte de données pour entraîner un prédicteur, comment l'agent peut-il s'assurer de la fiabilité des données fournies par la source ? Des problèmes semblables surviennent pendant l'entraînement, lorsque d'autres agents ont des objectifs non alignés sur ceux de l'agent principal. Ces agents stratégiques peuvent adapter leurs actions en fonction de notre processus d'apprentissage, ce qui engendre des environnements d'apprentissage fortement non stationnaires. Michael I. Jordan, professeur de génie électrique et d'informatique et professeur de statistique à l'UC Berkeley, a déjà abordé ici la manière dont l'apprentissage machine s'articule avec la théorie des jeux pour une meilleure adéquation aux problèmes pratiques.
Mes motivations pour travailler sur les cadres théoriques des jeux appliqués à l'apprentissage machine sont doubles. Premièrement, j'aimerais mieux comprendre le comportement des algorithmes d'apprentissage dans des environnements stratégiques. Notre objectif est d'étendre les résultats de l'analyse des algorithmes dans le cadre d'un seul agent à des contextes multi-agents. Deuxièmement, j'utilise la caractérisation des jeux pour comprendre l'interaction entre agents stratégiques (certains problèmes ouverts sont décrits en détail dans cette prépublication ). Cela nous permet de concevoir de meilleurs mécanismes pour promouvoir la coopération, améliorer le bien-être social, réduire l'exploitation et renforcer l'égalité. Lors de mon séjour, j'ai eu la chance de collaborer avec les chercheurs de Vector, Yaoliang Yu (mon hôte), Pascal Poupart et William Cunningham, sur plusieurs problèmes liés à ce sujet.
Dynamique d'apprentissage sans regret dans les jeux
L'un des concepts de solutions les plus populaires dans les systèmes multi-agents est l'équilibre de Nash , issu de la théorie des jeux et décrivant le comportement de joueurs rationnels et égoïstes (voir cet article sur la théorie algorithmique des jeux pour plus de contexte). Il caractérise un état stable entre les joueurs, où aucun individu n'a intérêt à dévier unilatéralement de sa stratégie. Nous nous intéressons à la dynamique décentralisée entre les joueurs dans les jeux répétés avec rétroaction de type bandit. Dans ce scénario, sur un horizon temporel donné, chaque joueur choisit indépendamment une stratégie à chaque étape et reçoit une rétroaction sur son coût. Outre l'objectif d'atteindre un équilibre de Nash, un joueur doit chercher à minimiser le coût subi tout en supposant que les autres joueurs sont hostiles. La notion de regret, issue du domaine de l'apprentissage en ligne, permet d'évaluer la performance d'un algorithme face à d'éventuels adversaires. Les algorithmes qui atteignent un regret sous-linéaire sont appelés algorithmes sans regret.
Pour les jeux généraux, la résolution d'un équilibre de Nash est connue pour être PPAD-difficile . Il a été établi que son calcul devient plus faisable dans des contextes de jeux spécifiques, comme les jeux de potentiel, où une fonction de potentiel permet de quantifier l'impact des changements de stratégie individuelle sur l'utilité collective. Un résultat important qui établit le lien entre l'apprentissage sans regret et l'équilibre de Nash est que la fréquence empirique des stratégies jouées par un algorithme d'apprentissage sans regret forme un équilibre corrélé. Cependant, même lorsque la fréquence empirique converge vers un équilibre, la stabilité de la dynamique globale à chaque point d'équilibre n'est pas garantie.
Durant mon passage chez Vector, on a travaillé sur deux types de jeux. Le premier est le jeu potentiel et son extension, le jeu potentiel de Markov. Dans ce travail , nous avons introduit une variante de l'algorithme de Frank-Wolfe avec exploration et estimation récursive du gradient, qui converge rapidement vers l'équilibre de Nash (au sens de la dernière itération) et garantit un regret sous-linéaire pour chaque joueur. Notre algorithme tire parti de la capacité de l'algorithme de Frank-Wolfe à contrôler l'écart de dualité du jeu, qui constitue une borne supérieure de l'écart à un équilibre de Nash. Cela nous permet d'analyser directement la capacité de Frank-Wolfe à résoudre les équilibres de Nash, sans recourir aux liens précédemment mentionnés entre l'apprentissage sans regret et la recherche d'équilibres. Afin d'assurer une convergence efficace vers l'équilibre de Nash, nous utilisons un gradient récursif pour réduire l'erreur d'estimation. Le résultat obtenu fournit des bornes supérieures pour le regret de Nash et un regret de O(T⁴/⁵), où T représente la durée de l'horizon temporel (ce qui implique une vitesse de convergence de O(T⁻¹/⁵)). Ce résultat peut être étendu aux jeux à potentiel markovien, qui ont des applications importantes comme le routage en cas de congestion routière.
Au-delà des jeux potentiels, nous étendons notre étude aux jeux monotones et lisses. Cela englobe un plus large éventail de jeux courants non couverts par la classe des jeux potentiels, tels que les jeux à somme nulle à deux joueurs, les jeux convexes-concaves et les jeux à somme nulle à matrices polynomiales. Cependant, la convergence des algorithmes sans regret vers l'équilibre de Nash dans les jeux monotones et lisses n'est possible que si l'on suppose une rétroaction exacte du gradient et une coordination entre les joueurs. Dans nos travaux , nous présentons un algorithme découplé basé sur la descente miroir, conçu pour converger vers l'équilibre de Nash dans les jeux monotones et lisses en général. Pour étendre l'algorithme classique de descente miroir à un jeu monotone, nous utilisons deux régularisateurs : un régularisateur de barrière auto-concordant pour construire un estimateur de gradient ellipsoïdal efficace et contrer la rétroaction du bandit ; et un régularisateur pour tenir compte des fonctions d'utilité monotones et non fortement monotones. Dans les jeux monotones et lisses en général, notre algorithme atteint un taux de convergence à la dernière itération de O(T⁻¹/⁴). Dans les cas où le jeu présente une forte monotonie, notre résultat s'améliore à O(T-1/2), correspondant aux meilleurs taux de convergence actuellement disponibles pour les jeux fortement monotones.
Conception de mécanismes d'information entre agents stratégiques
En réalité, les situations sont souvent caractérisées par des motivations mixtes : les agents cherchent à promouvoir leurs intérêts en influençant le comportement d’autrui. Les approches employées y parviennent généralement grâce à des mécanismes d’incitation (modification des gains), des mécanismes d’information (modification des observations) ou des méthodes indirectes (comme les systèmes de réputation et les institutions). Le problème que nous étudions est la conception des mécanismes d’information, qui jouent un rôle prépondérant dans les économies modernes, représentant, selon les estimations, entre 25 % et 30 % du PIB.
D'une part, la conception de l'information revêt une grande importance économique et sociétale, notamment dans la vie quotidienne (finances, assurances, discrimination par les prix, itinéraires, divertissement), les problématiques liées à l'espace de travail (évaluation, acquisition de données pour la recherche, rétroactions des employés, concours) et les enjeux de société (déploiement des forces de l'ordre, tests de résistance du secteur financier, formation de coalitions d'électeurs). D'autre part, ces sujets sont insuffisamment explorés dans les études existantes. Celles-ci se limitent souvent à une modélisation spécifique des problèmes, comme leur conversion en jeux matriciels.
Avec l'essor des jeux de simulation linguistique (LLM), il est maintenant possible d'utiliser le langage naturel pour décrire et interpréter une tâche, ainsi que pour interagir avec d'autres agents. Cela nous incite à verbaliser la persuasion bayésienne (PB), une formulation canonique en conception de l'information, et à proposer des solveurs génériques pour les LLM. Plus précisément, nous transposons la PB classique en un jeu augmenté par un médiateur et verbalisé, et proposons un algorithme généralisé de recherche d'équilibre dans l'espace des invites. C'est la première fois que la PB est étendue à des jeux du monde réel impliquant des dialogues humains. Un jeu matriciel classique de PB, appelé « lettre de recommandation », décrit comment un professeur pourrait utiliser des lettres de recommandation pour persuader un gestionnaire des ressources humaines d'embaucher plus d'étudiants. Dans notre cadre, le professeur rédige une vraie lettre (voir cette lettre à la page 30 de notre manuscrit ).
Grâce à la modélisation linéaire en langage naturel (LLM), nous avons également examiné les différences entre les résultats d'équilibre de la persuasion persuasive (BP) et ses résultats concrets. Comme on pouvait s'y attendre, la persuasion (et les discours creux) est bien plus honnête dans la réalité. La première raison, que nous avons démontrée dans notre article , est que la BP se réduit à un jeu de négociation . L'équilibre du jeu, qui correspond à un équilibre parfait en sous-jeu dans la négociation, est généralement rejeté par le destinataire (celui qui écoute la persuasion) grâce à une stratégie de représailles. Ces représailles sont possibles tant que le destinataire est conscient de la structure du jeu, ce qui est généralement le cas en pratique. La deuxième raison est l'alignement, où la fourniture d'informations exactes est liée à des mérites tels que l'honnêteté et l'intégrité. La troisième raison est l'institution, où les destinataires sont corrélés en pratique par des mécanismes comme les systèmes de réputation. Il est intéressant de noter que ces phénomènes sont observés dans nos expériences LLM, où le comportement persuasif des modèles LLM met en évidence l'émergence de la négociation dans le processus. Nos résultats suggèrent des pistes prometteuses pour réduire l'exploitation et renforcer l'égalité des personnes en situation de désavantage informationnel. Nous avons également hâte de poursuivre nos recherches sur la force persuasive des modèles linguistiques et leur harmonisation.
Conclusion
Durant mon temps en tant que chercheuse invitée chez Vector, j'ai eu le privilège de collaborer avec une communauté de chercheurs dynamique. Qu'il s'agisse de réunions régulières en personne, de discussions informelles autour d'un café ou d'échanges plus approfondis, l'expérience a été à la fois enrichissante et extrêmement productive. Je suis reconnaissante à Vector pour cette formidable opportunité et pour l'accueil exceptionnel qu'ils m'ont réservé. Bien que mon séjour soit terminé, notre collaboration se poursuit. Je suis particulièrement enthousiaste à l'idée de continuer à explorer les cadres théoriques de la théorie des jeux appliqués aux algorithmes d'apprentissage, afin d'approfondir notre compréhension du comportement et des interactions des agents apprenants. Une meilleure compréhension de ces agents dans des environnements stratégiques nous permettra de concevoir des algorithmes et des mécanismes plus performants, et d'en tirer des leçons précieuses sur leurs implications sociétales et économiques.
Collaborer avec les chercheurs de Vector
Joignez-vous à une communauté dynamique de plus de 860 chercheurs à l'Institut Vector de Toronto. Notre programme de chercheurs invités offre des ressources informatiques de pointe, un soutien spécialisé en ingénierie de l'IA et de nombreuses opportunités de collaboration aux chercheurs en année sabbatique ou prenant une année sabbatique entre deux étapes importantes de leur parcours universitaire.
