  Artificially intelligent agents deployed in the real-world will require the
ability to reliably \textit{cooperate} 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 \textit{population} 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 \textit{zero-shot} cooperation with members of the target population.
We therefore consider the problem of \textit{learning} 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.
