Beyond Fixed Coordination Graphs: Learning Interaction Topologies in Open Ad Hoc Teamwork

In ad hoc teamwork, the goal is to enable an autonomous agent to collaborate with other unknown agents without prior coordination or joint training. We study an open-environment variant of ad hoc teamwork in which agents with fixed policies can enter and exit the system at any time. Modeling multi-agent interaction is central to this problem, and prior coordination-graph methods rely on fixed topologies — dense complete graphs or sparse structures such as star graphs — often paired with cooperative-specific regularizers. These structural priors are efficient within the setting they are designed for, but degrade sharply outside it: dense fixed topologies accumulate noise as team size grows, while cooperative regularizers break down in the presence of adversarial agents. We introduce a dynamic, attention-based approach to model multi-agent interaction that requires no structural inductive bias or domain-specific regularizer, and whose learned interaction weights yield an interpretable coordination graph. We evaluate our method on both purely cooperative and mixed cooperative-competitive environments: it matches or exceeds the baselines on different benchmark problems, remains the only method that is competitive across both and scales substantially better as team size grows in the presence of adversarial agents. Our method is also highly robust to behavioral uncertainty, achieving substantial improvements in zero-shot generalization to unseen teammate policy distributions and team sizes.