First-Order Representation Languages for Goal-Conditioned RL

AI summary

Overview

Research area: Reinforcement learning and automated planning — specifically goal-conditioned RL (GCRL) and generalized planning using first-order (relational) representation languages.

Technical level: Advanced. The paper assumes familiarity with classical planning (STRIPS-style domains), Markov decision processes, Q-learning, and graph neural networks.

Scope in one sentence: The paper introduces and evaluates three variants of Hindsight Experience Replay that differ only in how hindsight goals are defined — full states, subsets of the original goal, or lifted (first-order) versions of those subgoals — and shows that the latter two learn general policies on large, sparse-reward planning instances.

What This Paper Is About

In planning problems with huge state spaces and sparse rewards, random exploration almost never reaches the goal, so learning stalls. Hindsight Experience Replay (HER) solves this by relabeling failed trajectories as successes for a goal that was actually achieved. This paper asks how the form of that relabeled goal matters when states and goals are represented as sets of first-order atoms, and whether richer hindsight goals let an agent learn policies that generalize across states and goals in large planning instances.

Key Contributions

1. Three HER variants tailored to classical planning: state HER (hindsight goal is the full final state, mirroring standard HER), propositional HER (hindsight goal is the largest subset of the original ground goal satisfied at the end of a subtrajectory), and lifted HER (hindsight goal is a first-order schema, generated by lifting grounded goals through a goal-dependency graph so that structurally similar but differently grounded goals count).

2. A concrete algorithm for lifting goals (Algorithm 1): it builds a goal-dependency graph over the grounded goal, identifies connected components, enumerates valid subgraphs that do not split existing components, and replaces objects with variables plus inequality constraints — turning, for example, On(a,b) ∧ On(b,c) into On(X,Y) ∧ On(Y,Z) ∧ (X≠Y) ∧ (Y≠Z).

3. Scalability beyond prior RL work on generalized planning: the authors report that their approaches scale to billions of states without precomputing optimal values V*(s) for uniform sampling, unlike earlier RL approaches to generalized planning (Ståhlberg, Bonet, and Geffner 2023), which were limited to small instances.

4. Automatic curriculum learning: the paper shows that propositional and lifted HER naturally produce a curriculum of progressively harder goals (larger goal sizes, longer trajectories) without any explicit curriculum mechanism.

Main Findings

• Lifted and propositional HER substantially outperform state HER on coverage. Across 15 domains with 100 test instances each (1500 total), lifted HER solved 78.6% of instances (1179 instances, total plan length 224757), propositional HER solved 82.4% (1236 instances, total plan length 226349), and state HER solved only 51.0% (765 instances, total plan length 158242).

• The learned models solve more instances than LAMA. LAMA solved 80.8% of the 1500 instances (1212 instances, total plan length 312029, median 213.5, mean 257.4), while the propositional HER models solved 82.4% — despite operating under a greedy policy without backtracking, while LAMA can backtrack.

• Learned solutions are often much shorter than LAMA's. In Blocks, for instance, the learned models' median plan length was 96.7 (lifted), 107.3 (propositional), and 111.0 (state), versus 218.0 for LAMA. Overall medians in Table 3 are 136 for lifted, 136.5 for propositional, and 148 for state HER.

• Lifted HER learns faster and with lower variance. On the Blocks domain, lifted HER reaches nearly 100% coverage with fewer episodes than propositional HER and shows lower variance, especially in later episodes; state HER needs substantially more episodes and retains high variance.

• An automatic curriculum emerges from relabeling. Training plots for Blocks show mean goal size initially decreasing for lifted HER (as it learns to deconstruct towers) and then increasing, alongside growing trajectory length — evidence of progressively harder tasks. State HER's goal sizes stay large and roughly constant, with only a modest increase in trajectory length.

• Propositional HER fails entirely on the Maze domain. The paper reports that in Maze, not a single trajectory was relabeled by propositional HER, so it is omitted from that comparison.

• Several domains resist learning. In Delivery, only 12% (lifted) and 11% (propositional) and 0% (state) of instances were solved; the truck carries one package at a time, so delivering multiple packages to the same location by random exploration is extremely unlikely. In Hiking, all three methods reached 0% coverage, as informative trajectories are too improbable under random exploration.

• High coverage in some domains reflects model selection rather than robust learning. For Childsnack and, to some extent, Spanner, the authors attribute high coverage to selecting the best model across runs using the validation set. Dead-end states are relabeled as successes for the relabeled goal (e.g., when gluten-free ingredients run out in Childsnack, or when only some nuts are tightened in Spanner), so there is no training data on how to avoid dead-ends for the original goal.

• Coverage degrades with scale in some domains. In Reward and Visitall, coverage decreases as grid size increases, which the authors suggest may relate to model depth — distant cells may not communicate effectively with larger grids.

Methodology in Plain English

The setting is classical planning formalized as goal-conditioned RL: actions are deterministic, the environment is fully observable, the initial state is fixed, and every action yields a reward of −1, so the agent is rewarded for reaching the goal in as few steps as possible. Goal states are terminal, and states with no applicable action get a dummy no-op action.

States, applicable actions, and goals are encoded as sets of atoms fed into a relational graph neural network (R-GNN). To keep the three sources distinct, the authors introduce new predicate symbols for applicable actions (P_A) and for goal atoms (P_G), plus a new object o_a for each applicable action. The R-GNN produces an embedding f(o) per object, and the Q-value is computed by a small MLP over the action object's embedding concatenated with the sum of the embeddings of the original state objects. Computing Q-values for all applicable actions in parallel is a deliberate design choice, and the authors note that using only f(o_a) empirically generalizes worse. New predicate symbols depend only on the domain, not on a specific problem instance, so a model trained on one instance set can be applied to others in the same domain.

Training follows a DQN-style loop: experience generation with Boltzmann exploration (temperature T controls exploration), storage of individual transition tuples in a replay buffer, and mini-batch gradient descent on a squared-error loss with a target network updated every k episodes (k = 1 in the experiments). Hindsight relabeling is applied as a separate "Refine" step operating on whole trajectories, greedily extracting the longest non-overlapping, cycle-free subtrajectories that achieve the hindsight goal only at their final states.

The only difference between the three methods is the HindsightGoal function. State HER uses the final state s of the subtrajectory (including static atoms, kept for consistency with the original HER formulation). Propositional HER picks the largest subset of the original goal satisfied in s. Lifted HER lifts the grounded goal into a set of goal schemas using a goal-dependency graph, chooses the largest schema that has a grounding satisfied in s, and returns that grounding — or ⊥ when no grounding exists.

Domains come from Drexler et al. (2024), where C₂ expressiveness suffices to distinguish all non-isomorphic states, plus a Maze domain. Instances are split into train/validation/test sets with one or two scaling parameters; test sets reach up to 50 blocks, 119 children (allergy-free), 25 grids and 10 packages, 129 balls, 26 couples, 80 people and 81 floors, 29 grids and 14 rewards, 50 nuts, and 30 grid cells respectively. Models were trained with 10 seeds per method and domain on a system with an Intel Xeon Platinum 8352M CPU, 16 GB RAM, and an NVIDIA A10 GPU with 24 GB VRAM, for up to 12 hours per model. Evaluation uses a greedy policy for at most 1000 steps with actions leading to previously visited states excluded. A larger R-GNN variant uses residual updates, layer normalization, and readouts from both a random layer and the last layer, which the authors say was necessary to train networks with 100 layers.

Why This Matters

Impact on research. The paper bridges goal-conditioned RL and generalized planning by showing that the structure of hindsight goals — not just the fact of relabeling — drives generalization and data efficiency. It also demonstrates that automatic curricula can emerge from relabeling rather than requiring an explicit curriculum mechanism, and it pushes RL-based generalized planning to instance sizes far beyond prior work, which required precomputed optimal values on small state spaces.

Real-world applications (potential uses of general, goal-conditioned planners in this family):

• Robotic manipulation and assembly tasks where success is defined by a conjunction of relational conditions (stacking, placing, tightening).
• Logistics and delivery scheduling, where the Delivery domain's one-package-at-a-time constraint mirrors real fleet limitations.
• Automated task planning in industrial workflows and service scheduling (multi-floor transport as in Miconic, resource-constrained preparation as in Childsnack).
• Grid navigation and coverage tasks (Visitall, Maze) relevant to inspection and exploration robots.

Industry relevance. Learned policies that transfer from small training instances to much larger test instances, without per-instance solver calls, are attractive where classical planners are too slow or where a fast reactive policy is preferred. That the greedy learned models solved 82.4% of 1500 instances versus LAMA's 80.8%, often with much shorter plans, is a concrete indicator of practical potential — while the Delivery and Hiking failures show where more work is needed before deployment.

Future Directions

• Handling dead-end states. The relabeling process currently turns dead-ends into apparent successes, removing any training signal about avoiding them, which the authors identify as the source of problems in Childsnack and Spanner.
• Exploration in domains where random rollouts never deliver useful trajectories. Delivery (12% lifted, 11% propositional, 0% state) and Hiking (0% for all three) remain unsolved; the paper points to heuristic reward shaping by Gehring et al. (2022) as orthogonal and combinable with this approach.
• Scaling depth and communication over long distances. Coverage falls with grid size in Reward and Visitall, which the authors tentatively link to the model's depth and the ability of distant cells to communicate.
• Reducing reliance on validation-set model selection. In Childsnack and Spanner, good reported coverage depends on picking the best model across runs via the validation set, raising the question of how to obtain consistently strong policies rather than best-of-run results.
• Extending lifted goal generation beyond the current constraints. The goal-dependency graph avoids structurally irrelevant subgoals, but the paper leaves open how far this lifting scheme generalizes across broader goal structures.

Target Audience

Researchers and graduate students in reinforcement learning, automated planning, and neuro-symbolic AI, particularly those working on goal-conditioned RL, hindsight relabeling, relational/Graph Neural Network policies, or generalized planning. Practitioners interested in learning policies that transfer from small planning instances to much larger ones will also find the benchmark results (Table 3) and the failure analysis directly useful. Readers without a background in STRIPS-style planning, MDPs, and Q-learning will find the formal sections difficult.

Authors’ abstract

First-order relational languages have been used in MDP planning and reinforcement learning (RL) for two main purposes: specifying MDPs in compact form, and representing and learning policies that are general and not tied to specific instances or state spaces. In this work, we instead consider the use of first-order languages in goal-conditioned RL and generalized planning. The question is how to learn goal-conditioned and general policies when the training instances are large and the goal cannot be reached by random exploration alone. The technique of Hindsight Experience Replay (HER) provides an answer to this question: it relabels unsuccessful trajectories as successful ones by replacing the original goal with one that was actually achieved. If the target policy must generalize across states and goals, trajectories that do not reach the original goal states can enable more data- and time-efficient learning. In this work, we show that further performance gains can be achieved when states and goals are represented by sets of atoms. We consider three versions: goals as full states, goals as subsets of the original goals, and goals as lifted versions of these subgoals. The result is that the latter two successfully learn general policies on large planning instances with sparse rewards by automatically creating a curriculum of easier goals of increasing complexity. The experiments illustrate the computational gains of these versions, their limitations, and opportunities for addressing them.