Interval Markov Decision Processes with Continuous Action-Spaces

1. Il Problema

I Processi Decisionali di Markov a Intervalli (IMDP) sono modelli Markoviani a stati finiti in cui le probabilità di transizione non sono valori fissi, ma appartengono a intervalli noti. Sono ampiamente utilizzati per la sintesi di controlli robusti in sistemi stocastici incerti.

Tuttavia, la maggior parte degli algoritmi esistenti per gli IMDP assume che lo spazio delle azioni sia discreto. Nelle applicazioni di controllo reali, le azioni sono spesso continue (es. velocità, forze, angoli). Le attuali strategie per gestire spazi continui si basano su:

1. Discretizzazione dello spazio delle azioni: Questo porta a una complessità computazionale che scala esponenzialmente con la dimensionalità del problema, rendendo i problemi ad alta dimensionalità intrattabili.
2. Euristiche: Metodi che risolvono i problemi di ottimizzazione senza garantire ottimalità o fornire limiti di sub-ottimalità.

Il paper affronta la mancanza di algoritmi computazionali per gli IMDP con spazi di azione continui, proponendo un approccio che evita la discretizzazione arbitraria e garantisce l'ottimalità.

2. Metodologia e Contributi Chiave

Gli autori introducono i caIMDP (continuous-action IMDP), una generalizzazione in cui i limiti inferiori e superiori delle probabilità di transizione sono funzioni delle variabili di azione continue.

A. Formulazione del Problema di Controllo Robusto

L'obiettivo è sintetizzare una politica che massimizzi il reward cumulativo atteso pessimistico (il caso peggiore). Questo si traduce in un problema di ottimizzazione max-min:
$$\max_{\pi} \min_{\xi} \mathbb{E} \left[ \sum \gamma^i R(q_i) \right]$$
dove $\pi$ è la politica (controllore) e $\xi$ è l'avversario (che risolve l'incertezza delle probabilità di transizione).

B. Decomposizione del Problema Max-Min

Il contributo teorico principale risiede nella decomposizione del problema di Value Iteration (iterazione del valore).
Invece di risolvere direttamente il complesso problema max-min per ogni stato, gli autori dimostrano (Teorema 3.2) che il problema può essere scomposto in $|Q|$ problemi di massimizzazione più semplici (dove $|Q|$ è il numero di stati), indicati come (MP).

Il processo funziona come segue:

1. Si utilizza la dualità per trasformare il problema min (interno) in un problema di massimizzazione.
2. Si sfrutta la struttura specifica dei vincoli per decomporre il problema in $|Q|$ sottoproblemi, ciascuno dei quali massimizza una funzione lineare rispetto alle probabilità di transizione, ordinando i valori della funzione di valore.
3. Questo riduce la complessità da un problema max-min non convesso a una serie di problemi di massimizzazione pura.

C. Casi di Risolvibilità Efficiente

Analizzando la forma dei problemi di massimizzazione (MP), gli autori identificano tre casi in cui il problema diventa trattabile (risolvibile in modo efficiente):

1. Caso Lineare: Se lo spazio delle azioni $A$ è un poliedro e i limiti di transizione sono funzioni lineari delle azioni.

   • Risultato: I problemi (MP) diventano Programmi Lineari (LP).
   • Insight: L'azione ottima si trova sempre sui vertici del poliedro $A$. Quindi, è sufficiente risolvere il problema su un IMDP a azioni discrete con azioni pari ai soli vertici di $A$.

2. Caso Concavo/Convesso: Se $A$ è convesso, il limite inferiore è concavo e il limite superiore è convesso rispetto all'azione.

   • Risultato: I problemi (MP) diventano Programmi Convessi (CP), risolvibili efficientemente con algoritmi standard.

3. Caso Convesso/Concavo: Se $A$ è un poliedro, il limite inferiore è convesso e il limite superiore è concavo.

   • Risultato: Si tratta di massimizzare una funzione convessa su un poliedro. La soluzione ottima si trova nuovamente sui vertici del poliedro, permettendo di ridurre il problema a un'enumerazione sui vertici (simile al caso lineare).

3. Risultati Sperimentali

Gli autori hanno validato la teoria su un esempio numerico:

• Setup: Un caIMDP con 25 stati e uno spazio di azioni continuo tridimensionale (un cilindro).
• Confronto: Hanno confrontato la sintesi su caIMDP (risolta tramite programmazione convessa) con la sintesi su IMDP a azioni discrete (ottenute campionando casualmente $s$ punti dallo spazio continuo).
• Risultati:
  • La politica ottenuta dal caIMDP ha fornito il reward ottimo ($R^*$).
  • Le politiche discrete sono risultate sub-ottimali. Anche con 125 punti di campionamento (5 per dimensione), l'errore di sub-ottimalità era significativo (~4.32%).
  • Efficienza Computazionale: Il tempo di calcolo per il caIMDP è stato paragonabile a quello richiesto per un IMDP discreto con solo 27 azioni (3 punti per dimensione), ma con un reward nettamente superiore.
  • Questo dimostra che l'approccio caIMDP non solo garantisce l'ottimalità, ma è anche computazionalmente efficiente rispetto alla discretizzazione brutale.

4. Significato e Applicazioni

A. Sintesi di Controllo per Sistemi Stocastici

Il paper discute come utilizzare i caIMDP come astrazioni per sistemi stocastici continui (es. $x_{k+1} = f(x_k, a_k, w_k)$).

• Lo spazio degli stati continui viene partizionato in insiemi discreti.
• I limiti di transizione del caIMDP sono calcolati come infimum e supremum delle probabilità di transizione del sistema originale su questi insiemi.
• Questo permette di derivare politiche per il sistema originale con garanzie formali.

B. Limiti di Sub-ottimalità

Gli autori mostrano come calcolare un limite superiore al reward ottimo del sistema reale (usando una funzione di reward opposta, $\sup$ invece di $\inf$). La differenza tra il reward ottimo del caIMDP (caso pessimistico) e quello del caso ottimistico fornisce un limite di sub-ottimalità sulla politica sintetizzata. Se il limite è troppo ampio, l'astrazione può essere raffinata.

Conclusione

Questo lavoro colma un vuoto significativo nella teoria del controllo robusto. Dimostra che, sfruttando la struttura matematica degli IMDP, è possibile gestire spazi di azione continui senza discretizzazione, trasformando problemi complessi in programmi lineari o convessi. I risultati offrono un metodo scalabile e garantito per la sintesi di controlli in sistemi stocastici incerti ad alta dimensionalità, superando le limitazioni delle attuali tecniche basate su discretizzazione o euristiche.