Chapter 7: Monte Carlo Tree Search: Searching with Reinforcement Learning Principles
This introduction presents Monte Carlo tree search as a blend of simulation, planning, and learning for exploring sequential decisions under uncertainty.
After this chapter you will be able to
- MCTS synthesis of approaches. Explain how MCTS brings together ideas from simulation, Markov decision processes, planning, and learning.
- Simulated business decision planning. Describe how MCTS uses simulated outcomes to think ahead about tree-like business decisions under uncertainty.
- Tree structure and paths. Explain how nodes, edges, roots, and leaves organize a tree, and describe the path from the root to a node.
- Routing decisions as branches. Describe how a vehicle-routing tree represents nested decisions and outcomes, and why a decision map alone does not select the best plan.
- Breadth First Search Mechanics. Explain how BFS uses a queue to explore routes and what its shortest-path guarantee means.
- Depth First Search Backtracking. Explain how DFS uses a stack or recursion to explore a route and then return to alternatives.
- Search Tradeoffs and Scalability. Distinguish the practical tradeoffs of BFS and DFS for vehicle routing, and explain the motivation for using a sampling-based alternative.
- Selective Search Strategy. Explain why MCTS explores some branches more deeply than others and balances exploration with exploitation.
- UCB1 Tree Selection. Describe how selection uses UCB1 to choose a path and how its terms balance observed reward with exploration.
- Incremental Tree Expansion. Explain how MCTS expands the tree after selection and why it adds only one new child per iteration.
- Simulation Rollout Outcomes. Describe how a simulation estimates the promise of a newly expanded route and what policy it can use.
- Backpropagation and Search Feedback. Trace how a simulation result updates the tree and influences later searches.
- Final Visit Count Choice. Explain why MCTS commonly selects the action with the most visits rather than the highest average reward.
- Capacitated routing objective. Explain the CVRP objective, capacity constraints, and why searching for a solution is difficult.
- Routing states and actions. Describe how a partial routing solution is represented and how legal actions create child states.
- MCTS selection and updates. Trace how the solver selects and expands routing branches and propagates simulation results.
- Rollout evaluation and rewards. Explain how a greedy rollout evaluates a partial route and how its distance is converted into a comparable reward.
- Local route refinement. Explain how 2-opt improves routes and complements MCTS in this solver.
What it builds on
- Markov decision process (chapter 2) · States, actions, and values in Markov decision processes.
- Paradigms on solving Markov decision process (chapter 4) · Paradigms for solving sequential decision problems.
- Tradeoff between exploitation and exploration (chapter 5) · The exploration-exploitation tradeoff.
- Temporal difference learning (chapter 6) · Experience-driven temporal-difference learning.
Section by section
Introduction
This introduction presents Monte Carlo tree search as a blend of simulation, planning, and learning for exploring sequential decisions under uncertainty.
- MCTS synthesis of approaches: Explain how MCTS brings together ideas from simulation, Markov decision processes, planning, and learning.
Why it matters: This combination connects MCTS to several decision-making approaches you have already encountered. - Simulated business decision planning: Describe how MCTS uses simulated outcomes to think ahead about tree-like business decisions under uncertainty.
Why it matters: Simulating possible futures makes MCTS relevant to practical decisions such as vehicle routing.
Key terms: Monte Carlo Tree Search, Monte Carlo simulation, Markov decision processes, dynamic programming, temporal-difference learning, exploration, tree-like decisions, simulate outcomes, uncertainty, vehicle routing
7.1 Tree data structure and its applications in business
This section introduces tree structures as maps of branching business decisions and illustrates them with a vehicle-routing example.
- Tree structure and paths: Explain how nodes, edges, roots, and leaves organize a tree, and describe the path from the root to a node.
Why it matters: These relationships are the foundation for representing and exploring sequences of decisions. - Routing decisions as branches: Describe how a vehicle-routing tree represents nested decisions and outcomes, and why a decision map alone does not select the best plan.
Why it matters: A decision tree makes nested planning choices visible without pretending that drawing the tree automatically finds the best one. - Kinds of decision trees: Distinguish binary trees, decision trees, and game trees by their branching or what their nodes represent.
Why it matters: These distinctions show how the same tree structure can organize different kinds of choices. - RouteNode representation: Describe what the Python RouteNode class stores and how it supports a routing decision tree.
Why it matters: This representation turns the conceptual decision tree into a structure a program can build.
Key terms: node, parent–child relationships, root node, edge, leaf node, directed acyclic graph, decision tree, Depot, route, accumulated cost
7.2 Fundamental tree search algorithms
This section explains breadth-first and depth-first tree search through a vehicle-routing example and compares their guarantees and practical limitations.
- Vehicle Routing Search Tree: Describe how the delivery problem is represented as a decision tree and how route cost is measured.
Why it matters: This representation turns route planning into a search over possible sequences of stops. - Breadth First Search Mechanics: Explain how BFS uses a queue to explore routes and what its shortest-path guarantee means.
Why it matters: BFS's search order explains both what it finds first and when that result is cost-optimal. - Depth First Search Backtracking: Explain how DFS uses a stack or recursion to explore a route and then return to alternatives.
Why it matters: Backtracking lets DFS pursue complete routes while retaining a way to explore alternatives. - Search Tradeoffs and Scalability: Distinguish the practical tradeoffs of BFS and DFS for vehicle routing, and explain the motivation for using a sampling-based alternative.
Why it matters: These tradeoffs explain why exhaustive search becomes impractical and why more selective search is attractive.
Key terms: root node, child node, path, cost, Breadth-First Search, BFS, queue, FIFO, level, Depth-First Search
7.3 Monte Carlo tree search theory and algorithm
This section explains how Monte Carlo Tree Search selectively builds and evaluates a search tree through repeated four-phase cycles.
- Selective Search Strategy: Explain why MCTS explores some branches more deeply than others and balances exploration with exploitation.
Why it matters: Selective search makes large decision spaces more manageable without committing too early to one direction. - UCB1 Tree Selection: Describe how selection uses UCB1 to choose a path and how its terms balance observed reward with exploration.
Why it matters: UCB1 directs the search using both evidence of success and the need to investigate less-visited choices. - Incremental Tree Expansion: Explain how MCTS expands the tree after selection and why it adds only one new child per iteration.
Why it matters: Incremental expansion lets the search use evidence before spending effort on more alternatives. - Simulation Rollout Outcomes: Describe how a simulation estimates the promise of a newly expanded route and what policy it can use.
Why it matters: A rollout gives the search an outcome for a new branch before its remaining tree has been built. - Backpropagation and Search Feedback: Trace how a simulation result updates the tree and influences later searches.
Why it matters: Passing outcomes back through the tree lets later selections benefit from earlier simulations. - Final Visit Count Choice: Explain why MCTS commonly selects the action with the most visits rather than the highest average reward.
Why it matters: The final choice can avoid overvaluing a branch that looks good only because of a few noisy outcomes.
Key terms: Monte Carlo Tree Search, exploration, exploitation, BFS, DFS, Selection, UCB1, exploitation term, exploration term, visit count
7.4 Solving capacitated vehicle routing problem with Monte Carlo tree search
The section applies Monte Carlo tree search and local route improvement to a capacitated vehicle routing problem.
- Capacitated routing objective: Explain the CVRP objective, capacity constraints, and why searching for a solution is difficult.
Why it matters: The objective and constraints determine what counts as a useful routing solution. - Problem data and distances: Describe the instance data and explain why the implementation precomputes pairwise distances.
Why it matters: Organizing the input and distance calculations makes repeated route evaluation practical. - Routing states and actions: Describe how a partial routing solution is represented and how legal actions create child states.
Why it matters: The state and actions turn routing choices into branches that MCTS can explore safely. - MCTS selection and updates: Trace how the solver selects and expands routing branches and propagates simulation results.
Why it matters: This cycle directs limited computation toward promising routing choices while still exploring alternatives. - Rollout evaluation and rewards: Explain how a greedy rollout evaluates a partial route and how its distance is converted into a comparable reward.
Why it matters: Rollouts provide a practical signal about partial routes without needing to solve each continuation optimally. - Local route refinement: Explain how 2-opt improves routes and complements MCTS in this solver.
Why it matters: Local improvement can polish the routes discovered by the broader search.
Key terms: Capacitated Vehicle Routing Problem, capacity constraints, total distance, CVRPInstance, coords, demands, depot, Euclidean distance, CVRPState, routes
7.5 Summary
Concepts explained in this chapter
- Monte Carlo Tree SearchMonte Carlo tree search is a planning algorithm that incrementally builds a search tree by selecting nodes, expanding actions, simulating outcomes, and backpropagating outcome statistics.
- 2-opt2-opt is a routing improvement heuristic that replaces two route edges by reconnecting the resulting segments in the opposite order.
- capacitated vehicle routing problemThe capacitated vehicle routing problem is an optimization problem that assigns customer visits to vehicle routes while respecting vehicle capacities and minimizing total travel cost.
- capacity constraintA capacity constraint limits the total demand assigned to a vehicle route to the vehicle's carrying capacity.
- local searchLocal search is an optimization technique that iteratively improves a candidate solution by examining nearby solutions.
- search treeA search tree is a branching data structure whose nodes represent states or decision points and whose edges represent possible actions or outcomes.
- tree searchTree search is a planning technique that represents possible action sequences and outcomes as branches of a search tree and uses them to guide decisions.
- breadth-first searchBreadth-first search explores graph or tree nodes in order of their distance from a starting node, typically using a FIFO queue.
- depth-first searchDepth-first search explores a graph or tree by following one branch as far as possible before backtracking, typically using a stack or recursion.
- backpropagation phaseThe backpropagation phase of Monte Carlo tree search propagates a simulation outcome toward the root while updating node statistics.
- expansion phaseThe expansion phase is the Monte Carlo tree search step that adds a child node for an action not previously represented at the selected node.
- selection phaseThe selection phase is the Monte Carlo tree search step that follows a path from the root through already expanded nodes to a node eligible for expansion or termination.
- simulation phaseThe simulation phase is the Monte Carlo tree search step that rolls out actions from an expanded node to obtain an outcome estimate.
- upper confidence boundAn upper confidence bound method selects actions using an optimistic estimate that combines estimated reward with an uncertainty-based confidence bonus.
- treeA tree is a hierarchical data structure of nodes connected by parent–child relationships without cycles.
- queueA queue is a data structure that processes elements in first-in, first-out order.
- stackA stack is a data structure that processes elements in last-in, first-out order.
- binary treeA binary tree is a tree in which each node has at most two children.
- decision treeA decision tree is a tree-shaped model in which internal nodes represent tests or decisions and leaf nodes represent outcomes.
- game treeA game tree is a tree representing possible states and moves in a strategic game or other sequential decision process.
- nodeA node is an element in a tree or graph that represents a state, decision point, or piece of information.
- exploitationExploitation is choosing the action currently believed to produce the greatest reward based on available knowledge.
- explorationExploration is the selection of actions whose outcomes are uncertain in order to gather information about their payoffs.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
