马尔可夫决策过程的属性驱动因果抽象
文章背景与核心概要
马尔可夫决策过程（MDP）是建模决策问题的经典数学模型，但在处理因子化状态空间（factored state spaces）时，常常会遭遇状态空间呈指数级膨胀的瓶颈。为了解决这一扩展性难题，本文在因子化MDP上引入了一种全新的因果关系概念，并提出了一种属性驱动的因果抽象技术。
该方法通过利用状态变量谓词（predicates）之间的因果关系，将那些由于相同原因满足或违反抽象属性的状态进行分组，从而在保留核心特性的同时大幅降低了模型复杂度。在标准基准测试上的实验评估表明，这种紧凑的抽象模型能够成功计算出近乎最优的策略，并且往往能够泛化到更大规模的MDP模型中。
Metadata
- arXiv ID: arXiv:2607.26787 [cs.AI]
- Subjects: Artificial Intelligence (
cs.AI); Logic in Computer Science (cs.LO) - Authors:
- Jule Schmidt
- Maximilian Weininger
- Clemens Dubslaff
- David Parker
- Nils Jansen
- Submission History:
- v1: 29 July 2026
- v2 (Current): 6 August 2026
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.
马尔可夫决策过程（MDP）被广泛用作决策模型，通常通过状态变量及其赋值在因子化状态空间上进行定义。状态数量的指数级膨胀使得MDP中的许多推理任务极具挑战性。抽象是简化MDP并从而缓解扩展性问题的前沿技术。在这项工作中，我们在因子化MDP上引入了因果关系的概念，以及一种新颖的属性驱动因果抽象技术，该技术保留了原始MDP模型的许多特征。为此，我们依赖于状态变量谓词之上的因果关系，并识别出那些因相同原因而满足或违反给定抽象属性的状态。我们从理论和实验上对比了各种因果MDP抽象，涉及MDP、区间MDP（interval MDPs）或随机对策（stochastic games）等不同模型类型。我们的评估展示了该方法的巨大潜力：对于几个标准基准测试，我们获得了精简的抽象模型，从而能够为原始MDP计算出近乎最优的策略。此外，我们的因果抽象通常可以泛化到相关的大规模MDP模型中。
