Title: BranPO: Scalable Contrastive Branch Sampling for Long-Horizon Agentic Reinforcement Learning

Abstract:

While agentic reinforcement learning empowers large language models to execute multi-turn planning and utilize tools, training over long horizons presents significant difficulties. This challenge stems from sparse, trajectory-level rewards, where a single final outcome is uniformly attributed to every decision made along the way. Although prior approaches attempt to mitigate this by implementing finer-grained supervision through tree-based exploration or process-level evaluation, these methods frequently suffer from high computational costs or generate noisy credit assignment signals.

A key characteristic of agentic trajectories is "non-monotonic correctness." This phenomenon occurs because early errors can be rectified by subsequent actions, whereas seemingly advantageous intermediate states may ultimately fail due to poor later decisions. Consequently, outcome rewards or state values alone are inadequate for directing specific actions from any given state.

To resolve these issues, we introduce Branching Relative Policy Optimization (BranPO), a value-free methodology that establishes localized contrastive supervision without relying on dense rewards. BranPO operates by truncating trajectories at intermediate prefixes and resampling their continuations to create contrastive branches. These branches share identical prefixes but result in divergent final outcomes, allowing the model to isolate the specific decisions that determine success or failure. Additionally, we implement difficulty-aware branch sampling and Redundant Step Masking to enhance sampling efficiency and eliminate redundant updates. Our experimental results demonstrate that BranPO consistently surpasses various baseline categories across multiple multi-hop question-answering benchmarks without incurring extra training expenses. Furthermore, it shows consistent improvements when applied to a wider range of long-horizon agentic tasks. Our code is publicly accessible at https://github.com/YubaoZhao/BranPO.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC