Answers.Body: <p>Yeah, it seems that you're right and based on the description of the paper it would indeed behave uniformly random at the very first iteration (or maybe just always deterministically pick whichever action happens to be the first one in the list). I can't find anything that would suggest otherwise in the paper, and also <a href="https://arxiv.org/src/1911.08265v2/anc/pseudocode.py" rel="nofollow noreferrer">the pseudocode they put on arXiv suggests the same behaviour</a>.</p>
  <p>I can't really think of any reason why this would be better than playing according to <span class="math-container">$P(s, a)$</span> in the very first iteration though. Maybe it creates a tiny little bit more variety in the tree search results you get? I suppose all the stochasticity that is normally inherent to a vanilla MCTS is no longer present in MuZero (or AlphaZero), because they always run for exactly the same number of iterations, and don't have any sort of random rollouts anymore; this would at least introduce a tiny bit of variation.</p>
  <p>On the other hand, I also can't imagine this choice really making a meaningful difference in practice, except maybe if you go down to extremely low iteration counts (like if you run fewer iterations than there are legal actions in the root node).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T14:15:10.933Z
Answers.Text: But as the policy network gets better and better, it would make a bit more difference no? When I think of a game of Go, where there are hundreds of actions stemming off the root node, I wouldn't want to waste time exploring bad ones from the start : /
Answers.UserDisplayName: Ziofil
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-29T15:16:07.473Z
Answers.Text: @Ziofil I feel that it would probably not matter much in practice because this is only an issue the first time you ever visit a node, for any node. And nodes that are "good" nodes are likely to get many more than just a handful of visits anyway because the policy network will keep steering towards it if the network is good (even from nodes multiple levels higher up in the tree). But again, that's just my intuition, only way to be sure is to test it. And theoretically, I certainly don't see any *advantage* to doing it the way it is described either
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-28T14:22:29.663Z
Answers.LastActivityDate: 2020-11-28T14:22:29.663Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I'm working on reimplementing the <a href="https://arxiv.org/abs/1911.08265" rel="nofollow noreferrer">MuZero paper</a>. In the description of the MCTS (page 12), they indicate that a new node with associated state <span class="math-container">$s$</span> is to be initialized with <span class="math-container">$Q(s,a) = 0$</span>, <span class="math-container">$N(s,a) = 0$</span> and <span class="math-container">$P(s,a) = p_a$</span>. From this, I understand that the root node with state <span class="math-container">$s_0$</span> will have edges with zero visits each, zero value and policy evaluated on <span class="math-container">$s_0$</span> by the prediction network.</p>
  <p>So far so good. Then they explain how actions are selected, according to the equation (also on page 12):</p>
  <p><a href="https://i.sstatic.net/7Ltgz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7Ltgz.png" alt="enter image description here" /></a></p>
  <p>But for the very first action (from the root node) this will give a vector of zeros as argument to the argmax: <span class="math-container">$Q(s_0,a) = 0$</span> and <span class="math-container">$\sum_bN(s_0,b)=0$</span>, so even though <span class="math-container">$P(s_0,a)$</span> is not zero, it will be multiplied by a zero weight.</p>
  <p>Surely there is a mistake somewhere? Or is it that the very first action is uniformly random?</p>
  
Tags: <monte-carlo-tree-search><muzero>
Title: How to choose the first action in a Monte Carlo Tree Search?
UserDisplayName: Ziofil
ThreadText: # How to choose the first action in a Monte Carlo Tree Search?
  
  (Asked by: username_0 on 2020-11-01)
  
  I'm working on reimplementing the [MuZero paper](https://arxiv.org/abs/1911.08265). In the description of the MCTS (page 12), they indicate that a new node with associated state $s$ is to be initialized with $Q(s,a) = 0$, $N(s,a) = 0$ and $P(s,a) = p\_a$. From this, I understand that the root node with state $s\_0$ will have edges with zero visits each, zero value and policy evaluated on $s\_0$ by the prediction network.
  
  So far so good. Then they explain how actions are selected, according to the equation (also on page 12):
  
  [![enter image description here](https://i.sstatic.net/7Ltgz.png)](https://i.sstatic.net/7Ltgz.png)
  
  But for the very first action (from the root node) this will give a vector of zeros as argument to the argmax: $Q(s\_0,a) = 0$ and $\sum\_bN(s\_0,b)=0$, so even though $P(s\_0,a)$ is not zero, it will be multiplied by a zero weight.
  
  Surely there is a mistake somewhere? Or is it that the very first action is uniformly random?
  
  **Tags:** monte-carlo-tree-search, muzero
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-11-28. Score: 1
  
  Yeah, it seems that you're right and based on the description of the paper it would indeed behave uniformly random at the very first iteration (or maybe just always deterministically pick whichever action happens to be the first one in the list). I can't find anything that would suggest otherwise in the paper, and also [the pseudocode they put on arXiv suggests the same behaviour](https://arxiv.org/src/1911.08265v2/anc/pseudocode.py).
  
  I can't really think of any reason why this would be better than playing according to $P(s, a)$ in the very first iteration though. Maybe it creates a tiny little bit more variety in the tree search results you get? I suppose all the stochasticity that is normally inherent to a vanilla MCTS is no longer present in MuZero (or AlphaZero), because they always run for exactly the same number of iterations, and don't have any sort of random rollouts anymore; this would at least introduce a tiny bit of variation.
  
  On the other hand, I also can't imagine this choice really making a meaningful difference in practice, except maybe if you go down to extremely low iteration counts (like if you run fewer iterations than there are legal actions in the root node).
  
  > **Comments:**
  > **username_0**: But as the policy network gets better and better, it would make a bit more difference no? When I think of a game of Go, where there are hundreds of actions stemming off the root node, I wouldn't want to waste time exploring bad ones from the start : /  
  > **username_1**: @username_0 I feel that it would probably not matter much in practice because this is only an issue the first time you ever visit a node, for any node. And nodes that are "good" nodes are likely to get many more than just a handful of visits anyway because the policy network will keep steering towards it if the network is good (even from nodes multiple levels higher up in the tree). But again, that's just my intuition, only way to be sure is to test it. And theoretically, I certainly don't see any *advantage* to doing it the way it is described either  
  
  ---
  
  