acceptodds
Under review as a conference paper at ICLR 2027

TreePPO: Learning from Trees and Exploring with Critics for Multi-Turn LLM Agents

Abstract

Multi-turn LLM agents typically make sequential decisions over long interaction trajectories, with reward signals often available only upon task completion. Existing reinforcement learning (RL) methods largely rely on these sparse terminal rewards, making it difficult to distinguish the contributions of intermediate actions to final task success. Although a critic can mitigate this limitation by estimating state values learning, accurate values for intermediate states remains challenging when the critic is trained primarily on sparse terminal rewards. To address this challenge, we propose TreePPO, a tree-search-based actor-critic RL framework that establishes a bidirectional feedback loop between rollout exploration and critic learning for continual improvement. TreePPO aggregates rollouts with shared action prefixes to provide fine-grained value supervision, while the learned critic guides adaptive rollout allocation toward tasks with greater exploration potential. Specifically, TreePPO organizes trajectories sharing ordered action prefixes into an Action-Prefix Value Tree (APVT). By aggregating terminal rewards from different continuations of each shared prefix, the APVT provides empirical value targets for intermediate states, enabling finer-grained critic learning. APVT provides supervision for critic warm-up, while subsequent on-policy rollouts continually expand the state space covered by APVT. We further use the critic's estimates of task difficulty to adaptively allocate the rollout budget, assigning more samples to moderately difficult tasks that offer greater exploration value. Extensive experiments across Multi-hop QA, ALFWorld, and WebShop show that TreePPO achieves the best overall performance among the evaluated methods with both Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct actors. With Qwen2.5-7B-Instruct, TreePPO achieves an average exact match (EM) of 36.60% across four Multi-hop QA benchmarks and an ALFWorld success rate of 86.07%, exceeding the strongest baselines in these two settings by 2.15 and 5.97 percentage points, respectively.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Tree search, Actor-Critic, Reinforcement Learning, Agent

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_LtNrOpenReview ↗
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
  1. 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.

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

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

  2. 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
AuthorsOpenReview ↗

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.

W1 & Q1: Differences from VinePPO and TRACE, and experimental comparison.

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:

Source of value estimatesRole of the value functionExtra sampling
VinePPOMC continuations from each intermediate stateReplaces the learned criticO(T·K) per trajectory
TRACEAn added prefix-value predictorBudget allocation onlyNone
TreePPOReturns pooled over shared action prefixes, across iterationsPer-turn baseline + budget allocationNone

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):

MethodHotpotQA2WikiMuSiQueBamboogleAvg.
VinePPO-style (K=1)35.7036.3511.9028.8028.19
VinePPO-style (K=2, ~2× budget)37.4035.9014.2026.4028.48
TRACE-style34.5737.1711.2527.2027.55
TreePPO38.7037.1014.2033.6030.90

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.

AuthorsOpenReview ↗

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 inputSupervision targetMSE ↓Pearson ↑
Full historySingle-trajectory return0.13680.1819
Full historyAggregated return0.06730.7192
Action prefixSingle-trajectory return0.11250.5699
Action prefixAggregated return0.06670.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 targetHotpotQA2WikiMuSiQueBamboogleAvg.
Single-trajectory return (α=1)36.8036.0013.5030.4029.18
Aggregated return (α=0.8, full TreePPO)38.7037.1014.2033.6030.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 matchingSemantic matching
Pairwise mean squared difference among histories sharing a prefix (MC noise removed)0.026600.06572
Error of the aggregated target against MC640.047540.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.

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

TreePPO improves multi-turn LLM agent training by combining tree-structured rollouts with a critic trained on outcomes pooled across shared action prefixes. The critic then helps allocate additional rollouts to moderately difficult tasks, connecting value learning with exploration. Experiments with Qwen2.5 models show improvements on multi-hop QA, ALFWorld, and WebShop.

Critical strengths

Thank you so much for submitting your paper. I appreciated the substantial implementation and evaluation details. Below are the main strengths from my point of view.

  • Well-motivated connection between critic learning and exploration: I particularly liked how you connect two related problems: learning useful intermediate values from sparse terminal rewards and deciding where to spend additional rollout budget. APVT allows the critic to learn from multiple outcomes associated with a shared action prefix, while the critic subsequently directs more sampling toward moderately difficult tasks. This is a coherent approach, and the reuse of outcomes across training iterations makes the contribution more substantial than simply adding branching to PPO.
  • Meaningful results supported by direct critic evaluation: The experiments provide useful evidence across both information-seeking and interactive tasks, with two actor sizes. The ALFWorld improvements are particularly convincing in magnitude: TreePPO achieves 83.33% and 86.07%, compared with 75.87% and 80.10% for the strongest evaluated baselines at the respective sizes. I also appreciated the evaluation against independently sampled continuation outcomes. Checking critic predictions against these estimates is more informative than relying only on training loss, especially when the competing critics use different supervision targets.
Critical weaknesses

Despite the aforementioned strengths, there are two weaknesses that limit how confidently I can attribute the improvements to the proposed mechanisms.

  • The ablations do not sufficiently isolate the benefit of APVT aggregation: The largest change in Table 2 is between independent rollouts with APVT and Turn-PPO, where average QA EM falls from 29.85 to 27.125. However, Appendix C.3 explains that this comparison also changes the training schedule: the APVT configuration warms up the critic while holding the actor fixed, whereas Turn-PPO updates both immediately. Similarly, the offline critic comparison changes the input representation, target construction, additional terminal supervision, and number of optimization updates. These experiments support the complete critic-learning procedure, but they do not establish which modification explains its advantage. I would particularly appreciate an action-prefix critic trained on individual returns, compared with APVT under the same warm-up, supervision budget, and optimizer settings.
  • The reliability of pooling outcomes across histories and training stages needs stronger validation: APVT groups trajectories by their action prefixes while omitting observations and reasoning, and it retains outcomes collected under earlier policies. For QA, semantic matching can also merge non-identical search actions. Consequently, the pooled outcomes may correspond to histories with different prospects or to policies with different capabilities. I appreciate that the paper acknowledges these limitations and mixes pooled values with the current trajectory’s outcome. However, the fixed-policy offline evaluation averages predictions and references within semantic nodes, which can conceal errors between the underlying histories and does not test policy drift. Comparisons of current-batch versus persistent aggregation, exact versus semantic matching, and different mixing weights would help establish when this central design choice remains reliable.
Questions for authors

There are some non-critical but nevertheless important points that I would like to phrase as questions to the authors.

1) Online critic evaluation: In Appendix C.1, which actor generates the trunks and the 64 continuations used to evaluate the two frozen critics? Since value predictions depend on the continuation policy, clarifying this would help interpret the comparison. Evaluating both critics under each actor would also show whether the advantage persists across continuation policies.

2) Actor and critic reward definitions: On WebShop, the actor uses the continuous task reward while the critic is trained on binary success. Could you explain this choice and whether using the actor’s reward definition for critic supervision changes the results? I would be interested in whether this is beneficial regularization or simply an implementation choice.

3) Related Work: Could you discuss TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents? It is relevant because it also restructures training-time rollout generation through tree-style search and evaluates on WebShop. The distinction is useful: TSR focuses on search-guided trajectory construction compatible with different policy optimizers, whereas TreePPO combines persistent prefix-based critic supervision with task-level rollout allocation and randomly selected branch points. Where feasible, a comparison on WebShop with matched compute and access to feedback would help clarify their respective benefits.

I would appreciate it if you could address these points!

4 comments
AuthorsOpenReview ↗

Response to Reviewer G8WV (1/3)

Thank you for the careful review, and for your kind words about linking critic learning with exploration and about checking the critic against independently sampled continuations. Our responses follow.

W1: The isolated contribution of APVT aggregation.

Response: As you suggested, we redid this comparison so that only one factor changes, both offline and online.

Offline comparison. The critic input is fixed to the action prefix. Both groups use the same data split, initialization, optimizer settings, 256 optimizer updates, and supervision positions and weights, and we removed the extra terminal samples that only the original Action+Merged configuration had. We use the 1,362 questions from Appendix C.1 (24 trajectories per question for training, 8 held out), with MC64 as the reference:

Supervision targetMSE ↓Pearson ↑
Single-trajectory return0.11250.5699
APVT aggregated return0.06670.7342

Online comparison. Average EM over the four 3B Multi-hop QA benchmarks (seed 42):

ComparisonConfigurationAvg. EM
TurnPPO: align optimization settings, then warm-upOriginal TurnPPO27.125
+ same policy update / clipping / task weighting as TreePPO27.625
+ same 25-step warm-up as TreePPO27.050
TreePPO: change only the supervision targetSingle-trajectory return (α=1)29.175
APVT aggregated return (α=0.8)30.900

For TurnPPO, aligning the optimization settings changes average EM by +0.500, and adding the warm-up (trained on TurnPPO's own single-trajectory returns) changes it by −0.575, so neither helps. The two TreePPO rows use the same warm-up (the critic is initialized from APVT node means in both), and α only sets the target during joint training. Changing the supervision target alone gives a 1.725-point gap, with all four benchmarks moving the same way. The original Figure 4(b) is not a controlled comparison. In the revision we will replace it with the offline table above and, following Appendix C.3, fix how §4.3 and the conclusion describe this step of Table 2.

With sparse terminal rewards, every intermediate state on a trajectory is regressed toward that trajectory's final return (Eq. 2). Holding everything else fixed, the comparisons above isolate the effect of pooling outcomes over shared prefixes, and it helps both offline and online.

AuthorsOpenReview ↗

Response to Reviewer G8WV (2/3)

W2: Reliability of pooling outcomes across histories and training stages.

Response: We ran the three comparisons you proposed.

Re (1): Current-batch versus persistent aggregation. Here the APVT return statistics are cleared at every PPO batch, so only the current batch is aggregated. Everything else, including α=0.8, is unchanged:

AggregationAvg. EM
Current batch only29.54
Persistent across iterations (full TreePPO)30.90

Persistent aggregation is 1.36 points higher, and all four benchmarks agree (this variant and the main-table run are not fully matched in warm-up procedure and step counting). Outcomes kept from earlier policies are biased, but overall they still carry useful information.

Re (2): Exact versus semantic matching. We measure per history instead of averaging within nodes. For histories grouped under the same prefix, we compute the pairwise mean squared difference of their MC64 success rates, after removing MC sampling noise. We also compare the error of the aggregated target against MC64 on 2,396 states that have training data under both matching rules:

Exact matchingSemantic matching
Pairwise mean squared difference among histories sharing a prefix0.026600.06572
Error of the aggregated target against MC640.047540.04439

Grouped histories do differ in value, so 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. Still, the aggregated target is no less accurate, because the extra samples that semantic matching brings in make up for those differences.

Re (3): Different mixing weights. We sweep α on a separate 1,024-question HotpotQA validation set:

α00.40.81
Validation EM (%)45.9047.5650.5943.46

α=0 uses only historical statistics and is 4.69 points below α=0.8; that is the cost of outcomes coming from older policies. α=1 uses no aggregation and is 7.13 points lower. Historical outcomes do drift, but throwing them away costs more, and the mix in Eq. (5) sits between the two.

Q1: The actor used for the continuations in Appendix C.1.

Response: The trunks and continuations come from the TreePPO actor (step-150 checkpoint), and we will state this in the appendix. Both critics were trained on the same HotpotQA questions with the same retrieval environment and prompt template, and both actors start from the same Qwen2.5-3B-Instruct, so these trunk states are within each critic's training distribution. The offline experiment in W1 controls for the actor separately. There, the training trajectories, evaluation states, and MC64 references for both critics all come from the same fixed Qwen2.5-3B-Instruct, so the two supervision schemes are compared under one policy and one set of references, and the result agrees with Figure 4(a).

AuthorsOpenReview ↗

Response to Reviewer G8WV (3/3)

Q2: Reward definitions of the actor and critic in WebShop.

Response: It is an implementation choice, and we do not claim it acts as regularization. The critic is also used for budget allocation in §3.4, and the rule that medium-difficulty tasks succeed about 50% of the time only makes sense on a success-probability scale. So in all three settings the critic regresses toward task success (Appendix A.2). In Multi-hop QA and ALFWorld this matches the actor's reward. Only WebShop gives partial credit, which is where the mismatch you noticed comes from.

What this mismatch does can be seen from how the advantage is computed. With γ=λ_A=1, A^t=R(τ)−Vˉk(xt)\hat A_t = R(\tau) - \bar V_k(x_t), where R(τ)R(\tau) is the actor's continuous reward and Vˉk\bar V_k is the pre-update critic's prediction for the prefix. The targets in Eq. (5) only train the next iteration's critic and do not enter the current advantages (§3.3). Since Vˉk\bar V_k is fixed before sampling and only sees the prefix, two trajectories on the same prefix differ in advantage by exactly the difference in their continuous rewards, so none of the information in the actor's reward is lost. Vˉk\bar V_k also does not depend on the current action or on how this trajectory turns out, so as a baseline it adds no bias to the policy gradient. Supervising the critic with continuous scores would mainly bring the baseline closer to the expected return, which changes how much variance it removes. We will describe this scaling rule in Appendix A.2.

Q3: Relation to TSR.

Response: Thank you for pointing us to TSR; we enjoyed reading it. TSR brings search from test-time scaling into training-time rollout generation, which gives multi-turn agent RL a way to improve that complements work on the optimizer. It targets the same problem we do: with only terminal rewards, a single trajectory says little about its intermediate decisions, and both papers address this through how rollouts are generated during training. TSR turns rollout generation into a search. A per-turn process scorer rates each prefix's progress, the top-B prefixes by cumulative score are kept and expanded, and the resulting trajectories go to the policy optimizer. Since it is decoupled from the optimizer, it can be paired with different methods, which makes it easy to reuse. The gap with and without the scorer in its Appendix Table 13 (85.3 vs. 75.9) also shows how much process signals are worth on WebShop.

The two methods focus on different things. TSR improves the trajectories that enter the policy update, and suits tasks where a per-turn progress measure can be built. We try to get more supervision out of the same trajectories: we pool all outcomes over shared action prefixes to train the critic, pick branch points at random, and need no scoring function. On a compute-matched comparison: TSR has no public code, its WebShop results depend on a scorer hand-designed for that environment, and it uses the webshop-minimal variant with a different sampling budget. A reproduction would be hard to attribute to the original method, so we do not include one. We will add a discussion of TSR to the related work.

Dear authors,

thank you so much for the detailed reply. I will keep my already positive score!

Thanks again!

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

Multi-turn LLM agents usually get a reward only when a task ends, so it is hard to tell which intermediate actions helped. Critic-free methods give every turn the same credit, and a critic trained on single trajectory outcomes learns noisy values.

TreePPO is a PPO-style actor-critic method with three parts. It samples a few full trajectories per task and then branches new continuations from points along them, so many rollouts share their early actions. It records outcomes in an Action-Prefix Value Tree, keyed by the sequence of actions taken so far, and trains the critic toward the average outcome at each shared prefix, accumulated across training iterations; the critic sees only the task and the actions taken. Finally, it uses the critic's predictions to rank tasks by difficulty and gives the middle third twice as many branches.

With Qwen2.5-3B and 7B actors, TreePPO beats PPO, GRPO, Tree-GRPO and Turn-PPO at matched trajectory counts on four multi-hop QA benchmarks, ALFWorld and WebShop, at both sizes, with the largest margins on ALFWorld. An ablation attributes most of the QA gain to the critic-learning step, and the critic tracks Monte Carlo value estimates much better than Turn-PPO's.

Critical strengths

S1. Consistent gains under a comparison that, if anything, favors the baselines. TreePPO beats all four directly comparable baselines on every QA benchmark at both model sizes, and on ALFWorld and WebShop at both sizes. The setup leans against it: in QA, Turn-PPO's six independent rollouts cost more tokens than TreePPO's tree (about four rollouts' worth, A.3), the critic warm-up counts against TreePPO's budget, and GRPO and Tree-GRPO are reported on QA at their best checkpoint, before their late collapse (Figure 6). The ALFWorld margins (+7.46 and +5.97) are well beyond evaluation noise, about 2.3-2.6 standard errors.

S2. The critic is tested against an independent value estimate, not just its own training loss. Figure 4 scores both critics against values estimated from 64 fresh continuations per state. TreePPO's critic correlates far better with these values than Turn-PPO's (Pearson 0.6133 vs 0.2201) and is better calibrated (expected calibration error 0.0390 vs 0.1232). The weak Turn-PPO critic itself supports the paper's motivation. Figure 3 also shows the difficulty grouping works: the medium group succeeds about half the time (50.6% and 50.8%).

Critical weaknesses

W1. The paper does not show which component produces the gain, and the main text overstates what the ablation proves.

The ablation step credited to the value tree (Table 2, 29.85 down to 27.13) is in fact a comparison with Turn-PPO: the last row matches Table 1's Turn-PPO row exactly, and Appendix C.3 confirms it. That one step accounts for 2.72 of the 3.78-point gain and changes at least five things at once: what the critic sees, the critic warm-up, the critic targets, the policy update and its clip range, and the per-task weighting. C.3 itself says this "compares complete critic-learning procedures, not return aggregation in isolation", yet Section 4.3 and the Conclusion present it as evidence for the value tree. A simple control is missing. When the critic sees only the action prefix, ordinary regression on each trajectory's own outcome already learns the average outcome at that prefix; Figure 1's own example gives 0.75 either way. Online, the pooled average gets a weight of only 0.2 in the target. Training TreePPO with each trajectory's own outcome as the target (alpha = 1) would show what pooling adds. The allocation component has the same gap: it rests on one run with a 0.82-point gain, compared only with random allocation (Q3).

W2. The statistical support and the baselines are weaker than the claims need.

The QA results report no seeds or variance, and ALFWorld and WebShop give three-seed means without spread. Evaluation noise alone is about 1.1 points on the QA average, so the two smaller ablation steps (0.82 and 0.23) and the WebShop gains (1.57 and 0.80) are within noise. The reproduced Tree-GRPO, whose sampling scheme TreePPO builds on, scores below GRPO in five of six settings, by up to 13.93 points, although the paper presents Tree-GRPO as an improvement on GRPO. The closest prior methods are cited but not compared: GiGPO, which groups outcomes over repeated states without a critic, and VinePPO, TRACE and ATPO, which build value estimates or rollout allocation from extra continuations or tree returns.

Questions for authors

Q1. Isolating the value tree. On 3B QA, can you run TreePPO with each trajectory's own outcome as the critic target (alpha = 1), and Turn-PPO with TreePPO's policy update, clip range, task weighting and format gate? A sweep over alpha (for example 1, 0.8 and 0.5) would show how much the pooled average matters. Does Table 2's row C use the mixed targets? Appendix C.3 says so only for rows A and B.

Q2. Seeds. Can you report the mean and standard deviation over at least three seeds for TreePPO, Turn-PPO and the Table 2 variants on 3B QA, and the spread of the ALFWorld and WebShop means?

Q3. Allocation baseline. The trunk rollouts' outcomes are known before branching. How does critic-guided allocation compare with grouping tasks by trunk success, or by each task's past success rate?

Q4. Tree-GRPO (clarification). What explains the reproduced Tree-GRPO's gap to GRPO? A GiGPO run on ALFWorld would also test outcome pooling with and without a critic.

Minor suggestions (do not affect the score).

Align Section 4.3 and the Conclusion with Appendix C.3, and label Table 2's last row "Turn-PPO".

5 comments
AuthorsOpenReview ↗

Response to Reviewer TNSw (1/3)

Thank you for the careful review. We especially appreciate that you checked each step of Table 2 and the statistics behind our results. Our responses follow.

W1 & Q1: Attribution of the value-tree step in Table 2.

Response: We reran these comparisons so that each one changes a single factor. Our answers to your specific questions are below.

Re (1): TurnPPO under aligned settings. We gave TurnPPO the same policy update, clipping range, and task weighting as TreePPO (the format gate was already the same), and then added the same 25-step fixed-actor warm-up. The warm-up uses no APVT statistics and counts toward the same step budget. Average EM over the four 3B Multi-hop QA benchmarks:

ConfigurationAvg. EM
Original TurnPPO27.125
TurnPPO + aligned policy update / clipping / task weighting27.625
TurnPPO + aligned settings + 25-step warm-up27.050
Independent rollouts + APVT (the corresponding Table 2 configuration)29.850

Neither the aligned settings nor the warm-up moves the result by more than the evaluation noise (about ±1.1), while adding APVT gives +2.80. The warm-up only helps when there are aggregated statistics to initialize from.

Re (2): α=1 and the α sweep. You pointed out that with action-prefix inputs, plain regression on each trajectory's own outcome already converges toward the prefix mean, and suggested α=1 to test what pooling adds. With α=1 and everything else unchanged, including the warm-up, full TreePPO drops from 30.90 to 29.18 macro-average EM, and all four benchmarks go down (same evaluation sets, seed 42). Sweeping α on a separate 1,024-question HotpotQA validation set gives:

α00.40.81
Validation EM (%)45.9047.5650.5943.46

α=1 is 7.13 points below α=0.8. The pooled mean only has a weight of 0.2, but it is what makes the targets of different trajectories at the same node differ, and that is what Eq. (2) is missing. Figure 1 shows aggregation within a single iteration only; accumulation across iterations is in Figure 2. We will say this in the Figure 1 caption.

Re (3): Does the "independent rollouts + APVT" configuration in Table 2 use the mixed target? Yes, the same 0.8/0.2 mixed target as full TreePPO and the random-allocation configuration. We will add this to Appendix C.3, label the last row of Table 2 as TurnPPO, and bring §4.3 and the conclusion in line with C.3.

Taken together: with sparse terminal rewards, every intermediate state on a trajectory is regressed toward the same terminal return (Eq. 2), so the critic cannot tell apart decisions of different value on that trajectory. Pooling outcomes at shared action prefixes gives each intermediate decision several outcomes to learn from. That is where the gain comes from; aligning the policy settings or adding the warm-up does not provide it.

AuthorsOpenReview ↗

Response to Reviewer TNSw (2/3)

W2 & Q2: Multi-seed results and spread.

Response:

Re (1): Multi-seed results on 3B Multi-hop QA. The Multi-hop QA numbers in the paper come from a single run (seed 42). We have now run three seeds (42, 1234, 7), the same for every method:

MethodHotpotQA2WikiMuSiQueBamboogleAvg.
TurnPPO34.97 ± 0.4733.53 ± 0.9612.87 ± 2.1829.33 ± 1.6727.68 ± 0.83
TreePPO39.55 ± 0.7638.07 ± 1.0614.73 ± 0.7633.33 ± 2.0131.42 ± 0.47

TreePPO is 3.75 points higher on average. The standard error of the difference is 0.55 (Welch t ≈ 6.8), and TreePPO beats TurnPPO on every seed.

Re (2): Spread on ALFWorld and WebShop. The main-table numbers are three-seed averages. Their standard deviations are below (success rate %, n=3):

ModelMethodALFWorldWebShop
3BPPO30.85 ± 3.0764.53 ± 2.24
3BGRPO75.87 ± 5.1166.87 ± 2.24
3BTree-GRPO61.94 ± 8.8560.20 ± 2.87
3BTurnPPO74.38 ± 3.3675.80 ± 1.91
3BTreePPO83.33 ± 0.7077.37 ± 1.60
7BPPO56.22 ± 2.5469.50 ± 2.55
7BGRPO79.10 ± 1.2278.57 ± 2.23
7BTree-GRPO66.67 ± 1.2770.73 ± 2.55
7BTurnPPO80.10 ± 6.1479.73 ± 2.23
7BTreePPO86.07 ± 2.4680.53 ± 1.59

On every seed, TreePPO is at least as good as each baseline. Since the methods share seeds, we also give the per-seed paired difference between TreePPO and TurnPPO (mean ± std): ALFWorld +8.96 ± 3.42 (3B) and +5.97 ± 4.90 (7B); WebShop +1.57 ± 0.39 (3B) and +0.80 ± 0.79 (7B). On 3B WebShop, for example, the two methods have standard deviations of ±1.9 and ±1.6, but the paired difference only varies by ±0.39. Most of the run-to-run variation is shared by both methods.

W1 & Q3: Critic-guided allocation versus grouping by success rate.

Response: The main difference is where the signal comes from. In actor–critic training such as PPO, we train a critic anyway, and its prediction is the value of a state under the current policy, which already tells us how hard a task is. We reuse that prediction to allocate the budget, at no extra sampling cost. The trajectories this produces go back into the APVT and update the critic's targets, so value learning and data collection feed each other.

Success rates need extra design before they can be used this way. With only two trunks per task, the trunk success rate is 0, 0.5, or 1. During training, 82.16% of task samples land on 0 or 1 and only 17.84% on 0.5, but our budget rule needs a third of the tasks in the medium group. We would need more trunks, or a tie-breaking rule for the many tasks with equal scores. Historical success rates require each task to come up again and again, and they mix outcomes from policies at different points in training. The critic averages its predictions over all action-prefix positions on the trunks and gives a continuous difficulty score from the same rollouts; the same prediction also serves as the baseline for per-turn advantages (Eq. 8). In Figure 3(c,d), when tasks are split into three equal groups by the critic's prediction, the medium group's actual success rate is 50.6% and 50.8%, so the signal is well calibrated.

AuthorsOpenReview ↗

Response to Reviewer TNSw (3/3)

W2 & Q4: Tree-GRPO's performance and comparison with related methods.

Response:

Re (1): Why Tree-GRPO falls below GRPO. We think the main reason is instability late in training. Tree-GRPO is a group-relative method, and Search-R1 reports that such methods on Instruct models "lead to reward collapse after training for many steps, whereas PPO remains stable" (§5.1, Appendix F). For the same reason, BranPO starts all its RL baselines, Tree-GRPO included, from an SFT checkpoint (§4, Appendix A.2). We train directly from Qwen2.5-Instruct, and the late drops of GRPO and Tree-GRPO in Appendix Figure 6 fit this picture. One possible explanation for the instability is groups with no return variation: in a diagnostic run, 65.98% of internal branch points had the same return for all descendants. The group-relative advantage there is zero, so the update depends on the few groups that do differ. With γ=λ_A=1, TreePPO computes each trajectory's advantage as R(τ)−Vˉk(xt)R(\tau)-\bar V_k(x_t), where Vˉk\bar V_k is the pre-update critic, so it does not have this problem, and it shows no late drop through 150 steps.

Re (2): Comparison with related methods. First, how these methods differ from ours. GiGPO groups repeated environment states to build step-level advantages without a critic, so it relies on states recurring within a group; our critic learns from returns pooled over shared action prefixes and does not need states to recur. VinePPO drops the learned critic and estimates each intermediate state's value from the mean return of extra continuations, so its extra sampling grows with the number of turns; we add no sampling and reuse returns from existing trajectories. TRACE adds a prefix-value predictor on top of group-relative RL that is only used to allocate the budget and does not enter the advantage; our critic provides both the per-turn baseline and the allocation signal. ATPO allocates rollouts with tree search and uncertainty-based pruning, on medical dialogue tasks with 128 rollouts per task; we use 6–8.

We reproduced GiGPO under the same protocol as ours (3B ALFWorld, about 1,000 training tasks, 134 unseen test tasks, 8 rollouts per task, the same three seeds). It reaches 77.85 versus 83.33 for TreePPO, a 5.48-point gap (about 5.5 standard errors of the difference). The GiGPO paper has no 3B result, uses more training tasks, and evaluates on seen tasks by default, so we do not compare with its published numbers. VinePPO and TRACE do not report our benchmarks, and TRACE has no public code, so we implemented their core mechanisms on Multi-hop QA with all other settings matching TreePPO:

MethodHotpotQA2WikiMuSiQueBamboogleAvg.
VinePPO-style (K=1)35.7036.3511.9028.8028.19
VinePPO-style (K=2, ~2× budget)37.4035.9014.2026.4028.48
TRACE-style34.5737.1711.2527.2027.55
TreePPO38.7037.1014.2033.6030.90

The VinePPO-style variant samples one continuation per decision position, which matches our budget of about 6 rollouts per question (the original K=9 would need 37). At K=2, about twice our budget, its average only goes from 28.19 to 28.48, still 2.42 points below TreePPO. ATPO's tasks and budget are too far from ours to adapt it, so we will discuss it in the related work instead.

In multi-turn interaction, trajectories of the same question, including ones collected at different stages of training, share many intermediate states. TreePPO treats these as shared action prefixes and pools the final outcomes on them to train the critic, so each intermediate decision gets several outcomes as evidence without extra sampling. The same critic then serves as the per-turn baseline and guides the budget, and new trajectories feed back into the prefix statistics. This is the design the comparisons above are testing.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.