# Learning Generalized Policies Without Supervision Using GNNs

arXiv: https://arxiv.org/abs/2205.06002 · HTML: https://mlsanity.com/paper/2205.06002/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 12 May 2022.

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning](https://mlsanity.com/paper/1810.08272/) (2018)
- [An Introduction to Deep Reinforcement Learning](https://mlsanity.com/paper/1811.12560/) (2018)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Learning with AMIGo: Adversarially Motivated Intrinsic Goals](https://mlsanity.com/paper/2006.12122/) (2020)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Learning First-Order Symbolic Representations for Planning from the Structure of the State Space](https://mlsanity.com/paper/1909.05546/) (2019)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Features, Projections, and Representation Change for Generalized Planning](https://mlsanity.com/paper/1801.10055/) (2018)
- [Unsupervised Grounding of Plannable First-Order Logic Representation from Images](https://mlsanity.com/paper/1902.08093/) (2019)
- [Learning First-Order Representations for Planning from Black-Box States: New Results](https://mlsanity.com/paper/2105.10830/) (2021)
- [Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning](https://mlsanity.com/paper/2007.06702/) (2020)
- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [Generalized Planning With Procedural Domain Control Knowledge](https://mlsanity.com/paper/1910.04999/) (2019)
- [Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version](https://mlsanity.com/paper/2105.04250/) (2021)

## Built on by (most cited first, 22 of 22)

- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [Symmetries and Expressive Requirements for Learning General Policies](https://mlsanity.com/paper/2409.15892/) (2024)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [Symmetry-Aware Transformer Training for Automated Planning](https://mlsanity.com/paper/2508.07743/) (2025)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)
- [Leveraging Action Relational Structures for Integrated Learning and Planning](https://mlsanity.com/paper/2504.20318/) (2025)
- [First-Order Representation Languages for Goal-Conditioned RL](https://mlsanity.com/paper/2512.19355/) (2025)
- [Graph Neural Network Based Action Ranking for Planning](https://mlsanity.com/paper/2412.04752/) (2024)
- [Per-Domain Generalizing Policies: On Validation Instances and Scaling Behavior](https://mlsanity.com/paper/2505.00439/) (2025)
- [Learning General Policies with Policy Gradient Methods](https://mlsanity.com/paper/2512.19366/) (2025)
- [Exploration Policies for On-the-Fly Controller Synthesis: A Reinforcement Learning Approach](https://mlsanity.com/paper/2210.05393/) (2022)
- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [On Policy Reuse: An Expressive Language for Representing and Executing General Policies that Call Other Policies](https://mlsanity.com/paper/2403.16824/) (2024)
- [Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains](https://mlsanity.com/paper/2404.02499/) (2024)
- [Learning to Ground Existentially Quantified Goals](https://mlsanity.com/paper/2409.20259/) (2024)
- [Meta-operators for Enabling Parallel Planning Using Deep Reinforcement Learning](https://mlsanity.com/paper/2403.08910/) (2024)
- [Learning General Policies From Examples](https://mlsanity.com/paper/2509.02794/) (2025)
- [On Sample-Efficient Generalized Planning via Learned Transition Models](https://mlsanity.com/paper/2602.23148/) (2026)
- [Per-Domain Generalizing Policies: On Learning Efficient and Robust Q-Value Functions (Extended Version with Technical Appendix)](https://mlsanity.com/paper/2603.17544/) (2026)
- [Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning](https://mlsanity.com/paper/2605.18674/) (2026)
- [Learning Admissible Heuristics via Cost Partitioning](https://mlsanity.com/paper/2606.04597/) (2026)

## Abstract (arXiv)

We consider the problem of learning generalized policies for classical planning domains using graph neural networks from small instances represented in lifted STRIPS. The problem has been considered before but the proposed neural architectures are complex and the results are often mixed. In this work, we use a simple and general GNN architecture and aim at obtaining crisp experimental results and a deeper understanding: either the policy greedy in the learned value function achieves close to 100% generalization over instances larger than those used in training, or the failure must be understood, and possibly fixed, logically. For this, we exploit the relation established between the expressive power of GNNs and the C2 fragment of first-order logic (namely, FOL with 2 variables and counting quantifiers). We find for example that domains with general policies that require more expressive features can be solved with GNNs once the states are extended with suitable "derived atoms" encoding role compositions and transitive closures that do not fit into C2. The work follows the GNN approach for learning optimal general policies in a supervised fashion (Stahlberg, Bonet, Geffner, 2022); but the learned policies are no longer required to be optimal (which expands the scope, as many planning domains do not have general optimal policies) and are learned without supervision. Interestingly, value-based reinforcement learning methods that aim to produce optimal policies, do not always yield policies that generalize, as the goals of optimality and generality are in conflict in domains where optimal planning is NP-hard.