Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Minimum Coverage Sets for Training Robust Ad Hoc Teamwork Agents
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes L-BRDiv, which jointly approximates the minimum coverage set of a cooperative environment and generates training teammate policies via a Lagrangian-constrained optimization, yielding more robust ad hoc teamwork agents than BRDiv and LIPO.
Problem
Ad hoc teamwork agents must cooperate robustly with unseen partners, but heuristic adversarial-diversity metrics used to generate training teammates do not always maximize robustness and can yield self-sabotaging teammates.
Approach
Argues that robust AHT agents should emulate the minimum coverage set (set of best-response policies to any partner policy) and introduces L-BRDiv, which learns Lagrange multipliers over constraints so teammate policies cover distinct MCS members without hand-tuning the diversity weight alpha.
Key results
- L-BRDiv significantly outperforms BRDiv and LIPO in the repeated matrix game, Weighted Cooperative Reaching, and Level-based Foraging in returns against unseen heuristic teammates.
- In the Repeated Matrix Game, L-BRDiv consistently discovers all three deterministic MCS members, whereas baselines find only two.
- In Cooperative Reaching, BRDiv slightly outperforms L-BRDiv, though the difference is only marginally significant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Lagrangian-optimized diversity weights with constrained MCS approximation (L-BRDiv) instead of heuristic adversarial diversity | teammate generation for AHT training · Repeated Matrix Game, Weighted Cooperative Reaching, Level-based Foraging | AHT agent robustness (episodic return vs unseen teammates) | Helped |
| L-BRDiv instead of BRDiv | teammate generation for AHT training · Cooperative Reaching | AHT agent episodic return | Hurt |
| Learned Lagrange multipliers instead of fixed cross-play weight alpha (BRDiv/LIPO need tuning) | teammate generation · Repeated Matrix Game | number of MCS members discovered | Helped |
| Adversarial diversity objectives (BRDiv, LIPO) with any constant uniform alpha (ablation) | teammate generation · Repeated Matrix Game and Weighted Cooperative Reaching | whether MCS members are preferred by diversity objective | Hurt |
| Using L-BRDiv's constrained objective with near-zero tolerance tau in MCS approximation | L-BRDiv teammate generation · Cooperative Reaching | BR policies quality against AHT partners | Hurt |
| Self-sabotage not filtered during teammate generation (no ADVERSITY-style prevention) | teammate generation · general | qualitative | No clear effect |
Surprising findings
- No constant alpha > 0 lets BRDiv or LIPO's diversity objective prefer the full MCS over an alternative policy set in the Repeated Matrix Game and Weighted Cooperative Reaching.
- LIPO and L-BRDiv generate suboptimal MCS-member teammates in Cooperative Reaching compared to BRDiv's counterparts.
Limitations
- Evaluated only in two-player cooperative environments with small heuristic evaluation teammate sets.
- Requires knowing or estimating a finite coverage set and a fixed K for the number of policies.
- Computational cost scales as K^2 forward passes per experience.
Experimental setup
Datasets: Repeated Matrix Game Cooperative Reaching Weighted Cooperative Reaching Level-based Foraging
Benchmarks: Repeated Matrix Game Cooperative Reaching Weighted Cooperative Reaching Level-based Foraging
Metrics: average episodic returns with heuristic evaluation teammates 95% confidence interval across four seeds number of MCS members discovered
Baselines: BRDiv LIPO
Builds on: BRDiv LIPO MAPPO RL^2
Closest papers by meaning
- ROTATE: Regret-driven Open-ended Training for Ad Hoc Teamwork (NeurIPS 2026 · similarity 0.90)
- N-agent Ad Hoc Teamwork (NeurIPS 2024 · similarity 0.88)
- Ad Hoc Teamwork via Offline Goal-Based Decision Transformers (ICML 2025 · similarity 0.88)
- Open Ad Hoc Teamwork with Cooperative Game Theory (ICML 2024 · similarity 0.87)
- Diversity Is Not All You Need: Training A Robust Cooperative Agent Needs Specialist Partners (NeurIPS 2024 · similarity 0.87)
- LLM-Assisted Semantically Diverse Teammate Generation for Efficient Multi-agent Coordination (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.