- 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
- 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.
- 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.
- 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.
- 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.
- Appendix A.2.3 replaces with a continuous allocation, treating rounding as an discrepancy. Such discrepancies can accumulate linearly across rounds. The proof needs to account explicitly for integer allocation and filtering.
- 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
- Can you compare post-step and post-trajectory updates while holding rewards, candidate allocation, backtracking, and resource budgets fixed?
- 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?
- Please justify the relative intermediate/terminal reward weights and reconcile the theoretical decay schedule with the experimental setting.
- Please state the dependence on action cardinality and probability gaps, and clarify the computational costs as the action space grows.
- Under what conditions does filtering prevent persistent minimum-one allocation from producing linear regret?
- 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
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):
| Factor | Level | Success | Merge | Miss | Wrong-prune | Cost |
|---|---|---|---|---|---|---|
| Revisit rate (hash-salted) | 84.2% (deployed) | 95.42 | 0 | 0 | 0.4% | 1.00× |
| 60% | 93.1 | 0 | 3.1% | 1.2% | 1.04× | |
| 40% | 89.4 | 0 | 8.7% | 2.4% | 1.11× | |
| 20% | 84.2 | 0 | 19.4% | 4.1% | 1.23× | |
| GRPO reference (same 20% salted subset) | — | 72.6±3.4 | — | — | — | — |
| Paraphrase, exact key | 25% | 91.8 | 0 | 18.6% | 3.8% | 1.00× |
| 50% | 86.9 | 0 | 37.2% | 6.9% | 1.00× | |
| Paraphrase, cluster (cos≥0.95) | 0% | 95.1 | 1.1% | — | 0.4% | 1.06× |
| 25% | 94.2 | 2.4% | — | 1.6% | 1.06× | |
| 50% | 92.7 | 4.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):
| Check | ALFWorld | WebShop |
|---|---|---|
| Engine-state fidelity | 100% | 99.2% |
| Full policy prompt byte-identical | 100% | 100% |
| Replay wall-clock overhead | +3.9% | +4.7% |
| Restoration failures | 0% | 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:
| Configuration | Score |
|---|---|
| 3SPO (with backtracking) | 77.6 |
| 3SPO, no backtracking | 74.9 |
| HGPO | 72.4 |
| GRPO | 68.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):
| Metric | 2–5 | 6–10 | 11–20 | 21+ |
|---|---|---|---|---|
| Share of steps | 18% | 41% | 33% | 8% |
| Mean candidates sampled (cap G_max=8) | 2.1 | 2.3 | 2.4 | 2.5 |
| Wall-clock (s/step) | 1.9 | 2.1 | 2.3 | 2.6 |
Table R7 — 3SPO's ALF Out advantage over the strongest compared baseline at matched rollout budgets (A.5.2, paper Table 21):
| Rollout budget | 1×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.
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):
| Metric | ep100 | ep200 | ep400 |
|---|---|---|---|
| Raw RMS estimation error | 0.126 | 0.076 | 0.054 |
| Rank error | 11.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):
| Variant | ALF In | WS Suc | Re-rank |
|---|---|---|---|
| Full history (deployed) | 95.42 | 79.46 | 62 epochs |
| Sliding window (W=100) | 94.8 | 78.7 | 21 epochs |
| Exponential discount (0.95 per epoch) | 95.1 | 79.1 | 17 epochs |
| CUSUM-reset | 95.3 | 79.3 | 14 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.0 | 94.6 / 95.4 / 94.7 |
| Decay rate γ_ω 0.05 / 0.1 / 0.2 | 95.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:
| Measure | Value |
|---|---|
| Share of transitions entering gated successors | 4.1% |
| Mean group-normalized advantage on these edges | +0.38σ (matched-novelty controls: +0.06σ) |
| Share of total absolute-advantage mass | 6.3% |
Table R12 — Separate masking modification (five paired seeds; Δ = masked − submitted):
| Metric | Δ (pp) | 95% CI | Excludes 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).
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):
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):
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.