TreeHCA: Hindsight-Guided Exploration and Credit Assignment for Multi-Turn LLM Agents

# TreeHCA: Hindsight-Guided Exploration and Credit Assignment for Multi-Turn LLM Agents
Source: [https://arxiv.org/html/2610.12828](https://arxiv.org/html/2610.12828)
Jeremy CarletonSushil VemuriSrinivas ShakkottaiDileep KalathilAffiliation:Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA

###### Abstract

Outcome\-supervised group\-relative policy optimization \(GRPO\) gives every token in an LLM agent’s trajectory the same advantage, leaving useful and unhelpful decisions undifferentiated\. Hindsight credit assignment \(HCA\) can refine this feedback, but its estimates depend on trajectories containing informative alternatives at consequential histories\. We introduceTreeHCA, which couples*sampling via hindsight ratios*to generate these alternatives with*hindsight credit assignment*to evaluate their contribution\. We use changes in reference\-answer likelihood to revisit intermediate histories and select alternative continuations, forming a tree of reasoning and tool interactions\. This exploration changes the distribution of sampled continuations\. We derive the corresponding inverse\-hindsight importance correction, including an exact finite\-pool identity, and use its structure in a normalized tree backup that propagates terminal outcomes into turn\-level advantages\. This common hindsight structure isTreeHCA’s central design principle, linking informative exploration to hindsight\-guided credit assignment\. Across seven question\-answering benchmarks and three Qwen backbones,TreeHCAoutperforms every baseline in aggregate exact match, validating our paired design for multi\-turn LLM training\. Our code is available at[github\.com/TheBlackCat22/TreeHCA](https://github.com/TheBlackCat22/TreeHCA)\.

![Refer to caption](https://arxiv.org/html/2610.12828v1/figures/TreeHCA_fig1.png)Figure 1:TreeHCApairs exploration with credit assignment\.\(a\)A drop in hindsight score identifies a parent history to revisit\. The sampled alternative continues alongside the retained original path, here illustrated with successful and unsuccessful outcomes\.\(b\)Outcome signals propagate backward using normalized inverse\-score weights to construct turn\-level advantages\.## 1Introduction

An LLM agent solves a multi\-turn task through reasoning steps and tool calls\. With terminal verification, success feedback arrives only after a rollout is completed\. Outcome\-supervised group\-relative policy optimization \(GRPO\) converts this feedback into a trajectory advantage and*assigns it to every generated token*\([Shao et al\., 2024](https://arxiv.org/html/2610.12828#bib.bib12)\)\. A successful trajectory can reinforce unhelpful turns, while a failed one can penalize useful decisions\. Therefore, a central challenge in providing feedback for training multi\-turn LLM agents is to score intermediate decisions by their contribution to success\.

*How should we assign credit to intermediate decisions?*Hindsight credit assignment \(HCA\) relates an action’s probability to the subsequent outcome\([Harutyunyan et al\., 2019](https://arxiv.org/html/2610.12828#bib.bib4)\)\. An action that appears disproportionately often in successful continuations receives a larger success\-conditioned hindsight ratio\. This ratio has an exact change\-of\-measure interpretation, which connects outcome\-conditioned observations to the action value under the original policy\. In a language agent, the space of interaction histories is large, so the usefulness of this construction depends on obtaining informative alternatives from comparable histories\. GiGPO forms groups of comparable states to obtain step\-level relative advantages, and HCAPO uses outcome\-conditioned LLM scores to refine trajectory feedback\([Feng et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib3);[Tan et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib15)\)\. These methods make intermediate credit available from policy\-generated chains\. However, their estimates critically depend on these chains containing informative alternatives\. In practice, such alternatives may be sparse at consequential histories, leaving the sampled trajectories insufficiently informative for turn\-level credit assignment\.

It is therefore crucially important to gather this information by revisiting histories from which alternative decisions can change the outcome\. When an observed turn reduces the likelihood of success, we need to return to its parent and sample new continuations while retaining the original path\. This produces comparisons under a shared prefix\. Entropy\-guided exploration allocates sampling effort to uncertain decisions\([Dong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib2);[Zong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib25)\)\. However, uncertainty alone does not reveal a decision’s contribution to success\. We instead use hindsight to guide exploration toward successful outcomes\. Hindsight scores identify turns worth revisiting and promising alternatives to sample from their parent histories\. We therefore introduce*hindsight\-guided sampling*as an exploration strategy for obtaining the information needed to evaluate intermediate decisions\.

We then make a complementary connection that is key to this paper: how we gather evidence through exploration determines how we must weight it when estimating turn\-level advantages\. By selecting continuations through hindsight, we change their distribution in the rollout tree\. We must therefore account for that selection when estimating advantages for the original rollout policy\. For a hindsight\-tilted proposal, we derive the inverse hindsight ratio as the required importance weight\. Our central insight is this correspondence:*the hindsight ratio guides exploration toward informative continuations, and its inverse accounts for that sampling preference when estimating credit\.*

We develop this correspondence inTreeHCA\. Its core idea has two parts\. First, we use*hindsight\-guided sampling*to generate informative trajectories\. Changes in the model’s likelihood of the reference answer identify turns to revisit and guide our selection of alternative continuations\. Second, we use*credit assignment to samples*to accord advantages to intermediate turns according to the outcomes of their continuations\. We propagate group\-normalized terminal rewards through the tree using inverse hindsight weights to counterbalance the selection preference\. The resulting turn\-level signals reflect the successful and unsuccessful continuations supported by each intermediate decision\. The key toTreeHCAis that these operations follow the same hindsight change of measure: the score that directs exploration also determines the inverse correction used to compute credit\. This pairing is the central design principle behind the gains evaluated in[Section6](https://arxiv.org/html/2610.12828#S6)\. See[Figure1](https://arxiv.org/html/2610.12828#S0.F1)\.

We make three contributions\.\(1\) Hindsight\-guided exploration\.We formulate an exploration rule that uses turn\-level hindsight scores to select histories and alternative continuations, connecting the exact hindsight ratio to candidate action values\.\(2\) Hindsight\-guided credit assignment\.We derive the importance correction for hindsight\-guided selection, including an exact finite\-pool identity, and use its inverse\-score structure to construct turn\-level advantages through a normalized tree backup\.\(3\) Experimental validation of the paired construction\.We evaluateTreeHCAon seven question\-answering benchmarks with Qwen2\.5\-3B\-Instruct, Qwen3\-4B, and Qwen3\-8B\. Across the reported model and task settings,TreeHCAoutperforms all compared methods in aggregate exact match \(EM\)\. The paired design also achieves the strongest EM and F1 in the component study\.

## 2Related Work

#### Intermediate credit from terminal outcomes\.

HCA expresses action values through outcome\-conditioned action probabilities\([Harutyunyan et al\., 2019](https://arxiv.org/html/2610.12828#bib.bib4)\)\. For LLM agents, GiGPO constructs groups around recurring or comparable environment states and combines step\-level and trajectory\-level advantages\([Feng et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib3)\)\. HCAPO uses the LLM as a hindsight critic, normalizes its outcome\-conditioned action scores within a trajectory, and combines them with group\-relative feedback\([Tan et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib15)\)\. IGPO uses changes in reference\-answer likelihood as information\-gain rewards\([Wang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib17)\)\. These mechanisms extract intermediate learning signals from linear rollouts\.TreeHCAuses outcome relevance to select the continuations supplying these signals\.

#### Tree sampling and turn\-level learning\.

Tree\-GRPO shares prefixes in LLM\-agent rollouts and constructs relative advantages within and across trees\([Ji et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib6)\)\. In diffusion models, TreeGRPO backs terminal advantages through a denoising tree\([Ding & Ye, 2026](https://arxiv.org/html/2610.12828#bib.bib1)\)\. AEPO allocates sampling using entropy\-based information proxies and shapes the optimization signal, while AT2PO combines entropy\-guided exploration with an entropy\-weighted tree backup\([Dong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib2);[Zong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib25)\)\. IGRPO uses reference\-answer likelihood to guide adaptive rollout expansion\([Zhang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib22)\)\. These approaches motivate examining exploration and credit together\. Our focus is the sampling distribution induced by hindsight selection and the corresponding inverse weighting in the backup\. The separate policy\-update ratio compares the updated and behavior policies\.[AppendixA](https://arxiv.org/html/2610.12828#A1)provides a detailed review of these sampling and credit mechanisms\.

## 3Problem Formulation

We consider an agent that starts from a questionxxand alternates reasoning, tool use, and observation before producing an answer\. At turntt, its historyh<th\_\{<t\}contains the prompt and preceding interactions\. The policy generates a reasoning sequencests\_\{t\}and an actionata\_\{t\}, which we treat jointly as a decisionut=\(st,at\)u\_\{t\}=\(s\_\{t\},a\_\{t\}\)\. Executing a tool action produces an observationoto\_\{t\}\. A completed turn isnt=\(ut,ot\)n\_\{t\}=\(u\_\{t\},o\_\{t\}\), and a trajectory isτ=\(x,n0,…,nT\)\\tau=\(x,n\_\{0\},\\ldots,n\_\{T\}\)\. A final\-answer action terminates the trajectory\. The verifier supplies a binary terminal rewardR⁡\(τ\)∈\{0,1\}R\(\\tau\)\\in\\\{0,1\\\}, and the objective is

J⁡\(θ\)=𝔼τ∼Pπθ​\[R⁡\(τ\)\],J\(\\theta\)=\\mathbb\{E\}\_\{\\tau\\sim P\_\{\\pi\_\{\\theta\}\}\}\[R\(\\tau\)\],\(1\)wherePπθP\_\{\\pi\_\{\\theta\}\}includes both policy decisions and environment responses\.

During one rollout\-collection round, we hold the behavior policyπ=πθold\\pi=\\pi\_\{\\theta\_\{\\rm old\}\}fixed\. All success probabilities and hindsight distributions below refer to continuations under this policy\. WriteVπ​\(h\)=ℙπ​\(R=1∣h\)V^\{\\pi\}\(h\)=\\mathbb\{P\}\_\{\\pi\}\(R=1\\mid h\)andQπ​\(h,u\)=ℙπ​\(R=1∣h,U=u\)Q^\{\\pi\}\(h,u\)=\\mathbb\{P\}\_\{\\pi\}\(R=1\\mid h,U=u\)\. The latter averages over the observation followinguuand subsequent policy decisions\. For a completed childc=\(u,o\)c=\(u,o\)ofnn,

pπ​\(c∣n\)=π⁡\(u∣h⁡\(n\)\)​Penv​\(o∣h⁡\(n\),u\)\.p\_\{\\pi\}\(c\\mid n\)=\\pi\(u\\mid h\(n\)\)P\_\{\\rm env\}\(o\\mid h\(n\),u\)\.\(2\)The historyh⁡\(n\)h\(n\)includes the full prefix ending atnn\. Multiple trajectories with shared prefixes form a tree𝒯\\mathcal\{T\}\. Its sibling nodes supply alternative completed turns from a common parent, and its leaves carry the verifier outcomes used for learning\. We use the reference answery⋆y^\{\\star\}during training to score these alternatives, and the learned agent uses its ordinary policy and search tool during evaluation\.

## 4Hindsight\-Guided Exploration

We first developTreeHCA’s hindsight exploration policy\. This is the sampling part of the paired construction: we use scores indicative of final outcome likelihood to decide where to gather informative alternatives\. A turn that reduces the likelihood of success identifies a parent history worth revisiting\. We sample from the history before that decision, so an alternative can change both the next action and the evidence subsequently available to the agent\. Retaining the original continuation provides a comparison under the same prefix\. We formalize this criterion through the exact hindsight distribution, then construct its practical score and tree\-sampling rule\. The terminal verifier evaluates each retained path, supplying the outcomes whose credit we compute in[Section5](https://arxiv.org/html/2610.12828#S5)\.

### 4\.1Sampling via Credit Assignment

For a supported decisionuuat historyhhand an outcomerrof positive probability, the hindsight ratio is

ρHCA​\(h,u,r\)=ℙπ​\(U=u∣h,R=r\)π⁡\(u∣h\)=ℙπ​\(R=r∣h,U=u\)ℙπ​\(R=r∣h\)\.\\rho\_\{\\mathrm\{HCA\}\}\(h,u;r\)=\\frac\{\\mathbb\{P\}\_\{\\pi\}\(U=u\\mid h,R=r\)\}\{\\pi\(u\\mid h\)\}=\\frac\{\\mathbb\{P\}\_\{\\pi\}\(R=r\\mid h,U=u\)\}\{\\mathbb\{P\}\_\{\\pi\}\(R=r\\mid h\)\}\.\(3\)Bayes’ rule gives the second equality\. A ratio above one means thatuuis more prevalent among continuations with outcomerrthan under the rollout policy\. For success,

ρHCA​\(h,u,1\)=Qπ​\(h,u\)Vπ​\(h\),log⁡ρHCA​\(h,u,1\)=log⁡Qπ​\(h,u\)−log⁡Vπ​\(h\)\.\\rho\_\{\\mathrm\{HCA\}\}\(h,u;1\)=\\frac\{Q^\{\\pi\}\(h,u\)\}\{V^\{\\pi\}\(h\)\},\\qquad\\log\\rho\_\{\\mathrm\{HCA\}\}\(h,u;1\)=\\log Q^\{\\pi\}\(h,u\)\-\\log V^\{\\pi\}\(h\)\.\(4\)Thus a negative log ratio identifies a decision after which success is less likely than it was at the parent history\. Exploring from that parent supplies alternatives to the observed decision\.

The same quantity ranks the alternatives\. The following identity instantiates the return\-conditioned HCA result of[Harutyunyan et al\. \(2019\)](https://arxiv.org/html/2610.12828#bib.bib4)for our turn\-level process\.

###### Lemma 1\(Hindsight ranking of candidate decisions\)\.

Forπ⁡\(u∣h\)\>0\\pi\(u\\mid h\)\>0, letT⁡\(h,π\)T\(h,\\pi\)be the distribution of complete continuations fromhhunderπ\\piand the environment\. Then

Qπ​\(h,u\)=𝔼τ∼T⁡\(h,π\)​\[R⁡\(τ\)​ρHCA​\(h,u,R⁡\(τ\)\)\]\.Q^\{\\pi\}\(h,u\)=\\mathbb\{E\}\_\{\\tau\\sim T\(h,\\pi\)\}\\left\[R\(\\tau\)\\rho\_\{\\mathrm\{HCA\}\}\(h,u;R\(\\tau\)\)\\right\]\.\(5\)For binary terminal rewards andVπ​\(h\)\>0V^\{\\pi\}\(h\)\>0, this reduces toQπ​\(h,u\)=Vπ​\(h\)​ρHCA​\(h,u,1\)Q^\{\\pi\}\(h,u\)=V^\{\\pi\}\(h\)\\rho\_\{\\mathrm\{HCA\}\}\(h,u;1\)\.

The parent value is common to all candidates, so the exact hindsight ratio ranks them by expected terminal reward\. A low ratio identifies an observed turn to revisit, while a high ratio identifies an attractive alternative from its parent \([sectionD\.1](https://arxiv.org/html/2610.12828#A4.SS1)\)\.

### 4\.2Scoring Histories with the Policy LLM

We obtain a training\-time proxy using the reference answery⋆=\(y1⋆,…,yJ⋆\)y^\{\\star\}=\(y\_\{1\}^\{\\star\},\\ldots,y\_\{J\}^\{\\star\}\)\. Following the use of answer likelihood as an information signal\([Wang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib17);[Zhang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib22)\), we append a fixed answer\-eliciting instructions⋆s^\{\\star\}to a history and teacher\-force its answer tokens\. The score is the mean token log probability

ℓπ​\(h,y⋆\)=1J​∑j=1Jlog⁡π⁡\(yj⋆∣h,s⋆,y<j⋆\)\.\\ell\_\{\\pi\}\(h;y^\{\\star\}\)=\\frac\{1\}\{J\}\\sum\_\{j=1\}^\{J\}\\log\\pi\(y\_\{j\}^\{\\star\}\\mid h,s^\{\\star\},y\_\{<j\}^\{\\star\}\)\.\(6\)For a completed turnc=\(u,o\)c=\(u,o\), leth−​\(c\)h^\{\-\}\(c\)andh\+​\(c\)h^\{\+\}\(c\)be the histories before and after that turn\.

δ⁡\(c\)=log⁡ρ^c=ℓπ​\(h\+​\(c\),y⋆\)−ℓπ​\(h−​\(c\),y⋆\)\.\\delta\(c\)=\\log\\widehat\{\\rho\}\_\{c\}=\\ell\_\{\\pi\}\(h^\{\+\}\(c\);y^\{\\star\}\)\-\\ell\_\{\\pi\}\(h^\{\-\}\(c\);y^\{\\star\}\)\.\(7\)This score measures how the realized turn changes compatibility with the reference answer\. It includes the information supplied by the tool observation\. A negative score identifies a reduction in that compatibility and motivates collecting alternatives fromh−​\(c\)h^\{\-\}\(c\)\. The teacher\-forced likelihood provides a computable surrogate for the conditional success probabilities in[Equation4](https://arxiv.org/html/2610.12828#S4.E4)\.

![Refer to caption](https://arxiv.org/html/2610.12828v1/figures/TreeHCA_fig2.png)Figure 2:Hindsight\-guided exploration\.\(1\)A low score on an observed completed turn identifies its parent for resampling\.\(2\)From that starting point,N=2N=2policy decisions are executed and scored as completed candidates\.\(3\)A categorical draw selects one using normalized hindsight scores\. It continues underπ\\pito a verifier reward, while the original child and subtree remain\. Scores and outcomes are illustrative\.
### 4\.3Selecting and Completing Alternatives

Starting fromMMcomplete policy rollouts, we identify turns withδ⁡\(c\)<κbr\\delta\(c\)<\\kappa\_\{\\rm br\}for a fixed negative threshold\. In each expansion round, we select up toKKlowest\-scoring turns\. If fewer thanKKsatisfy the threshold, uniform tie\-breaking fills the allocation from the available turns\. Each selected turn identifies its parent as a starting point for exploration, as illustrated in[Figure2](https://arxiv.org/html/2610.12828#S4.F2)\.

At a selected parent, we drawNNcandidate decisions fromπ\\pi, execute their actions to obtain completed candidatesC1,…,CNC\_\{1\},\\ldots,C\_\{N\}, and score them\. We sample one candidate index with

αi=ℙ\(I=i∣C1:N\)=exp⁡δ⁡\(Ci\)∑j=1Nexp⁡δ⁡\(Cj\)=ρ^Ci∑j=1Nρ^Cj\.\\alpha\_\{i\}=\\mathbb\{P\}\(I=i\\mid C\_\{1:N\}\)=\\frac\{\\exp\\delta\(C\_\{i\}\)\}\{\\sum\_\{j=1\}^\{N\}\\exp\\delta\(C\_\{j\}\)\}=\\frac\{\\widehat\{\\rho\}\_\{C\_\{i\}\}\}\{\\sum\_\{j=1\}^\{N\}\\widehat\{\\rho\}\_\{C\_\{j\}\}\}\.\(8\)OnlyCIC\_\{I\}is continued to termination, and the original child and its subtree remain available for learning\. This spendsNNturn executions and one full continuation per expansion\. Stochastic selection allocates the continuation budget across scored alternatives\.

[Algorithm1](https://arxiv.org/html/2610.12828#alg1)gives the complete construction\. The tree now contains both original rollouts and selectively retained alternatives\. Their outcomes provide comparisons under a shared prefix, while their selection probabilities determine how these comparisons should contribute to a rollout\-policy expectation\. This is the estimation task addressed next\.

Algorithm 1Hindsight\-guided tree construction0:Prompt

xx, reference answer

y⋆y^\{\\star\}, frozen policy

π\\pi, initial count

MM, rounds

LL, exploration budget

KK, candidates

NN, threshold

κbr<0\\kappa\_\{\\rm br\}<0\.

1:Initialize

𝒯\\mathcal\{T\}with

MMcomplete policy rollouts from

xx\.

2:for

ℓ=1,…,L\\ell=1,\\ldots,Ldo

3:Score each non\-root node by

b⁡\(c\)=min⁡\{δ⁡\(c\),κbr\}b\(c\)=\\min\\\{\\delta\(c\),\\kappa\_\{\\rm br\}\\\}\.

4:Select up to

KKnodes with the smallest scores, breaking ties uniformly\.

5:foreach selected node

ccdo

6:Draw

NNdecisions from

π\(⋅∣h−\(c\)\)\\pi\(\\cdot\\mid h^\{\-\}\(c\)\)and execute them\.

7:Score the completed candidates and sample

IIusing[Equation8](https://arxiv.org/html/2610.12828#S4.E8)\.

8:Attach

CIC\_\{I\}to

pa⁡\(c\)\\mathrm\{pa\}\(c\)and complete it under

π\\pi, retaining

ccand its subtree\.

9:return

𝒯\\mathcal\{T\}with its terminal verifier rewards\.

## 5Hindsight\-Guided Credit Assignment

We now develop the complementary part of the pair which includes assigning credit to the samples gathered byTreeHCA’s exploration policy\. Hindsight\-guided selection favors high\-scoring continuations, while the learning signal must reflect their value under the original rollout policy\. The same scores that guide exploration therefore determine the inverse weighting needed for estimation\. We derive this correspondence for the specified sampling laws and use its inverse\-score structure to construct turn\-level advantages on the tree\.

### 5\.1The Sampling and Estimation Correspondence

Fix a parentnnand writep​\(c\)=pπ​\(c∣n\)p\(c\)=p\_\{\\pi\}\(c\\mid n\)for its completed\-child kernel\. For a positive scores⁡\(c\)s\(c\)withZ=𝔼p​\[s⁡\(C\)\]∈\(0,∞\)Z=\\mathbb\{E\}\_\{p\}\[s\(C\)\]\\in\(0,\\infty\), consider the tilted proposal

qs​\(c\)=p⁡\(c\)​s​\(c\)Z,p⁡\(c\)qs​\(c\)=Zs⁡\(c\)\.q\_\{s\}\(c\)=\\frac\{p\(c\)s\(c\)\}\{Z\},\\qquad\\frac\{p\(c\)\}\{q\_\{s\}\(c\)\}=\\frac\{Z\}\{s\(c\)\}\.\(9\)The score specifies which children are favored in sampling, and its inverse supplies the change of measure back to the rollout policy\. Ifs⁡\(c\)s\(c\)is the exact success\-conditioned hindsight ratio of the completed child, this proposal is the success\-conditioned child distribution on its support\.

###### Proposition 1\(Credit\-guided sampling and inverse correction\)\.

Letffbe integrable underpp\. Ifqsq\_\{s\}covers the support ofp​fpf, then

𝔼qs​\[Zs⁡\(C\)​f​\(C\)\]=𝔼p​\[f⁡\(C\)\]\.\\mathbb\{E\}\_\{q\_\{s\}\}\\\!\\left\[\\frac\{Z\}\{s\(C\)\}f\(C\)\\right\]=\\mathbb\{E\}\_\{p\}\[f\(C\)\]\.\(10\)For a finite poolC1,…,CN∼iidpC\_\{1\},\\ldots,C\_\{N\}\\stackrel\{\{\\scriptstyle\\rm iid\}\}\{\{\\sim\}\}pand selection probabilitiesαi=s⁡\(Ci\)/∑js⁡\(Cj\)\\alpha\_\{i\}=s\(C\_\{i\}\)/\\sum\_\{j\}s\(C\_\{j\}\), the corresponding identity is

𝔼\[f⁡\(CI\)N​αI\|C1:N\]=1N∑i=1Nf\(Ci\)\.\\mathbb\{E\}\\\!\\left\[\\frac\{f\(C\_\{I\}\)\}\{N\\alpha\_\{I\}\}\\,\\middle\|\\,C\_\{1:N\}\\right\]=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}f\(C\_\{i\}\)\.\(11\)Consequently, averaging over the pool recovers𝔼p​\[f​\(C\)\]\\mathbb\{E\}\_\{p\}\[f\(C\)\]\.

The finite pool also determines the selected child’s marginal law\. ForNNcandidates and a fixed first candidatecc, symmetry gives

qN​\(c\)=N​p​\(c\)​𝔼​\[s⁡\(c\)s⁡\(c\)\+∑j=2Ns⁡\(Cj\)\],q\_\{N\}\(c\)=Np\(c\)\\,\\mathbb\{E\}\\\!\\left\[\\frac\{s\(c\)\}\{s\(c\)\+\\sum\_\{j=2\}^\{N\}s\(C\_\{j\}\)\}\\right\],\(12\)where the expectation is over the remaining independent policy candidates\. AtN=1N=1, selection followspp\. For scores bounded above and away from zero, concentration of the remaining scores around their mean givesqN​\(c\)→p⁡\(c\)​s​\(c\)/Zq\_\{N\}\(c\)\\to p\(c\)s\(c\)/Z\. Thus the direct tilt describes large\-pool selection, while[Equation11](https://arxiv.org/html/2610.12828#S5.E11)provides an exact correction at every finite pool size\.

[SectionD\.2](https://arxiv.org/html/2610.12828#A4.SS2)proves these identities by a change of measure and a conditional weighted sum, and gives a two\-child illustration\. For the finite\-pool selection in[Equation8](https://arxiv.org/html/2610.12828#S4.E8), the weight is the mean candidate score divided by the selected score\. The identity holds for any strictly positive score\. It also holds for a conditionally unbiased estimate off⁡\(CI\)f\(C\_\{I\}\)after averaging over continuation randomness\.

The direction of this weighting follows the target distribution\. In[Lemma1](https://arxiv.org/html/2610.12828#Thmlemma1), the hindsight ratio multiplies a return sampled under the rollout policy to recover an action\-conditioned value\. In[Proposition1](https://arxiv.org/html/2610.12828#Thmproposition1), the sampling law itself favors children with large scores, so recovering a rollout\-policy expectation uses the inverse score\. For the exact hindsight score, these identities express the two directions of the conditional\-distribution change of measure\.

These identities explain why exploration and credit must be designed together\. Hindsight\-guided selection makes high\-scoring continuations more common, so their observed frequency alone cannot represent the rollout policy\. Inverse weighting compensates for this preference when computing a policy\-based expectation\. The direct\-tilt identity gives the correction for score\-proportional sampling, and the finite\-pool identity gives it conditional on the sampled candidates\.TreeHCAcarries the same inverse\-score structure into a normalized backup over retained children, propagating their outcome signals to intermediate turns\.[SectionsD\.3](https://arxiv.org/html/2610.12828#A4.SS3)and[D\.4](https://arxiv.org/html/2610.12828#A4.SS4)provide the derivations\.

### 5\.2From Leaf Rewards to Turn\-Level Advantages

For the leaves belonging to one prompt, letμR\\mu\_\{R\}andσR\\sigma\_\{R\}be the mean and standard deviation of the verifier rewards\. Initialize a leafℓ\\ellwith its group\-relative signal

A^tree​\(ℓ\)=\{\(R⁡\(ℓ\)−μR\)/σR,σR\>0,0,σR=0\.\\widehat\{A\}^\{\\rm tree\}\(\\ell\)=\\begin\{cases\}\\bigl\(R\(\\ell\)\-\\mu\_\{R\}\\bigr\)/\\sigma\_\{R\},&\\sigma\_\{R\}\>0,\\\\ 0,&\\sigma\_\{R\}=0\.\\end\{cases\}\(13\)The zero\-variance case supplies a zero learning signal when every trajectory has the same outcome\. The tree then propagates these signals toward the root\. For the observed childrenCh⁡\(n\)\\mathrm\{Ch\}\(n\), define

w~n,c=ρ^c−1∑c′∈Ch⁡\(n\)ρ^c′−1,A^tree​\(n\)=∑c∈Ch⁡\(n\)w~n,c​A^tree​\(c\)\.\\widetilde\{w\}\_\{n,c\}=\\frac\{\\widehat\{\\rho\}\_\{c\}^\{\-1\}\}\{\\sum\_\{c^\{\\prime\}\\in\\mathrm\{Ch\}\(n\)\}\\widehat\{\\rho\}\_\{c^\{\\prime\}\}^\{\-1\}\},\\qquad\\widehat\{A\}^\{\\rm tree\}\(n\)=\\sum\_\{c\\in\\mathrm\{Ch\}\(n\)\}\\widetilde\{w\}\_\{n,c\}\\widehat\{A\}^\{\\rm tree\}\(c\)\.\(14\)The recursion proceeds in reverse topological order\. A node with one child inherits that child’s signal\. At a parent with multiple children, the inverse scores counterbalance the preference toward high\-scoring alternatives, and normalization produces a convex combination of the child signals\.

Under independent sampling from the specified tilted proposal, self\-normalized inverse\-score weighting consistently estimates the base\-policy expectation\. The tree operator applies this normalization to a finite, adaptively constructed tree with proxy scores\. Its finite\-tree behavior is evaluated through the credit\-rule ablation in[Section6\.3](https://arxiv.org/html/2610.12828#S6.SS3)\. The exact identities in[Proposition1](https://arxiv.org/html/2610.12828#Thmproposition1)explain the correction’s form, while the normalization preserves the scale and common shifts of the group\-relative signal\. The appendix states the estimator conditions and separates finite\-pool selection from the retained siblings\.

### 5\.3Turn\-Level Policy Optimization

Each policy\-generated token receives the advantage of its completed turn\. If tokenttof trajectoryyiy\_\{i\}belongs to nodeni,κi​\(t\)n\_\{i,\\kappa\_\{i\}\(t\)\}, setAi,t=A^tree​\(ni,κi​\(t\)\)A\_\{i,t\}=\\widehat\{A\}^\{\\rm tree\}\(n\_\{i,\\kappa\_\{i\}\(t\)\}\)\. Tool outputs and prompt tokens remain in the conditioning history and are masked from the loss\. LetMi,tM\_\{i,t\}be the policy\-token mask andNi=∑tMi,tN\_\{i\}=\\sum\_\{t\}M\_\{i,t\}\. We use the GSPO\-token surrogate\([Zheng et al\., 2025a](https://arxiv.org/html/2610.12828#bib.bib23)\), whose detached sequence ratio scales the token gradient:

ri​\(θ\)\\displaystyle r\_\{i\}\(\\theta\)=exp⁡\[1Ni​∑tMi,t​log⁡πθ​\(yi,t∣hi,t\)π⁡\(yi,t∣hi,t\)\],\\displaystyle=\\exp\\\!\\left\[\\frac\{1\}\{N\_\{i\}\}\\sum\_\{t\}M\_\{i,t\}\\log\\frac\{\\pi\_\{\\theta\}\(y\_\{i,t\}\\mid h\_\{i,t\}\)\}\{\\pi\(y\_\{i,t\}\\mid h\_\{i,t\}\)\}\\right\],\(15\)si,t​\(θ\)\\displaystyle s\_\{i,t\}\(\\theta\)=πθ​\(yi,t∣hi,t\)sg⁡\[πθ​\(yi,t∣hi,t\)\]​sg⁡\[ri​\(θ\)\]\.\\displaystyle=\\frac\{\\pi\_\{\\theta\}\(y\_\{i,t\}\\mid h\_\{i,t\}\)\}\{\\operatorname\{sg\}\[\\pi\_\{\\theta\}\(y\_\{i,t\}\\mid h\_\{i,t\}\)\]\}\\operatorname\{sg\}\[r\_\{i\}\(\\theta\)\]\.\(16\)Heresg\\operatorname\{sg\}denotes stop\-gradient\. This policy\-update ratio compares the updated and behavior policies\. The inverse\-hindsight weights in[Equation14](https://arxiv.org/html/2610.12828#S5.E14)instead counterbalance continuation selection\.

Letℬπ\(⋅∣x\)\\mathcal\{B\}\_\{\\pi\}\(\\cdot\\mid x\)denote the tree\-generation law of[Algorithm1](https://arxiv.org/html/2610.12828#alg1), and lety1,…,yGy\_\{1\},\\ldots,y\_\{G\}be its root\-to\-leaf trajectories\. We optimize

𝒥TreeHCA\(θ\)=𝔼x∼𝒟,𝒯∼ℬπ\(⋅∣x\)\[1G∑i=1G1Ni∑tMi,tmin\{si,t\(θ\)Ai,t,clip\(si,t\(θ\),1−εl,1\+εr\)Ai,t\}\]\.\\begin\{split\}\\mathcal\{J\}\_\{\\textsc\{TreeHCA\}\}\(\\theta\)=\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\},\\mathcal\{T\}\\sim\\mathcal\{B\}\_\{\\pi\}\(\\cdot\\mid x\)\}\\left\[\\frac\{1\}\{G\}\\sum\_\{i=1\}^\{G\}\\frac\{1\}\{N\_\{i\}\}\\sum\_\{t\}M\_\{i,t\}\\right\.\\\\ \\left\.\\quad\\min\\\!\\left\\\{s\_\{i,t\}\(\\theta\)A\_\{i,t\},\\operatorname\{clip\}\\\!\\left\(s\_\{i,t\}\(\\theta\),1\-\\varepsilon\_\{l\},1\+\\varepsilon\_\{r\}\\right\)A\_\{i,t\}\\right\\\}\\right\]\.\\end\{split\}\(17\)Advantages are held fixed during the update\. A shared\-prefix turn receives the same node advantage in every descendant trajectory, with the sequence ratio evaluated for each complete trajectory\.

## 6Experiments

We now conduct a set of experiments to answer two fundamental questions\.*Does hindsight\-guided exploration collect informative trajectories?*Chain\-method comparisons place intermediate credit signals in context, and tree\-method comparisons examine the choice of exploration rule\.*Does inverse\-hindsight weighting provide useful turn\-level credit?*The component comparison changes exploration and credit rules in turn, thereby examining their contribution to the complete method\.

### 6\.1Setup and Comparison Protocols

We evaluate search\-based question answering with Qwen2\.5\-3B\-Instruct against chain and tree baselines \([Tables1](https://arxiv.org/html/2610.12828#S6.T1)and[2](https://arxiv.org/html/2610.12828#S6.T2)\), and with Qwen3\-4B and Qwen3\-8B \([Table3](https://arxiv.org/html/2610.12828#S6.T3)\)\([Yang et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib18)\)\. Multi\-hop benchmarks comprise HotpotQA, 2WikiMultihopQA, MuSiQue, and Bamboogle\([Yang et al\., 2018](https://arxiv.org/html/2610.12828#bib.bib19);[Ho et al\., 2020](https://arxiv.org/html/2610.12828#bib.bib5);[Trivedi et al\., 2022](https://arxiv.org/html/2610.12828#bib.bib16);[Press et al\., 2023](https://arxiv.org/html/2610.12828#bib.bib11)\)\. Single\-hop benchmarks comprise Natural Questions \(NQ\), TriviaQA, and PopQA\([Kwiatkowski et al\., 2019](https://arxiv.org/html/2610.12828#bib.bib9);[Joshi et al\., 2017](https://arxiv.org/html/2610.12828#bib.bib8);[Mallen et al\., 2023](https://arxiv.org/html/2610.12828#bib.bib10)\)\. The agent interleaves reasoning with queries to a Wikipedia index, receiving the top three passages per query\. Qwen3 allows six tool calls and 6192 response tokens\.[Table7](https://arxiv.org/html/2610.12828#A2.T7)gives the Qwen2\.5 settings\. Exact match \(EM\) is the percentage of questions whose normalized extracted answer matches a reference answer\. Aggregate scores weight datasets by test\-set size\.

For Qwen3, we train on HotpotQA for 250 steps for multi\-hop evaluation and NQ for 200 steps for single\-hop evaluation\. The tree configuration usesM=10M=10initial rollouts,K=6K=6exploration parents, andL=2L=2expansion rounds\. We train AT2PO from its public implementation and apply TreeGRPO’s likelihood\-weighted backup\([Ding & Ye, 2026](https://arxiv.org/html/2610.12828#bib.bib1)\)to search trajectories\. These methods andTreeHCAshare an expansion budget \([Table3](https://arxiv.org/html/2610.12828#S6.T3)\)\. Published ReAct\([Yao et al\., 2023](https://arxiv.org/html/2610.12828#bib.bib20)\), GRPO, GSPO, and AEPO results complete the comparison\.[AppendixB](https://arxiv.org/html/2610.12828#A2)provides further setup details\.

Table 1:Qwen2\.5\-3B\-Instruct comparison for chain\-based baselines: EM \(%\)\. Darker to lighter green marks the three largest distinct values per column, with ties sharing a shade and maxima in bold\. Underlined entries indicate methods \(re\-\)evaluated in our setup\. Each of these methods uses five trajectories\.Table 2:Qwen2\.5\-3B\-Instruct comparison for tree\-based baselines: EM \(%\)\. Colors follow[Table1](https://arxiv.org/html/2610.12828#S6.T1)\.
### 6\.2Hindsight\-Guided Exploration

[Table1](https://arxiv.org/html/2610.12828#S6.T1)compares chain\-based methods withTreeHCA\. Search\-R1 and ZeroSearch learn from completed reasoning\-and\-search trajectories\([Jin et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib7);[Sun et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib14)\)\. GiGPO constructs turn\-level comparisons by grouping comparable states, IGPO scores changes in reference\-answer likelihood, and HCAPO weights actions using hindsight context\([Feng et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib3);[Wang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib17);[Tan et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib15)\)\.[Table2](https://arxiv.org/html/2610.12828#S6.T2)adds tree\-based baselines\. Tree\-GRPO uses shared\-prefix comparisons\([Ji et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib6)\), with its reported scores taken from the reproduction in[Zhang et al\. \(2026\)](https://arxiv.org/html/2610.12828#bib.bib22)\.TreeHCAconnects such feedback to the allocation of new continuations, explicitly revisiting histories before low\-scoring decisions\. It achieves the highest aggregate EM in this comparison, 44\.9, exceeding HCAPO by 0\.6 percentage points\.

Table 3:Qwen3 comparison: EM \(%\)\. ReAct, GRPO, GSPO, and AEPO results are from[Zong et al\. \(2026\)](https://arxiv.org/html/2610.12828#bib.bib25)\. TreeGRPO, AT2PO, andTreeHCAuse our shared training protocol\. W\. Avg\. weights datasets by test\-set size\. Colors rank values within each backbone\. Underlined entries indicate methods \(re\-\)evaluated in our setup\.[Table3](https://arxiv.org/html/2610.12828#S6.T3)examines tree construction and credit on the Qwen3 backbones\. Relative to AT2PO,TreeHCAincreases the multi\-hop weighted EM from 47\.62 to 48\.52 at 4B and from 48\.41 to 50\.25 at 8B\. The corresponding single\-hop increases are 55\.55 to 56\.38 and 56\.75 to 58\.75\. Relative to TreeGRPO, the gains are 2\.26 and 2\.74 percentage points on multi\-hop QA, and 1\.19 and 2\.07 points on single\-hop QA\. Across all seven methods,TreeHCAachieves the highest weighted EM for both model sizes and task families\. At 8B, it exceeds the strongest published comparison, AEPO, by 1\.63 points on multi\-hop QA and 0\.81 points on single\-hop QA\.

### 6\.3Credit Assignment and the Paired Construction

Table 4:Component comparison on HotpotQA with Qwen3\-4B \(seed 42\)\. Each row names the exploration rule and the credit rule\. EM and F1 validation scores are percentages\. Colors follow[Table1](https://arxiv.org/html/2610.12828#S6.T1)\.We vary exploration and credit one at a time \([Table4](https://arxiv.org/html/2610.12828#S6.T4)\)\. With theTreeHCAcredit rule, hindsight exploration attains 51\.76 EM, compared with 51\.17 for entropy and 49\.02 for random exploration\.

Under hindsight exploration,TreeHCAcredit reaches 51\.76 EM and 65\.88 F1, versus 49\.60 and 62\.74 with AT2PO credit\. Under entropy exploration, the EM scores are 51\.17 and 50\.78, respectively\. Switching toTreeHCAcredit therefore gains 2\.16 EM and 3\.14 F1 points under hindsight exploration, and 0\.39 EM and 0\.32 F1 points under entropy exploration\. Under AT2PO credit, however, entropy outperforms hindsight \(50\.78 versus 49\.60 EM\)\. The complete pair is strongest, and both metrics show that the effect of changing exploration depends on the credit rule\.

### 6\.4Variability and Training Cost

The accuracy comparisons raise two further questions:*How much does performance vary across training runs?**What training cost accompanies the gains?*We examine the variation across three seeds and the wall\-clock time required by the paired construction\.

#### Variation across training runs\.

[Table5](https://arxiv.org/html/2610.12828#S6.T5)reports the multi\-hop results across three training seeds\. The weighted EM is48\.52±0\.7548\.52\\pm 0\.75for Qwen3\-4B and50\.25±1\.2750\.25\\pm 1\.27for Qwen3\-8B\. Across individual benchmarks, standard deviations range from 0 to 2\.30 points at 4B and from 0\.36 to 4\.53 points at 8B\. The aggregate gains over the strongest baseline are 0\.90 and 1\.63 points, respectively\. Both gains exceed one standard deviation ofTreeHCA’s observed run variation, supporting reasonably consistent aggregate performance across these seeds\. The larger deviations on some individual benchmarks indicate greater sensitivity to the training seed\.

Table 5:TreeHCAmulti\-hop performance as mean±\\pmone standard deviation over three training seeds\. EM and its standard deviation are in percentage points\. Means match[Table3](https://arxiv.org/html/2610.12828#S6.T3)\. W\. Avg\. weights datasets by size\.
#### Training cost\.

The wall\-clock training times on eight H200 GPUs are 34\.40 versus 31\.50 hours at 4B and 36\.20 versus 32\.58 hours at 8B forTreeHCAand AT2PO, respectively\. These correspond to increases of 9\.2% and 11\.1%\. Under the shared expansion budget, the paired design therefore improves accuracy with 9–11% more training time\. The timing comparison quantifies the computational cost accompanying the stronger credit signals\.

## 7Conclusion

TreeHCAconnects exploration and intermediate credit through a common hindsight change of measure\. Hindsight scores guide the selection of alternative continuations, and inverse weights account for that sampling preference when estimating advantages\. We derive this relationship for a hindsight\-tilted proposal and finite\-pool candidate selection, then realize it through a normalized tree backup\. Across the evaluated question\-answering settings, the paired construction improves on the compared baselines, and component ablations connect its performance to the combination of exploration and credit\. Together, the sampling identities and component experiments identify the pairing as the central design principle behind these gains\.

## Reproducibility Statement

[Sections4](https://arxiv.org/html/2610.12828#S4)and[5](https://arxiv.org/html/2610.12828#S5)specify the exploration rule and learning objective\. Proofs and estimator conditions appear in[appendixD](https://arxiv.org/html/2610.12828#A4), and configurations, result provenance, and uncertainty reporting in[appendicesB](https://arxiv.org/html/2610.12828#A2)and[6\.4](https://arxiv.org/html/2610.12828#S6.SS4.SSS0.Px1)\. Code:[https://github\.com/TheBlackCat22/TreeHCA](https://github.com/TheBlackCat22/TreeHCA)\.

## References

- Ding & Ye \(2026\)Zheng Ding and Weirui Ye\.TreeGRPO: Tree\-Advantage GRPO for Online RL Post\-Training of Diffusion Models\.In*Proceedings of ICLR*, 2026\.
- Dong et al\. \(2026\)Guanting Dong, Licheng Bao, Zhongyuan Wang, Kangzhi Zhao, Xiaoxi Li, Jiajie Jin, Jinghan Yang, Hangyu Mao, Fuzheng Zhang, Kun Gai, Guorui Zhou, Yutao Zhu, Ji\-Rong Wen, and Zhicheng Dou\.Toward Generalized Web Agent Training: A Deep Dive into Entropy\-Balanced Reinforcement Learning\.In*Proceedings of the ACM Web Conference 2026*, 2026\.
- Feng et al\. \(2025\)Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An\.Group\-in\-Group Policy Optimization for LLM Agent Training\.In*Advances in Neural Information Processing Systems*, volume 38, 2025\.
- Harutyunyan et al\. \(2019\)Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nicolas Heess, Hado van Hasselt, Gregory Wayne, Satinder Singh, Doina Precup, and Remi Munos\.Hindsight credit assignment\.In H\. Wallach, H\. Larochelle, A\. Beygelzimer, F\. d'Alché\-Buc, E\. Fox, and R\. Garnett \(eds\.\),*Advances in Neural Information Processing Systems*, volume 32\. Curran Associates, Inc\., 2019\.URL[https://proceedings\.neurips\.cc/paper\_files/paper/2019/file/195f15384c2a79cedf293e4a847ce85c\-Paper\.pdf](https://proceedings.neurips.cc/paper_files/paper/2019/file/195f15384c2a79cedf293e4a847ce85c-Paper.pdf)\.
- Ho et al\. \(2020\)Xanh Ho, Anh\-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa\.Constructing A Multi\-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps\.In*Proceedings of the 28th International Conference on Computational Linguistics*, pp\. 6609–6625, 2020\.
- Ji et al\. \(2026\)Yuxiang Ji, Ziyu Ma, Yong Wang, Guanhua Chen, Xiangxiang Chu, and Liaoni Wu\.Tree Search for LLM Agent Reinforcement Learning\.In*Proceedings of ICLR*, 2026\.
- Jin et al\. \(2025\)Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Sercan O\. Arik, Dong Wang, Hamed Zamani, and Jiawei Han\.Search\-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning\.In*2nd Conference on Language Modeling*, 2025\.
- Joshi et al\. \(2017\)Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer\.TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension\.In*Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pp\. 1601–1611, 2017\.
- Kwiatkowski et al\. \(2019\)Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming\-Wei Chang, Andrew M\. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov\.Natural questions: A benchmark for question answering research\.*Transactions of the Association for Computational Linguistics*, 7:452–466, 2019\.doi:10\.1162/tacl\_a\_00276\.URL[https://aclanthology\.org/Q19\-1026/](https://aclanthology.org/Q19-1026/)\.
- Mallen et al\. \(2023\)Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi\.When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non\-Parametric Memories\.In*Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pp\. 9802–9822, 2023\.
- Press et al\. \(2023\)Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis\.Measuring and Narrowing the Compositionality Gap in Language Models\.In*Findings of the Association for Computational Linguistics: EMNLP 2023*, pp\. 5687–5711, 2023\.
- Shao et al\. \(2024\)Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y\. K\. Li, Y\. Wu, and Daya Guo\.DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models, 2024\.arXiv preprint arXiv:2402\.03300\.
- Sheng et al\. \(2025\)Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu\.HybridFlow: A Flexible and Efficient RLHF Framework\.In*Proceedings of the 20th European Conference on Computer Systems*, EuroSys ’25, pp\. 1279–1297, 2025\.
- Sun et al\. \(2025\)Hao Sun, Zile Qiao, Jiayan Guo, Xuanbo Fan, Yingyan Hou, Yong Jiang, Pengjun Xie, Yan Zhang, Fei Huang, and Jingren Zhou\.ZeroSearch: Incentivize the Search Capability of LLMs without Searching, 2025\.arXiv preprint arXiv:2505\.04588\.
- Tan et al\. \(2026\)Hui\-Ze Tan, Xiao\-Wen Yang, Hao Chen, Jie\-Jing Shao, Yi Wen, Yuteng Shen, Weihong Luo, Xiku Du, Lan\-Zhe Guo, and Yu\-Feng Li\.Hindsight Credit Assignment for Long\-Horizon LLM Agents, 2026\.arXiv preprint arXiv:2603\.08754\.
- Trivedi et al\. \(2022\)Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal\.MuSiQue: Multihop questions via single\-hop question composition\.*Transactions of the Association for Computational Linguistics*, 10:539–554, 2022\.doi:10\.1162/tacl\_a\_00475\.URL[https://aclanthology\.org/2022\.tacl\-1\.31/](https://aclanthology.org/2022.tacl-1.31/)\.
- Wang et al\. \(2026\)Guoqing Wang, Sunhao Dai, Guangze Ye, Zeyu Gan, Wei Yao, Yong Deng, Xiaofeng Wu, and Zhenzhe Ying\.Information Gain\-based Policy Optimization: A Simple and Effective Approach for Multi\-Turn Search Agents\.In*Proceedings of ICLR*, 2026\.
- Yang et al\. \(2025\)An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu\.Qwen3 technical report, 2025\.URL[https://arxiv\.org/abs/2505\.09388](https://arxiv.org/abs/2505.09388)\.
- Yang et al\. \(2018\)Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D\. Manning\.HotpotQA: A Dataset for Diverse, Explainable Multi\-Hop Question Answering\.In*Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing*, pp\. 2369–2380, 2018\.
- Yao et al\. \(2023\)Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao\.ReAct: Synergizing Reasoning and Acting in Language Models\.In*Proceedings of ICLR*, 2023\.
- Zhang et al\. \(2024\)Chi Zhang, Guangming Sheng, Siyao Liu, Jiahao Li, Ziyuan Feng, Zherui Liu, Xin Liu, Xiaoying Jia, Yanghua Peng, Haibin Lin, and Chuan Wu\.A Framework for Training Large Language Models for Code Generation via Proximal Policy Optimization\.In*NL2Code Workshop of ACM KDD*, 2024\.
- Zhang et al\. \(2026\)Yijun Zhang, Fan Xu, Jiaxin Ding, Yule Xie, Shiqing Gao, Xin Ding, Haoxiang Zhang, Luoyi Fu, and Xinbing Wang\.Information Gain\-based Rollout Policy Optimization: An Adaptive Tree\-Structured Rollout Approach for Multi\-Turn LLM Agents, 2026\.arXiv preprint arXiv:2607\.06223\.
- Zheng et al\. \(2025a\)Chujie Zheng, Shixuan Liu, Mingze Li, Xiong\-Hui Chen, Bowen Yu, Chang Gao, Kai Dang, Yuqiong Liu, Rui Men, An Yang, Jingren Zhou, and Junyang Lin\.Group Sequence Policy Optimization, 2025a\.arXiv preprint arXiv:2507\.18071\.
- Zheng et al\. \(2025b\)Xuhui Zheng, Kang An, Ziliang Wang, Yuhang Wang, and Yichao Wu\.StepSearch: Igniting LLMs Search Ability via Step\-Wise Proximal Policy Optimization\.In*Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing*, pp\. 21805–21830, 2025b\.
- Zong et al\. \(2026\)Zefang Zong, Dingwei Chen, Yang Li, Qi Yi, Bo Zhou, Chengming Li, Bo Qian, Peng Chen, and Jie Jiang\.AT2PO: Agentic Turn\-based Policy Optimization via Tree Search\.In*Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pp\. 24120–24143, 2026\.

## Appendix ADetailed related work

Intermediate credit assignment depends on both the information available at a decision and the continuations used to assess it\. We organize the relevant methods by how they collect alternatives and translate outcomes into learning signals\.

### A\.1Hindsight distributions and practical action credit

Hindsight credit assignment \(HCA\) measures an action’s relevance through its probability conditioned on a later state or return\([Harutyunyan et al\., 2019](https://arxiv.org/html/2610.12828#bib.bib4)\)\. Bayes’ rule relates this posterior\-to\-policy ratio to the action’s effect on future outcomes\. Under exact conditionals and appropriate support, the forward ratio recovers action\-conditioned values from policy\-mixture outcomes, while the inverse ratio recovers policy\-mixture expectations from action\-conditioned outcomes\. For binary rewards, the success\-conditioned ratio ranks actions by expected reward at a common parent\. These identities connect outcome relevance to a change of measure\.

GiGPO obtains practical credit by combining episode\-relative returns with discounted\-return comparisons among actions at recurring anchor states\([Feng et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib3)\)\. It matches environment\-state keys, using sequence similarity for search\-QA histories\. These comparisons can link actions at different times or histories sharing an anchor\. HCAPO uses the actor as a generative hindsight critic\([Tan et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib15)\)\. It scores recorded actions with successful\-outcome context, applies length and temperature normalization, divides each score by its trajectory mean, and clips the multiplier before combining discounted\-return and trajectory\-relative feedback\. Both obtain intermediate signals from collected trajectories\.TreeHCAuses the exact hindsight conditional for its ranking interpretation and reference\-answer scores to direct the collection of alternatives\.

### A\.2Outcome and process feedback along policy trajectories

Outcome\-supervised GRPO assigns each response’s standardized reward to its generated tokens, comparing responses to the same prompt\([Shao et al\., 2024](https://arxiv.org/html/2610.12828#bib.bib12)\)\. Its process\-supervised formulation instead accumulates intermediate reward\-model scores\. Search\-R1 learns interleaved reasoning and retrieval from terminal answer rewards, using PPO with a learned value model by default and GRPO as an alternative\([Jin et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib7)\)\. Retrieved passages condition subsequent decisions, while losses apply to generated tokens\. ZeroSearch trains with a retrieval simulator and a curriculum of increasingly noisy observations, combining terminal answer feedback with experience under changing retrieval conditions\([Sun et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib14)\)\.

Process rewards supply information about intermediate search decisions\. StepSearch rewards gains in gold\-evidence coverage, penalizes repeated retrieval, and adds answer and query supervision\([Zheng et al\., 2025b](https://arxiv.org/html/2610.12828#bib.bib24)\)\. PPO propagates these rewards through value estimates and generalized advantage estimation\. IGPO instead uses changes in the reference answer’s length\-normalized log likelihood as dense turn rewards, normalizing process and outcome feedback separately\([Wang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib17)\)\. These methods refine credit within collected chains\. InTreeHCA, answer information also determines which histories and decisions receive additional rollout budget\.

### A\.3Tree structure, exploration criteria, and credit aggregation

Shared\-prefix trees compare continuations from a common history while reusing earlier interaction\. The LLM\-agent Tree\-GRPO of[Ji et al\. \(2026\)](https://arxiv.org/html/2610.12828#bib.bib6)expands randomly selected nonleaf steps and combines reward\-normalized advantages within and across trees\. Shared\-prefix occurrences accumulate contributions from descendant trajectories\. The diffusion\-model TreeGRPO of[Ding & Ye \(2026\)](https://arxiv.org/html/2610.12828#bib.bib1)samples alternative denoising paths within a stochastic window and propagates normalized terminal advantages through child weights proportional to behavior\-policy likelihoods\. These distinct methods connect tree structure to credit in agent interactions and latent denoising, respectively\.

Entropy provides another exploration criterion\. AT2PO ranks histories using sampled\-token log probabilities and a penalty for repeated parent expansion, then aggregates leaf signals through entropy\-weighted backups and applies a turn\-level policy objective\([Zong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib25)\)\. AEPO uses a pilot trajectory to allocate sampling between the root and intermediate histories according to root and tool\-related entropy\([Dong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib2)\)\. It spreads exploration through a consecutive\-expansion penalty and combines entropy\-shaped advantages with a clipping modification that preserves positive\-advantage gradients beyond the upper threshold\.TreeHCAconnects history and candidate selection to reference\-answer compatibility and the corresponding sampling correction\.

### A\.4The sampling distribution and policy optimization

IGRPO directly connects answer information to rollout allocation\([Zhang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib22)\)\. It combines length\-normalized answer likelihood with improvement over the parent and exponentially transforms this score into expansion probabilities\. Under a fixed policy, equal horizon, and growing per\-layer budgets, its analysis gives an exponentially tilted trajectory distribution with a KL\-regularized teacher interpretation\. Group\-relative training uses samples from this teacher\. Our estimation target is the original rollout\-policy expectation at a selected parent, connecting continuation selection to the reciprocal weighting that recovers that target\.

For an independently generated candidate pool with positive selection probabilities,[Equation11](https://arxiv.org/html/2610.12828#S5.E11)gives an exact correction: conditional weighting recovers the pool mean, and averaging over candidate generation recovers the base\-policy expectation\. The practical tree backup in[Equation14](https://arxiv.org/html/2610.12828#S5.E14)normalizes inverse proxy scores over retained siblings\. Under independent draws from the specified direct tilt, the corresponding self\-normalized estimator is consistent \([SectionD\.4](https://arxiv.org/html/2610.12828#A4.SS4)\)\. The sampling law therefore supplies the inverse\-score form used in credit aggregation\.

Policy optimization addresses a separate distribution change between rollout and updated policies\. GSPO uses a length\-normalized sequence ratio, while GSPO\-token allows token\-specific advantages through a stop\-gradient construction\([Zheng et al\., 2025a](https://arxiv.org/html/2610.12828#bib.bib23)\)\. InTreeHCA, this optimizer acts on turn\-level advantages after tree credit has been computed\. The exploration rule and credit operator share a common principle: credit determines which alternatives are collected, and their collection law informs the credit assigned to their outcomes\.

## Appendix BAdditional experimental details

### B\.1Hyperparameters

[Table6](https://arxiv.org/html/2610.12828#A2.T6)groups the Qwen3 settings shared by AT2PO andTreeHCAaccording to their role in training\. The optimizer and learning rate govern parameter updates, while clipping controls the likelihood\-ratio range in the policy objective\. The training and PPO mini\-batch sizes specify the granularity of these updates\. Prompt and response lengths are measured in tokens, and the tool\-call limit bounds the number of external interactions along a trajectory\.

The rollout settings describe how trajectories are collected\. The tree starts withMMcomplete trajectories and adds alternatives from up toKKselected parents in each ofLLexpansion rounds\. These controls specify the allocation of exploration across histories and rounds, complementing the length and interaction limits on each trajectory\.

Table 6:Qwen3 training and rollout settings shared by AT2PO andTreeHCA\.Table 7:Rollout settings for Qwen2\.5\-3B experiments\.[Table8](https://arxiv.org/html/2610.12828#A2.T8)gives the additional controls for hindsight\-guided exploration\. Score smoothing stabilizes the comparison of reference\-answer likelihoods when these likelihoods are small\. The negative exploration threshold identifies completed turns that reduce the score, and the sibling penalty lowers the priority of parents that already have alternatives\. The candidate countNNdetermines how many completed turns are scored at a selected parent before choosing a continuation\.

Table 8:TreeHCAscore and exploration controls\.
### B\.2Runtime

All training experiments for QA tasks were conducted on a high\-performance computing cluster equipped with 8×\\timesNVIDIA H200 GPUs\.[Table9](https://arxiv.org/html/2610.12828#A2.T9)reports wall\-clock training time for Qwen3\-4B and Qwen3\-8B under AT2PO andTreeHCA\.

Table 9:Wall\-clock training time in hours on 8 H200 GPUs\.
### B\.3Code details

The experiments with the Qwen3 family models use code built upon the codebase for AT2PO\([Zong et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib25)\), which itself is built on the VeRL framework\([Sheng et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib13);[Zhang et al\., 2024](https://arxiv.org/html/2610.12828#bib.bib21)\)\. The experiments with the Qwen2\.5\-3B\-Instruct model use the codebase for IGRPO\([Zhang et al\., 2026](https://arxiv.org/html/2610.12828#bib.bib22)\)with the addition of ourTreeHCAimplementation\. That codebase uses the VeRL\-agent framework\([Feng et al\., 2025](https://arxiv.org/html/2610.12828#bib.bib3)\)\.

## Appendix CAdditional component measurements

[Table4](https://arxiv.org/html/2610.12828#S6.T4)reports EM and F1 for the component comparison\. The corresponding validation scores recorded for the six rows are 51\.56, 50\.00, 49\.41, 48\.05, 47\.66, and 39\.26, respectively\. These values preserve the distinction between the validation measurement and the EM and F1 metrics used in the main comparison\. All six rows use Qwen3\-4B on HotpotQA with seed 42\.

Figure 3:F1 for the component comparison in[Table4](https://arxiv.org/html/2610.12828#S6.T4)\. The figure reports the F1 column, including 65\.88 for the complete hindsight\-guided exploration and credit pair\.
## Appendix DHindsight Identities and Estimator Conditions

### D\.1The Return\-Conditioned HCA Identity

[Lemma1](https://arxiv.org/html/2610.12828#Thmlemma1)instantiates the return\-conditioned action\-value identity of[Harutyunyan et al\. \(2019\)](https://arxiv.org/html/2610.12828#bib.bib4), Theorem 5\. The states of our process are complete interaction histories\. A composite turnu=\(s,a\)u=\(s,a\)is an action, the environment supplies its observation, and the undiscounted return equals the terminal verifier reward\. This formulation retains the policy’s conditioning information and treats the tool response as part of the state transition\.

###### Proof of[Lemma1](https://arxiv.org/html/2610.12828#Thmlemma1)\.

Fixhhand a decisionuuwithπ⁡\(u∣h\)\>0\\pi\(u\\mid h\)\>0\. For every outcomerrwith positive probability under a continuation fromhh, Bayes’ rule gives

ℙπ​\(R=r∣h\)​ℙπ​\(U=u∣h,R=r\)π⁡\(u∣h\)=ℙπ​\(R=r∣h,U=u\)\.\\mathbb\{P\}\_\{\\pi\}\(R=r\\mid h\)\\frac\{\\mathbb\{P\}\_\{\\pi\}\(U=u\\mid h,R=r\)\}\{\\pi\(u\\mid h\)\}=\\mathbb\{P\}\_\{\\pi\}\(R=r\\mid h,U=u\)\.\(18\)Multiplying byrrand summing over the possible returns proves

𝔼τ∼T⁡\(h,π\)​\[R⁡\(τ\)​ρHCA​\(h,u,R⁡\(τ\)\)\]=∑rr​ℙπ​\(R=r∣h,U=u\)=Qπ​\(h,u\)\.\\mathbb\{E\}\_\{\\tau\\sim T\(h,\\pi\)\}\[R\(\\tau\)\\rho\_\{\\mathrm\{HCA\}\}\(h,u;R\(\\tau\)\)\]=\\sum\_\{r\}r\\mathbb\{P\}\_\{\\pi\}\(R=r\\mid h,U=u\)=Q^\{\\pi\}\(h,u\)\.\(19\)Zero\-probability return events contribute zero and need no conditional ratio\. For a binary terminal reward, onlyr=1r=1contributes\. WhenVπ​\(h\)\>0V^\{\\pi\}\(h\)\>0, the identity reduces toQπ​\(h,u\)=Vπ​\(h\)​ρHCA​\(h,u,1\)Q^\{\\pi\}\(h,u\)=V^\{\\pi\}\(h\)\\rho\_\{\\mathrm\{HCA\}\}\(h,u;1\), proving the shared\-parent ranking statement\. ∎

For completed children withpπ​\(c∣n\)\>0p\_\{\\pi\}\(c\\mid n\)\>0andVπ​\(h​\(n\)\)\>0V^\{\\pi\}\(h\(n\)\)\>0, apply Bayes’ rule toC=\(U,O\)C=\(U,O\)under the joint kernelpπ​\(c∣n\)p\_\{\\pi\}\(c\\mid n\)\. The corresponding ratio is

ρc=ℙπ​\(C=c∣h⁡\(n\),R=1\)pπ​\(c∣n\)=ℙπ​\(R=1∣h⁡\(n\),C=c\)ℙπ​\(R=1∣h​\(n\)\)\.\\rho\_\{c\}=\\frac\{\\mathbb\{P\}\_\{\\pi\}\(C=c\\mid h\(n\),R=1\)\}\{p\_\{\\pi\}\(c\\mid n\)\}=\\frac\{\\mathbb\{P\}\_\{\\pi\}\(R=1\\mid h\(n\),C=c\)\}\{\\mathbb\{P\}\_\{\\pi\}\(R=1\\mid h\(n\)\)\}\.\(20\)Its numerator conditions on the realized observation\. The action\-conditioned value in the lemma averages over that observation\. The practical score in[Equation7](https://arxiv.org/html/2610.12828#S4.E7)is evaluated on the completed history, and therefore supplies a proxy for this completed\-child quantity\.

### D\.2Exact Importance Identities

###### Proof of[Proposition1](https://arxiv.org/html/2610.12828#Thmproposition1)\.

For the direct tilt, substitution ofqs​\(c\)=p⁡\(c\)​s​\(c\)/Zq\_\{s\}\(c\)=p\(c\)s\(c\)/Zyields

∫qs​\(c\)​Zs⁡\(c\)​f​\(c\)​𝑑c=∫p⁡\(c\)​f​\(c\)​𝑑c\.\\int q\_\{s\}\(c\)\\frac\{Z\}\{s\(c\)\}f\(c\)\\,dc=\\int p\(c\)f\(c\)\\,dc\.\(21\)The same calculation applies to discrete children by replacing integrals with sums\. Support coverage ensures that all nonzero target contributions are represented\.

For finite\-pool selection, condition on the entire candidate pool\. Then

∑i=1Nαi​f⁡\(Ci\)N​αi=1N​∑i=1Nf⁡\(Ci\)\.\\sum\_\{i=1\}^\{N\}\\alpha\_\{i\}\\frac\{f\(C\_\{i\}\)\}\{N\\alpha\_\{i\}\}=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}f\(C\_\{i\}\)\.\(22\)Averaging over the iid candidates gives𝔼p​\[f​\(C\)\]\\mathbb\{E\}\_\{p\}\[f\(C\)\]\. The resulting inverse\-selection weight is

1N​αi=1N​∑js⁡\(Cj\)s⁡\(Ci\)\.\\frac\{1\}\{N\\alpha\_\{i\}\}=\\frac\{\\frac\{1\}\{N\}\\sum\_\{j\}s\(C\_\{j\}\)\}\{s\(C\_\{i\}\)\}\.\(23\)For random continuation estimatesf^i\\widehat\{f\}\_\{i\}, the same proof holds if𝔼\[f^i∣C1:N,I=i\]=f\(Ci\)\\mathbb\{E\}\[\\widehat\{f\}\_\{i\}\\mid C\_\{1:N\},I=i\]=f\(C\_\{i\}\)\. A fresh policy continuation supplies this conditional estimate of the selected child’s value\. ∎

The finite\-pool identity separates two sources of randomness\. Candidate generation gives a sample from the base kernel, and score\-based selection changes the conditional distribution over that sample\. Its exact correction uses the mean score of all proposed candidates, including candidates whose continuations are not completed\.

For the exact success\-conditioned ratio, a child with zero success probability has zero proposal mass\. The reward\-value integral can still satisfy coverage when its integrand vanishes on those children\. Recovering a general centered signal instead requires coverage for that signal’s support\. Positive proxy scores supply full conditional coverage within a finite candidate pool\.

#### Two\-child illustration\.

Suppose the rollout policy assigns probability1/21/2to each ofc1,c2c\_\{1\},c\_\{2\}, and their positive scores ares⁡\(c1\)=1s\(c\_\{1\}\)=1ands⁡\(c2\)=3s\(c\_\{2\}\)=3\. The tilted proposal samples them with probabilities1/41/4and3/43/4\. Its normalizer isZ=2Z=2, so the inverse weights are22and2/32/3\. For arbitrary child signalsf1,f2f\_\{1\},f\_\{2\}, their weighted expectation is

14​\(2​f1\)\+34​\(23​f2\)=12​f1\+12​f2\.\\tfrac\{1\}\{4\}\(2f\_\{1\}\)\+\\tfrac\{3\}\{4\}\(\\tfrac\{2\}\{3\}f\_\{2\}\)=\\tfrac\{1\}\{2\}f\_\{1\}\+\\tfrac\{1\}\{2\}f\_\{2\}\.\(24\)The higher\-scoring child receives more sampling effort, while each of its observations receives less weight in the base\-policy estimate\. The same calculation holds conditionally for a candidate pool containing these two children\. The score controls the allocation of samples, and the correction preserves the expectation they estimate\.

### D\.3The Marginal Law of Finite\-Pool Selection

LetC1,…,CNC\_\{1\},\\ldots,C\_\{N\}be iid fromppand select an index in proportion to a positive scoress\. Exchangeability gives the marginal density of the selected child as

qN​\(c\)=N​p​\(c\)​𝔼​\[s⁡\(c\)s⁡\(c\)\+∑j=2Ns⁡\(Cj\)\]\.q\_\{N\}\(c\)=Np\(c\)\\,\\mathbb\{E\}\\\!\\left\[\\frac\{s\(c\)\}\{s\(c\)\+\\sum\_\{j=2\}^\{N\}s\(C\_\{j\}\)\}\\right\]\.\(25\)To obtain this expression, sum the probability of selecting each of theNNpositions, condition on the value at that position, and integrate the remainingN−1N\-1candidates\. In particular,q1=pq\_\{1\}=p\. For scores bounded above and bounded away from zero, the law of large numbers and dominated convergence giveqN​\(c\)/p⁡\(c\)→s⁡\(c\)/𝔼p​\[s⁡\(C\)\]q\_\{N\}\(c\)/p\(c\)\\to s\(c\)/\\mathbb\{E\}\_\{p\}\[s\(C\)\]whereverp⁡\(c\)\>0p\(c\)\>0\. This identifies the normalized score tilt as the large\-pool limit of the selection rule\.

The finite\-pool correction in[Equation23](https://arxiv.org/html/2610.12828#A4.E23)is exact at every pool size\. The normalized sibling backup in[Equation14](https://arxiv.org/html/2610.12828#S5.E14)instead uses the completed children retained in the tree\. That set contains original policy children and alternatives added at adaptively selected parents\. Its scores and downstream signals are coupled to the tree\-construction history\. The direct\-tilt model supplies the inverse\-score form of the practical operator, and the empirical component comparison measures that operator on the resulting finite trees\.

### D\.4Self\-Normalized Estimation and Tree Backups

SupposeD1,…,DmD\_\{1\},\\ldots,D\_\{m\}are iid draws from the direct tiltqsq\_\{s\}, withs\>0s\>0on the base support,0<Z<∞0<Z<\\infty, and𝔼p​\|f⁡\(C\)\|<∞\\mathbb\{E\}\_\{p\}\|f\(C\)\|<\\infty\. The self\-normalized estimator is

μ^m=∑j=1mf⁡\(Dj\)/s⁡\(Dj\)∑j=1m1/s⁡\(Dj\)\.\\widehat\{\\mu\}\_\{m\}=\\frac\{\\sum\_\{j=1\}^\{m\}f\(D\_\{j\}\)/s\(D\_\{j\}\)\}\{\\sum\_\{j=1\}^\{m\}1/s\(D\_\{j\}\)\}\.\(26\)By the strong law of large numbers, the numerator divided bymmconverges almost surely to𝔼p​\[f\]/Z\\mathbb\{E\}\_\{p\}\[f\]/Z, and the denominator divided bymmconverges to1/Z1/Z\. Henceμ^m→𝔼p​\[f\]\\widehat\{\\mu\}\_\{m\}\\to\\mathbb\{E\}\_\{p\}\[f\]almost surely\. This is a consistency statement for the specified sampling model\. At a finite sample size, self\-normalization forms a ratio of random sums and generally introduces bias\.

The practical tree backup has useful algebraic properties independently of that sampling model\. Positive scores produce nonnegative weights summing to one, so the parent signal lies between the smallest and largest child signals\. For any constantsaaandbb,

∑cw~n,c​\(a​f​\(c\)\+b\)=a​∑cw~n,c​f​\(c\)\+b\.\\sum\_\{c\}\\widetilde\{w\}\_\{n,c\}\\bigl\(af\(c\)\+b\\bigr\)=a\\sum\_\{c\}\\widetilde\{w\}\_\{n,c\}f\(c\)\+b\.\(27\)Consequently, applying the same group\-wide affine reward normalization before or after a fixed weighted backup gives the same result\. A single\-child node propagates its child’s signal unchanged\. When all leaf rewards agree,[Equation13](https://arxiv.org/html/2610.12828#S5.E13)initializes and propagates a zero signal\.

The change\-of\-measure results concern a fixed integrand and a specified selection law\. The implemented learning rule combines proxy scores, a finite adaptive tree, group\-relative leaf normalization, and a clipped GSPO objective\. These components define the algorithm evaluated in[Section6](https://arxiv.org/html/2610.12828#S6)\. The propositions establish the sampling\-estimation relationships that motivate the algorithm\.

## Appendix ETree\-construction implementation details

Two details clarify the construction in[Algorithm1](https://arxiv.org/html/2610.12828#alg1)\. First, the practical hindsight score in[Equation7](https://arxiv.org/html/2610.12828#S4.E7)uses a*completed*turnn=\(u,o\)n=\(u,o\)\. We execute every candidate against the environment before scoring it, then continue only the selected candidate to termination\. One exploration step therefore costsNNturn executions and a single full rollout\. Second, line[3](https://arxiv.org/html/2610.12828#alg1.l3)clips the score atκbr\\kappa\_\{\\mathrm\{br\}\}, which assigns exactly the valueκbr\\kappa\_\{\\mathrm\{br\}\}to every node that is not flagged\. Taking theKKsmallest scores with uniform tie\-breaking therefore expands the flagged nodes in increasing order of score and fills any remaining slots uniformly at random, which is the selection rule described in[Section4](https://arxiv.org/html/2610.12828#S4)\.

For the Qwen2\.5\-3B experiments, we use a rollout\-matched variant of TreeHCA\. Rather than first completing a fixed set of initial trajectories and branching afterward, we monitor the hindsight ratio during rollout generation\. Whenever the hindsight ratio falls below a predefined threshold, we branch from that decision point and sample two alternative children\. This keeps the total rollout budget comparable to GRPO while concentrating additional exploration on decisions identified as potentially consequential by the hindsight signal\.

Algorithm 2Hindsight\-guided chain construction0:Prompt

xx, reference answer

y⋆y^\{\\star\}, frozen policy

π\\pi, candidate count

nn, maximum turns

TmaxT\_\{\\max\}, branching threshold

κbr\\kappa\_\{\\rm br\}\.

1:Initialize the trajectory with prompt

xxand context

ℋ<0\\mathcal\{H\}\_\{<0\}\.

2:for

t=0,…,Tmax−1t=0,\\ldots,T\_\{\\max\}\-1do

3:Sample a decision

ut∼π\(⋅∣ℋ<t\)u\_\{t\}\\sim\\pi\(\\cdot\\mid\\mathcal\{H\}\_\{<t\}\)and execute it\.

4:Compute its hindsight ratio

ρ^HCA​\(ut\)\\widehat\{\\rho\}\_\{\\mathrm\{HCA\}\}\(u\_\{t\}\)\.

5:if

ρ^HCA​\(ut\)<κbr\\widehat\{\\rho\}\_\{\\mathrm\{HCA\}\}\(u\_\{t\}\)<\\kappa\_\{\\rm br\}then

6:Sample

nncandidate decisions

\{ut\(i\)\}i=1n∼π\(⋅∣ℋ<t\)\\\{u\_\{t\}^\{\(i\)\}\\\}\_\{i=1\}^\{n\}\\sim\\pi\(\\cdot\\mid\\mathcal\{H\}\_\{<t\}\)and execute each candidate\.

7:Compute

ρ^HCA\(i\)\\widehat\{\\rho\}\_\{\\mathrm\{HCA\}\}^\{\(i\)\}for each candidate\.

8:Form the hindsight\-guided distribution

pi=exp⁡\(log⁡ρ^HCA\(i\)\)∑j=1nexp⁡\(log⁡ρ^HCA\(j\)\)\.p\_\{i\}=\\frac\{\\exp\\\!\\left\(\\log\\widehat\{\\rho\}\_\{\\mathrm\{HCA\}\}^\{\(i\)\}\\right\)\}\{\\sum\_\{j=1\}^\{n\}\\exp\\\!\\left\(\\log\\widehat\{\\rho\}\_\{\\mathrm\{HCA\}\}^\{\(j\)\}\\right\)\}\.
9:Sample

I∼Categorical⁡\(p1,…,pn\)I\\sim\\mathrm\{Categorical\}\(p\_\{1\},\\ldots,p\_\{n\}\)and set

ut←ut\(I\)u\_\{t\}\\leftarrow u\_\{t\}^\{\(I\)\}\.

10:Append the selected decision

utu\_\{t\}and its observation to the trajectory\.

11:Update the context

ℋ<t\+1\\mathcal\{H\}\_\{<t\+1\}\.

12:if

utu\_\{t\}produces a final answerthen

13:break

14:returnthe completed trajectory with its terminal verifier reward\.

## Appendix FResearch assets

The experiments use the Qwen2\.5 and Qwen3 model families and the seven question\-answering benchmarks cited in[Section6](https://arxiv.org/html/2610.12828#S6)\. Dataset annotations supply reference answers for training\-time hindsight scoring and evaluation\. Retrieved passages enter the agent’s history as tool observations and are masked from the policy\-token loss\. Training uses code from the prior works AT2PO and IGRPO, which are built upon the VeRL and verl\-agent frameworks, respectively \([appendixB](https://arxiv.org/html/2610.12828#A2)\)\.

## Appendix GSample generations during training

The sibling rollouts below come from one tree during Qwen3\-8B training on HotpotQA\. Their shared prefix retrieves passages mentioning several NBA Finals series \([Table10](https://arxiv.org/html/2610.12828#A7.T10)\)\. The unsuccessful continuation immediately answers San Antonio Spurs and receives rewardR=0R=0\([Table11](https://arxiv.org/html/2610.12828#A7.T11)\)\. The successful continuation searches explicitly for the Miami Heat’s 2012 opponent, retrieves Oklahoma City Thunder, and receivesR=1R=1\([Table12](https://arxiv.org/html/2610.12828#A7.T12)\)\. These trajectories expose alternative decisions under the same initial evidence: answering immediately or seeking further information\.TreeHCAuses their completed outcomes to compute intermediate credit through the tree\.

Table 10:Shared prefix of the sibling rollouts on HotpotQA\. Blue marks model output and green marks retrieved passages\. Tool\-response delimiters are omitted\.Table 11:The unsuccessful continuation from the shared parent of[Table10](https://arxiv.org/html/2610.12828#A7.T10)\. It issues no further query and commits to a wrong answer in a single turn\.Table 12:The successful continuation from the same shared parent\. It declines to answer from the ambiguous passages and reformulates the query, which retrieves an explicit statement of the required fact\.