acceptodds
Under review as a conference paper at ICLR 2027

Explorer-zero: Improving Self-Play for Long-Horizon Tasks with Decomposable Verifiable Rewards

Abstract

Training LLM agents on long-horizon interactive tasks with reinforcement learning typically relies on human-annotated tasks and reliable verification, both expensive to construct for stateful environments. Self-play offers an alternative, but must generate achievable, compositional tasks and provide feedback beyond binary outcomes. We propose Explorer-Zero, a self-play framework that jointly generates tasks and fine-grained, verifiable rewards through environment interaction. A learned proposer explores the environment, constructs tasks, and records intermediate and final states as verification targets. These checkpoints reward partial completion, while alternating proposer-solver training adapts the generated curriculum. We show theoretically that subtask rewards reduce collapse among unsuccessful rollouts when they complete different numbers of subtasks. Without human-annotated training tasks, Explorer-Zero outperforms the evaluated self-play baselines across ALFWorld, ScienceWorld, and AppWorld; on AppWorld, our 30B agent reaches % task success, approaching % for RL on human-annotated tasks. Further analyses support task-relevant composition and benefits on complex tasks, while self-play initialization improves subsequent human-data RL across all three benchmarks.

Primary area:
reinforcement learning
Keywords:
self-play, reinforcement learning

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

Explorer-zero alternates training a task proposer and solver in resettable stateful environments. The proposer explores, carries out a task, and records intermediate and final states as verification targets. The solver receives the generated instruction and obtains partial reward for matching intermediate checkpoints, in addition to final completion reward. Proposer incentives favour intermediate difficulty, subtasks and action diversity. Across ALFWorld, ScienceWorld and AppWorld, the method outperforms the evaluated self-play baselines without human-authored training tasks. A 30B AppWorld model reaches 59.67% task goal completion versus 51.93% for Self-Challenging and 62.65% for human-data RL. The theory characterises reduced reward collapse conditional on all rollouts failing and having varied subtask counts.

Critical strengths
  1. Reusing demonstrated intermediate states as reward checkpoints provides a coherent way to couple feasible task generation with process supervision. It avoids requiring a separate task-specific judge for each proposal, and the paper makes the resettable, inspectable-environment assumption explicit. This is a useful training-system contribution rather than merely another prompting scaffold.

  2. Evaluation uses the benchmarks' independent success criteria, not the proposer-generated checks. Consistent gains across three environments and two AppWorld model sizes therefore support downstream utility despite possible imperfections in the self-generated curriculum. The interactive-proposer ablation and complexity-stratified analysis further connect the gains to the intended long-horizon setting.

Critical weaknesses
  1. Semantic reliability of the generated verification targets is not sufficiently established. A reached state proves feasibility, but does not ensure that its retained changes exactly express the final instruction or that intermediate checkpoints represent substantive progress. Figure 8 provides a concrete example: a login checkpoint survives the validity filter, and another subtask mentions adding songs although the saved state contains only an empty playlist. Equation 7 also permits a failed final task to receive reward 1 after all checkpoints have been visited. These issues do not invalidate the independent benchmark gains, but they limit the claim that the generated supervision reliably encodes task completion.

  2. The reported evidence does not isolate the proposed reward-collapse mechanism. Table 2 changes both the generated task distribution and solver rewards, as the authors acknowledge. Figure 3 reports fewer zero-reward rollouts, whereas the proposition concerns equal rewards within a rollout group; a group can have nonzero identical rewards and still collapse. The gains establish the value of the combined approach more strongly than the particular optimisation explanation. Reported deviations also come from evaluation sampling, not independent training runs.

Questions for authors
  1. Clarification and targeted validation: how do the matching rules handle incidental state changes, logically equivalent solutions and unrelated destructive changes? Could you report a small audit of existing generated instructions/checkpoints, including the frequency of setup-only or mismatched checkpoints and failed-final rollouts receiving reward 1?

  2. Existing-log analysis: what fraction of GRPO groups has zero reward variance with and without subtask supervision, especially conditional on all final tasks failing? This directly tests the stated mechanism. If available, a fixed generated-task pool evaluated under binary versus checkpoint rewards would separate reward granularity from curriculum changes, but the group-variance statistic is the primary request.

3 comments

We thank reviewer QCJF for the careful assessment and for recognizing the value of grounded process supervision and independent benchmark evaluation. We address the reviewer's concerns below.

(1a) How does verification handle alternative solutions, incidental changes, and unwanted side effects?

Our verifier accepts different action sequences that reach the same checked goal state. Matching the proposer's reference can nevertheless be restrictive when a task admits valid solutions corresponding to different checkpoint states. In our targeted ALFWorld oracle study with GPT-5.5, over 70% of tasks had at least two distinct sampled action paths, while all-pass@5—the fraction of tasks for which all five attempts succeed—was 88.0% on generated tasks, compared with 87.1% on ALFWorld validation tasks using its own verifier (see our response to fXMZ for details).

(1b) Could the authors audit generated instructions and checkpoints, including setup-only or mismatched checkpoints and failed-final rollouts receiving reward 1?

We manually audited 100 accepted tasks and their checkpoints, split equally between early and late training. Instructions and targets agreed in 93 cases, with all seven mismatches in AppWorld:

EnvironmentSampled tasksInstruction and target agreeMismatch
ScienceWorld30300
ALFWorld30300
AppWorld4033 (82.5%)7 (17.5%)
All10093 (93.0%)7 (7.0%)

AppWorld mismatches fell from 5/20 early to 2/20 late: early errors included drafts instead of sent emails and clauses retained after failed API calls; the two late cases overstated an operation's effect or retained an unwanted deletion. We add the audit and clarify the checkpoint examples in Appendix E and Figure 8. Paper revisions are highlighted in blue.

When looking at intermediate checkpoints in these tasks, all 89 checkpoints audited in ALFWorld and ScienceWorld were supported by their subtask descriptions. Among the 41 AppWorld checkpoints, two were setup-only (4.9%). Separately, seven AppWorld tasks had instruction–target mismatches; only one of those tasks also contained a mislabelled intermediate checkpoint.

Finally, the reviewer correctly identified a missing weight in Eq. 7: the corrected equation assigns success reward 1 and bounds failed-task checkpoint credit by 0.15. We correct Eq. 7 and Appendix B, as discussed in our response to reviewer 8Dtg.

(2) What fraction of GRPO groups has zero reward variance with and without subtask supervision, especially when every rollout fails?

On the same saved rollouts, checkpoint rewards restore nonzero variance in 31–52% of all-final-failure groups. We rescore all logged updates under binary final-success and fine-grained subtask rewards, using groups of 8 rollouts for the same task and determining final success with the generated verifier. A group counts as collapsed whenever all 8 rewards are equal, including equal positive rewards:

Dataset / modelAll-fail groupsCollapse, binary rewardCollapse, subtask rewardRelative reduction
ALFWorld 4B255100%62.75%37.25%
ScienceWorld 4B621100%68.92%31.08%
AppWorld 4B171100%52.05%47.95%
AppWorld 30B231100%48.05%51.95%

Because the tasks and trajectories are identical in both reward columns, this comparison isolates how checkpoint rewards distinguish different amounts of progress. It directly measures group collapse, whereas Figure 3 measures individual zero-reward rollouts. We add this analysis to Appendix E.

AuthorsOpenReview ↗

Addressing concerns

Dear Reviewer QCJF,

Thank you again for your comments. As the discussion period is closing, we are looking forward to your comments on our rebuttal. We appreciate your valuable time and efforts in reviewing our work.

Some key takeaways from reviews and rebuttal:

  • Directly measuring reward collapse: Rescoring identical saved trajectories shows that checkpoint rewards restore nonzero reward variance in 31–52% of groups where every rollout fails the final task, directly testing the proposed mechanism without changing tasks or trajectories.
  • Auditing supervision reliability: Our manual audit finds instruction–target agreement in 93 of 100 accepted tasks, with all seven mismatches occurring in AppWorld; two of 41 AppWorld intermediate checkpoints were setup-only. More details in Appendix B.
  • Alternative solutions and verification limitations: The diverse-solution study achieves all-pass@5 of 88.0% on generated tasks versus 87.1% on ALFWorld validation tasks, while we acknowledge that reference-state matching can restrict valid alternative goal states and does not explicitly penalize unwanted side effects.
  • Reward for failed-final rollouts: The missing weighting factor in Equation 7 has been corrected: final success receives 1.0, while reward for a failed final task is bounded by 0.15 (even if all subtasks succeed).

Regards,
Authors

Thank you. Rescoring identical rollout groups addresses my reward-collapse concern, and the fixed-task-pool experiment further supports the contribution of checkpoint rewards. The clarification that failed-task rewards were capped at 0.15 in the experiments resolves my concern about Equation 7. The audit is also informative, although the AppWorld mismatches and lack of penalties for unwanted side effects remain important limitations. With these limitations stated clearly, my main concerns are substantially addressed. I remain at weak acceptance.

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

The paper introduces Explorer-Zero, a self-play framework that leverages environment interactions to generate compositional tasks and verifiable intermediate rewards through a proposer agent. The solver agent is then trained using intermediate rewards derived from the checkpoints recorded by the proposer. Experimental results show that this framework can improve performance on tasks requiring multiple operations.

Critical strengths
  1. The paper is well-structured and clearly organized.
  2. Using a self-play proposer agent to generate subtasks rewards for solver training within a jointly trained proposer–solver framework is an interesting idea.
  3. Experimental results across three benchmarks demonstrate that Explorer-Zero consistently improves performance.
Critical weaknesses
  1. The reward function cannot distinguish between successfully completing the final task and only completing all the intermediate subtasks. If a solver completes all intermediate subtasks but fails the final task, it can still receive the same reward as a solver that successfully completes the final task. How does the proposed method handle such situation?
  2. In Table 1, the comparison between RL and RL + Ours using human-annotated data raises concerns about the fairness of the training budgets. Since RL + Ours includes an additional self-play pretraining stage with intermediate subtask rewards, it is unclear whether the two settings are compared under equivalent training budgets. Are the total training steps and computational costs the same for both settings?
Questions for authors

See weakness. I am happy to discuss with the authors

3 comments

We thank reviewer 8Dtg for recognizing the paper’s clarity, the interest of proposer-generated subtask rewards, and the consistent improvements across benchmarks!

We address the concerns raised by the reviewer below.

(1) Can completing all intermediate subtasks receive the same reward as final-task success?
No. Eq. 7 contains a typo with an omitted weighting factor λsubR(subgoal)\lambda_{\text{sub}} R^{\text(subgoal)}, and we thank them for catching this. Terminal success receives 1.0, while terminal failure in spite of completing all subtasks receives a score of λsub\lambda_{\text{sub}} (set to 0.15 in our experiments). We have corrected Eq. 7 and Appendix B and clarified the implementation in Appendix D (edits in blue).

(2) Fair comparison between "RL-only" and "RL + our approach" ... does latter benefit from receiving more solver updates?
No -- both were trained under similar computational budgets. For instance, in AppWorld 30B, we account for both methods over 200 solver updates: RL-only uses 200 updates on human-annotated tasks, while RL + Ours uses 150 updates on proposer-generated tasks followed by 50 on human data. Interestingly, training the solver in RL + Ours uses approximately 9% fewer generated tokens, 14% fewer environment interactions, and 30% fewer GPU-hours. These lower costs are consistent with shorter rollouts on self-generated tasks, requiring fewer tokens and environment interactions. Separately, training the proposer for 100 updates in RL + Ours used approximately 105.4 training GPU-hours and 173.6M generated tokens. We have clarified the training schedule in Sec. 4.2 and added the accounting in Appendix D (edits in blue).

SettingUpdates chargedGenerated tokens, estimatedEnvironment interactionsTraining GPU-hours, estimated
RL-only200258.3M431,482147.3
RL + Ours (solver)200234.5M369,668103.7
RL + Ours (proposer)100173.6M241,881105.4
AuthorsOpenReview ↗

Addressing concerns

Dear Reviewer 8Dtg,

Thank you again for your comments. As the discussion period is closing, we are looking forward to your comments on our rebuttal. We appreciate your valuable time and efforts in reviewing our work.

Some key takeaways from reviews and rebuttal:

  • Distinguishing partial progress from final success: Equation 7 omitted the subtask weighting factor: final success receives reward 1.0, whereas failed-final rollouts receive at most 0.15, even when all intermediate subtasks are completed. We have corrected the equation and accompanying descriptions.
  • Training-budget comparison: Both settings use 200 solver updates, and our solver uses approximately 30% fewer training GPU-hours on AppWorld 30B. Proposer training incurs additional overhead, which we now report separately rather than claiming equal total end-to-end compute.

Regards,
Authors

I thank the authors for the rebuttal, after reading the rebuttal I keep my positive score ( 3 ).

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

The paper proposes Explorer-Zero, a self-play method for training LLM agents. The method comprises of two models, a proposer and a solver. The proposer explores the environment, interacts with it and constructs tasks based on what it managed to accomplish. Then it sets the goal for the solver and selects subtasks. Its trajectory is saved. The goal and subtasks are verified by the similarity to the states in the trajectory. The solver gets reward for solving the task, or gets partial reward for solved subtasks. Both models are trained with GRPO in alternating phases. The authors evaluate the method on two models and three environments. The method shows promising improvements over the baselines.

Critical strengths
  • The problem is practically important. I agree with the motivation. Constructing tasks and rewards for interactive environments is difficult and time consuming. I can imagine this method being useful when we have access to an environment but do not have enough tasks to train the agent. The paper introduces a way to ground the generation of the tasks and subtasks using proposers interaction within the environment. The states reached by the proposer allow verification of the partial progress combating the reward collapse common when solving hard, long tasks. The authors present results that support that, % of zero-reward rollouts is smaller, and success rate on complex tasks is higher.
Critical weaknesses
  • Limited evidence about why the method improves and how robust the results are. The results are promising, but I do not yet find the analysis sufficient to understand why the method works or how reliably it improves performance. The subtask ablation changes both task construction and solver rewards. Although the results show that this combination helps, it is hard to tell how much of the improvement comes from better tasks and how much comes from rewarding partial progress. The authors acknowledge this limitation, but a comparison using the same generated tasks would help separate these effects.

    I also have concerns about the broader applicability of the method. If verification requires matching the proposer’s particular solution, it could penalize other valid solutions, especially for open-ended tasks. Conversely, if it ignores unwanted side effects, it could reward attempts that do not correctly satisfy the task. I would expect the authors to evaluate how often these problems occur, since they directly affect what the solver learns.

Questions for authors
  • How does verification handle tasks that can be completed in several valid ways? How do the authors distinguish task-relevant changes from incidental changes or unwanted side effects?
  • All evaluated models belong to the Qwen family. Can the authors examine models from another family, for example Gemma or OLMo?
  • How stable is the alternating training of the proposer and solver (instability or performance deterioration)? Can the authors provide results with the models trained for longer?
  • The proposer explores less over time, could this lead to overfitting to a limited set of tasks? Have the authors tested generalization to different environments?
  • How much of the improvement comes from generating better tasks, and how much comes from rewarding partial progress? Have the authors compared training on the same generated tasks with and without subtask rewards?
3 comments

We thank Reviewer fXMZ for the thoughtful review. We appreciate that the reviewer finds the problem practically important and recognizes how grounding task and subtask generation in the proposer's interactions makes partial progress verifiable and reduces reward collapse on long-horizon tasks.

We address the reviewer's concerns in the following.

(1a) How does verification handle tasks that can be completed in several valid ways?
Our verification relies primarily on whether the task succeeded and not the way it was achieved. To support this statement, we ran a new experiment evaluating a strong policy (GPT-5.5) completing tasks in diverse ways (enabled by high temperature sampling) on ALFWorld tasks and verification artifacts sampled from our frozen proposer policy. We found a high all-pass@kk score (i.e., all k=5k=5 diverse trajectories succeeding) of 88.0% on proposer's tasks and verification, which appears also consistent with a all-pass@kk score of 87.1% on ALFWorld data and verification itself.

(1b) How do the authors distinguish task-relevant changes from incidental changes or unwanted side effects?
We do not distinguish. Our verification protocol does not penalize side-effects and allows the agent to reach the final goal state in multiple valid ways. While it would be ideal to specifically penalize unwanted side-effects, determining incidental-vs-unwanted side-effects in a self-play regime is challenging and we are happy to address this in future work.

(2) Can the authors examine models from another family, for example Gemma or OLMo?
Updated (2026-Nov-18) Thanks for the suggestion. We complement our existing models (4B and 30B-A3B) with evaluation on Olmo-3-7B-Instruct. We find promising results on ALFWorld: our self-play approach without annotated training data improves base success rates on both validation seen (5.2 → 54.1%) and unseen (5.4 → 53.2%) splits. More details in Section E.8.

(3) How stable is the alternating training of the proposer and solver (instability or performance deterioration)? Can the authors provide results with the models trained for longer?
We do not expect the training to be stable. Both proposer and solver policies are trained with GRPO and GRPO updates do not guarantee monotonic improvements. Nonetheless, we are currently running longer experiments and include the findings in the next version of the paper.

(4a) The proposer explores less over time, could this lead to overfitting to a limited set of tasks?
We find no evidence that reduced exploration causes curriculum overfitting. For instance, in AppWorld (which involves solving tasks with 9 day-to-day apps spanning 450+ APIs), we find the app-specific entropy increases from 2.162 to 2.186 with the 4B model and from 2.121 to 2.157 with the 30B model. Similarly distinct valid APIs in tasks also grow from 125 to 142 at 4B and from 147 to 168 at 30B. Thus, in spite of exploration steps reducing over the course of training, we nonetheless find diversity in the proposed tasks and do not find evidence of overfitting (e.g., to a narrow set of challenging apps/APIs).

(4b) Have the authors tested generalization to different environments?
Cross-environment transfer is not the intended setting in our work, since each environment has a different action space and state-verification interface. Our work specifically leverages the proposer to learn environment-specific knowledge through exploration and can provide a training curriculum to the solver. Within a particular environment, we demonstrate that the environment can generalize to unseen tasks despite training only on self-generated data.

(5a) Have the authors compared training on the same generated tasks with and without subtask rewards?
Updated response (2026-Nov-16)
Yes. To complement our existing findings in Table 2 and reaffirm benefit of subtask rewards, we run an additional experiment: we finetune a Qwen3-4B model on a frozen set of generated tasks, without and with subtask rewards. We find an improvement of 2.24% (30.65 → 32.89) on Appworld success rates, suggesting that subtask rewards provides a useful signal to train a solver. More details in Appendix E.7 of the paper.

(5b) How much of the improvement comes from generating better tasks, and how much comes from rewarding partial progress?
Updated response (2026-Nov-16)
We run additional ablations on a Qwen3-4B model and find our existing claim in Table 2 still holds. Combining both components achieves the highest TGC (38.39%), outperforming only generating better tasks (30.36%) and only rewarding partial progress (27.98%). More details in Appendix E.7.

AuthorsOpenReview ↗

Update (2026-Nov-16)

Thank you for your patience. We have updated our original rebuttal with additional experiments addressing Question 5, including ablations on subtask rewards and subtask generation.

AuthorsOpenReview ↗

Addressing concerns

Dear Reviewer fXMZ,

Thank you again for your comments. As the discussion period is closing, we are looking forward to your comments on our rebuttal. We appreciate your valuable time and efforts in reviewing our work.

Some key takeaways from reviews and rebuttal:

  • Separating task generation from partial-progress rewards: On a frozen generated-task pool, adding subtask rewards improves AppWorld success from 30.65% to 32.89%. More details in Appendix E.7.
  • Evaluation beyond the Qwen family: New experiments with Olmo-3-7B-Instruct improve ALFWorld success from 5.4% to 53.2%. More details in Appendix E.8.
  • Alternative solutions and side effects: Our diverse-solution study achieves all-pass@5 of 88.0% on our generated tasks and verification artifacts, compared with 87.1% using ALFWorld’s own tasks and verifier suggesting multiple ways to complete a task. However, our verifier does not explicitly penalize unwanted side effects.
  • Curriculum diversity and generalization: App coverage entropy and distinct API coverage increase during training despite shorter exploration, while our generalization claims concern unseen tasks within each environment rather than cross-environment transfer.
  • Longer-training stability: We acknowledge that GRPO does not guarantee monotonic improvement; longer-training experiments remain ongoing, as noted in our rebuttal.

Regards,
Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.