Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search

Question

I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most commonly associated with the MCTS. It is described as a repeated iteration of the following four steps:

1. Selection: Start from root R. Choose a leaf node L by iteration of some choice algorithm that determines which child node to choose at each branching. UTC being a prominent choice.
2. Expansion: Create one or more offspring nodes, unless L is terminal. Choose one of them, say C.
3. Simulation: Play the game from C, randomly or according to some heuristic.
4. Backpropagation: Update rewards and number of simulations for each node on the branch R-->C.

When implementing this algorithm by myself I was unclear about the following interpretation of step 1 and 2:

Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child? If I expand all, then the tree grows exponentially large on each MCTS step, I suspect. When I expand one or a few, then either the selection step itself becomes problematic or the term leaf does. The first problem arises, because after the expansion step the node L is no longer a leaf and can never be chosen again during the selection step and in turn all the children that were not expanded will never be probed. If, however, the node L keeps being a leaf node, contrary to graph-theoretic nomenclature, then during the selection step one would need to check at each node, whether there are non-expanded child-nodes. According to which algorithm should one then choose whether to continue down the tree or expand at this non-leaf "leaf" some more yet unexpanded children?

Q2. Related to the first question, but slightly more in the direction of the exploitation-exploration part of the selection, I am puzzled about the UTC selection step, which again raises issues for each of the above-mentioned expansion methods: In case that a few or all child-nodes are chosen during expansion at the leaf, one is faced with the problem that some of those nodes will not be simulated in that MCTS step and subsequently will have a diverging UTC value $w_i/n_i + c \sqrt{\frac{\ln{N_i}}{n_i}}\to \infty$, since $n_i\to 0$. On the other hand, in case that only one child is chosen, we are facing the issue that no UTC value can be assigned to the "unborn" children on the way. In other words, one cannot use UTC to decide whether to choose a child node according to UTC at each branching or to expand the tree at that node (since all nodes within the tree may have some unexpanded child nodes).

Answer 1

Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child?

Expanding all nodes or expanding just one node are both possible. There are different advantages and disadvantages. The obvious disadvantage of immediately expanding them all is that your memory usage will grow more quickly. I suppose that the primary advantage is that you no longer need to keep track separately of "actions that are legal but for which I did not yet create child nodes" and "already-created nodes", which I guess might sometimes lead to better computational efficiency (especially when memory isn't a concern for you, for instance if you do relatively few iterations anyway or if you have a huge amount of memory available).

In the more "modern" variants of MCTS that also use trained policy networks (like all the work inspired by AlphaGo / AlphaGo Zero / AlphaZero), it typically makes most sense to expand all children at once, because the trained network will immediately give you policy values for all children anyway, so then you can prime them all at once with those policy head outputs and also immediately start using all of those values.

In the case where you choose to expand only one child at a time, indeed the terminology of "leaf" nodes becomes confusing / incorrect. I never really like the term "leaf" node in the context of MCTS anyway; they're really not leaf nodes (unless they happen to represent terminal game states), they're just nodes for which did not yet choose to instantiate all the child nodes. It's a bit more verbose, but I prefer referring to them as "nodes that have not yet been fully expanded". That would change the description of the Selection phase to something more like:

Selection: Start from root R. Choose a node L that has not yet been fully expanded (or a terminal node) by iteration of some choice algorithm that determines which child node to choose at each branching.

---

In case that a few or all child-nodes are chosen during expansion at the leaf, one is faced with the problem that some of those nodes will not be simulated in that MCTS step and subsequently will have a diverging UTC value $w_i/n_i + c \sqrt{\frac{\ln{N_i}}{n_i}}\to \infty$, since $n_i\to 0$.

That's true, but I don't see that as a problem. Suppose we're at a non-fully-expanded node; a node where maybe some legal actions already have corresponding child nodes, or maybe none do, but at least some legal actions still don't have corresponding child nodes. We can view these as having a visit count of $0$, which we can view as leading to a UCB1 value of $\infty$. Since UCT picks nodes (or actions) according to an $\arg\max$ over the UCB1 values, we can simply think of this as UCT always preferring to pick actions that we did not yet expand over actions that we've already expanded and created a child node for. This leads to an implementation where we'll only re-visit a node that we've already visited before if we have already visited each of its possible siblings at least once too.