--- title: Monte Carlo Tree Search module: Tabular Solution Methods moduleNumber: 2 lessonNumber: 12 order: 212 summary: > Monte Carlo Tree Search is a rollout algorithm with memory: it accumulates value estimates across simulations and steers later ones toward promising branches. We work through the four steps — selection, expansion, simulation, backup — the UCT selection rule computed on real numbers, the asymmetric growing tree, and the full pseudocode. We close past Sutton & Barto with the lineage from UCT to AlphaGo, AlphaZero, and MuZero, where a learned network stands in for the leaf value and the rollout. topics: [Tabular Methods] sources: - book: Sutton & Barto ref: "§8.11 Monte Carlo Tree Search" --- This builds on [Decision-Time Planning](/reinforcement-learning/tabular-methods/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.[^sb-mcts] 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 $\varepsilon$-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. $$ % caption: One MCTS iteration. Selection descends the tree by the tree policy to a % leaf; expansion adds a child; simulation rolls out to a terminal state under the % rollout policy; backup carries the return up the traversed tree edges. Iterations % repeat until the move-time budget is spent. \begin{tikzpicture}[>=stealth, font=\small, st/.style={circle, draw, fill=white, minimum size=5.5mm, inner sep=0pt}, stepbox/.style={draw, minimum width=22mm, minimum height=7mm, align=center, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % phase labels across top \node[stepbox] (s1) at (0,4.4) {1. Selection}; \node[stepbox] (s2) at (3.5,4.4) {2. Expansion}; \node[stepbox] (s3) at (7.0,4.4) {3. Simulation}; \node[stepbox] (s4) at (10.5,4.4) {4. Backup}; \draw[->, black] (s1) -- (s2); \draw[->, black] (s2) -- (s3); \draw[->, black] (s3) -- (s4); % Selection \begin{scope}[shift={(0,0)}] \node[st] (r) at (0,3.3) {}; \node[st] (a) at (-0.7,2.2) {}; \node[st] (b) at (0.7,2.2) {}; \node[st] (c) at (0.35,1.1) {}; \draw[acc, thick] (r) -- (b); \draw[acc, thick] (b) -- (c); \draw[black] (r) -- (a); \node[acc, anchor=west, font=\scriptsize] at (0.9,1.6) {tree policy}; \end{scope} % Expansion \begin{scope}[shift={(3.5,0)}] \node[st] (r2) at (0,3.3) {}; \node[st] (b2) at (0.7,2.2) {}; \node[st] (c2) at (0.35,1.1) {}; \node[st, draw=acc, thick] (n2) at (0.7,0.1) {}; \draw[black] (r2) -- (b2); \draw[black] (b2) -- (c2); \draw[acc, thick] (c2) -- (n2); \node[acc, anchor=west, font=\scriptsize] at (0.95,0.1) {new node}; \end{scope} % Simulation \begin{scope}[shift={(7.0,0)}] \node[st] (r3) at (0,3.3) {}; \node[st] (c3) at (0.35,1.1) {}; \node[st] (n3) at (0.7,0.1) {}; \node[draw, fill=black!12, minimum size=4mm, inner sep=0pt] (term) at (0.7,-1.3) {}; \draw[black] (r3) -- (c3); \draw[black] (c3) -- (n3); \draw[acc, dashed, thick, ->] (n3) -- (term); \node[acc, anchor=west, font=\scriptsize] at (0.95,-0.6) {rollout}; \node[anchor=north, font=\scriptsize] at (0.7,-1.5) {terminal}; \end{scope} % Backup \begin{scope}[shift={(10.5,0)}] \node[st] (r4) at (0,3.3) {}; \node[st] (c4) at (0.35,1.1) {}; \node[st] (n4) at (0.7,0.1) {}; \node[draw, fill=black!12, minimum size=4mm, inner sep=0pt] (t4) at (0.7,-1.3) {}; \draw[red, thick, ->] (t4) -- (n4); \draw[red, thick, ->] (n4) -- (c4); \draw[red, thick, ->] (c4) -- (r4); \node[red, anchor=west, font=\scriptsize] at (0.95,1.7) {return}; \end{scope} \end{tikzpicture} $$ 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. $$ % caption: The tree grows asymmetrically. Early iterations expand near the root % (left); high-return branches accumulate visits and keep expanding, so the tree % deepens along promising continuations while poor branches stay shallow (right). \begin{tikzpicture}[>=stealth, font=\small, st/.style={circle, draw, fill=white, minimum size=4.5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % --- early (few iterations) --- \begin{scope}[shift={(0,0)}] \node[font=\footnotesize, anchor=south] at (0,2.0) {after a few iterations}; \node[st] (r) at (0,1.4) {}; \node[st] (a) at (-1.0,0.4) {}; \node[st] (b) at (0,0.4) {}; \node[st] (c) at (1.0,0.4) {}; \draw[black] (r) -- (a); \draw[black] (r) -- (b); \draw[black] (r) -- (c); \end{scope} % --- later (many iterations, deep on one branch) --- \begin{scope}[shift={(5.6,0)}] \node[font=\footnotesize, anchor=south] at (0,2.0) {after many iterations}; \node[st] (R) at (0,1.4) {}; \node[st] (A) at (-1.4,0.5) {}; \node[st, draw=acc, thick] (B) at (0,0.5) {}; \node[st] (C) at (1.4,0.5) {}; \draw[black] (R) -- (A); \draw[acc, thick] (R) -- (B); \draw[black] (R) -- (C); % deep expansion under B \node[st] (B1) at (-0.6,-0.5) {}; \node[st, draw=acc, thick] (B2) at (0.6,-0.5) {}; \draw[black] (B) -- (B1); \draw[acc, thick] (B) -- (B2); \node[st] (B2a) at (0.2,-1.5) {}; \node[st, draw=acc, thick] (B2b) at (1.1,-1.5) {}; \draw[black] (B2) -- (B2a); \draw[acc, thick] (B2) -- (B2b); \node[acc, anchor=west, font=\scriptsize] at (0.7,0.0) {high-return branch}; \end{scope} \end{tikzpicture} $$ ### 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: $$ a \;=\; \arg\max_{a}\;\Bigl[\,Q(s,a) \;+\; c\,\sqrt{\tfrac{\ln N(s)}{N(s,a)}}\,\Bigr]. $$ 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. $$ % caption: The UCT exploration bonus $c\sqrt{\ln N(s)/N(s,a)}$ against the number % of times an action has been tried, $N(s,a)$, at a fixed parent count. It falls % steeply at first and flattens: seldom-tried actions get a large boost, and as an % action accrues visits its selection is governed by its value estimate $Q(s,a)$. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} % axes \draw[->, black] (0,0) -- (6.3,0) node[anchor=north east] {N(s,a)}; \draw[->, black] (0,0) -- (0,3.6); % decreasing curve: bonus ~ 1/sqrt(N) \draw[acc, very thick] (0.5,3.2) .. controls (1.0,2.1) and (1.6,1.55) .. (2.4,1.25) .. controls (3.4,0.92) and (4.6,0.72) .. (6.0,0.62); \node[acc, anchor=west, font=\scriptsize] at (6.05,0.62) {bonus}; % annotations \node[acc, anchor=west, font=\scriptsize] at (0.7,3.15) {large: explore}; \node[black, anchor=south west, font=\scriptsize] at (3.6,0.72) {small: exploit $Q$}; \end{tikzpicture} $$ 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](/reinforcement-learning/foundations/multi-armed-bandits) applied at each internal tree node. > **Definition (UCT tree policy).** At an internal node $s$, select the action > $\arg\max_a \bigl[\,Q(s,a) + c\sqrt{\ln N(s)/N(s,a)}\,\bigr]$, where $Q(s,a)$ is > the mean simulated return through edge $(s,a)$, $N(s)$ and $N(s,a)$ are visit > counts, and $c$ weights exploration. Untried actions (count $0$) are selected > first. ### 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]$). | action | $Q(s,a)$ | $N(s,a)$ | bonus $c\sqrt{\ln 30 / N(s,a)}$ | UCT score | | --- | --- | --- | --- | --- | | $a_1$ | $0.60$ | $20$ | $\sqrt{3.401/20} = 0.412$ | $1.012$ | | $a_2$ | $0.70$ | $8$ | $\sqrt{3.401/8} = 0.652$ | $1.352$ | | $a_3$ | $0.50$ | $2$ | $\sqrt{3.401/2} = 1.304$ | $1.804$ | 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$: $$ \text{UCT}(a_3) = 0.367 + \sqrt{3.434/3} = 0.367 + 1.070 = 1.437, $$ 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. $$ % caption: A UCT selection at a root visited 30 times, c = 1. Each bar is an % action's UCT score, split into its value Q(s,a) (solid) and its exploration % bonus (light). Action a3 has the lowest value but by far the largest bonus (only % 2 visits), so UCT picks it: exploration wins when a promising action is % under-sampled. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \draw[black] (0,0) -- (6.2,0); \node[anchor=east, font=\scriptsize] at (-0.15,0) {0}; % scale: 1 unit score = 2.2 cm \foreach \x/\q/\b/\lab in {0.6/1.32/0.91/a1, 2.6/1.54/1.43/a2, 4.6/1.10/2.87/a3} { % Q part (solid) height = q, bonus stacked on top total = q+b(scaled) -- here q and total precomputed in cm } % a1: Q=0.60 -> 1.32cm, total 1.012 -> 2.23cm \draw[acc, fill=acc] (0.4,0) rectangle (1.1,1.32); \draw[acc, fill=acc!20] (0.4,1.32) rectangle (1.1,2.23); \node[anchor=north, font=\scriptsize] at (0.75,-0.05) {a1}; % a2: Q=0.70 -> 1.54cm, total 1.352 -> 2.97cm \draw[acc, fill=acc] (2.4,0) rectangle (3.1,1.54); \draw[acc, fill=acc!20] (2.4,1.54) rectangle (3.1,2.97); \node[anchor=north, font=\scriptsize] at (2.75,-0.05) {a2}; % a3: Q=0.50 -> 1.10cm, total 1.804 -> 3.97cm (chosen) \draw[red, thick, fill=red!12] (4.4,0) rectangle (5.1,1.10); \draw[red, thick, fill=red!4] (4.4,1.10) rectangle (5.1,3.97); \node[anchor=north, font=\scriptsize, text=red] at (4.75,-0.05) {a3}; \node[red, anchor=south, font=\scriptsize] at (4.75,3.99) {selected}; % legend \node[acc, anchor=west, font=\scriptsize] at (5.6,2.2) {bonus}; \node[acc, anchor=west, font=\scriptsize] at (5.6,0.7) {value Q}; \end{tikzpicture} $$ ### 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. ```algorithm caption: $\textsc{MCTS}(s_0)$ — decision-time planning by growing a search tree from the current state $s_0$ create root node $v_0$ for state $s_0$ while time budget remains do $v \gets v_0$ // Selection: descend by the tree policy (UCT) while $v$ is fully expanded and non-terminal do $v \gets$ child of $v$ maximizing $Q(v') + c\sqrt{\ln N(v)/N(v')}$ if $v$ is non-terminal then // Expansion $v \gets$ new child of $v$ from an untried action $G \gets \textsc{Rollout-Policy-Simulate}(v)$ // Simulation to a terminal state repeat // Backup along the traversed edges $N(v) \gets N(v) + 1$ $Q(v) \gets Q(v) + \dfrac{G - Q(v)}{N(v)}$ // running mean of returns $v \gets$ parent of $v$ until $v$ is above the root return action from $s_0$ with the largest visit count $N$ ``` 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](/reinforcement-learning/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.[^uct] That guarantee is why UCT, rather than plain $\varepsilon$-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.[^alphago] 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.[^alphazero] 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.[^muzero-dt] This is decision-time planning in a learned model: the search of this lesson, run inside a representation the agent learned. $$ % caption: The MCTS lineage. UCT (Kocsis-Szepesvari 2006) supplies the convergent % tree policy; AlphaGo adds value/policy networks in place of the rollout and leaf % heuristic; AlphaZero learns from self-play with one network and a PUCT tree % policy; MuZero plans the same search inside a learned latent model. Each keeps % the four-step selection/expansion/simulation/backup loop. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=26mm, minimum height=9mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \node[box, draw=acc, text=acc, thick] (uct) at (0,0) {UCT\\(convergent tree policy)}; \node[box] (ag) at (3.9,0) {AlphaGo\\(value + policy nets)}; \node[box] (az) at (7.8,0) {AlphaZero\\(self-play, PUCT)}; \node[box, draw=red, text=red] (mz) at (11.7,0) {MuZero\\(learned model)}; \draw[->, thick] (uct) -- (ag); \draw[->, thick] (ag) -- (az); \draw[->, red, thick] (az) -- (mz); \end{tikzpicture} $$ 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. [^sb-mcts]: **Sutton & Barto**, §8.11 — Monte Carlo Tree Search: MCTS as a rollout algorithm with memory, the four steps selection/expansion/simulation/backup (Figure 8.10), tree vs. rollout (default) policy, the UCB/UCT tree policy (Chapter 2), root action by visit count, and the extension to AlphaGo's network-guided search in §16.6. [^uct]: **Kocsis, L., & Szepesvári, C.** (2006), "Bandit Based Monte-Carlo Planning," _ECML_ — UCT: applying the UCB1 bandit rule at each tree node, with a convergence proof that the root value estimate approaches the optimal (minimax) value and the probability of a suboptimal root action tends to zero. [^alphago]: **Silver, D., et al.** (2016), "Mastering the Game of Go with Deep Neural Networks and Tree Search," _Nature_ 529:484–489 (AlphaGo) — MCTS combined with a policy network (move priors) and a value network (leaf evaluation), defeating a professional and then the world champion at Go. [^alphazero]: **Silver, D., et al.** (2018), "A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play," _Science_ 362:1140–1144 (AlphaZero) — self-play with a single value/policy network and a PUCT tree policy, learning Go, chess, and shogi from the rules alone; the search's visit counts serve as the policy-improvement target. [^muzero-dt]: **Schrittwieser, J., et al.** (2020), "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model," _Nature_ 588:604–609 (MuZero) — running AlphaZero-style MCTS over a learned latent dynamics model, planning without access to the environment's true rules and setting records on Atari.