Ein rekursiver Optimierungsrahmen, der mehrstufige Entscheidungsprobleme in sich überschneidende Teilprobleme zerlegt, die durch Rückwärts- oder Vorwärtsinduktion gelöst werden; die Wertfunktion zentralisiert die optimalen zukünftigen Erträge.

Prinzip

Bellmans Prinzip der Optimalität: Eine optimale Strategie hat die Eigenschaft, dass unabhängig vom Anfangszustand und der ersten Entscheidung die restlichen Entscheidungen eine optimale Strategie für den resultierenden Zustand bilden; Rekursion auf Wertfunktionen implementiert dies.

Demonstration

Im endlichen Horizont-Kontrollproblem berechne man die Restkosten V_t(x) durch Rückwärtsinduktion: V_T(x)=Terminalkosten und V_t(x)=min_u{ stage_cost(x,u)+V_{t+1}(f(x,u)) } bis t=0, wodurch eine optimale Steuerfolge entsteht.

Fehlanwendung

Nicht-Markov-Probleme fälschlich als Markov behandeln ohne Zustanderweiterung oder versuchen, exakte tabellarische DP in hochdimensionalen Räumen ohne Approximation anzuwenden (Fluch der Dimensionalität), führt zu falschen oder unlösbaren Ergebnissen.

Konsequenz

Richtige Anwendung liefert optimale Politiken und Wertfunktionen, brauchbare Zerlegungen für viele strukturierte Probleme und bildet die Grundlage für Algorithmen in Steuerung und Reinforcement Learning, erfordert bei großem Maßstab jedoch oft Approximationen.

Umkehrung

Greedy- oder myopische Methoden treffen lokal optimale Entscheidungen ohne Rekursion und finden typischerweise keine global optimalen mehrstufigen Strategien, wenn zukünftige Kosten die gegenwärtige Entscheidung stark beeinflussen.

Abgrenzung

Anwendbar, wenn das Problem stufenweise zerlegbar ist und eine Markov-Übergangsstruktur oder gleichwertige Zustanderweiterung besitzt; schließt direkt teilweise beobachtete Probleme oder nicht separierbare Ziele ohne Umformulierung aus.

Semantische Spannung

Spannung zu approximativer dynamischer Programmierung und Reinforcement Learning: DP liefert exakte Rekursion und Garantien, wenn möglich, während Approximationen Optimalität gegen Praktikabilität und Generalisierbarkeit in hochdimensionalen oder stochastischen Umgebungen eintauschen.

Synthese

Dynamische Programmierung = Bellmans Optimalität nutzen, um globale mehrstufige Optimierung als rekursive lokale Probleme über Wertfunktionen darzustellen, durch Rückwärts-/Vorwärtsinduktion oder iterative Backups lösen und Komplexität bei Bedarf durch Approximation reduzieren.