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

1. Il Problema

Il campo dell'Apprendimento per Rinforzo Multi-Agente (MARL) affronta la sfida di coordinare grandi popolazioni di agenti interagenti. Il problema principale è la maledizione della dimensionalità: lo spazio congiunto di stati e azioni cresce esponenzialmente con il numero di agenti $n$, rendendo il campionamento esaustivo e il calcolo delle politiche ottimali computazionalmente intrattabili.

Le soluzioni esistenti si dividono in due categorie con limiti specifici:

• Metodi a Campo Medio (Mean-Field): Semplificano le interazioni aggregando gli stati degli agenti in una distribuzione empirica. Tuttavia, assumono che le interazioni siano omogenee (tutti gli agenti interagiscono allo stesso modo), il che è irrealistico in sistemi complessi come il traffico o i robot in magazzino dove la prossimità e la topologia creano eterogeneità.
• Metodi basati su Graphon: I graphon permettono di modellare interazioni eterogenee e non uniformi in reti dense, definendo la forza dell'interazione tra agenti tramite una funzione limite $W(x, y)$. Tuttavia, i metodi attuali basati su graphon richiedono l'aggregazione dell'intera popolazione ad ogni passo temporale, mantenendo un costo computazionale elevato che scala male con $n$.

L'obiettivo del paper è colmare questo divario: sviluppare un algoritmo scalabile per MARL cooperativo che gestisca l'eterogeneità delle interazioni (tramite graphon) riducendo al contempo la complessità computazionale a una dipendenza polilogaritmica o polinomiale rispetto al numero di agenti.

2. Metodologia: GMFS (Graphon Mean-Field Subsampling)

Gli autori propongono GMFS, un framework che combina la teoria dei graphon con una tecnica di sottocampionamento (subsampling) intelligente.

Concetti Chiave:

1. Modellazione Eterogenea con Graphon:

   • Gli agenti sono mappati su coordinate latenti $\alpha_i \in [0, 1]$.
   • Un graphon $W(\alpha_i, \alpha_j)$ definisce il peso dell'interazione tra l'agente $i$ e l'agente $j$. Questo permette di catturare strutture di interazione non uniformi (es. agenti vicini interagiscono di più di quelli lontani).
   • L'agente $i$ osserva una "feature di vicinato" pesata dal graphon, che è una distribuzione empirica degli stati e azioni dei vicini.

2. Sottocampionamento Pesato (Weighted Subsampling):

   • Invece di osservare tutti gli $n-1$ altri agenti, ogni agente $i$ campiona un sottoinsieme di $\kappa$ vicini (dove $\kappa \ll n$).
   • Il campionamento non è uniforme, ma segue una distribuzione di probabilità proporzionale ai pesi normalizzati del graphon $\bar{w}_{ij}$. Questo garantisce che gli agenti più influenti (con pesi più alti) abbiano una probabilità maggiore di essere inclusi nel campione, riducendo la varianza dell'aggregato stimato.

3. Apprendimento Centralizzato ed Esecuzione Decentralizzata (CTDE):

   • Fase di Apprendimento (Offline): Viene utilizzato un oracolo generativo per apprendere una funzione Q ottimale su un modello surrogato di $(\kappa + 1)$ agenti. La funzione Q viene appresa sullo spazio degli stati di vicinato campionati ($\hat{g}^{(\kappa)}$).
   • Fase di Esecuzione (Online): Ogni agente esegue la politica appresa basandosi solo sulle proprie osservazioni locali e sul sottocampione $\kappa$ dei vicini, calcolato dinamicamente in base ai pesi del graphon. Non è necessaria la conoscenza globale dello stato di tutti gli agenti.

4. Operatori di Bellman:

   • Viene definito un operatore di Bellman campionato $\hat{T}_\kappa$ che agisce sulle funzioni Q definite sugli aggregati campionati.
   • Viene dimostrato che questo operatore è una contrazione $\gamma$, garantendo l'esistenza e l'unicità di un punto fisso (la funzione Q ottima per il modello surrogato).

3. Contributi Chiave

1. Algoritmo GMFS: Introduzione di un framework di sottocampionamento per MARL cooperativo eterogeneo, dove le interazioni sono approssimate usando $\kappa$ vicini campionati secondo i pesi del graphon.
2. Garanzie Teoriche:
   • Complessità Campionaria: Si dimostra che la complessità campionaria scende da esponenziale in $n$ (tipica del MARL) a polinomiale in $\kappa$, ovvero $\tilde{O}(\kappa |S| |A|)$.
   • Gap di Ottimalità: Viene stabilito un limite superiore per il gap tra la politica appresa e quella ottima. Il gap decresce a un tasso di $\tilde{O}(1/\sqrt{\kappa})$.
   • Stabilità: Viene provato che l'operatore di Bellman campionato rimane una contrazione, assicurando la convergenza dell'algoritmo.
3. Generalizzazione: Il framework è esteso a spazi di stati continui (tramite approssimazione lineare e numeri di copertura) e a scenari con ricompense stocastiche e apprendimento off-policy.
4. Validazione Numerica: Simulazioni in ambienti di coordinamento robotico (magazzini) e traffico dimostrano che le prestazioni migliorano monotonicamente all'aumentare di $\kappa$, avvicinandosi al limite del campo medio esaustivo con un costo computazionale drasticamente ridotto.

4. Risultati Principali

• Efficienza Computazionale: Rispetto ai metodi di campo medio tradizionali che richiedono $O(n)$, GMFS riduce il costo per agente a $O(\kappa)$. Se $\kappa = O(\log n)$, la complessità diventa polilogaritmica rispetto alla dimensione della popolazione, offrendo un'accelerazione esponenziale.
• Performance: Nelle simulazioni con robot in magazzino, GMFS raggiunge prestazioni quasi ottimali già con un sottocampione piccolo (es. $\kappa = 8$ su 25 agenti), avvicinandosi al limite teorico del campo medio completo ($\kappa = n-1$).
• Robustezza all'Eterogeneità: A differenza dei metodi di campo medio standard che falliscono in presenza di interazioni non uniformi, GMFS mantiene l'efficacia grazie al campionamento pesato che preserva le statistiche dominanti del vicinato.

5. Significato e Impatto

Questo lavoro è significativo perché risolve un problema fondamentale nel MARL scalabile: come gestire l'eterogeneità senza sacrificare la scalabilità.

• Teorico: Unifica la teoria dei graphon (per l'eterogeneità) con le tecniche di sottocampionamento (per l'efficienza), fornendo i primi limiti teorici rigorosi per il MARL cooperativo su graphon con sottocampionamento.
• Pratico: Abilita l'applicazione del MARL a sistemi reali su larga scala come:
  • Sciami di Robot: Dove la congestione è locale e dipende dalla posizione.
  • Veicoli Autonomi: Dove il traffico è influenzato dalla densità locale e non dalla media globale.
  • Reti Energetiche (Smart Grid): Dove le interazioni sono limitate da vincoli topologici e di trasmissione.

In sintesi, GMFS offre un percorso praticabile per implementare politiche di controllo cooperative ottimali in sistemi complessi e eterogenei, superando le barriere computazionali che hanno finora limitato l'adozione del MARL su larga scala.