Answers.Body: <p>Let's look at the first simulation where <span class="math-container">$k = 1$</span>.
  We have <span class="math-container">$G^0 = r_1 + \gamma v^0$</span> and <span class="math-container">$G^1 = v^1$</span>, and we can pick one of them as the update target. The difference is that <span class="math-container">$G^1$</span> is fully conditioned on the action <span class="math-container">$a_1$</span> we just took, while <span class="math-container">$G^0$</span> is only partially so.
  We choose <span class="math-container">$G^1$</span> for the same reason that we do the search: we assume the evaluations of child nodes conditioned on more actions is better than the evaluation of the root alone.</p>
  <p>EDIT:
  I believe the expectation should match so that <span class="math-container">$\mathbb{E}[G^n] = \mathbb{E}[r_{n+1} + \gamma G^{n+1}]$</span>.
  I looked deeper into it and I agree it's confusing.
  I think what's happening is that in the paper they mixed two different definitions of <span class="math-container">$Q$</span>: either <span class="math-container">$Q(s, a) = V(s')$</span> or <span class="math-container">$Q(s, a) = R(s, a) + V(s')$</span>.
  Their implementations (based on <a href="https://gist.github.com/Mononofu/7548d8aa4bf94e12bc7eb7662fd60b56#file-stochastic_muzero-py-L558" rel="nofollow noreferrer">MuZeor's pseudo-code</a> and <a href="https://github.com/deepmind/mctx/blob/7a51a4da9ded98fc60c93262b80bd8145000b91c/mctx/_src/tree.py#L135" rel="nofollow noreferrer">MCTX</a>) suggest that <span class="math-container">$Q(s, a) = V(s')$</span> because child nodes store values without considering the last received reward.
  However, the reward plays a part in the child selection phase, so a better way to write their selection formula is</p>
  <p><span class="math-container">$$a^{k}=\arg \max_{a} R(s, a) + Q(s, a)+P(s, a) \frac{\sqrt{\sum_{b} N(s, b)}}{1+N(s, a)}\left[c_{1}+\log \left(\frac{\sum_{b} N(s, b)+c_{2}+1}{c_{2}}\right)\right]$$</span> and this reflects what they are doing in the code.</p>
  <p>On the other hand, what you suggested make perfect sense too if we adopt the other definition of <span class="math-container">$Q$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-13T07:12:10.753Z
Answers.Text: Shouldnt $G^{n}\ =r_{n+1}+\gamma G^{n+1}$? You still havent explained how the immediate reward is accounted for. In the first simulation if you go with $G^{1}$, you disregard $r_{1}$.
Answers.UserDisplayName: Matrix001
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-13T20:55:02.403Z
Answers.Text: @Matrix001 Updated.
Answers.UserDisplayName: Uduse
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-28T20:01:57.617Z
Answers.Text: @Matrix001 does it make sense now?
Answers.UserDisplayName: Uduse
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-12T23:38:10.250Z
Answers.LastActivityDate: 2022-08-13T20:54:36.607Z
Answers.LastEditDate: 2022-08-13T20:54:36.607Z
Answers.UserDisplayName: Uduse
Body: <p>On page 12 of this paper: <a href="https://arxiv.org/pdf/1911.08265.pdf" rel="nofollow noreferrer">Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model</a>, it describes how MCTS works for the MuZero algorithm. It states in equation 4 that during the 'backup' after a simulation, the mean value (Q) for every edge in the simulation path is updated by:</p>
  <p><span class="math-container">$$Q\left(s^{k-1},\ a^k\right){\colon=}\frac{N\left(s^{k-1},\ a^k\right)Q\left(s^{k-1},\ a^k\right)+G^k}{N\left(s^{k-1},\ a^k\right)+1}$$</span></p>
  <p>where <span class="math-container">$G^k$</span> is the return from depth <span class="math-container">$k$</span> and onwards in the simulation.</p>
  <p>However, I don't see how this equation accounts for the immediate reward attained by transitioning from state <span class="math-container">$s^{k-1}$</span> to <span class="math-container">$s^{k}$</span>.</p>
  <p>Since <span class="math-container">$Q\left(s^{k-1},\ a\right)$</span> is used to determine what action to select from state <span class="math-container">$s^{k-1}$</span>, shouldn't the backprop use the return from k-1 (<span class="math-container">$G^{k-1}$</span>), to update the mean value instead of <span class="math-container">$G^k$</span>?</p>
  
Tags: <reinforcement-learning><papers><monte-carlo-tree-search><muzero>
Title: In the MuZero paper, how does backprop in the MCTS account for the immediate reward from each edge?
UserDisplayName: Matrix001
ThreadText: # In the MuZero paper, how does backprop in the MCTS account for the immediate reward from each edge?
  
  (Asked by: username_0 on 2022-05-31)
  
  On page 12 of this paper: [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://arxiv.org/pdf/1911.08265.pdf), it describes how MCTS works for the MuZero algorithm. It states in equation 4 that during the 'backup' after a simulation, the mean value (Q) for every edge in the simulation path is updated by:
  
  $$Q\left(s^{k-1},\ a^k\right){\colon=}\frac{N\left(s^{k-1},\ a^k\right)Q\left(s^{k-1},\ a^k\right)+G^k}{N\left(s^{k-1},\ a^k\right)+1}$$
  
  where $G^k$ is the return from depth $k$ and onwards in the simulation.
  
  However, I don't see how this equation accounts for the immediate reward attained by transitioning from state $s^{k-1}$ to $s^{k}$.
  
  Since $Q\left(s^{k-1},\ a\right)$ is used to determine what action to select from state $s^{k-1}$, shouldn't the backprop use the return from k-1 ($G^{k-1}$), to update the mean value instead of $G^k$?
  
  **Tags:** reinforcement-learning, papers, monte-carlo-tree-search, muzero
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-08-12. Score: 1 | Accepted answer
  
  Let's look at the first simulation where $k = 1$.
  We have $G^0 = r\_1 + \gamma v^0$ and $G^1 = v^1$, and we can pick one of them as the update target. The difference is that $G^1$ is fully conditioned on the action $a\_1$ we just took, while $G^0$ is only partially so.
  We choose $G^1$ for the same reason that we do the search: we assume the evaluations of child nodes conditioned on more actions is better than the evaluation of the root alone.
  
  EDIT:
  I believe the expectation should match so that $\mathbb{E}[G^n] = \mathbb{E}[r\_{n+1} + \gamma G^{n+1}]$.
  I looked deeper into it and I agree it's confusing.
  I think what's happening is that in the paper they mixed two different definitions of $Q$: either $Q(s, a) = V(s')$ or $Q(s, a) = R(s, a) + V(s')$.
  Their implementations (based on [MuZeor's pseudo-code](https://gist.github.com/Mononofu/7548d8aa4bf94e12bc7eb7662fd60b56#file-stochastic_muzero-py-L558) and [MCTX](https://github.com/deepmind/mctx/blob/7a51a4da9ded98fc60c93262b80bd8145000b91c/mctx/_src/tree.py#L135)) suggest that $Q(s, a) = V(s')$ because child nodes store values without considering the last received reward.
  However, the reward plays a part in the child selection phase, so a better way to write their selection formula is
  
  $$a^{k}=\arg \max\_{a} R(s, a) + Q(s, a)+P(s, a) \frac{\sqrt{\sum\_{b} N(s, b)}}{1+N(s, a)}\left[c\_{1}+\log \left(\frac{\sum\_{b} N(s, b)+c\_{2}+1}{c\_{2}}\right)\right]$$ and this reflects what they are doing in the code.
  
  On the other hand, what you suggested make perfect sense too if we adopt the other definition of $Q$.
  
  > **Comments:**
  > **username_0**: Shouldnt $G^{n}\ =r_{n+1}+\gamma G^{n+1}$? You still havent explained how the immediate reward is accounted for. In the first simulation if you go with $G^{1}$, you disregard $r_{1}$.  
  > **username_1**: @username_0 Updated.  
  > **username_1**: @username_0 does it make sense now?  
  
  ---
  
  