Search and Belief-Space Planning › Tree Search and Monte Carlo Tree Search

Before we can talk about searching over beliefs, we need the mechanics of searching over states. This section builds MCTS from the ground up: what problem it solves, why sampling is a reasonable answer, the four phases of the algorithm, the bandit theory underneath it, and the practical details that separate a working implementation from a minimal one. Even if you never implement MCTS yourself, the concepts here recur throughout the rest of the book: the difference between tree and default policies, the role of exploration bonuses, and the meaning of a backpropagated return. The belief-space algorithm later reuses MCTS selection, simulation, and backup, and adds history-indexed observation branching plus latent-state sampling from the current belief.

Recall from Markov and Partially Observable Decision Processes that a Markov decision process is a tuple $(S, A, P, R, \gamma)$, where $S$ is the state space, $A$ the action space, $P(s' \mid s, a)$ the transition kernel, $R(s, a)$ the reward, and $\gamma \in [0, 1)$ the discount factor. For the finite discrete case used below, the optimal value function satisfies the Bellman optimality equation:

$$V^*(s) = \max_{a \in A} \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^*(s') \right]$$

where:

• $V^*(s)$: the maximum expected discounted return obtainable from state $s$
• $R(s,a)$: the expected immediate reward for taking action $a$ in state $s$
• $P(s' \mid s,a)$: the probability of successor state $s'$ under the transition model
• $\gamma \in [0,1)$: the discount factor

If you can evaluate the right-hand side exactly, you can solve for $V^*$ by dynamic programming, as we did for the grid world in Classical Planning and Optimal Control. An exact tabular solution requires enumerating $S$ and iterating until convergence, and both scale badly. For factored state variables, the number of joint assignments grows exponentially; a few dozen binary features already yield billions of states, while a continuous space cannot be tabulated at all. But there is a second way to use the Bellman equation: not to solve for the whole function $V^*$, but to answer a single question about a single state. Given a state $s$, which action $a$ maximizes the right-hand side?

That reframing is the key move. You do not need to know $V^*$ everywhere. You need to know it at the states that arise from your current situation, and ideally only at those. Everything MCTS does follows from taking that observation seriously. The value function is a book with pages for every state in the world, most of which you will never read; MCTS is a procedure for reading only the pages you need. It is guided by the assumption that you do not need many of them.

The naive way to exploit it is a depth-limited expectimax tree. From the root state $s_0$, expand every action, then every successor with nonzero probability, then every action from there, and so on to depth $d$. If each state has $b_A$ available actions and each state-action pair has at most $b_S$ possible successors, the tree can have $(b_A b_S)^d$ leaves. In a deterministic 6-by-6 grid, $b_S=1$ and four actions already produce $4^{20} \approx 1.1 \times 10^{12}$ length-20 action sequences before transpositions or pruning. Even this tiny domain therefore yields roughly a trillion candidates, each of which requires model transitions and value bookkeeping rather than a single machine instruction. The point is not merely that we need a faster computer; uniform enumeration spends its effort in the wrong shape for this problem.

MCTS addresses this by refusing to build the tree uniformly. Instead of expanding every branch to depth $d$, it runs a fixed number of simulations, each of which walks from the root down to a leaf along a policy that balances exploitation of branches with strong sampled returns against exploration of under-sampled ones, evaluates the leaf cheaply, and then updates statistics along the visited path. The represented tree is therefore usually asymmetric. Its exact shape reflects the selection rule, the rollout or leaf evaluator, the model, and the finite budget; an initially misleading estimate can direct substantial work toward a poor branch before later evidence corrects it.

Each MCTS simulation executes four phases in sequence.

1. Selection. Starting at the root, repeatedly choose the child that maximizes the tree policy. The tree policy is what makes MCTS work, and we will spend most of this section on it. Selection stops when you reach a node that has not been fully expanded, or a terminal node. Because each step of selection moves one level down the tree, a single simulation visits $O(\text{depth})$ nodes, and the tree policy is consulted at each one.

2. Expansion. If the selected node is not terminal and has unexpanded actions, add one or more children. A common choice is to add all $|A|$ children at once and mark the node fully expanded. You can also add children lazily, one per visit; this matters when $|A|$ is large, and we will return to it. When child creation evaluates the model, eager expansion can require up to $|A|$ model queries, many for children that may never be revisited. Laziness delays that work until a child is needed.

3. Simulation (rollout). From the newly created node, simulate a trajectory using some default policy, such as uniform random actions or a cheap heuristic, until you hit a terminal state or a depth limit. Sum the discounted rewards to get a return estimate $G$. In rollout-based MCTS, this phase evaluates what lies beyond the explicit tree; other variants use a learned or heuristic leaf evaluator instead. A random default policy often produces noisy leaf values, while an accurate goal-directed heuristic can reduce that variance.

4. Backpropagation. Walk back up the path you came down, incrementing visit counts $N$ and updating the running mean return $Q$ at each visited node or edge. Every visited ancestor receives an update on that simulation; the update does not guarantee that its finite-sample estimate becomes more accurate.

The distinction between the tree policy (used during selection, inside the tree) and the default policy (used during simulation, outside the tree) is central. The tree policy can afford more computation per decision because it is applied only along the explicit-tree prefix and its job is to allocate future simulations well. The default policy is applied throughout the remaining rollout for every simulation, so its cost is multiplied across many simulated steps. The useful balance depends on depth, branching, simulator cost, and how much a better tree or default policy changes return variance and action ranking.

The tree policy treats action selection at each node like a multi-armed bandit problem. Each selected edge produces a sampled downstream return, and the selection rule balances exploiting actions with high observed returns against exploring actions with little evidence. A canonical rule is UCB1 (Auer, Cesa-Bianchi, and Fischer, 2002):

$$a^* = \arg\max_{a} \left[ \bar{Q}(s, a) + c \sqrt{\frac{\ln N(s)}{N(s, a)}} \right]$$

where:

• $\bar{Q}(s,a)$: the running mean return observed when action $a$ was tried from $s$
• $N(s)$: the number of times node $s$ has been visited
• $N(s,a)$: the number of times action $a$ has been tried from $s$
• $c$: the exploration constant controlling the size of the uncertainty bonus

The expression is evaluated only after every available action has been visited at least once; implementations usually force unvisited actions to be selected before applying it. Read the score as a conversation between two terms. The first term, $\bar{Q}(s,a)$, is exploitation: it prefers actions that have paid off so far. The second term is exploration: it grows when $N(s,a)$ is small relative to $N(s)$, so an action that has rarely been tried gets a large bonus. The logarithm in the numerator means the bonus grows slowly. Kocsis and Szepesvári (2006) applied upper-confidence selection recursively in a search tree and called the result UCT. They proved consistency for the finite-horizon and discounted MDP settings analyzed in their paper; the result depends on bounded rewards, a correct generative model, and sufficient exploration.

The bonus has the shape of a concentration bound. In the stationary bandit setting used to derive UCB1, uncertainty shrinks roughly as $1/\sqrt{N(s,a)}$, while the $\ln N(s)$ term makes an under-sampled action eligible again as the parent is revisited. The coefficient $c$ absorbs the reward range and the desired confidence level. Recursive tree search is more delicate than an independent stationary bandit at every node because the return distribution changes as policies deeper in the tree change. UCT's consistency analysis handles that coupling under its stated assumptions; the single-node UCB1 regret guarantee should not be copied to every node without those conditions.

UCT has one important weakness for our purposes. The exploration bonus has no place to insert side information about which actions are likely to be good. If a learned policy assigns most of its probability to one action, plain UCT does not use that ranking: it normally gives every legal action an initial visit and then allocates later visits from sampled returns and counts alone. With hundreds of legal moves, those mandatory first visits can consume much of a small simulation budget even when a useful prior is available.

PUCT fixes this by multiplying the exploration term by a prior $P(s,a)$:

$$a^* = \arg\max_{a} \left[ \bar{Q}(s,a) + c \, P(s,a) \frac{\sqrt{N(s)}}{1 + N(s,a)} \right]$$

where:

• $P(s,a) \in [0,1]$: the action prior, normally produced by a policy network, indicating how promising action $a$ looks before any search statistics are collected
• $c > 0$: PUCT's exploration coefficient, playing the same qualitative role as the UCB coefficient (though the two formulas have different scales, so their numerical values are not interchangeable)

The denominator $1 + N(s,a)$ makes the prior-weighted bonus decay relative to repeated visits to the same action. AlphaGo and AlphaZero use closely related prior-guided tree policies, with implementation-specific coefficients and root exploration. We will return to that design in the final section and in MuZero and Value-Equivalent Models.

The PUCT score combines three signals. The prior $P(s,a)$ says how promising the action looks before search at this node. The running mean $\bar{Q}(s,a)$ summarizes sampled returns, and $N(s,a)$ records how often the edge has been visited. High-prior actions receive a larger early exploration bonus; repeated visits reduce that bonus relative to alternatives. A positive prior and continued exploration can let later return evidence override an imperfect ranking. A zero prior is different: in the displayed formula it gives no exploration bonus, so implementations commonly add root noise, probability floors, or forced initial visits. PUCT is a knowledge-guided selection rule, not a general guarantee of using fewer simulations than UCT.

When a simulation returns a discounted return $G_{\text{rollout}}$ from the leaf, that value is the return from the leaf. But the node statistics you need to update are indexed by the path from the root. If the path is $n_0 \to n_1 \to \cdots \to n_k$ and $r_i$ is the reward received when entering node $n_i$, then the return from node $n_i$ is defined recursively:

$$\begin{aligned} G_k &= G_{\text{rollout}} \\ G_{k-1} &= r_k + \gamma G_k \\ G_{k-2} &= r_{k-1} + \gamma G_{k-1} \\ &\;\;\vdots \\ G_i &= r_{i+1} + \gamma G_{i+1} && \text{(general recursive step)} \end{aligned}$$

where:

• $G_i$: the return backed up to node $n_i$, obtained by working backward from the leaf
• $r_{i+1}$: the reward on the transition from $n_i$ to $n_{i+1}$
• $\gamma$: the discount factor
• $G_{\text{rollout}}$: the leaf evaluation or remaining rollout return at node $n_k$

Working backward along the path and adding each corresponding $G_i$ to node $n_i$ gives the correctly indexed discounted sample return. Backing up the root return unchanged to every node instead shifts the reward timing and biases deeper-node estimates. This matters because selection compares deeper-node values against each other, and a systematic shift in those values biases the search. A buggy implementation can still populate a tree and sometimes reach the goal, so the defect may surface as inefficient allocation or different action choices rather than a crash.

Once you have them, the node statistics are simple running averages:

$$\bar{Q}(n, a) = \frac{1}{N(n,a)} \sum_{i\,:\, (n,a) \in \text{path}_i} G^{(i)}_{n}$$

where:

• $N(n,a)$: the number of simulations in which action $a$ was taken from node $n$
• $G^{(i)}_{n}$: the discounted return from node $n$ recorded on simulation $i$
• the sum runs over simulations $i$ whose selected path passed through the edge $(n,a)$

This estimator is a sample mean of returns generated by the search procedure; it is not automatically an unbiased estimate of $Q^*(s,a)$. The tree policy and leaf evaluation change as the tree grows, so the samples are neither identically distributed nor drawn from the final policy. Uneven action sampling alone does not bias the conditional mean for an edge, but adaptive downstream policies, finite horizons, and approximate leaf values can. Treat a finite-budget MCTS $Q$ as a search statistic tied to a particular algorithm and budget, not as a calibrated critic unless calibration is checked separately.

When the budget runs out, you need to pick an action. Two options:

• Most-visited child. Return $\arg\max_a N(s, a)$. This convention reports which action received the largest allocation under the configured tree policy and budget.
• Highest-value child. Return $\arg\max_a \bar{Q}(s,a)$. This convention reports the largest sampled mean and can be sensitive to actions supported by very few visits.

Many implementations choose the root action by visit count while using value estimates inside the tree. Both statistics reflect returns propagated through a subtree, but they answer different questions. $\bar{Q}(s,a)$ is the observed mean for one edge; $N(s,a)$ records how often the selection rule returned to that edge after comparing it with alternatives. A high value supported by two visits is fragile, while a large visit count can still be wrong when the prior, exploration rule, or model is biased. Visit count is an allocation statistic, not a calibrated confidence probability.

The visit distribution at the root can itself serve as a policy or a policy-training target. AlphaZero uses $\pi(a) \propto N(s_0,a)^{1/\tau}$ as a search-policy target, where $\tau$ is a temperature. If a search allocates 80% of its simulations to one action, that is a strong preference under that search configuration and budget. We will exploit this in the Policies Learned in Imagination chapter. The temperature $\tau$ controls how sharp the distribution is: at $\tau = 1$ you take the raw visit proportions, at $\tau \to 0$ you get a one-hot distribution when the most-visited action is unique (ties require an explicit rule), and larger $\tau$ flattens the distribution. A training scheme may use a higher temperature while collecting exploratory data than at deployment, but the schedule is a design choice rather than a property of MCTS itself.

The scheme above assumes that expanding a node means adding all $|A|$ children. That can be manageable when $|A|$ is four and each child is cheap to instantiate. It is impossible to enumerate when $A$ is a continuous set, such as a bounded subset of $\mathbb{R}^7$, and costly when the discrete action set contains hundreds of moves. Progressive widening (Coulom, 2007; later refined by Auger, Couëtoux, and Teytaud, 2013) limits the number of instantiated children after $N$ visits to

$$k(N) = \lceil c_w N^{\alpha} \rceil$$

where:

• $k(N)$: the number of children the node is allowed to have at visit count $N$
• $c_w > 0$: the widening constant that sets the overall rate of growth
• $\alpha \in (0,1)$: the widening exponent controlling how quickly the child budget broadens

The constants are problem-dependent; $\alpha=0.5$ is a common starting point, not a universal default. Early visits instantiate few children and go deep; later visits broaden as the budget grows. POMCPOW (Sunberg and Kochenderfer, 2018) applies progressive widening to sampled actions and observations so a finite search tree can be used in continuous spaces. Widening does not by itself ensure that an optimal continuous action is ever sampled. That conclusion additionally requires an action proposal with suitable support and regularity assumptions. The practical tradeoff is depth against coverage: a slow schedule gives each instantiated child more visits, while a fast schedule covers more candidates with fewer samples per child.

Let us now build the MCTS algorithm. The first cell binds shared plot-style helpers alongside computation imports. Figure construction remains in the later visualization cells, while arrays and statistics are prepared beforehand.

The left panel shows that repeated closed-loop search reaches the goal in this seeded run: the guided rollout follows the ten-step route, while the uniform rollout takes thirteen steps. The right panel explains why this one trajectory should not be mistaken for a well-resolved root estimate. The 400-simulation search spreads visits nearly evenly, including across the two wall-bumping actions. Closed-loop replanning recovers a useful action sequence here even though each individual uniform-rollout search remains uncertain. Read visits and values together: the visit count records the selection rule's allocation, while the value is the sampled mean return on an edge. Neither is a calibrated confidence measure.

We can compare finite-budget root estimates under uniform and guided rollouts. The experiment below measures absolute error relative to $V^*(\text{START})$ over eight seeds. It tests these two implementations on this maze; it does not establish a general sample-complexity result.