PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tianyu Liu, Davide Belli, Bence Major, Arash Behboodi, Tribhuvanesh Orekondy

arXiv:2610.19868v1cs.AIcs.LG

TL;DR

Long-horizon RL in stateful environments is costly to supervise with human-authored tasks and reliable checks, and binary rewards can erase partial progress. Explorer-Zero jointly generates compositional tasks and verifiable intermediate rewards through proposer–solver self-play. It outperforms evaluated self-play baselines across three benchmarks without human-annotated training tasks, while its 30B AppWorld agent reaches 59.67 TGC, approaching 62.65 for human-data RL.

  • Problem

    Human-annotated tasks and reliable success checks are expensive to construct for stateful environments, and binary outcomes can discard meaningful progress on long-horizon tasks.

    Source: §1 · pp. 1–2

  • Method

    Explorer-Zero trains an environment-interacting proposer to generate compositional tasks and intermediate and final state checkpoints, which an alternating solver uses for verifiable rewards.

    Source: §1 · p. 2, §3.1 · pp. 4–5

  • Results

    Explorer-Zero outperforms evaluated self-play baselines across ALFWorld, ScienceWorld, and AppWorld without human-annotated training tasks; its 30B AppWorld agent reaches 59.67 TGC versus 62.65 for human-data RL.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The findings support using task-generation trajectories as a source of compositional tasks and intermediate supervision, with the largest gains on tasks requiring multiple dependent operations.

    Source: §1 · p. 2, §6 · p. 9

    Snapshot-based verification requires resettable environments whose states can be recorded and compared; extending it to partially observable or irreversible environments remains open.

    Source: H LIMITATIONS · p. 27

Abstract

from arXiv · show

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 59.67% task success, approaching 62.65% 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.

1 INTRODUCTION

Long-horizon tasks are costly to author and verify, while binary outcomes can discard meaningful partial progress. Explorer-Zero uses environment interaction to generate compositional tasks and intermediate checkpoints, and outperforms evaluated self-play baselines across three benchmarks.

Introduction

  • Human-authored tasks and reliable success checks are expensive to construct for stateful environments, limiting how broadly agentic RL can scale.Designers must determine what the current state permits, specify a meaningful state change, and define how to verify it.Source: §1 · p. 1
  • Stateful long-horizon self-play must discover reachable goals and preserve information about partial progress that binary success checks discard.A proposer may not know from the initial observation which goals are reachable, and unsuccessful trajectories receive no distinction for progress.Source: §1 · p. 1
  • Compositional tasks require sequences of meaningful state changes, which a proposer can discover through environment interaction and compose into grounded tasks.For example, locating an item can precede picking it up and moving it to a destination.Source: §1 · pp. 1–2
  • Explorer-Zero’s proposer records intermediate and final environment states as verifiable checkpoints, rewarding solver subtask completion and adapting the curriculum alongside the solver.The framework is designed to train without human-written tasks or a prompted frontier model.Source: §1 · p. 2
  • Explorer-Zero outperforms evaluated self-play baselines across ALFWorld, ScienceWorld, and AppWorld without human-authored training tasks, and improves subsequent human-data RL across all three.On AppWorld, its 30B agent reaches 59.67 TGC, approaching 62.65 for human-data RL.Source: §1 · p. 2

2 RELATED WORK

Prior self-play methods use static checks, fixed task generators, or task-selection strategies, while interaction-grounded approaches generally do not jointly train a proposer and reuse its trajectory as intermediate reward supervision. Explorer-Zero combines these functions for stateful environments.

Self-play with verifiable tasks

  • Prior self-play methods rely on known answers, automatic checks, or generated environments, leaving reachable compositional goal discovery in stateful target environments unresolved.The challenge also includes retaining a learning signal when the solver cannot yet complete the task.Source: §2 · p. 2

Interaction-grounded task generation

  • Interaction-grounded methods generate tasks from trajectories, but their generators are fixed prompted models and their trajectories are not reused as intermediate reward checkpoints.Explorer-Zero instead trains a proposer to compose tasks from multiple demonstrated transitions and uses those states to verify progress.Source: §2 · pp. 2–3

Fine-grained supervision for long-horizon RL

  • Existing self-play fine-grained feedback methods steer task selection, whereas Explorer-Zero derives solver rewards from the same proposer trajectory that generates each task.Other fine-grained methods outside self-play use matched states or hand-designed progress rules for predefined tasks.Source: §2 · p. 3

3 METHODOLOGY

Explorer-Zero replaces a fixed task distribution with an alternating proposer–solver process in which environment interaction yields tasks and state-based verification artifacts. Subtask checkpoints provide a learning signal even when every solver rollout fails, if failed rollouts complete different numbers of subtasks.

3 METHODOLOGY

  • Explorer-Zero replaces a fixed task distribution with tasks generated by an environment-interacting proposer, and alternates proposer and solver optimization so the task distribution can evolve with the solver.The proposer is frozen during solver training, and the solver is frozen during proposer training.Source: §3 · p. 3, §3.1 · p. 3

3.1 PROPOSER: INTERACTIVE GENERATION OF COMPOSITIONAL TASKS

  • The proposer explores to discover what the initial state permits, then solves its candidate task, declaring subtasks and a final task whose reached states become verification artifacts.State matching checks task-relevant changes against the common initial state; intermediate checkpoints are an unordered checklist, without explicitly modeled dependencies.Source: §3.1 · p. 4

3.2 SOLVER: TRAINING A POLICY TO SOLVE

  • The solver trains on accepted proposer-generated tasks using final-task and subtask verification, with successful trajectories receiving maximum reward and unsuccessful ones distinguished by verified subtask completion.A rule-based filter rejects malformed tasks, redundant subtasks, and task descriptions unsupported by the proposer’s interaction.Source: §3.2 · pp. 5–6

3.3 SUBTASK REWARDS REDUCE REWARD COLLAPSE

  • Subtask rewards make failed rollouts distinguishable when they complete different numbers of subtasks, reducing reward collapse and preserving nonzero normalized advantages even when all rollouts fail.With binary rewards, all-failure groups collapse with probability one; subtask rewards reduce that probability below one when at least two subtask-completion counts occur among failures.Source: §3.3 · p. 6

4 EXPERIMENTS

The experiments evaluate Explorer-Zero across three environments and compare it with self-play baselines, human-data RL, and component ablations. Results show gains over self-play baselines, benefits from combining self-play with human-data RL, and substantial additional gains from the full method over ablations.

4.1 EXPERIMENTAL SETUP

  • Evaluation covers ALFWorld unseen validation, ScienceWorld test, and AppWorld test_normal, reporting benchmark success rates and AppWorld TGC and SGC.Results are means and standard deviations over four samples per task prompt; training-time verification accommodates interchangeable object instances in ALFWorld and ScienceWorld.Source: §4.1 · p. 6, Table 1 · p. 7

4.2 MAIN RESULTS AND ABLATIONS

  • Explorer-Zero outperforms the stronger self-play baseline across all three environments, with gains of 18.67 ALFWorld points, 7.23 ScienceWorld points, and 7.74 AppWorld TGC points for the 30B model.The 4B AppWorld model gains 6.19 TGC points; Table 1 reports the benchmark results.Source: §4.2 · p. 7, Table 1 · p. 7
  • Explorer-Zero reaches 59.67 AppWorld TGC with the 30B agent, compared with 62.65 for RL on the full human-annotated training set.RL on human-annotated tasks remains stronger on the primary task-level metrics.Source: §4.2 · p. 7
  • On AppWorld, subtask-supervised proposer trajectories are similar in length, use fewer API calls on average, and contain a larger fraction of interactions contributing to the final task.Contributing interactions are identified by backward program slicing.Source: Figure 2 · p. 8
  • During AppWorld training, the proposer shifts from exploration toward executing proposed tasks, while declared subtasks increase from around 0.8 to 2.3 on average.The figure also shows zero-reward solver rollouts ending near 22% with subtask supervision versus 39% without it.Source: Figure 3 · p. 8
  • Combining Explorer-Zero pretraining with human-data RL improves over RL alone across all three environments, including gains of 13.63 ScienceWorld points and 6.55 AppWorld TGC points with the 30B model.The protocol uses 200 steps of Explorer-Zero followed by 150 RL steps on human-annotated tasks.Source: §4.2 · p. 8
  • Adding subtask supervision to interactive proposal yields further gains of 18.58 points on ALFWorld, 18.22 on ScienceWorld, and 13.84 AppWorld TGC points.Interactive proposal also improves over one-shot proposal across all three environments; this ablation combines changes to task construction and solver rewards.Source: Table 2 · p. 7, §4.2 · p. 8

5 ANALYSIS

The analyses find that subtask supervision is associated with more task-relevant proposer interactions and increasingly structured tasks. Its benefits are most pronounced for complex, compositional tasks, while subtask rewards preserve distinctions among unsuccessful solver rollouts.

5.1 SUBTASK SUPERVISION PRODUCES TASK-RELEVANT COMPOSITIONS

  • Subtask supervision increases the fraction of proposer interactions contributing to the final task without increasing trajectory length, and the proposer makes fewer API calls on average.Contributing interactions either produce target-state changes or support them through Python data flow, identified using backward program slicing.Source: §5.1 · p. 8

5.2 THE PROPOSER LEARNS TO CONSTRUCT STRUCTURED TASKS

  • During training, exploration turns decrease from roughly 14 to 7, solving turns rise from around 7 to 10, and declared subtasks increase from approximately 0.8 to 2.3.These trends indicate that the proposer allocates more interaction to task execution while constructing tasks with more explicit compositional structure.Source: §5.2 · p. 9

5.3 SUBTASK REWARDS PRESERVE LEARNING SIGNAL

  • With subtask supervision, zero-reward solver rollouts end near 22%, versus 39% without subtasks, preserving a learning signal when all sampled rollouts fail.The signal comes from rewarding differences in the number of subtask checkpoints reached.Source: §5.3 · p. 9

5.4 BENEFITS CONCENTRATE ON COMPOSITIONAL TASKS

  • Subtask supervision yields a large and consistent success advantage in AppWorld’s highest-complexity bins, while benefits on simpler tasks are little or inconsistent.Complexity is measured by test-case predicates, API calls, or reference-solution lines of code.Source: §5.4 · p. 9, Figure 4 · p. 9
  • The largest per-app gains occur for Todoist and Splitwise, which appear exclusively in multi-app tasks in this evaluation set.These tasks require carrying information and effects across application boundaries.Source: §5.4 · p. 9, Figure 4 · p. 9

6 CONCLUSION

Explorer-Zero uses environment interaction to generate compositional tasks and verifiable intermediate rewards; experiments show gains over evaluated self-play baselines and improvements to subsequent human-data RL. The preliminaries describe RLVR and GRPO for training agents on long-horizon tasks.

6 CONCLUSION

  • Explorer-Zero outperforms evaluated self-play baselines across three benchmarks without human-annotated training tasks and improves subsequent human-data RL.The conclusion attributes the gains to subtask supervision and reports the largest gains on tasks requiring multiple dependent operations.Source: §6 · p. 9
  • Deployment beyond benchmark environments requires safeguards because reference-state checks measure task completion, not safety or appropriateness.The authors identify access controls, action restrictions, and human oversight for consequential operations.Source: §6 · p. 10
  • The paper locates procedures and assumptions across the main text and appendices, including training hyperparameters, hardware, prompts, and proof details.The reproducibility statement points to sections and appendices for task generation, verification, reward functions, evaluation protocols, and task-composition analysis.Source: §6 · p. 10

A PRELIMINARIES

  • RLVR trains an agent against a deterministic verifier that assigns binary rewards to completed trajectories rather than using a learned reward model.The agent interacts with a stateful environment through actions and observations; the task distribution is typically human-curated.Source: A PRELIMINARIES · p. 12
  • GRPO estimates advantages relative to a group of rollouts without a learned value function and optimizes a clipped surrogate objective with a KL penalty.The objective applies ratios and clipping per token, while masking environment observations from the agent-generated tokens used for updates.Source: A PRELIMINARIES · pp. 12–13

B PROOF OF PROPOSITION 1

The proof contrasts binary-reward collapse with subtask rewards: diverse progress among failed rollouts can preserve a learning signal, while the benefit is conditional on all sampled rollouts failing.

B PROOF OF PROPOSITION 1

  • With binary rewards, collapse occurs when all rollouts succeed or all fail, with probability p^G + (1 − p)^G.As solver success probability p approaches zero, the all-fail term approaches one.Source: B PROOF OF PROPOSITION 1 · p. 13
  • The reduction is conditional: a failed rollout completing every subtask receives the same reward as a successful rollout, so unconditional collapse is not always lower.The comparison concerns collapse conditional on all sampled rollouts failing.Source: B PROOF OF PROPOSITION 1 · p. 13
  • At p = 0.01, binary-reward collapse is approximately 0.85 with G = 16 and 0.53 with G = 64; reducing it below 0.05 requires at least 299 rollouts per task.Keeping collapse below a fixed threshold requires group size to grow inversely with solver success probability.Source: B PROOF OF PROPOSITION 1 · p. 13
  • When failed rollouts reach multiple subtask-completion levels, subtask rewards keep conditional collapse below one, and collapse decreases as group size grows.The reduction depends on how broadly failed rollouts are distributed across completion levels.Source: B PROOF OF PROPOSITION 1 · p. 13

C TRAINING ALGORITHM

Explorer-Zero alternates proposer and solver training: the proposer explores and supplies tasks with reference states, while the solver trains on verified subtask rewards; their updates adapt task difficulty.

C TRAINING ALGORITHM

  • The proposer is scored using solver rollouts, while the solver trains with GRPO on proposed tasks and subtask-level rewards.Invalid tasks with malformed outputs or unverifiable completion conditions are discarded from solver training and give the proposer zero reward.Source: C TRAINING ALGORITHM · p. 13
  • Starting from an initial environment state, the proposer explores, declares a candidate task, records subtask reference states, and snapshots a final reference state.The algorithm initializes proposer and solver from the base model and bounds proposer exploration by a turn budget.Source: C TRAINING ALGORITHM · p. 14
  • During solver training, rollouts start from the task’s initial state; final and subtask states are checked against their references before GRPO updates.The two agents are updated in alternation, encouraging the proposer to explore further and compose longer sequences as the solver improves.Source: C TRAINING ALGORITHM · p. 14

D IMPLEMENTATION DETAILS

The implementation uses shared base-model initialization and a four-loop proposer-then-solver schedule. On AppWorld, the full method continues improving during training, unlike the no-subtask variant, whose gains plateau earlier.

D IMPLEMENTATION DETAILS

  • The proposer and solver share Qwen3 base-model initialization, use rank-32 LoRA adapters, and train in four outer loops that update the proposer before the solver.Training costs are reported as roughly 15 GPU-node hours per ALFWorld run and 29 per AppWorld run on 8×H100 GPUs.Source: D IMPLEMENTATION DETAILS · p. 14

E.1 TRAINING CURVES

  • On AppWorld, the full method keeps improving in TGC and SGC, while the no-subtask variant remains near its level after the first 60 steps.The no-subtask variant plateaus earlier; the one-shot proposer improves initially but later loses much of that gain.Source: §E.1 · p. 14, Figure 5 · p. 15
  • Table 3 lists Explorer-Zero’s hyperparameters and specifies that each listed value applies across all environments.The supplied passage does not give the individual hyperparameter values.Source: Table 3 · p. 15
  • Figure 5 reports single-rollout checkpoint evaluations, so its endpoints are not directly comparable to Table 1’s averaged metric.The figure places TGC on the left and SGC on the right, with shaded standard-error bands.Source: Figure 5 · p. 15

E.2 ADDITIONAL ANALYSIS OF GENERATED TASK COMPOSITION

The analysis measures task composition from executed steps, environment changes, and declared subtask boundaries. Over training, proposals show more dependency structure and acceptance, while subtask supervision slows losses in exploratory breadth relative to a control.

E.2 ADDITIONAL ANALYSIS OF GENERATED TASK COMPOSITION

  • Composition diagnostics count task-relevant API-supported subtasks, verified checkpoints with further final-state change, and dependency links across subtask boundaries.For read-only subtasks, provenance must trace to a task-relevant API; setup operations are excluded, and checkpoints must occur at distinct, increasing execution steps.Source: §E.2 · pp. 15–16
  • From the first to last 10-step block, dependency-chained segments rise from 0.57 to 1.13, environment-grounded subgoals from 0.55 to 1.22, and verified segments from 0.29 to 0.77.Well-posed proposals rise from 56% to 77%, while distinct APIs per task fall from 5.9 to 5.2 and multi-app tasks from 27% to 18%; declared subgoals increase from 53% to 74% of tasks and average 0.89 to 1.19 per proposal.Source: §E.2 · p. 16
  • Without subtask rewards, well-posed proposals and execution success still rise, but effective APIs fall 26% versus 18% with supervision, and cross-application value flow falls 52% versus 30%.The authors interpret these measurements as suggesting subtask supervision encourages dependency structure while slowing loss of exploratory breadth.Source: §E.2 · p. 16

E.3 ADDITIONAL PROPOSER TRAINING DYNAMICS

  • The acceptance rate—the share passing the rule-based filter for solver training—increases from roughly 45% to around 80% over training.The filter requires a final task, a non-redundant subtask checklist, and consistency between mentioned applications or objects and the proposer trajectory.Source: §E.3 · p. 16
  • Task descriptions lengthen from roughly 25 tokens early in training to around 35 later, but token count alone does not establish compositionality or instruction quality.The increase accompanies growth in declared subtasks; task relevance and downstream utility are assessed in other analyses.Source: §E.3 · p. 16

F QUALITATIVE EXAMPLES

The qualitative examples illustrate proposers moving from single-state-change tasks toward tasks composed of multiple operations and subtasks. The appendix also provides proposer and solver prompt templates for all three environments.

F QUALITATIVE EXAMPLES

  • On AppWorld, an early Todoist example has no subtasks and requires one state change, while a later Spotify example declares subtasks and specifies a playlist with four songs.The Spotify example includes a setup login subtask that the prompt says not to declare, and the validity filter does not remove it.Source: F QUALITATIVE EXAMPLES · p. 17, Figure 7 · p. 17, Figure 8 · p. 18
  • On ALFWorld, an early proposer recovers from a failed cabinet placement by using a drawer, while a later example composes cooling a plate and placing it in a cabinet.The later task records the cooled plate as an intermediate checkpoint.Source: F QUALITATIVE EXAMPLES · p. 17, Figure 9 · p. 19, Figure 10 · p. 19
  • AppWorld examples also show a Spotify task built from songs absent from playlists and a cross-app task that clears an Amazon cart before creating a Todoist task.The cross-app exploration recovers from three API errors.Source: Figure 11 · p. 20, Figure 12 · p. 21

G PROMPT TEMPLATES

  • The appendix presents proposer and solver prompt templates for ALFWorld, ScienceWorld, and AppWorld.Proposer prompts instruct exploration without a given task and expose calls for declaring subtasks and finishing tasks.Source: G PROMPT TEMPLATES · p. 21

H LIMITATIONS

Snapshot-based verification assumes a resettable environment whose state can be recorded and compared, limiting the stated setting to environments with those capabilities. Extending reference-state matching to partially observable or irreversible environments remains open; proposer prompts may also bias generated tasks away from real-world tasks.

H LIMITATIONS

  • Snapshot-based verification requires resettable environments whose states can be recorded and compared, and extending reference-state matching to partially observable or irreversible settings remains open.The authors also note that proposer-prompt inductive biases may make generated task distributions differ from real-world tasks.Source: H LIMITATIONS · p. 27

Related papers

Loading 2610.19868v1…