🤖 machine learning

GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning

Ce papier présente l'optimisation de politique à variance réduite (VRPO), un nouvel algorithme qui utilise un estimateur d'avantage à variance réduite par renforcement de $Q$ pour surmonter la forte variance inhérente à l'estimation d'avantage généralisée standard pour l'auto-jeu à information imparfaite, permettant ainsi d'obtenir des performances supérieures dans les jeux multi-agents compétitifs comme Dou Dizhu et le Texas Hold'em sans limite à tête-à-tête.

Auteurs originaux : Zhiyuan Fan, Gabriele Farina

Publié 2026-05-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zhiyuan Fan, Gabriele Farina

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous enseignez à un groupe de robots un jeu de cartes complexe comme le Poker ou le Dou Dizhu (un jeu de cartes chinois populaire). Le hic ? Ils ne peuvent pas voir les cartes des autres, et ils affrontent des adversaires qui tentent de les tromper. Pour gagner, les robots doivent apprendre une stratégie si équilibrée et imprévisible qu'aucun adversaire ne peut l'exploiter. Cela s'appelle trouver un « équilibre ».

Pendant longtemps, la meilleure façon d'enseigner à ces robots a été l'Auto-jeu : vous laissez les robots jouer contre des copies d'eux-mêmes des millions de fois. L'enseignant le plus populaire pour cela est un algorithme appelé PPO (Optimisation de Politique Proximale).

Cependant, les auteurs de cet article ont découvert un « bug » caché dans la façon dont le PPO enseigne aux robots dans ces jeux à cartes secrètes. Voici une analyse du problème et de leur solution, en utilisant des analogies simples.

Le Problème : Le « Chuchotement Bruyant » dans une Salle Bondée

Dans le PPO standard, le robot apprend en examinant un chemin qu'il a emprunté dans le passé et en se demandant : « Était-ce un bon coup ? » Pour répondre, il utilise un outil appelé GAE (Estimation Généralisée de l'Avantage).

Imaginez le GAE comme un entraîneur qui chuchote des conseils à un joueur basé sur un replay du match.

Dans un jeu simple (comme les Échecs) : L'avenir est prévisible. Si l'entraîneur dit : « Tu as déplacé le pion ici, et cela a mené à une victoire », le joueur sait exactement pourquoi.
Dans un jeu à cartes secrètes (comme le Poker) : L'avenir est rempli d'aléas. Le chuchotement de l'entraîneur devient brouillé car le robot doit deviner ce que les autres robots pourraient faire ensuite. Comme les robots jouent de manière aléatoire (pour garder leurs adversaires dans le doute), les conseils de l'entraîneur deviennent un « chuchotement bruyant ».

L'Analogie : Imaginez essayer d'apprendre une chorégraphie dans une pièce où tout le monde tourne dans des directions aléatoires.

L'Ancienne Méthode (GAE) : L'entraîneur essaie de vous dire : « Si vous faites un pas à gauche, vous serez en sécurité. » Mais parce que tout le monde tourne de façon folle, la voix de l'entraîneur est noyée dans le chaos. Le robot entend : « Faites un pas à gauche... peut-être ? Ou peut-être à droite ? C'est difficile à dire ! » Ce « bruit » rend l'apprentissage du robot instable et lent.
La Découverte de l'Article : Même si l'entraîneur est parfait (il possède une connaissance parfaite du jeu), le bruit vient du fait que les autres danseurs tournent de manière aléatoire. Le robot ne peut pas distinguer un mauvais coup d'une simple malchance causée par l'aléatoire des autres joueurs.

La Solution : « Q-Boosting » (La Boule de Cristal)

Les auteurs ont inventé un nouvel outil appelé Q-Boosting pour corriger ce bruit.

Au lieu que l'entraîneur devine ce qui va se passer ensuite basé sur un seul replay aléatoire, le Q-Boosting demande à l'entraîneur d'examiner tous les futurs possibles à la fois et de les moyenner.

L'Analogie : Au lieu que l'entraîneur dise : « Je vous ai vu faire un pas à gauche, et cette fois précise quelqu'un est entré en collision avec vous », le nouvel entraîneur dit : « J'ai calculé que si vous faites un pas à gauche, 50 % du temps vous serez en sécurité, 30 % du temps vous serez bloqué, et 20 % du temps vous serez trébuché. En moyenne, faire un pas à gauche est une bonne idée. »

En faisant les calculs pour moyenner l'aléatoire avant de donner le conseil, l'entraîneur élimine le « bruit ». Le robot reçoit un signal clair et calme : « Ce coup est bon en moyenne », plutôt que « Ce coup était bon cette fois précise mais peut-être mauvais cette autre fois ».

Ils appellent cette nouvelle méthode d'enseignement VRPO (Optimisation de Politique à Variance Réduite).

Les Résultats : Des Robots Plus Intelligents, Des Victoires Plus Rapides

L'article a testé cette nouvelle méthode (VRPO) contre l'ancienne norme (PPO) dans plusieurs jeux :

Petits Jeux (La Cuisine d'Essai) : Ils ont joué à des jeux comme « Les Dés du Mensonge » et « Le Morpion Fantôme ». Dans ces jeux, ils pouvaient prouver mathématiquement la qualité du robot.
- Résultat : VRPO a appris une stratégie bien plus forte que le PPO. Il était plus difficile à tromper, ce qui signifie qu'il était plus proche de la stratégie d'« équilibre » parfaite.
Jeux Moyens (L'Arène) : Ils ont joué au Dou Dizhu (un jeu de cartes complexe à trois joueurs).
- Résultat : VRPO a battu la meilleure IA précédente (appelée PerfectDou) lors de matchs directs, même s'ils ont utilisé la même puissance de calcul. Il a appris à gagner plus souvent.
Grands Jeux (Le Championnat) : Ils ont essayé le Texas Hold'em sans limite à deux joueurs (une variante de poker à enjeux élevés).
- Résultat : VRPO a très bien performé contre un puissant bot de poker nommé Slumbot. Il a réussi à gagner de l'argent sur une longue session sans avoir besoin de « tricher » comme en regardant les cartes futures ou en faisant des calculs complexes pendant le jeu. Il a simplement appris une meilleure stratégie grâce à l'entraînement.

Résumé

L'article soutient que lorsqu'on enseigne aux robots à jouer à des jeux à cartes secrètes, l'ancienne méthode d'apprentissage (GAE) se confond à cause de l'aléatoire des autres joueurs. La nouvelle méthode (VRPO avec Q-Boosting) agit comme un entraîneur sur-intelligent qui moyenne toutes les possibilités avant de donner des conseils. Cela élimine la confusion, permettant aux robots d'apprendre plus vite, de jouer plus stablement et de devenir beaucoup plus difficiles à battre.

Résumé Technique : GAE est Insuffisant dans l'Auto-jeu à Information Imperfaite

Énoncé du Problème

L'apprentissage par renforcement multi-agents (MARL) compétitif dans les jeux à information imparfaite nécessite que les agents opèrent sous une observabilité partielle face à des adversaires, ce qui impose des politiques stochastiques. Bien que l'apprentissage par renforcement par auto-jeu utilisant l'optimisation de politique proximale (PPO) ait connu des succès empiriques, il fait face à un goulot d'étranglement critique dans l'apprentissage d'équilibres : la variance de l'estimation de l'avantage.

Les implémentations standard de PPO reposent sur l'estimation généralisée de l'avantage (GAE) pour agréger les résidus de différence temporelle (TD) multi-étapes. Dans les environnements à agent unique, la GAE équilibre efficacement le biais et la variance. Cependant, dans l'auto-jeu à information imparfaite, les politiques d'équilibre sont intrinsèquement stochastiques. La GAE hérite du hasard issu de l'échantillonnage des actions futures au sein de sa trace multi-étapes. Étant donné que les politiques d'équilibre attribuent des valeurs différentes à différentes actions, l'échantillonnage des actions futures introduit un bruit intrinsèque. Cette variance est amplifiée dans les scénarios d'auto-jeu et persiste même lorsque le critique de valeur d'état ( $V$ -critic) est exact. Par conséquent, la GAE standard produit des estimations de gradient à haute variance précisément dans les régimes où un apprentissage stable est le plus critique, entravant la convergence vers des équilibres de haute qualité.

Méthodologie

Estimateur Q-Boosting

Pour résoudre la variance introduite par l'échantillonnage des actions, les auteurs proposent le Q-boosting, un estimateur d'avantage à variance réduite. L'innovation centrale consiste à remplacer la trace TD multi-étapes échantillonnée utilisée dans la GAE par une trace Expected SARSA( $\lambda$ ) multi-étapes calculée à partir d'un critique d'action centralisé ( $Q$ -critic).

Mécanisme : Au lieu de faire du bootstrap via des actions suivantes échantillonnées (ce qui introduit du bruit), le Q-boosting calcule les espérances de politique à chaque étape de sauvegarde. Il moyenne le bruit provenant des actions futures stochastiques en prenant l'espérance sur la distribution d'actions définie par la politique actuelle.
Formulation : Étant donné un critique $Q$ centralisé $Q_i(s, a)$ et une politique conjointe $\pi$ , la valeur d'état est calculée comme $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$ . L'estimation d'avantage Q-boosting $\hat{A}^{boost}_{i,\tau}$ est définie comme suit :
$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$
où le résidu TD Expected SARSA est $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$ .
Garantie Théorique : Les auteurs prouvent que pour des trajectoires on-policy et $\lambda=1$ , l'estimateur Q-boosting fournit une estimation sans biais du terme de gradient de politique de fonction de score. De plus, si le critique $Q$ est suffisamment précis, l'erreur quadratique moyenne de l'estimateur Q-boosting est strictement inférieure à celle de la GAE avec un critique $V$ exact, à condition que les actions futures présentent une variance non nulle dans leurs valeurs d'action.

Optimisation de Politique à Variance Réduite (VRPO)

Les auteurs intègrent le Q-boosting dans un algorithme de type PPO nommé Optimisation de Politique à Variance Réduite (VRPO).

Architecture : VRPO suit le paradigme de l'entraînement centralisé avec exécution décentralisée (CTDE). Il utilise des acteurs décentralisés pour l'exécution et un critique $Q$ centralisé pour l'entraînement.
Objectif : L'algorithme conserve la fonction objectif de substitution tronquée de PPO et les mises à jour de région de confiance, mais modifie les procédures d'estimation d'avantage et d'apprentissage du critique.
Procédure d'Entraînement :
1. Mise à jour de l'Acteur : Les acteurs sont mis à jour en utilisant les estimations d'avantage Q-boosting. Pour maintenir les propriétés on-policy, les termes d'espérance de politique dans le calcul de l'avantage sont recalculés en utilisant les probabilités de l'acteur actuel tout en maintenant les valeurs du critique fixes.
2. Mise à jour du Critique : Les critiques $Q$ centralisés sont entraînés en minimisant la perte de régression quadratique par rapport à la cible Q-boosting (une trace Expected SARSA multi-étapes).
3. Régularisation : Une pénalité explicite de divergence KL par rapport à une distribution uniforme est ajoutée à la fonction objectif de la politique pour favoriser l'exploration et encourager la convergence à la dernière itération.
Gestion des Grands Espaces d'Actions : Pour les jeux avec des ensembles d'actions massifs (par exemple, Dou Dizhu), les auteurs décomposent les décisions complexes en plusieurs étapes temporelles. Cela réduit le nombre d'actions disponibles par étape à une taille gérable, permettant l'énumération requise pour l'espérance de politique dans la trace Q-boosting.

Contributions Clés

Identification de la Source de Variance : L'article identifie que l'échantillonnage des actions futures dans la GAE introduit une variance supplémentaire dans l'auto-jeu stochastique, qui persiste même avec des fonctions de valeur exactes.
Estimateur Q-Boosting : Les auteurs dérivent le Q-boosting, un estimateur compatible avec PPO qui applique une trace Expected SARSA( $\lambda$ ) à un critique $Q$ centralisé pour moyenner le bruit de l'échantillonnage des actions futures.
Algorithme VRPO : La proposition de VRPO, un algorithme de type PPO qui exploite le Q-boosting pour atteindre une stabilité et des performances améliorées.
Validation Empirique : Démonstration que la réduction de la variance de l'estimation de l'avantage produit des gains substantiels dans la qualité des équilibres à travers des jeux de différentes échelles.

Résultats Expérimentaux

Jeux de Taille Moyenne (Exploitabilité Exacte)

Les auteurs ont évalué VRPO sur des jeux de taille moyenne où l'exploitabilité exacte peut être calculée : Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3) et Liar's Dice avec 2 dés et 5 faces (LiDi 2D5F).

Performance : VRPO a systématiquement atteint une exploitabilité inférieure de plus de 15 % par rapport à diverses bases de référence basées sur PPO (IPPO, MAPPO, MMD, PPG) sous un calendrier d'entraînement partagé.
Ablation : Les expériences ont confirmé que les gains de performance sont robustes face à différents paramètres de trace ( $\lambda$ ), coefficients de régularisation ( $\alpha$ ) et coefficients de troncature PPO ( $\epsilon$ ).

Jeux à Grande Échelle

Les auteurs ont évalué VRPO dans des domaines à grande échelle où l'exploitabilité exacte est intraitable.

Dou Dizhu : VRPO a été entraîné contre l'agent précédent de l'état de l'art, PerfectDou. Avec un budget d'entraînement équivalent ( $\approx 2,65 \times 10^9$ pas de temps), VRPO a surpassé PerfectDou après seulement 40 % des étapes d'entraînement. Lors d'évaluations en tête-à-tête sur 100 000 don, VRPO a réalisé des gains positifs contre PerfectDou, DouZero et lui-même (dans des confrontations avec échange de rôles), établissant un nouvel état de l'art.
Heads-Up No-Limit Texas Hold'em (HUNL) : VRPO a été entraîné sur HUNL avec une pile de 200 big blinds. Comparé à IPPO et MAPPO, VRPO a considérablement réduit l'écart-type des estimations d'avantage pendant l'entraînement. Contre la base de référence solide Slumbot, l'agent VRPO a réalisé un gain moyen de $33 \pm 19$ mBB/main sur 1 000 000 de mains. Fait notable, cette performance a été obtenue sans recherche en ligne, résolution de sous-jeux ou dimensionnement des relances basé sur des plans préétablis.

Signification et Portée

L'article affirme que la contribution principale est l'identification de la variance de l'estimation de l'avantage comme un goulot d'étranglement dans l'auto-jeu d'équilibre et la démonstration que le Q-boosting atténue efficacement ce problème. Les résultats suggèrent que la réduction de la variance dans l'estimation de l'avantage peut produire des gains substantiels dans la qualité des équilibres appris.

Les auteurs maintiennent une portée modeste concernant leurs affirmations :

L'approche est validée pour les jeux avec de grands ensembles d'actions discrètes (via décomposition) mais ne traite pas des espaces d'actions continus de haute dimension.
L'accent empirique est mis sur l'auto-jeu stochastique avec des critiques centralisés ; les auteurs ne revendiquent pas d'améliorations générales sur la GAE dans les benchmarks standard d'apprentissage par renforcement à agent unique.
La méthode repose sur la capacité de calculer des espérances de politique sur les actions, ce qui est réalisable dans les domaines testés mais peut nécessiter des considérations architecturales spécifiques pour des espaces d'actions extrêmement vastes.

En conclusion, VRPO représente une avancée significative dans l'application des méthodes de gradient de politique aux jeux à information imparfaite en traitant une source spécifique, précédemment sous-identifiée, de variance inhérente à l'apprentissage d'équilibres stochastiques.