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

Dit paper introduceert 'Territory Paint Wars', een Unity-omgeving om kritieke implementatiefouten en het emergente probleem van competitieve overfitting in multi-agent PPO te diagnosticeren, en stelt een eenvoudige oplossing voor door opponent-mixing om de generalisatie te herstellen zonder complexe infrastructuur.

De kern

Territory Paint Wars: Een Strijd om Vergeten en Herinneren

Stel je voor dat je twee kinderen, Roze en Groen, in een kamer zet met een groot, leeg vloerkleed van 10 bij 10 tegels. Hun opdracht is simpel: wie aan het einde van het spel de meeste tegels van hun eigen kleur heeft, wint. Ze mogen elke tegel die ze betreden "verf" geven, en ze kunnen een tegel zelfs "vergrendelen" zodat de ander hem nooit meer kan veroveren.

Dit is Territory Paint Wars, een digitaal bordspel dat de onderzoeker van dit paper heeft bedacht om te kijken hoe kunstmatige intelligentie (AI) leert strijden. Maar er gebeurde iets vreemds: de AI's werden niet beter, ze werden juist slechter.

Hier is wat er aan de hand was, verteld als een verhaal met een paar handige vergelijkingen.

1. De Grote Mislukking (De "Vervormde" AI)

In het begin probeerden de AI's te leren door tegen elkaar te spelen (een methode die "self-play" heet, alsof je tegen jezelf schaken). Maar na 84.000 pogingen won de AI slechts 26% van de tijd tegen een volledig willekeurige tegenstander. Dat is alsof je een schaker hebt die slechter speelt dan iemand die de stukken willekeurig over het bord gooit.

Waarom? Omdat de programmeur (de onderzoeker) per ongeluk vijf kleine foutjes had gemaakt in de regels van het spel:

1. De "Goudkoorts" Fout: De AI kreeg te veel punten voor het vergrendelen van tegels. Het was alsof het spel zei: "Vergrendel één tegel en je krijgt een miljoen punten!" Hierdoor negeerde de AI alles wat belangrijk was (zoals het veroveren van ruimte) en probeerde hij alleen maar te vergrendelen.
2. Het Vergeten van het Begin: Het spel duurde lang (250 stappen). De AI keek alleen naar het einde en vergeten wat hij in het begin had gedaan. Het was alsof je een boek leest en pas aan het einde begrijpt wat er in hoofdstuk 1 gebeurde.
3. De Verwarde Zintuigen: De AI kreeg informatie in een chaotische vorm. Soms zag hij "stap 5" en soms "positie 9" door elkaar. Het was alsof je een auto bestuurt waarbij het gaspedaal soms de snelheidsmeter is en soms de radio.
4. De Verkeerde Winnaar: Het spel telde de winnaar verkeerd uit omdat het de punten van de "Goudkoorts"-fout gebruikte in plaats van echt te tellen wie de meeste tegels had.
5. Geen Prijs voor Winnen: De AI kreeg geen duidelijke beloning als hij daadwerkelijk won. Hij wist niet dat het doel was om te winnen, maar alleen dat hij tegels moest pakken.

Zodra deze fouten werden opgelost, werd de AI plotseling heel goed: hij won 73% van de wedstrijden tegen een willekeurige tegenstander.

2. De Verrassende Valstrik: "Competitive Overfitting"

Maar hier wordt het verhaal interessant. De onderzoeker liet de AI's nog langer tegen elkaar spelen. Je zou denken dat ze steeds beter werden, maar nee. Na verloop van tijd stortte hun prestatie in. Ze wonnen plotseling maar 21% van de tijd tegen een willekeurige tegenstander.

Dit noemt de paper Competitive Overfitting (of: te specifiek worden).

De Vergelijking:
Stel je voor dat Roze en Groen tegen elkaar trainen in een sportzaal.

• Roze leert precies hoe Groen beweegt.
• Groen leert precies hoe Roze beweegt.
• Ze worden zo goed in het verslaan van elkaar dat ze een eigen, heel specifiek dansje hebben ontwikkeld.

Het probleem? Als je ze nu tegen een willekeurige vreemdeling zet (die dat specifieke dansje niet kent), weten ze niet meer wat ze moeten doen. Ze zijn te gespecialiseerd op hun tegenstander.

Het Gevaar:
Het ergste deel is dat dit onzichtbaar is. Als je alleen kijkt naar hoe Roze het doet tegen Groen, lijkt alles perfect: ze winnen en verliezen afwisselend (50/50). Het lijkt alsof ze nog steeds trainen, maar in werkelijkheid zijn ze vergeten hoe ze tegen iedereen moeten spelen. Het is alsof twee mensen die alleen maar met elkaar praten in een taal die niemand anders begrijpt; ze denken dat ze communiceren, maar ze zijn geïsoleerd.

3. De Simpele Oplossing: "De Willekeurige Tegenstander"

Hoe los je dit op? De onderzoeker deed iets heel simpels, een soort "remedie" die hij Opponent Mixing noemde.

Hij liet de AI's in 20% van de wedstrijden niet tegen elkaar spelen, maar tegen een willekeurige, domme tegenstander (een AI die alleen maar willekeurige moves maakt).

De Vergelijking:
Stel je voor dat je een pianist bent die alleen maar met een andere pianist oefent. Je wordt heel goed in het spelen van die ene melodie samen. Maar als je een concert geeft voor een publiek, faal je.
De oplossing? Laat de pianist af en toe spelen met iemand die de noten niet kent, of met een drumstel dat willekeurig slaat. Dit dwingt de pianist om zijn techniek aan te passen aan elke situatie, niet alleen aan zijn partner.

Door deze kleine toevoeging (slechts één regel code) gebeurde het wonder:

• De AI's werden weer robuust.
• Hun winpercentage tegen willekeurige tegenstanders steeg van 21% terug naar 77%.
• Ze waren niet meer "gevangen" in hun eigen wereldje.

Wat leren we hieruit?

De belangrijkste les van dit paper is dat alleen tegen elkaar spelen niet genoeg is om slimme AI's te maken. Als je ze alleen tegen elkaar laat trainen, kunnen ze in een valstrik stappen waarin ze alleen maar goed worden in het verslaan van elkaar, maar slecht in het verslaan van de echte wereld.

Om echt slim te worden, moet je je AI's af en toe blootstellen aan "domme" of willekeurige tegenstanders. Dit zorgt ervoor dat ze generaliseren kunnen: ze leren principes die werken voor iedereen, niet alleen voor hun specifieke partner.

Kortom:

1. Foutjes in de code kunnen AI's dom houden.
2. Te veel trainen tegen elkaar kan AI's "vergeten" hoe ze tegen anderen moeten spelen (Competitive Overfitting).
3. De oplossing is simpel: laat ze af en toe tegen een "domme" tegenstander spelen, zodat ze niet te specifiek worden.

De onderzoeker heeft het spel Territory Paint Wars gratis beschikbaar gesteld, zodat iedereen dit kan testen en leren van deze fouten. Het is een waarschuwing voor iedereen die AI's laat leren: zorg dat je niet alleen in een bubbel zit!

Technische samenvatting

Probleemstelling

Competitief Multi-Agent Reinforcement Learning (MARL) is een actief onderzoeksgebied, maar in de praktijk falen standaard single-agent RL-algoritmen (zoals PPO) vaak wanneer ze worden overgeplaatst naar competitieve multi-agent omgevingen. De oorzaken van dit falen zijn vaak diffuus en omvatten fouten in beloningsspecificatie, problemen met krediettoewijzing (credit assignment) en trainingsinstabiliteit.

De auteur introduceert Territory Paint Wars, een minimalistische, deterministische nul-sum spelomgeving op een 10x10 rooster, om deze falenmoden systematisch te diagnosticeren. Het centrale probleem is dat een goed geoptimaliseerde PPO-agent in deze setting zelfs slechter presteert dan een willekeurige tegenstander (26,8% winstpercentage), en dat standaard monitoring (zelfspel-winstpercentages) een specifiek, gevaarlijk falenpatroon volledig kan maskeren.

Methodologie

1. Omgeving: Territory Paint Wars

• Spelmechanisme: Twee agents (Roze en Groen) bewegen zich gelijktijdig op een 10x10 rooster. Ze kunnen een richting kiezen of hun huidige tegel "vergrendelen" (locked). Vergrendelde tegels kunnen niet worden teruggewonnen. De agent met de meeste tegels na 250 stappen wint.
• Implementatie: Gebouwd in Unity 2022.3 LTS met een aangepaste Python-Unity TCP-brug, zonder afhankelijkheid van ML-Agents.
• Observatieruimte: Een 206-dimensionale vector (eigen positie, tegenstanderpositie, eigendom van alle 100 tegels, vergrendelingsmasker, resterende stappen).
• Beloningsfunctie: Bestaat uit een gebiedswinst (+0,1 per tegel), een vergrendelingsbonus (+0,5 per nieuwe vergrendeling) en een terminale winst/verlies (+1/-1).

2. Diagnose van Falenmoden (Ablatie-studie)
De auteur identificeert eerst vijf implementatiefouten in een basisversie (v1) die leiden tot een winstpercentage van 26,8% tegen een willekeurige tegenstander:

1. Explosie van de beloningsschaal: Een cumulatieve bonus voor vergrendelingen leidde tot episode-returns van ±10.000, waardoor andere signalen (zoals het winnen van het spel) verwaarloosbaar werden.
2. Ontbrekend terminaal signaal: De winst/verlies-uitkomst gaf geen directe beloning, waardoor de agent geen doel had.
3. Ineffectieve krediettoewijzing: Het gebruik van pure Monte Carlo-returns over 250 stappen met $\gamma=0.99$ resulteerde in een verwaarloosbare gradiënt voor de eerste stappen ($0.99^{249} \approx 0.08$).
4. Ongenormaliseerde observaties: Het mengen van ruwe posities (0-9) met resterende stappen (0-250) in dezelfde inputlaar veroorzaakte numerieke dominantie van bepaalde features.
5. Foutieve winstdetectie: De winnaar werd bepaald op basis van cumulatieve beloningen (vervormd door de schaalbug) in plaats van het tellen van tegels.

3. Identificatie van "Competitive Overfitting"
Na het fixen van de bovenstaande bugs (versie v2), bereikte de agent 73,5% winst tegen een willekeurige tegenstander. Bij verder trainen stortte dit echter in naar 21,6% (slechter dan de originele gebroken versie).

• Mechanisme: Beide agents passen zich gelijktijdig aan elkaar aan (co-adaptatie). Ze specialiseren zich hyper-specifiek in het verslaan van de huidige strategie van de tegenstander, in plaats van een robuuste strategie te ontwikkelen.
• Het probleem met monitoring: Het zelfspel-winstpercentage blijft tijdens deze ineenstorting stabiel rond de 50% omdat beide agents evenveel "leren" en elkaar neutraliseren. Dit maakt het falen onzichtbaar voor standaard monitoring.

4. Oplossing: Opponent Mixing
Om dit te voorkomen, introduceert de auteur Opponent Mixing: in 20% van de trainingsepisodes wordt de co-adaptieve tegenstander vervangen door een uniforme willekeurige policy. Dit dwingt de agent om strategieën te behouden die generaliseren naar verschillende tegenstanders, zonder extra infrastructuur of population-based training.

Kernresultaten

• Herstel van Generalisatie: Na het toepassen van opponent mixing (versie v3) steeg het gemiddelde winstpercentage tegen een willekeurige tegenstander van 21,6% (versie v2 na ineenstorting) naar 77,1% (±12,6% over 10 seeds). De beste seed bereikte 93,9%.
• Kritieke Ablaties:
  • GAE (Generalized Advantage Estimation): Essentieel. Zonder GAE (gebruik van pure MC) daalt de winst naar 9,6%. De agent leert geen zinvolle strategieën voor vroege spelstappen.
  • Observatie-normalisatie: Essentieel. Zonder normalisatie daalt de winst naar 12,6%. De agent overfitte hier zelfs sneller op de co-adaptieve tegenstander.
  • Opponent Mixing: Essentieel. Zonder dit (terug naar v2) daalt de winst naar 21,6% door competitieve overfitting.
  • Terminale Beloning: Niet individueel noodzakelijk. Zelfs zonder de ±1.0 winst/verlies-beloning behaalde de agent 87,1% winst. De dichte stap-beloningen (terreinwinst + vergrendeling) zijn voldoende als de andere drie fixes aanwezig zijn.
• Statistische Significantie: De verbetering door opponent mixing is statistisch significant ($p < 10^{-7}$) ten opzichte van de ineenstortingsversie.

Bijdragen en Betekenis

1. Reproduceerbaar Benchmark: De publicatie van Territory Paint Wars als open-source benchmark voor competitief MARL, met een eenvoudige Unity-Python interface.
2. Systematische Diagnose: Een gedetailleerde taxonomie van implementatiefouten die leiden tot falen in PPO, specifiek gericht op schaalproblemen en krediettoewijzing in lange horizon-spellen.
3. Ontdekking van "Competitive Overfitting": De paper identificeert en karakteriseert een subtiel falenpatroon waarbij zelfspel-winstpercentages volledig misleidend kunnen zijn. Het stelt dat periodieke evaluatie tegen een vaste externe baseline (zoals een willekeurige agent) een standaard diagnostische stap moet zijn in elk zelfspel-trainingsregime.
4. Minimalistische Oplossing: Het bewijs dat een simpele code-wijziging (20% opponent mixing) een complex generalisatieprobleem kan oplossen, zonder de noodzaak van zware population-based training of league-play systemen.
5. Praktische Inzicht: De studie benadrukt dat niet alle "fixes" gelijk zijn; sommige (zoals GAE en normalisatie) voorkomen catastrofale leerfouten, terwijl andere (zoals terminale beloning) slechts marginale verbeteringen bieden.

Conclusie:
De paper concludeert dat zelfspel alleen onvoldoende is voor robuuste generalisatie in competitieve settings. Het handhaven van tegenstanderdiversiteit (via opponent mixing) is cruciaal om te voorkomen dat agents in een lokaal evenwicht van onderlinge specialisatie terechtkomen dat geen enkele buitenstaander kan verslaan. De bevindingen zijn van breed belang voor elke onderzoeker die competitieve MARL-systemen ontwikkelt.