Technische Samenvatting: ARMS – Automatische Beloningsvorming voor Multi-Agent Reinforcement Learning met Sparse Rewards

1. Probleemstelling

Multi-Agent Reinforcement Learning (MARL) staat voor een kritieke bottleneck bij het omgaan met sparse rewards. In omgevingen met sparse rewards ontvangen agenten zelden feedback, wat het leerproces aanzienlijk vertraagt. Dit probleem wordt in MARL verergerd ten opzichte van Single-Agent RL (SARL) door n-stationariteit en co-adaptatie: terwijl agenten gelijktijdig hun beleidsregels updaten, lijkt de omgeving vanuit het perspectief van elke individuele agent niet-stationair.

Hoewel beloningsvorming (het aanvullen of vervangen van sparse signalen door dichte signalen) een gebruikelijke oplossing is, brengt dit in MARL extra risico's met zich mee. In SARL kan onjuiste vorming de set van optimale beleidsregels veranderen. In MARL is het risico ernstiger: vorming kan de set van Nash-evenwichten veranderen, wat de strategische structuur van het spel fundamenteel wijzigt en leidt tot suboptimale of onbedoelde collectieve gedragingen. Bestaande methoden voor automatische beloningsvorming, zoals Self-Supervised Online Reward Shaping (SORS), vertrouwen op garanties voor globale trajectrangschikking die niet direct naar MARL overdraagbaar zijn vanwege het ontbreken van een notie van globale optimaliteit en de onderlinge afhankelijkheid van agentbeleidsregels.

2. Methodologie: ARMS-raamwerk

De auteurs stellen ARMS (Automatic Reward-shaping in Multi-agent Systems) voor, een zelftoezichtend raamwerk dat is ontworpen om dichte vormingssignalen te leren uit sparse omgevingsbeloningen, terwijl de speltheoretische evenwichtsstructuur behouden blijft.

Theoretische Grondslag: Conditional Best-Response Invariantie

De kerntheoretische bijdrage is een herformulering van beleidsinvariantie voor multi-agent settings.

• Single-Agent Beperking: Standaard garanties voor trajectrangschikking (bijvoorbeeld van SORS) gaan ervan uit dat als twee beloningsfuncties dezelfde totale ordening over alle trajectparen induceren, ze dezelfde optimale beleidsregels opleveren. Dit rust op een notie van globale optimaliteit die ontbreekt in MARL.
• ARMS-Formulering: De auteurs bewijzen dat, als de beleidsregels van alle andere agenten vaststaan, een individuele agent geconfronteerd wordt met een geïnduceerde single-agent omgeving. Onder dit conditional best-response-perspectief, als een vormingsbeloningsfunctie totale-orde-equivalent is aan de oorspronkelijke beloning over de trajecten van deze geïnduceerde omgeving, behoudt deze de set van beste reacties van de agent.
• Behoud van Evenwicht: Bij uitbreiding, als deze voorwaarde geldt voor alle agenten, blijft de set van Nash-evenwichten invariant. Dit biedt een speltheoretische rechtvaardiging voor het gebruik van trajectrangschikking in MARL zonder de onderliggende strategische oplossing te veranderen.

Algoritmische Implementatie

ARMS werkt in een afwisselende lus tussen twee fasen (Algoritme 1):

1. Reinforcement Learning-fase: Agenten interageren met de omgeving met behulp van hun huidige gevormde beloningen ($R_{\theta}$) en een basis MARL-algoritme (bijvoorbeeld IPPO of MAPPO). Ze verzamelen gezamenlijke trajecten, die worden opgeslagen in een buffer.
2. Beloningsvormingsfase: Het systeem steekt paren trajectsegmenten uit de buffer. Voor elke agent wordt een geparametriseerde beloningsnetwerk ($F_\theta$) bijgewerkt om een binaire classificatieverlies te minimaliseren. Dit verlies dwingt af dat de voorkeursordening van de gevormde beloning over trajectparen overeenkomt met de voorkeursordening die wordt geïnduceerd door de oorspronkelijke sparse omgevingsbeloning.
   • Gedeelde Parameters: Om efficiëntie en schaalbaarheid te verbeteren, delen alle agenten dezelfde parameters voor beloningsvorming ($\theta$). Het netwerk wordt getraind op trajectordeningen per agent, waarbij signalen over alle agenten worden geaggregeerd.
   • Input: Het beloningsnetwerk neemt lokale waarnemingen en acties als input, wat een gedecentraliseerde informatiestroom modelleert.

3. Belangrijkste Bijdragen

Het artikel schetst drie primaire bijdragen:

1. Formulering van Multi-Agent Beleidsinvariantie: De auteurs stellen vast dat totale-orde-equivalente vormingsbeloningen de set van beste reacties van elke agent behouden onder vaste tegenstandersbeleidsregels, waardoor de set van Nash-evenwichten behouden blijft. Dit adresseert de theoretische kloof die de directe toepassing van single-agent trajectrangschikkingsmethoden op MARL verhindert.
2. Het ARMS-raamwerk: Een praktische, zelftoezichtende online methode voor beloningslering die gebruikmaakt van trajectrangschikking, rekening houdend met multi-agent n-stationariteit. Het leert een gedeeld vormingssignaal dat onafhankelijk is van de onderliggende RL-ruggengraat.
3. Empirische Analyse van MARL-dynamiek: De studie identificeert een specifieke MARL-foutmodus waarbij beperkte exploratie, gecombineerd met beleids-beloningsdynamiek, oscillerend gedrag induceert en convergentie naar suboptimale cyclische patronen. De auteurs tonen aan dat het verhogen van de exploratie dit effect mitigeert.

4. Experimentele Resultaten

Experimenten werden uitgevoerd in een gedeeltelijk waarneembare multi-agent padvindingsdomein (Lifelong Pathfinding) met behulp van de POGEMA-omgeving. De auteurs evalueerden ARMS tegen een baseline zonder vorming en Potential-Based Reward Shaping (PBRS) met IPPO- en MAPPO-ruggengraten.

• Sampling-efficiëntie: ARMS presteerde significant beter dan baselines op het gebied van cumulatieve oorspronkelijke beloning, vooral naarmate het aantal agenten toenam (8, 16, 32) en naarmate de beloningen sparser werden (vertragingen van 10, 20, 30 tijdstappen).
• Generalisatie: Beleidsregels getraind met ARMS generaliseerden effectief naar 50 onbekende kaarten (inclusief willekeurige en doolhofachtige omgevingen), waarbij ze hogere beloningen verzamelden en betere coördinatie vertoonden dan baselines.
• Coördinatie en botsingen: ARMS resulteerde in aanzienlijk minder genormaliseerde botsingen in vergelijking met PBRS en geen vorming, wat aangeeft dat het geleerde signaal gecoördineerd gedrag bevordert in plaats van alleen beloningsmaximalisatie.
• Exploratie-gevoeligheid: Een cruciale bevinding was dat ARMS kon falen om te convergeren naar optimale beleidsregels als de exploratie te laag was (bijvoorbeeld exploratiecoëfficiënt $\alpha = 0.023$), wat leidde tot agenten die de beloning "hackten" via oscillerend gedrag. Het verhogen van de exploratiecoëfficiënt (bijvoorbeeld $\alpha = 0.35$) stabiliseerde het leerproces en herstelde een hoge doorvoer.

5. Betekenis en Claims

Het artikel stelt dat ARMS het eerste automatische raamwerk voor beloningsvorming voor MARL is waarvan het ontwerp expliciet wordt gemotiveerd door een speltheoretisch resultaat voor het behoud van evenwichten.

In tegenstelling tot eerdere methoden die het risico lopen de strategische structuur van multi-agent problemen te veranderen, biedt ARMS een theoretische garantie dat de set van Nash-evenwichten onder specifieke voorwaarden behouden blijft. De auteurs benadrukken dat, hoewel trajectrangschikking effectief is in SARL, het in MARL een fundamenteel andere formulering vereist om n-stationariteit en het ontbreken van globale optimaliteit aan te pakken. Het raamwerk toont aan dat automatische, dichte beloningssignalen kunnen worden geleerd om MARL in omgevingen met sparse rewards te versnellen, zonder de integriteit van de oplossingsruimte van het spel te compromitteren, mits voldoende exploratie wordt gehandhaafd om suboptimale feedbacklussen te voorkomen.