Von Markov-Entscheidungsprozessen zu Bandits: Ein tiefer Einblick in Schlüsselkonzepte des Reinforcement Learning
Reinforcement Learning ist die dritte Kategorie des Machine Learnings, welche darauf abzielt, dass ein Agent selbstständig eine Strategie erlernt. Mittels dieser entscheidet er, in welcher Situation welche Aktion ausgeführt wird, um die Belohnungsfunktion zu maximieren. Wenn dir das grundlegende Prinzip von Reinforcement Learning noch nicht bekannt ist, klicke hier, um zu dem übergeordneten Beitrag zu kommen. Der Oberbegriff Reinforcement Learning wird in Modelle des Markov Decision Prozess (MDP) und in Bandits unterteilt, welche in der folgenden Grafik dargestellt sind:
Markov Decision Process
Auf der ersten Ebene wird Reinforcement Learning (RL) in Markov Decision Process (MDP) und Bandits untergliedert. Der grundlegende Unterschied zwischen diesen Kategorien ist, dass Zustandsübergänge bei MDP von der getroffenen Entscheidung abhängig sind, wohingegen Bandits nur das Feedback der Aktion berücksichtigen. Letztere beachten dabei also nicht den Zustand der Umwelt. Daher können bei MDP-Modellen die durch den Agenten durchgeführten Aktionen die Umwelt für zukünftige Aktionen beeinflussen. Die Algorithmen der MDP-Kategorie lassen sich wiederum in Model-Based und Model-Free einteilen.
Model-Based
Bei den Model-Based Algorithmen wird ein (bekanntes oder erlerntes) vorhersagendes Modell verwendet, um herauszufinden was passiert, wenn eine bestimmte Aktion ausgeführt wird. Der Agent lernt somit die beste Strategie indirekt, indem zunächst ein Modell der Umwelt erstellt wird. Dies kann durch Interaktion mit der Umwelt und Beobachtung des dadurch entstehenden Outcomes geschehen. Anschließend wird der Agent mit dem Modell interagieren, um Simulationsdaten zu generieren. Wenn das Modell genau genug ist, kann eine gute Policy, erlernt werden. Die Algorithmen, die in dieser Subkategorie verwendet werden, werden wiederum in Given the Model und Learn the Model unterschieden. Im Folgenden werden wir für Given the Model den Monte Carlo Tree Search und für Learn the Model I2A vorstellen.
Monte Carlo Tree Search (MCTS)
Beim MCTS werden nach einem Spielzug alle möglichen Züge gesucht und daraus der beste ausgewählt. Dieser wird nach dem Zug ausgeführt, damit eine Reaktion des Agenten für diesen Zustand gefunden wird. Dies wird so lange wiederholt, bis die gewünschte Lösung erreicht und die Policy des Spiels gefunden wurde. Allgemein wird der Prozess der MCTS-Methode in vier Schritte zerlegt, die in der nachfolgenden Grafik zu erkennen sind:
Selektion
Ausgehend vom Wurzelknoten durchläuft der Algorithmus den gesamten Baum und versucht den Weg mit der höchsten Gewinnwahrscheinlichkeit zu finden. Beim Durchlaufen des Baumes wird eine bestimmte Policy verwendet, welche ausgehend von einem bestimmten State entscheidet, welche Aktion als nächstes ausgespielt wird.
Expansion
Nachdem der richtige unterste Knoten gefunden wurde, wird dieser erweitert. Dafür werden mehrere Knoten angehängt, welche die nächsten Spielzüge repräsentieren.
Simulation
Durchführung einer Simulation ab dem neu hinzugefügten Knoten, indem das Spiel ab diesem erneut gespielt wird. Jedem angehängten Knoten wird ein Reward zugewiesen, der den Erfolg dieses Knotens widerspiegelt.
Rückverfolgung
Ausgehend von dem neuen untersten Knoten wird zurück zum Wurzelknoten gegangen, um den übergeordneten Knoten zu updaten. Die so erzeugten neuen Scores der Knoten verändern schließlich den State des Baums und können weitere Selektionsprozesse beeinflussen.
1. Anwendung: Spiele
Ursprünglich wurde MCTS entwickelt, um in Schach und anderen Brettspielen Anwendung zu finden. Besonders in Spielprogrammen wie Alphago konnten sehr gute Leistungen erzielt werden.
2. Anwendung: Security Games
Die Anwendung von MCTS hat sich in den letzten Jahren auch beispielsweise auf die optimale Patroullienroute von Polizeikräften oder Sicherheitspersonal ausgeweitet. So soll die optimale Route zur Erfassung von Kriminellen gefunden werden können.
Imagination-Augmented Agents (I2A)
Diese Methode beinhaltet sowohl Model-Free als auch Model-Based Aspekte, weshalb die Zuordnung in eine der beiden Kategorien hier nicht genau möglich ist. Der Nachteil der Model-Free Algorithmen ist allgemein, dass der Agent nur reaktiv handelt. Mittels der Imagination wird nun versucht dem Agenten das Planen zu ermöglichen, wodurch die Vorteile von Model-Free mit denen von Model-Based kombiniert werden.
Model Free: Dieser Weg ist ähnlich zu anderen RL Algorithmen, wobei ausgehend vom aktuellen State Merkmale aus der Datenbasis extrahiert werden.
Model Based: Abhängig von dem State und der Action kann hier der nächste State und der Reward simuliert werden. Dieser Vorgang wird wiederholt, wodurch Trajektorien entstehen. Diese beinhalten eine Vielzahl von Informationen, aus denen anschließend mithilfe der Rollout Encoder nur die relevanten Informationen extrahiert werden.
Policy Module: Hier werden die Informationen des Model-Free and Model-Based Weges zusammengefasst und die Policy sowie der geschätzte Wert werden ausgegeben.
Model Free
Im Gegensatz zu modelbasierten Algorithmen existieren auch modellfreie Algorithmen, die für ihren Lernprozess kein Modell der Umwelt benötigen. Hierbei wird die Policy direkt durch die Interaktion mit der Umwelt erlernt. Dies hat den Vorteil, dass die modellfreien Methoden in unterschiedlichen Umgebungen eingesetzt werden und auch auf neue States besser reagieren können. Innerhalb der Kategorie der modellfreien Methoden, können wir die einzelnen Algorithmen in Policy-based und Value-based unterteilen. Bei ersterem wird eine Repräsentation der Policy erstellt, welche dem Agenten direkt sagt, welche Aktion abhängig des States durchgeführt wird. Im Gegensatz dazu wird bei den Value-based Algorithmen nicht direkt die Policy erlernt, sondern eine Wertfunktion geschätzt. Diese gibt an, wie gut ein bestimmter Zustand ist. Im Folgenden werden wir für die Value-based Methoden das Q-Learning & Deep Q-Learning und für Policy-based die Actor Critic Methode betrachten.
Q-Learning
Bei dieser Methode werden anstelle des Erlernens einer Policy die Q-Werte verwendet, welche den erwarteten zukünftigen Wert beinhalten. Die Q-Werte werden in der Q-Tabelle gespeichert. Diese Tabelle beinhaltet somit für jedes State-Action-Paar einen Q-Wert, wodurch für jeden State die beste Action gefunden werden kann. Um den Q-Wert zu bestimmen, wird zumeist die Bellman’s Formel verwendet, wodurch der erwartete Reward einer Action in einem spezifischen State berechnet wird.
Das grundlegende Prinzip von Q-Learning wird im Folgenden anhand eines kleinen Beispiels veranschaulicht. Dabei versucht eine Katze ausgehend von dem Startfeld (1,1) an die Maus auf dem Zielfeld (3,3) zu kommen. Die Katze darf dabei nicht dem Hund begegnen. Für die Punktevergabe gelten folgende Regeln:
- Katze betritt ein leeres Feld: -1, weil die Katze den kürzesten Weg finden soll.
- Katze trifft auf Hund: -10 und das Spiel endet
- Katze trifft auf Maus: +10 und das Spiel ist gewonnen
1. Schritt
Die Katze befindet sich am Startfeld und kann nach rechts oder unten gehen. Wenn sie nach unten geht, trifft sie auf den Hund und das Spiel endet.
2. Schritt
Die Katze hat sich dafür entschieden nach rechts zu gehen. Nun kann sie nach links, rechts und unten gehen.
3. Schritt
Die Katze ist jetzt auf dem Feld (2,2) und hat die Möglichkeit in alle vier Richtungen zu gehen, wobei sie bei dem Schritt nach links wieder dem Hund begegnen würde.
4. Schritt
Die Katze befindet sich auf dem Feld (3,2) und kann mit einem Schritt nach rechts die Maus erreichen und das Spiel gewinnen.
Deep Q-Learning
Das Problem mit dem vorherigen Q-Learning ist, dass die Q-Werte in der Q-Tabelle oftmals für bestimmte Aktionen überschätzt werden für bestimmte Aktionen. Dadurch kann es passieren, dass nicht die optimale Aktion für einen spezifischen State ausgewählt wird. Auch gerät die Q-Tabelle bei komplexeren Problemen mit mehreren Phasen an ihre Grenzen, weshalb ein Wechsel zu der Q-Funktion sinnvoll ist. Dabei wird das Q-Learning mit einem neuronalen Netz kombiniert, welche den optimalen Q-Wert berechnet. Der Unterschied zwischen diesen beiden Methoden ist in der nachfolgenden Grafik dargestellt.
Das DQN findet in der Praxis einige Anwendungsfälle, von denen wir im Folgenden ein Empfehlungssystem und ein Portfoliomanagementsystem für Kryptowährungen beispielhaft betrachten:
Empfehlungssystem: DQN kann genutzt werden, um personalisierte Empfehlungen auf Basis gesammelter Kundeninformationen, wie demographischen Informationen oder historischen Verhalten, zu ermitteln. Dies kann z.B. beim E-Commerce oder Streaming-Diensten wie Netflix angewendet werden.
Portfoliomanagement: Das DQN kann eingesetzt werden, um finanzielle Mittel in Kryptowährungen zu investieren und die Geldsummen in den verschiedenen Währungen dynamisch zu verteilen. Dabei ist es das Ziel, die Gesamtrendite zu maximieren, während das Risiko minimiert wird. Auch kann DQN für den Hochfrequenzhandel verwendet werden, bei dem das Modell sehr schnell Entscheidungen treffen muss, um auch von kleinen Preisschwankungen zu profitieren.
Actor Critic
Diese RL Methode gehört zu den Policy-based Modellen und setzt sich aus folgenden zwei Komponenten zusammen:
- Actor (Schauspieler): Dieser stellt den Agenten dar und entscheidet, welche Action innerhalb einer bestimmten Umgebung ausgeführt werden soll. Diese Entscheidung wird basierend auf der Policy getroffen und es wird angestrebt, die zukünftige Belohnung zu maximieren.
- Critic (Kritiker): Dieser bewertet die von dem Actor ausgewählten Actions hinsichtlich der übergeordneten Ziele. Diese kontinuierliche Rückkopplung ermöglicht dem Actor eine Verbesserung seiner Actions.
Das grundlegende Prinzip der Actor Critic Methode ist in der vorherigen Grafik dargestellt. Dabei ist zu erkennen, wie der Agent, bestehend aus Actor und Critic mit der Umwelt interagiert. Dabei erhält der Kritiker die vom Schauspieler durchgeführte Action sowie den daraus resultierenden Reward. Auf Basis dieser Informationen kann der Kritiker dem Schauspieler einen Wert zurückgeben, welcher aussagt, wie gut die von ihm durchgeführte Action war.
Bandits
Bandits sind ein mathematisches Modell, das in Situationen angewendet wird, in denen ein Entscheidungsträger vor einer Anzahl von Optionen steht. Jede dieser Optionen hat eine unterschiedliche, jedoch unbekannte Belohnung oder einen unbekannten Gewinn. Diese Optionen werden als “Banditen” bezeichnet. Das Ziel besteht darin die beste Strategie zu entwickeln, um die höchstmögliche Gesamtbelohnung zu erzielen, indem man die richtigen Banditen auswählt.
Zur Veranschaulichung kann man sich ein Kasino in Las Vegas mit einarmigen Banditen vorstellen. Jeder dieser Maschinen weist eine unterschiedliche Gewinnwahrscheinlichkeit auf, wobei es das Ziel eines jeden Spielers ist, möglichst viel zu gewinnen. Das Problem besteht darin, die optimale Balance zwischen Exploration und Exploitation zu finden, also neue Maschinen auszuprobieren
Unterschied zu MDP-Modellen
Wie wir zuvor gesehen haben, hat der Agent bei den MDP Modellen ein vollständiges Wissen über die Umgebung und ihre Übergangswahrscheinlichkeiten. Im Gegensatz dazu arbeiten Bandits mit unvollständigen Informationen der Umgebung. Der Agent muss in jedem Zeitschritt eine Entscheidung treffen, ohne zu wissen, wie sich diese auf zukünftige Entscheidungen auswirkt. MDP-Modelle sind in der Lage, optimale Strategien für Probleme mit vollständigen Informationen zu finden. Stattdessen sind Bandits speziell für Situationen mit unsicheren Belohnungen und begrenztem Wissen entwickelt worden.
Multi-Armed Bandits (MAB)
Multi-Armed Bandits (MAB) sind eine der grundlegenden und wohl auch die bekannteste Form von Bandits. Hier steht der der Agent vor einer Gruppe von Banditen und kann in jedem Zeitschritt einen Banditen auswählen, um eine Belohnung zu erhalten. Das Ziel besteht darin, im Laufe der Zeit die optimale Strategie zu finden, um die höchstmögliche Gesamtbelohnung zu erzielen.
Contextual Multi-Armed Bandits (CMAB)
Contextual Multi-Armed Bandits (CMAB) erweitern das MAB-Modell, indem sie den Banditen Kontextinformationen hinzufügen. Das bedeutet, dass jeder Bandit eine Beschreibung oder Merkmale der aktuellen Situation oder des Kontexts erhält. Der Agent muss nun nicht nur den besten Banditen auswählen, sondern auch berücksichtigen, wie der Kontext die Belohnungen beeinflusst. Dieses Modell findet viele reale Anwendungen, z.B. in personalisierten Empfehlungssystemen und Online-Werbungen, in denen Benutzerprofile und Kontextinformationen eine wichtige Rolle spielen.
Zusammenfassung
In diesem Blogbeitrag haben wir uns intensiv mit dem Thema Reinforcement Learning auseinandergesetzt. Diese stellt eine Kategorie des Machine Learnings dar, bei der ein Agent eigenständig Strategien erlernt, um Belohnungen zu maximieren. Wir haben verschiedene Aspekte des Reinforcement Learning behandelt, darunter Markov Decision Processes (MDP) und Bandits.
Im Rahmen der MDP haben wir Model-Based und Model-Free Algorithmen betrachtet. Dabei haben wir den Monte Carlo Tree Search (MCTS) als Beispiel für Model-Based und das Imagination-Augmented Agents (I2A) als hybride Methode vorgestellt.
Im Bereich der Model-Free-Algorithmen haben wir Q-Learning und Deep Q-Learning näher erläutert und deren Anwendungen in Portfoliomanagement und Empfehlungssystemen diskutiert.
Schließlich haben wir die Actor-Critic-Methode vorgestellt, eine Policy-basierte Methode, bei der ein Agent (Actor) Entscheidungen trifft und von einem Kritiker (Critic) bewertet wird.
Wir sind dann zu dem Thema Bandits übergegangen, einem mathematischen Modell, das in Situationen mit unsicheren Belohnungen und begrenztem Wissen angewendet wird. Wir haben den Unterschied zu MDP-Modellen erklärt und Multi-Armed Bandits (MAB) sowie Contextual Multi-Armed Bandits (CMAB) eingeführt. Abschließend haben wir einige reale Anwendungsgebiete für MAB und CMAB beleuchtet.
Insgesamt haben wir einen breiten Einblick in die Welt des Reinforcement Learnings und der Bandits gewonnen und gesehen, wie diese Modelle in verschiedenen realen Anwendungen eingesetzt werden können.
DE 
EN