Why is there logarithm (and the square root) in the UCB formula of Monte Carlo Tree Search?

Question

I studied Monte Carlo Tree Search (UCT) from several sources, like this: http://www.incompleteideas.net/609%20dropbox/other%20readings%20and%20resources/MCTS-survey.pdf

However, I didn't understand why there is logarithm (and the square root) in the UCB formula of Monte Carlo Tree Search (section 2.4.2 and 3.3.1).

The formula is the following:

Answer 1

The left hand side of the equation is a maximum likelihood estimation, that is it is just a measurement of the viewed win rate for this node and the right hand side is an estimate of uncertainty. The more uncertain we are, the higher we value the node and this promotes exploration.

Ultimately the use of whatever functions comes down to designing the shape of the curve they want to exhibit in their algorithm and how that shape was decided on you'll have to read the literature. If you would like to visualize the shape of the curve you can simply type graph square root of (ln x / y) into google search and it will give you an interactive graph you can inspect.

Logarithms are often used in uncertainty measurements because it's a way of saying each incremental value added has less impact than the one before so as we have more information it changes our estimate less and less which makes sense because the more information we have, the more we trust our estimate is correct.

Square roots do the same thing except to a lesser degree. There is a difference in the shape of the curves between the values of 0 and 1 however. For logarithms, values below 0 are negative, but since it's a logarithm of a count that's never the case. For square roots values increase quickly between 0 and 1 and then slow down their overall increase greatly. Because ln(sp) / si will often have a value between 0 and 1 (anytime si > ln(sp) using a logarithm does not make sense because it would subtract from the value of the estimate and reduce the likelihood we explore that branch!