Reinforcementvergleichsalgorithmen

Ohne es so zu nennen, wendete Samuel schon 1959 als erster ein Reinforcementvergleichsverfahren an [47]. Samuel schrieb ein Programm, welches lernte, `Dame' zu spielen. Dabei verwendete er eine Vielzahl von Techniken, was es zunächst nicht leicht macht, das Wesentliche an seinem Lernverfahren zu sehen. (Unter anderem war Samuel der erste, der das heute weithin gebräuchliche `alpha-beta-pruning' zur planenden Vorausschau benutzte.)

Das Wesentliche an Samuels Lernverfahren läßt sich durch folgendes Prinzip beschreiben:

Findet ein lernendes System eine Transition von einem von ihm selbst als schlecht eingeschätzten Zustand in einen von ihm selbst als gut eingeschätzten Zustand, so sollte diese Transition in ähnlicher Situation künftig ermutigt werden. Außerdem sollte der früher als schlecht eingeschätzte Zustand von nun an eher als gut beurteilt werden.

Ganz analog gilt:

Erfährt ein lernendes System, daß eine bestimmte Aktion in einem von ihm selbst als gut eingeschätzten Zustand stets einen als schlecht eingeschätzten Zustand nach sich zieht, so sollte diese Aktion in ähnlicher Situation künftig vermieden werden. Außerdem sollte der früher als gut eingeschätzte Zustand von nun an eher als schlecht beurteilt werden.

Die durch diese Prinzipien implizierte Rekursion wird durch die Umgebung beendet: Manchmal gibt es eben Situationen, bei denen man objektiv weiß, ob sie `schlecht' oder `gut' sind.

Bei Spielen wie `Dame' gibt es nur eine am Schluß des Spiels vergebene binäre Bewertung: `Gut' ist der Sieg, `schlecht' ist die Niederlage. Dem oben implizierten `Beurteiler' oder Kritiker obliegt es, aus dieser uninformierten Bewertung eine informiertere zu machen.

Samuels Kritiker war adaptiv: Er bestand aus einem linearen Polynom, dessen Variablen nach jedem Zug durch bestimmte vorprogrammierte Spielzustandsanalysen gesetzt wurden, und dessen Koeffizienten im wesentlichen nach den obigen einfachen Prinzipien adjustiert wurden. Mit der Zeit lernte das System durch das `Nachhintenschieben von Erwartungen über den Ausgang eines Spiels', schon frühzeitig (lange vor Ende des Spiels) `in die Zukunft zu blicken' und die Prognosen für sofortiges Handeln in Form von Wahrscheinlichermachen oder Unwahrscheinlichermachen bestimmter Züge auszunützen.

Heute würde man sagen, daß Samuels Kritiker die Form eines Perzeptrons hatte. Es ist das Verdienst von Barto, Sutton, und Anderson, Samuels Prinzip in isolierter Form studiert zu haben [5]. Sie kombinierten zwei neuronenähnliche Elemente namens `associative search element' $(ASE)$ und `adaptive critic element' $(ACE)$ auf folgende Weise:

Von der Umgebung kommt zu jedem Zeitpunkt $t$ ein Eingabevektor $x_t$ sowohl für $ASE$ als auch für $ACE$. $x_t$ hat die Eigenschaft, daß alle seiner Komponenten gleich $0$ sind bis auf eine, weche den Wert $1$ hat und den sichtbaren Zustand der externen Umgebung repräsentiert. Die Anzahl der möglichen Zustände der Umgebung sollte die Dimensionalität des Eingabevektors also nicht übersteigen.

Die Ausgabe von $ASE$ ist definiert als

$$y_t = f(w_t^T x_t) + ~ noise_t,$$

wobei $w_t$ $ASE$'s Gewichtsvektor, $f$ eine sigmoide Funktion oder eine Schwellenfunktion und $noise_t$ zufälliges Rauschen bedeutet. Die Gewichtsänderung wird definiert durch

$$\triangle w_t = \alpha \hat{r}_t x_t .$$

Dabei ist $\alpha$ eine positive Lernrate, und $\hat{r}_t$ das interne Reinforcement zur Zeit $t$. (In einer Erweiterung dieser Regel taucht auch noch ein Eligibilitätsvektor $e_t$ auf, dieser erschwert allerdings nur den Blick auf das Wesentliche des Verfahrens.)

Der Trick ist nun die Berechnung des internen Reinforcements $\hat{r}_t$. Dafür ist $ACE$ zuständig. $ACE$ macht eine Voraussage $P_t$ über das in Zukunft zu erwartende Reinforcement. Seine Ausgabe ist gegeben durch

$$P_t = v_t^T x_t,$$

wobei $v_t$ $AHC$'s Gewichtsvektor ist. Die Gewichtsänderung wird definiert durch

$$\triangle v_t = \beta (r_t + \gamma P_t - P_{t-1})x_t .$$

Dabei ist $\beta$ eine positive Lernrate, $r_t$ das externe Reinforcement zur Zeit $t$ und $0 < \gamma \leq 1$ ein Schwundfaktor, von dem wir vorläufig annehmen, daß er gleich $1$ ist. (In einer Erweiterung dieser Regel taucht auch noch eine exponentiell schwindende Spur vergangener Eingabevektoren auf, um die wir uns jetzt nicht kümmern wollen, da sie wiederum nur den Blick auf das Wesentliche des Lernverfahrens verstellt.)

Was $AHC$ tut, ist eigentlich nichts anderes, als die TD$(0)$-Methode für den Fall kumulativen Reinforcements zu implementieren (siehe Kapitel 2, Abschnitt 4). Betrachtet man die Berechnung von

$$\hat{r}_t = r_t + \gamma P_t - P_{t-1},$$

so stellt man für $\gamma = 1$ fest, daß Samuels oben angegebenes Prinzip zur Anwendung kommt: Der Vergleich sukzessiver Einschätzungen des zu erwartenden Reinforcements führt zur Gewichtsänderung für das Steuerelement ASE. Eine Verallgemeinerung dieses Prinzips für unbegrenzt lange Zeitdauern wird durch $\gamma < 1$ ermöglicht ($\gamma$ verhindert potentiell unendliche Summen).

Es muß erwähnt werden, daß es bisher keine allgemeine Theorie für das gleichzeitige Lernen von interagierenden AHC- und ASE-Elementen gibt. (Die existierende Theorie der TD-Methoden sagt nämlich zunächst nichts über Konvergenzeigenschaften von Reinforcementvergleichsalgorithmen aus.) So ist nicht auszuschließen, daß das oben beschriebene on-line-Verfahren für Instabilitäten anfällig ist. In jüngster Zeit zeigten allerdings Untersuchungen zu extrem simplifizierten Versionen des Ansatzes, daß zumindest unter bestimmten einschränkenden Bedingungen die Konvergenz beider parallel lernender Systeme garantiert werden kann [79].

Suttons Ph.-D.-Arbeit besteht im wesentlichen in der Isolierung des Prinzips der Reinforcementvergleichsverfahren und seiner Illustrierung durch ein Balancierproblem [66]. Seine weiterführenden Arbeiten über TD-Methoden kamen erst später und waren durch die Ergebnisse mit den Reinforcementvergleichsalgorithmen motiviert [67].

Anderson führte Suttons Arbeit über Reinforcementsvergleichsalgorithmen fort. Der Beitrag seiner Ph.-D.-Arbeit besteht im wesentlichen darin, die Perzeptron-ähnlichen Einheiten durch jeweils ein azyklisches Netzwerk zu ersetzen [2]. Andersons Kritiker ist ein BP-Netzwerk, welches in TD(0)-Manier auf `selbstüberwachte' Weise die entsprechenden Gewichtsänderungen berechnet. Damit ist man nicht mehr durch den Zwang zur linearen Separabilität eingeschränkt. (Auch Watkins' Algorithmen sind mit Reinforcementsvergleichsalgorithmen eng verwandt [71].)

In Kapitel 6 werden wir Reinforcementvergleichsalgorithmen auf den allgemeinen Fall rekurrenter Netze erweitern. Auch wird eine Möglichkeit zur Implementierung mehrdimensionaler adaptiver Kritiker beschrieben werden. (Alle bisherigen adaptiven Kritiker machen ja nur eine eindimensionale Voraussage über eine skalare Größe. Damit verzichten sie auf Information, die man aus verschiedenen Arten von Reinforcement (oder `Schmerz') ziehen könnte.)

Related links in English: Recurrent neural networks - Subgoal learning - Reinforcement learning and POMDPs - Reinforcement learning economies - Selective attention
Deutsche Heimseite