When Does Branching Pay? An Exact Variance Analysis of Tree-Structured Policy Gradients

Group-relative policy gradient methods sample a fixed number of independent completions per prompt, so the rollouts share nothing but the prompt. A growing literature makes use of tree-structured policy gradient estimators instead, branching at chosen points guided by heuristics. We formalize such designs as a pair $(\beta ,\alpha )$: a kernel $\beta$ that decides where and how much to branch, and an anchor map $\alpha$ that decides which ancestor supplies each edge's baseline group. For any such pair, we give an exactly unbiased on-policy gradient estimator and, to our knowledge, the first exact variance decomposition for tree policy gradients with adaptive branching and group baselines. From it, we derive design principles for where to branch and how to form baseline groups, and identify regimes in which branching does not help. We test these predictions on reasoning and multi-turn agentic tool-use tasks with verifiable rewards.