Expected Return Symmetries

Sintesi Tecnica: Simmetrie del Ritorno Atteso

Definizione del Problema
Nel apprendimento per rinforzo multi-agente cooperativo (MARL), una sfida fondamentale è la Coordinazione Zero-Shot (ZSC): la capacità di agenti addestrati indipendentemente di coordinarsi efficacemente con nuovi partner al tempo di test senza comunicazione preventiva. Un principale modo di fallimento nella ZSC è la rottura di simmetria mutuamente incompatibile. Quando gli agenti si addestrano in isolamento, possono convergere su politiche equivalenti ma incompatibili (ad esempio, un team concorda di segnalare "gioca" con il colore blu, mentre un altro usa il rosso).

Le soluzioni esistenti, come l'obiettivo Other-Play (OP), affrontano questo problema imponendo la compatibilità tra politiche equivalenti sotto le simmetrie Dec-POMDP (riclassificazioni di stati, azioni e osservazioni che lasciano invarianti le funzioni di transizione e di ricompensa). Tuttavia, questo approccio presenta due limitazioni:

1. Modalità di Fallimento della Coordinazione: La rottura della simmetria ambientale è solo un tipo di fallimento della coordinazione. Gli agenti possono comunque sovra-coordinarsi formando convenzioni eccessivamente specifiche anche in assenza di simmetrie Dec-POMDP non banali.
2. Accessibilità delle Simmetrie: I metodi attuali richiedono la conoscenza a priori delle simmetrie dell'ambiente. Scoprire automaticamente queste simmetrie in Dec-POMDP su larga scala è spesso computazionalmente impraticabile, e molti metodi si basano su informazioni privilegiate (ad esempio, dinamiche di verità fondamentale o gruppi di simmetria) che non sono disponibili in contesti del mondo reale.

Metodologia
Il documento introduce le Simmetrie del Ritorno Atteso (ER Symmetries), una classe più ampia di simmetrie che contiene le simmetrie Dec-POMDP come un sottogruppo.

• Definizione: Una trasformazione $\phi$ è una simmetria ER se preserva l'insieme delle politiche ottimali di esplorazione di Boltzmann self-play ($\Pi^*_\alpha$). Nello specifico, $\Phi_{ER} = \{ \phi \in \Psi \mid \forall \pi \in \Pi^*_\alpha: \phi(\pi) \in \Pi^*_\alpha \}$. A differenza delle simmetrie Dec-POMDP, che richiedono l'invarianza delle funzioni di transizione e di ricompensa, le simmetrie ER richiedono solo che la trasformazione mappi le politiche ottimali in altre politiche ottime (preservando il ritorno atteso).
• Proprietà Teoriche: Gli autori dimostrano che $\Phi_{ER}$ forma un gruppo sotto composizione di funzioni. Fondamentalmente, $\Phi_{ER}$ è un sovrainsieme stretto delle simmetrie Dec-POMDP in molti casi, catturando differenze di coordinazione basate sulla strategia piuttosto che sulla semplice permutazione di etichette.
• Algoritmo di Apprendimento: Poiché $\Phi_{ER}$ non è nota a priori, il documento propone metodi scalabili per apprendere approssimazioni delle simmetrie ER tramite ottimizzazione basata sul gradiente senza accesso alle simmetrie di verità fondamentale o alle dinamiche dell'ambiente.
  • Obiettivo 1 (Preservazione del Ritorno): Massimizzare il ritorno atteso delle politiche trasformate: $\max_\theta \mathbb{E}_{\pi \sim \Pi'} [J(\phi_\theta(\pi))]$, dove $\Pi'$ è un pool di politiche ottime di self-play.
  • Obiettivo 2 (Componibilità e Invertibilità): Viene introdotto un obiettivo regolarizzato per garantire che le trasformazioni apprese formino un gruppo (imponendo chiusura e invertibilità) penalizzando le deviazioni dall'identità dopo una doppia applicazione e massimizzando i ritorni sotto trasformazioni composte.
  • Obiettivo 3 (Massimizzazione del Cross-Play): Un approccio alternativo ottimizza direttamente le prestazioni di cross-play tra coppie di politiche.
  • Il metodo assume una struttura minima: fissa la trasformazione dello stato all'identità e apprende le trasformazioni di osservazione e azione (spesso tramite ricerca su permutazioni di azioni e reti neurali per le osservazioni).

Contributi Chiave

1. Definizione di Simmetrie ER: Il documento definisce un nuovo gruppo di simmetria basato sulla preservazione dei ritorni attesi per le politiche ottime, che assorbe le tradizionali simmetrie Dec-POMDP.
2. Scoperta Model-Free: Gli autori introducono algoritmi per apprendere queste simmetrie puramente attraverso l'interazione agente-ambiente, senza richiedere informazioni privilegiate sulla struttura o sulle dinamiche dell'ambiente.
3. Miglioramento delle Prestazioni ZSC: Il documento dimostra che combinare la regola di apprendimento OP con le simmetrie ER apprese supera significativamente il self-play standard e l'OP con simmetrie Dec-POMDP nel prevenire la sovra-coordinazione.
4. Robustezza in Ambienti Sfidanti: Il metodo si dimostra efficace in ambienti in cui i metodi allo stato dell'arte come l'Off-Belief Learning (OBL) e le Gerarchie Cognitive falliscono (ad esempio, specifici giochi a tre leve e Overcooked V2).

Risultati Sperimentali
Gli autori valutano il loro metodo attraverso quattro ambienti:

• Iterated Three-Lever Game: In questo setting, le simmetrie ER coincidono con le simmetrie Dec-POMDP, e il metodo recupera con successo la politica ottimale ZSC.
• Toy Coordination Game: Il metodo recupera con successo una simmetria ER non banale (uno scambio di azioni) che non è una simmetria Dec-POMDP, dimostrando la capacità di scoprire simmetrie al di fuori del gruppo tradizionale.
• Overcooked V2: In questo benchmark asimmetrico e stocastico, gli agenti che utilizzano le simmetrie ER apprese hanno ottenuto un punteggio medio di cross-play (XP) di 15.8, superando significativamente il baseline di self-play (6.74) e riducendo la varianza nei risultati di coordinazione.
• Hanabi: In questo complesso gioco di carte, gli agenti utilizzando 11 simmetrie ER apprese hanno ottenuto un punteggio medio XP di 21.64, superando sia il baseline IPPO (4.02) che il baseline IPPO vincolato da tutte le 120 simmetrie Dec-POMDP note (8.61). I risultati indicano che le simmetrie ER preservano meglio l'ottimalità pur imponendo la compatibilità.

Significatività e Rivendicazioni
Il documento sostiene che le Simmetrie del Ritorno Atteso rappresentino un avanzamento significativo nella ZSC poiché:

• Generalizzano la Simmetria: Si spostano dalle rigide invarianze ambientali a una definizione di simmetria più flessibile e centrata sulla politica, che affronta meglio la diversità delle strategie ottime.
• Rimuovono le Informazioni Privilegiate: Sono i primi a introdurre un metodo basato sulla simmetria che migliora la ZSC senza richiedere la conoscenza a priori di simmetrie o dinamiche, rendendolo applicabile a contesti in cui tali informazioni non sono disponibili.
• Risolvono i Fallimenti della Coordinazione: Forniscono una soluzione alla sovra-coordinazione che è efficace anche in ambienti in cui i precedenti metodi basati sulla simmetria o sulla diversità (come l'OBL) falliscono.

Gli autori riconoscono i limiti, notando che l'espressività dello spazio di ricerca (ristretto a biiezioni sugli spazi di azione/osservazione) potrebbe non essere sufficiente per tutti gli ambienti (ad esempio, la variante del gioco a due leve) e che il successo del metodo dipende dalla qualità delle politiche utilizzate per apprendere le simmetrie.