K-level Reasoning for Zero-Shot Coordination in Hanabi
Authors: Brandon Cui
Hengyuan Hu
Luis Pineda
Jakob Nicolaus Foerster
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Agent Reinforcement Learning
Reinforcement Learning
Zero-Shot Coordination
Deep Reinforcement Learning

Abstract:     The standard problem setting in cooperative multi-agent settings is \emph{self-play} (SP), where the goal is to train a \emph{team} of agents that works well together. 
    However, optimal SP policies commonly contain arbitrary conventions  (``handshakes'') and are not compatible with other, independently trained agents or humans. 
    This latter desiderata was recently formalized by \cite{Hu2020-OtherPlay} as the \emph{zero-shot coordination} (ZSC) setting and partially addressed with their \emph{Other-Play} (OP) algorithm, which showed improved ZSC and human-AI performance in the card game Hanabi. 
    OP assumes access to the symmetries of the environment and prevents agents from breaking these in a mutually \emph{incompatible} way during training. However, as the authors point out, discovering symmetries for a given environment is a computationally hard problem.
    Instead, we show that through a simple adaption of k-level reasoning (KLR) \cite{Costa-Gomes2006-K-level}, synchronously training all levels, we can obtain competitive ZSC and ad-hoc teamplay performance in Hanabi, including when paired with a human-like proxy bot. We also introduce a new method, synchronous-k-level reasoning with a best response (SyKLRBR), which further improves performance on our synchronous KLR by co-training a best response. 

K-level Reasoning for Zero-Shot Coordination in Hanabi
Brandon Cui Facebook AI Research bcui @ fb.com
Hengyuan Hu Facebook AI Research hengyuan @ com
Luis Pineda Facebook AI Research lep @ @ff.ff.com
Jakob Foerster
University of Oxford Jakob.foerster@ eng. ox.ac.uk
Abstract
The standard problem setting in cooperative multi-agent settings is self-play (SP), where the goal is to train Jeam of agents that works well together. However, optimal SP policies commonly contain arbitrary conventions ("handshakes") and not compatible with other, independently trained agents or humans. This latter desiderata was recently formalized by [18] as the zero-shot coordination (ZSC) setting and partially addressed with their Other-Play (OP) algorithm, which showed improved ZSC and human-Al performance in the card game Hanabi. OP assumes access the symmetries of the environment and prevents agents from breaking these in a mutually incompatible way during training. However, as the authors point out, discovering symmetries for given environment is a computationally hard problem. Instead, we show that through simple adaption of k-level reasoning (KLR) 77. synchronously training all levels, we can obtain competitive ZSC and ad-hoc teamplay performance in Hanabi, including when paired with human- like proxy bot. We also introduce new method, synchronous-k-lee k-level reasoning with best response (SyKLRBR), which further improves performance on our synchronous KLR by co-training a best response.
Introduction
Research into multi-agent reinforcement learning (MARL) has recently ranging from large-scale multiplayer zero-sum settings such as StarCraft [35] to partially observable, fully cooperative settings, such as Hanabi [1]. The latter (cooperative) setting is of particular interest, as it covers human-Al coordination, one of the longstanding goals of AI research [10] 6). However, most work in the cooperative syyping-typically modeled Dec-POMDPs has approached the problem in the self-play (SP) setting, where the only goal is to find team of agents that works well together. Unfortunately, optimal SP policies in Dec-POMDPs commonly communicate information through arbitrary handshakes (or conventions), which fail to generalize to other, independently trained, AI agents humans test time.
flurry of activity,
To address this, the zero-shot coordination setting 18 was recently introduced, where the goal is to find training strategies that allow independently trained agents coordinate test time. The main idea of this line of work is to develop learning algorithms that can use the structure of the Dec- POMDP itself to independently find mutually compatible policies, necessary step towards human-Al coordination. Related coordination problems have also been studied by different communities, in
Work done while at Facebook AI Research
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

Syndronowe XLR
Synchronoussc CH
SyRt RBR
Sequidts
Figure 1: Visualization of various hierarchical training schemas, including sequential KLR, syn- chronous KLR, synchronous CH, and new SyKLRBR for levels. Thicker arrows indicate greater proportion of games played with the level. Additionally, red boxes indicate an actively trained agent, while grey boxes indicate fixed agent. Typically To is uniform random agent.
particular behavioural game theory. One of the best-known approaches in this area is the cognitive- hierarchies (CH) framework (4), in which hierarchy of agents is trained. For this method, an agent at level-k models other agents as coming from a distribution up to level k - 1 and best-responds accordingly. The CH framework has been shown model human behavior in games for which equilibrium theory does not match empirical data [4]: thus, in principle, the CH framework could be leveraged to facilitate human-AI coordination complex settings. A specific instance of CH that is relevant to our work is K-level reasoning (KLR) [7]. wherein the level-k agent models the other agents as level-(A: - 1). However, KLR, like many of the ideas developed these works, has not been successfully scaled to large scale coordination problems [18]
In this paper show that k-level reasoning can indeed be scaled to large partially observable coordination problems, like Hanabi. We identify two key innovations that both increase training speed and improve the performance of the method. First, rather than training the different levels of the hierarchy sequentially, as would be suggested by a literal interpretation of the method (as was done as bascline (18), we instead develop synchronous version, where all levels are trained in parallel (see figure I. The obvious advantage is that the wall-clock time can be reduced from linear the number of levels constant, taking advantage of parallel training. The more surprising finding is that synchronous training also acts as a regularizer on the policies, stabilizing training.
The second innovation is that in parallel hierarchy, with more weight being placed on the highest two levels. This constitutes a hybrid approach between CH and KLR, and the resulting BR is our final test time policy. Our method, synchronous-k-e k-level reasoning with a best response (SyKLRBR), obtains high scores when evaluating independently trained agents in cross-play (XP). Importantly, this method also improves ad-hoc teamplay performance, indicating robust policy that plays well with various conventions.
also train best response (BR) to the entire KLR
Lastly, evaluate our SyKLRBR agents paired with proxy human policy and establish state- of-the-art performance, beating recent strong algorithms that, in contrast to our approach, require additional information beyond the game-prov prove-pd observations [18 17].
Our results show that indeed KLR can be adapted address large scale coordination problems, in particular those in which the main challenge is to prevent information exchange through arbitrary conventions. Our analysis shows that synchronous training regularizes the training process and prevents level-k from overfitting to the now changing policy at level-k - 1. In contrast, in sequential training each agent overfits to the static agent at the level below, leading to arbitrary handshakes and brittle conventions. Furthermore, training a best response to the entire hierarchy improves the final ZSC performance and robustness in ad-hoc settings. This intuitive since the BR can carry out on-the-fty adaptation in the ZSC setting.
Our results show that the exact graph-stree structure used, which were similarly studied in and the type of training regime (synchronous vs sequential) can have major impact on the final outcome when adapting ideas from the cognitive hierarchy literature to the deep MARL setting. We hope our findings will encourage other practitioners to seek inspiration in the game theory literature and to scale those ideas to high dimensional problems, even when there is precedent of unsuccessful attempts in prior work.

---

2 Related Work
significant portion of research in MARL has been focused on creating agents that do well in fully cooperative, partially observable settings. A standard approach is through variations of self-play (SP) methods [9] arbitrary policies, which are incompatible with independently trained agents. Clearly, test-time coordination with other, independently trained agents including humans is an important requirement for Al agents that is not captured in the SP problem setting. To address this, [18] introduced the zero-shot coordination (ZSC) setting, where the explicit goal is to develop learning algorithms that allow independently trained agents collaborate at test time.
however, as shown in [8] generally optimal SP agents learn highly
Another recent area of work trains an RL agent separately, and then evaluate its performance in a new group of AI agents or humans assuming access to small amount of test-time data [24] [3] These methods build SP policies that are compatible with the test time agents by guiding the learning to the nearest equilibria [24 33 Other methods use human data to build a human model and then train an approximate best response to this human model, making it compatible with human play [5]. While this presents promising near-term approach for learning human-like policies in specific settings where we have enough data, it does not enable us to understand the fundamental principles of coordination that lead this behavior in the first place, which is the goal of the 7SC setting. Our paper shows that even relatively simple training methods can lead to drastically improved ZSC performance when combined with modern engineering best practices and, importantly, that the performance gains directly translate into better coordination with a human-like proxy and ad-hoc teamplay (without requiring human data in the training process).
Our approach for scaling KLR to Hanabi relies heavily on the parallel training of all of the different levels, where each level is trained on machine and the models are exchanged periodically through a central server. This architecture draws inspiration from population based training (PBT), which was first popularized for hyperparameter turning (20) and then applied in the multi-agent context to train more robust policies in two player zero-sum team settings 19]. PBT has also been used to obtain better self-play policies in Hanabi, both in 12 and []]. In contrast prior work, do not use PBT to avoid local optima or train less exploitable agents but instead leverage this framework to implement KLR and best response to this KLR that is geared towards ZSC and coordination with human-like proxies.
There are a few other methods directly addressing the ZSC framework. The first, other-play (OP) [1]] requires access to the ground truth symmetries of the problem setting and then learns policies that avoid breaking these symmetries during training. OP has previously been applied to Hanabi and KLR compares favorably to the OP results (see Section 4 We also note, that KLR does not require access to the symmetries and can be applied in settings where symmetries are present. The next method, Ridge Rider (RR) (27) uses the connection between symmetries in an environment and repeated eigenvalues of the Hessian, solve ZSC problems. Like KLR, RR does not require prior ground truth access. However, unlike KLR, RR is extremely computationally expensive and has not been scaled to large scale RL problems. Life-Long Learning (LLL) has been studied for ZSC (26). However, LLL requires access to pool of pre-trained agents, and in this case they had access to symmetries, whereas our method never required access to such symmetries and our method compares favorably in the ZSC setting, Lastly, Off- Off-Belief Learning (OBL) [17 has been shown to provide well well-grounded play in hanabi and strong results in the ZSC setting, but requires simulator access to train. We note that KLR doesn't 't require simulator access and also matches or even outperforms OBL on various metrics.
3 Background
3.1 Dec-POMDPs
This work considers class of problems, Dec-POMDPs [2], where N agents interact in a partially observable environment. The partial observability implies that every agent i E (1, has an observation of O(s)) obtained from via the observation function O from the underlying state st E S. In our setting, at each timestep the acting agent samples an action ut from policy ,,, ui Th (u]) where 0 are the weights of the neural networks, and all other agents take no-op actions. Here we use action- action-obserrvation histories (AOH) which denote T¹ {ob, ug F1 "1."",,T-1 J.
3

---

where T is the length of the trajectory, and is the common reward at timestep t defined by the reward function R(s, u). The goal of the agents is maximize the total reward P(r(s()),.))) (R, (T)]; here we consider R₂ (T) to be the discounted sum of rewards, i.e. Re(r) = Σ " where y is the discount factor. Additionally, the environments in this work are turn-based and bounded in length at bmaz.
3.2 Deep Multi-Agent Reinforcement Learning
Deep reinforcement learning has been applied to a multitude of multi-agent learning problems with great success. Cooperative MARL is readily addressed with extensions of Deep Q-learning 25) where the Q-function is parameterized by neural networks to learn to predict the expected return based on the current state 8 and action u, Q(T,, uz) = P(r s.x)) (T).). Our work also builds off of state of the state of the art algorithm Recurrent Replay Distributed Deep Q-Network (R2D2) 22 R2D2 also incorporates other recent advancements such using a dueling network architecture (36). prioritized replay experience [29], and double DQN learning (34). Additionally, we use a similar architecture as the one proposed in [44 and run many environments in parallel, each of which has
actors with varying exploration rates that add to centralized replay buffer.
The simplest way adapt deep Q-learning to the Dec-POMDP setting is through Independent Q-lcarning (IQL) as proposed by [3).. In IQL, every agent individually estimates the total return and treats other agents part of the environment. There are other methods that explicitly account for the multi-agent structure by taking advantage of the centralized training with decentralized control regime [3] 28. However, since our work is based on learning best responses, here only consider IQL.
3.3 Zero-Shot Coordination Setting
Generally, many past works have focused on solving solving the self-play (SP) case for Dec-POMDPs. However, as shown in [18), these policies typically lead to arbitrary handshakes that work well within a team when jointly training agents together, but fail when evaluated with other independently trained agents from the same al algorithm or humans. However, many real-world problems require interaction with never before seen Al agents and humans.
This desiderata was formalized as the zero-shot coordination (ZSC) by 18] in which the goal is to develop algorithms that allow independently trained agents to coordinate test time. ZSC requires agents not to rely on arbitrary conventions as they lead to mutually incompatible policies across different training runs and implementations of the same algorithm. While extended episodes allow for agents to adapt to each other, this must happen at test time within the episode. Crucially, the ZSC setting is stepping stone towards human-Al coordination, since it aims to uncover the fundamental principles underlying coordination in complex, partially observable, fully cooperative settings.
Lastly, the 7SC setting addresses some of the shortcomings of the ad-hoe team play 30 problem setting, where the goal is to do well when paired with any well performing SP policy at test time. As Hanabi shows, this fails in settings where there is little overlap between good SP policies and those that are suitable for coordination. So notably in our ad-hoc experiments we do not use SP policies but instead ones that can be meaningfully coordinated with.
Cognitive Hierarchies for ZSC
The methods we investigate and improve upon in this work are multi-agent RL adaptations of behavioral game theory's 's [3] cognitive hierarchies, where level i agents are a BR to all preceding levels {0. -.- 1}; we define CH's as Poisson distributions over all previously trained levels. We consider k-level reasoning (KLR) to be a hierarchy wehre level l: agents are trained as an approximate BR to level &- - agents 77. Lastly, we propose a new type of hierarchy, SyKLRBR, which is
a hybrid of the two, where we train BR to a Poisson distribution over all levels of a KLR (see appendix
A. A.reniii(A.Ilaa for more details).

---

Algorithm 1: Client-Server Implementation of k-level reasoning, cognitive hierarchies, SyKLRBR.
1: Inputs: level &
2: Initialization: From the server retrieve trainable policy mh and corresponding set of collaborative policies
[g. II = [mx-1] for k-level reasoning, II, (mo...... ".0o....,,.. -, } for cognitive hierarchies, and
ПB.. = {To. m for the Best Response Agent in SyKLRBR.
3: iteration = =0;
4: for epoch in f1, lemmnnummmeeaaaeeee _ammecshss>> } do for iter (1.... num num__ter _eter_eer__pp_eeee jer__ee_epochhh---_____
6:
if iter % server server_update = then UppdateWiihssOnSeeverris
7:
8:
RetrieveServerreiihssTT... end if
10:
Update weights for my towards best response to 11x
11: end for
12:
end for
For all hicrarchies, we start training the first level of the hierarchy कi as an approximate BR uniform random policy over all legal actions F
To- The main idea of this choice is that it prevents the To agent from communicating any information through its actions, beyond the grounded information revealed by the environment (see [17] for more info). It thus forces the agent to only play based on this grounded information provided, without any conventions.
Furthermore, is a natural choice for solving zero-shot coorlination problems since makes the least assumptions about specific policy and certainly does not break any potential symmetries in the environment. Crucially, as is shown in B. in principle, the convergence point of CH and KIR should be a deterministic function of Ty and thus coordination between two independently trained agents.
Hommon-knowlede To should allow for zero-shot
A typical implementation of these training schemas is to train all levels sequentially, one level at time, until the given level has converged. We also draw inspiration from [23] and their deep cognitive central server to store the policies of a given hierarchy and periodically refresh these policies by sending updated policies to the server and retrieving policies we best responding to from the central server.
hierarchies framework (DCH) to instead train all levels simultaneously. To do so,
We implement the sequential training as follows: We halt the training of policy TT at a given level k after 24 hours and start training the next level T&+1 as BR to the trained set of policies I,, where 11, = {To, . - } for the CH case and I1, = [m } in the KLR case. This is the standard implementation of KLR and CH, as it was unsuccessfully explored in Hanabi by [8]
For syuchronous training we train all levels in parallel under client-server implementation (see algorithm Dp. Here all policies {π1, J are initialized randomly on the server. A client training given level {1..... .n]. fetches a policy Ty and corresponding set of partner policies II, and trains Ty as approximate BR to II, Periodically, the client sends a copy of its updated policy Tk. fetches an updated I and then continues to train Tg. The entire hierarchy is synchronously trained for 24 hours, the same amount as single level is trained in the sequential case.
Experimental Setup
5.1 Hanabi Setup
Hanabi is cooperative card game that has has been established as a complex benchmark for fully cooperative partially observable multi-agent decision making [T. In Hanabi, each player can see every player's hand but their own. As result, players can receive information about their hand either by receiving direct (grounded) "hints" from other players, or by doing counterfactual reasoning to interpret other player's actions. In 5-card Hanabi, the variant considered in this paper, there are 5 colors (G, B, W, Y, R) and 5 ranks (1 to 5). "hint" can of color or rank and will reveal all cards of the underlying color or rank in the target player; an example hint is, "your first and fourth cards
In Hanabi there are some illegal moves, e.g., an agent cannot provide hint when the given color or rank is present in the hand of the team mate.
5

---

are 1s." A caveat is that each hint costs scarce information token, which can only be recovered by "discard" card.
The goal in Hanabi is to complete stacks, one for each of the 5 colors, each stack starting with the "I" and ending with the "5". At one point per card the maximum score is 25. To add to stack players "play" cards and cards played out of order cost life token. Once the deck is exhausted or the team loses all lives ("bombs out"), the game will terminate.
5.2 Training Details
For a single agent we utilize distributed deep recurrent Q-Networks with prioritized replay experience 21. Thus, during training there are a large number of simultaneously running environments calling deep Q-networks to generating and adding trajectories to a centralized replay buffer, which are then used to update the model. The network calls are dynamically batched in order to run efficiently on GPUs [[]. This agent training schema for Hanabi was first used in [15), and achieved strong results in the self-play setting. Please see the Appendix A for complete training details.
5.3 Evaluation
We evaluate our method and baseline in both self-play (SP), zero-shot coordination (ZSC), ad-hoc teamplay and human-Al settings. For zero-shot coordination, we follow the problem definition from [18] and evaluate models through cross-play (XP) where we repeat training 5 times with different seeds and pair the independently trained agents with each other.
To test our models' performance against diverse set of unseen, novel partners (ad-hoc team play (30). we next use RL to train two types of agents that use distinct conventions. The first RL agent is trained with Other-Play, which almost always hints for the rank of the playable card to communicate with their partners. For example, played and the partner just draw new "Red 3", the other agent will hint 3 and then partner will play that card deeming that being a red card based on the convention. This agent is therefore referred to Rank Bot. The second RL agent is color-based equivalent of Rank Bot produced by adding extra reward for color hinting during early stage of the training to encourage color hinting behavior. This agent is called Color Bot. More details are in the appendix.
a case where "Red 1" and "Red 2" have been
We also train a supervised bot (Clone Bot) on human data, as a proxy evaluation for zero-shot human-AI coordination. We used dataset of 208, 974 games obtained from Board Game Arena During training. we duplicate the games so that there a training example from the perspective of each player, for a total of 417, 948 examples; that is, observations contain visible private information for exactly one of the players (the other being hidden). Using this dataset, we trained an agent reproduce human moves by applying behavioral cloning. The agent trained by minimizing cross-entropy loss on the actions of the visible player. After each epoch, the agent performs 1000 games of self-play, and we keep the model with the highest self-play score across all epochs.
Level
Self-play
Cross-Play
w/ (k-1)th level
XP (k-1)th level
w/ Color Bot
w/ Rank Bot
w/ Clone Bot
3.64 + 0.50
3.82 + 0.19
0.03 103::00 0.00
0.03=0.00
2.91 0.49
3.84
3.03 + 0.37
10.36 : 1.14
10.08 = 0.55
6.66
1.35
0.45
9.49 0 0.98
7.79
0.66
7.61 :: 1.12
13.32 + 1.29
13.10 0.67
17.99
0.21
12.62 + 0.95
10.49 + 0.94
8.03 + 1.13
8.80 1.26
4
15.63 + 2.35
14.18
1.31
21.41 + 0.15
15.48 + 1.33
13.63 + 2.09
12,47 = 0.79
12.33 + 1.90
16.97 + 1.19
17.17 = 0.98
22.77 = 0.08
17.04 = 1.54
14,80 + 1.77
12.36
= 1.44
13.03 + 1.91
Table I: Performance of sequentially trained KLR for Self-play (SP), Cross-Play (XP), with the
k - 1th level. XP with the A 1th level, with Color Bot, with Rank Bot, and with Clone Bot. We find that the score with level & - drops from over 22 points to roughly 17 in XP. This indicates that in the sequential training, each level-k can overfit to the static level-k and thus develop arbitrary handshakes that propagate along the hierarchy.
6 Results and Discussion
In this section we present the main results and analysis of our work, for sequential training, syn- chronous training, and SyKLRBR. For each variant/level we present self-play cross-play, ad-hoc

---

Level
Self-play
Cross-Play
w/ (k-1)th level
XP (k-1)tth level
w/ Color Bot
w/ Rank Bot
w/ Clone Bot
3.95 0.28
4.55 = 0.11
0.03 1:0:00000
0.03 0.00
3.41 0.32
4.59 0.22
3.70 0.28
14.97 0.31
15.67 0.09
9.95 0.29
9.81 0.12
8.40 = 0.11
7.71 0.225
9.95 0.54
3
20.00 + 0.25
20.67
0.08
19.27
+ 0.42
18.85 + 0.21
14.10 + 0.47
11661 0.36
13.38 + 0.51
21.28 + 0.22
21.05
0.16
22.61
+ 0.12
22.45 + 0.07
15.80 +: 0.57
15.43 + 0.64
14.09 + 0.18
22.29 0.08
22.14 0.12
23.47 0.10
23.16
0.16
17.21 +:
15.90 0.30
15.86 0.23
Table 2: Synchronously trained KLR performance for Self-play (SP), Cross-Play (XP). with the k 1th level, XP with the k - 1th level, with Color Bot, with Rank Bot, and with Clone Bot. Synchronous training produces extremely stable outcomes across the different runs, as indicated by the close correspondence between SP and XP scores. The fact that all levels are changing during training regularizes the process and prevents overfitting to the level k
leamplay and human-proxy results. Although we present self-play numbers, the purpose of this paper not to produce good self self-play scores, rather we are optimizing for the ZSC and ad-hoe settings. Therefore, our analysis focuses on the cross-play and ad-hoc teamplay settings, including the human- proxy results. We demonstrate that simply training the KLR synchronously achieves significant improvement over its sequentially trained counterpart in the ZSC setting. We also demonstrate that our new method SyKLRBR is able further improve upon the synchronous KLR results and achieve SOTA results in certain metrics e.g. scores with clone bot. We also provide analysis into the issues with sequential training and how synchronous training addresses them.
6.1 XP Performance
Table shows the XP scores for other-play, OBL, sequential KLR, synchronous KLR, and SyKLRBR. Changing the training schema from sequential to synchronous significantly increases the XP score to the stute-of-the-art XP score for methods that don't use access to the environment or known symmetries. Thus, by synchronously training the KLR, we are able to achieve strong results in the ZSC setting without requiring underlying game symmetries aether-play) or using simulator access (OBL). SyKLRBR improves upon this result by synchronously training the BR and the KLR, yielding even better XP results. Additionally, tables and show the performance of all levels of KLR. A KLR trained sequentially or synchronously is able to achieve good scores with the 1th level, as level & is explicitly optimized to be an approximate best response to level k: 1. However, the sequential KLR has a significant dropoff for the XP score with the k - 1th level, indicating that sequential KLRs have large inconsistencies across runs. This also indicates that the sequentially trained hierarchy is overfitting to the exact k 1th level. In contrast, the synchronously trained hierarchy keeps its score with the k 1th level close to the XP score with the k 1 level. Thus, by synchronously training the hierarchy we are able to minimize overfitting. For more analysis on overfitting section 6.4
6.2 Ad-hoc Teamplay
Table ssows the scores in the ad-hoc teamplay setting i.c. evaluation with color and rank bot, where the synchronously trained KLR outperforms the sequentially trained KLR for both bots. Similarly, our SyKLRBR further improves performance with both rank and color bot. Thus, the benefits from synchronous training and from training a BR measured in the ZSC setting translate to improvements in hd-hoc teamplay.
6.3 Zero-Shot Coordination with Human Proxies
Up to now we have focused Al agents playing well with each other. Next measure performance of bots playing with bots trained on human data, representing a human proxy, specifically the Clone Bot described in Section 5.3 In table B we present overall performance of our agents when trained under OP, OBL, sequentially KLR, synchronously KLR, and SyKLRBR. As a reference, we trained a bot using [8] OP, which when paired with Clone Bot achieved average score
of 8.55
When synchronously trained, KLR monotonically improves its score with Clone Bot. By level the synchronously trained KLR is able to achieve score of 15.801 + 0.26; the sequentially trained KLR has significantly lower score. Additionally, the synchronously trained KIR Clone Bot score is comparable to the more algorithmically complex OBL bot, which furthermore requires access
7

---

Method
Self-play
Cross-Play
w/ Color Bot
w/ Rank Bot
w/ Clone Bol
Limitations
Other-Play
24.14 = 0.03
21.77 = 0.68
4.05 0.37
8.55 0.48
Sym Env
OBL (level 4)
24.10 = 0.01
23.76 + 0.06
21.78 + 0.42
14.46
0.59
16.00 + 0.13
Sequential
16.97 + 1.19
17.17 + 0.98
14.80 + 1.77
12.36
1.44
13.03 + 1.91
Synchronous
22.29 + 0.08
22.14 + 0.12
17.21 + 0.86
15.90
0.30
15.86 + 0.23
SyKLRBR
23.40 + 0.07
23.29 + 0.05
17.62 + 0.69
17.01
+ 0.45
16,59 + 0.16
Table 3: Other-Play. OBL level 4, level 5 Sequential KLR, level Synchronous KLR, and SyKLRBR for Self-play (SP), Cross-Play (XP), ad-hoc play with Color Bot, Rank Bot, and Clone Bot. We include methodological limitations, requiring underlying game symmetries (sym) or requiring access to the simulator (env). Both synchronous training and our SyKLRBR improve upon XP, ad-hoc teamplay, and clone-bot scores. Also SyKLRBR achieves state-of-the-art results with clone-bot.
to the simulator. Lastly, our new method, SyKLRBR, is able to achieve state-of-the. results in coordination with human proxies. Therefore, through simply synchronously training KLR we are able to produce bots that cooperate well with human-like proxy policies at test time and by co-training BR we obtain state-of- of-te-of-the-arr arrt results.
Spack
artton Hest do
Figure 2: A plot of probability distributions of actions agent at level k- 1 will play with level k for KL. trained sequentially and synchronously. At lower levels, the synchronous KLR is stochastic, but at higher levels it stabilizes. The stochasticity in the lower levels broadens the range of policies seen and robustifies lower levels, which propagates upwards and leads to stable, robust policies.
Training Schema Sequential
% Bomb out with (k- level % Bomb out in XP with (k-1)th level 0.4 = 0.2
19.8 + 18.0
Synchronous
0.4 + 0.2
0.6 + 0.3
Table 4: Percentage of bombing out for the level 5 agent playing with the level 4 agent it trained with (k-1))th level) or the other level agents unseen training time (XP with (k- I )t level). By synchronously training we prevent overfitting to the policy distribution of a fixed agent. This allows us to be better off distribution, which significantly reduces bombing out in the XP case.
6.4 Observations of Training Behaviors
We plot the probability that an agent from k - will take a given type of action u when playing with an agent from level in Figure At low levels of the hierarchy (levels 2, 3), the synchronous hierarchy is trained as approximate best response to a set of changing policies. Higher up in the hierarchy the change in the policies gets attenuated, leading to stable policies towards the end of training. By synchronously training the hierarchy, we allow each policy to see wider distribution of states and ensure it is robust to different policies at test time. This robustness is reflected in the improved ZSC, XP with A 1th levels, ad-hoc teamplay, and human- -prxxy coordination.
In table 4 we present the percentage of "bombing out" for the level agent playing with the level agent it trained with or level 4 agents from other seeds of our KLRs. "Bombing out" is a failure case when too many unplayable cards have been played, leading to the agent losing all points the game. Both the sequential and synchronous KLRs rarely bomb out when paired with their training partners. Only the sequential KLR bombs out significantly more in XP, roughly 20% compared with <1% with the agent it trained with. This high rate illustrates that the agent is making a large number of mistakes, indicating that is off-distribution in XP. We verified this by checking the Q-values of the action the agent takes when it bombs out. The vast majority of cases (90%+) the agent has positive Q-value
8

---

for its play action when it bombs out and negative Q-values associated with other actions (discarding and hinting). Since the play action is causing the large negative reward, while the other actions are safe, these Q-values are clearly nonsensical, another indicator that the agent is off-distribution. All of this illustrates that the "bomb out" rate a good proxy for being off-distribution, which shows that the synchronously trained KLR agents are more on-distribution during XP testing.
6.5 Understanding Synchronous Training
At a training step t. the synchronous KLR иÿ trained towards a BR to - 1- There are a few reasons why synchronous training helps regularize training. First of all, weights are typically initialized s.t. Q-values at the beginning of training are small, so under a softmax all π.. vi k are close to uniform. Secondly, over the course of training the entropy for each policy decreases, as Q-values become more accurate and drift apart, so T! (the final policy) will have the lowest entropy. Lastly, the entropy of the average policy across the set { - 1. -,," } is higher than the average of the entropies from the same set (e.g. the average of two deterministic policies is stochastic, but the average entropy of the policies 0). Therefore, by playing against a changing distribution over stochastic policies we significantly broaden the support of our policy.
Entropy in .T-1 has two effects: First of all it increases robustness by exposing क, more states during training and, secondly, more entropic (i.e. random) policies will generally induce less informative posterior (counterfactual) belief's (a fully random policy completely uninformative posterior). As a consequence, the BR to set of different snapshots of a policy - is both more robust and less able extract information from the actions of kz-1 than the BR to only the final - This forces the policy to rely to a greater extend on grounded information in the game, rather than arbitrary conventions.
the extreme case, with
Empirically we show this effect by training belief model on a oं and on set of snapshots of of for = (100, 200, .000).)). The cross entropy of belief model for the final xं' is 1.58 + 0.01, while the cross entropy for the set is substantially higher (1.70 + 0.01) (both averaged over seeds).
6.6 Cognitive Hierarchies (CH)
We also use our synchronous setup to train a CH (i.e., a best response to a Poisson sample of lower levels) and present the results in table 5 We note that the scores for the synchronous CH are lower than the synchronous KLR in terms of SP, XP, ad-hoc teamplay, and human- -poxxy coordination. This likely because even at higher levels, the majority of the partner agents come from lower levels, as result the performance is similar to that of KLR level 3. Additionally, computing best response to a mix of lower level agents makes the hints provided less reliable and disincentivizes the agent to hint.
Level
Self-play
Cross-Play
w/ Color Bot
w/ Rank Bot
w/ Clone Bot
4.11 + 0.29
4.33 + 0.12
4.06 + 0.30
4.72 + 0.40
4.21 + 0.28
15.61 + 0.27
#.10
8.77 0.61
8.58
9.26 + 0.51
3
19.71 0.12
19.51 0.07
10.43
11.52
13.10 + 0.26
20.85
0.17
20.57 0.08
12.90
13.75 0.47
13.59 + 0.33
5
21.65 + 0.21
21.42 + 0.10
14.13 0.16
15.12 0.27
14.59 + 0.25
Table 5: CH synchronously trained performance for Self-play (SP), Cross-Play (XP), and ad-hoc play with Color Bot, Rank Bot, and Clone Bot. In the CH setting are unable to obtain very strong results, regardless of setting.
7 Conclusion
How to coordinate with independently trained agents is one of the great challenges of multi ageet learning. In this paper we show that classical method from the behavioral thme-theory literature, k-level reasoning, can easily be adapted to the deep MARL setting to obtain strong performance on the challenging benchmark task of two player Hanabi. Crucially, we showed that a simple engineering decision, to train the different levels of the hierarchy at the same time, made a large difference for the final performance of the method. Our analysis shows that this difference is due to the changing

---

policies at lower levels regularizing the training process, preventing the higher levels from overfitting specific policies. We have also developed new method SyKLRBR, which further improves on our synchronous training schema and achieves tate-of-the-an results for ad-hoc teamplay performance.
This raises number of possibilities for follow-up work: What other ideas have been unsuccessfully tried and abandoned too early? Where else can we use synchronous training as a regularizer? Another interesting avenue to investigate whether the different levels of the hierarchy are evaluated off- distribution during training and how this can be addressed. Level-k is only trained on the distribution induced when paired with level-k 1, but evaluated on the distribution induced from playing with k + 1. Furthermore, extending the work of [13] and searching for the optimal graph-structure during training a promising avenue for future work.
Limitations
Although synchronous training schema does alleviate overfitting in the KLR case, there is still large gap between cross-play and playing with the k 1th level. This indicates that there still exist some unfavorable dynamics in the hierarchy. Similarly, although work does provide steps towards human-Al cooperation, the policy can still be brittle with unseen bots resulting in lower scores.
Broader Impact
We have demonstrated that synchronously training a KLR greatly improves on sequentially training a KLR in the complex Dec-POMDP setting. Hanabi. This in essence is simple engineering decision, but it improves performance to very competitive methods. Our method, SyKLRBR, synchronously trains a BR to the KLR, which resulted in SOTA performance for coordination with human proxies through "clone bot." We have found that our method works as it provides distributional robustness in the trained policies. As a result, it can be a positive step towards improving human-Al cooperation. Clearly no technology is safe from being used for malicious purposes, which also applies to our research. However, fully-cooperative settings are clearly targeting benevolent applications.
References
[1] Nolan Bard, Jakob N. Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H. Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, lain Dunning, Shibl Mourad, Hugo Larochelle, Mare G. Bellemare, and Michael Bowling. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 180:103216, 2020.
[2] Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Math. Oper. Res., 27(4):819-840, November 2002.
[3] Colin Camerer, Teck Ho, and Juin-Kuan Chong. A cognitive hierarchy theory of one-shot games and experimental analysis. Social Science Research Network, 08 2003.
[4] Colin F Camerer, Teck-Hua Ho, and Juin Kuan Chong. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3):861-898 2004.
[5] Micah Carroll, Rohin Shah, Mark Ho, Thomas Grifliths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. Advances in Neural Information Processing Systems, 10 2019.
[6] Shan Carter and Michael Nielsen. Using artificial intelligence to augment human intelligence. Distill, 2017. https://dssilllpubb2001 7/aia.
[7] Miguel Costa-Gomes and Vincent P. Crawford. Cognition and behavior in two-person guessing games: An experimental study. In American Economic Review, volume 96(5), pages 1737-1768, 2006.
[8] Sam Devlin and Daniel Kudenko. Plan-based reward shaping for multi-agent reinforcement learning, The Knowledge Engineering Review, 31(1):44-58, 2016.
10

---

[9] Sam Devlin, Daniel Kudenko, and Marek Grzes. An empirical study of potential based reward shaping and advice in complex, multi aulti-agent systems. Advances in Complex Systems, 14:251- 278, 11 2011.
[10] D. C. Engelbart. Augmenting Human Intellect: A Conceptual Framework. Air Force Office of Scientific Rescarch, AFOSR-3233 www bootstrap ottp///uddot///rrieede0000000000 ahi62index html 1962.
[11] Lasse Espeholt, Raphaël Marinier, Piotr Stanczyk, Ke Wang, and Marcin Michalski. Seed rl: Scalable and efficient deep-rl with accelerated central inference. In International Conference on Learning Representations, 2020.
[12] Jakob Foerster, Francis Song, Edward Hughes, Neil Burch, lain Dunning, Shimon Whiteson, Matthew Botvinick, and Michael Bowling. Bayesian action decoder for deep multi-agent reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Leurning, volume 97 of Proceedings of Machine Learning Research, pages 1942-1951. PMLR, 09-15 Jun 2019.
[13] Marta Garnelo, Wojciech Marian Czarnecki, Siqi Liu, Dhruva Tirumala, Junhyuk Oh, Gau- thier Gidel, Hado Hasselt, and David Balduzzi. Pick your battles: Interaction graphs as population-level objectives for strategic diversity. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '21, page 1501-1503, Richland, SC, 2021. International Foundation for Autonomous Agents and Multiagent Systems.
[14] Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado van Hasselt, and David Silver. Distributed prioritized experience replay. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.nee 2018.
[15] Hengyuan Hu and Jakob N. Foerster. Simplified action decoder for deep multi-agent reinforce- ment learning. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[16] Hengyuan Hu, Adam Lerer, Noam Brown, and Jakob Nicolaus Foerster. Learned belief search: Efficiently improving policies in partially observable settings, 2021.
[17] Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, David Wu, Noam Brown, and Jakob N. Foerster. Off-belief learning. (To Appear) ICML, 2021.
[18] Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "Other play" for zero-shot coordination. In Hal Daumé III and Aarti Singh, editors, Proceedings the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages -399-4410. PMLR, 13-18 Jul 2020.
[19] Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil Rabinowitz, Ari S Morcos, Avraham Ruderman, al. Human-level performance in 3d multiplayer games with population-based reinforcement learn- ing. Science, 364(6443):8559 865, 2019.
[20] Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint 17X1v:/711.09440 2017.
[21] Steven Kapturowski, Georg Ostrovski, John Quan, Rémi Munos, and Will Dabney, Recurrent experience replay in distributed reinforcement learning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019.
[22] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.

---

[23] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls. Julien Perolat, David Silver, and Thore Graepel. A unified game-theorethe approach to multiagent reinforcement learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30, pages 4190-4203. Curran Associates, Inc., 2017.
[24] Adam Lerer and Alexander Peysakhovich. Learning existing social conventions via observa- tionally augmented self-play. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES '19, page 107-114, New York, NY, USA, 2019. Association for Computing Machinery.
[25] V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare, A. Graves, M. Ried- miller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):52995533 533, 2015.
[26] Hadi Nekoei, Akilesh Badrinaaraayanan, Aaron Courville, and Sarath Chandar. Continuous coordination as realistic scenario for lifelong learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8016-8024. PMLR, 18-24 Jul 2021.
[27] Jack Parker-Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alexander Peysakhovich, Aldo Pacchiano, and Jakob Foerster. Ridge rider: Finding diverse solutions by following cigenvectors of the hessian. Advances in Neural Information Processing Systems, 33:753-765 2020.
[28] Tabish Rashid, Mikayel Samvelyan. Christian Schröder de Witt, Gregory Farquhar, Jakob N. Foerster, and Shimon Whiteson. QMIX: monotonic value function factorisation for deep multi- agent reinforcement learning. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Leurning, ICML. 2018, Stockholmsmüssun, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Muchine Learning Research, pages 4292-432 4901- PMLR, R, 2018
[29] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Repre- sentations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[30] Peter Stone, Gal A Kaminka, Sarit Kraus, and Jeffrey S Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination. In Twenty-Fourt AAAI Conference Artificial Intelligence, 2010.
[31] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Pro- ceedings of the 17th international conference on autonomous agents and multiagent systems, pages 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
[32] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceed- ings of the tenth international conference on machine learning, pages 330-337, 1993.
[33] Mycal Tucker, Y. Zhou, and Julie Shah. Adversarially guided self-play for adopting social conventions. ArXiv, abs/2001. 105994, 2020.
[34] Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirfieth AAA/ Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 2094-2100. AAAI Press, 2016.
[35] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, P. Georgiev, A. S. Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler,, J. Agapiou, Julian Schrittwieser, John Quan, Stephen Gaffney, S. Petersen, K. Simonyan. T. Schaul, H. V. Hasselt, D. Silver, T. Lillicrap, Kevin
12

---

Calderone, Paul Keet, Anthony Brunasso. D. Lawrence, Anders Ekermo, J. Repp, and Rodney Tsing. Starcraft ii: A new challenge for reinforcement learning. ArXiv,
2017.
[36] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanctot, and Nando de Freitas. Dueling network architectures for deep reinforcement learning. Kilian Q Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICMI. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1995-2003, JorR.org, 2016.
Maria-Florina Balcan and
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No], or [N/A]. . You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license to the code and datasets? [No] proprietary.
The code and the data are
Did you include the license the code and datasets? [N/]]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss limitations in section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] discussed in section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] we included all information needed to reproduce results in section and appendix A We will release
an open source version of our code and copies of our trained agents later.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] They are included appendix [A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] reported in appendix A
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "gEO67Go11f0", "reviewer": "Reviewer_Y1va", "summary": "This paper proposes a new solution for the zero-shot coordination problem in Hanabi. Specifically, the authors took the k-level reasoning algorithm and made the training synchronous instead of sequential. Their proposed modification SyKLRBR also trains the agent at level ‘k’ to learn to generate best response to all the previous level players. Authors show that their proposed algorithm has better ad-hoc performance and human coordination than other methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nIn terms of novelty, this paper does not propose any new algorithm. It takes an existing idea from game theory and tweaks it a bit so that it can be applied to large scale problems like Hanabi. However, the authors have executed this idea very well and I will not penalize the paper for the lack of novelty. There is value in scaling up existing ideas as well.\n\nWhile I am impressed with the results in this paper, the writing of this paper needs to be improved.\n\n1. I am not able to get a clear idea of what is SyKLRBR doing and how it is different from Synchronous KLR. Figure 1 is very confusing and it is not helping. Is it that only the last level agent learns to play with all the lower-level agents? While I understand Seq KLR and Sync KLR, I need a clear explanation for what Synch CH and SyKLRBR are doing. Pseudocode for all these algorithms in the appendix will help.\n\n2. Introduction and related work have a lot of sentences that are easy to understand only during the second read. This is mainly because the authors keep mentioning levels and they introduce k-level reasoning only later in the paper.\n\n3. Nekoei et al. 2021 also solve the problem of zero-shot coordination for Hanabi and is not mentioned in the related work. Can you provide me with a qualitative comparison of their method and yours? I know quantitative comparison during rebuttal is not plausible due to time constraints, but I highly recommend you to add this comparison for the final version or the next version of this paper.\n\n4. Section 6.6: A best response to a Poisson sample of lower levels. What do you mean by that? With the given explanation, one cannot implement and reproduce your results.\n\nOverall, writing is a major issue with this paper. The writing is vague at some points and hence I cannot reimplement and reproduce results in this paper. I ideally would like to read the next version of this paper before I strongly accept this paper.\n\nReferences:\n\n\n[1] Nekoei et al. 2021. Continuous Coordination As a Realistic Scenario for Lifelong Learning.\n\n\nMinor comments:\n\n1. Line 19 -> did you mean “multi-player” games such as starcraft?\n2. Line 141 -> solving solving\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "YdduPFAIosD", "reviewer": "Reviewer_4AuN", "summary": "This paper proposed a new method to solve the Hanabi game.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper utilized k-level reasoning to solve the Hanabi game. Their method is quite simple. But I think they should give more theoretical analysis and demonstrate the effectiveness of their method. For example, they should compare their method with MAPPO[1]. And they also need to demonstrate the generalization of their method by applying their method to other multi-agent games.\n\n\n\n[1] Yu C, Velu A, Vinitsky E, et al. The surprising effectiveness of mappo in cooperative, multi-agent games[J]. arXiv preprint arXiv:2103.01955, 2021.\n\nAfter reading the author's response, I have increased the rating from 3 to 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. They should evaluate their method on more benchmarks, such as MPE, google football and other card games.\n\n2. They should compare their method with recent MARL algorithms, such as MAPPO.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "F1mek6WG-hz", "reviewer": "Reviewer_NyYA", "summary": "This paper demonstrates an approach to hierarchically train agents for Hanabi, adapted from a classical approach called k-level reasoning. The authors demonstrate that training these hierarchies in parallel improves performance by reducing overfitting. They present a novel training schema they call SyKLRBR, which demonstrates SOTA performance with a couple of agents. The paper ends with a large number of experiments and discussion. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The approach is certainly novel, both in terms of the simultaneous training and the specific SyKLRBR paradigm. The authors draw attention to the fact that they managed to get an abandoned older approach to work. However, I don't know the history of this approach sufficiently to comment on that. \n\nQuality: The quality of the paper is quite high. The experiments are extensive and the discussion is rich. I have no major concerns when it comes to paper quality. \n\nClarity: The paper is overall fairly clear. However, there are a few issues. To start, Figure 1 is rather unclear. The visual language is inconsistent (why are some arrows on the left side of the screen and some on the right?), and many of the choices are not explained (the choice of colours and the upward arrows/floating dots). While I mostly picked up on what was going on from context, I think the figure might need to be revised substantially. Later, the authors claim \"These datapoints... confirm that ZSC is a great proxy setting for human-AI coordination and ad-hoc team play\". However, it is unclear what they mean by this. Further, the way that \"clone bot\" is referred to across the paper is unclear. Sometimes the clone bot is correctly referred to as a proxy, but at other times the authors make claims suggesting that performance with the clone bot is equivalent to improved performance with humans, such as \"the performance gains directly translate into better human-AI coordination\". This is unclear at best and overblown at worst. \n\nSignificance: The authors present a clear benefit to their adapted k-level reasoning. However, many of their claims (as mentioned in the last paragraph) are somewhat unclear. In particular, there's no evidence shown that clone bot is a particularly good proxy for human behaviour. The authors do not present any comparison between the human training data and clone bot to get a sense of how well it corresponds to human behaviour. Given that a significant portion of the author's claims rely on the quality of clone bot as a proxy, I would have expected something like that instead of some of the existing analysis (perhaps Table 4, which seems to just reinforce other results). However, even with this I think that the other results from the paper are significant enough to largely outweigh my concerns with clone bot.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The major limitation I think relates to the discussion above, that the authors have not actually evaluated their method alongside humans. However, I don't believe this is strictly necessary for the majority of their claims. In terms of social impact I don't foresee this being an issue for this particular paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CrCSL-BgL4", "reviewer": "Reviewer_VvuS", "summary": "An important problem in multi-agent RL is how to train agents to cooperate and coordinate well with humans. One approach has been to train agents that can coordinate well with themselves, using self-play. Recently more attention has been paid to the problem of coordinating well with independent training runs: referred to as Zero-Shot Coordination, as an easier proxy for coordinating with particular other policies, such as humans. A benchmark game for this has been Hanabi, which is fully cooperative and, for strong play, requires sending signals whose meanings require multi-step chains of reasoning to deduce, resulting in complex conventions. One way to understand these chains has been via the so-called “cognitive hierarchy” (CH) from behavioural game theory, that was invented to characterize human non-equilibrium play in some settings: it’s a hierarchy in which higher levels select optimal strategies assuming other players are following strategies from lower levels.\n\nPast work has tried to tackle ZSC in Hanabi using this idea directly (training a chain of policies that each best-respond to the preceding one), but the resulting training process did not manage to avoid arbitrary conventions, hurting ZSC performance. Recent work has explored more sophisticated ways of rooting out arbitrary conventions, eg by using carefully grounded priors and an expensive simulator to reason about the state distribution, or by ensuring that policies don’t learn to rely on a particular way of breaking symmetries in the game (via data augmentation).\n\nThis paper revisits the chain-of-best-responders method, and modifies the training schema by training each policy in the chain simultaneously. This results in policies that have near-SOTA ZSC performance; behavioural analysis is shown to support the explanation that this is because the moving-target opponents strongly regularize away the overfitting that otherwise occurs when training best-responders against fixed opponents. With another tweak (learning a best-response to a mixture of the chain of policies), a policy is trained that is even stronger in ZSC and self-play, and achieves SOTA in playing alongside a human-play proxy policy (as well as consistently good performance in some other ad-hoc teams). The presented method seems to be the first to achieve good ZSC in Hanabi without requiring bespoke components such as a model of all of the symmetries or a simulator to use for deriving belief distributions, and is therefore an important contribution that’s likely to be applicable to many other settings for learning coordination and strategic behaviour.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper makes an important contribution to the literature by revealing that a previously-published negative result can be reversed to a strong positive result via some technical changes. The problem is well-motivated and relevant, and the paper is generally well-structured and informative.\n\nThe key method (synchronously trained KLR) is not very novel, nor is it accompanied by theoretical optimality results as other recent results in Zero-Shot Coordination have done. However, it is more readily applicable to more domains, the empirical results are competitive (and the comparison with previous methods is convincing), and the approach taken was dismissed as an unsuccessful idea in previous work.\n\nThe regularizing advantages of synchronous training are well-explored in the paper, with some interesting analyses of the effects on entropy, posteriors, and out-of-distribution-ness of bomb-outs. Another analysis that would be informative regarding the difference between sequential and synchronous training would be some measurement of the symmetry-invariance of the policy, since past work argued this was key to ZSC - this would also be interesting to compare with Other-Play, to see whether the XP benefit from synchronous training is accounted for.\n\nBut there are a couple of issues with other parts of the paper. For example, the paper presents an additional contribution SyKLRBR as an improvement on KLR, but since SyKLRBR requires training another BR alongside the K BR's in the KLR, the fair comparison would be with (K+1)LR. Extrapolating Table 2 suggests that KLR with K=6 may be on par with SyKLRBR with K=5; an experiment would be warranted to verify whether SyKLRBR provides any benefit.\n\nAnother thing that was unclear was the parameter of the Poisson distribution used in the implementation of both SyKLRBR and CH. The value wasn’t given, and eg a value $\\rightarrow\\infty$ would collapse both of them to KLR. (In the CH definition from Camerer et al, the Poisson distribution for level k needs to be restricted to 0, …, k-1 and rescaled.) As a result it’s unclear how to interpret the paper’s finding that CH significantly underperformed KLR.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors revisit classic ideas and show that with small modifications they can be made to achieve state-of-the-art coordination with held-out partners in Hanabi. Additionally, the authors provide some insight into why their modifications work, namely in curbing overfitting. While there were some concerns about novelty, the (mostly well-presented) results speak for themselves and make an interesting contribution to the ad-hoc teamplay / zero-shot coordination literature.

That said, I have serious concerns with the current discussion of "human-AI coordination" that I expect to be addressed for the camera-ready. The current draft repeatedly refers to demonstrating "human-AI coordination", however this claim is misleading, since evaluation is done only with a human proxy behavioral cloning (BC) agent, and not actual humans. Although the authors refer to previous circumstantial evidence showing agent scores with BC bots are similar to that with actual humans, this does not imply that this should be true of all agents, and seems an especially dangerous claim for coordination games. Moreover, using human proxies over actual humans removes the possibility of qualitative feedback from human players, as well as subjective preferences over agents, both of which are important components of evaluating human-AI coordination. Indeed, my confidence in the authors claim of BC-human equivalence is further weakened by claims in the draft that their results "confirm that ZSC [aka cross-play (XP)] is a great proxy setting for human-AI coordination and ad-hoc team play." While there seems to be a correlation in all score types, this claim is overblown. For example, in table 3, OP and synchronous KLR achieve similar cross-play scores, but the latter gets nearly double the score of the former with the human proxy - that's a big difference that would be missed if only doing cross-play! If the match between evaluation with human proxies and real humans is as tenuous, the human-AI coordination statements could be worse than misleading and actually wrong. Thus, I expect to see the human-AI coordination claims removed throughout the draft, including section titles, and clarified to specifically refer to coordination with human proxies or BC bots. Moreover, I would like to suggest that the authors in the future do not double down on coordination with human proxy bots alone, since this may well lead to a false sense of progress on their stated goal of coordination with real humans.

One more minor point of feedback - while the set of baselines included is fairly strong and appropriate, there are a couple more that would make the paper's claims stronger. One is simultaneous training but with a fully connected interaction graph. While the authors evaluate a few different interaction graphs, they don't seem to evaluate this very simple one, as far as I can tell. Another are BRs to the various bots (especially to the human proxy), which would help place in context how well the evaluated agents are performing. Finally, as pointed out by Reviewer VvuS, there are issues with the current CH baseline; however, the authors seem aware and are working on fixing them.

Finally, a few more minor points on presentation: Multiple reviewers found figure 1 confusing. This should be easy to improve. Also, I personally found figure 2 to be an odd way to represent probability distributions. The line segments connecting probabilities here are meaningless. Plotting points on a simplex, for example, might be more clear. Finally, [1] is a relevant study on different interaction graphs in multi-agent RL that e.g. should likely be cited for the claims on lines 64 and 351.

[1] Garnelo et al, Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity, AAMAS 2021
Decision: Accept (Poster)