Par Baoxiang Wang

Introduction

Plus tôt cette année, j’ai pris un congé de la CUHK Shenzhen pour rejoindre l’Institut Vector en tant que chercheur invité. Le programme de chercheur invité s’adresse tant aux chercheurs en début de carrière qu’aux chercheurs établis travaillant dans la recherche en apprentissage automatique et en apprentissage profond ainsi que dans leurs applications. Cela leur donne jusqu’à un an pour venir chez 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 intérêts de recherche portent sur l’apprentissage des algorithmes au sein d’agents stratégiques. Au lieu de traiter avec des agents statiques 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 pourrait-il s’assurer que la source de données rapporte fidèlement les données?  Des problèmes similaires surviennent lors de la formation, lorsque d’autres agents ont des objectifs qui ne sont pas alignés avec l’agent de l’ego. Ces agents stratégiques pourraient adapter leurs actions selon notre processus d’apprentissage, ce qui donne des environnements d’apprentissage très non stationnaires. Michael I Jordan, professeur de génie électrique et d’informatique et professeur de statistiques à l’UC Berkeley, a Déjà discuté Tiens Comment l’apprentissage automatique se mélange à la théorie des jeux pour mieux aligner avec les problèmes pratiques.

Mes motivations pour travailler sur des contextes de théorie des jeux dans l’apprentissage automatique sont doubles. La première consiste à mieux comprendre comment les algorithmes d’apprentissage fonctionnent dans des environnements stratégiques. Nous visons à étendre les résultats de l’analyse des algorithmes en mode agent unique aux paramètres multi-agents. La seconde consiste à utiliser la caractérisation des jeux pour comprendre l’interaction entre agents stratégiques (certains problèmes ouverts sont décrits en détail dans ce préprint). 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 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.

Dynamiques d’apprentissage sans regrets dans les jeux

L’un des concepts de solution les plus populaires dans les contextes 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 algorithmique des jeux pour plus de contexte). Elle caractérise un état stable entre les joueurs, où aucun individu n’a d’incitation à dévier unilatéralement de sa stratégie choisie. Nous mettons l’accent sur la dynamique décentralisée entre joueurs lors de parties répétées avec un retour de bandit. Dans ce scénario, sur un horizon temporel, chaque joueur choisit indépendamment une stratégie à chaque étape et reçoit un retour sur les coûts. Au-delà de l’objectif d’atteindre un équilibre de Nash, un joueur devrait essayer de minimiser le coût en supposant que les autres joueurs sont adversaires. Une notion qui évalue la performance d’un algorithme face à des adversaires potentiels est le regret, qui provient de la communauté d’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 comme étant PPAD-difficile. Il a été établi que son calcul devient plus réalisable dans des contextes de jeux spécifiques comme les jeux potentiels où une fonction potentielle peut quantifier comment 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é. Pourtant, même lorsque la fréquence empirique converge vers un équilibre, il n’est pas garanti que la dynamique globale ait évolué pour être stable à n’importe quel point d’équilibre. 

Pendant mon temps chez 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 (au sens de la dernière itération) et assure que chaque joueur ait 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, qui peut être démontré comme une borne 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 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 que nous obtenons est les bornes supérieures 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 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 enquête à des jeux monotones et fluides. Cela englobe un éventail plus large de jeux courants qui ne sont pas regroupés dans la catégorie des jeux potentiels, tels que les jeux à somme nulle à deux joueurs, les jeux convexes-concaves et les jeux polymatriciels à somme nulle. Pourtant, la convergence des algorithmes sans regret vers l’équilibre de Nash dans les parties monotones et fluides n’est pas possible à moins de supposer une rétroaction exacte du gradient et une coordination des joueurs. Dans nos travaux, nous présentons un algorithme basé sur la descente par miroir découplé 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égulariseurs : un régulateurneur de barrière auto-concordant pour construire un estimateur de gradient ellipsoïdal efficace et contester la rétroaction des bandits; et un régulariseur pour accommoder des fonctions utilitaires monotones et non fortement monotones. Dans les jeux monotones et lisses en général, notre algorithme atteint un taux de convergence de dernière itération de O(T-1/4). 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 disponibles actuellement pour les jeux fortement monotones.

Conception des mécanismes d’information parmi les agents stratégiques

Les scénarios réels sont mixtes où les agents cherchent à faire avancer leurs intérêts en façonnant le comportement des autres. Les approches y parviennent généralement par 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 joue un rôle important dans les économies modernes, avec des estimations suggérant de prendre entre 25% et 30% du PIB.

D’une part, la conception de l’information a une grande valeur économique et sociétale, incluant la vie quotidienne (financement, assurance, discrimination des prix, acheminement, divertissement), les enjeux liés aux espaces de travail (notation, recherche, approvisionnement, rétroaction des employés, concours) et des sujets sociétaux (déploiement des forces de l’ordre, tests de résistance dans le secteur financier, formation de coalitions électorales). D’un autre côté, ces sujets sont sous-étudiés dans les études existantes. Ils sont particulièrement limités à la modélisation spécifique des problèmes, comme leur conversion 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 interagir avec d’autres agents. Cela nous motive à verbaliser la persuasion bayésienne (BP), une formulation canonique en conception de l’information, et à proposer des solveurs à usage général dans les LLM. Plus précisément, nous associons le BP classique à un jeu verbalisé augmenté par un médiateur et proposons un algorithme généralisé de recherche d’équilibre dans l’espace des prompts. C’est la première fois que BP est étendu aux jeux réels impliquant des dialogues humains. Un jeu de matrice classique en BP appelé « lettre de recommandation » décrit comment un professeur pourrait utiliser des lettres de recommandation pour persuader un RH d’embaucher plus d’étudiants. Maintenant, le professeur dans notre cadre écrit une lettre réelle (voir cette lettre à la page 30 de notre manuscrit).

Propulsé par LLM, nous avons aussi examiné comment la BP diffère dans ses résultats d’équilibre et dans la vie réelle. Comme on pouvait s’y attendre, la persuasion (et aussi le langage facile) est beaucoup plus honnête dans la vraie vie. La première raison à cela, que nous avons prouvée dans notre manuscrit, est que BP est réductible à un jeu de négociation . L’équilibre du jeu, qui correspond à un équilibre parfait en sous-jeu en négociation, est souvent rejeté par le récepteur (celui qui écoute la persuasion) avec sa stratégie de riposte. Une telle riposte est possible tant que le receveur est conscient de la structure du jeu, ce qui, en pratique, est généralement le cas. La deuxième raison est l’alignement, où la fourniture précise d’informations est liée à des mérites tels que l’honnêteté et l’intégrité. La troisième est l’institution, où les administrateurs judiciaires sont en pratique corrélés par des mécanismes comme les systèmes de réputation. Fait intéressant, cela est observé dans nos expériences de LLM, où le comportement de persuasion des LLM montre l’émergence de la négociation dans le processus. Les résultats tirés de nos résultats suggèrent des implications potentielles pour réduire l’exploitation et améliorer l’égalité pour les agents désavantagés sur le plan informationnel. Nous sommes également enthousiastes à l’idée de poursuivre notre travail sur la persuasion des LLM et leur alignement.

Conclusion

Pendant mon temps comme chercheur invité chez Vector, j’ai eu le privilège de collaborer avec une communauté dynamique de chercheurs. Qu’il s’agisse de rencontres régulières en personne, de cafés informels ou de discussions ciblées, l’expérience était à la fois agréable et très productive. Je suis reconnaissant pour le merveilleux voyage que Vector a permis et pour les aménagements formidables offerts par le personnel et la communauté de Vector. Bien que ma visite soit terminée, nos efforts conjoints persistent. Je suis particulièrement enthousiaste à l’idée de continuer à explorer les paramètres liés à la théorie des jeux dans les algorithmes d’apprentissage, dans le but d’approfondir notre compréhension de la façon dont les agents apprenants se comportent et interagissent. En mieux comprenant les agents apprenants dans des environnements stratégiques, nous pouvons acquérir de nouvelles perspectives pour concevoir de meilleurs algorithmes et mécanismes pour leurs implications sociétales et économiques.