Reinforcement Learning with Decomposed Subtasks

Group Relative Policy Optimization (GRPO) and other reinforcement learning policy-gradient methods for training language model agents collapse an entire multi-turn rollout into a single scalar trajectory reward before that signal enters the policy update. When the underlying task is the composition of distinct skills, and especially when environmental feedback is sparse and delayed, this collapsing is lossy: the optimizer is left to implicitly infer which competency drove the outcome and how that should translate into behavioral change. We argue that the right primitive for these settings is not a better scalar but a decomposition: trajectory reward should be split along subtasks before it ever enters the policy update. We introduce Reinforcement Learning with Decomposed Subtasks (RLDS), a recipe whose core is Subtask-Decomposed Advantage Estimation (SDAE): a replacement for the scalar GRPO advantage that decomposes trajectory reward into per-subtask shares on a fixed subtask taxonomy, computes a group-relative advantage per subtask, and distributes per-token credit by weighting each subtask's advantage by its importance and concentrating it around the step where the reflection identifies that subtask's execution as being consequential to the outcome. We evaluate the resulting recipe on four agentic benchmarks spanning a range of complexity: FrozenLake (sparse grid navigation), HotpotQA (multi-hop QA with a single retrieval tool), ScienceWorld (long-horizon embodied science), and DeepResearch (long-form research with four tools and a composite rubric reward). Per-task heterogeneity diagnostics emitted during training show where decomposition pays off, and the empirical results match: gains scale with subtask heterogeneity, largest on the high-heterogeneity tasks ScienceWorld ($+6.3$ points, 95% CI $[-0.3,+12.8]$) and FrozenLake ($+5.9$ points, $[-0.7,+12.5]$), and within noise on the lower-heterogeneity HotpotQA and DeepResearch, which the diagnostics flagged as having little for decomposition to recover. ScienceWorld is additionally more compute-efficient under RLDS than under scalar GRPO ($-10.9\%$ wall-clock per training step), as long rollouts amortize the fixed reflect-and-grade overhead.