TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents

• URL: http://arxiv.org/abs/2607.13988v1
• Date: Wed, 15 Jul 2026 16:16:42 GMT
• Title: TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
• Abstract summary: TRACE (Turn-level Reward Assignment via Credit Estimation) is a dense credit-assignment method for agentic reinforcement learning.<n>It represents rollouts as state transitions at tool-call boundaries, obtains gold-answer log-probabilities from a frozen reference model, transforms them into log-ratio state values, and derives per-action rewards as Temporal-Difference changes in those values.<n>It substantially improves base-model tool-use ability using pure RL, without a cold-start supervised fine-tuning stage, an agentic mid-training stage, or training on live-web data.
• Score: 51.523913302114266
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-turn agents solve complex tasks through extended sequences of tool interactions before producing a final answer, making credit assignment a fundamental challenge during post-training. Outcome rewards provide reliable supervision for short-horizon reasoning, but become sparse and high-variance as trajectories grow to tens or hundreds of tool calls. They can also be misleading: a failed rollout may contain many useful actions that move the agent closer to the goal, yet outcome-only training assigns them the same negative advantage as the eventual mistake. We propose TRACE (Turn-level Reward Assignment via Credit Estimation), a dense credit-assignment method for agentic reinforcement learning. TRACE represents rollouts as state transitions at tool-call boundaries, obtains gold-answer log-probabilities from a frozen reference model, transforms them into log-ratio state values, and derives per-action rewards as Temporal-Difference changes in those values. This requires no additional critic or process-label training, and its one-step log-ratio TD component telescopes across redundant tool calls. On long-horizon complex search, TRACE substantially improves base-model tool-use ability using pure RL, without a cold-start supervised fine-tuning stage, an agentic mid-training stage, or training on live-web data. On the closed-web BrowseComp-Plus benchmark, it raises Qwen3-4B from $7.2$ to $35.6$ and Qwen3-30B-A3B from $8.4$ to $42.6$. The learned search behavior also transfers to open-web benchmarks, and the learning curves show earlier improvement and faster convergence during RL training.

Related papers

• VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning [6.237984544487965]
  VICT (VerifierInstrumented Credit Tracing) is a trainingtime interface that traces atoms back to actions through dependency-valid proof edges.<n>It improves substantially over outcome-only training and achieves strong performance alongside recent fine-grained credit methods.
  arXiv  Detail & Related papers  (2026-08-28T09:43:54Z)
• Teach the Magnitude, Not the Direction: Verifier-Bounded Credit Assignment for Multi-Turn Multi-step LLM Agents [15.12019413574721]
  Reinforcement learning with verifiable rewards conflates heterogeneous per-turn outcomes into a single reward signal.<n>On-policy distillation provides dense per-token supervision but is either teacher-bounded or prone to gradient concentration collapse.<n>We introduce $textbfCrEST$, a hierarchical credit assignment framework that retains RL's verifier-bounded ceiling while incorporating dense token-level signals from a privileged self-teacher.
  arXiv  Detail & Related papers  (2026-08-13T12:44:37Z)
• AgentOPSD: Recursive Self-Distillation for Agentic Reinforcement Learning [58.76655851910778]
  AgentOPSD is a critic-free, recursive method for turn-level credit assignment in agentic reinforcement learning.<n>We evaluate AgentOPSD on ALFWorld, WebShop, and Search-QA using Qwen2.5 models at two scales (3B and 7B)
  arXiv  Detail & Related papers  (2026-08-06T13:00:59Z)
• SeekJudge: A Practical Reward Framework for Reinforcement Learning in Computer-Use Agents [43.62427340281939]
  Rule-based evaluation struggles to align with human intention and goes stale when an app updates or its online content drifts.<n>We propose the textbfSeekJudge framework, in which four role-specialized agents, a Condense, a Ground, a Seek and an Analyze agent, reach a verdict.<n>SeekJudge is the first practical model-based reward to match or surpass native rule-based supervision in online RL.
  arXiv  Detail & Related papers  (2026-07-25T16:00:45Z)
• REVES: REvision and VErification--Augmented Training for Test-Time Scaling [53.197756110943395]
  We propose a two-stage iterative framework that alternates between online data/prompt augmentation and policy optimization.<n>We observe gains of +6.5 points over the RL baseline and +4.0 points over standard multi-turn training.
  arXiv  Detail & Related papers  (2026-06-17T10:37:23Z)
• PACT: Privileged Trace Co-Training for Multi-Turn Tool-Use Agents [57.69188221227875]
  We propose a Privileged trAce Co-Training framework for multi-turn tool-use agents.<n>The key idea is to use expert traces only as training-time optimization signals rather than rollout-time hints.<n>We show that PACT consistently improves over strong SFT- and RL-based baselines.
  arXiv  Detail & Related papers  (2026-06-15T04:46:23Z)
• Self-Induced Outcome Potential: Turn-Level Credit Assignment for Agents without Verifiers [26.97849381770806]
  Self-Induced Outcome Potential treats semantic clusters of final answers as latent future outcome states for potential-based turn-level credit assignment.<n>We formalize the framework, characterize its supervised gold-answer limit, and show that SIOP improves average performance over verifier-free outcome-level baselines.
  arXiv  Detail & Related papers  (2026-05-06T14:38:48Z)
• R$^3$L: Reflect-then-Retry Reinforcement Learning with Language-Guided Exploration, Pivotal Credit, and Positive Amplification [44.99719889905381]
  Reinforcement learning drives recent advances in reasoning and agentic capabilities, yet current approaches struggle with both exploration and exploitation.<n>We propose R$3$L, Reflect-then-Retry Reinforcement Learning with Language-Guided Exploration, Pivotal Credit, and Positive Amplification.<n>Experiments on agentic and reasoning tasks demonstrate 5% to 52% relative improvements over baselines while maintaining training stability.
  arXiv  Detail & Related papers  (2026-01-07T09:04:52Z)
• Agentic Reinforcement Learning with Implicit Step Rewards [92.26560379363492]
  Large language models (LLMs) are increasingly developed as autonomous agents using reinforcement learning (agentic RL)<n>We introduce implicit step rewards for agentic RL (iStar), a general credit-assignment strategy that integrates seamlessly with standard RL algorithms.<n>We evaluate our method on three challenging agent benchmarks, including WebShop and VisualSokoban, as well as open-ended social interactions with unverifiable rewards in SOTOPIA.
  arXiv  Detail & Related papers  (2025-09-23T16:15:42Z)
• Reinforcement Learning for Machine Learning Engineering Agents [52.03168614623642]
  We show that agents backed by weaker models that improve via reinforcement learning can outperform agents backed by much larger, but static models.<n>We propose duration- aware gradient updates in a distributed asynchronous RL framework to amplify high-cost but high-reward actions.<n>We also propose environment instrumentation to offer partial credit, distinguishing almost-correct programs from those that fail early.
  arXiv  Detail & Related papers  (2025-09-01T18:04:10Z)
• RRO: LLM Agent Optimization Through Rising Reward Trajectories [52.579992804584464]
  Large language models (LLMs) have exhibited extraordinary performance in a variety of tasks.<n>In practice, agents sensitive to the outcome of certain key steps which makes them likely to fail the task.<n>We propose Reward Rising Optimization (RRO) to mitigate this issue.
  arXiv  Detail & Related papers  (2025-05-27T05:27:54Z)

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.