1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm still struggling to convince myself. Maybe the following works: Since UCT converges to minimax, the probabilities $\pi$, extracted from MCTS, are almost optimal under our current value estimates (assuming we take enough steps). Now, in some sense $p$ is only as good as a single $v$. In other words, it's only as good as a single value estimate, while $\pi$ is close to optimal under value estimates for many many states... so it's probably better. This sounds half convincing, what do you think? $\endgroup$ – Euclid Sep 8 at 21:37
  • 1
    $\begingroup$ @Euclid I think so yeah. Think of it this way; suppose that for a specific action, $p$ is much lower than optimal. Then as soon as MCTS gets around to trying that action despite the low $p$, it will be more likely to receive a high $Q$ than we would expect based on the low $p$. As long as this keeps happening, and MCTS keeps receiving higher-than-expected $Q$s, it will also keep assigning more visits to it than it "should" based on $p$. But this will stop again if the $Q$-based feedback becomes negative/bad again. Warning: this was all very informal, just intuition. $\endgroup$ – Dennis Soemers Sep 9 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.