# Explorer-Zero: Improving Self-Play for Long-Horizon Tasks

> Explorer-Zero jointly generates compositional tasks and verifiable subtask rewards via self-play, outperforming human-data RL on AppWorld without annotations and improving subsequent RL.

- **Source:** [arXiv](https://arxiv.org/abs/2610.19868)
- **Published:** 2026-10-24
- **Permalink:** https://picx.dev/p/wmOaat
- **Whiteboard:** https://picx.dev/p/wmOaat/image

## Summary

# 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**

| Method | #annotation | ALFWorld (Qwen3-4B) | ScienceWorld (Qwen3-4B) | AppWorld TGC (4B-inst) | AppWorld SGC (4B-inst) | AppWorld TGC (30B-inst) | AppWorld SGC (30B-inst) |
|---|---|---|---|---|---|---|---|
| **Without human-annotated training data** | | | | | | | |
| Baseline | n=0 | 17.14 ± 5.7 | 7.03 ± 0.5 | 14.03 ± 5.1 | 3.95 ± 3.2 | 25.15 ± 5.2 | 8.04 ± 7.5 |
| R-Zero | n=0 | 24.28 ± 1.5 | 24.76 ± 0.9 | 17.41 ± 5.8 | 5.80 ± 1.6 | 47.32 ± 1.8 | 25.00 ± 2.7 |
| Self-Challenging | n=0 | 66.40 ± 3.5 | 35.69 ± 0.7 | 32.20 ± 3.2 | 16.25 ± 2.5 | 51.93 ± 1.3 | 32.25 ± 2.3 |
| **Ours** | **n=0** | **85.07 ± 1.6** | **42.92 ± 0.7** | **38.39 ± 2.4** | **16.96 ± 1.9** | **59.67 ± 3.1** | **39.29 ± 3.2** |
| **With human-annotated training data** | | | | | | | |
| RL | full | 95.71 ± 0.9 | 49.63 ± 0.4 | 46.38 ± 3.2 | 25.00 ± 2.4 | 62.65 ± 1.8 | 38.39 ± 3.2 |
| RL + Ours | full | 98.57 ± 0.9 | 63.26 ± 0.4 | 50.00 ± 2.0 | 32.14 ± 3.0 | 69.20 ± 4.6 | 53.12 ± 3.0 |

### Ablations

**Table 2: Ablation of Explorer-Zero components**

| | | ALFWorld | ScienceWorld | AppWorld TGC | AppWorld SGC |
|---|---|---|---|---|---|
| Self-play | one-shot proposer | 59.29 ± 9.4 | 4.80 ± 2.0 | 29.46 ± 4.7 | 16.96 ± 2.0 |
| | interactive proposer | 65.71 ± 2.3 | 24.70 ± 1.2 | 45.83 ± 1.9 | 33.04 ± 2.7 |
| | + subtask | 84.29 ± 1.5 | 42.92 ± 0.7 | 59.67 ± 3.1 | 39.29 ± 3.2 |

### 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

---

_Markdown view of https://picx.dev/p/wmOaat, served by PicX — AI-generated visual whiteboard summaries of research papers._