PaperlayerView exact revision on arXiv

Source-linked AI summary

Thinking Fast and Slow with Deep Learning and Tree Search

Thomas Anthony, Zheng Tian, David Barber

arXiv:1705.08439v4cs.AIcs.LG

TL;DR

Sequential decision problems require both planning and generalisation, while standard deep RL uses a neural network for both plan discovery and generalisation. Expert Iteration separates these roles with tree search and a neural-network apprentice, and on Hex it outperformed REINFORCE and defeated MoHex 1.0 after tabula-rasa training.

  • Problem

    Sequential decision problems require combining planning with generalisation, whereas standard deep RL networks select actions without lookahead and must also discover strong policies.

  • Method

    Expert Iteration uses tree search to plan and a deep neural network to generalise those plans and guide subsequent search.

  • Results

    Expert Iteration significantly outperformed a REINFORCE variant on Hex, and its tabula-rasa tree-search agent defeated MoHex 1.0.

  • Takeaways & Limitations

    Separating planning from generalisation yielded faster learning and state-of-the-art final performance for the challenging Hex task.

Abstract

from arXiv · show

Sequential decision making problems, such as structured prediction, robotic control, and game playing, require a combination of planning policies and generalisation of those plans. In this paper, we present Expert Iteration (ExIt), a novel reinforcement learning algorithm which decomposes the problem into separate planning and generalisation tasks. Planning new policies is performed by tree search, while a deep neural network generalises those plans. Subsequently, tree search is improved by using the neural network policy to guide search, increasing the strength of new plans. In contrast, standard deep Reinforcement Learning algorithms rely on a neural network not only to generalise plans, but to discover them too. We show that ExIt outperforms REINFORCE for training a neural network to play the board game Hex, and our final tree search agent, trained tabula rasa, defeats MoHex 1.0, the most recent Olympiad Champion player to be publicly released.

1 Introduction

The paper motivates Expert Iteration (EXIT) as a two-process approach: tree search plans, while a neural network generalises those plans and then guides later search.

  • Dual-process theory distinguishes fast, unconscious, automatic System 1 thinking from slow, conscious, explicit, rule-based System 2 reasoning.
  • Humans combine strong intuitions with analytic reasoning, forming a learning loop in which study improves intuitions and intuitions guide analysis.
  • EXIT uses tree search as a System 2 analogue to assist neural-network training, then uses the network’s fast intuitions to guide search.
  • At a low level, EXIT repeatedly applies imitation learning while improving the comparatively slow expert using the fast apprentice policy.
  • The apprentice can bias search direction, estimate encountered-state values, or provide both forms of assistance.

2 Preliminaries

The preliminaries define sequential decision making in MDPs and introduce imitation learning, where an apprentice learns to mimic an expert’s policy or value-related targets.

  • An MDP agent observes state s_t, chooses action a_t, and seeks to maximise episodic reward R observed in terminal state s_T.
  • A policy π(a|s) is a distribution over actions available in state s; V^π(s) is its mean future reward, while Q^π(s,a) is the expected reward after taking action a.
  • Imitation learning solves an MDP by mimicking a provided expert policy, producing an apprentice policy through that mimicry.
  • Expert targets may specify an optimal move or estimate action values, with action-value prediction providing a cost-sensitive alternative to direct action prediction.

3 Expert iteration

Expert Iteration alternates self-play data generation, expert-derived imitation targets, apprentice training, and expert improvement, using neural networks to generalise tree-search plans.

  • EXIT extends imitation learning with expert improvement, enabling fast imitation-learning convergence when no strong initial player is known.
  • Expert Iteration algorithm: At each iteration, apprentice self-play supplies states, the expert computes imitation targets, and a new apprentice is trained before updating the expert.
  • Choice of expert and apprentice: The expert uses tree search to find strong move sequences, while the apprentice generalises discovered policies across the state space and rapidly bootstraps future searches.
  • Choice of expert and apprentice: A deep neural network is the canonical apprentice because it generalises across large state spaces and can be evaluated rapidly on a GPU.
  • Distributed Expert Iteration: EXIT spends most runtime creating expert-move datasets because tree search is orders of magnitude slower than neural-network evaluation; these datasets are embarrassingly parallel.
  • Online expert iteration: Restarting imitation learning from scratch discards prior datasets and can substantially increase runtime, while online EXIT aggregates datasets across iterations.
  • Online expert iteration: Dataset aggregation lets online EXIT request fewer expert moves per iteration while maintaining a large dataset, enabling earlier generalisation and expert improvement.

4 Imitation Learning in the game Hex

This section develops imitation learning for Hex by training neural-network apprentices to imitate MCTS experts, using tree-policy targets and dataset aggregation. TPT achieves stronger play than CAT despite similar move-prediction errors, and DAGGER further improves the apprentice.

  • Imitation-learning setup: The Hex implementation trains a convolutional neural network to imitate an MCTS expert.The datasets are designed to reduce state correlations and match the apprentice’s test-time distribution.
  • Learning targets: Chosen-action targets train on the single move selected by MCTS, whereas tree-policy targets match the root action distribution n(s, a)/n(s).The selected move is a∗ = argmax_a n(s, a).
  • Learning targets: TPT is cost-sensitive: it penalises errors less when MCTS considers actions similarly strong, prioritising accuracy on critical decisions.This also preserves evaluations of alternative actions that future searches may use.
  • Results: 47.0% and 47.7% top-1 prediction errors were obtained by CAT and TPT, respectively, on the initial 100,000-move dataset.Their top-3 errors were 65.4% and 65.7%, respectively.
  • Results: 50 ± 13 Elo separates TPT from CAT despite their similar prediction errors.This suggests that TPT’s cost-awareness improves playing performance rather than merely move classification.
  • Results: 120 Elo improvement followed three additional 100,000-move DAGGER batches, and the final TPT network won 87/162 games against its MCTS teacher.The final apprentice therefore achieved similar performance to the MCTS it was trained to emulate.

5 Expert Improvement in Hex

This section improves MCTS by using an apprentice policy to guide search and by considering value-network estimates. Policy-guided N-MCTS substantially outperforms baseline MCTS, although neural evaluations slow search.

  • Policy-guided search: Neural-MCTS uses an apprentice network to improve the quality of tree search after imitation learning.The network provides fast action evaluations, while search can discover improvements through lookahead.
  • Policy-guided search: The policy network biases MCTS toward promising moves by adding a bonus proportional to the apprentice probability π̂(a|s) to UCT.The network policy is evaluated and stored whenever a node is expanded.
  • Policy-guided search: The network temperature is tuned because the optimal UCT bonus need not be linear in the TPT policy probability.The search-weight parameter w_a controls the balance between neural guidance and simulations.
  • Results: 97% of games were won by policy-network N-MCTS against baseline MCTS.Neural evaluations caused a two-times slowdown, while doubling vanilla MCTS iterations achieved a 56% win rate.
  • Value guidance: Value networks can reduce required search depth, but this implementation’s imitation procedure learns a policy rather than a value function.The paper therefore approximates the expert value with the apprentice value because sufficiently large independent expert datasets exceed available resources.
  • Value guidance: A multitask network combines policy and value heads by summing the TPT and value losses, and mixes network and rollout estimates during backup.At expanded leaves, value predictions are backed up through the tree alongside rollout results.

6 Experiments

Experiments evaluate EXIT against REINFORCE and MOHEX in Hex, including batch versus online training and policy-only versus value-and-policy variants. EXIT learns stronger policies faster, value estimation improves expert play, and EXIT defeats MOHEX under several comparisons.

  • 6.1 Comparison of Batch and Online EXIT to REINFORCE: EXIT learns stronger policies faster than REINFORCE, with consistent improvement and little variation across training runs.The authors attribute the absence of opponent overfitting to tree search considering multiple possible responses.
  • 6.1 Comparison of Batch and Online EXIT to REINFORCE: Online EXIT substantially outperforms batch EXIT, while the exponential-dataset variant appears marginally stronger than the buffer variant.The comparison suggests that retaining a larger dataset is useful.
  • 6.2 Comparison of Value and Policy EXIT: Value-and-policy EXIT significantly outperforms policy-only EXIT after training on approximately 550,000 positions and generating approximately 7,400,000 additional move choices.Improved plans from the better expert quickly appear in a stronger apprentice.
  • 6.2 Comparison of Value and Policy EXIT: Later apprentices comfortably outperform experts from earlier training, demonstrating the importance of expert improvement.The experiment uses asynchronous distributed online EXIT and compares policy-only and value-and-policy training.
  • 6.3 Performance Against MOHEX: Fair equal-wall-clock comparison with MOHEX is difficult because hardware bottlenecks differ, and MOHEX was approximately 50% faster on the authors’ machine.MOHEX relies heavily on the CPU, whereas EXIT’s experts are GPU-bottlenecked.
  • 6.3 Performance Against MOHEX: EXIT won 75.3% against 10,000-iteration MOHEX, 59.3% against 100,000-iteration MOHEX, and 55.6% against four-second-per-move MOHEX.The latter MOHEX settings were over six times slower than the EXIT searcher.

7 Related work

EXIT extends imitation learning with iterative expert improvement, allowing the apprentice and expert to strengthen one another. Unlike related approaches, it does not require a satisfactory initial expert or domain-specific heuristics.

  • Connections to existing RL algorithms: EXIT can recover a form of Policy Iteration when Monte Carlo Search is used as its expert, while Monte Carlo Tree Search gives stronger plans.The choice of expert class determines the resulting connection to existing reinforcement-learning algorithms.
  • Previous imitation-learning approaches: Earlier imitation-learning and reinforcement-learning hybrids cannot improve the original expert policy, whereas EXIT creates stronger experts throughout training.Those earlier approaches remain useful when strong experts exist, but only at the beginning of training.
  • AlphaGo Zero: AlphaGo Zero independently developed an EXIT-like algorithm and achieved state-of-the-art performance in Go.The paper reports a detailed comparison of the two closely related works in its appendix.
  • EXIT’s distinction from standard imitation learning: EXIT applies to reinforcement learning without assuming a satisfactory expert or requiring domain-specific heuristics.The Hex experiment uses a general-purpose search algorithm as the expert and learns tabula rasa.

8 Conclusion

The paper concludes that EXIT separates planning from generalisation: MCTS finds stronger plans case by case, and neural networks generalise them. In Hex, EXIT learns faster than REINFORCE and defeats MOHEX 1.0 despite tabula-rasa training.

  • Conclusion: EXIT separates reinforcement-learning planning and generalisation, using MCTS for case-by-case planning and neural networks to generalise stronger policies.The authors motivate the algorithm through dual-process theory and associate the separation with long-term planning.
  • Conclusion: EXIT enables long-term planning and is reported to produce faster learning and state-of-the-art final performance on challenging problems.This is the authors’ stated conclusion about the algorithm’s supported scope.
  • Conclusion: EXIT significantly outperforms a REINFORCE variant in learning Hex and its resulting tree-search agent beats MOHEX 1.0 after tabula-rasa training.The result indicates competitiveness with state-of-the-art heuristic search methods.
  • Conclusion: The reported MOHEX comparison depends on hardware-specific runtime differences, with MOHEX approximately 50% faster on the authors’ machine.The machine used an Intel Xeon E5-1620 and an Nvidia Titan X (Maxwell).

A Comparison to AlphaGo Zero

The paper compares its EXIT implementation with AlphaGo Zero across training targets, losses, architectures, search procedures, warm starts, and data-generation details. It also describes asynchronous neural-network evaluation and a synchronous alternative suited to EXIT’s large position datasets.

  • Training targets and datasets: Both implementations train apprentice policies with tree-policy targets, but AlphaGo Zero uses expert Monte Carlo values while EXIT uses apprentice estimates for value training.The authors note that AlphaGo Zero used approximately 100,000 times more training computation.
  • Training targets and datasets: EXIT uses KL loss for policy and value, early stopping instead of L2 regularisation, and reinitialised network weights at each iteration.AlphaGo Zero instead uses mean-square error for value prediction and L2 regularisation.
  • Network architecture: AlphaGo Zero uses a substantially larger 79-layer residual network, whereas EXIT uses a more standard CNN and reports improved imitation-learning performance for the larger architecture.The comparison concerns architecture and imitation-learning performance, not the Hex outcome directly.
  • Search and initialization: EXIT uses RAVE, rollouts, and warm starts from vanilla MCTS to policy-only and then value-and-policy networks; these warm starts save computation early in training.The authors state that warm starts are not essential for learning Hex.
  • Search and initialization: Unlike AlphaGo Zero, EXIT does not verify that each new expert defeats the previous one because such tests would be prohibitively expensive for its training times.The authors did not find verification necessary.
  • Neural-network evaluation: Asynchronous neural-network batching improves GPU throughput and prevents CPU idle time, but can place suboptimal moves in the tree before evaluations return.This is the standard implementation trade-off described for N-MCTS.
  • Neural-network evaluation: EXIT avoids asynchronous N-MCTS by searching many positions concurrently, allowing CPU threads to suspend one search while submitting another neural-network evaluation.The method is designed for large datasets of N-MCTS moves and batches multiple positions simultaneously.

C Monte Carlo Tree Search Parameters and Rapid Action Value Estimation (RAVE)

RAVE accelerates early action-value estimation by reusing rollout information across actions, while policy and value networks are incorporated into the tree policy to guide search.

  • Rapid Action Value Estimation (RAVE): RAVE estimates move values faster than UCT alone, reducing the sampling burden of Monte Carlo value estimates when many actions are available.It exploits the tendency for moves strong later to have been strong earlier.
  • Rapid Action Value Estimation (RAVE): RAVE updates statistics for every later action as if that action had been selected first, implementing the all-moves-as-first heuristic.This heuristic applies where actions can often be transposed.
  • Monte Carlo Tree Search: UCT_RAVE combines standard UCT with RAVE estimates, with β(s, a) decreasing RAVE’s weight as normal-sample counts increase.c_RAVE controls how quickly RAVE values are down-weighted.
  • Monte Carlo Tree Search: Policy-network guidance is incorporated into the tree policy alongside RAVE estimates, using the network policy π̂(a|s, τ) and visit counts n(s, a).The supplied parameters table distinguishes vanilla MCTS from network-guided N-MCTS configurations.
  • Monte Carlo Tree Search: When value estimates are used, Q̂(s, a) denotes the backed-up average of network value estimates at edge (s, a).This provides the network-value quantity used in the search formulae.

D Neural Network Architecture

The Hex neural network uses a six-channel board encoding and a convolutional architecture with separate move-policy outputs for each player and optional value outputs.

  • Input Features: The 9 × 9 Hex board is represented through six channels encoding stones and their connections to the board edges.The channels distinguish black and white stones and their respective connected edges.
  • Input Features: Board padding adds dummy edge stones without changing the game, giving edge-centered convolutions more meaningful input than zero-padding.Black dummy stones mark north and south; white dummy stones mark east and west, with both colors in corners.
  • Neural Network Architecture: The network contains 13 convolution layers followed by two parallel fully connected softmax output layers.The parallel outputs represent move probabilities for black-to-move and white-to-move positions.
  • Neural Network Architecture: A move mask removes occupied cells before softmax, ensuring the policy outputs only valid moves.The two policy heads correspond to the player whose turn it is.
  • Neural Network Architecture: Optional state-value prediction adds two sigmoid scalar outputs estimating winning probability for the player next to move.The value outputs complement the move-policy outputs during search.
  • Neural Network Architecture: Hexagonal 3 × 3 filters cover each cell and its six adjacent cells, matching the board’s hexagonal topology.Most convolution layers use 64 such filters with stride 1, while later layers include unpadded or 1 × 1 convolutions.

E Matches between EXIT and MOHEX

EXIT is reported as stronger than MOHEX 1.0, while the comparison is bounded by unavailable newer MOHEX versions and differences in tournament configurations.

  • Results: EXIT is clearly stronger than MOHEX 1.0 in the reported matches.The paper therefore describes EXIT as competitive with state-of-the-art scalable heuristic search methods.
  • Limitations: The comparison does not establish whether EXIT exceeds newer state-of-the-art methods, especially on larger 11 × 11 or 13 × 13 boards.MOHEX 2.0 is described as approximately 250 Elo stronger than MOHEX 1.0 on 11 × 11, but was unavailable for direct comparison.
  • Match Results: EXIT won 59.3% of 162 games against MOHEX9 while using 10,000 iterations per move versus MOHEX’s 100,000.The match included one game as black per legal opening move.
  • Match Results: The displayed games were selected from relatively even openings to illustrate comparative strengths and weaknesses rather than large opening advantages.The selection criterion was intended to avoid giving either player a large initial advantage.
Loading 1705.08439v4…