acceptodds
Under review as a conference paper at ICLR 2027

RegPO: Leveraging Regret-Based Feedback for Agentic Post-Training with Tree-Structured Sampling

Abstract

We introduce RegPO, a policy optimization method that uses regret-based feedback for step-level credit assignment in post-training large language model (LLM) agents. Specifically, motivated by the decomposition of regret for learning in Markov decision processes (MDPs) into action suboptimality gaps, RegPO develops sampled-search proxies for regret-based advantages at selected prefixes, leveraging tree-based sampling. These per-step regret proxies are constructed from sampled rollout subtrees by comparing each action’s estimated value with the highest estimate at the same prefix. We show that, in finite deterministic tree-structured MDPs, existing Tree-GRPO’s return-based advanatages can decrease the probability of selecting an optimal action during learning. This occurs when the action’s value under the current policy is lower than that of a suboptimal action. Experiments on these MDPs then show how the different advantage constructions affect the learning dynamics of policy optimization, e.g., which actions remain likely to be sampled during training. An ALFWorld analysis further examines how action value rankings relate to action selection, task-relevant intermediate-state reachability, and continuation execution in agentic settings. We also evaluate RegPO extensively on four agentic benchmarks spanning robotic manipulation, web interaction, browser control, and embodied reasoning. Under the benchmark-specific reporting protocol, the evaluated RegPO configurations attain the highest scores among the compared methods.

Primary area:
foundation or frontier models, including LLMs
Keywords:
credit assignment, RL, LLM, regret

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_FK3UOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes RegPO, a policy optimization method for multi-turn LM agents that focuses on step-level credit assignment. The authors argue that Tree-GRPO’s intra-tree advantage effectively compares actions at a shared prefix by their mean return if that action were taken under the current policy. That comparison can rank an action with a better achievable continuation below a better alternative, and so lower the probability of selecting it. RegPO instead estimates, at selected branching prefixes, each sampled action’s value as the best continuation found in a sampled rollout subtree. For the LM experiments, this uses a pseudo-posterior estimator that extrapolates to unsampled continuations. Comparing that value with the prefix-wise maximum gives a proxy for the action’s regret-based advantage. After centering, this term is added to the Tree-GRPO advantage.

The paper motivates the approach with a regret decomposition and a learning-dynamics analysis in a constructed “Hard-Safe” tree MDP. Experiments on Hard-Safe and random tree MDPs examine how the advantage constructions affect learning. The method is then evaluated on four agentic benchmarks: RoboTwin 2.0 (Beat Block Hammer), WebShop, MiniWoB++, and ALFWorld. RegPO achieves the highest point estimate on every reported split, with the largest margins on ALFWorld.

Critical strengths

The core motivation is clear and well argued.

I like that the authors first show how the method behaves in two controlled toy settings (Hard-Safe and random trees) before evaluating it in the environments of interest. This makes the intended mechanism easier to understand. The toy experiments are also run carefully, with many seeds and instances.

The benchmarks are diverse, including a vision-language-action manipulation task alongside text-based agent environments.

Critical weaknesses
  1. Baselines are substantially below published results. On ALFWorld with Qwen2.5-1.5B-Instruct, the GiGPO paper (Feng et al., 2025) reports about 72.8% success for GRPO and about 86% for GiGPO, with the same number of training iterations. The reproductions here reach 28.6% and 45.5%. The authors attribute the gap to a reduced episode horizon (30 vs. 50 steps) and response limit (256 vs. 512 tokens). That means the headline ALFWorld margins (+20.2 ID, +29.1 OOD) are measured in a regime where all methods are heavily handicapped, and it is unclear whether they would persist under standard settings. On WebShop, where the reproduction is closer to published numbers, RegPO (65.9) falls within the range of published GiGPO results (65.0–67.4) rather than clearly above it.

  2. Statistical evidence is thin on half the benchmarks. RoboTwin and MiniWoB++ each use a single training seed. MiniWoB++ is evaluated on 64 episodes, so the 2.1-point margin over GiGPO corresponds to roughly 1.3 episodes. It is also smaller than the reported standard deviation, which reflects only evaluation repetitions, not training variance. These results do not support a claim of improvement without additional training seeds.

  3. No ablations on the agentic benchmarks. RegPO combines several components: the pseudo-posterior estimator, a centering shift, and an additive regret term with w_reg = 1 on top of Tree-GRPO. None is ablated on the agentic tasks, so the gains cannot be attributed to regret-based feedback specifically. This matters particularly because the random-tree results show pure regret feedback underperforming Tree-GRPO at low branching factors, and the LM experiments use only two sampled actions per branching prefix. In that regime, the benefit may come from the pseudo-posterior extrapolation rather than from the regret signal itself. In addition, the regret term is only ever added to Tree-GRPO, even though GiGPO is the strongest baseline.

  4. Clarity and presentation is a major weakness: The description of the method is very dense. I strongly suggest simplifying the main-text presentation and deferring more technical details to the appendix. The caption for Figure 1 is hard to understand and seems to be missing relevant context. The last paragraph of the introduction, which discusses results, is also hard to understand and missing context. For example, what is “the benchmark-specific reporting protocol,” and what do the stated margins mean (relative to which baseline, in what units)? The conclusion, limitations, and related work are all deferred to the appendix, so the main text ends abruptly after the experiments. This is highly atypical; at minimum, the conclusion and limitations should appear in the main body.

Note that while I answered that "I have significant concerns about the paper’s soundness that do not appear easy to address.", I was between this option and option 2. I think you can make this into a strong paper by running substantially more experiments (assuming results hold up) , as the method itself is interesting and makes sense. But doing this, and also improving the clarity of the paper, seems like a tall order.

Questions for authors

Can you report results on ALFWorld under the standard GiGPO configuration (50-step horizon, 512-token responses), so the comparison can be related to published baselines?

Can you provide additional training seeds for RoboTwin and MiniWoB++?

Can you ablate the components of RegPO on at least one or two agentic benchmarks? Specifically: sampled-max vs. pseudo-posterior estimation, with vs. without centering, and a sweep over w_reg.

Does the regret component also improve GRPO or GiGPO when added to them, rather than only Tree-GRPO?

8 comments
AuthorsOpenReview ↗

Response to Reviewer FK3U (General Response)

Thank you for your detailed review and for recognizing the method's clear motivation, controlled studies and benchmark diversity. You identified substantially more experimental evidence and clearer presentation as the main requirements for making this a strong paper. We have organized the revision around these two priorities, expanding the evaluation from four to six agentic benchmarks, adding component ablations on agentic tasks, and simplifying the main-text explanation.

Please also see the updated manuscript and the revisions highlighted in color.

The main additions are:

  1. Two additional benchmarks. On Minesweeper with Qwen3-4B, RegPO reaches 59.4 ± 2.6%, versus 53.1 ± 0.8% for GiGPO, the strongest baseline. On Sokoban with Qwen2.5-1.5B, RegPO reaches 35.2 ± 0.6%, versus 27.7 ± 0.5% for Tree-GRPO, the strongest baseline (Table 1(a)). Both settings include a Tree-GRPO baseline that outperforms GRPO. These results extend the comparison to additional environments and a larger language-model backbone. The spreads summarize five evaluations of one final checkpoint per method on Minesweeper and three evaluations of one update-150 checkpoint per method on Sokoban, using 128 and 512 validation boards, respectively.
  2. Component ablations on agentic tasks (W3/Q3). We now compare predictive and observed-max estimation on ALFWorld, vary posterior concentration and regret weight on Minesweeper, and evaluate base removal and centering removal on Beat Block Hammer (BBH). The Minesweeper sweep retains the base and tests wreg=0,1,2,4w_{\rm reg}=0,1,2,4, with unit weight attaining the highest observed validation peak. On BBH, regret-only training reaches 68.9% success, and the centering-off variant reaches 65.6% success. We additionally compare RegPO with a doubled Tree-GRPO base on ALFWorld and WebShop. These studies examine the components you identified across language and manipulation tasks; the detailed replies state the scope and protocol differences of each comparison.
  3. ALFWorld with the requested episode and response limits (W1/Q1). A completed run with 50 steps per episode and 512 tokens per response, trained for 200 updates, reaches 84.3% ID / 83.5% OOD (Appendix J.3). This run uses the bias-focused posterior settings, so it measures a combined parameter-and-budget configuration. The longer-limit baseline comparison is still ongoing, as detailed in W1/Q1.
  4. Clearer main-text presentation (W4). We added a concise Tree-GRPO advantage formula, a method overview, and an explanation of the raw → centered → combined advantage construction. We revised Figure 1's caption, identified the comparison baselines and percentage-point units in the introduction, and added Conclusion and Limitations summaries to the main text.

Additional MiniWoB++ training-seed runs for GiGPO, Tree-GRPO and RegPO are ongoing, while BBH replications await capacity on the compatible VLA server. We will incorporate these results as they become available; W2/Q2 explains the current evidence and the limited interpretation of the MiniWoB++ margin.

Together, the expanded benchmark evaluation, agentic component studies and presentation revisions directly address the experimental and clarity priorities you outlined. We would be grateful if you would reassess the revised paper in light of these additions. The detailed replies below follow your original weakness/question order, with joint W1/Q1 and W2/Q2 answers.

AuthorsOpenReview ↗

Response to Reviewer FK3U (1/3)

W1 + Q1. ALFWorld protocol and the WebShop comparison.

The extended-limit ALFWorld run reaches 84.3% ID / 83.5% OOD at 50 episode steps and 512 response tokens. The original baseline comparison uses 30-step/256-token limits; the extended RegPO run uses the combined settings reported below.

Completed extended-budget ALFWorld run. The final update-200 model reaches 84.3% ID and 83.5% OOD success at 50 episode steps and 512 response tokens (Appendix J.3). This completed run uses the bias-focused posterior tuple (0.75,21,84,10.5,5)(0.75,21,84,10.5,5); it changes the estimator settings as well as the interaction and training budgets. The result measures performance under this combined configuration. Extended-limit Tree-GRPO training and the default-parameter RegPO follow-up are ongoing, and we will incorporate their results as they become available. The existing baseline comparisons use the original 30-step/256-token protocol (Appendix I.2.2), so the completed extended-budget RegPO result alone does not establish the margin over baselines under the longer-limit recipe.

On WebShop, 65.9% lies within the published GiGPO range you cite; 62.0% is our in-stack reproduction. Appendix I.2.2 explains the common implementation, prior-work configurations where compatible, and adaptations to prompts, wrappers, parser and budgets. Appendix I.2.1 distinguishes RegPO's final checkpoints on WebShop from baseline selection on the reported splits. These are in-stack comparisons under the documented implementation and checkpoint rules (Appendices I.2.2 and I.2.1).

W2 + Q2. Training variance and additional seeds.

Additional independent training and evaluation are underway for MiniWoB++ GiGPO, Tree-GRPO and RegPO, with one extra seed per method. We will incorporate these results into the manuscript as they become available.

We treat MiniWoB++'s 2.1-percentage-point margin as marginal, given the reported evaluation variation and the single training seed. Our interpretation is limited to the observed point estimate; repeated evaluation of one checkpoint does not measure training-seed variation (Appendix I.2.1).

BBH additional-seed runs await capacity on the compatible VLA server. In our tested setup, the pretrained SFT policy worked on an Intel-based server but not the available AMD-based alternative, restricting replication to compatible hardware with limited capacity. No additional BBH training-seed result is reported here.

BBH's reported margins are larger: RegPO reaches 78.9% ID / 73.4% OOD, versus the strongest baseline GRPO's 64.1% / 67.2%, giving 14.8 / 6.2 percentage points (Table 1(a)). These remain point-estimate gaps from the reported training run; independent replications are needed to quantify training-seed variation.

AuthorsOpenReview ↗

Response to Reviewer FK3U (2/3)

W3. Which components account for the gains?

Appendix J reports estimator, posterior-parameter, regret-weight, base-removal and scaling contrasts. We also report the BBH centering-off result below.

  • Posterior prediction on ALFWorld: replacing predictive values with observed sampled maxima, while retaining the base advantage and available-range centering, gives 37.1% ID / 40.3% OOD, compared with the RegPO point estimates in Table 1 of 65.7% / 62.4%. The reported comparison supports predictive estimation in the evaluated sparse-rollout setting (Appendix J.1.2); Q3 gives its interpretation.
  • Posterior settings on Minesweeper: default and lower-concentration settings reach validation peaks of 60.94% and 59.38%, respectively. The latter preserves the posterior means for identical observations while reducing concentration. Each setting has one training run, providing sensitivity measurements for the two tested configurations (Appendix J.1.1 (Table 11)).
  • Regret weight with the base fixed: Minesweeper now includes wreg=0,1,2,4w_{\rm reg}=0,1,2,4, with validation peaks 53.13%, 60.94%, 55.47%, 55.47%. Unit weight gives the highest observed peak among the tested retained-base settings (Appendix J.2.1 (Table 12)).
  • Base removal on BBH: training with only the unit-weight regret component reaches 68.9% success. This provides agentic evidence that the feedback can be useful without the additive Tree-GRPO base (Appendix J.2.3). We report this as a success rate without assigning an ID/OOD-specific margin.
  • Centering on BBH: the centering-off variant reaches 65.6% success, as reported in our response to Reviewer E9VM. Q3 discusses this measurement and its scope.
  • Whole-base scaling on ALFWorld: the 2×2\times Tree-GRPO control reaches 35.0 ± 10.5% ID across three training seeds, with per-seed best-ID scores of 47.1%, 30.0%, and 27.9% (mean ± sample standard deviation of the reported percentages). All three checkpoints are selected by best ID performance within 150 updates at 30 actions/256 tokens. RegPO’s paper reference is 65.7 ± 1.5% ID, also across three best-ID-selected training seeds. The control uses three base trajectories/one branching prefix, versus four/two in the paper. Appendix J.2.2 (Table 13).
  • Whole-base scaling on WebShop: the same doubled-base control improves faster during roughly the first 50 updates. From about update 55 through update 150, RegPO attains higher evaluation success; training success follows the same ordering after update 50, and the two training curves approach each other by update 150 (Appendix J.2.2, Figure 14).

The low-branching synthetic result in Section 4.1.2 (Figure 3) remains specific to its tested configuration; the new agentic evidence helps distinguish that result from the performance of individual components on the reported tasks. Q3 below gives the estimator, centering and weight interpretation, while Q4 addresses adding the term to GRPO or GiGPO.

W4. Presentation and reporting.

The main text now includes a short Tree-GRPO advantage formula and definitions at the end of Section 2, a method overview before Section 3.1, and a clarification of the raw → centered → combined advantage. Figure 1 now explains the current-policy mean versus best achievable continuation and identifies the schematic tree, omitted branches/levels and terminal-return labels. The introduction names the baseline set and reports point-estimate margins in percentage points of success rate. Table 1 now includes Minesweeper and Sokoban with explicit evaluation-repetition accounting. A main-text Conclusion and Limitations summary states the coverage, policy-support, predictive-model and stochastic-maximum restrictions and the absence of an LLM convergence guarantee (Section 5).

W5. Closing soundness note.

The two new benchmarks, estimator/weight/base-removal/scaling studies, reported centering-off result and extended-budget ALFWorld result expand the empirical evidence. The revised main text presents the method alongside these measurements, with the clearer advantage construction, Figure 1 caption, conclusion and limitations requested in W4.

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

This paper proposes RegPO, a method that adds regret-based step-level credit to tree-structured policy optimization. Its motivation is that an action can appear poor under the current policy yet lead to high reward if followed by better decisions. RegPO estimates this potential from sampled continuations at selected prefixes and uses it to guide training. The MDP experiments examine how different advantage estimates affect learning dynamics, while evaluations on four agentic benchmarks show strong performance.

Critical strengths
  1. Regret-based feedback offers a way to assign credit to individual actions whose potential may be missed by current-policy value estimates.
  2. The theoretical analysis illustrates when conventional advantage estimates can discourage hard but potentially rewarding actions.
  3. RegPO achieves the best reported results among the compared methods on four agentic benchmarks.
Critical weaknesses
  1. RegPO is intended to recognize the potential of hard actions. However, if the correct actions that follow a hard action have low probabilities, limited rollouts may never reveal a successful continuation. This could limit the method in precisely the setting it aims to address.
  2. Tree-GRPO provides the base advantage used by RegPO, but its computation is left to the appendix. A brief explanation in the main text would make the method easier to follow.
  3. RegPO adds credit at selected agent steps, but the paper does not show how often those steps yield a useful comparison between actions. It is therefore hard to tell how targeted this intervention is in practice.
Questions for authors
  1. When successful continuations after a hard action are unlikely under the current policy, how sensitive is RegPO to the rollout budget? Are there ways to address this limitation without substantially increasing that budget?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 61Sq (1/2)

Thank you for your thoughtful review. We are also glad that you found our theoretical analysis helpful in explaining why conventional advantages may discourage difficult but potentially rewarding actions, and that you acknowledged our strong results across the original four agentic benchmarks.

Please also see the updated manuscript and the revisions highlighted in color.

Additional experiments.

Beyond the weaknesses and questions you raised, we added experiments that support the paper more broadly. Two new benchmarks bring the comparison to six. On Minesweeper with Qwen3-4B, RegPO reaches 59.4 ± 2.6%, compared with 53.1 ± 0.8% for GiGPO, the strongest baseline; these are five evaluations of one final checkpoint per method, on 128 validation boards that were also used for model selection. On Sokoban with Qwen2.5-1.5B, RegPO solves 35.2 ± 0.6% of boards, compared with 27.7 ± 0.5% for Tree-GRPO, the strongest baseline; these are three evaluations of one update-150 checkpoint per method on 512 validation boards (Table 1(a)). On ALFWorld, a run with longer limits (50 actions per episode, 512 tokens per response, 200 updates) reaches 84.3% ID / 83.5% OOD.

Below, we respond to W1, W2, W3 and Q1 in your original order.

W1. What if successful continuations are rarely sampled?

Limited rollouts may fail to discover successful continuations. When all observed continuations yield identical failure returns, return-based group-relative methods (GRPO, GiGPO, Tree-GRPO, and ours) cannot distinguish among them. Once a successful continuation is observed, however, sampled-max feedback can preserve credit for the earlier action that enables success, even when its mean return under the current policy remains low. In contrast, mean-based group-relative feedback may still assign insufficient credit to such actions. Therefore, our method therefore provides stronger credit assignment for difficult but promising actions, facilitating more efficient exploration as training progresses. Theorem 2 characterizes this benefit under the condition that the estimated action gaps satisfy Δ^≥Δπ\widehat\Delta\ge\Delta_\pi throughout learning. Furthermore, the controlled experiments in Section 4.1 distinguish initial success discovery from subsequent policy improvement. The results demonstrate that, after a successful continuation is discovered, our method accelerates learning by reinforcing the actions that enable success, thereby improving exploration efficiency during subsequent training.

W2. Tree-GRPO computation in the main text

Thank you. Section 2 now ends with the Tree-GRPO advantage formula and brief definitions of its symbols, so readers can see what RegPO adds on top of it.

W3. How often RegPO's comparisons are useful

RegPO's extra credit matters when the current policy's average return and the best achievable return rank two actions differently. In the ALFWorld diagnostic (Appendix L), this happens at 65 of 96 fixed states (67.7%), giving 153 such action pairs; in MiniWoB++ (Appendix M), it happens at 41 of 86 fixed states (47.7%), giving 88 pairs. Both use the early policy and the GPT-5.5 reference described in W1. On these pairs, RegPO's estimate is at least as favorable to the reference-preferred action as the early policy's average in 92.2% and 84.1% of cases, respectively.

AuthorsOpenReview ↗

Response to Reviewer 61Sq (2/2)

Q1. Sensitivity to the rollout budget, and coping without a bigger one

Budget sweep (Section 4.1.2, Figure 3). We vary the number of children per node, b∈(2,5,10,30)b\in (2,5,10,30), train for 1,000 updates, and roughly match GRPO's number of generated actions at each bb. As bb increases, the performance gap between mean-based and regret-based methods becomes increasingly pronounced, particularly for b≥5b\geq 5, highlighting the growing advantage of regret-based feedback in settings with larger branching factors.

Rare successes (Appendix K.2, Figure 15). Here we lower the initial probability of the correct Hard steps (q0=0.46q_0=0.46, versus 0.720.72 in the main setting) and use depths H∈{6,8,10,12,14,16,20,30}H\in\{6,8,10,12,14,16,20,30\}, with b=10b=10, 1,000 training steps and 500 seeds per setting. In every run, every feedback rule samples at least one successful Hard rollout. Mean-return feedback and regret-based feedback alone both eventually make Hard worth at least Safe's return, Qπ(ξ,Hard)≥cQ^\pi(\xi,\mathrm{Hard})\ge c, in every run, but mean-return feedback needs about 2.2× as many steps at H=10H=10 and 3.5× at H=30H=30.

Ways to cope without a bigger budget. A key advantage of RegPO is its ability to provide more informative learning signals under a limited rollout budget by accounting for unobserved continuations. Rather than relying solely on sampled returns, the posterior predictor estimates the potential returns of unobserved branches using evidence shared across sibling actions. As a result, RegPO can assign meaningful credit to promising but underexplored actions even when successful continuations have not yet been observed. By accounting for uncertainty about unobserved branches, the predictor helps mitigate the limitations of sparse sampling without requiring additional rollouts. The ALFWorld ablation in Section J further demonstrates the importance of posterior prediction for effective learning.

Thank you again for your constructive guidance and positive assessment. We hope these answers (what RegPO does when successes are rare, how often its comparisons are useful, and how it behaves under small rollout budgets) address your questions and strengthen your support for acceptance.

Thank you for your detailed response. My concerns have been resolved.

Reviewer_E9VMOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes RegPO, a method for training LLM agents on top of Tree-GRPO rollout trees. At selected branching prefixes it adds a step-level "regret" advantage, A^t=Q^t(ξ,a)−max⁡a′Q^t(ξ,a′)\hat A_t = \hat Q_t(\xi,a) - \max_{a'}\hat Q_t(\xi,a'), to the Tree-GRPO advantage, with wreg=1w_{\text{reg}}=1. Q^\hat Q is either:

  • the maximum sampled continuation return under each action, or
  • a Beta pseudo-posterior predictive maximum that extrapolates to unsampled leaves.

The motivation is the decomposition of per-episode regret into action gaps V⋆−Q⋆V^\star - Q^\star (Prop. 1). In a "Hard-Safe" chain MDP, QπQ^\pi- and Q⋆Q^\star-based comparisons disagree. There, updates using only AπA^\pi need time exponential in HH, while sufficiently informative A⋆A^\star-like feedback needs only O(H2/ϵ)O(H^2/\epsilon) (Thm. 2, Props. 10–13).

Experiments cover:

  • synthetic Hard-Safe and random trees;
  • four agentic benchmarks (RoboTwin Beat Block Hammer, WebShop, MiniWoB++, ALFWorld) with Qwen2.5-1.5B and OpenVLA-OFT-7B;
  • a mechanistic ALFWorld/MiniWoB++ analysis that uses a single GPT-5.5 continuation as a Q⋆Q^\star proxy.

RegPO has the highest point estimate in every benchmark row. The largest gains are on ALFWorld (+20 ID / +29 OOD).

Critical strengths
  1. A clean isolation of an old issue in the tree-GRPO setting. Tree-GRPO's grouped intra-tree advantage induces a QπoldQ^{\pi_{\text{old}}} mean comparison at a prefix. The Hard-Safe construction, the finite-sample mean-vs-max comparison (Prop. 3), and the ODE analysis make it concrete when this suppresses an action whose value lies in a low-probability downstream suffix. The paper is also explicit about where the argument stops: stochastic outcomes, support limits, and the fact that a combined-loss step need not decrease L1L_1 (F.2).
  2. Diagnostics beyond headline numbers. The paper measures action-selection, intermediate-state reach, and forced-action success from frozen ALFWorld prefixes, and tests partial pooling across sibling actions (H.7). This tries to connect the mechanism to behavior, which most papers in this line do not attempt.
Critical weaknesses

W1. The "regret" mechanism is largely inoperative at the tree sizes actually used; gains are confounded with plain step-level credit assignment.

The theory and synthetic results rely on large recursive trees: b=10b=10 at every node, and GRPO group sizes up to ~2×1052\times10^5 to match. The agentic runs use:

  • 4 base trajectories;
  • 2 sampled actions per branching prefix;
  • depth 2.

That leaves roughly one or two leaves under each action, so Q^max⁡≈Q^mean\hat Q^{\max}\approx\hat Q^{\text{mean}}. On Beat Block Hammer (sampled-max with sampled-range centering, two actions), the centered regret advantage is algebraically

A~=Q^(a)−12(Q^(a)+Q^(b))=±12(Q^(a)−Q^(b)),\tilde A = \hat Q(a) - \tfrac{1}{2}(\hat Q(a)+\hat Q(b)) = \pm\tfrac{1}{2}(\hat Q(a)-\hat Q(b)),

which is just a mean-centered step-level advantage at the branch prefix.

Tree-GRPO broadcasts a trajectory-level scalar, so "Tree-GRPO + any local advantage at branch prefixes" would be expected to help. Prop. 2 itself argues this. The key missing ablation is RegPO with Q^mean\hat Q^{\text{mean}} in place of Q^max⁡\hat Q^{\max}/Q^post\hat Q^{\text{post}}, holding fixed:

  • the same prefixes;
  • the same centering;
  • wregw_{\text{reg}}.

Without it, the improvements cannot be attributed to regret/optimal-continuation feedback rather than local credit. For the language agents, the remaining difference lies in the pseudo-posterior extrapolation, which is effectively a model-based optimism bonus. Its strength depends on (μ0,η0,η,wobs,λleaf,Ka)(\mu_0,\eta_0,\eta,w_{\text{obs}},\lambda_{\text{leaf}},K_a), and the training-time values of KaK_a and these hyperparameters are not clearly reported or justified.

W2. The baselines look undertrained or broken, and protocol choices make the margins hard to trust.

  • Tree-GRPO is worse than GRPO on every benchmark: ALFWorld 23.1 vs 28.6, WebShop 48.1 vs 57.6, BBH-OOD 43.8 vs 67.2. RegPO is Tree-GRPO plus one term, so the headline "margin over strongest baseline" partly measures recovery from a weak base.
  • The reproduced GRPO/GiGPO ALFWorld numbers (28.6 / 45.5) are far below what the GiGPO paper reports for the same 1.5B backbone. The authors attribute this to a shortened horizon (30 vs 50 steps), a 256-token response limit, and 150 updates. Table 1(b) suggests all methods are still in an early regime.
  • Loss aggregation differs between groups (token-mean for GRPO/GiGPO, sequence-mean/token-mean for Tree-GRPO/RegPO).
  • BBH and MiniWoB++ use a single training seed. The MiniWoB++ margin (2.1 pts) is within plausible seed variance.
  • The branching configuration was chosen on the WebShop test split and the MiniWoB++ evaluation split (Table 9, seed 0).
  • The mechanistic analysis uses prefixes sampled from trained RegPO's own trajectories, with candidates that include RegPO's action. This favors RegPO by construction. A single GPT-5.5 continuation is also a weak Q⋆Q^\star proxy.

On the theory side, the results are largely known in spirit:

  • Prop. 1 is the performance-difference lemma with π⋆\pi^\star.
  • The AπA^\pi-only exponential lower bound is the standard vanishing-gradient result for combination-lock/chain MDPs.
  • The polynomial upper bound assumes access to (near-)A⋆A^\star, as in AggreVaTeD.

The sampled version still needs Ω(1/pπ)=Ω(q0−H)\Omega(1/p_\pi)=\Omega(q_0^{-H}) samples to discover the success leaf (Prop. 3). So the separation is in learning time given information, not in sample complexity. The paper should state this plainly, and the related work should discuss:

  • VinePPO (MC values at intermediate prefixes);
  • Setlur et al. 2024, "Rewarding Progress", which argues for advantages under a stronger prover policy rather than the base policy, essentially the QπQ^\pi vs QbetterQ^{\text{better}} point;
  • Math-Shepherd's "hard estimation", a sampled-max over completions;
  • pass@k / best-of-N-aware RL objectives.
Questions for authors
  1. (Decisive.) Can you run the ablation in W1, i.e. RegPO's exact pipeline with Q^mean\hat Q^{\text{mean}}, on ALFWorld and WebShop with 3 seeds? If most of the gain remains, the paper's framing should change.
  2. In the agentic runs, what fraction of branch-prefix comparisons have more than one leaf under both actions? How often does Q^max⁡≠Q^mean\hat Q^{\max}\neq\hat Q^{\text{mean}} actually occur?
  3. What are KaK_a and the pseudo-posterior hyperparameters during training, and how were they chosen? Were any chosen using evaluation-split or GPT-reference data?
  4. Why is Tree-GRPO below GRPO everywhere? Does it recover with a longer horizon (more updates, 50-step ALFWorld episodes)? Do RegPO's margins persist once baselines reach the regime reported in prior work?
  5. (Clarification.) Under base branching, the base-trajectory action typically has more descendant leaves than the alternative. Q^max⁡\hat Q^{\max} grows with leaf count, which would bias comparisons toward the base action. Is this corrected?
  6. (Clarification.) Can the mechanistic analysis be repeated on prefixes sampled from Tree-GRPO's or a neutral policy's trajectories?
14 comments
AuthorsOpenReview ↗

Response to Reviewer E9VM (General Response)

Thank you for recognizing the controlled Hard–Safe isolation of mean-return versus best-continuation feedback, its connection to action selection, intermediate-state reach and continuation success, and the sibling-pooling analysis. We also appreciate your recognition of the explicit scope statements on stochastic outcomes and policy support.

Please also see the updated manuscript and the revisions highlighted in color. We have focused the revision on making that case more concrete through ablation studies, explicit estimator specifications and additional environments. Before answering your points individually, we highlight the additions most relevant to that assessment, together with the broader work we are preparing. We expanded the evaluation from four to six agentic benchmarks by adding Minesweeper and Sokoban, alongside new component ablations and extended-horizon experiments.

  1. Agentic component evidence and a fully specified online estimator. We added an ALFWorld predictive-versus-observed-max comparison, Minesweeper posterior-concentration sensitivity and a regret-weight sweep with the Tree-GRPO base fixed. These examine the estimator and auxiliary signal in agentic training, complementing the controlled feedback comparisons you recognized. The appendix now gives the default posterior parameters, 128 predictive Monte Carlo draws and nominal Ka=2K_a=2. We also report a three-seed doubled-base ALFWorld control using best-ID checkpoints, with its rollout differences stated below, and the same control on WebShop as learning curves. The exact local-mean comparison remains a separate attribution question in W1/Q1.

  2. Sokoban: a sixth benchmark with Hard–Safe-type decisions. We added two-box Sokoban with Qwen2.5-1.5B as a sixth benchmark. Its decisions natively have the Hard–Safe structure: placing the first box on a target earns 1 and solving earns an additional 10, and because boxes cannot be pulled, an early push that secures the first box can block the second. RegPO solves 35.2 ± 0.6% of boards, compared with 27.7 ± 0.5% for Tree-GRPO, 17.8 ± 0.4% for GiGPO and 16.1 ± 0.8% for GRPO (Table 1(a)); these are three evaluation repetitions of one update-150 checkpoint per method on 512 validation boards.

  3. Minesweeper: a new benchmark where tree-based baselines already outperform GRPO. We added Qwen3-4B Minesweeper as a fifth benchmark, extending our evaluation beyond the original four agentic environments. Importantly, this new setting provides a stronger test of RegPO's contribution, as both GiGPO and Tree-GRPO already substantially outperform GRPO. At final update 300, RegPO reaches 59.4 ± 2.6%, compared with 53.1 ± 0.8% for GiGPO, 49.4 ± 2.0% for Tree-GRPO and 40.3 ± 1.0% for GRPO.

  4. A new comparison where the tree baseline already exceeds GRPO. On Qwen3-4B Minesweeper, final-update-300 RegPO reaches 59.4 ± 2.6%, compared with 53.1 ± 0.8% for GiGPO, 49.4 ± 2.0% for Tree-GRPO and 40.3 ± 1.0% for GRPO. These are five evaluation repetitions of one final checkpoint per method. Peak training-time validation performance is 60.94% for RegPO (update 275), 53.91% for GiGPO (300), 53.13% for Tree-GRPO (225) and 47.66% for GRPO (165). RegPO thus has the highest observed score under both summaries, with a 7.03-percentage-point margin over the strongest baseline peak. Peaks are selected over the same five-update evaluation cadence through update 300, using single evaluations on the same 128 validation boards and one training run per method; they are separate from the five-repeat final-checkpoint means above. This adds a setting where Tree-GRPO exceeds GRPO and RegPO improves the reported point estimate over both and the strongest listed comparator. Both summaries use the reused development board pool and one training run per method. Sokoban (item 2) gives a second such setting: Tree-GRPO solves 27.7% of boards versus 16.1% for GRPO.

  5. Extended-limit ALFWorld evidence and stronger reporting. A completed 50-action / 512-token / 200-update run reaches 84.3% ID / 83.5% OOD, using a different posterior settings. The new training recipe jointly changes posterior settings, interaction limits and training budget. The replies below also clarify training versus diagnostic settings, Theorem 2's conditions, and checkpoint choices.

Some additional ablations are still ongoing, particularly the extended-horizon ALFWorld comparison, which requires approximately 35 hours on two H200 GPUs per run. We are making every effort to secure the necessary computational resources and complete these experiments. Nevertheless, we believe the completed experiments and expanded analyses already address most of your questions, as detailed in our point-by-point responses below. We will continue incorporating additional results into the manuscript as they become available and update the paper accordingly.

AuthorsOpenReview ↗

Response to Reviewer E9VM (1/7)

W1 + Q1. Shallow-tree feedback and complementary ablations

1. Do max and mean coincide in shallow rollout trees?

Thank you for pointing this out: the equality Q^max⁡=Q^mean\widehat Q^{\max}=\widehat Q^{\mathrm{mean}} holds at the deepest split with one sampled terminal continuation per action, but it does not hold in general at earlier splits.

Consider the unbalanced base-branching tree discussed in your review, with illustrative terminal returns of 1, 0.6 and 0.2:

Each edge is labeled (centered local-mean advantage, centered max-based advantage); terminal labels are returns.

u
├─ a (base): (+0.3, +0.4) → v
│                           ├─ c (base): (+0.2, +0.2) → return 1
│                           └─ d (alternative): (−0.2, −0.2) → return 0.6
└─ b (alternative): (−0.3, −0.4) → return 0.2
Prefix / estimator / actionAction-value calculationRaw local advantageCentered local advantage
Deepest vv, max or local mean, ccSingle return: Qc=1Q_c=11−1=01-1=01−(1+0.6)/2=0.21-(1+0.6)/2=0.2
Deepest vv, max or local mean, ddSingle return: Qd=0.6Q_d=0.60.6−1=−0.40.6-1=-0.40.6−(1+0.6)/2=−0.20.6-(1+0.6)/2=-0.2
Earlier uu, max, aaQa=max⁡(1,0.6)=1Q_a=\max(1,0.6)=11−1=01-1=01−(1+0.2)/2=0.41-(1+0.2)/2=0.4
Earlier uu, max, bbSingle return: Qb=0.2Q_b=0.20.2−1=−0.80.2-1=-0.80.2−(1+0.2)/2=−0.40.2-(1+0.2)/2=-0.4
Earlier uu, local mean, aaQa=(1+0.6)/2=0.8Q_a=(1+0.6)/2=0.80.8−0.8=00.8-0.8=00.8−(0.8+0.2)/2=0.30.8-(0.8+0.2)/2=0.3
Earlier uu, local mean, bbSingle return: Qb=0.2Q_b=0.20.2−0.8=−0.60.2-0.8=-0.60.2−(0.8+0.2)/2=−0.30.2-(0.8+0.2)/2=-0.3

2. How do we distinguish regret feedback from additional mean-based credit?

Tree-GRPO already contains mean-return-based intra-tree feedback (local mean based advantage). This is a weighted-mean-based contribution, reducing to the ordinary mean comparison under the balanced conditions in Appendix C.4, Eq. (7). RegPO retains this mean-based feedback and adds the regret-based component, A^tree+wregA~reg\widehat A^{\mathrm{tree}}+w_{\mathrm{reg}}\widetilde A^{\mathrm{reg}}. In this manner, we therefore provide three complementary ablations: strengthening the existing base, varying the regret weight with the base fixed, and comparing regret-only with Tree-GRPO-only training.

2- Ablation 1. Testing the additional mean-feedback explanation: ALFWorld and Webshop (and Sec 4.1).

We test whether strengthening Tree-GRPO's existing mean-based feedback can account for the gain by comparing A^tree+A^tree\widehat A^{\mathrm{tree}}+\widehat A^{\mathrm{tree}} with A^tree+A~reg\widehat A^{\mathrm{tree}}+\widetilde A^{\mathrm{reg}}. The first repeats the complete base, including its mean-return intra-tree feedback; the second adds the best-continuation component.

Section 4.1 already studies normalized mixtures λAmean+(1−λ)Areg\lambda A^{\mathrm{mean}}+(1-\lambda)A^{\mathrm{reg}} with prefix-level tabular updates, using recursive-mean feedback as the synthetic counterpart of the Tree-GRPO comparison. At b=10b=10, the equal mixture improves attainment over recursive mean by 10.4 percentage points (paired 95% CI [5.8, 15.0]); pure max is worse at b=2b=2 in the tested setting. The agentic comparisons extend this investigation to the implemented full base.

1-WebShop — learning curves through update 150. The doubled-base control improves faster during roughly the first 50 updates. From about update 55 through update 150, RegPO attains higher evaluation success; training success follows the same ordering after update 50, and the two training curves approach each other by update 150 (Appendix J.2.2, Figure 14).

2-ALFWorld — three training seeds, best-ID checkpoints.

SplitDoubled Tree-GRPO baseRegPO, paper reference
ID35.0 ± 10.5%65.7 ± 1.5%

The control's per-seed best-ID scores are 47.1%, 30.0%, and 27.9%; its summary is the mean ± sample standard deviation computed from these reported percentages. All three runs use 30 actions/256 tokens and train for 150 updates. Both rows use best-ID-selected checkpoints across three training seeds. The control uses three base trajectories/one prefix, while the paper reference uses four/two. Appendix J.2.2 (Table 13).

(W1/Q1-2 - ablation 2 will be continued in the next response)

AuthorsOpenReview ↗

Response to Reviewer E9VM (2/7)

W1/Q1 2-Ablation 2. Varying regret weight while retaining the base: Minesweeper.

We train with A^tree+wregA~reg\widehat A^{\mathrm{tree}}+w_{\mathrm{reg}}\widetilde A^{\mathrm{reg}}, holding the base and default posterior settings fixed.

wregw_{\mathrm{reg}}0124
Peak validation success53.13%60.94%55.47%55.47%
Peak update225275220250

Unit regret weight gives the highest tested peak, 7.81 percentage points above the zero-regret setting. Each setting has one training run through update 300, evaluated every five updates on 128 validation boards. These are training-time peaks. Appendix J.2.1 (Table 12).

W1/Q1 2 - Ablation 3. Regret-only versus Tree-GRPO-only: Beat Block Hammer.

We remove the base and train using only A~reg\widetilde A^{\mathrm{reg}}, comparing it with Tree-GRPO-only training. The pure-regret variant reaches 68.9% success, reported above the Tree-GRPO baseline in the base-removal study (Appendix J.2.3). This comparison evaluates regret feedback without an additive Tree-GRPO base. For the centering off example with Beat Block Hammer reaches 65.6% success as well.

These comparisons are complementary across environments: the WebShop/ALFWorld controls compare amplification of the existing base with added regret feedback; the Minesweeper sweep measures the regret contribution with a fixed base; BBH tests regret feedback on its own.

The exact local-mean substitution requested in Q1 holds the base, prefixes, centering, budget, aggregation and weight fixed while replacing the max/predictive estimator inside the auxiliary term with Q^mean\widehat Q^{\mathrm{mean}}.

3. How is predictive extrapolation specified and justified?

The predictor estimates the best continuation return from observed returns and modeled unobserved continuations. For each pseudo-posterior draw, we take the maximum over observed and modeled normalized returns, average these maxima, and map back to reward units. Its dependence on the observed returns and remaining modeled leaves is explicit in Appendix G.4.

Training settings. Appendix I.2.3 now reports the default parameters (μ0,η0,η,wobs,λleaf)=(0.5,4,8,20,20)(\mu_0,\eta_0,\eta,w_{\mathrm{obs}},\lambda_{\mathrm{leaf}})=(0.5,4,8,20,20), nominal Ka=2K_a=2, and 128 predictive draws.

Rationale and empirical bias checks. The defaults use weak pooling: η0/wobs=0.2\eta_0/w_{\mathrm{obs}}=0.2 and η/wobs=0.4\eta/w_{\mathrm{obs}}=0.4, corresponding to root and action-level prior weights of 0.2 and 0.4 observations. Observed returns therefore quickly dominate as continuations accumulate. The nominal capacity of two follows the two-action, depth-two local model.

The paper also evaluates the estimator's empirical bias. In the controlled synthetic study of Appendix G.6, only two of 16 continuations per action are observed across 1,000 prefixes. The mean signed error against the known full-tree maximum is −0.00025, with 95% CI [−0.00274, 0.00203], indicating negligible mean signed bias in this setting. A separate task-held-out ALFWorld calibration study reports aggregate signed discrepancy −0.111 against the GPT continuation reference, with MAE 2.277 reward units (Appendix G.7). This diagnostic uses its own calibration configuration, separately from the training defaults.

Sensitivity and estimator comparisons. On Minesweeper, changing the parameters to (0.5,1,2,5,20)(0.5,1,2,5,20) preserves the shared mean, action-quality posterior means and pooling ratios for identical observations while reducing action-level concentration fourfold. The default and lower-concentration settings attain peak validation success of 60.94% and 59.38%, respectively, with one training run per setting (Appendix J.1.1, Table 11). These similar peaks suggest limited sensitivity to the tested change in posterior concentration. On ALFWorld, the reported observed-max variant reaches 37.1% ID / 40.3% OOD, compared with the predictive RegPO main-table scores of 65.7% / 62.4%, retaining the base advantage and available-range centering (Appendix J.1.2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.