In Bandit Based Monte-Carlo Planning by Levente Kocsis and Csaba Szepesvári (2006) they propose the UCT algorithm which is derived from the UCB1 algorithm.

UCB1 algorithm:
$$X_j + \sqrt{\frac{2\ln n}{n_j}}$$

where $X_j$ is the average reward for machine $j$, $n_j$ is number of times $j$ has been played and $n$ is the entire number of games played.

In comparison, UCT is $$\frac{W_i}{n_i} + c \sqrt{\frac{\ln N_i}{n_i}}$$ where $\frac{W_i}{n_i}$ is win:lose ratio (the same as $X_j$),
$c$ is temperature parameter, which is often set to $\sqrt{2}$ (so they just put it in front...)
and $\frac{N_i}{n_i}$ is number of total games played for parent Node / number of games played for the corresponding node, which is the same as $\frac{n}{n_j}$.

So what's new here?


As the authors state in the introduction to their paper, UCT is an application of UCB1 for a specific problem:

The main idea in this paper it to apply a particular bandit algorithm, UCB1 (UCB stands for Upper Confidence Bounds), for rollout-based Monte-Carlo planning. The new algorithm, called UCT (UCB applied to trees) described in Section 2 is called UCT.

It's not the algorithm but the particular application which is new.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.