Sketch Decompositions for Classical Planning via Deep Reinforcement Learning

1 Introduction

A common challenge in planning and reinforcement learning is achieving goals that require many actions. Addressing this challenge typically involves learning useful subgoals or hierarchical policies that abstract primitive actions [Sutton et al., 1999; McGovern and Barto, 2001; Kulkarni et al., 2016; Park et al., 2024]. Yet the principles underlying the corresponding problem decompositions are not well understood. Consequently, methods for learning subgoals and hierarchical policies often lack robustness, working effectively in some domains while failing completely in others, without a clear explanation for these differences in performance. Recently, a powerful language for expressing, learning, and understanding general problem decompositions has been proposed [Bonet and Geffner, 2021; Drexler et al., 2022]. A sketch decomposition for a class of problems Q defines a set of subgoal states G(s) for each reachable state s in an instance P ∈ Q. In any state s, the planner's task is not to reach the distant problem goal but to move to a closer subgoal state in G(s).

The concept of a goal being easily reachable or not is formalized through the notion of problem width [Lipovetzky and Geffner, 2012; Bonet and Geffner, 2024]. A class of problems with width bounded by a constant k can be solved optimally by the IW(k) algorithm in time exponential in k. Many planning domains have a width no greater than 2 when goals are restricted to single atoms. A sketch decomposition G(·) divides problems P in class Q into subproblems P[s,G(s)], which resemble P but with initial state s and goal states G(s). If all these subproblems have width bounded by k, the decomposition width over Q is bounded by k, allowing the problems in Q to be solved by a greedy sequence of IW(k) calls, provided the decomposition is acyclic and safe, meaning no subgoal cycles or dead-end states among the subgoals [Bonet and Geffner, 2021].

Methods for learning safe, acyclic sketch decompositions with bounded width, represented by a set of sketch rules, have been developed [Drexler et al., 2022; Drexler et al., 2023], following techniques previously used for learning general policies [Frances et al., 2021]. These learning methods rely on feature pools derived from domain predicates and a min-cost SAT solver, leading to two key limitations: scalability and expressivity. Large feature pools enhance expressivity but result in large theories that are difficult for combinatorial solvers to handle.

In this work, we address these limitations by framing the problem of learning sketch decompositions as one of learning general policies in a deep reinforcement learning (DRL) context 1 . Here, feature pools are not made explicit, and combinatorial solvers are unnecessary. We build on a novel observation connecting sketch decompositions with general policies and leverage an existing implementation for learning general policies via DRL [St˚ahlberg et al., 2023]. The resulting method learns sketch decompositions bounded by a given width parameter k and uses them to search for goals across various domains through a greedy sequence of IW(k) searches. Unlike symbolic methods, the DRL approach does not produce rule-based sketches but neural network classifiers. However, as we will demonstrate, while interpreting these classifiers is not straightforward, it is often possible to understand the resulting decompositions in a crisp manner.

1 Appendix available on arXiv (arxiv.org/abs/2412.08574), code and data available on Zenodo (zenodo.org/records/15614893).

The structure of the paper is as follows. We begin with an illustrative example and relevant background. We then present the proposed formulation, followed by experiments, an analysis of the decompositions found, related work, and a concluding discussion.

2 Example

The Delivery domain, similar to the Taxi domain in hierarchical reinforcement learning, involves N packages spread across an n ×m grid, with an agent tasked to deliver them, one by one, to a target cell. The sketch decomposition G2, where s′ ∈ G2(s) if the number of undelivered packages u(·) is smaller in s′ than in s, yields subproblems P[s,G2(s)] of width bounded by 2, solved optimally by IW(2). The subproblems P[s,G2(s)] are like P but with initial state s and goal states G2(s). Similarly, the sketch decomposition G1, where s′ ∈ G1(s) if either u(s′ ) < u(s) and a package is held in s, or u(s′ ) = u(s) and a package is not held in s but is held in s′ , produces subproblems P[s,G1(s)] of width 1, solvable optimally by IW(1).

A previous approach learns such decompositions using feature pools, a width parameter k ∈ {1, 2}, and combinatorial methods [Drexler et al., 2022]. The decompositions are represented implicitly by collections of sketch rules. This work is aimed at learning similar width-k decompositions Gk(s) but using neural networks trained via reinforcement learning. While the learned representations will not be as transparent, we will see that the resulting decompositions often are. Figure 1 shows indeed the number of IW(1) and IW(2) calls needed to solve Delivery instances as a function of the number of packages N after learning two general domain decompositions G1 and G2 via deep reinforcement learning. The number of calls, 2N and N, match exactly the number of calls that would be needed to solve these instances using the sketch decompositions defined above, despite using no rule-based representation or explicit feature pool, but solely a neural net trained via RL.

3 Background

We briefly review classical planning, the notion of width, general policies and sketches, and methods for learning them, following Lipovetzky and Geffner [2012], Frances et al. [2021], Bonet and Geffner [2021], Drexler et al. [2022], and St˚ahlberg et al. [2023].

3.1 Classical and Generalized Planning

A planning problem or instance is a pair P = (D, I) where D is a first-order domain with action schemas defined over predicates, and I contains the objects in the instance and two sets of ground atoms defined over the objects and predicates defining the initial and goal situations Init and Goal . An instance P defines a state model S(P ) = (S, s0, G, Act , A, f ) where the states in S are the possible sets of ground atoms, each one capturing the atoms that are true in the state. The initial state s0 is Init, the set of goal states G are those that include the goal atoms Goal , and the actions Act are the ground actions obtained from the schemas and objects. The ground actions in A(s) are the ones that are applicable in a state s; namely, those whose preconditions are (true) in s, and the state transition function f maps a state s and an action a ∈ A(s) into the successor state s′ = f(a, s). A plan π for P is a sequence of actions a0, . . . , an that is executable in s0 and maps the initial state s0 into a goal state; i.e., ai ∈ A(si), si+1 = f(ai, si), and sn+1 ∈ G. A state s is solvable if there exists a plan starting at s, otherwise it is a dead-end. The cost of a plan is assumed to be given by its length, and a plan is optimal if there is no shorter plan.

A generalized planning problem instead is given by a collection Q of instances P = (D, I) from a given domain; for example, all instances of Blocks world where the goal just involves on atoms. The solution of a generalized problem is not an open-loop action sequence but a closed loop policy as detailed below. In general, the instances in Q are assumed to be solvable, and moreover, the set Q is normally assumed to be closed in the sense that if P is in Q with initial state s0 and P ′ is P but with a solvable initial state reachable from s0, then P ′ is assumed to be in Q as well.

3.2 Width

The simplest width-based search procedure is IW(1), a modified breadth-first search over the rooted directed graph associated with the state model S(P). It prunes newly generated states that fail to make an atom true for the first time in the search. IW(k), for k > 1, extends this concept by pruning states that do not make a collection of up to k atoms true for the first time. These algorithms can be alternatively conceptualized using the notion of state novelty. In this view, IW(k) prunes states with novelty greater than k, where a state's novelty is defined by the size of the smallest set of atoms true in that state and false in all previously generated states. Central to these algorithms is the concept of problem width. The width of a problem P is determined by the size of the smallest chain of atom tuples t0, . . . tn that is admissible in P and has size maxi |ti| [Lipovetzky and Geffner, 2012]. For instance, Blocks World instances with atomic goals on(x, y) and Delivery instances with goals at(pkg, loc) have width 2 or less.

IW(k) algorithms find optimal (shortest) solutions in time and space exponential to the problem width. However, planning problems with multiple conjunctive goals often lack a bounded width (i.e., width independent of the instance size). To address this, a variant called SIW was developed. SIW greedily seeks a sequence of IW calls, each decreasing the number #g of unachieved atomic goals [Lipovetzky and Geffner, 2012]. It starts with IW(1), escalating to IW(2) and beyond if IW(1) fails to reach a state that decreases #g. While SIW exploits a particular problem decomposition based on unachieved goals, this approach is not universally effective due to potential high-width or unsolvable subproblems. Complete, width-based search algorithms incorporate novelty measures within a best-first search [Lipovetzky and Geffner, 2017; Franc`es et al., 2017].

For convenience, the width of problems P that can be solved in at most one step, is said to have width 0. Hence, IW(0) is defined as breadth-first search that prunes all and only nodes at depth greater than 1, and IW(k) is adjusted to never prune nodes at level 1.

3.3 General Policies and Sketches

A simple but powerful way to express the solutions to generalized planning problems Q made up of a collection of instances P, is by means of rules of the form C ↦→ E defined over a set of features Φ [Bonet and Geffner, 2018]. A state pair [s, s′ ] satisfies the rule if C is true in s and the features in Φ change value when moving from s to s′ in agreement with E. For example, E can express that a numerical feature must increase its value, and that a Boolean feature must become true, etc. A set of rules R defines a non-deterministic general policy π for Q which in any reachable state s in P ∈ Q selects the successor states s′ of s when the state pair [s, s′ ] satisfies a rule in R. The transitions (s, s′ ) are then called πtransitions, and the policy π solves an instance P ∈ Q if all the π-trajectories that start in the initial state of P reach a goal state. 2

The same language used to define general policies can be used to define sketch decompositions. Indeed, a set of rules R defines the subproblems P [s, GR(s)] over the reachable nongoal states s of instances P ∈ Q, which are like P but with initial state s and goal states s′ ∈ GR(s) for the state pairs [s, s′ ] that satisfy a rule in R. The width of the decomposition is the maximum width of the subproblems P [s, GR(s)], P ∈ Q, and the decomposition is safe and acyclic in Q if there is no sequence of (subgoal) states s1, . . . , sn, si+1 ∈ G∗R(si) and n > 1, in any P ∈ Q that starts in a reachable, alive state s1 (not a dead-end, not a goal), and ends in a dead-end state sn or in the same state sn = s1. Here G∗R(s) stands for the states s′ ∈ GR(s) that are closest to s. If the decomposition resulting from the rules R is safe, acyclic, and has

2 These general policies do not map states directly to actions. Instead, they select state transitions and, only indirectly, actions. This choice is convenient for relating general policies and sketches [Bonet and Geffner, 2021].

Algorithm 1 Actor-Critic RL for generalized planning

• 1: Input: Training MDPs {Mi}i, each with state priors pi
• 2: Input: Policy π(s′ | s) with parameters θ
• 3: Input: Value function V (s) with parameters ω
• 4: Ouput: Policy π(s′ | s)
• 5: Parameters: Step sizes α, β > 0, discount factor γ
• 6: Initialize parameters θ and ω
• 7: Loop forever:
• 8: Sample MDP index i ∈ {1, . . . , n}
• 9: Sample non-goal state S in Mi with probability pi
• 10: Sample state S′ fromN(S) with prob. π(S′ | S)
• 11: Let δ = 1 + γV (S′ ) - V (S)
• 12: ω ← ω + βδ∇V (S)
• 13: θ ← θ -αδ∇logπ(S′ | S)
• 14: If S′ is a goal state, ω ← ω - βV (S′ )∇V (S′ )

width bounded by k, then the problems P ∈ Q can be solved by a slight variant of the SIW algorithm where a sequence of IW(k) calls is used to move iteratively and optimally from a state si to a subgoal state si+1 ∈ GR(si), starting from the initial state of P and ending in a goal state [Bonet and Geffner, 2021].

3.4 Learning General Policies through DRL

Rule-based policies and sketches can be learned without supervision by solving a min-cost SAT problem over the state transitions of a collection of small training instances P from Q and a pool of features derived from domain predicates and a fixed set of grammar rules based on description logics [Bonet et al., 2019; Drexler et al., 2022]. However, some domains require highly expressive features, which necessitate the application of numerous grammar rules, leading to large feature pools that challenge combinatorial solvers. 3

To address this limitation, a recent approach introduced learning general policies in a deep reinforcement learning (DRL) setting [St˚ahlberg et al., 2023]. This approach employs a standard actor-critic RL algorithm [Sutton and Barto, 1998] with the policy and value functions π(s′ | s) and V (s) represented by neural networks. As shown in Fig. 1, gradient descent updates the parameters θ and ω of the policy and value functions. The key difference from standard actor-critic codes is that π selects the next state from possible successors N(s) instead of the next action.

The learned policy functions generalize to larger domain instances than those used in training. This generalization is achieved by encoding the policy and value functions in terms of a relational GNN, which generates real-vector embeddings f s (o) for each object in the instance [Scarselli et al., 2008; Hamilton, 2020]. Suitable readout functions then map these embeddings into the values V (s) and probabilities π(s′ | s).

3 A second type of expressive limitation, not discussed here, involves domains where rule-based policies and sketches may require features beyond the capabilities of standard description logic grammars, which are generally fragments of first-order logic with two variables and counting. This limitation also affects non-symbolic approaches based on GNNs [St˚ahlberg et al., 2022; Horˇc´ık and ˇS´ır, 2024].

4 Learning Decompositions via DRL

The contribution of this paper is a novel scheme for learning how to decompose planning problems into subproblems that can be solved through iterative applications of the IW(k) algorithm. Decomposing problems into subproblems is crucial, but the principles guiding such decompositions are not welldefined. Our goal is to achieve decompositions that are general (applicable across a class of problems Q), safe (avoiding dead-ends), acyclic, and have width bounded by k. Additionally, we aim to learn these decompositions without relying on combinatorial solvers or explicit feature pools, leveraging the relationship between sketch compositions and general policies, as well as the method reviewed above for learning general policies through DRL.

It is known that general policies are sketch decompositions of zero width, which are safe and acyclic [Bonet and Geffner, 2024]. Our new observation is that safe, acyclic sketch decompositions with approximate width k > 0 for a class of problems P ∈ Q can be derived from general policies over a slightly different class of problems Pk ∈ Qk, where the set of successor states N(s) in P is replaced by the set Nk(s) of states reachable from s via IW(k):

The successor states s′ that the policy π(s′ | s) selects in Pk will be subgoal states s′ in P that can be reached from s via IW(k). The decomposition's width is approximately bounded by k because while a width bounded by k guarantees reachability via IW(k), the reverse is not necessarily true. 4

The modification of the DRL algorithm from [St˚ahlberg et al., 2023] to learn safe and acyclic decompositions of width k over a class of problems P ∈ Q is straightforward: the only change required is to replace the set of successor states N(s) in line 10 of Algorithm 1 with the set Nk(s) reachable from s via IW(k). This extended set of successor states is then used in the softmax normalization to yield the probabilities π(s′ | s). Action costs are assumed to be all 1 for reaching either N or Nk successors.

Let π(s′ | s) be the general stochastic policy learned by the algorithm in Fig. 1 after replacing N(s) with Nk(s). The resulting decomposition Gπk (·) can then be defined in two ways: greedily, as the singleton sets:

and stochastically, as the singleton sets:

In the first case, a single subgoal state s′ for s is chosen as the most likely state in Nk(s) according to the learned policy π; in the second, case, s′ is sampled stochastically from the set Nk(s) with probability π(s′ | s). In P, s′ may not be a direct successor of s but can be reached from s via IW(k). Intuitively, to decompose the problem, we are allowing the

4 Lipovetzky and Geffner [2012] refer to reachability via IW(k) as effective width k, which is not a robust notion of width, as it is influenced by the order in which child nodes are explored in the breadth-first search.

"agent" to make IW(k) "jumps" in P following the learned policy for Pk where such "jumps" are primitive actions.

If the policy π solves the problem Pk, then the decomposition Gπk will be safe and acyclic. A sequence of subgoal states s0, s1, . . . , sn with n > 1 and si+1 ∈ Gπk (si) for i = 1, . . . , n-1, cannot be cyclic or unsafe, as that would imply the existence of π-trajectories that do not reach the goal, contradicting the assumption that π solves Pk. Additionally, this implies the subproblems P[s,Gπk (s)] to have an approximate width bounded by k, as Gπk (s) ∈ Nk(s) only includes states reachable from s via IW(k).

In summary, Algorithm 1 is adapted with minor modifications to learn a safe, acyclic, and width-k decomposition Gk(s) for a class of problems Q, though without formal guarantees. 5 The only change involves replacing the set of successor states N(s) in P ∈ Q with the set Nk(s) defined in (1). The learned stochastic general policy π for the resulting class of problems Pk ∈ Qk defines the decomposition Gk = Gπk over Q as described in (3).

At test time, the decomposition Gπk is evaluated by running the IW(k) algorithm sequentially from a state s to a state s′ in Gπk (s) until reaching the goal or a maximum number of IW(k) calls. We refer to this algorithm, which applies IW(k) searches to the decomposition Gπk (s) based on the learned policy π, as SIWπ (k). Unlike the SIW algorithm, SIWπ (k) performs a greedy sequence of IW(k) searches rather than IW searches, requiring each search to end in a state within Gπk (s), not merely a state where the number of unachieved top goals has decreased. Moreover, unlike SIW, SIWπ (k) requires IW(k) searches to run to completion, as this is necessary for determining the extended set of successors Nk(s) in the decomposition Gπk (s) defined in (1).

5 Experiments

The experiments aim to address several key questions. First, are the learned decompositions Gk = Gπk both general and effective? Specifically, can the (larger) test instances be solved by a greedy sequence of IW(k) calls? This question is non-trivial, as success with k = 1 would imply solving instances with linear memory relative to the number of atoms by running IW(1) sequentially, a significant contrast to solving instances via exponential time and memory search. Second, can the resulting decompositions, represented in the neural network, be understood and interpreted? This is also challenging, as there is no guarantee that the learned decompositions will be meaningful. To answer the first question, we will examine the coverage of the SIWπ (k) algorithm using the learned decomposition Gπk , the number of IW(k) calls (subgoals), and the total plan length. To address the second question, we will analyze plots showing the number of subgoals resulting from the learned decomposition Gπk as a function of relevant parameters of the test instances (e.g., the number of packages). In the experiments, the subgoal states Gπk (s) are sampled stochastically according to (3), although the results (in the appendix) are not too different when they are chosen deterministically as in (2). The code and data will be made publicly available.

5 The symbolic method for learning sketches [Drexler et al., 2022] enforces these properties in the training set but cannot guarantee them over the test set. However, this can be addressed manually, case by case.

Learning Setup. We use the DRL implementation from [St˚ahlberg et al., 2023] with the same hyperparameters to learn the policy π that defines the decomposition Gπk . The GNN has feature vectors of size 64 and 30 layers. The ActorCritic algorithm uses a discount factor γ = 0.999, a learning rate α = 2 × 10-4 , the Adam optimizer [Kingma and Ba, 2015], and runs on a single NVIDIA A10 GPU for up to 48 hours per domain. Five models are trained independently with different seeds, and the model with the best validation score is selected for testing. The validation score is determined by the ratio LV /L∗V , where LV is the plan length from SIWπ (k) and L∗V is the optimal plan length, both averaged over all states of a validation set. Training is stopped early if this ratio approaches 1.0.

Data. The domains and training data are primarily from previous works on learning sketches and general policies [Drexler et al., 2022; St˚ahlberg et al., 2023]. This includes Blocks with single and multiple target towers, Childsnack, Delivery, Grid, Gripper, Logistics, Miconic, Reward, Spanner, and Visitall. Each domain is tested on 40 larger instances, which extend those used in prior studies (details in the appendix).

5.1 Results

Table 1 presents the performance of the SIWπ (k) algorithm using the learned Gπk decomposition, where π is the policy derived from the RL algorithm after replacing the set of successors N(s) with Nk(s). Key performance metrics include coverage (Cov), subgoal count (SL), and plan length (L). The table's upper section shows results for IW(1), while the lower section displays IW(2) results for selected domains.

In the table, LM indicates the plan length computed by the classical planner LAMA, run on an Intel Xeon Platinum 8352M CPU with a 10-minute time and 100 GB memory limit. The columns labeled "subgoal cycle prevention" reflect a minor SIWπ (k) algorithm modification that avoids revisiting a subgoal state. For this, states that have already been selected as subgoals before are not considered as future subgoals. This adjustment impacts performance in three of the eleven domains, including two (Grid and Logistics) where the width-1 decompositions learned were poor.

Coverage The SIWπ (k) algorithm achieves nearly perfect coverage across all domains, except in Logistics, Grid, and Blocksworld-Multiple with IW(1). However, for width-2 decompositions, coverage improves to near 100% in all domains, including these three. By contrast, neither baseline was able to reach this performance.

The reason for this discrepancy in results by width is not entirely clear, but one possibility is that width-1 sketch decompositions cannot be fully captured in the logical fragment represented by GNNs. It is known that GNNs cannot represent width-0 sketch decompositions (i.e., general policies) for Logistics and Grid [St˚ahlberg et al., 2022], suggesting that the same might hold for width-1 decompositions. Interestingly, GNNs do accommodate width-2 sketch decompositions in these domains, as shown in the table, aligning with findings from previous research, which observed that while certain feature pools cannot express rule-based general policies, they can express rule-based sketches.

Subgoal Count The column SL in the table presents the average number of subgoals encountered by SIWπ (k) on the path to the goal. Although this number alone may not be highly meaningful, it is significantly lower than the average plan lengths, indicating that each subgoal requires multiple actions to be achieved. More interestingly, Figure 2 illustrates the number of subgoals as a function of the number of objects of a selected type per domain (e.g., packages in Delivery, balls in Gripper, children in Childsnack) for k = 1, and also k = 2 for Blocks. In the former cases, the relationship is nearly linear, with a coefficient of 1 in Spanner and Reward, and 2 in Delivery, Gripper, Childsnack, and Miconic. This suggests that the decomposition divides the problem into subproblems, one for each relevant object, which in some cases are further split in two (e.g., in Delivery, each package must be picked up and dropped off in separate IW(1) calls). Despite the use of neural networks and DRL, the resulting decompositions can be understood. In Blocksworld, however, the situation is different. The width-1 decomposition generates more subgoals than there are on-atoms in the goal (shown in black versus red), while the width-2 decomposition generates fewer subgoals than on-atoms in the goal (shown in blue). While individual on-atoms have a width of 2 and are thus always reachable by IW(2), certain states allow for pairs of on-atoms to be reached by IW(2) as well. The result is that the plots of subgoal counts in Blocksworld are not showing strict linear relationships.

Plan Quality The column L/LM in the table shows the ratio between the average plan lengths found by SIWπ (k) and those found by LAMA. Generally, this ratio is close to 1, but there are exceptions in certain domains, such as Reward and Visitall for IW(1) and several others for IW(2). The general explanation is that decompositions simplify the problems, allowing them to be solved by a linear search like IW(1), rather than an exponential search as in LAMA. This simplification, however, can preclude shortcuts, resulting in longer plans. A more specific explanation is that the DRL algorithm minimizes the number of IW(k) subproblems on the path to the goal, without considering the cost of solving these subproblems, as measured by the number of actions required. For instance, if a single package is to be delivered from a state s with two options-a nearby package and a distant oneSIWπ (k) does not prefer one over the other since both states s′ and s′′ where either package is held are Nk-successors of s with the same cost of 1. Naturally, the Drexler et al. [2022] baseline also exhibits such plan deficits, though to a lesser extent, whereas St˚ahlberg et al. [2023] can surpass LAMA in some domains due to directly optimizing plan cost.

To address this limitation, two approaches could be considered: 1) modifying SIWπ (k) to prefer Nk-successors s′ that have a high probability π(s′ | s) and are closer to s, or 2) retaining the true cost information of Nk-successors and using this in the DRL algorithm to optimize a combination of the number of subgoals and the cost of achieving them. The first approach would involve modifying the SIWπ (k) algorithm, while the second would require changes to the training process. Exploring these approaches, however, is beyond the scope of this work.

It is also worth noting that problem representations (in PDDL) influence problem width and overall plan length. For example, the width-1 decomposition for Gripper results in moving balls from one room to the next one by one, even though two grippers are available. This explains why the plans generated by SIWπ (1) are 33% longer than those computed by LAMA, which are optimal. One reason for this inefficiency is that IW(1) cannot load two grippers in a single call; the problem indeed has a width of 2. This situation would differ if the problem representation included a single atom that is true when both grippers are full. Thus, the ability to learn width-k decompositions is not just limited by the expressive power of GNNs, but also by the problem representation. Making these limitations and these dimensions explicit is a strength of our approach, enabling us to understand the general decompositions that are learned and those that are not or cannot be learned, rather than relying solely on performance metrics.

Baselines We also compare our method against two widthk decomposition baselines: the general policy deep RL framework of St˚ahlberg et al. [2023] with k = 0, and the rulebased combinatorial sketch synthesis approach of Drexler et al. [2022] with k = 1, 2.

Our method combines aspects of both, as it learns sketch decompositions from deep RL, but not in the form of rules. Empirically, our approach can solve domains in which both baselines fail. For instance, in Logistics and Grid, SIWπ (2) devises near-perfect width-2 decompositions, whereas both baselines fail to achieve substantial coverage. Similarly, in other grid-based environments (Reward, Visitall, Delivery), our decomposition approach attains 100% coverage, improving over the inconsistent performance of policies by St˚ahlberg et al. [2023]. Overall, our results demonstrate that learning subgoal-based decompositions via DRL imposes less expressive demands than learning general policies and scales better than combinatorial optimization. Further details on the baselines, can be found in the appendix.

6 Analysis

The symbolic approach to problem decompositions using sketch rules offers transparency, allowing direct interpretation of the defined decompositions. Interestingly, the inverse process is also possible: equivalent sketch rules can be reconstructed from learned decompositions by analyzing subgoal counts and plan structures. Indeed, the width-1 decompositions learned for Delivery, Gripper, Miconic, Childsnack, and Spanner can be understood in terms of four sketches with numerical features Ni and Boolean feature H:

Sketch R1 is a simple feature-decrementing sketch, capturing the decomposition in Reward, where N denotes the number of uncollected rewards. R2 models the decomposition in Delivery, where H indicates whether an undelivered package is held, and N tracks the number of undelivered packages. R3 uses two-counters, and prioritizes decrementing N2 until exhaustion, then focuses on N1. This ruleset characterizes the decomposition of domains like Miconic and Childsnack, where N2 represents intermediate goals (e.g., sandwiches to make, passengers to board) and N1 denotes final objectives (e.g., children/passengers to serve).

The plans in the Spanner domain follow the sketch R3, where the agent first picks up all the spanners (decrementing N1) and then tightens all the nuts (decrementing N2). If this process were perfectly aligned with the sketch, the points in the plot would fall exactly on the line y = x. However, the slight deviations from this line allow two observations. Points above the line represent unnecessary subgoals where neither N1 nor N2 change. Points below the line indicate shortcuts in instances with more spanners than nuts where some of the spanners are left uncollected. Often, in these cases however, more spanners are picked up than strictly needed. A possible explanation is that computing the minimum number of spanners to collect, in order to solve the task, may be beyond the expressivity of GNNs given the state encodings.

Finally, R4 extends R3 with a potential increment of N2 when decrementing N1. These rules describe the decomposition in Gripper, where N1 represents undelivered balls and N2 denotes balls available for pickup, i.e., the minimum of undelivered balls and free grippers. Indeed, the model alternates between picking and delivering balls, but only once both grippers hold a ball.

7 RelatedWork

Methods for decomposing problems into subproblems have been extensively studied in hierarchical planning [Erol et al., 1994; Nau et al., 1999; Georgievski and Aiello, 2015]. Hierarchical representations can be derived from precondition relaxations [Sacerdoti, 1974] and causal graphs [Knoblock, 1994], or learned from annotated traces [Hogg et al., 2008; Zhuo et al., 2009]. In RL, problem substructure emerges in the form of options [Sutton et al., 1999], hierarchies of abstract machines [Parr and Russell, 1997], MaxQ hierarchies [Dietterich, 2000], reward machines [Icarte et al., 2018; De Giacomo et al., 2020], and intrinsic rewards [Singh et al., 2010; Zheng et al., 2020], among others. Although this knowledge is often provided by hand, methods for learning these structures have leveraged concepts such as "bottleneck states" [McGovern and Barto, 2001], eigenvectors of the transition dynamics [Machado et al., 2017], and informal widthbased notions [Junyent et al., 2021]. Additionally, two-level hierarchical policies in DRL have been explored [Kulkarni et al., 2016; Park et al., 2024], with the assumption that a master policy can make multi-step "jumps" executed by a low-level worker policy. However, the challenge with bounding these jumps by a fixed number of steps (e.g., 8 steps) is that it fails to capture meaningful substructure that generalizes to larger instances.

Our approach is closely related to these two-level hierarchies but differs in that the "jumps" are bounded by the concept of width, and instead of being executed by a lowlevel policy, they are managed by polynomial-time IW(k) procedures. In principle, these two ideas can be combined. Indeed, symbolic methods for learning hierarchical policies based on width-based considerations have also been developed [Drexler et al., 2023].

8 Conclusion

We have shown that DRL methods can learn subgoal structures for entire collections of planning problems, enabling efficient solutions via greedy IW(k) searches. Though represented by neural networks rather than symbolic rules, these decompositions are often interpretable logically. Our experiments show that decompositions learned from small instances generalize to much larger ones via linear and quadratic IW(1) and IW(2) searches. By leveraging width, sketches, and GNN logic, the approach's limitations can be understood and addressed within this framework.

Two challenges for future work include: (1) incorporating subproblem costs to reduce plan lengths without sacrificing meaningful decompositions, and (2) developing two-level hierarchical policies to avoid IW(k) searches in subproblems.

Acknowledgements

Thanks to Simon St˚ahlberg for providing the code of Muninn. The research has been supported by the Alexander von Humboldt Foundation with funds from the Federal Ministry for Education and Research, Germany. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovations programme (Grant agreement No. 885107). This project was also funded by the German Federal Ministry of Education and Research (BMBF) and the Ministry of Culture and Science of the German State of North Rhine-Westphalia (MKW) under the Excellence Strategy of the Federal Government and the L¨ander.