EITC/AI/ARL Advanced Reinforced Learning

Das Reinforcement-Lernen unterscheidet sich vom überwachten Lernen darin, dass keine gekennzeichneten Eingabe/Ausgabe-Paare präsentiert werden müssen und keine suboptimalen Aktionen explizit korrigiert werden müssen. Stattdessen liegt der Schwerpunkt auf der Suche nach einem Gleichgewicht zwischen Exploration (Neuland) und Ausbeutung (nach aktuellem Kenntnisstand).

Die Umgebung wird typischerweise in Form eines Markov-Entscheidungsprozesses (MDP) angegeben, da viele Verstärkungslernalgorithmen für diesen Kontext dynamische Programmiertechniken verwenden. Der Hauptunterschied zwischen den klassischen dynamischen Programmiermethoden und den Verstärkungslernalgorithmen besteht darin, dass letztere keine Kenntnis eines genauen mathematischen Modells des MDP voraussetzen und auf große MDPs abzielen, bei denen genaue Methoden nicht mehr durchführbar sind.

Aufgrund seiner Allgemeinheit wird das verstärkte Lernen in vielen Disziplinen untersucht, wie z. B. Spieltheorie, Steuerungstheorie, Operationsforschung, Informationstheorie, simulationsbasierte Optimierung, Multiagentensysteme, Schwarmintelligenz und Statistik. In der Literatur zu Operations Research und Control wird das verstärkte Lernen als ungefähre dynamische Programmierung oder neurodynamische Programmierung bezeichnet. Die Probleme, die für das verstärkte Lernen von Interesse sind, wurden auch in der Theorie der optimalen Steuerung untersucht, die sich hauptsächlich mit der Existenz und Charakterisierung optimaler Lösungen und Algorithmen für ihre genaue Berechnung befasst, und weniger mit dem Lernen oder der Annäherung, insbesondere in Abwesenheit von ein mathematisches Modell der Umwelt. In der Wirtschafts- und Spieltheorie kann das verstärkte Lernen verwendet werden, um zu erklären, wie unter begrenzter Rationalität ein Gleichgewicht entstehen kann.

Die grundlegende Verstärkung wird als Markov-Entscheidungsprozess (MDP) modelliert. In der Mathematik ist ein Markov-Entscheidungsprozess (MDP) ein zeitdiskreter stochastischer Steuerungsprozess. Es bietet einen mathematischen Rahmen für die Modellierung der Entscheidungsfindung in Situationen, in denen die Ergebnisse teilweise zufällig sind und teilweise von einem Entscheidungsträger kontrolliert werden. MDPs sind nützlich, um Optimierungsprobleme zu untersuchen, die durch dynamische Programmierung gelöst werden. MDPs waren mindestens bereits in den 1950er Jahren bekannt. Ein Kern der Forschung zu Markov-Entscheidungsprozessen ergab sich aus Ronald Howards 1960er Buch Dynamic Programming and Markov Processes. Sie werden in vielen Disziplinen eingesetzt, darunter Robotik, automatische Steuerung, Wirtschaftlichkeit und Fertigung. Der Name MDPs stammt vom russischen Mathematiker Andrey Markov, da sie eine Erweiterung der Markov-Ketten sind.

Zu jedem Zeitschritt befindet sich der Prozess in einem Zustand S, und der Entscheidungsträger kann eine beliebige Aktion a auswählen, die in Zustand S verfügbar ist. Der Prozess reagiert beim nächsten Zeitschritt, indem er zufällig in einen neuen Zustand S 'übergeht und die gibt Entscheider eine entsprechende Belohnung Ra (S, S ').

Die Wahrscheinlichkeit, dass der Prozess in seinen neuen Zustand S 'übergeht, wird durch die gewählte Aktion a beeinflusst. Insbesondere ist es durch die Zustandsübergangsfunktion Pa (S, S ') gegeben. Somit hängt der nächste Zustand S 'vom aktuellen Zustand S und der Aktion des Entscheidungsträgers a ab. Bei gegebenem S und a ist es jedoch bedingt unabhängig von allen vorherigen Zuständen und Handlungen. Mit anderen Worten, die Zustandsübergänge eines MDP erfüllen die Markov-Eigenschaft.

Markov-Entscheidungsprozesse sind eine Erweiterung der Markov-Ketten. Der Unterschied besteht in der Hinzufügung von Aktionen (Auswahlmöglichkeiten) und Belohnungen (Motivation). Wenn umgekehrt für jeden Zustand nur eine Aktion vorhanden ist (z. B. „Warten“) und alle Belohnungen gleich sind (z. B. „Null“), wird ein Markov-Entscheidungsprozess auf eine Markov-Kette reduziert.

Ein Verstärkungslernmittel interagiert in diskreten Zeitschritten mit seiner Umgebung. Zu jedem Zeitpunkt t erhält der Agent den aktuellen Zustand S (t) und die Belohnung r (t). Anschließend wählt es aus den verfügbaren Aktionen eine Aktion a (t) aus, die anschließend an die Umgebung gesendet wird. Die Umgebung bewegt sich in einen neuen Zustand S (t + 1) und die mit dem Übergang verbundene Belohnung r (t + 1) wird bestimmt. Das Ziel eines Verstärkungslernagenten ist es, eine Richtlinie zu lernen, die die erwartete kumulative Belohnung maximiert.

Bei der Formulierung des Problems als MDP wird davon ausgegangen, dass der Agent den aktuellen Umgebungszustand direkt beobachtet. In diesem Fall soll das Problem vollständig beobachtbar sein. Wenn der Agent nur Zugriff auf eine Teilmenge von Zuständen hat oder wenn die beobachteten Zustände durch Rauschen verfälscht sind, wird der Agent als teilweise beobachtbar bezeichnet, und formal muss das Problem als teilweise beobachtbarer Markov-Entscheidungsprozess formuliert werden. In beiden Fällen kann der dem Agenten zur Verfügung stehende Aktionssatz eingeschränkt werden. Beispielsweise könnte der Status eines Kontostands auf positiv beschränkt werden. Wenn der aktuelle Wert des Zustands 3 ist und der Zustandsübergang versucht, den Wert um 4 zu verringern, ist der Übergang nicht zulässig.

Wenn die Leistung des Agenten mit der eines Agenten verglichen wird, der optimal handelt, führt der Leistungsunterschied zu dem Gedanken des Bedauerns. Um nahezu optimal zu handeln, muss der Agent über die langfristigen Konsequenzen seiner Handlungen nachdenken (dh das zukünftige Einkommen maximieren), obwohl die damit verbundene unmittelbare Belohnung negativ sein kann.

Daher ist das verstärkte Lernen besonders gut für Probleme geeignet, die einen langfristigen oder einen kurzfristigen Kompromiss zwischen Belohnungen beinhalten. Es wurde erfolgreich auf verschiedene Probleme angewendet, einschließlich Robotersteuerung, Aufzugsplanung, Telekommunikation, Backgammon, Kontrolleure und Go (AlphaGo).

Zwei Elemente machen das Lernen zur Verstärkung leistungsfähig: die Verwendung von Stichproben zur Optimierung der Leistung und die Verwendung der Funktionsnäherung zur Bewältigung großer Umgebungen. Dank dieser beiden Schlüsselkomponenten kann das verstärkte Lernen in großen Umgebungen in den folgenden Situationen eingesetzt werden:

• Ein Modell der Umgebung ist bekannt, eine analytische Lösung ist jedoch nicht verfügbar.
• Es wird nur ein Simulationsmodell der Umgebung angegeben (Gegenstand der simulationsbasierten Optimierung).
• Die einzige Möglichkeit, Informationen über die Umgebung zu sammeln, besteht darin, mit ihr zu interagieren.

Die ersten beiden dieser Probleme könnten als Planungsprobleme angesehen werden (da irgendeine Form von Modell verfügbar ist), während das letzte als echtes Lernproblem angesehen werden könnte. Durch das verstärkte Lernen werden jedoch beide Planungsprobleme in Probleme des maschinellen Lernens umgewandelt.

Der Kompromiss zwischen Exploration und Exploitation wurde am gründlichsten anhand des Problems der mehrarmigen Banditen und für MDPs im endlichen Staatsraum in Burnetas und Katehakis (1997) untersucht.

Verstärkungslernen erfordert clevere Erkundungsmechanismen. Die zufällige Auswahl von Aktionen ohne Bezugnahme auf eine geschätzte Wahrscheinlichkeitsverteilung zeigt eine schlechte Leistung. Der Fall von (kleinen) endlichen Markov-Entscheidungsprozessen ist relativ gut verstanden. Aufgrund des Fehlens von Algorithmen, die sich gut mit der Anzahl der Zustände skalieren lassen (oder auf Probleme mit unendlichen Zustandsräumen skalieren lassen), sind einfache Erkundungsmethoden am praktischsten.

Selbst wenn das Thema Exploration nicht berücksichtigt wird und selbst wenn der Staat beobachtbar war, bleibt das Problem, die Erfahrungen der Vergangenheit zu nutzen, um herauszufinden, welche Maßnahmen zu höheren kumulativen Belohnungen führen.