Communication complexity as a lower bound for learning in games

ABSTRACT

A fast-growing body of research in the AI and machine learning communities addresses learning in games, where there are multiple learners with different interests. This research adds to more established research on learning in games conducted in economics. In part because of a clash of fields, there are widely varying requirements on learning algorithms in this domain. The goal of this paper is to demonstrate how communication complexity can be used as a lower bound on the required learning time or cost. Because this lower bound does not assume any requirements on the learning algorithm, it is universal, applying under any set of requirements on the learning algorithm.We characterize exactly the communication complexity of various solution concepts from game theory, namely Nash equilibrium, iterated dominant strategies (both strict and weak), and backwards induction. This gives the tighest lower bounds on learning in games that can be obtained with this method.

REFERENCES

• 1: Blum, B., Shelton, C. R., & Koller, D. (2003). A continuation method for Nash equilibria in structured games. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI). Acapulco, Mexico.
• 2: Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
• 3: Conitzer, V., & Sandholm, T. (2003). AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. International Conference on Machine Learning (pp. 83--90).
• 4: Freund, Y., & Schapire, R. E. (1999). Adaptive game playing using multiplicative weights. Games & Econ. Behavior, 29, 79--103.
• 5: Fudenberg, D., & Levine, D. (1998). The theory of learning in games. MIT Press.
• 6: Itzhak Gilboa , Ehud Kalai , Eitan Zemel, The complexity of eliminating dominated strategies, Mathematics of Operations Research, v.18 n.3, p.553-565, Aug. 1993 [doi>10.1287/moor.18.3.553]
• 7: Greenwald, A., & Hall, K. (2003). Correlated Q-learning. International Conference on Machine Learning (pp. 242--249).
• 8: Hannan, J. (1957). Approximation to Bayes risk in repeated play. vol. III of Contributions to the Theory of Games, 97--139.
• 9: Junling Hu , Michael P. Wellman, Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Proceedings of the Fifteenth International Conference on Machine Learning, p.242-250, July 24-27, 1998
• 10: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 11: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 12: Leyton-Brown, K., & Tennenholtz, M. (2003). Local-effect games. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI). Acapulco, Mexico.
• 13: Michael L. Littman , Peter Stone, A polynomial-time nash equilibrium algorithm for repeated games, Proceedings of the 4th ACM conference on Electronic commerce, p.48-54, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779935]
• 14: Littman, M. L. (1994). Markov games as a framework for multiagent reinforcement learning. International Conference on Machine Learning (pp. 157--163).
• 15: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 16: Satinder P. Singh , Michael J. Kearns , Yishay Mansour, Nash Convergence of Gradient Dynamics in General-Sum Games, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.541-548, June 30-July 03, 2000
• 17: Stimpson, J., & Goodrich, M. (2003). Learning to cooperate in a social dilemma: A satisficing approach to bargaining. International Conference on Machine Learning (pp. 728--735).
• 18: Tan, M. (1993). Multi-agent reinforcement learning: Independent vs. cooperative agents. International Conference on Machine Learning (pp. 330--337).
• 19: Wang, X., & Sandholm, T. (2002). Reinforcement learning to play an optimal Nash equilibrium in team Markov games. Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS). Vancouver, Canada.
• 20: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]