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

AI summary

Overview

• Research area: Multi-agent reinforcement learning, specifically ad-hoc teamwork and zero-shot coordination.
• Technical level: Advanced. The paper assumes familiarity with Dec-POMDPs, best-response training, PPO, cognitive hierarchy models, and cross-play matrices.
• Scope: The paper introduces ConventionPlay, a training pipeline that builds a three-level population of agents (fixed-convention, capability-limited adaptive, and robust collaborator) to produce an agent that probes a new partner's capabilities and steers the team toward the best convention that partner can actually follow.
• Paper metadata: arXiv:2610.11842v1 [cs.MA], 08 Oct 2026, licensed CC BY 4.0. Authors: Abhishek Sriraman, Eleni Vasilaki (Sheffield, UK), Robert Loftin (Pittsburgh, PA 15213, USA).

What This Paper Is About

Many cooperative tasks can be solved in several equally valid ways, and teams succeed only if everyone commits to the same one. Prior ad-hoc collaboration methods train an agent to be a pure "follower" that detects whatever convention an unseen partner is using and immediately adapts to it, even when a better joint strategy exists. ConventionPlay instead trains an agent that treats partners as varying in ability: some can only follow one convention, while others could adopt several, and the agent must figure out which case it faces and, where possible, steer the team toward the higher-value convention.

Key Contributions

1. A formalization of "systems of conventions" as collections of policy subsets over a policy space, plus two algorithms for discovering them from a population's cross-play matrix: spectral clustering over interaction profiles, and low-rank matrix factorization of the form X ≈ Z W Zᵀ with a diagonal W capturing per-convention returns.
2. Convention-rebalanced training, which corrects for skew in a learned population by first sampling a convention uniformly and then sampling a policy within it, giving every convention equal weight regardless of how often it appears in the training population.
3. The ConventionPlay pipeline itself, a cognitive-hierarchy variant in which K0 agents are fixed-convention self-play policies, K1 agents are best-responses to restricted capability sets (non-empty subsets of conventions, with size constrained to 1 < |K_i| < |C|), and the final K2 agent trains against the union of both.
4. An empirical demonstration across three environments and three payoff structures showing that the probing-and-steering behavior induced by capability-limited K1 partners yields gains against adaptive partners that baselines do not achieve.

Main Findings

• Convention rebalancing corrects skewed training populations: On a matrix game variant where unequal action-set sizes cause K0 training to yield a heavily imbalanced population, training on the rebalanced population improved normalized return by a margin of up to 40% against a test population that is uniform over conventions.
• ConventionPlay trades a small cost against rigid partners for a large gain against adaptive ones: Under differentiated payoffs, the paper reports both a 10–50% gain against adaptive partners and a modest 0–5% reduction against fixed-convention partners relative to baselines.
• Non-differentiated settings are uninformative: When all conventions have equal value, ConventionPlay and baselines reach parity, because convergence on any shared convention is equally good.
• Adaptive partners are where the gap opens (Table 2, 𝒫_sampled^(1), full differentiation, n = 5 seeds): Matrix Game — ConvPlay spectral 52.63 ± 0.41 and matfact 51.52 ± 1.37, versus FCP 24.03 ± 1.31. PMR — ConvPlay spectral 66.11 ± 1.28 and matfact 65.54 ± 1.41, versus FCP 53.73 ± 5.81. Task-Relay — ConvPlay spectral 53.66 ± 8.03, versus FCP 14.45 ± 23.57.
• Against fixed-convention partners, the advantage narrows or reverses (Table 1, 𝒫_test^(0), full differentiation): Matrix Game — FCP 37.44 ± 0.06 versus ConvPlay matfact 36.35 ± 0.44 and spectral 36.56 ± 0.57. PMR — ConvPlay spectral 60.58 ± 0.11 leads, with FCP at 56.49 ± 6.22. Task-Relay — ConvPlay spectral 44.70 ± 4.44 leads, with SyKLRBR (L5) at 44.26 ± 4.43.
• Probing is directly observable: Analyzing Matrix Game trajectories under fully differentiated payoffs with a partner committed to the lowest-value convention, most baselines converge to the partner's convention within 1–3 time steps, whereas ConventionPlay probes for 3–6 time steps before converging. This explains the modest reward cost against 𝒫_test^(0).
• Performance scales with partner adaptivity: Using a modified 𝒫_sampled^(1) in which partners act for a fixed number of steps before committing, ConventionPlay matches the expected 0–5% drop at low adaptivity (where the partner behaves effectively like a K0 agent) and increasingly outperforms all baselines as adaptivity rises.
• Task-Relay is the hardest case for baselines: The paper attributes this to a co-adaptation deadlock, where each agent repeats non-committal actions waiting for the other to commit — the dynamic ConventionPlay is designed to break.
• Both discovery methods work, with differences by setting: Spectral clustering and matrix factorization are evaluated throughout; spectral produced the best full-differentiation scores in PMR and Task-Relay on both 𝒫_test^(0) and 𝒫_sampled^(1), while matrix factorization was competitive in the Matrix Game. Results for the third evaluation population (𝒫_heur^(1), hand-coded heuristic limited-capability agents) are reported as Table 7 in the paper.
• Evaluation scale and protocol: Each cell reports mean ± 1 s.d. (unbiased sample standard deviation, n − 1 denominator) across n = 5 seeds; all test populations are constructed independently of any training population, so performance against them reflects out-of-distribution generalization.
• Baselines compared: FCP, SyKLRBR at both five levels (L5) and a two-level hierarchy (L2) grounded in the learned K0 population, CoMeDi in original (BC) and best-response (BR) variants, LIPO, and MEP.

Methodology in Plain English

The approach proceeds in stages.

Model the task. Each coordination task is written as a symmetric, two-player Dec-POMDP, meaning both agents share the same action and observation spaces and swapping the two agents does not change the joint return.

Train a diverse starting population. A set of policies is trained in self-play (using PPO with recurrent LSTM networks so agents can infer a partner's strategy from interaction history). These are the K0 agents: each is locked into one convention.

Find the conventions. The population is played against itself to build a cross-play matrix, where entry (i, j) is the return of policy i paired with policy j. Two methods then partition policies: spectral clustering of rows (each row being a policy's "interaction profile"), and matrix factorization that reconstructs the cross-play matrix from soft membership weights and per-convention returns. Both require choosing the number of conventions q, which the paper says can be set via eigengap analysis, silhouette analysis, or domain knowledge.

Rebalance the training distribution. Instead of sampling partners from the empirical population, sample a convention uniformly first, then a policy within it, so no convention is under- or over-represented.

Build capability-limited partners. For each K1 agent, randomly sample a capability set — a subset of conventions strictly smaller than the full set, and larger than one. Collect a training population by drawing policies from those conventions and train the agent as a best-response to that restricted population. This is the key structural move: these partners can adapt, but only within limits.

Train the final agent. The K2 agent is trained as a best-response to the union of K0 and K1 partners. Because some partners can move to a better convention and some cannot, the agent must interact to find out — it has to probe, then either steer or defer.

Evaluate on three unseen populations. A convention-covering population of fixed partners, a sampled adaptive population built from the same capability-set procedure but using ground-truth labels, and hand-coded heuristic agents implementing limited-capability behavior directly.

Why This Matters

Impact on research. Most ad-hoc collaboration work treats the partner as either a fixed-strategy leader or an unknown black box to be adapted to. This paper argues that the more realistic assumption is partners with partial adaptability, and shows that injecting that structure into the training population produces qualitatively different, non-reactive behavior. It also separates the problem of discovering diverse solutions (which many existing methods handle) from the problem of training against them, explicitly noting that ConventionPlay is compatible with any diversity-generation technique. The paper also frames its method against zero-shot coordination approaches like Other-Play and Off-Belief Learning, arguing that avoiding conventions is unrealistic for human-AI interaction and that conventions should be embraced instead.

Real-world applications.

• Kitchens, mechanic shops, and sports teams, the paper's own motivating examples, where teammates share partially overlapping skills and must decide whether to fit the established routine or reorganize the work.
• Industrial manufacturing, directly modeled by the Task-Relay environment, where two agents build an object by switching tools and optimal policies try to minimize idling time.
• Human-AI teaming in assistive and service settings, where a deployed agent must decide whether a human counterpart can be pushed toward a more efficient joint routine or will only follow one.
• Multi-robot spatial coordination, as in Point Mass Rendezvous, where robots must commit to a meeting location under sparse reward.
• Autonomous driving conventions (driving on one side of the road, the paper's illustrative example), where the standard convention may vary by region or population.

Industry relevance. Any deployed system that must cooperate with partners it was not trained with — warehouse fleets, surgical or manufacturing assistants, game AI that teams with human players — faces the leader-versus-follower question this paper formalizes. The result that actively probing costs only 0–5% against rigid partners while yielding 10–50% against adaptive ones is a concrete argument that pure deference is a losing default.

Future Directions

• Richer convention signals. The authors identify reliance on cross-play returns as a primary limitation and suggest that state-action trajectories or policy similarity measures could give more nuanced representations of agent capability, improving how capability-limited K1 training sets are built.
• Scaling convention complexity. Evaluation covers relatively small populations of conventions; scaling to environments with many overlapping or complex convention structures remains, in the authors' words, an open question.
• Beyond two agents and beyond symmetric games. The method is developed in symmetric two-player Dec-POMDPs, though the authors state that any asymmetric two-agent Dec-POMDP can be made symmetric by assigning roles and letting policies condition on them, and that they see no fundamental barrier to extending to larger numbers of agents.
• Tasks that violate the factorization assumptions. The diagonal-W factorization encodes that a policy's compatibility with one convention is independent of another, and that any two same-convention agents are compatible. The authors note tasks where each player must take a distinct role fall outside these assumptions, even though their experimental tasks approximately satisfy them.
• K1 population sizing. The paper notes that the effect of K1 population size on ConventionPlay is studied in Appendix D.5 — a design question left as an experimental parameter rather than a fixed recipe.

Target Audience

This paper is aimed at multi-agent reinforcement learning researchers working on ad-hoc teamwork, zero-shot coordination, and population-based training, and at practitioners building agents that must cooperate with unfamiliar human or artificial partners. It is also relevant to cognitive-hierarchy and game-theory-adjacent researchers, since it adapts the level-k cognitive hierarchy model to a deep RL pipeline. Readers without a background in Dec-POMDPs and best-response training will find the formal sections dense, though the motivation and the experimental narrative are accessible without following the equations.

Authors’ abstract

Ad-hoc collaboration often requires agents to identify and adhere to some shared convention within a cooperative task. Existing work on reinforcement learning (RL) for ad-hoc collaboration focuses on training agents that adapt to the conventions established by their partners. These methods fail to consider the possibility that while some partners might follow only a single fixed convention, others may themselves be capable of adapting to multiple conventions. Here we present ConventionPlay, an RL-based approach that teaches agents to discover their partner's optimal convention by training against a learned population of partners that exhibit different degrees of adaptability across conventions. Some of these partners follow a single, fixed convention, while others are able to adapt to a subset of the possible conventions for the task in question. The existence of partners that support a limited subset of conventions forces agents trained against this population to actively probe their partner's capabilities, and steer their partner towards the most effective joint strategy that they are capable of following. Our experimental results demonstrate that agents trained via ConventionPlay achieve superior performance to existing ad-hoc collaboration methods against test populations of partners that are compatible with multiple conventions.