SGR-OPSD: Learning from Subgoal Plans with Graph-Regularized Credit Assignment for Agentic Reinforcement Learning

Introduction

Reinforcement learning (RL) enables LLM-based agents to solve complex tasks through multi-turn interactions, ranging from household manipulation to online shopping ([9, 14]). Effective training requires fine-grained supervision to evaluate intermediate decisions within a trajectory.

On-Policy Self-Distillation (OPSD) ([15]) provides dense feedback by conditioning a teacher model on privileged training-time information to score student-sampled actions ([7, 5]). This feedback complements the sparse outcome rewards used in methods like Group Relative Policy Optimization (GRPO) ([8]), enabling the student to internalize inference-unavailable guidance. OPSD thus offers a promising framework for dense supervision in agentic RL.

Existing methods supply privileged information through trajectory-derived skills or reference answers, integrating teacher feedback via advantage reweighting or auxiliary distillation objectives ([10, 12, 6]). AgentOPSD further accumulates likelihood evidence across turns, while TASPO maps action-level support into bounded advantage weights ([11, 13]). However, two key gaps remain between such supervision and true task progress. First, privileged guidance often lacks an explicit, ordered plan for the task at hand. For “cool bread and place it on the countertop”, a structured plan—locate the bread, cool it, then place it—makes the required progression explicit. Second, teacher–student logprobability gaps measure shifts in model preference rather than progress made through real interactions; even plan-conditioned feedback can incorrectly favor actions that stray from successful continuations. Thus, effective credit assignment requires both task-specific planning information and a mechanism that grounds its influence in execution evidence. To bridge these gaps, our approach uses subgoal plans to structure teacher guidance and uses evidence from the Subgoal Progress Graph to calibrate the resulting credit.

We propose SGR-OPSD, illustrated in Figure 1. An LLM generates a fixed subgoal plan from the task description alone, providing the scoring teacher with explicit task-progression guidance. We derive a constrained KL-regularized rule that converts action-level teacher–student likelihood evidence into bounded exponential weights on GRPO advantages. The rule accounts for advantage signs and enforces a fixed token-weighted budget within each trajectory, establishing a teacher reference for turn-level credit. To calibrate these weights, we construct a Subgoal Progress Graph from student rollouts and derive action preferences from empirical $Q - V$: each action’s discounted return relative to the visit-weighted state average. A joint objective incorporates these preferences while regularizing the allocation toward the teacher reference, connecting plan-guided supervision with evidence of task progress. The trained student requires neither the plan nor the graph at inference. We evaluate SGR-OPSD on ALFWorld, WebShop, and SearchQA with Qwen2.5-3B and Qwen2.5-7B. On the 7B model, it reaches 85.8% success on ALFWorld and 78.2% on WebShop, improving over GRPO by 7.4 and 7.6 percentage points, respectively.

Our contributions are as follows:

• We propose leveraging subgoal plans as privileged supervision and derive a constrained KL-regularized formulation to allocate turn-level credit via bounded exponential weights.

• We develop a Subgoal Progress Graph that derives action preferences from empirical return estimates to calibrate teacher-reference weights, while preserving advantage signs and a fixed token-weighted budget per trajectory.

• Extensive experiments across three environments and two model scales demonstrate the superiority of SGR-OPSD, outperforming GRPO by up to 7.6 percentage points and achieving an 85.8% success rate on ALFWorld.

Related Works

On-Policy Self-Distillation for LLMs

Self-distillation derives the teacher from the student and conditions it on privileged training-time information [10 b]. Existing works integrate diverse privileged signals via distinct mechanisms: Skill-SD leverages trajectory-derived skills [10], RLSD scales token updates using log-probability gaps between an answer-conditioned teacher and the student [12], and SDAR gates SkillBank guidance alongside RL (Liu et al., 2026). However, these privileged signals often contain irrelevant noise and lack explicit task-progress planning. To address this, SGR-OPSD uses a fixed, LLM-generated subgoal plan derived solely from the task description as privileged information and applies a constrained KL-regularized objective to transform action-level evidence into bounded turn weights.

Credit Assignment for Multi-Turn Agents

While GRPO provides trajectory-level advantages under outcome rewards, it fails to distinguish the contributions of individual turns [8]. Recent lines of work refine this coarse outcome signal: AgentOPSD accumulates privileged likelihood evidence via recursive belief updates [11], TASPO converts action-level support into bounded advantage weights [13], and AlignOPSD aligns sibling contexts to allocate credit across spans and turns [1]. Although such teacher likelihood preferences offer dense feedback, they lack explicit measurements of task progress. To bridge this gap, SGR-OPSD constructs a Subgoal Progress Graph from student rollouts, leveraging graph-derived action comparisons to calibrate turn-level credit from a subgoal-conditioned teacher.

Method

SGR-OPSD combines plan-conditioned teacher preferences with rollout-derived outcome evidence for turn-level credit assignment. Constrained KL weighting converts teacher feedback into reference weights, which the Subgoal Progress Graph calibrates through action comparisons (Figure 2).

Background

We consider multi-turn tasks where an agent interacts with an environment to complete an instruction $x$. Given a task $x$, the rollout policy $\pi_{\theta_{\mathrm{old}}}$ samples $K$ trajectories $\{\tau_i\}_{i=1}^{K}$. Each trajectory $\tau_i$ consists of $N_i$ turns indexed by $t$, with $k$ indexing individual tokens within a response. At turn $t$, given context $h^S_{i,t}$, the agent generates a response $y_{i,t}$ containing action $a_{i,t}$ and receives the next observation.

Outcome-based policy optimization assigns each turn a base advantage $A_{i,t}$, where positive values reinforce the sampled turn and negative values discourage it. Self-distillation supplements this sparse outcome feedback by re-scoring student-sampled trajectories using privileged information. Both scoring branches share the pre-update parameters $\theta_{\mathrm{old}}$, so their likelihood difference reflects the effect of privileged information.

Subgoal-Guided Credit Weights

Subgoal-conditioned supervision. Subgoal plans make the intermediate requirements of task completion explicit. We employ a fixed, ordered plan $z(x)$, generated by DeepSeek-V3.1 ([2]) solely from the task instruction $x$, as privileged information. $z(x)$ combines task-specific intermediate goals and ordering constraints without requiring prior task interactions or successful trajectories (Appendix § 6). Figure 2(b) illustrates how this plan conditions teacher scoring to yield subgoal-guided teacher–student log-likelihood gaps.

Specifically, the teacher branch receives the privileged context $h^T_{i,t}$ augmented with $z(x)$, whereas the student operates on the standard context $h^S_{i,t}$. Token probabilities for branch $B \in\{T,S\}$ are defined as $\pi^B_{i,t,k} = \pi_{\mathrm{old}}(y_{i,t,k} \mid h^B_{i,t}, y_{i,t,<k})$, with both branches retaining identical response prefixes $y_{i,t,<k}$. Summing the token-level log-probability differences over the token positions $\mathcal{A}_{i,t}$ of the executed action yields the action-level gap:

The gap $d_{i,t}$ measures how the plan changes the action’s log-likelihood, providing dense action-level evidence for credit assignment.

Constrained KL weighting. Subgoal support should strengthen positive updates and soften negative ones. We derive turn weights by balancing signed teacher evidence against KL regularization toward unit weights:

where $w = (w_{i,t})_{i,t}$ collects the turn weights and $w^{\mathrm{ref}}$ is their optimized teacher reference. The feasible set $\mathcal{W}$ bounds each weight by $1-\epsilon\le w_{i,t} \le1+\epsilon$ ($0 \le\epsilon< 1$), fixes $w_{i,t}=1$ when $A_{i,t}=0$, and imposes a token-weighted budget for each trajectory:

where $m_{i,t}$ counts effective response tokens in turn $t$. Thus, $p_{i,t}$ weights turns by their token share, and the budget redistributes emphasis while keeping the weighted mean at one. Within this budget, the signed teacher-support term is

where $d_{i,t}$ is the action-level gap in Equation (1) and $s_{i,t}=\operatorname{sign}(A_{i,t})$. The sign factor makes stronger teacher support favor larger weights for positive advantages and smaller weights for negative ones.

The KL term limits departures from unit weights, with $T>0$ controlling its strength. We use the token-weighted generalized KL divergence

where $u$ is a positive weight vector and $v$ its positive reference, with entries $u_{i,t}$ and $v_{i,t}$. In Equation (2), these are $w$ and the all-ones vector $\mathbf{1}$, respectively. For $A_{i,t}\ne0$, this objective yields

where $\nu_i$ is the trajectory-specific multiplier enforcing the budget (Appendix § 7). These bounded weights provide the reference for calibration by the Subgoal Progress Graph.

Subgoal Progress Graph

To complement teacher preferences with outcome evidence, we merge matched states across sampled rollouts into a Subgoal Progress Graph. Transition counts define empirical values:

Here $v,v'$ are current and successor nodes, $r\in\{0,1\}$ is the success reward, and $\gamma\in(0,1)$ discounts continuation. The expectation averages recorded transitions; $\widehat{\pi}(a\mid v)$ is the fraction of visits to $v$ taking action $a$. The indicator $I$ permits continuation only for nonterminal transitions with remaining budget and a successor recorded as a source node.

The relative graph signal is

Here $v_{i,t}$ is the pre-action node, $b_G>0$ bounds the signal, and positive $\delta_{i,t}$ indicates above-average empirical return.

Graph-derived action comparisons. The Subgoal Progress Graph determines action ordering; calibration translates these preferences into bounded weight adjustments. Beyond node matching for value estimation, comparisons require matching plans, student contexts, and remaining budgets, with all associated visits scoreable and having nonzero advantages:

Here $g$ collects turn signals; $H_a$ averages unique visits equally within trajectories, then across trajectories. Preferred pairs $e=(a,b)$ form $\mathcal{E}$. The same $H_a$ aggregates credit corrections below; graph-score magnitudes do not set the correction margin.

Joint credit calibration. Graph-preferred actions should receive stronger reinforcement for positive advantages and softer penalties for negative ones. We parameterize the turn weights as

Here $c$ collects the credit corrections $c_{i,t}$ and $w(c)$ their resulting weights. With $s_{i,t}$ defined above, increasing $c_{i,t}$ favors the action under either advantage sign. We balance teacher retention against graph preferences:

where $D_p$ is defined in Equation (5), $T_G>0$ controls anchoring to the teacher reference $w^{\mathrm{ref}}$, and $\beta\ge0$ scales the graph preference penalty

Here $b_e=H_a-H_b$ for each preferred pair $e=(a,b)\in\mathcal{E}$, so $b_e^{\top}c$ is the difference in mean corrections. With $[u]_+=\max(u,0)$, the penalty encourages this difference to reach margin $\mu\ge0$. The weight $\rho_e$ normalizes comparison count and coefficient scale (Appendix § 7). The optimization is subject to

These constraints preserve the token-weighted budget and weight bounds, with zero-advantage turns unchanged. Graph comparisons therefore redistribute emphasis within each trajectory; trajectories without eligible comparisons retain their teacher reference exactly.

Policy Optimization

The calibrated weights redistribute outcome-based credit through

Here $w_{i,t}^{*}=w_{i,t}(c^{*})$ is the calibrated weight from Equation (11). The resulting advantage $\widetilde{A}_{i,t}$ is shared by all effective response tokens in the turn, including reasoning tokens. The student minimizes

Here $\theta$ denotes the student parameters, $\mathcal{L}_{\mathrm{policy}}$ is the base clipped policy loss, and sg stops gradients through the advantages. The term $\mathcal{L}_{\mathrm{KL}}$ regularizes the student toward the reference policy with coefficient $\lambda_{\mathrm{KL}}$; Teacher and graph guidance thus enter the policy update through $\hat{A}$.

Experiments

We evaluate SGR-OPSD across three interactive environments and two model scales to examine whether subgoal-guided, graph-calibrated credit improves policy learning.

Experimental Setup

Benchmarks and metrics. For ALFWorld ([9]), we evaluate success on the 140-task seen split across six household task categories: Pick, Look, Clean, Heat, Cool, and Pick2. For WebShop ([14]), we evaluate product search and selection on 500 goals, reporting task score and full-task success rate. SearchQA follows Search-R1 ([4]); we report exact-match accuracy on 51,713 questions across NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, MuSiQue, and Bamboogle. Together, these environments test sequential state changes, constraint satisfaction, and evidence gathering.

Baselines. We compare with Vanilla and Skill-Prompt as training-free references, GRPO [8] as the outcome-based learner, and OPSD [16], GRPO+OPSD, Skill-SD [10], RLSD [12], SDAR [6], and AgentOPSD [11] as self-distillation baselines. Qwen3.5-Plus and DeepSeek-V3.1 provide additional closed-source model references.

Training configuration. We use the Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct backbones and carry out three independent training runs with seeds $\{0, 42, 2026\}$. We train SGR-OPSD on 8 NVIDIA A100 GPUs for 150 policy updates, with eight rollouts per task and a learning rate of $10^{-6}$. The maximum interaction lengths are 50, 15, and 4 turns for ALFWorld, WebShop, and SearchQA, respectively. We set $\epsilon= 0.1$, $T = T_G = 1$, $\beta= 2$, $\mu= 0.02$, and $\gamma= 0.1$. We provide subgoal-generation prompts in Appendix § 6 and environment-specific training and evaluation settings in Appendix § 8.

Main Results

Stronger multi-turn task completion. SGR-OPSD leverages task-specific subgoals and Subgoal Progress Graph to calibrate turn-level credit redistribution. As shown in Table 1, this method consistently improves task completion across both model scales, achieving the highest ALFWorld macro-average and top performance on both WebShop metrics among all baselines. At 7B scale, it achieves 85.6% success on ALFWorld and 78.2% on WebShop. The performance gain over GRPO holds across both scales, with improvements of 7.4–7.6 pp on ALFWorld and 5.7–7.6 pp on WebShop success, underscoring the benefit of augmenting outcome feedback with structured credit allocation.

Method	Pick	Look	Clean	Heat	Cool	Pick2	Avg	NQ	Triv	Pop	Hotp	2Wk	MuS	Bam	Avg	Score	Succ.
Closed-Source Models
Qwen3.5-Plus	82.9	30.8	66.7	6.3	44.0	66.7	49.5	28.5	55.1	35.0	28.6	37.2	23.5	42.8	35.8	9.8	9.5
DeepSeek-V3.1	91.4	69.2	48.1	50.0	32.0	54.2	57.5	20.6	64.0	35.6	35.4	31.0	18.6	54.4	37.1	10.2	8.4
Qwen2.5-3B-Instruct
Vanilla	44.4	11.1	6.2	15.4	28.6	12.5	19.7	24.6	48.1	31.0	26.3	25.3	7.2	21.5	26.3	6.7	0.8
GRPO	91.4	66.6	75.3	58.3	61.3	62.5	69.3	45.3	61.2	44.9	40.1	38.1	15.1	31.2	39.4	78.5	63.1
Skill-Prompt	51.7	66.7	48.4	0.0	4.3	10.0	30.2	23.7	46.2	30.6	24.4	22.1	7.5	12.5	23.9	0.2	0.8
OPSD	48.8	41.7	16.7	0.0	15.8	16.7	23.3	0.1	0.1	0.1	0.0	0.0	0.0	0.0	0.0	11.3	3.1
GRPO+OPSD	95.2	59.2	84.0	60.4	66.7	61.1	71.1	45.0	61.2	44.7	39.4	40.0	14.8	30.1	39.3	80.6	63.3
Skill-SD	81.8	43.3	56.9	39.8	42.0	45.3	51.5	44.1	60.7	43.8	39.3	40.2	16.3	34.4	39.8	75.6	58.8
RLSD	88.6	56.4	76.5	75.0	60.0	58.3	69.1	44.0	59.6	43.0	40.3	43.0	18.2	34.4	40.4	79.7	62.4
SDAR	96.2	61.5	86.4	70.8	69.3	65.3	74.9	44.5	60.0	43.6	39.5	37.5	15.7	31.2	38.9	72.3	57.5
AgentOPSD	91.4	53.8	82.7	58.3	65.3	59.7	68.6	43.0	59.4	45.1	36.7	38.3	12.9	24.8	37.2	71.3	54.7
AlignOPSD	82.9	53.8	70.4	50.0	80.0	58.3	65.9	44.7	60.3	44.7	39.8	40.3	14.5	28.8	39.0	75.9	58.6
SGR-OPSD	97.1	69.2	81.5	75.0	68.0	70.8	76.9	45.4	62.0	45.4	40.3	41.5	15.2	34.6	40.6	85.5	68.8
Qwen2.5-7B-Instruct
Vanilla	36.1	22.2	3.1	0.0	0.0	0.0	10.2	25.2	50.8	29.5	29.0	29.0	10.4	23.7	28.2	5.9	1.6
GRPO	90.5	69.2	88.9	79.2	73.3	68.1	78.2	48.2	64.0	45.8	43.9	45.0	20.2	43.2	44.3	81.7	70.6
Skill-Prompt	51.7	50.0	32.3	5.3	4.3	0.0	23.9	30.9	52.1	32.7	32.7	27.9	12.7	66.1	36.4	1.7	0.8
OPSD	50.0	60.0	22.7	21.4	17.6	9.5	30.2	8.8	8.6	17.5	2.5	4.2	0.5	1.2	6.2	4.5	2.3
GRPO+OPSD	97.1	69.2	88.9	62.5	76.0	75.0	78.1	47.2	63.8	45.6	42.7	41.8	19.5	40.8	43.1	85.2	72.8
Skill-SD	93.9	67.3	79.4	54.7	61.0	82.3	73.1	48.0	64.4	45.8	43.9	40.7	19.4	44.8	43.9	82.2	69.4
RLSD	91.4	69.2	76.5	77.1	56.0	58.3	71.4	47.2	62.8	46.1	44.4	45.8	20.6	39.2	43.7	85.6	74.1
SDAR	94.3	71.8	84.0	93.8	72.0	58.3	79.0	47.9	64.4	47.6	44.4	46.2	20.8	44.8	45.2	84.5	72.4
AgentOPSD	96.2	69.2	91.4	83.3	72.0	69.4	80.3	45.5	60.4	42.5	41.7	33.3	18.6	40.8	40.4	83.0	74.0
AlignOPSD	85.7	61.5	85.2	87.5	80.0	50.0	75.0	48.0	64.5	46.1	45.0	47.2	21.0	42.4	44.9	85.3	74.8
SGR-OPSD	97.1	73.2	85.2	84.6	89.6	85.4	85.8	46.8	64.7	45.9	43.3	43.9	25.4	54.6	46.4	88.6	78.2

Gains beyond existing Self-distillation methods. The advantage persists against GRPO+OPSD and the Skill-guided methods Skill-SD, SDAR, and AgentOPSD on both evaluated environments at each model scale. Relative to the strongest baseline for each backbone, SGR-OPSD improves the ALFWorld macro-average by 2.0–5.3 pp and WebShop success by 4.1–5.5 pp. Its leading 7B results on Cool and Pick2 sub-tasks provide concrete examples: these tasks require completing an object-state change or collecting two distinct objects before final placement. The results support the full method’s effectiveness on tasks whose success depends on satisfying intermediate requirements.

Generalizability to retrieval-based reasoning. SearchQA tests the method in a different action space, where progress depends on retrieving evidence and resolving information dependencies. SGR-OPSD improves macro-average accuracy over GRPO by 1.2 and 2.1 points at 3B and 7B, respectively. It achieves the highest macro-average at both scales, exceeding the strongest baseline by 1.2 points at 7B, with the best 7B results on TriviaQA and MuSiQue. These gains show that the approach also benefits retrieval-based reasoning beyond environment manipulation.

Component Ablations

The ablations examine three components: the Subgoal Progress Graph, teacher evidence, and task-specific subgoal plans (Table 2 and Table 3). The metrics are ALFWorld macro-average seen success, SearchQA macro-average exact-match accuracy, and WebShop success rate.

Method	ALFWorld	SearchQA	WebShop
SGR-OPSD	76.9	40.6	68.8
w/o Graph	77.4	39.5	64.8
w/o Teacher Signal	74.1	40.8	62.2
Skill instead of Subgoal	74.6	37.7	60.4

Method	ALFWorld	SearchQA	WebShop
SGR-OPSD	85.6	46.4	78.2
w/o Graph	66.7	43.8	74.2
w/o Teacher Signal	79.9	44.4	72.6
Skill instead of Subgoal	70.9	44.2	68.4

Role of graph calibration. Relative to w/o Graph, which removes the Subgoal Progress Graph and directly uses $w^{\mathrm{ref}}$, the full method scores 4.0 pp higher on WebShop at both model scales, and 1.1/2.6 pp higher on SearchQA at 3B/7B. These consistent improvements support calibrating teacher evidence with rollout-derived progress preferences. ALFWorld exhibits a scale-dependent pattern: performance at 3B is comparable (76.9% vs. 77.4%), whereas the 7B variant yields a substantial 18.9 pp gain.

Role of teacher evidence. Teacher guidance complements preferences from the Subgoal Progress Graph on ALFWorld and WebShop. Compared to w/o Teacher Signal, which initializes graph calibration from unit weights, the full method achieves 2.8/5.7 pp higher success rates on ALFWorld and 6.6/5.6 pp higher on WebShop at 3B/7B. This pattern underscores the necessity of pairing explicit task requirements with observed progress evidence. SearchQA shows a 2.0 pp gain at 7B and comparable scores at 3B (40.6% vs. 40.8%).

Choice of privileged guidance. Subgoal plans consistently outperform Skill guidance across all available comparisons, achieving gains of 8.4/9.8 pp on WebShop, 2.9/2.2 pp on SearchQA at 3B/7B, and 2.3 pp on ALFWorld at 3B, under an identical allocation framework. While both representations encode ordered workflows, these results demonstrate that instantiating guidance with task-specific objects, destinations, and intermediate state requirements is strictly superior (§ 4.4).

Subgoal Guidance Analysis

Task-specific requirements. Subgoal plans instantiate workflow rules with the task’s objects, destination, and required states. Table 4 illustrates this distinction for cleaning a soapbar and placing it on a countertop. The Skill rule specifies a general clean-task workflow; the Subgoal plan names the soapbar and countertop and makes placement conditional on the soapbar being clean and held. The contrast is concrete: the Skill rule refers to a “target object” and “final location,” while the plan specifies which object must reach which destination and in what state. These explicit completion conditions give teacher scoring a task-specific reference for assessing sampled actions. Through the teacher–student likelihood gap, the plan supplies credit evidence tied to the instruction’s intermediate requirements.

Skill: reusable workflow
Always execute clean tasks in the fixed sequence:
(1) locate and acquire target object,
(2) bring it to an available water source or sink to clean,
(3) navigate to final location,
(4) place object.
Subgoal: task-specific requirement
5. Put the clean soapbar on the countertop
Preconditions: Countertop is found and reachable, soapbar is clean and held

Compact privileged context. Across 601 ALFWorld plans, Subgoal guidance averages 87.79 tokens, whereas the six task-type Skill inputs range from 861 to 1,168 tokens. Counts use the Qwen2.5-3B-Instruct tokenizer without special tokens and exclude interaction history. The compact plan retains task-specific goals and preconditions, and is reused unchanged across turns. Appendix § 6 provides the generation prompts and full comparison.

Training Dynamics

We track validation performance every five training updates, comparing methods at 3B and model scales for SGR-OPSD.

Continued gains in later training. On ALF-World, SGR-OPSD sustains its performance lead across the final four validation checkpoints (updates 135–150), finishing 11.7 and 17.2 pp ahead of GRPO and AgentOPSD, respectively (Figure 3). While the competing methods overlap during early and intermediate training, SGR-OPSD establishes a sustained late-stage advantage, ultimately reaching 82.0% success. This trajectory confirms that the final improvement reflects a consistent separation maintained throughout the closing updates. On WebShop, all three methods progress from near-zero success to over 50%; their final evaluations under the standard protocol are detailed in Table 1.

Learning across scales and environments. Figure 4 illustrates performance gains across both model scales in all three environments. The 7B model accelerates earlier on ALFWorld and WebShop, whereas the 3B variant exhibits steady late-stage gains. On SearchQA, macro-average Exact Match (EM) accuracy rises from 26.1% to 39.5% at 3B scale and from 28.8% to 43.2% at 7B scale between updates 5 and 150. The 7B trajectory maintains a clear margin over the 3B curve through out training on this benchmark, with both scales reaching stability in the closing updates.

Credit Assignment Analysis

Independent progress verification. Preferences from the Subgoal Progress Graph agree with independent return rankings on 49/60 action pairs (81.7%), versus 30/60 (50.0%) for teacher evidence (Figure 5a). Using a fixed Qwen2.5-3B-Instruct checkpoint, we test one pair per ALFWorld task with 32 continuations per action from matched states, contexts, and budgets. Mean discounted returns determine the reference ranking; the graph and pairs are frozen before sampling these independent continuations. Graph-preferred actions also achieve 2.8 pp higher continuation success.

Credit calibration analysis. Calibration translates this progress evidence into better credit allocation (Figure 5b). Applying Equation (11) offline to saved rollouts raises ranking agreement from 8/21 (38.1%) to 16/21 (76.2%) on the same 21 eligible pairs, selected independently of continuation outcomes. Sign-aware credit measures support through stronger reinforcement or reduced

penalties, depending on the advantage sign. These findings confirm that calibration effectively aligns credit with independently observed returns. Appendix § 9 provides eligibility criteria, confidence intervals, coverage, and state-merging diagnostics.

Action-level case study. For the tomato-cooling task (Table 5), visiting garbagecan 1 reveals a tomato, whereas cabinet 1 is closed. Independent continuations from matched states favor the former in discounted return and success (32/32 vs 13/32). Relative to the teacher reference, offline calibration strengthens reinforcement for the positive-advantage garbagecan visit and penalties for the negative-advantage cabinet visits, shifting the credit gap from $-0.0109$ to $+0.0191$.

Trajectory	Action	$A_{i,t}$	Base	$w^{\mathrm{ref}}$	$w^{*}$
$\tau_{1}$	go to garbagecan 1	+2.735	1.0000	0.9596	0.9738
$\tau_{2}$	go to cabinet 1	$-0.365$	1.0000	1.0397	1.0540
$\tau_{3}$	go to cabinet 1	$-0.365$	1.0000	1.0192	1.0366

Generalization to Unseen Environments

SGR-OPSD successfully extends its performance gains to unseen ALFWorld environments, outperforming the strongest baseline by 1.0 pp at 3B scale and 2.7 pp at 7B scale (Table 6). It achieves 73.1% and 82.3% success on unseen environments at 3B and 7B, respectively, demonstrating robust transfer capabilities beyond seen evaluation settings.

Method	\multicolumn{2}{c}{Qwen2.5-3B}	\multicolumn{2}{c}{Qwen2.5-7B}
	Seen	Unseen	Seen	Unseen
GRPO	69.3	67.5	78.2	79.6
AgentOPSD	68.6	68.2	80.3	78.7
AlignOPSD	65.9	72.1	75.0	65.8
SGR-OPSD	76.9	73.1	85.6	82.3

These gains extend the benefit of structured credit assignment to unseen environments. Subgoal plans express task requirements, while the Subgoal Progress Graph calibrates action credit during training; evaluation uses the student’s ordinary interaction context. The unseen results support the transfer of the resulting policy improvements beyond the environments encountered during training.

Conclusion

We introduce SGR-OPSD, which combines subgoal-conditioned teacher evidence with calibration by the Subgoal Progress Graph to allocate credit across agent turns. It improves over GRPO at both 3B and 7B, reaching 85.6% ALFWorld macro-average success and 78.2% WebShop success at 7B, supporting structured credit assignment.

Limitations

Evaluation scope. We evaluate SGR-OPSD on three benchmarks using Qwen2.5-3B/7B-Instruct. Its applicability to other model families and open-ended environments requires further evaluation, particularly when observations and action spaces differ from those studied here.

Fixed subgoal guidance. Subgoal plans are generated from task instructions before interaction and remain fixed across turns. They may omit requirements or fail to accommodate new information revealed by the environment. Updating plans from observed feedback is a natural extension of the current framework.

Rollout-dependent graph evidence. The Subgoal Progress Graph estimates empirical action values from recorded transitions and outcomes; comparison coverage depends on exploration and the availability of matched action visits. When eligible comparisons are absent, the method retains the teacher reference. Graph scores summarize progress within sampled rollouts rather than establish true action values; broader exploration and more reliable state matching are directions for extending this evidence.

Privileged Information and Subgoal Generation

Comparison of Privileged Information

Table Table 7 compares task specificity, subgoal planning, and interaction requirements of privileged guidance in related methods. Subgoal plans condition guidance on the current instruction and explicitly connect intermediate goals through ordering preconditions. They are generated before student interaction and reused across turns, making the task’s object, destination, count, and required state explicit without requiring a successful rollout or a reference answer.

Method	Task-instance specific	Task-specific subgoal plan	No successful rollout required	No task-specific interaction required
OPSD (Skill) ([16])	×	×	✓	✓
RLSD ([12])	✓	×	✓	✓
Skill-SD ([10])	✓	✓	✓	×
SDAR ([6])	×	×	✓	✓
AgentOPSD ([11])	×	×	✓	✓
UniOPSD ([3])	✓	×	×	×
SGR-OPSD	✓	✓	✓	✓

Concrete Skill–Subgoal comparison. Table 8 pairs a recorded Subgoal plan with the Skill text selected for the same ALFWorld instruction. In this Skill configuration, task-type matching concatenates general rules with the corresponding task-specific file. Both forms encode ordering: Skill expresses reusable rules with generic objects and destinations, while Subgoal instantiates these requirements for the current task. The table reproduces two Skill excerpts and the complete stored plan.

Task: clean some soapbar and put it in countertop.
Skill guidance: verbatim excerpts	Subgoal guidance: complete recorded plan
10. Progressive Goal Decomposition: Break tasks into ordered sub-goals: (1) locate object, (2) obtain or transform it, (3) locate destination or reference object, (4) satisfy spatial relation or placement. Complete each sub-goal before moving to the next. Apply this at the start of every episode.	1. Find a soapbar in the environment Preconditions: None 2. Pick up the soapbar Preconditions: Soapbar is found and reachable 3. Clean the soapbar (e.g., rinse or wash it) so it is clean Preconditions: Soapbar is held 4. Find a countertop receptacle Preconditions: Soapbar is clean and held 5. Put the clean soapbar on the countertop Preconditions: Countertop is found and reachable, soapbar is clean and held
1. Phase-Ordered Plan: Always execute clean tasks in the fixed sequence: (1) locate and acquire target object, (2) bring it to an available water source or sink to clean, (3) navigate to final location, (4) place object. Apply this as soon as the goal specifies the object must be clean before placement.

Guidance length. We compare the six task-type Skill inputs with an ALFWorld corpus of 601 unique cached Subgoal plans, using the Qwen2.5-3B-Instruct tokenizer without special tokens. Skill inputs ranged from 861 to 1168 tokens; Subgoal plans averaged 87.79 tokens (median 85; range 28–162). These counts cover the privileged text supplied to the teacher, excluding interaction history. They quantify the compactness of the task-specific representation in this corpus.

DeepSeek-V3.1 Generation Prompts

We query DeepSeek-V3.1 [2] through a chat-completion interface with temperature 0 and a maximum output of 1024 tokens. Each initial request contains the environment-specific system prompt reproduced below and a user message containing only the task instruction $x$ (the question text for Search-QA). Outputs that fail validation are retried with the previous response and validation feedback. The deployment model identifier is deepseek-v31-meituan. Plans are cached by task and generation configuration and reused unchanged; ALFWorld and WebShop generate them before the first rollout for a new instruction, while Search-QA precomputes the scheduled training questions. The external model generates guidance, and the rollout policy supplies both likelihood scores.

The response is a JSON object containing 2–8 subgoals, each with nonempty goal and precondition fields. The teacher receives the numbered rendering $j$. <goal> Preconditions: <precondition>. The complete plan is supplied at each turn, without stage-dependent filtering, and is absent from the student’s acting context and evaluation prompts.

ALFWorld system prompt.

Plan an ALFWorld household task from its task description only. Return JSON only: {"subgoals": [{"goal": "...", "precondition": "..."}]}. Give 2 to 8 concise ordered subgoals, including any necessary exploration, acquisition, cleaning/heating/cooling, and final placement/use. State ordering preconditions. Describe desired states rather than a guessed action transcript. You do not know the initial scene or object locations. Never invent locations, object instance numbers, observations, or completed steps. Use conditional search where needed. Preserve the task’s exact object type, destination type, count, and required state. Never substitute another receptacle or add an alternative destination (a table is not interchangeable with a counter). A two-object task requires two distinct objects. Keep the whole plan below 350 English words. Do not include an explanation outside JSON.

WebShop system prompt.

Plan a WebShop shopping task using only the customer’s instruction. Return JSON only: {"subgoals": [{"goal": "...", "precondition": "..."}]}. Give 2 to 8 concise ordered subgoals and their ordering preconditions. Include searching for candidates, inspecting product details, checking ALL requested attributes, selecting the exact required options, verifying the price constraint, and buying only after the

visible evidence supports the requirements. Describe desired states, not a guessed action transcript. Preserve every stated product type, attribute, option (such as size/color), quantity, and price bound. Do not silently relax or substitute a requirement, even if it appears unusual. You have no catalog, search results, product IDs, prices, observations, past actions, or reward information. Never invent these, assert that a suitable product exists, or claim a step is complete. Use conditional search/refinement where needed. Do not add unstated purchase requirements. Keep the plan under 350 English words.

Search-QA system prompt.

Plan how to answer a retrieval question using only the question. Return JSON only: {"subgoals": [{"goal": "...", "precondition": "..."}]}. Give 2 to 8 concise ordered evidence goals and their dependencies, under 350 English words. Identify missing facts, bridge entities and constraints that must be established by retrieved evidence. For a single-hop question use a simple evidence lookup and answer verification. For a multi-hop question order lookups according to their dependencies. End with checking the evidence against the question and producing a concise answer. You have no search results, gold answer, supporting-fact labels, student history or reward. Do not supply or guess the answer, invent bridge entities, assert an unknown fact, or claim that a goal is complete. Use placeholders or conditional goals for unknown entities. Preserve the exact entities, relation and time constraints in the question. Do not prescribe more searches than the four-turn interaction budget.

Implementation Details of Credit Allocation

This appendix specifies the scoring, weighting, and graph conventions used by the allocation in § 3.

Scoring Context and Action Tokens

The teacher prompt prepends the cached task plan to the student prompt and is left-truncated to the environment-specific context limit. Consequently, $h^T_{i,t}$ and $h^S_{i,t}$ can retain different parts of the interaction context. Both branches use the same pre-update actor and score the original sampled response IDs. Action-token probabilities remain conditioned on earlier reasoning tokens; Equation (1) is not a probability marginalized over reasoning.

The action mask selects original response tokens that overlap the trimmed executable-action span, including tokens crossing its byte boundaries. The span is not retokenized. A turn without a scoreable action receives $d_{i,t}=0$ and is excluded from graph comparisons. Its outcome penalty and full-response policy update remain active. Such a turn still participates in its trajectory’s allocation budget, so its multiplier need not remain one.

Training Mass and Unique Visits

Training batches can contain padding copies of an environment turn. The allocator represents each unique turn once, after checking agreement of its copies’ evidence and base advantages. Its mass $m_{i,t}$ is the number of effective response tokens summed across all training copies. These copies contribute to the policy loss and hence to $\pi_{i,t}$, but do not create additional graph visits. The allocated advantage is broadcast back to all copies.

Base advantages retain the reward normalization and invalid-action penalties of the training recipe in § 4.1. The allocator does not replace them by a common trajectory advantage. Accordingly, positive, negative, and zero advantages can occur within one trajectory. The multiplier budget $\sum_{t=1}^{N_i}\pi_{i,t}w_{i,t}=1$ does not imply conservation of the sum of advantages or the optimizer’s gradient norm.

Graph Construction and Pair Eligibility

State and action identities. Each task’s group of eight student rollouts forms a separate Subgoal Progress Graph at each update. Recorded visits contribute transition counts once, excluding training padding copies. ALFWorld node keys combine observation-memory anchors with physical-state signatures hashing simulator facts and entity metadata. WebShop keys combine formatted observations with product identity, page, page name, and selected options. These descriptors support graph estimation without entering teacher or student prompts. Within a node, actions are grouped by their exact executed strings.

SearchQA states and actions. The graph ID hashes the update, rollout-group ID, and question ID. A node represents the exact formatted student context: the question, interaction count, and ordered executed queries with their returned evidence.

The four-turn history window covers preceding interactions within the four-turn budget. Nodes merge only when their context strings match within the graph. Different query histories remain separate even if they retrieve the same passage. The pre-action state signature hashes the question ID and context; the student-prompt hash checks the scoring input after prompt processing.

Actions use the projected executable string: <search>query</search> or <answer>answer</answer>. Projection removes surrounding reasoning, standardizes the wrapper, and trims payload-boundary whitespace without semantically normalizing queries or answers. Gold answers and reward labels are excluded from node keys and state signatures.

Empirical graph values. Let $N(v,a)$ count recorded visits taking action $a$ at node $v$, and $N(v)=\sum_a N(v,a)$. Equation (7) uses $\hat{\pi}(a\mid v)=N(v,a)/N(v)$; $\hat{Q}$ averages immediate rewards and discounted successor values over recorded transitions, and $\hat{V}$ averages action values by visit frequency. Their difference measures an action’s empirical return relative to the state average.

For ALFWorld and WebShop, the recorded binary success reward ($0$ or $1$) is divided by $10$ before value estimation; SearchQA uses binary terminal exact-match reward directly. Thus all three environments use $r\in\{0,1\}$ and $\gamma=0.1$, with success assigned to the terminating transition. Terminal transitions, exhausted budgets, and successors absent from the recorded source-node set have zero continuation value; immediate rewards are retained. Failed or budget-truncated episodes remain in the transition counts, with zero terminal success reward.

Values are initialized to zero and iterated until the maximum absolute change is below $10^{-12}$, with at most 200 iterations; failure to converge raises an error. Cycles are handled by these discounted fixed-point updates. Clipping is applied after subtracting $\hat{V}$ from $\hat{Q}$, as in Equation (8); there is no subsequent reward rescaling. All visits to a state–action pair share its empirical signal. The values summarize continuation behavior pooled by node; the additional context and budget checks below restrict comparisons, not the value-estimation pool.

Pair eligibility and averaging. Within each node–plan bucket, every visit associated with the two candidate actions must be scoreable, have nonzero base advantage, and agree on the preaction state signature, student-prompt hash, and remaining step budget. ALFWorld signatures use simulator facts and entity metadata; WebShop signatures use recorded session state and available actions. Success reachability is not an additional eligibility condition. We retain $(a,b)$ when $\bar{g}(a) > \bar{g}(b)$, excluding ties. The vector $H_a$ averages unique visits equally within each trajectory, then equally across trajectories. Although identical state–action visits share a graph score, this averaging also defines their mean credit correction. Graph scores supply pair ordering, while $\mu$ sets the correction margin. For each eligible pair $e$, the comparison weight is

where $\mathcal{E}_v$ contains the eligible pairs in the same node–plan bucket. This weight normalizes comparison count and coefficient scale; it is not a bootstrap reliability estimate.

Optimization and Fallback

For a nonzero advantage, differentiating the teacher objective before clipping gives $s_{i,t}d_{i,t} - T\log w_{i,t} - \nu_i = 0$. The resulting exponential tilt is clipped to the prescribed interval, and the trajectory multiplier $\nu_i$ is found by bisection to satisfy the budget. Zero-advantage turns retain $w_{i,t}=1$. This solves the bounded allocation directly, rather than clipping weights and subsequently renormalizing them outside their bounds.

Joint solver. We use float64 Nesterov-accelerated projected gradient descent, initialized at the teacher correction $c^{\mathrm{ref}}$, with monotone restart. Let $F(c)$ denote the joint objective, $D=\operatorname{diag}(p)$ the token-mass metric, and $\Pi_D$ its projection onto the bounded, per-trajectory budget constraints. The step size is $1/L$, with

where $B$ has rows $b_e^{\mathsf{T}}$, $M=|B|D^{-1/2}$, and the matrix infinity norm is the maximum row sum. The momentum coefficient is $(\sqrt{L}-\sqrt{m})/(\sqrt{L}+\sqrt{m})$ with $m=T_G/(1+\epsilon)$. An extrapolated step that increases the objective beyond $10^{-13}(1+|F(c)|)$ is replaced by the ordinary projected-gradient step and momentum is reset. Outside the feasible box, extrapolation uses the KL term’s quadratic extension matching its value, gradient, and curvature at the clipped boundary.

We stop when

with at most 5,000 iterations. Teacher-budget bisection uses 100 iterations; each metric projection uses 55. A solution must be finite, have maximum trajectory-budget error at most $10^{-10}$ and bound violation at most $10^{-12}$, and increase the objective over the teacher initialization by at most $10^{-9}$. Failure of convergence or these checks raises an error and stops the update; it does not silently substitute teacher weights.

No-comparison case. A trajectory with no eligible graph term retains its teacher reference exactly. Within a trajectory containing graph comparisons, the budget can also adjust turns that do not participate in a pair. The soft hinge term encourages pairwise margins but does not guarantee that every graph comparison is satisfied. The experimental allocation hyperparameters are reported in § 4.1.

Experimental Details

Training and Evaluation Protocols

The following settings describe the recorded SGR-OPSD training and full-evaluation configurations. The ALFWorld and WebShop training configurations use 16 tasks per batch, eight trajectories per task, and 150 policy updates. The learning rate is $10^{-6}$, the reference-policy KL coefficient is 0.01, and training and validation temperatures are 1.0 and 0.4, respectively. ALFWorld and WebShop retain a two-turn history window. SearchQA uses a four-turn history window, 128 tasks per batch, a reference-policy KL coefficient of 0.001, and a four-turn interaction budget. Its training data comprise NQ and HotpotQA; evaluation covers all seven datasets listed in § 4.1.

Base advantages. For ALFWorld and WebShop, row-level rewards are centered and scaled by the mean and sample standard deviation over training rows sharing a task UID, including padding copies, with stabilizer $10^{-6}$. The invalid-action penalty coefficient is 0.1, so advantages can differ across turns of one trajectory. The policy loss averages over effective response tokens. Allocation deduplicates turns while retaining their training token mass, as described in Appendix § 7.

Evaluation sets and decoding. Full ALFWorld evaluation uses 140 seen and 134 unseen tasks, with one rollout per task, temperature 0.4, top-$p = 1$, and top-$k = -1$. Table 1 uses the seen split and reports the unweighted mean of its six category success rates. WebShop evaluation uses the 500 goals indexed 0–499 with temperature 0.4. Success is the fraction of fully completed goals; Score is the mean native partial-completion reward multiplied by 100. SearchQA uses greedy decoding and question-level exact match across 51,713 questions in seven datasets. ALFWorld seen and WebShop full evaluation sets overlap their respective checkpoint-selection validation sets; ALFWorld unseen evaluation is separate from selection.

Setting	ALFWorld	WebShop
Maximum environment steps	50	15
Prompt / response tokens	2048 / 512	4096 / 512
PPO minibatch	256	64
Actor microbatch per GPU	32	8
Rollout tensor parallelism	2	2
Validation tasks per check	128	128
Validation interval (updates)	5	5
Periodic save interval	10	10

Checkpoint selection. ALFWorld and WebShop select saved checkpoints using training-time validation success. For the original SearchQA main-result runs and w/o Graph controls, scheduled post-update validation occurs at update 150 on all 51,713 questions; these runs use the update-150 checkpoint. The separate SearchQA curve runs validate every five updates on a fixed 3,125-question subset. Their selection criterion is the highest subset micro EM, with the earliest checkpoint retained on a tie; the displayed curve metric is macro EM. Full-set evaluation follows selection. The newly completed 7B w/o Teacher Signal and Skill controls use selected updates 150 and 140, respectively, for full-set evaluation.

Evaluation randomness. The frozen ALFWorld full-evaluation protocol uses environment seed 0, task seed 1000 + index, and engine seed 0. Training and evaluation seeds are recorded separately; a shared engine seed does not imply paired per-request sampling.

Aggregation. Table 1 reports three-seed aggregates for trained methods, using seeds $\{0, 42, 2026\}$. ALFWorld and SearchQA Avg first average equally over the six task categories and seven datasets, respectively, within each run, then across runs. WebShop Score and success use the same seed aggregation. In Table 2 and Table 3, full-method rows reproduce the main-table means. Figure 3 and Figure 4 show individual seed-0 runs.

Training-Curve Sources

SearchQA validation runs. Figure 4(c) uses dedicated 3B and 7B runs with every-five-update validation, separate from the original update-150 main-result runs. Each point at updates 5, 10, …, 150 comes from greedy student-only evaluation of the same fixed 3,125 questions: 500 each from NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, and MuSiQue, and all 125 Bamboogle questions. The subset is drawn from the 51,713-question evaluation pool and reused unchanged across checkpoints and model sizes. Macro EM is $100 \times\frac{1}{7}\sum_{d=1}^{7} C_d/N_d$, where $C_d$ and $N_d$ are each dataset’s correct-answer and question counts. The 60 plotted points are computed from these per-dataset validation counts. The original and curve-run packages use byte-identical graph construction, pair eligibility, and allocation solver files.

The full evaluation pool contains 3,610 NQ, 11,313 TriviaQA, 14,267 PopQA, 7,405 HotpotQA, 12,576 2WikiMultiHopQA, 2,417 MuSiQue, and 125 Bamboogle questions. Main-table and ablation SearchQA scores use this full pool. Both evaluations report macro EM across seven datasets: curves use the fixed subset at each checkpoint, while tables use full-pool checkpoint evaluations.

ALFWorld and WebShop curves. The other panels use recorded training-validation points from the seed-0 method-comparison and full-method runs, including their documented checkpoint-resume chains. Validation uses 128 episodes per check, and the plotted success is the fraction of successful episodes. ALFWorld curves therefore differ from the six-category macro-average in the result tables. In the 3B WebShop method comparison, GRPO and AgentOPSD use fixed validation tasks while SGR-OPSD samples tasks; final WebShop table entries use all 500 goals. All curves use recorded checkpoints and retain their validation protocols.

Progress Verification and Credit Calibration

Independent Progress Verification

Agreement with independent outcomes. Preferences from the Subgoal Progress Graph agree with independent continuation returns on 49/60 matched ALFWorld action pairs (81.7%), compared with 30/60 (50.0%) for teacher evidence. Graph-preferred actions also achieve higher mean discounted return and continuation success (Table 10). They succeed in 1,756/1,920 continuations, compared with 1,702/1,920 for their alternatives. At the task level, success is higher for 22 pairs, lower for nine, and tied for 29. On the 31 pairs with unequal success rates, graph preferences agree with the success ordering on 22 pairs (71.0%), compared with 16 (51.6%) for teacher evidence. Return agreement evaluates all 60 pairs and captures both completion and its timing.

Measure	Estimate	95% interval
Teacher return agreement	50.0%	[37.7, 62.3]
Graph return agreement	81.7%	[70.1, 89.4]
Mean return difference	+0.03461	[0.00054, 0.08394]
Success difference (pp)	+2.81	[0.05, 5.89]

Independent continuation protocol. The evaluation fixes Qwen2.5-3B-Instruct at update 150, selected by training-validation success (82.03%), and constructs graphs from eight rollouts for each of 140 ALFWorld tasks. Candidate actions must be legal and share the exact simulator-state signature, student-prompt hash, and remaining budget. The sampling protocol requires an absolute graph-score difference above $10^{-8}$ and positive recorded reliability for at least one source visit. The latter requires that its state–action pair occur in at least two trajectories, have nonzero empirical advantage, and appear in at least 16 of 64 trajectory-bootstrap replicates. Each replicate resamples the eight trajectories with replacement. These criteria select the evaluation pool; allocation uses the objective and pair weights defined in Appendix § 7.

The pool contains 311 action pairs across 94 tasks. Using selection seed 20261027, we choose one pair uniformly within each task, reserve eight disjoint tasks for replay checks, and select 60 formal tasks proportionally across the remaining task categories. The state and action manifest is frozen before continuation sampling. For each pair, we restore the recorded state and history, force either action, and sample 32 continuations per action with the remaining interaction budget. Sampling uses temperature 1, top-$p$ 1, no top-$k$ restriction, and at most 512 response tokens per turn. Request seeds differ between graph construction and continuation evaluation; the inference-engine initialization seed is 0. The resulting 3,840 continuations are

excluded from graph estimation and pair selection.

Outcome metrics. For each action, we average the independent discounted returns $\sum_{j\geq0}\gamma^j r_j$, with $\gamma= 0.1$, binary terminal success reward, and $j = 0$ denoting the forced action. Ranking agreement compares a predicted gap’s sign with the difference between these two sample means. All 60 empirical return differences exceed the outcome sign tolerance $10^{-12}$. Graph gaps use tolerance $10^{-8}$; teacher and credit gaps use $10^{-6}$. Success is also measured without discounting. Table 10 reports both endpoints. Proportion intervals are 95% Wilson intervals; paired differences use 10,000 task-level bootstrap resamples with seed 20261027, preserving the two actions within each task.

Coverage and state merging. Candidate comparisons cover 67.1% of tasks and 58.8% of trajectories in the graph-building pool, with direct participation concentrated in 3.95% of turns (Table 11). Coverage counts each task, trajectory, or turn once before nonzero-advantage allocation filtering. This measures where action comparisons are available; the trajectory budget determines how their calibration also affects other turns.

Covered unit	Count / total	Fraction
Tasks	94 / 140	67.1%
Trajectories	658 / 1,120	58.8%
Turns	1,055 / 26,717	3.95%
Additional node key	Same	Reversed	Below threshold
Formal pairs ($n = 60$)
Remaining budget	52	2	6
Budget and prompt	52	2	6
All candidates ($n = 311$)
Remaining budget	278	8	25
Budget and prompt	278	8	25

Splitting nodes by remaining budget preserves 52 of the 60 evaluated preference directions, reverses two, and leaves six below threshold. Adding prompt identity produces no further direction changes. Both refinements agree with independent returns on 44/54 remaining predictions (81.5%), with six abstentions. The diagnostic holds candidate actions and independent outcomes fixed while recomputing graph values under each node key. The original nodes include physical-state signatures; among 17,991 visited source nodes, 4,375 have repeated visits, 3,513 mix remaining budgets, and 3,540 mix student-prompt hashes. These mixed nodes account for 9,440 and 9,502 of the 26,717 turns, respectively. The results quantify how successor pooling affects preferences even when the compared actions share a matched starting state.

For example, the original graph favors go to countertop 1 over go to cabinet 1 by 0.000333; budget splitting reverses the gap to −0.000045. Both actions succeed in all 32 continuations, while the countertop action has 0.00028884 higher mean discounted return. This pair illustrates why success and discounted return are reported separately, and why finer merging keys are assessed against independent outcomes.

Credit Calibration Analysis

Improved outcome alignment. Calibration using Subgoal Progress Graph preferences increases agreement with independent returns from 8/21 (38.1%) to 16/21 (76.2%) on the same directly eligible pairs, with Wilson intervals [20.8%, 59.1%] and [54.9%, 89.4%] (Table 12). Across all 60 pairs, calibration yields eight additional correct rankings: nine corrections and one change from correct to incorrect. The paired gain is 13.3 percentage points over all 60 pairs (95% task-bootstrap interval [3.3, 23.3]). Thirty-five pairs involve zero-advantage visits and remain tied under both reference and calibrated credit; four further pairs fall outside the exact direct-comparison conditions. The table reports correctness and ties for both the complete set and the directly eligible subset.

Signal	Correct	Incorrect	Tied
All 60 pairs
Teacher evidence	30	30	0
Graph preference	49	11	0
Teacher-reference credit	11	14	35
Calibrated credit	19	6	35
Same 21 directly eligible pairs
Teacher evidence	9	12	0
Graph preference	16	5	0
Teacher-reference credit	8	13	0
Calibrated credit	16	5	0

Retrospective scoring and allocation. At a fixed checkpoint, we recompute credit weights from the saved graph-building rollouts of the 60 formal tasks using Equations (2) and (11). This offline comparison isolates the allocation mechanism while holding likelihood scores and continuations fixed. Teacher and student score the same saved response under their respective contexts. Scoring uses saved-text retokenization, checked by text round trips and student-prompt hashes, because original generation token IDs are unavailable. Of

the 60 task plans, 53 reuse cached plans and seven follow the original instruction-only generation protocol. Continuation outcomes are held out from plan generation, scoring, and calibration.

The reconstruction includes all eight graph-building trajectories per task: 8,202 unique turns, of which 8,201 have scoreable actions. Both actions in every selected pair are scoreable. Base advantages use the frozen GRP reward normalization and invalid-action penalty; token masses count the canonical response tokens once per unique visit. We use $\epsilon= 0.1$, $T = T_G = 1$, $\beta= 2$, $\mu= 0.02$, and graph-score bound $b_G = 0.3$, with the solver checks in Appendix § 7.

For pair $e$, raw teacher evidence is $b_e^T d$, while teacher-reference and calibrated credit gaps are $b_e^T c_e^{\mathrm{ref}}$ and $b_e^T c_e^*$, respectively, with $c_e^{\mathrm{ref}} = s \odot(w^{\mathrm{ref}} - 1)$. These sign-aware gaps compare favorable credit across advantage signs. Eligibility selects 21 pairs using scoreability, nonzero advantages, and matching state, context, and budget across their source visits, independently of continuation outcomes.