Subgoal Search For Complex Reasoning Tasks (2021-08-25T00:00:00.000000Z)

TL;DR

It is shown that a simple approach of generating $k$-th step ahead subgoals is surprisingly efficient on three challenging domains: two popular puzzle games, Sokoban and the Rubik's Cube, and an inequality proving benchmark INT.

Abstract

Humans excel in solving complex reasoning tasks through a mental process of moving from one idea to a related one. Inspired by this, we propose Subgoal Search (kSubS) method. Its key component is a learned subgoal generator that produces a diversity of subgoals that are both achievable and closer to the solution. Using subgoals reduces the search space and induces a high-level search graph suitable for efficient planning. In this paper, we implement kSubS using a transformer-based subgoal module coupled with the classical best-first search framework. We show that a simple approach of generating $k$-th step ahead subgoals is surprisingly efficient on three challenging domains: two popular puzzle games, Sokoban and the Rubik's Cube, and an inequality proving benchmark INT. kSubS achieves strong results including state-of-the-art on INT within a modest computational budget.

Authors

Yuhuai Wu

7 papers

K. Czechowski

3 papers

Lukasz Kuci'nski

2 papers

TL;DR

Abstract

Authors

References77 items

Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning

Goal-Conditioned Reinforcement Learning with Imagined Subgoals

Discovery of Options via Meta-Learned Subgoals

World Model as a Graph: Learning Latent Landmarks for Planning

On the role of planning in model-based deep reinforcement learning

Generative Language Modeling for Automated Theorem Proving

INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving

Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning

Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors

Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning

Hallucinative Topological Memory for Zero-Shot Visual Planning

Multilingual Denoising Pre-training for Neural Machine Translation

Planning with Goal-Conditioned Policies

Learning from Trajectories via Subgoal Discovery

Grandmaster level in StarCraft II using multi-agent reinforcement learning

Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulation

Variational Temporal Abstraction

Uncertainty-sensitive Learning and Planning with Ensembles

Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generation

Subgoal-Based Temporal Abstraction in Monte-Carlo Tree Search

Solving the Rubik’s cube with deep reinforcement learning and search

Keyframing the Future: Keyframe Discovery for Visual Prediction and Planning

An investigation of model-free planning

A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play

Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

Learning over Subgoals for Efficient Navigation of Structured, Unknown Environments

Time-Agnostic Prediction: Predicting Predictable Video Frames

Learning Plannable Representations with Causal InfoGAN

Semi-parametric Topological Memory for Navigation

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

Mastering the game of Go without human knowledge

Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigation

Purely Declarative Action Descriptions are Overrated: Classical Planning with Simulators

Imagination-Augmented Agents for Deep Reinforcement Learning

Neuroscience-Inspired Artificial Intelligence

Hindsight Experience Replay

Attention is All you Need

Automatic Goal Generation for Reinforcement Learning Agents

Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary

FeUdal Networks for Hierarchical Reinforcement Learning

Mastering the game of Go with deep neural networks and tree search

Width and Serialization of Classical Planning Problems

A Survey of Monte Carlo Tree Search Methods

The first learning track of the international planning competition

Horde: a scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction

Double Q-learning

Automated Theorem Proving in Software Engineering

SOKOBAN and other motion planning problems

Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning

Feudal Reinforcement Learning

Using Patterns and Plans in Chess

Proceedings of the 2nd Annual Conference on Learning for Dynamics and Control, L4DC 2020, Online Event, Berkeley, CA, USA, 11-12 June 2020

Information Processing Systems 2017, 4-9 December 2017

George Van Den Driessche, Thore Graepel, and Demis Hassabis

God’s number is 26 in the quarter-turn metric

Artificial intelligence: A modern approach

THE IMPORTANCE OF MATHEMATICS

Involvement of basal ganglia and orbitofrontal cortex in goal-directed behavior.

Learning to Achieve Goals

Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes

data, models) or curating/releasing new assets

Did you discuss any potential negative societal impacts of your work?

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation

Did you discuss whether and how consent was obtained from people whose data you're using/curating?

Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times

Have you read the ethics review guidelines and ensured that your paper conforms to them

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable?

If your work uses existing assets, did you cite the creators? [Yes] For one of domains we generate expert data with implementation of MCTS agent

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix sections B, D and C

We trained and evaluated Sokoban on CPU only mostly because of rather small neural network sizes. Training time varied from 2 to 3 days, whereas evaluation took only an hour

D.2 Sokoban For training of the convolutional networks in Sokoban we set the learning rate to 10 − 4 and the number of epochs to 200. 22

b ))+a) 2 )+(c+

Did you state the full set of assumptions of all theoretical results

evaluations without GPU. We used 20 CPU cores with 20 GB memory, while still ﬁtting in a 3-day time. trained and evaluated Sokoban on CPU only mostly because of rather small neural network sizes

b ))+a)·(a+1))+(c+( 1 b )))