TL;DR
DARS turns annotated task dependencies into signed step rewards: an unresolved mistake discounts dependent progress while independent work retains credit. Experiments cover household tasks, shopping, retrieval, and mathematics, with the clearest matched gain on a 1.5B ALFWorld agent.
Why it matters
Terminal success rewards poorly distinguish useful progress from wasted work in failed trajectories. Explicit prerequisite graphs offer an auditable process signal that can augment existing agent RL, while raising practical questions about annotation quality, graph design, and additional training cost.
Key findings
- 01
An annotator identifies task predicates and per-step verification, invalidation, and repair events. A fixed graph potential turns changes in dependency-weighted progress into signed rewards. Repair removes a break, but an invalidated predicate still needs verification to regain support.
- 02
The study uses Qwen2.5-1.5B/7B agents for ALFWorld and WebShop, Qwen2.5-7B for Search-R1, Qwen3-8B with Python for agentic mathematics, and Qwen3-1.7B/4B on DAPO-Math for tool-free reasoning. DARS integrates with GiGPO, ARPO/AEPO, or a token-level credit interface.
- 03
With the same 500-step budget and evaluation harness on ALFWorld, the 1.5B DARS agent achieves 96.9% unseen-game success versus 86.9% for local GiGPO, a 10.0 percentage-point gain. At 7B, the corresponding results are 98.6% versus 98.1%. These are matched training-step budgets, not matched total compute costs.
- 04
On held-out Search-R1 questions, DARS reaches 41.6% exact-match accuracy versus 39.5% for GiGPO after one epoch each. The separate shared-pool diagnostic reuses training questions and unequal step counts, so its larger gain is not a held-out generalization result.
- 05
WebShop headline policies continue trained GiGPO parents. Equally extending GiGPO explains the 1.5B parent-relative gain; at 7B, DARS retains a 1.5-point strict-success advantage over the equally extended control. Graded task score and completed-purchase success are distinct metrics.
- 06
For Qwen3-8B with Python, AEPO plus DARS has a 63.6% mean across the evaluated checkpoint grid versus 61.7% for AEPO on AIME24/25. DARS does not improve the analogous ARPO grid mean, and the authors report roughly ±5 points of decoding variation per cell.
Evidence & limits
The interactive learning curves come from single training runs. Repeated decoding estimates evaluation variability, not robustness across training seeds.
DARS depends on annotator judgments and domain-specific graphs. Applicability to open-ended tasks without clear predicates or prerequisite relations remains unestablished, and policy/annotator scaling is not systematically studied.
Published baseline rows, local reproductions, continuation runs, and from-initialization runs use different budgets. Parent-relative WebShop gains and best-checkpoint mathematics scores must not be presented as uniform compute-matched improvements.
Annotation adds work. Reported ALFWorld step times were measured on shared hosts and a shared endpoint, not in a controlled speed benchmark; they do not establish a general wall-clock or total-cost advantage.
Tool-free mathematics has few negatively credited segments, so those experiments mainly test placement of positive feedback rather than recovery from errors. Gains on the aggregate also need not hold on every individual benchmark.
Scaling dimensions
Models, methods & benchmarks
- Models
- Qwen2.5-1.5B, Qwen2.5-7B, Qwen3-1.7B, Qwen3-4B, Qwen3-8B
- Algorithms
- DARS, GiGPO, ARPO, AEPO
- Benchmarks
- ALFWorld, WebShop, Search-R1, AMC, AIME 2024, AIME 2025
Topics