# Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 58 references that are in the map.
- First posted on arXiv 21 Sep 2021.

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

- [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)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Inductive Biases for Deep Learning of Higher-Level Cognition](https://mlsanity.com/paper/2011.15091/) (2020)
- [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)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective](https://mlsanity.com/paper/2003.00330/) (2020)
- [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)
- [The Value-Improvement Path: Towards Better Representations for Reinforcement Learning](https://mlsanity.com/paper/2006.02243/) (2020)
- [A Geometric Perspective on Optimal Representations for Reinforcement Learning](https://mlsanity.com/paper/1901.11530/) (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 Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [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)
- [Automatic Induction of Bellman-Error Features for Probabilistic Planning](https://mlsanity.com/paper/1401.3847/) (2014)

## Built on by (most cited first, 30 of 38)

- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)
- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [Symmetries and Expressive Requirements for Learning General Policies](https://mlsanity.com/paper/2409.15892/) (2024)
- [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Symmetry-Aware Transformer Training for Automated Planning](https://mlsanity.com/paper/2508.07743/) (2025)
- [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)
- [Understanding Sample Generation Strategies for Learning Heuristic Functions in Classical Planning](https://mlsanity.com/paper/2211.13316/) (2022)
- [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)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [Sketch Decompositions for Classical Planning via Deep Reinforcement Learning](https://mlsanity.com/paper/2412.08574/) (2024)
- [Learning Efficiency Meets Symmetry Breaking](https://mlsanity.com/paper/2504.19738/) (2025)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [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)
- [WLPlan: Relational Features for Symbolic Planning](https://mlsanity.com/paper/2411.00577/) (2024)
- [LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning](https://mlsanity.com/paper/2605.29649/) (2026)
- [Provably Complete Generalized Planning with LLMs](https://mlsanity.com/paper/2609.27105/) (2026)
- [Language-Based Causal Representation Learning](https://mlsanity.com/paper/2207.05259/) (2022)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [Relational GNNs Cannot Learn C2 Features for Planning](https://mlsanity.com/paper/2506.11721/) (2025)

## Abstract (arXiv)

It has been recently shown that general policies for many classical planning domains can be expressed and learned in terms of a pool of features defined from the domain predicates using a description logic grammar. At the same time, most description logics correspond to a fragment of k-variable counting logic (Ck) for k=2, that has been shown to provide a tight characterization of the expressive power of graph neural networks. In this work, we make use of these results to understand the power and limits of using graph neural networks (GNNs) for learning optimal general policies over a number of tractable planning domains where such policies are known to exist. For this, we train a simple GNN in a supervised manner to approximate the optimal value function V*(s) of a number of sample states s. As predicted by the theory, it is observed that general optimal policies are obtained in domains where general optimal value functions can be defined with C2 features but not in those requiring more expressive C3 features. In addition, it is observed that the features learned are in close correspondence with the features needed to express V* in closed form. The theory and the analysis of the domains let us understand the features that are actually learned as well as those that cannot be learned in this way, and let us move in a principled manner from a combinatorial optimization approach to learning general policies to a potentially, more robust and scalable approach based on deep learning.