N-agent Ad Hoc Teamwork
Authors: Caroline Wang
Arrasy Rahman
Ishan Durugkar
Elad Liebman
Peter Stone
Venue: NeurIPS 2024 poster (2024)
Keywords: ad hoc teamwork
reinforcement learning
multi-agent systems
multi-agent reinforcement learning
Primary area: reinforcement_learning
TL;DR: Proposes a generalization of ad hoc teamwork to the N-agent setting.

Abstract: Current approaches to learning cooperative multi-agent behaviors assume relatively restrictive settings. In standard fully cooperative multi-agent reinforcement learning, the learning algorithm controls *all* agents in the scenario, while in ad hoc teamwork, the learning algorithm usually assumes control over only a *single* agent in the scenario. However, many cooperative settings in the real world are much less restrictive. For example, in an autonomous driving scenario,  a company might train its cars with the same learning algorithm, yet once on the road, these cars must cooperate with cars from another company. Towards expanding the class of scenarios that cooperative learning methods may optimally address, we introduce $N$*-agent ad hoc teamwork* (NAHT), where a set of autonomous agents must interact and cooperate with dynamically varying numbers and types of teammates. This paper formalizes the problem, and proposes the *Policy Optimization with Agent Modelling* (POAM) algorithm. POAM is a policy gradient, multi-agent reinforcement learning approach to the NAHT problem, that enables adaptation to diverse teammate behaviors by learning representations of teammate behaviors. Empirical evaluation on tasks from the multi-agent particle environment and StarCraft II shows that POAM improves cooperative task returns compared to baseline approaches, and enables out-of-distribution generalization to unseen teammates.

N-Agent Ad Hoc Teamwork
Caroline Wang
Arrasy Rahman
Department of Computer Science The University of Texas at Austin caroline. wangeuteaaaaaa.....e..mm edu
Department Computer Science
The University of Texas at Austin arrasy$cs utexas.
Ishan Durugkar
Elad Liehman"
Sony AI
Amazon
ishan. wwwtnuuuuuuuruonccooomm com
1iebelad00amazon.ccomm com
Peter Stone
Department of Computer Science
The University of Texas at Austin and Sony AI pstoneêcs. utexas edu
Abstract
Current approaches to learning cooperative multi-agent behaviors assume rela- tively restrictive settings. In standard fully cooperative multi-agent reinforcement learning, the learning algorithm controls all agents in the scenario, while ad hoc teamwork, the learning algorithm usually assumes control over only single agent in the scenario. However, many cooperative settings in the real world are much less restrictive. For example, in an autonomous driving scenario, company might train its cars with the same learning algorithm, yet once on the road, these from another company. Towards expanding the
must cooperate with class of scenarios that cooperative learning methods may optimally address, we introduce aggett ad hoc teamwork (NAHT), where set of autonomous agents must interact and cooperate with dynamically varying numbers and types of team- mates. This paper formalizes the problem, and proposes the Policy Optimization with Agent Modelling (POAM) algorithm. POAM is a policy gradient, multi-agent reinforcement learning approach to the NAHT problem that enables adaptation diverse teammate behaviors by learning representations of teammate behaviors. Empirical evaluation on tasks from the multi-agent particle environment and Star- Craft II shows that POAM improves cooperative task returns compared to baseline approaches, and enables out-of-distribution generalization to unseen teammates.
Introduction
Advances in multi-agent reinforcement learning (MARL) [3] have enabled agents to learn solutions various problems rero-sum games, social dilemmas, adversarial team games, and cooperative tasks [37, 8, 19, 21, 33]. Within MARL, cooperative multi-agent reinforcement learning (CMARL) a paradigm for learning agent teams that solve common task via interaction with each other and the environment [22, 28, 46]. Recent CMARL methods have been able to learn impressive examples of cooperative behavior from scratch in controlled settings, where agents are controlled by the same learning algorithm [33, 38, 4]. A related paradigm for learning cooperative behavior is ad hoc
Work was done while at SparkCognition.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

MARL
AHT
NAHT
???
???
Figure I: Left: CMARL algorithms assume full control over all M agents in a cooperative scenario. Center: AHT algorithms assume that only a single agent is controlled by the learning algorithm. while the other M 1 agents are uncontrolled and can have diverse, unknown set of behaviors. Right: NAHT, the paradigm proposed by this paper, assumes that potentially varying N agents are controlled by the learning algorithm, while the remaining M N agents are uncontrolled.
teamwork (AHT). contrast to CMARL,, the objective of AHT to create single agent policy that can collaborate with previously unknown teammates to solve common task [27, 39].
While a large and impressive body of work on CMARL and AHT exists, the current literature has largely examined scenarios in which either complete control over all agents is assumed, or only single agent is adapted for cooperation [33, 38, 21, 4, 15]. Even learning methods for handling cooperative tasks in open multiagent systems [46], which encompass one of the most challenging settings where agents may enter or leave the system anytime, either operate assuming full control over all agents [17, 23] or only single adaptive agent [31, 18, 32].
However, real-world collaborative scenarios-e.g search-and-rescue, robot fleets for warehouses might demand agent subteams that are able to collaborate with unfamiliar teammates that follow different coordination conventions. Towards producing agent teams that more flexible and applicable to realistic cooperative scenarios, this paper formalizes the problem setting of N N-agent ad hoc teamwork (NAHT), which set of autonomous agents must interact with uncontrolled set of teammates to perform a cooperative task. When there is only a single ad hoc agent, NAHT equivalent AHT. On the other hand, when all ad hoc agents are jointly trained by the same algorithm and there are no uncontrolled teammates, NAHT is equivalent to CMARL. Thus, the proposed problem setting generalizes both CMARL and AHT.
Drawing from ideas in both CMARL and AHT, we introduce Policy Optimization with Agent Modelling (POAM). POAM is policy-gradient based approach for learning cooperative multi-agent team behaviors, in the presence of varying numbers and types of teammate behaviors. It consists of (I) an agent modeling network that generates vector characterizing teammate behaviors, and (2) an independent actor-critic architecture, which conditions on the learned teammate vectors to enable adaptation to a variety of potential teammate behaviors. Empirical evaluation on multi-agent particle environment (MPE) and StarCraft II tasks shows that POAM learns to coordinate with a changing number of teammates of various types, with higher competency than CMARL, AHT, and naive NAHT baseline approaches. An evaluation with out-of--istribute teammates also reveals that POAM's agent modeling module improves generalization to cut-of-distribuiien teammates, compared to baselines without agent modeling.
2 Background and Notation
The NAHT problem is formulated within the framework of Decentralized Partially Observable
Markoy Decision Processes, or Dec-POMDPs [7]. Dec-POMDP consists of M agents, a state space S, action space A. per-agent observation spaces O,, transition function T S x A + (SS common reward function r S x A + ( (thus defining cooperative task), discount factor E [0, 1] and horizon T Z, which represents the maximum length of an interaction, or episode. Each agent observes the environment via its observation function, O x A A(O.). The state space is factored such that S = S x ... x Sas. where S; for i E {1 ... M) corresponds to the state space for agent The action space is defined analogously. Denoting H, as its space of localized observation and action histories, agent acts according a policy, H. H; + ((A.). The notation -i represents all agents other than agent i, and is applied throughout the paper to the mathematical
(A))) denotes the space of probability distributions set S.

---

objects introduced above. For example, the notation O_ refers to the cross product of the observation space of all agents other than In the following, we overload r' to refer both the reward function, and the task defined by that reward function, whereas r denotes the reward at time step 4.
NAHT Problem Formulation
Drawing from the goals MARL and AHT [39], the goal of N-agent ad hoc teamwork is to create set of autonomous agents that are able to efficiently collaborate with both known and unknown teammates to maximize return on a task. The goal is formalized below.
Let C' denote a set of ad hoc agents, If the policies of the agents in C' are generated by an algorithm, we say that the algorithm controls agents in C. Since our intention to develop algorithms for generating the policies of agents in C, we refer to agents in C' as controlled. Let U denote set of uncontrolled agents, which we define as all agents the environment not included in C. Following
Stone et al., we assume that agents in U are not adversarially minimizing the objective of agents in C.
We model open system of interaction, in which random selection of M agents from sets C. and U must coordinate to perform task r. For illustration, consider a warehouse staffed by robots developed by companies A and B, where there is box-lifting task that requires three robots accomplish. If Company A's robots are controlled agents (corresponding to C), then some robots from Company A could collaborate with robots from Company (corresponding to U) to accomplish the task, rather than requiring that all three robots come exclusively from A or B. Motivated thus, we introduce team sampling procedure X (U, C.. At the beginning of each episode, X samples team of M agents by first sampling N < M, then sampling N agents from the set C and M N agents from U. We restrict consideration to teams containing at least one controlled agent, i.e N 2 1. We consider X a problem parameter that is not under the control of any algorithm for generating ad hoc teammates, analogous to the transition function of the underlying Dec-POMDP. A more explicit definition of X is provided in Appendix A.I.
Without loss of generality, let C(0) (-Iss) denote a of M controlled agent policies parameterized by 0, such that a learning algorithm might optimize for 0. Let the x(M) indicate team of M agents and π (MM) XUU C)) indicate sampling such team from U and C' via the team sampling procedure. The objective of the NAHT problem is to find parameters 8, such that ( maximizes the expected return in the presence of teammates from U:
Σ rrr Exmr
max 0
Challenges of the NAHT problem include: (1) coordinating with potentially unknown teammates (generalization), and (2) coping with varying number of uncontrolled teammates (openness).
4 The Need for Dedicated NAHT Algorithms
Having introduced the NAHT problem. natural question to consider is whether AHT solutions may optimally address NAHT problems. so, then there would be little need consider the NAHT problem setting. For instance, a simple yet reasonable approach consists of directly using an AHT policy to control as many agents as required in an NAHT scenario. This section illustrate the limitations of the aforementioned approach by giving a concrete example of matrix game where (1) an AHT policy that is learned in the AHT (N 1) scenario is unlikely to do well an NAHT scenario where N- = 2, and (2) even optimal AHT policy is suboptimal in the N = 2 setting.
Define the following simple game for M agents: at each turn, each agent a picks one bit b, E (0, at the end of each turn, all the bits are summed s == Σ; b, The team wins if the sum of the chosen bits is exactly We denote the probability of winning by P(s = 1). Suppose the uncontrolled agents
'The original AHT problem statement used the terms "known" and "unknown" agents. However, it is common for modern AHT learning methods to assume some knowledge about the "unknown" teammates during training [27]. Thus, instead employ the terms controlled and uncontrolled.
3

---

follow policy that independently selects 1 with probability p 1 4 In the following, we consider M
the three agent case, M = 3. for simplicity.
In the AHT problem setting, learning algorithm assumes control of only a single agent. Let Paht denote the probability with which the AHT agent selects 1. Given the aforementioned team of uncontrolled agents, we show that any value of Paht results in the same probability of winning, which occurs because the probability of winning, P(s 1) 5. independent of Pahr (Lemma A.2).
Next, consider an NAHT scenario where a learning algorithm must define the actions of two out of three agents. Suppose that the same AHT policy is used to control both agents: both agents select 1 with probability Puit- Above, we demonstrated that an AHT algorithm trained in the = 1 scenario could result in learning any Patt- However, in the N = 2 setting, we show that the optimal AHT policy Pahı = 3 and the winning probability for this policy is P(s = 1) = 5 (Lemma A.3).
4
Finally, we show there exists an NAHT policy that controls both agents and obtains higher winning probability. Consider the policy where one controlled agent always plays 0, while the other plays with probability Pnaht- Lemma A.4 shows that the optimal Peaht 1, and the probability of winning Thus, we have exhibited an NAHT scenario where an AHT policy that is optimal
P(s = = when N = I, performs worse than simple NAHT joint policy in the N 2 setting. Empirical validation of the prior results are provided in Appendix 1.5.1.
Policy Optimization with Agent Modeling (POAM)
This section describes the proposed Pol- icy Optimization with Agent Modeling (POAM) method, which trains a collection of NAHT agents that can adaptively deal with different collections of unknown team- mates. POAM relies on an agent model- ing network initially build an embedding vector characterizing teammates encoun- tered during an interaction. Adaptive agent policies that can maximize the controlled agents' returns are then learned by train- ing policy conditioned on the environ- ment observation and team embedding vec- tor. To enable controlling a varying num- ber of agents while learning in a sample- efficient manner, POAM adopts the inde- pendent learning framework with full pa- rameter sharing. The training processes for agent modeling and policy networks are de- scribed in Sections 5.1 and 5.2 respectively, while an illustration of how POAM trains NAHT agents is provided in Figure 2.
POAM
Agent Meddllig Netsonk
of.
(6/ a. 11
:t (ef))
V: (eff)
Nenvok
x%
U
x of
Team Policy
Figure 2: POAM trains a single policy network ,., which characterizes the behavior of all controlled agents (green), while uncontrolled agents (yellow) are drawn from U. Data from both controlled and uncontrolled agents is used to train the value network, v:"- while the policy trained on data from the controlled agents only. The policy and value function are both conditioned on a learned team embedding vector, eç.
5.1 Agent Modeling Network
Designing adaptive policies that enable NAHT agents to achieve optimal returns against any team of uncontrolled agents drawn from some set U, requires information on the encountered team's 's unknown behavior. However, in the absence of prior knowledge about uncontrolled teammates' policies. local observations from single timestep may not contain sufficient information regarding the encountered team. To circumvent this lack of information, POAM's agent modeling network plays crucial role in providing team embedding vectors that characterize the observed behavior of tcammates in the encountered team.
We identify two main criteria for desirable team embedding vectors. First, team embedding vec- tors should identify information regarding the unknown state and behavior of other agents in the environment (both controlled and uncontrolled). Second, team embedding vectors should ideally
'Lemma A. shows that p x is the optimal value of p for team composed of such agents.

---

be computable from the sequence of local observations and actions of the team. Fulfilling both requirements provides an agent with useful information for recision-makingg NAHT problems, even under partial observability.
For each controlled agent, POAM produces informative team embedding vectors by training model with an encoder-decoder architecture, illustrated by red components in Figure 2. For ease of presentation, the encoder-decoder models for controlled agent will be referred without the index i. The encoder, f H, + IR" is parameterized by 0 and processes the modeling agent's s history of local observations and actions up to timestep 1, h [of a; " k==1 to compute team embedding vector of dimension n, eς E I" that characterizes the modeled agents. This reliance on local observations helps ensure that the agent modeling network can operate without having access to the environment state that is unavailable under partial observability. The team embedding vector is decoded by two decoder networks: the observation decoder, før R - O- and the action decoder, Ige R + A(A-:). The decoder networks are respectively trained to predict the observations and actions of all other agents on the team at timestep t. (o'_,, ,), to encourage of to contain relevant information for the current NAHT agent's 's pocision-making process. While the observation decoder directly predicts the observed -i observations, the action decoder predicts the parameters of probability distribution over the -i agents' actions, p(a'_; fdoe (f0r (h())), where an appropriate distribution for should be selected by the system designer.
Concretely, agent i's encoder-decoder model is trained to minimize maximum likelihood loss over all teammates' observations and actions, given its own local observations and actions. As the experimental setting in this paper considers continuous observations and discrete actions, the observation loss a mean squared error loss, while the action loss the negative log likelihood of the -i agents' actions, under the Categorical distribution.
L8 00,00000000000 000 (hi d' d'x;)= = (11500 (fom (h()) 1.122-lo(ppp'... f0 (f (K)))))
(2)
5.2 Policy and Value Networks
POAM relies on an actor-critic approach to train agent policies, where the policy and critic are both conditioned on the teammate embedding described in Section 5.1.
The policy network of agent i, n. H, x RR + A(A)). is parameterized by 08, and uses the NAHT agent's local observation, of. and the team embedding from the encoder network, ef, to compute policy followed by the NAHT agents. Conditioning the policy network on et allows an NAHT agent to change its behaviour based on the inferred characteristics of encountered agents. When training the policy network, we also rely a value (or critic) network, V. H; x Th + R. parameterized by 8 which measures the expected returns given h; and eç. The value network serves as a baseline to reduce the variance of the gradient updates, while conditioning on the learned teammate embeddings for similar reasons to the policy.
POAM then trains the policy and value networks using an approach based on the Independent PPO algorithm [45] (IPPO). IPPO is selected the base MARL algorithm for two reasons. First, using an independent MARL method circumvents the need to deal with the changing number of agents resulting from environment openness. Second, IPPO has been demonstrated to be effective on various MARL tasks. To improve learning efficiency and enable information sharing between agents, full parameter sharing is employed for all neural networks. POAM trains the value network to produce accurate state value estimates by minimizing the following loss function:
= 2 (v." (h,, SØ (It) - v.')²
Lge (h1)
where V/ is the TD(A) return. The policy network analogously trained to minimize the PPO loss function [35], but where the policy additionally conditions on the team embeddings.
Leveraging data from uncontrolled agents In the NAHT setting, we assume access to the joint observations and actions generated by the current team deployed in the environment al training time only, where the team consists of a mix of controlled and uncontrolled agents. This assumption provides opportunity to learn useful cooperative behaviors more quickly, by bootstrapping based
5

---

on transitions from the initially more competent, uncontrolled teammate policies, as also observed by Rahman et al. [31].
POAM leverages data from both controlled and uncontrolled agents to train the value network- in effect, treating the uncontrolled agents exploration policies. Note that this aspect of POAM is a significant departure from PPO, which is a fully on-policy algorithm. Since the policy update is highly sensitive to off-policy data, only data from the controlled agents is used train the policy network.
6 Experiments and Results
This section presents an empirical evaluation of POAM and baseline approaches across different NAHT problems. We investigate three questions and foreshadow the conclusions:
Q1: Does POAM learn cope with uncontrolled teammates with higher sample efficiency and asymptotic return than baselines? (Usually)
Q2: Does POAM improve generalization to previously unseen and out-of-distribution teammates, compared to baselines? (Yes)
Q3: Can we verify that the two key ideas of POAM agent modelling and use of data from uncontrolled agents-work desired and contribute positively towards POAM's performance? (Yes)
Full implementation details, including hyperparameter values and additional empirical results, appear in the Appendix. Our code is available at https: //ggtttt.b..////////////. caamm/aarllii wwwoooleewwnn////0
6.1 Experimental Design
In the following, we summarize the experimental design, including the particular NAHT problem instance, training procedure, experimental domain, and baselines. Details on evaluation metrics are provided in Appendix A.3.3.
A Practical Instantiation of NAHT Similarly to AHT, the NAHT problem can be parameterized by the amount of knowledge that controlled agents have about uncontrolled agents, and whether uncontrolled agents can adapt to the behavior of controlled agents [5]. Furthermore, as a direct result of the fact that an NAHT algorithm may control more than a single agent, the NAHT problem may also be parameterized by whether the controlled agents are homogeneous, whether they can com- municate, and what the team sampling procedure is. While the fully general problem setting allows for heterogeneous, communicating, controlled agents that have no knowledge of the uncontrolled agents, as a first step, this paper focuses on a special case of the NAHT problem, where agents are homogeneous, non-communicating. may learn about uncontrolled agents via interaction, and where the team sampling procedure consists Appendix A.3.1 for details). This case is designed primarily to assess whether controlled subteams may outperform independent controlled agents, when cooperating with multiple types uncontrolled agents. We leave consideration of broader NAHT scenarios for future work.
uniform random sampling scheme from U and C' (see
Generating Uncontrolled Teammates To generate a set of uncontrolled teammates U, the follow- ing MARL algorithms are used to train agent teams: VDN [41], QMIX [33], IQL [42], IPPO, and MAPPO [45]. We verify that the generated team behaviors are diverse by checking that (1) teams trained by the same algorithm learn non-compatible coordination conventions, and (2) teams trained by different algorithms also learn non-compatible coordination conventions (Appendix A.5.2). The emergence of diverse teammate behaviors from training agents using different MARL algorithms under different seeds aligns with the findings from Strouse et al. [40].
Let Utrain denote the set of uncontrolled teammates used to train all (N)AHT methods. Utrain consists of five teams, where each individual team is trained via VDN, QMIX, IQL., IPPO and MAPPO, respectively. Utest consists of set of holdout teams trained via the same MARL algorithms, but that have not been seen during training. The experimental results reported in Sections 6.2 and 6.4 are computed with respect to Utrain only, while the experimental results in Section 6.3 use Utest-
Experimental Domains Experiments are conducted on a predator-prey mpe-pp task implemented within the multi-agent particle environment [24], and the 5v6, 8v9, 10v11, 3s5z tasks from the

---

sp
Svb
8v9
3152
10V11
25.0
17.5
175
130
250
33
125
POAM
10.
AHT
75
Naive MARI
15
1.6
1.6
Timeshops
507
Thmestops
Timestops
Timestop
Timestops
Figure 3: POAM consistently improves over the baselines of IPPO-NAHT, POAM-AHT, and the best naive MARL baseline in all tasks, in either sample efficiency or asymptotic return.
StarCraft Multi-Agent Challenge (SMAC) benchmark [34]. On the mpe-pp task, three predators must cooperatively pursue pretrained prey agent. The team receives reward of +1 per time step that two or more predators collide with the prey. On the SMAC tasks, a team of allied agents must defeat a team of enemy agents controlled by the game server. For each task, the first number in the task name indicates the number of allied agents, while the second indicates the number of enemy agents. The team is rewarded for defeating enemies, with large bonus for defeating all enemies. See Appendix A.3.2 for full details.
Baselines As NAHT is new problem proposed by this paper, there are no prior algorithms that are directly designed for the NAHT problem. Therefore, we construct three baselines to contextualize the performance of POAM. All methods employ full parameter sharing [30].
Naive MARL: various well- known MARL algorithms are considered, including both independent and centralized training with decentralized execution algorithms [14]. The algorithms evaluated here include IQI. [10], VDN [41], QMIX [33], IPPO, and MAPPO [45]. The MARL baselines are trained in self-play and then evaluated in the NAHT setting. In the following, only the performance of the best naive MARL baseline reported.
Independent PPO in the NAHT setting (IPPO-NAHT): IPPO is a policy gradient MARL algorithm that directly generalizes PPO [35] to the multi-agent setting. It was found to be surprisingly effective on a variety of MARL benchmarks [45]. In contrast to the naive MARL baselines, IPPO-NAHT is trained using the NAHT training scheme presented in Section 6. The variant considered here employs full parameter sharing, where the actor is trained on data only from controlled agents, but the critic is trained using data from both controlled and uncontrolled agents. The latter detail is a key algorithmic feature which POAM also employs, but is an extension from the most naive version of PPO (see Section 6.4). IPPO can be considered an ablation of POAM, where the agent modeling module is removed.
POAM in the AHT setting (POAM-AHT): As considered in Section 4, a natural baseline approach to the NAHT problem is use AHT algorithms that train only single controlled agent, and copy these policies as many times as needed in the NAHT setting. To evaluate the intuition that AHT policies do not suffice for the NAHT problem setting, we consider AHT version of POAM that is trained identically to POAM, but where the number of controlled agents is always one (N 1) during training. Note that POAM-AHT is equivalent to the AHT algorithm introduced by Papoudakis et al. [29]. LIAM.
6.2 Main Results
This section addresses Qh-that is, whether POAM learns cope with uncontrolled teammates with greater sample efficiency or asymptotic returns, compared to baselines. Figure 3 shows the learning curves of POAM and IPPO-NAHT, and the test returns achieved by the best naive MARL baseline and POAM-AHT, on all tasks.$ All learning curves consist of the mean test returns across five trials, while the shaded regions reflect the % confidence intervals.
We find that for all tasks, POAM outperforms baselines in terms of asymptotic return for three out of five tasks (mpe-pp, 5v6, 3s5z). For all tasks, POAM's initial sample efficiency is similar to that of IPPO-NAHT for the first few million steps of training, after which POAM displays higher return. We attribute the initial similarity in sample efficiency to the initial cost incurred by learning team embedding vectors, which once learned, improves learning efficiency. IPPO-NAHT, which
SSee the Appendix for tables providing the performances of all naive MARL methods, across all tasks.
7

---

can be viewed as an ablation of POAM with agent modeling, is the next best performing method. Although IPPO-NAHT has generally poorer sample efficiency than POAM, the method converges to approximately the same returns on two out of five tasks (8v9 and 10v11). While the agent modeling module of POAM provides team embedding vectors to the policy learning process, the embeddings are themselves produced from each agent's & own observation. Since no additional information is provided to POAM agents, it is unsurprising that IPPO-NAHT can converge to similar solutions as POAM, given enough training steps.
Preditor Prey
Finally, while the best naive MARL baseline and POAM-AHT learn good solutions on some tasks, neither method consistently performs well across all tasks. Overall, POAM discovers the most consistently performant policies compared to baseline methods, in a relatively sample-efficient manner. We conclude that (1) agent modeling improves learning efficiency, and (2)
17.5
Mean Tust Rature
15.0
12.5
10.0
direct duplication of AHT-trained policies is less effective than
5.0
methods that co-train agents for NAHT.
0.0
6.3 Out of Distribution Generalization
ippo
[n]
mappo
qmix
vdn
Target Algorthis
In- Daselre
PPO-WNI
POAM
The AHT literature commonly assumes that uncontrolled team- mates of interest may be interacted directly with during training [29, 31]; experiments the prior section were conducted under this assumption. However, in realistic scenarios, it may be challenging to enumerate all teammates likely to be encoun- tered in the wild. This section examines the effectiveness of POAM under a true NAHT evaluation scenario, where POAM agents must coordinate with teammates that were not available at training time and are ouittr-disttibuutio (OOD) (Q2). Here, OOD teammates are created by running MARL algorithms with different random seeds than those used to generate train-time teammates.
Figure 4: Test returns achieved by POAM and IPPO-NAHT, when paired with out-of-distribution teammates. POAM has improved generalization to OOD teammates, compared with IPPO-NAHT.
Figures and 10 show the mean and 95% confidence intervals the test return achieved by POAM, compared to IPPO-NAHT, when the algorithm in question is paired with previously unseen seeds of IPPO, IQL, MAPPO, QMIX, and VDN. For each type of teammate, the performance of IPPO- NAHT/POAM against the exact teammates seen during training is shown as the in-distribution baseline. Both POAM and IPPO-NAHT consistently exhibit reduced performance against the OOD teammates, compared to their respective in-distribution performances. In three out of five tasks (mpe, 5v6, 3s5z), POAM has a significantly higher return than IPPO-NAHT, while the remaining two tasks exhibit smaller improvement. In Appendix A.5.3, similar findings are presented with an alternative OOD teammate generation strategy, where the set of five MARL algorithms used to generate uncontrolled teammates (IPPO, IQL, MAPPO, QMIX, VDN) are divided into train/test sets.
6.4 A Closer Look at POAM
Two key aspects of POAM are the teammate modeling module, and the use of data from uncontrolled agents to train the critic (Q3). We study the impact of both aspects on POAM's sample efficiency, focusing on the mpe-pp and 5v6 tasks. Results on 5v6 may be found in Appendix A.4.
Teammate modeling performance In the NAHT training/evaluation setting, a new set of team- mates is sampled at the beginning of each episode. Therefore, an important subtask for competent NAHT agent is to rapidly model the distribution and type of teammates at the beginning of the episode, to enable the policy to exploit that knowledge as the episode progresses. This task is especially challenging in the presence of partial observability (a property of the SMAC tasks). To address the above challenges, POAM employs a recurrent encoder, which encodes the POAM agent's ''s history of observations and actions to embedding vector, and a (non-recurrent decoder network, which predicts the egocentric observations and action distribution for all teammates.
8

---

Average Episode
Average Prob Over Episode
A natural question then, is whether the learned teammate embedding vectors actu- ally improve over the course of an episode. Figures and depict the within-episode mean squared error (MSE) of the observa- tion predicted by the decoder, and the within- episode probability of the action actually taken by the modeled teammates, according to the decoder's 's modeled action distribution. Each curve corresponds to a different training checkpoint of single run.
Average MSE
Average Prob
0.60
0.55
0.2
0.50
0.1
0.45
100
75
100
Episode Timestep
Episode Timestep
training timesteps (rounded nearest million)
0m
4m
8m
12m
16m
17m
2m 6m
10m
14m
18m
3m 7m
11m
15m
19m
For both tasks, we observe that the average MSE decreases over the course of training, while the average probability of the taken actions increases. For later training check- points, we observe that the average MSE ac- tually decreases within an episode, while the average probability increases, reflecting the increased confidence of the agent modelling module more data is observed about teammates. Thus, we conclude that POAM is able to cope with the challenges introduced by the sampled teammates and partial observability, to learn accurate teammate models.
Figure 5: Evolution of a POAM agent's within- episode mean squared error (left) and within-episode probability of actions of modeled teammates (right), over the course of training on ope-pp.
Impact of data from non-controlled agents Recall that both POAM and IPPO-NAHT update the value network using data from both the controlled and uncontrolled agents. As Figures 6 and 9 show, this algorithmic feature results in a significant performance gain over training using on-policy data only, for both POAM and IPPO-NAHT.
7 Related Works
Predator Prey
This section summarizes literature in areas most closely related to NAHT, namely, ad hoc teamwork, zero-shot coordination, evaluation of cooperative capabilities, agent modeling, and CMARL.
Test Return Mean
15
10
5
Ad Hoe Teamwork Zero-Shot Coordination. Prior works in ad hoc teamwork [39] and zero-shot coordination (ZSC) [16] explored methods to design adaptive agents that can optimally collaborate with unknown teammates. While they both highly resemble the NAHT problem, existing methods for AHT [31, 27] and ZSC [16, 25] have been limited to single-agent control scenarios. We argue that direct, naive applications of AHT and 7SC techniques to our problem of interest are ineffective- the discussion in Section 4 and results in Section 6.
0.0
0.5
1.0
1.5
2,0
Timesteps
1e7
Learning curves of POAM and IPPO-NAHT, where the value network is trained w/w.o. uncontrolled agents' data (UCD).
Figure 6:
Recent research in AHT and ZSC utilizes neural networks to improve agent collaboration within various team configurations. These recent works mostly focus two approaches. The first approach trains the agent to adapt to unknown teammates by characterizing teammates' behavior as fixed-length vectors using neural networks and learning a policy network conditioned designs teammate policies that maximize the agent's 's performance when collaborating with diverse teammates [25, 31]. Our work builds on the first category, extending it to control multiple agents amid the existence of unknown teammates. While this also offers a potential path for robust NAHT agents, designing teammate policies for training will be kept future work.
these vectors [31, 29, 47]. The second
Evaluating Agents' Cooperative Capabilities. Beyond training agents to collaborate with team- mates having unknown policies, researchers have developed environments and metrics to assess cooperative abilities. The Melting Pot suite [20, 1] mostly evaluates controlled agents' ability to maximize utilitarian welfare against unknown agents. However, this evaluation suite focuses on mixed-mon motive games where agents may have conflicting goals. This contrasts with our work's 'ss scope

---

of fully cooperative settings, where all agents share the same reward function. MacAlpine et al. [26] also explored alternative metries to measure agents' cooperative capabilities while disentangling the effects of their overall skills in drop-in RoboSoccer.
Agent Modeling. Agent modeling enables agents to characterize other agents based on their actions [2]. Such characterizations could attempt to directly infer modeled agents' actions, goals [13], or policies [29]. The modeled attributes have been used in cooperative, competitive, and general sum settings inform update rules 36] to directly inform decision making [29]. POAM relies on agent modeling to provide important teammate information for decision-making when collaborating with unknown teammates.
Cooperative MARL (CMARL). CMARL explores algorithms for training agent teams on fully cooperative tasks. Some existing methods focus on credit assignment and decentralized control [12, 33]. Other works in CMARL also leverage parameter sharing and role assignment (e.g.. [9, 44]) to decide an optimal division of labor between agents. However, these techniques assume control over all existing agents during training and evaluation, which limits their effectiveness in settings with unseen or uncontrolled teammates, as shown in prior work [43, 16, 31].
8 Conclusion
This paper proposes and formulates the problem of N N-agent ad hoc teamwork (NAHT), generaliza- tion of both AHT and MARL. It further proposes a multi- reinforcement learning algorithm to train NAHT agents called POAM, and develops procedure to train and evaluate NAHT agents. POAM is a policy gradient approach that uses an encoder-decoder architecture to perform teammate modeling, and leverages data from uncontrolled agents for policy optimization. Empirical validation on MPE and StarCraft II tasks shows that POAM consistently improves over baseline methods that naively apply existing MARL and AHT approaches, in terms of sample efficiency, asymptotic return, and generalization to out- -fitt--distribution teammates.
Limitations and Future Work. This paper addresses special case of the NAHT problem, with homogeneous and non-communicating agents. POAM, which employs full parameter sharing, may not perform well in settings with hetergeneoous agents, or in settings that require highly differentiated roles. POAM also does not leverage centralized state information or allow communication between controlled agents. Incorporating this information might enable learning improved NAHT policies. Further, POAM's actor update is purely on-policy, and therefore cannot leverage data generated by uncontrolled agents. Future work might consider employing off-policy methods exploit the uncontrolled agent data. In addition to the directions suggested by POAM's limitations, algorithmic ideas from AHT, such as diversity-bais -ased teammate generation [25] and teammate- coeeee-odel-baaaeeee planning methods [6]. also suggest rich avenues for future work. Having introduced the NAHT problem in this work, we hope the community explores the many potential directions to design even better NAHT algorithms by considering advances in MARL, AHT, and agent modeling.
Acknowledgments and Disclosure of Funding
This work has taken place in the Learning Agents Research Group (LARG) UT Austin. LARG research is supported in part by NSF (FAIN-2019844, NRT-2125858), ONR (800014-1--243)) ARO (W91NNF-23-2-004, W91 1911NN-17-2--1888
Lockheed Martin, and UT Austin's 's Good Systems grand challenge. Peter Stone serves as the Executive Director of Sony AI America and receives financial compensation for this work. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research.
References
[1] John P Agapiou, Alexander Sasha Vezhnevets, Edgar A Duéficz-Guzmite Jayd Matyas, Yi- Mao, Peter Sunehag, Raphael Köster, Udari Madhushani, Kavya Kopparapu, Ramona Comanescu, et al. Melting pot 2.0. arXiv preprint 1xXi:22/1.137/44 2022.
[2] Stefano Albrecht and Peter Stone. Autonomous agents modelling other agents: A compre- hensive survey and open problems. Artificial Intelligence, 258:66-95, 2018.
10

---

[3] Stefano V. Albrecht, Filippos Christianos, and Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024. URL https://www. marl-book. com.
[4] Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent Tool Use From Multi-Agen Autocuriiula. In International Conference on Learning Representations, September 2019. URL https://openre forum?id=Sten SSxxpp
net/
[5] Samuel Barrett and Peter Stone. An analysis framework for ad hoc teamwork tasks. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume Volume 1, pages 357-364, 2012.
[6] Samuel Barrett, Avi Rosenfeld, Sarit Kraus, and Peter Stone. Making friends on the fly: Cooperating with new teammates. Artificial Intelligence, 242:132-171, January 2017. ISSN 0004-3702. doi: 10.1016/j att.:/o/arttin.221110..0000 URL https: /wwp://wwwww/////oo/////// sciencedirect com/ htt.a//c/arriceee///////000//02.
[7] Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The Complexity of Decentralized Control of Markov Decision Processes. Mathematics of Operations Research, 27(4):819-840, November 2002. ISSN 0364-765X. doi: 18.1287/mor 27....99...... URL
https://pubsonling informs...... httg//oi/11... mmor/moor::. 27 8.9...9.80
[8] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(637))4488-224 2018. doi: 10. 1 121///ience..a0 1733
URL htttps:/wwwt science.......... wwt. http/dd//aaab/00.1111 http:/...111//ciiieeeee swwenccieccccccccooccooooe aao1733.
[9] Filippos Christianos, Georgios Papoudakis, Muhammad A Rahman, and Stefano V Albrecht. Scaling multi-agent reinforcement learning with selective parameter sharing. In International Conference on Machine Learning, pages 1989-1998 PMLR, 2021.
[10] Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of the fifteenth national/tenth conference on Artificial inteliggence/mmovtiiee applications of artificial intelligence, AAAI '98/IAAI '98, pages 746- 752, USA, July 1998. American Association for Artificial Intelligence. ISBN 978-0-262-51098-
[11] Jakob Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MulriAgent Systems, page 122-130. International Foundation for Autonomous Agents and Multiagent Systems, 2018
[12] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
[13] Josiah Hanna, Arrasy Rahman, Elliot Fosong, Francisco Eiras, Mihai Dobre, John Redford, Subramanian Ramamoorthy, and Stefano V Albrecht. Interpretable goal recognition in the pres- ence of occluded factors for autonomous vehicles. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 7044-7051. IEEE, 2021.
[14] Pablo Hernandez-Leal Bilal Kartal, and Matthew F. Taylor. A Survey and Critique of Multiagent Deep Reinforcement Learning. Autonomous Agents and Multi-Agent Systems, (3(6)7750-797, November 2019. ISSN 1387-2532, 1573-7454. doi: 10000///0588-099100 http://arxiv.. org/ abs 181001110000 05587. 1rX [cs].
URL
[15] Hengyuan Hu and Jakob N. Foerster. Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning. September 2019. URL http::////ppeeeeeeeeeeeee/totote Bixm3RVtwB.
[16] Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "other-play" Sapppla"ooo for zero-shot coordination. International Conference on Machine Learning, pages 4399-4410. PMLR, 2020.
11

---

[17] Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongging Lu. Graph convolutional reinffrrcemeeeecceeecmmmm reinforcement learning. In International Conference on Learning Representations. 2019.
[18] Anirudh Kakarlapudi, Gayathri Anil, Adam Eck, Prashant Doshi, and Leen- Soh. Decision- theoretic planning with communication in open multiagent systems. In Uncertainty in Artificial Intelligence, pages 938-948. PMLR, 2022.
[19] Raphael Koster, Miruna Pislar. Andrea Tacchetti, Jan Balaguer. Leqi Liu, Romuald Elic, Oliver P Hauser, Karl Tuyls, Matt Botvinick, and Christopher Summerfield. Using deep reinforcement learning to promote sustainable human behaviour on a common pool resource problem, 2024.
URL htt.htttss/aaat /awpivv.aivvv.v/aaa org/ ftp wwwxxii/papers//40000 20404/22044 15059.pd.
[20] Joel Z Leibo, Edgar A Duefiez-Guzman, Alexander Vezhnevets, John P Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch, and Thore Graepel. Scalable evaluation of multi-agent reinforcement learning with melting pot. In International conference on machine learning, pages 6187-6199. PMLR, 2021.
[21] Fanqi Lin, Shiyu Huang, Tim Pearce, Wenze Chen, and Wei-Wei Tu. TiZero: Mastering Multi-Agent Football with Curriculum Learning and Self-Play. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, pages 67-76, Richland, SC, May 2023. International Foundation for Autonomous Agents and Multia- gent Systems. ISBN 978- 1778--45003-432-11
[22] Michael L Littman. Markov games as framework for multi-agent reinforcement learning, In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[23] Bo Liu, Qiang Liu, Peter Stone, Animesh Garg, Yuke Zhu, and Anima Anandkumar. Coach- player multi-agent reinforcement learning for dynamic team composition. In International Conference on Machine Learning, pages 6860-6870, PMLR, 2021.
[24] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative--oompttiiee environments. Neural Information Processing Systems (NIPS), 2017.
[25] Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot coordination. In International conference on machine learning, pages 7204-7213, PMLR, 2021.
[26] Patrick MacAlpine and Peter Stone. Evaluating ad hoc teamwork performance in drop-in in player challenges. In Gita Sukthankar and Juan Rodriguez-Aguilar, editors, Autonomous Agents and Multiagent Systems, AAMAS 2017 Workshops, Best Pupers, pages 188-186. Springer International Publishing. 2017. URL http://mt wtt.anc.....a.sssseccmeemoom.a.s edw hwtp//LNAA11--- -MMA117iaa
[27] Reuth Mirsky, Ignacio Carlucho, Arrasy Rahman, Elliot Fosong, William Macke, Mohan Sridharan, Peter Stone, and Stefano Albrecht. A survey of ad hoc teamwork research. In European Conference Multi-Agent Systems, pages 275-293. Springer, 2022.
[28] Liviu Panait and Sean Luke. Cooperative multi-agent learning: The state of the art. Autonomous Agents and Multi-Agent Systems, 11:387-434, 2005. URL htt.:pppp//ppp...saaaaaaaaaaeaa semanticscholar. org/Corpus ID: 19706.
[29] Georgios Papoudakis, Filippos Christianos, and Stefano V. Albrecht. Agent modelling under partial observability for deep reinforcement learning. In Advances in Neural Information Processing Systems, 2021.
[30] Georgios Papoudakis. Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Bench- marking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks. In Advances in Neural Information Processing Systems, volume 34, 2021.
[31] Arrasy Rahman, Niklas Höpner, Filippos Christianos, and Stefano V. Albrecht. Towards Open Ad Hoe Teamwork Using Graph-based Policy Learning. Proceedings of the 38 th International Conference Machine Learning, volume 139. PMLR, June 2021.
12

---

[32] Arrasy Rahman, Ignacio Carlucho, Niklas HAllpner, and Stefano V. Albrecht. A general learning framework for open ad hoc teamwork using graph-based policy learning. Journal of Machine Learning Research, 24(298):1-74, 2023. URL. http: // jmlr. pappps/ppps/eeeee
22-099. html.
[33] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research. PMLR, 2018.
[34] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung. Philiphh H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. CoRR, abs/1902.04043, 2019.
[35] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Prox- imal policy optimization algorithms. ArXiv, abs/1707.06341 2017. URL https://api semanticscholar wowg/Corpusuiii 28695052.
[36] Macheng Shen and Jonathan P. How. Robust opponent modeling via adversarial ensemble reinforcement learning in asymmetric imperfect-information games. In Proceedings of the Tiirty-Firsl International Conference on Automated Planning and Scheduling, 2021.
[37] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[38] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learn- ing. In Proceedings of the 36th International Conference on Machine Learning, pages 5887- 5896. PMLR, May 2019. URL htttps://proceeeeeeee
mlr. www.ppres////e wwtees//v9//aoet
html.
[39] Peter Stone, Gal Kaminka, Sarit Kraus, and Jeffrey Rosenschein. Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 1504-15000 July 2010. doi: 10.
htdp:p/pp//..../aarrra////////// wtt.a///rrrcccleeeee//2222222 URL https://ojss aaai wwtooor/nnaaeeeee werg/indx....// php/AAAI/
[40] DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett. Collabo- rating with Humans without Human Data. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14502-14515, 2021. URL /ttttt:://ppocet https://prooeeeeingg. neurips. cc/paper_ pdf..
[41] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinieius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel 7.. Leibo, Karl Tuyls, and Thore Graepel. Value-decoomossitoon networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, AAMAS 18, 2018
[42] Ming Tan. Multi-agent reinforcement learning: Independent versus cooperative agents. In In- termational Conference on Machine Learning, 1997. URL htttps://apt semanticscholes
org/Corpus 267858156.
[43] Alexander Vezhnevets, Yuhuai Wu, Maria Eckstein, Rémi Leblond, and Joel Z Leibo. Options as responses: Grounding behavioural hierarchies in multi-agent reinforcement learning. In International Conference on Machine Learning, pages 9733-9742. PMLR, 2020.
[44] Mingyu Yang, Jian Zhao, Xunhan Hu, Wengang Zhou, Jiangcheng Zhu, and Houqiang Li. Ldsa: Learning dynamic subtask assignment in cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 35:1698 1710, 2022.
[45] Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surpris- ing effectiveness of mappo in cooperative multi-agent games. Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2022.
13

---

[46] Lei Yuan, Ziqian Zhang, Lihe Li, Cong Guan, and Yang Yu. A survey of progress cooperative multi-agent reinforcement learning in open environment. arXiv preprint arXiv:2312.01058. 2023.
[47] Luisa Zintgraf, Sam Devlin, Kamil Ciosek, Shimon Whiteson, and Katja Hofmann. Deep
interactive bayesian reinforcement learning via meta-learnng. arXiv preprint arXiv:2101.0386. 2021.
14

---

A Appendix
A.1 An Example of the Team Sampling Procedure
Let g(k, μ, s) represent function for randomly selecting & elements from generic set μ., conditioned on a state s E S. For instance, g might be the distribution, Multinomial kk [u], ((s)), for selecting elements with replacement from the set je, parameterized by the state dete-deeenddnt probability logits ((s) E [o, 1] Hl, Allowing
depend on an initial state enriches the representable open interactions. Returning to our robot warehouse example, a state-dependent y might enable us to model that robots suitable for heavy loads are more likely to be present near the loading dock area. Similarly, if the time included in the state, we would be able to model dynamic characteristics, e.g. that certain types of robots are only available during regular working hours, when humans are available to supervise. Of course, in simple cases, 9 might be state-independent. For & E S, X is a sampling procedure parameterized by the tuple (s, M, U, C, DM, I0 ,C), where ΦM [0, 1|M represents the logits of categorical distribution:
1. Sample an integer N from Cat(das).
2. Sample N controlled agents via 9u from U.
3. Sample M N uncontrolled agents via gc from C.
Note that the agent sampling functions gt, 9C could employ sampling with replacement to model scenarios where two robots may the same policy, sampling without replacement for scenarios where that is not possible (e.g. if all robots are heterogeneous).
A.2 Further Discussion of the Motivating Example
This section provides proofs for claims in Section 4, and further discussion in support the motivating example.
Lemma A.1. For a team of M agents independently and identically selecting actions with probability P. the p that maximizes the probability of winning is p M
Proof. The probability of winning, P(s = 1) may be computed as follows:
P(s 1) = M * P(agent chooses 1 and i choose 0) MMp11 - -p
We wish to analytically compute the global maxima of this expression with respect to p, by considering the boundary points p {0, 1} and the zeros of the first derivative.
Clearly, all agents select with probability 0, the team cannot win; thus, p = is not a maxima. Similarly, if all agents select with probability 1, the team also never wins; thus, p is also not maxima. Next, we compute the derivative of P(s = 1):
d = =Mi(1 p) M-1 (M 1)p(1 - p) M-21
dp
MI(1 - p) M- p) -M 1)p]]-
The zeros of the above expression occur at 0 and 1 For 37 note that P(s = 1) M-1 ) > 0: thus, p M must be the global maximum.
Lemma A.2. In a team of three agents consisting of two uncontrolled agents who select I with probability p 3. and one controlled ad hoc agent who selects with probability Pato the probability winning is ((s
Proof. Let S, denote the sum of the bits chosen by the two uncontrolled agents, and dakt denote the bit value chosen by the controlled agent. The probability of winning can be computed by partitioning the winning outcomes by whether s, and the ad hoc agent selects O, whether the ad hoc agent selects and both uncontrolled agents select 0, s. = 0.
15

---

P(s 1) = P(s, = 1A boht = =0) + P(s. = 0 A baht 1)
2
2
(1 Panc) + Paht 3 3
3
3
4
4
Pahi + Pahn
9
9
4
9
Lemma A.3. In team of three agents where two ad hoc agents select I with probability Pah and the remaining uncontrolled agent selects with probability 3. the maximizing Pohr = and the corresponding winning probability is 1)
Proof. Let Sakt denote the sum of the bits chosen by the two ad hoc agents, and b, denote the bit value chosen by the uncontrolled agent. The probability of winning may be directly computed as follows:
((s 1) P(Saht A au 0) ((Shht 0 au
1
= 2 Paht (1
Pahn
+ (11- Pahn) 2
3
(1 Paha)
3 Pahi
+ _ Pata)
(1 Paha)
+ Pahl
3
To determine the maximizing value, compute P(s 1) the boundary points Paht E {0, 1} and at the zeros of the derivative of P(s 1). Note that for patt 0, P(s = 1) 3. while for Paht 1, P(s 1) 0.
The derivative of the analytic expression of P(s = 1) with respect to Pat is:
(1P(s=1)) (1-Pal)) (1 + Paht
=
2Pahn
(4)
dpaht
3
The zeros of the above expression occur at Paht = 3.2 which corresponds to P(s = 1) = J.J
L
Lemma A.4. In team of three agents where agent always selects O, agent selects I with probability 3. and the last agent selects 1 with probability Paols, the optimal Puatu and results in winning probability of P(s = 1)= =
Proof. Since one of the two controlled agents always plays O, the game effectively becomes two-player game instead.
Let a, denote the action selected by the uncontrolled agent, and let anaht denote the action of the controlled agent. The probability of winning may be directly computed as follows:
P(s = 1) P(a, = 1 anaht =0) + P(a, = 0 Onaht = 1)
1
2
(1 Pnati) +
Prahn
3
1
Pnaht-
3
3
is clear that Praht maximizes P(s 1), and the corresponding value of P(s 1)
A.3 Experiment Details
A.3.1 Team Sampling Procedure Used in Experiments
16

---

Recall that U and C' denote the sets of uncontrolled and controlled agent policies, respectively, while M denotes the team size for the task, and N the number of agents sampled from C. The experiments in the following con- sider an X train consisting of sampling N uniformly from { .M- - 1). sampling N agents from and agents from U in uniform fashion (Figure 7). The sampling procedure takes place at the beginning of each episode to select team, which is then deployed in the environment. Data generated by the deployed team (e.g. joint observations, joint actions, and rewards) are returned to the learning algorithm. See Appendix A.3.3 for further details the evaluation procedure.
U
M 5,
A.3.2 Experimental Domains
Figure A practical instantiation of the NAHT problem.
MPE Predator Prey The MPE environment [24] (re-
leased under the MIT License) is a setting where particle
agents interact within bounded 2D plane, equipped with
a discrete action space and continuous observation space. The observation space is 16-dimensional, and contains the agents' own position and velocity, relative positions//clocities of all other agents, landmarks, and prey. The action space consists of five discrete actions, corresponding to the four cardinal movement directions and a no-op action. The observation range is normalized to [-1, 1], while the discrete action space is one-hot encoded.
The predator-prey task (mpe-pp) is a custom task implemented by the authors of this paper within the fork of the MPE environment released by Papoudakis et al. [30] (MIT License). In this task, three predators must cooperatively pursue a pre-trained prey agent. We use the pre-trained prey policy provided by the ePymarl MARL framework. The prey policy was originally trained by Papoudakis et al. [30], by using the MADDPG MARL algorithm to train both predator and prey agents for 25M steps, and generally attempts to escape approaching predators. The team receives reward of if two or more predators collide with the prey at a single time step, and no reward if only a single agent collides with the prey. A shaping reward consisting of 0.01 times the & distance between each agents in the team and the prey is provided as well. Since the prey policy is pre-trained and fixed, note that our predator-pee prry task is a fully cooperative task from the perspective of the predator (learning) agents. The maximum episode length is 100 time steps.
SMAC SMAC [34] (released under the MIT License) features set of cooperative tasks, where team of allied agents must defeat team of enemy agents controlled by the game server. It is partially observable domain with continuous state space and discrete action space. For each agent, the observation space continuous, and consists of features about itself, enemy, and allied agents within some radius. The action space is discrete, and allows an agent to choose an enemy to attack, a direction to move in, or to not perform any action. As the number of allies and enemies varies between tasks, the dimensionality of the observation and action spaces is particular to each task. The observation space normalized be between [-1, 1], while the action space is one-hot encoded. The maximum number of time steps per episode is also task specific, although early termination occurs if all enemies are defeated. At each time step, the team receives a shaped reward corresponding to the damage dealt, and bonuses of 10 and 200 points for killing enemy and winning the scenario by defeating all enemies. The reward is scaled such that the maximal return achievable in each task is 20.
The SMAC tasks considered in this paper are described in more detail below:
5v6: stands for 5m 6m, five allied Marines versus six enemy Marines.
8v9: stands for 8m vs 9m, eight allied Marines versus nine enemy Marines.
10v11: 1: stands for 10m vs I Hm, ten allied Marines versus eleven enemy Marines.
3s52: stands for 38 vs 5z, three allied Stalkers versus five enemy Zealots.
17

---

A.3.3 Evaluation Details
This section provides details how mixed teams are evaluated in the NAHT setting, and how cross-play scores, and self-play scores, and uncertainty measures are computed.
M .V score. Given a set of controlled agents C, and set of uncontrolled agents U, the goal of the M - N score is to quantify the performance when these two teams must cooperate within the NAHT scenario. The M .N score is computed in a deterministic and exhaustive fashion, by iterating over all possible values of N. Let N be the number of agents sampled from set C, such that M - 1}, construct the joint policy π (M) by selecting N agents uniformly from C and M N agents from U. Evaluate the resultant team the task for E episodes. This
N < M. For N E [1,
results in (M - 1) * E' episode returns, which is averaged to form the M - N score.
Cross- pass-ppayyaee scores. The cross-play scores reported in this paper are the average returns of teams generated by algorithm A, when coordinating with those generated by B. To compute the cross-play score, we first train multiple teams (by varying the seed) via both algorithms A and B. Next, the M - N score is computed for random pairings of teams (seeds) from A and B, following the procedure specified above. Summary statistics can be computed over the set of all such NAHT returns.
For example: each algorithm (VDN, QMIX, IQL. MAPPO, IPPO) is run k times with different seeds, to generate & teams of agents that may act uncontrolled teammates, For each pair of algorithms, we sample a subset the possible seed pairs, and evaluate the teams that result from merging said seed pairs. If VDN and QMIX have seeds 1 2, and 3, the cross-play evaluation might consider the seed pairings (VDN 1, QMIX 2). (VDN 2, QMIX 3), (VDN 3, QMIX 1). Given a pair of seeds (e.g. (VDN 1), (QMIX 2)), the M N cross-play score is computed the average return generated by sweeping N E {1.... .M- }} and evaluating the merged team that consists of selecting N agents from the first team, and M N agents for F. episodes. In our experiments, E 128, and k 5.
Self-play scores. The self-play scores reported in this paper are model self-play score, rather than algorithm self-play score [3]. The reason for this is that we are interested in the performance of agents when paired with known teammates.
Mcasuring uncertainty Means and 95% confidence intervals are computed over all team/seed pairings considered for any given scores, as treat each M N evaluation as an independent trial. For most experiments, five seed pairs are considered, where seeds are paired to ensure that all seeds participate in at least evaluation. This ensures that the computational cost of the evaluation remains linear in N, rather than quadratic. However, note that for the OOD experiments presented in Section 6.3, consider all possible seed pairings for the most comprehensive evaluation.
A.3.4 Algorithm Implementation
The experiments in this paper use algorithm implementations from the ePyMARL codebase [30] (released under the Apache License). The value-based methods are used without modification (i.e. IQL, VDN, QMIX), but implement our version of policy gradient methods (IPPO, MAPPO), based on the implementation of Yu et al. [45].
Parameter Sharing. All methods employ recurrent actors and critics, with full parameter sharing, i.e. all agents are controlled by the same policy, where the agent id is input to the actor and critic networks, to allow behavioral differentiation between agents. For POAM, which also maintains encoder-decoder networks for agent modeling, parameter sharing is used for the encoder and decoder networks, to improve training sample efficiency. Further, POAM's decoder, which predicts observa- tions and actions for all -i agents, employs parameter sharing across agent predictions, prevent the target dimensionality from scaling with the number teammates.
Optimizer and Neural Architecture. The Adam optimizer is applied for all networks involved. For policy gradient methods, the policy architecture is two fully connected layers, followed by an RNN (GRU) layer, followed by an output layer. Each layer has 64 neurons with ReLU activation units, and employs layer normalization. The critic architecture is the same the policy architecture.
18

---

no, yes The malue-based methods employ the same architecture, except that there is only single fully connected layer before the RNN layers, and layer normalization is not used. following the ePyMARL implementation. Please consult the codebase for full implementation details.
Algorithm
Buffer size
Epochs
Minibatches
Entropy
Clip
Clip value
loss
ΙРРO
128, 256, 512
1, 4,4, 10
1,3
0.01, 0.03,
0.01, 0.05, 0.1
no, yes
0.05
MАPPO
64, 128, 256
4, 10
1,
0.01, 0.03,
0.05, 0.1, 0.2
0.05, 0.07
Table Hyperparameters evaluated for the policy gradient algorithms. Selected values are bolded
Hyperparameters. For the value-based methods, default hyperparameters are used. We tune the hyperparameters of the policy gradient methods the 5v6 task, and apply those parameters directly to the remaining SMAC tasks. The hyperparameters considered for policy gradient algorithms are given in Table 1. POAM adopts the same hyperparameters as IPPO where applicable. We also tuned additional hyperparameters specific to POAM (Table 2).
Task
Algorithm
ED epochs
ED Minibatches
ED LR
5v6
POAM
1, 5, 10
1, 0.0005, 0.005
mpe-p2 pp
POAM
1,5
1.2
0.0005, 0.001
Table 2: Additional hyperparameters evaluated for POAM; note that ED stands for encoder-decoder. Selected values are bolded.
A.4 Supplemental Figures
This section contains additional figures referenced by the main paper. Please Section 6 for the corresponding analysis and discussion.
5v6
Averrage Episode
Average Over
Average MSF
Test Return Mean
0.35
Aearoge
0.33
10
Timestep
step
training timesteps trounded to nearest millio))
16m 10m
2m
1.0m
0.0
0.5
Timesteps
1.0
1.5
1e7
2.0
INPO NART
Figure 8: Evolution the within-episode mean squared error (left) and probability of actions that were actually taken by modeled teammates (right), computed by the POAM agent over the course of training, on the 5v6 task. The agent modeling performance improves over the course of episode, more data about teammate behavior is observed.
Figure Learning curves of POAM and IPPO, where the value network trained with and without uncontrolled agents' data (UCD) 5v6.
A.5 Supplemental Analysis
The following subsections contains secondary analysis and results, intended to support the primary analysis of the main paper. For all results, the mean and 95% confidence interval over five trials reported. All reported returns are test returns.
19

---

0OD Evaluation: SC2
5vB
DvD
3NS2
10v13
Mean Test Reburn
15.0
20
20
15
15
20.
10
IPPO-NAHT
POWM
003
h Target Algorithms
mapzs am>
wth
202 mepzo
000 131
maaEo andx vSn
mappo Target Algorithms
Target Algorithms
Target Algorithms
Figure 10: Returns achieved by POAM and IPPO-NE NAHT, when paired with outt----iistiiuttion teammates. POAM shows improved generalization to OOD teammates, as compared IPPO-NAHT, across all StarCraft tasks. For each type of teammate, the performance of IPPO-NAHT/POAM against the exact teammate seen during training shown as the in-distribution baseline.
A.5.1 The Need for Dedicated NAHT Algorithms Empirical Evidence
Section argues theoretically that with a population of uncontrolled teammates that select one with probability 1/3 and zero otherwise, an optimal policy learned in the AHT setting would not be optimal in the NAHT setting. Here, we present experiments on the three agent bit matrix game that empirically verify the theory. Let N denote the number of controlled agents. The episode length is 25, and the observation for each agent consists of the agent index and the joint action at the previous time step. The team reward at each time step is 3 * 1 b,=1-
The optimal expected return in the N and in the N = 2 (NAHT) setting is 50.0 (derived from Lemma A.4). The methods compared are POAM-AHT and POAM. Table 3 shows the expected returns achieved by POAM and POAM-AHT on the N - 1 and N = 2 scenarios. Since any policy is optimal in the N case, as expected, both methods achieve near- near-optimal returns. In the N 2 case, as expected, POAM outperforms POAM-AHT by a large margin, achieving a near-optimal return of 48.858 = 1.092.
(AHT) setting 33.333 (derived from Lemma A.3),
N=1 (AHT)
N=2 (NAHT)
POAM-AHT
33.441 0.511
22.5 8.250
POAM
33.483 + 0.485
48.858 + 1.092
Table 3: Returns of POAM-AHT versus POAM on the three agent bit matrix game, in the N=1 (AHT) and N=2 (NAHT) setting. POAM and POAM-AHT both achieve the optimal return for the = case, but POAM has much higher return on the N = 2 case.
A.5.2 Validating the Existence of Coordination Conventions
The experimental procedure detailed in Section 6.1 generates diverse teammates in SMAC and MPE by using MARL algorithms to train multiple teams of agents. Two underlying assumptions of the procedure are that (1) teams trained by the same algorithm learn non-compatible coordination conventions, and (2) teams trained by different algorithms not compatible. Both points experimentally verified this section.
Self-play with MARL algorithms. For the tasks under consideration, teams trained using the same MARL algorithm, but different seeds, can converge to distinct coordination conventions. Figure 11 demonstrates this by depicting the return of teams trained together (matched seeds) versus those of teams that were not trained together (mismatched seeds), across all naive MARL algorithms (IPPO, IQL, MAPPO, QMIX, VDN) and tasks considered. Overall, the returns of the teams that were trained together are higher than those not trained together.
The general phenomenon has been previously observed and exploited by prior works in ad hoc teamwork [40]. This paper takes advantage of this to generate set of diverse teammates for StarCraft II experiments. We select tasks where the effect is significant, to ensure that there are distinct coordination behaviors for POAM to model. Tasks that were considered subsequently ruled out for this reason include 3m 3m, 8m
8m, 6h 8z, and the MPE Spread task.
20

---

Matched vs Mismatched Seed Self Play Evaluation
Tpp op
9r6
Bvg
3:52
10v11
23
125
33
7.5
1:0
notched
mismmatched
1890
HAEE onea vde
E09
141. PRANO OP14
(90000 CPTA
vdH
D09
18
PREER 014
000
PagOO KPEE
Figure 11: Agent teams that were trained together using the same algorithm (matched seeds) have higher returns than teams that were not trained together but were trained with the same algorithm (mi shed sceds).
vdn
qmix
Iqi
lppo
mappo
poam-aht
méan xp Score
vdn
14.305
8.657 (2.925)
4.423 (1.677)
2.374 (C.730)
1:912 (1.394)
8:101 1/ (1:164)
4.342
(1.244)
qmix
8.057 +/ (2:925]
23.29/ +/- (8 (4.
3.159 + (1. (9199)
2.892 + (1,522)
2.091 +/ (1.365)
10 20/ +/ (1 (9/9
4.350 +/ (1:255)
iql
4.423 +/- (1.677)
3.359 k/- 693)
1.987 97- (3.)
1.520 6/ (20)
0:325 4/ (0.552)
4 4.809 6/ (1:524)
2:407 63 (0.811)
lppo
2.374 (0.730)
522)
820)
(1.621)
8.776
3,840 + (1.056)
mappo
1.912 +/ (1.394)
2.691 +/ (1.365)
0.325 *> (0.552)
3.776 +/ (1.244)
10.616 +/ (1.874)
8.809 +/ (2.032)
3:426 +/ (1.157)
poam-aht
8.101 +/- (1.144)
10.267 +/- 12 2971
4 4,809 4/- (1:924)
584 +,- (1.412)
6.809 +/- (2.012)
15 727 (1 2901
9:118 +:A- (1,068)
Table 4: Cross-play results for the mpe-pp task.
vdn
qmix
lql
Ippo
mappo
poam-aht
mean xp
vdn
17.239 +/ (0.315)
12.164 +/ (1.142)
11.851 4/ (0.988)
9.437 +/ [0.955]
8.791 +/ (0.786)
11.521 +/ 11 11.278)
10.561 +/ (0.585)
qmix
12.164 4/ (1.142)
17.935 (0.146)
9.857 47 (0.672)
11.758 47 (1.138)
10:623 4/ 11 (1.188)
11.991 11.051)
11.101 4/- (0.565)
1ql
+/ (0.980)
9.057 (0.672)
+/ (0.622)
8.057 +/ 047)
10.340 10 (0.)7))
(04469)
ippo
9.437 +/ (0.955)
11.758 +/- (1.130)
9.100 +: 00.0221
10.737 +3 (0.587)
11 100 + (70))
11:373 +/- 11 151)
10. 00.367 + 526)
mappo
8.791
+/ (0.786)
10.623 +/ (1.188)
8.657 ./ (0.747)
31.168 +/ (0.878)
18 826 +/ 10 205)
10:345 +/ 11.233)
9.810 +/ 10 518)
poam-aht
31.521
4/-
11.901
10.340 (0.973)
4, (1.154)
10.502
(0.585)
11:114
Table Cross- play results for the 5v6 task.
vdn
qmix
Igl
Ippo
mappo
poam-aht
mean xp
Score
vdn
19.788 +/ (0.036)
10.631 +/ (0.207)
15.520 +/- (0.839)
16.099 +/- (0.573)
14.999 +/ 10 952)
14.330
+/- (1.002)
16.512 +/ 422)
qmix
18.691
(0.207)
19.811
(0.035)
15.754
(0.810)
17.588
(0.473)
338
(0:799)
14.815
88.828 (0.385)
1/
15.520 +/- (0.838)
15.754 +2- (0.819)
18.854 +/- (0.00000 (0.093)
14.229 +1- 863)
12 995 +/ 878)
13:053 +/ 10 953)
14 625 +/- 10 (63)
ippo
16.899
+2- (0.571)
17.568 +/- (0.17) 4771
14.229 +/- (0.000000000 06.3)
19.093 +/- (0.163)
15 390 +-- 10 625)
15. +/- 10 922)
16 027 + 10 113)
14.999
(0.952)
15.338
(0.799)
12.965
(0.878)
15.390 +3- (0.825)
795 +A (0.037)
13.905
(0.999)
10. 462)
poam-aht
14.330
1/ (1.002)
14.815 1/ (1.004)
13.083
ap (0.953)
15.107
+7 (0.922)
13:065 k. (0.000)
12.370 4/. (0.460)
1// (0.450)
Table 6: Cross results for the 8m task.
vdn
qmix
Iq]
Ippo
mappo
poam sht
mean xp
score
vdn
9.879 +/ (3.722)
13.742 (3,270)
13.345
(2.144)
8.361 + 981)
8.689 + (1.618)
19 367 +/- 10 6016
10. 10.959 +/- (1.416)
qmix
13.742 +/ (3.270)
16.562 +/- (3.350)
15.780
12.290)
11:130 + 13.400)
14.541 + (2.43))
19:333 10 (0.914)
13.790 +/ (1.542)
kgl
13.345 1/ (2.114)
15.780 17 (2.200)
10.429 17 (0.594)
12.757 17 (1.224)
11.704 17 (2.275)
17.131 1/ (0. (0.805)
13.397 1/ (1.009)
Ippo
8.051 +/ (1.981)
11.130
(3.400)
12.757 +/ (1.224)
11.794 +/ (1.034)
11.291 +r (2.297)
19 629 (1.080)
10.810 +/ (1.203)
mappo
8.689 4/ (1.688)
14.541
11. 01.704440
(1.275)
4A-
16.910 +/-
20 257
11.556 (1.079)
poam-aht
19.367 +/- (0.601)
19.333 + (0.814)
17.131 +/- 10 (0.095)
19.80 19.809 +/ (1.080)
20.257 +/ (0.793)
20 20.172 + 10.579)
19:139 +/- (0.480)
Table 7: Cross-play results for the 3s5z task.
Cross-play with MARL algorithms Tables 4, 5, 6, 7, and 8 display the full cross-play results for all MARL algorithms and POAM-AHT, on all tasks. Note that the tables are reflected across the diagonal axis for viewing ease. The values on the off-diagonal (i.e., where the two algorithms are not the same) are the cross-play score, while the values shown the diagonal are self-play scores,
21

---

vdn
qmix
igl
ippo
poam-eht
score
vdn
19.868
18.980
(0.274)
18.638
453
16 928
qmix
10.960 + (0.260)
19.681 +/- (0.034)
17 3/6 (0:453)
18.193 +1: (0.31:)
608 10.3 370
16. 385 +/- 661)
282 +/- 199)
10.276 +x (0.274)
17:345 +/- (0.45.3)
10.901 +/ (0.279)
10,610 +7- (0.547)
16 290 +/ 10 092)
14.520 10 0.0)
17:110 +/- 202)
lppo
10.635 +y- (0.197)
10:193 (0.311)
16.620 (0.547)
10.971 +/ (0.1122)
17.004 0.00
16:125 10.586)
17.522 247)
mappo
16.453 +/ (0.864)
60. +/ (0.370)
16:206
(0.692)
+/ (0.559)
+/- (0.029)
+/ (0.3
poam-aht
16.328 1/ (0.734)
16.305 1/ (0.684)
14.826 4, (0. 650)
16 125 67 10 (0.566)
15 670 of 10 708)
12:179 4. 10 151)
1.5 869 xy (0 508)
Table 8: Cross-play results for the 10v11 task.
computed as described in App. A.3.3. The cross-play and self-play scores displayed are means and 95% confidence intervals. The rightmost column reflects the row average and 95% confidence interval of the cross-play (XP) scores corresponding to the test set of VDN, QMIX, IQI., IPPO, and MAPPO, excluding the self-play score. Thus, the rightmost column reflects how well average the row MARL/AHT algorithm can generalize to the test set used throughout this paper.
Overall, we find that MARL algorithms perform significantly better in self-play than cross-play. We note that there are few exceptions (e.g., IPPO vs QMIX on 8m), and that the cross- pooss-play and self-play scores are much closer on 10v11, but overall the trend is consistent across tasks.
A.5.3 Generalization to Unseen Teammate Types
As discussed and experimentally verified in Section A.5.2, diverse coordination conventions in StarCraft and MPE Predator Prey can generated by (1) running the same MARL algorithm with various random seeds, or (2) running various MARI algorithms. In Section 6.3, the out-of-distribution (OOD) teammates considered were generated by running MARL. algorithms with different random seeds than those used to generate train-time teammates- in other words, generating diverse and unseen teammates using first procedure specified above.
Evaluation Train/Test Set: MAPPO, QMIX, IQL//QL/
20
12
15.0
35
10.0
PPO NAHT POAM
Lane
Target Algerithms
Target Algoritmms
Target Algorithing
Target Algorithes
Target Aggrrthim
Returns achieved by POAM and IPPO-NAHT, when trained on MAPPO, QMIX, and IQL, and tested on IPPO, VDN.
Figure 12:
Here, we generate OOD teammates using the second procedure. More precisely, the five MARL algorithms used to generate teammates may be divided into train/test sets. Figure 12 shows the results of such an experiment, where POAM and IPPO-NAHH are trained with MAPPO, QMIX, and IQL teammates, and tested with agents from IPPO and VDN. Similar to the results presented in Section 6.3, we find that POAM generally outperforms IPPO-NAHT for the unseen teammate types for all tasks.
A.5.4 Modeling Controlled and Uncontrolled Agents
POAM's encoder-decoder (ED) models both controlled and uncontrolled agents. Since the controlled agents are updated during the training process, the encoder-decoder must deal with "moving target". Thus, in principle, the problem of modeling the controlled agents is more challenging than modeling uncontrolled agents.
Fig. 13 shows the probability of predicting the correct action for the uncontrolled agents and controlled agents separately, on the mpe-pp task. Note that the action probabilities shown in Fig. (right) the main paper would be the average of the two plots shown in Fig. 13.
22

---

Average Proh Over Episode
Average Prob Over Episode
0.05
0.60
0.55
0.50
0.50
0.40
0.40
20
40
60
80
100
20
40
00
80
100
Episode Timestep
Episode Timestep
train froundedd neareed millia))
17m
2m
6m
10m
14m
18m
11m
15m
18m
Figure 13: Loss of POAM's encoder-decoder the mpe-pp task, separated by uncontrolled (left) and controlled agents (right).
For uncontrolled agents (Fig. 13, left), we observe that the accuracy of action predictions for the uncontrolled agents increases much more consistently training goes on, and is higher than that for the controlled agents. As expected, the ED is able to model the uncontrolled agents more easily than the nonstationary controlled agents.
A.5.5 Performance as a Function of the Number of Controlled Agents
To provide more insight on how an NAHT team's performance changes as the number of controlled agents increases, Figure 14 displays the mean test returns of POAM and POAM-AHT of the number of controlled agents, where the evaluation returns are averaged across five types of uncontrolled teammates: QMIX, VDN, IQL, MAPPO, and IPPO. Note that the self-play returns of POAM and POAM-AHT (i.e. where the number of controlled agents is maximal) are shown as horizontal lines, while the performances N 0 correspond to the averaged self-play returns of the five uncontrolled team types.
function
trained the N scenario only, while POAM is trained on the full NAHT setting. As expected, POAM outperforms POAM-AHT for all values of N > 1, while for N 1, the methods perform similarly. POAM-AHT's performance declines the number of controlled agents increases, which likely occurs because the evaluation setting becomes further from the training setting N increases.
Recall that POAM-AHT
Varying Number of Controlled Agents
5vG
10v11
14
14
12
12
24
Controlles Agents
N Controlled Agents
2
Controlled Agents
Controlted Agents
Conttolles
LS
FOAM (sel play!
POAM AHT (2af pay)
POAM
POAN AHT
Figure 14: Comparing the performance of POAM versus POAM-AHT, as the number of controlled agents varies. POAM and POAM-AHT agents are evaluated with the following set of uncontrolled agents: QMIX, VDN, IQL, MAPPO, IPPO.
A.6 Computing Infrastructure
All value-basee algorithms (e.g. QMIX, VDN, IQL) were run without parallelizing environments, while policy gradient algorithms were run with parallelized environments. All methods were trained for 20M steps on all tasks. Each run took between 12-48 hours of compute, and used less than 2gB of GPU memory. Runs were parallelized to use computational resources efficiently. The servers used for our experiments ran Ubuntu 20.04 with the following configurations:
23

---

Intel Xeon CPU E5-2630 v4; Nvidia Titan V GPU.
Intel Xeon CPU E3-2698 v4; Nvidia Tesla V100-SXM2 GPU.
Intel Xeon Gold 6342 CPU; Nvidia A40 GPU.
Intel Xeon Gold 6342 CPU; Nvidia A100 Gpu.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims and contributions made in the paper are summarized in the abstract and introduction.
Guidelines:
The answer NA 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 the paper and important assumptions and limitations. A No or NA 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed throughout the paper and once more in the conclusion (Section 8).
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiaatinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification: The paper does not present theoretical results; however, some mathematical statements are made in Section 4, and corresponding proofs provided in Appendix A.2.
Guidelines:
The answer NA 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 short proof sketch to provide intuition.
Inversell, 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 properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The only contributions of the paper for which reproducibility is concern is the proposed algorithm and experiments. We give an overview of the most important implementation details within the paper, including details on hyperparameters, architecture, optimizers, and original code that our methods are based on.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 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 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 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or 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 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
26

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The codebase is included with the submission and will be released upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/ hubbic/guides/// httggguddes/Ccoo hatps//Coeeeubbeseeeeeee wttpimmsssiooooooooioooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //niss. cctpublic////ccccccccccccccccccp gww.d/gg///e/eeeee/oooe/oeo.eee/ Cooeee/mmddSSbiicaaa wwwteeSuumisssooo. seeiiisssooooooooo.o
for more details.
The authors should provide instructions 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. only 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 much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All training and evaluation details are specified in the main paper in the Appendix. The code base is released for additional implementation concerns.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Statistical significance measures are provided in the form of 95% confidence intervals for the learning curves, and standard eттоr bars for the OOD evaluation plot and cross play matrix scores. The specific protocol to compute the evaluation means and standard errors is explained and justified in Section A.3.3.
Guidelines:
The answer NA means that the paper does not include experiments.
27

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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.
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 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Machine types used run the experiments are fully specified. Time and GPU memory required to run all experiments are also specified.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /neurips.....// cc cctpublic///ccccccccccccccccclcc /Ethiiiiiie cetiideeleel
Answer: [Yes]
Justification; This paper does not involve research on human subjects, use data from humans, or rely on copyrighted data. Social impact: this paper motivates, proposes, and formalizes new research problem within cooperative MARL. Thus, this paper constitutes fundamental research that is relatively removed from real world situations, and is therefore unlikely to cause direct social impact. Impact mitigation: most of the suggested measures do not apply to this paper, except for the ones related to reproducibility. This paper conforms with the reproducibility guidelines suggested within the checklist.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
28

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper does not involve research on human subjects, data from humans, or foundation models. also does not consider generative models, or technologies with proximal impact society. The algorithms released and arguments made are in support of fundamental research MARL and AHT.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal 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 tied to particular applications, let alone deployments. However, if there is 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, 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
As explained above, this paper does not examine foundation models, pro- prietary or scraped datasets. All data used in the paper was generated via the methods considered in the paper. All experiments were performed simulation benchmarks that are widely used within the CMARL community.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. 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?
29

---

Answer: [Yes]
Justification: The only asset used by this work is the simulation environments and the code base which this project is based on. All have been cited, with licenses mentioned, in the Appendix. All licenses allow creative reuse, modification, and re-distribution.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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, paperswi thcode. cow com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- 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 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 base is released along with the submission and includes documenta-
tion.
Guidelines:
The answer NA 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 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: [NA]
Justification: This paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
30

---

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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA 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 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 the institution conducting the review.
31


Reviews:
[{"review_id": "GXJSoMLwY9", "reviewer": "Reviewer_5dYr", "summary": "This work is motivated by the realistic limitations of current multi-agent studies, specifically the assumption that either all agents are controllable or that only a single agent is controlled in the multi-agent system. To address this challenge, the authors introduce the N-agent ad hoc teamwork (NAHT) approach, in which multiple controllable agents interact with randomly selected uncontrolled agents. In the proposed framework, the controllable agent can make flexible decisions using information from its teammates. To implement this, the authors leverage an encoder-decoder structure designed to predict the observations and actions of other teams based on the agent’s trajectory history. The simulation results demonstrate improved performance compared to other multi-agent reinforcement learning baselines.", "questions": "Proposed solution\n- The reviewer wants to know if the proposed solution works only with the PPO backbone. This question arises from the authors' reasoning about why they do not leverage data from uncontrolled agents. In line 193, the authors mention that the policy update is highly sensitive to off-policy data. However, the reviewer believes this issue might be mitigated by replacing the backbone algorithm with an off-policy algorithm, e.g., soft actor-critic (SAC).\n-\tLine 59: What is the common reward function? Is it a team reward or an individual reward? Please provide details.\n-\tDoes each controlled agent have a separate encoder and decoder? Or do the controlled agents learn a single network and then use it in a distributed manner?\n\n-\tEquation (2)\no Why is observation decoding loss based on mean squared error (MSE) and action decoding loss based on likelihood?\no How to calculate probability p? There is no definition of p. Please provide details.\n\nExperiment\n- Uncontrolled agents and controlled agents operate as a team, but their training processes are entirely separate. In the training process of controlled agents, they can learn cooperative decision-making adapting to pre-trained uncontrolled agents. Conversely, In the pre-training of uncontrolled agents, what cooperative decisions do they learn? For example, if three uncontrolled agents are needed for a task in which five agents form a team, how can we pre-train only the three agents separately?\n-\tHow does a team consisting of only uncontrolled agents perform? Such empirical results can be used as a baseline.\n\nFigure 4\n- What is the range of observation and action? If it is generally assumed that the range is between [-1, 1], the MSE in Figure 4 appears to have a very large error rate.\n- What information can we get from action probability? Unlike MSE, it is difficult to identify trends.\n\nFigure 5\n- The main idea of POAM lies in building an agent modeling network, and it requires uncontrolled agent data (UCD). In Figure 5, how to train agent modeling network in POAM without UCD?\n- What is the difference between POAM without a modeling network and IPPO?\n\nFigure 6\n - It would be easier to check how much performance increases or decreases if a baseline for non-OOD cases is also provided.", "limitations": "The authors provided the general limitations in MARL algorithms.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "-\tThis paper is well motivated. The proposed solution is easy to implement.\n-\tThe proposed solution addresses a crucial aspect in the realm of MARL society. The reviewer believes that implementing a method that can collaborate with unknown teammates can effectively enhance the practicality of the MARL solution.", "weaknesses": "The reviewer is not convinced of the effectiveness of the agent modeling network for the following reasons.\n\t\n- The proposed framework is defined under a partially observable domain, in which each agent cannot observe all the other teammates. For this reason, the reviewer wonders how the model can accurately infer other teammates’ observations and actions using only the agent’s trajectory history.\t\n- The result in Figure 4 does not demonstrate the performance of the agent modeling network. In this result, the maximum action probability achieved through training is about 0.6. The reviewer thinks that this performance does not indicate that the model has been successfully trained. \n\nThis paper has some typos and needs to redefine some notations to enhance clarity.\n- In line 13, 'Modelling' should be corrected to 'Modeling'.\n- The reviewer suggests that the notation $h^t$ should be redefined as $h_i^t$. This change is necessary because $h^t$ represents the trajectory history of agent $i$, and including $i$ in the notation will enhance clarity.\n- The reviewer believes that the figures in the simulation results section have room for improvement.\n- The authors have marked the baseline names in lowercase in the figure legends. The reviewer suggests using capitalized words for consistency with the manuscript.\n- The authors refer to the results in the appendix for the simulation analysis in Section 6. The reviewer believes the analysis in the main manuscript should use the results presented in the main body.\n\nWeak evaluation\n- The selected demonstration task is limited to SMAC tasks.\n- It is necessary to consider an appropriate task that can show the difference between AHT and NAHT problems.\n- Line 163 (h^t={o_i^k,a_i^(k-1) }_(k=1)^t): How to handle input where history length changes?\n- Line 316: What is the different non-controlled and uncontrolled agents?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Points Addressed in Common Rebuttal**\n\n- Only one evaluation domain \n- Question about on/off-policy algorithms for POAM\n- Requested baselines: in-distribution performance for Fig. 6; performance of uncontrolled teams\n\n**Accuracy of Inferred Actions and Observations in the Dec-POMDP setting**\n\nWe agree that the agent model should experience a drop in accuracy from operating in partially observable environments, due to limited information about teammates. However, the agent model does not need to be perfect to be useful for NAHT; it only needs to be able to characterize the uncontrolled agents sufficiently s.t. POAM agents may best respond to the uncontrolled agents. \n\nExperiments demonstrate that compared to IPPO-NAHT (equivalent to POAM without agent modeling), POAM has improved sample efficiency, asymptotic performance (Fig. 3), and out-of-distribution generalization to unseen teammates (Fig. 10) in the partially observable SMAC tasks. \n \n**Agent Modelling Network Performance in Fig. 4**\n\n>The reviewer thinks that this performance [0.6] does not indicate that the [agent] model has been successfully trained.\n\nWe provide three counter-arguments:\n\n(1) *The maximum theoretical value for the action probabilities is not 1.0, as the maximum depends on the stochasticity of the modeled policies.* For example, if an agent turns left 80% of the time and right 20%, even if we perfectly model the policy, then the expected modeled action probability is $0.8^2 + 0.2^2 = 0.68$. A follow-up comment will make a formal argument. Further, partial observability might preclude achieving the maximum theoretical value.\n\n(2) We have included loss plots of the encoder-decoder in Fig. 1 of the rebuttal PDF to show that the observation and action losses reduce smoothly during training.\n\n(3) We provide additional empirical results on the bit matrix game showing that in a fully observable setting the encoder-decoder reduces both observation and action losses to the theoretical minimum value (Fig. 2 in rebuttal pdf). Derivation of the minimum action loss in follow-up comment. \n\n## Clarifications/Typos\n\nWe thank the reviewer for pointing out typos and clarity issues, and will implement all corrections in the paper.\n\n**History Length - Line 163**\n\nPOAM uses a recurrent encoder-decoder, where the hidden state is only reset at the start of the episode. The lowercase $t$ in the expression $h^t=(o_i^k,a_i^{k-1} )_{k=1}^t$ refers to the current timestep of the episode, which varies. Thus, POAM deals naturally with changing history lengths.\n\n**Un- vs Non-controlled Agent - Line 316**\n\nNon-controlled agents are the same as uncontrolled agents; we will make the terminology consistent.\n \n**Common Reward Function**\n\nA common reward means that all the agents in a team get the same reward at every time step. This follows the standard Dec-POMDP setup, as specified in Section 2.\n\n> …do the controlled agents learn a single [encoder decoder] network and then use it in a distributed manner?\n\nControlled agents learn a single encoder-decoder and use it in a distributed fashion, a practice called parameter sharing [1]. This was mentioned in Line 394 of the original paper: “POAM, which employs full parameter sharing…”\n\n## Questions\n\n> Why is observation decoding loss based on mean squared error (MSE) and action decoding loss based on likelihood? \n\nThe MSE loss is equivalent to the negative log-likelihood loss (NLL) under a Gaussian distribution, and is the standard loss for modeling continuous features (as we have in our tasks). Thus, the observation decoding loss is a unified methodology with the action decoding NLL loss, which uses a Categorical distribution for the discrete action space.\n\n> How to calculate probability p?\n\nWe noticed that Eq. 2 is missing a summation over the controlled agent index $i$, for $i \\in C$, which may have reduced readability. We will fix this typo. \n\n$p$ is the probability of observing the actions of agents $-i$, where the probability distribution is parameterized by the output of the decoder. In practice, since the experimental tasks have discrete actions, $p$ is the Categorical distribution over the action space (corresponding to the ground-truth Categorical agent policies).\n\n> In the pre-training of uncontrolled agents, what cooperative decisions do they learn? For example, if three uncontrolled agents are needed for a task in which five agents form a team, how can we pre-train only the three agents separately?\n\n The uncontrolled agents in our paper are derived from running MARL algorithms. Thus, they are trained within their own team, under whatever assumptions that MARL algorithm makes. The partial uncontrolled team is not trained separately; it is simply a subset of the full uncontrolled team that was trained to work together.\n\n> What is the range of observation and action? …the MSE in Fig. 4 appears to have a very large error rate.\n\nThe obs. range was normalized to [-1,1] for the experiments, while the discrete action space is one-hot encoded. The observation MSE decreases over training and over the episode, and can be further decreased by increasing agent model training epochs. We will post a further discussion of the observation MSE in Fig. 4.\n\n> In Fig. 5, how to train agent modeling network in POAM without UCD?\n\nTraining without UCD means that the encoder-decoder’s training dataset is limited to observations corresponding to agents from the controlled set. Importantly, agents from the controlled set may still _observe_ uncontrolled agents, making it possible to predict observations and actions corresponding to uncontrolled agents. \n\n> What is the difference between POAM without a modeling network and IPPO?\n\nPOAM w/o modeling network is equivalent to IPPO-NAHT. The difference between IPPO-NAHT and IPPO is the use of uncontrolled agent data to train the value function. \n\n## References:\n\n[1] Christianos et al. Scaling multi-agent reinforcement learning with selective parameter sharing. ICML 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SVhZl22E4X", "reviewer": "Reviewer_9xa8", "summary": "The paper proposes a MARL algorithm for the N-agent ad hoc teamwork setting. The algorithm specifically includes policy optimisation by modelling the other agents. The agent modelling uses and encoder-decoder architecture. In the actor-critic framework, the critic uses data from both controlled and uncontrolled agents. The agent modelling allows their approach to generalise well to scenarios with unseen teammates.", "questions": "How would this work when there are teammates from more than 2 different teams? For example: Team A + Competitive Team B + Competitive Team C? Is there any assumption on the identification of the team the agent belongs to in the observation space?", "limitations": "The experiments are carried out in only one environment (SMAC). It would be good to see POAM in more applied scenarios like search and rescue as mentioned in the introduction.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The problem setting is quite interesting and the solution proposed is quite simple and easy to simple to implement.\n- The paper is quite well-written and easy to follow. I liked the motivating example for NAHT in Section 4.\n- The ablation studies are quite comprehensive.", "weaknesses": "- The baselines considered in the paper do not seem to include algorithms that model other agents explicitly. Also, the related works section for agent modeling seems to be incomplete. There have been a lot of papers related to agent/opponent modelling. I would be curious to see how these baseline algorithms would compare against POAM.\n- In the out-of-distribution experiments, the authors do not give a reason for why POAM performs much better in only a few scenarios. Is there anything specific within those scenarios that helps POAM generalise better?\n\nMinor: The plots could be smoothened to make them more readable. Especially Figure 4.\n\nRelevant references:\n\n[1] Everett, R., & Roberts, S. (2018, March). Learning against non-stationary agents with opponent modelling and deep reinforcement learning. In *2018 AAAI spring symposium series*.\n\n[2] Shen, M., & How, J. P. (2021, May). Robust opponent modeling via adversarial ensemble reinforcement learning. In *Proceedings of the International Conference on Automated Planning and Scheduling* (Vol. 31, pp. 578-587).\n\n[3] Papoudakis, G., & Albrecht, S. V. (2020). Variational autoencoders for opponent modeling in multi-agent systems. *arXiv preprint arXiv:2001.10829*.\n\n[4] Foerster, J. N., Chen, R. Y., Al-Shedivat, M., Whiteson, S., Abbeel, P., & Mordatch, I. (2017). Learning with opponent-learning awareness. *arXiv preprint arXiv:1709.04326*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Points addressed in common rebuttal** \n\n- Additional agent modeling baselines and suggested references\n- Number of test domains\n\n**On Off-policy data for training PPO critic**\n\n> (R 9xa8) The decision to use data from uncontrolled agents is not well justified in the paper. The value function is also \"on policy\" in PPO, so it is unclear why this additional data is helpful in NAHT training.\n\nWhile the data from the uncontrolled agents is not “on-policy” with respect to controlled agents, here are some reasons why using this particular off-policy data to update POAM’s critic network is useful. \n\nUseful cooperative behavior can be learned more quickly by bootstrapping based on transitions from the initially more competent, uncontrolled teammate policies (Section 5.6 of [1]). Early in training, value function learning based on the competent, uncontrolled agents’ data leads to controlled agents’ high appraisal of all uncontrolled agents’ decisions leading towards high returns. Controlled agents then learn to adopt similar decisions after using the learned value function for policy updates. Also, [2] demonstrated the improved data efficiency and stability in single-agent RL from using off-policy data to update the critic in an otherwise on-policy algorithm.\n\n**Insights on Out-of-Distribution Performance**\n\nIt is difficult to pinpoint causal factors that lead to the difference in performance in these domains. While they are broadly used to test coordination and cooperation, there are multiple factors that could influence the difficulty of NAHT in these domains. Nevertheless, we can look at some of the results in these domains and make educated guesses.\n\nFor example, Fig. 11 in the Appendix shows the return of teams trained together (matched seeds) versus those of teams that were not trained together (mismatched seeds), across all naive MARL algorithms. We observed that for the three domains where there is a larger difference in performance between matched and mismatched seed teams (5v6, 3s5z, MPE-PP), there is also a larger difference in performance between POAM and IPPO-NAHT in the OOD experiments. This perhaps indicates that coordination is highly sensitive in those domains, so agent modeling makes a larger difference.\n\n**Clarity - Improved Figures**\n\nThank you for the suggestion. We will add smoothing to all figures\n\n**Questions - Addressing Cooperation With >2 Agent Teams**\n\nAddressing the question about the observation space first: POAM does not require the observation space to include any team ID information. Instead, the goal of POAM’s agent modeling module is to infer this information. \n\nIn theory, applying POAM to the scenario of Team A + Team B + Team C would be as simple as extending the training/evaluation framework to sample from two uncontrolled teams, rather than one. In practice, we anticipate credit assignment problems. For example, if the uncontrolled teams B and C do not interact well together, the overall team performance might drop greatly, but this would not be the fault of the controlled team A. \n\nAddressing the scenario of blending multiple teams would be an interesting direction for future work.\n\n## References\n\n[1]  Rahman et al. A general learning framework for open ad hoc teamwork using graph-based policy learning. JMLR 2023.\n\n[2] O'Donoghue et al. Combining policy gradient and Q-learning. ICLR 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TRnkZNkzs7", "reviewer": "Reviewer_hc6T", "summary": "This paper proposes a generalization to the ad hoc teamwork (AHT) setting where N agents follow a trained policy instead of just 1 agent or all agents. Within this NAHT framework, the authors describe a technique for modeling the other agents, accelerating the ability to learn in this setting relative to baselines.", "questions": "- Does the agent modeling network improve few-shot learning? In particular, if there is a new team and we let the POAM agent play with this configuration for multiple episodes (starting from the previous episode's hidden state instead of resetting), does this improve performance in future episodes? [Positive results in this direction would be very significant in the domain of few-shot ad hoc coordination.]\n- Does NAHT training improve AHT performance?\n- Why is the probability of predicting the correct action lower for the checkpoint at 19m timesteps versus 15m timesteps?", "limitations": "The limitations section is solid, though I think it should mention that finding diverse (or human-like) conventions in new settings is still an open question (or point to existing works that may be integrated with POAM as a future direction).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The NAHT domain is an important contribution to the general field of MARL. In particular, this work specifically investigates settings with more than 2 players, which is often understudied in the broader AHT field.\n- This paper investigates multiple settings and includes significant supplementary data in the appendix. Furthermore, all details for reproducing the results are present in the appendix.\n  - There are also many ablations, justifying each design decision in their POAM algorithm.\n- The paper is well written and easy to read. The proofs presented in the appendix are also sound.", "weaknesses": "- The \"out of distribution generalization\" results are unsatisfactory to me, undermining the central thesis that POAM benefits NAHT. In particular, the \"mismatched\" scores are quite high relative to cross-play scores when varying algorithms, indicating that algorithms learn compatible conventions when only varying seeds in these settings. This means that the OOD evaluation may not be representative of performance when paired with humans or new conventions. A game that requires more convention-dependent behavior (such as Hanabi) would provide a more informative evaluation for your technique. Otherwise, using explicit cross-play minimization techniques to provide a performance lower bound (i.e. agents that are explicitly training to maximize self-play while minimizing cross-play with your trained model), human subject studies, or models trained on human data could demonstrate the limits of your technique's out of distribution capabilities.\n- The decision to use data from uncontrolled agents is not well justified in the paper. The value function is also \"on policy\" in PPO, so it is unclear why this additional data is helpful in NAHT training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Out-of-Distribution Evaluation - Environment Selection**\n\nHanabi represents a challenging scenario for AHT and requires a large amount of computational resources. Prior papers have used billions of training steps to train agents, in contrast with the tens of millions used in our work [1,2]. Unfortunately, experimenting on Hanabi is not possible for this current paper due to computational constraints, but we agree that this game is very interesting for NAHT purposes. \n\nThere are two barriers to the reviewer’s suggested strategy of using explicit cross-play minimization techniques to generate opponents.\nFirst, existing cross-play minimization techniques such as BrDIV [3] are designed for the two-player AHT scenario and do not directly apply to the N-player scenario, and such an extension would merit its own paper.\n\nSecond, explicitly training agents that are bad for our agent violates a key assumption of AHT — that the uncontrolled teammates are acting in good faith / have some minimal level of competency.\n\n**Out-of-Distribution Evaluation - Agent Team Generation**\n\nWe do not mean to claim that the OOD experiment would represent performance when paired with arbitrary conventions or against specific classes of interest, such as human opponents, and will modify the language in the paper to clarify the limited scope of the OOD experiment. These goals remain open challenges for the AHT, ZSC, and human-AI coordination communities. The goal of our work is to introduce the NAHT problem and a viable approach to solving it.\n\nWe also acknowledge that the teammate generation method suggested by the reviewer would accentuate the generalization challenge more than the teammates we have used in the OOD generalization experiments. However, the matched-mismatched experiment (Fig. 11) and cross-play tables (Tables 12-15) clearly demonstrate the generalization challenge. Specifically, the fact that performance decreases when we pair agents with another team trained under a different seed/algorithm implies none of the uncontrolled teams perform optimally against all other teams in evaluation. This emphasizes the need for adaptation and generalization when dealing with previously unseen uncontrolled agents. Note that other papers [2, 4] have also used the teammate generation method we propose to train agents that can robustly deal with a wide range of teammates.\n\n**Question - Agent Modeling for Few-Shot Learning**\n\nAs POAM was not trained under the framework of allowing multiple episodes to learn about a new set of teammates, we do not expect that it would perform well under this setting. We agree that this would be an interesting contribution for few-shot AHT, but  this is out of the scope of our current paper. \n\n**Question - NAHT methods for AHT Performance**\n\nTheoretically, an optimal NAHT agent should perform optimally for N=1, which is the AHT scenario. We confirm our hypothesis empirically in the new bit matrix results. Please see Section 1 and Table 1 of the rebuttal pdf for a discussion. \n\n**Question - Lower Probability for Correct Action as Training Progresses**\n\nPOAM’s encoder-decoder (ED) models both controlled and uncontrolled agents. \n\nSince the controlled agents are updated during the training process, this creates a moving target for the encoder-decoder, thus making the problem of modeling the controlled agents both more challenging and noisy. The observation that the overall action probabilities are lower at 19m than at 15m is largely due to noise in the modeling of the controlled agents.\n\nFig. 4 in the rebuttal pdf shows the probability of predicting the correct action for the uncontrolled agents and controlled agents separately.Note that the action probabilities shown in Fig. 4 of the original paper would be the average of the two plots shown in the aforementioned Fig. 4.\n\nFor uncontrolled agents (Fig. 4, left) we observe that the accuracy of action predictions for the uncontrolled agents increases much more consistently as training goes on, and is higher than that for the controlled agents, indicating that the ED is able to model the uncontrolled agents more easily.\nFrom these plots, we can also see that the observed sudden decrease in action probabilities from 15m to 19m occurs for the controlled agents only. \n\n## References:\n\n[1] Hu et al. Off-belief learning. ICML 2021.\n\n[2] Hu & Foerster. Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning. ICLR 2020.\n\n[3] Rahman et al. Generating teammates for training robust ad hoc teamwork agents via best-response diversity. TMLR 2023. \n\n[4] Strouse et al. Collaborating with humans without human data. NeurIPS 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6p4hox9QCo", "reviewer": "Reviewer_eZ5A", "summary": "The paper introduces a novel problem setting within cooperative multi-agent systems, where a dynamically varying number of autonomous agents must cooperate with a set of uncontrolled teammates to achieve a common goal. This setting generalizes existing paradigms of cooperative multi-agent reinforcement learning (CMARL) and ad hoc teamwork (AHT). The authors propose the Policy Optimization with Agent Modeling (POAM) algorithm, which utilizes a policy gradient approach combined with agent modeling to enable agents to adapt to diverse teammate behaviors. The algorithm's effectiveness is demonstrated through empirical evaluations in multi-agent particle environments and StarCraft II tasks, showing improved performance over baseline approaches and better generalization to unseen teammates.", "questions": "Please refer to the weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents a new problem setting, NAHT, which extends existing frameworks by addressing more realistic scenarios where teams are not fully controlled or consist of a single adaptive agent. The methodology is well-structured, with a clear explanation of the problem formulation and the proposed algorithm. The paper is well-written, with a clear flow from problem definition to solution proposal and empirical validation.", "weaknesses": "Although the author raised a new question, the solution adopted lacks innovation. The encoder and decoder architecture used in the Agent Modeling Network is also very common in the field of opponent modeling. I did not learn anything new in terms of methodology.\n\nWhile the empirical results are good, the paper could benefit from a more thorough theoretical analysis of the POAM algorithm's convergence properties and performance guarantees. \n\nThe scalability of the POAM algorithm with respect to the number of agents and the complexity of the tasks is not fully addressed. It would be beneficial to include more extensive experiments or discussions on how the algorithm performs as these factors increase.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Novelty - Encoder/Decoder-based Agent Modelling**\n\nWhile we understand the reviewer’s reservations on the prevalent use of the encoder-decoder architectures for agent modeling, we believe it should not be the sole basis for assessing the novelty of our work. \n\nDespite using encoder-decoders for agent modeling, whose use was proposed as early as 2016 [1], some important recent works in AHT research [2, 3, 4] have contributed to the community by proposing creative ways to use representations produced by the encoder-decoder network to tackle unaddressed problems/settings in AHT teamwork. Therefore, we argue that *how the agent modeling component is used to address existing issues in AHT research* should also be considered when measuring novelty.\n\nHere, our innovation is our use of the agent modeling component’s representations during joint training for all controlled agents, for addressing NAHT problem. We show through our motivating example (Section 4) and experimental baseline of POAM-AHT (Fig. 3) that solely relying on agent modeling without joint training will yield controlled agents whose joint policy is suboptimal for addressing even the simplest NAHT problems. In the end, we believe that the AHT community could build upon this insight to extend current AHT methods to NAHT methods. We expect this insight to lead towards better solutions to the NAHT problem, which may come from improvements to the agent modeling component or the joint training process.\n\n**Convergence & Performance Guarantees, other theoretical analysis**\n\nFrom a theoretical perspective, POAM would inherit IPPO’s convergence guarantees for a nonstationary learning environment, which have recently been established [6]. \n\nIn POAM, the gradient corresponding to the encoder-decoder (ED) embeddings is detached when the encoder-decoder embeddings are computed in the actor and critic networks. Thus, the actor/critic updates do not change the weights of the ED networks. Conversely, as the ED update is fully independent of the actor/critic networks, updates to the ED do not change the weights of the actor/critic networks. \n\nThe effect of this architecture and update scheme is that the ED updates cause a small amount of nonstationarity for the PPO backbone learning algorithm. Empirically, we address this issue by using a small learning rate for the ED. Further, as POAM uses an independent learning scheme, another source of nonstationarity is the updates of the controlled agents themselves. \n\n**Scalability to Increasing Number of Agents & Task Complexity**\n\nIn practice, the paper demonstrates that POAM is effective on tasks with a variety of team sizes. The task with the most agents is the 10v11 task, which has 10 agents on the allied agent team, and 11 enemies controlled by the game AI, which is a relatively large number of agents—especially in the context of AHT research, which typically considers only 2 agents.  \n\nWe employ several techniques to help POAM scale to a larger number of agents. \n*Multi-agent Reinforcement Learning*: the backbone multi-agent learning algorithm is independent learning with parameter sharing [5], which aids scalability in the homogeneous agent setting. \n\n*Agent Modeling*: In the agent modeling problem, the prediction target dimension increases linearly with the number of agents. To prevent the output dimension of the decoder network from similarly scaling with the number of agents, the decoder employs parameter sharing as well.\n\n## References\n\n[1] He et al. Opponent modeling in deep reinforcement learning. ICML 2016.\n\n[2] Papoudakis et al. Agent modelling under partial observability for deep reinforcement learning. NeurIPS 2021.\n\n[3] Zintgraf et al. Deep Interactive Bayesian Reinforcement Learning via Meta-Learning. AAMAS 2021.\n\n[4] Gu et al. Online ad hoc teamwork under partial observability. ICLR 2022.\n\n[5] Christianos et al. Shared experience actor-critic for multi-agent reinforcement learning. NeurIPS 2020.\n\n[6] Sun et al. Trust region bounds for decentralized PPO under non-stationarity. AAMAS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for lending their expertise in reviewing our paper, as well as for their thoughtful and helpful feedback. Here we address questions and points brought up by multiple reviewers. We respond to the other questions individually below.

Our contributions include: 
1. Proposing and formulating the NAHT problem.
2. Demonstrating the issues from the direct application of AHT methods in NAHT problems.
3. Outlining how existing agent modeling techniques for AHT can be applied for NAHT through the proposed algorithm, POAM.

We thank reviewers for recognizing the importance of Contribution 1(hc6T, 5dYr) by calling the NAHT problem realistic (eZ5A), interesting (9xa8), and well-motivated (5dYr). The rigor of the proofs is also highlighted as a strength (hc6T). Regarding Contribution 3 (POAM), the reviewers acknowledge that the solution is clear and easy to implement (5dYr, 9xa8), and recognized the comprehensive experiments (9xa8, hc6T). Additionally, ¾ reviewers found the paper well-written and clear (hc6T, 9xa8, eZ5A). 

Finally, the most negative review has several misunderstandings. We accept responsibility for making the paper as clear as possible. But we respectfully request that the reviewer reevaluate their rating considering many of their points/questions were already addressed in the submission.

**Use of Uncontrolled Agent Data & On/Off-Policy Algorithm Selection (R 5dYr, R 9xa8)**

> (R 5dYr) The reviewer wants to know if the proposed solution works only with the PPO backbone. This question arises from the authors' reasoning about why they do not leverage data from uncontrolled agents....this issue might be mitigated by replacing the backbone algorithm with an off-policy algorithm.

Please observe that POAM *does* use data from uncontrolled agents to update the value function. As the reviewer stated, it does not use that data to update the policy, because the policy update is sensitive to off-policy data.

It is possible to combine the agent modeling scheme with an off-policy learning method. However, a key aspect of POAM is the use of *independent learning*, allowing scalability and enabling the POAM team to operate in an environment where the number of controlled agents may vary. *Off-policy MARL algorithms following the independent learning paradigm are very uncommon for cooperative MARL.* The main challenge is that stale data in the experience replay may not reflect teammates' current behavior [1]. 

On the other hand, prior work has observed that independent PPO performs well in challenging multi-agent coordination problems [2], with theoretical justification[3]. 

**Misconception: only tested on one domain (R 5dYr, R 9xa8)**

To clarify, we evaluated on *two* domains at submission time: StarCraft II and the Multi-Agent Particle Environment (predator-prey task). Please see Figs. 3 (left), 4, 5, 6, along with various results in the Appendix.

**Baseline Selection (R 5dYr, R 9xa8)**

> (R 5dYr) Performance of teams consisting of only uncontrolled agents (and their potential as a baseline).

We concur that the performance of uncontrolled agents is an interesting baseline for NAHT, and in fact,  implemented this baseline in our paper. The naive MARL baseline in Fig. 3 is the performance of the best uncontrolled team, as evaluated through cross-play. 

In the paper, we consider uncontrolled agent teams that are trained by five MARL algorithms and discuss/analyze these agents in Section A.4.1. Fig. 11 shows the performance of each of these algorithms on all tasks when the uncontrolled team is trained together (matched seed condition), versus when we mix two teams that were trained using the same algorithm but different seeds (mismatched seed condition). Tables 12-15 display the full cross-play results for all MARL algorithms on all tasks. 

> (R 5dYr) It would be easier to check how much performance increases or decreases if a baseline for non-OOD cases is also provided.

We added the in-distribution performance of IPPO and POAM to the OOD plot (Fig. 3 of the rebuttal pdf).

> (R 9xa8) The baselines considered in the paper do not seem to include algorithms that model other agents explicitly. Also, the related works section for agent modeling seems to be incomplete….

The paper does not aim to develop new agent modeling techniques. Instead, it hypothesizes that agent modeling can help in solving the NAHT problem. In that regard, the innovation of this paper is in _how_ agent modeling should be applied for the NAHT problem. Through the POAM-AHT baseline, which combines IPPO with agent modeling similar to LIAM (ref. 28 in the submitted paper), the paper shows that naively applying an agent modeling AHT algorithm is insufficient for solving the NAHT problem. The question of which agent modeling technique is optimal for which NAHT problem is promising for future work, which we will highlight in the paper. 

We will cite and discuss the papers that the reviewer mentioned alongside this survey on agent modeling[4]. Please note that the suggested reference 3 is actually a prior version of ref. 28 in the submitted paper.

## References
[1] Foerster et al. Stabilising experience replay for deep multi-agent reinforcement learning. ICML 2017.

[2] Yu et al. The surprising effectiveness of ppo in cooperative multi-agent games. NeurIPS 2022.

[3] Sun et al. Trust region bounds for decentralized PPO under non-stationarity. AAMAS 2023.

[4] Albrecht et al. Autonomous agents modelling other agents: a comprehensive survey and open problems. AIJ 2021.

Meta-review: This paper introduces and formalized a novel problem, MALR in the N-agent ad-hoc network, that generalizes MARL in both cooperative and ad-hoc network scenarios, and that is relevant for real-world applications. The paper also sets a baseline for this problem, showing that it outperforms naive baselines. I believe this paper can inspire further research.

The discussion during the rebuttal period has been very helpful to make the contributions clearer and sounder. The authors must improve the paper according to the discussion with the reviewers, especially on the points on evaluation (setup, baselines and results), scope, use of data from uncontrolled agents, and convergence.


p.s. Couple of additional minor comments:
* It is not clear what "Without loss of generality" in line 89 refers to, using a parametric policy is not general.
* "training scheme presented in Section 6.1", does it mean the practical instantiation of NAHT discussed above (homogeneous, non-communicating agents that may learn about uncontrolled agents via interaction)?
Decision: Accept (poster)