EMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Games

Sintesi Tecnica: EMAgnet

Problema

I recenti progressi nella risoluzione di giochi a informazione imperfetta a due giocatori (IIG) hanno dimostrato che i metodi di gradiente della politica regolarizzati, come il Proximal Policy Optimization (PPO), possono eguagliare o superare gli algoritmi specializzati di teoria dei giochi quando utilizzati nell'auto-gioco (self-play). Una decisione critica di progettazione in questo framework è la scelta del target di regolarizzazione. La distribuzione uniforme è emersa come un target standard, implementata tramite un bonus di entropia. Tuttavia, il target uniforme è strategicamente agnostico; regolarizza la politica equamente verso tutte le azioni, indipendentemente dalla loro validità.

In giochi con spazi strategici ampi che contengono molte strategie strettamente dominate (opzioni subottimali), il target uniforme spreca il budget di regolarizzazione su strategie irrilevanti. Questa limitazione diventa sempre più consequenziale man mano che la complessità del gioco cresce e la frazione di strategie strategicamente rilevanti diminuisce. Inoltre, gli approcci esistenti che utilizzano una regolarizzazione uniforme con annealing affrontano un dilemma: una forte regolarizzazione nelle fasi iniziali forza la politica a esplorare strategie dominate, mentre una regolarizzazione debole nelle fasi finali non fornisce una pressione sufficiente per incoraggiare il mixing strategico, portando spesso alla convergenza su strategie pure invece che su equilibri di Nash.

Metodologia

Gli autori introducono EMAgnet, un metodo che estende il concetto di target di regolarizzazione "moving magnet" (calamita mobile) dai contesti tabulari al deep reinforcement learning. Invece di regolarizzare verso una distribuzione uniforme fissa, EMAgnet regolarizza verso una media mobile esponenziale (EMA) dei parametri della rete della politica stessa.

Meccanismo Core

Il metodo si basa su PPO in auto-gioco simmetrico. L'obiettivo standard di PPO è aumentato da un termine di divergenza di Kullback-Leibler (KL) che attira i parametri della politica corrente ($\theta$) verso una politica "calamita" ($\theta_{mag}$):

$$L_{PPO-EMAg}(\theta) = L_{PPO}(\theta) + \lambda_{KL} \mathbb{E}_{z \sim \mathcal{T}} \left[ D_{KL}(\pi_{\theta_{mag}}(\cdot | z) \parallel \pi_{\theta}(\cdot | z)) \right]$$

I parametri della calamita vengono aggiornati dopo ogni step di PPO utilizzando una media aritmetica nello spazio dei parametri:
$$\theta_{mag} \leftarrow (1 - \tau) \theta_{mag} + \tau \theta$$
dove $\tau \in (0, 1]$ è il passo (step size). La calamita è inizializzata con gli stessi pesi casuali della politica.

Proprietà Adattive

L'innovazione chiave è la natura adattiva del target:

1. Dimenticare le Strategie Cattive: Man mano che la politica impara a evitare le strategie strettamente dominate, la calamita EMA smette gradualmente di regolarizzare verso di esse perché i pesi della politica non supportano più quelle azioni.
2. Ricordare le Buone Strategie: L'EMA accumula naturalmente un mix smussato delle strategie incontrate durante i cicli di auto-gioco. Ciò incoraggia la politica a mantenere la copertura sulle opzioni strategicamente rilevanti.
3. Forza Costante: A differenza della regolarizzazione uniforme con annealing, la forza della regolarizzazione KL ($\lambda_{KL}$) rimane costante, ma il target evolve. Questo evita il "dilemma" per cui una forte regolarizzazione forza l'esplorazione di strategie cattive o una debole regolarizzazione non riesce a prevenire il collasso verso strategie pure.

Contributi Chiave

1. Estensione Algoritmica: Il paper estende il concetto tabulare di moving magnet (precedentemente esplorato da Sokota et al.) al deep RL, implementando un'EMA dello spazio dei parametri dei pesi della politica come target di regolarizzazione.
2. Regolarizzazione Adattiva: Il metodo fornisce un target di regolarizzazione adattivo che evolve con la strategia migliorata dell'agente, distinguendosi dai target fissi come la distribuzione uniforme.
3. Valutazione Empirica: Gli autori valutano PPO-EMAg rispetto a PPO self-play con regolarizzazione a calamita uniforme (utilizzando sia programmi di annealing lineari che a legge di potenza) attraverso tre categorie di giochi:
   • Benchmark standard (Biased RPS, Goofspiel-4, Kuhn Poker).
   • Benchmark modificati con un'unica azione di rinuncia ("forfeit") strettamente dominante (varianti FF).
   • Benchmark modificati dove la stragrande maggioranza dello spazio strategico è dominata tramite task di navigazione in gridworld (varianti Control).

Risultati

La valutazione dimostra che PPO-EMAg raggiunge una sfruttabilità (exploitability) inferiore rispetto ai baseline uniformi in ambienti contenenti strategie strettamente dominate, rimanendo al contempo competitivo nei benchmark standard.

• Giochi Standard: In Biased RPS, Goofspiel-4 e Kuhn Poker, PPO-EMAg è competitivo con i baseline, con la politica della calamita EMA che spesso raggiunge la sfruttabilità finale più bassa.
• Giochi Forfeit (FF): Nei giochi aumentati con un'azione di rinuncia strettamente dominante, PPO-EMAg supera significativamente i baseline uniformi. La calamita uniforme continua a regolarizzare verso l'azione di rinuncia durante tutto l'addestramento, mentre la calamita EMA si adatta per ridurre la regolarizzazione verso di essa man mano che la politica impara a evitarla.
• Giochi di Controllo: Negli ambienti in cui la maggior parte delle strategie è strettamente dominante (a causa di fallimenti nella navigazione), PPO-Emag mostra prestazioni superiori e una convergenza significativamente più veloce.
  • In Control Biased RPS, l'annealing lineare uniforme fallisce nell'apprendimento per circa 7 milioni di step prima di scendere tardi nell'addestramento, mentre PPO-EMAg converge entro 2 milioni di step.
  • In Control Goofspiel, l'annealing lineare uniforme migliora appena dopo 6 milioni di step, mentre PPO-EMAg raggiunge una bassa sfruttabilità molto prima.
• Analisi delle Traiettorie: Le visualizzazioni delle traiettorie della politica nel simplesso strategico rivelano che l'annealing uniforme causa alle politiche di bloccarsi su strategie dominate precocemente o di collassare verso strategie pure successivamente. PPO-EMAg evita questo problema riducendo gradualmente la massa sulle azioni dominate pur mantenendo la pressione di mixing, permettendo alla politica di ciclare vicino all'equilibrio di Nash.

Significato e Assertions

Il paper sostiene che EMAgnet offre un meccanismo semplice ed efficace per adattare i target di regolarizzazione alla strategia evolutiva di un agente in giochi ampi. Regolarizzando verso un'EMA nello spazio dei parametri dei pesi della propria politica, il metodo evita le insidie della regolarizzazione uniforme in giochi con un gran numero di strategie strettamente dominate.

Gli autori postulano che man mano che i giochi crescono in complessità, la frazione dello spazio strategico che è strategicamente rilevante tende a diminuire. In tali scenari, allocare il budget di regolarizzazione a opzioni subottimali comporta un costo crescente. EMAgnet affronta questo problema "dimenticando" le strategie cattive e "ricordando" quelle buone, richiedendo solo un singolo aggiornamento EMA per ogni step di addestramento oltre al loop standard di PPO. Il paper conclude che, sebbene PPO-EMAg sia competitivo sui benchmark standard, il suo vantaggio principale risiede nei giochi con alta densità di strategie dominate, dove consente una convergenza più rapida e una sfruttabilità finale inferiore rispetto alla regolarizzazione uniforme con annealing.