ベルマン方程式
ある状態で実現しうる最良の目的関数の値を示す関数を 価値関数 (value function) と呼ぶ。
リチャード・ベルマンは、離散時間形式の動的最適化問題が、ある時刻の価値関数とその次の時刻の価値関数の間の関係式を書き下すことによって、再帰的な、後ろ向き帰納法(英語版)(backward induction)と呼ばれる逐次的な形式で表現できることを示した。上述の時間的に隣接する二つの価値関数の関係式がベルマン方程式である。このアプローチでは、終端時刻における最適な方策は、その時刻の状態変数の関数としてすでに決まっており、結果として得られる目的関数の最適値は状態変数で与えられる。次に、最後から一つ前の時刻の最適化を考えると、決定に際して、その状態変数に付随する最適な方策のもとで、その時刻の目的関数と未来の目的関数の和を最大化する。このアルゴリズムは、再帰的に時間を遡る形で進み、初期時刻において、初期状態の関数としての決定ルールが初期時刻に固有の目的関数と2番目のステップの価値関数(第2ステップ以降すべての未来の価値)の和の最適化計算によって得られるまで繰り返される。ゆえに、各ステップにおける決定は、それ以降の未来すべての判断が最適である事を前提として行われるのである。