RewardFlow: Can Action-Level Reward Be Estimated from State-Graph Topology in Agentic RL?
Xiao Feng, Bo Han, Zhanke Zhou, Jiaqi Fan, Jiangchao Yao, Ka Ho Li, Dahai Yu, Michael Kwok-Po Ng
原文摘要
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 https://github.com/tmlr-group/RewardFlow.
cs.AI · cs.CL · cs.LG