TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning

• URL: http://arxiv.org/abs/2606.11119v1
• Date: Tue, 09 Jun 2026 17:16:03 GMT
• Title: TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning
• Abstract summary: 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.
• Score: 52.67756371231985
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models. However, rollout-intensive policy optimization is often limited by insufficient reward contrast, arising when overly simple or complex prompts generate low-variance feedback and when outcome-only rewards assign the same terminal assessment to every decision in a multi-turn rollout. Past efforts have focused on allocating available rollout resources to promising prompts, yet they only leverage sample informativeness at the prompt level and neglect variation in prefix-level informativeness across turns within the same rollout. This work targets multi-turn agentic RL by modeling each ReAct-style thought-action-observation turn as a semantically distinct node, allowing budget allocation to extend from prompt roots to turn-level prefixes with further continuations, which naturally forms tree-structured rollouts. We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework that enhances reward contrast within a fixed sampling budget. Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards. A shared generalizable predictor estimates conditional success probability at these anchors from prefix histories to guide this allocation. The resulting adaptive tree structure enriches outcome-only feedback and amplifies the policy-update signal. Empirically, TRACE achieves competitive performance and efficiency gains on typical agentic benchmarks, e.g., improving Qwen3-14B Multi-Hop QA average accuracy by 2.8 points over competitive baselines at equal sampling cost.

Related papers

• Contrastive Branch Policy Optimization [16.16893757028268]
  Reinforcement learning with verifiable rewards (RLVR) enables language models to learn multi-turn interaction with external tools.<n>Existing methods tend to conflate two distinct problems: allocating a fixed rollout budget and translating branch outcomes into token-level credit.<n>We introduce Contrastive Branch Policy Optimization (CBPO), which disentangles these two problems and assigns a dedicated mechanism to each.
  arXiv  Detail & Related papers  (2026-08-25T09:25:55Z)
• Process Reward Informed Tree Rollout for Effective Multi-Turn RL [58.392997761968566]
  In long-horizon agentic tasks, a uniform rollout strategy can waste budget on uninformative dead-end attempts.<n>We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL.<n>PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops paths to reduce wasted sampling.
  arXiv  Detail & Related papers  (2026-07-17T04:16:58Z)
• Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agents [38.00321502420564]
  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.
  arXiv  Detail & Related papers  (2026-07-07T12:47:23Z)
• Breaking $\textit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
  Group Cooperative Policy Optimization shifts the training paradigm from rollout competition to team cooperation.<n>GCPO replaces independent rollout scoring with team-level credit assignment.<n>It redistributes the collective team reward to each single rollout according to its average marginal contribution to the team.
  arXiv  Detail & Related papers  (2026-05-12T03:20:24Z)
• Blockwise Advantage Estimation for Multi-Objective RL with Verifiable Rewards [39.489554597919145]
  Group Relative Policy Optimization (GRPO) assigns a single scalar advantage to all tokens in a completion.<n>For structured generations with explicit segments and objectives, this couples unrelated reward signals across segments, leading to objective interference and misattributed credit.<n>We propose Blockwise Advantage Estimation, a family of GRPO-compatible methods that assigns each objective its own advantage and applies it only to the tokens in the corresponding text block.
  arXiv  Detail & Related papers  (2026-02-10T19:22:37Z)
• Outcome-Grounded Advantage Reshaping for Fine-Grained Credit Assignment in Mathematical Reasoning [60.00161035836637]
  Group Relative Policy Optimization has emerged as a promising critic-free reinforcement learning paradigm for reasoning tasks.<n>We introduce Outcome-grounded Advantage Reshaping (OAR), a fine-grained credit assignment mechanism that redistributes advantages based on how much each token influences the model's final answer.<n>OAR-G achieves comparable gains with negligible computational overhead, both significantly outperforming a strong GRPO baseline.
  arXiv  Detail & Related papers  (2026-01-12T10:48:02Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• Enhancing Agentic RL with Progressive Reward Shaping and Value-based Sampling Policy Optimization [13.475938754147625]
  Large Language Models (LLMs) empowered with Tool-Integrated Reasoning (TIR) can iteratively plan, call external tools, and integrate returned information to solve complex, long-horizon reasoning tasks.<n>Agentic Reinforcement Learning (Agentic RL) optimize such models over full tool-interaction trajectories.<n>Two key challenges hinder effectiveness: (1) Sparse, non-instructive rewards, such as binary 0-1 verifiable signals, provide limited guidance for intermediate steps and slow convergence.<n>We propose two complementary techniques: Progressive Reward Shaping (PRS) and Value-based Sampling Policy Optimization (VSPO).
  arXiv  Detail & Related papers  (2025-12-08T11:59:25Z)
• 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)
• Intra-Trajectory Consistency for Reward Modeling [67.84522106537274]
  We develop an intra-trajectory consistency regularization to enforce that adjacent processes with higher next-token generation probability maintain more consistent rewards.<n>We show that the reward model trained with the proposed regularization induces better DPO-aligned policies and achieves better best-of-N (BON) inference-time verification results.
  arXiv  Detail & Related papers  (2025-06-10T12:59:14Z)
• Distributional Reward Estimation for Effective Multi-Agent Deep Reinforcement Learning [19.788336796981685]
  We propose a novel Distributional Reward Estimation framework for effective Multi-Agent Reinforcement Learning (DRE-MARL) Our main idea is to design the multi-action-branch reward estimation and policy-weighted reward aggregation for stabilized training. The superiority of the DRE-MARL is demonstrated using benchmark multi-agent scenarios, compared with the SOTA baselines in terms of both effectiveness and robustness.
  arXiv  Detail & Related papers  (2022-10-14T08:31:45Z)

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.