Learning to Search with MCTSnets

By Arthur Guez, Theophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, R´emi Munos, David Silver. 2018

96 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Reinforcement Learning, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

In Model Architectures

Citations in the corpus

Relational inductive biases, deep learning, and graph networks (2018, background): “, 2016), partial tree traversals in a state-action graph (Guez et al., 2018; Farquhar et al., 2018), hierarchical action policies (Andreas et al.”
Relational Deep Reinforcement Learning (2018, background): “, [32]), and hierarchical RL and planning [33, 34] to allow structured representations and reasoning to translate more fully into structured behaviors.”
Adaptive Online Planning for Continual Lifelong Learning (2019, background): “Recent work [14] generalizes the MCTS algorithm and proposes to learn the algorithm instead; having the algorithm set computation levels could be effective in our setting.”
Deep Multi-Agent Reinforcement Learning with Relevance Graphs (2018, methodology): “A recent study [5] incorporates a neural network inside the tree-search by expanding, evaluating and backing-up a vector embedding of the states.”
Deep reinforcement learning with relational inductive biases (2018, methodology): “Our approach may also interface well with approaches for hierarchical RL (Vezhnevets et al., 2017), planning (Guez et al., 2018), and structured behavior representation (Huang et al., 2018), so that the structured internal representations and patterns of reasoning can translate into more structured…”
Differentiable SLAM-net: Learning Particle SLAM for Visual Navigation (2021, background): “Differentiable algorithms are emerging for a wide range of learning domains, including state estimation [24; 31; 34; 42], visual mapping [23; 36], planning [55; 33; 18; 49; 22; 62] and control tasks [2; 50; 17; 6].”
The Barbados 2018 List of Open Issues in Continual Learning (2018, background): “New planning algorithms may be necessary that yield meaningful results when used with inaccurate or partial, or even abstract, learned models [4, 15].”
An investigation of model-free planning (2019, methodology): “For example the neural network may be designed to represent search trees (Farquhar et al., 2017; Oh et al., 2017; Guez et al., 2018), forward simulations (Racanière et al., 2017; Silver et al., 2016), or dynamic programming (Tamar et al., 2016).”
Small Sample Learning in Big Data Era (2018, background): “…et al., 2016; Xu et al., 2018), learning to transfer (Ying et al., 2018), learning to optimize (Li and Malik, 2017; Nir et al., 2018), learning to infer (Hu et al., 2017a; Marino et al., 2018), learning to search (Guez et al., 2018; Balcan et al., 2018), learning to control (Duan, 2017) and so on.”