acceptodds
Under review as a conference paper at ICLR 2027

History Matters: Strengthen Collaboration Through Delegation for Multi-agent Reinforcement Learning Systems

Abstract

AI agents are expected to play an increasingly important role in future decision-making systems. In this paper, we consider collaborative heterogeneous multi-agent systems (MAS), where their members have different capabilities and operating costs. We study how agents can delegate tasks to one another so that certain research tasks can be completed effectively under resource-constrained scenarios. We first develop a multi-agent reinforcement learning-based (MARL) delegation training that enables agents to make sequential delegation decisions while minimizing the total execution cost. We then extend this approach to MARL with prescribed delegation topologies. Furthermore, we introduce two new frameworks for collaboration and delegation in multi-agent systems. The first framework proposes that an agent's policy depends not only on the current state of the underlying Markov decision process but also on the interaction history, including previous joint actions. This history-dependent formulation can improve coordination even in fully observable environments, where conventional MARL methods typically restrict policies to depend only on the current state. The second framework proposes a novel, potentially multi-dimensional monetary mechanism to facilitate the collaboration and delegation for MAS.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, multi-agent system, game theory

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_2pASOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies cost-efficient task delegation in heterogeneous multi-agent reinforcement learning systems. The authors propose three main components: (1) a MARL-based delegation framework with hierarchical and graph-based constraints, (2) history-dependent policies to facilitate reciprocal cooperation, and (3) a virtual money-transfer mechanism to incentivize collaboration, alongside theoretical equilibrium analysis.

Experiments on GSM8K show that a DQN-based coordinator reduces synthetic execution costs while maintaining competitive accuracy, although graph-based delegation underperforms hierarchical delegation. Additional toy-game experiments demonstrate improved cooperation through money transfers. Overall, the validation is largely limited to controlled settings and simplified multi-agent scenarios.

Critical strengths
  1. The paper incorporates past joint actions into agent policies, enabling reciprocal cooperation even in fully observable environments. This provides a useful perspective on coordination beyond conventional Markov policies.

  2. The virtual money-transfer mechanism separates cooperation incentives from environmental rewards through budget-constrained payments. This formulation offers an alternative way to model inter-agent cooperation without directly modifying the reward function.

Critical weaknesses
  1. The GSM8K experiments train only a centralized DQN coordinator with frozen agent policies, rather than learning decentralized delegation strategies. Without comparisons to established routing methods such as RouteLLM, the claimed MARL contribution remains unconvincing.

  2. Table 2 shows that graph-based delegation underperforms hierarchical delegation in both accuracy (96.1% vs. 98.6%) and cost ($0.043 vs. $0.024), questioning the value of the proposed generalization.

  3. The history-dependent policies and money-transfer mechanism are not jointly validated in realistic delegation tasks. Moreover, the toy-game experiments enforce cooperation through predefined payment contracts, making it difficult to attribute the improvements to learned cooperative behavior.

Questions for authors
  1. Since only a centralized DQN coordinator is trained, how does the proposed method differ fundamentally from conventional model routing? Can the authors demonstrate improvements over RouteLLM or simpler cost-aware routing baselines under identical experimental settings?

  2. In Table 2, graph-based delegation achieves both lower accuracy (96.1% vs. 98.6%) and higher costs ($0.043 vs. $0.024) than hierarchical delegation. What empirical evidence justifies the more general delegation framework?

  3. Can the authors provide ablations comparing Markov and history-dependent policies, with and without money transfers, on the same delegation task? Given that the toy-game contracts enforce cooperation upon payment, how can the observed improvements be attributed to learned coordination rather than predefined rules?

5 comments
AuthorsOpenReview ↗

Cost-aware baseline

We greatly appreciate the reviewer's question and suggestions. We have made corresponding changes. In particular, we have added new examples and extensive experiments demonstrating the advantages of history-dependent policies.

W1 and Q1\textbf{W1 and Q1}: We greatly appreciate the reviewer's question and suggestions helping clarify our contributions. However, our proposed framework and numerical evaluations are not limited to centralized routing, and the framework also works without a central router. In the numerical results section, our paper also evaluates decentralized MARL using independent Q-learning (IQL) (Section 3.3), where each agent maintains its own Q-function, selects its own actions independently, and learns only from its individual environmental reward. In this setting, there is no centralized coordinator selecting the joint action. We use this decentralized setting to study whether history-dependent monetary transfers can enable independently learning agents to reach cooperative outcomes that standard IQL does not discover.

Therefore, we view the GSM8K and IQL experiments as addressing complementary aspects of the theoretical framework. The GSM8K experiments evaluate cost-aware delegation among heterogeneous pretrained LLM agents, while the IQL experiments demonstrate decentralized agent-level learning and coordination. The theoretical formulation, however, allows delegation decisions to be represented as agent actions and supports management constraints, peer-to-peer delegation, history-dependent behavior, and transferable-money mechanisms.

Our delegation problem formulation is also different from conventional model routing. In our setting, we have management constraints and graph-based constraints, where an agent can delegate AA to another BB only if BB is willing to listen to the command of AA, namely satisfying the ''affiliation'' or ''command'' constraints (due to ownership of agents, for example), which are not present in conventional model routing.

Comparison with cost-aware central routing baseline

We have added comparisons with a cost-aware routing baseline to the GSM8K experiment under identical solver outputs, costs, data splits, and evaluation settings. For each question-difficulty level, we compare all seven nonempty solver kickoff subsets on the training questions and select the one with the highest mean immediate reward. The comparison uses the same cached solver answers, correctness labels, synthetic costs, and kickoff fees as the learned graph coordinator (λ=100\lambda=100, α=0.05\alpha=0.05). All solvers in the selected subset answer without further delegation. The resulting choice is {B,C}\{B,C\} (Llama 3B and Llama 1B) at all three difficulty levels.

Under the same 3232-question episode and retry protocol, the new cost-aware baseline router achieves 23.90±0.0823.90\pm0.08 return and 0.884±0.0010.884\pm0.001 accuracy, at a synthetic cost of 0.007±0.0000.007\pm 0.000 per episode. The learned graph-based delegation coordinator reaches 25.20±0.4225.20\pm0.42 return and 0.961±0.0050.961\pm0.005 accuracy, at 0.043±0.0020.043\pm0.002 per episode. The graph-based delegation coordinator's return and accuracy are higher in all 2020 paired seeds (two-sided Wilcoxon signed-rank test, p=2−19p=2^{-19} for each comparison), but it also incurs a higher cost. We have added the baseline and its evaluation protocol to the revised paper's ''Delegation Constraints on GSM8K'' subsection and GSM8K

Our results determine that, even under the graph-based delegation constraints (due to mandatory ``command'' or ''affiliation'' relationships between agents), the centralized delegation implementation provides an accuracy advantage over the cost-aware baseline, while the decentralized IQL experiments demonstrate the multi-agent learning aspects of the proposed framework.

AuthorsOpenReview ↗

Explanation on the general graph-based delegation framework

W2 and Q2\textbf{W2 and Q2}: We thank the reviewer for this careful observation regarding the empirical results.

Regarding the Experiment\textbf{Regarding the Experiment} We acknowledge that the hierarchical delegation achieves higher accuracy with lower execution cost than the graph-based delegation in the GSM8K experiment. However, we emphasize that the two experiments differ in the action space and execution rules. The hierarchical delegation restricts the coordinator to only three execution choices, allowing exactly one solver to execute per attempt. In contrast, the graph-based delegation allows multiple solvers to execute simultaneously. Thus, graph-based delegation may cause additional execution costs when multiple solvers are activated. As shown by Figure 3(a) and Figure 3(b), the graph-based delegation policy also invokes the less-capable solver C more frequently, which may also contribute to the lower accuracy.

Regarding the necessity of graph-based delegation\textbf{Regarding the necessity of graph-based delegation}: We would like to emphasize the necessity of the proposed graph-based constrained delegation formulation, because the simple hierarchical relation between agents does not always exist. For example, A can delegate to C, B can also delegate to C, but A cannot delegate B, due to agent ownership or command chain relationships. In realistic settings, there are usually constraints on the delegation relations, including whether an agent can ``command'' another agent to accept the delegation. For example, consider that user 1 owns agent A and agent B while user 2 owns agent C. Although both users are collaborating, their ownership of the agents prevents agent A from directly delegating any task to agent C. Using our graph-based constrained formulation, we can model such scenarios and just remove the edge between A and C.

AuthorsOpenReview ↗

Ablations comparing Markov and history-dependent policies, with and without money transfers

W3 and Q3\textbf{W3 and Q3}: We thank the reviewer for emphasizing the validation of history-dependent policies and the money-transfer mechanism. We answer these questions in separate points.

Ablation comparing Markov and history dependent policies/with or without money transfer.\textbf{Ablation comparing Markov and history dependent policies/with or without money transfer.} First, we would like to politely point the reviewer to the two-step sequential game presented in Appendix BB and the corresponding algorithm for finding history-dependent Nash equilibrium policies in Appendix CC. In this example, we numerically enumerate all deterministic Markov Nash equilibria and history-dependent Nash equilibria. The results demonstrate that history-dependent policies can support additional cooperative equilibrium outcomes with higher global returns. (Please see Appendix B.)

We also added an explicit example in our reply to Reviewer 1, demonstrating that history-dependent policies can indeed provide a much improved Nash equilibrium in social welfare and individual rewards, and also guarantee fairness. Please refer to the comment replying to Reviewer E7zd, named \textit{Example of improving social welfare without trading self-interests}.

We have an ablation of no-money-trained and money-trained IQL policies in the original manuscript. (Section 3.3) Nevertheless, we acknowledge that the original manuscript did not include a controlled empirical comparison of history-dependent policies and Markov policies in a more comprehensive environment. To address this limitation, we conduct an additional experiment with Externality Mushrooms\texttt{Externality Mushrooms} (Agapiou,2023), as detailed in Appendix G of the revised manuscript. We claim that policies that do not depend on money balance are the Markov policies, while the policies dependent on the money balance are the history-dependent policies, since money is a summary statistics of the ``good deeds'' an agent has done before.

In particular, monetary balances encode information about agents' previous interactions, allowing them to condition their following decisions on previous behavior. We do this because learning history-dependent policies is in general computationally expensive, as the history space grows rapidly with the number of past states and joint actions. To address this challenge, we instead formulate policies that are dependent on the dynamically updated money balances, which serve as a compact summary of past interactions.

We implement the money-transfer framework on top of Multi-agent Proximal Policy Optimization(MAPPO), and compare it against the baseline without money transfers. The results show a substantial improvement in both the level of cooperation and overall social welfare, as reported in Table 6 and 7 in Appendix G. In the two-agent case, the consumed blue mushroom (degree of collaboration) is increased from 5.75.7 to 16.516.5, and the global return is increased from 579579 to 16731673, which are both tripled. In the five-agent case, both the consumed blue mushroom and the global return are also almost tripled under two different payment rules.

MethodBlue mushrooms consumed BBGlobal episodic return WW
No money transfer5.7579
With money transfer16.51,673

Evaluation results for the five-agent system.

MethodBlue mushrooms consumed BBGlobal episodic return WW
No money transfer119.547,957
Money transfer with no-loan rule331.4132,892
Money transfer with allow-loan rule321.1128,834

Predefined transfer rules.\textbf{Predefined transfer rules.} We claim that the improvement in collaboration is not only due to the prescribed transfer rules but also to the agents' learned decisions. In our framework, money transfers are separate from the environmental rewards, and each agent's objective function remains maximizing their physical rewards ∑t=0Tri,env⁡\sum_{t=0}^Tr_{\operatorname{i,env}}. Note that the money transfer systems do NOT transfer the environmental rewards. The predefined contracts specify the rules when transfers of money are executed, but they do not directly let an agent choose to initiate a transfer or not. So the agents have to learn the collaboration behaviors themselves. For example, in the early stage of the training, their actions are not collaborative, but as the number of time steps increases, their actions become collaborative, supporting our claim. Moreover, our history-dependent mechanism does not need any predefined contracts or rules,\textbf{Moreover, our history-dependent mechanism does not need any predefined contracts or rules,} but they can still improve the collaborations as in our examples, further validating our claim.\textbf{but they can still improve the collaborations as in our examples, further validating our claim.} In some sense, the money-transfer mechanism is a special case of the history-dependent policy, since the money is a summary statistic of how many ''good deeds'' an agent has done in history.

Reviewer_P37xOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a high-quality theoretical analysis and an insightful central idea. However, the connection between mitigating spectral dilution and learning more discriminative and transferable representations remains unclear. The authors also acknowledge that the proposed strategy does not yield reliable downstream performance gains. What practical significance, then, does improving the response to individual spectral modes have? The authors should further explain how this mechanistic improvement translates into better representation quality and provide more comprehensive experimental evidence to validate its practical value.

Critical strengths

1.The paper proposes an interesting monetary mechanism to facilitate cooperation among agents with potentially conflicting individual incentives. By introducing monetary transfers and contract-based incentives, the mechanism provides a way to encourage agents to perform actions that may be individually costly but beneficial to other agents. Although the current experiments do not yet establish the mechanism's general effectiveness in complex multi-agent systems, the idea is compelling and deserves further investigation.

2.The paper is well organized and easy to follow. The authors present the motivation, formal setup, proposed mechanisms, and experimental results in a logical progression. The separation between the delegation experiments, the monetary cooperation environment, and the theoretical discussion helps readers understand the different components of the work. Overall, the presentation makes a relatively complex multi-agent learning problem accessible and helps communicate the intuition behind the proposed approach.

Critical weaknesses
  1. Incomplete Baselines for Evaluating Delegation Benefits. The evaluation in Section 3.1 compares the learned DQN coordinator primarily against an Always-Ultra baseline, without reporting Always-B and Always-C results. This makes it difficult to disentangle the benefits of learned delegation from the individual capabilities and cost profiles of the underlying solvers. In particular, the DQN achieves higher accuracy than Always-Ultra, raising questions about the assumed solver hierarchy and the extent to which the observed improvement arises from complementary model errors, adaptive delegation, or an insufficiently comprehensive baseline. I recommend adding single-solver baselines to better establish the source of the gains.

  2. Limited Evaluation of Cost Structures with Multiple Optimal Assignments. The three-agent, three-job experiment in Appendix F uses a highly structured cost matrix in which each job has a unique minimum-cost agent. This simplifies the assignment problem and may not capture realistic settings in which multiple agents have equal minimum costs for the same task or multiple globally optimal assignments exist. Such cases introduce additional coordination challenges, including competition for the same task, assignment ambiguity, and variability across training runs. I encourage the authors to evaluate the monetary mechanism under tied minimum costs and multiple optimal assignments, reporting social welfare, optimal-assignment convergence rate, run-to-run variance, redundant execution, and payment statistics. This would help clarify whether the proposed mechanism generalizes beyond the current structured setting.

  3. Insufficient Ablation of History-Dependent Policies. A central motivation of the paper is that history-dependent policies can facilitate cooperation by allowing agents to condition their behavior on past interactions. However, the main experiments do not provide a controlled ablation that isolates the contribution of history-dependent policies relative to Markov policies. The theoretical expressiveness of history-dependent policies alone does not establish that they improve empirical cooperation or task performance. I recommend a controlled comparison between Markov policies and history-dependent policies with matched training budgets. Such experiments are necessary to substantiate the paper's claims about the practical role of history in multi-agent cooperation.

Questions for authors

Please refer to "Weaknesses" above.

5 comments
AuthorsOpenReview ↗

Statistics of Always-B and Always-C in the GSM8K experiment

W1\textbf{W1}: We thank the reviewer for the comment on clarification of our GSM8K experiment. We updated the manuscript (Table 1) and report the requested statistics here:

MethodReturnAccuracyCost (USD/episode)Cumulative cost (USD)
DQN+map27.56 ± 0.320.982 ± 0.0020.033 ± 0.00231.1 ± 0.7
DQN no map27.65 ± 0.280.982 ± 0.0020.032 ± 0.00231.1 ± 0.7
always-Ultra23.90 ± 0.300.971 ± 0.0020.063 ± 0.00260.8 ± 0.2
always-B21.51 ± 0.110.847 ± 0.0020.007 ± 0.0006.8 ± 0.0
always-C3.10 ± 0.170.550 ± 0.0030.001 ± 0.0001.2 ± 0.0

Management constraints: Late-training results over the last 100 episodes, reported as mean ± standard deviation across 20 seeds. Cumulative costs are over 1,000 episodes.

These returns are computed considering the hand-off delegation costs and the execution costs denoted in Section 3.1. The accuracy of each model follows the assumed solver hierarchy: A>B>CA>B>C. Therefore, we can confirm that the observed improvement arises from the adaptive delegation layer.

AuthorsOpenReview ↗

Extra experiment with the equal minimum cost structure

W2\textbf{W2}: We really appreciate the reviewer's suggestion to provide experiments under more general coordination challenges. We add to our three-agent-three-job experiment an equal minimum-cost setting. Appendix F2.5 now reports four cost matrices, all with the theoretical maximum return W=15000W=15000. Matrix 1 is the original matrix. Matrix 2 keeps the same cost-11 jobs and sets the other costs to 33. Matrix 3 has tied minimum cost, where Agent 1 and Agent 2 share the minimum cost of 11 on Job 3, and Agent 2 also has a cost of 11 on Job 1. In Matrix 4, each agent reaches the minimum cost by choosing its own lowest-cost job. For each matrix, we train five seeds with no money and individual rewards, five seeds with no money transfer mechanism and the sum of the three rewards as collaborative objective, and five seeds with individual rewards and one prescribed money transfer payment of 22. Table 6 reports the mean WW and its standard deviation across seeds, the number of seeds that use the maximum-reward joint action on at least 99%99\% of steps, the share of such steps, the share of steps on which two agents choose the same job, and the mean money transferred per step.

ConditionMatrixW (mean ± std)Seeds ≥99% optimalOptimal stepsSame-job stepsGross transfer / step
No money, own reward19000 ± 00/5000
No money, own reward29000 ± 00/5000
No money, own reward39000 ± 00/5000
No money, own reward415000 ± 05/5100
No money, shared reward115000 ± 05/5100
No money, shared reward215000 ± 05/5100
No money, shared reward315000 ± 05/5100
No money, shared reward415000 ± 05/5100
Payment of 2, own reward112598 ± 29383/50.6003.60
Payment of 2, own reward212598 ± 29413/50.6003.60
Payment of 2, own reward312596 ± 29413/50.6003.60
Payment of 2, own reward415000 ± 05/5104.00

Base-reward results across the four cost matrices (5 seeds per condition).

AuthorsOpenReview ↗

Ablation of History-Dependent Policies

W3\textbf{W3}: We thank the reviewer for emphasizing the importance of empirically comparing Markov policies with history-dependent policies.

First, we would like to politely point the reviewer to the two-step sequential game presented in Appendix BB and the corresponding algorithm for finding history-dependent Nash equilibrium policies in Appendix CC. In this example, we numerically enumerate all deterministic Markov Nash equilibria and history-dependent Nash equilibria. The results demonstrate that history-dependent policies can support additional cooperative equilibrium outcomes with higher global returns. (Please see Appendix B.)

We also added an explicit example in our reply to Reviewer 1, demonstrating that the history-dependent policies can indeed provide a much improved Nash equilibrium in the social welfare, individual rewards, and also guarantee the fairness, compared with pure Markov policies. Please refer to the comment replying reviewer E7zd, named \textit{Example of improving social-welfare without trading self-interests}.

Nevertheless, we acknowledge that the original manuscript did not include a controlled empirical comparison of history-dependent policies and Markov policies in a more comprehensive environment. To address this limitation, we conduct an additional experiment with \texttt{Externality Mushrooms} (Agapiou,2023), as detailed in Appendix G of the revised manuscript. We implement the money-transfer framework on top of Multi-agent Proximal Policy Optimization(MAPPO), and compare it against the baseline without money transfers. The policies that do not depend on money balance are the Markov policies, while the policies dependent on the money balance are the history-dependent policies. In particular, monetary balances encode information about agents' previous interactions, allowing them to condition their following decisions on previous behavior. We do this because learning history-dependent policies is in general computationally expensive, as the history space grows rapidly with the number of past states and joint actions. To address this challenge, we instead formulate policies that are dependent on the dynamically updated money balances, which serve as a compact summary of past interactions.

The results show a substantial improvement in both the level of cooperation and overall social welfare, as reported in Tables 6 and 7 in Appendix G. In the two-agent case, the consumed blue mushroom (degree of collaboration) is increased from 5.75.7 to 16.516.5, and the global return is increased from 579579 to 16731673, which are both tripled. In the five-agent case, both the consumed blue mushroom and the global return are also almost tripled under two different payment rules.

Evaluation results for the two-agent system.

The number of blue mushrooms consumed (BB) reflects cooperation. Each evaluation statistic is averaged across multiple random seeds.

MethodBlue mushrooms consumed BBGlobal episodic return WW
No money transfer5.7579
With money transfer16.51,673

Evaluation results for the five-agent system.

MethodBlue mushrooms consumed BBGlobal episodic return WW
No money transfer119.547,957
Money transfer with no-loan rule331.4132,892
Money transfer with allow-loan rule321.1128,834
Reviewer_E7zdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates task delegation and collaboration in heterogeneous LLM-based multi-agent systems, where agents have different pretrained capabilities and execution costs. The authors first formulate task delegation as a MARL problem, allowing agents to decide whether to execute tasks, delegate them to other agents, or remain inactive. To further facilitate collaboration among agents with different interests, the paper introduces history-dependent policies that condition agents' decisions on previous states and joint actions rather than solely on the current environmental state. A two-step Nash equilibrium value iteration algorithm is developed, along with theoretical analysis of history-dependent equilibrium policies. Furthermore, the authors propose a transferable-money mechanism that incorporates agents' money balances into their state representations, enabling past interactions and prescribed payment contracts to influence future decisions without directly modifying environmental rewards. Experiments on GSM8K and synthetic multi-agent games demonstrate that learned delegation policies can reduce execution costs while maintaining task performance, and that appropriately designed money-transfer mechanisms can facilitate cooperative behaviors.

Critical strengths
  1. This paper investigates task delegation and collaboration among heterogeneous agents with different capabilities and execution costs. This is an important problem for practical LLM-based multi-agent systems, where balancing task performance and computational costs is increasingly relevant.

  2. The authors explicitly incorporate task execution and delegation decisions into the agents' action spaces. The consideration of hierarchical management constraints and more flexible delegation constraints provides a useful framework for studying task allocation among heterogeneous agents.

  3. The authors develop a two-step Nash equilibrium value iteration algorithm and provide theoretical analysis of the resulting history-dependent equilibrium policies. These results offer a theoretical foundation for understanding how historical interactions can support reciprocal cooperation under certain conditions.

  4. The proposed framework incorporates transferable money into agents' state representations without directly modifying environmental rewards. Experiments on GSM8K and synthetic multi-agent games demonstrate improved cost efficiency and show that appropriately designed payment mechanisms can facilitate cooperative outcomes.

Critical weaknesses
  1. The authors do not sufficiently justify the advantages of explicitly learning delegation actions over alternative approaches, such as appropriate reward design or constrained MARL, which could also balance task performance and execution costs.

  2. Cooperation in general-sum games is fundamentally related to the trade-offs among three objectives: individual self-interest, social welfare, and fairness. This paper does not sufficiently explain why history-dependent policies are necessary to address these challenges. In my view, cooperation in general-sum games is more related to these objectives, while history-dependent policies serve as only policy mechanisms.

  3. Previous studies, such as Willis et al. (2024), have investigated reward-transfer mechanisms for promoting cooperation. Although this paper incorporates money balances into agents' states rather than directly modifying environmental rewards, the advantages of this distinction remain unclear.

  4. The experiments do not compare the proposed money-transfer mechanism with a fully cooperative baseline that optimizes the sum of agents' individual rewards, making it difficult to assess the additional benefits of the proposed mechanism.

  5. The three proposed components are largely evaluated separately, and the money-transfer results are sensitive to prescribed payment rules. More comprehensive experiments are needed to establish the effectiveness and generality of the complete framework.

References:

[1] Willis R, Du Y, Leibo J Z, et al. Resolving social dilemmas with minimal reward transfer[J]. Autonomous Agents and Multi-Agent Systems, 2024, 38(2): 49.

Questions for authors
  1. Can the authors compare the proposed delegation formulation with reward-design or constrained MARL approaches to clarify its advantages?

  2. How do history-dependent policies address the trade-offs among individual self-interest, social welfare, and fairness? Can similar cooperation be achieved with appropriately augmented Markov states?

  3. What are the specific advantages of representing money transfers as state information rather than directly transferring rewards? Could the authors provide comparisons with existing reward-transfer approaches?

  4. Would directly using the sum of agents' individual rewards as a shared reward function achieve comparable or better cooperation? Such a baseline could help clarify the benefits of the money-transfer mechanism.

11 comments
AuthorsOpenReview ↗

Comparison with reward design and constrained MARL

W1 and Q1\textbf{W1 and Q1}: We thank the reviewer for the comment on comparing our delegation formulation with reward design and constrained MARL. We would first like to politely clarify that the delegation constraint is indeed represented as a cost term in our reward, as stated at the end of Section 2.1: ''Therefore, the one-step reward function of each agent ii is formulated as Ri(s,a)=Rˉ(s,aexec)−βCi(ai),R_i(s,\textbf{a})=\bar{R}(s,a_{exec})-\beta C_i(a_{i}), where α\alpha and β\beta are scaling factors, since the environmental reward and the money cost differ in units. " Here, the second term penalizes execution or delegation costs.

The major advantage of the delegation formulation is that it explicitly separates delegation decisions from execution policies. We assume that the delegation process does not have access to the internal policies of the agents, so we cannot retrain them with the delegation as a hard constraint or with an auxiliary reward added to the environmental reward, but we can add the delegation cost term to the reward of the coordinator\textit{coordinator}. This enables cost-aware coordination without another end-to-end training of the backbone agents. This is particularly useful when agents are only accessible through external API calls or when agents are expensive to retrain.

In addition, we would like to highlight that it is hard to design rewards that induce desirable coordination. However, our delegation formulation could easily and explicitly model the pre-existing relationships inside the agent group, which would reduce the difficulty of inducing cooperation. For example, suppose that there are nn agents and all of them can only use their pre-trained policies. There are pre-existing ''affiliation'' or ''command'' relationships between them: Agent AA can delegate a task to Agent B only if BB was ''affiliated'' with AA (in other words, Agent AA ''commands'' Agent BB). So in this scenario, it is natural to let the agents learn the delegation policy to balance task performance and costs. These pre-existing ''affiliation'' or ''command'' relationships are modeled by the graph constraints in our work.

AuthorsOpenReview ↗

Example of improving social-welfare without trading self-interests

W2 and Q2\textbf{W2 and Q2}: We appreciate the reviewer's comment on the history-dependent policy. In the general-sum game context, the history-dependent policies in this paper were invented to encourage a larger set of cooperation relating to the time horizon. For example, history-dependent policies encourage reciprocal altruism, where individual agents take turns helping each other in a costly way with the expectation that they will be helped in the future.

The history-dependent policies considered in this paper are fundamentally different from conventional recurrent RL policies. In conventional RL, recurrent architectures encode historical observations and actions into a latent hidden state that summarizes past information and infers the next action based on it. In contrast, our formulation explicitly conditions policy on the interaction histories with other agents.

We are thankful that the reviewer brings an interesting balance among self-interest, social welfare, and fairness. In fact, our history-dependent policy can even allow agents to increase the social welfare or satisfy fairness constraints without sacrificing self-interest. We provide a general-sum two-step sequential game example:

Example\textit{Example}: Two agents play in a two-step sequential game, with S=s1,s2,A1=A2=Coop⁡,Defect⁡\mathcal S=\\{s_1,s_2\\}, \mathcal{A}_1=\mathcal{A}_2=\\{\operatorname{Coop},\operatorname{Defect}\\}. At t=1t=1, suppose they play a classic prisoner dilemma game with reward function shown in Table 1, whether the environment state x1x_1 at the first time step is x1=s1x_1=s_1 or x1=s2x_1=s_2. At t=2t=2, they play a game with a different reward function (Table 2). If they both cooperate, their return is (5,5)(5,5) if the environment state x2=s1x_2=s_1, and the reward is (4,4)(4,4) if the environmental state x2=s2x_2=s_2. If they take other joint actions, the reward function is the same regardless of state. The transition function is a uniform distribution: P(x2=s1∣x1=s1,a)=0.5,∀aP(x_2=s_1|x_1=s_1,\textbf{a})=0.5,\forall \textbf{a} and P(x2=s1∣x1=s2,a)=0.5,∀aP(x_2=s_1|x_1=s_2,\textbf{a})=0.5,\forall \textbf{a}. Each entry gives the rewards (A, B). Rows correspond to agent A's actions, and columns correspond to agent B's actions.

Reward function at t=1t=1, for both x1=s1x_1=s_1 and x1=s2x_1=s_2:

A ↓ / B →CoopDefect
Coop(2,2)(-1,3)
Defect(3,-1)(0,0)

Reward function at t=2t=2:

A ↓ / B →CoopDefect
Coop(5,5) / (4,4)(-1,0)
Defect(0,-1)(0,0)

In the (Coop, Coop) cell of the second table, the rewards are (5,5) when x2=s1x_2=s_1 and (4,4) when x2=s2x_2=s_2. All other entries are identical in the two states.

With Markov policies, the best return each agent can achieve is VA=VB=0+0.5∗(5+4)=4.5V^A=V^B=0+0.5*(5+4)=4.5 (The social welfare is 99; Every agent satisfies the fairness constraint Vi≥4.5,∀iV_i\geq 4.5,\forall i), when they adopt the Nash equilibrium Markov policy π(x1)=(defect⁡,defect⁡),π(x2)=(coop⁡,coop⁡),∀x1∈{s1,s2},∀x2∈{s1,s2}\pi(x_1)=(\operatorname{defect},\operatorname{defect}), \pi(x_2)=(\operatorname{coop},\operatorname{coop}), \forall x_1\in\{s_1,s_2\}, \forall x_2 \in\{s_1,s_2\}. For either initial state x1=s1x_1=s_1 or x1=s2x_1=s_2, the policies are defined as follows.

However, with history-dependent policies, the best return of each agent is VA=VB=2+0.5∗(5+4)=6.5V^A=V^B=2+0.5*(5+4)=6.5 and V0B=2+0.5∗(5+4)=6.5V_0^B=2+0.5*(5+4)=6.5(The social welfare is 1313; Every agent satisfies the fairness constraint Vi≥6.5,∀iV_i\geq 6.5,\forall i), when they adopt the Nash equilibrium history-dependent policy:

At t=1t=1, both agents cooperate:

\qquad h_1=x_1.$$ **At $t=2$, each agent cooperates if the other agent cooperated at $t=1$, and defects otherwise:** $$\pi^A(h_2)= \begin{cases} \operatorname{coop}, & \text{if } a_1^B=\operatorname{coop}, \\\\ \operatorname{defect}, & \text{if } a_1^B=\operatorname{defect}. \end{cases}$$ $$\pi^B(h_2)= \begin{cases} \operatorname{coop}, & \text{if } a_1^A=\operatorname{coop}, \\\\ \operatorname{defect}, & \text{if } a_1^A=\operatorname{defect}. \end{cases}$$ Yes, we agree with the reviewer that with augmented Markov states, such across-time-step cooperation can be achieved. In the ideal case, the augmented Markov state $\hat{s}_t$ should carry the interaction history (represented by past joint actions and states) until time step $t-1$: $\hat{s}_t=(s_1,\textbf{a}_1,\dots, \textbf{a}_t-1, s_t)$. However, we noticed that the augmented state space explodes quickly by doing so. Our money transferring framework provides a practical way of accounting for the history of agents' actions.
AuthorsOpenReview ↗

Distinguish between money and reward

W3 and Q3\textbf{W3 and Q3}: We highly appreciate the reviewer's question about clarifying the distinctions between reward transferring, money transferring, and history-dependent policies. In the following, we give their advantages and connections.

Whether to require the rewards to be transferrable\textbf{Whether to require the rewards to be transferrable} Thanks for the pointer to the reference. We have cited (Willis et al., 2024), and clarified this distinction in the \textit{related work} section and the manuscript. Compared with (Willis et al., 2024), which directly redistributes environmental payoffs to align individual incentives, our framework introduces money transfer as a record of previous interactions without modifying environmental rewards. Notice that the payments between agents are not included in the environmental return, and agents aim to maximize only their environmental returns. In this paper, both history-dependent policies and money-transfer mechanisms can work even when the rewards themselves are not transferable and where reward transfer schemes do not work. For example, money works as a ``virtual'' medium for trading, even when the real rewards are not transferable.

For example, for agents as autonomous self-driving cars, during traffic congestion, the rewards received by a car AA are the shorter time staying in the traffic jam, when another car BB does a favor for this car AA by yielding the road rights to car AA. However, the shorter time rewards received by car AA cannot be directly transferred to car BB: after all, the shorter time is experienced by car AA and cannot be directly transferred to be enjoyed by car BB.

However, both history-dependent policy and the money transfer-based policy do not require the rewards to be directly transferable. For example, if car BB let car AA go through a traffic jam first in the past, based on this history, car AA can let car BB pass first in the next traffic jam. In the money transfer mechanism, car AA can give BB 10 dollars for BB letting car AA pass first; now that car BB has 10 dollars, in the next traffic jam, car BB can pay car AA or even another car so that car BB has the road rights to spend less waiting time in the traffic jam.

As another example, suppose that we have two agents. The first agent only eats bread, and his/her rewards are the enjoyment of eating bread. The 2nd agent only eats vegetables such as lettuces, and his/her rewards are the enjoyments of eating vegetables. So the rewards of these two agents are not directly transferable: the 2nd agent cannot give the vegetables to the 1st agent for the 1st agent to enjoy, since the 1st agent does not enjoy eating vegetables at all; similarly, the 1st agent cannot directly give bread to the 2nd agent to enjoy, since the 2nd agent does not eat bread at all.
However, for the history-dependent policy or money transfer policy, this will not be a problem. This is because the 2nd agent can help the 1st agent in obtaining bread if the 1st agent historically helped the 2nd agent acquire vegetables: this does not require directly transferring their rewards.

In human society, money transfer is also more widely used and useful than reward transfer in the following scenario. Consider three agents AA, BB, and CC. For agent AA, the reward is the enjoyment of music. For agent BB, the reward is the acquisition of clothes. For Agent C, the reward is the enjoyment of food. These rewards of different enjoyments are not directly transferable since other agents are currently not lacking the same life needs or materials. However, A can produce clothes for B, B can produce food for C, and C can produce music for A in history-dependent policies and money transfer policies. For a similar setting, in our numerical experiments in Appendix FF of the paper, we also find that the money-transfer mechanism can find good policies which increase the rewards of each agent, even though the agents' rewards are not transferable.

Whether to require changing the underlying physical game\textbf{Whether to require changing the underlying physical game} Even when the reward is transferable, strictly speaking, the mechanism of reward transferring and sharing actually redesigns and changes the underlying physical MDP games. This is because reward transfer needs to add the new actions of transferring rewards, and these actions directly change the environmental rewards of involved agents. These additions effectively change the definition of the original MDP game. For example, if agent B gets an environmental reward of 100 for taking an action, and agent AA decides to transfer another reward of 100 to agent BB, then the effective reward of agent BB taking that action is actually changed from 100100 to 100+100=200100+100=200.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of rebuttal to all reviewers

We believe this paper offers a novel approach for MARL policy and collaboration where the policy takes into account the action history of agents for better collaboration. This new approach can improve the social welfare, self-interest, and maintain fairness at the same time.

We have substantially revised our paper in response to the reviewers' comments, substantially strengthened the experimental verifications. In particular, we have explicitly mentioned the connections between our contributions, as detailed in the introduction and related work section. The main technical revisions are summarized below:

Experimental Contributions

  1. Empirically validated effects of history-dependent policies and money-transfer frameworks\textbf{Empirically validated effects of history-dependent policies and money-transfer frameworks}: We conducted comprehensive experiments in the large-scale Externality Mushroom\texttt{Externality Mushroom} environment to evaluate both proposed frameworks. We added controlled ablation studies comparing Markov and history-dependent policies, and also policies trained with and without money transfers. The results show that both frameworks greatly improve global returns and cooperation among agents.

  2. Delegation layer in the GSM8K experiments\textbf{Delegation layer in the GSM8K experiments}: We clarified the performance of the always-B and always-C baselines, confirming that the observed improvements arise from the proposed delegation layer. We also introduced an additional cost-aware routing baseline, showing that our graph-constrained delegation coordinator achieves higher returns and accuracy.

  3. Cost functions and fully cooperative baselines\textbf{Cost functions and fully cooperative baselines}: We examined alternative cost functions and introduced a fully cooperative baseline in the three-job assignment experiment. Results show that money transfers enable self-interested agents to achieve global returns closer to the fully cooperative baseline. We further show that the optimal assignment is insensitive to the choice of cost function.

Theoretical Clarifications

  1. Benefits of history-dependent policies\textbf{Benefits of history-dependent policies}: We clarified how consideration of history-dependent policies can expand the set of achievable Nash equilibrium outcomes, and increasing both social welfare and fairness without need of self-interest agents to sacrifice their individual utilities. We also provided an additional illustrative example to support this theoretical conclusion.

  2. Comparison with reward-design and constrained MARL\textbf{Comparison with reward-design and constrained MARL}: We expanded our discussion of related approaches and clarified the key advantage of our delegation framework: It can leverage pretrained agents through a learned delegation layer without requiring end-to-end retraining of their underlying policies.

Clarifying connections between three components or contributions

  1. We would like to mention the connections between these three components. The first contribution introduces delegation actions and is mostly concerned with using delegations for optimizing shared objectives of agents. The second contribution introduces a new history-dependent policy for general MARL systems, but this new approach is particularly useful for promoting collaboration of agents with individual rewards through delegation (it works as a general novel approach for MARL and can be useful even without delegation). The third contribution (money transfer) is a practical version of the history-dependent policy, and is also very useful for promoting collaboration of agents with individual rewards. Overall, these methods enable cooperation among agents whose individual objectives must remain unchanged: delegation determines task allocation, history supports reciprocity, and money provides a compact record of past interactions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.