Territory Paint Wars: Diagnosing and Mitigating Failure Modes in Competitive Multi-Agent PPO

Cet article présente l'environnement « Territory Paint Wars » pour identifier des modes d'échec critiques de l'algorithme PPO en apprentissage par renforcement multi-agent compétitif, notamment le surapprentissage compétitif, et propose une solution simple basée sur le mélange d'adversaires pour restaurer la capacité de généralisation des agents.

L'essentiel

🎨 Le Jeu : "La Guerre de Peinture"

Imaginez un jeu sur un plateau de 10x10 cases. Deux joueurs, disons Rose et Vert, sont des robots qui doivent peindre le plus de cases possible.

• À chaque tour, ils peuvent bouger ou "verrouiller" une case (la rendre immuable).
• Celui qui a le plus de cases à la fin gagne.
• C'est un jeu à somme nulle : si Rose gagne, Vert perd.

L'objectif des chercheurs était d'entraîner ces robots à devenir des champions en les faisant s'affronter l'un contre l'autre (ce qu'on appelle l'auto-jeu ou self-play).

📉 Le Problème : Des Robots qui échouent lamentablement

Au début, les chercheurs ont programmé un robot (Rose) avec une méthode intelligente appelée PPO. Ils pensaient qu'il deviendrait un génie.
Résultat catastrophique : Après des milliers d'heures d'entraînement, le robot Rose perdait contre un adversaire qui jouait au hasard (qui ne fait que cliquer n'importe où). Il gagnait seulement 26 % des parties. C'est comme si un grand maître d'échecs battait un enfant de 5 ans... mais seulement si l'enfant joue au hasard, alors que le robot perdait contre un enfant qui joue au hasard !

🔍 L'Autopsie : Pourquoi ça a raté ? (Les 5 Bugs)

Les chercheurs ont fouillé dans le code et trouvé 5 bugs (des erreurs de programmation) qui gâchaient tout. Imaginez que vous essayiez d'apprendre à quelqu'un à cuisiner, mais que vous lui donnez des instructions fausses :

1. Le bug de la "Récompense Géante" : Le robot pensait que le plus important était de poser des "verrous". À cause d'une erreur de calcul, chaque verrou lui donnait une récompense énorme, écrasant tout le reste. Il jouait comme un maniaque qui pose des verrous partout sans jamais peindre de cases.
   • Analogie : C'est comme si un élève recevait 1000 points pour chaque crayon qu'il pose sur sa table, mais 1 point seulement pour chaque bonne réponse en maths. Il passerait son temps à poser des crayons.
2. L'oubli du "Gagne ou Perds" : Le robot ne savait pas vraiment quand il avait gagné ou perdu à la fin. Il jouait sans but.
3. Le problème de la "Mémoire Courte" : Dans ce jeu, les décisions prises au début (les 50 premiers tours) sont cruciales. Mais la méthode utilisée par le robot "oubliait" ces décisions trop vite. Il ne comprenait pas que son action du début avait causé sa défaite 200 tours plus tard.
4. Le "Désordre dans les Chiffres" : Le robot recevait des informations mélangées : sa position (un chiffre entre 0 et 9) et le nombre de tours restants (un chiffre entre 0 et 250). Pour son cerveau artificiel, c'était comme si on lui parlait en chuchotant et en hurlant en même temps. Il ne comprenait rien.
5. Le "Compteur de Victoire" Faux : Le robot se croyait gagnant parce qu'il avait accumulé beaucoup de points intermédiaires, alors qu'il avait perdu la partie.

Après avoir corrigé ces 5 bugs, le robot Rose est devenu excellent : il battait le robot aléatoire dans 73 % des cas.

🤯 Le Piège Invisible : "L'Overfitting Compétitif"

C'est ici que ça devient fascinant. Les chercheurs ont continué l'entraînement. Rose et Vert s'affrontaient encore et encore.

• Ce qui semblait se passer : Ils jouaient parfaitement l'un contre l'autre. Le score restait à 50/50. Tout semblait stable.
• La réalité cachée : Les deux robots avaient développé une stratégie ultra-spécialisée pour contrer exactement les mouvements de l'autre. Ils avaient appris à se battre contre un "clone" de leur adversaire, pas contre un vrai joueur.

C'est ce qu'on appelle l'overfitting compétitif (ou "surapprentissage compétitif").

• Analogie : Imaginez deux boxeurs qui s'entraînent ensemble pendant des années. Ils connaissent chacun le moindre mouvement de l'autre. Ils s'affrontent en boucle, et tout va bien. Mais si on les met face à un inconnu (un adversaire aléatoire), ils sont perdus car ils ne savent pas réagir à l'imprévu. Ils sont devenus des champions de "la danse avec leur partenaire", mais pas des boxeurs.

Le pire ? Le score interne ne donnait aucun signe d'alarme. Ils continuaient à faire 50/50 entre eux, alors que leur capacité à gagner contre un inconnu s'effondrait (de 73 % à seulement 21 % !).

💡 La Solution Magique : "Le Mélange d'Adversaires"

Comment régler ça ? Les chercheurs ont ajouté une astuce simple, une seule ligne de code : le mélange d'adversaires.

• La règle : 20 % du temps, le robot Vert ne joue pas contre Rose. Il joue contre un robot qui joue au hasard (qui bouge n'importe où).
• L'effet : Cela force Rose à ne pas se spécialiser uniquement contre Vert. Elle doit apprendre des stratégies qui fonctionnent contre n'importe qui, y compris les joueurs bêtes.

Résultat final :
Avec cette petite astuce, le robot Rose redevient un champion. Il gagne 77 % des parties contre un adversaire aléatoire (et jusqu'à 93 % pour les meilleurs d'entre eux).

🏆 Ce qu'on retient de cette histoire

1. Les détails comptent : Parfois, un petit bug de calcul (comme la taille des récompenses) peut rendre un robot plus bête qu'un humain qui joue au hasard.
2. Se battre contre soi-même ne suffit pas : Si deux robots s'entraînent uniquement l'un contre l'autre, ils risquent de devenir des experts d'une danse très spécifique, mais incapables de s'adapter au monde réel.
3. La diversité est la clé : Pour bien apprendre, il faut s'entraîner contre des adversaires variés (des experts, des débutants, des joueurs au hasard). C'est comme un athlète qui s'entraîne avec des partenaires différents pour être prêt à tout.
4. Attention aux faux signes : Parfois, tout semble aller bien (score stable), mais en réalité, le système est en train de s'effondrer. Il faut toujours tester ses robots contre des "inconnus" pour vérifier qu'ils sont vraiment intelligents.

En résumé, ce papier nous dit : "Ne laissez pas vos robots s'ennuyer en jouant uniquement entre eux. Donnez-leur des adversaires imprévisibles, sinon ils deviendront des champions de rien du tout."

Résumé technique

1. Problématique

L'apprentissage par renforcement multi-agents (MARL) compétitif vise souvent à utiliser l'auto-jeu (self-play) pour générer des agents surpassant les humains (ex: AlphaGo, AlphaStar). Cependant, les praticiens constatent fréquemment que les algorithmes standards, comme PPO (Proximal Policy Optimization), échouent à apprendre des tâches compétitives simples lorsqu'ils sont transplantés dans des environnements multi-agents.

Les causes de ces échecs sont souvent diffuses et difficiles à isoler (mauvaise spécification des récompenses, problèmes d'attribution du crédit, instabilité de l'entraînement). L'article se propose de rendre ces causes concrètes en identifiant et en corrigeant systématiquement des modes de défaillance spécifiques dans un environnement minimaliste.

2. Méthodologie et Environnement

Environnement : Territory Paint Wars

L'auteur a développé un environnement de jeu minimaliste et déterministe, Territory Paint Wars, implémenté dans Unity avec une interface TCP personnalisée vers Python (sans dépendance aux ML-Agents).

• Mécanique : Deux agents (Rose et Vert) évoluent sur une grille $10 \times 10$. À chaque étape, ils peuvent se déplacer (N, S, E, O) ou verrouiller la case actuelle (rendue inaccessible à l'adversaire).
• Objectif : Contrôler le plus grand nombre de cases après 250 étapes.
• Récompense : Une combinaison de gains de territoire (+0.1 par case), de bonus de verrouillage (+0.5 par nouveau verrouillage) et d'une récompense terminale (+1/-1 pour la victoire/défaite).

Approche Expérimentale

L'étude suit une démarche itérative :

1. Baseline (v1) : Entraînement d'un agent PPO avec des bugs d'implémentation courants.
2. Correction (v2) : Identification et correction de cinq modes de défaillance techniques.
3. Diagnostic (v2) : Découverte d'un nouveau mode de défaillance émergent : le surapprentissage compétitif (competitive overfitting).
4. Solution (v3) : Introduction d'une stratégie de mélange d'adversaires (opponent mixing) pour stabiliser la généralisation.
5. Validation : Ablations systématiques pour isoler la contribution de chaque correction sur 10 graines aléatoires.

3. Contributions Clés et Résultats

A. Identification de cinq modes de défaillance d'implémentation (v1)

L'agent de base (v1), entraîné sur 84 000 épisodes, n'atteint qu'un taux de victoire de 26,8 % contre un adversaire aléatoire (pire que le hasard). L'analyse a révélé cinq bugs critiques :

1. Explosion de l'échelle des récompenses : Une récompense cumulative incorrecte pour les verrouillages a créé des valeurs de retour d'épisode allant de -10 000 à +10 000, noyant les signaux de gain de territoire.
2. Absence de signal terminal : Sans récompense finale (+1/-1), l'agent ne comprenait pas l'issue du jeu.
3. Attribution du crédit inefficace : L'utilisation de retours Monte Carlo (MC) sur 250 étapes avec $\gamma=0.99$ réduisait le gradient des premières étapes (décisions territoriales) d'un facteur $\approx 0.08$. L'utilisation de GAE (Generalized Advantage Estimation) avec $\lambda=0.95$ était nécessaire.
4. Observations non normalisées : Le mélange de positions brutes (0-9) et du nombre d'étapes restantes (0-250) dans la même couche d'entrée perturbait l'apprentissage.
5. Détection erronée du vainqueur : Le gagnant était déterminé par la somme des récompenses (corrompue par le bug d'échelle) plutôt que par le comptage réel des cases.

B. Découverte du « Surapprentissage Compétitif » (Competitive Overfitting)

Après correction des bugs (v2), l'agent atteignait 73,5 % de victoires contre un adversaire aléatoire, mais ce taux s'effondrait à 21,6 % après 12 000 épisodes supplémentaires.

• Mécanisme : Les deux agents co-adaptent leurs stratégies l'un contre l'autre, créant un équilibre de Nash étroitement spécialisé. Ils deviennent excellents l'un contre l'autre mais incapables de généraliser à des politiques inconnues (comme un agent aléatoire).
• Piège de surveillance : Le taux de victoire en auto-jeu reste stable autour de 50 %, masquant totalement l'effondrement de la généralisation.

C. Solution : Mélange d'Adversaires (Opponent Mixing)

Pour contrer le surapprentissage, l'auteur propose une intervention minimale : remplacer l'adversaire co-adaptif par une politique uniforme aléatoire dans 20 % des épisodes ($\epsilon = 0.2$).

• Résultat : Cette simple modification (une ligne de code) restaure le taux de victoire contre un adversaire aléatoire à 77,1 % (moyenne sur 10 graines, écart-type ±12,6 %), avec un pic à 93,9 % pour la meilleure graine.
• Avantage : Aucune infrastructure supplémentaire (pas de population d'agents, pas de stockage de checkpoints) n'est requise.

D. Étude d'Ablation et Importance Relative

L'étude d'ablation révèle une asymétrie fascinante dans l'importance des corrections :

• Critiques (Catastrophiques) : Le retrait de GAE, de la normalisation des observations ou du mélange d'adversaires fait chuter le taux de victoire en dessous de la baseline brisée (v1), respectivement à 9,6 %, 12,6 % et 21,6 %. Ces éléments sont indispensables.
• Complémentaire (Non essentiel) : Le retrait de la récompense terminale ne fait chuter le taux de victoire que de 77,1 % à 87,1 %. Cela démontre que les récompenses denses par étape (gain de case + bonus de verrouillage) suffisent à apprendre une politique robuste si les trois autres corrections sont en place.

4. Signification et Impact

1. Benchmark Reproductible : L'article ouvre source Territory Paint Wars comme un benchmark minimaliste pour étudier les modes de défaillance du MARL compétitif, accessible via une interface TCP simple.
2. Diagnostic de l'Auto-Jeu : L'article met en évidence que le taux de victoire en auto-jeu est un indicateur trompeur dans les environnements compétitifs. Une évaluation périodique contre une baseline externe fixe est indispensable pour détecter le surapprentissage compétitif.
3. Efficacité des Solutions Simples : Il démontre que des problèmes complexes de généralisation peuvent être résolus par des interventions légères (comme le mélange d'adversaires) plutôt que par des architectures complexes de population.
4. Nuance sur les Récompenses : Il souligne que l'échelle des récompenses (et non seulement leur signe) est critique, et que les récompenses terminales ne sont pas toujours nécessaires si les signaux intermédiaires sont bien calibrés.

En conclusion, cette étude fournit une taxonomie claire des échecs du PPO en contexte compétitif et prouve que la diversité des adversaires est essentielle pour garantir une généralisation robuste, même dans des environnements simples.