Training Multi-Turn Search Agent via Contrastive Dynamic Branch Sampling
This work addresses a key bottleneck in agentic reinforcement learning for complex planning, offering a more efficient and stable method for training search agents, though it is incremental relative to prior tree-based approaches.
The paper tackles the challenge of sparse rewards in long-horizon reinforcement learning for multi-turn search agents by proposing Branching Relative Policy Optimization (BranPO), which uses contrastive supervision to reduce credit ambiguity, resulting in significant accuracy gains on long-horizon tasks without increasing training budget.
Agentic reinforcement learning has enabled large language models to perform complex multi-turn planning and tool use. However, learning in long-horizon settings remains challenging due to sparse, trajectory-level outcome rewards. While prior tree-based methods attempt to mitigate this issue, they often suffer from high variance and computational inefficiency. Through empirical analysis of search agents, We identify a common pattern: performance diverges mainly due to decisions near the tail. Motivated by this observation, we propose Branching Relative Policy Optimization (BranPO), a value-free method that provides step-level contrastive supervision without dense rewards. BranPO truncates trajectories near the tail and resamples alternative continuations to construct contrastive suffixes over shared prefixes, reducing credit ambiguity in long-horizon rollouts. To further boost efficiency and stabilize training, we introduce difficulty-aware branch sampling to adapt branching frequency across tasks, and redundant step masking to suppress uninformative actions. Extensive experiments on various question answering benchmarks demonstrate that BranPO consistently outperforms strong baselines, achieving significant accuracy gains on long-horizon tasks without increasing the overall training budget. Our code is available at \href{https://github.com/YubaoZhao/BranPO}{code}.