Terminal-using agents benefit from reinforcement learning (RL) in coding, debugging, and other multi-step terminal tasks. In these tasks, later commands often depend on information or intermediate results produced by earlier commands. However, existing trajectory-level and step-level credit assignment methods do not explicitly trace the read-write dependencies through which commands affect the final outcome. Consequently, training signals could still be assigned to irrelevant operations, weakening learning from relevant steps. In this paper, we propose Dependency-Aware Group Policy Optimization (DepGPO), which uses execution dependencies between commands to guide credit assignment for terminal agents. Specifically, we construct a command dependency graph from execution traces and trace backward from the resources inspected by the task verifier. We then assign credit to relevant writes and their supporting reads along these paths, and use it to redistribute trajectory advantages across steps. Extensive comparative experiments and ablation studies demonstrate that DepGPO improves task performance and training stability on complex terminal tasks.
Figures & tables
Figure 1: Pilot analysis of credit assignment in terminal tasks. (a) With K=4 , an SFT policy yields zero group-relative advantages on 61% of tasks. (b) Sparse anchor-state recurrence in our terminal implementation of GiGPO. (c) Example command dependencies and raw credits; E denotes the resources read by the verifier. (d) Cumulative distributions of the fraction of commands connected to E in passing Terminal-Bench 2.0 reference trajectories ( n=51 ) and the subset with at least five commands ( n=18 ). Pink guides illustrate GRPO’s uniform step weights.
Figure 2: Overview of DepGPO. Unlike GRPO’s uniform trajectory-level assignment and GiGPO’s generic step-level grouping, DepGPO traces read–write dependencies to the verifier-inspected resources E and redistributes the group-relative advantage according to dependency-derived step factors. The example illustrates the transformation from raw credit to the final per-step advantage.
Figure 3: Illustration of write-credit assignment through direct and indirect dependencies.
Figure 4: Illustration of read-credit assignment through dependency paths in G .
Method
Qwen3.5-9B
Qwen3.6-27B
SETA
TMAX
SETA
TMAX
TB2.0
TB2.1
TB2.0
TB2.1
TB2.0
TB2.1
TB2.0
TB2.1
SFT
15.28 ± 0.81
16.48 ± 1.35
14.01 ± 2.38
10.56 ± 2.82
25.92 ± 0.72
26.37 ± 1.83
23.45 ± 2.97
24.27 ± 0.78
GRPO
11.09 ± 0.26
11.01 ± 0.67
14.91 ± 2.26
17.83 ± 0.57
25.09 ± 1.11
23.37 ± 0.67
23.82 ± 1.95
24.94 ± 0.45
DAPO
13.11 ± 0.13
13.26 ± 0.67
15.13 ± 1.32
13.86 ± 2.36
27.34 ± 2.16
28.16 ± 1.11
26.74 ± 2.34
25.09 ± 0.13
DPPO
15.36 ± 0.91
15.81 ± 0.47
17.23 ± 1.28
18.95 ± 2.36
28.24 ± 1.53
28.01 ± 0.34
26.07 ± 1.35
26.67 ± 1.94
Table 1: Task performance on Terminal-Bench 2.0 and 2.1. Results are reported as pass@1 (%), mean ± SD over three evaluation rounds; blue shading and underlining denote the best and second-best results within each setting, respectively.
Figure 5: Panels (a)–(c) compare training reward, policy entropy, and gradient norm of DepGPO, GRPO, and GiGPO on Qwen3.5-9B trained with SETA, with shading marking the late training window and entropy plotted on a logarithmic scale. Panel (d) further shows the standard deviation of DepGPO’s step factors across interaction steps, whose mean is fixed at one by normalization.
Variant
TB2.0
TB2.1
GRPO
11.09 ± 0.26
11.01 ± 0.67
Binary write contribution
23.07 ± 0.85 ↓ 2.17
22.55 ± 0.91 ↓ 2.09
Without verifier filtering
18.65 ± 1.03 ↓ 6.59
17.75 ± 1.19 ↓ 6.89
Without supporting-read credit
21.42 ± 0.94 ↓ 3.82
20.15 ± 1.13 ↓ 4.49
Direct writes only
23.45 ± 0.91 ↓ 1.79
23.00 ± 1.04 ↓ 1.64
Full DepGPO
25.24 ± 1.01
24.64 ± 2.36
Table 2: Ablation study of Qwen3.5-9B trained on SETA. Pass@1 (%), mean ± SD. Red arrows denote performance drops relative to Full DepGPO.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Definition
Cw,Cr
Disjoint sets of agent write commands and read commands.
G,GE
Command dependency graph and write-reachability graph.
E
Files, ports, and processes inspected by the verifier under the extraction rules.
Wc
Tracked file records written by command c , resolved at line level when available.
Dc,Ic
Records of c that qualify for direct and indirect contribution.
Contrib(c)
Contribution score of write command c .
Appendix
Table 3: Key notation used in the DepGPO credit-assignment procedure.
Condition
Result
No step information or unavailable credit module
Unit factors.
Missing usable verifier or agent-command records
Unit factors; the missing-trace case is recorded.
Empty command-credit output
Unit factors.
Si=∅
Unit factors.
Δi≤10−9
Unit factors, including equal-credit and all-zero cases.
Exception caught by the calling trainer
Unit factors and an error diagnostic.
Appendix
Table 4: Fallback conditions that retain the baseline GRPO advantage assignment. These cases use unit dependency factors, or disable dependency weighting in the baseline configuration, without removing the trajectory from the baseline reward and group-relative advantage computation.
Setting
SETA/9B
SETA/27B
TMAX/9B
TMAX/27B
Training conversations
79,882
79,882
16,355
16,355
Validation conversations
3,690
3,690
166
166
Maximum sequence length
8,192
8,192
32,768
32,768
Per-device micro-batch
1
1
1
1
Devices
6
4
4
4
Epochs
1
1
1
1
Appendix
Table 5: Supervised fine-tuning configurations. The 9B and 27B columns use Qwen3.5-9B and Qwen3.6-27B, respectively.
Setting
SETA/9B
SETA/27B
TMAX/9B
TMAX/27B
Candidate tasks
1,376
1,376
2,998
2,998
Zero successful attempts
639
279
2,200
1,950
Four successful attempts
200
501
258
400
Retained tasks
537
596
540
648
RL training tasks
483
536
486
583
RL validation tasks
54
60
54
65
Appendix
Table 6: Task selection using four attempts per candidate task. Each setting uses its own SFT checkpoint.
Setting
SETA/9B
SETA/27B
TMAX/9B
TMAX/27B
Tasks per update
4
4
4
4
Trajectories per task K
8
8
8
8
Trajectories per update
32
32
32
32
Policy updates
150
150
150
150
Optimizer
AdamW
AdamW
AdamW
AdamW
Learning rate
10−6
10−6
10−6
10−6
Appendix
Table 7: RL configurations for the GRPO and DepGPO comparison. Each column starts from its corresponding SFT checkpoint. Method-specific baseline components are retained separately.
Figure 6: Task-level success-rate differences between DepGPO and GRPO using Qwen3.5-9B trained on SETA and evaluated on Terminal-Bench 2.0 (a) and 2.1 (b). Each panel independently sorts 89 tasks by Δ , computed as DepGPO minus GRPO in percentage points. Green and orange bars indicate improvements and regressions, gray markers denote ties, and dashed lines show the mean difference over all tasks. Annotations highlight selected task-level differences.
Metric
Interpretation
Training reward
Terminal task performance observed during training.
Policy entropy
Concentration of the policy distribution over generated tokens.
Gradient norm
Magnitude of the actor update during policy optimization.
Step-factor std.
Variation in DepGPO’s allocation of the group-relative advantage across interaction steps.
Appendix
Table 8: Training diagnostics used in Figure 5 . These statistics characterize optimization behavior and are not used for checkpoint selection.
β
TB2.0
TB2.1
0.25
24.27 ± 1.19
23.75 ± 1.63
0.50
25.24 ± 1.01
24.64 ± 2.36
0.75
24.87 ± 0.91
24.12 ± 1.75
1.00
23.97 ± 1.28
23.45 ± 1.88
Appendix
Table 9: Sensitivity to the dependency-decay coefficient β using Qwen3.5-9B trained on SETA. Results are pass@1 (%), mean ± SD.
Metric
GRPO
DepGPO
Difference
Relative wall-clock time / update
1.00 ×
1.07 ×
+7.0%
Peak GPU memory
1.00 ×
1.01 ×
+1.0%
Dependency processing / trajectory
–
3.8 s
–
Additional model forward passes
0
0
0
Appendix
Table 10: Computational cost of DepGPO relative to GRPO using Qwen3.5-9B trained on SETA.
Statistic
Value
Commands per trajectory
6.8
Trajectories with usable dependency credit
82.4%
Trajectories using the unit-factor fallback
17.6%
Write commands with positive credit
38.7%
Read commands with positive credit
27.9%
Positive-credit writes with indirect contribution
18.6%
Appendix
Table 11: Dependency-trace statistics for Qwen3.5-9B trained on SETA.
Step
Command
Role
q(c)
t17
python3 <<’EOF’ … EOF
Supporting read
0.50
t18
echo "63841" > /app/answer.txt
Relevant write
1.00
t19
cat /app/answer.txt
Read with no downstream use
0
Appendix
Table 12: Supporting-read example from count-dataset-tokens . Only the commands relevant to this dependency are shown.
Step
Command
Contribution type
q(c)
t2
R -e ’…install_version("bnlearn", …)’
No recorded dependency
0
t3
cat > modify_bn.R <<’EOF’ … EOF
Indirect write
1.00
t4
Rscript modify_bn.R
Direct write
1.00
Appendix
Table 13: Indirect-write example from bn-fit-modify . The trajectory is a reference solution and therefore has no rollout-group advantage.
Step
Command
Dependency outcome
q(c)
t4
cat <<’EOF’ > …/meeting_scheduled.ics
Deleted before contribution
0
t5
cat /app/meeting_scheduled.ics
No downstream relevant write
0
t6
rm /app/meeting_scheduled.ics
No credited output
0
t7
printf ’…’ > …/meeting_scheduled.ics
Reaches E
1.00
t8
cat /app/meeting_scheduled.ics
No downstream relevant write
0
t10
cat <<’EOF’ > …/meeting_scheduled.ics
Reaches E
1.00
Appendix
Table 14: Example of verifier-relevant and irrelevant commands from constraints-scheduling .
Group-based reinforcement learning (RL) methods have achieved remarkable success in improving the performance of large language models (LLMs) and have been rapidly extended to agentic tasks. However, their credit assignment relies heavily on coarse-grained trajectory-level attribution according to final outcomes, making it difficult to capture the contribution of individual steps, such as valuable steps obscured within failed trajectories. To uncover latent information and enable more faithful step-level credit assignment, we propose Graph-based Group Policy Optimization (GraphGPO), which first aggregates all rollout trajectories into a unified state-transition graph and then estimates the distance from each state to the task goal using the global information encoded in the graph. Finally, GraphGPO assigns credit to each edge by estimating a graph-based advantage, based on how much the transition reduces the distance to the task goal. In this way, GraphGPO significantly improves training efficiency and achieves state-of-the-art performance across a range of challenging benchmarks.
Xin Cheng, Shuo He, Lang Feng +4
Nanyang Technological University, Singapore · Tongyi Lab, Alibaba Group · Southeast University, China
When training large language models with reinforcement learning, terminal rewards provide little guidance about which steps matter. Common methods for assigning step credit overlook that work built on uncorrected mistakes is wasted while independent work remains valid. With only a final success/failure reward, every step in a failed episode has zero total future reward, even when it made progress. We propose Dependency-Aware Reward Shaping (DARS), which represents task progress as predicates linked by prerequisite relations and assigns step-level credit over the dependency graph. An annotator marks which predicates each step verifies, invalidates, or repairs. Verified predicates are discounted according to graph distance from the nearest broken prerequisite, while independent predicates are unaffected. Repairs update these weights based on any errors that remain; invalidated predicates need re-verification to regain credit. A fixed potential converts these annotations into signed per-step rewards. A common reward and annotation interface allows DARS to integrate with a range of reasoning and agentic training methods, such as GiGPO and ARPO/AEPO, without changing their rollout strategies or optimizers. Across five task families and models from 1.5B to 8B, DARS improves success by up to 10 points over GiGPO trained with the same budget and harness (ALFWorld), raises the WebShop task score and Search-R1 QA accuracy, complements AEPO's entropy-based training on AIME24/25 with a Python interpreter, and exceeds OmniOPD in controlled tool-free reasoning comparisons at 1.7B and 4B. Ablations show that step-level credit, dependency attenuation, and graph topology each contribute. On ALFWorld, a distilled 8B annotator matches the API annotator, enabling DARS to run efficiently without a frontier judge. Code is available at https://github.com/JianhuiWei7/DARS.
Ziyi Chen, Yan Zhang, Jianhui Wei +2
University of Illinois Urbana-Champaign · National University of Singapore · Zhejiang University +1
Group Relative Policy Optimization (GRPO) and related policy-gradient methods for training language model agents collapse an entire multi-turn rollout into a single scalar trajectory reward before it enters the policy update. When the task composes distinct skills, especially under sparse and delayed environmental feedback, this collapsing is lossy: the optimizer must implicitly infer which competency drove the outcome and how that should change behavior. We argue the right primitive is not a better scalar but a decomposition: trajectory reward should be split along subtasks before it enters the policy update. We introduce Reinforcement Learning with Decomposed Subtasks (RLDS), whose core is Subtask-Decomposed Advantage Estimation (SDAE): a replacement for the scalar GRPO advantage that splits trajectory reward into per-subtask shares on a fixed taxonomy, computes a group-relative advantage per subtask, and distributes per-token credit by weighting each subtask's advantage by its importance, concentrating it around the step where a reflection marks that subtask's execution as consequential. We evaluate on four agentic benchmarks: FrozenLake (sparse grid navigation), HotpotQA (multi-hop QA, one retrieval tool), ScienceWorld (long-horizon embodied science), and DeepResearch (long-form research, four tools, composite rubric reward). Heterogeneity diagnostics emitted during training show where decomposition pays off - gains scale with subtask heterogeneity, largest on the high-heterogeneity tasks ScienceWorld (+11.5 points, paired-bootstrap 95% CI [+9.8, +13.3]) and FrozenLake (+9.8 points, [+7.0, +12.8]), and within noise on HotpotQA and DeepResearch, where the diagnostics predicted little to recover. ScienceWorld is also more compute-efficient under RLDS than scalar GRPO (-10.9% wall-clock per step), as long rollouts amortize the fixed reflect-and-grade overhead.