- Reinforcement Learning
-
Bestärkendes Lernen bzw. Verstärkendes Lernen (engl. Reinforcement Learning) ist eine Variante des Maschinellen Lernens, bei dem ein Agent (ein Computerprogramm) lediglich durch ein System von Belohnung und Bestrafung lernt, seinen Nutzen zu optimieren.
Inhaltsverzeichnis
Einführung
Betrachtet wird ein dynamisches System - bestehend aus einem Agenten und seiner Umgebung (der Welt) - in diskreten Zeitschritten . Zu jedem Zeitpunkt befindet sich die Welt in einem Zustand und der Agent wählt eine Aktion aus. Daraufhin geht die Welt in den Zustand und der Agent erhält eine Belohnung .
Erwarteter Gewinn
Ziel ist es den erwarteten Gewinn (engl. expected return)
- mit
zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man den Diskontierungsfaktor (engl. discount factor). Bei episodischen Problemen, d. h. die Welt 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 man ein wählen, damit die unendliche Reihe konvergiert. Für zählt nur die aktuelle Belohnung ; alle zukünftigen Belohnungen werden ignoriert. Geht gegen 1, wird der Agent weitsichtiger.
Strategien
Beim Bestärkenden Lernen verfolgt der Agent eine Strategie (engl. policy). Üblicherweise wird die Strategie als eine Funktion betrachtet, die jedem Zustand eine Aktion zuweist. Jedoch sind auch nichtdeterministische Strategien (oder gemischte Strategien) möglich, sodass eine Aktion mit einer bestimmten Wahrscheinlichkeit ausgewählt wird. Im Allgemeinen wird eine Strategie demnach als bedingte Wahrscheinlichkeitsverteilung definiert: .
Markow-Entscheidungsprozess
Bestärkendes Lernen wird häufig als Markow-Entscheidungsprozess (engl. Markov Decision Process) aufgefasst. Charakteristisch ist die Annahme, dass die Markow-Eigenschaft erfüllt ist:
- .
Zentrale Begriffe eines Markow-Entscheidungsprozess sind das Aktionsmodell (oder Transitionswahrscheinlichkeit) und die erwartete Belohnung im nächsten Zeitschritt (engl. expected reward). Das Aktionsmodell ist die bedingte Wahrscheinlichkeitsverteilung, dass die Welt von Zustand in Zustand übergeht, falls der Agent die Aktion ausgewählt hat. Im deterministischen Fall ist das Aktionsmodell einfach eine Funktion, die einem Zustands-Aktions-Paar einen neuen Zustand zuordnet. Die Erwartete Belohnung ist folgendermaßen definiert
- .
Approximation
Bei unendlichen Zustandsräumen muss diese Nutzenfunktion approximiert werden, z. B. mit Neuronalen Netzen oder Gaußschen Prozessen.
Simultanes Lernen mehrerer Agenten
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.[1]
Literatur
- Richard Sutton, Andrew Barto: Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998 (Online-Version)
- Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz. Pearson Studium, August 2004, ISBN 3827370892 (deutsche Übersetzung der 2. Auflage) Kapitel 21.
- ↑ J. F. Knabe: Kooperatives Reinforcement Lernen in Multiagentensystemen. B. Sc. Thesis, Universität Osnabrück, 2005. http://www.panmental.de/papers/CooperativeRLinMAS.pdf
Weblinks
- Reinforcement learning an Robotern mit neuronalen Netzen, Michel Tokic (deutsch)
- Tutorial zu Reinforcement Learning (englisch, PDF)
- Häufige Fragen (FAQ) zu RL verwaltet von Richard Sutton (englisch)
- Artikel über TD-Gammon, eine KI, basierend auf Verstärkendem Lernen, die Backgammon spielt (englisch)
- Artikel in Scholarpedia (englisch, inkl. Literaturangaben)
Wikimedia Foundation.