Bestärkendes Lernen

Reihe von Methoden des maschinellen Lernens, bei denen ein Agent selbständig eine Strategie erlernt, um erhaltene Belohnungen zu maximieren
(Weitergeleitet von Reinforcement Learning)

Bestärkendes Lernen oder verstärkendes Lernen (englisch reinforcement learning, RL) steht für eine Reihe von Methoden des maschinellen Lernens, bei denen ein Software-Agent selbständig eine Strategie (englisch policy) erlernt, um erhaltene Belohnungen zu maximieren. Dabei wird dem Agenten nicht vorgezeigt, welche Aktion in welcher Situation die beste ist, sondern er erhält durch die Interaktion mit seiner Umwelt zu bestimmten Zeitpunkten eine Belohnung, die auch negativ sein kann.

Der Begriff ist der Psychologie entlehnt und wurde bereits seit den Anfängen der Kybernetik verwendet. So benutzte schon Marvin Minsky den Begriff in seiner Dissertation von 1954.[1] Die Modelle des bestärkenden Lernens versuchen, das Lernverhalten in der Natur nachzubilden.

Es besteht eine besonders enge Beziehung des bestärkenden Lernens zur dynamischen Programmierung und optimalen Steuerung. In Letzteren ist, anders als bei Ersterem, a priori ein Umgebungsmodell gegeben, das die Interaktion mit der Umwelt überflüssig macht.[2]

Ein Spezialfall ist die Verwendung eines Bewertungsmodells, welches durch menschliche Interaktion mit überwachtem Lernen vorprogrammiert wird und die Interaktion mit der Umwelt ergänzt. In diesem Fall erfolgt bestärkendes Lernen durch menschlich beeinflusste Rückkopplung (englisch reinforcement learning through human feedback, (RLHF)).[3]

Die mathematischen Grundlagen des bestärkenden Lernens bilden die folgenden fünf Begriffe: Der Agent (englisch agent), die Umwelt (englisch environment), die Zustände (englisch states), die Aktionen (englisch actions) und die Belohnungen (englisch rewards). Die Methoden des bestärkenden Lernens betrachten die Interaktion des lernenden Agenten mit seiner Umwelt. Die Umwelt ist dabei als Markow-Entscheidungsproblem (englisch markov decision process, MDP)   formuliert. Die Umwelt besteht aus einer Menge von Zuständen   und einer Menge von Aktionen  , sowie einer Dynamik   und einer Startverteilung  . Die Interaktion des Agenten mit der Umwelt findet zu diskreten Zeitpunkten   statt. Zu jedem Zeitpunkt befindet sich der Agent in einem Zustand, wählt eine Aktion aus und erhält dafür eine reellwertige Belohnung. Da diese nicht vorhersehbar sind, fasst man sie als Zufallsvariablen   und   in   und   auf. Zum Zeitpunkt   befindet sich der Agent in Zustand   und wählt eine Aktion   gemäß einer Policy   aus. Eine Policy   ist eine Kollektion von Wahrscheinlichkeitsmaßen   auf  .   gibt dabei die Präferenz des Agenten an, zum Zeitpunkt   die Aktion   zu wählen, wenn er sich in Zustand   befindet. In Zufallsvariablen gesprochen bedeutet dies  . Anschließend gibt die Umwelt eine Belohnung   und einen Folgezustand   gemäß einer Dynamik   aus. Die Dynamik   ist eine Kollektion von (Übergangs-)Wahrscheinlichkeitsverteilungen   auf  . Es gilt demnach  . Der Zustand, in dem sich der Agent zum Zeitpunkt   befindet, ist durch die Startverteilung   festgelegt:  .

Total Discounted Reward Kriterium

Bearbeiten

Ziel des Agenten ist es, den zukünftig zu erwarteten Gewinn (englisch total discounted reward)

  mit  

zu maximieren. Der Gewinn entspricht der Gesamtbelohnung als diskontierte Summe aller folgenden Belohnungen. Dabei gewichtet der Diskontierungsfaktor   zukünftige Belohnungen. Bei episodischen Problemen ( ), d. h. die Umwelt geht nach einer endlichen Anzahl von Schritten in einen Endzustand über (wie z. B. eine Schachpartie), eignet sich der Diskontierungsfaktor  . In diesem Fall wird jede Belohnung   gleich gewertet. Bei kontinuierlichen Problemen ( ) muss ein   gewählt werden, um Konvergenz der unendlichen Reihe   zu gewährleisten. Für   zählt nur die aktuelle Belohnung  , alle zukünftigen Belohnungen werden ignoriert. Geht   gegen 1, wird der Agent weitsichtiger.

Da der Agent nur Einfluss auf die Policys  , nicht aber auf die Dynamik   der Umwelt hat, ist das Ziel des Agenten, eine Policy   zu finden, die den zu erwartenden Gewinn maximiert.[1]

Lernverfahren

Bearbeiten

Zum Erlernen der Strategie des Agenten gibt es verschiedene Algorithmen. Sie lassen sich grob einteilen in modellbasiert und modellfrei. Die am häufigsten genutzten modellfreien Ansätze sind wertbasiert oder strategiebasiert. Die Mischform wird meist als Actor-Critic bezeichnet.[4]

Modellfrei

Bearbeiten

Wertbasiert

Bearbeiten

Bekannte Beispiele sind Monte-Carlo-Methoden und Temporal Difference Learning. Bei diesen handelt es sich um Algorithmen, bei denen der Agent eine Nutzenfunktion besitzt, welche einen bestimmten Zustand oder eine bestimmte Aktion in einem Zustand bewertet.

Bei kleinen Zustands- oder Aktionsräumen kann dies eine Tabelle sein, deren Felder anhand der erhaltenen Belohnung aktualisiert werden. Bei großen Zustandsräumen muss die Funktion jedoch approximiert werden. Dazu eignet sich beispielsweise die Fourierreihe oder auch ein Neuronales Netz.

Soll mehr als ein Agent lernen, kann selbst bei kooperativen Agenten, außer in trivialen Fällen, die Konvergenz der Lernvorgänge (bislang) nicht mehr garantiert werden. Trotzdem kann unter Zuhilfenahme von Heuristiken oft ein in der Praxis nützliches Verhalten gelernt werden, da der worst case selten auftritt.[5]

Strategiebasiert

Bearbeiten

Strategiebasierte Methoden versuchen, die zu erwartende kumulative Belohnung direkt durch Parametrisierung der Strategie zu maximieren. Meistens erfolgt diese Maximierung durch stochastisch gradientbasierte Optimierung (englisch policy gradient). Prominente Vertreter dieser Klasse sind REINFORCE, Trust Region Policy Optimization (TRPO) und Proximal Policy Optimization (PPO).

Beispiel REINFORCE
Bearbeiten

Der einfach herzuleitende Algorithmus REINFORCE[6] schätzt den Gradienten des zu erwartenden Gewinns

 , um damit seine Parameter über empirisch gewinnbare Spielabläufe zu aktualisieren. Hierbei muss die Strategie   nach   differenzierbar sein und   stellt einen Spielablauf dar, der aus der Wahrscheinlichkeitsverteilung   entnommen wird. Diese setzt sich einerseits aus der Strategie  , als auch der möglicherweise nicht-deterministischen Umgebung   (auf die der Agent keinen Einfluss hat), zusammen:

 ,

wobei   eine Verteilung über den Startzustand darstellt. Über die Definition der Erwartungswerts kann nun REINFORCE wie folgt hergeleitet werden:

 : 

wobei für die erste Gleichung die Leibnizregel verwendet wurde und für die dritte Gleichung die Regel

 ,

wobei der natürliche Logarithmus gemeint ist. Als letzten Schritt erkennen wir, dass

 .

Nun kann man einen erwartungstreuen Schätzer   des Gradienten des zu erwartenden Gewinns erhalten, indem man erst einen Spielablauf   mit dem Agenten generiert und einsetzt:

 .

Der Parameterupdate mit Lernrate   erfolgt dann wie folgt:

 .

Modellbasiert

Bearbeiten

Modellbasierte Verfahren konstruieren ein prädiktives Modell ihrer Umwelt. Dies bedeutet, dass der Agent Vorhersagen für Anfragen der Art „Was wird passieren, wenn ich eine bestimmte Aktion ausführe?“ generieren kann.[7] Das Modell stellt somit einen (gelernten oder bekannten) reversiblen Zugang zur Umgebungsdynamik dar, da der Agent eine Vorhersage zu jedem beliebigen Zustands-Aktions-Paar ermitteln kann und nicht an die durch den Spielablauf vorgegebene Ordnung gebunden ist. Anders als in modellfreien Ansätzen ermöglicht das Modell explizites Planen.[8] Dies wird in Algorithmen wie z. B. MuZero von Deepmind genutzt, um ein präzise Vorausberechnung zu ermöglichen, die in einigen Spielen wie Schach oder Go von besonderer Relevanz ist.[9] Eine andere Klasse von Methoden, welche auf dem Dyna-Algorithmus[10] basiert, kombiniert den modellbasierten mit dem modellfreien Ansatz, indem sie das gelernte Modell nutzt, um künstliche (halluzinierte) Daten zu generieren. Diese werden dann wiederum zum Lernen einer Strategie und/oder Wertfunktion eingesetzt.[11]

Forschende erhoffen sich, dass modellbasierte RL-Methoden künftig noch mehr zum Verständnis realer Kausalitäten medizinischer, sozial- und wirtschaftswissenschaftlicher Wissenschaftszweige oder Politikgestaltung beitragen können (causal machine learning), deren Themenfelder bisher über wenige inhaltliche und personelle Überschneidungen verfügen.[12]

Literatur

Bearbeiten
  • Richard Sutton, Andrew Barto: Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
  • Dimitri P. Bertsekas, John Tsitsiklis: Neuro-Dynamic Programming. Athena Scientific, Cambridge, MA, 1996.
  • Csaba Szepesvári, Algorithms for Reinforcement Learning, Morgan and Claypool, 2010 (ualberta.ca PDF).
  • Marc Patrick Deisenroth, Gerhard Neumann, Jan Peters: A Survey on Policy Search for Robotics. Foundations and Trends in Robotics, 21, S. 388–403, 2013 (ausy.tu-darmstadt.de PDF).
  • Jens Kober, Drew Bagnell, Jan Peters: Reinforcement Learning in Robotics: A Survey. International Journal of Robotics Research, 32, 11, S. 1238–1274, 2013 (ausy.tu-darmstadt.de PDF).
  • Uwe Lorenz: Reinforcement Learning: Aktuelle Ansätze verstehen – mit Beispielen in Java und Greenfoot. (aktual. 2. Auflage) Springer Vieweg, 2024, ISBN 978-3-662-68311-8
  • Warren B. Powell: Approximate Dynamic Programming. John Wiley and Sons, 2011.
  • Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz. Pearson Studium, August 2004, ISBN 3-8273-7089-2 (deutsche Übersetzung der 2. Auflage) Kapitel 21.
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b Richard Sutton: Reinforcement Learning FAQ. 2. April 2004, archiviert vom Original (nicht mehr online verfügbar) am 28. August 2016; abgerufen am 21. April 2016 (englisch).
  2. Yi Ma und Shankar Sastry: Reinforcement Learning & Optimal Control Overview. (PDF) University of California, Berkeley, 17. Februar 2021, abgerufen am 18. April 2022 (englisch).
  3. Illustrating Reinforcement Learning from Human Feedback (RLHF). huggingface.co, 9. Dezember 2022. Abgerufen am 8. August 2023 (englisch)
  4. Sergey Levine: Actor-Critic Algorithms. (PDF) In: Actor-Critic Algorithms. UC Berkley, abgerufen am 27. Dezember 2021 (englisch).
  5. J. F. Knabe: Kooperatives Reinforcement Lernen in Multiagentensystemen. B. Sc. Thesis, Universität Osnabrück, 2005 (panmental.de PDF)
  6. Ronald J. Williams: Simple statistical gradient-following algorithms for connectionist reinforcement learning. In: Machine Learning. Band 8, Nr. 3, 1. Mai 1992, ISSN 1573-0565, S. 229–256, doi:10.1007/BF00992696.
  7. Daniel Seita: Model-Based Reinforcement Learning:Theory and Practice. Abgerufen am 18. April 2022.
  8. Thomas M. Moerland, Joost Broekens, Aske Plaat, Catholijn M. Jonker: Model-based Reinforcement Learning: A Survey. 31. März 2022, doi:10.48550/arxiv.2006.16712, arxiv:2006.16712 [abs].
  9. Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre: Mastering Atari, Go, chess and shogi by planning with a learned model. In: Nature. Band 588, Nr. 7839, Dezember 2020, ISSN 1476-4687, S. 604–609, doi:10.1038/s41586-020-03051-4.
  10. Richard S. Sutton: Integrated Architectures for Learning, Planning and Reacting. In: ACM SIGART Bulletin. Band 2, Nr. 4, 1. Juli 1991, S. 160–163, doi:10.1145/122344.122377 (psu.edu [PDF]).
  11. Daniel Seita: Model-Based Reinforcement Learning:Theory and Practice. Abgerufen am 18. April 2022.
  12. Jean Kaddour, Aengus Lynch, Qi Liu, Matt J. Kusner, Ricardo Silva: Causal Machine Learning. A Survey and Open Problems. 21. Juli 2022, S. 70 ff., arxiv:2206.15475v2.