Multi-Environment POMDPs with Finite-Horizon Objectives

Sintesi Tecnica: MEPOMDP con Obiettivi a Orizzonte Finito

Enunciato del Problema
Questo lavoro affronta il problema del calcolo di valori e politiche ottimali nei Processi Decisionali di Markov Parzialmente Osservabili Multi-Ambiente (MEPOMDP) con obiettivi a orizzonte finito. In un Processo Decisionale di Markov Parzialmente Osservabile (POMDP) standard, un agente interagisce con un ambiente stocastico ricevendo solo informazioni parziali sullo stato. Un MEPOMDP estende questo modello assumendo che lo stato iniziale sia sconosciuto e scelto in modo avversario da un insieme di $n$ possibili stati iniziali $\{s_1, \dots, s_n\}$. L'agente deve calcolare una singola politica che massimizzi il reward atteso minimo su tutti i possibili ambienti iniziali. L'obiettivo è massimizzare la somma dei reward su un orizzonte finito $k$.

Il lavoro si concentra su due problemi computazionali:

1. Il Problema del Valore: Calcolare il valore ottimo $v = \sup_{\sigma} \min_{i \in [n]} E^k_{s_i}(\sigma)$.
2. Il Problema della Soglia: Decidere se $v \ge \lambda$ per una data soglia razionale $\lambda$.

Una sottigliezza teorica critica identificata è che, a differenza dei POMDP standard dove le politiche deterministiche sono sufficienti per l'ottimalità, i MEPOMDP richiedono generalmente politiche randomizzate per raggiungere il valore ottimo, poiché le strategie deterministiche potrebbero non soddisfare il vincolo dello stato iniziale nel caso peggiore.

Metodologia e Algoritmi
Gli autori sviluppano sia limiti di complessità teorica sia algoritmi pratici per risolvere questi problemi.

• Analisi della Complessità: Il lavoro stabilisce che il problema della soglia e la sua versione approssimata sono PSPACE-completi. Il limite inferiore è ereditato dalla nota PSPACE-durezza dei POMDP standard (dove $n=1$). Il limite superiore è dimostrato tramite un algoritmo non deterministico che sfrutta il teorema di Carathéodory. Questo teorema implica che, se esiste una politica che raggiunge un certo valore su $n$ ambienti, esiste una "miscela" di al più $n$ politiche deterministiche che garantisce lo stesso risultato. Ciò permette di ridurre lo spazio di ricerca alle combinazioni di un numero limitato di strategie deterministiche.

• Algoritmo Deterministico a Spazio Efficiente (Algoritmo 2): Per evitare i requisiti di spazio esponenziale della determinizzazione standard (ad esempio tramite il teorema di Savitch), gli autori presentano un algoritmo deterministico che opera entro uno spazio polinomiale. Invece di indovinare intere politiche, l'algoritmo enumera possibili valori di payoff multi-attesi e ne verifica la raggiungibilità in modo ricorsivo. Costruisce somme parziali dell'equazione di aggiornamento di Bellman, verificando se un valore target può essere decomposto in sotto-strategie valide. Sebbene teoricamente ottimale in termini di spazio ($O(|S| \cdot |O| \cdot n \cdot k \cdot \pi(N))$), gli autori notano che questo approccio è computazionalmente non fattibile per la maggior parte delle istanze pratiche a causa di cicli annidati.

• Algoritmo Pratico a Tempo Efficiente (Algoritmo 3): Per la valutazione empirica, gli autori propongono un algoritmo bottom-up che calcola l'insieme dei payoff multi-attesi raggiungibili per orizzonti crescenti. Questo metodo mantiene un insieme di vettori di payoff non dominati (la "frontiera"). Ad ogni passo, pota i vettori che sono convessamente dominati da altri, poiché questi corrispondono a famiglie di politiche che non necessitano di ulteriore esplorazione. Sebbene questo algoritmo possa utilizzare spazio esponenziale nel caso peggiore, è progettato per la scalabilità nella pratica.

Contributi Chiave

1. Classificazione della Complessità: Il lavoro dimostra che il calcolo dei valori nei MEPOMDP con orizzonti finiti è PSPACE-completo, corrispondendo alla complessità dei POMDP standard nonostante il vincolo aggiuntivo dello stato iniziale avversario.
2. Insight Teorico: Dimostra che le politiche ottimali nei MEPOMDP possono essere rappresentate come miscele di al più $n$ politiche deterministiche, dove $n$ è il numero di ambienti iniziali.
3. Avanzamenti Algoritmici:
   • Un algoritmo deterministico a spazio polinomiale (Algoritmo 2) che fornisce un limite superiore teorico sulla complessità spaziale.
   • Un algoritmo pratico a tempo efficiente (Algoritmo 3) che utilizza la potatura dei vettori di payoff dominati.
4. Validazione Empirica: L'algoritmo pratico è stato valutato contro l'unico algoritmo esatto precedentemente noto (di Bovy et al. [1]) su tre suite di benchmark: Rock Sample, Robot Navigation e Identification (Friend or Foe).

Risultati
I risultati sperimentali indicano che l'algoritmo pratico proposto (Algoritmo 3) supera significativamente lo strumento all'avanguardia di [1].

• Prestazioni: Il nuovo metodo risolve istanze con fino a 574 stati e orizzonti fino a $k=7$ entro tempi ragionevoli, mentre lo strumento di base va frequentemente in timeout (limite di 3600s) su istanze molto più piccole.
• Scalabilità: Il tempo di calcolo scala fortemente con l'orizzonte $k$, che è identificato come il principale collo di bottiglia per la scalabilità. Il numero di stati e di ambienti iniziali ha un effetto meno dominante sul tempo di esecuzione rispetto all'orizzonte.
• Confronto: Nei benchmark Rock Sample, il metodo proposto ha risolto istanze in cui lo strumento di base andava in timeout, raggiungendo spesso accelerazioni di diversi ordini di grandezza (ad esempio, risolvendo un'istanza da 574 stati in ~784 secondi contro un timeout per lo strumento di base).

Significato e Limitazioni
Il lavoro rivendica importanza nel fornire i primi limiti di complessità stretti per i MEPOMDP e nell'offrire un algoritmo pratico che migliora sostanzialmente gli strumenti esistenti. Gli autori riconoscono un compromesso standard tra prestazioni teoriche e pratiche: l'algoritmo a spazio efficiente (Algoritmo 2) è teoricamente solido ma praticamente lento, mentre l'algoritmo a tempo efficiente (Algoritmo 3) è veloce nella pratica ma manca di una garanzia di spazio polinomiale nel caso peggiore.

Il lavoro è limitato agli obiettivi a orizzonte finito. Gli autori notano che, sebbene il problema esatto per gli obiettivi a somma scontata sia indecidibile per i POMDP, il loro algoritmo potrebbe potenzialmente essere adattato per obiettivi scontati approssimati riducendoli a problemi a orizzonte finito, sebbene ciò rimanga lavoro futuro. Il lavoro non propone nuove applicazioni oltre ai benchmark standard utilizzati per la valutazione.