Can good learners always compensate for poor learners?

ABSTRACT

Can a good learner compensate for a poor learner when paired in a coordination game? Previous work presented an example where a special learning algorithm (FMQ) is capable of doing just that when paired with a specific less capable algorithm even in games which stump the poorer algorithm when paired with itself. We argue that this result is not general. We give a straightforward extension to the coordination game in which FMQ cannot compensate for the lesser algorithm. We also provide other problematic pairings, and argue that another high-quality algorithm cannot do so either.

REFERENCES

• 1: 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 ]
• 2: 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
• 3: K. De Jong. Evolutionary Computation: A unified approach. MIT Press, 2006.
• 4: 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
• 5: Spiros Kapetanakis , Daniel Kudenko, Reinforcement learning of coordination in cooperative multi-agent systems, Eighteenth national conference on Artificial intelligence, p.326-331, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 6: Spiros Kapetanakis , Daniel Kudenko, Reinforcement Learning of Coordination in Heterogeneous Cooperative Multi-Agent Systems, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1258-1259, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.227]
• 7: Martin Lauer , Martin A. Riedmiller, An Algorithm for Distributed Reinforcement Learning in Cooperative Multi-Agent Systems, Proceedings of the Seventeenth International Conference on Machine Learning, p.535-542, June 29-July 02, 2000
• 8: M. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the 11th International Conference on Machine Learning (ML-94), pages 157--163, New Brunswick, NJ, 1994. Morgan Kaufmann.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
cooperative games, multiagent systems, reinforcement learning