ベルマン方程式
時刻 t {\displaystyle t} における状態を x t {\displaystyle x_{t}} とする。時刻0から始まる決定問題において、初期状態 x 0 {\displaystyle x_{0}} は与えられているものとする。任意の時間において、選択可能なアクションはその時の状態の関数であり、 a t ∈ Γ ( x t ) {\displaystyle a_{t}\in \Gamma (x_{t})} と表すことができる。 a t {\displaystyle a_{t}} は一つ以上の制御変数を表している。アクション a {\displaystyle a} が選ばれると、それによって状態は x {\displaystyle x} から新しい状態 T ( x , a ) {\displaystyle T(x,a)} へと変化するものとする。さらに、状態 x {\displaystyle x} においてアクション a {\displaystyle a} をとった時の損得を F ( x , a ) {\displaystyle F(x,a)} で表す。最後に、我々は性急さ(せっかちさ)の度合いが、割引率(discount factor) 0 < β < 1 {\displaystyle 0<\beta <1} で表されるものとする。
動的計画法は、この決定問題をより小さな部分問題に分割する。リチャード・ベルマンの最適性の原理がその方法を示している:
最適性の原理(Principle of Optimality) : 最適な方策は、初期状態と初期決定がどんなものであれ、その結果得られる次の状態に関して、以降の決定が必ず最適方策になっているという性質をもつ。 (参照: Bellman, 1957、Chap. III.3.)
コンピュータ・サイエンスでは、このように分割できる問題の事を「部分構造最適性(英語版)(optimal substructure)を持つ」と表現する。 この原理は、動的ゲーム理論における部分ゲーム完全均衡(subgame perfect equilibrium)と相似な概念である。ただし、動的ゲーム理論における最適方策は、相手プレイヤーが同様に最適方策を選択するという前提に立つ。
最適性の原理から示唆されるように、我々は将来の選択(時刻1から新しい状態 x 1 {\displaystyle x_{1}} でスタートする)について一旦保留して、最初の決定だけを独立に検討する。将来の決定に関する項を大括弧の中に集めることにより、先の問題は次のように表現される。