Answers.Body: <p><strong>In theory: yes, you can backpropagate any sort of scores you want to maximise.</strong> They don't have to be restricted to just a small, discrete set of values such as <span class="math-container">$\{-1, 0, 1\}$</span>, and also do not have to be in any particular range like <span class="math-container">$[-1, 1]$</span> or <span class="math-container">$[0, 1]$</span>.</p>
  <p>However, <strong>in practice it may still be useful if you can normalise whatever &quot;raw&quot; scores you have down to some smaller range</strong> (like the ranges mentioned above). This can <strong>primarily be useful for hyperparameter tuning</strong>. For example, consider the UCB1 equation that we normally use in UCT during tree traversal:</p>
  <p><span class="math-container">$$a^* = {\arg\max}_a \left( Q(s, a) + C \sqrt{\frac{\ln(\sum_{a'}N(s,a'))}{N(s,a)}} \right).$$</span></p>
  <p>We typically have a <span class="math-container">$C$</span> hyperparameter / constant in there, which controls our tradeoff between exploration and exploitation. Higher <span class="math-container">$C$</span> means more exploration, lower <span class="math-container">$C$</span> means more exploitation. The <span class="math-container">$Q(s,a)$</span> term is the average of the scores backpropagated so far for action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>. In this equation, the <span class="math-container">$Q(s, a)$</span> and the <span class="math-container">$C$</span> terms are sort of &quot;competing&quot; against each other, so their optimal values are closely related to each other. If you take an existing problem and multiply all the score values by, say, <span class="math-container">$100$</span>, you'd probably also want to multiply whatever your <span class="math-container">$C$</span> constant used to be by <span class="math-container">$100$</span> to get the same behaviour again from your tree search.</p>
  <p>Actually, what really matters for this story is not even the raw magnitudes of your <span class="math-container">$Q$</span> values, but rather the magnitudes of the typical <strong>differences</strong> you see between <span class="math-container">$Q$</span> values for different actions in the same state. So, if your problem only has <span class="math-container">$Q$</span> values that lie in the range <span class="math-container">$[99, 101]$</span>, you'll actually want a similar <span class="math-container">$C$</span> constant as when you have <span class="math-container">$Q$</span> values in the range <span class="math-container">$[-1, 1]$</span>, but if your problem has <span class="math-container">$Q$</span> values in the range <span class="math-container">$[-100, 100]$</span>, you'll likely want about <span class="math-container">$100$</span> times as big a <span class="math-container">$C$</span> value too.</p>
  <p>If you can roughly normalise your values down to approximately a <span class="math-container">$[-1, 1]$</span> or <span class="math-container">$[0, 1]$</span> range, you can feel relatively confident that similar kinds of <span class="math-container">$C$</span> values as typically used by other people in zero-sum settings will also work fine (like, <span class="math-container">$C$</span> values somewhere in the range <span class="math-container">$[0, 2]$</span>, more often than not below <span class="math-container">$1$</span>.... but the ideal constant can also very often depend on lots of other factors).</p>
  <hr />
  <p>Aside from all that, I usually also tend to prefer values that do not have a crazy high magnitude because it makes me feel like I won't have to worry about annoying things like numerical overflow when summing up lots of values from lots of different iterations through the same node.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-21T14:34:52.587Z
Answers.Text: What if you are playing a game where the maximum reward is unbounded or unknown, i.e. when you don't know how to normalize values or Q to, say [-1, 1]?
Answers.UserDisplayName: Darkdragon84
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-21T15:22:42.040Z
Answers.Text: @Darkdragon84 Such a setting is more annoying, but it is possible to work around it by tracking your min/max bounds online, and normalising based on those (also updating by re-normalizing throughout the tree later on if you observe new minima/maxima). This paper has some details (in second-to-last paragraph of Section 4.4): https://jair.org/index.php/jair/article/view/11099
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-21T17:56:35.077Z
Answers.Text: thanks for the quick reply @Dennis Soemers
Answers.UserDisplayName: Darkdragon84
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-01T20:39:14.813Z
Answers.LastActivityDate: 2021-12-01T20:39:14.813Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Usually, when I read about Monte Carlo Tree Search, values between 0 and 1 (or values between -1 and 1) are backpropagated, depending on whether the simulation was a win or loss.</p>
  <p>Now, suppose you have an AI which needs to play a game in which it is also important to score as high as possible. For example, it needs to score as many points as possible in the game of Carcassonne against one other player.</p>
  <p>What kind of options are there for the values being backpropagated in such cases? Can you just backpropagate the number of points, and then, depending on the node, use the points of only the players in UCT? Or would that lead to the search converging to a worse move than the optimal move?</p>
  
Tags: <game-ai><monte-carlo-tree-search><board-games>
Title: Which value to propagate in Monte Carlo Tree Search in a non-zero-sum game?
UserDisplayName: pepijno
ThreadText: # Which value to propagate in Monte Carlo Tree Search in a non-zero-sum game?
  
  (Asked by: username_0 on 2021-12-01)
  
  Usually, when I read about Monte Carlo Tree Search, values between 0 and 1 (or values between -1 and 1) are backpropagated, depending on whether the simulation was a win or loss.
  
  Now, suppose you have an AI which needs to play a game in which it is also important to score as high as possible. For example, it needs to score as many points as possible in the game of Carcassonne against one other player.
  
  What kind of options are there for the values being backpropagated in such cases? Can you just backpropagate the number of points, and then, depending on the node, use the points of only the players in UCT? Or would that lead to the search converging to a worse move than the optimal move?
  
  **Tags:** game-ai, monte-carlo-tree-search, board-games
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-12-01. Score: 3
  
  **In theory: yes, you can backpropagate any sort of scores you want to maximise.** They don't have to be restricted to just a small, discrete set of values such as $\{-1, 0, 1\}$, and also do not have to be in any particular range like $[-1, 1]$ or $[0, 1]$.
  
  However, **in practice it may still be useful if you can normalise whatever "raw" scores you have down to some smaller range** (like the ranges mentioned above). This can **primarily be useful for hyperparameter tuning**. For example, consider the UCB1 equation that we normally use in UCT during tree traversal:
  
  $$a^\* = {\arg\max}\_a \left( Q(s, a) + C \sqrt{\frac{\ln(\sum\_{a'}N(s,a'))}{N(s,a)}} \right).$$
  
  We typically have a $C$ hyperparameter / constant in there, which controls our tradeoff between exploration and exploitation. Higher $C$ means more exploration, lower $C$ means more exploitation. The $Q(s,a)$ term is the average of the scores backpropagated so far for action $a$ in state $s$. In this equation, the $Q(s, a)$ and the $C$ terms are sort of "competing" against each other, so their optimal values are closely related to each other. If you take an existing problem and multiply all the score values by, say, $100$, you'd probably also want to multiply whatever your $C$ constant used to be by $100$ to get the same behaviour again from your tree search.
  
  Actually, what really matters for this story is not even the raw magnitudes of your $Q$ values, but rather the magnitudes of the typical **differences** you see between $Q$ values for different actions in the same state. So, if your problem only has $Q$ values that lie in the range $[99, 101]$, you'll actually want a similar $C$ constant as when you have $Q$ values in the range $[-1, 1]$, but if your problem has $Q$ values in the range $[-100, 100]$, you'll likely want about $100$ times as big a $C$ value too.
  
  If you can roughly normalise your values down to approximately a $[-1, 1]$ or $[0, 1]$ range, you can feel relatively confident that similar kinds of $C$ values as typically used by other people in zero-sum settings will also work fine (like, $C$ values somewhere in the range $[0, 2]$, more often than not below $1$.... but the ideal constant can also very often depend on lots of other factors).
  
  ---
  
  Aside from all that, I usually also tend to prefer values that do not have a crazy high magnitude because it makes me feel like I won't have to worry about annoying things like numerical overflow when summing up lots of values from lots of different iterations through the same node.
  
  > **Comments:**
  > **username_2**: What if you are playing a game where the maximum reward is unbounded or unknown, i.e. when you don't know how to normalize values or Q to, say [-1, 1]?  
  > **username_1**: @username_2 Such a setting is more annoying, but it is possible to work around it by tracking your min/max bounds online, and normalising based on those (also updating by re-normalizing throughout the tree later on if you observe new minima/maxima). This paper has some details (in second-to-last paragraph of Section 4.4): https://jair.org/index.php/jair/article/view/11099  
  > **username_2**: thanks for the quick reply @username_1  
  
  ---
  
  