Technische Samenvatting: ACPO: Agent-Chained Policy Optimization voor Multi-Agent Reinforcement Learning

Probleemstelling

Coöperatieve Multi-Agent Reinforcement Learning (MARL) streeft naar het vinden van gedecentraliseerde beleidsregels (policies) die gezamenlijk een gedeelde beloning maximaliseren. Onder het Centralized Training with Decentralized Execution (CTDE) paradigma blijft een fundamentele uitdaging bestaan: het direct berekenen van de gezamenlijke beleidsgradiënt (joint policy gradient) is moeilijk. Bestaande benaderingen vallen over het algemeen uiteen in twee categorieën, die beide significante beperkingen hebben:

1. Onafhankelijke Beleidsoptimalisatie (bijv. MAPPO, MADDPG): Agenten updaten hun beleid onafhankelijk met behulp van gecentraliseerde critics. Hoewel deze methoden schaalbaar zijn, ontbreken ze aan algemene garanties voor gezamenlijke beleidsverbetering omdat ze geen rekening houden met de niet-stationariteit die wordt geïntroduceerd door de veranderende beleidsregels van andere agenten. Convergentie is alleen gegarandeerd onder sterke structurele aannames, zoals waardedecompositie.
2. Alternerende Best-Response Optimalisatie (bijv. HAPPO, HATRPO): Agenten updaten sequentieel, waarbij zij de beleidsregels van anderen als vast beschouwen. Hoewel dit een monotone verbetering van de gezamenlijke beloning garandeert bij elke stap, is het vaste punt een Nash-evenwicht (NE). In coöperatieve settings kan een NE willekeurig suboptimaal zijn vergeleken met het werkelijke sociale optimum, en agenten hebben geen mechanisme om deze suboptimale evenwichten te verlaten.

Het artikel stelt dat geen van beide benaderingen effectief de optimale gezamenlijke beleidsregel van de onderliggende Multi-Agent MDP (MMDP) target zonder restrictieve aannames of convergentie naar suboptimale evenwichten.

Methodologie: Agent-Chained Policy Optimization (ACPO)

De kernbijdrage van het artikel is de afleiding van een exacte gedecentraliseerde decompositie van de gezamenlijke beleidsgradiënt. Dit wordt bereikt door de introductie van een nieuwe formalisering, de Agent-Chained Belief MDP (AC-BMDP), die het simultane gezamenlijke beslissingsprobleem transformeert naar een geserialiseerd beslissingsproces met imperfecte informatie.

1. De Agent-Chained Belief MDP (AC-BMDP)

Gemotiveerd door speltheoretische resultaten die stellen dat simultane spelen kunnen worden geherformuleerd als geserialiseerde processen met imperfecte informatie, deelt de auteurs elke omgevingstijdstap $t$ op in $N$ micro-stappen, één voor elke agent $i \in \{1, \dots, N\}$.

• Serialisatie: Agenten committeren acties sequentieel binnen een enkele tijdstap. Agent $i$ handelt na agenten $1$ tot en met $i-1$.
• Toestandsaugmentatie: De toestand voor agent $i$ wordt uitgebreid met een belief $b^{(i)}_t$ over de gerealiseerde acties van voorafgaande agenten ($\vec{a}^{<i}_t$).
• Gedecentraliseerde Executie: Omdat de gerealiseerde acties van voorafgaande agenten niet worden waargenomen tijdens de executie, wordt de belief geconstrueerd uit de actieverdelingen ($\phi^{(j)}_t$) van voorafgaande agenten. Deze verdelingen zijn deterministische functies van de gedeelde toestand en de beleidsregels van de agenten, waardoor ze toegankelijk zijn zonder communicatie.
• Chained Bellman Operators: De waardefunctie voor agent $i$, $Q^{(i)}$, wordt recursief gedefinieerd. De waarde van agent $i$ hangt af van de waarde van agent $i+1$ (de volgende agent in de keten). Alleen de laatste agent ($N$) ontvangt de beloning van de omgeving en bootstrapt naar de waarde van de eerste agent bij de volgende tijdstap. Deze "keten" (chaining) maakt credit assignment mogelijk zonder een decomponeerbare gezamenlijke waardefunctie te veronderstellen.

2. Theoretische Fundamenten

Het artikel stelt twee belangrijke stellingen vast:

• Agent-Chained Policy Gradient Theorem: De beleidsgradiënt voor de AC-BMDP kan worden berekend met behulp van een standaard scorefunctie en een gedecentraliseerde critic $Q^{(i)}$ die alleen conditioneel is op de eigen toestand van de agent en de belief over voorafgaande acties.
• Multi-Agent Policy Gradient Decomposition Theorem: De gezamenlijke beleidsgradiënt van de oorspronkelijke MMDP wordt getoond exact equivalent te zijn aan een som van $N$ onafhankelijke per-agent termen afgeleid van de AC-BMDP.
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  Cruciaal is dat deze decompositie geen structurele aannames vereist op de gezamenlijke waardefunctie (in tegenstelling tot VDN of QMIX) en de suboptimale vaste punten van alternerende updates vermijdt.

3. Algoritmische Instantiaties

De auteurs instantiëren ACPO in twee praktische vormen:

• ACPPO (On-Policy): Een PPO-gebaseerd algoritme waarbij elke agent een afgeknipte (clipped) surrogate objective optimaliseert met behulp van de agent-chained advantage schattingen. De advantage wordt berekend via een Generalized Advantage Estimation (GAE) die de chained Temporal Difference (TD) residuen over de agent-keten opstelt.
• ACTD3 (Off-Policy): Een TD3-gebaseerd algoritme voor continue controle, waarbij agenten twee twin critics bijhouden volgens de chained Bellman-structuur.

Belief Approximatie:

• In volledig observeerbare (MMDP) settings berekenen agenten beliefs exact door de policy netwerken van voorafgaande agenten te bevragen.
• In gedeeltelijk observeerbare (Dec-POMDP) settings gebruiken agenten een Action Belief Network om de actieverdelingen van voorafgaande agenten te voorspellen op basis van hun eigen lokale historie, getraind via een KL-divergentie verliesfunctie tegenover de gecentraliseerde target.

Belangrijkste Bijdragen

1. Formalisering van AC-BMDP: De introductie van een formeel kader dat serialisatie combineert met belief-augmentatie, wat optimale gezamenlijke beleidsoptimalisatie mogelijk maakt onder CTDE zonder waardedecompositie-aannames.
2. Exacte Gradiënt Decompositie: Het bewijs dat de gezamenlijke beleidsgradiënt exact een decompositie toelaat in per-agent termen, waardoor onafhankelijke updates collectief een enkele gradiëntstap op de gezamenlijke doelstelling vormen.
3. Convergentie naar Optimale Gezamenlijke Beleidsregel: In tegenstelling tot alternerende methoden die convergeren naar Nash-evenwichten, bewijst het artikel dat in tabulaire settings, Agent-Chained Policy Iteration (ACPI) convergeert naar de optimale gezamenlijke beleidsregel van de onderliggende MMDP.
4. Schaalbare Algoritmen: De ontwikkeling van ACPPO en ACTD3, die aantonen dat agent-chaining kan worden toegepast op zowel on-policy als off-policy deep RL algoritmen.

Experimentele Resultaten

De auteurs evalueerden ACPO op drie standaard benchmarks: Multi-Robot Warehouse (RWARE), SMACv2, en MA-MuJoCo.

• Prestaties: ACPO (specifiek ACPPO) presteerde consistent beter dan sterke baselines, inclusief MAPPO (onafhankelijke optimalisatie), HAPPO/HATRPO (alternerende optimalisatie) en waardedecompositie-methoden (VDN, QMIX).
• Schaalbaarheid met Agenten: Een kritieke bevinding is dat het prestatieverschil tussen ACPO en baselines groter wordt naarmate het aantal agenten toeneemt. In RWARE was het voordeel het meest uitgesproken in scenario's met 8 en 12 agenten, wat suggereert dat ACPO bijzonder effectief is in omgevingen met hoge coördinatie en drukte.
• Off-Policy Prestaties: De off-policy variant, ACTD3, presteerde ook beter dan baselines (MADDPG, HATD3) in MA-MuJoCo, wat de algemeenheid van het agent-chaining mechanisme aantoont.
• Ablatie Studies: Het verwijderen van het agent-chaining mechanisme (waardoor ACPPO werd gereduceerd tot MAPPO met belief inputs) resulteerde in prestaties vergelijkbaar met MAPPO, wat bevestigt dat de winst voortkomt uit de chained advantage berekening, en niet enkel uit de toevoeging van belief states.
• Efficiëntie: Hoewel ACPO sequentiële belief-berekening vereist, blijft de wall-clock trainingstijd vergelijkbaar met MAPPO en is deze aanzienlijk sneller dan alternerende methoden (HAPPO/HATRPO), die sequentiële agent-updates vereisen tijdens de training.

Betekenis en Claims

Het artikel claimt dat ACPO een geprincieerde oplossing biedt voor het coöperatieve MARL-probleem onder CTDE. De significantie ligt in:

• Het overbruggen van de kloof: Het verenigt de voordelen van onafhankelijke updates (schaalbaarheid) en alternerende updates (garanties voor monotone verbetering) terwijl het hun respectievelijke nadelen (niet-stationariteit en suboptimale Nash-evenwichten) vermijdt.
• Theoretische Rigor: Het biedt de eerste exacte decompositie van de gezamenlijke beleidsgradiënt die niet afhankelijk is van waardedecompositie-aannames, wat theoretisch convergentie naar het sociale optimum garandeert in tabulaire settings.
• Praktische Effectiviteit: Empirische resultaten suggereren dat expliciete coördinatie via belief chaining een superieur mechanisme is voor het afhandelen van complexe multi-agent coördinatietaken vergeleken met huidige state-of-the-art methoden, vooral naarmate de complexiteit van de agentenpopulatie groeit.

De auteurs merken bescheiden de beperkingen op, specifiek dat de belief-berekening lineair schaalt met het aantal agenten (wat leidt tot $O(N^2)$ forward passes) en dat de huidige theoretische garanties steunen op volledige observeerbaarheid (MMDP), waarbij de uitbreiding naar algemene Dec-POMDP's als toekomstig werk wordt beschouwd.