Multiagent learning in large anonymous games

ABSTRACT

In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if best-reply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed.

REFERENCES

• 1: M. Blonski. Equilibrium characterization in large anonymous games. Technical report, U. Mannheim, 2001.
• 2: Avrim Blum , Eyal Even-Dar , Katrina Ligett, Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146392]
• 3: Michael H. Bowling, Convergence Problems of General-Sum Multiagent Reinforcement Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.89-94, June 29-July 02, 2000
• 4: M. H. Bowling and M. M. Veloso. Rational and convergent learning in stochastic games. In 17th Int. Joint Conf. on Artificial Intelligence (IJCAI 2001), pages 1021--1026, 2001.
• 5: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 6: Caroline Claus , Craig Boutilier, The dynamics of reinforcement learning in cooperative multiagent systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.746-752, July 1998, Madison, Wisconsin, United States
• 7: D. P. Foster and P. Young. Regret testing: Learning to play Nash equilibrium without knowing you have an opponent. Theoretical Economics, 1:341--367, 2006.
• 8: Eric J. Friedman , Joseph Y. Halpern , Ian Kash, Efficiency and nash equilibria in a scrip system for P2P networks, Proceedings of the 7th ACM conference on Electronic commerce, p.140-149, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134723]
• 9: E. J. Friedman and S. Shenker. Learning and implementation on the internet. 1998.
• 10: D. Fudenberg and D. Levine. Theory of Learning in Games. MIT Press, 1998.
• 11: F. Germano and G. Lugosi. Global Nash convergence of Foster and Young's regret testing. Games and Economic Behavior, 60(1):135--154, July 2007.
• 12: A. Greenwald, E. J. Friedman, and S. Shenker. Learning in networks contexts: Experimental results from simulations. Games and Economic Behavior, 35(1--2):80--123, 2001.
• 13: S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127--1150, 2000.
• 14: S. Hart and A. Mas-Colell. A reinforecement learning procedure leading to correlated equilibrium. In G. Debreu, W. Neuefeind, and W. Trockel, editors, Economic Essays, pages 181--200. Springer, 2001.
• 15: Junling Hu , Michael P. Wellman, Nash q-learning for general-sum stochastic games, The Journal of Machine Learning Research, 4, p.1039-1069, 12/1/2003
• 16: L. P. Kaelbling, M. L. Littman, and A. P. Moore. Reinforcement learning: A survey. J. Artif. Intell. Res. (JAIR), 4:237--285, 1996.
• 17: J. R. Marden, G. Arslan, and J. S. Shamma. Connections between cooperative control and potential games. In Proc. 2007 European Control Conference (ECC), 2007.
• 18: Jason R. Marden , Gürdal Arslan , Jeff S. Shamma, Regret based dynamics: convergence in weakly acyclic games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329175]
• 19: J. R. Marden, H. P. Young, G. Arslan, and J. S. Shamma. Payoff-based dynamics for multi-player weakly acyclic games. SIAM J. Control and Optimization, 2008. To appear.
• 20: P. Milgrom and J. Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255--1277, 1900.
• 21: M. Osborne and A. Rubenstein. A Course in Game Theory. MIT Press, 1994.
• 22: Y. Shoham, R. Powers, and T. Grenager. Multi-agent reinforcement learning: a critical survey. Technical report, Stanford, 2003.
• 23: Gerald Tesauro , Jeffrey O. Kephart, Pricing in Agent Economies Using Multi-Agent Q-Learning, Autonomous Agents and Multi-Agent Systems, v.5 n.3, p.289-304, September 2002 [doi>10.1023/A:1015504423309]
• 24: Katja Verbeeck , Ann Nowé , Johan Parent , Karl Tuyls, Exploring selfish reinforcement learning in repeated games with stochastic rewards, Autonomous Agents and Multi-Agent Systems, v.14 n.3, p.239-269, June 2007 [doi>10.1007/s10458-006-9007-0]
• 25: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]
• 26: H. P. Young. Learning by trial and error. http://www.econ.jhu.edu/People/Young/Learning22Feb08.pdf.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
anonymous games, best-reply dynamics, game theory, large games, multiagent learning