Technische Samenvatting: Graph-SND: Sparse Aggregation voor Gedragsdiversiteit in Multi-Agent Reinforcement Learning

1. Probleemstelling

In Multi-Agent Reinforcement Learning (MARL) is System Neural Diversity (SND) een metriek die wordt gebruikt om gedragsheterogeniteit tussen agenten te meten door de gemiddelde paarsgewijze Wasserstein-afstanden tussen hun actie-distributies te berekenen. Hoewel SND diversiteitscontrole mogelijk maakt (bijvoorbeeld via het DiCo-algoritme), vormt de berekening ervan een ernstig schaalbaarheidsprobleem. Het berekenen van volledige SND vereist het evalueren van alle $\binom{n}{2}$ agentparen, wat resulteert in een kwadratische complexiteit van $O(n^2)$ in het aantal agenten $n$. Deze aggregatiekosten worden onbetaalbaar voor teams op grote schaal, waardoor de praktische toepassing van diversiteitsbewuste training en controle beperkt wordt. Het artikel identificeert de stap "subgroep-naar-systeem-aggregatie" als de belangrijkste open uitdaging, waarbij wordt opgemerkt dat bestaande metrieken de gemiddelde waarde over alle paren behandelen als een vaste, niet-onderhandelbare vereiste.

2. Methodologie: Graph-SND

De auteurs introduceren Graph-SND, een generalisatie van SND die het gemiddelde over een compleet graf vervangt door een gewogen gemiddelde over de randen van een willekeurige graf $G = (A, E, w)$.

Definitie

Laat $d(i, j)$ de Monte Carlo-gedragsafstand zijn tussen agent $i$ en agent $j$. Graph-SND wordt gedefinieerd als:
$$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$$
waarbij $W(G) = \sum_{\{i,j\} \in E} w_{ij}$ het totale randgewicht is.

Drie Operationele Regimes

Het kader ondersteunt drie distincte regimes op basis van de keuze van de graf $G$:

1. Exacte Herstelling ($G = K_n$): Wanneer $G$ de complete graf is met eenheidsgewichten, herstelt Graph-SND de originele SND exact.
2. Gelokaliseerde Diversiteit (Vaste Sparse Grafen): Wanneer $G$ een vaste sparse graf is (bijvoorbeeld $k$-naaste buren, communicatietopologie), meet de metriek diversiteit alleen over taakrelevante interacties. Dit reduceert de rekenkosten tot $O(|E|)$.
3. Sparse Schatting (Willekeurige Grafen): Wanneer randen willekeurig worden bemonsterd (bijvoorbeeld Bernoulli-bemonstering), fungeert Graph-SND als een sparse schatter van de volledige SND.
   • Ongewenste Schatting: Met behulp van Horvitz-Thompson-gewichten ($w_{ij} = 1/p$) is de schatter onvoorwaardelijk onbevooroordeeld.
   • Concentratie: De genormaliseerde steekproefgemiddelde (uniforme gewichten) voldoet aan Hoeffding-type concentratiegrenzen en convergeert naar de ware SND met een snelheid van $O(1/\sqrt{m})$, waarbij $m$ het aantal bemonsterde randen is.

Theoretische Grenzen

• Deterministische Distorsie: Voor vaste verbonden grafen leidt het artikel grenzen af die $\text{SND}_G$ relateren aan $\text{SND}$ met behulp van de edge forwarding index $\pi(G)$. Specifiek wordt $|\text{SND}_G - \text{SND}|$ begrensd door factoren die $\pi(G)$ bevatten.
• Expander Grafen: Voor willekeurige $d$-regelmatige expander grafen schaal de forwarding index als $O(n \log n / d)$. De auteurs bewijzen dat met $d = \Theta(\log n)$ de worst-case relatieve distorsie $O(\log n)$ is.
• Spectrale Verfijning: Onder lage-rang afstandsstructuren (gecontroleerde genormaliseerde nucleaire norm) verbetert de foutgrens voor expanders tot $O(\rho^*/\sqrt{d})$, wat empirische ratio's dicht bij één verklaart.
• Probabilistische Grenzen: Voor willekeurige $d$-regelmatige grafen wordt een onvoorwaardelijke probabilistische grens van $\tilde{O}(D_{\max}/\sqrt{n})$ vastgesteld.

3. Belangrijkste Bijdragen

1. Definitie van Graph-SND: Een sparse aggregatielaag die SND herstelt op complete grafen en kosten van $O(|E|)$ heeft op vooraf berekende grafen.
2. Theoretische Garanties: Bewijzen van herstel, niet-negativiteit, graf-automorfisme-invariantie, Horvitz-Thompson-onbevooroordeeldheid en concentratieongelijkheden (Hoeffding/Serfling). Het artikel stelt ook deterministische distorsiegrenzen vast voor vaste grafen en onvoorwaardelijke probabilistische grenzen voor willekeurige regelmatige grafen.
3. Empirische Validatie:
   • Herstel & Onbevooroordeeldheid: Geverifieerd in VMAS-omgevingen, waarbij exacte herstelling op $K_4$ en onbevooroordeeldheid van de Horvitz-Thompson-schatting bij $n=8$ worden aangetoond.
   • Schaalbaarheid: Aangetoonde muurkloksnelheidswinsten die lineair schalen met $1/p$ (bemonsteringswaarschijnlijkheid) tot $n=500$.
   • Closed-Loop Controle: Graph-SND geïntegreerd in de DiCo-diversiteitscontroller. Bij $n=50$ volgde Bernoulli-0.1 Graph-SND setpoints met een relatieve fout onder de 1% en produceerde beloningsverschillen die niet te onderscheiden waren van nul in vergelijking met volledige SND, terwijl de kosten per aanroep van de metriek met $\sim 9,5\times$ werden gereduceerd.
   • Expander Prestaties: Willekeurige $d$-regelmatige expanders bereikten $\text{SND}_G/\text{SND} \in [0,9987, 1,0013]$ bij $\Theta(n \log n)$ randen, wat significant beter presteerde dan andere sparse baselines in verhouding distorsie-tot-kosten.

4. Resultaten

• Efficiëntie: In een PPO-run van 500 iteraties met $n=100$ volgde Bernoulli-0.1 Graph-SND de volledige SND, terwijl de tijd per aanroep van de metriek met ongeveer $10\times$ werd gereduceerd.
• Schaalbaarheid: GPU-timing bij vast beleid tot $n=500$ bevestigde de voorspelde snelheidswinst $\binom{n}{2}/|E|$, waarbij de metriektijd bij $n=500$ met 10% randdichtheid van ~15,5 seconden werd gereduceerd tot ~1,5 seconden.
• Controlestabiliteit: In DiCo-experimenten bij n=50} handhaafde de sparse controller setpoint-tracking en leverde gepaarde beloningsverschillen op die rond nul lagen over negen gekoppelde cellen, met een gemiddeld beloningsverschil van -6,2 \times 10^{-4}$.
• Robuustheid: De methode werd overgebracht naar niet-Gaussische settings (PettingZoo MPE met categorische beleidsplannen en Total Variation Distance), waarbij kleine bias en kostenreducties behouden bleven.

5. Betekenis en Claims

Het artikel beweert dat Graph-SND succesvol de aggregatiebottleneck van SND verwijdert zonder de semantiek van de metriek te veranderen of wijzigingen in beleidsarchitecturen of trainingsalgoritmen te vereisen.

• Drop-in Alternatief: Het biedt een "drop-in sparse alternatief" dat schaalt buiten complete-graf SND, en zowel passieve meting als closed-loop diversiteitscontrole ondersteunt.
• Semantische Flexibiliteit: De graf $G$ wordt gepresenteerd niet als een lastige parameter, maar als een bewuste keuze die het meetdoel bepaalt:
  • Gebruik Bernoulli-bemonstering om volledige systeemdiversiteit te schatten.
  • Gebruik vaste lokale grafen (bijvoorbeeld communicatie, $k$-NN) om diversiteit te meten die relevant is voor specifieke interactiestructuren.
  • Gebruik expander grafen voor deterministische, bijna-lineaire sparse proxies met sterke worst-case structurele garanties.
• Beperkte Beperkingen: De auteurs erkennen dat hoewel theoretische grenzen voor expanders $O(\log n)$ zijn, de waargenomen ratio's dicht bij één data-afhankelijk zijn en deels worden verklaard door de spectrale eigenschappen van MARL-afstandsmatrices. Zij merken ook op dat de huidige experimenten zich richten op Independent PPO, waarbij algoritmen met gecentraliseerde criticus voor toekomstig werk worden achtergelaten.

Kortom, Graph-SND herformuleert diversiteitsaggregatie als een graf-selectieprobleem, en biedt een unificerend kader dat rekenkundige efficiëntie in evenwicht brengt met theoretische garanties voor gedragsdiversiteit in MARL.