# A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 3 Oct 2021.

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

- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://mlsanity.com/paper/1901.10995/) (2019)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Solving Hard AI Planning Instances Using Curriculum-Driven Deep Reinforcement Learning](https://mlsanity.com/paper/2006.02689/) (2020)

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

- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Environment Generation for Zero-Shot Compositional Reinforcement Learning](https://mlsanity.com/paper/2201.08896/) (2022)
- [Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning](https://mlsanity.com/paper/2206.14298/) (2022)
- [Lightweight Online Learning for Sets of Related Problems in Automated Reasoning](https://mlsanity.com/paper/2305.11087/) (2023)
- [Keke AI Competition: Solving puzzle levels in a dynamically changing mechanic space](https://mlsanity.com/paper/2209.04911/) (2022)
- [Rethinking Teacher-Student Curriculum Learning through the Cooperative Mechanics of Experience](https://mlsanity.com/paper/2404.03084/) (2024)
- [Graph Value Iteration](https://mlsanity.com/paper/2209.09608/) (2022)
- [Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem](https://mlsanity.com/paper/2508.08718/) (2025)
- [LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language](https://mlsanity.com/paper/2510.05972/) (2025)

## Abstract (arXiv)

In recent years, we have witnessed tremendous progress in deep reinforcement learning (RL) for tasks such as Go, Chess, video games, and robot control. Nevertheless, other combinatorial domains, such as AI planning, still pose considerable challenges for RL approaches. The key difficulty in those domains is that a positive reward signal becomes em exponentially rare as the minimal solution length increases. So, an RL approach loses its training signal. There has been promising recent progress by using a curriculum-driven learning approach that is designed to solve a single hard instance. We present a novel em automated curriculum approach that dynamically selects from a pool of unlabeled training instances of varying task complexity guided by our em difficulty quantum momentum strategy. We show how the smoothness of the task hardness impacts the final learning results. In particular, as the size of the instance pool increases, the ``hardness gap'' decreases, which facilitates a smoother automated curriculum based learning process. Our automated curriculum approach dramatically improves upon the previous approaches. We show our results on Sokoban, which is a traditional PSPACE-complete planning problem and presents a great challenge even for specialized solvers. Our RL agent can solve hard instances that are far out of reach for any previous state-of-the-art Sokoban solver. In particular, our approach can uncover plans that require hundreds of steps, while the best previous search methods would take many years of computing time to solve such instances. In addition, we show that we can further boost the RL performance with an intricate coupling of our automated curriculum approach with a curiosity-driven search strategy and a graph neural net representation.