# Hierarchical Width-Based Planning and Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 23 references that are in the map.
- First posted on arXiv 15 Jan 2021.

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://mlsanity.com/paper/1901.10995/) (2019)
- [Planning from Pixels in Atari with Learned Symbolic Representations](https://mlsanity.com/paper/2012.09126/) (2020)
- [Deep Policies for Width-Based Planning in Pixel Domains](https://mlsanity.com/paper/1904.07091/) (2019)
- [Planning with Pixels in (Almost) Real Time](https://mlsanity.com/paper/1801.03354/) (2018)

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

- [General Policies, Subgoal Structure, and Planning Width](https://mlsanity.com/paper/2311.05490/) (2023)
- [Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning](https://mlsanity.com/paper/2106.04866/) (2021)
- [Sketch Decompositions for Classical Planning via Deep Reinforcement Learning](https://mlsanity.com/paper/2412.08574/) (2024)
- [Is Policy Learning Overrated?: Width-Based Planning and Active Learning for Atari](https://mlsanity.com/paper/2109.15310/) (2021)
- [Width-based Lookaheads with Learnt Base Policies and Heuristics Over the Atari-2600 Benchmark](https://mlsanity.com/paper/2106.12151/) (2021)
- [Multi-stage Planning for Multi-target Surveillance using Aircrafts Equipped with Synthetic Aperture Radars Aware of Target Visibility](https://mlsanity.com/paper/2604.16962/) (2026)

## Abstract (arXiv)

Width-based search methods have demonstrated state-of-the-art performance in a wide range of testbeds, from classical planning problems to image-based simulators such as Atari games. These methods scale independently of the size of the state-space, but exponentially in the problem width. In practice, running the algorithm with a width larger than 1 is computationally intractable, prohibiting IW from solving higher width problems. In this paper, we present a hierarchical algorithm that plans at two levels of abstraction. A high-level planner uses abstract features that are incrementally discovered from low-level pruning decisions. We illustrate this algorithm in classical planning PDDL domains as well as in pixel-based simulator domains. In classical planning, we show how IW(1) at two levels of abstraction can solve problems of width 2. For pixel-based domains, we show how in combination with a learned policy and a learned value function, the proposed hierarchical IW can outperform current flat IW-based planners in Atari games with sparse rewards.