4
$\begingroup$

From the AlphaGo Zero paper, during MCTS, statistics for each new node are initialized as such:

${N(s_L, a) = 0, W (s_L, a) = 0, Q(s_L, a) = 0, P (s_L, a) = p_a}$.

The PUCT algorithm for selecting the best child node is $a_t = argmax(Q(s,a) + U(s,a))$, where $U(s,a) = c_{puct} P(s,a) \frac{\sqrt{\sum_b N(s,b)}}{1 + N(s, a)}$.

If we start from scratch with a tree that only contains the root node and no children have been visited yet, then this should evaluate to 0 for all actions $a$ that we can take from the root node. Do we then simply uniformly sample an action to take?

Also, during the expand() step when we add an unvisited node $s_L$ to the tree, this node's children will also have not been visited, and we run into the same problem where PUCT will return 0 for all actions. Do we do the same uniform sampling here as well?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ This is a very good question. Related to this is the backprop step (which influences the $N(s,b)$ statistic). The original paper states that the backprop step updates for all time steps $t \le L$, but it doesn't make sense to update $(s_L, a_L)$ because $s_L$ is the leaf node that we just expanded: what is $a_L$, do we uniformly pick an action at random? Or does the author mean to backprop for all time steps $t < L$ instead? This code (github.com/suragnair/alpha-zero-general/blob/master/MCTS.py) does backprop only on $t < L$, not $t \le L$. $\endgroup$
    – user3667125
    Dec 30, 2020 at 7:51
  • 2
    $\begingroup$ Additionally, (to answer your question) the code above adds a small epsilon $\epsilon = 1e-8$ to $\sum_b N(s,b)$ so that $U(s,a) \neq 0$ and does the selection proportional to the prior $P(s,a)$, but I cannot verify if the AlphaZero authors do it this way as well, so I cannot submit that as an answer. $\endgroup$
    – user3667125
    Dec 30, 2020 at 7:57
  • $\begingroup$ While I can't verify whether the original paper does this or not, backprop'ing $t<L$ and adding that epsilon seems reasonable. It makes no sense to use some other arbitrary sampling scheme when we have priors already. $\endgroup$
    – sb3
    Dec 30, 2020 at 19:28
  • $\begingroup$ It's a bit more complicated, because AlphaZero's MCTS algorithm is a modified version of a true MCTS algorithm (AlphaZero doesn't actually use a true MCTS because it doesn't use Monte-Carlo simulations to roll out the entire game). The true MCTS algorithm does select a node at random, so it would make sense for AlphaZero to also select a $a_L$ at random if it stays true to MCTS. See analyticsvidhya.com/blog/2019/01/… for more info on how the true MCTS selects the first node. $\endgroup$
    – user3667125
    Dec 30, 2020 at 23:03
  • $\begingroup$ I did some more research, and found the answer. See my post below. $\endgroup$
    – user3667125
    Dec 30, 2020 at 23:58

1 Answer 1

Reset to default
3
$\begingroup$

I looked at the Python pseudo-code attached to the Data S1 of the Supplementary Materials of the AlphaZero paper. Here is my findings:

  • Contrary to the paper, AlphaZero does not store $\{N(s, a), W(S, a), Q(s, a), P(s, a)\}$ statistics for each edge $(s,a)$. Instead, AlphaZero stores $\{N(s), W(S), Q(s), P(s)\}$ statistics for each node $s$.
  • When a leaf node $S_L$ is expanded, it's visit count, value scores, and action policies are immediately updated in $\{N(s), W(S), Q(s), P(s)\}$, so $N(s)$ is at least $1$. This is why in the paper, the backprop step updates for all time steps $t \le L$ rather than $t < L$. It makes sense to update $s_L$ even though there is no corresponding $a_L$ to pair it with.
  • Therefore, when a new leaf node is expanded, the value $U(s, a)$ of a child of that leaf node will be nonzero, since $\sqrt{\sum_b N(s,b)}$ is actually computed as $N(s_{parent})$ in the code, which is at least 1.
  • Oddly enough, I think there might be a bug in the pseudocode, because at the beginning on the first iteration (starting at the root node), $U(s,a) = 0$ for all child nodes of the root node. This is because at the first iteration, $N(s_{root}) = 0$. The value of all child nodes will be $0$, and since the authors chose to break ties according to Python's max function, the algorithm simply chooses the first element it finds in case of a tie.
  • After the first iteration, $N(s_{root}) > 0$ and so $U(s,a) \neq 0$ and things proceed as normal since the backprop step will have updated the visit count of the root node. So this possible bug/unintuitive behavior only affects the first iteration. It is extremely minor and insignificant, and does not affect the outcome of the MCTS, which is probably why it went unnoticed.
Improve this answer
$\endgroup$
11
  • $\begingroup$ I'm good on everything except the third bullet point, which seems very counterintuitive and not how the authors described it in the paper. It sounds like you're saying that every time we run the PUCT algorithm, $\sqrt{\sum_b N(s, b)}$ uses the visit count of the parent node $s_{L-1}$ and in the denominator, $1 + N(s, a)$ is the visit count of the new leaf node $s_L$? I thought the whole point of the $U$ term in PUCT was to encourage exploration by selecting nodes that have been visited less, in which case the numerator should be counting the total number of visits to children of $s_{L-1}$. $\endgroup$
    – sb3
    Dec 31, 2020 at 20:24
  • $\begingroup$ Yes, $\sqrt{\sum_b N(s,b)}$ is actually just the visit count of the parent, and $N(s,a)$ is just the visit count of the current node. If the current selection is looking at a leaf node, then yes the parent would be $s_{L-1}$ and current node would be $s_L$. I was surprised as well because this differs from the equation in the paper, but it's how it is coded. $\endgroup$
    – user3667125
    Dec 31, 2020 at 20:26
  • $\begingroup$ To me, this defeats the purpose and intuition behind the PUCT algorithm. How are we encouraging exploration with the $U$ term if in the numerator, we are counting the visits to the parent node $s_{L-1}$? Or maybe it's only the denominator that matters for exploration? $\endgroup$
    – sb3
    Dec 31, 2020 at 20:28
  • $\begingroup$ The denominator is what encourages exploration. All the sibling nodes have the same numerator (since they have the same parent), but the ones that are less visited have a smaller denominator, so the overall fraction is larger. $\endgroup$
    – user3667125
    Dec 31, 2020 at 20:29
  • $\begingroup$ I guess it still does what it was intended to do, albeit not quite the way the algorithm is described in the paper. I wish this was clarified but, oh well. $\endgroup$
    – sb3
    Dec 31, 2020 at 20:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .