acceptodds
Under review as a conference paper at ICLR 2027

Which Environments Teach Cooperation? Guarantees, Feedback, and Competence

Abstract

Choosing environments for independently trained agents involves two different questions: are their near-optimal self-play solutions compatible, and can the learners reach those solutions? We study this distinction while requiring competence on a fixed task distribution. For sequential protocols with shared preferences and action-independent paths, an exact balanced partition of diagnostic losses characterizes incompatible near-optimal pairs. Conflicting one-step sources instead induce signed exposures; conflicting sequential sources need not admit the same representation. We then show that observable failure locations lead to a polynomial singleton-exposure objective for a correction learner, even when a terminal-reward estimator requires much more data. Experiments separate solution-set guarantees from learned performance. On invariant tasks with delayed rewards, training on the competence distribution is a strong default. In small action-steering tasks, controls with matched target information reveal that the advantage of margin selection depends on the competence floor and nominal tie-breaking rule. Additional mixtures selected independently of the margin show a positive association within positive-margin regimes. The resulting framework gives conditional certificates and identifies which environmental, feedback, and competence assumptions are needed to interpret them; it does not make a large margin a universal curriculum objective.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
multi-agent reinforcement learning, self-play, cooperation, environment design, curriculum learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_34SiOpenReview ↗
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
AuthorsOpenReview ↗

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=.98c=.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).

  • With the same seeds, the exact optimizer reaches 80.6% [77.4, 83.8] joint success (a new row of Table 1), 24.70 points [19.08, 29.92] above the joint-margin LP and 7.40 points [2.48, 12.32] above training on ν\nu, the task distribution that defines competence. At 4,096 episodes it leads inverse singleton (which weights diagnostic sources inversely to their singleton exposure) by 3.80 points [0.15, 6.91], but not at 8,192 episodes (−0.69 [−2.08, 0.00]).
  • It ties competence cover, which at this floor equals probe all. Probe all maximizes the smallest probe signal, the average reward gain from correcting one decision under a random convention, and competence cover takes that minimum only over decisions that competence or the target requires. Each singleton exposure upper-bounds its decision's signal, and probe all selects nearly the same weights as the exact optimizer (Appendix L.1), so this tie does not show that the margin itself drives learning.
  • Optimized exactly at c=.95c=.95, .90 and .85 (Table 7), at 4,096 episodes the margin curriculum reaches 81.2%, 91.8% and 97.2% joint success and beats training on ν\nu by 7.3 to 17.3 points. However, at each floor at least one objective using the same exact tables ties it: path coverage (an LP ignoring competence) and the joint-margin LP at .85, the joint-margin LP and competence cover at .90, and competence cover at .95. These comparators were designed at .98 or ignore the floor.

Learning curves (Figures 5 and 7). Table 1 is a snapshot taken while joint success is still rising. By 16,384 episodes, training on ν\nu, 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 ν\nu (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 ν\nu, 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 ν\nu, it already beats training on ν\nu 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.

AuthorsOpenReview ↗

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 c=.50c=.50 and 13.86 points [4.69, 22.58] at c=.55c=.55, but from c=.60c=.60 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 ν\nu at c=.60c=.60, the margin teacher beats the easy-source control by 21.78 points [7.49, 36.96] when ν\nu omits the anti-target source (the source fully opposed to the target), and by 27.02 points [15.26, 40.38] when ν\nu is the aligned source. In the second case plain training on ν\nu does about as well, trailing the margin teacher by 1.95 points [0.00, 4.39], which we count as unresolved.
  • At c=.60c=.60 with the baseline ν\nu, 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 c=.60c=.60 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 c=.98c=.98), 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 c=.98c=.98 (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 ν\nu depends on the budget: at 4,096 episodes the interval excludes 0 at d=6d=6 (+7.4 [2.5, 12.3]) and d=10d=10 (+7.0 [2.2, 11.5]), while at d=8d=8 and d=12d=12 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 c=.45c=.45, the margin teacher still beats training on ν\nu 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.
AuthorsOpenReview ↗

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 Γ\Gamma 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 κ/2≤Γ≤κ\kappa/2\le\Gamma\le\kappa, where κ\kappa 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 η\eta of the best self-play return is safe exactly when Γ>η\Gamma>\eta 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.

  1. 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.
  2. 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.
  3. 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 dd 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).
Reviewer_7Ys8OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Despite my best effort and familiarity with the literature I am not able to make sense of the paper. My best guess is that the authors are trying to generate a curriculum learning method that allows independently trained agents to collaborate.

Critical strengths

None

Critical weaknesses

The current writing of the paper makes it impossible for me to assess the contributions. For example, the abstract and introduction are full of terminology that is both not standard in the field and has not been introduced.

Examples include: "Conflicting one-step sources instead induce signed exposures;" and "We then show that observable failure locations lead to a polynomial singleton-exposure objective for a correction learner,"

Questions for authors

NA

1 comment
AuthorsOpenReview ↗

Response to Reviewer 7Ys8

Response to Reviewer 7Ys8

Thank you for the candid review. The submitted abstract and introduction used our own undefined shorthand, such as "signed exposure" and "singleton-exposure objective".

What changed.

  • The abstract (p. 1) is rewritten in plain language and no longer uses either sentence you quoted.
  • The introduction (pp. 1–3) now defines each term at first use (self-play, cross-play, convention, preferred convention, target task, η\eta-optimal, diagnostic exposure, harmful pair, harmful disagreement) and ends with a numbered list of contributions.
  • Each of Sections 3–6 now opens by saying what it shows. Section 3 adds a worked example with three policies (Figure 4), and Appendix K adds a glossary (Table 3).

The paper in plain terms. Your guess is close. We study when a weighting of the training environments (a mixture) guarantees that agents trained separately and later paired will cooperate. We do not propose a new curriculum method. A policy follows a convention, which assigns roles at each of dd decision points. Each training environment prefers one assignment at each point, and a wrong assignment makes an episode fail with some probability. A policy is η\eta-optimal if its self-play return on the training mixture is within η\eta of the best. The compatibility margin is the smallest η\eta at which two η\eta-optimal policies can fail together on the target, or one of them can fall below a required average return on a task distribution ν\nu. Learners whose suboptimality is below the margin therefore never form such a pair.

Main results.

  • Suppose all environments prefer the same convention, both agents label decision points alike, choices do not change which points are visited, every convention is available, and the target penalizes only disagreement. Then the coordination margin, which ignores the average-return requirement, has an exact formula (Theorem 2). Call a set of decision points a harmful disagreement if two policies that disagree exactly there fail on the target. Two learners produce it by splitting the set, each erring on one part, and each one's self-play return drops by the probability that its own errors make a training episode fail. The coordination margin is the smallest value of the larger drop, over all harmful disagreements and all ways to split them.
  • The margin does not determine how hard learning is (Theorem 5). On a fixed path of dd decision points where every wrong assignment is fatal, the margin is 1, yet a learner seeing only final success can need exponentially many episodes in dd, while one told where each episode failed needs at most dd.
  • In tasks with six decision points where learners see only final success, the exact margin-maximizing mixture beats training on ν\nu after 4,096 episodes at every required average return tested. However, another objective using the same exact returns ties it, and with four times the budget, training on ν\nu reaches 100% success. When choices change which points are visited, a simpler selector with the same information about the target can do as well.

"Conflicting one-step sources instead induce signed exposures." It concerns environments that prefer different assignments in single-decision episodes. A mixture then gives each decision jj a net score sjs_j, its signed exposure (Eq. 8), which is positive if the weighted environments favor one assignment, negative if they favor the other, and zero if they cancel. A policy loses ∣sj∣|s_j| at each decision where it goes against that sign, and the split formula above holds with these costs (Theorem 4). With several decisions per episode, the formula can fail. Item (ii) of the introduction (p. 2) now says this in words.

"Observable failure locations lead to a polynomial singleton-exposure objective for a correction learner, even when a terminal-reward estimator requires much more data." A correction learner is told where an episode failed and flips its decision at that point. The singleton exposure of decision jj is the probability that one wrong choice at jj makes a training episode fail. Under Theorem 2's conditions, this learner needs at most d/sd/s episodes in expectation, where ss is the smallest singleton exposure (Eq. 10). Maximizing ss over mixtures is a linear program with one constraint per decision (Eq. 12, Appendix A.2), solvable in polynomial time for explicit Markov models. The terminal-reward estimator sees only final success, and its signal can shrink geometrically with dd while the margin stays fixed (Proposition 14). Item (iii) of the introduction describes both learners in words, and Section 5 makes them precise.

We would be glad to explain any term that remains unclear, and we would be grateful if you revisited your evaluation in light of the revision.

Reviewer_b9BWOpenReview ↗
Rating
3
Confidence
1(−2)
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies how the selection of training environments affects cooperation between independently trained agents. The authors introduce a compatibility margin to understand when near-optimal self-play policies can cooperate successfully, while also considering whether the agents remain competent on the given tasks. The paper develops theoretical results based on balanced exposure, examines cases where training environments prefer different conventions, and shows how the type of feedback available to the learner can affect learning difficulty. The authors evaluate these ideas using synthetic sequential and action-steering environments, comparing different curriculum-selection methods and competence requirements. The results highlight the importance of considering both coordination and learning difficulty when designing training environments.

Critical strengths
  1. The paper gives a clear way to understand when independently trained agents can cooperate, even if they learn slightly different policies. I found the balanced-exposure analysis particularly interesting, as it helps explain how the choice of training environments affects cooperation. It is also good that the authors consider task competence rather than focusing only on coordination.
  2. I liked how the paper separates the question of whether good policies can cooperate from whether agents can actually learn those policies. The example showing how knowing where a failure occurs can make learning much easier was particularly helpful. The experiments also include several useful baselines and comparisons across different settings, which help support the analysis.
Critical weaknesses
  1. Although the paper includes several theoretical examples, a small worked example explicitly calculating the compatibility margin would make the main formulation look better.
  2. The paper provides a thorough theoretical analysis and useful synthetic experiments. A brief illustrative discussion connecting these results to practical environment-selection decisions would help communicate their potential relevance to broader multi-agent learning applications.
Questions for authors
  1. The paper includes several useful theoretical examples. Would it be possible to add a small worked example that explicitly demonstrates how the compatibility margin is calculated from the training rewards of a few policies?
  2. Could the authors briefly illustrate how the proposed framework might guide curriculum selection in a practical multi-agent learning scenario?
2 comments
AuthorsOpenReview ↗

Response to Reviewer b9BW (1/2): a worked example of the margin (W1, Q1)

Response to Reviewer b9BW (1/2): a worked example of the margin (W1, Q1)

Thank you for the positive and constructive review. Section 3 of the revised PDF now works through the example below, and Appendix K.1 gives the full calculation, a table, the sequential case and a schematic (Figure 4).

Setup. Take three policies π1,π2,π3\pi_1,\pi_2,\pi_3 and two training environments with these self-play returns:

π1\pi_1π2\pi_2π3\pi_3
environment e1e_110.81
environment e2e_2110.8

On the target, π1\pi_1 and π3\pi_3 coordinate, while π2\pi_2 fails with both. Writing TijT_{ij} for the target return when πi\pi_i and πj\pi_j are paired, T13=T31=1T_{13}=T_{31}=1, T12=T21=T23=T32=0T_{12}=T_{21}=T_{23}=T_{32}=0 and Tii=1T_{ii}=1, with threshold τ=0.8\tau=0.8.

  1. With weight pp on e1e_1, the self-play scores are S=(1, 1−0.2p, 0.8+0.2p)S=(1,\,1-0.2p,\,0.8+0.2p), so the gaps to the best policy are g=(0, 0.2p, 0.2(1−p))g=(0,\,0.2p,\,0.2(1-p)) (Eq. 1).
  2. Without a competence requirement, a pair is bad if its target return is below τ\tau, so the bad pairs are (1,2)(1,2), (2,3)(2,3) and their reverses (Eq. 3).
  3. The margin is the smallest value, over bad pairs, of the larger gap in the pair (Eq. 2). Pair (1,2)(1,2) gives 0.2p0.2p and pair (2,3)(2,3) gives at least that, so Γ(p)=0.2p\Gamma(p)=0.2p: training on e1e_1 alone gives 0.2, e2e_2 alone gives 0, and the equal mix gives 0.1. Environment e1e_1 teaches the distinction the target needs, while e2e_2 teaches one it does not.
  4. Now also require competence: each policy's average return on the tasks ν\nu, here uniform over e1e_1 and e2e_2, must reach the floor c=0.95c=0.95. The average returns are V=(1,0.9,0.9)V=(1,0.9,0.9), so π2\pi_2 and π3\pi_3 are incompetent, and pairs (1,3)(1,3) and (3,3)(3,3) become bad, with larger gap 0.2(1−p)0.2(1-p). The joint margin, which counts both kinds of bad pair, is min⁡{0.2p,0.2(1−p)}\min\lbrace 0.2p,0.2(1-p)\rbrace. It peaks at 0.1 when p=1/2p=1/2, while e1e_1 alone drops to 0. With c=0.90c=0.90 all three policies are competent, and e1e_1 alone is best again.
  5. Add 18 neutral environments where every policy scores 1, and sample all 20 uniformly. The equal-mix gaps shrink tenfold to g=(0,0.01,0.01)g=(0,0.01,0.01), and the joint margin falls to 0.01 (Corollary 3). A learner that may fall 0.02 short of optimal can now output π2\pi_2 or π3\pi_3, even though no informative environment was removed.

Sequential case (Theorem 2; Appendix K.1 and Figure 4a). Here a convention sets one bit per decision point (00 is preferred), each training episode visits each of the two points once, and a wrong bit fails with probability 1/2 at that visit. The target visits one point uniformly at random and fails if the agents disagree there. With τ=1/4\tau=1/4, disagreeing on one point gives target cross-play 1/2, which is acceptable, while disagreeing on both gives 0.

  • The conventions 00, 10, 01 and 11 have self-play returns 1, .5, .5 and .25, so their gaps are 0, .5, .5 and .75.
  • The bad pairs are (00, 11), with larger gap .75, and (10, 01), with larger gap .5. Hence Γ=0.5\Gamma=0.5, attained when each learner errs at one point.
  • If one learner made the whole disagreement alone, it would pay κ=0.75\kappa=0.75. A check limited to that case would call learners within 0.6 of optimal safe, yet two learners with gaps of .5 each are incompatible.
AuthorsOpenReview ↗

Response to Reviewer b9BW (2/2): practical guidance for choosing environments (W2, Q2)

Response to Reviewer b9BW (2/2): practical guidance for choosing environments (W2, Q2)

The revised Section 7 condenses the steps below under "A practical reading". Steps 2, 3 and 5 rest on results that assume every convention is available, both agents label decision points alike, all environments prefer the same convention, and the agents' choices do not change which points are visited (l. 066–068, 173). Steps 2 and 3 also assume a target that penalizes only disagreement. Where actions steer the trajectory, as in Overcooked-style layouts, the steps are heuristics suggested by the theory.

  1. Fix what competence means. Choose ν\nu (the tasks each agent must perform well on) and the target task. Start from training on ν\nu, which needs no target information.
  2. Check coverage. If disagreeing on every choice that no environment penalizes can push target success below the threshold, no mixture certifies compatibility (Corollary 3). Adding an environment that penalizes wrong choices at those points fixes this.
  3. Avoid dilution. If most layouts in a library score every convention the same, sampling it uniformly multiplies the margin by the total weight on the other layouts (Corollary 3). The factor is exact for fully neutral layouts, while partly informative layouts that share the preferred convention shrink the margin by at most this factor, because they never reward a wrong convention (Appendix G.5).
  4. Check for conflict. Layouts rewarding "the nearest agent hands off" and layouts rewarding "a fixed role" can cancel in a mix. When each episode makes one decision, Theorem 4 describes this cancellation exactly, but for sequential conflicts the exact formula of Theorem 2 can fail, so compute the margin from the return table (Definition 1).
  5. Match the objective to the feedback. If episode records show where each self-play episode failed, a learner that flips the failed decision has a correction-time bound set by the smallest probability that one wrong decision makes an episode fail (Eq. 10). A small linear program maximizes this probability over mixtures (Eq. 12, Appendix A.2). With this learner (Appendix L.2), all nine curricula we tested reach 100% joint success (both learners competent and the pair meeting the target) by 1,024 episodes. The linear program did not beat training on ν\nu with 6 decision points, where its mean correction time is 0.23 episodes longer [−0.69, 1.21], and with 8 to 12 it is faster by only 1.0 to 1.6 episodes (Appendix O.1).
  6. Attribute gains carefully. Compare a new teacher with training on ν\nu and with a selector given the same target information. In our tasks where actions steer the episode, such a selector picks, from the same exact tables, the mixture whose optimal policy scores best on the target, among those whose optimal policy is competent (ties go to the largest optimal training return). It matches the margin teacher at our baseline floor c=.60c=.60 (+0.14 [−7.65, 7.31]), but the margin helped at the lower floor c=.50c=.50 (+23.64 [9.58, 38.41]).

A concrete reading of the example (Appendix N). As a hypothetical illustration, not a benchmark result, read e1e_1 and e2e_2 as two kitchen layouts: e1e_1 penalizes the wrong handoff (π2\pi_2), e2e_2 the wrong counter side (π3\pi_3), and deployment needs only the handoff convention. Then e1e_1 alone certifies compatibility for learners less than 0.2 short of optimal. Requiring a high average return on both layouts (c=0.95c=0.95) moves the best mix to equal weights, and adding 18 layouts where any convention works shrinks the equal-mix margin tenfold, from 0.1 to 0.01.

Trained populations (Appendix N). Without exact tables, one trains KK policies, estimates their returns and pairwise target returns by rollouts, and computes this finite table's margin with sampling-error bounds (Theorem 19). This certificate covers only the tabulated policies, and Proposition 10 corrects the gaps when the population's best policy falls short of the class optimum. Proposition 15 separately lower-bounds the probability that fresh training runs succeed. The tables are costly: the pilot-based teacher of Section 6.2 uses 450,560 episodes per task instance, and the Appendix O.2 tables use about 4.5×1074.5\times10^7 per instance. On 7-node trees in which choices steer the episode (Appendix O.2), the sampled-table margin still beats the step-6 selector at c=.50c=.50 (+21.6 [9.1, 35.9]), as the exact-table margin did, but with 15 and 31 nodes it no longer does. With 512 rollouts per entry, the certificate is zero for every mixture at all three sizes, so at that scale the table margin is a heuristic and Proposition 15 is the remaining guarantee.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

General response

We thank the three reviewers. Reviewers 7Ys8 and 34Si found the paper hard to follow, and Reviewer b9BW asked for a worked example and practical guidance. Our uploaded revision addresses these points. In our replies, "l." refers to a line of the submitted PDF, while section, table and figure numbers refer to the revision.

What the paper does. Two agents trained separately by self-play on the same mixture of environments can fail when paired on a target task because they learned different conventions (choices of who does what at each decision point). The paper analyzes which mixtures guarantee that any two near-optimal policies coordinate on the target while each keeps a required average return on a task distribution, and whether learners can reach such policies. Its experiments choose mixtures by maximizing a compatibility margin (defined in our reply to Reviewer 7Ys8) only to test this analysis, not as a proposed method.

Main changes. The abstract and introduction are rewritten in plain language, and the introduction now defines every term at first use. Section 3 adds a worked example and Section 7 a practical reading of the results, while the appendices add a glossary, learning curves, the mixtures each method selected, and larger instances. All theorems and submitted results are unchanged. Our reply to Reviewer 34Si explains why we have not run a standard large benchmark.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.