Bellman-Gleichung

Die Bellman-Gleichung ist der mathematische Ausdruck des **Optimalitätsprinzips**, das Richard Bellman in seinem Buch von 1957 (*Dynamic Programming*, Princeton University Press) formalisierte: eine optimale Politik hat die Eigenschaft, dass — was immer Anfangszustand und Erstentscheidung sind — die verbleibenden Entscheidungen eine optimale Politik bezüglich des Folgezustandes bilden müssen. Für ein deterministisches Problem mit endlichem Horizont lautet sie V*(s) = max_a { r(s, a) + V*(s') }, wobei V*(s) den optimalen Gesamtgewinn aus Zustand s, r(s, a) die Sofortbelohnung und s' den Zustand nach Aktion a bezeichnet. Für ein diskontiertes Problem mit unendlichem Horizont lautet sie V*(s) = max_a { r(s, a) + γ E[V*(s')] }, mit Diskontfaktor γ ∈ (0, 1). Für stochastische Entscheidungsprozesse (Markov Decision Processes, MDP) sind Bellman und Dreyfus (1962) und Bertsekas (1995) *Dynamic Programming and Optimal Control* die Standardreferenzen; die Hamilton-Jacobi-Bellman-PDE ist die kontinuierliche-zeitliche Differentialform desselben Prinzips für stochastische Kontrolle. Klassische Lösungsalgorithmen für die Bellman-Gleichung umfassen Value Iteration (tabellenbasierte rekursive Aktualisierung), Policy Iteration (Howard 1960) und die LP-Reformulierung (Manne 1960). Die Bellman-Gleichung ist der gemeinsame Kern von Bestandsmanagement (Wagner-Whitin-Lot-Sizing 1958), Ausrüstungsersatz (Bellman 1955), Travelling Salesman (Held-Karp DP 1962), Portfolioauswahl (Merton 1969) und jeder dynamischen Programmieranwendung in OR/CS. Stochastic Dual Dynamic Programming (SDDP, Pereira und Pinto 1991) und Approximate Dynamic Programming (Powell 2007) sind moderne Ansätze für hochdimensionale Bellman-Gleichungen.