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

Technische Samenvatting: Identificeerbaarheid van Transitiekernen in Gereduceerde MDP's

Probleemstelling
Dit artikel onderzoekt het inverse probleem van het terugvinden van de transitiekansen van een eindige, gedisconteerde Markov Beslissingsproces (MDP), gegeven uitsluitend de verzameling optimale acties voor elke mogelijke beloningsfunctie binnen een specifieke klasse. Hoewel het transitiemodel zowel het optimale beleid als de dynamiek van de omgeving bepaalt, kunnen twee verschillende transitiekernen identieke optimale acties aanbevelen. De centrale vraag is: onder welke condities zijn twee kernen $P$ en $Q$ ononderscheidbaar op basis van enkel de door hen geïnduceerde optimale acties?

De studie vergelijkt drie verschillende klassen beloningen, die de dynamiek op verschillende manieren testen:

1. Toestandsbeloningen: $r(s)$, afhankelijk van alleen de huidige toestand.
2. Toestand-actie beloningen: $r(s, a)$, afhankelijk van de huidige toestand en actie.
3. Transitie-afhankelijke beloningen: $r(s, a, s')$, afhankelijk van de toestand, de actie en de resulterende volgende toestand.

Het artikel definieert drie begrippen van equivalentie: $P \equiv_{tr} Q$ (ononderscheidbaar onder transitiebeloningen), $P \equiv_{sa} Q$ (ononderscheidbaar onder toestand-actie beloningen), en $P \equiv_{s} Q$ (ononderscheidbaar onder toestandsbeloningen).

Methodologie
De analyse steunt op de structurele eigenschappen van de Bellman-optimaliteitsvergelijkingen en de relatie tussen waardefuncties en transitiekernen.

• Toestand-actie Beloningen: De auteur construeert een specifieke familie van beloningen, $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$, die elke actie optimaal maken voor een gegeven waardevector $v$. Door de belejsevaluatievergelijkingen onder kernen $P$ en $Q$ voor deze beloningen te vergelijken, leidt het artikel een noodzakelijke en voldoende voorwaarde voor equivalentie af. Dit omvat het identificeren van een unieke inverteerbare matrix $L$ die de waardefuncties van de twee kernen met elkaar verbindt.
• Transitie-afhankelijke Beloningen: De methodologie maakt gebruik van het vermogen om specifieke transitierijen te isoleren. Als een toestand meerdere acties heeft, kan een transitie-afhankelijke beloning worden ontworpen die een verwachte waarde van nul heeft onder één transitierij en een niet-nul waarde onder een andere, waardoor ze effectief onderscheiden worden. Voor toestanden met een enkele actie rust de analyse op de vraag of de specifieke transitierij de optimaliteit van acties elders in de toestandsruimte beïnvloedt.
• Toestandsbeloningen: De analyse karakteriseert equivalentie door het onderzoeken van de "beleidsregio's" $R_P(\pi)$, gedefinieerd als de verzameling toestandsbeloningen waarvoor een deterministisch beleid $\pi$ optimaal is. Twee kernen zijn equivalent als en slechts als deze regio's identiek zijn voor alle deterministische beleidsregels.

Belangrijkste Resultaten

1. Toestand-actie Equivalentie ($P \equiv_{sa} Q$):
   Twee kernen $P$ en $Q$ leveren voor elke toestand-actie beloning dezelfde optimale acties op indien en slechts indien er een unieke inverteerbare matrix $L$ bestaat (voldoende aan $L\mathbf{1} = \mathbf{1}$) zodanig dat:
   $$Q_{s,a} = \left( P_{s,a} + \frac{1}{\gamma} e_s^T (L - I) \right) L^{-1}$$
   Dit impliceert dat het voordeel van elke actie ten opzichte van een beleid behouden blijft onder de transformatie. Nabij een kern met strikt positieve entiteiten vormt de verzameling ononderscheidbare kernen een gladde variëteit van dimensie $n(n-1)$, waarbij $n$ het aantal toestanden is. Dit is een strikte deelverzameling van de omringende kernruimte, wat betekent dat hoewel de transitiekerne niet uniek bepaald is, de ambiguïteit beperkt is tot een specifieke laagdimensionale familie. Het resultaat blijft geldig, zelfs als de data beperkt is tot beloningen met een unieke optimale actie bij elke toestand.

2. Transitie-afhankelijke Equivalentie ($P \equiv_{tr} Q$):
   Transitie-afhankelijke beloningen bieden aanzienlijk meer informatie.

   • Bij elke toestand met ten minste twee acties wordt de transitierij uniek geïdentificeerd.
   • Bij toestanden met een enkele actie wordt de rij geïdentificeerd, tenzij de specifieke transitiekansen nooit de optimaliteit van acties elders in de toestandsruimte beïnvloeden (een conditie die alleen geldt voor een maat nul verzameling van strikt positieve kernen).
   • Bijgevolg, als de MDP ten minste één toestand bevat met een echte keuze (meerdere acties), is bijna elke strikt positieve transitiekerne uniek geïdentificeerd door transitie-afhankelijke beloningen.

3. Toestandsbelonings Equivalentie ($P \equiv_{s} Q$):
   Toestandsbeloningen bieden de minste informatie. Twee kernen zijn equivalent indien en slechts indien zij dezelfde verzameling optimale deterministische beleidsregels delen voor elke toestandsbeloning. Deze conditie is equivalent aan de gelijkheid van de beleidsregio's $R_P(\pi) = R_Q(\pi)$ voor alle $\pi$. Deze equivalentie is strikt zwakker dan toestand-actie equivalentie; verschillende kernen kunnen ononderscheidbaar zijn onder toestandsbeloningen terwijl ze wel onderscheidbaar zijn onder toestand-actie beloningen.

4. Hiërarchie van Identificeerbaarheid:
   Het artikel stelt een strikte hiërarchie van equivalentie vast:
   $$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$$
   Geen van de implicaties is omkeerbaar. Het toestaan dat de beloning afhankelijk is van meer componenten van de transitie (specifiek de volgende toestand) vergroot strikt de capaciteit om tussen verschillende transitiemodellen te onderscheiden.

Betekenis en Claims
Het artikel beweert de vraag te hebben opgelost hoe groot het deel van de transitiedynamiek is dat kan worden teruggevonden uit optimaal gedrag alleen. Het demonstreert dat:

• Optimale acties onvoldoende zijn voor volledige reconstructie: Zelfs met kennis van de optimale acties voor alle beloningen, is de transitiekerne over het algemeen niet uniek bepaald wanneer beloningen enkel afhankelijk zijn van toestanden of toestand-acties.
• Structurele beperkingen bestaan: Voor toestand-actie beloningen is de ambiguïteit niet willekeurig; deze is precies gekarakteriseerd door een matrixtransformatie die actievergelijkingen (voordelen) over alle beleidsregels heen behoudt.
• De structuur van de beloning bepaalt de reproduceerbaarheid: De vorm van de beloning is cruciaal. Transitie-afhankelijke beloningen kunnen de kern bijna volledig herstellen, terwijl toestandsbeloningen aanzienlijke structurele verschillen verborgen kunnen laten.
• Onderscheid tussen besluitvorming en voorspelling: De resultaten benadrukken dat een model voldoende kan zijn voor het reproduceren van optimale beslissingen (beleidsreproductie), zonder voldoende te zijn voor het voorspellen van transities, het simuleren van contrafeitelijke scenario's of het overdragen naar ongeziene beloningsklassen.

Het werk breidt de eerdere literatuur (bijv. Letcher et al.) uit door de focus te verschuiven van het terugvinden van kernen uit numerieke Q-waarden naar het terugvinden ervan uit de discrete verzameling optimale acties, terwijl het tegelijkertijd de reikwijdte van de overwogen beloningsklasse vergroot. Het artikel concludeert dat hoewel optimale acties aanzienlijke informatie onthullen over de dynamiek, ze de dynamiek zelf niet algemeen onthullen, tenzij de beloningsfunctie voldoende rijk is (d.w.z. afhankelijk is van de volgende toestand).