Riepilogo Tecnico: Ricerca ad Albero Monte Carlo Epistemica (EMCTS)

Enunciato del Problema

La famiglia di algoritmi AlphaZero/MuZero (A/MZ) ha ottenuto successi significativi integrando la Ricerca ad Albero Monte Carlo (MCTS) con modelli appresi di valore e dinamiche dell'ambiente. Tuttavia, questi modelli appresi introducono incertezza epistemica—l'incertezza derivante dalla copertura limitata dei dati durante l'addestramento. Sebbene A/MZ utilizzi MCTS per la pianificazione, l'algoritmo standard è stato progettato per la ricerca con dinamiche vere e non tiene conto della propagazione dell'incertezza epistemica. Di conseguenza, A/MZ non può sfruttare efficacemente MCTS per la esplorazione profonda (la capacità di cercare ricompense lontane dallo stato corrente) in ambienti a ricompensa rada, né può sfruttare l'incertezza associata alle previsioni dell'albero di ricerca per altri scopi, come la riduzione degli errori di sovrastima.

I metodi attuali per l'esplorazione profonda spesso si affidano a strategie Upper Confidence Bound (UCB) che stimano l'incertezza alla radice o tramite ensemble, ma non propagano questa incertezza attraverso l'albero di ricerca stesso. Ciò limita la capacità dell'agente di distinguere tra previsioni basate su evidenze e quelle basate sulla generalizzazione durante la fase di pianificazione.

Metodologia: MCTS Epistemica (EMCTS)

Gli autori propongono Epistemic MCTS (EMCTS), un'estensione teoricamente motivata di MCTS che stima e propaga esplicitamente l'incertezza epistemica dai modelli appresi (valore, ricompensa e transizione) attraverso l'intero albero di ricerca.

Componenti Principali

1. Formulazione dei Modelli come Variabili Casuali: Il modello appreso $\hat{m}$ è trattato come una variabile casuale. La funzione di valore nel modello, $Q^\pi_{\hat{M}}(s, a)$, è definita come una variabile casuale la cui varianza rappresenta l'incertezza epistemica.
2. Fondamento Teorico (Costruzione UCB): Il documento deriva un limite superiore teorico (Teorema 1) che mostra come, con alta probabilità ($1-\delta$), il valore ottimo vero $Q^*(s, a)$ sia limitato dal valore atteso massimo nel modello appreso più un termine proporzionale alla deviazione standard di tale valore:
   $$Q^*(s, a) \leq \max_\pi \left( Q^\pi_{\hat{M}}(s, a) + \frac{1}{\sqrt{\delta}} \sqrt{V[Q^\pi_{\hat{M}}(s, a)]} \right)$$
   Ciò giustifica l'uso della varianza delle previsioni di valore come bonus per l'esplorazione.
3. Politiche di Ricerca Epistemica: La politica di selezione PUCT standard è modificata per includere un bonus di incertezza. La nuova politica di selezione, Epistemic P/UCT (EPUCT), seleziona le azioni basandosi su:
   $$a^{EPUCT} = \arg\max_{a} \left( q^\beta_{\hat{M}}(s_k, a) + C_{PUCT} \frac{\pi(a|s_k)}{\sqrt{N(s_k, a)}} \right)$$
   Dove $q^\beta_{\hat{M}}$ è il valore medio più un bonus $\beta$ volte la deviazione standard stimata delle previsioni di valore.
4. Propagazione dell'Incertezza:
   • Passo di Backup: L'algoritmo stima l'incertezza epistemica di un singolo passo di backup, $V[\nu_i]$, sommando le varianze della ricompensa e del valore dello stato successivo (assumendo indipendenza o utilizzando un limite superiore per backup correlati).
   • Incertezza del Valore del Nodo: Per stimare l'incertezza del valore del nodo $q_{\hat{M}}(s_k, a)$ (la media di $N$ backup), gli autori propongono un limite superiore sulla varianza della media. Poiché i backup in A/MZ non sono indipendenti (condividono lo stesso modello), la varianza della media è limitata superiormente dal quadrato della media delle deviazioni standard:
     $$V[q_{\hat{M}}(s_k, a)] \leq \left( \frac{1}{N(s_k, a)} \sum_{i=0}^{N(s_k, a)} \sqrt{V[\nu_i(s_k, a)]} \right)^2$$
   • Stimatori di Incertezza: Il metodo utilizza stimatori esistenti per l'incertezza locale (ad esempio, Distillazione di Reti Casuali (RND) o conteggi di visite per ricompense/transizioni) e l'Equazione di Bellman dell'Incertezza (UBE) per l'incertezza di valore.

Implementazione

Gli autori forniscono un'implementazione parallelizzata in JAX, accoppiando EMCTS con un agente AlphaZero (E-AZ) e un agente MuZero (E-MZ). Il sistema alterna episodi esplorativi (utilizzando la politica di ricerca epistemica) ed episodi sfruttativi (utilizzando MCTS standard) per garantire un addestramento stabile da dati off-policy.

Contributi Chiave

1. Motivazione Teorica: Una derivazione che mostra come costruire un UCB valido per l'esplorazione profonda utilizzando la varianza delle previsioni dei modelli appresi all'interno di un framework MCTS.
2. Innovazione Algoritmica: L'algoritmo EMCTS, che propaga l'incertezza epistemica dai modelli appresi di valore, ricompensa e transizione attraverso l'albero di ricerca, permettendo alla ricerca stessa di affinare le stime di incertezza.
3. Implementazione Pratica: Un'implementazione basata su JAX di EMCTS accoppiata con AZ e MuZero, includendo adattamenti specifici per l'ambiente subleq del linguaggio Assembly e il benchmark Deep Sea.

Risultati Sperimentali

Gli autori valutano EMCTS in due domini impegnativi a ricompensa rada:

1. Subleq (Programmazione Assembly):

   • Compito: Scrivere codice in un linguaggio assembly a un'istruzione per risolvere compiti come "Negare i Positivi" e "Funzione Identità".
   • Risultati: E-AZ (AlphaZero con EMCTS) supera significativamente la linea di base AZ nell'efficienza del campione. E-AZ risolve il compito più difficile "Funzione Identità" (che richiede uno spazio di ricerca di $\approx 16^6$ stati) in molti meno passi rispetto alla linea di base. I risultati suggeriscono che la qualità dello stimatore di incertezza (ad esempio, l'uso di un hash IO rispetto a un hash dello stato completo) impatta direttamente sulle prestazioni, con stimatori migliori che portano a una scoperta della soluzione più precoce.

2. Benchmark Deep Sea:

   • Compito: Un mondo a griglia in cui il percorso ottimale è nascosto e richiede un'esplorazione profonda; l'esplorazione casuale fallisce esponenzialmente all'aumentare della dimensione della griglia.
   • Risultati:
     • Esplorazione Profonda: E-AZ ed E-MZ risolvono con successo il compito in grandi dimensioni di griglia (fino a 50x50) dove le linee di base A/MZ e A/MZ+UBE (che utilizzano l'incertezza ma non cercano con essa) falliscono completamente.
     • Vantaggio della Ricerca: EMCTS supera significativamente l'ablazione "A/MZ+UBE", dimostrando che cercare con l'incertezza (propagandola attraverso l'albero) produce un'esplorazione migliore rispetto al semplice aggiunta di un bonus di incertezza alla selezione dell'azione alla radice.
     • Ricompense Stocastiche: Il metodo gestisce con successo le variazioni stocastiche delle ricompense di Deep Sea, risolvendole dove le linee di base non riescono.
     • Dinamiche Apprese: I benefici di EMCTS sono mantenuti anche quando si utilizza il modello di transizione appreso di MuZero (astrazione equivalente al valore), confermando la robustezza del metodo in contesti basati su modelli.

Significato e Affermazioni

Il documento afferma che EMCTS fornisce un metodo pratico e teoricamente fondato per incorporare l'incertezza epistemica negli agenti basati su MCTS. Il suo significato principale risiede in:

• Abilitazione dell'Esplorazione Profonda: Permette agli agenti A/MZ di risolvere compiti a ricompensa rada e ad esplorazione difficile (come la progettazione di algoritmi o la programmazione complessa) che sono praticamente irrisolvibili dalle linee di base A/MZ a causa della loro incapacità di propagare l'incertezza attraverso la ricerca.
• Ricerca per l'Incertezza: Dimostra che utilizzare la ricerca per stimare l'incertezza (invece di usare la ricerca solo per stimare il valore) fornisce vantaggi significativi nell'efficienza del campione.
• Applicabilità più Ampia: Oltre all'esplorazione, gli autori notano che la capacità di EMCTS di stimare l'incertezza nelle previsioni di valore durante e dopo la ricerca potrebbe essere benefica per l'RL offline (ad esempio, riducendo la sovrastima tramite pessimismo) e per la generazione di target off-policy (Reanalyze), rendendo gli agenti A/MZ più affidabili di fronte all'ignoto.

Gli autori rimangono modesti, notando che, sebbene il metodo sia promettente per ambienti a ricompensa rada e progettazione di algoritmi, l'utilità specifica in altri domini (come l'RL offline) è proposta come una potenziale applicazione futura basata sulle capacità del metodo.