An Efficient End-to-End Training Approach for Zero-Shot Human-AI Coordination
Authors: Xue Yan
Jiaxian Guo
Xingzhou Lou
Jun Wang
Haifeng Zhang
Yali Du
Venue: NeurIPS 2023 poster (2023)
Keywords: Zero-Shot Coordination
Human-AI coordination
Training Efficiency
Partner Modeling
TL;DR: We propose an efficient end-to-end training approach for human-AI zero-shot coordination with mixture partner policy and partner modeling module incorporated.

Abstract: The goal of zero-shot human-AI coordination is to develop an agent that can collaborate with humans without relying on human data. Prevailing two-stage population-based methods require a diverse population of mutually distinct policies to simulate diverse human behaviors. The necessity of such populations severely limits their computational efficiency. To address this issue, we propose E3T, an **E**fficient **E**nd-to-**E**nd **T**raining approach for zero-shot human-AI coordination. E3T employs a mixture of ego policy and random policy to construct the partner policy, making it both coordination-skilled and diverse. In this way, the ego agent is end-to-end trained with this mixture policy without the need of a pre-trained population, thus significantly improving the training efficiency.  In addition, a partner modeling module is proposed to predict the partner's action from historical information. With the predicted partner's action, the ego policy is able to adapt its policy and take actions accordingly when collaborating with humans of different behavior patterns. Empirical results on the Overcooked environment show that our method significantly improves the training efficiency while preserving comparable or superior performance than the population-based baselines. Demo videos are available at https://sites.google.com/view/e3t-overcooked.

An Efficient End-to-End Training Approach for Zero-Shot Human-AI Coordination
Xue Yan 1 Jiaxian Guo 3, Xingzhou Lou't
Jun Wang
Haifeng Zhang Yali Du
Institute of Automation, Chinese Academy of Science, Beijing, China
School Artificial Intelligence, University Chinese Academy of Sciences, China
University of Tokyo, Japan *University College London, UK 'King's 's College London, UK 2yanxue 1ouxingzh22000000000000000 hawiennaannnnieaaa zhang)@ia. ac j jiaxian, iaxiannguo@xxeblab guo@weblab. u-tokyo. ac jp, jun, wang ucl. ac uk, yali www.duulll.... ac. uk
Abstract
The goal of zero-shot human-AI coordination is to develop agent capable of collaborating with humans without relying on human data. Prevailing two-stage nopulation-basee methods require diverse population of mutually distinct poli- cies to simulate diverse human behaviors. The necessity of such populations severely limits their computational efficiency. To address this issue, pro- pose E3T, an Efficient End-to-Ena Training approach for zero-shot human-Al coordination. E3T employs mixture of ego policy and random policy struct the partner policy, making it both skilled in coordination and diverse. This way, the ego agent trained end-to-end with this mixture policy, eliminating the need for a pre-trained population, and thus significantly improving training efficiency. In addition, predict the partner's 's actions based on historical contexts. With the predicted part- ner's action, the ego policy can adapt its strategy and take actions accordingly when collaborating with humans exhibiting different behavior patterns. Empirical results on the Overcooked environment demonstrate that our method substan- tially improves the training efficiency while preserving comparable or superior performance than the population based baselines. Demo videos are available woogee..gogll......oooooooolooe.
introduce a partner modeling module designed
google.... wwtp://ettooercooo..e..
Introduction
Cooperation between Al agents and humans has gained significant attention, spanning various fields such as robotics 26), automatic driving [4I) Human-Al dialogue [14 and Human-Al coordination games [30]. Due to the high cost of collecting human data and involving humans during training, recent studies train an ego agent capable of collaborating with humans without relying on human data.
have focused on zero-shot human-Al coordination problems, with the aim to
To train such an ego agent, the prevailing approach [15 21 involves training the ego agent with diverse partner agents that can simulate human behavior without the need of human data. One method for achieving this through self-play [3 29), where the ego agent plays against itself the partner agent. However, empirical evidence has shown that self-play can lead to agents getting stuck in single cooperative pattern during training [15], hindering their ability to adapt to diverse human behaviors. Alternative approaches like other-play [15) aim to introduce diversity by breaking the symmetry of self-pl self-play policies. Nevertheless, this method relies on the assumption of strict symmetry in the action state space, limiting its practical applicability.
Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In contrast to relying solely on single partner policy, advanced population- based methods [21 42
32 18 19
construct a population with multiple policies simulate diverse human behaviors, and then train the ego agent to collaborate with this population. Among these methods, FCP 32 obtains a diverse population by training several self-play policies with different random seeds and saving multiple past checkpoints reflecting various coordination levels. TrajeDi [21] promotes diversity by maximizing the divergence of trajectory distributions within the partner population. MEP [42] achieves cooperative and diverse population by maximizing self-play rewards and population entropy as auxiliary rewards.
However, these population ropulation-based methods suffer from two major limitations. Firstly, they are highly computationally inefficient due to their two-stage framework, which involves training a population of policies before training the ego agent. For example, training a MEP agent for one environment in overcooked [ can take over 15 hours on single 3090Ti GPU. By contrast, a self-play agent can be trained in less than hour. Secondly, these methods only learn single response for all partners in the population, neglecting the diverse behavior patterns among them. As a result, the learned ego agent lacks the capability to adjust its policy based on each partner's 's unique behavior pattern, leading to unsatisfactory performance in zero-shot human-Al coordination.
130
In this paper, we introduce an Efficient End-to-En End Training approach, called E3T, which aims to im- prove both efficiency and the ability to recognize behavior patterns in zero-shot human-AI coordina- tion. To achieve efficient training, E3T utilizes blend of ego and random policies as partners during training, and integrates partner modeling module into the ego policy. This approach is motivated by the idea that the partner policies should be both skilled in coordination and diverse 42 By breaking down these two objectives into two policies i.e. ego policy and random policy, and merging them as the partner policy, E3T is able to be and-to-end trained without the need for pre- training a population, thus enjoy- ing higher efficiency and simpler implementation compared to population- based methods.
Al Coordination Performance
Performance
HoingHour Hour Requirements
Training Time
-15
120
110
-10
100
-5
Training
90
SP
PBT
FCP Algorithm
MEP
E3T
Figure 1: Illustration of training time and zero-shot coordination performance of base- lines. The right y-axis is the required hours to train one model. The left y-axis represents the average rewards of collaborating with Al baselines across 5 layouts.
In order to improve the collaboration capabilities of of ego agents when working with partners exhibiting different behaviors, we introduce a partner modeling module that predicts the partner's ss actions based on historical contexts. By incorporating this module into the ego policy, the agent able to know not only the current observation, but also the predicted actions of the partner. This enables the ego agent to adapt its behavior more effectively, aligning it better with the partner's ' preferences and resulting in improved collaboration performance. To the best of our knowledge, partner action prediction module in the context of a two-player human-Al coordination task.
paper is the first to utilize
Our contributions are three-fold. Firstly, we introduce an efficient end-to-end ego training approach, named E3T, for zero-shot Human-Al coordination, which offers higher training efficiency compared to population-based methods. Secondly, we propose partner modeling module that predicts partner actions from the context, allowing the ego policy to adapt when collaborating with humans exhibiting different behavior patterns. Lastly, empirical results on Overcooked show that our method, E3T, significantly improves training efficiency while achieving comparable or superior performance to existing methods as Figure [ shows. Specifically, E3T demonstrates significant improvement in training efficiency when compared to statc-of-the-at population- based methods.
2
Related Work
Our work investigates how to train an ego agent for zero-shot Human-AL coordination, field with broad applications in real-world scenarios such as robotics [5] 26), service allocation [36 37 35
and Human-Al coordination games [30]. In zero-shot Human-Al coordination tasks, reinforcement
learning (RI.) algorithms [5] are tasked with training robust ego agent without relying on human
data, due to the high cost of collecting real human data.

---

Self-Play Training There are number of methods to tackle zero-shot coordination, broadly categorized into two classes: self-play and population based training. Self-play has demonstrated impressive capability in competitive games such as Go (2)). Dota 38 StarCraft (44) and imperfect
information games [3.. Self-play can also master high-level skills cooperative games [ However,
self-play agents often struggle to coordinate effectively with previously unseen partners due to their tendency to adopt rigid conventions formed during training against themselves (32]. Other-play [IS]
attempts to mitigate these conventions by breaking the symmetries of self-play policies. However, it heavily relies on the prior knowledge of strict symmetries in the environment, limiting its applicability in general environments lacking such symmetries. In this work, E3T follows the self-play training framework, which avoids falling into conventions by encouraging the partner policies to be more diverse. In addition, method offers greater generality compared to other-play, making it applicable in a wider range of environments.
Population- Training Methods Population- -based methods train a robust AI by collaborating with diverse population. Experimental results show that population-based methods achieve superior zero-shot coordination performance compared to self-play and other-play [[5]. For example, PBT & employs an online evolutionary algorithm, which iteratively updates policy parameters and performs policy substitution within the population. FCP [32] achieves diversity within a population by training several self-play policies with different random seeds and saving multiple past checkpoints to obtain agents with various coordination levels. In a similar vein, TrajeDi [2I] regulates the partner population to be diverse by maximizing the divergence of trajectory distributions between policies within the population. Furthermore, MEP 42 introduces an auxiliary reward by designing the entropy of the average of policies in the population, thus promoting population diversity. More recently, COLE 18 [9] reformulate two- two-player coordination as a game-theoe game-theoretic problem, where the trainer's 's objective is estimate the best responses the most recent population based on the cooperative incompatibility distribution. Our work improves the partner behavior diversity by maximizing the entropy, but E3T directly increases the randomness of single-agent partner policy, making it more efficient than MEP and TrajeDi.
Agent Modeling Agent modeling is an important ability for autonomous agents, enabling them to reason about various properties of other agents such actions and goals [3]. Typical agent modeling methods focus on reasoning about types of other agents 2 31), plan recognition 9 7.. group modeling 23 1II 20 and especially policy reconstruction 66 25 27. which is also adopted in
E3T to improve zero-shot human-Al coordination performance. However, a key difference is that E3T's ego agent's partner modeling module is trained by pairing with agents and aims to predict the actions of partners. In addition, we directly employ the predicted partner actions for decision -akiing. instead of using the embedding of partner behaviors [10].
3 Preliminary
In this section, we introduce the two-player cooperative Markov Game and a representative pipeline of population-basee training for two-player zero-shot coordination.
Two- Swo-player Cooperative Markov Game A two-player cooperative Markov Game is described by a tuple (S,A, A, ,, R). where S is a finite set of states, AA is the finite set of actions, and suppose two agents have the same action space. Po S - R is the initial state distribution. T S x A x A x S + fo. 1] is the transition function and assumes the transition dynamic is deterministic. R S A R is the reward function and assume rewards are bounded by a, i.e. a(s,at,a") S a, Vs, at, a². We assume the transition and reward functions are unknown. In this work, we solve the two-policy cooperative Markov Game via single-agent reinforcement learning and the self-play framework as previous studies g [5]. Specifically, the ego policy Te is trained by pairing with fixed partner policy Tp with the object defined as n. arg max, V (IT (TTTT)). Tp).The value function of joint policy (TT, mp) is defined as V(T, mp) E Tal.T,a's,. Etmo RR(s,, at af). where y E (0, 1) is the discounted factor.
Population- of policies to simulate diverse human behaviors. Intuitively, we expect that the policy the population should be both skilled in coordination and diverse. Taking Maximum Entropy Population (MEP) [4 as an example, constructs the partner population by maximizing the self-play rewardsand simultancously increasing the entropy of policies in the population. The objective of Maximum
Training Population bassed methods (1 42 32 aim to construct a population
3

---

Ego Agent
Tr
Partner Action Prediction
Sampling
Ego Policy
Sc
Policy Copy
Policy
Ego Agent
Copy
Partner Agent
ac
Pariner
Partner Agent
Policy
Random action distribution
Rundom Policy
Sampling dp
Policy Mixiume
(a) Self-play
(b) E3T
Figure 2: (a). The illustration of the self-play training framework, which trains the ego policy by pairing it with the copied partner policy. (b). The illustration of E3T. The green box shows the decision process of the ego agent. The blue box shows that the partner agent.
Entropy Population training is defined as:
(( = BTOP Σ
[R(s), af at) + XH((
(I)
Here P [1T, T2. ..., Nnj denotes a population of policies, #(1ss) - - (((()s)) is the mean policy of the population and determines the relative importance of the population entropy term against the task reward. The task reward under the joint action is obtained by self-play with uniformly sampled policy from the population, and the population entropy term acts as an auxiliary reward. With this competent and diverse population as the partner population, by collaborating with the population via prioritized sampling that assigns a higher priority to the partner policy that is difficult to cooperate with. The objective of ego policy training is defined
ego policy is trained
J(me) = Σ al [R(st, at af))
(2)
where p(.) as the prioritized sampling mechanism. However, the training process of MEP is inefficient due to the complex two-stage training and the necessity of maintaining large population for behavioral diversity. Our work draws inspiration from MEP, which achieves hehaviorally diverse and cooperative partners by maximizing the self-play reward and the entropy of partner policy and then trains a robust ego policy by cooperating with those partners. In the next section, we will discuss how to solve zero-shot coordination using efficient end-to-end training process.
4 Methodology
In this section, we introduce the proposed method, E3T, an efficient end-to-end training approach, which trains an ego policy मe through collaborating with a partner policy тp- To take into account both training efficiency and partner diversity, we employ mixture of the copied ego policy and random policy as the partner policy Tp. The objective E3T is defined as follows:
((me) Σ El al)) [R(s at af)
The proposed method contains two key components, a diverse partner policy and a partner modeling module for adapting to unseen partners, which will be introduced Section 4.1 and Section 4.2 respectively, An overview of E3T is presented in Figure 2
4.1 A Mixture Policy as Partner
We begin with the motivation leveraging the proposed mixture partner policy. Recall that MEP trains a partner population by maximizing self-play rewards of policies within it and maximizing the population entropy as shown in Equation (T). The first term on maximizing self-play rewards tends to learn population with cooperative ability. The second entropy term can force the partner population

---

to be diverse. However, optimizing the objective of Equation ①I suffers very high computational complexity due to the necessity of training number of policies to collaborate effectively with them- selves. Moreover, it exhibits unstable convergence properties, requiring meticulous hyperparameter tuning for additional entropy term 12]
To circumvent computational cost and non-stable training, we construct the partner policy via di- viding Equation (I) into two parts with different partner policies learned, i.e. Tpl and Tp2. which aim to maximize the rewards E, (e..p.) [R[ at]] and the entropy of the policy output E, (e) (=(Tp((-1))) tion is aligned with the goal of learning coordination skills, akin the self-play training objective. In this way, we can directly use the ego policy Tee as Tpl. On the other hand. if we directly learn the latter one objective, i.e. the entropy of the mean policy, policy Tp2 will lead to the random policy T.. Le., a uniform distribution over the action space.
respectively. We can see that maximizing the former objective func-
To construct partner who has both skills in coordination and diverse behaviors, directly mix the above-discussed partner policies Tpl and Tp2 as the partner policy Tp. As previously discussed, Tpl can directly apply ego policy Te to achieve high reward for coordination. T22 random policy Tr which has the maximum policy entropy. In this way, the partner policy Tp is the mixture between the self-play ego policy and the random policy with the balance parameter e, formally defined as:
Tp EM, + (1 (1-63 E)
(4)
We can see that the computation cost for obtaining this mixture partner policy is significantly lower than population-based methods since the conversion eliminates the need to train a population of policies. Additionally, the partner policy achieves behavioral diversity by simply leveraging random policy with maximum entropy, whereas population- based approaches rely on more complex mechanisms, such as gradient descent [2]] or reward shaping [4], to enforce the diversity. Both diversity and coordination ability are two keys to constructing a partner policy. Intuitively, the diversity reflected by entropy increases, and the coordination performance decreases with the random coefficient epsilon increasing. We attempt to quantitatively verify these intuitions through Propositions 1 and 2. Firstly,
amalyze the behavior diversity of the partner policy of E3T. The entropy of partner policy reflects the diversity of partner behaviors. Proposition| I showw that the entropy of the mixture partner policy is related to that of the random policy with maximum entropy.
Proposition (Entropy of Mixture Partner Policy). The entropy of the mixture purtner policy, defined as up (1 - E) + ET7, satisfies that:
H(mp(-1sx)) 2 (((T(()) -C,,
(5)
where C1 = eloge + |A|(1 - e). and |A| is the cardinality of the action apace A. In addition, the lower bound of ((()(((s:)) is increased as the increasing of Proof. See Appendix.
Secondly, we demonstrate the benefits of improving coordination skills when pairing with the partner policy of E3T. According to Proposition]? 2 although n¹ is the best response to the mixture partner policy rather than the ego policy itself, the coordination performance of n' with the ego policy is lower bounded by that of ego policy self-play with a punishment term Ç. The Ç is related to the balance parameter c and smaller e, which means less weight on the random policy, leads to lower Ç.
Proposition (Coordination Skill Improvement). Let the ne. as the best response to TTp = (1 (1-6) E) + 4nc
em, ie n'-- = arg max; VTT,, Tp). then we have V (TT me) 2 (TTe Te) - C, where ( = [I-7]= Proof. See Appendix.
4.2 Partner Modeling
In this section, we describe the details of the proposed partner modeling module, designed to extract and analyze the behavior pattern of the partner from historical information. This module equips the ego policy with the ability to consider not only the current state but also the partner's behavior pattern, empowering the ego agent to adapt to previously unseen partners
Partner Action Prediction As in previous works 66 25 4. we model the partner agent by policy reconstruction. the actual partner action distribution a is given, the two-player cooperative Markov Game will reduce to a single-agent MDP about the ego agent, in which the ego agent can easily find the best response to the current state. Formally, under the partner policy up with af = Tp(((s)). the two-player MDP with transition function T can be converted in to a single-agent MDP with transition
5

---

Algorithm 1 E3T: An efficient end-to-end training approach with mixture policies and partner modeling
Input: Parameters of context encoder Eg, action prediction network F, ego policy Te. hyper-
parameter k.
Output: Well-trained context encoder Eg, action prediction network and the ego policy Te.
1: while not done do
2: Set data buffer D = 0.
3: for 1, step do
4: Encode context of the partner: z E.{rT)
5:
Predict partner action distribution: a F(2))
6:
Randomly select an action distribution: aj
7:
Mixture partner policy as: Tp(-|st, āï) (1 m) (-s,, aß) + cTr(.)
8:
Gather data from Te(- St, af) and Tpp (ps, a then D D [(T411 St, oi al rx)}
9:
end for
Update parameters of partner modeling module by minimizing Equation
11: Update parameters of the ego policy Te via PPO.
end while
function denoted as Ta, (5'(8t, =) op Tp(aPlos simultaneously. the ego agent only infer the partner's 's action from historical information instead of directly observing the actual partner's 's action.
-
(T aP, a). However, because the agents act
To obtain the predicted partner action åf, we first devise an encoder network Eg to extract historical partner context of from a sequence of past state-action pairs т; = {( d )- The historical partner context z contains rich information of the partner's behavior and coordination pattern, enabling our action prediction network I to predict the partner's action distribution based on a and current state 8,, This procedure is formally written follows:
2f (Ti), a. F( zi)
(6)
The parameters of the context encoder Eg and the action prediction network F are jointly optimized by minimizing a cross-entropy loss:
N C= Σ y: -y &"
where N is the batch size, and y, is one-hot vector indicating the actual partner action.
We provide theoretical analysis of how the accuracy of partner modeling affects the coordination ability as shown in Proposition 3 We analyze the coordination performance gap between the best responses to the ground-trutt partner policy and the partner prediction module. It is established that this performance gap proved to be proportional to the prediction error.
Proposition 3. Denote ग. (-]ss) = [,,[F((s E((t)) as the expectation of the proposed partner prediction module over historical trajectory Tt- The ground-truth partner policy is denoted as (p(-) Assume the learned π. (.]ss) satisfies that Drv(D+ (T]()) (-(ss))) S cms Vsy. Define the μr, and μン, the best response to the partner prediction module and the ground-truth partner policy respectively. Then the value functions of these best responses collaborating to the partner policy satisfy that: [V(n mp) (( xp)l
27ema Proof. See Appendix.
(1-7)
4.3 Ego Policy Training and Test
E3T separately trains the partner action prediction module via minimizing the loss function in Equation (7) and trains the ego policy that makes decisions depending both observations and predicted partner action distribution via PPO [24]. The detailed training process of E3T is described in the Algorithm [ During testing time, the ego agent zero-shot coordinates with an unseen partner, without parameters updating or temporally-extended exploration as (22).
Implement Details The partner modeling module of E3T takes current observation at step and partner's 's past state-action pairs as input as shown in Equation (6), we set
this work. The ego policy ne(. (s,, af") conditions on current state s, and predicted partner action distribution a,,

---

Table 1:
The cardinality of the state space of 5 layouts. The state space's cardinality of Counter
Circuit is up 5.8
1016.
Layout Cramped Rm.
Asymm. Adv. Coord. Ring
Forced Coord. Counter Cire.
State Space
5.3 10'
1.2 10
10
2.0 10
5.8 10th
Table 2:
Comparisons of baselines in terms of training time and coordination performance with behaviour-eloned human proxies. The training time represents the hours required for training one model on the layout Cramped Rm (training time on other layouts is similar). We report the average and the standard error of coordination rewards over 5 random seeds.
Baseline
SP
PBT
FCP 7.6
MEP
E3T
Training Time(h)
0.5
2.7
17.9
1.9
Average Reward
65.8 + 5.5
66.8 5.0
71.7 3.7
89.7
114.16..4
which enables the ego agent to analyze and adapt to its partner, while random action distribution at fed into the partner policy as the predicted ego agent policy. The random action distribution breaks symmetries and conventions commonly seen in self-play agents and introduces randomness into the partner policy, which in turn improves partner diversity. Moreover, this is consistent with the fact that some humans may not take their AI partners' actions into consideration, but the Al agents should adapt to their human partners.
Experiments
In this section, evaluate E3T zero-shot collaborating with behavior-cloned human proxies, real humans, and AI baselines. More details of the experiment setting and additional results can be found in Appendix.
5.1 Environments
We evaluate the zero-shot coordi- nation performance of E3T on 100 x 100 cooperative matrix game
Cross-Play
1.00
PBT MEP
0.65
0.64
0.87
0.9
21 and the Overcooked environ- Overcooked has discrete action space with actions, and we conduct experiments on 5 different layouts that pose various coordination challenges, such avoiding blocking each other and preparing the required ingredients for soup together. In ad- dition, the state spaces of 5 layouts different shown in Table 1 For instance, the state space of Counter Circuit reaches up 5.8 x 10t6 This statistic indicates the 5 layouts are challenging for explorations. We have conducted additional experiments on the Google Football 17 environment's "3 vs with Keeper" layout, which is three-player cooperative game with a discrete action space comprising 19 actions. More details about the environment descriptions can be found in Appendix.
0.75
0.
0.68
0.68
0.8
ment B
0.50
Other Pay
-0.64 0.59
3.786.88
TrajeDi
EST
BT FCP
00 68 0.668.000 68 0.73
0.85
0.7
0.00
07900.60.780.000.33
25
100
-0.6
Training Steps
MEP P0T SP
FCP E3T Mean
(a) Results on 100 x 100 matrix game
(b) AI-AI coordination
Figure 3: (a) We report the cross cross-play returns between 10 independently trained models for each baseline. (b) These results show the normalized coordination rewards between baselines averaged over layouts.
5.2 Baselines
We compare proposed E3T with 6 baselines: Self-Play (SP) 28 Population-Basn Based Training (PBT) 8). Fictious Co-Play (FCP) [32) Trajectory Diversity (TrajeDi) [21], Maximum-Entron Entrrop Population-
and Other-Play (OP) [5]. All methods, except SP, OP, and E3T, fall under the category of population-basee methods, which aim to develop a robust ego policy through interaction with a partner population. Detailed descriptions of baselines and the network details of E3T can be found in Appendix.
training (MEP)
7

---

5.3 Result Analysis
We compare E3T with other baselines on zero-shot collaboration with the human proxy, real humans, and Al baselines.
Performance with human model
175
23T
155
PDT
NEP
1.5
Trae0
TrajoD1
100
fowey MEP
"pway E97
PCP
75
PST
20
440 600
200
120
140
Carracd Rrs. Asymi, Adv.
Cood, Ring
Farcod Courd.
Courter Cir.
Avcragg 10 50d0
(a) Results on coordinating with human proxy models (b) Results collaborating with real humans Figure 4: (a) We plot the mean and standard error of coordination rewards over 5 random seeds. The parameter e set to 0.5 for all layouts except Forced Coord., where is settoas 0.0. In this layout, the ego agent does not need too much exploration due to the narrow active range. (b) We plot the mean and standard error humans collaborating with baselines over all layouts. These results show that E3T outperforms all other baselines when collaborating with real humans.
Zero-shot Coordination on 100 100 matrix game Figure 3(a) presents the cross-play [5] results of 10 independently trained policies for each baseline on a one-step matrix game. The cross-play result measures the coordination performance between models that belong the same baseline but have different random seeds. In this game, two players select a row and a column independently, and the reward determined by the intersection of their choices. As shown in Figure ([a]] E3T and MEP can converge to the optimal strategies with the largest return as 1, while E3T can converge faster than MEP. These results indicate that the mixture partner policy can enable sufficient exploration and avoid getting stuck in local optima that generalize poorly on the game with large action space. More
details of the matrix game are given in Appendix.
Training Efficiency Analysis Table_ccom compares the training time and average rewards of different baselines, where the rewards are calculated by averaging over 5 layouts on collaboration with human proxies. These results suggest that E3T outperforms existing baselines on collaboration with human proxies, and E3T is more efficient than population-base -baed methods. For instance, it only spends 10.6% training time of previous state-of-thee of-the-art art MEP.
AI-AI Coordination The zero-shot coordination performance between Al baselines are shown in Figure 3(b] where each element represents the normalized cooperation rewards averaged over 5 layouts for a pair of baselines. The performance of baselines cooperating with themselves measured by the cross-play metrie. As shown in Figure 3(b) E3T outperforms other baselines in coordinating with AI models. In addition, SP and PBT, which train policies only based on rewards and ignore diversity, have poor generalization unseen AI partners. MEP and FCP, which train the ego agent by best responding to a pre-trained diverse partner population, perform better than SP and PBT, but worse than E3T. These results indicate that partner diversity is essential for zero-shot coordination, and E3T learns roust ego policy by providing sufficient partner diversity and being equipped with adaptation ability. More results of AI-AI coordination on layouts can be found in Appendix.
Human Proxy-Al Coordination Figure 4(a) shows the results of baselines cooperating with behavior-cloned human proxies. These results suggest that E3T consistently outperforms existing baselines on all layouts. In addition, FCP, MEP, and TrajeDi have gained better or similar gener- alization performance than SP and PBT, owing to training an ego agent based on diverse partner policy. These results indicate that the diversity of partners is important for the zero-shot coordination task. Note that SP achieves comparable performance and E3T achieves the best coordination performance at parameter = 0.0. One possible reason that the Forced Coord. layout is a difficult layout with very narrow activity range and two agents being forced to coordinate to complete soup. Therefore, it requires more cooperation than exploration. Moreover, E3T with module is beneficial to adapting to an unseen partner.
population-bail based MEP on Forced Coord.
0.0 is better than SP, indicating that the partner modeling
Human-Al Coordination The average rewards over 5 layouts of AI baselines coordinating with real humans are shown in Figure 4(b) We follow the Human-Al coordination testing protocol
8

---

proposed in [32 and recruit 20 individuals to evaluate the Human-Al coordination ability of E3T and state-of-the-art MEP, where individuals play a total of 600 rounds with AI. For cost and time consideration, we reuse the Human-AI coordination results of other baselines reported in 8 42 Figure (bb shows that E3T outperforms all other baselines when zero-shot coordinating with real humans. We also collect individuals' subjective assessment of E3T and MEP about the degree of intelligence, collaborative ability, and preference between the two. More details of the Human-Al coordination setting and individuals" subjective assessment are given in Appendix.
Ablation Stusles components Al-Al coordination
The influence Hyper-parammterr
EST(++1)
Avarage ruward of ber spicode
140
150
EST(+ R]
1.2
Aowrage rwoeard of pay
E3T((+P-R)
1000
100
80
75
50
25
20
Honey EST
Cramped
Forced
0.1
0.0
F=
0.5
0.7
0.9
(a) Ablations of E3T's components
(b) Ablations of the balance parameter e
Figure 5: (a) Ablation of E3T's components on collaborating with AI baselines. E3T(+R) and E3T(+P) respectively integrate the mixture partner and the partner modeling module into the self-play framework. The balance parameter is set to 0.3 for E3T(+R). (b) Results on E3T with different balance parameters e. We plot the average rewards over 5 random seeds when E3T collaborating with AI (MEP, PBT) baselines and human proxy on layout Coord. Ring. The blue bar shows performance of E3T cooperating with Al baselines, while the orange and the green bars show its performance when cooperating with the human proxy, with starting positions switched.
5.4
Ablation Study
Analysis of Component Ablation Results We present the ablation results of E3T's components (ig We evaluate the effectiveness of each component on collaborat- ing with Al baselines (including MEP, FCP, and PBT). We use (+R) and (+P) to denote models incorporated with the mixture partner policy and the partner modeling module, respectively. As shown in Figure 5(a) E3T(+P) achieves higher average reward than SP on each layout, which shows that the partner modeling module can improve zero-shot coordination by apdating actions accordingly. Likewise, E3T(+R) surpasses SP on 4 layouts except for the Forced Coord., which shows that encouraging more exploration in the partner policy can discover more coordination patterns during training and thus can enhance zero-shot coordination with unseen partners during testing. The lower performance on Forced Coord. may be due to its narrow action space and the lack of reward incentives for coordination when using a too random partner policy during training. More- over, E3T(++P) that combines both the mixture partner policy and the partner modeling module performs better than E3T(R) and EPT(P) on the average reward over all layouts.
Averogg Reengg Reware per Ephoode
140
Accracy Actionn Prodictioo
220
300
0.4
60
S Rewendd
0.3
40
2 Accurscy
Accuraky
Environmant Stops
Figure 6: Relationship between the ac- curacy of partner action prediction and coordination performance when collab- orating with the human proxy on layout Coord. Ring. We plot the rewards and prediction accuracy obtained by coor- dinating with the human proxy at dif- ferent checkpoints along the training process.
Analyzing the effect of the hyper-paramette e Figure 5(b) shows how the balance parameter e of the mixture partner affects the performance of E3T when collaborating with AI baselines and the human proxy. We observe that the coordination rewards of E3T increase and then decrease as c increases for both types of partners. The results indicate that both collaboration ability and partner diversity are essential for zero-shot coordination, but simply increasing the partner action diversity is not enough. The optimal values of are 0.3 and 0.5 for Al baselines and human proxy, respectively. One possible reason for this discrepancy is that the human proxy tends to generate more 'noop' actions (8), which reduces the need for coordination behaviors compared to Al baselines.

---

Table 3: We present the coordination performance of baselines during training and zero-shot testing on a three-player Google Football game, where the coordination performance is measured by the winning rates of scoring goal. We independently train 3 policies with different random seeds for each baseline. For zero-shot testing, we consider all 6 possible permutations of the 3 trained policies and report the mean and standard error of the winning rates as Zero-shot (Mean). We also report the highest winning rate among the permutations as Zero-shot (Max).
Training Performance Zero-shot (Mean) Zero-shot (Max)
Self-play E3T(mixture policy)
0.79 + 0.08
0.07 + 0.08
0.24
0.76 + 0.09
0.49 + 0.21
0.78
Analyzing the effect of partner modeling module To demonstrate the effect of the proposed partner modeling module, we plot the accuracy of predicting partner actions and the rewards when cooperating with human proxy. As shown in Figure [ the reward and the prediction accuracy show the same tendency: better partner modeling leads to improvement in coordination. In addition, the accuracy at 0.5 reaches around 55%, which is higher than the accuracy around 40% when e = 0.0. This indicates that mixing a random policy can provide more exploration and thus generalize well to unseen partners.
Does the mixture partner policy accommodate the multi- Salti-player&eee game? We verify the effect of the mixture partner policy on improving the zero-shot coordination performance on a three-player Google Football game, the 3 vs with Keeper scenario. We train self-play policies via the Multi- Agent PPO (MAPPO) 40 where policies have shared parameters. E3T(mixture policy) integrates the mixture partner policy into the self-play training process, in detail, the three agents randomly sample an action with a probability as e, otherwise, take actions according to the action policies. We independently train 3 policies with different random seeds for each baselines and report the cross-play results between unseen policies to test the zero-shot coordination ability of these models.
Table that self-play policies fail to zero-shot cooperate with policies from different training seeds, because they may fall into some specific coordination conventions during training. Our proposed mixture partner policy can increase the behavioral diversity of the partners, allowing the ego policy encounter different coordination patterns during training. Consequently, our method with the mixture partner policy can train robust ego policies that can adapt well to policies independently trained from different training seeds. Moreover, increasing partner's 's behavior diversity during training can significantly improve the generalization ability of the trained ego policy.
6 Conclusion
In this paper, we propose an Efficient End-to-Ent End Training approach for zero-shot human-AI coordination, called E3T. Different from previous population-based methods, E3T employs mixture policy of ego policy and random policy to construct the partner policy, enabling the partner policy to be both coordination-skille and diverse. In this way. the ego-agent is able to be end-to-end trained in such a mixture policy without pre-training a population, thus significantly improving the training efficiency. Additionally, we introduce partner modeling module that allows the ego agent to predict the partner's next action, enabling adaptive collaboration with partners exhibiting different behavior patterns. Empirical results on Overcooked clearly demonstrate that E3T can significantly improve training efficiency while achieving comparable or superior performance compared to existing methods.
Limitations and Future Work In this paper, we only explore the feasibility of our framework in zero-shot two-player human-Al coordination tasks but neglect general multi-player (more than two) human-Al coordination tasks. Future research will focus on expanding the framework to multi-player (more than two) human-Al coordination tasks, with goal of enhancing both zero-shot coordination performance and training efficiency. Since Al agents are unable to regulate human behavior, indiscriminately collaborating with humans in accomplishing their goals could result in unlawful circumstances. Therefore, future research should concentrate on developing Al agents capable of detecting dangerous intentions and preventing their misuse for illicit or military purposes.
10

---

Acknowledgements
We would like to thank Yang Li for providing the models for the MEP and FCP baselines. Haifeng Zhang thanks to the support of the NSFC Grant Number 62206289.
References
[1] Stefano Albrecht, Jacob Crandall, and Subramanian Ramamoorthy, Belief and truth in hypothesised behaviours. Artificial Intelligence, 235:63-94, 94, 2016.
[2] Stefano V Albrecht, Somchaya Liemhetcharat, and Peter Stone. Special issue on multiagent interaction without prior coordination: Guest editorial. Autonomous Agents and Mulli-Agent Systems (AAMAS), 31(4):765-766 2017.
[3] Stefano V Albrecht and Peter Stone. Autonomous agents modelling other agents: A compre- hensive survey and open problems. Artificial Intelligence, 258:66-95, 2018.
[4] Dipyaman Banerjee and Sandip Sen. Reaching pareto-optimality in prisoner's dilemma using conditional joint action learning. Autonomous Agents and Multi-Agent Systems (AAMAS), 15:91-108, 2007.
[5] Cynthia Breazeal, Cory D Kidd, Andrea Lockerd Thomaz, Guy Hoffman, and Matt Berlin. Effects of nonverbal communication on efficiency and robustness in human-robot teamwork. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 708-713. IEEE, 2005.
[6] George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951.
[7] Sandra Carberry. Techniques for plan recognition. User Modeling and User-Adapted Interaction, 11(1):31-8,, 2001.
(8) Micah Carroll, Rohin Shah, Mark Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[9] Philip R Cohen, C Raymond Perrault, and James F Allen. Beyond question answering. Strategies for Natural Language Processing, 245274, 1981.
[10] Hao Ding, Chengxing Jia, Cong Guan, Feng Chen, Lei Yuan, Zongzhang Zhang, and Yang Yu. Coordination scheme probing for generalizable multi-agent reinforcement learning, 2023.
[11] Can Erdogan and Manuela Veloso. Action selection via learning behavior patterns in multi-robot systems. In -venty-Second International Joint Conference Artificial Intelligence (ICCAI), 2011.
[12] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning (ICML), pages 1861-1870. PMLR, 2018.
[13] Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. NeurIPS Deep Reinforcement Learning (DRL) Workshop. 2016.
[14] Ehsan Hosseini-Asi. Bryan McCann, Chien-Sheng Wu, Semih Yavuz, and Richard Socher. A simple language model for task-oriented dialogue. Advances in Neural Information Processing Systems (NeurIPS), 03:20179-20199 2020.
(15) Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "other-play" for zero-shot coordination. International Conference on Machine Learning, pages 4399-4410. PMLR, 2020.
[16] Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojeiech M Czamncki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et Population based training of neural networks. arXiv preprint 17X1v:1711.0984.. 2017.
11

---

[17] Karol Kurach, Anton Raichuk, Piotr Stanczykk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet. al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4501-4510, 2020.
(18) Yang Li, Shao Zhang. Jichen Sun, Yali Du, Ying Wen, Xinbing Wang. and Wei Pan. Cooperative open-ended learning framework for zero-shot coordination. International Conference on Machine Learning (ICML). PMLR, 2023.
[19] Yang Li, Shao Zhang, Jichen Sun, Wenhao Zhang, Yali Du, Ying Wen, Xinbing Wang, and Wei Pan. Tackling cooperative incompatibility for zero-shot human-ai coordination. arXiv preprint arXiv:2306.. 03034, 2023.
[20] Xingzhou Lou, Jiaxian Guo, Junge Zhang, Jun Wang, Kaiqi Huang, and Yali Du. Pecan: Leveraging policy ensemble for context-aware zero-shot human-ai coordination. Autonomous Agents and Multi-Agent Systems (AAMAS), 2023.
[21] Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot coordination. In International Conference Machine Learning (ICML), pages 7204-7213.
PMLR, 2021.
[22] Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off-policy metu-reinforcement learning via probabílistic context variables. In International Conference Machine Learning (ICML), pages 5331-5340. PMLR, 2019.
[23] Patrick Riley and Manuela Veloso. Recognizing probabilistic opponent movement models. In RoboCup 2001: Robot Soccer World Cup V 5, pages 453-458. Springer, 2002.
[24] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
[25] Sandip Sen and Neeraj Arora. Learning to take risks. In AAAI-97 Workshop on Multiagent Learning, pages 59 64, 1997.
[26] Thomas Sheridan. Human-robot interaction: status and challenges. 58(4))525-532) 2016.
Human Factors,
[27] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis 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.
[28] David Silver, Thomas Hubert, Julian Schritwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint 17Xiv:1712.01815 2017.
[29] David Silver, Julian Schritwieseer, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)335433555 2017.
[30] Ho Chit Siu, Jaime Peña, Edenna Chen, Yutai Zhou, Victor Lopez, Kyle Palko, Kimberlee Chang, and Ross Allen. Evaluation of human-ai teams for learned and rule-based agents in hanabi. Advances in Neural Information Processing Systems (NeurIPS), 34:161833161195 2021.
[31] Peter Stone, Gal A Kaminka, Sarit Kraus, and Jeffrey Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination. In Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
[32] DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett. Collaborat- ing with humans without human data. Advances in Neural Information Processing Systems (NeurIPS), 14:44522-44515, 2021.
12

---

[33] Gerald Tesauro. Td-gammon, self-teaching backgammon program, achieves master-level play. Neural Computation, 6(2):215-219, 1994.
[34] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782):350 354, 2019.
[35] Haoning Xi, Didier Aussel, Wei Liu, 'Travis Waller, and David Rey. Single-leader multi- follower games for the regulation of two-sided mobility-as-a-seee markets. European Journal of Operational Research, 2022.
[36] Haoning Xi, Wei Liu, S Travis Waller, David A Hensher, Philip Kilby, and David Rey. Incentive- compatible mechanisms for online resource allocation in mobility-as-a-sere systems. Trans- portation Research Part B: Methodooogical, 170:119-147, 2023.
[37] Haoning Xi, Yili Tang, S Travis Waller, and Amer Shalaby. Modeling, equilibrium, and demand management for mobility and delivery services in mobility-as-a-sere ecosystems. Computer-Aided Civil and Infrastructure Engineering, 38(11): 1113:::4403122,,, 2023.
[38] Gui-Song Xia, Xiang Bai, Jian Ding, Zhen Zhu, Serge Belongie. Jicbo Luo, Mihai Datcu, Marcello Pelillo, and Liangpei Zhang. Dota: large-scale dataset for object detection in acrial images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3974-3983, 2018.
[39] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. Advances in Neural Information Processing Systems (NeurIPS), 33:15737-15749, 2020.
[40] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Systems (NeurIPS), 35:2461 1-24624, 2022.
[41] Yi Zhang, Ping Sun, Yuhan Yin, Lin Lin, and Xuesong Wang. Human-like autonomous vehicle speed control by deep reinforcement learning with double q-learning. In 2018 IEEE Intelligent Vehicles Symposium (IV), pages 1251-1256. IEEE, 2018.
[42] Rui Zhao, Jinming Song, Yufeng Yuan, Haifeng Hu, Yang Gao, Yi Wu, Zhongqian Sun, and Wei Yang. Maximum entropy population-based training for zero-shot human-ai coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 6145-6153,
2023.
13

---

A Proposition Proofs
A.1 Proof of Proposition I
Proposition (Entropy of Mixture Partner Policy). The entropy of the mixture partner policy, defined as Tp (1 eT + ETT, satisfies that:
H(mp(-196)) 2 HH(T(()) C1,
(5)
where cloge lower bound of H(Tp(((sss) is increased the increasing of c. Proof. See Appendix.
e + |A[(1 - c). and |A| is the cardinality of the action apace A. In addition, the
Proof. The mixture partner policy is defined as Tp = (1 <) + ea, with the balance parameter
Detailed derivations Equation in Proposition are as follows:
H nT (-(p)))))
Σ
Tp log (a)ss)
Σ ([T + (1 (1
Σ
2 Σ (a) log sp(a|st)
Σ Em)(a) log (t.(() | (1-c) ())
]
(8)
(a)(a)
Σ (a) logge + logmr(a) + (1-e) ()c)))((((ss)
(TT((a)
Σ EEm(() loge (ag - -(1 e))o(a())s)
(.)(()) - eloge e |A (1 c)To(a)s))
2 H.(m(-)) c clog E |A[(1 c)
= =.((m(-)) - -C,
where = cloge + [1 - e). and |A| the cardinality of the action apace A. Inequality (1) and
(3) hold because (c)s)) s. < 1 and Ne (als:) < 1. Inequality (2) holds because log(1 + x) I x. Since C decreases in the range e (0, e|4111 and belongs to [0, 1], the lower bound of H(TT((lss)) increases as increases.
A.2 Necessary Notations and Lemmas for Proofs of Proposition 2 and
Notations As the previous statement in section 4.2 that when the partner policy Tp is given with a" = (p(()s)). the two-player MDP with transition function T can be converted to a single-agent MDP with transition function denoted as Tay (s' (st, a) >.> (ap((a)s))T
st, al, a). Note that the value estimation V( R2) under the two-player transition function T is equal to under the single- agent transition function Tag- Pr. (Tm,) denotes the stationary state-action distribution under the single-agent transition function Txy, formally written as:
the value estimation (T=( = I Bis pap, (Taz) I2 T2 (2(a²ls) (((,, a aa2)
Pr, (s, (1 - (7)) P((s = 8, at = a Tra)
(9)
14

---

Then, the equivalence between the the value estimations
(( Tr (TI)
is proven as:
VT
Ey Re( (Tx²)
7T 22 a²)]
?
PP(ss =, a 11, TT, T2 m
.a t=0
(10)
PP(s = =5,0 = aa,aa : = a²; m1 m2, a ,a,"))
8,0 _
(TTI m2)
We next give the necessary lemmas for proofs of Proposition and 3 Lemma, which describes the relationship between value estimation and policy distribution discrepancy on single-agent MDP.
first introduce the following
Lemma 1. Given single agent MDP with transition T, assume there are two policies no and wh with (ma((s))) (-)))))) S e, Vs, a holding. Then the difference between value functions satisfies
2ixe where rewards are bounded by and y the discounted factor. that [V (Ta) VT (Tb) (Tb)) S [1-7)²
Proof. The Lemma can be proved directly following the proof process of Theorem in
We provide the error bound value estimations under different transitions used for the proof of Proposition 3
Lemma 2. Given MDP with true transition function T and assume the estimated transition function T' satisfies that, for a policy Epe(r=) [Drv (T ( a)) S cm. then we have:
vT (अ) - VT (T) (1-2)2
(11)
where rewards are bounded by a and y is the discounted factor
Proof. The Lemma can be proved directly following the prove process of Lemma 7 in 39
A.3 Proof of Proposition 2
Proposition (Coordination Skill Improvement). Let the n'c as the best response TTp (1 e) em, i. T. arg max, (TT, Tp), then have V (TT,, Te) 2 ((Te, Re) - Ç, where See Appendix.
(1 (1-))2 Proof.
4ue
Proof. The total variance distance between the ego policy me and the mixture partner policy policy Tp satisfies Dry (To((ls),Tpp(ss)) < e, derived by:
(Tv(To((ss)
(a((s))) mp(a|s)]
Σ [=c(als) - (1 -
Σ
(12)
(<c(als) (a(s))
< Σ
([Te(a|s) (a(ss))
2
Σ (a)))) s) (als))
E
15

---

Next, following the Lemma 1 and the equivalence of the value estimations as shown in Equation 1O we have that IV (TT, Tp) (TT me) <= [1-7}=: VT, where == 2nr
(I-7)² Combing the definition of
Th arg maxx VIT, Tp), we have
V V me) 2 Tp)
Tp) ò (TTo: Tp) - - ((Te: me) -28,
(13)
let Ç 26, then the proof is completed.
A.4 Proof of Proposition 3
Proposition 3. Denote (-100) = Er, (F(t; ET(TT)) as the expectation of the proposed partner
prediction module over historical trajectory Tr. The ground-truth parmer policy is denoted as Ty(:1s)). Assume the learned π., (.]ss) satisfies that Drv (T, (.]s:), Tp(.(s:)) S Ems 4st. Define the Mr and Hip are the best response to the partner prediction module and the ground-truth partner policy respectively. Then the value functions of these best responses collaborating the partner policy
satisfy that: (1, (1i: mp) < [1-?]2.
2 Proof. See Appendix.
Proof. Recall that, when the partner policy Tp is given with a. = TT(((s)). the two-player MDP with transition function T can be converted in single-agent MDP with transition function denoted as Try (s') ss, a) Eer Tp(aals))T ( aP, a). The total variance distance between single-agen agent transition functions under the partner prediction module or the ground grothd-truth truth partner policy is given by:
DTv (Tx, a), (-1,
Σ
Σ
Tr (a' (st) Tp(aals)] ((8l|s, [((((1))]
1
|T(al|s) (s) - (T(a")s)]T(s(|l>
2
(14)
(x(a|ss) Tp(aa1s)]
Tp((s))
S Fm
The equation (1) is holds because that the transition function T is deterministic and equals to 1 at unique next state s". Define the μ and n are the best response to the partner prediction module and the ground-trute partner policy respectively. Then the performance gap of these best responses collaborating to the partner policy is bounded by:
Vip. mp) V Vig. Tp)
(To()()) - V Tap (K5))
(++) VTa (4/) - VTa (R:) + VTa (K/) + VTa, (x+) - Vra (45)
VT (KG) - T (M+) + VT= (46) VTn (4/) + Tar (x+) - Tr. (4,1)
VT (ut) TT. -w²)) + TT. vTx((4)) Txp (m5) + 81
(15)
VT (1C) TTa (wt) + Vo- (46) VT (11²
(x+) TT. (xt) Tv (44) VT, (xp)
1 71-
Due the optimality of μ when collaborating with the partner policy Tp. thus V(nG, mp) V(n,, mp) 0. In addition, according to the definitions of 14 i.e, the optimal policy under the MDP with transition function Txp- and μ=, Le, the optimal policy under the MDP with transi-
tion function Ta., thus we have TTa (pt) Tup (mz) < 0, T (45) - T (ut)) < 0. Let 8
16

---

VTa ((t)) -V V (H+) 2 O. In summary. the inequality (1) holds because ViH,, -p) V Tp) S 0. (1 - V~0 (1)) 50, V** (15) - V** (n,) & and 2 0.
The inequality (2) holds by applying Lemma with the condition Drv (Tx, (-18,a), TT (-1 S cm, Vs, a satisfied as proven Equation [4
Selr-Play Return
Cross-Play Roturn
1.0
1.0
AVG reTUT
E3T em 0.1
E3T c=
02
02
E3T =m 0.3
E3T m.3
G
6.02
0.02
0.4
E3T 0.5
E3T em 0.7
0.4
E3T em
02
0.2
E3T 0.9
0.2
E3T e 0.99
E3T 0.99
0.02
50
100
150
200
50
100
150
200
Training Steps
Training Steps
(a) Matrix Game
(b) Returns
Figure 7: (a) The illustration of 10x 10 sub-matris of in the upper left of the 100 X 100 matrix. (b) The returns of E3T with varying balance parameters e. The left subfigure shows the self-play returns and the right subfigure shows the coordination returns across 10 independently trained policies.
Figure 8: Overcooked Layouts. From left to right: the layouts are Cramped Room, Asymmetric Advantages, Coordination Ring, Forced Coordination, and Counter Circuit.
B Experiment Settings
B.1 Environments
100x 100 Matrix game We verify the effectiveness of the mixed partner policy for learning robust policy on one-step matrix game. The matrix partially shown in Figure 7(a) where we zoom in on the upper left 10x 10 mat-ixt The matrix denoted as M is constructed such that Mii = Mi 1, i + 1] 0.2 for i 2 and [1, 1] [2, elements are Iero.In the matrix game, two players select row and column independently. and the reward is determined by the intersection of their choices. We use one-step matrix game to test the robustness of our mixture partner policy. The game has 100x 100 matrix, where each element represents the reward for both players if they choose the corresponding row and column.
1. All other
Overcooked We validate the mixed partner policy and the partner modeling module for improving zero-shot coordination on the Overcooked environment [8]. In this environment, the target of players is make soup using onions, and dishes, and then serve After successfully serving soup, players gain 20 rewards. Its discrete action space contains 6 actions: up, down, left, right, noop, and interact.
We conduct experiments on layouts illustrated in Figure 8 The calculation of the cardinality of state spaces shown Table T explained as follows. Let's take the example of calculating the state space cardinality for the Counter Circuit layout. In the Counter Circuit layout, there are 16 positions on the kitchen counter where plates, onions, soup, or nothing can placed. Fach pot can be one of 24 states, which includes being empty, having onion, two onions, three onions, waiting for
17

---

20 counts. There are two players, each of whom can stand at one of 14 grids and face one of four directions. Each player can hold either a plate, an onion, soup, or nothing in their hands. Therefore, the total number of possible states for this layout is: 2 24 R 5.8 x 10T6. Despite having a smaller state space, Forced Coordination is more challenging than Asymmetric Advantages for zero-shot coordination. This is because the two players are separated and must complete different tasks in a timely manner to finish a soup in Forced Coordination, while players can independently complete soup in Asymmetric Advantages.
B.2 Baselines
We compare proposed E3T with 6 baselines: Self-Play (SP) 128 Population-Based Training
(PBT) [ Fictious Co-Play (FCP) [32]. Trajectory Diversity (TrajeDi) (21), Maximum-Entrropy
Population-based training (MEP) 42 and Other-Play (OP) [5]. The baselines are described in detail
below:
Self-Play (SP) [28 In coordination self-play, two players share the same policy during sampling and iteratively improve the policy by focusing on coordinating well with itself. If it converges, the self-play policy is able to coordinate with itself but is poor in generalization when meeting unseen policies.
Population Based Training (PBT) [6 g PBT is an online evolutionary algorithm, which is widely used in multi-agent RL to iteratively improve policies and finally converge to a population with high quality, At each iteration, paired policies randomly sampled from the population are improved by interacting with a number of timesteps, and then the population is updated according to the recorded performance. Specifically, the worst policy in the population is replaced with a mutation of the best policy.
Fictitious Co-Play (FCP) [32 FCP trains a policy that coordinates well with unseen humans by making the best response to diverse population of partners. To obtain the population, it trains several self-play policies with different random seeds, in addition, saves past checkpoints with different levels of coordination during training self-play policies.
Trajectory Diversity (TrajeDi) 21 TrajeDi solves the two-player zero-shot coordination problem by jointly training diverse population and its common best response (BR). To be as diverse as possible, the training of the population regularized by maximizing the Jensen-Shannon divergence (ISD) the trajectory distributions of policies. Additionally, it trains a common BR to diverse population, which indicates that the BR is able to coordinate well with unseen policies. We reuse the results of TrajeDi coordinating with human proxies reported in 42].
Maximum Entropy Population-bass through PBT, and this population is encouraged to be diverse with the entropy of the mean policies in the population as an auxiliary reward. Secondly, a common best agent is trained to cooperate with policies in this diversified population, and the selection of partner policies is via prioritized sampling. The prioritization is dynamically updated based on coordination rewards during training progress. Other-Play [15] Both E3T and other-play [15] both belong the self-play training framework, and we discuss the difference between them as follows. Other-play avoids trapping into specialized conventions by breaking known symmetries in environments, for example the colors in Card games are symmetric, and thus improves the robustness of the trained ego agent. However, this approach relies heavily on the assumption of the state or action space is strongly symmetric, for example, the colors of the cards are symmetric on Hanabi. But it does not adapt to the Overcooked environment, a population two-player cooperative game, since there do not exist obvious and easy to exchange symmetries. Our work shares the benefits of other-play with end-to-end training and breaking the symmetric of self-play training, but E3T is more general since incents partner exploration by employing a constant random policy and does not rely on any assumptions on environments.
training (MEP) [2] MEP first trains a diverse population
E3T We propose an efficient and robust training approach, combing a mixed partner policy for enhancing the diversity of partner policy and the partner modeling module for better adaptation. An ego policy is trained by pairing with the mixture partner which consists of the parameter-copied ego policy and the random policy. We set the length of the context k: = 5.
B.3 Experiments design of zero-shot coordination with humans
We describe the details of Human-Al coordination experiments. The results of baselines coordinating with real humans are shown in (b)) We follow the Human-AI coordination testing protocol proposed in (32]. We recruit 20 individuals to evaluate the coordination ability of E3T and state-
18

---

0.6
(a) Rating on the intelligence level and coordination ability
(b) Preference for MEP and E3T
Figure 9: Subjective assessments of E3T and MEP providing by real humans. (a). Average scores of the intelligence degree and the coordination ability, both scores are rated in the range of [1, 5], and larger score indicates higher intelligence and coordination ability. (b). The proportion of real humans' preference for E3T and MEP.
of-the-art MEP, humans play a total of 600 rounds with them. For cost and time consideration, we reuse the Human-Al AI coordination results of other baselines reported in 8 42 We select models with the best coordination performance with human proxies for both E3T and MEP. For E3T, we set the 0.5 on layouts except for Forced Coord. with e = 0.0 on it. We use the code provided in (20) to implement the Human-Ai interaction interface.
Participants first watched description video explaining the game rules and then they were familiar with the experimental process on single-agent demo layout with the other player not moving to experience the game. During formal experiments, each participant cooperated with the Al agents complete the layouts and is suggested get as larger rewards as possible. Pairing with each agent on each layout will repeat 3 times, and the experiment has total of 30 rounds, with each round lasting one minute. We incentivized game performance: participants earned 50 yuan complete 30 rounds, and the participants with the top 5 highest rewards eamed an extra 50 yuan.
Besides the objective coordination rewards, also collected participants' subjective assessment of E3T and MEP about the degree of intelligence, collaboration ability, and preference between the required to answer these three questions.
two. After the experiments of each layout, participants Study sessions lasted around 50 minutes on average, including being familiar with the experiment process, playing with AI agents, recording rewards, and filling in subjective assessments.
Figure Hbb shows that E3T outperforms all other baselines when zero-shot coordinating with real humans average reward across all layouts. Subjective assessments of E3T and MEP are shown in Figure These results show that participants rate E3T with higher scores on the intelligence level and the coordination ability than MEP, across all layouts. In addition, more participants prefer E3T than MEP.
B.4
The network details of E3T
The network architecture of E3T including the policy network and the partner modeling module is described in Table We describe E3T for the Overcooked environment, which has discrete action space with 6 actions. E3T trained based on Tensorflow-GPU 1.15.5 and cudal 1.4+cudnn8.8.
C Additional Results
C.1 Results on 100 x 100 Matrix Game
The performance of E3T under different balance parameters is illustrated in Figure 7(b) When = 1.0, the ego policy is trained by pairing with the completely random partner policy and fails to coordinate during self-play and cross-play with other independently trained ego policies. When < 1.0, E3T sacrifices some self-play returns during training due to the random policy mixture but
19

---

Table 4: The network details of E3T.
Partner Prediction Module
index
Layers
Channels
Kernel Size
Conv2D LeakyReLU
25
5
2
Conv2D> LeakyRel.U
25
3*3
3
Conv2I) LeakyReLUU
25
3*3
Concatenate state embedding and action embedding
5
(FC + LeakyRelu)x3
64
6
Concatenate embedding of state-action pairs
64 x
7
(FC + LeakyRelu)x3
64
8
FC + Tanh
64
9
FC L2 normalize
Policy Network
index
Layers
Channels
Kernel Size
Conv2D LeakyReLU
25
5*5
2
Conv2D Leaky ReLU
25
3#3
3
Conv2D LeakyReLU
25
3#3
Concatenate state embedding and action embedding
5
(FC + LeakyRelu)x3
64
6
FC
Self Play Return
Cross Play Retur
Avg retum
0.6
0.6
pop=2 1-15.0
pop-2
0.2
MEP Am10.0
0.2
MEP pop=2 Am10.0
MEP pop=2
A=5.0
MEP pop-2 A=5,0
НEP
160
175
200
150
175
Training Steps
Training Stops
Figure 10: Results of MEP with varying entropy coefficient on 100x matrix game.
Performance with human proxy model
Average reward of per episode
H SP
150
Harxy PBT
Hymay
Hymx TrajeDI
100
Haoxy
75
Hpoay E3T
50
25
Cramped Asymm. Adv.
Coord, Ring Layouts
Forced Coord,
Counter Circ.
Figure 11: Results on coordinating with human proxy models. The difference between this figure with the (ggure[(a)ta is that the starting positions of two agents are switched. We plot the mean and standard error of coordination rewards over random seeds. The parameter is set as 0.5 for all layouts except for Forced Coord, which sets the 0.0. In this layout, the ego agent does not need too much exploration due to the range activity being very narrow.
20

---

Coord. Ring
Cramped Rm.
Asymm. Adv.
0.95
B
0.96
0.86
0.88
0.40
0.80
0.84
6
0.72
0.72
F8
0.82
0.773
0.70
0.77
2
0.08
0.88
0.74
0.91
0.91
6.78
0.72
0.77
0.68
0.64
0.64
0.76
0.75
0.78
0.78
1.00
0.51
0.56
6.87
0.87
0.83
0.91
0.87
6.88
0..81
0.59
0.94
3.89
НÊP
PBT
SP
EST
Mean
НЕP
PBT
5P
PCP
Mean
НЕP
FBT
SP
PDP
EST
Mean
Counter
1.0
PST HB
1.00
0.60
6.27
0.22
0.58
0.53
0.90
0:78
6.67
6.82
0:63
0.76
0.73
0.85
60.71
0.64
0:68
0.75
0.73
0.90
0.8
0.00
0.53
0.54
0.51
0.50
0.53
0.67
0.59
0.36
0.51
0.84
0.59
0.71
0.66
0.58
0.68
0.78
0.68
0.84
2.6
0.78
$
0.27
6.54
0.94
0.83
0.00
0.82
0.36
0.45
0.51
0.65
0.59
0.71
0.78
3.67
0.4
0.72
0.22
0.51
0.87
0.95
0.70
0.45
10.51
0.51
0.00
0.87
3.72
-02
0.06
0.58
0.50
0.74
0.84
0.65
0.72
0.55
0.93
0.60
НEP
PBT
Mean
PDT
Mean
МЕP PCP
EST
Mear
Figure 12: Results coordinating with other AI baselines. These results plot the normalized cross-play [I5) rewards between baselines. The first 5 subtigures show the results on 5 layouts and the last shows the average results over 5 layouts. The last column of each subfigure represents the average result of collaborating with other baselines. For each baseline, we train different models varying only over random seeds. The syper-paramette Adv., as 0.3 on Coord. Ring, and Counter Circ and a 0.0 on Forced Coord.
is set as 0.5 Cramped Rm, and Asymm.
Ablation of components Al-Human Praxy coordination
Aversqe reward of per epsode
150
SP
140
Sverage roward of per optrode
125
E3T(+R)
P
300
100
80
75
Efficontestt
20
EST[-A]
Cramped Rm. Asymm. Adv. Coord. Ring Forced Coord. Counter Circ.
Mean
(a) Ablations about the main components
(b) Ablations about imple- ment details
Figure 13: Ablation of E3T's components collaborating with human proxies. We plot the average performance over standing in two different positions. (a) (+R) and (+P) respectively integrate the mixed partner policy and the partner modeling module into the self-play framework. For versions with the mixed partner policy (+R), the balance parameter is defined as 0.5, and as 0.3 on Forced Coord.. (b) E3T(context) means that the policy depends on the concatenation of the state and the context embedding. E3T(-A) means that both the partner policy and ego policy use outputs of the partner prediction module additional latent. We plot the results of models coordinating with the human proxy on Coord. Ring with = 0.5.
achieves optimal cross-play returns during testing. These results demonstrate that E3T explore effectively and avoid being stuck in suboptimal on the diagonal line as shown in Figure ((a
Results of MEP with varying population entropy coefficients are shown in Figure 10 The entropy coefficient corresponds the in Equation ( MEP with population=2 can reach the best self-play
returns but fail to coverage to the optimal policy (with the first column, the first and second rows)
21

---

when À = 15, which indicates the hyper-pasn parameter À for reward reshaping is hard to tune. We select 0.99 and À 5.0 for results in Figure (aa)
C.2
Results on Overcooked
Results collaborating with human proxies with starting position switched are shown in Figure 11 E3T achieves superior or comparable performance compared to other baselines.
AI-AI coordination results on layouts Additional results of Al-AI coordination on all layouts and the average performance over all layouts are shown Figure [2] E3T outperforms other baselines on 4 layouts and has comparable performance with population based method MEP on Asymm. Adv. In addition, E3T achieves the highest average performance over all layouts when collaborating with Al baselines. Moreover, MEP and FCP training the ego agent by pairing with pre-trained diverse partner populations are better than SP and PBT, which only improve the coordination rewards during training.
Ablation studies of E3T's components cooperation with human proxies The ablation studies of E3T's components on cooperation with human proxies are shown in Figure [3(a) The average reward of E3T(+PP) is larger than that of SP each layout, thus the partner modeling coordination since the ego policy adapts to the predicted partner actions. In addition, E3T(+R) also outperforms SP on 4 layouts except for the Forced Coord., which indicates that encouraging the partner policy to be more diverse during training time is beneficial to zero-shot coordinating with unseen partners. Moreover, E3T(R+P) that combing the partner modeling and the mixed policy is better than other models on the averaged reward over all layouts. Figure 13(b compares the ego policy that conditions on the context embedding with the one that conditions on the predicted partner action. The results show that the latter policy performs better, suggesting that the predicted partner action is easier to comprehend and respond to than the context embedding. Moreover, E3T(-A) has lower coordination performance than E3T, which demonstrates the advantage of using asymmetric latent variables for ego and partner policies during training, as explained section 4.3 This technique enhances choo coordination by introducing more diversity in the latent space and breaking the asymmetry between ego and partner policies.
assist the zero-shot
Hyperparameter Cramped
Hyper-parameter
spiode
175
150
125
125
1.00
75
50
ESTIA
Average
ET
0707
oftypergara Coord.
Hyperparameter Circ
80
70
70
60
Average reward per
50
40
40
80
Brersge
20
EST
A
ESTRAI ESTe
EST Huray
2=0.9
Figure 14: Ablation studies of e on 4 layouts. In general, the can be set small when the layout space is not large, e.g. smaller for the Forced Coordination layout. For layouts with big space, larger can provide more explanation about different cooperation patterns.
Ablation studies of epsilon (in the range of 10 0.3, 0.5, 0.7, 0.9]) on the other 4 layouts are shown in Figure 14 of the rebuttal material. In general, the epsilon can be set small when the layout space is not large, e.g. smaller epsilon
Further ablation studies of on more layouts Figure 14
22

---

for the Forced Coordination layout can achieve better performance because the activation range is narrow and the partner's coordination ability is more important than behavior diversity in this case. For layouts with big spaces, there exist different coordination patterns, such as multiple paths to deliver soups. Therefore, we normally set the epsilon larger to encourage the policy to explore more coordination patterns. For example, our method achieves higher rewards with epsilon=0.5 when coordinating with human proxies in other layouts, and with epsilon=0.3 or 0.5 when coordinating with other AI baselines.
intuare partner modelin
375
375
Des or
230
533
(a) Effect of partner modeling (h) Effect of asymmetric action distribution
Figure 15: (a) We plot the effect of the partner modeling to Self-play and MEP when collaborating with AI baselines. (b) We plot the effect the asymmetric input setting. E3T(-A) indicates both ego and partner policies are equipped with the partner modeling module.
The effect of the partner modeling module We have incorporated the partner modeling module into two baselines (Self-play and the results demonstrate that the partner modeling module can further enhance the zero-shot coordination performance of baselines when they collaborate with AI baselines.
MEP) as illustrated in Figure [5(a] These
The effect of the asymmetric inputs for the ego and partner policies This work makes use of predicted partner action distribution for ego policy and random action distribution for the partner policy during training. The motivation of the asymmetric input setting comes from two considerations. Firstly, the random action distribution introduces extra randomness into the partner policy, which in turn improves partner diversity. Secondly, this is consistent with the real- world command that Al agents should adapt to human partners' behavior, while different humans may have various cooperative patterns and not necessary to try fit AI agents.
In addition, we have empirically verified that asymmetric input is helpful to zero-shot coordination as illustrated in Figure [1(b) of the rebuttal material, where the performance of our method with asymmetric input slightly outperforms the model that uses the partner modeling for both ego and partner policies on most layouts.
The partner modeling module with only the historical observations accessible In more complex environments, we do not have the ground truth of partner actions, but only the historical observations of the ego policy are available, thus it worth developing an advanced model to predict the partner action from changes in the observed environment. In the Overcooked environment, agents can observe the global state (this is the environmental setting). We also empirically verified that partner action can be predicted from the sequence of ego states on Coord. Ring layout. As shown in Table [S] the prediction accuracy from only the state sequence is comparable that from the state-action sequence. Note that the accuracy of random prediction is around 0.17.
Table 5: The accuracy of partner prediction and the coordination performance under the settings of the state state-action available.
Prediction accuracy Coordination reward with human proxy
state-action
0.54 + 0.04
143.3 + 8.3
state
0.50 + 0.01
139.3 + 6.8
23


Reviews:
[{"review_id": "gvlQQDIdUs", "reviewer": "Reviewer_dkSb", "summary": "This paper introduces a one-stage training framework for human-AI coordination. The key insight is that partner policies should exhibit both coordination skills and diversity. However, the traditional approach of constructing a competent and diverse partner population in the first stage and training an ego policy given this population in the second stage is complex and inefficient. To address this, the author proposes to decouple the partner policy into two components: one aligned with self-play (ego policy) and another component introducing diversity (random policy). By implementing this approach, the paper significantly improves efficiency compared to the Maximum Entropy Population (MEP) method. The effectiveness of the proposed method is demonstrated through experiments conducted on five different Overcooked layout scenarios.", "questions": "1. The partner policy observes random actions, which implies it is unlikely to exhibit coordinated behavior. And the ego policy achieves the best performance when $\\epsilon = 0.5$, which is a considerably large value. Does the ego policy adopt a more conservative approach and attempt to complete the task independently?\n2. The significant performance improvement of this method compared to MEP is intriguing. It appears that this paper can be viewed as a one-staged MEP combined with partner modeling. Is the performance disparity primarily attributed to the partner modeling?\n3. In the ablation study, when partner modeling is removed, what serves as the input for the ego policy?\n4. Minor comments:\na) Figure 6 is difficult to comprehend. The importance of \"environment steps\" is not clear in the figure. I think it would be helpful to use the \"accuracy of action prediction\" as the x-axis, as it could better illustrate the correlation between \"average reward per episode\" and \"action prediction\".", "limitations": "I appreciate that the author acknowledges the limitation of the current method in neglecting general multi-player human-AI coordination tasks.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated and easy to follow.\n2. The key idea behind the proposed method is straightforward and intuitive.\n3. The experiments section of the paper is substantial, covering a range of important aspects such as zero-shot coordination with human proxy, comparisons against human and AI baselines, and a well-conducted ablation study.\n4. This paper offers a sound theoretical analysis of the proposed method.", "weaknesses": "Based on Figure 5, it appears that the proposed method is highly task-sensitive. Therefore, I find it less convincing to solely rely on experiments conducted on five different layouts of Overcooked. It would be beneficial for the authors to consider conducting experiments on various multi-agent reinforcement learning benchmarks, such as matrix games, MPE, Hanabi, SMAC, and others, to provide a more comprehensive evaluation of their method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the time and effort reviewer dkSb has invested in reviewing our paper, and we appreciate that you concur with the main advantages of our method: (1) it is well-motivated and easy to follow (2) the substantial experiments (3) sound theoretical analysis of the proposed method. We have provided detailed explanations and clarifications to resolve your concerns regarding the experiments, and thus respectfully hope you can consider the response to the final decision. \n\n> Q1:  ....... It would be beneficial for the authors to consider conducting experiments on various multi-agent reinforcement learning benchmarks, such as matrix games, MPE, Hanabi, SMAC, and others, to provide a more comprehensive evaluation of their method. \n\nThanks for your suggestion. We point out that we have conducted experiments on a 100x100 matrix game as shown in Figure 4 (a) of the main paper. Our method can achieve the best performance with superior training efficiency than existing baselines. Ablation studies about the random coefficient epsilon are shown in Figure 10 (b) in the appendix, which demonstrate that E3T with $0<\\epsilon<1$ can effectively explore the strategy space to find the optimal strategy and to avoid getting trapped in suboptimal solutions.\n\nWe conduct additional experiments on the Google Football environment's \"3 vs 1 with Keeper\" layout.  We provide more details and results in the R1 of our \"global\" response above.\n\n\n> Q2:The partner policy observes random actions, which implies it is unlikely to exhibit coordinated behavior. And the ego policy achieves the best performance when , which is a considerably large value. Does the ego policy adopt a more conservative approach and attempt to complete the task independently?\n\nThanks for your question. If without partner modelling, the policy tends to complete the task independently. With partner modeling,  the ego policy adapts to diverse partner behaviors well during training to improve the generalization ability. The design of partner policy merging random actions makes the partner policy more diverse in its behaviors while the ego policy can adjust well to different partner behaviors. This is also consistent with the real-world scenario that the ideal AI agent should adapt to human partners' behavior, while different humans may appear in various cooperative patterns and are not necessary to try to fit AI agents.  \n\n> Q3: The significant performance improvement of this method compared to MEP is intriguing. It appears that this paper can be viewed as a one-staged MEP combined with partner modeling. Is the performance disparity primarily attributed to the partner modeling?\n\nThe performance improvement of our method attributes to both the partner modeling and the mixture partner policy. The partner modeling benefits zero-shot coordination since the ego policy can respond to the predicted partner action. The mixture partner policy exhibits behavior diversity and coordination competence by directly combing the ego and random policies. In addition, our method is a single-staged framework and an end-to-end training approach, so it can improve training efficiency by 9x compared to the population-based MEP.   \n\nWe plot the performance of E3T variants and MEP in coordination with AI baselines as shown in Figure 1.(b) of the rebuttal material. These results show that E3T only with the mixture partner policy can achieve comparable performance with MEP, and the partner modeling module can further improve the coordination ability.\n\n> Q4: In the ablation study, when partner modeling is removed, what serves as the input for the ego policy?\n\nWhen the partner modeling is removed, the ego policy only depends on the state and has the form $\\pi_e(a|s)$. When we use partner modeling, the ego policy also depends on the predicted partner action distribution $a_p$ and has the form $\\pi_e(a|s,a_p)$.\n\n> Q5: Minor comments: a) Figure 6 is difficult to comprehend. The importance of \"environment steps\" is not clear in the figure. I think it would be helpful to use the \"accuracy of action prediction\" as the x-axis, .......\n\nThe environment step is the number of interactions used for training checkpoints. It is useful to plot the \"average reward per episode\" and the \"action prediction\" metrics over time to present how the agents improve their coordination and partner modeling skills. We have also illustrated the correlation between these two metrics in Figure 1. (a) of the rebuttal material, where the x-axis is the \"action prediction\" accuracy.\n\n"}, {"review_id": "r4y8B6O0xy", "reviewer": "Reviewer_kGQD", "summary": "This paper proposes a simple end-to-end training mechanism for zero-shot coordination. Existing works in the ZSC literature often make use of population-based training, where a large pool of policies is trained to play well against itself while maintaining a certain form of diversity to prepare for an unknown online partner. This work proposes that sufficient diversity can be achieved by simply adding epsilon-greedy noise into the self-play policy. Performance is further improved by an additional partner modeling module, which takes the past trajectory of the partner and predicts its next action. Experiments against human players and various baselines in the Overcooked environment show some improvements.", "questions": "-  Are there any details that differ from those in [2], e.g. the human proxy partner or the reward function?\n- Can the proposed methods be used in more challenging scenarios, e.g., more players, mixed games, or partial observation?\n\n[2] Strouse, D., McKee, K., Botvinick, M., Hughes, E., and Everett, R. Collaborating with humans without human data. Advances in Neural Information Processing Systems, 34: 14502–14515, 2021.", "limitations": "This paper will be improved by evaluating on more complex environments and showing the scalability of the proposed methods.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Simplicity of method, where only a single policy is learned. This is much more efficient than population-based training approaches.\n- Experiments are performed against various agents, including human proxy, actual human players, and some baselines.\n- Code is available in the submission.", "weaknesses": "- The limited novelty. The method is a simple combination of existing techniques (epsilon-greedy, partner modeling, etc). Besides ablations, a more detailed analysis would provide more insight as to why this works.\n- The Overcooked environments are out-of-date. It is required to further evaluate the method on more complex Overcooked environments[1], e.g.,  more recipes,  and more layouts.\n\n[1 ]Wu, Sarah A., et al. \"Too Many Cooks: Bayesian Inference for Coordinating Multi‐Agent Collaboration.\" Topics in Cognitive Science 13.2 (2021): 414-432.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the time and effort reviewer kGQD has invested in reviewing our paper, and we appreciate that you concur with the main advantages of our method: (1) simplicity and high training efficiency (2) experiments are performed against various agents. We have provided detailed explanations and clarifications to resolve your concerns regarding the insights and experiments, and thus respectfully hope you can consider the response to the final decision. \n\n> Q1: The limited novelty. The method is a simple combination of existing techniques (epsilon-greedy, partner modeling, etc). Besides ablations, a more detailed analysis would provide more insight as to why this works.\n\nThank you for acknowledging the simplicity of our method, which indeed contributes to its higher training efficiency compared to other approaches. However, we'd like to respectively clarify that our method is more than just a straightforward combination of existing techniques. **In fact, we are motivated by the idea of population-based methods that partner policies should be both skilled in coordination and diverse behaviors**. To achieve this, we are the first to decompose the population training objectives of MEP into two policies: one being a simple copy of the ego policy for coordination skills, and the other being a random policy for diverse behaviors.\n\nAlthough this decomposition appears similar to epsilon-greedy, the underlying motivation and induction process are entirely distinct, and we believe our decomposition is experimentally grounded as results show and the simplicity may benefit or inspire more subsequent works based on population-based methods. Besides ablations, we have also provided a theoretical analysis of partner modeling in Proposition 3, which indicates that smaller partner action prediction error leads to better coordination performance. \n\n> Q2:The Overcooked environments are out-of-date. It is required to further evaluate the method on more complex Overcooked environments[1], e.g., more recipes, and more layouts.\n\nThank you for sharing this work with us. Although our paper and [1] both conduct experiments on Overcooked, our contributions differ in their focus. Our paper aims to achieve human-AI zero-shot coordination **without using human data,** while [1] whereas proposes a hierarchical planning method that can quickly complete a recipe. Due to the baselines of [1] being based on model-based dynamic programming, they do not support human-AI zero-shot coordination.  \n\nWe'd like to try to run our method in the environment you suggest, but it is challenging to transfer our codebase and compare zero-shot coordination baselines on the new Overcooked environments[1] within a limited time. In our main paper, we use the same Overcooked environment as human-AI zero-shot coordination baselines (including BCP[3], FCP[2] you mentioned, and MEP), and we have tested our approach on 5 different layouts, which cover the three open, partially passable, and challenging forced coordination scenarios in [1]. These layouts are not as simple as imagined. Here are some analyses of the complexity of these layouts. \n\n|  | *Cramped Room* | *Asymmetric Advantages* | *Coordination Ring* | *Forced Coordination* | *Counter Circuit*   |\n| -- | -- | -- | -- | --- | -- |\n| State space | $5.3 \\times 10^7$ | $1.2\\times 10^{14}$     | $6.8\\times 10^{10}$ | $2.0\\times 10^9$  | $5.8\\times 10^{16}$ |\n\nWith consistently superior performance than baselines in these layouts in the Overcooked environment, we believe our evaluations are sufficient, and we also would like to add the discussion and differences with [1] in the final version of our paper, as per your suggestion. \n\nTo further verify the effectiveness of our method and to explore new coordination challenges beyond Overcooked, we alternatively evaluate our method on the Google Football environment following your suggestions. The details and the results are shown in the R1 of our \"global\" response above.\n\n[1 ]Wu, Sarah A., et al. \"Too Many Cooks: Bayesian Inference for Coordinating Multi‐Agent Collaboration.\" Topics in Cognitive Science 13.2 (2021): 414-432.\n\n[2] Strouse, D., McKee, K., Botvinick, M., Hughes, E., and Everett, R. Collaborating with humans without human data. Advances in Neural Information Processing Systems, 34: 14502–14515, 2021.\n\n[3] Carroll, M., Shah, R., Ho, M. K., Griffiths, T., Seshia, S., Abbeel, P., and Dragan, A. On the utility of learning about humans for human-ai coordination. *Advances in neural information processing systems*, 32, 2019.\n\n> Q3: Are there any details that differ from those in [2], e.g. the human proxy partner or the reward function?\n\nThank you for your question. We follow the same overcooked environment and human proxies as BCP[3]. The reward function of our work is the same as FCP[2], which gives 20 points for each successful delivery. We also use the same layouts and recipes as FCP. The state representations and the training data for human proxies of FCP[2] are different from that of BCP and our work, so we implemented the FCP[2] based on our codebase for a fair comparison with our method. We would like to publish the implementation in the future.\n\n> Q4:Can the proposed methods be used in more challenging scenarios, e.g., more players, mixed games, or partial observation?\n\nFollowing your suggestion, we conduct additional experiments on a three-player cooperative game of the Google Football environment. The details and the results are shown in the R1 of our \"global\" response above.\n\nIn summary, we provided additional experiments on a more complex environment following your suggestions and explain the motivation of our method and the difference from the previous work. We believe our response sufficiently addresses your concerns regarding the experiments and novelty, and thus respectfully hope you can reconsider your final decision. If you have further concerns, please feel free to respond to us and we would like to discuss them with you."}, {"review_id": "AKc5OvkpKj", "reviewer": "Reviewer_dKj6", "summary": "This paper proposes E3T, an method to train agent for zero-shot coordination with humans. The main contribution in E3T is that, in contrast to population-based approaches, it can be trained in a single stage, significantly reducing training time. E3T also includes a model to predict the next action of the partner agents, given that trajectory. By conditioning on that action, the coordination agent can adapt to different partner behaviors according to their observed trajectories. The method is tested on Overcooked against both zero-shot coordination agents and real humans, showing improved performance and lower training time than competitive zero-shot coordination methods.", "questions": "- I am surprised at Fig 4.a results, particularly on th efact that E3T coordinates better with self-play than self-play itself. This seems really counterintuitive, could authors comment on that?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality\n- The proposed method is a simple extension to MEP, with the adition of the partner action prediction module, which have been explored before. Despite highly relying on these 2 components the method is simple and provides gains in training time and performance.\n\nQuality:\n- The paper provides thorough experiments showing that the proposed method can coordinate with several zero-shot coordination agents in different tasks and layouts. The proposed method shows better training time than competitive approaches, as well as improved coordination results. More importantly, it shows significant improvements over baselines when coordinating with real humans.\n\n- Clear and simple to implement method, with comparisons with main coordination approaches and analysis of the entropy and reward bounds of the proposed method.\n\n\nClarity:\n- The paper provides a clear overview of the main methods for zero-shot coordination and their limitations. The proposed method is clearly explained, and section 4.1 provides a clear intution for the design choices, building from the limitations of self-play appraoches such as MEP to motivate different design decisions.\n\n- The explanation of the algorithm, figures and pseudocode provide a clear udnerstanding of the proposed method.\n\n- Clear analysis of the results, and ablations to understand the importance of the two components\n\n\nSignificance:\n- Building agents that can coordinate with other agents in a zero-shot manner is an important problem, and as the paper points out, the two stage training of existing approaches make learning highly inefficient. Proposing a zero-shot coordination coordination agent that can be trained in a single stage is an important problem. Overcooked is a very simplified coordination setting, but one that showcases some of the challenges in zero-shot coordination, and thus showing improved performance and training time resuls is a significant result.", "weaknesses": "- Figure 5.b seems to indicate that the value of epsilon has a strong effect on the final performance and changes for different kinds of tasks, making it potentially hard to find a good parameter for novel tasks. How is that epsilon chosen in the other experiments?\n\n- Figure 5.a shows that partner modeling has a significant effect in the coordination performance. Given the importance of that module, which is compatible with the other proposed baselines, it would be worth testing whether adding that into them would improve their performance results, even if training time would still be higher.\n\n- The mixture policy looks a lot like a self-play policy where a temperature to add noise to the policy is added. What are the main differences to that, if the partner modeling module is eliminated?\n\n- Propositions 1 and 2 are sound, and show that both the entropy and performance of the mixture policy are lower bounded by random and ego policy counterparts, safe for some terms depending on the mixture parameter and action space size. Despite the analysis being sound I am not sure about the value they add that was not known before. The entropy is equal to that of the random policy when \\eps is 1, and decreases as we decrease \\eps (increasing C_1). Similar analysis can be done for Proposition 2, meaning that the ego and random policies serve as upper bounds. How do propositions 1 and 2 help?\n\n- Having access to the partners action and state pairs is a big assumption that may not hold in more complex environments.\n\n- It seems strange that an ego policy that is trained with actions coming from the partner action prediction model can generalize when training the partner, where a random action distribution is used at the input. As epsilon becomes smaller, this gap should increase further. Could authors comment on that?\n\n- Related work: Authors should consider citing, and commenting on the differences with https://arxiv.org/pdf/2104.07750.pdf, which also models the partner for multi-agent collaboration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the time and effort reviewer dKj6 has invested in reviewing our paper, and we appreciate that you concur with the main advantages of our method: (1) simplicity and high training efficiency (2) thorough experiments and superior performance over existing methods (3) clarity of motivation and presentation. We have provided detailed explanations and clarifications to resolve your concerns regarding experiments, and thus respectfully hope you can consider the response to the final decision. \n\n> Q1: How is epsilon chosen in the other experiments?\n\nThank you for your question. Ablation studies of epsilon on the other 4 layouts are shown in Figure 2. of the rebuttal material. For more details and analysis about the epsilon selection, please see our response to Q1 of reviewer DWEk.\n\n> Q2: About adding partner modeling into other baselines\n\nThank you for your suggestion. We have incorporated the partner modeling module into two baselines (Self-play and the state-of-the-art MEP) as illustrated in Figure 3. (a) of the rebuttal material. These results demonstrate that the partner modeling module can further enhance the zero-shot coordination performance of baselines when they collaborate with AI baselines.\n\n> Q3: The mixture policy looks a lot like a self-play policy where a temperature to add noise to the policy is added. What are the main differences to that, ......\n\nThank you for your question. In the implementation, the mixture partner policy $\\pi_p=\\epsilon\\pi_r +(1-\\epsilon) \\pi_e$ is constructed by adding noise $\\pi_r$ (a uniform distribution) to the self-play policy $\\pi_e$ with a temperature $\\epsilon$. Then, the partner action is sampled from this mixed distribution. This method is inspired by the idea of population-based methods that partner policies should be both skilled in coordination and diverse behaviors. Our method simplifies previous population-based methods as a single-staged framework and an end-to-end training approach, so it can improve training efficiency by 9x compared to the state-of-the-art MEP. \n\n> Q4: Propositions 1 and 2 are sound, ...... How do propositions 1 and 2 help?\n\nThank you for acknowledging the soundness of our propositions. Intuitively, the diversity reflected by entropy increases, and the coordination performance decreases with the random coefficient epsilon increasing. We attempt to quantitatively verify these intuitions as Propositions 1 and 2. Regarding the $\\epsilon$ selection, we rely on empirical analysis to balance the coordination ability and behavior diversity as explained in Q1.  \n\n> Q5: Having access to the partners action and state pairs is a big assumption that may not hold in more complex environments.\n\nIn more complex environments, we do not have the ground truth of partner actions, but only the historical observations of the ego policy are available, thus it is worth developing an advanced model to predict the partner action from changes in the observed environment. In the Overcooked environment, agents can observe the global state (this is the environmental setting). We also empirically verified that partner action can be predicted from the sequence of ego states on Coord. Ring layout. As shown in the table below, the prediction accuracy from only the state sequence is comparable to that from the state-action sequence. Note that the accuracy of random prediction is around 0.17. \n||Prediction accuracy|Coordination reward with human proxy|\n|-|-|-|\n|state-action| 0.54(0.04)|143.3(8.3)|\n|state| 0.50(0.01) |139.3(6.8)|\n> Q6: It seems strange that an ego policy that is trained with actions coming from the partner action prediction model can generalize when training the partner, where a random action distribution is used at the input. ......\n\nThe motivation of the asymmetric input setting, with predicted partner action distribution for ego policy and random action distribution for the partner policy during training, comes from two considerations. Firstly, the random action distribution introduces extra randomness into the partner policy, which in turn improves partner diversity. Secondly, this is consistent with the real-world command that AI agents should adapt to human partners' behavior, while different humans may have various cooperative patterns and are not necessary to try to fit AI agents. \n\nIn addition, we have empirically verified that asymmetric input is helpful to zero-shot coordination as illustrated in Figure 3. (b) of the rebuttal material, where the performance of our method with asymmetric input slightly outperforms the model that uses the partner modeling for both ego and partner policies on most layouts.\n\n> Q7: About differences with the mentioned related work\n\nThank you for your recommendation. Our work and this paper both infer agents' intention to enhance multi-agent coordination. The intention inference purposes are different in the two works. This paper infers each agent's visual attention region and designs additional rewards to incentive all agents to focus on the same elements of the environment to reduce the cost of multi-agent exploration. Our work infers partner actions from historical contexts, which helps to adapt well to unseen partners with different coordination patterns by reflecting on predicted partner actions. We will include this work in the related work of the revision.\n\n> Q8: About E3T coordinates better with self-play than self-play itself \n\nThanks. I think you are referring to the coordination results between baselines shown in Fig 4. b of the main paper, where each baseline has 5 different random seeds. Self-play policies may fall into some specific conventions during training and thus fail to cooperate with other self-play policies trained **by different random seeds** during testing. By contrast, E3T with the mixture partner policy and the partner modeling module can adapt well to unseen self-play policies, so it is reasonable E3T can achieve good performance when collaborating with self-play.\n"}, {"review_id": "7IsBtaU8q5", "reviewer": "Reviewer_DWEk", "summary": "The authors propose an Efficient End-to-End training (E3T) approach for zero-shot human-AI coordination. E3T uses a mixture of an ego policy and a random policy as a simple way of training a diverse policy that is still capable of coordination. Unlike prior population based approaches, E3T does not require training populations of agents and thus is more efficient. The authors also propose a partnering module that models the agent’s partner’s actions, enabling improved zero-shot human collaboration. The experiments show a clear improvement over a range of prior methods, testing with both proxy and real human partners.", "questions": "Based on figure 6, the overall accuracy of action predictions is pretty low (less than 60%) — it’s surprising that the partnering module is still helpful even when accuracy is not very high. Why do the authors think this is?", "limitations": "Limitations are clearly discussed in the paper. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The idea is straightforward and easy to employ, and directly addresses a meaningful challenge (efficient zero-shot coordination with humans). The combination of an ego policy and a random policy brings together the strengths of self play for training a coordination policy, whilst also incorporating diversity through the random policy to prevent overfitting to a specific partner. \n-  The inclusion of a partnering module makes sense and shows a clear advantage empirically.\n- The experiments are thorough and show comparisons against a range of prior approaches, including experiments with real people, as well as detailed ablations of the proposed method.", "weaknesses": "- The method seems like it would be sensitive to $\\varepsilon$. While 5b) shows that evaluation for one task, it would be interesting to see of all tasks (i.e. do we need to tune $\\varepsilon $ for each task separately?)\n- nit: missing epsilon in line 7 in the algorithm\n- nit: line 232 has a typo — \"Assume the *learned*...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the time and effort reviewer DWEk has invested in reviewing our paper, and we appreciate that you concur with the main advantages of our method: (1) simplicity of the method (2) the reasonableness and effectiveness of introducing the partner modeling module (2) thorough experiments and superior performance over existing methods. We have provided detailed explanations and clarifications to resolve your concerns regarding experiments, and thus respectfully hope you can consider the response to the final decision. \n\n> Q1: The method seems like it would be sensitive to . While 5b) shows that evaluation for one task, it would be interesting to see of all tasks (i.e. do we need to tune  for each task separately?)\n\nThank you for your question.  Ablation studies of epsilon (in the range of [0.1, 0.3, 0.5, 0.7, 0.9]) on the other 4 layouts are shown in Figure 2. of the rebuttal material. In general, the epsilon can be set small when the layout space is not large, e.g. smaller epsilon for the Forced Coordination layout can achieve better performance because the activation range is narrow and the partner's coordination ability is more important than behavior diversity in this case. For layouts with big space, we normally set the epsilon larger. For example, our method achieves higher rewards with epsilon=0.5 when coordinating with human proxies in other layouts, and with epsilon=0.3 or 0.5 when coordinating with other AI baselines.\n\n> Q2: nit: missing epsilon in line 7 in the algorithm\n>\n> nit: line 232 has a typo — \"Assume the *learned*...\"\n\nThanks for pointing out these typos, and we will correct them in the revision following your suggestions.\n\n> Q3: Based on figure 6, the overall accuracy of action predictions is pretty low (less than 60%) — it’s surprising that the partnering module is still helpful even when accuracy is not very high. Why do the authors think this is?\n\nThank you for your question. Although the partner modeling module can not exactly predict the partner's action(from 6 actions), it has a relatively high prediction accuracy (less than 60%) compared to a random prediction (with a probability of 1/6, less than 20%). Therefore, we think the partner modeling module can potentially reason about the behavior patterns of unseen partners. Figure 6 shows that coordination performance improves as prediction accuracy increases.  "}]

Author rebuttal:
We thank the time and effort reviewers have invested in reviewing our paper. We have provided detailed explanations and clarifications to resolve your concerns regarding experiments and insights. If you have further concerns, please feel free to respond to us and we would like to discuss them with you.

We have conducted further experiments and ablations to address your comments and concerns. The results are presented in the rebuttal PDF file.

**R1: Common response to Reviewers dkSb and kGQD. Additional experiments on Google Football**
To further verify the effectiveness of our method, we conduct additional experiments on the Google Football environment's "3 vs 1 with Keeper" layout, which is a three-player cooperative game with 19 actions in the discrete action space. Following the Other-Play [1], we use the coordination performance among independent training runs ("random seeds") from the same training method to evaluate the zero-shot coordination ability. We report the mean and standard error of the winning rates of scoring a goal in the table below.

|                     | Training performance | Test performance Zero-shot coordination  across different random seeds |
| ------------------- | -------------------- | ------------------------------------------------------------ |
| Self-Play           | 0.87(0.05)           | 0.03(0.01)                                                   |
| E3T(mixture policy) | 0.79(0.04)           | 0.70(0.01)                                                   |

These results show that the policy trained by self-play can coordinate well with itself but it fails to cooperate with policies trained with different random seeds (with different behavior preferences). However, the policy trained by our method (with a mixture policy) can cooperate well with itself and with policies trained under other random seeds. These results indicate that increasing partner diversity during training can significantly improve the generalization ability of trained ego policy.

[1] Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J. “other- play” for zero-shot coordination. In International Conference on Machine Learning, pp. 4399–4410. PMLR, 2020.






Meta-review: The paper proposes an approach for zero-shot coordination with humans, where an agent adapts to different partner behaviors in a collaborative task. The reviewers initially had several concerns including:

(1) Limited set of experiments (e.g., using only 5 layouts)

(2) Limited novelty

(3) Sensitivity of the performance to the parameters

(4) Strong assumptions such as having access to the partner’s state-action pairs

The rebuttal addressed the concerns very well leading to an increase of the rating by some of the reviewers. Despite the weaknesses (such as running experiments in simple environments), the AC believes the paper has merit and the insights are useful for human-AI coordination tasks. Hence, acceptance is recommended.
Decision: Accept (poster)