- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes TreePPO, an on-policy actor–critic reinforcement learning framework for multi-turn LLM agents with sparse terminal rewards. It introduces an Action-Prefix Value Tree (APVT) that aggregates terminal rewards from trajectories sharing action prefixes to supervise critic learning, and uses the learned critic for turn-level advantage estimation and adaptive rollout allocation.
Critical strengths
-
The paper combines action-prefix-based critic learning with adaptive rollout allocation in a unified framework, and provides ablation studies and critic analyses to evaluate the effectiveness of the proposed components.
-
TreePPO consistently outperforms the evaluated baselines across Multi-hop QA, ALFWorld, and WebShop with both Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct models.
Critical weaknesses
-
The main ideas of this paper are closely related to previous studies. VinePPO proposes Monte Carlo-based value estimation using multiple continuations, while TRACE uses a learned prefix value predictor for adaptive rollout allocation. TreePPO combines these ideas within an actor–critic framework, but the additional benefits over existing approaches are not sufficiently demonstrated. In particular, neither VinePPO nor TRACE is included in the experimental comparisons, making it difficult to assess the novelty and practical contributions of the proposed method.
-
TreePPO trains a critic by aggregating terminal rewards from trajectories sharing the same action prefix. However, even when action sequences are identical, differences in observations or reasoning histories may lead to different success probabilities. The impact of this information loss is not sufficiently analyzed. Furthermore, the critic comparison changes both the input representation (full history vs. action prefix) and the supervision target (individual return vs. aggregated return) simultaneously. Therefore, it remains unclear which component contributes to the improvement in value estimation, and additional ablation studies are needed to examine the individual effects of these components.
Questions for authors
-
Could the authors compare TreePPO with TRACE and VinePPO under comparable experimental settings? In particular, comparing TreePPO with TRACE using matched rollout budgets would help clarify the benefits of the proposed critic-guided allocation. A comparison with VinePPO-based value estimation would also help evaluate the effectiveness of the learned critic.
-
Could the authors conduct ablation studies that separately examine the effects of critic input representations (full history vs. action prefix) and supervision targets (individual return vs. aggregated return)? In addition, evaluating differences in Monte Carlo success probabilities among histories sharing the same action prefix would help assess the impact of information loss on value estimation. These comparisons should use consistent training settings to better isolate the contribution of each component.
5 comments
Response to Reviewer LtNr (2/2)
W2 & Q2: Separating input representation from supervision target, and information loss from the prefix abstraction.
Response:
Re (1): Separating input representation from supervision target. We train four critics on trajectories from a fixed Qwen2.5-3B-Instruct, using the 1,362 questions from Appendix C.1 (24 trajectories per question for training, 8 held out). All four share the same data split, initialization, optimizer settings, and 256 optimizer updates, and use the same supervision positions and weights within each input type. We removed the extra terminal samples that only the original Action+Merged configuration had. Evaluation is done at each of 2,857 history positions, with MC64 as the reference:
| Critic input | Supervision target | MSE ↓ | Pearson ↑ |
|---|---|---|---|
| Full history | Single-trajectory return | 0.1368 | 0.1819 |
| Full history | Aggregated return | 0.0673 | 0.7192 |
| Action prefix | Single-trajectory return | 0.1125 | 0.5699 |
| Action prefix | Aggregated return | 0.0667 | 0.7342 |
With the input fixed, aggregated supervision clearly improves value prediction for both inputs (MSE drops by 51% and 41%), and with aggregated supervision the two inputs end up with similar MSE. So the better value estimates come mostly from the supervision target, not the input representation. We therefore see the action prefix as a state abstraction that makes shared supervision possible, and as a way to keep cost down (the critic input is capped at 1,024 tokens, versus 4,096 for the actor). We will revise the claim about representation alignment in §3.2 accordingly.
The supervision target matters in online training too. In full TreePPO we changed only the critic target to each trajectory's own return (α=1), keeping the warm-up and everything else the same (seed 42):
| Critic target | HotpotQA | 2Wiki | MuSiQue | Bamboogle | Avg. |
|---|---|---|---|---|---|
| Single-trajectory return (α=1) | 36.80 | 36.00 | 13.50 | 30.40 | 29.18 |
| Aggregated return (α=0.8, full TreePPO) | 38.70 | 37.10 | 14.20 | 33.60 | 30.90 |
Aggregated supervision raises the average by 1.72 points, and all four benchmarks go the same way.
Re (2): Differences among histories sharing an action prefix. As you suggested, we measured this directly. For full histories grouped under the same prefix, we compute the pairwise mean squared difference of their MC64 success rates, separately for prefixes with identical retrieval strings and for prefixes merged by semantic matching. We also compare the error of the aggregated target against MC64 on 2,396 states that have training data under both rules:
| Exact matching | Semantic matching | |
|---|---|---|
| Pairwise mean squared difference among histories sharing a prefix (MC noise removed) | 0.02660 | 0.06572 |
| Error of the aggregated target against MC64 | 0.04754 | 0.04439 |
After removing MC sampling noise, about 90% of the difference remains, so it is not a sampling artifact. The information loss is real, and the action prefix is a lossy abstraction. Under exact matching, the E5 retriever is deterministic and the same queries return the same passages, so the two histories see identical observations and differ only in their reasoning text. Semantic matching adds differences in observations as well. This loss does not make the targets used for value estimation less accurate, though: the extra samples that semantic matching brings in make up for the differences it introduces.
Follow-up on the Rebuttal
Thank you for the detailed responses and additional experiments. Several of my concerns have been addressed.
However, the comparison with TRACE changes both the policy optimization method and rollout allocation mechanism, while the allocation ablation shows only a modest improvement. Thus, the independent contribution of critic-guided allocation remains insufficiently established.
I will maintain my original rating.
Response to Reviewer LtNr (1/2)
Thank you for reviewing our manuscript and for your positive comments on both the integration of action-prefix critic learning and adaptive rollout allocation into a single framework and the consistent gains across the three task families. We address your comments point by point below.
Response:
Re (1): Relation to VinePPO and TRACE. Our design starts from one observation. In multi-turn interaction, trajectories of the same question, even ones collected at different stages of training, share many intermediate states (in 3B HotpotQA, the hit rate of historical prefixes rises from about 30% to 50%, Figure 5). TreePPO pools the final outcomes on these shared action prefixes to train the critic, without extra sampling, and uses the same critic as the per-turn baseline and to guide the budget. VinePPO instead drops the learned critic, which it considers unreliable for LLM reasoning, and estimates values from Monte Carlo returns of extra continuations sampled at each intermediate state. TRACE deals with the zero advantage that group-relative RL gets when all returns in a group are equal, and trains a separate prefix-value predictor that is only used to allocate the budget. TreePPO neither samples extra continuations nor adds a separate predictor, so it is not a combination of the two:
Re (2): Comparison under the same conditions. Neither paper reports our benchmarks (VinePPO works on single-turn math, and TRACE has no public code), so we implemented their core mechanisms on Multi-hop QA with the same model, data, retrieval environment, interaction limits, and evaluation protocol. As in TRACE's own experiments, the TRACE-style version is built on the Tree-GRPO codebase. It allocates trunks and continuations using predicted question and prefix success, with the same budget as ours (6 rollouts per question on average), and uses the original Qwen3-0.6B predictor for allocation only. The VinePPO-style version has no learned critic and samples one extra continuation per decision position to match our budget (the original K=9 would need 37 rollouts per question):
TreePPO is 3.35 points above the TRACE-style version, so using the critic as the baseline and letting its predictions guide allocation works better than group-relative optimization with a separate predictor. It is 2.71 points above the VinePPO-style version at the same budget, and even at about twice the budget (K=2) the VinePPO-style version only reaches 28.48.
Because intermediate states overlap so much, final outcomes can be pooled without extra sampling. Each intermediate decision gets several outcomes to learn from, and the resulting critic in turn guides data collection. This is the design the comparisons above are testing.