3
$\begingroup$

The first step of MCTS is to keep choosing nodes based on Upper Confidence Bound applied to trees (UCT) until it reaches a leaf node where UCT is defined as

$$\frac{w_i}{n_i}+c\sqrt{\frac{ln(t)}{n_i}},$$

where

  • $w_i$= number of wins after i-th move
  • $n_i$ = number of simulations after the i-th move
  • $c$ = exploration parameter (theoretically equal to $\sqrt{2}$)
  • $t$ = total number of simulations for the parent node

I don't really understand how this equation avoids sibling nodes being starved, aka not explored. Because, let's say you have 3 nodes, and 1 we'll call it node A is chosen randomly to be explored, and just so happens to simulate a win. So, node A's UCT$=1+\sqrt(2)\sqrt{\frac{ln(1)}{1}}$, while the other 2 nodes UCT = 0, because they are unexplored and the game just started, so by UCT the other 2 nodes will never be explored no? Because after this it'll go into the expansion phase and expansion only happens it reaches a leaf node in the graph. So because node A is the only one with a UCT $> 0$ it'll choose a child of node A and it will keep going down that node cause all the siblings of node A have a UCT of 0 so they never get explored.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Note that for those 2 unvisited nodes in your example, we do not have UCT = $0$. It's technically undefined (due to a division by $n_i = 0$), but if we want to pretend that division by $0$ isn't undefined, the most "sensible" value to assign to it would probably be $\infty$ (infinity). And if you assume that all unvisited nodes have a value of $\infty$, you basically arrive at Cohensius' answer $\endgroup$
    – Dennis Soemers ♦
    Commented Feb 10, 2021 at 18:33

1 Answer 1

Reset to default
2
$\begingroup$

First explore the nodes A,B,C once.

For reference see this paper by David Silver and Sylvain Gelly, Combining Online and Offline Knowledge in UCT

If any action from the current state $s$ is not represented in the tree, $\exists a \in \mathcal{A}(s),(s, a) \notin \mathcal{T},$ then the uniform random policy $\pi_{\text {random }}$ is used to select an action from all unrepresented actions, $\tilde{\mathcal{A}}(s)=\{a \mid(s, a) \notin \mathcal{T}\}$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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