|
[SWD+26]
Jule Schmidt, Maximilian Weininger, Clemens Dubslaff, David Parker and Nils Jansen.
Property-driven Causal Abstractions for Markov Decision Processes.
In Proc. 26th Conference on Formal Methods in Computer-Aided Design (FMCAD'26). To appear.
September 2026.
[pdf]
[bib]
[Investigates abstraction techniques for MDPs using causal information, with an implementation that uses an extension of PRISM.]
|
|
Links:
[Google]
[Google Scholar]
|
|
Abstract.
Markov Decision Processes (MDPs) are widely used
as decision-making models, commonly specified over factored
state spaces through state variables and their valuations. The
exponential blowup in the number of states renders many
reasoning tasks in MDPs challenging. Abstractions are promising
techniques to reduce MDPs and thus mitigate scalability issues.
In this work, we introduce a notion of causality on factored
MDPs and a novel property-driven causal abstraction technique
that retains many characteristics of the original MDP model. For
this, we rely on causal relations over state variable predicates and
identify those states that share the same reasons for fulfilling
or violating a given abstraction property. We theoretically and
empirically compare various causal MDP abstractions using
different model types such as MDPs, interval MDPs, or stochastic games. Our evaluation demonstrates the potential of our
approach: For several standard benchmarks, we obtain small
abstractions that allow us to compute near-optimal policies for
the original MDP. Furthermore, our causal abstractions often
generalize to related large-scale MDP models.
|