Credit Where It Matters: Dependency-Aware Policy Optimization for Terminal Agents

Yu Li; Guangfeng Cai; Long-Fei Li; Shuo Han; Shengtian Yang; Han Luo; Kaibing Yang; Lei Feng

cs.AIOct 2, 2026

Credit Where It Matters: Dependency-Aware Policy Optimization for Terminal Agents

Authors: Yu Li, Guangfeng Cai, Long-Fei Li, Shuo Han, Shengtian Yang, Han Luo, Kaibing Yang, Lei Feng

Organizations: School of Computer Science and Engineering, Southeast University, Nanjing, China · Huawei Noah’s Ark Lab, China

Abstract

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 $\pm$ 0.81	16.48 $\pm$ 1.35	14.01 $\pm$ 2.38	10.56 $\pm$ 2.82	25.92 $\pm$ 0.72	26.37 $\pm$ 1.83	23.45 $\pm$ 2.97	24.27 $\pm$ 0.78
GRPO	11.09 $\pm$ 0.26	11.01 $\pm$ 0.67	14.91 $\pm$ 2.26	17.83 $\pm$ 0.57	25.09 $\pm$ 1.11	23.37 $\pm$ 0.67	23.82 $\pm$ 1.95	24.94 $\pm$ 0.45
DAPO	13.11 $\pm$ 0.13	13.26 $\pm$ 0.67	15.13 $\pm$ 1.32	13.86 $\pm$ 2.36	27.34 $\pm$ 2.16	28.16 $\pm$ 1.11	26.74 $\pm$ 2.34	25.09 $\pm$ 0.13
DPPO	15.36 $\pm$ 0.91	15.81 $\pm$ 0.47	17.23 $\pm$ 1.28	18.95 $\pm$ 2.36	28.24 $\pm$ 1.53	28.01 $\pm$ 0.34	26.07 $\pm$ 1.35	26.67 $\pm$ 1.94

Table 1: Task performance on Terminal-Bench 2.0 and 2.1. Results are reported as pass@1 (%), mean

\pm

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 $\pm$ 0.26	11.01 $\pm$ 0.67
Binary write contribution	23.07 $\pm$ 0.85 $\downarrow$ 2.17	22.55 $\pm$ 0.91 $\downarrow$ 2.09
Without verifier filtering	18.65 $\pm$ 1.03 $\downarrow$ 6.59	17.75 $\pm$ 1.19 $\downarrow$ 6.89
Without supporting-read credit	21.42 $\pm$ 0.94 $\downarrow$ 3.82	20.15 $\pm$ 1.13 $\downarrow$ 4.49
Direct writes only	23.45 $\pm$ 0.91 $\downarrow$ 1.79	23.00 $\pm$ 1.04 $\downarrow$ 1.64
Full DepGPO	25.24 $\pm$ 1.01	24.64 $\pm$ 2.36

Table 2: Ablation study of Qwen3.5-9B trained on SETA. Pass@1 (%), mean

\pm

SD. Red arrows denote performance drops relative to Full DepGPO.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Definition
$\mathcal{C}_{\mathrm{w}},\mathcal{C}_{\mathrm{r}}$	Disjoint sets of agent write commands and read commands.
$G,\ G_{E}$	Command dependency graph and write-reachability graph.
$E$	Files, ports, and processes inspected by the verifier under the extraction rules.
$\mathcal{W}_{c}$	Tracked file records written by command $c$ , resolved at line level when available.
$D_{c},\ I_{c}$	Records of $c$ that qualify for direct and indirect contribution.
$\operatorname{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.
$\mathcal{S}_{i}=\varnothing$	Unit factors.
$\Delta_{i}\leq 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	$\mathbf{537}$	$\mathbf{596}$	$\mathbf{540}$	$\mathbf{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

\Delta

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

$\beta$	TB2.0	TB2.1
0.25	24.27 $\pm$ 1.19	23.75 $\pm$ 1.63
0.50	25.24 $\pm$ 1.01	24.64 $\pm$ 2.36
0.75	24.87 $\pm$ 0.91	24.12 $\pm$ 1.75
1.00	23.97 $\pm$ 1.28	23.45 $\pm$ 1.88

Appendix

Table 9: Sensitivity to the dependency-decay coefficient

\beta

using Qwen3.5-9B trained on SETA. Results are pass@1 (%), mean

\pm

SD.

Metric	GRPO	DepGPO	Difference
Relative wall-clock time / update	1.00 $\times$	1.07 $\times$	+7.0%
Peak GPU memory	1.00 $\times$	1.01 $\times$	+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)$
$t_{17}$	python3 <<’EOF’ … EOF	Supporting read	0.50
$t_{18}$	echo "63841" > /app/answer.txt	Relevant write	1.00
$t_{19}$	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)$
$t_{2}$	R -e ’…install_version("bnlearn", …)’	No recorded dependency	0
$t_{3}$	cat > modify_bn.R <<’EOF’ … EOF	Indirect write	1.00
$t_{4}$	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)$
$t_{4}$	cat <<’EOF’ > …/meeting_scheduled.ics	Deleted before contribution	0
$t_{5}$	cat /app/meeting_scheduled.ics	No downstream relevant write	0
$t_{6}$	rm /app/meeting_scheduled.ics	No credited output	0
$t_{7}$	printf ’…’ > …/meeting_scheduled.ics	Reaches $E$	1.00
$t_{8}$	cat /app/meeting_scheduled.ics	No downstream relevant write	0
$t_{10}$	cat <<’EOF’ > …/meeting_scheduled.ics	Reaches $E$	1.00

Appendix

Table 14: Example of verifier-relevant and irrelevant commands from constraints-scheduling .

Explore similar work

Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning
May 26, 2026Xin Cheng, Shuo He, Lang Feng +4Group Relative Policy Optimization Credit Assignment in RL
Nanyang Technological University, Singapore · Tongyi Lab, Alibaba Group · Southeast University, China
Dependency-Aware Reward Shaping for Agentic Reinforcement Learning
Oct 1, 2026Ziyi Chen, Yan Zhang, Jianhui Wei +2RL for Language Models Agentic RL
University of Illinois Urbana-Champaign · National University of Singapore · Zhejiang University +1
Reinforcement Learning with Decomposed Subtasks
Sep 22, 2026Mattie Terzolo, Mikolaj Sacha, Ayan Sinha +1Group Relative Policy Optimization Credit Assignment in RL
Upwork

May 26, 2026J/K move · Enter open · S save

Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning

Xin Cheng, Shuo He, Lang Feng, HaiYang Xu+3

Nanyang Technological University, Singapore · Tongyi Lab, Alibaba Group · Southeast University, China

Group Relative Policy Optimization Credit Assignment in RL Step-Level Credit Assignment in RL Step-Level Credit Assignment Credit Assignment RL for LLM Agents

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

Reinforcement Learning with Decomposed Subtasks