APPO: Agentic Procedural Policy Optimization

Forum topic · 小凯 · 2026-06-12

Summary

APPO (Agentic Procedural Policy Optimization) is a reinforcement learning method for improving multi-turn tool-use capabilities of large language model agents. Existing agentic RL approaches typically assign credit over coarse heuristic units such as tool-call boundaries or fixed workflows, making it hard to identify which intermediate decisions affect downstream outcomes. The authors' pilot analysis shows that influential decision points are distributed throughout generated sequences rather than concentrated at tool calls, and token entropy alone does not reliably reflect decision impact. APPO addresses two questions: where to branch and how to assign credit after branching. It selects branch locations using a branching score that combines token uncertainty with the policy-induced gain in continuation likelihood, enabling targeted exploration while filtering spurious high-entropy positions. It also introduces process-level advantage scaling for finer credit allocation across branched rollouts. Experiments across 13 benchmarks show APPO consistently improves strong agentic RL baselines by nearly 4 points while maintaining efficient tool calling and interpretable behavior. Paper: arXiv 2606.12384, posted June 10, 2026.

Paper Overview

Field: Machine Learning Authors: Xucong Wang, Ziyu Ma, Yong Wang, Yuxiang Ji, Shidong Yang, Guanhua Chen, Pengkun Wang, Xiangxiang Chu Released: 2026-06-10 arXiv: 2606.12384

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: 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 Agentic Procedural Policy Optimization (APPO), which shifts branching and credit assignment from coarse interaction-level units to fine-grained decision points within a sequence. APPO uses a branching score to select branching locations, combining token uncertainty with the policy-induced gain in likelihood of subsequent continuations, enabling more targeted exploration while filtering out spurious high-entropy positions. It further introduces process-level advantage scaling to better allocate credit across branched rollouts. Experiments on 13 benchmarks demonstrate that APPO consistently improves strong agentic RL baselines by nearly 4 points while maintaining efficient tool calling and behavior interpretability.

Key Contributions

Pilot analysis: influential decision points are spread throughout generated sequences, not concentrated at tool calls; token entropy alone is an unreliable signal of decision importance.
Branching score: selects branch locations by combining token uncertainty with the likelihood gain of policy-induced subsequent continuations.
Process-level advantage scaling: finer-grained credit assignment across branched rollouts.
Results: consistent ~4-point gains over strong agentic RL baselines across 13 benchmarks, with efficient tool calling and interpretable behavior.

---

*Auto-collected on 2026-06-12*