This paper, presented at NeurIPS 2026, introduces a principled axiomatic framework for reinforcement learning in open multi-agent systems—environments where you only control a subset of agents and must coordinate with others whose behaviors are unknown or changing. By grounding value function learning in the classical axioms of the Shapley value, the authors provide a theoretical bridge between cooperative game theory and temporal-difference learning, resulting in algorithms that generalize significantly better to unseen teammates.
TL;DR
The authors derive a new reinforcement learning framework for open multi-agent systems by treating the Shapley axioms (Efficiency, Symmetry, and Linearity) as structural constraints on learning. This approach naturally links cooperative game theory to $n$-step returns in RL, producing "Shapley Machines" that outperform standard methods in coordinating with unknown teammates.
What Problem Does This Paper Address?
Most Cooperative Multi-Agent Reinforcement Learning (CMARL) research assumes a "closed" system: you control all agents, and the team composition is fixed. In the real world—think smart grids or autonomous traffic—systems are "open." You might control a few robots in a swarm, but you have no control over the others, and the "teammates" you encounter tomorrow might behave differently than the ones you trained with today.
This setting is formalized as n-agent ad hoc teamwork (NAHT). The core challenge is credit assignment: how do you learn an individual value function for a controlled agent when the team's success depends on the unpredictable actions of uncontrolled partners? Existing methods often rely on heuristic design choices that fail to generalize when the team composition changes.
Methods
The authors propose an axiomatic approach, moving away from heuristic designs toward structural constraints derived from cooperative game theory.
- NAHT Decomposition: They decompose the team value into two parts: Internal Cooperation (interactions among controlled agents) and External Teamwork (interactions involving uncontrolled agents).
- The Axiomatic Framework: They enforce three core Shapley axioms as constraints on how individual value functions ($V_i$) are learned:
- Efficiency: The sum of individual values must equal the total team value ($\sum V_i = V_{total}$). This leads to a principled form of reward shaping.
- Symmetry: Agents who contribute equally to all possible coalitions should receive equal value. This is implemented through specific neural architectures that are invariant to agent ID reordering.
- Linearity: This is the paper's most novel contribution. They prove that the Linearity axiom induces a structure equivalent to truncated $TD(\lambda)$.
- Algorithmic Templates:
- Shapley Machines (SM): Enforce all three axioms.
- Banzhaf Machines (BM): Relax the Efficiency axiom, which aligns the learning with the Banzhaf power index rather than the Shapley value.
These templates can be "plugged into" existing algorithms like Independent PPO (IPPO) or POAM to create SM-IPPO, SM-POAM, etc.
Datasets
The methods were evaluated on two major benchmarks adapted for the "open" setting:
- MPE Predator-Prey (MPE-PP): A continuous 2D environment where pursuers must coordinate to capture an evader.
- StarCraft Multi-Agent Challenge (SMAC): A high-dimensional micromanagement benchmark. The authors tested several scenarios, including 5v6, 8v9, 10v11, and 3s5z, where the number of controlled allied units varies.
Key Insights and Ideas
- The $TD(\lambda)$ Connection: The authors provide a theoretical explanation for why $n$-step returns are effective in multi-agent settings. They show that the Linearity axiom implies that the RL horizon should be related to the number of non-empty coalitions in the game.
- Coalition-Based Horizon: As shown in Figure 2, the number of $n$-step return components ($m$) can be determined by the number of non-empty coalitions ($m = 2^M - 1$). Setting $m$ based on this game-theoretic logic maximizes learning performance.
- Decomposition of Openness: The NAHT decomposition (Figure 1) visually demonstrates how ignoring "External Teamwork" (the blue vector) and only focusing on "Internal Cooperation" (the red vector) leads to a loss of information, which explains why closed-system CMARL fails in open environments.
Key Results
- Superior Performance: Shapley and Banzhaf Machines consistently achieved higher win rates and returns across all SMAC and MPE tasks compared to base IPPO and POAM (see Figure 3).
- Robust Generalization: In "Out-of-Distribution" (OOD) tests, the proposed methods showed a much stronger ability to coordinate with unseen agent types and unseen conventions (teammates trained with different random seeds).
- Axiom Flexibility: Interestingly, the authors found that while the Efficiency axiom helps coordination, relaxing it (Banzhaf Machine) sometimes improved generalization to totally unknown agent types, suggesting that "fair" value distribution isn't always the best for pure adaptability.
Limitations and Future Work
- Scalability of Coalitions: The number of basis games (coalitions) grows exponentially with the number of agents ($2^M - 1$). For large teams (like 10v11), the authors had to approximate the horizon using the episode length because the theoretical number of coalitions (511) far exceeded the episode steps (150).
- Stability in Large Scenarios: Enforcing the Efficiency axiom via reward shaping can introduce instability in very large-scale scenarios. The authors used a "value loss clip" to mitigate this, but more robust stabilization techniques are a noted area for future work.
- Dynamic Horizons: The current work uses a fixed horizon schedule. Future research could explore adaptive horizons that change based on the state or the specific coalition being evaluated.
Summary updated