acceptodds
Under review as a conference paper at ICLR 2027

3SPO: State-Score-Supervised Policy Optimization for LLM Agents

Abstract

Training large language models (LLMs) as autonomous agents via reinforcement learning (RL) has enabled frontier models to achieve superhuman performance in long-horizon tasks. However, existing RL algorithms operate at the trajectory level, performing policy optimization only after collecting complete episode rollouts. This coarse-grained approach faces fundamental challenges in multi-turn agent settings where rewards are sparse, delayed, and credit assignment across individual steps is critical. In this work, we propose State-Score-Supervised Policy Optimization (3SPO), a novel RL algorithm that performs post-step policy optimization with dynamic state score supervision. At each step, 3SPO computes the state score based on historical success rates, supervising step-wise credit assignment, adaptive rollout and post-step policy optimization without requiring value function estimation or additional auxiliary models. Theoretically, under a per-state bandit abstraction, we show that the proposed score-supervised allocation mechanism achieves logarithmic allocation regret and provide sample-complexity guarantees for action identification, score distinguishability, and filtering stability. Experiments on ALFWorld and WebShop with Qwen2.5-1.5B/7B-Instruct show that 3SPO consistently outperforms GRPO by on ALFWorld and points on WebShop, while using comparable resources to achieve more state exploration and faster convergence.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, LLM

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

The paper proposes 3SPO, a training framework for multi-turn LLM agents that uses historical state success rates to construct step-wise rewards, allocate candidate rollouts, and support post-step policy updates. It combines these mechanisms with ranked backtracking and evaluates them on ALFWorld, WebShop, and supplementary benchmarks.

Critical strengths

A shared state-score mechanism connects credit assignment, sampling allocation, and policy updates without an additional critic or learned reward model. Results show improvements over trajectory-level and step-level baselines across multiple model scales.

Critical weaknesses
  1. The proposed method combines step-wise credit assignment, success-rate-guided sampling, and state grouping with immediate updates and backtracking, but the ablations do not isolate post-step updating from the accompanying changes in rewards, sampling, and search.
  2. The core mechanisms are broadly applicable RL heuristics, while the theory does not model language-specific structure. Exact state matching, admissible actions, and environment backtracking may also restrict applicability beyond the evaluated environments.
  3. The overall factor of 0.5 largely cancels under group-normalized advantages; the substantive choices are the relative weighting of intermediate and terminal rewards and the exponential transition from novelty to score differences. The relationship between the theoretically derived decay rate and the experimentally reported setting is unclear.
  4. The correspondence between theoretical arms, sampled textual candidates, environment actions, and successor states is insufficiently specified. The assumed one-to-one action–successor correspondence further limits the abstraction.
  5. Appendix A.2.3 replaces ⌈Gmax⁡S(a)⌉\lceil G_{\max}S(a)\rceil with a continuous allocation, treating rounding as an O(1)O(1) discrepancy. Such discrepancies can accumulate linearly across rounds. The proof needs to account explicitly for integer allocation and filtering.
  6. The analysis treats eventual success probabilities as fixed, whereas post-step optimization changes the continuation policy throughout training. Historical success rates therefore combine outcomes generated by different policies. The paper does not establish when these estimates remain valid or how the concentration and allocation guarantees extend to this nonstationary setting.
Questions for authors
  1. Can you compare post-step and post-trajectory updates while holding rewards, candidate allocation, backtracking, and resource budgets fixed?
  2. Which components specifically address LLM-agent training rather than general RL? How does the method extend to open-ended text actions, rarely repeated observations, or environments without efficient state restoration?
  3. Please justify the relative intermediate/terminal reward weights and reconcile the theoretical decay schedule with the experimental setting.
  4. Please state the dependence on action cardinality and probability gaps, and clarify the computational costs as the action space grows.
  5. Under what conditions does filtering prevent persistent minimum-one allocation from producing linear regret?
  6. How are historical statistics corrected for policy changes? Please evaluate windowed, discounted, or reset statistics and clarify which theoretical conclusions survive when success probabilities evolve during training.
6 comments
AuthorsOpenReview ↗

Response to Reviewer gVGR (1/4): Update Timing, Applicability, and Action-Space Costs

Response to Reviewer gVGR: Update Timing, Applicability, Reward Design, and Theoretical Scope

Thank you for the questions about timing, applicability, reward design and nonstationarity. We give the empirical controls first and delimit the theoretical conclusions separately. We have revised the manuscript accordingly. Metrics are ALF In/Out and WS Score/Success at 1.5B unless stated otherwise; "±" is the seed s.d.

1. Update timing (W1/Q1)

The online V0/V1 contrast is the relevant timing evidence. V0 updates after each step; V1 defers updates. The controls use the same reward and allocation rules, DFS, nominal optimizer-step budget, batch/normalization, learning rate, initialization and paired seeds (§4.5, A.4.3). Subsequent trajectories may differ because updates change behavior.

Table R1 — Update-timing controls (paper Table 13; three seeds):

VariantUpdate scheduleALF InALF OutWS ScoWS Suc
V0 (full 3SPO)post-step, per state95.4293.1890.2879.46
V1delayed to episode end, count-matched92.689.988.176.3
V2delayed, single batch per episode91.889.087.275.4
V3post-step, no DFS (= w/o Backtrack)88.9887.0085.3274.18
V4delayed, no DFS86.784.983.672.6

The paired V0−V1 gain is +2.82±0.46 pp on ALF In (95% CI [1.68,3.96]); WS Success gains 3.16 pp. A.4.3 now reports the audited run accounting against the nominal targets E₀=E₁=B_E, T₀=T₁=B_T, U₀=U₁=B_U:

Table R2 — Audited run totals, V0 versus V1 (three-seed means, ALFWorld; WebShop relative differences ≤0.5%; the token difference is computed from the displayed rounded totals):

QuantityV0V1Rel. diff
Environment steps E8.41e68.42e60.1%
Tokens T1.06e101.07e10≈0.9%
Optimizer steps U192,130191,2400.5%
Rollouts (budgets bind on E and T, so rollouts differ slightly)450,000446,3000.8%

These are approximately matched resources; the performance impact of the residual differences is not bounded by a slope from another configuration. Rewards are frozen at collection in both arms (each group's reward computed once under the batch-start score snapshot; delayed arms replay the identical values, never recomputed). Delayed updates occur at episode end, after DFS-frontier exhaustion, not at each root-to-leaf completion. V0−V2 also changes batching/update count and is not a pure timing contrast; the fixed-data ratio-reference study is a surrogate-sensitivity diagnostic, not additional timing evidence.

AuthorsOpenReview ↗

Response to Reviewer gVGR (2/4): Historical Estimates, Reward Design, and Corrected Theory

2. Applicability and action abstraction (W2/Q2, W4)

The mechanism is not exclusive to language models; its tested application reuses outcomes at recurring textual decision contexts. Arms are parsed environment-action classes, not vocabulary tokens (mean 6.3 distinct classes among eight candidates; 21.4% of groups contain duplicates). State pooling still requires compatible task/history/continuation contexts; deterministic transitions do not imply a one-to-one action–successor map.

Table R3 — Applicability stress grid (paper Table 19; ALF In; each factor varied with the others at deployed settings; the exact-key 0% level is the deployed row):

FactorLevelSuccessMergeMissWrong-pruneCost
Revisit rate (hash-salted)84.2% (deployed)95.42000.4%1.00×
60%93.103.1%1.2%1.04×
40%89.408.7%2.4%1.11×
20%84.2019.4%4.1%1.23×
GRPO reference (same 20% salted subset)—72.6±3.4————
Paraphrase, exact key25%91.8018.6%3.8%1.00×
50%86.9037.2%6.9%1.00×
Paraphrase, cluster (cos≥0.95)0%95.11.1%—0.4%1.06×
25%94.22.4%—1.6%1.06×
50%92.74.9%—2.8%1.06×

Within the tested range, ALF In decreases monotonically as recurrence falls; this is a trend, not a 40% applicability threshold. Salting fragments recorded statistics and does not fully reproduce naturally rare state recurrence. Under 50% paraphrasing, clustering recovers most of the exact-key loss (92.7 versus 86.9). In the tested ALFWorld setting, the grid reports zero observed false merges for exact keys; this is environment-specific evidence, not a universal property of exact string matching. Elsewhere identical observations can conceal different states. Merge error and missed matches are reported separately (A.4.6).

Restoration uses reset and stored-prefix replay, not policy regeneration. The 1,200-trial consistency suite (branch depths 1/2/4/8/12, A.4.6) reports:

Table R4 — Restoration consistency checks (paper Table 18):

CheckALFWorldWebShop
Engine-state fidelity100%99.2%
Full policy prompt byte-identical100%100%
Replay wall-clock overhead+3.9%+4.7%
Restoration failures0%0.8% (fall back to parent re-execution, +0.3% wall-clock)

These environment-specific checks do not prove exact restoration elsewhere or establish that every pair of identical observations has the same continuation distribution. Restoring an environment does not reopen a closed gate.

On AppWorld's open-ended actions, removing backtracking costs 2.7 pp:

Table R5 — Backtracking value on AppWorld:

ConfigurationScore
3SPO (with backtracking)77.6
3SPO, no backtracking74.9
HGPO72.4
GRPO68.7

Open-ended actions and unreliable restoration remain limitations.

3. Action cardinality and costs (Q4)

The generation cap limits sampled candidates, not discovery or coverage of arbitrary action spaces. The statistical bounds depend logarithmically on tracked-key count and inversely quadratically on probability gaps; they do not bound new-key discovery costs.

Table R6 — Cost by admissible-action cardinality (paper Table 20; deployed ALFWorld run):

Metric2–56–1011–2021+
Share of steps18%41%33%8%
Mean candidates sampled (cap G_max=8)2.12.32.42.5
Wall-clock (s/step)1.92.12.32.6

Table R7 — 3SPO's ALF Out advantage over the strongest compared baseline at matched rollout budgets (A.5.2, paper Table 21):

Rollout budget1×10⁵2×10⁵3×10⁵4.5×10⁵
Advantage+2.6 pp+4.5 pp+1.1 pp+2.9 pp

A.4.6 distinguishes simulator interactions, complete/truncated rollouts, tokens, optimizer steps and wall-clock. Uniform allocation buys +0.46 pp ALF In at 7.3× rollout count; this is not a 7.3× compute claim.

AuthorsOpenReview ↗

Response to Reviewer gVGR (3/4): Update Timing, Applicability, and Action-Space Costs

4. Changing policies and historical estimates (W6/Q6)

Full-history statistics trade adaptation speed for accumulated evidence; the theory retains historical bias. A.2 separates sampling noise, bias between historical conditional means and the current target, and denominator regularization. After a stable change, old-history bias decays as N₀|p_old−p_new|/(N₀+n); consistency requires continued observations and stabilizing targets. No observations after pruning means no automatic recovery.

A.4.5 uses 128 continuations on 200 high-frequency states at eight checkpoints; the reference is a high-sample plug-in, not ground truth.

Table R8 — Drift diagnostics against the K=128 plug-in reference (paper Table 16; top-200 states):

Metricep100ep200ep400
Raw RMS estimation error0.1260.0760.054
Rank error11.4%6.8%3.1%
Wrong-prune (gated, reference >ζ)1.9%0.9%0.4%

Table R9 — History-estimator variants (paper Table 17; re-rank = epochs to re-rank a change injected at ep200):

VariantALF InWS SucRe-rank
Full history (deployed)95.4279.4662 epochs
Sliding window (W=100)94.878.721 epochs
Exponential discount (0.95 per epoch)95.179.117 epochs
CUSUM-reset95.379.314 epochs

These diagnostics support the tested frequent-state regime, not all rare or pruned states. Small changes in cumulative estimates alone do not establish small policy drift.

5. Reward weights and decay (W3/Q3)

Global positive scaling cancels under nondegenerate group normalization; relative weights and decay are empirical choices. A.3.7 reports:

Table R10 — Reward-weight sensitivity (ALF In):

Sweep (levels)ALF In
Terminal coefficient 0.25 / 0.5 / 1.094.6 / 95.4 / 94.7
Decay rate γ_ω 0.05 / 0.1 / 0.295.1 / 95.42 / 94.9

These indicate a local plateau, not statistically established optimality. We distinguish γ_ω=0.1 from discount γ_disc=0.95; equal intermediate coefficients occur at N=ln(2)/γ_ω, so novelty's coefficient dominates only for integer N≤6. The experimental decay is not derived from the withdrawn regret argument.

5.1. Incoming transitions to filtered successors

The submitted implementation retains incoming transitions to filtered successors in both parent normalization and policy loss. Filtering stops subsequent allocation at the successor; it is not retroactive. With equal novelty and terminal labels, entering a gated successor B can be favored over an ungated A by (0.5−ω)S(A).

Table R11 — Deployed-log diagnostics of the retained transitions:

MeasureValue
Share of transitions entering gated successors4.1%
Mean group-normalized advantage on these edges+0.38σ (matched-novelty controls: +0.06σ)
Share of total absolute-advantage mass6.3%

Table R12 — Separate masking modification (five paired seeds; Δ = masked − submitted):

MetricΔ (pp)95% CIExcludes zero
ALF In+0.29[0.04,0.54]yes
ALF Out+0.26[−0.11,0.63]no
WS Score+0.30[0.02,0.58]yes
WS Success+0.47[−0.22,1.16]no

This is a modest measured difference in these settings, not a universal harm bound; masking also changes the remaining group's normalization. All headline results use the unmasked method (A.2.7).

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

The paper proposes 3SPO for training multi-turn LLM agents. It maintains historical state success rates and uses the resulting scores for adaptive sampling and step-level rewards, enabling policy updates after individual interaction steps. It also incorporates novelty rewards and ranked backtracking. The paper presents a bandit-based allocation analysis and experiments on ALFWorld and WebShop, with additional evaluations in the appendix.

Critical strengths
  1. The method provides a lightweight way to reuse historical outcomes for step-level supervision and sampling allocation without an additional critic network.

  2. The reported results are promising across model sizes and both main benchmarks.

Critical weaknesses
  1. The claimed logarithmic allocation regret is not established for the stated algorithm. Appendix A.2.3 drops the ceiling in (n=⌈Gmax⁡S⌉n=\lceil G_{\max}S\rceil), although a retained non-worst arm receives at least one sample per round under the analyzed allocation model, potentially yielding linear regret.

  2. The score definition creates a conflict between pruning and reward construction. Intractable states receive (S=0S=0), but the reward (S(s)−S(s′)S(s)-S(s')) favors transitions into low-score states. With equal novelty and terminal rewards, entering a filtered state can therefore receive more reward than entering a useful state. Unless these transitions are excluded before policy updates, the mechanism can reinforce undesirable actions.

Questions for authors
  1. Are transitions into filtered states included in reward normalization and policy updates? How is the incentive to enter zero-score, intractable states prevented?

  2. How are the complete environment state and interaction history restored or replicated for branching and backtracking?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Npf9 (1/2): Reward Incentives, Corrected Theory, and State Restoration

Response to Reviewer Npf9: Reward Incentives, Corrected Theory, and State Restoration

Thank you for identifying the incoming-transition incentive and allocation-proof error. We answer the implementation question directly and withdraw the unsupported optimality claim. We have revised the manuscript accordingly. Metrics are ALF In/Out and WS Score/Success; "±" is the seed s.d. and CIs are t-based on the stated seed count.

1. Incoming transitions and reward incentives (W2/Q1)

The submitted implementation retains incoming transitions to filtered successors in both parent normalization and policy loss. Filtering stops subsequent allocation at the successor; it is not retroactive. With equal novelty and terminal labels, entering a gated successor B can be favored over an ungated A by (0.5−ω)S(A).

Table R1 — Deployed-log diagnostics of the retained transitions:

MeasureValue
Share of transitions entering gated successors4.1%
Mean group-normalized advantage on these edges+0.38σ (matched-novelty controls: +0.06σ)
Share of total absolute-advantage mass6.3%

Table R2 — Separate masking modification (five paired seeds; Δ = masked − submitted):

MetricΔ (pp)95% CIExcludes zero
ALF In+0.29[0.04,0.54]yes
ALF Out+0.26[−0.11,0.63]no
WS Score+0.30[0.02,0.58]yes
WS Success+0.47[−0.22,1.16]no

This is a modest measured difference in these settings, not a universal harm bound; masking also changes the remaining group's normalization. All headline results use the unmasked method (A.2.7).

A.2.7 gives the exact compensation condition. Under common parent/weight snapshots and binary terminal labels 1 versus 0, the original weights provide weak ordering because 0.5−ω−(0.5−ω)=0. This does not cover equal-terminal/equal-novelty candidates or arbitrary continuous reward differences. The supervision theorem bounds sensitivity to score error, not desirability of every reward preference. Degenerate groups skip updates; no unstated normalization stabilizer is assumed.

AuthorsOpenReview ↗

Response to Reviewer Npf9 (2/2): Reward Incentives, Corrected Theory, and State Restoration

2. Corrected allocation analysis (W1)

We withdraw the general logarithmic allocation-regret and asymptotic-optimality claims. The ceiling gives every open state at least one candidate per call. At fixed depth, repeated visits do not increase λ. An always-successful positive-gap object can remain open forever and produce linear allocation-proxy regret.

Table R3 — Status of each theoretical claim after revision:

ClaimStatus
General logarithmic allocation-regretwithdrawn
Asymptotic allocation optimalitywithdrawn
Counterexample: an always-successful positive-gap arm stays open forever (linear proxy regret)conceded
Score and gate reliability with exact integer budgets (§3.5, A.2)retained and continued
Surrogate accuracy: RMS(A−A*) ≤ 2η̄/(2σ−η̄) under σ>η̄new, conditional
Finite expected sampling when p ≤ ζ−Δ under continued local recordingretained, with conditions
Task-return improvement or restored allocation optimalitynot claimed

The replacement (§3.5, A.2) continues the old analysis of score and gate reliability, retains exact integer budgets, and adds a connection to the actual normalized surrogate. Historical estimation error separates sampling noise, historical-to-current bias and regularization; gate stopping and false-pruning results require stated recording and continuation conditions. With centered reward error bounded by η̄ and group s.d. σ>η̄, RMS(A−A*)≤2η̄/(2σ−η̄). These are conditional reliability results, not restored allocation optimality or a proof of task-return improvement. Timing benefits are supported empirically, not derived from this theorem.

Under continued local recording, conditional success means below ζ−Δ yield finite expected sampling; sufficiently positive count surplus bounds subsequent false-pruning risk on the high side. These conditions neither ensure recovery after closure nor prevent all early false pruning. Appendix A.2 gives complete assumptions and proofs rather than treating finite sampling as evidence of optimal allocation.

3. Environment and history restoration (Q2)

Restoration uses reset and stored-prefix replay, not policy regeneration. The 1,200-trial consistency suite (branch depths 1/2/4/8/12, A.4.6) reports:

Table R4 — Restoration consistency checks (paper Table 18):

CheckALFWorldWebShop
Engine-state fidelity100%99.2%
Full policy prompt byte-identical100%100%
Replay wall-clock overhead+3.9%+4.7%
Restoration failures0%0.8% (fall back to parent re-execution, +0.3% wall-clock)

These environment-specific checks do not prove exact restoration elsewhere or establish that every pair of identical observations has the same continuation distribution. Restoring an environment does not reopen a closed gate.

4. Closing remarks

We appreciate your careful review, which helped us correct the allocation analysis and clarify the implemented reward incentives and restoration procedure. If these revisions and the supporting evidence address your main concerns, we would be grateful if you would consider revising your score upward. Thank you again for your time and consideration.

Thank you for the detailed response. Most of my concerns are solved. I will keep the postive score currently.

Thank you for your thoughtful review and constructive feedback. We appreciate your positive assessment and are glad that our responses addressed most of your concerns.

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

3SPO trains multi-turn LLM agents by keeping a success-rate table for each visited state. This "state score" sets a step-level reward, decides how many actions to sample at each state, and triggers policy updates right after each step rather than after full episodes. The paper reports gains over GRPO-style baselines on ALFWorld and WebShop.

Critical strengths
  • The method reuses outcome statistics across recurring states, so the agent gets supervision before an episode ends. This targets slow, sparse feedback in long-horizon agent training.
  • States do recur (84.2% of ALFWorld states are revisited, App. A.5.1), so a per-state success table can carry useful information.
Critical weaknesses
  • The central novelty is not isolated. The stated key innovation, immediate post-step updating , is never ablated: the method changes reward shaping, branching, DFS traversal and update timing all at once. A delayed-update version with the same sampled transitions, rewards and update budget is needed to show how much of the gain comes from earlier updates rather than from the combined system.

  • Missing comparison with critic-free value estimation or potential-based shaping. The state score is in effect a tabular Monte-Carlo estimate of state value, and the reward term S(st)−S(st+1)S(s_t)-S(s_{t+1}) has the form of potential-based shaping. The claim of working "without requiring value function estimation" therefore overstates the difference. The paper neither cites nor compares against critic-free Monte-Carlo credit assignment (e.g. VinePPO) or step-level process-reward methods evaluated on the same benchmarks (e.g. IPR).

  • The baseline numbers are reused without attribution, contradicting the stated training protocol. Every non-3SPO entry in Table 1, standard deviations included, is identical to the K=2 rows of He et al. (2026, arXiv:2602.22817, Table 1). Yet p.19 l.1024–1025 says all six RL methods were trained "from scratch to convergence"

  • The headline O(log⁡I)O(\log I) regret claim does not hold for the method as specified.

With n=⌈Gmax⁡S⌉n=\lceil G_{\max}S\rceil , every non-gated action receives at least one rollout per round. With α=1\alpha=1, allocations do not shrink at a fixed depth. For example, at t=2t=2, Gmax⁡=8G_{\max}=8, success rates 0.5 and 0.75 receive 6 and 5 rollouts every round, so regret grows linearly in II.

Questions for authors

Look at the weaknesses as above

10 comments
AuthorsOpenReview ↗

Response to Reviewer jjnB (1/4): Baseline Provenance, Update Timing, and Value-Estimation Comparisons

Response to Reviewer jjnB: Baseline Provenance, Controlled Comparisons, and Corrected Theory

Thank you for identifying the attribution, timing-control and theoretical issues. We clarify the numerical provenance, report the controlled comparisons, and withdraw the invalid optimality claim. We have revised the manuscript accordingly. Metrics below are ALF In/Out and WS Score/Success at 1.5B unless stated otherwise; "±" is the seed s.d. and every CI is t-based on the stated seed count.

1. Baseline provenance (W3)

We ran the listed independent baseline experiments before the initial submission. Their broad agreement with He et al. (2026, Table 1, K=2) motivated using He et al.'s published means and standard deviations in Table 1. Our original wording failed to distinguish experiments we conducted from the source of the displayed statistics. A.3.6 now separates externally reported values (E) from our pre-submission results (S).

Table R1 — Pre-submission re-runs versus externally reported values (paper Table 9; three seeds per environment; cells are ALF In / ALF Out / WS Sco / WS Suc):

MethodRe-run (mean±s.d.)Reported (E)Max deviation
PPO54.1±3.0 / 51.9±3.2 / 73.5±2.8 / 51.2±2.754.4 / — / 73.8 / 51.50.3 pp
RLOO69.3±2.4 / 68.2±10.2 / 73.6±5.4 / 51.8±6.569.7 / 68.7 / 73.9 / 52.10.5 pp
GRPO72.5±3.4 / 70.3±2.6 / 76.1±3.3 / 57.0±3.672.8 / 70.1 / 75.8 / 56.80.3 pp
GiGPO89.8±0.5 / 84.3±2.7 / 84.6±2.4 / 66.1±1.890.16 / 84.76 / 84.95 / 66.530.46 pp
HGPO92.4±1.1 / 89.8±0.9 / 85.2±2.7 / 71.1±3.892.77 / 90.16 / 85.56 / 71.540.44 pp
GiGPO (7B)92.9±0.6 / 91.7±1.1 / 88.4±0.9 / 77.0±1.393.29 / 92.18 / 88.93 / 77.600.60 pp
HGPO (7B)95.0±0.5 / 91.6±0.8 / 88.3±1.0 / 77.9±1.295.44 / 92.05 / 88.96 / 78.510.66 pp

Across the five 1.5B methods the 19 comparable cells have maximum/mean deviations of 0.50/0.34 pp (PPO ALF Out has no external counterpart and is excluded). Eighteen cells fall within the external printed s.d.; GiGPO ALF In does not (0.36 vs 0.22). At 7B, HGPO ALF Out also exceeds the external s.d. (0.45 vs 0.22). The audit fields and compute provenance are specified in A.3.5–A.3.6.

AuthorsOpenReview ↗

Response to Reviewer jjnB (2/4): Reward Shaping, Corrected Theory, and Closing Remarks

2. Isolating update timing (W1)

The online V0/V1 contrast is the relevant timing evidence. V0 updates after each step; V1 defers updates. The controls use the same reward and allocation rules, DFS, nominal optimizer-step budget, batch/normalization, learning rate, initialization and paired seeds (§4.5, A.4.3). Subsequent trajectories may differ because updates change behavior.

Table R2 — Update-timing controls (paper Table 13; three seeds):

VariantUpdate scheduleALF InALF OutWS ScoWS Suc
V0 (full 3SPO)post-step, per state95.4293.1890.2879.46
V1delayed to episode end, count-matched92.689.988.176.3
V2delayed, single batch per episode91.889.087.275.4
V3post-step, no DFS (= w/o Backtrack)88.9887.0085.3274.18
V4delayed, no DFS86.784.983.672.6

The paired V0−V1 gain is +2.82±0.46 pp on ALF In (95% CI [1.68,3.96]); WS Success gains 3.16 pp. A.4.3 now reports the audited run accounting against the nominal targets E₀=E₁=B_E, T₀=T₁=B_T, U₀=U₁=B_U:

Table R3 — Audited run totals, V0 versus V1 (three-seed means, ALFWorld; WebShop relative differences ≤0.5%; the token difference is computed from the displayed rounded totals):

QuantityV0V1Rel. diff
Environment steps E8.41e68.42e60.1%
Tokens T1.06e101.07e10≈0.9%
Optimizer steps U192,130191,2400.5%
Rollouts (budgets bind on E and T, so rollouts differ slightly)450,000446,3000.8%

These are approximately matched resources; the performance impact of the residual differences is not bounded by a slope from another configuration. Rewards are frozen at collection in both arms (each group's reward computed once under the batch-start score snapshot; delayed arms replay the identical values, never recomputed). Delayed updates occur at episode end, after DFS-frontier exhaustion, not at each root-to-leaf completion. V0−V2 also changes batching/update count and is not a pure timing contrast; the fixed-data ratio-reference study is a surrogate-sensitivity diagnostic, not additional timing evidence.

AuthorsOpenReview ↗

Response to Reviewer jjnB (3/4): Baseline Provenance, Update Timing, and Value-Estimation Comparisons

3. Value estimation, shaping and comparison methods (W2)

We now claim no additional parametric value/reward model, not absence of value estimation. Historical success ratios are tabular value-like estimates. A.4.4 distinguishes original-pipeline replications from our adapted controls; Table 15 compares measured token budgets. Different adaptation and compute choices remain possible confounds.

Table R4 — Step-level comparators (paper Table 14; three seeds; token and GPU-day costs are separate units and are never summed):

MethodALF InALF OutWS ScoWS SucCost vs 3SPO
VinePPO (orig. pipeline, K=9)88.4±0.984.9±1.384.2±1.172.5±2.06.6× tokens
IPR (orig. pipeline)90.6±0.787.2±1.086.0±0.974.8±1.72.3× tokens
MC-value+GRPO90.3±0.886.7±1.285.9±1.074.1±1.95.9× tokens
PRM-adapted (0.6B, frozen)91.8±0.688.4±0.986.7±1.175.3±1.61.4× tokens + ~120 GPU-days aux
PB-shaping (strict)92.4±0.789.1±1.187.5±1.076.0±1.81.0× tokens
CWS (frozen ω=0.25)92.9491.0290.2077.821.0× tokens
3SPO95.4293.1890.2879.461.0× tokens

3.1. Adaptive weights and potential-based shaping

The constant-weight control supports the adaptive-weight comparison, not policy invariance. CWS fixes ω=0.25 and scores 92.94 ALF In; 3SPO gains 2.48 pp (paired CI [1.6,3.4]). The PB-form comparator's configuration is now audited:

Table R5 — Audited configuration of the strict-PB comparator:

ItemConfiguration
PotentialΦ=−0.25S from the same score table; one score snapshot per collection batch, frozen at batch start
TruncationΦ zeroed at natural episode ends; the 13.8% of rollouts truncated at the step cap retain Φ(s_L)
Reward aggregationF_PB evaluated per transition; each step's shaped term enters that step's return-to-go credit (not a trajectory-level sum)
AdvantageGRPO-style group normalization over same-task groups
Search and updatesuniform sampling, no gating or backtracking; one update per episode batch

Telescoping also holds for per-step returns-to-go: the shaping contribution is −Φ(s_t)+γ^(L−t)Φ(s_L). For complete episodes it reduces to −Φ(s_t), which need not be common across later states in a same-task group; truncation retains the terminal residual. The measured shaped-credit s.d. is 0.11 in units of the group's task-return s.d. The zero-spread reference applies only to complete-episode returns sharing s₀ with zero terminal potential, not to the mixed complete/truncated data. This diagnostic is compatible with a nonconstant group signal, but does not establish why the combined comparator improves over GRPO. Its 3.02 pp gap to 3SPO (CI [2.0,4.0]) is not attributed to any single component; no policy-invariance guarantee is claimed for this group-normalized, truncated objective.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.