# On the Complexity of Learning to Cooperate with Populations of Socially Rational Agents

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 29 Jun 2024.

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

- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [A Survey of Ad Hoc Teamwork Research](https://mlsanity.com/paper/2202.10450/) (2022)
- [A New Formalism, Method and Open Issues for Zero-Shot Coordination](https://mlsanity.com/paper/2106.06613/) (2021)
- [K-level Reasoning for Zero-Shot Coordination in Hanabi](https://mlsanity.com/paper/2207.07166/) (2022)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Imitation Learning by Reinforcement Learning](https://mlsanity.com/paper/2108.04763/) (2021)
- [Minimum Coverage Sets for Training Robust Ad Hoc Teamwork Agents](https://mlsanity.com/paper/2308.09595/) (2023)
- [On-the-fly Strategy Adaptation for ad-hoc Agent Coordination](https://mlsanity.com/paper/2203.08015/) (2022)
- [On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games](https://mlsanity.com/paper/2206.10614/) (2022)
- [Towards a Unifying Model of Rationality in Multiagent Systems](https://mlsanity.com/paper/2305.18071/) (2023)

## Abstract (arXiv)

Artificially intelligent agents deployed in the real-world will require the ability to reliably textitcooperate with humans (as well as other, heterogeneous AI agents). To provide formal guarantees of successful cooperation, we must make some assumptions about how partner agents could plausibly behave. Any realistic set of assumptions must account for the fact that other agents may be just as adaptable as our agent is. In this work, we consider the problem of cooperating with a textitpopulation of agents in a finitely-repeated, two player general-sum matrix game with private utilities. Two natural assumptions in such settings are that: 1) all agents in the population are individually rational learners, and 2) when any two members of the population are paired together, with high-probability they will achieve at least the same utility as they would under some Pareto efficient equilibrium strategy. Our results first show that these assumptions alone are insufficient to ensure textitzero-shot cooperation with members of the target population. We therefore consider the problem of textitlearning a strategy for cooperating with such a population using prior observations its members interacting with one another. We provide upper and lower bounds on the number of samples needed to learn an effective cooperation strategy. Most importantly, we show that these bounds can be much stronger than those arising from a "naive'' reduction of the problem to one of imitation learning.