ConventionPlay: Capability-Limited Training for Robust Ad-Hoc Collaboration

1 INTRODUCTION

• In cooperative tasks, agents must coordinate on one shared solution, and misaligned strategies can reduce performance.The paper calls collections of mutually compatible strategies “conventions.”Source: §1 · p. 1
• A new teammate may either infer the status quo or try to improve outcomes by changing the joint strategy, if others can adapt.The motivating example describes teams whose members have partially overlapping skills.Source: §1 · p. 1
• Prior approaches train a diverse partner population and then train a generalist to coordinate with any member, each effectively committed to a fixed convention.The generalist then acts as a follower expected to adapt to its partner.Source: §1 · pp. 1–2
• Existing generalists defer to a partner’s convention even when it is sub-optimal because they are trained only with fixed-convention partners.This leaves them without a mechanism to recognize when a partner could adapt to a higher-value convention.Source: §1 · p. 2
• ConventionPlay trains against partners with varying adaptability so agents can probe capabilities and steer toward the most effective convention the partner can follow.The approach discovers how a population partitions into conventions and uses that partition to build followers limited to restricted subsets.Source: §1 · p. 2

Population Diversity

• ConventionPlay leverages task solutions to train generalists for partners of varying proficiency and is compatible with existing diversity-generation techniques.Prior methods generate diverse solutions using self-play checkpoints, human data, trajectory diversity, entropy bonuses, or incompatible self-play policies.Source: §2 · p. 2
• TBS and SyKLRBR structure policy diversity hierarchically, but neither models the range of adaptive behaviors partners may exhibit.Source: §2 · p. 2

Convention-Free Strategies

• Zero-shot coordination methods avoid conventions, whereas ConventionPlay embraces conventions present in a population and targets uncertainty about which equilibrium a partner prefers.Other-Play seeks policies invariant to task symmetries, while Off-Belief Learning suppresses arbitrary conventions.Source: §2 · p. 2

Partner Shaping

• Unlike explicit influence-reward methods and learning-based partner-shaping approaches, ConventionPlay’s influence arises from best-response training against partners with latent capabilities.LOLA requires a predefined partner-learning model; M-FOS repeatedly interacts with a specific partner and resets its learning process.Source: §2 · pp. 2–3
• ConventionPlay assumes no specific partner-learning algorithm and probes a new partner with limited strategies to find a best response within one episode.It uses task structure to identify behaviors a partner may be capable of implementing.Source: §2 · p. 3

3 PRELIMINARIES

• The paper introduces formalisms for Dec-POMDPs, best responses to populations, and systems of conventions.Source: §3 · p. 3

3.1 DEC-POMDPS

• Experiments use symmetric, two-player Dec-POMDPs, where either individual policy can be executed by either agent and joint returns are symmetric.The tasks are fully cooperative, with agents sharing reward; the authors note no fundamental barrier to extending the approach beyond two agents.Source: §3.1 · p. 3

3.2 BEST-RESPONSE TRAINING

• Best-response training first builds a finite partner-policy population, then trains a policy to maximize expected joint return over uniformly sampled partners.PPO with recurrent LSTM networks lets the policy infer its partner’s strategy from interaction history; adapting online can cost reward against a specific partner compared with a specialized policy.Source: §3.2 · p. 3

3.3 CONVENTIONS

• A convention is a set of strategies that implement a compatible joint behavior, and conventions can overlap when adaptive policies implement multiple conventions.Compatibility is defined by return: compatible pairs achieve high joint return and incompatible pairs low return; the cross-play matrix records returns for every policy pair.Source: §3.3 · p. 4

4 DISCOVERING CONVENTIONS

• The approach partitions a finite policy population into conventions using algorithms based on its cross-play matrix.Source: §4 · p. 4

4.1 PARTITIONING INTO CONVENTIONS

• Spectral clustering groups policies by similar interaction profiles; the clustering requires the number of conventions as a hyperparameter.The method seeks clusters whose members achieve comparable returns with the same partners; the figure contrasts baseline diversity in K0 with ConventionPlay’s diversity among K1 agents, prompting K2 to infer partner capability.Source: §4.1 · p. 4, Figure 1 · p. 5
• The diagonal matrix-factorization formulation assumes convention compatibilities are independent and that policies following the same convention are mutually compatible.The authors note these assumptions may fail in tasks requiring distinct roles without an environmental signal, though their experimental tasks approximately satisfy them.Source: §4.1 · p. 5

4.2 CONVENTION-REBALANCED TRAINING

• Convention rebalancing samples a convention uniformly, then a policy uniformly within it, giving each convention equal training weight regardless of population frequency.This addresses possible skew when learned populations overrepresent common conventions; the method assumes test-time partners are equally likely to follow any convention.Source: §4.2 · p. 5

• ConventionPlay models target partners at levels 0 and 1 of a Cognitive Hierarchy and trains its final policy at level 2.Each level-k policy is a best response to a mixture of policies at lower levels.Source: §5 · p. 5
• K0 agents each follow one fixed convention, while the population as a whole represents multiple conventions; population-diversity methods train against K0 alone.Source: §5 · p. 6
• Unlike SyKLRBR’s best responses to the uniform distribution over the full K0 population, ConventionPlay models K1 partners with varying capabilities by restricting each to a subset of conventions.Source: §5 · p. 6
• Each K1 agent best-responds to policies sampled from conventions in its non-empty capability set, and the population uses sets larger than one but smaller than all conventions.This sampling creates partners that can adapt across some, but not all, conventions.Source: §5 · p. 6
• The level-2 policy trains against the union of fixed-convention and limited-capability partners, encouraging it to probe partners and steer toward a high-value convention they support.Source: §5 · p. 6

6.1 ENVIRONMENTS

• Each environment has uniform, partially differentiated, and fully differentiated payoff variants, testing coordination when conventions have equal or distinct returns.Source: §6.1 · p. 6, Figure 2 · p. 7
• In the Repeated Matrix Game, agents must match actions over 20 trials while observing a limited three-step history of their partner’s actions.Source: §6.1 · p. 6
• Point Mass Rendezvous requires agents to meet at one of six landmarks using sparse rewards; landmark rewards vary to create uniform or differentiated conventions.Source: §6.1 · pp. 6–7
• Task-Relay models two-agent manufacturing: agents apply tools to build an object, with labor allocation affecting idle time and five goal states representing distinct manufacturing sequences.Source: §6.1 · p. 7

6.2 EVALUATION PROTOCOL

• Evaluation includes convention-covering fixed partners, sampled limited-capability partners, and hand-coded heuristics; the latter may exhibit unseen behaviors or noise, testing out-of-distribution generalization.Source: §6.2 · p. 7
• Comparisons include FCP, SyKLRBR, MEP, LIPO, and CoMeDi, with both original CoMeDi (BC) and a best-response variant, CoMeDi (BR).Source: §6.2 · p. 7

7 RESULTS AND DISCUSSION

• The experiments validate convention discovery through rebalancing and evaluate a generalist K2 agent, using spectral clustering and matrix factorization.Results are reported as normalized reward and coordination efficiency.Source: §7 · p. 7

Convention Rebalancing

• Rebalancing a heavily imbalanced training population improves normalized return by up to 40% on a test population uniform over conventions.The experiment uses a matrix-game variant with unequal action-set sizes across conventions.Source: §7 · p. 8

Performance on Test Populations

• Across three environments and evaluation populations, ConventionPlay gains 10–50% against adaptive partners and loses 0–5% against fixed-convention partners under differentiated conventions, while matching baselines in non-differentiated settings.The comparison is reported for Tables 1, 2, and 7 and Figure 3.Source: §7 · p. 8, Figure 3 · p. 8
• Task-Relay shows the largest performance gap against P(1) heur partners, where agents can deadlock by waiting for the other to commit.ConventionPlay is designed to break this co-adaptation deadlock.Source: §7 · p. 9

Analysis of Probing

• Against a fixed partner committed to the lowest-value convention, ConventionPlay probes for 3–6 steps before converging, versus 1–3 steps for most baselines.The longer probing explains its modest reward cost against P(0).Source: §7 · p. 9, Figure 4 · p. 9

Performance on Test Populations

• As partner adaptivity increases, ConventionPlay increasingly outperforms baselines; at low adaptivity it matches the expected 0–5% performance drop.The evaluation varies how long partner policies adapt before committing to their last action.Source: §7 · p. 9

8 CONCLUSION AND FUTURE WORK

• ConventionPlay moves beyond purely reactive partner adaptation, and outperforms existing methods when partners can adapt across conventions.It does so by probing partner capabilities and steering teams toward high-value conventions.Source: §8 · p. 9
• Convention identification relies on cross-play returns, and evaluation covers relatively small convention populations.Scaling to many overlapping or complex convention structures remains an open question.Source: §8 · p. 9
• The authors report targeted AI assistance in software development, experiment debugging and hyperparameter suggestions, and grammar and language refinement.They state that AI-assisted work was heavily reviewed and revised.Source: AI USE STATEMENT · p. 10

A ENVIRONMENTS

• The environments section describes evaluation environments and how domain knowledge is used to construct P(0).Source: A ENVIRONMENTS · p. 12

A.1 REPEATED MATRIX GAME

• The repeated matrix game asks agents to match actions over 20 trials, with uniform and fully differentiated payoff variants.Agents observe their partner’s three most recent actions and choose among eight discrete actions per trial.Source: §A.1 · p. 12

A.2 POINT MASS RENDEZVOUS (PMR)

• Point Mass Rendezvous requires agents to meet at one of six landmarks using continuous 2D acceleration actions.Agents observe their own position and velocity, landmark distances, and their partner’s velocity.Source: §A.2 · p. 12

A.3 TASK-RELAY

• Task-Relay agents jointly build an object along one of five manufacturing paths, interleaving tool staging and object handling because only the holder can apply a tool.Switching tools takes time, so the agents must coordinate to avoid wasted time.Source: §A.3 · p. 12, Figure 5 · p. 13
• Evaluation partners support singleton or paired manufacturing-path repertoires, so optimal scoring requires identifying which line or lines the partner can follow.The hard-coded partner does not initiate or contest its partner’s line choice, but can competently collaborate on a supported path.Source: §A.3 · p. 13

B.1 CHOICE OF BASELINES

• The comparison includes FCP, SyKLRBR, MEP, LIPO, and CoMeDi, with CoMeDi evaluated as both behavior-cloning and best-response variants.The CoMeDi (BR) variant isolates population diversity from the method used to leverage it for ad-hoc collaboration.Source: §B.1 · pp. 13–14

B.2 SELF-PLAY AND BEST-RESPONSE HYPERPARAMETERS

• Tables 3 and 4 report self-play and best-response hyperparameters by environment family.Source: Table 3 · p. 14, Table 4 · p. 15

B.3 BASELINE POPULATION PARAMETERS

• Tables 5 and 6 report method-specific K0 population sizes and shared K1 evaluation-population sizes, alongside the convention-count setting q.Source: Table 5 · p. 15, Table 6 · p. 15, §B.3 · p. 15

C.1 K0 POPULATION CONSTRUCTION

• The K0 population is trained with independent PPO runs across random seeds; random initialization provided behavioral diversity but does not guarantee well-structured incompatible policies.The authors empirically verify inter-convention incompatibility before using the population in later training.Source: §C.1 · pp. 15–16

C EXPERIMENT IMPLEMENTATION DETAILS

• ConventionPlay’s three stages are to generate and partition K0 agents, train diverse K1 agents with sampled convention capability sets, and train a K2 best response.Source: C EXPERIMENT IMPLEMENTATION DETAILS · p. 15, §C.1 · p. 16

C.2 CONVENTION PARTITIONING

• Spectral clustering clusters normalized cross-play features with an RBF affinity, while matrix factorization learns convention assignments by reconstructing the cross-play matrix.Matrix factorization anneals its softmax temperature from 1.0 to 0.01; the expected convention count q is set using domain knowledge.Source: §C.2 · p. 16

C.3 K1 POPULATION CONSTRUCTION

• K1 capability sets are sampled from smaller to larger sizes, giving the later K2 agent partners with varying degrees of adaptability.Sets satisfy 1 < |Kj| < q, ranging from two conventions to nearly all conventions.Source: §C.3 · p. 16
• Each K1 training population samples the same number of policies from every convention in its capability set, but K0 policies can be unevenly represented across the full K1 population.Source: §C.3 · p. 16
• Figure 6 summarizes K0 cross-play structure, K1 subset sampling and capability variation, and the frequency of K0 policies across K1 training distributions.Source: Figure 6 · p. 17, §C.3 · p. 17

D.1 CONVENTION-REBALANCED TRAINING

• The test setup gives all four equally rewarding conventions different discovery difficulty, with compatible-action counts of 1, 1, 2, and 6; self-play overrepresents easier-to-find conventions.The test population is uniform over convention labels.Source: §D.1 · p. 17, Figure 7 · p. 18
• 40% improvement in return over the naive baseline is achieved by spectral-clustering and k-means rebalancing on the uniform P(0) test population.Figure 8 compares partner-sampling marginals and normalized episodic return across the rebalancing schemes.Source: §D.1 · pp. 17–18, Figure 8 · p. 18
• All three rebalancing methods improve over the unrebalanced baseline across tested q values, peak at the correct q, and degrade when q is underspecified.Matrix factorization is more resilient to overspecifying q; Figure 9 reports normalized returns across q values.Source: §D.1 · p. 18, Figure 9 · p. 19

D.2 NORMALIZED RETURN

• Normalized return is measured against each environment’s known reward range, while the reference maximum averages each test partner’s empirically computed achievable best response.Table 7 reports mean normalized episodic return on P(1).Source: §D.2 · pp. 18–19, Table 7 · p. 19

D.3 COORDINATION EFFICIENCY

• Coordination Efficiency η normalizes an agent’s return by its partner’s achievable maximum, allowing comparison when partners have different attainable returns.For K1 partners, the maximum is restricted to policies from conventions in the partner’s repertoire.Source: §D.3 · pp. 19–20
• Tables 8–10 report coordination efficiency on P(0) and P(1), with cells summarized as mean ± 1 standard deviation across five seeds.Source: Table 8 · p. 20, Table 9 · p. 20, Table 10 · p. 20

D.4 ANALYSIS OF PROBING IN PMR

• ConventionPlay’s winding PMR trajectories reflect probing toward a higher-value landmark to induce adaptation, while supporting leadership with adaptive partners and following fixed-convention partners.The comparison shows FCP inferring a partner’s initially preferred convention and coordinating accordingly.Source: §D.4 · p. 20, Figure 10 · p. 21

D.5 EFFECT OF K1 POPULATION SIZE

• The K1 inflection point varies by environment and convention-discovery method, and interactions between these choices remain for further analysis.The reported pattern suggests diminishing returns beyond a moderate K1 population size.Source: §D.5 · p. 20
• ConventionPlay’s coordination efficiency gains are substantial up to moderate K1 diversity, then diminish; FCP is invariant to K1 size.Figure 11 shows the relationship, with error bars of ±1 sample standard deviation across seeds’ mean efficiency over test partners.Source: Figure 11 · p. 21, §D.5 · p. 21