Riepilogo Tecnico: Apprendimento Bayesiano per il Problema del Percorso Breve Stocastico

1. Formulazione del Problema

Il documento affronta il problema del Percorso Breve Stocastico (Stochastic Shortest Path - SSP), definito come un processo decisionale di Markov (MDP) a orizzonte infinito e non scontato, con uno stato terminale assorbente. A differenza degli MDP standard scontati ($\gamma = 1$), la formulazione SSP richiede l'esistenza di un unico stato obiettivo assorbente a ricompensa nulla ($s_g$) e l'esistenza di almeno una politica "propria" (una politica che raggiunge $s_g$ con probabilità 1 da qualsiasi stato).

L'obiettivo primario è apprendere la funzione valore-azione ottimale, $Q^*$, che soddisfa le Equazioni di Ottimalità di Bellman (BOE). La sfida risiede nel fatto che $Q^*$ non è osservata direttamente; vengono osservate solo triplette stato-azione-ricompensa $(s, a, r)$ attraverso l'interazione. Gli autori mirano a costruire un framework bayesiano per quantificare l'incertezza su $Q^*$ e facilitare i compromessi esplorazione-sfruttamento tramite il Thompson Sampling (campionamento della distribuzione a posteriori), senza fare affidamento sulle ipotesi irrealistiche o sulle approssimazioni ad hoc comuni nella letteratura esistente sul Reinforcement Learning (RL) Bayesiano.

2. Metodologia

2.1. Costruzione della Verosimiglianza tramite le Equazioni di Bellman

Il principale contributo metodologico è la costruzione diretta della funzione di verosimiglianza basata sulle BOE, piuttosto che su algoritmi di approssimazione stocastica (come il Q-learning) o errori di differenza temporale (TD).

• Parametrizzazione: La funzione valore ottimale è approssimata da una funzione parametrica $Q_\theta$.
• Vincolo: Per una coppia stato-azione $(s, a)$, la ricompensa attesa $\bar{r}_{s,a}$ deve soddisfare la BOE: $\bar{r}_{s,a} = Q_\theta(s, a) - \mathbb{E}[\max_{a'} Q_\theta(S', a')]$.
• Verosimiglianza: Gli autori definiscono una funzione di verosimiglianza $p(r_t | \theta, \psi, s_t, a_t)$ dove la ricompensa osservata $r_t$ è modellata come la ricompensa attesa deterministica più del rumore. Ciò vincola i parametri $\theta$ affinché siano coerenti con le BOE osservate.

2.2. Gestione delle Ricompense Deterministiche e delle Posterior su Manifold

Una significativa sfida teorica sorge quando le ricompense sono deterministiche (senza rumore). In questo caso, le BOE impongono vincoli di uguaglianza rigorosi su $\theta$.

• Densità di Manifold: La distribuzione a posteriori di $\theta$ collassa dall'intero spazio dei parametri su un manifold a bassa dimensione definito dall'intersezione dei vincoli BOE.
• Misura di Hausdorff: Gli autori caratterizzano questa distribuzione a posteriori utilizzando una densità rispetto alla misura di Hausdorff (Teorema 2), piuttosto che una densità di Lebesgue standard. Ciò fornisce una descrizione matematica rigorosa della distribuzione a posteriori per ricompense prive di rumore.

2.3. Rilassamento della Verosimiglianza e Approssimazione

Il campionamento diretto da una densità di manifold è computazionalmente intrattabile per i metodi Monte Carlo standard. Per facilitare l'inferenza, gli autori propongono di rilassare la verosimiglianza:

• Convoluzione: La verosimiglianza esatta viene convoluta con un kernel (ad esempio, Gaussiano o uniforme) con tolleranza $\epsilon$.
• Densità di Lebesgue: Questo rilassamento "ispessisce" il manifold, risultando in una distribuzione a posteriori con una densità di Lebesgue standard adatta al campionamento MCMC.
• Compromesso: Il documento analizza rigorosamente le conseguenze di questo rilassamento. Sebbene consenta un campionamento trattabile, introduce problemi di non identificabilità. Nello specifico, per le parametrizzazioni tabulari, la verosimiglianza rilassata può assegnare massa infinita a insiemi di parametri corrispondenti a politiche improprie (politiche che non raggiungono mai l'obiettivo), mentre la distribuzione a posteriori esatta non lo fa.

2.4. Campionamento della Posterior per l'Esplorazione

Il framework utilizza il Thompson Sampling (Campionamento della Posterior) per l'esplorazione. Ad ogni episodio, una politica viene campionata dalla distribuzione a posteriori di $Q_\theta$ (sia campionando direttamente $\theta$, sia calcolando la massa di probabilità sulle politiche) e viene implementata fino al raggiungimento dell'obiettivo o al rilevamento di un loop improprio.

3. Contributi Chiave

1. Formulazione Bayesiana Rigorosa: Il documento fornisce una formulazione bayesiana dai primi principi per gli SSP, derivando la verosimiglianza direttamente dalle Equazioni di Ottimalità di Bellman, evitando le verosimiglianze euristiche spesso usate nei metodi TD-based di RL Bayesiano.
2. Caratterizzazione del Manifold: Stabilisce che, per ricompense deterministiche, la distribuzione a posteriori risiede su un manifold a bassa dimensione e fornisce la formula esplicita della densità rispetto alla misura di Hausdorff (Teorema 2).
3. Analisi del Rilassamento e della Non Identificabilità: Gli autori dimostrano matematicamente che il rilassamento della verosimiglianza tramite un kernel Gaussiano (per ottenere una densità di Lebesgue) crea un problema specifico di non identificabilità: la distribuzione a posteriori può essere dominata da politiche improprie se la varianza del prior è elevata (Teorema 4). Ciò contrasta con la distribuzione a posteriori esatta, che esclude correttamente le politiche improprie.
4. Derivazione della Posterior Tabulare: Per le parametrizzazioni tabulari con prior Gaussiani e verosimiglianze rilassate, si dimostra che la posterior è un mix di Gaussiane troncate (Proposizione 1).
5. Benchmarking e Validazione Empirica: Il documento introduce un protocollo di benchmarking utilizzando le varianti dell'ambiente "Deep Sea" per confrontare il proprio metodo con approcci bayesiani basati su TD (Bayes-TD, Bayes-TD-En, Bayes-TD-Max).

4. Risultati

4.1. Risultati Teorici

• Convergenza: Al tendere della tolleranza di rilassamento $\epsilon \to 0$, la posterior approssimata converge alla posteriore esatta sul manifold.
• Dominanza delle Politiche Improprie: In presenza di politiche improprie, un prior Gaussiano combinato con una verosimiglianza rilassata può portare a una posterior in cui la massa è "allungata" lungo le direzioni corrispondenti a politiche improprie, potenzialmente influenzando negativamente la selezione delle azioni ottimali. Questo effetto viene mitigato utilizzando $\epsilon$ più piccoli o utilizzando prior che penalizzano esplicitamente le politiche improprie.

4.2. Esperimenti Numerici

Gli esperimenti sono stati condotti su varianti del benchmark Deep Sea (ambienti standard, pyramid e swirl):

• Efficienza dei Dati: Il framework proposto (Bayes-BR) ha dimostrato una superiorità nell'efficienza dei dati rispetto ai metodi bayesiani basati su TD, in particolare quando la tolleranza di rilassamento $\epsilon$ era piccola (ad esempio, 0.01).
• Convergenza: La probabilità a posteriori della politica ottimale è convergente rapidamente a 1 nell'ambiente Deep Sea standard (8 episodi per profondità-3).
• Molti Ottimi: Nella variante "Deep Sea Pyramid" con molteplici politiche ottimali, la posterior ha distribuito correttamente la massa equamente tra tutte le politiche ottimali.
• Politiche Improprie: Nella variante "Deep Sea Swirl" (che contiene politiche improprie), il framework è riuscito a recuperare la classe di politiche ottime nonostante il rischio teorico di dominanza delle politiche improprie, a condizione che $\epsilon$ fosse sufficientemente piccolo.
• Sfide di Campionamento: Lo studio ha notato che l'algoritmo standard Hamiltonian Monte Carlo (HMC) ha avuto difficoltà a campionare efficacemente dalla posterior rilassata quando $\epsilon$ era molto piccolo (0.01), evidenziando la difficoltà di campionare vicino al manifold anche con il rilassamento.

5. Significato e Rivendicazioni

Il documento sostiene che il suo framework quantifica fedelmente l'incertezza nel contesto SSP senza fare affidamento sulle "ipotesi di modellazione irrealistiche" o sulle "approssimazioni ad hoc" presenti in molti lavori esistenti di RL Bayesiano (che spesso derivano dagli aggiornamenti del Q-learning).

• Fedeltà: Derivando la verosimiglianza dalle BOE, la distribuzione a posteriori risultante è teoricamente fondata sulle condizioni di ottimalità dell'MDP.
• Approfondimento sulle Approssimazioni: Il lavoro fornisce un'analisi matematica critica del passaggio di "rilassamento" spesso usato in pratica. Rivela che, sebbene il rilassamento permetta un'inferenza trattabile, esso altera fondamentalmente la geometria della posterior, portando potenzialmente alla selezione di politiche improprie se non gestito con cura.
• Benchmarking: Gli autori forniscono un nuovo benchmark per confrontare i metodi di RL Bayesiano, dimostrando che il loro approccio è più efficiente in termini di dati rispetto alle metodologie concorrenti basate su TD nel contesto SSP.

Il documento conclude con modestia, riconoscendo che, sebbene il framework sia robusto, è necessario ulteriore lavoro per progettare prior che escludano esplicitamente le politiche improprie e per sviluppare metodi di campionamento più sofisticati per gestire le sfide poste dai valori di $\epsilon$ molto piccoli.