An Axiomatic Framework for Reinforcement Learning in Open Multi-Agent Systems

Jianhong Wang, Yang Li, Samuel Kaski, Jonathan LawryarXiv 2026 · arXiv

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.

  1. NAHT Decomposition: They decompose the team value into two parts: Internal Cooperation (interactions among controlled agents) and External Teamwork (interactions involving uncontrolled agents).
  2. The Axiomatic Framework: They enforce three core Shapley axioms as constraints on how individual value functions ($V_i$) are learned:
  3. 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.
  4. 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.
  5. Linearity: This is the paper's most novel contribution. They prove that the Linearity axiom induces a structure equivalent to truncated $TD(\lambda)$.
  6. Algorithmic Templates:
    • Shapley Machines (SM): Enforce all three axioms.
  7. 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.
Figure 2: Experiments verifying that the number of n-step return components in TTD(λ) can be determined by the number of non-empty coalition basis games. In MPE-PP the number of basis games is m = 7, in 5v6 it is m = 31, and in 8v9 it is m = 120.
  • 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.
Figure 1: Visualization of state-specific cooperative games and the loss of information when ignoring external teamwork.

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.
Figure 3: Evaluation curves showing SM and BM variants achieving the best performance across various tasks.

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

Abstract

Open multi-agent systems, where only a subset of agents are controllable, are central to real-world domains such as smart grids, yet lack a principled foundation for reinforcement learning algorithm design. We study this setting through n-agent ad hoc teamwork (NAHT), a recent framework for learning in open multi-agent environments. We propose an axiomatic framework that derives value function learning from the Shapley axioms (Efficiency, Symmetry and Linearity), treating them as structural constraints rather than heuristic design choices. This formulation builds on a novel NAHT decomposition, which characterises the fundamental difference between open and fully controllable multi-agent systems, and establishes a cooperative game-theoretic foundation for learning. We further show that enforcing these axioms on learning individual value functions recovers the Shapley value for Dec-POMDPs, providing a principled bridge between reinforcement learning and classical cooperative game theory. Building on this framework, we introduce Shapley Machines and Banzhaf Machines, two generic algorithmic templates that can be instantiated with standard reinforcement learning methods. When applied to strong base algorithms such as IPPO and POAM, our methods consistently improve learning efficiency and generalisation to unseen agent types and conventions across NAHT benchmark tasks. The code of experiments is published on https://github.com/hsvgbkhgbv/axiomatic-rl-naht.
BibTeX
@misc{wang2026axiomatic,
  author = {Jianhong Wang and Yang Li and Samuel Kaski and Jonathan Lawry},
  title = {{An Axiomatic Framework for Reinforcement Learning in Open Multi-Agent Systems}},
  year = {2026},
  eprint = {2611.03301},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03301},
}
Figure