When several learning agents must act together, the reward often depends on what three or more of them do jointly. For example, a target falls only if three units attack it at once. Existing value decompositions cannot see this dependence. They split the team's value into per-agent terms or per-pair terms. In a task where three agents must coordinate, every single agent's choice and every pair's choice looks uncorrelated with reward, just as each variable in a three-bit parity problem looks like noise when examined alone or in pairs. The learner then wanders through a joint action space that grows exponentially with team size before it stumbles on the rare successful combination. That is the sample-inefficiency problem in its sharpest form.
We propose to write the team's action-value as a sum of interaction terms of every order up to $M$, with the parameters of those terms tied at the level of individual agents rather than learned separately for every group of agents. The construction borrows the ANOVA-kernel dynamic program from Higher-Order Factorization Machines. That paper showed that all degree-$m$ products among $d$ features can be evaluated in $O(dm)$ time, and that the model is linear in any single feature's parameters. In our setting, those two properties give three things. The model can represent three-way and higher coordination. Its size grows linearly in the number of agents rather than with the number of agent subsets. And greedy action selection reduces to exact per-agent best responses computed from a handful of broadcast numbers.
Core Claim
Our central claim concerns what makes learning sample-efficient. We claim the decisive factor is how the model shares parameters across interaction orders and agent groups, not whether it contains higher-order terms at all. A model that ties all $m$-way payoffs to shared per-agent factors should find three-way coordinated optima in far fewer environment steps than two alternatives: pairwise coordination graphs, which cannot represent those optima, and untied hyperedge models, which can represent them but must estimate a separate payoff for each group.
Concretely, let $q_i(a_i)$ be agent $i$'s individual utility. Let $z_{ik}(a_i)$ be the $k$-th of $K$ factor scores that a shared network produces for agent $i$ from its observation history. Let $w_{m,k}(s)$ be state-dependent weights that may take either sign. Let $e_m$ denote the elementary symmetric polynomial of degree $m$, which is the sum over all $m$-agent subsets of the product of their scores. The value function is then
$$ Q(s,\mathbf a)=\sum_{i=1}^n q_i(a_i)+\sum_{m=2}^{M}\sum_{k=1}^{K} w_{m,k}(s)\,e_m\big(z_{1k}(a_1),\dots,z_{nk}(a_n)\big). $$
Each $e_m$ is computed by the recurrence $e_m^{(j)}=e_m^{(j-1)}+z_{jk}\,e_{m-1}^{(j-1)}$ over agents $j$. This costs $O(nMK)$ per evaluation and supports exact gradients, as shown in the HOFM paper. When the other agents' actions are held fixed, $Q$ is affine in agent $i$'s factor vector. Agent $i$'s best response is therefore the action maximizing $q_i(a_i)+\mathbf c_i^\top \mathbf z_i(a_i)$. The coefficient vector $\mathbf c_i$ depends only on the lower-order symmetric sums of the other agents, and every agent can recover it from $O(MK)$ broadcast scalars. The cost of this communication does not grow with the number of pairs or groups.
Relation to Prior Work
Four groups of work bear on this proposal, and they play different roles.
The pairwise line motivates the gap. Deep Coordination Graphs (DCG) factorizes the team value into per-agent and pairwise payoffs, using low-rank payoff matrices and message passing to choose actions. It solves the pairwise version of relative overgeneralization, the failure where uncoordinated partners make coordinated actions look bad. The authors leave higher orders out because message passing over larger groups is expensive. Context-Aware Sparse Deep Coordination Graphs (CASEC) prunes pairs whose payoff varies little with the partner's action. Non-Linear Coordination Graphs (NL-CG) passes pairwise payoffs through a piecewise-linear mixing network. This makes greedy selection hard and requires non-negative weights.
Our model differs from all three in two ways. Its primitives are genuinely multi-way. Its action selection stays exact at the level of each agent, and this holds without sign restrictions, because the weights $w_{m,k}(s)$ depend on the state and not on the actions.
The hypergraph line shows that group structure matters but builds that structure heuristically. HYGMA forms disjoint agent groups by spectral clustering and then runs hypergraph attention within each group. Pairwise is Not Enough (HMAGAT) builds spatial k-means hyperedges and is trained by imitating an expert solver. Both place higher-order structure in the representation layer, the part of the network that processes observations. Neither places it in the value decomposition itself. HYGMA cannot express overlapping group memberships. HMAGAT leaves pure reinforcement learning with sparse rewards untested. In our model every agent belongs to every subset, and the learned factors and weights decide which subsets matter. Group-Aware Coordination Graph (GACG) injects group covariance into pairwise edges at a cost of $O(n^4)$, but its message channel remains pairwise.
The low-rank line supplies the evidence that parameter tying buys samples. Matrix Low-Rank Approximation For Policy Gradient Methods cut training episodes on the rocket task from about 22,000 to about 7,000 using matrix factorization. The authors name the extension to higher-order tensors as open. DCG found that even rank-1 pairwise payoffs work well. Our model can be read as the tensor extension of this idea: a symmetric low-rank factorization of every joint-payoff tensor at once.
Research Program
We will build the model on a standard centralized-training value-learning pipeline, with double Q-learning targets and replay. We will study three questions.
The first question is representational. For which payoff structures is tying across subsets harmless, and for which does it lose expressiveness? Tied factors cannot, by themselves, say that "agents 1, 2, 3 interact but agents 1, 2, 4 do not." That selectivity must come from state-conditioned factors that shrink toward zero for inactive agents. We will characterize this limit on synthetic games.
The second question is about optimization. Coordinate ascent on a multilinear objective converges to a joint action from which no single agent can improve. We will measure how often that point is the global optimum. On small teams we can compare against exhaustive search. We will also test cheap restarts and a pairwise warm start.
The third question is the sample-complexity mechanism. We will vary the maximum order $M$ and the rank $K$, and we will compare tied against untied factors, while holding the total parameter budget fixed.
Baselines
The naive reference point is VDN (additive per-agent values) together with independent Q-learning. The DCG paper reports that these fail completely on predator-prey tasks with miscoordination penalties. They show how much of the task is solvable without any coordination modeling.
QMIX, which combines per-agent values through a mixer constrained to be monotonic, is the standard strong decomposition. It tests whether a monotonic mixer already suffices.
DCG, both fully connected and at ranks 1 and higher, is the most direct competitor. It solves pairwise coordination with the same kind of low-rank payoffs we use. Our order-2 ablation, $M=2$, is essentially DCG with tied factors. Comparing it against $M=3$ isolates the contribution of higher orders.
NL-CG is the strongest pairwise-primitive method that allows non-linear combinations of payoffs. If non-linear mixing of pairs can emulate three-way payoffs, NL-CG will reveal it.
HYGMA is the strongest existing higher-order competitor on SMAC. SMAC is the StarCraft Multi-Agent Challenge, a benchmark of cooperative unit-control battles. HYGMA reports a win rate of about 90% on the super-hard map 3s5z_vs_3s6z, against under 40% for QPLEX (reported in HYGMA). CASEC is included on the MACO coordination suite, where its sparsity is known to help.
The key ablation is an untied model. It uses explicit rank-$K$ three-way payoffs, one set of factors per agent triple, with exact enumeration of joint actions on small teams. This model has the same representational order as ours but no cross-subset sharing. If it matches our sample efficiency, the tying claim is false.
All methods will use the same environment-step budget, the same replay and target-network settings, an equal hyperparameter-search budget per method (the same number of configurations), matched parameter counts where the architecture allows, and at least eight seeds. We will rerun baselines ourselves rather than quote their curves. Beating a baseline means a higher area under the win-rate or return curve at matched steps, with non-overlapping bootstrap confidence intervals. On SMAC, it also means reaching the rerun HYGMA's final win rate in fewer steps.
Why not just…?
Why not just use NL-CG's non-linear mixing over pairwise payoffs? A non-linear function of pairwise payoffs can in principle produce three-way effects. But in a task where the reward depends only on a three-way interaction, every pairwise payoff has nothing to fit in expectation. The learning signal reaching the pairwise terms is therefore pure noise until the mixer has already discovered the interaction. The three-agent parity and coordinated-attack games below test exactly this. If NL-CG solves them in comparable steps, our motivation weakens. We would then report that honestly and reframe the contribution as cheaper action selection.
Why not just use hypergraph attention as in HYGMA? HYGMA is a real threat on SMAC, where group structure is often spatial and clustering finds it. Its groups are disjoint and are chosen from behavioral similarity rather than from payoff. So it should struggle when the functional groups overlap, or when they are spatially scattered, as with a spotter and distant artillery. We include a MACO-style variant with overlapping required triples to test this. Combining HYGMA's encoder with our value head is also a natural outcome if both help.
Why not just enumerate all triples explicitly? For eight agents there are only 56 triples, so explicit hyperedge payoffs are affordable. This is the most dangerous alternative, which is why it is our main ablation. Our prediction is that the untied model needs roughly as many more samples as it has more free parameters, because each triple's payoff is learned only from the transitions where that triple's actions varied informatively. The gap should widen with team size. If the gap is absent at $n \le 10$, the method's value reduces to scalability alone, and we would say so.
Why not just scale a centralized critic? HMAGAT's 1M-parameter hypergraph model beat an 85M-parameter pairwise transformer trained on 100 times more data. That result suggests scale does not substitute for interaction structure. However, it was obtained under imitation learning, not reinforcement learning. We will therefore include a transformer mixer of matched parameter count trained on the same reinforcement-learning budget.
Proposed Experiments
The decisive diagnostic is a family of synthetic cooperative matrix games with $n$ between 4 and 12 agents. In these games, reward arrives only when exactly three agents, or a specific three-agent pattern, choose a coordinated action, and miscoordination is penalized. Such games have zero first- and second-order signal by construction. We will measure the environment steps needed to reach the optimum and the fraction of seeds that do so, as $n$ grows. The prediction is that DCG, QMIX, and VDN fail, the untied model succeeds but needs steps growing with the number of triples, and the tied model's steps grow roughly linearly in $n$.
Next, we will modify the DCG predator-prey task so that capture requires three predators. On the original task, VDN, QMIX, and independent learners fail completely while DCG succeeds; no numerical value is reported there beyond this success/failure outcome. This extends a known pairwise failure into the three-way regime.
On MACO (Aloha, Pursuit, Sensor, Gather), we compare against CASEC and NL-CG. The file reports no win-rate numbers for these tasks, only CASEC's 30–90% message savings and NL-CG's 50–65% runtime savings. We will therefore also report communication volume per decision, since broadcasting $O(MK)$ scalars should undercut per-edge message passing.
On SMAC we will use 5m_vs_6m, MMM2, 10m_vs_11m, 3s5z_vs_3s6z, and corridor. The reference numbers are HYGMA's roughly 90% on 3s5z_vs_3s6z, and SMAC's report that most methods reach 0% on corridor. The central measurement is sample efficiency at matched budgets.
Across all settings, we will report the gap between coordinate ascent and exhaustive argmax on teams of up to 8 agents. We will also report the learned magnitudes $|w_{m,k}|$ as a function of order, which tests whether the model uses third-order terms exactly where the task requires them.
The proposal fails if one of two things happens. Either the untied triple model matches the tied model on the synthetic games at every team size, or $M=3$ provides no gain over $M=2$ on the three-predator task.
References
- Higher-Order Factorization Machines
- Deep Coordination Graphs
- Context-Aware Sparse Deep Coordination Graphs
- Non-Linear Coordination Graphs
- HYGMA: Hypergraph Coordination Networks with Dynamic Grouping for Multi-Agent Reinforcement Learning
- Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding
- Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning
- Matrix Low-Rank Approximation for Policy Gradient Methods