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

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

cs.AIOct 14, 2026

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

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

Organizations: ETH Zurich · Qualcomm AI Research‡

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

Figures & tables

Figure 1: Overview of Explorer-Zero. Left: the proposer ${{\pi}_{\textnormal{P}}}$ explores the environment, declares an initial task intent ( declare ), completes subtasks ( subtask ) and the final task ${x}$ ( finish ). Each subtask and finish call snapshots the environment as a reference state, yielding ${s}^{\operatorname{ref}}_{1},\dots,{s}^{\operatorname{ref}}_{{K}}$ and ${{s}^{\operatorname{ref}}_{\textnormal{final}}}$ . Right: the solver ${{\pi}_{\textnormal{S}}}$ ’s traversed states are matched against the reference states to compute ${{R}^{\textnormal{solver}}}$ , and the resulting solve rate determines ${{R}^{\textnormal{proposer}}}$ .

Without human-annotated training data
	#annotation	ALFWorld	ScienceWorld	AppWorld
		Qwen3-4B	Qwen3-4B	Qwen3-4B-inst		Qwen3-30B-A3B-inst
				TGC	SGC	TGC	SGC
Baseline	n=0	17.14 $\pm$ 5.7	0 7.03 $\pm$ 0.5	14.03 $\pm$ 5.1	0 3.95 $\pm$ 3.2	25.15 $\pm$ 5.2	0 8.04 $\pm$ 7.5
In-Context	n=1	19.28 $\pm$ 7.7	11.40 $\pm$ 0.4	12.28 $\pm$ 3.7	0 6.58 $\pm$ 4.6	28.95 $\pm$ 5.0	15.79 $\pm$ 7.7
	n=2	18.57 $\pm$ 4.7	0 9.50 $\pm$ 0.4	15.35 $\pm$ 4.0	0 1.32 $\pm$ 1.3	27.63 $\pm$ 4.8	11.84 $\pm$ 6.2

Table 1: Experimental results on ALFWorld, ScienceWorld, and AppWorld. We report success rates on ALFWorld (unseen validation split) and ScienceWorld (test split), and TGC and SGC (task and scenario goal completion) on AppWorld (test normal split). We report means and standard deviations over four samples per task prompt.

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

Table 2: Ablation of Explorer-Zero components. Results on ALFWorld are on valid-seen, and results on AppWorld are with Qwen3-30B-A3B-Instruct-2507.

Figure 2: Task relevance of AppWorld proposer trajectories with and without subtask supervision. Left two: Trajectory lengths are similar across the two variants, while the proposer with subtasks makes fewer API calls on average. Right two: With subtasks, a larger fraction of steps and API calls contributes to the final task. We identify contributing interactions using backward program slicing ( Weiser, 1984 ) : they either produce target-state changes or support those changes through Python data flow.

Figure 3: Proposer and solver training dynamics on AppWorld. Left: The proposer shifts its effort from environment exploration toward executing the task it proposes: exploration turns decrease from

14

7

, while solving turns rise from

7

10

. Center: The mean number of declared subtasks increases from around

0.8

2.3

. Right: The fraction of zero-reward solver rollouts with subtask supervision remains consistently below the no-subtask ablation, ending near

22\%

versus

39\%

Figure 4: Left: On AppWorld, tasks with greater multi-step solution complexity (measured by the number of test-case predicates, API calls, or lines of code in their reference solutions) are substantially harder for the RL agent trained on human-authored tasks. Center: Subtask supervision in Explorer-Zero provides little consistent benefit on simpler tasks but substantially higher success in the highest-complexity bins. Right: Per-app success rates on AppWorld test_normal , where each task counts toward every app it requires. The largest gains occur for Todoist and Splitwise, which are the only apps appearing exclusively in multi-app tasks.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

	ALFWorld, ScienceWorld	AppWorld
Base model	4B	4B, 30B-A3B
Outer self-play loops $N$	$4$
Proposer / solver steps per loop $M_{\textnormal{P}}$ , $M_{\textnormal{S}}$	$25$ / $25$	$15$ / $50$
Proposer exploration budget $T_{\textnormal{P}}$ (turns)	$30$	$40$
Max solver turns	$30$	$40$
Context length (tokens)	$40{,}960$

Appendix

Table 3: Hyperparameters of Explorer-Zero. A single value applies to all environments.

Figure 5: Learning curves on AppWorld (Qwen3-30B-A3B-Instruct-2507) (left: TGC, right: SGC; shaded bands: standard error). Curves evaluate one single rollout per task at each checkpoint, so endpoints are not directly comparable to the reported averaged metric in Table 1 . Without any human-annotated task, the full method ( with subtask ) keeps improving throughout training, whereas removing the subtask reward ( no subtask ) plateaus earlier and converges to lower scores. R-Zero and one-shot proposer verify tasks against solver-rollout consensus states instead of proposer snapshots, with interactively and one-shot generated tasks, respectively.

Figure 6: Additional proposer training dynamics on AppWorld. Left: The fraction of proposed tasks accepted for solver training increases from roughly

45\%

early in training to around

80\%

in later stages. Right: Task descriptions become longer over training, rising from roughly

25

tokens to around

35

, with substantial variation between steps.

Reward Decomposition

See all 11 papers

The Chase Is the Curriculum, the Capture Anchors the Credit: Pursuit-Evasion Self-Play for Zero-Data LLM Reasoning
Aug 22, 2026Jing Yu, Shengchao Chen, Yiyun TanSelf-Play RL RL for Language Model Reasoning
College of Computer and Information Engineering, Xi’an University of Architecture and Technology · Australian Artificial Intelligence Institute, University of Technology Sydney
Tool-R0: Self-Evolving LLM Agents for Tool-Learning from Zero Data
Feb 24, 2026Emre Can Acikgoz, Cheng Qian, Jonas Hübotter +3LLM Agent Training Self-Evolving Agents
UIUC · ETH Zurich
G-Zero: Self-Play for Open-Ended Generation from Zero Data
May 11, 2026Chengsong Huang, Haolin Liu, Tong Zheng +7Open-Ended Generation Self-Play RL
Washington University in St. Louis · University of Virginia · University of Maryland +1

Aug 22, 2026J/K move · Enter open · S save

The Chase Is the Curriculum, the Capture Anchors the Credit: Pursuit-Evasion Self-Play for Zero-Data LLM Reasoning

Jing Yu, Shengchao Chen, Yiyun Tan

College of Computer and Information Engineering, Xi’an University of Architecture and Technology · Australian Artificial Intelligence Institute, University of Technology Sydney

Self-Play RL RL for Language Model Reasoning Curriculum RL Reinforcement Learning with Verifiable Rewards Reward Design for RL

Open paper AskPDF arXiv

Reinforcement learning with verifiable rewards has become the dominant recipe for improving large language model reasoning, yet it presumes large human-curated task collections. Zero-data self-play removes this dependency, but existing methods vet learnability only by probing candidates and rejecting post hoc, never learning where along an environment's difficulty axis to place a task, and credit the solver with sparse terminal rewards alone. We recast zero-data self-play as a pursuit-evasion game: in LURE, an LLM evader positions tasks along each environment's difficulty axis to stay one step ahead of a planner-executor pursuer that hunts it down through verifiable interaction. The evader is trained on a capture-frontier reward that peaks when the solver captures it on exactly half of its rollouts, turning barely catchable into a learned positioning strategy rather than a hand-tuned rejection band. The pursuer earns capture-anchored dense process credit, in which monotone verifier progress is group-normalized jointly with the terminal capture under a round-anchored KL that keeps the co-evolution stable. Across three verifiable reasoning environments and three backbone families, LURE outperforms advanced baselines under unified/specialist settings, while the unified model attains stronger aggregate OOD zero-shot accuracy than all trained baselines across nine held-out benchmarks from three task families.

Abstract

Reward Decomposition

Explore similar work

The Chase Is the Curriculum, the Capture Anchors the Credit: Pursuit-Evasion Self-Play for Zero-Data LLM Reasoning

Tool-R0: Self-Evolving LLM Agents for Tool-Learning from Zero Data

G-Zero: Self-Play for Open-Ended Generation from Zero Data