Reinforcement learning with verifiable rewards (RLVR) enables language models to learn multi-turn interaction with external tools, yet its sparse outcome rewards provide no signal for identifying which intermediate decisions are responsible for success. Branch sampling induces local comparisons among alternative continuations, but existing methods tend to conflate two distinct problems: allocating a fixed rollout budget and translating branch outcomes into token-level credit. We introduce Contrastive Branch Policy Optimization (CBPO), which disentangles these two problems and assigns a dedicated mechanism to each. Generation entropy screens candidate branch positions across the entire response, while path-level and node-level decay distribute a fixed budget across trajectories and positions to prevent exploration from collapsing onto a few paths or adjacent tokens. A parent trajectory together with the branches that share an identical token prefix forms an exact-prefix group, and the reward variation within this controlled group defines the Contrastive Branch Value (CBV), an outcome-based estimate of local decision sensitivity that rescales continuation advantages without altering their sign. When multiple nodes are selected along the same trajectory, CBPO partitions it into non-overlapping credit segments, thereby avoiding duplicated gradients on shared tokens. Requiring only outcome rewards and no process-level annotation, CBPO provides a practical solution for fine-grained credit assignment in tool-integrated agent training. Extensive experiments on ten benchmarks, including five for mathematical reasoning and five for knowledge-intensive search, show that CBPO consistently outperforms state-of-the-art policy-optimization and branch-based methods, attaining the highest macro-average accuracy in both domains and across two model scales.
Figures & tables
Figure 1. CBPO training framework. The model first performs interactive reasoning with Python and Search tools and samples complete initial trajectories. Candidate nodes are identified across the full response, and path-level and node-level decay allocate the branch budget. Outcome rewards estimate CBV within exact-prefix groups. Shared-prefix deduplication and non-overlapping hierarchical segmentation then construct token-level advantages for the policy update. End-to-end CBPO pipeline from tool-integrated trajectory sampling through balanced branching, CBV estimation, and policy optimization.
Figure 2. Full-response candidate discovery. Fixed-interval entropy scans identify high-entropy decisions beyond predefined tool-call boundaries. Line plot of token entropy across a full response, with fixed-interval windows, tool-call positions, and selected candidate branch points.
Figure 3. Outcome-contrastive credit assignment. Exact-prefix continuations are compared by outcome to construct CBV-aware credit while deduplicating shared-prefix credit. Tree schematic in which three continuations share a prefix, receive different outcome rewards, and obtain CBV-aware continuation credit alongside deduplicated shared-prefix credit.
Table 1. Measured results (%) for Qwen3-1.7B and Qwen3-4B under a unified protocol. Mathematical tasks report Pass@1; WebWalker reports LLM-as-a-Judge Pass@1; the other search tasks report normalized token-level F1. Math Avg. and Search Avg. are unweighted five-task means. Green subscripts show improvement over size-matched GIGPO.
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 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.
Xucong Wang, Ziyu Ma, Yong Wang +5
University of Science and Technology of China · AMAP, Alibaba Group · Southern University of Science and Technology
Reinforcement learning has emerged as the dominant paradigm for training large language model (LLM) agents that interact with executable sandboxes. State-of-the-art algorithms such as PPO, RLOO, and GRPO inherit their rollout topology from RLHF: for each prompt, N independent trajectories are sampled from the initial state, and an advantage is computed by subtracting a group baseline. This design ignores a defining property of agent sandboxes. They are deterministic, snapshottable, and resumable from any intermediate state. We argue that this property enables a fundamentally different rollout topology: rather than N independent trees of depth T, one can construct a single tree of N leaves whose siblings share prefixes, and therefore share variance. We instantiate this idea as Branching Policy Optimization (BPO), a sandbox-native RL algorithm that (i) adaptively snapshots the sandbox at high-entropy decision points along a backbone trajectory, (ii) forks K alternative actions per branch point and rolls out each to termination, and (iii) computes per-step advantages from sibling returns rather than from independent prompts. We prove this estimator is unbiased and has strictly lower variance than the trajectory-level baseline, with the reduction equal to the prefix-explained portion of return variance. On WebShop, ALFWorld, and SWE-bench Verified with Qwen2.5-7B and Llama-3.1-8B backbones, BPO improves success by 3.6--6.1 absolute points over GRPO and RLOO at matched compute, halves gradient-norm variance, and matches the best baseline using 38% fewer policy updates.
Bowei He, Yankai Chen, Xiaokun Zhang +1
Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE · McGill Univeristy, Montreal, Canada · City University of Hong Kong, Hong Kong SAR.
Reinforcement learning with verifiable rewards (RLVR) has become a powerful paradigm for improving the reasoning abilities of large language models, yet group-based methods lose their learning signal when every sampled response receives zero reward. We propose Group Contrastive Policy Optimization (GCPO), a hybrid objective that preserves standard on-policy optimization for informative rollout groups and activates a proximal contrastive objective only when exploration completely fails. The auxiliary objective pairs an offline golden reasoning trajectory with the current policy's failed responses, thereby providing a reliable positive reference and prompt-specific hard negatives without treating the golden trajectory as an on-policy rollout. Its old-policy token probabilities are evaluated through teacher forcing and used solely to constrain the update, rather than as an importance-sampling correction for the teacher distribution. A first-order analysis shows that the resulting update increases a length-normalized likelihood margin between reliable reasoning and observed failures. Experiments across two model scales and 10 core mathematical reasoning benchmarks demonstrate that GCPO improves training efficiency and final reasoning performance over competitive supervised and RLVR baselines.