Heuristische dynamische Programmierung

Werbos' heuristische dynamische Programmierung (HDP) [74] [73] [75] begreift sich als eine Erweiterung der adaptiven Kritiker.

Es wird wieder angenommen, daß der komplette Zustand $R_t$ der Umgebung eines lernenden Systems zur Zeit $t$ als Eingabevektor vorliegt. Gegeben sei weiterhin eine Nutzenfunktion $U$, welche Aussagen über die Güte von Aktionssequenzen (Sequenzen von Transformationen, die den Umweltzustand verändern) liefert.

Die Kunst bei der dynamischen Programmierung kann in nichtstationären Umgebungen (wie bereits früher ausgeführt) darin gesehen werden, eine Funktion $J$ anzugeben, deren Minimierung zum Zeitpunkt $t$ schon bedeutet, diejenige Aktion für die Transformation von $R_t$ nach $R_{t+1}$ zu wählen, die auch für die Minimierung von $U$ notwendig ist. Ein Problem bei der dynamischen Programmierung ist, daß trotz der gewaltigen Einsparungen im Vergleich zur erschöpfenden Suche die Anzahl der Berechnungen in der Regel immer noch exponentiell mit der Anzahl der Komponenten von $R$ steigt.

Die heuristische dynamische Programmierung versucht nun, $J$ nicht zu berechnen, sondern nur zu schätzen. Der Schätzer ist ein überwacht lernendes neuronales Netzwerk, typischerweise ein BP-Netz, und wird im folgenden in Analogie zu den Reinforcementvergleichsalgorithmen wieder der Kritiker genannt.

Die Nutzenfunktion $U$ habe die Form

$$U = u(R_1 ) + u(R_2 ) + \ldots + u(R_m ) ,$$

wobei $m$ unendlich sein kann.

Die Überwachung ist nicht durch einen externen Lehrer gegeben, sondern durch sukzessive Ausgaben des Kritikers selbst: Die gewünschte Ausgabe zum Zeitpunkt $t$ eines Trainingsintervalls ist gegeben durch

$$J(R_{t+1}) + u(R_t).$$

Dabei hängt $J$ außer von der Umgebung nur von dem gegenwärtigen Gewichtsvektor $w$ ab, der für die Dauer eines Trainingsintervalls allerdings konstant bleibt. $J$ soll zu einem gegebenen Zeitpunkt ausdrücken, was zu erwarten ist, wenn man mit dem gegenwärtigen Steuernetzwerk weitermacht. Konventionelles Back-Propagation dient zur Berechnung der Gewichtsinkremente für alle Zeitpunkte. Erst am Ende des Trainingsintervalls wird jedoch die Gewichtsänderung wirklich ausgeführt.

Eigentlich gibt es bei der dynamischen heuristischen Programmierung keinen sehr wesentlichen Unterschied zu dem im letzten Abschnitt beschriebenen Ansatz. Ein kleinerer Unterschied zu Barto, Sutton, und Andersons Verfahren besteht in der Tatsache, daß die Gewichte nicht on-line geändert werden. Damit begibt man sich auf mathematisch sichereres Pflaster. Werbos konnte unter den gegebenen Bedingungen nachweisen, daß für ein einfaches Lernproblem (bei dem die `idealen' Gewichte auch analytisch berechenbar sind), HDP zu den `idealen' Gewichten hinkonvergiert [75].

Was macht man mit den Voraussagen, die $J$ liefert? Sie können z.B. analog zu Suttons Arbeiten direkt zur Berechnung des internen Reinforcements herangezogen werden. Oder man könnte versuchen, ein drittes azyklisches `Modellnetzwerk' die Umwelt simulieren zu lassen und Fehler vom Kritiker durch das Modellnetz in das Steuernetz zu propagieren. Damit würde man als zusätzliche Komponente den Systemidentifikationsansatz ins Spiel bringen [73] [74][19]. Das Modellnetzwerk könnte (wie früher ausgeführt) dazu beitragen, aus immer noch relativ `uninformierten' internen Reinforcementsignalen `informiertere' zu machen. Vor allem für große Steuernetzwerke ist diese Alternative bedenkenswert.

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