Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement
Authors: Jakob Nyberg
Pontus Johnson
Venue: Accepted by TMLR ()

Abstract: We present and evaluate Vejde; a framework which combines data abstraction, graph learning and reinforcement learning
to produce inductive policy functions for decision problems with richly structured states, such as object classes and relations.
Markov decision process 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.

Published in Transactions on Machine Learning Research (1/2026)
Vejde: A Framework for Inductive Deep Reinforcement Learn- ing Based on Factor Graph Color Refinement
Jakob Nyberg
jakngb@kth.ss
Division of Network and Systems Engineering KTH Royal Institute of Technology Stockholm, Sweden
Pontus Johnson
pontusj@kth..s
Division of Network and Systems Engineering KTH Royal Institute of Technology Stockholm, Sweden
Reviewed on OpenReview: https: openrevvee..........mmmmm net/ net/ forum? id= EFS2mL1K12
Abstract
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 object classes and relations. MDP states are represented as data bases of facts about entities, and VEJDE converts each state to 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 len 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 unseen instances for the VEJDE agents were compared to MLP agents trained 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 unseon test instances that on average wore close to the instance-specific MLP agents.
1 Introduction
We are interested in two topics: Deep reinforcement learning (RL) for problem domains that fit relational data models, and agents that can generalize to classes of problems. This interest. mainly stems from experiences in researching automated network incident response, where both of the aforementioned qualities
are important for practical use, though not always prioritized (Wolk et al. 2022 Nyberg & Johnson, 2024 Thompson et al. 2024). The two topics are interleaved, in that incorporating structure to the traditional Markov decision process (MDP) formalism typically used in RL is in itself a method for improving agent generalization (Van Otterlo 2009 Mohan et al. 2024 Kirk et al. 2023) though neither topic necessitates the other. To this end, we have developed a small reinforcement learning library which we have named VEJDE ! VEIDE combines graph neural networks and reinforcement learning to incorporate data struetures which be observed defined in different problem areas, and to produce neural policy functions that can be used for classes of problems defined with shared data description language.
A decision agent policy is a function which takes the state of a decision problem, usually modeled as MDP or partially observable MDP, as input and produces probability distribution over actions that are possible
Vejde is the Swedish name the flower Isatis finctoria, traditionally refined produce indigo dye for textiles.

---

Published in Transactions on Machine Learning Research (1/2026)
in the given state. An optimal policy will produce actions that maximize the expected reward; the assigned metric of success at the task the MDP models. Our aim is to find inductive policies that can perform well across a domain, or class, of problems. This has long been a goal within the realm of relational RL (Dzeroski ct al.
2001 Van Otterlo 2009), which combines reinforcement learning with elements of symbolic logic, but ideas for improving RL. generalization have also come from more recent. sources in deep learning research (Kirk
ct al. 2023).
Relational database systems and data modeling remains popular option for data storage in several areas which motivates investigating machine learning methods that can utilize the structure relational databases provide. Relational databases use SQL (Chamberlin & Boyce, 1974h and to varying degrees conform with a formal relational model [Codd] 1970). Previous work has investigated methods for applying supervised learning to relational databases (Fey et al.) 2024b) using graph neural networks (GNNs), From that perspective, this work concerns instead using RI. and GNNs with relational databases. Another way of regarding a relational database as a set of facts about entities described using a typed first-order logical language, where every possible set of facts given the language is a discrete state of some problem domain.
One way of describing a policy for such a logical state representation is decision list. Each entry in the decision list defines a set of logical conditions, defined in the same language or data model as the database, that when fulfilled leads to an agent choosing an action (Fern et al. 2006). There exists approaches, both symbolic (Fern et al., 2006) and neuro- symbolc (Hazra & Raedt 2023) which aim to find and represent the decision list in an explicit and human-readable form. We instead opt to use message- paouggg-assingg neural networks (MPNNs) to implicitly encode the rules of a decision list. This choice trades interpretability for flexibility and case of numerical optimization, is typical with deep learning methods. The abilities, and limitations, of MPNNs to express logical classifiers has been covered by Barceló et al. (0020) and Grohe 2021).
Thus, in our implementation, the state of the problem consists of a set of known, true, facts about entities expressed in predicate logic. The set of facts is then represented as a bipartite factor graph, and encoded using neural graph color refinement. The color refinement algorithm generates vector embeddings for nodes in the graph through iterative message-passing, where at each step the vector representations of each node is updated by combination of itself and the graph neighborhood vectors (Morris et al.) 2019). A policy head, also using neural networks, predicts the probability of action components from the embedding vectors. The implementation lets VEJDE agents, like symbolic decision list, handle states with varying numbers of entities and possible actions.
We evaluate VEJDE with eight decision problem domains defined in the Relational Dynamic Influence Diagram Language (RDDL). Each RDDL domain shares a common description language and state transition dynamics, from which ten problem instances with varying parameter values per domain have been defined. The problem domains we include for evaluation include deterministic and probabilistic state transitions, as well as both discrete and continuous state variables. To test the inductive qualities of the VEJDE policies, we separate problem instances into two sets, where one is used for training and the other for testing. As all problem instances share the same reward and state transition functions, an inductive policy should receive in the same average score on test set as it does on the training set.
We performed two main experiments. One in which we trained VEIDE policies in a supervised manner, using actions provided by another agent as labels, to test if VEJDE can encode an inductive policy for the problem domains. In the second experiment, we trained policies using RL, using the actor-critic algorithm proximal policy optimization (PPO), to test if an inductive policy can be found without labeled data.
We compare VEJDE policies with two other adaptive decision agent types. The first are policies parametrized using fully-connected lulti-layer perceptrons (MLPs). Unlike the VEJDE policies, based on GNNs, these take constant-sized and instance-specifie vector inputs, and can not generalize across multiple instances. The MLPs encodes policies which are specially developed for a particular problem instance, and which they ideally should be optimal for. Our other point of comparison is the online planning algorithm PROST. PROST represents different problem-solving methodology than RL, and uses tree-search algorithm based on
2 PAccording to htttt:://bbbbbb..:ee: http::////bbeneneee..// wwtpb/eennnneccneeee/eeeeeeeeeee com/en/rankinng
2

---

Published in Transactions on Machine Learning Research (1/2026)
repeated simulated trials to estimate optimal action for each encountered state. PROST, for most problems, serves as an upper bound of scores in our evaluation. We also set lower performance bound for each problem, in the form of random and do-nothing policies, to determine if the learned policies are better than trivial policy.
The results from the supervised learning experiment showed that VEJDE policies in average generalized the unseen test set problems without a statistically significant drop in score. The mimic policies are receiver higher scores than the trivial policies on all domains, but the differences to the PROST scores are larger problem domains than others. From the reinforcement learning experiment, we observed that the scores of the VEJDE policics in average were not statistically different from those of the MLP policies. However, we also noted that the scores of the RL policies varied a lot between problem domains, with the VEJDE agent not outperforming the trivial policies on two domains. As expected, the RL policies of both types consistently received lower scores than PROST, though on one domain the VEIDE agent received higher average score than PROST.
Our work builds upon previous work in the area of symbolic, and neuro-symbolic, decision learning, both
within the realm of automated planning through machine learning (Stählberg et al. 2023 Chen & Thiébaux
2024) and deep relational reinforcement learning (Janisch] 2024 Sharma et al. 2023 b. Unlike problems
common in symbolic planning research, we focus on problems with uncertain outcomes, formalized as MDPs, and which we assume may include continuous variables.
The source code for VEJDE and the RDDL extension both available publicly to facilitate application new problem domains.
Contributions We present and evaluate the framework VEJDE. The contributions of this work can be summarized as follows:
A methodology to use deep reinforcement learning with problem areas where relational data is observed or can be defined.
A neural architecture to encode and parametrize an inductive decision policy for relational data.
We show that for all the decision problems we evaluate with, the architecture can parametrize an inductive policy and that it can mimic the near-optimal performance of a planning algorithm on some problems.
We show that for majority of problems we evaluate with, inductive policy parametrized using the neural architecture that is better than trivial policies and close to instance-specific policies can be found through reinforcement learning.
A Python library, named VEJDE, with generic interfaces so that it can be applied to problem domains not defined in RDDL.
2 Background
This section covers topics related knowledge representation, graph neural networks and reinforcement learning relevant to this work. We emphasize that our focus is not on how to design or learn data abstracctons for problem domain, and assume that. for a given problem there already exists data model of object classes, attributes and relations.
2.1 Knowledge Representation
Predicate logic, or first-order logic, has long been used to describe situations and dynamics of decision problems [Reiter 2001 Russell & Norvig 2010). Through this text, will use components of first-order
http:://gthub.cm//aaarr////
httpe//gghubl.cm//aaaar////jj
3

---

Published in Transactions on Machine Learning Research (1/2026)
logic to describe the states of problems. We thus use the following definitions: Predicates are used to represent properties or relations. We will denote predicate symbols with capital letters such as P or Q. An alom is a predicate symbol combined with tuple of variables, denoted with lowercase letters. Predicate symbols have an arity which defines the length of tuples it can be applied to. We will use the term object when referring to instantiations of variables, denoted with lowercase letters and a subscript, like T1 or 111 A fact refers to a ground atom where all variables have been substituted by objects, as P(x1) or Q(11, V1). Function symbols map objects or tuples of objects to other elements in the language. Given function symbol Z, we could for instance make the statement Z(x1) 30. Lastly, we assume typed logic. This means that each predicate is also associated with a tuple that specifies the types of the variables. Each object thus has a type or class. Any ground atom that is the result of combining a predicate symbol with a tuple of objects with mismatched types is defined as false. We will simply use the letter used to identify the object to indicate its type, meaning that æ1 and y1 can be read as belonging to different object classes. All the definitions form a language, which can be specific to a particular problem domain.
2.2 Markov Decision Processes
We choose to represent decision problems as Markov decision processs Putterman 1994). A MDP is a formalization of a system where an agent makes sequential decisions, under the assumption of potential uncertainty about the decision outcomes. A reward or cost value defines a mcasure of success at the task the agent should perform. MDPs are assumed to have the Markov property that the state and reward dynamics are dependent only on the immediate previous state and action. The agent is assumed to follow a policy, n, by which it selects actions given the state it observes. For finite MDP, an optimal policy maximizes the expected discounted return, G2 = E y'r,, The term relational MDP has been used by several authors to describe MDPs where the problem state is structured, factored or explicilly represented using symbolic logic (Guestrin et al., 2003 Diuk et al., 20088 Dzeroski et al. 2001 Van Otterlo| [2099] Kersting & Driessens) 2008). A relational MDP can be described as collection of problems, each individually a MDPs, which all share a common description language.
2.3 Reinforcement Learning
To search for optimal policy, we use PPO; a model-free actor-critic reinforcement learning (RL) algo- rithm (Schulman et al. 2017). Reinforcement learning (RL) constitutes class of methods to find, or at least search for, the optimal policy of a MDP (Sution & Barto 2018). Different RL approaches mainly alter the methods of selecting actions, what data is used to gather or update the policy and the step intervals between updates. Model-free RL learns policy through selecting actions from the agent policy and updating it solely based the resulting transitions of the MDP. This means that model-free methods requires little to no prior knowledge of the problem dynamics, at the expense of requiring more data than model-based methods, which instead incorporate system knowledge to improve the policy. Value-based RL methods uses data to generate estimates of the stato-value vn (s) = E, [G,|S, = s] or action-value Q" a) = E, [G,|S, = A = a] functions of the MDP, which the policy is then based on. Policy gradient algorithms instead use data to directly optimize a differentiable function towards the optimal policy. Actor-critic methods combines elements of value estimation with policy gradient methods to improve optimization stability, where an "actor" component produces action probabilities, [a]ss), and a "critic" component produces a state value estimate, ū(s)). PPO is a policy gradient algorithm that enforces hard limit on how much the policy can change per update. The actor loss for PPO is calculated as Lp(st, at, 0) min (r(0)- A(si, a:), clip (r(0), 1 c, c) A(se, a:)) where r(st, az, 8) = aa (s.)
[.)) a ratio between the old and updated policy output which is used to clip the loss. A is the action advantage, which may be calculated in different ways, but is typically defined as the difference between the state-value and action-value for the action.
2.4 Dassagg-Passing Neural Networks
In order to use policy gradient methods we need a differentiable function that can go from the data contained in the state, which we assume to be relational by design, to action probabilities. We use GNNs for this purpose, specifically MPNNs. The properties of MPNNs are closely related to those of the Weisfehlee-Lehman (WT.)
4

---

Published in Transactions on Machine Learning Research (1/2026)
algorithm, and we will use that algorithm as the basis for this explanation. The WL algorithm is designed to test if two graphs are isomorphic. The algorithm can also be used to generate graph or node represental ions for graph similarity and classification tasks, At each iteration, the WL algorithm updates a label of each node to a hash value calculated from the old label and labels from the node neighborhood. This is also known as a graph color refinement algorithm (Grohe 2021), as nodes are assigned metaphorical "colors" which are continuously mixed with neighboring node colors. MPNNs follow the same general color refinement algorithm, but use neural networks rather than hash functions to calculate node "colors", which are represented using high-dimensional vectors. This allows for parameterizing differentiable functions on graphs that can be optimized through gradient descent for common machine learning tasks such as classification or regression. A useful feature of MPNNs is that the model parameters are shared across nodes, meaning that the size of the neural network does not need lo change with the size of the input graph. It has been shown that MPNNs can not be more expressive than the WL algorithm (Wang & Zhang 2022 Morris et al. 2019). As such, if the WL test fails to distinguish two graphs, so will MPNN. From this result, it follows that a classifier based on MPNNs will always produce the same results if the WL algorithm fails distinguish two graphs, subgraphs. This result has been elaborated on in the context of logical classifiers by [arceló et al. graded
(2020) as well as Grohe (2021), showing that GNN without global a readout are expressive first-order classifier A common categorization in graph learning is transductive and inductive graph learning. Transductive graph learning aims find model for a task based on a single graph. If the graph structure changes, or a new graph is introduced, a new model has to be trained. Inductive graph learning instead focuses on solving a task for classes of graphs that share some common underlying data distribution. On a practical level, inductive graph learning typically implies that node representations can not be calculated based on identifiers that do not convey meaning outside the particular graph instance.
3 Implementation
VEJDE is formed by four primary components described in this section: Representing the problem state using predicate logic, representing the data basc as a bipartite graph, encoding the graph using a graph neural network and lastly using the object encoding vectors to produce action probabilities and state value estimation. A key implementation detail is that the sizes of both the agent input and output is not fixed, and dependent on the number of facts and entities in the state.
3.1 States & Actions
We represent the state of the MDP in given time step a set of facts expressed in the domain languag To reduce the size of the state data base, facts that are explicitly known to be false are not included. No information is lost through this choice if we maintain the assumption of full observability in the environment, as there is no need to distinguish between a fact being false or missing from the data base (Reiter 1977). Actions in the MDP are represented as ground atoms from the same language as the state by assigning a subset of predicates in the domain language as action symbols, A C P. An example state with actions is shown in Appendix A
3.1.1 Bipartite State Graph
In order to generate object representations through graph color refinement, we first represent the state databasc as a biparitite graph, which consists of two distinct sets of nodes, V and U. V is a set of all facts in the state and U is a set of observed objects. A set of edges relate facts in V to objects in U. Each odge is formed by an object being present in the object tuple of a fact. Following the representation lt al. 2024), , each edge between an object u and literal is associated with the position of in the tuple of objects of A rendering of the state graph representation is shown in Figure Ia along with possible actions in Vigure 1b]
Chen
"Craaded" in this context meaning that path between two entitics needs exist in the graph. 6Since the truthiness and values of literals are assumed to be variable, it would be more correct to denote each fact with time or step. We do not, however, since our calculations only ever involve the current state.
5

---

Published in Transactions on Machine Learning Research (1/2026)
A
Aa
P(z1)
(
As(as)
Asles)
a(A4, xn)
((42,
A.(a)
Ay(r))
21
(z)
y1
#2
m(A1, m2) = 0.1
((22)22) 0.2
(pn)
As(yn)
1/1
<(A,,n)) 0.2
<(An.)) - 0.0
(21.
(a) Bipartite graph representation of the set (b) Rendering action combinations for the state, along (P(æ)), ((21, 91), 4(m)) 5, Q(22, с). Squares with hypothetical action probabilities assigned by denote ground expressions, circles objects and rhombuses agent policy. the position of objects in atoms.
Figure 1: Renderings of factored state and action representations.
3.2
Vector Encoding
All clements of the state are encoded into the vector space Rd using embedding vectors. The encoded elements form two multisets of initial node embeddings K {(k, : V}} and H = {( E U},, corresponding to the factor nodes and object nodes U. We also encode the positions objects in the argument list of facts by mapping the positions to vectors in D.
3.2.1 Literals
Two types of ground expressions are inchuded in our data model; ground atoms, e.g. P(x1), Q(11, v1), and grounded function symbols that map objects to a real value e.g. 2(y)) = 1. Ground atoms are encoded by the embedding vector of the predicate symbol. Function atoms are encoded as lincar scaling of the function symbol's embedding vector by the value it equal ud] We can represent the encoding of both types in single expression by defining the function v: V + R that maps all elements of V to value from R. If the element is ground atom, the value is defined to be 1, and it is an expression with function symbol it returns the value of the function. Thus, we define the embedding vector k, for literal v k = v()) EP(JV-p())), Ep P
Expressions with nullary atoms are handled with an additional step. We denote the set of these literals as G V. and assume that nullary literals influence all objects. The encoding vectors of the nullary literals are aggregated and added to the initial embedding vector of each object. We use the function
((G)
Σ Softmax (101(0)) ((oo))lve)) Φ2(v)
VEG
to aggregate the vectors, where di : DR + R and 02 RD R are implemented using neural networks by Li et al. 2016).
7 As simplifying delimitation, function symbols are assumed always map objects singular values in

---

Published in Transactions on Machine Learning Research (1/2026)
3.2.2 Objects
To avoid using object identifiers as features, objects are mapped to their respective types through a function JU-T: U + T, where T is the set of types defined in the language. The type identifiers are then mapped to vectors in I. The embedding vector hn for an object thus defined as ha (f(--r())), ET R.D.
3.2.3 Positions
Edge embeddings are defined as Cuv Ex Vx u)); F N and an object, and maps them to the set of aritics for predicates in the language, N.
N - RD. The function JU.V takes a fact.
3.3 Message Passing
The messago-passing scheme we use for color refinement is similar previous work on neural message passing factor graphs (Satorras & Welling, 2021 A single iteration of message passing consists of nodes in K sending messages to neighboring nodes in H. H is updated and sends messages back to K which is then also updated. Each step of message passing uses a unique set of four neural networks, which we denote with 6. Incoming messages to node are aggregated by taking the element wise maximum over the node neighborhood, max : D D. While a max aggregation is theoretically less expressive than a sum aggregation (Xu et al. 2019), it has been found to work well in practice in previous work (Janisch] 2024 Messages from U to V are defined m (++1) @v- (h k(6)) and the reverse hg (((+1) || euv) Representation vectors for object nodes in U are calculated at each
Ståhlberg et al.
2023
as mu-se = o vvv (
iteration as
((+1)) = {{
M ((+1) = o (1()
max (m(ittt)) u u { vEN(u)
where to denotes vector concatenation and {0) multiset. Updates to factor nodes in V are defined as
k(-11) = {{ (((+1) k(00 + + (0) [109 max (ml-tt) :0 :wer]]
uEN(v)
3.4 Policy
A policy function can in a more general view be regarded as classifier, which takes a state representation and assigns a probability each action that is possible given the state. In this setting, the state is represented set of facts, which are encoded using embedding vectors and message passing to latent state H of object embeddings. Thus, from the multiset. H, the policy function should assign a probability to each action that is possible given the objects in U and the action symbols A, as described in Section 3.1 Since we limit action symbols to be mullary or unary, all actions contain a predicate symbol, a E A C P, and a single object, u E U. Nullary actions have no arguments by definition, but for ease of implementation we define a null object, Ø, which is the only selectable object for nullary actions. We denote the joint probability over action symbols and entities as T(a, u| H),, such that T(a,, in (H) would be the probability of the action di (wi) given the set of object embeddings, H. The joint action probability can be predicated in full, factorized in three different ways, which lead to different agent properties (Nyberg & Johnson 2024 S For this work, we solely evaluate the factorization (a, u/ H)) (a)HH) Ty (ula, H), which corresponds to first sampling a predicate symbol, followed by an object. The conditional of will be omitted from here onward, for notation brevily. We calculate the action symbol probability, (a),,, as a weighted sum of conditional action probabilities over objects
V
n (a) = Σ ग. (alu)) (u)
8The main property that changes is the dependency global readouts. Sampling an object first and then an action symbol based on that choice be done without considering the entire graph.
7

---

Published in Transactions on Machine Learning Research (1/2026)
where =A(a/u)= == Softmax (W hus a). W E R A|D and Te( == Softmax" V (W. H, H,u), WER..
The probability of selecting an object given an action symbol, Tu(w))), is calculated as Ty = Softmax / (H Wa, u), W E Dx]a where Wa is the column vector in W identified by a. We use Softmax" moaaxxx( (z, i) = E, ets to denote the i-th element of a vector x where the softmax function is ap- plied over dimension D.
3.5 Value Estimate
As a part of the actor-critic framework, the architecture should produce an estimate, ë", of the state value. We calculate 8th as an expectation over the action probabilities and an action-value estimate,
1-
Σ (a)
Σ Au(ula) WEU
aEA
where Q(u, a) = h.g Wa: W E PXIAI hy E H. This formulation can be regarded as dividing a single step in the MDP into two sub-steps, where the first consists of the agent choosing a predicate symbol. If we were to extend the number of object arguments for actions, the number of sub-steps would increase to account for the additional choices.
4 Evaluation
We evaluate VEJDE using set of problems defined with the Relational Dynamic Influence Diagram Language (RDDL) and executed in the Python library PyRDDLGy Taitler et al. 2024). RDDL is a description language that can be used for specifying Markov decision problems as dynamic Bayesian networks (Sanner) 2010 We test the ability of VEJDE to model inductive decision policies in two ways: supervised learning from examples and reinforcement learning.
We compare VEJDE policies with policies parametrized using MLPs, and a planning algorithm named PROST [Kllerr & Helmert 2013), the winner of the probabilistic track of the 2014 International Probabilistti Planning Competition (IPPC) (Vallati et al.] 2015 PROST uses a tree-scarch algorithm framework to find optimal action for each state based on series of simulations initiated from the stale. As such, for each state PROST runs thousands of trials to construct the search-tree. We think it should be noted that this is a fundamentally different problen-solving approach than the reinforcement learning method used to train the VEJDE and MLP policy functions. With RL, a simulator is only used during training to find the parameters of the policies, whereas PROST always needs access to a simulator of the problem order to perform searches.
We use an existing interface for PROST to PyRDDLGym for all experiments For the MLP policies, we used the implementation included in the PyRDDLGym set of libraries, which in turn is based on Stable Baselines 3 TH In the MLP implementation, the state is represented as a vector over all possible facts, the length of which is dependent on the language and number of objects in the problem instance. This means that the total parameter count of the MLPs input and output layers varies between instances and domains, but all use two hidden layers with 64 latent parameters each. The MLP policies are transductive, and can not be used for multiple problem instances due to the varying input and output shapes. We thus train one MLP agent for each domain and instance combination.
Including inductive agent from previous works would have been useful, but were unable to find single method that cover the set of problem domains as we are evaluating on. We should note, however, that there is overlap with previous works on subsets of the domains we include (Janisch) 2024 Garg et al. 2019 Sharma lt al. 2023). We did evaluate an alternative encoding method, however, based on graph atlention. The main difference between this approach and the message passing method described in Section 3.3 is that the graph attention method incorporates information from the entire graph in a single step of message passing. We ultimately found that the graph altention method did not perform significantly better than the message
httpps//githubb. cwwppyoddlgpppcccoocccccc http:///hw...aaoooooo/o/////////
bttps://github... com/ commpyyrd/gga.. pttp://oeoe///otoooooooaooooooaa
https://github.. cwn/co//////e wttp:p/wwwwnnggooooooooooo/o///o

---

Published in Transactions on Machine Learning Research (1/2026)
passing method, at a significantly higher computational cost. An extended description of the graph attention method, together with evaluation results, is shown in Appendix H
4.1 Problem Selection
RDDL defines problems as combination of a domain description file and an instance description file. The domain file primarily defines state transition dynamics and object classes, whereas instance files declares object instances, ground values and parameters to instantiate problems in the domain. VEJDE can be used with the different domains with no modifications other than adjusting the input and output sizes based on each domain description, meaning that we train one agent per domain. RDDL is similar to the Planning Domain Definition Language (PDDL) in that it is a formal description language used to describe decision problems, but adds modeling features such as probabilities, continuous state variables and partial observability.
PyRDDLGym hosts a repository of RDDL problem definitions [2] We evaluated VEJDE the following problem domains from previous IPPCs: Elevators (2014), SysAdmin, Navigation, Traffic (2014), ShillTeaching (2014), AcademicAdvissigg (2014), Crossing Traffic (2014) and Tamarisk Each problem domain has ten instances which vary initial values and the number of entities. All problems have a time horizon of 40 steps, after which the MDP is terminated, and all problems have the option for the agent to do nothing. We selected domains based on a set of exclusionary criteria that filter out problems that define continuous actions, action literals with an arity greater than one, state-dependent conditions on actions and lastly problems that implement partial observability. For example, the IPPC 2014 problem Wildffre were excluded since it contains the action fluent put_ oott_outtr y), which has arity of two. Modifying domains specifications to include more problems is possible, but we considered it out of scope for this work. While we did not modify the domains, we edited all instance specifications that allow for concurrent agent actions to only permit one action per timestep. This includes subsets of instances in ShillTeaching, AcademicAdvisinng Elevators and all instances in Traffic. Removing concurrent actions allows us to compare the GNN policy against the pyRDDL MLP policy on all instances, at the expense of slightly changing the problem premises! The conditions used to select. problems are discussed further in Appendix [
The included domains cover two general types of decision problems: SysAdmin, Elevators, ShillTeachhngg Tamarisk and Traffic are reward maximization, or cost minimization, tasks. Crossing Traffic, Navigation and AdoisiicAdossing are goal-oriented, where the agent actions should lead to a given condition being fulfilled. Based on the arities of the action literals defined for the problems, we can also separate the eight problem domains into three categories. Ignoring the "do nothing" action, SysAdmin, Traffic and AcudemicAdrising have only one unary action and no nullary actions. Elevators, SkillTeaching and Tomarisk have multiple unary actions and no nullary actions. Crossing Traffic, Navigalion have four nullary actions that represent. cardinal directions for the agent to move, but unary actions. The maximum predicate arity in all domains is two. This fact was not part of our inclusion criteria, but came as a consequence of the selected problems.
4.2 Data Generation
A RDDL problem instance defines constant number of objects. As we are interested in use-cases where the total number of objects vary, or is unknown, sample transitions evenly from multiple problem instances as if they constitute a single relational MDP. To test that the policy generalizes, we divide the 10 problem instances of each domain into two sets by random selection and use one for training and the other for testing, as per common practice in supervised learning. The object counts are not evenly distributed, so to reduce bias we sample five train/test splits and repeat experiments for each split, and calculate the final results as an average over them. For the other agents, PROST and the MLPs, considering a "test" set of problems is not possible, as PROST always performs searches and each MLP agent is tied to a problem instance.
hhtttps://giie 15 hercnthesized year denotes the version used where muluple are available. Withhont concurrent actions for Elenators, an agent has prioritize moving one two elevators at each time step rat than controlling both simultaneously.
9

---

Published in Transactions on Machine Learning Research (1/2026)
4.3 Experiments
To evaluate VEJDE, we performed two main experiments. One experiment in which agents are trained by examples generated from PROST, and one where agents are trained without examples through reinforcement learning. We then compare the scores of VEJDE agents against bascline policies, and other approximate policy methods. Both experiments use the same splits of training and test problems.
4.3.1 Imitation Learning
We lested the capability of VEJDE to encode a near-optimal policy by having agents mimic the actions of the planning algorithm PROST on the training set of problems. The resulting mimic policy was then scored on the test set of problems. To collect training data for each domain, we ran PROST on every instance in the training set for ten episodes, each consisting of 40 state-action transitions with the recommended "IPC2014" configuration. This resulted in 2000 samples for each domain, each of which consists of state and an action taken by PROST. The mimic agent was then trained through imitation learning, where the policy is optimized to simply maximize the probability of actions selected by PROST. This procedure was repeated five times, once for each train/test split. The results of this experiment can be found in Section 5.1
4.3.2 Reinforcement Learning
As we do not wish lo assume access to labeled data or an expert policy, the primary interest for us with this work is to find decision policies using RL. While we solely used PPO for RL, other policy gradient algorithms could be used in theory. In training the agent, maximize the loss L = - La ce + C₁ ((x) through stochastic gradient ascent, where Lg is the actor loss, Le the critic prediction loss (ö RR)² and (T) the entropy of the action distribution given the state. The entropy term serves as regularization parameter and encourages exploration. Each VEJDE policy was trained with total of 500 000 samples from problem instances in the training set. All MLP policies were trained with 400 000 samples per instance with the same hyperparameters for all problems. Though both the MLP and VEJDE agents are trained as stochastic policies, we evaluated them deterministically by picking the most probable action from the action distribution for a given stale, rather than sampling the distribution. This choice was made to lower the variance of the results, but it ignores that the policy may assign nearly equal probabilities some actions. The results of this experiment can be found in Section 5.2
5 Results
Our primary evaluation metric is the average return for agents on problem instances in the test set, which VEJDE agents were not trained on. For transductive agents, iee. PROST and the MLP agents, we only count scores on problems that are in the test set, averaged over the respective train/test splits.
Fach RDDT, domain uses rewards with different scales and magnitudes. We thus present returns normalized to the range [0, 1], calculated using the method from IPPC 2014 & (Vallati al.] 2015). Raw return values for each domain, instance and agent can be obtained from our GitHub repository Tb All experiments were done on machine equipped with 32 GB of RAM, an Intel Xeon Silver CPU with 24 cores and an NVIDIA Quadro RTX 4000 GPU.
5.1 Imitation Learning
Running PROST on the 90 problems for ten episodes each to collect training data took approximately hours. We then ran PROST for 100 episodes on all 90 problems for scores to use in evaluation, which took roughly two days. Each mimic policy was trained for 1000 epochs over the training data, which was fed to the agent in single batches of 2000 samples. Training mimic policies for all domains took approximately 30 minutes, repeated five times with different train-test splits for total of 2.5 hours. The mimic policy was then tested on all problem instances for 100 episodes. To summarize the differences between the agents, we performed
10

---

Published in Transactions on Machine Learning Research (1/2026)
Differences in average normalized scores for imitation learning policies. Comparing PROST scores, VEIDE scores on test instances, and scores on train instances. Poutt is probability according null distribution produced by permutation testing that P(X 2 |41 - p2l)..
Table 1:
Comparison
P1
11
Pouil
Test -rain
0.01
0.82
Test PROST
-0.26
0.00
Train PROST
-0.28
0.00
Table 2: Average normalized score per domain on test. instances for PROST and VEIDE policies trained with imitation learning.
Domain
VEJDE μ + o
PROST μ + o
SysAdmin
0.99 + 0.03
0.87 + 0.12
SkillTeaching
0.91 + 0.22
0.98 + 0.02
Tamarisk
0.88 + 0.06
1.00 + 0.01
Elevators
0.87 + 0.13
0.99 + 0.02
Traflic
0.73 + 0.16
1.00 0.00
Crossing Traffic
0.63 + 0.31
1.00 0.00
Navigation
0.33 + 0.48
0.99 + 0.03
GeademicAdvising
0.21 + 0.42
0.75 = 0.44
permutation test to compare average mimic scores on train and test instances, as well as PROST scores To The test calculates a distribution a selected metric, in our case the difference in means, under the hypothesis that the compared sample distributions are equal. It docs so by pooling all the samples and caleulating the metric for permutations of the samples for a given number of repelitions. If the observed metric is unlikely given the resulting distribution of metrics, then the null hypothesis of the samples have equal means can be rejected. We observed difference of 0.01 between the agent scores test problems compared to train problems, which according to the null distribution has probability of occurring by 83%. We thus have more confidence in the means being equal than not according to the test. The differences between PROST and both the training and test sets are significantly larger, with a difference of -0,26 between PROST and the VEJDE scores on the test set. The differences mean with the p-values from the permutation test is shown in Table T] and a plot of the null distribution from the test is shown Appendix
From the average test scores per domain, we observed varying differences PROST between problem domains. On some domains, such SkillTeaching and SysAdmin there was not significant difference between the scores of PROST and the mimic policy. Two VEJDE scores fall under and average of 0.5, those for Academic.dvisiin and Navigation. We noted that PROST barely performs better than the lower bound return on certain instances of Academic.Adviste which is a possible cause of the low mimic performance on this domain. Mimic test scores for each domain are shown in Table
5.2 Reinforcement Learning
Training VEJDE policies for all domains using reinforcement learning took approximately 5 hours, which repeated five times took total of 35 hours. Training one MLP policy for each of the 90 problem instances took approximately 24 hours. After training, all policies were executed on each of the problem instances for 100 episodes, and the average return per instance was recorded. We used the same evaluation data for PROST as was used in the imitation learning experiment. To create a summary score for over all domains, we performed a permutation test with 10 samples to compare the test problem scores of the VEJDE agents with the scores of the MLP policies and PROST on the same problems, with the null hypothesis that the agents have equal average scores. If assume that reject the mill hypothesis with p 0.05, we not do
16We used https: //docs. http://ccccccccc......./ sttp:p/wrpplllssssst/eeeee/ee/es stt.pppptttatt..mmmtttitiooo tttpttttttttttte html the

---

Published in Transactions on Machine Learning Research (1/2026)
Table 3: Difference average score between VEIDE RL agents, instance-specific MLP agents and PROST on test instances, averaged across all problem domains. Pnott probability according to null distribution produced by permutation testing that P(X 2 |/1 p2l)).
Comparison
141
P2
Pnail
VEJDE MLP
0.05
0.17
VEJDE- PROST
-0.43
0.00
MLP- PROST
-0.48
0.00
Table 4: Average normalized test. instances for agents trained using RL and PROST, per problem
domain.
Domain
VEJDE μ
MLP μ o
PROST μ p=c
Skill'Teaching
0.84 + 0.10
0.83 + 0.12
0.99 + 0.02
AcademicAdvisinee
0.77 +: 0.39
0.19 + 0.39
0.41 + 0.46
SysAdmin
0.75 + 0.23
0.89 = 0.11
0.94 0.09
Traffic
0.61 + 0.24
0.11 0.12
1.00 0.00
Tamarisk
0.56 + 0.26
0.61 + 0.11
1.00 0.00
Crossing Traffic
0.42 + 0.19
0.45 + 0.25
1.00 + 0.00
Navigation
0.01 + 0.03
0.13 = 0.33
1.00 + 0.00
Elevators
0.00 + 0.00
0.21 = 0.19
1.00 + 0.00
so for the difference between the mean scores of the MLP and VEJDE agents, but we can for the difference between PROST and the other agents. There was thus, in average, not significant statistical difference between the average scores of the VEJDE agents and the MLP agents, which consider good given that the VEJDE agents were not trained on the considered instances. Both RL agents have significantly worse scores than PROST in average. The statistics of the test are shown in Table 3. and we have included plot of the resulting null distribution from running the test in Appendix
We observed the VEIDE agent achioved significantly higher scores than the MLP agents on the domain Traffic, and on one domain, AcademicAdvising, the VEJDE agent had higher scores than both PROST and the MLPs. On the domain Navigation and Elevators the VEJDE agents had significantly worse scores than the other agents, well as their imitation learning counterparts. The scores of the MLP agents these domains, though slightly higher than those of the VEJDE agents, are also relatively low, indicating a general difficulty in finding policies for these domains using reinforcement learning. Normalized test scores for each domain are shown in Table 4
12

---

Published in Transactions on Machine Learning Research (1/2026)
6
Related Work
There have been a number of previous works that combine machine learning on graphs with decision problems, and VEJDE piece-wise overlaps with several of these. We summarize the primary differences and overlapping features with a non-cxhaustive selection of related works in Table 5
There exists a large body of work in the realm of relational reinforcement learning. The book by Van Otterlo (2009) covers much of research in the area prior to the 2010s, which is composed of both purely symbolic and non-ncural machine learning mothods for both value-based and policy-based relational reinforcement learning. The survey by Mohan et al. (2024) covers more recent works, as well as some older, from a more general perspective of incorporating structure in RL. They use the term "side information" to refer to various forms of structural information provided to agents to improve learning, but which is not part of the typical MDP formalism. Side information used by various works include data abstractions, information about system dynamics and goal formulations, which lypically improve data efficiency or policy generalization ion at the cost of requiring more prior knowledge about the problem or computational power. By their categorization, the only side information we use in VEJDE is data abstraction, where we assume that there cxists a data description language that can describe object classes and relations from a given problem domain. This is, in our opinion, a significantly lighter assumption than for instance (Sharma et al.] (2023) makes, which is full knowledge of the dynamic Bayesian network in order to construct the input graph for the policy.
An alternate method of inductive policy generation which we consider interesting is decision list learning. The state is represented with symbolic logic, but rules for action selection are represented explicitly in a human-readable manner rather than implicitly encoded as weights in a neural network. [eern et al. (2006) presents a symbolic method that searches for a policy through a combination of beam-searching and policy iteration. Neural methods for decision list rule generation that incorporate numeric optimization have also been proposed (Hazra & Raedt, 2023 Delfosse et al. 2023), ; which in some cases assign numeric weights to the rules in order to make the poliey probabilistic. Representing rules in human-readable manner has an immediate benefit of being able to manually analyze and interpret the policy, which is good for transparency, but requires a method for scarching a potentially large space of possible rules. We also recognize the possibility to extract explicit rules from a trained MPNN policy post-hoc.
The topic of generalization in reinforcement learning for classes of problems has also been covered from the perspective of deep learning. In their survey of RL generalization, Kirk et al. (2023) separate learning problems into three categories: singleton problems where the training and test environments are the same; Independent and Identically Distributed (IID) generalization problems, where the test environments are different but sampled from the same distribution as the train environments; Out of Distribution (OOD) generalization problems, where the test environments are sampled from a different distribution. An example of such problems is the collection "ProcGen", which define problems using distributions over variables such that randomly generated problem instances can be sampled from them (Cobbe et al. 2020). By their classification, we are focusing on IID generalization of the agent in our evaluation.
6.1 Deep Relational Reinforcement Learning
The works which we consider closest in type to ours are those which use graph-based state representations to predict action probabilities in a model-free learning context. The sequential method we use to sample actions is influenced by Janisch (2024), who presents an autoregressive decoding scheme to sample the components of actions, which allows for both nullary and higher-order actions. For actions with an arity greater than one, additional rounds of message- passingggpinngggggg are executed after sampling an object, marking objects that have already been selected with additional feature. Unlike us, they use simple graphs to represent the facts of the state, which limits the method to problems with binary relations. Agents are trained using policy gradient optimization in an unsupervised manner. They evaluate their method on implementations of Sdmid Blockworld and a modified version of the game Sokoban.
Garg et al. (2019), like us, use reinforcement learning to train policies based on the RDDL domains SysAdmin, Game of Life and Academic Advising. These are all represented as a simple graph of binary relations between objects, with single unary action. While this work use similar evaluation as us, we can not compare our
13

---

Published in Transactions on Machine Learning Research (1/2026)
results directly with them, they too present normalized scores but have not calculated them in relation to any baseline policies. Therefore, we can not determine if their method performs better than random or null policy on these domains. Additionally, they train and test on hand-picked subsets of instances, rather than all instances.
Ammanabrolu & Riedl (2019) offers a somewhat different perspective, coming from natural language processing context. Agents are evaluated on text-based game, where an agent has navigate a simulated space and solve puzzles. They represent observations using simple graph, which use word embeddings node features, and select actions Resource Description Framework (RDF) triplets, on the form (subject, verb, object).
We also wish to highlight a set of works we refer to as object-orienled reinforcement learning, which includes works by Guestrin et al. (2003). Diuk et al. (2008) and more recently Zambaldi et al. (2019). We categorize these works by the fact that they model the state using conditionally independent objects, but without explicit relationships. [Mohan et al. (0224) classifies these works as faclored representations, as opposed to relational representations that include relations, we do. A number of works in the context of multi-agent reinforcement learning, such as Foerster et al. (2018). arguably fit this category when the complete system state is factorized into discrete states or observations for each individual agent. The object-oriented approach is practical in the sense that one does not have to define or observe relationships between objects, but tends to have worse scaling properties since approaches typically compares every entity to one another. It is, however, less sensitive to violations of the homophily assumptions which MPNNs rely on, i.e. that things which are connected in the graph are related.
6.2 Automated Planning
Many works that use symbolic logic to represent problems operate in the research area of planning, which tends to assume deterministic system models, as opposed to MDPs with probabilistic state transitions. Nevertheless, we share features with multiple works within this research area. For instance, [Chen & Thiébaux (2024) and [Stählberg et al. (2023) both use factor graph state representations, but predict heuristic scores over subsequent states rather than probabilities over actions. Chen et al. (2024) use the WT. algorithm to generate latent states, which are then used to produce heuristic scores. In a subsequent work, [Cenn & Thiébaux 2024) exlends the WL algorithn to incorporate numeric features, and evaluate their method on a single deterministic goal-oriented problem, Blockworld. They train their models in a supervised manner based on pro-calculated optimal plans. We find this pair of works interesting in that they show that a computationally simpler representation can be used generate latent states, at least for the singular problem they investigated. In Ståhlberg al. (2023) agents are trained in unsupervised manner using reinforcement learning, well value function using supervised learning. They evaluate their method several problems defined in PDDL. In a subsequent work, (Säählberg et al. (2025) focuses on methods for higher-order action selection, but these are only evaluated with supervised learning.
14

---

Published in Transactions on Machine Learning Research (1/2020)
Table 5: Summary of features in a selection of related works in graph-based decision policy learning compared to VEJDE. Only works that base their states on observalions, rather than environment dynamics, are included. The "KG" column tells the state is bounded to only include binary relations, and the "action arity" column shows the number of arguments of actions, when actions are used rather than heuristics.
Work
Supervised learning
Probabilistic problems
Continous features
KG
Action arity
Ammanabrohu & Riedl 2019
No
No No
Yes
2
Garg et al. (2019)
No
Yes
No
Yes
1
Stählberg et al.
(023)
No
No
No
No
N/A
Chen &z Thiebaux [2024
Yes
No
Yes
No
N/A
Janisch [2024]
No
Yes
No
Yes
[0,
1, 2]
Ståhlberg et al.
(0025)
Yes
No
No
No
2
Vejde (Our work)
No
Yes
Yes
No
[0, 1]
15

---

Published in Transactions on Machine Learning Research (1/2026)
7
Discussion
This section covers our thoughts on the results, the design decisions made with VEJDE and the problem selection.
7.1
Agent Performance
7.1.1
Vejde
The VEJDE agent trained with RL received average scores higher than the trivial policies on 8/10 domains. We consider this positive indication that VEJDE can be used to represent policies that generalize to unseen problem instances within a class of problems. We observed a negative difference in score between the mimic policy and RL policy for most problem domains. Elevators has the most significant difference, with an 87 percent unit drop between the experiments. Since the problems and VEJDE architectures were the same for both experiments, we attribute this difference to PPO not discovering a set of policy parameters that work and those found when imitating PROST. It remains an open question as how this difference can be reduced. Navigation and CrossingTraffic occur in the set of problems the VEJDE policies receive the lowest scores in, both in the reinforcement and imitation learning experiments. They are both grid-based, with discrete cartesian coordinates represented objects and only nullary actions. These are arguably not the kinds of problems that we would choose to use VEJDE with, in that representing a uniform grid as a graph is needlessly complicated and the number of possible actions is constant regardless of the grid size. Nevertheless, they fit the selection criteria we set, so we feel that it would be unfairly selective to exclude them. They are arguably a good test of the architectures ability to generate whole-graph embeddings, in that they can be regarded as graph classification tasks, but the hypothesis that a whole graph aggregation is needed to solve these problems remains untested.
7.1.2 MLP
The transductive MLP policies received higher average scores than VEJDE agents for individual instances, meaning that they represent a good alternative to VEJDE if generalization is not a priority. If the number of entitios in the problem changes, additional policies need to be trained to account for the different input space or an input space that is agnostic to the number of entities need to be used. In theory, VEJDE policy can only be as good as MLP policy on a given instance, assuming that the MLP policy is optimal, and the inductive policy is also optimal for all problem instances. If the inductive policy can not be optimal for all instances due to problem complexity, we would expect a score of the inductive policy to occur between those for the optimal policy for the instance and the trivial policies. We observe, on average, that the scores of the VEJDE agents were statistically close to the scores of the MLP agents, In practice, due to the somewhat unstable optimization that deep RL constitutes, both the MLP and GNN may converge to local minima. This is our primary explanation to why VEJDE policies scored higher than MLP policies some domains. We could strengthen our evaluation by training five copies of MLP policies with some variation, such as different initialization values, to pair with the five VEJDE agents using different training sets. However, given the long training time required to train the 90 MLP policies, we opted against this. We hypothesize that our primary takeaway, that the scores of the inductive VEJDE policies is correlated with the transductive MLP policies, will still hold.
7.1.3 Prost
PROST receives the highest scores on most problems, showing its strong capability to search for optimal actions. However, the main drawback of PROST that it always dependent on an accurate generative model of the problem during test-time inference. This can be difficult to accommodate for use-cases where an accurate system model is not available, or the execution environment does not have the resources to perform continuous simulations. In contrast, the RL policies only need the simulator during training but do not perform any planning when choosing actions. The cost of the high scores with PROST is also paid with a much higher inference time, which we had to count in days, as opposed to minutes for the RL policies.
17e practical benefits of having handle one agent per domain as opposed ten is hard quantify, but insignificant.
16

---

Published in Transactions on Machine Learning Research (1/2026)
Despite strong overall performance, PROST performs little better than the do-nothing policy certain problem instances, most notably from the domain Acudemic.Arising We are unsure if this is caused by PROST not being well-adapted for this particular problem, or the instances being defined such that doing nothing is indeed the optimal course of action. The higher average scores of the VEIDE agents suggests the latter may not. be the case, however. The low scores of PROST on this domain is also reflected the mimic policy, which are significantly worse on the problem compared to its RL counterpart.
7.2 Alternative State Representations
The maximum arity of facts across the problems we evaluate with is two. We could therefore represent the state for all included problems as a simple graph consisting of only nodes and edges, as Janisch (2024) or Garg et al. (2019). This is format which is also known as Knowledge graphs (KGs), or RDF graphs, within certain rescarch contexts (Ammanabrolu & Riedl 2019). However, it is not common for works that handle KGs to incorporate nuneric features, or object-specific features at all, which require. Fey et al. (2024a) presents a graph representation directly influenced by relational databases, which extends simple graphs to include heterogeneous data. They group unary attributes of entities into fixed-sized vectors, analogous to the table columns in relational databases, forming a heterogencous graph. The bipartite reprosentation we use is more flexible in that entities can be represented with variably-sized sets of unary attributes. Being able to ignore missing or unseen attributes without padding is practical for problems where there are many possible object attributes, but only a small subset present at given time. We may, for instance, want to define many possible alerts for hosts in network intrusion detection system, while only including the alerts that have actually been observed in the agent input.
In addition to changing the graph structure, there are also alternate methods for encoding the information in the graph, such as the graph attention method we describe in Appendix H. The conceptually simpler WL algorithm can be used instead of neural peessag--psssnng to encode the nodes and graph into latent states. However, for domains with continuous state variables the number of possible states becomes infinite, and we lose the ability to interpolate between latent states. Modifications can be made to the WL to allow for continuous representations (Chen & Thiébaux 2024). We have also noted methods for belief propagation factor graphs which incorporate neural networks, such as the one by Kuck et al. (2020), which could provide a different method for pressage-passing compared to the WL algorithm.
7.3 Limits to Generalization
Problems defined in RDDL arguably represent an ideal situation for structural generalization. The dynamics and reward are specified in factored and lifted manner, meaning that we can map objects to their respective types and not lose instanco-specific information. The dynamics are also constant across problem instances and the observations use the exact same predicates that are given to the agent, meaning that the value function and optimal policy can be defined using the language. In a realistic setting, there may be a disconnect between the data abstractions and the system they represent. This arguably forms a partially observable MDP, or "context" MDP as described by Kirk et al. (2023) which each require more complex solutions methods than for the fully observable problems consider in this evaluation.
17

---

Published in Transactions on Machine Learning Research (1/2026)
8 Conclusion
We have developed and evaluated framework that combinos graph learning with model-free RL to find inductive policies for structured MDPs, which we call VEJDE. The design allows policies to handle states which vary in both size and structure, as well as variable amounts of possible actions. We evaluated VEJDE policies on eight problem domains defined with the Relational Dynamic Influence Diagram Language, training policies both by examples provided by the planner PROST, and with reinforcement learning. From our results, found that the VEJDE policies had, in average, test performance on unseen instances not significantly different to MLP policies trained each individual instance We also found that some problem domains, policies trained with RL performed significantly worse than the corresponding policies trained with imitation learning. This leads us to a conclusion that different optimization procedures may be needed, such as improved exploration, to close this difference. Given that we as a society store much our data, using relational databases, we see a need to explore methods that allow us to apply neural networks to the data in the way it is stored. Previous work has explored the use of neural graph learning on databases for supervised learning, and in this work we show that similar methodology can be used for reinforcement learning. Incorporating structure like relational databases provides in the design of the architecture facilitates structural gencralization of agent policies, which we believe improves the real-world usability of reinforcement learning solutions.
Acknowledgments
The authors would like to thank the authors of the pyRDDLGym library for making the problem domains, the MLP policy and Prost easily accessible for evaluation, and for responding questions that arose during the work.
18

---

Published in Transactions on Machine Learning Research (1/2026)
References
Prithviraj Ammanabrolu and Mark O. Riedl. Playing text-adventure games with graph-based deep rein- forcement learning. In Jill Burstein, Christy Doran, and Thamar Solorio (cds.), Proceedings of the 2019 Conference of the North American Chapter of the Associalion for Compulational Linguislics: Human Language Technologies, NAACL-HLT 2019, Minneapoliss MN, USA, June 2-7, 2019, Volume 1 (Long and Short Pupers), pp. 3557 3563, Association for Computational Linguistics, 2019. doi: 10.18653/V1/ND 1358. URL https:///oi org/ 10. 18653/v1/n19-
Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nee net, 2020. URL https://opeereviie
het/forum?id-r111777
Donald D. Chamberlin and Raymond F. Boyce. Sequel: A structured english query language. In Proceedings of the 1974 ACM SIGFIDET (Now SIGMOD) Workshop on Dala Descriplion, Access and Control, SIGFIDET '74, pp. 349-264, New York, NY, USA, 1974. Association for Computing Machinery. ISBN 9781450374156 doi: 10.1145/ 10.1145/800296 888886000188350
URL atttps://ooi org/10. 1145/800296... 0015/88009968115555
Dillon Z. Chen and Sylvie Thiébaux. Graph learning for numeric planning. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Urrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neu- rul Information Processing Systems 38: Annual Conference on Newral Information Processing Systems 2024, NewrIPS 2024. Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http::/papers. http://ppprr...p....... cc/ paper fillss/pperr/22244 htt.0/////aaaa////////////////// Dttpa///oaa..oooaaaeeeeaaaaaeee-
html
Dillon Z. Chen, Felipe W. Trevizan, and Sylvic Thiébaux. Return to tradition: Learning reliable hcuristies with classical machine learning. In Sara Bernardini and Christian Muise (eds.). Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling, TCAPS 2024, Bansf, Alberta, Canada, June 1-6, 2024, pp. 68 76. AAAI Press, 2024. doi: 10. L0.1609/ICAPS..3B0 /33.L/AA........1........ URL https://doi.oor ort../rgggo//o 10. (t/69//ccas... 1184411114466
Karl Cobbe, Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 19-18 18-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 2048 2056. PMLR, 2020. URL http://proceeeinnss mlr haa..pprees//119/cbbeeeee
html
E. F. Codd. A relational model of data for large shared data banks. Commun. ACM, 13(6):377 387, June 1970. ISSN 0001-0782. doi: 10.1145/3622 062334.3626888 URL https: 111gg//6...4/333344...4 3626655
Quentin Delfosso, Hikaru Shindo, Devendra Singh Dhami, and Kristian Kersting, Interpretable and explainable logical policies via neurally guided symbolic abstraction. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Newral Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL http::/papers. nips.cc/ppsaeeeeee cc/paper /221e///pppr//223/ 314f006544a22700a174444448353333 wtte-e-bbbtttttceeee
html
Carlos Diuk, Andre Cohen, and Michael L. Littman. An object-oriented representation for efficient re- inforcement learning. In William W. Cohen, Andrew McCallum, and Sam T. Roweis (eds.), Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, June 5-9, 2008 volume 307 of A ACM International Conference Proceeding Series, pp. 240-247 247. ACM, 2008. doi: 01444///19106619999
URL
1145/1399016.1... 1390187
Saso Dzeroski, Luc De Raedt, and Kurt Driessens. Relational reinforcement learning. Mach. Learn., 43(1/2): 7 52, 2001. doi: 10.1023 A: 10779994059958
Alan Fern, Sung Wook Yoon, and Robert Givan. Approximate policy itcration with a policy language bias: Solving relational markov decision processes. J. Artif. Intell, Res., 25:75-118, 2006. doi: 10.1613/JAIR.1700 URL httt:p::/aai..or//oo..ii/0///
19

---

Martin Grohe. The logic of graph neural networks. In Proceedings of the 36th Annual ACM/ Symposium on Logic in Computer Science, LICS '21, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781665448956. doi: 2.110//IICS5222442001..09 Published in Transactions on Machine Learning Research (1/2026)
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorrh Geometric. In ICLR Workshop on Represenlation Learning on Graphs and Manifolds, 2019.
Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Position: Relational deep learning graph representation learning on relational databases. In Forty-first International Conference on Machine Learning, 1CML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.ng net, 2024a. URL https::/ wttpeeerreiiee.eee/fouuu... net/forummid BIMPHniyCP]
Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Position: Relational Deep Learning- - Graph Representation Learning on Relational Databases. In Proceedings of the 41st International Conference on Machine Learning, pp. 13592-13607. PMLR, July 2024b. URL htttps://proceeddings... mml press/v235/fey22 html ISSN: 2640-3498.
Jakob N. Foerster, Gregory Farquhar, Triantaffllos Afouras, Nantas Nardelli, and Shimon Whiteson. Coun- terfactual multi-agent policy gradients. In Proceedings of the Thérty-Second AAAI Conference on Arlificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, 2018. ISBN 978-1-57735-800-8.
AAAI Press,
Sankalp Garg, Aniket Bajpai, and Mausam. Size independent neural transfer for RDDL planning. In J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, and Siddharth Srivastava (eds.), Proceedings of the Twenty-Nine Ninth International Conference on Automated Planning and Scheduling, ICAPS 2019, Berkeley, CA, USA, July 11-15, 2019, pp. 631 636. AAAI Press, 2019. URL https://ojs.co aaai. , org/index. iidex. index.ppp//
URL https:
//doi.org 1119/ 2021.907067771.
Carlos Guestrin, Daphne Koller, Chris Gearhart, and Neal Kanodia. Generalizing plans to new environments in relational mdps. In Georg Gottlob and Toby Walsh (eds.), LJCAI-03, Proczedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Merico, August 9-15, 2003, pp. 1003- 1010. Morgan Kaufmann, 2003. URL http::/ijcai. htt.://aaa......oooooeeee/////// Ptths//aperrr//eee 144.pdf
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse control tasks through world models. Nature, 640 653, 2025. doi: 14.1033//411556--25---777--4
Rishi Hazra and Lue De Raedt. Deep explainable relational reinforcement learning: A neuro-symbolic approach. In Danai Koutra, Claudia Plant, Manuel Gomez Rodriguez, Elena Baralis, and Francesco Bonchi (eds.), Machine Learning and Knowledge Discovery in Dalabases: Research Track European Conference, ECML PKDD 2023, Turin, Italy, September 18- 2023, Proceedings, Part IV, volume 14172 of Lecture Notes in Computer Science, pp. 213 229. Springer, 2023. doi: 10.1007/978-3-031--83222 https:///oi. org 1 030-778------11-42-1--11-1-
13. URL
Jaromír Janisch. Applications of Deep Reinforcement Learning in Practical Sequential Information Acquisition Problems. PhD thesis, Czech Technical University, 2024.
Thomas Keller and Malte Helmert. Trial-based hcuristic tree scarch for finite horizon MDPs. In Proceedings of the Twenly- Third International Conference on Aulomaled Planning and Scheduling (ICAPS 2013), pp. 135-143. AAAI Press, 2013.
Kristian Kersting and Kurt Driessens. Non-parametric policy gradients: a unified (reatment of propositional and relational domains. In William W. Cohen, Andrew McCallum, and Sam T. Roweis (eds.). Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, June 5-9, 2008, volume 307 of ACM International Conference Proceeding Series, pp. 456-463. ACM, 2008. doi: 10.1145/1390 11155//195666 111.56..133 139021.. URL http::ttt:///e /ttttp::/ddi..or/11...tot 11w.......1111111....1 1390214
20

---

Published in Transactions on Machine Learning Research (1/2026)
Mitchell Kiely, Metin Ahiskali, Etienne Borde, Benjamin Bowman, David Bowman, Dirk Van Bruggen, KC Cowan, Prithviraj Dasgupta, Erich Devendorf, Ben Edwards, Alex Fitts, Sunny Fugate, Ryan Gabrys, Wayne Gould, H. Howie Huang, Jules Jacobs, Ryan Kerr, Isaiah J. King, Li Li, Luis Martinez, Christopher Moir, Craig Murphy, Olivia Naish, Claire Owens, Miranda Purchase, Ahmad Ridley, Adrian Taylor, Sara Farmer, William John Valentine, and Yiyi Zhang. Exploring the efficacy of multi-agent reinforcement learning for autonomous cyber defence: A CAGE challenge perspective. In Toby Walsh, Julie Shah, and Zico Kolter (eds.), AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, Februory 25 March 2025, Philadelphia, PA, USA, pp. AAAIV339228331158 URL https:///o// org/ 1 1609/ aaai. 009918..3199
AAAI Press, 2025. doi: 10.1609/
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of zero-shot generalisation in deep reinforcement learning. J. Artif. Intell. Res., 76:201 264, 2023. doi: 10.1613/JAIR...4111 URL
https://doi. 10. 1rgg/...113//ai........ 1tt.1//aaarr..111.....
Jonathan Kuck, Shuvam Chakraborty, Hao Tang, Rachel Luo, Jiaming Song, Ashish Sabharwal, and Stefano Ermon. Belief propagation neural networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Mlrii-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL
wew.gip...u.p..... cc/papper/222//aaee haahh/
Abstrac html
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua. Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations,
ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Aditya Mohan, Amy Zhang, and Marius Lindauer. Structure in deep reinforcement learning: A survey and open problems. J. Artif. Int. Res., 79, April 2024. ISSN 1076-9757. doi: 10.1613/jair. URL
https://doi. org/ 10. 1613/jair... 1. 15703
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty- Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty- First Innovative Applications of Artificial Intelligence Conference, TAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, FAAT 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pp. 4602440000 4609. AAAI Press, 2019. doi: 10.1609/ AAAL W33.V..331010000000 URL hatpps///don http://oo..org///// wrg/o0..//oo..... 1609/ waa.////aa........ v33101 33014602
Jakob Nyberg and Pontus Johnson. Structural generalization in autonomous cyber incident response with pressage-passing neural networks and reinforcement learning. In IEFE International Conference on Cyber Security and Resilience, CSR 2024, London, UK, September 2-4, 2024, pp. 282 289. IEEE, 2024. doi: URL attps://dol org/ 10. 1109/ 10/11/1199SSS1 CSR61664.66666 2024. 10679456
10.1109 /C////6662.222244444
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programminng Wiley Scries in Probability and Statisties. Wiley, 1994. ISBN 978-0-17161977-2. doi: 17.1002/97704403166887 URL
https:///oi. org
Raymond Reiter. On closed world data bases. In Hervé Gallaire and Jack Minker (eds.), Logic and Data Bases, Symposium on Logic and Data Bases, Centre d' d'études de recherches de Toulouse, France, 1977, Advances in Data Base Theory, pp. 55 76, New York, 1977. Plemun Press. doi: 10.10077998--14464---18 3384--8---3--33
3.
URL attpp::/daoi.org/11.11000
Raymond Reiter Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT Press, 2001. ISBN 978-0-262-52700-2 978-0-262- 2-23111-4 978-00-55544480-5 978-0-262-18218-2
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 3 edition, 2010.
Scott Sanner. Relational dynamic inffuence diagram language (rddl): Language description, 2010. URL
https://users.. cecs. anu. edu. au/-ssaneer/IPPC Ttt.:/PPPPPP21DDD.PPP.P
21

---

Published in Transactions on Machine Learning Research (1/2026)
Victor Garcia Satorras and Max Welling. Neural enhanced belief propagation on factor graphs. In Arindam Banerjee and Kenji Fukumizu (eds.), The 24th International Conference on Artāficial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning
Research, pp. 685-693 PMLR, 2021. URL httpp://proceedings . mww.mrr..eesseeee. html
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High-dimensional contimuuu control using generalized advantage estimation. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, Son Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http::/aaxii..rrrttt http:///xxxvv.oo////// aa//a/bb///50/ 02438
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707 /1/07700006777 2017. URL http://arxiv.. wrgg abs/ 1707.
Vishal Sharma, Daman Arora, Mausam, and Parag Singla. Symnet 3.0: Exploiting long-range influences in learning generalized neural policies for relational mdps. In Robin J. Evans and Ilya Shpitser (eds.), Uncertainty in Artificial Intelligence, UAI 2023, July 31 August 2023, Pittsburgh, PA, USA, volume 216 of Proceedings of Machine Learning Research, pp. 1921 1931. PMLR, 2023. URL https: pottps://pan //pppee///rooeeiingg mlr. www.ppees/vv16 2ttp:////221////ra2aaa.... wwwamaa3c..haaacmeeemaa html
Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning more expressive general policies for classical planning domains. In Thirty-Ninth AAAI Conference on Artificial Intelligence (AAA1-25), 2025.
Simon Ståhlborg, Blai Bonet, and Hoctor Geffner. Learning general policies with policy gradient methods. In Pierre Marquis, Tran Cao Son, and Gabricle Kern-Isberner (eds.), Proceedings of the 20th International Conference on Principles of Knowledge Represenlation and Reasoming, KR 2023, Rhodes, Greece, September 2-8, 2023, pp. 647 657, 2023. doi: 10.24963/ /44966/KK.2000 KKR.2023/66 /63. URL http::ttt////// //doi. org/ 10. 24963/kr6 /r 2023/63
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Newrocomputing, 568:127063, 2024. ISSN 0925-2312. doi: (tt.://i..orr.10111/......... 2023..276............ 127063. URL https:///ww/t http://wwccieeeereeet.ccoooessss artiCle//1//0022222220018
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ayal Taitler, Michael Gimelfarb, Jihwan Jeong, Sriram Gopalakrishnan, Martin Mladenov, Xiaotian Liu, and Scout Sanner. pyrddlgym: From rddl to gym environments, 2024. CRL https: wwwpw//g/////////// aba/2211
05939
Isaac Symes Thompson, Alberto Caron, Chris Hicks, and Vasilios Mavroudis. Entity-based reinforcement learning for autonomous cyber defence. In Ali Dehghantanha, Reza. M. Parizi, and Gregory Epiphaniou (eds.), Proceedings of the Workshop Autonomous Cybersecurity, AutonomoussCyber 2024, Salt Lake City, UT, USA, October 14-18, 2024, pp. 56-67. ACM, 2024. doi: https:://bo..or//10..1 101///00...14/33999333333 36908355
URL
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Vicent,,,, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: standard interface for reinforcement learning environments, 2024. URL
17032
Mauro Vallati, Lukas Chrpa, Marek Grzeš, Thomas Leo McCluskey, Mark Roberts, Scott Sanner, and Managing Editor. The 2014 international planning competition: Progress and trends. AI Magazine, 36(3): 90-98. Sep. 2015. doi: 10. 1609 13mm...36.3.... v3613.2571. 2571. URL hhttps://jjs wtwoossssaaaa....aa.aaa.aaa..a.a aaai.arg/ htt///mmaazzineiinneee hhtp:/ almagezinee/arttcll//eeee
Martijn Van Otterlo (ed.). The Logic of Adaptive Behavior: Knowledge Representation and Algorithms for Adaptive Sequential Decision Making under Uncertainty First-Orden and Relational Domains. Number v. 192 in Frontiers in Artificial Intelligence and Applications. Ios Press, Amsterdam Washington, D.C, 2009.
ISBN 978- 977-1-60750-406-1 978-1-4416-166864
22

---

Published in Transactions on Machine Learning Research (1/2026)
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, 1CML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings PMLR, 2022. URL
of Machine Learning Research, pp. v162/ wttp//am.gnaaaaaammmm html
mlr. press//
Melody Wolk, Andy Applebaum, Camron Dennler, Patrick Dwyer, Marina Moskowitz, Harold Nguyen, Nicole Nichols, Nicole Park, Paul Rachwalski, Frank Rau, and Adrian Webster. Beyond cage: Investigating generalization of learned autonomous network defense policics. In International Conference on Machine Learning Workshop, ML4 Cyber. International Conference on Machine Learning Workshop, ML4Cyber, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.nen net, 2019. URL http:://pppueeeeiee.eeeeerrrrrrs
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tin Liu. Do transformers really perform badly for graph representation? In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 28877 28888, 2021. URL htttps://ppoceeddnngg meeriii neurips /ttp:///00/0..012221111000000000
Abstract .html
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, Murray Shanahan, Victoria Langston, Razvan Pascanu, Matthew Botvinick, Oriol Vinyals, and Peter Battaglia. Deep reinforcement learning with relational inductive biases. In International Conference on Learning Representations, 2019. URL https: //openreview.c http://eeeee/ooommm/dddaaaaaaaaa
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. In The Fleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview .nct, 2023. URL
23

---

Published in Transactions on Machine Learning Research (1/2026)
9 Appendices
A Example State and Actions
Given the predicates (P.Q, 2, and objects {01, V/. U2), particular state can be described the set Z(n) Z(n) 5, (42, C}. Given the action symbols {Ai, A2), which can have different arities and type restrictions, possible set of actions for the state may be {A1 (z1); A1 (1) (12)), A2(x1)) ( In the resulting bipartite graph, = (r,, and = (P(x)), Q(11,91), Z(n) = 5, (1). C).
(P(z)))((m,,)))
B Implementation Details
This appendix contains details which are less important in theory, but are relevant to the practical aspects of the implementation.
B.1 Batching
Since cach sample can vary in size, the common batching method of stacking vectors can not be used unless padding is added. We opt for the batching method used by graph learning code libraries such as Py Torch Geometric (eey & Lenssen 2019), where the adjacency matrix of the graph is stored in a COO matrix format. Thus, the node and adjacency vectors for each graph are concatenated in order to produce a single, albeit disconnected, graph.
B.2 Action Masking
We calculate the probability each action symbol for every object in the state, leading to the joint probability function including literals that are not possible according to the argument types of the action symbols. Under the assumption that taking invalid actions is equivalent doing nothing, this leads to unnccessary exploration during training, the agent has to explore potentially large number of parameter combinations that will never be viable. We thus mask out parameter combinations that are incorrect according to the types of the action symbol. In practice this means that the weights of invalid predicate-object combinations are assigned large negative values, so that the corresponding probabilities becomes zero.
B.3 Code Library Design
VEJDE designed to be domain-agnostic, and is built upon the Gymnasium interface (Towers et al. 2024h. The heart of the implementation a relational data model class, where predicate symbols, action symbols and object types of the particular problem domain are specified. This class is then used shape the GNN and construct the graph representation of the state. We use a RDDL-specific instance of this class for our evaluation, which pulls the required information from RDDL domain specification. In order to apply the library to a new problem domain, relational data model for that domain has to be defined.
B.4 Score Normalization
Returns are normalized according to the method used in IPPC 2014 (Vallati et al. 2015): For each instance, lower bound return, Riows is the maximum average return received from taking random actions doing nothing. A maximum return, Rmax for an instance is the highest return obtained among the evaluated methods. The score of an agent on given instance is then Ri.i-RRRoo..//RRm..----
where I is the average return over a given number of episodes. Thus, a score means that an agent performs worse or equal to acting at random or doing nothing, and represents always having the highest score among the compared agents. We emphasize that a score of 1 does not imply that the agent follows the optimal policy of the MDP, which do not have access to for comparison.
24

---

Published in Transactions on Machine Learning Research (1/2026)
Parameter Name
Value
Graph Neural Network
Embedding size
16
Activation function
tanh
Message passing layers
Critic prediction heads
Aggregation function
max
Proximal Policy Optimization
Policy ratio clip factor
0.2
Entropy loss coefficient
0.1 0.100.001/0.0001
Critic loss coefficient
1.0
GAE À
0.95
Rollout steps
1024
Update epochs
10
General Optimization
Optimizer
Amsgrad
Max. grad.2-norm
1.0
Total steps
1 500 000
Batch size
16
Number of parallel envs.
16
Discount factor
0.99
Learning rate
10 10-3 3 1/133/1////////
11004/10-6
Exponential average a
0.99
Table 6: Hyperparameters for reinforcement learning of VEJDE policics. Learning rate and entropy coefficient was lowered every 500 000 steps.
C Hyperparameters
We used the same set of hyperparameters while training the GNN for all domains, which were chosen manually based on training time and returns observed in preliminary experiments on the training set. rudimentary annealing scheme was used while training VEJDE agents, where the learning rate was lowered by factor of 10 for every 500 000 samples. The coefficient of the entropy term was also lowered after 500 000 samples, guard against the policy converging to local minima early.
A source of difficulty in assigning single set of hyperparameters was that the return values of the different domains, and even instances within the same domain, can have vastly different magnitudes. To improve the robustness of the optimization, we used two tricks from Dreamer (Hafner et al. 2025). The first is to scale RG and the value estimate by the symlog function, and the second is to scale the advantage A by an exponential moving average of the return value range. The advantage A, was calculated using generalized advantage estimation (GAE) (Schulman et al.) 2016), as is common implementations of PPO.
Table summarizes hyperparameters used in VEJDE during experiments.
D Problem Selection & Extensions
In selecting the domains for evaluation, we excluded problems based set of filters, which comment in this appendix as stepping stones for extensions to the work.
D.0.1 Continuous Actions
Since the policy is parameterized by neural networks, and PPO has previously used for continuous action selection, including actions with continuous values is theoretically straightforward but would require changing
25

---

Published in Transactions on Machine Learning Research (1/2026)
the formulas for action probabilities and value estimations to account for the additional choice that the action value represents. Currently, the value for all actions is assumed to be logical "True".
D.0.2 Higher-Order Actions
We define higher-order actions actions which involve more than object. If set the limit to at most binary actions, predicting the action is roughly equivalent to link prediction in the greater context of graph learning. Implementations of higher-order actions tend to require that tuples of objects are compared, which scales poorly if done naively (Ståhlberg et al. 2025 Ammanabrolu & Riedl 2019 Morris et al. 2019). For binary actions, the number of argument combinations scales quadratically, trinary cubically and so on. Autoregressive sampling of action arguments, as done by [anischi (2024), is an alternative method for producing higher-order actions which scales better than evaluating every possible tuple, but requires solution for representing partial actions to the decoding model.
D.0.3 Concurrent Actions
The decentralized nature MPNNs makes them suitable for implementing concurrent action selection, i.e. agents performing more than one action a given timestep. Janisch| (2024) demonstrated this with the SysAdmin domain, where the problem is changed to the agent selecting subset of hosts rather than single hosts. Having the agent select one action for each object, a subset of objects, moves us closer to cooperative multi-agent reinforcement learning formulation (Focrster et al.) (018)), where we can view the graph as consisting of an arbitrary number of conditionally independent policies that should act in a cooperative manner.
D.0.4 Partial Observability
Including problems with partial observability, or hidden contert variables as defined by Kirk et al. (2023) would, in our opinion, improve the practical usability of VEJDE. Finding inductive solutions to problems with partial observability would likely require the addition of memory to the agent, or a temporal component to the database.
D.0.5 Action Preconditions
This filter came about as consequence of how PyRDDLGym handles action constraints. Certain domains in rddlrepository define logical constraints that limit what actions an agent is allowed to exccute given the current state. If an agent execules an action which violates a constraint, the options in the simulator are either crash, or put the simulator into an undefined state. A naive solution this problem is to check if actions violate constraint, and replace them with default action, but not all domains define default actions. Another solution is to repeatedly sample the policy until legal action is picked, but this requires tighter coupling of the policy and environment than the Gymnasium interface typically defines.
D.0.6 Nullary Domains
Though did not formally include it in our results, also tested VEJDE with the RDDL definition of the classic control problem CartPole with discrete actions. In this relational context CartPole becomes somewhat of an edge-case, as it is defined with only nullary predicates and actions. The policy decision is thus solely based on the aggregation of nullary predicates, described in 3.2 While recognizing that it constitutes a somewhat overcomplicated solution to the problem, we anecdotally found that VEJDE was able to find a satisfactory policy for the domain.
D.1 Problems not Defined in RDDL
While we do not focus on problems not defined in RDDL in this paper, our implementation is designed to be used for other, yet relational, problem arcas. We chose use RDDL for our evaluation as it allows us evaluate VEJDE on varied selection of abstracted problem types without much additional implementation work. For the purpose of developing policies for automated defense, incident response has been simulated in
26

---

Published in Transactions on Machine Learning Research (1/2026)
Test Statistic: 0.0495, p-value. 0.1682
-0.15
-0.10
0.10
0.15
Mean (scone mlp)
Figure 2: Null distribution from permutation test between average scores of VEJDE and MLP agent on all problems. p-value is calculated P(X >> 0.0495) 2.
number of works, often as two-agent game between attacking and defending agent Wolk et al. 2022 One of the more prominent examples of network incident response simulation is the CAGE set of problems, of which CAGF is the most recent instance (Kiely et al. 2025). The problem state in both simulated and real-world incident response is often derived from log and system data, which tends to be relational by design and thus fits the ronal reinforcement learning paradigm fairly well, as demonstrated by Thoompon el al. (2024) for instance.
E
Notes on Navigation
The goal of Navigation for the agent reach given location, at which point a reward of given for each step. All IPPC problems uses 40 timesteps, meaning that if the agent reaches the end early the optimal action is for the agent to do nothing. This leads to significant number of state-action tuples in the data collected from Prost consisting of Prost doing nothing. This skewed data distribution seems to impact mimic training negatively. With extended amount of epochs over the training data, mimic performance improved significantly. Improved results was also oblained when all state-action tuples from after the agent has reached the goal were removed from the training data. This does not explain the RL agent's poor performance on Navigation, but does answer the question of whether the architecture can encode policy that does well on the problem.
F Plots from Permutation Test
Figures and show mull distributions produced by sampling permutations of the pooled data and calculating the average score, with the observed average score marked with red line. 10 permutations were used. Null distributions from PROST comparisons not included the probability of the test statistic is 0.
G Box plots of scores per domain
F'iurre 4 shows box plots of average scores for each agent type for each domain.
27

---

Published in Transactions on Machine Learning Research (1/2026)
Test Statistic: 0.0086, p-value: 0.0191
-0.15
-0.00
-0.05
0.05
0.10
0.is
0.20
train)
Figure 3: Null distribution from permutation test between average scores on test and train set problems for imitation learning agents. p-value is calculated as P(X 0.0086) 2.
28

---

Published in Transactions on Machine Learning Research (1/2026)
AcademicAdvising 2014
TrossingTraffic 2014
1.0
1.0
Score
0.6
0.6
0.2
0.2
0.0
prost
mip
vejde
prost
mlp
vejde
Model
Model
Elevators 2014
Navigation 2011
1.0
1.0
0.8
0.8
Score
0.6
0.6
0.2
0.2
0.0
prost
mip
vejde
prost
mlp Model
vejde
Model
SkillTeachig
2014
SysAdmin 2011
1.0
0.8
0.8
8
Score
0.4
0.4
0.2
0.2
0.0
0.0
prost
mip
vejde
prost
vejde
Model
Model
Tamarisk 2014
Traffic 2014
1.0
0.8
0.8
Score
0.6
0.4
0.4
0.0
0.0
prost
mip Model
vejde
prost
vejde
Model
Figure 4: Box plots normalized scores of VEJDE agents, MLP agents and PROST for each domain.
29

---

Published in Transactions on Machine Learning Research (1/2026)
H Graph Attention
H.1 Introduction
In addition to the message passing procedure described in Section 3.3 we also implemented and evaluated an encoder based on graph attention mechanisms. The primary difference between the local message- nessage-passing passing and attention-based graph representation methods is that the latter typically incorporates information from the entire graph at each step rather than the local node neighborhood. The attention function is technically pussage-passing over fully connected graph, but for the purposes of this evaluation we will distinguish between graph attention and message-passing, with the latter referring to aggregations node neighborhoods.
Dot-product attention does not incorporate the graph structure, meaning that locality information is lost Ying et al. 2021). For instance, given the example shown in la a policy using only dot-product attention can not distinguish between æ1 and T2, assuming both are of the same type. This means that the naive application of transformer in this context bound perform poorly this context, which we also confirmed preliminary experiments.
A remediation to the position invariance of attention is to explicitly include positional information with the input sequence. For sequential data, such as natural language, sinusoidal vectors derived from the element positions or relative distances have been used (Su et al. 2024). This approach fails for graphs, however, graphs do not have a natural ordering. Instead, various properties that is derived from the adjacency matrix has been used, such as the degree, pairwise distances or graph Laplacian (Ying et al. 2021 Zhang et al. 2023
H.2 Implementation
Given that the state graph is bipartite, we chose to define the attention function
a (X,Y) 9 ()(W())))
function of the two node sets, meaning that the resulting attention matrix consists of one weight for each pair in the cartesian product of the two sets. The attention function alone do not capture any graph structure, so in line with Zhang et al. (002)) we add the pairwise shortest-path distances between the objects and facts to the attention matrix. In line with previous work, distances are treated as indices that are mapped to learnable scalars. The embedded distance matrix is then multiplied element-wise with the attention matrix. The infinite distance, such as between disconnccted nodes, is assigned a learnable scalar as well. The resulting, augmented, allention matrix thus defined
(X,Y) = a (X,Y)
where denotes element wise multiplication. Updates to the both node sets done analogously to the prssage-passing method, but with y replacing the adjacency matrix:
HOO (H()) k(i+1) = o69 (H((HH))))) k(0) H(0)) k()) + K()
H(++1) = ob (
H.3 Experiments
We conduct the experiments with the graph altention policy with the same hyperparameters as for the message passing policy. The two architectures have roughly the same number of parameters (#s 12000). The transformer thcorctically requires less messago-passes, as information is distributed across the entire graph in one step, but still benefits from additional layers. The imitation learning and reinforcement learning experiments was conducted in the way described in Section 4.3.1 Due to the higher memory requirements
30

---

Published in Transactions on Machine Learning Research (1/2026)
Table 7: Average normalized score per domain on test instances for PROST and graph attention policies trained with imitation learning.
Domain
GA μ = o
PROST μl 4
SysAdmin
0.71 + 0.41
0.85 0.39
SkillTeaching
0.60 + 0.22
0.99 = 0.31
Tamarisk
0.42 + 0.22
1.00 = 0.31
CrossingTrasfic Traflic
0.31 + 0.42
1.00 = 0.32
Traffic
0,12 + 0.34
1.00 = 0.15
Elevators
0.10 + 0.75
1.00 0.51
AcademicAdvissing
0.00 + 0.44
0.80 0.66
Navigation
0.00 + 0.00
1.00 0.61
of the graph transformer, we were forced to train the mimic with batihe rather than with the full dataset as with the message-passingg neural network. The number of epochs over the data was kept the same, however.
H.4 Results
We found that the graph atlention policy produced produced siguificantly lower scores than the message- passing policy in both the imitation learning and reinforcement learning experiments. In addition to the lower scores, the training time of the attention-based policy was significantly higher for some domains, owing to the quadratic scaling of the altention function. The training times compared to the message passing policy are shown in Figure 5 The scores of the message passing agent and transformer agents for each domain are also shown sideeb in Figure 6
The full results of the imitation learning agent is shown in Table and the RL agent in is shown in Table S
H.5 Discussion
The somewhat poor results of the graph atlention method is consistent with results we have observed in previous work, where the method that incorporated graph-wide information had worse generalization properties than the entirely local method Nyberg & Johnson (2024). The message passing policy is not entirely localized either, however, as the first action made based on information from the entire graph, but the message passing is local.
The graph attention implementation adds major compute costs. One is in calculating pairwise distances, which we do for each step [8 The second additional compute cost is memory. Due to the dot-product in the aforementioned dot-product attention, the resulting attention matrix will scale quadratically with the number of nodes in the graph.
We recognize that the graph attention method we evaluated is a somewhat basic implementation. Additional steps could be added, such as self-attention step, and different graph metrics can be added the attention matrix, but we opted for a simple initial approach that still incorporates the main components of Transformer- esque models.
1ittth caching, the case every unique state. However, attempts cache the distances each state led system memory running for problems with large state spaces.
31

---

Published in Transactions on Machine Learning Research (1/2026)
Table 8: Average normalized scores on test instances for graph attention agents trained using RL and PrOST, per problem domain.
Domain
GA 4
MLP μ w
PROST μ
SkillTeaching
0.58 + 0.34
0.83 = 0.23
0.99 = 0.31
Tamarisk
0.32 + 0.18
0.61 + 0.18
1.00 0.31
Crossing TrossingTraffic Traffic
0.27 = 0.47
0.46 = 0.50
1.00 0.32
SysAdmin
0.26 + 0.37
0.93 + 0.34
0.95 0.47
Traffic
0.14 + 0.39
0.12 0.27
1.00 = 0.15
Navigation
0.01 + 0.25
0.12 0.29
1.00 = 0.61
AcademicAdvising
0.00 + 0.39
0.29 = 0.09
0.80 = 0.66
Elevators
0.00 + 0.57
0.20 + 0.52
1.00 + 0.51
Training Time Comparison: Graph Attention vs Message Passing
Graph Attention
4.0
Message Passing
3.5
Training 250,00 350,000 Timestegs
2.5
2.0
1.0
0.5
Academickdhvising
Tressingttaficc
Elevators
Hovigation
SkirRachiig
Systddmin
Tamarisk
Traffic
Domain
Figure 5: A bar chart showing training times in hours for message passing agents and graph attention agents on each domain. Times were averaged over five runs.
32

---

Published in Transactions on Machine Learning Research (1/2026)
Normalized Score: Graph Attention Message Passing
Message Passing
0.8
0.2
AcademicAdbbingg
CrosstngTraffe
Blevator
Navigation
Suankaching
SydAdmin
Tomarist
Traffic
Figure 6: A bar chart showing normalized scores for message passing agents and graph attention agents on each domain. Scores were averaged over five runs.
33


Reviews:
[{"review_id": "jJaS7NFaAu", "reviewer": "Reviewer_zxeU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents Vejde, a framework combining graph neural networks (GNNs) and reinforcement learning (RL) to produce inductive policies that generalize across problem instances within a domain. Vejde represents MDP states as bipartite factor graphs derived from relational databases, uses message-passing neural networks (MPNNs) to generate latent representations, and applies PPO for training.\nThe authors evaluate Vejde on eight RDDL domains, using both imitation learning (from Prost) and RL, comparing results against instance-specific MLP agents and the Prost planner. Results show that Vejde generalizes to unseen instances with only minor performance loss and achieves scores close to instance-specific MLPs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper articulates the problem of RL generalization to relational domains well and situates it convincingly within relational and neuro-symbolic RL literature. The factor graph and color refinement formulation are well-grounded in prior work. The mapping from logic-based state descriptions to GNN representations is well-motivated.", "audience_yn": "Yes", "audience_explanation": "The topic is relevant, the proposed architecture is coherent, and the evaluation spans a comparatively large portion of RDDL benchmarks for relational RL and I think TMLR's audience can be interested in knowing the findings.", "requested_changes": "The goal of the paper is important and aligns with a renewed interest in structured RL and neuro-symbolic generalization. The combination of a bipartite fact–object factor graph with MPNN message passing is straightforward, interpretable, and domain-agnostic. The framework should be re-usable in other relational RL settings. From what I know about previous literature, testing across 8 RDDL domain is substantially broader than what several prior relational RL works present. However I feel there are some issues. While MLPs and Prost are strong baselines, the lack of comparison to other inductive or graph-based RL methods is a missed opportunity. The authors acknowledge this but could better contextualize their results relative to prior work. Furthermore, the paper would benefit from an ablation study (e.g., the effect of message-passing layers, aggregation functions, or the bipartite graph structure) to justify design choices and sensitivity to hyperparameters (e.g., embedding size, learning rate schedules) is not discussed, which could affect reproducibility. Several domains show near-zero RL performance  This raises concerns: are these failures due to PPO instability, representational limits of the architecture, or training hyperparameters? why does imitation succeed in Elevators but PPO fails? The paper acknowledges this but provides no diagnostic analysis.\nThe paper has an ambitious goal and a clear design to model the problem it want to solve, but I feel it is still incomplete and with many directions of improvement. However, my confidence in the assessment is not very high as my expertise is more concerned with the theoretical nature of RL, so I may have missed the more recent developments in the field and I may not be aware of some of the most common and best practices of the literature, so I'm very open to change my mind if the authors provide convincing explanations.", "broader_impact_concerns": "No broader impact concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0o6HVkM0vN", "reviewer": "Reviewer_gZxp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Vejde, a framework that works on MDP of relational databases of facts about entities, converts each state to bipartite graph, use of GNN architecture and trained with PPO objective. The key idea is that factored representation of both states and actions allows Vejde agents to handle problems of varying size and structure. The evaluation results are on eight problem domains defined in\nRDDL, with ten problem instances each. When initialized via imitation learning, Vejde achieves performance comparable to an online planning algorithm. With reinforcement learning, Vejde’s GNN-based agents outperform MLP baselines, specifically in the AcademicAdvising and Traffic domains.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The experiments are well structured for supervised and RL training results provided over five randomly sampled train/test splits and\nrepeated experiments for each split. The online planning algorithm PROST provides a good upper bound to compare with and p_null value is discussed puts the results into perspective.", "audience_yn": "No", "audience_explanation": "The topic might be of interest to TMLR's audience. But people will appreciate the findings of the paper if it is revised from its current form. Here are the three reasons:\n\n1. The relational scope is limited. By excluding higher-arity predicates and simplifying domains, the setup no longer reflects the complexity of real relational databases, making the tasks less compelling for the broader ML community. \n\n2. The architectural choice is focused on using GNNs with color refinement and compared to MLPs. But GNN with bipartite graph on each state seems less flexible than Transformers, which could more naturally model subject–predicate interactions and scale beyond the small RDDL datasets used.\n\n3. While the paper covers exhaustive details, it is overly long. The draft could be condensed to about 12 pages, with standard background and detailed implementation moved to appendices, improving clarity and impact.", "requested_changes": "1. Clarify why the problem is still interesting and novel despite the simplification. It seems that the key aspects of RDDL has been filtered out in the current evaluation.\n1. Include transformers as a baseline, at least for the imitation learning experiments. What is needed to cover the clear gaps in Navigation (0.33 vs 0.99) and Traffic (0.73 vs 1.00) environments?\n1. Make the paper concise in 12 pages and move extra details to Appendix.", "broader_impact_concerns": "broader impact is not discussed in the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qs4MPJxTyu", "reviewer": "Reviewer_LTcH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel graph-based RL to learn inductive policies for structured MDPs. The states of the MDP are represented as the data bases of fact and then encoded as embeddings using the neural message passing. A policy parameterized by neural networks outputs the probability of the actions over the states. In practical implementation, some techniques including batching and action chunking are used. Experimental evaluated are conducted on 8 problem domains from RDDL. The results show that the learned policy achieves good generalization, without a significant loss in performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The statements are supported by empirical results.", "audience_yn": "Yes", "audience_explanation": "Readers interested in RL may find this paper of interest.", "requested_changes": "The empirical results show that VEJDE achieves worse average performance than the MLP policies on 5 of 9 problem domains. These results are fine for me, since the MLP policies are trained on each problem instance. However, I notice that the paper does not show the comparison of VEJDE to other inductive policies. Adding a comparison to similar inductive policies is helpful to show the benefits of the proposed method, particularly when its performance does not surpass the MLP policies. Although the authors explain that they cannot find a single method that covers the set of problem domains, providing comparisons on a subset of problem domains is still helpful.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)