Subgoal Search For Complex Reasoning Tasks

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.

NeurIPS 2021

References in corpus (13)

• HuggingFace's Transformers: State-of-the-art Natural Language Processing
• Learning Plannable Representations with Causal InfoGAN
• Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigation
• Generative Language Modeling for Automated Theorem Proving
• Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning
• Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulation
• Goal-Conditioned Reinforcement Learning with Imagined Subgoals
• Variational Temporal Abstraction
• On the role of planning in model-based deep reinforcement learning
• Keyframing the Future: Keyframe Discovery for Visual Prediction and Planning
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning
• Learning from Trajectories via Subgoal Discovery
• Uncertainty-sensitive Learning and Planning with Ensembles