Thinking Fast and Slow with Deep Learning and Tree Search

1 Thinking fast and Slowwith deep Learning and tree SearchThomas Anthony1, ,Zheng Tian1, andDavid Barber1,21 University College London2 Alan Turing Institute decision making problems, such as structured prediction, robotic control,and game playing, require a combination of planning policies and generalisation ofthose plans. In this paper, we present Expert Iteration (EXIT), a novel reinforcementlearning algorithm which decomposes the problem into separate planning andgeneralisation tasks. Planning new policies is performed by tree Search , while adeep neural network generalises those plans. Subsequently, tree Search is improvedby using the neural network policy to guide Search , increasing the strength of newplans.

2 In contrast, standard deep Reinforcement Learning algorithms rely on aneural network not only to generalise plans, but to discover them too. We show thatEXIT outperformsREINFORCEfor training a neural network to play the boardgame Hex, and our final tree Search agent, trained tabula rasa, ,the most recent Olympiad Champion player to be publicly IntroductionAccording to dual-process theory [1,2], human reasoning consists of two different kinds of 1is a fast , unconscious and automatic mode of thought, also known 2, an evolutionarily recent process unique to humans, is a slow , conscious, explicitand rule-based mode Learning to complete a challenging planning task, such as playing a board game, humans exploitboth processes.

3 Strong intuitions allow for more effective analytic reasoning by rapidly selectinginteresting lines of play for consideration. Repeated deep study gradually improves intuitions feedback to stronger analysis, creating a closed Learning loop. In other words,humans learn bythinking fast and deep Reinforcement Learning (RL) algorithms such asREINFORCE[3] and DQN [4], neuralnetworks make action selections with no lookahead; this is analogous to System 1. Unlike humanintuition, their training does not benefit from a System 2 to suggest strong policies. In this paper,we present Expert Iteration (EXIT), which uses a tree Search as an analogue of System 2; this assiststhe training of the neural network.

4 In turn, the neural network is used to improve the performance ofthe tree Search by providing fast intuitions to guide a low level,EXITcan be viewed as an extension of Imitation Learning (IL) methods to domainswhere the best known experts are unable to achieve satisfactory performance. In IL anapprenticeis trained to imitate the behaviour of anexpertpolicy. WithinEXIT, we iteratively re-solve the ILproblem. Between each iteration, we perform an expert improvement step, where we bootstrap the( fast ) apprentice policy to increase the performance of the (comparatively slow ) Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, [ ] 3 Dec 2017 Typically, the apprentice is implemented as a deep neural network, and the expert by a tree searchalgorithm.

5 Expert improvement can be achieved either by using the apprentice as an initial bias in thesearch direction, or to assist in quickly estimating the value of states encountered in the Search tree ,or proceed as follows: in section 2, we cover some preliminaries. Section 3 describes the generalform of the Expert Iteration algorithm, and discusses the roles performed by expert and 4 and 5 dive into the implementation details of the Imitation Learning and expert improve-ment steps ofEXITfor the board game Hex. The performance of the resultantEXIT algorithm isreported in section 6. Sections 7 and 8 discuss our findings and relate the algorithm to Markov Decision ProcessesWe consider sequential decision making in a Markov Decision Process (MDP).

6 At each timestept, an agent observes a statestand chooses an actionatto take. In a terminal statesT, an episodicrewardRis observed, which we intend to can easily extend to two-player, perfectinformation, zero-sum games by Learning policies for both players simultaneously, which aim tomaximise the reward for the respective call a distribution over the actionsaavailable in statesapolicy, and denote it (a|s). The valuefunctionV (s)is the mean reward from following starting in states. ByQ (s,a)we mean theexpected reward from taking actionain states, and following policy Imitation LearningIn Imitation Learning (IL), we attempt to solve the MDP by mimicking anexpertpolicy thathas been provided.

7 Experts can arise from observing humans completing a task, or, in the contextof structured prediction, calculated from labelled training data. The policy we learn through thismimicry is referred to as create a dataset of states of expert play, along with some target data drawn from the expert, whichwe attempt to predict. Several choices of target data have been used. The simplest approach is to askthe expert to name an optimal move (a|s)[5]. Once we can predict expert moves, we can takethe action we think the expert would have most probably taken. Another approach is to estimate theaction-value functionQ (s,a).

8 We can then predict that function, and act greedily with respectto it. In contrast to direct action prediction, this target is cost-sensitive, meaning the apprentice cantrade-off prediction errors against how costly they are [6].3 Expert iterationCompared to IL techniques, Expert Iteration (EXIT) is enriched by an expert improvement the expert player and then resolving the Imitation Learning problem allows us to exploitthe fast convergence properties of Imitation Learning even in contexts where no strong player wasoriginally known, including when Learning tabula rasa. Previously, to solve such problems, researchershave fallen back on RL algorithms that often suffer from slow convergence, and high variance, andcan struggle with local each iterationi, the algorithm proceeds as follows: we create a setSiof game states by selfplay of the apprentice i 1.

9 In each of these states, we use our expert to calculate an ImitationLearning target ats( the expert s action i 1(a|s)); the state-target pairs ( (s, i 1(a|s)))form our datasetDi. We train a new apprentice ionDi(Imitation Learning ). Then, we use ournew apprentice to update our expert i= (a|s; i)(expert improvement). See Algorithm 1 reward may be decomposed as a sum of intermediate rewards ( Tt=0rt)2 The expert policy is calculated using a tree Search algorithm. By using the apprentice policy todirect Search effort towards promising moves, or by evaluating states encountered during Search morequickly and accurately, we can help the expert find stronger policies.

10 In other words, we bootstrapthe knowledge acquired by Imitation Learning back into the planning Imitation Learning step is analogous to a human improving their intuition for the task by studyingexample problems, while the expert improvement step is analogous to a human using their improvedintuition to guide future 1 Expert Iteration1: 0= initial_policy()2: 0= build_expert( 0)3:fori = 1; i max_iterations; i++do4:Si= sample_self_play( i 1)5:Di={(s, imitation_learning_target( i 1(s)))|s Si}6: i= train_policy(Di)7: i= build_expert( i)8:end Choice of expert and apprenticeThe Learning rate ofEXITis controlled by two factors: the size of the performance gap between theapprentice policy and the improved expert, and how close the performance of the new apprenticeis to the performance of the expert it learns from.