Tree-Aware Posterior Distillation for Long-Horizon Agentic Reinforcement Learning

• Terminal-only rewards make turn-level supervision sparse and high-variance, while sequential mini-batch updates cause policy staleness as the current policy departs from the behavior policy.Broadcasting one trajectory-level advantage can over-credit unhelpful actions in successful trajectories and penalize useful steps in failed ones.Source: §1 · p. 1
• Shared-prefix branching isolates alternative continuations, letting recursive backup derive implicit turn credit directly from terminal rewards without auxiliary value or reward models.Independent trajectories confound the turns along each rollout.Source: §1 · p. 2
• Importance-sampling ratios and clipping constrain policy drift but leave a fixed-credit ascent direction without a finite destination for sequential updates.The paper seeks an objective that adapts its gradient as the current policy evolves, stopping at the target and reversing after overshoot.Source: §1 · p. 2
• TreeOPSD maps backed-up credit to a frozen behavior-relative teacher and distills the student toward it; its tangent at the behavior policy recovers the tree policy-gradient direction.Figure 1 separates outcome-derived target construction from student–teacher distribution matching.Source: §1 · p. 2, Figure 1 · p. 2
• TreeOPSD improves over matched-budget baselines at both scales on Multi-Hop QA and Deep Research, with larger gains on the longer-horizon setting.The introduction also reports longer-horizon agent behavior with more interaction turns in Deep Research.Source: §1 · p. 2

2.1 Agentic reinforcement learning

• In ReAct, nonterminal turns contain thought and tool actions followed by environment observations, while only policy-generated tokens receive gradients.Observation tokens enter as fixed context and are masked from the policy loss.Source: §2.1 · p. 3
• The setup focuses on binary or sparse rule-based outcome rewards, with no explicit reference penalty and no direct supervision for intermediate turns.Source: §2.1 · p. 3

2.2 Initialize-then-expand rollout trees

• Initialize-then-expand sampling retains complete behavior-policy rollouts and adds fresh terminal suffixes from sampled nonterminal prefixes, merging shared turns into a tree.The branched set is designed to match the expected rollout budget of full trajectories in GRPO.Source: §2.2 · p. 3

2.3 Tree-based turn credit

• Terminal trajectory rewards are standardized into leaf advantages, then recursively backed up through the tree using behavior-policy likelihood weights to assign turn credit.Each tree node enters the gradient once after its credit aggregates outcomes from branches below it.Source: §2.3 · pp. 3–4
• The resulting prompt-level direction weights each policy-generated token in turn i by V_i/L_x and matches the tree policy-gradient ascent direction at the behavior policy.Source: §2.3 · p. 4

3 TreeOPSD

• TreeOPSD turns sparse terminal outcomes into dense turn-level credit by branching continuations from shared prefixes and backing rewards up the rollout tree.Each turn is treated as a node, with its scalar credit attached to the complete realized turn span.Source: §3.1 · p. 4

3.1 Behavior-relative turn distributions

• The behavior-relative posterior uses a per-token average log-likelihood ratio, avoiding compounded turn-length discrepancies and a partition function over unsampled continuations.Normalizing the current-to-behavior likelihood ratio against the behavior baseline yields a two-point Bernoulli posterior.Source: §3.1 · p. 5

3.2 Teacher construction

• A forward-KL trust region maps backed-up credit to a closed-form affine teacher, with temperature calibrated to keep targets bounded at every tree depth.The affine teacher is the unique symmetric radius-calibrated map that commutes with convex tree backup.Source: §3.2 · p. 6

3.3 Distribution matching and off-policy analysis

• Matching a backed-up parent teacher gives the same gradient as aggregating descendant-leaf distillation losses, enabling each unique turn to be scored once.The affine credit-to-target map commutes with tree backup, preserving shared-prefix credit without repeating prefixes across leaves.Source: §3.3 · pp. 6–7
• At the behavior policy, TreeOPSD recovers the tree policy-gradient direction; as the policy drifts, its bounded correction vanishes at the finite target and reverses after overshoot.The correction counteracts policy shift without the exponential variance of multiplicative importance ratios.Source: §3.3 · p. 7

3.4 Practical optimization

• Training freezes behavior-policy teachers once per rollout tree, then recomputes student posteriors and updates against those teachers in each sequential mini-batch.The implementation assigns token-level loss-gradient weights from the current student–teacher posterior gap.Source: §3 · p. 4, §3.4 · p. 8

4.1 Experimental setup

• The evaluation covers Multi-Hop QA and Deep Research, using Qwen3-4B and Qwen3-30B-A3B models and exact match, with four test sets contributing to each scenario average.Multi-Hop QA trains on HotpotQA; Deep Research trains on OpenResearcher and includes closed-corpus and open-web evaluations.Source: §4.1 · pp. 8–9

4.2 Main results

• Deep Research averages rise from 13.07 to 15.45 for Qwen3-4B and from 17.59 to 21.20 for Qwen3-30B-A3B with TreeOPSD over TreePO.TreeOPSD has the highest Multi-Hop QA and Deep Research averages at both scales; Table 1 summarizes performance across four test sets per scenario.Source: §4.2 · p. 9, Table 1 · p. 9

4.3 Pointwise credit and the posterior map

• Pointwise credit Vc can raise two useful children together, whereas group-relative Vc−Vi can assign them opposite updates and leave their combined probability near the behavior policy.On BrowseComp-Plus with Qwen3-4B, the pointwise curve lies above the listwise control.Source: §4.3 · pp. 9–10
• The odds teacher’s affine map commutes with tree backup, while the logistic map does not; on BrowseComp-Plus, the odds-map curve lies above the logistic control.The two maps can match the first update, but the student then stops at the odds teacher.Source: §4.3 · p. 10, Figure 5 · p. 10

4.4 Rollout allocation and target-radius sensitivity

• At half budget, the (2, 2) rollout split improves over flat (4, 0), while the passage also notes a match on Deep Research without identifying its comparator.At the same budget, (4, 2) raises both averages and outperforms the more continuation-heavy (2, 6) split.Source: §4.4 · p. 10
• Both averages peak at the default target radius, and Deep Research varies more with radius than Multi-Hop QA while remaining close to its peak across the sweep.The first optimizer block is independent of radius; later blocks move toward teachers whose distance from 1/2 is set by the radius.Source: §4.4 · p. 11, Table 2 · p. 11

5 Conclusion

• TreeOPSD combines shared-prefix tree backups of terminal rewards with Forward-KL matching to a finite teacher relative to the behavior policy.The framework is critic-free and is designed for long-horizon agentic RLVR.Source: §5 · p. 11
• The affine target commutes with tree backup, and distillation recovers the tree policy-gradient direction at the behavior policy before stopping or reversing after overshoot.The sequential updates use neither a learned critic, process labels, nor an external teacher.Source: §5 · p. 11
• TreeOPSD improves over matched-budget baselines at both scales on Multi-Hop QA and Deep Research, with a much larger gain on Deep Research.Source: §5 · p. 11

A Related Work

• TreeOPSD derives turn targets from verifiable outcomes and optimizes acquired rollout trees, complementing methods that allocate sampling across prompts or turn-level prefixes.The cited work distinguishes tree acquisition, credit assignment, and policy optimization as separate decisions.Source: A Related Work · p. 17
• TreeOPSD backs sibling continuation evidence into turn credit while retaining value shared by useful continuations, using behavior-relative Bernoulli targets and Forward KL rather than a closed sibling choice set.Its targets provide a finite destination for policy updates, unlike fixed-credit gradients that do not specify one.Source: A Related Work · pp. 17–18

B.1 Calibrated affine targets on a fixed tree

• The affine teacher is the unique symmetric credit-to-target map with the specified radius, and applying it before or after normalized tree backup leaves the parent target unchanged.The fixed-tree analysis bounds backed-up turn credit and establishes a target radius for the affine map.Source: §B.1 · p. 18

B.2 Exact Forward-KL aggregation

• A backed-up parent teacher produces the same shared-turn gradient as aggregating descendant distillation losses, while descendant turns retain their own policy scores and targets.The equivalence applies to a complete cut below the shared turn, including terminal descendants or children.Source: §B.2 · p. 19

B.3 On-policy tangent and off-policy drift analysis

• TreeOPSD matches fixed-credit optimization at the on-policy first mini-batch, then departs with accumulated score drift; reducing its Forward-KL loss monotonically improves the proximal objective by the same amount.The departure is proportional to off-policy score drift accumulated across subsequent mini-batches.Source: §B.3 · pp. 20–21

C.1 Tree acquisition, credit assignment, and policy optimization

• TreeOPSD updates a sampled tree using normalized child weights and behavior-relative targets, while rollout acquisition and credit assignment remain distinct decisions.The same target construction can pair with random branching, learned rollout allocation, or other tree samplers.Source: §C.1 · p. 21

C.2 Independent turn targets and pairwise preferences

• Independent behavior-relative turn targets can raise all sampled useful continuations, and unlike hard pairwise preferences they stop at finite targets while retaining nonzero mean credit.For two siblings with centered credits, the behavior-policy tangent is proportional to the usual pairwise direction.Source: §C.2 · p. 21

C.3 Finite-target feedback under sequential optimization

• Across sequential blocks, recomputed student–teacher residuals reduce, stop, or reverse updates; unlike clipping, the bounded teacher specifies a destination.The target radius bounds the target probability and the geometric-mean likelihood ratio of the observed turn.Source: §C.3 · pp. 21–22

C.4 Limitations and future work

• With ρ=0.25 and K=12, teacher RMS displacement is about 0.075 when rewards are not all equal; only one dissenting leaf reaches the full radius.Allocators favoring mixed outcomes move trees toward balanced rewards, motivating a radius set from realized credits or K.Source: §C.4 · p. 22
• Replayed-tree credits average continuations from the collecting policy and therefore age as the policy improves.Weighting stored trees by off-policiness is proposed to account for that aging.Source: §C.4 · p. 22
• Current-task KL does not control drift on prior-task distributions, so post-training can still forget across task sequences.The authors propose mixing stored trees from earlier environments, with logged behavior probabilities, into later batches.Source: §C.4 · p. 22

D.1 Applicability to other model families

• The Llama-3.2-3B-Instruct run begins from a weaker ReAct initialization, while TreeOPSD stays ahead of GRPO through the rest of training.Source: §D.1 · p. 22
• TreeOPSD has the highest Multi-Hop QA average on both Qwen3-1.7B and Llama-3.2-3B-Instruct.Figure 6 shows training accuracy curves for these models; the table caption identifies the four-test-set comparison.Source: §D.1 · p. 22, Table 3 · p. 23, Figure 6 · p. 23

D.2 Controlled numerical studies

• After the student passes the teacher, TreeOPSD’s residual changes sign, stopping updates at the finite target; TreePO instead retains its collection-time credit.Both methods share the tree-policy-gradient tangent at the behavior policy.Source: §D.2 · p. 23
• Across five seeds, TreeOPSD consistently outperforms competitive baselines on the Multi-Hop QA and Deep Research averages.Table 4 reports mean ± standard deviation for Qwen3-4B-Thinking-2507.Source: Table 4 · p. 24
• The odds map with Forward KL preserves the parent gradient because its affine teacher map commutes with backup; logistic mapping and Reverse KL do not.Listwise group-relative credits are centered under backup weights and therefore cannot raise both useful children relative to the behavior policy.Source: §D.2 · p. 24

D.3 Interaction length and training efficiency in Deep Research

• On BrowseComp-Plus, TreeOPSD uses more assistant turns at evaluation and later in training, while its accuracy remains above GRPO within GRPO’s measured training-time budget.The comparison is plotted against cumulative training time, not only policy updates.Source: §D.3 · p. 24, Figure 8 · p. 24

D.4 Stability across training seeds

• Across five Qwen3-4B-Thinking-2507 seeds, TreeOPSD–TreePO and TreeOPSD–GRPO gaps keep the same order; the remaining method gap is residual matching versus fixed credit.Variation also reflects collected rollouts and checkpoint choice within the evaluation window.Source: §D.4 · pp. 24–25

E.1.1 Multi-Hop QA

• Multi-Hop QA training uses all 90,447 HotpotQA distractor training questions, a local E5 Wikipedia retrieval server, and at most four tool-calling turns per rollout.Evaluation covers HotpotQA, 2WikiMultiHopQA, MuSiQue, and Bamboogle; training uses thresholded token F1 while reported curves use exact match.Source: §E.1.1 · p. 25

E.1.2 Deep Research

• Deep Research uses one prompt for each of 6,102 unique MiroVerse questions and closed-corpus retrieval for BrowseComp-Plus training and evaluation.Final evaluation covers BrowseComp-Plus, BrowseComp, GAIA, and xbench-DeepSearch; exact match is reported without the training reward’s well-formed-answer bonus.Source: §E.1.2 · p. 25

E.2 Models

• The main experiments use Qwen3-4B-Thinking-2507 and Qwen3-30B-A3B-Thinking-2507; Appendix D.1 adds Qwen3-1.7B and Llama-3.2-3B-Instruct.Source: §E.2 · p. 25

E.3 Training and evaluation settings

• TreeOPSD uses M=4, N=2, likelihood-weighted backup, ρ=0.25, and E=4 sequential Forward-KL blocks with unique-turn reconstruction.Training uses bfloat16, AdamW, and no auxiliary KL penalty or entropy regularization.Source: §E.3 · p. 26
• Multi-Hop QA collects 256 prompts across four blocks and caps rollouts at five assistant turns; Deep Research collects 128 prompts and allows 60 training turns.BrowseComp-Plus evaluation allows 80 assistant turns, with evaluation every five updates in both settings.Source: §E.3 · p. 26

E.4 Baselines and rollout-budget control

• TreePO shares TreeOPSD’s trees, backed-up credits, unique-turn reconstruction, prompt normalization, and optimizer blocks, but uses fixed credit rather than a finite posterior target.Source: §E.4 · p. 26
• TreeOPSD’s M=4, N=2 tree retains 12 terminal leaves while its expected rollout cost matches GRPO’s eight full rollouts per prompt.Branch continuations start from intermediate prefixes and have roughly half the generation cost of root rollouts.Source: §E.4 · p. 26

F Data Examples

• Each serialized RL row stores the chat prompt, target, and per-example tool-routing metadata, but no teacher trajectory or hidden evidence.Source: F Data Examples · p. 27

F.1 Multi-Hop QA (HotpotQA)

• HotpotQA records use a Search-R1 question prompt and search the fixed Wikipedia-2018 index for the top three passages, with queries truncated at 512 characters.The example asks which of Arthur’s Magazine or First for Women started first; its rule-based target is Arthur’s Magazine.Source: §F.1 · pp. 27–28

F.2 Deep Research (OpenResearcher)

• Deep Research training rows use unique OpenResearcher questions after discarding teacher messages, while evaluation uses the same interface with BrowseComp-Plus or Serper.The example asks whether Neil Patrick Harris narrated the Henry Huggins audiobook; its target answer is yes.Source: §F.2 · pp. 28, 30