Multi-Agent Guided Policy Search for Non-Cooperative Dynamic Games

Titel: Multi-Agent Guided Policy Search voor Niet-Coöperatieve Dynamische Spellen

1. Het Probleem

Niet-coöperatieve dynamische spelen vormen een fundamenteel raamwerk voor het modelleren van strategische interacties tussen zelfbelanghebbende agenten met tegenstrijdige doelen (bijv. autonoom rijden, robotcoördinatie). Een centrale oplossing is het Nash-evenwicht, waarbij geen enkele agent zijn kosten kan verlagen door eenzijdig van strategie te veranderen.

Hoewel Multi-Agent Reinforcement Learning (MARL) veelbelovend is voor het vinden van deze evenwichten in hoogdimensionale ruimtes, lijden data-gedreven methoden zoals Multi-Agent Policy Gradients (MA-PG) vaak aan:

• Instabiliteit: De dynamiek van het leren convergeert niet naar een stabiel punt.
• Limietcycli: Agenten oscilleren rond een oplossing zonder te convergeren.
• Beperkingen van bestaande stabilisatie: Huidige technieken vertrouwen vaak op entropie-gedreven exploratie, wat het leerproces vertraagt en de variantie verhoogt.
• Schalingsproblemen: Klassieke model-gebaseerde methoden (zoals iteratieve lineair-kwadratische benaderingen) zijn stabiel maar rekenkundig te duur voor complexe, niet-lineaire dynamieken met veel agenten.

2. Methodologie: MA-GPS

De auteurs stellen een hybride aanpak voor die de schaalbaarheid van MARL combineert met de stabiliteit van model-gebaseerde optimalisatie. De kernmethode heet Multi-agent Guided Policy Search (MA-GPS).

Kernidee:
In plaats van puur op data te vertrouwen, wordt een model-gebaseerde prior (een benadering van een Nash-evenwicht) gebruikt als regularisatie in de beloningsfunctie. Dit prior fungeert als een gedeeld referentiepunt dat de updates van de agenten stabiliseert en hen leidt naar een consistent evenwicht.

Technische Implementatie:

1. Theoretische Basis (LQ Spelen):

   • Voor lineair-kwadratische (LQ) spelen wordt bewezen dat het toevoegen van een regularisatieterm aan de kostenfunctie, gebaseerd op een afwijking van een "leidende" stabiliserende feedback-beleid $\check{K}$, de instabiliteit van MA-PG oplost.
   • De nieuwe kostenfunctie voor agent $i$ wordt:
     $$\hat{J}_i^\rho = J_i + \rho \cdot \mathbb{E} \left[ \sum (u_i - \check{u}_i)^\top R_i (u_i - \check{u}_i) \right]$$
   • Hierbij is $\rho$ een gewicht. Een voldoende groot $\rho$ verschuift de eigenwaarden van de Jacobiaan van de pseudo-gradiënt naar het positieve domein, wat lokale exponentiële convergentie garandeert naar een stationair punt.

2. Uitbreiding naar Niet-Lineaire Spelen:

   • Voor complexe, niet-lineaire dynamieken is het moeilijk om een exacte leidende strategie te berekenen.
   • MA-GPS gebruikt lokale LQ-benaderingen langs de trajecten van de huidige neurale netwerken.
   • Procedure:
     • Simuleer een nominale traject met het huidige beleid $\pi_\theta$.
     • Lineariseer de dynamiek en kwadratiseer de kosten rond dit traject om een lokaal LQ-spel te creëren.
     • Los dit lokale LQ-spel op (bijv. via iLQGames-achtige methoden) om een Nash-evenwicht voor dat lokale probleem te vinden.
     • Gebruik de eerste stap van dit lokale evenwicht als leidende actie ($\check{u}$) voor de huidige toestand.
   • Dit leidende beleid wordt gebruikt om de beloningsfunctie te regulariseren tijdens het trainen van het neurale netwerk.

3. Algoritme (MA-GPS):

   • Het algoritme wisselt af tussen het verzamelen van roll-out data en het updaten van het beleid.
   • Bij elke update wordt de gradiënt berekend op basis van de geleide kostenfunctie (originele kosten + regularisatie naar het leidende beleid).
   • Het gewicht $\rho$ kan tijdens het trainen worden afgebouwd (decay) om de bias van de leidende prior te verminderen terwijl de stabiliteit behouden blijft.

3. Belangrijkste Bijdragen

1. Theoretische Stabilisatie voor LQ Spelen: Wiskundig bewijs dat elke stabiliserende feedback-beleid (niet noodzakelijk een Nash-evenwicht) kan dienen als effectieve geleiding. Dit garandeert lokale exponentiële convergentie van geleide policy gradients, zelfs als de oorspronkelijke MA-PG dynamiek instabiel is.
2. Framework voor Niet-Lineaire Spelen: Een efficiënt algoritme (MA-GPS) dat lokale LQ-benaderingen gebruikt om real-time geleiding te genereren voor neurale netwerken, zonder de noodzaak van vooraf berekende beleidslijnen. Dit elimineert de beperkingen van klassieke Guided Policy Search in niet-coöperatieve settings.
3. Empirische Validatie: Demonstratie van superieure prestaties in vergelijking met state-of-the-art MARL-methoden (zoals IPPO, MA-PPO, MA-DDPG) op zowel lineaire als complexe niet-lineaire taken.

4. Resultaten

De methode werd getest op drie scenario's:

• Twee-agent LQ-spel: Toonde aan dat MA-PG zonder geleiding in limietcycli terechtkomt. Met geleiding (zelfs met een onnauwkeurige prior) convergeerde het systeem stabiel naar een buurt van het ware Nash-evenwicht.
• Niet-lineaire voertuigplatooning (3 voertuigen): MA-GPS bereikte snellere convergentie en lagere variantie dan baselines. Het leerde hoogwaardige beleidslijnen sneller dan methoden die alleen op entropie-regularisatie leunden.
• Strategische basketbalformatie (6 spelers): Een complex scenario met 24 dimensies. MA-GPS overtrof IPPO aanzienlijk in convergentiesnelheid en stabiliteit. Het bleek ook robuust te zijn voor niet-differentieerbare objectieven (bijv. "max" functies in de kosten).

Vergelijking met iLQGames:
Hoewel iLQGames nauwkeurig is, is het rekenkundig zwaar voor lange horizonnen en real-time toepassing. MA-GPS verplaatst de zware berekening naar de offline training en levert neurale netwerken op die real-time uitvoerbaar zijn met minimale latentie.

5. Betekenis en Impact

Dit paper biedt een cruciale oplossing voor een van de grootste uitdagingen in Multi-Agent Reinforcement Learning: de instabiliteit bij het leren van Nash-evenwichten in niet-coöperatieve omgevingen.

• Stabiliteit zonder vertraging: In tegenstelling tot entropie-regularisatie, die het leren vertraagt, versnelt model-gebaseerde geleiding het leerproces door een duidelijke richting te geven.
• Praktische toepasbaarheid: De methene maakt het mogelijk om complexe strategieën te leren in real-time omgevingen (zoals autonoom rijden of robotica) waar klassieke model-gebaseerde optimalisatie te traag is en puur data-gedreven methoden te instabiel.
• Hybride toekomst: Het paper markeert een verschuiving naar hybride methoden die de sterktes van model-gebaseerde planning en datagedreven versterking leren combineren voor robuuste multi-agent systemen.