Certifying Actual Causes in Stochastic Systems Learned From Finite Rollouts

When an autopilot, robot controller, or other stochastic system fails, engineers want to know which earlier event actually caused the failure. In a random system the classic "it would not have happened otherwise" test does not work, because chance alone can produce the failure along another path. So the operative question becomes: did this event make the failure substantially more likely? Recent tools answer that question well, but only when the system's exact transition probabilities are handed to them. In practice those probabilities are estimated from a limited number of simulated or logged runs. This project asks what it costs, in data and in computation together, to certify a cause when the model itself is uncertain. It proposes a method that answers both costs with one mechanism.

The mechanism is state abstraction, meaning that many concrete states are merged into a few coarse ones. Abstraction is already used to make causal checking fast. Our observation is that it also pools data: merged states share their samples, so their estimated transition probabilities are less noisy. An abstraction that is too coarse cannot separate a true cause from a bystander. One that is too fine has too few samples per state to trust. We propose a refinement procedure that splits abstract states only where the statistical evidence is ambiguous, and stops splitting where a cell would have too few samples to support a verdict. For each candidate cause it returns one of three verdicts: certified, refuted, or undetermined at the current data budget. We pair the procedure with a sample-complexity analysis. The analysis separates what an unlimited-compute tester could conclude from the data from what the polynomial-time abstraction procedure can conclude.

Core Claim

Probabilistic actual causality is defined over discrete-time Markov chains (systems that move between states with fixed transition probabilities), following Fenton-Glynn's probability-raising notion. Efficient Discovery of Actual Causality in Stochastic Systems and Efficient Discovery of Actual Causality with Uncertainty check this property by encoding it as a constraint-satisfaction problem for a Satisfiability Modulo Theories (SMT) solver, and they accelerate the check with counterexample-guided abstraction refinement. Both assume the transition matrix is known exactly. Our claim is that, once the matrix is estimated from $N$ rollouts, abstraction refinement should be driven by confidence intervals rather than by reachability heuristics. Driving it this way gives sound causal verdicts with high probability and needs fewer rollouts than estimating the concrete chain and then checking.

The statistical target can be stated in one inequality. Let $\gamma$ be the probability-raising margin, defined as $P(\text{failure} \mid \text{candidate occurs}) - P(\text{failure} \mid \text{candidate removed})$. Let $H$ be the horizon and $M$ the number of candidate causes considered. A computationally unbounded tester then needs roughly

$$n_{\text{state}} \gtrsim \frac{H^2 \log(M/\delta)}{\gamma^2}$$

visits to each relevant state to get every verdict right with probability $1-\delta$. The bound follows from the simulation lemma: reachability error is at most $H$ times the per-state transition error. A union bound over the $M$ candidates contributes the $\log M$ term. Because $M$ enters only logarithmically, the statistical cost of searching over exponentially many candidate sets is small. The computational cost of that search is not small. The Computational Complexity of Structure-Based Causality shows that even deterministic singleton actual causality is $\Sigma^P_2$-complete in binary models. This is the familiar pattern behind statistical-computational gaps: the information is available, but finding the answer is hard. The same pattern appears in On the Efficiency of ERM in Feature Learning for best-subset search and in Globally optimal score-based learning of directed acyclic graphs in high-dimensions for DAG recovery at $\Omega(s \log p)$ samples.

The less obvious part of the claim runs the other way. In this setting the efficient algorithm can need fewer samples than the naive exact pipeline. Its requirement scales with the number of abstract states rather than concrete ones, provided the merged states have close transition probabilities. Pooling states whose probabilities differ introduces bias. We will make the resulting bias-variance trade-off explicit and measure it.

Research Program

The first component is the estimator. Rollouts give empirical transition counts. For each abstract state we form a simultaneous confidence region over its transition distribution. This turns the abstract model into an interval Markov chain, a chain whose transition probabilities are only known to lie in ranges. Probability raising is checked robustly. A candidate is certified if the margin exceeds zero for every chain consistent with the intervals. It is refuted if the margin falls below zero for every such chain. Otherwise it is undetermined. The existing SMT encodings already handle abstract models that are Markov decision processes, so interval constraints fit into them naturally.

The second component is the refinement rule. When a candidate is undetermined, we locate the abstract states whose interval width contributes most to the ambiguity in the margin. We split such a state only if each resulting piece would retain enough samples, judged against the bound above, to narrow the interval. If no split helps, the procedure either requests more rollouts targeted at the ambiguous states or reports "undetermined" as its final answer. This replaces the reachability-probability and action-count heuristics of Rafieioskouei et al. with a rule that accounts for both computation and data.

The third component is theory. We will prove two things. First, the procedure is sound with probability at least $1-\delta$: it never certifies a non-cause at that confidence level. Second, it uses a number of rollouts governed by the abstract state count, plus a bias term set by the transition heterogeneity inside merged cells. We will also try to prove that exact minimal-cause search remains hard when the model is known. A natural route is a reduction from the deterministic Halpern-Pearl case, since a chain with deterministic transitions is a special case of a Markov chain. If this succeeds, the gap is two-sided. It is a computational gap at fixed data and a statistical advantage from abstraction at fixed compute. Whether some polynomial-time method can match the unbounded tester's rollout count in the worst case is left as an explicit open question, framed in the same way Aragam et al. leave theirs open.

Baselines

The naive reference point is the plug-in pipeline. It estimates the concrete transition matrix by empirical frequencies, treats that estimate as exact, and runs the unmodified abstraction-refinement checker of Efficient Discovery of Actual Causality in Stochastic Systems. This is the most likely way practitioners use the existing tool today. Its failure mode is false attribution at small $N$, because noise in rarely visited states can make a bystander look like it raises probability. It also serves as the runtime reference. On the exact F-16 chain with over 13,800 states, Efficient Discovery of Actual Causality with Uncertainty reports concrete SMT taking over 633 seconds and abstraction refinement taking 1 second, with up to a 95% runtime reduction across benchmarks. Our method must stay within a small constant factor of that 1-second figure when given the exact model. It beats this baseline if it reaches lower false-certification rates at equal $N$, or equal accuracy at smaller $N$. We found no reported result on Lacuna for actual-cause recovery from estimated transitions on these benchmarks, so we will establish the baseline curves ourselves.

The strongest methodological competitor is Probability-Raising Causality for Uncertain Parametric Markov Decision Processes with PAC Guarantees. That paper samples concrete models from a parameter distribution, model-checks each one for strict probability-raising causes, and solves a set-cover problem across the samples, with PAC guarantees. We adapt it by treating the posterior over transitions given the rollouts as the parameter distribution. The comparison is fair if both methods receive the same rollouts, the same candidate set, the same confidence level $\delta$, and the same wall-clock budget. The number of posterior samples in Oura and Ito's method will be tuned over a grid of equal size to our refinement thresholds. Our method beats it if it attains equal or higher recall of true causes at equal soundness while using less compute on the larger benchmarks. That paper reports no isolated numerical runtime that we found on Lacuna.

The ablation that isolates our key ingredient is fixed-interval checking. It uses the same interval abstraction as our method but refines with the original reachability heuristics instead of the sample-aware rule. If this ablation matches the full method, the contribution reduces to "use confidence intervals," and the refinement rule adds nothing.

Why not just…?

Why not just estimate the chain with lots of data and use the existing checker? With enough rollouts the plug-in pipeline converges to the right answer. The question is how many rollouts that takes. Benchmarks such as the F-16 chain have thousands of states, many of them rarely visited. A per-concrete-state requirement then multiplies the bound above by the state count, and the plug-in pipeline gives no signal telling the user that the data are insufficient. The rollout-to-correct-verdict curves in our experiments measure this directly. If the plug-in pipeline reaches low error at budgets comparable to ours, our statistical claim fails and we will say so.

Why not just run interventions in the simulator and estimate probability raising directly? When a resettable simulator exists, Monte Carlo estimation of each candidate's margin is simple and model-free. This is a real threat. Its cost grows linearly in the number of candidates, because each candidate needs its own interventional rollouts, whereas a learned model lets all candidates share the same data. Logged data with no reset capability rules the approach out entirely. Our experiments include this baseline at matched rollout counts. We expect it to win when only a few candidates are evaluated and to lose as $M$ grows. The candidate count at which the two curves cross is itself a result we will report.

Why not just use the uncertain-parametric approach of Oura and Ito? Treating estimation uncertainty as parameter uncertainty is principled, and it already comes with PAC guarantees. However, its per-sample model checking and set covering work over the full state space, and the authors acknowledge that this cost is substantial for large models. Our method keeps data uncertainty inside a single interval abstraction. The head-to-head comparison on Lunar Lander and F-16 under equal budgets will show whether that difference matters in practice.

Proposed Experiments

We use the three chains from Rafieioskouei et al.: Mountain Car with a Deep Q-Network controller, Lunar Lander with a Proximal Policy Optimization controller, and the F-16 autopilot. Because their exact transition matrices are available, we can compute ground-truth causes once with the exact checker. We then hide the matrix and give each method $N$ rollouts sampled from the chain, sweeping $N$ over several orders of magnitude. We measure false-certification rate, recall of true causes, fraction of candidates left undetermined, rollouts needed to resolve 90% of candidates, and wall-clock time.

The decisive checks are threefold. First, the empirical false-certification rate must stay below $\delta$ at every $N$. If it does not, soundness fails and the method is unusable. Second, the rollout requirement should track the abstract state count rather than the concrete one. We test this by varying the concrete resolution of Mountain Car while holding its dynamics fixed: our curve should stay flat while the plug-in curve rises. Third, a controlled heterogeneity experiment inserts states whose transitions differ but which the initial abstraction merges. This tests whether the refinement rule detects the resulting bias rather than certifying through it.

A secondary experiment moves to the Sepsis Treatment Simulator used by Robust Counterfactual Policy Optimisation via Nondeterministic Causal Models. That paper reports actual return gains of 7.4 ± 10.7 on diabetic trajectories and 5.0 ± 7.4 on non-diabetic trajectories for its confounding-robust policy. The secondary experiment asks whether our three-valued verdicts for treatment-caused deterioration stay sound when a hidden confounder, diabetes status, is present. We expect the method to flag such cases as undetermined rather than certify them, and we report this as a stress test, not a headline result.