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

Summary (Overview)

• Explorer-Zero is a novel self-play framework for training LLM agents on long-horizon interactive tasks in stateful environments, jointly generating tasks and fine-grained, verifiable rewards through environment interaction.
• The framework introduces a learned proposer that explores environments, constructs compositional tasks, and records intermediate and final states as verification checkpoints, while a solver is trained on these generated tasks.
• The method provides theoretical guarantees that subtask rewards reduce "reward collapse" (where all failed rollouts receive identical zero rewards, eliminating learning signal) in group-normalized RL.
• Empirical results show Explorer-Zero outperforms existing self-play baselines (Self-Challenging, R-Zero) across ALFWorld, ScienceWorld, and AppWorld without human-annotated training tasks, and improves subsequent RL on human-annotated tasks.
• On AppWorld, the 30B agent reaches 59.67% task goal completion (TGC) without human annotations, approaching the 62.65% achieved by RL on human-annotated tasks.

Introduction and Theoretical Foundation

Background and Motivation

Training LLM agents with reinforcement learning with verifiable rewards (RLVR) traditionally depends on human-annotated tasks paired with reliable success checks. This is expensive for stateful environments: task designers must understand what the current state permits, specify meaningful changes, and define verification methods. Human task construction limits how broadly agentic RL can scale.

Key Observations

1. Compositionality: Long-horizon agentic tasks are often compositional—completion requires a sequence of meaningful state changes (e.g., locate an item before picking it up). A proposer that acts in the environment can discover feasible components and compose them into grounded tasks.

2. Sparse reward problem: Delayed outcomes of long-horizon tasks make binary rewards particularly limiting. In group-normalized RL, this causes reward collapse: when all sampled trajectories receive the same reward (e.g., all fail), their advantages vanish despite meaningful differences in progress.

Theoretical Foundation

The paper formalizes the reward collapse problem. For a binary task reward with success probability $p$ and group size $G$, a group collapses with probability:

$$p^G + (1-p)^G$$

Conditional on all rollouts failing, binary rewards collapse with probability one. The paper proves:

Proposition 1 (Subtask rewards reduce reward collapse): Under Eq. (7) (the subtask reward), conditional on all sampled rollouts failing, the collapse probability is:

$$\sum_{j=0}^{K} \tilde{q}_j^G$$

where $\tilde{q}_j$ is the probability that a failed rollout completes exactly $j$ subtasks. This probability is strictly below one whenever at least two subtask-completion counts have positive probability among failed rollouts.

Methodology

Problem Setup

An agent with policy $\pi_\theta$ interacts with a stateful environment $\varepsilon$: given a task $x$, it produces a trajectory $\tau = (a_1, o_1, \dots, a_T, o_T)$ of actions and observations traversing environment states $s_0, \ldots, s_T$.

Proposer: Interactive Generation of Compositional Tasks

The proposer $\pi_P$ interacts with the environment and generates:

• Task description $x$ (natural language)
• Final reference state $s_{\text{final}}^{\text{ref}}$
• Optional intermediate checkpoints $\{(g_k, s_k^{\text{ref}})\}_{k=1}^K$

Proposer phases:

1. Exploration phase: Examines the environment over multiple turns to identify a candidate task
2. Solving phase: Attempts to complete its own task, declaring meaningful subtasks as they are completed

Control tools:

• declare(task_description) — ends exploration, declares candidate task
• subtask(subtask_description) — records completed subtask and reference artifact
• finish(task_description) — submits final task and records $s_{\text{final}}^{\text{ref}}$

Proposer reward:

$$R^{\text{proposer}}(x, \tau^{\text{prop}}) = \begin{cases} R^{\text{difficulty}}(x) + R^{\text{subtask}}(x, \tau^{\text{prop}}) + R^{\text{diversity}}(\tau^{\text{prop}}), & \text{if the proposal is valid}, \\ 0, & \text{otherwise}. \end{cases} \tag{1}$$

The components are:

$$R^{\text{difficulty}}(x) = 1 - |2\hat{p}(x) - 1| \tag{2}$$ $$R^{\text{subtask}}(x, \tau^{\text{prop}}) = w_{\text{sub}} K \tag{3}$$ $$R^{\text{diversity}}(\tau^{\text{prop}}) = w_{\text{div}} |\mathcal{A}(\tau^{\text{prop}})| \tag{4}$$

where $K$ is the number of declared subtasks, $\mathcal{A}(\tau^{\text{prop}})$ is the set of distinct proposer action types, and $w_{\text{sub}}, w_{\text{div}} > 0$ are weights.

Solver: Training with State-Based Verification

Final-task reward:

$$R(x, \tau^{\text{solv}}) = \mathbb{I}\{s_T \simeq s_{\text{final}}^{\text{ref}}\} \tag{5}$$

Subtask reward (for $K > 0$):

$$R^{\text{subgoal}}(x, \tau^{\text{solv}}) = \frac{1}{K} \sum_{k=1}^{K} \mathbb{I}\{\exists s \in \mathcal{S}(\tau^{\text{solv}}): s \simeq s_k^{\text{ref}}\} \tag{6}$$

where $\mathcal{S}(\tau^{\text{solv}}) = \{s_0, \ldots, s_T\}$ is the set of visited states.

Combined solver reward:

$$R^{\text{solver}}(x, \tau^{\text{solv}}) = \begin{cases} 1, & \text{if } R(x, \tau^{\text{solv}}) = 1, \\ R^{\text{subgoal}}(x, \tau^{\text{solv}}), & \text{otherwise}. \end{cases} \tag{7}$$

Training Algorithm

The proposer and solver are trained in alternating phases. The proposer's reward includes a difficulty term (maximized at 50% solve rate), a subtask incentive, and a diversity term. Tasks are filtered by validity rules before solver training.

Empirical Validation / Results

Main Results

Table 1: Experimental results on ALFWorld, ScienceWorld, and AppWorld

Ablations

Table 2: Ablation of Explorer-Zero components

Key Findings

• vs. Self-Challenging baseline: +18.67 points on ALFWorld, +7.23 on ScienceWorld, +7.74 TGC on AppWorld (30B)
• vs. human-data RL: 59.67 vs. 62.65 TGC on AppWorld (30B)—a small gap without using task annotations
• RL + Ours: Improves over RL alone across all benchmarks (e.g., +13.63 on ScienceWorld, +6.55 TGC on AppWorld)
• Interactive proposal adds gains over one-shot; subtask supervision adds a further 18.58 points on ALFWorld, 18.22 on ScienceWorld, and 13.84 TGC on AppWorld

Analysis Results

1. Task-relevant composition: Subtask supervision increases the fraction of contributing interactions (identified via backward program slicing) without increasing trajectory length; the proposer makes fewer API calls on average.

2. Proposer learns structure: Exploration turns decrease from ~14 to 7, solving turns rise from ~7 to 10, and declared subtasks increase from ~0.8 to 2.3 during training.

3. Learning signal preserved: The fraction of zero-reward solver rollouts with subtask supervision ends near 22% vs. 39% without.

4. Benefits concentrate on complex tasks: Gains are largest in the highest-complexity bins (measured by test-case predicates, API calls, or lines of code) and on apps appearing exclusively in multi-app tasks (Todoist, Splitwise).

Theoretical and Practical Implications

Theoretical Contributions

• Reward collapse analysis: The paper provides a formal characterization of when binary rewards fail to provide learning signal in group-normalized RL, and proves that subtask rewards strictly reduce collapse probability when failed rollouts complete different numbers of subtasks.
• Scaling analysis: Shows that as $p \to 0$, keeping collapse probability below a fixed threshold requires group size $G$ to grow on the order of $1/p$ for binary rewards, making subtask rewards a more sample-efficient alternative.

Practical Implications

• Removing the annotation bottleneck: Explorer-Zero demonstrates that self-play can generate training tasks and verification signals for stateful environments without human annotation, achieving performance close to human-data RL.
• Self-play as pretraining: The method serves as an effective initialization for subsequent RL on human-annotated tasks, improving final performance across all benchmarks.
• Fine-grained supervision from task generation: The same proposer trajectory that generates tasks also provides verifiable checkpoints, unifying task generation and reward shaping in a single framework.

Conclusion

Explorer-Zero uses environment interaction to jointly generate compositional tasks and fine-grained, verifiable rewards. The theoretical analysis characterizes when subtask rewards preserve learning signal despite task failure, and experiments show that subtask supervision encourages task-relevant dependencies, with the largest gains on tasks requiring multiple dependent operations. Across three benchmarks, Explorer-Zero outperforms evaluated self-play baselines without human-annotated training tasks and improves subsequent human-data RL.

Future directions suggested by this work include:

• Deployment safeguards for real-world use (access controls, action restrictions, human oversight)
• Further investigation of dependency modeling between subtasks (currently treated as an unordered checklist)
• Extension to other stateful environments and larger-scale models