Learning Automata as a Basis for Multi Agent Reinforcement Learning AnnNowé Vrije Universiteit Brussel
Pleinlaan 2 1050 Brussel
KatjeVerbeeck Vrije Universiteit Brussel
Pleinlaan 2 1050 Brussel
MaartenPeeters Vrije Universiteit Brussel
Pleinlaan 2 1050 Brussel
Learning Automata as a Basis for Multi Agent Reinforcement Learning 1D5046FEABE97E58BD17943AF4F2E23C GROBID - A machine learning software for extracting information from scholarly documents

Learning Automata (LA) are adaptive decision making devices suited for operation in unknown environments [12]. Originally they were developed in the area of mathematical psychology and used for modeling observed behavior. In its current form, LA are closely related to Reinforcement Learning (RL) approaches and most popular in the area of engineering. LA combine fast and accurate convergence with low computational complexity, and have been applied to a broad range of modeling and control problems. However, the intuitive, yet analytically tractable concept of learning automata makes them also very suitable as a theoretical framework for Multi agent Reinforcement Learning (MARL).

Reinforcement Learning (RL) is already an established and profound theoretical framework for learning in stand-alone or single-agent systems. Yet, extending RL to multi-agent systems (MAS) does not guarantee the same theoretical grounding. As long as the environment an agent is experiencing is Markov, and the agent can experiment sufficiently, RL guarantees convergence to the optimal strategy. In a MAS however, the reinforcement an agent receives, may depend on the actions taken by the other agents acting in the same environment. Hence, the Markov property no longer holds. And as such, guarantees of convergence are lost. In the light of the above problem it is important to fully understand the dynamics of multi-agent reinforcement learning.

Although, they are not fully recognized as such, LA are valuable tools for current MARL research. LA are updated strictly on the basis of the response of the environment, and not on the basis of any knowledge regarding other automata, i.e. nor their strategies, nor their feedback. As such LA agents are very simple. Moreover, LA can be treated analytically. Convergence proofs do exist for a variety of settings ranging from a single automaton model acting in a simple stationary random environment to a distributed automata model interacting in a complex environment.

In this paper we argue that LA are very interesting building blocks for learning in multi agent systems. The LA can be viewed as policy iterators, who update their action probabilities based on private information only. This is a very attractive property in applications where communication is expensive. LA are in particular appealing in games with stochastic payoffs. Then we move to collections of learning automata, that can independently converge to interesting solution concepts. We study the single stage setting, including the analytical results. Then we generalize to interconnected learning automata, that can deal with multi agent multi-stage problems. We also show how Ant Colony Optimization can be mapped to the interconnected Learning Automata setting.
Swarm Intelligence, From Natural to Artificial Systems EricBonabeau MarcoDorigo GuyTheraulaz Santa Fe Institute studies in the sciences of complexity Oxford University Press 1999 Planning, learning and coordination in multiagent decision processes CBoutilier Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge the 6th Conference on Theoretical Aspects of Rationality and Knowledge
Renesse, Holland
 1996 Sequential optimality and coordination in multiagent systems CBoutilier Proceedings of the 16th International Joint Conference on Artificial Intelligence the 16th International Joint Conference on Artificial Intelligence
Stockholm, Sweden
 1999 Stochastic Models for Learning RRBush FMosteller 1958 Wiley New York The dynamics of reinforcement learning in cooperative multiagent systems CClaus CBoutilier Proceedings of the 15th National Conference on Artificial Intelligence the 15th National Conference on Artificial Intelligence 1998 Heuristics from nature for hard combinatorial optimization problems AColorni MDorigo FMaffioli VManiezzo GRighini MTrubian International Transactions in Operational Research 1996 Ant algorithms for discrete optimization MDorigo GDiCaro LMGambardella Artificial Life 5 2 1999 The ant colony optimization meta-heuristic MarcoDorigo GiannoDi Caro New Ideas In Optimization DCorne MDorigo FGlover
Maidenhaid, UK
 McGraw-Hill 1999 The ant system: Optimization by a colony of cooperating agents MarcoDorigo VittorioManiezzo AlbertoColorni IEE Transactions on Systems, Man, and Cybernetics 1996 Ant Colony Optimization MarcoDorigo ThomasStützle 2004 The MIT Press Markov games as a framework for multi-agent reinforcement learning MLittman Proceedings of the 11th International Conference on Machine Learning the 11th International Conference on Machine Learning 1994 Learning Automata: An Introduction KNarendra MThathachar 1989 Prentice-Hall International, Inc Learning automata approach to hierarchical multiobjective analysis KSNarendra KParthasarathy No. 8811 1988 New Haven, Connecticut Electrical Engineering Yale University Technical Report Report Learning automata as a basis for multi agent reinforcement learning. Learning and Adaptation in Multi-Agent Systems AnnNowé KatjaVerbeeck MaartenPeeters Lecture Notes in Artificial Intelligence 3898 2005 Continuous learning automata solutions to the capacity assignment problem BJOommen TDRoberts IEEE Transactions on Computations 49 2000 Reinforcement Learning: An Introduction RSutton ABarto 1998 MIT Press Cambridge, MA Automaton theory and modelling of biological systems MLTsetlin Mathematics in Science and Engineering 102 1973 Multiple stochastic learning automata for vehicule path control in an automated highway system CUnsal PKachroo JSBay IEEE Transactions on Systems, Man, and Cybernetics, Part A 29 1999 Coordinated Exploration in Multi-Agent Reinforcement Learning KVerbeeck 2004 Belgium Computational Modeling Lab ; Vrije Universiteit Brussel PhD thesis Multi-agent reinforcement learning in stochastic single and multi-stage games KVerbeeck ANowé KTuyls MPeeters Adaptive Agents and Multi-Agent Systems II Kudenko 2005 3394