# Solving Sokoban with forward-backward reinforcement learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 5 May 2021.

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

- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)
- [Recall Traces: Backtracking Models for Efficient Reinforcement Learning](https://mlsanity.com/paper/1804.00379/) (2018)
- [Forward-Backward Reinforcement Learning](https://mlsanity.com/paper/1803.10227/) (2018)
- [Solving Hard AI Planning Instances Using Curriculum-Driven Deep Reinforcement Learning](https://mlsanity.com/paper/2006.02689/) (2020)

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

- [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)
- [ChemGymRL: An Interactive Framework for Reinforcement Learning for Digital Chemistry](https://mlsanity.com/paper/2305.14177/) (2023)
- [Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents](https://mlsanity.com/paper/2509.01022/) (2025)
- [Keke AI Competition: Solving puzzle levels in a dynamically changing mechanic space](https://mlsanity.com/paper/2209.04911/) (2022)

## Abstract (arXiv)

Despite seminal advances in reinforcement learning in recent years, many domains where the rewards are sparse, e.g. given only at task completion, remain quite challenging. In such cases, it can be beneficial to tackle the task both from its beginning and end, and make the two ends meet. Existing approaches that do so, however, are not effective in the common scenario where the strategy needed near the end goal is very different from the one that is effective earlier on. In this work we propose a novel RL approach for such settings. In short, we first train a backward-looking agent with a simple relaxed goal, and then augment the state representation of the forward-looking agent with straightforward hint features. This allows the learned forward agent to leverage information from backward plans, without mimicking their policy. We demonstrate the efficacy of our approach on the challenging game of Sokoban, where we substantially surpass learned solvers that generalize across levels, and are competitive with SOTA performance of the best highly-crafted systems. Impressively, we achieve these results while learning from a small number of practice levels and using simple RL techniques.