Timezone: »

 
Poster
Single-Agent Policy Tree Search With Guarantees
Laurent Orseau · Levi Lelis · Tor Lattimore · Theophane Weber

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #168
in Wed Poster Session B »

We introduce two novel tree search algorithms that use a policy to guide search. The first algorithm is a best-first enumeration that uses a cost function that allows us to provide an upper bound on the number of nodes to be expanded before reaching a goal state. We show that this best-first algorithm is particularly well suited for ``needle-in-a-haystack'' problems. The second algorithm, which is based on sampling, provides an upper bound on the expected number of nodes to be expanded before reaching a set of goal states. We show that this algorithm is better suited for problems where many paths lead to a goal. We validate these tree search algorithms on 1,000 computer-generated levels of Sokoban, where the policy used to guide search comes from a neural network trained using A3C. Our results show that the policy tree search algorithms we introduce are competitive with a state-of-the-art domain-independent planner that uses heuristic search.

Keywords: Game Playing · Planning · CNN Architectures
[ Paper] 

Author Information

Laurent Orseau (DeepMind)
Levi Lelis (Universidade Federal de Viçosa)
Tor Lattimore (DeepMind)
Theophane Weber (DeepMind)

More from the Same Authors