Artificially intelligent agents deployed in the real world must be able to reliably cooperate with humans (as well as other, heterogeneous AI agents). To provide formal guarantees of successful cooperation, we must make some assumptions about how these partner agents could plausibly behave. Realistic assumptions must account for the fact that other agents may be just as adaptable as our agent is. In this work, we consider the setting where an AI agent must cooperate with members of some target population of agents in a finitely repeated two-player general-sum game, where individual utilities are private. Two natural assumptions in this setting are 1) all agents in the target population are individually rational learners, and 2) when paired with another member of the population, with high-probability the agents will achieve the same expected utility as they would under some Pareto-efficient equilibrium strategy of the underlying stage game. Our theoretical results show that these assumptions alone are insufficient to select an AI strategy that achieves zero-shot cooperation with members of the target population. We therefore consider the problem of learning such a cooperation strategy using observations of members of the target population interacting with one another, and provide upper bounds on the sample complexity of learning such a cooperation strategy. Our main result shows that, under the above assumptions, these bounds can be much stronger than those arising from a “naive” reduction of the problem to one of imitation learning.

Coevolving teams of agents promises effective solutions for many coordination tasks such as search and rescue missions or deep ocean exploration. Good team performance in such domains generally relies on agents discovering complex joint policies, which is particularly difficult when the fitness functions are sparse (where many joint policies return the same or even zero fitness values). In this paper, we introduce Novelty Seeking Multiagent Evolutionary Reinforcement Learning (NS-MERL), which enables agents to more efficiently explore their joint strategy space. The key insight of NS-MERL is to promote good exploratory behaviors for individual agents using a dense, novelty-based fitness function. Though the overall team-level performance is still evaluated via a sparse fitness function, agents using NS-MERL more efficiently explore their joint action space and more readily discover good joint policies. Our results in complex coordination tasks show that teams of agents trained with NS-MERL perform significantly better than agents trained solely with task-specific fitnesses.

Learning to cooperate with other agents is challenging when those agents also possess the ability to adapt to our own behavior. Practical and theoretical approaches to learning in cooperative settings typically assume that other agents' behaviors are stationary, or else make very specific assumptions about other agents' learning processes. The goal of this work is to understand whether we can reliably learn to cooperate with other agents without such restrictive assumptions, which are unlikely to hold in real-world applications. Our main contribution is a set of impossibility results, which show that no learning algorithm can reliably learn to cooperate with all possible adaptive partners in a repeated matrix game, even if that partner is guaranteed to cooperate with some stationary strategy. Motivated by these results, we then discuss potential alternative assumptions which capture the idea that an adaptive partner will only adapt rationally to our behavior.