2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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]? $\endgroup$ Jun 21 at 14:34
  • 1
    $\begingroup$ @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): jair.org/index.php/jair/article/view/11099 $\endgroup$
    – Dennis Soemers
    Jun 21 at 15:22
  • $\begingroup$ thanks for the quick reply @Dennis Soemers $\endgroup$ Jun 21 at 17:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .