# Minimum Coverage Sets for Training Robust Ad Hoc Teamwork Agents

arXiv: https://arxiv.org/abs/2308.09595 · HTML: https://mlsanity.com/paper/2308.09595/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 28 references that are in the map.
- First posted on arXiv 18 Aug 2023.

## Builds on (most cited first, 14 of 14)

- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [RL2: Fast Reinforcement Learning via Slow Reinforcement Learning](https://mlsanity.com/paper/1611.02779/) (2016)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [The Hanabi Challenge: A New Frontier for AI Research](https://mlsanity.com/paper/1902.00506/) (2019)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [Shared Experience Actor-Critic for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.07169/) (2020)
- [Agent Modelling under Partial Observability for Deep Reinforcement Learning](https://mlsanity.com/paper/2006.09447/) (2020)
- [Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning](https://mlsanity.com/paper/2210.05492/) (2022)
- [A Survey of Ad Hoc Teamwork Research](https://mlsanity.com/paper/2202.10450/) (2022)
- [Towards Open Ad Hoc Teamwork Using Graph-based Policy Learning](https://mlsanity.com/paper/2006.10412/) (2020)
- [Deep Interactive Bayesian Reinforcement Learning via Meta-Learning](https://mlsanity.com/paper/2101.03864/) (2021)
- [Generating Teammates for Training Robust Ad Hoc Teamwork Agents via Best-Response Diversity](https://mlsanity.com/paper/2207.14138/) (2022)

## Built on by (most cited first, 13 of 13)

- [ZSC-Eval: An Evaluation Toolkit and Benchmark for Multi-agent Zero-shot Coordination](https://mlsanity.com/paper/2310.05208/) (2023)
- [Seven Security Challenges in Cross-domain Multi-agent LLM Systems](https://mlsanity.com/paper/2505.23847/) (2025)
- [ROTATE: Regret-driven Open-ended Training for Ad Hoc Teamwork](https://mlsanity.com/paper/2505.23686/) (2025)
- [Improving Human-AI Coordination through Online Adversarial Training and Generative Models](https://mlsanity.com/paper/2504.15457/) (2025)
- [Quantifying Agent Interaction in Multi-agent Reinforcement Learning for Cost-efficient Generalization](https://mlsanity.com/paper/2310.07218/) (2023)
- [Symmetry-Breaking Augmentations for Ad Hoc Teamwork](https://mlsanity.com/paper/2402.09984/) (2024)
- [Benchmarking the Limits of In-Context Reinforcement Learning for Ad-Hoc Teamwork](https://mlsanity.com/paper/2605.24423/) (2026)
- [Seldonian Reinforcement Learning for Ad Hoc Teamwork](https://mlsanity.com/paper/2503.03885/) (2025)
- [Efficient Generation of Diverse Cooperative Agents with World Models](https://mlsanity.com/paper/2506.07450/) (2025)
- [JaxAHT: A JAX-Based Library for Ad Hoc Teamwork](https://mlsanity.com/paper/2609.13716/) (2026)
- [On the Complexity of Learning to Cooperate with Populations of Socially Rational Agents](https://mlsanity.com/paper/2407.00419/) (2024)
- [Assistax: A Multi-Agent Hardware-Accelerated Reinforcement Learning Benchmark for Assistive Robotics](https://mlsanity.com/paper/2507.21638/) (2025)
- [Learning When to Cooperate Under Heterogeneous Goals](https://mlsanity.com/paper/2603.07253/) (2026)

## Abstract (arXiv)

Robustly cooperating with unseen agents and human partners presents significant challenges due to the diverse cooperative conventions these partners may adopt. Existing Ad Hoc Teamwork (AHT) methods address this challenge by training an agent with a population of diverse teammate policies obtained through maximizing specific diversity metrics. However, prior heuristic-based diversity metrics do not always maximize the agent's robustness in all cooperative problems. In this work, we first propose that maximizing an AHT agent's robustness requires it to emulate policies in the minimum coverage set (MCS), the set of best-response policies to any partner policies in the environment. We then introduce the L-BRDiv algorithm that generates a set of teammate policies that, when used for AHT training, encourage agents to emulate policies from the MCS. L-BRDiv works by solving a constrained optimization problem to jointly train teammate policies for AHT training and approximating AHT agent policies that are members of the MCS. We empirically demonstrate that L-BRDiv produces more robust AHT agents than state-of-the-art methods in a broader range of two-player cooperative problems without the need for extensive hyperparameter tuning for its objectives. Our study shows that L-BRDiv outperforms the baseline methods by prioritizing discovering distinct members of the MCS instead of repeatedly finding redundant policies.