Learning to Search with MCTSnets

Abstract

Planning problems are among the most important and well-studied problems in artificial intelligence. They are most typically solved by tree search algorithms that simulate ahead into the future, evaluate future states, and back-up those evaluations to the root of a search tree. Among these algorithms, Monte-Carlo tree search (MCTS) is one of the most general, powerful and widely used. A typical implementation of MCTS uses cleverly designed rules, optimized to the particular characteristics of the domain. These rules control where the simulation traverses, what to evaluate in the states that are reached, and how to back-up those evaluations. In this paper we instead learn where, what and how to search. Our architecture, which we call an MCTSnet, incorporates simulation-based search inside a neural network, by expanding, evaluating and backing-up a vector embedding. The parameters of the network are trained end-to-end using gradient-based optimisation. When applied to small searches in the well known planning problem Sokoban, the learned search algorithm significantly outperformed MCTS baselines.

arXiv commentICML 2018 (camera-ready version)

References in corpus (3)

• Thinking Fast and Slow with Deep Learning and Tree Search
• The Predictron: End-To-End Learning and Planning
• Learning model-based planning from scratch

Cited by in corpus (17)

• A Review of Tracking, Prediction and Decision Making Methods for Autonomous Driving
• Relational Deep Reinforcement Learning
• Deep Multi-Agent Reinforcement Learning with Relevance Graphs
• Particle Filter Networks with Application to Visual Localization
• On the Feasibility of Learning, Rather than Assuming, Human Biases for Reward Inference
• TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs
• Procedural Content Generation: Better Benchmarks for Transfer Reinforcement Learning
• Adaptive Online Planning for Continual Lifelong Learning
• Neural Packet Classification
• Integrating Algorithmic Planning and Deep Learning for Partially Observable Navigation
• The Barbados 2018 List of Open Issues in Continual Learning
• Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration
• A novel approach to model exploration for value function learning
• Amanuensis: The Programmer's Apprentice
• Biological Blueprints for Next Generation AI Systems
• An investigation of model-free planning
• Planning in Dynamic Environments with Conditional Autoregressive Models