Answers.Body: <p>The most important word for answering your question from that quote from the paper is probably the word &quot;usually&quot;: These search probabilities <strong>usually</strong> select much stronger moves than the raw move probabilities <span class="math-container">$p$</span> of the neural network. It's not always going to be true, but more often than not / most of the time / &quot;on average&quot;, 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.</p>
  <p>Recall that in the Selection phase of MCTS, Alpha(Go) Zero always selects the action <span class="math-container">$a$</span> that maximises the following expression for a state <span class="math-container">$s$</span> when traversing the tree (see supplementary material of Alpha Zero paper):</p>
  <p><span class="math-container">$$Q(s, a) + C(s) \frac{P(s, a) \sqrt{N(s)}}{1 + N(s, a)}$$</span></p>
  <p>The <span class="math-container">$Q(s, a)$</span> 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.</p>
  <p>These same <span class="math-container">$Q(s, a)$</span> values are the things that can cause the final distribution of visit counts <span class="math-container">$\pi$</span> to shift away from the prior neural network distribution <span class="math-container">$P$</span>. Suppose that we have a hypothetical case where for <em>all the different actions</em> <span class="math-container">$a$</span>, the <span class="math-container">$Q(s, a)$</span> values end up staying identical. In this (unlikely) hypothetical case, the visit counts would continue getting distributed proportionally to <span class="math-container">$P(s, a)$</span>, causing the <span class="math-container">$\pi$</span> distribution to stay equal to the <span class="math-container">$P$</span> one (barring minor potential differences due to <span class="math-container">$\pi$</span> being derived from discrete, integer visit counts which may not be able to <strong>exactly</strong> replicate the real-valued probabilities in <span class="math-container">$P$</span>). Only if the <span class="math-container">$Q(s, a)$</span> values resulting from a (hopefully smart!) tree search algorithm give us reason to shift away from the prior distribution <span class="math-container">$P$</span> do we actually really start shifting away from it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-08T21:37:29.310Z
Answers.Text: 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?
Answers.UserDisplayName: Euclid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-09T07:52:54.113Z
Answers.Text: @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.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-08T19:32:59.070Z
Answers.LastActivityDate: 2020-09-08T19:32:59.070Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>Basically, the policy network just looks at the current state and doesn't have any added benefit from searching. I think of the policy network as a chess player's initial candidate move selection and the final mcts evaluation as being the evaluation after looking at their opponent's possible responses.</p>
  <p>Hopefully this intuitive answer will provide a complementary perspective to the other (much more complete) answer.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-26T17:04:13.313Z
Answers.LastActivityDate: 2022-06-26T17:04:13.313Z
Answers.UserDisplayName: JacKeown
Body: <p>I've read through the Alpha(Go)Zero paper and there is only one thing I don't understand.</p>
  <p>The paper on page 1 states:</p>
  <blockquote>
  <p>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);</p>
  </blockquote>
  <p>My question: Why is this the case? Why is <span class="math-container">$\pi$</span> usually better than <span class="math-container">$p$</span>? I think I can imagine why it's the case but I'm looking for more insight.</p>
  <p>what <span class="math-container">$\pi$</span> and <span class="math-container">$p$</span> are:</p>
  <p>Say we are in state <span class="math-container">$s_1$</span>. We have a network that takes the state and produces <span class="math-container">$p_1$</span> (probabilities for actions) and <span class="math-container">$v_1$</span> (a value for the state).
  We then run MCTS from this state and extract a policy <span class="math-container">$\pi(a|s_1) = \frac{N(s_1,a)^{1/\tau}}{\sum_b N(s_1,b)^{1/\tau}}$</span>.
  The paper is saying that <span class="math-container">$\pi(-|s_1)$</span> is usually better than <span class="math-container">$p_1$</span>.</p>
  
Tags: <reinforcement-learning><monte-carlo-tree-search><alphazero><alphago-zero>
Title: In Alpha(Go)Zero, why is the policy extracted from MCTS better than the network one?
UserDisplayName: Euclid
ThreadText: # In Alpha(Go)Zero, why is the policy extracted from MCTS better than the network one?
  
  (Asked by: username_0 on 2020-09-06)
  
  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$.
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, alphazero, alphago-zero
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-09-08. Score: 2
  
  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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: @username_0 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.  
  
  ---
  
  ### Answer by username_2 on 2022-06-26. Score: 2
  
  Basically, the policy network just looks at the current state and doesn't have any added benefit from searching. I think of the policy network as a chess player's initial candidate move selection and the final mcts evaluation as being the evaluation after looking at their opponent's possible responses.
  
  Hopefully this intuitive answer will provide a complementary perspective to the other (much more complete) answer.
  
  
  ---
  
  