Robust Counterfactual Inference in Markov Decision Processes

Deze paper introduceert een schaalbaar, niet-parametrisch kader voor robuuste contrafactuele inferentie in Markov-beslissingsprocessen dat, in plaats van te vertrouwen op één specifiek causaal model, gesloten formules gebruikt om nauwkeurige grenzen te berekenen voor contrafactuele overgangskansen en zo robuuste beleidsplannen garandeert die het worst-case scenario optimaliseren.

De kern

De Kern: "Wat als?" in een onzekere wereld

Stel je voor dat je een recept voor een taart hebt gevolgd, maar de taart is een beetje mislukt. Je vraagt je af: "Wat als ik een ander type bloem had gebruikt? Was de taart dan wel gelukt?"

In de wereld van kunstmatige intelligentie (AI) en robots noemen we dit counterfactual inference (tegenfeitelijk redeneren). Het is het vermogen om te zeggen: "Als we in het verleden een andere beslissing hadden genomen, wat was er dan gebeurd?"

Dit is superbelangrijk in veilige gebieden zoals zorg of luchtverkeer. Je kunt een nieuwe behandelingsmethode of een nieuw vliegsysteem niet zomaar testen op echte patiënten of vliegtuigen als je niet zeker weet of het veilig is. Je wilt eerst "in de computer" weten wat er gebeurt.

Het Probleem: De "Gok" met de waarheid

Het probleem is dat we vaak niet precies weten hoe de wereld werkt. We hebben alleen data van wat er gebeurd is.
Stel je voor dat je een spookhuis binnenloopt. Je ziet dat de deur open ging toen je op de knop drukte. Maar je weet niet zeker waarom:

1. Was het toeval?
2. Was er een onzichtbare geest die de deur open duwde?
3. Was het een mechanisch systeem dat alleen werkt op dinsdag?

In de wetenschap noemen we dit de causale structuur. Bestaande methoden doen alsof ze weten hoe het spookhuis werkt (bijvoorbeeld: "Het is altijd een geest"). Ze maken dan een simpele voorspelling: "Als je op de knop had gedrukt terwijl de deur dicht was, was hij open gegaan."

Maar wat als het geen geest was, maar een mechanisch systeem? Dan is hun voorspelling misschien helemaal fout. Als je in het echt een nieuwe beslissing neemt op basis van die verkeerde voorspelling, kan het misgaan.

De Oplossing: De "Veilige Omheining"

De auteurs van dit paper zeggen: "Wacht even, we weten niet welke 'geest' het is. Laten we niet gokken op één antwoord, maar laten we alle mogelijke antwoorden bekijken."

Hun nieuwe methode doet het volgende:

1. Geen gokken, maar grenzen: In plaats van één getal te geven (bijv. "80% kans op succes"), geven ze een bereik (bijv. "Tussen de 40% en 90%").
2. De "Slechtste Geval" Strategie: Ze bouwen een Interval MDP. Denk hierbij aan een veilige omheining rondom alle mogelijke werelden. Ze zeggen: "Zelfs als de wereld werkt op de allerergste manier die nog mogelijk is binnen onze data, is deze nieuwe strategie nog steeds veilig en goed."
3. Snelheid: Vroeger moest de computer een enorme, ingewikkelde puzzel oplossen om deze grenzen te vinden (zoals het zoeken naar een naald in een hooiberg). De auteurs hebben een wiskundige formule gevonden die dit direct berekent. Het is alsof ze een magische sleutel hebben die de deur direct opent, in plaats van te boren.

De Vergelijking: De Weervoorspeller

Laten we het vergelijken met weer:

• De oude methode (Gumbel-max): De voorspeller zegt: "Morgen is het 100% zeker regen." Hij heeft een specifiek model van de lucht gebruikt. Als het model fout is, ben je nat.
• De nieuwe methode (Robuust): De voorspeller zegt: "Morgen kan het regenen, maar het kan ook droog zijn. De kans ligt ergens tussen 10% en 90%."
  • Omdat ze niet zeker zijn, adviseren ze je om zowel een paraplu als een zonnebril mee te nemen.
  • Zo ben je voorbereid op elk scenario dat binnen de mogelijke grenzen valt. Je bent "robuust" tegen verrassingen.

Wat hebben ze bewezen?

Ze hebben hun methode getest op verschillende situaties, zoals:

• Een robot die door een labyrint moet (GridWorld).
• Een arts die een patiënt met sepsis moet behandelen.
• Een vliegtuig dat een botsing moet voorkomen.

De resultaten:

1. Veiliger: Hun strategieën faalden veel minder vaak als de werkelijkheid anders bleek dan verwacht. Ze waren "veerkrachtiger".
2. Sneller: Omdat ze de snelle wiskundige formule gebruiken, is hun methode 4 tot 251 keer sneller dan de oude methoden. Dat betekent dat je dit ook kunt toepassen op grote, complexe systemen.

Conclusie in één zin

In plaats van te gokken op één verhaal over hoe de wereld werkt, bouwen deze onderzoekers een veiligheidsnet dat alle mogelijke verhalen omvat, zodat je beslissingen kunt nemen die altijd goed werken, ongeacht welke "geest" er in het spookhuis zit.

Technische samenvatting

Probleemstelling

Bestaande methoden voor contrafactuele inferentie (het beantwoorden van de vraag "wat zou er gebeurd zijn als...") in Markov Beslissingsprocessen (MDP's) lijden onder een fundamenteel probleem: niet-identificeerbaarheid.

• Om contrafactuele kansen te berekenen, nemen deze methoden doorgaans een specifiek causaal model aan (bijvoorbeeld het Gumbel-max Structureel Causaal Model of SCM).
• Echter, gegeven een waarneming en een MDP, zijn er vaak vele causale modellen die consistent zijn met de geobserveerde en interventionele data, maar die elk leiden tot verschillende contrafactuele kansen.
• Het vertrouwen op één enkel model (zoals Gumbel-max) kan leiden tot onnauwkeurige inferenties, wat vooral riskant is in veiligheidskritieke domeinen zoals gezondheidszorg.
• Bestaande methoden voor "partiele contrafactuele inferentie" (die grenzen berekenen in plaats van exacte waarden) zijn vaak te inefficiënt. Ze vereisen het oplossen van enorme optimalisatieproblemen waarvan het aantal constraints exponentieel groeit met de grootte van de MDP, waardoor ze onpraktisch zijn voor grootschalige toepassingen.

Methodologie

De auteurs stellen een niet-parametrische aanpak voor die gebruikmaakt van korte, analytische grenzen (closed-form bounds) voor contrafactuele transitiekansen. De kern van de methode bestaat uit de volgende stappen:

1. Canonieke SCM Formulering:
   De MDP wordt gemodelleerd als een canoniek Structureel Causaal Model (SCM). Hierbij wordt de exogene variabele $U_t$ voor elke tijdstap geïnterpreteerd als een index voor een unieke structurele vergelijking die alle mogelijke state-action paren $(s, a)$ deterministisch afbeeldt op de volgende staat $s'$.

2. Optimalisatie naar Analytische Oplossing:
   In plaats van een lineair optimalisatieprobleem op te lossen (zoals voorgesteld door Zhang et al.), bewijzen de auteurs dat in een Markoviaanse setting (zonder verborgen confounders) dit probleem reduceert tot exacte analytische formules.
   De grenzen voor de contrafactuele kans $\tilde{P}_t(\tilde{s}' | \tilde{s}, \tilde{a})$ hangen af van de relatie tussen het geobserveerde state-action paar $(s_t, a_t)$ en het contrafactuele paar $(\tilde{s}, \tilde{a})$:

   • Gelijk aan geobserveerd: De kans is exact 1 voor de geobserveerde uitkomst en 0 voor andere.
   • Disjuncte steun (Disjoint support): Als de steun van het contrafactuele paar geen overlap heeft met het geobserveerde paar, worden de grenzen berekend op basis van de verhouding van de nominale kansen.
   • Overlappende steun: Als er overlap is, worden de grenzen bepaald door de minimale en maximale mogelijke overdrachten onder de gegeven constraints.

3. Incorporatie van Redelijke Aannames:
   Om de grenzen informatief te maken (en te voorkomen dat ze triviaal zijn, d.w.z. [0, 1]), introduceren de auteurs twee aannames die als constraints aan het optimalisatieproblema worden toegevoegd:

   • Contrafactuele Stabiliteit (Counterfactual Stability): Als de relatieve waarschijnlijkheid van een uitkomst onder een contrafactuele situatie niet toeneemt ten opzichte van de geobserveerde uitkomst, dan mag de uitkomst niet veranderen.
   • Contrafactuele Monotonie (Counterfactual Monotonicity): Als een uitkomst niet werd waargenomen (maar wel mogelijk was), mag de kans hierop in de contrafactuele wereld niet toenemen. Als een uitkomst wel werd waargenomen, mag de kans erop niet afnemen.

4. Interval Contrafactuele MDP (ICFMDP) en Robuste Policy:
   Met deze analytische grenzen construeren de auteurs een Interval Contrafactuele MDP, waarbij elke transitie een interval van kansen heeft $[P^{LB}, P^{UB}]$.
   Om een robuuste policy te vinden, wordt pessimistische waarde-iteratie (robust value iteration) toegepast. Deze methode optimaliseert de verwachte beloning voor het slechtst mogelijke geval binnen de interval-MDP, wat resulteert in een policy die robuust is tegen onzekerheid in het onderliggende causale model.

Belangrijkste Bijdragen

1. Analytische Grenzen: Het bewijs dat het complexe optimalisatieprobleem voor partiele contrafactuele inferentie in MDP's reduceert tot exacte, gesloten-formule oplossingen. Dit elimineert de noodzaak voor zware numerieke optimalisatie.
2. Efficiëntie: De methode is aanzienlijk sneller dan bestaande benaderingen (zoals Gumbel-max SCM) omdat deze geen steekproeven vereist, maar directe berekeningen uitvoert.
3. Robuuste Policy Learning: Het introduceren van een framework om policies te leren die optimaal presteren onder de slechtst mogelijke causale modellen die consistent zijn met de data, in plaats van te vertrouwen op één specifiek model.
4. Validatie van Aannames: Het tonen aan dat de aannames van stabiliteit en monotonie de grenzen versterken zonder de bruikbaarheid te beperken, en dat de methode modulair is (de aannames kunnen worden verwijderd indien nodig).

Resultaten

De methode werd geëvalueerd op vier verschillende omgevingen: GridWorld, Frozen Lake, Sepsis (klinische besluitvorming) en Aircraft (veiligheidskritieke besturing).

• Snelheid: De analytische aanpak is 4 tot 251 keer sneller dan de Gumbel-max SCM methode, die afhankelijk is van steekproeven uit een Gumbel-verdeling.
• Robuustheid: In vergelijking met policies die zijn afgeleid van het Gumbel-max model, presteren de policies van de auteurs (ICFMDP) significant beter in het slechtst mogelijke geval (worst-case scenario).
  • Bijvoorbeeld, in de Sepsis-en omgeving behaalde de ICFMDP-policy een gemiddelde pessimistische waarde ($V(s_0)$) van 1660, terwijl de Gumbel-policy een negatieve waarde van -85.4 had.
  • De ICFMDP-policies vertonen minder variatie en zijn minder gevoelig voor de onzekerheid van het causale model.
• Kwaliteit van Grenzen: De toegevoegde aannames (stabiliteit en monotonie) verkleinen de breedte van de kansen-intervallen slechts marginaal (gemiddeld minder dan 0.1), maar elimineren wel onlogische contrafactuele scenario's (zoals in het voorbeeld in Figuur 3 van het paper).

Significantie

Dit werk is van groot belang voor de toepassing van Reinforcement Learning (RL) in veiligheidskritieke domeinen (zoals gezondheidszorg en autonome systemen).

• Het biedt een manier om beleid te evalueren en te verbeteren zonder het risico van directe deployering in de echte wereld (offline policy evaluation).
• Door rekening te houden met de onzekerheid over het ware causale model, biedt de methode garanties voor de prestaties van een agent. Dit is cruciaal wanneer fouten hoge kosten kunnen hebben.
• De schaalbaarheid door de analytische grenzen maakt het mogelijk om contrafactuele inferentie toe te passen op grootschalige MDP's, wat eerder onhaalbaar was door de computationele complexiteit van bestaande methoden.

Kortom, de auteurs leveren een wiskundig onderbouwde, efficiënte en robuuste oplossing voor het probleem van onzekerheid in contrafactuele redenering binnen sequentiële besluitvorming.