acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, LLM, Agentic Workflows, PPO, Tree Search, Counterfactual Credit Assignment, Retrieval-Augmented Generation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_NNVUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies credit assignment for agentic RL. The authors propose ASCT, which runs training-time tree search over alternative legal actions from recoverable prefixes, estimates local action values, and centers them with the frozen actor's probabilities to credit PPO updates on actor-sampled trajectories. Uniform, UCT, and AgentUCT instantiate the search. On HotpotQA RAG with Qwen3-4B, all three evaluators improve held-out utility over trajectory-return PPO and VinePPO, and ASCT-AgentUCT reaches 0.6187 versus 0.5939 for VinePPO.

Critical strengths
  1. Credit assignment for local decisions in multi-step agentic workflows is an important problem, and using search only at training time while deploying the actor alone is a reasonable design.
  2. The paper reports auxiliary token cost, difficulty splits, transfer results, and an ActorRollout control, which provides useful diagnostics on the proposed credit estimator.
Critical weaknesses
  1. This paper seems largely written by an LLM, which makes it really hard for humans to follow the motivation and logic across sentences. Thus, I think the manuscript needs substantial rewriting to meet the bar of publication at ICLR.
  2. The novelty seems limited. I cannot identify a principled rationale in this workflow, which reads like a combination of several established agentic tree search methods [1-6]. I think the authors need a clear discussion and comparison to justify the novelty over them.

[1] VinePPO: Refining Credit Assignment in RL Training of LLMs

[2] Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models

[3] Tree Search for LLM Agent Reinforcement Learning

[4] Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning

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

[6] TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning

Questions for authors
  1. Can the authors add a clear discussion of the novelty over [1-6], especially [5] (whose search rules are directly inherited) and [6]?
  2. Uniform achieves the highest F1, while AgentUCT mainly wins on execution cost. Does this mean the credit interface, rather than the search allocator, is the main source of gain?
  3. The AT2PO adaptation performs close to PPO without method-specific tuning. Is this comparison fair, and if so, why is learning from branch collections not helpful here?
3 comments

Thank you for the constructive feedback.

1. Novelty, relationship to prior work, and writing

There are several approaches to multi-step exploration and credit assignment in agentic RL:

  • VinePPO uses Actor/LLM-generated Monte Carlo continuations to estimate state values.
  • BPO/Tree-GRPO branches from Actor/LLM trajectories at high-uncertainty decision points and uses the resulting trajectories for policy optimization.
  • ASCT takes a different approach: decoupling Actor/LLM trajectory exploration from tree-search evaluation.

In ASCT, the Actor generates trajectories for PPO updates, while a separate tree-search evaluator estimates counterfactual action values. This separates two interacting problems: Policy Optimization and Search-based Value Evaluation.

Here, tree-search selection and budget allocation need not follow the LLM Actor's policy. Instead, strategies such as Uniform, UCT, and AgentUCT can guide tree expansion and construct the Q-value table used for credit assignment. This allows evaluation to cover alternatives the actor rarely selects while keeping policy-update trajectories actor-sampled. Even a simple Monte Carlo evaluator can still benefit from this separation.

Regarding [5], [6], and [2], AgentUCT provides a search and allocation strategy, like UCT or Uniform. TRACE focuses on fine-tuning a Qwen3-0.6B predictor to allocate additional searches during GRPO training. LATS is an agent framework without training LLMs or updating LLMs’ parameters. These methods address different problems, and we thank the reviewer for highlighting the need to clarify this distinction.

We have rewritten the Abstract and Introduction in the latest version to clarify our novelty and relationship to prior work. We hope this addresses the reviewer's concerns and welcome any further questions.

2. Uniform versus AgentUCT

We agree with the reviewer's observation. Uniform achieves the highest mean F1 (0.7316), while AgentUCT achieves the highest mean utility (0.6187) with lower evaluation cost. Their performance differences are relatively small.

This is precisely one of the questions ASCT investigates: different search evaluators can improve the final policy through the same credit interface, while their allocation strategies lead to different trade-offs between policy quality and computational cost.

We do not claim that AgentUCT consistently outperforms Uniform, and ASCT does not depend on a particular search allocation algorithm.

In an additional full-policy control experiment, Root MC balances root actions and samples later actions uniformly, without internal tree visit allocation. It achieves utility of 0.6159±0.01250.6159 \pm 0.0125, compared with ActorRollout’s 0.5975±0.01280.5975 \pm 0.0128, and outperforms ActorRollout in all three seeds. These results show that a simple evaluator can provide useful training credit without following the actor’s continuation policy.

3. AT²PO comparison

Our AT²PO implementation uses the same workflow and experimental setup as the other methods, without additional SFT or method-specific tuning, to maintain comparable experimental conditions.

We cannot determine exactly why its performance is close to PPO. Method-specific tuning or the absence of additional SFT could affect the results, but we have not evaluated these possibilities.

Importantly, we do not claim that branch-based policy optimization is generally ineffective.

We have explicitly clarified the absence of additional SFT as an experimental control and the scope of our conclusions in the revised manuscript to avoid misunderstanding.

Thank you again for the suggestions. We hope these clarifications address the main concerns, and we welcome any further questions.

Thanks for the response, but the two critical weaknesses are still not addressed. The writing is still poor: many sentences and paragraphs lack logical connection, and there are still stray fragments like code paths left in the text, making the current manuscript far below publication standard. Not just the abstract and introduction, the whole paper needs a rewrite. Partly because of the writing, I still find it hard to see the principled rationale and novelty behind this workflow.

Thank you for your response and further feedback.

  1. Code paths: The referenced paths are intentional implementation references in Appendix A.3, included for reproducibility. This is a common practice in ML papers, including previously accepted ICLR papers.

  2. AI-assisted writing: We have explicitly disclosed our use of AI assistance in accordance with ICLR 2027 policy and take full responsibility for the manuscript.

We appreciate your time and consideration.

Reviewer_qpsAOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ASCT, which uses auxiliary counterfactual search to estimate action values at actor-visited workflow states. These values are centered by the frozen actor's probabilities and supply credit for PPO updates on actor-sampled trajectories. Uniform, UCT, and cost-aware evaluators are tested in a RAG workflow, while deployment uses only the trained actor.

Critical strengths
  1. The separation of actor sampling from auxiliary action evaluation is clearly specified, and the learned policy requires no counterfactual search at deployment.

  2. The matched three-seed experiments show higher held-out utility than VinePPO, with useful continuation controls and detailed auxiliary-token accounting.

Critical weaknesses
  1. The estimated action values depend on search continuations rather than the actor's own continuation policy. It remains unclear how reliable the resulting credit is when the actor cannot reproduce the favorable suffixes found by search.

  2. Most mechanistic controls use small fixed-state cohorts, and the ActorRollout control changes both allocation and continuation sampling. Their separate contributions to full-policy gains remain only partially isolated.

  3. The main setting uses supplied candidate passages and a small, fixed component library. Applicability to open-ended search or much larger legal-action spaces remains unvalidated.

Questions for authors

See the Weaknesses above.

1 comment

Thank you for your thoughtful comments. To address your concerns, we added a full-policy training experiment with Root MC to fill the gap between ActorRollout and ASCT-Uniform. Root MC uses balanced root allocation and uniform continuation sampling. This added control lets us directly compare continuation policies under the same root allocation and assess whether the policy gains require internal tree allocation. All three methods use 12 terminal evaluations per visited state, the same actor-centered credit and PPO settings, three training seeds, and 400 test questions.

EvaluatorTest utility, mean ± SDAuxiliary Qwen tokens
ActorRollout0.5975 ± 0.0128495.2M
Root MC0.6159 ± 0.0125195.4M
ASCT-Uniform0.6146 ± 0.0191197.1M

1. Comparing continuation policies under the same allocation rule

ActorRollout and Root MC share the same root-balanced allocation rule, with no internal tree visit allocation. They differ in the continuation policy: ActorRollout samples subsequent actions from the frozen actor, whereas Root MC samples uniformly from the legal actions.

Root MC achieves higher test utility in all three seeds while using fewer auxiliary tokens. At test time, the trained actor makes its own decisions without auxiliary search. This directly shows that, in this setting, changing the evaluation continuation policy can improve the actor itself. It supports decoupling evaluation continuations from the actor's current policy: an alternative continuation policy can provide more useful training credit.

2. Clarifying the contribution of internal tree allocation

The Root MC–ASCT-Uniform comparison further clarifies the contribution. Root MC has no internal tree visit allocation, whereas ASCT-Uniform uses internal visit counts to distribute trials. Their mean utilities are close, and the paired differences change sign across seeds.

Taken together, these comparisons show that separating evaluation continuations from the actor's policy can already be useful with a simple evaluator. The gains do not require a particular tree-search allocation strategy. These results support ASCT's contribution as a training framework that is independent of any particular search allocation strategy.

Your comments prompted this additional control, helping us better distinguish the sources of improvement and present the contributions more clearly in the revised Discussion and Appendix F.

3. Limitations and future work

Our experiments focus on a finite component library. We also examine description-guided selection of a newly introduced component in a controlled setting (Section 5.5, Table 6) and cross-dataset transfer to 2WikiMultihopQA and MuSiQue (Section 5.4, Table 5).

We agree that performance in larger action spaces, open-domain tasks, and dynamic environments still requires further experiments. We state the current scope explicitly in the paper's Limitations and regard broader evaluation in these environments as an important next step.

Thank you again for your professional and instructive feedback, as well as your recognition and encouragement of this work. We hope the new experiments and explanations address your main concerns.

Reviewer_VVHmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ASCT for credit assignment in agentic retrieval-augmented generation. At states visited by the policy, ASCT evaluates alternative actions through multi-step search, centers their estimated values using the frozen policy’s action probabilities, and uses the resulting advantages to update the policy with PPO. At inference, the trained policy acts directly. On HotpotQA, all three ASCT variants improve mean held-out utility over PPO and workflow-adapted VinePPO.

Critical strengths
  1. The method cleanly separates search from behavior sampling. Search supplies action-level credit, while PPO updates use decisions sampled from the policy. Figure 1 makes this distinction easy to follow.

  2. The HotpotQA gains are consistent across the three reported seeds for AgentUCT versus VinePPO. The mean utility gain of 0.0248 reflects both higher answer F1 and lower workflow execution cost.

Critical weaknesses
  1. The effect of within-tree trial allocation on the learned policy remains unclear. Table 7 changes both allocation and continuation sampling. Appendix E shows improved repeatability at the training budget on fixed states, leaving open how much that improvement matters for final policy utility.

  2. The token breakdown in Table 3 is informative. The reported 50.3% reduction in auxiliary Qwen tokens comes mainly from eliminating actor scoring on continuations, while the environment-token count increases. The magnitude of any end-to-end training speedup remains uncertain.

Questions for authors
  1. The token breakdown in Table 3 is informative. The reported 50.3% reduction in auxiliary Qwen tokens comes mainly from eliminating actor scoring on continuations, while the environment-token count increases. The magnitude of any end-to-end training speedup remains uncertain.

  2. How does the wall-clock time of ASCT-AgentUCT compare with that of workflow-adapted VinePPO for a representative training iteration on the same hardware?

2 comments

Thank you for your constructive comments. We address the two types of auxiliary computation, add the same-hardware timing comparison you suggested, and provide a new control to distinguish continuation sampling from tree allocation.

1. Accounting for both parts of auxiliary evaluation

To obtain training feedback, actor-guided methods use LLM computation both to select auxiliary actions and to execute them. ASCT selects auxiliary actions using explicit rules, eliminating the LLM calls needed for action selection. This can support more exploration within the same budget or reduce the cost of auxiliary evaluation. For completeness, we report environment tokens alongside actor-scoring tokens to show where computation is spent. We evaluate this trade-off using overall token counts, final policy quality, and same-hardware timing measurements.

Auxiliary Qwen tokensVinePPOASCT-AgentUCT
Environment execution137.1M193.1M
Actor continuation scoring251.3M0
Total388.4M193.1M

The auxiliary Qwen total decreases by 50.3%. Including main-trajectory scoring and optimizer forwards, the recorded Qwen total decreases by 39.1%. Including E5 and BGE-M3, total auxiliary tokens decrease from 389.2M to 194.0M (50.1%).

WTB provides a separate saving by reusing executed workflow prefixes; both methods already use WTB under the same eight-A800 training protocol.

2. Token savings and measured training time

Token counts and elapsed time measure different aspects of efficiency. To answer the timing question directly, we added a dedicated benchmark on the same eight A800 GPUs, with identical actor, workflow, worker settings, B=12 and PPO configuration. Both methods additionally use the same exact generation reuse in this benchmark, which avoids repeating identical deterministic generation requests.

The benchmark uses 32 training questions and two policy iterations. Times below run from collection start to update completion, including PPO and model offload/restore:

SeedIterationASCT-AgentUCTVinePPO
111172.47 s179.69 s
112169.25 s177.39 s
231170.60 s183.91 s
232167.96 s177.71 s

ASCT takes 4.02–7.24% less time per iteration. Complete-process times, including startup, both iterations, validation/test and checkpointing, are 420.12 vs. 439.62 seconds at seed 11 and 418.06 vs. 445.68 seconds at seed 23: reductions of 4.44% and 6.20%. Appendix G reports the measurement boundaries and both reuse conditions: without generation reuse, the seed-11 process times are 561.40 vs. 502.34 seconds. All 16 recorded semantic comparisons pass.

The main experiments show higher utility and lower auxiliary token use. The matched timing benchmark shows that these savings do not come at the expense of training speed.

3. What does internal tree allocation add?

Thank you for asking how within-tree allocation affects the learned policy. We added full-policy training with Root MC, which uses balanced root allocation and uniform continuations without internal tree visit allocation. This provides the missing intermediate control between ActorRollout and ASCT-Uniform. All three use B=12, the same actor-centered credit and PPO settings, three seeds, and 400 test questions.

EvaluatorTest utility, mean ± SDAuxiliary Qwen tokens
ActorRollout0.5975 ± 0.0128495.2M
Root MC0.6159 ± 0.0125195.4M
ASCT-Uniform0.6146 ± 0.0191197.1M

Root MC and ASCT-Uniform achieve similar mean utilities, and their paired differences change sign across seeds. Root MC also improves over ActorRollout in every seed under the same root allocation rule with uniform continuations. Together, these results show that separating evaluation continuations from the actor's policy can already improve the performance without internal tree allocation. This additional control helps us distinguish the contribution of ASCT's training framework from that of the search allocation strategy. We clarify this distinction in the revised Discussion and Appendix F.

Thank you again for your suggestions on the mechanism ablations and timing measurements. They helped us clarify the contribution and report performance more completely. We hope these results address your main concerns and welcome further questions and discussion.

Reviewer_VVHmOpenReview ↗

Official Comment by Reviewer VVHm

Thank you for your response and the additional experiments. I will maintain my original rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.