Search papers, labs, and topics across Lattice.
This paper introduces a property-driven causal abstraction technique for Markov Decision Processes (MDPs) that leverages causal relations among state variables to mitigate the exponential state space explosion. By identifying states that share common reasons for satisfying or violating abstraction properties, the authors achieve significant reductions in MDP complexity while retaining essential characteristics of the original model. Empirical evaluations on standard benchmarks show that their approach yields small abstractions that enable the computation of near-optimal policies, with promising generalization to larger MDPs.
Causal abstractions can drastically simplify MDPs, enabling near-optimal policy computation even in complex decision-making scenarios.
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.
