OvercookedV2: Rethinking Overcooked for Zero-Shot Coordination

We thank the time and effort reviewer GLBf has invested in reviewing our paper.

Weaknesses

1. Insufficient evaluations of current ZSC methods on the new environment.

We are currently running additional experiments with the Fictitious Co-Play [1] algorithm and will update the paper accordingly. Furthermore, we will outline how OBL [4] could potentially solve certain layouts, however the algorithm implementation is highly complex and beyond the scope of this work.

2. Some grammatical mistakes, e.g. 'where agents independently trained agents can adopt similar strategies but with arbitrary variations in execution'

We addressed this particular grammatical mistake and are going over the paper to potentially polish the writing.

Questions

1. In the paper, you mentioned that in the Overcooked, ZSC failure can be attributed poor state coverage rather than more sophisticated coordination challenges. In this way, the Overcooked mainly evaluates policy generalization rather than coordination. So I wonder what is your definition of 'coordination'? Because I think generalizing to new partners is almost equal to ZSC.

Here we refer to generalisation in the sense of state-coverage. Our results show that mere state-coverage is sufficient to virtually solve Overcooked, just like it is sufficient to solve the button game [2]. This is in opposition to other games where state coverage itself does not lead to strong coordination, like in Hanabi [3], the cat-dog problem [4], or other toy problems.

2. Could you include more ZSC baselines in the paper. Other-play relies on pre-known symmetries in the environment so it may not work in the new environment. But there are also many ZSC methods that I believe are completely data-driven.

As pointed out above, we are currently running additional experiments with the Fictitious Co-Play [1] algorithm and will update the paper accordingly. We agree that further baselines would be good and are working to implement additional ones.

3. I wonder whether you plan to integrate human-AI coordination into OvercookedV2, since another important advantage of the Overcooked is its support for human-AI interaction.

We have a human-AI interface available, which is described in the Appendix. We will add more details to the description as well as screenshots of what it looks like. We hope to conduct human-AI studies in the future, but this is out of scope now.

[1] Strouse, D. J., et al. "Collaborating with humans without human data." Advances in Neural Information Processing Systems 34 (2021): 14502-14515.

[2] Section 4, OvercookedV2: Rethinking Overcooked for ZSC

[3] Bard, Nolan, et al. "The hanabi challenge: A new frontier for ai research." Artificial Intelligence 280 (2020): 103216.

[4] Hu, Hengyuan, et al. "Off-belief learning." International Conference on Machine Learning. PMLR, 2021.

We thank the reviewer XSHM for the time and effort invested in extensively reviewing our paper.

State robustness is a part of ZSC

The intended solution seems to be to base conventions off of actions that are meaningfully grounded in the environment dynamics, which I would call “grounded communication,” following Hu et al.

This is not what "grounded" means. Grounded communication is communication that contains verifiable information, independent of the speaker's intentions (i.e., grounded actions carry meaning even if taken by a purely random agent). In OvercookedV2, the recipe indicator acts as grounded communication since it communicates the correct recipe as soon as triggered, even if triggered randomly. However, OvercookedV2 purposely features layouts where grounded communication is impossible, such as the layouts Test Time Simple/Wide and Demo Cook Simple/Wide, where agents can only form protocols by moving in specific ways or placing items on a counter, but where those actions do not carry any information a priori.
A way to solve these scenarios is to dynamically form an arbitrary protocol at test time through repetition. As such, OvercookedV2 is about more than just grounded communication.

While this is all technically accurate, this is irrelevant to the ZSC problem, where the whole point is that the agents do not get to coordinate ahead of time on an optimal joint policy. In fact, the Overcooked video game that the benchmark is based on is itself (usually) fully observable, but nonetheless poses significant ZSC challenges, as anyone who has played it can attest.

The bigger point is that, in a fully observable setting, other agents can simply be reactive by observing what the other is doing and choosing the immediate best response. However, the scenario is challenging for humans because they have limited attention; so, although it is fully observable, players cannot attend to all information at all times. Furthermore, the video game introduces stochasticity by randomising recipes (unlike OvercookedV1).

Missing Details

We agree that a discussion of the intended solution for the handcrafted challenges is needed, and we will include those. Moreover, we will outline how OBL could help in each of the scenarios.

Why is OvercookedV2 difficult?

In OvercookedV2, state augmentation doesn’t change the gap on three environments but does substantially reduce the gap on the other three environments. So while state augmentation is certainly less effective for OvercookedV2, it isn’t ineffective.

It is correct that state augmentation still reduces the gap significantly in OvercookedV2, but not nearly as much as seen in OvercookedV1. OvercookedV2 can still be used to create simple environments, and indeed, Demo Cook Simple can be considered simpler than the others. However, it also allows for constructing much more complex and rich layouts.

However, the more important objection is that this doesn’t convince me that OvercookedV2 is limited by the ability to do grounded communication.

Again, not all layouts we propose even contain the option for grounded communication. In layouts such as Test Time Simple/Wide, agents must form a protocol at test time through pattern-matching, as none of their actions carry verifiable information.

It is plausible that state augmentation was enough to address state robustness in the relatively limited OvercookedV1 environments but could not address state robustness in OvercookedV2.

Yes, this is precisely correct. OvercookedV1 mostly depended on the state space (which is independent of the history or partner policy). In contrast, optimal policies in OvercookedV2 depend on belief states, which are determined by the history and partner policy. Therefore, belief state augmentation requires reasoning about potential partners, which is key to addressing coordination challenges.

To address this, the authors could conduct a qualitative analysis of the failures exhibited during cross-play in OvercookedV2.

We agree that a qualitative analysis would be valuable, and we are including a discussion as well as making GIFs of these scenarios available.

The authors could also investigate how the effectiveness of the state augmentation method changes with the complexity of the environment.

This raises the question: how do we measure complexity? We do have SA results for environments without grounded communication, such as Test Time Simple/Wide.

Baselines

We agree that additional baselines would be valuable and are currently running experiments with Fictitious Co-Play. Implementing OBL is a complex effort beyond the scope of this paper. However, we will outline how we expect OBL to perform in the handcrafted coordination scenarios.

Questions on the General Message

Is it accurate to say that the focus of the paper is on grounded communication, rather than coordination more generally? (If not, why not?)

No, this is not accurate, as outlined above (see comments under "State robustness is a part of ZSC").

Can you say more about the intended solutions for each of the handcrafted challenges?

Yes, we agree that there should be a more detailed explanation for each challenge. We will describe the intended solution and also outline how algorithms such as Off-Belief Learning (OBL) could solve certain scenarios.

Do you think humans would solve these environments as intended, if they were given only the rules of the game and some time to familiarize themselves with the environment? (It would be interesting to do a human study to check.)

In the grounded coordination layouts, humans would most likely be able to make meaningful progress. For example, it is intuitive for humans to accept a negative reward of -5 to reveal the recipe. However, using this grounded information to perform even more optimally—by forming a protocol at test time—is significantly more challenging.
Similarly, in the test-time layouts, there is no straightforward way to leverage grounded communication. Here, players would need to interact repeatedly to form a protocol, which humans should be capable of.
Lastly, the demo cook layouts provide solutions that are intuitive for humans. Humans can reason about the meaning of others' actions and generally assume that the other actor is rational, which would lead them to successfully solve these layouts.
However, conducting human studies is beyond the scope of this work. We hope that future work will explore human-AI coordination in OvercookedV2.

Questions About the Handcrafted Layouts

Here are my current guesses about how the layouts work – are any of these incorrect?

These are all correct. We will add clarification to Figure 5.

What is the view radius for each of the environments? This matters to interpret the environments – for example, a view radius of 1 in Demo Cook would imply that the agents must communicate via counter placements or pot interactions, whereas a view radius of 2 or more would allow the agents to communicate via their movements as well.

The view radius for all handcrafted coordination challenges in the paper is 2. This is also stated in Appendix C.1. Communication through movement is possible in some layouts, such as the Grounded Coordination Ring.

(Incidentally, I would recommend the authors also consider communication through movement as a form of grounded communication – this has been studied under the term “legibility”; see, e.g., Dragan et al., 2013.)

While movement can carry information (e.g., by moving toward a goal to indicate the intention of reaching it), it only conveys information if we assume the moving agent is approximately rational. A random agent performing the same movement would not communicate any bits of information.

Note that our Demo Cook layouts specifically serve to study the emergence of meaning through actions directed at specific goals, such as depositing a onion item in the pot to communicate that the three onion recipe is the correct one.

(Ideally the paper would also specify other hyperparameters such as the sizes of various positive and negative rewards, but they are not as crucial.)

The sizes of positive and negative rewards (+/- 20) are stated in Appendix B.2.

Other Notes

Please add some more clarification about the Button game somewhere (appendix is fine).

We will rewrite the explanation and include more details to make this clearer.

Thanks for agreeing to add baselines and more details about the layouts. I've increased my score to a 5.

I still do not understand what your definition of zero-shot coordination is, if you think that "mere state robustness" does not count as a solution to ZSC. And it's not just me, Reviewer GLBf also has this confusion, saying "So I wonder what is your definition of 'coordination'? Because I think generalizing to new partners is almost equal to ZSC."

One argument I am more sympathetic to is: the original Overcooked benchmark is almost saturated using a simple state robustness method. So, it is time to develop a harder benchmark. In this story, the state robustness algorithm is simply one algorithm for achieving ZSC, that works in the original Overcooked setting, but doesn't work for Overcookedv2.

The bigger point is that, in a fully observable setting, other agents can simply be reactive by observing what the other is doing and choosing the immediate best response.

I'm not sure exactly what you are trying to say here, but I think it is probably untrue. There is no unique "best response" that is independent of the other agent, even in a fully observable setting. This was the main point in the original Overcooked paper (Carroll et al) -- Figure 1 demonstrates how incorrect beliefs about the partner agent's future actions can lead to bad outcomes.

While movement can carry information (e.g., by moving toward a goal to indicate the intention of reaching it), it only conveys information if we assume the moving agent is approximately rational. A random agent performing the same movement would not communicate any bits of information.

Yes, of course this depends on some minimal rationality assumptions, but this is also true of test-time protocol formation more generally. A random agent doesn't communicate information through its movement -- but you also can't form any test-time protocol with a random agent.

We thank reviewer XSHM for their comments.

I still do not understand what your definition of zero-shot coordination is, if you think that "mere state robustness" does not count as a solution to ZSC. And it's not just me, Reviewer GLBf also has this confusion, saying "So I wonder what is your definition of 'coordination'? Because I think generalizing to new partners is almost equal to ZSC."

We follow the ZSC definition by Hu et al. The goal of the ZSC problem is to develop algorithms that enable agents to be trained independently while coordinating effectively at test time. There are multiple aspects that make ZSC challenging. State-coverage is one of them; however, it is not the only factor that makes coordination difficult. ZSC may also require learning grounded communication strategies or test-time protocols. Thus, while state-coverage contributes to the difficulty of the ZSC problem, solving state-coverage alone is not equivalent to solving ZSC.

One argument I am more sympathetic to is: the original Overcooked benchmark is almost saturated using a simple state robustness method. So, it is time to develop a harder benchmark. In this story, the state robustness algorithm is simply one algorithm for achieving ZSC, that works in the original Overcooked setting, but doesn't work for Overcookedv2.

This is precisely the point. In Overcooked, we show that merely achieving state-coverage is sufficient to perform well in a ZSC setting. Consequently, it is not a good coordination benchmark, as state coverage represents only one aspect of ZSC. To address this limitation, we present a more challenging benchmark, OvercookedV2, which provides richer coordination challenges. While state-coverage remains part of the challenge in OvercookedV2, it is no longer sufficient to solve the benchmark. OvercookedV2 allows us to create scenarios that cannot be solved through state coverage alone. For instance, agents may need to rely on grounded communication or test-time protocol formation. This makes OvercookedV2 a much more comprehensive benchmark for evaluating ZSC, enabling the development of more complex and realistic scenarios. We will make this point clearer in the paper.

I'm not sure exactly what you are trying to say here, but I think it is probably untrue. There is no unique "best response" that is independent of the other agent, even in a fully observable setting. This was the main point in the original Overcooked paper (Carroll et al) -- Figure 1 demonstrates how incorrect beliefs about the partner agent's future actions can lead to bad outcomes.

The reviewer is correct; our initial statement was misstated and as a result inaccurate. What we meant is this:

In fully observable settings, each agent can independently compute all optimal joint-policies conditioned exclusively on the current state rather than on the action-observation history. It can then enact its part of one of the optimal joint-policies. If both agents do so, they will only fail to coordinate if they happen to choose joint-policies which are immediately incompatible. This can indeed happen, but we argue that it does so rarely in Overcooked, given our results in Section 5 which show that state augmentation greatly boosts XP even though we use non-recurrent policies.

A follow-up [1] to Overcooked by some of the same authors echoes our claim, stating the following in Section 7:

"there is non-trivial strategically relevant information in Overcooked only in situations in which simultaneous decisions between incompatible optimal joint plans must be made. Given that such situations are rare, this provides a theoretical explanation as to why relatively good coordination with humans is achievable in this domain without any human data (Strouse et al., 2021). Our framework also explains why the introduction of simultaneous decisions (most easily through partial observability) can lead to benchmarks that are specifically more challenging for coordination, such as Hanabi"

We hope this clarifies any confusion.

While movement can carry information (e.g., by moving toward a goal to indicate the intention of reaching it), it only conveys information if we assume the moving agent is approximately rational. A random agent performing the same movement would not communicate any bits of information. Yes, of course this depends on some minimal rationality assumptions, but this is also true of test-time protocol formation more generally. A random agent doesn't communicate information through its movement -- but you also can't form any test-time protocol with a random agent.

This is correct; however, this is therefore not considered grounded communication. As stated previously, the test-time protocol formation layouts cannot be solved solely by relying on grounded communication. OvercookedV2 presents coordination challenges that include, but are not limited to, grounded communication.

[1] Lauffer et al., 2023. https://arxiv.org/pdf/2306.09309

We thank the time and effort reviewer Fs42 has invested in reviewing our paper.

Weaknesses

It would've been nice for all evaluations of the state-augmented agents on the default layouts to see how well they play with humans. If state coverage is really the key to removing the SP-XP gap, then we should see performance with humans be higher than conventional SP method playing with humans. Otherwise, it is not clear that state-coverage alone is getting at the ZSC capabilities methods like population-based training tries to learn.

We remind that ZSC is a formal setting introduced in Hu et al. that requires constructing an algorithm that allows agents to be trained independently yet coordinate effectively at test time. It is a prerequisite to human-AI coordination since it is the lowest bar to cross, but not necessarily sufficient. Regardless of whether SA agents can play with humans or not in Overcooked, that environment does not assess human-AI coordination or ZSC in stochastic partially observable settings. OvercookedV2 provides the ability to evaluate that, and we show a gap in ZSC, which necessarily implies a gap in human-AI coordination as well.

A similarly insightful analysis would be comparing how well the state-augmented agents on the default layouts play with other algorithms (SP, MEP, E3T, etc.) that are SOTA for ZSC on overcooked. If state-augmented agents can perform at SOTA levels or close to that, it would be more compelling evidence that the issue with generalization on the original problems was just state coverage.

The aforementioned algorithms may themselves not be robust to unseen states. Low XP scores might therefore come from those other algorithms, rather than from the SA agents. For an extreme example of this see ADVERSITY [2].

For the new environments, it would be compelling to see baselines such as MEP or E3T, which are some of the most successful algorithms for ZSC in Overcooked (the former being population based, the latter being self-play based). MEP and other population-based methods in particular try to simulate strategy diversity (by generating diversity in trajectories of states visited), so if these methods fail on your new benchmark it would be especially compelling as a new challenge for the MARL community to try to tackle.

We agree that additional baselines are good and we are currently running additional experiments with the Fictitious Co-Play [3] algorithm and will update the paper accordingly. Furthermore, we will outline how OBL [4] could potentially solve certain layouts, however the algorithm implementation is highly complex and beyond the scope of this work.

Questions

The "environment creation via ASCII text" was listed as a contribution. How does this differ from the same functionality the original JaxMARL codebase already included beyond the additional object predicates from your new layout?

The interface is similar to the one in the original JaxMARL codebase, however it is modified to allow for the additional objects introduced in OvercookedV2. Moreover, the interface allows additional parameters such as possible recipes.

Similarly, you listed there was an interactive interface for humans to play on the new environment. JaxMARL included this for Overcooked as well, so how is your interface different? If it's easy to benchmark human-AI coordination would you be able to show preliminary results on the new benchmark?

We modified the interface to allow players to collaborate with trained policies, this was not possible previously. Moreover, the interface is extended to include all new items introduced in OvercookedV2. If partial observability is enabled, it is possible to also restrict the view radius of the player to simulate what the agent would see. This enables future human-AI experiments, however this is beyond the scope of this paper.

[1] Hu, Hengyuan, et al. "“other-play” for zero-shot coordination." International Conference on Machine Learning. PMLR, 2020.
[2] Cui, Brandon, et al. "Adversarial diversity in hanabi." The Eleventh International Conference on Learning Representations. 2023.
[3] Strouse, D. J., et al. "Collaborating with humans without human data." Advances in Neural Information Processing Systems 34 (2021): 14502-14515.
[4] Hu, Hengyuan, et al. "Off-belief learning." International Conference on Machine Learning. PMLR, 2021.