Formal Quality Measures for Predictors in Markov Decision Processes

Christel Baier, Sascha Klüppelholz, Jakob Piribauer, Robin ZiemekAAAI 2025 · DOI

Introduction

In the design of complex, adaptive AI systems, anticipating failures before they occur is a critical safety requirement. We often identify specific "predictor" states—such as a particular sensor reading or a network delay—that we suspect serve as "red flags" for an impending failure. However, quantifying the quality of these predictors is notoriously difficult in non-deterministic environments.

Traditional statistical measures like precision and recall are designed for static datasets where outcomes are fixed. In a Markov Decision Process (MDP), the system's behavior is dynamic and depends on a "policy" (the strategy the system follows). A specific state might be an excellent predictor under one strategy but a poor one under another. This paper introduces a formal framework to evaluate predictor quality by accounting for the entire space of possible system behaviors.

Formalizing Predictor Quality in MDPs

To bridge the gap between static classification and dynamic systems, the authors adapt the standard confusion matrix to the world of MDPs. They define events based on temporal logic: let $C$ be the "cause" (the predictor state) and $E$ be the "effect" (the failure state). A "True Positive" in this context is the probability that the system reaches the predictor state and subsequently reaches the failure state.

The formal adaptation of the confusion matrix for MDPs, defining metrics like True Positives and False Negatives as reachability probabilities.

By defining these terms formally, the authors can derive MDP-specific versions of precision, recall, and the F-score. Because these values depend on the chosen policy $\mathfrak{S}$, the framework treats them as functions over the policy space rather than single scalar values.

Methodology: Averaging and Causal Volume

The paper proposes two primary methods for measuring the robustness of a predictor:

  1. Averaging over Policy Spaces: Instead of focusing on the best-case or worst-case performance, the authors calculate the expected quality (Precision, Recall, F-score) across all possible memoryless randomized policies. By treating the set of all policies as a geometric object (a product of simplices), they use Lebesgue integration to find the average performance. This provides a measure of how well a predictor performs "on average" when the environment or strategy is uncertain.
  2. Causal Volume: Borrowing from causality theory, the authors define Probability-Raising (PR) policies. A policy is considered PR if reaching the predictor state actually increases the probability of the failure occurring. The "Causal Volume" is the fraction of the total policy space that satisfies this condition. A high causal volume suggests that the predictor is robustly linked to the failure across a wide variety of system behaviors.

To make these calculations computationally feasible, the authors utilize a "two-copy MDP" construction. This transformation allows them to distinguish between paths that encounter the predictor before the failure and those that do not, effectively reducing complex temporal logic properties to simple reachability problems.

Illustrative Benchmarks

The framework is evaluated using two primary benchmarks. The first is the Suzy and Billy Example, a classic problem from causality literature. In this scenario, two individuals throw rocks at a bottle. The MDP models the timing and success of their throws, demonstrating how different actions (such as waiting vs. throwing) change the predictive power of certain states.

The Suzy and Billy MDP benchmark, used to illustrate how different strategies affect the predictive power of intermediate states.

The second benchmark is a Communication Network MDP, a synthetic model of a message-passing network with faulty nodes. This example demonstrates how to compare different nodes as predictors for message loss, showing that a node might have a high average F-score but a different "causal volume," providing two distinct "lenses" through which to view system reliability.

Key Insights and Complexity

A major contribution of this work is treating non-determinism as a form of uncertainty rather than a problem to be optimized. This shift allows for an "average-case" analysis that is more representative of real-world systems operating in unpredictable environments. Furthermore, the authors prove several results regarding the computational complexity of their measures:

  • Checking the existence of a "Strict Probability-Raising" policy is in P (polynomial time).
  • Checking for a "Global Probability-Raising" policy is in NP.
  • While exact volume computation is #P-hard, the authors demonstrate that these measures can be efficiently approximated using Monte Carlo integration.

Limitations and Future Work

The current framework focuses on memoryless randomized policies. While these are sufficient for many reachability properties, complex behaviors might require policies with memory. Additionally, the "average" calculation assumes a uniform distribution over the policy space. Future research could involve weighting the policy space based on more realistic or "likely" system behaviors. Despite these limitations, this work provides a rigorous mathematical foundation for identifying and validating the "red flags" that keep autonomous systems safe.

Summary updated

BibTeX
@inproceedings{baier2025formal,
  author = {Christel Baier and Sascha Klüppelholz and Jakob Piribauer and Robin Ziemek},
  title = {{Formal Quality Measures for Predictors in Markov Decision Processes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34879},
}
Figure