Beim Reinforcement Learning befindet sich ein sogenannter Agent in einer abgegrenzten Umgebung und interagiert mit dieser. In dieser Umgebung soll der Agent mittels der Trial-and-Error-Methode eine Strategie entwickeln, die auf der Gabe von hypothetischen virtuellen Belohnungen basiert. Im Englischen wird die entwickelte Strategie als Policy und die Belohnungen als Rewards bezeichnet. Der Agent observiert die Umgebung und soll darauf aufbauend die bestmögliche Aktion aus einem Satz unterschiedlicher Aktionen finden, die die maximale Belohnung garantiert. Diese Observation der Umgebung durch den Agenten wird durch einen sogenannten Interpreter gesteuert, der die Umgebung analysiert.
Eine Aktion des Agenten verändert die Umgebung und der Interpreter berechnet daraufhin den Reward für die durchgeführte Aktion, sowie den neuen Zustand der Umgebung und übermittelt beides an den Agenten. Dieser Vorgang wird in der Regel so lange wiederholt, bis der Agent seine Aufgabe abgeschlossen hat. Handelt es sich bei dem Agenten zum Beispiel um ein autonomes Fahrzeug, wird es so lange Aktionen, in diesem Falle Fahrmanöver ausführen, bis er am gewünschten Zielort angelangt ist.
Diesen und andere Beiträge von mir kannst du als sauber formatierte PDF-Datei zum Ausdrucken oder offline Lesen erwerben. Mehr Informationen dazu findest du hier.
Zu diesem Artikel findest du auch ein Video von mir auf YouTube.
Nötige Vorkenntnisse
Um die Idee hinter der Policy beim Reinforcement Learning verstehen zu können, solltest du grundlegende mathematische Kenntnisse von Funktionen, Mengen und Statistik haben.
Reinforcement Learning Beispiel
Betrachten wir nun einmal ein vereinfachtes Beispiel eines Saugroboters in einer Wohnung. Das Quadrat auf der linken Seite der obigen Abbildung zeigt eine Wohnung von oben und ist unterteilt in $5\times5$ kleinere Quadrate. Der rote Kreis stellt einen Saugroboter dar, der sich innerhalb dieser Wohnung befindet. Dieser Saugroboter hat am unteren Ende der Wohnung eine Ladestation. Insgesamt sind vier Flächen dieser Wohnung verdreckt und die Aufgabe des Saugroboters ist es diese zu säubern und anschließend zur Ladestation zurückzukehren. Zusätzlich wird die Wohnung durch weitere Wände unterteilt, die die Bewegungsmöglichkeiten des Saugroboters einschränken.
Mittels dieser simulierten Umgebung lassen sich jetzt Daten erzeugen, mit denen der Agent seine Strategie erlernen kann. Dabei wird ihm die gleiche Aufgabe, hier das Säubern der Wohnung, immer wieder gestellt. Es kann mehrere hundert oder tausende Iterationen dauern, bis der Agent eine für uns sinnvolle Strategie zum Säubern der Wohnung durchläuft. Vor allem zu Beginn wird er sich vermutlich nur unkontrolliert hin und her bewegen und mehr durch Zufall als durch eine wirkliche Strategie einen Teil der Wohnung vom Dreck befreien.
Strategie (Policy)
Betrachten wir nun einmal die zu berechnende Strategie, also die Policy, des Agenten genauer. Wenn es sich um eine nicht deterministische Policy handelt, wird diese zumeist mit dem Buchstaben $\pi$ dargestellt. Deterministische Policies sind eine vereinfachte Version nicht deterministischer Policies, worauf ich dann an den entsprechenden Stellen kurz verweisen werde. Die Policy $\pi$ ist letztlich nicht anderes als eine Funktion mit zwei Input Variablen aus den Mengen $A$ und $S$:
$\pi: A \times S$
$A$ ist dabei die Menge der möglichen Aktionen eines Agenten und die $S$ die Menge der möglichen Zustände. Wir könnten hier also auch einfach $\pi(a, s)$ schreiben, wobei $a \in A$ und $s \in S$ gilt. Um zu verdeutlichen, was diese beiden Menge $A$ und $S$ eigentlich aussagen, gehen wir jetzt noch einmal zu dem Beispiel mit dem Saugroboter über.
Policy am Beispiel Saugroboter
Betrachten wir einmal die möglichen Aktionen des Saugroboters. Dieser kann sich immer je ein Feld nach links, rechts, oben oder unten bewegen. Diagonale Bewegungen lassen wir an dieser Stelle einmal außen vor. Weiterhin kann der Saugroboter ein kleines Quadrat vom Dreck reinigen und es sauber zurücklassen. Insgesamt stehen dem Saugroboter also fünf mögliche Aktionen zur Verfügung.
Gehen wir nun zu den möglichen Zuständen über. Die Position des Saugroboters innerhalb der Wohnung ist ein Teil des Zustands. Da es sich um ein $5 \times 5$ Gitter handelt, gibt es insgesamt $25$ mögliche Positionen des Saugroboters. Zusätzlich gehört Anzahl und Position des Drecks in der Wohnung zum Zustand der Umgebung. Wir gehen davon aus, dass sich die Position und Anzahl des Drecks in jedem neuen Durchlauf dieses Beispiels verändern kann. So erlernt der Agent nicht einfach nur eine festgelegte Position zu säubern, sondern nur die Stellen, an denen sich auch wirklich Dreck befindet.
In einfachen Szenarien, bei denen sonst keine Änderungen in der Umgebung stattfinden, würde diese Angabe des Zustands bereits ausreichen. Wenn sich zusätzlich auch die Position der Ladestation in jedem Durchlauf verändern soll, so muss diese auch mit übergeben werden. Wird die Position der Ladestation nie verändert, dann muss diese auch nicht mit übergeben werden. Das Gleiche gilt für die zusätzlichen Wände innerhalb der Wohnung. Möchte man, dass der Saugroboter in unterschiedlichen Wohnungen arbeiten kann, so müssen beim Training auch unterschiedliche Positionen der Wände berücksichtigt werden.
Policy Funktion
Springen wir zurück zur Policy des Agenten. Der Output der Funktion $\pi (a, s)$ liegt im Intervall $[0,1]$:
$\pi: A \times S \rightarrow [0,1]$
Diese Zahl gibt die Wahrscheinlichkeit an, mit der die Aktion $a$ ausgeführt wird, wenn der Agent sich im Zustand $s$ befindet. Dies lässt sich auch schreiben als $p(a|s)$:
$\pi (a, s) = p(a|s)$
Man kann dies ausdrücken als die Wahrscheinlichkeit für $a$, wenn $s$ bereits eingetreten ist. Bei deterministischen Policies würde der Teil mit der Wahrscheinlichkeit wegfallen, das heißt, wenn sich der Agent in einem Zustand $s$ befindet, wird immer eine festgelegte Aktion $a$ ausgeführt.
Betrachten wir nun einmal die drei Zustände $s_1$, $s_2$ und $s_3$. Wir befinden uns einmal beispielhaft im Zustand $s_1$ und haben jetzt die Möglichkeit eine der beiden Aktionen $a_1$ und $a_2$ auszuführen, wie in der oberen Abbildung links dargestellt. Nehmen wir einmal an, die Policy $\pi (a, s)$ würde für diesen Fall, also ausgewertet für den Zustand $s_1$, eine Wahrscheinlichkeit von $0.6$ für $a_1$ und eine Wahrscheinlichkeit von $0.4$ für $a_2$ ausgeben, wie auch noch einmal auf der rechten Seite grafisch dargestellt. Beispielhaft könnte sich jetzt während der Optimierung der Policy zeigen, dass die Aktion $a_2$ deutlich besser ist, als die Aktion $a_1$. Dementsprechend würde die Wahrscheinlichkeit für $a_2$ erhöht und für $a_1$ gesenkt, wie im unteren Bild zu sehen.
Schauen wir uns nun einmal an, was danach passiert. Nach Ausführung der Aktion $a_1$ im Zustand $s_1$ nehmen wir an, dass es möglich ist, dass wir in den Zustand $s_1$ zurückkehren oder aber in Zustand $s_3$ übergehen, wie in der obigen Abbildung dargestellt. Damit nehmen wir automatisch an, dass sich Zustand $s_2$ nicht durch Ausführen der Aktion $a_1$ im Zustand $s_1$ erreichen lässt. Auch hierzu können wir beispielhaft Wahrscheinlichkeiten angeben, mit denen der Agent in den Zustand $s_1$ oder $s_3$ nach dem Ausführen der Aktion $a_1$ wechselt. Beachtet, dass der gesamte in Lila dargestellte Teil nicht zur Policy des Agenten gehört. Dieser Teil gehört zur Modellierung der Umgebung, in dem sich der Agent befindet.
Genauso kann man jetzt für die Aktion $a_2$ vorgehen, in der wir annehmen, dass wir nur den Zustand $s_2$ und $s_3$ erreichen können, nicht aber wieder den Zustand $s_1$. Äquivalent lässt sich das Verhalten des Agenten aufzeigen, wenn dieser sich in Zustand $s_2$ oder $s_3$ befindet. Auch dort kann der Agent eine der möglichen Aktionen ausführen und anschließend entweder in einen anderen wechseln, oder aber in den gleichen Zustand zurückkommen.
An dieser Stelle fehlt nun noch der Reward des Agenten, den er für die Ausführung der E erhält. Ich habe dies einmal beispielhaft in der obigen Abbildung in Gelb dargestellt. Die Rewards können sich dabei bei der gleichen ausgeführten Aktion unterscheiden, je nachdem in welchem Zustand sich der Agent nach dem Ausführen der Aktion befindet. Zum besseren Verständnis der Rewards schauen wir einmal zurück auf das eben beschriebene Beispiel mit dem Saugroboter.
Reward am Beispiel Saugroboter
In der folgenden Tabelle ist einmal am Beispiel des Saugroboters eine mögliche Vergabe von Rewards dargestellt:
| Aktion | Reward |
|---|---|
| Bewegung um ein Feld | -1 |
| Boden reinigen | 100 |
| Sauberen Boden reinigen | -30 |
| Gegen Wand fahren | -100 |
| Rückkehr Ladestation | 1000 |
Der am Ende der Tabelle vergebene Reward für die Rückkehr zur Ladestation wird nur bei vollständig gereinigtem Boden vergeben und stellt so die finale Belohnung für den Saugroboter dar.
Für jede Bewegung des Saugroboters in eine beliebige Richtung erhält der Saugroboter einen Reward von $-1$. Das heißt, wenn der Saugroboter sich zum Beispiel zu Beginn ein Feld nach oben bewegt, so ist der aktuelle Reward des Saugroboters $-1$. Bewegt sich dieser jetzt noch einmal nach oben und nach rechts, um zum oberen verdreckten Feld zu gelangen, liegt der Reward des Roboters bei insgesamt $-3$.
Das Ziel des Roboters ist es ja den Boden zu reinigen, sodass wird dies auch entsprechend honorieren sollten. Daher erhält der Agent einen Reward von $100$, wenn ein verdreckter Boden gereinigt wird. Nun bewegt sich der Roboter zum nächsten Feld mit Dreck und reinigt auch dieses, womit der aktuelle Reward auf insgesamt $193$ steigt. Nehmen wir jetzt an, der Roboter würde versuchen, nach unten zu fahren. Die Wand würde ihn logischerweise daran hindern. Das Fahren gegen eine Wand wird in diesem Beispiel mit einem Reward von $-100$ bestraft, womit der gesamte Reward wieder auf $93$ fällt.
Der Roboter bewegt sich ganz nach rechts, bleibt aber ein Feld vor dem verdreckten Boden stehen. Er führt anschließend die Aktion zum Säubern des Bodens auf, was bei einem sauberen Boden mit einem Reward von $-30$ bestraft wird. Anschließend macht der Roboter es richtig, fährt nach unten und säubert den Boden. Es ist jetzt nur noch ein Feld zu reinigen und anschließend folgt die Rückkehr zur Ladestation. Die Rückkehr zur Ladestation bei vollständig gereinigtem Boden wird mit einem hohen Reward von $1000$ belohnt, da dies das eigentliche Ziel des Roboters ist. Am Ende steht ein Reward von $1252$ zu Buche.
Das Beispiel mit dem Saugroboter ist etwas einfacher gehalten als das mathematische Beispiel von eben. Wir nehmen nämlich an, dass sich der Saugroboter nach dem Ausführen einer Aktion nur in einem bestimmten neuen Zustand befinden kann und nicht mit einer gewissen Wahrscheinlichkeit auch in einem anderen Zustand. Es handelt sich bei diesem Beispiel also um eine deterministische Umgebung.
Man könnte dieses Beispiel aber dahin gehend erweitern, in dem man etwa die Möglichkeit betrachtet, dass mit einer gewissen Wahrscheinlichkeit der Saugroboter nicht in der Lage ist, den Dreck zu entfernen. Dann würde sich der Zustand des Systems nach dem Säubern des Bodens nicht ändern, da der Dreck weiterhin da ist. Dann müsste der Saugroboter einen neuen Versuch unternehmen, den Boden zu reinigen. Den Reward gibt es natürlich auch nur dann, wenn der Boden auch wirklich gesäubert wird.
Reinforcement Learning Algorithmen
Ich gehe nun am Ende dieses Artikels noch kurz auf verschiedene Typen von Algorithmen ein, mit denen ein Reinforcement Learning Agent trainiert werden kann. Ich werde an dieser Stelle jedoch nicht allzu sehr ins Detail gehen, sondern mehr einen groben Überblick bieten. Zwischen verschiedenen Reinforcement Learning Algorithmen wird vor allem unterschieden, ob es sich um modellbasierte oder modellfreie Algorithmen sind.
Modellbasierte Algorithmen
Unter den modellbasierten Algorithmen findet man die Modellierung des Systems als Markov Decision Process (MDP). Wenn wir im Artikel gedanklich noch einmal etwas zurückspringen, ist die eben gezeigte Darstellung von Zuständen, Aktionen, sowie den Übergangen zwischen diesen inkl. der Rewards nicht anderes als eine bildliche Darstellung eines Markov Decision Process:
Wobei hier, wie zuvor bereits gesagt, natürlich noch die Ausführungen von Aktionen in den Zuständen $s_2$ und $s_3$ fehlen. Um eine optimale Strategie in einem System zu finden, das durch einen Markov Decision Process modelliert wurde, existieren die beiden Algorithmen Policy Iteration und Value Iteration.
Eine andere Möglichkeit ein System zu modellieren, ist mittels eines Satzes von Differentialgleichungen, die in den meisten Fällen nicht linear sind. Die Lösung der Differentialgleichungen mit festgelegten Anfangsbedingungen und Constraints führt dann zu einem Optimal Control Problem (OCP), welches gelöst werden muss. Viele sehen diese Art von Algorithmen nicht als echte Reinforcement Learning Algorithmen an, da hier kein explizites Training eines Agenten mittels Rewards erfolgt. Stattdessen wird auf Basis einer Kostenfunktion ein optimales Verhalten des Agenten berechnet.
Modellfreie Algorithmen
Häufig sind die Systeme, in denen der Agent aktiv ist, jedoch so komplex, dass eine modellierte Darstellung des Systems schwierig bis unmöglich ist. Wenn wir zum Beispiel noch einmal das Saugroboterbeispiel betrachten, dann gibt es allein 25 mögliche Zustände für die Position des Roboters. Dies müsste man multiplizieren mit der möglichen Anzahl und Position des verdreckten Bodens. Allein in diesem einfachen Beispiel hätten wir damit bereits mehrere hundert, wenn nicht gar Tausende möglicher Zustände für dieses doch recht einfach wirkende System. Wenn man doch noch verschiedene Positionen der Ladestation und der Wände betrachtet, wird es weitestgehend unmöglich den Überblick zu behalten. Hinzu kämen dann natürlich noch die fünf möglichen Aktionen des Saugroboters in jedem Zustand.
Kurzum, selbst dieses einfache Beispiel kann rasch so komplex werden, dass eine modellierte Darstellung, zum Beispiel als Markov Decision Process, schlicht unmöglich wird. Dafür gibt es dann modellfreie Algorithmen, die kein exaktes Modell des Systems benötigen. Hier existieren gradientenfreie und gradientenbasierte Verfahren. Bei den gradientenfreien Verfahren wird zwischen einem Off Policy Verfahren, dem Q-Learning, und On-Policy Verfahren, dem SARSA Algorithmus, unterschieden. Gradientenbasierte Verfahren basieren auf dem Gradientenverfahren, bei der die Parameter $\theta$ der Policy nach der in der obigen Abbildung gezeigten Gleichung iterativ berechnet werden:
$\theta^{k+1} = \theta^k + \alpha \nabla_{\theta} V|_{\theta = \theta^k}$
Die Algorithmen bzw. Methoden, die unter diesen Punkt fallen, werden unter dem Begriff Policy Gradient Optimization zusammengefasst.
Deep Reinforcement Learning Algorithmen
Als wäre das alles noch nicht genug, wurde durch die rasche Ausbreitung und Weiterentwicklung von neuronalen Netzen ein ganz neuer Zweig an Algorithmen, den Deep Reinforcement Learning Algorithmen, entdeckt. Alle die in der obigen Abbildung im orangen Kasten gezeigten Algorithmen fallen unter die jeweilige Kategorie, neben der sie stehen, beinhalten aber zusätzlich auch Teile des Deep Learnings. DQN steht dabei für Deep Q Learning und DPN für Deep Policy Network. Wie ihr sehen könnt, ist die Anzahl an Reinforcement Learning Algorithmen und der damit verbundenen Möglichkeiten genauso groß wie beim Supervised und Unsupervised Learning.
Zusammenfassung Reinforcement Learning
In diesem Artikel habe ich einmal dargelegt, wie ein Agent in einer abgegrenzten Umgebung durch die Vergebung von Rewards eine Policy erlernen kann, um eine fest definierte Aufgabe zu erfüllen. Ich habe dies beispielhaft an einem Beispiel mit einem Saugroboter gezeigt. Das Reinforcement Learning findet in vielen Bereichen Anwendung, z. B. in der Robotik, beim Erlernen von Spielen und beim autonomen Fahren. Zu den beliebten Algorithmen des Reinforcement Learning gehören Q-Learning, SARSA und Policy-Gradient-Methoden. Jüngste Fortschritte beim Deep Learning haben zur Entwicklung von Deep Reinforcement Learning Algorithmen geführt, die neuronale Netze zur näherungsweisen Berechnung von Q-Werten oder der Policy-Funktion verwenden.
Weitere Informationen
In meinen Videos auf YouTube stelle ich dieses und weitere Machine Learning Themen noch einmal detaillierter vor. Bei Fragen oder Anmerkungen schreibt mir gerne einen Kommentar :).