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

1. Introduction

• In the pilot study, 61% of task groups had zero group-relative advantages, and only four of 25 anchor states recurred in the two traced tasks with the most anchors.Among passing reference trajectories, the median fraction of commands on dependency paths to verifier-read resources was 0.57, falling to 0.18 for trajectories with at least five commands.Source: §1 · p. 2, Figure 1 · p. 2
• DepGPO traces resource reads, writes, and subsequent output uses backward from verifier-read resources, crediting relevant writes and their supporting reads.Write credit reflects the fraction of written lines that reach verifier-read resources; supporting-read credit decays with shortest-path distance.Source: §1 · p. 2
• The paper reports consistent task-performance improvements and more stable reinforcement learning with Qwen3.5-9B and Qwen3.6-27B using SETA and TMAX training data.The contribution summary reports delayed training degradation and improved stability.Source: §1 · p. 3

Reinforcement Learning with Outcome Supervision

• Outcome-supervised RL uses response- or trajectory-level rewards, while sparse terminal rewards provide limited intermediate-command guidance and continued updates can become unstable.PPO uses a learned value model, whereas GRPO uses group-relative rewards without a separate critic (Schulman et al., 2017; Shao et al., 2024).Source: §2 · p. 3

Training Stability

• Stability methods such as DAPO, DPPO, and TMAX improve optimization stability but do not identify which intermediate commands contribute to outcomes.TMAX combines DPPO with an FP32 language-model head and larger rollout groups to reduce numerical mismatch and training collapse (Ivison et al., 2026).Source: §2 · p. 3

Process Feedback and Step-Level Credit Assignment

• Process-feedback and step-level methods provide finer feedback, but learned scores require supervision, predefined penalties cover specified behaviors, and state-based methods may omit file or process changes.Examples include human- or continuation-based process reward models, rule-based penalties, and state comparisons or graphs.Source: §2 · p. 3

Execution Traces for Terminal Agents

• Execution-trace work studies observability, failure attribution, and provenance; DepGPO instead uses traces as credit-assignment evidence by following dependencies from verifier-inspected resources.CodeTracer localizes failure onset for diagnostic replay, while Shepherd supports branching from recorded intermediate states and computes advantages from additional rollouts.Source: §2 · p. 3

3.2. Command Dependency Graph

• DepGPO constructs a directed graph of commands linked by file-content and standard-output dependencies, then identifies the resources inspected by the verifier as the backward-tracing target.Commands are the units of dependency analysis, even though optimization applies to tokens generated in each response.Source: §3.2 · pp. 4–5, §3.1 · p. 4

3.3. Dependency-Aware Credit Assignment

• Write credit is the fraction of a command’s written lines that contribute directly or indirectly to verifier-inspected resources; supporting read commands receive credit through paths to positive-credit writes.For indirect write contributions, consuming commands must write to another file without overwriting the input lines being counted.Source: §3.3 · pp. 5–6

3.4. Advantage Redistribution and Policy Optimization

• Within each trajectory, step credits are compared relative to the minimum credit, and steps without traced operations or usable variation fall back to factor one.The factors are normalized by a token-weighted mean before multiplying the trajectory advantage, preserving relative weights and the advantage’s overall scale.Source: §3.4 · p. 7
• DepGPO retains GRPO’s policy optimization procedure and clipping configuration, changing only the distribution of group-relative advantages across interaction steps.Nonnegative dependency factors change signal magnitude, not its sign; the resulting per-step advantages are assigned to tokens in their respective steps.Source: §3.4 · p. 8

4.1. Experimental Setup

• Experiments cover four model–data configurations on Terminal-Bench 2.0 and 2.1, with methods sharing selected tasks and controlled GRPO comparisons holding optimization settings fixed.Source: §4.1 · pp. 8–9

4.2. Main Results

• DepGPO achieves the best pass@1 across all eight settings, beating each setting’s strongest competing RL baseline by 3.22–10.03 percentage points.Source: §4.2 · p. 9, Table 1 · p. 9

4.3. Training Stability

• In the runs shown, DepGPO maintains higher late-training reward and comparatively stable entropy and nonzero gradients, while GRPO and GiGPO show reward or optimization deterioration.Source: §4.3 · p. 10, Figure 5 · p. 10
• DepGPO’s step-factor standard deviation generally rises during training while its normalized mean stays one, indicating increasingly differentiated weights across interaction steps.Source: §4.3 · p. 10, Figure 5 · p. 10

4.4. Ablation Study

• Binary write credit drops performance by 2.17 and 2.09 points on Terminal-Bench 2.0 and 2.1; removing verifier filtering drops it another 4.42 and 4.80 points versus binary credit.Source: §4.4 · p. 11
• Removing supporting-read credit lowers performance by 3.82 and 4.49 points, while direct-write-only credit lowers it by 1.79 and 1.64 points.The ablations indicate that information-gathering reads and earlier writes on dependency paths both contribute useful credit.Source: §4.4 · p. 11

• DepGPO traces written content to the verifier’s read set, assigns graded credit to relevant writes, and uses dependency paths to credit their supporting reads.Source: §5 · p. 11
• Experiments on Terminal-Bench 2.0 and 2.1 demonstrate improved task performance, while training analyses show more stable learning.Source: §5 · p. 11
• The findings support observable read-write dependencies as an effective basis for fine-grained credit assignment in terminal agents.Source: §5 · p. 11

A.1. Notation and Recorded Events

• Writes are tracked by file and line when available, while reads are recorded at file level; any command with a recorded write is classified as a write command.Unresolved writes use a whole-file marker, and multiple writes by one command are pooled. Path identity is normalized but remains alias-sensitive because symbolic links are not resolved; line ownership is not rebased after later edits, allowing limited positional mismatch.Source: §A.1 · pp. 16–17

A.2. Construction of the Command Dependency Graph

• The command dependency graph links later commands to earlier writers whose recorded file content they read, and links commands that reuse typed values printed earlier.File-read dependencies are established before the current command’s writes update ownership; overwriting alone creates no edge. Prompt-provided values are excluded from standard-output matching, and execution-order edges make the graph acyclic.Source: §A.2 · pp. 17–18

A.3. Verifier Read Set and Indirect Write Contributions

• DepGPO assigns credit to writes that directly affect verifier-inspected resources or contribute through qualifying downstream writes, tracing backward from verified endpoints.The verifier endpoint set includes files read or probed, plus checked ports and processes; indirect attribution requires a later write command to read the earlier writer’s input and propagate information to another file without replacing that input. Reverse traversal identifies qualifying earlier writers, and each record is counted at most once.Source: §A.3 · pp. 18–19

A.4. Complete Command Credit

• Write credit is the fraction of a command’s tracked records that contribute to verification, while read credit sums distance-decayed contributions from reachable positive-credit writes.A matching non-file resource gives credit one when no tracked file record exists; reads without a path to a positive-credit write receive zero. Credits measure recorded relevance, not correctness, and the signed group-relative advantage determines reinforcement or penalty.Source: §A.4 · pp. 19–20

A.5. Advantage Redistribution and Policy Objective

• DepGPO sums command credits within each step, rescales nondegenerate factors within a trajectory, then normalizes final weights by their loss-included token counts.The token-weighted mean redistributed advantage remains equal to the original group-relative advantage, and nonnegative weights preserve its sign; empty or degenerate tracing falls back to baseline assignment. These coefficient identities do not guarantee unchanged policy-gradient or clipped-objective dynamics, and DepGPO retains the GRPO clipping rule and token-mean reduction.Source: §A.5 · pp. 20–21

A.6. End-to-End Procedure

• The end-to-end pipeline computes resource extraction and dependency-based credit from recorded trajectories, then holds them fixed during the corresponding policy updates.Step factors are mapped to policy-token positions and normalized with the policy-loss mask before being applied to baseline group-relative advantages and the actor update.Source: §A.6 · p. 22, §A.5 · p. 22
• The procedure samples trajectories, runs each task verifier, builds command dependency and write-consumption relations, and traces backward from verifier endpoints to compute write credit.Each qualifying write record is counted once.Source: §A.6 · p. 22
• Read credit, aggregated command credits, and step factors are expanded and normalized over policy-generated tokens before redistributing advantages and updating the policy.Unit-factor fallbacks are applied when necessary; the updated policy then collects the next trajectory group.Source: §A.6 · p. 23

B. Experimental Setup and Reproducibility

• All methods use supervised fine-tuning followed by reinforcement learning, with SETA and TMAX paired separately with Qwen3.5-9B and Qwen3.6-27B.Within each model and data setting, methods share the SFT checkpoint, task pool, splits, and agent scaffold; GRPO and DepGPO also share the objective and optimization settings.Source: B. Experimental Setup and… · p. 23

B.1. Supervised Fine-Tuning

• SFT uses AdamW at a 10−5 learning rate, with weight decay 0.01, gradient clipping at 1.0, and one epoch over each training corpus.The learning rate warms up over the first 3% of training and stays constant afterward.Source: §B.1 · p. 23
• Training retains preceding conversational context but computes loss only on assistant tokens, truncating overlength conversations from the left.Models are updated in bfloat16 using FSDP, gradient checkpointing, and sequence packing; SETA and TMAX use different sequence budgets.Source: §B.1 · p. 23

B.2. Selecting Training Tasks

• Tasks are retained when four SFT attempts produce both successes and failures, targeting groups with nonzero centered group-relative advantages.Retained success rates are 0.25, 0.50, or 0.75; task pools are fixed across RL methods within each setting.Source: §B.2 · pp. 23–24
• Approximately 61% of SETA/9B candidate tasks are excluded: 839 of 1,376 have either zero or four successful attempts.Pool sizes vary by model and source; for TMAX, the retained pools include 540 of 2,998 tasks for 9B and 648 for 27B.Source: §B.2 · p. 24

B.3. Reinforcement Learning

• RL runs for 150 updates, each sampling four tasks and eight trajectories per task, while DepGPO weights group-relative advantages before policy updates.The verifier supplies a binary terminal outcome; the outcome reward and policy objective remain unchanged in the GRPO comparison.Source: §B.3 · p. 25

B.4. Checkpoint Selection

• Each method’s checkpoint with the highest RL-validation success rate is used for final benchmark evaluation, allowing selection of an earlier checkpoint if performance later deteriorates.Terminal-Bench scores are reserved for reporting selected policies, not checkpoint selection.Source: §B.4 · p. 26

B.5. Benchmark Evaluation and Score Aggregation

• Selected checkpoints are evaluated separately on Terminal-Bench 2.0 and 2.1, with five attempts per task and three complete evaluation repeats.Each attempt starts from the task’s initial environment and allows at most 56 interaction steps.Source: §B.5 · p. 26
• Pass@1 averages each task’s five binary outcomes and then averages across tasks; reported standard deviations measure evaluation variability for a fixed checkpoint.Treating a task as solved if any attempt succeeds would estimate pass@5 instead.Source: §B.5 · p. 26

B.6. Data Separation and Verifier Information

• Benchmark tasks are excluded from training and checkpoint selection, while verifier-inspected resources are recorded after a trajectory and used to compute weights rather than as generation inputs.Access to verifier scripts through the terminal depends on the agent scaffold, independently of the weighting procedure.Source: §B.6 · pp. 26–27

C. Task-Level Paired Comparison

• 14.2 pp on Terminal-Bench 2.0 and 13.6 pp on Terminal-Bench 2.1 are the mean task-level improvements, with DepGPO improving on 31 and 33 tasks, respectively.The corresponding ties/regressions are 53/5 and 54/2; among tasks with different observed success rates, 86.1% and 94.3% favor DepGPO.Source: Figure 6 · p. 27, C. Task-Level Paired Comparison · p. 27
• Several task-level gains are large, including approximately 80 pp on extract-moves-from-video and 67 pp on git-leak-recovery and pypi-server on Terminal-Bench 2.0.On Terminal-Bench 2.1, git-leak-recovery improves by approximately 87 pp, while three named tasks improve by approximately 73 pp each.Source: C. Task-Level Paired Comparison · pp. 27–28
• Ties make up most tasks on both benchmarks, so the median task-level difference is zero despite positive means.Terminal-Bench 2.1 has two more improved tasks and three fewer regressed tasks than 2.0, yet its mean improvement is slightly smaller; independently sorted panels do not show whether the same tasks improve.Source: C. Task-Level Paired Comparison · p. 28
• The task-level comparison supports task-dependent benefits in this Qwen3.5-9B SETA setting, not universal improvement or statistical significance for every task.Higher observed success rates do not necessarily mean tasks were newly solved, and equal rates can include shared failures.Source: C. Task-Level Paired Comparison · pp. 27–28

D. Additional Training Stability Analysis

• The additional training-stability analysis covers reward, policy entropy, gradient norm, and DepGPO step-factor dispersion across the specified model and training runs.Panels (a)–(c) compare three methods using Qwen3.5-9B on SETA; panel (d) compares DepGPO step-factor dispersion at two model scales.Source: D. Additional Training Stability… · p. 28, §D.1 · p. 29

D.1. Diagnostics and Plotting Protocol

• Training diagnostics are smoothed for visualization, and the shaded late-training region marks differing optimization behavior without affecting training or checkpoint selection.Table 8’s statistics characterize optimization behavior and are not used for checkpoint selection.Source: §D.1 · p. 29, Table 8 · p. 29

D.2. Training Reward Dynamics

• DepGPO fluctuates but maintains overall higher late-stage reward, while GRPO loses much of its earlier gain and GiGPO deteriorates earlier and remains comparatively low.The reward curves establish an association with more stable late-stage optimization in the examined runs, not that credit assignment alone caused baseline degradation.Source: §D.2 · p. 29

D.3. Policy Entropy and Gradient Norm

• The baselines show substantial late-stage entropy or gradient changes, while DepGPO’s entropy is comparatively stable and it continues to receive nonzero updates.GRPO’s gradient norm is exactly zero on 43 of the final 45 unsmoothed updates; entropy and gradient norm are not performance metrics in isolation.Source: §D.3 · p. 30

D.4. Evolution of Credit Redistribution

• For both Qwen3.5-9B and Qwen3.6-27B trained on SETA, step-factor standard deviation generally grows later in training, indicating more differentiated allocation across steps.The trajectories fluctuate, and this descriptive comparison does not establish that model size causes differences between them.Source: §D.4 · p. 30

D.5. Relationship Between Credit Redistribution and Stability

• The analyzed runs associate dependency-aware redistribution with more stable late-stage optimization, but do not establish that individual dependency edges or step factors cause particular diagnostic changes.Such causal attribution would require interventions on individual trajectories or dependency paths.Source: §D.5 · pp. 30–31

E.1. Sensitivity to Dependency Decay

• DepGPO’s average pass@1 is 25.24/24.64 on Terminal-Bench 2.0/2.1 at β = 0.5, versus 24.27/23.75 at β = 0.25 and 23.97/23.45 at β = 1.0.β = 0.75 yields 24.87/24.12; moderate decay performs best in this setting, while performance remains relatively stable across a broad range.Source: Table 9 · p. 31, §E.1 · p. 31

E. Sensitivity and Computational Cost

• Moderate dependency decay provides the strongest performance in the examined setting, and the added trace-processing cost is modest relative to the full training loop.The sensitivity analysis indicates effectiveness across a range of coefficients; the cost analysis attributes overhead mainly to recorded-trace processing rather than neural-network computation.Source: §E.1 · p. 31, §E.2 · p. 32

E.2. Computational Overhead

• DepGPO adds approximately 7.0% to average update time and changes peak GPU memory by 1.0% in the tested Qwen3.5-9B SETA configuration.Dependency processing takes approximately 3.8 seconds per trajectory and requires no additional language-model inference.Source: §E.2 · p. 32

E.3. Dependency-Trace Statistics

• 82.4% of trajectories have usable dependency credit, while 17.6% revert to unit factors because no usable relative credit can be constructed.Approximately 38.7% of traced write commands and 27.9% of read commands receive positive credit.Source: §E.3 · p. 32
• Among positive-credit writes, 18.6% receive at least part of their credit through downstream write dependencies, and credited reads reach writes at a mean shortest distance of 1.74 edges.These statistics indicate that supporting information can extend beyond an immediately adjacent command.Source: §E.3 · pp. 32–33

E.4. Summary

• The trace statistics and sensitivity analysis together indicate that credit redistribution applies to most trajectories and frequently credits both relevant writes and supporting reads.The added computation remains small relative to the full training loop and requires no additional model evaluations.Source: §E.3 · p. 32, §E.4 · p. 33

F.1. Supporting Reads

• A read receives supporting credit when its output feeds a later relevant write, unlike a read that merely inspects the answer after it has been written.In the count-dataset-tokens example, a command’s printed result is used by the following answer-file write, whereas the later read receives zero credit.Source: §F.1 · p. 34

F.2. Indirect Write Contribution

• The bn-fit-modify example gives indirect credit to all 102 tracked lines of a script read by a command that writes verifier-inspected outputs.The script itself is not in the verifier’s read set; the execution step that writes the inspected outputs receives direct credit.Source: §F.2 · pp. 34–35

F.3. Overwritten and Irrelevant Commands

• In constraints-scheduling, overwritten output and read-backs that support no later positive-credit write receive zero credit, while records reaching the final inspected file receive full credit.This successful trajectory illustrates that DepGPO does not assign equal responsibility to every action.Source: §F.3 · p. 35

F.4. From Command Credit to the Training Signal

• Raw command credits are aggregated within interaction steps, normalized into step factors, then token-normalized to produce the per-step advantages.The resulting weights determine how strongly the trajectory-level signal is applied to tokens generated in each step.Source: §F.4 · p. 36
• Dependency-derived weights change the magnitude, not the sign, of the original group-relative advantage assigned to tokens in each step.Positive advantages strengthen reinforcement at higher-weight steps, negative advantages strengthen the penalty, and zero advantages remain zero.Source: §F.4 · p. 36
• DepGPO does not assign a separate notion of command-level correctness; execution dependencies determine how the outcome-derived signal is distributed across commands.The terminal outcome continues to determine whether the trajectory is reinforced or penalized.Source: §F.4 · p. 36