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

Debajoy Mukherjee; Jeremy Carleton; Sushil Vemuri; Srinivas Shakkottai; Dileep Kalathil

cs.LGOct 9, 2026

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

Authors: Debajoy Mukherjee, Jeremy Carleton, Sushil Vemuri, Srinivas Shakkottai, Dileep Kalathil

Organizations: Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA

Abstract

Outcome-supervised group-relative policy optimization (GRPO) assigns the same advantage to every token in an LLM agent trajectory, leaving useful and unhelpful decisions undifferentiated. Hindsight credit assignment (HCA) can refine this feedback, but its estimates rely on trajectories containing informative alternatives at consequential histories. We introduce TreeHCA, which couples hindsight-guided exploration with hindsight credit assignment. TreeHCA uses changes in reference-answer likelihood to revisit intermediate histories and sample alternative continuations, forming a tree of reasoning and tool interactions. Because this exploration changes the distribution of sampled continuations, we derive the corresponding inverse-hindsight importance correction, including an exact finite-pool identity. We use this structure in a normalized tree backup that propagates terminal outcomes into turn-level advantages. This shared hindsight structure is TreeHCA's central design principle, linking informative exploration with hindsight-guided credit assignment. Across seven question-answering benchmarks and three Qwen backbones, TreeHCA outperforms all baselines in aggregate exact match, validating the effectiveness of paired exploration and credit assignment for multi-turn LLM agent training. Our code is available at github.com/TheBlackCat22/TreeHCA.

Figures & tables

Figure 1: TreeHCA pairs 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.

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=2$ policy decisions are executed and scored as completed candidates. (3) A categorical draw selects one using normalized hindsight scores. It continues under $\pi$ to a verifier reward, while the original child and subtree remain. Scores and outcomes are illustrative.

Method	Type	Multi-hop QA				Single-hop QA			Avg.
Method	Type	Hotpot	2Wiki	MuSiQue	Bamb.	NQ	TriviaQA	PopQA	Avg.
Backbone: Qwen2.5-3B
Search-R1	Chain-based	32.4	31.9	10.3	26.4	34.1	54.5	37.8	37.4
ZeroSearch	Chain-based	27.4	30.0	9.8	11.1	41.4	57.4	44.8	39.1
GiGPO	Chain-based	36.8	36.2	12.2	29.6	43.1	60.5	46.1	43.3
IGPO	Chain-based	37.5	36.4	11.8	25.6	44.9	61.8	46.5	43.6

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.

Method	Type	Multi-hop QA				Single-hop QA			Avg.
Method	Type	Hotpot	2Wiki	MuSiQue	Bamb.	NQ	TriviaQA	PopQA	Avg.
Backbone: Qwen2.5-3B
Tree-GRPO	Tree-based	31.1	31.7	11.9	28.0	44.5	60.4	43.7	40.8
IGRPO	Tree-based	38.0	39.0	14.3	29.6	45.1	60.0	45.2	43.9
TreeHCA (n=5)	Tree-based	39.9	39.4	14.8	32.4	45.3	61.5	44.4	44.9

Table 2: Qwen2.5-3B-Instruct comparison for tree-based baselines: EM (%). Colors follow Table 1 .

Method	Multi-hop QA					Single-hop QA
Method	Hotpot	2Wiki	MuSiQue	Bamb.	W. Avg.	NQ	TriviaQA	PopQA	W. Avg.
Backbone: Qwen3-4B
ReAct	30.42	32.92	12.83	44.80	30.01	26.75	53.53	35.34	41.31
GRPO	44.76	51.40	21.60	50.40	46.02	45.98	65.17	49.18	54.97
GSPO	47.07	49.25	22.68	50.40	45.69	46.01	64.24	48.50	54.28
TreeGRPO	46.40	51.10	20.27	53.60	46.26	46.31	64.91	49.75	55.19

Table 3: Qwen3 comparison: EM (%). ReAct, GRPO, GSPO, and AEPO results are from Zong et al. (2026) . TreeGRPO, AT 2 PO, and TreeHCA use 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.

Exploration	Credit	EM	F1
Hindsight	TreeHCA	51.76	65.88
Entropy	TreeHCA	51.17	64.17
Entropy	AT 2 PO	50.78	63.85
Hindsight	AT 2 PO	49.60	62.74
Random	TreeHCA	49.02	61.60
Policy chains	GSPO	47.46	60.76

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 Table 1 .

Backbone	Hotpot	2Wiki	MuSiQue	Bamb.	W. Avg.
Qwen3-4B	$49.23\pm 2.30$	$52.73\pm 0.34$	$24.15\pm 1.68$	$53.60\pm 0.00$	$48.52\pm 0.75$
Qwen3-8B	$50.51\pm 1.03$	$54.99\pm 1.55$	$24.50\pm 0.36$	$56.00\pm 4.53$	$50.25\pm 1.27$

Table 5: TreeHCA multi-hop performance as mean

\pm

one standard deviation over three training seeds. EM and its standard deviation are in percentage points. Means match Table 3 . W. Avg. weights datasets by size.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Policy optimization
Hyperparameter	Value
Optimizer	AdamW
Learning rate	1e-6
Clip_ratio	0.2
Training batch size	64
PPO mini-batch size	8

Appendix

Table 6: Qwen3 training and rollout settings shared by AT 2 PO and TreeHCA .

Training
Hyperparameter	Value
Number of training steps	200
Exploration threshold $\kappa_{\mathrm{br}}$	$-0.14$
Sequence and interaction limits
Maximum turns	4
Maximum rollout length	512

Appendix

Table 7: Rollout settings for Qwen2.5-3B experiments.

Hyperparameter	Value
Reference-answer score smoothing $\epsilon_{\mathrm{smooth}}$	0.05
Exploration threshold $\kappa_{\mathrm{br}}$	$-0.14$
Sibling penalty $\gamma$	0.05
Candidates per selected parent $N$	2

Appendix

Table 8: TreeHCA score and exploration controls.

Model	AT 2 PO	TreeHCA
Qwen3-4B	31.50	34.40
Qwen3-8B	32.58	36.20

Appendix

Table 9: Wall-clock training time in hours on 8 H200 GPUs.

Figure 3: F1 for the component comparison in Table 4 . The figure reports the F1 column, including 65.88 for the complete hindsight-guided exploration and credit pair.

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)}.

Appendix

Algorithm 2 Hindsight-guided chain construction

Shared Prefix (identical in both continuations)
Question: Juwan Howard beat what team to win his first NBA Final?
Labeled Answer: Oklahoma City Thunder
<think> Okay, I need to find out which team Juwan Howard beat to win his first NBA Finals. First, I should confirm who Juwan Howard is. He was an NBA coach, right? Wait, but the question says he beat a team to win his first NBA Final. Hmm, maybe I’m mixing up some details. Let me check. </think> <search> Juwan Howard NBA coach </search>
Page 1: “Juwan Howard” Juwan Antonio Howard (born February 7, 1973) is an American former professional basketball player who is an assistant coach for the Miami Heat of the National Basketball Association (NBA). Howard formerly played for the Heat from 2010 until 2013. A one-time All-Star and one-time All-NBA power forward, he began his NBA career as the fifth overall pick in the 1994 NBA draft, selected by the Washington Bullets.
Page 2–3: * Omitted for brevity *
<think> Wait, the search result says Juwan Howard was a player, not a coach. But the original question says he beat a team to win his first NBA Final. Maybe there’s confusion here. Perhaps I should search for “Juwan Howard NBA Finals” to see if he was a coach or player in the Finals. </think> <search> Juwan Howard NBA Finals </search>

Appendix

Table 10: Shared prefix of the sibling rollouts on HotpotQA. Blue marks model output and green marks retrieved passages. Tool-response delimiters are omitted.

Unsuccessful Continuation Terminal reward $R=0$
* Shared prefix omitted; see Table 10 *
<think> Wait, the first search result says the 2012 NBA Finals were between Miami Heat and the San Antonio Spurs. So, the Heat beat the Spurs. Therefore, the answer is San Antonio Spurs. </think>
Juwan Howard won his first NBA championship with the Miami Heat in the 2012 NBA Finals. The team he beat to achieve this victory was the San Antonio Spurs.
<answer> The final answer is San Antonio Spurs </answer>

Appendix

Table 11: The unsuccessful continuation from the shared parent of Table 10 . It issues no further query and commits to a wrong answer in a single turn.

Successful Continuation Terminal reward $R=1$
* Shared prefix omitted; see Table 10 *
<think> Hmm, the first search result says that in the 2012 NBA Finals, the Miami Heat were in the series, but it doesn’t mention the opponent. The first paragraph says the Heat had previously appeared in 2006 and 2011 against the Mavericks. The Spurs were the team that beat the Heat in the 2014 Finals. So the answer isn’t in the search result. Let me think again. Since Howard was on the Heat team that won the 2012 NBA Finals, but the search result is not clear, maybe I should search for “2012 NBA Finals Miami Heat opponent” directly. </think> <search> 2012 NBA Finals Miami Heat opponent </search>
Page 1: “2012 NBA Finals” * Identical to Page 1 above; omitted for brevity *
Page 2: “2012 NBA Finals” The 2012 NBA Finals was the championship series of the 2011–12 season of the National Basketball Association (NBA), and the conclusion of the season’s playoffs. The Eastern Conference champion Miami Heat defeated the Western Conference champion Oklahoma City Thunder 4 games to 1 to win their second NBA title. Heat Small forward LeBron James was named the Finals MVP.
Page 3: “2011–12 Miami Heat season” …On June 21, the Miami Heat won the NBA Championship at home against the Oklahoma City Thunder,
<think> Wait, according to this, the Miami Heat defeated the Oklahoma City Thunder in the 2012 NBA Finals. So, the answer would be the Oklahoma City Thunder. But let me check again. From the last search result, the 2012 NBA Finals were between the Miami Heat and the Oklahoma City Thunder. So, the team Juwan Howard beat was the Oklahoma City Thunder. </think>

Appendix

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.

LLM Agent Training

Large language model agent training teaches models to plan, use tools, and learn from multi-step interaction with environments.

See all 586 papers

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents
Sep 28, 2026Haodong Zhu, Yangyang Ren, Changbai Li +4Credit Assignment in RL Step-Level Credit Assignment in RL
Beihang University · Zhongguancun Academy · Communication University of China +1
Hindsight Credit Assignment for Long-Horizon LLM Agents
Mar 7, 2026Hui-Ze Tan, Xiao-Wen Yang, Hao Chen +7Credit Assignment in RL Long-Horizon LLM Agents
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China +2
Multiscale Policy Optimization for Long-Horizon LLM Agents
Oct 26, 2026Tao Ren, Hui Yang, Jia Deng +16Policy Optimization RL for LLM Agents
Peking University · IQuest Research · Tsinghua University +3

Sep 28, 2026J/K move · Enter open · S save

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents

Haodong Zhu, Yangyang Ren, Changbai Li, Sheng Xu+3

Beihang University · Zhongguancun Academy · Communication University of China+1

Credit Assignment in RL Step-Level Credit Assignment in RL Model-Free RL Long-Horizon LLM Agents Policy Learning RL for LLM Agents

Open paper AskPDF arXiv

Group-based reinforcement learning (RL) has advanced large language models (LLMs) and is increasingly extending to agentic tasks, where sparse terminal rewards make step-level credit assignment essential. Existing methods assign credit from what follows an action in sampled rollouts, but do not explicitly capture its retrospective relation to the realized outcome. Hindsight credit assignment (HCA) instead attributes credit through the ratio of hindsight to behavior-policy probabilities, but estimating the hindsight distribution requires an auxiliary model or an extra pass. To address this estimation bottleneck, we propose GraphHCA, a model-free realization of HCA that eliminates explicit hindsight-distribution estimation. For terminal-goal tasks with deterministic transitions, Bayes' rule reduces the hindsight ratio to a ratio of behavior-policy success probabilities at consecutive states. Taking logs yields a state-wise success potential, whose increment across a transition provides step-level credit. GraphHCA estimates this potential from pooled rollouts through a discounted recursion on the induced transition graph, which admits a unique fixed point on any directed graph. The resulting step-level signal is combined with the trajectory-level advantage, requiring neither a learned hindsight model nor an extra forward pass and recovering GRPO when the step-level weight is zero. Among all compared baselines, GraphHCA achieves state-of-the-art results on ALFWorld and WebShop at both LLM scales, and on Sokoban with a vision-language agent. For example, on ALFWorld it improves overall success rate by up to 24.6 points over GRPO and by up to 4.7 points over the strongest step-level baseline.

Abstract

LLM Agent Training

Explore similar work

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents

Hindsight Credit Assignment for Long-Horizon LLM Agents

Multiscale Policy Optimization for Long-Horizon LLM Agents