A Distributed Primal-Dual Method for Constrained Multi-agent Reinforcement Learning with General Parameterization

Technische Samenvatting: Een Gedistribueerde Primaal-Duale Methode voor Gelimiteerde Multi-agent Versterkende Leer met Algemene Parametrisering

Probleemformulering
Dit artikel behandelt de uitdaging van Coöperatieve Gelimiteerde Multi-agent Versterkende Leer (CMARL) binnen een netwerksetting. Het probleem wordt geformuleerd als een Gelimiteerd Markov-spel (CMG) met $N$ agenten die opereren in een gedeelde omgeving. De agenten werken samen om een globale objectief functie te minimaliseren, gedefinieerd als het gemiddelde van lokale verwachte kosten, onderworpen aan $K$ globale beperkingen. Deze beperkingen worden eveneens geformuleerd als het gemiddelde van lokale beperkingskosten over alle agenten.

Een kritisch onderscheid van dit werk is de vereiste voor volledig gedecentraliseerd online leren. In tegenstelling tot centraal trainen of methoden die coördinatie tijdens uitvoering vereisen, gaat het voorgestelde uitgangspunt ervan uit dat agenten onafhankelijk handelen met uitsluitend lokale informatie en lokale communicatie met buren. Het probleem wordt bemoeilijkt door het feit dat, in tegenstelling tot single-agent gelimiteerde RL, coöperatieve CMARL vaak een niet-nul dualiteitskloof vertoont, met name bij gebruik van algemene functiebenadering (geparametriseerde beleidsregels). Deze kloof introduceert inherente complexiteit in het voldoen aan globale beperkingen terwijl de globale objectief wordt geoptimaliseerd.

Methodologie
De auteurs stellen een gedistribueerd primaal-duaal algoritme voor gebaseerd op het actor-critic-kader. De kerninnovatie ligt in hoe agenten de Lagrange-multiplicatoren behandelen die geassocieerd zijn met de globale beperkingen.

1. Lokale Schatting van Multiplicatoren: In plaats van te vertrouwen op een centrale coördinator voor het berekenen van globale Lagrange-multiplicatoren, onderhoudt elke agent $n$ een lokale schatting $\hat{\lambda}_n$ van de globale multiplicatorvector $\lambda$.
2. Gedecomposeerde Objectief: De globale Lagrangiaan wordt herschreven met behulp van deze lokale schattingen. De agenten optimaliseren een lokale Lagrangiaanse objectief die afhankelijk is van hun eigen beleidsparameters $\theta_n$ en hun lokale multiplicatorschattingen $\hat{\lambda}_n$.
3. Drie-tijdschaal Update: Het algoritme werkt op drie distincte tijdschalen om convergentie te garanderen:
   • Snelste Tijdschaal (Critic): Agenten updaten hun lokale waardefunctie-approximatoren (critics) met Temporal Difference (TD) leren om de lokale Lagrangiaanse kosten te schatten.
   • Intermediaire Tijdschaal (Actor): Agenten updaten hun beleidsparameters (actors) met behulp van een beleidsgradiëntstelling die is aangepast voor de multi-agent setting, gebruikmakend van de geschatte advantage-functie.
   • Langzaamste Tijdschaal (Dual/Multiplicatoren): Agenten updaten hun lokale Lagrange-multiplicatorschattingen. Deze update omvat twee stappen: een consensusstap waarbij agenten hun schattingen middelen met buren (met behulp van een dubbel-stochastische communicatiematrix), en een opwaartse stap gebaseerd op de lokale beperkingsovertreding.
4. Consensusmechanisme: Het algoritme dwingt consensus af tussen de lokale multiplicatorschattingen $\hat{\lambda}_n$ over het netwerk. Theoretische analyse bewijst dat deze lokale schattingen convergeren naar een gemeenschappelijke waarde, waardoor de globale multiplicator effectief wordt gereconstrueerd zonder centrale coördinatie.

Belangrijkste Bijdragen
Het artikel levert vier primaire bijdragen:

1. Gedistribueerde Formulering: Het introduceert een nieuwe gedistribueerde formulering voor Lagrange-multiplicatoren in coöperatieve CMARL, waarbij elke agent zijn eigen lokale schattingen onderhoudt en updatet met uitsluitend lokale informatie en communicatie met buren.
2. Algoritme-ontwikkeling: Het ontwikkelt een gedistribueerd online primaal-duaal algoritme dat actor-critic-methoden gebruikt met algemene functiebenadering (lineaire critics en geparametriseerde beleidsregels).
3. Convergentiegaranties: De auteurs leveren theoretische bewijzen die aantonen dat de lokale Lagrange-multiplicatoren bijna zeker consensus bereiken en dat het totale algoritme convergeert naar een evenwichtspunt van het geprojecteerde dynamische systeem.
4. Sub-optimaliteit en Haalbaarheidsanalyse: Het artikel analyseert de haalbaarheid van de beperkingen op het evenwicht en kwantificeert de sub-optimaliteit van de oplossing. Het leidt een bovengrens af voor de dualiteitskloof voor het geparametriseerde probleem, rekening houdend met fouten die worden geïntroduceerd door beleidsparametrisering en het consensusproces.

Experimentele Resultaten
Om de aanpak te valideren, evalueerden de auteurs het algoritme op een gelimiteerd coöperatief Cournot-spel met stochastische dynamiek. In dit scenario treden agenten op als producenten in een markt, waarbij ze productieniveaus kiezen om winst te maximaliseren (kosten te minimaliseren) terwijl ze zich houden aan prijsgebaseerde beperkingen.

• Consensus: Simulatie-resultaten (Figuur 1) tonen aan dat de lokaal geschatte Lagrange-multiplicatoren voor verschillende agenten convergeren naar een consensuswaarde.
• Prestatie: De trainingscurven (Figuur 2) tonen aan dat het algoritme de globale objectiefkosten succesvol minimaliseert terwijl de globale beperkingsovertredingen dicht bij nul worden gehouden.

Betekenis en Claims
Het artikel claimt een gat in de literatuur aan te pakken waar slechts weinig methoden algemene CMARL-problemen met gekoppelde lokale kosten en globale beperkingen op een volledig gedecentraliseerde manier behandelen. Waar bestaande werken vaak vertrouwen op centraal trainen, parameterdeling met homogene agenten, of communicatie tijdens uitvoering, maakt deze methode volledig gedecentraliseerd online leren mogelijk.

De auteurs formuleren hun bijdrage bescheiden als een gelimiteerde uitbreiding van bestaande ongelimiteerde gedistribueerde actor-critic-methoden (met name verwijzend naar eerder werk over ongelimiteerde MARL). Zij erkennen dat, vanwege de niet-nul dualiteitskloof in geparametriseerde coöperatieve settings, het algoritme convergeert naar een evenwichtspunt dat sub-optimaal kan zijn ten opzichte van de exacte oplossing van het ongeparametriseerde probleem. Echter, de voorgestelde methode biedt een schaalbare, gedecentraliseerde oplossing die waarborgt dat beperkingen worden nageleefd in complexe, real-world scenario's zoals slimme netwerken en autonome systemen, zonder de schaalbaarheidsknelpunten van centrale benaderingen.