Bestärkendes Lernen

Bestärkendes Lernen bzw. Verstärkendes Lernen (engl. reinforcement learning) ist der Überbegriff für eine Reihe von Methoden des Maschinellen Lernens, bei denen ein Agent den Nutzen von Aktionsabfolgen in einer Welt bestimmt. Zu diesem Zweck benutzt Bestärkendes Lernen die Theorie der Markow-Entscheidungsprobleme (engl. Markov Decision Processes (MDP)). Konkret formuliert, steht dahinter der Versuch, an einen Agenten ausgeschüttete Belohnungen so über die vorangegangenen Aktionen zu verteilen, dass der Agent den Nutzen einer jeden Aktion kennt und ausnutzen kann.

Einführung

Betrachtet wird ein dynamisches System - bestehend aus einem Agenten und seiner Umgebung (der Welt) - in diskreten Zeitschritten $ t=0,1,2,...\,\! $. Zu jedem Zeitpunkt $ t\,\! $ befindet sich die Welt in einem Zustand $ z_{t}\in Z $ und der Agent wählt eine Aktion $ a_{t}\in A(z_{t}) $ aus. Daraufhin geht die Welt in den Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): z_{t+1}\in Z und der Agent erhält eine Belohnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b_t\in B .

Erwarteter Gewinn

Ziel ist es den erwarteten Gewinn (engl. expected return)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): B_t = \sum_{k=0}^N \delta^k\cdot b_{t+k+1} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 0\le\delta\le 1

zu maximieren. Der erwartete Gewinn ist also so etwas wie die erwartete Gesamtbelohnung. Dabei nennt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \delta\,\! 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \delta=1\,\! . In diesem Fall wird jede Belohnung $ b_{t+k+1}\,\! $ gleich gewertet. Bei kontinuierlichen Problemen (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): N=\infty ) muss man ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \delta<1\,\! wählen, damit die unendliche Reihe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): B_t\,\! konvergiert. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \delta=0\,\! zählt nur die aktuelle Belohnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b_t\,\! ; alle zukünftigen Belohnungen werden ignoriert. Geht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \delta\,\! 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): s:Z \rightarrow A(Z) 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: $ s(z,a)=p(a|s)\quad $.

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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): p(z_{t+1},r_{t+1}|z_{0:t},a_{0:t},b_{0:t})=p(z_{t+1},r_{t+1}|z_{t},a_{t})\,\! .

Zentrale Begriffe eines Markow-Entscheidungsprozess sind das Aktionsmodell (oder Transitionswahrscheinlichkeit) und die erwartete Belohnung im nächsten Zeitschritt (engl. expected reward). Das Aktionsmodell Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): p(z_{t+1}|z_{t},a_{t})\,\! ist die bedingte Wahrscheinlichkeitsverteilung, dass die Welt von Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): z_{t}\,\! in Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): z_{t+1}\,\! übergeht, falls der Agent die Aktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a_t\,\! 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b(z_t,z_{t+1},a_t):=E\{b_{t+1}|z_t,z_{t+1},a_t\}\,\! .

Approximation

Bei unendlichen Zustandsräumen muss diese Nutzenfunktion approximiert werden, z. B. mit Neuronalen Netzen^[1] 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.^[2]

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 3-8273-7089-2 (deutsche Übersetzung der 2. Auflage) Kapitel 21.

Weblinks

• Tutorial zu Reinforcement Learning (englisch, PDF; 101 kB)
• 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)