Correctly selecting best possible branch? about mcts

[esparano]

I haven't experienced this, but there is another open issue with a possible implementation bug. It could be related.

A few other issues could be at fault. Are your custom rewards small, say in the range [-1, 1]? If not, the ratio between exploration-const and typical reward magnitude needs to be kept roughly the same.

[DarioBernardo]

Hi, and thanks for your response.
My reward is a score, like in a video game, and starts from 0 with no upper bound, but generally a typical value would be between 0 and let's say 1000000. Does it mean that the exploration value must me in the same range? I actually tried that and you are right, it actually mitigated the problem. I have more visits in the less promising branch now, and at least it is not just 1. Also the game is more stable.
Could you also point me to the open issue with a possible implementation bug you are referring to in your response, so I can have a look?
thank you

[esparano]

Hi Dario,

The open issue I referenced is #6. I don't think it's related to your exploration issue, but it can potentially affect multi-player games.

If your values can be as high as 1M, then it makes sense why only one branch is being explored. Check out the code that chooses which branch to explore:

MCTS/mcts.py

Line 98 in 366972d

nodeValue = child.totalReward / child.numVisits + explorationValue * math.sqrt(

Because totalReward is so high, the exploration component of the equation is mostly ignored.

There are two possible solutions I can recommend:

1. Increase explorationValue until it's in roughly the same range as a typical reward (then tweak it by up to an order of magnitude until you're getting good results).
2. Rework your reward function to return a value in a more reasonable range. Perhaps you simply divide your reward by 100k before returning it. Or perhaps you could apply a more complicated function like log or arctan to the reward. Some implementations even pass the game state through a neural network before returning a confidence value between [-1, 1]! There are a lot of options here.