Die Bellman-Gleichung (auch Bellman-Optimalitätsgleichung) ist eine rekursive Funktionalgleichung, die den optimalen Wert einer Entscheidung als unmittelbare Belohnung plus den optimalen erwarteten Wert aller Folgeentscheidungen beschreibt. Sie geht auf den US-amerikanischen Mathematiker Richard E. Bellman zurück und ist das Fundament der dynamischen Programmierung sowie vieler Verfahren des Reinforcement Learning.
Optimalitätsprinzip
Bellman formulierte das Prinzip der Optimalität: Eine optimale Policy hat die Eigenschaft, dass unabhängig vom Ausgangszustand und der ersten Entscheidung die verbleibenden Entscheidungen eine optimale Policy für den resultierenden Zustand bilden müssen. Dadurch lässt sich ein komplexes Optimierungsproblem in einfachere Teilprobleme zerlegen, die rekursiv lösbar sind.
Die Gleichung
Für einen Markov-Entscheidungsprozess lautet die Bellman-Optimalitätsgleichung für den optimalen Wert V*(s) eines Zustands s: V*(s) = max über a von [R(s,a) + γ mal Summe über s' von P(s'|s,a) mal V*(s')]. Der optimale Wert ist also die beste unmittelbare Belohnung plus der diskontierte erwartete optimale Wert des Folgezustands. Eine analoge Gleichung existiert für die optimale Aktionswertfunktion Q*(s,a).
Bedeutung für Lernalgorithmen
Verfahren wie Value Iteration und Policy Iteration nutzen die Gleichung direkt, um optimale Werte zu berechnen. Lernende Verfahren approximieren sie aus Daten: Q-Learning aktualisiert Q-Werte mit einer Stichprobe der Gleichung, Temporal-Difference-Learning schätzt die Wertfunktion, ohne ein Modell der Umgebung zu benötigen. Die Bellman-Gleichung verknüpft damit Theorie und Praxis des Reinforcement Learning.
Verwandte Grundlagen: Markov-Entscheidungsprozess, Wertfunktion.