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

Introduction

Multi-agent systems (MAS) have become a central paradigm for modelling real-world domains such as smart grids [31], railway networks [40], and swarm robotics [17, 16], where multiple agents must coordinate under uncertainty. Reinforcement learning (RL) [27], and in particular cooperative multi-agent reinforcement learning (CMARL), has shown promise in solving such problems. However, existing CMARL methods typically assume that all agents are controllable and that team composition is fixed, which we call the closed multi-agent systems; these assumptions rarely hold in practice.

In many real-world scenarios, agents must operate in open multi-agent systems, where only a subset of agents is controllable and the remaining agents may be unknown or dynamically changing. This setting introduces two fundamental challenges: (i) generalisation to previously unseen teammate behaviours, and (ii) openness to varying team compositions. To address these challenges, recent work has introduced the n-agent ad hoc teamwork (NAHT) [29], which extends CMARL to settings with partially controllable and dynamically formed teams.

Although the NAHT objective is to maximise the team value over varying team compositions, this objective does not specify how agents can form cooperation in an open system with both controlled and uncontrolled agents. From the perspective of CMARL, an agent is represented by its individual value. This raises a fundamental question:

How should individual value functions be structured and learned to support cooperation in open multi-agent systems?

In this paper, we address this question from the perspective of cooperative game theory. Specifically, we introduce an NAHT decomposition that represents a team value by two parts: internal cooperation among controlled agents and external teamwork involving uncontrolled agents. This decomposition reveals a structural distinction between open and closed multi-agent systems, which is not innately captured by the NAHT objective.

Building on this structure, we propose an axiomatic framework to derive individual value functions, grounded in the axioms of the Shapley value [24, 12]. Rather than constructing individual value functions directly by the explicit form of the Shapley value, we derive the individual value function learning by enforcing its axioms (Efficiency, Symmetry and Linearity) as structural constraints. This yields a principled approach to designing learning algorithms, where individual value functions are shaped to satisfy some properties, such as cooperative game-theoretic properties applied in this paper. Notably, we prove in theory that enforcing these axioms on learning individual value functions recovers the Shapley value for Dec-POMDPs [18], while relaxing specific axioms leads to alternative payoff allocations, such as the Banzhaf index.

More importantly, our axiomatic framework also reveals a novel connection between cooperative game theory and reinforcement learning. In particular, we show that the Linearity axiom induces a structure equivalent to the truncated TD($\lambda$) [8], where the number of $n$-step return components can be estimated by the number of non-empty coalitions of cooperative games. This provides a theoretical explanation for the role of $n$-step returns and suggests a new perspective on the design of temporal-difference learning methods in the NAHT (see § 5.2).

NAHT includes two extreme cases: single-agent RL with an environment of other uncontrolled agents, and CMARL with fully controllable agents. The above result therefore extends to both settings.

Based on this axiomatic framework, we introduce two generic algorithmic templates: Shapley Machines, which enforce all axioms, and Banzhaf Machines, which relax the Efficiency axiom. These templates can be instantiated with existing RL algorithms, such as IPPO [11] and POAM, to yield practical methods for solving the NAHT.

We evaluate the proposed methods on modified MPE and SMAC benchmarks adapted to the NAHT setting [29]. Our results show that the proposed framework consistently improves learning efficiency and generalisation to unseen agent types and conventions. Furthermore, we demonstrate that relaxing specific axioms can lead to improved performance in certain regimes, highlighting the flexibility of the proposed axiomatic perspective. Due to the limit of space, we leave the related work section to Appendix § 9.

Background

N-Agent Ad Hoc Teamwork

In this section, we describe a problem setting for open multi-agent systems, referred to as n-agent ad hoc teamwork (NAHT) [29]. The main challenges of NAHT are as follows: (1) cooperating with potentially unknown types of teammates (generalization), and (2) coping with a varying number of uncontrolled teammates (openness). A decentralized partially observable Markov decision process (Dec-POMDP) [18] is considered to formalize the problem. There is a team of agents $M$ whose size is denoted as $M$, a state space $\mathcal{S}$, a joint action space $\mathcal{A} = \times_{i\in M}\mathcal{A}_i$, a per-agent observation space $\mathcal{O}_i$, a transition function $P_T : \mathcal{S} \times\mathcal{A} \to\Delta(\mathcal{S})$, a common reward function $R_t : \mathcal{S} \times\mathcal{A} \to\mathbb{R}$, a discount factor $\gamma\in[0, 1]$ and an episode length $T \in\mathbb{Z}^{+}$. Each agent receives observations via an observation function $O_i : \mathcal{S} \times\mathcal{A} \to\Delta(\mathcal{O}_i)$. $\mathcal{H}_i$ is defined as an agent $i$’s space of observation and action histories. Each agent is equipped with a policy $\pi_i : \mathcal{H}_i \to\Delta(\mathcal{A}_i)$.

In this problem, there are two groups of agents: a set of controlled agents denoted as $\mathcal{C}$ whose size is denoted as $N$, and a set of uncontrolled agents denoted as $\mathcal{U}$ whose size is denoted as $M-N$. As NAHT is an open multi-agent system, at the beginning of a multi-agent interaction process, a team of agents $\mathcal{M}$ are randomly drawn from the controlled agent pool and the uncontrolled agent pool. For conciseness, each controlled agent is characterised by its policy, and the set of controlled agents can be expressed as $\mathcal{C}(\theta)=\{\pi_i^\theta\}_{i=1}^N$. The above sampling procedure is denoted as $X(\mathcal{U},\mathcal{C}(\theta))$. The aim of NAHT is learning parameters $\theta$ to solve the following optimization problem:

where $\pi(\mathcal{M})$ denotes the joint policy of a team of agents $\mathcal{M}$. Note that different number of controlled agents $N$ would lead to various teams of agents $\mathcal{M}$; the expectation in Eq. (1) is usually approximated by a team value which we will specify in the following section.

Cooperative Games and Shapley Value

Representation of Cooperative Games. A cooperative game is usually described as a characteristic function $v : 2^\mathcal{M} \to\mathbb{R}_{\ge0}$, where $\mathcal{M}$ is a team of agents. An arbitrary cooperative game $v$ can be uniquely represented by a set of basis games $\{v^\mathcal{C} \mid\varnothing\ne\mathcal{C} \subseteq\mathcal{M}\}$ [12], as delineated in Definition 2.1. In this paper, we focus on investigating how cooperative games are approximated over a team of agents $\mathcal{M}$. Therefore, we only consider the function values $v(\mathcal{M})$ and $v^\mathcal{C}(\mathcal{M})$ for a team of agents $\mathcal{M}$ in the presentation of this work.³ As per previous work in the MARL [30], we consider the superadditive game as the game class of $\mathcal{G}$, which is suitable for a cooperative multi-agent task, such as NAHT (see Appendix § 10.2 for more details).

Shapley Value. Shapley value is a multidimensional linear transformation $\phi: \mathcal{G} \to\mathbb{R}^{M}$ defined on the set of cooperative game $\mathcal{G}$, given that there are $M$ agents in total. Each dimension of $\phi$ indicates the payoff allocation to an agent. It has been proved that Shapley value is a unique payoff allocation function on the set of cooperative games $\mathcal{G}$ which satisfies the following axioms: Efficiency, Symmetry and Additivity [12],⁴ highlighted in the following Theorem 2.2:

N-Agent Ad Hoc Teamwork Decomposition

To understand how learning differs in open multi-agent systems, we first characterise the cooperative-game structure of team values of the NAHT. Recall that in the NAHT a team consists of two groups of agents: a set of controlled agents $\mathcal{C}$, whose policies are optimized, and a set of uncontrolled agents $\mathcal{U}$, whose behaviours are unknown and may vary across episodes. Unlike the closed multi-agent systems, the performance of a team in the NAHT depends not only on coordination among controlled agents, but also on their ability to adapt to diverse and potentially unseen teammates. To make this distinction explicit, we represent a team value at a given state in the NAHT as a state-specific cooperative game that is the weighted sum of non-empty coalition basis games, from the perspective of cooperative game theory, as follows:

We decompose a team value into two parts. Based on generalisation of the cooperative game representation from the classic cooperative game as shown in Definition 3.1 and the game structure for the NAHT in Definition 3.2, we define a state-specific cooperative game $v_s$, as follows:

where $\mathcal{M}=C\cup U$ denotes the full team, $\mathcal{P}_{+}(\cdot)$ indicates the powerset of a set excluding the empty set, and each term corresponds to a contribution from a subset (coalition) of agents. The first term captures internal cooperation, i.e., interactions solely among controlled agents $C$. This corresponds to the standard task in the CMARL, where all agents are optimised jointly. The second term captures external teamwork, i.e., interactions between controlled agents $C$ and uncontrolled agents $U$, along with interactions among uncontrolled agents $U$. The second term is unique to open multi-agent systems, and reflects the need to coordinate with agents whose behaviours are not controlled and may vary across episodes. When all agents are controlled, i.e., $C=\mathcal{M}$, the external teamwork part vanishes, and the decomposition reduces to internal cooperation, recovering the fully controllable setting of the CMARL.

Implication. This decomposition highlights a fundamental difference between NAHT and CMARL: In the CMARL, all agents are controllable, and learning focuses exclusively on internal cooperation. In the NAHT, learning must additionally account for external teamwork with uncontrolled agents. Ignoring the external component effectively reduces the problem to a closed multi-agent system, which introduces bias and limits generalisation to unseen team compositions. The NAHT decomposition therefore provides a structural characterisation of openness, and it will serve as the foundation for the axiomatic framework introduced as follows.

From Shapley Axioms to Learning Algorithms

Building on the NAHT decomposition, we now derive an axiomatic framework for learning in open multi-agent systems. Our approach is based on the axioms of the Shapley value, which we interpret as structural constraints on individual value functions. In detail, we aim to show that how the individual values, as the output of a multidimensional linear transformation $\phi$ applied on a team value (represented as a cooperative game), satisfy the Shapley value’s axioms in learning. When we enforce all these axioms together, the Shapley-form individual values are uniquely shaped (see Theorem 4.7). Moreover, the axioms can be directly translated into algorithmic design principles: (1) The Efficiency axiom corresponds to reward shaping; (2) The Linearity axiom corresponds to truncated TD($\lambda$)-style updates; (3) The Symmetry axiom corresponds to individual value function structures. These principles will later lead to two generic algorithmic templates, referred to as Shapley Machine and Banzhaf Machine.

From Game Structure to Dec-POMDPs

The game structure for the NAHT in Definition 3.2 can be used to represent any sequential decision-making process evaluated in states. However, it does not necessarily imply that the process embedded in the game structure strictly follows the problem setting of the NAHT — Dec-POMDPs [18]. To bridge this gap, we augment the game structure with Markov dynamics and per-step common rewards to link the values of different states. When the instantiation of each state value is represented as $v_{s_t}(\mathcal{M}) = \mathbb{E}_{\pi}\left[\sum_{\tau=0}^{T-t-1}\gamma^\tau R_{t+\tau}\mid s_t\right]$, we can derive the famous $n$-step return in the RL [27][Chap. 7], with a horizon $\bar{n}$ to link $v_{s_t}(\mathcal{M})$ and $v_{s_{t+\bar{n}}}(\mathcal{M})$, such that

For ease of the following presentation, we simplify $v_{C,s}^{v_s(\mathcal{M})}(\mathcal{M})$ as $V(C,s)$,⁶ for all $C\subseteq\mathcal{M}$.

By Proposition 4.1 (see the proof and full explanation of Definition D.2 in Appendix § 12), we obtain the following formula that aligns state-specific basis games of various coalitions to their $n$-step returns with the corresponding horizons $n\in\{1,\ldots,m\}$, for all $\varnothing\ne C_n\subseteq C_{n+1}$, $C_m=\mathcal{M}$, such that

Linearity Axiom and Temporal-Difference Learning

The Linearity axiom plays a central role in connecting cooperative game theory to temporal-difference learning. We show this in the following Proposition 4.2 (see the proof in Appendix § 14):

In Proposition 4.2, the term within the $\mathbb{E}_{\pi}[\cdot]$ takes the form of truncated $\lambda$-return [27][Chap. 12], if all $k'_{C_n}$ are seen as weightings for the $n$-step return components. This indicates that the horizon can be estimated by the number of non-empty coalition basis games $m$.

In practice, we only need to learn $\phi_i(V(\mathcal{M},s_t))$ directly for each controlled agent $i\in C$. For brevity, we represent each $\phi_i(V(\mathcal{M},s_t))$ as $V_i(s_t)$ in the following paragraphs. Based on Eq. (5), we derive the $\lambda$-return error $\delta_{t,i}$ [27][Chap. 12] of truncated TD($\lambda$) (TTD($\lambda$)) for each agent $i$ purely from the game structure for the NAHT, such that

Efficiency Axiom and Reward Shaping

Note that $\phi(R_{t+\tau})$ in Eq. (6) has not yet been defined so far, because $R_{t+\tau}$ is not belonging to the state-specific cooperative game space $\mathcal{G}(s)$. As a result, it is necessary to represent $\phi(R_{t+\tau})$ in the form of $\phi(V(\mathcal{M},s))$, where $V(\mathcal{M},s)=v^{v_s(\mathcal{M})}_{\mathcal{M},s}(\mathcal{M})$ and $v^{v_s(\mathcal{M})}_{\mathcal{M},s}\in\mathcal{G}(s)$. The Efficiency axiom can address this problem. To satisfy the Efficiency axiom such that $\sum_{i=1}^{M}\phi_i(V(\mathcal{M},s_t))=V(\mathcal{M},s_t)$, we reasonably presume that its sufficient condition holds: $\sum_{i=1}^{M}\phi_i(R_t)=R_t$. Then, we demonstrate that how $\phi_i(R_t)$ is represented by the Efficiency axiom in the following Proposition 4.4 (see the proof in Appendix G):

By replacing $\phi_j(V(\mathcal{M},s_t))$ with $V_j(s_t)$ as there is in Eq. (6), we get that

The condition $\sum_{i=1}^{M}\phi_i(R_t)=R_t$ for deriving the Efficiency axiom is also referred to as additively factored immediate reward function. The following Theorem 4.5 shows that the Efficiency axiom always exists in the Dec-POMDP, given a factorization scheme of the transition function.

Since NAHT is considered in Dec-POMDPs (see § 2.1), to guarantee the feasibility of the Efficiency axiom as shown in Theorem 4.5, another constraint is added to implicitly facilitate searching for a factorization of the transition function, such that

Symmetry Axiom and Value Function Structure

The Symmetry axiom here means that two agents who contribute equally to every possible coalition (excluding the ones involving themselves) should receive equal payoff allocations [6][Chap. 2]. In the literature from Dubey [ [12], it was described as the permutation-equivariance of an multidimensional operator $\phi$ defined on a cooperative game, as shown in the following Theorem 4.6 (see the proof in Appendix G):

Next, we aim to show how to construct such an operator to fulfil the permutation-equivariance, such that $\phi_{\sigma(i)}(v_s)=\phi_i(\sigma(v_s))$ can be constructed in practice, where $\sigma$ means relabelling agent IDs to another ordering, e.g., $(1,2)\mapsto(2,1)$. For consistency of notations, we also denote $\phi_i(v_s(\mathcal{M}))$ as $V_i(s)$. This can be achieved by the following two conditions: (1) The operator $\phi$’s output is changeable consistently with reordering agent IDs, e.g., $(1,2)\mapsto(2,1)\Rightarrow(V_1(s),V_2(s))\mapsto(V_2(s),V_1(s))$; (2) The operator’s output with respect to each agent should be invariant to reordering agent IDs on its input $inp$ (e.g., the world information or other agents’ information), e.g., $V_i(\sigma(inp))=V_i(inp)$. Note that the second condition usually holds when other agents’ information is not directly included in the input to an agent’s individual value function, such as POAM [29] and IPPO [11].

From Shapley Axioms to Learning Algorithms

The algorithm that implements $V_i$ as agents’ individual values to fulfil the Efficiency, Linearity and Symmetry axioms through learning is named as Shapley Machine: (1) Shape individual rewards $\phi_i(R)$ following Eq. (8) and set Eq. (9) as a regularization term, to fulfil the Efficiency axiom. (2) Implement the TTD($\lambda$) following Eq. (6), to fulfil the Linearity axiom. The $k'_C > 0$ is implemented as geometric distribution following the convention of TTD($\lambda$) [27][Chap. 12]. (3) Structure the policy and individual value networks to fulfil the Symmetry axiom.

Since the Linearity axiom is a sufficient condition for the Additivity axiom (see Appendix § 10.3), the individual values satisfying all those axioms in implementation realizes Shapley values for the Dec-POMDPs, as highlighted in the following Theorem 4.7 (see the proof in Appendix § 15):

To realize the Shapley Machine, we use two base algorithms structurally satisfying the Symmetry axiom: POAM [29] and IPPO [11]. We then shape the objective functions following conditions imposed by other two axioms, to obtain the algorithms SM-POAM and SM-IPPO, respectively. The details of implementation are left to Appendix § 16.1.

Following the same principle of designing algorithms via axiomatic characterization, we also propose a variant that enforces the Linearity and Symmetry axioms while omitting Efficiency. Since the resulting $V_i$ aligns with the Banzhaf index, we call this algorithm Banzhaf Machine. Analogous to the implementation of Shapley Machine, its instantiation on POAM and IPPO are named as BM-POAM and BM-IPPO, respectively.

Remark 4.8. Banzhaf Machine is an algorithm generating $V_i$, fulfilling Symmetry and Linearity.

Experiments

In experiments, we evaluate the proposed SM-POAM, SM-IPPO, BM-POAM and BM-IPPO on the modified MPE-PP and SMAC benchmark tasks tailored to the NAHT settings [29], against the counterpart baseline algorithms POAM and IPPO. The uncontrolled agents are taken from five pre-trained policies, which were trained in fully controllable CMARL settings using the algorithms IPPO, MAPPO, VDN, QMIX, and IQL. To avoid confusion between the standard IPPO algorithm (trained under the CMARL settings) and the version trained within the NAHT process (where only a subset of agents is controllable), we refer to the latter as IPPO-NAHT.

More importantly, we validate the game structure for the NAHT, a core concept in our theory, by setting the number of $n$-step return components considered in TTD($\lambda$) using the number of basis games $m$. In practice, the horizon in our theoretical framework is the episode length. Since the number of basis games is far more than the preset episode length (511 vs. 150) in 10v1l, we approximate the number of basis games to the episode length as a trade-off. About the 8v9 scenario, the number of basis games needed in theory is close to the episode length (127 vs. 120), so the number of basis games can be naturally approximated by the episode length. As a result, for 8v9 and 10v1l Banzhaf Machine is equivalent to the baseline counterparts in implementation. The details of baselines, experimental settings and evaluation metrics are provided in Appendix § 16. All results are obtained by first computing each metric with 128 episodes and then averaging these per-seed metrics across 5 random seeds, with 95% confidence intervals reported.

Research Questions. We focus on the following research questions in experimentation: (1) Is the number of coalition$s$ $m$ used to decide the horizon of TTD($\lambda$) (see § 4.2) a reasonable choice? (2) Are all Shapley value’s axioms equally appropriate across scenarios? (3) Which axiom is key to generalization to unseen conventions or unseen agent types?

Main Results and Analysis

Answer to Question 1. We conduct experiments with varying numbers of basis games $m$ using SM-POAM as the candidate algorithm. As shown in Figure 2, learning performance in MPE-PP and

8v9 is sensitive to the choice of $m$, while in 5v6 it is comparatively robust. Overall, these results indicate that setting the number of $n$-step return components as the number of non-empty coalition basis games can nearly maximize learning performance, thereby providing an empirical evidence to support the mathematical rationale behind the Linearity axiom that derives this setting for the NAHT. Although we do not deny that there may exist other preferred choices of $m$ (as observed in the results of MPE-PP and 5v6), this does not undermine the effectiveness of using the number of non-empty coalition basis games, as a criterion, to decide the horizon for TTD($\lambda$) in practice.

Answer to Question 2. We evaluate all baselines alongside our proposed algorithms. For the large-scale tasks 8v9 and 10v11, the base algorithms IPPO-NAHT and POAM are effectively equivalent to BM-IPPO and BM-POAM under the approximation of $m$ due to limited episode lengths, and are therefore omitted in implementation. Figure 3 shows that, for either IPPO-NAHT or POAM, at least one of their Shapley Machine or Banzhaf Machine variants achieves the best performance. Recall that Banzhaf Machine corresponds to dropping the Efficiency axiom. In MPE-PP and 3sv5z with IPPO-NAHT as the base algorithm, Banzhaf Machine performs on par with Shapley Machine. In most other scenarios (except 10v11 with IPPO-NAHT), Shapley Machine outperforms Banzhaf Machine, although sometimes by a narrow margin. Moreover, comparisons between the base algorithms and their Banzhaf counterparts in MPE-PP, 5v6, and 3sv5z underscore the importance of the Linearity axiom. Overall, the results suggest that all three Shapley axioms generally enhance learning performance (in possibly unseen team compositions), but the Efficiency axiom can, in some cases, reduce it. This justifies the value of our proposed axiomatic framework, which provides a novel perspective on analysing performance through the falsifiable axioms. We believe that this axiomatic framework, as a paradigm, can help design new algorithms in the future.

Answer to Question 3. We evaluate all baselines alongside our proposed algorithms after training, to test their capability of generalization to unseen conventions and unseen agent types, respectively. The evaluation is conducted by the best model saved during training for each random seed of running experiments. Note that the wide range of confidence intervals is due to that the result averages performance across various number of controlled agents, and we further demonstrate the result per the number of controlled agents in Appendix I.5. It can be seen from fig:4a that SM-POAM outperforms both BM-POAM and POAM on all scenarios, except for the 10v11. This implies that in general all Shapley axioms may be instrumental in tackling unseen conventions. As seen from fig:4b, the performance of BM-POAM is comparable to and even better than SM-POAM in most cases. This implies that the Efficiency axiom could weaken the capability of generalization to unseen agent types. This phenomenon recurs, and becomes even more pronounced, in the evaluation of IPPO-NAHT related algorithms, as shown in fig:11b in Appendix I.3.

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 [29].

Number and Weightings of Basis Games

The weightings of basis games ($k'_C$ in Eq. (6)) are set by the probability values of a geometric distribution governed by $\lambda$, respecting the convention of RL. $\lambda$ will influence the shape of the geometric distribution. As $\lambda$ increases, the geometric distribution becomes a longer tail with the probability decaying slowly as the number of basis games $m$ increases. In other words, controlling $m$ can be achieved by simply changing the weightings of basis games, or equivalently, the $\lambda$, under the assumption of the geometric distribution. To verify this result in the NAHT, we conduct a case study, as shown in Figure 5. It can be observed that the number of effective basis games (the probability values over which are non-zero) for $m = 31$ and $m = 70$ is the same under $\lambda= 0.85$, resulting in nearly identical learning performance. This aligns with the conventional view of $\lambda$’s impact on TTD($\lambda$) in RL, primarily as a mechanism for controlling the tail length of the return [27][Chap. 12.3].

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.

In contrast, we demonstrate that even with the same number of basis games, the values of their corresponding weightings significantly influence the learning performance. As shown in Figure ??, given the same number of active basis games as $m = 7$, the learning processes with $\lambda= 0.5$ and $\lambda= 0.85$ result in very different performance. This provides an alternative insight into how weightings influence the TTD($\lambda$), different from the traditional RL perspective.

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 $\lambda$, under the same effective number of basis games.

Discussion, Limitations and Future Work

We studied reinforcement learning (RL) in open multi-agent systems through the lens of the n-agent ad hoc teamwork (NAHT), and introduced a cooperative game-theoretic framework that makes explicit how openness is distinguished from the cooperative multi-agent reinforcement learning (CMARL). Central to our approach is the NAHT decomposition, which separates internal cooperation among controlled agents from external teamwork with uncontrolled agents. Building on this structure, we proposed an axiomatic framework that derives value function learning from the Shapley axioms (Efficiency, Symmetry, and Linearity) by enforcing them as structural constraints. This perspective shifts the design of RL algorithms from heuristic constructions to principled designs in the NAHT. Since CMARL is an extreme case of the NAHT, our framework also works on it.

Our framework also reveals a novel connection between cooperative game theory and reinforcement learning: The Linearity axiom provides a theoretical explanation for the $n$-step return methods and the TTD($\lambda$) in the NAHT. This result is coincidentally related to the latest finding in single-agent offline RL that the $n$-step return methods with selected horizons can improve scalability to the increasing size of datasets [19]. As the NAHT encompasses the case of single-agent RL with other unknown agents, our framework suggests that, through the TTD($\lambda$), the increasing size of datasets could be a promising way to address the NAHT, which is left for the future work.

More broadly, the axiomatic perspective suggests new opportunities for exploring richer classes of weighting schemes beyond the standard geometric forms in temporal-difference learning for the NAHT (as demonstrated in § 5.2). For example, weightings $k_C$ satisfying $\sum(k_C)^2 = 1$ as shown in Figure 1 could define alternative weighting schedules. Because the NAHT problem can be reduced to the special case of single-agent RL with other uncontrolled agents, with an appropriate connection between the world model (transition function) and the concept of other uncontrolled agents, this result can be relaxed to the broader single-agent RL.

A key limitation of our work is that it is still unclear about how to deal with the scenario where the predefined horizon is far less than the number of non-empty coalition basis games. Our tentative strategy to mitigate this shortcoming is using the horizon under the minimal horizon schedule (e.g., $n_i = n_{i-1} + 1$) as the number of random basis games with no control. In the future work, this can be further investigated by relaxing the minimal horizon schedule (e.g., $n_i = f(i, s)$, where $f(i, s) \in\mathbb{N}$ is a function of states $s$ and coalition indices $i$), which can be used to control the effective number of basis games to be applied.

Acknowledgements

Jianhong Wang and Jonathan Lawry are supported by the Engineering and Physical Sciences Research Council (EPSRC) [Grant Ref: EP/Y028732/1]. Samuel Kaski is supported by UKRI Turing AI World-Leading Researcher Fellowship, EP/W002973/1 and EU, ERC ODD-ML 101201120.

References

Related Work

TD() in Reinforcement Learning and Multi-Agent Reinforcement Learning

Related work on temporal-difference learning with eligibility traces centers on the seminal TD($\lambda$) algorithm proposed by Sutton [1988], which unified one-step TD and Monte Carlo methods via a trace-decay parameter $\lambda$ and introduced the forward- and backward-view equivalence for efficient multi-step credit assignment. Subsequent theoretical analyses [9, 10, 28] established convergence guarantees and characterized the bias-variance trade-off inherent in $\lambda$-returns, while extensions by Watkins et al. [1989], Peng and Williams [1994] adapted eligibility traces for off-policy control, Q($\lambda$). Advances in function approximation, including true online TD($\lambda$) [23] and gradient-TD methods, further broadened applicability to large-scale and nonlinear settings, inspiring $n$-step return techniques such as generalized advantage estimation (GAE) [22] for policy optimization. In the multi-agent reinforcement learning (MARL), algorithms of PPO family such as MAPPO [39] and IPPO [11], applied GAE to optimize policies and thus used the TD($\lambda$) as the target values to train critics. Our work highlights the theoretical link between the truncated TD($\lambda$), denoted as TTD($\lambda$) [8], in the NAHT and the Linearity axiom of the Shapley value. It further shows that the number of $n$-step return components in the TTD($\lambda$) can be estimated by the number of non-empty coalition basis games. This insight provides a theoretical foundation that can inform the design of a broader class of MARL algorithms.

Theoretical Models for Ad Hoc Teamwork

We now discuss theoretical models describing the ad hoc teamwork (AHT). Brafman and Tennenholtz [1996] pioneered research into the AHT by investigating repeated matrix games involving a single teammate. Subsequent studies expanded this framework to scenarios with multiple teammates, notably by Agmon and Stone [2012]. Later, Agmon et al. [2014] further relaxed earlier assumptions by allowing teammates’ policies to be selected from a known set. Stone and Kraus [2010] initially formalized the AHT through collaborative multi-armed bandits, albeit under notable assumptions such as prior knowledge of teammates’ policies and environmental conditions. Albrecht and Ramamoorthy [2013] advanced this field significantly by introducing the stochastic Bayesian game (SBG), the first comprehensive theoretical framework accommodating dynamic environments and unknown teammate behaviours in the AHT. Building on the SBG, Rahman et al. [2021] proposed the open stochastic Bayesian game (OSBG), addressing the open ad hoc teamwork (OAHT). Zintgraf et al. [2021] modelled the AHT through interactive Bayesian reinforcement learning (IBRL) within Markov games, specifically targeting non-stationary teammate policies within single episodes. Xie et al. [2021] introduced the hidden parameter Markov decision process (HiP-MDP) to handle situations where teammates’ policies vary across episodes but remain stationary during individual episodes. Most recently, Wang et al. [2024] extended the OSBG by incorporating principles from cooperative game theory, introducing the open stochastic Bayesian coalitional affinity game (OSBG-CAG), which theoretically justifies a graph-based representation for joint Q-value functions and includes rigorous convergence proofs for Q-learning algorithms in open team settings. Our work adopts the perspective of cooperative game theory, introducing an NAHT decomposition based on state-specific cooperative games to address the NAHT. This well captures the structural difference between the CMARL and the NAHT. Based on the NAHT decomposition, we derive an axiomatic framework to address the NAHT, which introduces a novel perspective for solving this problem. The key difference in assumptions between the work by Wang et al. [2024] and our work is that the work by Wang et al. [2024] was built on the non-transferable utility games, while our work is built on the transferable utility games. For more details about the difference between these two cooperative game models, please refer to Chalkiadakis et al. [2011].

Shapley Value in Multi-Agent Reinforcement Learning

Early studies [30] incorporated the Shapley value into credit assignment scheme in a principled way and proposed an algorithm named as SQDDPG, underpinned by the equivalence between cooperative-game theoretical models in dynamic scenarios and the team reward Markov game. Wang et al. [2022] further improved the theory by proving the existence of the Shapley value under the team reward Markov game through construction, and proposed an algorithm, relying on the construction, named as SHAQ — an algorithm with promising convergence to find an optimal joint policy. It also shed light on the relationship between the Shapley value and the relevant value decomposition and credit assignment approaches for the CMARL. Li et al. [2021] improved the stability of SQDDPG and proposed an algorithm named Shapley Counterfactual Credits. Han et al. [2022] incorporated the Shapley value into the model-based PPO as each agent’s advantage value, through the estimated coalition values by trained transition and reward models. Chai et al. [2024] continued the idea from Han et al. [2022], by replacing the transition and reward models with more powerful world models. On the other hand, Xue et al. [2022] incorporated the Shapley value into multi-agent communication, as a criterion for forming communication between agents. One of our work’s aims is learning the Shapley value to address the NAHT, a generalized problem to the CMARL. More importantly, the Shapley value is learned by satisfying its axioms, rather than by constructing their explicit formulas as implemented in the previous work. This may help overcome the notorious learning instability issues caused by learning substantial “coalitional values” in the existing algorithms based on the Shapley value. Furthermore, the insight of axiomatic characterization can facilitate improving the flexibility of the Shapley value approaches in a wide variety of tasks. Specifically, one can safely drop any part of a learning algorithm, if it is justified that the targeting task does not align with the corresponding axiom.

Extra Background

λ-Return and TD(λ)

We now introduce an extension of return named λ-return. Mathematically, a λ-return $G_t^\lambda$ for infinite-horizon cases can be expressed as follows:

Similarly, the λ-return for finite-horizon cases can be expressed as follows:

Note that if $\lambda= 1$, updating according to the λ-return is a Monte Carlo algorithm. In contrast, if $\lambda= 0$, then the λ-return reduces to $G_{t:t+1}$, the one-step return. The Monte Carlo algorithm is known as its high variance but low bias, while one-step return is known as its low variance but high bias. For this reason, the change of λ can be seen as a tradeoff between bias and variance. The TD prediction using λ-return as the target value is referred to as TD(λ) [26].

A variant of TD(λ) by shaping $G_t^\lambda$ with a designated horizon $H \in\{t+1,\ldots,T\}$ is referred to as truncated TD(λ), shortened as TTD(λ) [8]. Mathematically, $G_t^\lambda$ with a designated horizon $H$ can be formulated as follows:

Note that in the convention of RL, the horizon $H$ is defined as the time difference from the starting point of an episode, denoted by $t = 0$.

Remark B.1. In this paper, to simplify the presentation of our work, we redefine the horizon as the time difference from each timestep $t$, denoted as $m$, such that $m = H - t$. With the new definition of horizon, we can rewrite the above formula of $G_t^{\lambda,H}$ as follows:

Superadditive Game and Cooperative Multi-Agent Reinforcement Learning

The superadditive game is a subclass of characteristic games that satisfies an additional condition: $v(C \cup D) \ge v(C) + v(D)$, for any two distinct coalitions $C, D \subseteq\mathcal{M}$ with $C \cap D = \emptyset$. Previous work in the CMARL Wang et al., [30] has shown the equivalence on the task objective function between the state-based superadditive games with action spaces and the team reward Markov games with coalition structures.⁸ Intuitively, the Shapley value is a solution to the stability of a team formation, resembling cooperation. Since the NAHT is a generalization of the CMARL, this conclusion is still valid in principle. It has been already proved that the Shapley value exists in superadditive games [24] and each game instance in superadditive games can be uniquely represented as $\sum_C k_C v_C^*$, where $k_C \ge0$ [12]. In cooperative game theory, any game can be transformed to a superadditive game if its value $v$ is transformed by a superadditive cover $v^*$ such that $v^*(C) = \max_{CS(C)} \sum_{D \in CS(C)} v(D)$ [13]. As a result, it will not lose generality if we consider the cooperative game space as superadditive games in our work.

Axioms of Shapley Values

Efficiency and Symmetry have been well investigated in the literature of multi-agent reinforcement learning [30, 15, 14, 32, 5], but Additivity still lacks attention. In detail, Additivity means that $\phi(w_1 + w_2) = \phi(w_1) + \phi(w_2)$, for any cooperative games $w_1, w_2 \in\mathcal{G}$. If we consider $m$ possible games, then we have the following expression: $\phi(\sum_{i=1}^{m} w_i) = \sum_{i=1}^{m} \phi(w_i)$, where $w_1, w_2, \ldots, w_m \in\mathcal{G}$ and the sum $\sum_{i=1}^{m} w_i$ can be seen as a game reproduced by the above games. Linearity is a stronger condition than Additivity [12, 38]. Specifically, Linearity requires $\phi(\sum_{i=1}^{m} \alpha_i w_i) = \sum_{i=1}^{m} \alpha_i \phi(w_i)$, for all $\alpha_i \in\mathbb{R}$. In contrast, Additivity only requires to satisfy the above equation when $\alpha_i = 1$. In our work, we use the Linearity axiom to establish the Additivity axiom, to adapt to our derivation.

Baseline Algorithms: POAM and IPPO

POAM. In general, POAM is an algorithm built upon IPPO [11]. The primary difference between POAM and IPPO is as follows: For each agent’s policy and value, in addition to its observation used in IPPO, POAM takes as input an embedding vector to predict other agents’ potential behaviours. More specifically, this embedding vector is trained by an encoder-decoder structure, wherein the encoder is modeled as RNNs and decoder is modeled as MLPs. For brevity, we use $-i$ to denote the set of all agents excluding agent $i$. Let $h_{t,i} = \{o_{k,i}, a_{k-1,i}\}_{k=1}^{t}$ denote agent $i$’s history of observations and actions up to timestep $t$. $e_{t,i} \in\mathbb{R}^{n}$ denote the resulting embedding vector of $n$ dimensions. The encoder parameterized by $\theta^e$ is defined as $f_{\theta^e}^{enc}: \mathcal{H}_i \to\mathbb{R}^{n}$. The embedding vector is decoded by two decoder networks: the observation decoder $f_{\theta^o}^{dec}: \mathbb{R}^{n} \to O_{-i}$, and the action decoder $f_{\theta^a}^{dec}: \mathbb{R}^{n} \to\Delta(\mathcal{A}_{-i})$. The decoder networks are respectively trained to predict the observations and actions of all other agents in the team at timestep $t$, $o_{t,-i}$ and $a_{t,-i}$, to encourage $e_{t,i}$ to contain information about collective behaviors corresponding to $h_{t,i}$. While the observation decoder directly predicts the observed $-i$’s observations, the action decoder predicts the parameters of a probability distribution over the $-i$’s actions $\pi_{-i}(a_{t,-i}; f_{\theta^a}^{dec}(f_{\theta^e}^{enc}(h_{t,i})))$. As we consider continuous observations and discrete actions, the loss function with using categorical distribution to model $\pi_{-i}$ is as follows:

For brevity, we define $g(h) := (h, f_{\theta^e}^{enc}(h))$ in the following description.

POAM employed generalized advantage estimation (GAE) [22] to form the policy gradient, and the value function used to form GAE is trained by the following loss function:

where $\hat{V}_{t,i}$ is the finite-horizon TD($\lambda$) return, for which the horizon is up to the episode length $T$. Each agent $i$’s GAE estimation is as follows:

where $\delta_{t,i}=R_t+\gamma V_i(g(h_{t,i}))-V_i^{\theta^c}(g(h_{t,i}))$ and $V_i(g(h_{t,i}))$ denotes the non-parameterized target individual value. Based on the GAE defined above, the policy optimization loss is defined as

IPPO. By removing the loss for the encoder-decoder structure as shown in Eq. (14) and replacing the input $g(h_{t,i})$ by $h_{t,i}$ in the above set of equations, we get the loss functions of IPPO.

Preliminary Results

Remark C.3. Following discussion in § 2.2, we aim to restrict the state-specific cooperative game class to the superadditive game. By Proposition C.2, we can conclude that $k'_C \ge0$ is a sufficient condition for $v_s$ belonging to the superadditive game class. In other words, $k'_C \ge0$ is a key condition for reaching cooperation within a team of agents. However, $k'_C = 0$ is a singularity condition, which leads to $0$ for all state-specific cooperative games in values, with no actual meaning in practice. For this reason, we only choose $k'_C > 0$ as the condition in our work.

Introducing Markovian Dynamics and Rewards to Game Structures

Based on the game structure for the NAHT in Definition 3.2, we now introduce Markovian dynamics to establish the link between the state-specific cooperative games of consecutive states, aligned with the environmental setting in Dec-POMDPs [18].

The only postulate is that each state-specific cooperative game can be represented in the form of rewards: $v_{s_t}(\mathcal{M}) = \mathbb{E}_{\pi}\left[\sum_{\tau=0}^{T-t-1} \gamma^\tau R_{t+\tau} \mid s_t\right] \in\mathcal{G}(s_t)$. By the convention of RL [27][Chap. 7], it is feasible to use the $n$-step return to express the $v_{s_t}(\mathcal{M})$ under a fixed horizon $\bar{n}$ to define the transformation, such that

For brevity, we rewrite $v^{v_s(\mathcal{M})}_{C,s}(\mathcal{M})$ as $V(C,s)$ for all $C \subseteq\mathcal{M}$. Then, we get the following fact:

Proof. The result can be immediately obtained from the definition of $V(C_i,s)$ in Definition D.2, and the statement that each $V(C_i,s)$ is equal to $V(\mathcal{M},s)$, directly following Fact D.1.

Justification of Coalition Ordering by Size and Horizon Assignment

Sketch of Justification Procedure

In this section, we will justify the insight behind the coalition ordering by size and horizon assignment, as shown in Definition D.2. In the beginning, we define a discrete-time stochastic process of TD error terms $(Z_n)_{n\in\mathbb{N}_0}$, where $v_{\pi}(s_t)$ denotes a generic state value function:

As a result, the $n$-step return $G_{t:t+n}$ has the following recursive relationship:

We first show in Lemma E.2 that, given $s_t=s$, the variance of the $n$-step return is non-decreasing with the return horizon when the TD-error sequence $(Z_n)$ has non-negative autocovariances. Specifically, extending the horizon from $n$ to $n+1$ adds the discounted TD-error term $\gamma^n Z_{n+1}$, whose covariance with the existing return is non-negative. The return variance therefore increases strictly when this additional term has positive conditional variance and remains unchanged when it has zero conditional variance. Then, we make the coalition-variance monotonicity assumption in Assumption E.3, which can be justified by Remark E.4 with evidence from the definition of the game structure for the NAHT and a verification experiment that partially supports Assumption E.3. In summary, Assumption E.3 concerns the following situation: The number of agents increases when more exploration is conducted (i.e., $C_i$ becomes larger in sizes), so more diverse agent types and behaviours emerge, resulting in that the estimation for the corresponding $V(C_i,s)$ has a higher variance.

By Lemma E.2 and Assumption E.3, we prove in Proposition E.5 that for the coalition enumeration $\{i\}$ there exist non-decreasing orderings of variances for both the sequence of basis games of coalitions non-decreasing by sizes and the sequence of $n$-step returns, under the horizon schedule $n_i=n_{i-1}+1$. This motivates us to define the following term under this monotone-variance regularity:

From the perspective of the coalition enumeration, the horizon schedule controls how the number of agents increases. The justification of Definition D.2 is completed.

Remark E.1. Among all sequences $(\tilde n_i)$ with $\tilde n_1=1$, $\tilde n_i>\tilde n_{i-1}$, and $\tilde n_i\geq|C_i|$ for all $i$, the schedule in Definition D.2 is pointwise minimal: $\tilde n_i\geq n_i$ for every $i$.

Remark E.1 highlights that alternative horizon schedules (e.g., $n_i=n_{i-1}+k$, $n_1=1$, $k>0$) exist, which offers additional design possibilities within our framework.

Mathematical Results Supporting for Justification

Proof. Use $G_{t:t+n+1}=G_{t:t+n}+\gamma^n Z_{n+1}$ and expand the variance conditioning on $s_t=s$, we can get the following formula:

We first prove that if $(Z_n)$ has non-negative autocovariances given $s_t=s$, then $n\mapsto\operatorname{Var}(G_{t:t+n}\mid s)$ is non-decreasing, as follows:

Using the sum of TD errors to represent the Monte Carlo error [27][Chap. 6], we have the following formula:

Given the linear property of covariance and a fact that the covariance of a constant is zero, we can get the following equation:

Therefore, if all autocovariances $\operatorname{Cov}(Z_i,Z_j\mid s)\geq0$, then $\operatorname{Cov}(G_{t:t+n},Z_{n+1}\mid s)\geq0$.

Since $\operatorname{Var}(Z_{n+1}\mid s)\geq0$ must hold, we obtain the following inequality:

That is, $n \mapsto\operatorname{Var}(G_{t:t+n} \mid s)$ is non-decreasing.

We next prove $\operatorname{Var}(G_{t:t+n+1} \mid s) = \operatorname{Var}(G_{t:t+n} \mid s)$ if and only if $\operatorname{Var}(Z_{n+1} \mid s) = 0$, as follows:

Given a fact that $\operatorname{Var}(G_{t:t+n+1} \mid s) = \operatorname{Var}(G_{t:t+n} \mid s)$ if and only if the following condition holds:

we now aim to prove that $\operatorname{Var}(Z_{n+1} \mid s) = 0$ is sufficient for $\operatorname{Cov}(G_{t:t+n}, Z_{n+1} \mid s) = 0$, and the proof is completed:

If a non-negative random variable (r.v.) $W \ge0$ satisfies $\mathbb{E}[W \mid s] = 0$, then $W = 0$ almost surely (a.s.) given $s$ [35][Chap. 9].

Apply this with $W = (Z_{n+1} - \mathbb{E}[Z_{n+1} \mid s])^2$. If $\operatorname{Var}(Z_{n+1} \mid s) = 0$, then

The covariance $\operatorname{Cov}(G_{t:t+n}, Z_{n+1} \mid s)$ can be expressed as the following formula:

Since $Z_{n+1} - \mathbb{E}[Z_{n+1} \mid s] = 0$ a.s., we get the following result:

Remark E.4 (Explanation and Verification for Assumption E.3). Recall from Section C that $v_{C,s}^{v_s(\mathcal{M})} = v_{C,s}^{1}$. Following Definition 3.1, we can express $v_{C,s}^{v_s(\mathcal{M})}$ as follows:

As described in Definition 3.2, a basis game $v_{C,s}^{v_s(\mathcal{M})}(D)$ can effectively evaluate the performance of a coalition of agents $C$¹⁰ with an agent-type composition denoted by $\times_{i \in D} T_i$, where $T_i$ indicates the agent $i$’s type. Therefore, we can get the following result: The larger the size of coalition $C$, the more agent-type compositions are required to be explored during agent interactions, so that the value of $V(C, s) := v_{C,s}^{v_s(\mathcal{M})}(\mathcal{M})$ can predict $v_s(\mathcal{M})$. In other words, as the size of coalition $C$ increases, higher variance of the value prediction is incurred to get $v_s(\mathcal{M})$, due to the growing agent-type composition space. Similarly, if the sizes of two coalitions are equal, their variances are equal.

To make Assumption E.3 more convincing, we additionally provide a new proof-of-concept experiment to demonstrate its reasonableness. The key idea behind Assumption E.3 is that a larger coalition $C_i$ is associated with more complicated interactions among various types of agents, so there is a larger functional class to describe the $V(C_i, s)$ and therefore the variance during training would be larger (for searching the appropriate function).

Because we are not allowed to change the number of agents in the existing environment (which is fixed with pre-trained teammates), we partially prove Assumption E.3 by showing the relation between the agent-type compositions and variances: We would like to show that when the number of agent-type compositions increases, the variance will not decrease. We design three settings denoted as Exp A, Exp B and Exp C to capture different numbers of agent-type compositions. The number of agent-type compositions in descent would be Exp A $\geq$ Exp B $\geq$ Exp C, and the variance should be in the same order in expectation.¹¹

In Figure 7, it can be observed that the relation between variances of three setups above is almost always as the following order: Exp A $\ge$ Exp B $\ge$ Exp C, over the whole training procedure (i.e., Exp A bounded above by Exp B, and Exp B bounded above by Exp C).¹² This result conforms to our expectation above and thus partially verifies the reasonableness of Assumption E.3.

Proof. Since $n_i=n_{i-1}+1$ is strictly increasing, Lemma E.2 yields non-decreasing variance in $i$, with strictness when the added step contributes nonzero variance. Assumption E.3 gives non-decreasing $\operatorname{Var}(\widehat{V}(C_i,s))$ as $|C_i|$ (hence $i$) increases.

Proof for Results of Incorporating Linearity Axiom

Proposition F.1. Given the expression of state-specific basis games in Eq. (4), applying the Linearity axiom to state-specific cooperative games expressed as Eq. (2) can lead to the following equation:

Proof. By Lemma C.1, a state-specific cooperative game expressed as Eq. (2) can be equivalently represented by the form: $v_s=\sum_{\varnothing\ne C\subseteq\mathcal{M}}k'_C\cdot v_{C,s}^{v_s(\mathcal{M})}$ with setting $z=v_s(\mathcal{M})$ and $k'_C=\frac{k_C}{v_s(\mathcal{M})}$, and $v_s(\mathcal{M})\ne0$.¹³ Herein, the set of $v_{C,s}^{v_s(\mathcal{M})}$ become a set of new state-specific basis games and $k'_C$ are their corresponding weightings. Introducing a linear multidimensional operator $\phi: \mathcal{G}(s) \to\mathbb{R}^{M}$ (i.e., supposing that $\phi$ satisfies the Linearity axiom) on a state-specific cooperative game $v_s$ defined by Lemma C.1, we derive the following formula:

Recall that $v_{C_n,s_t}^{v_{s_t}(\mathcal{M})}$ is denoted by $V(C_n,s_t)$, and $v_{s_t}(\mathcal{M})$ is denoted by $V(\mathcal{M},s_t)$. Substituting (4) into the Linearity axiom in (19) and applying linearity of the expectation operator, we obtain the following formula:

Proof for Results of Incorporating Efficiency and Symmetry Axioms

Proposition G.1 (Representation of Transformed Rewards). Given the condition that $\sum_{i=1}^{M}\phi_i(R_t)=R_t$, each agent’s payoff allocation defined on rewards $R_t$, i.e., $\phi_i(R_t)$ can be expressed as

Proof. Recall that $\phi(\cdot)\in\mathbb{R}^{M}$ is a multidimensional linear transformation,${}^{13}$ where $M$ is the number of agents. We now express $\phi(R_t)$ according to the Efficiency axiom.

To satisfy the Efficiency axiom such that $\sum_{i=1}^{M}\phi_i(V(\mathcal{M},s_t))=V(\mathcal{M},s_t)$, it is reasonable to assume that $\sum_{i=1}^{M}\phi_i(R_t)=R_t$. In other words, each agent’s value expansion can be expressed independently in its own $\phi_i(R_t)$, justified by Theorem 4.5.

Next, we aim to show how each $\phi_i(R_t)$ is expressed in terms of $\phi(V(\mathcal{M},s_t))$.

It is not difficult to observe that for each agent $i\in\mathcal{M}$, we have

By the condition $\sum_{i=1}^{M}\phi_i(R_t)=R_t$, we can derive a formula such that

Since $\phi_j(R_t)=\phi_j(V(\mathcal{M},s_t))-\gamma\phi_j(V(\mathcal{M},s_{t+1}))$, we can express $\phi_i(R_t)$ as follows:

Theorem G.2. The payoff allocation operator satisfying permutation-equivariance is a sufficient condition for the Symmetry axiom.

Proof. Let $\mathcal{M}=\{1,\ldots,M\}$. Let $\mathcal{G}$ be the set of cooperative games $v:2^{\mathcal{M}}\to\mathbb{R}$, and $S_C$ be a permutation group acting on $C\subseteq\mathcal{M}$.

Let $S_C$ act on an arbitrary $C\subseteq\mathcal{M}$ by exchanging agents:

Let a payoff allocation operator $F:\mathcal{G}\to\mathbb{R}^{M}$ output payoffs $F(v)=(F_1(v),\ldots,F_n(v))$.

Let $S_M$ act on $\mathbb{R}^{M}$ by permuting coordinates: $(\sigma\cdot x)_i:=x_{\sigma^{-1}(i)}$.

$F$ is permutation-equivariant if

Recall that agents $i$ and $j$ are symmetric in $v$ if

Equivalently, the transposition $\tau=(i\ j)$ leaves the game $v$ invariant:

Next, we aim to show $F_i(v)=F_j(v)$ to prove the statement in the theorem.

By Eqs. (20) and (21), we have

Note that $\tau\cdot F(v)$ is just $F(v)$ with coordinates $i$ and $j$ swapped. Therefore, $F(v)=\tau\cdot F(v)$ implies the $i$-th and $j$-th entries are equal:

Experimental Details

Implementation Details

Our algorithm is built upon POAM and IPPO. All loss functions for training the encoder-decoder model, policy networks and value networks have been remained. Please refer to Appendix § 10.4 for details. For conciseness, we only list the novel loss functions proposed in this paper.

Shapley Machine

We now describe the details about implementing our proposed algorithm, referred to as Shapley Machine. In general, our algorithm is established based on the base algorithms POAM and IPPO, with modification to fulfil all the three axioms of the Shapley value: Efficiency, Linearity and Symmetry. Since the Symmetry axiom has been realised in POAM and IPPO, we only need to fulfil the Efficiency and Linearity axioms.

Implementing the Linearity Axiom. In general, both POAM and IPPO have implemented TD($\lambda$), which does not strictly conform to the principle of the Linearity axiom. To address this problem, we change the TD($\lambda$) to TTD($\lambda$), where the number of $n$-step return components is equal to the number of the non-empty coalition basis games, as informed by our theory. Note that in some scenarios the episode length is smaller than the number of non-empty coalition basis games. In these cases, the TTD($\lambda$) can be reduced to the TD($\lambda$) for the finite-horizon tasks with the episode length as $T$, equivalently, the TTD($\lambda$) with $m = T$. Alternatively, we can select a value of $m$ for each task based on extra conditions, which is left for the future work. In this paper, we set $m = T$ for the scenarios 8v9 and 10v11. For the 8v9 scenario, the episode length as 120 is not too far from the number of non-empty coalition basis games as 127. For the 10v11 scenario, the episode length is 150, while the number of non-empty coalition basis games is 511.

Implementing the Efficiency Axiom. By introducing the partial observation in Dec-POMDPs, the Eq. (8) we have derived the condition for realizing the Efficiency axiom is transformed as follows:

where $V_j(h_{t,j})$ indicates an agent $j$’s non-parameterized individual value. During the practical training procedure, the $V_j(h_{t,j})$ generated by the individual value network could be severely inaccurate in the beginning, which may result in the instability of learning. To mitigate this issue, we add an extra coefficient $\alpha\in(0,1)$ to the term $\sum_{j \ne i} \left(V_j(h_{t,j}) - \gamma V_j(h_{t+1,j})\right)$, such that

This coefficient $\alpha$ can be either manually set up as a fixed value, or implemented by a scheduler starting from 0 to some preset upper limit. The $R_t$ in $L_\theta(h_{t,i}, a_{t,i})$ and $L^c_\theta(h_{t,i})$ is replaced by the above $\phi_i(R_t)$. To clarify this change, the two new losses are expressed as $\hat{L}_\theta(h_{t,i}, a_{t,i})$ and $\hat{L}^c_\theta(h_{t,i})$.

Furthermore, it is needed to search the underlying factorization scheme of the transition function in Dec-POMDPs, according to Theorem 4.5. To implement this requirement, we need to fulfil the following condition:

The above equality is implemented as a regularization term during training.

To maintain consistency with the critic losses, we consider to use the $\lambda$-return denoted by $\hat{G}^{\lambda}_t$ to represent $V(\mathcal{M}, h_t)$. In turn, the above equation can be expressed as

where each $\hat{G}_{t:t+n}$ contributing to the $\hat{G}^{\lambda}_t$ represented in TTD($\lambda$) is expressed as follows:

Substituting the above formula into Eq. (23), we can obtain the regularization term, referred to as the efficiency loss for one timestep $t$, as follows:

In summary, the total loss function of the Shapley Machine for POAM (SM-POAM) is as follows:

where $T$ is the episode length; $\beta_1, \beta_2 \in(0,1)$ are two coefficients to control the importance of the two losses; $C_t$ indicates the controlled agent set at timestep $t$ and $\mathcal{M}$ indicates the ad hoc team following the convention in Wang et al. [ [29].

Similarly, the total loss function of the Shapley Machine for IPPO (SM-IPPO) is as follows:

Implementation of $k'_{C}>0$. As mentioned in Section C, it is necessary to fulfil $k'_{C}>0$ for reaching cooperation, which can be implemented following the convention of TD($\lambda$) in the RL [26]. Specifically, the weightings for $m$ basis games ($k'_{C_1}, k'_{C_2}, \cdots, k'_{C_m}$) are generated using a geometric distribution $P_{\lambda}$ with the parameter $0<\lambda<1$, such that $k'_{C_n}=P_{\lambda}(n)$, resulting a tuple $((1-\lambda),(1-\lambda)\lambda,\cdots,(1-\lambda)\lambda^{m-1},\lambda^m)$. With this condition, Eq. (6) becomes the well-known truncated TD($\lambda$), shortened as TTD($\lambda$) [8].

Partial Observations. In practice, a controlled agent is only able to receive an observation, following the settings of Dec-POMDPs. Therefore, an agent is required to infer the state of the environment as an individual hidden state, through the history of observations. To this end, the policy and individual networks are realized by recurrent neural networks (RNNs) (e.g., GRUs [7]), where observations or representations transformed from observations are used as inputs.

Implementation of the Symmetry Axiom. It can be observed that both POAM and IPPO are implemented by the sharing parameters, with agent ID to differentiate agent identities. Given an agent ID, its input is either individual observations or individual observations + teammate embeddings, where the teammate embeddings are transformed from individual observations through an encoder network.

Estimation of Uncontrolled Agent Individual Values. We maintain all possible controlled agent policy and individual value networks as implemented by Wang et al. [ [29], given that the maximum number of controlled agents is known in the experimental settings of the NAHT, but only part of controlled agents in an episode can make decision. Thanks to the parameter sharing technique, this can be simply implemented by maintaining only a policy and/or an individual value network, with a set of agent IDs to represent and differentiate all possible controlled agents. During the training phase, the uncontrolled agents’ individual values are also required to implement the Efficiency axiom, as informed in Eq. (9), but they are unknown to the controlled agents; all training paradigms that we design should be based on the view of the controlled agents. To address this problem, the uncontrolled agents’ individual values are approximated by the maintained individual value function with the agent IDs of those inactive controlled agents, given that the observations of the uncontrolled agents are available for controlled agents during training.

POAM and IPPO

The implementations of POAM and IPPO have been detailed in Appendix B.4.

In summary, the total loss function of POAM is as follows:

The total loss function of IPPO is as follows:

Banzhaf Machine

The overall loss function and implementation of the Banzhaf Machine closely follow those of POAM and IPPO. The only distinction is that Banzhaf Machine employs the TTD($\lambda$) in place of the TD($\lambda$) that is applied in POAM and IPPO.

Experimental Domains

We now briefly introduce the experimental domains for running experiments. If one would like to know more about details, please refer to Wang et al. [2025].

MPE Predator Prey (MPE-PP)

The MPE Predator Prey (MPE-PP) environment is a predator-prey task implemented within the Multi-Agent Particle Environment (MPE) framework. It simulates interactions within a two-dimensional space populated by two static obstacles, where three pursuer agents must cooperate to capture a single adversarial evader. A successful capture is defined as at least two pursuers simultaneously colliding with the evader, upon which the pursuers receive a positive reward of +1. If the capture is unsuccessful, no reward is granted. This environment is designed to test the ability of agents to coordinate under spatial and dynamic constraints. The length of an episode is $T=100$,

The StarCraft Multi-Agent Challenge (SMAC)

The StarCraft Multi-Agent Challenge (SMAC) serves as a benchmark suite for evaluating CMARL algorithms in partially observable settings. Built on top of the StarCraft II game engine, SMAC presents a variety of micromanagement tasks where each agent (e.g., a Marine or Stalker) operates based on limited local observations and must coordinate actions with teammates to overcome enemy units. In this work, we focus on four specific SMAC scenarios: 5v6: five allied Marines versus six enemy Marines, 8v9: eight allied Marines versus nine enemy Marines, 10v11: ten allied Marines versus eleven enemy Marines, 3s5z: three allied Stalkers versus five enemy Zealots. At each timestep, agents receive a shaped reward proportional to the damage they inflict on opponents, along with bonus rewards of 10 points for each enemy defeated and 200 points for achieving overall victory by eliminating all adversaries. The total return is normalized so that the maximum achievable return in each scenario is 20. The action space in SMAC is discrete, enabling each agent to choose actions such as attacking a particular enemy, moving in a specific direction, or remaining idle. The length of an episode varies across different scenarios: 3s5z with $T=250$, 5v6 with $T=70$, 8v9 with $T=120$ and 10v11 with $T=150$.

Evaluation Metrics

For in-distribution evaluation, the mean return (or winrate) is computed over $E$ randomly sampled episodes. In each episode, we form a joint policy $\pi^{(N)}$ by sampling $N$ agents uniformly from $\mathcal{C}$ and the remaining $M-N$ agents from $\mathcal{U}$. For the out-of-distribution (OOD) evaluation, the M–N score [29] is applied. Given a set of controllable agents $\mathcal{C}$ and uncontrolled agents $\mathcal{U}$, the M–N score measures how well mixed teams of these agents cooperate in the NAHT setting. The score is computed exhaustively by changing the number of controllable agents included in the team. Specifically, for each $N\in\{1,\ldots,M-1\}$, we form a joint policy $\pi^{(N)}$ by sampling $N$ agents uniformly from $\mathcal{C}$ and the remaining $M-N$ agents from $\mathcal{U}$. The mixed teams are then evaluated on the task for $E$ episodes. This procedure yields $(M-1)\cdot E$ returns (or winrates) in total, whose average defines the M–N score.

In this experiment, each convention of an uncontrolled agent is a random seed that pretrains it. For the OOD evaluation on the unseen conventions, the M–N score is computed by averaging the per-convention M–N scores across 4 other conventions for each agent type. For the OOD evaluation on the unseen agent types, the per-convention M–N score is computed by averaging the per-convention M–N score across 5 conventions for each unseen agent type. All results are obtained by first computing each metric with 128 episodes and then averaging these per-seed metrics across 5 random seeds, with 95% confidence intervals.

Experimental Settings

The training procedure of the NAHT process is briefly introduced here. For more details, please refer to Wang et al. [ [29]. For each scenario (e.g. MPE, 3sv5z, 5v6, 8v9 and 10v11), there are five groups of pretrained agents (e.g. IQL, MAPPO, VDN, QMIX and IPPO) acting as the uncontrolled agents. Given that each task specifies a fixed total number of agents $M$, the number of controlled agents is $N$. For each episode evaluation, the number of uncontrolled agents $M-N$ is sampled, and then a group of pretrained agents is sampled.¹⁵ The distribution for all sampling procedures are modelled as the multinational distribution with no replacement. Each uncontrolled agent executes the greedy policy in both training and testing procedures. In contrast, each controlled agent executes the on-policy sampling via the parameterized policy during the training procedure, while the greedy policy during the testing procedure.

Hyperparameter Settings

Since our algorithm is established based on POAM and IPPO, most hyperparameter settings follow that in Wang et al. [ [29]. First, the actors and critics are implemented in recurrent neural networks, with full parameter sharing. Specifically, they are implemented by two fully connected layers followed by a GRU layer and an output layer. Each layer has 64 dimensions with a ReLU activation function, and layer normalization is applied. The encoder-decoder networks for inferring agent characteristics are also implemented in parameter sharing. The encoder is implemented by a GRU layer, followed by a fully connected layer with a ReLU activation function and an output layer. The decoder is implemented by two fully connected layers with ReLU activation functions, followed by an output layer. Adam Optimizer is used to train all models. The detailed hyperparameters for experiments are shown in Tables 1 and 2. For the scenarios such as MPE, 3sv5z and 5v6, the values of $m$ are set as the number of non-empty coalition basis games. For the scenarios such as 8v9 and 10v11, the values of $m$ are simply set as the length of an episode (see Appendix § 16.1 for more details). Note that the term $\sum_{j\ne i}(V_j(s_t)-\gamma V_j(s_{t+1}))$ in shaped rewards is standardised to match the scales of standardised rewards. To stabilize learning in large-scale scenarios, we add a value loss clip to Shapley Machine and Banzhaf Machine for POAM on both 8v9 and 10v11, and for IPPO on 10v11 only.

Algorithm	Task	$\lambda$	$m$	$\alpha$	$\beta_1$	$\beta_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
	3sv5z	0.85	7	N/A	0.5	N/A
	5v6	0.85	31	N/A	0.5	N/A
	8v9	0.95	120	N/A	0.5	N/A
	10v11	0.95	150	N/A	0.5	N/A

Hyperparameter	Value
LR	0.0005
Epochs	5
Minibatches	1
Buffer size	256
Entropy coefficient	0.05
Clip	0.2
ED LR	0.0005
ED epochs	1
ED Minibatches	1
Optim_alpha (Adam)	0.99
Optim_eps (Adam)	0.00001
Use_obs_norm	True
Use_orthogonal_init	True
Use_adv_std	True
Standardise_rewards	True
num_parallel_envs	8

Computational Resources

All experiments are conducted on Intel Xeon Gold 6230 CPUs and Nvidia V100-SXM2 GPUs. Each experiment run on MPE takes approximately 7 hours, utilizing 20 CPU cores and 1 GPU. Each experiment run on SMAC takes between 8 and 19 hours, utilizing 30 CPU cores and 1 GPU. All experiments are trained with 20M timesteps. The post-training evaluation for each scenario takes between 6 and 16 hours, utilizing 8 CPU cores and 1 GPU.

Additional Experiments

Empirical Evidence for the Strength of the Axiomatic Framework

We now discuss the phenomenon observed from the performance under stochastic policy exploration during training. Discussing this phenomenon is meaningful: When a machine learning algorithm is deployed and has to adapt to real-world environments through online learning due to the mismatch between simulators and real-world environments, it is expected that random exploration diminishes rapidly over time to avoid the damage on real-world environments (e.g. physical systems).

Recall that the PPO family algorithms implement exploration by the natural stochastic policy sampling from the learned policy distribution and maximizing policy entropy. As seen from Figure 8, either Shapley Machine or Banzhaf Machine can outperform their base algorithm counterparts with a large margin. The reasons are as follows: As shown in Figure 9, policy entropy decreases rapidly over the course of training (except for the IPPO implementation on 3sv5z, which underperforms due to incompatibility between IPPO and the task). This indicates that the learned policies become more deterministic than those of the base algorithms, despite all methods being optimized with an entropy-maximization objective. A possible explanation for this phenomenon is illustrated in Figure 10: The critic losses of Shapley and Banzhaf Machines decrease faster than that of their base algorithm counterparts. This provides evidence for the advantage of structured individual value functions under our proposed axiomatic framework.

Analyzing Effects of Efficiency Axioms

We now demonstrate the association between the changing of the shaping rewards and the response of corresponding testing returns. As shown in Figure 13, the shaped reward increases in the beginning and then gradually reaches a plateau. The efficiency loss also exhibits the similar phenomenon. As shown in Figure 14, it can be observed that when instability happens during training as evidenced by the sudden changes of test returns, the shaped reward can consistently manifest this situation (as highlighted in red vertical dashed lines). This feature is crucial in the NAHT, since it could be a frequent and typical case when an unseen agent appears in the environment, which may perturb the training stability. This justifies the effectiveness of the shaping rewards $\phi_{i}(R_{t})$ we propose to fulfil

the Efficiency axiom. More importantly, this highlights the importance and necessity of the Efficiency axiom to perceive and measure the changing of environments.

Extra Results of OOD Evaluation

We also conducted experiments on evaluating the OOD performance of Shapley Machine and Banzhaf Machine on the base algorithm IPPO (IPPO-NAHT). As seen from Figure 11a, Banzhaf Machine is competitive to Shapley Machine on dealing with unseen conventions. Although it seems that the result is opposite to the conclusion drawn from the POAM related results, the underlying reason could be the general weaker performance of IPPO than POAM due to the lack of agent modelling, as shown in Figure 15. This could inhibit the full capability of Shapley Machine. As seen from Figure 11b, the general performance of Banzhaf Machine is better than Shapley Machine. This is consistent with the conclusion drawn from the POAM related results. In Figure 12, we show additional comparisons between algorithms: POAM vs. IPPO, SM-POAM vs. SM-IPPO and BM-POAM vs. BM-IPPO. We find no strong evidence that the axioms are sensitive to the choice of base algorithm.

Potential Instability for Large-Scale Scenarios

During our repeated trials, we observe that the performance of Shapley Machine is not stable in large-scale scenarios (e.g. 8v9 and 10v11), compared with in small-scale scenarios (e.g. MPE-PP, 3sv5z and 5v6). We now analyze the potential reason behind this phenomenon. As observed from Figure 16 and Figure 17, it can be confirmed that the instability of shaped rewards is the key reason to cause the instability of learning procedure for large-scale scenarios. According to the functionality of shaping rewards discussed in Appendix § 17.2, we hypothesize that the instability could be caused by the unstable changing of value difference in the shaping reward: $\sum_{j \ne i} (V_j(s_t) - \gamma V_j(s_{t+1}))$. Specifically, when the number of agents increases, the accumulating prediction error of individual value functions will be amplified.

To mitigate the above issue, we have added the value loss clip to stabilize the learning procedure of individual value functions for the large-scale scenarios such as 8v9 and 10v11. As seen from Figure 3, even with the value loss clip the instability of SM-IPPO is still out of control. This could be the cascading effect caused by the lack of agent modelling in contrast to SM-POAM, the instability of which is far beyond the capability of value loss clip. This reflects the value of agent modelling in POAM for tackling the large-scale multi-agent scenarios.

As seen from Figure 18, the learning procedures with the value loss clip for the SM-POAM apparently perform more stably than those without. This verifies our initial hypothesis. Because this strategy will slow down and even hinder the performance for the other three scenarios, we have not posted this as a common strategy. We believe this deserves further investigation in the future before any claims can be made about its general performance.

OOD Evaluation Across Different Numbers of Controlled Agents

We report the results on unseen conventions and agent types for each specific number of controlled agents $N$ in Figure 19-Figure 22, by fixing the $N$ value in the $M$–$N$ score. We would like to highlight that the NAHT problem is a far more difficult task to deal with than the CMARL problem. As a result, our work is only a starting point in this direction, and we believe that the potential stability issue is due to the lack of more exact axioms tailored to the concrete task to face. However, following the framework and principle we develop in this work, this can be improved by considering more axioms that we do not cover in this work, from either the game-theoretical perspective or the physical world.

Broader Impact

This paper introduces an axiomatic framework for learning in open multi-agent systems, with potential applications in domains such as smart grids, transportation networks, and multi-robot systems. By providing a principled foundation for coordinating with partially controllable and potentially unknown agents, the proposed approach may improve the reliability, adaptability, and generalisation of multi-agent systems deployed in real-world environments.

Positive Impacts

A key potential benefit lies in infrastructure systems, such as power distribution networks, where coordination among heterogeneous and partially controllable agents (e.g., distributed energy resources, consumer devices) is essential. More robust and generalisable learning algorithms could improve efficiency, reduce energy waste, and enhance grid stability. Similarly, in autonomous transportation and logistics, improved coordination with unknown or non-cooperative agents may lead to safer and more efficient traffic management and resource allocation.

The proposed axiomatic perspective may also contribute to trustworthy AI, as it provides interpretable structural constraints on learning algorithms. By grounding value function design in well-established principles from cooperative game theory, the framework may improve transparency and facilitate reasoning about agent behaviour in safety-critical settings.

Potential Risks and Negative Impacts

Despite these benefits, the deployment of open multi-agent systems introduces several risks. First, improved coordination capabilities could be applied in strategic or adversarial settings, such as automated market manipulation or competitive multi-agent environments, where agents learn to exploit or collude with others. The ability to generalise to unseen agent behaviours may amplify such risks.

Second, systems trained under the proposed framework may exhibit unintended coordination behaviours when interacting with human users or legacy systems, especially if the underlying assumptions about cooperation do not hold. In safety-critical domains, such behaviours could lead to undesirable or unpredictable outcomes.

Third, while the framework introduces structural constraints, it does not inherently guarantee fairness or alignment with human values. The allocation of value among agents, even when principled from a game-theoretic perspective, may not correspond to socially desirable outcomes in all contexts.

NeurIPS Paper Checklist

Claims

Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

Answer: [Yes]

Justification: All key contributions covered in the abstract and introduction can be well matched to the theoretical results described in Sections 3 and 4, as well as experimental results as shown in Section 5. The scope of this paper is restricted to n-agent ad hoc teamwork, an open multi-agent system problem.

Guidelines:

• The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.

• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.

• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

Limitations

Question: Does the paper discuss the limitations of the work performed by the authors?

Answer: [Yes]

Justification: We have discussed the key limitation of this work in the Section 6. The key limitation lies in a parameter of our algorithm that could not well adapt to large-scale agent teams, but it can be improved by relaxing the assumption of our theoretical framework.

Guidelines:

• The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.

• The authors are encouraged to create a separate “Limitations” section in their paper.

• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

Theory assumptions and proofs

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

Answer: [Yes]

Justification: All theoretical claims are numbered and we have clarified clearly the corresponding sections in Appendix that include their proofs. In short words, all proofs and justifications for assumptions are given in Appendices C to G.

Guidelines:

• The answer [N/A] means that the paper does not include theoretical results.

• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

• All assumptions should be clearly stated or referenced in the statement of any theorems.

• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

• Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

• Theorems and Lemmas that the proof relies upon should be properly referenced.

Experimental result reproducibility

Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

Answer: [Yes]

Justification: All implementation details, evaluation metrics and hyperparameters for reproducing results are disclosed in Appendices H.1, H.3 and H.5.

Guidelines:

• The answer [N/A] means that the paper does not include experiments.

• If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in

some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

Open access to data and code

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

Answer: [Yes]

Justification: The opensource code is uploaded as supplemental materials, along with instructions to reproduce key results.

Guidelines:

• The answer [N/A] means that paper does not include experiments requiring code.

• Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

• While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

Experimental setting/details

Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?

Answer: [Yes]

Justification: All training and testing details are shown in Appendices H.3 and H.5.

Guidelines:

• The answer [N/A] means that the paper does not include experiments.

• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

• The full details can be provided either with the code, in appendix, or as supplemental material.

Experiment statistical significance

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

Answer: [Yes]

Justification: All experimental results are demonstrated following mean with 95% CIs over 5 random seeds.

Guidelines:

• The answer [N/A] means that the paper does not include experiments.

• The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

• The assumptions made should be given (e.g., Normally distributed errors).

• It should be clear whether the error bar is the standard deviation or the standard error of the mean.

• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).

• If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

Experiments compute resources

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

Answer: [Yes]

Justification: All computer resources for experiments are disclosed in Appendix H.6.

Guidelines:

• The answer [N/A] means that the paper does not include experiments.

• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).

Code of ethics

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

Answer: [Yes]

Justification: This paper does not violate any term in the code of ethics.

Guidelines:

• The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.

• If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.

• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).

Broader impacts

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

Answer: [Yes]

Justification: We have clearly discussed both positive and potentially negative impacts in Appendix J.

Guidelines:

• The answer [N/A] means that there is no societal impact of the work performed.

• If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.

• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.

• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.

• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).

Safeguards

Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?

Answer: [N/A]

Justification: Our work is mainly about theoretical aspects, with no relation to such issues.

Guidelines:

• The answer [N/A] means that the paper poses no such risks.

• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.

• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.

• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

Licenses for existing assets

Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

Answer: [Yes]

Justification: All baseline algorithm (codes) we used for experiments have been credited by citing the corresponding work.

Guidelines:

• The answer [N/A] means that the paper does not use existing assets.

• The authors should cite the original paper that produced the code package or dataset.

• The authors should state which version of the asset is used and, if possible, include a URL.

• The name of the license (e.g., CC-BY 4.0) should be included for each asset.

• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.

• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

• If this information is not available online, the authors are encouraged to reach out to the asset’s creators.

13. New assets

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

Answer: [Yes]

Justification: The code for training has been with a clear documentation.

Guidelines:

• The answer [N/A] means that the paper does not release new assets.

• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

• The paper should discuss whether and how consent was obtained from people whose asset is used.

• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.

14. Crowdsourcing and research with human subjects

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

Answer: [N/A]

Justification: Our work has no relation to this term.

Guidelines:

• The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.

• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.

• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.

15. Institutional review board (IRB) approvals or equivalent for research with human subjects

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

Answer: [N/A]

Justification: This paper is with no relation to this term.

Guidelines:

• The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.

• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.

• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.

Declaration of LLM usage

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.

Answer: [N/A]

Justification: The core part of research does not involve LLMs.

Guidelines:

• The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.

• Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.