Toward Learning POMDPs Beyond Full-Rank Actions and State Observability

Sintesi Tecnica: Verso l'apprendimento di POMDP oltre le azioni a pieno rango e l'osservabilità dello stato

Definizione del problema
Il documento affronta la sfida di abilitare agenti autonomi a apprendere e ragionare su sistemi con stati nascosti, modellandoli come processi decisionali di Markov parzialmente osservabili (POMDP) discreti. L'agente riceve lo spazio delle azioni e delle osservazioni ma manca della conoscenza a priori dello spazio degli stati, della dinamica delle transizioni o dei modelli di osservazione. L'obiettivo è stimare il numero di stati nascosti e le esplicite matrici di transizione e osservazione da una sequenza di azioni e osservazioni raccolte tramite esplorazione casuale.

Sebbene i metodi spettrali come le Rappresentazioni di Stato Predittivo (PSR) possano apprendere statistiche sufficienti per predire risultati futuri, essi funzionano come modelli "black-box". Non forniscono esplicite probabilità di transizione e osservazione, rendendo difficile manipolare il modello per nuovi compiti di pianificazione (ad esempio, cambiando le funzioni di ricompensa) senza riapprendere l'intero sistema. Al contrario, gli esistenti metodi di decomposizione tensoriale per il recupero di modelli POMDP completi si basano solitamente su ipotesi rigide: che le matrici di transizione siano a pieno rango e che ogni stato abbia una distribuzione di osservazione unica per ogni azione. Queste ipotesi falliscono in molti scenari del mondo reale che coinvolgono l'aliasing degli stati (dove stati distinti condividono distribuzioni di osservazione identiche) o azioni che possono fallire probabilisticamente.

Metodologia
Gli autori propongono un metodo che combina la decomposizione spettrale con la decomposizione tensoriale per apprendere i parametri dei POMDP sotto ipotesi più blande. L'approccio procede in tre fasi principali:

1. Costruzione della matrice di Hankel e apprendimento della PSR:
   Il metodo inizia costruendo una matrice di Hankel dalle traiettorie osservate di azione-osservazione. Questa matrice codifica le probabilità congiunte di osservazioni passate e future. Eseguendo una fattorizzazione di rango (tramite SVD) su questa matrice, l'algoritmo deriva una Rappresentazione di Stato Predittivo (PSR) lineare. Ciò produce un insieme di matrici di aggiornamento lineare ($M_{ao}$), un vettore iniziale ($m_0$) e un vettore finale ($m_\infty$). Questi componenti rappresentano la dinamica del sistema fino a una trasformazione di similitudine ignota $P$.

2. Recupero della trasformazione di similitudine:
   Per recuperare le matrici esplicite di transizione ($T^a$) e osservazione ($O_{ao}$), l'algoritmo deve stimare la trasformazione di similitudine $P$. Gli autori riformulano le tecniche di decomposizione tensoriale per stimare $P$.

• In primo luogo, marginalizzano le osservazioni per ottenere le matrici di transizione fino alla trasformazione: $\sum_o M_{ao} = P T^a P^{-1}$.
• Per le azioni con matrici di transizione a pieno rango, calcolano il prodotto $M_{ao} M_a^{-1} = P O_{ao} P^{-1}$.
• Poiché le $O_{ao}$ sono diagonali, gli autovalori di questi prodotti corrispondono alle voci diagonali. Per risolvere l'ambiguità causata da autovalori ripetuti (che si verificano quando gli stati condividono distribuzioni di osservazione), il metodo impiega una diagonalizzazione congiunta di una somma pesata di queste matrici. I pesi casuali sono campionati per garantire che gli autovalori siano distinti quasi certamente per gli stati con distribuzioni di osservazione uniche attraverso tutte le azioni a pieno rango.

3. Apprendimento fino alle partizioni di osservabilità:
   Il documento introduce il concetto di Partizione di Osservabilità a Pieno Rango. Se più stati condividono l'esatta stessa distribuzione di osservazione per tutte le azioni con transizioni a pieno rango, non possono essere distinti dai soli dati sequenziali. L'algoritmo recupera la trasformazione di similitudine $P$ fino a questa partizione. Di conseguenza, il modello appreso fornisce matrici di transizione e osservazione esplicite tra partizioni di stati piuttosto che tra singoli stati. Per gli stati all'interno di una singola partizione, il modello apprende la dinamica aggregata.

Contributi Chiave

• Ipotesi Rilassate: Il metodo estende gli approcci di decomposizione tensoriale per apprendere POMDP in cui gli stati possono essere aliati (condividendo distribuzioni di osservazione) e dove le matrici di transizione non sono necessariamente a pieno rango per ogni azione, a condizione che il prodotto delle matrici forward e backward sia a pieno rango.
• Recupero Esplicito del Modello: A differenza delle PSR, il metodo recupera esplicite matrici di transizione e osservazione (fino a una partizione), consentendo la specifica di nuove funzioni di ricompensa e obiettivi dopo la fase iniziale di apprendimento senza dover riaddestrare il sistema.
• Limiti Teorici: Gli autori dimostrano che apprendere le dinamiche di transizione e osservazione oltre la partizione di osservabilità è impossibile da una singola traiettoria di dati sequenziali. Costruiscono un controesempio che dimostra come due POMDP distinti con dinamiche interne differenti possano produrre identiche distribuzioni di osservazione per tutte le sequenze di azioni, stabilendo il limite teorico di identificabilità.

Risultati Sperimentali
Gli autori valutano il loro metodo su diversi domini, tra cui il dominio "Sense-Float-Reset" (caratterizzato da aliasing degli stati), il problema della Tigre e il T-Maze.

• Convergenza: Il metodo recupera con successo i modelli di osservazione sottostanti e le matrici di transizione a livello di partizione, convergendo ai valori reali all'aumentare degli scambi di esplorazione. Al contrario, l'Expectation-Maximization (EM) spesso converge a minimi locali che predicono correttamente le osservazioni ma producono parametri di modello errati.
• Prestazioni di Pianificazione: Quando utilizzato con un pianificatore standard (PO-UCT), i POMDP a livello di partizione appresi raggiungono prestazioni di pianificazione comparabili ai modelli reali e alle PSR.
• Specificazione della Ricompensa: In nuovi domini "Noisy Hallway" e "Directional Hallway", gli autori dimostrano che le esplicite probabilità di transizione e osservazione permettono a un agente di essere diretto verso stati latenti specifici (ad esempio, uno stato di corridoio centrale con osservazioni ambigue) assegnando ricompense agli stati piuttosto che solo alle coppie azione-osservazione. Questa capacità non è disponibile con le PSR standard o i modelli basati su EM che falliscono nel recuperare la corretta struttura degli stati.

Significato e Rivendicazioni
Il documento sostiene che il proprio metodo colma il divario tra il potere predittivo delle PSR e l'interpretabilità dei modelli POMDP espliciti. Apprendendo fino a una partizione di osservabilità, il metodo cattura una classe più ampia di sistemi del mondo reale (particolarmente nella manipolazione robotica dove le azioni possono fallire o gli stati possono essere aliati) rispetto ai precedenti metodi basati su tensori.

Gli autori affermano con modestia che, sebbene il loro metodo non possa recuperare l'esatta struttura interna degli stati aliati dai dati sequenziali, esso recupera la massima quantità di informazioni teoricamente possibile. La capacità di manipolare il modello appreso per nuovi compiti (tramite la specifica esplicita della ricompensa) è evidenziata come un vantaggio primario rispetto ai modelli predittivi black-box. Il lavoro suggerisce che per molte applicazioni pratiche, l'apprendimento della dinamica tra le partizioni di osservabilità è sufficiente per una pianificazione ed un ragionamento efficaci.