Monte Carlo, TD, and Search

TL;DR — Every method in this part is an estimator for one quantity: the advantage $A^{\pi }(s,a)$, “how much better than average was that action”. You can estimate it from the full empirical return $G_t$ (Monte Carlo: unbiased, high variance, needs the episode to end) or from one step plus a bootstrapped value $r_t+\gamma V(s_{t+1})$ (TD: biased by the value function’s error, low variance). GAE interpolates between them with $\lambda$; because LLM episodes are short and $\gamma =1$, all of the bias-variance burden sits on $\lambda$ and on the value head. MCTS moves the same trade into inference time, spending forward passes to buy lookahead and using UCB1/PUCT to decide which branch deserves them. Each term of PUCT prevents a specific degenerate search.

1. Why this exists

Here is a failure. You train a policy with REINFORCE on a task where a correct response earns reward 1 and an incorrect one earns 0. The gradient for a response is its own return times the log-probability of each token in it. Since the return is 0 or 1, the gradient for a wrong answer is exactly zero — nothing is learned from errors, which is where most of the signal is. And for a correct answer, every token in a 400-token response, including the boilerplate and the “let me think step by step” preamble, receives the full credit.

Two problems, and they are different:

1. The estimator has enormous variance. The return of a sampled trajectory is a single random draw. If the answer happened to come out right, the whole trajectory is reinforced; if it came out wrong, the whole trajectory is pushed down, by an amount that depends on the luck of the sample rather than on how good the reasoning was.
2. There is no notion of “better than expected”. Reward 1 is good in absolute terms but says nothing about whether this action was better than what the policy would normally do here. A policy that already solves 90% of a problem set gets the same gradient on a solved problem as one that solves 10%.

The fix for both is the same object: subtract a baseline so that what you reinforce is the surprise, not the outcome. Doing that correctly requires the whole value-function vocabulary — return, value, action-value, advantage, the Bellman equations — and it requires deciding whether to estimate that baseline from observed returns or from a learned function. That decision is the Monte Carlo versus TD question, and it is the first half of this chapter.

The second half is a different way to spend compute on the same problem. Instead of asking “what is the average value of this state”, tree search asks “if I spend $N$ extra forward passes exploring the alternatives from this state, which action looks best”. That is MCTS, and the criterion it uses to allocate those passes is UCB1/PUCT — an algorithm that exists precisely because spending budget evenly is wasteful and spending it greedily is myopic.

Why this chapter is placed here. PPO (PPO for LLMs) is GAE plus a clipped ratio. GRPO (GRPO) is the decision to skip the value function and use the group mean instead. You cannot evaluate either choice without the estimator vocabulary below, and you cannot answer “is tree search worth it for reasoning” without the search half.

2. How it works

2.1 An autoregressive generation is an MDP

The mapping is exact, and almost every confusion in this part comes from moving between the RL object and the LLM object:

Two consequences that trip people up:

• The transition kernel is known and trivial. “Model-based RL” is a strange framing for a single response: the next state is always the concatenation. All the interesting uncertainty in LLM RL is in the policy, not the environment.
• The reward is terminal and sparse. Zero everywhere except the last token. That single fact is why credit assignment is hard, why value heads are difficult to fit, and why process reward models were proposed at all (§2.10).

2.2 Return, value, action-value, advantage

$$G_t=\sum _{k=0}^{T-t}{\gamma }^k{r}_{t+k}$$

• $G_t$ — the empirical return from step $t$: everything the agent actually collected, summed. It is an observable, not a model, which is why Monte Carlo methods can use it directly.
• $r_{t+k}$ — the reward received $k$ steps after $t$.
• $T$ — the terminal step. The sum stops at the end of the episode; there is no tail beyond it.
• $\gamma \in [0,1]$ — the discount factor, deciding how much a reward $k$ steps in the future counts, as ${\gamma }^k$.
• $T-t$ — the remaining horizon, so the number of terms varies with $t$.

What $\gamma$ does, and why removing it changes the problem. $\gamma$ is horizon control: the exchange rate between a reward now and a reward later. $\gamma =0$ makes the agent myopic — it maximises only the immediate reward and will not take a step that costs anything, even when that step leads to certain success. $\gamma \to 1$ makes it patient, at the cost of a longer effective horizon and higher-variance returns. The effective horizon is roughly $1/(1-\gamma )$: $\gamma =0.99$ gives 100 steps, $\gamma =0.9$ gives 10.

Why LLM RL sets $\gamma =1$. A response is one bounded episode with the reward delivered at the end. Discounting it would make the objective depend on where the answer happened to end: the same correct answer would be worth ${\gamma }^T$ if it ran long and ${\gamma }^{T^{\prime }}$ if it ran short, so the policy would be rewarded for terseness on a task where length is irrelevant. Setting $\gamma =1$ removes that artefact and removes the main variance-control knob, which is why $\lambda$ in §2.6 carries the whole burden — and why “$\gamma =1.0$” appears in every LLM RL hyperparameter table.

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid s_t=s],Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid s_t=s,a_t=a]$$

• $V^{\pi }(s)$ — the state value: the return you expect, on average, if you start in state $s$ and then behave according to $\pi$. It is the baseline that makes a gradient about surprise rather than outcome.
• $Q^{\pi }(s,a)$ — the action value: the same expectation, conditioned on taking action $a$ right now and following $\pi$ afterwards.
• ${\mathbb{E}}_{\pi }$ — the expectation over trajectories generated by $\pi$. Both quantities are defined with respect to a policy; “the value of a state” is meaningless without saying whose policy.
• The conditioning is the only difference between $V$ and $Q$, and it is the difference between “how good is this position” and “how good is this move from this position”.

$$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$$

The advantage: how much better action $a$ is than the policy’s own average behaviour in state $s$. It is the quantity every policy-gradient method needs, and it has one property that makes everything else work:

$${\mathbb{E}}_{a\sim \pi (\cdot \mid s)}[A^{\pi }(s,a)]=0$$

The policy-weighted average advantage is exactly zero. That identity is why you may subtract any baseline: replacing $G_t$ with $G_t-b(s_t)$ for any $b$ that does not depend on the action leaves the gradient’s expectation unchanged, because

$${\mathbb{E}}_{a\sim \pi }[{\nabla }_{\theta }\log {\pi }_{\theta }(a\mid s)b(s)]=b(s){\nabla }_{\theta }\sum _a{\pi }_{\theta }(a\mid s)=b(s){\nabla }_{\theta }1=0$$

Subtracting a baseline therefore buys variance reduction for free. Two baselines appear in this part: $V_{\psi }(s_t)$ (PPO, learned) and $\mathrm{mean}(r_1\dots r_G)$ over a group of samples (GRPO, learned-free). Both are legitimate for exactly the reason above.

2.3 The Bellman equations, term by term

Bellman expectation equation — what $V^{\pi }$ must satisfy for a given policy:

$$V^{\pi }(s)=\sum _a\pi (a\mid s)[r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)V^{\pi }(s^{\prime })]$$

• ${\sum }_a\pi (a\mid s)$ — the average over the policy’s own action choices. This is what makes the equation about this policy; swap it for a $\max$ and you get the optimality version below.
• $\pi (a\mid s)$ — the probability the policy takes action $a$ in state $s$. Remove this weighting and the equation describes a deterministic policy, an assumption you do not want to bake in.
• $r(s,a)$ — the expected immediate reward of taking $a$ in $s$. It is an expectation because in a general MDP the reward may be stochastic even for a fixed state-action pair. In an LLM it is deterministic and zero except at the end (§2.1), so this term does almost no work here.
• $\gamma$ — the discount. It is what makes the equation recursive and contractive: because $\gamma <1$, the right-hand side is a contraction mapping in $V$, which is the mathematical reason value iteration converges.
• $p(s^{\prime }\mid s,a)$ — the transition probability. In an LLM this is a point mass on the concatenated state, so the inner sum collapses to one term. That collapse is why LLM RL looks like a bandit if you squint and like a deterministic chain if you do not.
• $V^{\pi }(s^{\prime })$ — the same function, one step later. This self-reference is the whole content of the equation: value now equals reward now plus discounted value next, averaged over what happens next.

Bellman optimality equation — what the best value satisfies:

$$V^{\ast }(s)=\underset{a}{\max }[r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })]=\underset{a}{\max }{Q}^{\ast }(s,a)$$

• ${\max }_a$ — replaces the policy average. The optimal action maximises the bracketed quantity, and there is no averaging because a deterministic policy is optimal in an MDP. This is where greedy action selection comes from.
• Removing the $\max$ gives the expectation equation back. Setting $\gamma =0$ leaves a one-step greedy rule — the myopic policy that ignores consequences, which is exactly the failure mode §2.2 warned about.

Action-value and TD forms, which are the ones implementations touch:

$$Q^{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)V^{\pi }(s^{\prime }),V^{\pi }(s)=\sum _a\pi (a\mid s)Q^{\pi }(s,a)$$

$${\delta }_t=r_t+\gamma V(s_{t+1})-V(s_t)$$

• ${\delta }_t$ — the temporal-difference (TD) residual, or one-step surprise. The first two terms, $r_t+\gamma V(s_{t+1})$, are the bootstrap estimate of the return: “what I got, plus what I now think the future is worth”. Subtracting $V(s_t)$ — what I expected before acting — leaves the surprise. If ${\delta }_t>0$, things went better than expected and the action should become more likely.
• The word bootstrap is doing real work: the target contains $V$, the thing being estimated. That is what lets you learn without waiting for the episode to end, and it is what makes the target move as $V$ changes — a non-stationary regression.

2.4 Monte Carlo versus TD

Two estimators of the same quantity, at opposite ends of a trade-off:

The structure is not symmetric, and it is worth being precise about why:

• Monte Carlo is unbiased but its variance grows with horizon. $G_t$ sums $T-t$ random rewards. In an LLM, where the reward is terminal and binary, that sum is a single Bernoulli draw — maximum variance for the information it carries. You also cannot update until the episode ends.
• TD is biased but its variance does not grow with horizon. Its error has two sources: the reward’s own noise (one step, not $T-t$ steps) and the bias from $V$ being wrong. In LLM RL the second dominates early, because the value head is freshly initialised and has to predict a terminal reward from a partial response.

The GAE paper’s own formulation separates the two regimes exactly:

GAE$(\gamma ,1)$ “is $\gamma$-just regardless of the accuracy of $V$, but it has high variance due to the sum of terms”; GAE$(\gamma ,0)$ “is $\gamma$-just for $V=V^{\pi ,\gamma }$ and otherwise induces bias, but it typically has much lower variance”; $0<\lambda <1$ is “a compromise between bias and variance, controlled by parameter $\lambda$”. — Schulman et al. 2015, arXiv:1506.02438

Which side is LLM RL on? Deliberately mixed, and this is the design tension of the whole part. PPO + GAE bootstraps through the critic (TD). GRPO/REINFORCE-style methods use the terminal reward (MC) with a baseline that needs no learning. That is one reason the critic-free methods are more robust in practice for sparse-reward reasoning: there is no bootstrap target to be wrong. When you cannot fit a value function to a 32k-token chain of thought, the honest move is to stop pretending you can.

2.5 $n$-step returns, and why interpolation is possible at all

$$G_t^{(n)}=r_t+\gamma r_{t+1}+\cdots +{\gamma }^{n-1}{r}_{t+n-1}+{\gamma }^{n}V(s_{t+n})$$

• $n$ — how many real rewards you collect before switching to the bootstrap. $n=1$ is TD; $n=T-t$ (or beyond the episode end) is Monte Carlo.
• $r_t\dots r_{t+n-1}$ — the observed rewards.
• ${\gamma }^{n}V(s_{t+n})$ — the bootstrap term, discounted back to time $t$ by exactly the number of steps it sits in the future. Getting this exponent wrong (using $\gamma$ instead of ${\gamma }^n$) silently changes the effective horizon.
• Removing the bootstrap term makes it pure Monte Carlo; setting $n=1$ makes it pure TD. The family exists because intermediate $n$ is often better than either end: you trade a bounded amount of bias for a large reduction in variance.

TD($\lambda$) and GAE($\lambda$) average over all $n$ with geometric weights $(1-\lambda ){\lambda }^{n-1}$. The GAE paper states the analogy explicitly: its technique is “analogous to TD($\lambda$)”.

2.6 GAE: the $\lambda$ dial, and what its endpoints actually are

Schulman et al. 2015, arXiv:1506.02438:

$${\delta }_t^V=r_t+\gamma V(s_{t+1})-V(s_t)$$

$${\hat{A}}_t^{(k)}=\sum _{l=0}^{k-1}{\gamma }^l{\delta }_{t+l}^V$$

$${\hat{A}}_t^{\mathrm{GAE}(\gamma ,\lambda )}=(1-\lambda )({\hat{A}}_t^{(1)}+\lambda {\hat{A}}_t^{(2)}+{\lambda }^2{\hat{A}}_t^{(3)}+\dots )=\sum _{l=0}^{\infty }(\gamma \lambda {)}^l{\delta }_{t+l}^V$$

Symbol by symbol:

• $r_t$ — the reward at step $t$. In the LLM adaptation this is per token: $0$ for every token except the last, plus the KL penalty at every token. The reward vector fed to GAE is therefore not sparse in practice, because the KL term is dense.
• $\gamma \in [0,1]$ — the discount, setting the problem’s horizon. In LLM RL $\gamma =1$.
• $V(s)$ — the value estimate. Its error is the source of the bias: with a wrong $V$, bootstrapping propagates the error along the trajectory.
• ${\delta }_t^V$ — the TD residual from §2.3: the one-step surprise.
• ${\hat{A}}_t^{(k)}$ — the $k$-step advantage estimate: the sum of the next $k$ TD residuals, each discounted by ${\gamma }^l$. At $k=1$ this is just ${\delta }_t^V$.
• $\lambda \in [0,1]$ — the GAE decay, an exponential weighting over the $k$-step estimators. The effective decay of the whole sum is $\gamma \lambda$, and this is the paper’s key structural point: $\lambda$ changes the estimator’s bias-variance position without changing the problem’s effective horizon (which is $\gamma$’s job). Two dials, two distinct purposes.
• $(1-\lambda )$ — the normaliser that makes the weights $(1-\lambda ){\lambda }^l$ sum to 1. Without it the sum is unnormalised and the advantage’s scale changes with $\lambda$, which would entangle $\lambda$ with the learning rate.
• The infinite upper limit is not a modelling claim: past the end of the episode there is nothing to add, so the sum terminates at $T-t$.

Reading the dial, with the endpoints derived rather than asserted.

$\lambda =0$ collapses the geometric series to its first term:

$${\hat{A}}_t={\delta }_t^V=r_t+\gamma V(s_{t+1})-V(s_t)$$

“Trust the critic completely, react to one step.” Low variance, and biased by exactly the critic’s error. In LLM RL this is the worst regime, because $V$ is always bad early: the value head is freshly initialised and must predict a terminal reward from a partial response. A biased-by-$V$ estimator with a random $V$ is not a gradient, it is noise with a direction.

$\lambda =1$ makes the weights $(1-\lambda ){\lambda }^l$ degenerate, so read the final form. With $\lambda =1$ and $\gamma =1$, the sum telescopes:

$${\hat{A}}_t=\sum _{l=0}^{\infty }{\gamma }^l{\delta }_{t+l}^V=\left(\sum _{l=0}^{\infty }{\gamma }^l{r}_{t+l}\right)-V(s_t)=G_t-V(s_t)$$

which is exactly Monte Carlo return minus a baseline. So the endpoints are literally the two estimators of §2.4: $\lambda =0$ is one-step TD, $\lambda =1$ is Monte Carlo with a baseline. GAE is the family between them, parametrised so that you can dial the trade without touching $\gamma$.

Why the intermediate value is used. Neither endpoint is acceptable: $\lambda =0$ is dominated by critic bias you cannot remove, and $\lambda =1$ has the variance of a full return sum with no bootstrap to damp it. $\lambda =0.95$ is the standard setting — the value in the original paper’s experiments and in the N+ RLHF reproduction, with $\gamma =1.0$. Read the pair as: use the critic only to damp the far tail of the sum, not to replace the observed reward.

Why $\gamma \lambda$ and not $\gamma$ or $\lambda$ alone. The product is the effective decay of the sum ${\sum }_l(\gamma \lambda {)}^l{\delta }_{t+l}$. With $\gamma =1$, $\lambda$ alone sets the effective horizon of the estimator. That is why $\lambda$ is the useful knob here and $\gamma$ is not: one of them still does something.

2.7 The policy gradient, and where the advantage enters

The policy gradient theorem gives

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}\left[\sum _{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t){\hat{A}}_t\right]$$

• $J(\theta )$ — the objective: expected return of the policy.
• $\tau$ — a trajectory: in LLM terms, one full response.
• ${\pi }_{\theta }(a_t\mid s_t)$ — the probability of the sampled token.
• ${\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$ — the score function: the direction in parameter space that makes the sampled token more likely. It is a direction, not a magnitude; all of the magnitude comes from ${\hat{A}}_t$.
• ${\hat{A}}_t$ — the advantage estimate. This is where every method in this part differs. PPO computes it with GAE and a critic; GRPO computes it as a group-normalised scalar broadcast to every token; RLOO computes it as a leave-one-out mean.
• The sum over $t$ says every token in the response gets a gradient contribution. Whether it gets the same advantage (sequence-level) or a per-token one is the choice discussed in PPO for LLMs and GRPO, and it matters more than it sounds: a token-level mean weights long responses more heavily.

The REINFORCE special case is ${\hat{A}}_t=G_t$ (or $G_t-b$). It is the simplest unbiased estimator and the one with the worst variance, which is the whole motivation for everything above.

2.8 On-policy, off-policy, and importance sampling

• On-policy: the data used for the gradient was generated by the current policy. The policy gradient theorem’s expectation is over $\tau \sim {\pi }_{\theta }$, so this is the distribution the theorem is about.
• Off-policy: the data comes from a behaviour policy $\mu \ne {\pi }_{\theta }$. To correct the mismatch you multiply by the importance-sampling (IS) ratio

$$\rho =\frac{{\pi }_{\theta }(\tau )}{\mu (\tau )},\text{and per action}{\rho }_t=\frac{{\pi }_{\theta }(a_t\mid s_t)}{\mu (a_t\mid s_t)}$$

• ${\pi }_{\theta }(\tau )$ — the probability the current policy assigns to the whole trajectory. It factors as a product of per-token probabilities, which is why the trajectory ratio telescopes into a product of per-step ratios.
• $\mu$ — the behaviour policy. In PPO, $\mu ={\pi }_{{\theta }_{\text{old}}}$, the snapshot taken at the top of the iteration, and ${\rho }_t$ is exactly PPO’s probability ratio $r_t(\theta )$. This is the identity to have at your fingertips: PPO’s ratio is an importance weight.
• Why it is needed: without it, the surrogate is a biased estimator of the policy gradient, and the multi-epoch updates that make PPO sample-efficient are invalid.
• The problem with IS: unbiased, but with unbounded (possibly infinite) variance when the ratio is heavy-tailed. A single token the current policy finds much less likely than the behaviour policy did produces a huge weight. This is why every practical method clips (PPO), truncates (veRL’s rollout_is_threshold: 2.0), or masks (DeepSeek-V3.2) the ratio.

LLM RL is nominally on-policy and off-policy in four ways, all of which you should be able to name:

1. PPO epochs. $K$ gradient epochs over the same rollout batch. Every epoch after the first is off-policy by construction — and that is the point of PPO’s ratio.
2. Minibatching. A large rollout batch is split into minibatches for several gradient steps, which is off-policy for the same reason.
3. Training/inference engine mismatch. vLLM and the training stack do not compute identical logprobs, so the ${\pi }_{{\theta }_{\text{old}}}$ in the denominator is not quite the one that sampled. This is the classic “the logprobs from vLLM don’t match the logprobs from FSDP” bug.
4. Sampling truncation. Top-p/top-k during rollout changes the action space, so the IS identity breaks: DeepSeek-V3.2 notes that this “introduces a mismatch between the action spaces of ${\pi }_{\text{old}}$ and ${\pi }_{\theta }$, which violates the principles of importance sampling”.

What on-policy costs. Because each gradient update needs fresh generation, and generation is autoregressive and memory-bandwidth-bound, rollout dominates the wall clock. OpenRLHF’s README states it as a design premise: “RLHF training spends 80% of the time on sample generation” — a project self-report, not a controlled measurement, but the qualitative claim is forced by the algorithm. It is why 2026 systems invest in asynchronous or partially-off-policy RL: the goal is to overlap generation with training, and then pay for the resulting staleness with IS correction or masking.

2.9 Why the bandit framing works, and when it stops working

InstructGPT calls the RL environment a bandit: “a random customer prompt and expects a response to the prompt. Given the prompt and response, it produces a reward determined by the reward model and ends the episode.” Under that framing:

• The critic is only a variance-reduction device. There is no future state to plan over, so $V$ has no decision-theoretic content.
• $\gamma$ is degenerate. Whether you set it to 1 or 0.99 changes nothing about the problem; it only changes the estimator.
• The group-mean baseline (GRPO) is exactly as legitimate as a learned critic, because with a terminal reward and one action per prompt, the group mean is an unbiased estimate of $V(s_0)$.

The framing breaks in four identifiable places, each corresponding to a real project decision:

1. Multi-turn / tool use. The reward arrives at the end of an interaction, so credit assignment spans turns. A bandit has no mechanism for “the third tool call was the mistake”.
2. Genuinely intermediate rewards. A process reward model (§2.10) or a verifier that scores partial progress makes $r_t\ne 0$ for $t<T$, at which point the Bellman machinery becomes load-bearing rather than decorative.
3. Episode length as a decision. If the policy can choose to stop, the horizon is endogenous and $\gamma$ stops being a free parameter.
4. Search. A bandit cannot look ahead. The moment you want to evaluate a prefix that has not been completed, you need a value estimate for a partial state — a genuine $V(s)$ — and you are in §2.11.

2.10 Where process supervision stands

Short version, with sources, because the honest state of the field is contested.

• The case for process reward models (PRMs). Let’s Verify Step by Step (Lightman et al. 2023, arXiv:2305.20050) showed step-level supervision beating outcome supervision on MATH, and Math-Shepherd (Wang et al. 2023, arXiv:2312.08935) removed the human labels by bootstrapping step values from whether the model eventually solved the problem — a direct answer to the sparse-reward problem of §2.1.
• The case against. PRMs are expensive to train and to score (one model call per step per candidate), their labels are noisy, and a PRM can itself be reward-hacked: the policy learns to produce steps that look checkable. The decisive datum is Kimi k1.5, whose recipe works “without relying on more complex techniques such as Monte Carlo tree search, value functions, and process reward models” (arXiv:2501.12599).
• The defensible position [as of 2026-10]: outcome and verifiable rewards dominate for training frontier reasoning models; PRMs survive as a search heuristic inside inference-time tree search, a data filter for constructing SFT traces, and an evaluation signal. They are not the default training reward. This is contested, not settled.

2.11 MCTS: the four phases

Monte Carlo Tree Search builds a tree by repeatedly running simulations from the root. Each simulation has four phases:

flowchart TD
    ROOT["root: state s_0 (the prompt)"]
    SEL["1. SELECTION<br/>descend by argmax(Q + U)<br/>until a node is not fully expanded"]
    EXP["2. EXPANSION<br/>add one new child (one action)"]
    EVAL["3. EVALUATION<br/>classical: random playout to terminal<br/>AlphaZero: v = f_theta(s), no playout"]
    BACK["4. BACKPROPAGATION<br/>walk the selection path<br/>update N(s,a) and Q(s,a)"]
    CHOOSE["move selection<br/>argmax_a N(s_0,a), or pi ~ N^(1/tau)"]

    ROOT --> SEL --> EXP --> EVAL --> BACK
    BACK -->|"budget remains"| SEL
    BACK --> CHOOSE

1. Selection. From the root, repeatedly pick the child maximising a bandit criterion (UCB1 / UCT / PUCT) until reaching a node that is not fully expanded.
2. Expansion. Add one or more new child nodes (in AlphaZero, one per simulation).
3. Evaluation. Estimate the value of the new node. Classical MCTS uses a random playout to a terminal state; AlphaGo/AlphaZero substitute the value network’s output $v=f_{\theta }(s)$. That substitution is the single most important change from classical MCTS, because a random playout in a game is cheap and in text generation is meaningless.
4. Backpropagation. Propagate the value back up the path from phase 1, updating $N(s,a)$ and $Q(s,a)$ at every edge on the path.

Then the move is chosen from the root statistics: $a=\arg {\max }_{a}N(s_0,a)$ (visit-count selection) or the search policy $\pi (a)\propto N(s_0,a{)}^{1/\tau }$.

Why MCTS is more robust than minimax with a learned evaluator — AlphaZero’s own argument, and it is a first-class insight for the LLM analogy:

“AlphaZero evaluates positions using non-linear function approximation based on a deep neural network … This provides a much more powerful representation, but may also introduce spurious approximation errors. MCTS averages over these approximation errors, which therefore tend to cancel out when evaluating a large subtree. In contrast, alpha-beta search computes an explicit minimax, which propagates the biggest approximation errors to the root of the subtree.”

In one sentence: averaging noisy value estimates is more robust than trusting one.

2.12 UCB1, every symbol

The criterion is from Auer, Cesa-Bianchi & Fischer 2002, Finite-time Analysis of the Multiarmed Bandit Problem, whose explicit form of the confidence width is $c_{t,s}=\sqrt{2\ln t/s}$:

$$a_t=\arg \underset{a}{\max }\left[{\bar{X}}_a+c\sqrt{\frac{2\ln t}{N_t(a)}}\right]$$

• $a$ — an arm. In MCTS, an action at a node.
• ${\bar{X}}_a$ — the exploitation term: the empirical mean reward of arm $a$ over the $N_t(a)$ times it has been pulled. Written $Q_t(a)$ in the action-value presentation. Without it the search never concentrates on what works — it degenerates into a uniformly-random sampler with extra bookkeeping.
• $N_t(a)$ — the number of times arm $a$ was pulled before step $t$. It is in the denominator, so a heavily-tried arm earns a smaller bonus. This is the term that makes the algorithm converge instead of exploring forever.
• $t$ — the total number of pulls so far. In UCT this becomes the parent node’s visit count $N(s)$.
• $\sqrt{2\ln t/N_t(a)}$ — the exploration bonus, and its shape is not arbitrary:
  • $\ln t$ in the numerator grows without bound but very slowly. That is exactly the rate needed to pull every arm infinitely often while still letting the empirical means dominate asymptotically. It comes from the Chernoff-Hoeffding one-sided confidence bound the paper applies to each arm’s mean.
  • $1/N_t(a)$ makes the bonus decay to zero as an arm is tried, which is what forces the search to eventually stop re-exploring a settled question.
  • $N_t(a)=0$ gives an infinite bonus, which is a feature, not a bug: it forces every arm to be tried at least once. Implementations special-case it rather than relying on floating-point infinity.
  • The square root converts the $1/N$ decay into a shape where the bonus is worth roughly the standard error of the mean estimate — the natural scale for “how uncertain am I about this arm”.
• $c$ — the exploration constant: the exchange rate between one unit of reward and one unit of the bonus. The $2$ inside the square root is UCB1’s Hoeffding constant; $c$ is the free scale (Sutton & Barto present the same rule with $c$ absorbing it, as $c\sqrt{\ln t/N_t(a)}$). Larger $c$ gives a wider, noisier search; smaller $c$ gives greedy descent into current beliefs. It is the one hyperparameter worth tuning here, and its correct value scales with the scale of the reward: double the reward units and you must double $c$ to keep the same behaviour. This is the most common tuning mistake in MCTS implementations.

2.13 UCT: the same rule, inside a tree

UCT is UCB1 applied recursively at every node of a tree (Kocsis & Szepesvári 2006). The only change is what the symbols mean:

• $t$ (total pulls at the bandit) becomes $N(s)$, the visit count of the node.
• ${\bar{X}}_a$ becomes $Q(s,a)$, the action value maintained by backpropagation: the mean of the values backed up through edge $(s,a)$.

UCT converges to the minimax value of the tree as simulations $\to \infty$, and it is the direct ancestor of PUCT.

2.14 PUCT: every symbol, and what each removal breaks

PUCT is the Predictor + UCT rule from Rosin 2011, Multi-armed bandits with episode context. Its distinguishing feature is that the exploration bonus is scaled by an external prior $P(a\mid s)$ — a prediction about which action is good, available before any simulation. AlphaGo Zero uses exactly this form:

$$a_t=\arg \underset{a}{\max }(Q(s_t,a)+U(s_t,a)),U(s,a)=c_{\text{puct}}\cdot P(s,a)\cdot \frac{\sqrt{{\sum }_{b}N(s,b)}}{1+N(s,a)}$$

Term by term, with the justification and the counterfactual:

• $s$ — the current state (a tree node). $a$, $b$ — actions (children). The ${\sum }_b$ ranges over all children of $s$; note that it is the parent’s total visit count, not the action’s. Using $N(s,a)$ in the numerator instead is a subtle and common bug: the bonus would then depend on the action it is meant to be correcting for, and heavily-visited actions would be rewarded with a bigger bonus.
• $Q(s,a)$ — the action value: the mean of the backed-up values observed on the simulations that passed through edge $(s,a)$. This is the exploitation term. Without it, the search is a random walk guided only by the prior — it spends its whole budget on whatever the network liked at the start and never revises.
• $U(s,a)$ — the exploration bonus, the “upper confidence” term. It is what makes the search revise. Remove it and you have greedy descent on the first value estimate: one unlucky evaluation on a good move prunes it forever.
• $P(s,a)$ — the prior probability of action $a$ in state $s$, produced by the policy network ($p=f_{\theta }(s)$ in AlphaGo Zero). This is the crucial difference from UCT, and it is what makes PUCT worth having: a strong prior tells the search where to look for free, so a hopeless branch can be deprioritised before any simulation is spent on it. Without $P$, the search spends budget rediscovering what the network already knows. It also makes the search asymmetric in a way UCT is not: two actions with identical $Q$ and identical visit counts are still ordered, because the network has an opinion.
• $N(s,a)$ — the number of times edge $(s,a)$ has been visited. It appears in $1+N(s,a)$, offset by one so the expression is finite at $N(s,a)=0$. Drop the $1+$ and the first visit to any action divides by zero. As an action is tried, its bonus decays; this is the term that forces the search to eventually stop re-exploring the same move.
• ${\sum }_{b}N(s,b)$ — the total visit count of the parent state: how much search budget the parent has already absorbed. Its square root is what gives the bonus the correct diminishing-returns shape. Doubling the parent’s budget multiplies the bonus by only $\sqrt{2}$, so exploitation can eventually win; with a linear numerator the bonus would grow as fast as the budget and the search would never converge. It is the same $\sqrt{\cdot }$ scaling job that UCB1’s confidence-width derivation produces.
• $c_{\text{puct}}$ — the exploration constant, AlphaGo Zero’s $c_{\text{puct}}$. Same role as UCB1’s $c$, and the same units problem: it is the price of exploration in reward units. AlphaZero notably reuses the same hyperparameters across Go, chess and shogi without game-specific tuning, which is a strong signal that the form of the rule matters more than the constant.

AlphaGo Zero’s own one-line gloss, which is the whole formula in a sentence: the rule “initially prefers actions with high prior probability and low visit count, but asymptotically prefers actions with high action-value.”

The symmetric failure modes, stated for recall:

2.15 The AlphaGo/AlphaZero/MuZero chain, and what each step removed

• AlphaGo (Silver et al. 2016, DOI 10.1038/nature16961): MCTS + PUCT + two networks (policy net and value net) + supervised bootstrapping from human games.
• AlphaGo Zero (Silver et al. 2017, DOI 10.1038/nature24270, public PDF): tabula rasa self-play, a single network $f_{\theta }(s)=(p,v)$ producing both the move prior and the value, no human data, and no random playouts — the leaf is evaluated by $v$. Each simulation “starts from the root state and iteratively selects moves that maximise an upper confidence bound $Q(s,a)+U(s,a)$, where $U(s,a)\propto P(s,a)/(1+N(s,a))$, until a leaf node $s^{\prime }$ is encountered.”
• AlphaZero (arXiv:1712.01815): the same algorithm and hyperparameters on chess and shogi. Training used 5,000 first-generation TPUs for self-play and 64 second-generation TPUs for training, 700k steps of minibatch 4,096, and 800 MCTS simulations per move; at evaluation it “selects moves greedily with respect to the root visit count”.
• MuZero (Schrittwieser et al. 2019, arXiv:1911.08265): removes the requirement of knowing the rules by learning a latent dynamics model that predicts exactly the three quantities MCTS needs — reward, policy, value — and plans inside it. This is the model-based RL datum the LLM world keeps re-deriving.

2.16 The connection to LLM reasoning, and its limits

The mapping. Token generation is action selection; “think step by step” is an implicit linear rollout; a tree search over reasoning steps is explicit planning. A reasoning step (a sentence, a line of algebra, a tool call) is the natural action granularity, which is why nearly all LLM tree-search methods work at the step level, not the token level.

The distinction that matters: inference time versus training time. Search can be used (a) at inference time, to spend more compute on one problem (ToT, RAP, LATS), or (b) at training time, to produce better data or a better value/policy target (MCTS-DPO, AlphaMath, expert iteration). Only (b) changes the weights. Both are test-time-compute techniques and must be costed as such: tree search multiplies the number of forward passes by roughly the branching factor times the depth, and every one of those forward passes is a full model call.

The limits, and the counter-evidence. This must not be omitted. Kimi k1.5 reports an RL recipe that explicitly avoids search:

“Long context scaling and improved policy optimization methods are key ingredients of our approach, which establishes a simplistic, effective RL framework without relying on more complex techniques such as Monte Carlo tree search, value functions, and process reward models.” — Kimi k1.5, arXiv:2501.12599

So the honest [as of 2026-10] statement is:

• MCTS is a live research direction and a legitimate inference-time technique, but the strongest scaling result for reasoning LLMs deliberately drops it. Do not present tree search as a required component of reasoning-model RL.
• The action space is the wrong shape for classical MCTS. A game has around 100 legal moves; a token step has around 100,000 (the vocabulary), and a reasoning step has an unbounded, near-continuous set of possible sentences. There is no cheap “expansion” operator, so every node costs a full generation.
• There is no cheap simulator. AlphaZero can play a random playout to the end of a game and get a real reward. A random playout of token generation produces garbage, so the leaf evaluation must come from a learned value or a heuristic judge — which puts all the weight back on the thing the value function was supposed to supply in the first place.
• The value estimate is the bottleneck. MCTS’s guarantee is an average over noisy values. If the per-node value is systematically wrong — as a self-evaluating LLM’s confidence often is — averaging does not help; it produces a confidently-wrong subtree.
• The cost is multiplicative and hard to amortise. $B$ branches at depth $D$ is on the order of $B\cdot D$ extra generations per problem, against one generation for greedy decoding and $n$ for best-of-$n$. Whether that beats $n$ independent samples at the same cost is an empirical question with no settled answer.

The defensible synthesis: use MCTS when you have a genuine value function and a cheap expansion operator; use best-of-$n$ or long-context RL when you do not. The honest evaluation for a specific project is a compute-matched comparison against best-of-$n$, and most published MCTS-for-reasoning results do not report one.

3. Implementation

3.1 GAE, implemented so the $\lambda$ endpoints are checkable

"""Generalized Advantage Estimation, with the endpoint identities asserted.

torch >= 2.0, CPU. This is PPO's advantage computation, isolated.
"""
import torch


def compute_gae(rewards: torch.Tensor,
                values: torch.Tensor,
                gamma: float = 1.0,
                lam: float = 0.95,
                mask: torch.Tensor | None = None):
    """GAE over one or more trajectories.

    Args:
        rewards: [T] per-step rewards. In LLM RL this is 0 for t < T-1, the RM
            score at t = T-1, plus -beta * log(pi/pi_ref) at EVERY step.
        values:  [T] critic outputs V(s_t); no extra V(s_T) is included.
        gamma:   discount. 1.0 in LLM RL.
        lam:     GAE lambda. 0.0 -> one-step TD, 1.0 -> MC return minus baseline.
        mask:    [T] 1 for real tokens, 0 for padding. Zeroing the accumulator at
            padding is mandatory: a padded step has no reward and no real value,
            and letting it through adds a constant to every later advantage.
    Returns:
        advantages [T], returns [T] (the value-regression targets).
    """
    T = rewards.shape[0]
    advantages = torch.zeros_like(rewards)
    last_gae = torch.zeros((), dtype=rewards.dtype)

    for t in reversed(range(T)):
        # Past the final step there is no next state, so the bootstrap is 0. The
        # same is true across the padding boundary: V(s_{t+1}) is only defined for
        # a real next token, otherwise the padding's value leaks into the last real
        # advantage.
        if t + 1 < T and (mask is None or mask[t + 1]):
            next_value = values[t + 1]
        else:
            next_value = torch.zeros((), dtype=values.dtype)
        # delta_t = r_t + gamma * V(s_{t+1}) - V(s_t)
        delta = rewards[t] + gamma * next_value - values[t]
        # A_t = delta_t + (gamma * lam) * A_{t+1}. Note the PRODUCT gamma*lam:
        # this is why lambda alone controls the estimator's horizon when gamma=1.
        last_gae = delta + gamma * lam * last_gae
        if mask is not None:
            last_gae = last_gae * mask[t]
        advantages[t] = last_gae

    # The critic regresses on the empirical return estimate, V_target = A + V.
    returns = advantages + values
    return advantages, returns


# --- checks that pin the endpoints ------------------------------------------
torch.manual_seed(0)
T = 40
rewards = torch.zeros(T)
rewards[-1] = 1.0                       # terminal-only reward, as in RLHF
values = torch.randn(T) * 0.5 + 0.5     # a deliberately imperfect critic

adv_mc, _ = compute_gae(rewards, values, gamma=1.0, lam=1.0)
adv_td, _ = compute_gae(rewards, values, gamma=1.0, lam=0.0)

# lambda = 1 must equal the Monte Carlo return minus the baseline V(s_t).
mc_return = rewards.sum()               # gamma = 1, single terminal reward
expected_mc = mc_return - values        # G_t - V(s_t) for every t
print("lambda=1 max abs error vs  G_t - V(s_t):",
      (adv_mc - expected_mc).abs().max().item())      # ~1e-7, floating point

# lambda = 0 must equal the TD residual at each step:
#   delta_t = r_t + gamma * V(s_{t+1}) - V(s_t), with V(s_T) = 0 past the end.
next_vals = torch.cat([values[1:], torch.zeros(1)])
expected_td = rewards + next_vals - values
print("lambda=0 max abs error vs  delta_t:",
      (adv_td - expected_td).abs().max().item())      # ~1e-7, floating point

Three implementation details in that function are where the bugs live:

• gamma * lam, not gamma or lam. The recursion ${\hat{A}}_t={\delta }_t+\gamma \lambda {\hat{A}}_{t+1}$ is the closed form of the geometric sum; writing the wrong product silently changes the effective horizon and is invisible in the loss curve.
• The padding mask multiplies the accumulator, not the output. Masking after the recursion would leave last_gae intact across the boundary and leak real values into padded positions.
• The final bootstrap is zero. That is correct for a terminal episode and not correct if the episode was truncated by a length cap rather than by EOS — then you should bootstrap from the truncated state’s value, or the agent learns that running out of budget is the same as finishing.

3.2 A from-scratch MCTS with PUCT

The skeleton to have in your head in an interview, small enough to write on a whiteboard: classical MCTS with a value-function leaf evaluation (the AlphaZero substitution). The defaults degrade gracefully — uniform priors give UCT, a random-playout value_fn gives classical MCTS.

"""MCTS with PUCT. Pure Python, no dependencies.

Caller supplies:
  actions(s) -> list of legal actions;  step(s, a) -> (next_state, reward)
  is_terminal(s) -> bool
  prior_fn(s) -> {action: P(s,a)}   (uniform if omitted)
  value_fn(s) -> float              (if omitted, a random playout evaluates the
                                     leaf and its accumulated reward is backed up)
"""
import math
import random
from dataclasses import dataclass, field


@dataclass
class Node:
    state: object
    parent: "Node | None" = None
    action: object = None                  # the action that led here
    prior: float = 1.0                     # P(s_parent, action)
    children: dict = field(default_factory=dict)
    N: int = 0                             # visits to THIS node
    W: float = 0.0                         # sum of backed-up values
    terminal: bool = False

    @property
    def Q(self) -> float:
        """Mean backed-up value; 0.0 when unvisited -- see the notes below."""
        return self.W / self.N if self.N > 0 else 0.0


def mcts(root_state, actions, step, is_terminal, n_sims,
         prior_fn=None, value_fn=None, c_puct=1.5, gamma=1.0):
    root = Node(root_state, terminal=is_terminal(root_state))

    for _ in range(n_sims):
        node, path = root, [root]

        # 1. SELECTION: descend while every child is expanded.
        while (not node.terminal and node.children
               and len(node.children) == len(actions(node.state))):
            total_N = sum(c.N for c in node.children.values())   # sum_b N(s,b)
            best, best_child = -float("inf"), None
            for a, child in node.children.items():
                # U(s,a) = c * P(s,a) * sqrt(sum_b N(s,b)) / (1 + N(s,a))
                u = c_puct * child.prior * math.sqrt(total_N) / (1 + child.N)
                if child.Q + u > best:
                    best, best_child = child.Q + u, child
            node = best_child
            path.append(node)

        # 2. EXPANSION: add exactly one new child.
        edge_reward = 0.0
        if not node.terminal:
            n_actions = len(actions(node.state))
            untried = [a for a in actions(node.state) if a not in node.children]
            a = random.choice(untried)
            prior = (1.0 / n_actions) if prior_fn is None else prior_fn(node.state)[a]
            nxt, edge_reward = step(node.state, a)
            node = Node(nxt, parent=path[-1], action=a, prior=prior,
                        terminal=is_terminal(nxt))
            path[-1].children[a] = node
            path.append(node)

        # 3. EVALUATION: value network, or a random playout to a terminal state.
        #    `value` is the return from this node onward: the network's estimate,
        #    or the rewards a random playout actually collects. The reward on the
        #    edge into this node is added either way -- `step` returns the signal.
        if node.terminal:
            value = 0.0
        elif value_fn is not None:
            value = value_fn(node.state)          # AlphaZero: v = f_theta(s)
        else:
            s, value = node.state, 0.0
            while not is_terminal(s):
                s, r = step(s, random.choice(actions(s)))
                value += r                        # gamma = 1 in the LLM setting
        value += edge_reward

        # 4. BACKPROPAGATION
        for n in reversed(path):
            n.N += 1
            n.W += value * (gamma ** 0)           # gamma = 1 in the LLM setting

    # Root move selection uses visit counts, not Q -- see the notes below.
    return max(root.children.items(), key=lambda kv: kv[1].N)[0] if root.children else None

Five details in that skeleton are exactly the ones to talk about:

• The reward comes out of step, and the backup must carry it. step(s, a) returns (next_state, reward); the code adds the edge reward into the leaf’s value and accumulates every reward the random playout collects before backing the total up the path. Discard the step return — as an earlier version of this skeleton did — and every leaf evaluates to 0.0, so the search has no signal to maximise and its visit counts are noise. A random-playout value_fn is only meaningful in a reward-bearing game; for a generic search with no reward, pass an explicit value_fn instead of silently evaluating to zero.
• Q returns 0.0 for an unvisited child, which is why the $1+N(s,a)$ offset and the prior matter so much: a fresh child’s score is entirely $U$, and $U$ is proportional to its prior. So the initial order of exploration is the network’s prior order — the free pruning of §2.14. Whether 0.0 is right depends on the reward scale: with all-negative rewards it is an optimistic initialisation, which is a legitimate design choice but must be made deliberately.
• total_N is the sum over children. Here it equals node.N because every backprop increments the node, but the distinction matters if you prune or lazily materialise children — and using N(s,a) in the numerator is the bug of §2.14.
• Root move selection uses N, not Q. Visit count is lower-variance and is what AlphaZero uses; a single high $Q$ from few visits is exactly the noisy estimate MCTS exists to smooth away.
• gamma ** 0 is written out to make the discounting choice explicit. In a tree you control the horizon locally; in a long-horizon game you would apply gamma ** depth on backup. Writing it out stops it silently becoming a no-op.

3.3 The knob table

4. Numbers and trade-offs

4.1 The variance of a Monte Carlo baseline is not a metaphor

Take the RLOO-style setup from GRPO: $G$ completions per prompt, a binary reward, a pass rate $p$. The group-mean baseline has variance $p(1-p)/G$ as an estimate of $V$. (example) At $p=0.5$:

The baseline’s noise falls as $1/\sqrt{G}$, so going from $G=8$ to $G=64$ buys an 8x-variance-reduced baseline for 8x the rollout tokens. That is the exchange rate GRPO offers, and it is why $G$ is typically 8-16 rather than 64: the marginal variance reduction stops paying for itself, and the tokens are better spent on more prompts, which reduces the variance of the outer expectation instead.

4.2 What a forward pass costs, and therefore what search costs

The number that governs whether tree search is affordable: a search budget of $S$ simulations at branching factor $B$ and depth $D$ costs on the order of $S$ extra model evaluations per decision (every selection-expansion-evaluation cycle needs at least one leaf evaluation), against $n$ for best-of-$n$.

(example) At 800 simulations per decision, the search spends 800 leaf evaluations, and with a value network each leaf evaluation is one forward pass over the prefix. Generating the answer instead costs about one forward pass per token, so a 300-token response is roughly 300 forward passes. Put both on the same axis: a per-problem budget of 16 full responses is $16\times 300=4,800$ forward passes, so the compute-matched search budget is roughly 4,800 simulations, not 800. Comparing 800 simulations against best-of-50 silently mixes a per-decision count with a per-problem one. Almost no published MCTS-for-LLM-reasoning result is compute-matched against best-of-$n$ in these units, and you should say so when you cite one.

4.3 Where each method sits on the cost axis

Read the last two rows together. Best-of-$n$ requires nothing but a scorer and buys a real improvement in expected reward; MCTS requires a value function for partial states and buys lookahead. The AlphaZero evidence says the value function is worth it when you have it, because self-play generates an unlimited supply of ground-truth outcomes to train it on. Reasoning problems do not come with an unlimited supply of partial-state labels, which is the structural reason search has not displaced sampling here.

4.4 The $\lambda$ trade-off, made concrete

(example) For a 400-token response with a single terminal reward and a critic with per-step error $ϵ$, the bias of the GAE estimator is approximately $ϵ\cdot \gamma \lambda /(1-\gamma \lambda )$ — the geometric sum of the critic’s errors along the trajectory — while the variance scales roughly with the effective number of terms, $1/(1-\gamma \lambda )$. At $\gamma =1$:

The table is illustrative rather than measured, but the shape is the point: bias and variance both grow as $\lambda \to 1$, with the variance the larger of the two, and the reason to use 0.95 rather than 0.99 is that both are about five times smaller at 0.95 — 0.99 buys a longer effective horizon at roughly five times the bias and five times the variance. The N+ reproduction’s verified value is $\lambda =0.95$, $\gamma =1.0$.

5. Pitfalls

Writing $\gamma$ instead of $\gamma \lambda$ in the GAE recursion. Symptom: the advantages are systematically scaled wrong, the policy learns much faster or much slower than an identical run with a different $\lambda$, and the loss curve shows unstable spikes. Nothing looks wrong, because both symbols are floats.

Forgetting the padding mask in GAE. Symptom: the advantages of short responses in a padded batch are inflated by the accumulated sums of their padding positions, so the policy preferentially reinforces whatever came last in short responses. The bug is invisible in aggregate metrics and obvious in a per-token advantage histogram.

Truncating an episode without bootstrapping. You hit the max length cap and treat the last token as terminal. Symptom: the model learns to stop early on problems it cannot solve, because running out of room is scored exactly like finishing. DAPO’s overlong reward shaping and OpenRLHF’s --reward.overlong_penalty_factor exist because this is common and expensive.

Setting $\gamma <1$ “for stability”. Symptom: the model produces progressively shorter answers and the reward curve improves on short tasks while long-form quality degrades. With a terminal reward, discounting is a length penalty with no justification.

Tuning $c$ for PUCT/UCB without rescaling when the reward changes. Symptom: the search either explores uniformly forever (constant too large) or commits to the prior’s first guess (constant too small), and the behaviour changes discontinuously when you switch reward models. $c$ is in reward units; change the reward and you have changed $c$.

Using $N(s,a)$ instead of ${\sum }_{b}N(s,b)$ in the PUCT numerator. Symptom: search quality degrades in a way that is hard to attribute — exploration and exploitation become entangled, and increasing the simulation budget stops helping.

Trusting the prior with no exploration term. Symptom: only the top-$k$ tokens the policy net likes are ever expanded, so the search can never discover that the network’s second choice was better. This is the failure mode that makes pure policy-guided decoding look deceptively good on easy problems.

Assuming MCTS will beat sampling because it is “smarter”. Symptom: an expensive evaluation-time search that loses to best-of-$n$ at equal compute, on problems where the value function is unreliable. Always compute-match against best-of-$n$, and report the value function’s own accuracy alongside.

Treating the leaf evaluation as free. Symptom: you use the LLM’s own token log-likelihood as the value, and the search confidently prefers short, fluent, confident-sounding continuations. Likelihood is not correctness; a value function must be trained on outcomes, not derived from the policy’s fluency.

Believing RLVR capability gains are settled. Symptom: you design an evaluation around pass@1 only, and miss that the base model may already have solved the problem at large $k$. The dispute between Yue et al. 2025 (redistribution) and ProRL (expansion) is unresolved; report both pass@1 and pass@k and say the question is open.

6. Using it in a project

6.1 Which estimator to reach for

1. Single-turn, outcome reward, cheap scoring (the RLVR default). Use Monte Carlo with a group baseline: GRPO/RLOO. No value function, no bootstrap, no critic-bias problem. You pay $G$x the rollouts and the only bias is the group’s sampling noise.
2. Dense or shaped reward, long horizon, a value estimate you trust. Use GAE with a critic (PPO). This is where the bias-variance dial earns its keep. VAPO (arXiv:2504.05118) is the strongest published counter-argument to the “critic-free always” position, reporting 60.4 on AIME 2024 with Qwen-32B.
3. Multi-turn or agentic. The bandit framing is gone; you need either a critic or a carefully designed per-turn reward. This is where credit assignment becomes the whole problem.
4. You have a value function and a cheap expansion operator. Only then consider MCTS, and compute-match it against best-of-$n$.

6.2 When NOT to use each of these

• When NOT to use GAE: when you cannot fit a value function. Fitting a critic to predict the terminal reward of a 32k-token chain of thought is genuinely hard, and a bad critic turns $\lambda =0$ into noise and $\lambda =1$ into a slower Monte Carlo. If your value loss is not going down, use a critic-free method instead of tuning $\lambda$.
• When NOT to use Monte Carlo: when episodes are very long and the reward is dense. A 10,000-step agentic episode with per-turn rewards has an enormous return variance, and bootstrapping is the only way to make the gradient usable.
• When NOT to use MCTS: when leaf evaluation is expensive and unreliable, which is the normal case for LLM reasoning. Also when the branching factor is large and the expansion operator is a full generation — you are paying a generation per node to explore a space where the value estimate has no ground truth. If your value function is a self-evaluating LLM’s confidence, you do not have a value function.
• When NOT to use importance sampling: when the behaviour and target policies are far apart. The ratio’s variance blows up; fix the staleness (fewer PPO epochs, fresher weights, async weight sync) rather than adding a clip and hoping.
• When NOT to use a learned baseline at all: in a single-turn task with a cheap reward, the group mean is unbiased, needs no training, and cannot be attacked. A learned critic is a second model to fit, serve, and hack.

6.3 The two dials people confuse

• $\gamma$ changes the problem. It decides what the agent is trying to achieve over what horizon. Changing it changes the optimal policy.
• $\lambda$ changes only the estimator. It decides how you measure the advantage for a fixed objective. It cannot change the optimum, only how fast and how stably you get there.

If you are tuning $\lambda$ and the behaviour changes qualitatively, something else is wrong: either the value head is bad enough that the estimator’s bias dominates, or the ratio correction is off, or the reward is not what you think it is.

7. How you would prove it worked

7.1 Proving the estimator choice mattered

Run the identical RL setup from an identical checkpoint, varying exactly one thing:

1. $\lambda \in \{0,0.95,1.0\}$ with everything else fixed. (example) In sparse-reward LLM RL the usual shape is: $\lambda =0$ is unstable and plateaus early (critic bias dominates), $\lambda =1$ has the highest variance and a noisy reward curve, $\lambda =0.95$ is in between and usually best. Report the variance of the advantage estimate within a batch for each arm — that is the mechanism, not just the outcome.
2. Critic-free versus critic at equal rollout budget. GRPO at $G=8$ against PPO with a critic, matched on generated tokens rather than on gradient steps. (example) The common outcome on verifiable reasoning is that the critic-free arm wins on both stability and final accuracy, and the critic arm wins on sample efficiency per generated token early in training.
3. Search versus sampling at equal compute. MCTS with $S$ simulations against best-of-$n$ with $n\approx S$. This is the comparison the literature is missing and the one an interviewer will ask about.

7.2 The diagnostics worth logging

The explained variance of $V$ is the most under-used diagnostic here. It is a single number answering “is the value function worth having at all”. If it is negative, the critic is worse than predicting the batch mean and is actively harmful; switch to a group baseline the same day.

7.3 The MCTS-specific ablation

If you do use search, the only honest evaluation has four arms, all compute-matched: (1) greedy decoding; (2) best-of-$n$ with a verifier or reward model; (3) MCTS with uniform priors and the same value function (i.e. UCT); (4) MCTS with the trained prior (PUCT). Arm 3 versus 4 isolates the value of $P(s,a)$; arm 2 versus 3 isolates the value of search at all. (example) A common result is that arm 2 wins, because the value function is the bottleneck — and reporting that honestly is more valuable than reporting the arm where search won.

8. Interview drill

“Why do you need an advantage instead of just using the return?”

Strong answer: because the policy-weighted mean advantage is zero, so subtracting a baseline that does not depend on the action leaves the gradient’s expectation unchanged while reducing its variance. The return alone has variance that grows with horizon and, with a terminal binary reward, is a single Bernoulli draw. The advantage measures surprise rather than outcome, so a solved-easy-problem sample contributes almost nothing to the gradient while an unexpected success contributes a lot.

Common wrong answer: “the return is biased.” It is not; it is unbiased and high-variance. Confusing the two is the fastest way to fail this question.

“Monte Carlo or TD?”

Strong answer: MC targets the full empirical return — unbiased, high variance, needs the episode to end. TD targets $r_t+\gamma V(s_{t+1})$ — biased by exactly the value function’s error, low variance, online. Which is right depends on whether you can fit $V$. In LLM RL with terminal rewards and long responses, $V$ is hard to fit, which is a structural argument for the critic-free Monte Carlo methods.

Follow-up: “so why does PPO work at all in RLHF?” Because the per-token KL penalty makes the reward dense, so the TD residual at each step carries real information even though the RM reward is terminal.

“Walk me through GAE. What is $\lambda$ doing?”

Strong answer: GAE is ${\sum }_l(\gamma \lambda {)}^l{\delta }_{t+l}$, the exponentially weighted sum of TD residuals. $\lambda$ sets the effective decay $\gamma \lambda$ and therefore moves the estimator between its two endpoints: $\lambda =0$ is the one-step TD residual $r_t+\gamma V(s_{t+1})-V(s_t)$, and $\lambda =1$ telescopes to $G_t-V(s_t)$, the Monte Carlo return minus a baseline. The $(1-\lambda )$ factor normalises the weights so the scale does not move with $\lambda$. Standard is $\lambda =0.95$, $\gamma =1$.

Common wrong answer: “$\lambda$ is the discount factor.” No — $\gamma$ is. $\lambda$ is the estimator’s bias-variance decay, and the paper’s specific point is that they are separable: $\gamma$ sets the horizon of the problem, $\lambda$ tunes the estimator.

“Why is $\gamma =1$ in LLM RL?”

Strong answer: the episode is one bounded response with the reward at the end, so a discount would make the objective depend on where the answer ended. It would behave as an implicit length penalty with no justification. The cost is that you lose the main variance-control knob, which is why $\lambda$ carries the burden.

“What is importance sampling for, and what is the problem with it?”

Strong answer: it corrects the distribution mismatch when the data comes from a behaviour policy $\mu$ rather than the current policy. The per-action ratio ${\pi }_{\theta }(a\mid s)/\mu (a\mid s)$ is exactly PPO’s $r_t(\theta )$ with $\mu ={\pi }_{{\theta }_{\text{old}}}$. It is unbiased but has unbounded variance when the ratio is heavy-tailed, which is why every practical implementation clips, truncates or masks it.

Follow-up: “name three ways LLM RL is off-policy even though it is called on-policy.” PPO’s multiple epochs over one batch; minibatching within an epoch; and the training/inference engine logprob mismatch. A fourth: top-p sampling truncation changes the action space and breaks the IS identity outright.

“Derive the PUCT formula’s terms and tell me what happens if I remove one.”

Strong answer: the score is $Q+U$ with $U=c_{\text{puct}}P(s,a)\sqrt{{\sum }_{b}N(s,b)}/(1+N(s,a))$. $Q$ is exploitation — the mean backed-up value over simulations that visited the edge; remove it and the search never revises the prior and becomes a prior-guided random walk. $P$ is the network’s prior, which lets hopeless branches be pruned before any simulation is spent; remove it and you are back to plain UCT with uniform priors, paying full price to rediscover what the network knew. $c_{\text{puct}}$ is the exploration price in reward units and must be rescaled with the reward. ${\sum }_{b}N(s,b)$ in the numerator, square-rooted, makes the bonus grow with the parent’s budget but at a diminishing rate, so exploitation can eventually win; un-square-rooted, the search never converges. $1+N(s,a)$ in the denominator makes the bonus decay as the edge is tried and keeps the expression finite at $N(s,a)=0$; drop the offset and you divide by zero.

Common wrong answer: describing $U$ as “random exploration”. It is not random — it is a directed bonus, largest exactly where the prior is confident and the edge is under-explored.

“Why does MCTS beat minimax with a neural evaluator?”

Strong answer: because minimax propagates the largest approximation errors to the root, while MCTS averages over them so they cancel. AlphaZero’s own stated reason. The corollary for LLMs is less comfortable: the averaging argument only helps if the errors are roughly independent across the subtree. A value estimator with a systematic bias — a self-evaluating LLM that prefers confident-sounding text — produces averaged errors, not cancelled ones.

“Should you use MCTS for LLM reasoning?”

Strong answer: not by default. It is a legitimate inference-time technique with a real research literature (ToT, RAP, LATS, rStar), but the strongest published scaling result for reasoning LLMs deliberately drops it: Kimi k1.5’s recipe works “without relying on more complex techniques such as Monte Carlo tree search, value functions, and process reward models”. The structural reasons are the action space (a reasoning step has no cheap expansion operator), the absence of a cheap simulator, and the fact that the leaf value estimate is the bottleneck. If you do use it, compute-match against best-of-$n$ and report the value function’s accuracy.

Common wrong answer: “yes, search is strictly better than sampling because it looks ahead.” Lookahead is only worth paying for when the leaf evaluation is better than the sampling estimate it replaces, and in this domain it usually is not.

“Is RLVR teaching models new reasoning, or just sharpening what they had?”

Strong answer: genuinely contested, and say so. Yue et al. argue RLVR sharpens pass@1 by concentrating on paths the base model already had, without raising pass@k at large $k$; ProRL reports prolonged RL does expand the reasoning boundary. Both are primary sources; neither has been refuted. The practical consequence is to report both pass@1 and pass@k and to distrust any claim based on pass@1 alone.

Next: RL Frameworks — these estimators are cheap to write down and expensive to schedule: the rollout/training boundary, weight synchronisation, and the colocated-versus-disaggregated choice are what the frameworks exist to manage.