On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games
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.