Planning and Monte-Carlo Tree Search

A planning problem, in the sense used here, assumes an agent has a model of the environment — a function or simulator that, given a state and an action, returns a next state (and reward), possibly stochastically. This is the model-based setting: instead of learning a policy from real experience, the agent can query the model as many times as it likes to think ahead before acting, exactly as in Model-Based Reinforcement Learning. The difficulty is that for problems with large branching factor $b$ and depth $d$, the full tree has $O(b^d)$ nodes, which is infeasible to enumerate exhaustively even for modest $b$ and $d$.

Monte-Carlo Tree Search addresses this by building a partial search tree incrementally, using repeated simulated episodes ("rollouts") from the current state. Each simulation is a complete trajectory to a terminal state (or a fixed horizon) sampled using the model. The key design choice is that the tree is asymmetric: it is expanded most in the parts of the state space that appear most rewarding, and expanded conservatively — but never entirely ignored — elsewhere. This is achieved by treating every internal node of the tree as a multi-armed bandit problem, where the "arms" are the legal actions from that state, and the reward of pulling an arm is the outcome of a simulated trajectory that starts by taking that action. The bandit view motivates the UCT algorithm (Upper Confidence bounds applied to Trees), which selects, at each tree node, the action maximizing

where $Q(s,a)$ is the average simulated return after taking action $a$ from state $s$, $N(s)$ is the number of times $s$ has been visited, $N(s,a)$ is the number of times $a$ was chosen at $s$, and $c$ is an exploration constant. The first term favors actions with high estimated value (exploitation); the second term favors actions tried rarely relative to their parent (exploration), and shrinks as $N(s,a)$ grows. This formula is derived directly from the UCB1 bandit algorithm, applied recursively at every node encountered along a simulated trajectory — hence "Trees."

MCTS proceeds by running many iterations, each consisting of four phases, until a computational budget (time or number of simulations) is exhausted. It then commits to an action at the root, typically the one with the highest visit count (more robust than raw average value, since visit count reflects sustained confidence).

1. Selection. Starting at the root, repeatedly apply the UCT rule to descend into the tree, choosing the child with highest UCT score, until reaching a node that is not fully expanded (has an untried action) or is a terminal state.

2. Expansion. If the reached node is non-terminal and has untried actions, add one new child node to the tree corresponding to one such action.

3. Simulation (rollout). From the newly added node, simulate the rest of the episode using a fast default policy — often uniformly random action choices, or a lightweight heuristic — without adding further nodes to the tree, until a terminal state or horizon is reached, yielding a return.

4. Backpropagation. Propagate the simulation's return back up through every node visited during selection and expansion, incrementing each visit count and updating each node's average value estimate. ```pseudocode function MCTS(root_state, num_iterations, c): root ← new Node(state = root_state, parent = null) for i in 1 .. num_iterations: node ← root

# 1. SELECTION: descend using UCT until a node with

# untried actions or a terminal state is reached while node.is_fully_expanded() and not node.is_terminal(): node ← select_child_UCT(node, c)

# 2. EXPANSION: add one untried child, if possible if not node.is_terminal() and not node.is_fully_expanded(): action ← node.pick_untried_action() next_state ← model.step(node.state, action) child ← new Node(state = next_state, parent = node, action = action) node.children.append(child) node ← child

# 3. SIMULATION: rollout to a terminal state / horizon return_value ← rollout(node.state, default_policy, model)

# 4. BACKPROPAGATION: update statistics along the path while node is not null: node.N ← node.N + 1 node.W ← node.W + return_value node.Q ← node.W / node.N return_value ← discount(return_value) # if using a discount factor node ← node.parent

# After the budget is exhausted, choose the root's best action return argmax_a root.children[a].N # robust child: most-visited action

function select_child_UCT(node, c): best_score ← -infinity best_child ← null for child in node.children: exploit ← child.Q explore ← c * sqrt( ln(node.N) / child.N ) score ← exploit + explore if score > best_score: best_score ← score best_child ← child return best_child

function rollout(state, policy, model): total_return ← 0 while not model.is_terminal(state): action ← policy(state) # e.g. uniform random state, reward ← model.step(state, action) total_return ← total_return + reward return total_return ``` Two implementation notes matter in practice. First, `N(s,a)` starting at zero makes the UCT formula undefined; the usual fix is to force every untried action to be tried once before the UCT rule is applied (this is exactly what the expansion phase guarantees, since selection only descends past fully expanded nodes). Second, for two-player zero-sum games the backpropagated value must flip sign at every other level (the opponent's gain is your loss), which is the basis for the minimax flavor of MCTS used in game-playing systems.

Per-iteration time. Selection descends the tree along a single path of length at most the current tree depth $d_{\text{tree}}$, at each step scanning up to $b$ children to compute UCT scores — cost $O(b \cdot d_{\text{tree}})$. Expansion is $O(1)$ or $O(b)$ depending on how untried actions are tracked. The simulation phase depends on the rollout horizon $H$ (up to the episode length), costing $O(H)$ model calls. Backpropagation revisits the same path, $O(d_{\text{tree}})$. So one iteration costs

Total time for $n$ iterations. Because the tree grows by at most one node per iteration, after $n$ iterations the tree has at most $n$ nodes, and $d_{\text{tree}} = O(\min(n, d_{\max}))$ where $d_{\max}$ is the maximum possible search depth. In the regime where rollouts dominate (common in practice), total cost is roughly $O(n \cdot H)$, i.e. linear in the simulation budget — this is exactly what makes MCTS an anytime algorithm: doubling the time budget roughly doubles the number of simulations and further sharpens the value estimates, with no restructuring needed.

Space. The tree stores at most $O(n)$ nodes after $n$ iterations (one node added per iteration in the worst case), each storing $O(b)$ statistics for its children, giving $O(nb)$ space in the worst case — far smaller than the $O(b^{d_{\max}})$ required to store the full game tree.

Why UCT is a sound selection rule. At a single node, choosing among its children is a stochastic multi-armed bandit problem: each child $a$ has an unknown mean return $\mu(s,a)$, and pulling arm $a$ (running a simulation through it) yields a noisy sample. The UCB1 policy of choosing $\arg\max_a \left[Q(s,a) + c\sqrt{\ln N(s)/N(s,a)}\right]$ is known to have regret (cumulative loss versus always playing the best arm) bounded by $O(\ln n)$ after $n$ pulls, meaning the fraction of pulls spent on suboptimal arms shrinks to zero — the algorithm eventually concentrates almost all trials on the best arm at each node while still probing others logarithmically often, which guarantees it will not get permanently stuck on a suboptimal move due to unlucky early samples. Chaining this bandit guarantee recursively down every level of the tree is the content of the UCT consistency theorem (Kocsis & Szepesvári, 2006): under the (mild) assumption that leaf rollout returns are bounded and the tree is finite-depth, the probability that UCT selects a suboptimal action at the root converges to zero as the number of simulations $n \to \infty$, and the bias of the value estimates decreases at rate $O(\log n / n)$ at each node. Intuitively: correctness at the leaves (accurate rollout estimates) combined with the regret-minimizing property of UCB1 at every internal node implies that value estimates propagate upward with vanishing error, so the estimated best root action converges to the true optimal action given enough simulations.

Honest tradeoffs. MCTS gives no finite-sample optimality guarantee — with a small simulation budget it can and does pick suboptimal moves, especially in domains with "trap" states that look good on average but are catastrophic (the classic pathology is when a losing move has a slightly higher mean rollout return but a very low probability of leading to disaster, which random rollouts may under-sample). Random rollouts also make the estimated value depend heavily on the quality of the default policy: a poor rollout policy in a domain requiring precise tactics (many chess middlegames) yields noisy, misleading estimates, which is a central motivation for replacing rollouts with learned evaluation functions, foreshadowing the architecture used in AlphaGo and AlphaZero.

Consider a small two-player decision tree at the root state $R$, with two available actions, `Left` and `Right`, and $c = 1.0$. We trace four MCTS iterations by hand (rollout returns are given as fixed illustrative numbers, since the "random" rollout policy is stochastic in general).

After 4 iterations the root's children have $N(\text{Left})=3$, $Q(\text{Left})\approx 0.67$, and $N(\text{Right})=1$, $Q(\text{Right})=0.00$. Even though the raw averages might shift with more samples, `Left` has already attracted three times as many simulations as `Right`, illustrating the asymmetric growth: UCT's exploration term kept `Right` from being starved after its early loss (it was still worth $\sqrt{\ln 3 / 1} \approx 1.05$ in exploration bonus at iteration 4), but the accumulating evidence for `Left` pulled the search decisively in that direction. With a much larger budget, this asymmetry becomes extreme — the tree under `Left` might contain thousands of nodes while `Right`'s subtree contains only a handful, exactly the behavior needed to make search feasible when $b^d$ is astronomically large. The final action returned is the one with the highest visit count at the root — here, `Left`, with $N=3$ versus $N=1$ — rather than the one with the highest raw $Q$, because visit count reflects sustained confidence and is empirically more robust to variance in individual rollout outcomes.

The statistical backbone of MCTS — balancing exploration and exploitation via confidence bounds — traces to the theory of sequential decision-making and the multi-armed bandit problem, formalized decades before it was applied to trees.

MCTS is the search engine behind essentially every strong modern game-playing system for domains with large branching factors: Go, Hex, general game playing competitions, and real-time strategy game AI. It is a natural fit whenever a simulator or generative model exists but a full policy is too costly to learn or compute in advance — general game playing agents, certain robotics motion-planning pipelines, and combinatorial optimization tools (scheduling, puzzle solving) all use MCTS variants when exact search is intractable. Its most influential legacy is architectural: AlphaGo replaced pure random rollouts with a learned value network (to estimate position quality) and a learned policy network (to bias the selection/expansion phase toward promising moves), while keeping the UCT-style tree search as the backbone. AlphaZero pushed this further, discarding rollouts entirely in favor of a single neural network trained by self-play whose outputs directly seed both the prior probabilities used during selection and the value estimates used at leaves — MCTS became the mechanism that generates high-quality training targets for the network, and the improved network in turn makes the tree search sharper, in a virtuous training loop. Related ideas underlie search-augmented reasoning in board games beyond Go (chess, shogi), and MCTS-style lookahead has been explored in non-game planning domains such as autonomous vehicle trajectory selection and industrial scheduling, wherever a model can be queried faster than the real world can be observed.

Ask the tutor: How does the PUCT variant used in AlphaZero modify the UCT formula to incorporate a learned policy prior?