liveBook · Manning

Monte Carlo Tree Search

As explained in Applied Reinforcement Learning

Monte Carlo tree search is a planning algorithm that incrementally builds a search tree by selecting nodes, expanding actions, simulating outcomes, and backpropagating outcome statistics.

A delivery company choosing routes faces a branching set of decisions: which customer to serve next, and when to use another vehicle. Monte Carlo Tree Search (MCTS) plans by sampling possible futures rather than examining every route. It builds a search tree incrementally, giving promising choices more attention while still testing less-explored alternatives. section 7.0 section 7.3

Each MCTS iteration repeats four phases:

  • Selection: follow existing children from the root, balancing their observed rewards against how little they have been explored. Stop at a node with an untried action or a terminal state. section 7.5
  • Expansion: if an untried action is available, add a child representing its resulting state. section 7.5
  • Simulation: complete a possible solution from that state using a rollout policy, such as a random or greedy policy, and evaluate the outcome. section 7.5
  • Backpropagation: pass the outcome up the path to the root, updating visit counts and accumulated rewards so later selections can use the experience. section 7.5
Figure 7.4 The four-phase cycle of Monte Carlo Tree Search.

Use the four-phase diagram to follow how one iteration grows the tree and updates its estimates. section 7.3

UCB1 is one way to select a child. It combines average reward with an exploration bonus that favors less-visited children; an exploration weight controls the balance. In the routing implementation, unvisited children receive priority. After searching, the implementation can choose the root action with the most visits. section 7.4

Capacitated vehicle routing

Represent a state by the routes built so far, the unvisited customers, and the current vehicle. An action adds an eligible customer or, when no customer can be added, moves to the next vehicle. Eligibility checks both whether the customer is unvisited and whether its demand fits the vehicle’s remaining capacity. The objective is to serve every customer exactly once while minimizing total fleet distance. One solver completes rollouts greedily using the nearest eligible customer, improves routes with 2-opt, and penalizes rollouts that cannot finish. Repeated simulations guide the search toward better route combinations. section 7.4

MCTS trades exhaustive coverage for selective sampling: it can spend more computation on promising routes without checking every possibility. The result depends on the search budget and rollout choices, so a promising sampled solution is not a guarantee of the optimal route. section 7.3 section 7.4

How Applied Reinforcement Learning covers it

How deep it goes
Explains the four search phases and UCB1, then implements a routing solver with greedy rollouts and local improvement.
Examples
Uses delivery-fleet routing with customer demands, vehicle capacities, nearest-neighbor rollouts, and 2-opt route improvement.
What you can do after
Build it from scratch for capacitated vehicle routing using a tree of states, simulated completions, and reward updates.
How it connects
Connects Monte Carlo simulation, Markov decision processes, dynamic programming, temporal-difference learning, and exploration versus exploitation.

Also explained in

Compare how 2 books explain Monte Carlo Tree Search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.