English

Multi-agent reinforcement learning is an extension of reinforcement learning concept to multi-agent environments. Reinforcement learning allows to program agents by reward and punishment without specifying how to achieve the task. Formally agent-environment interaction in multi-agent reinforcement learning is presented as a discounted stochastic game. The task the agents are facing is formalized as the problem of finding Nash equilibria.

This thesis is devoted to development of multi-agent reinforcement learning algorithms. We propose an algorithm converging in self-play to Nash equilibria for high percentage of general-sum discounted stochastic games. The approach is based on generalization of replicator dynamics for discounted stochastic games. Before there was no algorithm that converged to Nash equilibria for general-sum discounted stochastic games (only for particular cases). The approach also outperforms the methods for solving general-sum discounted stochastic games: nonlinear optimization and stochastic tracing procedure. These algorithms function under the assumption that the games are known from the very beginning in contrast to reinforcement learning where the agent's task is to learn an optimal behavior in unknown environment. Another contribution is an algorithm that always converges to stationary policies and to best-response strategies against stationary opponents. Unlike the first algorithm it doesn't require that the opponents' rewards are observable. We give theoretical foundations for the convergence of the algorithms proposed in this thesis.

The possible application areas include traditional reinforcement learning tasks in multi-agent environments like robot soccer and development of trading agents along with numerous economic problems as a rule modeled as differential games in the field of capital accumulation, advertising, pricing, macroeconomics, warfare and resource economics. We propose to approximate the differential games with stochastic games and apply the developed solver.

Deutsch

Multiagenten Reinforcement Learning erweitert das klassische Reinforcement Learning auf Multiagenten Umgebungen. Reinforcement Learning erlaubt es, Agenten auf Basis von Belohnung und Bestrafung zu programmieren, ohne zu spezifizieren, wie die Aufgabe erledigt werden soll. Die Interaktion zwischen den Agenten und der Umgebung wird beim Multiagenten Reinforcement Learning formal als discounted stochastic Game angegeben. Die Aufgabe, die die Agenten zu Lösen haben, wird als Problem formalisiert ein Nash-Gleichgewicht zu finden.

Diese Arbeit widmet sich der Entwicklung von Algorithmen für das Multiagenten Reinforcement Learning. Wir präsentieren einen Algorithmus, der für viele general-sum discounted stochastic Games einem Nash-Gleichgewicht konvergiert. Der Ansatz basiert auf der Generalisierung von Replikatordynamiken bei discounted stochastic Games. Bisher gab es keinen Algorithmus, der zu einem Nash-Gleichgewicht für general-sum discounted stochastic Games konvergiert (nur für ganz spezielle Fälle). Der Ansatz übertrifft auch die Methoden zum Lösen von general-sum discounted stochastic Games, nämlich nichtlineare Optimierung und Tracingverfahren. Diese Algorithmen treffen die Annahme, dass die Spiele von Beginn an bekannt sind, was beim Reinforcement Learning nicht der Fall ist, da die Aufgabe eines Agenten das Erlernen optimalen Verhaltens in unbekannten Umgebungen ist. Ein weiterer Beitrag ist ein Algorithmus, der immer zu stationären Strategien konvergiert und zu Strategien, die immer die beste Antwort gegenüber stationären Gegnern liefern. Anders als im ersten Ansatz, setzt dieser Algorithmus nicht voraus, dass die Belohnungen des Gegners beobachtbar sind. Wir legen zudem die theoretischen Grundlagen für die Konvergenz der in dieser Arbeit vorgestellten Algorithmen.

Mögliche Anwendungsgebiete schließen traditionelle Reinforcement Learning Aufgaben in Multiagenten Umgebungen, wie Roboterfußball, ein, sowie die Entwicklung von Händleragenten nebst einer Vielzahl ökonomischer Probleme, wie einer Regel, die als differentielles Spiel im Umfeld von Kapitalbildung, Werbung, Kalkulation, Makroökonomie, Kriegsführung und Ressourcenökonomie modelliert wird. Wir schlagen vor, diese differentiellen Spiele durch stochastic Games zu approximieren und die vorgeschlagenen Lösungsverfahren einzusetzen.