skip to main content
10.1145/1160633.1160767acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
Article

Selecting informative actions improves cooperative multiagent learning

Published: 08 May 2006 Publication History

Abstract

In concurrent cooperative multiagent learning, each agent simultaneously learns to improve the overall performance of the team, with no direct control over the actions chosen by its teammates. An agent's action selection directly influences the rewards received by all the agents, resulting in a co-adaptation among the concurrent learning processes. Co-adaptation can drive the team towards suboptimal solutions because agents tend to select those actions that are rewarded better, without any consideration for how such actions may affect the search of their teammates. We argue that to counter this tendency, agents should also prefer actions that inform their teammates about the structure of the joint search space in order to help them choose from among various action options. We analyze this approach in a cooperative coevolutionary framework, and we propose a new algorithm, iCCEA, that highlights the advantages of selecting informative actions. We show that iCCEA generally outperforms other cooperative coevolution algorithms on our test problems.

References

[1]
T. Bäck, D. Fogel, and Z. Michalewicz. Handbook of Evolutionary Computation. Oxford University Press, 1997.
[2]
R. Becker, S. Zilberstein, V. Lesser, and C. V. Goldman. Solving Transition Independent Decentralized Markov Decision Processes. Journal of Artificial Intelligence Research, 22:423--455, December 2004.
[3]
R. Brafman and M. Tennenholtz. Efficient learning equilibrium. In Advances in Neural Information Processing Systems (NIPS-2002), 2002.
[4]
A. Bucci and J. Pollack. On identifying global optima in cooperative coevolution. In Hans-Georg Beyer et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2005, pages 539--544, ACM, 2005.
[5]
L. Bull. Evolutionary computing in multi-agent environments: Partners. In T. Back, editor, Proceedings of the Seventh International Conference on Genetic Algorithms, pages 370--377. Morgan Kaufmann, 1997.
[6]
L. Bull. Evolutionary computing in multi-agent environments: Operators. In D. W. V W Porto, N Saravanan and A. E. Eiben, editors, Proceedings of the Seventh Annual Conference on Evolutionary Programming, pages 43--52. Springer Verlag, 1998.
[7]
C. Claus and C. Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of National Conference on Artificial Intelligence (AAAI-98), pages 746--752, 1998.
[8]
K. De Jong. Evolutionary Computation. The MIT Press, 2006.
[9]
E. Hansen, D. Bernstein, and S. Zilberstein. Dynamic programming for partially observable stochastic games. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004.
[10]
P. Husbands and F. Mill. Simulated coevolution as the mechanism for emergent planning and scheduling. In R. Belew and L. Booker, editors. Proceedings of the Fourth International Conference on Genetic Algorithms, pages 264--270. Morgan Kaufmann, 1991.
[11]
S. Kapetanakis and D. Kudenko. Reinforcement learning of coordination in cooperative multi-agent systems. In Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI-02), 2002.
[12]
M. Lauer and M. Riedmiller. An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 535--542, 2000.
[13]
M. I. Lichbach. The cooperator's dilemma. University of Michigan Press, 1996.
[14]
S. Luke. ECJ 13: A Java EC research system. Available at http://cs.gmu.edu/~eclab/projects/ecj/, 2005.
[15]
R. Nair, M. Tambe, M. Yokoo, D. Pynadath, and S. Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), 2003.
[16]
L. Panait and S. Luke. Cooperative multi-agent learning: The state of the art. Autonomous Agents and Multi-Agent Systems, 11(3), 2005.
[17]
L. Panait and S. Luke. Time-dependent collaboration schemes for cooperative coevolutionary algorithms. In Proceedings of the 2005 AAAI Fall Symposium on Coevolutionary and Coadaptive Systems, 2005.
[18]
L. Panait, R. P. Wiegand, and S. Luke. Improving coevolutionary search for optimal multiagent behaviors. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), pages 653--658, Acapulco, Mexico, 2003. Morgan Kaufmann.
[19]
L. Panait, R. P. Wiegand, and S. Luke. A sensitivity analysis of a cooperative coevolutionary algorithm biased for optimization. In Kalyanmoy Deb et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2004, page (to appear). Springer, 2004.
[20]
L. Panait, R. P. Wiegand, and S. Luke. A visual demonstration of convergence properties of cooperative coevolution. In Parallel Problem Solving from Nature---PPSN-2004. Springer, 2004.
[21]
E. Popovici and K. D. Jong. Understanding cooperative co-evolutionary dynamics via simple fitness landscapes. In Hans-Georg Beyer et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2005, pages 507--514. ACM, 2005.
[22]
M. Potter. The Design and Analysis of a Computational Model of Cooperative CoEvolution. PhD thesis, George Mason University, Fairfax, Virginia, 1997.
[23]
Y. Shoham, R. Powers, and T. Grenager. On the agenda(s) of research on multi-agent learning. In Proceedings of Artificial Multiagent Learning. Papers from the 2004 AAAI Fall Symposium. Technical Report FS-04-02, 2004.
[24]
D. Szer, F. Charpillet, and S. Zilberstein. MAA*: A heuristic search algorithm for solving decentralized POMDPs. In Proceedings of the Twenty First Conference on Uncertainty in Artificial Intelligence, 2005.
[25]
R. P. Wiegand. Analysis of Cooperative Coevolutionary Algorithms. PhD thesis, Department of Computer Science, George Mason University, 2003.
[26]
R. P. Wiegand, W. Liles, and K. De Jong. An empirical analysis of collaboration methods in cooperative coevolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 1235--1242, 2001.

Cited By

View all
  • (2024)Metaheuristics for variable-size mixed optimization problems: A unified taxonomy and surveySwarm and Evolutionary Computation10.1016/j.swevo.2024.10164289(101642)Online publication date: Aug-2024
  • (2020)Bi-Hierarchical Cooperative Coevolution for Large Scale Global OptimizationIEEE Access10.1109/ACCESS.2020.29764888(41913-41928)Online publication date: 2020
  • (2019)A Survey on Cooperative Co-Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.286877023:3(421-441)Online publication date: Jun-2019
  • Show More Cited By

Index Terms

  1. Selecting informative actions improves cooperative multiagent learning

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems
    May 2006
    1631 pages
    ISBN:1595933034
    DOI:10.1145/1160633
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 May 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. cooperation
    2. cooperative co-evolution
    3. coordination
    4. multiagent learning

    Qualifiers

    • Article

    Conference

    AAMAS06
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Metaheuristics for variable-size mixed optimization problems: A unified taxonomy and surveySwarm and Evolutionary Computation10.1016/j.swevo.2024.10164289(101642)Online publication date: Aug-2024
    • (2020)Bi-Hierarchical Cooperative Coevolution for Large Scale Global OptimizationIEEE Access10.1109/ACCESS.2020.29764888(41913-41928)Online publication date: 2020
    • (2019)A Survey on Cooperative Co-Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.286877023:3(421-441)Online publication date: Jun-2019
    • (2018)Enhancing Cooperative Coevolution with Selective Multiple Populations for Large-Scale Global OptimizationComplexity10.1155/2018/92670542018Online publication date: 24-Jul-2018
    • (2017)Large-scale cooperative co-evolution using niching-based multi-modal optimization and adaptive fast clusteringSwarm and Evolutionary Computation10.1016/j.swevo.2017.03.00135(65-77)Online publication date: Aug-2017
    • (2014)Compensate information from multimodal dynamic landscapes: An anti-pathology cooperative coevolutionary algorithm2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900512(2578-2584)Online publication date: Jul-2014
    • (2014)Fitness Landscapes That Depend on TimeRecent Advances in the Theory and Application of Fitness Landscapes10.1007/978-3-642-41888-4_10(265-299)Online publication date: 2014
    • (2012)Cooperative Machine Learning with Information Fusion for Dynamic Decision Making in Diagnostic ApplicationsProceedings of the 2012 International Conference on Advances in Mobile Network, Communication and Its Applications10.1109/MNCApps.2012.19(70-74)Online publication date: 1-Aug-2012
    • (2012)Coevolutionary PrinciplesHandbook of Natural Computing10.1007/978-3-540-92910-9_31(987-1033)Online publication date: 2012
    • (2010)Quality-Based Development of Agent SystemsQuality Assurance of Agent-Based and Self-Managed Systems10.1201/9781439812679.ch5(113-138)Online publication date: 19-Feb-2010
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media