The world of independent learners is not markovian

Article type: Research Article

Authors: Laurent, Guillaume J.^{; *} | Matignon, Laëtitia | Le Fort-Piat, N.

Affiliations: FEMTO-ST Institute, CNRS / ENSMM / UFC/ UTBM, 24 rue Alain Savary, 25000 Besançon, France

Correspondence: [*] Corresponding author. E-mail: guillaume.laurent@ens2m.fr

Abstract: In multi-agent systems, the presence of learning agents can cause the environment to be non-Markovian from an agent's perspective thus violating the property that traditional single-agent learning methods rely upon. This paper formalizes some known intuition about concurrently learning agents by providing formal conditions that make the environment non-Markovian from an independent (non-communicative) learner's perspective. New concepts are introduced like the divergent learning paths and the observability of the effects of others' actions. To illustrate the formal concepts, a case study is also presented. These findings are significant because they both help to understand failures and successes of existing learning algorithms as well as being suggestive for future work.

Keywords: Multi-agent system, machine learning, reinforcement learning

DOI: 10.3233/KES-2010-0206

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 15, no. 1, pp. 55-64, 2011