In Alpha(Go)Zero, why is the policy extracted from MCTS better than the network one?

Question

I've read through the Alpha(Go)Zero paper and there is only one thing I don't understand.

The paper on page 1 states:

The MCTS search outputs probabilities π of playing each move. These search probabilities usually select much stronger moves than the raw move probabilities p of the neural network fθ(s);

My question: Why is this the case? Why is $\pi$ usually better than $p$? I think I can imagine why it's the case but I'm looking for more insight.

what $\pi$ and $p$ are:

Say we are in state $s_1$. We have a network that takes the state and produces $p_1$ (probabilities for actions) and $v_1$ (a value for the state). We then run MCTS from this state and extract a policy $\pi(a|s_1) = \frac{N(s_1,a)^{1/\tau}}{\sum_b N(s_1,b)^{1/\tau}}$. The paper is saying that $\pi(-|s_1)$ is usually better than $p_1$.

Answer 1

The most important word for answering your question from that quote from the paper is probably the word "usually": These search probabilities usually select much stronger moves than the raw move probabilities $p$ of the neural network. It's not always going to be true, but more often than not / most of the time / "on average", we intuitively expect it to be true. In theory there could be pathological cases, especially with low MCTS iteration counts and/or a poorly-trained network, where it may not be true. But even if we just find it to be true most of the time, that can be good enough for the algorithm to work well in practice.

Recall that in the Selection phase of MCTS, Alpha(Go) Zero always selects the action $a$ that maximises the following expression for a state $s$ when traversing the tree (see supplementary material of Alpha Zero paper):

$$Q(s, a) + C(s) \frac{P(s, a) \sqrt{N(s)}}{1 + N(s, a)}$$

The $Q(s, a)$ values here are the value estimates resulting from the MCTS search; these are the results produced by our tree search, and these generally become more and more accurate the longer our tree search runs. If we run our tree search for an infinite amount of time, we expect these to converge to the true minimax values.

These same $Q(s, a)$ values are the things that can cause the final distribution of visit counts $\pi$ to shift away from the prior neural network distribution $P$. Suppose that we have a hypothetical case where for all the different actions $a$, the $Q(s, a)$ values end up staying identical. In this (unlikely) hypothetical case, the visit counts would continue getting distributed proportionally to $P(s, a)$, causing the $\pi$ distribution to stay equal to the $P$ one (barring minor potential differences due to $\pi$ being derived from discrete, integer visit counts which may not be able to exactly replicate the real-valued probabilities in $P$). Only if the $Q(s, a)$ values resulting from a (hopefully smart!) tree search algorithm give us reason to shift away from the prior distribution $P$ do we actually really start shifting away from it.