# General Policies, Subgoal Structure, and Planning Width

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 84 references that are in the map.
- First posted on arXiv 9 Nov 2023.

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

- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Count-Based Exploration with Neural Density Models](https://mlsanity.com/paper/1703.01310/) (2017)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [What Can Learned Intrinsic Rewards Capture?](https://mlsanity.com/paper/1912.05500/) (2019)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Action Schema Networks: Generalised Policies with Deep Learning](https://mlsanity.com/paper/1709.04271/) (2017)
- [Features, Projections, and Representation Change for Generalized Planning](https://mlsanity.com/paper/1801.10055/) (2018)
- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version](https://mlsanity.com/paper/2203.14852/) (2022)
- [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)
- [Hierarchical Width-Based Planning and Learning](https://mlsanity.com/paper/2101.06177/) (2021)
- [Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning](https://mlsanity.com/paper/2106.04866/) (2021)
- [Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems](https://mlsanity.com/paper/2204.04301/) (2022)

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

- [Sketch Decompositions for Classical Planning via Deep Reinforcement Learning](https://mlsanity.com/paper/2412.08574/) (2024)
- [On Policy Reuse: An Expressive Language for Representing and Executing General Policies that Call Other Policies](https://mlsanity.com/paper/2403.16824/) (2024)
- [Mini-BEHAVIOR-Gran: Revealing U-Shaped Effects of Instruction Granularity on Language-Guided Embodied Agents](https://mlsanity.com/paper/2604.17019/) (2026)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [Learning General Policies From Examples](https://mlsanity.com/paper/2509.02794/) (2025)
- [Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning](https://mlsanity.com/paper/2605.18674/) (2026)

## Abstract (arXiv)

It has been observed that many classical planning domains with atomic goals can be solved by means of a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width, which in these cases is bounded and small. Yet, while the notion of width has become part of state-of-the-art planning algorithms such as BFWS, there is no good explanation for why so many benchmark domains have bounded width when atomic goals are considered. In this work, we address this question by relating bounded width with the existence of general optimal policies that in each planning instance are represented by tuples of atoms of bounded size. We also define the notions of (explicit) serializations and serialized width that have a broader scope as many domains have a bounded serialized width but no bounded width. Such problems are solved non-optimally in polynomial time by a suitable variant of the Serialized IW algorithm. Finally, the language of general policies and the semantics of serializations are combined to yield a simple, meaningful, and expressive language for specifying serializations in compact form in the form of sketches, which can be used for encoding domain control knowledge by hand or for learning it from small examples. Sketches express general problem decompositions in terms of subgoals, and sketches of bounded width express problem decompositions that can be solved in polynomial time.