Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement
作者: Jakob Nyberg, Pontus Johnson
分类: cs.LG, cs.AI
发布日期: 2025-09-11 (更新: 2026-01-19)
期刊: Transactions on Machine Learning Research, January 2026
💡 一句话要点
Vejde：基于因子图着色优化的归纳深度强化学习框架，解决结构化状态决策问题。
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 深度强化学习 图神经网络 归纳学习 结构化状态 消息传递
📋 核心要点
- 现有方法在处理具有复杂结构化状态的决策问题时，泛化能力不足，难以适应不同规模和结构的问题。
- Vejde框架将MDP状态表示为二分图，利用图神经网络进行消息传递，学习状态的潜在表示，实现策略的归纳泛化。
- 实验结果表明，Vejde策略在未见过的测试实例上表现良好，分数接近于特定实例训练的MLP智能体，验证了其泛化能力。
📝 摘要（中文）
本文提出并评估了Vejde，一个结合了数据抽象、图神经网络和强化学习的框架，旨在为具有丰富结构化状态（如对象类别和关系）的决策问题生成归纳策略函数。马尔可夫决策过程（MDP）状态被表示为关于实体的数据库，Vejde将每个状态转换为二分图，并通过神经消息传递将其映射到潜在状态。状态和动作的分解表示使Vejde智能体能够处理不同大小和结构的问题。我们在RDDL中定义的八个问题域上测试了Vejde智能体，每个问题域有十个问题实例，并使用监督学习和强化学习训练策略。为了测试策略的泛化能力，我们将问题实例分为两组，一组用于训练，另一组仅用于测试。我们将Vejde智能体在未见实例上的测试结果与在每个问题实例上训练的MLP智能体以及在线规划算法Prost进行了比较。结果表明，Vejde策略平均可以推广到测试实例，而分数没有显著损失。此外，归纳智能体在未见测试实例上获得的分数平均接近于特定实例的MLP智能体。
🔬 方法详解
问题定义：论文旨在解决具有丰富结构化状态的决策问题，例如涉及对象类别和关系的场景。传统方法，如直接使用MLP处理状态，难以泛化到不同大小和结构的问题实例。每个实例都需要单独训练，无法利用跨实例的知识。
核心思路：论文的核心思路是将状态表示为图结构，利用图神经网络学习状态的潜在表示。通过图神经网络的消息传递机制，可以有效地聚合实体及其关系的信息，从而实现对状态的抽象和泛化。这种方法允许智能体处理不同大小和结构的问题，并利用跨实例的知识进行学习。
技术框架：Vejde框架包含以下主要步骤：1) 状态表示：将MDP状态表示为关于实体的数据库，并将其转换为二分图，其中节点表示实体和属性，边表示实体之间的关系。2) 图神经网络：使用图神经网络（GNN）对二分图进行消息传递，学习每个节点的潜在表示。3) 策略学习：基于GNN学习到的潜在表示，使用强化学习或监督学习训练策略函数，用于选择动作。4) 动作执行：根据策略函数选择动作，并执行动作以更新环境状态。
关键创新：Vejde的关键创新在于将图神经网络引入到强化学习中，用于处理具有结构化状态的决策问题。通过图神经网络，Vejde可以学习到状态的抽象表示，从而实现策略的归纳泛化。与传统方法相比，Vejde不需要为每个问题实例单独训练，可以利用跨实例的知识进行学习，从而提高学习效率和泛化能力。
关键设计：论文中使用了基于消息传递的图神经网络，具体来说，使用了神经消息传递（Neural Message Passing）机制。状态被表示为二分图，其中一部分节点代表实体，另一部分节点代表属性。消息在实体节点和属性节点之间传递，从而聚合实体及其关系的信息。策略函数的训练可以使用强化学习算法（如Q-learning或Policy Gradient）或监督学习算法。损失函数根据具体的学习算法选择。论文中使用了RDDL（Relational Dynamic Influence Diagram Language）来定义问题域。
🖼️ 关键图片
📊 实验亮点
实验结果表明，Vejde策略在未见过的测试实例上表现良好，分数接近于特定实例训练的MLP智能体。具体来说，Vejde策略在测试实例上的平均得分与MLP智能体相比没有显著损失，并且接近于在线规划算法Prost的性能。这表明Vejde框架具有良好的归纳泛化能力，可以有效地处理具有结构化状态的决策问题。
🎯 应用场景
Vejde框架可应用于各种具有结构化状态的决策问题，例如机器人导航、资源分配、交通控制和游戏AI等领域。该框架的归纳泛化能力使其能够适应不同规模和结构的问题，从而降低了开发成本和提高了应用范围。未来，Vejde可以与其他技术（如知识图谱和迁移学习）相结合，进一步提高其性能和泛化能力。
📄 摘要（原文）
We present and evaluate Vejde; a framework which combines data abstraction, graph neural networks and reinforcement learning to produce inductive policy functions for decision problems with richly structured states, such as object classes and relations. MDP states are represented as data bases of facts about entities, and Vejde converts each state to a bipartite graph, which is mapped to latent states through neural message passing. The factored representation of both states and actions allows Vejde agents to handle problems of varying size and structure. We tested Vejde agents on eight problem domains defined in RDDL, with ten problem instances each, where policies were trained using both supervised and reinforcement learning. To test policy generalization, we separate problem instances in two sets, one for training and the other solely for testing. Test results on unseen instances for the Vejde agents were compared to MLP agents trained on each problem instance, as well as the online planning algorithm Prost. Our results show that Vejde policies in average generalize to the test instances without a significant loss in score. Additionally, the inductive agents received scores on unseen test instances that on average were close to the instance-specific MLP agents.