Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning

1. Probleemstelling

Multi-Agent Reinforcement Learning (MARL) staat voor de uitdaging om grote populaties van interacterende agenten te coördineren. De kernproblemen zijn:

• Curse of Dimensionality: De gezamenlijke ruimte van toestanden en acties groeit exponentieel met het aantal agenten ($n$), wat exacte oplossingen onbereikbaar maakt voor grote schalen.
• Homogeniteitsaannames: Bestaande 'Mean-Field' methoden (die agenten aggregeren tot één gemiddelde entiteit) lossen de schaalbaarheid op, maar gaan uit van uniforme interacties. Dit is onrealistisch voor complexe systemen zoals verkeersstromen of robotzwermen, waar interacties heterogeen zijn (bijv. afhankelijk van afstand of lokale congestie).
• Berekeningskosten van Graphon-methoden: Recentere benaderingen gebruiken graphons (limietfuncties die interactiestructuren in dichte netwerken modelleren) om heterogeniteit vast te leggen. Echter, deze methoden vereisen vaak het aggregeren van de volledige populatie bij elke tijdstap, wat computationally onhaalbaar blijft naarmate $n$ groeit.

Het artikel stelt de vraag: Kan een mean-field MARL-algoritme heterogeniteit hanteren via niet-uniforme interacties, terwijl de berekeningskosten worden gereduceerd tot een polylogaritmische afhankelijkheid van het aantal agenten?

2. Methodologie: GMFS

De auteurs introduceren GMFS (Graphon Mean-Field Subsampling), een raamwerk dat de schaalbaarheid van subsampling combineert met de expressiviteit van graphon-theorie.

• Graphon-gebaseerde Heterogeniteit: Het systeem wordt gemodelleerd als een dicht graphon $W: [0,1]^2 \to [0,1]$. Elke agent $i$ heeft een latente coördinaat $\alpha_i$. De interactiestrkte tussen agent $i$ en $j$ wordt bepaald door $W(\alpha_i, \alpha_j)$. Dit stelt het model in staat om niet-uniforme interacties (bijv. sterkere invloed van naburige agenten) te modelleren.
• Gezond Subsampling (Subsampling): In plaats van alle $n$ agenten te observeren, selecteert elke agent $i$ een subset van $\kappa$ buren ($\kappa \ll n$).
  • Gewogen Subsampling: Agenten worden niet uniform gesampled, maar volgens de genormaliseerde graphon-gewichten $\bar{w}_{ij}$. Dit zorgt ervoor dat agenten met een sterke interactie (hoge gewichten) een grotere kans hebben om in de steekproef te komen, wat de variantie verlaagt.
• Leren en Executie:
  • Offline Training: Een centrale criticus leert een gedeelde Q-functie op een "surrogaatmodel" van $\kappa + 1$ agenten. Dit wordt gedaan via een Bellman-operator die is gedefinieerd op de gesamplede empirische verdelingen.
  • Decentralized Execution: Tijdens de uitvoering gebruikt elke agent lokaal alleen zijn eigen staat en de gesamplede gemiddelde toestand van zijn $\kappa$ buren om een actie te kiezen. De agent hoeft geen kennis te hebben van de identiteit of staat van de volledige populatie.

3. Belangrijkste Bijdragen

1. Het GMFS-algoritme: Een nieuw subsampling-raamwerk voor coöperatief MARL met heterogene agenten, waarbij graphon-gewogen mean-field interacties worden benaderd met slechts $\kappa$ gesamplede buren.
2. Theoretische Garantieën:
   • De auteurs bewijzen dat de Bellman-operator voor het gesamplede systeem een $\gamma$-contractie is, wat convergentie garandeert.
   • Ze leiden een optimaliteitskloof af van $\tilde{O}(1/\sqrt{\kappa})$. Dit betekent dat de kwaliteit van het beleid snel convergeert naar het optimale graphon-mean-field beleid naarmate $\kappa$ toeneemt.
   • Sample Complexiteit: De complexiteit wordt gereduceerd van exponentieel in $n$ ($(|S||A|)^n$) naar polynoom in $\kappa$ ($\kappa |S| |A|$). Zelfs bij $\kappa = O(\log n)$ is er een exponentiële versnelling ten opzichte van traditionele mean-field methoden.
3. Oplijzing van Variatie: Het artikel lost het probleem van positie-afhankelijke variantie op door gebruik te maken van graphon-gewogen subsampling in plaats van uniform sampling, wat essentieel is voor heterogene systemen.

4. Resultaten

• Numerieke Simulaties: De auteurs testen GMFS in een coöperatieve robotcoördinatietaak in een magazijnomgeving (met 25 agenten).
  • Prestatie: De resultaten tonen een monotoon stijgende gemiddelde afgepaste return naarmate $\kappa$ toeneemt. Bij een relatief klein $\kappa$ (bijv. 8 van de 25 agenten) wordt al bijna optimale prestatie behaald, die dicht bij de volledige mean-field limiet ligt.
  • Schaalbaarheid: De grootte van de Q-tabel (en dus de rekenkosten) groeit polynomiaal met $\kappa$, wat het mogelijk maakt om grote systemen te hanteren zonder de volledige populatie te hoeven verwerken.
• Theoretische Validatie: De experimentele resultaten bevestigen de theoretische voorspelling dat de optimaliteitskloof afneemt met $1/\sqrt{\kappa}$.

5. Significantie en Impact

Dit werk is significant omdat het een brug slaat tussen twee belangrijke gebieden:

1. Schaalbaarheid: Het overwint de "curse of dimensionality" in MARL door niet langer de volledige populatie te hoeven observeren.
2. Realisme: Het behoudt de noodzakelijke complexiteit van heterogene interacties (via graphons), die vaak worden genegeerd in traditionele mean-field benaderingen.

Toepassingsgebieden:
De methode is direct toepasbaar in domeinen waar lokale interacties en heterogeniteit cruciaal zijn, zoals:

• Autonoom rijden: Waar voertuigen vooral reageren op verkeer in hun directe omgeving.
• Robotzwermen: Voor coördinatie in beperkte ruimtes waar botsingsrisico's lokaal zijn.
• Slimme netwerken: Voor energieverdeling in smart grids met niet-uniforme transmissieverliezen.

Kortom, GMFS biedt een theoretisch onderbouwde en schaalbare oplossing voor het leren van optimale beleidslijnen in grote, heterogene multi-agent systemen, waarbij de rekenkosten onafhankelijk worden gemaakt van de totale populatiegrootte $n$.