Answers.Body: <p>I don't think you've necessarily made any real mistakes in your calculations or anything like that, that all seems accurate. I can't really confidently answer your questions about &quot;Does X usually happen?&quot; or &quot;How common is X?&quot;, would have to experiment to make sure of that. I think we can also confidently immediately answer the question about whether MCTS is robust and can still produce high quality policies with &quot;yes&quot;, since we've seen state-of-the-art, superhuman results in a bunch of games using these techniques.</p>
  <p>But I do think there's a few important details that may change your perception:</p>
  <ol>
  <li><p>MCTS does not compare <span class="math-container">$Q(s, a)$</span> values to <span class="math-container">$U(s, a)$</span> values in its selection phase. It compares <span class="math-container">$Q(s, a) + U(s, a)$</span> expressions of actions <span class="math-container">$a$</span>, to <span class="math-container">$Q(s, b) + U(s, b)$</span> expressions for different actions <span class="math-container">$b$</span>. So, the difference in magnitudes <span class="math-container">$Q(s, a) - U(s, a)$</span> is not nearly as important as the difference in magnitude <span class="math-container">$Q(s, a) - Q(s, b) + U(s, a) - U(s, b)$</span>!</p>
  </li>
  <li><p>For any single given state <span class="math-container">$s$</span>, it is certainly not the case that we expect the different <span class="math-container">$Q$</span>-values to be have a nice average like <span class="math-container">$0.5$</span> or anything like that. There will likely be plenty of states <span class="math-container">$s$</span> where we're already in such a strong position that we can afford to make a mistake or two and still expect to win; all the <span class="math-container">$Q$</span> values here will be close to <span class="math-container">$1.0$</span>. There will also be many states where we're in such a terrible position that we expect to lose no matter what; all the <span class="math-container">$Q$</span> values here will be close to <span class="math-container">$0.0$</span>. And then there will of course be states that a network is not sure about, which will have <span class="math-container">$Q$</span> values somewhere in between. I suspect that &quot;in between&quot; won't often be a nice mix of all sorts of different values though. If it's something like <span class="math-container">$0.7$</span>, and there's higher values that attract more attention, during training the MCTS + network will likely become very interested in learning more about that state, and very quickly learn whether that should really just be a <span class="math-container">$1.0$</span> or whether it should be lowered. For this reason, I imagine that in unsure states, values will have a tendency to hover around <span class="math-container">$0.5$</span>.</p>
  </li>
  <li><p>MCTS will only let the <span class="math-container">$Q(s, a)$</span> term <strong>dominate the selection phase for as long as it believes that this is actually likely to lead to a win</strong>. If this is correct and indeed leads to a win, well, that's great, no need to explore anything else! During the tree search, if further investigation of this action leads the MCTS to believe that it actually is a loss, the <span class="math-container">$Q$</span> value will drop (ideally towards <span class="math-container">$0$</span>), and then it will automatically stop being a dominant term. If the tree search fails to adjust for this in time, and we end up wandering down this losing path anyway, we'll get a value signal of <span class="math-container">$0$</span> at the end and update our value network and in the future we'll know better than to repeat this mistake.</p>
  </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-04T20:08:44.673Z
Answers.LastActivityDate: 2020-12-04T20:08:44.673Z
Answers.UserDisplayName: Dennis Soemers
Body: <h2>AlphaGo Zero</h2>
  <p>AlphaGo Zero uses a Monte-Carlo Tree Search where the selection phase is governed by <span class="math-container">$\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$</span>, where:</p>
  <ol>
  <li>the exploitation parameter is <span class="math-container">$Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$</span> (i.e. the mean of the values <span class="math-container">$v_i$</span> of all simulations that passes through edge <span class="math-container">$(s_t, a)$</span>)</li>
  <li>the exploration parameter is <span class="math-container">$U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$</span> (i.e. the prior probability <span class="math-container">$P(s_t, a)$</span>, weighted by the constant <span class="math-container">$c_{puct}$</span>, the number of simulations that passes through <span class="math-container">$(s_t, a)$</span>, as well as the number of simulations that passes through  <span class="math-container">$s_t$</span>).</li>
  </ol>
  <p>The prior probability <span class="math-container">$P(s_t, a)$</span> and simulation value <span class="math-container">$v_i$</span> are both outputted by the deep neural network <span class="math-container">$f_{\theta}(s_t)$</span>:</p>
  <blockquote>
  <p>This neural network takes as an input the raw board representation s of the position and its history, and outputs both move probabilities and a value, (p, v) = fθ(s). The vector of move probabilities p represents the probability of selecting each move a (including pass), pa = Pr(a| s). The value v is a scalar evaluation, estimating the probability of the current player winning from position s.</p>
  </blockquote>
  <h2>My confusion</h2>
  <p>My confusion is that <span class="math-container">$P(s_t, a)$</span> and <span class="math-container">$v_i$</span> are probabilities normalized to different distributions, resulting in <span class="math-container">$v_i$</span> being about 80x larger than <span class="math-container">$P(s_t,a)$</span> on average.</p>
  <p>The neural network outputs <span class="math-container">$(p, v)$</span>, where <span class="math-container">$p$</span> is a probability vector given <span class="math-container">$s_t$</span>, normalized over all possible actions in that turn. <span class="math-container">$p_a = P(s_t, a)$</span> is the probability of choosing action <span class="math-container">$a$</span> given state <span class="math-container">$s_t$</span>. A game of Go has about 250 moves per turn, so on average each move has probability <span class="math-container">$\frac{1}{250}$</span>, i.e. <span class="math-container">$\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$</span></p>
  <p>On the other hand, <span class="math-container">$v$</span> is the probability of winning given state <span class="math-container">$s_t$</span>, normalized over all possible end-game conditions (win/tie/lose). For simplicity sake, let us assume <span class="math-container">$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$</span>, where the game is played randomly and each outcome is equally likely.</p>
  <p>This means that the expected value of <span class="math-container">$v_i$</span> is at least 80x larger than the expected value of <span class="math-container">$P(s_t, a)$</span>. <strong>The consequence of this is that <span class="math-container">$Q(s_t, a)$</span> is at least 80x larger than <span class="math-container">$U(s_t, a)$</span> on average.</strong></p>
  <p>If the above is true, then the selection stage will be dominated by the <span class="math-container">$Q(s_t, a)$</span> term, so AlphaGo Zero should tend to avoid edges with no simulations in them (edges where  <span class="math-container">$Q(s_t, a) = 0$</span>) unless all existing <span class="math-container">$Q(s_t, a)$</span> terms are extremely small (<span class="math-container">$&lt; \frac{1}{250}$</span>), or the MCTS has so much simulations in them that the <span class="math-container">$\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$</span> term in <span class="math-container">$U(s_t, a)$</span> evens out the magnitudes of the two terms. The latter is not likely to happen since I believe AlphaGo Zero only uses <span class="math-container">$1,600$</span> simluations per move, so <span class="math-container">$\sqrt{\sum_b N(s_t, b)}$</span> caps out at <span class="math-container">$40$</span>.</p>
  <h2>Selecting only viable moves</h2>
  <p>Ideally, MCTS shouldn't select every possible move to explore. It should only select viable moves given state <span class="math-container">$s_t$</span>, and ignore all the bad moves. Let <span class="math-container">$m_t$</span> is the number of viable moves for state <span class="math-container">$s_t$</span>, and let <span class="math-container">$P(s_t, a)$</span> = 0 for all moves <span class="math-container">$a$</span> that are not viable. Also, let's assume the MCTS never selects a move that is not viable.</p>
  <p>Then the previous section is partly alleviated, because now <span class="math-container">$\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$</span>. <strong>As a result, <span class="math-container">$Q(s_T, a)$</span> should only be <span class="math-container">$\frac{m_t}{3}$</span> times larger than <span class="math-container">$U(s_t, a)$</span> on average</strong>. Assuming <span class="math-container">$m_t \le 6$</span>, then there shouldn't be too much of an issue</p>
  <p>However, this means that AlphaGo Zero works ideally only when the number of viable moves is small. In a game state <span class="math-container">$s_t$</span> where there are many viable moves (<span class="math-container">$&gt;30$</span>) (e.g. a difficult turn with many possible choices), the selection phase of the MCTS will deteriorate as described in the previous section.</p>
  <h2>Questions</h2>
  <p>I guess my questions are:</p>
  <ol>
  <li>Is my understanding correct, or have I made mistake(s) somewhere?</li>
  <li>Does <span class="math-container">$Q(s_t, a)$</span> usually dominate <span class="math-container">$U(s_t, a)$</span> by this much in practice when the game state has many viable moves? Is the selection phase usually dominated by <span class="math-container">$Q(s_t, a)$</span> during these game states?</li>
  <li>Does the fact that <span class="math-container">$Q(s_t, a)$</span> and <span class="math-container">$U(s_t, a)$</span> being in such different orders of magnitude (when the game state has many viable moves) affect the quality of the MCTS algorithm, or is MCTS robust to this effect and still produces high quality policies?</li>
  <li>How common is it for a game state to have many viable moves (&gt;30) in Go?</li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-03T09:48:50.193Z
Comments.Text: Too many questions in a single post and this is a big post. I suggest that you simplify this post as much as possible (i.e. to contain only the necessary info), and ask each question in its separate post.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><monte-carlo-tree-search><alphazero><alphago-zero><alphago>
Title: AlphaGo Zero: does $Q(s_t, a)$ dominate $U(s_t, a)$ in difficult game states?
UserDisplayName: user3667125
ThreadText: # AlphaGo Zero: does $Q(s_t, a)$ dominate $U(s_t, a)$ in difficult game states?
  
  (Asked by: username_0 on 2020-12-03)
  
  ## AlphaGo Zero
  
  AlphaGo Zero uses a Monte-Carlo Tree Search where the selection phase is governed by $\operatorname\*{argmax}\limits\_a\left( Q(s\_t, a) + U(s\_t, a) \right)$, where:
  
  1. the exploitation parameter is $Q(s\_t, a) = \displaystyle \frac{\displaystyle \sum\_{v\_i \in (s\_t, a)} v\_i}{N(s\_t, a)}$ (i.e. the mean of the values $v\_i$ of all simulations that passes through edge $(s\_t, a)$)
  2. the exploration parameter is $U(s\_t, a) = c\_{puct} P(s\_t,a) \frac{\sqrt{\sum\_b N(s\_t, b)}}{1 + N(s\_t, a)}$ (i.e. the prior probability $P(s\_t, a)$, weighted by the constant $c\_{puct}$, the number of simulations that passes through $(s\_t, a)$, as well as the number of simulations that passes through $s\_t$).
  
  The prior probability $P(s\_t, a)$ and simulation value $v\_i$ are both outputted by the deep neural network $f\_{\theta}(s\_t)$:
  
  > This neural network takes as an input the raw board representation s of the position and its history, and outputs both move probabilities and a value, (p, v) = fθ(s). The vector of move probabilities p represents the probability of selecting each move a (including pass), pa = Pr(a| s). The value v is a scalar evaluation, estimating the probability of the current player winning from position s.
  
  ## My confusion
  
  My confusion is that $P(s\_t, a)$ and $v\_i$ are probabilities normalized to different distributions, resulting in $v\_i$ being about 80x larger than $P(s\_t,a)$ on average.
  
  The neural network outputs $(p, v)$, where $p$ is a probability vector given $s\_t$, normalized over all possible actions in that turn. $p\_a = P(s\_t, a)$ is the probability of choosing action $a$ given state $s\_t$. A game of Go has about 250 moves per turn, so on average each move has probability $\frac{1}{250}$, i.e. $\mathbb{E}\left[ P(s\_t, a) \right] = \frac{1}{250}$
  
  On the other hand, $v$ is the probability of winning given state $s\_t$, normalized over all possible end-game conditions (win/tie/lose). For simplicity sake, let us assume $\mathbb{E} \left[ v\_i \right] \ge \frac{1}{3}$, where the game is played randomly and each outcome is equally likely.
  
  This means that the expected value of $v\_i$ is at least 80x larger than the expected value of $P(s\_t, a)$. **The consequence of this is that $Q(s\_t, a)$ is at least 80x larger than $U(s\_t, a)$ on average.**
  
  If the above is true, then the selection stage will be dominated by the $Q(s\_t, a)$ term, so AlphaGo Zero should tend to avoid edges with no simulations in them (edges where $Q(s\_t, a) = 0$) unless all existing $Q(s\_t, a)$ terms are extremely small ($< \frac{1}{250}$), or the MCTS has so much simulations in them that the $\frac{\sqrt{\sum\_b N(s\_t, b)}}{1 + N(s\_t, a)}$ term in $U(s\_t, a)$ evens out the magnitudes of the two terms. The latter is not likely to happen since I believe AlphaGo Zero only uses $1,600$ simluations per move, so $\sqrt{\sum\_b N(s\_t, b)}$ caps out at $40$.
  
  ## Selecting only viable moves
  
  Ideally, MCTS shouldn't select every possible move to explore. It should only select viable moves given state $s\_t$, and ignore all the bad moves. Let $m\_t$ is the number of viable moves for state $s\_t$, and let $P(s\_t, a)$ = 0 for all moves $a$ that are not viable. Also, let's assume the MCTS never selects a move that is not viable.
  
  Then the previous section is partly alleviated, because now $\mathbb{E} \left[ P(s\_t, a) \right] = \frac{1}{m\_t}$. **As a result, $Q(s\_T, a)$ should only be $\frac{m\_t}{3}$ times larger than $U(s\_t, a)$ on average**. Assuming $m\_t \le 6$, then there shouldn't be too much of an issue
  
  However, this means that AlphaGo Zero works ideally only when the number of viable moves is small. In a game state $s\_t$ where there are many viable moves ($>30$) (e.g. a difficult turn with many possible choices), the selection phase of the MCTS will deteriorate as described in the previous section.
  
  ## Questions
  
  I guess my questions are:
  
  1. Is my understanding correct, or have I made mistake(s) somewhere?
  2. Does $Q(s\_t, a)$ usually dominate $U(s\_t, a)$ by this much in practice when the game state has many viable moves? Is the selection phase usually dominated by $Q(s\_t, a)$ during these game states?
  3. Does the fact that $Q(s\_t, a)$ and $U(s\_t, a)$ being in such different orders of magnitude (when the game state has many viable moves) affect the quality of the MCTS algorithm, or is MCTS robust to this effect and still produces high quality policies?
  4. How common is it for a game state to have many viable moves (>30) in Go?
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, alphazero, alphago-zero, alphago
  
  > **Comments:**
  > **username_1**: Too many questions in a single post and this is a big post. I suggest that you simplify this post as much as possible (i.e. to contain only the necessary info), and ask each question in its separate post.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-12-04. Score: 2 | Accepted answer
  
  I don't think you've necessarily made any real mistakes in your calculations or anything like that, that all seems accurate. I can't really confidently answer your questions about "Does X usually happen?" or "How common is X?", would have to experiment to make sure of that. I think we can also confidently immediately answer the question about whether MCTS is robust and can still produce high quality policies with "yes", since we've seen state-of-the-art, superhuman results in a bunch of games using these techniques.
  
  But I do think there's a few important details that may change your perception:
  
  1. MCTS does not compare $Q(s, a)$ values to $U(s, a)$ values in its selection phase. It compares $Q(s, a) + U(s, a)$ expressions of actions $a$, to $Q(s, b) + U(s, b)$ expressions for different actions $b$. So, the difference in magnitudes $Q(s, a) - U(s, a)$ is not nearly as important as the difference in magnitude $Q(s, a) - Q(s, b) + U(s, a) - U(s, b)$!
  2. For any single given state $s$, it is certainly not the case that we expect the different $Q$-values to be have a nice average like $0.5$ or anything like that. There will likely be plenty of states $s$ where we're already in such a strong position that we can afford to make a mistake or two and still expect to win; all the $Q$ values here will be close to $1.0$. There will also be many states where we're in such a terrible position that we expect to lose no matter what; all the $Q$ values here will be close to $0.0$. And then there will of course be states that a network is not sure about, which will have $Q$ values somewhere in between. I suspect that "in between" won't often be a nice mix of all sorts of different values though. If it's something like $0.7$, and there's higher values that attract more attention, during training the MCTS + network will likely become very interested in learning more about that state, and very quickly learn whether that should really just be a $1.0$ or whether it should be lowered. For this reason, I imagine that in unsure states, values will have a tendency to hover around $0.5$.
  3. MCTS will only let the $Q(s, a)$ term **dominate the selection phase for as long as it believes that this is actually likely to lead to a win**. If this is correct and indeed leads to a win, well, that's great, no need to explore anything else! During the tree search, if further investigation of this action leads the MCTS to believe that it actually is a loss, the $Q$ value will drop (ideally towards $0$), and then it will automatically stop being a dominant term. If the tree search fails to adjust for this in time, and we end up wandering down this losing path anyway, we'll get a value signal of $0$ at the end and update our value network and in the future we'll know better than to repeat this mistake.
  
  
  ---
  
  