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:
- Starting from the current position, we (randomly) traverse the current search tree
- Once we reach a leaf node the current NN is evaluated to get a value and policy
- The node is expanded. The policy is used to initialize the likelihood of picking the respective possible next moves
- The value is propagated upwards, so paths that lead to large values are visited more often during this MCTS
- 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?