Was ist Reinforcement Learning? (Teil 1)

MDP

Das mathematische Objekt im Zentrum von RL ist der Markov-Entscheidungsprozess (MDP). Ein MDP ist wie folgt definiert:

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

Reinforcement Learning bedeutet, dass ein Agent, bei dem es sich um einen Chatbot, ein selbstfahrendes Auto usw. handeln könnte, mit dem MDP interagiert, indem er sich in einem Zustand $$s \in S$$ befindet, in dem er eine Aktion $$a \in A$$$ wählen muss. Nach der Anwendung von $$a$$ auf die Umgebung befindet sich der Agent über die Übergangswahrscheinlichkeit $$s' \in S$$$ in dem Zustand $$s' \sim P(\cdot | s, a)$$. Für diesen Schritt wird der Agent mit $$R(s',s,a)$$$ belohnt oder bestraft. Ein bekanntes Beispiel aus der Praxis für diese Art des Lernens ist die operante oder instrumentelle Konditionierung in der Hundeerziehung. 

Das Verhalten des Agenten wird durch die "Strategie" $$\pi: A \times S \rightarrow \left[ 0,1 \right]$$ dargestellt: das ist die Wahrscheinlichkeit, dass er die Aktion wählt $$a$$, wenn er sich im Zustand $$s$$ befindet. Das Ziel des Agenten ist es, eine optimale Strategie $$\pi^{\ast}$$ zu erlernen, so dass die erwartete kumulative diskontierte Belohnung maximiert wird, d.h.

[Loss]

wobei $$r_t := R(s_{t+1}, s_t, a_t)$$ die im Zeitschritt  $$t$$ erhaltene Belohnung ist und $$s_{t+1} \sim P(\cdot | s_t, a_t)$$. $$T$$ ist die Anzahl der im MDP unternommenen Schritte, und oft haben wir $$T \rightarrow \infty$$. $$\gamma$$ ist nur ein Reduktionsfaktor, der $$0\leq \gamma \leq 1$$ erfüllt.

Im Allgemeinen kann es sein, dass $$P$$ dem Agenten unbekannt ist (modellfreies RL), aber der MDP kann gesamplet werden und das Optimierungsproblem [Loss] kann mit Monte-Carlo-Simulationen gelöst werden.

Modellfreie RL-Algorithmen können weiter kategorisiert werden, wie $$\pi$$ behandelt wird. Es gibt die Kategorie, in der $$\pi$$ direkt modelliert wird, die als strategiebasierte RL bekannt ist. Auf der anderen Seite gibt es die wertbasierte RL, die wir hier diskutieren werden. Der Name lässt bereits vermuten, dass wertbasierte RL-Methoden auf irgendeiner Wertfunktion beruhen. Üblicherweise ist die interessierende Wertfunktion die so genannte $$Q$$-Funktion. Die $$Q$$-Funktion $$Q(s, a)$$ bildet Zustands-Aktions-Paare auf die erwartete Belohnung ab, wenn der Agent im Zustand $$s$$ gestartet ist und die Aktion $$a$$ durchgeführt hat, d.h.

[DefQfunction]

wobei $$\pi$$$ eine "gierige" Strategie in Bezug auf die Q-Funktion ist. Eine gierige Strategie ist eine Strategie, bei der $$s$$ in jedem Zustand immer die Aktion $$a = {\mathrm{argmax}}_{a'} Q(s, a')$$ wählt. Vereinfacht kann man sich vorstellen, dass die Q-Funktion $$Q(s, a)$$$ misst, wie "gut" es wäre, im Zustand $$s$$ die Handlung $$a$$ auszuführen und in allen nachfolgenden Zuständen gierig zu handeln.

Dies wirft die Frage auf, wie $$Q(s, a)$$ aus der Stichprobe des MDP gelernt werden kann. Im MDP beobachtet der Agent bei jedem Zeitschritt $$t$$ eine Erfahrung $$(s_t, a_t, s_{t+1}, r_t)$$, die manchmal auch als "Übergang" bezeichnet wird. Am Anfang können wir die Q-Funktion zufällig erraten und mit der Simulation des MDP beginnen. Nach jedem Übergang führen wir den Aktualisierungsschritt durch:

[QLearningUpdate]

mit $$\alpha$$ als Lernrate. Wenn $$s_{t+1}$$ ein Endstatus des MDP ist, sieht der Aktualisierungsschritt wie folgt aus:

[QLearningUpdateTerminal]

[QLearningUpdate] kann umgeschrieben werden als

[QLearningUpdate2]

Der eingeklammerte Begriff auf der rechten Seite wird als temporaler Differenz-(TD-)Fehler bezeichnet, daher wird diese Art des Q-Lernens als temporales Differenzlernen bezeichnet.

Q-Learning funktioniert durch Stichproben des MDP und Aktualisierung der Q-Funktion entsprechend den gesammelten Erfahrungen. Eine Eigenschaft des MDP ist, dass Entscheidungen, die früher getroffen werden, einen Einfluss auf die Zustände haben, die der Agent während der gesamten Laufzeit des MDP durchlaufen wird, was wiederum die gesammelten Erfahrungen und die vorgenommenen Aktualisierungen der Q-Funktion beeinflusst.

Betrachten Sie einen Agenten, der nur Aktionen ausführt, die gemäß seiner aktuellen Q-Funktion optimal sind. Der Agent dringt tief in das MDP vor und sammelt wertvolle Erfahrungen für spätere Phasen. Das heißt, der Agent nutzt sein aktuelles Wissen, um Erfahrungen zu sammeln, die wertvoll sind. Die aktuelle Q-Funktion könnte jedoch nicht optimal sein und zu einem suboptimalen Verhalten führen. Es könnte für den Agenten vorteilhaft sein, neue Wege zu erkunden, z.B. durch das zufällige Erraten einiger Aktionen. Dies wird zu zufälligen Erfahrungen führen und könnte helfen, neue, möglicherweise bessere Strategien zu entdecken. Dieses Dilemma ist als der Kompromiss zwischen Exploration (Erkundung) und Exploitation (Ausbeutung) bekannt.

Es gibt einige Möglichkeiten, diesen Kompromiss auszuhandeln. Der bekannteste Ansatz wäre die Anwendung einer $$\epsilon$$-gierigen Strategie. $$\epsilon$$-gierig bedeutet, dass der Agent im Zustand $$s$$ die gierige Aktion $$a = {\mathrm{argmax}}_{a'} Q(s, a')$$ mit einer Wahrscheinlichkeit von $$1-\epsilon$$ für irgendein $$\epsilon \in [0,1]$$ auswählt und ansonsten $$a$$ nach dem Zufallsprinzip (gleichverteilt) probiert. Gewöhnlich wird $$\epsilon = 1$$ zu Beginn des Trainings gewählt und im Laufe der Trainingszeit durch einen Abbauplan verringert, z.B. $$\epsilon(t) = k^{-t}$$ für einen Abbauparameter $$k < 1$$.

Bislang haben wir keine Annahmen über die Implementierung der Q-Funktion getroffen. Im Prinzip könnte es eine einfache Tabelle sein. Dies ist jedoch für viele Anwendungen technisch nicht machbar, da der Zustandsraum $$S$$ zu groß wäre. Wenn $$S$$ kontinuierlich ist, müssten wir außerdem eine Diskretisierung einführen, die im Allgemeinen recht verlustbehaftet ist. Ein echter Durchbruch im Bereich RL wurde von DeepMind 2013 mit der Einführung von Deep Q-Learning (DQN) erreicht.

Im DQN wird die Q-Funktion durch ein tiefes neuronales Netzwerk (DNN) approximiert, das $$s$$ als Input nimmt und einen Vektor ausgibt, wobei das $$a$$$-te Element der Q-Wert für die Aktion $$a$$ ist, d.h. $$Q_a(s|\theta)$$, wobei $$\theta$$ die Menge der Parameter des neuronalen Netzwerks ist. Um ein DNN als Näherungswert für die Q-Funktion zu verwenden, müssen die Aktualisierungsregeln [QLearningUpdate] und [QLearningUpdateTerminal] so umformuliert werden, dass sie mit Gradientenabstieg durchgeführt werden können. Betrachten Sie

[DQNUpdate]

mit der Verlustfunktion

[DQNLoss1]

wenn $$s_{t+1}$$ ein nicht-terminaler Zustand des MDP ist und

[DQNLoss1Terminal]

wenn $$s_{t+1}$$$ terminal ist. Beachten Sie, wie im Zielwert $$r_t + \gamma \max_{a'} Q_{a'}(s_{t+1}|\theta')$$ ein anderer Satz von Parametern $$\theta'$$ verwendet wird. Der Grund dafür ist, dass der Gradientenabstieg das Q-Netz nur in Richtung des Zielwertes aktualisieren und den Zielwert fixieren sollte. In der Praxis kann dies erreicht werden, indem man zunächst den Zielwert berechnet und diesen in der Verlustfunktion als konstant betrachtet.

Es hat sich auch gezeigt, dass das Training stabiler ist, wenn $$\theta'$$ nicht nach jedem Gradientenabstiegsschritt aktualisiert wird, sondern nur mit einer bestimmten Periode, z.B. jedem 10., 100. oder 1000. Auf diese Weise werden störende Rückkopplungsschleifen von Rauschen vermieden. Um die verzögerte Aktualisierung von $$\theta'$$ zu realisieren, wird ein Sekundärmodell mit den Parametern $$\theta'$$ beibehalten, wobei $$\theta'$$ nur entsprechend der Aktualisierungsperiode aktualisiert wird. Dieses sekundäre Modell wird als Zielnetz oder Zielmodell bezeichnet.

Double Deep Q-Learning

Ein Problem mit dem TD-Fehler [DQNLoss1] besteht darin, dass im Zielwert das Maximum über $$a'$$ verwendet wird. Dies führt dazu, dass die Q-Funktion die Q-Werte überschätzt. Um diesen Effekt abzuschwächen, wurde das Double Deep Q-Learning eingeführt. Beim Double Deep Q-Learning erfordert der Zielwert zwei verschiedene Netzwerke, eines für die Wahl der optimalen Aktion im nächsten Zustand und eines für den Q-Wert dieser Aktion. In der Praxis wird die Aktion mit dem Primärmodell gewählt, während der Q-Wert aus dem Zielmodell entnommen wird. Die Verlustfunktion sieht nun wie folgt aus:

[DQNLoss2]

mit

[DQNLoss3]

Beachten Sie die unterschiedlichen Q-Funktions-Parameter $$\theta$$ und $$\theta'$$ in [DQNLoss2] und [DQNLoss3]. Auf diese Weise führt die Minimierung des TD-Fehlers nicht notwendigerweise zu einer Verschiebung der Q-Funktion in Richtung des Maximalwertes des Ziels und hilft somit, eine Überschätzung der Q-Funktion zu vermeiden.

Experience Replay Buffer

Das folgende Problem kann auftreten, wenn ein DNN als Q-Funktions-Approximator verwendet wird: Bei der Aktualisierung der Modellparameter wird nicht nur der Q-Wert des bestimmten Trainingsdatenpunktes geändert, der zur Berechnung des TD-Fehlers verwendet wird. Tatsächlich ändern sich die Q-Werte für viele Aktionszustandspaare auf unkontrollierte Weise. Dies kann zu einem so genannten "katastrophalen Vergessen" führen. Mnih 2015 führte eine Technik namens Experience Replay Buffer (RB) ein, um diesen Effekt abzuschwächen.

Der Übergang $$(s_t, a_t, s_{t+1}, r_t)$$ wird im RB gespeichert. Sobald die Parameter des Q-Funktions-Approximators aktualisiert sind, wird das DNN nicht auf diesen einzelnen Übergang trainiert, sondern auf einen Mini-Batch der Größe $$M$$ von zufällig ausgewählten Übergängen aus der RB. Daher werden bei der Aktualisierung der Modellparameter auch Übergänge aus der Vergangenheit verwendet. Dies hilft, katastrophales Vergessen zu verhindern.

Der Algorithmus

Setzt man alle diskutierten Konzepte zusammen, ergibt sich folgender Algorithmus. $$\theta$$ und $$\theta_{Ziel}$$ parametrisieren die Primär- bzw. Zielmodelle, $$k$$ ist der $$\epsilon$$-Zerfallszeitplan, $$\alpha$$ die Lernrate, $$\gamma$$ der Diskontierungsfaktor für die diskontierte Belohnung, $$T_{max}$$ die maximale Anzahl der auszuführenden Schritte, $$T_{Update}$$ der Zeitraum der Aktualisierungen des Zielmodells und $$M$$ die aus dem RB zu entnehmende Stichprobengröße.

Lassen Sie uns ein kleines Beispiel diskutieren. Wir verwenden eine Umgebung aus der OpenAI Gym-Bibliothek. OpenAI Gym ist eine Python-Bibliothek, die verschiedene kleine Spiele zum Spielen implementiert. Wir wählen die LunarLander-Umgebung. Das Ziel ist es, die Mondlandefähre auf einem Landeplatz zu landen, ohne sie abstürzen zu lassen. Der Standort des Moduls wird durch die Koordinaten $$x$$ und $$y$$ beschrieben, während der Ursprung dieses Koordinatensystems in der Mitte des Landeplatzes liegt. Zu Beginn jeder Episode beginnt das Modul oberhalb des Landeplatzes mit einer zufällig gewählten, aber kleinen Geschwindigkeit. Die Mondlandefähre hat zwei Beine, die den Boden berühren müssen, um zu landen. Die Beine sind über Federn an der Mondlandefähre befestigt. Wenn die Federn so zusammengedrückt werden, dass beide oder eines der Beine die Mondlandefähre berührt, ist die Episode beendet. Auf diese Weise soll der Agent das Fliegen lernen und das Modul vorsichtig landen, anstatt es auf den Boden zu prallen.

Zur Steuerung verfügt das Modul über drei Motoren: den nach unten gerichteten Hauptmotor und zwei weniger leistungsstarke Seitenmotoren. Die Zündung der Triebwerke wird durch kleine rote Kugeln modelliert, die in die Richtung des jeweiligen Triebwerks ausgestoßen werden, wobei eine kleine zufällige Störung zu ihrer Dynamik beiträgt. Die Abstoßung durch den Auswurf der Kugeln treibt die Mondlandefähre an. Das Haupttriebwerk ist viel leistungsstärker als die seitlichen Triebwerke, da das Haupttriebwerk zum Schweben verwendet werden soll, während die seitlichen Triebwerke zum Ausbalancieren der Mondlandefähre dienen.

Die Dimension des Zustandsraums ist $$\dim(S) = 8$$, wobei jeder Zustand $$s$$ gegeben ist durch

wobei $$x$$ und $$y$$ die Koordinaten des Schwerpunkts des Moduls sind, $$\dot{x}$$ und $$\dot{y}$$ die jeweiligen Geschwindigkeiten, der Winkel $$\phi$$ beschreibt die Neigung des Moduls und $$\dot{\phi}$$ die jeweilige Winkelgeschwindigkeit. $$C_r$$ und $$Cl$$ sind boolesche Variablen und gleich 1, wenn das rechte oder linke Bein den Boden berührt, und sonst gleich 0. Die Dimension des Aktionsraums ist $$\dim(A) = 4$$, wobei der Agent wählen kann, nichts zu tun ($$a_1$$), den rechten Seitenmotor zu zünden ($$a_2$$), den Hauptmotor zu zünden ($$a_3$$) oder den linken Seitenmotor zu zünden ($$a_4$$).

Die Belohnung im Zeitschritt $$t$$ wird ausgestellt nach

[LunarLanderReward]

wobei $$F_\text{main}$$ und $$F_\text{side}$$ boolesche Variablen sind, die angeben, ob die Haupt- oder einer der Seitenmotoren gezündet wurde. Die tiefgestellten $$t$$ und $$t-1$$ geben die Zeitschritte an. Die Belohnung [LunarLanderReward] gibt dem Agenten einen Anreiz, den Lunar Lander in Richtung des Landeplatzes am Ausgangspunkt zu bewegen, was durch die ersten beiden Begriffe in den Klammern beschrieben wird. Darüber hinaus wird es belohnt, die Geschwindigkeiten begrenzt zu halten, da der dritte und vierte Term belohnt, langsamer zu fliegen als im vorherigen Zeitschritt. Es wird auch belohnt, die Neigung des Moduls zu verringern. Die Terme $$+ 10(C_{rt}-C_{rt-1}) + 10(C_{lt}-C_{lt-1})$$ belohnen Bodenkontakt für jedes Bein und bestrafen, wenn die Beine den Bodenkontakt unterbrechen. Die letzten beiden Begriffe bestrafen den Einsatz der Motoren. Dies gibt dem Agenten einen Anreiz, mit weniger Triebwerksverbrauch zu fliegen, obwohl in dieser simulierten Umgebung der Treibstoff nicht begrenzt ist. Wie oben erwähnt, endet die Episode, wenn das Modul auf den Boden aufprallt, so dass die Beine das Modul berühren. In diesem Fall wird anstelle von [LunarLanderReward] eine Belohnung von -100 vergeben. Wenn das Modul zum Stillstand kommt, ohne abzustürzen, endet auch die Episode, und dem Agenten wird eine Belohnung von 100 ausgehändigt.

Weitere Einzelheiten finden Sie in der Dokumentation oder im Original-Quellcode.  

In der folgenden Animation können wir sehen, wie sich der Agent im Laufe der Zeit bei der Landung des Moduls langsam verbessert.

Während der Lander anfangs einfach hoffnungslos auf den Boden knallt, lernt der Agent nach etwa 500 Trainingsepisoden das Schweben. Danach sind die Landungen sehr wackelig, aber mit der Zeit werden sie immer sicherer. Die Leistung könnte sich mit mehr Training wahrscheinlich noch verbessern.

Deep Q-Learning ist ein sehr grundlegender Ansatz für RL, aber er erlaubt es, einige der Herausforderungen hervorzuheben, die bewältigt werden müssen, um gute Lösungen für RL-Probleme zu finden. Es gibt ein paar Probleme, die angegangen werden müssen.

Kontinuierliche Aktionsräume

Bisher sind wir stillschweigend davon ausgegangen, dass der Aktionsraum $$A$$ diskret ist, oder zumindest ausreichend gut diskretisiert werden kann. Oftmals ist dies nicht möglich und es wird eine Möglichkeit benötigt, mit kontinuierlichen $$A$$ umzugehen. Der grundlegende Algorithmus zur Verwendung von DNNs für kontinuierliche $$S$$ und $$A$$ ist der Deep Deterministic Policy Gradient (DDPG).

Effiziente Exploration

Während $$\epsilon$$-gierig die bekannteste Lösung für den Kompromiss zwischen Exploration und Exploitation ist, gibt es aktive Forschung zu anderen Methoden, die sich in einigen Fällen als effizienter erwiesen haben. Vor allem versucht man, Bayes'sche Methoden zu verwenden und sie mit Techniken des Tiefen Lernens zu kombinieren.

Multi-Agenten RL

Oben haben wir ausschließlich RL-Algorithmen diskutiert, die einen einzigen Agenten verwenden, der sich mit der Umgebung auseinandersetzt. Für viele Aufgaben ist es notwendig, mehrere unabhängige Agenten zu haben, die ihre Bemühungen koordinieren, um ein gemeinsames Ziel zu erreichen, oder die um Ressourcen konkurrieren, um divergierende Ziele zu erreichen. Dies ist der Bereich des Multi-Agenten-RL (MARL). MARL wird aktiv erforscht, und in den letzten Jahren sind einige beeindruckende Fortschritte erzielt worden. MARL wird im nächsten Beitrag dieser Reihe ausführlicher behandelt.

Einige Nachteile

RL ist einer der vielversprechendsten Ansätze zu dem, was einige als künstliche "Intelligenz" bezeichnen könnten. Es gibt jedoch einige Probleme. Erstens hängen RL-Algorithmen stark von der Fähigkeit ab, den Prozess abzutasten, den sie kontrollieren sollen. Der Agent muss aus Versuch und Irrtum lernen, indem er das Szenario immer und immer wieder wiederholt, gewöhnlich Tausende von Malen. Dies ist in der realen Welt nicht durchführbar, daher muss eine Simulationsumgebung bereitgestellt werden. Dies wiederum erfordert einen hohen Aufwand, da die Simulation jeden relevanten Aspekt des vorliegenden Problems erfassen muss.

Das zweite Problem stellt sich insbesondere dann, wenn DNNs als Q-Funktions-Approximatoren verwendet werden. DNNs sind berüchtigte "Black Boxes". Ihre innere Logik wird oft nicht gut verstanden, so dass Sicherheitsaspekte und die Art und Weise, wie der Agent lernt, über seine Umgebung nachzudenken, mit besonderer Vorsicht behandelt werden müssen. Es gab Beispiele dafür, dass RL-Agenten scheinbar in der Lage waren, eine Aufgabe perfekt zu lösen, und später stellte sich heraus, dass sie ihre Entscheidungen auf der Grundlage von Artefakten der Simulation trafen. Sobald sie mit einem etwas anderen Szenario konfrontiert wurden, begannen die Agenten, überraschend für ihre Entwickler, zu versagen.

Ein weiteres Problem ist die Belohnungsfunktion. Sie muss so gestaltet werden, dass sie Anreize für das gewünschte Verhalten schafft und unerwünschte Aspekte bestraft. Andernfalls könnte der Agent Strategien finden, die numerisch optimal sind, aber das wahre Ziel vernachlässigen.

Ich hoffe, Sie konnten sich einen Überblick über das Thema Reinforcement Learning und einige seiner Herausforderungen verschaffen. Im nächsten Teil werden wir den Stand der Technik von MARL ausführlicher diskutieren.