Was ist Reinforcement Learning? (Teil 2)

Im letzten Beitrag diskutierten wir grundlegende Konzepte des RL, wie z.B. den Markov-Entscheidungsprozess (MDP). Hier geht der Agent vom Zustand $$s$$ zum Zustand $$s'$$ über, indem er die Aktion $$a$$ wählt und eine Belohnung $$R(s, s', a)$$ erhält. Aus wiederholten Interaktionen mit dem MDP lernt der Agent die Q-Funktion $$Q(s, a)$$, die die erwartete Belohnung für die Wahl der Aktion $$a$$ im Zustand $$s$$ misst. Die Q-Funktion bildet die Grundlage für die Entscheidungsfindung der Agenten. Diese Form des RL wird Q-Learning genannt.

Es gibt einen alternativen Ansatz, den wir nicht diskutiert haben, der als Actor-critic bezeichnet wird. Auch dies ist im Prinzip ein Single-Agent-Algorithmus, aber er wird recht häufig für MARL verwendet, einschließlich in der Forschung, die wir weiter unten besprechen werden.

Actor-critic

Erinnern wir uns an das Optimierungsproblem, das mit RL gelöst werden soll. Im Grunde versuchen wir, eine Strategie $$\pi^{\ast}$$ zu erlernen, die die erwartete diskontierte Belohnung optimiert, d.h.

[Loss]

wobei $$r_t := R(s_{t+1}, s_t, a_t)$$ die Belohnung ist, die im Zeitschritt $$t$$ erhalten wird und $$\gamma$$ ein Wert zwischen $$0$$ und $$1$$ hat.

Beim Q-Lernen wird die Strategie beibehalten (z.B. $$\epsilon$$-gierig) und die Q-Funktion optimiert, wodurch die Strategie indirekt gelernt wird.

Wie das Q-Learning löst auch Actor-critic das Problem [Verlust], aber der Hauptunterschied besteht darin, dass Actor-critic, anstatt die Strategie zu fixieren und die Q-Werte zu lernen, eine bestimmte Art des Lernprozesses mit einem Strategiegradienten verwendet, bei dem die Strategie $$\pi_\theta$$ mit $$\theta$$ parametrisiert wird und der Gradient von [Verlust] in Bezug auf $$\theta$$ berechnet wird. Der Akteur handelt nach der Politik $$\pi_\theta$$. Um die Varianz des Gradienten zu reduzieren, wird ein Kritiker eingesetzt. Dieser Kritiker wird durch $$\omega$$ parametrisiert. Während es mehrere mögliche Kandidaten für den Kritiker gibt, ist eine gängige Wahl die Vorteilsfunktion

wie sie in Advantage Actor-Critic (A2C) und Asynchronous Advantage Actor-Critic (A3C) verwendet wird. $$V_\omega (s)$$ ist die Wertfunktion

und quantifiziert, wie "gut" es ist, im Zustand $$s$$ zu sein. Die Parameter von $$\pi_\theta$$ werden entsprechend dem Gradienten optimiert:  

Zusammenfassend lässt sich sagen, dass bei Actor-critic-Methoden wie A2C der Akteur, repräsentiert durch die Strategie $$\pi_\theta$$, und ein Kritiker, hier repräsentiert durch die Wertfunktion $$V_\omega$$, durch Anpassung der Parameter $$\theta$$ und $$\omega$$ trainiert werden müssen. Wie beim Q-Learning können $$\pi_\theta$$ und $$V_\omega$$ mit Deep Neural Networks approximiert werden.

Partially Observable Markov Decision Process (POMDP)

Im vorhergehenden Beitrag dieser Serie haben wir den MDP vorgestellt. Für viele Anwendungen in der realen Welt müssen wir dieses Konzept ein wenig erweitern. Bei einem MDP weiß der Lernende, in welchem Zustand er sich befindet, d.h. der Zustand $$s \in S$$ ist vollständig beschrieben. Es könnte jedoch eine gewisse Unsicherheit in den Beobachtungen des Zustands bestehen. Dies könnte darauf zurückzuführen sein, dass der Agent nur begrenzte Informationen über den wahren Zustand der Umgebung hat, z.B. ein Roboter, der mit einer komplexen Außenwelt auf der Grundlage begrenzter Sensoreingaben interagiert. Diese Situation wird durch einen Partially Observable Markov Decision Process (POMDP) modelliert.

Ein POMDP ist ein 6-Tupel $$(S, A, R, P, O, T)$$, wobei $$S$$ die Menge der Zustände, $$A$$ die Menge der Aktionen, $$R: S\times S \times A \rightarrow \mathbb{R}$$ eine Belohnungsfunktion, $$P: S \times S \times A \rightarrow \left[ 0, 1\right] $$ die bedingte Übergangswahrscheinlichkeit, $$O$$ die Menge der Beobachtungen und  $$T: S \times O \rightarrow \left[ 0,1 \right]$$ die bedingten Beobachtungswahrscheinlichkeiten sind.

In einem POMDP wird der Zustand der Umwelt $$s$$ dem Akteur nicht präsentiert, aber eine Beobachtung $$o \in O$$ wird mit Wahrscheinlichkeit $$T(o|s)$$ gegeben. Abgesehen davon funktioniert der POMDP genauso wie der MDP: der Akteur befindet sich im Zustand $$s \in S$$, beobachtet aber nur $$o \in O$$. Daraufhin entscheidet er sich, die Aktion $$a \in A$$ anzuwenden, und über die Übergangswahrscheinlichkeit $$P$$ wechselt der Akteur in einen neuen Zustand $$s'$$. Für diesen Übergang wird der Akteur mit $$R(s, s', a)$$ belohnt. Beachten Sie den Hauptunterschied zum MDP: Der Akteur wählt die Aktion auf der Grundlage der Beobachtung $$o$$ und nicht auf der Grundlage des zugrunde liegenden Zustands $$s$$.

Zwei der Hauptthemen des MARL sind die Nicht-Stationarität und die partielle Beobachtbarkeit. Einige neuere Veröffentlichungen sollen hier hervorgehoben werden, in denen diese Probleme behandelt werden.

MARL gibt es in mehreren verschiedenen Varianten, die durch die Beziehung der Agenten charakterisiert sind, siehe Zhang 2019. Es gibt das kooperative Umfeld, in dem die Agenten zusammenarbeiten, um eine bestimmte Aufgabe zu lösen, es gibt das kompetitive Umfeld, in dem die Agenten versuchen, sich gegenseitig in einem Spiel zu übertreffen, und es gibt das gemischte Umfeld, in dem die Beziehung der Agenten uneingeschränkt ist. Zur Zeit wird MARL hauptsächlich in der Wissenschaft erforscht, und es gibt noch wenig Beispiele für Anwendungen in der realen Welt. Bei dida haben wir uns jedoch mit der Deutschen Bahn zusammengetan, um Anwendungen von MARL für das Kapazitäts- und Verkehrsmanagement zu erforschen. Wir stellten fest, dass dieses spezielle Problem, aber auch andere Probleme von industriellem Interesse, wie z.B. Ressourcenallokation und Netzoptimierung, in der kooperativen MARL-Situation interpretiert werden können. Daher gebe ich einen kurzen Überblick über interessante Ansätze, die MARL zu einem praktikablen Ansatz für viele Probleme machen.

Formale Aspekte

Die Problemstellung von MARL kann mit dem Begriff des stochastischen Spiels formalisiert werden.

Ein stochastisches Spiel für N Spieler ist das Tupel $$(S, A_1, A_2, ... , A_N, R_1, R_2, ..., R_N, P)$$, wobei $$S$$ die Menge der Zustände ist, $$A_i$$ die Menge der Aktionen des Agenten $$i$$, $$R_i: S \times A_1 \times ... \times A_N \rightarrow \mathbb{R}$$ die Belohnung von Agent $$i$$ und $$P: S \times S \times A_1 \times ... \times A_N \rightarrow [0, 1]$$ die bedingte Übergangswahrscheinlichkeit ist.

Im Zustand $$s \in S$$ wählt jeder Agent $$i$$ eine Aktion $$a_i \in A_i$$ und das Spiel geht in den Zustand $$s' \in S$$ mit der Wahrscheinlichkeit $$P(s'|s, a_1, ... , a_N)$$ über. Als Folge davon erhält jeder Agent $$i$$ eine Belohnung $$R_i(s, s', a_1, ..., a_N)$$. Analog zum Single-Agent RL wird jeder Agent $$i$$ durch seine Strategie $$\pi_i: S \times A_i \rightarrow [0, 1]$$ repräsentiert. Die einzelnen Aktionen werden oft als gemeinsame Aktion $$\pmb{a} = [a_1, ..., a_N]$$ geschrieben und die Strategien werden zur Strategie $$\pmb{\pi}(\pmb{a} | s) = [\pi_1(a_1|s), ..., \pi_N(a_N|s)]$$ zusammengefasst.

Jeder Agent $$i$$ hat seine eigene Wertfunktion $$v_i^{\pmb{\pi}}$$ unter der gemeinsamen Strategie

wobei $$r_{t,i} = R(s_t, s_{t+1}, a_{t,1}, ..., a_{t,N})$$. Die Q-Funktion ist sehr ähnlich definiert:

Mit diesen Notationen sieht MARL ziemlich ähnlich aus wie der Fall des Einzelagenten. Das Setting, kooperativ, kompetitiv oder gemischt, wird durch die jeweiligen Belohnungsfunktionen bestimmt.

Dezentralisierte Akteure

In Lee 2019 versuchen die Autoren, ein kooperatives MARL-Szenario mit teilweiser Beobachtbarkeit durch einen dezentralen Imitationslernansatz zu lösen. Die wichtigsten Beiträge sind eine verbesserte Trainingsmethode für dezentralisierte Akteure durch den Einsatz von Actor-critic RL mit einem zentralen Kritiker und die Verbesserung der Trainingsdaten durch Beispiele aus einer Referenzstrategie. Da die Kritik nur während des Trainings relevant ist, werden die Akteure zur Testzeit dezentralisiert. Die zur Verbesserung der Trainingsdaten verwendete Referenz-Strategie ist eine traditionelle MARL-Lösung. Dies ermöglicht es, globale Informationen des Systems zu sammeln, um das Training von unabhängigen Akteuren mit begrenzter Sichtbarkeit zu informieren.

Lernen effizienter Kommunikation

In Kim 2019 nutzen die Autoren auch das Actor-critic Deep Reinforcement Learning, um dezentrale Akteure mit einem zentralen Kritiker zu trainieren. Sie nannten ihren Algorithmus SchedNet. Das Problem war wieder voll kooperativ, und die Akteure mussten effiziente Kommunikation über einen Kanal mit begrenzter Bandbreite lernen, d.h. nur eine begrenzte Anzahl von Agenten durften zu einem bestimmten Zeitpunkt ihre Informationen austauschen. Dazu mussten die Agenten lernen, ihren eigenen Nachrichten Gewichtungen zuzuweisen, und ein Scheduler versandte die Nachrichten auf der Grundlage dieser Gewichtungen. Ein Agent bestand aus drei Neuronalen Netzen, jeweils eines für die Nachrichtengenerierung, die Gewichtungsgenerierung und die Aktionsauswahl. Die Aktionen wurden durch die empfangenen Nachrichten bestimmt. Der Algorithmus wurde in einem Räuber-Beute-Szenario getestet und mit Algorithmen ohne Kommunikation und mit Kommunikation ohne intelligentes Scheduling für die Nachrichten verglichen. SchedNet erwies sich als überlegen gegenüber seinen Konkurrenten und wurde nur von Agenten übertroffen, deren Kommunikationsbandbreite unbegrenzt war. Dies zeigt, dass eine effiziente Kommunikation den dezentralen Akteuren dabei helfen kann, Multi-Agenten-Aufgaben viel effektiver zu lösen, und dass die entsprechende Kommunikation auch erlernbar ist.

Mean-field MARL

Je mehr Agenten in einer Umgebung interagieren, desto größer wird der Raum der möglichen Interaktionen zwischen den Agenten. Dies kann das Lernen behindern und die Anzahl der Agenten begrenzen, die in der Umgebung eingesetzt werden können, bevor die Ausbildung nicht mehr konvergiert. In Yang 2018 gehen die Autoren dieses Problem an, indem sie das Problem auf MARL mit nur zwei Agenten reduzieren, indem sie eine Molekularfeldapproximation verwenden. Normalerweise würde die Q-Funktion in MARL einen exponentiell großen Vektor von Aktionen erfordern. Diese Komplexität kann reduziert werden, indem nur eine begrenzte Anzahl von Agenteninteraktionen berücksichtigt wird, z.B. die Interaktionen zwischen einem Agenten und seinen nächsten Nachbarn. Für eine große Anzahl von Agenten könnte dies immer noch zu komplex sein. Daher reduzieren die Autoren das Problem auf eine Zwei-Agenten-Interaktion, indem sie nur die Interaktion zwischen einem Agenten und dem Mittelwert seiner nächsten Nachbarn betrachten. Mit diesem Ansatz gelingt es ihnen, eine viel größere Problemstellung zu lösen, als es mit den traditionellen MARL-Methoden möglich war.

Alles in allem ist MARL ein aufstrebendes Forschungsgebiet. Während industrielle Anwendungen in der Praxis noch sehr selten sind, gibt es viele mögliche Anwendungen, die untersucht werden. Ich hoffe, dass dieser Artikel einen breiten Überblick über die Möglichkeiten und Grenzen des Ansatzes gegeben hat, sowie eine Inspiration, MARL als eine Problemlösung zu betrachten.