Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: 
In 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.

While I am impressed with the results in this paper, the writing of this paper needs to be improved.

1. 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.

2. 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.

3. 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.

4. 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.

Overall, 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.

References:


[1] Nekoei et al. 2021. Continuous Coordination As a Realistic Scenario for Lifelong Learning.


Minor comments:

1. Line 19 -> did you mean “multi-player” games such as starcraft?
2. Line 141 -> solving solving

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

Past 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).

This 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.
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.

The 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.

The 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.

But 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.

Another 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.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

Quality: 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. 

Clarity: 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. 

Significance: 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.
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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposed a new method to solve the Hanabi game.
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.



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

After reading the author's response, I have increased the rating from 3 to 5.
limitations_and_societal_impact: 1. They should evaluate their method on more benchmarks, such as MPE, google football and other card games.

2. They should compare their method with recent MARL algorithms, such as MAPPO.
review_title: null

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)