- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how to select training environments to improve zero-shot coordination between independently trained agents while maintaining task competence. It introduces a compatibility margin to characterize whether near-optimal self-play policies can coordinate successfully. The paper derives theoretical results for sequential environments, analyzes how different feedback mechanisms affect learning complexity, and evaluates curriculum selection methods on synthetic coordination tasks. The results highlight the distinction between theoretical compatibility guarantees and actual learning performance.
Critical strengths
S1. Meaningful theoretical analysis.
The paper provides a structured analysis of compatibility guarantees, competence constraints, and feedback-dependent learning complexity. The distinction between solution-set guarantees and practical learnability offers useful insights into environment selection for zero-shot coordination.
S2. Careful experimental controls.
The experiments include competence-threshold analyses and comparisons with teachers having matched target information, which help distinguish the effects of the proposed margin objective from other factors.
Critical weaknesses
W1. Insufficient experimental validation.
The experiments are limited to small synthetic tasks with only 6–7 nodes and at most 128 deterministic conventions. No standard multi-agent coordination benchmarks are evaluated, leaving the generalizability of the proposed framework unclear. Moreover, the joint-margin curriculum underperforms simpler baselines in Table 1 and shows no meaningful improvement over the information-matched nominal baseline in Table 2. The absence of learning curves and systematic analyses of the selected source mixtures further limits the evidence for its practical benefits.
W2. Weak presentation and limited visualization.
Despite the extensive theoretical analysis, the main paper contains only two experimental figures, both showing joint success across competence thresholds. The figures are cluttered, with overlapping curves that make comparisons difficult. Important concepts and results, such as diagnostic exposure, environment selection, and the relationship between compatibility margins and learning outcomes, lack intuitive visualizations. The dense theoretical exposition also makes the main contributions difficult to follow.
Questions for authors
Q1. What is the key theoretical novelty of the proposed compatibility framework compared with existing version-space and machine-teaching formulations?
Q2. Can the authors provide evidence on more complex or standard multi-agent coordination benchmarks to demonstrate the generalizability of the proposed framework?
Q3. Since the joint-margin curriculum does not consistently outperform simpler baselines, can the authors provide learning curves or analyses of the selected environment distributions to clarify when and why margin optimization is beneficial?
5 comments
Response to Reviewer 34Si (2/3): when the margin helps (Q3), benchmarks and larger instances (W1, Q2)
Response to Reviewer 34Si (2/3): when the margin helps (Q3), benchmarks and larger instances (W1, Q2)
When the margin helped (Section 7). In the task where choices steer the episode, the baseline floor of .60 was chosen after a pilot study, so we report all five floors (.50 to .70), with pointwise intervals.
- Against the easy-source control, the margin teacher gains 23.64 points [9.58, 38.41] at and 13.86 points [4.69, 22.58] at , but from to .70 the two teachers are not distinguishable. Against the aligned-source oracle, which is told which source matches the target, every interval contains 0.
- With two other choices of at , the margin teacher beats the easy-source control by 21.78 points [7.49, 36.96] when omits the anti-target source (the source fully opposed to the target), and by 27.02 points [15.26, 40.38] when is the aligned source. In the second case plain training on does about as well, trailing the margin teacher by 1.95 points [0.00, 4.39], which we count as unresolved.
- At with the baseline , Table 10 lists the mixtures four teachers selected in each library (one randomly generated task instance). In the 10 feasible libraries, where some pair of policies meets every requirement, the margin teacher beats the easy-source control in 6, loses in 3 and ties in 1. The 3 losses have the smallest selected margins (0.02 to 0.05, against 0.28 to 0.40), an untested pattern we found after the fact.
- For 24 random mixtures per library drawn independently of the margin (Figure 8), the within-library Spearman correlation with joint success at is 0.86 [0.77, 0.92] for the margin and 0.79 [0.72, 0.85] for a binary indicator of whether the mixture's optimal convention, paired with itself, meets all requirements. Among positive-margin mixtures, the margin's correlation is 0.64 [0.36, 0.84]. These associations are exploratory.
We claim no necessary or sufficient condition for when the margin helps.
Benchmarks. We have not run a standard large benchmark such as Hanabi or Overcooked, and the revision claims neither benchmark-level generality nor an end-to-end efficiency gain. The tasks are small because the theorems concern every near-optimal pair, so checking them exactly requires a policy class small enough to enumerate (Appendix I.2). For larger settings, Appendix N gives a certificate for a finite trained population (Theorem 19) and a lower bound on the probability that fresh training runs succeed (Proposition 15). Exact design does not always need enumeration either: under the conditions of Theorem 2 and at strict floors, where any mistake makes a learner incompetent (as at ), finding the best mixture is a linear program with one constraint per decision point, solvable in polynomial time for explicit rational Markov sources (new Corollary 23).
Larger instances (Appendix O).
- The Table 1 suite now also has 8, 10 and 12 decision points, with up to 4,096 conventions checked exactly at (Tables 14–15, Figure 9). At every size after 4,096 episodes, the exact optimizer beats path coverage by 25 to 59 points and the joint-margin LP by 18 to 28 points, with all intervals excluding 0, but competence cover ties it at every size and budget. The exact optimizer's lead over training on depends on the budget: at 4,096 episodes the interval excludes 0 at (+7.4 [2.5, 12.3]) and (+7.0 [2.2, 11.5]), while at and it first does so at 8,192 episodes (+7.3 [3.3, 10.8] and +11.3 [2.6, 22.8]). The exact joint margin is rank-correlated with the nine curricula's joint success at 4,096 episodes (within-library Spearman 0.83 to 0.88), whereas the coordination-only margin is weakly negatively correlated (−0.24 to −0.36).
- We also built trees where choices steer the episode, with 7, 15 and 31 nodes (Tables 16–17, Figure 10). Because the 31-node class cannot be enumerated, table-based teachers at every depth see only sampled estimates from 280 trained pilot policies, so that all depths share one pipeline. Deeper trees use lower floors, because sampled competence falls with depth. At 15 and 31 nodes the low-floor advantage did not persist: at 31 nodes and , the margin teacher still beats training on by 9.3 points [0.4, 20.4], but loses to the easy-source control (−17.1 [−30.7, −2.9]) and to a teacher using the pilot's observed joint success (−19.6 [−30.8, −8.0]). With 512 rollouts per entry, Theorem 19's certificate, which corrects the margin for sampling error, is zero at every depth, so these selections are heuristics.
Response to Reviewer 34Si (3/3): novelty (Q1) and presentation (W2)
Response to Reviewer 34Si (3/3): novelty (Q1) and presentation (W2)
Q1: novelty. The key novelty is an exact structural calculation of the margin. Under Theorem 2's conditions, the cost of a set of mistakes is a submodular failure probability, and the coordination margin is the larger cost in the most even split of a harmful disagreement (a set of decision points on which disagreeing breaks the target) between two learners, minimized over such sets. This yields , where is the cost for one learner to make the cheapest harmful disagreement alone. It also yields an LP over mixtures with a tight factor-1/2 guarantee (Proposition 11), an exact condition for a positive margin and a dilution law (Corollary 3), and weak NP-hardness of exact evaluation when the target threshold is part of the input (Proposition 9). The bad-pair relation itself is not new (l. 084–085), and the statement that every pair of policies within of the best self-play return is safe exactly when is only an organizing lemma (l. 121).
Section 2 now relates the margin to version spaces (Mitchell, 1982) and machine teaching (Goldman & Kearns, 1995; Zhu, 2015). Our problem differs from them in three ways.
- Machine teaching usually drives a learner to a target, whereas our teacher only has to exclude bad pairs formed by two independent learners, so no unique surviving policy is needed (l. 122–123). Teaching many learners with one set (Zhu, Liu & Lopes, IJCAI 2017) still requires each learner to reach the target.
- A policy survives if its reward under a weighted mixture is near-optimal, so informative environments can be diluted (Corollary 3) and conflicting ones can cancel (Theorem 4). Neither happens in consistency-based teaching.
- The right curriculum objective depends on the learner's feedback. With final-success feedback, learning can need exponentially many episodes, while with failure-location feedback it needs at most on a deterministic path with fatal wrong assignments (Theorem 5). This mirrors the classical contrast between equivalence queries that answer only yes or no and those that return a counterexample (Angluin, 1988). What we add is that an LP maximizing the smallest singleton exposure (Eq. 12, Appendix A.2), not the margin in general, optimizes the bound on episodes needed by a learner that flips each failed decision.
W2: presentation.
- Figure 1 now has two panels sharing one legend, and Figure 2 has three panels separating teachers without extra target information, controls using the same exact tables, and teachers with other target information.
- A worked example in Section 3 and a schematic (Figure 4) illustrate diagnostic exposure and the balanced split.
- Selected mixtures (Table 10), the margin against joint success for 384 held-out mixtures (Figure 8) and learning curves (Figures 5–7 and 9) are new. The 10-page limit keeps them in the appendix, with pointers from the main text.
- The introduction now defines each term at first use, Sections 3–6 each open by saying what they show, and Appendix K adds a glossary (Table 3).
Response to Reviewer 34Si (1/3): Tables 1 and 2, and learning curves (W1, Q3)
Response to Reviewer 34Si (1/3): Tables 1 and 2, and learning curves (W1, Q3)
Thank you for the careful review. We agree with your reading of both tables. The submitted phrase "the teacher's robust objective" (l. 130) invited reading the margin teacher as our method, so Section 3 now states that Section 6 evaluates margin teachers "as tests of the analysis, not as a proposed method". Our claim is a separation (l. 020–021, 025–028): the margin certifies which near-optimal solutions are compatible, whereas the curriculum that helps learning depends on the learner's feedback and the teacher's knowledge.
Table 1. In this suite, where choices do not change which decision points are visited, the joint-margin LP falls short because it optimizes a surrogate. At the competence floor (required average return) c=.98, only the preferred convention, which every source favors, is competent (l. 322–323). The exact joint margin is then the smallest singleton exposure (the probability that one wrong decision makes a training episode fail), and a small linear program (LP) maximizes it (new Proposition 22, Appendix L.1). The submitted joint-margin LP (55.9%) instead maximizes a certificate guaranteed only to reach half of that margin or more (l. 205–206).
Learning curves (Figures 5 and 7). Table 1 is a snapshot taken while joint success is still rising. By 16,384 episodes, training on ν, inverse singleton, competence cover and the exact optimizer reach 100% and the joint-margin LP 98.6%, but path coverage and probe cover (competence cover without the competence requirement) reach only 54.6% and 55.9%. These two put zero weight on two diagnostic sources, so their smallest singleton exposure averages 0.014 and their learners fall below the floor. In a descriptive comparison (Appendix L.1), ranking the curricula by exact joint margin reproduces their order of joint success at 4,096 episodes up to near-ties, while ranking by the coordination-only margin, which ignores competence, does not. Uniform sampling is the one exception to this ranking: it reaches only 8.5% at 4,096 episodes, because its margins are diluted to exactly 6/14 of those of training on ν (Corollary 3) and the sufficient budget of a learner that sees only final success grows with the inverse square of its signal. Figure 7, for the task where choices steer the episode, shows every curriculum leveling off by about 4,096 episodes and omits the Small FCP baseline, whose partner generation follows a different protocol.
Table 2. The margin teacher reaches 43.2%, against 16.8% for training on ν, but target information explains much of this gap. A nominal control uses the same exact tables to pick, among mixtures whose optimal policy is competent, the one whose optimal policy scores best on the target. With ties broken toward ν, it already beats training on ν by 12.09 points [5.19, 19.75]. With ties broken toward the mixture with the largest optimal training return (the easy-source control, "Nominal, easy-source ties" in Table 2), it reaches 43.1%, only 0.14 points [−7.65, 7.31] behind the margin teacher.