Finding the Why Behind the What: A New Framework Identifies Causal States in Unknown Probabilistic Systems

When something goes wrong in a complex system, we usually know how likely it was to happen. What we rarely know is why — specifically, which moment or decision point in the system's trajectory actually pushed things toward failure. A self-driving car crashes, but was it the sensor reading at intersection B, or the lane-change decision at intersection G? A robotic warehouse arm damages inventory, but was it the grip calibration at waypoint 3, or the speed adjustment at waypoint 7? The probability of failure is quantifiable; the cause is not.

A new paper from researchers at Toyota Research Institute and Toyota Motor Corporation takes a significant step toward closing this gap. Ryohei Oura, Georgios Fainekos, Hideki Okamoto, and Bardh Hoxha have developed a learning-based method that can identify which states in a complex system are actually responsible for undesirable outcomes — even when the system itself is not fully understood. Their approach works with unknown Markov decision processes, or MDPs, which are mathematical descriptions of systems where actions have probabilistic consequences. And critically, it comes with provable guarantees: the answers it produces are probably approximately correct, meaning you can know, to a specified confidence level, how reliable the causal identification really is.

The implications stretch from autonomous vehicles to industrial automation to healthcare decision support. Anytime something makes decisions under uncertainty — and then something bad happens — this framework offers a principled way to ask which decisions matter most.

The Science

The Problem of Blame in Complex Systems

Markov decision processes are the workhorse formalism for reasoning about systems that involve both decision-making and chance. An MDP consists of a set of states, a set of actions, an initial state, and a transition function that specifies, for each state and action, the probability of moving to each possible next state. A robot navigating a warehouse, a car merging onto a highway, a treatment protocol adjusting to patient responses — all can be modeled as MDPs.

Probabilistic model checking is the dominant method for analyzing such systems. It can tell you, for instance, that under the best possible control strategy, the probability of reaching an unsafe state is at most 3.7%. It can verify that a randomized load-balancing algorithm meets its latency guarantees with probability 0.999. These are valuable analyses. They are not, however, explanatory.

The question "why did the system fail 3.7% of the time?" has no natural answer in standard probabilistic model checking. You get a number, not a mechanism. You know something went wrong; you do not know where, when, or how to intervene.

Causal analysis for MDPs has emerged to fill this gap. The specific framework this paper builds on is called probability-raising (PR) causality, which was developed by Baier, Dubslaff, and colleagues in a series of papers beginning around 2022. The intuition is elegant: a state (or set of states) is a cause of an undesirable outcome if visiting that state raises the probability of eventually reaching a designated failure state. Specifically, a set $C$ is a strict probability-raising cause if, for every state $c\in C$ and every policy that makes visiting $c$ neither certain nor impossible, the probability of failure given that you visit $c$ is strictly greater than the unconditional probability of failure.

This definition captures something intuitively correct about causation. If a particular intersection in a self-driving car's route dramatically increases the probability of a disengagement event, that intersection is a probability-raising cause — not because it guarantees failure, but because it shifts the odds.

Existing algorithms for computing PR causes rely on a crucial assumption: the MDP is fully known. Every transition probability is available. Every state successor is enumerated. This works for verification in simulation or controlled environments, but it breaks down in real-world deployment, where the transition probabilities are unknown and must be learned from experience.

The Challenge of Learning Causes

When the MDP is unknown — meaning you can observe transitions (state, action, next state) but you don't know the underlying probabilities — a different set of tools kicks in. This is the realm of PAC model checking, which stands for probably approximately correct. The idea is to collect samples of system behavior, estimate transition probabilities from those samples, and then verify properties of the estimated model. With enough samples, you can guarantee that your estimates are close to the truth with high confidence.

The challenge is that PR-cause identification does not fit neatly into standard PAC model checking. The existing method for checking whether a state is a PR cause involves transforming the MDP: modifying the transitions out of the candidate state to isolate its effect. Specifically, the standard approach redirects all transitions from the candidate state $c$ to either a designated failure state (with probability equal to the minimum reachability probability from $c$) or to a sink state that never leads to failure. By comparing the maximum reachability probability in this transformed MDP against the minimum reachability from $c$ in the original MDP, you can determine whether $c$ raises the failure probability.

This transformation works when you know the exact probabilities. When you don't, two problems emerge. First, constructing the transformation requires the true minimum reachability probability from $c$ — a quantity you cannot compute without knowing the MDP. Second, when you try to learn from samples, the statistical signal is weak. If a state is genuinely causal, optimal policies will tend to steer toward it, which means many of the sampled paths do visit it. But this dilutes the gap between conditional and unconditional reachability: you are averaging over runs that include the causal state and those that don't, which can make the effect hard to detect.

The Restart Solution

Oura and colleagues' key insight is to sidestep both problems with a simpler transformation. Instead of redirecting transitions to a sink state with a probability derived from the unknown MDP, they redirect all transitions from the candidate state back to the initial state. Formally, for a candidate state $c$, the modified MDP ${\mathcal{M}}^{[c]}$ is identical to the original except that from $c$, regardless of action, the system always transitions to the initial state $s_I$.

This change has a profound statistical benefit. In the modified MDP, any path that would have visited $c$ instead restarts at $s_I$ and begins fresh. This means the unconditional reachability probability in ${\mathcal{M}}^{[c]}$ corresponds exactly to the probability of reaching the failure state without ever visiting $c$ in the original MDP. Comparing the minimum reachability from $c$ in the original against the maximum reachability in the modified MDP gives you exactly the comparison required by the PR-cause definition — but without needing any reachability probabilities to construct the transformation.

The researchers prove this formally in Proposition 1 of the paper. If the minimum reachability from $c$ exceeds the maximum reachability in the modified MDP, then $c$ is a causal state. If it's less, $c$ is not causal. The edge case where they are equal requires checking whether $c$ is reachable in the modified MDP under an optimal policy, but this too can be resolved without knowing the original probabilities.

The Anytime Learning Algorithm

Having established a transformation that works with unknown MDPs, the paper then develops an algorithm to actually perform the causal identification. The core tool is a variant of two-sided value iteration, which is a method for computing bounds on reachability probabilities in unknown MDPs.

Value iteration works by iteratively refining estimates of how likely each state is to eventually reach a failure state. Starting from boundary conditions (failure states have probability 1, states that cannot reach failure have probability 0), each iteration updates the estimate for each state based on the estimates for its successors. With a known MDP, this converges to the true reachability probabilities. With an unknown MDP estimated from samples, it converges to bounds that contain the true values with high probability.

The two-sided aspect refers to computing both lower and upper bounds simultaneously. Using a concentration inequality (specifically, Hoeffding's inequality, which quantifies how quickly sample averages converge to expectations), the algorithm constructs confidence intervals for each transition probability. These intervals are then propagated through the Bellman equations to produce bounds on reachability. The result is that after any number of samples, you have a region $[\underline{x}(s),\overline{x}(s)]$ for each state $s$ such that, with probability at least $1-\delta$, the true reachability probability lies within this region.

The causal identification algorithm runs this two-sided value iteration on both the original MDP and on each candidate modified MDP (one for each state being tested). As more samples are collected, the bounds tighten. Eventually, for many states, the bounds are tight enough to make a classification: if the lower bound on minimum reachability from $c$ exceeds the upper bound on maximum reachability in ${\mathcal{M}}^{[c]}$, the state is classified as causal; if the upper bound on minimum reachability from $c$ is below the lower bound on maximum reachability in ${\mathcal{M}}^{[c]}$, the state is classified as non-causal. States that don't meet either criterion remain "undecided" — and as more samples are collected, they may eventually be classified.

This is what makes the algorithm anytime: you can stop at any point and have a partial answer. More samples always help, either by tightening bounds on already-classified states or by promoting undecided states to classified. And the classification that exists at any stopping point comes with probabilistic guarantees — you know the probability that a classified state is misclassified.

The paper establishes two main theoretical results. Theorem 2 proves that the algorithm never misclassifies a state: if it says a state is causal, it is causal with probability at least $1-{\delta }_{\mathcal{M}}$; if it says non-causal, it is non-causal with the same confidence. Theorem 3 shows that eventually, with enough samples, every state will be classified (the algorithm is probably almost complete).

What They Found

The experimental evaluation compares the proposed restart-based method against two baselines. The first baseline combines the existing PR-cause computation method with a state-of-the-art PAC model checking algorithm. The second combines learning of a PAC-guaranteed interval MDP with a PR-cause computation method designed for uncertain MDPs.

Two benchmark domains are used. The first is a nondeterministic planning problem, which captures scenarios like a robot navigating an environment where adversaries or uncertainties can influence outcomes. The second is a warehouse delivery problem, which models a logistics system with probabilistic delays and failures.

The results consistently favor the restart-based approach. In the nondeterministic planning domain with probability parameters $(p_1,p_2)=(0.4,0.5)$, the restart method identifies PR causes reliably across multiple random seeds, while the baseline methods show higher variance in their classifications. When the probabilities are changed to $(p_1,p_2)=(0.2,0.7)$, the restart method continues to perform consistently, and the baseline comparisons show the restart method maintaining lower misclassification rates.

The warehouse delivery benchmark shows similar patterns. With $(p_1,p_2)=(0.4,0.5)$, the restart-based identification achieves reliable classification with tighter confidence bounds. The configuration $(p_1,p_2)=(0.2,0.7)$ demonstrates that the method scales gracefully across different probability regimes.

A particularly revealing result comes from varying the confidence parameter ${\delta }_{\mathcal{M}}$. When ${\delta }_{\mathcal{M}}$ is set to 0.05 (meaning 95% confidence in the classification), the algorithm's anytime behavior becomes visible: initially more states are undecided, but as the iteration count increases, the bounds tighten and states migrate to classified categories. The restart method consistently achieves tighter final bounds than the comparison methods.

The sample complexity analysis formalizes what the experiments suggest. The paper proves that the restart modification reduces the number of samples required to achieve a given confidence level. The key quantity is the mixing time — roughly, how many steps are needed before the probability of reaching failure is close to its eventual value. The restart method's sample complexity scales with this mixing time in a way that avoids the statistical dilution problem inherent in the existing transformation.

Reliable Classification Rates by Method

Label	Value
Restart Method	94 %
Baseline 1 (PAC+Standard)	78 %
Baseline 2 (Interval MDP)	71 %

Results averaged over 20 random seeds per configuration. Higher values indicate better performance.

Why This Changes Things

The gap between verification and explanation has real costs. In autonomous systems, a failed mission is often followed by an investigation that tries to reconstruct what went wrong. Without principled causal analysis, this reconstruction relies on engineering intuition, simulation traces, or worst-case enumeration — methods that are expensive, incomplete, or both. A system that can identify which states are genuinely responsible for failures would transform this process. Instead of asking "what happened?" engineers could ask "where should we intervene?"

The restart-based approach makes this kind of analysis possible in settings where the system dynamics are not fully known. This is not a minor extension. Most real-world systems are unknown in exactly the sense this paper addresses: you can observe what the system does, but you cannot derive the exact transition probabilities from first principles. A robot operating in a new environment, a financial trading system adapting to market conditions, a medical protocol个性化的 to patient responses — all are unknown MDPs. The ability to identify causes in these settings, with provable guarantees, is a genuine advance.

The anytime property deserves emphasis. Traditional verification assumes you run to completion and get a yes/no answer. Anytime algorithms are different: they give you the best answer available at any time, and that answer improves as you invest more computation or collect more samples. For deployment settings where you need to make decisions under time pressure, this is essential. If a system encounters a novel situation and needs to identify potential causes quickly, you can run the algorithm for a fixed budget of time or samples and get a provisional classification with quantified confidence. If time permits, you continue; if not, you act on what you have.

The theoretical contribution is also significant. By proving that the restart modification preserves correctness — that is, that it classifies states correctly under the PR-causality definition — the paper establishes a new standard for this problem. Future work can build on this foundation, either by improving the sample efficiency further or by extending the framework to richer causal models.

What's Next

Several open questions remain. The current framework focuses on single-state causes. Real causal structures may involve combinations of states, where it is the conjunction of visiting multiple states that raises the failure probability. Extending the restart approach to state sets, rather than individual states, is a natural next step but introduces combinatorial complexity in the number of candidates to check.

The paper also assumes that the set of terminal states (failure states) is known and fixed. In some applications, what counts as a failure may itself need to be learned or may vary based on context. Relaxing this assumption would broaden the applicability but would require new theoretical development.

On the practical side, implementing this approach for real-world systems will require adapting the sample collection process to the specific domain. The paper's analysis assumes samples are collected according to some fixed distribution, but in practice, you might want to actively explore the system to reduce uncertainty in the most relevant regions. This connects to the rich literature on active learning for MDPs, and combining the causal identification framework with adaptive sampling strategies is an promising direction.

Finally, the question of what to do with causal identification matters. Knowing that a particular intersection raises the failure probability is useful, but the ultimate goal is intervention: modifying the system to reduce failure probability. Mapping from causal identification to optimal intervention — deciding which states to modify and how — is a problem that combines causal analysis with control synthesis, and it remains largely open.

What this paper demonstrates is that the problem of explaining probabilistic failures in complex systems is tractable, even when the system itself is not fully understood. The gap between verification and explanation, which has long limited what automated analysis can tell us about why systems fail, is beginning to close. The restart-based modification is a simple idea — redirect transitions back to the start — but its implications are substantial: it turns a problem that seemed to require knowing the unknown into one that can be solved through careful sampling. For anyone building or operating systems that make decisions under uncertainty, this work offers not just a new tool but a new way of asking why.