RewardFlow：智能体 RL 中动作级奖励能否从状态图拓扑中估计

View PDF

Abstract:In agentic tasks such as household assistance and web shopping, large language model (LLM) agents take multiple actions before receiving a final outcome indicating success or failure. For reinforcement learning (RL), this outcome obscures individual actions' contributions: a shopping trajectory may find the right product but fail to complete the purchase. To address this credit-assignment problem, we introduce RewardFlow, which connects multiple trajectories for the same task through shared states (states grouped by task-relevant equivalence or semantic similarity). The resulting directed state graph links observed trajectory segments. Therefore, an action in a failed trajectory may reach a state from which another trajectory succeeds. It propagates reward signals backward from states where the task succeeds, assigning state potentials that decrease with shortest-path distance to success in the graph. Potential differences then reward actions that reduce this distance, bringing the agent closer to success in the graph. These estimated rewards yield action-level advantages that complement trajectory-level advantages from outcome rewards during policy optimization, without a learned process reward model or manual action-level annotations. Experiments on ALFWorld, WebShop, Sokoban, and search tasks show gains over RL baselines across model scales. With 3B policies, graph construction and reward estimation take $1.47$-$2.39$ seconds per training step on ALFWorld, WebShop, and Sokoban (Fig. 1). Code is available at this https URL.

Submission history

From: Xiao Feng [view email]
[v1] Thu, 19 Mar 2026 13:07:12 UTC (1,915 KB)
[v2] Thu, 28 May 2026 06:59:57 UTC (1,737 KB)
[v3] Thu, 12 Nov 2026 03:57:23 UTC (1,446 KB)