Introduction
Ad Hoc Teamwork (AHT) presents a significant challenge in multi-agent reinforcement learning: an agent must collaborate effectively with a teammate whose behavior and "conventions" are unknown a priori. For instance, in a driving scenario, a teammate might follow the convention of driving on the left or the right. To achieve robustness, agents are typically trained against a diverse population of generated teammates. However, existing methods often rely on heuristic diversity metrics that can lead to "self-sabotaging" teammates or fail to capture essential cooperative conventions. This work introduces a theoretically grounded framework based on the Minimum Coverage Set (MCS) and a novel algorithm, L-BRDiv, to address these limitations.
The Minimum Coverage Set (MCS)
The core contribution of this research is the formalization of the Minimum Coverage Set (MCS). An MCS represents the smallest possible set of policies such that for any potential teammate policy within an environment, there exists a "best response" within the set.
By training an agent to emulate every policy in the MCS, it becomes theoretically prepared to coordinate with any teammate, regardless of the specific convention they follow. This shifts the focus from arbitrary "diversity" to "coverage" of the strategic space.
L-BRDiv: Lagrangian Best Response Diversity
To practically identify the MCS and train robust agents, the authors propose L-BRDiv (Lagrangian Best Response Diversity). Unlike previous approaches that require manual tuning of diversity weights—a process that is often tedious and environment-specific—L-BRDiv treats these weights as Lagrange multipliers.
The algorithm solves a constrained optimization problem, aiming to maximize returns with a designated partner while ensuring that each generated policy pair represents a distinct, non-redundant cooperative convention. By utilizing Multi-Agent PPO (MAPPO) for the underlying policy networks, L-BRDiv automatically balances the trade-off between diversity and performance, effectively pushing the search toward undiscovered members of the MCS.
Experimental Evaluation
The robustness of L-BRDiv was evaluated across four diverse cooperative environments:
- Repeated Matrix Game: A fundamental test of coordination with three distinct optimal conventions.
- Cooperative Reaching: A grid-world task requiring coordination to reach specific targets.
- Weighted Cooperative Reaching: A complex grid-world where agents must adapt to a partner's reward preferences.
- Level-based Foraging (LBF): A standard benchmark involving the collection of items with varying difficulty.
In these tests, L-BRDiv significantly outperformed state-of-the-art baselines such as BRDiv and LIPO. Notably, in the Matrix Game, L-BRDiv consistently identified all three optimal conventions, whereas baselines often missed one. In LBF, it discovered a wider array of distinct cooperative strategies, leading to superior performance against unseen heuristic teammates.
Key Insights and Conclusion
The research highlights that coverage of the best-response space is more critical for robustness than simple heuristic diversity. By focusing on best-response relationships, L-BRDiv avoids the "self-sabotage" trap where training partners become intentionally poor performers to satisfy diversity scores. Furthermore, the automated tuning provided by the Lagrangian formulation makes the algorithm more efficient and easier to deploy across different domains.
Future work will look to scale these concepts to teams larger than two agents and explore the application of MCS to competitive or general-sum games, potentially leading to more robust AI opponents in complex, multi-interest environments.
Summary updated