Training Multi-Turn Search Agent via Contrastive Dynamic Branch Sampling

• URL: http://arxiv.org/abs/2602.03719v1
• Date: Tue, 03 Feb 2026 16:43:09 GMT
• Title: Training Multi-Turn Search Agent via Contrastive Dynamic Branch Sampling
• Abstract summary: Branching Relative Policy Optimization (BranPO) is a value-free method that provides step-level contrastive supervision without dense rewards.<n>BranPO truncates trajectories near the tail and resamples alternative continuations to construct contrastive suffixes over shared prefixes.<n>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.
• Score: 29.182538022605627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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}.

Related papers

• Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching [70.73681123064533]
  We show that a simple and unbiased dense reward formulation, which we term progressive point matching, scales exponentially more efficiently to long-horizon tasks.<n>On extremely hard math reasoning problems, sparse outcome rewards cannot make any progress, whereas segment-level rewards enable improvements at larger test-time token budgets.
  arXiv  Detail & Related papers  (2026-09-07T10:21:41Z)
• SCOUT: Self-Checking and Recovery-Aware Tool-Thought Agents for Ultra-Long Egocentric Video Reasoning [45.039898006163405]
  We develop SCOUT (Self-Checking Chain-Of-Tool-thought), a recovery-aware agentic framework for ultra-long egocentric video understanding.<n>SCOUT trades off exploitation (zoom-in) and exploration (region switching) to enable robust multi-hop reasoning over extremely long horizons.<n>We show that SCOUT achieves state-of-the-art results on ultra-long egocentric benchmarks, while remaining competitive on shorter-horizon long-video settings.
  arXiv  Detail & Related papers  (2026-08-08T06:48:08Z)
• CARE: Competence-Aware Reward Shaping for Adaptive Reasoning Length in Video-MLLMs [50.189987475377656]
  We propose CARE, a competence-aware reward shaping framework for adaptive reasoning length optimization in multimodal reasoning.<n> CARE maintains a smoothed competence estimate via an exponential moving average of pass rates, and uses it to route training into progressive stages.<n>Experiments on multiple video reasoning and general video understanding benchmarks demonstrate that CARE consistently improves reasoning accuracy, stabilizes reinforcement learning, and significantly enhances token efficiency.
  arXiv  Detail & Related papers  (2026-06-18T08:28:26Z)
• APPO: Agentic Procedural Policy Optimization [28.730334202611257]
  We study agentic RL from two perspectives: textitwhere to branch and how to assign credit after branching<n>We propose APPO, which shifts branching and credit assignment from coarse interaction units to fine-grained decision points in the sequence.<n>APPO consistently improves strong agentic RL baselines by nearly 4 points, while keeping efficient tool-calls and maintaining behavior interpretability.
  arXiv  Detail & Related papers  (2026-06-10T17:47:07Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Reducing Credit Assignment Variance via Counterfactual Reasoning Paths [11.514388061694268]
  Reinforcement learning for multi-step reasoning with large language models (LLMs) often relies on sparse terminal rewards.<n>We introduce a counterfactual comparison-based credit assignment framework, which samples multiple reasoning trajectories under the same input.<n>We construct an implicit process-level advantage estimator that transforms sparse terminal rewards into step-sensitive learning signals.
  arXiv  Detail & Related papers  (2026-04-20T13:33:54Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
  We propose Search-R2, a novel Actor-Refiner collaboration framework that enhances reasoning through targeted intervention.<n>Our approach decomposes the generation process into an Actor, which produces initial reasoning trajectories.<n>We show that Search-R2 consistently outperforms strong RAG and RL-based baselines across model scales.
  arXiv  Detail & Related papers  (2026-02-03T15:32:09Z)
• Spark: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning [31.17280303212164]
  We propose textbfSpark (textbfStrategic textbfPolicy-textbfAware explotextbfRation via textbfKey-state dynamic branching)<n>Our key insight is to activate adaptive branching exploration at critical decision points to probe promising trajectories.<n>textscSpark achieves superior success rates with significantly fewer training samples, exhibiting robust generalization even in unseen scenarios.
  arXiv  Detail & Related papers  (2026-01-28T03:15:34Z)
• Reinforced Efficient Reasoning via Semantically Diverse Exploration [73.41112984160992]
  Reinforcement learning with verifiable rewards (RLVR) has proven effective in enhancing the reasoning of large language models (LLMs)<n>We propose reinforced efficient reasoning via semantically diverse explorations, i.e., ROSE, for LLMs.<n>Our method incorporates a semantic-entropy-based branching strategy and an $varepsilon$-exploration mechanism.
  arXiv  Detail & Related papers  (2026-01-08T15:56:44Z)
• Anti-Length Shift: Dynamic Outlier Truncation for Training Efficient Reasoning Models [29.56923793047279]
  We introduce Dynamic Outlier Truncation (DOT), a training-time intervention that selectively suppresses redundant tokens.<n>DOT targets only the extreme tail of response lengths within fully correct rollout groups while preserving long-horizon reasoning capabilities.<n>Our method reduces inference token usage by 78% while simultaneously increasing accuracy compared to the initial policy.
  arXiv  Detail & Related papers  (2026-01-07T14:31:07Z)
• BOTS: A Unified Framework for Bayesian Online Task Selection in LLM Reinforcement Finetuning [82.925106913459]
  Reinforcement finetuning (RFT) is a key technique for aligning Large Language Models (LLMs) with human preferences and enhancing reasoning.<n>We introduce BOTS, a unified framework for Bayesian Online Task Selection in RFT reinforcement finetuning.
  arXiv  Detail & Related papers  (2025-10-30T11:15:23Z)
• Reinforcing Video Reasoning with Focused Thinking [65.85683941058916]
  We propose TW-GRPO, a novel framework that enhances visual reasoning with focused thinking and dense reward granularity.<n>Specifically, we employ a token weighting mechanism that prioritizes tokens with high informational density.<n>We also reformulate RL training by shifting from single-choice to multi-choice QA tasks.
  arXiv  Detail & Related papers  (2025-05-30T15:42:19Z)
• Reinforcing Multi-Turn Reasoning in LLM Agents via Turn-Level Reward Design [35.544075583073685]
  We present the first systematic study of textitturn-level reward design for multi-turn RL algorithms and agent applications.<n>We conduct case studies on multi-turn reasoning-augmented search agents, where we carefully design two types of turn-level rewards: verifiable and LLM-as-judge.<n>Our experiments on multi-turn search tasks demonstrate that incorporating well-designed turn-level rewards enables RL algorithms to significantly outperform baseline methods with trajectory-level rewards.
  arXiv  Detail & Related papers  (2025-05-17T04:09:46Z)
• The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs [40.35884943268004]
  We show that for very long sequences, larger and highly sparse models are preferable to smaller and dense ones.<n>There is no clear strategy that performs best across tasks and phases, with different units of sparsification or budget adaptivity needed for different scenarios.<n>We introduce and validate novel scaling laws specifically tailored for sparse attention, providing evidence that our findings are likely to hold true beyond our range of experiments.
  arXiv  Detail & Related papers  (2025-04-24T17:39:25Z)
• Path-Consistency with Prefix Enhancement for Efficient Inference in LLMs [3.6696973040141034]
  path-consistency improves inference latency by up to 40.5%, while maintaining task accuracy across various tasks.<n>Our empirical results demonstrate that path-consistency improves inference latency by up to 40.5%, while maintaining task accuracy across various tasks.
  arXiv  Detail & Related papers  (2024-08-25T01:45:53Z)
• Deep Boosting Learning: A Brand-new Cooperative Approach for Image-Text Matching [53.05954114863596]
  We propose a brand-new Deep Boosting Learning (DBL) algorithm for image-text matching. An anchor branch is first trained to provide insights into the data properties. A target branch is concurrently tasked with more adaptive margin constraints to further enlarge the relative distance between matched and unmatched samples.
  arXiv  Detail & Related papers  (2024-04-28T08:44:28Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.