Robust Counterfactuals for Markov Decision Processes under Statistical and Causal Uncertainties
Counterfactual reasoning in Markov Decision Processes is complicated by two distinct sources of uncertainty: statistical uncertainty in transition probabilities estimated from finite data, and causal uncertainty arising from multiple compatible structural causal models. This paper introduces a framework for partial counterfactual inference that addresses both simultaneously by deriving closed-form probability bounds for Interval MDPs and computing minimal robust interventions via pessimistic value iteration. The approach is motivated by safety-critical applications like sepsis treatment, where explanations and interventions must remain valid across all plausible models entailed by the data.
This paper makes a strong theoretical and algorithmic contribution by unifying statistical and causal uncertainty in MDP counterfactual inference for the first time. The derivation of closed-form bounds avoids an otherwise exponential optimization, and the resulting minimal robust intervention framework is both provably sound and empirically scalable. Experiments across GridWorld, Frozen Lake, Sepsis, and Aircraft tasks demonstrate that data-driven bounds converge to exact ones with increasing data and that the resulting policies outperform Gumbel-max baselines under worst-case evaluation.
The analytical characterization of counterfactual bounds for IMDPs is the central strength. As the authors note, without it, computing robust counterfactual probabilities entails solving an optimization with a number of constraints exponential in the size of the MDP. The confidence propagation result cleanly lifts the IMDP coverage guarantee to the CFIMDP, and the empirical off-policy evaluation confirms unbiased convergence: the data-driven bounds consistently contain the true expected return and tighten toward the exact bounds as $N$ increases.
The framework assumes a grey-box setting where the MDP topology is known, which limits applicability to truly black-box domains. A more fundamental conservatism arises because the CFIMDP bounds each transition separately, meaning the worst-case is taken over a superset of CFMDPs that may combine probabilities induced by different causal models and are not jointly realizable: as the authors acknowledge, this yields conservative but efficiently computable guarantees. Finally, the conservative closed-form lower bounds in Cases 1 and 3 of Theorem B.7 are not tight, and while experiments suggest the practical impact is small, interventions derived from them may require more action changes than strictly necessary.
The evidence generally supports the claims. The off-policy evaluation shows data-driven bounds bracket the true interventional value, and Figure 2 demonstrates that pessimistic values closely track the exact CFIMDP across environments. The comparison to Gumbel-max is revealing: because it commits to a specific causal model, its policies perform substantially worse under adversarial selection from the exact CFIMDP, supporting the argument that causal robustness matters. The comparison between conservative and tight lower bounds further shows that the conservative approach is preferable in practice, affecting at most 4.4% of transitions with negligible width changes.
Reproducibility is moderately strong: the authors provide code at a public GitHub repository and specify hyperparameters including the Clopper-Pearson confidence level with evenly distributed alpha, a minimum probability epsilon, and trajectory counts. The value iteration algorithm is detailed in Appendix E and builds on the Julia IntervalMDP package. However, independent reproduction could be hindered by the grey-box topology assumption, the need for specific simulator details for the Sepsis and Aircraft benchmarks, and the computational cost of tight lower bounds, which require solving nested optimizations and are orders of magnitude slower than the conservative version in larger environments.
Counterfactual reasoning (asking what would have happened, had a decision been different) is a powerful tool for identifying causes of failure and explaining the behaviour of AI systems in sequential decision-making tasks. In Markov Decision Processes (MDPs), two sources of uncertainty complicate counterfactual inference: statistical uncertainty in the MDP transitions when the MDP is estimated from trajectory data, and uncertainty about the unknown causal model, as there are multiple structural causal models (SCMs) compatible with each MDP. Existing work addresses these two challenges in isolation. We address both simultaneously by introducing a framework for partial counterfactual inference in MDPs that is robust to both statistical and causal uncertainty. Our approach provides: 1) closed-form analytical bounds for the counterfactual probabilities that are valid across all SCMs entailed by a given interval MDP (IMDP); 2) a method to compute minimal robust interventions to achieve a desired counterfactual outcome via pessimistic value iteration on the induced counterfactual IMDP. Since the latter is constructed using our analytical bounds, our approach remains efficient and scalable to realistic MDP environments. Experiments across multiple case studies demonstrate our method's robustness and practical utility for identifying minimal sets of actions that, if changed, would have led to improved outcomes.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.