MDP Planning as Policy Inference

Questo lavoro riformula la pianificazione nei processi decisionali di Markov come inferenza bayesiana sulle politiche, adattando il metodo VSMC per approssimare la distribuzione a posteriori delle politiche ottimali e generando azioni tramite campionamento predittivo che incorpora l'incertezza a livello di politica, distinguendosi così dai metodi di regolarizzazione entropica come il Soft Actor-Critic.

L'essenziale

Immagina di dover insegnare a un robot come giocare a un gioco complesso, come gli scacchi o un videogioco di avventura. Tradizionalmente, gli scienziati dicono al robot: "Prova milioni di volte, guarda cosa funziona meglio e impara a fare esattamente quello".

Questo articolo, scritto da David Tolpin, propone un modo completamente diverso di pensare. Invece di cercare una risposta perfetta, chiede al robot di imparare tutte le possibili risposte buone e di scegliere quella giusta al momento giusto, basandosi su quanto è sicuro di sé.

Ecco la spiegazione semplice, con qualche metafora divertente.

1. Il Problema: La Mappa vs. La Bussola

Immagina di dover attraversare una foresta piena di nebbia (il "mondo" del gioco).

• Il metodo vecchio (Apprendimento per Rinforzo classico): Il robot prova a camminare mille volte. Se sbaglia strada, si punisce. Alla fine, costruisce una mappa fissa: "Se sono qui, devo andare a destra". Se la nebbia cambia o c'è un imprevisto, la mappa potrebbe non funzionare più.
• Il metodo nuovo (Inferenza Bayesiana sulle Politiche): Invece di una mappa fissa, il robot immagina di avere un gruppo di esploratori (chiamati "particelle"). Ogni esploratore ha una sua idea su come attraversare la foresta. Alcuni pensano che la strada di sinistra sia la migliore, altri quella di destra.

L'obiettivo non è trovare l'unico esploratore perfetto, ma capire quanto sono sicuri gli esploratori delle loro idee.

2. La Grande Idea: "Credere" nelle Strategie

Il cuore di questo lavoro è trattare la strategia (la "politica") come una cosa misteriosa che dobbiamo indovinare, proprio come un detective indovina il colpevole.

• La "Probabilità di Ottimalità": Immagina che ogni strategia abbia un punteggio. Più alta è la ricompensa che porta, più "credibile" diventa quella strategia.
• La Nebbia della Certezza: Se una strategia porta a un risultato fantastico e sicuro, il robot diventa molto sicuro di sé (la "nebbia" si dirada). Se due strategie sembrano entrambe buone ma portano a risultati diversi, il robot rimane incerto. Questa incertezza non è un errore! È una informazione preziosa. Significa: "Ehi, non sono sicuro di quale strada sia la migliore, quindi devo essere flessibile".

3. Come Funziona la Magia (Senza Matematica Complessa)

Il paper usa un trucco intelligente chiamato VSMC (Variational Sequential Monte Carlo). Immaginalo così:

1. Il Gruppo di Esploratori: Il robot lancia 10 esploratori (particelle) nella foresta contemporaneamente.
2. La Regola d'Oro (Coerenza): Se un esploratore decide di girare a sinistra alla prima svolta, deve continuare a girare a sinistra ogni volta che torna a quella svolta. Non può cambiare idea a metà strada. Questo evita confusione.
3. La Tempesta Condivisa: Se due esploratori si trovano nello stesso punto e fanno la stessa mossa, devono affrontare esattamente la stessa tempesta o lo stesso ostacolo. Questo è fondamentale! Serve a capire se un esploratore è bravo perché è intelligente, o solo perché ha avuto fortuna con il tempo. Se entrambi affrontano la stessa tempesta e uno sopravvive e l'altro no, allora sappiamo chi è il vero esperto.
4. La Scelta Finale (Campionamento Thompson): Quando il robot deve muoversi, non guarda la "mappa media". Fa così:
   • "Ok, quale esploratore scelgo oggi?"
   • Pesca a caso uno degli esploratori dal suo gruppo di idee.
   • Esegue la mossa che quell'esploratore suggerisce.

Se il robot è molto sicuro (tutti gli esploratori pensano la stessa cosa), la scelta sarà quasi sempre la stessa (comportamento deterministico). Se è incerto (gli esploratori litigano), il robot cambierà strategia di volta in volta, esplorando diverse opzioni.

4. Perché è Diverso dagli Altri Metodi?

I metodi moderni (come SAC) usano una tecnica chiamata "regolarizzazione dell'entropia". È come dire al robot: "Sii un po' casuale, non essere troppo rigido, così impari di più".

• Il problema: Questa casualità è un trucco matematico forzato.
• La soluzione di Tolpin: La casualità qui è naturale. Il robot è casuale solo perché non è sicuro di quale sia la strada migliore. Se fosse sicuro, non sarebbe casuale. È come un guidatore: se conosce la strada, guida dritto. Se è in un posto nuovo e non sa dove andare, guarda a destra e a sinistra, esita e prova diverse direzioni.

5. Cosa Hanno Scoperto nei Test?

Hanno provato questo metodo su giochi come il Blackjack e mondi a griglia:

• Nel Blackjack: Il metodo nuovo ha imparato a giocare meglio rispetto ai metodi tradizionali che usano troppa "casualità forzata".
• Nei Mondi a Griglia: Il metodo vecchio tendeva a fare cose strane solo per aumentare la "casualità" (come andare contro i bordi del muro). Il metodo nuovo, invece, capisce che andare contro il muro è stupido e non lo fa, a meno che non sia davvero incerto su cosa fare.
• Il trucco dei Premi: Hanno scoperto che se i premi sono troppo alti o troppo bassi, il robot diventa troppo sicuro o troppo confuso. Bisogna calibrare bene quanto "valore" diamo alle ricompense, proprio come un allenatore che deve motivare il giocatore senza esagerare.

In Sintesi

Questo paper ci dice che per prendere decisioni intelligenti in un mondo incerto, non dobbiamo cercare la "soluzione perfetta" fissa. Dobbiamo invece mantenere un ventaglio di buone idee, capire quanto siamo sicuri di ciascuna, e scegliere di volta in volta in base a quella sicurezza.

È come avere un consiglio di amministrazione interno: invece di avere un solo CEO che decide tutto, hai un gruppo di esperti. Se sono tutti d'accordo, agisci deciso. Se sono in disaccordo, ascolta tutti e prova diverse strade finché non trovi quella giusta.

Sommario tecnico

Titolo: MDP Planning as Policy Inference (Pianificazione MDP come Inferenza sulle Politiche)

1. Problema e Contesto

Il paper affronta il problema della pianificazione in processi decisionali di Markov (MDP) episodici. L'obiettivo tradizionale è identificare una politica che massimizzi il ritorno atteso.
La letteratura esistente su "controllo come inferenza" (Control-as-Inference) e sull'apprendimento per rinforzo regolarizzato dall'entropia (come SAC) tende a modificare l'obiettivo classico di pianificazione. Questi approcci spesso introducono variabili di ottimalità ausiliarie o osservazioni fittizie, trattando la stocasticità come una preferenza di modellazione o un dispositivo di esplorazione. Di conseguenza, l'incertezza sulla soluzione ottimale del problema originale del ritorno atteso non è direttamente interpretabile dalla politica inferita.

Il paper propone una formulazione bayesiana che preserva l'obiettivo classico del MDP (massimizzazione del ritorno atteso) senza alterare la funzione di ricompensa o introdurre variabili latenti fittizie a livello di traiettoria.

2. Metodologia

A. Formulazione Probabilistica
L'autore tratta la politica ($\pi$) stessa come la variabile latente da inferire, anziché le azioni o gli stati.

• Viene definita una densità di probabilità non normalizzata per ogni politica, monotona rispetto al suo ritorno atteso:
  $$\log \tilde{p}(\pi) = \mathbb{E}_{\tau_\pi} \left[ \sum_{t=1}^H R(s_t, a_t, s_{t+1}) \right]$$
• Questo induce una distribuzione di Boltzmann-Gibbs sulle politiche. I modi della distribuzione a posteriori corrispondono alle politiche che massimizzano il ritorno, mentre la dispersione della distribuzione quantifica l'incertezza sul comportamento ottimale.
• L'azione viene selezionata campionando dalla distribuzione predittiva a posteriori, interpretabile come Thompson sampling ricorrente, non come regolarizzazione dell'entropia.

B. Algoritmo: VSMC per Politiche Deterministiche
Per approssimare questa distribuzione a posteriori in MDP discreti con transizioni stocastiche, l'autore adatta il Variational Sequential Monte Carlo (VSMC).
L'algoritmo inferisce politiche deterministiche (una singola azione per stato) e genera stocasticità solo marginalizzando su queste politiche al momento dell'esecuzione. Due adattamenti chiave sono necessari:

1. Coerenza della Politica (Policy Consistency): Per ogni particella, l'azione per uno stato viene campionata dalla proposta solo alla prima visita a quello stato e riutilizzata in tutte le rivedite successive. Questo garantisce che ogni particella rappresenti una politica coerente e non una sequenza di azioni casuali.
2. Accoppiamento della Casualità delle Transizioni (Coupled Transition Randomness): All'interno di una singola passata (sweep) SMC, la casualità delle transizioni dell'ambiente è condivisa tra tutte le particelle. Se due particelle visitano lo stesso stato con la stessa azione e lo stesso numero di visite, sono forzate a transire verso lo stesso stato successivo. Questo assicura che i pesi delle particelle riflettano le differenze tra le politiche e non realizzazioni indipendenti del rumore dell'ambiente.

C. Funzione di Obiettivo e Ottimizzazione
L'obiettivo è massimizzare la stima del log-evidenza ($\log \hat{Z}$) tramite VSMC. Poiché la proposta sulle azioni è categorica (non reparametrizzabile), l'algoritmo mantiene i termini della funzione di punteggio (score-function) derivanti dal campionamento delle azioni, utilizzando un segnale di apprendimento stratificato temporalmente per ridurre la varianza.

3. Contributi Chiave

1. Nuova Formulazione Bayesiana: Una definizione di pianificazione MDP come inferenza su politiche che mantiene il criterio di ottimalità del ritorno atteso classico, generando una politica stocastica ottimale sotto incertezza sulle preferenze tramite campionamento predittivo.
2. Adattamento VSMC: Un adattamento specifico del VSMC per l'inferenza su politiche deterministiche in MDP con transizioni stocastiche, includendo la coerenza nella rivedita degli stati e l'accoppiamento del rumore di transizione.
3. Valutazione Empirica: Un'analisi comparativa tra la politica indotta dal campionamento predittivo (VSMC) e l'ottimizzazione diretta di politiche stocastiche regolarizzate dall'entropia (Discrete Soft Actor-Critic - SAC) su diversi benchmark.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su Grid Worlds, Blackjack, Triangle Tireworld e Academic Advising, confrontando VSMC con SAC.

• Grid Worlds:

  • VSMC produce distribuzioni multimodali che riflettono l'incertezza reale.
  • A differenza di SAC, che tende a massimizzare l'entropia muovendosi verso i bordi della griglia (anche se non ottimali), VSMC evita azioni che aumentano l'entropia a scapito della raggiungibilità dell'obiettivo, penalizzando fortemente le azioni che porterebbero fuori dalla griglia in un contesto deterministico.
  • L'uso di dinamiche condivise tra le particelle è cruciale: senza di esse, l'agente tende a scegliere percorsi più brevi ma rischiosi a causa del rumore indipendente.

• Blackjack:

  • VSMC ottiene un ritorno atteso superiore a SAC con il peso di entropia standard ($\alpha=1$).
  • Per avvicinarsi alle prestazioni di VSMC, SAC richiede una regolarizzazione dell'entropia molto più debole ($\alpha=0.1$) e, per avvicinarsi alla politica ottima, richiede $\alpha=0.01$ e un numero molto maggiore di passi.
  • VSMC mostra una probabilità di pareggio inferiore rispetto sia alla politica ottima che a SAC.

• Triangle Tireworld:

  • Questo dominio presenta eventi stocastici irreversibili (foratura).
  • Con le ricompense originali (grande gap tra comportamenti "veloci ma rischiosi" e "lenti ma sicuri"), la distribuzione a posteriori di VSMC diventa altamente concentrata, portando a prestazioni scadenti.
  • Riducendo la scala delle ricompense (fattore 0.2), la posterior diventa meno concentrata e le prestazioni di VSMC diventano comparabili a quelle di SAC. Questo evidenzia che, a differenza della pianificazione classica, l'inferenza bayesiana è sensibile alla scala delle ricompense.

• Academic Advising:

  • In problemi combinatori complessi con orizzonti lunghi, entrambi i metodi faticano sugli istanze difficili.
  • Tuttavia, VSMC mostra distribuzioni di ritorno con code più pesanti (heavy tails) rispetto a SAC, indicando una maggiore variabilità nelle traiettorie risolte, il che può essere utile in scenari dove l'incertezza strutturale è alta.

5. Significato e Conclusioni

Il lavoro dimostra che è possibile trattare la pianificazione come inferenza bayesiana senza sacrificare l'obiettivo di massimizzazione del ritorno atteso.

• Interpretazione dell'Incertezza: La stocasticità nella politica finale non è un artefatto di regolarizzazione (come in SAC), ma riflette l'incertezza epistemica su quale politica deterministica sia quella migliore. Se le politiche candidate hanno rendimenti simili, la distribuzione a posteriori rimane diffusa, portando a un comportamento stocastico naturale. Se una politica è chiaramente superiore, la posterior si concentra e il comportamento diventa deterministico.
• Distinzione Concettuale: A differenza degli approcci "Control-as-Inference" tradizionali che introducono variabili di ottimalità fittizie, questo metodo inferisce direttamente sulla politica, separando l'incertezza sulla soluzione dall'aleatorietà dell'ambiente.
• Implicazioni Pratiche: L'approccio offre un modo strutturato per incorporare l'incertezza nelle decisioni (Thompson sampling) e suggerisce che la scala delle ricompense gioca un ruolo critico nel controllare il livello di esplorazione/stocasticità, agendo come un parametro di "preferenza" piuttosto che come un semplice moltiplicatore di entropia.

In sintesi, il paper propone un framework unificato che combina la robustezza degli algoritmi SMC con la chiarezza semantica dell'inferenza bayesiana, offrendo un'alternativa promettente ai metodi di ottimizzazione diretta delle politiche stocastiche.