Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

Ziyi Chen; Yan Zhang; Jianhui Wei; Daoan Zhang; Zuozhu Liu

cs.AIOct 1, 2026

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

Authors: Ziyi Chen, Yan Zhang, Jianhui Wei, Daoan Zhang, Zuozhu Liu

Organizations: University of Illinois Urbana-Champaign · National University of Singapore · Zhejiang University · University of Rochester

Abstract

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.

Figures & tables

Figure 1: Top: Comparison of existing methods. GRPO shares an episode-level signal across all steps; GiGPO uses time-discounted future returns; and ARPO/AEPO allocates additional rollouts around uncertain positions. Bottom: A schematic DARS credit assignment example. Product type $c_{1}$ is a prerequisite for size $c_{2}$ and scent $c_{3}$ , while price $c_{4}$ is independent. Picking body wash (Step 5) breaks $c_{1}$ , attenuating the weights of $c_{2},c_{3}$ while preserving $c_{4}$ . Re-selecting lotion (Step 7) repairs and re-verifies $c_{1}$ , restoring full weight to the retained local evidence for $c_{2},c_{3}$ . Step rewards $\tilde{r}_{t}$ are signed changes in the dependency-weighted potential $\Phi$ , with $\lambda=\kappa=\rho=1$ .

Figure 2: DARS on the GiGPO backbone. The learner samples $N$ rollouts and retains its episode-level advantage $A^{E}$ . An annotator identifies task predicates and their per-step verification (V), invalidation (B), and repair (P) events. A deterministic graph potential converts these events into signed step rewards $\tilde{r}_{t}$ , which replace the environment rewards in the anchor-state channel producing $A^{S}$ .

Method	1.5B	7B
GRPO	$72.8\pm 3.6$ †	$87.4\pm 0.4$
RLOO	$69.7\pm 2.5$ †	$85.9\pm 0.4$
GiGPO (w/ std) †	$86.7\pm 1.7$	$90.8\pm 1.3$
GiGPO (w/o std) †	$86.1\pm 4.7$	$90.2\pm 2.3$
GiGPO (same budget)	$86.9\pm 0.8$	$98.1\pm 0.1$
DARS (ours)	$\mathbf{96.9\pm 0.0}$	$\mathbf{98.6\pm 0.2}$

Table 1: Interactive agent tasks (Qwen2.5-Instruct; scores in %). † Published result and uncertainty ( Feng et al., 2025 ) . Unmarked rows are our runs (DARS script, hyper-parameters, and harness; mean

\pm

SE over decoding draws); ours are shaded.

\Delta

: gain of DARS over the matched GiGPO row in points (paired, before rounding; tests in Appendix D ). ‡ DARS continues its GiGPO parent. Search-R1 : “shared” reuses the training pool and “held-out” is disjoint from it; 662 GiGPO vs. 360 DARS steps (shared), one epoch each (held-out); single-hop is NQ, TriviaQA, PopQA, multi-hop the other four; DARS leads in all three decoding groups for every

\Delta

. Protocols: Appendix F .

Arm	Step 5	Step 10	Step 15	Grid mean	Best	$\Delta$ vs. init.
ARPO ( Dong et al., 2026b )	61.7	61.3	62.9	62.0	62.9	$+5.0$
AEPO ( Dong et al., 2026a )	63.3	61.7	60.0	61.7	63.3	$+5.4$
ARPO $+$ DARS	59.2	61.3	64.2	61.6	64.2	$+6.3$
AEPO $+$ DARS	60.4	67.5	62.9	63.6	67.5	$\mathbf{+9.6}$

Table 2: Agentic mathematics with ARPO/AEPO (Qwen3-8B, Python interpreter). Mean AIME24/25 accuracy (%); approximate decoding variation

\pm 5

points per cell; our methods are shaded. All arms retain ARPO’s rollouts. “Best” is the maximum across the displayed checkpoints on the reported problems;

\Delta

is its gain over initialization (

57.9

), in points. Protocols, per-benchmark results, and checkpoint-selection rationale: Appendix I .

	Qwen3-1.7B				Qwen3-4B
Method	AMC	AIME24	AIME25	Avg.	AMC	AIME24	AIME25	Avg.
Untrained model	84.38	50.56	37.50	57.48	97.21	73.75	66.55	79.17
StaRPO	84.37	50.42	37.50	57.43	97.03	72.40	67.40	78.94
On-policy distillation	84.45	50.62	36.88	57.32	96.83	71.64	67.39	78.62
OmniOPD	85.52	49.86	36.34	57.24	96.33	72.43	66.56	78.44
DARS w/o step credit	84.94	49.25	36.50	56.90	97.48	74.20	65.71	79.13

Table 3: Tool-free mathematical reasoning. Percentage scores averaged over each method’s evaluation cells; Avg. is the mean of AMC, AIME24, and AIME25. Bold marks the best score within each model size. Our method is shaded. Protocols, cell counts, and uncertainty: Appendix J .

	Qwen3-1.7B				Qwen3-4B
Variant	AMC	AIME24	AIME25	Avg.	AMC	AIME24	AIME25	Avg.
Scalar only ( $\eta=0$ )	84.94	49.25	36.50	56.90	97.48	74.20	65.71	79.13
DARS ( $\eta=1$ )	86.53	49.92	38.25	58.23	96.72	74.64	67.12	79.50

Table 4: Ablations and annotator comparison. All scores are percentages; Avg. in (a) is the mean of AMC, AIME24, and AIME25; DARS rows are shaded. The sweep in (b) reports validation-selected peaks under a separate recipe (

\Delta

before rounding). Panel (d) reports peak success (eight draws) and training-step time from the matched comparison. Protocols, uncertainty, and tests: Appendices J , K , B , and G .

Appendix figures & tables29 assets

Supplementary material from the paper’s appendix.

Appendix

Measure	ungated	gated
Failed trajectories with $\Phi_{G}\geq 0.99$ (over-credit) $\downarrow$	0.12	0.02
Failed trajectories with $\Phi_{G}\geq 0.75$ $\downarrow$	0.14	0.04
Count-aware graphs on multi-object tasks $\uparrow$	0/48	48/48
Mean $\Phi_{G}$ on successful trajectories (preserve)	0.91	0.89
Usable verdicts / median latency	—	122/123 / 23 s

Appendix

Table 5: Offline graph-induction bench. Replay of

123

recorded unseen-split ALFWorld trajectories (

51

failed,

72

successful, including all

48

multi-object tasks) through the production message path, with no training involved. Gating reduces the fraction of failed trajectories whose induced graph nonetheless saturates; mean potential on successful trajectories changes only slightly.

Arm / configuration [checkpoint]	Draws	Metric	Table
ALFWorld — Qwen2.5-1.5B-Instruct 500 steps, 128 unseen games
GiGPO (local) [final 500]	4	86.9	8
GiGPO (local) [milestones 100 / 150 / 200 / 300 / 400]	4	67.7 / 86.5 / 90.2 / 84.6 / 86.3	9
DARS ( $\lambda{=}1$ , $\kappa{=}0.3$ ) [final 500]	4	96.9	1
DARS [milestones 100 / 150 / 200 / 300 / 400]	4	77.9 / 91.6 / 91.0 / 90.1 / 93.4	9
ALFWorld — Qwen2.5-1.5B-Instruct 200 steps, 128 unseen games

Appendix

Table 6: All experiments at a glance. The principal trained arms, variants, and controls reported in this paper, one row per (arm, checkpoint) cell; detailed selection results appear in the cited tables. “Draws” is the number of independent decoding draws (interactive tasks and agentic mathematics) or evaluation cells (tool-free reasoning) behind the cell. Success / task score for ALFWorld and WebShop; exact-match QA accuracy for Search-R1; mean AIME24/25 for agentic mathematics; the average of AMC, AIME24, and AIME25 for tool-free reasoning, all in percent. Checkpoints are shown in italic brackets in the first column. DARS rows are shaded. Rows marked † are published references ( Feng et al., 2025 ) .

Setting	DARS	Local GiGPO reference	$\Delta$ vs. reference	$\Delta$ vs. published
ALFWorld 1.5B	$96.9$	$86.9$ (same 500-step budget)	$+10.0$ ( $p=0.001$ ; 4/4)	$+10.2$
ALFWorld 7B	$98.6$	$98.1$ (same 500-step budget)	$+0.5$ ( $p=0.014$ ; 9W/2L/5T)	$+7.8$
WebShop 1.5B ‡	$83.1$ / $93.4$	$81.5$ / $92.4$ (parent, 400 steps)	$+1.5$ / $+1.1$ ( $p=0.001$ ; 11/12)	$+15.7$
WebShop 7B ‡	$88.5$ / $94.6$	$84.3$ / $93.1$ (parent, 600 steps)	$+4.2$ / $+1.5$ ( $p=0.0005$ ; 12/12)	$+13.3$
Search-R1 shared	$43.1$	$38.7$ (662 steps; DARS 360)	$+4.4$ (3/3 groups)	–
Search-R1 held-out	$41.6$	$39.5$ (one epoch each)	$+2.1$ (3/3 groups)	–

Appendix

Table 7: Matched references for the DARS rows of Table 1 . Success (success / task score for WebShop).

\Delta

against the reference is paired over identical evaluation draws where available, with

p

and draws won as in Tables 8 and 12 ; the last column repeats the margin over the stronger published GiGPO variant. ‡ DARS continuation from the listed parent.

Environment	Method	Success $\uparrow$	Task score $\uparrow$	$\Delta$ ( $p$ )
ALFWorld 1.5B, 500 steps	GiGPO (local)	$86.9\pm 0.8$	–	–
ALFWorld 1.5B, 500 steps	DARS (ours)	$\mathbf{96.9\pm 0.0}$	–	$\mathbf{+10.0}$ ( $0.001$ ; 4/4 draws)
ALFWorld 1.5B, 200 steps	GRPO (local)	$71.7\pm 0.6$	–	$-17.0$
	RLOO (local)	$86.9\pm 0.6$	–	$-1.8$
	GiGPO (local)	$88.7\pm 0.8$	–	–
	DARS (ours)	$\mathbf{92.0\pm 0.2}$	–	$\mathbf{+3.3}$ ( $0.02$ ; 4/4 draws)

Appendix

Table 8: Budget-matched local baselines. GRPO, RLOO, and GiGPO trained by us with the same script, hyper-parameters, policy-training budget, and evaluation harness as the DARS arm of the same block, and evaluated on the same checksum-verified evaluation file; only the advantage estimator or the content of the step channel differs. ALFWorld 1.5B has two blocks: the 500-step runs behind Table 1 (GiGPO and DARS launched together on one host) and the earlier 200-step runs that include GRPO and RLOO; ALFWorld 7B trains every arm for 500 steps, WebShop for 150 steps at 1.5B and 250 at 7B. ALFWorld 7B rows use training-validation peaks; final and intermediate checkpoints appear in Table 11 .

\pm

is the standard error over independent decoding draws (4 at ALFWorld 1.5B; 16 at ALFWorld 7B; 12 paired at WebShop 7B; WebShop 1.5B cells are means of 4 draws, 8 for GRPO).

\Delta

is the difference from local GiGPO (success, or success / task score), computed as the paired mean difference on shared environment seeds where draws are paired (all 8 shared seeds for ALFWorld 7B GRPO and RLOO) and as the difference of means otherwise;

p

is an exact sign-flip test over paired draws where at least 8 exist, otherwise a Welch

t

-test over draws. WebShop 1.5B GRPO was evaluated on a different host from its references, so no

\Delta

or paired test is reported for those rows. The ALFWorld 1.5B 500-step and ALFWorld 7B DARS rows repeat Table 1 ; the WebShop DARS rows are the fixed-budget runs trained from the instruction-tuned policy, not the continuation policies of Table 1 . Scores are percentages and

\Delta

is in percentage points; DARS rows are shaded.

Step	100	150	200	300	400	500 (final)
GiGPO (local)	$67.7\pm 1.9$	$86.5\pm 1.0$	$90.2\pm 0.2$	$84.6\pm 0.2$	$86.3\pm 0.4$	$86.9\pm 0.8$
DARS	$\mathbf{77.9\pm 1.6}$	$\mathbf{91.6\pm 0.6}$	$\mathbf{91.0\pm 0.4}$	$\mathbf{90.1\pm 0.7}$	$\mathbf{93.4\pm 0.4}$	$\mathbf{96.9\pm 0.0}$
$\Delta$ (draws won)	$+10.2$ (4/4)	$+5.1$ (4/4)	$+0.8$ (3/4)	$+5.5$ (4/4)	$+7.1$ (4/4)	$\mathbf{+10.0}$ (4/4)

Appendix

Table 9: ALFWorld 1.5B milestone curve of the 500-step runs (unseen-game success, mean

\pm

SE over the same four evaluation seeds per cell; the step-500 DARS entry is repeated in Table 1 ).

Method	Pick	Look	Clean	Heat	Cool	Pick2	All
GiGPO	72.6	100.0	82.6	100.0	93.5	97.5	88.7
+ DARS	88.3	91.9	93.2	90.3	92.4	100.0	92.0

Appendix

Table 10: ALFWorld per-class success (unseen split, 200-step runs of Table 8 , step-200 checkpoint, four draws). Classes: Pick

=

pick_and_place , Look

=

look_at_obj_in_light , Clean / Heat / Cool

=

pick_X_then_place , Pick2

=

pick_two_obj_and_place . Success in percent. In these runs DARS improves overall success from

88.7\%

92.0\%

(

+3.3

points), with the largest gains on Pick (

+15.7

) and Clean (

+10.6

), and reaches perfect success on Pick2. GiGPO remains stronger on Look, Heat, and Cool.

Figure 3: ALFWorld 1.5B learning dynamics of the 200-step runs in Table 8 (validation on the 128 unseen games every five steps, one draw at temperature

0.4

). DARS reaches each success level earlier in (a) optimizer steps and (b) rollout tokens, and (c) ends with lower token entropy.

Selection	Method	Step	Draws	Success $\uparrow$	$\Delta$	W/8
Peak	GiGPO	470	8	$98.1\pm 0.1$	–	–
	GRPO	460	16	$87.4\pm 0.4$	$-10.3\pm 0.4$	0/8
	RLOO	460	16	$85.9\pm 0.4$	$-12.2\pm 0.5$	0/8
Final	GiGPO	500	8	$97.0\pm 0.2$	–	–
	GRPO	500	16	$81.1\pm 0.4$	$-15.8\pm 0.6$	0/8
	RLOO	500	16	$87.6\pm 0.4$	$-9.7\pm 0.6$	0/8

Appendix

Table 11: ALFWorld 7B baselines across checkpoint selections. Success is mean

\pm

SE over the listed decoding draws on 128 unseen games. “Peak” is selected on training validation, not on these evaluation draws.

\Delta

is baseline minus GiGPO, mean

\pm

SE over eight shared evaluation seeds; W counts baseline wins. All eight baseline–GiGPO tests have two-sided exact sign-flip

p=0.0078

. GiGPO rows use the archived reference pools for this comparison; the peak row here has eight draws, while Table 8 reports its fuller 16-draw summary. Paired differences need not equal differences of the displayed full-cell means. Success and differences are in percent.

Size	Checkpoint	Success	Task score	$\Delta$ success (won; $p$ )	$\Delta$ task score (won; $p$ )
1.5B, selection draws (seeds 0–11)
1.5B	GiGPO parent (400 steps)	$80.4\pm 2.4$	$91.7\pm 1.0$	–	–
	DARS, graded, seed 1, step 400 (locked)	$82.1\pm 2.2$	$93.0\pm 1.0$	$+1.7$ (11/12; .001)	$+1.3$ (12/12; .0005)
	DARS, graded, seed 0, step 400	$82.1\pm 2.2$	$93.0\pm 1.2$	$+1.7$ (9/12; .004)	$+1.3$ (10/12; .003)
	DARS, graded, mixing weight $0.10$ , step 400 ( $n{=}11$ )	$81.6\pm 2.4$	$93.1\pm 1.1$	$+1.3$ (10/11; .002)	$+1.4$ (11/11; .001)
1.5B, confirmation draws (fresh seeds 12–23)

Appendix

Table 12: WebShop continuation from our best saved stock-GiGPO checkpoint. Mean

\pm

standard deviation over decoding draws;

\Delta

is the paired difference on identical environment seeds, computed before rounding (draws won / total; raw two-sided sign-flip

p

, leading zero omitted). The confirmation rows are the headline and the main-table cells: fresh evaluation seeds on the same validation task pool. At 1.5B, success wins on confirmation are 11 wins and one tie and task-score wins are 11 wins and one loss; at 7B every confirmation draw favors DARS on both metrics. Scores are percentages;

\Delta

in points; DARS rows are shaded.

Size (added steps)	GiGPO continuation $-$ parent	DARS continuation $-$ parent	DARS $-$ GiGPO continuation
	success / task score	success / task score	success; task score
7B (+250)	$+2.8$ / $+2.3$	$+4.2$ / $+2.1$	$\mathbf{+1.5}$ (20/2/2; $p<10^{-5}$ ); $-0.2$ ( $p=0.16$ )
1.5B (+400)	$+2.0$ / $+1.0$	$+1.7$ / $+1.2$	$-0.3$ ( $p=0.12$ ); $+0.3$ ( $p=0.13$ )

Appendix

Table 13: WebShop continuation versus an equally extended GiGPO continuation of the same parent (fresh evaluation seeds 12–35,

n=24

, paired by seed; draws won / tied / lost; exact sign-flip

p

). The 7B success contrast passes the Holm correction over the four DARS-versus-control claims. Differences are in percentage points.

	Success			Task score
Step	DARS	GiGPO twin	$\Delta$ (W/L; $p$ )	DARS	GiGPO twin	$\Delta$ (W/L; $p$ )
50	$36.8\pm 1.1$	$34.0\pm 0.9$	$+2.8\pm 1.1$ (7/4; $0.042$ )	$73.6\pm 0.4$	$68.5\pm 0.4$	$+5.1\pm 0.5$ (12/0; $0.0005$ )
100	$61.3\pm 0.9$	$55.7\pm 0.9$	$+5.6\pm 0.8$ (12/0; $0.0005$ )	$82.3\pm 0.3$	$79.2\pm 0.4$	$+3.1\pm 0.5$ (12/0; $0.0005$ )
150	$\mathbf{70.6\pm 0.8}$	$65.6\pm 0.8$	$\mathbf{+5.0\pm 0.8}$ (11/0; $0.001$ )	$\mathbf{86.1\pm 0.5}$	$83.7\pm 0.3$	$\mathbf{+2.4\pm 0.4}$ (11/1; $0.001$ )
200 a	$74.5\pm 0.9$	$74.3\pm 0.9$	$+0.1\pm 0.7$ (3/4; $0.89$ )	$87.7\pm 0.3$	$88.1\pm 0.6$	$-0.4\pm 0.4$ (3/5; $0.40$ )
50 b	$37.0\pm 1.1$	$33.8\pm 0.9$	$+3.2\pm 1.0$ (9/3; $0.009$ )	$73.8\pm 0.8$	$67.6\pm 0.6$	$+6.2\pm 0.7$ (12/0; $0.0005$ )

Appendix

Table 14: WebShop 1.5B from scratch: DARS (additive,

\alpha=1

) versus an identically configured GiGPO twin at matched steps (training seed 0). Mean

\pm

standard error over evaluation seeds 0–11 (12 draws); a evaluation seeds 0–7 (8 draws); b fresh evaluation seeds 12–23 (12 draws).

\Delta

is the difference paired by evaluation seed, with its standard error, draws won / lost, and the exact two-sided sign-flip

p

. The standard errors reflect evaluation variability, not training-seed variability. Scores are percentages;

\Delta

in points.

Track	Topology	Node instantiation (per rollout)	$\kappa$	$\lambda$	$\sigma$	Optional terms
ALFWorld 1.5B/7B	Object chains	objects, treatment	$0.3$	$1.0$	$1.0$	none
WebShop 1.5B (fixed budget)	Parallel-AND	attributes, options	$0.3$ / $1.0$	$1.0$	$1.0$	optional verifier
WebShop 7B (fixed budget)	Parallel-AND	attributes, options	$0.3$	$1.0$	$1.0$	none
Search-R1 7B	Hop chain	required hops	$0.3$	$1.0$	$1.0$	answer-commitment term
Math with Python	Derivation chain	required steps	$0.3$	$1.0$	$1.0$	none
Math tool-free	Derivation chain	required steps	$0.3$	$1.0$	$1.0$	none

Appendix

Table 15: Reward configurations behind the main DARS results. Topology is the fixed domain rule; node instantiation is performed jointly with event annotation for each rollout. The WebShop continuation study uses its own configuration (Appendix E ).

Variant	Success $\uparrow$	Task score $\uparrow$
GiGPO (local)	$65.9$	$84.9$
DARS, $\kappa=0.3$	$63.0$	$77.6$
DARS, $\kappa=1$	$67.7$	$\mathbf{85.8}$
DARS, $\kappa=1$ $+$ completion verifier	$\mathbf{69.6}$	$85.6$

Appendix

Table 16: WebShop 1.5B clip-bound sensitivity. Same optimizer, rollout budget and step-

150

checkpoint; four decoding draws at temperature

0.4

. Scores in percent; DARS rows are shaded.

Arm	NQ	TriviaQA	PopQA	HotpotQA	2Wiki	MuSiQue	Bamboogle	All
GiGPO (step 662)	33.3	66.0	49.5	37.5	46.8	15.0	28.5	39.5
DARS (step 360)	39.0	66.2	54.7	50.2	42.7	17.7	37.2	44.0
$\Delta$	$+5.7$	$+0.2$	$+5.2$	$+12.7$	$-4.1$	$+2.7$	$+8.7$	$+4.5$

Appendix

Table 17: Search-R1 shared-pool diagnostic by QA subset (first decoding group, four draws, final checkpoints; each subset has 100 questions, and “All” pools them). DARS is higher on six of seven subsets, with the largest gains on the multi-hop HotpotQA and Bamboogle subsets. Accuracy in percent;

\Delta

in points; DARS is shaded.

Arm	Selected step	test350	$\Delta$ vs. GiGPO (per group)
GiGPO (our reproduction)	600	$39.5\pm 0.4$	–
Commitment terms only	100	$24.6\pm 0.5$	$-15.0$ ( $-15.7$ , $-13.5$ , $-15.7$ )
Graph credit only	80	$36.9\pm 0.3$	$-2.6$ ( $-2.9$ , $-2.0$ , $-3.0$ )
DARS, $\sigma=0.5$	410	$39.7\pm 0.2$	$+0.2$
DARS (Table 1 )	490	$\mathbf{41.6\pm 0.6}$	$+2.1$ ( $+1.8$ , $+3.5$ , $+1.0$ )

Appendix

Table 18: Search-R1 held-out protocol. Exact-match accuracy on test350 at each arm’s val350 -selected checkpoint; mean

\pm

SE over three decoding groups of four draws each. The commitment-only and graph-only arms each keep one of the two terms of the DARS reward (a

2\times 2

factorial with GiGPO and DARS; same launcher, rendering, and selection rule). Accuracy in percent; DARS rows are shaded.

Step	Arm	MATH500	AIME24	AIME25	Mean AIME
5	ARPO	—	68.3	55.0	61.7
	AEPO	93.3	72.5	54.2	63.3
	ARPO $+$ DARS	95.8	64.2	54.2	59.2
	AEPO $+$ DARS	93.3	65.8	55.0	60.4
10	ARPO	—	65.8	56.7	61.3
	AEPO	90.0	65.8	57.5	61.7

Appendix

Table 19: Matched-step results by benchmark. Accuracy in percent; DARS arms are shaded.

Arm	MATH500	GSM8K	MATH
AEPO	94.8	95.6	97.3
AEPO $+$ DARS	94.9	96.1	96.9
ARPO $+$ DARS	94.6	95.8	96.2

Appendix

Table 20: Saturated benchmarks at each arm’s best grid checkpoint. Accuracy in percent; DARS arms are shaded.

Signal source	Arm	cells	Avg.	$\Delta$ vs. DARS ( $p$ /wins)
Dependency graph	DARS ( $\eta{=}1$ , $\lambda{=}1$ )	10	58.23 (1.09)	–
	DARS, $\lambda{=}0$ (same graphs)	14	57.50 (1.13)	$-0.73$ (7/10)
	DARS ( $\eta{=}2$ )	3	57.27 (1.75)	$-0.96$
	DARS, wider group admission	3	57.14 (0.44)	$-1.09$
	DARS, broken-node penalty ( $\rho_{\mathrm{b}}{=}0.25$ )	3	57.10 (0.15)	$-1.13$
	DARS, answer-commit gates	3	57.08 (0.33)	$-1.15$

Appendix

Table 21: Reported arms, tool-free reasoning, Qwen3-1.7B chat (78 cells). Average of AMC, AIME24, and AIME25 (Avg.), as the mean over evaluation cells (standard deviation across cells in parentheses);

p

is an exact permutation test against DARS (

\eta{=}1

) where the cell composition permits one; for the

\lambda{=}0

arm the entry is the number of (checkpoint, host)-matched cells on which DARS is higher. ‡ evaluated on the second host.

Gate	1.7B	4B
Usable induced chains	96.9% (prior judge 61.4%)	91.2%
$\rho(\Phi_{G}(T),\text{outcome})$	$+0.468$	$+0.218$
Answer-node agreement with the outcome verifier	79%	80.2%
Groups with nonzero $\Phi$ variance	142/200	263 groups
Segments carrying credit	28.6%	28.3%
Negative credit share	3.5%	1.2%

Appendix

Table 22: Annotation gates, tool-free reasoning. Coverage is compared with the reference step judge.

Arm	$n$	Avg.	AIME
DARS ( $\eta{=}1$ )	20	79.50 (1.06)	70.88
Untrained model	14	79.17 (0.77)	70.15
DARS w/o step credit	13	79.13 (0.81)	69.95
StaRPO (paper segmentation)	4	78.94 (1.17)	69.90
Rejection fine-tuning	4	78.79 (1.16)	69.64
On-policy distillation	15	78.62 (0.96)	69.51

Appendix

Table 23: Tool-free reasoning at 4B (Qwen3-4B chat). Avg. is the mean of AMC, AIME24, and AIME25, and AIME is the mean of AIME24 and AIME25. The upper panel pools evaluation cells across hosts, with counts

n

and standard deviations in parentheses. The lower panel reports the primary-host analysis, using

16

15

13

, and

9

cells for DARS, initialization, the scalar control, and OmniOPD, respectively, with permutation

p

-values; this analysis uses a different evaluation-cell set from the pooled summary, so its counts are not a subset of the upper panel.

$\lambda$	Success	$\Delta$ vs. $\lambda=0$
$0$ (milestone counting)	90.2	–
$0.5$	94.3	$+4.1$
$1$ (default)	91.4	$+1.2$
$\infty$ (hard masking)	84.2	$-6.1$

Appendix

Table 24: Decay-strength sweep on ALFWorld 1.5B from initialization. Unseen-game success at the training-validation peak checkpoint, four draws per cell; distilled annotator,

\kappa=0.3

, 150 steps. Success in percent;

\Delta

in points.

Corpus	Variant	Changed	Mean change	10th pct.	$>50\%$ lost
WebShop 1.5B (371 graphs)	sequential chain	12.7%	$-20.4\%$	$-99.5\%$	25.2%
WebShop 1.5B (371 graphs)	$\lambda=0$	8.6%	$+27.6\%$	$+0.0\%$	0.0%
ALFWorld 1.5B (2000 graphs)	sequential chain	10.6%	$-1.0\%$	$-2.8\%$	0.5%
ALFWorld 1.5B (2000 graphs)	$\lambda=0$	11.7%	$-1.0\%$	$-9.5\%$	1.2%
ALFWorld 7B (27,520 graphs)	$\lambda=0$	2.0%	–	–	–
Math 1.7B (775 graphs)	$\lambda=0$	10.6%	–	–	–

Appendix

Table 25: Offline census of the ablations on persisted annotation graphs. “Changed” is the fraction of trajectories whose reward vector differs from the DARS reward; the remaining columns describe the distribution of the relative change in total credit over the changed trajectories.

Environment	Goal structure	First-error prefix credit vs. GiGPO	Observed behavior
ALFWorld	ordered chain	$+3.2$ points success	chain credit and graph credit nearly coincide
WebShop	parallel-AND	$-42$ points task score	credits 7 browsing turns without a purchase
Search-R1	instrumental prefix	success falls to $0\%$	$96\%$ of trajectories never commit an answer

Appendix

Table 26: First-error prefix credit as a graph-free process reward. The same annotator model localizes the first erroneous turn and the turns before it receive front-weighted credit (no predicates, no dependency graph). Outcomes relative to the GiGPO baseline in each environment’s earlier local study (training-validation peaks for ALFWorld).

$t$	Executed action	Recorded events	$\Phi_{G}$	Credit
0	search[blu ray gold plated high speed heavy duty HDMI cable blue braided 20-pack price < 40.00]	—	$0.000$	$+0.000$
1	click[b08qsnm69h]	Verify: T, A1, A2, A3, A4, P	$0.750$	$+0.300$
2	click[20-pack]	Verify: S	$0.875$	$+0.125$
3	click[blue braided]	Verify: C	$1.000$	$+0.125$
4	click[buy now]	—	$1.000$	$+0.000$

Appendix

Table 27: Completing both requested options (record 71441). All five actions are shown.

$t$	Executed action	Recorded events	$\Phi_{G}$	Credit
0	search[Vanity bronze finish vanity light price < 110.00]	—	$0.000$	$+0.000$
1	click[b09j9y9h95]	Verify: T, B, L, P	$1.000$	$+0.300$
2	click[back to search]	Error: B, L	$0.500$	$-0.300$
3	search[ Kira Home Ainsley 21.5" 3-Light Farmhouse Vanity/Bathroom Light + Clear Cylinder Glass Shades, Oil-Rubbed Bronze Finish $77.99]	—	$0.500$	$+0.000$
4	click[b09j9y9h95]	Verify: T, B, L, P; Repair: B, L	$1.000$	$+0.300$
5	click[buy now]	—	$1.000$	$+0.000$

Appendix

Table 28: Abandoning and recovering a suitable product (record 71074). All six actions are shown.

$t$	DARS	GiGPO
0	Search: Uruguayan former footballer who managed team with Charlie Oatway	Search: What is the birthdate of this Uruguayan former footballer, who management team consists of Charlie Oatway
1	Search: Gus Poyet Uruguayan football manager	Search: Gastón Pereyra birthdate uruguayan former footballer
2	Answer: 15 November 1967	Search: Gastón Pereyra birthdate uruguayan former footballer
3	—	Answer: 30 May 1984

Appendix

Table 29: Search: using the retrieved intermediate entity. Complete action sequences; no shaping credits were recorded at evaluation.

$t$	DARS	GiGPO
0	go to countertop 1	go to countertop 1
1	go to toilet 1	take soapbottle 1 from countertop 1
2	take soapbar 1 from toilet 1	go to garbagecan 1
3	go to garbagecan 1	move soapbottle 1 to garbagecan 1
4	move soapbar 1 to garbagecan 1	go to countertop 1
5	go to toilet 1	go to toilet 1

Appendix

Table 30: ALFWorld: avoiding a soap-bottle detour on a soapbar task. Complete action sequences; both policies succeed.

$t$	DARS	GiGPO
0	go to sidetable 1	go to sidetable 1
1	go to shelf 1	go to dresser 1
2	go to dresser 1	go to sofa 1
3	go to sofa 1	go to sidetable 1
4	go to sidetable 1	go to armchair 1
5	go to armchair 1	take pillow 1 from armchair 1

Appendix

Table 31: ALFWorld: completing the second required pillow. Complete action sequences; DARS succeeds at action 13, GiGPO reaches the 50-action limit.

$t$	DARS	GiGPO
0	Search: Team USA baseball at 2000 Summer Olympics	Search: Which of the starting pitchers for Team USA in the Baseball at the 2000 Summer Olympics was not born August 29, 1977
1	Search: Ben Sheets born date 1977 August 29	Answer: Juan Pe~na
2	Answer: Ben Sheets	—

Appendix

Table 32: Search: checking the birthdate exclusion. Complete action sequences; no shaping credits were recorded at evaluation.

Explore similar work

Aug 4, 2026cs.LG

Agentic Reinforcement Learning with Self-Distilled Reward Shaping

Agentic reinforcement learning enables LLM agents to learn through interaction, but sparse trajectory-level rewards reveal success without identifying which intermediate decisions deserve credit. Training-only privileged skills can provide denser supervision by allowing the same frozen policy snapshot to rescore fixed tokens from skill-free trajectories while conditioned on task-matched procedural skills. Existing methods, however, do not jointly calibrate teacher scores across interaction steps, relate teacher confidence to realized returns, and integrate the resulting signal into native reward-to-advantage construction. We introduce Agentic Reinforcement Learning with Self-Distilled Reward Shaping (ADRS), a framework for constructing return-associated token-level credit for multi-turn language agents. ADRS centers and normalizes privileged token scores within each step, modulates them with a return-associated Teacher Value Advantage (TVA) gate based on within-group confidence--return association, and incorporates the gated token signal into native RL credit construction. Together, these components determine what the teacher prefers, when that preference is return-relevant, and how it enters the native reinforcement-learning credit path, while keeping rollouts and inference skill-free. Finally, experiments across three interactive benchmarks show that ADRS consistently improves performance on long-horizon tasks, with gains persisting across RL backbones, reduced-data settings, unseen tasks, and extended training. For anonymous review, our code is available at the following the link: https://github.com/gitrxh/ADRS-arxiv

Ranxu Zhang, Guinan Chen, Chenshaodong +5

Alibaba Group · University of Science and Technology of China Hefei, China · Alibaba Group Hangzhou, China

Agentic Reinforcement Learning Potential-Based Reward Shaping Credit Assignment Teacher

Ask PDF

Sep 30, 2026cs.LG

Make Sparse Rewards Count: Density-Aware Reward Aggregation for Multi-Reward RL

Multi-reward reinforcement learning trains large language models to satisfy multiple behavioral objectives simultaneously. Reward-wise normalization, as used in GDPO, preserves reward-specific relative information within rollout groups, but different objectives can still exhibit uneven learning progress. We study this behavior through advantage energy, the sum of a reward's squared advantages over a batch. Under idealized GDPO normalization, we show that this energy is proportional to active-group density: the fraction of rollout groups in which the reward provides nonzero relative advantages. This reveals a residual batch-level signal imbalance and provides a basis for calibrating reward contributions. Based on this relation, we propose Density-Aware Reward Aggregation (DARA). We derive an inverse-square-root density correction that gives greater weight to signals from less frequently active rewards. DARA computes its weights from each rollout batch, adapting to changes in reward activity throughout training without modifying the underlying policy optimization objective. Experiments on tool calling and mathematical reasoning show that DARA learns the targeted behaviors faster than GDPO, reaching high format compliance in up to 26% fewer training steps on tool calling and near-saturated length compliance in up to 65% fewer steps on mathematical reasoning, while remaining competitive in final performance. Our code is available at https://github.com/zhaihaotian/DARA.

Tong Zheng, Skylar Zhai, Zhan Cheng +7

University of Chinese Academy of Sciences · University of Minnesota Twin Cities · University of Wisconsin–Madison +5

Topic pending

Ask PDF

Sep 30, 2026cs.LG

SHARPO: Segment-Level Credit Assignment for Agentic Reinforcement Learning

Agentic reinforcement learning (RL) trains a large language model (LLM) to act over long, multi-step interactions. However, a single localized error can cause task failure, while trajectory-level rewards provide limited guidance for assigning credit to individual decisions. To address this limitation, we introduce Segment-level Hindsight Advantage Reweighting for Policy Optimization (SHARPO), a credit-assignment mechanism that refines Group Relative Policy Optimization (GRPO) at the level of environment-facing segments. Inspired by the existing on-policy self-distillation (OPSD) method, SHARPO computes teacher-student log-probability gaps within each segment and uses the resulting signal to compute a bounded multiplier on the GRPO advantage. This multiplier is shared by all tokens within the segment, allowing credit to vary across different segments. With Qwen2.5-7B-Instruct, SHARPO outperforms existing baselines on the ALFWorld and WebShop benchmarks, including GRPO, SDAR, RLSD, and StepOPSD.

Xinchen Du, Zhengze Zhou, Wenhui Zhu +4

LinkedIn Corporation · Georgia Institute of Technology

Agentic Reinforcement Learning Credit Assignment

Ask PDF