Answers.Body: <p>First explore the nodes A,B,C once.</p>
  <p>For reference see this paper by David Silver and Sylvain Gelly, <a href="https://www.researchgate.net/publication/29651027_Combining_Online_and_Offline_Knowledge_in_UCT" rel="nofollow noreferrer">Combining Online and Offline Knowledge in UCT</a></p>
  <blockquote>
  <p>If any action from the current state <span class="math-container">$s$</span> is not represented in the tree, <span class="math-container">$\exists a \in \mathcal{A}(s),(s, a) \notin \mathcal{T},$</span> then the uniform random policy <span class="math-container">$\pi_{\text {random }}$</span> is used to select an action from all unrepresented actions, <span class="math-container">$\tilde{\mathcal{A}}(s)=\{a \mid(s, a) \notin \mathcal{T}\}$</span>.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T13:17:30.450Z
Answers.LastActivityDate: 2021-02-10T13:48:37.377Z
Answers.LastEditDate: 2021-02-10T13:48:37.377Z
Answers.UserDisplayName: Cohensius
Body: <p>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</p>
  <p><span class="math-container">$$\frac{w_i}{n_i}+c\sqrt{\frac{ln(t)}{n_i}},$$</span></p>
  <p>where</p>
  <ul>
  <li><span class="math-container">$w_i$</span>= number of wins after i-th move</li>
  <li><span class="math-container">$n_i$</span> = number of simulations after the i-th move</li>
  <li><span class="math-container">$c$</span> = exploration parameter (theoretically equal to <span class="math-container">$\sqrt{2}$</span>)</li>
  <li><span class="math-container">$t$</span> = total number of simulations for the parent node</li>
  </ul>
  <p>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<span class="math-container">$=1+\sqrt(2)\sqrt{\frac{ln(1)}{1}}$</span>, 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 <span class="math-container">$&gt; 0$</span> 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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-10T18:33:03.970Z
Comments.Text: 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](https://ai.stackexchange.com/a/26315/1641)
Comments.UserDisplayName: Dennis Soemers
Tags: <monte-carlo-tree-search><upper-confidence-bound>
Title: How UCT in MCTS selection phase avoids starvation?
UserDisplayName: user8714896
ThreadText: # How UCT in MCTS selection phase avoids starvation?
  
  (Asked by: username_0 on 2021-02-10)
  
  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.
  
  **Tags:** monte-carlo-tree-search, upper-confidence-bound
  
  > **Comments:**
  > **username_1**: 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 [username_2' answer](https://ai.stackexchange.com/a/26315/1641)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-02-10. Score: 2 | Accepted answer
  
  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](https://www.researchgate.net/publication/29651027_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}\}$.
  
  
  ---
  
  