What should the initial UCT value be with MCTS, when leaf's simulation count is zero? Infinity?

Question

I am implenting a Monte Carlo Tree Search algorithm, where the selection process is done through Upper Confidence Bound formula:

def uct(state):
        log_n = math.log(state.parent.sim_count) 
        explore_term = self.exploration_weight * math.sqrt(log_n / state.sim_count)
        exploit_term = (state.win_count / state.sim_count)

        return exploit_term + explore_term

I have trouble however choosing the initial value for UCT, when the sim_count of the node is 0. I tried with +inf (which would be appropriate as approaching lim -> 0 from the positive side would give infinity), but that just means the algorithm will be always choosing an unexplored child.

What would you suggest as a initial value for the uct?

Thank you in advance!

Answer 1

Assigning a value of $\infty$ to unvisited nodes is indeed the "default" or most basic choice, and it indeed ensures that the search never visits a node for a second time if it also still has siblings that have not had any visits. But many other kinds of values have been tried in the literature too.

Gelly and Wang, in "Exploration exploitation in Go: UCT for Monte-Carlo Go" referred to the parameter as "First-play Urgency" (FPU), and indeed really treated it as a hyperparameter; they simply tried various different values and some were found to work better than others.

Other more specific values that you may want to consider (but in most cases we can't really say much about which one will be better than which other ones, without empirical evaluations) are:

• The value of a loss; treating nodes that have not had any visits as losing nodes is probably the most "pessimistic" initialisation you could pick. It's not very clearly described in the papers, but there is some evidence out there that this was used by AlphaGo Zero and AlphaZero. Those are not simply vanilla UCTs though, those programs had very strong trained Deep Neural Networks to make additional recommendations for actions. If you don't have such strong neural networks to introduce additional biases in your selection, I would not recommend treating unvisited nodes as losing nodes.
• The value of a draw; treating unvisited nodes as draws means that you may prioritise re-visiting nodes that look like winning nodes, but you won't prioritise re-visiting nodes that look like losing nodes.
• The value of a win; this probably produces similar behaviour in practice as a value of $\infty$
• The average value backpropagated into the parent (correcting for differences in player-colour-to-move); you may prioritise re-visiting nodes that perform better than average in this subtree, but won't prioritise re-visiting nodes that perform worse than average in this subtree