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

AI summary

Overview

Research area: Cooperative multi-agent reinforcement learning and cooperative game theory, specifically reinforcement learning in open multi-agent systems via n-agent ad hoc teamwork (NAHT).

Technical level: Advanced. The paper builds on Dec-POMDP formalism, cooperative game theory (Shapley value, Banzhaf index, basis games), and temporal-difference learning; it presupposes comfort with multi-agent RL notation and axiomatic characterisations of payoff allocations.

Scope: The paper proposes a cooperative game-theoretic, axiom-based framework for deriving individual value functions in open multi-agent systems, instantiates it as two algorithmic templates (Shapley Machines and Banzhaf Machines), and evaluates them on NAHT-adapted MPE and SMAC benchmarks.

What This Paper Is About

Standard cooperative multi-agent reinforcement learning (CMARL) assumes every agent is controllable and the team composition is fixed, which the authors call closed multi-agent systems. In contrast, real-world settings such as smart grids are open: only a subset of agents can be controlled, while the rest are unknown or change over time. The paper asks how individual value functions should be structured and learned so that controlled agents can cooperate in such open systems, and answers by treating the Shapley axioms (Efficiency, Symmetry and Linearity) as structural constraints on value learning rather than as heuristic design choices.

Key Contributions

1. An NAHT decomposition. The authors express a state-specific team value as a sum of two parts: internal cooperation (basis games over coalitions of controlled agents only) and external teamwork (basis games involving uncontrolled agents). The external term vanishes when all agents are controlled, recovering the CMARL setting, so the decomposition isolates exactly what makes openness structurally different.

2. An axiomatic framework for value learning. Rather than writing down the Shapley value formula directly, the paper derives individual value functions by enforcing the Shapley axioms as constraints: Efficiency corresponds to reward shaping plus a value-sum regularisation term, Linearity corresponds to truncated TD(λ)-style updates, and Symmetry corresponds to the structure of individual value/policy networks.

3. A theoretical bridge to temporal-difference learning. The paper shows the Linearity axiom yields a truncated TD(λ) form (Cichosz, 1994), where the number of n-step return components can be estimated by the number of non-empty coalitions. It also proves (Theorem 4.7) that enforcing Efficiency, Symmetry and Linearity makes the learned individual values the Shapley value for Dec-POMDPs (Oliehoek et al., 2016).

4. Two generic algorithmic templates, with four instantiations. Shapley Machines enforce all three axioms; Banzhaf Machines enforce Symmetry and Linearity while relaxing Efficiency, yielding values aligned with the Banzhaf index. Instantiated on POAM and IPPO, these give SM-POAM, SM-IPPO, BM-POAM and BM-IPPO. Code is released at https://github.com/hsvgbkhgbv/axiomatic-rl-naht.

Main Findings

• The coalition count is a workable horizon criterion. Using the number of non-empty coalition basis games to set the number of n-step return components in TTD(λ) nearly maximises learning performance. Performance in MPE-PP and 8v9 is sensitive to the choice of m, while in 5v6 it is comparatively robust. The specific counts used are m = 7 in MPE-PP, m = 31 in 5v6, and m = 120 in 8v9.

• Axiom-enforcing variants beat their base algorithms. For either IPPO-NAHT or POAM, at least one of the Shapley Machine or Banzhaf Machine variants achieves the best performance. In most scenarios Shapley Machine outperforms Banzhaf Machine, sometimes narrowly, with exceptions such as MPE-PP and 3sv5z with IPPO-NAHT, where Banzhaf Machine performs on par, and 10v11 with IPPO-NAHT.

• Efficiency is not always beneficial. All three axioms generally help, but dropping Efficiency (Banzhaf Machine) can improve generalisation to unseen agent types. The paper states the Efficiency axiom can in some cases reduce performance, which the authors present as evidence that the framework supports falsifiable analysis of design choices.

• Shapley Machine generalises best to unseen conventions. In out-of-distribution evaluation, SM-POAM outperforms both BM-POAM and POAM on all scenarios except 10v11, suggesting all Shapley axioms are instrumental for handling unseen conventions.

• Banzhaf Machine is competitive or better on unseen agent types. BM-POAM is comparable to and in most cases better than SM-POAM, implying the Efficiency axiom may weaken generalisation to unseen agent types; the pattern recurs, and is more pronounced, for IPPO-NAHT-related algorithms (reported in the appendix).

• Linearity matters for base-algorithm improvement. Comparisons between base algorithms and their Banzhaf counterparts in MPE-PP, 5v6 and 3sv5z underscore the importance of the Linearity axiom.

• Weighting shape matters independently of coalition count. With λ = 0.85, m = 31 and m = 70 give the same number of effective (non-zero-probability) basis games and nearly identical performance. But with the same m = 7, λ = 0.5 and λ = 0.85 produce very different learning, giving an alternative view of how λ affects TTD(λ) beyond tail length.

• Large benchmarks collapse to the baselines. In 10v11 the number of basis games (511) far exceeds the episode length (150), and in 8v9 it is 127 versus 120, so the coalition count is approximated by episode length. Consequently, for 8v9 and 10v11 the Banzhaf Machine is equivalent to its baseline counterpart in implementation, and IPPO-NAHT and POAM are omitted as separate baselines.

Methodology in Plain English

The authors start from an existing problem setting, n-agent ad hoc teamwork (NAHT), in which a team is sampled each episode from a pool of controlled agents plus a set of uncontrolled agents, and the goal is to maximise expected discounted return over varying team compositions. They represent the team value at a given state as a cooperative game: a weighted sum of simple "basis games", one per non-empty coalition, in the style of Dubey (1975). Splitting the coalitions into those made only of controlled agents and those involving uncontrolled agents gives the internal/external decomposition.

They then ask what happens if the per-agent value assignments must respect the three Shapley axioms, and translate each axiom into a concrete learning rule. Efficiency leads to a shaped per-agent reward that subtracts other agents' value differences, plus a regulariser forcing individual values to sum to the team value. Linearity leads to a truncated TD(λ) error term in which each coalition corresponds to an n-step return, with weights following a geometric distribution as is conventional for TTD(λ). Symmetry leads to network designs whose outputs permute consistently with agent ID relabelling and which do not take other agents' information as direct input; POAM and IPPO are chosen as base algorithms because they already satisfy this structurally.

The resulting recipe is the Shapley Machine; removing the Efficiency constraint gives the Banzhaf Machine. Experiments compare SM-POAM, SM-IPPO, BM-POAM and BM-IPPO against IPPO-NAHT and POAM on NAHT-adapted MPE-PP and SMAC tasks, with uncontrolled agents drawn from five pre-trained policies (IPPO, MAPPO, VDN, QMIX, IQL). Each metric is computed over 128 episodes and averaged across 5 random seeds with 95% confidence intervals; out-of-distribution tests use MAPPO, QMIX and IQL for training and IPPO and VDN for testing, scored by the M–N score of Wang et al. (2025).

Why This Matters

Impact on research. The paper reframes multi-agent RL algorithm design as satisfying explicit, falsifiable axioms rather than assembling heuristic losses. It also supplies a theoretical account of why n-step returns and truncated TD(λ) are natural in open multi-agent settings, and it shows Banzhaf Machines as a principled alternative when Efficiency is undesirable — a route to systematic ablation of design principles.

Real-world applications (domains named in the paper):

• Smart grids, where a utility controls only some devices while others behave unpredictably.
• Railway networks, where coordination involves operators with differing control.
• Swarm robotics, where robots must cooperate with teammates of unknown or changing type.
• Any deployment where controlled agents must generalise to unseen teammate behaviours and varying team compositions.

Industry relevance. Any system where a company's agents must interoperate with third-party or human-operated agents — energy management, logistics, traffic, robotics fleets — faces exactly the openness the paper formalises. The Shapley/Banzhaf templates are drop-in wrappers around existing algorithms (demonstrated on IPPO and POAM), which lowers the cost of adoption.

Future Directions

• Scaling to large datasets and long horizons. The discussion links the n-step-return result to recent single-agent offline RL findings (Park et al., 2026) that n-step returns with selected horizons improve scalability as dataset size grows, and suggests this as a promising route for NAHT — the sentence is cut off in the supplied text, so the full argument is not reported.

• Choosing the horizon when coalitions outnumber the episode length. In 10v11 the theory requires 511 basis games against an episode length of 150, forcing an approximation that makes Banzhaf Machines identical to their baselines. A better principled treatment of this regime remains open.

• Understanding when to drop Efficiency. Since relaxing Efficiency helps on unseen agent types but hurts on unseen conventions in some tasks, a systematic account of which axioms suit which distribution shift is an open question the authors explicitly invite.

• Designing new axiom sets. The authors position the framework as a general paradigm in which other properties beyond the Shapley axioms could be imposed as constraints to derive further algorithms.

Target Audience

Multi-agent RL researchers and graduate students working on ad hoc teamwork, open team composition, or value decomposition; game theorists interested in operationalising Shapley and Banzhaf allocations inside learning loops; and applied researchers in energy, transport, and robotics who need agents that cooperate with teammates they do not control. Readers should be comfortable with Dec-POMDP notation and TD learning; the paper places related work in Appendix A and proofs in Appendices B–G for those who want the formal detail.

Authors’ 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.