liveBook · Manning

Expansion phase

As explained in Applied Reinforcement Learning

The expansion phase is the Monte Carlo tree search step that adds a child node for an action not previously represented at the selected node.

In Monte Carlo tree search (MCTS), expansion grows the search tree one child at a time: from a selected node, try an action not yet represented there and add its child node. Repeating this step builds the tree incrementally instead of exploring every possible route. section 7.5

Expansion sits between selection and simulation in the MCTS cycle:

  • Selection navigates the existing tree to a node with unexplored actions; expansion adds one child for an untried action. section 7.5
  • Simulation completes a solution from the expanded node, and backpropagation updates statistics along the path to the root. section 7.5

Vehicle routing

When searching for customer routes, expansion adds a child for an action not yet tried at the selected node, gradually extending the route-search tree. section 7.3 section 7.5

Figure 7.4 The four-phase cycle of Monte Carlo Tree Search.

Use the four-phase cycle to see where expansion fits between selection and simulation. section 7.3

How Applied Reinforcement Learning covers it

How deep it goes
Describes the expansion step procedurally, stopping at adding one child per iteration without detailing implementation.
Examples
Uses vehicle routing, where an untried action adds a child to the route-search tree.
What you can do after
Understand how adding an untried action's child incrementally extends an MCTS search tree.
How it connects
Connects expansion to Monte Carlo tree search, selection, simulation, and backpropagation.

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.