Rollout

The default policy (or rollout policy) is the simple, fast strategy used to simulate a complete sequence of actions from a given state to a terminal state. Unlike the complex tree policy used for node selection within the search tree, the default policy is computationally cheap, often random or based on simple heuristics.

• Purpose: To provide a rapid, unbiased estimate of a state's value when a deep, analytical search is infeasible.
• Example: In AlphaGo's early versions, the rollout policy was a small linear network trained via supervised learning on expert human games, allowing for thousands of fast simulations per second.

The rollout simulation continues until it reaches a terminal state—a state where the game or task concludes (e.g., win, loss, draw, or a defined end condition). The outcome of this terminal state is then scored to produce a reward or value (e.g., +1 for win, 0 for draw, -1 for loss).

• Backpropagation: This scalar reward is propagated back up the tree, updating the statistics (visit count, total value) of all nodes along the path from the root to the rollout's starting node.
• Value Estimation: The aggregated results of many rollouts from a node provide a Monte Carlo estimate of that node's expected utility, guiding future tree expansions.

Rollouts are inherently stochastic simulations. They sample possible futures by making random or probabilistically guided moves according to the default policy. This randomness is crucial for two reasons:

• Exploration: It ensures the algorithm samples a broad, representative set of possible game trajectories from a node, not just a single deterministic line.
• Variance Reduction: While a single rollout is noisy, the law of large numbers ensures that the average reward from hundreds or thousands of rollouts converges to a robust value estimate for the node.

A core design principle of the rollout phase is computational lightness. The heavy thinking is reserved for the tree search's selection and expansion steps. Rollouts must be fast to allow for a high volume of simulations, which is necessary for accurate value estimation.

• Trade-off: Speed vs. Accuracy. A more sophisticated default policy might yield better individual estimates but would drastically reduce the total number of simulations possible within a fixed time budget.
• Optimization: In high-performance systems like AlphaZero, rollouts were eventually eliminated entirely, replaced by a highly accurate value network. This demonstrates the rollout's role as a computationally efficient estimator that can be superseded by more advanced, learned models.

The rollout is the third step in the four-phase Monte Carlo Tree Search cycle: Selection, Expansion, Simulation (Rollout), and Backpropagation.

1. Selection: Traverse the tree from the root using the tree policy (e.g., UCT) to select a node.
2. Expansion: Add one or more child nodes to the selected node.
3. Simulation (Rollout): From a newly expanded child node (or the selected node if not expanded), run a rollout using the default policy to a terminal state.
4. Backpropagation: Update the node statistics along the traversed path with the rollout's result.

The rollout provides the essential data that fuels the algorithm's learning and guides future tree growth.

It is critical to distinguish the rollout (default) policy from the tree policy. They serve fundamentally different roles within MCTS:

• Tree Policy (e.g., UCT): Used within the constructed search tree. It is explorative and selective, balancing known high-value nodes (exploitation) with less-visited ones (exploration). It dictates how the tree grows.
• Default/Rollout Policy: Used outside the tree, in the unexpanded state space. It is fast and stochastic, designed purely for sampling. It does not involve complex balancing; its goal is to generate a terminal outcome as efficiently as possible to feed back a value estimate.

This separation of concerns is key to MCTS's efficiency: expensive computation is focused on promising parts of the tree (via the tree policy), while vast areas of the state space are cheaply sampled (via rollouts).

Monte Carlo Tree Search is the overarching heuristic search algorithm where a rollout is performed. MCTS builds a search tree incrementally by iterating through four phases: Selection, Expansion, Simulation (Rollout), and Backpropagation. It is renowned for balancing exploration and exploitation, famously powering AI systems like AlphaGo and AlphaZero. The algorithm does not require a domain-specific evaluation function, instead relying on random playouts (rollouts) to estimate state values.

The simulation phase, synonymous with the rollout, is executed using a default policy (also called a rollout policy). This is a fast, often random or simple heuristic strategy that plays the game or sequence of actions from the newly expanded node until a terminal state is reached. The outcome of this simulation (win/loss, final score) provides a stochastic estimate of the value of the starting node. The quality and speed of this policy are critical for the efficiency of the overall MCTS.

Upper Confidence Bound for Trees is the canonical formula used during the Selection phase of MCTS to navigate the tree. It balances two competing goals:

• Exploitation: Favoring nodes with high average reward.
• Exploration: Visiting nodes that have been sampled less frequently. The UCT formula UCT = Q/N + c * sqrt(ln(ParentVisits)/N) guides the search toward promising but underexplored regions, ensuring the rollout budget is allocated intelligently. The constant c controls the exploration weight.

Backpropagation is the final phase of an MCTS iteration. After a rollout completes and a value (e.g., win=1, loss=0) is determined, this result is propagated back up the tree along the path from the expanded node to the root. All nodes on that path have their:

• Visit count (N) incremented.
• Cumulative value (Q) updated with the simulation result. This process gradually improves the value estimates for all nodes in the tree, refining the algorithm's understanding of which moves are strongest.

Temporal Difference (TD) Learning is a foundational reinforcement learning concept related to value estimation. In advanced MCTS implementations, like those in AlphaZero, rollouts are replaced or augmented by value networks—neural networks trained via TD methods. These networks provide a more accurate and sample-efficient state value estimate than a random rollout, dramatically reducing the number of simulations required for strong play.

The planning horizon refers to the depth of future states an agent considers when making a decision. In MCTS, the effective horizon is defined by the length of the rollouts. A short rollout may not reach a true terminal state, requiring a heuristic evaluation. A long rollout provides a direct outcome but is computationally expensive. Managing this trade-off—using truncated rollouts with value function approximation—is key to applying MCTS to complex, long-horizon real-world problems beyond games.