Achtung Baustelle! Dies ist nur eine Bearbeitungsversion

Bearbeiten

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

Bearbeiten

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 das System in den Zustand   und der Agent erhält eine Belohnung  .

Erwarteter Gewinn

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Bei unendlichen Zustandsräumen muss diese Nutzenfunktion approximiert werden, z. B. mit Neuronalen Netzen[1] oder Gaußschen Prozessen.

Simultanes Lernen mehrerer Agenten

Bearbeiten

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]

Beispiel

Bearbeiten

In dem folgendem Beispiel wird Bestärkendes Lernen eingesetzt, um eine künstliche Intelligenz (KI) für das bekannte Spiel Tic Tac Toe zu trainieren. Voraussetzung an den trainierenden Gegner sei, dass dieser noch nicht perfekt spielt, sondern gelegentlich Fehlentscheidungen trifft, um der KI eine Möglichkeit zum Lernen zu geben. Diese Bedinung ist nötig, da ein perfekter Tic Tac Toe Spieler niemals eine Spielrunde verlöre und die künstliche Intelligenz keine Gelegenheit bekäme, zu lernen, wie Fehler des Gegners ausgenutzt werden können. Ferner sei anzunehmen, dass die KI immer als Spieler X spielt.

Zunächst wird eine Tabelle angelegt, die jeden möglichen möglichen Spielzustand enthält ( ). Im Vergleich zu anderen Spielen wie Schach ist die Anzahl der möglichen Spielzustände bei Tic Tac Toe überschaubar. Weiterhin wird in der Tabelle jedem Spielzustand eine Bewertung zugeordnet. Je höher die Bewertung eines Spielzustandes ist, desto besser ist die Spielstellung für den Spieler X, d.h. für die KI. Die Bewertungen werden wie folgt initialisiert:

  • Für jeden Spielzustand, in denen drei O in einer Reihe stehen, wird die Bewertung 0 festgelegt, da der Spieler X verloren hat.
  • Für jeden Spielzustand, in denen drei X in einer Reihe stehen, wird die Bewertung 1 festgelegt, da der Spieler X gewonnen hat.
  • Für jeden anderen Spielzustand wird die Bewertung mit 0,5 initialisiert.

Die Tabelle lässt sich auch als Relation   beschreiben, die zu jedem möglichen Spielzustand  eine Bewertung als reelle Zahl kennt. Als mögliche Spielzüge gelten jeweils alle verbleibenden freien Felder des Spielbretts, auf dem der Spieler sein Symbol setzen kann. Für jeden Spielzug von Spieler X wird mit einer bestimmten Wahrscheinlichkeit   ein erkundender Zug gewählt, andernfalls ein erfahrener Zug. Dabei gillt:

  • Bei einem erkundenden Zug wird rein zufällig gezogen.
  • Bei einem erfahrenen Zug wird so gezogen, dass der dadurch entstehende neue Spielzustand ( ) die höchste Bewertung gemäs der Tabelle erzielt. Wenn mehrere Züge zur gleichen Bewertung führen würden und kein anderer Zug eine bessere Bewertung erzielt, so wird zwischen diesen Zügen zufällig gewählt.

Optimierung

Bearbeiten

Um einen Lerneffekt zu erwirken, wird nach jedem erfahrenen Zug, der zum Spielstatus   mit der Bewertung   führt, die Bewertung   des vorhergehenden Spielzustandes  , an dem X auch am Zug war, in der Tabelle nach der Formel angepasst:

 

Dabei ist   ein festgelegter Trainingsfaktor. Nach vielen Spielrunden wird die Bewertung der Zustände   immer genauer und somit werden die erfahrenen Züge immer gewinnversprechender. Mit der Zeit gelingt es der KI dadurch, Fehler des Gegners auszunutzen und die Gewinnrate zu steigern.

Justieren der Trainingsparameter

Bearbeiten

Zu Beginn des Trainings müssen die Wahrscheinlich für einen erkundenden Zug   und der Trainingsfaktor   relativ hoch angesetzt werden, beispielsweise auf   und  . Je höher die Wahrscheinlichkeit  , desto eifriger lernt die KI neue und noch unbekannte Spielzustände, nutzt dafür jedoch auch weniger bereits erlernte Strategien. Je höher der Trainingsfaktor  , desto schneller aber auch ungenauer lernt die KI. Beide Werte müssen deshalb während vielen Spielrunden ständig verkleinert werden, damit die KI feinere Strategien lernt und einsetzt. Die KI passt sich damit immer mehr auf das Spielverhalten des Trainingsgegners an und approximiert. Wenn der Trainingsgegner jedoch nur eine einseitige Strategie einsetzte und die KI nun gegen einen Gegner mit ganz anderer Strategie spielen muss, so müssen beide Trainingsparameter   und   wieder leicht erhöht werden, um eine erneute Anpassung an den neuen Gegner zu ermöglichen.

Lösung des Markow-Entscheidungsproblems

Bearbeiten

Als Lösen eines Markow-Entscheidungsproblems gillt das Maximieren des erwarteten Gewinns. Im Beispiel kann der erwartete Gewinn maximiert werden, indem immer erfahrene Züge gewählt werden, d.h. immer der Zug gewählt wird, der zum Zustand   mit der besten Bewertung   führt.

Literatur

Bearbeiten

Literatur

Bearbeiten
  • 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.
  1. Michel Tokic: Reinforcement Learning an Robotern mit Neuronalen Netzen, M.Sc. Thesis, University of Applied Sciences Ravensburg-Weingarten, 2008. (Online-Version)
  2. J. F. Knabe: Kooperatives Reinforcement Lernen in Multiagentensystemen. B. Sc. Thesis, Universität Osnabrück, 2005. http://www.panmental.de/papers/CooperativeRLinMAS.pdf
Bearbeiten