acceptodds
Under review as a conference paper at ICLR 2027

Policy-Relative Frontier Learning for Self-Evolving Language Models

Abstract

As language agents are deployed across increasingly diverse tasks, self-evolution offers a practical way to adapt them through their own experience under limited budgets and strict data privacy requirements. Yet many real-world domains provide only outcome feedback, leaving the policy's current capability bottlenecks unclear. Each round of self-evolution therefore raises a central question: what should the policy learn next, and how far should supervision extend? We propose **Policy-Relative Frontier Learning**, a framework that uses progress differences among the policy's own rollouts to determine the boundaries and granularity of supervision. Using the shortest successful rollout as a reference, we identify the furthest shared progress of each failed rollout as its relative frontier. Each failed rollout learns from its own frontier to the next frontier in the group, or to task completion if no further frontier exists. By focusing on local progress, this design recognizes that even a rollout that ultimately fails can contain useful segments that help another attempt cross its relative frontier. We therefore also select segments from failed rollouts, expanding supervision beyond successful trajectories. We fine-tune the policy on the selected segments and reconstruct learning targets from fresh experience after each update. supervision from failed rollouts. Experiments on ALFWorld and WebShop show that our method outperforms baselines with fewer rounds of evolution. Ablations reveal that the effectiveness of fixed supervision granularity varies across tasks, highlighting the value of policy-relative learning intervals derived from the policy’s own progress. Code is available at https://anonymous.4open.science/r/relative-frontier-evolve-657F/.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
Self-evolve, language model, agent

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

This paper treats different rollouts by the same agent as a set of mutually instructive experiences. It uses progress differences among failed trajectories to determine the learning frontier, then selects local demonstrations from successful or failed attempts that cross the next frontier, driving multi-round self-evolution through more targeted SFT.

Critical strengths
  1. Where to learn and how far to learn are distinct questions. Rather than merely changing the optimization objective, the paper focuses on training-data construction, which is practically relevant for interactive agent self-training.

  2. It requires neither an additional trained PRM nor a stronger teacher providing revised trajectories each round. The complexity lies mainly in offline state matching and segment selection.

  3. The experiments compare full successful trajectories, next-action supervision, full continuation, successful-donor-only selection, and removal of position weighting.

Critical weaknesses

W1. The relative frontier may not reflect actual capability bottlenecks. The method requires matching each reference state in order without skipping, so an early mismatch prevents later, closer-to-success states from counting as progress. The frontier thus measures ordered path consistency with one reference rather than distance to task completion. This affects the core learning signal, not just future extensions.

Please compare

  • single vs. multiple references
  • strict vs. skip-allowed matching
  • ordered-path vs. task-relevant state progress

and report sensitivity to reference choice.

W2. The Agent-R baseline omits its core mechanisms (Appendix A.2). On ALFWorld, Agent-R is implemented by collecting successful MCTS paths as fine-tuning data. However, Agent-R's key design involves the actor selecting revision points, constructing revised trajectories that incorporate failure experience, adding revision signals, and learning to recover from errors. Training only on successful MCTS paths DOES NOE adequately represent Agent-R.

Please implement the full method or clarify this deviation when interpreting the comparison.

W3. The closest strong baselines are missing (§5.1). The main experiments lack of

  • GiGPO
  • SALT
  • full UI-Voyager-style fork correction
  • milestone-based RL methods.

The paper should include at least one credible modern step-level RL baseline and one faithful matched-state correction baseline. The next-action ablation is not equivalent to full UI-Voyager, as it uses the paper's own frontier starting points rather than UI-Voyager's fork detection and transition alignment. The current results thus show gains over these specific trajectory-level schemes, but do not establish that the local learning mechanism outperforms the most relevant prior methods.

W4. The gain from failed donors conflates coverage and segment quality. Relative to successful-donor-only selection, the full method improves by 3.36 points on ALFWorld and 3.60 points on WebShop. This shows that allowing failed donors makes the full scheme more effective, but not that segments from failed donors are of higher quality than those from successful donors. Including failed donors may also

  • increase learner coverage
  • the number of usable samples
  • path diversity
  • the proportion of short segments.

Please compare the two settings with matched coverage, sample count, and segment length.

W5. What is the precise definition of state matching? When a donor segment is replayed from the learner's state, what fraction of replays reach the target milestone?

W6. The reported statistics appear inconsistent with the stated evaluation protocol. Table A.3 specifies four decoding seeds over 134 ALFWorld tasks, but ReSTEM’s overall result of 96.64 ± 0.53 in Table 1 cannot arise from four per-seed success rates under either the conventional sample or population standard deviation. Instead, it matches the sample statistics of two runs with 129 and 130 successes.

Please clarify the actual number of evaluation seeds, provide per-seed results, and reconcile the tables. Moreover, decoding-only repetitions do not quantify training variability, so independent training runs are needed to substantiate robustness.

Questions for authors

See Weakness

2 comments
AuthorsOpenReview ↗

Response to Reviewer 2Wp1 - 1

We thank the reviewer for recognizing the practical value of our training-data construction approach and the distinction between where and how far to learn. We also appreciate your recognition of the design without an additional trained PRM or stronger teacher, and of the ablation comparisons. Thank you for your time, effort, and valuable questions. Below, we address your concerns and present additional experiments and analyses.



2Wp1-W1 Frontier definition and reference choice

Reply to 2Wp1-W1

The relative frontier is the last reference state a failed rollout matches in order. It marks the start of that rollout’s learning interval. We use the shortest successful rollout as our default reference, although a single reference can underestimate progress along another valid path, as discussed in §6. Longer successful rollouts can include detours. If a location visited on a detour becomes a milestone, the learner may be trained to repeat that detour.

We evaluated the multi-reference variant on ALFWorld and WebShop. The other two proposals, which are allowing reference states to be skipped and measuring progress through task-relevant states, typically require more detailed prior knowledge of the dataset and task to determine which states can be skipped or which changes represent meaningful progress. They therefore introduce more environment-specific rules and manual intervention. Our method aims to provide a general framework across environments, within which these proposals can serve as environment-specific extensions and refinements.

Using multiple references gave some failed rollouts a later learning start, but final success rates did not improve in either environment after retraining (Table 2Wp1-W1). Each successful rollout provided its own milestone sequence. For each failed rollout, we chose the reference whose last match came latest in the failed rollout itself. We kept the prefix through that match and used the next milestone on the chosen reference as the target. Final success rates were close on WebShop (70.90% with one reference and 69.60% with multiple references). On ALFWorld, the single-reference run scored 8.21 percentage points higher (98.51% versus 90.30%). In some cases, the new target was simply a location visited during search. Even when the target stayed the same, the selected segment could include more detours.

Table 2Wp1-W1. Effect of reference choice on learning intervals and final success rates

EnvironmentLater learning startLater start and changed next targetFinal success, single referenceFinal success, multiple references
WebShop R441/231 (17.7%)13/231 (5.6%)70.90%69.60%
ALFWorld R340/187 (21.4%)7/187 (3.7%)98.51%90.30%


2Wp1-W2 Scope of the Agent-R implementation

Reply to 2Wp1-W2

We agree that Agent-R on ALFWorld is a search-only adaptation and does not represent the full method. Agent-R’s revision procedure, tested on WebShop, does not transfer directly to our ALFWorld setup because actions in the failed prefix can change the object states needed to execute the successful continuation. In both environments, we excluded ShareGPT conversational data to keep supervision derived from each method’s own rollouts. However, our main conclusions remain supported. On WebShop, Agent-R retains MCTS search, policy-selected revision points, revision signals, and the concatenation of failed and successful trajectories. PRFL still outperforms it, achieving 71.00% versus 58.70% success. Our ALFWorld conclusion also does not depend on Agent-R: the strongest baseline there is ReST-EM at 96.64%, compared with 97.76% for PRFL.

We omitted revision trajectories on ALFWorld for environment compatibility. Intermediate states cannot be saved directly and must be restored by replaying actions from the initial state. Agent-R’s revision trajectories concatenate a failed branch’s prefix with a successful branch’s continuation. In ALFWorld, actions such as picking up, placing, or heating objects persistently change the environment, so observations in the concatenated trajectory can become inconsistent with the actual state. To avoid training on such inconsistencies, we used only successful paths actually executed during search.

We will label this result as an adaptation in Table 1, document the mechanisms retained and omitted in each environment in Appendix A.2, and polish the experimental analysis.

AuthorsOpenReview ↗

Response to Reviewer 2Wp1 - 2

2Wp1-W3 Missing Step-Level RL and Full UI-Voyager-Style Baselines

Reply to 2Wp1-W3

Our main comparisons focus on SFT baselines to evaluate how the choice of training content affects self-evolution. RL also changes credit assignment and policy optimization. Following your suggestion, we evaluated GiGPO, which uses its own rollouts and environment feedback without external training data or process supervision.

We adapted GiGPO from full-parameter training to LoRA, using the same Qwen2.5-7B-Instruct base model and rollout budgets as our method, with 4,800 on ALFWorld and 8,000 on WebShop. The ALFWorld budget is one quarter of GiGPO's published 19,200 rollouts. We retained its native prompt and interaction history.

The original learning rate of 10−610^{-6} may not be optimal for LoRA. After an initial run at this rate, we tested 10−510^{-5}, 10−410^{-4}, and 2×10−42\times10^{-4} on ALFWorld and selected the best-performing rate, 10−410^{-4}, which we also used on WebShop. Our method achieved higher success on both benchmarks under these settings.

Table 2Wp1-W3. Success rates under matched training rollout budgets.

MethodALFWorldWebShop
GiGPO (LoRA)66.60% ± 2.477.15% ± 1.08
Our method97.76% ± 1.6171.00% ± 0.52

We have not yet included a full UI-Voyager comparison. Its original screenshot-based matching requires adaptation for our text environments, including fork detection and transition alignment. Our next-action ablation holds the PRFL frontier fixed and compares learning only the donor’s next action with learning the segment up to the next milestone. This tests supervision scope and does not reproduce the full UI-Voyager pipeline.



2Wp1-W4 What adding failed donors establishes

Reply to 2Wp1-W4

We do not claim that failed donors provide higher-quality segments than successful donors in general. We include them to give each learner more routes to the same milestone. The benefits you mentioned, including a wider choice of paths and the possibility of covering more learners, are precisely why we expand the donor pool.

Following your suggestion, we compared training coverage across all rounds (Table 2Wp1-W4). Relative to using successful donors alone, coverage was slightly lower on ALFWorld (89.2% vs. 90.2%) and higher on WebShop (76.6% vs. 69.9%). The higher coverage on WebShop illustrates one intended benefit of including failed donors: a larger share of eligible learners contributed training examples.

Table 2Wp1-W4. Training coverage in the donor-source ablation. The numerator counts failed learners used for training, and the denominator counts eligible failed learners in the corresponding run.

EnvironmentSuccessful donors onlyOur method
ALFWorld716/794 (90.2%)696/780 (89.2%)
WebShop1,306/1,869 (69.9%)1,316/1,718 (76.6%)


2Wp1-W5 Exact state matching and replay from the learner’s state

Reply to 2Wp1-W5

1. Replay success. Donor segments reached the next milestone in nearly every case when replayed from the learner’s state. On ALFWorld, 780/780 selected segments (100%) reached their target in post-hoc replay. On WebShop, 1,449/1,459 replays (99.31%) reached their target among attempts that began executing donor actions from the restored learner state. We count a replay as successful if the state after the final donor action matches the target milestone or, for a terminal target, if the environment reports success.

2. State matching.

  • ALFWorld. Two states match when their complete simulator fact sets are identical after we normalize names and sort the facts, preserving object identities and argument order.
  • WebShop. Page type, product ID, selected options, reward, and any recorded cart, purchase, or terminal fields must agree. If the next reference action clicks a product on a search page, the product must also be clickable in the matched state. In R1, its ID must also appear in the recorded observation.


2Wp1-W6 ReST-EM results on ALFWorld

Reply to 2Wp1-W6

Our review identified an inconsistency between the ReST-EM statistics in Table 1 and the evaluation protocol reported in Table A.3. Across two additional runs on ALFWorld, ReST-EM achieved 94.22% mean success (sample SD 1.85 percentage points). We will report this result in Table 1 and correct the corresponding protocol description in Table A.3.

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

This paper introduces PRFL framework, designed to facilitate the self-evolution of language agents in the absence of step-level annotations. The core idea is to leverage the progress disparities among rollouts generated by the agent’s own policy; by using the shortest successful trajectory within a group as a reference, the framework identifies a "relative frontier" for each unsuccessful trajectory. Based on this, PRFL defines a local learning interval and extracts compatible, shortest-possible segments—derived from either successful trajectories or unsuccessful ones that achieved greater progress—to serve as data for supervised fine-tuning, thereby enabling an iterative, adaptive curriculum learning process. The experiments were evaluated on the ALFWorld and WebShop benchmarks, with Qwen2.5-7B-Instruct as the base model.

Critical strengths

This paper exploits the local value of failure trajectories, overcoming the limitations of traditional methods that rely exclusively on complete, successful trajectories. By utilizing failure trajectories as "donors" to provide shorter, more direct segments of local actions, the approach effectively improves task success rates and reduces ineffective actions in both ALFWorld and WebShop.

Critical weaknesses
  1. The experimental section evaluates only the Qwen2.5-7B-Instruct model, which is quite dated. The study fails to verify the framework's generalizability to newer, more capable large language model (LLM) architectures; consequently, it is difficult to substantiate its universal applicability across various modern LLMs.

  2. ALFWorld and WebShop, as classic environments for evaluating intelligent agents, offer limited discriminative power. Furthermore, the paper only provides comparisons against a few baseline methods, failing to benchmark against more recent approaches—specifically the latest developments from 2025–2026. Consequently, it is difficult to clearly define the distinct advantages of this framework within the current landscape.

  3. Unable to determine the end-to-end efficiency of generating the training trajectories.

Questions for authors
  1. In the ALFWorld and WebShop experiments, what proportion of all sampled tasks were ultimately identified as "mixed-outcome task groups" and used to construct training data? Within these groups, how many failed trajectories were able to find a "donor segment" that met the compatibility criteria, thereby forming valid training samples? Furthermore, in the training set constructed during each round, what are the respective proportions of donor segments derived from failed trajectories versus successful trajectories?

  2. Since all-failure task groups are not used to construct training data, could the authors report the number or proportion of all-failure task groups in each round, as well as the ratio at which these tasks transition into mixed-outcome task groups in subsequent rounds? This information would help assess whether the proposed method can progressively cover tasks that the current policy was initially completely unable to solve.

  3. Could the authors provide further details on the specific state representations and matching rules used in ALFWorld and WebShop—including whether any manually designed logic related to the task structure is employed? To what extent do these state representations and matching criteria encode information regarding task stages, progress, or subgoals? This clarification is relevant to evaluating the authors' claim that the method "does not rely on manually defined task stages, subgoals, or additional step-level supervision."

  4. Many tasks may have multiple distinct yet equally valid paths to success; however, the current method uses a single shortest successful trajectory as a reference for sequential state matching. Could the authors clarify how a failed trajectory is handled if it makes progress along a valid path that differs from the reference trajectory—such that it cannot be sequentially matched against the states in the reference trajectory? Might this single-reference-trajectory design systematically underestimate valid progress made along alternative paths, thereby reducing the likelihood of such trajectories being selected as a "learner" or "donor"?

4 comments
AuthorsOpenReview ↗

Response to Reviewer aTz9 - 1

We thank the reviewer for recognizing PRFL’s use of valuable local segments from failed trajectories to improve task success and reduce ineffective actions through shorter, more direct demonstrations. We appreciate your time, effort, and valuable questions. Below, we address your concerns and present additional experiments and analyses.



aTz9-W1 Generalization to newer models

Reply to aTz9-W1

Following your suggestion, we prioritized PRFL and two baselines, Agent-R and All-task SFT, for the Qwen3-8B evaluation within the rebuttal timeline. Results show that our performance is stable across different backbones. We plan to complete the remaining baseline runs next week and add their results to the same table.

Table aTz9-W1. WebShop success rate with Qwen3-8B after four rounds of evolutions

MethodSuccess rate
All-task SFT (all successful rollouts)40.80%
Agent-R58.80%
PRFL70.20%


aTz9-W2 Benchmark difficulty and recent baselines

Reply to aTz9-W2

Thank you for the suggestions on benchmark discriminative power and recent baselines. The strongest methods on ALFWorld are already close to the success-rate ceiling, leaving limited room for improvement. WebShop still clearly distinguishes methods: PRFL achieves 71.00% success, compared with 67.15% for All-task SFT, 58.70% for Agent-R, and 51.30% for ReST-EM.

We also conducted a limited-scale, four-round self-evolution experiment on ScienceWorld to assess feasibility in a new environment. Using Qwen2.5-7B-Instruct on the same 100 held-out test tasks, PRFL achieved 25.00% success versus 20.00% for All-task SFT, with average rewards of 0.3646 and 0.2955, respectively. We are refining the experimental configuration and expanding the training data for a more comprehensive comparison.

Our main comparisons focus on SFT baselines to evaluate how the choice of training content affects self-evolution. RL also changes credit assignment and policy optimization. Following your suggestion, we evaluated GiGPO, which uses its own rollouts and environment feedback without external training data or process supervision.

We adapted GiGPO from full-parameter training to LoRA, using the same Qwen2.5-7B-Instruct base model and rollout budgets as our method, with 4,800 on ALFWorld and 8,000 on WebShop. The ALFWorld budget is one quarter of GiGPO's published 19,200 rollouts. We retained its native prompt and interaction history.

The original learning rate of 10−610^{-6} may not be optimal for LoRA. After an initial run at this rate, we tested 10−510^{-5}, 10−410^{-4}, and 2×10−42\times10^{-4} on ALFWorld and selected the best-performing rate, 10−410^{-4}, which we also used on WebShop. Our method achieved higher success on both benchmarks under these settings.

Table Sg3p-W3. Success rates under matched training rollout budgets.

MethodALFWorldWebShop
GiGPO (LoRA)66.60% ± 2.477.15% ± 1.08
Our method97.76% ± 1.6171.00% ± 0.52


aTz9-W3 End-to-end efficiency of generating training data

Reply to aTz9-W3

Our training data generation process is of high efficiency. The generation contains two stages, generating the rollouts and constructing milestone and learning signals. All methods share the same input data and inference procedure, thus have the same level of efficiency. Afterwards, we construct milestones and select learning periods from the recorded states purely based on CPUs, without additional policy rollouts or teacher calls. The additional time and resource cost is thus neglitable. The two stages combine to prove our advantage.

We also have a high utility fraction of training data. In WebShop R1, we used failed rollouts as learner contexts and extracted useful local demonstrations from both successful and failed rollouts. This allowed 275 of the 480 mixed-group rollouts (57.3%) to contribute to training, turning failed experience into usable training data.

AuthorsOpenReview ↗

Response to Reviewer aTz9 - 2

aTz9-Q1 The proportion of mixed-outcome task groups, the utility of failure donors within those groups and the source distribution of donated segments

Reply to aTz9-Q1

Thanks for your suggestions. We summarized the data from WebShop to address your concern. On WebShop, every sampling round produced mixed-outcome tasks for training. Within these groups, the proportion of failed rollouts finding a compatible donor increased across rounds, while the selected demonstrations came predominantly from successful rollouts.

Proportion of mixed-outcome task groups Each evolution round sampled 250 tasks with eight rollouts per task. From R1 to R4, 60, 154, 159, and 125 mixed-outcome tasks were used for data construction, representing 24.0%, 61.6%, 63.6%, and 50.0% of sampled tasks.

Utility of failed donors Within the mixed groups, 65.3%, 86.3%, 90.8%, and 94.0% of failed rollouts found compatible donors, providing local demonstrations for most failed learners in the later sampling pools.

Source distribution of donated segments Failed donors supplied 19.1%, 0%, 0.3%, and 0% of the final training segments across the four rounds. The remaining segments came from successful rollouts, including the designated reference and other successes. In R2, no failed candidate passing the static matching rules was shorter than the selected successful segment. Equally short failed candidates existed for 217/433 training segments (50.1%), but our rule tries successful donors first when action counts tie. Consequently, all selected R2 donors were successful.

The results are summarized below. Learner matches are counted before the training/validation split; donor shares use final training segments as their denominator. R3 and R4 include one and three group-level successful-reference fallbacks, respectively, counted under reference donors.

Table aTz9-Q1. WebShop task coverage, learner matching, and donor sources across evolution rounds

RoundSampled tasks × rollouts per taskMixed tasks / sampled tasksMatched learners / failed rollouts in mixed groupsTraining segmentsSegments from reference (%)Segments from other rollouts (%)Segments from other successes / failures (%)
R1250 × 860/250 (24.0%)247/378 (65.3%)21571.2%28.8%9.8% / 19.1%
R2250 × 8154/250 (61.6%)478/554 (86.3%)43372.3%27.7%27.7% / 0.0%
R3250 × 8159/250 (63.6%)413/455 (90.8%)37671.5%28.5%28.2% / 0.3%
R4250 × 8125/250 (50.0%)311/331 (94.0%)29684.5%15.5%15.5% / 0.0%


aTz9-Q2 Coverage of initially all-failure tasks

Reply to aTz9-Q2

Most tasks with no successful base-model attempts became solvable in the final evaluation: 60/61 tasks on ALFWorld (98.36%) and 149/189 on WebShop (78.84%) succeeded at least once with the final PRFL model. The gains therefore also covered tasks whose initial sampled attempts had all failed.

We reevaluated the same round-one training tasks with the final PRFL checkpoint, keeping the number of attempts per task unchanged: 400 ALFWorld tasks with four attempts using R3, and 250 WebShop tasks with eight attempts using R4. We tracked the initially all-failure tasks and classified their final outcomes as all-failure, mixed, or all-success.

Across rounds, all-failure task counts were 61, 38, and 31 on ALFWorld and 189, 72, 53, and 46 on WebShop. Because each round sampled different tasks, these counts do not track changes on a fixed task set. The table instead follows the original round-one tasks from Base to the final model.

Table aTz9-Q2. Outcomes of initially all-failure round-one training tasks after self-evolution

Environment (attempts per task; final model)Initially all-failure / all R1 tasksStill all-failureMixed outcomesAll-successAt least one success
ALFWorld (4; R3)61/400118 (29.51%)4260/61 (98.36%)
WebShop (8; R4)189/2504097 (51.32%)52149/189 (78.84%)
AuthorsOpenReview ↗

Response to Reviewer aTz9 - 3

aTz9-Q3 State matching and hand-designed task knowledge

Reply to aTz9-Q3

We use no hand-written rules that define task stages or subgoals. For each environment, we only provide minimum specifications on which recorded facts to compare and what is the matching criteria, which are then excuted via fixed CPU program.

In ALFWorld, two states match when their complete simulator fact sets agree after we normalize names and sort the facts, preserving object identities and argument order. In WebShop, the system maintains the current state after each action (page type, product ID, selected options, reward, and any recorded cart, purchase, or terminal fields). We treat two states as equal when these field values agree. For example, if both rollouts have the same shirt open, with green selected and no size chosen, their states match provided the remaining fields also agree. If one rollout has also selected XL, the states differ. We will add these details to Appendix A.1.



aTz9-Q4 Valid alternative paths and selection as learner or donor

Reply to aTz9-Q4

We agree that strict matching against a single reference can underestimate progress along a valid alternative path, a limitation already discussed in the paper. We choose the shortest successful rollout as a verified, relatively compact reference. Successful rollouts can also contain redundant search; turning these incidental states into milestones may introduce supervision on unnecessary detours. The shortest successful reference is therefore a simple, conservative choice to reduce this risk.

To address your concern, we implemented and retrained a multiple-reference variant on both benchmarks. Each successful rollout defines its own milestone sequence. For each failed rollout, we select the reference whose ordered matches extend furthest along that rollout’s own trajectory, retain the corresponding prefix, and use the next milestone as the learning target.

Multiple references moved the learning start later for 17.7% of WebShop learners and 21.4% of ALFWorld learners, but did not yield higher final success. Results were close on WebShop (70.90% versus 69.60%), while the single-reference variant scored 8.21 percentage points higher on ALFWorld (98.51% versus 90.30%). Some changes recovered genuine progress; others introduced incidental search targets or longer demonstrations. We therefore retain the shortest successful reference as the default, while allowing environment-specific matching rules.

The first two metrics below compare learning-boundary changes for the same final-round learners; the last two report final success rates from complete training runs.

Table aTz9-Q4. Effect of reference choice on learning boundaries and final success

EnvironmentLearners starting laterLearners starting later with a different next milestoneSuccess with one referenceSuccess with multiple references
WebShop R441/231 (17.7%)13/231 (5.6%)70.90%69.60%
ALFWorld R340/187 (21.4%)7/187 (3.7%)98.51%90.30%
AuthorsOpenReview ↗

Follow-up on Our Responses and Manuscript Updates

Thank you again for your review. We briefly summarize our responses and the corresponding manuscript updates:

  • Generalization to newer models (W1): On WebShop with Qwen3-8B, our method achieves 70.20% success, compared with 58.80% for Agent-R and 40.80% for All-task SFT (§5.4, Table 4; Appendix A.3).
  • Recent RL baseline (W2): We added GiGPO (LoRA), and our method achieves higher success on both benchmarks under matched rollout budgets (§5.4, Table 3; Appendix A.2).
  • Training-data construction efficiency (W3): Milestone construction operates on recorded states using CPU computation, without additional policy rollouts or teacher calls, as explained in our earlier W3 response.
  • Data utilization and donor sources (Q1): Our earlier Q1 response provides round-wise WebShop statistics on mixed-outcome tasks, compatible learner–donor matches, and the contributions of reference, other successful, and failed donors.
  • Coverage of initially all-failure tasks (Q2): Reevaluating the original round-one tasks with the final model yielded at least one success on 60/61 initially all-failure ALFWorld tasks and 149/189 WebShop tasks, as detailed in our earlier Q2 response.
  • State matching and task knowledge (Q3): We specify the recorded facts and exact matching rules for both environments, without manually labeling task stages or subgoals (§4.2; Appendix A.1).
  • Alternative successful paths (Q4): Multiple references recovered later learning starts for some failed rollouts but did not improve final success, supporting our shortest-successful-reference default (§5.3, Table 2; Appendix B.4).

As the discussion period is nearing its end, we would appreciate a brief update on whether these responses address your main concerns. Please let us know if any points remain unclear; we would be happy to clarify.

Thank you again for your time and consideration.

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

This paper proposes Policy-Relative Frontier Learning, a framework that constructs automatic curricula from an agent’s own trajectories. Using the shortest successful trajectory in a group as the reference, it identifies each failed rollout’s relative frontier, i.e., the furthest reference state the rollout matches in order, and orders these frontiers into a sequence of milestones. Each failed rollout then learns to move from its frontier to the next milestone, using its own prefix as context, and a matching segment from another rollout as the SFT target.

The main contribution is identifying a central challenge in agent self-evolution, which is deciding what the policy should learn and how far supervision should extend, and proposing a framework that converts outcome-only trajectories into dense milestone-based supervision. Experiments on ALFWorld and WebShop show that the method outperforms the evaluated baselines, and surpasses the final results of several baselines with fewer evolution rounds.

Critical strengths

Problem formulation is clear and well-motivated. The idea of learning from failure and constructing "relative learning intervals" to provide dense supervision from outcome-only trajectories is reasonable.

The method is simple and does not need extra components like a reward model, a stronger teacher or human step annotations, so it is easy to implement and plug into existing self-training pipelines. Code is also released. The ablations are well designed and map directly to the research questions, e.g. next-action vs full continuation vs relative interval for “how far supervision should extend”, and successful-donors-only for the donor source.

Critical weaknesses

Assumptions behind the relative frontier, and scalability to other environments. As far as I understand, the adaptive milestone construction and state matching rely on recorded environment states, i.e., the complete set of simulator facts in ALFWorld and a structured progress state in WebShop (Appendix A.1). Although these states are only used offline, I wonder whether this might limit how well the framework scales to other environments or more practical settings, where such states may not be easily available. It also raises a question about the fairness of the comparison, since most of the baselines do not rely on this information.

Modest improvement over the strongest baselines. On ALFWorld, the method reaches 97.76% compared with 96.64% for ReST-EM, which is within the reported standard deviation (±1.61). It is a bit hard for me to tell whether this difference is significant. The ALFWorld benchmark also seems quite saturated in the first place. In addition, this gain seems to partly rely on the ALFWorld-specific position weighting (Appendix C). In Table C.6, removing it reduces the final success rate from 98.51% to 95.90%, which would be below ReST-EM’s 96.64% in Table 1. Overall, I find the current results not yet fully convincing. Also, GiGPO is mentioned in the paper but not compared in the experiments. It seems to me that GiGPO shares a similar high-level idea of exploiting shared states across rollouts to obtain step-level signals from outcome feedback, while being a policy-gradient method.

It would be helpful if the authors could add a small-scale experiment on a less saturated benchmark, e.g., ScienceWorld, Sokoban. A comparison with GiGPO, either a discussion or an empirical one, would also be valuable.

Questions for authors
  1. Source of performance gain. In the supervision-scope and donor-source ablations (Figure 5 and Table B.4), the “Successful donors only” variant ends supervision at the next milestone, while “Full continuation” ends at task completion, and both use only successful donors. The two perform similarly on ALFWorld (94.40% vs. 94.78%), and “Successful donors only” is lower on WebShop (67.40% vs. 71.60%). Does this suggest that the performance gain of the method mainly comes from using failed rollouts as donors, while the main benefit of learning only up to the next milestone is better efficiency (i.e., fewer supervised tokens)?

  2. Potential evolution cost. Within each group, the learning signal is essentially anchored on the shortest successful trajectory sampled by the policy itself. In iterative self-evolution, could this reduce the agent's behavioral diversity or lead to self-reinforcement? Reporting the base model’s pass@k or the diversity of successful trajectories across rounds could be helpful.

  3. Assumption on single successful reference. If a task can be solved in different ways (e.g., selecting XL before green in Figure 3), a failed rollout’s progress may be underestimated. Could the authors discuss in slightly more detail, how this might affect the method, or how the frontier would change if all successful rollouts in the group were used as references?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Sg3p - 1

We thank the reviewer for recognizing our motivation and the simple design of using relative learning intervals to construct dense supervision from failed trajectories. We also appreciate your recognition of the results in task success and the number of evolution rounds required. Thank you for your time, effort, and valuable questions. Below, we address your concerns and present additional experiments and analyses.



Sg3p-W1 State availability and baseline fairness

Reply to Sg3p-W1

The concept of state is constantly occuring in agent applications, which describes the condition of an environment at a given step [1, 2]. Beyond ALFWorld and WebShop, ScienceWorld also provides a concrete example. When an agent heats ice until it melts, the simulator records the change from solid to liquid, whether or not anyone has designated melting as a task milestone [3]. This is also why our milestone construction method can generalize across environments: comparable states are widely existing in agent rollouts across different environments, and PRFL can identify milestones from those rollouts without any pre-defined task stages.

In our experiments, the comparison between PRFL and baselines is based on fair condition, they have access to the same environment and receive the same level of observations. No external information is provided, including supervision from external models or human-annotated steps. When preparing milestones, PRFL only compares state records across rollouts of the same task offline, and such process runs entirely on CPU.

References for Sg3p-W1

[1] A Survey of Self-Evolving Agents: What, When, How, and Where to Evolve on the Path to Artificial Super Intelligence.

[2] Environment Scaling for Interactive Agentic Experience Collection: A Survey.

[3] ScienceWorld: Is your Agent Smarter than a 5th Grader?



Sg3p-W2 The ALFWorld gain over ReST-EM and its dependence on position weighting

Reply to Sg3p-W2

We agree that PRFL’s average gain over ReST-EM on ALFWorld is modest, because ReST-EM is already close to saturation, leaving limited room for improvement. Yet, by breaking ALFWorld into separate tasks, our advantage over ReST-EM becomes obvious. On 6 officially classified tasks, PRFL scores higher on 3 of them (Pick, Cool, and Pick2), ties on 2 of them (Clean and Heat), and only slightly lower on one (Look). Besides, a fair comparison of two methods should be made on both datasets. On WebShop, PRFL outperforms ReST-EM by a large margin of 19.70 percentage points.

About the concern of our dependence on position weighting, the updated ReST-EM result is 94.22% ± 2.54, based on four new independent runs and excluding the original runs. PRFL without position weighting (95.90%) is therefore 1.68 percentage points above ReST-EM. More importantly, we did not apply position weighting to any methods on WebShop, and PRFL is still much better than ReST-EM.



Sg3p-W3 Less saturated environments and the GiGPO comparison

Reply to Sg3p-W3

Thank you for the suggestion. We conducted a limited-scale, four-round self-evolution experiment on ScienceWorld to assess feasibility in a less saturated environment. Using Qwen2.5-7B-Instruct on the same 100 held-out test tasks, PRFL achieved 25.00% success versus 20.00% for All-task SFT, with average rewards of 0.3646 and 0.2955, respectively. We are refining the experimental configuration and expanding the training data for a more comprehensive evaluation.

Our main comparisons focus on SFT baselines to evaluate how the choice of training content affects self-evolution. RL also changes credit assignment and policy optimization. Following your suggestion, we evaluated GiGPO, which uses its own rollouts and environment feedback without external training data or process supervision.

We adapted GiGPO from full-parameter training to LoRA, using the same Qwen2.5-7B-Instruct base model and rollout budgets as our method, with 4,800 on ALFWorld and 8,000 on WebShop. The ALFWorld budget is one quarter of GiGPO's published 19,200 rollouts. We retained its native prompt and interaction history.

The original learning rate of 10−610^{-6} may not be optimal for LoRA. After an initial run at this rate, we tested 10−510^{-5}, 10−410^{-4}, and 2×10−42\times10^{-4} on ALFWorld and selected the best-performing rate, 10−410^{-4}, which we also used on WebShop. Our method achieved higher success on both benchmarks under these settings.

Table Sg3p-W3. Success rates under matched training rollout budgets.

MethodALFWorldWebShop
GiGPO (LoRA)66.60% ± 2.477.15% ± 1.08
Our method97.76% ± 1.6171.00% ± 0.52
AuthorsOpenReview ↗

Response to Reviewer Sg3p - 2

Sg3p-Q1 Source of performance gain: failed donors and supervision up to the next milestone

Reply to Sg3p-Q1

Failed donors and supervision targeting the next milestone jointly contribute to the performance gains. Milestones allow us to turn useful segments from failed trajectories into supervision. This is particularly valuable early in self-evolution, when successful trajectories are scarce and supervision extracted from failed trajectories helps drive improvement.

For example, in the first round on WebShop, 40 of the 60 mixed-outcome training tasks had only one successful rollout out of eight. Mixed-task SFT trains on the shortest successful trajectory in each mixed-outcome group, whereas PRFL additionally extracted 36 training segments from failed trajectories in these 40 groups. Both methods started at a success rate of 3.9%. After one training round, Mixed-task SFT reached 7.2%, while PRFL reached 40.6%, a difference of 33.4 percentage points. These results highlight the complementary roles of milestone-based supervision and failed donors. Reducing the number of supervised tokens is an additional efficiency benefit of this design, consistent with its performance gains.



Sg3p-Q2 Behavioral diversity across rounds

Reply to Sg3p-Q2

We agree that repeatedly training a policy on its own rollouts could narrow the range of solutions it learns. This is also why we include useful segments from failed rollouts alongside successful demonstrations.

To quantify this, we compared Base with the final PRFL and All-task SFT checkpoints (ALFWorld R3 and WebShop R4), using the same four decoding seeds on each test task. We measured how often two successful attempts at the same task completed goal actions in opposite orders—for example, switching on a lamp before picking up a book versus picking up the book first, or selecting the required color and size in opposite orders on WebShop. Each pair counts once if at least one reversal is confirmed.

We considered only same-task seed pairs where both attempts succeeded under all three models: 523 pairs across 109 ALFWorld tasks and 18 pairs across 13 WebShop tasks. Unresolved pairs remain in the denominator. As shown below, PRFL matched Base on ALFWorld and showed a higher observed reversal rate on WebShop. We therefore still observe alternative valid action orders after training.

Table Sg3p-Q2. Goal-action order reversals across successful attempts

EnvironmentBasePRFLAll-task SFT
ALFWorld3/523 (0.57%)3/523 (0.57%)0/523 (0.00%)
WebShop2/18 (11.11%)4/18 (22.22%)0/18 (0.00%)


Sg3p-Q3 Alternative successful paths and reference choice

Reply to Sg3p-Q3

We agree that a single reference can underestimate progress along another valid route, as discussed in the paper. We chose the shortest successful rollout as a conservative reference because longer successful rollouts may contain detours that become unnecessary learning targets.

Following your suggestion, we retrained PRFL with multiple references on both benchmarks. Each successful rollout defines its own milestone sequence. For each failed rollout, we select the reference that preserves the longest prefix under ordered state matching, then use its next milestone as the target.

From the data side of view, adding multiple references moved the learning start later for 17.7% of WebShop learners and 21.4% of ALFWorld learners, allowing more of their existing trajectory to be retained and potentially avoiding repeated supervision of correct actions. For 5.6% and 3.7% of all learners, respectively, the next milestone also changed. More reference choices therefore affects both where learning begins and what the learner aims to reach.

However, the experiments suggest that recognizing more progress through multiple references does not necessarily improve learning. Final success remained close on WebShop (70.90% with one reference versus 69.60% with multiple references), while the multiple-reference variant performed worse on ALFWorld (98.51% versus 90.30%). One possible explanation is that some reference changes introduced incidental search targets or longer demonstrations of the same transition, making the resulting supervision less useful. We therefore retain the shortest successful rollout as the default, while allowing environment-specific matching rules. The results are summarized below.

Table Sg3p-Q3. Effect of reference choice on learner frontiers and final success

EnvironmentLearners starting laterLearners starting later with a different next milestoneSuccess with one referenceSuccess with multiple references
WebShop R441/231 (17.7%)13/231 (5.6%)70.90%69.60%
ALFWorld R340/187 (21.4%)7/187 (3.7%)98.51%90.30%
AuthorsOpenReview ↗

Follow-up on Our Responses and Manuscript Updates

Thank you again for your review. We briefly summarize our responses and the corresponding manuscript updates:

  • State availability and fairness (W1): We construct milestones from environment-maintained facts without predefined task stages, using the same environment access as our SFT baselines (§§4.2 and 5.1; Appendix A.1).
  • Performance gains and weighting (W2): The corrected ReST-EM result, 94.22% ± 2.54, summarizes four new independent runs, excluding the original runs; our 19.70-point WebShop advantage involves no position weighting (Table 1; Appendix C).
  • Recent RL baseline (W3): We added GiGPO (LoRA), and our method achieves higher success on both benchmarks under matched rollout budgets (§5.4, Table 3; Appendix A.2).
  • Source of performance gains (Q1): Local milestone endpoints make useful segments from ultimately failed rollouts available as supervision, so these two components jointly contribute to learning (§5.3; Appendices B.1–B.2).
  • Behavioral diversity (Q2): Our matched evaluations still show alternative valid goal-action orders after training on both benchmarks, as detailed in our earlier Q2 response.
  • Single-reference limitations (Q3): Multiple references recovered later learning starts but did not improve final success in either benchmark, supporting our compact single-reference default (§5.3, Table 2; Appendix B.4).

As the discussion period is nearing its end, we would appreciate a brief update on whether these responses address your main concerns. Please let us know if any points remain unclear; we would be happy to clarify.

Thank you again for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for recognizing novel idea of targeted learning from failures, improved success and action efficiency, and simple integration into existing self-training pipelines.

We summarize the shared concerns below, with references to our reviewer-specific responses for details.

1. Can other environments provide the state information our method requires?

State is a general concept describing an environment at a given step. Many interactive environments already maintain facts such as object properties, spatial relations, or selected options. We compare these records on CPU to construct milestones without predefined task stages or subgoals. The same framework can therefore transfer wherever states can be recorded and compared, with environment-specific matching rules providing further refinements (Sg3p W1; aTz9 Q3).

2. Why use only the shortest successful trajectory as a reference?

Multiple references can introduce incidental search targets or longer demonstrations containing detours. After retraining, single/multiple-reference success rates were 98.51%/90.30% on ALFWorld and 70.90%/69.60% on WebShop. Although multiple references recovered some valid progress, they did not yield higher final success. We therefore retain the verified, relatively compact shortest successful trajectory as a conservative default to reduce supervision on unnecessary detours (Sg3p Q3; aTz9 Q4; 2Wp1 W1).

3. Why prioritize SFT comparisons, and have recent RL baselines been added?

Our contribution focuses on what to learn, so we initially compared supervision content under the same SFT training approach. Step-level RL focuses more on how to learn through credit assignment and policy optimization. We subsequently evaluated GiGPO using the same base model and training-rollout budgets. PRFL/GiGPO achieved 97.76%/66.60% on ALFWorld and 71.00%/7.15% on WebShop (Sg3p W2–W3; aTz9 W2; 2Wp1 W3).

4. Does the ablation establish that failed donors provide better demonstrations?

Our central finding is that failed trajectories also contain useful local demonstrations worth including in the training candidate pool. We aim to give learners more viable routes to the same milestone without judging segment quality solely by the donor’s final outcome. Expanding the pool can provide demonstrations for more learners or alternative routes for learners already covered. On WebShop, including failed donors increased training coverage from 69.9% to 76.6% and task success from 67.40% to 71.00% (2Wp1 W4).

5. Does learning to the next milestone only save supervision tokens?

Milestones and failed donors jointly provide additional local supervision, particularly early in training when successful demonstrations are scarce. In WebShop R1, 40 of the 60 mixed-outcome tasks had only one successful rollout. PRFL extracted 36 additional training segments from failed rollouts in these groups. After one evolution round, PRFL reached 40.6% success, compared with 7.2% for Mixed-task SFT. Local targets allow ultimately failed rollouts to contribute useful demonstrations, with fewer supervised tokens providing an additional efficiency benefit (Sg3p Q1).

We also provide the requested statistics and additional analyses:

  • Data use and efficiency: round-wise learner and donor statistics, CPU-based construction, and supervised-token savings of 42.37% on ALFWorld and 11.77% on WebShop (aTz9 W3 and Q1).
  • Effectinvess on initially unsolved tasks: reevaluating the same tasks with the same attempts per task, the final model gains at least one success on 60/61 ALFWorld tasks and 149/189 WebShop tasks (aTz9 Q2).
  • A second backbone: Qwen3-8B achieves 70.20% on WebShop, versus 58.80% for Agent-R and 40.80% for All-task SFT (aTz9 W1).
  • Behavioral diversity: matched evaluations still show alternative valid goal-action orders after training (Sg3p Q2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.