Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

Monte Carlo Tree Search & UCT

Bandits at every node: UCB1 and its regret bound.

Monte Carlo tree search judges a position by playing random games from it, and it spends its simulations unevenly, on moves that look best or are least explored. The rule that decides is a bandit algorithm with a provable regret bound. This lesson proves that bound, stacks the bandits into a tree, and marks where the guarantees stop.

What you’ll learn

  • Define the stochastic bandit problem and its regret, and prove UCB1's finite-time bound E[Ti(n)]≤8ln⁡nΔi2+1+π23\E[T_i(n)]\le\frac{8\ln n}{\Delta_i^2}+1+\frac{\pi^2}{3}.
  • Compare UCB1 with the Lai–Robbins lower bound: why its rate is optimal while its constants are loose.
  • State UCT's consistency theorem (Kocsis & Szepesvári, 2006), explain the drifting-payoff problem its proof must handle, and describe Coquelin and Munos's worst case.
  • Explain the practical machinery of MCTS: final move selection, RAVE, progressive widening, priors and parallel search.

Bandits and the UCB1 bound

DerivationProof sketch
  1. Ti(n) ≤ ℓ+∑t=Kn−11{min⁡0<s<t(Xˉs∗+ct,s)≤max⁡ℓ≤si<t(Xˉi,si+ct,si)}T_i(n)\ \le\ \ell+\sum_{t=K}^{n-1}\mathbf{1}\Big\{\min_{0<s<t}\big(\bar X^*_{s}+c_{t,s}\big)\le\max_{\ell\le s_i<t}\big(\bar X_{i,s_i}+c_{t,s_i}\big)\Big\}

    Let Xˉi,s\bar X_{i,s} be the mean of arm ii's first ss rewards, ct,s=2ln⁡t/sc_{t,s}=\sqrt{2\ln t/s} and ℓ=⌈8ln⁡n/Δi2⌉\ell=\lceil8\ln n/\Delta_i^2\rceil. Apart from its first ℓ\ell pulls, arm ii is pulled at time t+1t+1 only if its index is at least the optimal arm's:

  2. Xˉs∗≤μ∗−ct,sorXˉi,si≥μi+ct,siorμ∗<μi+2ct,si\bar X^*_{s}\le\mu^*-c_{t,s}\qquad\text{or}\qquad\bar X_{i,s_i}\ge\mu_i+c_{t,s_i}\qquad\text{or}\qquad\mu^*<\mu_i+2c_{t,s_i}

    If Xˉs∗+ct,s≤Xˉi,si+ct,si\bar X^*_s+c_{t,s}\le\bar X_{i,s_i}+c_{t,s_i}, at least one of three events holds: the optimal arm is underestimated, arm ii is overestimated, or arm ii's confidence interval is still wide:

  3. Pr⁡(Xˉs∗≤μ∗−ct,s)≤t−4,Pr⁡(Xˉi,si≥μi+ct,si)≤t−4\Pr\big(\bar X^*_{s}\le\mu^*-c_{t,s}\big)\le t^{-4},\qquad\Pr\big(\bar X_{i,s_i}\ge\mu_i+c_{t,s_i}\big)\le t^{-4}

    For si≥ℓs_i\ge\ell the third is impossible, because ct,si≤2ln⁡n/ℓ≤Δi/2c_{t,s_i}\le\sqrt{2\ln n/\ell}\le\Delta_i/2. Hoeffding's inequality bounds each of the other two by e−2s ct,s2=t−4e^{-2s\,c_{t,s}^2}=t^{-4}:

  4. E[Ti(n)] ≤ ℓ+∑t=1∞∑s=1t∑si=1t2t−4 ≤ 8ln⁡nΔi2+1+π23\E\big[T_i(n)\big]\ \le\ \ell+\sum_{t=1}^{\infty}\sum_{s=1}^{t}\sum_{s_i=1}^{t}2t^{-4}\ \le\ \frac{8\ln n}{\Delta_i^2}+1+\frac{\pi^2}{3}

    A union bound over the at most t2t^2 pairs (s,si)(s,s_i), summed over tt, gives the constant, since ∑t2t−2=π2/3\sum_t2t^{-2}=\pi^2/3:

Predict before you look

Two arms with gap Δ=0.1\Delta=0.1 and a horizon of n=10,000n=10{,}000 pulls. About how many pulls of the worse arm does the UCB1 bound allow?

Show the answer

7400

8ln⁡(104)/0.12≈8⋅9.21/0.01≈7,3708\ln(10^4)/0.1^2\approx8\cdot9.21/0.01\approx7{,}370, plus 1+π2/3≈4.31+\pi^2/3\approx4.3. Playing both arms equally would spend only 5,000 pulls on the worse one, so at this horizon the bound says nothing useful. Its content is the rate: at n=106n=10^6 it allows about 11,060 pulls, a vanishing fraction of the horizon, and refined analyses shrink the constant 8.

UCT: a bandit at every node

UCT (Kocsis & Szepesvári, 2006) is the form of Monte Carlo tree search that runs a bandit at every internal node of the search tree. Each child is an arm, and its reward is the return of a simulation that passes through it. At node ss, after N(s)N(s) visits, the tree policy picks

a(s)=arg max⁡a[ Xˉs,a+2Cpln⁡N(s)N(s,a) ],Cp=12 recovers UCB1a(s)=\argmax_{a}\Big[\,\bar X_{s,a}+2C_p\sqrt{\frac{\ln N(s)}{N(s,a)}}\,\Big],\qquad C_p=\tfrac{1}{\sqrt2}\ \text{recovers UCB1}
In two-player games each node's averages are kept from the point of view of the player to move there, so maximizing at every node becomes minimax in the limit.

The catch is that a child's payoffs are not i.i.d. As the child's own subtree is explored, the policy below it improves, so its average drifts. Kocsis and Szepesvári extended UCB1's analysis to payoff sequences whose means converge and whose deviations satisfy tail bounds, then applied it inductively from the leaves up.

Check your understanding

In a two-player game, UCT keeps each node's averages from the point of view of the player to move there. As the number of iterations grows, what does the value estimate at the root converge to?

  1. The expected outcome of random play from the root
  2. The minimax value of the tree
  3. The average of all leaf values
  4. The value of the best leaf for the player at the root
Show the answer

B. The minimax value of the tree

Visits concentrate on each node's best move for the player to move, so averages at MAX nodes approach the maximum over children and at MIN nodes the minimum: in the limit the backed-up value is the minimax value. With few iterations the estimate is still pulled toward the average of random play.

MCTS in practice

Plain UCT with random playouts is only a starting point. Strong programs add:

  • Robust final selection. Play the most visited root move, whose estimate is the least noisy. At the root what counts is simple regret, the quality of the final recommendation, not cumulative regret; Bubeck, Munos and Stoltz (2009) showed that the two objectives conflict, so a root allocation can afford more exploration than UCB1 performs.
  • Shared statistics. RAVE, or all-moves-as-first (Gelly & Silver, 2007), credits a move with the results of simulations in which it was played later: a biased but low-variance estimate, blended out as real visits accumulate.
  • Progressive widening. With huge or continuous action sets, a node adds children only as its visit count grows, roughly like N(s)αN(s)^\alpha for some α<1\alpha<1 (Coulom, 2007; Chaslot et al., 2008).
  • Priors. PUCT-style rules (Rosin, 2011; AlphaGo) multiply the exploration term by a prior probability P(s,a)P(s,a) from a policy, concentrating the search on plausible moves.
  • Parallelism. Many threads descend the tree at once, and a temporary virtual loss on each path steers them apart.

Key takeaways

  • UCB1 pulls the arm maximizing Xˉi+2ln⁡t/Ti\bar X_i+\sqrt{2\ln t/T_i}. Hoeffding's inequality and a union bound give E[Ti(n)]≤8ln⁡n/Δi2+1+π2/3\E[T_i(n)]\le8\ln n/\Delta_i^2+1+\pi^2/3, so regret is O(∑iln⁡n/Δi)\order{\sum_i\ln n/\Delta_i}.
  • The Lai–Robbins bound makes logarithmic regret unavoidable; UCB1's rate is optimal up to constants, and KL-UCB and Thompson sampling match the constant for Bernoulli arms.
  • UCT runs UCB1 at every node. Despite drifting payoffs its root decision is consistent (Kocsis & Szepesvári, 2006), but on deceptive trees convergence can take a tower of exponentials in the depth (Coquelin & Munos, 2007).
  • Practical MCTS adds robust final-move selection, RAVE, progressive widening, learned priors (PUCT) and parallel search with virtual loss.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

UCB1 runs for nn rounds on two Bernoulli arms whose means differ by Δ\Delta. How does its expected regret scale?

  1. O(n)\order{\sqrt n}
  2. O(nΔ)\order{n\Delta}
  3. O(ln⁡n/Δ2)\order{\ln n/\Delta^2}
  4. O(ln⁡n/Δ)\order{\ln n/\Delta}
Show the answer

D. O(ln⁡n/Δ)\order{\ln n/\Delta}

Regret is Δ⋅E[Ti(n)]≤Δ(8ln⁡n/Δ2+O(1))=O(ln⁡n/Δ)\Delta\cdot\E[T_i(n)]\le\Delta\big(8\ln n/\Delta^2+\order{1}\big)=\order{\ln n/\Delta}. Small gaps need many pulls to detect, but each of those pulls costs only Δ\Delta.

Question 2

In the UCB1 proof, why is the exploration bonus 2ln⁡t/s\sqrt{2\ln t/s}?

  1. It makes each misleading event have probability at most t−4t^{-4} by Hoeffding's inequality, which is summable over times and sample counts
  2. It is the standard deviation of a Bernoulli reward
  3. It makes the index an unbiased estimate of the mean
  4. It guarantees that every arm is pulled equally often
Show the answer

A. It makes each misleading event have probability at most t−4t^{-4} by Hoeffding's inequality, which is summable over times and sample counts

Hoeffding gives Pr⁡(Xˉs≥μ+c)≤e−2sc2\Pr(\bar X_s\ge\mu+c)\le e^{-2sc^2}, and c2=2ln⁡t/sc^2=2\ln t/s turns this into t−4t^{-4}. Summed over the t2t^2 pairs of sample counts and over all tt, that leaves the constant π2/3\pi^2/3.

Question 3

Why can't UCB1's i.i.d. analysis be applied directly at an internal node of a UCT tree?

  1. Rewards at internal nodes are unbounded
  2. A child's rewards drift, because the policy in its subtree keeps changing as the search improves
  3. Internal nodes have more children than UCB1 allows
  4. UCB1 requires Gaussian rewards
Show the answer

B. A child's rewards drift, because the policy in its subtree keeps changing as the search improves

The return through a child depends on how its subtree is searched, and that improves over time, so its payoff sequence is non-stationary. Kocsis and Szepesvári extended the analysis to drifting payoffs whose means converge, then applied it level by level up the tree.

Question 4

What did Coquelin and Munos (2007) show about UCT?

  1. UCT is inconsistent: it can converge to a wrong move
  2. UCT attains the Lai–Robbins lower bound at every node
  3. On deceptive trees, UCT's convergence can take a number of iterations growing like a tower of exponentials in the depth
  4. UCT works only for single-player problems
Show the answer

C. On deceptive trees, UCT's convergence can take a number of iterations growing like a tower of exponentials in the depth

Consistency is an asymptotic statement with tree-dependent constants. Coquelin and Munos built trees on which the optimism of UCB1, applied to drifting averages, stays misled for exp⁡(exp⁡(⋯ ))\exp(\exp(\cdots)) iterations, and proposed variants that use smoothness assumptions to avoid it.

Further reading

  • P. Auer, N. Cesa-Bianchi & P. Fischer, "Finite-time analysis of the multiarmed bandit problem," Machine Learning 47 (2002), 235–256.
  • L. Kocsis & C. Szepesvári, "Bandit based Monte-Carlo planning," Proceedings of ECML (2006).
  • P.-A. Coquelin & R. Munos, "Bandit algorithms for tree search," Proceedings of UAI (2007).
  • C. B. Browne et al., "A survey of Monte Carlo tree search methods," IEEE Transactions on Computational Intelligence and AI in Games 4(1) (2012), 1–43.
  • T. Lattimore & C. Szepesvári, Bandit Algorithms (Cambridge University Press, 2020).