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

Sintesi Tecnica: Un Metodo Primal-Duale Distribuito per l'Apprendimento per Rinforzo Multi-Agente Vincolato con Parametrizzazione Generale

Formulazione del Problema
Questo articolo affronta la sfida dell'Apprendimento per Rinforzo Multi-Agente Vincolato Cooperativo (CMARL) in un contesto di rete. Il problema è inquadrato come un Gioco di Markov Vincolato (CMG) che coinvolge $N$ agenti operanti in un ambiente condiviso. Gli agenti cooperano per minimizzare una funzione obiettivo globale, definita come la media dei costi locali attesi, sottoposta a $K$ vincoli globali. Anche questi vincoli sono formulati come la media dei costi dei vincoli locali su tutti gli agenti.

Una distinzione critica di questo lavoro è il requisito di apprendimento online completamente decentralizzato. A differenza dell'addestramento centralizzato o dei metodi che richiedono coordinamento durante l'esecuzione, l'approccio proposto assume che gli agenti agiscano in modo indipendente utilizzando solo informazioni locali e comunicazione locale con i vicini. Il problema è complicato dal fatto che, a differenza dell'RL vincolato ad agente singolo, il CMARL cooperativo spesso presenta un gap di dualità non nullo, in particolare quando si utilizza un'approssimazione di funzione generale (politiche parametrizzate). Questo gap introduce una complessità intrinseca nel soddisfare i vincoli globali mentre si ottimizza l'obiettivo globale.

Metodologia
Gli autori propongono un algoritmo primal-duale distribuito basato sul framework actor-critic. L'innovazione principale risiede nel modo in cui gli agenti gestiscono i moltiplicatori di Lagrange associati ai vincoli globali.

1. Stima Locale dei Moltiplicatori: Invece di affidarsi a un coordinatore centrale per calcolare i moltiplicatori di Lagrange globali, ogni agente $n$ mantiene una stima locale $\hat{\lambda}_n$ del vettore dei moltiplicatori globali $\lambda$.
2. Oggetto Decomposto: Il Lagrangiano globale è riformulato utilizzando queste stime locali. Gli agenti ottimizzano un obiettivo Lagrangiano locale che dipende dai propri parametri della politica $\theta_n$ e dalle proprie stime locali dei moltiplicatori $\hat{\lambda}_n$.
3. Aggiornamento a Tre Scale Temporali: L'algoritmo opera su tre scale temporali distinte per garantire la convergenza:
   • Scala Temporale Più Veloce (Critic): Gli agenti aggiornano i loro approssimatori locali della funzione valore (critics) utilizzando l'apprendimento Temporal Difference (TD) per stimare il costo Lagrangiano locale.
   • Scala Temporale Intermedia (Actor): Gli agenti aggiornano i propri parametri della politica (actor) utilizzando un teorema del gradiente della politica adattato all'impostazione multi-agente, sfruttando la funzione di vantaggio stimata.
   • Scala Temporale Più Lenta (Duale/Moltiplicatori): Gli agenti aggiornano le proprie stime locali dei moltiplicatori di Lagrange. Questo aggiornamento comporta due passaggi: un passaggio di consenso in cui gli agenti mediando le loro stime con i vicini (utilizzando una matrice di comunicazione doppiamente stocastica) e un passaggio di ascesa basato sulla violazione locale del vincolo.
4. Meccanismo di Consenso: L'algoritmo impone il consenso tra le stime locali dei moltiplicatori $\hat{\lambda}_n$ attraverso la rete. L'analisi teorica dimostra che queste stime locali convergono a un valore comune, ricostruendo efficacemente il moltiplicatore globale senza coordinamento centralizzato.

Contributi Chiave
L'articolo apporta quattro contributi principali:

1. Formulazione Distribuita: Introduce una nuova formulazione distribuita per i moltiplicatori di Lagrange nel CMARL cooperativo, dove ogni agente mantiene e aggiorna le proprie stime locali utilizzando solo informazioni locali e comunicazione con i vicini.
2. Sviluppo dell'Algoritmo: Sviluppa un algoritmo primal-duale online distribuito che utilizza metodi actor-critic con approssimazione di funzione generale (critics lineari e politiche parametrizzate).
3. Garanzie di Convergenza: Gli autori forniscono dimostrazioni teoriche che dimostrano che i moltiplicatori di Lagrange locali raggiungono il consenso quasi certamente e che l'algoritmo complessivo converge a un punto di equilibrio del sistema dinamico proiettato.
4. Analisi di Sub-ottimalità e Fattibilità: L'articolo analizza la fattibilità dei vincoli all'equilibrio e quantifica la sub-ottimalità della soluzione. Deriva un limite superiore per il gap di dualità per il problema parametrizzato, tenendo conto degli errori introdotti dalla parametrizzazione della politica e dal processo di consenso.

Risultati Sperimentali
Per validare l'approccio, gli autori hanno valutato l'algoritmo su un gioco di Cournot cooperativo vincolato con dinamiche stocastiche. In questo scenario, gli agenti agiscono come produttori in un mercato, scegliendo livelli di produzione per massimizzare il profitto (minimizzare il costo) rispettando vincoli basati sul prezzo.

• Consenso: I risultati della simulazione (Figura 1) dimostrano che i moltiplicatori di Lagrange stimati localmente per diversi agenti convergono a un valore di consenso.
• Prestazioni: Le curve di addestramento (Figura 2) mostrano che l'algoritmo minimizza con successo il costo dell'obiettivo globale mantenendo le violazioni dei vincoli globali vicine allo zero.

Significato e Affermazioni
L'articolo afferma di colmare una lacuna nella letteratura, dove pochi metodi gestiscono problemi CMARL generali con costi locali accoppiati e vincoli globali in modo completamente decentralizzato. Mentre i lavori esistenti spesso si affidano all'addestramento centralizzato, alla condivisione dei parametri con agenti omogenei o alla comunicazione durante l'esecuzione, questo metodo abilita l'apprendimento online completamente decentralizzato.

Gli autori inquadrano modestamente il loro contributo come un'estensione vincolata dei metodi esistenti di actor-critic distribuiti non vincolati (riferendosi specificamente a lavori precedenti sul MARL non vincolato). Riconoscono che, a causa del gap di dualità non nullo negli ambienti cooperativi parametrizzati, l'algoritmo converge a un punto di equilibrio che può essere sub-ottimale rispetto alla soluzione esatta del problema non parametrizzato. Tuttavia, il metodo proposto fornisce una soluzione scalabile e decentralizzata che garantisce il rispetto dei vincoli in scenari complessi e reali, come le reti elettriche intelligenti e i sistemi autonomi, senza i colli di bottiglia di scalabilità degli approcci centralizzati.