acceptodds
Under review as a conference paper at ICLR 2027

APPO: Agentic Procedural Policy Optimization

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 high-entropy candidate positions are distributed throughout generated reasoning rather than concentrated only at tool calls, while entropy alone does not reliably order observed branch outcomes. Motivated by these observations, we propose 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 future-aware Branching Score that combines token uncertainty with a discounted suffix policy-shift signal. It further introduces dual-group advantage estimation and procedure-level advantage scaling to provide more targeted credit after branching. We evaluate APPO on 13 benchmarks spanning mathematical reasoning, knowledge-intensive reasoning, and deep search, and find consistent improvements over strong agentic RL baselines by nearly 4 points on aggregate, while retaining efficient tool use and interpretable behavior.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Agent, LLMs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_q5KFOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Agentic Procedural Policy Optimization (APPO), a framework that shifts branching and credit assignment from coarse-grained tool-call boundaries to fine-grained decision points in agentic reasoning trajectories. APPO introduces a future-aware Branching Score that combines token entropy with discounted suffix policy shifts, together with dual-group advantage estimation and procedure-level advantage scaling. Experiments across mathematical reasoning, knowledge-intensive reasoning, and deep-search benchmarks demonstrate improvements over existing agentic reinforcement learning baselines.

Critical strengths
  1. The paper identifies an important limitation of existing agentic RL methods, namely their reliance on coarse-grained branching and credit assignment at tool-call or workflow boundaries. Motivating finer-grained exploration through a pilot study provides a reasonable starting point for the proposed approach.
  2. APPO combines a future-aware Branching Score, dual-group advantage estimation, and procedure-level advantage scaling within a unified framework. The paper also includes component-wise ablations to investigate the contributions of these mechanisms.
  3. The authors evaluate APPO across a broad range of mathematical reasoning, knowledge-intensive reasoning, and deep-search benchmarks, using multiple model backbones and competitive baselines. The reported improvements across different tasks and model scales suggest the potential usefulness of the proposed method.
Critical weaknesses
  1. The paper lacks sufficient theoretical justification for the proposed method. In particular, there is no rigorous analysis explaining why the discounted suffix policy-shift signal can identify important procedural decisions or improve credit assignment. The proposed mechanisms remain largely heuristic.

  2. The formulation of the Branching Score raises concerns. Multiplying two z-score-normalized quantities may assign high scores to tokens with both low entropy and low policy shift. Moreover, when the current policy equals the behavior policy, the policy-shift signal becomes constant, potentially making the normalization undefined. These issues undermine the reliability of the core algorithm.

  3. The claimed procedure-level credit assignment is not convincingly demonstrated. The proposed advantage estimation still relies on trajectory-level rewards, and changes in token likelihood do not necessarily reflect the causal importance of intermediate decisions. Therefore, it remains unclear whether APPO genuinely achieves fine-grained credit assignment.

  4. The experimental evaluation is insufficient to fully support the claims. The paper lacks comprehensive multi-seed evaluations and statistical significance analysis, making it difficult to assess the robustness of the reported improvements. Furthermore, the ablation studies do not adequately investigate alternative Branching Score formulations or simpler advantage-scaling strategies, making it difficult to isolate the contributions of the proposed components.

Questions for authors
  1. Could the authors provide stronger theoretical justification for why the discounted suffix policy-shift signal can reliably identify important procedural decisions and improve credit assignment?

  2. How do the authors address the potential issues in Eq. (5), particularly the zero-variance normalization when the current policy equals the behavior policy and the possibility of assigning high scores to low-entropy, low-policy-shift tokens?

  3. Could the authors clarify how the proposed procedure-level advantage estimation differs fundamentally from trajectory-level credit assignment, given that it still relies on trajectory-level rewards?

  4. Could the authors provide additional ablations comparing alternative Branching Score formulations and simpler advantage-scaling strategies to better isolate the contributions of the proposed components?

2 comments

Thank you for the detailed assessment. We address the suffix signal, the behavior of Eq. (5), the status of the credit-assignment claim, and the ablation evidence.

The suffix signal within the score. Local entropy measures uncertainty at a candidate position. The discounted suffix signal summarizes how the likelihood of the realized continuation changes between the behavior policy and the current policy, with the form log Ω_{n,i} = Σ_{j≥i} γ^{j−i} log ρ_{n,j}, where the discount concentrates weight on nearby tokens and clipping bounds extreme ratios. The two signals describe different aspects of a candidate, namely how under-determined the position is and how strongly the observed continuation responds to the policy update. Positions in a reasoning trace are therefore ranked by local uncertainty together with the behavior of their continuation, not by local uncertainty alone. The branching criterion is a design choice whose justification is empirical, and the paper presents it as such rather than as a derived optimum. Section 2.2 defines the criterion, the pilot in Figure 2 compares branch accuracy under entropy and under the combined score, and the ablation in Table 4 shows that entropy-only selection reduces the five-task average from 58.1 to 56.3 on Qwen2.5-7B and from 57.9 to 57.0 on Llama3.1-8B.

Behavior of Eq. (5). You identify two properties of the product correctly. First, since both factors are within-rollout z-scores, the product is positive both when the two normalized terms are jointly above their means and when they are jointly below them. The score is a ranking over positions, and it does not assert that every selected position has above-average entropy and above-average suffix shift. Second, when the current policy coincides with the behavior policy every ratio equals one and the suffix signal is constant across positions. Eq. (5) computes the standard deviation within the rollout and adds a constant of 1e-6 to the denominator, so the standardized suffix value remains defined in this case, and all candidate positions then receive the same standardized suffix value. The product consequently carries no information about which position is preferable, and the retained positions follow the order in which candidate positions are enumerated along the sequence. The normalization is described in Section 2.2.

Procedure-level credit and outcome rewards. APPO optimizes with trajectory-level outcome rewards and makes the effective advantage vary across positions within a trajectory. The initial-rollout and branch groups supply outcome-based comparisons, and the suffix-based factor scales the resulting advantage at each position, so two positions in the same rollout carry different effective weights even though they share the same outcome reward. The reward direction comes from the outcome comparison, while the position weighting comes from the observed continuation. The distinction you draw is the one that matters here. A change in suffix likelihood is not a causal estimate of the effect of an individual token on the final outcome. What APPO provides is an optimization signal that is resolved at the level of positions inside a trajectory while keeping outcome-based supervision, and the ablations in Table 4 measure the effect of each part of this signal on task performance. The advantage structure is given in Section 2.3, and Appendix A summarizes the components and points to the pilot study and ablation results that examine them.

Alternative formulations and robustness. The component ablation in Table 4 reports three comparisons on the five-task average.

Five-task averageQwen2.5-7BLlama3.1-8B
APPO58.157.9
Entropy-only branching56.357.0
Without future-aware advantage54.756.5
Without dual-group estimation56.056.8

These isolate the branching criterion, the future-aware scaling and the dual-group estimation in turn. Appendix D visualizes alternative score combinations, including additive combinations and the suffix signal alone, as qualitative comparisons. Uncertainty is currently characterised through the consistent direction and magnitude of the ablation gaps across the two backbones.

We wish that the above would address your concerns!

Thank you for the authors' response. I will maintain my initial score.

Reviewer_tzZ5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes APPO, an agentic RL method that decides where to branch during rollouts and how to assign credit after branching. It branches at fine-grained positions within the reasoning process, rather than only at tool calls, and assigns credit at the process level.

Critical strengths
  1. The motivation is convincing. The pilot study shows that high-entropy tokens are not limited to tool calls and that entropy alone does not predict branch quality, which exposes a limitation of methods like ARPO. The Branching Score is also simple and needs no extra model.

  2. The experiments are comprehensive, with broad backbone and baseline coverage plus ablations, budget allocation, and Pass@K analyses.

Critical weaknesses
  1. Scope of evaluation environments. The paper is motivated by multi-turn tool use, but the evaluation focuses mainly on math and QA, with search and Python as the only tools. In Table 1, zero-shot Qwen2.5 already performs well on math, and TIR slightly lowers accuracy on GSM8K, which suggests these tasks may not depend heavily on tool use. The QA tasks also mostly follow a retrieve-then-answer pattern. Results on benchmarks with richer multi-turn interaction, such as ALFWorld and WebShop (used in GiGPO) or τ-bench, would help show how well the method carries over to more complex agentic settings.

  2. Clarity of procedure-level credit assignment. As I understand the formulation, the base advantage is shared across all tokens in a trajectory, and branches mainly contribute to the baseline rather than being trained on directly. The main token-varying term, A^fut\hat{A}^{fut}, appears to be an importance ratio that does not depend on reward. I may be missing something here, and a clearer explanation of how token-level credit arises would strengthen this part of the paper.

Questions for authors
  1. Would it be possible to include results on ALFWorld, WebShop, or τ-bench?

  2. After branching at position ii, how is the difference between successful and failed continuations credited back to position ii? If branching mainly affects the baseline, could the authors clarify how this differs from a standard trajectory-level advantage?

3 comments

Thank you for highlighting the motivation, the pilot study and the experimental coverage. We address the role of the evaluated environments and the mechanism that produces position-varying advantages.

Evaluation environments. Our evaluation spans mathematical reasoning, knowledge-intensive reasoning and deep search, with Search and Python as tools. Strong zero-shot performance on GSM8K indicates that this benchmark alone does not demand tool use, and the evaluation therefore also includes knowledge-intensive and deep-search tasks where retrieval supplies information required to answer. On deep search, APPO improves GAIA from 38.8 to 42.7 with Qwen3-8B and from 43.7 to 46.6 with Qwen3-14B, and HLE from 8.8 to 13.4 and from 10.0 to 12.3, as reported in Table 2. ALFWorld, WebShop and τ-bench use different action spaces and state transitions, and no results on these environments are reported in this submission. The scope of the evaluated tools and tasks is stated explicitly in the Limitations section.

Where the position-varying advantage comes from. Your reading of the base term is accurate. For an initial rollout, the base advantage is computed from outcome rewards and group statistics, so it is shared across positions of that rollout. The token-varying component is the future-aware factor, and it enters through a specific mechanism described in Section 2.3. Branches are not optimized directly, and gradients flow only through the initial rollouts, so the shared prefix between a rollout and its branches contributes to the gradient once. Branches contribute outcome values to the branch group, whose mean and standard deviation enter the base advantage through Eq. (6), and the discounted suffix likelihood ratio then scales that base advantage at each position as Â_{n,i} = Â_base_n (1 + b·Â_fut_{n,i}). The resulting objective therefore combines an outcome-level comparison across rollouts with a position-level weighting inside each rollout, rather than applying one unmodified trajectory advantage to all tokens.

How successful and failed continuations enter. Successful and failed continuations from a branching position contribute as outcome samples in the branch group of Eq. (6), which shifts the mean and standard deviation used for the base advantage, and the branch outcomes are additionally summarized by the suffix likelihood term that scales each position. Eq. (6) performs this comparison at the group level, and it does not define a separate per-position contrast between sibling branches. The ablation in Table 4 isolates the two parts of the design. On Qwen2.5-7B, removing future-aware scaling reduces the five-task average from 58.1 to 54.7 and removing dual-group estimation reduces it to 56.0, with corresponding values of 56.5 and 56.8 on Llama3.1-8B.

We wish that the above would address your concerns!

Dear reviewers,

Will you please check the authors' response and reply it?

Best, AC

Thank the authors for the detailed response. However, my concerns have not been fully addressed. The experiments on multi-turn agentic environments like ALFWorld were not provided, so my question of how well the method performs in other multi-turn agentic settings remains open. I will keep my original score.

Reviewer_tptXOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes APPO. The idea is to identify critical tokens that have high entropy and are likely to shift future trajectories and then branch from these tokens to sample paths. Through extensive benchmarking, the authors show modest improvements of APPO over other RL approaches.

Critical strengths

The proposed APPO method is reasonable. The evaluation is quite thorough across 13 different benchmarks. The paper included the relevant baseline methods such as ARPO.

Critical weaknesses

The authors should report results across multiple training seeds with error bars and compare against baselines under matched training compute (e.g generated tokens, tool calls, and GPU-hours).

It'd be helpful if the authors also clarify the main novelties of the method compared to literature, because many of the components of APPO have been explored before.

More quantitative analysis of the selected branching tokens would be interesting.

Questions for authors

See the suggestions above.

2 comments

Thank you for recognizing the motivation of APPO and the breadth of the evaluation. We address novelty, branching-position analysis, and experimental robustness below.

Novelty. APPO addresses two connected questions, namely where an agent should explore alternative continuations and how the resulting branch information should enter policy optimization. Relative to ARPO, which branches at high-entropy tokens following each tool call, APPO draws branching candidates from the entire generated reasoning sequence and ranks them with a Branching Score that multiplies within-rollout standardized token entropy and a discounted suffix policy-shift signal. Relative to FIPO, which uses a future-KL signal to reweight token advantages, APPO uses a suffix-based signal to select branching locations and additionally combines branch outcomes with group-relative advantage estimation. The contribution is the joint design of procedural branching and position-dependent advantage scaling, and it is stated in Section 2.2 and Section 2.3.

Quantitative analysis of branching positions. The pilot study in Figure 2 evaluates sampled continuations directly. Using Qwen2.5-7B-Instruct, 1,000 prompts, N=4 initial rollouts per prompt, 1,500 sampled candidate positions and top-B=3 branching, it bins branch accuracy for valid completed branches by entropy and by Branching Score under a shared candidate pool and continuation budget. High-entropy positions appear throughout reasoning rather than concentrating at tool calls, and the combined score orders observed branch outcomes more informatively than entropy alone. The component ablation in Table 4 measures the same design at the training level. Replacing the Branching Score with entropy-only selection reduces the five-task average from 58.1 to 56.3 on Qwen2.5-7B and from 57.9 to 57.0 on Llama3.1-8B, i.e. by 1.8 and 0.9 points respectively.

Seeds and compute. The reported figures are point estimates, and cost is accounted in rollout slots. The branching configuration analysis in Table 3 compares allocations at equal rollout budget. At M=16 on the same five tasks, ARPO reaches an average of 52.7 while APPO with (N=4, B=3) reaches 58.1, and other allocations of the same budget give 57.9 for (N=8, B=1) and 56.1 for (N=2, B=7). M counts rollout slots per prompt rather than generated tokens or GPU-hours, and the definition is given in Section 2.2.

We wish that the above would address your concerns!

I thank the authors for their response. I will keep my score of 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.