Sub-optimality bounds for certainty equivalent policies in partially observed systems

Sintesi Tecnica: Limiti di sub-ottimalità per le politiche di equivalenza della certezza in sistemi a osservabilità parziale

Definizione del Problema

In molti domini come la robotica, i sistemi autonomi e la finanza, i decisori operano sotto osservabilità parziale, modellata come Processi Decisionali di Markov Parzialmente Osservabili (POMDP). Risolvere i POMDP in modo ottimale è computazionalmente intrattabile (PSPACE-hard), e trovare politiche approssimativamente ottimali è altrettanto difficile. Sebbene esistano metodi euristici, essi spesso mancano di garanzie di prestazione dimostrabili.

Il principio di Equivalenza della Certezza (CE), ben consolidato nel controllo Lineare-Quadratico-Gaussiano (LQG), suggerisce che l'azione ottimale per un sistema stocastico può essere ottenuta applicando la politica ottimale di feedback dello stato del corrispondente sistema deterministico alla stima dell'Errore Quadratico Medio Minimo (MMSE) dello stato. Tuttavia, per sistemi non lineari a osservabilità parziale generali, la politica CE (utilizzando qualsiasi stima dello stato) è generalmente non ottimale.

Il problema centrale affrontato in questo articolo è quantificare il grado di sub-ottimalità delle politiche di equivalenza della certezza nei POMDP generali. Nello specifico, gli autori cercano di derivare espliciti limiti superiori sul divario di prestazione tra una politica CE e la politica ottimale del POMDP, in particolare quando la dinamica del sistema e i costi sono regolari (smooth) e quando l'errore di stima dello stato è piccolo.

Metodologia

L'articolo generalizza il principio CE ad arbitrari POMDP e arbitrari stimatori di stato (non limitati al MMSE). La metodologia si basa sul framework dello Stato Informativo Approssimato (AIS).

1. Modellazione del Sistema:

   • Gli autori considerano un POMDP a tempo discreto $\mathcal{P}$ con spazio degli stati $\mathcal{S}$, spazio delle osservazioni $\mathcal{Y}$ e spazio delle azioni $\mathcal{A}$.
   • Definiscono un corrispondente Processo Decisionale di Markov (MDP) completamente osservabile $\mathcal{M}$ dove il controllore ha accesso al vero stato $S_t$.
   • Una Politica di Equivalenza della Certezza $\mu^E$ è definita come $\mu^E_t(h_t) = \pi^M_t(E_t(h_t))$, dove $\pi^M$ è la politica ottimale per l'MDP completamente osservabile $\mathcal{M}$, e $E_t$ è un arbitrario stimatore di stato che mappa la storia $h_t$ in una stima dello stato.

2. Astrazione dello Stato:

   • Per gestire sistemi su larga scala, il framework viene esteso all'Astrazione dello Stato. Viene introdotto uno spazio di stato astratto $\tilde{\mathcal{S}}$ tramite una funzione di astrazione $\phi: \mathcal{S} \to \tilde{\mathcal{S}}$.
   • Viene costruito un MDP astratto $\tilde{\mathcal{M}}$ con dinamiche e costi derivati dall'MDP originale tramite kernel stocastici $\lambda^P$ e $\lambda^c$.
   • La politica CE è quindi definita utilizzando la politica ottimale dell'MDP astratto $\tilde{\mathcal{M}}$ e le stime dello stato astratto.

3. Assunzioni di Regolarità (Smoothness):

   • L'analisi assume che la dinamica del sistema e i costi per passo siano "regolari" nel senso definito da funzioni concave e non decrescenti $F^P_t$ e $F^c_t$.
   • Nello specifico, la distanza Wasserstein-1 tra i kernel di transizione e la differenza nei costi sono limitate da queste funzioni della distanza tra gli stati (o stati astratti). Questo generalizza le standard assunzioni di continuità Lipschitziana.

4. Framework dello Stato Informativo Approssimato (AIS):

   • Gli autori utilizzano il framework AIS per limitare il divario di sub-ottimalità. Dimostrano che la terna composta dallo stimatore di stato, dalla funzione di costo astratta e dalla dinamica astratta forma un generatore $(\epsilon, \delta)$-AIS.
   • I parametri $\epsilon_t$ (errore di approssimazione del costo) e $\delta_t$ (errore di predizione della dinamica) sono derivati esplicitamente in termini del peggior caso dell'errore di stima condizionato atteso $\eta_t$.

Contributi Chiave

L'articolo apporta tre contributi primari:

1. Limiti Espliciti di Sub-ottimalità: Gli autori derivano espliciti limiti superiori sulla sub-ottimalità delle politiche di equivalenza della certezza. Questi limiti dipendono dalla "regolarità" del sistema (costanti Lipschitziane o funzioni generalizzate $F^P, F^c$) e dalla qualità dello stimatore di stato (misurata dal peggior caso dell'errore atteso di stima $\eta_t$).

   • Il limite è dato da $W^{\mathcal{P}, \mu^E}_t(h_t) - W^{\mathcal{P}}_t(h_t) \leq 2\alpha_t$, dove $\alpha_t$ è una funzione ricorsiva di $\epsilon_t$ e $\delta_t$.

2. Estensione all'Astrazione dello Stato: I risultati sono generalizzati a contesti che coinvolgono l'astrazione dello stato (quantizzazione o estrazione di feature). Ciò consente al framework di applicarsi a sistemi su larga scala dove il pieno stato è aggregato in uno stato astratto a minore dimensionalità. I limiti tengono conto degli errori derivanti sia dal processo di astrazione che dalla stima dello stato.

3. Esempi Illustrativi: L'articolo fornisce diversi esempi concreti che dimostrano l'applicabilità dei limiti derivati:

   • Rumore di Osservazione Limitato: Mostrando la scalabilità lineare del limite di sub-ottimalità con il raggio del rumore.
   • Osservazioni Intermittentemente Degradate: Gestendo scenari in cui le osservazioni sono occasionalmente scarse.
   • Quantizzazione dello Stato: Analizzando l'effetto combinato dell'errore di quantizzazione e del rumore di osservazione.
   • Apprendimento/Controllo Adattivo: Applicando i limiti a problemi di stima dei parametri in cui i parametri del sistema sono sconosciuti.
   • Comunicazione Innescata da Eventi (Event-Triggered): Analizzando sistemi di controllo in cui la comunicazione è attivata solo quando l'errore di stima supera una soglia.
   • Sistemi Multi-particella Non Omogenei: Applicando il framework a sistemi con una componente globale di campo medio e dinamiche locali delle particelle.

Risultati

Il principale risultato teorico (Teorema 2) stabilisce che se la dinamica del sistema e i costi soddisfano specifiche condizioni di regolarità (Assunzione 5) e lo stimatore ha un errore peggior caso limitato (Assunzione 6), il divario di prestazione tra la politica CE e la politica ottimale è limitato.

• Dipendenza dall'Errore di Stima: I limiti sono direttamente proporzionali all'errore di stima $\eta_t$. Quando $\eta_t \to 0$ (stima perfetta), il divario di sub-ottimalità svanisce.
• Dipendenza dalla Regolarità: L'entità del divario è scalata dalle costanti di tipo Lipschitz delle funzioni di dinamica e di costo.
• Astrazione dello Stato: Quando si utilizzano stati astratti, il limite include termini relativi all'errore di astrazione (la distanza tra il vero stato e la sua astrazione) oltre all'errore di stima.

Negli esempi illustrativi, gli autori mostrano che per sistemi con rumore limitato o osservazioni accurate frequenti, la politica CE raggiunge prestazioni quasi ottimali, fornendo un'alternativa computazionalmente trattabile alla risoluzione del pieno POMDP.

Significato e Rivendicazioni

L'articolo sostiene di fornire una generalizzazione del principio di equivalenza della certezza per i POMDP generali, andando oltre il setting restrittivo dell'LQG. La sua importanza risiede in:

• Giustificazione Teorica: Offre una base teorica rigorosa per l'uso di politiche CE in contesti non lineari e a osservabilità parziale, quantificando esattamente quanto possa essere "cattiva" la politica in base alla qualità della stima.
• Trattabilità Pratica: Suggerisce che in scenari in cui le soluzioni ottime dei POMDP sono computazionalmente intrattabili, le politiche CE offrono un'alternativa pratica. Se l'errore di stima dello stato è piccolo, queste politiche possono raggiungere prestazioni quasi ottimali senza la complessità esponenziale del dynamic programming basato sullo stato di credenza (belief-state).
• Framework Unificato: Incorporando l'astrazione dello stato, il framework colma il divario tra la teoria del controllo e la progettazione di sistemi su larga scala, permettendo l'analisi di strategie di controllo basate su quantizzazione o feature.

Gli autori notano esplicitamente che la loro analisi si basa sul framework AIS e sulle assunzioni di regolarità. Non pretendono che le politiche CE siano ottimali per tutti i modelli (notano ad esempio nel Remark 3 che le politiche CE possono fallire in modelli in cui è richiesto il sensing attivo per apprendere lo stato). I risultati sono presentati come limiti che caratterizzano il grado di sub-ottimalità piuttosto che come garanzie di ottimalità.