mlsanityData to 7 Oct 2026

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

arXiv 2610.01207 ↗First posted 1 Oct 2026cs.AIcited by 0

On the map: LLM agents and tool use → Reinforcement learning for LLM agents

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use. Builds on 44 of its 56 references that are in the map. First posted on arXiv 1 Oct 2026.

Builds on

44 of 56 references.

Closest ancestors · 11

Same direction, newest first

  1. 2026Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning26 May
  2. 2026HiPER: Hierarchical Reinforcement Learning with Explicit Credit Assignment for Large Language Model Agents18 Feb
  3. 2026Learning from the Irrecoverable: Error-Localized Policy Optimization for Tool-Integrated LLM Reasoning10 Feb
  4. 2025CARL: Criticality-Aware Agentic Reinforcement Learning4 Dec
  5. 2025Tree Search for LLM Agent Reinforcement Learning25 Sep
  6. 2025Agentic Reinforcement Learning with Implicit Step Rewards23 Sep
  7. 2025The Landscape of Agentic Reinforcement Learning for LLMs: A Survey2 Sep
  8. 2025Agentic Reinforced Policy Optimization26 Jul
  9. 2025SPA-RL: Reinforcing LLM Agents via Stepwise Progress Attribution27 May
  10. 2025Group-in-Group Policy Optimization for LLM Agent Training16 May
  11. 2024ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL29 Feb

Other references · 33

  1. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  2. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  3. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  5. 2023Let's Verify Step by Stepcited by 3,598
  6. 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scalecited by 2,678
  7. 2024A Survey on LLM-as-a-Judgecited by 1,384
  8. 2025Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learningcited by 1,371
  9. 2022WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agentscited by 1,197
  10. 2020ALFWorld: Aligning Text and Embodied Environments for Interactive Learningcited by 1,143
  11. 2024Tulu 3: Pushing Frontiers in Open Language Model Post-Trainingcited by 988
  12. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 895
21 more
  1. 2022Solving math word problems with process- and outcome-based feedbackcited by 871
  2. 2023On-Policy Distillation of Language Models: Learning from Self-Generated Mistakescited by 840
  3. 2025Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoningcited by 540
  4. 2025Process Reinforcement through Implicit Rewardscited by 478
  5. 2024ProcessBench: Identifying Process Errors in Mathematical Reasoningcited by 277
  6. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoningcited by 267
  7. 2024Agent-as-a-Judge: Evaluate Agents with Agentscited by 223
  8. 2025Which Agent Causes Task Failures and When? On Automated Failure Attribution of LLM Multi-Agent Systemscited by 170
  9. 2018RUDDER: Return Decomposition for Delayed Rewardscited by 162
  10. 2024Free Process Rewards without Process Labelscited by 162
  11. 2024The pitfalls of next-token predictioncited by 156
  12. 2025Phi-4-reasoning Technical Reportcited by 146
  13. 2025Where LLM Agents Fail and How They can Learn From Failurescited by 118
  14. 2019Hindsight Credit Assignmentcited by 74
  15. 2022LAMBADA: Backward Chaining for Automated Reasoning in Natural Languagecited by 66
  16. 2025Emergent Hierarchical Reasoning in LLMs through Reinforcement Learningcited by 42
  17. 2023Would I have gotten that reward? Long-term credit assignment by counterfactual contribution analysiscited by 10
  18. 2026Entropy-Preserving Reinforcement Learningcited by 10
  19. 2026StaRPO: Stability-Augmented Reinforcement Policy Optimizationcited by 5
  20. 2026OmniOPD: Logit-Free On-Policy Distillation via Speculative Verificationcited by 5
  21. 2026Not All Tokens Learn Alike: Attention Entropy Reveals Heterogeneous Signals in RL Reasoningcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Agentic Reinforcement Learning with Self-Distilled Reward Shaping
  2. 2026RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models
  3. 2026Verifiable Process Rewards for Agentic Reasoning
  4. 2026From Reasoning to Agentic: Credit Assignment in Reinforcement Learning for Large Language Models
  5. 2026Rewarding Beliefs, Not Actions: Consistency-Guided Credit Assignment for Long-Horizon Agents
  6. 2026Beyond Reward Engineering: A Data Recipe for Long-Context Reinforcement Learning
  7. 2026Reward-Zero: Language Embedding Driven Implicit Reward Mechanisms for Reinforcement Learning
  8. 2026TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents