Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2017 Volume 32
Article Contents
Next Previous
ORIGINAL RESEARCH   Open Access    

Multi-agent credit assignment in stochastic resource management games

  • 1.

    Department of Computer Science & Applied Physics

  • 2.

    Discipline of Information Technology

  • 3.

    Department of Computer Science

More Information
  • Abstract: Multi-agent systems (MASs) are a form of distributed intelligence, where multiple autonomous agents act in a common environment. Numerous complex, real world systems have been successfully optimized using multi-agent reinforcement learning (MARL) in conjunction with the MAS framework. In MARL agents learn by maximizing a scalar reward signal from the environment, and thus the design of the reward function directly affects the policies learned. In this work, we address the issue of appropriate multi-agent credit assignment in stochastic resource management games. We propose two new stochastic games to serve as testbeds for MARL research into resource management problems: the tragic commons domain and the shepherd problem domain. Our empirical work evaluates the performance of two commonly used reward shaping techniques: potential-based reward shaping and difference rewards. Experimental results demonstrate that systems using appropriate reward shaping techniques for multi-agent credit assignment can achieve near-optimal performance in stochastic resource management games, outperforming systems learning using unshaped local or global evaluations. We also present the first empirical investigations into the effect of expressing the same heuristic knowledge in state- or action-based formats, therefore developing insights into the design of multi-agent potential functions that will inform future work.
  • 加载中
  • Arthur W. B. 1994. Inductive reasoning and bounded rationality. The American Economic Review 84, 406–411.

    Google Scholar

    Binmore K. 2012. Playing for Real: A Text on Game Theory. Oxford University Press.

    Google Scholar

    Buşoniu L., Babuška R. & Schutter B. 2010. Multi-agent reinforcement learning: An overview. In Innovations in Multi-Agent Systems and Applications – 1, Volume 310 of Studies in Computational Intelligence, Srinivasan, D. & Jain, L. (eds). Springer Berlin Heidelberg, 183–221.

    Google Scholar

    Colby M., Duchow-Pressley T., Chung J. J. & Tumer K. 2016. Local approximation of difference evaluation functions. In Proceedings of the 15th International Conference on Autonomous Agents & Multiagent Systems (AAMAS), 521–529.

    Google Scholar

    de Jong S. & Tuyls K. 2009. Learning to cooperate in a continuous tragedy of the commons. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems – Volume 2, 1185–1186. International Foundation for Autonomous Agents and Multiagent Systems.

    Google Scholar

    Devlin S. & Kudenko D. 2011. Theoretical considerations of potential-based reward shaping for multi-agent systems. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 225–232.

    Google Scholar

    Devlin S. & Kudenko D. 2012. Dynamic potential-based reward shaping. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 433–440.

    Google Scholar

    Devlin S., Grzes M. & Kudenko D. 2011a. An empirical study of potential-based reward shaping and advice in complex, multi-agent systems. Advances in Complex Systems 14(2), 251–278.

    Google Scholar

    Devlin S., Grzes M. & Kudenko D. 2011b. Multi-agent, potential-based reward shaping for robocup keepaway (extended abstract). In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1227–1228.

    Google Scholar

    Devlin S., Yliniemi L., Kudenko D. & Tumer K. 2014. Potential-based difference rewards for multiagent reinforcement learning. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 165–172.

    Google Scholar

    Grześ M. & Kudenko D. 2009. Theoretical and empirical analysis of reward shaping in reinforcement learning. In International Conference on Machine Learning and Applications, 2009. ICMLA’09, 337–344. IEEE.

    Google Scholar

    Howley E. & Duggan J. 2011. Investing in the commons: a study of openness and the emergence of cooperation. Advances in Complex Systems 14(2), 229–250.

    Google Scholar

    Malialis K., Devlin S. & Kudenko D. 2015. Distributed reinforcement learning for adaptive and robust network intrusion response. Connection Science 27(3), 234–252.

    Google Scholar

    Malialis K., Devlin S. & Kudenko D. 2016. Resource abstraction for reinforcement learning in multiagent congestion problems. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 503–511.

    Google Scholar

    Mannion P., Duggan J. & Howley E. 2016a. An experimental review of reinforcement learning algorithms for adaptive traffic signal control. In Autonomic Road Transport Support Systems, McCluskey, L. T., Kotsialos, A., Müller, P. J., Klügl, F., Rana, O. & Schumann, R. (eds). Springer International Publishing, 47–66.

    Google Scholar

    Mannion P., Duggan J. & Howley E. 2016b. Generating multi-agent potential functions using counterfactual estimates. In Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS 2016).

    Google Scholar

    Mannion P., Duggan J. & Howley E. 2017. Analysing the effects of reward shaping in multi-objective stochastic games. In Proceedings of the Adaptive and Learning Agents Workshop (at AAMAS 2017).

    Google Scholar

    Mannion P., Mason K., Devlin S., Duggan J. & Howley E. 2016c. Dynamic economic emissions dispatch optimisation using multi-agent reinforcement learning. In Proceedings of the Adaptive and Learning Agents Workshop (at AAMAS 2016).

    Google Scholar

    Mannion P., Mason K., Devlin S., Duggan J. & Howley E. 2016d. Multi-objective dynamic dispatch optimisation using multi-agent reinforcement learning. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1345–1346.

    Google Scholar

    Mason K., Mannion P., Duggan J. & Howley E. 2016. Applying multi-agent reinforcement learning to watershed management. In Proceedings of the Adaptive and Learning Agents Workshop (at AAMAS 2016).

    Google Scholar

    Ng A. Y., Harada D. & Russell S. J. 1999. Policy invariance under reward transformations: theory and application to reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML ’99, 278–287. Morgan Kaufmann Publishers Inc.

    Google Scholar

    Puterman M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st edition. John Wiley & Sons, Inc.

    Google Scholar

    Randløv J. & Alstrøm P. 1998. Learning to drive a bicycle using reinforcement learning and shaping. In Proceedings of the Fifteenth International Conference on Machine Learning, ICML ’98, 463–471. Morgan Kaufmann Publishers Inc.

    Google Scholar

    Shoham Y., Powers R. & Grenager T. 2007. If multi-agent learning is the answer, what is the question? Artificial Intelligence 171, 365–377.

    Google Scholar

    Tumer K. & Agogino A. 2007. Distributed agent-based air traffic flow management. In Proceedings of the 6th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 330–337.

    Google Scholar

    Tumer K., Agogino A. K. & Welch Z. 2009. Traffic congestion management as a learning agent coordination problem. In Multiagent Architectures for Traffic and Transportation Engineering, Bazzan, A. & Kluegl, F. (eds). Lecture notes in AI. Springer, 261–279.

    Google Scholar

    Watkins C. J. & Dayan P. 1992. Technical note: Q-learning. Machine Learning 8, 279–292.

    Google Scholar

    Watkins C. J. C. H. 1989. Learning from Delayed Rewards. PhD thesis, King’s College.

    Google Scholar

    Wiering M. & van Otterlo M. (eds) 2012. Reinforcement Learning: State-of-the-Art. Springer.

    Google Scholar

    Wiewiora E., Cottrell G. & Elkan C. 2003. Principled methods for advising reinforcement learning agents. In Proceedings of the Twentieth International Conference on Machine Learning, 792–799.

    Google Scholar

    Wolpert D. H. & Tumer K. 2002. Collective intelligence, data routing and Braess’ paradox. Journal of Artificial Intelligence Research 16, 359–387.

    Google Scholar

    Wolpert D. H., Wheeler K. R. & Tumer K. 2000. Collective intelligence for control of distributed dynamical systems. EPL (Europhysics Letters) 49(6), 708.

    Google Scholar

    Wooldridge M. 2001. Introduction to Multiagent Systems. John Wiley & Sons Inc.

    Google Scholar

  • Cite this article

    Patrick Mannion, Sam Devlin, Jim Duggan, Enda Howley. 2017. Multi-agent credit assignment in stochastic resource management games. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891700011X
    Patrick Mannion, Sam Devlin, Jim Duggan, Enda Howley. 2017. Multi-agent credit assignment in stochastic resource management games. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891700011X
    shu
Download PDF

Article Metrics

Article views(33) PDF downloads(53)

Other Articles By Authors

ORIGINAL RESEARCH   Open Access    

Multi-agent credit assignment in stochastic resource management games

  • 1.

    Department of Computer Science & Applied Physics

  • 2.

    Discipline of Information Technology

  • 3.

    Department of Computer Science

  • Published online: 24 August 2017
The Knowledge Engineering Review  32,  2017, 32(1)  |  Cite this article

Abstract: Abstract: Multi-agent systems (MASs) are a form of distributed intelligence, where multiple autonomous agents act in a common environment. Numerous complex, real world systems have been successfully optimized using multi-agent reinforcement learning (MARL) in conjunction with the MAS framework. In MARL agents learn by maximizing a scalar reward signal from the environment, and thus the design of the reward function directly affects the policies learned. In this work, we address the issue of appropriate multi-agent credit assignment in stochastic resource management games. We propose two new stochastic games to serve as testbeds for MARL research into resource management problems: the tragic commons domain and the shepherd problem domain. Our empirical work evaluates the performance of two commonly used reward shaping techniques: potential-based reward shaping and difference rewards. Experimental results demonstrate that systems using appropriate reward shaping techniques for multi-agent credit assignment can achieve near-optimal performance in stochastic resource management games, outperforming systems learning using unshaped local or global evaluations. We also present the first empirical investigations into the effect of expressing the same heuristic knowledge in state- or action-based formats, therefore developing insights into the design of multi-agent potential functions that will inform future work.

    HTML

    Acknowledgments

    • P. M.’s PhD work at the National University of Ireland Galway was funded in part by an Irish Research Council Postgraduate Scholarship.

    Rights and permissions
    • © Cambridge University Press, 2017 2017Cambridge University Press
References (33)
  • About this article
    Cite this article
    Patrick Mannion, Sam Devlin, Jim Duggan, Enda Howley. 2017. Multi-agent credit assignment in stochastic resource management games. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891700011X
    Patrick Mannion, Sam Devlin, Jim Duggan, Enda Howley. 2017. Multi-agent credit assignment in stochastic resource management games. The Knowledge Engineering Review 32(1), doi: 10.1017/S026988891700011X
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return