Integrating organizational control into multi-agent learning

ABSTRACT

Multi-Agent Reinforcement Learning (MARL) algorithms suffer from slow convergence and even divergence, especially in large-scale systems. In this work, we develop an organization-based control framework to speed up the convergence of MARL algorithms in a network of agents. Our framework defines a multi-level organizational structure for automated supervision and a communication protocol for exchanging information between lower-level agents and higher-level supervising agents. The abstracted states of lower-level agents travel upwards so that higher-level supervising agents generate a broader view of the state of the network. This broader view is used in creating supervisory information which is passed down the hierarchy. The supervisory policy adaptation then integrates supervisory information into existing MARL algorithms, guiding agents' exploration of their state-action space. The generality of our framework is verified by its applications on different domains (distributed task allocation and network routing) with different MARL algorithms. Experimental results show that our framework improves both the speed and likelihood of MARL convergence.

REFERENCES

• 1: Sherief Abdallah , Victor Lesser, Learning the task allocation game, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160786]
• 2: Sherief Abdallah , Victor Lesser, Multiagent reinforcement learning and self-organization in a network of agents, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329172]
• 3: R. A. C. Bianchi, C. H. C. Ribeiro, and A. H. R. Costa. Heuristic selection of actions in multiagent reinforcement learning. In IJCAI'07, Hyderabad, India, 2007.
• 4: J. A. Boyan and M. L. Littman. Packet routing in dynamically changing networks: A reinforcement learning approach. In NIPS'94, volume 6, pages 671--678, 1994.
• 5: Rajbala Makar , Sridhar Mahadevan , Mohammad Ghavamzadeh, Hierarchical multi-agent reinforcement learning, Proceedings of the fifth international conference on Autonomous agents, p.246-253, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376302]
• 6: Andrew Y. Ng , Daishi Harada , Stuart J. Russell, Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping, Proceedings of the Sixteenth International Conference on Machine Learning, p.278-287, June 27-30, 1999
• 7: L. Peshkin and V. Savova. Reinforcement learning for adaptive routing. In International Joint Conference on Neural Networks (IJCNN), 2002.
• 8: M. T. Rosenstein and A. G. Barto. Supervised actor-critic reinforcement learning. In J. Si, A. Barto, W. Powell, and D. Wunsch, editors, Learning and Approximate Dynamic Programming: Scaling Up to the Real World, pages 359--380. John Wiley and Sons, 2004.
• 9: H. A. Simon. Nearly-decomposable systems. In The Sciences of the Artificial, pages 99--103, 1969.
• 10: Satinder Singh , Tommi Jaakkola , Michael L. Littman , Csaba Szepesvári, Convergence Results for Single-Step On-PolicyReinforcement-Learning Algorithms, Machine Learning, v.38 n.3, p.287-308, March 2000 [doi>10.1023/A:1007678930559]
• 11: Peter Stone , Manuela Veloso, Team-partitioned, opaque-transition reinforcement learning, Proceedings of the third annual conference on Autonomous Agents, p.206-212, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301195]
• 12: P. Tangamchit, J. Dolan, and P. Khosla. Learning-based task allocation in decentralized multirobot systems. In DARS'00, pages 381--390, 2000.
• 13: Nigel Tao , Jonathan Baxter , Lex Weaver, A Multi-Agent Policy-Gradient Approach to Network Routing, Proceedings of the Eighteenth International Conference on Machine Learning, p.553-560, June 28-July 01, 2001
• 14: C. Zhang, V. Lesser, and S. Abdallah. Self-organization for dynamically supervising distributed learning. In University of Massachusetts Amherst Computer Science Technical Report UM-CS-2009-007, 2009.
• 15: Haizheng Zhang , Victor Lesser, A reinforcement learning based distributed search algorithm for hierarchical peer-to-peer information retrieval systems, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329182]
• 16: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML'03, pages 928--936, 2003.

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

General Terms:
Algorithms, Experimentation

Keywords:
coordinated learning, multi-agent learning, organization control, policy adaptation, supervision