Learning of coordination: exploiting sparse interactions in multiagent systems

ABSTRACT

Creating coordinated multiagent policies in environments with uncertainty is a challenging problem, which can be greatly simplified if the coordination needs are known to be limited to specific parts of the state space, as previous work has successfully shown. In this work, we assume that such needs are unknown and we investigate coordination learning in multiagent settings. We contribute a reinforcement learning based algorithm in which independent decision-makers/agents learn both individual policies and when and how to coordinate. We focus on problems in which the interaction between the agents is sparse, exploiting this property to minimize the coupling of the learning processes for the different agents. We introduce a two-layer extension of Q-learning, in which we augment the action space of each agent with a coordination action that uses information from other agents to decide the correct action. Our results show that our agents learn both to act coordinate and to act independently, in the different regions of the space where they need to, and need not to, coordinate, respectively.

REFERENCES

• 1: D. Aberdeen. A (revised) survey of approximate methods for solving partially observable Markov decision processes. Technical report, National ICT Australia, Canberra, Australia, 2003.
• 2: Daniel S. Bernstein , Robert Givan , Neil Immerman , Shlomo Zilberstein, The Complexity of Decentralized Control of Markov Decision Processes, Mathematics of Operations Research, v.27 n.4, p.819-840, November 2002 [doi>10.1287/moor.27.4.819.297]
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 4: M. Bowling and M. Veloso. Rational and convergent learning in stochastic games. In Proc. Int. Joint Conf. Artificial Intelligence, pages 1021--1026, 2001.
• 5: 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
• 6: Mohammad Ghavamzadeh , Sridhar Mahadevan , Rajbala Makar, Hierarchical multi-agent reinforcement learning, Autonomous Agents and Multi-Agent Systems, v.13 n.2, p.197-229, September 2006 [doi>10.1007/s10458-006-7035-4]
• 7: A. Greenwald and K. Hall. Correlated Q-learning. In Proc. Int. Conf. Machine Learning, pages 242--249, 2003.
• 8: C. Guestrin, D. Koller, and R. Parr. Multiagent planning with factored MDPs. In Proc. Adv. Neural Information Proc. Systems 14, pages 1523--1530, 2001.
• 9: Carlos Guestrin , Shobha Venkataraman , Daphne Koller, Context-specific multiagent coordination and planning with factored MDPs, Eighteenth national conference on Artificial intelligence, p.253-259, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 10: J. Kok, P. Hoen, B. Bakker, and N. Vlassis. Utile coordination: Learning interdependencies among cooperative agents. In Proc. Symp. on Computational Intelligence and Games, pages 29--36, 2005.
• 11: Jelle R. Kok , Nikos Vlassis, Sparse cooperative Q-learning, Proceedings of the twenty-first international conference on Machine learning, p.61, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015410]
• 12: D. Leslie and E. Collins. Generalised weakened fictitious play. Games and Economic Behavior, 56:285--298, 2006.
• 13: M. Littman. Value-function reinforcement learning in Markov games. J. Cognitive Systems Research, 2(1):55--66, 2001.
• 14: Maayan Roth , Reid Simmons , Manuela Veloso, Reasoning about joint beliefs for execution-time communication decisions, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082593]
• 15: Maayan Roth , Reid Simmons , Manuela Veloso, Exploiting factored representations for decentralized execution in multiagent teams, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329213]
• 16: Matthijs T. J. Spaan , Francisco S. Melo, Interaction-driven Markov games for decentralized multiagent planning under uncertainty, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 17: Ming Tan, Multi-agent reinforcement learning: independent vs. cooperative agents, Readings in agents, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 18: X. Wang and T. Sandholm. Reinforcement learning to play an optimal Nash equilibrium in team Markov games. In Proc. NIPS 15, pages 1571--1578, 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms

Keywords:
local interaction, multiagent coordination, reinforcement learning