Answers.Body: <p>The answer is somewhat of a puzzle using other neighboring text from the book. We will begin by determining if the selected leaf node is a state leaf node or state-action leaf node through some of the rest of the text:</p>
  <blockquote>
  <ol start="2">
  <li><em>Expansion</em>. On some iterations (depending on details of the application), the
  tree is expanded from the selected leaf node by adding one or more child nodes
  reached from the selected node via unexplored actions.</li>
  </ol>
  </blockquote>
  <p>Since the selected leaf node is connected to a child node <em>through actions</em> (via unexplored actions), it can be inferred that <strong>the selected leaf node is a state leaf node</strong>. Next, we will determine which node in the tree is the selected node.</p>
  <blockquote>
  <ol start="3">
  <li><em>Simulation</em>. From the selected node, or from one of its newly-added child nodes
  (if any), simulation of a complete episode is run with actions selected by the
  rollout policy. The result is a Monte Carlo trial with actions selected first by
  the tree policy and beyond the tree by the rollout policy.</li>
  </ol>
  </blockquote>
  <p>The circled node in the expansion phase tree must be a newly-added child node because it is not present in the selection phase tree. Since this node is the child node of the node circled in the selection phase tree, <strong>the node circled in the selection phase tree must be the selected node</strong> during the selection phase. Therefore, since the text you provided states that the selection phase always selects a leaf node, we conclude that <strong>the authors are calling the circled node in the selection phase tree the selected <em>leaf</em> node</strong>.</p>
  <p>Leaf nodes in tree data structures are usually defined as nodes without children, and <strong>as you mentioned, this seemingly contradicts the notion of the selected node in the tree being called a leaf node</strong>. Other sources use different conventions for designating the selected node which appear to prevent this contradiction. For example, a highly cited survey on MCTS (<a href="https://ieeexplore.ieee.org/abstract/document/6145622" rel="nofollow noreferrer">link</a>) selects the <em>most urgent expandable node</em>. This node does not need to be a leaf since it only needs child nodes not yet present in the tree. In AlphaGo (<a href="https://www.nature.com/articles/nature16961" rel="nofollow noreferrer">link</a>), <em>the selected leaf node does not exist in the tree unless it is a terminal node</em>: the selection phase incorporates a policy that chooses actions until it reaches a node not present in the tree (which must be a leaf node if it were to be added to the tree during the expansion phase) or a terminal node (also a leaf node). The node is added to the tree during the expansion phase if its visit count reaches a prespecified threshold.</p>
  <p>In conclusion, <strong>it seems that using a term such as expandable node is better than leaf node in this section of Sutton &amp; Barto</strong>. My advice is to simply understand the concepts in this section since the exact details of a MCTS are highly dependent on the application at hand.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-16T19:48:52.687Z
Answers.LastActivityDate: 2024-06-16T19:48:52.687Z
Answers.UserDisplayName: DeepQZero
Body: <p><a href="https://i.sstatic.net/e8n9p1nv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/e8n9p1nv.png" alt="enter image description here" /></a></p>
  <blockquote>
  <p>Figure 8.10: Monte Carlo Tree Search. When the environment changes to a new state, MCTS
  executes as many iterations as possible before an action needs to be selected, incrementally building a tree whose root node represents the current state. Each iteration consists of the four operations Selection, Expansion (though possibly skipped on some iterations), Simulation, and Backup, as explained in the text and illustrated by the bold arrows in the trees. Adapted from Chaslot, Bakkes, Szita, and Spronck (2008).</p>
  </blockquote>
  <blockquote>
  <p>In more detail, each iteration of a basic version of MCTS consists of the following four
  steps as illustrated in Figure 8.10:</p>
  <ol>
  <li><em>Selection</em>. Starting at the root node, a tree policy based on the action values attached to the edges of the tree traverses the tree to
  select a leaf node.</li>
  </ol>
  </blockquote>
  <p><strong>Question</strong>: What is a &quot;leaf node&quot; in this context?</p>
  <p>For instance, I'm unsure if a leaf node is a <em>state</em> leaf node or <em>state-action</em> leaf node. If by a leaf node a <em>state</em> leaf node is meant, then the figure on the leftmost is not consistent
  because the root is a state but the last blue node is not a state leaf node because it has a child. On the other hand, if by a leaf node they mean a <em>state-action</em> leaf node, again there is an inconsistency because of two reasons: (i) the root node is not a state-action node (ii) the blue arrows in the leftmost figure do not cover the state-action leaf node.</p>
  
Tags: <reinforcement-learning><monte-carlo-tree-search><sutton-barto>
Title: Confusing convention in Sutto-Barto on Monte Carlo Tree Search: is a leaf node a state leaf node or state-action leaf node?
UserDisplayName: DSPinfinity
ThreadText: # Confusing convention in Sutto-Barto on Monte Carlo Tree Search: is a leaf node a state leaf node or state-action leaf node?
  
  (Asked by: username_0 on 2024-05-27)
  
  [![enter image description here](https://i.sstatic.net/e8n9p1nv.png)](https://i.sstatic.net/e8n9p1nv.png)
  
  > Figure 8.10: Monte Carlo Tree Search. When the environment changes to a new state, MCTS
  > executes as many iterations as possible before an action needs to be selected, incrementally building a tree whose root node represents the current state. Each iteration consists of the four operations Selection, Expansion (though possibly skipped on some iterations), Simulation, and Backup, as explained in the text and illustrated by the bold arrows in the trees. Adapted from Chaslot, Bakkes, Szita, and Spronck (2008).
  
  > In more detail, each iteration of a basic version of MCTS consists of the following four
  > steps as illustrated in Figure 8.10:
  >
  > 1. *Selection*. Starting at the root node, a tree policy based on the action values attached to the edges of the tree traverses the tree to
  >    select a leaf node.
  
  **Question**: What is a "leaf node" in this context?
  
  For instance, I'm unsure if a leaf node is a *state* leaf node or *state-action* leaf node. If by a leaf node a *state* leaf node is meant, then the figure on the leftmost is not consistent
  because the root is a state but the last blue node is not a state leaf node because it has a child. On the other hand, if by a leaf node they mean a *state-action* leaf node, again there is an inconsistency because of two reasons: (i) the root node is not a state-action node (ii) the blue arrows in the leftmost figure do not cover the state-action leaf node.
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, sutton-barto
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-06-16. Score: 1 | Accepted answer
  
  The answer is somewhat of a puzzle using other neighboring text from the book. We will begin by determining if the selected leaf node is a state leaf node or state-action leaf node through some of the rest of the text:
  
  > 2. *Expansion*. On some iterations (depending on details of the application), the
  >    tree is expanded from the selected leaf node by adding one or more child nodes
  >    reached from the selected node via unexplored actions.
  
  Since the selected leaf node is connected to a child node *through actions* (via unexplored actions), it can be inferred that **the selected leaf node is a state leaf node**. Next, we will determine which node in the tree is the selected node.
  
  > 3. *Simulation*. From the selected node, or from one of its newly-added child nodes
  >    (if any), simulation of a complete episode is run with actions selected by the
  >    rollout policy. The result is a Monte Carlo trial with actions selected first by
  >    the tree policy and beyond the tree by the rollout policy.
  
  The circled node in the expansion phase tree must be a newly-added child node because it is not present in the selection phase tree. Since this node is the child node of the node circled in the selection phase tree, **the node circled in the selection phase tree must be the selected node** during the selection phase. Therefore, since the text you provided states that the selection phase always selects a leaf node, we conclude that **the authors are calling the circled node in the selection phase tree the selected *leaf* node**.
  
  Leaf nodes in tree data structures are usually defined as nodes without children, and **as you mentioned, this seemingly contradicts the notion of the selected node in the tree being called a leaf node**. Other sources use different conventions for designating the selected node which appear to prevent this contradiction. For example, a highly cited survey on MCTS ([link](https://ieeexplore.ieee.org/abstract/document/6145622)) selects the *most urgent expandable node*. This node does not need to be a leaf since it only needs child nodes not yet present in the tree. In AlphaGo ([link](https://www.nature.com/articles/nature16961)), *the selected leaf node does not exist in the tree unless it is a terminal node*: the selection phase incorporates a policy that chooses actions until it reaches a node not present in the tree (which must be a leaf node if it were to be added to the tree during the expansion phase) or a terminal node (also a leaf node). The node is added to the tree during the expansion phase if its visit count reaches a prespecified threshold.
  
  In conclusion, **it seems that using a term such as expandable node is better than leaf node in this section of Sutton & Barto**. My advice is to simply understand the concepts in this section since the exact details of a MCTS are highly dependent on the application at hand.
  
  
  ---
  
  