On the Complexity of Learning to Cooperate in Populations of Socially Rational Agents

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.