# On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 20 Jun 2022.

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

- [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)
- [Off-Belief Learning](https://mlsanity.com/paper/2103.04000/) (2021)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1912.02288/) (2019)
- [Diverse Agents for Ad-Hoc Cooperation in Hanabi](https://mlsanity.com/paper/1907.03840/) (2019)

## Built on by (most cited first, 5 of 5)

- [ROTATE: Regret-driven Open-ended Training for Ad Hoc Teamwork](https://mlsanity.com/paper/2505.23686/) (2025)
- [Towards a Unifying Model of Rationality in Multiagent Systems](https://mlsanity.com/paper/2305.18071/) (2023)
- [On the Complexity of Learning to Cooperate with Populations of Socially Rational Agents](https://mlsanity.com/paper/2407.00419/) (2024)
- [Heterogeneous Decision Making in Mixed Traffic: Uncertainty-aware Planning and Bounded Rationality](https://mlsanity.com/paper/2502.18529/) (2025)
- [NestRL: A Nested Training Regime for Mutual Adaptation in Human-AI Teaming](https://mlsanity.com/paper/2602.17737/) (2026)

## Abstract (arXiv)

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.