Property-driven Causal Abstractions for Markov Decision Processes

• URL: http://arxiv.org/abs/2607.26787v2
• Date: Thu, 06 Aug 2026 15:45:37 GMT
• Title: Property-driven Causal Abstractions for Markov Decision Processes
• Abstract summary: Decision Processes (MDPs) are widely used as decision-making models, commonly specified over factored state spaces.<n> Abstractions are promising techniques to reduce MDPs and thus mitigate scalability issues.<n>We introduce a notion of causality on factored MDPs and a novel property-driven causal abstraction technique.
• Score: 15.195623277178095
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs [8.784438985280092]
  We study model-based learning of finite-window policies in partially observable Markov decision processes (POMDPs)<n>A common approach to learning under partial observability is to approximate history dependencies using finite action-observation windows.<n>Once a model of this superstate MDP is available, standard MDP algorithms can be used to compute optimal policies.
  arXiv  Detail & Related papers  (2026-04-01T15:32:47Z)
• Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning [4.024538378639506]
  This paper defines Realizable Abstractions, a new relation between generic low-level MDPs and their associated high-level decision processes.<n>We show that any abstract policy for Realizable Abstractions can be translated into near-optimal policies for the low-level MDP, through a suitable composition of options.<n>We propose RARL, a new HRL algorithm that returns compositional and near-optimal low-level policies.
  arXiv  Detail & Related papers  (2025-12-04T16:26:56Z)
• Robust Counterfactual Inference in Markov Decision Processes [3.047215509762019]
  Current approaches assume a specific causal model to make counterfactuals identifiable.<n>We propose a novel non-parametric approach that computes tight bounds on counterfactual transition probabilities.
  arXiv  Detail & Related papers  (2025-02-19T13:56:20Z)
• Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet [12.056104044376372]
  Markov decision processes (MDPs) are a standard model for sequential decision-making problems.<n>They are widely used across many scientific areas, including formal methods and artificial intelligence (AI)
  arXiv  Detail & Related papers  (2024-11-18T10:34:14Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  Contextual decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. CMDPs serve as an important framework to model many real-world applications with time-varying environments. We study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights.
  arXiv  Detail & Related papers  (2024-02-05T03:25:04Z)
• Causal Dynamics Learning for Task-Independent State Abstraction [61.707048209272884]
  We introduce Causal Dynamics Learning for Task-Independent State Abstraction (CDL) CDL learns a theoretically proved causal dynamics model that removes unnecessary dependencies between state variables and the action. A state abstraction can then be derived from the learned dynamics.
  arXiv  Detail & Related papers  (2022-06-27T17:02:53Z)
• Model-Invariant State Abstractions for Model-Based Reinforcement Learning [54.616645151708994]
  We introduce a new type of state abstraction called textitmodel-invariance. This allows for generalization to novel combinations of unseen values of state variables. We prove that an optimal policy can be learned over this model-invariance state abstraction.
  arXiv  Detail & Related papers  (2021-02-19T10:37:54Z)
• Learning Robust State Abstractions for Hidden-Parameter Block MDPs [55.31018404591743]
  We leverage ideas of common structure from the HiP-MDP setting to enable robust state abstractions inspired by Block MDPs. We derive instantiations of this new framework for both multi-task reinforcement learning (MTRL) and meta-reinforcement learning (Meta-RL) settings.
  arXiv  Detail & Related papers  (2020-07-14T17:25:27Z)
• Invariant Causal Prediction for Block MDPs [106.63346115341862]
  Generalization across environments is critical to the successful application of reinforcement learning algorithms to real-world challenges. We propose a method of invariant prediction to learn model-irrelevance state abstractions (MISA) that generalize to novel observations in the multi-environment setting.
  arXiv  Detail & Related papers  (2020-03-12T21:03:01Z)
• Plannable Approximations to MDP Homomorphisms: Equivariance under Actions [72.30921397899684]
  We introduce a contrastive loss function that enforces action equivariance on the learned representations. We prove that when our loss is zero, we have a homomorphism of a deterministic Markov Decision Process. We show experimentally that for deterministic MDPs, the optimal policy in the abstract MDP can be successfully lifted to the original MDP.
  arXiv  Detail & Related papers  (2020-02-27T08:29:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.