MCTS Planning

MCTS (Monte Carlo Tree Search) plans sequential decisions as tree search, looping over four steps: selection (pick nodes by UCT $UCT = \bar{v} + c\sqrt{\frac{\ln N}{n}}$, balancing exploration vs exploitation, with $N$ the parent's visit count and $n$ the child's), expansion, simulation (rollout), and backpropagation of the leaf value. In classic RL, node values come from policy-value networks — AlphaGo/AlphaZero iteratively improve through self-play — or from a learned world model (MuZero plans MCTS in latent space, see this module's muzero card).

RL perspective: for LLM reasoning, nodes are partial reasoning states, actions are next-token steps, and node values come from PRM/verifier scores, powering test-time search and high-quality trajectory generation for RL. See the LLM module: full definition and exam points in the LLM module's mctsSearch card (id: mcts-search).

games and planning (AlphaZero family), latent-space planning with learned models (MuZero), test-time scaling and RL data generation for reasoning models.

greedy/single-path decisions cannot recover from an early mistake, and errors propagate along the path; MCTS explores multiple paths with value-guided pruning, finding better trajectories at decision time and raising success rates on hard tasks.

What do MCTS's four steps do? Write the UCT formula and explain each symbol?

How does MCTS combine with policy-value networks (AlphaGo/AlphaZero self-play)?

How are nodes/actions/values defined for MCTS in LLM reasoning? Why PRM values?

MCTS vs plain sampling (best-of-N): compute complexity vs gains?

How does MuZero run MCTS in latent space? Difference from explicit dynamics models?