Riassunto Tecnico: Apprendimento per Rinforzo Multi-Agente Cooperativo Condizionato da Automi (ACC-MARL)

1. Definizione del Problema

Il documento affronta la sfida di apprendere politiche multi-task e multi-agente per squadre cooperative che operano sotto un paradigma di addestramento centralizzato e decurtazione decentralizzata (CTDE). Il contesto specifico prevede che agli agenti vengano assegnati compiti temporali a priori sconosciuti durante l'esecuzione, che devono completare senza comunicazione esplicita.

La difficoltà principale risiede nel generalizzare a questi compiti dinamici pur soddisfacendo obiettivi complessi a lungo termine. Gli approcci esistenti che utilizzano specifiche formali (come gli Automi a Stati Finiti Deterministici, DFA) per rappresentare i compiti sono spesso poco efficienti in termini di campionamento e limitati a scenari a singolo compito, richiedendo un nuovo addestramento per nuovi obiettivi. Inoltre, in un contesto multi-agente, tre sfide primarie ne ostacolano la fattibilità:

1. Dipendenza dalla Storia: Le politiche devono tracciare il progresso del compito (storia) per prendere decisioni, rompendo la proprietà di Markov e portando a politiche subottimali.
2. Assegnazione del Credito: La ricompensa a livello di squadra è sparsa (viene assegnata solo al completamento totale del compito), rendendo difficile per gli agenti discernere come le singole azioni contribuiscano all'obiettivo globale.
3. Collo di Bottiglia della Rappresentazione: L'apprendimento simultaneo delle rappresentazioni latenti dei DFA e delle politiche di controllo crea un problema di scalabilità, particolarmente per squadre con più di due agenti.

2. Metodologia: Framework ACC-MARL

Gli autori propongono l'Apprendimento per Rinforzo Multi-Agente Cooperativo Condizionato da Automi (ACC-MARL), un framework che condiziona le politiche decentralizzate su rappresentazioni dei compiti derivate da DFA. L'approccio affronta le tre sfide attraverso i seguenti meccanismi:

A. Mitigazione della Dipendenza dalla Storia tramite Riformulazione Markoviana

Invece di condizionare le politiche sulla storia grezza delle osservazioni, il framework aumenta lo spazio degli stati con lo stato minimo corrente del DFA per ogni agente.

• Meccanismo: Ad ogni passo, lo stato dell'ambiente viene etichettato e i DFA assegnati progrediscono (si aggiornano) in base a queste etichette. Le osservazioni degli agenti sono aumentate con le ultime rappresentazioni minimali dei DFA.
• Risultato: Questo trasforma il gioco non-Markoviano in un gioco Markoviano sullo spazio prodotto degli stati dell'ambiente e degli stati dei DFA ($S \times D^n$). Gli autori dimostrano (Teorema 3.1) che massimizzare il ritorno in questo gioco riformulato è equivalente a massimizzare la probabilità di soddisfare gli obiettivi temporali originali quando il fattore di sconto $\gamma \to 1$.

B. Risoluzione dell'Assegnazione del Credito tramite Reward Shaping Basato sul Potenziale (PBRS)

Per superare la scarsità delle ricompense, gli autori applicano il Potential-Based Reward Shaping.

• Meccanismo: Una funzione di potenziale $\Phi_i$ è definita per ogni agente $i$, restituendo 1 se il suo DFA assegnato è soddisfatto e 0 altrimenti. La ricompensa è modellata dalla differenza di potenziale tra lo stato attuale e quello successivo: $R_{PBRS} = R_{base} + \gamma \Phi_i(next) - \Phi_i(current)$.
• Risultato: Gli agenti ricevono un feedback positivo denso per il completamento dei loro specifici sottotemi, mantenendo al contempo la garanzia teorica che la politica ottimale per la ricompensa modellata rimanga ottimale per l'obiettivo originale.

C. Risoluzione del Collo di Bottiglia della Rappresentazione con Embedding RAD

Per evitare di apprendere le rappresentazioni latenti dei DFA da zero durante l'addestramento (il che causa una degradazione delle prestazioni in squadre più grandi), il framework utilizza Embedding RAD (ReachAvoidDerived) pre-addestrati.

• Meccanismo: Un encoder Graph Attention Network (GATv2) congelato mappa i DFA in vettori latenti (Embedding RAD). Questi embedding sono addestrati per rappresentare in modo unico distinti DFA minimizzati e codificare somiglianze semantiche attraverso una vasta classe di compiti temporali.
• Risultato: Le politiche si condizionano su questi embedding fissi piuttosto che su DFA grezzi o rappresentazioni apprese. Ciò scinde l'apprendimento della rappresentazione dall'apprendimento del controllo, consentendo di scalare efficientemente a squadre più grandi (es. 4 agenti).

D. Assegnazione Ottimale dei Compiti

Il framework sfrutta le funzioni di valore apprese per assegnare i compiti in modo ottimale al momento del test. Valutando l'aspettativa delle prestazioni della squadra (somma delle funzioni di valore) per diverse permutazioni di assegnazione dei compiti, il sistema può selezionare un'assegnazione Pareto-ottimale che massimizza il successo complessivo della squadra, particolarmente in ambienti asimmetrici.

3. Contributi Chiave

1. Introduzione del Framework: La proposta di ACC-MARL, un framework per l'apprendimento di politiche multi-task, multi-agente ed ego-centriche condizionate da DFA.
2. Garanzie Teoriche: Dimostrazione che la proposta riformulazione Markoviana e il reward shaping preservano l'ottimalità rispetto al problema non-Markoviano originale.
3. Soluzione alla Scalabilità: Dimostrazione che l'uso di Embedding RAD pre-addestrati supera il collo di bottiglia della rappresentazione, permettendo l'apprendimento efficace in squadre con più di due agenti.
4. Assegnazione dei Compiti: Un metodo per utilizzare le funzioni di valore apprese per calcolare l'assegnazione ottimale dei compiti durante il test.
5. Toolchain: Implementazione di una toolchain basata su JAX (DFAx) per operazioni sui DFA parallelizzate e un pacchetto Python per integrare i compiti di automi nelle applicazioni di RL.

4. Risultati Sperimentali

Il framework è stato valutato in un ambiente discreto e completamente osservabile chiamato TokenEnv, caratterizzato da varianti a due e quattro agenti con layout che includono pulsanti, porte e token.

• Fattibilità e Scalabilità (Q1 & Q2):
  • Gli studi di ablazione mostrano che senza le soluzioni proposte (specificamente PBRS e Embedding RAD), le politiche falliscono la convergenza o raggiungono bassi tassi di successo (<0.5).
  • Negli ambienti a 2 agenti, sia gli encoder pre-addestrati che quelli non addestrati si comportano in modo simile, sebbene gli embedding pre-addestrati offrano una varianza inferiore.
  • Negli ambienti a 4 agenti, le politiche che utilizzano Embedding RAD pre-addestrati superano significativamente quelle che apprendono le rappresentazioni da zero, confermando che il pre-addestramento è cruciale per la scalabilità.
• Generalizzazione (Q3):
  • Le politiche addestrate su RAD DFA generalizzano a classi di compiti non viste (Reach e ReachAvoid) e a DFA out-of-distribution (OOD) con più stati di quelli visti durante l'addestramento.
  • Gli embedding pre-addestrati migliorano specificamente le prestazioni su compiti che coinvolgono vincoli di "Evitamento" (condizioni irrecuperabili).
• Assegnazione dei Compiti (Q4):
  • In ambienti simmetrici (Buttons), l'ordine di assegnazione dei compiti ha avuto un impatto trascurabile.
  • In ambienti asimmetrici (Rooms), l'assegnazione ottimale dei compiti derivata dalle funzioni di valore apprese ha migliorato significativamente le probabilità di successo della squadra rispetto all'assegnazione casuale.
• Comportamenti Emergenti (Q5):
  • L'analisi qualitativa rivela abilità cooperative emergenti, come agenti che tengono aperte le porte per i compagni per risparmiare tempo e il "taglio corto" dei compiti (es. un agente che sblocca una porta per permettere a un altro di prendere una strada più breve).

5. Significato e Rivendicazioni

Il documento sostiene di essere il primo lavoro a utilizzare specifiche formali (DFA) in un contesto di multi-task cooperative MARL dove i compiti vengono assegnati al momento dell'esecuzione. La sua importanza risiede nel:

• Unire Metodi Formali e MARL: Estende l'apprendimento condizionato da automi dal singolo agente al multi-agente, permettendo la decomposizione di obiettivi di squadra complessi in sottotemi.
• Risolvere la Sfida della Scalabilità: Decoupling (scollegando) l'apprendimento della rappresentazione tramite embedding pre-addestrati, affronta i colli di bottiglia delle prestazioni che precedentemente limitavano l'automata-conditioned MARL a piccole squadre.
• Ottimalità: Fornisce un approccio teoricamente fondato che garantisce un comportamento ottimale della squadra pur consentendo un'efficiente assegnazione del credito e la generalizzazione.

Gli autori segnalano limitazioni, tra cui l'assunzione di funzioni di etichettatura fisse, l'osservabilità completa e il costo computazionale dell'enumerazione degli assegnamenti dei compiti per squadre molto grandi. Suggeriscono come lavoro futuro l'osservabilità parziale, l'etichettatura dinamica e i domini continui.