Dynamische Programmierung

Für gewisse `mehrstufige Entscheidungsprozesse' (was das genau ist, wird unten beschrieben) gibt es etablierte Techniken, die in vieler Hinsicht wesentlich günstiger sind als erschöpfende Suche.

Ein `diskreter deterministischer mehrstufiger Entscheidungsprozeß' (wir werden uns hier auf diese Sorte beschränken, obwohl die Verallgemeinerung keine Schwierigkeiten bereitet) ist ein Prozeß, bei dem endlich oder höchstens abzählbar viele Transformationen (auch Entscheidungen genannt) den Prozeßverlauf bestimmen. Der Prozeß startet im Zustand $p_{1}$, für $t > 1$ wird der Zustand $p_{t}$ durch eine deterministische Entscheidung $q_{t-1}$ (aus einer gegebenen Menge möglicher Entscheidungen) und $p_{t-1}$ bestimmt:

$$p_{t} = T( p_{t-1}, q_{t-1} ).$$

Zu maximieren sei für einen $n$-stufigen Prozeß eine Kostenfunktion $U( q_{1}, q_{2}, \ldots, q_{n})$.

Unter der Voraussetzung, daß der Prozeß die Markov-Eigenschaft besitzt (letztere wird unten nochmals in Erinnerung gerufen), braucht man nicht alle möglichen Kombinationen von Aktionen durchzuprobieren, sondern man kann sich auf relativ wenige Kombinationen beschränken.

Ein $n$-stufiger Prozeß hat die Markov-Eigenschaft, wenn nach $k$ Entscheidungen der Effekt der ausstehenden $n-k$ Entscheidungen auf die Kostenfunktion $U$ nur noch von dem Zustand des Systems nach der $k$-ten Entscheidung und den folgenden Entscheidungen abhängt.

Hat $U$ z.B. die Form

$$U = u( p_{1}, q_{1}) + u( p_{2}, q_{2}) + \ldots + u( p_{n}, q_{n}) ,$$

so ist die Markov-Eigenschaft gewährleistet.

Viele deterministische Prozesse sind Markov-Prozesse. Ein Beispiel sind nahezu alle Brettspiele: Es kommt nicht darauf an, wie man zu einem Spielzustand gekommen ist. Alle Information, die man zum Weiterspielen braucht, ist in dem gegenwärtigen Zustand enthalten.

Viele Prozesse sind jedoch keine Markov-Prozesse. Insbesondere für biologische Systeme typische Handlungsweisen hängen oft nicht nur vom gegenwärtig wahrnehmbaren Zustand der Umgebung ab, sondern auch von vergangenen Perzeptionen.

Für Markov-Prozesse spielt nun Bellmans Optimalitätsprinzip eine entscheidende Rolle:

Eine optimale Folge von sukzessiven Entscheidungen (eine optimale Strategie) hat die Eigenschaft, daß unabhängig vom Initialzustand des Prozesses und der ersten Entscheidung die noch ausstehenden Entscheidungen eine optimale Strategie bezüglich des Zustands darstellen, der aus der ersten Entscheidung resultiert.

Das Optimalitätsprinzip führt für Markov-Prozesse zum Ansatz der dynamischen Programmierung [6]. Rekursiv definiert man sich eine Menge von Funktionen wie folgt:

$$f_{1}( p_{1}) = Max_{q_{1}} u( p_{1}, q_{1})$$

und

$$f_{t}( p_{1}) = Max_{q_{1}} ( u( p_{1}, q_{1}) + f_{t-1}( T( p_{1}, q_{1} ) ) )$$

Durch das Optimalitätsprinzip ist der Beitrag der letzten $n-1$ Schritte gleich $f_{n-1}( T( p_{1}, q_{1} ) )$.

Die wesentliche Auswirkung der dynamischen Programmierung ist: Die Auswahloperation eines Punktes im $pn$-dimensionalen Raum wird reduziert auf $n$ Auswahloperationen im $p$-dimensionalen Raum (hierbei ist $p$ die Zahl der Dimensionen, die zur Beschreibung der Prozeßzustände notwendig sind, im allgemeinen kann man sich also, wenn auch nicht notwendigerweise auf einen $1$-dimensionalen, so doch zumindest auf einen niederdimensionalen Raum beschränken). Damit erspart man sich bei der Suche oft sehr viele von vornherein auszuschließende Sackgassen.

In nichtstationären Umgebungen kann die Kunst bei der dynamischen Programmierung 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 immer noch exponentiell mit der Anzahl der Komponenten der Prozeßzustandsbeschreibungen steigt.

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