Why does training a NN using MCTS work even if the number of simulations isn't much larger than the number of actions?

Question

tl;dr If the visit rates of children generated by MCTS is biased because not enough samples were taken, why doesn't the network learn random behavior?

My understanding of combining MCTS and NNs (e.g. for MuZero) is that we start with an untrained network, and then play games. For each new game, we pick the next move by doing a MCTS:

1. Starting from the current position, we (randomly) traverse the current search tree
2. Once we reach a leaf node the current NN is evaluated to get a value and policy
3. The node is expanded. The policy is used to initialize the likelihood of picking the respective possible next moves
4. The value is propagated upwards, so paths that lead to large values are visited more often during this MCTS
5. Restart from step 1, for a total of N simulations

Once this is done, we sample the next move by looking at the children of the root node. The more often it has been visited, the more likely the respective action is to be chosen. We also save the current game state and the distribution of visits to our replay buffer.

During training, a random game state is picked from the replay buffer. The networks policy head is trained to return the empirical distribution generated by the MCTS: Children that were visited more often should have a higher prior.

But I'm not sure why this algorithm succeeds, given the apparently low number of MCTS iterations compared to the action space. According to their pseudo code and paper, Go has 362 possible actions, and they run 800 simulations (MCTS iterations) per generated move. So for the initial network which was untrained, we would expect that every child has approximately the same prior (they even refer to a UniformNetwork in their code). Therefore, during the initial games, the maximum depth reached will be about 3. This is not deep enough to discern good moves from bad ones, so the value head will not receive useful training signals.

Say, due to randomness, action 1 is chosen twice, but action 2 is not chosen at all. Then, the network will learn this distribution, even though there's no reason behind it. Once it has learned this, future plays will rarely visit action 2, further enforcing this.

The only explanation I could see is that the number of games played before any training starts is huge - some of them will favor action 1, some will favor action 2. On average, this may cancel out. Is this correct? Or is there another mechanism at work?

If the reason this works is the averaging, is there some literature on how many games are necessary to benefit from this effect?

Answer 1

Your understanding of AlphaZero-style MCTS seems correct, except that tree traversal does not happen randomly! It uses the PUCT formula to pick the child node. Similarly the policy is not simply the probability of picking a certain child, it's just a term in the PUCT formula. In fact the tree search is fully deterministic, except for the additional Dirichlet noise injected at the root node. Your summary of the training process is correct.

My answer here covers the "true signals" the (Alpha/Mu)Zero training process gets, and how training can initially get started even with a random or uniform network. This should already provide some intuition for why all of this works!

Some additional responses to your questions, not in order:

Say, due to randomness, action 1 is chosen twice, but action 2 is not chosen at all. Then, the network will learn this distribution, even though there's no reason behind it.

Like I said, this randomness can only come from the Dirichlet noise. But it will tend to average out over many positions. The NN will not really learn specific details caused by noise, it will only learn the average that remains, which is a lot better.

The only explanation I could see is that the number of games played before any training starts is huge - some of them will favor action 1, some will favor action 2. On average, this may cancel out. Is this correct? Or is there another mechanism at work?

You partially got it right (things average out) but this does not require that many games are played before training starts, this averaging out can also happen over time while the network keeps training. More importantly, there are always the true signals I linked to earlier to provide useful learning information that's able to overcome the noise.

Therefore, during the initial games, the maximum depth reached will be about 3. This is not deep enough to discern good moves from bad ones, so the value head will not receive useful training signals.

Yes, very few nodes are searched during selfplay (typically 200-2000). Two things to keep in mind though:

• The NN learns to approximate the result of tree search. This is very important and the core idea behind AlphaZero! This means that each NN evaluation can almost be seen as its own mini tree search, greatly extending the "real" depth of the search that happens.
• Though the policy term in PUCT, the tree search is very selective, meaning it explores some branches deeply and other only very shallowly. Even with limited visits, the tree search commonly reaches depths of 20-30 for some moves.