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

Robert Loftin, Frans A Oliehoek
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:14197-14209, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-loftin22a, title = {On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games}, author = {Loftin, Robert and Oliehoek, Frans A}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {14197--14209}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/loftin22a/loftin22a.pdf}, url = {https://proceedings.mlr.press/v162/loftin22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games %A Robert Loftin %A Frans A Oliehoek %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-loftin22a %I PMLR %P 14197--14209 %U https://proceedings.mlr.press/v162/loftin22a.html %V 162 %X 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.
APA
Loftin, R. & Oliehoek, F.A.. (2022). On the Impossibility of Learning to Cooperate with Adaptive Partner Strategies in Repeated Games. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:14197-14209 Available from https://proceedings.mlr.press/v162/loftin22a.html.

Related Material