An Axiomatic Framework for Reinforcement Learning in Open Multi-Agent Systems
Authors: Jianhong Wang, Yang Li, Samuel Kaski, Jonathan Lawry
Organizations: INFORMED-AI Hub, University of Bristol · School of Computer Science, Shanghai Jiao Tong University · ELLIS Institute Finland · Aalto University · University of Manchester · School of Engineering Mathematics and Technology, University of Bristol
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.
Figures & tables
Figure 1: Geometric illustration of the NAHT decomposition. The red and blue vectors are two games represented by different basis game sets, denoted by ws(M) and us(M) . Their difference is measured by the θ . The shading area in red indicates the range of generated cooperative games with that kC≥0 and ∑(kC)2=1 .
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 .
Figure 3: Evaluation curves during training in NAHT.
Figure 4: Out-of-distribution (OOD) evaluation after training, assessing unseen conventions and unseen agent types during training, between learned agents (POAM, SM-POAM and BM-POAM) and uncontrolled agent types (IPPO, VDN, IQL, QMIX and MAPPO). The performance is evaluated by averaging all pairings of N controlled and M−N uncontrolled agents and their corresponding random seeds, called M–N score ( Wang et al., 2025 ) .
Figure 5: Controlling the number of effective basis games can be implemented by changing the parameters to control the shape of weightings of basis games. Note that the probability values for m>31 are nearly zero.
Figure 6: Influence of different values of basis games given the same number of effective basis games m . Note that the shapes of geometric distributions vary significantly with different values of λ , under the same effective number of basis games.
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Empirical verification for Assumption E.2 .
Algorithm
Task
λ
m
α
β1
β2
Shapley Machine
MPE-PP
0.85
7
0.01
0.5
0.01
3sv5z
0.85
7
0.01
0.5
0.01
5v6
0.85
31
0.01
0.5
0.001
8v9
0.95
120
0.01
0.5
0.001
10v11
0.95
150
0.01
0.5
0.001
Banzhaf Machine
MPE-PP
0.85
7
N/A
0.5
N/A
Appendix
Table 1: Key hyperparameters of Shapley and Banzhaf Machine: λ indicates the parameter for the weighting functions of TTD( λ ), m indicates the number of basis games, α controls the importance of the term ∑j=i(Vj(st)−γVj(st+1)) in Eq. ( 22 ), β1 controls the importance of the critic loss ∑i∈ML^θc(ht,i) , and β2 controls the importance of the efficiency loss Lθce(ht) .
Hyperparameter
Value
LR
0.0005
Epochs
5
Minibatches
1
Buffer size
256
Entropy coefficient
0.05
Clip
0.2
Appendix
Table 2: Common hyperparameters of RL settings.
Figure 8: Performance under the stochastic exploration policy during training in NAHT.
Figure 9: Policy entropy across scenarios during training in NAHT.
Figure 10: Critic loss across scenarios during training in NAHT.
Figure 11: Out-of-distribution (OOD) evaluation after training, assessing unseen conventions and unseen agent types during training, between learned agents (IPPO-NAHT, SM-IPPO and BM-IPPO) and uncontrolled agent types (IPPO, VDN, IQL, QMIX and MAPPO). The performance is evaluated by averaging all pairings of N controlled and M−N uncontrolled agents and their corresponding random seeds, called M–N score [ Wang et al., 2025 ] .
Figure 12: Out-of-distribution (OOD) evaluation after training, assessing unseen conventions during training, between learned agents (IPPO-NAHT, SM-IPPO, and BM-IPPO) and uncontrolled agent types (IPPO, VDN, IQL, QMIX and MAPPO). The performance is evaluated by averaging all pairings of N controlled and M−N uncontrolled agents and their corresponding random seeds, called M–N score [ Wang et al., 2025 ] .
Figure 13: One run of MPE to show the variation of test return, shaped reward and efficiency loss.
Figure 14: One run of 5v6 to show the variation of test return, shaped reward and efficiency loss.
Figure 15: Average evaluation performance on unseen conventions across 4 SMAC tasks. The star denotes the in-convention baseline, and the histograms denotes the unseen conventions.
Figure 16: A case of 8v9 with SM-POAM to show the instability of learning progress via the mean shaped rewards. The range bounded by two red dashed lines shows the fluctuation of the learning process.
Figure 17: A case of 10v11 with SM-POAM to show the instability of learning progress via the mean shaped rewards. The range bounded by two red dashed lines shows the fluctuation of the learning procedure.
Figure 18: Comparison between the learning procedure of SM-POAM with and without the value loss clip in the 8v9 and 10v11 scenarios.
Figure 19: Out-of-distribution (OOD) evaluation after training, assessing unseen conventions during training, between learned agents (IPPO-NAHT, SM-IPPO and BM-IPPO) and uncontrolled agent types (IPPO, VDN, IQL, QMIX and MAPPO).
Figure 20: Out-of-distribution (OOD) evaluation after training, assessing unseen agent types during training, between learned agents (IPPO-NAHT, SM-IPPO and BM-IPPO) and unseen uncontrolled agent types (IPPO and VDN).
Figure 21: Out-of-distribution (OOD) evaluation after training, assessing unseen conventions during training, between learned agents (POAM, SM-POAM, and BM-POAM) and uncontrolled agent types (IPPO, VDN, IQL, QMIX and MAPPO).
Figure 22: Out-of-distribution (OOD) evaluation after training, assessing unseen agent types during training, between learned agents (POAM, SM-POAM and BM-POAM) and unseen uncontrolled agent types (IPPO and VDN).
Sparse rewards are a major bottleneck in multi-agent reinforcement learning (MARL), where simultaneous learning induces non-stationarity and makes reward design especially delicate. Reward shaping can accelerate learning, but in the multi-agent setting it must preserve the strategic structure of the problem rather than merely improve short-term optimization. We propose Automatic Reward-shaping in Multi-agent Systems (ARMS), a self-supervised reward shaping framework for MARL that learns dense shaping signals from sparse environmental rewards through trajectory ranking. Since single-agent trajectory-ranking guarantees do not directly transfer to MARL, we reformulate policy invariance through conditional best-response reasoning, and show that if certain conditions hold, then using shaping rewards preserves each agent's best-response set under fixed opponent policies, and consequently preserve the set of Nash equilibria. Guided by this perspective, ARMS alternates between policy learning and reward learning while sharing shaping parameters across agents for efficiency. Experiments in a partially observable multi-agent pathfinding domain show that ARMS improves sampling efficiency under increasing reward sparsity and agent count, generalizes to unseen environments, and reveals a MARL-specific failure mode in which limited exploration and coupled policy--reward dynamics induce oscillatory behavior. Increasing exploration mitigates this effect and stabilizes learning. To the best of our knowledge, ARMS is the first automatic reward shaping framework for MARL whose design is motivated by a game-theoretic equilibrium-preservation result.
Elie Abboud, Oren Gal
Department of Marine Technologies University of Haifa
Multi-agent systems are widely used in safety-critical applications that require coordinated behavior under strict safety constraints. Existing approaches face a fundamental trade-off: learning-based methods achieve strong empirical performance but lack theoretical safety guarantees, while control-theoretic methods enforce safety but often lead to overly conservative and inefficient behaviors. We propose a hierarchical multi-agent reinforcement learning framework that enforces hard safety constraints under mild assumptions at low level via a constraint manifold, while enabling effective coordination through high-level policy learning. Our approach provides theoretical safety guarantees in the multi-agent setting and yields stationary learning dynamics, thereby enabling stable and efficient training. Empirically, our method achieves competitive performance while maintaining nearly perfect safety rates, and generalizes effectively to varying numbers of agents and obstacles.
Zihao Guo, Jianing Zhao, Ling Li +3
1King’s College London · University of California, Berkeley · 3The Alan Turing Institute
Multi-objective multi-agent reinforcement learning (MOMARL) addresses agent coordination and objective trade-offs simultaneously while optimising overall system performance. Existing work tends to treat multi-agent cooperation and multi-objective optimisation as largely independent components of a learning problem, which amounts to an exorbitant complexity except in trivial cases. We study here whether the structure provided by multiple objectives can itself be exploited to facilitate cooperation, rather than being treated as an additional optimisation challenge. We formulate MOMARL at both the team and individual levels and introduce objective-wise counterfactual credit assignment to evaluate each agent's contribution across the team objectives. We propose Meta-Gradient Informed Multi-Objective Multi-Agent Reinforcement Learning (MIRL), with static (MIRL-S) and dynamic (MIRL-D) variants. By incorporating meta-gradient information, MIRL enables agents to learn how to prioritise objectives individually while collectively optimising the system-level objective, allowing the multi-objective structure to directly guide cooperation. Experiments on a multi-objective multiple particle environment show that our methods improve Pareto-front quality over baselines, with the dynamic variant achieving the strongest performance.
Qiyue Xia, J. Michael Herrmann
School of Informatics, University of Edinburgh, Edinburgh, United Kingdom