PORTool: Importance-Aware Policy Optimization with Rewarded Tree for Multi-Tool-Integrated Reasoning

1. Problem Statement

The paper addresses the challenge of training Large Language Model (LLM) agents to perform multi-tool-integrated reasoning (interleaving natural language reasoning with external tool calls). While Reinforcement Learning (RL) has shown promise, existing methods suffer from credit-assignment ambiguity when relying solely on outcome-level rewards (i.e., whether the final answer is correct).

• Step-Supervised Limitations: Methods like ToolRL assign rewards at every step based on ground-truth intermediate actions. This enforces rigid, canonical routines, discourages exploration, and fails in non-stationary environments where tool outputs vary (e.g., real-time weather data).
• Trajectory-Supervised Limitations: Methods like GRPO or ARPO optimize based on the final outcome of a trajectory. However, they broadcast the same trajectory-level reward to all steps. This creates ambiguity: the model cannot distinguish which specific tool-call decision led to success or failure.
• The Core Issue: The authors prove (Theorem 3.1) that uniform credit assignment can lead to "collateral unlearning," where the model decreases the probability of generating a necessary step because that step appeared in some failed trajectories (due to other errors later in the chain).

2. Methodology: PORTool

The authors propose PORTool (Importance-Aware Policy Optimization with Rewarded Tree), a framework that transforms sparse outcome feedback into fine-grained, step-level importance signals without requiring dense step annotations.

A. Rewarded Rollout Tree (Tree Rollouts)

Instead of sampling $n$ trajectories independently, PORTool organizes rollouts into a bounded-branching tree:

• Prefix Sharing: Trajectories share the same initial prefix (history) and diverge only at specific tool-call steps (forks).
• Matched Comparisons: This structure allows for direct comparison of sibling actions (different tool calls) under the exact same context, isolating the impact of specific decisions.

B. Step-Wise Importance Estimation

PORTool computes a reward $R(s_{j,t})$ for each step by aggregating the outcomes of its descendants in the tree:
$$R(s_{j,t}) = G\left( \{ \gamma^{T_k-t} R_{out}(q, \tau_k) + R_{fm}(s_{j,t}) \}_{k \in m(s_{j,t})} \right)$$

• Outcome Dominance: The primary signal is the final answer correctness ($R_{out} \in \{+1, 0, -1\}$), decayed by a factor $\gamma$ to favor shorter trajectories.
• Auxiliary Signal: A bounded formatting/execution reward ($R_{fm}$) is added to penalize invalid JSON or failed tool calls, but it is scaled to be strictly smaller than the outcome reward to ensure correctness remains the priority.
• Adaptive Aggregation ($G$):
  • If sibling branches have different best-case outcomes, $G$ uses max to highlight the superior branch.
  • If siblings are tied in best-case performance, $G$ uses avg to favor the branch with higher reliability (consistency of success) rather than a single lucky rollout.

C. Mixed Advantage Optimization

The policy is updated using a token-level advantage $A(s_{j,t,o})$ that combines two signals:

1. Trajectory-Relative Advantage ($A_{trj}$): A coarse-grained signal comparing the entire trajectory against other sampled trajectories.
2. Fork-Relative Advantage ($A_{fork}$): A fine-grained signal comparing a specific step against its siblings at the same fork in the tree.

The final advantage is a weighted sum:
$$A(s_{j,t,o}) = \omega_1 \cdot \text{Avg}(A_{trj}) + \omega_2 \cdot A_{fork}$$
The authors derive a principled scaling for $\omega_2$ (Theorem 3.2) to ensure the fork-level objective aligns mathematically with the standard per-token GRPO objective, preventing gradient distortion.

3. Key Contributions

1. Theoretical Insight: Formalized the problem of "collateral unlearning" in trajectory-supervised RL, proving that uniform rewards can suppress necessary steps.
2. Algorithm Design: Introduced PORTool, which utilizes a prefix-sharing rollout tree to enable within-context comparisons and derives a step-wise importance signal from sparse outcome feedback.
3. Robust Learning Signal: Proposed an adaptive aggregation mechanism that distinguishes between "lucky" successes and "reliable" strategies, ensuring the model learns robust tool-use policies.
4. Empirical Validation: Demonstrated that PORTool outperforms state-of-the-art baselines (GRPO, ARPO, AgentFlow, etc.) in accuracy while reducing the number of tool calls and failure rates.

4. Experimental Results

The method was evaluated on a dataset of 3,607 real-world user queries across 8 domains (Weather, Sports, Geo, etc.) using Qwen-2.5-7B and Qwen-3-1.7B backbones.

• Accuracy: PORTool achieved the highest accuracy (51.98% on Qwen-2.5-7B), outperforming the second-best baseline (ARPO/AgentFlow ~48%) by a significant margin.
• Efficiency: It reduced the average number of tool-call steps (3.07 vs. ~3.3 for baselines), indicating more efficient decision-making.
• Robustness: It significantly lowered the unanswerable rate (7.10% vs. >11% for baselines) and improved formatting/execution scores.
• Generalization: PORTool showed strong performance on out-of-distribution benchmarks (ToolBench and TravelPlanner), achieving the best or tied-best aggregate pass rates, proving its ability to generalize beyond the training distribution.
• Ablation Studies:
  • Decay Factor ($\gamma$): $\gamma=0.95$ provided the best balance between correctness and efficiency.
  • Advantage Scaling: The theoretically derived scaling for $\omega_2$ was crucial; removing it or using only trajectory/fork advantages led to performance drops.
  • Aggregation ($G$): The adaptive (max/avg) rule outperformed fixed "always max" or "always avg" strategies.

5. Significance

PORTool represents a significant advancement in Agentic RL by solving the fundamental credit-assignment problem in multi-step tool use.

• Practical Impact: It enables LLM agents to learn from real-world, dynamic tool interactions without needing expensive step-by-step human annotations.
• Reliability: By distinguishing between necessary steps and incidental errors, it prevents the model from "unlearning" correct behaviors, leading to more robust and reliable agents in production environments.
• Efficiency: The method encourages the model to find the most direct path to a solution, reducing computational costs associated with excessive tool calls.

In summary, PORTool bridges the gap between sparse outcome supervision and fine-grained policy optimization, offering a scalable and robust framework for training LLM agents in complex, multi-tool environments.