Paper 2606.12384
APPO: Agentic Procedural Policy Optimization
- Published
- Jun 2026
- Research lab
- Independent
- Citations
- 0
- GitHub
- 73 stars
01 In brief
Summary
The paper introduces APPO (Agentic Procedural Policy Optimization), a reinforcement learning algorithm for LLM agents that shifts branching and credit assignment from coarse units like tool-call boundaries to fine-grained decision points in the generated sequence.
A pilot study showed that influential decision points are distributed throughout the thinking span, and token entropy alone does not reliably indicate their impact.
APPO selects branching locations using a Branching Score that combines token entropy with a future-aware likelihood gain (Ω), filtering out spurious high-entropy positions.
It also introduces procedure-level advantage scaling and dual-group advantage estimation for branches and initial rollouts.
Experiments on 13 benchmarks (mathematical reasoning, knowledge-intensive reasoning, and deep search) show APPO consistently improves over strong baselines like ARPO by nearly 4 points on average, with gains in pass@k and training stability.
Ablations confirm the contribution of each component.
Theoretical results provide variance reduction and policy improvement bounds.
02 From the paper
Abstract
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.