Sintesi Tecnica: ACPO: Agent-Chained Policy Optimization per il Multi-Agent Reinforcement Learning

Definizione del Problema

Il Cooperative Multi-Agent Reinforcement Learning (MARL) mira a trovare politiche decentralizzate che massimizzino congiuntamente un ritorno condiviso. Sotto il paradigma Centralized Training with Decentralized Execution (CTDE), una sfida fondamentale rimane: calcolare direttamente il gradiente della politica congiunta è difficile. Gli approcci esistenti ricadono generalmente in due categorie, entrambe con significativi limiti:

1. Independent Policy Optimization (es. MAPPO, MADDPG): Gli agenti aggiornano le proprie politiche indipendentemente utilizzando critici centralizzati. Sebbene scalabili, questi metodi mancano di garanzie generali di miglioramento della politica congiunta perché non tengono conto della non-stazionarietà introdotta dalle politiche mutabili degli altri agenti. La convergenza è garantita solo sotto forti assunzioni strutturali, come la decomposizione del valore.
2. Alternating Best-Response Optimization (es. HAPPO, HATRPO): Gli agenti si aggiornano sequenzialmente, trattando le politiche degli altri come fisse. Sebbene ciò garantisca il miglioramento monotono del ritorno congiunto ad ogni step, il punto fisso è un Equilibrio di Nash (NE). In contesti cooperativi, un NE può essere arbitrariamente subottimale rispetto al vero ottimo sociale, e gli agenti non hanno meccanismi per uscire da questi equilibri subottimali.

Il paper sostiene che nessuno dei due approcci punta efficacemente alla politica congeturale ottimale del Multi-Agent MDP (MMDP) sottostante senza assunzioni restrittive o convergenza verso equilibri subottimali.

Metodologia: Agent-Chained Policy Optimization (ACPO)

Il contributo principale del paper è la derivazione di una decomposizione decentralizzata esatta del gradiente della politica congiunta. Ciò viene ottenuto introducendo un nuovo formalismo, l'Agent-Chained Belief MDP (AC-BMDP), che trasforma il problema decisionale simultaneo congiunto in un processo decisionale serializzato con informazione imperfetta.

1. L'Agent-Chained Belief MDP (AC-BMDP)

Ispirandosi ai risultati della teoria dei giochi che affermano che i giochi simultanei possono essere ricanalizzati come processi serializzati con informazione imperfetta, gli autori decompongono ogni step temporale dell'ambiente $t$ in $N$ micro-step, uno per ogni agente $i \in \{1, \dots, N\}$.

• Serializzazione: Gli agenti si impegnano nelle azioni sequenzialmente all'interno di un singolo step temporale. L'agente $i$ agisce dopo gli agenti $1$ attraverso $i-1$.
• Augmentazione dello Stato: Lo stato per l'agente $i$ è aumentato da una credenza (belief) $b^{(i)}_t$ sulle azioni realizzate dagli agenti precedenti ($\vec{a}^{<i}_t$).
• Esecuzione Decentralizzata: Poiché le azioni realizzate dagli agenti precedenti non sono osservate durante l'esecuzione, la credenza è costruita dalle distribuzioni delle azioni ($\phi^{(j)}_t$) degli agenti precedenti. Queste distribuzioni sono funzioni deterministiche dello stato condiviso e delle politiche degli agenti, rendendole accessibili senza comunicazione.
• Chained Bellman Operators: La funzione valore per l'agente $i$, $Q^{(i)}$, è definita ricorsivamente. Il valore dell'agente $i$ dipende dal valore dell'agente $i+1$ (il successivo agente nella catena). Solo l'ultimo agente ($N$) riceve la ricompensa dall'ambiente e effettua il bootstrapping al valore del primo agente al passo temporale successivo. Questa "concatenazione" (chaining) permette l'attribuzione del credito senza assumere una funzione di valore congiunta decomponibile.

2. Fondamenti Teorici

Il paper stabilisce due teoremi chiave:

• Teorema del Gradiente della Politica Agent-Chained: Il gradiente della politica per l'AC-BMDP può essere calcolato utilizzando una funzione di score standard e un critico decentralizzato $Q^{(i)}$ che condiziona solo sullo stato dell'agente e sulla credenza rispetto alle azioni precedenti.
• Teorema di Decomposizione del Gradiente della Politica Multi-Agente: Si dimostra che il gradiente della politica congiunta del MMDP originale è esattamente equivalente a una somma di $N$ termini indipendenti per agente derivati dall'AC-BMDP.
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  Fondamentalmente, questa decomposizione non richiede assunzioni strutturali sulla funzione di valore congiunta (a differenza di VDN o QMIX) ed evita i punti fissi subottimali degli aggiornamenti alternati.

3. Istantiazioni Algoritmiche

Gli autori istanziano ACPO in due forme pratiche:

• ACPPO (On-Policy): Un algoritmo basato su PPO in cui ogni agente ottimizza un obiettivo surrogato con clipping utilizzando le stime di vantaggio concatenate. L'vantaggio è calcolato tramite una Generalized Advantage Estimation (GAE) che somma i residui TD (Temporal Difference) concatenati attraverso la catena degli agenti.
• ACTD3 (Off-Policy): Un algoritmo basato su TD3 per il controllo continuo, dove gli agenti mantengono twin critic seguendo la struttura Bellman concatenata.

Approssimazione della Credenza (Belief Approximation):

• Nei contesti completamente osservabili (MMDP), gli agenti calcolano le credenze esattamente interrogando le reti delle politiche degli agenti precedenti.
• Nei contesti parzialmente osservabili (Dec-POMDP), gli agenti impiegano una Action Belief Network per predire le distribuzioni delle azioni degli agenti precedenti basandosi sulla propria storia locale, addestrata tramite una perdita di divergenza KL contro il target centralizzato.

Contributi Chiave

1. Formalizzazione di AC-BMDP: L'introduzione di un framework formale che combina la serializzazione con l'augmentazione della credenza, consentendo l'apprendimento della politica congiunta ottimale sotto CTDE senza assunzioni di decomposizione del valore.
2. Decomposizione Esatta del Gradiente: La prova che il gradiente della politica congiunta ammette una decomposizione esatta in termini per singolo agente, permettendo aggiornamenti indipendenti che costituiscono collettivamente un singolo step di gradiente sull'obiettivo congiunto.
3. Convergenza alla Politica Congiunta Ottimale: A differenza dei metodi alternati che convergono a un Equilibrio di Nash, il paper dimostra che in contesti tabulari, l'Agent-Chained Policy Iteration (ACPI) converge alla politica congiunta ottimale del MMDP sottostante.
4. Algoritmi Scalabili: Lo sviluppo di ACPPO e ACTD3, che dimostrano come l'agent-chaining possa essere applicato sia ad algoritmi di RL deep on-policy che off-policy.

Risultati Sperimentali

Gli autori hanno valutato ACPO su tre benchmark standard: Multi-Robot Warehouse (RWARE), SMACv2 e MA-MuJoCo.

• Performance: ACPO (specificamente ACPPO) ha superato costantemente i baselines forti, inclusi MAPPO (ottimizzazione indipendente), HAPPO/HATRPO (ottimizzazione alternata) e i metodi di decomposizione del valore (VDN, QMIX).
• Scalabilità con il numero di Agenti: Un risultato critico è che il divario di performance tra ACPO e i baselines si amplia all'aumentare del numero di agenti. In RWARE, il vantaggio è stato più pronunciato negli scenari con 8 e 12 agenti, suggerendo che ACPO è particolarmente efficace in ambienti ad alta coordinazione e densamente popolati.
• Performance Off-Policy: La variante off-policy, ACTD3, ha inoltre superato i baselines (MADDPG, HATD3) in MA-MuJoCo, dimostrando la generalità del meccanismo di agent-chaining.
• Studi di Ablazione: Rimuovendo il meccanismo di agent-chaining (riducendo ACPPO a MAPPO con input di credenza), le performance risultavano simili a quelle di MAPPO, confermando che i guadagni derivano dal calcolo del vantaggio concatenato e non solo dall'aggiunta di stati di credenza.
• Efficienza: Sebbene ACPO richieda il calcolo sequenziale delle credenze, il tempo di addestramento (wall-clock time) rimane comparabile a MAPPO ed è sostanzialmente più veloce dei metodi alternati (HAPPO/HATRPO), che richiedono aggiornamenti sequenziali degli agenti durante l'addestramento.

Significato e Rivendicazioni

Il paper sostiene che ACPO fornisca una soluzione fondata al problema del MARL cooperativo sotto CTDE. La sua importanza risiede nel:

• Colmare il Divario: Unifica i benefici degli aggiornamenti indipendenti (scalabilità) e degli aggiornamenti alternati (garanzie di miglioramento monotono) evitando i rispettivi problemi (non-stazionarietà e equilibri di Nash subottimali).
• Rigore Teorico: Offre la prima decomposizione esatta del gradiente della politica congiunta che non si basa su assunzioni di decomposizione del valore, garantendo teoricamente la convergenza all'ottimo sociale in contesti tabulari.
• Efficacia Pratica: I risultati empirici suggeriscono che la coordinazione esplicita tramite il chaining delle credenze sia un meccanismo superiore per gestire compiti di coordinazione multi-agente complessi rispetto ai metodi allo stato dell'arte attuali, specialmente con l'aumentare della complessità della popolazione di agenti.

Gli autori notano con modestia i limiti, specificamente che il calcolo della credenza scala linearmente con il numero di agenti (portando a $O(N^2)$ passaggi forward) e che le attuali garanzie teoriche si basano sulla piena osservabilità (MMDP), lasciando l'estensione ai generi Dec-POMDP come lavoro futuro.