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 .
- 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
Let be the mean of arm 's first rewards, and . Apart from its first pulls, arm is pulled at time only if its index is at least the optimal arm's:
If , at least one of three events holds: the optimal arm is underestimated, arm is overestimated, or arm 's confidence interval is still wide:
For the third is impossible, because . Hoeffding's inequality bounds each of the other two by :
A union bound over the at most pairs , summed over , gives the constant, since :
Two arms with gap and a horizon of pulls. About how many pulls of the worse arm does the UCB1 bound allow?
Show the answer
7400
, plus . 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 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 , after visits, the tree policy picks
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.
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?
- The expected outcome of random play from the root
- The minimax value of the tree
- The average of all leaf values
- 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 for some (Coulom, 2007; Chaslot et al., 2008).
- Priors. PUCT-style rules (Rosin, 2011; AlphaGo) multiply the exploration term by a prior probability 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 . Hoeffding's inequality and a union bound give , so regret is .
- 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.
UCB1 runs for rounds on two Bernoulli arms whose means differ by . How does its expected regret scale?
Show the answer
D.
Regret is . Small gaps need many pulls to detect, but each of those pulls costs only .
In the UCB1 proof, why is the exploration bonus ?
- It makes each misleading event have probability at most by Hoeffding's inequality, which is summable over times and sample counts
- It is the standard deviation of a Bernoulli reward
- It makes the index an unbiased estimate of the mean
- It guarantees that every arm is pulled equally often
Show the answer
A. It makes each misleading event have probability at most by Hoeffding's inequality, which is summable over times and sample counts
Hoeffding gives , and turns this into . Summed over the pairs of sample counts and over all , that leaves the constant .
Why can't UCB1's i.i.d. analysis be applied directly at an internal node of a UCT tree?
- Rewards at internal nodes are unbounded
- A child's rewards drift, because the policy in its subtree keeps changing as the search improves
- Internal nodes have more children than UCB1 allows
- 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.
What did Coquelin and Munos (2007) show about UCT?
- UCT is inconsistent: it can converge to a wrong move
- UCT attains the Lai–Robbins lower bound at every node
- On deceptive trees, UCT's convergence can take a number of iterations growing like a tower of exponentials in the depth
- 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 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).