K-level Reasoning for Zero-Shot Coordination in Hanabi

Introduction

Research into multi-agent reinforcement learning (MARL) has recently seen a flurry of activity, ranging from large-scale multiplayer zero-sum settings such as StarCraft to partially observable, fully cooperative settings, such as Hanabi . The latter (cooperative) setting is of particular interest, as it covers human-AI coordination, one of the longstanding goals of AI research . However, most work in the cooperative setting—typically modeled as a Dec-POMDPs—has approached the problem in the self-play (SP) setting, where the only goal is to find a 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 or humans at test time.

To address this, the zero-shot coordination setting was recently introduced, where the goal is to find training strategies that allow independently trained agents to coordinate at 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, a necessary step towards human-AI coordination. Related coordination problems have also been studied by different communities, in particular behavioural game theory. One of the best-known approaches in this area is the cognitive-hierarchies (CH) framework , in which a 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 to model human behavior in games for which equilibrium theory does not match empirical data ; thus, in principle, the CH framework could be leveraged to facilitate human-AI coordination in complex settings. A specific instance of CH that is relevant to our work is K-level reasoning (KLR) , wherein the level-$k$ agent models the other agents as level-$(k-1)$. However, KLR, like many of the ideas developed in these works, has not been successfully scaled to large scale coordination problems .

In this paper we 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 a baseline in ), we instead develop a synchronous version, where all levels are trained in parallel (see figure 1). The obvious advantage is that the wall-clock time can be reduced from linear in the number of levels to 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 we also train a best response (BR) to the entire KLR 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-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 a robust policy that plays well with various conventions.

Lastly, we evaluate our SyKLRBR agents paired with a proxy human policy and establish new state-of-the-art performance, beating recent strong algorithms that, in contrast to our approach, require additional information beyond the game-provided observations .

Our results show that indeed KLR can be adapted to 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 is intuitive since the BR can carry out on-the-fly adaptation in the ZSC setting.

Our results show that the exact graph-structure used, which were similarly studied in , and the type of training regime (synchronous vs sequential) can have a 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.

Related Work

A 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 ; however, as shown in generally optimal SP agents learn highly 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 AI agents that is not captured in the SP problem setting. To address this, introduced the zero-shot coordination (ZSC) setting, where the explicit goal is to develop learning algorithms that allow independently trained agents to collaborate at test time.

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 a small amount of test-time data . These methods build SP policies that are compatible with the test time agents by guiding the learning to the nearest equilibria . 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 . While this presents a 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 to this behavior in the first place, which is the goal of the ZSC 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 one 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 and then applied in the multi-agent context to train more robust policies in two player zero-sum team settings . PBT has also been used to obtain better self-play policies in Hanabi, both in and . In contrast to prior work, we do not use PBT to avoid local optima or train less exploitable agents but instead leverage this framework to implement a KLR and a 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) 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 no symmetries are present. The next method, Ridge Rider (RR) uses the connection between symmetries in an environment and repeated eigenvalues of the Hessian, to 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 . However, LLL requires access to a 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-Belief Learning (OBL) has been shown to provide well-grounded play in hanabi and strong results in the ZSC setting, but requires simulator access to train. We note that KLR doesn’t require simulator access and also matches or even outperforms OBL on various metrics.

Background

2 Deep Multi-Agent Reinforcement Learning

The simplest way to adapt deep Q-learning to the Dec-POMDP setting is through Independent Q-learning (IQL) as proposed by . In IQL, every agent individually estimates the total return and treats other agents as 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 . However, since our work is based on learning best responses, here we only consider IQL.

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 , 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 algorithm or humans. However, many real-world problems require interaction with never before seen AI agents and humans.

This desiderata was formalized as the zero-shot coordination (ZSC) by , in which the goal is to develop algorithms that allow independently trained agents to coordinate at 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 a stepping stone towards human-AI coordination, since it aims to uncover the fundamental principles underlying coordination in complex, partially observable, fully cooperative settings.

Lastly, the ZSC setting addresses some of the shortcomings of the ad-hoc team play 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 cognitive hierarchies, where level $k$ agents are a BR to all preceding levels $\{0,\cdots k-1\}$; we define CH’s as a Poisson distributions over all previously trained levels. We consider k-level reasoning (KLR) to be a hierarchy wehre level $k$ agents are trained as an approximate BR to level $k-1$ agents . Lastly, we propose a new type of hierarchy, SyKLRBR, which is a hybrid of the two, where we train a BR to a Poisson distribution over all levels of a KLR (see appendix A.1 for more details).

For all hierarchies, we start training the first level of the hierarchy $\pi_{1}$ as an approximate BR to a uniform random policy over all legal actions In Hanabi there are some illegal moves, e.g., an agent cannot provide a hint when the given color or rank is not present in the hand of the team mate., $\pi_{0}$. The main idea of this choice is that it prevents the $\pi_{0}$ agent from communicating any information through its actions, beyond the grounded information revealed by the environment (see for more info). It thus forces the $\pi_{1}$ agent to only play based on this grounded information provided, without any conventions.

Furthermore, it is a natural choice for solving zero-shot coordination problems since it makes the least assumptions about a specific policy and certainly does not break any potential symmetries in the environment. Crucially, as is shown in , in principle, the convergence point of CH and KLR should be a deterministic function of $\pi_{0}$ and thus a common-knowledge $\pi_{0}$ should allow for zero-shot coordination between two independently trained agents.

A typical implementation of these training schemas is to train all levels sequentially, one level at a time, until the given level has converged. We also draw inspiration from and their deep cognitive hierarchies framework (DCH) to instead train all levels simultaneously. To do so, we use a 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 are best responding to from the central server.

We implement the sequential training as follows: We halt the training of a policy $\pi_{k}$ at a given level $k$ after 24 hours and start training the next level $\pi_{k+1}$ as a BR to the trained set of policies $\Pi_{k}$, where $\Pi_{k}=\{\pi_{0},\cdots,\pi_{k-1}\}$ for the CH case and $\Pi_{k}=\{\pi_{k-1}\}$ in the KLR case. This is the standard implementation of KLR and CH, as it was unsuccessfully explored in Hanabi by .

For synchronous training we train all levels in parallel under a client-server implementation (see algorithm 1). Here all policies $\{\pi_{1},\cdots,\pi_{n}\}$ are initialized randomly on the server. A client training a given level $k\in\{1,\cdots,n\}$, fetches a policy $\pi_{k}$ and corresponding set of partner policies $\Pi_{k}$ and trains $\pi_{k}$ as an approximate BR to $\Pi_{k}$. Periodically, the client sends a copy of its updated policy $\pi_{k}$, fetches an updated $\Pi_{k}$ and then continues to train $\pi_{k}$. The entire hierarchy is synchronously trained for 24 hours, the same amount as a single level is trained in the sequential case.

Experimental Setup

Hanabi is a cooperative card game that has has been established as a complex benchmark for fully cooperative partially observable multi-agent decision making . In Hanabi, each player can see every player’s hand but their own. As a 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). A “hint” can be 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 are 1s.” A caveat is that each hint costs a scarce information token, which can only be recovered by “discard” a card.

The goal in Hanabi is to complete 5 stacks, one for each of the 5 colors, each stack starting with the “1” and ending with the “5”. At one point per card the maximum score is 25. To add to a stack players “play” cards and cards played out of order cost a life token. Once the deck is exhausted or the team loses all 3 lives (“bombs out”), the game will terminate.

2 Training Details

For a single agent we utilize distributed deep recurrent Q-Networks with prioritized replay experience . 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 , and achieved strong results in the self-play setting. Please see the Appendix A for complete training details.

3 Evaluation

We evaluate our method and baseline in both self-play (SP), zero-shot coordination (ZSC), ad-hoc teamplay and human-AI settings. For zero-shot coordination, we follow the problem definition from 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 a diverse set of unseen, novel partners (ad-hoc team play ), 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, in a case where “Red 1" and “Red 2” have been played and the partner just draw a new “Red 3”, the other agent will hint 3 and then partner will play that card deeming that 3 being a red card based on the convention. This agent is therefore referred to as Rank Bot. The second RL agent is a 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.

We also train a supervised bot (Clone Bot) on human data, as a proxy evaluation for zero-shot human-AI coordination. We used a dataset of $208,974$ games obtained from Board Game Arena (https://en.boardgamearena.com/). During training, we duplicate the games so that there is 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 to reproduce human moves by applying behavioral cloning. The agent is 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.

Results and Discussion

In this section we present the main results and analysis of our work, for sequential training, synchronous training, and SyKLRBR. For each variant/level we present self-play, cross-play, ad-hoc teamplay and human-proxy results. Although we present self-play numbers, the purpose of this paper is not to produce good self-play scores, rather we are optimizing for the ZSC and ad-hoc 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 to 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.

Table 3 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 state-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 (other-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 1 and 2 show the performance of all levels of KLR. A KLR trained sequentially or synchronously is able to achieve good scores with the $k-1$th level, as level $k$ 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-1$th level, indicating that sequential KLRs have large inconsistencies across runs. This also indicates that the sequentially trained hierarchy is overfitting to the exact $k-1$th level. In contrast, the synchronously trained hierarchy keeps its score with the $k-1$th 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 see section 6.4.

2 Ad-hoc Teamplay

Table 3 shows the scores in the ad-hoc teamplay setting i.e. 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 ad-hoc teamplay.

3 Zero-Shot Coordination with Human Proxies

Up to now we have focused on AI agents playing well with each other. Next we 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 3, 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 ’s OP, which when paired with Clone Bot achieved an average score score of $8.55\pm 0.48$.

When synchronously trained, KLR monotonically improves its score with Clone Bot. By level 5 the synchronously trained KLR is able to achieve a score of $15.801\pm 0.26$; the sequentially trained KLR has a significantly lower score. Additionally, the synchronously trained KLR Clone Bot score is comparable to the more algorithmically complex OBL bot, which furthermore requires access to the simulator. Lastly, our new method, SyKLRBR, is able to achieve state-of-the-art 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 a BR we obtain state-of-the-art results.

4 Observations of Training Behaviors

We plot the probability that an agent from $k-1$ will take a given type of action $u$ when playing with an agent from level $k$ in Figure 2. At low levels of the hierarchy (levels 2, 3), the synchronous hierarchy is trained as an 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 a 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 $k-1$th levels, ad-hoc teamplay, and human-proxy coordination.

In table 4 we present the percentage of “bombing out” for the level 5 agent playing with the level 4 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 in 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 it 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 a positive Q-value 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 is a good proxy for being off-distribution, which shows that the synchronously trained KLR agents are more on-distribution during XP testing.

5 Understanding Synchronous Training

At a training step $t$, the synchronous KLR $\pi^{t}_{i}$ is trained towards a BR to $\pi^{t}_{i-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 $\pi^{0}_{i}\;\forall i\in 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 $\pi^{T}_{i}$ (the final policy) will have the lowest entropy. Lastly, the entropy of the average policy across the set $\{\pi_{i-1}^{1},\pi_{i-1}^{2},\cdots,\pi_{i-1}^{T}\}$ 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 $\pi_{i-1}$ has two effects: First of all it increases robustness by exposing $\pi_{i}$ to more states during training and, secondly, more entropic (i.e. random) policies will generally induce less informative posterior (counterfactual) beliefs (a fully random policy is the extreme case, with a completely uninformative posterior). As a consequence, the BR to a set of different snapshots of a policy $\pi^{t}_{i-1}$ is both more robust and less able to extract information from the actions of $\pi_{i-1}$ than the BR to only the final $\pi^{T}_{i-1}$. This forces the policy to rely to a greater extend on grounded information in the game, rather than arbitrary conventions.

Empirically we show this effect by training a belief model on a $\pi^{T}_{1}$ and on a set of snapshots of $\pi^{t}_{1}$ for $t=(100,200,...1000)$. The cross entropy of belief model for the final $\pi^{T}_{1}$ is $1.58\pm 0.01$, while the cross entropy for the set is substantially higher ($1.70\pm 0.01$) (both averaged over 3 seeds).

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-proxy coordination. This is likely because even at higher levels, the majority of the partner agents come from lower levels, as a result the performance is similar to that of KLR level 3. Additionally, computing a best response to a mix of lower level agents makes the hints provided less reliable and disincentivizes the agent to hint.

Conclusion

How to coordinate with independently trained agents is one of the great challenges of multi-agent learning. In this paper we show that a classical method from the behavioral game-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 to specific policies. We have also developed a new method SyKLRBR, which further improves on our synchronous training schema and achieves state-of-the-art results for ad-hoc teamplay performance.

This raises a 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 is 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 and searching for the optimal graph-structure during training is a promising avenue for future work.

Limitations

Although our synchronous training schema does alleviate overfitting in the KLR case, there is still a large gap between cross-play and playing with the $k-1$th level. This indicates that there still exist some unfavorable dynamics in the hierarchy. Similarly, although our work does provide steps towards human-AI 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 a 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-AI 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

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] to [Yes] , [No] , or [N/A] . You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing a 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] The code and the data are proprietary.

Did you include the license to the code and datasets? [N/A]

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.

Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? [Yes]

Did you describe the limitations of your work? [Yes] We discuss limitations in section 8.

Did you discuss any potential negative societal impacts of your work? [Yes] discussed in section 9.

Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

If you are including theoretical results…

Did you state the full set of assumptions of all theoretical results? [N/A]

Did you include complete proofs of all theoretical results? [N/A]

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] we included all information needed to reproduce results in section 4 and appendix A. We will release an open source version of our code and copies of our trained agents later.

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] They are included in appendix A

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]

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

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…

If your work uses existing assets, did you cite the creators? [N/A]

Did you mention the license of the assets? [N/A]

Did you include any new assets either in the supplemental material or as a URL? [N/A]

Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

If you used crowdsourcing or conducted research with human subjects…

Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

Appendix A Experimental Details

In training every agent we use a distributed framework for simulation and training. For simulation, we run 6400 Hanabi environments in parallel and the trajectories are batched together for efficient GPU computation. This is done efficiently as every thread can hold many environments in which many agents interact. Every agent chooses actions based on neural network calls, which are more intensive and done by GPUs. By doing these calls asynchronously it allows a thread to support multiple environments while waiting for prior agents’ actions to be computed. Therefore, by stacking multiple environments into a thread and utilizing multiple threads we are able to maximize GPU utility and generate a massive amount of data on the simulation side. Every environment is considered to be in a permanent simulation loop, where at the end of the environment the entire action observation history, consisting of action, observation, and reward is aggregated together into a trajectory, padded to a length 80, and then added to a centralized replay buffer as done in . We compute the priority of each trajectory as $\xi=0.9\cdot max_{i}\xi_{i}+0.1\cdot\xi$ , where $\xi_{i}$ is the TD error per step. From the training perspective we have a training loop that continuously samples trajectories from the replay buffer and updates the model based on TD error. The simulation policies are updated to be the training policy every $10$ gradient steps. We utilize epsilon exploration for training agent exploration. At the beginning of every simulated game we generate epsilon $\epsilon_{i}$ from the equation $\epsilon_{i}=\alpha^{1+\beta*\frac{i}{N-1}}$, where $\alpha=0.1,\beta=7,N=80$. For our entire training, inference infrastructure we use a machine with 30 CPU cores and 2 GPUs, one GPU for training and one GPU for simulation.

We use the same network architecture as described in . We follow their design choices of utilizing a 3-layer feedforward neural network to encode the entire observation and then using a one-layer feedforward neural network followed by an LSTM to encode only the public observation. We combine these two outputs with element-wise multiplication and use a dueling architecture to get the final Q-values. We also use double DQN as done in . Other relevant hyper-parameters are presented in table 6.

For synchronous hierarchy training, every $50$ gradient steps, each client sends the weights of the policy it is training $\pi_{i}$ to the server and queries the server for the corresponding set of updated policies $\Pi_{i}$ that $\pi_{i}$ is trained to be an approximate best response.

For CH and SyKLRBR, each responds to a Poisson distribution over some set of agents $\{\pi_{0},\pi_{1},\cdots\pi_{k}\}$. Concretely, each of the games played simultaneously has an agent from a set level. We use a Poisson distribution with a PMF of $\frac{\lambda^{k}*e^{-\lambda}}{k!}$. For SyKLRBR we use $\lambda=1$, which means for a given level $j$ and a hierarchy of $i$ levels $k=i-j$ in the PMF. Therefore, a BR to a 5 level KLR has $\sim 37\%$ of the actors from level 5, $\sim 37\%$ from level 4, $\sim 18\%$ from level 3, $\sim 6\%$ from level 2, $\sim 1\%$ from level 1, and $<1\%$ from level 0.

Similarly, for CH we use $\lambda=2$, which is a standard value for CHs as noted by . Thus, a CH at a given level $i$ and partner level $j$, it will have $k=j$ in the Poisson PMF for a given level $j$ (excluding level 0). Therefore, for a 5 level cognitive hierarchy, $\sim 37\%$ of the actors are from level 1, $\sim 37\%$ from level 2, $\sim 20\%$ from level 3, and $\sim 6\%$ are from level 4.

Appendix B Details on Rank Bot and Color Bot

We train two distinct policies to test the ad-hoc teamplay performance of our agents. Both two policies use the same network design as our KLR policies. The first policy is trained with the Other-Play technique where one of the two players always observe the world, i.e. both input observation and output action space, in a randomly permuted color space. The color permutation is sampled once at the beginning of each episode. This method is capable of preventing the agent from learning arbitrary conventions and previously achieved the best zero-shot coordination score in Hanabi. Empirically, policies trained with Other-Play tends to use a rank based convention where it hints about the rank of a playable card to indicate play and partner will often safely play a rank hinted card without knowing the color. Therefore we refer to this policy as Rank Bot. Similarly, we may expect a color based equivalent of the Rank Bot but in practice we find it difficult to learn such policy naturally. We instead use a reward shaping technique where we give extra reward of 0.25 when the agent hints a color. To wash out the artifact of the reward shaping, we first train the agent with reward shaping till convergence and then disable the extra reward and train it for another 24 hours. However, we find that the reward shaping may lead to inconsistent training results across different runs and thus make it hard to reproduce. We use a simple trick of zeroing out the last action field of the observation to stabilize the learning. Note that the last action is a shortcut to learn arbitrary conventions but it is redundant in our setting since the agent with RNN can infer last action from the board. The policy trained this way predominantly uses color based conventions and is referred to as Color Bot.