Expansion (MCTS Phase)

The core function of expansion is to enumerate the legal actions available from the leaf node's state. This creates the set of potential child nodes.

• In a board game like Go, this involves listing all empty intersections.
• For a planning agent, it involves listing all valid API calls or sub-task initializations.
• The complexity of this enumeration directly impacts the branching factor of the search tree.

A critical technique for managing large or continuous action spaces. Instead of expanding all legal actions at once, the algorithm gradually adds child nodes as the parent node is visited more.

• A common rule: only add a new child when visit_count(parent) ^ (1/expansion_coefficient) increases.
• This prevents the tree from becoming impractically wide early in the search, focusing computational budget on the most promising branches first.
• It is essential for scaling MCTS to real-world problems like robotic motion planning or chemical design.

In advanced architectures like AlphaZero, expansion is guided by a neural network. When a new child node is created for action a, it is initialized with:

• Prior Probability (P(s, a)): A value from the network's policy head, estimating the likelihood that a is the best move from state s. This biases future selection.
• Initial Value Estimate: Often set to the network's value head output for the parent state or zero, to be updated during backpropagation.
• This replaces random or uniform initialization, dramatically increasing search efficiency.

A design choice in the MCTS loop: how many child nodes to add per iteration.

• Standard Single Expansion: Adds one child node per iteration (the first unvisited action from the selected leaf). This is the classic approach.
• Multiple Expansion: Adds all unvisited child nodes at once. This can speed up initial exploration but increases memory usage and may lead to a less focused search if not paired with strong priors.
• The choice affects the trade-off between breadth and depth of exploration in the early stages.

Expansion is skipped if the selected leaf node is a terminal state (e.g., game over, goal achieved).

• The algorithm proceeds directly to the Simulation phase, which in this case is a null operation, and then Backpropagation with the terminal reward.
• Correct detection of terminal states is crucial to avoid attempting illegal expansions and to ensure value estimates are accurate.
• In adversarial settings, the terminal reward is often +1 (win), 0 (draw), or -1 (loss).

In AlphaZero and MuZero, expansion is deeply integrated with learned models.

• AlphaZero: The network suggests priors P(s, a) and a value v for the current state s during expansion.
• MuZero: The network's dynamics function is used. After choosing an action a to expand, the function predicts the next latent state s' and immediate reward r. The new child node represents this predicted state s'.
• This allows planning in environments where the true rules (transition model) are unknown, using the learned model as a substitute.

Selection is the phase immediately before Expansion, where the algorithm traverses the existing tree from the root to a leaf node. It uses a tree policy, most commonly the Upper Confidence Bound for Trees (UCT), to balance exploring less-visited paths and exploiting paths with high estimated value. The chosen leaf node becomes the target for the subsequent Expansion phase.

Simulation, or rollout, is the phase that follows Expansion. Starting from the newly added child node (or the selected leaf if expansion was skipped), a fast playout policy (often random) is used to simulate a trajectory to a terminal state. The outcome of this simulation (win/loss, score) is the sample used to evaluate the expanded node's potential.

Progressive widening is a critical technique for managing Expansion in domains with vast or continuous action spaces. Instead of expanding all possible actions at once, the algorithm gradually increases the number of child nodes for a parent node as its visit count grows. This ensures computational resources are focused on promising areas of a large search space.

• Key Mechanism: The number of children considered is a function f(N), where N is the parent's visit count.
• Use Case: Essential for robotics planning, continuous control, and games with many legal moves.

UCT is the canonical formula that guides the Selection phase, directly influencing which leaf node is chosen for Expansion. It balances:

• Exploitation: Favoring children with a high average reward.
• Exploration: Favoring children that have been visited less frequently.

The selected node's statistics, updated via Backpropagation, determine the UCT values for future selections, creating a feedback loop that efficiently grows the tree.

In advanced architectures like AlphaZero, the Expansion phase is guided by a neural network. When a leaf node is selected for expansion, a policy network suggests a probability distribution over possible actions, and a value network provides an initial estimate of the state's worth. This replaces random or heuristic-based expansion, allowing the algorithm to build a much more informed and efficient search tree from the outset.

Understanding these two policies is essential for differentiating the Expansion and Simulation phases.

• Tree Policy: Used during Selection and Expansion. It is computationally expensive and aims for optimal growth of the search tree (e.g., UCT). It decides which nodes to add to the tree.
• Playout Policy: Used during Simulation. It is designed to be very fast to allow many rollouts. It decides how to simulate from an expanded node to a terminal state, often using random actions or a simple heuristic.