ASCT: Attentive Search over Counterfactual Trees for Credit Assignment in Agentic Reinforcement Learning

Yang Li; Jinhan Yang; hai liu; Di Wan; Xiyu Chen; Zongsi Xu; Tuo Zhou; Sheng Zhong

cs.AISep 28, 2026

ASCT: Attentive Search over Counterfactual Trees for Credit Assignment in Agentic Reinforcement Learning

Authors: Yang Li, Jinhan Yang, hai liu, Di Wan, Xiyu Chen, Zongsi Xu, Tuo Zhou, Sheng Zhong, +3 more

Organizations: University of Hong Kong · The Chinese University of Hong Kong · Jiangxi Science and Technology Normal University · Shenzhen University

Abstract

Terminal utility evaluates a complete agentic workflow, but learning requires credit for the decisions within it. We introduce Attentive Search over Counterfactual Trees (ASCT), a framework that turns training-time multi-step search into local action credit. At actor-visited states, an auxiliary tree evaluates alternative legal actions from the same recoverable prefix. Its action-value table is centered by the frozen actor's probabilities and supplies credit for PPO on actor-sampled trajectories. This protocol connects counterfactual evaluation to policy learning while deploying the actor alone. Uniform, UCT, and cost-aware AgentUCT instantiate the framework. On HotpotQA agentic retrieval-augmented generation, all three improve mean held-out utility over trajectory-return PPO and workflow-adapted VinePPO. Across three seeds, ASCT-AgentUCT reaches 0.6187 utility versus 0.5939 for VinePPO, with gains in answer F1 and execution cost, and uses 50.3% fewer recorded auxiliary Qwen tokens. Transfer and component-description studies examine the learned policies beyond the training setting.

Figures & tables

Stage	Actions
Query formulation	Original question; Query2Doc; two-query decomposition
Retriever	BM25; E5 dense; BGE-M3 hybrid; Qwen3 embedding; reciprocal-rank fusion
Passage selection	Relevance ranking; maximal marginal relevance
Retrieval width	3 or 6 passages
Retrieval control	Stop; continue while fewer than three rounds have executed
Reranking	Preserve order; Qwen3 reranker

Table 1: Executable RAG decisions. A workflow uses up to three retrieval rounds. Choices within a row are legal alternatives at that stage.

Method	Workflow utility	Answer F1	Execution words
Base	0.5648	0.6954	5,348.7
PPO	0.5651 $\pm$ 0.0021	0.6913 $\pm$ 0.0021	5,170.4 $\pm$ 76.8
VinePPO	0.5939 $\pm$ 0.0062	0.7115 $\pm$ 0.0026	4,817.7 $\pm$ 179.7
ASCT-Uniform	0.6146 $\pm$ 0.0191	0.7316 $\pm$ 0.0168	4,792.2 $\pm$ 151.4
ASCT-UCT	0.6075 $\pm$ 0.0241	0.7257 $\pm$ 0.0260	4,841.2 $\pm$ 112.8
ASCT-AgentUCT	0.6187 $\pm$ 0.0076	0.7266 $\pm$ 0.0126	4,420.8 $\pm$ 213.3

Table 2: HotpotQA held-out results of the final policies. Workflow utility is the mean over test questions, using official F1 and execution words. Trained rows are mean

\pm

sample SD over three seeds.

Auxiliary environment execution
Token count (M)	VinePPO	ASCT- Uniform	ASCT- UCT	ASCT- AgentUCT
Auxiliary total	388.374 $\pm$ 4.694	197.077 $\pm$ 0.024	197.588 $\pm$ 0.068	193.088 $\pm$ 0.404
Environment subtotal $T_{\mathrm{env}}$	137.088 $\pm$ 1.231	197.077 $\pm$ 0.024	197.588 $\pm$ 0.068	193.088 $\pm$ 0.404
Generator input (4B)	89.972 $\pm$ 0.278	139.452 $\pm$ 0.162	139.613 $\pm$ 0.193	137.776 $\pm$ 0.174
Generator output (4B)	3.590 $\pm$ 0.009	5.874 $\pm$ 0.003	5.883 $\pm$ 0.002	5.833 $\pm$ 0.003
Query embedding (0.6B)	0.611 $\pm$ 0.012	0.689 $\pm$ 0.002	0.690 $\pm$ 0.001	0.689 $\pm$ 0.002

Table 3: Combined token ledger for the listed Qwen model operations across three training iterations, in millions (mean

\pm

sample SD over three seeds). The first row sums auxiliary environment execution and auxiliary actor scoring within each seed. Indented rows are components of their section subtotal.

Evaluator	Mean rollout $U$	Auxiliary tokens (M)	$\overline{J}_{\mathrm{search}}$
VinePPO	0.5507 $\pm$ 0.0027	388.374 $\pm$ 4.694	0.4893 $\pm$ 0.0019
ASCT-Uniform	0.5283 $\pm$ 0.0022	197.077 $\pm$ 0.024	0.4972 $\pm$ 0.0022
ASCT-UCT	0.5515 $\pm$ 0.0031	197.588 $\pm$ 0.068	0.5203 $\pm$ 0.0031
ASCT-AgentUCT	0.5526 $\pm$ 0.0016	193.088 $\pm$ 0.404	0.5220 $\pm$ 0.0016

Table 4: Mean auxiliary rollout utility, recorded auxiliary token cost, and

\overline{J}_{\mathrm{search}}

over complete training runs. Rollout utility uses the training scorer; tokens include the listed Qwen environment operations and auxiliary actor scoring. Values are mean

\pm

sample SD across three seeds.

Dataset	Method	F1	Utility	Execution words
2Wiki	Base	0.5583	0.4732	3,488.0
2Wiki	PPO	0.5883 $\pm$ 0.0100	0.5067 $\pm$ 0.0102	3,342.6 $\pm$ 130.9
2Wiki	VinePPO	0.6517 $\pm$ 0.0375	0.5767 $\pm$ 0.0360	3,069.3 $\pm$ 133.7
2Wiki	ASCT-Uniform	0.6567 $\pm$ 0.0321	0.5832 $\pm$ 0.0329	3,009.9 $\pm$ 47.6
2Wiki	ASCT-UCT	0.6583 $\pm$ 0.0522	0.5837 $\pm$ 0.0508	3,055.2 $\pm$ 59.8
2Wiki	ASCT-AgentUCT	0.6700 $\pm$ 0.0321	0.5982 $\pm$ 0.0313	2,939.3 $\pm$ 73.7

Table 5: Cross-dataset results on the fixed 100-question cohorts. F1, workflow utility, and execution words are mean

\pm

sample SD over three seeds; Base is deterministic.

Planner	Type + correct relation	Type only	Name only	Type + opposite relation
Base	0.820	0.010	0.000	0.020
PPO	0.830 $\pm$ 0.044	0.033 $\pm$ 0.042	0.000 $\pm$ 0.000	0.020 $\pm$ 0.000
VinePPO	0.947 $\pm$ 0.035	0.280 $\pm$ 0.108	0.000 $\pm$ 0.000	0.040 $\pm$ 0.010
ASCT-Uniform	0.960 $\pm$ 0.017	0.300 $\pm$ 0.111	0.000 $\pm$ 0.000	0.037 $\pm$ 0.006
ASCT-UCT	0.933 $\pm$ 0.021	0.197 $\pm$ 0.068	0.000 $\pm$ 0.000	0.027 $\pm$ 0.012
ASCT-AgentUCT	0.950 $\pm$ 0.036	0.373 $\pm$ 0.205	0.000 $\pm$ 0.000	0.050 $\pm$ 0.020

Table 6: Selection rate for the same new retriever under four descriptions. The correct relation states a preference for tagged, answer-bearing evidence; the opposite relation states a preference for untagged passages. Values are mean

\pm

sample SD over three seeds.

Continuation variant	Test F1	Test Utility	Aux. tokens (M)
ASCT-ActorRollout	$0.7142\pm 0.0090$	$0.5975\pm 0.0128$	$495.24\pm 13.29$
ASCT-Uniform	$0.7316\pm 0.0168$	$0.6146\pm 0.0191$	$197.08\pm 0.02$

Table 7: ASCT continuation control: shared

B=12

, credit, PPO settings, and 400 test QIDs. Full-run auxiliary tokens; mean

\pm

sample SD over three seeds.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Inputs: actor $\pi_{\theta}$ , training tasks $\mathcal{D}$ , evaluator $E$ , budget $B$ , utility $U$ .
1	for each training iteration do
2	Freeze $\pi_{\mathrm{old}}\leftarrow\pi_{\theta}$ ; initialize actor-record buffer $\mathcal{R}\leftarrow\varnothing$ .
3	for each task in $\mathcal{D}$ do
4	Initialize workflow state $s$ .
5	while $s$ is nonterminal do
6	Compute $p_{a}=\pi_{\mathrm{old}}(a\mid s)$ for $a\in\mathcal{A}(s)$ ; sample $a_{t}\sim p$ .

Appendix

Algorithm 1 ASCT with actor-centered credit and PPO

Setting	Value
Planner	Qwen3-4B-Instruct-2507
Adapter	LoRA rank 4, alpha 8, dropout 0; query and value projections
Optimizer	AdamW; learning rate $10^{-5}$
Optimizer batch size	8
PPO	Two update epochs per iteration; clipping $\epsilon=0.2$
Advantage processing	Standardization across collected decisions within each iteration

Appendix

Table 8: Shared training and evaluation configuration. Training uses the repository answer scorer; endpoint reporting uses the corresponding evaluation scorer.

Method	Credit at a sampled actor decision	Auxiliary evaluation
Base	No policy update	None
PPO	Terminal trajectory utility	None
VinePPO	Adjacent Monte Carlo state values	Actor continuations
ASCT-Uniform	Actor-centered action advantage	Uniform tree evaluator
ASCT-UCT	Actor-centered action advantage	Utility-directed UCT evaluator
ASCT-AgentUCT	Actor-centered action advantage	Cost-aware AgentUCT evaluator

Appendix

Table 9: Experimental methods. All trained rows use the same planner family and PPO update settings.

Role / input	Core instruction	Output constraint
Actor / current workflow observation	“You select the next action in a RAG workflow.”	JSON with one action field; probabilities normalized over legal labels.
Query2Doc / question	“Write a short hypothetical passage that would answer the question.”	JSON with one pseudo_document string, used as the retrieval query.
Decomposition / question	“Decompose the multi-hop question into exactly two focused search queries.”	JSON queries : exactly two nonempty strings.
Answer / question and evidence passages	“Answer only from the evidence. Return the shortest answer span that satisfies the question.”	JSON answer and citations ; use UNKNOWN if evidence is insufficient and cite relevant evidence.

Appendix

Table 10: Fixed LLM instructions and their runtime inputs. Quoted instructions are taken from the implementation; output constraints are summarized.

Evaluator	Total tokens (M)	Tokens / actor state	$\overline{J}_{\mathrm{search}}$
ASCT-Uniform	197.077 $\pm$ 0.024	3,732.5 $\pm$ 3.2	0.4972 $\pm$ 0.0022
ASCT-UCT	197.588 $\pm$ 0.068	3,749.5 $\pm$ 2.6	0.5203 $\pm$ 0.0031
ASCT-AgentUCT	193.088 $\pm$ 0.404	3,664.5 $\pm$ 9.2	0.5220 $\pm$ 0.0016

Appendix

Table 11: Auxiliary evaluation cost within ASCT. Totals are millions of environment tokens. Per-state values normalize within each seed. Search return charges realized auxiliary work as in Equation 5 . Values are mean

\pm

sample SD.

Method	$N=100{,}000$	$N=500{,}000$	$N=1{,}000{,}000$
PPO	0.5651 $\pm$ 0.0021	0.5651 $\pm$ 0.0021	0.5651 $\pm$ 0.0021
VinePPO	0.2055 $\pm$ 0.0046	0.5162 $\pm$ 0.0056	0.5550 $\pm$ 0.0059
ASCT-Uniform	0.4175 $\pm$ 0.0190	0.5752 $\pm$ 0.0191	0.5949 $\pm$ 0.0191
ASCT-UCT	0.4099 $\pm$ 0.0241	0.5680 $\pm$ 0.0241	0.5878 $\pm$ 0.0241
ASCT-AgentUCT	0.4256 $\pm$ 0.0075	0.5801 $\pm$ 0.0076	0.5994 $\pm$ 0.0076

Appendix

Table 12: Projected final-policy value after amortizing total auxiliary tokens:

J_{\mathrm{deploy}}(N)

, mean

\pm

sample SD over three seed-level projections.

N

is the assumed number of uses. These values correspond to Figure 5 .

Method	Easy ( $n=76$ )	Medium ( $n=256$ )	Hard ( $n=68$ )
Base	0.6348	0.5723	0.4582
PPO	0.6405 $\pm$ 0.0023	0.5702 $\pm$ 0.0050	0.4616 $\pm$ 0.0053
VinePPO	0.6613 $\pm$ 0.0046	0.6031 $\pm$ 0.0108	0.4836 $\pm$ 0.0191
ASCT-Uniform	0.6565 $\pm$ 0.0045	0.6334 $\pm$ 0.0265	0.4968 $\pm$ 0.0097
ASCT-UCT	0.6540 $\pm$ 0.0056	0.6222 $\pm$ 0.0345	0.5005 $\pm$ 0.0097
ASCT-AgentUCT	0.6583 $\pm$ 0.0111	0.6338 $\pm$ 0.0178	0.5174 $\pm$ 0.0120

Appendix

Table 13: Final-policy utility by HotpotQA test difficulty, using the official answer scorer. Values are mean

\pm

sample SD across three training seeds; Base is deterministic. The three difficulty groups partition the same 400 test questions used in Table 2 .

Seed	All decisions	Multi-action decisions	Sign changes	Rate (%)
11	52,828	12,000	1,043	8.69
23	52,833	12,000	1,021	8.51
37	52,741	12,000	1,053	8.78

Appendix

Table 14: Baseline semantics on actual ASCT-Uniform training decisions. Counts cover three training iterations per seed. Multi-action states have at least three legal actions. Sign changes compare actor-weighted and uniform-action centering of the same recorded Q table at the actual sampled action.

Evaluator	Repeat Q SD	Credit agreement (%)	Tokens (k)
Root-stratified MC	$0.1203\pm 0.0653$	$63.3\pm 11.5$	$11.09\pm 0.13$
ASCT-Uniform	$0.0619\pm 0.0293$	$80.0\pm 10.0$	$11.28\pm 0.51$

Appendix

Table 15: Internal tree allocation at the training budget (

B=12

). Both evaluators cover legal root actions, use uniform expansion/rollout sampling, and retain WTB reuse. Two training questions provide five-action retriever states for each of three frozen actors; two repeats per state. Cells report mean

\pm

sample SD across seed means. Q SD and credit-sign agreement measure repeatability.

$B$	Evaluator	Repeat Q SD	Credit (%)	Tokens (k)
12	Root-stratified MC	$0.1203\pm 0.0653$	$63.3\pm 11.5$	$11.09\pm 0.13$
12	ASCT-Uniform	$0.0619\pm 0.0293$	$80.0\pm 10.0$	$11.28\pm 0.51$
48	Root-stratified MC	$0.0368\pm 0.0088$	$83.3\pm 5.8$	$38.15\pm 1.03$
48	ASCT-Uniform	$0.0484\pm 0.0158$	$90.0\pm 17.3$	$36.98\pm 1.67$

Appendix

Table 16: Root-stratified MC and Uniform tree evaluation on the same five-action states. All values are mean

\pm

sample SD across three seed means. Each state has two repeats; budgets are prefixes of the completed 48-trial records.

Evaluator	Repeat Q SD	Ref. order (%)	Tokens (k)
Root-stratified MC	$0.0149\pm 0.0221$	$97.9\pm 3.6$	$3.90\pm 0.31$
ASCT-Uniform	$0.0064\pm 0.0093$	$99.0\pm 1.8$	$4.16\pm 0.31$
ASCT-UCT	$0.0093\pm 0.0148$	$96.9\pm 5.4$	$4.18\pm 0.32$
ASCT-AgentUCT	$0.0085\pm 0.0121$	$99.0\pm 1.8$	$4.07\pm 0.37$
Actor MC	$0.0038\pm 0.0040$	$99.0\pm 1.8$	$4.78\pm 0.53$

Appendix

Table 17: Four-question binary-state diagnostic: eight states per actor seed, four repeats at

B=12

. Order agreement uses two independent 96-trial actor-continuation batches as its reference. Total auxiliary tokens include actor scoring. Values are mean

\pm

sample SD across three seed means.

S/E/R	Tokens@12 (k)	Tokens@48 (k)	Q SD@48	Credit@48 (%)
UCT (000)	$11.14\pm 0.63$	$35.66\pm 1.36$	$0.0609\pm 0.0150$	$66.7\pm 5.8$
001	$10.94\pm 0.66$	$35.93\pm 0.73$	$0.0528\pm 0.0128$	$80.0\pm 20.0$
010	$11.69\pm 1.55$	$37.01\pm 1.96$	$0.0526\pm 0.0123$	$76.7\pm 15.3$
011	$11.55\pm 1.29$	$34.90\pm 2.24$	$0.0492\pm 0.0219$	$80.0\pm 10.0$
100	$11.24\pm 0.57$	$34.94\pm 2.12$	$0.0471\pm 0.0197$	$70.0\pm 17.3$
101	$11.01\pm 0.50$	$36.15\pm 0.68$	$0.0450\pm 0.0074$	$76.7\pm 5.8$

Appendix

Table 18: Cost-aware selection, expansion and rollout (S/E/R) on the same two questions and three actors. Bits enable cost awareness at each phase; 000 is UCT and 111 is native AgentUCT. Cells are mean

\pm

sample SD across seed means, with two repeats per state. WTB reuse is enabled throughout.

Evaluator	Mean utility	Tokens	$\overline{J}_{\mathrm{search}}$	Credit agreement (%)
ASCT-Uniform	0.5449	21,077.9	0.4571	76.7
ASCT-UCT	0.5887	20,788.5	0.5021	76.7
ASCT-AgentUCT	0.5960	20,531.3	0.5105	73.3

Appendix

Table 19: The 24-evaluation checkpoint of the full curves. Values average the same two questions, two repeats and three actor seeds. The complete curves retain seed-level variability.

Explore similar work

Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness
Jul 27, 2026Yang Li, Hai Liu, Dian Shao +8Agentic Workflows Agentic Optimization
1The University of Hong Kong · School of Artificial Intelligence, Jiangxi Science and Technology Normal University · 3The Hong Kong University of Science and Technology +2
CRAFT: Counterfactual Credit Assignment from Free Sibling Rollouts for Self-Distilled Agentic Reinforcement Learning
Jun 28, 2026Zibin Meng, Kani ChenAgentic Reinforcement Learning Credit Assignment
The Hong Kong University of Science and Technology
TRIAGE: Role-Typed Credit Assignment for Agentic Reinforcement Learning
Jun 30, 2026Yuanda Xu, Zhengze Zhou, Hejian Sang +6Credit Assignment Agentic Reinforcement Learning
1LinkedIn Corporation · 2Harvard University · 3Johns Hopkins University +1

Jul 27, 2026, cs.AIJ/K move · Enter open · S save

Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness

Yang Li, Hai Liu, Dian Shao, Yu Wang+7

1The University of Hong Kong · School of Artificial Intelligence, Jiangxi Science and Technology Normal University · 3The Hong Kong University of Science and Technology+2

Agentic Workflows Agentic Optimization Cost-Aware Monte Carlo Tree Search

Open paper AskPDF arXiv

Optimizing agentic workflows, such as retrieval-augmented generation (RAG) pipelines, requires navigating a combinatorial space of discrete component choices under tight evaluation budgets. Existing approaches - heuristic search, black-box optimization, and standard tree search methods - do not explicitly exploit the compositional structure of these workflows, leading to redundant computation and inefficient budget allocation. We introduce Agent-UCT (Agent-based Cost-Aware Upper Confidence Bounds Applied to Trees), a tree search algorithm that extends UCT with a reuse-aware regularization term derived from a bipartite prefix reuse graph. Agent-UCT biases selection toward branches that leverage previously materialized configuration prefixes, reducing redundant execution while maintaining effective exploration. Our framework, RAGSpace, unifies heterogeneous RAG components from LongRAG, LightRAG, and Self-RAG into a five-dimensional configuration space, enabling systematic cross-framework recombination. WTB (Workflow Test Bench) provides deterministic replay, content-addressable caching, and transactional consistency, ensuring that intermediate states are materialized once and reused across the search. Experiments on HotpotQA and UltraDomain demonstrate that Agent-UCT identifies configurations with the highest out-of-sample performance among the evaluated fixed framework presets. Under full-pool evaluation, bipartite prefix reuse reduces logical search cost by 73.6% relative to the no-prefix-sharing cost upper bound. Compared with full-pool evaluation, sampling-based evaluation further achieves a 4.2x wall-clock speedup. Agent-UCT, RAGSpace, and WTB together provide a unified framework for cost-aware, reproducible, and compositionally efficient agentic workflow optimization.

Abstract

Explore similar work

Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness

CRAFT: Counterfactual Credit Assignment from Free Sibling Rollouts for Self-Distilled Agentic Reinforcement Learning

TRIAGE: Role-Typed Credit Assignment for Agentic Reinforcement Learning