Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems

1 Introduction

Deep Reinforcement Learning (DRL) has been successfully used for sequential decision making in tasks using imagebased state representations [Mnih et al., 2013]. However, many problems in the real world cannot be readily expressed as such and are naturally described in factored representations in a symbolic representation language such as the Planning Domain Definition Language (PDDL) [Long and Fox, 2003] or the Relational Dynamic Influence Diagram Language (RDDL) [Sanner, 2010]. For example, in a logistics problem, the objective consists of delivering packages to their destined locations using a truck to carry them. Symbolic description languages such as first-order logic (FOL) can easily capture states and objectives of this scenario using predicates such as in-truck(p) where p is a parameter that can be used to represent any package. Symbolic representations for such problems are already available in the form of databases and converting them to image-based representations would require significant human effort. Due to their practical use, symbolic descriptions and algorithms utilizing them are of keen interest to the research community.

A key difficulty in applying RL to problems expressed in such representations is that their state spaces generally grow exponentially as the number of state variables or objects increases. However, solutions to such problems can often be described by compact, easy-to-compute "generalized policies" that can transfer to a class of problems with differing object counts, significantly reducing the sample complexity for learning a good, instance-specific policy.

Running Example We illustrate the benefits of computing generalized policies using the SysAdmin(n) domain [Guestrin et al., 2001] that has been used as a benchmark domain in several planning competitions. A problem in this domain consists of a set of n computers connected to each other in an arbitrary configuration. At any time step, the computers can shutdown with an unknown probability distribution that depends on the network connectivity wherein a shutdown computer increases the tendency of its neighbors to shutdown. The agent is also awarded a positive reward that is proportional to the total number of running computers. Similarly, at each time step, the agent may reboot any one of the n computers bearing a small negative reward or may simply do nothing. In our problem setting, action dynamics are not available as closed-form probability distributions making RL the natural choice for solving such problems.

A state in this problem is succintly described by a factored representation with boolean state variables (propositions) that describe which computers are running and their connectivity. It is easy to to see that the state spaces grow exponentially as n increases. However, this problem has a very simple, greedy policy that can provide a very high cumulative reward; reboot any computer that is not running or do nothing. Even though a general policy for such a problem is easy to express, traditional approaches to RL like Q-learning cannot transfer learned knowledge, and thus, have difficulties scaling to larger problems with more computers. Our major contribution in this paper is learning a generalized, relational Qfunction that can express such a policy and use it to efficiently transfer knowledge to larger instances.

Many existing techniques that compute generalized policies do so by using human-guided or automatic feature engineering to find relevant features that facilitate efficient transfer (see Sec. 5 for a detailed discussion of related work). For example, Ng and Petrick [2021a] use an external feature discovery module to learn first-order features for Q-function approximation. API [Fern et al., 2006] uses a taxonomic language with beam search to form rule-based policies.

In this paper, we approach the problem of learning generalized policies from a Q-function approximation perspective. We utilize deep learning along with an automatically generated feature list to learn a nonlinear approximation of the Q-function. Our approach learns a generalizable, relational Q-function that facilitates zero-shot transfer of knowledge to larger instances at the propositional level. We extend our previous work on leapfrogging, a data-efficient automatic self-training technique, to RL settings. Our empirical results show that our approach can outperform existing approaches for zero-shot transfer.

The rest of this paper is organized as follows: The next section presents the required background. Sec. 3 describes our approach for transfer followed by a description of our algorithm for generalized reinforcement learning (Sec. 3.3). Sec. 4 presents an extensive empirical evaluation along with a discussion of some limitations and future work. Sec. 5 provides an account of related work in the area and Sec. 6 concludes this paper by summarizing our contributions.

2 Formal Framework

We establish our problem in the context of reinforcement learning for Markov Decision Processes (MDPs). We represent relational MDPs using the notation used by Fern et al. [2006]. Let D = ⟨P,A⟩ be a problem domain where P is a set of predicates of arity no greater than 2, 1 and A is a set of parameterized action names. An MDP problem for a domain D is a tuple M = ⟨O, S, A, T, R, γ, s0⟩ where O is a set of objects. A fact is an instantiation of a predicate p ∈ P with the appropriate number of objects from O. A state s is a set of true facts and the state space S is a finite set consisting of all possible sets of true facts. Similarly, the action space A is composed of all possible instantiations of action names a ∈ A with objects from O. T is a transition system, implemented by a simulator, that returns a state s′ according to some fixed, but unknown probability distribution P(s′ |s, a) when applying action a in a state s. We assume w.l.o.g. that the simulator only returns actions that are executable in a given state and that there is always one such action (which can be easily modeled using a no-op). R : S × A → R is a reward function that is also implemented by the simulator. γ is the discount factor, and s0 is the initial state.

Example The SysAdmin domain introduced in the preceding section can be described by predicates running(cx) and connected(cx, cy). The possible actions are reboot(cx), and no-op(). cx and cy are parameters that can be grounded with objects of a specific problem. A state of a problemMeg drawn from SysAdmin(2) with connectivity K2 using computer names c0 and c1 where only c0 is running can be described as seg = {running(c0), connected(c0, c1), connected(c1, c0)}. The action space of Meg would consist of actions no-op(), reboot(c0), and reboot(c1) with their dynamics implemented by a blackbox simulator.

A solution to an MDP is expressed as a deterministic policy π : S → A, which is a mapping from states to actions. Let t be any time step, then, given a policy π, the value of taking action a in a state s is defined as the expected return starting from s, executing a, observing a reward r and following the policy thereafter [Sutton and Barto, 1998].

1 Predicates with arity greater than 2 can be easily converted to binary predicates using a simple compilation.

The optimal action-value function (or Q-function) is defined as the maximum expected return over all policies for every s ∈ S and every a ∈ A; q∗(s, a) = max π qπ(s, a). It is easy to prove that the optimal Q-function function satisfies the Bellman equation (expressed in action-value form):

Reinforcement learning algorithms iteratively improve the Q-function estimate Q(s, a) ≈ q∗(s, a) by converting the Bellman equation into update rules. Given an observation sequence (st, at, rt+1, st+1), the update rule for Q-learning [Watkins, 1989] to estimate Q(st, at) is given by:

where δt = rt+1 + γmax a′∈A Q(st+1, a′ ) - Q(st, at) is the temporal difference, TD(0), error, and α is the learning rate. Q-learning has been shown to converge to the optimal Q-function under certain conditions [Sutton and Barto, 1998]. Q-learning is an off-policy algorithm and generally uses an ϵ-greedy exploration strategy, selecting a random action with probability ϵ, and following the greedy policy π(s) = argmax Q(s, a) otherwise.

a

We define a feature f for a domain D as a first-order formula over P with one free variable. We then define a feature kernel ϕf(s) for a problem M as the set of objects o ∈ O that satisfy f in a state s ∈ S. We utilize description logic to derive and express feature kernels building upon the recent work by Bonet et al. [2019]. This is described in Sec. 3.1.

3 Our Approach

Our goal is to compute approximate Q-functions whose induced policies zero-shot generalize to problem instances with differing object counts in a way that allows RL approaches to find good policies with minimal learning. To do so, we automatically generate domain-specific relational abstractions that lift problem-specific characteristics like object names and numbers (Sec. 3.1). Sec. 3.2 describes our method of representing these abstractions as input features to a deep neural network. Finally, Sec. 3.3 and Sec. 3.4 expand on how our algorithm, Generalized Reinforcement Learning (GRL), performs iterative automatic self-training of the deep neural network to learn approximate Q-values of abstract states and uses them for transfer, especially in the zero-shot setting.

3.1 Relational Abstraction

This paper develops a novel approach for learning, expressing, and transferring generalized Q-functions using logicbased features. One challenge in Q-function approximation is the selection of a representation language in which it would be possible to express features that provide useful information for the decision making process. Prior work on computing generalized plans and policies considers using logic-based features to develop lifted policy languages for feature synthesis [Khardon, 1999; Cumby and Roth, 2002; Mart´ın and Geffner, 2004; Fern et al., 2006]. Counters derived from logic-based features have been found to be useful for expressing generalized plans [Srivastava et al., 2008] and can be used to derive measures of progress for proving correctness [Srivastava et al., 2010; Srivastava et al., 2011; Srivastava et al., 2015]. Bonet et al. [2019] develop new approaches for learning logic-based features that can express such counters. Karia and Srivastava [2021] use such featurebased counters to learn generalized heuristics for planning.

We now provide a formal description of the general classes of abstraction-based, domain-independent, automatic feature synthesis algorithms that we used to yield counters for RL.

Description Logics (DLs) are a family of representation languages often used for knowledge representation [Baader et al., 2017]. We chose DLs since they provide a good balance between expressiveness and tractability in feature expression.

In the relational MDP paradigm, unary predicates P1 ∈ P and binary predicates P2 ∈ P of a domain D can be viewed as primitive concepts C and roles R in DL. DL includes constructors for generating compound concepts and roles from primitive ones to form expressive terms. Our feature list FDL consists of concepts and roles formed by using a reduced set of grammar fromBonet et al. [2019]:

where P1 and P2 represent the primitive concepts and roles, and R-1 represents the inverse. ∀R.C = {x | ∀y R(x, y) ∧ C(y)} and ∃R.C = {x | ∃y R(x, y) ∧ C(y)}. R = R′ denotes {x | ∀y R(x, y) = R′ (x, y)}. We also use Distance(c1, r, c2) features that compute the minimum number of role r steps between two objects satisfying concepts c1 and c2 [Franc`es et al., 2021]. We found this reduced grammar (that excludes transitive closure) to generate features that facilitated good generalization in our experiments.

We control the total number of features generated by only considering features up to a certain complexity k (a tunable hyperparameter) that is defined as the total number of grammar rules required to generate a feature.

Example The primitive concepts and roles of the SysAdmin domain are running(cx) and connected(cx, cy) respectively. For the running example Meg, the feature kernel for a feature fup ≡ running(cx) evaluates to the set of objects satisfying it, i.e., ϕfup (seg) = {c0}. This feature can be interpreted as tracking the set of computers that are running (or up). Similarly, ϕfcon (seg) = {c1} for a different feature fcon ≡ ∃connected.running. fcon can be viewed as tracking the set of computers that are connected to at least one running computer. It is easy to see that DL features such as fup and fcon capture relational properties of the state and can be applied to problems with differing object names and quantities.

We implemented a reduced version of the D2L system [Franc`es et al., 2021] for generating such DL based features and describe our process for doing so in Sec. 4.2.

3.2 Deep Learning for Q-value Approximation

Given a list of DL features F, the key challenge is to identify a subset F ′ ⊆ F of features that can be used to learn a good approximation of the Q-function. We use deep learning, utilizing the entire feature list F for Q-value estimation.

Given a feature list F and a domain D, the input to our network is a vector of size |F | + |A| +N × |F | where |A| is the total number of actions in the domain, and N is the maximum number of parameters of any action in A. Since the dimensionality of the input vector is fixed and does not depend upon a specific problem instance, the same network can be used to predict Q-values across problem instances. This is the key insight into our method for transfer.

Given a concrete state s, the abstract state feature vector is defined as s = ⟨|ϕf1 (s)|, . . . , |ϕfn (s)|⟩ for all features fi ∈ F. Similarly, given a grounded action a(o1, . . . , on), the abstract action feature vector is defined as a vector a = ⟨Aname|Fo1 | . . . |FoN ⟩ where Aname is a one-hot vector of length |A| encoding the action name a, Foi is a vector of length |F| encoded with values 1[oi∈ϕfj (s)] for every feature fj ∈ F, and | represents vector concatenation. The vector ⟨s|a⟩ comprises the input to our network.

Since Distance features directly return numerical values, we simply define |ϕf (s)| = ϕf (s) and ∀o ∈ O, o ∈ ϕf (s) = 0 for such distance-based features.

Example Let FDL = ⟨fup, fcon⟩ for the SysAdmin domain where fup ≡ running(cx) and fcon ≡ ∃connected.running. Then, the abstract state vector seg for the concrete state seg of the running example would be ⟨1, 1⟩ and it indicates an abstract state where there is a single computer running and where there is only a single computer that is connected to a running computer. The same vector would be generated for any SysAdmin problem where these properties hold irrespective of the total number of computers or what computer names are used to represent the objects in the state.

Assuming actions are indexed in alphabetical order, for seg, no-op() would be encoded as ⟨1, 0|0, 0⟩. Similarly, reboot(c0) and reboot(c1) would be encoded as ⟨0, 1|1, 0⟩ and ⟨0, 1|0, 1⟩ respectively.

Fig. 1 illustrates our process for estimating the Q-values. Given a concrete state s and action a, our network (that we call QGRL) predicts the estimated Q-value QGRL(s, a) ≈ q∗(s, a) by converting s and a to abstract state s and action a feature vectors based on the feature list F .

Algorithm 1 Generalized Reinforcement Learning (GRL)

Require: MDP M, GRL network QGRL, feature list F , epsilon ϵ, learning rate α

• 1: Q← initializeEmptyTable()
• 2: for s ∈ S, a ∈ A do
• 3: s, a ← abstraction(F, s, a)
• 4: Q(s, a) = QGRL(s, a)
• 5: end for
• 6: B← initialize replay buffer
• 7: s ← s0
• 8: while stopping criteria not met do
• 9: a ←getEpsilonGreedyAction(s, ϵ)
• 10: s′ , r ←executeAction(s, a)
• 11: δ = r +γmax a′∈A Q(s′ , a′ ) - Q(s, a)
• 12: Q(s, a) = Q(s, a) +αδ
• 13: s, a ←abstraction(F, s, a)
• 14: Add (s, a,Q(s, a)) to B
• 15: Sample a mini-batch B fromB
• 16: Train QGRL using B
• 17: s ← s′ {s ← s0 if episode ends}
• 18: end while
• 19: return Q,QGRL

The abstract state captures high-level information about the state structure, whereas the abstract action captures the membership of the instantiated objects in the state, allowing our network to learn a generalized, relational Q-function that can be transferred across different problem instances.

3.3 Generalized Reinforcement Learning

Intuitively, Alg. 1 presents our approach for Generalized Reinforcement Learning (GRL). For a given MDP M, an initial QGRL network, and a list of features F, GRL works as follows: Lines 1-5 transfer knowledge from the QGRL network by converting every concrete state s and action a to abstract state s and abstract action a vectors using the approach in Sec. 3.2. Next, every concrete Q-table entry Q(s, a) is initialized with the predicted value QGRL(s, a). The Q-table for different problems M ′ ̸= M are different since their state and action spaces are different, however, s and a are fixed-sized vector representations of any state and action in these problems. This allows QGRL to transfer knowledge to any problem M ′ with any number of objects. Lines 9-12 do Q-learning on M to improve the bootstrapped policy further. Lines 13 - 16 further improve the generalization capabilities of QGRL by incorporating any policy changes that were observed while doing Q-learning on M. GRL returns the task-specific policy Q and the updated generalized policy QGRL.

Algorithmic Optimization Lines 2 - 5 can be intractable for large state spaces. We optimized transfer by only initializing entries in a lazy evaluation fashion, i.e., we start with an empty Q-table and only transfer values for states that do not have an entry in the Q-table. An added benefit is that updates to QGRL for any abstract state can be easily reflected when encountering a new state that maps to the same abstract state. We empirically observed this to be helpful in improving the sample efficiency for solving the task.

Theorem 3.1. Solving problem M using GRL converges under standard conditions of convergence for Q-learning.

Proof (Sketch). The proof is based on the following intuition. QGRL is used to initialize every Q(s, a) entry of M exactly once after which Q-learning operates as normal. The rest of the proof follows from the proof of convergence for Qlearning [Sutton and Barto, 1998].

3.4 Scaling Up Q-learning and Transfer

Transfer capabilities can often be improved if the training strategy uses a curriculum that organizes the tasks presented to the learner in increasing order of difficulty [Bengio et al., 2009]. However, the burden of segregating tasks in order of difficulty often falls upon a domain expert.

We extend our work on leapfrogging, which is an automatic, data-efficient self-training method [Groshev et al., 2018; Karia and Srivastava, 2021], to RL settings. Leapfrogging follows the "learning-from-small-examples" paradigm by using a problem generator to automatically create a curriculum for learning. It is an iterative process for speeding up learning when used in conjunction with a transfer learning algorithm such as GRL. Leapfrogging is analogous to a loose curriculum, enabling self-supervised training in contrast to curriculum learning, which on its own, does not enable automatic self-training.

Leapfrogging operates by initially generating a small problem, Msmall, that can be easily solved by vanilla Q-learning without any transfer. It applies GRL (Alg. 1) to this problem using an uninitialized QGRL network. Once this problem is solved, leapfrogging generates a slightly larger problem and invokes GRL again. The QGRL network learned in the previous iteration allows GRL to utilize knowledge transfer to solve this new problem quickly while also improving the generalization capabilities of the next generation QGRL network.

4 Empirical Evaluation

We performed an empirical evaluation on four different tasks and our results show that GRL outperforms the baseline in zero-shot transfer performance. We also show that GRL is competitive with approaches receiving additional information in the form of closed-form action models. We now describe the evaluation methodology that we employed for assessing these hypotheses.

We ran our experiments utilizing a single core and 16 GiB of memory on an Intel Xeon E5-2680 v4 CPU containing 28 cores and 128 GiB of RAM.

We used the network architecture from Fig. 1 for all of our experiments. Our system is implemented in Python 2 and we used PyTorch [Paszke et al., 2019] with default implementations of mean squared error (MSE) as the loss function and Adam [Kingma and Ba, 2015] as the optimization algorithm for training each domain-specific QGRL network.

Our system uses RDDLsim as the simulator, and thus, accepts problems written in a subset of RDDL.

2 Our code is available at: https://github.com/AAIR-lab/GHN

4.1 Baselines

As our baseline, we compare our approach with a firstorder Q-function approximation based approach for transfer; MBRRL [Ng and Petrick, 2021a; Ng and Petrick, 2021b]. We also compare with SymNet [Garg et al., 2020], an approach that requires access to closed-form action models, information that is unavailable to MBRRL and GRL in our setting. 3

MBRRL computes first-order abstractions using conjunctive sets of features and learns a linear first-order approximation of the Q-function over these features. They employ "mixed approximation," where both the concrete Q(s, a) values as well as the approximated Q-values are used to select actions for the policy.

SymNet uses a Graph Neural Network (GNN) representation of a parsed Dynamic Bayes Network (DBN) for a problem. SymNet thus has access to additional domain knowledge in the form of closed-form action models, and as a result, it is not directly applicable in the RL setting that we consider. Nevertheless, it can serve as a good indicator of the transfer capabilities of GRL, which does not need such closed-form representations of action models. We also tried modifying TraPSNet [Garg et al., 2019], a precursor of SymNet that does not require action models, but could not run it due to the limited support for the domains we considered.

4.2 Tasks, Training, and Test Setup

We consider tasks used in the International Probablistic Planning Competition (IPPC) [Sanner, 2011; Sanner, 2014], some of which have been used by SymNet and MBRRL as benchmarks for evaluating transfer performance.

SysAdmin(n) is the IPPC version of the SysAdmin domain that was described earlier in the paper. The IPPC version also allows for computers to automatically restart with a fixed probability p.

Academic Advising(l, c, p) is a domain where the objective is to complete a degree program by passing a certain number of levels l containing c courses, each of which need p prerequisites to be passed first. Courses have a higher probability of passing if all of their prerequisites have been passed first. At each time step, the agent is provided with a large negative reward if the agent has not yet completed the program. Thus, the objective is to complete the program in the shortest number of time steps.

Game of Life(x, y) is John Conway's Game of Life environment on a grid of size x × y [Izhikevich et al., 2015]. The rules are as follows: (a) a live cell with fewer than two or greater than three live neighbors dies, (b) cells with two or three live neighbors live on to the next time step, and (c) any dead cell with exactly three live neighbors becomes a live cell. At each time step, the agent is awarded with a positive reward proportional to the total number of live cells.

Wildfire(x, y) is an environment set in a grid of size x×y with some cells containing fuel. Cells that contain fuel can spontaneously ignite with a probability proportional to the total number of their neighbors that are on fire. At each time step, the agent is awarded a large negative reward for each cell that is burning. The initial state starts with some cells already on fire and thus the objective is to put out all the fires as quickly as possible.

3 We thank the authors of SymNet and MBRRL for help in setting up and using their source code.

The IPPC versions of Game of Life and Wildfire contain 4ary predicates that we converted to an equivalent binary version by converting predicates like neighbor(x1, y1, x1, y2) to neighbor(l11, l12) for use with all baselines and GRL.

Training For SymNet, we utilized the same problems (IPPC instances 1, 2, and 3) for training as published by the authors. We trained each problem for 1250 episodes. For MBRRL, we utilized the original authors' training procedure wherein we used IPPC instance #3 for training. We trained this problem for 3750 episodes using Q-learning with an initial ϵ = 1 and a decay rate of 0.997.

For training GRL with our leapfrogging approach, we used problem generators that were used in the IPPC to randomly generate problems for training. We used SysAdmin(n) with n ∈ {3, 4, 6}, Academic Advising(n, n, n) with n ∈ {2, 3, 4}, Game of Life(n, n) with n ∈ {2, 3} and Wildfire(n, n) with n ∈ {2, 3, 4} for generating problems used for training each domain respectively. We trained each problem for 1250 episodes using GRL using a fixed ϵ = 0.1. for each problem.

Testing We used the same set of problems as SymNet: instances 5 - 10 from the IPPC problem collection. The only exception was Academic Advising where we used instances 5, 7, and 9 since instances 6 and 10 used concurrent actions and this was not compatible with our system. To better evaluate transfer performance, the test problems are selected such that their state spaces are much larger than the training problems used by GRL. For example, the state space size of SysAdmin(n) is 2n . For training, the largest problem used by GRL was SysAdmin(6), whereas the largest test problem, instance 10 (SysAdmin #10) of the IPPC is SysAdmin(50).

Table 1 lists the minimum and maximum state space sizes of the training and test problems that we used in our evaluation respectively. A detailed description of the problem instances and parameters that we used in our training and test sets can be found in the extended version of this paper [Karia and Srivastava, 2022].

Hyperparameters We used the IPPC horizon H of 40 time steps for each episode after which the simulator was reset to the initial state. To train a QGRL network, we used a replay buffer of size 20000, a mini-batch size of 32, and a training interval of 32 time steps with 25 steps of optimization per interval. For our test setup, we used Q-learning with ϵ = 0.1 for GRL and MBRRL. We used γ = 0.9 and α = 0.05 for the SysAdmin and Game of Life domains and used γ = 1.0 and α = 0.3 for Academic Advising and Wildfire.

For MBRRL and SymNet, we used the default values of all other settings like network architecture, feature discovery threshold, etc., that were published by the authors.

Evaluation Metric To showcase the efficacy of transfer learning, our evaluation metric compares the performance of MBRRL and our approach after zero-shot transfer. We freeze the policy after training, transfer it to the test instances and run it greedily for 100 episodes. We report our results using mean and standard deviation metrics computed using 10 individual runs of training and testing.

Feature Generation We generated sampled state spaces and transitions between states using random walks on the first problem used by GRL for training per domain. These transitions were used in conjunction with the DL grammar from Sec. 3.1 to generate the DL feature list FDL using a modified version of the D2L system [Franc`es et al., 2021], which does not require closed-form action models or knowledge of goals. We set a complexity bound of k = 5 for goal-independent feature generation. We empirically observed that using this single small problem instance and complexity bound together with the reduced DL grammar from Sec. 3.1 to generate FDL was sufficient in generating features that enabled good generalization using GRL.

4.3 Analysis of Results

Our results are shown in Fig. 2. It is easy to see that GRL has excellent zero-shot transfer capabilities and can easily outperform or remain competitive with both MBRRL and SymNet. We now present our analysis followed by a brief discussion of some limitations and future work.

Comparison with MBRRL Our approach is able to significantly outperform MBRRL on SysAdmin, Academic Advising, and Wildfire. The DL abstractions used by GRL are more expressive than the conjunctive first-order features used by MBRRL, allowing GRL to learn policies that are more expressive. Additionally, leapfrogging allows scaling up training and learning of better generalized policies in the same number of training episodes in contrast to using a fixed instance for training.

For the Game of Life domain, we observed that even a random policy performs similarly to GRL and the baselines. This is surprising since PROST [Keller and Eyerich, 2012], an approach that requires closed-form action models, has demonstrated that it is possible to achieve high reward in this domain [Sanner, 2011]. We leave this investigation to future work.

Comparison with SymNet SymNet utilizes significant domain knowledge in constructing the graphs. For example, edges are added between two nodes iff an action affects them. Such information is unavailable when just observing states as sets of predicates. It is impressive that despite not using such knowledge, GRL is able to remain competitive with SymNet in most of the problems.

4.4 Limitations and FutureWork

In the SysAdmin domain, the probability with which a computer shuts down depends on how many shutdown computers it is connected to. Our representation of o ∈ ϕf(s) for representing the action vectors cannot capture such dependencies. However, this is easy to mitigate using a new feature that counts the number of shutdown computers a specific computer is connected to. We plan to investigate the automatic generation and use of such features in future work.

Leapfrogging requires an input list of object counts for the problem generator that we hand-coded. However, we believe that our approach is a step forward in curriculum design by relieving the designer from knowing intrinsic details about the domain, which is often imperative for assessing the difficulty of tasks. The lack of a problem generator can be mitigated by combining leapfrogging with techniques that sample "subgoals" [Fern et al., 2006; Andrychowicz et al., 2017] and utilizing GRL to learn a generalized policy that can later be efficiently transferred to any subsequent problems.

5 RelatedWork

Our work adds to the vast body of literature on learning in relational domains. Several of these approaches [Khardon, 1999; Guestrin et al., 2003; Wu and Givan, 2007; Garg et al., 2020] assume that action models are available in an analytical form and thus are not directly applicable to RL settings. For example, FOALP [Sanner and Boutilier, 2005] learns features for approximating the value function by regressing over action models. D2L [Franc`es et al., 2021] learns abstract policies for deterministic problems assuming an action model where actions can increment or decrement features. We focus our discussion on relational RL (see Tadepalli et al. [2004] for an overview).

Q-estimation Approaches Q-RRL [Dzeroski et al., 2001] learns an approximation of the Q-function by using logical regression trees. GBQL [Das et al., 2020] learns a gradientboosted tree representation of the Q-function. Their tree representations use "lifted" predicates thus enabling transfer across problem instances with differing object counts. These approaches were evaluated on relatively simple tasks using hand-coded support predicates, demonstrating the difficulty of transfer using a tree-based approach. Our evaluation does not use any support predicates and shows that GRL can learn good policies that transfer well to larger problems.

RePReL [Kokel et al., 2021] uses a high-level planner together with hand-coded abstractions to train task-specific RL agents for transfer learning. Rosenfeld et al. [2017] use hand-crafted features and similarity functions to speed up Qlearning. MBRRL [Ng and Petrick, 2021a; Ng and Petrick, 2021b] learns conjunctive first-order features for Q-function approximation using hand-coded contextual information for improved performance. In contrast to these approaches, GRL does not require any hand-coded or expert knowledge.

Policy-based approaches Fern et al. [2006] use taxonomic syntax with beam search and approximate policy iteration to learn decision-list policies. They sample sub-goals using random walks to scale up learning. However, it is not clear how to apply their approach to problems that do not have goals. GRL can work on problems with or without goals. Janisch et al. [2020] use graph neural network (GNN) representations of the state to compute policies. GNNs are reliant on the network's receptive field unlike QGRL which uses multilayer perceptrons and thus have limited generalization capabilities w.r.t. the number of objects. TraPSNet [Garg et al., 2019] also uses a GNN and is limited to domains with a single binary predicate and actions with a single parameter. Moreover, the binary predicate in TraPSNet is required to be a non-fluent meaning that its truth value in a problem can never change. GRL can be used in domains with any number of action parameters and binary predicates and allows binary predicates to change their valuations across different states.

Automatic Curriculum Generation Fern et al. [2006] sample goals from random walks on a single problem. Their approach relies on the target problem to adequately represent the goal distribution for generalization. Similar ideas are explored in Ferber et al. [2020] and Andrychowicz et al. [2017]. These techniques are intra-instance, sampling different goals from the same state space and are orthogonal to GRL, that addresses inter-instance transfer. Our approach of leapfrogging is most similar to that of Groshev et al. [2018] and Karia and Srivastava [2021] and the learn-from-small-examples approach of Wu and Givan [2007]. We extend their ideas to RL settings and demonstrate its efficacy in transfer. Narvekar and Stone [2019] automatically generate a curriculum for tasks by solving a curriculum MDP (CMDP). However, they require domain-dependent, hand-coded basis features for effective curriculum learning whereas leapfrogging does not require any domain-dependent hand-coding.

6 Conclusion

We presented an approach for reinforcement learning in relational domains that can learn good policies with effective zero-shot transfer capabilities. Our results show that Description Logic based features acquired simply through state trajectory sequences can offer performance similar to that of of analytical (closed-form) action models. In the future, we plan to investigate improving the features so that abstract actions can also take into account relationships between the instantiated parameters and the abstract state.

Acknowledgements

We would like to thank the Research Computing Group at Arizona State University for providing compute hours for our experiments. This research was supported in part by the NSF under grant IIS 1942856.