Technische Samenvatting: Vormgeven van Zero-Shot Coördinatie via State Blocking

Probleemstelling

Zero-Shot Coördinatie (ZSC) heeft tot doel multi-agent systemen in staat te stellen samen te werken met onafhankelijk getrainde partners (inclusief mensen) zonder voorafgaande gezamenlijke interactie. Hoewel bestaande methoden zoals Self-Play (SP) effectief zijn voor agenten die samen zijn getraind, convergeren ze vaak naar een enkele coördinatieconventie, wat leidt tot ernstige prestatiedegradatie wanneer ze worden gekoppeld aan partners die zijn getraind onder verschillende random seeds of methoden (Cross-Play, XP).

Eerdere benaderingen proberen dit te mitigeren door partnerdiversiteit te vergroten via populaties, gerandomiseerde beleidsregels of aanpassingen van de omgeving. Deze strategieën falen echter vaak in het vastleggen van een diverse reeks gestructureerde suboptimale coördinatiemodi. Ze genereren ofwel gedragingen die te veel lijken op de optimale conventie, ofwel introduceren ze ongestructureerde variabiliteit die niet goed generaliseert. Bovendien vereisen omgeving-diversiteitsbenaderingen vaak expliciete toegang tot of modificatie van de omgeving, wat hun toepasbaarheid beperkt. De kernuitdaging blijft: hoe een ego-agent systematisch bloot te stellen aan een diverse reeks gestructureerde, suboptimale partnergedragingen zonder de onderliggende omgeving te modificeren of externe menselijke data te vereisen.

Methodologie: State-Blocked Coördinatie (SBC)

De auteurs stellen State-Blocked Coördinatie (SBC) voor, een kader dat gestructureerde diversiteit in partnergedragingen induceert door virtuele omgevingsvariaties te creëren via state blocking.

1. State-Blocked MDP (SB-MDP)

SBC definieert een gemodificeerd Markov Decision Process waarbij specifieke staten worden aangewezen als "penalty states".

• Mechanisme: Een set penalty states $\tilde{S}$ wordt geselecteerd uit de replay buffer. De beloningsfunctie wordt gewijzigd om transities naar deze staten te bestraffen:
  $$\tilde{R}(s_t, a_t, s_{t+1}; \tilde{S}) = R(s_t, a_t, s_{t+1}) - \alpha \sum_{\tilde{s} \in \tilde{S}} \frac{1}{\|s_{t+1} - \tilde{s}\|^2 + \epsilon}$$
  waarbij $\alpha$ de penalty-coëfficiënt is.
• Effect: Door partners te dwingen specifieke staten te vermijden terwijl ze de taak nog steeds voltooien, induceert de SB-MDP onderscheidende, lokaal optimale coördinatiestrategieën. Deze strategieën vertegenwoordigen gestructureerde suboptimale gedragingen die afwijken van het globale optimum maar wel taak-geldig blijven.

2. Trainingsprocedure

SBC hanteert een tweestaps trainingsproces met een blocking-aware policy en een normale ego policy:

• Blocking-Aware Policy ($\tilde{\pi}$): Deze policy wordt getraind in de SB-MDP. Deze conditieert op de specifieke set geblokkeerde staten $\tilde{S}$ als input. Door tijdens het trainen diverse sets van penalty states te samplen, genereert het systeem een familie van blocking-aware partners, die elk een andere coördinatieconventie volgen die wordt opgelegd door hun specifieke geblokkeerde staten.
• Normale Ego Policy ($\pi_e$): Het uiteindelijke beleid dat tijdens de testfase wordt gebruikt, wordt getraind in de originele MDP (zonder input van penalty states). Het wordt blootgesteld aan een mengsel van:
  1. Standaard Self-Play partners (kopieën van zichzelf).
  2. Blocking-aware partners (getraind in SB-MDPs maar handelend in de originele MDP tijdens de training van de ego).
     Deze blootstelling stelt de ego-agent in staat om coördinatie te leren met een breed spectrum aan gestructureerde gedragingen zonder over te fitten op een enkele conventie.

3. Waarde-gestuurde Planning van Penalty States

Om te voorkomen dat staten worden geselecteerd die kritiek zijn voor het voltooien van de taak (wat de partnerprestaties te sterk zou degraderen), introduceert SBC een planningsmechanisme:

• Kritikaliteitsmetriek: De waardenkloof $\Delta V(\tilde{s}) = V^{\pi}(s_0) - \tilde{V}^{\tilde{\pi}}(s_0, \tilde{s})$ kwantificeert hoe sterk het blokkeren van een staat de return degradeert.
• Samplingstrategie: Penalty states worden gesampled met waarschijnlijkheid $P(\tilde{s}) \propto \exp(-\beta \Delta V(\tilde{s}))$.
• Annealing: De temperatuur $\beta$ wordt geannealed van 0 naar 1. Vroeg in de training is sampling bijna uniform om diversiteit te maximaliseren. Later weegt de scheduler sterk kritieke staten progressief minder zwaar, met focus op blokkeringsconfiguraties die betekenisvolle maar niet-catastrofale suboptimale gedragingen induceren.

4. Aanvullende Componenten

Om de robuustheid verder te versterken, omvat SBC:

• Partner-Actie Predictie: Een auxiliair model voorspelt partneracties, die aan de ego policy worden toegevoerd om adaptatie te ondersteunen.
• Random Actie Injectie: Partners voeren af en toe willekeurige acties uit om robuustheid tegen afwijkingen te verbeteren.

Belangrijkste Bijdragen

1. Kader: Introductie van SBC, een methode die gestructureerde partnerdiversiteit genereert via state blocking zonder de overgangsdynamiek van de omgeving te modificeren of externe data te vereisen.
2. Mechanisme: De formulering van de State-Blocked MDP en de waarde-gestuurde planningsstrategie om diversiteit in evenwicht te brengen met taakhaalbaarheid.
3. Prestaties: Aantonen dat SBC superieure Zero-Shot Coördinatie-prestaties bereikt over meerdere benchmarks, waarbij de kloof tussen Self-Play en Cross-Play scores aanzienlijk wordt verkleind.
4. Mens-AI Coördinatie: Validatie dat SBC effectief coördineert met zowel menselijke proxies als echte menselijke deelnemers, en bestaande baselines overtreft op het gebied van taakreturn, reductie van botsingen en waargenomen coördinatievlotheid.

Experimentele Resultaten

De auteurs evalueerden SBC op Multi-Destination Spread en Overcooked v1 (vijf lay-outs), in vergelijking met baselines waaronder IPPO, FCP, MEP, E3T, GAMMA en CEC.

• Multi-Destination Spread: SBC behaalde een XP-score van 957,2 (tegenover 77,4 voor IPPO) met een Gap van 24,8 (tegenover 912,6 voor IPPO). Het was de enige methode die hoge prestaties handhaafde in zowel SP als XP.
• Overcooked v1: SBC presteerde consistent beter dan baselines in Cross-Play over alle lay-outs. Bijvoorbeeld, in de Coordination Ring lay-out behaalde SBC een XP van 316 (Gap 17), terwijl IPPO 41 scoorde (Gap 246). SBC handhaafde of verbeterde ook de Self-Play-prestaties ten opzichte van andere methoden.
• Held-Out XP: SBC demonstreerde robuuste generalisatie naar partners die waren getraind met verschillende ZSC-methoden, niet alleen verschillende seeds.
• Mens-AI Evaluatie: In experimenten met 40 echte menselijke deelnemers behaalde SBC de hoogste scores op alle vijf lay-outs. Het resulteerde in het laagste aantal botsingen per levering en de hoogste deelnemersbeoordelingen voor coördinatievlotheid op een 7-punts Likert-schaal.

Betekenis en Claims

Het artikel claimt dat SBC de fundamentele beperking van bestaande ZSC-methoden aanpakt: het onvermogen om diverse doch gestructureerde suboptimale partnergedragingen te construeren. Door "blocking-aware" partners te induceren, stelt SBC de ego-agent bloot aan een breed scala aan coördinatieconventies, wat robuuste generalisatie naar onbekende partners mogelijk maakt.

De auteurs benadrukken dat:

• SBC geen expliciete omgevingsmodificatie vereist (in tegenstelling tot CEC) en geen grootschalige verzameling van menselijke data nodig heeft.
• De methode de coördinatie met menselijke partners verbetert, wat suggereert dat blootstelling aan diverse, lokaal optimale strategieën agenten helpt zich aan te passen aan menselijke eigenaardigheden.
• Hoewel SBC hyperparameters introduceert ($\alpha$ en $K$), maakt de waarde-gestuurde planning de methode robuust tegen matige variaties, en is de computere overhead bescheiden in vergelijking met de prestatiewinst en in vergelijking met zwaardere baselines zoals GAMMA of CEC.

Het werk positioneert SBC als een praktische stap naar het inzetten van coöperatieve AI-agenten die naadloos kunnen integreren met onafhankelijk getrainde systemen en menselijke samenwerkers in real-world scenario's.