liveBook · Manning

Selection phase

As explained in Applied Reinforcement Learning

The 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.

In Monte Carlo tree search, selection follows the existing tree from the root, choosing a branch at each node. It directs search toward promising routes without ignoring under-explored ones. section 7.3

At each step, selection uses UCB1 to balance:

  • Exploitation: favor nodes with higher average reward from past visits. section 7.3
  • Exploration: give less-visited nodes a larger bonus. section 7.3
  • Continue until reaching a node with unexplored actions or a terminal state. section 7.5

Choosing between routes

With the given visit counts and rewards, Route A scores −14.28 and Route B scores −45.36 under UCB1. Since selection chooses the higher score, it follows Route A. section 7.3

Figure 7.5 UCB1 algorithm for node selection in MCTS.

The UCB1 figure illustrates the score used to select a child node. section 7.3

How Applied Reinforcement Learning covers it

How deep it goes
Explains tree navigation and UCB1’s reward and exploration terms, stopping at the selection step.
Examples
Compares two vehicle routes using calculated UCB1 scores.
What it assumes
Assumes a rooted search tree with visit and reward statistics, while explaining UCB1’s scoring terms.
What you can do after
Apply UCB1 to choose which child node to follow during selection.
How it connects
Connects Monte Carlo tree search with UCB1 and the exploration–exploitation trade-off.

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.