When Is Diversity Rewarded in Cooperative Multi-Agent Learning?
Authors: Michael Amir
Matteo Bettini
Amanda Prorok
Venue: ICLR 2026 Poster (2026)
Keywords: multi-agent systems
heterogeneity
multi-agent reinforcement learning
co-design
Primary area: learning theory

Abstract: The success of teams in robotics, nature, and society often depends on the division of labor among diverse specialists; however, a principled explanation for when such diversity surpasses a homogeneous team is still missing. Focusing on multi-agent task allocation problems, we study this question from the perspective of reward design: what kinds of objectives are best suited for heterogeneous teams? We first consider an instantaneous, non-spatial setting where the global reward is built by two generalized aggregation operators: an inner operator that maps the N agents’ effort allocations on individual tasks to a task score, and an outer operator that merges the M task scores into the global team reward. We prove that the curvature of these operators determines whether heterogeneity can increase reward, and that for broad reward families this collapses to a simple convexity test. Next, we ask what incentivizes heterogeneity to emerge when embodied, time-extended agents must learn an effort allocation policy. To study heterogeneity in such settings, we use multi-agent reinforcement learning (MARL) as our computational paradigm, and introduce Heterogeneity Gain Parameter Search (HetGPS), a gradient-based algorithm that optimizes the parameter space of underspecified MARL environments to find scenarios where heterogeneity is advantageous.  Across different environments, we show that HetGPS rediscovers the reward regimes predicted by our theory to maximize the advantage of heterogeneity, both validating HetGPS and connecting our theoretical insights to reward design in MARL. Together, these results help us understand when behavioral diversity delivers a measurable benefit.

Published as a conference paper at ICLR 2026
WHEN IS DIVERSITY REWARDED IN COOPERATIVE MULTI-AGENT LEARNING?
Michael Amir Matteo Bettini"
Amanda Prorok
Department of Computer Science and Technology University of Cambridge
(ma2151, mb2389, asp45) @cl. cam ac
M
M
Rhet Global rewards
R hom"
Heterogeneity gain
AR Rht Rhom
when + Schur-convex
when ① Schur-concave
M Lasks
agents
effort of agent Lask]
Heterogeneous
Homogeneous
Figure 1: We study and categorize what reward structures lead to the need for behavioral heterogeneity in multi-agent multi-task environments.
ABSTRACT
The success of teams in robotics, nature, and society often depends the division of labor among diverse specialists; however, a principled explanation for when such diversity surpasses homogeneous team is still missing. Focusing multi-agent task allocation problems, we study this question from the perspective of reward design: what kinds of objectives are best suited for heterogeneous teams? We first consider an instantaneous, non-spatial setting where the global reward is built by two generalized aggregation operators: an inner operator that maps the N agents' effort allocations on individual tasks to task score, and an outer operator that merges the M task scores into the global team reward. We prove that the curvature of these operators determines whether heterogeneity can increase reward, and that for broad reward families this collapses to a simple convexity test. Next, we ask what incentivizes heterogeneity to emerge when embodied, time-extended agents must learn an effort allocation policy. To study heterogeneity in such settings, we multi-agent reinforeement learning (MARL) our computational paradigm, and introduce Heterogeneity Gain Parameter Search (HetGPS), a gradient- based algorithm that optimizes the parameter space of underspecified MARL. environ- ments to find scenarios where heterogeneity is advantageous. Across different environments, we show that HetGPS rediscovers the reward regimes predicted by our theory to maximize the advantage of heterogeneity. both validating HetGPS and connecting our theoretical insights to reward design in MARL. Together, these results help us understand when behavioral diversity delivers a measurable benefit.
'Equal contribution, listed alphabetically.
Websi te and code: https: wws. gowgle..oooe..oooooooooooooooo.. www.gll...oooieeeeeeeeeeeeoeeeee wttpee.oo///////t//////eee

---

Published as a conference paper at ICLR 2026
INTRODUCTION
Collective systems, from robot fleets to insect colonies, tend to adopt one of two structures; a uniform shared blueprint or a set of distinct, specialized roles. In multi-agent learning, this reflected in the choice between behavioral homogeneity (all agents behave identically) and behavioral heterogeneity (agents specialize) (Bettini et al., 2023; 2025; Rudolph et al., 2021). Such behavioral diversity can be achieved, e.g., via distinct policies (neural heterogeneity) or shared policies conditioning on diverse inputs, such as agent roles (Leibo et al., 2019). Although diversity unlocks role specialization and asymmetric information use, it also introduces extra coordination cost, representation overhead, and learning complexity (Li et al., 2021). This trade-off leads us to ask: under what conditions will heterogeneous agents outperform the best homogeneous baseline?
A natural setting to study this question in is multi-agent task allocation, where N agents allocate effort across M concurrent tasks. Here. we define effort agent's s contribution to a given task (e.g.. proximity to a goal, or quantity of task-specific resource the agent gathered), computed in environment-specife manner. The focus of our work is behavioral, outcome-based heterogeneity, defined through these efforts: a homogeneous team is one where all agents have the same effort allocations (e.g., every agent allocates 0.75 of its effort task and 0.25 to task B), whereas a heterogeneous team allows agents to achieve specialized allocations. We relate this abstract effort to environmental rewards in many diverse environments, including cooperative navigation, tag, football (Sec. 5), Colonel Blotto games, and level based foraging (App. E) (Roberson, 2006; Noel, 2022; Papoudakis al., 2021; Terry et al., 2021). We ask: what effort-based reward functions require heterogeneous behaviors to be maximized?
abstract quantity representing the
Theoretical Insights. We first study pure, non-spatial and instantaneous variant of multi-agent task allocation: each agent commits its effort allocation once, and the team is rewarded immediately (Sec. 2). We start from the observation that team reward many effort-allocation problems can be expressed as R(A)- U (Ti (a1).... Tas (ax)), where A (ray) is the N x M matrix of agent effort allocations, and a, is the effort allocation vector of agent The inner, task-level operator T; assigns score corresponding to the N agents' efforts on the ith task and the outer operator U combines the resulting M task scores into a scalar global reward. Choosing T and U to be the sum operator Σ recovers the Ej ΣS Pay reward common in RL, whereas alternatives such as MAX, MIN, power means, or soft-ma encode very different effort-reward relationships. Assuming such a reward structure, we compare the optimal heterogeneous reward, Rhets with the best reward attainable under a homogeneous allocation, Rhom, and define their difference as the heterogeneity gain AR Rhct - Rhom (Fig. 1). Our main insight is that AR is determined by the curvature of T and U: specifically, whether they are Schur-convex or Schur-concave. These criteria immediately enable us to characterize the heterogeneity gain of broad families of reward functions (Table 3); for instance. the soft-max operator switches from Schur-concave to Schur-convex as its temperature increases. We also find exact expressions for AR in several important cases. These results help explain, for example, why a reward structure that involves a min operator (usually used to enforce that only one agent should pursue goal) will require behavioral diversity from the agents (Bettini et al., 2024). We relate our findings to multi-agent reinforcement learning (MARL), where environments may be embodied and tine-extended. by setting R(Ar) as the stepwise reward over allocation sequence (Ar))=1......r
Algorithmic Search. To study heterogeneity in MARL settings not covered by our theoretical analysis, we develop Heterogeneity Gain Parameter Search (HetGPS), a gradient-based algorithm that optimizes parameters 0 of underspecified, differentiable MARL environments via backpropagation to find configurations that maximize or minimize the empirical AR (we assume differentiabilliy for training efficiency, but consider non-differentiable environments in App. P). While HetGPS can in principle optimize any differentiable environment feature to influence AR, we use it here to explore reward structures, as a means of verifying and extending our theoretical insights. Maximizing the heterogeneity gain allows us discover reward functions where behavioral diversity is essential. Minimizing the gain leads us to settings where homogeneous policies are sufficient.
Experiments. We validate our theoretical insights, and HetGPS, in simulation, by evaluating in both single-shot and long-horizon reinforcement learning environments whose reward structure instantiates the kinds of aggregation operators studied. First, in a continuous and discrete matrix game, we test reward structures based on all nine possible combinations of (min, mean, max). and find that the heterogeneity gains that result from the agents' learned policies match our theoretical predictions: concave outer operators and convex inner operators benefit heterogeneous teams. Next, we test
2

---

Published as a conference paper at ICLR 2026
the same operators in embodied, partially observable environments: calpite, Tag, and Football. We find that our theory also transfers to such long-horizon MARL settings, and show that reward structures that maximize heterogeneity are meaningful and practically useful. Finally, we find that the empirical heterogeneity gain disappears as the richness of agents' observations is increased, recovering the finding that rich observations allow agents with identical policy networks be behav- iorally heterogeneous (Bettini et al., 2023; Leibo et al., 2019).
We then turn to HetGPS. Across two parameterizable families of operators (Softmax and Power-Sum), we show that, despite running on embodied environments, HetGPS rediscovers the reward regimes predicted by our eurvature theory to maximize the heterogeneity gain, validating both HetGPS and the connection between our theoretical insights and MARL reward design (Sec. 5).
1.1 RELATED WORKS
Behavioral Diversity in MARL. Behavioral heterogeneity, where capability-identical agents learn distinct policies, can markedly improve exploration, robustness, and reward (Bettini et al., 2023). Yet heterogeneity reduces parameter sharing and thus sample-effiiiency, so core practical question is when its benefits outweigh that cost. Existing MARL methods typically adopt one of two poles: en- dowing each agent with its own network, enforcing parameter sharing all agents follow single policy (Gupta et al., 2017a; Rashid et al., 2020; Foerster et al., 2018; Kortvelesy & Prorok, 2022; Sukhbaatar al., 2016). A large body of work explores the fifciencyy-iversiie trade-off (Christianos et al., 2021; Fu et al., 2022) by interpolating between these extremes: e.g., injecting agent IDs into the observation (Foerster et al., 2016; Gupta al., 2017a). masking different subsets of shared weights (Li et al., 2024b), sharing only selected layers (Li et al., 2021), pruning a shared network into agent-specific sub sub-graphs (Kim & Sung, 2023), or producing per-agent parameters with a hypernet- work (Tessera et al., 2024). Further, several methods for promoting behavioral diversity in MARL have been proposed, such as: conditioning agents' policies on a latent representation (Wang et al., 2020), decomposing and clustering action spaces (Wang et al., 2021), dynamically grouping agents to share parameters (Yang et al., 2022), applying structural constraints to the agents' policies (Bettini et al., 2024), or by intrinsic rewards that maximize diversity (Li et al., 2021; Jaques et al., 2019; Wang et al., 2019; Jiang & Lu, 2021; Mahajan et al., 2019; Liu et al., 2023; 2024; Li et al., 2024a). While these studies demonstrate how to obtain diversity. they presume tasks where heterogeneity is advantageous. Our work addresses the orthogonal question of when diversity is beneficial, giving a principled characterization of which reward structures create that incentive in the first place.
Task Allocation. Classic resource-allocatioo settings, in which a team must divide finite effort among simultaneous objectives, a central proving ground for cooperative MARL. In robotics, potential-field and market-based learning are the dominant tools for coverage, exploration, and load-balancing tasks (Gupta et al., 201 7b; Lowe et al., 2017). Game-theoretic analysis and, recently, MARL, play the same role in discrete counterparts such as Colonel-Blott contests, where players decide how to spread forces over several "battlefields" (Roberson, 2006; Noel, 2022). Embodied benchmarks like level-based foraging are heavily studied in MARI,, and expose the tension between uniform and specialized effort allocations (Papoudakis et al., 2021). The survey of (Zhang et al., 2019) highlights how cooperative performance is governed by the shape of the shared reward and the equilibria it induces. Our contribution sharpens this perspective: we prove that the curvature of nested aggregation operators characterizes when heterogeneous allocations dominate homogeneous ones, and introduce algorithmic tools for further exploring settings where diversity is needed.
Environment Co-design. Co-design is a paradigm where agent policies and their mission envi- romment are simultancously optimized (Gao et al., 2024; Amir et al., 2025). Our HetGPS algorithm is related to PAIRED (Dennis et al., 2020), method which automatically designs environments in a curriculum such that an antagonist agent succeeds while the protagonist agent fails. This makes so that resulting environments are challenging enough without being unsolvable. Similarly, HetGPS designs environments that are advantageous to heterogeneous teams, while disadvantaging homogeneous teams. The key differences are: (1) the environment designer uses direct regret gradi- ent backpropagation via differentiable simulator instead of RL; this enables higher efficiency by directly leveraging all the environment gradient data available during collection while preventing RL-related issues identified in subsequent works (Jiang et al., 2021; Parker-Holder et al., 2021) such as exploration inefficiency and the need for a reward signal; and (2), the protagonist and antagonist are independent multi-agent teams instead of single agents.
3

---

Published as a conference paper at ICLR 2026
2 PROBLEM SETTING
Consider a set of N agents and M tasks. Each agent i {I...., : allocates effort among the tasks according to the budget constraints: r1i, ri....., , Tiad 2 with ΣØ= Faj I 1, where Tiy is defined as the effort agent puts into task j. Here, "effort" rij i8 scalar input to the reward function representing the agent's 's contribution to the task, such resource allocation (App. E) or realized goal proximity (Sec. 5). We can consider both continuous allocations (Tay can be any real number) and discrete allocations (raj restricted to
finite set of options), with most results in this work focusing the continuous case. We collect all agents' allocations into N x M matrix: A [ra]]'
For each task let the j-th column of the effort matrix be 02 [r.j:..., "Nn]] "Ny)). A task-level aggregator T IR + maps these efforts to task score, and an outer aggregator U RM -R combines the M scores into the team reward, R(A) = (T (m1), .......... Tar (am)). Both T; and U are generalised aggregators: symmetric and coordinate-we wise non-decreasing. mirroring the familiar properties of >. When every task shares the same inner aggregator we simply drop the subscript and write T. In Figure 1, to highlight fact that is aggregating rewards, we write R(A) = + = Tiy, where (in abuse of notation) the outer symbol + denotes U and the inner symbol + denotes Tj.
N
Homogeneous vs. Heterogeneous Strategies. A homogeneous strategy is one where all agents have the same allocation (i.e., devote the same amount of effort to given task j): rij V,Vi, i, In this case, the allocation matrix A consists of identical rows. We define Rnom = max (c.....x))44 R R(A)
where - {(c1...., Cj 2 0, Σ s 1} is the closed unit simplex. heterogeneous strategy allows each agent i to choose any (Fai,.... TiM) E 4 independently. Then Bhot
max max - R ((A) We define the heterogeneity gain as: AR Rhet Rhom This quantity
measures how much greater the overall reward can be when agents are allowed to specialize differently across tasks, compared to when they must behave identically. Characterizing when AR is our main focus in this work.
MARL extension. In MARL, the effort value Fij represents the contribution of agent to task j as computed by the environment based on agent i's actions. The aggregate reward R(A) can represent: (i) the payoff of a one-shot effort-allocation game, (ii) the return or sparse terminal reward of an episode, or (iii) the stepwise reward, giving the discounted return Σ 7' (((A.) for sequence (At) of allocations? AR 0 implies that the best heterogeneous policies outperform the best homogeneous ones. practice, this is evidence of an advantage to heterogeneity and not formal guarantee, as learning agents may not always converge to optimal policies.
Examples. App. contains examples of generalized aggregators. Our framework flexible, and can be applied to many settings, including ones not ordinarily thought of as "task allocation": in Sec. 5, we apply it to one-shot allocation games, aueti- navigation, tag, and football. Furthermore, in App. E, we analyze the heterogeneity gain of two well-known environments from the literature: Team Colonel Blotto games (Noel, 2022) and level-based foraging (Papoudakis et al., 2021).
ANALYSIS
Focusing on continuous allocations, we ask what properties of aggregators guarantee AR > O. We draw on the concept of Schur-convexity. Schur-convex functions can be understood generalizing symmetric, convex aggregators: every convex and symmetric function is Schur-convex, but a Schur- convex function is not necessarily convex (Roberts & Varberg, 1974; Peajcariaac & Tong, 1992). Proofs for all results are available in App. G.
All results in this work can be extended the where ra, TIM 2 Buin and Σn4 rij S
Bmaz for some arbitrary Bmin, Bmaz E R.
To extend this further, our theoretical results hold even the reward function varies over time, Re(At).
4

---

Published as a conference paper at ICLR 2026
Since both the outer aggregator U and the task-level aggregators T non-decreasing, optimal effort allocation will always have each agents' efforts summing to 1. Hence, from here on, we assume without loss of generality that Σラ= Tij = L. We call such allocations admissible.
Definition 3.1 (Majorization). Let x (II,...,ZN) .N) and = (V1...., UN) be two vectors in RV such that Ei=1 ((( -i=1 U(s)- Les I(I) L()) 2 =(2) 2 .... 2 (NN) and V(1) 9(2) 2 .... 2 U(N) be the components of x and y sorted in descending order. We say that x majorizes y (written z > y) 1.N.
E() 2 Ex= M(i) for k = 1.22....,
Definition 3.2 (Schur-Convex Function). A symmetric function f T:R R is Schur-convex if for any two vectors æ. E RN with x > y. we have f(x) 2 f())- If the inequality is strict whenever x: and y are not permutations of each other, then is said be strictly Schur-convex. Similarly, is Schur-concave if f(x) S f1y whenever x >
Intuitively, x > y means one can obtain y from x by repeatedly moving mass from larger to smaller coordinates, thereby making the vector more uniform. Schur-convexity is then statement functionns 's curvature: I is Schur-convex if it increases with inequality, or is Schur-concave increases with uniformity. We show here connection between Schur-convexity (concavity) and AR.
Call an allocation matrix A trivial if there exists a task j" such that every agent allocates its entire budget to that task, i.e. rij* Bmax and rij 0 Vi, Vj j"; otherwise A is non-trivial. Then:
Theorem 3.1 (Positive Heterogeneity Gain via Schur-convex Inner Aggregators). Let N, M 2 2, and assume that (i) each task-level aggregator Т is strictly cchur-conve and (ii) the outer aggregator U is coordinate-wise strictly increasing. Then either all admissible optimal homogeneous allocations are trivial, or AR >> 0.
If the task-level aggregator is instead Schur-concave, we can show there is no heterogeneity gain: Theorem 3.2 (No Heterogeneity Gain via Schur-concave Inner Aggregators). Let N, 2 If each task-level aggregator T, is Schur-concave then AR
0.
We see that Schur- Schur-convexity of the inner aggregator produces AR >> 0. whereas Schur- Schur-concavity implies AR = O. Analyzing the outer aggregator U is trickier, because acts on task-score vectors (Ti(a)).... TM (am=) whose sum Σm Ti(a;) may vary, so majorization is not directly applicable. extend our analysis to U if our inner aggregators normalized to keep the sum constant: Ee' Ti(a)) C' for any admissible allocation. Assuming this, we can invoke majorization again, and the relationship between convexity and AR reverses: if the outer aggregator U is Schur-convex, the heterogeneity gain vanishes. Let us prove this.
However,
Theorem 3.3 (No Heterogeneity Gain for Schur-Convex U with Constant-Sum Task Scores). Let N. M 2 2. Suppose that for any admissible allocation A, (i) every task score is non-negative, and obeys T; (O....... ... 0) O, and (ii) the sum of task score is always Σ T (a;)) C. IfU is strictly Schur-convex function, then AR = 0.
It is crucial to note that this constant-sum assumption is specific to Thm. 3.3 and is not required for our other results, which apply broadly.
Sum-Form Aggregators. In App. F, we show that the above results reduce to a simple convexity test for sun-form aggregators: a broad class of aggregators that describes most reward structures we consider in this work. This makes testing whether AR > 0 a simple computation in many cases.
Parameterizable Families of Aggregators. A core topic this work is reward design: how can we craft team objectives that either advantage or disadvantage behavioral diversity? To do this, it helpful to first identify an appropriate search space. Our theoretical analysis enables us to narrow down this search space, and focus on aggregators whose curvature can be parametrized. Many family of aggregator functions [()))) can be parametrized by a scalar which controls whether the aggregation is Schur-conver or Schur-concave, and how strongly it penalizes (or favors) esp(trr)) is parametrized by its temperature, t, transitioning from being strictly Schur-concave when < 0 to strictly Schur-convex when > 0. We can define space of reward functions by selecting both the
inequalities among the components. For example, the softmax aggregator ΣN ΣY exp(t-red
5

---

ask what the Published as a conference paper at ICLR 2026
H eeterggeneity Gain AR (N M 2)
10.0
Discrete and continuous heterogeneity gains
7.5
T min
mean
(Inner temperaturee
5.0
0.4
(appr (pprox))
ARp
(M 1)/M
0.3
ARp
[N/M]/N
MNN2M)
ARP
Onler MOUR
1)/M
-2.5
0.2
ARp
(min M. N) 1)/M
-5.0
Outer max
0.1
ARP
-7.5
A8p
-10.0
0.0
-10
-5
10
(outer temperature)
Figure Left: Discrete (ARp) and continuous-allocation (ARp) heterogeneity gains for all U, T E {min, mean, max]. The indicator 1(N2M) equals 1 if N 2 M and O otherwise. Right: We plot the parametrized heterogeneity gains TR(L, N) when U and T are soft-max aggregators.
expl exp((erg)
task scores and outer aggregator to be softmax functions: let T2(A) Dist
EY exp (1122) Tijo
and let U (ai),, Tas (am))))) Σ/ exp(T-T,(A))
EN (x)()-T((A) (A(A), where 1, E RR parametrize the
inner and outer aggregators, respectively. AR is then dependent on and r. Fig. plots A AR when
N M 2. As a case study, we derive lower bounds on AR when N .M in Thm. 3.4.
Theorem 3.4 (Softmax heterogeneity gain for N M). Assume N = M 2 2, and ler (t,
e +N The heterogeneity gain for softmax aggregators (i) equals AR(t, r; N) = when t S
0: (ii) is bounded below by (1,,
when 0, S 0; and (iil) bounded below by
max ol,, - o(T, when I. > 0, 2 0.
Tab. contains more examples of aggregation operators parameterized by t. These families provide sweep smoothly from AR 0 to AR > () reward regimes. As f - #oo, most such aggregators converge to either min or max, and often reduce the arithmetic mean for certain parameter choices, motivating heterogeneity gain is when the outer and inner aggregator belong to the set {min, mean, max]. These aggregators are of special interest, since "min" can be seen as "maximally" Schur-concave function, "max" can be seen as "maximally" Schur-convex function, and "mean" is both Schur- convee and Schur-concave. Hence,
search space for potential reward functions, allowing
worth asking what the heterogeneity gain is when the outer and inner aggregator belong to the set (min, mean, max). We derive these gains in two cases: continuous allocations where rıy E (0, 1). and discrete effort allocations where rij {0, 1}. The results are summarized in Fig. 2, lefthand side (formal derivation available in App. G).
4 HETEROGENEITY GAIN PARAMETER SEARCH (HETGPS)
In complex scenarios where theory might be less applicable, we study heterogeneity through algo- rithmic search. We consider the setting of a Parametrized Dec-POMDP (PDec-POMDP defined in App. O). A PDec-POMDP represents Dec-POMDD (Oliehoek et al., 2016). where the observations, transitions, or reward are conditioned on parameters Hence, the return obtained by the agents, Go (T)) can be differentiated with respect 0: V.Go à gradient in differentiable simulator allows us back-propagate through time and optimize 0 via gradient ascent'.
d GO In particular, computing this
Heterogeneity Gain Parameter Search (HetGPS). We consider the problem of learning the environment parameters to maximize the empirical heterogeneity gain. The empirical heterogeneity gain is defined the difference in performance between heterogencous and homogeneous teams in
Although the same approach can train policies (Xu et al., 2022; Song et al., 2024), HetGPS instead optimizes environment parameters and policies separately, using standard zeroth-order policy-gradient methods, to avoid heing trapped in local minima.

---

Published as a conference paper at ICLR 2026
Algorithm 1 Heterogeneity Gain Parameter Search (HetGPS)
input Environment parameters 0, environment learning rate a, heterogeneous agent policy Thet homogeneous agent policy Thom
1: for in iterations do
2: Batch jet Rollout(0,mhe)) frollout het policies in environment 0)
3: Batch Rollout(O Thom) (rollout hom policies in environment 0}
4: HetGain = ComputeGain(Batchi..c Batc hom
5: if train env (i) then
6: 0 0 + a. (HetGain (train environment via backpropagation)
7: if trtaitraaeemnne agents(() then
(train het policies via MARL] 9: Thom MarlTrain(Thomm BaaTTrain(Thom.Batchhh.. homm) (train hom policies via MARL)
8: Whet f- TeanTraiiTTheeBathhhe
output final environment configuration 0, policies Thet, Thom
a given PDec-POMDP parametrization. We compare neurally heterogeneous agents (independent parameters) with neurally homogeneous agents (shared parameters). We denote their policies as Thet and Thom- Then, we can simply write the gain as: HelGain (Thet; Thom) G (Thet) G (Thom). representing the return of heterogeneous agents minus that of homogeneous agents on environment parametrization 0. HetGPS, shown in Alg. learns 0 by performing gradient ascent maximize the gain: 0 4- 0 V WoteeGainn (aaGGaiinnnaaaa (Thet: Thom]. The environment and the agents are trained in an iterative, bilevel optimization process. We discuss this process, and alternatives when the simulator is non-differentiable, in App. P. At every training iteration, HetGPS collects roll-out batches in the current environment 0 for both heterogeneous and homogeneous teams, computing the heterogeneity gain on the collected data. Then, updates 0 maximize the heterogeneity gain. Finally, to train the agents, it uses MARL, with any on-policy algorithm (c.g.. MAPPO (Yu et al., 2022)). The functions train env and train aangantgnssss s determine when to train each of the components in HetGPS. We consider two possible training regimes: (1) alternated: where HetGPS performs cycles of agent training iterations followed by y environment training iterations and (2) concurrent: where agents train at every iteration and the environment is updated every x iterations. Note that by performing descent instead of ascent, HetGPS can also be used to minimize the heterogeneity gain.
EXPERIMENTS
To empirically ground our theoretical analysis, we conduct a three-stage experimental study in cooperative MARL. We first analyze one-step. observation free matrix game in which each agent allocates effort rij over M tasks, and consider reward structures defined by aggregator pairs U, T e {min, mean, max]. We find that the agents' learned policies recover the exact heterogeneity gains derived in the theory (Fig. 2). Next, we transfer the same reward structures into embodied, time- extended environments: Multi-goal-capture 2v2 Tag, and Football. We show that our curvature theory continues to be informative in these settings. We discuss the learning dynamics that result, and perform further experiments highlighting the difference between neural and behavioral heterogeneity (Bettini et al., 2023). important for understanding our insights. Finally, to study HetGPS, we parametrize the reward structure of Multi-goal-capture using either parametrized Softmax or Power-Sum aggregators (App. 1), and run HetGPS to learn parameterizations that maximize the heterogeneity gain. HetGPS learns the theoretically optimal aggregator instantiations, validating its effectiveness discovering heterogeneous missions. Implementation details and visualizations are available in App. C and App. K.
(i) Task Allocation. We consider one-step observationless matrix game where N agents need to choose between M tasks. Their actions are effort allocations riy with rış 2 0,E, rij 1, composing matrix A. With aggregators taken from the set U,T T E (min, mean, max), our goal is to empirically confirm the heterogeneity gains derived in the theory in learning context. Each time the game is played, all agents obtain the global reward R(A) computed through the double aggregator. We consider two setups: (1) Continuous (rij Ro agents can distribute their efforts across tasks, (2) Discrete (r.j E {0, 1))) agents choose only one task. We train with N = M = 4 for 12 million steps. Fig. 6 shows the evolution of the heterogeneity gains. The final results match exactly the
7

---

Published as a conference paper at ICLR 2026
Discrete
Contimuous
1.0
1.0
U=min, T= min
Heterggnnett gain
U mean, T min
U max, T= min
0.5
0.5
U= max, T min
U= mean, T mean
0.0
0.0
U= T' mean
U= min, T= max
U= mean, T= max
10
10
U= max, T'= max
Number of frames (Millions)
Number of fromes (Millions)
Figure 3: Heterogeneity gain for the discrete and continuous matrix games with N = M = 4 over training iterations. We report mean and standard deviation after 12M frames over random seeds. The final results match the theoretical predictions in the Table of Fig. 2. Solid lines indicate reward structures predicted by theory to have AR > 0 in either the discrete or continuous setting; dashed lines indicate predicted no gain in both settings. Final gain values reported in Tab. 7 and Tab. 8.
Uwmmen Timin 2. mas T min
near, mamn
main 7 maa 6 mas 7 mac
am
max mea
mam, max
E moy T rean
leeterogenely gain
lettrrgeenets gailt
0.2
0.1
0.0
-0.1
0
5
10
15
20
25
30
10
15
20
Nutnerr of fremes (Milhons)
Namber frames (Millions)
(a) calttre
(b) 2v2 Tag.
Figure 4: Heterogeneity gain for Multi-goal-capture and 2v2 Tag throughout training. We report mean and standard deviation for 30 million training frames over 9 random seeds. Final gain values are reported in Tab. 11 and Tab. 12.
theoretical predictions of Fig. 2 and our curvature theory: concave outer and convex inner aggregators favor heterogeneity. Additional details and results, e-g. for N, M E (2, 8, 11), are in App. J.
(ii-1) Multi-goal-capture. Next, we investigate time-extended, embodied scenario called Multi- goal-capture, based on multi-goal navigation missions (Terry et al., 2021). In Multi-goul caatie agents need to navigate to goals, and efforts rf, are continuous scalars computed based on their proximity to these goals. We provide details in App. K. Our goal is to show that the results obtained in the matrix game still hold in this embodied, long-horizs horizong setting. We again consider aggregators U,T e {min, mean, max). After 30M training frames (Fig. 4a) the empirical heterogeneity gains differ, numerically, from those of the static matrix-game because agents now realize their allocations ri through eime-extended motion. Nonetheless, our curvature theory reliably predicts when there is heterogeneity gain (Fig. 2): is positive only for the concave-conver pairs U min, T max and U mean, T max. We further explain these results (including the interesting presence of "negative" heterogeneity gains) in App. K. Note that the aggregator pairs in this experiment contrived: they encode practically meaningful global objectives. For example, U max, T max implies "at least one agent should go at least one goal"; U max, T min implies "all agents should go to the same goal",, and so on. U = min, T = max, concave-convex setting shown by our theory to favor heterogeneity, implies "each agent should go to a different goal and all goals should be covered" which is natural goal for this scenario. This is because T max encodes a task that needs just one agent to be completed (e.g., find an object), while U = min encodes that all tasks should be attended (i.e., agents need to diversify their choices).
not
Observability- HbserrabiityyHeeenngeeity Trade-Oft Off: To understand our theoretical results, is important to solidify the difference between neural heterogeneity (agents having different neural networks) and behavioral heterogeneity (agents acting differently). Our insights concern behavioral heterogeneity, which need not be neurally induced. We show this in App. N, showing that: as the observability of
8

---

Published as a conference paper at ICLR 2026
Soltmax (U)
Het. gain
50
Softmax
0.1
0.0
0
25
50
75
25
50
75
0
25
50
73
Number of frames (Millions)
Number of frames (Millions)
Number of frames (Millions)
(a) HetGPS with Softmax aggregators (r E R). T 2 i Schur-convex;
0 Schur-coneave.
Powerstam (T)
(U
1.5
0.2
Het. gain
Powerssu
1.0-
0.5
0.0
25
0
75
50
Number of frames (Millions)
Number of frames (Millions)
Number of frames (Millions)
(b) HetGPS with Power-Sum aggregators (T [0.3, 6). r 2 is Schur-convex; T S is Schur-concave.
Figure 5: HetGPS results in Multi caali-g The two leftmost columns report the evolution of aggregator parameters through training. while the rightmost column shows the obtained heterogeneity gain. This result empirically demonstrates that HetGPS rediscovers the reward structure predicted by our theory to maximize the gain, making the inner aggregator convex, and the outer aggregator concave. We report mean and standard deviation for 90M training frames over 13 random seeds.
neurally homogeneous agents increases (allowing them to sense each other), these agents can become behaviorally heterogencous, and thus optimize the heterogeneity gain. This result is visualized here.
(ii-2) 2v2 Tag. In our tag experiment, two learning chasers pursue two heuristic escapees in randomized obstacle field. We define the effort r'y to be 1 if chasing agent manages to capture escaping agent) j by time t. and otherwise. Whereas Multi Multi-goal-capale goal-capture had continuous effort allocations, here they are discrete. The global reward is again computed with aggregators U, T e (min, mean, max). }, and is awarded at every time step. This is a sparse reward signal only awarded upon mission success. For example, U min, T max pays out only if both escapees are each caught by a chaser, encouraging heterogeneity. Training outcomes are summarized in Fig. 4b. We again see that our theoretical results in Fig. 2 (discrete efforts) predict exactly which aggregators will exhibit AR > 0. More details, visuals, and experiments with greater number of agents are available in App. L and here.
(ii-3) Football. We evaluate our theory in a complex continuous control football game to explore what happens when our reward structure R( () is only part of global cooperative reward. To this end, we design a drill in the VMAS Foothall environment (Bettini et al., 2022), where one agent is tasked to score, while the other has block the incoming opponent. App. M shows that, also in this case, our theory is highly predictive, with visuals available here.
(iii) Heterogeneous Reward Design. We apply HetGPS
multi-goal-capture and ask whether finds the same aggregator parameterizations predicted by our theory to maximize the heterogeneity gain. We turn the environment into a PDec-POMDD by parameterizing the reward as R (A')
OH ① D Pr(,- with parametrized inner and outer aggregators U = + T = + Our goal is to learn the parameters = (71, 72), parametrizing T and U respectively, that maximize the heterogeneity gain. We consider two parametrized aggregators from Tab. Softmax and Power-Sum. Softmax: we parameterize both U and 7 using Softmax. We initialize = = 0, so U and T are initially mean, and run HetGPS (in App- Q we show that HetGPS is robust to adversarial initializations). In Fig. 5a, we show that, to maximize the heterogeneity gain, HetGPS learns to maximize TI, making T' Schur-convex, while minimizing 72, making U Schur-concave. Hence, it rediscovers the theoretically optimal reward function. The large variance in final parameters occurs because the Softmax aggregator saturates for large magnitudes (c.g.. |T| > 5): HetGPS correctly identifies this, leading seeds converge to arbitrary large values within it. Power-Sum: we parametrize both aggregators with nower-Sum. We initialize both functions to T = T2 = 1, representing sum, and run HetGPS. We constrain 71,2 [0.3, 6) to stabilize learning. In Fig. 5b,

---

Published as a conference paper at ICLR 2026
show that HetGPS learns to maximize 71, making T Schur-convex, while minimizing 72, making U Schur-concave; again rediscovering the optimal parametrization our theory predicts. These results simultaneously validate HetGPS and our curvature theory, since each arrives the same reward structure independently.
DISCUSSION
This work introduces tools for both diagnosing and designing reward functions that incentivize heterogeneity in cooperative MARL. In task allocation settings, our theory shows that the advantage of behavioral diversity is a predictable consequence reward curvature: if the inner aggregator is Schur-convex, amplifying inequality, and the outer aggregator is Schur-concave, amplifying uniformity, heterogeneous policies are strictly superior; reversing the curvature removes the benefit. Complementing this analysís, and covering settings where theory doesn't apply, the proposed HetGPS algorithm automatically steers underspecified environments to either side of the diversity boundary, letting us encourage suppress heterogeneity and providing sandbox for studying its advantages. Together, these results help turn the choice of heterogeneity from an ad-hoc heuristic into a controllable design dimension, and help reconcile past mixed results on parameter sharing.
A key remaining open question concerns how the environment's ' transition dynamics interact with reward curvature to shape heterogeneity gains, We expand on this open question, other directions for future work, and our scope/limitations, in App. R.
REPRODUCIBILITY STATEMENT
Our supplementary website contains the source code we used produce all results in this work, including the code used to train the agents, implementation of HetGPS, and the code used to produce all plots in the paper (see Appendix C). The readme contains detailed instructions on how to use this code. All mathematical claims made in this work are fully proven in the Appendix, and our assumptions are described in detail in Section ("Problem Setting"). Appendices Q and P address potential questions readers may have regarding the stability of the bilevel optimization process used in HetGPS and similar environment design algorithms in the literature. Finally, Appendix addresses the assumptions and scope of our work, and outlines some remaining open questions.
ACKNOWLEDGMENTS
This work is supported by European Research Council (ERC) Project 949940 (gAla) and ARL DCIST CRA 1911NE-11-2-0181.. We gratefully acknowledge their support.
REFERENCES
Michael Amir, Guang Yang, Zhan Gao, Keisuke Okumura, Heedo Woo, and Amanda Prorok. Recode: Reinforcement learning-bart dynamic constraint design for multi-agent coordination, 2025. arXiv preprint 2507.19151. https: arwiv www.iiivooooo orgg abs 2507 19151.
Matteo Bettini, Ryan Kortvelesy, Jan Blumenkamp, and Amanda Prorok. Vmas: A vectorized multi- agent simulator for collective robot learning. Proceedings of the 16th International Symposium on Distributed Autonomous Robotic Systems, 2022. URL https:t/////ccc. htt:///ink swrinngr.rrig......... com/
chapter/10.11i http:/1...111//990 3-031-51497-5
Matteo Bettini, Ajay Shankar, and Amanda Prorok. Heterogeneous multi-robot reinforcement learning. Proceedings of the 22nd International Conference on Autonomous Agents and Multi- agent Systems, pp. 1485-1494 2023, URL https: /dl. acm. org/ /oi/ aalo///bs/iii 5555/ 3545946. 3598801.
Matteo Bettini, Ryan Kortvelesy, and Amanda Prorok. Controlling behavioral diversity in multi-agent agent reinforcement learning. Forty-first International Conference on Machine Learning, 2024. URL https: http////pppe/eeeee//e/p/e./eeeep net foo.mriiddoooooo dorumm?id-g
10

---

Published as a conference paper at ICLR 2026
Matteo Bettini, Ajay Shankar, and Amanda Prorok. System neural diversity: Measuring behavioral heterogeneity in multi-agent learning. Journal of Machine Learning Research, 26(163):1-27, 2025.
URL http: jmir org/ papers/ vv2 /226//2/44444 1477 .hmml.
Albert Bou, Matteo Bettini, Sebastian Dittert, Vikash Kumar, Shagun Sodhani, Xiaomeng Yang. Gianni De Fabritiis, and Vincent Moens. Torchrl: A data-driven decision- making library for pytorch. In The Twelfth International Conference on Learning Representations, 2023.
Filippos Christianos, Georgios Papoudakis, Muhammad A Rahman, and Stefano V Albrecht. Scaling multi-agent reinforcement learning with selective parameter sharing. International Conference on Machine Learning, pp. 1989-1998, 2021.
Michael Dennis, Natasha Jaques, Eugene Vimitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Advances in neural information processing systems, 33: 18:13099-10661 2020.
Jakob Foerster, Ioannis Alexandros Assacl, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems, 29, 2016.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. Proceedings of the AAAI conference artificial intelligence, 32, 2018.
Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang, and Yi Wu. Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning. International Conference on Machine Learning, pp.
2022.
Zhan Gao, Guang Yang. and Amanda Prorok. Co-optimization of environment and policies for decentralized multi-agent navigation. arXiv preprint arXiv:2403.14555 2024.
Michael R Garey, David S Johnson, et al. A guide to the theory of np-completeness. Computers and intractability, pp. 37-79, 1990.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In Autonomous Agents and Multiagent Systems: AAMAS 2017 Workshops, Best Papers, São Paulo, Brazil, May 8-12, 2017, Revised Selected Papers 16, pp. 66 83. Springer, 2017a.
Jayesh K. Gupta, Maxim Egorov, and Mykel J. Kochenderfer. Cooperative multi-agent control using deep reinforeement learning- In Proceedings of the International Conference Autonomous Agents and Multiagent Systems (AAMAS), 2017b.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. International Conference on Machine Learning, pp. 3040- 3049, 2019.
Jiechuan Jiang and Zongqing Lu. The emergence of individuality. Proceedings of the 38th In- terntiional Conference Machine Learning, 139:4992-5000 18 24 Jul 2021. URL https: / //proceedings..... mlr wwt.:mmw.....m....mmmmmmmmmmme.e wwwpppssssivl/1 (t233/jiaanee jiang21g html.
Minqi Jiang, Michael D Dennis, Jack Parker- Parker-Holder, Jakob Nicolaus Foerster, Edward Grefen- stette, and Tim Rocktäschel. Replay-guided adversarial environment design. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: /ttp///pppeeeieeeeeeeeee ew net. forum? i -d00::-
Woojun Kim and Youngchul Sung. Parameter sharing with network pruning for scalable multi- agent deep reinforcement learning. Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 1942-1950, 2023.
Ryan Kortvelesy and Amanda Prorok. Qgnn: Value function factorisation with graph neural networks. arXiv preprint arX5v:2205.13000 2022.
11

---

Published as a conference paper at ICLR 2026
Joel Z Leibo, Julien Perolat, Edward Hughes, Steven Wheelwright, Adam H Marblestone, Edgar Modñez-Guzzán, Peter Sunchag, lain Dunning, and Thore Graepel. Malthusian reinforcement learning. In Proceedings of the 18th International Conference on Autonomous Agents and MultiA- gen Systems, pp. 1099-1107, 2019.
Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang. Celebrating diversity shared multi-agent reinforcement learning. Ad- vances in Neural Information Processing Systems, 34:3991-4002, 2021. neurips fttpripsssepppprrrfeeelee//eee/e www.aeeaeaa.5aaaaaaaaeeaae Sttparr_feeeeeaparr/////////
URL
20aee3a5f46437555
Tianuu Li, Kun Zhu, Juan Li, and Yang Zhang. Learning distinguishable trajectory representation with contrastive loss. Advances in Neural Information Processing Systems, 37:64454-6441 2024a.
Xinran Li, Ling Pan, and Jun Zhang. Kaleidoscope: Learnable masks for heterogeneous multi- agent reinforcement learning. Advances in Neural Information Processing Systems, 37:22081 22106, 2024b. URL https: http:::ss/ppppeeeeengeeeeeeeee/s neurips ce ct/ wwtp:/aaperppeeeeee httpee//pppppeeeeeeeeeeeeeeeeeee
falfflilaaaaaae paper/ pdf.
Shunyu Liu, Yihe Zhou, Jie Song, Tongya Zheng, Kaixuan Chen, Tongtian Zhu, Zunlei Feng, and Mingli Song. Contrastive identity-aware learning for multi-agent value decomposition. Proceedings of the AAAI Conference Artificial Intelligence, 37(10): 1100:-11995110100 2023.
Shunyu Liu, Jie Song, Yihe Zhou, Na Yu, Kaixuan Chen, Zunlei Feng, and Mingli Song. Interaction pattern disentangling for multi-agent reinforcement learning. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2024.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Picter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compettive environments. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi- agent variational exploration. Advances in Neural Information Processing Systems, 32, 2019. URL https: neurips www.res.c.eappppppeeeeooe file/f81 / http://EEaaccaaaaeee///eeeeeeea2
pdf.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari.
Markov decision processes with continuous side information. In Algorithmic learning theory, pp. 597-618. PMLR, 2018.
Joseph Christian Noel. Reinforcement learning agents in colonel blotto. arXiv preprint
arXiv:2204.02785,, 2022.
Frans A Oliehoek, Christopher Amato, al. A concise introduction decentralized POMDPs, volume 1. Springer, 2016.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks (NeurIPS). 2021.
Jack Parker-Holder, Minqi Jiang, Michael D Dennis, Mikayel Samvelyan, Jakob Nicolaus Foerster, Edward Grefenstette, and Tim Rocktäschel. That escalated quickly: Compounding complexity by editing levels at the frontier of agent capabilities. In Deep RL Workshop NewrlPS 2021, 2021. URL httpt:tt//.. http:///peeerreee
net forum? 3d=
Josip E Peajcariaac and Yung Liang Tong. Convex functions, partial orderings, and statistical applications. Academic Press, 1992.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agen reinforcement learning. Journal of Machine Learning Research, 21(178):1-51 2020. URL http: : / fmlrr. ptgg/papers///1//22 /20- 081 html.
12

---

Published as a conference paper at ICLR 2026
Brian Roberson. The colonel blotto game. Economic Theory, 29(1):1-24, 2006.
A Wayne Roberts and Dale E Varberg. Convex Functions: Convex Functions, volume 57. Academic Press, 1974.
Max Rudolph, Sonia Chernova, and Harish Ravichandar. Desperate times call for desperate measures: towards risk-adaptive task allocation. 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2597, 2021.
Marwaan Simaan and Jose B Cruz. On the stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications, 11(5):333-55, 1973.
Yunlong Song, Sang bae Kim, and Davide Scaramuzza. Learning quadruped locomotion using differentiable simulation. In 8th Annual Conference Robot Learning, 2024. URL https: // //oppnneviieeeeeee////eee/e wwwp:/ewwwwwww.eeeeeeeeeeeeeeeee
i XoxXopTTjbby.
Kenneth O Stanley, Jeff Clune, Joel Lehman, and Risto Mikkuulainen, Designing neural networks through neuroevolution. Nature Muchine Intelligence, 1(1):24-35, 2019.
Sainbayar Sukhbaatar, arthur szlam, and Rob Fergus. Learning multiagent communica- tion with backpropagation. Advances in Neural Information Processing Systems, 29, 2016. URL httpps:/pproceeeingngge/ neurips cwtppppr.pppppppppeeeeeeeeeeeee htappee_filesspppre/a222a pdf.
J Terry, Benjamin Black, Nathaniel Grammel, Mario Jayakumar, Ananth Hari, Ryan Sullivan, Luis Santos, Clemens Dieffendahl, Caroline Horsch, Rodrigo Perez- Vicente, et al. Pettingzoo: Gym for multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34: 15032-15043, 2021.
Kale-ab Abebe Tessera, Arrasy Rahman, and Stefano V Albrecht. Hypermarl: Adaptive hypernet- works for multi-agent rl. arXiv preprint arXiv:2412.04233, 2024.
Wang, T Gupta, B Peng, A Mahajan, S Whiteson, and C Zhang. Rode: learning roles to decompose multi- agent tasks. Proceedings of the International Conference Learning Representations, 2021.
Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang, Influence- Based Multi-Agent Explo- ration. International Conference on Learning Representations, 2019.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. ROMA: Multi-agent reinforcement learning with emergent roles. Proceedings of the 37th International Conference Machine Learning, 119:9876-9886, 13-18 Jul 2020. URL https: U mlr. par..press/// v119/wawd 1119/wang20f html.
Jie Xu, Miles Macklin, Viktor Makoviychuk, Yashraj Narang, Animesh Garg. Fabio Ramos, and Woj- ciech Matusik. Accelerated policy learning with parallel differentiable simulation. In International Conference on Learning Representations, 2022. URL https: wwwp///eeeeeeeeeeeeeeeeeee www.:/ee//ofuuuaa forum? id=zsKRQMvttc.
Omry Yadan. Hydra framework for elegantly configuring complex applications. Github, 2019.
URL https::///// / / github. con/ www.b/oorrreeerrccheeaeea.
Mingyu Yang, Jian Zhao, Xunhan Hu, Wengang Zhou, Jiangcheng Zhu, and Houqiang Li. Ldsa: Learning dynamic subtask assignment in cooperative multi-agent reinforcement learning. Advances in neural information processing systems, 35: 15:1668-1710, 2022.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo cooperative multi-agent games. Advances in Neural Information Processing Systems, 35:24611-24624, 2022.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:1911.10633 2019.
13

---

Published as a conference paper at ICLR 2026
A COMPUTATIONAL RESOURCES USED
For the realization of this work, we have employed computational resources that have gone towards: experiment design, prototyping, and running final experiment results. Simulation and training are both run on GPUs, no CPU compute has been used. Results have been stored on the WANDB cloud service. We estimate:
300 compute hours on an NVIDIA GeForce RTX 2080 Ti GPU,
500 compute hours NVIDIA L40S GPU.
Simply reproucing our results using the available code will take considerably less compute hours (around a day).
B CODE AND DATA AVAILABILITY
We provide the link to the code in the supplementary website. The code contains instructions on how to reproduce the experiments in the paper and dedicated YAML files containing the hyperparameters for each experiment presented. The YAML files are structured according to the HYDRA (Yadan, 2019) framework which allows smooth reproduction as well systematic and standardized configuration. We further attach all scripts to reproduce the plots in the paper from the experiment results.
C IMPLEMENTATION DETAILS
For all experiments, we use the MAPPO MARL algorithm (Yu et al., 2022). Environments are implemented in the multi-agent environment simulator VMAS (Bettini al., 2022), and trained using TorchRL (Bou et al., 2023). Both the actor and critic are two-layer MLPs with 256 neurons per layer and Tanh activation. Further details, such hyperparameter choices, are available in the attached code and YAML. configuration files.
single Nvidia L40 GPU. In the HetGPS experiments (Sec. 4), standard MARL training iteration (60,000 frames) takes approx. 15s; including the environment backpropaga- tion increases this approximately 20s.
Experiments
D USE OF LLMS
We used LLMs (ChatGPT 4o and Gemini 2.5 Pro) improve parts of the writing, e.g., make wording suggestions. We verified and take responsibility for all LLM-related outputs this work.
E COLONEL BLOTTO & LEVEL-BASED FORAGING
We describe how two well-known settings from the literature fit into our theoretical framework, and check what our theoretical results say about their heterogeneity gain.
E. TEAM COLONEL BLOTTO (FIXED ADVERSARY)
The Colonel Blotto game is well-known allocation game studied in both game theory and MARL (Roberson, 2006; Noel, 2022).
used to model election strategies and other resource based competitions. In the team variant with fixed adversary, N friendly colonels (agents) each distribute (fixed and equal) budget of troops riy 2 0, E Túp 1 across M battlefields j E {l...., M) (our tasks). A fixed adversary selects stochastic opposing allocation strategy, i.e. distribution madv over vectors
(a1..... as) which is fixed throughout training and evaluation. Let 85 Σn' Fij denote the team force committed to battlefield j. Our agents win against the adversary if the troops they allocate to a given field surpass the troops allocated by the adversary. The expected value secured on battlefield j is therefore
Ta Dj EaNsnai
[1[83
a
Uj
Pr ar-
[sj
az}.
14

---

Published as a conference paper at ICLR 2026
where 1[2: y] denotes the indicator function. This is a thresholded-sum that remains symmetric and coordinate-ve wise non-decte con-eecrgsinng in every agent's ' contribution Tíj. Aggregating across battlefields with value-weighte sum yields the team reward
M R(A)
E T(a)) ==1
Σ
T
rij
so the game fits the double-aggress aggreeationn structure R(A) +
Q Fij assumed in our analysis.
Heterogeneity Gain: This is continuous allocation game, and the inner aggregator Tj is an indicator function over the sum of troop allocations to battlefield j. This functiin is Schur-concave (and Schur-convex the same time!). Hence, by Thm. 3.2, heterogeneous colonel teams, where each colonel has a distinct troop allocation strategy, have no advantage over homogeneous teams, where all colonels employ the same allocation strategy: AR O. This makes sense, as it makes no difference whether two different colonels allocate x/2 troops to a battlefield, or one colonel allocates z troops the battlefield.
Our analysis also tells us what happens when we change Tj: this provides insights for generalizations of the Colonel Blotto game. For example, maybe the troops of different colonels don't cooperate as well with each other, such that two colonels allocating x/ 2 troops to a battlefield results in lower Ta-value than a single colonel allocating x troops. this case, Tÿ becomes strictly Schur-convex, and Thm. 3.1 tells us that AR > as long as the optimal allocation is non-trivial. Hence, heterogeneous teams are advantaged.
E.2 LEVEL--BASD FORAGING
The well-known level-based foraging (LBF) benchmark, based on the knapsack problem (Garey et al., 1990). is deceptively challenging, embodied MARL environment, where N agents are placed on a grid with M food items, and are tasked with collecting them. Each item j has an integer level Ly that must be met exceeded by the combined skills of the agents standing on that cell before can be collected (Papoudakis et al., 2021). I) Let agent i's skill be e,. At a given step the binary variable
M
my E (0.es),
with
Tij S
j=1
denotes whether contributes its skill to item j. our setting, we assume all agents are equally skilled, so = 1 Vi. Collecting these variables thus yields an allocation matrix A = [rip] E e; NxM which again matches our framework.
Inner aggregator.
A food item is harvested if the summed skill its cell reaches the threshold, so
Ty(a;) = L, /EM 2 T.g. = (r,)
This threshold-sum is symmetric and monotone, depending only on the sum of its arguments and therefore simultaneously Schur-convex and Schur-concave.
Outer aggregator.
The stepwise team reward the sum of harvested item values,
M
R(A)
Ti
T
ri))
Tij
j=1
so LBF also conforms to the double-aggregation form R(A) = (0) + ri--
15

---

Published as a conference paper at ICLR 2026
MARL Environment Reward. In the level-foraging environment, items that are picked up either disappear; replace themselves with different items; or replace themselves with the same item (possibly at a different cell). In all of these cases we can represent the cumulative reward as Σi ?' Rd (At) for some sequence (Rs)t=1....11 of rewards adhering to the above reward structure.
Heterogeneity Gain: We analyze the heterogeneity gap of specific stepwise reward R.
Because this an embodied environment where each agent can either stand on an item (rej = 1) or not (rij 0), effort allocations discrete. Our continuous curvature test therefore does not apply directly, but the discrete analysis in Fig. 2 (left panel) does.
The table in Fig. 2 tells something about the where all items have level L, = 1. In this case, since we assumed e; = 1 for all agents, the inner aggregator reduces to
Ty(a,) Σ raj 1 max; Tijj
while the outer aggregator is an unnormalized sum, which becomes the mean when divided by M. Hence R(AA) E, max; rig, which, up to the constant 1/M, is exactly the case U mean, T max of Fig. 2. That table shows
1 M AR min M, - -1
M
so the heterogeneity gap is strictly positive whenever the team could in principle cover more than one item (min(M, N} > 1). Intuitively, a homogeneous team can only collect one item per step (all agents flock to the same cell), whereas heterogeneous agents may spread out and capture up to min M, M, } items simultaneously.
This analysis be extended the case where all items have the same level T. >>> and L. N by grouping agents into Ñ := N/ agent teams, each bundle contributing exactly L units of skill. This yields
1 AR
min Min -
ML (We omit the formal analysis, which is not difficult). Thus, if the team can form at least two such bundles (Ñ > 1), heterogeneity is again advantageous. If it cannot, then AR = 0, and there is no advantage heterogeneity.
M
When the levels }Lا differ, an exact closed form is harder, but in general we expect AR > 0 whenever there some combination of items that the heterogeneous team can collect, which in total is worth more than the largest single item that can be collected if all N agents stand on its cell.
In LBF, therefore, our theory suggests that behavioral diversity is often advantageous. Note that (unlike the Colonel Blotto game) since LBF is an embodied, time-extended MARL environment, this analysis does not formally guarantee an advantage to RL-based heterogencous agent teams: rather, it identifies that there are effort allocation strategies that will give these teams an advantage over homogeneous teams. The agents must still learn and be able to execute these strategies to gain this advantage (e.g., they must learn how to move to attain the desired allocations).
F SUM-FORM AGGREGATORS
Many useful reward functions are sum-form aggregators:
Definition F.1 (Sum-Form Aggregator). task-level aggregator J R. -> R. for task j is sum- form aggregator it can be written as: f(z;) = Em= g(x)), where gj :R + R is differentiable. We say f is (strictly) convex concave if g is (strictly) convex concave, respectively.
Tab. 3 contains examples. When our aggregators have this form, Schur-convexity (concavity) is determined by whether is convex (concave)-a simple computational test. This because of the following known connection between sum-form aggregators and Schur-convexity/concea
Lemma F.1 (Schur Properties of Sum-Form Aggregators (Peajcariaac & Tong, 1992)). Given sum- form task-level aggregator f(x) = > g(xx). the following holds: (i) if g is (strictly) convex, then is (strictly) Schur-convex; and (ii) g (strictly) concave, then f is (strictly) Schur-concave.
16

---

Published as a conference paper at ICLR 2026
This lemma simplifies checking the conditions of our heterogeneity gain results. For example, the following corollary can be used to establish AR for many of the aggregators in Tab.
Corollary F.1 (Convex-Corfe Concave Positive Heterogeneity Gain), Let N, M 2 2. Let [0 Ry0 be non-negative strictly convex function satisfying g(0) = O, and let h Rz0 + T. be stricily concave, increasing function satisfying h((0) = If each task-level aggregator is a strictly convex sum-form aggregator Tý(a;) sum-form aggregator U(y) ΣØ= h(y)), then AR > O.
(==1g(Ta)) and the outer aggregator is strictly concave
Proof of Corollary F.I. We will apply Theorem 3.1 by verifying its conditions:
First, by Lemma F.1, since is strictly convex, the (identical) task-level aggregators T₃(x) =
Em1g(() g(2;) strictly Schur-convex, satisfying condition (i) of Theorem 3.1.
Second, the outer aggregator U (yl,....yMM) is strictly increasing at every coordinate by definition, satisfying condition (ii).
Hence, the conditions of Thm. 3.1 apply. To establish AR > 0, it remains to verify that the optimal allocation is non-trive non-trivial: it distributes effort across at least two tasks. In any admissible homogeneous solution, each of the N agents chooses the same effort-distribution (ci,-.., CM) on
tasks, with E3 Cj = Then task j's reward is Tí N g(c,), so R(A)
Σj=1 M(N g(1)))
The trivial all-agent single-task allocation uses (cj 1, Ck#s 0). Its reward is therefore Reorner = I(N s()) Exzz (NNN g()) h( g(1)) since g(0) 0 and h(0) 0.
Strict concavity implies that i(N N g(1) N N.NNNMg Mg(1)). Hence, agents can attain a better reward by allocating effort to N different tasks rather than single task. This shows that the best solution must use at least two nonzero Cj, completing the proof.
G FORMAL ANALYSIS
G.1 PROOF OF THM. 3.1
Proof of Thm. 3.1. Let Anom be optimal homogeneous allocation (i.e., R(Anom) whose ith row the vector
Rhom )
M
(CI...., CM) with
Σ 1=1
9
=1
Then each column j of Ahom is the uniform vector uj = (G) E RN, Hence the task-level reward is T, (u,), and the overall reward is
R( R(Anom) (UT)) TMr()))).
Because Ej cj = 1, there least one task j with e, > 0. construct heterogeneous allocation Ahet such that each column vy in Abet has the same sum as the corresponding column in Abom-
The total effort allocated to task j can be expressed as [Ne,] + fk. where 0 - fj < 1. First, we assign |Ney agents to allocate effort 1 to task j. for every task j. These agents are all distinct. This leaves with Σ, ʃj N Σ, [Nez] agents that have not allocated any effort yet. Let be the first of those agents. We have agent allocate fi effort to task 1, f2 effort to task 2, and so until we arrive at a task such that fi ...... + fa + 8, for some >> We have allocate fx: to this task k. Then, move to agent + 1, and allocate the remaining fractional efforts in the same manner (and in particular, allocating s effort to task k), until agent + 1 overflows. Then we move to agent i + and on. This ensures that we have allocated N effort in total across the agents, and that every agent's 's effort allocation sums exactly to 1, so is feasible.
Let z, be the jth column of Anet- We note the following fact: any non-uniform vector whose sum is Ne; majorizes the uniform vector uy. Hence, Tz, 2 (,,,), with equality only if x = Uy. This means that if Abet o Ahom. then
17

---

Published as a conference paper at ICLR 2026
R(Abet) = (IT((I))..... Tar(())) > (TT( Tas (uss)) R( (Ahomm).
We note that Ahom Ahet only Ahom is trivial allocation, Aner contains at least one agent allocating effort to some task, and Ahom 's agents only allocate fractional efforts, if it is non-trivial. Otherwise, since (((Ah))) = Rhom, the above inequality implies AR Rhet Rhom >> 0. This
completes the proof.
L
G.2 PROOF OF THM. 3.2
Proof of Thm. 3.2. Let A be an arbitrary feasible allocation, and let Anom be a homogeneous alloca- tion with the same column sums. Concretely, for each column j. define
5j
Tij
and
Uj
(*+
*)
so új is the uniform distribution of total mass sj across N agents. Then construct
N
N
Ahom
which is clearly homogeneous (each row is the same), and respects each column sum 8j. Since Σ, 5j = N, each row sums to hence the allocation feasible. By Schur-concavity of Tj, for each column we have
Ta(a)) S Tj(u)),
unless is uj. In other words, any deviation from the uniform vector with the same sum Σ i= aji = 8j will not increase (a;) under Schur-concavity. Hence for each column j of A, (aj) - (ug), Since is non-decreasing in each coordinate,
R(A)
s U(Ti(U)).......... (ms(us)) R( (((hom)).
This implies AR
G.3 PROOF OF THM. 3.3
Proof of Thm. 3.3. By hypothesis, the components of the task score vector
T(A) = (a:), T2(2)) .... Tas Tar(am))
always sum to C. By strict Schur-convexing the maximum value of U over such vectors is attained precisely at an extreme point the C-simplex, i.e. some permutation of (C, 0,....0), 00. Hence, we seek to find an allocation of efforts, Acorners that causes T(A) to equal this vector.
Let each agent invest all of its effort into task 1. This is the trivial allocation. Then the first column of Acorner is (1, 1,..,,.. T)T and all other columns új are zero. Since task scores sum to C, we get Ti (ai) C, T₃ (a,) 0 for j + 1. By assumption (2), we infer that the vector of task-level scores is indeed (C, O, O).
Notice that each row of Acorner is the same (1, ...., 0), making Acorner homogeneous allocation. Hence, we attained the maximum possible reward R(A) through a homogeneous allocation, implying AR O.
G.4 PROOF OF THM. 3.4
Before proving the statement, let's write the expressions for homogeneous and heterogeneous optima. For each task j. we defined
exp(t (sp()-rts) Tij.
Ty(A) = Σ
Ex exp(t (())
18

---

Published as a conference paper at ICLR 2026
while defining the outer aggregator be
M
exp(T (T(T))T(AA)
((Ti(a))...Ta(((0)) = Σ
Tz(A),
DM exp(r -T(())
where T temperature parameters. In the homogeneous setting, where all agents share the exp (t
same allocation ( therefore have (2(A) Di=1 Dd exp (te,) cj = cj- Thus,
exp(T c2) 1- exp (epp(T (Te))
Rhom
max CE M
Cj.
where M-1 the simplex of all admissible allocations.
In the general heterogeneous setting, each row (ra..... .rass can be different. Then
Tras)
N exp(tris) Téj TA(A)
E exp(tres)
and we choose (AM-1)N maximize
exp(T (AA))
Rhet max
k= exp (A)) (A()).
Keeping these expressions mind, we proceed with the proof of Thm. 3.4. Reminder: assuming N .M 2, want to prove AR(t, T; when S and
((L, N' maxfo(t, N) a(T,N), 0), t>0, 0, 7
1> 0, r 0,
AR(4T;N)
otherwise, where oll, N) = C
Proof Thm. 3.4. When t 0, T3 is Schur-concave 4R 0 by Thm. 3.2. We assume t for the rest the proof.
Homogeneous optimum. If every row of A equals the same allocation N then (A) Cj-
U is Schur-concave for r < 0, and Schur-convex for 7 2 0, hence it is maximized by the uniform distribution in the former case, and by 1-hot vector in the latter case, yielding:
1
T 0,
Phom
max U(c) cEAN-1
N (T,,
(H)
<> 0.
Lower bound on Rhet- The trivial allocation, where every agent works on the same task, produces Resviill = N). The spread allocation, where agent works exclusively task i, makes each column "one-hot": this gives T₃ = (1,, N) for all j. and plugging this into U, we get Rapread = (I,, N). Consequently
N).
Rhet maxfo N). ( N)).
(L)
Combining (H) and (1.) gives the desired lower bound.
19

---

Published as a conference paper at ICLR 2026
Table 1: All nine extreme cases of inner/outer aggregators belonging the set {min, mean, max). In each cell, we show the best possible outcome for Heterogeneous vs, Homogeneous allocations and the resulting AR.
T min
T mean
T max
min
Inner: 2 miny
Inner: 2 2 Σ, ray (avg over
Inner: 2 = max,
Best Rhet, Rnomt must have
Maximize min; Tý: Both Rast.
Outer: picks miny TT. R
push min; 1/M.
Raom must make T. all equal (Tor
Ruet: min, T;
x
best min), so T2 = 1/M.
Rhom: min; 1j 1/M
Ty 1/M.
Outer: min;
1/M
R= I/M.
Outer: min, T3 1/M
= 1/M.
Gap: 37 17 m.
R= 1/M.
Gap:
Gap: 0.
U = meam
Inmer: T3 min; ri = 1/M.
Inner: Ti = N 2, Ti5-
Inner: 73 max,
Outer: simple avg M E, Tj-
Σ, T3
Outer: avg 31 Σ, 7;.
2; T3 M (1/M)
Outer: avg E, Ty.
Rhet: M
R=
Both Rhet. Rhom
I/M.
Hence R
Same Riset. Rhom- W
Gap:
Rhom: sum = 1 = n 1/M.
M
M
AR =
Gap:
Gap:
U = max
Inner: T3 = min; Pij can be made
Inmer: Tj = avg over picks max, T₃. Both Ruat. Bhom can put all effort into one task to get T2 = 1, max, = R =11. 1.
Inner: T; = max; Fia
Outer: picks max, T3-
Outer: picks max, T3
Both Rhet- Rhom can achieve
Same for Rhets Bhom.
Gap: 0.
Gap:
Gap: 0.
Table 2: A "9 extreme cases" table for discrete, one-task-per-agent allocations.
mean
max
min
Inner:
Inner: 12
Inner:
Outer: min; T
Ty +
1, if all agents pick otherwise.
AR [N/M]/N.
Ract LN/M//N. Rhom
Ty Ty
(0,
1,
least agent picks J, agent picks j.
Outer: miny Ty. To get It > 0, must have for every all agents pick all tasks, impossible). Hence Ruat Raom typically, AR O.
Outer: min; Tj.
Heterogeneou chonse distinet tasks. If want miny 1. must pick tasks.
requires N Then R 1. Honogeneous covers only task = min,
M
R
AR 1 iiN
2 M. else 0.
Inmer: Ty only pick j. O,
Inner: 7j 12,1
T3
Summation >;, Tú is number of tasks chusen by all agents. Usually 0 or
Outer: Avernge across tasks: R
agent, else 0.
1 Σn I 3 matter how
Outer: Average across J: is E, Ti. (# of tusks chosen). Heterogencoue can pick up
Outer: Averge
Σ, Tj
R
agents are distributed, Σ =N
This is
R = 1/M, 2
Hence Rhom S AR O.
miniM, N) tasks, so R Homogeneons exactly task = R 1/M.
Ef
AR
min(d,N)-
M
max
Inner: T, 1 only if pick else Outer: max, Ty.
Inner: T3
N,I/N.
Inner: T, T least picks j. else
Outer (7 +oo): max, T, can task, get =
AR = 0.
place all agents
Outer: max, T, 1 agent picks
Then It 1. Same for homogeneous or heterogeneous. AR
j. Even a single task yields It. = 1. So Rhom Rhoe AR
H DERIVING THE {min, mean, max) HETEROGENEITY GAINS IN THE FIG. 2 TABLE
We derive these heterogeneity gain case- Tab. summarizes the derivation for continuous allocations (raj E (0, 1), and Tab. does the same for discrete effort allocations (raj {0, 1)).
20

---

Published as a conference paper at ICLR 2026
I PARAMETRIZED FAMILIES OF AGGREGATORS
The Table in this section illustrates several families of generalized aggregators that the analysis in this paper applies to. The scalar parametrizes each family of aggregators, continuously shifting the aggregators from Schur-concave to Schur-convex.
Table Illustrative families of parametric (and one nonparametric) aggregators fe(z). Changing the real parameter 1. can switch between Schur-convex and Schur-concave behaviors (on nonnegative inputs), or control how strongly the aggregator favors "peaked" vs. "uniform" distributions. As t + +oo or 1 > 0, many reduce to well-known extremes such as max, min, or the arithmetic mean.
Name
Definition
Schur Property & Limits
Power-Sum
Strictly Schur-conver for t >> I.
fi(x) = Σ (a:)',
24 2.0 t>0
Strietly Schur-concave for 0 <
< 1.
At f 1, it is linear (both Schur-
convex and Schur-concave).
Undefined at 0 if any 2; = 0, though one can extend limits.
Power-Mean
Strietly Schur-conver for
Mi(a) (M Σ (+:)) [(:)"
2,
Strietly Schur-concave for
Reduces arithmetic mean
1. As converges 24;
converges -
min,
Log-Sum-Exp (LSE)
NV
Strictly Schur-comver for >>
(.),())
In c
t
Strictly Schur-concave for t < O.
1=1
As + oo, approaches max, 2n as -c, approaches min, Zi--
Softmax Aggregator
Strietly Schur-comex for
e 12
Softmax,(1))
Σ
R4 tER
Strictly Schur-concave O.
Σ crg
1-1
> co, converges to max, wi: -0, converges
min, Zz.
O, each weight is t. Softmaxo(1)) = E, on.
ADDITIONAL RESULTS IN THE MULNT-AGENT MULTI-TASK MATRIX GAME
We report further details and results on the heterogeneity gains obtained the multi-agent multi-task matrix game.
J.1 GAME FORMULATION
In Tab. 4 provide example of the pay-off matrix in this game for N -M 3.
J.2 = M 2
We train with N 2, M = for 100 training iterations (each consisting of 60,000 frames). We report the results for the continuous case in Tab. 5 and for the discrete case in Tab, The evolution of the heterogeneity gains training is shown in Fig. 6.
21

---

Published as a conference paper at ICLR 2026
Table Example of Aulti-Agent Multi-Task matrix game for N M 3. Agents choose their
actions = (ray) and receive global reward R( A) - 4 M
N
Taj-
Tasks
Agents
P11
T12
713
2
P21
722
723
P31
F32
133
Table Heterogeneity gain AR E Rogag1 of the continuous matrix game with = = 2. The results match the theoretical analysis in the Table of Fig. We report mean and standard deviation after 6 million training frames over 9 different random seeds.
T Mean
Min
Max
Min
-0.002 + 0.002
0.000 + 0.003
0.504 + 0.007
U
Mean -0.002 + 0.002
0.000 + 0.000
0.496 + 0.001
Max -0.003 = 0.002
-0.001 + 0.001
0.003 = 0.001
Table 6: Heterogeneity gain AR E Roças1 of the discrete matrix game with N = M 2. The results match the theoretical analysis in Fig. 2. We report mean and standard deviation after 6 million training frames over 9 different random seeds.
T
Min
Mean
Max
Min
0.0 0.0
0.5 + 0.0
U
Mean
0.0 + 0.0
0.0 + 0.0
0.5 + 0.0
Max
0.0 0.0
0.0 0.0
0.0 - 0.0
Discrete
Contimuous
1.0
U = min, T min
Hetergeneity gain
U mean, T min max, T min U = min, T mean U mean, T- mean U max, T
0.5
0.5
min, T max U mean, T max U- max, T max
0.5
0.5
Number of fremes (Millions)
Number of fromes (Millions)
Figure 6: Heterogeneity gain for the discrete and continuous matrix games with N M 2 over training iterations. We report mean and standard deviation after 6 million training frames over different random seeds. The final results match the theoretical predictions in Fig.
J.3 N = M = 4
In the case N = M = 4, the evolution of the heterogeneity gains during training is shown in Fig. 3. further report the final obtained gains for the continuous case in Tab. and for the discrete case in Tab. 8.
J.4 N - AND N = 12, =
To test scalability, further report results for the discrete matrix game with N M 8 in Tab. 9, N = 11, -M 2 in Tab. 10. In the case of = 11, 2, results match the predictions of Table (discrete rewards) precisely.
22

---

Published as a conference paper at ICLR 2026
Table 7: Heterogeneity gain AR R of the continuous matrix game with N The results match the theoretical analysis in Fig. 2. We report mean and standard deviation after 12 million training frames over 9 different random seeds.
T Mean
Min
Max
Min
-0.003 + 0.002
0.000 + 0.001
0.690 = 0.026
U
Mean 0.002 + 0.000
0.000 + 0.000
0.722 = 0.002
Max 0.037 + 0.023
-0.009 + 0.005
0.029 + 0.006
Table 8: Heterogeneity gain AR Rugaş1 of the discrete matrix game with N M The results match the theoretical analysis in the Table of Fig. 2. We report mean and standard deviation after 12 million training frames over 9 different random seeds.
T Mean
Min
Max
Min
0.0 0.0
0.25 = 0.0
1.0 0.0
U
Mean
0.0 0.0
0.0 + 0.0
0.75 + 0.0
Max
0.0 0.0
0.0 + 0.0
0.0 + 0.0
For N = M = 8, we match the predictions precisely except for two cells which have negative empirical AR. As discussed in Sec. 5, due the larger agent scale and action dimensionality (8 agents and 8 tasks), for some reward structures the empirical heterogeneity gain is negative, since the neurally heterogeneous agents we train require more time to discover the optimal policy, hence lag behind their homogeneous counterparts under fixed training budget. Increasing the number of training steps steers the negative AR values O. This nuance aside, what is important that the results still follow our theory exactly in terms of which reward structures yield positive heterogeneity gain. For such reward structures, our theory also precisely predicts the numerical value of AR (Fig. 2)
Table 9: Heterogeneity gain AR E Rogasa of the discrete matrix game with N M = 8. We report mean and standard deviation after 12 million training frames over 8 different random seeds.
T Mean
Min
Max
Min
0.0 0.0
0.0
0.125 + 0.0
1.0 + 0.0
U Mean
0.094 + 0.068
0.0 0.0
0.875 + 0.0
Max
-0.75 + 0.5
0.0 + 0.0
0.0 + 0.0
Table 10: Heterogeneity gain AR E Ragast of the discrete matrix game with N = 11, = 2. We report mean and standard deviation after 12 million training frames over different random seeds. The results match the predictions of Table 2 (discrete rewards) precisely.
T Mean
Min
Max
Min
0.0 0.0 0.0
0.454545 ~ 5/11 0.0
1.0
U Mean
00.094 0004=000 0.0
0.0 0.0
0.5 + 0.0
Max
0.75 = 0.5
0.0 0.0
0.0 0.0
K MULTI-GOAL-CAPTURE
In Multi-goal-cappe agents need to navigate to goals. Each agent observes the relative position to the goals, and agent actions are continuous 2D forces that determine their direction of motion. The entries r,, of matrix A' at time / represent the local reward of agent i towards goal j. computed as
23

---

Published as a conference paper at ICLR 2026
m.y = (1- M d;g /MM - -1), where di is the distance between agent and goal j. This makes it so that Σ j=1 ri 1 and ri > O. At each step, the agents receive the global reward R(A"), with aggregators U, {min, mean, max].
Our results, shown in Fig. 4a and Tab. 11, show that our curvature theory reliably predicts when there a heterogeneity gain (Fig. 2): it is positive only for the concave-convex pairs U min, T max and U mean, 7 = max. The heterogeneity gain is smaller in the latter case because learning dynamies matter: with must steer to the midpoint between the two goals) so homogeneous learners seldom find it, leaving room for heterogeneous policies to excel (see App. K). By contrast, U mcan, T max admits continuum of good homogeneous policies, which homogeneous teams execute more easily, For U = max, T min and U max, T = mean, the theoretical AR O, yet the empirical heterogeneity gap negative (Fig. 4a). This occurs because the reward peaks only when all agents coordinate on the same goal. Neurally heterogencous teams learn this uniform behavior slower than homogeneous teams, they underperform within the fixed training budget. Additional training would close this gap to AR 0.
min, T max the best homogeneous policy is unique (every agent
Table II: Heterogeneity gain at the end of training for the Multi-goal-capture experiments in Fig. 4a. We report mean and standard deviation after 30 million training frames over 9 different random seeds.
T
Min
Mean
Max
Min
0.0 + 0.02
0.01 + 0.02
0.21 + 0.03
U
Mean
-0.03 0.01
0.0 = 0.0
0.12 + 0.09
Max
- 0.08 + 0.06
-0.07 = 0.08
0.0 = 0.0
In Fig. we juxtapose two representative N M 2 roll-outs of the MULTI-GOAL- CAPTURE environment for homogeneous teams (top row) and heterogeneous teams (bottom row) when U min, T = max. Consistent with the discussion in Sec. 5, homogeneous agents steer to the geometric midpoint between the two goals, producing almost overlapping paths-this is suboptimal, as they cannot cover both goals. On the other hand, heterogeneous agents exaggerate their differences, taking sharply diverging trajectories and ensuring one goal each.
L 2v2 TAG EXPERIMENTS
The goal of our tag experiment is to showcase that our theoretical results, which predict the value of AR based the curvature of the aggregators, hold for discrete, sparse rewards. Specifically, our results for discrete efforts in Fig. 2 predict that only (U,T) = (min, max), (min, mean), (mean, max) will have positive heterogeneity gain, with (min, max) maximizing the gain. We show in Fig. 4b and Tab. 12 that this holds in 2v2 tag, despite the fact that this is challenging, embodied, long- horizon, whereas our formal results are for instantaneous allocation games*. Note that this is a highly interpretable result: (min, max) means that agents are only awarded when both escapers are caught, incentivizing heterogeneous strategies where chaser agents split their behaviour so that the chasing efforts rfy are equally distributed between both escapers. Fig. 8 visualizes the trajectories learned by agents trained under this (min, max) reward structure, showing distinct emergent pursuit strategies emerging depending on whether the agents are neurally heterogeneous or neurally homogeneous.
To test the robustness of our predictions to greater number of agents, we also ran an experiment with 11 agents: 8 chasers and 3 escapers. We trained the agents over 500 episodes of length 1000 each (this episode length is more than twice as long our other experiments. indicating that our predictions are stable over longer horizons). Note that we still collect the same amount of total frames (30M) reduce the number of environments sampled in parallel.
*The gain for (mean, max) is small compared to the other two aggregator combinations, but still positive 4 R Re 0.37. This is also significantly higher than aggregator combinations for which we predict A R is not positive, the largest of which attained ÁR < 0.01.
24

---

Published as a conference paper at ICLR 2026
(a) Homogeneous run
(b) Homogeneous run
(c) Heterogeneous
(d) Heterogeneous run
Figure 7: Behaviour under the concave-convex aggregator U min, T = max. Each dot is an agent position; line segments indicate instantaneous velocity; green squares mark goal locations. Homogeneous policies collapse to single "mid-point" route, while heterogencous policies split and follow distinct paths to cover both goals. Note how the heterogeneous agents exaggerate the difference in their trajectories, rather than head directly to the goal: this is an outcome of the reward structure, which encourages maximal diversity.
Due to the high computational cost associated with these experiments, we selected 2 aggregator combinations for which Table 2 predicts positive AR: (U, 7) (min, mean) and (U, T) (min, max), and we further selected three "control" combinations for which we expect AR < 0. The results, shown Figure (discrete rewards), illustrate that our predictions still hold in this case. The final AR values are (U min, T = mean) = +.6411 (U min, T max) 0.01440.084 (U = mean, T = mean) = 096 + 0.053, (U = mean, T = max) -0.990 + 1.025, and (U max, T max)
3.709 + 2.491.
is important to note that, while our theoretical predictions regarding when AR > 0 hold for any number of agents N, they specifically tell what happens when agents allocate their efforts optimally. The empirical heterogeneity gain AR crucially depends on the quality of strategy agents learn in practice, which in turn also depends the transition dynamics of the environment, complicating things. When the number of agents or complexity of the task is very large, we may eventually witness divergence between the empirical heterogeneity gain and the theoretical predictions, for this reason. This does not indicate a problem with our theoretical predictions. Rather, it is a limitation of learning-based methods; using better methods in environments which enable optimal effort allocation will lead to empirical results that more closely mirror our predictions.
M FOOTBALL EXPERIMENTS
In some environments, the reward structure might not entirely follow the double-gend generalized- aggregator structure study in this work, but at least some part of the reward function might
25

---

Published as a conference paper at ICLR 2026
Figure 8: Comparison of homogeneous (top row) and heterogeneous (bottom row) 2v2 tag policies for chaser agents, trained with the reward structure U min, max across different initializations. Every column shows the trajectory of the homogeneous (top) and heterogeneous (bottom) policies. (Note that trajectories here are smoothened; agents don't go over obstacles in actual execution). The heterogeneous policies prioritize capturing both agents, whereas the homogeneous policies focus on just one, In the U min, max setting, this gives heterogeneous agents greater reward, hence AR 0. Please find more visualizations
website.
U=mean, T=mean
U=min, T=mean U=max, T=max
U=mean, T=max
U=min, T=max
Heterogeneigy gain
2.5
0.0
-2.5
-5.0
-7.5
100
200
300
400
500
Number of frames (Millions)
Figure Heterogeneity gain for 8v3 Tag throughout training. We report mean and standard deviation for 30 million training frames over 8 random seeds. Positive aggregator combinations are colored and follow the predictions of Table 2 for discrete rewards. Final gain values are reported in the text of Appendix L.
obey this structure. In our study of the VMAS football scenario (Bettini al., 2022), ask what happens when this is the case.
Foothall is a complex, embodied, long-horizon scenario that requires the agents to learn low-level dribbling skills as well as high-level strategy purely from a shared cooperative reward. The VMAS
Table 12:
Heterogeneity gain at the end of training for the Tag experiments in Fig. 4b. We report mean and standard deviation after million training frames over different random seeds.
T
Min
Mean
Max
Min
0.0
0.0
1.68 + 0.24
3.47 + 0.23
U
Mean
-0.03 + 0.04
-0.02 + 0.06
0.36 + 1.44
Max
-0.02 0.09
-0.11 0.18
-0.30 + 0.15
26

---

Published as a conference paper at ICLR 2026
Table 13: Football heterogeneity gains across different reward formulations. Results obtained after
500 training iterations of 240k frames each (6 seeds). Opponent speed annealed from 0% to 100%.
Reward
AR
Theory AR > 0? Reward meaning
U min, T max
1.76 + 0.72
Yes
One agent should attend the ball, the other the opponent; reward capped by the less-covered task. Similar to (min, max), but reward is dictated by average task perfor- mance.
mean, max
1.18 + 0.11
Yes
U mean.
== mean
0.01 + 0.07
No
Agents should attend both the op- ponent and the ball. least one agent should attend least the opponent or the ball.
U min, T min
-0.08 + 0.73
No
scenario uses reward shaping to enable agents to learn such behaviors. We add reward structure UTT(r1, r(), T(riz r52)) on top of this and ask how this affects heterogeneity.
In our experimental scenario, two learning agents spawn at midfield. A ball is located between them and the goal to the right; heuristic defender spawns to their left and chases the ball. Agents receive a global reward that increases when the ball moves toward the goal and the defender stays away from it. Additionally, we reuse the reward structure from our Multi Multi-Goal-Can Goal-Capture define rewards for two tasks: tackling the ball, and tackling the opponent.
The effort at time is:
1 (1
d /d
where dij is distance of agent i to ball or opponent). The global reward given to all agents is then computed as:
Rd UTT r2)) . (ri22,222) + [[(dhalt.goa
chatt.goat)
(d 11
ball dopp.baal )
where 3 weighs the global football reward.
Since this reward structure does not follow theory entirely, we ask whether, when U are, respectively, strictly Schur-concave and strictly Schur-convex, we should expect AR >> 0 as in our other scenarios. We test this for U min, T max and U mean, T max. To control for the possibility that football is heterogeneous "by default", we also test the aggregator combinations U mean, T mean and
min, min as controls.
We report heterogeneity gains after training homogeneous and heterogeneous policies in Tab. 13. This shows that our curvature test predicts the heterogeneity gain of different reward structures, despite only being component in the overall reward structure. This insight is important, as it may indicative our thcoretical insights (the curvature test) may extend beyond environments that strictly follow task allocation setting. However, this is just possible scenario, and such, this possibility requires further verification in future work.
The resulting policies are reported in Fig. 10 with videos here.
N OBSERVARILITYYHHEEERRRGEEEE
TRADE-OFF
In this Appendix, we crystallize the relationship between environment observability and empirical heterogeneity gains. It is well known that neurally homogeneous agents (i.e., sharing the same parameters) can achieve behavioral heterogeneity by conditioning their actions on diverse input contexts (behavioral typing). This can be achieved by naively appending the agent index to its observation (Gupta et al., 2017a) or by providing relevant observations that allows the agents to infer their role (Bettini et al., 2023). Behavioral typing is impossible in matrix games, as these games observationless. However, it is possible in more complex games, such scenario. We augment agents the positive gain scenario (U = min, T = max) with a range sensor, providing proximity readings for other agents within radius. In Fig. 11, show that the
Multi-goal capp-ce
27

---

Published as a conference paper at ICLR 2026
Figure 10: Left: Results of training heterogeneous policy on VMAS Football where agents are trained with U min, T max aggregators. Our learning agents are drawn in blue; the heuristic opponent in red; and the ball in black. The learning agents split their efforts, tackling both the ball and the opponent. Right: Results of training homogeneous policy. Agents are unable to split their efforts, so either they both tackle the ball, or both tackle the opponent. This results in lower reward, hence AR > These policies are visualized on our website.
Sensing tange 0.35
Seneing range 0.1
Semsing trage 0.2
Sereing runge
0.3
Heterogenelly gain
0.2
0.1
0.0
0.1
20
25
30
Number of frames (Millions)
Figure 11: Gain w.r.t. observability when U min,
Figure 12: Heterogeneity gain for Multi-goal-capturr throughout training when the agents' obser- vation range is gradually increased from to 0.35 over random seeds (4 random seeds suffice as this phenomenon is established in the literature (Bettini al., 2023), and only wish show its emergence in the context of our work.)
heterogeneity gain decreases as the agent visibility increases (higher sensing radius). This is because, with a higher range, homogeneous agents can sense each other and coordinate to pursue different goals. This result highlights the tight interdependence between the heterogeneity gain and agents' observations.
O PARAMETRIZED DEC-POMDP
Parametrized Decentralized Partially Observable Markov Decision Process (PDec-POMDP) is defined as tuple
(N, SN (Othev fot) (AthiE R², T .7, 80)
where A' {1, .I....,n) n denotes the set of agents, is the state space, and, 1OtheN and {Ar) the observation and action spaces, with O; C S, Vi W. Further, {of and R2 the agent observation and reward functions, such that of S + O,, and, R : S x [Athen + R. T is the stochastic state transition model, defined T S x [Ai + 4S, which outputs the probability (s' (af)seN s(+1) of transitioning to state t+1 S given the current state s S and actions
28

---

Published as a conference paper at ICLR 2026
{aj kev. with of E A, y is the discount factor. Finally, s E S is the initial environment state. PDec-POMDP represents a set of traditional PoMDPS (Olichoek et al., 2016), where the observation function, the transition function, the reward function, and the initial state conditioned on parameters 0. This formalism is similar to the concepts of Underspecified POMDP (Dennis et al., 2020) and contextual MDP (Modi et al., 2018).
Agents are equipped with (possibly stochastic) policies n. (a, which compute an action given a local observation. Their objective maximize the discounted return:
G (n) B
ERR (s' (s', 8t T a'), m.(o))) o =f
where म, a are the vectors of agents' policies and actions. G (T) represents the expected sum of discounted rewards starting in state si and following policy и in PDec-POMDP parametrized by 6.
P STABILITY OF BILEVEL OPTIMIZATION IN HETGPS
The Heterogeneity Gain Parameter Search (HerGPS) algorithm employs a bilevel optimization framework to simultancously optimize environment parameters and agent policies. This appendix discusses the structure of this optimization problem, its convergence properties, practical stability, and alternatives for con-differentiable environments.
P.1 HETGPS AS STACKELBERG GAME
HetGPS can be formalized as a Stackelherg game, a hierarchical optimization problem involving a leader and followers (Simaan & Cruz, 1973). In our setting:
1. The Leader is the environment designer (the outer loop of HetGPS), which aims to maximize the heterogeneity gain H HetGain" by adjusting the environment parameters O.
2. The Followers are the homogeneous and heterogeneous multi-agent teams (the inner loop), which aim to maximize their respective returns G (x) by optimizing their policies What and Thom within the environment defined by 0.
The leader's objective function (the heterogeneity gain) depends on the optimized policies of the followers, which, in turn, depend on the parameters set by the leader. Formally, the objective is:
max [G (The (0)) G (T (0))
where ग (0) represents the optimized policies for a given environment configuration 0.
P.2 CONVERGENCE AND STABILITY
Generally speaking, multi-agent reinforcement learning is a concurrent optimization process that faces non-stationarity agents constantly adapt
another's 's evolving policies (Zhang al., 2019). HetGPS extends this challenge as agents must also adapt to a changing environment. Consequently, formal convergence guarantees global optimum remain an open question with regards to HetGPS in particular, but also MARL algorithms in general. However, recent theoretical work in environment co-design has established conditions under which convergence of bilevel optimization processes similar to HetGPS to local optima can be guaranteed, such as requiring sufficient smoothness of the environment dynamics and policy updates (Gao et al., 2024).
Despite the theoretical complexities inherent in multi-agent learning and bilevel optimization, as shown in Sec. 5 and App. Q, HetGPS demonstrates strong empirical stability even under adversarial initializations. This stability is expected, as it mirrors the practical success observed in related co- design and automated curriculum learning literature (Dennis et al., 2020; Gao et al., 2024). However, emphasize that empirical stability is not guarantee of convergence. Although did not identify such cases ourselves, it is possible that in some scenarios, HctGPS will oscillate rather than converge.
P.3 ADVANTAGE OF DIFFERENTIABLE SIMULATION
In our experiments, HetGPS increased training time by roughly 25% compared to training agents in environment with fixed reward structure. Hence, it is highly efficient and does not impose much
29

---

Published as a conference paper at ICLR 2026
overhead. A key strength contributing to the efficiency of HetGPS is its use of differentiable simulation (e.g., VMAS (Bettini et al., 2022)). By leveraging backpropagation through the entire rollout, HetGPS computes the exact gradient VeHetGain' This approach is more sample-efficien than alternative methods that treat the environment design as a separate RI. problem (e.g., PAIRED (Dennis et al., 2020) Designer-RI. RI. (Gao et al., 2024; Amir al., 2025)). Such methods rely on high-variance policy gradient estimates for the outer loop and often struggle with exploration inefficiency (Parker- Holder et al., 2021; Jiang et al., 2021; Xu et al., 2022). By utilizing exact gradients, HetGPS mitigates these issues.
P.4 HANDLING NON-DIFFERENTIALE ENVIRONMENTS
A requirement for the implementation of HetGPS presented in Alg. 1 is access to differentiable simulator. When the environment involves mmn-smooth physics or black-box components, direct backpropagation is infeasible.
In such cases, the environment optimization step (Line of Alg. 1) can replaced with the gradient- free methods mentioned above, such as PAIRED (Dennis et al., 2020), the bilevel method from (Gao et al., 2024), or evolutionary strategies (Stanley et al., 2019). While these methods have empirically been shown to be stable and robust in other co-design settings, and may enable the extension of HetGPS to non-differentiable settings, they typically require more samples and may exhibit more noise compared to the direct backpropagation approach utilized in this work.
Q HETGPS UNDER ADVERSARIAL INITIAL CONDITIONS
To evaluate the robustness of HetGPS to initialization, we repeated the Softmax experiment in Multi-GoallCapture (Fig. 5a) with adverse initialization. We initialized the outer aggregator with 5 (making it convex) and the inner aggregator T' with r = -5 (making it concave), which is the opposite the concave-convex configuration predicted by theory to maximize heterogeneity gain.
As shown in Table 14, HetGPS successfully overcomes the adverse initialization and converges towards the theoretically optimal parameters (large positive for T, large negative 7 for U).
Table 14: Convergence of HetGPS parameters (r) in the Softmax Multi-Goal-Ce Goal-Capture experiment starting from adverse initialization (Tr -5, To = 5). Mean and standard deviation reported over seeds.
Frames (M)
0
50
75
100
7 of T (Inner Agg.)
-5.0 + 0.0
13.32 + 2.15
18.88 + 3.96
22.95
5.71
7 of U (Outer Agg.)
5.0 - 0.0
-10.26 + 1.70
- -14.59 + 2.24
-17.16 2.43
R BEST PRACTICES, LIMITATIONS, AND OPEN QUESTIONS
We list number of limitations, open questions, and possible extensions. We then discuss best practices: where and how should our theoretical results be applied? What parameters should HetGPS optimize?
R.1 THEORETICAL SCOPE
Beyond fask-allocation RL domains. The benchmark domains we study and the additional settings covered in App. E all fit into our abstract task-allocation framework: we can interpret agents' state, such as goal proximity Multi multi-goallccature, or whether they captured an escaping agent in tag, abstractly what enables us to make predictions about these environments. Although our framework is quite general, and accommodates environments that one might not traditionally view "task allocation" (such as football and tag), several notable multi-agent RL domains, e.g., multi-robot manipulation, might not be representable within this framework. Our heterogeneity analysis does not directly apply to these settings, and extending our results to them is important for getting a complete picture of the benefits of heterogeneity.
"efforts" rij and represent the reward in terms of such efforts. This
30

---

Published as a conference paper at ICLR 2026
R.2 ALGORITHMIC ASSUMPTIONS
Differentiable simulation. HetGPS requires Va (Ir). hence a simulator that is end-to-end differentiable and tractable to back-propagate through. We assume differentiability mainly for considerations of training efficiency. However, many realistic environments still rely on non-smooth physics black-box generators, requiring us modify HetGPS for these settings. We note that there are good, established methods for learning environment parameters in non- differentiable settings (at the cost of efficiency/inereased noise). We discuss these in detail in App. P. However, we did not test such variants of HetGPS, and leave these extensions to future work.
R.3 OPEN QUESTIONS
i. What is the connection between the transition function and heterogeneity? Our analysis is reward-centric: the curvature criterion reasons only about the team reward. In a Dec-POMDP, however, heterogeneity can be beneficial purely because agents are constrained by state transi- tions. When do state transition dynamics benefit heterogeneity?
ii Learning dynamics vs. reward structure. The theory predicts whether a given reward structure enables an advantage to heterogeneous teams, not whether a particular learning algorithm will learn in response to it. This is connected to the difference between neural and behavioral heterogeneity that emphasize throughout the paper. Our experiments suggest, empirically, that neurally heterogeneous agents will, in practice, learn to exploit heterogeneous reward structures (i.e., be behaviorally heterogeneous); but a formal link be established between our reward structure insights and what reward the learning dynamics converge to in practice?
Tackling these challenges would sharpen our understanding when and how diversity should be engineered in cooperative multi-agent learning.
R.4 SCOPE OF THE CURVATURE ANALYSIS
The theoretical framework presented in Section 2 provides precise characterization of the hetero- geneity gain based on the curvature of reward aggregators. We provide an extended discussion of when we expect our theoretical predictions can, and cannot, be applied for deciding whether to heterogeneous or homogeneous agent policies.
Symmetry and Monotonicity, Our analysis hinges on the definition of generalized aggregators as symmetric and coordinate-wise non-decreasing. These assumptions are appropriate for studying emergent behavioral specialization among capability-identical agents. Symmetry ensures that agents (and tasks) are interchangeable ex-ante, isolating how the reward structure drives specialization. If symmetry is violated (e.g., due to inherently heterogeneous agent capabilities), heterogeneity is often trivially necessary. Monotonicity ensures rational cooperative setting where increased effort does not decrease the reward.
Effort Constraints. We define the feasible effort space over the closed unit simplex (where efforts sum < 1). However, because both the inner aggregators Tý and the outer aggregator U are non- decreasing, any optimal
homogeneous or heterogeneous. will necessarily saturate the budget constraint (efforts sum 1). Therefore, our analysis focuses on this efficient frontier without loss of generality.
Constant-Sum Task Score Constraints. It is crucial to clarify that the assumption of constant-sum task scores (E (a,) = C) is specific only to Theorem 3.3, enabling the use of majorization to analyze the outer aggregator U. Theorems 3.1 and 3.2, and our sum-form aggregator analysis (App. F), do not rely this.
When this assumption is violated, the analysis of AR involves a trade-off between the distribution of scores (influenced by curvature) and their total magnitude. Despite this complexity, our empirical findings (Section 5) suggest that the curvature analysis remains a robust heuristic for predicting the heterogeneity gain even when the task scores are variable-sum.
31

---

Published as a conference paper at ICLR 2026
Reward functions that do not precisely follow the theory. Our football experiments show that even when only part the reward function adheres to our curvature theory (c.g., is a sum R(A) = Rí (A) + (A) where R is concave-convex and R2 is function with unclear curvature), our theoretical results may still predict the heterogeneity gain. We make no formal claims about the robustness of our predictions in such scenarios, but it is valuable to keep in mind that even if the entire reward function does not perfectly follow the theory, it may still be worthwhile to see what the concave-coneex curvature test says about the part of it that does.
32


Reviews:
[{"review_id": "rNtkhc12nm", "reviewer": "Reviewer_JKoM", "summary": "This paper investigates aggregation functions in a multi-task/multi-objective multi-agent RL setting, particularly answering the question of for which aggregations heterogeneous behavior is advantageous over homogeneous behavior.\nA theoretical analysis shows that this is connected to the schur-convexity of the aggregation functions.\nExperiments confirm the theoretical analysis.\nFurther, a method to optimize environment parameters such that they favor heterogenity is proposed and validated.", "questions": "*  See question about assumption in weaknesses\n * In HetGPS, it is not entirely clear to me why an approach that alternates between policy and environment improvement was chosen. Intuitively, it could be posed as an entirely bi-level process, in which the policies are trained from scratch for each environment configuration\n\n\nNitpicks:\n * L71 It may be better to introduce the symbols T and U for agent-wise and team-wise aggregation here already, on a first read the two addition symbols are a bit unclear.\n * L172 Similar issue, the abuse of notation is initially confusing and (in my opinion) unnecessary\n * L177 Introducing the allocations under the close simplex, i.e. allowing for sum < 1, and then excluding this case in L207 seems unnecessary\n * L351 \"continues to be and informative\"\n\nOverall I really enjoyed reading this paper, great work!", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The problem setting is interesting and relevant. The question of whether or not to share parameters in Multi-Agent RL is relevant and the analysis of aggregation functions in this paper provides a useful step towards answering it.\n * The theoretical analysis and its presentation are very clear and well explained\n * The experiments nicely confirm the theoretical predictions.", "weaknesses": "Minor points:\n * The assumption of normalized inner aggregators could be justified better. It's not entirely clear to me whether this is justified in practice", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pEnzIGOBMH", "reviewer": "Reviewer_j8eg", "summary": "This paper provides a theoretical analysis of the heterogeneous vs homogeneous credit assignment in MARL, which provides insights for the reward shaping problem in different MAS tasks. It presents HetGPS to optimize the parameter space of an underspecified MARL environment. The experiments showcase that it can discover new reward regimes to maximize the advantage of heterogeneity.", "questions": "1. What are the conservative bounds $\\Delta R$ when constant-sum is violated?\n2. Will there be any cases where curvature is only a part of the total reward yet remains predictive?\n3. In non-differentiable simulators, how do sample complexity and final performance compare when using score-function/ES estimators?\n4. For non-symmetric or non-monotone aggregators (e.g., capacity/bottleneck constraints), will the results admit first-order approximations or sharp counter-examples?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "It is novel to formulate diverse reward allocation choices to a mathematical curvature question via Schur-convex/concave tools. The theorems/constructive counter-examples are clean with explicit assumptions. The algorithm description and experiment analysis are clearly presented. This work has significance in influencing environment/reward design and architecture choices in MARL.", "weaknesses": "1. Results hinge on symmetry/coordinate-wise monotonicity and near constant-sum task scores. It would be good to tabulate common benchmarks that violate these assumptions and provide bounds or heuristics for the reward difference when constant-sum fails.\n2. Longer-horizon Dec-POMDP dynamics may interact with curvature in nontrivial ways; more systematic ablations or counterexamples would strengthen the claim\n3. Figures all consist of 9 cases, making it difficult to distinguish the lines", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n3HF8UxQAd", "reviewer": "Reviewer_M2TT", "summary": "This paper addresses the critical and previously unresolved question of when behavioral heterogeneity is inherently beneficial in cooperative multi-agent task allocation problems. The authors provide a principled theoretical answer by demonstrating that the potential advantage of specialized policies is determined by the curvature of the global reward function, which is modeled as a double aggregation of agent efforts. Specifically, positive heterogeneity gain is predicted when the inner, task-level aggregator is Schur-convex and the outer, team-level aggregator is Schur-concave. To validate and extend these insights to complex, time-extended environments, the paper introduces HetGPS (Heterogeneity Gain Parameter Search), a gradient-based bilevel optimization algorithm. HetGPS efficiently searches the parameter space of rewards and successfully rediscovers the theoretically optimal reward regimes in various MARL settings, thereby connecting the abstract theoretical predictions directly to reward design in practical environments5. The results ultimately offer clear criteria for diagnosing and designing missions where agent diversity is essential for maximizing team performance.", "questions": "1. The two issues mentioned in the Weaknesses section.\n2. The curves in Figure 4 overlap significantly, making them difficult to distinguish clearly.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow. The author provide sufficient supplementary material, making the conclusions of this paper clearer and more convincing.\n2. This paper provides a rigorous, formal theory for predicting when behavioral heterogeneity is advantageous in multi-agent task allocation problems. This theoretical framework, based on the curvature of reward aggregation operators (Schur-convexity/concavity), moves the selection of diversity from ad-hoc heuristics to a principled design dimension.\n3. The introduction of Heterogeneity Gain Parameter Search (HetGPS) is a significant algorithmic contribution. This gradient-based bilevel optimization method efficiently searches the reward parameter space to find configurations that maximize or minimize the empirical heterogeneity gain.\n4. The extensive experiments, ranging from abstract matrix games to complex embodied MARL scenarios (Multi-goal-capture, Tag, Football), successfully demonstrate that the theoretical predictions derived from reward curvature reliably transfer to long-horizon settings. HetGPS further validates the theory by automatically discovering the predicted optimal reward regimes.", "weaknesses": "1. The core theoretical criterion for heterogeneity gain is based solely on the curvature of the reward function (Schur-convexity/concavity). This analysis is inherently restricted to the reward structure and does not formally integrate the complexity of environment dynamics.\n2. The high efficiency and tractability of the HetGPS algorithm fundamentally rely on the assumption of an end-to-end differentiable simulator. This is required to compute the exact environment gradients via backpropagation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "93BV9i4O4n", "reviewer": "Reviewer_icAF", "summary": "This paper presents a principled framework for understanding when and why behavioral diversity among cooperative agents leads to improved collective performance. The authors introduce the notion of heterogeneity gain, defined as the performance difference between heterogeneous and homogeneous teams, and formally analyze it within a general two-level reward aggregation model. Using majorization theory and Schur-convexity analysis, they prove that the curvature of the inner and outer aggregation functions determines whether diversity enhances or hinders performance — specifically, concave-outer and convex-inner structures favor heterogeneity. Building on this theoretical foundation, the paper proposes HetGPS (Heterogeneity Gain Parameter Search), a differentiable environment co-design algorithm that discovers reward parameterizations maximizing or minimizing heterogeneity gain through bilevel optimization. Empirical studies across analytic matrix games and embodied MARL tasks (multi-goal capture, tag, and football) validate the theory, showing that HetGPS consistently rediscovers curvature conditions predicted to reward diverse behaviors. The work provides a unifying explanation for when diversity benefits cooperative learning and establishes a new paradigm linking reward curvature, environment design, and emergent specialization in multi-agent systems.", "questions": "> Please answer the following questions:\n\n1. The theory presumes identical agents differing only in behavior (i.e., “behavioral heterogeneity”). What if agents differ in capacity, observation space, or action bounds? Would Schur-convexity still capture heterogeneity gain?\n2. The method performs bilevel optimization: inner MARL loop + outer gradient update of environment parameters. Does the paper analyze or guarantee convergence, or could gradient coupling cause oscillations?\n3. HetGPS successfully rediscovers concave-outer/convex-inner curvature. Would it also succeed if reward functions were implemented via neural networks instead of analytic forms?\n\n> The possible suggestions:\n\nA prior work [1] also found that the reward structure (even encoding the same goal) in a real-world problem could impact the performance of MARL algorithms a lot, though it does not consider the multi-task scenarios. This can be used as an example to motivate the research goal of this paper.\n\n[1] Wang, Jianhong, Wangkun Xu, Yunjie Gu, Wenbin Song, and Tim C. Green. \"Multi-agent reinforcement learning for active voltage control on power distribution networks.\" _Advances in neural information processing systems_ 34 (2021): 3271-3284.\n\nThe global reward structure that aggregates reward functions embedding different subtasks/roles is highly relevant to payoff allocations/credit assignment. Especially, in prior work MARL algorithms with Shapley values [2] also demonstrate that agents with heterogenous behaviors is corresponding to different payoffs assigned by Shapley values. This paper aims to automatically search for a design of local rewards which is an reverse process against the prior work, that design local rewards inspired by cooperative game theory leading to heterogeneous behaviors. Thus, this relevant prior work is encouraged to be discussed in related work.\n\n[2] Wang, Jianhong, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. \"Shapley Q-value: A local reward approach to solve global reward games.\" In _Proceedings of the AAAI conference on artificial intelligence_, vol. 34, no. 05, pp. 7285-7292. 2020.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a mathematically precise metric $\\Delta R = R_{\\text{het}} - R_{\\text{hom}}$​ to quantify when heterogeneous (specialized) teams outperform homogeneous (identical) teams. It proves that the sign of ΔR depends solely on the Schur-convexity or concavity of the inner and outer reward aggregators: (1) Schur-convex inner operator leads to heterogeneity gain; (2) Schur-concave inner operator leads to no gain; (3) Schur-convex outer operator (under constant-sum normalization) leads to no gain. This gives a simple convexity test for when diversity helps — a clear theoretical advance over heuristic assumptions in prior MARL work.\n2. This paper provides closed-form and bounded results for Softmax, Power-Sum, and {min, mean, max} families, creating a general mathematical map of reward structures that promote or suppress diversity.\n3. A new gradient-based environment co-design algorithm that directly optimizes environment parameters to maximize or minimize $\\Delta R$: (1) It operates via differentiable simulators (back-propagates through environment); (2) It avoids inefficiencies and instability of RL-based environment design (e.g., PAIRED); (3) It can either promote or suppress heterogeneity by switching gradient ascent/descent. The algorithm alternates MARL policy training and environment updates efficiently — roughly 25 % overhead — and robustly rediscovering the theoretical curvature configurations.\n4. Tests across (i) analytical matrix games, (ii) embodied long-horizon MARL tasks (Multi-Goal Capture, 2v2 Tag, Football). All experiments confirm theoretical predictions: **concave-outer + convex-inner** reward structures yield the largest heterogeneity gains. The algorithm autonomously learns the same curvature conditions predicted by theory (inner convex, outer concave) for both Softmax and Power-Sum parameterizations — a strong consistency check.\n5. This paper links convex analysis and majorization theory to concrete MARL reward design, turning diversity from a heuristic into a controllable design variable. Also, it provides a principled answer to an open question in cooperative MARL — under what reward structures does behavioral diversity outperform homogeneity?\n6. The contribution of this paper is applicable beyond RL to any cooperative optimization setting expressible as nested aggregations (e.g., task allocation, team composition, distributed robotics).\n7. Complete code and YAML configurations provided; all mathematical proofs and assumptions detailed in appendices. Figures (e.g., Fig. 2–5) clearly demonstrate the alignment between theoretical curvature analysis and empirical $\\Delta R$ outcomes. Writing is logically structured, connecting intuition, theory, and experiment in a coherent flow.", "weaknesses": "1. While elegant, the use of Schur-convexity assumes symmetric and differentiable reward functions. Many practical rewards in MARL are asymmetric, piecewise, or sparse — outside the smooth function classes covered by majorization theory.\n2. Though claimed to be “25% higher,” the method still requires dual policy training (heterogeneous vs homogeneous teams) and outer-loop environment gradient updates. The bilevel optimization may become prohibitively expensive for large-scale, high-dimensional MARL tasks.\n3. Empirical validation is confined to simple matrix games and small-scale MARL benchmarks (Multi-goal Capture, 2v2 Tag, Football mini-games). There are no large-scale or high-dimensional tasks (e.g., SMACv2, MPE with >10 agents, or real robotic control) to demonstrate robustness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)