Correlated Policy Optimization in Multi-Agent Subteams
Authors: Dingyang Chen
Jianing Ye
Zhenyu Zhang
Xiaolong Kuang
Xinyang Shen
Ozalp Ozer
Chongjie Zhang
Qi Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: multi-agent reinforcement learning
multi-agent coordination
Bayesian network
subteam
Primary area: reinforcement learning

Abstract: In cooperative multi-agent reinforcement learning, agents often face scalability challenges due to the exponential growth of the joint action and observation spaces. Inspired by the structure of human teams, we explore subteam-based coordination, where agents are partitioned into fully correlated subgroups with limited inter-group interaction. We formalize this structure using Bayesian networks and propose a class of correlated joint policies induced by directed acyclic graphs . Theoretically, we prove that regularized policy gradient ascent converges to near-optimal policies under a decomposability condition of the environment. Empirically, we introduce a heuristic for dynamically constructing context-aware subteams with limited dependency budgets, and demonstrate that our method outperforms standard baselines across multiple benchmark environments.

Published as a conference paper at ICLR 2026
CORRELATED POLICY OPTIMIZATION IN MULTI-AGENT SUBTEAMS
Dingyang Chen'
Jianing Ye²
Zhenyu Zhang'
Xiaolong Kuang'
Xinyang Shen'
Ozalp Ozer
Chongjie Zhang?
Qi Zhang
@Wocesterr Polytechnic Institute [dingerwa, zhenyuzh, xkkuang, xinyans, ozalpo Paamaoo com (jianing.y. chongjie) qzhang edu
Amazon ?Washington University in St. Louis
ABSTRACT
In cooperative multi-agent reinforcement learning, agents often face scalability challenges due the exponential growth of the joint action and observation spaces. Inspired by the structure of human teams, we explore subteam-bars based coordination, where agents are partitioned into fully correlated subgroups with limited inter-group interaction. We formalize this structure using Bayesian net- works and propose a class of correlated joint policies induced by directed acyclic graphs Theoretically, we prove that regularized policy gradient ascent converges to near-optimal policies under decomposability condition the environment. Empirically, we introduce a heuristic for dynamically constructing context-aware subteams with limited dependency budgets, and demonstrate that our method out- performs standard baselines across multiple benchmark environments.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) enables autonomous agents jointly opti- mize a common objective and has been applied to domains such as traffic control (Chu et al., 2019), multi-robot coordination (Corke al., 2005), and power grid management (Callaway & Hiskens, 2010). In many real-world scenarios, humans naturally organize into subteams, groups that exhibit tight internal coordination and limited external interaction, allowing for specialization and reduced communication complexity. Inspired by this, we explore how agents in cooperative MARL can also benefit from structured subteams that induce localized coordination and scalable learning.
Forming subteams reduces the effective dimensionality of the joint action and observation spaces within each group, alleviating the curse of dimensionality that plagues centralized coordination. Moreover, many tasks exhibit weak interdependencies across certain agent clusters, motivating the design of policies that encourage strong intra- intra-group correlations while ignoring unnecessary global entanglements. For instance, in distributed cearch-and-reset rescue mission, drones surveying separate regions need strong coordination within each team but limited communication across distant ones.
To model such structured correlations, employ Bayesian networks (BNs), where joint policy is factorized according to a directed acyclic graph (DAG) over agents. Agents within the same subteam fully connected in the DAG, enabling expressive, correlated policies. Across subteams, are introduced, effectively enforcing conditional independence. This structure allows us to capture meaningful dependencies without incurring the full complexity of unstructured joint policies. Our contributions are as follows:
edges
As warm-up, we extend Chen & Zhang (2023) by establishing convergence rate for tabular softmax BN policy gradient ascent under any fixed DAG, strengthening their asymptotic results.
Our main theoretical results focus subclass of BNs where the agents be partitioned into subteams, where agents select actions in a fully correlated manner within subteam and inde- pendently in different subteams. Under decomposability condition the reward and transition

---

Published as a conference paper at ICLR 2026
functions (subject to bounded errors), prove that for such BNs regularized policy gradient cent converges to a policy with bounded suboptimality. The bound hinges on the decomposition emrors and the sizes of the subteams.
Finally, we propose heuristic to construct context-aware DAGs dynamically from local ob- servations with a limit on the number of edges, relaxing the assumptions such as oracle value functions and global observability. We integrate this with deep multi-agent reinforcement learn- ing algorithms and demonstrate that our method outperforms the slate-of-the-e across several benchmark environments.
RELATED WORK
Product policies in MARL. MARL algorithms often adopt produet policies, where the joint pol- icy is represented
the product of agents' individual policies (Kuba et al., 2022; Yu et al., 2021; Lowe et al., 2017; Zhong et al., 2024; Foerster et al., 2018; Liu et al., 2024; Egorov & Shpilman, 2022: Li et al., 2024). This factorization is widespread in MARL due to its scalability and the abil- ity to execute policies without communication at runtime. Despite their empirical success, policy gradient-based optimization methods for product policies are generally not guaranteed to converge to the global optimum (Ye et al., 2023). Most existing theoretical results focus on convergence to Nash equilibria, which is weaker solution concept than global optimality (Leonardos et al., 2021; Chen et al., 2022; Ding et al., 2022; Fox et al., 2022; Sun et al., 2023).
Correlated policies via Bayesian networks. To address the suboptimality of product policies within the policy gradient framework, number of works have proposed optimizing correlated joint policies, since deeper correlation indicates a stronger expressiveness of the joint policy class, and thus often a better optimality guarantee. One popular approach for representing a correlated joint policy is to use Bayesian networks (BNs) (Heckerman, 2020). These methods (Ye et al., 2023; Chen & Zhang, 2023; Ruan et al., 2022; Christianos et al., 2023) represent the joint policy as directed acyclic graph (DAG), allowing the joint policy to be factored into a product of several correlated conditional distributions. However, suboptimality persists whenever the BN is not fully connected.
Value-based methods in Markoy Team Problems. There are also a number of works that have studied value-based methods in Markov Team Problems such as Littman (2001); Donmez et al. (2025); Sunehag et al. (2018); Rashid et al. (2018); Wang et al. (2020a). These studies typically treat the agent as a whole, tackling the scalability issue by the implicit decomposability of their value functions. In contrast, Phan et al. (2021a); Zang et al. (2023); Wang et al. (2020c;b); Kapoor al. (2025) develop methods to explicitly group agents into subteams to learn a uncorrelated or factorized value function among subteams for better scalability. A more similar concept among value-based methods is the coordination graph (Guestrin et al., 2002; Böhmer et al., 2020; Li al., 2020; Yang et al., 2022; Kang et al., 2022; Wang et al., 2022), which factorizes the joint value function according to a graph structure that encodes the coordination relationships among agents. Nonetheless, the optimality of these approaches is affected by the incompleteness of the function class and the imperfect approximation of the TD target under the imposed graph structure (Fioretto al., 2016).
Structural assumptions and sparse correlations. For a policy with weak correlation (e.g., a sparse BN), the optimality of the algorithm may rely on certain assumptions about the environment. There is relatively limited theoretical work in this area. Some early research has demonstrated that the transitions between agents exhibit some independence, certain algorithms (such as dynamic programming and independent learning) can achieve global optimality (Lauer & Riedmiller, 2004; Becker et al., 2004; Zhang & Lesser, 2011) I). Wang et al. (2021) and Dou et al. (2022) prove the convergence of the value-based algorithm VDN (Sunehag et al., 201 8) under the assumption that the environment admits a decomposable structure. Building upon similar decomposability assumptions in Dou et al. (2022), our work extends the theoretical guarantees to the class of policy gradient based methods with BN represented correlated policies. To our best knowledge, this is the first work that establishes optimality guarantees for BN policies without requiring full independence among agents.
2

---

Published as a conference paper at ICLR 2026
3 PRELIMINARIES
We consider a cooperative Markov game (MG) defined by tuple (N, S,A, pi), involving N agents indexed by E .V fI...... N). The game consists of a state space S, a joint tion space A = A x ... x A with A being the action space of agent i, a transition function S A R. and initial state dis-
P S x A + A(S), shared team reward function tribution E A(S). Here, A(A) denotes the set of probability distributions over X. The game progresses in discrete time steps with next states and rewards generated from P and r, respec- tively. The discounted cumulative reward from time step t is denoted as R& == D00 7'rtt with r1 == r(s,, Qt). With full observability, meaning each agent observes the global state s E S, a general joint policy
S + A(A) maps states to distributions over the joint ac- tion space, inducing its value function (=+))) :al)::==e+t.:..... -x.+11o::4....-7 [R.] the action-value function (s,, at) == Eec+ aere [Re]s,, az). and its (unnormalized) discounted state visitation mea- sure (s) == Exg-y 1===0 "Pr" (st = S|so]]]- The objective is to optimize the joint policy to maximize its value with respect to the initial state distribution, i.e., max= V=(u)) == B (V~ (so)]- Denote the optimal value as V.(n) = max, V=()). We say i is c-optimal if its suboptimality
subopt(a) = V.(u) V (u)= S.
Given the exponential growth of A with N, the commonly used joint policy subclass is the product policy, = (T² ................................ TT) ) + A(A', where joint policy is factored as product of local policies n² + ((A'), such that ((ass) = ILe H' [a'ls). well known that there exists a deterministic policy (and hence product policy) with zero suboptimality.
Although the best product policy does not introduce suboptimality, the restriction of conditional independence among agents' actions restricts the expressiveness of the joint policy, which creates difficulties for optimizing the joint policy and often results in suboptimal behavior (Ye et al., 2023).
Chen & Zhang (2023) extended beyond product policies by incorporating correlation in the local policies through a Bayesian network (BN) among the agents. A BN is represented by a directed acyclic graph (DAG) G EN, with agents N being the vertices and & S [i...) i,j N,i i + j} being the set of directed edges. The parents of an agent i are denoted by p = {i (i, E E} with their actions denoted as a E A ~
XjEPiA'. DAG G induces a joint policy S - A(A), where each agent i's local policy T. S x AP + (AA')
TG = (... is conditioned on both the global state and the actions of its parents, and therefore joint action T'y("'ls:
a (a² w is selected as (a)s)) = Ie a²"). It is clear that BN policies define a continuum: TH reduces to product policy when G has no edges and is as expressive as general joint policies when G is dense. We define the equilibrium gap of a BN policy as:
gap'(Fc) == max,g V#g.Ta: (1) Vxa (H), gap(Tc) := maxseN (TG)
Here, the deviating BN policy (4'g TT') is consistent with मa in terms of the underlying G. We say BN policy TG is an e-approximate equilibrium if gap(TG) S e. Note this equilibrium notion resembles standard ones like Nash equilibrium (Nash, 1951) and coarse correlated equilibrium (Au- mann, 1987), but they are different: Nash equilibrium only applies to product policies; the coarse correlated equilibrium applies to general policies but does not allow the deviating local policy to condition on any other agent's action.
Shorthand notations. When the underlying DAG is clear from the context, we will drop subscript G and write BN policy as n. For a subset M C V of the agents and its complement -M, a joint action is decomposed as a (a a -M). The conditionals of policy æ given some a .M -M is defined as π (a-Mls a -M) = IT M a-- aaM1ss) //)///M Eam Ta a MM])) with the corresponding action-value function Q= (s, MM) := E, (a (Q, a a-M]]. Let Pi : := Ut'( denote the set of agent and its parents.
WARM-UP: CONVERGENCE OF TABULAR BN POLICY GRADIENT ASCENT
Prior work (Chen & Zhang, 2023) established the asymptotic convergence of tabular softmax BN policy gradient ascent under any fixed DAG. To provide formality and as a warm-up, we here extend their result get finteetime convergence rate with the help of log barrier regularizer.
3

---

Published as a conference paper at ICLR 2026
Fixing DAG G, consider parameterizing local policies of BN policy in the tabular softmax manner from the global state and parent actions as in Chen & Zhang (2023), i.e., for each agent we have its policy parameter and the induced softmax policy as
0¹ (s, aa) C 8 & S,a EA" EA). T (a'1s,a*) x exp (0'(s,a" .a')
(1)
and the BN policy is therefore parameterized as Ty = (TT), TgN)
To provide a finite-time convergence guarantee, we optimize a log barrier regularized objective in similar fashion to Agarwal et al. (2021) for the single-agent counterpart:
(+) = Vo( - A Σ E wuiif EEN
KL (Unif Th (-18, [)]
SXAPi
where Vi and Qa are shorthands for Vr, and QT in this paper; À > O is the regularization parame- ter; Unifx is the uniform distribution over X: KL(:,-) :) denotes the KL divergence. The log barrier regularization, i.e., the KL divergence with respect the uniform cetion-selection distribution, applied to each agent's policy independently. The standard gradient ascent for Lx in (2) is
0+ 02 (O.) Vi E
where 17 is a fixed stepsize. The explicit regularized policy gradient form shown in Lemma 1. Lemma (Proof in A.2). For the BN policy parameterized as in Equation (1), have:
30 (s, a aaa""a" a²) 1-2 N (8, A a
@Lx(0)
a,," " "bb(s, ,a') |S|APi
T (a'
[AA
where di (s, a
a = dif (s) E.r pi ...1))) as, .a') = Qo(s, Pt) Qa(s,
The gradient form in Lemma enables extend the single-agent finite-time convergence guaran- tees (Agarwal et al., 2021) to BN joint policies under the same assumptions used in the convergence results for product policies (Zhang et al., 2022; Chen al., 2022), which we state below and are required in all of the theoretical results in this paper.
Assumption 1. For any joint policy a and any state of the Markov game, d,{(s) >> 0.
Assumption I is standard (e.g., Agarwal et al. (2021): Zhang al. (2024; 2022); Chen & Zhang (2023)) and holds if the initial-state distribution satisfies uus) > 0 for all E S, ensuring every state reachable with positive probability under any policy.
Assumption 2. The reward function is bounded in the range [0, 1]. such that the value function is bounded as Vs, n,0 0 < V*(8)= & 1/(1 1 7)
Let M == max,, / quantify the maximum pointwise ratio between state visitation
measures induced by any two policies. By Assumption 1, M is well-defined and finite. This constant appears in Lemma that extends the results in the single-agent setting (Agarwal et al., 2021) and the multi-agent setting with product policies (Zhang et al., 2022; Chen et al., 2022), stating that, with the log barrier, approximate first-order stationary points are approximate equilibria.
Lemma (Proof A.3). f is such that (0)]l < S/ max; [A')), BN policy mo is 2AM -aproxximaie equilibrium.
With Lemma 2, we establish the convergence rate stated in Theorem 1.
Theorem (Proof in A.4). For any e > 0, under updates (3) beginning with 0g and using S.v 2xM being an upper bound on the smoothness of B3 with 3x ك- ST
ZNI and stepsize
L, (f), we have min <T gap(TT,) I whenever
256NN M 8 max; L T
32N M|S max; 1A91
(4)
(1 22
7)c
The key idea in our proof is to reinterpret parent actions Pi as part of the state for agent i, treating the tuple (s, a Pi) as an augmented state. Under this formulation, the joint distribution d a²") becomes the state visitation measure the augmented state space. This transformation brings
4

---

Published as a conference paper at ICLR 2026
the gradient ascent updates (3) into close alignment with those for the product policy (Zhang al., 2022: Chen et al., 2022), enabling a natural generalization of the analysis to the BN policy setting.
Although Theorem establishes convergence rate to approximate equilibrium, which is the strongest type of result one can expect for general cooperative MGs, it may still yield arbitrarily suboptimal policies. To address this, next characterize subclass of MGs where optimality can be guaranteed via regularized policy gradient ascent, along with an approximation where the suboptimality is explicitly quantified by deviations from the defining conditions for this subclass.
CONVERGENCE TO HEAR-OPTIMALITY VIA SUBTEAMS DECOMPOSITION
If the transition and reward functions of cooperative MG can be decomposed into components associated with disjoint subsets of agents, then strong dependencies exist among the agents within each subset while agents in different subsets exhibit limited dependencies. In such a case, the BN policy only preserves full correlation in the local policies within each subset (but not between the subsets), turns out that the regularized policy gradient ascent can achieve near-optimal coordina- tion, as we will establish in this section. As a first step, we define our notion of subteam:
Definition 1 (Subteam). Given DAG G
-N, E) and subset of its vertices (i.e., agents) C C.N. The subgraph of G induced by C is denoted as Ge &C) with &c := {(i. i.j E C, (1, E}. Subset C is subteam in G if. for every pair of distinct i, E C, either (i.5) or (j,t) is in &c.
By Definition 1, agents in subteam are fully connected by directed edges, subject to the the acyelic- ity constraint. For example, any single agent is subteam; any pair of two connected agents is subteam. Intuitively, for a BN policy with G being the underlying DAG, the local policies in a sub- team of G are fully correlated in the sense that the BN policy is expressive enough to represent any joint action distribution of the agents in the subteam. We will partition all agents into subteams for a BN policy, which reasonable when the cooperative MG of interest can be well decomposed by this partition. We define a cooperative MG's decomposability by partition of its agents as follows:
Definition 2 (Decomposition of a cooperative MG by partition of agents). Consider a cooperative MG (N, S, A, P, r, μ)) and a collection of K subsets of agents N,, {C+] being a partition of N, i.e., U Cx = N and Cx CC = 9 V1 S k + k I K. The MG is decomposed by the partition with errors (ep,5r) if its transition functiooonuunctinn P and reward function r can be decomposed as
a(sl(s,a)= = Ex= p* + a)) r(s,u) = ΣK E + (s) (5)
for any s E ES.aE E A and some real-valued functions cp, G,, and (Pk, " hISAKK.
In words, the transition/rewarr function is decomposed into components, one per subset of the par- tition, where each component depends on actions taken by only the agents the corresponding subset. We here make few remarks on Definition 2: 1) We do not impose any regularity assump- tions on pe and p²; especially, p* needs not be a probability measure. 2) Because the errors (Ep, can be arbitrarily chosen, the decomposition of P and R given in Equation (5) is always feasible for any partition {C of NV, as one can simply accommodate the decomposition errors into (CP, G.). As one might expect, our suboptimality guarantee will degrade the errors increase. Let- ting [cp]= := maX (cp(s') |s, a) and |G, := max,,a (8, a)l, we have the following proposition confirming the intuition that finer partitions only introduce larger decomposition errors.
1K' are two partitions of N, and the latter is finer than the former in the sense that, for all 1 S. k' $.'S K', Cy S Ck for some 1 S k S K. If the MG is decomposed by (Cr, KK' with errors (cp, c,),, then the MG can be decomposed by [C K with errors (Ep,er) such that lepl S jépl and |er1 |e.l.
Proposition 1 (Proof in A.7). Suppose {C& and {Cp
We are ready to state the conditions that DAG needs to satisfy for our main theoretical result: Assumption 3. For the cooperative MG of interest equipped with DAG G = (N,E), there is collection of subsets {Cx) satisfy the following conditions:
(i) KK is a partition of N; each Cg is subteam in G for all 1 < k < K;
(ii) The MG is decomposed by [C& kmm with errors (Ep,6r)
5

---

Published as a conference paper at ICLR 2026
(iii) For any 1 S k + K I K, & does not have any edge fi. E Ck and j E Cy-
Conditions (i) and (ii) are directly taken from Definitions and Condition (iii) excludes any edge between any two subsets. While any additional edges increase the expressiveness of the induced BN policy and therefore should ease the policy optimization, (iii) is technically required in our proof. Specifically, a key step in Lemma 3's proof is to upper bound the gain of d over the subteam base- line V (s), which derived from a telescoping sum that would fail if subteams are not independent, as shown in the proof in Appendix A.5.
In the remainder of this section, we consider the regularized policy gradient ascent (3) to optimize the tabular softmax BN policy induced by a DAG that satisfies the conditions in Assumption 3 for given cooperative MG. The following lemma states that, in this case, the approxmiate equilibrium guarantee in Lemma 2 can be strengthened into a near-optimality one. For case of exposition, define g(CC 1K ) := E 1 2|ca1 - K, where g(-) is a real-valued function of an arbitrary collection of sets {C its output value depends on the number and the sizes of the sets.
Lemma 3 (Proof in A.5). Suppose BN policy To is parameterized in the tabular softmax manner as in Equation (1) with the underlying DAG satisfying all conditions in Assumption 3 with partition {Ca } k- If0 is such that Lx) 2 ( |AA max: [At(), To is
(2XMg((C.) 2K
|e-l (1->) + >ISller!)) optimal.
(6)
Compared with Lemma 2, the requirement on @ being an approximate stationary point remains the same, yet the bound of the equilibrium gap is strengthen to a suboptimality bound in (6) consisting of two terms. The first term can be made arbitrarily small by choosing sufficiently small regular- ization parameter A like in Lemma 2 but also quantifies the impact of the partition with function g()), the value of which becomes smaller the partition gets finer as stated in the following proposition: Proposition 2 (Proof in A.8). Suppose [C&) and {Cr, sition We have a( (Ck, >x= S )
{Cgrl = satisfy the same conditions in Propo-
The second term captures the impact of the decomposition errors, which increases as the decom- position errors become larger as stated in Proposition 1. Therefore, the suboptimality bound in (6) reveals a tradeoff when choosing the fineness/courseness of the decomposition.
In a similar manner, the guarantee of finite-time convergence an approximate equilibrium in Theorem can be strengthened into a near-optimality one as stated below.
Theorem 2 (Proof in A.6). Suppose the underlying DAG G of BN policy no satisfies the same conditions as in Lemma 3. For any >> O. under updates (3) beginning with Og = 0 and using
A SM- AMM--gl (((( and n) S 3x (Bx as in Theorem 1), we have
minggr subopt(Ta)
E 2K
(1-7)
|t-l + sSslee!))
(1-7)²)
(7)
whenever
T2
256N 25S max, 1A'1 0((C*) + S2NM|S||A max, LA' <(1-))
g( (((C))
(8)
2(1--)"
The second term in (7) matches the second term of (6) from Lemma 3, which quantifies the asymp- totic suboptimal bias caused by the decomposition errors. In the extreme case of K = 1, all agents form a single subteam, making the decomposition error-free (lell = |erl = 0) and ensuring e- optimality. A larger K tries to impose stronger independence assumptions across the subteams, often resulting in larger lepl and |e+| and therefore a larger asymptotic suboptimal bias. Regarding the convergence rate of (8), the dominating term is the first one that scales with 1/e², which matches the first term of (4) from Theorem 1 up to the factor of g((C2) K )² that favors finer partitions into subteams according to Proposition 2. Increasing K can create finer partitions and speed up the con- vergence. However, this speedup comes at the cost of potentially larger decomposition errors and thus greater suboptimality. This reveals a fundamental trade-off in subteams design.
Proof sketch. We here provide the key steps in our proof of Theorem 2. 1) Value function de- composition: By Definition 2, the transition function and reward function decompose by the sub- teams { with additive errors ep and Ey. Consequently, the global value functions admit ad- ditive decompositions: Qo(s,a) = Ek= (8 (x( + Eq. (8, Vo(s) = Σk- V2 ev, (s),

---

Published as a conference paper at ICLR 2026
where emror terms <Q. and év, accumulate from errors (c), 2) Bounding subteam advantage: From Lemma I, the regularized policy gradient provides a bound on local advantage A a²,, .a)) Consider a topological ordering over the agents in subteam Cs. For agents i and j such that directly precedes in the ordering, we have a = a due to the full connectivity in C. and no cross-subtcam connectivity, implying Qo a =E á PP- (- ++) Qo(s, "e,,aaaaaa P+)]=
Applying this in the reverse topological order and combining with the local advan- tage bound yields bound on Qo(s, as,, - Vo(s). 3) Bounding Q (s, (,,, (s):: Apply the value function decomposition from step 1 to separate Qo(s, d and Vo(s) into components de- pendent on a and a CCc Their difference cancels out unrelated components, producing a bound on (*, a VV) up to approximation errors that can be bounded using errors (e), 4) Lemma 3 and the finite-time convergence: Summing the bounds from the previous step across all subteams gives bound on Qo(s, a) Vo(s). which leads to the suboptimality guarantee stated in Lemma Using the same convergence argument as in Theorem 1, we choose a sufficiently small stepsize 17 for gradient ascent. Since (0) is smooth, we can guarantee that after enough iterations, the gradient norm becomes small enough to invoke Lemma 3. With a proper choice of X, this leads to the statement in Theorem 2.
Qo(s, a
EMPIRICAL RESULTS
Our empirical study progresses in two parts. In Section 6.1, we begin with experiments that exactly adhere to the setting in Section 5, providing an empirical analysis of our theoretical results. Next, informed by the theoretical insights, in Section 6.2 propose a practical heuristic that constructs subteams that potentially induce low decomposition errors given an edge budget, which is integrated into and improves state-of-ther ahrt deep MARL algorithms.
6.1 TABULAR EXACT GRADIENT ASCENT WITH FIXED DAG IN THE COORDINATION GAME
We consider an N-agent extension of the two-player Coordination Game in Zhang et al. (2024) with
N (2,3, 5). Each agent has a binary local state and action space, S AA' = {0, 1}. The reward function encourages agents to align their local states, with preference for global configurations containing more agents in state O when majority counts are tied. The local state transition of agent depends only on its own action: P(s Ola' = 0) = 1-6, P(s* 0ja² 1) e, where = 0.05.
We intentionally choose this minimal and didactic domain, so that we are able to afford the re- quirements of the theoretical results: exact gradient ascent for the tabular softmax BN policy pa- rameterization with a fixed DAG. We compare the following DAG topologies: 1) the product DAG with no edges; 2) the full DAG where every pair of agents is connected, so it is K = subteam including all agents; 3) DAGs with K subteams and have no edges between any two subteams are labeled with the subteam sizes, e.g., 2+3 for N = 5 agents; 4) the 1ine DAG where each agent i < N is connected to agent + 1, as considered in prior work (Böhmer et al., 2020; Chen & Zhang, 2023). Note that all DAGS satisfy Assumption except for the 1 line DAG.
Figure in the appendix confirms that all DAGS converge equilibria, in agreement with Theorem 1. We assess the op- timality gap across subteam partitions in Figure 1: For N 2, 5, policies with coarser partitions (i.e., fewer, larger sub- teams) consistently achieve higher final performance. For example, with N = 5, full 1 performs similarly to 1+4 and are the best, followed by 2+3, and finally the product. For N = 3, full still performs the best, while line and product perform similarly, with 1+2 2 slightly worse.
Table 1: Fitted decomposition errors.
DAG
|erl
[rr
product
2.04c-01
1.26c+00
2
full 3.57c-03
2,38c-07
1+2 2.94e-01
1.50e+00
product
3.96c-01
2.00c+00
full
2.21c-05
2.79c-09
1+4
3.38e-01
1.44e+00
To explain this ordering, we fit {P* r Jk=1 with three-layer multilayer perceptrons by minimizing the decomposition er- rors when regressed to the transition and reward functions
2+3
4,80c-01
2.38c+00
product full
6.03e-01
1.56c+00
7.13e-08
3.73e-08
(cf. Definition 2). Table 1 presents the fitted errors across
subteam partitions. Notably, the partitions that yield smaller decomposition emror consistently cor-
7

---

Published as a conference paper at ICLR 2026
Coordination Game, N=2
Coordination Game, Nw3
Coardination Game, Nw5
0.6
Nomalized suboptimaity
0.5-
product
0.5
line
line
0.4
0.4
product
1+2
0.4
1+4
0.3-
0.3
0.3
product
0.2
0.1
0.1
0.1
0.0
10"
10
10"
10
10"
0.0
10"
10
10
10
10
0.0
16a
10
10'
107
10"
Iterations
Figure Results of tabular softmax BN policy gradient ascent under various DAG topologies. Averaged over 50 seeds, with shaded areas showing standard enror; normalized suboptimality at iteration is defined Vo, (u)/V.(1)) and initial policy 0o ~ (0,
respond to petter-performe policies for most cases, which aligns with Theorem The only ex- ception is N 3, where 1+2 has smaller errors product, but the product performs slightly better. possible reason is that the additional correlation introduced by 1+2 may not yet be significant enough to yield performance gain over product. Meanwhile, product, with fewer parameters, may be easier to optimize and thus achieves better performance in this particular case.
6.2 PRACTICAL METHIOSS
We have been focusing on exact gradient updates of (3) to optimize BN policies with fixed DAGs. Further, while our results so far justify partitions that induce low decomposition errors, finding such partitions is non-trivial. These issues motivate to introduce below heuristic approach that dynamically constructs subteams in a way that potentially induces low decomposition errors given edge budget. This method can be easily integrated into deep MARL algorithms for practical use.
Dependency-based subteams construction. Given limit of most B edges, our heuristic method constructs a DAG, along with a collection of subteams in the DAG that satisfies the con- ditions in Assumption given a priori based on domain knowledge that roughly quantify the dependency between any pair of agents. Initialized with singleton subteams with no edges, the core idea iteratively merge two subteams C, C' that maximize the average pair-wise dependency score between the agents in the two subteams: d(C,C") == शলा Liec,jEc' diz. The chosen two subteams are merged by adding edges between them, and the merging will repeat until reaching edge limit B, as outlined Algorithm 1 in the appendix. Because merging larger subteams needs more edges, the averaging encourages efficiently use of the edge budget. The dependency scores can change dynamically, e.g., based on the state/episode information, minimize decomposition errors in context-aware manner.
The construction guided by dependency scores, [djJ) which are
6.2.1 BN POLICY WITH DYNAMIC DAG IN DEEP MULTI- ACTOR-CRITIC
For practical usage, we integrate the BN policy as the actor into deep multi-agent actor-critic algo- rithms such as MAPPO (Yu et al., 2022) and MADDPG (Lowe et al., 2017). During training, parent actions are detached from the computation graph to prevent backpropagation, which we find ensures proper credit assignment and stabilizes training. handle the variable number of parent actions duced by the dynamic DAG, we construct fixed-length input vector of size N EJEN IA*), where the actions of non-parent agents are zero-pades pero-padded. This design enables consistent input formatting across different DAG topologies and supports efficient batch processing. The implementation details are provided Appendix
Environments and their dependency score. For the Coordination Game, we treat each agent's local binary state its ID position, enabling natural way compute pairwise dependency scores based on positional proximity. We consider two more environments. Aloha from Wang et al. (2022) involves 10 agents arranged in 2 grid, each maintaining message queue and chooses whether
8

---

Published as a conference paper at ICLR 2026
Coordination Game, N=5
Aloha, N=10
Prey, N=
Narmalizet suboplimailyy
0.5
product
5
random heuristic
Reward
Reward
0.3-
0
2
0.2
-100
-200
0.0
0.5
1.0
1.5
2.0
2 Timesteps
3
Timesteps
1e5
Timesteps
1e5
1e5
Figure 2: Results of integrating dynamic decomposition with MAPPOMMADDPG Averaged over 60, 60, and 10 seeds for Coordination Game, Aloha, and Predator-Prey. respectively, with shaded areas showing standard error.
to transmit each timestep. With probability 0.6, new message added each queue at every step. A successful, collision-free transmission yields global reward of 0.1, while collision incurs a shared penalty of -00. We use Manhattan distances between the agents to define their dependency scores. Predator-Prey from Li al. (2020) has N = 15 controllable predators and multiple uncon- trollable preys moving in a 2D space. The environment introduces additional challenges compared to the previous ones, including stochastic initial positions and higher coordination complexity due to continuous movement. The dependency scores we define again rely on predators' spatial locations.
Base algorithms, DAGs. We select MAPPO as the base algorithm for Coordination Game and Aloha they in- volve discrete action spaces. Tredator-Prey involves con- tinuous action spaces, pare four types of DAG topologies: full and product as described previously, the dynamic DAG constructed via our heurist ic approach, and the random DAG. For fair comparison, heurist. istristi and random are con- strained under the same edge budget B with B 4, 10, 50 for Coordination Game, Aloha, and Predator- Prey, respectively.
Warehouse, N=16
adopt MADDPG. We
20-
Reward
10:
QTRAN
VAST (meta-learming)
VAST (heuristic)
-10-
0.0
0.5
1.0
1.5
le6
Results. As shown in Figure 2, our heuristic achieves the highest performance in all three environ- ments. In Coordination Game, the performance is ordered as heuristic x full random & product. Aloha, while the four methods are comparable by end of training, heuriste Prey, heurist i is still best while full 1. becomes the worst, with random comparable to product.
Battle, N-40
50
Reward
25
and full clearly learns fastest.
-25
6.2.2 VALUE FACTORIZATION
PER AGENT SURGROUPS CENTRALIZED TRAINING
2.0
Timesteps
1e6
We here repurpose our heuristic in Section 6.2 for cen- tralized training methods that involves value factoriza- tion per agent subgroups. Specifically, we consider VAST (Phan et al., 2021b): given partition (C VAST replaces agent-wise values as in traditional works like QTRAN (Son et al., 2019) with subgroup-wise and these values are fed into the mixer to estimate joint value Qx a) as QvAsT(s, a)
Figure 3: Our heuristic for VAST. Aver- aged over 10 and seeds for Warehouse and Battle, respectively, with shaded ar- eas showing standard error.
ones {Q* (s,
(s,at.) ..., QK(s, (x))) where 4h the mixer parameterized by th. Phan al. (2021b)

---

Published as a conference paper at ICLR 2026
consider various methods to determine subgroups { and their meta-learned approach per- forms the best. Our VAST variant instead determines {C*} by our heuristic, with the mixer and learning losses follow the original VAST algorithm. We use the same edge budget in Phan et al. (2021b), which sets K = [ with v = /4. Notably, like QTRAN, VAST falls into the central- ized training and decentralized execution (CTDE) paradigm, which equivalently employs product policies with no inter-agent correlation. This is fundamental difference from the previous sections of this paper.
Environments and their dependency score. Warehouse: N=16 robots move on a grid with shelves and stations. The objective to pick items and deliver them efficiently. Rewards are positive for successful deliveries and include small penalties for wasted moves or blocking. Battle: N=40 units move and attack on a grid against forty opponents. The objective is to win local fights and ad- vance. Rewards positive for damaging or defeating enemies and negative for losses or ineffective actions. In both tasks dependency scores are computed from 2D positions as in Predator-Prey.
Results. Figure shows that, in both Warehouse and Battle, VAST with our heuristic outperforms original VAST with their meta learning approach to determine the subgroups, which is the best variant reported in Phan al. (2021b), and both VAST variants surpass the ungrouped QTRAN.
CONCLUSION
Our theoretical results establish finite-time convergence and suboptimality guarantees for BN policy gradient methods under decomposability assumptions on the reward and transition functions. These results highlight the role of subteam structures in achieving near-optimal coordination. In em- pirical study, we propose heuristic for dynamically constructing context-aware DAGs that induce subteam policies, and demonstrate its effectiveness across tabular and deep MARL benchmarks.
ACKNOWLEDGMENTS
This work was supported by AF Office of Scientific Research (AFOSR) under grant FA9550-25-1- 0318 and with the generous support of the Amazon Research Award program. Qi Zhang acknowl- edges funding support from National Science Foundation (NSF) award 2544947 and NSF CAREER award 2544948.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Robert Aumann. Correlated equilibrium as an expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pp. 1-18, 1987.
Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V Goldman. Solving transition independent decentralized markov decision processes. Journal Artificial Intelligence Research, 02:423-455 2004.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991. PMLR, 2020.
Duncan S Callaway and Ian Hiskens. Achieving controllability of electric loads. Proceedings of the IEEE, 1941):184-199 2010.
Dingyang Chen and Qi Zhang. Context-aware bayesian network actor-critic methods for cooperative multi-agent reinforcement learning. International Conference on Machine Learning, pp. 5327- 5350. PMLR, 2023.
Dingyang Chen, Qi Zhang, and Thinh T. Doan. Convergence and price of anarchy guarantees of the softmax policy gradient in markov potential games, 2022. URL https: //axiiv.. org/ abs/ 2206. 67..
10

---

Published as a conference paper at ICLR 2026
Filippos Christianos, Georgios Papoudakis, and Stefano V Albrecht. Pareto actor-critic for equi- librium selection in multi-agent reinforcement learning. Transactions on Machine Learn- ing Research, 2023. ISSN 2835-8856. URL https: http:::://penreveww.eeeee www.:rrrreew.netfoorml...... forum?id- 3AzqYal 8ah.
Tianshu Chu, Jie Wang, Lara Codecà, and Zhaojian Li. Multi-agent deep reinforcement learning for large-scale traffic signal control. IEEE Transactions on Intelligent Transportation Systems, 21(3): 1086-1095, 2019.
Peter Corke, Ron Peterson, and Daniela Rus. Networked robots: Flying robot navigation using a sensor net. In Robotics research. The eleventh international symposium, pp. 234-243. Springer, 2005.
Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Mihailo Jovanovic. Independent policy gra- dient for large-scale markov potential games: Sharper rates, function approximation, and game- agnostic convergence. In International Conference on Machine Learning, pp. 3166-5220. PMLR, 2022.
Ahmed Said Donmez, Onur Unlu, and Muhammed O. Sayin. Logit-q dynamics for efficient learning in stochastic teams, 2025. URL
wwt.oogg/////.o..o.o.o.........t 2202. 09806.
Zehao Dou, Jakub Grudzien Kuba, and Yaodong Yang. Understanding value decomposition algo- rithms in deep cooperative multi-agent reinforcement learning. ArXiv, abs/2202.04868, 2022. URL httph:ttph..m wtw.:pp..s...nnnn.c..seeeeee.e :ttpaaaroo./ccppp.10:2525755
Vladimir Egorov and Alexei Shpilman. Scalable multi-agent model-based reinforcement learning. In Proceedings of the 2 International Conference on Autonomous Agents and Multiagent Sys- tems, AAMAS '22, pp. 381-390, Richland, SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 171099222.36
Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. Distributed constraint optimization prob- lems and applications: A survey. CoRR, abs/ abs/1602.06337, 2016. URL /ttLtttt/////i..orrr abs / 160.6.222 06347.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Roy Fox, Stephen M. Mcaleer, Will Overman, and Ioannis Panageas. Independent natural pol- icy gradient always converges in markov potential games. In Gustau Camps-Vall Francisco R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Arti- ficial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 4414-4425. PMLR, 28-30 Mar 2022. URL httpsttppt..oo httpc//roeeeieecoocooooooooee.ec .gs.mllss.........mmmmm...mmm.m. mlr. wwwps/eessll.. fox22a html.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML, volume 2, pp. 227-234. Citeseer, 2002.
David Heckerman. A tutorial on learning with bayesian networks. CoRR, abs/2002.00269, 2020. abs/ /atss./222.oo2 00269.
URL pettps://arxive
Yipeng Kang, Tonghan Wang, Qianlan Yang, Xiaoran Wu, and Chongjie Zhang. Non-linear coordi- nation graphs. Advances in Neural Information Processing Systems, 35:25655-25666, 2022.
Aditya Kapoor, Benjamin Freed, Jeff Schneider, and Howie Choset. Assigning credit with partial reward decoupling in multi-agent proximal policy optimization. Reinforcement Learning Journal, 1:380-399, 2025.
Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang. and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. In International Conference on Learning Representations, 2022. URL https: http///pppnpeeeeeeeeeeee net forum? 1d=EcGGFFNTTxcl

---

Published as a conference paper at ICLR 2026
Martin Lauer and Martin Riedmiller. Reinforcement learning for stochastic cooperative multi-agent systems. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1516-1517, 01 2004. doi: A..1009AAMMAS.2004..222
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-geent policy gradient markov potential games. arXiv preprint arXiv:2106.00 01969, 2021.
Mengxian Li, Qi Wang, and Yongjun Xu. Gtde: Grouped training with decentralized execution for multi-agent actor-critic, 2024. URL https:/ /arxivivvvv.////a//aaaaaaaaaavva www.ai.wrgg/a/.aaaaaao/....oo abs 2551 10367.
Sheng Li, Jayesh K. Gupta, Peter Morales, R. Allen, and Mykel J. Kochenderfer. Deep implicit coordination graphs for multi-agent reinforcement learning. In Adaptive Agents and Multi-Agent Systems, 2020. URL https: //ap::///pppp./ semanticscholes org/ Cttp///rrppaaaa
Michael L. Littman. Value-function reinforcement learning in markov games. Cogni-
tive Systems Research. 2(1):55-66, 2001. ISSN 1389-0417.
doi: hyps://doi.org/II/ 10166$11899-41177000001555 URL httpps:/wwwx http////wciieeeerreeeeereeeeeeee com/ science/ atticieepp1/111189111100000
Qihan Liu, Jianing Ye, Xiaoteng Ma, Jun Yang, Bin Liang, and Chongjie Zhang. Efficient multi-
agent reinforcement learning by planning. In The Twelfth International Conference on Learning Representations, 2024. URL https: http://///ppeeeee....oo net www.fformmmiooeeo htte//orrnnnnnnnnnaeeaeee
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-eritic for mixed oopprative-competitie environments. Advances in neural informa- fion processing systems, 30, 2017.
John Nash. Non-cooperative games. Annals Mathematics, 54(2):286-295, 1951.
Thomy Phan, Fabian Ritz, Lenz Belzner, Philipp Altmann, Thomas Gabor, and Claudia Linnhoff- Popien. Vast: Value function factorization with variable agent sub-teams. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neu- ral Information Processing Systems, volume 34, pp. 24018-24032. Curran Associates, Inc., 2021a. URL https::/proceeddiiiii #iLee/c37e7T51155aabb6655
neurips. ce cw/paper_aaeeeeeeeeeeeeeeeeeeeee fareer_fieesseeeeeeeeee ffilee/pappe//221/ Paper.papppeeeee .dd.
Thomy Phan, Fabian Ritz. Lenz Belzner, Philipp Altmann, Thomas Gabor, and Claudia Linnhoff- Popien. VAST: Value function factorization with variable agent sub-teams. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021b. URL httttt::// /ttp:///////eeeeeeeeeeeee net forumm?---yyy
Tabish Rashid, Mikayel Samvelyan. Christian Schröder de Witt, Gregory Farquhar, Jakob N. Fo- erster, and Shimon Whiteson. QMI:: monotonic value function factorisation for deep multi- agent reinforcement learning. CoRR, abs/1805: 11111803.1144 11455, 2018. URL http:://axii.oo
abs/1803, 11.883..11880 11485.
Jingqing Ruan, Yali Du Xuantang Xiong, Dengpeng Xing, Xiyun Li, Linghui Meng, Haifeng Zhang, Jun Wang, and Bo Xu. Gcs: Graph-based coordination strategy for multi-agent rein- forcement learning. arXiv preprint AXXiv2201100655: 2022.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN: Learn- ing to factorize with transformation for cooperative multi-agen reinforcement learning. In Ka- malika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Con- ference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp- 5887-5896. PMLR, 09-15 Jun 2019. URL https: son: 9a html.
httpps:/prooeeiiiii /ttp//peeccccccscceeeepppoe...se wtt.:smlr..prrrr.. pre.s//rrs///////
Youbang Sun, Tao Liu, Ruida Zhou, Panganamala Kumar, and Shahin Shahrampour Provably fast convergence of independent natural policy gradient for markov potential games. In Thirty-evvntth Conference on Neural Information Processing Systems, 2023. URL https: //pp///eepe.....////// net/foruu d=mA JD3.
12

---

Published as a conference paper at ICLR 2026
Peter Sunehag, Guy Lever, Audrumas Gruslys. Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Proceed- ings of the 17th International Conference on Autonomous Agents and MuliiAgent Systems, AA- MAS 18, pp. 2085-2087, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: duplex dueling multi-agent g-learning. CoRR, abs/2008.01062, 2020a. URL https:://axxi..tttt abs/ 2008. 01 62.
Jianhao Wang, Zhizhou Ren, Beining Han, Jianing Ye, and Chongjie Zhang. Towards understanding cooperative multi-agent q-learning with value factorization. Advances in Neural Information Processing Systems, 14:229142222 122-29155, 2021.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforcement learning with emergent roles, 2020b. URL https: aaaaaiivvvorr..aaaaa org/ 22///2203.0000
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose multi-agent tasks, 2020c. URL attpp:://ariiy. abs/2010 0. 0153..
Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang. Context- aware sparse deep coordination graphs. In International Conference on Learning Representations, 2022. URL https: http///ppneeeeeeeeeeeeeeeee
Qianlan Yang, Weijun Dong, Zhizhou Ren, Jianhao Wang, Tonghan Wang, and Chongjie Zhang.
Self-organized polynomial-time coordination graphs. In International Conference Machine Learning, pp. 24963-24979. PMLR, 2022.
Jianing Ye, Chenghao Li, Jianhao Wang. and Chongjic Zhang. Towards global optimality in cooperative marl with the transformation and distillation framework, 2023. URL https:
org. abs 220/22222222 11143.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre M. Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. In Neural Information Processing Systems, 2021. URL https: / /api. iecchllc.. wttp/oorpusD::2220900
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang. Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in neural information processing systems, 555:24611-24622 2022.
Yifan Zang, Jinmin He, Kai Li. Haobo Fu, QIANG FU, Junliang Xing, and Jian Cheng, Automatic grouping for efficient cooperative multi-agent reinforcement learning. In Thirty- Confer- ence on Neural Information Processing Systems, 2023. URL /tttts::/cppnreeeeee net/ Forum?id=CGs TyGJy.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Proceedings of the AAAI conference on artificial intelligence, volume 25, pp. 764-770, 2011.
Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the global conver- gence rates of decentralized softmax gradient play in markov potential games. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neu- ral Information Processing Systems, volume 35, pp. 1923-1935. Curran Associates, Inc., 2022. URL ptttps:://proceedangss neurips ce c// lallpaapp_lllll ftles//aper/2022 http://ccceeccaaao.....22eeeeee.
www.aaapprrcccccecceeeccc .df..
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, con- vergence, and sample complexity. IEEE Transactions on Automatic Control, 2024.
Yifan Zhong, Jakub Grudzien Kuba, Xidong Feng, Siyi Hu, Jiaming Ji, and Yaodong Yang- Heterogeneous-agent reinforcement learning. Journal of Machine Learning Research, 25(32): 1-67, 2024.
13

---

Published as a conference paper at ICLR 2026
A PROOFS
A.1 THE SMOOTHNESS BOUND
8N Lemma 4. (x is 3x-smooth with 3x (1-3)3 +
2AN [8]
Proof. Lemma A.3 in Chen & Zhang (2023) establishes that Vo (1-7)3 smooth. From the per- spective of the augmented state, Lemma D.4 in Agarwal et al. (2021) implies that the regularizer for each agent is 2x 22 -smooth. Therefore, the overall smoothness of Lx (0) is bounded above by [S|AAP
SNV
SN
2A
7)3
S AP
PM
Since E: [APT] S N, we have
2A
2AN
Σ
S
[S]
Thus, 3x [1-7)²
8NN
+
2AN ST
serves as upper bound the smoothness of L (0).
A.2 PROOF OF LEMMA 1
Proof.
a OAΣN E pi Unit sxaPi
(0) 00 (s, aP: a²)
(V)
00 ap', a²)
00' a:i aa))
(1)
(2)
According to Lemma 5.1 in Chen & Zhang (2023),
11)
t (s, (s, a²) (ag A ""'(asss .a)).
By the definition of KI. Divergence,
()) S ai log bogrjji (a
1 A An
E Li=1
s
Unif
EM
[ ||A4|
+ log 14'1
(2)
30'
a4)
A
1
Té (a)(a")s,
SP
1
(Ai
Therefore,
(T)
08 (s, a: o²)
(1) (2)
[Aii] (11)
1 ? 1 (s, a P' a ('b(sa a" ,at)
=z (d(((()s
[
14

---

Published as a conference paper at ICLR 2026
A.3 PROOF OF LEMMA 2
Proof. The proof extends the proof of Theorem 5.2 in Agarwal et al. (2021) by the usage of the multi-agent performance difference lemma (Lemma C.1 in Leonardos al. (2021)).
Similar to the proof of Theorem 5.2 in Agarwal et al. (2021), can establish upper bound on the advantage function (s, a ,a') for any (s, (s,a² ,a') suffices to consider the case where As aP' .a') 2 0 (since when Ab (s, a ,a") < O, any positive number serves as a valid upper bound):
1/(2|S||A| max (441)
3 2//(2|S| (|
(=i
(0)
00 (s, aP a²)
1
dhd (s, a Pi ) a ap') Ab aa))
1 S|||APi|| (A4 (12)
i
Tei (d'ls,
|S|APPI (149) ablaalssa
A
where the last inequality is due Ab, pi ,a") 2 0, and by rearranging get
T (a' (a']ss, (,,aaaa))) ")) 1
2/
Solving (i) for Alss, a", aa),, we have
A/ a Pi .at)
1-7
+ [SPiAPi (1-
A
0 (s, aP))
Kg. (a'ls, aP) (s, a Pi a²)
Tz.
(ails, a {AAi
a
1 7
2/AA" 12/A"/eppt kopt +
(a 20'aa))))
1
dji (8, aP))
S S
2|
2(1 -7)
(Fopt 4/(215)14211444))
(10)
di (8, (pa))))811 (S|(APPP
We are now ready to use the multi-agent performance difference lemma on two BN policies with only agent i's parameters changed. For convenience, denote E.-p< To (aa "ppp"""PP [s) that d (s, a P = d (s) Tp (-1s). Fix an arbitrary agent E N and suppose it deviates from m to an optimal policy Th w.r.t. the corresponding single-agent MDP specified by 0-$, Let 0' 1 be the parameters of any joint policy where only agent i's parameters changed to the optimal
as 7. (-1s) so
15

---

Published as a conference paper at ICLR 2026
policy in the the corresponding single-agent MDP. We have
Ver (n) Vo(u)
E sndz or Barnay (Ao(s.a) (performance difference lemma)
E 1 7 E snoago (.) ()Bap Bapl (11) (1 (11,,Pi)
1
O0(3, ,ā', a - Vo(33)
r Ptrage (18,a
Since : which means Tे (-13) = - (-13), Te Pt ( (-13,a++)
= - (-13, )
1
E sudd (-) Rami wFI (-13) B Rainaja (11 E
Finn (1Baa Qo((,a , P:) Vo(8)
1
1
way 1bb(,,aP) .d) Vo(
E Fawa, of (.)
B Paptway" (-15) Ra
1 y
1
E snad (1) B 0T wag" (11x) 2
(b(3, aa) Vo(3)
1
1
E Rand or (-) B PapSway (11))
a² .²) + @b(5, Vo(3)
1 y
1
1 pari ~ag" (-13) Ab .a)) E s of (.)
Ab(5,
1 7
[06(3, a aP)) vo(3)
+ 1
E swa,,
of B Papiia (-18) ai (11.ar))
1
2(1 A)1
E
snd oor (.)
B gor Nor (-13) 1 B (18,,77))
7
di (3, aP) ]|S||AP1
1
E Saadf of BB (118 1b(5, 2
+ 1 ?
1
2(1 - 7)
E Ssaaft of (-) B Barinao (-13) (-13) d (5, a0 1
1 7
1
2(1 - 7))
E sna, of (1) Parri (11) die ( (-1s) |8
1 7
2X
E 2n ( d
d7 (5) ||
2A
dee (3)
IPP
IPI
2A
2X . < 2AM.
API
max
APP
By definition of c-approximate equilibrium, we know that the BN (joint) policy no (T is a 2XM approxxaie equilibrium.
A.4
PROOF OF THEOREM 1
Proof. Since (0) is Bx -mooohh we have
min (OL)) || < 28x(Lx(0*) - (0o)) <
2mxxx Vmmn))
2,3x
T
T
T(1
-r)
where the second inequality holds because we initialize On = 0. We can choose T large enough such that
2,3
$ A/(2)S) max (4'1)-
T(1 7)
8,9, 3 max: LA
Solving the above inequality we obtain T > to achieve the specified equilibrium-gau of Plugging in À 2M and 8x
By Lemma we should set
X-(1-7)
2
[1>y}3
SN
+
2AN
[S]
16

---

Published as a conference paper at ICLR 2026
have
32M22 812 max; 1A
T
è²(1 7)
256N [5)2 max; 1
64XNM2|S Maxx
max; [
(1 -)
(1-7)e2
256N 126N22251 max, 1 32N M S max; LAY2
7)
(1 (1-7)c
Lemma's (Properties of subteams-decom cooperative MGs). Suppose the underlying DAG of a BN policy x satisfies all conditions in Assumption with partition [Ck]iSkeK decomposing the cooperative MG of interest with errors (Ep,er) Ep). We have
(i) Factorized joint policy. For any state S and joint action E A, the BN policy is factorized into the K subteams T [[lls) IIx (a (s).
(ii) Decomposed value functions. The global action-value function Qr a) and state-value function V (8) are decomposed additively by the subteams as
as (5, (s,a) and V=(s)= - V+) +v,
where (* (s, (x) y. (P [V((''),
(s) -B ( as.
(s, e (s, a) + D' (V'() Ev, (s) == Ea (s) [eq (s. a)]
(iii) Marginal Consistency Property. This property captures that each subteam's 's partially ag- gregated Q-function (i.e., after marginalizing out actions of agents outside the subteam) differs from the value function V in exactly the same way that the subteam's 's local Q differs from its local baseline V. Formally, for every subteam Ch and any joint action a of agents that subteam,
ax(s,a(t) Va(() (s, (²( + (EQ, (s, - ev. (s))
where
EQ_ EQ_ (z) Ea CENT (x(1)) (ee(s, ct cx)]
Proof. (i) Factorized Joint Policy Functions. No edges exist between agents in different subteams, so each subteam C₁ 's local policy depends only on s and its sutra-subteam parents:
II F (a(aa s, a aP),, where pt S Ca.
iec,
Because these subteams are disjoint, the overall joint policy factors:
K
(a 5)
II
c (a ss).
Hence Property (i) follows.
(ii) Factorized Critic and Value Function. We first show Q(s, a) factorizes. By definition,
Q(s,a) = r(s,a) + yE (B [+()).
By the factorized transition and reward defined in Equation (5), we have
K
Q(s,a) = c(( Σ * (s, + E
Σ E B. PM [Va(6)])
17

---

Published as a conference paper at ICLR 2026
Define
(= = ()) + yB = [Va(')]
and
EQr (s,a) cr(s,a) + BB (Bxree(( Va(s')
Hence
((s.a) = -e (s,
k=1
We can then show (s) factorizes the following
(8( = (- (Q(s.
K
Σ
(s, + cq.
= (s))
R=1
Define
(s) = (
and
(s) == Eawa(11))
cq (8,00
Hence,
K Vi((s) Σ cr)
Therefore, both Q(s, a) and (*( factor over the subteams, establishing Property (ii).
(iii) Marginal Consistency Property. For each subteam Cs, we first define
eQ (s, E. cent (e(1))) (et1))//e/e of a cc)
By definition we have
(x( E -a (-(1s)
(s, + col a c2. (5,
Σ Egk
-a- (1)) 12 + + (s,
= Q3,
+
Σ
E a- - (e -B- (0. E
+ t (x)
Eg
(+( +
Σ
E (C JG [V((s] (s,
Lg
(= +
Σ v*(s) + c2. (8,
tx
and
Vs(() Σ (s) + (v)(s) (s( + (v((s) +vv
Exkk
Hence,
(+) (s) ( v*(()) + (s, cv, (s)).
This establishes the Marginal Consistency Property (iii) and completes the proof of Lemma n
18

---

Published as a conference paper at ICLR 2026
Below define the bounds for the decomposition errors for the transition and reward. Lemma 6 (Bound on Deviations in Factorized Critic and Value Functions). For any policy state 8 E S. joint action a E A, and subteam action axx, the following deviations are upper bounded::
(1,,((,aa), a)l, lev, (s)l, (s, (3, S
Er
7/(1-7)
reward crror
transition crnar
cumuulative reward bound
The bound consists of two parts: 1) quantifies the one-step error due to reward decomposition, and the second term captures the cumulative effect of transition decomposition, scaled by the worst-case return bound 7/(1 7). The overall deviation becomes small when both decomposition errors are small, and vanishes entirely when K = 1, in which case no decomposition is needed.
Proof. We begin with the definition:
(s, a) :- (s + +
Taking the absolute value and applying the triangle inequality:
IEq. (s. a)l $ (e, a)l + Σ lep(s' s, (V)(
Since we have:
(8, a)) $ lerls Σ lep(d' [8,0)] s [S1|e]. [V((')] s 1-7
we obtain:
7|S|
(s, S |erl f >|S||ep] 1-7 lerl + lep
1-7
Now consider the deviation in the value function:
Ev. (s) == E (1)
Applying Jensen's inequality:
lev, (8) S E. l1ec, (8, S /lerl + lep| 7|S]
1-7
Finally, for any subteam Cs:
EQ, (s, (s, := Eg cRnT a aa)+)]
Again applying Jensen's 's inequality:
(e, s E,-c, [leo(s, a s |erl lepl 7/S1
A.5 PROOF OF LEMMA 3
Proof. By bound on the advantage inequality (10), we know that Vs, A .a.,
2(1 - 7)
2(1 - >)
At
a pi ,aa) S d (s.a (s,aPi){SS(A APT
(11)
d# (S)Ta(a |s)| |AP
By inequality (9), we know
( Pi [s) =
II
sola"ls, a pd
2|A0| 2/a [APi]
je
19

---

Published as a conference paper at ICLR 2026
Plugging in (11), we have
21a"11+1 H+1 (1 7)
Ag(s, a'',a)) S d (s)|s)
,d))
Assume without loss of generality that agents in Cs have agent id 2,2.....CA, and have corre- sponding topological ordering of 2........ [C& determined by G. Note that this case, since each subteam Cs disjoint other subteams and agents within each subteam are fully connected, have Vi E Ck. a = P which means that
Qa(s,a² g ~mo(-ls Qolloaa" (ol(,a""aa-p))
rf ~no(lan 1 po(s,apt' ,a -=)
-o((saat))
(12)
Following the reverse topological ordering, we have Va = 11 _alcelj.
Qa(ss aloca ,alce)
<Qo(s, 200c)1-1++1(1 - 7)
(by inequality (10))
(s)
SQo(s, 5Q0(s,0pleel1) +
(2(ckl 1(cx)l1)(111))))) 7)
(by Equation (12))
d (s)]S}
SQols, ploel ") (2/Cal 2101l-11)
7)
(by inequality (10))
d (s))s²
plecl-2 2ccll-2) + (2)c + 2|Cal-1 - >)
Qol(s, QQ
(by Equation (12)
(
(keep doing the same procedure above)
sQo(s,a²) ) (E 21) - 7)
de (s)[S[
Qo(ssa (2/cx|+1 21 7)
di (s][S)
VV((s)+ + (2)calt1_ - 21 - 77)
(since a Pi 0).
d400 (
By property (iii) in Lemma 5, get
Q5(s, s (o) + (2) +1 2) - >)
+ (ev,(s) - EQ as)
dif0 (s))88
20

---

Published as a conference paper at ICLR 2026
By property (ii), we can bound the difference between Global Q and V by the following:
K
Q0(s,a) a) Σ lo a () + cc((,
R=1
(8)+ (2 - 21 7)/
+ (s), (2.(1))) tr((s,a)
(4(ss)s)
k K=] 2| - -2K) 7
(s) +
Σ (x), + =c((s,)
dF' (s)[o)
=Vo(s) + (2 2/c1111 (k)(1-7))
K
+
Σ
(ev, (8)
-EQ, (s, + (eq(s. a) - ev, (6))
(s))
k=1
(EK) Ek= 2 1+1 21 - - + (I: (s) - Σ (s, cQ(s,a)
K
=Vo(s)+
die (s)]s)
kml
(E 2 22)22KN (1))((1-2))) +
<V((s)+ +
(by Lemma 6).
(s)
Letting 0 be the parameters of the optimal joint policy, we have
Ve- (p) Vo(u)
E Bawd? En-arg Ao(5,a) a))
(by performance difference lemma)
K Lk=1 2|0x|+1 2K)(1 -7)
E Bandzo EANTTO
+ +2K +2K(1c lcpl1//1/(111))
(
K k==1
2/c1111 - 21) - -
? Σ oh (8)
(0///(11))) -7)3)
(s){S)
Σ M (Eke 2/011+1 2k) - -))2 +2K(1c//0-m+++ooh/////
1
|8|
K
AM + 2K (lc (t/p:/(117))+/1/111)10 11pph/////(11/// Cu 1+1 2K
Thus, we know that (T Tgx) is an
K (E>K> 2/0x|+1 - 2K)AM + 2K(lc1/(11 - 7) +
1151lepl/11-793 )))) -optimal policy.
A.6 PROOF OF THEOREM 2
Proof. Since (0) is Bm-soohth, we have
VOLA( || < -8x(Lx(0*)) (xOo))
23x(Vmax - Vmin)
2,3
min
T <
<
T
T(1 7))
where the second inequality holds because we initialize 0n = 0. We can choose T large enough such that
2 S A/(2[8))AA max max]A
T(1 -
Solving the above inequality we obtain T>
max: L44
By Lemma 3, we should set À =
(11->)
EE 2 - to achieve the specified optimality gap of c+ (22 (lc,1/11111111 (1-1)1++ +
21

---

Published as a conference paper at ICLR 2026
)) Plugging in À (Et=) 2 -KK and Ax
SN
2AN
[8] we have
(1-3)3
T 2 8M3 A max;; (1 -2K)
e²11 7)
64N max, |49 K
Ck=1 2|c/1+1 2K)²
2MN S
max; |A4 K k=1 2/c/|=1 -2K
[8|
c² 77)²
<² -7)
256N max; (A K 2/ K)a
32N S|JA| max; |AT 2k= 2/(a| K)
2k=1
(1 7)4
c(1 -7)
A.7 PROOF OF PROPOSITION
Proof. Let {C be the coarser partition and {Cr, 1K" TK==1 be its refinement, i.c Cj S Cp((") for mapping yp : {1,..., K"} + (I....,k) K}.
Because the Markov game is decomposed by {Cp} } with errors (cp, 4) by Definition 2 we have, for 8, 5 S and a E A,
K'
K'
P(s' ssa) = Σ
pk (s' (s,00t) + cp(5'ss,a,, r(s,a) = xk (s.a + (s)
Σ K=1
k'=1
(13)
Constructing a decomposition for the coarser partition. For each coarse block C. define
(*((') 8, ax = Σ
pk (5' vv),
(" = Σ
n (s,a
Summing over l I,.... and substituting (13),
K'
(5 8, 18
Σ
pk
pk'(8' ( P(s' 8, -')(('18,a),
1=1
P=1
Σ
( Σ nk (s, -((0))))) -
(s)
Hence P and r admit the coarse decomposition
K
K
p(s = Σ (s s, ( + {)(5'ss,)), r(s,a) = Σ (s + ((,
cr(s/paa)
(x.0))
Error comparison. Because we have simply reused the original error terms,
|epl max (ep(s') ss a)) max (c/ s, a)l 1é/l, s,
|,,1= [-1=led |</
s,s'a
Consequently |epl |dpp and |e,1 S |6,], completing the proof.
A.8 PROOF OF PROPOSITION 2
Proof. Recall (((+)) := Ex= 2 K. We show that splitting any block into two (thereby refining the partition) never increases gi applying this operation repeatedly proves monotonicity for an arbitrary refinement chain.
Let partition { be given, and fix some C, with |C, = 2 2. Split it into two non-empty disjoint sets A, B such that AUB = C1 and |A| a, [B] with a, b 2 and + b = m. The new (refined) partition therefore has K blocks, and its g- gavalue is
K
Inew = (2" + 2 + Σ 2l
(K + 1).
2=
22

---

Published as a conference paper at ICLR 2026
The change A Inew
Fold satisfies
A (2 + 2n) 2 1
(since gold contains 2n for Ci)
2" + 2 22 1.
Because a, b 2 1, we have 2n, 2h S 2atb_1, and therefore
+ 2 < 20+b-1 + 2- 2a+b.
Therefore A < -1 - Equality impossible, so g strictly decreases after any non-trivial split.
Since any refinement can be obtained by a finite sequence of such splits, it follows that if {Cp Jk=1 refines {C& [k= then
g(Ckk)) s g((cx)).
23

---

Published as a conference paper at ICLR 2026
B EXPERIMENTS DETAILS
B. ALGORITHM
Algorithm Dependency-baan based subteams construction under an edge budget
Require:
Agents N, dependency scores di for i. E N, edge budget B Initialize subsets { for E N and edge set & +
Singleton subteams with edges
2: while there are more than one subset and E < B do
3: Find the two subsets C, C' that maximize d(C.c")
4: Enew f- {u, v) u E C, v E C*}
All edges from C to C' D Budget would be exceeded Merge the two subteams
5:
if | - Enewl > then break
6:
E U-EUS Enew merge C and C'
7:
end while
8:
return Subteams hc partitioning DAG G (N,E)
B.2 DETAILS OF DECOMPOSITION ERROR FITTING
We measure the decomposition errors |epl and |,, (cf. Definition 2) by fitting local models {Pk, r²} for each subteam Cs. The goal is to estimate how well the environment's dynamics and rewards can be factorized according to different subteam partitions.
B.2.1 NEURAL NETWORK ARCHITECTURE
For each subteam C.. we implement two multi-layer perceptron models:
A transition model pk Φx AC* -> R S1 that maps subteam actions to transition components
A reward model r th S + that maps subteam states to reward components
Both networks use a three-layer architecture with hidden dimension 128:
FC(in_dim, 128) > ReLU + FC(128, 128) - ReLU - FC(128, out_
B.2.2 GLOBAL APPROXIMATION
We reconstruct global approximations by summing the outputs the subteam-speciff networks:
Po(-aa) Σ P&. (laCt) (s(s)
Σ (s).
The decomposition errоrs are then computed as the maximum absolute differences between the true environment dynamics and our factorized approximations:
EP max (Po(a)))) ((s((a))((s(())) | max (o(s) r(s)].
a.s!
B.2.3 TRAINING PROCEDURE
The models for each partition structure were trained using the Adam optimizer with learning rate of 10-3 over 10,000 epochs. The training process minimizes two Mean Squared Error losses:
CP(V)
1
Σ aEA.NES
P(s'(a) (oyla-)Ppe We (6'1aSu)
Eps,
pe
(14)
[A||S]
(,)
1
Σ
r(s)
Σ
net (sce)
(15)
S
SES
24

---

Published as a conference paper at ICLR 2026
B.3 DYNAMIC DAG CONSTRUCTION
Handling variable parents. To accommodate the variable parent sets p induced by the dynamic DAG each timestep, construct the input agent v's actor the concatenation of its observation (or encoded state) and the actions (and optionally observations) of its parents:
Input; Concat(o' or o(o'), {a', ,0' JEP:))
where <f-) an optional encoder. For agents that are not parents of agent their actions are zero- padded to ensure fixed input dimension. This design enables consistent batching across agents and supports seamless integration into standard actor-critic architectures.
Dependency computation.
The pairwise dependency scores de reflect the spatial proximity between agents and are computed as the negative pairwise distances, with specific formulations for each environment:
Coordination Game:
=-= s²1
where s {0, 1) denotes the binary state of agent i.
Aloha: Agents are fixed on a 2 x grid at positions (I v) E [0, x (0,1,2,3,4) The dependency score is the negative Manhattan distance:
dij (Ix; z, lys My|).
Predator-Prey, Warehouse, and Battle: Each agent occupies a continuous 2D position (1) R The dependency score is the negative Euclidean distance:
di = v (z; - x2)² + (y) - y,
B.4 PSEUDOCODE FOR THE REWARD FUNCTION IN COORDINATION GAME
Algorithm Compute Team Reward for N Agents State
1: if NN E [2,3) then
2: di fiffeeenceeboud +-
3: else
4:
differeencebount + 2
5: end if
6: co + s.count(0) (0)
7: e₁ < s.count(1)
8: if cp
S diffeeccce bound then
9: if co < c then
10:
reward+
11: else
12:
reward +
13: end
else if 6o ci then
15: reward + 3
else
17: reward +-2 2
end if
25

---

Published as a conference paper at ICLR 2026
B.5 HYPERPARAMETERS
Table 2: Hyperparameters for MAPPO (Coordination Game and A MADDPG (Predator-Preg) Prey)
Hyperparameter
Value
Environment steps
2 x 10 (CG), x 10 (Aloha), 4 x 10 (Predator-Prey)
Episode length
20 (CG), 25 (Aloha and Predator-Prey)
PPO epochs
5 (CG and Aloha)
Actor/Critic learning rate
x 10 (CG and Aloha), 10 (Predator-Prey)
Optimizer
Adam
Evaluation episodes
100 (CG and Aloha), 200 (Predator-Prey)
Rollout threads
32 (CG and Aloha)
Training threads
32 (CG and Aloha)
Hidden size
64 (CG and Aloha), 128 (Predator-Prey)
Random seeds
60 (CG and Aloha),
(reddator-Pre))
Actor architecture (CG)
Conca((Base(s). Pi) - FC([ Softmax
Actor architecture (Aloha)
Concat(Base( Base(Concat .aP' 1)) + FC((A4)) - Softmax
Actor architecture (Predator-Prey)
Concat a²) + FC ReLU + FC - ReLU - FC((A1))
Critic architecture (CG/Aloha)
Joint state or observation - Base FC(1)
Critic architecture (Predator-Prey)
[o':a") GCN, - FC - GCN₂ - PC MaxPool FC(1)
Notation: CG Coordination Game. Base: FC(hidden) - ReLU FC(hidden) - ReLU
Table 3: Hyperparameters for value-based methods (Warehouse and Battle)
Hyperparameter
Value
Environment steps
1.5 10th (Warehouse). 2 10 (Battle)
Episode length
50 (Warehouse), 100 (Battle)
Learning rate
x 10
Optimizer
Adam
Evaluation episodes
10
Hidden size
64 (Subteam QC+), 128 (Mixer)
Random seeds
10 (Warehouse), 5 (Battle)
Subteam ratio 7)
1/4 [TAV
Subteam Qhx architecture (per subteam C.)
FC ELU - FC(64) - ELU - FC([
Mixer architecture (QTRAN/VAST)
Concat QC: "........,,,, + FC(128) + ELU - FC(128)
ELU FC(1)
Notes: All hyperparameters follow VAST (Phan al., 2021b).
26

---

Published as a conference paper at ICLR 2026
C ADDITIONAL RESULTS
Coordination
Coordination N=3
Coordination N=5
Tull
full
tull
12.5
Equilbrium gap
10.0-
1+2
1+4
product
3
2+3
2
0.0
10
10-
10a
10
10"
10a
10
10a
100
10
10a
10
10
10a
10*
Iterations
Figure 4: Equilibrium gap of tabular softmax BN policy gradient ascent under various DAG topolo- gies. Averaged over 50 seeds, with shaded areas showing standard error; initial policy 0, ~ N(0, 1).
27

---

Published as a conference paper at ICLR 2026
D RESULTS ON SMAC
bane vs. bane
1.0
product
full
0.8
Win Rate
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0 1e6
Timesteps
Figure 5: Full DAG vs. product DAG with MAPPO on the SMAC bane bane map.
The learning curves Figure 5 display the mean and standard error over 12 random seeds on the SMAC bane bane map, heterogeneous large-scale scenario with 24 controllable agents (20 Zerglings and 4 Banelings). The fully correlated DAG and the product DAG achieve nearly iden- tical performance, indicating that additional correlation provides little benefit in this environment and therefore the heuristic is not expected to outperform the product structure when even the fully expressive DAG offers no advantage.
28


Reviews:
[{"review_id": "RTHZryeAoc", "reviewer": "Reviewer_Qy1s", "summary": "This paper addresses the critical challenge of scalability in cooperative multi-agent reinforcement learning (MARL), which is often hindered by the exponential growth of the joint action space. The authors draw inspiration from human teams to propose a \"subteam-based coordination\" structure. This structure is formalized using Bayesian networks (BNs) , where agents within a subteam are fully correlated (modeled as a fully connected subgraph ) while interactions between subteams are limited (modeled as conditionally independent ).\n\nThe paper's contributions are threefold:\n\n- It provides a finite-time convergence rate for tabular softmax BN policy gradient ascent under a fixed DAG, strengthening prior asymptotic results.\n\n- It proves that for this subteam-based BN structure, regularized policy gradient ascent converges to a near-optimal policy (not just an equilibrium) under a \"decomposability condition\" on the environment's reward and transition functions. The resulting suboptimality bound is explicitly characterized by the decomposition errors.\n\n\n- It introduces a practical heuristic for dynamically constructing these subteam DAGs based on \"dependency scores\" and an edge budget. This heuristic is integrated with deep MARL algorithms (MAPPO/MADDPG) and value-factorization methods (VAST) , demonstrating superior performance over baselines across several benchmarks.", "questions": "- (W1) Could the authors comment on the generality of low-error decomposability? The tabular experiments show this holds for the Coordination Game, but how restrictive is this assumption for more complex, non-obvious benchmarks? Is it possible to estimate or bound these errors a priori to determine if an environment is suitable for this method?\n\n- (W2) How sensitive is the heuristic to the quality of these scores? What would happen in a task where the primary dependency is functional (e.g., \"passer\" and \"shooter\") rather than spatial? Could these dependency scores be learned dynamically, perhaps by analyzing value function contributions or action correlations, to make the approach more general?\n\n- (W3) How challenging would it be to relax this assumption? For example, if a small number of inter-team edges were permitted, would this completely break the value function decomposition (Lemma 5), or could it be handled by introducing additional, bounded error terms into the analysis?\n\n- (W4) Does this suggest that the 'fully-correlated subteam' structure is a sufficient, but perhaps not strictly necessary, condition for good performance? It implies that other sparse, structured DAGs might also be effective, even if they don't fit the specific subteam partition model.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**Clear Motivation and Formalism**: The paper's premise is intuitive and well-motivated. The core idea of partitioning agents into highly-coordinated subteams to reduce complexity is a natural one. The use of Bayesian networks to formalize this—capturing full correlation within teams and independence between them—is an elegant and clean way to model the problem .\n\n**Theoretical Contribution**: The main theoretical result (Theorem 2) is a strong contribution. It moves beyond typical convergence guarantees (to an equilibrium, like in Theorem 1) to provide a bound on the policy's suboptimality. Crucially, it connects this bound directly to a structural property of the environment: the decomposability errors. This provides a concrete, formal basis for why and when subteam factorization should work.\n\n- **Identification of a Key Trade-off**: The theory and experiments jointly expose a fundamental trade-off in subteam design. Coarser partitions (i.e., fewer, larger subteams) lead to smaller decomposition errors and thus a lower asymptotic suboptimality bias. Finer partitions (i.e., more, smaller subteams) may converge faster but suffer from larger errors. The tabular experiments in Section 6.1, which fit the decomposition errors (Table 1) and plot the final suboptimality (Figure 1), provide a clear and compelling validation of this theoretical insight.\n\n- **Empirical Validation and Practical Heuristic**: The paper successfully bridges the theoretical insights to a practical setting. The theory motivates the search for partitions with low decomposition error, and the authors propose a sensible heuristic (Algorithm 1) to approximate this by merging subteams with high \"dependency\" . The empirical results are comprehensive, showing the heuristic's effectiveness in:\n\n  - Tabular settings (validating the theory).\n\n  - Deep MARL actor-critic methods (outperforming 'full', 'product', and 'random' DAGs) .\n\n  - Centralized training (CTDE) value-factorization methods (improving VAST) .", "weaknesses": "- **On the \"Decomposability\" Assumption**: The main result hinges on the environment's decomposability (Definition 2). The authors correctly state that any environment can be decomposed this way, as the errors can absorb any discrepancy. However, the utility of the bound in Theorem 2 depends on these errors being small. \n\n- **Dependency Scores for the Heuristic**: The practical heuristic (Algorithm 1) requires pre-defined \"dependency scores\" to guide the merging process. In all experiments, these scores are based on domain-specific spatial proximity (e.g., Euclidean or Manhattan distance, or binary state position) . This seems to be a form of privileged information. \n\n- ** Strictness of Assumption 3(iii)**: The theoretical framework (specifically Assumption 3(iii)) requires no edges between subteams. This is noted as a technical requirement for the proof. This hard partitioning seems somewhat rigid, as real-world teams often have sparse but important cross-team coordination. \n\n- **\"Line\" DAG Baseline**: In the tabular results (Section 6.1), the \"line\" DAG is used as a baseline and performs quite well (Figure 1). The paper notes this DAG does not satisfy Assumption 3  (as it's a single chain, not a partition of fully-connected subteams). This is an interesting result.", "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": "KFi4LPy4Am", "reviewer": "Reviewer_Duum", "summary": "This paper utilizes Bayesian Networks (BNs) to model the structured correlations among multi-agent subteams and proposes a class of correlated joint policies induced by directed acyclic graphs (DAGs). Building upon prior work, it establishes a convergence rate for tabular softmax BN policy gradient ascent under fixed DAG structures. Furthermore, the authors prove that, for BNs aligned with the context of multi-agent subteams, regularized policy gradient ascent converges to a policy with bounded suboptimality. Finally, this paper relaxes certain assumptions and proposes a heuristic method, which is evaluated across multiple benchmark environments.", "questions": "1. If possible, please answer the questions mentioned in the Weaknesses Section first.\n\n2. What impact will partial observability have on the theoretical conclusions of this paper?\n\n3. Why is maximizing the average pair-wise dependency score between the agents considered a reasonable criterion for merging two subteams? What are the underlying motivations or theoretical considerations behind this method?\n\n4. What are the considerations for selecting baseline algorithms (MAPPO/MADDPG) in different experimental environments?\n\n5. This is my second time reviewing your submission. As you can see, I continue to hold a generally positive view of your work. I appreciate that you have added new experimental scenarios in response to the previous round of reviewers’ comments — that is definitely a constructive improvement. However, it is somewhat disappointing that the additional experiments are still based on the VAST (2021) scenario, which is relatively dated and not particularly convincing as an evaluation benchmark. Therefore, the new results do not substantially strengthen the empirical evidence of your claims. I strongly encourage you to follow the suggestion of Reviewer QYoJ from NeurIPS25 and include experiments on large-scale scenarios in SMAC with more than 20 agents, which would make your framework’s advantages much more persuasive. For this round, I maintain my overall positive inclination toward the paper, but I must note that I cannot guarantee other reviewers will share the same perspective — some may weigh empirical validation more heavily than theoretical contribution. I therefore reserve the right to align my final assessment with the consensus on other reviewers' evaluation on your experiment.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-structured, with a clear and well-defined motivation.\n\n2. The description of the background and the theoretical analyses are detailed, with clear explanation of the underlying thoughts.\n\n3. This is the first work that establishes optimality guarantees for BN policies without requiring full independence among agents.\n\n4. This paper conducts sufficient experiments to demonstrate the effectiveness of the method.", "weaknesses": "1. The assumptions required for the proof section (full observability, fully correlated with a sub-team and fully independent across sub-teams, fixed DAG topology) are too strict.\n\n2. Practical methods relax some assumptions in the proof section, but some may deviate significantly from the original proof (such as global observability).\n\n3. Experimental scenarios are too simple to demonstrate the upper limit of the method's advantages.", "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": "IWcye1PcS0", "reviewer": "Reviewer_g5cJ", "summary": "This paper studies correlated policy optimization in cooperative multi-agent reinforcement learning (MARL) using subteam-based coordination. The authors represent joint policies as Bayesian networks (BNs), where agents within a subteam are fully connected and thus act in a correlated manner, while inter-subteam dependencies are limited.\n\nTheoretical results extend previous work on BN policy gradients by establishing finite-time convergence to near-optimal policies under a decomposability assumption on the environment’s reward and transition functions. The analysis reveals a trade-off: finer partitions of agents yield faster convergence but potentially higher suboptimality due to decomposition errors.\n\nEmpirically, the authors validate their theory in a tabular coordination game that precisely satisfies the theoretical assumptions, and then introduce a heuristic for constructing context-aware subteams based on pairwise dependency scores. This heuristic is integrated into deep MARL algorithms such as MAPPO and MADDPG, where it consistently improves learning speed and final performance across multiple benchmark environments.", "questions": "1. How exactly are the dij dependency scores computed in each environment? Are they purely distance-based, or do they involve any learned or empirical statistics?\n2. In Section 6.2.1 you mention that “parent actions are detached from the computation graph to prevent backpropagation.” Could you elaborate on this?\n3. Have the authors seen or considered the following closely related paper? Kapoor, A., Freed, B., Schneider, J., & Choset, H. (2025). Assigning Credit with Partial Reward Decoupling in Multi-Agent Proximal Policy Optimization. Reinforcement Learning Journal, 1, 380–399. This work also decomposes agents into subgroups with partially decoupled rewards and might provide a useful empirical or conceptual comparison.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The problem is well-motivated. The work addresses a central challenge in MARL—scaling coordination to large agent populations—by introducing a principled way to exploit structured correlations.\n- The exposition is clear, and the theoretical intuitions are well communicated.\n- The paper has a strong theoretical contribution.  The finite-time convergence and near-optimality guarantees under decomposability assumptions extend prior results (e.g., Chen & Zhang, 2023) in a meaningful way.\n- The experiments are well-aligned with the theory. The tabular experiments are well designed to exactly satisfy the theoretical setup, lending credibility to the claims.\n- The empirical results are convincing. The proposed heuristic for subteam construction yields consistent performance improvements in deep MARL tasks, as shown in Figures 2–3.", "weaknesses": "Dependence on domain-specific priors: The heuristic requires a priori pairwise dependency scores dij , which rely on domain knowledge. This may limit generality and make comparisons to methods that learn dependency structures less direct.", "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": "RtnFqpaxDN", "reviewer": "Reviewer_2vBZ", "summary": "The paper considers subteams in cooperative multi-agent RL as a means to balance coordination and scalability. First, under the tabular setting, the authors establish theoretical results investigating convergence and suboptimality for bayesian networks policy gradients under decomposability assumptions. Second, the authors empirically validate their theoretical results in a tabular setting. Third, the authors propose a practical approach for constructing subteams in MARL tasks and test it in three MARL environments, as well as investigate how it can be used for value factorization in centralized training.", "questions": "- The authors consider access to the full underlying state of the environment (Markov game). What about the case of Dec-POMDPs?\n- While assumption 1 may be used by previous works, I still believe it is a bit restrictive. How hard would it be to extend the theoretical results while removing Assumption 1?\n- Maybe the authors could discuss after presenting Theo. 1 what are the key differences between the result in Theo. 1 and the equivalent single-agent result.\n- line 288 - \"1. Therefore, the suboptimality bound in (6) reveals a tradeoff when choosing the fineness/coarseness of the decomposition\" - Is it possible to find the optimal tradeoff between the two terms in the bound of Lemma 3?\n- How many runs were performed to get the empirical results (e.g., Fig. 1)?\n- Figure 1: What do the shaded areas in the plots represent?\n- Secs. 6.2 and 6.3 of the paper seem a bit disconnected from the theoretical part of the paper. I'm particularly referring to the algorithmic aspect (not to the problem of finding good partitions). The gradient ascent algorithm proposed and analysed by the authors in (2) and (3) considers a regularized objective. What would be the closest \"function-approximation\" variant of such an algorithm? Why did you choose MAPPO and MADDPG? Can these algorithms be seen as some kind of \"function-approximation-counterparts\" of the tabular algorithm in (2)-(3)?\n- No other previous works (e.g., those discussed in Sec. 2) propose ways to perform subteams decomposition? If so, I believe such methods should also be included as baselines in the empirical part of the work.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The papers features a good discussion of related work in Sec. 2. I believe the key contributions of this work are related with the analysis of gradient-based methods to optimize BN policies - the paper seems to contribute with a novel analysis of gradient-based methods to optimize BN policies in the tabular setting. The paper is clear and well-organized. The experiments seem to support the theoretical findings.", "weaknesses": "The contribution of the paper in the empirical part seems a bit marginal. In particular, I have two key concerns (take a look at my last question below for additional details): (i) are the baselines considered representative of the multiple previously proposed algorithms discussed in Sec. 2?; and (ii) the empirical algorithms analysed in Sec. 6.2 do not seem directly linked to the algorithm analyzed in the theoretical part of the paper. The theoretical results also rely on some assumptions that are a bit restrictive (access to the underlying state and Asssumption 1), but I believe this should not be a reason to reject the paper alone.", "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)