Beyond Trajectory Rewards: Step-level Credit Assignment for Agentic Search via Graph Modeling
In Agentic Search, trajectory-level outcome rewards fail to quantify the behavioral contributions of individual steps, while existing step-level reward methods typically rely on costly tree sampling. We view world knowledge as a latent world graph and each IS task as search within a latent task graph, where effective steps should make graph progress toward the answer node. Based on this prior, we propose Graph-Distance Contribution Reward (GDCR), a step-level process reward that scores newly-retrieved and newly-cited entities by their distance to the answer node in a training-time Entity-Relation (ER) graph. We further propose Step Advantage Policy Optimization (SAPO), which converts GDCR into step-level advantages and combines them with trajectory-level outcome advantages. Experiments on four challenging benchmarks validate the effectiveness of our method.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
TIER: Trajectory-Invariant Execution Rewards for Multi-Step Tool Composition
Tool use enables large language models to solve complex tasks through sequences of API calls, yet existing reinforcement learning approaches fail to scale to multi-step composition settings. Outcome-based rewards provide…
Reinforcement LearningABSeeker: Training Long-Horizon Search Agents via Answer-Backtracked Credit Assignment
Long-horizon search agents must make multiple sequential actions (steps) to search, retrieve, verify, and integrate evidence to reach a final answer. However, existing methods for training these agents typically treat al…
Reinforcement LearningMemory-R2: Fair Credit Assignment for Long-Horizon Memory-Augmented LLM Agents
Memory-augmented LLM agents enable interactions that extend beyond finite context windows by storing, updating, and reusing information across sessions. However, training such agents with reinforcement learning in multi-…
Reinforcement LearningPiCA: Pivot-Based Credit Assignment for Search Agentic Reinforcement Learning
Large Language Model (LLM)-based search agents trained with reinforcement learning (RL) have significantly improved the performance of knowledge-intensive tasks. However, existing methods encounter critical challenges in…
Reinforcement LearningAgentic Reinforcement Learning with Implicit Step Rewards
Large language models (LLMs) are increasingly developed as autonomous agents using reinforcement learning (agentic RL) that reason and act in interactive environments. However, sparse and sometimes unverifiable rewards m…
Reinforcement Learning