Riepilogo Tecnico: GAE è Inadeguato nell'Auto-Play con Informazione Imperfetta

Enunciato del Problema

L'apprendimento per rinforzo competitivo multi-agente (MARL) nei giochi con informazione imperfetta richiede che gli agenti operino sotto osservabilità parziale contro avversari avversari, rendendo necessarie politiche stocastiche. Sebbene l'apprendimento per rinforzo tramite auto-play utilizzando l'Ottimizzazione della Politica Prossimale (PPO) abbia ottenuto successi empirici, incontra un collo di bottiglia critico nell'apprendimento dell'equilibrio: la varianza nella stima del vantaggio.

Le implementazioni standard di PPO si affidano alla Stima del Vantaggio Generalizzata (GAE) per aggregare i residui temporali-differenziali (TD) su più passi. In contesti ad agente singolo, la GAE bilancia efficacemente bias e varianza. Tuttavia, nell'auto-play con informazione imperfetta, le politiche di equilibrio sono intrinsecamente stocastiche. La GAE eredita la casualità dal campionamento delle azioni future all'interno della sua traccia multi-passo. Poiché le politiche di equilibrio assegnano valori diversi a diverse azioni, il campionamento delle azioni future introduce rumore intrinseco. Questa varianza viene amplificata negli scenari di auto-play e persiste anche quando il critico del valore dello stato ($V$-critic) è esatto. Di conseguenza, la GAE standard produce stime del gradiente ad alta varianza proprio nei regimi in cui un apprendimento stabile è più critico, ostacolando la convergenza verso equilibri di alta qualità.

Metodologia

Stimatore Q-Boosting

Per affrontare la varianza introdotta dal campionamento delle azioni, gli autori propongono il Q-boosting, uno stimatore del vantaggio a varianza ridotta. L'innovazione principale consiste nel sostituire la traccia TD multi-passo campionata utilizzata nella GAE con una traccia multi-passo Expected SARSA($\lambda$) calcolata a partire da un critico centralizzato del valore-azione ($Q$-critic).

• Meccanismo: Invece di effettuare il bootstrap attraverso azioni successive campionate (che introduce rumore), il Q-boosting calcola le aspettative della politica ad ogni passo di backup. Mediando il rumore derivante dalle azioni future stocastiche prendendo l'aspettativa sulla distribuzione delle azioni definita dalla politica corrente.
• Formulazione: Dato un critico centralizzato $Q_i(s, a)$ e una politica congiunta $\pi$, il valore dello stato è calcolato come $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$. La stima del vantaggio Q-boosting $\hat{A}^{boost}_{i,\tau}$ è definita come:
  $$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$$
  dove il residuo TD Expected SARSA è $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$.
• Garanzia Teorica: Gli autori dimostrano che per traiettorie on-policy e $\lambda=1$, lo stimatore Q-boosting fornisce una stima non distorta del termine del gradiente della politica basato sulla funzione di punteggio. Inoltre, se il critico $Q$ è sufficientemente accurato, l'errore quadratico medio dello stimatore Q-boosting è strettamente inferiore a quello della GAE con un critico $V$ esatto, a condizione che le azioni future presentino una varianza non nulla nei loro valori d'azione.

Ottimizzazione della Politica a Varianza Ridotta (VRPO)

Gli autori integrano il Q-boosting in un algoritmo in stile PPO denominato Ottimizzazione della Politica a Varianza Ridotta (VRPO).

• Architettura: Il VRPO segue il paradigma dell'Addestramento Centralizzato con Esecuzione Decentralizzata (CTDE). Utilizza attori decentralizzati per l'esecuzione e un critico $Q$ centralizzato per l'addestramento.
• Obiettivo: L'algoritmo mantiene l'obiettivo surrogato troncato e gli aggiornamenti della regione di fiducia della PPO, ma modifica le procedure di stima del vantaggio e di apprendimento del critico.
• Procedura di Addestramento:
  1. Aggiornamento dell'Attore: Gli attori vengono aggiornati utilizzando le stime del vantaggio Q-boosting. Per mantenere le proprietà on-policy, i termini di aspettativa della politica nel calcolo del vantaggio vengono ricalcolati utilizzando le probabilità attuali dell'attore, mantenendo fissi i valori del critico.
  2. Aggiornamento del Critico: I critici $Q$ centralizzati vengono addestrati minimizzando la perdita di regressione al quadrato rispetto all'obiettivo Q-boosting (una traccia Expected SARSA multi-passo).
  3. Regolarizzazione: Viene aggiunta una penalità esplicita di divergenza KL rispetto a una distribuzione uniforme all'obiettivo della politica per promuovere l'esplorazione e incoraggiare la convergenza all'ultima iterazione.
• Gestione di Spazi di Azione Grandi: Per giochi con enormi insiemi di azioni (ad esempio, Dou Dizhu), gli autori scompongono le decisioni complesse in più passi temporali. Questo riduce il numero di azioni disponibili per passo a una dimensione gestibile, consentendo l'enumerazione richiesta per l'aspettativa della politica nella traccia Q-boosting.

Contributi Chiave

1. Identificazione della Fonte di Varianza: Il documento identifica che il campionamento delle azioni future nella GAE introduce varianza aggiuntiva nell'auto-play stocastico, che persiste anche con funzioni di valore esatte.
2. Stimatore Q-Boosting: Gli autori derivano il Q-boosting, uno stimatore compatibile con la PPO che applica una traccia Expected SARSA($\lambda$) a un critico $Q$ centralizzato per mediare il rumore del campionamento delle azioni future.
3. Algoritmo VRPO: La proposta del VRPO, un algoritmo in stile PPO che sfrutta il Q-boosting per ottenere stabilità e prestazioni migliorate.
4. Validazione Empirica: Dimostrazione che la riduzione della varianza nella stima del vantaggio produce guadagni sostanziali nella qualità dell'equilibrio attraverso giochi di scale diverse.

Risultati Sperimentali

Giochi di Dimensione Media (Sfruttabilità Esatta)

Gli autori hanno valutato il VRPO su giochi di dimensione media in cui è possibile calcolare la sfruttabilità esatta: Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3) e Liar's Dice con 2 Dadi e 5 Facce (LiDi 2D5F).

• Prestazioni: Il VRPO ha costantemente raggiunto una sfruttabilità inferiore di oltre il 15% rispetto a vari baseline basati su PPO (IPPO, MAPPO, MMD, PPG) sotto un programma di addestramento condiviso.
• Ablazione: Gli esperimenti hanno confermato che i guadagni di prestazioni sono robusti attraverso diversi parametri di traccia ($\lambda$), coefficienti di regolarizzazione ($\alpha$) e coefficienti di clipping PPO ($\epsilon$).

Giochi su Larga Scala

Gli autori hanno valutato il VRPO in domini su larga scala in cui la sfruttabilità esatta è intrattabile.

• Dou Dizhu: Il VRPO è stato addestrato contro l'agente precedente stato dell'arte, PerfectDou. Con un budget di addestramento abbinato ($\approx 2.65 \times 10^9$ passi temporali), il VRPO ha superato PerfectDou dopo solo il 40% dei passi di addestramento. Nelle valutazioni testa a testa su 100.000 mani, il VRPO ha ottenuto guadagni positivi contro PerfectDou, DouZero e se stesso (in confronti con ruoli scambiati), stabilendo un nuovo stato dell'arte.
• Heads-Up No-Limit Texas Hold'em (HUNL): Il VRPO è stato addestrato su HUNL con una pila di 200 big blind. Rispetto a IPPO e MAPPO, il VRPO ha ridotto significativamente la deviazione standard delle stime del vantaggio durante l'addestramento. Contro il forte baseline Slumbot, l'agente VRPO ha raggiunto un guadagno medio di $33 \pm 19$ mBB/mano su 1.000.000 di mani. Notabilmente, questa prestazione è stata ottenuta senza ricerca online, risoluzione di sottogiochi o dimensionamento delle puntate basato su blueprint.

Significato e Ambito

Il documento afferma che il contributo principale è l'identificazione della varianza nella stima del vantaggio come collo di bottiglia nell'auto-play di equilibrio e la dimostrazione che il Q-boosting mitiga efficacemente questo problema. I risultati suggeriscono che la riduzione della varianza nella stima del vantaggio può produrre guadagni sostanziali nella qualità degli equilibri appresi.

Gli autori mantengono un ambito modesto riguardo alle loro affermazioni:

• L'approccio è validato per giochi con grandi insiemi di azioni discrete (tramite scomposizione) ma non affronta spazi di azione continui ad alta dimensionalità.
• Il focus empirico è sull'auto-play stocastico con critici centralizzati; gli autori non rivendicano miglioramenti generali rispetto alla GAE nei benchmark standard di RL ad agente singolo.
• Il metodo si basa sulla capacità di calcolare aspettative di politica sulle azioni, il che è fattibile nei domini testati ma potrebbe richiedere considerazioni architetturali specifiche per spazi di azione estremamente grandi.

In conclusione, il VRPO rappresenta un passo significativo in avanti nell'applicazione dei metodi del gradiente della politica ai giochi con informazione imperfetta, affrontando una fonte specifica e precedentemente sottostimata di varianza intrinseca nell'apprendimento di equilibri stocastici.