Technische Samenvatting: Coördinatiegrafieken voor Constrained Multi-Agent Reinforcement Learning (CG-CMARL)

1. Probleemformulering

Het artikel behandelt Constrained Multi-Agent Reinforcement Learning (CMARL), een domein waar meerdere coöperatieve agenten een primaire doelstelling moeten maximaliseren terwijl zij aan veiligheidsrestricties voldoen (bijv. botsingsvermijding, energiebudgetten). De auteurs identificeren twee verweven uitdagingen:

1. Schaalbaarheid: De gezamenlijke actieruimte groeit exponentieel met het aantal agenten ($N$), waardoor gecentraliseerde benaderingen onhandelbaar worden voor gemiddelde teamgroottes.
2. Constraint Coupling (Restrictie-koppeling): Veiligheidsrestricties koppelen agenten vaak op manieren die door beloningsstructuren alleen niet worden gevangen. Onafhankelijke leerders die hun eigen Lagrange-multiplicatoren optimaliseren, kunnen collectief globale restricties schenden, terwijl gecentraliseerde primal-dual methoden toegang vereisen tot de globale staat en de gezamenlijke actieruimte, wat de voordelen van gefactoriseerde benaderingen tenietdoet.

Het probleem wordt geformaliseerd als een Constrained Markov Decision Process (CMDP) waarbij het doel is om de verwachte gedisconteerde primaire beloning $V^\pi_0$ te maximaliseren, onder de voorwaarde dat de restrictie-beloningen $V^\pi_j$ specifieke drempelwaarden overschrijden. De auteurs gaan uit van onafhankelijke transities (de volgende toestanden van agenten hangen alleen af van hun eigen acties) en additieve beloningsfactorisatie over een coördinatiegrafiek, waarbij beloningen worden gedecomposeerd in regionale componenten (specifiek paargewijze regio's).

2. Methodologie: CG-CMARL

Het voorgestelde framework, CG-CMARL, integreert Coördinatiegrafieken (CG) met Lagrange-dualiteit om schaalbare, gedecentraliseerde restrictie-optimalisatie te bereiken. De methode werkt onder een Centralized Training, Decentralized Execution (CTDE) paradigma.

2.1 Two-Head Q-functie Architectuur

In plaats van één enkele Q-functie te leren voor een gecombineerd signaal (wat hertraining vereist voor verschillende afwegingen), onderhoudt CG-CMARL twee aparte Q-functies per regio:

• Primaire Head ($Q_{prim}$): Leert de optimale regionale Q-functie voor de primaire doelstelling met behulp van standaard Q-learning.
• Cost Head ($Q_{cost}$): Leert de verwachte restrictie-beloning (bijv. botsingskosten) onder het door de primaire head geïnduceerde gulzigheidbeleid (greedy policy). Cruciaal is dat de cost head niet zijn eigen waarde maximaliseert; het evalueert de consequenties van de beslissingen van de primaire agent. Dit zorgt voor coherente compositie tijdens de actie-selectie.

2.2 Lagrangian Trade-off en Pareto Sweeping

Tijdens de uitvoering worden de twee heads gecombineerd via een Lagrange-multiplier $\lambda$:
$$Q_{aug, R}(s_R, a_R) = Q_{prim, R}(s_R, a_R) + \lambda Q_{cost, R}(s_R, a_R)$$

• Training: Agenten onderhouden lokale multipliers $\lambda_i$ die worden bijgewerkt via geprojecteerde dual ascent op basis van geobserveerde restrictie-schendingen. De gemiddelde multiplier $\bar{\lambda}$ wordt gebruikt tijdens de actie-selectie.
• Evaluatie: Door $\lambda$ over een bereik te laten "sweepen" op een enkel getraind model, traceert het systeem de volledige doelstelling-restrictie Pareto-front zonder hertraining. Dit ontkoppelt de restrictie-afweging van het leerproces.

2.3 Max-Sum Message Passing

Om acties over de factorgrafiek te coördineren zonder gecentraliseerde berekening, gebruikt de methode Max-Sum message passing:

• Agenten (variabele knopen) en regionale Q-functies (factor knopen) wisselen berichten uit om de combinatorische optimalisatie $\max_a \sum_R Q_{aug, R}(s_R, a_R)$ op te lossen.
• Damping (Demping): Omdat paargewijze coördinatiegrafieken cycli bevatten voor $N \ge 3$, wordt message damping toegepast om convergentie te stabiliseren.
• Complexiteit: De complexiteit per stap is polynomiaal in $N$ ($O(N^2 |A| K)$), een significante verbetering ten opzichte van de exponentiële $O(|A|^N)$ van exhaustieve zoektochten.

2.4 Parameter Sharing

Alle paargewijze regio's delen een enkele set Q-functie parameters. Aangezien elke regio precies twee agenten bevat, is het aantal geleerde modellen $O(1)$ ongeacht de teamgrootte $N$, wat schaling naar grote teams mogelijk maakt.

3. Theoretische Bijdragen

Het artikel biedt rigoureuze theoretische garanties onder milde aannames (onafhankelijke transities, beloningsfactorisatie, Slater's conditie):

• Convergentie: De two-head Q-learning convergeert bijna zeker naar de optimale regionale Q-functie en de restrictiewaarde onder het primaire gulzige beleid. De gemiddelde Lagrange-multiplier convergeert naar de optimale duale oplossing.
• Compositionele Foutmarge (Error Bound): Het artikel leidt een grens af op de kloof tussen de geleerde oplossing en het ware optimum, waarbij de fout wordt gedecomposeerd in vier interpreteerbare bronnen:
  1. Structurele Fout ($\beta$): Ontstaat door de factorisatie-benadering (overlappende regio's).
  2. Coördinatiefout ($\epsilon_{MS}$): Ontstaat door de benaderende aard van Max-Sum op loopy grafen.
  3. Samplingfout: Door eindige data ($O(1/\sqrt{n})$).
  4. Representatiefout: Door functie-approximatie ($\epsilon_{NN}$).
     De grens kwantificeert hoe deze fouten door de Bellman-backup propageren, wat kwalitatieve sturing biedt voor systeemontwerp.

4. Experimentele Resultaten

De methode werd geëvalueerd op de Simple Spread coöperatieve navigatie benchmark (PettingZoo/MPE) met teamgroottes $N \in \{3, 4, 6, 10\}$.

• Baselines: Vergeleken met IQL, QMIX, Deep Coordination Graphs (DCG), MAPPO, en MAPPO-Lagrangian.
• Prestaties: CG-CMARL produceert Pareto-fronten die alle baselines domineren. Terwijl andere methoden (QMIX, MAPPO, etc.) aparte training-runs vereisen voor vaste reward-shaping ratio's (wat resulteert in enkelvoudige werkpunten), traceert CG-CMARL de volledige afwegingscurve vanuit één model.
• Schaalbaarheid: De methode schaalt naar $N=10$ agenten, waarbij gecentraliseerde benaderingen onhandelbaar worden. De dichtheid van de paargewijze coördinatiegrafiek neemt toe met $N$, maar de methode behoudt de prestaties, waarbij de structurele fout in de praktijk klein blijft door de zwakke koppeling tussen paargewijze botsingsstraffen ten opzichte van landmark beloningen.
• Veiligheid: De methode balanceert effectief tussen dekking (primaire doelstelling) en botsingsvermijding (restrictie), waarbij de Lagrange-multiplier het beleid succesvol richting haalbaarheid stuurt.

5. Betekenis en Claims

Het artikel claimt dat CG-CMARL het eerste werk is dat de schaalbaarheid van gefactoriseerde waardefuncties (via coördinatiegrafieken) combineert met de restrictie-afhandelingscapaciteiten van Lagrange-methoden in een gedecentraliseerde architectuur met convergentiegaranties.

Belangrijke claims zijn onder meer:

• Ontkoppeling van Leren en Afweging: Door het leren van primaire en restrictie-beloningen te scheiden, maakt de methode post-hoc exploratie van het Pareto-front mogelijk zonder hertraining, een capaciteit die ontbreekt in standaard constrained RL-benaderingen.
• Schaalbare Decentralisatie: Het framework bereikt een $O(1)$ modelcomplexiteit en een polynomiale actie-selectie complexiteit, waarmee de "vloek van de dimensionaliteit" in multi-agent gezamenlijke actieruimtes wordt overwonnen.
• Interpreteerbaarheid: De compositionele foutmarge linkt prestatiekloven expliciet aan specifieke ontwerpkeuzes (grafiektopologie, sampling, netwerkcapaciteit), wat een geprincipeerde manier biedt om systemen te analyseren en te verbeteren.

De auteurs erkennen beperkingen, waarbij zij opmerken dat de paargewijze grafiek dicht wordt voor grote $N$ (wat de Max-Sum berekening verhoogt) en dat de two-head formulering een conservatieve benadering inhoudt (de cost head evalueert het primaire-gulzige beleid, niet het uiteindelijke beleid). Zij suggereren dat toekomstig werk een $\lambda$-augmented formulering zou kunnen verkennen (conditionering van de Q-functie direct op $\lambda$) om de conservatieve benadering theoretisch op te lossen, zij het ten koste van de sample complexiteit.