PaperlayerView exact revision on arXiv

Source-linked AI summary

Who Deserves the Reward? SHARP: Shapley Credit-based Optimization for Multi-Agent System

Yanming Li, Xuelin Zhang, WenJie Lu, Ziye Tang, Maodong Wu, Haotian Luo, Tongtong Wu, Zijie Peng, Hongze Mi, Yibo Feng, Naiqiang Tan, Chao Huang, Lian Peng, Li Shen

arXiv:2602.08335v2cs.AI

TL;DR

Multi-agent systems can decompose complex tool-using tasks, but sparse team-level rewards make it difficult to assign credit to individual agents. SHARP combines task-level, Shapley-based agent-level, and tool-process rewards with agent-specific advantage normalization; across benchmarks, it reports average match gains of 23.66% and 14.05% over single-agent and multi-agent approaches, respectively.

  • Problem

    Sparse or globally broadcast rewards make it difficult to distinguish individual agents’ contributions to multi-agent decision trajectories.

    Source: §1 · p. 1, §4.2 · p. 3

  • Method

    SHARP combines global task-alignment, Shapley-based marginal-credit, and tool-process rewards, while normalizing agent-specific advantages across trajectory groups.

    Source: §1 · p. 2

  • Results

    23.66% and 14.05% average match gains over single-agent and multi-agent approaches, respectively, are reported across diverse benchmarks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    SHARP provides a framework for fine-grained credit attribution and stable joint optimization in multi-agent systems.

    Source: §6 · p. 9

    Useful subagents remain a minority of total calls in the tested systems, indicating that many calls may be redundant or neutral.

    Source: §5.5 · p. 8

Abstract

from arXiv · show

Integrating Large Language Models (LLMs) with external tools via multi-agent systems offers a promising new paradigm for decomposing and solving complex problems. However, training these systems remains notoriously difficult due to the credit assignment challenge, as it is often unclear which specific functional agent is responsible for the success or failure of decision trajectories. Existing methods typically rely on sparse or globally broadcast rewards, failing to capture individual contributions and leading to inefficient reinforcement learning. To address these limitations, we introduce the Shapley-based Hierarchical Attribution for Reinforcement Policy (SHARP), a novel framework for optimizing multi-agent reinforcement learning via precise credit attribution. SHARP effectively stabilizes training by normalizing agent-specific advantages across trajectory groups, primarily through a decomposed reward mechanism comprising a global broadcast-accuracy reward, a Shapley-based marginal-credit reward for each agent, and a tool-process reward to improve execution efficiency. Extensive experiments across various real-world benchmarks demonstrate that SHARP significantly outperforms recent state-of-the-art baselines, achieving average match improvements of 23.66% and 14.05% over single-agent and multi-agent approaches, respectively.

1. Introduction

SHARP addresses the difficulty of assigning credit among planner and worker agents when team-level rewards obscure individual contributions. It combines decomposed rewards with agent-specific advantage normalization, and reports gains over single-agent and multi-agent baselines.

1. Introduction

  • Sparse, globally broadcast rewards treat agents with different roles as a monolithic entity, obscuring individual contributions and making policy updates inefficient.The paper frames this as a credit-assignment challenge in collaborative planner-worker systems.Source: §1 · pp. 1–2
  • SHARP decomposes rewards into global task alignment, Shapley-based marginal credit for individual impact, and tool-process execution validity.Its counterfactual masking mechanism estimates an agent’s impact by measuring performance changes after removing relevant agents from a trajectory.Source: §1 · p. 2
  • SHARP normalizes agent-specific advantages across trajectory groups to stabilize optimization, and its reward design is presented for varied model sizes and multi-agent structures.The described structures include sequential chains, communication graphs, and hierarchical planner-worker systems.Source: §1 · p. 2
  • 23.66% and 14.05% average match gains over single-agent and multi-agent approaches, respectively, are reported for SHARP with Qwen3-8B.The reported gains are across diverse real-world benchmarks.Source: §1 · p. 2

2. Related Works

Prior work develops multi-agent architectures for complex tool-integrated tasks and value-free reinforcement-learning methods for uncertain environments. The paper identifies precise agent-level credit assignment during training as an unresolved gap.

Multi-Agent Architectures and Operational Strategies

  • Multi-agent architectures include sequential agent chains, graph-based communication structures, and planner-worker or decomposer-solver hierarchies for managing complex tasks.The cited examples are COA [Li et al., 2025a], G-Designer [Zhang et al., 2025b], CARD, AceSearcher [Xu et al., 2025], and MATPO [Mo et al., 2025].Source: §2 · p. 2

Reinforcement Learning and Credit Assignment

  • Existing work emphasizes inference-time interaction protocols and topology, leaving precise credit assignment during multi-agent training largely unresolved.The paper positions counterfactual reasoning via Shapley-induced rewards as a mechanism for isolating individual contributions in optimization.Source: §2 · pp. 2–3
  • Value-free methods such as GRPO [Shao et al., 2024] and OSPO [Zhao & Li, 2025] address critic-estimation errors, while multi-agent extensions generalize group-relative baselines and coordination.The paper says these extensions often remain trajectory-level and struggle to disentangle individual marginal contributions.Source: §2 · pp. 2–3

3. Problem Setup

The setup models tool use as sequential action-and-observation trajectories, then instantiates planner and worker roles through one shared policy conditioned on role-specific prompts.

3.1. Tool-Integrated Interaction Trajectory

  • A tool-integrated trajectory is a sequence of model actions and corresponding tool observations, generated until termination.Actions may be reasoning or tool invocations.Source: §3.1 · p. 3
  • At each step, the policy samples an action from cumulative context and receives a tool response; because tool responses are independent of policy parameters, optimization acts through generated actions.The policy context includes the system prompt, query, and prior actions and observations.Source: §3.1 · p. 3

3.2. Self-Play Multi-Agent Modeling

  • A single shared policy instantiates heterogeneous planner and worker roles through role-specific system prompts, with the planner generating high-level actions and workers executing assigned subtasks.The self-play formulation jointly optimizes planning and execution trajectories under the shared policy.Source: §3.2 · p. 3

4. Methodology

SHARP models tool-integrated problem solving as hierarchical planner–worker execution under a shared policy, then combines task, agent-credit, and tool-process rewards. It approximates Shapley credit and uses group-relative policy optimization to normalize agent rewards across trajectories.

4.1. Tool-Integrated Multi-Agent Execution

  • Planner and workers use role-specific prompts with a shared policy to produce a hierarchical trajectory of planner reasoning and worker execution for subtasks.The joint process is described as a single trajectory that can be optimized end to end.Source: §4 · p. 3, §4.1 · p. 3

4.2. Compositional Reward Design

  • SHARP combines broadcast accuracy, agent-specific marginal credit, and tool-process rewards in a weighted surrogate reward.These components respectively capture terminal success, individual contribution, and execution quality; the tool-process signal evaluates tool-invocation validity.Source: §4.2 · pp. 4–5

4.3. Shapley-based Marginal Credit Assignment

  • Shapley credit quantifies an agent’s marginal contribution across possible coalitions, but estimating every agent’s credit in multi-agent tool-integrated planning is computationally intractable.SHARP approximates individual credits through counterfactual marginal contributions, including worker ablation while preserving the environment and other agents.Source: §4.3 · p. 5
  • The planner’s credit accounts for its structural influence through task decomposition, unlike workers’ direct effects on the environment.The planner’s marginal credit is formalized separately from worker credit.Source: §4.3 · p. 5

4.4. SHARP Optimization via GRPO

  • Improved group-relative policy optimization normalizes agentic rewards using each agent’s mean and standard deviation across sampled trajectories.The paper presents this as a way to support efficient, stable optimization under sparse rewards and multi-agent coordination.Source: §4.4 · p. 5

5. Experimental Evaluation

The evaluation compares SHARP with single-agent and multi-agent baselines, then examines credit components, task generalization, scaling, training stability, and coordination.

5.2. RQ1: Overall Performance

  • SHARP (Qwen) achieved 32.56 average performance, 1.75 points above MATPO, with average match gains of 23.66% over single-agent and 14.05% over multi-agent baselines.Zero-shot RAG scores were 5.65–8.00, while MAS RL baselines without marginal credit modeling reached 28.15–30.81.Source: §5.2 · pp. 6–7

5.3. RQ2: Component Contribution Assessment

  • On MuSiQue, full SHARP reached 50.76 accuracy, versus 47.00 without Shapley credit, 47.60 with planner-only credit, and 48.00 with worker-only credit.Figure 3 compares full SHARP with variants removing planner- or worker-level credit.Source: Figure 3 · p. 7, §5.3 · p. 7

5.4. RQ3: Stability and Scalability Analysis

  • SHARP performed best across DocMath-Eval’s simple-short, simple-long, complex-short, and complex-long document-reasoning settings.Figure 3 reports the four settings and compares SHARP across those subtasks.Source: Figure 3 · p. 7, §5.4 · p. 8
  • On MuSiQue, SHARP accuracy rose from 6.29 at 0.6B to 50.76 at 8B, reaching a 14.41-point advantage over the single-agent baseline at 8B.Figure 4 covers model sizes from 0.6B to 8B and reports a larger advantage at larger scales.Source: Figure 4 · p. 7, §5.4 · p. 8

5.3. RQ2: Component Contribution Assessment

  • Planner credit yielded gains of 0.6–0.65, while worker credit yielded 0.88–1.00, with worker credit identifying high-utility and redundant tool calls.The authors note that tool-calling and execution failures can be more challenging in long-horizon training.Source: §5.3 · p. 7

5.4. RQ3: Stability and Scalability Analysis

  • On GAIA-text, SHARP accuracy improved monotonically from 27.53 to 33.70 over 180 optimization steps, while single-agent GRPO and MATPO fluctuated.Figure 5 shows training-step behavior and shaded 95% confidence intervals.Source: Figure 5 · p. 8, §5.4 · p. 8

5.5. RQ4: Coordination Analysis

  • SHARP raised the planner’s average Shapley score to 0.5084 and useful-subagent share to 12.96%, while reducing harmful calls from 5.48% to 4.40%.Useful subagents nevertheless remained a minority of tested calls, and the authors identify pruning low-utility paths as a future need.Source: Figure 6 · p. 8, §5.5 · p. 8

6. Conlucions

The conclusion presents SHARP as a framework for fine-grained credit assignment and stable joint optimization in multi-agent systems.

  • SHARP combines tripartite rewards to disentangle agents’ individual impacts from aggregate outcomes in parameter-sharing multi-agent hierarchies.Source: §6 · p. 9
  • The paper presents fine-grained credit attribution as supporting stable joint optimization and cross-task generalization in complex multi-agent systems.Source: §6 · p. 9
  • The authors describe SHARP as a foundation for scalable and interpretable coordination in hierarchical multi-agent systems.Source: §6 · p. 9

Impact Statement

The impact statement describes SHARP’s intended scope, while the workflow snippets outline trajectory collection, reward computation, and policy updating.

Impact Statement

  • SHARP integrates Shapley-based credit attribution with hierarchical planner–worker optimization for precise credit assignment in collaborative multi-agent systems.Source: Impact Statement · p. 9

A. Algorithm Workflow

  • It computes broadcast and counterfactual marginal-credit rewards, then uses group-relative advantages to update policy parameters.Source: A. Algorithm Workflow · p. 12
  • The workflow collects tool-integrated-planning trajectories by running workers on subtasks and recording their interactions and participating-worker sets.Source: A. Algorithm Workflow · p. 12

B. Information of Training and Test Dataset

The dataset appendix lists five benchmarks, specifies training and evaluation splits, and describes a planned release of experimental materials.

B. Information of Training and Test Dataset

C. Implementation Details

Implementation combines role-specialized agents with counterfactual marginal-credit estimation and group-wise advantage normalization. Training and tool access are configured with fixed settings and role-scoped execution.

C. Implementation Details

  • Baseline comparisons use Qwen3-8B backbones for fairness, excluding models built on LLaMA-3.1-8B, Qwen2.5-7B, or typology-only strategy.Source: C. Implementation Details · p. 13
  • The Qwen-3-8B and LLaMA-3.1-8B instruction-tuned models use AdamW at 10−5, batch size 256, eight rollouts per input, and 180 gradient steps.Training uses 64×A100 GPUs; reward coefficients are α = 0.9, β = 0.9, and γ = 0.1.Source: C. Implementation Details · p. 13
  • The Planner decomposes objectives into subtasks, while Workers execute them through environment and tool interactions under role-specific prompts.All agents share policy πθ.Source: C. Implementation Details · p. 13
  • For each trajectory, SHARP masks an agent’s contribution to form a counterfactual trajectory and derives marginal credit from the change in accumulated reward.Source: C. Implementation Details · p. 13
  • Group-wise normalization statistics are estimated across each mini-batch, with ϵ = 0.2 and δ = 10−6.Source: C. Implementation Details · p. 13
  • Tool access is role-scoped: planners delegate, execution agents use designated backends, and each agent is limited to one tool call per step.The service interface separates specialized auxiliary agents and their non-overlapping toolsets.Source: C. Implementation Details · p. 13

D. Cost Analysis

The cost analysis varies the fraction of subagent invocations assigned Shapley-based credit. Denser credit increases training expenditure while reducing inference token use and improving task accuracy.

D. Cost Analysis

  • Increasing p assigns Shapley-based credit to a larger fraction of subagent invocations; the remaining invocations receive zero marginal credit without Shapley computation.Source: D. Cost Analysis · p. 13
  • 47.00% to 50.76% task accuracy accompanies inference token consumption falling from ∼9.1k to ∼8.3k and per-batch training latency rising from approximately 684s to 1345s as p increases from 0 to 1.Source: Figure 7 · p. 14, D. Cost Analysis · p. 14
  • Shapley-based marginal credit is presented as a mechanism for reducing redundant actions: higher p trains agents to suppress low-utility invocations and shorten inference trajectories.Source: D. Cost Analysis · p. 14
  • Marginal-credit evaluations for different subagents can be parallelized and remain at trajectory-level counterfactual evaluation, without rerunning the full optimization process.Source: D. Cost Analysis · p. 14
  • The authors characterize the trade-off as allocating more computation to training for more selective, efficient, and accurate execution at deployment.Source: D. Cost Analysis · p. 14

E. Catastrophic Forgetting Analysis

On MMLU, SHARP and MATPO exceed the inference-only Planner–Worker baseline; the following case study presents verbatim agent trajectories.

E. Catastrophic Forgetting Analysis

  • The evaluation compares an inference-only Planner–Worker setup with MATPO and SHARP trained on the search dataset using the Qwen3 backbone.Source: E. Catastrophic Forgetting Analysis · p. 15
  • MMLU accuracy was 94.65% for SHARP, 94.00% for MATPO, and 93.04% for the inference-only Planner–Worker baseline.The authors report that specialized training did not regress general-domain performance.Source: E. Catastrophic Forgetting Analysis · p. 15
  • The authors hypothesize that targeted Shapley-based credit localizes subagent contributions and reduces unnecessary changes to latent representations, helping safeguard general-purpose knowledge.Source: E. Catastrophic Forgetting Analysis · p. 15

F. Case Study: Raw Agent Trajectories

F.1. Case Study 1: Useful Sub-agent

This section examines how sub-agents can help through targeted evidence retrieval or harm answers with distracting caveats, and details prompts for iterative, context-rich tool use and delayed finalization. It also reports that the LLM was used only for manuscript editing.

F.1. Case Study 1: Useful Sub-agent

  • With a useful sub-agent, the system gives the correct 92% answer, while without one the main agent’s 85% estimate is incorrect.The sub-agent retrieves and cross-checks historical evidence, resolving the main agent’s numerical uncertainty.Source: §F.1 · p. 18

F.2. Case Study 2: Harmful Sub-agent

  • With a harmful sub-agent, the answer shifts from the benchmark-correct Democratic–Republican label to “No formal party,” turning a correct outcome into an incorrect one.The sub-agent’s caveat about the lack of formal parties in 1781 adds complexity that conflicts with the dataset’s labeling scheme.Source: §F.2 · p. 20

G. System Prompts: Planner Agent, and Worker Agents

  • The planner prompt calls for iterative sub-goals, one tool call per step, context-rich queries, and no final answer until the task is complete.It also instructs the agent to summarize known information, identify gaps, choose a relevant tool, and avoid vague queries.Source: G. System Prompts: Planner Agent, and… · p. 22
  • The worker agent is instructed to solve tasks step by step, plan and pursue sub-goals sequentially, and make one tool call per step unless the task is already solved.Its objective is to provide complete, accurate, well-reasoned answers using tools; it should answer directly when tool use is unnecessary.Source: G. System Prompts: Planner Agent, and… · pp. 22, 24
  • The worker uses search to find candidate sources and scrape to retrieve page content, with tool calls following specified XML-style tags and input schemas.Tool calls must appear at the end of the response and follow the prescribed format for parsing.Source: G. System Prompts: Planner Agent, and… · pp. 23–24
  • The browsing agent is instructed to return factual, verifiable information, flag uncertainty or conflicting findings, avoid guessing, and request clarification when needed.It should assess source credibility, provide source URLs when available, and prefer original-source excerpts over interpretation.Source: G. System Prompts: Planner Agent, and… · p. 25

H. Disclosure of LLM Usage

  • The LLM was used only during editing for grammar, spelling, and word choice, not for ideation, research methodology, experimental design, or data analysis.The authors accept responsibility for the manuscript, including LLM-generated or refined text, to support ethical compliance and prevent plagiarism.Source: H. Disclosure of LLM Usage · p. 25

Related papers

Loading 2602.08335v2…