MCTS: How to choose the final action from the root

Question

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root?

• The original UCT paper (2006) says bestAction in their algorithm.

• Monte-Carlo Tree Search: A New Framework for Game AI (2008) says

The game action finally executed by the program in the actual game, is the one corresponding to the child which was explored the most.

• A Survey of Monte Carlo Tree Search Methods (2012) says

The basic algorithm involves iteratively building a search tree until some predefined computational budget – typically a time, memory or iteration constraint – is reached, at which point the search is halted and the best-performing root action returned.

[...] The result of the overall search a(BESTCHILD(v0)) is the action a that leads to the best child of the root node v0, where the exact definition of “best” is defined by the implementation.

[...] As soon as the search is interrupted or the computation budget is reached, the search terminates and an action a of the root nodet0is selected by some mechanism. Schadd [188] describes four criteria for selecting the winning action, based on the work of Chaslot et al [60]:

1. Max child: Select the root child with the highest reward.

2. Robust child: Select the most visited root child.

3. Max-Robust child: Select the root child with both the highest visit count and the highest reward. If none exist, then continue searching until an acceptable visit count is achieved [70].

4. Secure child: Select the child which maximises a lower confidence bound.

[...] Once some computational budget has been reached, the algorithm terminates and returns the best move found,corresponding to the child of the root with the highest visit count.

The return value of the overall search in this case is a(BESTCHILD(v0,0)) which will give the action a that leads to the child with the highest reward, since the exploration parameter c is set to 0 for this final call on the root node v0. The algorithm could instead return the action that leads to the most visited child; these two options will usually – but not always! – describe the same action. This potential discrepancy is addressed in the Go program ERICA by continuing the search if the most visited root action is not also the one with the highest reward. This improved ERICA’s winning rate against GNU GO from 47% to 55% [107].

But their algorithm 2 uses the same criterion as the internal-node selection policy:

$$\operatorname{argmax}_{v'} \frac{Q(v')}{N(v')} + c \sqrt{\frac{2 \ln N(v)}{N(v')}}$$

which is neither the max child nor the robust child! This situation is quite confusing, and I'm wondering which approach is nowadays considered most successful/appropriate.

Answer 1

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" in the 2012 paper you linked.

In algorithm 2 of the 2012 paper, they actually use the highest average reward, which corresponds to "Max child". It looks like they're using the UCB1 policy, but they actually use a value of $0$ for the exploration parameter $c$, which makes the entire square root term drop out. This is also explained in the text at the end of your quote. But usually, a robust child / max visit count performs better.

Progressive Strategies for Monte-Carlo Tree Search is a different paper from 2008, in which these strategies are experimented with a bit. Usually, they perform similarly, but a robust child tends to be the best if there is any difference at all.