From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

Sintesi Tecnica: Identificabilità dei Kernel di Transizione in MDP Scontati

Enunciato del Problema
Questo articolo investiga il problema inverso del recupero delle probabilità di transizione di un processo decisionale di Markov (MDP) finito e scontato, data solo l'insieme delle azioni ottimali per ogni funzione di ricompensa all'interno di una specifica classe. Sebbene il modello di transizione determini sia la politica ottimale che la dinamica dell'ambiente, due diversi kernel di transizione possono raccomandare azioni ottime identiche. La questione centrale è: in quali condizioni due kernel $P$ e $Q$ diventano indistinguibili basandosi esclusivamente sulle azioni ottime che inducono.

Lo studio confronta tre classi distinte di ricompense, che testano le dinamiche in modi differenti:

1. Ricompense di stato: $r(s)$, dipendenti solo dallo stato corrente.
2. Ricompense stato-azione: $r(s, a)$, dipendenti dallo stato e dall'azione correnti.
3. Ricompense dipendenti dalla transizione: $r(s, a, s')$, dipendenti dallo stato, dall'azione e dal successivo stato risultante.

Il documento definisce tre nozioni di equivalenza: $P \equiv_{tr} Q$ (indistinguibili sotto ricompense di transizione), $P \equiv_{sa} Q$ (indistinguibili sotto ricompense stato-azione) e $P \equiv_{s} Q$ (indistinguibili sotto ricompense di stato).

Metodologia
L'analisi si basa sulle proprietà strutturali delle equazioni di ottimalità di Bellman e sulla relazione tra le funzioni di valore e i kernel di transizione.

• Ricompense Stato-Azione: L'autore costruisce una specifica famiglia di ricompense, $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$, che rende ogni azione ottimale per un dato vettore di valore $v$. Confrontando le equazioni di valutazione della politica sotto i kernel $P$ e $Q$ per queste ricompense, l'articolo deriva una condizione necessaria e sufficiente per l'equivalenza. Ciò comporta l'identificazione di una matrice invertibile unica $L$ che mette in relazione i valori delle funzioni dei due kernel.
• Ricompense Dipendenti dalla Transizione: La metodologia sfrutta la capacità di isolare specifiche righe di transizione. Se uno stato ha più azioni, una ricompensa dipendente dalla transizione può essere progettata per avere un valore atteso nullo sotto una riga di transizione e non nullo sotto un'altra, distinguendoli efficacemente. Per gli stati con una singola azione, l'analisi si basa sul fatto che la specifica riga di transizione influenzi l'ottimalità delle azioni in altri stati.
• Ricompense di Stato: L'analisi caratterizza l'equivalenza esaminando le "regioni di policy" $R_P(\pi)$, definite come l'insieme delle ricompense di stato per cui una politica deterministica $\pi$ è ottimale. Due kernel sono equivalenti se e solo se queste regioni sono identiche per tutte le politiche deterministiche.

Risultati Chiave

1. Equivalenza Stato-Azione ($P \equiv_{sa} Q$):
   Due kernel $P$ e $Q$ producono le stesse azioni ottime per ogni ricompensa stato-azione se e solo se esiste una matrice invertibile unica $L$ (che soddisfa $L\mathbf{1} = \mathbf{1}$) tale che:
   $$Q_{s,a} = \left( P_{s,a} + \frac{1}{\gamma} e_s^T (L - I) \right) L^{-1}$$
   Ciò implica che il vantaggio di qualsiasi azione rispetto a una politica è preservato sotto la trasformazione. Vicino a un kernel con voci strettamente positive, l'insieme dei kernel indistinguibili forma una varietà (manifold) liscia di dimensione $n(n-1)$, dove $n$ è il numero di stati. Questo è un sottoinsieme stretto dello spazio ambiente dei kernel, il che significa che, sebbene il kernel di transizione non sia determinato univocamente, l'ambiguità è vincolata a una specifica famiglia a dimensione inferiore. Il risultato è valido anche se i dati sono limitati a ricompense con un'azione univoca per ogni stato.

2. Equivalenza Dipendente dalla Transizione ($P \equiv_{tr} Q$):
   Le ricompense dipendenti dalla transizione forniscono molte più informazioni.

   • In qualsiasi stato con almeno due azioni, la riga di transizione è identificata univocamente.
   • Negli stati con una singola azione, la riga è identificata a meno che la specifica probabilità di transizione non influenzi l'ottimalità delle azioni in altri stati (una condizione che si verifica solo per un insieme di misura zero di kernel strettamente positivi).
   • Di conseguenza, se l'MDP contiene almeno uno stato con una scelta genuina (molteplici azioni), quasi ogni kernel di transizione strettamente positivo è identificato univocamente dalle ricompense dipendenti dalla transizione.

3. Equivalenza di Ricompensa di Stato ($P \equiv_{s} Q$):
   Le ricompense di stato forniscono il minor numero di informazioni. Due kernel sono equivalenti se e solo se condividono lo stesso insieme di politiche deterministiche ottime per ogni ricompensa di stato. Questa condizione è equivalente all'uguaglianza delle regioni di policy $R_P(\pi) = R_Q(\pi)$ per ogni $\pi$. Questa equivalenza è strettamente più debole dell'equivalenza stato-azione; kernel distinti possono essere indistinguibili sotto ricompense di stato pur essendo distinguibili sotto ricompense stato-azione.

4. Gerarchia di Identificabilità:
   Il documento stabilisce una gerarchia di equivalenza stretta:
   $$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$$
   Nessuna delle implicazioni è reversibile. Consentire alla ricompensa di dipendere da più componenti della transizione (specificamente dallo stato successivo) aumenta rigorosamente la capacità di distinguere tra diversi modelli di transizione.

Significato e Rivendicazioni
Il documento sostiene di aver risolto la questione di quanto della dinamica di transizione possa essere recuperata solo dalla condotta ottimale. Dimostra che:

• Le azioni ottime sono insufficienti per il recupero completo: Anche con la conoscenza delle azioni ottime per tutte le ricompense, il kernel di transizione generalmente non è determinato univocamente quando le ricompense dipendono solo dagli stati o dagli stati-azioni.
• Esistono vincoli strutturali: Per le ricompense stato-azione, l'ambiguità non è arbitraria; è precisamente caratterizzata da una trasformazione matriciale che preserva i confronti tra azioni (vantaggi) attraverso tutte le politiche.
• La struttura della ricompensa determina la recuperabilità: La forma della ricompensa è critica. Le ricompense dipendenti dalla transizione possono recuperare quasi interamente il kernel, mentre le ricompense di stato possono lasciare nascoste differenze strutturali sostanziali.
• Distinzione tra decisione e predizione: I risultati evidenziano come un modello possa essere sufficiente per riprodurre decisioni ottime (riproduzione della policy) senza essere sufficiente per predire le transizioni, simulare controfattuali o trasferirsi a classi di ricompense non viste.

Il lavoro estende la letteratura precedente (es. Letcher et al.) spostando l'attenzione dal recupero dei kernel da valori Q numerici al recupero degli stessi dall'insieme discreto di azioni ottime, ampliando contemporaneamente l'ambito della classe di ricompense considerata. Il documento conclude che, sebbene le azioni ottime rivelino una struttura significativa della dinamica, esse non rivelano generalmente la dinamica stessa, a meno che la funzione di ricompensa non sia sufficientemente ricca (ovvero, dipenda dallo stato successivo).