# Subgoal Search For Complex Reasoning Tasks (@ NeurIPS 2021)

### Konrad Czechowski, Tomasz Odrzygóźdź, Marek Zbysiński, Michał Zawalski, Krzysztof Olejnik, Yuhuai Wu, Łukasz Kuciński, Piotr Miłoś

This paper shows one way to do this in three search problems, in a really appealing framework: they simply train a deep generative model to generate sub-goals that are trained to be approximately $k$-steps ahead of the current state, and that should be on the path to the solution. They train this generator from expert trajectories, which are available in the 3 problems they choose (Rubik's Cube, where they train by generating solutions in reverse, Sokoban and INT). At test time, the execution is straightforward: you first query the generator to generate a candidate set of sub-goals, which shouldn't be far from the current state. You then run a standard search algorithm to try to reach one of those subgoal states. You repeat until you get to an actual goal state.