ベルマン方程式
これまでのところ、我々は単に現在の決定を未来の決定から分割することによって、単に問題を厄介にしたにすぎないように見える。だが、右側の角括弧の中を状態 x 1 = T ( x 0 , a 0 ) {\displaystyle x_{1}=T(x_{0},a_{0})} から始まった時点1における意思決定問題の価値として表せたことで、問題の単純化が可能になっている。
従って、問題を価値関数に関する再帰的な定義式として書き直すことができる。
V ( x 0 ) = max a 0 { F ( x 0 , a 0 ) + β V ( x 1 ) } {\displaystyle V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}}
ただし次の条件のもとで:
a 0 ∈ Γ ( x 0 ) , x 1 = T ( x 0 , a 0 ) . {\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).
ベルマン方程式を理解するには、いくつかの背景となる概念を理解しなくてはならない。 第一に、最適化問題は何らかの目標を持つ。具体例を挙げれば、移動時間を最短にする、コストを最小に抑える、利益を最大化する、効用を最大化する、などである。これらの目標を数学の関数で表現したものを 目的関数 (objective function) と呼ぶ。
動的計画法は複数段階にわたる計画問題を、各時点の簡単な手順へと分解する。そのため、ある時点でなされた決定がそれ以降どのように影響を及ぼすか正しく記述しなくてはならない。正しい判断を下すために必要な現在の状況を示す情報を 状態 (state) と呼ぶ。例えば、人がある時点で何をどれだけ消費するか決めるには、(何よりもまず)現在の富(資産額)を知らなくてはならない。 そのゆえ、富は、経済活動を行う人が持つ状態変数(英語版)の一つと考えられる。言うまでもなく、このような状態変数は他にも存在する。
任意の時点で選ぶことのできる変数を通常 制御変数(英語版) (control variables) と呼ぶ。 例えば、人々は与えられた富のもとで、どれだけ消費すべきか判断する。制御変数を選ぶことは、次の状態を選択することでもある。ただし、一般に次の状態は制御変数だけではなく他の要因によっても影響を受ける。
r {\displaystyle r} はマルコフ過程なので、問題は動的計画法によって劇的に単純化される。ベルマン方程式は単に以下の形となる。
V ( a , r ) = max 0 ≤ c ≤ a { u ( c ) + β ∫ V ( ( 1 + r ) ( a − c ) , r ′ ) Q ( r , d μ r ) } . {\displaystyle V(a,r)=\max _{0\leq c\leq a}\{u(c)+\beta \int V((1+r)(a-c),r')Q(r,d\mu _{r})\}.}
ある一般的な仮定のもとで、結果として得られる最適な方策関数 g ( a , r ) {\displaystyle g(a,r)} は可測となる。
マルコフ的なショックを伴い、主体が事後に選択を行うような一般的な確率的時系列の最適化問題に対しては、ベルマン方程式は非常に良く似た形をとる。
V ( x , z ) = max c ∈ Γ ( x , z ) F ( x , c , z ) + β ∫ V ( T ( x , c ) , z ′ ) d μ z ( z ′ ) . {\displaystyle V(x,z)=\max _{c\in \Gamma (x,z)}F(x,c,z)+\beta \int V(T(x,c),z')d\mu _{z}(z').}