- 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
-
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.
-
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
-
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.
-
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.
-
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
-
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?
-
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?
-
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
Explanation on the general graph-based delegation framework
: We thank the reviewer for this careful observation regarding the empirical results.
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.
: 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.
Ablations comparing Markov and history-dependent policies, with and without money transfers
: We thank the reviewer for emphasizing the validation of history-dependent policies and the money-transfer mechanism. We answer these questions in separate points.
First, we would like to politely point the reviewer to the two-step sequential game presented in Appendix and the corresponding algorithm for finding history-dependent Nash equilibrium policies in Appendix . 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 (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 to , and the global return is increased from to , 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.
| Method | Blue mushrooms consumed | Global episodic return |
|---|---|---|
| No money transfer | 5.7 | 579 |
| With money transfer | 16.5 | 1,673 |
Evaluation results for the five-agent system.
| Method | Blue mushrooms consumed | Global episodic return |
|---|---|---|
| No money transfer | 119.5 | 47,957 |
| Money transfer with no-loan rule | 331.4 | 132,892 |
| Money transfer with allow-loan rule | 321.1 | 128,834 |
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 . 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. 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.
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: 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 A to another B only if B is willing to listen to the command of A, 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, α=0.05). All solvers in the selected subset answer without further delegation. The resulting choice is {B,C} (Llama 3B and Llama 1B) at all three difficulty levels.
Under the same 32-question episode and retry protocol, the new cost-aware baseline router achieves 23.90±0.08 return and 0.884±0.001 accuracy, at a synthetic cost of 0.007±0.000 per episode. The learned graph-based delegation coordinator reaches 25.20±0.42 return and 0.961±0.005 accuracy, at 0.043±0.002 per episode. The graph-based delegation coordinator's return and accuracy are higher in all 20 paired seeds (two-sided Wilcoxon signed-rank test, p=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.