Open Ad Hoc Teamwork using Graph-based Policy Learning

Arrasy Rahman, Niklas Höpner, Filippos Christianos, Stefano V. Albrecht

Abstract

Ad hoc teamwork (AHT) requires autonomous agents to collaborate with unknown teammates without prior coordination. Traditional AHT research often assumes a fixed team size, whereas real-world scenarios are frequently "open," with agents joining or leaving dynamically. This paper introduces Graph-based Policy Learning (GPL), a framework that combines Graph Neural Networks (GNNs) with factorized joint-action value models. GPL enables agents to effectively credit teammate contributions and generalize to varying team sizes. Experimental results across multiple environments demonstrate that GPL outperforms state-of-the-art baselines in both training efficiency and zero-shot generalization to larger teams.

Introduction

The challenge of ad hoc teamwork lies in designing agents capable of collaborating "on the fly" with previously unknown partners. While most existing work focuses on closed teams, real-world applications—such as autonomous vehicles in traffic or warehouse robotics—operate in open environments where the number of participants fluctuates.

Open ad hoc teamwork presents three primary difficulties: unknown teammate policies, dynamic roles necessitated by changing team sizes, and variable input dimensions that break standard reinforcement learning (RL) models. To address these, we propose Graph-based Policy Learning (GPL), which treats the team as a dynamic graph, allowing for flexible input handling and sophisticated coordination modeling.

Methodology

The GPL architecture is built upon three integrated pillars designed to handle the complexities of open teamwork:

  1. Type Inference: Since teammate strategies are unknown, the learner utilizes LSTMs to process historical observations, generating a "type embedding" for each agent.
  2. Agent Modeling: A GNN-based Relational Forward Model predicts the likely future actions of teammates based on their inferred type embeddings.
  3. Joint-Action Value Estimation: The framework employs a Coordination Graph (CG) to model a joint-action value function, factorized into individual utility terms and pairwise interaction terms.
The GPL architecture integrates type inference, agent modeling, and joint-action value estimation to handle open teams.

The core innovation of GPL is its ability to select actions by marginalizing out teammate actions. By weighting the joint-action value model with probabilities from the agent model, the learner can disentangle its own contributions from those of its teammates, facilitating better credit assignment.

Experiments and Results

GPL was evaluated in three distinct multi-agent environments: Level-Based Foraging (LBF), Wolfpack, and FortAttack. In each scenario, an "open process" was simulated where agents were added or removed dynamically.

GPL was compared against several baselines, including standard Q-Learning, GNN-based RL, and MARL algorithms such as MADDPG and DGN.

Training performance of GPL compared to baselines across Level-based Foraging, Wolfpack, and FortAttack.

Key Findings

  • Superior Training Performance: GPL achieved higher returns and faster convergence than all baselines, particularly in the complex FortAttack environment.
  • Robust Generalization: GPL demonstrated remarkable zero-shot generalization. When trained on teams of 3 agents and tested on teams of 5, GPL maintained high performance while baseline models often failed. For instance, in LBF, GPL achieved a score of ~2.40 versus the best baseline's ~1.80.
  • Emergent Coordination: In FortAttack, the model learned to position itself strategically to drive enemies into teammates' shooting ranges, demonstrating a high level of emergent coordination derived from its pairwise utility modeling.

Discussion and Conclusion

GPL's success stems from its use of GNNs as a "universal interface" for variable team sizes and its explicit modeling of joint actions for disentangled credit assignment. While the current framework assumes full observability, it provides a strong foundation for future work in partially observable environments and continuous action spaces. By treating teamwork as a dynamic graph problem, GPL offers a scalable and robust solution for the challenges of open ad hoc collaboration.

Summary updated

BibTeX
@inproceedings{rahman2021open,
  author = {Arrasy Rahman and Niklas Höpner and Filippos Christianos and Stefano V. Albrecht},
  title = {{Open Ad Hoc Teamwork using Graph-based Policy Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=DvysihI1NF},
}
Figure