Thinking Fast and Slow with Deep Learning and Tree Search

By Thomas W. Anthony, Zheng Tian, David Barber. 2017

481 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Economics and Econometrics, Natural Language Processing, Prompting & Reasoning

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 Economics and Econometrics

In Natural Language Processing

In Prompting & Reasoning

Citations in the corpus

Recursively Summarizing Books with Human Feedback (2021, methodology): “Could other methods for optimizing against human feedback, such as expert iteration (Anthony et al., 2017), be more efﬁcient?”
Scalable agent alignment via reward modeling: a research direction (2018, background): “• Training a new model to predict answers to questions without having to expand the subquestions, akin to using a value network to the estimate the result of a tree search (Anthony et al., 2017; Silver et al., 2017).”
Supervising strong learners by amplifying weak experts (2018, methodology): “Expert Iteration: our method is very similar to Expert Iteration (ExIt) (Anthony et al., 2017) and AlphaZero (Silver et al., 2017b,a) and has recently achieved strong performance in the board games Hex, Go, Chess, and Shogi.”
Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (2017, methodology): “Machine Learning, 40(3):243–263, 2000.”
STaR: Bootstrapping Reasoning With Reasoning (2022, methodology): “There are further similarities between STaR and expert iteration methods [21].”
TALM: Tool Augmented Language Models (2022, background): “Iterative self-play is related to expert iteration [Anthony et al., 2017], which has been demonstrated to work well in tasks with extremely weak supervision [Christiano et al., 2018].”
Dota 2 with Large Scale Deep Reinforcement Learning (2019, methodology): “Building upon this work, AlphaGoZero, AlphaZero, and ExIt discard imitation learning in favor of using Monte-Carlo Tree Search during training to obtain higher quality trajectories [12, 37, 38] and apply this to Go, Chess, Shogi, and Hex.”
Adaptive Online Planning for Continual Lifelong Learning (2019, background): “Algorithms that combine planning with learning have been studied in both discrete and continuous domains [1, 6].”
Dual Policy Iteration (2018, methodology): “Note that in practice MBOC solver (e.g., a second order optimization method, as we will show in our practical algorithm below) could be computationally expensive and slow (e.g. tree search in ExIt and AlphaGo-Zero), but once ˆ P is provided, MBOC does not require additional samples from the real sys”
Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control (2018, background): “Planning and learning: Combining elements of planning and search with approximate value functions has been explored in discrete game domains [30, 31] where an MCTS planner is informed by the value function.”
Learning to Search with MCTSnets (2018, methodology): “Although we have focused on a supervised learning setup, our approach could easily be extended to a reinforcement learning setup by leveraging policy iteration with MCTS (Silver et al., 2017a; Anthony et al., 2017).”
Autoformalization with Large Language Models (2022, methodology): “In this section, we combine autoformalization with expert iteration algorithms [3], and achieve a new state of the art in miniF2F benchmark.”
Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Models (2023, background): “• Expert Iteration (ExiT) (Anthony et al., 2017) alternates between two steps: expert improvement and policy distillation.”
Diffusion Model Alignment Using Direct Preference Optimization (2023, background): “Alternative approaches sample base model answers and select based on predicted rewards [4, 6, 16] to use for supervised training [3, 18, 53].”
Scaling Scaling Laws with Board Games (2021, background): “In fact, despite sustained attention from games researchers [19]–[21], computers only surpassed human-level play at large board sizes in 2020 [22].”
Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking (2024, background): “Another direction for teaching reasoning relies on a language model’s own generated reasoning, which can be seen as building on a large body of literature on self-play (Silver et al., 2017; Anthony et al., 2017; Polu & Sutskever, 2020).”
Solving math word problems with process- and outcome-based feedback (2022, unknown): “…RL. Conversely, supervised imitation of reasoning traces ﬁltered by outcomes (e.g., traces which led to highly-rated user interactions) blurs together with RL approaches based on supervised learning of high-return trajectories (Silver et al., 2017; Anthony et al., 2017; Abdolmaleki et al., 2018).”
Contrastive Distillation Is a Sample-Efficient Self-Supervised Loss Policy for Transfer Learning (2022, unknown): “Expert iteration was originally proposed for well-deﬁned games like Hex (Anthony et al., 2017; Silver et al., 2017) and consists of alternating epochs of rolling out trajectories using an expensive expert model such as MCTS biased by an apprentice model, followed by ﬁne-tuning the apprentice model o”