APPO: Agentic Procedural Policy Optimization
Xucong Wang, Ziyu Ma, Yong Wang, Yuxiang Ji, Shidong Yang, Guanhua Chen, Pengkun Wang, Xiangxiang Chu
APPO tackles a specific weakness in how RL training signals get distributed across LLM agent trajectories: existing methods assign credit at coarse boundaries like tool-call edges or fixed workflow steps, which misses the fine-grained decisions that actually drive outcomes. The method introduces a Branching Score combining token-level uncertainty with policy-induced likelihood gains to find where to branch during rollout, then uses procedure-level advantage scaling to distribute credit across those branches. Across 13 agentic benchmarks, it claims roughly 4-point gains over strong baselines while keeping tool-call efficiency intact.
No production traction yet. Zero citations and the GitHub appearances are all automated paper-tracking feeds, not implementations or integrations. This is very fresh (June 2025) and the ideas — fine-grained branching during RL rollouts for agent training — are relevant to anyone building on frameworks like RAGEN or OpenRLHF, but nothing is shipping against this paper yet.
Recent advances in agentic Reinforcement Learning (RL) have substantially improved the multi-turn tool-use capabilities of large language model agents. However, most existing methods assign credit over coarse heuristic units, such as tool-call boundaries or fixed workflows, making it difficult to identify which intermediate decisions influence downstream outcomes. In this work, we study agentic RL from two perspectives: \textit{where to branch and how to assign credit after branching}. Our pilot analysis shows that influential decision points are broadly distributed throughout the generated sequence rather than concentrated at tool calls, while token entropy alone does not reliably reflect their impact on final outcomes. Motivated by these observations, we propose \textbf{Agentic Procedural Policy Optimization (APPO)}, which shifts branching and credit assignment from coarse interaction units to fine-grained decision points in the sequence. APPO selects branching locations using a Branching Score that combines token uncertainty with policy-induced likelihood gains of subsequent continuations, enabling more targeted exploration while filtering out spurious high-entropy positions. It further introduces procedure-level advantage scaling to better distribute credit across branched rollouts. Experiments on 13 benchmarks show that APPO consistently improves strong agentic RL baselines by nearly 4 points, while keeping efficient tool-calls and maintaining behavior interpretability.