Monte Carlo Tree Search

This builds on Decision-Time Planning, which developed real-time DP, heuristic search, and rollout algorithms — planners that compute one action for the current state and discard the work. Rollouts throw away every simulated trajectory. Monte Carlo Tree Search keeps them, and that one change is what carried computer Go from weak amateur to superhuman.

Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a rollout algorithm with memory. Plain rollouts throw away every simulated trajectory; MCTS accumulates the value estimates from successive simulations and uses them to steer later simulations toward the higher-rewarding parts of the space.¹ It is largely responsible for the improvement of computer Go from a weak amateur level in 2005 to grandmaster (6 dan or more) in 2015, and, combined with a deep neural network, it is the search behind the 2016 AlphaGo victories. It applies to any single-agent sequential problem with a model fast enough for repeated multistep simulation, not only games.

Like any rollout algorithm, MCTS runs after each new state to select the action, is an iterative process that simulates many trajectories from the current state to a terminal state (or until discounting makes further reward negligible), and repeats until a compute budget is spent. Its one addition is the tree. MCTS maintains a tree rooted at the current state, holding Monte Carlo value estimates for the state–action pairs most likely to be reached in a few steps. Any simulated trajectory passes through the tree and then exits it at some leaf. Inside the tree, where it has estimates for at least some actions, MCTS selects with an informed tree policy that balances exploration and exploitation — for example an $\epsilon$-greedy or UCB rule. Outside the tree, and at the leaves, it falls back to the simple rollout policy (the default policy).

The four steps

Each iteration of a basic MCTS consists of four operations, repeated until time runs out.

1. Selection. Starting at the root, a tree policy based on the action values attached to the tree's edges traverses the tree to select a leaf node.
2. Expansion. On some iterations (depending on the application), the tree is expanded from the selected leaf by adding one or more child nodes reached from it via unexplored actions.
3. Simulation. From the selected node — or one of its newly added children — a complete episode is simulated with actions chosen by the rollout policy. The result is a Monte Carlo trial: tree policy inside the tree, rollout policy beyond it.
4. Backup. The return of the simulated episode is backed up to update (or to initialize) the action values on the tree edges the tree policy traversed this iteration. No values are saved for the states and actions the rollout policy visited beyond the tree.

The growing tree

Over many iterations the tree grows unevenly — deeper along branches that keep producing high returns, barely at all along branches that do not. This asymmetric growth is deliberate: MCTS spends its expansions where they matter.

UCT: the tree policy

The tree policy supplies MCTS's exploration–exploitation balance: at each node, prefer actions with good estimates so far, but add a bonus for actions that have barely been tried — a value estimated from two samples is far less reliable than one from two hundred. The most common rule that does this treats each node as a bandit and applies UCT (Upper Confidence bounds applied to Trees), which selects, among the actions available at state $s$, the one maximizing an upper confidence bound:

Here $Q(s,a)$ is the current Monte Carlo estimate (exploitation), $N(s)$ is the number of times $s$ has been visited, $N(s,a)$ the number of times action $a$ was taken from $s$, and $c>0$ tunes the exploration weight. The bonus $c\sqrt{\ln N(s)/N(s,a)}$ is large for actions tried seldom relative to their parent, so it pulls selection toward under-explored actions; as $N(s,a)$ grows, the bonus shrinks and the value term $Q(s,a)$ dominates.

Any action with $N(s,a)=0$ is treated as having infinite bound and is selected first — every action gets tried at least once before the bound refines. This is the UCB1 bandit rule applied at each internal tree node.

A UCT selection, computed

Put real numbers on the bound. Suppose the root $s$ has been visited $N(s)=30$ times and has three actions with the statistics below; take exploration weight $c=1$ (a common choice when returns are scaled to $[0,1]$).

Here $\ln 30=3.401$. The greedy choice by value alone is $a_2$ (highest $Q=0.70$), but UCT selects $a_3$: its low visit count $N=2$ gives it a large exploration bonus $1.304$, enough to overtake the better-valued but well-explored $a_1$ and $a_2$. This is the intended behavior: an action that might be good but has barely been tried is selected for further sampling.

Now suppose the simulation through $a_3$ returns a poor $0.1$, dragging its mean to $Q(a_3)=(0.50\cdot 2+0.1)/3=0.367$ and its count to $3$. Recompute with $N(s)=31$, $\ln 31=3.434$:

while $a_2$'s score rises only slightly to $0.70+\sqrt{3.434/8}=1.355$. So $a_3$ is still selected next — one bad rollout does not eliminate it — but each additional visit shrinks its bonus and sharpens its mean, and after a few more poor returns its score will fall below $a_2$'s and selection will move on. The bound keeps sampling uncertain actions until accumulated evidence, not a single sample, settles their value.

The full algorithm

Putting the four steps and the UCT tree policy together gives the standard decision-time procedure. Each call plans from the current root state and returns the action to play; the environment then advances and the whole thing runs again.

After the budget is exhausted, the agent selects a root action by the accumulated statistics — commonly the action with the largest visit count (robust to outliers) rather than the largest value. The environment transitions to a new state, and MCTS runs again, usually starting from the surviving subtree rooted at the new state (any descendants of the chosen child are reused; the rest is discarded).

Why MCTS works

MCTS's success follows from principles already covered in this course. At its base it is a decision-time rollout algorithm on Monte Carlo control from the root, so it inherits online, incremental, sample-based value estimation and one-step policy improvement. Beyond that, it saves the action-value estimates on the tree edges and updates them with the sample updates of reinforcement learning. By incrementally expanding the tree along high-return trajectories, MCTS effectively grows a lookup table — a partial action-value function — with memory allocated to the state–action pairs in the initial segments of high-yielding sample trajectories. It gets the benefit of a learned $Q$ concentrated where it matters, without approximating a value function globally, and it retains past experience to guide exploration.

From MCTS to AlphaZero

Finally, the leaf evaluation and the rollout policy need not stay simple. Plain MCTS evaluates a leaf by rolling out to termination under a weak default policy — noisy, and only as good as that policy. Replace the rollout with a deep neural network that maps a position to a value estimate $v_{\theta }(s)$ and a policy prior $p_{\theta }(a\mid s)$, and fold that prior into the tree policy (a PUCT-style variant of UCT that biases selection toward high-prior actions), and the search becomes much stronger: the network supplies the leaf values and the move suggestions that make a deep, focused lookahead tractable, while MCTS supplies the lookahead that corrects the network's errors. Train that network by self-play, using the search's own visit counts and game outcomes as targets, and MCTS becomes the search inside AlphaGo and AlphaZero. The full account — the value/policy network, self-play training, and the tree-search integration — is the subject of the deep-RL case studies.

From UCT to AlphaZero and MuZero

The four-step MCTS above is the tabular skeleton; the systems that made it famous are a decade of additions, each traceable to a canonical paper.

UCT. The tree policy this lesson calls UCT is Kocsis and Szepesvári's Upper Confidence bounds applied to Trees, which analyzed MCTS as a nested set of bandit problems and proved that treating each node with the UCB1 rule makes the value estimate at the root converge to the minimax (optimal) value, with the probability of selecting a suboptimal root action going to zero.² That guarantee is why UCT, rather than plain $\epsilon$-greedy, became the default tree policy: it is the reason the asymmetric tree grows toward the right branches.

AlphaGo. Silver and colleagues combined MCTS with two deep networks — a policy network to narrow the search to plausible moves and a value network to evaluate leaf positions without a full rollout — and defeated a professional Go player, then the world champion, on a $19\times 19$ board long thought a decade away from computer mastery.³ The search is the MCTS of this lesson; the networks replace the weak default rollout policy and the hand-built leaf heuristic.

AlphaZero. The successor stripped out every Go-specific component — no human games, no handcrafted features, no separate rollout — and learned from self-play alone, using a single network for both value and policy and folding the policy prior into the tree policy (a PUCT variant of UCT that biases selection toward high-prior actions). One algorithm reached superhuman play in Go, chess, and shogi, each from the rules alone.⁴ The training target is the search's own visit-count distribution, so the network learns to imitate the improved policy the search produced — generalized policy improvement, with MCTS as the improvement operator.

MuZero. The last assumption to fall was the model itself. MuZero learns a latent dynamics model and runs the same MCTS over it, so it plans without ever being told the environment's rules — matching AlphaZero on board games and setting records on Atari, where the rules are not available in closed form.⁵ This is decision-time planning in a learned model: the search of this lesson, run inside a representation the agent learned.

In summary: to act well at a state, a global policy is not always needed. A good action for this state can be computed by looking ahead from it — with asynchronous value iteration on the states actually visited (RTDP), a lookahead tree backed up from leaf estimates (heuristic search), Monte Carlo estimates under a rollout policy (rollouts), or a tree grown asymmetrically toward promising continuations (MCTS). The deeper the lookahead, the less the imperfect value function matters — and with a learned network standing in for both the leaf value and the rollout, that lookahead is what carried reinforcement learning to superhuman play.