Approximate Dynamic Programming ist ein mathematischer Optimierungsansatz, der im betriebswirtschaftlichen Kontext vor allem zum Lösen mehrstufiger stochastischer Optimierungsprobleme eingesetzt wird. Der Ansatz vereint ein breites Spektrum an Methoden aus den Bereichen mathematische Programmierung, Simulation und statistisches Lernen.
Stochastische Optimierungsprobleme
Mehrstufige stochastische Optimierungsprobleme treten im betriebswirtschaftlichen Kontext meist auf, wenn eine Reihe von zeitlich aufeinanderfolgenden Entscheidungen getroffen wird. Zwischen zwei Entscheidungen kann sich die Informationslage durch exogene Einflüsse (wie neu eintreffende Kundenaufträge) verändern. Um über alle Entscheidungsschritte hinweg den erwarteten Gesamtzielerreichungsgrad zu maximieren, sollte jede Entscheidung mögliche zukünftige Änderungen der Informationslage sowie mögliche Folgeentscheidungen optimal antizipieren. Approximate Dynamic Programming zielt darauf, solche Entscheidungen zu ermöglichen. Mehrstufige stochastische Optimierungsprobleme treten in zahlreichen Gebieten auf. Beispiele sind der Wertpapierhandel unter schwankenden Preisen und die Tourenplanung mit nachträglich auftretenden Kundenanfragen.
Modellierung als Dynamisches Programm
Das Lösen eines stochastischen Optimierungsproblems mit Approximate Dynamic Programming setzt dessen Modellierung als Dynamisches Programm voraus. Die Modellierung umfasst fünf Elemente [Powell 2011, S. 168]:
-
Zustandsvariablen: Sie repräsentieren an jedem Entscheidungszeitpunkt die zum Berechnen von Entscheidung und Zustandsübergang benötigte Information.
-
Entscheidungsvariablen: Sie werden vom Entscheider kontrolliert. Für jeden Zeitpunkt wird die Menge zulässiger Entscheidungen modelliert.
-
Exogene Informationsprozesse: Diese Zufallsvariablen repräsentieren die auf den Entscheider von außen (zufällig) eintreffende Information.
-
Zustandsübergangsfunktion: Diese Funktion definiert, wie sich die Zustandsvariablen durch eine Entscheidung und durch neu eintreffende exogene Information von einem Zeitpunkt zum folgenden verändern.
-
Zielfunktion: Diese Funktion definiert welche Kosten (welcher Gewinn) an einem Entscheidungszeitpunkt entstehen.
Optimale Lösung
Jede Lösung eines mehrstufigen stochastischen Optimierungsproblems repräsentiert eine Entscheidungsregel (engl. „policy“) [Powell 2011, S. 221]. Eine Policy ist eine Funktion, welche die Information eines beliebigen gegebenen Zustands auf eine zu treffende zulässige Entscheidung abbildet.
Zur Herleitung einer optimalen Policy kann das Konzept der Wertfunktion (engl. „value function“) genutzt werden. Eine Value Function ordnet jedem Zustand seinen Wert im Sinne der bis zum letzten Entscheidungsschritt erwarteten Folgekosten (Folgegewinne) zu.
Den Ansatzpunkt zur Berechnung der Value Function für eine optimale Policy liefert die Bellman Gleichung [Bellman, 1957]. Sie beschreibt den Zusammenhang zwischen dem Wert eines Zustandes und dem Wert seiner möglichen direkten Folgezustände. Das resultierende System von Bellman Gleichungen hat als Lösung die Value Function für eine optimale Policy.
Exakte Verfahren zum Lösen des Gleichungssystems sind unter dem Namen Stochastic Dynamic Programming [Puterman, 2005] bekannt. Diese Verfahren haben jedoch für die allermeisten betriebswirtschaftlichen Optimierungsprobleme extrem hohe Laufzeiten und sind deshalb praktisch nicht anwendbar. Approximate Dynamic Programming zielt auf eine bestmögliche Approximation an die optimale Value Function (an die optimale Policy) mit geringen Laufzeiten.
Approximative Lösung
Approximate Dynamic Programming Verfahren folgen meist den aus dem Stochastic Dynamic Programming bekannten Grundprinzipien „Value Iteration“ und „Policy Iteration“. Sie sind lernende Verfahren, die iterativ neue Policies berechnen. Eine Policy wird jeweils aus statistischen Schätzern für Zustandswerte abgeleitet. Häufige Vorgehensweisen zur schnellen Erzeugung von Schätzern sind:
-
Repräsentation der Value Function als parametrische Funktion
-
Definition einer Value Function auf aggregiertem Zustandsraum
-
Generierung von Stichproben für Zustandswerte durch Monte Carlo Simulation
-
Aktualisieren der Wertschätzer durch stochastische Gradientenverfahren
Oft ist es mit Approximate Dynamic Programming möglich, in sehr kurzer Zeit eine gute Lösung für das betrachtete Optimierungsproblem zu berechnen. Die Lösung ist in der Regel nicht optimal. Jedoch gibt es für praxisrelevante stochastische Optimierungsprobleme meist keinen alternativen Ansatz, der ohne Value Function Approximation eine optimale Policy garantiert. Für eine ausführliche Einführung in Approximate Dynamic Programming sei auf die Werke von Powell [Powell, 2011] und Bertsekas [Bertsekas, 2012] verwiesen.
Literatur
Bellman, Richard: Dynamic Programming. Princeton University Press : Princeton, NJ, 1957
Bertsekas, Dimitri: Dynamic Programming and Optimal Control : Approximate Dynamic Programming. 4. Auflage. Athena Scientific : Belmont, MA 2012.
Powell, Warren B.: Approximate Dynamic Programming : Solving the Curses of Dimensionality. 2. Auflage. Wiley : Hoboken, NJ 2011.
Puterman, Martin L.: Markov Decision Processes : Discrete Stochastic Dynamic Programming. 2. Auflage. Wiley : Hoboken, NJ 2005
