Mon mandat de chercheur invité à l'Institut Vecteur

13 décembre 2024

2024 Recherche Recherche 2024

Par Baoxiang Wang

Introduction

Au début de cette année, j'ai pris un congé de CUHK Shenzhen pour rejoindre l'Institut Vecteur en tant que chercheur invité. Le programme de chercheurs invités s'adresse aux chercheurs en début de carrière et aux chercheurs confirmés qui travaillent dans le domaine de l'apprentissage automatique et de l'apprentissage profond, ainsi que de leurs applications. Il leur donne jusqu'à un an pour venir à Vector, accéder à nos ressources et collaborer avec sa communauté. De janvier à août, j'ai travaillé avec les plus grands esprits de l'IA et tenté de repousser les limites de ce que l'IA peut accomplir.

Mes recherches portent sur les algorithmes d'apprentissage au sein d'agents stratégiques. Au lieu de traiter avec des agents statiques et des données statiques, nous étudions des scénarios dans lesquels l'agent d'apprentissage ne peut pas dicter le comportement d'autres "composants" du processus d'apprentissage. Par exemple, lors de la collecte de données pour former un prédicteur, comment l'agent pourrait-il s'assurer que la source de données rapporte fidèlement les données ? Des problèmes similaires se posent pendant la formation, lorsque d'autres agents ont des objectifs qui ne sont pas alignés sur ceux de l'agent ego. Ces agents stratégiques pourraient adapter leurs actions en fonction de notre processus d'apprentissage, ce qui donnerait lieu à des environnements d'apprentissage hautement non stationnaires. Michael I Jordan, professeur de génie électrique et d'informatique et professeur de statistiques à l'université de Berkeley, a déjà expliqué ici comment l'apprentissage automatique s'allie à la théorie des jeux pour mieux s'aligner sur les problèmes pratiques.

Mes motivations pour travailler sur la théorie des jeux dans le domaine de l'apprentissage automatique sont doubles. La première est de mieux comprendre comment les algorithmes d'apprentissage fonctionnent dans des environnements stratégiques. Nous souhaitons étendre les résultats de l'analyse des algorithmes dans le cadre d'un seul agent à des environnements multi-agents. Le second est d'utiliser la caractérisation des jeux pour comprendre l'interaction entre les agents stratégiques (certains problèmes ouverts sont décrits en détail dans ce document). 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é. Au cours de ma visite, j'ai eu la chance de travailler 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 solution les plus populaires dans les environnements multi-agents est l'équilibre de Nash, qui trouve son origine dans la théorie des jeux et décrit les comportements de joueurs rationnels et égoïstes (voir cet article sur la théorie des jeux algorithmiques pour plus de contexte). Il caractérise un état stable entre les joueurs, où aucun individu n'a intérêt à s'écarter unilatéralement de la stratégie qu'il a choisie. Nous nous concentrons sur la dynamique décentralisée entre les joueurs dans les jeux répétés avec rétroaction des bandits. Dans ce scénario, sur un horizon temporel, chaque joueur choisit indépendamment une stratégie à chaque étape et reçoit des informations sur les coûts. Au-delà de l'objectif d'arriver à un équilibre de Nash, un joueur doit essayer de minimiser les coûts subis tout en supposant que les autres joueurs sont adversaires. Une notion qui évalue la performance d'un algorithme en présence d'adversaires possibles est le regret, qui provient de la communauté de l'apprentissage en ligne, et les algorithmes qui atteignent des regrets sous-linéaires sont appelés algorithmes sans regret. 

Pour les jeux généraux, cependant, la résolution d'un équilibre de Nash est connue pour être PPAD-Hard. Il a été établi que le calcul de l'équilibre de Nash devient plus facile dans des contextes de jeu spécifiques tels que les jeux potentiels où une fonction potentielle peut quantifier la façon dont les changements de stratégie individuels affectent 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, il n'est pas garanti que la dynamique globale évolue vers la stabilité à n'importe quel point d'équilibre. 

Pendant mon séjour à Vector, nous avons travaillé sur deux types de jeux. Le premier type est le jeu potentiel et son extension de 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 (dans le sens du dernier itéré) et assure à chaque joueur un regret sous-linéaire. Notre algorithme tire parti de la capacité de l'algorithme de Frank-Wolfe à contrôler l'écart de dualité du jeu, dont on peut montrer qu'il s'agit d'une limite supérieure de l'écart vers un équilibre de Nash. Cela nous permet d'analyser directement la capacité de Frank-Wolfe à résoudre les équilibres de Nash, sans utiliser les liens mentionnés précédemment entre l'apprentissage sans regret et les résultats d'équilibre. Pour garantir une convergence efficace vers l'équilibre de Nash, nous utilisons un gradient récursif pour réduire l'erreur d'estimation. Le résultat que nous obtenons est une borne supérieure pour le regret de Nash et le regret de O(T4/5), où T est la longueur de l'horizon temporel (ce qui implique un taux de convergence de O(T-1/5)). Ce résultat peut être étendu aux jeux potentiels de Markov, qui ont des applications importantes comme le routage dans les embouteillages.

Au-delà des jeux potentiels, nous étendons notre étude aux jeux monotones et lisses. Cela permet d'englober un plus large éventail de jeux courants qui ne sont pas pris en compte par la classe des jeux potentiels, tels que les jeux à somme nulle à deux joueurs, les jeux convexes-concaves et les jeux polymatrix à somme nulle. Pourtant, la convergence des algorithmes sans regret vers l'équilibre de Nash dans les jeux monotones et lisses n'est pas disponible, sauf si l'on suppose un retour de gradient exact et une coordination des joueurs. Dans notre travail, nous présentons un algorithme non couplé basé sur la descente en miroir conçu pour converger vers l'équilibre de Nash dans les jeux monotones et lisses généraux. Pour étendre l'algorithme classique de descente en miroir à un jeu monotone, nous utilisons deux régularisateurs : un régularisateur à barrière autoconcordante pour construire un estimateur de gradient ellipsoïdal efficace et contester la rétroaction du bandit ; et un régularisateur pour prendre en compte les fonctions d'utilité monotones et non fortement monotones. Dans les jeux généraux monotones et lisses, notre algorithme atteint un taux de convergence au dernier tour de O(T-1/4). Dans les cas où le jeu présente une forte monotonicité, notre résultat s'améliore pour atteindre O(T-1/2), ce qui correspond aux meilleurs taux de convergence actuellement disponibles pour les jeux fortement monotones.

Conception de mécanismes d'information entre agents stratégiques

Les scénarios du monde réel sont mixtes, les agents cherchant à promouvoir leurs intérêts en influençant le comportement des autres. Les approches permettent généralement d'atteindre cet objectif par le biais de mécanismes d'incitation (modification des gains), de mécanismes d'information (modification des observations) ou de méthodes indirectes (telles que les systèmes de réputation et les institutions). Le problème que nous étudions est celui de la conception des mécanismes d'information, qui joue un rôle important dans les économies modernes, les estimations suggérant qu'ils représentent 25 à 30 % du PIB.

D'une part, la conception de l'information a une grande valeur économique et sociétale, notamment dans la vie quotidienne (financement, assurance, discrimination par les prix, routage, divertissement), dans l'espace de travail (classement, acquisition de recherches, retour d'information des employés, concours) et dans des sujets sociétaux (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 peu étudiés dans les études existantes. Elles se limitent en particulier à une modélisation spécifique des problèmes, par exemple en les convertissant en jeux matriciels.

Avec l'essor des LLM, il est désormais possible d'utiliser le langage naturel pour décrire et interpréter la tâche et pour interagir avec d'autres agents. Ceci nous motive à verbaliser la persuasion bayésienne (BP), une formulation canonique dans la conception de l'information, et à proposer des solveurs généraux dans les LLM. Plus précisément, nous transposons la persuasion bayésienne classique à un jeu verbalisé augmenté d'un médiateur et nous proposons un algorithme généralisé de recherche d'équilibre dans l'espace d'invite. C'est la première fois que la BP est étendue à des jeux du monde réel impliquant des dialogues humains. Un jeu matriciel classique de la BP, appelé "lettre de recommandation", décrit comment un professeur peut utiliser des lettres de recommandation pour persuader un RH d'embaucher davantage d'étudiants. Dans notre cadre, le professeur écrit une lettre réelle (voir cette lettre à la page 30 de notre manuscrit).

Grâce au LLM, nous avons également examiné les différences entre les résultats d'équilibre et les résultats réels de la BP. Comme on peut s'y attendre, la persuasion (ainsi que les paroles faciles) est beaucoup plus honnête dans la vie réelle. La première raison à cela, que nous avons prouvée dans notre manuscrit, est que la BP est réductible à un jeu de négociation. L'équilibre du jeu, qui correspond à un équilibre parfait en négociation, est généralement rejeté par le destinataire (celui qui écoute la persuasion) avec sa 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 dans la pratique. La deuxième raison est l'alignement, car 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 : dans la pratique, les destinataires sont corrélés par des mécanismes tels que les systèmes de réputation. Il est intéressant de noter que ces éléments sont observés dans nos expériences de LLM, où le comportement de persuasion des LLM met en évidence l'émergence de la négociation dans le processus. Nos résultats suggèrent des implications potentielles pour la réduction de l'exploitation et l'amélioration de l'égalité pour les agents désavantagés sur le plan de l'information. Nous sommes également enthousiastes à l'idée de poursuivre nos travaux sur la persuasion des LLM et leur alignement.

Conclusion

Pendant mon séjour en tant que chercheur invité à Vector, j'ai eu le privilège de collaborer avec une communauté dynamique de chercheurs. Qu'il s'agisse de réunions régulières en personne, de discussions informelles autour d'un café ou de discussions ciblées, l'expérience a été à la fois agréable et très productive. Je suis reconnaissant au personnel et à la communauté de Vector pour le merveilleux voyage qu'ils m'ont permis de faire et pour l'accueil extraordinaire qu'ils m'ont réservé. Bien que ma visite soit terminée, nos efforts communs se poursuivent. Je suis particulièrement enthousiaste à l'idée de continuer à explorer les paramètres théoriques des algorithmes d'apprentissage, dans le but d'approfondir notre compréhension du comportement et de l'interaction des agents d'apprentissage. En comprenant mieux les agents d'apprentissage dans des environnements stratégiques, nous pouvons acquérir de nouvelles connaissances pour concevoir de meilleurs algorithmes et mécanismes pour leurs implications sociétales et économiques.

Collaborer avec les chercheurs de Vector

Rejoignez une communauté florissante de plus de 860 chercheurs à l'Institut Vecteur de Toronto. Notre programme de chercheurs invités offre des ressources informatiques de pointe, un soutien technique dédié à l'IA et de riches opportunités de collaboration pour les chercheurs en congé sabbatique ou qui prennent une année sabbatique entre deux étapes académiques.

En rapport :

2025
Recherche
Recherche 2025

Clonage de la pensée : Apprendre à l'IA à penser comme les humains pour une meilleure prise de décision

Ordinateur portable vectoriel
2025
Ingénierie de l'IA
Recherche
Recherche 2025

FairSense : Intégrer l'IA responsable et le développement durable

Des femmes écrivent sur un tableau blanc. Un homme à sa gauche regarde le tableau.
2024
Recherche
Recherche 2024

Les chercheurs de Vector présentent plus de 98 articles à NeurIPS 2024