Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agents

• URL: http://arxiv.org/abs/2607.06223v1
• Date: Tue, 07 Jul 2026 12:47:23 GMT
• Title: Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agents
• Abstract summary: Reinforcement learning has become a promising paradigm for improving large language model (LLM) agents on long-horizon search tasks.<n>Existing methods face a key limitation: the rollout budget is often allocated without explicitly assessing the utility of intermediate states.<n>We propose Information Gain-based Rollout Policy Optimization (IGRPO), a policy optimization framework that treats intermediate-state informativeness as the organizing principle of rollout collection.
• Score: 38.00321502420564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning has become a promising paradigm for improving large language model (LLM) agents on long-horizon search tasks, where the agent must make a sequence of intermediate decisions before receiving a final outcome. However, existing methods still face a key limitation: the rollout budget is often allocated without explicitly assessing the utility of intermediate states. As a result, substantial computation may be spent on low-value states, even though different branches can vary drastically in their informativeness. In this paper, we propose Information Gain-based Rollout Policy Optimization (IGRPO), a policy optimization framework that treats intermediate-state informativeness as the organizing principle of rollout collection. Specifically, IGRPO performs budget-aware tree-structured rollouts by allocating expansion budget according to node-level informativeness, so that more informative branches are expanded more frequently while unpromising branches are progressively suppressed. We further demonstrate that the information gain-based rollout induces an explicit limiting teacher distribution over trajectories, which naturally yields a clear policy optimization target, thereby unifying adaptive tree-structured exploration with principled policy learning under a single framework. Experiments on seven challenging search-augmented QA benchmarks demonstrate that IGRPO consistently outperforms strong baselines under the same rollout budget constraints, validating the effectiveness of leveraging the induced teacher distribution to guide policy optimization for long-horizon search agents.

Related papers

• 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)
• Ratio-Variance Regularized Policy Optimization [64.95520246570446]
  We show that explicitly constraining the policy ratio variance provides a principled local approximation to trust-region constraints.<n>We introduce $bf R2bf VPO$ (Ratio-Variance Regularized Policy Optimization), which implements this constraint via a primal-dual optimization framework.
  arXiv  Detail & Related papers  (2026-05-26T09:53:42Z)
• One-Way Policy Optimization for Self-Evolving LLMs [63.8638342097375]
  Reinforcement Learning with Verifiable Rewards (RLVR) has become a promising paradigm for scaling reasoning capabilities of Large Language Models (LLMs)<n>We propose One-Way Policy Optimization (OWPO), a method based on the principle of decoupling optimization direction from update magnitude.<n> Experimental results demonstrate that OWPO outperforms strong baselines, including DAPO, OPD, and MOPD.
  arXiv  Detail & Related papers  (2026-05-21T08:25:27Z)
• Segment-Aligned Policy Optimization for Multi-Modal Reasoning [55.29606572822562]
  We propose a novel reinforcement learning paradigm that treats coherent reasoning steps, rather than tokens or full sequences as fundamental units of policy update.<n>Experiments on representative reasoning benchmarks demonstrate that SAPO consistently outperforms token-level and sequence-level policy optimization methods.<n>Our work underscores the importance of aligning reinforcement learning updates with the structure of reasoning, paving the way for more efficient and semantically grounded policy optimization in complex reasoning tasks.
  arXiv  Detail & Related papers  (2026-05-02T08:47:45Z)
• Enhancing LLM-based Search Agents via Contribution Weighted Group Relative Policy Optimization [47.7937991619078]
  We propose Contribution-Weighted GRPO, a framework that integrates process supervision into group relative policy optimization.<n>CW-GRPO employs an LLM judge to assess the retrieval utility and reasoning correctness at each search round, producing per-round contribution scores.<n> Experiments on multiple knowledge-intensive benchmarks show that CW-GRPO outperforms standard GRPO by 5.0% on Qwen3-8B and 6.3% on Qwen3-1.7B.
  arXiv  Detail & Related papers  (2026-04-15T17:37:59Z)
• Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization [60.87651283510059]
  Group Relative Policy Optimization (GRPO) effectively scales LLM reasoning but incurs prohibitive computational costs.<n>We propose Dynamic Pruning Policy Optimization (DPPO), a framework that enables dynamic pruning while preserving unbiased gradient estimation.<n>To mitigate the data sparsity induced by pruning, we introduce Dense Prompt Packing, a window-based greedy strategy.
  arXiv  Detail & Related papers  (2026-03-04T14:48:53Z)
• Learning Branching Policies for MILPs with Proximal Policy Optimization [0.0]
  Branch-and-Bound (B&B) is the dominant exact solution method for Mixed Linear Programs (MILP)<n>Current approaches rely on Imitation Learning (IL), which tends to overfit to expert demonstrations and struggles to generalize to structurally diverse or unseen instances.<n>In this work, we propose Tree-Gate Proximal Policy Optimization, a novel framework that employs Proximal Policy Optimization (PPO), a Reinforcement Learning (RL) algorithm, to train a branching policy.
  arXiv  Detail & Related papers  (2025-11-17T05:16:14Z)
• Think Outside the Policy: In-Context Steered Policy Optimization [13.24687763539952]
  In-context Steered Policy Optimization provides expert guidance using existing datasets.<n>ICPO consistently enhances reinforcement learning performance and training stability on mathematical reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-10-30T14:14:15Z)
• Information Gain-based Policy Optimization: A Simple and Effective Approach for Multi-Turn LLM Agents [28.145430029174577]
  Large language model (LLM)-based agents are increasingly trained with reinforcement learning (RL) to enhance their ability to interact with external environments.<n>Existing approaches typically rely on outcome-based rewards that are only provided at the final answer.<n>In this paper, we propose Information Gain-based Policy Optimization (IGPO), a simple yet effective RL framework that provides dense and intrinsic supervision for multi-turn agent training.
  arXiv  Detail & Related papers  (2025-10-16T17:59:32Z)

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.