RACCOON: Regret-based Adaptive Curricula for Cooperation

We thank the reviewer for their insightful feedback. We address the raised weaknesses in turn below.

Regret estimate: We use the difference between the maximum return ever achieved on a (partner, task) pair and the current return as our regret estimate. We do also discuss alternative methods for estimating regret in Appendix A. The simplicity of our metric is one of its strengths; if regret on (partner, task) is defined as A-B, where A is the maximum achievable expected return on (partner, task), then estimating A more directly would require, for example, training a single best response to each (partner, task) to estimate the maximum achievable returns with that (partner, task). For our approach, we don’t need to incur such costs, instead only needing to store metrics we already have from the run so far. In addition, we posit that there may be an advantage to using the maximum return achieved so far, rather than the maximum return ever achievable, since this scales to the student’s current ability.

Low quality figures: We thank the reviewer for pointing this out. We find this somewhat surprising, as reviews on the whole seem to have found the paper clear and well-presented. We ask which of the figures, and which parts of the text, the reviewer found unclear, so that we can directly provide clarifications and strengthen the written communication of the paper.

Scaling to more agents: We acknowledge that the paper is currently limited to the two-player setting, which has been studied throughout much of the ad-hoc coordination literature [1, 2, 3]. The two-agent setting has different, but not necessarily less interesting dynamics than the > 2-player setting, as when there is only one partner with which the agent can coordinate, they have more potential to shape the behaviour of the other agent and influence equilibrium selection. With greater numbers of agents, the coordination problem for an individual agent increasingly reduces to "fitting in" with the group. We have added this point to the paragraph on “Environment” in Section 4 of the manuscript (coloured in red). This being said, there is certainly scope for RACCOON to be scaled to more partners. How this is done depends on the setting and whether partners are interchangeable; one option which is less computationally costly than simply increasing the number of dimensions of the buffer is to use pre-trained teams of partners, and use RACCOON to sample teams and tasks.

Answering Questions:

1. The jumps in training returns in Figure 3 likely arise from the student acquiring new skills and learning to cooperate with new partners.

2. We apologise for unclear wording; all the plots in Figure 3 show the training return averaged across all partners, and we merely intend to point out that this is the reason for the returns for Forced Coordination and Counter Circuit being so low (since the student gets 0 return with most partners on these tasks). We have amended the wording in the manuscript to improve clarity.

3. Section 4 describes how partners are generated. Partners of different skill levels are obtained using checkpoints of policies from the beginning, middle and end of training, following prior work [1]. More specifically, partners are trained in self-play until their returns converge. These final policies are the “high-skilled” partners. The “medium-skilled” partners use the checkpoint which achieves half of the final return. The “low-skilled” partners use the checkpoint at initialisation.

4. We choose to use Counter Circuit to analyse effects of scaling the number of training partners because it is challenging enough that we expect partners to exhibit more diverse policies than for an easier layout such as Cramped Room. In particular, training a student on a single, easy layout such as Cramped Room is almost trivial, and the task is too easy to present additional challenges as the student has to deal with additional training partners.

5. See “scaling to more agents” above.

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

[2] Li, Yang, et al. "Cooperative Open-ended Learning Framework for Zero-Shot Coordination." The 40th International Conference on Machine Learning. 2023.

[3] Wang, Rose, et al. "Too many cooks: Coordinating multi-agent collaboration through inverse planning." The 9th International Conference on Autonomous Agents and Multi-Agent Systems. 2020.

We thank the reviewer for their detailed feedback, and address the weaknesses raised below.

Two-agent environment: We acknowledge that the paper is currently limited to the two-player setting, which is studied throughout much of the ad-hoc teamwork literature through environments like Overcooked and Hanabi [1, 3, 4, 5, 6]. The two-agent setting has different, but not necessarily less interesting, dynamics than the setting with > 2 players, as when there is only one partner with whom the agent can coordinate, they have more potential to shape the behaviour of the other agent and influence equilibrium selection. With greater numbers of agents, the coordination problem for an individual agent increasingly reduces to "fitting in" with the group. However, RACCOON could be scaled to multiple partners by, for example, adding extra dimensions to the buffer, or by using teams of partners in place of individual partners in the algorithm.

Complexity of Overcooked: Overcooked has been used as a benchmark throughout much of the ad-hoc teamwork literature precisely because it isolates the effective partial observability induced by not knowing a partner's policy or higher-level convention [1]. The coordination biases of a previously unseen partner are unobserved and can only be discovered through an interaction history. Introducing environment partial observability, as in the Hanabi challenge, does introduce further challenges worthy of research, however we do not focus on these in this paper.

Motivation for Overcooked: We thank the reviewer for pointing out that we should include an explicit motivation for the experimental setting in the paper to improve clarity. We have added this to the “Environment” paragraph in Section 4 (coloured red). We appreciate that this will strengthen the paper and that it ties in with the other concerns raised.

Answering Questions:

1. Use of regret in RL: Agents are still learning through environment interactions, and the statistics used to estimate regret are derived entirely from these interactions. As noted in [7, 8], curricula in reinforcement learning are intended to prioritise future experiences based on regularly updated regret statistics in order to improve sample efficiency. This has been shown to be immensely valuable in a field that consistently suffers from sample inefficiency.

2. Extension to partial observability. We acknowledge that the partially observable setting comes with its own host of challenges, making it a direction worthy of a distinct investigation. This is because of the potential for “irreducible regret”, which can arise when an agent cannot simultaneously be optimal with two distinct partners under partial observability, because they rely on different conventions [2]. This is beyond the scope of our paper but we acknowledge it as a fruitful direction for future research.

[1] Sarkar, Bidipta, Andy Shih, and Dorsa Sadigh. "Diverse conventions for human-AI collaboration." Advances in Neural Information Processing Systems 36 (2024).

[2] Beukman, Michael, et al. "Refining Minimax Regret for Unsupervised Environment Design." Forty-first International Conference on Machine Learning.

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

[4] Zhao, Rui, et al. "Maximum entropy population-based training for zero-shot human-ai coordination." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 5. 2023.

[5] Charakorn, Rujikorn, Poramate Manoonpong, and Nat Dilokthanakul. "Generating diverse cooperative agents by learning incompatible policies." The Eleventh International Conference on Learning Representations. 2023.

[6] Cui, Brandon, et al. "Adversarial diversity in hanabi." The Eleventh International Conference on Learning Representations. 2023.

[7] Jiang, Minqi, Edward Grefenstette, Tim Rocktäschel. "Prioritized level replay." The Thirty-Eighth International Conference on Machine Learning. 2021.

[8] Dennis, Michael, et al. "Emergenet complexity and zero-shot transfer via unsupervised environment design." The Thirty-Fourth Conference on Neural Information Processing Systems. 2020.

We thank the reviewer for their feedback and are pleased they found our idea interesting and original, and were compelled by our results. We also appreciate the reviewer’s feedback on the clarity of our presentation - we are pleased that the algorithm was easy to follow, and it is useful to know that the switch between multi-task and single-task settings can be confusing at first glance. We have taken on the reviewer’s feedback on the presentation of our results in Section 5, and the corresponding modifications can be found in the manuscript (coloured in red). We address additional feedback below.

Showing states where agents fail: We agree that it would be insightful to include qualitative analysis of agent failures by including visualisations of the states in which the behaviours of DR and RACCOON agents fail - however, at present we do not have the means to easily obtain these visualisations in time for the discussion period. We will endeavour to look into doing so for a camera-ready copy, but ask if there are any intermediate results that might provide qualitative insights of interest to the reviewer.

Why agents do better in the single-task setting for the same layout. We attribute this to there being a trade-off in performance across all tasks for a fixed training budget. Since each task requires different skills to complete, it is more challenging for an agent to perform well in all tasks than just one of them. Therefore, the returns for an agent trained on a single task tend to be higher than returns on the same task when it’s one of multiple distinct tasks being trained on.

We thank the reviewer for their feedback, and appreciate that they found the paper well-written. We address the weaknesses outlined below.

Multi-task experimental set up: We use the five Overcooked layouts because they present a diverse range of challenges - in particular they are designed to provide different cooperative challenges (such as division of labour and avoiding collisions), so performing well on all of them is highly non-trivial. In addition, using these five fixed tasks makes it easier to obtain partners of particular, known skill levels on each task, making the performance of the algorithm more interpretable. However, beyond using this set-up to demonstrate the effectiveness of RACCOON, unsupervised environment design methods such as RACCOON are indeed particularly well-suited to procedurally generated environment spaces, so a fruitful step for follow-up work would indeed be to apply RACCOON with a more open-ended environment generator, such as [3].

Partner generation: While a range of partner generation methods exist, fictitious co-play [1], the method we follow, has been shown to be effective for diverse partner generation despite its simplicity [2]. In addition, an advantage of using a regret-based autocurriculum is its ability to automatically discover the partners with whom it’s challenging to cooperate, which will implicitly reflect partner diversity without us needing to know in advance which conventions each partner follows.

Answering Questions:

1. Sampling tasks after partners: We design RACCOON to be applicable in the most general cases where we may not have access to privileged knowledge about which partners are best at which task (and it might be difficult to know this a priori); the power of RACCOON is that it can automatically discover which tasks are most useful to train on with each partner. Therefore, we didn’t restrict the algorithm to sample only (partner, task) pairs where the partner was explicitly trained on the task, instead allowing the algorithm to discover high-regret (partner, task) pairs for itself. The decision to sample a partner first and then a task given that partner, rather than vice versa, is because the size of the population of partners is fixed, whereas in procedurally generated environments there may be arbitrarily many tasks, and it would be infeasible to maintain a buffer for every possible task.

2. Negative scores: While it is possible for scores to dip below zero, doing so would immediately update the stored “maximum return achieved” and therefore restore the scores to non-negative in the next iteration.

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

[2] Charakorn, Rujikorn, Poramate Manoonpong, and Nat Dilokthanakul. "Investigating partner diversification methods in cooperative multi-agent deep reinforcement learning." Neural Information Processing: 27th International Conference, ICONIP 2020, Bangkok, Thailand, November 18–22, 2020, Proceedings, Part V 27. Springer International Publishing, 2020.

[3] Ruhdorfer, Constantin, et al. "The Overcooked Generalisation Challenge." CoRR (2024).

I would like to thank the authors for replying to my questions, particularly on the motivation behind the design and experimental setup of the proposed method. However, I am still not convinced that the proposed method can effectively generalize to the multi-task setup, considering the low performance of the 3 harder layouts. Hence I will maintain my current score.