Monte Carlo Tree Search (MCTS) Fundamentals

While model-free methods learn directly from experience, model-based approaches involve learning a model of the environment. Once such a model is available, even an approximate one, how can it be leveraged for decision-making? Monte Carlo Tree Search (MCTS) provides a powerful framework for planning using a generative model or simulator, making it a natural fit for model-based reinforcement learning. MCTS is a heuristic search algorithm that excels in finding optimal decisions in domains defined by states, actions, and rewards, particularly when the state space is large or complex. Its notable success in game playing, particularly AlphaGo's defeat of champion Go players, highlights its effectiveness.

The core idea of MCTS is to simulate many possible future trajectories from the current state and incrementally build a search tree. The statistics gathered from these simulations are used to estimate the long-term value of taking different actions, guiding the search towards more promising parts of the state-action space. This allows MCTS to balance exploration (trying out less-visited actions) and exploitation (focusing on actions that currently look best).

A typical MCTS iteration consists of four steps, repeated many times to build the search tree and refine action value estimates before making a decision:

1. Selection: Starting from the root node (representing the current state), traverse down the existing tree by selecting actions according to a tree policy. This policy aims to balance exploring uncertain branches and exploiting known good ones. A very common tree policy is based on Upper Confidence bounds applied to Trees (UCT). At a state node $s$ in the tree, UCT selects the action $a$ that maximizes:

   $$Q(s, a) + C \sqrt{\frac{\ln N(s)}{N(s, a)}}$$

   Here, $Q(s, a)$ is the current estimated value (average return) of taking action $a$ from state $s$ within the tree, representing the exploitation term. $N(s)$ is the total number of times state $s$ has been visited during the search, and $N(s, a)$ is the number of times action $a$ has been selected from state $s$. The square root term represents exploration, giving a bonus to actions that have been tried less often relative to the parent state visits. $C$ is a constant that controls the degree of exploration. This selection process continues until a leaf node (a node not yet fully expanded or representing a terminal state) is reached.

2. Expansion: If the selected leaf node $s_L$ is not a terminal state and has untried actions, choose one untried action $a$. Use the environment model (either known or learned) to simulate the transition. This involves sampling the next state $s'$ from $P(s' | s_L, a)$ and potentially the reward $R(s_L, a, s')$. Add a new child node representing $s'$ to the tree, connected from $s_L$ via action $a$.

3. Simulation (Rollout): From the newly expanded node $s'$ (or from the selected leaf node $s_L$ if it was terminal or fully expanded), perform a simulation or "rollout". This involves following a default policy (often simple, like random action selection, but potentially more sophisticated) from state $s'$ until a terminal state is reached or a predefined depth limit is hit. The total discounted reward accumulated during this simulation is the outcome, let's call it $G$.

4. Backpropagation (Backup): The result of the simulation, $G$, is used to update the statistics of all nodes visited during the selection and expansion phases (from the new node $s'$ back up to the root). For each state-action pair $(s, a)$ on this path, update its visit count $N(s, a)$ and its value estimate $Q(s, a)$. Typically, $Q(s, a)$ is updated as the running average of the returns $G$ obtained from simulations passing through $(s, a)$:

   $$N(s, a) \leftarrow N(s, a) + 1$$ $$Q(s, a) \leftarrow Q(s, a) + \frac{G - Q(s, a)}{N(s, a)}$$

   The visit count for the parent state $N(s)$ is also incremented.

Visualization of one MCTS iteration. Selection (blue) follows the UCT policy down to node s6. Expansion (red) adds action a1 and state s7. Simulation (green, dashed) runs from s7 yielding return G. Backup (orange, dotted) updates statistics along the selection path using G.

These four steps (Selection, Expansion, Simulation, Backup) are repeated, typically for a fixed computational budget (e.g., number of simulations or time limit). After the search terminates, the action taken from the root node is usually the one with the highest estimated $Q(s_{root}, a)$ value or the highest visit count $N(s_{root}, a)$.

Important MCTS Components

• Search Tree: Stores the explored part of the state-action space. Nodes represent states, and edges represent actions. Statistics ($Q$-values, visit counts $N$) are maintained for nodes or edges.
• Tree Policy (e.g., UCT): Governs action selection within the existing tree during the Selection phase. Its role is important for balancing exploration and exploitation during the search process itself.
• Default Policy (Rollout Policy): Used outside the explicitly expanded tree during the Simulation phase. It needs to be fast to execute, as many rollouts are performed. While a better default policy generally improves MCTS performance, even a random policy can work surprisingly well, as the UCT selection focuses the search effort.
• Environment Model/Simulator: This is the engine MCTS uses for the Expansion and Simulation steps. In model-based RL, this is precisely where the learned transition model $P(s'|s, a)$ and reward function $R(s, a, s')$ come into play. MCTS queries this learned model repeatedly to simulate potential futures.

Characteristics of MCTS

MCTS has several appealing properties:

• Asymmetric Growth: The tree grows unevenly, focusing computational resources on exploring regions deemed more promising by the UCT policy.
• Anytime Capability: The search can be stopped at any point, and the currently best action (based on visit counts or Q-values at the root) can be returned. More computation generally leads to better decisions.
• Model Requirement: It relies on having access to a simulator or a generative model of the environment. This can be the true environment dynamics if known, or, significantly for this chapter, a learned model.

However, it also has considerations:

• Computational Cost: Performing thousands or millions of simulations per decision point can be computationally demanding, especially if the model prediction or simulation step itself is slow.
• Model Dependency: The quality of the plan heavily depends on the accuracy of the model used for simulation. Errors in the learned model can mislead the search.

In the context of model-based RL, MCTS provides a principled way to perform planning using the learned dynamics. Instead of just one-step lookahead or simple trajectory sampling, MCTS performs a more directed, adaptive search deep into the future, leveraging the learned model to evaluate the long-term consequences of actions. The insights gained from MCTS can then be used to select actions directly or to further improve policies or value functions, as we will see when discussing integrations like AlphaZero.