Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

Sintesi Tecnica: Verso l'apprendimento di rappresentazioni di policy in giochi a informazione imperfetta a due giocatori a somma zero

Definizione del Problema
Nei giochi a informazione imperfetta (IIG) a due giocatori a somma zero, gli agenti traggono spesso beneficio dal ragionare sulle proprie policy e su quelle degli avversari. Sebbene la ricerca con lookahead a profondità limitata sia fattibile in giochi piccoli utilizzando rappresentazioni tabulari (ad esempio, il Counterfactual Regret Minimization), questo approccio diventa intrattabile in giochi con grandi stati di credenza pubblica, dove enumerare tutte le possibili policy è impossibile. Di conseguenza, esiste la necessità di rappresentazioni compatte e utili (embedding) delle policy che permettano agli agenti di ragionare sull'intento strategico senza dover accedere alle complete tabelle delle policy. Tuttavia, la ricerca esistente sull'apprendimento di tali embedding di policy nei IIG è scarsa, mancando sia di metodi sistematici per generare dataset di policy sia di compiti downstream standardizzati per la valutazione.

Metodologia
Gli autori propongono un framework sistematico composto da tre componenti principali: generazione del dataset, apprendimento dell'embedding e valutazione downstream.

1. Generazione del Dataset: Il documento introduce tre metodi per creare dataset diversificati di policy per un dato gioco:

   • Inizializzazione Casuale: Inizializzazione casuale delle reti neurali delle policy con uno schema personalizzato per garantire la diversità comportamentale, evitando l'omogeneità delle standard inizializzazioni di PyTorch.
   • Policy Space Response Oracle (PSRO): Addestramento iterativo di best-response rispetto a miscele di policy esistenti per generare un pool in espansione di strategie diversificate.
   • Neural Population Learning (NeuPL): Addestramento di una singola rete neurale condizionale condivisa da tutti gli agenti; nuove policy vengono generate campionando dallo spazio di embedding latente della rete.

2. Apprendimento dell'Embedding: Vengono proposti diversi metodi per mappare le policy in rappresentazioni vettoriali:

   • Weight Autoencoder: Un baseline ingenuo che tenta di ricostruire il vettore dei pesi appiattito di una rete di policy da uno strato bottleneck.
   • Functional Encoder: Simile al weight autoencoder, ma minimizza la divergenza KL tra le distribuzioni delle azioni delle reti originali e ricostruite sugli stati informativi campionati, concentrandosi sulla ricostruzione comportamentale piuttosto che sulla ricostruzione dei pesi.
   • Trajectory Encoder: Un approccio di apprendimento contrastivo (ispirato a SimCLR) che mappa traiettorie di lunghezza variabile (raccolte tramite rollout di policy contro avversari casuali) in uno spazio latente a dimensione fissa. Questo metodo non richiede l'accesso agli interni della rete.
   • NeuPL-style Conditional Embeddings: Un approccio generativo in cui una rete condizionale impara a decodificare qualsiasi vettore dallo spazio latente in una policy, generando congiuntamente la popolazione e gli embedding.
   • Baseline di Grover et al.: Un modello ibrido generativo-discriminativo che utilizza un encoder MLP e una rete di policy condizionale addestrata con perdite di imitazione e identificazione di triplette.
   • Baselines: Include un Tabular Baseline (concatenazione delle distribuzioni delle azioni in tutti gli stati informativi) e un Identity Baseline (utilizzo diretto dei pesi grezzi della rete).

3. Compiti di Valutazione Downstream: L'efficacia delle rappresentazioni è valutata utilizzando cinque compiti:

   • Task A & B (Previsione del Payoff): Prevedere i payoff attesi contro un avversario casuale uniforme (Task A) o tra due specifiche policy (Task B) utilizzando un predittore lineare.
   • Task C (Previsione della Sfruttabilità): Prevedere il payoff della best-response di un avversario rispetto a una data policy.
   • Task D (Zero-Shot Best-Response): Addestrare una rete di policy condizionale per approssimare una best-response a una policy dato il suo embedding.
   • Task E (Identificazione dell'Agente): Classificare quale policy ha generato una determinata traiettoria utilizzando k-NN o probe lineari.

Risultati Sperimentali
Gli esperimenti sono stati condotti su Kuhn Poker (12 stati informativi) e Leduc Poker (936 stati informativi), con risultati preliminari su giochi più grandi (Liar's Dice, Phantom Tic-Tac-Toe).

• Previsione del Payoff (Task A & B): In Kuhn Poker, il baseline tabulare ha dominato a causa delle piccole dimensioni del gioco. Tuttavia, in Leduc Poker, gli encoder appresi (Trajectory, Grover, NeuPL) hanno superato il baseline tabulare, che soffriva di un'alta dimensionalità (2808 dimensioni). Gli encoder Grover e Trajectory hanno ottenuto i maggiori miglioramenti (fino al 32,3% di riduzione del MSE) sul Task A in Leduc. I semplici autoencoder Weight e Functional generalmente non sono riusciti a migliorare rispetto alla previsione della media.
• Sfruttabilità e Risposta Zero-Shot (Task C & D): Il metodo NeuPL ha superato significativamente i baseline nella previsione dei payoff della best-response (Task C) e nell'addestramento di responder zero-shot (Task D), particolarmente sulle popolazioni di policy generate da NeuPL. I baseline Identity e Weight si sono comportati male, spesso peggio del baseline della media.
• Identificazione dell'Agente (Task E): Il Trajectory Encoder (utilizzando un classificatore lineare) ha superato sostanzialmente il baseline di Grover, ottenendo un'accuratezza top-1 del 47,9% su Kuhn e del 57,8% su Leduc, rispetto al 25,7% e 38,9% di Grover rispettivamente.
• Visualizzazione: Le visualizzazioni t-SNE degli embedding di Kuhn Poker hanno rivelato che il Trajectory Encoder ha separato con successo le strategie aggressive e passive, mentre gli embedding del Weight Autoencoder non mostravano tale struttura.

Contributi Chiave

1. Creazione del Dataset: Introduzione di tre distinti metodi (Random, PSRO, NeuPL) per generare dataset di policy diversificati nei IIG.
2. Apprendimento della Rappresentazione: Proposta e confronto di molteplici tecniche di embedding, che spaziano dalla ingenua ricostruzione dei pesi all'apprendimento contrastivo delle traiettorie e ai modelli condizionali generativi.
3. Suite di Valutazione: Definizione di un set completo di compiti downstream (previsione del payoff, sfruttabilità, risposta zero-shot, identificazione dell'agente) per valutare rigorosamente le rappresentazioni delle policy.
4. Confronto Sistematico: Per quanto a conoscenza degli autori, questo è uno dei primi lavori che confronta sistematicamente le tecniche di apprendimento auto-supervisionato per le rappresentazioni delle policy.

Significato e Rivendicazioni
Il paper sostiene di essere un passo fondamentale verso l'apprendimento di rappresentazioni comportamentali compatte e utili nei giochi a informazione imperfetta. Sebbene i metodi siano descritti come "molto basilari", i risultati dimostrano che semantiche comportamentali utili sono presenti negli embedding appresi, in particolare quando si utilizza l'apprendimento contrastivo delle traiettorie o il condizionamento in stile NeuPL. Il lavoro evidenzia come, mentre le rappresentazioni tabulari siano sufficienti per giochi piccoli, gli embedding appresi diventino superiori all'aumentare della complessità del gioco. Gli autori pongono questo lavoro come un framework aperto (codice disponibile) per facilitare ulteriore ricerca nella rappresentazione delle policy, notando che il lavoro futuro potrebbe coinvolgere il raffinamento dei termini di perdita o l'integrazione di queste rappresentazioni con la pianificazione al tempo di decisione.