acceptodds
Under review as a conference paper at ICLR 2027

Promises as a Common Language for Zero-Shot Coordination

Abstract

Zero-shot coordination (ZSC) requires agents to cooperate with unseen partners without prior joint training. Existing approaches typically seek behavioral diversity by varying training partners, environments, or action distributions, but such diversity does not necessarily yield behaviors that are useful for coordination. To address this limitation, we propose *Promise-based Partner Coordination* (PPC), which structures partner diversity through *promises*: explicit commitments to coordination-relevant behaviors. Inspired by Promise Theory, PPC leverages an LLM to generate executable promises from task descriptions and iteratively refine them through interaction-based feedback, enabling diverse coordination patterns without manually designing partner behaviors. We train a population of *Promisers* to follow different promises and a *Promisee* to coordinate with them based on their inferred trustworthiness. Across diverse ZSC environments, PPC substantially improves both self-play and cross-play performance over existing approaches and generalizes effectively to human partners. These results demonstrate the effectiveness of promises as a common language for coordination with unfamiliar partners.

Primary area:
reinforcement learning
Keywords:
Zero-Shot Coordination, Multi-Agent Reinforcement Learning, Human–AI Coordination, Promises, Large Language Models

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_2JntOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Promise-based Partner Coordination (PPC), a training framework for zero-shot coordination with unfamiliar AI and human partners. An LLM generates and refines executable promises that specify when coordination rules apply and which actions satisfy them. Different promise combinations and randomized enforcement shape a population of training partners. A separate, unconstrained Promisee learns to respond to these partners using a trust estimator trained to infer enforcement probabilities from local interaction history. Evaluation covers Overcooked-v1, Overcooked-v2, and Hanabi, including self-play, cross-play between seeds of the same method, external AI partners, and a 40-participant human study. PPC reports improvements over the tested baselines, with additional support from common-partner BR-Prox evaluation on Overcooked-v1 and human collaboration. Evaluation uses frozen policies without LLM calls or action masking of the Promisee.

Critical strengths
  1. Promises make training-partner behaviors inspectable, with recognizable conventions such as yielding and handoffs. Randomized enforcement introduces variation while leaving the responding agent unconstrained.

  2. Forty participants evaluate all methods across both Overcooked variants and two-player Hanabi. Randomized presentation, concealed method identities, and paired participant-level analysis strengthen the comparison. The reported gains provide practical evidence of transfer to human partners without using human trajectories for training.

  3. The common held-out partner pool provides complementary evidence beyond same-method cross-play. Figure 19 reports aggregate BR-Prox of 0.866 versus 0.769 for the strongest baseline on Overcooked-v1.

Critical weaknesses
  1. Table 1 uses method-specific partner distributions, so its SP/XP ranking combines task competence and within-method compatibility with partner adaptation. Shared Promiser populations across PPC seeds further limit the interpretation of cross-seed XP (Appendix G.5). Figures 18–19 provide more direct evidence of external-partner generalization, but appear only in the appendix: BR-Prox covers Overcooked-v1, and inter-algorithm cross-play covers one setting per environment. The main comparison should distinguish within-method compatibility from performance with common test partners.

  2. The framework depends on domain semantics and environment-specific integration. Although summaries and promises are LLM-generated, generation requires detailed task dynamics, state/observation/action definitions, role observability, and implementation interfaces (Table 5). Each layout or player-count condition receives its own promise set (Table 7). The experiments demonstrate a reusable workflow for structured games, but the effort and manual intervention needed to integrate a new environment are not quantified. Appendix A acknowledges the focus on recurrent, locally identifiable decisions; broader portability remains uncertain.

  3. Component ablations support the combined design, but do not isolate promise constraints from useful semantic priors and training choices. SemDiv already generates semantic behaviors and reward programs with feedback [1], and CoMeDi targets strategic diversity [2]; neither is evaluated. A controlled reward-versus-constraint comparison with matched semantic information would clarify the contribution. PPC also receives hyperparameter search and different Overcooked optimizer settings without comparable baseline tuning.

[1] Li et al. LLM-Assisted Semantically Diverse Teammate Generation for Efficient Multi-agent Coordination. ICML, 2025. Paper.

[2] Sarkar et al. Diverse Conventions for Human-AI Collaboration. NeurIPS, 2023. Paper.

Questions for authors
  1. Could Figures 18–19 be summarized in the main text, with Table 1 explicitly framed as task competence and within-method compatibility? Are broader common-partner AI evaluations available for Overcooked-v2 and Hanabi beyond the representative settings in Figure 18?

  2. What inputs, environment-specific interfaces, and manual interventions are required for a new environment? How variable are results across independently generated promise sets?

  3. Can one existing layout compare reward-based partner generation with promise constraints under matched semantic specifications, population size, learner, tuning budget, and evaluation information?

  4. What signal is supplied in the “true trust” ablations for unconstrained Promisee partners, and does it represent enforcement or fulfillment?

4 comments

We thank the reviewer for the questions on generalization, promise generation, controlled comparisons, and true trust. Below, we respond to each point.


W1/Q1 (Generalization to Unseen Partners)

Table 1 measures task competence through SP and compatibility between independently trained policies of the same method through XP. It does not, by itself, establish generalization to external partners. We now make this distinction explicit in the main text and present held-out XP and BR-Prox as separate evaluations in Figure 4 and Table 2. We also extended held-out XP to all Overcooked layouts and Hanabi team sizes in both ego and partner roles, with full results in Figures 19–21.

Table R.1. Held-out XP, ego / partner. Approximate averages exclude diagonals and equally weight other methods and all layouts/team sizes.

MethodOvercooked-v1Overcooked-v2Hanabi (2-5 players)
IPPO88.8 / 87.69.1 / -11.96.7 / 8.4
OP84.5 / 90.51.7 / -0.26.6 / 8.8
FCP124.3 / 127.620.8 / 16.211.0 / 10.3
MEP109.8 / 116.2-3.3 / 12.97.9 / 6.8
E3T111.6 / 107.1-1.7 / -8.07.9 / 9.7
HSP118.8 / 110.1-6.6 / 10.86.4 / 3.7
GAMMA110.8 / 97.1-5.8 / 13.66.6 / 4.2
CoMeDi133.2 / 128.911.4 / 6.69.7 / 10.0
SemDiv79.9 / 95.317.1 / 13.08.9 / 8.7
PPC141.2 / 142.343.6 / 33.110.2 / 11.3

PPC leads both roles in Overcooked-v1/v2 and the partner role in Hanabi, while FCP leads as Hanabi ego. For a common-pool test, all egos face the same unseen biased partners in v1; PPC obtains the highest BR-Prox (Table 2). The pool is uninformative in v2/Hanabi, where the full held-out matrices provide broader coverage. These results support coordination with partners beyond PPC's training population.


W2/Q2 (Automatic Promise Generation and Variability)

Applying PPC to a new environment requires a task specification and an interface through which promises can be checked and executed. These inputs include dynamics, state, observation, and action definitions, and role information, as summarized in Table 7. Given these specifications, the same pipeline generates state summaries and executable promises, validates them, and refines them using interaction feedback without manual promise design or editing. We clarify this procedure in Appendices C.1–C.3.

To assess variation across generations by the same LLM, we independently repeated promise generation, refinement, Promiser learning, and ego learning, then cross-played the resulting egos.

Table R.2. Shared versus independent construction (Table 15). SP/XP: mean ±\pm SD over layout means. Time counts one shared or ten independent constructions plus the same ego-training term.

EnvironmentConstructionSPXPTime (min)
Overcooked-v1Shared291.25±36.14277.75±42.8090.75
Overcooked-v1Independent290.00±37.02268.45±46.91558.75
Overcooked-v2Shared173.67±14.42140.50±19.1793.33
Overcooked-v2Independent168.73±14.03144.37±23.62510.33

Although promise definitions and action sets vary across runs, XP remains comparable to the shared setup. This supports coordination without identical promises or a shared Promiser population, while explaining why the default shares construction to save cost (Appendix F.4).


W3/Q3 (Baseline Comparisons and Promise Ablations)

To distinguish the contribution of semantic task knowledge from that of promise constraints, we added two types of evidence: comparisons with SemDiv [1] and CoMeDi [2] across all benchmarks, and a controlled reward-based variant using PPC's own promises. SemDiv uses the same LLM, recurrent backbone, five generated partners, and per-ego budget as PPC, but retains specialized egos and an evaluation-time LLM selector. PPC instead adapts one Promisee through inferred trust, without evaluation-time LLM calls, as described in Table 11.

Table R.3. Additional baselines (Table 1). Cells: SP / XP, mean ±\pm SD across seeds; v1/v2 denote Overcooked-v1/v2.

EnvironmentLayoutIPPOCoMeDiSemDivPPC
Overcooked-v1Counter Circuit158.00±27.00 / 32.00±12.00165.00±26.90 / 128.90±32.6039.90±48.00 / 42.10±36.90260.00±22.00 / 231.00±29.00
Coordination Ring287.00±23.00 / 41.00±11.00311.20±19.50 / 231.50±80.2098.80±10.00 / 87.60±17.20325.00±9.00 / 311.00±9.00
Cramped Room253.00±9.00 / 187.00±36.00243.40±8.40 / 227.40±33.70192.40±15.10 / 183.00±12.80260.00±4.00 / 252.00±7.00
Forced Coordination200.00±29.00 / 10.00±11.00194.60±8.40 / 188.00±10.00166.90±15.20 / 149.50±28.80320.00±12.00 / 317.00±28.00
Overcooked-v2Grounded Coordination Simple138.00±17.00 / -60.00±39.0050.00±79.40 / -5.20±80.50114.40±48.70 / 110.50±46.60156.00±23.00 / 117.00±14.00
Grounded Coordination Ring162.00±9.00 / -18.00±29.00113.20±22.80 / 67.90±28.6042.00±18.70 / 44.80±10.50167.00±12.00 / 120.00±58.00
Test Time Simple149.00±32.00 / -69.00±46.008.00±10.60 / -0.10±14.3060.90±58.00 / 46.40±41.50165.00±18.00 / 140.00±13.00
Test Time Wide178.00±30.00 / -51.00±12.00126.60±32.50 / 78.90±35.6071.80±38.70 / 67.90±32.00186.00±9.00 / 167.00±25.00
Demo Cook Simple142.00±35.00 / 12.00±17.00132.80±58.60 / 82.30±47.40101.20±72.60 / 98.60±68.20173.00±55.00 / 150.00±59.00
Demo Cook Wide152.00±41.00 / 9.00±6.00122.00±53.60 / 19.20±55.4079.30±28.00 / 72.80±25.50195.00±12.00 / 149.00±34.00
Hanabi2 players23.50±0.50 / 7.30±4.4014.57±1.21 / 14.32±0.7713.37±0.41 / 13.47±0.2623.00±0.20 / 22.90±0.30
3 players23.00±0.20 / 8.60±1.5016.20±0.71 / 15.84±0.7612.61±0.46 / 12.52±0.3422.70±1.00 / 21.90±1.20
4 players22.50±0.60 / 4.20±1.9013.75±1.70 / 13.54±0.8914.62±1.17 / 14.67±0.7522.70±0.50 / 21.10±0.40
5 players21.70±0.90 / 6.00±2.1015.05±2.27 / 14.82±1.6013.24±1.14 / 13.11±0.9322.00±0.30 / 20.50±0.60

PPC achieves higher XP than both added baselines in every setting. To isolate the effect of action constraints under the same semantics, Reward-based PPC keeps the promises, five Promisers, recurrent ego learner, sampled gates, and inferred-trust evaluation, but replaces masks with Promiser-only rewards of +0.1+0.1 for fulfillment and −0.1-0.1 for violation. Each Promiser and ego receives 30M training steps. Random masking provides a complementary control without meaningful promises.

Table R.4. Promise controls (Tables 6 and 20). Mean ±\pm SD across layout means.

EnvironmentEval.FCPRandom maskingReward-based PPCPPC
Overcooked-v1SP153.50±52.28171.93±50.17234.11±65.20291.25±36.14
Overcooked-v1XP160.00±50.77184.45±42.71203.30±63.95277.75±42.80
Overcooked-v2SP66.67±37.0838.53±25.18127.16±52.43173.67±14.42
Overcooked-v2XP50.50±20.8639.28±25.3062.33±38.04140.50±19.17

PPC outperforms Reward-based PPC and random masking in both Overcooked versions. The former supports the tested action-constraint implementation over intrinsic rewards with matched promises; the latter shows that arbitrary restrictions alone are insufficient. Thus both meaningful promises and constraint-based enforcement contribute to the results (Appendix G.3.1).

Section 5.1 clarifies baseline tuning and PPC's SP-selected benchmark-wide configuration; the promise controls use matched Promiser and ego training budgets.

References

[1] Li et al., "LLM-Assisted Semantically Diverse Teammate Generation for Efficient Multi-agent Coordination", ICML 2025.

[2] Sarkar et al., "Diverse Conventions for Human-AI Collaboration", NeurIPS 2023.


Q4 (True-Trust Ablation Protocol)

The true-trust ablation does not assume that every partner has a known enforcement vector. During training with Promisers, the variant uses their sampled enforcement probabilities, setting ρ=η\boldsymbol{\rho}=\boldsymbol{\eta}. Unconstrained Promisees have no corresponding enforcement target, so the existing estimator infers trust from their behavior relative to predefined promise categories, including during self-play. SP and XP evaluation use inferred trust for all partners, as shown in Figures 9 and 29. Thus, the ablation tests access to oracle enforcement information during Promiser-partner training, not at evaluation, and does not treat observed fulfillment as enforcement.


Once again, we thank the reviewer for the careful review. We hope these additions clarify PPC's design and generalization.

I’ve raised my rating to 3. I find the Overcooked-v1 results convincing: PPC leads on all four layouts when every method faces the same unseen partners. The expanded cross-play results give me more confidence that PPC can coordinate beyond its training population. I also appreciate the new controls showing that cross-play remains strong with independently trained Promisers and that action constraints outperform reward-based enforcement using the same promises.

We sincerely thank the reviewer for their positive reassessment and encouraging feedback. We are pleased that the additional experiments have addressed the main concerns and provided stronger evidence supporting our proposed approach. We greatly appreciate your thoughtful feedback and consideration throughout the discussion.

Reviewer_MsD9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

PPC uses “promises” to structure partner diversity for zero-shot coordination. Each promise is an executable rule specifying when it applies and which actions are allowed. An LLM writes the rules from the task description, then revises them using feedback from training rollouts. Five Promisers learn under different combinations of enforced promises. A Promisee trains against this population and conditions its policy on estimated partner compliance. PPC reports the highest self-play and same-method cross-play return on ten Overcooked layouts, and the highest cross-play return on all four Hanabi team sizes. The paper also evaluates play with humans and partners trained by other methods.

Critical strengths

S1. Promises make partner diversity inspectable. The rules specify both an activation condition and an allowed-action set (Def. 1). The refinement loop uses activation, value gap, and Promise Mode Separation rather than an unrestricted request for better rules. The paper provides examples and categories of the final promises, so a reader can see what kinds of behavior are being encouraged.

S2. The paper goes beyond same-method cross-play. In the 40-participant study, PPC had the highest human–AI return in all three environments. It also leads to a comparison with held-out hidden-utility partners on Overcooked-v1. These are useful tests of coordination with unfamiliar partners.

Critical weaknesses

W1. Table 1 tests new policy seeds within a shared promise setup. Cross-play pairs independently trained Promisee seeds, so the partner policy is unseen. Within each condition, though, the seeds use the same generated promise set and Promiser population. The large gaps in Table 1, therefore, do not show how PPC handles independently generated conventions. The inter-algorithm tests in Fig. 18 are helpful, but cover only one condition per environment. Cross-play between separately generated promise sets and Promiser populations would more directly test the broader claim.

W2. The baseline comparison mixes method differences with tuning and task priors. Most methods receive the same environment-step budget. Still, PPC's configuration is selected via hyperparameter search, whereas the baselines use their original settings (Sec. 5.1). Several baselines have very low self-play returns in Overcooked-v2 and Hanabi (Table 1). That does not prove they were under-trained, but it makes their cross-play scores less informative without a diagnosis. PPC also receives task-specific rules written by an LLM. A tuned comparison and a control for the LLM's task knowledge would help separate the value of the promise machinery from these other advantages.

W3. Human-behavior coverage depends on the analysis choices. The reported 74.4% coverage on Overcooked-v1 uses an embedding fitted with rule-based behavior labels. Several labels resemble the activities named in the promises. Every method is evaluated in the same space, but the result still depends on the taxonomy and embedding used. Does PPC remain ahead with an unsupervised embedding or a comparison using the original behavior features? Variation across human pairs would also help judge the result.

W4. Variation across promise generations is still unknown. Table 4 changes the LLM, but does not show variation across repeated generations by the same model. The gains may depend on which rules were produced. Repeating the experiment with new promise sets would help assess that sensitivity and address W1.

Questions for authors
  1. What happens when cross-play partners are trained with independently generated promise sets and Promiser populations? Do the baseline methods also share training populations across ego seeds?
  2. Can you extend the inter-algorithm cross-play results in Fig. 18 to all conditions, showing PPC both as ego and as partner?
  3. Why are several baseline self-play scores so low in Overcooked-v2 and Hanabi? How much do the comparisons change when those methods receive comparable tuning effort?
  4. Can you separate the benefit of the executable promise structure from the task knowledge supplied by the LLM, for example, with a language-informed baseline or another source of promise rules?
  5. Is the human-coverage ranking stable under an unsupervised embedding or a direct comparison of behavior features?
4 comments

We thank the reviewer for the questions on independent generation, external partners, comparison settings, and human behavior. Below, we describe the corresponding revisions.


W1/W4/Q1/Q2 (Independent Generation and Generalization)

The reviewer correctly distinguishes cross-play between independently trained policies from cross-play between independently generated conventions. Our original XP evaluation addressed the former, but not the latter. In the default setup, promises and frozen Promisers are shared to reduce construction cost, as in our fixed-population baseline implementations, while egos are trained independently. We therefore repeated promise generation, refinement, Promiser learning, and ego learning independently, then cross-played the resulting egos using inferred trust.

Table R.1. Shared versus independent construction (Table 15). SP/XP: mean ±\pm SD over layout means. Time counts one shared or ten independent constructions plus the same ego-training term.

EnvironmentConstructionSPXPTime (min)
Overcooked-v1Shared291.25±36.14277.75±42.8090.75
Overcooked-v1Independent290.00±37.02268.45±46.91558.75
Overcooked-v2Shared173.67±14.42140.50±19.1793.33
Overcooked-v2Independent168.73±14.03144.37±23.62510.33

XP remains comparable under independent generation in both Overcooked versions, even though the promises and action sets differ across runs. This shows that coordination does not require identical promises or a shared Promiser population (Appendix F.4).

Q2. We also expanded held-out XP from representative settings to every Overcooked layout and Hanabi team size, evaluating each method as both ego and partner. Figure 4 summarizes the Overcooked results, with full matrices in Figures 19–21.

Table R.2. Held-out XP, ego / partner. Approximate averages exclude diagonals and equally weight the other nine methods and all layouts/team sizes.

MethodOvercooked-v1Overcooked-v2Hanabi (2-5 players)
IPPO88.8 / 87.69.1 / -11.96.7 / 8.4
OP84.5 / 90.51.7 / -0.26.6 / 8.8
FCP124.3 / 127.620.8 / 16.211.0 / 10.3
MEP109.8 / 116.2-3.3 / 12.97.9 / 6.8
E3T111.6 / 107.1-1.7 / -8.07.9 / 9.7
HSP118.8 / 110.1-6.6 / 10.86.4 / 3.7
GAMMA110.8 / 97.1-5.8 / 13.66.6 / 4.2
CoMeDi133.2 / 128.911.4 / 6.69.7 / 10.0
SemDiv79.9 / 95.317.1 / 13.08.9 / 8.7
PPC141.2 / 142.343.6 / 33.110.2 / 11.3

PPC leads both roles in Overcooked-v1/v2 and the partner role in Hanabi; FCP leads the Hanabi ego role. For a fixed external partner pool, PPC also achieves the highest BR-Prox against unseen biased partners in v1 (Table 2). That pool yields uninformative returns in v2/Hanabi, where we instead use the full cross-method matrices. These results extend the generalization evidence beyond PPC-generated partners.


W2/Q3/Q4 (Fair Comparisons and LLM Task Knowledge)

The concerns about baseline tuning and LLM-derived task knowledge involve different potential advantages, so we address them separately. We also clarify how low baseline SP affects the interpretation of XP.

W2/Q3. We use published tuned baseline configurations on their original benchmarks and follow author guidance elsewhere. PPC selects hyperparameters using SP alone and shares one configuration across layouts within each benchmark. Per-ego budgets are 30M Overcooked steps and 3B Hanabi steps, except GAMMA's original 100M-step Overcooked budget (Section 5.1).

Low SP can limit XP interpretation, but task competence alone does not explain the gap. IPPO achieves high SP yet low XP in v2 Test Time Wide and four-player Hanabi. The same-population Action latent control likewise matches PPC's v2 SP but has substantially lower XP (Table 20).

W2/Q4. To control for access to LLM task knowledge, we added SemDiv [1] with the same LLM, recurrent backbone, five generated partners, and per-ego budgets. SemDiv retains its test-time LLM selector; PPC uses inferred trust without evaluation-time LLM calls (Table 11).

PPC achieves higher XP in every listed setting. Since the deployment mechanisms differ, we also compare Reward-based PPC with identical promise definitions, population size, learner, and trust-based evaluation. Replacing masks with intrinsic rewards lowers XP in both Overcooked versions, supporting action constraints beyond access to the same semantic information (Tables 6 and 20; Appendix G.3.1).

Table R.3. PPC versus SemDiv (Table 1). Cells: SP / XP, mean ±\pm SD across seeds.

EnvironmentLayoutIPPOSemDivPPC
Overcooked-v1Counter Circuit158.00±27.00 / 32.00±12.0039.90±48.00 / 42.10±36.90260.00±22.00 / 231.00±29.00
Coordination Ring287.00±23.00 / 41.00±11.0098.80±10.00 / 87.60±17.20325.00±9.00 / 311.00±9.00
Cramped Room253.00±9.00 / 187.00±36.00192.40±15.10 / 183.00±12.80260.00±4.00 / 252.00±7.00
Forced Coordination200.00±29.00 / 10.00±11.00166.90±15.20 / 149.50±28.80320.00±12.00 / 317.00±28.00
Overcooked-v2Grounded Coordination Simple138.00±17.00 / -60.00±39.00114.40±48.70 / 110.50±46.60156.00±23.00 / 117.00±14.00
Grounded Coordination Ring162.00±9.00 / -18.00±29.0042.00±18.70 / 44.80±10.50167.00±12.00 / 120.00±58.00
Test Time Simple149.00±32.00 / -69.00±46.0060.90±58.00 / 46.40±41.50165.00±18.00 / 140.00±13.00
Test Time Wide178.00±30.00 / -51.00±12.0071.80±38.70 / 67.90±32.00186.00±9.00 / 167.00±25.00
Demo Cook Simple142.00±35.00 / 12.00±17.00101.20±72.60 / 98.60±68.20173.00±55.00 / 150.00±59.00
Demo Cook Wide152.00±41.00 / 9.00±6.0079.30±28.00 / 72.80±25.50195.00±12.00 / 149.00±34.00
Hanabi2 players23.50±0.50 / 7.30±4.4013.37±0.41 / 13.47±0.2623.00±0.20 / 22.90±0.30
3 players23.00±0.20 / 8.60±1.5012.61±0.46 / 12.52±0.3422.70±1.00 / 21.90±1.20
4 players22.50±0.60 / 4.20±1.9014.62±1.17 / 14.67±0.7522.70±0.50 / 21.10±0.40
5 players21.70±0.90 / 6.00±2.1013.24±1.14 / 13.11±0.9322.00±0.30 / 20.50±0.60

Additionally, to assess how much PPC's coordination performance depends on the task descriptions supplied to the LLM, we remove all or selected descriptions and generate fresh promises for each variant. The executable interface and RL observations, actions, and rewards remain unchanged.

Table R.4. Task-description simplification (Table 21). Cells: SP / XP, mean ±\pm SD over layout means.

Task descriptionOvercooked-v1Overcooked-v2
Full (PPC)291.25±36.14 / 277.75±42.80173.67±14.42 / 140.50±19.17
None (all removed)214.43±90.96 / 197.29±63.12134.93±49.90 / 107.30±52.12
No goal/reward227.12±70.02 / 228.10±59.48114.19±44.27 / 81.76±46.59
No state/observation232.66±55.15 / 221.52±50.27151.34±32.78 / 128.97±35.75
No action227.78±67.70 / 217.02±65.48113.56±50.46 / 54.85±25.66

PPC maintains reasonable performance in both v1 and v2 without explicit task descriptions. Goal/reward and action descriptions appear more influential than state/observation descriptions in the more complex Overcooked-v2. Even without explicit task descriptions, PPC can discover useful promises through feedback-guided refinement (Appendix G.4).


W3/Q5 (Human-Behavior Validation without Labels)

The original coverage analysis uses activity labels to make coordination patterns interpretable, but its ranking could depend on those labels or the learned embedding. We therefore added a direct comparison of unlabeled joint state-action features, including position, orientation, held item, and action. Cosine similarity is computed within each layout and role and averaged across roles, layouts, and SP/XP conditions, as detailed in Appendix G.2.1.

Table R.4. Unlabeled human-agent cosine similarity (Table 18, Appendix G.2.1).

MethodOvercooked-v1Overcooked-v2
IPPO0.31920.1512
OP0.32210.1688
FCP0.32900.1080
MEP0.16430.1723
E3T0.20600.1279
HSP0.12950.0930
GAMMA0.24150.1789
PPC0.50730.2058

PPC has the highest similarity in both Overcooked versions. This complementary result supports alignment with human coordination behavior independently of the labels and embedding used in the original coverage analysis.


Once again, we thank the reviewer for the feedback. We hope these revisions address the concerns raised.

Thanks for the detailed response and clarification. I’ll keep my current score.


The independent-pipeline results, the Reward-based PPC control, and the unlabeled similarity analysis address my main concerns I raised in my original review.


However, I do agree with Reviewer sRRv that trust needs more support. Since the enforcement probabilities are sampled from U(0, 1), predicting 0.5 already yields an MAE of 0.25. Thus, I was also wondering which entries the reported MAE (0.21 / 0.30 / 0.37) covers, and how it compares with this baseline. If trust is not recovered well in this case, I think the head should be described as an auxiliary representation rather than a trust estimate.

Two smaller points that can still be improved further: XP drops on some layouts under independent construction could be further verified and explained (e.g., Forced Coordination, 317 → 233), and the held-out XP margins would be easier to judge with standard deviations. Still, I thank the authors again for the effort on the rebuttal.

We thank the reviewer for the thoughtful follow-up and for acknowledging that our additional experiments address the main concerns. We provide further clarification on the remaining points below.

1. Reliability of Trust Estimation

We appreciate the reviewer for raising this important point. Upon revisiting our evaluation, we found that the previously reported MAE was averaged over all states, including those where promises were inactive, whereas our other analyses focused on active promises. Since promises can only be enforced when active, prediction accuracy in these states is more relevant. We therefore recalculated the MAE using only active promises, as shown in Table R.2.1. The resulting MAE values are substantially lower, ranging from 0.11 to 0.14, indicating that the estimator can reliably capture promise-specific enforcement tendencies even under partial observability. We thank the reviewer for the opportunity to clarify this distinction.

Table R.2.1 Trust prediction when promises are active.

EnvironmentTrust MAE (active promises)
Overcooked-v10.1066 ± 0.016
Overcooked-v20.1441 ± 0.039
Hanabi0.1416 ± 0.040

2. Variation under Independent Promise Generation

As the reviewer noted, Table 15 in Appendix F.4 shows that independent generation decreases XP in some layouts while improving it in others. In Forced Coordination, where object handoffs require tighter coordination, the decrease may arise because the original feedback loop evaluates coordination within a shared promise set but does not explicitly consider compatibility across independently generated sets. This suggests that incorporating cross-set coordination into the feedback loop could improve performance. Conversely, the improvements in other layouts may result from more diverse promise sets, allowing Promisees to experience a broader range of coordination patterns. We will discuss these observations in the revised manuscript.

3. Held-Out XP Clarification

Following the reviewer's suggestion, we report the standard deviations of held-out XP in Table R.2.2. Since ZSC policies trained independently within the same method may vary in task competence, poorly trained partners can lead to substantial performance variation. Nevertheless, the method-wise results in Appendix F.2 show that PPC achieves stronger coordination with partners that have learned effective policies.

Table R.2.2. Held-out XP with standard deviations.

MethodOvercooked-v1Overcooked-v2Hanabi (2–5 players)
IPPO88.8±65.0 / 87.6±65.39.1±36.1 / -11.9±55.16.7±0.7 / 8.4±0.9
OP84.5±62.4 / 90.5±60.21.7±32.3 / -0.2±39.56.6±1.2 / 8.8±1.5
FCP124.3±57.3 / 127.6±56.420.8±29.7 / 16.2±42.011.0±0.2 / 10.3±0.5
MEP109.8±64.7 / 116.2±63.2-3.3±35.3 / 12.9±29.97.9±0.2 / 6.8±0.2
E3T111.6±53.8 / 107.1±57.2-1.7±31.2 / -8.0±35.07.9±0.3 / 9.7±0.3
HSP118.8±44.0 / 110.1±59.9-6.6±35.7 / 10.8±31.56.4±0.3 / 3.7±0.1
GAMMA110.8±59.3 / 97.1±54.2-5.8±30.0 / 13.6±30.26.6±0.7 / 4.2±0.8
CoMeDi133.2±62.3 / 128.9±62.011.4±41.7 / 6.6±36.99.7±0.2 / 10.0±0.4
SemDiv79.9±62.5 / 95.3±64.217.1±33.1 / 13.0±30.98.9±0.1 / 8.7±0.2
PPC141.2±64.5 / 142.3±62.243.6±74.2 / 33.1±62.910.2±0.4 / 11.3±0.5

We hope these additional clarifications and results adequately address the remaining concerns. Thank you again for your time and thoughtful consideration.

Reviewer_sRRvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies zero-shot coordination with unfamiliar partners and proposes Promise-based Partner Coordination (PPC), which structures the behavioral diversity of training partners through executable promises. The framework uses a frozen LLM to generate state-dependent action constraints from task descriptions and refine them using interaction feedback. A population of Promisers is trained with randomized enforcement probabilities to produce different coordination behaviors. A Promisee is then trained to adapt to partners using a trust estimate inferred from its own interaction history. At deployment, the agent requires neither LLM calls nor explicit promises or natural-language descriptions from its partner. The authors provide theoretical analyses of constraint enforcement and the effect of trust-estimation error on performance. Experiments on Overcooked and Hanabi, including held-out-partner evaluations and human–AI cooperation, show improvements over the evaluated baselines. The paper also includes component ablations and cost analyses.

Critical strengths
  1. PPC provides a concrete mechanism for partner generation and adaptation. It translates LLM-generated coordination rules into state-dependent action constraints, constructs diverse training partners through randomized enforcement, and trains a history-conditioned response policy. The resulting agent does not require LLM calls or explicit partner descriptions at deployment, which is a useful practical advantage.

  2. The evaluation covers two versions of Overcooked, multiple Hanabi team sizes, multiple random seeds, held-out and cross-algorithm partners, and a human–AI study with 40 participants. These experiments support the effectiveness of the complete system. In particular, the held-out-partner and human–AI results provide evidence that the gains extend beyond pairings between agents trained by the same method. This is the strongest empirical argument in favor of acceptance.

Critical weaknesses
  1. The contribution beyond closely related LLM-based semantic partner generation, particularly SemDiv, has not been clearly established. SemDiv is cited but not included in the experiments. The conventional ZSC baselines demonstrate overall performance gains, but do not separate the contribution of LLM-derived semantic priors from that of the promise-based action constraints. This makes it difficult to assess what PPC adds to existing approaches. A controlled comparison with matched partner information and comparable training budgets would help resolve this issue.

  2. The meaning and validation of the trust representation need clarification. The estimator is supervised by the externally specified enforcement probabilities η, which need not equal the probabilities of actual promise compliance. Recovering η from interaction histories also requires identifiability. The oracle inputs and partner configurations used in the “true trust” ablations are not clearly specified, particularly for Promisee partners, since Promisee self-play provides no corresponding supervision target. A comparison with a capacity-matched, history-based partner representation is also missing. Without this control, it is difficult to determine whether the gains depend on the proposed promise-based trust representation or on more general history-based partner adaptation.

Questions for authors
  1. Under matched access to LLM-derived task knowledge and matched deployment-time partner information, how does PPC compare with a SemDiv-style semantic partner-generation baseline? Could the same ego learner and comparable population sizes and training budgets be used to isolate the value of promise constraints? This is a targeted validation request, rather than a request to compare incompatible information protocols.
  2. What exactly is supplied as “true trust” in Figures 8 and 26? How are they obtained for each type of partner, and are they provided during training, evaluation, or both?
  3. Under what assumptions can η be identified from the ego’s interaction history? How does the estimated enforcement rate relate to observed promise compliance, and how accurately is η recovered when its value is known?
  4. Does η supervision improve performance over a capacity-matched recurrent partner representation trained on the same Promiser population? Please also clarify which stages are repeated independently across seeds and which promises or populations are shared.
2 comments

We thank the reviewer for the comments on PPC's contribution, trust validation, and training independence. Below, we present the additional comparisons and clarifications.


W1/Q1 (Promise-Based Coordination beyond Semantic Priors)

The key distinction from SemDiv is not simply whether an LLM provides task knowledge, but how that knowledge is used to construct partners and support adaptation. To examine this distinction, we added SemDiv [1] using the same GPT-5.6 Sol model, recurrent IPPO backbone, five generated partners, and per-ego training budgets of 30M steps in Overcooked and 3B in Hanabi. SemDiv retains its specialized egos and test-time LLM selector, while PPC uses a single Promisee with inferred trust and no evaluation-time LLM calls, as detailed in Appendix C.5 and Table 11.

PPC's distinction is the shared promise representation linking partner construction to adaptation. Promisers learn diverse commitments through probabilistic action constraints, and the Promisee infers which commitments its partner tends to follow. The LLM generates and refines promises rather than selecting actions at deployment.

Table R.1. PPC versus SemDiv (Table 1). Cells report SP / XP, mean ±\pm SD across seeds. v1/v2 denote Overcooked-v1/v2.

EnvironmentLayoutIPPOSemDivPPC
Overcooked-v1Counter Circuit158.00±27.00 / 32.00±12.0039.90±48.00 / 42.10±36.90260.00±22.00 / 231.00±29.00
Coordination Ring287.00±23.00 / 41.00±11.0098.80±10.00 / 87.60±17.20325.00±9.00 / 311.00±9.00
Cramped Room253.00±9.00 / 187.00±36.00192.40±15.10 / 183.00±12.80260.00±4.00 / 252.00±7.00
Forced Coordination200.00±29.00 / 10.00±11.00166.90±15.20 / 149.50±28.80320.00±12.00 / 317.00±28.00
Overcooked-v2Grounded Coordination Simple138.00±17.00 / -60.00±39.00114.40±48.70 / 110.50±46.60156.00±23.00 / 117.00±14.00
Grounded Coordination Ring162.00±9.00 / -18.00±29.0042.00±18.70 / 44.80±10.50167.00±12.00 / 120.00±58.00
Test Time Simple149.00±32.00 / -69.00±46.0060.90±58.00 / 46.40±41.50165.00±18.00 / 140.00±13.00
Test Time Wide178.00±30.00 / -51.00±12.0071.80±38.70 / 67.90±32.00186.00±9.00 / 167.00±25.00
Demo Cook Simple142.00±35.00 / 12.00±17.00101.20±72.60 / 98.60±68.20173.00±55.00 / 150.00±59.00
Demo Cook Wide152.00±41.00 / 9.00±6.0079.30±28.00 / 72.80±25.50195.00±12.00 / 149.00±34.00
Hanabi2 players23.50±0.50 / 7.30±4.4013.37±0.41 / 13.47±0.2623.00±0.20 / 22.90±0.30
3 players23.00±0.20 / 8.60±1.5012.61±0.46 / 12.52±0.3422.70±1.00 / 21.90±1.20
4 players22.50±0.60 / 4.20±1.9014.62±1.17 / 14.67±0.7522.70±0.50 / 21.10±0.40
5 players21.70±0.90 / 6.00±2.1013.24±1.14 / 13.11±0.9322.00±0.30 / 20.50±0.60

PPC achieves higher XP than SemDiv across all layouts and Hanabi team sizes. Because the methods retain different deployment mechanisms, this comparison supports the overall framework rather than isolating action constraints. We therefore added Reward-based PPC, which uses the same promises, population size, learner, and inferred-trust evaluation but replaces masking with intrinsic rewards. Its lower XP in both Overcooked versions supports the constraint-based implementation. Random masking also performs worse, indicating that arbitrary restrictions alone are insufficient (Tables 6 and 20; Appendix G.3.1). Together, these controls support both meaningful promises and their action-constraint implementation.

References

[1] Li et al., "LLM-Assisted Semantically Diverse Teammate Generation for Efficient Multi-agent Coordination", ICML 2025.

W2/Q2/Q3/Q4 (Trust Clarification and Validation)

The trust representation is intended to characterize a partner's tendency to enforce particular promises, which must be distinguished from whether those promises happen to be fulfilled. In PPC, trust predicts the Promiser's sampled enforcement vector rather than observed fulfillment frequency. A Promiser may voluntarily comply even when masking is inactive, so the two quantities need not coincide.

Q2. In the true-trust ablation, actual enforcement probabilities are supplied during training with Promisers, setting ρ=η\boldsymbol{\rho}=\boldsymbol{\eta}. Unconstrained Promisees have no such vector; during self-play, the existing trust estimator infers their behavior relative to the predefined promise categories. Both SP and XP evaluation use inferred trust, as in standard PPC. Figures 9 and 29 therefore test oracle enforcement information during training, not at evaluation.

Q3. Identifying η\boldsymbol{\eta} from history requires informative promise activations and distinguishable behavior under different enforcement rates. Partial observability and stochasticity can limit recovery, especially for unfamiliar partners. We report trust-prediction MAE and the separate enforcement-fulfillment discrepancy to assess these two aspects without equating them.

Table R.2. Trust prediction and enforcement-fulfillment discrepancy.

EnvironmentTrust MAEEnforcement/fulfillment error
Overcooked-v10.213013.15%
Overcooked-v20.29547.13%
Hanabi0.37358.32%

The prediction MAE measures recovery of the known enforcement target; the second metric measures its discrepancy from realized fulfillment. These need not coincide because fulfillment can occur without masking.

Q4. To test whether generic history modeling suffices, Action latent uses the same frozen Promisers, histories, observation encoder, 128-unit GRU, and 25-dimensional latent as PPC, but predicts partner actions instead of enforcement probabilities (Table 20).

Table R.3. Trust versus action-prediction latent (Table 20). Cells report SP / XP, mean ±\pm SD across layout means.

EnvironmentAction latentPPC
Overcooked-v1282.00±37.88 / 226.25±33.97291.25±36.14 / 277.75±42.80
Overcooked-v2177.40±17.72 / 76.11±69.79173.67±14.42 / 140.50±19.17

Action latent achieves comparable SP but substantially lower XP in both Overcooked versions, supporting promise-indexed trust for partner adaptation beyond a capacity-matched action-prediction representation.

The default shares generated promises and frozen Promisers to reduce construction cost, while ego training is independent. We also repeated promise generation, refinement, Promiser learning, and ego learning independently. Cross-play remains comparable without sharing (Table 15; Appendix F.4).


Once again, we thank the reviewer for the careful review. We hope these comparisons clarify the contributions of promises and trust.

Comments on the paper

2 comments

General Response to All Reviewers

We sincerely thank the Area Chair and all reviewers for their careful review and constructive feedback. In response, we expanded our experiments and clarified PPC's contributions, trust representation, generalization, and evaluation protocols. We summarize the main revisions below.

(i) Trust Clarification and Empirical Validation (Reviewers sRRv, 2Jnt; Figures 9 and 29, Table 20)

Reviewers sRRv and 2Jnt raised important questions about what trust represents and how it is validated. We clarified that the trust estimator predicts a Promiser's sampled enforcement probabilities, which need not equal observed promise fulfillment because commitments may be satisfied even without masking. We now report trust-prediction errors separately from enforcement-fulfillment discrepancies and discuss when enforcement can be inferred from interaction histories. We also clarified that the true-trust ablation uses actual enforcement probabilities only during training with Promisers, while evaluation relies on inferred trust. Finally, a capacity-matched action-prediction latent achieves comparable SP but lower XP, supporting the benefit of promise-indexed supervision over generic history-based partner modeling.

(ii) Broader Generalization through Held-Out XP and BR-Prox (Reviewers MsD9, 2Jnt; Figure 4, Table 2, Appendix F.2)

The reviewers noted that within-method XP and representative external-partner tests alone do not establish generalization to diverse unseen partners. We therefore expanded held-out XP to all Overcooked layouts and Hanabi team sizes, evaluating each method as both ego and partner. PPC achieves the highest averages in both roles on Overcooked-v1/v2 and in the partner role on Hanabi, while FCP leads Hanabi's ego role. We also highlight BR-Prox, which evaluates all egos against the same unseen biased-partner pool in Overcooked-v1, where PPC ranks first. These evaluations provide broader evidence of coordination with partners outside PPC's training population, while distinguishing within-method compatibility from external-partner generalization.

(iii) Additional Baselines and Controlled Promise Comparisons (Reviewers sRRv, MsD9, 2Jnt; Tables 1, 6, 11, and 20, Appendix G.3.1)

To assess whether PPC's gains arise from LLM-derived task knowledge or from its promise-based design, we added SemDiv and CoMeDi across all benchmarks. The SemDiv comparison matches PPC's LLM, recurrent backbone, population size, and per-ego training budget while retaining each method's deployment mechanism. PPC achieves higher XP across the evaluated settings. We further introduced two controls to examine the role of promises more directly. Reward-based PPC uses the same promises and trust-conditioned learner but replaces action masking with intrinsic rewards, while random masking applies restrictions without meaningful promises. Both perform below PPC, supporting the contribution of task-grounded commitments and their constraint-based enforcement rather than LLM access or masking alone.

(iv) Fair Comparison Protocols and Independent Promise Generation (Reviewers sRRv, MsD9, 2Jnt; Section 5.1, Table 15, Appendix F.4)

We clarified the comparison protocol in response to concerns about hyperparameter selection. Baselines use published tuned configurations where available and author-guided settings otherwise; PPC selects its configuration using SP and applies it across layouts within each benchmark. We also addressed the concern that sharing promises and Promisers across ego seeds might overstate generalization. Although sharing reduces population-construction cost, we independently repeated promise generation, refinement, Promiser learning, and ego learning to test cross-play between separately constructed populations. Performance remains comparable to the shared setup, indicating that coordination does not require identical promise sets or a common Promiser population.

We additionally clarified the task specifications and interfaces required for automated promise generation in Appendices C.1-C.3. We also show that PPC maintains reasonable performance without explicit task descriptions (Appendix G.4). To address concerns about human-behavior labels and learned embeddings, we added a direct comparison using unlabeled state-action features, where PPC achieves the highest human-agent cosine similarity among the evaluated methods (Table 18, Appendix G.2.1). Detailed responses follow.

Dear Reviewers,

We appreciate the time and effort you have devoted to evaluating our work. Your feedback has helped us strengthen the manuscript through additional experiments and clarifications, mainly regarding trust modeling, promise-based coordination, and evaluation protocols.

With the discussion period approaching its conclusion, we would welcome any remaining questions or concerns regarding our responses and revisions. We would be happy to address them.

Thank you again for your consideration.

Best regards, Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.